SymFit: Making the Common (Concrete) Case Fast for Binary-Code Concolic Execution

SymFit: Making the Common (Concrete) Case Fast for Binary-Code Concolic Execution

Speakers: Zhenxiao Qi, UC Riverside

Conference: USENIX Security '24

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

Overview

In the realm of software security and vulnerability research, concolic execution (a hybrid of concrete and symbolic execution) stands as a powerful technique for path exploration and bug finding. This talk, presented by Zhenxiao Qi from UC Riverside at USENIX Security '24, introduces SymFit, a novel approach designed to significantly enhance the efficiency of binary-code concolic execution. SymFit addresses critical performance bottlenecks in existing tools, particularly when analyzing binary-only software such as proprietary applications, stripped dependencies, or firmware, where source code is unavailable.

The core problem SymFit tackles is the substantial overhead incurred by current binary-only concolic executors, even during concrete execution paths. These overheads stem from pervasive instrumentation, inefficient shadow memory management, and slow symbolic state handling. By focusing on making the "common case"—where inputs or intermediate values are concrete—exceptionally fast, SymFit achieves remarkable speedups, thereby enabling more extensive and practical application of concolic execution in real-world security analysis.

This research is crucial for advancing automated vulnerability discovery and software analysis. The ability to rapidly explore execution paths, even in the absence of source code, directly translates to more effective bug hunting, improved security auditing of third-party components, and better understanding of complex, obfuscated binaries. SymFit's innovations promise to expand the practical applicability of concolic execution, making it a more viable tool for security researchers and developers alike.

Background

▶ Watch: Introduction: SymFit's goal and current challenges (0:00)

The evolution of binary-code concolic execution has seen several significant stages, each attempting to overcome inherent challenges. Early tools like Angr and S2E typically operated in a two-stage process: executing the binary concretely up to a predefined point of interest, then switching to a symbolic execution environment. While effective, this approach demanded considerable engineering effort to identify relevant functions and suffered from non-trivial overheads due to frequent context switches and the complex synchronization required to maintain consistent state between the concrete and symbolic execution spaces.

A subsequent wave of tools, notably QSYM and SimCFI, built upon the QEMU dynamic binary translation (DBT) framework, aimed to resolve the context-switching problem. These tools directly instrument the symbolic emulation logic into the target binary at runtime, allowing symbolic execution to occur within the same execution space as the concrete execution. This eliminated the need for explicit context switches and simplified state synchronization. However, these QEMU-based solutions introduced new performance bottlenecks:

1. Heavy Instrumentation Overhead: For every instruction executed, these tools instrument a helper function that checks if the instruction's operands are symbolic. Even if both operands are concrete, the overhead of a function call and conditional checks is incurred. This fine-grained, instruction-level checking, while theoretically precise, becomes a significant performance drag when the vast majority of execution is concrete. For instance, SimCFI was observed to suffer an average of 34 times slowdown compared to vanilla QEMU when all inputs were concrete.
2. Slow Shadow Memory Access: To track the concreteness or symbolicity of memory locations, existing tools like QSYM and SimCFI typically employ a two-level map data structure for shadow memory. When checking a memory address, the system first locates the page in the map and then reads every byte within the relevant memory region to determine if any byte is symbolic. This byte-by-byte checking, without exploiting spatial locality, is inherently inefficient and contributes substantially to execution slowdowns.
3. Inefficient Symbolic State Management: The backend of QSYM and SimCFI often represents symbolic expressions using a tree data structure. Each symbolic expression is essentially a pointer, and its allocation involves frequent calls to malloc on the heap. This dynamic memory allocation for individual expressions, coupled with the overhead of pointer dereferencing and potential cache misses, leads to slow lookup and allocation of symbolic states, especially as the number of symbolic expressions grows.

These combined inefficiencies highlighted a fundamental problem: existing binary-code concolic executors were not optimized for the common scenario where most code paths and data remain concrete. SymFit directly addresses these limitations by re-architecting how concreteness is checked, how shadow memory is accessed, and how symbolic states are managed, prioritizing speed for the concrete execution path.

Key Findings

▶ Watch: High instrumentation overhead from fine-grained concrete checks (2:30)

SymFit's primary contribution is a substantial improvement in the efficiency of binary-code concolic execution, particularly by optimizing the handling of concrete execution paths. The key findings and innovations include:

1. Efficient Basic Block Level Concreteness Checking: Instead of instrumenting every instruction with checks, SymFit introduces basic block level checking. This significantly reduces instrumentation overhead by identifying "clean" basic blocks (where all CPU registers are concrete) and executing them with minimal, lightweight instrumentation, primarily for memory accesses. This optimization leverages the observation that over 80% to 90% of basic blocks are executed concretely.
2. Optimized Shadow Memory Access with Block-Level Caching: SymFit replaces inefficient two-level map-based shadow memory access with a block-level caching mechanism inspired by the Translation Lookaside Buffer (TLB). By buffering recently accessed clean memory blocks and employing a direct mapping strategy between application and shadow memory, SymFit achieves a high cache hit rate (~95%) for concrete memory accesses, drastically speeding up memory checks.
3. Fast Symbolic State Management via Union Table: SymFit adopts a union table approach for managing symbolic expressions, moving away from heap-allocated tree structures. This design stores symbolic expressions in an array, identified by 32-bit integer labels that also serve as offsets. This enables extremely fast allocation through atomic increments and rapid lookup, significantly improving the overhead associated with symbolic state manipulation.
4. Decoupling Symbolic Tracing from Constraint Solving: SymFit explicitly decouples the symbolic tracer (which generates constraints) from the constraint solver. This architectural separation addresses the problem of constraint solving being a blocking task, allowing for parallelization of solving and enabling various downstream applications that utilize symbolic expressions beyond just constraint satisfaction.
5. Significant Performance Gains: Evaluations using fastbench programs demonstrate that SymFit achieves remarkable speedups compared to SimCFI:

• 10 times speedup when all inputs are concrete.
• 8 times speedup when inputs are symbolic but constraint solving is disabled.
• 5 times speedup even when constraint solving (the dominant overhead) is enabled.

1. Novel Application for Crash Deduplication: SymFit demonstrates a unique and highly efficient application of its symbolic tracing capabilities for crash deduplication. By collecting symbolic constraints from the last branch before a crash site and grouping crashes with similar constraints, SymFit achieved an 80% F1 score on the Magma benchmarks, proving its practical utility in vulnerability analysis workflows.

These findings collectively establish SymFit as a significant advancement in binary-code concolic execution, making the technique more performant and practical for real-world security challenges.

Technical Deep Dive

▶ Watch: Basic block level optimization for concrete instruction handling (4:00)

SymFit's efficiency gains are rooted in several key technical innovations that specifically target the bottlenecks identified in prior binary-code concolic execution frameworks.

Optimized Concreteness Checking at the Basic Block Level

Traditional QEMU-based concolic executors like QSYM and SimCFI perform checks at the instruction level. This means that for every single instruction, helper functions are invoked to determine if operands are symbolic. Even if both operands are concrete, the overhead of the function call, parameter passing, and conditional checks is incurred. This fine-grained approach, while ensuring correctness, is highly inefficient for the common case where instructions operate solely on concrete values.

SymFit addresses this by implementing basic block level checking. Instead of per-instruction checks, SymFit examines the state of CPU registers at the entry point of each basic block. If all CPU registers are identified as "clean" (i.e., holding only concrete values), SymFit assumes that most instructions within that basic block will also operate concretely. For such "clean" basic blocks, SymFit applies a lightweight instrumentation strategy. The only exceptions are memory load and store operations, which can potentially interact with symbolic memory. These memory accesses still require checks, but the overall reduction in instrumentation overhead across the block is substantial. If, however, any CPU register is symbolic, or if a load/store operation accesses symbolic memory, the basic block is executed with full instrumentation to ensure correct symbolic propagation. This optimization is highly effective because, as SymFit's evaluation showed, over 80% to 90% of basic blocks during execution typically deal exclusively with concrete values. This smart granularity significantly reduces the performance penalty associated with concreteness checks.

Block-Level Shadow Memory Checking with Caching

Existing solutions manage shadow memory (which tracks the symbolicity of application memory) using two-level map data structures. Accessing shadow memory in these systems involves locating the relevant page in the map and then iteratively checking every byte within the memory region to determine if it's symbolic or concrete. This process is slow, especially for larger memory accesses, as it fails to leverage the spatial locality often present in memory access patterns.

SymFit introduces a novel block-level checking mechanism for shadow memory, drawing inspiration from the Translation Lookaside Buffer (TLB) in modern CPUs. It maintains a buffer (a cache) of recently accessed clean blocks. When a shadow memory access occurs, SymFit first checks this buffer. If there's a cache hit, it immediately knows that the targeted memory block is entirely concrete and can return without further checks, significantly accelerating concrete memory accesses.

The design of the "block" size for this cache is critical. SymFit experimented with various block sizes, ranging from 32 bytes to 248 bytes, ultimately settling on an optimal size of 512 bytes. This block size yielded a cache hit rate of approximately 95%. It's important to note that this hit rate is not comparable to a typical CPU TLB hit rate (which might be 99% or higher) because any access to symbolic memory will inherently result in a cache miss within this scheme. However, for the concrete common case, this 95% hit rate represents a massive performance improvement. Furthermore, SymFit employs a direct mapping strategy between application memory and shadow memory, trading some space complexity for enhanced time efficiency in memory access.

Efficient Symbolic State Management via Union Table

In tools like QSYM and SimCFI, symbolic expressions are typically managed as nodes in a tree data structure. Each node contains pointers to its children and stores expression details. The allocation of these nodes often involves frequent calls to malloc on the heap. This approach introduces several performance drawbacks: heap allocation overhead, pointer dereferencing costs, and potential cache misses due to fragmented memory layouts.

SymFit adopts an alternative, more efficient approach borrowed from SSAN, a source-code based concolic execution tool, and adapts it for the binary-only context. It uses a union table, which is essentially a large array. Every symbolic expression is assigned a unique 32-bit integer label, and this label also serves as the direct offset of that expression within the union table array.

This design fundamentally changes how symbolic expressions are managed:

1. Fast Allocation: Allocation of a new symbolic expression simply involves an atomic increment of a counter that tracks the last allocated label. This bypasses the overhead of malloc and ensures extremely fast allocation.
2. Fast Lookup: Given a symbolic label, retrieving the corresponding expression is a direct array lookup using the label as an index, eliminating pointer dereferencing chains and improving cache locality.

This union table design drastically reduces the time spent on symbolic state management, which is a critical factor in overall concolic execution performance.

Decoupling Symbolic Tracing and Constraint Solving

A common architectural pattern in concolic execution is for the symbolic execution engine to generate constraints and then immediately invoke a constraint solver to find satisfying inputs. This makes constraint solving a blocking task; the entire engine often idles while waiting for the solver to return results. This significantly limits throughput and scalability.

SymFit addresses this by explicitly decoupling the symbolic tracer (the component that instruments the binary and generates symbolic expressions and constraints) from the constraint solver. The symbolic tracer continuously generates constraints, which are then passed to a separate constraint solving component. This architectural separation offers several advantages:

1. Parallelization: Constraint solving can often be parallelized, as many sets of constraints are independent. Decoupling allows multiple solver instances to operate concurrently, processing accumulated constraints without blocking the tracing engine.
2. Downstream Applications: The generated symbolic expressions and constraints can be used for a variety of downstream tasks beyond just finding new inputs for path exploration. These include crash analysis, crash deduplication, and other forms of program analysis, making the symbolic tracing output a versatile artifact.

Architectural Integration

SymFit is built on top of QEMU, leveraging its dynamic binary translation capabilities to instrument the target binary's execution flow. It dynamically injects logic that allows it to switch seamlessly between concrete mode (when basic blocks are clean and lightweight instrumentation is used) and symbolic mode (when symbolic variables are involved and full instrumentation is required). The symbolic expressions are efficiently managed in the union table, and shadow memory accesses benefit from the block-level cache. This integrated architecture allows SymFit to function as an efficient symbolic tracer, producing constraints that feed into various applications, including hybrid fuzzing and crash analysis.

Demo / Proof of Concept

▶ Watch: Fast symbolic expression management using a union table (7:30)

While the talk did not feature a live, interactive demonstration, SymFit's effectiveness was thoroughly validated through a comprehensive evaluation against existing state-of-the-art tools and benchmarks. These evaluations served as a robust proof of concept for its design principles and performance claims.

The primary evaluation focused on performance comparison with SimCFI, a prominent QEMU-based concolic executor, using a suite of fastbench programs. The results highlighted SymFit's significant speed advantages:

• When all inputs to the programs were concrete, SymFit achieved an impressive 10 times speedup compared to SimCFI. This directly validates SymFit's core premise of making the common concrete case exceptionally fast.
• Even when inputs were symbolic, with the constraint solving component temporarily disabled, SymFit still demonstrated an 8 times speedup. This indicates the efficiency gains from optimized instrumentation, shadow memory, and symbolic state management are substantial, irrespective of solver activity.
• Crucially, even when constraint solving was enabled (which is typically the dominant overhead in concolic execution), SymFit maintained a 5 times speedup over SimCFI. This demonstrates that SymFit's optimizations effectively reduce the non-solver-related overheads, allowing the overall system to perform better even when the most computationally intensive part is active.

Beyond raw performance, SymFit was also evaluated in a hybrid fuzzing scenario. It was paired with an existing fuzzing instance to compare coverage growth. For some programs, SymFit's concolic execution component enabled faster coverage growth, suggesting its ability to guide the fuzzer into deeper or harder-to-reach paths. However, for other programs, the coverage growth was similar to fuzzing alone. The speaker noted that in this combination, fuzzing often remains the primary driving force for path exploration, implying that a "smarter combination" or more sophisticated integration of concolic execution with fuzzing might be needed for universally superior coverage.

A unique and impactful application demonstrated by SymFit is its use for crash deduplication. For this, SymFit was run on the Magma benchmarks, a collection of crashing inputs. The tool collected symbolic constraints from the last executed branch before each crashing site, as well as any other constraints that showed input dependency with that last branch. By grouping different crashing inputs (or "seeds") that produced the same or very similar symbolic constraints, SymFit could effectively identify and deduplicate unique crashes. This simple yet powerful approach achieved an 80% F1 score for crash deduplication, indicating a high balance of precision and recall. Furthermore, this method proved to be very efficient, offering a practical solution for triaging large numbers of crashes generated by fuzzers.

The speaker also mentioned that SymFit's code is open source and available on a GitHub repository. They are in the process of updating the tool to the latest QEMU version and have also developed a kernel version of SymFit capable of tracing symbolic value propagation within kernel functions, highlighting the versatility and extensibility of their approach.

Defensive Implications

▶ Watch: Decoupling symbolic tracing and parallelizing constraint solving (9:00)

The advancements brought by SymFit have significant implications for defenders and security professionals engaged in software analysis and vulnerability management:

1. Accelerated Vulnerability Discovery: By dramatically speeding up binary-code concolic execution, SymFit empowers security researchers to find vulnerabilities more efficiently in software where source code is unavailable. This includes proprietary applications, commercial off-the-shelf (COTS) products, third-party libraries, and firmware. Faster analysis means more bugs found in less time, enhancing overall software security posture.
2. Enhanced Fuzzing Campaigns: While SymFit showed mixed results in hybrid fuzzing for coverage growth, its ability to quickly generate symbolic constraints and explore specific paths can be a valuable complement to fuzzing. Defenders can potentially use SymFit to target specific complex functions or to generate inputs that satisfy intricate conditions, guiding fuzzers towards deeper bugs that are difficult to reach with random mutation alone.
3. Efficient Crash Analysis and Triage: The demonstrated crash deduplication capability is directly beneficial for security teams dealing with large volumes of crashes from fuzzing or exploit development. An 80% F1 score for deduplication, coupled with high efficiency, means less time spent manually triaging duplicate crashes, allowing analysts to focus on truly unique and potentially critical vulnerabilities. This streamlines the vulnerability disclosure and patching process.
4. Deeper Understanding of Binary Behavior: For complex or obfuscated binaries, concolic execution provides insights into program logic that static analysis alone cannot. SymFit's improved performance makes it more practical to apply this technique to larger binaries, helping defenders understand how inputs influence execution paths, identify potential attack surfaces, and reverse engineer unknown functionalities.
5. Improved Security Audits of Dependencies: Many modern applications rely heavily on external libraries and components. When these are provided as stripped binaries, auditing their security is challenging. SymFit offers a more efficient tool for performing security assessments on these critical dependencies, helping organizations identify and mitigate risks inherited from their software supply chain.
6. Potential for Automated Exploit Generation: While not explicitly discussed as a defensive implication in the talk, faster concolic execution is a fundamental building block for automated exploit generation. Defenders can potentially use this capability to generate proof-of-concept exploits for discovered vulnerabilities, which can then be used to validate patches and ensure effective remediation.

In essence, SymFit provides security practitioners with a more powerful and practical tool for binary analysis, allowing them to conduct more thorough security assessments and respond more effectively to emerging threats in a binary-only world.

Key Takeaways

• Optimized for Concrete Execution: SymFit's core innovation lies in making the common concrete execution path significantly faster, addressing a major bottleneck in existing binary-code concolic executors.
• Block-Level Concreteness Checks: By checking CPU register states at the basic block level and applying lightweight instrumentation for concrete blocks, SymFit drastically reduces overhead compared to instruction-level checking.
• Efficient Shadow Memory Management: A block-level caching mechanism inspired by TLBs, with an optimal 512-byte block size and direct mapping, achieves a ~95% cache hit rate for concrete memory accesses.
• Fast Symbolic State Management: The adoption of a union table with 32-bit integer labels and atomic increment allocation enables extremely fast lookup and allocation of symbolic expressions.
• Decoupled Tracing and Solving: Separating the symbolic tracer from the constraint solver allows for parallelized solving and opens up new avenues for downstream tasks beyond just path exploration.
• Substantial Performance Gains & Practical Applications: SymFit delivers up to a 10x speedup for concrete inputs and a 5x speedup even with symbolic inputs and solving enabled, demonstrating its practical value in hybrid fuzzing and achieving an 80% F1 score for efficient crash deduplication.

About the Speaker(s)

The talk "SymFit: Making the Common (Concrete) Case Fast for Binary-Code Concolic Execution" was presented by Zhenxiao Qi. Zhenxiao Qi is associated with UC Riverside, where this research was conducted. With a demonstrated expertise in systems security and binary analysis, as evidenced by the development of SymFit and its kernel version, Zhenxiao Qi is actively seeking job opportunities in the field. The work presented, including the open-sourcing of SymFit, underscores a commitment to advancing practical solutions in software security.