Binary Search-Based Minimization

Overview

Binary search-based minimization is a test-case reduction strategy used by the RISCSmith tool to compress the size of a divergent instruction sequence down to the smallest program that still reliably reproduces a detected bug in a RISC-V CPU ^[1].

Role in RISCSmith's On-the-fly Bug Analysis

Within RISCSmith's on-the-fly bug analysis pipeline, the binary search-based minimization step is applied as follows ^[1]:

1. Detection of a divergence. RISCSmith observes a behavioral difference—either in exception behavior, register state, or memory contents—between a target RISC-V CPU implementation and a golden reference model such as Spike.
2. Structured logging. All executed RISC-V instructions from the target CPU are automatically logged, timestamped, and organized into a structured reproduction log.
3. Deterministic reproduction. Using the reproduction log, RISCSmith deterministically reproduces the divergence.
4. Binary search-based minimization. A binary search–based minimization algorithm is applied to the reproduced instruction sequence to isolate the shortest instruction sequence that consistently triggers the bug.

Purpose

By repeatedly halving the candidate instruction sequence and retaining only the half whose execution still exposes the divergence, binary search-based minimization yields a minimal reproducer. This minimal sequence is easier for engineers to inspect, share, and map onto specific hardware locations inside the CPU under test, supporting rapid root-cause analysis of the kinds of bugs RISCSmith reports—such as the 18 newly detected bugs across PicoRV32 and CVA6 ^[1].

Implementations

• RISCSmith — applies a binary search–based minimization algorithm to logged RISC-V instruction traces to shrink divergent test programs down to a minimal reproducer ^[1].