Binary-level code coverage analysis can be done either statically or dynamically. Static instrumentation can, among other things, offer drastic performance improvements over dynamic tools like Pin. However, it is considered, somewhat traditionally, to be brittle, i.e., it breaks binaries. For example, see the last note on static rewriting in afl-qemu. Hence, dynamic coverage analysis tools like DynamoRIO's
drcov are more popular.
That said, this paper (disclosure: first author here), describes
bcov, a tool which was able of leveraging static instrumentation while achieving at the same time better transparency in comparison to the popular DBI tools Pin and DynamoRIO. However, this work required an orchestrated effort which combined:
- Probe pruning. Leveraged dominance analysis in order to prune basic blocks that do not offer additional coverage information. This can cut the number of required probes down to 46% of the total number of basic blocks.
- Precise jump table analysis. Imprecision in the recovered control flow graph can cause the instrumented binaries to break. Therefore, recovering the targets of indirect jumps was necessary. This in turn enables the instrumentation of jump table entries.
- Various static instrumentation tricks. Aggressive overwriting of padding bytes and hosting detours in neighboring basic blocks.
bcov supports x86-64 ELF binaries. It can dump a single coverage file at process shutdown. This file contains a static array of booleans indicating the coverage of individual basic blocks. This means that merging (or diffing) coverage data of multiple tests can be done using simple boolean operations on the files themselves without the need to first post-process the data files. This feature improves the efficiency of the fuzzing workflow.
The source code of
bcov is now available.