Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (5): 1212-1228.doi: 10.1007/s11390-021-1196-0

Special Issue: Software Systems

• Regular Paper • Previous Articles    

Vulnerable Region-Aware Greybox Fuzzing

Ling-Yun Situ1,2, Member, CCF, Zhi-Qiang Zuo1,*, Member, CCF, Le Guan3, Member, ACM, IEEE Lin-Zhang Wang1,*, Distinguished Member, CCF, Xuan-Dong Li1, Fellow, CCF Jin Shi2, Member, CCF, and Peng Liu4, Member, ACM, IEEE        

  1. 1 State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China;
    2 School of Information Management, Nanjing University, Nanjing 210023, China;
    3 Department of Computer Science, University of Georgia, Athens, GA 30602, U.S.A.;
    4 College of Information Sciences and Technology, Pennsylvania State University, State College, PA 16802, U.S.A
  • Received:2020-12-03 Revised:2021-05-18 Online:2021-09-30 Published:2021-09-30
  • About author:Ling-Yun Situ is an assistant professor in the School of Information Management, Nanjing University, Nanjing. He received his Ph.D. degree in computer science from Nanjing University, Nanjing, in 2020. His research interests include software and system security, static analysis, fuzzing and deep learning.
  • Supported by:
    This work was (partially) supported by the National Key Research and Development Program of China under Grant No. 2017YFA0700604, the National Natural Science Foundation of China under Grant Nos. 62032010 and 61802168, the Leading-Edge Technology Program of Jiangsu Natural Science Foundation under Grant No. BK20202001, and the 2021 Double Entrepreneurship Big Data and Theoretical Research Project of Nanjing University.

Fuzzing is known to be one of the most effective techniques to uncover security vulnerabilities of large-scale software systems. During fuzzing, it is crucial to distribute the fuzzing resource appropriately so as to achieve the best fuzzing performance under a limited budget. Existing distribution strategies of American Fuzzy Lop (AFL) based greybox fuzzing focus on increasing coverage blindly without considering the metrics of code regions, thus lacking the insight regarding which region is more likely to be vulnerable and deserves more fuzzing resources. We tackle the above drawback by proposing a vulnerable region-aware greybox fuzzing approach. Specifically, we distribute more fuzzing resources towards regions that are more likely to be vulnerable based on four kinds of code metrics. We implemented the approach as an extension to AFL named RegionFuzz. Large-scale experimental evaluations validate the effectiveness and efficiency of RegionFuzz-11 new bugs including three new CVEs are successfully uncovered by RegionFuzz.

Key words: vulnerability detection; greybox fuzzing; code metrics; resource distribution;

[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. DOI:10.1145/96267.96279.
[2] Li J, Zhao B, Zhang C. Fuzzing:A survey. Cybersecurity, 2018, 1(1):Article No. 6. DOI:10.1186/s42400-018-0002-y.
[3] Sutton M, Greene A, Amini P. Fuzzing:Brute Force Vulnerability Discovery (1st edition). Addison-Wesley Professional, 2007.
[4] Chen C, Cui B, Ma J, Wu R, Guo J, Liu W. A systematic review of fuzzing techniques. Computers & Security, 2018, 75:118-137. DOI:10.1016/j.cose.2018.02.002.
[5] Man`es V J M, Han H S, Han C, Cha S K, Egele M, Schwartz E J, Woo M. The art, science, and engineering of fuzzing:A survey. IEEE Trans. Software Engineering. DOI:10.1109/TSE.2019.2946563.
[6] Devarajan G. Unraveling SCADA protocols:Using sulley fuzzer. In Proc. the DEF CON 15 Hacking Conf., August 2007.
[7] Gascon H, Wressnegger C, Yamaguchi F, Arp D, Rieck K. Pulsar:Stateful black-box fuzzing of proprietary network protocols. In Proc. the 11th International Conference on Security and Privacy in Communication Networks, October 2015, pp.330-347. DOI:10.1007/978-3-319-28865-918.
[8] Ganesh V, Leek T, Rinard M. Taint-based directed whitebox fuzzing. In Proc. the 31st Int. Software Engineering, May 2009, pp.474-484. DOI:10.1109/ICSE.2009.5070546.
[9] Wang T, Wei T, Gu G, Zou W. TaintScope:A checksumaware directed fuzzing tool for automatic software vulnerability detection. In Proc. the 2010 IEEE Symposium on Security and Privacy, May 2010, pp.497-512. DOI:10.1109/SP.2010.37.
[10] Stephens N, Grosen J, Salls C, Dutcher A, Wang R, Corbetta J, Shoshitaishvili Y, Kruegel C, Vingna G. Driller:Augmenting fuzzing through selective symbolic execution. In Proc. the 23rd Annual Network and Distributed System Security Symposium, February 2016. DOI:10.14722/ndss.2016.23368.
[11] Godefroid P, Levin M Y, Molnar D. SAGE:Whitebox fuzzing for security testing. Communications of the ACM, 2012, 55(3):40-44. DOI:10.1145/2093548.2093564.
[12] Situ L, Wang L, Li X, Guan L, Zhang W, Liu P. Energy distribution matters in greybox fuzzing. In Proc. the 41st Int. Software Engineering:Companion Proceedings, May 2019, pp.270-271. DOI:10.1109/ICSE-Companion.2019.00109.
[13] B?hme M, Pham V T, Roychoudhury A. Coveragebased greybox fuzzing as Markov chain. IEEE Trans. Software Engineering, 2017, 45(5):489-506. DOI:10.1109/TSE.2017.2785841.
[14] Pham V T, B?hme M, Santosa A E, Caciulescu A R, Roychoudhury A. Smart greybox fuzzing. IEEE Transactions on Software Engineering. DOI:10.1109/TSE.2019.2941681.
[15] Du X, Chen B, Li Y, Guo J, Zhou Y, Liu Y, Jiang Y. Leopard:Identifying vulnerable code for vulnerability assessment through program metrics. In Proc. the 41st Int. Software Engineering, May 2019, pp.60-71. DOI:10.1109/ICSE.2019.00024.
[16] Li Y, Su Z, Wang L, Li L. Steering symbolic execution to less traveled paths. ACM SIGPLAN Notices, 2013, 48(10):19-32. DOI:10.1145/2544173.2509553.
[17] Wang X, Sun J, Chen Z, Zhang P, Wang J, Lin Y. Towards optimal concolic testing. In Proc. the 40th Int. Conf. Software Engineering, May 2018, pp.291-302. DOI:10.1145/3180155.3180177.
[18] Inozemtseva L, Holmes R. Coverage is not strongly correlated with test suite effectiveness. In Proc. the 36th Int. Conf. Software Engineering, May 2014, pp.435-445. DOI:10.1145/2568225.2568271.
[19] Petsios T, Zhao J, Keromytis A D, Jana S. SlowFuzz:Automated domain-independent detection of algorithmic complexity vulnerabilities. In Proc. the 2017 ACM SIGSAC Conference on Computer and Communications Security, October 2017, pp.2155-2168. DOI:10.1145/3133956.3134073.
[20] Lemieux C, Sen K. FairFuzz:A targeted mutation strategy for increasing greybox fuzz testing coverage. In Proc. the 33rd ACM/IEEE Int. Automated Software Engineering, September 2018, pp.475-485. DOI:10.1145/3238147.3238176.
[21] B?hme M, Pham V T, Nguyen M D, Roychoudhury A. Directed greybox fuzzing. In Proc. the 2017 ACM SIGSAC Conference on Computer and Communications Security, October 2017, pp.2329-2344. DOI:10.1145/3133956.3134020.
[22] Gan S, Zhang C, Qin X, Tu X, Li K, Pei Z, Chen Z. CollAFL:Path sensitive fuzzing. In Proc. the 2018 IEEE Symposium on Security and Privacy, May 2018, pp.679-696. DOI:10.1109/SP.2018.00040.
[23] Chen P, Chen H. Angora:Efficient fuzzing by principled search. In Proc. the 2018 IEEE Symposium on Security and Privacy, May 2018, pp.711-725. DOI:10.1109/SP.2018.00046.
[24] Dolan-Gavitt B, Hulin P, Kirda E, Lee T, Mambretti A, Robertson W, Ulrich F, Whelan R. LAVA:Large-scale automated vulnerability addition. In Proc. the 2016 IEEE Symposium on Security and Privacy, May 2016, pp.110-121. DOI:10.1109/SP.2016.15.
[25] Woo M, Cha S K, Gottlieb S, Brumley D. Scheduling blackbox mutational fuzzing. In Proc. the 2013 ACM SIGSAC Conference on Computer & Communications Security, November 2013, pp.511-522. DOI:10.1145/2508859.2516736.
[26] B?hme M. STADS:Software testing as species discovery. ACM Transactions on Software Engineering and Methodology, 2018, 27(2):Article No. 7. DOI:10.1145/3210309.
[27] Situ L Y, Wang L Z, Liu Y, Mao B, Li X. Automatic detection and repair recommendation for missing checks. Journal of Computer Science and Technology, 2019, 34(5):972-992. DOI:10.1007/s11390-019-1955-3.
[28] Rawat S, Jain V, Kumar A, Cojocar L, Giuffrida C, Bos H. VUzzer:Application-aware evolutionary fuzzing. In Proc. the 24th Annual Network and Distributed System Security Symposium, February 26-March 1, 2017. DOI:10.14722/ndss.2017.23404.
[29] Klees G, Ruef A, Cooper B, Wei S, Hichk M. Evaluating fuzz testing. In Proc. the 2018 ACM SIGSAC Conference on Computer and Communications Security, October 2018, pp.2123-2138. DOI:10.1145/3243734.3243804.
[30] Wang Y, Jia X, Liu Y, Zeng K, Bao T, Wu D, Su P. Not all coverage measurements are equal:Fuzzing by coverage accounting for input prioritization. In Proc. the 27th Annual Network and Distributed System Security Symposium, February 2020. DOI:10.14722/ndss.2020.24422.
[31] Chen H, Xue Y, Li Y, Chen B, Xie X, Wu X, Liu Y. Hawkeye:Towards a desired directed grey-box fuzzer. In Proc. the 2018 ACM SIGSAC Conference on Computer and Communications Security, October 2018, pp.2095-2108. DOI:10.1145/3243734.3243849.
[32] Vargha A, Delaney H D. A critique and improvement of the CL common language effect size statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics, 2000, 25(2):101-132. DOI:10.3102/10769986025002101.
[33] Arcuri A, Briand L. A hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability, 2014, 24(3):219-250. DOI:10.1002/stvr.1486.
[34] Li Y, Chen B, Chandramohan M, Lin S W, Liu Y, Tiu A. Steelix:Program-state based binary fuzzing. In Proc. the 11th Joint Meeting on Foundations of Software Engineering, August 2017, pp.627-637. DOI:10.1145/3106237.3106295.
[35] Serebryany K, Bruening D, Potapenko A, Vyukov D. AddressSanitizer:A fast address sanity checker. In Proc. the 2012 USENIX Annual Technical Conference, June 2012, pp.309-318.
[36] Stepanov E, Serebryany K. MemorySanitizer:Fast detector of uninitialized memory use in C++. In Proc. the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, February 2015, pp.46-55. DOI:10.1109/CGO.2015.7054186.
[37] Serebryany K, Iskhodzhanov T. ThreadSanitizer:Data race detection in practice. In Proc. the Workshop on Binary Instrumentation and Applications, December 2009, pp.62-71. DOI:10.1145/1791194.1791203.
[38] Li Y, Xue Y, Chen H, Wu, X, Zhang C, Xie X, Wang H, Liu Y. Cerebro:Context-aware adaptive fuzzing for effective vulnerability detection. In Proc. the 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, August 2019, pp.533-544. DOI:10.1145/3338906.3338975.
[1] Gen Zhang, Peng-Fei Wang, Tai Yue, Xu Zhou, Kai Lu. MEBS: Uncovering Memory Life-Cycle Bugs in Operating System Kernels [J]. Journal of Computer Science and Technology, 2021, 36(6): 1248-1268.
[2] Ling-Yun Situ, Student Member, CCF, Lin-Zhang Wang, Distinguished Member, CCF, Yang Liu, Member, ACM, IEEE, Bing Mao, Xuan-Dong Li, Fellow, CCF. Automatic Detection and Repair Recommendation for Missing Checks [J]. Journal of Computer Science and Technology, 2019, 34(5): 972-992.
Full text



[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[7] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[8] Xu Xiaoshu;. Simplification of Multivalued Sequential SULM Network by Using Cascade Decomposition[J]. , 1986, 1(4): 84 -95 .
[9] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[10] Zhong Renbao; Xing Lin; Ren Zhaoyang;. An Interactive System SDI on Microcomputer[J]. , 1987, 2(1): 64 -71 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved