基于MATLAB的一维条形码检测技术，运用了ROBDD的细颗粒度污点分析方法

北京大学博士学位论文 第二章 基于ROBDD的细颗粒度污点分析技术 文献[113]中证明BDD的合并操作复杂度为O(m ∗ n)。由于其消除了冗余信息,在存 储空间上BDD一般要比布尔函数的真值表小很多。因此，BDD内部的节点数通常 远远小于BDD所表达集合的势。图2.2给出了集合{0, 1, 2, 9, 10}的BDD表达。 2.4 基于roBDD的细颗粒度污点分析系统架构设计与实现 2.4.1 污点传播属性分析 本节分析细颗粒度污点分析过程中污点数据的传播特点，介绍如何利用这些 特点，降低细颗粒度分析的内存需求，提高分析效率。 首先，污点数据的传播具有重复性。污点分析主要是追踪内存单元对污 点数据的依赖关系，而很多内存单元/寄存器可能具有同样的污点属性。例如， mov是一个经常使用的x86指令，用于内存、寄存器之间的数据移动。这意味着执 行mov指令后，其源操作数与目的操作数具有相同的污点属性。从高级语言层来 看，很多高级语言特征例如函数参数的值传递、临时变量、对象克隆等都会引起 污点数据的重复性。很多研究[180, 79, 107]都有类似的发现。显然，利用污点传 播的重复性将有助于降低分析的内存需求。 其次，污点数据的传播具有重叠性。污点数据的交互操作引起了重叠性。对 于二元操作，如果两个操作数都依赖于污点数据，那么操作结果将依赖于两个操 作数污点属性的并集。例如，表2.1中，变量z依赖于集合{0,1,2,3,4,5,6,7}，而变 量x污点属性为集合{0,1,2,3}，变量y污点属性为集合{4,5,6,7}。变量z与变量x、y 的污点属性都有重叠。利用不同内存单元污点属性的重叠性也有助于降低污点分 析的内存使用。 最后，污点数据的传播具有连续性。由于局部性原理，连续的污点数据通常 被一起使用。例如，一个32比特的整数通常保存至连续4个字节。如果一个内存单 元依赖该整数，意味着该内存单元的污点属性依赖于连续4个字节。其他原语类 型例如字符串也具有类似的特性。 X. Zhang等人 [180]在对程序动态切片的研究中，发现基于roBDD的集合表达 可以有效利用上述特性，降低集合的空间需求，能够提高切片效率。本文在细颗 粒度污点分析中引入roBDD结构，采用roBDD描述污点属性起到了很好的效果。 – 19 –