Sanitizers serve as the primary bug detection Oracle during automated testing. They "crash" the program gracefully and tell the fuzzer when and where a bug was triggered. The most well-known sanitizer is ASan or AddressSanitizer which adds redzones around memory objects to detect whenever an access is out-of-bounds. MSan or MemorySanitizer detects access to uninitialized memory. Upon allocation, all memory of an object is marked as uninitialized. When written, the memory is marked as initialized. For each read, the sanitizer validates that the underlying memory was properly initialized.
Compared to ASan, MSan faces a key challenge: all code must be instrumented, otherwise, some memory initialization may be missed resulting in false positive crashes. For ASan, missing instrumentation only results in false negatives (i.e., some bugs will be missed) but MSan is prone to both false positives and false negatives which so far hindered MSan's deployment. Therefore, only 210 out of 528 targets of OSS-Fuzz were fuzzed with MSan.
In our QMSan project, we develop a mechanism that reduces these false positives, creating an efficient MSan sanitizer for fuzzing environments. Our system uses two key ideas to reduce false positives: first, we use binary instrumentation to track all writes and second, we build a two-stage approach to massively reduce the cost of tracking initialized data.
The first contribution is simple: instead of using a compiler-pass to add instrumentation during compilation, we add the instrumentation through QEMU when code is being executed. The QEMU binary instrumentation engine allows us to analyze and instrument all code as it is being executed and gives us complete support for all code. Binary instrumentation comes at a slight overhead to compiler-based instrumentation but the reduction of false positives is worth the trade-off.
The second contribution is geared towards making MSan efficient for fuzzing. MSan requires that the state of memory (initialized or not) is copied whenever data is copied. This requires an expensive propagation of metadata information whenever data is read and stored in other areas of memory. Our key idea here was that fuzzing allows us to replay executions as we have the exact input. For the majority of executions, we only track reads and writes but ignore shadow propagation (that is otherwise required on nearly all other instructions). If our sanitizer detects a crash, we call i ta potential violation and replay the same input with the full sanitizer that extensively propagates memory. If it turns out to be true positive, we report it as a bug. If it turns out to be a false positive, we mark the location of the false positive and ignore future false positives at this location.
Our evaluation on 10 OSS-Fuzz targets and 5 proprietary discovered 44 new bugs that we responsibly disclosed. Our implementation is competitive to the compiler-based one with massively increased compatibility. The source code of our sanitizer is available as open-source. Please reach out to us with any questions!
This work was a collaboration between Matteo Marini, Daniele Cono D'Elia, Mathias Payer, and Leonardo Querzoni. Matteo was the main PhD student working on the project. He and Daniele deserve the majority of the credit for this work.