Bottom-Up Instruction Space Exploration

Overview

Bottom-Up Instruction Space Exploration is the sequence-generation strategy used by the RISCover fuzzer to test closed-source RISC-V CPUs for user-exploitable architectural security vulnerabilities. Instead of uniformly random instruction selection or coverage-guided mutation (which is unavailable to black-box post-silicon fuzzers), RISCover starts from the smallest, most promising part of the RISC-V encoding space and gradually grows the search space as testing proceeds.

The strategy is motivated by the C1 "Sequence Generation" challenge identified in the RISCover paper: with no feedback for coverage, the fuzzer must rely on the number of bugs found and time-to-bug as quality metrics, and must reconcile a very large encoding space with the need for depth (many instructions per sequence) per test case.

Distribution of the RISC-V 4-Byte Instruction Space

RISCover's bottom-up strategy is grounded in a measured distribution of the RISC-V instruction space (Table 1 of the paper):

The remaining 14.49 % of the 4-byte instruction space is unknown or not specified — either reserved for future use, unclaimed, or undocumented. Because these encodings are rarely validated by upstream tests and real-world software, RISCover treats them as a high-yield starting point.

How the Bottom-Up Approach Works

The server-side generator combines three building blocks to construct instruction sequences, starting from the rarest encodings and widening as the campaign progresses.

1. Instruction Classification

The generator uses the official RISC-V Opcodes repository as a machine-parsable source of truth. The repository encodes all standard RISC-V instructions and several unratified ones, and clusters them into their respective extensions. By examining specific bits in the instruction encoding, RISCover can classify whether an encoding is a standard instruction, a vendor-specific instruction, or undefined. This produces the groups visualized in Figure 3 of the paper (RISC-V Opcodes, vendor documented, unratified, vector, Zfh, C extension, etc.) and underpins the whole bottom-up stratification.

2. Instruction Exclusion

Encoding-based filtering is also used to exclude instructions or entire instruction classes that would distort the differential comparison:

• CSR-based instructions are excluded in general, because they can change the behavior of subsequent instructions on the current core and would introduce false positives in the architectural state differences.
• frcsr and fscsr are the only CSR-touching instructions permitted, because they read/modify the Floating-Point Control and Status Register (fcsr), which is part of the CPU's well-defined architectural state.
• Coverage of other CSRs is left to future work.

3. Weighted Instruction Selection

The core of the bottom-up idea: instructions are sampled inversely proportional to their real-world frequency. This steers the search toward rarely used or undocumented encodings, which the authors argue have a higher potential for harboring undiscovered vulnerabilities.

Key parameters of the weighted selection:

• Frequency source: the paper analyzed 1.36 billion disassembled instructions from 84,164 Debian software packages to build the real-world frequency distribution.
• Inverse-frequency sampling: commonly executed instructions (e.g., integer adds, loads) are sampled less often; rare or undocumented instructions are sampled more often.
• Immediate values: drawn from a predefined set of "interesting" corner-case values (e.g., 0, negative numbers, maximal integer values), and augmented with a randomly chosen value in 1 out of every 5 instructions to ensure broad encoding coverage.
• Registers: source and target registers are initialized with a limited set of 5 possible registers starting from x0, deliberately introducing dependencies between instructions in a sequence.
• Undocumented encodings: when an instruction is not defined in the RISC-V Opcodes repository, RISCover generates a random 4-byte value that cannot be decoded to a valid instruction. For any undocumented instruction, the full instruction encoding with all bits set is already a valid test, so no bitfields need to be filled in. This allows the fuzzer to cover the entire instruction space, including the 14.49 % unknown portion.
• Sequence length: fixed at runtime. The evaluation reports that 3–5 instructions provide an optimal trade-off between vulnerability-discovery effectiveness and computational efficiency.

Why "Bottom-Up"?

The phrase refers to two stacked gradients:

1. Encoding-space gradient (low → high coverage): the fuzzer first targets the undocumented 14.49 % of the space, then progressively includes documented but uncommon encodings, and finally converges on the more common ratified parts. This is the literal "bottom" — the rarest, least-validated encodings.
2. Frequency gradient (rare → common): within the documented portion, instructions are weighted by inverse real-world frequency, again starting from the rarest usages first.

The authors justify this prioritization empirically: while RISCover also uncovers architectural bugs in commonly used instructions, these tend to be functional discrepancies rather than directly exploitable security vulnerabilities. Rare and undocumented encodings are the more promising attack surface.

Relation to Other RISCover Components

• The bottom-up generator runs on the server in RISCover's centralized client/server architecture. The server constructs sequences and input registers and ships them to multiple RISC-V CPU clients for execution.
• The clients are constrained RISC-V CPUs; the heavy sequence-construction work is therefore deliberately offloaded to the server.
• Differences in architectural state observed by the server across CPUs are logged as reproducer files, which can be compiled as standalone binaries for further analysis (optionally reduced with techniques from Solt et al.).

Limitations / Open Work

• Coverage of CSRs other than fcsr is explicitly left to future work.
• The classification does not need to separate ISA extensions perfectly; encoding-based filtering is described as a rough but deterministic guidance technique to prevent wasting resources on encodings that mainly consist of large-immediate instructions.
• Because RISCover is a black-box post-silver fuzzer, no coverage feedback is available; the strategy is evaluated purely on the number of findings and time-to-bug.