Make out like a (Multi-Armed) Bandit: Improving the Odds of Fuzzer Seed Scheduling with T-Scheduler

Fuzzing is an industry-standard software testing technique that uncovers bugs in a target program by executing it with mutated inputs. Over the lifecycle of a fuzzing campaign, the fuzzer accumulates inputs inducing new and interesting target behaviors, drawing from these inputs for further mutation and generation of new inputs. This rapidly results in a large pool of inputs to select from, making it challenging to quickly determine the "most promising" input for mutation. Reinforcement learning (RL) provides a natural solution to this seed scheduling problem---a fuzzer can dynamically adapt its selection strategy by learning from past results. However, existing RL approaches are (a) computationally expensive (reducing fuzzer throughput), and/or (b) require hyperparameter tuning (reducing generality across targets and input types). To this end, we propose T-Scheduler, a seed scheduler built upon multi-armed bandit theory to automatically adapt to the target. Notably, our formulation does not require the user to select or tune hyperparameters and is therefore easily generalizable across different targets. We evaluate T-Scheduler over 35 CPU-yr fuzzing effort, comparing it to 11 state-of-the-art schedulers. Our results show that T-Scheduler improves on these 11 schedulers on both bug-finding and coverage-expansion abilities.