简介

Angora的主要目标是无需借助符号执行的情况下, 求解路径约束以提高分支覆盖率, 为达到该目标, 其引入了四种关键技术: 字节级污点跟踪, 上下文敏感的分支计数, 梯度下降法以及输入长度探索.

  • 上下文敏感的分支覆盖: AFL使用上下文无关的分支覆盖率来近似认为程序状态, 但实验表明上下文敏感能让Angora探索更广泛的状态
  • 字节级别的污点跟踪: 大多数的路径约束其实只跟输入里的少量字节相关, 因此Angora回去跟踪哪些字节跟对应的路径约束相关, 仅变异这些相关的字节而非整个输入.
  • 梯度下降法: Angora使用梯度下降法来解决路径约束.
  • 类型/形状推断: 输入中的许多字节经常会作为整体共同作用于一个值, 比如4字节用作32位有符号整数, 为了让梯度下降能有效地搜索, Angora设法找到上述的组并推断其类型.
  • 输入长度探索: 程序有时对输入有长度的要求, 符号执行和梯度下降都不能告诉Fuzzer何时应当增加输入的长度, Angora则会检测输入是否会影响到路径约束, 并适时增加输入长度.

设计

上下文敏感的分支覆盖

将分支定义为(prev, cur, context), prev和cur是当前分支前后基本块ID, 而context则是h(stack), h代表哈希函数, stack则是调用堆栈状态. 但用堆栈表示上下文的话, 遇到递归就会出现重复很多次. 因此h这个哈希函数仅将每个调用点计算一次来规避递归带来的重复问题.

字节级别的污点跟踪

Angora将程序的每个变量与一个污点标签tx做关联, tx表示可能流入x的输入中字节偏移量. 当然这里的污点标签需要满足快速的Insert/Find/Union操作, 因此作者通过构建二叉树来优化了时空效率.

梯度下降法和类型/形状推断

使用梯度下降法得到局部最优解作为路径约束的解, 而对于字节而言, 简单的应用梯度下降是合适的, 但对于多个字节组成的单个值, 在计算梯度的时候会出现问题, 所以作者必须解决类型推断的问题.

为了解决该问题, Angora需要确定 (1) 输入里哪些字节被组合成单个值 (2) 判断这单个值其类型. 论文里将(1)称为形状推断(shape inference), 将(2)成为类型推断(type inference)

  • shape inference: 初识时所有字节都视为独立的. 在污点分析期间, 当一条指令读取字节序列输入给变量, 且该字节序列长度与原始类型的大小匹配(例如1,2,4,8字节), 则将这些字节序列标记为同一个值
  • type inference: Angora通过指令的语义作为依据来判断类型. 比如是一个对有符号整数进行运算的指令, Angora则将其操作数认作有符号整数, 如果一个数被同时用做有符号和无符号时, Angora则默认认为其是无符号. 当然推断不出来的话, Angora也没辙了.

输入长度探索

污点跟踪期间, Angora会在read类函数调用时, 将目的内存地址和对应输入的字节偏移关联起来. Angora也会将read函数调用的返回值用特殊标签进行标记. 如果在条件语句中使用到了返回值同时又不满足约束条件了, 那么Angora就会增加输入的长度以满足分支的约束.