一句话：提出用极值理论估计差分模糊测试漏检风险，并通过提前停止提升测试效率。
差分模糊测试能自动发现涉及多执行规约的缺陷，但作为动态分析无法保证无缺陷：当一轮测试未发现缺陷或仅发现很小差异时，继续运行一步或多步后发现缺陷或更大差异的风险仍不明确。本文研究用极值理论（EVT）刻画这一风险。作者观察到差分模糊测试的随机过程近似于观测差异的最大值分布，因此可用 EVT 分析测试活动尾部，从而对漏检或低估缺陷的风险进行外推。实验在真实 Java 库上开展，用差分模糊测试寻找侧信道信息泄漏，探索 EVT 的可行性与最优超参数，并与 Markov 不等式、Chebyshev 不等式和 Bayes 因子等基线比较。EVT 外推在 14.3% 情况下优于基线，在 64.2% 情况下持平；启用 EVT 的差分模糊测试通过提前停止平均节省数千万次字节码执行。
Differential testing is a highly effective technique for automatically detecting software bugs and vulnerabilities when the specifications involve an analysis over multiple executions simultaneously. Differential fuzzing, in particular, operates as a guided randomized search, aiming to find (similar) inputs that lead to a maximum difference in software outputs or their behaviors. However, fuzzing, as a dynamic analysis, lacks any guarantees on the absence of bugs: from a differential fuzzing campaign that has observed no bugs (or a minimal difference), what is the risk of observing a bug (or a larger difference) if we run the fuzzer for one or more steps?This paper investigates the application of Extreme Value Theory (EVT) to address the risk of missing or underestimating bugs in differential fuzzing. The key observation is that differential fuzzing as a random process resembles the maximum distribution of observed differences. Hence, EVT, a branch of statistics dealing with extreme values, is an ideal framework to analyze the tail of the differential fuzzing campaign to contain the risk. We perform experiments on a set of real-world Java libraries and use differential fuzzing to find information leaks via side channels in these libraries. We first explore the feasibility of EVT for this task and the optimal hyperparameters for EVT distributions. We then compare EVT-based extrapolation against baseline statistical methods like Markov’s as well as Chebyshev’s inequalities, and the Bayes factor. EVT-based extrapolations outperform the baseline techniques in 14.3% of cases and tie with the baseline in 64.2% of cases. Finally, we evaluate the accuracy and performance gains of EVT-enabled differential fuzzing in real-world Java libraries, where we reported an average saving of tens of millions of bytecode executions by an early stop.
DOI 原文 ·
@inproceedings{paperbot9252,
title = {Risk Estimation in Differential Fuzzing via Extreme Value Theory},
author = {Rafael Baez and Alejandro Olivas and Nathan K Diamond and Marcelo Frias and Yannic Noller and Saeid Tizpaz-Niari},
booktitle = {ASE},
year = {2025},
doi = {10.1109/ase63991.2025.00036}
}