QMSan: Efficiently Detecting Uninitialized Memory Errors During Fuzzing

QMSan: Efficiently Detecting Uninitialized Memory Errors During Fuzzing

Speakers: Matteo Marini

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=4AL-SGWHpJM

Overview

In the realm of software security, Use of Uninitialized Memory (UUM) errors represent a particularly insidious class of vulnerabilities. These errors occur when a program attempts to read from a memory location that has been allocated but not yet written to, leading to unpredictable behavior, crashes, or even exploitable conditions. Matteo Marini's talk, "QMSan: Efficiently Detecting Uninitialized Memory Errors During Fuzzing," introduces a novel, binary-based solution designed to overcome the significant limitations of existing UUM detection tools, particularly in the context of large-scale fuzzing of closed-source or complex software.

QMSan leverages a multi-layered detection strategy built upon the QEMU emulator, making it compatible with the popular AFL++ fuzzer. The core innovation lies in its ability to drastically reduce the performance overhead typically associated with binary-level instrumentation for UUM detection, enabling more practical and widespread application. By addressing the challenges posed by recompilation requirements and excessive slowdowns, QMSan offers a "plug-and-play" solution that significantly expands the scope of UUM error detection, as evidenced by the discovery of 44 new bugs and the issuance of four CVEs.

Background

▶ Watch: Introduction to Use of Uninitialized Memory (UUM) errors (0:00)

UUM errors are a pervasive and dangerous flaw in software. Marini illustrates this with a simple C code example: a program attempts to read four bytes from standard input into a buffer, then compares the first byte (A) with a magic value. If the read function fails, A remains uninitialized. Critically, the subsequent conditional branch if (A == magic_value) will still evaluate, using the arbitrary, uninitialized value in A. This can lead to nondeterministic issues that are notoriously difficult to debug and detect without specialized tools.

The general workflow for detecting UUM errors involves three key steps:

1. Shadow Memory: A parallel memory region is maintained, reflecting the initialization status of every byte in the program's main memory.
2. Propagation: The initialization status from the shadow memory is propagated through memory operations (e.g., copies, arithmetic).
3. Deferred Detection: Checks for uninitialized data are performed only at "sensitive operations" such as pointer dereferences or conditional branches.

The deferral of detection is crucial because merely loading uninitialized memory is not inherently an error. Compiler optimizations, such as load widening, might load more bytes than strictly necessary, with the expectation that the uninitialized portions will be discarded before use. Detecting an error at the point of load would lead to numerous false positives.

The state-of-the-art solution for UUM detection is Memory Sanitizer (MSan). MSan is a compile-time solution known for its accuracy due to its access to detailed compile-time information. It typically incurs a performance slowdown of 2x to 3x. However, MSan suffers from a critical drawback: it requires the entire user-space stack, including all libraries an application uses at runtime, to be recompiled with MSan instrumentation. This requirement makes MSan highly impractical for fuzzing large, complex applications, especially closed-source software or projects with extensive, unmodifiable dependencies. Marini highlights that MSan was disabled in OSS-Fuzz a few years ago due to operating system updates, and as of today, more than half of C/C++ projects in OSS-Fuzz have MSan disabled, leaving a significant gap in UUM detection coverage.

In contrast to compile-time solutions, binary-level UUM detection approaches offer greater generality, allowing instrumentation of a broader range of software, including closed-source applications, as instrumentation is inserted at runtime. However, these binary-level tools, such as Valgrind's Memcheck or Dr. Memory, traditionally suffer from much higher slowdowns, typically in the range of 10x to 20x. Furthermore, they have not historically been compatible with modern fuzzing solutions like AFL++, leaving a critical need for an efficient, generic, and fuzzing-compatible UUM detector for binaries. QMSan aims to fill this void.

Key Findings

▶ Watch: Introducing QMSan: a new binary-based UUM detector (4:40)

QMSan emerges as a significant advancement in the field of UUM error detection, particularly for binary and closed-source software. Its core contribution is a binary-based, multi-layered solution that drastically limits the performance overhead typically associated with such tools. By leveraging the QEMU emulator and demonstrating compatibility with AFL++, QMSan provides a practical and efficient means to uncover these challenging vulnerabilities in contexts where compile-time sanitizers like MSan are infeasible.

The practical impact of QMSan is substantial. During its evaluation, the tool successfully detected a total of 44 new UUM bugs. This includes 27 bugs found in nine closed-source binaries—a category notoriously difficult to analyze with traditional source-based tools—and 17 bugs in 10 open-source projects selected from OSS-Fuzz that were not currently being fuzzed with MSan. These discoveries led to the issuance of four CVEs, underscoring the real-world security implications of the found vulnerabilities.

From a performance perspective, QMSan achieves remarkable efficiency for a binary-level UUM detector. It demonstrated a slowdown of 1.51x over QEMU-AFL as a baseline. When compared to the gold standard of compile-time MSan, QMSan was only 1.55 times slower, a stark contrast to the 10x-20x slowdowns typical of other binary instrumentation frameworks. This efficiency makes QMSan a viable tool for integrating into continuous fuzzing pipelines, offering a "plug-and-play" solution that does not require the extensive recompilation efforts demanded by MSan.

Technical Deep Dive

▶ Watch: QMSan's three core components: accurate, runtime, opportunistic (5:00)

QMSan's innovative design is centered around a multi-layered approach that strategically balances accuracy and performance. It is built on the QEMU emulator, which provides the necessary dynamic binary instrumentation capabilities to analyze and modify program execution at runtime without requiring source code. This foundation allows QMSan to operate on various architectures, with experiments demonstrating success on x86 and ARM platforms, including detection of the same bugs in Nvidia binaries.

The architecture of QMSan comprises three main components:

1. Accurate Detector: This component functions similarly to established binary UUM error detectors like Valgrind's Memcheck or Dr. Memory. It is highly accurate, providing a definitive assessment of whether a UUM error is genuine. However, its comprehensive instrumentation makes it inherently slow. In QMSan's design, the Accurate Detector serves as the "ground truth" validator, only invoked when necessary.

1. Runtime Module: This module is responsible for the core mechanics of UUM detection and shadow memory management. It maintains the initialization status of memory regions and propagates this status as data moves through the program.

1. Opportunistic Detector: This is the novel and most crucial component for QMSan's efficiency. It is designed to be very fast but is also inherently inaccurate, initially generating a high number of false positives (referred to as "violations"). The key insight behind the Opportunistic Detector is that the vast majority of loads from uninitialized memory are actually safe and do not lead to exploitable UUM errors. By quickly identifying and "ignoring" these safe loads, QMSan avoids the heavy overhead of full instrumentation for most execution paths.

The QMSan workflow orchestrates these components to achieve its performance goals:

• The program under test is initially run within the Opportunistic Detector.
• When the Opportunistic Detector identifies a "violation" (a load from uninitialized memory), it first checks an ignore list.
• If the violation is already known and marked as safe in the ignore list, execution resumes immediately, incurring minimal overhead.
• If the violation is not known, it is flagged as potentially problematic. To validate this, the execution is replayed specifically for this code path within the Accurate Detector.
• The Accurate Detector then determines if the violation is a genuine UUM error or a false positive.
• If it's a false positive, the violation is added to the ignore list, and fuzzing continues. This ensures that subsequent encounters with the same "safe" violation will not trigger the expensive Accurate Detector.
• If the Accurate Detector confirms a real UUM error, an error is raised, indicating a successful bug detection.

The Opportunistic Detector operates by monitoring all memory accesses (read and write operations). When a write operation occurs, it initializes the corresponding shadow memory region. When a read operation occurs, it checks the shadow memory: if the memory is initialized, execution continues without interruption. If the memory is uninitialized, a "violation" is recorded. This simple, fast check is what generates the initial set of potential issues.

A critical element for QMSan's accuracy and efficiency is its ignore list policy. Incorrectly adding violations to the ignore list could lead to false negatives, where genuine bugs are missed. To prevent this, QMSan's policy considers three key properties when characterizing a violation for the ignore list:

1. Instruction Address: The memory address of the instruction that triggered the uninitialized load. While fundamental, this alone is insufficient because the same instruction can sometimes cause a UUM error and sometimes not, depending on the context.
2. Spatial Locality: This refers to the calling context or call stack when the violation occurs. Considering the call stack helps differentiate between identical instructions in different execution paths.
3. Temporal Locality: This property accounts for the sequence of violations. The order in which violations occur can be indicative of a specific program state or execution flow.

Marini notes that early development experiments attempted to include register values or other memory statuses but found this led to "too much noise" and an "explosion" in the number of executions required by the Accurate Detector, effectively negating the performance benefits of the opportunistic approach. The chosen combination of instruction address, spatial locality, and temporal locality was found to be robust enough to characterize violations accurately without observing false negatives in practice.

The QEMU-based nature of QMSan is a significant advantage, allowing it to instrument and analyze arbitrary binaries without source code. This capability extends to different CPU architectures, as demonstrated by successful tests on ARM, where QMSan detected the same bugs in Nvidia binaries with similar performance characteristics as on x86, despite potential differences in memory models. This architectural flexibility further broadens QMSan's applicability beyond typical x86-focused security tools.

Demo / Proof of Concept

▶ Watch: Opportunistic detector's key intuition: most uninitialized loads are safe (6:15)

While the talk did not feature a live, step-by-step demonstration of QMSan in action, the effectiveness of its approach was robustly validated through extensive evaluation and the discovery of numerous real-world security vulnerabilities. The speaker detailed the methodology and results of this empirical proof of concept, highlighting QMSan's practical utility.

For bug detection, a comprehensive dataset was assembled:

• Closed-source binaries: Nine binaries commonly used as targets in binary fuzzing research papers were selected.
• Open-source programs: Ten programs were chosen from OSS-Fuzz, specifically those written in C/C++ that were not currently being fuzzed with MSan and had a high historical count of security-related bugs.

Using this dataset, QMSan successfully identified 27 new UUM bugs in the closed-source binaries and 17 new UUM bugs in the open-source projects, totaling 44 new vulnerabilities. These findings directly led to the issuance of four CVEs, providing concrete evidence of QMSan's capability to uncover previously unknown security flaws.

To evaluate performance, a separate dataset was used, consisting of eight common fuzzing benchmarks from Google Fuzzer Test. This dataset was chosen because its projects are also compatible with MSan, allowing for a direct comparison with the state-of-the-art compile-time sanitizer. The performance metrics were critical to demonstrating QMSan's efficiency:

• QMSan exhibited a slowdown of 1.51x over QEMU-AFL, which served as the baseline for a QEMU-based fuzzer. This indicates that QMSan adds a relatively modest overhead to an already instrumented QEMU environment.
• When compared to compile-time MSan, QMSan was found to be 1.55 times slower. This is a remarkable result for a binary-level detector, as typical binary instrumentation tools often introduce slowdowns 10 to 20 times higher than compile-time solutions.
• Compared to a "compiler" (implying the execution of the application without any instrumentation), QMSan was 3.75 times slower.

These evaluation results conclusively demonstrate that QMSan provides a highly effective and acceptably efficient solution for detecting UUM errors in binaries, making it a viable alternative where source-level sanitizers are impractical or impossible. The availability of the code and evaluation data on GitHub ensures reproducibility and further research.

Defensive Implications

▶ Watch: Importance of ignore list policies to prevent false negatives (7:45)

The introduction of QMSan has several significant implications for software developers, security researchers, and organizations striving to enhance their defensive posture against UUM errors.

For developers, QMSan serves as a stark reminder of the persistent and often subtle nature of uninitialized memory vulnerabilities. Even with rigorous code reviews and static analysis, UUM errors can evade detection, especially in complex codebases or when interacting with third-party libraries. The nondeterministic behavior caused by these errors makes them incredibly difficult to diagnose in production environments. Developers should prioritize explicit initialization of all variables and memory regions, particularly those sourced from external inputs or shared across different modules. While compile-time sanitizers like MSan are invaluable for projects where full source control is possible, QMSan highlights the necessity of considering binary-level checks for dependencies or when integrating components that cannot be recompiled.

Security researchers and fuzzers gain a powerful new tool with QMSan. Its ability to perform efficient UUM detection on arbitrary binaries, including closed-source software, fills a critical gap left by source-code-dependent tools. The compatibility with AFL++ means it can be seamlessly integrated into existing, mature fuzzing pipelines, significantly expanding their bug-finding capabilities. This is particularly valuable for analyzing proprietary software, firmware, or complex embedded systems where source code is unavailable. Furthermore, QMSan's support for multiple architectures (x86, ARM) broadens its applicability across a diverse range of computing platforms. Researchers can leverage QMSan to systematically identify UUM vulnerabilities that might otherwise remain hidden, contributing to a more secure software ecosystem.

For organizations, QMSan offers a practical strategy to improve the security of their software supply chain. Many organizations rely heavily on third-party binaries, commercial off-the-shelf (COTS) software, or legacy applications for which source code is not accessible. Integrating QMSan-like binary analysis into their vulnerability assessment and quality assurance processes can provide an additional layer of defense, identifying critical UUM errors before they can be exploited. The relatively low performance overhead, especially compared to other binary instrumentation tools, makes it feasible to incorporate QMSan into automated testing frameworks, allowing for more comprehensive and continuous security validation of binary components. This "plug-and-play" capability, without the need for extensive recompilation, streamlines the security auditing process for complex software stacks.

Key Takeaways

• Fills a Critical Gap: QMSan addresses the significant limitations of existing UUM error detection tools, particularly MSan, by offering an efficient, binary-based solution for closed-source software and complex projects where full recompilation is impractical.
• Multi-Layered Efficiency: Its novel architecture combines a fast, opportunistic detector with an accurate, but slower, detector. This allows QMSan to drastically reduce the performance overhead (only 1.51x slowdown over QEMU-AFL, 1.55x slower than MSan) compared to traditional binary instrumentation (10-20x slowdowns).
• Fuzzing Compatible: Built on QEMU and compatible with AFL++, QMSan is a practical tool for integration into modern fuzzing pipelines, enabling automated discovery of UUM errors in binaries.
• Proven Bug-Finding Capability: QMSan successfully found 44 new UUM bugs (27 in closed-source, 17 in open-source) and led to the issuance of four CVEs, demonstrating its effectiveness in uncovering real-world security vulnerabilities.
• Robust Ignore List Policy: The system's ignore list leverages a combination of instruction address, spatial locality (calling context), and temporal locality (sequence of violations) to accurately distinguish between safe and problematic uninitialized memory loads, preventing false negatives.
• Architectural Flexibility: Being QEMU-based, QMSan can be applied to various architectures, with successful tests on x86 and ARM, extending its utility across diverse computing environments.

About the Speaker(s)

Matteo Marini is a researcher whose work focuses on addressing challenging problems in software security, particularly in the domain of fuzzing and binary analysis. His presentation on QMSan at the NDSS Symposium highlights his expertise in developing innovative solutions for detecting subtle yet critical vulnerabilities like Use of Uninitialized Memory errors. Marini's research, as demonstrated by QMSan, emphasizes practical, efficient, and generic approaches to security testing, aiming to overcome the limitations of traditional methods for analyzing complex, real-world software.