# Matryoshka: Fuzzing Deeply Nested Branches

arXiv: https://arxiv.org/abs/1905.12228 · HTML: https://mlsanity.com/paper/1905.12228/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

## Built on by (most cited first, 4 of 4)

- [Exploring the Limits of ChatGPT in Software Security Applications](https://mlsanity.com/paper/2312.05275/) (2023)
- [UniTSyn: A Large-Scale Dataset Capable of Enhancing the Prowess of Large Language Models for Program Testing](https://mlsanity.com/paper/2402.03396/) (2024)
- [Content Fuzzing for Escaping Information Cocoons on Digital Social Media](https://mlsanity.com/paper/2604.05461/) (2026)
- [DeepGo: Predictive Directed Greybox Fuzzing](https://mlsanity.com/paper/2507.21952/) (2025)

## Abstract (arXiv)

Greybox fuzzing has made impressive progress in recent years, evolving from heuristics-based random mutation to approaches for solving individual path constraints. However, they have difficulty solving path constraints that involve deeply nested conditional statements, which are common in image and video decoders, network packet analyzers, and checksum tools. We propose an approach for addressing this problem. First, we identify all the control flow-dependent conditional statements of the target conditional statement. Next, we select the data flow-dependent conditional statements. Finally, we use three strategies to find an input that satisfies all conditional statements simultaneously. We implemented this approach in a tool called Matryoshka and compared its effectiveness on 13 open source programs against other state-of-the-art fuzzers. Matryoshka found significantly more unique crashes than AFL, QSYM, and Angora. We manually classified those crashes into 41 unique new bugs, and obtained 12 CVEs. Our evaluation also uncovered the key technique contributing to Matryoshka's impressive performance: it collects only the nesting constraints that may cause the target conditional statements unreachable, which greatly simplifies the constraints that it has to solve.