SHF: Small: Xsmith, A Configurable Generator of Highly Effective Fuzz Testers

点击翻译按钮获取中文摘要

This project is developing new techniques for the creation of highly effectivefuzz testers, also known as "fuzzers," for programming language compilers andinterpreters. Fuzz testing is an automatic and low-cost technique for findingdefects in software systems. A fuzzer randomly creates test inputs for asoftware system; a fuzzer is effective if it can continually create test casesthat reveal defects throughout the system under test. It is difficult tocreate effective fuzzers for programming language compilers and interpretersbecause these systems have highly structured inputs, but it is important thatsuch fuzzers exist. Programming language implementations are critical softwareinfrastructure: defects in compilers and interpreters can potentially havegreat costs in terms of software correctness and reliability, humanproductivity, and computer security. This project seeks to reduce the time andhuman effort needed to create sophisticated fuzzers for programming languageimplementations. In so doing, this project is expected to advance the state ofthe art in random software testing, improve the quality of several programminglanguage implementations selected for study, and produce new open-sourcesoftware tools that programmers can use to develop new and more effective fuzztesters.The techniques developed by this project will be embodied in a new generator offuzz testers, called Xsmith. Xsmith will generate language fuzzers fromspecifications and thus reduce the time and effort required to create fuzzers.More importantly, Xsmith will inject sophisticated program-generationtechniques into the language fuzzers it creates. This project will investigatethree techniques in particular. This first is generation-time analysis,intended to allow Xsmith-derived fuzzers to create output that is both complexand meaningful. The second is feature subsetting, intended to increase thelikelihood that Xsmith-derived fuzzers will output bug-triggering testprograms. The third is iterative refinement, intended to further diversify theoutputs from Xsmith-derived fuzzers. The project participants will use Xsmithto create fuzz testers for a varied set of programming languages. Wherepossible, the bug-finding power of Xsmith-derived fuzzers will be compared tothat of existing fuzzers: quantitatively, in terms of the number ofidentifiably unique defects found within a fixed test-time budget, andqualitatively, in terms of the kinds of defects uncovered. This evaluationwill allow the investigators to assess the impact of the techniques embodied inXsmith, both individually and collectively, over a range of programminglanguage implementations. Xsmith will be successful if it permits highlyeffective fuzz testers to be constructed with significantly less ad hoc code,and thus significantly less effort, than if they had been constructed fromscratch.