Characterizing and Improving Bug-Finders with Synthetic Bugs

Automated bug-finding tools such as KLEE have achieved mainstream success over the last decade, and have proved capable of finding deep bugs even in programs that have received significant manual testing. Some recent works have demonstrated techniques for finding bugs in these bug-finding tools themselves; however, it remains unclear whether these correctness issues have any practical impact on their ability to uncover serious bugs. In this paper, we study this issue by conducting experiments with KLEE 1.4 and 2.2 on several corpora of memory safety bugs. Using automated bug injection, we can automatically find false negatives (i.e., bugs missed by KLEE); moreover, because the bugs we inject come with triggering inputs, we can then use concolic execution to tell which bugs were missed due path explosion and which are caused by soundness issues in KLEE. Our evaluation uncovers several sources of unsoundness, including a limitation in how KLEE detects memory errors, mismatches in the modeling of the C standard library, lack of support for floating point and C++, and issues with calls to external functions. Our results suggest that bug injection and other synthetic corpora can help highlight implementation issues in current tools and illuminate directions for future research in automated software engineering.