Constrained Random Verification

Overview

Constrained Random Verification (CRV) is a constrained-random or constraint-based testcase-generation technique used in hardware design verification. In the evidence available, CRV is described as a stimulus generator that "samples uniformly over the subset of legal actions at each cycle, modeling typical constrained-random stimulus," and is used as one of several compared stimulus-generation methods in recent chip-verification studies. [crv-stimulusrl]

In the FuSS paper, CRV is grouped with "random and constrained-random verification" as part of "conventional verification approaches" that "struggle to achieve adequate coverage of the vast state space in modern SoCs," motivating coverage-guided and semi-formal alternatives. [crv-fuss]

In industry-oriented reporting on RISC-V verification, CRV is described as one of the methodologies needed to achieve complete RISC-V verification, exemplified through "coverage driven simulation based on UVM constrained random methods and compliant with the Universal Verification Methodology (UVM) standard," using the Google RISCV-DV open-source project as an example flow. [crv-riscv-uvm]

Description from evidence

The provided evidence characterizes CRV at a high level rather than specifying a single internal algorithm:

• Action space sampling: CRV is modeled as sampling actions uniformly from the subset of legal actions at each cycle, rather than uniformly over the entire action space. [crv-stimulusrl]
• Legality enforcement: CRV enforces protocol legality by construction (sampling only from legal actions), which means it does not explicitly target bins corresponding to illegal operations; in the StimulusRL evaluation, this is why CRV converges to fewer bins than Random on benchmarks such as FIFO8 where some bins encode illegal-operation attempts. [crv-stimulusrl]
• No coverage feedback or learned policy: In the compared taxonomy of stimulus generators, CRV uses legality constraints but neither coverage feedback nor a learned policy. [crv-stimulusrl]
• Runtime profile: CRV completes quickly relative to learning-based methods because it only samples actions and steps the design model; on the DMCache design, a 2000-step run takes 0.537 ± 0.004 s, compared with 0.378 ± 0.004 s for Random and 2.111 ± 0.005 s for StimulusRL. [crv-stimulusrl]
• Coverage limitations: CRV is described as struggling to achieve adequate coverage in modern SoCs; "even millions of random or constrained-random test vectors (input stimuli) fail to activate a majority of complex execution paths, leaving many potential corner cases untested." [crv-fuss]

Relationship to coverage-driven simulation

The SemiEngineering whitepaper on UVM functional coverage for RISC-V cores describes coverage driven simulation based on UVM constrained random methods that comply with the Universal Verification Methodology (UVM) standard, using Google RISCV-DV as the open-source test-generator. CRV supplies the stimulus-generation mechanism, while coverage-driven simulation supplies the feedback metric and closure methodology that guides test selection and randomization weights. [crv-riscv-uvm]

Python-based CRV environments

A 2024 study evaluates a Python-based verification environment for constrained random verification built on open-source frameworks such as PyUVM (a Python-based UVM 1.2 implementation) and PyVSC (which facilitates constrained randomization and functional coverage), and compares the resulting testbenches against established SystemVerilog-UVM methodology across multiple design IPs. [crv-pyuvm]

Formal distribution guarantees for CRV

A separate line of work addresses the fact that conventional CRV solutions provide no formal guarantees on the distribution of generated stimuli. The TraceSampler paper presents an algorithm based on Algebraic Decision Diagrams for sampling bounded traces (sequences of states) of a sequential circuit with provable uniformity (or bounded bias) guarantees while satisfying given constraints, and reports that TraceSampler outperforms alternative approaches offering similar uniformity guarantees. [crv-tracesampler]

Relationship to RISC-V verification

A reference list in a RISC-V test-sequence generation paper cites Constrained random verification for RISC-V: Overview, evaluation and discussion by Ahmadi-Pour, Herdt, and Drechsler (MBMV 2021; 24th Workshop, 2021: 1–8), placing CRV directly within the RISC-V verification literature. [crv-riscv-overview]

Relationship to coverage-guided fuzzing

The strongest direct evidence connecting CRV-adjacent testcase generation to coverage-guided fuzzing comes from the paper Verifying Instruction Set Simulators using Coverage-guided Fuzzing. That paper proposes using coverage-guided fuzzing (CGF) for ISS verification, implemented on top of LLVM libFuzzer with a functional coverage metric that complements code coverage and a mutation procedure tailored to ISS verification. [cgf-method]

The paper reports a case study on three publicly available RISC-V ISSs. It states that the fuzzer was effective at maximizing most coverage metrics and found new errors in every considered ISS, including an error in the official RISC-V reference simulator Spike. [cgf-results]

For CRV, the relevant comparison point is complementarity: the paper states that fuzzing is useful for triggering and checking corner cases and error cases and "can complement other testcase generation techniques." Its references include constraint-based and constrained-random verification work, indicating that CRV belongs to the broader testcase-generation landscape against which CGF is positioned. [cgf-complementarity]

Practical interpretation from the evidence

Within the limits of the provided evidence, CRV should be treated as a constrained-random stimulus-generation technique that samples from the legal action subspace, commonly used as a baseline in chip-design verification studies. Coverage-driven simulation wraps CRV with UVM-compliant feedback and closure methodology, coverage-guided fuzzing and reinforcement-learning-based stimulus agents (such as StimulusRL) are presented as related but distinct techniques that can complement CRV (particularly for ISS corner-case and error-case discovery and for addressing CRV's coverage limitations on complex SoC designs), and formal approaches such as TraceSampler address CRV's lack of distribution guarantees by providing provably uniform sampling under given constraints. [crv-fuss][crv-stimulusrl][crv-riscv-uvm][crv-tracesampler][cgf-complementarity]