paper

Angora: Efficient Fuzzing by Principled Search

Angora: Efficient Fuzzing by Principled Search

0x00 解决路径问题的五种技术

  1. 上下文敏感路径覆盖 （像AFL这种都是基于bitmap的edge计数，并不细分edge的上下文）

  2. 关于taint analysis 确定 input 和 path constraints之间的映射。

  3. 梯度下降算法 作用在 input mutate(ion)

  4. input的结构推导 （shape => 结构， type => 结构里面字段）

  5. input长度的探索方法

0x01 Something interesting

上下文分支敏感的分支统计

通常情况下我们的分支记录在有向图CFG上来完成，通过执行过程中对经过有向边edge进行计数，这里会丢失一些东西，理想情况下，在CFG上记录一条完整的分支，应该是edges的一个拓扑排序 ,这里变成了单纯的edge计数。作者并没有对这里进行改进，同样还是edge计数，但是他们把相同的edge，置于不同的上下文当作两个不同的edge，这里的上下文特指执行当前edge的函数调用栈。这样在原来计数的基础上提出了更细的计数对象，在一定程度能更细致的区别执行过程中edge的变化。（这些理解只看原文，其实有一点难理解，需要具体的看一下Angora中LLVM Pass过程）

文章在这里用一个例子说明问题，但是这个例子我觉得并不好，作者认为原有的edge计数并不能区别输入为10和01的区别，实际上是可以区别的：

image-20201009104051280

10: L3:true;L4:false;L3:false;L10:true; 01: L3:false:L10:true;L3:true:L4:true;L5:(true|false);

两次执行走的分支情况，在01下是其实触发了新的路径，会多出一个L5分支记录，原文说两次都触发执行了L4，L10会被认为没有触发新路径。但是01的时候是触发了L5。 f

注意label %5这个基本块，01是会触发label %5到label %8这条边的。所以这个例子实际上在这里不合适。那在这里什么样的例子应该合适呢？应该是确保走过相同的edge的，不同上下文带来的影响。我能想到的唯一改变是下列这种情况:

1
2
3
4
5
6
7
8
9
10
void f(int x){
  ...
}

void main(){
  if(input()=='111'){
    f(input());
    f(input());
  }
}

加入context以后，因为L7和L8,处于不同callside,但是两者调用f,假设经过的edge一样，会导致在f,会多出一倍的edge元素，就像我前面说的，可能以前某个edge计数为2，可能现在被拆分成了两个不同的edge。在某种程度上改变了AFL中的edge计数的feature，可能变得更“敏感”一些了。但是我很难去推演它的这种”敏感“，到底能带来什么？我想要知道这种形式的”敏感“，是否可以孤身存在，而不对其他东西产生影响？这些东西于我而言，现在还是难以解释。

字节粒度的污点分析 （没有涉及taint rules）

文中没有细讲taint的过程，而是主要讲了一下taint过程中的污点表示，taint存在的意义是为了将输入和路径条件建立映射关系，在mutating阶段能更好的去解决路径条件。

定义：标签 表示输入input中的哪些字节会流入变量 。通常 用位向量来表示， 会随着输入的大小线性增长。为了应对large input，文中构造了一个数据结构，来存储和查询 ：

  1. Binary tree：（ 代表一个位向量， 代表位向量的长度，长度概念应用树里面，就是指结点的高度）每一个位向量 ,都可以用这个树上的高度为 的节点 唯一表示，从根节点root到 路径上的节点依次展开为 。其中的每个结点都一个指向它父结点的指针，这样可以从 开始顺着树回溯遍历得到完整 。

  2. Look-up table: 表里存储着 , 即保存着指向 Binary tree里面结点的指针。

    画了一个图，方便理解和记忆：

    binary_tree1

插入操作： 1. 去掉 结尾所有的0。 2. 遵循Binary tree策略，用 去遍历Binary tree，如果 ,则follow左子结点，反之亦然，如果子结点不存在则创建结点。 3. 把 存储到树上最后一个visited的结点。

注意到这个算法只在生产新结点的时候，插入 ，所以某个结点如果存在 则后面都是不会发生改变的。我计算得到的空间复杂度跟原文有一定区别,原文是 ,我在计算最坏复杂度时得到的是 . Maybe i am wrong,who know!

基于梯度下降的搜索算法

目标是解决路径，让路径条件满足某种要求，我们从最简单的条件出发，某个二元运算，和两个基本变量：我用 泛指所有可能出现的二元运算，基本变量用 , 表示： 文中尝试将求解约束转化成最优化问题，所以需要让上面的问号变成一个具体的值，而不是通常情况下的 ，文中做一个漂亮的转换。

image-20201010112614754

将二元运算转化成了具体函数，函数值间接表示约束的成立。通过合适的函数表示，将所有的约束成立都变成了 ，复杂的组合条件可以经过转换变成简单的二元运算：

1
2
3
4
5
6
7
8
if(a&b){}

//transform
if(a){	
	if(b){
		
	}
}

这样，向最优化问题的转换变成了可能。注意 实际上还是一个黑盒函数，你是并不知道它完整构造的，只能通过输入，得到输出，也是一个无约束最优化的标准问题，为了解决这个问题，文中使用梯度下降的方法。

使用梯度下降过程中需要计算梯度，但是前面说了这里的 是一个完全黑盒的函数，甚至可能都不是一个连续的函数。在没有其他方法的情况，只能通过近似计算梯度，来保证后面的运算。

现给出 的定义： ,其中 ,即输入input中与f对应二元运算相关联的值。注意这里的 并不完全是像 中的 一样是单个字节，后面还有一个结构感知的过程，这里 可能是一个完整类型的变量。对于多元函数 而言，它的梯度定义为：

其中 $$ 是一个极小的正数（e.g. ,1）， 表示 方向上的单位向量。为了计算每个方向上的偏导数，需要跑两次input,第一次使用original input ，第二次使用经过变换preturbed input ，这里有一个非常重要的问题，有可能第二次使用preturbed input的时候，导致 所指的二元运算所在程序位置变成了unreachable，这个时候会导致无法计算或者计算出来的结果是毫无意义的。原文在这里没有细谈，而是一笔带过，但是在Matryoshka中在这里提到一种解决方法，有兴趣的同学可以去看看。

最后是否能收敛到理想状态的下(小于0或者小于等于0) ，文中提到了三个点：

  • 是一个单调函数或者凸函数。
  • 局部最小值满足约束。
  • 如果局部最小值不满足于约束，Angora将会随机的使用其他的 ，直到局部最小值满足约束。

结构和类型推断

前面提到过 中的 并不是完全字节粒度的位向量，Angora会尝试把一起使用的字节归纳为一个type。文中这里也提到了一个问题，关于为什么要引入这个机制？假设某个程序把4个连续的字节 当作一个int类型，用 代表这个整型，那么在计算 的时候，只需要在 加上 ,但是把其分开成4个方向偏导数分别计算，可能会影响其收敛速度。

结构推断：哪些bytes总是一起被使用？

类型推断：一起被使用bytes是什么类型？

Angora里面的primitive type分为1，2，4，8bytes。它们之前可能会出现矛盾情况（e.g. 相同连续位置，被fetch一次8bytes，同时也被fetch一次4bytes），这种情况下，取最短的type。类型推断的依据使用其上下文的语义所决定的，比如某个指令操作对象是signed int,那么对应的type也是signed int。注意其整个过程都是在动态的污点分析中完成的。

输入长度探索

Angora这里特别地采取了关于输入长度的判断策略，通过关联read-like函数和read 系统调用，对read-like函数传参判定对应的输入offset(taint相关), 还会特殊标记它们的返回值，如果它们的返回值流到了路径条件上，且没有满足路径条件，Angora会尝试增加输入长度。这里我觉得这个策略并不会普遍适用于一般的程序输入，只能说一种有趣的尝试。

0x02 Self Conclusion

很有趣且朴素的一篇文章，使用的5种解决路径方法很实用，且开源（能看代码的感觉真好），但是仔细研究细节可能还是与自己想的不太一样。其中很多东西，可以尝试应用到实际情况下，我觉得就值得。“纸上得来终觉浅，绝知此事要躬行”。