Fuzzy testing or fuzzing is a technique for finding software vulnerabilities. Fuzzing works by feeding quasi-random, auto-generated input sequences to a target program and searching for failures. Fuzzers find inputs that trigger bugs; however, understanding those bugs is easier when extraneous data is removed to the extent possible. Extraneous data is removed by bisection, which is typically a serial procedure, e.g., doesn’t advance without knowing the result of the previous step. This makes test case optimization slow, sometimes taking hours to complete while CPU cores sit idle.
This disclosure describes techniques that parallelize the bisection procedure, e.g., by speculatively executing test cases steps ahead of the current position of the bisection procedure. Test results often become known by the time the bisection procedure reaches a certain step, which substantially accelerates testing.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Ormandy, Tavis, "Parallelizing tests with pessimistic speculative execution", Technical Disclosure Commons, (February 13, 2019)