More Web Proxy on the site http://driver.im/

research-article

Open access

Rare Path Guided Fuzzing

Authors:

Md Shafiuzzaman,

Ganesh Sankaran,

Tevfik BultanAuthors Info & Claims

ISSTA 2023: Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis

Pages 1295 - 1306

https://doi.org/10.1145/3597926.3598136

Published: 13 July 2023 Publication History

Abstract

Starting with a random initial seed, fuzzers search for inputs that trigger bugs or vulnerabilities. However, fuzzers often fail to generate inputs for program paths guarded by restrictive branch conditions. In this paper, we show that by first identifying rare-paths in programs (i.e., program paths with path constraints that are unlikely to be satisfied by random input generation), and then, generating inputs/seeds that trigger rare-paths, one can improve the coverage of fuzzing tools. In particular, we present techniques 1) that identify rare paths using quantitative symbolic analysis, and 2) generate inputs that can explore these rare paths using path-guided concolic execution. We provide these inputs as initial seed sets to three state of the art fuzzers. Our experimental evaluation on a set of programs shows that the fuzzers achieve better coverage with the rare-path based seed set compared to a random initial seed.

References

[1]

2006. laf-intel. https://lafintel.wordpress.com/

[2]

2022. Calculator. https://github.com/btmills/calculator

[3]

2022. CodeQL. https://codeql.github.com

[4]

2022. Docker for AFL++. https://hub.docker.com/r/aflplusplus/aflplusplus

[5]

2022. Docker for FairFuzz. https://hub.docker.com/r/zjuchenyuan/fairfuzz

[6]

2023. SV-Benchmark:seq-mthreded. https://gitlab.com/sosy-lab/benchmarking/sv-benchmarks/-/tree/main/c/seq-mthreaded

[7]

Frances E. Allen. 1970. Control Flow Analysis. SIGPLAN Not., 5, 7 (1970), jul, 1–19. issn:0362-1340 https://doi.org/10.1145/390013.808479

Digital Library

[8]

Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, and Thorsten Holz. 2019. REDQUEEN: Fuzzing with Input-to-State Correspondence. https://doi.org/10.14722/ndss.2019.23371

[9]

Abdulbaki Aydin, Lucas Bang, and Tevfik Bultan. 2015. Automata-Based Model Counting for String Constraints. 255–272. isbn:978-3-319-21689-8 https://doi.org/10.1007/978-3-319-21690-4_15

[10]

Thomas Bach, Artur Andrzejak, Ralf Pannemans, and David Lo. 2017. The Impact of Coverage on Bug Density in a Large Industrial Software Project. https://doi.org/10.1109/ESEM.2017.44

Digital Library

[11]

Sofia Bekrar, Chaouki Bekrar, Roland Groz, and Laurent Mounier. 2012. A Taint Based Approach for Smart Fuzzing. Proceedings - IEEE 5th International Conference on Software Testing, Verification and Validation, ICST 2012, 04, https://doi.org/10.1109/ICST.2012.182

Digital Library

[12]

Dirk Beyer. 2021. Software Verification: 10th Comparative Evaluation (SV-COMP 2021). 401–422. isbn:978-3-030-72012-4 https://doi.org/10.1007/978-3-030-72013-1_24

Digital Library

[13]

Dirk Beyer. 2022. Advances in Automatic Software Testing: Test-Comp 2022. 321–335. isbn:978-3-030-99428-0 https://doi.org/10.1007/978-3-030-99429-7_18

Digital Library

[14]

Marcel Bohme, Thuan Pham, and Abhik Roychoudhury. 2017. Coverage-Based Greybox Fuzzing as Markov Chain. IEEE Transactions on Software Engineering, PP (2017), 12, 1–1. https://doi.org/10.1109/TSE.2017.2785841

[15]

Sergey Bratus, Axel Hansen, and Anna Shubina. 2008. LZfuzz: a fast compression-based fuzzer for poorly documented protocols.

[16]

Jacob Burnim and Koushik Sen. 2008. Heuristics for Scalable Dynamic Test Generation. In 2008 23rd IEEE/ACM International Conference on Automated Software Engineering. 443–446. https://doi.org/10.1109/ASE.2008.69

Digital Library

[17]

Cristian Cadar, Daniel Dunbar, and Dawson R Engler. 2008. Klee: unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI. 8, 209–224.

Digital Library

[18]

Antonio Filieri, Corina Păsăreanu, Willem Visser, and Jaco Geldenhuys. 2014. Statistical symbolic execution with informed sampling. 437–448. https://doi.org/10.1145/2635868.2635899

Digital Library

[19]

Andrea Fioraldi, Dominik Maier, Heiko Eiß feldt, and Marc Heuse. 2020. $AFL++$: Combining Incremental Steps of Fuzzing Research. In 14th USENIX Workshop on Offensive Technologies (WOOT 20).

[20]

Shuitao Gan, Chao Zhang, Peng Chen, Bodong Zhao, Xiaojun Qin, Dong Wu, and Zuoning Chen. 2020. $GREYONE$: Data flow sensitive fuzzing. In 29th USENIX Security Symposium (USENIX Security 20). 2577–2594.

[21]

Jaco Geldenhuys, Matthew Dwyer, and Willem Visser. 2012. Probabilistic symbolic execution. 2012 International Symposium on Software Testing and Analysis, ISSTA 2012 - Proceedings, 07, https://doi.org/10.1145/2338965.2336773

Digital Library

[22]

Patrice Godefroid, Adam Kiezun, and Michael Levin. 2008. Grammar-based Whitebox Fuzzing. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 43, 206–215. https://doi.org/10.1145/1379022.1375607

Digital Library

[23]

Adrian Herrera, Hendra Gunadi, Shane Magrath, Michael Norrish, Mathias Payer, and Antony Hosking. 2021. Seed selection for successful fuzzing. 230–243. https://doi.org/10.1145/3460319.3464795

Digital Library

[24]

Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with code fragments. In 21st USENIX Security Symposium (USENIX Security 12). 445–458.

[25]

Caroline Lemieux and Koushik Sen. 2018. FairFuzz: a targeted mutation strategy for increasing greybox fuzz testing coverage. 475–485. https://doi.org/10.1145/3238147.3238176

Digital Library

[26]

Caroline Lemieux and Koushik Sen. 2021. FairFuzz-TC: a fuzzer targeting rare branches. International Journal on Software Tools for Technology Transfer, 23, 6 (2021), 01 Dec, 863–866. issn:1433-2787 https://doi.org/10.1007/s10009-020-00569-w

Digital Library

[27]

Caroline Lemieux and Koushik Sen. 2021. FairFuzz-TC: a fuzzer targeting rare branches. International Journal on Software Tools for Technology Transfer, 23, 6 (2021), 01 Dec, 863–866. issn:1433-2787 https://doi.org/10.1007/s10009-020-00569-w

Digital Library

[28]

Yuekang Li, Bihuan Chen, Mahinthan Chandramohan, Shang-Wei Lin, Yang Liu, and Alwen Tiu. 2017. Steelix: Program-State Based Binary Fuzzing. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2017). Association for Computing Machinery, New York, NY, USA. 627–637. isbn:9781450351058 https://doi.org/10.1145/3106237.3106295

Digital Library

[29]

Hongliang Liang, Xiaoxiao Pei, Xiaodong Jia, Wuwei Shen, and Jian Zhang. 2018. Fuzzing: State of the Art. IEEE Transactions on Reliability, 67, 3 (2018), 1199–1218. https://doi.org/10.1109/TR.2018.2834476

[30]

Jie Liang, Yu Jiang, Mingzhe Wang, Xun Jiao, Yuanliang Chen, Houbing Song, and Kim-Kwang Raymond Choo. 2021. DeepFuzzer: Accelerated Deep Greybox Fuzzing. IEEE Transactions on Dependable and Secure Computing, 18, 6 (2021), 2675–2688. https://doi.org/10.1109/TDSC.2019.2961339

Digital Library

[31]

Chenyang Lyu, Shouling Ji, Chao Zhang, Yuwei Li, Wei-Han Lee, Yu Song, and Raheem Beyah. 2019. $MOPT$: Optimized mutation scheduling for fuzzers. In 28th USENIX Security Symposium (USENIX Security 19). 1949–1966.

[32]

Björn Mathis, Rahul Gopinath, Michaël Mera, Alexander Kampmann, Matthias Höschele, and Andreas Zeller. 2019. Parser-Directed Fuzzing. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2019). Association for Computing Machinery, New York, NY, USA. 548–560. isbn:9781450367127 https://doi.org/10.1145/3314221.3314651

Digital Library

[33]

Michał Zalewski. 2014. American Fuzzy Lop. http://lcamtuf.coredump.cx/afl/

[34]

George C. Necula, Scott McPeak, Shree P. Rahul, and Westley Weimer. 2002. CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs. In Compiler Construction, R. Nigel Horspool (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 213–228. isbn:978-3-540-45937-8

Digital Library

[35]

Haibo Pang, Jie Jian, Yan Zhuang, Yingyun Ye, and Zhanbo Li. 2021. SpotFuzz: Fuzzing Based on Program Hot-Spots. Electronics, 10 (2021), 12, 3142. https://doi.org/10.3390/electronics10243142

[36]

Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. 2017. VUzzer: Application-aware Evolutionary Fuzzing. https://doi.org/10.14722/ndss.2017.23404

[37]

Seemanta Saha, Mara Downing, Tegan Brennan, and Tevfik Bultan. 2022. PREACH: A Heuristic for Probabilistic Reachability to Identify Hard to Reach Statements. In 44th IEEE/ACM 44th International Conference on Software Engineering, ICSE 2022, Pittsburgh, PA, USA, May 25-27, 2022. ACM, 1706–1717. https://doi.org/10.1145/3510003.3510227

Digital Library

[38]

Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang, Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna. 2016. Driller: Augmenting Fuzzing Through Selective Symbolic Execution. https://doi.org/10.14722/ndss.2016.23368

[39]

Fish Wang and Yan Shoshitaishvili. 2017. Angr - The Next Generation of Binary Analysis. In 2017 IEEE Cybersecurity Development (SecDev). 8–9. https://doi.org/10.1109/SecDev.2017.14

[40]

Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2017. Skyfire: Data-Driven Seed Generation for Fuzzing. In 2017 IEEE Symposium on Security and Privacy (SP). 579–594. https://doi.org/10.1109/SP.2017.23

[41]

Mingyuan Wu, Ling Jiang, Jiahong Xiang, Yuqun Zhang, Guowei Yang, Huixin Ma, Sen Nie, Shi Wu, Heming Cui, and Lingming Zhang. 2022. Evaluating and Improving Neural Program-Smoothing-based Fuzzing. In 2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE). 847–858. https://doi.org/10.1145/3510003.3510089

Digital Library

[42]

Jingbo Yan, Yuqing Zhang, and Dingning Yang. 2013. Structurized grammar‐based fuzz testing for programs with highly structured inputs. Security and Communication Networks, 6 (2013), 11, https://doi.org/10.1002/sec.714

[43]

Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’11). Association for Computing Machinery, New York, NY, USA. 283–294. isbn:9781450306638 https://doi.org/10.1145/1993498.1993532

Digital Library

[44]

Hyunguk Yoo and Taeshik Shon. 2016. Grammar-based adaptive fuzzing: Evaluation on SCADA modbus protocol. 557–563. https://doi.org/10.1109/SmartGridComm.2016.7778820

[45]

Wei You, Xuwei Liu, Shiqing Ma, David Perry, Xiangyu Zhang, and Bin Liang. 2019. SLF: Fuzzing without Valid Seed Inputs. In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). 712–723. https://doi.org/10.1109/ICSE.2019.00080

Digital Library

[46]

Insu Yun, Sangho Lee, Meng Xu, Yeongjin Jang, and Taesoo Kim. 2018. $QSYM$: A practical concolic execution engine tailored for hybrid fuzzing. In 27th USENIX Security Symposium (USENIX Security 18). 745–761.

[47]

Lei Zhao, Yue Duan, Heng Yin, and Jifeng Xuan. 2019. Send Hardest Problems My Way: Probabilistic Path Prioritization for Hybrid Fuzzing. In NDSS. https://doi.org/10.14722/ndss.2019.23504

Cited By

St. Amour LTilevich EErtl MKirsch C(2024)Toward Declarative Auditing of Java Software for Graceful Exception HandlingProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685057(90-97)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685057
Chen JYan FCai SWang SChen J(2024)FMUZZ: A Novel Greybox Fuzzing Approach based on Mutation Strategy Optimization with Byte Scheduling2024 IEEE 24th International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS62785.2024.00061(550-561)Online publication date: 1-Jul-2024
https://doi.org/10.1109/QRS62785.2024.00061
Li TZong WWang YTian HWang YCheung SKramer J(2023)Nuances are the Key: Unlocking ChatGPT to Find Failure-Inducing Tests with Differential Prompting2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE56229.2023.00089(14-26)Online publication date: 11-Sep-2023
https://doi.org/10.1109/ASE56229.2023.00089

Index Terms

Rare Path Guided Fuzzing
1. Software and its engineering
  1. Software organization and properties
    1. Extra-functional properties
      1. Software reliability
    2. Software functional properties
      1. Formal methods
        Software verification

Recommendations

Guiding Greybox Fuzzing with Mutation Testing
ISSTA 2023: Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis

Greybox fuzzing and mutation testing are two popular but mostly independent fields of software testing research that have so far had limited overlap. Greybox fuzzing, generally geared towards searching for new bugs, predominantly uses code coverage ...
Fuzzing: A Survey for Roadmap
Fuzz testing (fuzzing) has witnessed its prosperity in detecting security flaws recently. It generates a large number of test cases and monitors the executions for defects. Fuzzing has detected thousands of bugs and vulnerabilities in various ...
Growing A Test Corpus with Bonsai Fuzzing
ICSE '21: Proceedings of the 43rd International Conference on Software Engineering

This paper presents a coverage-guided grammar-based fuzzing technique for automatically synthesizing a corpus of concise test inputs. We walk-through a case study of a compiler designed for education and the corresponding problem of generating ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2023: Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis

July 2023

1554 pages

ISBN:9798400702211

DOI:10.1145/3597926

General Chair:
René Just
University of Washington, USA
,
Program Chair:
Gordon Fraser
University of Passau, Germany

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '23

Sponsor:

SIGSOFT

ISSTA '23: 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis

July 17 - 21, 2023

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
900
Total Downloads

Downloads (Last 12 months)504
Downloads (Last 6 weeks)45

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

St. Amour LTilevich EErtl MKirsch C(2024)Toward Declarative Auditing of Java Software for Graceful Exception HandlingProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685057(90-97)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685057
Chen JYan FCai SWang SChen J(2024)FMUZZ: A Novel Greybox Fuzzing Approach based on Mutation Strategy Optimization with Byte Scheduling2024 IEEE 24th International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS62785.2024.00061(550-561)Online publication date: 1-Jul-2024
https://doi.org/10.1109/QRS62785.2024.00061
Li TZong WWang YTian HWang YCheung SKramer J(2023)Nuances are the Key: Unlocking ChatGPT to Find Failure-Inducing Tests with Differential Prompting2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE56229.2023.00089(14-26)Online publication date: 11-Sep-2023
https://doi.org/10.1109/ASE56229.2023.00089

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents