REDQUEEN: Fuzzing with Input-to-State Correspondence

By Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, Thorsten Holz. Network and Distributed System Security Symposium, 2019

431 citations recorded by the source corpus.

—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 efﬁciently 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 unmodiﬁed) 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 efﬁcient manner. Our prototype implementation, called R EDQUEEN , 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-speciﬁc code. R EDQUEEN is the ﬁrst method to ﬁnd more than 100% of the bugs planted in L AVA -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 R EDQUEEN is fast, widely applicable and outperforms concurrent approaches by up to three orders of magnitude.

Subfields: Information Systems, Software, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f51ee4f4cb3b3d28b8ff3bbcc2628c3e94352726

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Software

In Signal Processing

Citations in the corpus

AFL++ : Combining Incremental Steps of Fuzzing Research (2020, methodology): “Recently, REDQUEEN [5], based on KAFL [36], explored the possibility to bypass hard comparisons and checksum checks, like other previous works in literature [35] [12] [33] [44], but without the use of expensive techniques like taint tracking [46] or symbolic execution [6, 37].”
The Art, Science, and Engineering of Fuzzing: A Survey (2018, background): “FairFuzz [141] H# ✓ ✓ ✓† H#† ✓ ✓ ✓ go-fuzz [225] H# ✓ ✓ ✓ ✓ ✓ ✓ H# ✓ Hawkeye [56] H# ✓ ✓ ✓ ✓ H# ✓ ✓ honggfuzz [213] H# ✓ ✓ ✓ kAFL [191] H# ✓ ✓ LibFuzzer [9] H# ✓ ✓ ✓ ✓ ✓ ✓ MagicFuzzer [50] H# ✓ ✓ ✓ Nautilus [25] H# ✓ ✓ ✓ H# ✓ ✓ RaceFuzzer [197] H# ✓ ✓ ✓ RedQueen [26] H# ✓ ✓ H# ✓”
Fuzzing: A Survey for Roadmap (2022, methodology): “Many coverage-guided fuzzers [7, 23, 116, 177, 204, 206] implement a bitmap to provide fuzzingwith the knowledge of edge coverage.”