Position-Adaptive Mutation Scheduling Strategy in Fuzzing

YANG Zhi; XU Hang; SANG Weiquan; SUN Haodong; JIN Shuyuan

doi:10.11999/JEIT240060

Volume 46 Issue 9

Sep. 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(9): 3797-3806

YANG Zhi, XU Hang, SANG Weiquan, SUN Haodong, JIN Shuyuan. Position-Adaptive Mutation Scheduling Strategy in Fuzzing[J]. Journal of Electronics & Information Technology, 2024, 46(9): 3797-3806. doi: 10.11999/JEIT240060

Citation:

YANG Zhi, XU Hang, SANG Weiquan, SUN Haodong, JIN Shuyuan. Position-Adaptive Mutation Scheduling Strategy in Fuzzing[J]. Journal of Electronics & Information Technology, 2024, 46(9): 3797-3806. doi: 10.11999/JEIT240060

Citation:

PDF( 4509 KB)

Position-Adaptive Mutation Scheduling Strategy in Fuzzing

doi: 10.11999/JEIT240060

1.
School of Cryptographic Engineering, Information Engineering University, Zhengzhou 450004, China
2.
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510275, China

Funds: The National Natural Science Foundation of China (62176265)

Received Date: 2024-01-26
Rev Recd Date: 2024-07-13

Available Online: 2024-08-02

Publish Date: 2024-09-26

Abstract

Abstract

The seed-adaptive mutation scheduling strategy is the latest technology in mutation-based fuzzing, which can adaptively adjust the probability distribution of the mutation operators according to the syntax and semantic characteristics of the seed. However, it has two problems: (1) it is unable to adaptively adjust the probability distribution according to the mutation position; (2) The Thompson Sampling algorithm used in the fuzzing scenario is easy to lead to the learned probability distribution close to the average distribution, which leads to the failure of the mutation scheduling strategy. Focusing on the above problems, a position-adaptive mutation scheduling strategy is proposed. This technology establishes the relationship between the mutation position and the mutation operators through a user-defined double-layer multi-armed bandit model, and uses the Upper Confidence Bound algorithm to select the mutation operator, so as to achieve position adaptation and avoid the problem of average distribution. The position-adaptive fuzzer Position-Adaptive Mutation Scheduling Strategy AFL (PAMSSAFL) is implemented based on American Fuzzy Lop (AFL). The comparison results show that the position-adaptive mutation scheduling strategy can improve the bug detection ability and coverage ability of the fuzzer.
- Vulnerability mining,
- Fuzzing,
- Mutation,
- Coverage

FullText(HTML)

References(17)

References

[1]	ZALEWSKI M. American Fuzzy Lop (AFL) fuzzer[EB/OL]. https://lcamtuf.coredump.cx/afl/, 2023.
[2]	Honggfuzz: A security oriented, feedback-driven, evolutionary, easy-to-use fuzzer[EB/OL]. https://github.com/google/honggfuzz, 2023.
[3]	LLWM. LibFuzzer—A library for coverage-guided fuzz testing[EB/OL]. http://llvm.org/docs/LibFuzzer.html, 2023.
[4]	LEE M, CHA S, and OH H. Learning seed-adaptive mutation strategies for greybox fuzzing[C]. 2023 IEEE/ACM 45th International Conference on Software Engineering, Melbourne, Australia, 2023: 384–396. doi: 10.1109/ICSE48619.2023.00043.
[5]	AGRAWAL S and GOYAL N. Analysis of thompson sampling for the multi-armed bandit problem[C]. The 25th Annual Conference on Learning Theory, Edinburgh, UK, 2012: 39.
[6]	AUER P, CESA-BIANCHI N, and FISCHER P. Finite-time analysis of the Multiarmed bandit problem[J]. Machine Learning, 2002, 47(2/3): 235–256. doi: 10.1023/A:1013689704352.
[7]	JAUERNIG P, JAKOBOVIC D, PICEK S, et al. DARWIN: Survival of the fittest fuzzing mutators[C]. The 30th Annual Network and Distributed System Security Symposium, San Diego, USA, 2023. doi: 10.14722/ndss.2023.23159.
[8]	LEMIEUX C and SEN K. FairFuzz: A targeted mutation strategy for increasing greybox fuzz testing coverage[C]. The 33rd IEEE/ACM International Conference on Automated Software Engineering, Montpellier, France, 2018: 475–485. doi: 10.1145/3238147.3238176.
[9]	SHE Dongdong, SHAH A, and JANA S. Effective seed scheduling for fuzzing with graph centrality analysis[C]. The 43rd IEEE Symposium on Security and Privacy, San Francisco, USA, 2022: 2194–2211. doi: 10.1109/SP46214.2022.9833761.
[10]	SAHA S, SARKER L, SHAFIUZZAMAN M, et al. Rare path guided fuzzing[C]. The 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis, Seattle, USA, 2023: 1295–1306. doi: 10.1145/3597926.3598136.
[11]	LÜ Chenyang, JI Shouling, ZHANG Chao, et al. MOPT: Optimized mutation scheduling for fuzzers[C]. The 28th USENIX Security Symposium, Santa Clara, USA, 2019: 1949–1966.
[12]	WU Mingyuan, JIANG Ling, XIANG Jiahong, et al. One fuzzing strategy to rule them all[C]. The 44th International Conference on Software Engineering, Pittsburgh, USA, 2022: 1634–1645. doi: 10.1145/3510003.3510174.
[13]	SUTTON R S and BARTO A G. Reinforcement Learning: An Introduction[M]. 2nd ed. Cambridge: The MIT Press, 2018: 31–47.
[14]	李明磊, 陆余良, 黄晖, 等. 模糊测试变异算子调度优化模型[J]. 小型微型计算机系统, 2021, 42(10): 2190–2195. doi: 10.3969/j.issn.1000-1220.2021.10.029. LI Minglei, LU Yuliang, HUANG Hui, et al. Fuzzy tester mutation operator scheduling optimization algorithm[J]. Journal of Chinese Computer Systems, 2021, 42(10): 2190–2195. doi: 10.3969/j.issn.1000-1220.2021.10.029.
[15]	FIORALDI A, MAIER D C, EIßFELDT H, et al. AFL++: Combining incremental steps of fuzzing research[C]. The 14th USENIX Conference on Offensive Technologies, Berkeley, USA, 2020: 10.
[16]	HAZIMEH A, HERRERA A, and PAYER M. Magma: A ground-truth fuzzing benchmark[J]. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2020, 4(3): 49. doi: 10.1145/3428334.
[17]	DOLAN-GAVITT B, HULIN P, KIRDA E, et al. LAVA: Large-scale automated vulnerability addition[C]. 2016 IEEE Symposium on Security and Privacy, San Jose, USA, 2016: 110–121. doi: 10.1109/SP.2016.15.