Saffron: Adaptive Grammar-based Fuzzing for Worst-Case Analysis
Saffron: Adaptive Grammar-based Fuzzing for Worst-Case Analysis
复制标题
DOI：
10.1145/3364452.3364455
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
X. Le;C. Păsăreanu;Rohan Padhye;David Lo;W. Visser;Koushik Sen
中科院分区：
文献类型：
--
作者：
X. Le;C. Păsăreanu;Rohan Padhye;David Lo;W. Visser;Koushik Sen
最近，绒毛测试已获得了大量专门针对该地区的基础。通常，模糊器采用一组种子输入并利用随机突变，以不断提高成本的投入，例如程序代码覆盖范围，发现漏洞或错误。遵循这种方法，模糊非常擅长生成获得高覆盖范围的非结构化输入。但是，当输入是构造时，模糊不清的效果较小，说它们符合输入语法。由于随机突变的性质，这种常见的模糊实践产生的大量投入通常会不利地阻碍了模糊器对语法感知应用的有效性和效率。当目标不仅要实现与其他成本指标有关的ND复杂漏洞（例如应用程序中的大量资源消耗）时，测试问题变得更加困难。我们建议一种基于自适应语法的藏红花方法，以有效，有效地生成在程序中揭示昂贵执行的输入。藏红花作为输入用户提供的语法，该语法描述了分析程序的输入空间，并使用它来生成测试输入。藏红花假定语法描述是近似的，因为精确描述输入程序空间通常很困难，因为程序可能会因解析错误而接受意外输入。然而，这些输入可能会揭示最坏情况的复杂性漏洞。然后，藏红花的新颖性是双重的：（1）鉴于用户提供的语法，藏红花试图发现该程序是否接受提供的语法之外的意外输入，如果是这样，它可以通过语法突变进行修复语法。修复的语法是应用程序接受的实际输入的特定阳离子。 （2）基于RE NED语法，它生成具体测试输入。首先，它以语法中的每个生产规则处理，其概率是用于生成混凝土输入。然后，它通过增加用于生成提高成本的输入的规则的概率来适应概率。评估结果表明，藏红花明显胜过最先进的基线。
Fuzz testing has been gaining ground recently with substantial e orts devoted to the area. Typically, fuzzers take a set of seed inputs and leverage random mutations to continually improve the inputs with respect to a cost, e.g. program code coverage, to discover vulnerabilities or bugs. Following this methodology, fuzzers are very good at generating unstructured inputs that achieve high coverage. However fuzzers are less e ective when the inputs are structured, say they conform to an input grammar. Due to the nature of random mutations, the overwhelming abundance of inputs generated by this common fuzzing practice often adversely hinders the effectiveness and efficiency of fuzzers on grammar-aware applications. The problem of testing becomes even harder, when the goal is not only to achieve increased code coverage, but also to nd complex vulnerabilities related to other cost measures, say high resource consumption in an application. We propose Saffron an adaptive grammar-based fuzzing approach to effectively and efficiently generate inputs that expose expensive executions in programs. Saffron takes as input a user-provided grammar, which describes the input space of the program under analysis, and uses it to generate test inputs. Saffron assumes that the grammar description is approximate since precisely describing the input program space is often difficult as a program may accept unintended inputs due to e.g., errors in parsing. Yet these inputs may reveal worst-case complexity vulnerabilities. The novelty of Saffron is then twofold: (1) Given the user-provided grammar, Saffron attempts to discover whether the program accepts unexpected inputs outside of the provided grammar, and if so, it repairs the grammar via grammar mutations. The repaired grammar serves as a speci cation of the actual inputs accepted by the application. (2) Based on the re ned grammar, it generates concrete test inputs. It starts by treating every production rule in the grammar with equal probability of being used for generating concrete inputs. It then adaptively re nes the probabilities along the way by increasing the probabilities for rules that have been used to generate inputs that improve a cost, e.g., code coverage or arbitrary user-de ned cost. Evaluation results show that Saffron signi cantly outperforms state-of-the-art baselines.