Skip to content
STIMSMITH

Basic Block Agent

Concept WIKI v2 · 8/19/2026

The Basic Block Agent is the low-level micro-step policy in HiFuzz's two-level hierarchical reinforcement-learning architecture. Within the global context fixed by the Program Agent, it decides the instruction-category mix and termination mode of each basic block, is trained with Proximal Policy Optimization (PPO), and receives both an extrinsic coverage-based reward and an intrinsic semantic novelty reward derived from a frozen Semantic-Aware Basic Block Encoder.

Overview

The Basic Block Agent is the low-level micro-step policy in HiFuzz's two-level hierarchical reinforcement-learning architecture. While the high-level Program Agent selects the global structure of a test program, the Basic Block Agent decides the instructions inside each basic block (BB) at micro steps within that global context.[C1]

HiFuzz separates these roles because program-level choices such as memory layout, BB count, and control flow operate at a different abstraction level and timescale from instruction-level decisions such as operand selection, dependency management, and BB termination.[C1] The decomposition follows the hierarchical reinforcement-learning framework of Sutton, Precup, and Singh, in which a high-level policy selects among temporally extended options whose execution is carried out by lower-level policies.[C8]

Role in HiFuzz

The low-level Basic Block Agent serves as the executor of HiFuzz. Given the global context set by the Program Agent, it determines the mix of instruction categories within a specific basic block (such as integer arithmetic, floating-point operations, or memory access) and decides when a basic block should terminate.[C2] Concretely, for each basic block, HiFuzz represents the local generation problem as a BB Level Config: a target instruction-category mix, such as integer, floating-point, memory, or CSR instructions, plus a termination mode such as branch, jump, or exception. A constrained generator then instantiates concrete instructions while enforcing constraints including operand dependencies, privilege constraints, address legality, and jump-target consistency.[C2]

The Basic Block Agent therefore does not directly emit every concrete instruction. Instead, it outputs compact category-level distribution parameters and a BB-termination signal. This avoids an impractically large combinatorial action space that would grow with both basic-block length and ISA breadth, while still allowing the policy to influence instruction mix and BB termination.[C3]

Learning algorithm: PPO

Because the Basic Block Agent makes decisions at every micro-step of the generation process, it requires more frequent feedback than the Program Agent. To obtain stable updates that do not drift too far from successful strategies, HiFuzz trains the Basic Block Agent with Proximal Policy Optimization (PPO), an actor-critic algorithm introduced by Schulman, Wolski, Dhariwal, Radford, and Klimov.[C2][C9]

The PPO clipped-surrogate objective used for the agent's policy $\theta$ is:

text L^CLIP(θ) = Ê_t [ min(r_t(θ) Â_t, clip(r_t(θ), 1−ε, 1+ε) Â_t) ]

where $r_t(\theta)$ is the probability ratio between the new and old policy and $\hat{A}_t$ is the estimated advantage. The clipping range $\epsilon$ bounds how far a single update can move the policy, which keeps micro-step learning stable across the many decisions made per basic block.[C2]

Multi-head Actor-Critic

The PPO implementation uses a multi-head Actor-Critic architecture. The actor emits the BB-level configuration, and the critic uses separate value heads for intrinsic and extrinsic returns so that reward streams with different scales and variances are not collapsed into one target.[C3] The implementation uses intrinsic/extrinsic reward coefficients $\alpha_{\text{int}}=1$ and $\alpha_{\text{ext}}=2$, plus an extrinsic-baseline diminishing factor $\gamma=0.75$.[C6]

Reward design

The agent receives both intrinsic and extrinsic rewards.

Intrinsic reward. The intrinsic signal is a semantic novelty reward inspired by Random Network Distillation, but it replaces a random target projection with a Semantic-Aware Basic Block Encoder. This makes novelty depend on learned, micro-architecture-aware basic-block features rather than arbitrary random features.[C4] The encoder itself has three components: (i) a structured tokenizer that converts RISC-V instructions into semantically tagged token sequences (operand roles such as destination, source, memory address, CSR, and immediate; execution-unit tags such as INT_ALU, LOAD, STORE, BRANCH, FPU; and symbolic CSR names such as 0x300→mstatus); (ii) a Bi-LSTM backbone chosen for its structural match to short, strictly ordered instruction sequences; and (iii) a two-stage training pipeline consisting of self-supervised Masked Language Modeling on RISC-V assembly followed by supervised fine-tuning on a micro-architecture-aware similarity metric called BB-Sim.[C7] The frozen encoder is deliberately DUT-agnostic so the same trained model can be deployed across Rocket, BOOM, and CVA6 without retraining.[C7]

The intrinsic reward is computed as cluster-distance novelty on frozen BB Encoder embeddings:

text R_int = min_k (1 − cos(E(bb), C_k))

Here, E(bb) is the L2-normalized embedding of the generated basic block, and {C_k} are online-updated cluster centers.[C4]

Extrinsic reward. The extrinsic reward is based on coverage improvement normalized against a dynamic baseline:

text R_ext = (Δcov − baseline) / baseline baseline = mean_recent_rewards * γ

This gives the Basic Block Agent a coverage-derived learning signal while compensating for recent reward scale through the baseline.[C4]

Dual-advantage objective

HiFuzz's Basic Block Agent uses a dual-advantage actor loss to keep the intrinsic and extrinsic reward streams separate through learning. The actor loss combines intrinsic and extrinsic Generalized Advantage Estimation values with separate weights:

text L_actor = α_int * A_int + α_ext * A_ext

The total objective augments this actor loss with per-head critic mean-squared-error losses and an entropy bonus:

text L = L_actor + Σ_{k∈{int,ext}} MSE(V_k(s_t), y_k) − β H(π(·|s_t))

In this objective, y_int and y_ext are the discounted returns for the two streams, and β controls exploration.[C5]

Relationship to the Semantic-Aware Basic Block Encoder

The Semantic-Aware Basic Block Encoder supplies the intrinsic reward used by the Basic Block Agent. It quantifies the novelty of a generated basic block directly in an ISA semantic space without RTL simulation, then drives an online cluster-distance novelty estimator whose output is R_int for the Basic Block Agent.[C7] Because the encoder is pre-trained on RISC-V assembly and is DUT-agnostic, this novelty feedback can be computed immediately after a basic block is generated rather than only after a full program has been simulated on the hardware-under-test.[C7]

LINKED ENTITIES

3 links
HiFuzz USES
Proximal Policy Optimization USES
Hierarchical Reinforcement Learning PART_OF

CITATIONS

12 sources
12 citations
[1] The Basic Block Agent is the low-level micro-step policy in HiFuzz's two-level hierarchical reinforcement-learning architecture, deciding instructions inside each basic block while the Program Agent selects global structure. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[2] Given the global context set by the Program Agent, the Basic Block Agent determines the mix of instruction categories within a specific basic block and decides when a basic block should terminate. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[3] For each basic block, HiFuzz represents the local generation problem as a BB Level Config (target instruction-category mix plus termination mode), and a constrained generator instantiates concrete instructions while enforcing operand, privilege, address, and jump-target constraints. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[4] The Basic Block Agent outputs compact category-level distribution parameters and a BB-termination signal rather than every concrete instruction, avoiding an impractically large action space. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[5] HiFuzz trains the Basic Block Agent with Proximal Policy Optimization using the clipped-surrogate objective L^CLIP, providing stable micro-step updates. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[6] The PPO implementation uses a multi-head Actor-Critic with separate intrinsic and extrinsic value heads, with coefficients α_int=1, α_ext=2 and extrinsic-baseline diminishing factor γ=0.75. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[7] The intrinsic reward R_int = min_k (1 − cos(E(bb), C_k)) is computed as cluster-distance novelty over frozen BB-Encoder embeddings. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[8] The extrinsic reward R_ext = (Δcov − baseline)/baseline with baseline = mean_recent_rewards * γ provides a coverage-derived learning signal normalized against a dynamic baseline. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[9] The Basic Block Agent uses a dual-advantage actor loss L_actor = α_int A_int + α_ext A_ext combined with per-head critic MSE losses and an entropy bonus in the total objective. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[10] The Semantic-Aware Basic Block Encoder consists of a structured RISC-V tokenizer, a Bi-LSTM backbone, and a two-stage training pipeline (Masked Language Modeling pre-training followed by supervised BB-Sim fine-tuning), and is DUT-agnostic across Rocket, BOOM, and CVA6. HiFuzz: Hierarchical Reinforcement Learning for Semantic-Aware and Adaptive CPU Fuzzing
[11] Proximal Policy Optimization was introduced by Schulman, Wolski, Dhariwal, Radford, and Klimov. Proximal Policy Optimization Algorithms
[12] The two-level Program Agent / Basic Block Agent decomposition is justified by the options framework and semi-MDP formalization of hierarchical reinforcement learning. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning

VERSION HISTORY

v2 · 8/19/2026 · minimax/minimax-m3 (current)
v1 · 7/10/2026 · gpt-5.5