  Code coverage analysis plays an important role in the software testing
process. More recently, the remarkable effectiveness of coverage feedback has
triggered a broad interest in feedback-guided fuzzing. In this work, we
introduce bcov, a tool for binary-level coverage analysis. Our tool statically
instruments x86-64 binaries in the ELF format without compiler support. We
implement several techniques to improve efficiency and scale to large
real-world software. First, we bring Agrawal's probe pruning technique to
binary-level instrumentation and effectively leverage its superblocks to reduce
overhead. Second, we introduce sliced microexecution, a robust technique for
jump table analysis which improves CFG precision and enables us to instrument
jump table entries. Additionally, smaller instructions in x86-64 pose a
challenge for inserting detours. To address this challenge, we aggressively
exploit padding bytes and systematically host detours in neighboring basic
blocks. We evaluate bcov on a corpus of 95 binaries compiled from eight popular
and well-tested packages like FFmpeg and LLVM. Two instrumentation policies,
with different edge-level precision, are used to patch all functions in this
corpus - over 1.6 million functions. Our precise policy has average performance
and memory overheads of 14% and 22% respectively. Instrumented binaries do not
introduce any test regressions. The reported coverage is highly accurate with
an average F-score of 99.86%. Finally, our jump table analysis is comparable to
that of IDA Pro on gcc binaries and outperforms it on clang binaries.
