Control Flow Edge Coverage

Definition and Role in Fuzzing

Control Flow Edge Coverage (also referred to as CF edge coverage) is a coverage-feedback metric used in grey-box fuzzing. Instead of recording which basic blocks (BBs) have been executed, CF edge coverage tracks information about the CF edges that were actually taken during a target program's execution. Each edge is identified by its source and target basic blocks (or equivalently, its source and target program counters, PCs).

Traditional grey-box fuzzers, including popular frameworks such as AFL and AFL++, guide test-case generation primarily using this form of control flow edge coverage. The metric is used to decide which inputs are "interesting" and should be retained and further mutated in the fuzzer's corpus. As an alternative to edge coverage, hash digests identifying entire CF paths can be used; these guide a fuzzer toward high path coverage and may find a new path per run by mutating a single loop limit, but at the cost of missing other relevant CF edges. The benefit of any particular coverage approach depends on the individual fuzzing target.

Limitations

While CF edge coverage is the dominant guidance signal in modern grey-box fuzzing, it can overlook bugs not easily exposed through control-flow analysis alone. This limitation arises because many vulnerabilities manifest through data-propagation patterns (definition-use chains) that may share the same control-flow paths as benign code. Research frameworks such as FuzzRDUCC argue that integrating dataflow analysis alongside CF edge coverage can expose security vulnerabilities that pure control-flow-based feedback misses.

CF edges with complex conditions can also be inherently hard to fuzz, because a specific edge is taken only when all partial conditions are met simultaneously. Some compilers mitigate this by splitting the condition over multiple basic blocks, so that the fuzzer receives more runtime feedback to find inputs that meet all partial conditions. However, such CF-altering transformations affect the application's runtime behavior and may be inappropriate for real-time IoT targets.

Hardware Implementation via Hashed Indexing

In FPGA-accelerated fuzzing frameworks such as TaPaFuzz, control-flow edge coverage is realized in hardware attached to a RISC-V core (e.g., CVA5) via the core's built-in tracing interface, which exposes dedicated PC and instruction-word outputs. Because a complete coverage map keyed by raw 32-bit (source, destination) PC pairs would be prohibitively large, the hardware hashes each CF edge into a pseudo-random index within a compact coverage map whose cell values count each edge's occurrences.

The hashing scheme is designed around several constraints:

Throughput: the implementation must process one CF edge per cycle so it does not become the bottleneck for instruction execution.
Low collision risk: distinct edges should map to distinct indices with high probability.
Low hardware overhead: a small footprint is required for FPGA deployment.
No cryptographic security: collision resistance only needs to be probabilistic, not adversarial.

Cryptographic hashes such as SHA were ruled out due to massive hardware overhead and limited throughput. Instead, a lightweight hash from the "hash prospector" repository was selected, providing only 8 cycles of latency and a guaranteed throughput of 1 item per cycle. Concretely, the 32-bit hash algorithm is fed the edge's source PC; the destination PC is then added to an intermediate value of the algorithm to reduce collisions with nearby CF edges; finally, the result's bit-length is trimmed, depending on the chosen coverage map size, to form a valid index.

After each program execution, the host software fetches the coverage map, exception status, and cycle count via an interrupt signaled by the hardware, and uses this data to generate the next fuzzer run's inputs.

Throughput Bottlenecks

Because the hardware must count every jump and branch on the traced core, throughput is ultimately limited by the read-and-write round-trip time to the result memory. This latency is increased by arbitration between PE-external and internal access and by the AXI BRAM controller. To avoid missing control-flow transfers when the memory subsystem stalls, a direct stall signal into the processor is asserted if required.

Relation to Other Coverage Metrics

CF edge coverage sits between two extremes:

Basic-block coverage: records only which BBs execute and how many times. It is cheaper to instrument and store, but provides less discriminative feedback because different execution paths through the same blocks are indistinguishable.
Path-coverage digests: identify entire executed CF paths (e.g., via hashes). This produces strong path-coverage signal — a fuzzer can reach a new path per run by mutating one loop limit — but loses sensitivity to individual edges, since paths not yet reached dominate the signal.

Edge coverage thus offers a balance: finer-grained than basic-block coverage for distinguishing new transitions, but cheaper and more stable than full path-coverage hashes.