Skip to content
STIMSMITH

cf-ambiguous instruction

Concept WIKI v1 · 7/2/2026

A cf-ambiguous instruction is a control-flow instruction in the Cascade CPU fuzzer whose operand value cannot be computed until late in program generation, forcing the instruction set simulator (ISS) to run at least once per such instruction unless mitigated.

cf-ambiguous instruction

In the Cascade CPU fuzzing framework, a cf-ambiguous instruction is a control-flow instruction whose required operand value is not known when the instruction is first selected during program generation. The canonical examples are indirect jumps such as jalr, which must be supplied with a specific target value val that Cascade intends to impose on the CPU under test. Because val is not yet determined, Cascade cannot simply pre-compute a static target operand; instead, it must take special steps to materialize val later, which has implications for instruction set simulator (ISS) pre-simulation and overall fuzzing throughput.

Why such instructions are problematic

If Cascade relies on a per-instruction ISS execution to keep the simulator's state consistent with the program being generated, then for every cf-ambiguous instruction the ISS cannot advance to the next basic block — and cannot correctly service the pending memory operation — without first being executed at least once with the real operand value. Treating each cf-ambiguous instruction this way becomes a critical performance bottleneck.

Construction under the dependency-preservation principle

Cascade applies the principle of dependency preservation: rather than constraining the randomized data flow, it makes the imposed target value val depend on a randomly chosen register rd whose value is already produced by the program’s data flow and is therefore unknown when the cf-ambiguous instruction is picked. To obtain val from the unknown rd, Cascade introduces:

  1. An offset register r_off, whose value is fixed at generation time so that, combined with rd, it produces val.
  2. An offset applier instruction (e.g., xor) that combines rd and r_off and writes the intended value val into an applied register r_app.
  3. Optionally, a third register may be used as r_app to maximize the degrees of freedom; rd and r_off are not required to be reused as the destination.

Branches are handled differently: because applied registers are a precious resource, Cascade uses ISS feedback to obtain the operand values and selects a suitable branch opcode (still or hopping) rather than the offset-applier scheme used for cf-ambiguous instructions.

Offset state machines

To make the construction well-formed, Cascade maintains a simple state machine per architectural integer register enforcing three conditions:

  1. r_app must be available when the cf-ambiguous instruction is picked.
  2. r_off must be ready before the offset applier instruction executes.
  3. rd must be available when the offset applier instruction executes.

Registers traverse free, gen, ready, and unrel states during the offset construction cycle, with transitions forming a specific instruction category in Cascade.

Mitigation: asymmetric ISA pre-simulation

To avoid the per-cf-ambiguous-instruction ISS execution cost, Cascade introduces asymmetric ISA pre-simulation. Instead of feeding the ISS the ultimate program the CPU under test will execute, Cascade provides an intermediate program satisfying three invariants:

  • (a) the values of all dependent registers (in the constructions of applied registers) are identical between the intermediate and ultimate programs,
  • (b) the programs' control flows are identical, and
  • (c) in the intermediate program, no applied register depends on the randomized data flow.

Concretely, the intermediate program differs from the ultimate program in three ways:

  1. The immediates imm1 and imm2 are chosen so that r_off is set directly to val (bypassing the unknown rd).
  2. The offset-applying instruction is replaced with an mv that copies r_off into r_app.
  3. Non-taken branches are transformed into NOPs, because their operand values are not yet known.

With these transformations, the intermediate program complies with the three invariants and the ISS only needs to be executed once for the whole program rather than once per cf-ambiguous instruction.

Intermediate register states

The offset construction scheme guarantees by design that at any point in the program, all free and applied registers have the same value in both the intermediate and the ultimate program. This invariant does not hold for registers in the gen, ready, and unrel states; therefore, those registers must never be used as the input of any instruction other than the next instruction in the offset construction cycle (steps (b) and (c) in Figure 4 of the source paper).

LINKED ENTITIES

1 links
Cascade USES

CITATIONS

8 sources
8 citations
[1] A cf-ambiguous instruction is exemplified by indirect jumps such as `jalr`, which require a specific operand value `val` that Cascade intends to impose. Cascade (USENIX Security 2024 preprint)
[2] Without mitigation, the ISS cannot proceed to the next basic block (or complete a correct memory operation) without running at least once per cf-ambiguous instruction, creating a critical performance bottleneck. Cascade (USENIX Security 2024 preprint)
[3] Following dependency preservation, Cascade makes `val` depend on a randomly picked dependent register `rd` whose value is unknown when the cf-ambiguous instruction is picked, and introduces an offset register `r_off` and an offset applier instruction (e.g., `xor`) whose output is the applied register `r_app` holding `val`. Cascade (USENIX Security 2024 preprint)
[4] Branches are handled via ISS feedback rather than the offset-applier scheme, because applied registers are a precious resource; Cascade selects a still or hopping branch opcode accordingly. Cascade (USENIX Security 2024 preprint)
[5] Cascade maintains a per-architectural-integer-register state machine ensuring (1) `r_app` is available when the cf-ambiguous instruction is picked, (2) `r_off` is ready before the offset applier instruction, and (3) `rd` is available when the offset applier instruction executes. Cascade (USENIX Security 2024 preprint)
[6] Cascade's asymmetric ISA pre-simulation feeds the ISS an intermediate program that (a) has identical dependent-register values, (b) has identical control flow, and (c) contains no applied register that depends on the randomized data flow, enabling a single ISS execution per program. Cascade (USENIX Security 2024 preprint)
[7] The intermediate program differs from the ultimate program in three ways: (1) immediates `imm1` and `imm2` set `r_off` directly to `val`, (2) the offset-applying instruction is substituted with an `mv` from `r_off` to `r_app`, and (3) non-taken branches are transformed into NOPs. Cascade (USENIX Security 2024 preprint)
[8] Free and applied registers hold identical values between the intermediate and ultimate programs at every program point, but registers in the `gen`, `ready`, and `unrel` states do not, so they must never be used as input to any instruction other than the next step of the offset construction cycle. Cascade (USENIX Security 2024 preprint)