Evaluating Feedback-Driven Black-Box Processes via Stochastic Modeling and Simulation

Mengfan Xu, Zirui Liu, Juan Zhai, Shiqing Ma, Barry NelsonarXiv 2026 · arXiv

In the worlds of software engineering and machine learning, we often rely on "feedback-driven black-box processes." Whether it’s a fuzzer trying to crash a program or an algorithm tuning hyperparameters, these systems generate inputs, observe outputs, and use that feedback to decide what to do next.

Despite their ubiquity, evaluating these processes is notoriously messy. In software fuzzing, for instance, researchers often argue over whether "code coverage" or "unique bug counts" is the better metric. These metrics are often ad-hoc, sensitive to randomness, and lack a theoretical foundation. A new paper from researchers at UMass Amherst and Northwestern University aims to fix this by introducing a rigorous stochastic framework that treats these processes as Markov chains.

TL;DR

The authors propose a unified stochastic framework to model and evaluate feedback-driven black-box processes (like fuzzing) using Markov chains and spectral theory. By moving beyond ad-hoc metrics to principled measures like the "bug detection rate," they provide provable guarantees for fuzzer evaluation and a scientific basis for determining how long a test should actually run.

What Problem Does This Paper Address?

The core challenge is the "black-box" nature of these systems. We often don't know the internal state of the program being tested or the exact logic of the heuristic policy (the fuzzer) driving the inputs. This leads to evaluation "debates" where different metrics yield inconsistent conclusions.

For example, in fuzzing, "unique bug counts" are history-dependent; once a bug is found, it's no longer "unique," meaning the discovery rate eventually drops to zero even if the fuzzer is still performing well. This makes it a poor metric for long-term asymptotic behavior. Furthermore, there is no principled way to decide if a 24-hour evaluation is sufficient or if the results are just a fluke of randomness.

Methods

The researchers model the interaction between a policy (e.g., a fuzzer) and a system (e.g., a target program) as a discrete Markov chain.

Figure 1: The workflow of a fuzzing process.

Key components of their approach include:

  • Stochastic Modeling: They represent the fuzzer's mutation strategy as a transition matrix. The "quality" of a fuzzer is then tied to the spectral properties of this matrix—specifically the spectral gap (or its inverse, the relaxation time $\delta_R$).
  • New Metrics: They introduce the bug detection rate ($P_R$), defined as the asymptotic fraction of executions that trigger a bug. Unlike unique bug counts, this provides a stable target for theoretical analysis.
  • Monte Carlo Simulation: Instead of using a simplified "simulator," they use actual repeated executions of the real system to collect data, ensuring no "fidelity gap" between theory and practice.
  • Evaluation Scenarios: The paper provides different evaluation procedures depending on what is known about the system, ranging from cases where the spectral gap is known to "estimation-free" scenarios where only outputs are observable.
A summary of evaluation strategies based on the availability of the spectral parameter $\delta_R$.

Datasets

The authors conducted an massive empirical study involving over 233,000 CPU hours:

  • Fuzzing: 9 representative fuzzers (including AFL, AFL++, and Honggfuzz) tested on 18 benchmarks from FuzzBench and the Magma ground-truth benchmark.
  • Non-Fuzzing Domains: To prove generality, they applied the framework to:
  • Random walks on various graph structures.
  • Adversarial input search for image classifiers (CIFAR-10).
  • Adversarial search for vision-language models (CLIP).
  • Mutation-based prompt search for Large Language Models (Smollm-360M).

Key Insights and Ideas

  • The Spectral Gap is the "Speed Limit": The most important finding is that a fuzzer's performance is fundamentally governed by the spectral gap of its transition matrix. A smaller relaxation time ($\delta_R$) leads to faster convergence to the true bug detection rate.
  • Coverage is a Flawed Proxy: The evaluation shows that code coverage often plateaus early, while bug-related metrics continue to evolve. This suggests that coverage-based metrics are less aligned with actual bug discovery than previously thought.
  • Principled Duration ($T$): The framework allows users to calculate the minimum time $T$ required to reach a specific confidence level in the evaluation, moving away from "fixed-duration" heuristics like the standard 24-hour rule.
  • Proxy-based Evaluation: In practical settings where the true bug rate is unknown, the authors show that the union of all bugs found by all fuzzers in a trial serves as a mathematically sound proxy for ranking.

Key Results

The empirical results strongly validate the Markov chain model. In the Magma benchmark (which has known ground-truth bugs), the proposed metrics correctly ranked the fuzzers, and the error bars remained tight across trials.

Figure 2: Panels (a),(b) show bug ratio; (c),(d) bug counts; (e),(f) code coverage; (g),(h) convergence across time segments; (i),(j) DR(T) and ϵ; and (k),(l) time sufficiency on ffmpeg and harfbuzz.

In the non-fuzzing case studies, the theory held up perfectly: policies designed to have the smallest relaxation time (like uniform random jumps) consistently achieved the lowest deviation from the target event rate, confirming that the spectral gap is a universal driver of performance in these black-box processes.

Limitations and Future Work

  • Ergodicity Assumption: The theoretical guarantees rely on the assumption that the process is "ergodic"—meaning the fuzzer can eventually reach any part of the input space. If a fuzzer gets permanently "stuck" in a specific region, the current bounds may not apply.
  • State Observability: While the framework handles hidden states, estimating the spectral gap becomes significantly harder if the internal states of a "stateful" fuzzer are completely opaque.
  • Multi-objective Evaluation: The authors suggest that future work could integrate their "bug detection rate" with "unique bug discovery" into a more complex multi-objective optimization framework.

By grounding empirical testing in the language of Markov chains, this work provides a long-overdue "ruler" for measuring the effectiveness of the tools we use to secure our software.

Summary updated

Abstract

We study feedback-driven black-box processes across software engineering and machine learning. These processes are inherently sequential: policies generate inputs, observe outputs/feedback from systems, and use the feedback to guide the design of subsequent inputs. While many policies are developed under structural assumptions on the underlying systems, many real-world systems operate without such knowledge, necessitating black-box policies that lack a unified evaluation framework. We introduce a stochastic framework that models and evaluates such policies using Markov chains and simulation, thereby connecting empirical practice with theory. We instantiate the framework in mutation-based fuzzing (widely used for discovering software bugs via sequential input mutation), by a novel Markov chain model of fuzzing whose transitions are governed by the mutation strategy and whose feedback is given by program execution. We develop a rigorous evaluation paradigm with new performance measures, sound estimators, and evaluation procedures with provable guarantees. Guided by the theory, we evaluate 9 fuzzers on 18 widely used fuzzing benchmarks and conduct case studies in 4 non-fuzzing domains. These results show that the framework provides a principled basis for evaluation while connecting to practice, with implications beyond fuzzing.
BibTeX
@misc{xu2026evaluating,
  author = {Mengfan Xu and Zirui Liu and Juan Zhai and Shiqing Ma and Barry Nelson},
  title = {{Evaluating Feedback-Driven Black-Box Processes via Stochastic Modeling and Simulation}},
  year = {2026},
  eprint = {2611.18477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18477},
}
Figure