Pusher: an augmented fuzzer based on the connection between input and comparison operand

Abstract

Coverage based fuzzing is a widespread vulnerability detection technique, and it has exposed many bugs in many real-world programs. However, its attention is to eliminate the testing on the repeated paths, yet it still employs random mutation to generate inputs, which is blind to penetrate complex comparisons in the program. As a result, the testing coverage is limited. Despite some solution proposals are presented, this problem is still partially solved. This paper argues that random mutation is mainly limited by two challenges, the sizable search spaceand the lack of a useful feedback to direct the search. Then we present an augmented fuzzing technique by addressing these two challenges. First of all, we point out a black relationship between input contents and comparison operands, which is dubbed connection. Second, we present a novel method to collect the comparison operands during execution, which is leveraged to infer the connections. Based on the connections, the fuzzer can learn about which input byte affects on which comparison instruction to establish a smaller search space. Third, the connection provides a useful feedback to direct the search. We resort to a modern meta-heuristic algorithm to satisfy this searching requirement. We developed a prototype \text{Pusher} and evaluated its performance on several benchmarks and four real-world programs. The experimental results demonstrate that \text{Pusher} works better than some other state-of-the-art fuzzers on bug detection, and can achieve a higher testing coverage. Moreover, we take a detailed statistic about the execution overhead in Pusher, and the results indicate that the execution overhead introduced by our approach is within an acceptable scope.

Graphical abstract

Keywords

software safety / software testing / information security / vulnerability / searching

References

[1] Miller B P , Fredriksen L , So B . An empirical study of the reliability of UNIX utilities. Communications of the ACM, 1990, 33( 12): 32– 44

[2] Liang H , Pei X , Jia X , Shen W , Zhang J . Fuzzing: state of the art. IEEE Transactions on Reliability, 2018, 67( 3): 1199– 1218

[3] Serebryany K. Continuous fuzzing with libfuzzer and addresssanitizer. In: Proceedings of IEEE Cybersecurity Development. 2016, 157– 157

[4] Gan S, Zhang C, Qin X, Tu X, Li K, Pei Z, Chen Z. CollAFL: path sensitive fuzzing. In: Proceedings of IEEE Symposium on Security and Privacy. 2018, 679−696

[5] Demoura L, Bjørner N. Z3: An efficient SMT solver. In: Proceedings of Tools and Algorithms for the Construction and Analysis of Systems. 2008, 337– 340

[6] Stephens N, Grosen J, Salls C, Dutcher A, Wang R, Corbetta J, Shoshitaishvili Y, Kruegel C, Vigna G. Driller: augmenting fuzzing through selective symbolic execution. In: Proceedings of Network and Distributed System Security Symposium. 2016

[7] Zhao L, Duan Y, Yin H, Xuan J. Send hardest problems my way: probabilistic path prioritization for hybrid fuzzing. In: Proceedings 2019 Network and Distributed System Security Symposium. 2019

[8] Pak B S. Hybrid fuzz testing: discovering software bugs via fuzzing and symbolic execution. PhD thesis, Carnegie Mellon University Pittsburgh, PA, 2012

[9] Baldoni R , Coppa E , Doelia D C , Demetrescu C , Finocchi I . A survey of symbolic execution techniques. Journal of ACM Computer Survey, 2018, 51( 3): 1– 39

[10] Peng H, Shoshitaishvili Y, Payer M. T-Fuzz: fuzzing by program transformation. In: Proceedings of IEEE Symposium on Security and Privacy. 2018, 697– 710

[11] Newsome J, Song D X. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In: Proceedings of the Network and Distributed System Security Symposium. 2005

[12] Rawat S, Jain V, Kumar A, Cojocar L, Giuffrida C, Bos H. VUzzer: application-aware evolutionary fuzzing. In: Proceedings of Network and Distributed System Security Symposium. 2017

[13] Dowser: A guided fuzzer to find buffer overflow vulnerabilities. In: Proceedings of the USENIX Security Symposium

[14] Chen P, Chen H. Angora: efficient fuzzing by principled search. In: Proceedings of IEEE Symposium on Security and Privacy. 2018, 711– 725

[15] Li Y, Chen B, Chandramohan M, Lin S W, Liu Y, Tiu A. Steelix: program-state based binary fuzzing. In: Proceedings of the Joint Meeting on Foundations of Software Engineering. 2017, 627– 637

[16] Ye J , Zhang B , Li R , Feng C , Tang C . Program state sensitive parallel fuzzing for real world software. IEEE Access, 2019, 7 : 42557– 42564

[17] Böhme M, Pham V T, Roychoudhury A. Coveragebased greybox fuzzing As Markov chain. In: Proceedings of ACM SIGSAC Conference on Computer and Communications Security. 2016, 1032−1043

[18] Lemieux C, Sen K. FairFuzz: a targeted mutation strategy for increasing greybox fuzz testing coverage. In: Proceedings of ACM/IEEE International Conference on Automated Software Engineering. 2018, 475– 485

[19] Dave M, Agrawal R. Search based techniques and mutation analysis in automatic test case generation: a survey. In: Proceedings of IEEE International Advance Computing Conference. 2015, 795– 799

[20] Harman M, Jia Y, Zhang Y. Achievements, open problems and challenges for search based software testing. In: Proceedings of IEEE International Conference on Software Testing, Verification and Validation. 2015, 1– 12

[21] Fraser G, Arcuri A. EvoSuite: automatic test suite generation for object-oriented software. In: Proceedings of ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering. 2011, 416– 419

[22] Rowe J E. Genetic algorithm theory. In: Proceedings of Conference Companion on Genetic and Evolutionary Computation. 2007, 3585

[23] Dolan-Gavitt B, Hulin P, Kirda E, Leek T, Mambretti A, Robertson W, Ulrich F, Whelan R. LAVA: large-scale automated vulnerability addition. In: Proceedings of IEEE Symposium on Security and Privacy. 2016, 110–121

[24] Lattner C, Adve V. LLVM: a compilation framework for lifelong program analysis & transformation. In: Proceedings of IEEE International Symposium on Code Generation and Optimization. 2004, 75– 86

[25] Liang J, Jiang Y, Chen Y, Wang M, Zhou C, Sun J. PAFL: extend fuzzing optimizations of single mode to industrial parallel mode. In: Proceedings of ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2018, 809– 814

[26] Serebryany K, Bruening D, Potapenko A, Vyukov D. AddressSanitizer: a fast address sanity checker. In: Proceedings of USENIX Annual Technical Conference. 2012, 309– 318

[27] Security M. fuzzdata: fuzzing resources for feeding various fuzzers with input. Mozilla Security, December 2017

[28] Aschermann C, Schumilo S, Blazytko T, Gawlik R, Holz T. REDQUEEN: fuzzing with input-to-state correspondence. In: Proceedings of Annual Network and Distributed System Security Symposium. 2019

[29] Böttinger K, Eckert C. Deepfuzz: triggering vulnerabilities deeply hidden in binaries. In: Proceedings of International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment. 2016, 25– 34

[30] Wang M, Liang J, Chen Y, Jiang Y, Jiao X, Liu H, Zhao X, Sun J. Safl: increasing and accelerating testing coverage with symbolic execution and guided fuzzing. In: Proceedings of International Conference on Software Engineering: Companion Proceeedings. 2018

[31] Cho M, Kim S, Kwon T. Intriguer: field-level constraint solving for hybrid fuzzing. In: Proceedings of ACM SIGSAC Conference on Computer and Communications Security. 2019, 515– 530

[32] Gong W, Zhang G, Zhou X. Learn to accelerate identifying new test cases in fuzzing. In: Proceeding of Security, Privacy, and Anonymity in Computation, Communication, and Storage. 2017, 298– 307

[33] Wang Y , Wu Z , Wei Q , Wang Q . Neufuzz: efficient fuzzing with deep neural network. IEEE Access, 2019, 7 : 36340– 36352

[34] She D, Pei K, Epstein D, Yang J, Ray B, Jana S. NEUZZ: efficient fuzzing with neural program smoothing. In: Proceedings of IEEE Symposium on Security and Privacy. 2019, 803– 817

[35] Wang T, Wei T, Gu G, Zou W. Taintscope: a checksumaware directed fuzzing tool for automatic software vulnerability detection. In: Proceedings of IEEE Symposium on Security and Privacy. 2010, 497– 512

[36] Liu X , Wei Q , Wang Q , Zhao Z , Yin Z . Cafa: a checksum-aware fuzzing assistant tool for coverage improvement. Journal of Security and Communication Networks, 2018, 2018 : 1– 13

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 61702540) and Hunan Provincial Natural Science Foundation of China (2018jj3615).

RIGHTS & PERMISSIONS

2022 Higher Education Press