Dependency Chain Length

Concept

A program metric used in CPU fuzzing that measures the depth of the dependency chain between fuzzing instructions. In the Cascade paper (SEC'24), it is computed per register and per instruction, and is shown to be substantially longer for Cascade (average 9.5, median 4.0, up to 270) than for DifuzzRTL (average 2.1, median 2.0). The metric matters because longer chains entangle data flow with control flow, force non-termination when a bug is triggered, and exercise corner cases in CPU designs.

First seen 6/14/2026

Last seen 6/14/2026

Evidence 3 chunks

Wiki v1

WIKI

Dependency Chain Length

Definition

Dependency Chain Length is a program-level metric introduced in the Cascade CPU-fuzzing paper (USENIX Security 2024). It characterizes, for each fuzzing instruction in a generated program, how many other fuzzing instructions its inputs transitively depend on. It is used to quantify how entangled the data flow and control flow are inside a fuzzing program, and to argue that longer chains are beneficial for exercising deep corner cases in CPU designs ^[1].

READ FULL ARTICLE →

NEIGHBORHOOD

2 nodes · 1 edges

graph · Dependency Chain Length · depth=1

RELATIONSHIPS

1 connections

Cascade ← evaluates 100% 2e

Cascade analyzes dependency chain lengths in generated programs as a quality metric.

LINKED ENTITIES

1 links

Cascade EVALUATES Extracted graph relationship

CITATIONS

9 sources

9 citations — click to expand

[1] Dependency Chain Length is a program metric introduced in the Cascade paper that measures how many preceding fuzzing instructions each fuzzing instruction depends on. Cascade: CPU Fuzzing via Intricate Program Generation

[2] Each register starts with dependency number -1; the number resets on CSR reads or instructions taking only immediates, and an instruction's dependency number is the max of its source registers' numbers plus one. Cascade: CPU Fuzzing via Intricate Program Generation

[3] For Cascade, the average dependency-chain length is 9.5, the median is 4.0, and fuzzing instructions depended on up to 270 other fuzzing instructions (Figure 12). Cascade: CPU Fuzzing via Intricate Program Generation

[4] For DifuzzRTL, the average number of dependencies is 2.1 and the median is 2.0 (Figure 11). Cascade: CPU Fuzzing via Intricate Program Generation

[5] Long dependency chains entangle data flow with control flow to force non-termination when a bug is triggered, and they can exercise corner cases inside a CPU's design. Cascade: CPU Fuzzing via Intricate Program Generation

[6] DifuzzRTL produces programs with very few interdependencies and TheHuzz does not explicitly generate or favor programs with dependencies, so both yield shorter chains than Cascade. Cascade: CPU Fuzzing via Intricate Program Generation

[7] Cascade's chain lengths could be further increased by lowering the probabilities of picking dependency-resetting instructions such as CSR reads. Cascade: CPU Fuzzing via Intricate Program Generation

[8] In Figures 11 and 12, control-flow instructions are represented in orange. Cascade: CPU Fuzzing via Intricate Program Generation

[9] Dependency chain length is reported in Section 7.3 'Program metrics' alongside completion and prevalence metrics. Cascade: CPU Fuzzing via Intricate Program Generation