BENZENE: A Practical Root Cause Analysis System with an Under-Constrained State Mutation

BENZENE: A Practical Root Cause Analysis System with an Under-Constrained State Mutation

Speakers: Younggi Park, Hwiwon Lee, Jinho Jung, Hyungjoon Koo, Huy Kang Kim

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=Y426LOXNowY

Overview

Software crashes pose a persistent and critical security challenge, frequently signaling underlying vulnerabilities such as memory corruption bugs. The sheer volume of crash reports generated daily – exemplified by Ubuntu's reported millions of error reports – far exceeds the capacity for manual human analysis. This talk, "BENZENE: A Practical Root Cause Analysis System with an Under-Constrained State Mutation," introduces an innovative automated system designed to streamline and enhance the efficiency of root cause analysis for software crashes. Presented by Younggi Park from Korea University, alongside collaborators from Korea University and Sejong University, the research addresses a fundamental bottleneck in modern software security: the ability to quickly and accurately pinpoint the origins of software failures in complex, highly structured programs.

The core contribution of BENZENE lies in its novel approach to generating the necessary behavioral data for effective root cause analysis. Traditional methods, particularly those based on predictive fault localization, struggle to create specific "crash-similar but non-crashing behaviors" that are vital for distinguishing between faulty and correct execution paths. BENZENE tackles this by employing an under-constrained state mutation technique. This method intelligently alters the program's internal state during execution, circumventing the limitations of input-based fuzzing and enabling the system to efficiently discover the precise conditions that trigger or avert a crash. The system's demonstrated accuracy of 93% across 60 real-world bugs and an average 8x speed improvement over prior approaches underscore its potential to significantly impact software development and security practices.

Background

▶ Watch: The growing need for automated root cause analysis. (0:00)

The prevalence of software crashes has long been a major concern for both industry and academia. More than mere program termination, crashes often serve as indicators of critical security vulnerabilities, particularly memory corruption issues. The exponential growth in software complexity and the continuous deployment of new features have led to an overwhelming increase in the number of reported crashes. For instance, the Ubuntu operating system alone generates over a million error reports daily, an insurmountable volume for manual developer intervention. This necessitates the development of automated systems for root cause analysis (RCA) to efficiently identify and rectify bugs.

One of the most promising avenues for automated RCA is predictive-based fault localization. This technique operates on a fundamental principle: by observing and comparing the behaviors of crashing and non-crashing executions, it can infer the specific conditions, or predicates, that lead to a program failure. The typical workflow involves several stages:

1. Data Set Collection: Gathering a multitude of crash-related behaviors.
2. Behavior Monitoring: Identifying differences between crashing and non-crashing executions.
3. Predicate Inference: Deriving logical conditions that describe the crashing scenario.
4. Predicate Ranking: Prioritizing these conditions to highlight the most likely root causes.
5. Report Generation: Providing actionable insights for developers.

This approach is particularly attractive because it can scale to large and complex programs, making it suitable for modern software environments.

However, a significant challenge arises in the initial data collection phase, especially for highly structured programs. The success of predictive-based fault localization hinges on the availability of a diverse set of behaviors, specifically those that are "crash-similar but non-crashing." These behaviors are crucial because they demonstrate the boundary conditions where a program transitions from correct execution to a crash. Without them, it becomes exceedingly difficult to synthesize the precise predicates that pinpoint the root cause.

To illustrate, the talk presents a real-world example: a heap overflow vulnerability in PHP's GD imagecolor match function, related to a CVE report in 2019. The bug occurs when the cost_total value is set to 1, leading to the allocation of a small 20-byte buffer. Subsequently, a color value of 80 causes a pointer (BP) to access memory far beyond this allocated buffer (e.g., B + 280), resulting in an out-of-bounds access and a crash. The developer's patch addressed this by ensuring a maximum allocation based on cost_total. For predictive-based fault localization to identify cost_total < 80 as the root cause, it needs to observe cases where cost_total is both below and above 80. If only crashing behaviors (e.g., cost_total = 1) and irrelevant non-crashing behaviors (e.g., cost_total values that don't even reach the vulnerable code path) are collected, the critical predicate cost_total < 80 cannot be inferred, and the root cause remains elusive. This highlights the problem: traditional fuzzing techniques, while good at finding crashes, often fail to generate these specific "crash-similar but non-crashing" scenarios that are essential for effective root cause inference.

Key Findings

▶ Watch: Illustrating a real-world heap overflow crash in PHP. (2:40)

The central insight and primary finding of this research is the critical importance and inherent difficulty of obtaining crash-similar but non-crashing behaviors for successful automated root cause analysis. These specific behaviors are the linchpin for predictive-based fault localization, as they provide the crucial contrast necessary to infer the exact predicates that define a crashing condition. The researchers meticulously analyzed what constitutes such a "key behavior," identifying two essential characteristics:

1. It must be a non-crashing execution, providing a counter-example to the observed crash.
2. It must follow a program path similar to the original crashing execution, ensuring its relevance to the root cause. Without path similarity, a non-crashing behavior might be entirely unrelated to the vulnerability, offering no useful information for predicate inference.

The talk highlights the limitations of existing program testing techniques, particularly fuzzing, in generating these specific behaviors. Fuzzers excel at producing a wide array of inputs, but for highly structured programs with complex input constraints (like PHP scripts), they often generate inputs that are syntactically invalid or that follow execution paths entirely divergent from the crash site. Such inputs, while technically "non-crashing," are not "crash-similar" and thus provide no actionable intelligence for root cause analysis. The challenge lies in creating nuanced input modifications that touch the vulnerability-related path but alter a specific internal state to prevent the crash, a task beyond the scope of typical fuzzer capabilities.

To overcome this, the authors introduce under-constrained state mutation, the core innovation of the BENZENE system. This technique deviates significantly from traditional fuzzing by modifying the program's internal state during execution, rather than altering the input before execution. This strategic shift allows BENZENE to bypass complex input parsing and constraint checks, directly manipulating variables or registers at a point deep within the program's execution flow. This approach inherently generates crash-similar behaviors because it starts from the exact crashing execution path and only diverts at a specific, targeted point.

The effectiveness of BENZENE's under-constrained state mutation is empirically validated through extensive evaluation. The system was tested on 60 real-world bugs collected from a diverse set of applications, including highly structured programs like PHP and SQLite, as well as multimedia-related software. These bugs spanned 11 different bug classes, such as heap overflow, integer overflow, and use-after-free vulnerabilities. BENZENE successfully located the root cause for 56 out of 60 bugs, achieving an impressive 93% accuracy. Furthermore, the system demonstrated significant performance gains, operating eight times faster on average compared to prior fault localization approaches like Aurora and Arus. These findings collectively demonstrate that BENZENE offers a practical, highly accurate, and efficient solution for automated root cause analysis, particularly in scenarios where traditional methods fall short.

Technical Deep Dive

▶ Watch: How predicate-based fault localization works with examples. (4:00)

BENZENE's architecture is meticulously designed to automate the complex process of root cause analysis, leveraging its novel state mutation technique. The system operates through a structured workflow:

1. Initial Setup and Dynamic Analysis:

• A user provides the target program and a specific crashing input.
• BENZENE performs dynamic binary analysis on the crashing execution. This initial phase is crucial for gathering foundational information, including:
• Function extraction: Identifying and mapping all functions within the binary.
• Data flow analysis: Tracing how data propagates through the program.
• Crash origin backtracking: Pinpointing the exact instruction where the crash occurred and tracing relevant data/control flow backward to understand its immediate context.

1. Behavior Collection via Under-Constrained State Mutation:

• This is the heart of BENZENE. Based on the initial dynamic analysis, the system identifies potential points for state mutation.
• The goal is to collect a diverse set of crash-similar but non-crashing behaviors.
• The mutation process involves intelligently altering the program's internal state (e.g., register values, memory contents) during execution.

1. Crashing Condition Synthesis and Predicate Ranking:

• With the collected data set of crashing and non-crashing behaviors, BENZENE compares the observed values of variables and program states.
• It then synthesizes crashing conditions – logical predicates that differentiate between the two types of behaviors.
• These predicates are ranked by their likelihood or significance in explaining the crash.

1. Report Generation:

• Finally, BENZENE generates a user-friendly report, highlighting suspicious root cause locations and the inferred predicates. This report provides developers with actionable insights to fix the underlying bug.

The core innovation, under-constrained state mutation, addresses the fundamental challenge of generating relevant non-crashing behaviors. Unlike fuzzers that modify program inputs before execution, BENZENE intervenes mid-execution. As the talk explains, "a typical fuzzer often modifies the program input before execution. However, as the bug cause is located in the deep of the program, we have trouble passing complex constraints before reaching it." BENZENE's solution is to "move the mutation point to a location behind the complex constraints." This approach offers several advantages:

• Ease of Reaching Root Cause: By modifying state directly within the program, BENZENE can easily target variables or registers that are directly involved in the bug, even if they are deep within the program's logic and difficult to influence via external input.
• Inherent Crash Similarity: The mutation is applied to an execution path that would have crashed, making the resulting non-crashing behavior inherently "crash-similar." The program path diverges only at the point of mutation, ensuring relevance.

A critical aspect of state mutation is the validity problem: if the program state is forcefully changed, do the resulting behaviors still make sense for bug discovery? BENZENE acknowledges that its mutation might lead to unreachable states, meaning a "valid" input might not naturally produce that specific state. However, the system's purpose is not bug discovery (the crash is already given), but rather root cause analysis. The key insight here is that "even if the current state is unreachable, we found an important aspect that a crashing condition still persist [for] the non-crashing behaviors." This means that the relationship between values and the logical conditions that define a crash can still be inferred, even from states that are not strictly reachable through natural input. The focus is on the informational value of the behavior for predicate inference, not on its strict input-reachability.

To manage the vast number of potential mutation points, BENZENE employs a sophisticated scope reduction strategy:

• Function Granularity: The system first identifies interesting functions from the crashing execution. This significantly narrows down the search space compared to mutating arbitrary instructions.
• Target Function Selection: Functions that contribute to the crashing values are prioritized. This is achieved by tracing data flow and reference edges backward from the crashing instruction. If a crash occurs due to a specific value, any function that influenced that value or a pointer to it becomes a candidate. For instance, if a crash happens at a move instruction due to an invalid address, BENZENE traces the data flow and reference edges from that address to identify the functions responsible for its creation or manipulation.
• State Selection within a Function: Even within a target function, many states could be mutated. BENZENE further refines this by focusing on values that originate outside of the function, such as function parameters or global variables. The intuition is that a function's behavior is often largely determined by these "entry nodes." Mutating these external inputs to a function allows for a comprehensive exploration of its behavior without needing to explore every internal register or variable.
• Mutation Cycle: For each chosen target function and selected state within it, BENZENE performs a mutation cycle. This involves using a fork system call at the function entry point, applying the state mutation to the chosen state, and then monitoring whether the program crashes or not. This process is repeated for different values and across all identified target functions.

This systematic approach to state mutation, combined with intelligent scope reduction, allows BENZENE to efficiently discover the crucial crash-similar but non-crashing behaviors necessary for accurate root cause analysis.

Demo / Proof of Concept

▶ Watch: Key characteristics of essential 'similar but non-crashing' behaviors. (7:10)

While the talk does not feature a live, interactive demonstration of the BENZENE tool in action, it provides a compelling conceptual proof of concept through a detailed explanation of the PHP GD imagecolor match vulnerability. This example effectively illustrates the core mechanism and power of the under-constrained state mutation technique.

The speaker walks through the scenario where the cost_total value in the GD imagecolor match function is initially set to 1 by a crashing input. This leads to the allocation of an insufficient 20-byte buffer. Later, a color value of 80 causes a pointer (BP) to access memory at B + 280, resulting in an out-of-bounds access and a crash.

BENZENE's approach is then demonstrated: the GD imagecolor match function is compiled into machine code, and the cost_total value corresponds to the RAX register within a LEA instruction. Instead of trying to craft a complex PHP input that would set cost_total to a non-crashing value, BENZENE suspends the program execution just before this LEA instruction. At this point, the RAX register, which holds the cost_total value, is inspected and found to be 1. BENZENE then mutates this register, changing its value from 1 to, for example, 0xFF (255).

The result of this internal state modification is immediate and profound: with RAX now set to 255, the program allocates a sufficiently large buffer. Consequently, the subsequent memory access at B + 280 no longer triggers an out-of-bounds error, and the program terminates gracefully without a crash. This modified execution is precisely the "crash-similar but non-crashing behavior" that traditional fuzzers struggle to produce. The example clearly articulates how BENZENE's state mutation achieves the same effect as manually crafting a complex, non-crashing input, but with far greater efficiency and precision, directly at the point of vulnerability.

Defensive Implications

▶ Watch: Why typical fuzzers fail to generate these crucial behaviors. (8:00)

The BENZENE system offers significant defensive implications for developers, security engineers, and organizations striving to enhance software security:

1. Accelerated Vulnerability Patching: By providing an automated and highly accurate method for root cause analysis, BENZENE can dramatically reduce the time it takes for developers to understand why a crash occurred. This acceleration directly translates to faster patch development and deployment, shrinking the window of vulnerability that attackers could exploit. An 8x speed improvement over prior methods means critical bugs can be addressed in hours or days, rather than weeks.

1. Improved Security for Complex Software: The system's demonstrated ability to effectively analyze highly structured programs like PHP and SQLite is particularly valuable. These types of applications often feature intricate codebases and complex input parsing, making manual debugging and traditional fuzzing less effective for root cause identification. BENZENE's approach provides a robust tool for securing these challenging environments.

1. Actionable Insights for Developers: The output of BENZENE is not just a crash report; it's a set of ranked predicates that precisely describe the crashing condition (e.g., "cost_total value is less than 80"). This granular information empowers developers to focus their efforts on specific code paths and variable conditions, leading to more targeted and effective bug fixes rather than speculative patches.

1. Enhanced Understanding of Exploit Conditions: The core concept of "crash-similar but non-crashing behaviors" is itself a powerful defensive insight. It forces developers and security analysts to think not just about what causes a crash, but about the specific boundary conditions and state transitions that differentiate a secure execution from a vulnerable one. This deeper understanding can inform more robust code reviews, security testing strategies, and the design of defensive mechanisms.

1. Proactive Bug Prevention: While BENZENE is primarily a post-crash analysis tool, the insights gained from its use can feed back into the development lifecycle. Identifying common types of root causes or patterns of predicates can inform static analysis rules, coding guidelines, and developer training, leading to the prevention of similar bugs in future code.

In essence, BENZENE equips defenders with a powerful, automated microscope to peer into the intricate mechanics of software crashes, transforming overwhelming volumes of error reports into precise, actionable intelligence for enhancing software resilience.

Key Takeaways

• Automated root cause analysis is indispensable for managing the overwhelming volume of software crashes, which often signal critical security vulnerabilities.
• The effectiveness of predictive-based fault localization heavily relies on collecting diverse "crash-similar but non-crashing behaviors" to infer accurate crashing conditions.
• Traditional fuzzing techniques are often inadequate for generating these specific, relevant non-crashing behaviors, especially in complex, highly structured programs with intricate input constraints.
• BENZENE introduces under-constrained state mutation, a novel technique that efficiently discovers these crucial behaviors by directly modifying the program's internal state during execution, bypassing complex input parsing.
• The system demonstrates high practical utility, achieving 93% accuracy in locating root causes for 60 real-world bugs across diverse applications and bug classes.
• BENZENE significantly improves efficiency, performing root cause analysis 8x faster on average compared to prior fault localization approaches, enabling quicker vulnerability remediation.

About the Speaker(s)

The research behind BENZENE is a collaborative effort by academics from Korea University and Sejong University. The talk was presented by Younggi Park from Korea University. The co-authors of the paper include Hwiwon Lee, Jinho Jung, and Hyungjoon Koo, all affiliated with Korea University, and Huy Kang Kim, who is associated with both Korea University and Sejong University. Their collective work focuses on advancing automated techniques for software security, particularly in the challenging domain of root cause analysis for software crashes.