作者：Zheng Leong Chua, Yanhao Wang, Teodora Baluta,Prateek Saxena,Zhenkai Liang, Purui Su

单位：新加坡国立大学，中科院软件所

出处：NDSS‘19

原文：https://www.comp.nus.edu.sg/~prateeks/papers/TaintInduce.pdf

贡献

• 提出了一个操作时生成规则的动态污点分析方法
• 精确地定义了动态污点分析中的ISC，提出了一种有效的规则生成算法
• 实现了TaintInduce并进行了评估

问题

污点推断问题

目标是实现一个可以自动生成规则的污点分析机制，粒度为bit，规则要尽可能地completeness和soundness。

• 运行环境和假设

  程序运行在冯诺伊曼体系计算机上，污点引擎可以识别指令，区分指令是否进行寄存器和内存访问

  假设寄存器数目和最大内存槽数已知

  不需要知道指令的反汇编，对于操作数不同和操作相同的指令，认为是不同的指令

• soundness与completeness

  对于一条规则，如果存在能满足这条规则的指令运行结果，那么就认为这个规则不是冗余的

  反过来，对于每一次指令运行的结果，规则都能满足，那它就是完整的

污点推断的挑战

• 输入的上下文带来的影响

  对于and eax, ebx这条指令，第二操作数是否为0，影响了eax的污点能否继续传播

  

• 不完整性

  有的工具不包含对标志位的影响。如下图所示，libdft对and eax, 0xff的操作规则，没有考虑标志位。

  

• 架构奇点

  对于and eax, ebx这条指令，在x64下，如果操作数为32位，目标寄存器会被0扩展。而16位和8位不会。

设计

污点传播策略

有别于通用的动态污点传播策略，作者实现的策略是有条件的成分的，而条件依赖于输入。比如前面and eax, ebx的例子，ebx的值会影响指令对eax的污点传播情况。

概述

工作的重点在于如何自动化的生成污点规则。

TaintInduce通过观察程序状态来学习规则，程序状态包含了指令的寄存器状态和内存访问。如下图虚线部分。

当分析一条指令时，TaintInduce观测它在一系列种子输入下得到的不同状态，由状态生成观测，通过不同观测得到前提条件和污点传播规则，二者的组合会放到规则数据库中，以供查阅。

定义直接依赖

对于有n个位的状态S，TaintInduce翻转n个位从而生成n个新的突变状态，在n个状态下分别concretely executes，然后将输出状态作为观测值。

输入翻转i会造成输出j变化，则把结果对(i, j)作为“change”观测；而没有变化的j，就作为”noChange”观测，

学习出精简的条件

这个部分讲的是如何生成前提条件，本工作的前提条件是一个析取范式。具体的，是一个n个布尔变量之上的析取范式。为了得到这个析取范式，作者首先在n个输入位之上构造了一个函数(function over the n bits，我的理解是这个函数的输入是n^2个对)，当所有程序状态位于之前生成的所有观测值中时，这个函数返回真；否则返回假。也就是构造了个和所有程序观测有关的真值表，然后把这个真值表做处理，就可以得到析取范式。

处理的过程引用了ESPRESSO这个算法，作者强调这个算法不会产生过污染，这个处理的过程即布尔表达式最小化。

定义间接依赖

间接依赖大多是有条件的，如果同一指令生成的规则有歧义，即对于同一个i，发生变化的j会变，则以间接依赖处理。和直接依赖相比，它的在生成前提条件时，所构造的函数，返回真值的条件变成了观测到了i的变化会影响j，反之为假。

实现

对于学习过程，作者实现了两种模式，精确模式和整理模式，这两种模式的区别仅在布尔表达式最小化的策略和是否建立内存化的规则两点上有区别。

评估

评估围绕4个方面进行

• 漏洞诊断能力

  能否检测出污点类的的漏洞

• 对架构的覆盖性与准确度

  在归纳模式下，有多少跨平台指令可以传播污点。和现代工具相比，效果如何

• 多用途

  TaintInduce能不能辅助污点引擎、模拟器、ISA手册的开发与设计

• 性能

漏洞诊断能力

作者使用26个有漏洞的程序和CVE攻击载荷作为样本。使用学习出的规则来传播污点。在精确模式和整理模式下，污点都能达到已知的漏洞。其中24个例子是可以恰好由污点输入到达污点的。其余的2个会在间接引用处断掉。由都能到达，说明污点没有漏过；由没有得到错误的sink说明没有污点过度。

作用于多个架构

评估了unicorn支持的4种被广泛应用的架构：x86，x64，ARMAArch64和MIPS-I。每条规则使用1000个随机数值。指令的数学相关性越强，规则就越不准确，ARM的结果和x64比很差，就是因为ARM的SIMD指令的数学运算多。

会出错的例子，作者举了maxpd xmm1, xmm2这个指令。这个指令会根据两个操作数的大小关系将源操作数放到目标操作数之中。TaintInduce只能得出将xmm2放到xmm1这样的规则。此外，对于add eax, ebx这个指令，会生成一个不准确的规则，但是不影响污点分析的结果(Recall that although the rule is unsound in the general sense, it is correct for the set of 100 states it is trained on.)

上述结果基于整理模式的，在精确模式下，污点可以100%得到传播。

与其他工具进行正确性比较

与TEMU，Triton和libdft进行比较。TEMU使用rpcss, mssql, atphttpd, ntpd, smbd, ghttpd。Triton和libdft使用10个LAVA-M benchmarks以及libtiff和binutils的fuzz测试包。

TaintInduce使用归纳模式，并且在运行前，对每一个事先测试得到指令，进行100个随机种子的训练。在运行过程中，如果出现了差异，则将已有工具的状态赋予TaintInduce，以同步状态。

最后比较出来的结果，是TaintInduce和已有工具有不到7%的差异。进一步的，这些差异中只有0.28%是TaintInduce有错。具体的，在和TEMU的比较中，二者的输出有0.5%的差异，对于这些差异，经过手工分析可以知道，TaintInduce都是对的。

而在和Triton与Libdft的比较中，有93.27%的指令TaintInduce和这两种没有差异。在有差异的指令中，有21.42%时因为libdft没有实现，即shl，shr，movd，shld，fst，和pmovmskb。libdft把这些指令当作nop处理。剩余的78.3%来自于污点的粒度。

作为引用工具

最终，作者在libdft，Triton，TEMU，中分别发现了11、7、2处规则错误，并且在unicorn中发现了17处模拟错误和指令集手册中的3处描述错误。

• 指令集手册错误

  对于bt r16/r32, r16/r32这条指令，它的功能是取出一个位，这个位来自于第一操作数，第二个操作数指定了是第一个操作数的第几位，取出的位放在CF寄存器上。手册中说，这个位影响的是CF的第3或第5个，但是实测这个位影响的是4或5（16位操作数为4，32位操作数位5）

• 手册中的描述不完备

  对于bsf指令，它的功能是在源操作数中扫描第一个“1”，将位好返回到目的操作数。目的操作数如果未定义，之后会产生什么行为，在Intel的手册中未定义，而在AMD的手册中，写明了如果源操作数位0，目的操作数不会发生变化。（笔记作者按：习惯上讲，编程人员可能认为是会把目的操作数清零）

• CPU实现差异

  对于tzcnt这个指令，它的功能可以认为是bsf的一个扩展。对于操作数为0的情况，tzcnt会返回输入的数据大小，而bsf指令没有定义。对于不支持tzcnt的CPU，这个指令的字节码会被当做bsf来执行。

• unicorn的模拟缺失

性能

1台机器，学习1条指令，需要大概30秒

总结

读这篇论文的出发点是很喜欢这种自动化地处理机械重复劳动的思维。而高度的自动化，除了能提高效率，有时还能有其它发现，这种现象，在日常工作中也有体现。对于本文，作者在实现了足够准确的自动化生成规则的方案后，在测试中甚至发现了指令集手册中的不足，这个实例是前面说的现象的一个很生动的例子。

作者在评估样本的样本说明中说the test and training datasets are completely different，而没有具体指出，有些疑惑。