Цикломатическая сложность - это метрика программного обеспечения, используемая для обозначения сложности программы . Это количественная мера количества линейно независимых путей в исходном коде программы . Он был разработан Томасом Дж. МакКейбом-старшим в 1976 году.
Цикломатическая сложность вычисляется с использованием графа потока управления программы: узлы графа соответствуют неделимым группам команд программы, а направленное ребро соединяет два узла, если вторая команда может быть выполнена сразу после первой команды. Цикломатическая сложность также может применяться к отдельным функциям , модулям , методам или классам в программе.
Один тестирование стратегии, называется основа тестирования пути по МакКейбам , кто первый предложил это, чтобы проверить каждый линейно независимый путь через программу; в этом случае количество тестовых примеров будет равно цикломатической сложности программы. [1]
Описание
Определение
Цикломатическая сложность раздела исходного кода - это максимальное количество линейно независимых путей внутри него - где «линейно независимый» означает, что каждый путь имеет по крайней мере одно ребро, которое не находится ни в одном из других путей. Например, если исходный код не содержит операторов потока управления (условных выражений или точек принятия решений), сложность будет равна 1, поскольку в коде будет только один путь. Если бы в коде был один оператор IF с одним условием, в коде было бы два пути: один, где оператор IF принимает значение ИСТИНА, а другой, где он оценивается как ЛОЖЬ, поэтому сложность будет равна 2. Два вложенных оператора IF с одним условием , или один IF с двумя условиями, даст сложность 3.
Математически цикломатическая сложность структурированной программы [a] определяется со ссылкой на граф потока управления программы, ориентированный граф, содержащий основные блоки программы, с границей между двумя базовыми блоками, если управление может переходить от от первого ко второму. Сложность M тогда определяется как [2]
- M = E - N + 2 P ,
где
- E = количество ребер графа.
- N = количество узлов графа.
- P = количество подключенных компонентов .
Альтернативная формулировка - использовать график, на котором каждая точка выхода связана с точкой входа. В этом случае граф является сильно связным , а цикломатическая сложность программы равна цикломатическому числу его графа (также известному как первое число Бетти ), которое определяется как [2]
- М = Е - Н + Р .
Это можно рассматривать как вычисление количества линейно независимых циклов , существующих в графе, то есть тех циклов, которые не содержат других циклов внутри себя. Обратите внимание: поскольку каждая точка выхода возвращается к точке входа, существует по крайней мере один такой цикл для каждой точки выхода.
Для отдельной программы (или подпрограммы, или метода) P всегда равно 1. Таким образом, более простая формула для одной подпрограммы:
- M = E - N + 2. [3]
Однако цикломатическая сложность может применяться к нескольким таким программам или подпрограммам одновременно (например, ко всем методам в классе), и в этих случаях P будет равно количеству рассматриваемых программ, поскольку каждая подпрограмма появится как отключенное подмножество графика.
МакКейб показал, что цикломатическая сложность любой структурированной программы только с одной точкой входа и одной точкой выхода равна количеству точек принятия решения (т. Е. Операторов «если» или условных циклов), содержащихся в этой программе, плюс один. Однако это верно только для точек принятия решения, подсчитываемых в самых нижних командах машинного уровня. [4] Решения, включающие составные предикаты, подобные тем, которые встречаются в языках высокого уровня, например, IF cond1 AND cond2 THEN ...
должны учитываться в терминах задействованных переменных предиката, то есть в этом примере нужно подсчитывать две точки принятия решения, потому что на уровне машины это эквивалентно IF cond1 THEN IF cond2 THEN ...
. [2] [5]
Цикломатическая сложность может быть расширена до программы с несколькими точками выхода; в этом случае он равен
- π - s + 2,
где π - количество точек принятия решения в программе, а s - количество точек выхода. [5] [6]
Объяснение в терминах алгебраической топологии
Даже подграф графа (также известный как эйлеровый подграф ) является одним , где каждая вершина падает с четным числом ребер; такие подграфы представляют собой объединение циклов и изолированных вершин. В дальнейшем четные подграфы будут отождествляться с их наборами ребер, что эквивалентно рассмотрению только тех четных подграфов, которые содержат все вершины полного графа.
Множество всех четных подграфов графа замкнуто относительно симметричной разности и, таким образом, может рассматриваться как векторное пространство над GF (2) ; это векторное пространство называется пространством циклов графа. Цикломатическое число графа определяется как размерность этого пространства. Поскольку GF (2) имеет два элемента и пространство циклов обязательно конечно, цикломатическое число также равно 2-логарифму числа элементов в пространстве циклов.
Базис для пространства циклов легко построить, сначала зафиксировав остовный лес графа, а затем рассмотрев циклы, образованные одним ребром не в лесу, и тропой в лесу, соединяющей концы этого ребра; эти циклы составляют основу пространства циклов. Следовательно, цикломатическое число также равно количеству ребер, не входящих в максимальный остовный лес графа. Поскольку количество ребер в максимальном остовном лесу графа равно количеству вершин минус количество компонентов, формулавыше для цикломатического числа следует. [7]
Для более склонных к топологии цикломатическая сложность может быть альтернативно определена как относительное число Бетти , размер группы относительной гомологии :
который читается как «ранг первой группы гомологий графа G относительно конечных узлов t ». Это технический способ обозначить «количество линейно независимых путей в потоковом графе от входа до выхода», где:
- «линейно независимый» соответствует гомологии и означает, что обратный отсчет не производится дважды;
- «пути» соответствуют первой гомологии: путь - это одномерный объект;
- «относительный» означает, что путь должен начинаться и заканчиваться в точке входа или выхода.
Это соответствует интуитивному представлению о цикломатической сложности и может быть рассчитано, как указано выше.
В качестве альтернативы, можно вычислить это через абсолютное число Бетти (абсолютная гомология - не относительная), идентифицировав (склеив вместе) все конечные узлы на данном компоненте (или, что эквивалентно, нарисовав пути, соединяющие выходы со входом), и в этом случае (вызов новый расширенный граф , что [ требуется пояснение ] ), получаем
Его также можно вычислить с помощью гомотопии . Если рассматривать граф потока управления как одномерный комплекс CW, называемый, То фундаментальная группа из будет . Значениецикломатическая сложность. Фундаментальная группа считает, сколько петель проходит через граф, вплоть до гомотопии, и, следовательно, согласуется с тем, что мы интуитивно ожидаем.
Это соответствует описанию цикломатической сложности как «количество петель плюс количество компонентов».
Приложения
Ограничение сложности во время разработки
Одно из оригинальных приложений МакКейба заключалось в ограничении сложности подпрограмм во время разработки программ; он рекомендовал программистам подсчитывать сложность разрабатываемых модулей и разбивать их на более мелкие модули всякий раз, когда цикломатическая сложность модуля превышает 10. [2] Эта практика была принята методологией структурированного тестирования NIST с замечанием, что, поскольку В первоначальной публикации МакКейба цифра 10 получила существенные подтверждающие доказательства, но что в некоторых обстоятельствах может быть целесообразно ослабить ограничения и разрешить модули со сложностью до 15. Поскольку методология признавала, что были случайные причины для выхода за рамки согласованный предел, он сформулировал свою рекомендацию как «Для каждого модуля либо ограничьте цикломатическую сложность до [согласованного предела], либо предоставьте письменное объяснение того, почему предел был превышен». [8]
Измерение «структурированности» программы
Раздел VI статьи МакКейба 1976 года посвящен определению того, как выглядят графы потока управления (CFG) неструктурированных программ в терминах их подграфов, которые МакКейб идентифицирует. (Подробнее об этой части см. В теореме о структурированной программе .) Маккейб заключает этот раздел, предлагая численную меру того, насколько близка к идеалу структурированного программирования данная программа, то есть ее «структурированность» с использованием неологизма МакКейба. Маккейб назвал изобретенную для этой цели меру существенной сложностью . [2]
Чтобы вычислить эту меру, исходный CFG итеративно сокращается путем определения подграфов, которые имеют точку с одним входом и точку с одним выходом, которые затем заменяются одним узлом. Это сокращение соответствует тому, что сделал бы человек, если бы он извлек подпрограмму из более крупного фрагмента кода. (В настоящее время такой процесс подпадал бы под общий термин рефакторинга .) Метод редукции МакКейба позже в некоторых учебниках был назван сгущением , поскольку он рассматривался как обобщение сгущения на компоненты, используемые в теории графов . [9] Если программа структурирована, то процесс редукции / уплотнения МакКейба сводит ее к одному узлу CFG. Напротив, если программа не структурирована, итерационный процесс идентифицирует несократимую часть. Существенная мера сложности, определенная МакКейбом, - это просто цикломатическая сложность этого неприводимого графа, поэтому она будет в точности 1 для всех структурированных программ, но больше единицы для неструктурированных программ. [8] : 80
Последствия для тестирования программного обеспечения
Другое применение цикломатической сложности - определение количества тестовых примеров, необходимых для достижения полного тестового покрытия конкретного модуля.
Это полезно из-за двух свойств цикломатической сложности M для конкретного модуля:
- M - это верхняя граница количества тестовых примеров, необходимых для достижения полного покрытия ветки .
- M - это нижняя граница количества путей через граф потока управления (CFG). Предполагая, что каждый тестовый пример использует один путь, количество случаев, необходимых для достижения покрытия пути, равно количеству путей, которые фактически могут быть пройдены. Но некоторые пути может оказаться невозможным, так что, хотя число путей через CFG, очевидно , верхняя граница количества тестов , необходимых для покрытия пути, это последнее число ( возможных путей) иногда меньше М .
Все три приведенных выше числа могут быть равны: покрытие филиала цикломатическая сложность количество путей.
Например, рассмотрим программу, состоящую из двух последовательных операторов if-then-else.
если ( c1 ()) f1 (); иначе f2 ();если ( c2 ()) f3 (); иначе f4 ();
В этом примере двух тестовых примеров достаточно для достижения полного покрытия ветки, а четырех необходимо для полного покрытия пути. Цикломатическая сложность программы составляет 3 (поскольку сильно связный граф для программы содержит 9 ребер, 7 узлов и 1 компонент связности) (9-7 + 1).
В общем, чтобы полностью протестировать модуль, должны быть проверены все пути выполнения через модуль. Это означает, что для модуля с высоким числом сложности требуется больше усилий по тестированию, чем для модуля с более низким значением, поскольку более высокое число сложности указывает на большее количество путей прохождения кода. Это также означает, что модуль с более высокой сложностью труднее понять программисту, поскольку программист должен понимать различные пути и результаты этих путей.
К сожалению, не всегда удобно проверять все возможные пути прохождения программы. Рассматривая приведенный выше пример, каждый раз, когда добавляется дополнительный оператор if-then-else, количество возможных путей увеличивается в 2 раза. По мере того, как программа растет таким образом, она быстро достигает точки, когда проверка всех путей становится непрактично.
Одна из распространенных стратегий тестирования, поддерживаемая, например, методологией структурированного тестирования NIST, заключается в использовании цикломатической сложности модуля для определения количества тестов белого ящика , необходимых для получения достаточного покрытия модуля. Почти во всех случаях, согласно такой методологии, модуль должен иметь как минимум столько тестов, сколько его цикломатическая сложность; в большинстве случаев этого количества тестов достаточно для проверки всех соответствующих путей выполнения функции. [8]
В качестве примера функции, которая требует большего, чем просто покрытие ветвей для точного тестирования, снова рассмотрим приведенную выше функцию, но предположим, что во избежание возникновения ошибки любой код, который вызывает либо f1 (), либо f3 (), должен также вызывать другой. [b] Предполагая, что результаты c1 () и c2 () независимы, это означает, что функция, представленная выше, содержит ошибку. Покрытие ветвей позволит нам протестировать метод всего двумя тестами, и один из возможных наборов тестов будет тестировать следующие случаи:
c1()
возвращает истину иc2()
возвращает истинуc1()
возвращает ложь иc2()
возвращает ложь
Ни в одном из этих случаев ошибка не обнаружена. Если, однако, мы используем цикломатическую сложность для обозначения количества требуемых тестов, это число увеличивается до 3. Следовательно, мы должны протестировать один из следующих путей:
c1()
возвращает истину иc2()
возвращает ложьc1()
возвращает ложь иc2()
возвращает истину
Любой из этих тестов выявит ошибку.
Соотношение количества дефектов
В ряде исследований изучалась корреляция между цикломатическим числом сложности МакКейба и частотой дефектов, возникающих в функции или методе. [10] В некоторых исследованиях [11] обнаруживается положительная корреляция между цикломатической сложностью и дефектами: функции и методы, которые имеют наивысшую сложность, как правило, также содержат наибольшее количество дефектов. Однако корреляция между цикломатической сложностью и размером программы (обычно измеряемым в строках кода ) была продемонстрирована много раз. Лес Хаттон утверждал [12], что сложность обладает той же способностью к предсказанию, что и строки кода. Исследования, в которых учитывался размер программы (т. Е. Сравнение модулей, которые имеют разную сложность, но схожий размер), как правило, менее убедительны: многие не находят существенной корреляции, в то время как другие находят корреляцию. Некоторые исследователи, изучавшие эту область, сомневаются в достоверности методов, используемых в исследованиях, не обнаруживая корреляции. [13] Хотя это соотношение, вероятно, верно, его нелегко использовать. [14] Поскольку размер программы не является контролируемой функцией коммерческого программного обеспечения, полезность числа МакКейбса была поставлена под сомнение. [10] Суть этого наблюдения состоит в том, что более крупные программы имеют тенденцию быть более сложными и иметь больше дефектов. Доказано, что уменьшение цикломатической сложности кода уменьшает количество ошибок или ошибок в этом коде. Однако международные стандарты безопасности, такие как ISO 26262 , предписывают руководящие принципы кодирования, которые обеспечивают низкую сложность кода. [15]
Искусственный интеллект
Цикломатическая сложность также может использоваться для оценки семантической сложности программ искусственного интеллекта. [16]
Ультраметрическая топология
Цикломатическая сложность оказалась полезной в географическом и ландшафтно-экологическом анализе после того, как было показано, что ее можно реализовать на графиках ультраметрических расстояний. [17]
Смотрите также
- Сложность программирования
- Ловушка сложности
- Компьютерная программа
- Компьютерное программирование
- Поток управления
- Путь от решения к решению
- Предикаты проектирования
- Существенная сложность (числовая мера «структурированности»)
- Меры сложности Холстеда
- Программная инженерия
- Тестирование программного обеспечения
- Статический анализ программы
- Ремонтопригодность
Заметки
- ^ Здесь «структурированный» означает, в частности, «с одним выходом ( оператором возврата ) для каждой функции».
- ^ Это довольно распространенный тип состояния; рассмотрите возможность того, что f1 выделяет некоторый ресурс, который высвобождает f3.
Рекомендации
- ^ AJ Sobey. «Тестирование базового пути» .
- ^ а б в г д МакКейб (декабрь 1976 г.). «Мера сложности» . IEEE Transactions по разработке программного обеспечения (4): 308–320. DOI : 10.1109 / tse.1976.233837 .
- ^ Филип А. Лапланте (25 апреля 2007 г.). Что должен знать каждый инженер о программной инженерии . CRC Press. п. 176. ISBN. 978-1-4200-0674-2.
- ^ Фрикер, Себастьян (апрель 2018 г.). "Что такое цикломатическая сложность?" . froglogic GmbH . Проверено 27 октября 2018 года .
Чтобы вычислить графическое представление кода, мы можем просто дизассемблировать его ассемблерный код и создать граф, следуя правилам: ...
- ^ а б Белцер, Кент, Хольцман и Уильямс (1992). Энциклопедия компьютерных наук и технологий . CRC Press. С. 367–368.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Харрисон (октябрь 1984 г.). «Применение меры сложности Маккабе к программам с несколькими выходами». Программное обеспечение: практика и опыт . 14 (10): 1004–1007. DOI : 10.1002 / spe.4380141009 .
- ^ Дистель, Рейнхард (2000). Теория графов . Тексты для выпускников по математике 173 (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-98976-1.
- ^ а б в Артур Х. Уотсон; Томас Дж. МакКейб (1996). «Структурированное тестирование: методология тестирования с использованием метрики цикломатической сложности» (PDF) . Специальная публикация NIST 500-235.
- ^ Пол К. Йоргенсен (2002). Тестирование программного обеспечения: подход мастера, второе издание (2-е изд.). CRC Press. С. 150–153. ISBN 978-0-8493-0809-3.
- ^ а б Норман Э. Фентон; Мартин Нил (1999). «Критика моделей прогнозирования дефектов программного обеспечения» (PDF) . IEEE Transactions по разработке программного обеспечения . 25 (3): 675–689. CiteSeerX 10.1.1.548.2998 . DOI : 10.1109 / 32.815326 .
- ^ Шредер, Марк (1999). «Практическое руководство по объектно-ориентированным метрикам». ИТ-специалист . 1 (6): 30–36. DOI : 10.1109 / 6294.806902 . S2CID 14945518 .
- ^ Лес Хаттон (2008). «Роль эмпиризма в повышении надежности программного обеспечения будущего» . версия 1.1.
- ^ Кан (2003). Метрики и модели в инженерии качества программного обеспечения . Эддисон-Уэсли. С. 316–317. ISBN 978-0-201-72915-3.
- ^ Г.С. Черф (1992). «Исследование характеристик обслуживания и поддержки коммерческого программного обеспечения». Журнал качества программного обеспечения . 1 (3): 147–158. DOI : 10.1007 / bf01720922 . ISSN 1573-1367 .
- ^ ISO 26262-3: 2011 (en) Транспорт дорожный - Функциональная безопасность - Часть 3: Фаза концепции . Международная организация по стандартизации.
- ^ Пападимитриу, Fivos (2012). «Искусственный интеллект в моделировании сложности трансформации средиземноморского ландшафта». Компьютеры и электроника в сельском хозяйстве . 81 : 87–96. DOI : 10.1016 / j.compag.2011.11.009 .
- ^ Пападимитриу, Fivos (2013). «Математическое моделирование землепользования и ландшафтной сложности с ультраметрической топологией». Журнал науки о землепользовании . 8 (2): 234–254. DOI : 10.1080 / 1747423X.2011.637136 .
Внешние ссылки
- Создание показателей цикломатической сложности с помощью Polyspace
- Роль эмпиризма в повышении надежности программного обеспечения будущего
- Небольшой анализатор исходного кода C / C ++, использующий метрику циклометрической сложности (только для Windows, без исходного кода)
- Цикломатическая сложность Маккейба и почему мы ее не используем