Efficient Binary-Level Coverage Analysis (Abstract)
Conference: MBMV 2020 – Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen - GMM/ITG/GI-Workshop
03/19/2020 - 03/20/2020 at Stuttgart, Deutschland
Proceedings: GMM-Fb. 96: MBMV 2020
Pages: 4Language: englishTyp: PDF
Khadra, M. Ammar Ben; Stoffel, Dominik; Kunz, Wolfgang (Technische Universität Kaiserslautern, Germany)
Code coverage analysis plays an important role in software testing. More recently, the remarkable effectiveness of coverage feedback has triggered wide interest in feedback-guided fuzzing. In this work, we introduce bcov, a coverage analysis tool for x86-64 ISA. Our tool tracks basic block coverge by statically instrumenting ELF binaries 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 super blocks to reduce overhead. Second, we introduce sliced microexecution, a precise and robust technique for jump table analysis. Our technique improves CFG precision and allows 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 8 well-tested packages like FFmpeg and LLVM’s backend. Two instrumentation policies, with different edge-level precision, are applied to all functions in this corpus - more than 1:6106 functions . Instrumented binaries do not introduce any test suite regressions. Our precise policy has average performance and memory overheads of 15% and 22% respectively.