Abstract Local Execution

Overview

In the context of RISC-V compliance testing, Abstract Local Execution is the symbolic filtering step described in the paper Closing the RISC-V Compliance Gap: Looking from the Negative Testing Side (DAC 2020). It is performed by the fuzzer's filter on each candidate bytestream before the bytestream is accepted into the test suite and executed on a real (or simulated) RISC-V implementation.

The purpose of abstract local execution is to walk the local control flow of the fuzzer-generated bytestream and to check whether every reachable instruction in that flow is safe. Bytestreams whose reachable control-flow paths all satisfy the filter's safety checks are accepted; bytestreams that would exercise forbidden behavior on a reachable path are dropped.

Abstract Execution State

The filter maintains a small abstract execution state that it updates as it walks the bytestream:

• Program counter (PC) — points to the next instruction to be fetched within the bytestream. Initialized to zero (the start of the injected bytestream).
• Per-register clean/dirty mark — for each architectural register, a bit indicating whether it is currently safe to use as an address register in a memory access. All registers are initialized as dirty except x30 and x31, which are clean because the test-case template initializes them with a label pointing into data memory.
• Control-flow history — data structures used to keep track of taken/pending control-flow edges so that loops are detected and the same PC is not revisited.

Fetch–Decode–Execute Loop

The filter repeats a fetch/decode/execute loop over the bytestream:

1. Fetch. Look at the next instruction at the current PC.
2. Compressed-instruction check. Inspect the two least significant bits of the instruction word to decide whether the instruction is compressed (advances PC by 2) or normal (advances PC by 4).
3. Decode. Decode the instruction.
4. Abstract execute. Update the abstract state accordingly: advance the PC for sequential flow, fork the active path at branch/jump instructions, and update clean/dirty marks on the destination registers.

If, on any path, the filter encounters a forbidden construct, the bytestream is dropped.

Accept / Drop Semantics

A bytestream is accepted when every control-flow path starting from the initial state ends in an accepting state without traversing a forbidden instruction. A bytestream is dropped when at least one reachable path leads to a forbidden or unsafe construct.

Example

The paper illustrates the loop with a 32-byte RISC-V ASM example (Fig. 2 of the source). In that example:

• A WFI instruction exists in the program but is forbidden; however, because the filter's abstract traversal shows it is unreachable on every path, the program is still accepted.
• A BLT and a BEQ instruction fork the active abstract path so that the traversal continues at multiple successor PCs simultaneously (e.g., {P CT =28, P CF =20} and {P CT =16, P CF =28}).
• An ADD that would mark x30 dirty is also unreachable, so the subsequent LW x5, -16(x30) — which requires x30 to be clean — still passes the filter.

This shows that abstract local execution reasons about reachability, not just local instruction legality: an illegal or unsafe instruction can be tolerated as long as no path reaches it.

Interaction With the Custom Mutator

The custom mutator that injects valid RISC-V opcodes into the bytestream only emits candidates that pass the abstract local execution filter — otherwise the bytestream would simply be dropped. This constrains injected opcodes in two ways described in the paper:

• Forbidden-category instructions (e.g., WFI) are avoided.
• Branch and jump instructions are injected only with small offsets, since larger offsets are more likely to be rejected by the filter (although the rejection probability is small).
• Load/store instructions are restricted to use x30 or x31 as the address register, since those are the only registers guaranteed to be clean and to point into the test-case data memory.

If a new RISC-V ISA extension is to be supported, the filter's abstract local execution must be extended as well; otherwise the filter treats instructions from the new extension as illegal and lets them pass unconditionally.

ISA Coverage

The filter currently targets the RV32GC ISA. The accepted test-suite can therefore be executed on any sub-ISA of RV32GC (e.g., RV32I, RV32IMC). Floating-point registers are loaded and stored alongside the general-purpose registers, guarded by the riscv_fdiv GCC define that is set when a FP-capable -march is selected.

Role in the Overall Negative-Testing Pipeline

Abstract Local Execution sits between the fuzzer/mutator and the system under test:

1. The mutator proposes a bytestream.
2. The filter performs abstract local execution of the bytestream.
3. If every reachable path passes, the bytestream is wrapped in a test-case template (with start/finish sequences, register save/restore, FP register handling, etc.) and dispatched to the Instruction-Set Simulator (ISS) of the open-source RISC-V VP for execution under custom coverage feedback.

This makes abstract local execution the gatekeeper that keeps only negatively meaningful — yet reachable — test cases in the generated compliance suite.

Related Concepts

• RISC-V Instruction-Set Simulator (ISS) — the bit-true ISS of the open-source RISC-V VP that is used to execute the bytestreams that pass the filter.
• Custom coverage metrics — additional feedback signals (beyond ISS code coverage) that guide the fuzzing process once a bytestream has passed abstract local execution.
• Test-case template — the surrounding ASM scaffold into which the accepted bytestream is injected, providing start/finish sequences, register save/restore, and FP-register handling.