（计算机科学与技术专业论文）基于函数摘要的c程序全局静态分析研究.pdf

一 _ ， 缺陷举例：内存泄露模式 缺陷描述t 程序没有释放之前分配给他的内存，在有些路径上对动态内存的引 用可能会丢失。 举例： 8 原因分析：在代码的第5 行，当i 为非零值时，会执行语句p = n e l l 。引起p 指向 的内存丢失而泄露。 解决方法s 动态分配的内存重新赋值或者退出作用域之前，均要将其释放。 2 安全漏洞模式 安全漏洞模式大多基于网络应用程序总结出的，有缓冲区溢出模式，未验证输 入模式，滥用a p i 模式，竞争条件模式等容易提供他人攻击的漏洞，在网络应用软 件通常会看重此类模式，安全漏洞会暴露给黑客更多攻击软件的方式，而带来很大 经济利益损失。 缺陷举例：输入变量导致缓冲区溢出 如果数据是从外部传进来的，而且在使用之前也没有进行检测，那么，这是个 错误这样的变量主要有：a r g v 口，o p t a r g ，e n v 。 同时，如果一个变量传入到个公有函数中，或者一个全局变量( 不知道声明在 何处) 被公有函数使用，并且没有对变量的合法性进行检查。 原因分析： 函数中没有对变量a r g v 进行检查，导致程序在第5 行处，可能会将溢出 9 北京邮电大学硕士学位论文 第二章相关研究 a r g v b u f f e r 指向的数组。 解决办法： 在使用a r g v 之前进行检查，或者用s t r n c p y 安全函数来替代s t r c p y 。 3 疑问代码模式 疑问代码模式主要指代码中容易引起歧义的、迷惑人的编写方式，这些故障多 用于代码质量本身的控制，或者执行效率比较低，为了软件进一步开发和维护而要 求的代码风格。 缺陷举例：没有被使用过的变量 缺陷描述：变量没有被读取，有的变量在定义后就未被调用过，有的变量定义 后重新赋值但未被使用过，这样的变量都属于不良的代码，会对软件系统的性 能有不良的影响，应该避免这种现象发生。 原因分析：在代码的第5 行，定义局部变量v a r ，而在函数体内，完全没有用到 v a r 值。 解决方法t 对没有使用或者无意义的局部变量值应该尽量删除 4 规则模式 规则模式主要包括某些标准或者行业特定要求编码规范或使用限制，并没有本 质的逻辑性错误，但是大量的使用对程序维护和进一步开发有一定风险，通常某些 特定行业会提出一些规则模式，例如国内航天领域软件就有指定国家标准来约束其 中软件。包括命名规则、复杂性规则、控制流规则、可移植性规则和资源规则等。 1 0 北京邮电大学硕士学位论文 第三章c + + 程序全局分析框架 第三章c + + 程序全局分析框架 从对程序分析策略上区分，静态分析可分为全局分析( i n t e r - p r o c e d u r a la n a l y s i s ) 和本地分析( i n t r a p r o c e d u r a la n a l y s i s ) 3 1 1 。本地分析中每次分析只针对一个函数或者 类进行相关分析，并不能理解函数或类之间的交互关系，以及全局的上下文环境。 而全局分析则在本地分析的基础上兼顾了各函数或者类之间的控制和数据依赖关 系，并通过对全局上下文环境抽象更完备的抽象程序属性和行为本地分析由于 没有全局信息而产生很多的漏报，而全局分析的难点在于对随着程序代码量的增加 如何有效的组织以及分析程序信息，因此实用性和扩展性对全局分析算法尤为重要 圈圈一 。_ 。_ 。_ _ - h _ 一 ! x 日轿圈 枷横式幢 广一一 一一1 南 向 j 图 lc + + 全局分析框架示意图 本课题在基于已有d t sc p p 系统基础上，经过扩展和修改使之可以支持全局 静态分析( 图3 1 ) 。首先对程序进行预处理和预分析，以得到的中间文件为分析的 基本单元，通过词法和语法分析得到其抽象语法树，依次遍历建立全局独立的类型 系统，并通过文件中的函数全局调用关系来近似估计分析单元的控制逻辑顺序，并 按照该顺序对分析单元中函数进行本地分析。此外由抽象语法树构建对应的控制流 图，进行变量区间运算然后产生该函数对应的函数摘要，最后通过遍历本地函数的 控制流图，用缺陷模式状态机进行缺陷检测。具体分为三个步骤：全局预分析，本 地分析和缺陷模式检测。修改和改进后的框架可以对c + + 源程序进行部分上下文敏 感( p a r t i a ic o n t e x t s e n s i t i v e ) ，路径敏感( p a t h s e n s i t i v e ) ，结构体成员不敏感 ( f i l e d i n s e n s i t i v e ) 的分析。 北京邮电大学硕士学位论文第三章c + + 程序全局分析框架 3 1 全局预分析 鉴于c + + 源程序的声明和实现离散的存放于不同的头文件和源文件中，大量的 包含自定义宏，因此在静态分析建立抽象语法树之前必须对源代码进行预处理，实 现头文件扩展，条件编译及替换宏，为后续静态分析做准备。预处理之后的中间文 件至少包含一个c + + 的源文件，以及一个或多个c + + 头文件，本框架中每一步分析 都是以这些中间文件为最小文件读入处理单位，我们称之为分析单元。 全局预分析的目的是为了确定大规模c + + 工程中各文件之间的依赖关系，以及 组织好整个工程中的类型信息因此必须在预分析中收集足够的类型信息和函数信 息，以便服务于全局分析。基于函数摘要的全局分析以函数为最小控制流分析单元， 因此必须确定全局函数之间的调用关系，包括c + + 类的成员函数，全局函数等，通 过按序遍历函数全局调用图准确获得整个被测项目的函数信息，最终达到跨函数全 局分析的要求。 另外预分析之后并不保留之前的抽象语法树结构，因为对于大规模的分析语法 树的规模通常是很大的，保留内存中会消耗很多空间所以我们选择在预分析之后 仅保留全局类型信息、计算出的函数调用图和分析单元依赖关系。具体算法和设计 实现在第三章中会详细讨论。 3 2 本地分析 本地分析是第二次对c 抖的分析单元进行扫描检测，首先d t sc p p 再次通过 词法和语法分析模块将分析单元转换成抽象语法树。然后在抽象语法树基础之上进 行符号表分析，其中包括类型分析，变量声明和使用关联，变量作用域分析以及表 达式类型推导等。其后通过特定算法将抽象语法树转化为控制流图，并利用区间运 算，数据流分析等技术来判定程序中变量的取值范围和路径信息，实际上这也是抽 象解释理论的某种实现。函数摘要的分析和生成是在每个函数区间运算完之后，根 据需要收集指定类型的函数摘要并保存到全局上下文中。最后缺陷模式检测模块会 根据函数的调用顺序，以及加载的缺陷模型依次检测缺陷。其中本地分析的关系和 全局分析的关系可以通过图3 2 表示，本地分析顺序由全局分析得到的分析单元逻 辑依赖顺序决定的，而全局函数调用图的构建也必须依靠预分析建立。 1 2 北京邮电大学硕士学位论文 第三章c + + 程序全局分析框架 图p 2 本地分析和全局分析的关系 将抽象语法树转换到控制流图的过程中，要考虑c + + 语言顺序、循环、条件判 断等结构的特点，此外还要考虑到c + + 中异常路径对控制流的影响。控制流图对大 多数程序分析和结构测试都是必不可少的基础数据结构是一种反应程序逻辑控制 流程的有向图。通常一个函数的控制流图可表示为( n ，e ，e n t r y ，e x i t ) 。其中n 代表节点的集合，反映程序中的简单语句和复合语句的条件判断以及控制流汇合点 等，e 代表有向边的集合，反映程序中语句问的控制流关系。e n t r y 为函数的固定唯 一入口节点，e x i t 为函数唯一的退出节点。简单来讲：控制流图即是具有单一的、 固定的入口节点和出口节点的有向图。对于非单入口和单出口的程序，可以通过人 为添加一个统一入口和出口的方法解决。为了支持c + + 异常分析，在控制流图中人 为添加了e x c e p t 节点，表示所有未捕获异常的退出点，最终也是连out e x c e p to u t 接到函数的e x i t 节点上。 ， 从数据结构实现上考虑，控制流图实际上为一个有向图。有向图有多种实现方 式，在d t sc p p 中要求能很方便和高效地做到如下几点t 1 从每个顶点出发能很方便地找到每个顶点的出边集合和入边集合。 2 从每个边出发能很方便地找到它的始点和终点，也能很方便地找到和该边具 有共同始点或共同终点的边。 3 能够方便地对控制流图进行各种遍历。 4 能够方便地从控制流图节点找到对应的语法树节点，反之亦然。 c + + 程序中影响变量取值范围语句有：各种赋值语句、条件判断、控制流。对 于赋值语句，它对变量的取值范围的影响是显然的。例如：a _ a + 5 ；假设a 原来的取 值范围为【0 ，2 】，则执行了该语句后a 的取值范围为【5 ，7 】。程序中的条件判断也会 1 3 北京邮电大学硕士学位论文第三章c + + 程序全局分析框架 影响变量取值范围。例如： i f ( a - 1 ) ) e l s e ) a 原来的取值范围为【o ，2 1 那么在i f 语句真分支上由于受到a = l 条件取真的 限定，则a 的取值范围为：【l ，2 】，相应地在i f 假分支上受到a = l 条件取假的限定， 则a 的取值范围为：【0 ，0 】。控制流对于变量的区间起传递和汇合的作用。 区间运算【3 2 】【3 3 】的引入，确定了程序中变量的取值范围，也为缺陷模型检测避免 了大量的不可达路径，从而减少了误报。d t sc p p 通过在迭代控制流图分析中，利 用数据流方程f 6 埏；算。 i n ( s ) = n ，。石f j ) o u t ( s ) o u t ( s ) = g e n ( s ) uf i n ( s ) 一k i l l ( s ) ) 方程中各项的含义如下： i n ( s ) ：程序点s 执行之前的数据流信息。 o u t ( s ) ：程序点s 执行之后的数据流信息。 g e n ( s ) ：程序点s 新产生的数据流信息。 k i l l ( s ) ：程序点s 杀死的数据流信息 p r e d ( s ) ：程序点j 的前驱点集合。 目前d t s c p p 区间运算能够处理整型，浮点型，布尔型，指针型，数组类型 等变量的区间取值和运算，具体与c + + 的类型对应关系如表3 1 ，为保证运算的完 备性和封闭性，区间的取值范围大量的参考了近世代数中格理论。其中 u n k o w n d o m a i n 是应对当前区间运算能力有限而人工添加的，当d t sc p p 无法计 算出某变量的区间时如无法获得某函数返回值区间时，我们即认为其区间值为 u n k o w n 。添加了u n k o w n d o m a i n 后使得整个区间运算更具完备性和容错性，可适应 复杂程序分析。 表3 1d t s - c p p 区间类型与数据类型对应关系 北京邮电大学硕士学位论文第三章c + + 程序全局分析框架 区问类型c + + 数据类型取值范围 i n t e g e r d o m a i nb y t e ，c h a r ，s h o r t ，i n t ，l o n g ，e 整数，范围根据类型字节，范围 n u m不同 b o o l e a n d o m a i nb o o l t r u e ，f a l s e ，t r u e 一0 r f a l s e ， d o u b l e d o m a i nd o u b l e f l o a t浮点数，范围根据不同类型字节 p o i n t d o m a i n指针类型 o f f s e t 表示指针偏移，r a n g e 表 示指针范围，二者均是罄犁 a r r a y d o a m i n 数组类型 数组维数 u n k o w n d o m a i n应对区间运算无法计算 的值 3 3 缺陷模式检测 缺陷模式检测】是d t sc p p 全局静态分析框架的最后一步，通过这步尽量发 现程序中的缺陷。缺陷模式是指从大量程序错误和故障中总结和抽象出来的模型， 比如在指针变量被赋空值之后，再对其解引用则会出现空指针错误。缺陷模式通常 ，采用有限状态机来描述，缺陷模式状态机也称属性状态机，包括属性状态集合d 、 状态转移集合t 及转移条件集合c o n d i t i o n s ”j ，其中d = $ s t a r t ，s e n o r ) ud o t h c r s ， t d x c o n d i t i o n s 。$ s t a r l 和$ e r r o r 分别表示起始状态和错误状态，d o t l ：l e m 表示其他 状态的集合，不同的缺陷模式状态机有不同的集合d o t h e r s 。d t sc p p 中状态转移 条件有多种类型，可以基于x p a t h 匹配，变量区间值，变量作用域等，提供了丰富 的可扩展接口。 d t sc p p 的缺陷模式分为故障模式、安全漏洞模式、疑问代码模式和规则模式 四类。故障模式里面包含未初始化变量，数组越界，空指针异常，悬挂指针，内存 泄露，非法计算和资源泄露等。安全漏洞模式包含未验证输入，缓冲区溢出，滥用 a p i ，竞争条件异常等模式。从缺陷模式是否跟变量相对应划分，缺陷模式状态机 可以分为变量相关和变量无关两种。从检测模式时状态机是否需要迭代控制流图划 分，可以分为路径敏感和路径不敏感两类。从状态机检测范围来分，可以分为全局 范围缺陷模式，类范围缺陷模式，函数范围缺陷模式。分别检测出现在整个文件中 的缺陷，一个类中的缺陷以及单个函数里面出现的缺陷。 例如c + + 中空指针缺陷模式，属于变量相关，路径敏感，函数范围缺陷模式。 1 5 北京邮电大学硕士学位论文第三章c + + 程序全局分析框架 故障状态机图如图3 4 所示，其中n o tn u l l 和n u l lo rn o t n u l l 均表示状 态机中不同的状态，而每个节点之间的边表示各状态之间的迁移，其中转换条件并 没有详细的列在图中。缺陷检测模块会在每个函数控制流图的开始节点中根据条件 创建n p d s t a t e m a c h i n e ，n p d s t a t e m a c h i n e 的创建条件是根据当前函数里面是否 有指针解引用，如果有指针使用的话，会对每个不同指针变量创建状态机。刚创建 的状态机处于s t a r t 状态。在当通过初始化或者赋值语句，对某指针变量赋值为空指 针时，状态机会迁移到n u l l 状态，当变量的值变为非空值时，状态会迁移到 n u l lo rn o t n u l l 状态，在无法有足够的信息来确定指针值时，也是处于该状 态，这样可以尽量避免误报，因为区间运算的信息有时候并不足够准确。当在n u l l 状态下对指针变量进行解引用操作时，则会转移到e r r o r 状态，这时缺陷检测框架 会记录下该检查点的所有信息，包括行号，代码片段等写入数据库，以便后期人工 确认。若在变量退出作用域之前均没有解引用，则状态机会转移到e n d 状态。结 束本次函数中对该变量的检测。 p d s ta te i a c h l 。r a c 图3 - 4c + + 中n p d 缺陷模式的故障状态机转化图 d t sc p p 框架中通过x m l 脚本和j a v a 的反射机制来实现可扩展的缺陷模式 其缺陷模式是可以动态插拔的，根据配置数据库，程序会加载用户指定的缺陷模式 1 6 北京邮电大学硕士学位论文第三章c + + 来进行检测，这样用户可以根据被测工程选择自身感兴趣的缺陷模式 在框架中通过有限状态机来形式化描述程序中可能的故障模式，然后 析的控制流图进行数据流迭代，并对符合条件的模式状态机进行对应 直到其到达错误状态或正常退出状态。分析的过程中利用了本地分析 果，避免遍历程序中的不可达路径。 加入函数摘要的缺陷模式检测，在原有基础上还需考虑在当前上 数的作用，例如在当前检测函数中调用的其他函数的影响，通过本地分析记录的函 数摘要来抽象一次调用的作用本文将在第五章中详细讨论如何在已有模式中使用 函数摘要。 3 4 效率的讨论 在分析实际项目中，往往头文件和源文件并不是放在同一个目录，有些工程依 赖单独的开发库，常见工程如g c c 提供m a k e f i l e 来编译，v i s u a ls t u d i o 提供工程文 件来组织头文件和源文件。因此在分析之前，可以先通过解析m a k e f i l e 或类似工程 文件来加速确定文件间的依赖关系，避免暴力搜索带来的时间开销 通常经过预处理之后的分析单元会很大，因为预处理只是进行简单的文件包含 和拷贝，因此可能出现同一个头文件被拷贝到多个分析单元中去，导致重复的解析 同一个文件内容，这样会影响后期的分析效率，而且多次分析有可能会给后面类型 系统带来歧义并增加分析的复杂性。因此在预处理之后，我们需要对每个分析单元 做些处理，避免同样的头文件出现多次，提高后续的分析效率。 在对大规模程序进行分析的时候，文件数可能有几百甚至上千，因此分析过程 中数据结构如抽象语法树和控制流图并不能全部缓存在内存中，尤其是当需要对分 析单元进行两次或多次分析时。第二次的分析必须重新建立抽象语法树和控制流图， 虽然这样会带来一定的时间开销，但是这样降低了运行时对内存的需求，大大提高 了系统对被测代码规模的适应能力。 但是类型信息和函数调用图等信息，则应该尽量保持全局的独立和唯一，而不 应该和抽象语法树或者控制流图耦合到一起。在预分析之后即保存在全局上下文中， 而不需要第二遍分析的时候再次解析。因为这些信息通常不会占用很多系统空间， 而且存放在全局上下文环境中，有利于后续本地分析以及缺陷模式检测方便迅速的 查找。 北京邮电大学硕士学位论文 第三章c + + 程序全局分析框架 不同类型对框架前端需要的支持信息是不同的，简单的例如类型信息，变量的 取值范围，函数类型；复杂点的如定义使用链，别名信息，数据传播感染等，通过 将各个信息模块独立起来，并以控制流图和抽象语法树为基础数据结构，这样能够 将各模块单独开发并维护，有利于系统的多人并行开发。 1 8 北京邮电大学硕士学位论文 第四章c + + 程序类型分析及实现 第四章c + + 程序类型分析及实现 在分析c + + 语言时需要维护分析过程使用到的类型信息，包括变量、函数、类 以及用户自定义的类型。因为程序中的缺陷跟变量类型存在很大关联，如检测数组 越界错误时需要判断变量是否为数组类型以及数组下标的变量是否是整型。此外由 于c + + 本身语法就有二义性，例如图4 1 例程中仅根据语法分析结果难区分表达式 语句( e x p r e s s i o n s t a t e m e n t ) 和声t l 凋( d e c l a r a t i o n s ) t 3 7 1 ，只有在足够的类型支持下才能确 定正确的分析，c + + 中名字空间，多继承等语法也存在二义性。 图4 - 1c + + 语法二义性示例 其次，跨函数的全局分析，仅知道每个变量的类型还是不够的。因为在c + + 语 言中支持自定义类型( t y p e d e f ) ，子类型以及函数重载和虚函数，要在静态的时候确 定函数之间调用关系，必须建立类型的关系并且能够推导出表达式的类型。由于c + + 是面向对象的语言，有着父子类型的区别，而且子类型可以隐式转换为父类型。因 此类型系统的目的不仅是根据名字确定对应类型，还需要维护类型之间的结构关系 ( c l a s sh i e r a r c h y a n a l y s i s 3 8 】) ，以及判断类型是否等价或匹配。 4 1 类型分析和推导 对于c + + 这种面向对象的静态类型语言，在构建类型系统时，首先尽可能的从 1 9 北京邮电大学硕士学位论文 第四章c + + 程序类型分析及实现 用户代码中抽取类型信息，建立全局独立的类型系统和类型结构。因此我们设计c + + 语言中类型系统如图4 2 所示，其中c p 脚e 是d t s c p p 中可识别的全部类型的 公共抽象父类。c p p t y p e b a s e t y p e 对应c + + 中出现的所有基本类型，包括c h a r 、b o o l 、 s h o r t 、i n t 、f l o a t 、d o u b l e 、l o n g 等常用类型。c p p t y p e _ _ q u a l i f i e d 类对应着c + + 语言 中用c o n s t 、v o l a t i l e 等修饰符修饰的类型。 d c p p _ t y p h y、 c p p t y p e _ b s e t y p c r p t y 辨q u - i i r i i c p p t y l m _ a d d r e m l c p p t y p e _ s t m c tl c p p t y p ee m u - i c p i p t y p e _ a b i p m l e r i i c p r t y p _ t y p d r ii c p p t y i - u n l o r e l c p i r r y p e _ u m k o w m l iii |lil li ill llij ?。 伞 。 l c p p t y 一_ c l m m il c p p t y p ea r r i y li c i p l r f y p e _ p 删i e r l ii l i il iillll 图4 - 2d t s _ c p p 中c + + 语言类型关系 考虑到c + + 语言中s t r u c t 和c l a s s 关键字区别较小( 仅在类默认访问属性上有差 别) ，我们用c p p t y p es t r u c t 表示结构体，而c p p t y p 作为它的子类表示c+class 中的类类型，c p p t y p e记录本结构体内所有成员的字节大小和对齐问题( 为 后续计算指针区间大小_ ，s t r 以u c 及ts i z e o f 运算符准备) ，以及本结构体的所有父类列表， 以便类型推导时构建出类结构图。同样在d t sc p p 系统区间运算中我们将指针和 数组看做可以相互转换的变量，因此我们用c p p t y p e来表示抽象的指abstpointer 针类型，而c p p t y p e ： 和 作为具体子类分别对应数组和指针_ a r r a yc p p t y p e p o i n t e r 类型，另外c p p t y p e本身还记录了数组元素的类型和数组的维数。此外 、 _ a r r a y c p p t y p c _ a d d r e s sc p p t y p c _ e s u m 、c p p t y p c _ u n i o n 分别对应c 抖语言中的引用， 枚举和联合类型，而c p p t y p e是为了在分析过程中遇到无法识别类型或者unkown 类型识别出错时设计的，增强系统的容错性。 类型系统还必须能够确定每个类型的大小，因为在c + + 语言中大量的使用s i z e o f 运算符来计算类型的大小，在动态分配内存时也需要类型大小。由于函数调用参数 和异常匹配，也涉及到不同类型之间的匹配和转换问题，因此类型系统根据c + + 标 北京邮电大学硕士学位论文 第四章c + + 程序类型分析及实现 准定义的隐式类型转换和类型匹配规则来判定函数匹配和异常捕获时的匹配。 实现时，简单的变量和符号我们可以通过在语法树上查找和遍历来确定其类型， 但是c + + 中大量的表达式语句的类型却无法这样获得，在后续的函数调用分析以及 缺陷模式检测时常需要确定某指定表达式的类型。因此在获取单独变量类型之后， 我们通过对抽象语法树进行后序遍历，利用h i n d l e y - m i l n e r 3 9 】【加1 类型推导算法，推 导出所有表达式节点的类型。图4 3 用简单的入系统演示c + + 中表达式类型推导规 则 墨 i r a r 】删 一删工z 望丝警? l 卫皿坦 a p p 删 - 一删q 吃0 2 堕型堕塑誓盘世l 堕碰凸 o p t k i k - b m le l o p t e , ：f 3 卫立睾譬型l 罢盥 【c a s t 删 r h 删c a s t ( e 1 ) ：吃 。” 图4 - 3c + + 中表达式类型推导规则 其中r 是绑定类型的上下文环境，在此指全局的类型系统，而r 则是程序中定 义的类型，e 是程序中的表达式。y mj 删规则从类型系统中确定当前变量的类型， 【a 】瞪j 删规则是针对根据函数的类型来确定函数调用表达式返回值的类型， o p t n m 是确定c + + 语言中根据二元操作数的类型确定操作符表达式的类型，卜酗l j 删规则 用于推导程序中强制类型转换之后表达式的类型。由于c + + 中的大部分运算符可以 重载，虽然运算符的本质也是函数，但是为了便于在不同的语法树节点上应用推导 规则，我们将他们分开考虑。 在d t sc p p 实现中我们是对抽象语法树进行遍历获取这些类型信息，通过对 语法树两次遍历来收集和推导类型信息。第一次访问记录出现在语法树中的所有类 型，包括c + + 自身的类型以及用户自定义的类型，为了简化，我们采用自顶向下的 访问顺序简化需要访问的节点数目，仅仅访问与类型相关的节点。第二次访问推导 程序中变量和表达式的类型，采用自底向上的访问顺序，首先确定所有单独变量的 类型，然后利用上面的算法向上推导出所有表达式的类型，简便起见，我们将表达 式类型记录在其对应的语法树节点上。 其中第二次遍历的访问者类e x p r e s s i o n t y p e f i n d e r 结构如图所示，d t sc p p 北京邮电大学硕士学位论文 第四章c + + 程序类型分析及实现 中表达式相关的抽象语法树节点均继承自抽象类a b s t r a c t e x p r e s s i o n 。 e x p r e s s i o n t y p e f i n d e r 实现了对所有跟表达式有关节点的处理，包括算术表达式、逻 辑表达式、布尔表达式以及函数调用表达式等，此外还有复杂结构体的表达式以 算术表达式为例，推导算法实现为： p u b l i co b j e c tv i s i t ( a s t a d d i t i v e _ e x p r e s s i o nn o d e , o b j e c td a t a ) s u p e r v i s i t ( n o d e , d a t a ) ；, c p p t y p ec u r r e n t = n u l l ； l i s t o p e r a t o r = n o d e g e t o p e r a t o r t y p e o ； f o r ( i n ti = o ；i n o d e j j t g e t n u m c h i l d r e n ( ) & & i o p e r a t o r s i z e ( ) + l ；it - + ) a b s t r a c t e x p r e s s i o na b s t = ( a b s t r a c t e x p r e s s i o n ) n o d e j j t g e t c h i l d ( i ) ； i f ( c u r r e n t n u l l ) c u r r e n t = a b s t g e f f y p e o ； ) e l s e c u r r e n t = c a s t b a s e t y p e ( a b s t , c u r r e n t , a b s t g e t t y p e o , o p e r a t o r g e t ( i - 1 ) ) ； ) n o d e t t y p c ( c u r r 哦 r e t u r nn u l l ； ) 北京邮电大学硕士学位论文第四章c + + 程序类型分析及实现 侈s o f t t e 5 t s y m b o l t a b l e c p p e x p r e s d o n t y p e f i n d e r 镌；浮瓢穆i 蕊：露黟强v ：一磁辨匆哆馔簪孽。疆； 白o b j e c tv i 5 | t ( a 5 t e x t e r n a i ! d e c l a r a t j o nn o d e ，0 9o b j e c tv i d t ( a s t a d d i t i v e e x p r e s s i o nn o d e 0 oo b 皿tv i s i t ( a 5 t m u l t i p l k ：a t i v e _ e x p r e s s i o nn o d o b j e c tv i s i t ( a s t a n d _ e x p r e s s i o nn o d e o b j e c t 9o b j e tv i s i t ( a s t a s s i g n m e r c e x p r e s d o nn o d e j oo b j e c tv i s i t ( a s t c a s t _ e x p r e s s i o nn o d e , o h j e t 9o b 如c tv i s j t ( a s t c o n d i t j o r l a i _ e x p r e s s i o nn o d e , l o b j e c tv i s k ：( a s t c o n s t a n tr l l o d e j fo b j e c td a t a ) o b j e c tv i d t ( a s t c o n s t a n te x p r e s s i o nn o d e j0 0 b i e c t 哦( a s t d e l e t e e x l x e s s i o nn o d e ，o b i oo b j e c tv i s i t ( a s t e q u a 艟ye x p r e s s i o nr l l o d e t l0 o b j e c tv b i l ：( a s t e x c k i s i ，e _ o w _ e x p r e s s i o nn o d o b j e c tv i s i t ( a s t e x p r e s s i o nr l l o 出jo b j e c td a t a ) 痧o b j e c tv i s i t ( a s t q u a l i f i e d _ dn o d e ，o b ：i e c td a b ) 痧o b j e c - tv i 5 t ( a 5 喇：e x 够s mn o d e jo b 砖 td n a m e o e d 曹a t j o n5 e i d l i n c o m t y p e ( n a m d 墩 o b j e c t1 ，i 绒( a 5 t n c l il s e 9 r ! e x p r e 5 5 i o nr d d e o b 两：tv 酸( a 5 t 1 0 9 i c a i a n d j x p r 如1n o l c k j o b j e c tv i s j l ：( a s t i o g k ：a l _ o re x p r e s s i o nn o d e oo b j e c tv i s i t ( a s t n e w e x p r e s s i o nn o d e jo b 虹 9o b j e c tv i s i t ( a s t p m _ e x p r e s s i o nn o d e jo b j e c t 图4 - 4 推导表达式类型的访问者类 最后类型系统应该独立于分析单元的中间表示，因为类型信息会在整个分析过 程中用到，只有全局独立才能适应分析规模的变化和效率提高，通过合理的组织可 以将类型信息单独保存以实现递增的分析。 4 2 程序依赖性分析 在全局分析中，只有确定函数间依赖关系，按照控制流和数据流顺序才能计算 出准确有效的函数摘要信息。通常是建立全局控制流图i c f g ( i n t e r p r o c e d u r a l c o n t r 0 1 f l o wg r a p h ) 4 ，然后基于i c f g 进行数据流和控制流分析。但是这样需要将 所有的程序一次性分析才能得到完整的i c f g ，效率过低。 根据c + + 自身特点，我们可以根据头文件的包含关系初步确定文件之间的依赖 关系，然而这种分析方式太过于粗略，很难推广到其他语言分析中。我们根据分析 单元的控制依赖关系定义了全局分析单元的控制依赖图c d g ( c o n t r o ld e p e n d e n c e 北京邮电大学硕士学位论文 第四章c + + 程序类型分析及实现 g r a p h ) ，其中分析单元之间的依赖是指由于函数调用而产生的控制流依赖，没有考 虑数据流的依赖关系。其中计算全局程序依赖的算法如下： s t e p l 分析全局的函数调用关系，建立全局中函数的调用关系图。 s t e p 2 跟据全局函数调用关系，判断函数所对应的分析单元之间的依赖关系。 s t e p 3 对c d g 进行拓扑排序，优先选择依赖其他单元的分析单元并从图中移 去加入最终分析单元顺序表中，如果c d g 中不存在环，可得到完美的拓扑排序结 果，由此得到分析单元分析顺序，退出。如果存在环，则转到s t e p 4 。 s t e p 4 从入度为0 的节点开始，通过深度排序，对当前的c d g 图查找一个环， 并对根据相应破环策略打破这个环，转入s t e p 3 c d g 中的依赖环通常是函数或者类之间的交互引用导致，可以分为两种：一种 是隐式递归，一种只是文件中的不同函数之间调用，因此在s t e p 4 中的破环策略， 我们可以随机的选取环中的条边来，也可以根据环中分析单元的依赖关系，选取 边权重小的来破环。从软件设计角度来看，根据类的职责原则和模块独立原则，应 该尽量避免多个类之问的交互引用，因此程序中不大可能出现节点数很多的环，通 过实验分析也验证了这点，我们对多个开源项目的分析，通常环中节点的个数都是 在3 5 个之间，因此可以将依赖环中的分析单元一次读入内存同时处理，在空间和 时间上都是可以接受的，而且可以避免文件反复读写和函数信息计算的不准确。 具体设计如图4 5 所示，在第一次预分析过程中记录所有函数的节点并用 m e t h o d n o d e 表示，其中每个m e t h o d n o d e 与每个m e t h o d 一一对应m e t h o d 类是 c + + 中函数( 包括类成员函数，普通全局函数) 唯一对应的实体，其中记录了函数 名，函数参数列表，函数返回值等信息，足够标识被测代码中的函数，被保存在全 局上下文中，在第五章函数摘要中也会大量涉及到该类。每个m e t h o d n o d e 对应着 函数调用有向图上的一个节点，包含该函数调用的其他函数的节点，也就是当前函 数调用的其他函数。通过a d d c a u 方法会增加被调用函数到m e t h o d n o d e 上面去。 i n t c r c a l l g r a p h 是全局函数集合类，它通过i n t e rm e t h o d s 成员属性包含了当前 分析工程中出现的所有函数，并提供了计算c d g 的方法，g e t a n a l y s i s t o p o r d e r 会返 ，、 回一个按逻辑顺序排序的分析单元列表。 此外i n t e r m e t h o d v i s i t o r 访问者是遍历当前分析单元抽象语法树来建立调用关系 的访问者，对于每个a s t f u n c t i o nd e f i n t i o n ，a s t c t o rd e f i n i t i o n ，a s t c t o rd e f i n i t i o n 等 抽象语法树节点，会创建一个m e t h o d n o d e 。在出现函数调用的a b s t r a c t e x p r e s s i o n 2 4 北京邮电大学硕士学位论文第四章c + + 程序类型分析及实现 节点中利用m e t h o d n o d e 的a d d c a l l 方法来建立函数调用关系。 g f f t t e s t i n t e r p r o c p p i n t 甘c 6 _ g r h 口5h a s h 5 e t i n t e r m e t i 嬲 9s o f t t e s t i n t e r l ”o c p p i n l ：e r m e t h o d v t s i t o r nsh a s l 惭 i n t e r _ 瞧t cm e t h o d n o d ec u r r m e t h o d a 吐c o l o r _ w h i t e 9o b j e c tv i