循環的複雑性

循環的複雑度は、プログラムの複雑度を示すために使用されるソフトウェア メトリックです。これは、プログラムのソース コードを通る線形独立パスの数を定量的に測定するものです。これは、1976 年に Thomas J. McCabe, Sr. によって開発されました。

循環的複雑度は、プログラムの制御フロー グラフを使用して計算されます。グラフのノードは、プログラムの分割できないコマンドのグループに対応し、 2 番目のコマンドが最初のコマンドの直後に実行される可能性がある場合は、有向エッジが2 つのノードを接続します。循環的複雑度は、プログラム内の 個々の関数、モジュール、メソッド、またはクラスにも適用できます。

最初に提案したマッケイブによって基底パステストと呼ばれるテスト戦略の1 つは、プログラム内の各線形独立パスをテストすることです。この場合、テストケースの数はプログラムのサイクロマティック複雑度に等しくなります。^[1]

ソース コードセクションの循環的複雑度を定義する方法は複数あります。一般的な方法の 1 つは、その中の線形独立パスの数です。内の任意のパスのエッジ セットがの一部のサブセット内のパスのエッジ セットの和集合でない場合、パスのセットは線形独立です。ソース コードに制御フロー ステートメント(条件または決定ポイント) が含まれていない場合、コードを通過するパスは 1 つしかないため、複雑度は 1 になります。コードに単一条件のIF ステートメントが1 つある場合、コードを通過するパスは 2 つあります。1 つは IF ステートメントが TRUE の場合で、もう 1 つは FALSE の場合です。この場合、複雑度は 2 になります。ネストされた 2 つの単一条件 IF、または 2 つの条件を持つ 1 つの IF では、複雑度は 3 になります。 ${\displaystyle S}$${\displaystyle P}$${\displaystyle S}$${\displaystyle S/P}$

プログラムの循環的複雑度を定義する別の方法は、制御フローグラフを見ることです。これは、プログラムの基本ブロックを含む有向グラフで、制御が最初のブロックから2番目のブロックに渡される場合、2つの基本ブロックの間にエッジがあります。複雑度Mは次のように定義されます^[2]

$${\displaystyle M=E-N+2P,}$$

どこ

• E = グラフのエッジの数。
• N = グラフのノード数。
• P =連結成分の数。

元々提案されていたように、この別の定式化は、各出口点が入口点に接続されているグラフを使用することです。この場合、グラフは強く接続されています。ここで、プログラムの循環的複雑度は、そのグラフの循環数（最初のベッティ数とも呼ばれます）に等しく、次のように定義されます^[2] $${\displaystyle M=E-N+P.}$$

これは、グラフ内に存在する線形独立サイクルの数を計算するものと見ることができます。線形独立サイクルとは、それ自体の中に他のサイクルを含まないサイクルのことです。各終了ポイントはエントリ ポイントにループバックするため、各終了ポイントには少なくとも 1 つのサイクルが存在します。

単一のプログラム（またはサブルーチンやメソッド）の場合、Pは常に1に等しい。単一のサブルーチンのより単純な式は^{[3]である。} $${\displaystyle M=E-N+2.}$$

循環的複雑度は、複数のプログラムまたはサブプログラムに同時に適用される場合があります (たとえば、クラス内のすべてのメソッド)。このような場合、P は問題となるプログラムの数に等しくなり、各サブプログラムはグラフの切断されたサブセットとして表示されます。

McCabe は、エントリ ポイントと終了ポイントが 1 つしかない構造化プログラムのサイクロマティック複雑度は、そのプログラムに含まれる決定ポイント (if 文または条件ループ) の数に 1 を加えた数に等しいことを示した。これは、最も低いマシン レベルの命令でカウントされる決定ポイントにのみ当てはまる。^[4]のような高水準言語に見られる複合述語を含む決定は、IF cond1 AND cond2 THEN ...含まれる述語変数でカウントされる必要がある。この例では、マシン レベルでは と同等であるため、決定ポイントを 2 つカウントする必要がある。IF cond1 THEN IF cond2 THEN ...[ ^{2] [5]}

循環的複雑度は、複数の終了点を持つプログラムに拡張されることがあります。この場合、それは に等しくなります。ここで は プログラム内の決定点の数、s は終了点の数です。^{[5] [6]}$${\displaystyle \pi -s+2,}$$${\displaystyle \pi}$

グラフの偶数サブグラフ (オイラーサブグラフとも呼ばれる) は、すべての頂点が偶数個の辺に接続されているグラフです。このようなサブグラフは、サイクルと孤立した頂点の結合です。サブグラフは、その辺の集合で識別されます。これは、完全なグラフのすべての頂点を含む偶数サブグラフのみを考慮することと同じです。

グラフのすべての偶数部分グラフの集合は対称差に関して閉じており、したがってGF(2)上のベクトル空間として見ることができます。このベクトル空間はグラフのサイクル空間と呼ばれます。グラフのサイクロマティック数は、この空間の次元として定義されます。GF(2) には 2 つの要素があり、サイクル空間は必然的に有限であるため、サイクロマティック数はサイクル空間の要素数の2 対数にも等しくなります。

サイクル空間の基底は、まずグラフの全域森を固定し、次に森にない1つの辺とその辺の端点を結ぶ森のパスによって形成されるサイクルを考慮することで簡単に構築できます。これらのサイクルはサイクル空間の基底を形成します。サイクロマティック数は、グラフの最大全域森にない辺の数にも等しくなります。グラフの最大全域森の辺の数は、頂点の数から要素の数を引いた数に等しいため、この式はサイクロマティック数を定義します。^[7]${\displaystyle E-N+P}$

循環的複雑度は、相対ベッチ数、つまり相対ホモロジー群の大きさとして定義することもできます。

$${\displaystyle M:=b_{1}(G,t):=\operatorname {rank} H_{1}(G,t),}$$

これは、「グラフGの最初のホモロジーグループの、ターミナル ノードtに対するランク」と読みます。これは、「フロー グラフのエントリから出口までの線形独立パスの数」を技術的に表現したものです。

• 「線形独立」はホモロジーに対応し、バックトラックは二重にカウントされません。
• 「パス」は第1ホモロジーに対応します（パスは1次元オブジェクトです）。
• 「相対」とは、パスがエントリ ポイント (または終了ポイント) で始まり、終了する必要があることを意味します。

この循環的複雑度は計算可能です。また、与えられたコンポーネントの終端ノードを特定したり、出口と入口を結ぶパスを描画したりすることで、絶対ベッチ数を介して計算することもできます。新しい拡張グラフは、 ${\displaystyle {\tilde {G}}}$$${\displaystyle M=b_{1}({\tilde {G}})=\operatorname {rank} H_{1}({\tilde {G}}).}$$

これはホモトピーを介して計算することもできます。(連結された) 制御フロー グラフがと呼ばれる1 次元CW 複合体であると考えられる場合、の基本群はになります。 の値は循環的複雑度です。基本群は、ホモトピーまでのグラフを通るループの数を数え、予想どおりに整列します。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle \pi _{1}(X)\cong \mathbb {Z} ^{*n}}$${\displaystyle n+1}$

トム・マッケイブは、国土安全保障省向けの プレゼンテーション「リスクを特定するためのソフトウェア品質メトリクス」^{[8]で、循環的複雑性の次の分類を紹介しました。}

• 1 - 10: 手順が簡単で、リスクが少ない
• 11 - 20: より複雑、中程度のリスク
• 21 - 50: 複雑、高リスク
• > 50: テスト不可能なコード、非常に高いリスク

McCabe の元々の応用の 1 つは、プログラム開発中にルーチンの複雑さを制限することでした。彼は、プログラマーが開発中のモジュールの複雑さを数え、モジュールのサイクロマティック複雑度が 10 を超える場合はモジュールを小さなモジュールに分割することを推奨しました。 ^{[2]この方法は、} NIST構造化テスト方法論で採用されました。この方法では、McCabe の最初の発表以来、10 という数字がかなりの裏付けとなる証拠を得ていることが観察されました。ただし、状況によっては制限を緩和し、15 までの複雑さを持つモジュールを許可することが適切である場合もあると指摘しました。この方法論では、合意された制限を超える理由が時々あることを認めていたため、推奨事項を「各モジュールについて、サイクロマティック複雑度を [合意された制限] に制限するか、制限を超えた理由を文書で説明してください」と表現しました。^[9]

マッケイブの 1976 年の論文の第 6 節は、マッケイブが特定したサブグラフの観点から、非構造化プログラムの制御フロー グラフ (CFG) がどのように見えるかを決定することに関するものです。(詳細については、構造化プログラム定理を参照してください。) マッケイブは、そのセクションの結論として、特定のプログラムが構造化プログラミングの理想にどれだけ近いか、つまりその「構造化度」を数値的に測定する方法を提案しました。マッケイブは、この目的のために考案した測定方法を本質的複雑性と呼びました。^[2]

この尺度を計算するには、単一の入口と単一の出口を持つサブグラフを特定することによって元の CFG を反復的に縮小し、それらを単一のノードに置き換えます。この縮小は、人間がより大きなコードからサブルーチンを抽出する場合に行うことに相当します。(今日では、このようなプロセスはリファクタリングという包括的な用語に含まれます。) McCabe の縮小方法は、グラフ理論で使用されるコンポーネントへの凝縮の一般化と見なされたため、後に一部の教科書で凝縮と呼ばれました。^[10]プログラムが構造化されている場合、McCabe の縮小/凝縮プロセスにより、単一の CFG ノードに縮小されます。対照的に、プログラムが構造化されていない場合、反復プロセスにより、縮小できない部分が特定されます。McCabe によって定義された本質的な複雑性尺度は、この縮小できないグラフの循環的複雑性にすぎないため、すべての構造化プログラムでは正確に 1 になりますが、非構造化プログラムでは 1 より大きくなります。^{[9] : 80}

循環的複雑度のもう 1 つの応用は、特定のモジュールの完全なテスト カバレッジを達成するために必要なテスト ケースの数を決定することです。

これは、特定のモジュールの 循環的複雑度Mの 2 つの特性により有用です。

• M は、完全な分岐カバレッジを達成するために必要なテストケースの数の上限です。
• M は、制御フロー グラフ (CFG) を通るパスの数の下限です。各テスト ケースが 1 つのパスを取ると仮定すると、パス カバレッジを達成するために必要なケースの数は、実際に取ることができるパスの数と等しくなります。ただし、一部のパスは不可能な場合があるため、CFG を通るパスの数はパス カバレッジに必要なテスト ケースの数の上限であることは明らかですが、この後者の数 (可能なパスの数) はMより少ない場合があります。

上記の 3 つの数値はすべて同じになる場合があります: 分岐カバレッジ、サイクロマティック複雑度、パスの数。 ${\displaystyle \leq}$${\displaystyle \leq}$

たとえば、2 つの連続した if-then-else ステートメントで構成されるプログラムを考えてみます。

c1 ()の場合、 f1 ();それ以外の場合はf2 (); 
    

    

c2 ()の場合、 f3 ();それ以外の場合はf4 (); 
    

    

この例では、完全なブランチ カバレッジを達成するには 2 つのテスト ケースで十分ですが、完全なパス カバレッジを達成するには 4 つのテスト ケースが必要です。プログラムの循環的複雑度は 3 です (プログラムの強く接続されたグラフには 9 つのエッジ、7 つのノード、および 1 つの接続されたコンポーネントが含まれているため) ( 9 − 7 + 1 )。

一般的に、モジュールを完全にテストするには、モジュールのすべての実行パスを実行する必要があります。これは、複雑度の高い数値を持つモジュールは、コード内のパスの数が多いことを意味するため、複雑度の低い数値を持つモジュールよりも多くのテスト作業が必要であることを意味します。また、複雑度の高いモジュールは、プログラマがさまざまなパスとそれらのパスの結果を理解する必要があるため、理解が難しくなることも意味します。

残念ながら、プログラムですべての可能なパスをテストすることは必ずしも現実的ではありません。上記の例を考えると、if-then-else ステートメントが追加されるたびに、可能なパスの数は 2 倍に増えます。プログラムがこのように大きくなると、すべてのパスをテストすることが非現実的になるポイントにすぐに到達します。

NIST構造化テスト方法論などで採用されている一般的なテスト戦略の1つは、モジュールのサイクロマティック複雑度を使用して、モジュールを十分にカバーするために必要なホワイトボックステストの数を決定することです。ほとんどの場合、このような方法論によれば、モジュールには少なくともそのサイクロマティック複雑度と同じ数のテストが必要です。ほとんどの場合、このテストの数は、関数の関連するパスをすべて実行するのに適しています。^[9]

正確なテストを行うために単なる分岐カバレッジ以上のものを必要とする関数の例として、上記の関数を再考してみましょう。ただし、バグが発生しないようにするには、またはのいずれかを呼び出すコードはf1()、f3()もう一方を呼び出す必要があるものとします。^[a]との結果が独立していると仮定するとc1()、c2()上記の関数にはバグが含まれます。分岐カバレッジを使用すると、次のテスト ケースのように、メソッドを 2 つのテストだけでテストできます。

• c1()trueを返し、c2()trueを返します
• c1()falseを返し、c2()falseを返す

どちらの場合もバグは発生しません。ただし、サイクロマティック複雑度を使用して必要なテストの数を示すと、その数は 3 に増加します。したがって、次のパスのいずれかをテストする必要があります。

• c1()trueを返し、c2()falseを返す
• c1()falseを返し、c2()trueを返す

どちらのテストでもバグが明らかになります。

複数の研究で、McCabe の循環的複雑度と関数またはメソッドで発生する欠陥の頻度との相関関係が調査されています。^[11] いくつかの研究^[12]では、循環的複雑度と欠陥の間に正の相関関係があることがわかっています。つまり、最も複雑度の高い関数とメソッドには、最も多くの欠陥が含まれる傾向があります。ただし、循環的複雑度とプログラム サイズ (通常はコード行数で測定) との相関関係は、何度も実証されています。Les Hatton は^[13]、複雑度にはコード行数と同じ予測能力があると主張しています。プログラム サイズを制御した研究 (つまり、複雑度は異なるがサイズが類似しているモジュールの比較) は、一般的に結論が出にくく、多くの研究で有意な相関関係が見つからなかったのに対し、相関関係が見つかっています。一部の研究者は、相関関係が見つからなかった研究で使用された方法の妥当性を疑問視しています。^[14]この関係が存在する可能性は高いですが、実際には簡単に使用できません。^[15]プログラム サイズは商用ソフトウェアの制御可能な機能ではないため、McCabe の数値の有用性は疑問視されています。^[11]この観察の本質は、大規模なプログラムはより複雑になり、より多くの欠陥を持つ傾向があるということです。コードの循環的複雑度を減らすことで、そのコード内のエラーやバグの数が減ることは証明されていません。しかし、 ISO 26262などの国際安全規格では、コードの複雑度を低く抑えるコーディングガイドラインを義務付けています。^[16]

• プログラミングの複雑さ
• 複雑さの罠
• コンピュータプログラム
• コンピュータプログラミング
• 制御フロー
• 意思決定から意思決定への道
• 設計述語
• 本質的な複雑さ（「構造化度」の数値的尺度）
• ハルステッド複雑性尺度
• ソフトウェアエンジニアリング
• ソフトウェアテスト
• 静的プログラム解析
• 保守性

• Polyspace による循環的複雑度メトリックの生成
• 将来のソフトウェアの信頼性を向上させる経験主義の役割
• McCabe の循環的複雑性とそれを使わない理由