论文地址：
http://www.ieee-security.org/TC/SP2015/papers-archived/6949a725.pdf
本文发表于IEEE Security&Privacy 2015，论文的三位作者分别是Sang Kil Cha, Maverick Woo和David Brumley，三位作者均来自于卡内基梅隆大学。
一 主要内容
黑盒变异测试是现在用来在软件中找到安全问题与漏洞的最流行与有效的方法。目前fuzzing的效率与fuzzer运行时所需要的参数具有很强的关联，比如最近的研究表明fuzzer能够发现的bug数量很大程度上依赖于种子文件的质量，因此现在一个很关键的问题是如何找到这些参数的组合来在给定有限资源的条件下，让fuzzer找到最多的bug。
现有的解决这个问题的方法被称作Fuzz Configuration Scheduling，即对fuzzing的参数空间进行搜索，这个工作发表在了USENIX Security 2014上。但是参数的可行解空间可能会很大，比如Mutation Ratio（变异率r：每次变异的bit占input bit的比率），可以在[0,1]区间内选择任意实数。
对于传统的mutational fuzzing的变异率选取，常常采用两种方法，一种是指定mutation ratio，另一种是指定一个mutation ratio的区间，然后在这个区间中去进行调度。这些fuzzer都没有自适应性的变异率选取过程。本文所要研究的关键问题是，对于给定的程序，自适应性的变异率选取能否最大化fuzzer发现bug的概率（这个概率被称作failure rate，记为θ）？如果可以的话，我们能否找到这个最优的变异率。在本文中，作者首先推导出了用r计算failure rate的公式，接着求出了θ取得最大值时r对应的取值。但是，要计算最优的r的取值，需要计算input-bit之间的依赖关系，而获得这种关系需要对将要fuzz的程序做程序分析，这样对不同的输入程序都将通过分析取得最优变异率。
本文的主要贡献主要有以下几点：
1.对mutational fuzzing中的mutation ratio、 failure rate等关键参数和指标进行形式化的表述及关系推导，通过求解input-bit之间依赖关系的算法来计算最佳的变异率r，进而通过mutational fuzzing在给定资源的情况下发现最多的bug；
2.一个被称作Mutation Ratio Optimization的创新方法，用来选择一个变异率，最大化发现bug的概率；
3.设计了一个被称作SYMFUZZ的框架，实现这些技术；
4.开放了SYMFUZZ的源代码。
二 数学框架
2.1 基础概念
Hamming Distance：表示input之间不同的bit个数，用 来表示。
Definition 1：K-neighbours
NK(i)={j∈{0,1}N1| }，这个概念的意思就是说一个input(j)和input(i)的Hamming Distance是K，即有K个bit不同。
我们把μ定义为这样一个函数，它把一个test case和包含bit position的集合作为输入，然后通过反转test case中被bit position指定的位置，获得一个新的test case，比如：δ(μ(s, {3, 4}), s) = 2。
利用控制流，可以定义input-bit之间的依赖关系，当一个控制流图上的顶点u决定了另一个顶点v是否会被执行，那么我们就称v依赖于u
Definition 2：Input-bit Dependence
给定一个seed，考虑这个seed的位置x与y，如果sx依赖于sy，那么我们就记为 , 这种依赖关系的成立需要满足以下两个条件之一：
1.有一个条件分支读取了sx和sy；
2.有两个条件分支c1与c2，它们分别读取了sx和sy，且c1在控制流上依赖于c2；
上图通过CFG，对控制流上的依赖关系进行的简要阐释，下图将从代码从面阐释。
可以看出input[1]将会依赖于input[0]。
Definition 3：Dependency Bitset
对于程序p和种子s，给定一个由bit position构成的集合X，那么X的依赖集合为：
Definition 4：Mutational Fuzzing
给定一个包含N个bit的种子s，再给定一个变异率s，首先产生一个测试用例构成的集合，这个集合的元素来自于 ，其中
，接下来变异模糊测试会对这个利用这个集合中的元素进行测试。
Definition 5：Failure Rate
令 是能够让程序p产生bug的N-bit输入，给定样本空间IN（N为下标），那么定义通过随机选择能够从
中选择到元素的概率θ：
Definition 6：Buggy Bitset
给定一个程序p和一个N-bit的seed，一个buggy bitset指的是包含bit positions的集合，它是{1,2,3,…,N}的子集，且对集合中声明的bit position进行flip将会触发bug。
Definition 7：Minimum Buggy Bitset
比如有一个buggy bitset是{1,2}，但是如果只翻转第二个bit也能触发同样的bug，而再去掉其它元素将不能触发bug，那么就称{2}这个buggy bitset为minimu buggy bitset。
2.2 问题建模
现在我们通过minimum buggy bitset来计算failure rate，令