Semantic Mutation Strategy in Grey-Box Fuzzing
https://doi.org/10.15514/ISPRAS-2025-37(2)-7
Abstract
With the advancement of modern information technology, dynamic analysis is becoming an essential part of software development. Fuzz testing is one of the most efficient and widely used techniques in this field. The core idea behind this approach is to input a large amount of random data into the program under the test. Mutation-based fuzzing tools generate test data by applying modifications (mutations) to successful variants that have already been identified, thus increasing the number of detected behaviors and code coverage. A common mutation strategy is to randomly select a mutation operator with a predefined probability.
This paper proposes a method to improve the effectiveness of mutation fuzzing through an adaptive mutation selection strategy. This approach was tested on commonly used Java packages and showed a statistically significant improvement in the number of errors detected and the diversity of program behaviors (execution traces).
About the Authors
Grigoriy Romanovich RAYKIN
ITMO University
Russian Federation
Russian Federation
Postgraduate student at the ITMO Institute of Computer Science. Research interests: static and dynamic software analysis, fuzzing, formal software specification.
Maksim Sergeevich PELEVIN
Saint Petersburg Electrotechnical University LETI
Russian Federation
Russian Federation
Master of the Faculty of Computer Science and Technology at ETU "LETI". Research interests: dynamic and static software analysis, fuzzing.
Vladimir Mikhailovich ITSYKSON
ITMO University
Russian Federation
Russian Federation
Cand. Sci. (Tech.), associate professor of the Institute of Applied Computer Science ITMO. Research interests: static and dynamic software analysis, software verification, methods for detecting defects in source code, methods for automating software testing.
References
1. M. Eberlein, Y. Noller, T. Vogel, and L. Grunske, «Evolutionary Grammar-Based Fuzzing», ArXiv, 2020. Accessed: https://api.semanticscholar.org/CorpusID:220961614.
2. R. Dutra, R. Gopinath, and A. Zeller, «FormatFuzzer: Effective Fuzzing of Binary File Formats», CoRR, 2021. Accessed: https://arxiv.org/abs/2109.11277.
3. X. Zhang et al., «A Survey of Protocol Fuzzing», ACM Comput. Surv., v. 57, No. 2, Oct. 2024, doi:10.1145/3696788.
4. H. Han, D. Oh, and S. K. Cha, «CodeAlchemist: Semantics-Aware Code Generation to Find Vulnerabilities in JavaScript Engines», Proceedings 2019 Network and Distributed System Security Symposium, 2019. Accessed: https://api.semanticscholar.org/CorpusID:142503428.
5. V. J. Manès et al., «The Art, Science, and Engineering of Fuzzing: A Survey», IEEE Transactions on Software Engineering, v. 47, No. 11, pp. 2312–2331, 2021, doi: 10.1109/TSE.2019.2946563.
6. M. Eberlein, Y. Noller, T. Vogel, and L. Grunske, «Evolutionary Grammar-Based Fuzzing». 2020 г.
7. Н. Ерохина, «Метод мутации сложноструктурированных входных данных при фаззинг-тестировании JavaScript интерпретаторов», Труды Института системного программирования РАН, т. 35, вып. 5, сс. 55–66, 2024, doi: 10.15514/ISPRAS-2022-35(5)-4.
8. A. Slowik, and H. Kwasnicka, «Evolutionary algorithms and their applications to engineering problems», Neural Computing and Applications, v. 32, No. 16, pp. 12363–12379, Mar. 2020, doi: 10.1007/s00521-020-04832-8.
9. C. Lyu et al., «MOPT: Optimized Mutation Scheduling for Fuzzers», в 28th USENIX Security Symposium (USENIX Security 19), Santa Clara, CA: USENIX Association, Aug. 2019, pp. 1949–1966. Accessed: https://www.usenix.org/conference/usenixsecurity19/presentation/lyu.
10. T. D. Nguyen, L. H. Pham, and J. Sun, «Fuzzing with Quantitative and Adaptive Hot-Bytes Identification». Доступно на: https://arxiv.org/abs/2307.02289.
11. L. Binosi, L. Rullo, M. Polino, M. Carminati, and S. Zanero, «Rainfuzz: Reinforcement-Learning Driven Heat-Maps for Boosting Coverage-Guided Fuzzing», в International Conference on Pattern Recognition Applications and Methods, 2023. Доступно на: https://api.semanticscholar.org/CorpusID:257361890.
12. C. Chen, V. Gohil, R. Kande, A.-R. Sadeghi, and J. Rajendran, «PSOFuzz: Fuzzing Processors with Particle Swarm Optimization». Accessed: https://arxiv.org/abs/2307.14480.
13. P. Jauernig, D. Jakobović, S. Picek, E. Stapf, and A. Sadeghi, «DARWIN: Survival of the Fittest Fuzzing Mutators», Jan. 2023, doi: 10.14722/ndss.2023.23159.
14. K. Böttinger, P. Godefroid, and R. Singh, «Deep Reinforcement Fuzzing», CoRR, 2018. Accessed: http://arxiv.org/abs/1801.04589.
15. D. She, R. Krishna, L. Yan, S. Jana, and B. Ray, «MTFuzz: fuzzing with a multi-task neural network», в Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, в ESEC/FSE ’20. ACM, Nov. 2020. doi: 10.1145/3368089.3409723.
16. K. Gong, W. Yang, B. Cui, and C. Chen, «DRLFCfuzzer: fuzzing with Deep-Reinforcement-Learning under Format Constraints», in 2022 2nd International Conference on Electronic Information Engineering and Computer Technology (EIECT), Oct. 2022, pp. 374–380. doi: 10.1109/EIECT58010.2022.00080.
17. S. Li et al., «Deep Learning for Coverage-Guided Fuzzing: How Far are We?», IEEE Transactions on Dependable and Secure Computing, pp. 1–13, 2022, doi: 10.1109/TDSC.2022.3200525.
18. A. Slivkins, «Introduction to Multi-Armed Bandits», CoRR, 2019. Accessed: http://arxiv.org/abs/1904.07272.
19. V. Gohil, R. Kande, C. Chen, A.-R. Sadeghi, and J. Rajendran, «MABFuzz: Multi-Armed Bandit Algorithms for Fuzzing Processors». 2023.
20. T. Yue et al., «EcoFuzz: Adaptive Energy-Saving Greybox Fuzzing as a Variant of the Adversarial Multi-Armed Bandit», в 29th USENIX Security Symposium (USENIX Security 20), USENIX Association, Aug. 2020, pp. 2307-2324. Accessed: https://www.usenix.org/conference/usenixsecurity20/presentation/yue.
21. Z. Huang, X. Song, Y. Luo, J. Yang, and B. Cui, «Syzballer: Kernel Fuzzing Based on Basic Block Weight and Multi-armed Bandit», in 2022 IEEE 8th International Conference on Computer and Communications (ICCC), Dec. 2022, pp. 2364–2369. doi: 10.1109/ICCC56324.2022.10065711.
22. G. Zhang et al., «MobFuzz: Adaptive Multi-objective Optimization in Gray-box Fuzzing», в Proceedings 2022 Network and Distributed System Security Symposium, в NDSS 2022. Internet Society, 2022. doi: 10.14722/ndss.2022.24314.
23. M. Lee, S. Cha, и H. Oh, «Learning Seed-Adaptive Mutation Strategies for Greybox Fuzzing», в 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), 2023, pp. 384–396. doi: 10.1109/ICSE48619.2023.00043.
24. M. Böhme, and B. Falk, «Fuzzing: on the exponential cost of vulnerability discovery», 2020, pp. 713–724. doi:10.1145/3368089.3409729.
25. S. Karamcheti, G. Mann, and D. S. Rosenberg, «Adaptive Grey-Box Fuzz-Testing with Thompson Sampling», CoRR, 2018. Accessed: http://arxiv.org/abs/1808.08256.
26. N. Gupta, O.-C. Granmo, и A. Agrawala, «Thompson Sampling for Dynamic Multi-armed Bandits», Machine Learning and Applications, Fourth International Conference on, v. 1, pp. 484–489, 2011, doi: 10.1109/ICMLA.2011.144.
27. P. Auer et al., «Achieving Optimal Dynamic Regret for Non-stationary Bandits without Prior Information», в Proceedings of the Thirty-Second Conference on Learning Theory, A. Beygelzimer and D. Hsu, Ed., in Proceedings of Machine Learning Research, vol. 99. PMLR, 2019, pp. 159–163. Accessed https://proceedings.mlr.press/v99/auer19b.html.
28. M. Eceiza, J. L. Flores, and M. Iturbe, «Improving fuzzing assessment methods through the analysis of metrics and experimental conditions», Computers & Security, v. 124, p. 102946, 2023, doi: https://doi.org/10.1016/j.cose.2022.102946.
29. Y. Li et al., «UNIFUZZ: A Holistic and Pragmatic Metrics-Driven Platform for Evaluating Fuzzers», в 30th USENIX Security Symposium (USENIX Security 21), USENIX Association, Aug. 2021, pp. 2777–2794. Доступно на: https://www.usenix.org/conference/usenixsecurity21/presentation/li-yuwei.
30. D. Paaßen, S. Surminski, M. Rodler, and L. Davi, «My Fuzzer Beats Them All! Developing a Framework for Fair Evaluation and Comparison of Fuzzers», CoRR, 2021. Accessed: https://arxiv.org/abs/2108.07076.
31. J. Bundt, A. Fasano, B. Dolan-Gavitt, W. Robertson, and T. Leek, «Evaluating Synthetic Bugs», в Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security, в ASIA CCS '21. Virtual Event, Hong Kong: Association for Computing Machinery, 2021, pp. 716–730. doi: 10.1145/3433210.3453096.
32. Arcuri and L. Briand, «A Hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering», Software Testing, Verification and Reliability, v. 24, No. 3, pp. 219–250, 2014, doi: https://doi.org/10.1002/stvr.1486.
33. A. Vargha and H. Delaney, «A Critique and Improvement of the "CL" Common Language Effect Size Statistics of McGraw and Wong», Journal of Educational and Behavioral Statistics – J EDUC BEHAV STAT, v. 25, No. 2, pp. 101-132, 2000, doi: 10.2307/1165329.
Review
For citations:
RAYKIN G.R., PELEVIN M.S., ITSYKSON V.M. Semantic Mutation Strategy in Grey-Box Fuzzing. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(2):97-114. (In Russ.) https://doi.org/10.15514/ISPRAS-2025-37(2)-7
Email this article 