Azuma-Hoeffding Inequality
ConceptA 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.
First seen 6/20/2026
Last seen 6/20/2026
Evidence 1 chunks
Wiki v1
WIKI
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
NEIGHBORHOOD
No graph connections found for this entity yet. It may appear in future ingestion runs.
explore full graph →RELATIONSHIPS
1 connectionsThe paper uses the Azuma-Hoeffding inequality in its theoretical analysis.
CITATIONS
5 sources5 citations — click to expand
[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