💻 computer science

Countering the Path Explosion Problem in the Symbolic Execution of Hardware Designs

This paper introduces piecewise composition, a novel symbolic execution technique for hardware designs that leverages modular structure to offload path exploration to SMT solvers, achieving a 97% reduction in runtime and an order-of-magnitude decrease in explored paths while directly analyzing RTL Verilog without netlist translation.

Original authors: Kaki Ryan, Cynthia Sturton

Published 2026-07-22

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kaki Ryan, Cynthia Sturton

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery inside a giant, futuristic city. This city is a computer chip, a tiny piece of silicon that controls everything from your phone to the satellites orbiting Earth. To make sure the city is safe, you need to check every single street, alley, and hidden door to ensure no bad guys can sneak in or break the rules. This field of science is called hardware verification, and it's the digital equivalent of a safety inspector making sure a bridge won't collapse before anyone drives across it.

The main tool detectives use for this job is called "symbolic execution." Instead of walking down one street at a time with a specific set of keys, symbolic execution is like having a magical map that lets you walk down every possible street at the same time. You replace specific numbers with "ghosts" that represent any number, and you watch how the city reacts to every ghostly possibility. The problem? As the city gets bigger and more complex, the number of streets multiplies so fast that it becomes impossible to check them all. This is known as the "path explosion problem." It's like trying to drink from a firehose; the water (or in this case, the number of paths to check) comes out so fast that you get overwhelmed before you can find the leak. If we can't check every path, we might miss a hidden trapdoor that hackers could use to steal secrets or crash the system.

This is where the paper "Countering the Path Explosion Problem in the Symbolic Execution of Hardware Designs" comes in. The authors, Kaki Ryan and Cynthia Sturton, introduce a clever new strategy called "piecewise composition." Instead of trying to walk through the entire city at once, they realized that the city is built in neighborhoods (or "blocks"). You can explore each neighborhood separately, map out all the possible routes within that single neighborhood, and then use a super-smart calculator (called an SMT solver) to figure out how those separate maps fit together.

Think of it like solving a giant jigsaw puzzle. The old way was to try to force every single piece into place one by one, hoping the picture eventually appears. If the puzzle has a million pieces, you'd be there forever. The new "piecewise composition" method is like sorting the pieces into small, manageable piles first. You solve the "sky" pile, then the "ocean" pile, and then the "tree" pile. Once you have the solutions for these smaller piles, you use a quick check to see how they connect. The paper shows that this approach doesn't just help a little; it drastically cuts down the work. In their tests on five different open-source designs, including complex CPUs and system-on-chips, this method reduced the number of paths the engine had to explore by about 92% to 99%.

The results were striking. The new engine ran 97% faster than the old methods. It successfully found security bugs and rule violations in designs that had previously been too difficult to check thoroughly. For example, when testing a specific processor core called OR1200, the engine found 27 out of 30 known bugs, whereas previous tools had found fewer. The authors emphasize that this isn't just a theoretical idea; they built a working tool that reads the actual code (Verilog) used to build these chips and produces a "counter-example"—a specific set of instructions that proves a bug exists.

However, the paper is careful to note that this isn't a magic wand that solves everything instantly. The method relies on the hardware being designed in a modular way, with distinct blocks that don't messily overlap in confusing ways. If a design has certain types of messy connections (like "write-write" dependencies where two parts try to write to the same memory at the same time), the tool will stop and report an error rather than guessing. But for the vast majority of well-structured hardware designs, this new approach offers a way to tame the firehose of possibilities, making it much easier to ensure our digital cities are safe, secure, and ready for the future.

Technical Summary: Countering the Path Explosion Problem in the Symbolic Execution of Hardware Designs

Problem Statement
Symbolic execution is a potent verification tool for hardware designs, capable of generalizing testing by replacing concrete input values with symbols to explore all possible execution paths. However, it suffers severely from the "path explosion" problem. In conventional symbolic execution, the number of paths to explore grows exponentially with the number of branch points (control flow statements) in the design. For complex hardware designs, this exponential growth renders full exploration computationally intractable. Prior attempts to mitigate this have involved combining symbolic execution with model checking, utilizing concrete execution traces, or restricting analysis to small designs, but these approaches often fail to scale to large, real-world Register Transfer Level (RTL) designs.

Methodology: Piecewise Composition
The authors introduce piecewise composition, a technique that leverages the inherent modular structure of hardware designs to shift the burden of path exploration from the symbolic execution engine to Satisfiability Modulo Theories (SMT) solvers.

Core Concept: Instead of exploring the entire design as a single monolithic control flow graph, the approach decomposes the design into independent blocks (specifically, Verilog always blocks). The engine symbolically explores each independent block exactly once per clock cycle, generating a set of path fragments (trees) for each block.
Composition via SMT: To reconstruct full root-to-leaf paths or verify assertions, the engine uses an SMT solver to compose these independent path fragments. The solver checks the feasibility of combining specific fragments from different blocks based on their path conditions and symbolic stores.
Complexity Reduction: For a design with $N$ independent always blocks, each containing at most $b$ binary branch points, conventional symbolic execution requires exploring $O(2^{bN})$ paths. Piecewise composition reduces this to exploring $O(2^b \cdot N)$ paths. The complexity becomes exponential only with the branch points within a single block, and linear with the number of blocks.
Handling Dependencies: The methodology accounts for various data dependencies between blocks:
- Read-Read: Blocks can be explored separately; the SMT solver filters infeasible combinations where shared variables conflict.
- Read-Write: Non-blocking assignments ensure updates in one block do not conflict with reads in another within the same cycle.
- Write-Write: The tool detects and errors out on write-write dependencies, which violate Verilog best practices.
Implementation Details: The engine operates directly on Verilog RTL without translation to C or netlists. It handles combinational logic by re-evaluating assignments based on "dirty" signals after exploring sequential blocks. It supports multiple clock cycles by merging states at cycle boundaries and includes optimizations such as handling repeated submodules (merging results via SMT) and Cone of Influence (COI) analysis to prune irrelevant blocks.

Key Contributions

Definition of Piecewise Composition: A formal technique that exploits hardware modularity to counter path explosion by transferring path combination logic to SMT solvers.
Symbolic Execution Engine: The design and implementation of a cycle-accurate engine for Verilog RTL that utilizes piecewise composition, operating directly on the source code.
Empirical Evaluation: A comprehensive evaluation on five open-source designs, including SoC and CPU architectures (OR1200, PULPissimo, openMSP430, etc.), using 84 security-critical assertions.

Results
The evaluation demonstrates significant performance improvements and efficacy in finding assertion violations:

Path Reduction: Piecewise composition reduces the number of lines of code visited by 92%–99% and branch points visited by 64%–99% compared to conventional symbolic execution.
Runtime: The technique reduces overall runtime by an average of 97%. In a full exploration of the MC68HC11 SPI design, the engine explored only ~7% of the lines of code and ~4% of the branch points required by the baseline.
Solver Efficiency: Contrary to the concern that composition might explode SMT query complexity, the reduction in explored paths led to an 18% average decrease in the number of SMT queries and a 21% decrease in solver time.
Bug Detection: The engine successfully found assertion violations in all five designs. Specifically, it identified 24 out of 31 bugs in the Hack@DAC SoC and 27 out of 30 bugs in the OR1200 processor.
Comparison: The tool found exploits in comparable designs in under 2 minutes, whereas prior state-of-the-art tools (e.g., Coppelia, RTLConTest) required hours to find similar vulnerabilities.

Significance and Claims
The paper claims that piecewise composition offers a viable path to scaling symbolic execution for large hardware designs without sacrificing the granularity of RTL-level analysis. By decoupling the exploration of independent hardware modules and relying on modern SMT solvers to recombine them, the approach maintains the benefits of individual path information while mitigating the exponential growth of the search space. The authors assert that this method allows for the verification of complex SoCs and CPUs that were previously intractable for symbolic execution, providing precise counter-examples that are directly traceable to the original RTL design. The work is presented as a step forward in hardware security verification, enabling the detection of assertion violations and potential vulnerabilities in real-world designs.

More like this