What we talk when we talk about coverage

Read Time: 5 minutes

Code coverage is a fundamental metric in software testing, yet it’s often misunderstood. When we say “coverage,” what exactly do we mean? In this post, I’ll explore different types of coverage and their implications for C++ fuzzing.

Types of Coverage

Line Coverage

The most basic form - did we execute this line?

void process(int x) {
    if (x > 0) {        // Line 1
        handle_positive(); // Line 2
    } else {
        handle_negative(); // Line 3
    }
}

Line coverage tells us if lines 1, 2, and 3 were executed, but not how many times or in what order.

Branch Coverage

Did we take both sides of each conditional?

if (condition1 && condition2) {  // 4 possible paths
    // ...
}

Branch coverage ensures we test both true and false cases for each decision point.

Path Coverage

Did we explore all possible execution paths?

void complex_function(int a, int b) {
    if (a > 0) {
        if (b > 0) {
            // Path 1: a>0, b>0
        } else {
            // Path 2: a>0, b<=0
        }
    } else {
        if (b > 0) {
            // Path 3: a<=0, b>0
        } else {
            // Path 4: a<=0, b<=0
        }
    }
}

Path coverage is exponential in the number of branches - often impractical for real code.

Coverage in Fuzzing

Edge Coverage (AFL-style)

AFL popularized edge coverage - tracking transitions between basic blocks:

// Simplified AFL coverage map
coverage_map[hash(prev_location, cur_location)]++;

This captures control flow information beyond simple line coverage.

Context-Sensitive Coverage

Going deeper - tracking calling contexts:

void foo() {
    bar();  // Called from foo
}

void baz() {
    bar();  // Called from baz - different context
}

Data-Flow Coverage

Tracking how data flows through the program:

int x = input();      // Definition
if (x > 0) {         // Use
    int y = x * 2;   // Definition and use
    output(y);       // Use
}

The Coverage Plateau Problem

Most fuzzers hit a coverage plateau after initial exploration:

Coverage
  ^
  |     _______________
  |    /
  |   /
  |  /
  |_/___________________> Time

This happens because:

1. Easy-to-reach code is found quickly
2. Complex conditions require specific inputs
3. Some code paths are simply unreachable

Beyond Traditional Coverage

Semantic Coverage

Instead of syntax-based coverage, consider semantic properties:

// Traditional: Did we call allocate()?
// Semantic: Did we allocate >1GB? Did allocation fail?
void* allocate(size_t size) {
    if (size > MAX_SIZE) {
        return nullptr;  // Error path
    }
    return malloc(size);
}

Type Coverage

For C++ templates, covering different instantiations:

template<typename T>
class Container {
    // Coverage for Container<int>, Container<string>, etc.
};

State Coverage

Tracking state machine transitions:

enum State { INIT, RUNNING, STOPPED };
// Coverage: Did we transition from RUNNING to STOPPED?

Practical Implications

For Fuzzing

1. Choose the right metric: Edge coverage is usually a good default
2. Combine metrics: Use multiple coverage types for better results
3. Consider diminishing returns: 100% coverage is often impossible

For Static Analysis

Coverage guides where to focus analysis efforts:

// High coverage area - likely well-tested
// Low coverage area - needs more attention

For Code Review

Coverage highlights untested code:

// Coverage: 0% - RED FLAG!
void critical_security_check() {
    // ...
}

Tools and Techniques

Compile-Time Instrumentation

clang++ -fprofile-instr-generate -fcoverage-mapping

Runtime Coverage Collection

__attribute__((no_sanitize("coverage")))
void coverage_callback(const uint8_t* pc) {
    // Custom coverage tracking
}

Coverage Visualization

Tools like llvm-cov provide visual coverage reports:

llvm-cov show ./binary -instr-profile=default.profdata

Conclusion

Coverage is not a single metric but a family of related measurements. Understanding the nuances helps us:

• Write better fuzzers
• Design more effective test suites
• Identify truly untested code

Remember: coverage is a means to an end, not the end itself. High coverage doesn’t guarantee bug-free code, but low coverage almost certainly means untested bugs.

Next post: I’ll discuss how we achieved 90% coverage in TVM’s tensor compiler through targeted fuzzing.