← Назад ко всем статьям

Критические уроки NASA о cyclomatic complexity: почему простой код спасает жизни

Опубликовано

Как software metric стала критически важной для space missions после failures Boeing CST-100 Orbital Flight Test.

После критических software failures во время Boeing Crew Space Transportation (CST)-100 Orbital Flight Test главный инженер NASA Ralph Roe выразил опасение, что software testing requirements NASA могут быть недостаточными. Возможность серьезных ошибок, которые остаются незамеченными до flight, была неприемлемой.

Это привело NASA Engineering and Safety Center (NESC) к исследованию cyclomatic complexity и basis path testing в safety-critical software.

Что такое Cyclomatic Complexity?

Cyclomatic complexity - software metric, которая измеряет количество independent paths через code на основе его control flow graph. Можно думать об этом как о подсчете decision points: конструкции if, while, for и switch добавляют complexity.

Базовая формула:

Cyclomatic Complexity = Number of Decisions + 1

Function без conditional statements имеет complexity 1, потому что у нее один straight path. Добавьте один if, и complexity станет 2: один path, когда condition true, и другой, когда false.

Два nested single-condition if statements или один if с двумя conditions дают complexity 3.

Исследование NASA: real-world impact

NESC assessment рассмотрела три крупных software sets:

  • Space Launch System (SLS) Flight Software.

  • Core Flight Software (CFS) bundle и applications.

  • Autonomous Power Controller (APC) system.

Результаты показали, как быстро testing effort растет по мере усложнения functions.

Стоимость complexity во времени

NASA попросила APC developers выполнить basis path testing для functions с разными levels complexity. Зафиксированный total effort:

  • Complexity 5: 45 minutes.

  • Complexity 9: 1.65 hours.

  • Complexity 28: 31 hours.

Function с complexity 28 потребовала больше 30 hours testing, а developer оценил confidence в полном coverage только в 30%. Для lower-complexity functions confidence был близок к 100%.

Это была small practical evaluation, а не proof универсальной формулы, но она ясно показала burden, который highly complex control flow накладывает на testing.

История успеха SLS

Coding standard SLS Flight Software требовал cyclomatic complexity не выше 20. Units выше threshold должны были быть reworked или получить waiver, с exception для больших switch statements.

Результат - average complexity примерно 2.9 по SLS flight software. Был обработан только один waiver, касающийся части legacy guidance, navigation and control code.

Почему limit стал 15

После review NASA practices, military requirements, industry standards и academic research assessment team выбрала 15 как maximum cyclomatic complexity для safety-critical software.

Report отметил несколько reference points:

  • U.S. Air Force: complexity level 15-20.

  • Industry and academic examples, включая MISRA, AUTOSAR, HIS и JSF AV++: requirements в диапазоне 10-20.

  • Practical testing: lower complexity упрощает и ускоряет verification и testing.

Team также подчеркнула, что complexity нельзя использовать отдельно. Architectural complexity, code and requirements changes и defect density тоже важны.

Три типа Cyclomatic Complexity

Report обсуждает три common variants:

  • Standard (CC1): decisions + 1, basic measure.

  • Strict (CC2): считает individual conditions в compound Boolean expressions, делая metric stricter.

  • Modified (CC3): относится к multi-branch switch мягче, чем standard measure.

Assessment team не mandated один variant. Projects могут выбрать version под свои needs, но выбор должен быть consistent и justified.

Beyond the Numbers: что действительно важно

Дело не в line count

Function на 100 lines без decisions может иметь complexity 1, а function на 10 lines с nested conditions - гораздо более высокую complexity.

Lines of code не показывают cyclomatic complexity напрямую.

Architecture тоже важна

Даже simple functions могут быть problematic, если они highly interdependent. NASA подчеркнула, что нужно смотреть beyond function-level complexity и tracking factors:

  • Code churn: как часто меняется code.

  • Inter-module dependencies.

  • Architectural complexity.

  • Defect density и requirements changes.

Снижение complexity отдельных functions не должно делать overall architecture более tangled.

Testing revolution

NASA сравнила basis path testing с Modified Condition/Decision Coverage (MC/DC). В evaluated functions MC/DC:

  • Требовал на 30-50% less time для более complex cases.

  • Reduced redundant path testing.

  • Давал more robust approach для safety-critical software в сочетании с functional и requirements testing.

  • Уже был established в safety-critical aviation guidance вроде DO-178C.

MC/DC проверяет, что каждая condition в decision может independently affect outcome decision. Он стремится к strong coverage без необходимости проверять every possible combination of conditions.

Tools of the Trade

NASA рассмотрела tools, способные calculating или working with cyclomatic complexity.

Free Options

  • Unified Code Counter (UCC) from the University of Southern California.

  • Complexity metrics, доступные в некоторых IDEs и development toolchains.

Commercial Solutions

  • Scientific Toolworks’ Understand для CC1, CC2 и CC3 analysis и complexity visualizations.

  • Static analysis products вроде Coverity и CodeSonar.

  • Coverage tools вроде LDRA и VectorCAST для MC/DC testing.

Конкретный tool менее важен, чем consistent measurement и integration analysis в development workflow.

Alternative viewpoint

Не все в assessment team согласились, что bounding complexity - самый effective way улучшить code quality. Gerard Holzmann представил alternative viewpoint, сфокусированный на disciplined engineering practices:

  • Rigorous coding standards, aimed at risk reduction.

  • Один или preferably multiple strong static analyzers на every build.

  • All compiler warnings enabled at their highest level, with zero warnings produced.

  • Average assertion density at least 2%.

  • Tests, derived from higher-level requirements, alongside MC/DC coverage analysis.

Это важное напоминание: complexity threshold - guardrail, а не substitute for sound engineering.

Practical Recommendations

На основе findings NASA:

  1. Установите complexity limit 15 для safety-critical code.

  2. Оценивайте любую function выше limit по testability, maintainability и code quality.

  3. Используйте MC/DC testing для safety-critical functions вместе с functional и requirements testing.

  4. Track code churn, dependencies и architectural complexity.

  5. Run static analyzers на every build и держите compiler warnings at zero.

  6. Фокусируйтесь на reducing risk, а не просто satisfying style rule.

The Bottom Line

NASA study показала, что complex code не просто harder to read: его может быть dramatically harder to test with confidence. Когда software controls hazardous systems, manageable cyclomatic complexity становится частью mission assurance.

В следующий раз, когда захочется добавить “еще одно condition” в уже complex function, вспомните: simpler control flow делает thorough testing более achievable.

Source: NASA’s Cyclomatic Complexity and Basis Path Testing Study, report NASA/TM-20205011566, NESC document NESC-RP-20-01515.