基于 roBDD 的细颗粒度动态污点分析
第一次接触污点分析，很多地方还不了解，就当是先入个门吧。目前先看看王铁磊大佬的文章跟着学一学
论文关注的研究现状
一个有代表性的方法是维护一个从内存地址到用于指示污染属性的数据结构的映射(即影子内存)。 许多传统的污染分析系统只关注内存地址是否被污染。 因此，布尔值足以存储内存单元格的 taint 属性。
通常，需要考虑两种依赖关系: 数据流依赖关系和控制流依赖关系]语句 S2是依赖于 S1 的控制流当且仅当 s 的执行被 sp. 有条件地保护。 语句 S2是依赖于 S1的数据流，当且仅当 S1 修改了 S2读取的资源并且在执行中优先于 S2。 在本文中，只关注数据流依赖性。
论文的主要工作
本文实现的污点分析技术，将实现变量对于所有输入位置的污点关系。
污点定义方式
如果z=x+y，x由输入0123决定，y由输入4567决定，则z由01234567决定
对于n字节的整数，使用n个bool量来表示
二元决策图是一种用来表示布尔函数的数据结构。 BDD 有两个终端节点，即0端节点和 l 端节点。 除了两个终止节点外，其他节点(响应不同的 Booleanvariables)有两条边，称为0边和1边。 当 BDD 的变量顺序固定时，roBDD 给出了 BDD 的标准形式。 我们建议读者参阅参考资料。[11] B ryant R E ． G rap h—b ased algorithm s f o r B oolean fun ction m an ipu lation ． IE E E T ran s C om p ut． 19 8 6， 3 5 ： 6 7 7- 6 9 l [12] B ryant R E ． S ym b olic b oolean m anipulation w ith ord ered b in ary —d ecision d ia gram s． A C M C o m p ut Su rv, 19 92 ， 2 4 ： 2 9 3—3 18 。来具体的了解BDD（之后有需要再了解吧）
本文介绍了一种有效的离线细粒度污染分析系统 TaintReplayer。 TaintReplayer 主要由两个模块组成: 记录器和重播器。 有几个新颖的功能。 首先，TaintReplayer 是一个离线的污染分析系统。 它首先记录执行跟踪，然后重放跟踪。 在线污染分析的性能和内存开销往往导致目标程序不能很好地运行，甚至在程序运行的早期阶段就已经存在，而离线污染分析只能在运行时记录执行轨迹。 与在线污染分析相比，测井的性能开销大大降低 。 执行跟踪是可以接受的。 其次，在离线回放阶段，TaintReplayer 利用 obdds 表示集合结构，从而大大降低了内存使用量。 最后，TaintReplayer直接处理二进制程序，不需要访问源代码。 另外，TaintReplayer 可以在 Linux 和 windows 平台上运行。
本文的动态污点分析是基于二进制插桩技术。 记录器负责记录执行的痕迹。 对于每一条执行的指令，这些信息包括指令访问器的内存位置的地址和值，修改寄存器的值，以及指令的地址。 记录器还会记录一些有趣的系统调用的效果。 例如，对于将输入文件中的数据读入缓冲区的文件读取系统调用，记录的信息包括文件位置、缓冲区的起始地址和读取的字节数。
结果生成的是每个内存对于各个输入字节的依赖。（可以想见的这会非常庞大）使用roBDD来表示。
指令执行跟踪的处理
给定一个执行跟踪 T= <I, i0>，I 是执行指令的序列，i0是跟踪的第一条指令。 让 env 是一个 tuple （M，R) ，其中 M 是从内存地址到 roBDDs 的映射，而 R 是从寄存器到 roBDDs 的映射。 用 Fi表示指令 I 的语义功能，它负责根据指令 i 和输入环境的语义来更新 M 和 R。 开始的时候是M0 和 R0,
（Mi，Ri） = Fi * Fi-1 … F0（M0，R0）
指令语义函数 Fi 的目的是将污染信息从源操作数转移到目的操作数，特别是当系统调用指令系统并读取输入数据时，语义函数 f 将用唯一污染的 lacl 标记对应的内存地址。 下面的算法用于模拟系统读调用。
我们实现了一个 TaintReplayer 原型系统。 记录器模块构建在 PIN 二进制检测平台4的基础上，重播模块用 c + + 实现。 本文选择 BuDDY (一个 BDDpackage)作为roBDD 实现。
相比于别的动态污点分析工具，roBDD不会随输入的增加而大幅需要内存。结论为，ropdd 可以显著提高离线细粒度污点分析的性能，并且消耗更少的内存空间。
总结
提出了一种有效的离线细粒度污染分析方法，该方法首先记录执行轨迹，然后对执行轨迹(离线)进行污染分析，而不是在运行时(在线)跟踪输入数据的传播。 此外，我们的方法利用了减少排序的二进制决策图(roBDD)来表示集合结构。 实验结果表明，该方法能显著提高离线细粒度污染分析的性能。
动态分析技术的离线分析和在线监测？
就是自行加载程序的汇编代码进行检测还是 在运行中检测