Assembly-Level Instruction Generation

Overview

Assembly-level instruction generation is a technique used in hardware fuzzing to produce sequences of assembly instructions as inputs to a processor design under test (DUT). TheHuzz employs this technique to generate instructions that increase desired coverage values, thereby finding hardware bugs exploitable from software. The generated instructions are executed directly on the processor RTL simulation without requiring an operating system.

Input Format

In TheHuzz, each input to the DUT consists of two types of instructions:

• Configuration Instructions (CIs): Setup the baremetal environment by configuring the stack, exception handler table, and clearing general-purpose registers. CIs are not mutated, ensuring correct initialization of the processor for fuzzing.
• Test Instructions (TIs): The actual instructions used to fuzz the processor. TIs are generated by the instruction generator and are mutated to explore new coverage points.

This baremetal environment allows TheHuzz to run instructions directly on the processor without the need for an operating system.

Generation Strategy

Seed Generation

• Each seed input contains 20 TIs, a number selected empirically based on observations before a random TI leads to a deadlock.
• Events such as exceptions, branch, jump, system calls, and atomic instructions can cause the control flow of the processor to jump to a different location or freeze for many clock cycles (e.g., waiting for resources in the case of atomic instructions).
• First half of TIs: Generated uniformly from instructions less likely to trigger such problematic events (e.g., arithmetic and logical instructions). This maximizes the number of TIs executed by TheHuzz in each simulation.
• Other half of TIs: Generated uniformly from all instructions returned by the optimizer.
• The processor is reset after the execution of every 20 instructions and simulated with new input, resulting in periodical initialization of the processor control flow back to the location of the TIs.
• The GCC toolchain compiles C programs to generate executable files which are loaded onto the processor RAM and used as seeds.

Mutation-Based Generation

The stimulus generator mutates current inputs to generate new inputs and discards underperforming inputs. Seed inputs are used to generate the first set of new inputs.

Key characteristics of mutation:

• Instructions are mutated directly as binary data rather than at a higher abstraction level such as assembly. This enables mutation of all bits of the instruction based on the mutation technique used.
• Mutating at the binary level allows testing the processor with out-of-spec inputs like illegal instructions (i.e., instructions not specified in the ISA) generated through mutation of the opcode bits of the instruction.
• This approach can detect issues that other verification techniques may not detect, such as bugs that cannot be discovered with legal instructions alone.
• Only TIs are mutated; CIs are not mutated.

Mutation Types

The mutation techniques are classified into two types:

1. Data-only mutations: Mutate only the data bits while keeping the opcode unchanged. These increase coverage on different data paths that are close to each other.
2. Opcode mutations: Mutate the opcode bits, enabling generation of illegal instructions that can uncover bugs related to instruction decoding and validation.

Optimization

TheHuzz uses an optimization framework to select the most effective instruction-mutation (IM) pairs:

• A Profiler characterizes the control and data flow paths explored by each IM pair via hardware simulation.
• An Optimizer solves an optimization problem to find the smallest subset of IM pairs, denoted as Q, that covers all coverage points identified during the profiling stage.
• The optimizer generates weights for each IM pair; the seed generator uses weights (wI) to select instructions, and the stimulus generator uses weights (wM) to select mutation techniques, eliminating underperforming instructions.

Coverage Metrics Driven by Instruction Generation

The generated assembly instructions target several coverage metrics that model intrinsic hardware behaviors:

• Branch coverage: Detects bugs such as incorrect implementation of logic for specific instructions (e.g., FENCE.I).
• Toggle coverage: Detects bugs like incorrect propagation of exception types.
• Condition coverage: Detects bugs related to illegal instruction execution.
• FSM coverage: Captures different FSM states and transitions, e.g., cache coherency violations.
• Expression coverage: Tests combinational blocks, e.g., incorrect ALU logic implementation.

Use in Bug Detection

Assembly-level instruction generation in TheHuzz has been used to detect numerous bugs across multiple open-source processor designs, with coverage types varying by bug class and hardware common weakness enumeration (CWE) mapping.