Randomized Instruction Stream Generation

Definition

Randomized instruction stream generation is a processor-level stimuli generation technique in which binary instruction words are produced at random and fed to the design under verification (DUT). The DUT's resulting architectural state (typically register and memory values) is then compared against a reference model, most commonly an instruction set simulator (ISS) of the same instruction set architecture. It is described in the processor verification literature as the classical approach to test program generation, against which more directed methods are measured.

"To generate processor-level input stimuli several test generation techniques have been proposed that improve upon the classical randomized instruction stream generation." — DATE 2023, Processor Verification using Symbolic Execution: A RISC-V Case Study (chunk 822339b8-e783-4af4-9103-70d19f4317fc)

Role in Processor Verification Flows

In a typical cross-level co-simulation flow, the randomized instruction stream is supplied to both the RTL processor description (translated to a C++ model via a tool such as Verilator) and the ISS reference. After execution, the architectural state of the DUT and the ISS is compared and any mismatch indicates a potential bug.

Key characteristics:

No explicit input grammar is required; the generator only needs to produce valid-enough binary words.
The technique scales easily because generation cost is negligible compared to simulation cost.
Effectiveness on hard-to-reach corner cases is limited, because purely random streams rarely hit rarely-taken branches or rarely-combined instruction interactions.

Limitations and Known Issues

Two main weaknesses are reported in the literature:

Coverage stagnation. Random streams plateau in coverage quickly; novel behaviors are rarely discovered without feedback.
Co-simulation complexity when the stream evolves dynamically. When the stream is not fixed but dynamically evolves (e.g., a single endless stream where the same program counter returns different instructions over time), aligning the ISS and the RTL pipeline becomes non-trivial. The core performs speculative pre-fetching and out-of-order execution, so the testbench must reason about pipeline timing to compare registers at the right cycle.

"They generate one single endless instruction stream that dynamically evolves at runtime, this means that for the same program counter, different instructions will be returned over time. Moreover, in combination with the different fetch behavior of the ISS and RTL-core, for example the core has a pipeline with branch prediction and hence performs speculative pre-fetching of instructions, this dynamic instruction stream property makes the co-simulation setup very complex." — GLSVLSI 2022, Efficient Cross-Level Processor Verification using Coverage-guided Fuzzing (chunk bd64b9b0-cb73-4254-8410-6f3c470f62c6)

Extensions Beyond Classical Random Generation

Because of the limitations above, randomized instruction stream generation is usually used as a starting point that is augmented with one or more of the following directions:

Constraint-based / model-based generation

Replace pure randomness with a constraint-satisfaction formulation that guides the generated program toward legal and interesting combinations of instructions and operands. Examples in the RISC-V verification literature include the Genesys-Pro line of work and constraint-satisfaction random test program generation.

Coverage-guided fuzzing (CGF)

Treat the instruction stream as the input to a coverage-guided grey-box fuzzer (e.g., AFL, libFuzzer). The fuzzer mutates an initial random seed, and edge coverage feedback from the ISS (or from a co-simulation of ISS + RTL) steers mutation toward new behaviors. Because no grammar is required, the fuzzer can robustly mutate binary instructions. This direction is described as "a particular effective technique" for processor verification.

"Modern coverage-guided fuzzer work by mutating randomly created data and are guided by coverage, hence they do not require an input model specification." — DATE 2023, Processor Verification using Symbolic Execution: A RISC-V Case Study (chunk 822339b8-e783-4af4-9103-70d19f4317fc)

Coverage-guided aging

Combine randomized instruction stream generation with an aging mechanism that mutates and grows successful seeds to keep coverage improving over long runs. This is the basis of the Bruns et al. cross-level processor verification approach, which generates one endless instruction stream whose evolution is directed by coverage feedback.

Symbolic execution

Use symbolic values for instructions and register initializations, and let a symbolic execution engine (e.g., KLEE) drive the exploration. Symbolic execution is positioned as a more recent alternative that mitigates the model-specification cost of purely constraint-based methods.

Reinforcement learning and machine learning

Steer test generation with reinforcement learning or Bayesian-network coverage models to focus on coverage gaps. These are described as further refinements of coverage-directed test generation.

Use in the RISC-V Verification Literature

In the RISC-V context, randomized instruction stream generation appears as the baseline against which newer approaches are compared:

Constrained random verification for RISC-V surveys constrained-random methods that explicitly build on top of random instruction generation.
Towards specification and testing of RISC-V ISA compliance and Closing the RISC-V compliance gap describe negative-testing approaches that complement randomized generation.
The Cross-level processor verification via endless randomized instruction stream generation with coverage-guided aging paper (Bruns et al., DATE 2022) is the canonical reference for the coverage-guided aging extension and uses randomized instruction stream generation as the underlying generation mechanism for an endless stream.
The A RISC-V Test Sequences Generation Method Based on Instruction Generation Constraints article (Journal of Electronics & Information Technology, 2023) explicitly uses instruction-generation constraints on top of randomized streams to improve the quality of generated RISC-V test sequences.

References

Bruns, Herdt, Jentzsch, Drechsler. Cross-level processor verification via endless randomized instruction stream generation with coverage-guided aging. DATE 2022.
Herdt, Große, Drechsler. Towards specification and testing of RISC-V ISA compliance. DATE 2020.
Herdt, Große, Drechsler. Closing the RISC-V compliance gap: Looking from the negative testing side. DAC 2020.
Bruns, Herdt, Jentzsch, Drechsler. Efficient Cross-Level Processor Verification using Coverage-guided Fuzzing. GLSVLSI 2022.
DATE 2023. Processor Verification using Symbolic Execution: A RISC-V Case Study.
Ahmadi-Pour, Herdt, Drechsler. Constrained random verification for RISC-V: Overview, evaluation and discussion. MBMV 2021.
Bin, Emek, Shurek et al. Using a constraint satisfaction formulation and solution techniques for random test program generation. IBM Systems Journal, 2002.
Adir, Almog, Fournier et al. Genesys-Pro: Innovations in test program generation for functional processor verification. IEEE Design & Test of Computers, 2004.
Liu, Hu, Liu, Han, Liu. A RISC-V test sequences generation method based on instruction generation constraints. Journal of Electronics & Information Technology, 2023.