Journal of Computer Science and Technology ›› 2020, Vol. 35 ›› Issue (6): 1406-1427.doi: 10.1007/s11390-020-0525-z

Special Issue: Software Systems

Previous Articles     Next Articles

Automatic Buffer Overflow Warning Validation

Feng-Juan Gao1,2, Yu Wang1,2, Lin-Zhang Wang1,2,*, Distinguished Member, CCF Zijiang Yang3, Senior Member, IEEE, and Xuan-Dong Li1,2, Fellow, CCF        

  1. 1 State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China;
    2 Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China;
    3 Department of Computer Science, Western Michigan University, Kalamazoo 49008-5466, U.S.A
  • Received:2020-04-11 Revised:2020-10-22 Online:2020-11-20 Published:2020-12-01
  • Contact: Lin-Zhang Wang E-mail:lzwang@nju.edu.cn
  • About author:Feng-Juan Gao is a Ph.D. candidate in Nanjing University, Nanjing. She received her B.S. degree in computer science from University of Electronic Science and Technology of China, Chengdu, in 2014. Her research is in software engineering, with focus on symbolic execution.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China under Grant No. 62032010, and partially by the Postgraduate Research and Practice Innovation Program of Jiangsu Province of China.

Static buffer overflow detection techniques tend to report too many false positives fundamentally due to the lack of software execution information. It is very time consuming to manually inspect all the static warnings. In this paper, we propose BovInspector, a framework for automatically validating static buffer overflow warnings and providing suggestions for automatic repair of true buffer overflow warnings for C programs. Given the program source code and the static buffer overflow warnings, BovInspector first performs warning reachability analysis. Then, BovInspector executes the source code symbolically under the guidance of reachable warnings. Each reachable warning is validated and classified by checking whether all the path conditions and the buffer overflow constraints can be satisfied simultaneously. For each validated true warning, BovInspector provides suggestions to automatically repair it with 11 repair strategies. BovInspector is complementary to prior static buffer overflow discovery schemes. Experimental results on real open source programs show that BovInspector can automatically validate on average 60% of total warnings reported by static tools.

Key words: buffer overflow; static analysis warning; symbolic execution; automatic repair;

[1] Anderson J P. Computer security technology planning study. Technical Report, Air Force Electronic Systems Division, 1972. https://apps.dtic.mil/sti/citations/AD0758206, Oct. 2020.
[2] Shahzad M, Shafiq M Z, Liu A X. A large scale exploratory analysis of software vulnerability life cycles. In Proc. the 34th Int. Conference on Software Engineering, Jun. 2012, pp.771-781.
[3] Viega J, Bloch J T, Kohno Y, McGraw G. ITS4:A static vulnerability scanner for C and C++ code. In Proc. the 16th Annual Computer Security Applications Conference, Dec. 2000, pp.257-267.
[4] Wagner D A, Foster J S, Brewer E A, Aiken A. A first step towards automated detection of buffer overrun vulnerabilities. In Proc. the Network and Distributed System Security Symp., Feb. 2000.
[5] Evans D, Larochelle D. Improving security using extensible lightweight static analysis. IEEE Software, 2002, 19(1):42-51.
[6] Xie Y, Chou A, Engler D. ARCHER:Using symbolic, pathsensitive analysis to detect memory access errors. In Proc. the 9th European Software Engineering Conference Held Jointly with the 11th ACM SIGSOFT Int. Symp. Foundations of Software Engineering, Sept. 2003, pp.327-336.
[7] Le W, Soffa M L. Marple:A demand-driven path-sensitive buffer overflow detector. In Proc. the 16th ACM SIGSOFT Int. Symp. Foundations of Software Engineering, Nov. 2008, pp.272-282.
[8] Avgerinos T, Cha S, Hao B, Brumley D. AEG:Automatic exploit generation. In Proc. the Network and Distributed System Security Symp., Feb. 2011, pp.59-66.
[9] Yamaguchi F, Golde N, Arp D, Rieck K. Modeling and discovering vulnerabilities with code property graphs. In Proc. the 2014 IEEE Symp. Security and Privacy, May 2014, pp.590-604.
[10] Cowan C, Pu C, Maier D, Walpole J, Bakke P, Beattie S, Grier A, Wagle P, Zhang Q, Hinton H. StackGuard:Automatic adaptive detection and prevention of buffer-overflow attacks. In Proc. the 7th USENIX Security Symp., Jan. 1998, pp.63-78.
[11] Jones R W, Kelly P H. Backwards-compatible bounds checking for arrays and pointers in C programs. In Proc. the 3rd International Workshop on Automated Debugging, May 1997, pp.13-26.
[12] Wagner D, Dean R. Intrusion detection via static analysis. In Proc. the 2001 IEEE Symp. Security and Privacy, May 2001, pp.156-168.
[13] Haugh E, Bishop M. Testing C programs for buffer overflow vulnerabilities. In Proc. the Network and Distributed System Security Symp., Feb. 2003.
[14] Xu R G, Godefroid P, Majumdar R. Testing for buffer overflows with length abstraction. In Proc. the 2008 ACM/SIGSOFT Int. Symp. Software Testing and Analysis, Jul. 2008, pp.27-38.
[15] Gao F, Wang L, Li X. BovInspector:Automatic inspection and repair of buffer overflow vulnerabilities. In Proc. the 31st IEEE/ACM Int. Conference on Automated Software Engineering, Sept. 2016, pp.786-791.
[16] Clarke L A. A system to generate test data and symbolically execute programs. IEEE Trans. Software Engineering, 1976, 2(3):215-222.
[17] Cadar C, Dunbar D, Engler D R et al. KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proc. the 8th USENIX Symp. Operating Systems Design and Implementations, Dec. 2008, pp.209-224.
[18] Ye T, Zhang L, Wang L, Li X. An empirical study on detecting and fixing buffer overflow bugs. In Proc. the IEEE Int. Conference on Software Testing, Verification and Validation, Apr. 2016, pp.91-101.
[19] Sinha S, Harrold M J, Rothermel G. Interprocedural control dependence. ACM Trans. Software Engineering and Methodology, 2001, 10(2):209-254.
[20] Larochelle D, Evans D. Statically detecting likely buffer overflow vulnerabilities. In Proc. the 10th USENIX Security Symp., Aug. 2001, pp.177-190.
[21] Zitser M, Lippmann R, Leek T. Testing static analysis tools using exploitable buffer overflows from open source code. In Proc. the 12th ACM SIGSOFT Int. Symp. Foundations of Software Engineering, Oct. 2004, pp.97-106.
[22] Lu S, Li Z, Qin F, Tan L, Zhou P, Zhou Y. BugBench:Benchmarks for evaluating bug detection tools. In Proc. the Workshop on the Evaluation of Software Defect Detection Tools, Jun. 2005.
[23] Burnim J, Sen K. Heuristics for scalable dynamic test generation. In Proc. the 23rd IEEE/ACM Int. Conference on Automated Software Engineering, Sept. 2008, pp.443-446.
[24] Taneja K, Xie T, Tillmann N, de Halleux J. eXpress:Guided path exploration for efficient regression test generation. In Proc. the 20th Int. Symp. Software Testing and Analysis, Jul. 2011, pp.1-11.
[25] Babić D, Martignoni L, McCamant S, Song D. Staticallydirected dynamic automated test generation. In Proc. the 20th Int. Symp. Software Testing and Analysis, Jul. 2011, pp.12-22.
[26] Xie T, Tillmann N, De Halleux J, Schulte W. Fitness-guided path exploration in dynamic symbolic execution. In Proc. the 2009 IEEE/IFIP Int. Conference on Dependable Systems and Networks, Jun. 2009, pp.359-368.
[27] le Goues C, Dewey-Vogt M, Forrest S, Weimer W. A systematic study of automated program repair:Fixing 55 out of 105 bugs for $8 each. In Proc. the 34th Int. Conference on Software Engineering, Jun. 2012, pp.3-13.
[28] Qi Y, Mao X, Lei Y, Dai Z, Wang C. The strength of random search on automated program repair. In Proc. the 36th Int. Conference on Software Engineering, May 2014, pp.254-265.
[29] Weimer W, Fry Z P, Forrest S. Leveraging program equivalence for adaptive program repair:Models and first results. In Proc. the 28th IEEE/ACM Int. Conference on Automated Software Engineering, Nov. 2013, pp.356-366.
[30] Qi Z, Long F, Achour S, Rinard M. An analysis of patch plausibility and correctness for generate-and-validate patch generation systems. In Proc. the 2015 Int. Symp. Software Testing and Analysis, Jul. 2015, pp.24-36.
[31] Gazzola L, Micucci D, Mariani L. Automatic software repair:A survey. IEEE Trans. Software Engineering, 2017, 45(1):34-67.
[32] Monperrus M. Automatic software repair:A bibliography. ACM Computing Surveys, 2018, 51(1):Article No. 17.
[33] Sidiroglou-Douskos S, Lahtinen E, Long F, Rinard M. Automatic error elimination by horizontal code transfer across multiple applications. In Proc. the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun. 2015, pp.43-54.
[34] Ke Y, Stolee K T, le Goues C, Brun Y. Repairing programs with semantic code search (T). In Proc. the 30th IEEE/ACM Int. Conference on Automated Software Engineering, Nov. 2015, pp.295-306.
[35] Smirnov A, Chiueh T C. DIRA:Automatic detection, identification and repair of control-hijacking attacks. In Proc. the Network and Distributed System Security Symp., Feb. 2005.
[36] Sidiroglou-Douskos S, Lahtinen E, Rinard M. Automatic discovery and patching of buffer and integer overflow errors. Technical Report, Massachusetts Institute of Technology, Cambridge, 2015. https://dspace.mit.edu/handle/1721.1/97087, Oct. 2020.
[37] Perkins J H, Kim S, Larsen S et al. Automatically patching errors in deployed software. In Proc. the 22nd ACM SIGOPS Symp. Operating Systems Principles, Oct. 2009, pp.87-102.
[38] Ruthruff J, Penix J, Morgenthaler J, Elbaum S, Rothermel G. Predicting accurate and actionable static analysis warnings. In Proc. the 30th ACM/IEEE Int. Conference on Software Engineering, May 2008, pp.341-350.
[39] Junker M, Huuck R, Fehnker A, Knapp A. SMT-based false positive elimination in static program analysis. In Proc. the 14th Int. Conference on Formal Engineering Methods, Nov. 2012, pp.316-331.
[40] Muske T, Khedker U P. Efficient elimination of false positives using static analysis. In Proc. the 26th IEEE Int. Symp. Software Reliability Engineering, Nov. 2015, pp.270-280.
[41] Fan G, Wu R, Shi Q, Xiao X, Zhou J, Zhang C. Smoke:Scalable path-sensitive memory leak detection for millions of lines of code. In Proc. the 41st IEEE/ACM Int. Conference on Software Engineering, May 2019, pp.72-82.
[42] Kim Y, Lee J, Han H, Choe K M. Filtering false alarms of buffer overflow analysis using SMT solvers. Information and Software Technology, 2010, 52(2):210-219.
[43] Arzt S, Rasthofer S, Hahn R, Bodden E. Using targeted symbolic execution for reducing false-positives in dataflow analysis. In Proc. the 4th ACM SIGPLAN Int. Workshop on State of the Art in Program Analysis, Jun. 2015, pp.1-6.
[1] Ming-Zhe Zhang, Yun-Zhan Gong, Ya-Wen Wang, Da-Hai Jin. Unit Test Data Generation for C Using Rule-Directed Symbolic Execution [J]. Journal of Computer Science and Technology, 2019, 34(3): 670-689.
[2] Liu Zongtian; Chen Fuan;. Research on Decompiling Technology [J]. , 1994, 9(4): 311-319.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[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] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] Wu Enhua;. A Graphics System Distributed across a Local Area Network[J]. , 1986, 1(3): 53 -64 .
[5] Qu Yanwen;. AGDL: A Definition Language for Attribute Grammars[J]. , 1986, 1(3): 80 -91 .
[6] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[7] 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 .
[8] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[9] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[10] 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 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved