动态污点分析和前向符号执行 (2010)

原文：All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask)

动态污点分析（Dynamic Taint Analysis，DTA）运行程序并观察计算是否被预先定义的污点所影响；前向符号执行（Forward Symbolic Execution，FSE）自动构造描述程序执行路径的逻辑公式，从而将推理执行过程的问题化简到了逻辑领域。

两项技术广泛用于：

1. 未知漏洞检测
2. 自动输入过滤器生成
3. 恶意软件分析
4. 测试用例生成

这篇文章给出了关于DFA和FSE的形式化定义，然后描述了其中的实现细节以及可能遇到问题及可能的解答。

首先需要定义一种中间语言，通常中间语言会包含赋值、断言、（条件）跳转几类语句。可能的变化在于：数据类型的识别、内存读写的处理、输入的处理、数据长度、大小端等。函数调用等高级特性即可以用上面的简单的中间语言表示出来（汇编中，函数调用实际上是进出栈的操作和跳转操作的组合），也可以直接加到中间语言里（此时可能需要栈上下文、函数名的映射、作用域上下文等）。

其次设计一种操作语义，以无二义地描述语句执行时发生的操作（对系统的影响）。一个执行环境通常可以有5个参数决定：语句集、当前内存状态、变量的当前值、程序计数器、当前语句。

DTA

动态污点分析用于跟踪source和sink之间的信息流动。任何依赖于污点source的程序值都被认为污染了，其他的则被认为未被污染。污染策略决定：

1. 程序执行时污点如何传播
2. 何种操作引入新的污点，比如输入来源不同，是否受污染也不同
3. 对被污染的值做何种检查

显然，针对不同的分析，污染策略是不同的。

和所有的分析一样，污点分析可能出现两类错误：overtainted（误报）和undertainted（漏报）。如果两种问题都不出现，则称分析是准确的。由于分析时需要记录各个变量/值的污染情况，所以上面的中间语言在表示变量时应加入污点信息，如<v, t>的形式，t为污点信息。

污点分析目前的挑战在于：

1. 被污染地址和地址内容的区分。如果将两者完全区分开，攻击者可以利用被污染的值作为函数表的索引，从而指定任意函数执行；但是，tcpdump却利用读入的数据包中的某个特定数据作为包处理函数表的索引。也就是说，在有些情况下并不合适区分，有些情况下却必须做。
2. undertainting。动态分析对于某些类型的信息流的处理并不太好。尤其是信息流动受控制流影响时。由于DFA只能跟踪执行时的那条路径的信息，其它未执行分支的信息它无从获知。解决办法是：加入静态分析或者启发式算法
3. overtainting。知道什么时候加入污点，更要知道什么时候消除污点，后者被称为taint sanitization problem，它更难解决。一个典型的需要消除污点的情况是常数函数，如 b = a xor a，b显然为0，不受a是否被污染影响。某些时候，如加密函数，允许用户修改输出，但无法修改为指定值，所以可以认为其输出是未污染的。目前的消除策略基本都是根据特定问题提出的非普适性方法。
4. 检测和攻击的时间差。在用DTA做攻击检测时，可能发现问题的时候已经太晚（攻击已然发生）。比如攻击者修改函数返回值，使之指向shellcode。显然返回值被污染了，但是警报要在它作为跳转目标时才会发出，那么在被污染和发警报之间，程序可能对文件或网络进行某些操作而没有收尾，这样警报发出、程序中断则会对其造成影响。动态分析得到的信息有限，因此无法追所有可能修改返回值的位置。对于整数溢出的检测来说，也有类似的问题。BitBlaze为此加入了事后分析，但这样会丧失纯动态分析环境的一些优势。

FSE

FSE允许我们一次性推理多个不同输入下的程序行为。由于引入了符号，那么程序在计算表达式时就不会得到具体值，而是一个关于符号的表达式，所以中间语言需要修改，加入符号表达式的集合。当遇到分支语句时，实际执行的路径的约束也会加入符号表达式集合。

FSE的难点在于：

1. 符号内存。一个常见的sound的办法是考虑所有满足该符号表达式的内存。这种符号内存地址问题会引出别名的问题，即两个不同的符号是否指向同一块内存？不同的应用会有不同的妥协方案，比如Vine默认不同的变量指向也不一样。除去这种简单的方法，还可以利用SMT solver求解约束以获得别名信息；或者采用别名分析。但是别名分析是静态的/offline的，在实时分析中加入静态分析可能不太吸引人。KLEE采用了一种别名分析和SMT求解的办法；DART和CUTE则只能处理线性约束。到目前为止恶意软件分析里还没有能处理好符号内存的很好的方案。
2. 系统调用（包括符号跳转）。测试用例生成不处理符号跳转影响并不大，不过覆盖率低一点，但对于恶意软件分析就不行了。通常由三种手段：混合执行，concolic analysis；SMT求解得到目标的具体值；静态分析整个程序，得到所有可能的跳转目标，实际分析中源代码的静态分析会使用指针分析，二进制代码的分析则推理跳转表达式引用的可能值。对于系统调用，一种办法是手工建立summary，模拟它们的副作用。另一种办法是混合执行，采用实际执行时的值，然而问题是有些调用可能不是总返回同样的值，如gettimeofday。

3. 路径选择。即需要一种指导遇到分支时需要选择先执行哪一条的策略。这个策略很重要，因为碰到循环时，有时候分支会无穷无尽地出现。典型的办法是人为地加上循环上限。常见的策略有：

   • 深度优先搜索。其主要问题在于必须加上循环上限，以防止掉进无限循环的分支里。KLEE就采用了这种方法。
   • 混合测试。先用具体值执行一遍程序，然后用符号执行执行相同的路径。通过对条件跳转的约束取反来执行新的路径。由于符号执行很慢，产生了一种叫generational search的策略，用一个符号执行生成多个具体执行的输入。
   • 随机路径。KLEE也采用了这样的策略。
   • 启发式。如当前执行点到未执行指令的距离，过去多久没有执行到未执行指令，之类。

FSE会导致执行时间和程序分支成指数关系、指数增长的符号表达式，以及每条分支上指数级的符号表达式。解决的办法包括：

1. 使用更强大的硬件
2. 每次变量赋值给它一个新名字
3. 识别公式中的冗余，并进行精简
4. 区分相互独立的子公式，在SMT求解时增加cache，减少重复计算，KLEE采用了这种办法。
5. 用weakest precondition来替代FSE计算公式。前者的时间复杂度和空间复杂度都只有O(n*n)。它是一种从后往前的静态分析方法，不过也有人提出可以从任意方向开始计算的wp，但必须使用特定的表示法。

有一种mixed execution，允许部分输入是具体值，部分是符号值。

DTA和FSE可以应用在以下领域：

1. 自动测试用例生成
2. 自动过滤器生成。入侵检测系统会用输入过滤的办法阻止会触发已知bug的输入，FSE可以做这件事。
3. 自动网络协议理解。DTA可以做这件事。
4. 恶意软件分析。DTA对恶意软件的代码展开尤其有效
5. 网络应用。DTA已经被用来检测SQL注入、跨站脚本等攻击，有时候也会加入静态分析。
6. 污点性能框架。即一个污点分析的平台，有基于硬件的、基于编译器的、也有基于软件的。
7. 污点分析的扩展。