SandPuppy: Deep-State Fuzzing Guided by Automatic Detection of State-Representative Variables

Current state-of-the-art automated fuzzing approaches cannot explore deep program-states without human assistance. Recently, Ijon allowed humans to provide code-annotations on the target to expose program state to the fuzzer. However, this requires a human to read, understand, and annotate the program source, which limits scalability and applicability. In this paper we introduce SandPuppy, a technique that automatically identifies potential state-representative variables and applies Ijon-style instrumentation to expose corresponding state to the fuzzer. To identify these variables and their semantics, SandPuppy collects runtime variable-value traces from an initial fuzzing run and analyzes them along with the program source to instrument the program and expose internal state to the fuzzer. This process repeats and identifies additional variables, allowing the exploration of deeper states. We evaluated SandPuppy against synthetic and real-world targets representing various fuzzing-challenges. The results show that SandPuppy can automatically solve problems that purely coverage-based approaches cannot solve without assistance from human experts. For example, SandPuppy can automatically play and solve levels of Super Mario Bros, maze programs, and identify complex, deep states in real-world targets such as libtpms, resulting from combinations of previously identified states. Evaluating SandPuppy on real-world targets such as jsoncpp, libtpms, PcapPlusPlus, and readelf demonstrates that SandPuppy generally improves coverage compared to AFL, AFL++, LafIntel, RedQueen, SGFuzz, and Ferry. In all, SandPuppy identified ten unknown vulnerabilities in PcapPlusPlus and one unknown vulnerability in dmg2img.