IJON: Exploring Deep State Spaces via Fuzzing

### Overview Academic research on fuzzing predominantly focuses on fully automated approaches such as AFL and libFuzzer. While automation simplifies testing across diverse security scenarios, security practitioners often require finer control over fuzzer behavior. IJON (presented phonetically as Ejon) introduces an approach where human experts guide fuzzers using lightweight annotations. By combining standard code coverage feedback with selective value feedback on specific data points within the program's state space, IJON enables fuzzers to explore deep state spaces without becoming overwhelmed by state noise.

### Key Topics - **Equivalence Classes and Feedback Limitations**: Modern fuzzers divide the input space into equivalence classes based on code coverage, discarding mutations that produce no new coverage. When equivalence classes are too vast—such as in complex state machines or arithmetic constraints—mutations fail to reach interesting states. - **Selective Value Feedback**: Instead of tracking all program state (which causes noise and state explosion) or relying purely on code coverage, analysts add inline annotations to direct the fuzzer toward specific values or exploration goals. - **Feedback Primitives**: IJON introduces feedback primitives such as state-tracking annotations and optimization feedback (e.g., maximizing coordinates or loop counters, minimizing arithmetic differences). - **Limitations in Interactive Applications**: Long-running or interactive inputs face a severe cubic disadvantage: input queues expand, promising inputs become longer (leading to fewer mutations on critical bytes), and individual executions slow down drastically.

### Technical Details - **Maze Solving**: In a modified maze game allowing revisiting of board positions, standard fuzzers and KLEE fail because code coverage is exhausted after pressing W, S, A, and D once. A one-line IJON annotation directing the fuzzer to treat new (X, Y) coordinate combinations as new coverage enabled AFL to solve the maze in seconds. - **Protocol and Format Parsing (libpng)**: In stateful parsing (like FTP or chunk-based formats like PNG), identical code executes repeatedly across states. In `libpng`, tracking the last four observed chunk headers created artificial coverage that allowed AFL to discover a bug requiring a specific sequence of chunks without needing a full file format specification. - **Maximization and Optimization**: In an integer factorization example, minimizing the difference between equation sides guided the fuzzer toward solutions. Applied to Super Mario Bros., maximizing the player's X coordinate turned AFL into an effective speed-running bot. - **Vulnerability Discovery & CGC Evaluation**: An inline annotation targeting a `malloc` call quickly confirmed an integer overflow resulting in a zero-sized allocation. Evaluating undefeated DARPA Cyber Grand Challenge (CGC) binaries (via Trail of Bits' x86 port), IJON solved a third of inspected challenges by removing checksum checks during fuzzing and using AFL crash exploration mode with maximization annotations—replicating T-Fuzz results without symbolic execution. Other solved cases involved maximizing loop counters, single pointers, or bypassing string comparisons.

### Takeaways IJON demonstrates that minimal, human-in-the-loop annotations can bridge the gap where fully automated coverage-guided fuzzers fail. It also highlights open challenges for automated fuzzing, including long-running interactive targets, loop counters, and deep checksum logic.