Skip to content
STIMSMITH

Concolic Testing

Technique WIKI v1 · 9/28/2026

Concolic testing is a hybrid software and hardware verification technique that combines concrete execution with symbolic constraint tracking. By solving symbolic constraints, it systematically generates new inputs that steer execution along unexplored paths to maximize code coverage and expose bugs. The method has been adapted from general-purpose software into specialized settings such as logic programming, embedded RISC-V binaries analyzed through virtual prototypes, and RTL hardware designs, while known limitations include the path-explosion problem and scalability challenges on complex programs.

Overview

Concolic testing (CT) is a verification technique that fuses concrete execution with symbolic execution. As a program runs concretely, CT records symbolic constraints on inputs along each branch. By negating selected constraints and invoking a constraint solver, CT produces new concrete inputs that drive execution down previously unexplored paths. The technique is widely used to maximize code coverage, activate hard-to-reach branches, expose assertion violations, and generate test suites that exercise different program behaviors (citation: Abstraction-driven Concolic Testing; LLM4DV; Sci China Inf Sci 2022, §6.1).

Core Mechanism

The conceptual pipeline (as implemented by tools such as RVX) consists of:

  1. Concrete execution with instrumentation – The binary or program executes natively while a tracer attaches symbolic metadata to each operation on input-derived values.
  2. Path constraint accumulation – At each conditional branch, the symbolic constraint corresponding to the taken direction is appended to a path constraint.
  3. Constraint solving for new inputs – The engine selects a branch in the accumulated path, flips its constraint, and asks an SMT/SAT solver for a satisfying assignment; the resulting assignment becomes the next concrete input.
  4. Path exploration – Each new input explores a fresh execution path; symbolic constraints can simultaneously be used to evaluate assertions or other safety properties alongside the concrete run (citation: Sci China Inf Sci 2022, §6.1).

By generating one test per path, CT aims to systematically drive up coverage rather than relying on chance.

Strengths and Known Limitations

CT is effective at activating assertions and reaching branches that random and constrained-random stimuli miss, because it directly reasons about the conditions guarding them (citation: LLM4DV).

However, the technique is subject to two well-known issues:

  • Path explosion – The number of feasible paths grows exponentially with program size, so naive exploration quickly becomes infeasible.
  • Complex symbolic constraints – Nonlinear arithmetic, memory aliasing, and interaction with hardware peripherals can produce constraints that solvers struggle with or that explode the search space.

These limitations motivate hybridization with complementary techniques such as model checking and coverage-guided fuzzing (citation: Abstraction-driven Concolic Testing; Sci China Inf Sci 2022, §6.1–6.2).

Notable Variants and Hybrid Approaches

Abstraction-driven Concolic Testing

This method iteratively couples concolic testing with counterexample-guided abstraction refinement. When concolic testing stalls, the model checker refines its program abstraction to prove additional paths infeasible, shrinking the search space before concolic testing resumes. An implementation built on CREST (concolic testing) and CPAchecker (model checking) improved branch coverage over standalone CREST from 66% to 71% on average and from 48% to 63% in the best case on SV-COMP benchmarks (citation: Abstraction-driven Concolic Testing, https://arxiv.org/abs/1511.02615v2).

Concolic Testing in Constraint Logic Programming (CLP)

A prior approach for logic programs was unsound because it represented only positive constraints via substitutions, leaving negative constraints inexpressible. A subsequent framework lifts CT to full CLP, in which both positive and negative constraints are representable, yielding a sound (and potentially more efficient) technique. The work argues that defining verification/testing methods for CLP is increasingly relevant because CLP is being adopted as an intermediate representation for analyzing programs from other paradigms (citation: Concolic Testing in CLP, https://arxiv.org/abs/2008.00421v3).

Concolic Testing for RTL Hardware

In hardware verification, CT is described as a semi-formal method that generates effective test sequences by analyzing the control-flow graph (CFG) of register-transfer level (RTL) designs. The generated sequences are simulated, coverage scores are measured, and the results guide the next round of sequence generation. The approach requires a thorough understanding of both the design and the grammatical structure of the RTL to accurately analyze control and data flow (citation: DeepVerifier / TODAES 2026, §1).

Concolic Testing for Embedded RISC-V Binaries (RVX)

The RVX tool applies CT to embedded binaries that extensively interact with SystemC-based peripherals on RISC-V platforms. Its approach instruments the RISC-V instruction-set simulator (ISS) and memory to track symbolic constraints alongside native execution, and provides a specialized interface for SystemC-based peripheral models. Reported applications include finding buffer overflows in the FreeRTOS TCP/IP stack and a bug in the RISC-V-specific memcpy of newlib (citation: Sci China Inf Sci 2022, §6.1; RVX, Herdt et al., ATAV 2020).

Concolic Testing Combined with Coverage-Guided Fuzzing

Because of CT's scalability limits, complementary coverage-guided fuzzing (CGF) is used. While CT leverages formal constraint solving, CGF mutates randomly created inputs and is guided by code coverage (e.g., libFuzzer, AFL). In the RISC-V VP-based setting, CGF has been combined with SystemC-based virtual prototypes and guided by both software and peripheral coverage metrics to bridge the HW/SW gap (citation: Sci China Inf Sci 2022, §6.2).

Tools

  • CREST – a representative concolic-testing tool used as the concrete-execution engine in the abstraction-driven approach (citation: Abstraction-driven Concolic Testing).
  • CPAchecker – a configurable software model checker paired with CREST to refine abstractions and prune the search space (citation: Abstraction-driven Concolic Testing).
  • RVX – a tool that implements concolic testing of embedded binaries targeting RISC-V platforms, tightly integrated with SystemC-based virtual prototypes (citation: RVX, Herdt et al., ATAV 2020; Sci China Inf Sci 2022, §6.1).

Relationship with Coverage-Guided Fuzzing

CT and CGF are explicitly positioned as complementary in the RISC-V virtual prototype setting: CT leverages formal constraint solving, while CGF uses scalable random mutation driven by coverage feedback. The same execution engine (a virtual prototype) can host either technique, with the tracer/checker providing feedback to guide test generation (citation: Sci China Inf Sci 2022, §6.1–6.2).

Related Techniques

  • Coverage-guided fuzzing (CGF) – scalable simulation-based technique that mutates random inputs and is guided by coverage metrics such as libFuzzer and AFL; used to complement CT on complex embedded binaries (citation: Sci China Inf Sci 2022, §6.2).
  • Dynamic information flow tracking (DIFT) – security-focused technique that tracks data flow alongside execution to check integrity and confidentiality; combined with VPs to enable early, accurate analysis of embedded RISC-V binaries (citation: Sci China Inf Sci 2022, §6.3).
  • Instruction stream generators (ISGs) – e.g., FORCE-RISCV, used in simulation-based verification to systematically produce test sequences (citation: DeepVerifier / TODAES 2026, §1).

LINKED ENTITIES

2 links
RVX-a tool for concolic testing of embedded binaries targeting RISC-V platforms USES
RVX IMPLEMENTS

CITATIONS

9 sources
9 citations
[1] Concolic testing is a hybrid verification technique that combines concrete execution with symbolic constraint tracking, using a constraint solver to generate new inputs that steer execution along unexplored paths. Advanced virtual prototyping for cyber-physical systems using RISC-V: implementation, verification and challenges (Herdt & Drechsler, Sci China Inf Sci 2022)
[2] The RVX tool instruments the RISC-V ISS and memory to track symbolic constraints alongside native execution and provides a specialized interface for SystemC-based peripheral models, enabling concolic testing of embedded binaries that extensively interact with peripherals. Advanced virtual prototyping for cyber-physical systems using RISC-V (Sci China Inf Sci 2022, §6.1)
[3] RVX was effective in finding buffer overflows in the TCP/IP stack of FreeRTOS and a bug in the RISC-V specific memcpy function of the newlib C library. Advanced virtual prototyping for cyber-physical systems using RISC-V (Sci China Inf Sci 2022, §6.1)
[4] Concolic testing suffers from the path-explosion problem and may be susceptible to scalability issues due to complex symbolic constraints, motivating complementary methods such as coverage-guided fuzzing. Advanced virtual prototyping for cyber-physical systems using RISC-V (Sci China Inf Sci 2022, §6.1–6.2)
[5] Abstraction-driven concolic testing iteratively combines concolic testing with model checking; when concolic testing fails to cover some test goals, the model checker refines its abstraction to prove more paths infeasible, reducing the search space. Abstraction-driven Concolic Testing (arXiv 1511.02615v2)
[6] An implementation built on CREST and CPAchecker improved branch coverage compared to standalone CREST from 48% to 63% in the best case and from 66% to 71% on average on SV-COMP benchmarks. Abstraction-driven Concolic Testing (arXiv 1511.02615v2)
[7] A previous approach to concolic testing in logic programming was not sound because it only dealt with positive constraints (by means of substitutions); a subsequent framework lifts concolic testing to CLP, where both positive and negative constraints can be represented naturally, yielding a sound and potentially more efficient technique. Concolic Testing in CLP (arXiv 2008.00421v3)
[8] In RTL hardware verification, concolic testing is described as a semi-formal method that generates effective test sequences by analyzing the control-flow graph of RTL designs and uses coverage scores to guide subsequent sequence generation. DeepVerifier: Learning to Update Test Sequences for Coverage-Guided Verification (ACM TODAES 2026)
[9] Lyu and Mishra utilized concolic testing to activate assertions by regarding assertions as branches and searching through the branch statement tree with heuristics to obtain a path and generate test stimuli that cover the targeted branches. LLM4DV: Using Large Language Models for Hardware Test Stimuli Generation