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就会增加输入的长度以满足分支的约束.
作者认为符号执行中的执行器是性能的主要瓶颈, 而目前大多数的符号执行引擎都会将被测程序转化成IR(比如LLVM bitcode), 然后在IR基础上符号执行, 而作者解决该瓶颈的方案就是将符号处理编译到二目标程序中去, 最终得到无需外部解释即可执行的二进制文件, 在运行目标程序的同时, 跟踪各个符号表达式, 使得在符号推理的同时又能保证程序的运行速度.
符号执行的早期就有多个引擎采用了该思路, 但它们都受到了以下两点的影响:
- 源代码的插装会使得其绑定到某个固定的编程语言上, 而SymCC则是处理IR, 与语言无关
- 在完整的编程语言集上实现该目的可能非常困难, 而IR相比完整编程语言集而言小得多.
SymCC基于LLVM构建, 首先获取待测程序的LLVM bitcode, 然后将其编译成具有符号执行功能的二进制文件, 而在程序的每个分支点, 都会生成一个偏离当前执行路径的输入. 换句话说就是SymCC能产生混合执行的Binary.
动态数据流跟踪(DFT)用于处理程序在运行期间传递的标记并跟踪感兴趣的数据, 我们以下图示例代码为例, 其主要分为以下三个方面:
- Data Source: source是程序或者一个内存位置, 通常在执行函数或系统调用之后, 就会引入相关数据, 比如Figure 1中我们把文件定义为source, 那么read函数就会继而标记data和pass
- Data Tracking: 程序运行期间会跟踪标记数据的复制情况和更改情况. 比如Figure 1中标记了data变量, 那么在接下来的while循环里, csum与data数据相关, 就会继而标记csum. 而(b)中, pass跟phash有数据相关, 而phash跟authorized存在控制相关, 这就是一种间接的控制流依赖.
- Data Sink: sink也是程序或内存位置, 通常可以在sink点处对标记数据进行检查, 比如不允许数据存在某些内存区域或者函数参数的检验. 比如在Figure 1中, 写入文件作为sink, write函数则对csum进行了相关操作.
DFT需要额外的空间保存数据标签, 另外, 程序本身也需要使用标签传播逻辑和数据标签进行扩展, 并且分别检查source和sink的逻辑, 为此使用插桩代码来实现. 代码插桩可以通过静态注入方式(在源代码开发/编译/加载过程)实现, 也可以使用虚拟化或动态二进制插桩(DBI)实现. 无论静态/动态方法实现插桩, 都需要将程序的数据和标签进行关联, 并注入逻辑以在source处声明标签, 然后根据程序语义定义的数据依赖性来传播它们, 最终检查sink是否存在标记数据.
视频地址: 21. Data Tracking
视频以Android的TaintDroid为例介绍污点分析.
- sources: 敏感数据的来源, 比如传感器数据, 联系人信息, IMEI这些都是敏感数据
- sink: 不希望敏感数据到达的地方, 比如网络.
- taintdroid使用32位向量表示taint, 用于跟踪32个taint sources
- 污点的传播方式:
- mov dst, src: 污点直接从src传递到dst
- union: 比如两个污染源影响同一个变量
- native method: 一些native的方法比如arraycopy也能传播污点
- IPC消息
- 文件
- 需要标记的污点: 局部变量, 函数参数, 对象实例的成员, 静态类型的成员, 数组
- 污点的难题: 性能开销大, 误报多, x86指令复杂,很难准确建模
- implicit flow: 隐式的控制流去影响某些变量的值以达到传播的目的, PC被污染