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

Article

MOPT: optimized mutation scheduling for fuzzers

Authors:

Raheem BeyahAuthors Info & Claims

SEC'19: Proceedings of the 28th USENIX Conference on Security Symposium

Pages 1949 - 1966

Published: 14 August 2019 Publication History

Abstract

Mutation-based fuzzing is one of the most popular vulnerability discovery solutions. Its performance of generating interesting test cases highly depends on the mutation scheduling strategies. However, existing fuzzers usually follow a specific distribution to select mutation operators, which is inefficient in finding vulnerabilities on general programs. Thus, in this paper, we present a novel mutation scheduling scheme MOPT, which enables mutation-based fuzzers to discover vulnerabilities more efficiently. MOPT utilizes a customized Particle Swarm Optimization (PSO) algorithm to find the optimal selection probability distribution of operators with respect to fuzzing effectiveness, and provides a pacemaker fuzzing mode to accelerate the convergence speed of PSO. We applied MOPT to the state of the-art fuzzers AFL, AFLFast and VUzzer, and implemented MOPT-AFL, -AFLFast and -VUzzer respectively, and then evaluated them on 13 real world open-source programs. The results showed that, MOPT-AFL could find 170% more security vulnerabilities and 350% more crashes than AFL. MOPT-AFLFast and MOPT-VUzzer also outperform their counterparts. Furthermore, the extensive evaluation also showed that MOPT provides a good rationality, compatibility and steadiness, while introducing negligible costs.

References

[1]

J. Wang, B. Chen, L. Wei, and Y. Liu, "Skyfire: Datadriven seed generation for fuzzing," in S&P, 2017.

[2]

M. Woo, S. K. Cha, S. Gottlieb, and D. Brumley, "Scheduling black-box mutational fuzzing," in CCS, 2013.

Digital Library

[3]

A. Rebert, S. K. Cha, T. Avgerinos, J. Foote, D. Warren, G. Grieco, and D. Brumley, "Optimizing seed selection for fuzzing." in USENIX, 2014.

Digital Library

[4]

S. Gan, C. Zhang, X. Qin, X. Tu, K. Li, Z. Pei, and Z. Chen, "Collafl: Path sensitive fuzzing," in S&P, 2018.

[5]

M. Böhme, V.-T. Pham, and A. Roychoudhury, "Coverage-based greybox fuzzing as markov chain," in CCS, 2016.

Digital Library

[6]

S. Rawat, V. Jain, A. Kumar, L. Cojocar, C. Giuffrida, and H. Bos, "Vuzzer: Application-aware evolutionary fuzzing," in NDSS, 2017.

[7]

K. Böttinger, P. Godefroid, and R. Singh, "Deep reinforcement fuzzing," arXiv preprint arXiv:1801.04589, 2018.

[8]

W. Drozd and M. D. Wagner, "Fuzzergym: A competitive framework for fuzzing and learning," arXiv preprint arXiv:1807.07490, 2018.

[9]

P. Chen and H. Chen, "Angora: Efficient fuzzing by principled search," in S&P, 2018.

[10]

Y. Li, B. Chen, M. Chandramohan, S.-W. Lin, Y. Liu, and A. Tiu, "Steelix: program-state based binary fuzzing," in FSE, 2017.

Digital Library

[11]

H. Peng, Y. Shoshitaishvili, and M. Payer, "T-fuzz: fuzzing by program transformation," in S&P, 2018.

[12]

W. Xu, S. Kashyap, C. Min, and T. Kim, "Designing new operating primitives to improve fuzzing performance," in CCS, 2017.

Digital Library

[13]

I. Haller, A. Slowinska, M. Neugschwandtner, and H. Bos, "Dowsing for overflows: a guided fuzzer to find buffer boundary violations." in USENIX, 2013.

Digital Library

[14]

S. K. Cha, M. Woo, and D. Brumley, "Program adaptive mutational fuzzing," in S&P, 2015.

Digital Library

[15]

N. Stephens, J. Grosen, C. Salls, A. Dutcher, R. Wang, J. Corbetta, Y. Shoshitaishvili, C. Kruegel, and G. Vigna, "Driller: Augmenting fuzzing through selective symbolic execution." in NDSS, 2016.

[16]

"American Fuzzy Lop," http://lcamtuf.coredump.cx/afl/.

[17]

K. Serebryany, "Continuous fuzzing with libfuzzer and addresssanitizer," in SecDev, 2016.

[18]

R. Swiecki, "Honggfuzz," Available online at: http://code.google.com/p/honggfuzz, 2016.

[19]

R. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in MHS, 1995.

[20]

C. Lyu, S. Ji, C. Zhang, Y. Li, W.-H. Lee, Y. Song and R. Beyah, "MOPT: Optimized Mutation Scheduling for Fuzzers, Technical Report," https://github.com/puppet-meteor/MOpt-AFL.

[21]

M. Böhme, V.-T. Pham, M.-D. Nguyen, and A. Roychoudhury, "Directed greybox fuzzing," in CCS, 2017.

Digital Library

[22]

T. Petsios, J. Zhao, A. D. Keromytis, and S. Jana, "Slowfuzz: Automated domain-independent detection of algorithmic complexity vulnerabilities," in CCS, 2017.

Digital Library

[23]

T. Petsios, A. Tang, S. Stolfo, A. D. Keromytis, and S. Jana, "Nezha: Efficient domain-independent differential testing," in S&P, 2017.

[24]

"AddressSanitizer," http://clang.llvm.org/docs/AddressSanitizer.html.

[25]

G. Klees, A. Ruef, B. Cooper, S. Wei, and M. Hicks, "Evaluating fuzz testing," in CCS, 2018.

Digital Library

[26]

"Common Vulnerability Scoring System (CVSS)," https://www.first.org/cvss.

[27]

"Cve details," https://www.cvedetails.com/.

[28]

B. Dolangavitt, P. Hulin, E. Kirda, T. Leek, A. Mambretti, W. Robertson, F. Ulrich, and R. Whelan, "Lava: Large-scale automated vulnerability addition," in S&P, 2016.

[29]

I. Yun, S. Lee, M. Xu, Y. Jang, and T. Kim, "Qsym: A practical concolic execution engine tailored for hybrid fuzzing," in USENIX, 2018.

Digital Library

[30]

"p value," https://en.wikipedia.org/wiki/P-value.

[31]

Y. Benjamini and Y. Hochberg, "Controlling the false discovery rate: a practical and powerful approach to multiple testing," J R STAT SOC B, 1995.

[32]

T. Wang, T. Wei, G. Gu, and W. Zou, "Taintscope: A checksum-aware directed fuzzing tool for automatic software vulnerability detection," in S&P, 2010.

Digital Library

[33]

Y. Li, S. Ji, C. Lyu, Y. Chen, J. Chen, Q. Gu, and C.Wu, "V-fuzz: Vulnerability-oriented evolutionary fuzzing," arXiv preprint arXiv:1901.01142, 2019.

[34]

C. Holler, K. Herzig, and A. Zeller, "Fuzzing with code fragments." in USENIX, 2012.

Digital Library

[35]

K. Dewey, J. Roesch, and B. Hardekopf, "Language fuzzing using constraint logic programming," in ASE, 2014.

Digital Library

[36]

P. Godefroid, H. Peleg, and R. Singh, "Learn&fuzz: Machine learning for input fuzzing," in ASE, 2017.

Digital Library

[37]

J. Corina, A. Machiry, C. Salls, Y. Shoshitaishvili, S. Hao, C. Kruegel, and G. Vigna, "Difuze: interface aware fuzzing for kernel drivers," in CCS, 2017.

Digital Library

[38]

H. Han and S. K. Cha, "Imf: Inferred model-based fuzzer," in CCS, 2017.

Digital Library

[39]

W. You, P. Zong, K. Chen, X. Wang, X. Liao, P. Bian, and B. Liang, "Semfuzz: Semantics-based automatic generation of proof-of-concept exploits," in CCS, 2017.

Digital Library

[40]

H. Chen, Y. Xue, Y. Li, B. Chen, X. Xie, X. Wu, and Y. Liu, "Hawkeye: Towards a desired directed grey-box fuzzer," in CCS, 2018.

Digital Library

[41]

N. Nichols, M. Raugas, R. Jasper, and N. Hilliard, "Faster fuzzing: Reinitialization with deep neural models," arXiv preprint arXiv:1711.02807, 2017.

[42]

C. Lyu, S. Ji, Y. Li, J. Zhou, J. Chen, P. Zhou, and J. Chen, "Smartseed: Smart seed generation for efficient fuzzing," arXiv preprint arXiv:1807.02606, 2018.

Cited By

Xu HJiang ZWang YFan SXu SXie PFu SPayer MLuo BLiao XXu JKirda ELie D(2024)Fuzzing JavaScript Engines with a Graph-based IRProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690336(3734-3748)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690336
Wang KChen MHe LSu PCai YChen JZhang BFeng CTang CLuo BLiao XXu JKirda ELie D(2024)OSmart: Whitebox Program Option FuzzingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690228(705-719)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690228
Vikram VLaybourn ILi ANair NOBrien KSanna RPadhye RJust RFraser G(2023)Guiding Greybox Fuzzing with Mutation TestingProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598107(929-941)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598107
Show More Cited By

MOPT: optimized mutation scheduling for fuzzers
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

A Static Approach to Prioritizing JUnit Test Cases

Test case prioritization is used in regression testing to schedule the execution order of test cases so as to expose faults earlier in testing. Over the past few years, many test case prioritization techniques have been proposed in the literature. Most ...
Spartan: a spectral and entropy-based partial-scan and test point insertion algorithm
Faster mutation testing inspired by test prioritization and reduction
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis

Mutation testing is a well-known but costly approach for determining test adequacy. The central idea behind the approach is to generate mutants, which are small syntactic transformations of the program under test, and then to measure for a given test ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SEC'19: Proceedings of the 28th USENIX Conference on Security Symposium

August 2019

2002 pages

ISBN:9781939133069

Program Chairs:
Nadia Heninger
University of Pennsylvania
,
Patrick Traynor
University of Florida

Sponsors

Google Inc.
IBMR: IBM Research
Microsoft: Microsoft
Intel: Intel
Facebook: Facebook

Publisher

USENIX Association

United States

Publication History

Published: 14 August 2019

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xu HJiang ZWang YFan SXu SXie PFu SPayer MLuo BLiao XXu JKirda ELie D(2024)Fuzzing JavaScript Engines with a Graph-based IRProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690336(3734-3748)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690336
Wang KChen MHe LSu PCai YChen JZhang BFeng CTang CLuo BLiao XXu JKirda ELie D(2024)OSmart: Whitebox Program Option FuzzingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690228(705-719)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690228
Vikram VLaybourn ILi ANair NOBrien KSanna RPadhye RJust RFraser G(2023)Guiding Greybox Fuzzing with Mutation TestingProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598107(929-941)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598107
Zhao YWang XZhao LCheng YYin H(2022)Alphuzz: Monte Carlo Search on Seed-Mutation Tree for Coverage-Guided FuzzingProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3564660(534-547)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3564625.3564660
Zhang KXiao XZhu XSun RXue MWen SDwyer MDamian DZeller A(2022)Path transitions tell moreProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510063(1658-1668)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510063
Zhang TJiang YGuo RZheng XLu H(2020)A Survey of Hybrid Fuzzing based on Symbolic ExecutionProceedings of the 2020 International Conference on Cyberspace Innovation of Advanced Technologies10.1145/3444370.3444570(192-196)Online publication date: 4-Dec-2020
https://dl.acm.org/doi/10.1145/3444370.3444570
Hazimeh AHerrera APayer M(2020)MagmaProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283344:3(1-29)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1145/3428334

View Options

View options

Media

Figures

Other

Tables

View Table of Contents