Skip to content
STIMSMITH

Constraint Solving for Instruction Generation

Concept WIKI v1 · 5/27/2026

Constraint solving for instruction generation is a model-based test-generation technique used to automatically construct instruction sequences that reach desired architectural states while avoiding undefined behavior. The provided evidence describes its use in CHERI-MIPS work based on an L3 specification, its application to CHERI ARM Morello from a Sail model, and its expected role in automating templates for deep architectural states in TestRIG-related workflows.

Overview

Constraint solving for instruction generation is a technique for automatically producing instruction sequences from a formal architectural model. In the evidence, the technique is described as generating instruction sequences that reach a desired state while avoiding undefined behavior. This was used in prior CHERI work and is discussed as a future direction for TestRIG-style generation of templates targeting deep states in architectural models.

Use in CHERI-MIPS testing

Previous CHERI work generated tests from a formal model of the CHERI-MIPS ISA. That model was written in the L3 Specification Language, compiled from L3 to HOL4, and then used with constraint solving to automatically generate instruction sequences. The goal of those generated sequences was to reach a desired state without triggering undefined behavior.

Use with Sail models

The same approach is reported as having been applied to the CHERI ARM Morello instruction set starting from a Sail Language model. The evidence also describes ongoing work on a Sail-OCaml VEngine with direct access to the data structures of a Sail RISC-V model. This is intended to eliminate independent encodings in the VEngine and support further automation of templates that target specific deep states in an architectural model using constraint solving.

Relationship to template-based generation

The evidence also references IBM’s Genesys-Pro in the context of templates that can intelligently solve for desired deep states. In the TestRIG discussion, constraint solving is presented as a way to automate generation of templates aimed at specific deep states in an architectural model.

Role in verification workflows

Within the provided TestRIG evidence, constraint solving is positioned alongside randomized and model-based testing techniques. The surrounding workflow includes reduced counterexamples, smart shrinking, non-shrinkable initialization sequences, and assertions, but the constraint-solving-specific contribution is the automatic construction of instruction sequences or templates that drive the implementation toward targeted architectural states.

LINKED ENTITIES

3 links
Genesys-Pro USES
L3 Specification Language USES
Sail Language USES

CITATIONS

6 sources
6 citations
[1] Constraint solving was used to automatically generate instruction sequences that reach a desired state without triggering undefined behavior. Randomized Testing of RISC-V CPUs using Direct
[2] Previous CHERI work used a CHERI-MIPS ISA formal model written in the L3 specification language, compiled from L3 to HOL4, before applying constraint solving for instruction generation. Randomized Testing of RISC-V CPUs using Direct
[3] The same constraint-solving approach was applied to the CHERI ARM Morello instruction set starting from a Sail model. Randomized Testing of RISC-V CPUs using Direct
[4] A Sail-OCaml VEngine with direct access to Sail RISC-V model data structures is described as eliminating independent encodings in the VEngine and enabling future automation of templates for deep architectural states using constraint solving. Randomized Testing of RISC-V CPUs using Direct
[5] IBM’s Genesys-Pro is referenced in connection with template-based solving for desired deep states. Randomized Testing of RISC-V CPUs using Direct
[6] The surrounding TestRIG workflow includes smart shrinking, non-shrinkable sequences, and assertions. Randomized Testing of RISC-V CPUs using Direct