Constrained Random Test Generation

Overview

Constrained random test generation is one of the most widely adopted methods for generating stimuli for simulation-based hardware verification. It combines randomized test creation with design-specific constraints that keep tests valid and bias generation toward interesting, hard-to-reach, or still-untested design logic. [C1]

Core idea

The technique relies on two complementary mechanisms: [C1]

• Randomness gives test diversity.
• Constraints keep tests legal and steer them toward behaviors the verifier wants to exercise. Constraints are typically written manually.

The cited survey emphasizes that constraints serve two purposes at once: keeping tests valid and biasing them toward logic that matters for coverage closure. [C1]

Common forms of constraints

Cited evidence from hardware-accelerated random test generation work characterizes the constraints typically found in constrained random test benches in two broad categories: [C11]

• Selection of control bits. Examples include randomly selecting a grant line from among requesting masters in an arbiter model, or randomly selecting a transfer type (single/burst) from an allowable set. These constraints are typically Boolean or can be modeled as Boolean constraints without much overhead.
• Selection of data words. Examples include generating addresses that lie within a specific range so that a given device is selected in a memory-mapped architecture, or generating a starting address aligned to specific byte boundaries (e.g., 10 K byte boundaries) for a burst transfer. These constraints operate on words, and any Boolean encoding grows combinatorially because each word on a 64-bit architecture introduces 64 Boolean variables.

In practice the constraints used by verification engineers are usually simple. The most common form is a range constraint that limits the value of an individual variable. A second common form involves two variables — e.g., a randomly generated address constrained within a specified offset of a base address. Individual constraints involving more than two variables are rare in real test benches; the cited work reports that across the test bench architectures for ARM AMBA, IBM CoreConnect (IBMCC), and PCI Bus, no constraint required more than two variables, even though many variables were constrained. [C11]

Main limitation

A recurring problem is diminishing returns. Although constrained random generation produces many diverse tests, those tests tend to repeatedly exercise the same design logic. As verification progresses, most constrained random tests yield little to no effect on functional coverage. [C2]

This observation leads to a practical implication: if stimulus generation is significantly cheaper than simulation, it can be more efficient to randomly generate a large number of tests, select the most effective subset, and only simulate that subset — rather than simulating every randomly generated test. [C3]

Hardware-accelerated constrained random generation

Cited work targets the problem of synthesizing a circuit in hardware that deterministically generates pseudo-random valuations of a set of variables subject to a known set of constraints, so that constrained random value selection can be accelerated together with simulation. The synthesis target has two notable features: [C11]

• The constraints are known a priori because they are hard-coded in the test bench.
• The generated circuit must guarantee that every valuation satisfying the constraints has a non-zero probability of being selected.

The methodology works in two steps: [C11]

1. Constraint pre-processing in software. An integer linear programming (ILP) solver is used to deduce a set of regions covering the constraint-satisfying valuations. Because this step runs once in software before emulation begins, sophisticated algorithms are affordable.
2. Constrained random selection in hardware. A constrained random test generator is synthesized in hardware. It uses a pseudo-random generator based on a linear feedback shift register (LFSR), together with constraint-specific circuitry that constrains the generator within the regions produced by step 1.

The cited approach targets systems of linear constraints in which each constraint involves at most two variables, reflecting the empirical observation that such constraints dominate real industrial test benches. [C11]

Worked example: AMBA-like master address generation

The cited paper illustrates the methodology with a Master device that can initiate transfers to two Slaves on a shared bus. The slave address map is [0, 1023], with Slave₁ in [0, 511] and Slave₂ in [512, 1023]. A SystemVerilog constrained random test-bench fragment declares a randomized base (10 bits) and offset (5 bits), and inside the AnySlave state the test bench calls: [C11]

TB.randomize() with {
  base >= 0 && offset >= 0 &&
  (base + offset)       <= 511  &&
  (base + 2 * offset)   <= 1023 &&
  (base + 2 * offset)   >= 512;
}

The proposed methodology takes those test-bench constraints and pre-computes the solution region in software, then entails it in a well-defined data structure for the hardware step. [C11]

Implementation example: TL-Test cache verification framework

TL-Test is a Unit Level Verification Framework for cache systems. It supports the Tilelink protocol and cache coherence checking, and can quickly generate constrained random test cases. [C4]

It also supports converting real cache access traces into testbenches, so a designer can dump a trace from the whole XS-Core and then run the cache system alone as a trace-driven model. The same trace mode can be used for fast reproduction of functional bugs and for analysis of performance problems. [C4]

In a worked cache-coherence example, an injected bug in an L2-to-L1 grant buffer (d.data := data << 8, i.e., Grant Data shifted by 8 bits) is caught by TL-Test: the framework generates a constrained random test case and flags the issue at address 0x4000. The resulting TL-Log can then be grepped for that address to identify the precise cycle of the wrong transaction. [C4]

Implementation example: V²PRO vector co-processor self-testing

In a RISC-V-based system with a V²PRO vector co-processor, random vector instruction generation requires explicit constraint checks during generation and register-file addressing. The cited evidence describes three families of constraints: [C5]

• RAW-hazard avoidance. During vertical (sequential) processing of vector elements in the vector lane pipeline, source and destination operands can generate Read-After-Write hazards. Because the vector hardware explicitly avoids control logic for hazard resolution in order to reach high operating frequencies, the generator checks that randomly generated vector operand addresses do not produce RAW hazards over a period set to the pipeline depth.
• Chaining / deadlock avoidance. When a vector lane requires chained data, the data-generating vector instruction must appear before another vector instruction can execute on the waiting lane. To avoid deadlocks (e.g., situations where all vector lanes wait for chained data and no further instruction is issued), a constraint check is performed during operand source selection. The implementation tracks the individual chaining states of vector lanes during generation.
• Sequence finalization. When chain dependencies are introduced (for example, by generating a vector instruction with a chain input operand), the generator emits finalizing vector instructions on the source vector lane to produce the needed chained data. Chains are generated by random selection of vector instruction parameters (e.g., chain source/target attribute) and added to the executed sequence; finalization instructions are chosen based on the final chain state to ensure valid execution.

After execution, the stored results of the V²PRO co-processor and the RISC-V "twin" are compared; on a mismatch, verification fails and detailed results (the executed instruction sequence, in- and output data, resulting register states) are reported. [C5]

Implementation example: PATARA framework

PATARA is an open-source tool that implements and extends the REVERSI post-silicon validation approach. It imports processor and instruction descriptions from XML files that can be reconfigured for different processors and instruction sets. [C6]

Within PATARA: [C6]

• The instruction list to be tested is selected from the XML description.
• Different instruction sequences are generated depending on the test mode (single-instruction tests or more complex test procedures).
• Modification and restoring operations are generated, and the content of the register file is initialized with random values.
• The output is a set of assembly files for the target processor.

For custom ISA extensions (such as RISC-V), the description files specify the layout of the new instructions and the corresponding sequence to restore custom operations. For example, the RISC-V ADD instruction is defined in PATARA with SUB as its reverse counterpart, along with variants of immediate and signage data. [C6]

PATARA also supports stacked test cases: in this interleaving process, modification operations of test cases are chained together, and the restoring operations are performed in the reverse order of the modifications. Multiple stacks can be interleaved to produce arbitrarily long test cases. [C6]

RISC-V test generation landscape

The cited compliance-testing literature surveys several RISC-V-targeted test-generation approaches, of which constrained random generation is one style: [C7]

• Torture Test generator [1] (Scala-based): generates tests by integrating pre-defined randomized test-sequences.
• RISCV-DV [10] (Google): uses SystemVerilog in combination with UVM to generate RISC-V instruction streams based on constrained-random descriptions. It requires a commercial RTL simulator providing SystemVerilog and UVM support.
• Fuzzing-based approach [22]: generates randomized instruction streams as platform-dependent binary files (ELFs).

The cited work notes that these approaches are designed to continuously generate randomized test-cases for verification purposes, but do not support the compliance testing format, and that mutation-based compliance testing is therefore complementary. [C7]

The same survey mentions formal verification approaches such as riscv-formal [8] and the OneSpin 360 DV RISC-V verification app [6], which target verification of an implementation rather than generating randomized test cases. [C7]

Related test-program generation methods

Beyond RISC-V, the cited surveys describe additional test-generation families that complement constrained random generation: [C7]

• Model-based techniques with constraint solving (e.g., [13–15, 27]) — including an optimized test-generation framework that propagates constraints among multiple instructions, and a constraint-based coverage model describing execution paths of individual instructions.
• Coverage-guided test generation based on Bayesian networks [16] / [17] and other machine learning techniques [25] / [11, 23].
• Fuzzing [29] / [26], including ISS-level coverage-guided fuzzing [19, 22].
• Mutation-based testing, originally a software-domain technique, and hardware fault injection (e.g., [30]) for measuring test-case quality on RTL designs.

The cited EPEX work additionally describes an equivalent-program-execution verification approach in which a formal ISA model and an SMT solver are used to replace each instruction of a test program P with an equivalent instruction sequence P̂_ij (potentially of length j > 1), so that two instantiations of the same processor implementation execute P and P̂ and are checked for equal architectural states. EPEX is presented as complementary to constrained random and coverage-guided generation because it broadens existing tests automatically and extends verification across different data and control paths. [C10]

The mutation-based compliance testing work itself uses mutation classes together with a reference Instruction Set Simulator and a symbolic execution engine: a mutant is killed if any test case in the compliance test suite makes the mutant's execution differ from the reference's execution. Alive mutants are then passed to the mutation solver, which uses symbolic execution to generate specific test cases. [C7]

Cross-level testing and constraint propagation

The cited EPEX related-work section also notes cross-level testing approaches for processor verification that generate an endless instruction stream on-the-fly during simulation (e.g., [21]). These complement constraint-propagation techniques [9, 12] that handle multiple instructions effectively. [C10]

Relationship to coverage-directed test selection

The cited arXiv paper presents coverage-directed test selection as a direct response to the inefficiency of plain constrained random testing late in verification. It uses supervised learning from coverage feedback to perform automatic constraint extraction and test selection, biasing simulation toward tests that are more likely to increase functional coverage. The paper claims this can: [C8]

• reduce manual constraint writing,
• prioritize effective tests,
• reduce verification resource consumption, and
• accelerate coverage closure on a large, real-life industrial hardware design.

A related companion paper proposes a hybrid intelligent testing approach that combines coverage-directed test selection with novelty-driven verification (learning to identify and simulate stimuli that differ from previous stimuli) to address each method's individual limitations. [C9]

Practical characterization

Across the provided evidence, constrained random test generation can be characterized as:

• a widely used stimuli-generation technique for simulation-based verification; [C1]
• a method that combines randomness for diversity with manually written constraints to keep tests valid and targeted, where the constraints most often fall into two categories — control-bit selection (Boolean) and data-word selection (range / two-variable linear) — and rarely involve more than two variables in practice; [C1][C11]
• a method whose efficiency can degrade as functional coverage saturates; [C2]
• a foundation for more selective, learning-guided verification flows such as coverage-directed test selection and novelty-driven verification; [C3][C8][C9]
• a target for hardware acceleration via a two-step flow that pre-computes the constraint solution region in software using an ILP solver and then synthesizes a hardware constrained random generator (LFSR-based pseudo-random source plus constraint-specific circuitry) that guarantees every valid valuation has a non-zero probability of being selected; [C11]
• a style of test generation realized in practice by dedicated unit-level frameworks (TL-Test) [C4], by online self-testing flows in RISC-V systems with vector co-processors (with explicit hazard, chaining, and finalization constraints) [C5], by XML-based, randomly-initialized self-test generators such as PATARA [C6], by SystemVerilog+UVM-based instruction-stream generators such as RISCV-DV [C7], by Scala-based randomized-sequence template generators such as RISC-V Torture [C7][C10], by SMT-based equivalent-program-execution approaches such as EPEX [C10], and by ISS-level coverage-guided fuzzers [C7][C10];
• complementary to mutation-based compliance testing, which uses mutation classes and symbolic execution to derive targeted test cases. [C7]