NASA's Critical Lessons on Cyclomatic Complexity: Why Simple Code Saves Lives

How a software metric became crucial for space missions after Boeing’s CST-100 Orbital Flight Test failures.

After Boeing’s Crew Space Transportation (CST)-100 Orbital Flight Test experienced critical software failures, NASA Chief Engineer Ralph Roe raised concerns that NASA’s software testing requirements might be insufficient. The possibility of serious errors going undetected until flight was unacceptable.

This concern led the NASA Engineering and Safety Center (NESC) to study cyclomatic complexity and basis path testing in safety-critical software.

What Is Cyclomatic Complexity?

Cyclomatic complexity is a software metric that measures the number of independent paths through code based on its control flow graph. Think of it as counting decision points: constructs such as if, while, for, and switch add complexity.

The basic formula is:

Cyclomatic Complexity = Number of Decisions + 1

A function with no conditional statements has a complexity of 1 because it has one straight path. Add a single if statement, and the complexity becomes 2: one path when the condition is true and another when it is false.

Two nested single-condition if statements, or one if with two conditions, produce a complexity of 3.

The NASA Study: Real-World Impact

The NESC assessment examined three major software sets:

• Space Launch System (SLS) Flight Software.

• The Core Flight Software (CFS) bundle and applications.

• The Autonomous Power Controller (APC) system.

The results showed how quickly testing effort can grow as functions become more complex.

The Time Cost of Complexity

NASA asked APC developers to perform basis path testing on functions with different complexity levels. The documented total effort was:

• Complexity 5: 45 minutes.

• Complexity 9: 1.65 hours.

• Complexity 28: 31 hours.

The function with complexity 28 took more than 30 hours to test, and the developer estimated only 30% confidence that full coverage had been achieved. For the lower-complexity functions, the confidence estimate was close to 100%.

This was a small practical evaluation rather than proof of a universal formula, but it clearly demonstrated the burden that highly complex control flow can place on testing.

The SLS Success Story

The SLS Flight Software coding standard required cyclomatic complexity no higher than 20. Units above that threshold had to be reworked or receive a waiver, with an exception allowed for large switch statements.

The result was an average complexity of approximately 2.9 across the SLS flight software. Only one waiver was processed, covering part of the legacy guidance, navigation, and control code.

Why 15 Became the Limit

After reviewing NASA practices, military requirements, industry standards, and academic research, the assessment team selected 15 as the maximum cyclomatic complexity for safety-critical software.

The report noted several reference points:

• U.S. Air Force: a complexity level of 15–20.

• Industry and academic examples, including MISRA, AUTOSAR, HIS, and JSF AV++: requirements in the 10–20 range.

• Practical testing: lower complexity simplifies and accelerates verification and testing.

The team also stressed that complexity should not be used alone. Architectural complexity, code and requirements changes, and defect density matter too.

The Three Types of Cyclomatic Complexity

The report discusses three common variants:

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

• Strict (CC2): counts individual conditions in compound Boolean expressions, making the metric stricter.

• Modified (CC3): treats a multi-branch switch more leniently than the standard measure.

The assessment team did not mandate one variant. Projects can choose the version that fits their needs, but the choice should be consistent and justified.

Beyond the Numbers: What Really Matters

It Is Not About Line Count

A 100-line function with no decisions can have a complexity of 1, while a 10-line function with nested conditions can have much higher complexity.

Lines of code do not directly indicate cyclomatic complexity.

Architecture Matters Too

Even simple functions can be problematic when they are highly interdependent. NASA emphasized looking beyond function-level complexity and tracking factors such as:

• Code churn: how often code changes.

• Inter-module dependencies.

• Architectural complexity.

• Defect density and requirements changes.

Reducing the complexity of individual functions should not make the overall architecture more tangled.

The Testing Revolution

NASA compared basis path testing with Modified Condition/Decision Coverage (MC/DC). In the evaluated functions, MC/DC:

• Required 30–50% less time for the more complex cases.

• Reduced redundant path testing.

• Provided a more robust approach for safety-critical software when combined with functional and requirements testing.

• Was already established in safety-critical aviation guidance such as DO-178C.

MC/DC verifies that every condition in a decision can independently affect the decision’s outcome. It aims for strong coverage without requiring every possible combination of conditions.

Tools of the Trade

NASA reviewed tools capable of calculating or working with cyclomatic complexity.

Free Options

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

• Complexity metrics available in some IDEs and development toolchains.

Commercial Solutions

• Scientific Toolworks’ Understand for CC1, CC2, and CC3 analysis and complexity visualizations.

• Static analysis products such as Coverity and CodeSonar.

• Coverage tools such as LDRA and VectorCAST for MC/DC testing.

The specific tool matters less than measuring consistently and integrating analysis into the development workflow.

The Alternative Viewpoint

Not everyone on the assessment team agreed that bounding complexity was the most effective way to improve code quality. Gerard Holzmann presented an alternative viewpoint focused on disciplined engineering practices:

• Rigorous coding standards aimed at risk reduction.

• One or preferably multiple strong static analyzers on every build.

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

• An average assertion density of at least 2%.

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

This is an important reminder that a complexity threshold is a guardrail, not a substitute for sound engineering.

Practical Recommendations

Based on NASA’s findings:

1. Set a complexity limit of 15 for safety-critical code.

2. Assess any function above that limit for testability, maintainability, and code quality.

3. Use MC/DC testing for safety-critical functions alongside functional and requirements testing.

4. Track code churn, dependencies, and architectural complexity.

5. Run static analyzers on every build and keep compiler warnings at zero.

6. Focus on reducing risk, not merely satisfying a style rule.

The Bottom Line

NASA’s study showed that complex code is not just harder to read—it can be dramatically harder to test with confidence. When software controls hazardous systems, keeping cyclomatic complexity manageable becomes part of mission assurance.

The next time you’re tempted to add “just one more condition” to an already complex function, remember that simpler control flow makes thorough testing more achievable.

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