# Presentation: 733187

## The Relationship of Cyclomatic Complexity, Essential Complexity and Error Rates

- Mike Chapman and Dan Solomon
- chapman@ivv.nasa.gov
- solomon@ivv.nasa.gov

## Hypothesis

- Essential complexity is a better predictor of error than cyclomatic complexity.

## Cyclomatic Complexity, or v(G), measures the number of linearly independent paths through a given program.
Essential complexity is the measure of the degree to which a module contains unstructured constructs.
Module design complexity, iv(G), is a measure of the module’s decision structure as it relates to calls to other modules.

- Essential complexity is the measure of the degree to which a module contains unstructured constructs.
- Module design complexity, iv(G), is a measure of the module’s decision structure as it relates to calls to other modules.

- Complexity Definitions

## Lines of Code

- McCabe finds the open bracket and starts counting until it finds the close bracket.  This metric was used to show LOC error prediction in this study.

## The Dataset

- 312K executable lines of C code
- 8 years of problem reports (life of project)
- 1652 Software problem reports whose fix included a change to at least one software module.
- 2078 modules changed at least once due to a problem report
- 4221 total module changes as the result of problem reports
- 12,094 modules as identified by McCabe IQ

**Notes:**
Any change in a module associated with a problem report, we are calling an error for that module.  From the numbers, the average PR resulted in 2.5 module changes (errors)

## What Was Eliminated

- A CSCI that had recently been redesigned using C++
- 1007 modules that no longer exist in the baseline or were ambiguous in their naming
- A CSCI that consisted of multiple directories of essentially the same code
- Leaving 11,494 modules with 3154 errors

## Number of Modules

**Notes:**
As mentioned, this is a large data set.  Here is how the modules are distributed with respect to v, ev, LOC, and iv.

Note in particular only 17 modules with ev = 2, which will be of some amusement later.

Note there are very few modules with very high v, ev, LOC, or iv (often just one).

## Error Rate

**Notes:**
Take all the modules with a given v(G), find the average number of errors across those modules.  This gives us a relationship between error rate and v(G).

Note it it possible to write a module with v = 392 and no errors.

First conclusion:  if your metric is extremely high, you probably have errors.  
Therefore, it makes sense to focus on reasonable values, say up to 75 for v and ev.

Second:  if your metric is extremely low (with the amusing exception of ev=2), you probably don’t.

According to the McCabe software, modules whose v(G) >10 or ev(G) > 4 are potentially problematic.  In this data set, those values don’t look useful.  That is, things aren’t lot’s higher to the right of 10 & 4.  To me, 20 and 10 look better for error rate.

## Error Prediction

- What does it mean to say that a metric is a good predictor of error(s)?
- Or that one is better than another?
- How does one select a threshold?

## A Closer Look at v(G)

**Notes:**
You can see an upward trend in the error rate.  Approx every third module of v(g) = 10 has an error.

## A Closer Look at ev(G)

## Thresholds

- Compare the error rate among modules above a threshold with that of those below

**Notes:**
Modules whose v >10 have five times as many errors as those <=10.

If you pick an even higher threshold, your ratio improves, but you are beginning to miss a lot of errors.

## Probability of Error

## A Closer Look at v(G)

## A Closer Look at ev(G)

## Thresholds

- Compare the error probability for modules above a threshold with those below

**Notes:**
Modules whose v >10 are 2.5 times as as likely to have errors as those <=10.

## Conclusions

- Both cyclomatic and essential complexities indicate errors
- Cyclomatic is a better indicator
- The McCabe thresholds (10 and 4) aren’t bad, but 20 and 10 look better

**Notes:**
higher complexities are linked with higher error rates and probabilities

How complicated the s/w is matters more than how structured it is

Capers-Jones “it’s impossible to test a module with v >20”

## Future Work

- This analysis should be carried out for additional programs.
- We have proposed to investigate the relation between software structures and errors
- IV&V Facility Metrics Data Program will provide metrics and error data to the research community

**Notes:**
We have another large program (1.2 M SLOC) in house with four years of error data at the module level, which we are in the process of generating the metrics and error rates.