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

这个项目正在开发新的技术，用于创建高效的模糊测试器，也被称为“模糊器”，用于编程语言编译器和解释器。 模糊测试是一种自动化的、低成本的软件缺陷发现技术。 模糊器随机地为软件系统创建测试输入;如果模糊器能够不断地创建测试用例，从而揭示整个被测系统的缺陷，那么它就是有效的。 很难为编程语言编译器和解释器创建有效的模糊器，因为这些系统具有高度结构化的输入，但这种模糊器的存在很重要。 编程语言实现是关键的软件基础设施：编译器和解释器中的缺陷可能会在软件正确性和可靠性，人类生产力和计算机安全方面造成巨大损失。 该项目旨在减少为编程语言实现创建复杂模糊器所需的时间和人力。 通过这样做，该项目有望推进随机软件测试的最新技术，提高几种编程语言实现的质量，并产生新的开放源代码软件工具，程序员可以使用这些工具来开发新的和更有效的模糊测试器。该项目开发的技术将体现在一个新的模糊测试器生成器中，称为Xsmith。 Xsmith将从规范生成语言模糊器，从而减少创建模糊器所需的时间和精力。更重要的是，Xsmith将把复杂的程序生成技术注入到它创建的语言模糊器中。 本项目将特别研究三种技术。 第一个是生成时分析，旨在允许Xsmith派生的模糊器创建既复杂又有意义的输出。 第二个是特征子集化，旨在增加Xsmith衍生的模糊器将输出触发bug的测试程序的可能性。 第三个是迭代细化，旨在进一步多样化Xsmith衍生模糊器的输出。 项目参与者将使用Xsmith为各种编程语言创建模糊测试器。 在可能的情况下，Xsmith衍生的模糊器的缺陷发现能力将与现有的模糊器进行比较：定量地，在固定的测试时间预算内发现的可识别的独特缺陷的数量方面，定性地，在发现的缺陷种类方面。 这一评估将使研究人员能够评估Xsmith中体现的技术在一系列编程语言实现中的影响，无论是单独的还是集体的。 如果Xsmith允许高效的模糊测试器用更少的特别代码来构建，那么它将是成功的，因此比从头开始构建要少得多。

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.