Skip to content
STIMSMITH

Azuma-Hoeffding Inequality

Concept WIKI v1 · 6/20/2026

A concentration inequality for martingales with bounded differences. In the FuSS framework, it is applied to a Doob martingale sequence derived from fuzzing iterations to bound the probability that the total number of successful discoveries deviates below its expected value, yielding a theoretical iteration lower bound.

Azuma-Hoeffding Inequality

The Azuma-Hoeffding inequality is a concentration-of-measure result that provides a tail bound on the deviation of a martingale from its expected value when the martingale has bounded successive differences. It generalizes the classical Hoeffding bound to the martingale setting.

Application in the FuSS Framework

In the paper FuSS: Coverage-Directed Hardware Fuzzing with Selective Symbolic Execution (ACM Transactions on Embedded Computing Systems, 2025), the Azuma-Hoeffding inequality (referenced as citation [7]) is used to derive a theoretical runtime bound for coverage-directed hardware fuzzing.

Setup

The analysis models fuzzing with a feedback loop as a stochastic process:

  • Let (X) be the total number of successful discoveries (reaching new paths) after (T) iterations.
  • Let (Z = (Z_1, Z_2, \ldots, Z_T)) be the sequence of random variables representing random choices during fuzzing iterations.
  • Let (\mathcal{F}_t) be the sigma-algebra generated by (Z_1, \ldots, Z_t), representing the information available up to iteration (t).
  • Let ((M_t)_{t=0}^{T} = \mathbb{E}[X \mid \mathcal{F}_t]) be the Doob martingale sequence.

By the tower property of conditional expectation:

$$\mathbb{E}[M_{t+1} \mid \mathcal{F}t] = \mathbb{E}[\mathbb{E}[X \mid \mathcal{F}{t+1}] \mid \mathcal{F}_t] = \mathbb{E}[X \mid \mathcal{F}_t] = M_t$$

so (M_t) is a martingale by construction.

Bounded-Difference Condition

Because discovering a new state or bug in any iteration can change the expected total number of successes by at most 1, the sequence satisfies:

$$|M_t - M_{t-1}| \leq 1$$

Resulting Bound

Applying the Azuma-Hoeffding inequality with the parameters above yields:

$$\Pr[X \leq (1 - \delta),\mathbb{E}[X]] \leq e^{-\delta^2 \mathbb{E}[X]^2 / (2T)}$$

Substituting (\mathbb{E}[X] = T P_i), where (P_i) is the average activation probability per iteration for a given fuzzing strategy, and solving for (T) gives:

$$T \geq \frac{\delta}{2 P_i^2} \cdot 2 \ln\left(\frac{1}{\epsilon}\right)$$

Interpretation

Because (P_{f+s} > P_{f+p} > P_f) (where (P_f) is the success probability of traditional fuzzing, (P_{f+p}) is fuzzing with property checking, and (P_{f+s}) is FuSS with selective symbolic execution), the required number of iterations (T) decreases as the activation probability increases. This provides theoretical justification for integrating selective symbolic execution into fuzzing, predicting that it is most beneficial when the per-iteration success probability is higher.

LINKED ENTITIES

1 links
FuSS: Coverage-Directed Hardware Fuzzing with Selective Symbolic Execution USES

CITATIONS

5 sources
5 citations
[1] The Azuma-Hoeffding inequality is applied to a Doob martingale sequence with bounded differences |M_t - M_{t-1}| ≤ 1 to obtain a tail bound on successful fuzzing discoveries. FuSS: Coverage-Directed Hardware Fuzzing with Selective Symbolic Execution
[2] Applying the Azuma-Hoeffding inequality yields Pr[X ≤ (1−δ)E[X]] ≤ exp(−δ² E[X]² / (2T)). FuSS: Coverage-Directed Hardware Fuzzing with Selective Symbolic Execution
[3] Substituting E[X] = T·P_i and solving for T gives the iteration lower bound T ≥ (δ / (2 P_i²)) · 2 ln(1/ε). FuSS: Coverage-Directed Hardware Fuzzing with Selective Symbolic Execution
[4] Because P_{f+s} > P_{f+p} > P_f, the required number of iterations T decreases as per-iteration success probability increases, theoretically justifying selective symbolic execution. FuSS: Coverage-Directed Hardware Fuzzing with Selective Symbolic Execution
[5] The Azuma-Hoeffding inequality is referenced as citation [7] in the FuSS paper. FuSS: Coverage-Directed Hardware Fuzzing with Selective Symbolic Execution