Effective Seed Scheduling for Directed Fuzzing with Function Call Sequence Complexity Estimation
Source abstract
Abstract
Directed grey-box fuzzers focus on testing specific target code. They have been utilized in various security applications, such as reproducing known crashes and identifying vulnerabilities resulting from incomplete patches. Distance-guided directed fuzzers calculate the distance to the target node for each node in a CFG or CG, which has always been the mainstream in this field. However, the distance can only reflect the relationship between the current node and the target node, and it does not consider the impact of the reaching sequence before the target node. To mitigate this problem, we analyzed the properties of the instrumented function’s call graph after selective instrumentation, and the complexity of reaching the target function sequence was estimated. Assisted by the sequence complexity, we proposed a two-stage function call sequence-based seed-scheduling strategy. The first stage is to select seeds with a higher probability of generating test cases that reach the target function. The second stage is to select seeds that can generate test cases that meet the conditions for triggering the vulnerability as much as possible. We implemented our approach in SEZZ based on SelectFuzz and compare it with related works. We found that SEZZ outperformed AFLGo, Beacon, WindRanger, and SelectFuzz by achieving an average improvement of 13.7×, 1.50×, 9.78×, and 2.04× faster on vulnerability exposure, respectively. Moreover, SEZZ triggered three more vulnerabilities than the other compared tools.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Software Testing and Debugging Techniques · Advanced Malware Detection Techniques · Software Reliability and Analysis Research
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Cyber Science and Engineering, Sichuan University, Chengdu 610065, China
Funding
National Key R&D Program of China
References (40)
Show source-provided references
1. Fuzzing: State of the art10.1109/TR.2018.2834476 ↗
2. Fuzzing: A survey for roadmap10.1145/3512345 ↗
3. Fuzzing: Progress, Challenges, and Perspectives
4. DDIML: Explainable detection model for drive-by-download attacks
5. bjCnet: A contrastive learning-based framework for software defect prediction10.1016/j.cose.2024.104024 ↗
6. (2025, June 10). American Fuzzy Lop. Available online: https://lcamtuf.coredump.cx/afl/.
7. Chen, H., Xue, Y., Li, Y., Chen, B., Xie, X., Wu, X., and Liu, Y. (2018, January 15–19). Hawkeye: Towards a desired directed grey-box fuzzer. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada.10.1145/3243734.3243849 ↗
8. Huang, H., Guo, Y., Shi, Q., Yao, P., Wu, R., and Zhang, C. (2022, January 23–25). Beacon: Directed grey-box fuzzing with provable path pruning. Proceedings of the 2022 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP46214.2022.9833751 ↗
9. Zhu, X., and Böhme, M. (2021, January 15–19). Regression greybox fuzzing. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual.10.1145/3460120.3484596 ↗
10. Du, Z., Li, Y., Liu, Y., and Mao, B. (2022, January 21–29). Windranger: A directed greybox fuzzer driven by deviation basic blocks. Proceedings of the 44th International Conference on Software Engineering, Pittsburgh, PA, USA.10.1145/3510003.3510197 ↗
11. Search-based crash reproduction and its impact on debugging10.1109/TSE.2018.2877664 ↗
12. You, W., Zong, P., Chen, K., Wang, X., Liao, X., Bian, P., and Liang, B. (November, January 30). Semfuzz: Semantics-based automatic generation of proof-of-concept exploits. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA.10.1145/3133956.3134085 ↗
13. Zheng, Y., Song, Z., Sun, Y., Cheng, K., and Sun, L. (2019, January 29–31). An Efficient Greybox Fuzzing Scheme for Linux-based IoT Programs Through Binary Static Analysis. Proceedings of the 2019 IEEE 38th International Performance Computing and Communications Conference (IPCCC), London, UK.10.1109/IPCCC47392.2019.8958740 ↗
14. Dong, F., Dong, C., Zhang, Y., and Lin, T. (2015, January 23–25). Binary-oriented Hybrid Fuzz Testing. Proceedings of the 2015 6th IEEE International Conference on Software Engineering and Service Science (ICSESS 2015), Beijing, China.
15. Wang, P., Zhou, X., Yue, T., Lin, P., Liu, Y., and Lu, K. (2024). The progress, challenges, and perspectives of directed greybox fuzzing. Softw. Test. Verif. Reliab., 34.10.1002/stvr.1869 ↗
16. Böhme, M., Pham, V.T., Nguyen, M.D., and Roychoudhury, A. (November, January 30). Directed greybox fuzzing. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA.10.1145/3133956.3134020 ↗
17. Chen, P., and Chen, H. (2018, January 21–23). Angora: Efficient fuzzing by principled search. Proceedings of the 2018 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP.2018.00046 ↗
18. Luo, C., Meng, W., and Li, P. (2023, January 22–24). Selectfuzz: Efficient directed fuzzing with selective path exploration. Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP46215.2023.10179296 ↗
19. Srivastava, P., Nagy, S., Hicks, M., Bianchi, A., and Payer, M. (2022, January 4–8). One fuzz doesn’t fit all: Optimizing directed fuzzing via target-tailored program state restriction. Proceedings of the 38th Annual Computer Security Applications Conference, Austin, TX, USA.10.1145/3564625.3564643 ↗
20. RDFuzz: Accelerating directed fuzzing with intertwined schedule and optimized mutation10.1155/2020/7698916 ↗
21. Nguyen, M.D., Bardin, S., Bonichon, R., Groz, R., and Lemerre, M. (2020, January 14–18). Binary-level directed fuzzing for {use-after-free} vulnerabilities. Proceedings of the 23rd International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2020), San Sebastian, Spain.
22. Österlund, S., Razavi, K., Bos, H., and Giuffrida, C. (2020, January 12–14). {ParmeSan}: Sanitizer-guided greybox fuzzing. Proceedings of the 29th USENIX Security Symposium (USENIX Security 20), Berkeley, CA, USA.
23. Lemieux, C., and Sen, K. (2018, January 3–7). Fairfuzz: A targeted mutation strategy for increasing greybox fuzz testing coverage. Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, Montpellier, France.10.1145/3238147.3238176 ↗
24. Aschermann, C., Schumilo, S., Blazytko, T., Gawlik, R., and Holz, T. (2019, January 24–27). REDQUEEN: Fuzzing with Input-to-State Correspondence. Proceedings of the NDSS, San Diego, CA, USA.10.14722/ndss.2019.23371 ↗
25. Liang, J., Wang, M., Zhou, C., Wu, Z., Jiang, Y., Liu, J., Liu, Z., and Sun, J. (2022, January 23–25). Pata: Fuzzing with path aware taint analysis. Proceedings of the 2022 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP46214.2022.9833594 ↗
26. Yun, I., Lee, S., Xu, M., Jang, Y., and Kim, T. (2018, January 15–17). {QSYM}: A practical concolic execution engine tailored for hybrid fuzzing. Proceedings of the 27th USENIX Security Symposium (USENIX Security 18), Baltimore, MD, USA.
27. Cho, M., Kim, S., and Kwon, T. (2019, January 11–15). Intriguer: Field-level constraint solving for hybrid fuzzing. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK.10.1145/3319535.3354249 ↗
28. Huang, H., Yao, P., Wu, R., Shi, Q., and Zhang, C. (2020, January 18–20). Pangolin: Incremental hybrid fuzzing with polyhedral path abstraction. Proceedings of the 2020 IEEE Symposium on Security and Privacy (SP), Virtual.10.1109/SP40000.2020.00063 ↗
29. Zong, P., Lv, T., Wang, D., Deng, Z., Liang, R., and Chen, K. (2020, January 12–14). {FuzzGuard}: Filtering out unreachable inputs in directed grey-box fuzzing through deep learning. Proceedings of the 29th USENIX Security Symposium (USENIX Security 20), Berkeley, CA, USA.
30. Cyclomatic complexity density and software maintenance productivity10.1109/32.106988 ↗
31. Lattner, C., and Adve, V. (2004, January 21–24). LLVM: A compilation framework for lifelong program analysis & transformation. Proceedings of the International Symposium on Code Generation and Optimization, Palo Alto, CA, USA.
32. Magma: A ground-truth fuzzing benchmark10.1145/3428334 ↗
33. A survey of symbolic execution techniques10.1145/3182657 ↗
34. Symbolic execution and program testing10.1145/360248.360252 ↗
35. Stephens, N., Grosen, J., Salls, C., Dutcher, A., Wang, R., Corbetta, J., Shoshitaishvili, Y., Kruegel, C., and Vigna, G. (2016, January 21–24). Driller: Augmenting fuzzing through selective symbolic execution. Proceedings of the NDSS, San Diego, CA, USA.10.14722/ndss.2016.23368 ↗
36. Jin, W., and Orso, A. (2012, January 2–9). Bugredux: Reproducing field failures for in-house debugging. Proceedings of the 2012 34th International Conference on Software Engineering (ICSE), Zurich, Switzerland.10.1109/ICSE.2012.6227168 ↗
37. Cadar, C., Dunbar, D., and Engler, D.R. (2008, January 8–10). Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. Proceedings of the OSDI, San Diego, CA, USA.
38. Jezuita, F. (2023, January 11–15). Improving AFLGo’s Directed Fuzzing by Considering Indirect Function Calls. Proceedings of the 2023 38th IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW), Luxembourg.10.1109/ASEW60602.2023.00024 ↗
39. Tan, X., Zhang, Y., Lu, J., Xiong, X., Liu, Z., and Yang, M. (2023, January 26–30). SyzDirect: Directed Greybox Fuzzing for Linux Kernel. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, Copenhagen, Denmark.10.1145/3576915.3623146 ↗
40. Xiang, Y., Zhang, X., Liu, P., Ji, S., Liang, H., Xu, J., and Wang, W. (2024, January 14–16). Critical Code Guided Directed Greybox Fuzzing for Commits. Proceedings of the 33rd USENIX Security Symposium (USENIX Security 24), Philadelphia, PA, USA.