一种基于离线约束图的指针分析方法

摘要

本发明公开了一种基于离线约束图的指针分析方法，包括两个阶段：离线分析阶段和在线分析阶段。在离线分析阶段，ADD首先构造离线约束图，其次在离线约束图中为每个结点定义并计算祖先集和后裔集，然后计算离线约束图对应的支配树，基于支配结点信息计算指针等价的顶层变量对信息。在线分析阶段，ADD一方面利用结点的祖先集和后裔集进行在线循环检测，另一方面利用指针等价的顶层变量对信息来降低分析过程中结点间指向信息的传播开销。与现有的基于包含的指针分析方法LCD相比，ADD能够在不影响指向信息精度的前提下提高指针分析的效率。

说明书

技术领域

本发明属于静态程序分析领域，涉及一种指针分析方法。

背景技术

指针分析是一种静态程序分析技术，它的目标是静态确定一个指针变量能够指向 哪些地址(变量或函数的存储位置)，也就是静态确定一个指针变量在程序运行时所 有可能的值。指针分析以程序源代码(或某种中间代码表示)作为输入，输出该程序 所包含的指针指向信息。由于指针(引用)在C/C++(Java)程序中被广泛使用，许 多静态程序分析技术需要根据指针指向信息来解析程序中包含的间接引用，指针分析 的结果直接影响其它静态程序分析技术的有效性，指针分析作为许多静态程序分析技 术的使能技术一直是一项重要的议题。

目前软件系统和工业级源代码库的规模越来越大(如数百万代码行甚至数千万代 码行)，对于动态性较弱、使用指针较少、规模较小的程序，现有的指针分析技术已 经较为成熟，可以很好地分析处理这些程序。然而，对于规模更大、动态性更强的程 序，现有指针分析算法还存在许多问题，需要进一步地研究：(1)如何在不影响指向 信息精度的条件下，提高指针分析算法的效率和可扩展性；(2)如何提高指针分析算 法的精度，同时尽可能地保证算法的效率和可扩展性；(3)如何设计适用于并发程序 的指针分析算法等。

在设计一个指针分析算法时，首先需要对程序的元素(如程序语句，函数，结构 体等)进行建模，这些建模策略也被称为分析维度；如流敏感性，上下文敏感性，域 敏感性等。从理论上来说，精确的指针分析是非常困难的：当允许动态内存分配时， 过程内流敏感指向分析是不可判定的；当不允许动态内存分配时，过程内流敏感指向 分析是PSPACE-完全问题；当不允许动态内存分配时，对于包含任意数目指针间接访 问操作符的程序来说，流不敏感指向分析是NP-Hard问题。这些复杂性结论表明现有 的指针分析算法都是近似算法，都需要在算法的精度、效率和可扩展性之间进行折衷。

流敏感性和上下文敏感性是两个独立的分析维度；流敏感性关注的是分析算法如 何处理函数内的控制流信息：流敏感分析和流不敏感分析；上下文敏感性侧重的是分 析算法如何处理函数间的调用信息：上下文敏感分析和上下文不敏感分析。一个指针 分析算法根据其处理函数内的控制流信息时所采取的策略可以被划分为流敏感分析 或流不敏感分析；同时根据其处理函数间调用信息时所使用的策略可以被划分为上下 文敏感分析或上下文不敏感分析。因此，同时考虑流敏感性和上下文敏感性，现有的 指针分析算法将被划分成以下四类：流不敏感上下文不敏感算法、流不敏感上下文敏 感算法、流敏感上下文不敏感算法、流敏感上下文敏感算法。

总的来说，基于合并的流不敏感上下文不敏感算法(Steensgaard指针分析)具有 较好的效率和可扩展性(scalability)，但是指针分析的精度很差；基于包含的流不敏感 上下文不敏感、流敏感上下文不敏感算法和流敏感上下文敏感算法具有更好的精度， 但是指针分析过程的效率和可扩展性将会变得很差。为了在算法的精度、效率和可扩 展性之间获得一个较好的折衷，基于包含的流不敏感上下文不敏感算法一直是指针分 析领域的研究热点之一。

对基于包含的流不敏感(上下文不敏感)指针分析算法的研究主要是围绕如何设 计有效的在线循环检测技术，因为在线循环检测技术能够在不影响指向信息精度的条 件下，显著地提高基于包含的指针分析算法的效率和可扩展性。

对基于包含的流不敏感(上下文不敏感)指针分析算法来说，在线循环检测过程 需要被多次触发；因此，在设计在线循环检测技术时就存在一个难点：如何确定在线 循环检测的频度来控制指针分析算法的开销，也就是说，在约束求解的过程中，决定 什么时候触发循环检测。在确定在线循环检测的频度时存在两个极端：一方面，如果 每添加一条有向边到约束图中，约束求解算法就触发一次循环检测；在这种情形下， 很多循环检测过程是不必要的，因为约束图此时并没有形成循环，过早触发循环检测 将产生大量不必要的时间开销用于搜索约束图；另一方面，如果约束求解算法没有及 时触发循环检测，也就是说，有向边不断地被加入到约束图中，约束图存在很多未被 检测出来的循环；在这种情形下，结点的指向信息将沿着这些循环被冗余传播。没有 及时触发循环检测将会影响算法的效率以及会减少循环检测和合并本身所带来的收 益。因此，在设计一个在线循环检测技术来改进基于包含的指针分析算法时，设计者 需要在循环检测的开销和指向信息沿着未被检测出来的循环被冗余传播的开销之间 做出权衡，从而提高基于包含的指针分析算法的效率和可扩展性。不同的在线循环检 测技术代表了对基于包含的指针分析算法的不同改进。

Hardekopf等人提出了一种有趣的在线循环检测技术LCD(lazycycledetection)， Hardekopf等人基于这种在线循环检测技术实现了一个基于包含的指针分析算法，称 为LCD算法。LCD基于如下策略进行在线循环检测：在沿着有向边进行指向信息传 播之前，LCD首先判断这条有向边的源结点和目的结点是否具有相同的指向集；如果 这两个结点具有相同的指向集，LCD认为此时约束图中存在一个循环，并触发深度优 先搜索过程去寻找约束图中存在的循环。LCD来源于这样一个想法：因为在指针分析 算法终止时，同一个循环中的结点将具有相同的指向集；所以，当有向边的两个结点 具有相同的指向集时，约束图中很可能存在循环。LCD的优点在于：与其它在线循环 检测技术相比，LCD采用的循环检测策略是惰性的，也就是说，只有在约束图中非常 可能存在循环的情况下，LCD才会触发循环检测。这种在线循环检测策略极大地降低 了在线循环检测过程本身的开销，实验结果表明，与其它在线循环检测技术相比，LCD 的实际效果很好。LCD的缺陷在于：(1)这种在线循环检测策略的有效性依赖于这样 一个假设：有向边的两个结点具有相同的指向集通常是因为这两个结点在同一个循环 中。如果上述假设经常不成立，LCD的在线循环检测策略将导致LCD在约束图中不 存在循环的情况下去搜索约束图，这将极大地影响指针分析算法的效率；(2)对SPEC 2000测试集，绝大多数LCD触发的深度优先搜索过程是没有发现循环的(平均 99.7％)，也就是说，LCD触发的深度优先搜索过程绝大多数是多余的，只有极少数 的优先搜索过程能够发现并合并循环。因此，LCD的效率可以被进一步地提高，如果 可以显著地减少上述LCD触发的多余的深度优先搜索过程。由于在线循环检测策略 能够显著地提高基于包含的流不敏感指针分析算法的效率和可扩展性，因此，如何设 计更有效的在线循环检测策略(包括如何进一步改进LCD)仍然是个热点，值得进一 步深入研究。

发明内容

技术问题：本发明针对基于包含的指针分析算法LCD存在的不足，提供一种能 够在不影响指向信息精度的前提下提高指针分析的效率的基于离线约束图的指针分 析方法ADD。

技术方案：本发明的基于离线约束图的指针分析方法ADD，包括以下步骤：

(1)根据输入约束集，构造离线约束图；

(2)在所述离线约束图中触发一次深度优先搜索，得到一个有向无环图和多个 循环，并记录循环信息；

(3)在所述有向无环图中，根据结点的拓扑序计算每个结点的祖先集和后裔集； 同时在所述有向无环图中，利用LengauerandTarjan算法计算该图对应的支配树或支 配森林；

(4)在所述支配树或支配森林中，计算指针等价的顶层变量对信息；

(5)根据输入约束集，构造初始的在线约束图，然后在所述在线约束图中，将 与步骤(4)得到的顶层变量对信息对应的结点合并；

(6)首先利用同时满足如下条件的结点对优先级队列current进行初始化：(a) 结点的指向集为非空；(b)结点含有出边或者含有复杂约束，所述复杂约束为加载约 束或存储约束；然后基于工作集算法框架迭代处理current，得到指针指向信息。

进一步的，本发明方法中，步骤(3)中，计算一个结点p的祖先集的具体流程 为：

在所述有向无环图的转置图中，以结点p为根进行深度优先搜索，该搜索过程过 程中遇到的所有结点记为结点p在有向无环图中的祖先集；

计算一个结点p的后裔集的具体流程为：

在所述有向无环图中，以结点p为根进行深度优先搜索，该搜索过程过程中遇到 的所有结点记为结点p在有向无环图中的后裔集。

进一步的，本发明方法中，所述步骤(4)的具体流程为：

在支配树或支配森林中，检查每个点对(m,n)是否为指针等价的顶层变量对， 从而得到指针等价的顶层变量对信息，其中m为为支配树或支配森林的结点，n为支 配树或支配森林的结点；具体判断方法为，如果m与n同时满足下面三个条件，则m 与n是指针等价的顶层变量对，否则不是：

(a)n是m的直接支配结点idom(m)；

(b)m与n都是顶层变量；

(c)在离线约束图中，从n到m的所有路径都只涉及顶层变量结点，即从n到 m的所有路径不包含取地址变量结点或解引用结点。

进一步的，本发明方法中，所述步骤(6)中，基于工作集算法框架迭代处理优 先级队列current，是对优先级队列current中的结点逐个进行如下处理：

(i)当结点s不存在复杂约束时，直接进入步骤(iii)，当结点s存在复杂约束 时，按照如下方式添加新的有向边到在线约束图中：

对于每一个复杂约束，即加载约束u＝*s或者存储约束*s＝v，如果*s属于离线约 束图中的循环，则按照下列(a)的方式处理，如果*s不属于离线约束图中的循环， 则按照下列(b)的方式处理，其中，u和v是在线约束图中不同于s的结点：

(a)根据步骤(2)记录的循环信息(s，t)，首先对结点s的指向集中每个元素 w，分别进行w与t的合并，其中，t是在线约束图中不同于s的结点；然后将结点t 添加到current中，最后按照如下方式进行加边：

复杂约束为加载约束u＝*s时，进一步判断在线约束图中是否包含有向边t->u， 如果不包含，则添加新的有向边t->u，同时再次将结点t添加到current中，删除加载 约束u＝*s，否则，直接删除加载约束u＝*s；

复杂约束为存储约束*s＝v时，进一步判断在线约束图中是否包含有向边v->t，如 果不包含，则添加新的有向边v->t，同时将v添加到current中，删除存储约束*s＝v， 否则，直接删除存储约束*s＝v；

(b)根据结点s的指向集添加对应的有向边到约束图中，即，对结点s的指向 集中任一元素w按照如下方式进行加边：

对加载约束u＝*s，当在线约束图中不包含有向边w->u时，添加新的有向边w->u， 同时将w添加到current中，否则，就不做任何处理；

对存储约束*s＝v，当在线约束图中不包含有向边v->w时，添加新的有向边v->w， 同时将v添加到current中，否则，就不做任何处理；

(ii)首先进行取交集操作，即复杂约束为加载约束u＝*s时，对结点s的指向集 和结点u对应的后裔集进行取交集操作，复杂约束为存储约束*s＝v时，对结点s的指 向集和结点v对应的祖先集进行取交集操作，然后根据操作结果是否非空来决定此时 是否触发一次循环检测过程；

(iii)沿着有向边进行指向信息传播。

进一步的，本发明方法中，所述步骤(ii)中，根据结果是否非空来决定此时是 否触发一次循环检测过程的的具体方法为：

对于加载约束u＝*s，如果取交集操作的结果points-to(s)∩Descendant(u)是非空， 则在结点u处触发一次循环检测搜索；否则，在结点u处不触发循环检测搜索；

对于存储约束*s＝v，如果取交集操作的结果points-to(s)∩Ancestor(v)是非空，则 在结点v处触发一次循环检测搜索；否则，在结点v处不触发循环检测搜索。

本发明方法是结合离线约束图的信息对基于包含的指针分析算法LCD进行改进。

有益效果：本发明与现有技术相比，具有以下优点：

(1)LCD基于如下策略进行在线循环检测：在沿着有向边进行指向信息传播之 前，LCD首先判断这条有向边的源结点和目的结点是否具有相同的指向集；如果这两 个结点具有相同的指向集，LCD认为此时约束图中存在一个循环，并触发深度优先搜 索过程去寻找约束图中存在的循环。LCD的缺陷在于：(a)这种在线循环检测策略的 有效性依赖于这样一个假设：有向边的两个结点具有相同的指向集通常是因为这两个 结点在同一个循环中。当上述假设经常不成立时，LCD的在线循环检测策略将导致 LCD在约束图中不存在循环的情况下去搜索约束图，这将极大地影响指针分析算法的 效率；(b)对SPEC2000测试集，绝大多数LCD触发的深度优先搜索过程是没有发 现循环的(平均99.7％)，也就是说，LCD触发的深度优先搜索过程绝大多数是多余 的，只有极少数的深度优先搜索过程能够发现并合并循环。因此，LCD采用的在线循 环检测策略在判断在线约束图的循环构成时机这一问题上是不充分的。与LCD相比， ADD进行在线循环检测的策略混合了离线约束图的结构信息；这些结构信息使得 ADD在判断在线约束图的循环构成时机这一问题上具有更好的精度，因此，ADD能 够进一步地提高LCD检测循环的质量(即减少LCD算法触发的那些循环检测结果是 约束图中不存在循环的循环检测过程的数目)，降低分析过程的时间开销，提高基于 包含指针分析的效率。

(2)基于包含的指针分析算法的时间复杂度是O(n3)，n为分析过程中程序变量 的数目；目前对基于包含的指针分析算法进行改进，主要是围绕着如何在不影响指向 信息精度的前提下提高算法的效率和可扩展性；为了提高算法的效率，一种主流策略 是在保证不影响算法精度的条件下如何减少算法规模的大小，也就是让n变小。为了 让n变小，对基于包含的指针分析来说，当分析算法检测出指针等价的变量对信息(两 个指针变量是指针等价的如果它们的指向集是相同的)，分析算法能够合并这些指针 等价的变量对，从而减少分析过程中待分析和追踪的结点数目，实现上面的目标：在 保证不影响算法精度的条件下提高基于包含指针分析算法的效率和可扩展性。在研究 如何能够识别指针等价的变量对信息这一问题上，在线循环检测技术是一种重要的技 术，如LCD。与LCD只进行在线循环检测不同，本发明方法ADD不仅混合离线约 束图的结构信息进行在线循环检测，而且还基于离线约束图中包含的必经结点信息来 识别指针等价的顶层变量对信息；尽可能早地合并这些顶层变量对信息能够减少后续 在线分析过程中结点间指向信息传播的开销，有助于进一步提高基于包含指针分析的 效率。

附图说明

图1所示为本发明方法ADD的框架结构示意图；

具体实施方式

下面结合附图对本发明的技术方案进行详细说明。

如图1所示，本发明的基于离线约束图的指针分析方法ADD，包括以下步骤：

(1)根据输入约束集，构造离线约束图；

对于输入约束集，ADD使用简单约束语句、加载约束语句和存储约束语句构造 离线约束图，离线约束图的构造规则如下：当输入约束集涉及N个变量时，离线约束 图中包含2*N个结点；即每个变量h，对应的有两个结点h和*h；对于简单约束语句 p＝q，离线约束图中对应的边是q->p；对于加载约束语句p＝*q，离线约束图中对应的 边是*q->p；对于存储约束语句*p＝q，离线约束图中对应的边是q->*p。

(2)在所述离线约束图中触发一次深度优先搜索，得到一个有向无环图和多个 循环，并记录循环信息；

在离线约束图中触发一次循环检测搜索，ADD将得到一个有向无环图DAG和若 干循环；此时循环可能有两种形式；一种是循环不包括解引用结点，如循环{a，b， c}；另一种是循环包括解引用结点，如循环{m，*n，w，*t}；ADD记录这些循环相 关信息，后续的在线分析阶段将使用这些循环相关信息；这里，ADD会维护一个映 射关系mapping，对于每一个结点变量m，如果m属于离线约束图中的循环，mapping 将m映射到m所在循环的代表元m.rep，即mapping(m)＝m.rep；否则，mapping保持 m不变，即mapping(m)＝m。

(3)在所述有向无环图中，根据结点的拓扑序计算每个结点的祖先集和后裔集；

同时在所述有向无环图中，利用LengauerandTarjan算法计算该图对应的支配树 或支配森林；

计算一个结点p的祖先集的具体流程为：

在所述有向无环图的转置图中，以结点p为根进行深度优先搜索，该搜索过程过 程中遇到的所有结点记为结点p在有向无环图中的祖先集；

计算一个结点p的后裔集的具体流程为：

在所述有向无环图中，以结点p为根进行深度优先搜索，该搜索过程过程中遇到 的所有结点记为结点p在有向无环图中的后裔集。

LengauerandTarjan算法，用于计算有向图中的支配结点信息，该算法由Lengauer 和Tarjan于1979年提出；与当前已有的其它用于计算有向图中的支配结点信息的算 法相比，LengauerandTarjan算法具有非常高的效率，因此，ADD利用Lengauerand Tarjan算法计算支配树或支配森林。

(4)在所述支配树或支配森林中，计算指针等价的顶层变量对信息；

首先，介绍一下指针等价的概念，指针等价用于描述结点之间的关系：变量m 与n是指针等价的，如果在算法迭代终止时变量m与n具有相同的指针指向信息。

其次，计算指针等价的顶层变量对信息的步骤如下：

在支配树或支配森林中，检查每个点对(m，n)是否为指针等价的顶层变量对， 从而得到指针等价的顶层变量对信息，其中m为为支配树或支配森林的结点，n为支 配树或支配森林的结点，；具体判断方法为，如果m与n同时满足下面三个条件，则 m与n是指针等价的顶层变量对，否则不是：

(a)n是m的直接支配结点idom(m)；

(b)m与n都是顶层变量；

(c)在离线约束图中，从n到m的所有路径都只涉及顶层变量结点，即从n到 m的所有路径不包含取地址变量结点或解引用结点。

在上面的计算过程中，当考虑离线约束图中从n到m的所有路径时，ADD采取 的策略是：对结点n，ADD只向下遍历K层，然后通过检查遍历过程访问到的结点， 来确定这个遍历是否已覆盖n和m之间所有的路径，如果是，ADD应用上面的策略 来检查点对(m，n)；否则，出于算法的正确性考虑，ADD忽略这个点对，即ADD 认为点对(m，n)不是指针等价的顶层变量对。

(5)根据输入约束集，构造初始的在线约束图，然后在所述在线约束图中，将 与步骤(4)得到的顶层变量对信息对应的结点合并；

当输入约束集涉及N个变量时，在线约束图中包含N个结点；即每个变量h，对 应的有一个结点h；根据取地址约束语句，计算结点的初始指向集；对于简单约束语 句p＝q，添加有向边q->p到在线约束图中。

根据步骤(4)得到的顶层变量对信息，如(m，n)，在在线约束图中，合并结 点m与n。

(6)首先利用同时满足如下条件的结点对优先级队列current进行初始化：(a) 结点的指向集为非空；(b)结点含有出边或者含有复杂约束，所述复杂约束为加载约 束或存储约束；然后基于工作集算法框架迭代处理current，得到指针指向信息。

ADD基于工作集算法框架迭代处理优先级队列current，是对优先级队列current 中的结点逐个进行如下处理：

(i)当结点s不存在复杂约束时，直接进入步骤(iii)，当结点s存在复杂约束 时，按照如下方式添加新的有向边到在线约束图中：

对于每一个复杂约束，即加载约束u＝*s或者存储约束*s＝v，如果*s属于离线约 束图中的循环，则按照下列(a)的方式处理，如果*s不属于离线约束图中的循环， 则按照下列(b)的方式处理，其中，u和v是在线约束图中不同于s的结点：

(a)根据步骤(2)记录的循环信息(s，t)，首先对结点s的指向集中每个元素 w，分别进行w与t的合并，其中，t是在线约束图中不同于s的结点；然后将结点t 添加到current中，最后按照如下方式进行加边：

复杂约束为加载约束u＝*s时，进一步判断在线约束图中是否包含有向边t->u， 如果不包含，则添加新的有向边t->u，同时将t添加到current中，删除加载约束u＝*s， 否则，直接删除加载约束u＝*s；

复杂约束为存储约束*s＝v时，进一步判断在线约束图中是否包含有向边v->t，如 果不包含，则添加新的有向边v->t，同时将v添加到current中，删除存储约束*s＝v， 否则，直接删除存储约束*s＝v；

(b)根据结点s的指向集添加对应的有向边到约束图中，即，对结点s的指向 集中任一元素w按照如下方式进行加边：

对加载约束u＝*s，当在线约束图中不包含有向边w->u时，添加新的有向边w->u， 同时将w添加到current中，否则，就不做任何处理；

对存储约束*s＝v，当在线约束图中不包含有向边v->w时，添加新的有向边v->w， 同时将v添加到current中，否则，就不做任何处理；

(ii)首先进行取交集操作，即复杂约束为加载约束u＝*s时，对结点s的指向集 和结点u对应的后裔集进行取交集操作，复杂约束为存储约束*s＝v时，对结点s的指 向集和结点v对应的祖先集进行取交集操作，然后根据操作结果是否非空来决定此时 是否触发一次循环检测过程；

根据结果是否非空来决定此时是否触发一次循环检测过程的的具体方法为：

对于加载约束u＝*s，如果取交集操作的结果points-to(s)∩Descendant(u)是非空， 则在结点u处触发一次循环检测搜索；否则，在结点u处不触发循环检测搜索；

对于存储约束*s＝v，如果取交集操作的结果points-to(s)∩Ancestor(v)是非空，则 在结点v处触发一次循环检测搜索；否则，在结点v处不触发循环检测搜索。

(iii)沿着有向边进行指向信息传播；

沿着有向边s->k进行指向信息传播，其中，k是在线约束图中不同于s的结点； 此时，points-to(k)＝points-to(k)∪points-to(s)，这里points-to(k)表示结点k的指向集， points-to(s)表示结点s的指向集，如果points-to(k)发生变化，将k添加到current中， 否则不将k添加到current中。

本发明中所述具体实施案例仅是本发明的优选实施方式，应当指出：对于本技术 领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和等 同替换，这些对本发明权利要求进行改进和等同替换后的技术方案，均落入本发明的 保护范围。