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

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

\left\{ \begin{array} \ (l_{prev},l_{cur},context) \\ h(stack) \end{array} \right.

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

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

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。

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

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阶段能更好的去解决路径条件。

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

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

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

画了一个图,方便理解和记忆:

binary_tree1

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

注意到这个算法只在生产新结点的时候,插入 t_x ,所以某个结点如果存在 t_x 则后面都是不会发生改变的。我计算得到的空间复杂度跟原文有一定区别,原文是 O(l*logl) ,我在计算最坏复杂度时得到的是 O(nl-l*logl) .

S= 2n+2(n-1)+4(n-2)+\cdots+(2^{log_2l-1})(log_2-1) \\ S= nl-\sum_{n=1}^{log_2l-1} n2^n \\ S= nl - (l*logl) ,(\sum_{n=1}^{m} n2^n = (n-1)2^{m+1}+2)

Maybe i am wrong,who know!

基于梯度下降的搜索算法

目标是解决路径,让路径条件满足某种要求,我们从最简单的条件出发,某个二元运算,和两个基本变量:我用 \odot 泛指所有可能出现的二元运算,基本变量用 a , b 表示:

a \odot b = ?

文中尝试将求解约束转化成最优化问题,所以需要让上面的问号变成一个具体的值,而不是通常情况下的 \{0,1 \} ,文中做一个漂亮的转换。

将二元运算转化成了具体函数,函数值间接表示约束的成立。通过合适的函数表示,将所有的约束成立都变成了 f(x) \le 0 ,复杂的组合条件可以经过转换变成简单的二元运算:

if(a&b){}

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

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

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

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

\nabla f(\mathbf{x}) = \bigg(\frac{\partial f}{\partial x_{1}}(\mathbf{x}), \cdots, \frac{\partial f}{\partial x_{n}}(\mathbf{x})\bigg)

其中

\frac{\partial f(\mathbf{X})}{\partial x_i} = \frac{f(\mathbf{X}+\delta v_i)-f(\mathbf{X})}{\delta}

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

f(\mathbf{X}) 最后是否能收敛到理想状态的下(小于0或者小于等于0) ,文中提到了三个点:

  • f(\mathbf{X}) 是一个单调函数或者凸函数。
  • 局部最小值满足约束。
  • 如果局部最小值不满足于约束,Angora将会随机的使用其他的 \mathbf{X}' ,直到局部最小值满足约束。

结构和类型推断

前面提到过 f(\mathbf{X}) 中的 \mathbf{X} 并不是完全字节粒度的位向量,Angora会尝试把一起使用的字节归纳为一个type。文中这里也提到了一个问题,关于为什么要引入这个机制?假设某个程序把4个连续的字节 b_3b_2b_1b_0 当作一个int类型,用 x_i 代表这个整型,那么在计算 f(\mathbf{X}+\delta v_i) 的时候,只需要在 x_i 加上 \delta ,但是把其分开成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种解决路径方法很实用,且开源(能看代码的感觉真好),但是仔细研究细节可能还是与自己想的不太一样。其中很多东西,可以尝试应用到实际情况下,我觉得就值得。“纸上得来终觉浅,绝知此事要躬行”。