Abstract
Modern software testing faces a significant hurdle in exploring deep program states, especially within complex network protocols. Traditional concolic execution often becomes trapped in local "state-space explosions," failing to reach logic buried under intricate input sequences. MACE (Model-inference-Assisted Concolic Exploration) introduces a novel approach by iteratively building a finite-state machine (FSM) that acts as a navigational map. By alternating between high-level model inference and low-level guided exploration, MACE can "teleport" past initialization code to discover vulnerabilities in deep protocol states.
The Challenge of Deep State Exploration
Concolic execution—a hybrid of concrete and symbolic execution—is designed to explore program branches systematically. However, it lacks structural awareness. It treats a program as a flat collection of branches rather than a structured protocol with distinct states like "Authenticated" or "Data Transfer." Consequently, tools often exhaust their computational budget on loops or irrelevant local code, hitting a "depth barrier" typically around 3 or 4 messages. To find critical vulnerabilities, testing tools need a "big picture" view to navigate efficiently toward complex application logic.
The MACE Architecture
MACE addresses this by creating an iterative loop between learning and exploring. The system architecture consists of several key components that work in tandem to refine a model of the target program.
The process follows four main stages:
- Model Inference: Using the $L^*$ online learning algorithm, MACE treats the program as a black box to infer a Mealy machine (FSM). It sends message sequences and observes outputs to build an initial behavioral model.
- Guided Exploration: The FSM serves as a scaffold. For every state, MACE calculates the "shortest transfer sequence"—the most direct path to reach that specific protocol state.
- Concolic Probing: Once the program is driven into a target state, a concolic engine explores the immediate "vicinity" of that state, uncovering new branches and behaviors unique to that protocol phase.
- Refinement: New behaviors discovered during probing are filtered for relevance and fed back into the $L^*$ algorithm to expand and refine the FSM.
Bridging the Abstraction Gap
The core innovation of MACE is using the inferred FSM not just as an output, but as a navigational tool. This creates a hierarchical search strategy where high-level protocol states guide the fine-grained exploration of the underlying code.
As illustrated above, the high-level model (a) provides the "map" necessary to reach clusters of deep program states (b). This allows MACE to bypass "boring" initialization code and focus its heavy-duty symbolic reasoning on the code that actually matters for protocol logic. A crucial part of this efficiency is Smart Filtering: MACE uses the current FSM to discard redundant inputs generated by concolic execution, keeping the learning process computationally feasible.
Evaluation and Impact
The researchers evaluated MACE on several complex server implementations, including Vino (RFB), Samba (SMB), RealVNC, and the Windows XP SMB implementation. The results demonstrated a significant leap over traditional concolic execution:
- Vulnerability Discovery: MACE identified 7 vulnerabilities, including 4 previously unknown zero-days. Notably, it found a "Blocker" severity out-of-bounds read in GNOME (CVE-2011-0904).
- Increased Coverage: Instruction coverage improved by 58.86% for Samba and 21.01% for RealVNC compared to baseline methods.
- Breaking the Depth Barrier: While traditional tools often stalled at a depth of 4 messages, MACE successfully reached and explored states at a depth of 10 messages.
Limitations and Future Directions
Despite its success, MACE has limitations. It currently requires manual "output abstraction functions" to help the tool distinguish between different server responses. It also assumes program determinism and struggles with encrypted traffic unless encryption is disabled. Future work may involve automating abstraction and using more expressive models, such as subsequential transducers, to capture even more sophisticated program behaviors.
Summary updated