Цикломатическая сложность

Цикломати́ческая сло́жность програ́ммы (англ. Cyclomatic complexity of a program) — структурная (или топологическая) мера сложности программ, используемая для измерения качества программного обеспечения, основанная на методах статического анализа кода. ЦСП равна увеличенному на единицу цикломатическому числу графа программы.

Она была разработана Томасом Дж. Мак-Кейбом в 1976 году; он использовал эти показатели сложности для программ. Он производил непосредственные численные измерения для линейно независимых путей в исходных кодах программ. Концепция, но не метод, отчасти похож на измерение сложности с помощью теста удобочитаемости Флеша-Кинкейда^[англ.] для общего текста.

При вычислении цикломатической сложности используется граф потока управления программы: узлы графа соответствуют неделимым группам команд программы и ориентированным рёбрам, каждый из которых соединяет два узла и соответствует двум командам, вторая из которых может быть выполнена сразу после первой. Цикломатическая сложность может также быть применена для отдельных функций, модулей, методов или классов в пределах программы.

Эта стратегия тестирования называется основным маршрутом тестирования Мак-Кейба, который первым предложил его. Это тестирование каждого линейного независимого маршрута через программу; в этом случае, число тестов должно быть равно цикломатической сложности программы.^[1]

Описание

Цикломатическая сложность части программного кода — количество линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек ветвления или циклов, то сложность равна единице, поскольку, есть только единственный маршрут через код. Если код имеет единственный оператор IF, содержащий простое условие, то существует два пути через код: один если условие оператора IF имеет значение TRUE и один — если FALSE.

Математически цикломатическая сложность структурированной программы^[2] определяется с помощью ориентированного графа, узлами которого являются блоки программы, соединенные рёбрами, если управление может переходить с одного бока на другой. Тогда сложность определяется как:^[3]:

M = E − N + 2P,

где:

M = цикломатическая сложность,

E = количество рёбер в графе,

N = количество узлов в графе,

P = количество компонент связности.

В другой формулировке используется граф, в котором каждая точка выхода соединена с обратной — точкой входа. В этом случае говорят, что граф будет сильносвязанным и цикломатическая сложность программы будет равняться цикломатическому числу этого графа (также известному как first Betti number (англ.)), которое определяется как:^[3]

M = E − N + P

Это может рассматриваться как вычисление числа линейно независимых циклов, которые существуют в графе, то есть тех циклов, которые не содержат в себе других циклов. Надо учитывать, что каждая точка выхода из цикла становится точкой входа в него, то есть по крайней мере одна итерация его для каждой точки выхода.

Для простой программы, или подпрограммы, или метода P всегда эквивалентно 1. Цикломатическая сложность может, тем не менее, применяться к некоторым таким программам или подпрограммам (например, ко всем методам в классе), в таком случае P эквивалентен числу программ, о которых идёт речь, как о каждой подпрограмме, проявляющейся как разрозненное подмножество графа.

Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек решения (то есть, if операторных или условных циклов), содержащихся в этой программе, плюс один.^[3]^[4]

Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна:^[4]^[5]

π − s + 2

где:

π — число точек решения в программе,

s — число точек выхода.

Формальное определение

Формально, цикломатическая сложность может быть определена, как относительное число Бетти, как размер относительнооднородной группы:

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

Это читается, как «первый однородный граф G, относительно терминального узла t». Этот технический путь произносится, как «число линейно независимых маршрутов через граф от входа к выходу», где:

«линейно независимый» соответствует однородности и означает, что один не возвращается в исходное состояние двойного счета;
«маршрут» соответствует нальной однородности: маршруту соответствует одномерный объект;
«относительно» означает, что путь должен начаться и закончится в точке входа или выхода, соответственно.

Это соответствие интуитивно понятно как цикломатическая вложенность, и может быть вычислено как указанно выше.

Кроме того, его можно вычислить через абсолютное число Бетти (абсолютно однородное — не относительное) определяющее все терминальные узлы данного компонента (или равно, получение маршрутов соединяющих входы с выходами), в этом случае (вызов нового, расширенного графа ${\tilde {G}}$ , которым он является) получаем:

M=b_{1}({\tilde {G}})=\operatorname {rank} \,H_{1}({\tilde {G}})

Это соответствие характеризуется цикломатической сложностью как «количество циклов плюс количество компонентов».

Этимология (происхождение названия)

Название цикломатическая сложность может попервоначалу показаться не являющимся целостным, но это не так, так как эта метрика не только считает циклы в программе. Она должна быть первостепенно заинтересована в подсчёте количества других циклов, тех, которые контролируются по построенному по программе графу, которые заключаются в присутствии веток возврата (ветки от выходного узла к входному), которые выявляются при построении графа.^[3]

Применение

Ограничение сложности при разработке

Одно из оригинальных предложений Мак-Кейба в том, что необходимо ограничивать сложность программ в течение их разработки; он рекомендует, чтобы программистов обязывали считать сложность разрабатываемых ими модулей, и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит десять.^[3] Эта практика была адаптирована НИСТ-ом для методологии структурного тестирования. С помощью этих наблюдений, со времени исходной публикации Мак-Кейба, счёт от десяти считается, что преемственная надёжность подтверждена. В некоторых случаях может быть более целесообразны ослабленные ограничения и разрешить модули со сложностью выше, чем 15. Методологически признано, что существуют случайные причины, выводящие за рамки согласованного лимита, и это сформулировано как рекомендация: "Для каждого модуля, либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен".

Мак-Кейб^[6]:

Для каждого модуля, либо ограничивай цикломатическую сложность (до оговоренного предела), либо предоставляй запись, поясняющую, почему ограничение должно быть превышено.

Оригинальный текст (англ.)
For each module, either limit cyclomatic complexity to [the agreed-upon limit] or provide a written explanation of why the limit was exceeded.

Применение при тестировании программного обеспечения

Другое применение цикломатической сложности — при детерминизме числа проведённых тестов, необходимых для достижения тщательного покрытия тестированием модуля.

Он полезен, поскольку цикломатическая сложность M имеет два свойства, для конкретного модуля:

M — верхняя граница для числа произведённых тестов, которые необходимо достичь для полного покрытия ветки;
M — пониженная граница для числа маршрутов через контролируемый поток графа (КПГ).

Допустим, тест применяется каждый раз для единственного маршрута, тогда необходимое количество раз применений теста определяется числом покрытия, равного числу путей, которые действительно могут быть использованы при работе программы.

Но некоторые пути могут быть невозможными, так что, число путей через КПГ — это, несомненно, верхняя граница числа тестов, для обеспечения покрытия пути (возможного пути), чей номер идёт последним, которое иногда может быть меньше чем M.

Все три вышеуказанные числа могут быть равны: покрытие ветки $\leq$ cyclomatic complexity $\leq$ количества путей.

Для примера рассмотрим нижеприведённую программу, состоящую из последовательного применения двух операторов if-then-else.

if( c1() )
   f1();
else
   f2();

if( c2() )
   f3();
else
   f4();

Связность

Корреляция числа дефектов

Сложность больше 50 означает очень высокий риск и практически не тестируемый код.^[7]

См. также

Примечания

↑ A J Sobey. Основной маршрут тестирования (неопр.). Архивировано 26 апреля 2012 года.
↑ Here «structured» means in particular «with a single exit (return statement) per function».
↑ ¹ ² ³ ⁴ ⁵ McCabe (1976). "A Complexity Measure" ( (недоступная ссылка)). IEEE Transactions on Software Engineering: 308—320. {{cite journal}}: Неизвестный параметр |month= игнорируется (справка)
↑ ¹ ² Belzer, Kent, Holzman and Williams. Encyclopedia of Computer Science and Technology. — CRC Press, 1992. — P. 367–368.
↑ Harrison (October 1984). "Applying Mccabe's complexity measure to multiple-exit programs". Software: Practice and Experience. J Wiley & Sons.
↑ Мак-Кейб. Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric (англ.). Дата обращения: 3 июня 2010. Архивировано 26 апреля 2012 года.
↑ Цикломатическая сложность

[1] A J Sobey. Основной маршрут тестирования (неопр.). Архивировано 26 апреля 2012 года.

[2] Here «structured» means in particular «with a single exit (return statement) per function».

[mccabe76-3] ¹ ² ³ ⁴ ⁵ McCabe (1976). "A Complexity Measure" ( (недоступная ссылка)). IEEE Transactions on Software Engineering: 308—320. {{cite journal}}: Неизвестный параметр |month= игнорируется (справка)

[ecst-4] ¹ ² Belzer, Kent, Holzman and Williams. Encyclopedia of Computer Science and Technology. — CRC Press, 1992. — P. 367–368.

[harrison-5] Harrison (October 1984). "Applying Mccabe's complexity measure to multiple-exit programs". Software: Practice and Experience. J Wiley & Sons.

[6] Мак-Кейб. Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric (англ.). Дата обращения: 3 июня 2010. Архивировано 26 апреля 2012 года.

[7] Цикломатическая сложность

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Цикломатическая сложность

Содержание