# Pythia: Grammar-Based Fuzzing of REST APIs with Coverage-guided Feedback and Learning-based Mutations

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2020.

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

- [The Threat of Offensive AI to Organizations](https://mlsanity.com/paper/2106.15764/) (2021)
- [Multi-Agent Penetration Testing AI for the Web](https://mlsanity.com/paper/2508.20816/) (2025)
- [Neural Network Guided Evolutionary Fuzzing for Finding Traffic Violations of Autonomous Vehicles](https://mlsanity.com/paper/2109.06126/) (2021)
- [Automating a Complete Software Test Process Using LLMs: An Automotive Case Study](https://mlsanity.com/paper/2502.04008/) (2025)
- [APIRL: Deep Reinforcement Learning for REST API Fuzzing](https://mlsanity.com/paper/2412.15991/) (2024)

## Abstract (arXiv)

This paper introduces Pythia, the first fuzzer that augments grammar-based fuzzing with coverage-guided feedback and a learning-based mutation strategy for stateful REST API fuzzing. Pythia uses a statistical model to learn common usage patterns of a target REST API from structurally valid seed inputs. It then generates learning-based mutations by injecting a small amount of noise deviating from common usage patterns while still maintaining syntactic validity. Pythia's mutation strategy helps generate grammatically valid test cases and coverage-guided feedback helps prioritize the test cases that are more likely to find bugs. We present experimental evaluation on three production-scale, open-source cloud services showing that Pythia outperforms prior approaches both in code coverage and new bugs found. Using Pythia, we found 29 new bugs which we are in the process of reporting to the respective service owners.