Backward Tracing
Definition
Backward tracing is an analysis strategy in which the investigator begins from a specified effect, behavior, or symptom and reasons or searches backward toward the causes, inputs, or faults that could produce it. It is the conceptual inverse of forward tracing, in which causes (e.g., specific fault injections) are chosen first and the resulting effects are observed.
The term is used in two distinct technical literatures supported by the provided evidence:
- Hardware reliability and formal verification — where backward tracing is applied to exhaustive fault analysis in digital designs.
- Software debugging research — where backward tracing is one of two cognitive reasoning modes developers alternate between when diagnosing bugs.
Backward Tracing in Hardware Reliability (Formal Verification)
Problem Setting
Simulation-based fault injection, the conventional approach to evaluating soft-error (Single Event Upset, SEU) reliability of microprocessors, is forward tracing: a specific fault is injected into the design and the resulting response is monitored. Each simulation run explores at most one fault and one path through the state space, so exhaustive coverage is practically impossible for complex designs. Random fault injection is therefore used as a compromise, reducing fault coverage and accuracy.
The Backward-Tracing Method
Backward tracing reverses this direction. Instead of specifying faults, the analyst specifies the desired correct behavior as formal properties (e.g., SystemVerilog Assertions, SVA) and uses formal model checking to find every fault that could violate those properties. The two core steps are:
- Define the correct behavior, based on the design specification, as formal properties.
- Use model checking to find all faults that may violate the corresponding properties.
This approach is implemented on Register Transfer Level (RTL) models using a commercial formal verification tool (Cadence JasperGold FPV) supporting SVA.
Why It Is "Backward"
In the fault model, a fault controller produces two fault-control signals that gate XOR-based fault injection at every register bit. Forward tracing (e.g., simulation) requires these signals to be assigned explicit values; leaving them unspecified is treated as invalid. In model checking, however, unspecified inputs are treated as unconstrained: the formal tool explores every possible combination of the fault-control signals in order to prove or refute the assertions. As a consequence, an arbitrary fault at any bit location and at any time is implicitly considered, and the entire fault list is covered. Faults are therefore identified from their effects (assertion violations) rather than being injected explicitly and monitored — which is precisely the definition of backward tracing in this context.
Properties Exploited
The method develops three groups of formal properties corresponding to three categories of harmful SEU effects (the fourth category, "no effect," is treated as the baseline of correct behavior):
- Silent Data Corruption (SDC) properties — both strobe properties (a faulty core is compared against a duplicated golden core) and architectural properties (specific bits are monitored in a single core instance).
- Crash properties — architectural.
- Hang properties — architectural.
Advantages Over Forward Tracing
Backward tracing using model checking offers three advantages over simulation-based forward tracing:
- All paths through the state space are explored at once, rather than one path per simulation run.
- The whole fault list is covered, because fault-control signals are unconstrained and any bit at any time may carry a fault.
- Multiple faults violating different assertions can be identified in a single model checking run, whereas simulation can identify at most one fault per run.
Application and Findings
The technique has been demonstrated on the open-source 32-bit RISC-V Ibex Core (supporting the RV32IMC instruction sets). Findings reported when applying backward tracing to the Ibex include:
- Misaligned instructions can amplify fault effects.
- Some register bits are more vulnerable to SEUs than others.
- Most bits in the Ibex Core are vulnerable to SDC.
- The second pipeline stage is more vulnerable to SDC than the first.
The SVA properties are adaptable, via signal remapping, to other RISC-V processors, so the method is, in principle, general across the RISC-V family.
Backward Tracing in Software Debugging
Outside hardware verification, backward tracing is also a recognized reasoning mode in professional software debugging practice. A grounded-theory study of seven professional developers and five professional live-coding streamers working on 17 debugging tasks in their own codebases theorizes debugging as a structured, iterative diagnostic process in which programmers update a mental model of the system to guide information gathering. Within that process, developers alternate between navigation and execution strategies and employ forward and backward tracing modes of reasoning, adapting them according to codebase context, complexity, and familiarity. Backward tracing, in this sense, complements forward tracing as a cognitive strategy for moving between hypotheses, code, and observed symptoms.
A separate line of work applies LLM-driven backward tracing to automated test generation. In ConCovUp, a multi-agent framework for concurrency testing, a backward-tracing step uses a large language model's semantic reasoning to deduce concrete inputs that satisfy complex path constraints, then iteratively refines the generated tests using dynamic execution feedback. Combined with static analysis of shared-memory accesses, this backward-tracing approach raised average Shared Memory Access Pair Coverage from 36.6% (a general agent baseline) to 68.1% across nine real-world C/C++ libraries.
Comparison with Forward Tracing
| Dimension | Forward Tracing | Backward Tracing |
|---|---|---|
| Starting point | Specified fault(s) / inputs | Specified correct behavior / effect to be explained |
| Direction | Cause → effect | Effect → cause |
| Typical implementation (hardware) | Simulation-based fault injection with explicit fault-control values | Formal model checking with unconstrained fault-control signals |
| Coverage per run | One fault, one path | All fault-signal combinations, all paths |
| Faults identified per run (hardware) | At most one | Potentially many, across multiple assertions |
| Exhaustive coverage | Practically infeasible for complex designs | Achievable through formal search |
| Use in debugging | Reasoning forward from a hypothesized cause | Reasoning backward from an observed symptom |
Limitations and Considerations
- The backward-tracing approach in hardware verification depends on the availability of mature formal model checking tools and on the tractability of the resulting proof problems; complex designs can produce long runtimes or memory pressure.
- Quality and completeness of the formal properties (SVA) directly determine which fault effects can be discovered. Effects not captured by any property will not be enumerated.
- The ConCovUp results suggest that LLM-driven backward tracing can be effective for input synthesis under complex path constraints, but evaluation was limited to nine C/C++ libraries and the general agent baseline used for comparison.
- In debugging research, the grounded theory is based on 17 tasks across a relatively small set of practitioners and is intended as theory generation rather than statistical generalization.
See Also
- Forward Tracing — the complementary technique.
- Formal Verification and Model Checking — the underlying machinery that enables hardware backward tracing.
- Single Event Upset (SEU) and Soft Error — the fault class addressed by the Ibex Core evaluation.
- SystemVerilog Assertions (SVA) — the property language used.
- RISC-V Ibex Core — the evaluation platform.