REDQUEEN: Fuzzing with Input-to-State Correspondence

被引:152
作者
Aschermann, Cornelius [1 ]
Schumilo, Sergej [1 ]
Blazytko, Tim [1 ]
Gawlik, Robert [1 ]
Holz, Thorsten [1 ]
机构
[1] Ruhr Univ Bochum, Bochum, Germany
来源
26TH ANNUAL NETWORK AND DISTRIBUTED SYSTEM SECURITY SYMPOSIUM (NDSS 2019) | 2019年
基金
欧盟地平线“2020”;
关键词
D O I
10.14722/ndss.2019.23371
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Automated software testing based on fuzzing has experienced a revival in recent years. Especially feedback-driven fuzzing has become well-known for its ability to efficiently perform randomized testing with limited input corpora. Despite a lot of progress, two common problems are magic numbers and (nested) checksums. Computationally expensive methods such as taint tracking and symbolic execution are typically used to overcome such roadblocks. Unfortunately, such methods often require access to source code, a rather precise description of the environment (e.g., behavior of library calls or the underlying OS), or the exact semantics of the platform's instruction set. In this paper, we introduce a lightweight, yet very effective alternative to taint tracking and symbolic execution to facilitate and optimize state-of-the-art feedback fuzzing that easily scales to large binary applications and unknown environments. We observe that during the execution of a given program, parts of the input often end up directly (i.e., nearly unmodified) in the program state. This input-to-state correspondence can be exploited to create a robust method to overcome common fuzzing roadblocks in a highly effective and efficient manner. Our prototype implementation, called REDQUEEN, is able to solve magic bytes and (nested) checksum tests automatically for a given binary executable. Additionally, we show that our techniques outperform various state-of-the-art tools on a wide variety of targets across different privilege levels (kernel-space and userland) with no platform-specific code. REDQUEEN is the first method to find more than 100% of the bugs planted in LAvA-M across all targets. Furthermore, we were able to discover 65 new bugs and obtained 16 CVEs in multiple programs and OS kernel drivers. Finally, our evaluation demonstrates that REDQUEEN is fast, widely applicable and outperforms concurrent approaches by up to three orders of magnitude.
引用
收藏
页数:15
相关论文
共 38 条
  • [1] [Anonymous], GEN PURPOSE FUZZER
  • [2] [Anonymous], 2008, P NDSS
  • [3] A Hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering
    Arcuri, Andrea
    Briand, Lionel
    [J]. SOFTWARE TESTING VERIFICATION & RELIABILITY, 2014, 24 (03) : 219 - 250
  • [4] Bastani O, 2017, ACM SIGPLAN NOTICES, V52, P95, DOI [10.1145/3140587.3062349, 10.1145/3062341.3062349]
  • [5] Bellard F, 2005, USENIX Association Proceedings of the FREENIX/Open Source Track, P41
  • [6] Bohme Marcel, 2016, IEEE T SOFTWARE ENG
  • [7] Bruening Derek, 2001, ACM WORKSH FEEDB DIR
  • [8] Cadar C., 2008, P OP SYST DES IMPL, P209
  • [9] Program-Adaptive Mutational Fuzzing
    Cha, Sang Kil
    Woo, Maverick
    Brumley, David
    [J]. 2015 IEEE SYMPOSIUM ON SECURITY AND PRIVACY SP 2015, 2015, : 725 - 741
  • [10] Unleashing MAYHEM on Binary Code
    Cha, Sang Kil
    Avgerinos, Thanassis
    Rebert, Alexandre
    Brumley, David
    [J]. 2012 IEEE SYMPOSIUM ON SECURITY AND PRIVACY (SP), 2012, : 380 - 394