Journal of Computers, Vol 6, No 5 (2011), 881-888, May 2011
doi:10.4304/jcp.6.5.881-888

A New Fuzzing Method Using Multi Data Samples Combination

Xueyong Zhu, Zhiyong Wu, J. William Atwood

Abstract


Knowledge-based Fuzzing technologies have been applied successfully in software vulnerability mining, however, its current methods mainly focus on Fuzzing target software using a single data sample with one or multi-dimension input mutation [1], and thus the vulnerability mining results are not stable, false negatives of vulnerability are high and the selection of data sample depends on human analysis. To solve these problems, this paper proposes a model named Fuzzing Test Suite Generation model using multi data sample combination (FTSGc), which can automatically select multi data samples combination from a large scale data sample set to fuzz target software and generate the test cases that can cover more codes of the software vulnerabilities. To solve Data Sample Coverage Problem (DSCP) in the proposed FTSGc, a method of covering maximum nodes’ semantic attributes with minimum running cost is put forward and a theorem named Maximum Coverage Theorem is given to select the data sample combination. We conclude that DSCP is actually the Set Covering Problem (SCP). Practical experimental results show that the proposed Fuzzing method works much better than the other current Fuzzing method on the Ability of Vulnerability Mining (AVM).


Keywords


Fuzzing; Vulnerability mining; FTSGc; DSCP; AVM

References


[1]Zhiyong Wu, J. William Atwood, Xueyong Zhu. A New Fuzzing Technique for Software Vulnerability Mining, In Proceedings of the IEEE CONSEG’09. Chennai, India, Dec. 19, 2009.

[2]P. Oehlert. Violating Assumptions with Fuzzing [J]. IEEE Security & Privacy, Vol.3 (No.2), 2005, pages 58-62, In IEEE Computer Society.

[3]L. Andrea, M. Lorenzo, M. Mattia and P. Roberto. A Smart Fuzzer for x86 Executables[C]. In Proceedings of the Third International Workshop on Software Engineering for Secure Systems: IEEE Computer Society, 2007.

[4]P. Godefroid, M. Levin, and D. Molnar. Automated whitebox fuzz testing[C]. In NDSS, 2008.

[5]P. Godefroid, Peli de Halleux, Aditya V.,et al. Automating Software Testing Using Program Analysis [J], IEEE SOFTWARE, September/October 2008, pp. 30-37.
doi:10.1109/MS.2008.109

[6]LIU Guang-Hong, WU Gang, Zheng Tao, SHUAI Jian-Mei, TANG Zhuo-Chun. Vulnerability Analysis for X86 Executables Using Genetic Algorithm and Fuzzing[C]. In Third 2008 International Conference on Convergence Hybird Information Technology (ICCIT.2008.9).

[7]Sherri Sparks, Ryan Cunningham, Shawn Embleton, Cliff C. Zou. "Automated Vulnerability Analysis: Leveraging Control Flow for Evolutionary Input Crafting", in 23rd Annual Computer Security Softwares Conference (ACSAC), p.477-486, Miami Beach, Florida, Dec. 10-14, 2007. (acceptance ratio: 40/191=21%).

[8]Peach[CP/OL].Webpage: http://www.peachFuzzer.com. http://peachfuzz.sourceforge.net.http://peachfuzz@googlegroups.com. Visited on June, 2009.

[9]Sulley[CP/OL]. Web page: http://www.fuzzing.org. Visited on June, 2009.

[10]AutoDafe[CP/OL].Webpage: http://autodafe.sourceforge.net/docs/autodafe.pdf. Visited on June, 2009.

[11]C. Miller, Z. N.J. Peterson. Analysis of Mutation and Generation-Based Fuzzing[EB/OL], March 1, 2007. Web page:http://securityevaluators.com/files/papers/analysisfuzzing.pdf, visited on June, 2009.

[12]FileFuzz[CP/OL] .http://labs.idefense.com/software/fuzzing.php Visited on Sept., 2009.

[13]Guanghui Lan, Gail W. DePuy, Gary E. Whitehouse. An effective and simple heuristic for the set covering problem. European Journal of Operation Research 176(2007). P.1387-1403.
doi:10.1016/j.ejor.2005.09.028

[14]Garey, M.R., Johnson, D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.

[15]David S.Johnson, Approximation algorithms for combinatorial problems. Proceedings of the fifth annual ACM symposium on theory of computing. P.38-49. April 30-May02, 1973, Austin, Texas, United States.

[16]LibPng[CP/OL]. http://www.libpng.org. Visited on Sept., 2009.

[17]T. Boutell, et al., PNG (Portable Network Grapics) Specification, Version 1.0[M/OL], IETF Request for Comments 2083.

[18]Greg Roelofs, PNG: The Definitive Guide[M/OL]. O′ REILLY. 2009.9. http://www.libpng.org/pub/png/book.

[19]Ntafos, Simeon,"A Comparison of Some Structural Testing Strategies", IEEE Trans. Software Eng., Vol.14, No.6, June 1988, pp.868-874.
doi:10.1109/32.6165

[20]Beizer, Boris, "Software Testing Techniques", 2nd edition, New York: Van Nostrand Reinhold, 1990.


Full Text: PDF


Journal of Computers (JCP, ISSN 1796-203X)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.