Accelerating Modern Greybox Fuzzers

The impressive growth rate of modern software projects has forced security practitioners to develop automated techniques to reduce the manual effort required to review a security-sensitive piece of software. Among these, the technique that has gained the most traction in recent years is fuzzing, which aims at triggering bugs in software by injecting unexpected, usually randomly generated, inputs. Its lack of false positives and the ease of reproducibility of the bugs it finds are two of the main reasons it enjoyed so much success in recent years. The bug finding capabilities of a fuzzer are determined by two main factors: its ability to generate test cases that are likely to be buggy and the speed at which it generates them. Novel fuzzing techniques have to strike a perfect balance between these two: being too clever usually implies lower speeds, resulting in too few test cases to be able to generate a buggy test case by chance. In this thesis, we focus on the second factor: we optimize speed in three categories of fuzzers, exploiting the peculiarities of each one to push its performance to the limit. First, we consider snapshot-based fuzzers, proposing a novel technique to optimally place snapshots in the execution trace so that redundant computation can be avoided. Then, we consider hybrid fuzzers, proposing a novel technique to schedule queries to the SMT solver which results in more executions per second because the concolic engine spends less time solving. Finally, we consider directed fuzzers, to which we apply existing performance optimizations coming from the normal fuzzing literature that have been ignored by the current state of the art. We explore the performance implications of introducing these techniques in a directed fuzzer and provide recommendations on how directed fuzzers should be developed in the future.