Цикломатическая сложность (Cyclomatic Complexity)

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

Определение из книги Ли Копланда - “A Practitioner's Guide to Software Test Design”, Главы 10:

Цикломатическая сложность​ - это конечное минимальное количество независимых, нецикличных маршрутов (называемых основными маршрутами), которые могут образовывать все возможные линейные пути в программном модуле.

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

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

M = E − N + 2P,

где:

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

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

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

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

В другой формулировке используется граф, в котором каждая точка выхода соединена с точкой входа. В этом случае граф является сильносвязным, и цикломатическая сложность программы равна цикломатическому числу этого графа (также известному как первое число Бетти), которое определяется как

M = E − N + P.

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

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

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

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

π − s + 2,

где:

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

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

Применение:

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

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

○ M — оценка сверху для количества тестов, обеспечивающих покрытие условий (точек ветвления);

○ M — оценка снизу для количества маршрутов через граф потока управления и, таким образом, количества тестов для полного покрытия путей.

● В составе других метрик: используется в качестве одного из параметров в индексе удобства сопровождения (англ. maintainability index).

Источники:

● Types of Static Analysis Methods

● Software Testing - Static Testing

● Static program analysis

● What is Static Analysis

● Software Engineering - Control Flow Graph (CFG)

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

Доп. материал:

● Михаил Моисеев - “Формальные методы обеспечения качества ПО: Введение в статический анализ”

● Y.N. Srikant - “Control Flow Analysis”

● Levels in Data Flow Diagrams (DFD)

● Control Flow Graph (CFG)

● Static analysis tools

Dynamic -> White box

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

Глобально основных техник динамического тестирования методом белого ящика всего две:

1. Тестирование потока управления (Control Flow Testing);
2. Тестирование потока данных (Data Flow Testing).

Фактически, это динамическая часть одного цельного тестирования, статическая часть которого - анализ и построение графа, описывается в предыдущей теме про статический анализ, а на этом определяется целевое покрытие (Coverage Target), создаются соответствующие тест-кейсы, тесты исполняются и результаты выполнения тестов анализируются.

1. Уровни тестового покрытия в тестировании потока управления

Под “покрытием" имеется в виду отношение объема кода, который уже был проверен, к объему, который осталось проверить. В тестировании потока управления покрытие определяется в виде нескольких различных уровней. Заметим, что эти уровни покрытия представлены не по порядку. Это потому, что в некоторых случаях проще определить более высокий уровень покрытия, а затем определить более низкий уровень покрытия в условиях высокого.

100% покрытие операторов (Statement/node coverage). Оператор (statement) - это сущность языка программирования, обычно являющаяся минимальным неделимым исполняемым блоком (ISTQB). Покрытие операторов - это метод проектирования тестов методом белого ящика, который включает в себя выполнение всех исполняемых операторов (if, for и switch) в исходном коде как минимум один раз. Процентное отношение операторов, исполняемых набором тестов, к их общему количеству является метрикой покрытия операторов. Борис Бейзер написал: "тестирование, меньшее чем это [100% покрытие операторов], для нового программного обеспечения является недобросовестным и должно быть признано преступлением. …”. Несмотря на то, что это может показаться разумной идеей, на таком уровне покрытия может быть пропущено много дефектов и затруднен анализ покрытия некоторых управляющих структур. Покрытие операторов позволяет найти:

● Неиспользованные выражения (Unused Statements);

● Мертвый код (Dead Code);

● Неиспользуемые ветви (Unused Branches);

● Недостающие операторы (Missing Statements);

100% покрытие альтернатив/ветвей (Decision/branch/all-edges/basis path/DC/C2/ decision-decision-path/edge coverage). «Решение» - это программная точка, в которой control flow имеет два или более альтернативных маршрута (ветви). На этом уровне достаточно такого набора тестов, в котором каждый узел с ветвлением (альтернатива), имеющий TRUE или FALSE на выходе, выполняется как минимум один раз, таким образом, для покрытия по веткам требуется как минимум два тестовых примера. На данном уровне не учитываются логические выражения, значения компонент которых получаются вызовом функций. В отличие от предыдущего уровня покрытия данный метод учитывает покрытие условных операторов с пустыми ветками. Покрытие альтернатив не гарантирует покрытие всех путей, но при этом гарантирует покрытие всех операторов;

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

100% покрытие условий (Condition/Toggle Coverage). Рассматриваются только выражения с логическими операндами, например, AND, OR, XOR. На этом уровне достаточно такого набора тест-кейсов, в котором каждое условие, имеющее TRUE и FALSE на выходе, выполнено как минимум один раз. Покрытие условий обеспечивает лучшую чувствительность к control flow, чем decision coverage. Для обеспечения полного покрытия по данному методу каждая компонента логического условия в результате выполнения тестовых примеров должна принимать все возможные значения, но при этом не требуется, чтобы само логическое условие принимало все возможные значения, т.е. Condition Coverage не дает гарантии полного decision coverage;

100% покрытие условий + альтернатив (Decision + Condition coverage). На этом уровне тест-кейсы создаются для каждого условия и для каждой альтернативы, т.е. данный метод сочетает требования предыдущих двух методов - для обеспечения полного покрытия необходимо, чтобы как логическое условие, так и каждая его компонента приняла все возможные значения;

100% покрытия множественный условий (Multiple condition coverage). Для выявления неверно заданных логических функций был предложен метод покрытия по всем условиям. При данном методе покрытия должны быть проверены все возможные наборы значений компонент логических условий: условий, альтернатив и условий/альтернатив. Т.е. в случае n компонент потребуется 2^n тестовых примеров, каждый из которых проверяет один набор значений. Тесты, необходимые для полного покрытия по данному методу, дают полную таблицу истинности для логического выражения. Несмотря на очевидную полноту системы тестов, обеспечивающей этот уровень покрытия, данный метод редко применяется на практике в связи с его сложностью и избыточностью. Еще одним недостатком метода является зависимость количества тестовых примеров от структуры логического выражения. Кроме того, покрытие множественных условий не гарантирует покрытие всех путей;

Покрытие бесконечного числа путей. Если, в случае зацикливания, количество путей становится бесконечным, то имеет смысл существенно их сократить, ограничив количество циклов выполнения, что позволит уменьшить количество тестовых случаев. Первый вариант - не выполнять цикл совсем; второй - выполнить цикл один раз; третий - выполнить цикл n раз, где n - это небольшое значение, представляющее символическое количество повторений цикла; четвертый - выполнить цикл m раз, где m - максимальное количество повторений цикла. Кроме того, можно выполнить цикл m-1 и m+1 раз. Перед тем, как начинать тестирование потока управления, должен быть выбран соответствующий уровень покрытия;

100% покрытие путей (Path coverage). Проверяет каждый линейно независимый путь в программе, что означает, что число тестовых примеров будет эквивалентно цикломатической сложности программы. Для кода модулей без циклов количество путей, как правило, достаточно мало, поэтому на самом деле можно построить тест-кейсы для каждого пути. Для модулей с циклами количество путей может быть огромным, что представляет неразрешимую проблему тестирования.

Путь на самом деле является направлением, потоком выполнения, который следует за последовательностью инструкций. Он охватывает функцию от входа до точки выхода. Он охватывает statement, branch/decision coverage. Покрытие пути можно понять в следующих терминах:

● Loop coverage: используется для проверки того, что все циклы были выполнены и сколько раз они были выполнены. Цель этого метода покрытия - убедиться, что циклы соответствуют предписанным условиям и не повторяются бесконечно и не завершаются ненормально. Цикл тестирования направлен на мониторинг от начала до конца цикла. Ценным аспектом этой метрики является определение того, выполняются ли циклы while и for более одного раза, т.к. эта информация не сообщается другими метриками;

● Function coverage: показывает, вызывали ли вы каждую функцию или процедуру;

● Call coverage: показывает, выполняли ли вы каждый вызов функции. Гипотеза состоит в том, что ошибки обычно возникают в интерфейсах между модулями (вызывающая функция и вызываемая функция). Также известен как покрытие пары вызовов (call pair coverage);

7 вышеперечисленных уровней описываются в книге Копленда “A Practitioner's Guide to Software Test Design”, но можно найти и другие