  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.
