（计算机软件与理论专业论文）cc语言程序切片中的指针别名分析.pdf

摘要 本论文主要研究了c ，c + + 语言程序切片中的指针分析算法。在安全性分析工 具的设计中，我们采用程序切片技术进行安全性分析。当进行数据流分析时，指 针的出现会引起到达一定值的不确定，影响数据流分析的精度。指针别名分析确 定指针变量可能的指向，从而缩小假设的范围，使数据流分析更加准确。 本文实现了一个流敏感的过程内指针别名分析算法。在实现算法的过程中， 首先利用g c c 编译系统的前端将源程序转换为抽象语法树，再从中提取出指针赋 值语句和函数调用语句里的指针信息并保存在控制流图里，最后使用一个迭代的 算法来实现别名分析。本文还讨论了跨过程分析算法的基本框架。文中的指针算 法可以处理c c + + 语言主要的数据类型，但在处理数组时只能把数组作为一个整 体对待而不能区分其元素。 关键词：指针分析别名程序切片抽象语法树控制流图 a b s t r a c t t h i sp a p e rs t u d i e s p o i n t e ra n a l y s i si n t h ep r o g r a ms l i c i n go fc c + + p r o g r a m s l i c i n gt e c h n o l o g yi s u s e di nt h e d e s i g no ft h es e c u r i t ya n a l y s i st 0 0 1 i nd a t af l o w a n a l y s i s 。t h ee x i s t e n c eo fp o i n t e rw i l l m a k er e a c h d e f i n i t i o ni n d e t e r m i n a b l e s ot h e p r e c i s i o no fa n a l y s i sm a y b e a f f e c t e d b yp o i n t e r a l i a sa n a l y s i s ，w ec a nm a k eo u tw h i c h o b j e c t st h ep o i n t e rm a yp o i n tt o ，s ot h a tw e c a nl e s s e nt h ea s s u m e ds e ta n di n c r e a s et h e p r e c i s i o no f d a t a f l o w a n a l y s i s i nt h i s p a p e r ，a f l o w - s e n s i t i v e i n t r a - p r o c e d u r ep o i n t e ra n a l y s i sa l g o r i t h m i s i m p l e m e n t e d t oi m p l e m e n tt h i sa n a l y s i s ，f i r s tt h es o u r c ep r o g r a mi st r a n s f o r m e di n t o a b s t r a c ts y n t a xt r e eb yt h ef r o n te n do fg c c c o m p i l e r s e c o n dp o i n t e ri n f o r m a t i o ni s e x t r a c t e df r o mt h ep o i n t e ra s s i g n m e n ts t a t e m e n ta n di sr e c o r d e di nt h ec o n t r o lf l o w g r a p h f i n a l l y ，a ni t e r a t i v ea l g o r i t h mi si m p l e m e n t e d h o wt oe x t e n dt h ea n a l y s i st oa n i n t e r - p r o c e d u r ep o i n t e ra n a l y s i si sa l s od i s c u s s e d t h ea l g o r i t h mc a nd e a lw i t hm o s t d a t at y p e so fc c + + w h e n d e a l i n gw i t ha r r a y t h ea n a l y s i sc a no n l yr e g a r da na r r a ya s aw h o l ea n dc a n td i s t i n g u i s ht h ee l e m e n t so f a n a r r a y k e y w o r d ：p o i n t e ra n a l y s i s a l i a s p r o g r a ms l i c i n g a s tc f g 创新性声明 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得西安电子科技 大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究工作所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文若有不实之处，本人承担一切相关责任。 本人签名：圣煎日期：亟! ：! ! ! 兰 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。 本人签名： 导师签名： 圣鲎日期：塑h 生 蛆 第一章绪论 第一章绪论 1 1 研究背景 随着网络技术的发展和自由软件的广泛使用，软件的安全变得越来越重要。由 于计算机的安全性隐患( 包括无意的和人为的) 大量存在于软件系统中，如系统 入侵、信息窃取、病毒、以及由于程序设计语言自身问题造成的各种安全漏洞等， 使得在软件的使用阶段会发生意想不到的错误，从而造成重大损失。 对于自主开发的软件，主要可以通过测试来检查所有可能的不安全因素。这就 需要对软件的功能、特性等具有深刻了解，并且根据软件特性设计完备的测试集。 而对于在实际使用中常常见到的第三方软件，往往只能得到其代码，对其特性并 不了解，不能采用这种动态测试的方法。因此，如何能在静态( 不运行) 时尽量 检测出软件的安全性问题，避免不必要的损失，成为当前计算机安全领域中需要 研究的一个重要课题。 1 1 1 研究目的 项目总的研究目的是安全性分析，重点是静态解决广泛应用的程序设计语言 c c h 的程序分析技术和面向不同领域的软件安全模式构建技术。图1 1 为整个安 全性分析的系统框图，该系统将安全性分析抽象为两个主要模块，即提取源程序 信息的静态程序分析部分和定义安全规则的软件安全模式部分。此框架将与安全 相关的具体模式从程序分析中剥离出来，从而以不同的方法解决最适合解决的问 题。 图1 1 安全性分析系统的结构图 框图的输入为c c + + 源程序。因为c c + + 是编写系统程序的主流语言，c c + + 语言在多个领域得到了广泛的应用，同时c c + + 由于其自身的语言特性，在提供 c ，c + + 语言程序切片中的指针别名分析 给程序员对系统底层( 如对内存，外设) 灵活的控制能力的同时，也带来了一些 潜在的安全性问题，如指针的错误使用，会带来内存漏洞。所以我们选择c c + + 语言编写的源程序作为安全性分析的目标语言。 安全性分析的目的是发现程序中的安全漏洞，因此需要寻求不同安全性漏洞的 安全模式并构建安全性规则。分布式环境下的安全性漏洞大多出现在以下几个方 面：与c c + + 类型机制漏洞相关的访问控制问题，如数组越界( 缓冲区溢出) 、 指针非法或无效引用、不加限制的类型转换等；与多进程相关的并发控制问题， 如共享内存的不一致、超时死等、缺少异常处理等；与分布式环境相关的信息 流问题，如不明信息的流入或大量信息的流出等。对于上述安全性漏洞，可按如 下步骤进行安全模式的认定和安全性规则的构建。确认漏洞的类型、表现形态、 危害方式等；根据对安全性漏洞的处理策略确认各类安全漏洞的安全模式并构 建安全性规则；建立安全性规则与对应程序分析方法的结合方式。 本文主要讨论1 1 安全性分析系统框图中的灰色方框部分，即静态程序分析部 分。在安全性分析中，静态程序分析部分将程序的特定信息提取出来，以便和安 全性规则相匹配，从而发现源程序中的安全漏洞。只有在静态分析抽象出程序的 信息之后，安全性规则才可以作用于这些信息之上，从而发现系统中的安全漏洞。 1 1 2 程序切片( p r o g r a ms l i c i n g ) 程序分析( p r o g r a ma n a l y s i s ) 技术通过静态分析来预测在程序执行中动态产 生的值和性能的集合，计算出近似解1 3 1 。程序分析不考虑程序运行的实际数据及特 定的执行环境，它分析程序或系统在任何实际执行中都成立的那些特性。程序分 析早期多用于编译器的优化，现在也常用于软件安全特性的验证、程序调试、软 件维护等。 程序切片是一种分析和理解程序的程序分析技术，它通过对源程序中每个兴 趣点分别计算切片来达到对程序的分析和理解。程序切片技术在程序调试、测试、 程序理解、逆向工程和软件维护等方面有着广泛的应用。 1 1 2 1 程序切片的概念和国内外主要算法 m a r kw e i s e r 提出了最初的程序切片概念f 。j 研。w e i s e r 对切片准则和程序切片 进行了定义。程序p 的一个彩带麓彬( s l i c i n gc r i t e r i o n ) 是一个二元组 ，n 是程序p 中的一个状态，v 是p 中变量的一个子集。关于切片准则 的程垆勿 芹s 是源程序简化后的可执行程序，通过去除程序p 中的一些语句丽得到，s 只保 留了p 的部分特性。程序p 关于准则仳v ) 的切片s 必须满足以下性质：对给定值， 第一章绪论 p 终止时，s 也终止；对v 中变量，无论何时执行相应于结点n 的语句，用p 和s 都能求得相同的值。 根据计算切片时采用可获得的静态信息还是动态信息，可将程序切片分为静态 切片与动态切片。静态切片不考虑程序的输入和运行的环境，而动态切片却与于 特定的测试用例有关。基于项目的要求，我们采用静态切片技术。 莓稳静怒现竞镪主要途径奄求解数据流方程，计算信息流关系以及翻甬程亭 j 谨：赫唇乳w e i s e r 的切片方法是基于数据流方程的，它根据数据流和控制流依赖， 计算间接相关语句的连续集而获得切片。b e r g e r e t t i 和c a r t e 提出根据信息流关系 来定义切片，这些信息流关系来源于语法制导方式的程序【1 0 】。信息流关系是以语 法制导、自下而上的方式计算的。这里不对信息流的方法加以介绍。o t t e n s t e i n 提 出了基于程序依赖图的静态切片方法j 。这种方法易于理解，并且具有一定的效 率和精度。因此我们利用基于程序依赖图的方法来进行程序切片。 1 1 2 2 基于依赖图的程序切片方法 瘥臌劝图( p r o g r a md e p e n d e n c eg r a p h ，p d g ) 是一个有向图，其中的结点 对应于语句和控制谓词，边对应于数据和控制依赖。在p d g 中，将切片准则看作 一个结点v 。即结点v 对应于切片准贝l j ，其中n 是对应于v 的控制流图结点， v 是在v 处定义和使用的所有变量的集合。对于单过程程序，关于某个准则的切 片由图中所有可到达v 的结点组成。这样，程序切片的问题就转为程序依赖图的 可到达性问题。只要在构造p d g 时保持p d g 结点与源程序的映射关系，即可从 这些结点找到源程序的相关部分，从而得到程序切片。 1 2 分层切片模型 构造面向对象程序的依赖图是非常复杂的工作，而且容易出错。我们参考李 必信等人的分层切片设计思想【1 2 】i t 3 t 4 1 1 15 1 ，设计了我们的切片工具框架。 1 2 1 基本思想 层次化的思想是解决许多软件问题的一个好方法。面向对象程序有着清晰的层 次结构。例如，c + + 语言类由方法和成员变量组成，方法由语句组成。因此，我们 可以用层次化的结构来构造分析工具，逐层构造依赖图并切片。我们按照逻辑结 构把c + + 源程序分为三个层次：类层、类中的方法和成员变量层、方法中的语句 和变量层。相应的把切片也分为类级切片和方法级切片。面向对象的分层切片算 法的主要思想就是分层计算关于切片准则 的程序切片。 c ，c + + 语言程序切片中的指针别名分析 我们定义程序中关于切片准则 v ，的类级切片为一些类的集合，这些类可能 影响程序点i 处的某个变量v 的值。同理，程序中关于切片准则 v ，的方法级切 片为可能影响程序点i 处的某个变量v 的值的那些方法和成员变量的集合。这样就 可以逐层对c + + 源程序进行切片。 ( 1 ) 在类层计算那些影响切片准则 的类，删除无关的类，得到类级切片 s ( p ) 。 ( 2 ) 成员变量和方法层在类级切片的基础上进一步计算单个类中影响切片准则 或受切片准则影响的成员方法和成员变量，删除无关的成员方法和成员数据，得 到方法级切片s ”( p ) 。方法级切片s 。( p ) 是类级切片s ( p ) 的子集。 ( 3 ) 语句和局部变量层在方法级切片的基础上，进一步计算方法中与切片准则 有关的变量和语句，删除无关的变量、语句和控制谓词等，得到整个面向对象程 序的切片s ( p ) 。这一层的工作与传统的面向过程程序切片是一样的。s ( p ) 是类间切 片s 8 ( p ) 的子集。 最后，得到的结果是面向对象程序关于切片准则 的程序切片s ( p ) 。 1 2 2 实现 切片工具的结构可以分为三层：语法分析层，依赖图生成层，切片层。如图1 2 所示。 图1 2 层次化切片工具的结构 第一章绪论 首先对c + + 源程序进行传统的语法语义分析，得到的信息用中间表示抽象语 法树来存储。 依赖图产生器利用抽象语法树中包含的信息分别生成类级依赖图、方法级依赖 图和语句级依赖图。 类级依赖图表示类或接口之间的继承，实现和创建关系。若类c 1 中直接创建 了一个属于类c 2 的对象，就说c 1 和c 2 有创建关系。如果类a 中直接创建了类 b 的对象，则a b 之间有一条双向的“创建边”。如果类b 继承了类a ，则有一条 继承边从b 到a 。另外假设所有的函数和全局变量都属于一个虚拟的类s t a t i c 。 方法级依赖图表示类成员变量和成员函数之间的两种关系：( 1 ) 多个成员方法共 享某些成员变量而形成的直接定义或使用关系，简称为m s v 关系( m e t h o d ss h a r i n g v a r i a b l e s ，m s v ) ；( 2 ) 通过调用其它方法来间接使用成员变量而形成调用关系， 简称为c r v 关系( c a l lr e l a t i o n v a r i a b l e s ，c r v ) 。在方法级依赖图中， 1 如果一个类的方法m 使用了某个变量i ，则从m 到i 有一条使用边； 2 如果一个类的方法m 定义了一个变量，则从i 到m 有一条定义边； 3 如果类c 1 的方法m 1 可能调用类c 2 的方法m 2 ，则c 2 的所有子类的m 2 方法( 可能被覆盖) 的参数( 包含隐含参数) 有一条定义边到m 1 。 语句级依赖图采用传统的程序依赖图，在第二章将详细讨论语句级依赖图的生 成。 接下来在这三种依赖图的基础上逐级生成类级切片，方法级切片和程序切片。 类级切片根据切片准则 v ，去除一些无关的类。首先定位切片点i 所在的类c ， 然后根据类级依赖图找出c 结点沿创建边能够到达的结点集合a 以及从a 中的结 点出发沿继承边可到达的结点集合b ，a 和b 的并集就是所求的关于 的切片 s ( p ) 。 方法级切片在类级切片的基础上进一步去除无关的类和方法。由于基类的方法 和成员变量会被子类继承，因此在方法级切片中，首先根据切片准则 v 定位切 片点i 所在的方法的集合m ，然后根据方法级依赖图找出和m 中结点有m s v 和 c r v 关系的结点，这些结点就是关于 n e x t ，这些表达式都是访问路径。若两个访 问路径在语句s 的所有执行中都指向相同的存储空间，则称它们为必删名 ( m u s t a l i a s ) 。若两个访问路径在语句s 的部分执行中指向相同的存储空间，则 是可麟影窖( m a y a l i a s ) 。必然别名是可能别名的子集，如不加说明，本文中的“别 名”表示“可能别名”。 揩铲秀焰分笏( p o i n t e ra l i a sa n a l y s i s ) 旨在确定两个指针表达式何时会指向同 样的存储单元，即确定程序中的别名。对于语句+ p = i ，访问路径p 与i 别名，这个 别名关系可以用一个二元组 来表示。表示别名主要有完全别名对、压缩别名 对、指向关系以及别名图等几种方法。 寇佥影当矽( c o m p l e t ea l i a sp a i r s ) 直接存储所有的别名关系【 】。例如，对于 下面的语句 q = & p ；p = i ；r = i ； 有完全别名对p q ，p q ， 。 压缩勇铲当矽( c o m p a c t a l i a sp a i r s ) 仅存储那些基本的别名对【3 0 】。通过脱引用、 传递性和交换性导出新的别名对。对于3 1 的语句，用压缩法表示的别名集合为 ) ，其它的别名可以从压缩表示法中推导出来。 赭句关莠( p o i n t s t or e l a t i o n s ) 用指向对来指示一个变量指向另一个变量【i 9 】。 第三章指针别名分析 语句3 一i 可以得出指向关系( q ，p ) ( p ，i ) ( r ，i ) 。 我们的别名分析采用压缩别名对表示法，以减少分析的存储要求。在压缩表示 中，我们用命名对象( n a m e do b j e c t s ) 来代表存储位置的名称【3 5 】。这些名称既 可以是变量名也可以是分析中人为创建的表示内存地址的名称。例如，对于一个 用m a l l o c 分配的存储位置，我们将根据其文件名和行号产生一个名称来表示这个 位置。我们规定压缩别名对表示法的每个别名关系都满足以下两点： i 至少有一条访问路径是不包含脱引用的命名对象。例如 是不行 的。 2 任何访问路径没有一级以上的脱引用。例如 是不符合的。 因此，压缩表示法中的所有的别名关系都为 或 ，其中a 和b 为命 名对象。压缩表示法没有顺序之分， - - - 。 除了这些表示法之外，别名也可以用一种直观的形式来表示，就是别名图。勇矿 名母将包含指针脱引用的关系映射到图中。例如，语句3 1 的别名图如图3 1 所示， 其中结点对应于命名对象，边p 寸q 对应于别名关系 。别名图中的边基本上 对应于压缩别名表示法中的别名对。 图3 1 别名图 3 2 别名分析算法 本节给出一个跨过程指针别名分析算法框架【2 6 】，并给出一个实现这个框架的流 敏感算法。 数据流分析算法可以分为流敏感的和流非敏感的。流敏感的分析算法在分析过 程中考虑过程内的控制流信息，流非敏感的分析算法不考虑控制流信息。通常流 敏感的数据流分析算法较流非敏感的分析算法更精确。流非敏感的算法效率更高， 适用于那些采用流敏感算法不能提供更高精度的问题。指针别名分析也是数据流 分析的内容之一，本文采用流敏感的别名分析算法。 3 2 1 跨过程别名分析框架 常见的跨过程分析算法根据其跨过程分析技术可以分为跨过程控制流图【 1 引，调用图 2 0 1 2 2 1 ，和过程调用图t 3 0 1 1 2 5 1 。 跨过程控觏流圆( i n t e r - p r o c e d u r a lc o a 灯o 、f l o w g r a p h 。i c f g ) 嗣讽甩结南秘退 c ，c + + 语言程序切片中的指针别名分析 回结点将各自孤立的过程内的控制流图相连接，得到一张总的跨过程控制流图。 如果有较多的过程调用，i c f g 就可能会非常的庞大，从而效率和可扩展性差。i c f g 也不能区分同一个过程的不同次调用。 堀禺留( i n v o c a t i o ng r a p h ，i g ) 中的每个结点是一个过程调用点。函数调用是 i g 中从调用点出发的一条唯一路径。i g 从m a i n 函数开始递归处理每个函数调用， 使用自定义的m a p 和u n m a p 映射函数来对形参一实参配对，如图3 2 。由于调用 图递归处理函数调用，如果调用层次较多，i g 结点的数目会指数级的增加，导致 大量的内存需求，同时也需要很大的计算量来处理每个i g 结点的函数体。 调用进程被调用进程被调用进程 m a i n ( ) 沙 s t u ( ) ： 一 s t u ( ) 矽 b o o k ( ) ： 溢 圈3 2 调用圈不葸 也翟堀现雾( p r o c e d u r ec a l lg r a p h ，p c g ) 中的结点是一个过程，边是过程调 用点，如图3 3 。p c g 对每个过程f 定义过程入口和出口处的别名集合e n t r y f 年d e x i t f ， 迭代的更新这两个集合直到其收敛。在一次跨过程的迭代中，访问每个过程，计 算每个过程的过程内集合。当更新了当前过程的跨过程别名集合之后，就不再需 要过程内信息了。因此，用来计算过程内集合的空间可以在随后的跨过程阶段重 用。这样，通过仅要求当前分析集合的过程内集合减少了存储要求。因此，我们 采用过程调用图的别名分析算法。在数据流分析中，别名分析通常是最早需要p c g 的阶段，在别名分析中构造p c g 时开销最小。 c 在调用过程中 m a i n ( ) c i ：s t u ( ) ： c 2 ：s t u o ； l 过程调用图过程调用 e n t r y s t u ( 迭代更新 这两个集合) e x i t t u 圈3 3 过程调用图示意 在实现中，对每个过程f 定义了两个跨过程别名集合；e i l t r y f 为在过程a n 处 第三章指针别名分析 成立的别名关系，e x i t f 为在过程出口处成立的别名关系。由于这两个集合会被其 它过程更新和引用，因此称它们为跨过程别名集合。由于被调用的过程中可能存 在指针赋值，因此被调用的过程可能会影响调用过程在调用点后的别名。同样调 用过程中的别名关系也会影响被调用过程中的别名。这样，别名可以从调用点c 向被调用过程g 的e n t r y g ，或从被调用过程g 的e x i t g 到调用点后的程序点跨过程 传播。 本文选用b u r k e 等人在 2 6 1 q b 提出的跨过程别名分析算法框架，如图3 4 。 s 1 ：建立初始p c g 8 2 ： f o r 每个p c g 中的过程f ，l o o p s 3 ：初始化f 的跨过程别名集合 8 4 ： e n d l o o p s 5 ： r e p e a t s 6 ：f o rp c g 中的每个过程f ，l o o p 8 7 ： 使用跨过程别名集合( e n t r y f 和f 中的过程调用点) 计算f 的过程内别名集合 s 8 ： 使用f 的过程内别名集合，更新所有 表示f 对每个调用f 或被f 调用的过程的影响的 跨过程别名集合 8 9 ： e n d l o o p s 1 0 ： 使用新的函数指针别名更新p c g $ 1 1 ： f o r 每个在$ 1 0 中加到p c g 中的新过程f l o o p s 1 2 ：初始化f 的跨过程别名集合 s 1 3 ：e n dl o o p s 1 4 ：u n t i lp c g 和所有的跨过程别名集合收敛 图3 4 跨过程别名分析算法框架 s 1 - - $ 4 建立初始的p c g 并初始化跨过程别名集合，假设这些集合在初始时都 为空。$ 5 - - s 1 4 为迭代部分。该框架的主要特点为s 7 和s 8 中过程内分析与跨过 程分析的交错。$ 1 0 将由函数指针产生的新的边扩展到p c g 中。直到程序调用图 和跨过程别名集合收敛。该框架结合了别名分析和更新p c g 的过程。 框架的目的是计算跨过程别名集合及跨过程算法终止后( 跨过程别名集收敛) 最终的过程内别名信息。 3 2 2 流敏感的别名分析算法 我们用流敏感的跨过程别名分析算法3 1 来实现上一节的算法框架。 算法3 1 ：流敏感的跨过程指针别名分析算法 6 c ，c + + 语言程序切片中的指针别名分析 算法输入：初始的p c g ，每个过程的c f g ，已计算的静态别名 算法输出：跨过程别名集合，过程内别名集合，更新的p c g s 1 ：建立初始p c g s 2 ：f o rp c g 中的每个过程f l o o p s 3 ： e n t r y f = f 的静态别名) s 4 ： e x i t f = ( ) s 5 ： e n d l o o p s 6 ： r e p e a t s 7 ：f o rp c g 中的每个过程f ，l o o p s 8 ： r e p e a t s 9 ： f o r 深度优先遍历每个c f g 结点s ，l o o p 计算流敏感过程内别名： s 1 0 ： 用方程3 2 计算i n 。 s 1 1 ： i f s 为调用点t h e n s 1 2 ：f o rs 处的每个被调用过程g ，l o o p s 1 3 ： 用b a c k w a r d b i n d ；( e x i t g ) 和i n b 计算o u t , s 1 4 ： e n dl o o p s 1 5 ：e l s ei fs 为指针赋值t h e n s 1 6 ：用方程3 - 3 计算o u t , s 1 7 ：e l s e s 1 8 ： o u t , = i n 。 s 1 9 ：e n d i f $ 2 0 ：e n dl o o p $ 2 1 ：u n t i lf 的过程内别名集合收敛 $ 2 2 ： e x i t f 2 o u t l e t ( n e m 为f 的c f g 的结束结点) s 2 3 ： f o r f 中的每个调用点o ，l o o p s 2 4 ：f o rc 处的每个被调用过程g ，l o o p s 2 5 ： 使用f o r w a r d b i n d 。f ( 玩) 更新e n b h $ 2 6 ：e n dl o o p $ 2 7 ：e n dl o o p $ 2 8 ：e n dl o o p s 2 9 ： 使用新的函数指针别名更新p c g s 3 0 ： f o r 在$ 2 9 中加入p c g 的每个新过程f ，l o o p $ 3 1 ： 初始化e n t r y f 和e x i t f $ 3 2 ：e n dl o o p s 3 3 ： u n t i l 跨过程别名集合和p c g 收敛 图3 5 算法3 i ：流敏感的跨过程指针别名分析算法 算法3 1 要利用每个单独过程里的过程内控制流，因此它是流敏感的分析算法。 e n t r y f 初始化为f 中的静态别名，e x i t f 初始化为空集。下一节介绍静态别名。在算 第三章指针别名分析 法的跨过程部分，f o r w a r d b i n d ；将在过程f 中的调用点c 成立的别名集合映射到 被调用的过程入口的别名集合、b a c k w a r d b i n d ；将被调用过程出口的别名映射到紧 跟调用点c 之后的别名集合，3 3 2 节将介绍这两个映射函数。算法在s 6 $ 3 3 反复 遍历p c g 直到集合收敛。在每次对p c g 的遍历中s 2 2 使用过程内信息更新当前 所处理过程的e x i t 集合。s 2 3 一$ 2 7 中，通过对f o r w a r d b i n d ；( z n ，) 与e n t r y 。在上一 次遍历中的值求并集得到e n t r y g ，调用点之前的别名信息i i l c 后向传播到每个被调 用过程g 的入i = 1 。s 9 s 2 2 的部分为过程内分析。接下来的两节介绍算法的具体内 容。 3 3 别名的处理 c + + 中的别名可以分为：过程内静态别名，由u n i o n 等某些结构产生；过程内 动态别名，由指针赋值产生：跨过程别名，由函数的调用产生。不是每个语句都 会影响别名关系。只有指针赋值语句才会改变别名信息，其它控制流语句不会修 改别名信息。当存在过程调用时，由于被调用的过程里也可能含有指针赋值语句， 因此对于调用过程来说，在过程调用之后，别名关系也可能产生变化。因此一个 过程中指针赋值语句和过程调用语句可能对别名信息产生影响，我们研究这两种 语句引起的别名。 3 3 1 计算指针赋值语句的i n 和o u t 集合 如不考虑跨过程因素，则只有指针赋值语句才会改变别名关系。程序中其它语 句开始程序点的指针别名信息与结束点的相一致，即o m = i n 。流敏感的指针分析 算法遍历控制流图，遇到指针赋值语句则使用相应的方程计算别名关系。 定义3 1 ：指针赋值语句是左部表达式类型求值结果为指针类型的赋值语句。 指针赋值语句的执行结果是使赋值语句左部的指针变量所指向的目标发生改 变，从而使指针别名信息发生相应的变化。 定义3 2 ：i n 。和o u t 。分别为c f g 结点n 开始和结束的程序点处成立的别名集 合。 对于任何c f g 结点n ，有方程3 - 2 如下， n 。= u o u t 。 口e p r e d s ( n ) 方程3 - 2 说明i n n 是n 的所有前驱p 的0 集合的并集。 的所有结点都是成立的。 定义3 3 ：我们将指针赋值语句表示为“p i = q j ”的形式。 该式对于控制流图中 其中p i 为变量p 有i c ，c + + 语言程序切片中的指针别名分析 级脱引用的指针表达式，q j 为变量q 有j 级脱引用的指针表达式。 我们记“& ”运算符的脱引用级别为1 。例如，赋值语句+ p = a 可表示为”p 1 = a 0 ”， & a 记为”p o - a 一1 ”。 因此，对于表示为”p i = q j ”的指针赋值语句，有方程3 - 3 ， o u t = ”( 1 n 。一m u s r ( c o m p “t e a l i a s e $ ( p ，f ) ) 3 3 1 u 3 3 2 ；：g 端t e a h 。a s 嘶e p h , t ) 1 ) 计算方程3 - 3 需要获得指针赋值语句中“变量名+ 脱引用级别”的信息，4 1 节 讲述如何从抽象语法树中找出指针赋值语句，并将其表示为p i = q i 的形式。 方程3 3 表示指针赋值语句的o u t 集合是两部分的并集：i n 集合减去结点n 注 销的别名关系( 3 3 1 ) ，与结点n 所产生的别名关系( 3 3 2 ) 。3 - 3 2 的直观含义 为：对于别名图中从结点p 出发路径长度为i 的所有结点集合p 和从q 出发路径长 度为j + 1 的所有结点集合q ，指针赋值语句p i q j 使p 的每个元素到q 的每个元 素都有一条边。转换函数c o m p u t e a l i a s e s 使用h k 别名集合递归计算，它返回别名 图中从结点p 出发，路径长度等于i 的结点集合。c o m p u t e a l i a s e s 函数的计算将在 4 2 节详细叙述。在图3 6 的别名图中，若有指针赋值语句 。q = r ； 由c o m p u t e a l i a s e s ( q ，1 ) 得到 t ，c o m p u t e a l i a s e s ( r ，1 ) 得到沁v ) a 因此，这个赋值 语句引起新的别名图中的边t u ，t _ v ，也即压缩表示法中新的别名对 ， 。指针赋值语句“q = & r ；”由3 3 2 得到的别名对为 。 圈3 6 一个别名图 3 - 3 1 中的m u s t 也是一个函数，它找出被该赋值语句注销的那些别名关系。 m u s t 函数以c o m p u t e a l i a s e s 的结果集合p 为输入，返回一个满足下列条件的别名 集合：这个别名集合中的每个别名关系是p 中元素与一个确切表示运行时内存空 间的对象的别名。即，当分析中该指针变量仅指向一个对象的时候，认为它是一 第三章指针别名分析 1 9 个必然别名。用别名图来直观的理解就是：对于c o m p u t e a l i a s e s ( p ，i ) 得出的结点集 合p 中的每个结点a ，若a 只有唯一一条出边a 寸u ，则 在m u s t 集合中。对 于图3 6 ，m u s t ( c o m p u t e a l i a s e s ( p ，1 ) ) = m u s t ( s ，r ，t ) - ， ，因为s ，t 都只有唯一的出边，分别是s _ u ，t _ w ，因此u 和v 是确切表示运行时内存空间 的对象。而r 有多条出边，r 的指向是不确定的，因此r u ，r v 不在m u s t 集合 中。根据稳妥性的原则，对m u s t 的计算也应是稳妥的。对于m u s t ( ) ，定义它等 于所有的别名关系即整个i n 集合。 c o m p u t e a l i a s e s 也会返回空集。例如，对图3 6 有语句+ x = r ；此时不会产生 新的别名关系。在两种情况下c o m p u t e a l i a s e s 会返回空集： ( 1 ) x 未初始化，程序中存在对未赋初值的指针变量的脱引用。 ( 2 ) 还没有处理与x 有关指针表达式的那些语句。 由于算法要对控制流图反复迭代，( 2 ) 的情况会在下一次迭代中得到更新。 3 3 2 函数调用( 参数和局部变量) 在跨过程别名分析中，别名会从函数调用点正向( 调用者影响被调用函数) 或 反向( 被调用函数影响调用者) 传播。因此我们定义两个函数f o r w a r d b i n d 和 b a c k w a r d b i n d 来捕捉过程调用的影响，从而计算过程调用点处的别名集合。 f o r w a r d b i n d 将调用点c 处的有效别名关系通过c 的实参映射到调用点处被调用的 过程中，b a c k w a r d b i n d 将c 处被调用过程中有效的别名关系的集合映射成调用点 c 后有效的别名关系的集合。由算法3 2 ，使用f o r w a r d b i n d ；( i n 。) 更新e n t r y g ， 用b a c k w a r d b i n d 。r ( e x i t ，) 计算o u 。 本节给出跨过程别名分析中处理参数和局部变量的方法，如何将传值和传引用 参数和别名计算相结合。 3 3 2 1 值调用和复写一恢复参数( c a l l - b y - v a l u e c o p y - i n c o p y o u t ) 令a i 和为过程g 在c 点调用过程h 的第i 个实参或形参。 对于f o r w a r d b i n d ，当有值调用和复写参数时，只需考虑何时实参( a i ) 所包 含的值等于对象x 的地址： a r = 其中x 也可为实参。在这种情况下，f i 得到a i 的值， 这包括了形参直接包含对象地址的情况，女l l & x 。 对于b a c k w a r d b i n d ，当有值调用参数时，可在过程的结束忽略掉某些别名关 系，即所有那些满足其访问路径包含被调用过程中局部变量的别名关系。但是若 c ，c + + 语言程序切片中的指针别名分析 从被调用过程也可到达调用过程，例如存在递归，则这些别名关系不能忽略。因 此我们定义b a c k w a r d b i n d ；，这样在没有对调用和被调用过程的递归调用的情况 下，别名关系不会从调用过程的调用点传播回去。递归调用可以通过检查调用图 中是否有环来找出。 有恢复参数时，通过b a