Home   >   CSC-OpenAccess Library   >    Manuscript Information
Using Grammar Extracted from Sample Inputs to Generate Effective Fuzzing Files
Hamad Al Salem, Jia Song
Pages - 146 - 168     |    Revised - 30-09-2021     |    Published - 31-10-2021
Volume - 15   Issue - 5    |    Publication Date - October 2021  Table of Contents
MORE INFORMATION
KEYWORDS
Software Testing, Fuzzing, Grammar Analysis, Security Testing.
ABSTRACT
Software testing is an important step in the software development life cycle. It focuses on testing software functionalities, finding vulnerabilities, and assuring the software is executing as expected. Fuzzing is one of the software testing techniques which feeds random input to programs and monitors for abnormal behaviors such as a program crash. One of the limitations of fuzzing is that most of the fuzzers require highly structured input or certain input pattern; otherwise, the fuzz testing may be terminated at the early stage of the program execution because of not meeting the input format requirements. Some fuzzers resolve this problem by manually creating program specific input grammars to help guide fuzzing, which is tedious, error prone, and time consuming. In addition, this solution cannot work efficiently when testing multiple programs which require different input patterns. To solve this problem, a general grammar-based fuzzing technique is proposed and developed in this paper. The new fuzzer can extract grammar from the sample input files of a program, and then generate effective fuzzing files based on the grammar. This fuzzing tool is able to work with different programs by extracting grammar from them automatically and hence generate program specific fuzzing files. The fuzzing tool is fast and can find a crash in a short time. From the experiments, it successfully crashed 79 (out of 235) programs of the DARPA CGC dataset.
1 Semantic Scholar 
2 refSeek 
3 Doc Player 
4 J-Gate 
5 Scribd 
6 SlideShare 
Al Salem, H., & Song, J. (June 2019). A Review on Grammar-Based Fuzzing Techniques. International Journal of Computer Science & Security (IJCSS), 13(3), 114-123.
Amini, P. a. (2013, May). Sulley: Pure Python fully automated and unattended fuzzing framework.
Aschermann, C., Frassetto, T., Holz, T., Jauernig, P., Sadeghi, A.-R., & Teuchert, D. (2019). NAUTILUS: Fishing for Deep Bugs with Grammars. NDSS.
Atlidakis, V., Geambasu, R., Godefroid, P., Polishchuk, M., & Ray, B. (2020). Pythia: Grammar-Based Fuzzing of REST APIs with Coverage-guided Feedback and Learning-based Mutations.
Atlidakis, V., Geambasu, R., Godefroid, P., Polishchuk, M., & Ray, B. (2020). Pythia: Grammar-Based Fuzzing of REST APIs with Coverage-guided Feedback and Learning-based Mutations. arXiv preprint arXiv:2005.11498.
Böhme, M., Pham, V.-T., & Roychoudhury, A. (2017). Coverage-based greybox fuzzing as markov chain. IEEE Transactions on Software Engineering, 45, 489–506.
Blazytko, T., Bishop, M., Aschermann, C., Cappos, J., Schlögel, M., Korshun, N., . . . others. (2019). GRIMOIRE: Synthesizing structure while fuzzing. 28th USENIX Security Symposium (USENIX Security 19), (pp. 1985–2002).
Darpa challenge binaries on multiple os systems. (n.d.). Retrieved from https://github.com/trailofbits/cb-multios
Eberlein, M., Noller, Y., Vogel, T., & Grunske, L. (Sept. 2020). Evolutionary Grammar-Based Fuzzing. International Symposium on Search Based Software Engineering.
Fuzzer, P. (2016). Discover unknown vulnerabilities. Peach, Peach Fuzzer.[Online]. Available: http://www. peachfuzzer. com/. Accessed on: Jul, 13.
Gan, S., Zhang, C., Chen, P., Zhao, B., Qin, X., Wu, D., & Chen, Z. (Aug. 2020). GREYONE: Data Flow Sensitive Fuzzing. Proceedings of the 29th USENIX Security Symposium.
Godefroid, P. (Jan, 2020). Fuzzing: Hack, art, and science. Communications of the ACM, 63(2), 70-76.
Godefroid, P., Peleg, H., & Singh, R. (2017). Learn&fuzz: Machine learning for input fuzzing. Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, (pp. 50–59).
Grieco, G., Ceresa, M., & Buiras, P. (2016). Quickfuzz: an automatic random fuzzer for common file formats. Proceedings of the 9th International Symposium on Haskell, (pp. 13–20).
Guo, T., Zhang, P., Wang, X., & Wei, Q. (2013). GramFuzz: Fuzzing testing of web browsers based on grammar analysis and structural mutation. Informatics and Applications (ICIA), 2013 Second International Conference on, (pp. 212–215).
Helin, A. (2006). Radamsa fuzzer. Radamsa fuzzer.
Hodován, R., Kiss, Á., & Gyimóthy, T. (2018). Grammarinator: a grammar-based open source fuzzer. Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, (pp. 45–48).
Holler, C., Herzig, K., & Zeller, A. (2012). Fuzzing with Code Fragments. USENIX Security Symposium, (pp. 445–458).
Hu, Z., Shi, J., Huang, Y., Xiong, J., & Bu, X. (2018). GANFuzz: a GAN-based industrial network protocol fuzzing framework. Proceedings of the 15th ACM International Conference on Computing Frontiers, (pp. 138–145).
Jitsunari, Y., & Arahori, Y. (2019). Coverage-guided Learning-assisted Grammar-based Fuzzing. IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW).
Kim, S. Y., Cha, S., & Bae, D.-H. (2013). Automatic and lightweight grammar generation for fuzz testing. Computers & Security, 36, 1–11.
Koroglu, Y., & Wotawa, F. (2019). Fully automated compiler testing of a reasoning engine via mutated grammar fuzzing. IEEE/ACM 14th International Workshop on Automation of Software Test (AST), (pp. 28–34).
Lemieux, C., & Sen, K. (2018). Fairfuzz: A targeted mutation strategy for increasing greybox fuzz testing coverage. Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, (pp. 475–485).
Liang, H., Pei, X., Jia, X., Shen, W., & Zhang, J. (Sept. 2018). Fuzzing: State of the Art. IEEE Transactions on Reliability, 67(3), 1199-1218.
Lyu, C., Ji, S., Zhang, C., Li, Y., Lee, W.-H., Song, Y., & Beyah, R. (2019). MOPT: Optimized mutation scheduling for fuzzers. 28th USENIX Security Symposium (USENIX Security 19), (pp. 1949–1966).
Miller, B. P., Fredriksen, L., & So, B. (1990). An empirical study of the reliability of UNIX utilities. Communications of the ACM, 33, 32–44.
Noller, Y. (Sept. 2018). Differential program analysis with fuzzing and symbolic execution. ASE 2018: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, (pp. 944-947).
Norris, J. (1998, July). Markov Chain (Cambridge Series in Statistical and Proba-bilistic Mathematics). Cambridge, U.K.: Cambridge Univ. Press.
Oehlert, P. (2005). Violating assumptions with fuzzing. IEEE Security & Privacy, 3, 58–62.
Pham, V.-T., Böhme, M., Santosa, A. E., Caciulescu, A. R., & Roychoudhury, A. (2019). Smart greybox fuzzing. IEEE Transactions on Software Engineering.
Ruderman, J. (2007). Introducing jsfunfuzz. URL http://www. squarefree. com/2007/08/02/introducing-jsfunfuzz, 20, 25–29.
Sargsyan, S., Kurmangaleev, S., Mehrabyan, M., Mishechkin, M., Ghukasyan, T., & Asryan, S. (2018). Grammar-Based Fuzzing. Ivannikov Memorial Workshop (IVMEM), (pp. 32–35).
Serebryany, K. (2015). Simple guided fuzzing for libraries using LLVM’s new libFuzzer. Simple guided fuzzing for libraries using LLVM’s new libFuzzer.
Shoshitaishvili, Y., Wang, R., Salls, C., Stephens, N., Polino, M., Dutcher, A., . . . others. (2016). Sok:(state of) the art of war: Offensive techniques in binary analysis. IEEE Symposium on Security and Privacy (SP), (pp. 138–157).
Veggalam, S., Rawat, S., Haller, I., & Bos, H. (2016). Ifuzzer: An evolutionary interpreter fuzzer using genetic programming. European Symposium on Research in Computer Security, (pp. 581–601).
Wang, J., Chen, B., Wei, L., & Liu, Y. (2017). Skyfire: Data-driven seed generation for fuzzing. Security and Privacy (SP), IEEE Symposium on, (pp. 579–594).
Wang, J., Chen, B., Wei, L., & Liu, Y. (2018). Superion: Grammar-Aware Greybox Fuzzing. arXiv preprint arXiv:1812.01197.
Yang, D., Zhang, Y., & Liu, Q. (2012). Blendfuzz: A model-based framework for fuzz testing programs with grammatical inputs. Trust, Security and Privacy in Computing and Communications (TrustCom), IEEE 11th International Conference on, (pp. 1070–1076).
Zalewski, M. (2014). American fuzzy lop. American fuzzy lop.
Mr. Hamad Al Salem
Computer Science Department, University of Idaho, Moscow, ID, 83844 - United States of America
alsa5294@vandals.uidaho.edu
Dr. Jia Song
Computer Science Department, University of Idaho, Moscow, ID, 83844 - United States of America


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS