一种面向堆操作程序的内存泄漏检测方法

摘要

本发明公开了一种面向堆操作程序的内存泄漏检测方法，要解决的技术问题是针对当前堆操作程序内存错误检测方面存在精度和效率的问题，提供一种新的内存泄漏检测方法，提高检测的精度和效率。技术方案是先对程序源代码进行语句分析和词法分析，生成中间文件；然后进行预处理，包括切片和转换；接着根据程序中指针变量扩展类型的定义得到堆内存抽象状态；采用前向数据流迭代方法进行过程内和过程间检测；最后检查和统计内存泄漏检测的结果。本发明在静态分析的精度和效率间找到了一个较好的平衡点，可加速迭代算法的终止，提高了检测精度和效率，可扩展性强，存储开销少。

说明书

技术领域

本发明涉及计算机程序中一类具有动态、易变共享内存操作特性的堆操作程序内存泄漏的静态检测方法。 

背景技术

堆操作程序包括使用动态数据结构(如：链表、树等)存储和处理数据的程序，在系统软件和应用软件非常常见，比如：操作系统(如：Linux、FreeRTOS)常常使用优先级队列或哈希表管理系统的任务；设备驱动管理程序使用共享单向或双向链表管理各种设备；服务器软件(如：Apache)使用容器(Collection)接受和存储各种用户请求；信息系统管理软件使用各类容器表示视图和存储从数据库中查询得到的数据。这类程序都具有运行过程中动态分配、聚合、分离或释放堆中内存单元的特点；另一方面，分析这类程序源代码时可知，程序员使用指针变量(或指针域)直接(或间接)操纵这些内存单元，使得这些动态内存单元间存在着复杂的指向关系，比如：某个内存单元可能被多个指针变量或其它内存单元所指向。因此，判断堆操作程序中已申请的内存单元是否最终被释放比其他类型的程序困难和复杂得多。内存泄漏是指动态分配的内存没有即时被释放，它是一类重要的软件错误，它能够导致持续运行的系统由于内存资源耗尽而崩溃，或者重要的信息泄漏。 

当前，内存泄漏检测有多种方法及其工具，主要分为动态和静态的方法。典型动态方法的工具有Purify、JPF等，这类方法虽能准确地定位错误，自动化程度高，但受限于输入用例，不能检查所有的内存泄漏错误；静态方法是在不运行软件前提下检查是否存在内存泄漏，典型工作有：LCLint、SATURN等，可以找到所有可能的内存泄漏错误，但是存在较高的误报率。因此，如何在保证精度的前提下使得静态检测工具能够检测大规模程序是当前静态检测研究的热点和难点。针对动态、易变分配内存的堆操作程序中内存泄漏检测的方法主要可以分为： 

(1)域不敏感检测方法 

域不敏感检测方法是基于指针别名分析检测程序中每个分配的内存结点是否最终被释放，又可以分为流敏感和流不敏感、路径敏感和路径不敏感、上下文敏感和上下文不 敏感6种检测方法。例如：Zongxing Xu等人在2008年软件质量国际会议(QSIC′08)上提出了基于约束求解器CVC3路径敏感的过程间内存泄漏算法；Yungbum Jung和Kwangkeun Yi在国际内存管理论坛会议(ISMM’08)上提出了一种自动化的静态分析工具SPARROW，设计了基于逃逸模型的参数化过程函数摘要方法；除此之外，Xie Yichen和Alex Aiken在第10届欧洲软件工程会议上提出了内存泄漏检测工具Saturn，将内存泄漏问题规约为布尔公式的可满足性问题，然后使用SAT求解器判断是否存在内存泄漏；David L.Heine等人在第28届软件工程国际会议上提出了内存泄漏检测工具Clouseau，它是基于指针所有权描述释放堆内存结点的指针变量，然后构造所有权约束系统检测内存泄漏错误。所有这些工具不能直接应用于检测堆操作程序中内存泄漏错误。 

(2)域敏感检测方法 

域敏感检测方法涉及到堆内存单元间的可达性关系。Mooly Sagiv等人在2002年ACM程序语言与系统汇刊(TOPLAS’02)上提出了三值逻辑TVLA(Three-Value Logic)，对具有链表类型的程序通过定义核心(core)和辅助(instrumental)谓词集将内存结点划分成有限的等价类，通过分析程序的形态来证明各种链表操作程序没有内存泄漏错误，然而TVLA应用于其他类型的堆操作程序内存泄漏检测时存在比较高的误报；Hackett等人在2005年ACM程序语言原理国际会议(POPL’05)上提出了一种新颖的基于引用计数的区域形态分析算法，并能够在2分钟内对3个流行的几万行大型C程序进行检测并发现97个错误，其中只有37个是真实错误，虽然效率比较高，但是，存在着较高的误报率；Ji Wang等人在2009年计算机学报英文版(JCST’09)上设计了基于内存抽象指向图需求驱动的内存泄漏检测算法，并且在精度和效率上取得相对比较好的平衡，但是，存储开销和计算复杂度仍比较高。最近，相继出现了对堆操作程序使用逻辑推理的形态分析方法检测内存错误，典型工作有：SpaceInvader和Xisa。SpaceInvader在2008年计算机辅助验证国际会议(CAV’08)上使用分离逻辑(Separation Logic)公式递归定义链表数据结构不变式，然后基于递归定义设计了各种推理规则对堆操作程序进行推理，已经成功分析和验证了Windows和Linux下一些设备驱动管理程序的内存正确性；Xisa在2008年ACM程序语言原理国际会议(POPL’08)上使用抽象解释框架支持参数化的用户自定义数据结构不变式分析和验证堆操作程序的内存安全性质。但是，这些方法受到用户自定义数据结构不变式的约束，自动化程度不高，很难实用于大规模实际程序的内存错误自动检测。 

综上所述，虽然目前学术界和工业界有多种不同的内存泄漏检测方法，每种方法都 有各自的特点与适用范围，但它们在检测堆操作程序上均有不足之处。域不敏感的检测方法虽能检测大规模程序，但是检测精度较低，尤其是面对具有堆内存聚合、分离特性的堆操作程序时，不能够检测同一指针变量指向内存区域中的所有内存结点是否全部被释放；域敏感的检测方法虽能检测堆操作程序中所有内存泄漏错误，但是由于自动化程序不高或系统资源(主要包括内存、时间)消耗代价太大，所以效率不高，能够分析的程序规模比较小。 

发明内容

本发明要解决的技术问题是：针对当前内存泄漏检测方法在具有动态共享内存申请、合并、分离、删除等操作特性的堆操作程序内存错误检测方面存在精度和效率的问题，提供一种基于堆内存局部抽象的前向数据流迭代的内存泄漏检测方法，提高检测的精度和效率。 

具体技术方案为： 

第1步，利用编译器平台对被检测程序进行词法分析、语法分析，生成被检测程序的抽象语法树、控制流图(描述程序基本语句间的前后继关系)、过程调用图(程序中函数间的调用关系图)这样的中间信息。 

第2步，预处理。在对一个真实的堆操作程序内存检测之前需要进行两步预处理。 

2.1切片，即将那些没有使用任何指针类型变量的赋值语句从程序中删除，得到切片后的程序。 

2.2将经过切片后的程序中不符合标准形式的指针赋值语句按照转换规则转换成标准形式。标准形式的指针赋值语句包括7种：1，将指针变量p置为空，形如：p＝null；2，将指针变量p的指针域p-＞f_m置为空，形如：p-＞f_m＝null；3，指针变量间拷贝语句，形如：p＝q；4，指针p与指针q的指针域间的拷贝语句，形如：p＝q-＞f_m；5，指针p的指针域与指针q间的拷贝语句，形如：p-＞f_m＝q；6，内存申请语句，形如：p＝malloc；7，内存释放语句，形如：free(p)。转换规则有5种，分别是：1，引入辅助指针变量pt₀将形如p-＞f_m＝q-＞f_n的指针赋值语句转换为：pt₀＝q-＞f_n；p-＞f_m＝pt₀；2，引入辅助指针变量pt₁将形如p＝p-＞f_m的指针赋值语句转换为：pt₁＝p-＞f_m；p＝pt₁；3，引入辅助指针变量pt₂将形如p-＞f_m＝malloc的指针赋值语句转换为：pt₂＝malloc；p-＞f_m＝pt₂；4，引入辅助指针变量pt₃将形如p＝q-＞f_m-＞f_n的指针赋值语句转换为：pt₃＝q-＞f_m；p＝pt₃-＞f_n；5，引入辅助指针变量pt₄将形如free(p-＞f_m)的内存释放语句转换为：pt₄＝p-＞f_m；free(pt₄)。 

第3步，根据函数中每个指针变量的别名信息定义指针的扩展类型，得到程序的堆内存抽象状态。堆操作程序中，指针变量p的扩展类型 定义为：<f₁：<dist；2^PVar>；f₂：<dist，2^PVar>；...f_i：<dist；2^PVar>...；f_n：<dist；2^PVar>>，其中：f₁，f₂，...f_i，...，f_n分别表示p指向内存单元中指针域的名字，1≤i≤n，即：p指向由n个指针域聚集的内存单元，内存单元又称为内存结点；变量dist表示堆中内存结点距离指针p的值；2^PVar表示所有指向距离p所指向内存结点值为dist的内存结点构成的指针变量集，称为指针别名集，包括：全局指针变量、局部指针变量、函数中具有指针类型的形式参数。分析堆操作程序7种标准基本指针赋值语句可知：一条指针赋值语句中p直接或间接引用的内存结点距离p的最大值为1，例如：语句p-＞f_i＝q，将指针p所指向的内存结点中指针域f_i的值修改为指针q所指向的内存结点的地址，在此语句中，p通过指针域f_i路由可达的内存结点距离p的值为1。因此，变量dist值的范围为：0、1和2，其中：元素0和1表示堆内存中距离p所指向的内存结点精确值，值2是一个抽象值，表示通过某个指针域f_i两次或两次以上的路由次数(又称指针解引用操作，dereferencing)，在堆内存中这样得到的内存结点又称摘要结点(summary node)。指针集2PVar中有两个特殊的元素：空集 表示堆内存中没有任何指针变量指向该内存单元，而该内存单元在堆内存中已经被分配；⊥表示某个指针变量p或指针域f_i的值为null(特殊标记值，表示该指针变量值为无效内存地址)，p或指针域f_i所指向的内存单元在堆中还没有被分配。堆操作程序HP的活性指针变量是程序片段中一类被使用或修改的指针变量，由谓词LivePVar表示。所以，堆内存局部抽象状态 是具有活性指针变量的扩展类型构成的集合，即： 公式中，p_i表示任意一个具有活性的指针变量， 表示p_i的扩展类型。由此可知：堆操作程序中，堆内存局部抽象状态的数目是有限的。假设堆操作程序中指针变量个数为pn，聚集类型中指针域的数目为fn，那么堆内存局部抽象状态 的最大数目为：[fn×3×(2^pn+1)]^pn，公式中，3表示距离值的种类，2^pn表示指针别名集的幂集中子集数，1表示加上指针别名集中特殊元素值⊥。 

第4步，过程内内存泄漏检测。根据上述指针扩展类型的定义，得到堆操作程序中基本语句关于堆内存抽象状态的迁移关系，具体地，从被检测程序的过程调用图中自顶向下选择某个函数f，并将函数f入口处的抽象状态 设置为空，根据前向数据流迭代方法进行过程内内存泄漏检测，前向数据流迭代方法是： 

4.1初始化函数f中每个程序点i的堆内存抽象状态 置为空，并将队列W置 为空，W是一个先进先出FIFO的队列，基本元素为 对，s为语句。 

4.2将函数f的入口语句s₀和抽象状态 加入到队列W。 

4.3判断队列W是否为空，如果为空则转第6步，如果不为空则执行4.4。 

4.4从队列W中弹出项 根据语句s的类型转换抽象状态 得到新的抽象状态 具体方法如下： 

4.4.1如果语句s为基本指针赋值语句，则按7种指针赋值语句的类型转换状态 得到新的抽象状态 并从Succ(s)中选择某个元素s’，Succ(s)表示控制流图中语句s的后继语句集。然后执行4.5。按7种指针赋值语句的类型转换 的方法是： 

(1)指针赋值语句p＝null。转换规则是：在状态 中，首先从通过某个指针域f_i路由可达p指向内存结点的指针别名集中删除p，然后将 置为null，即：将 中所有通过f_i路由距离值为0、1和2的指针别名集置为⊥，得到新的抽象状态 如果状态 中指针p所指向的内存结点存在且没有被其他指针变量或堆内存中其他内存结点通过某个指针域路由可达，则发生内存泄漏，将该语句s和抽象状态 加入到内存泄漏队列heapleakListF中，heapleakListF是保存所有发生内存泄漏的语句和状态的队列，基本元素为：语句和抽象状态对 

(2)语句p-＞f_m＝null。转换规则是：在状态 中，指针变量x代表能够通过某个指针域f_i路由可达p指向内存结点的指针变量。首先，修改x的扩展类型：如果x与p别名，即：x到p的距离为0，则从 中将通过f_i路由距离值为1和2的指针别名集置为空；如果x到p的距离值为1或2，则从 中通过f_i路由距离为2的指针别名集中删除 中通过f_i路由距离值为1和2的指针别名集。然后，将 中通过f_m路由距离值为1和2的指针别名集置为空，得到新的抽象状态 如果状态 中p指向内存结点中的f_m指向的内存结点存在且没有被其他指针变量或其他内存结点通过f_i路由可达，则发生内存泄漏，将语句s和状态 加入到内存泄漏队列heapleakListF中。 

(3)指针拷贝语句p＝q。转换规则是：首先，在状态 下按照规则(1)执行语句p＝null得到中间抽象状态 然后在中间抽象状态 下，将 赋值给 即将p的指向修改为q指向的结点，得到新的抽象状态 如果状态 中p指向的内存结 点存在且没有被其他指针变量或堆内存中其他内存结点通过某个指针域路由可达，则发生内存泄漏，将语句s和状态 加入到内存泄漏队列heapleakListF中。 

(4)语句p＝q-＞f_m。转换规则是：首先，在状态 下按照规则(1)执行语句p＝null得到中间抽象状态 然后在中间抽象状态 下，将 中通过f_m路由距离值为1的指针别名集赋值给与 中通过某个指针域f_i路由距离值为0的指针别名集，将p加入到 中通过f_i路由距离值为1的指针别名集中，得到新的抽象状态 如果状态 中p指向的内存结点存在且没有被其他指针变量或堆内存中其他内存结点通过某个指针域路由可达，则发生内存泄漏，将语句s和状态 加入到内存泄漏队列heapleakListF中。 

(5)语句p-＞f_m＝q。转换规则是：首先，在状态 下按照规则(1)执行语句p-＞f_m＝null得到中间抽象状态 然后在中间抽象状态 下，集合Q表示 中通过某个指针域f_i路由距离为0的指针别名集，指针变量t表示抽象状态 中能够通过f_i一次或多次路由到达p指向的内存结点的指针。按照以下规则修改中间抽象状态 首先，修改集合Q中每个指针变量y的扩展类型 将 中通过f_i路由距离为0的指针别名集加入到 中通过f_i路由距离为1的指针别名集中，将 中通过f_i路由距离为1和2的指针别名集添加到 中通过f_i路由距离为2的指针别名集中；然后，将通过f_i路由距离q值为0、1和2的指针别名集同q一起添加到 中通过f_i路由距离为2的指针别名集中，得到新的抽象状态 如果状态 中p指向的内存结点中f_m指向的内存结点存在且没有被其他指针变量或堆内存中其他内存结点通过某个指针域路由可达，则发生内存泄漏，将语句s和状态 加入到内存泄漏队列heapleakListF中。 

(6)内存分配语句p＝malloc()。转换规则是：首先，在状态 下按照规则(1)执行语句p＝null得到中间抽象状态 然后在中间抽象状态 下，新申请一个内存结点并且将该内存结点的地址赋值给指针p，即：将 中通过某个指针域f_i路由距离为0的指针别名集置为空集 通过f_i路由距离为1和2的指针别名集置为⊥，得到新的抽象状态 如果状态 中p指向的内存结点存在且没有被其他指针变量或堆内 存中其他内存结点通过某个指针域f_i路由可达，则发生内存泄漏，将语句s和状态 加入到内存泄漏队列heapleakListF中。 

(7)内存释放语句free(p)。转换规则是：在状态 中，指针变量w表示活指针变量集LivePVar(HP)中除p所有其他指针变量，首先，从 中通过某个指针域f_i路由距离值为0、1和2的指针别名集中删除 中通过f_i路由距离为0的指针别名集，然后将 中通过f_i路由距离值为0、1和2的指针别名集置为⊥，得到新的抽象状态 如果状态 中p指向内存结点中某个指针域所指向的内存结点存在没有被其他指针变量或堆内存中其他内存结点通过某个指针域路由所可达，则发生内存泄漏，将语句s和状态 加入到内存泄漏队列heapleakListF中。 

4.4.2如果语句s为switch条件选择语句，则：首先在当前堆内存抽象状态 下求解switch语句条件的真值，然后根据条件真值从Succ(s)中选择下一条执行语句s’，并将s’作为语句s的后继语句，状态 作为新的抽象状态 执行4.5。 

4.4.3如果语句s为无条件跳转语句，则：并将目标语句s’作为语句s的后继语句，状态 作为新的抽象状态 执行4.5。 

4.4.4如果语句s为函数调用语句，则执行第5步，得到新的抽象状态 从Succ(s)中选择某个元素s’，作为s的后继语句。 

4.4.5如果语句s是函数返回语句return e，则在抽象状态 下，将指针变量e的扩展类型作为函数返回值的扩展类型，全局指针变量的扩展类型不变，其他局部指针变量的扩展类型赋值置空，得到新的抽象状态 并作为函数f的出口状态 出口语句s’作为返回语句s的后继语句，然后执行4.5。 

4.5将新的抽象状态 与后继语句s’的初始状态 通过合并操作Join得到该程序点新的抽象状态 执行4.6步。为了尽可能地检测出堆操作程序内存泄漏的错误，合并操作是：当且仅当任意两个抽象状态 和 存在包括关系时才能合并，否则两个抽象状态分别作为合并操作的元素。两个堆内存抽象状态 和 存在包含关系 当且仅当：状态 中任意元素在状态 中。合并操作由公式可以表示为： 

4.6将合并后的堆抽象状态 采用饱和操作达到饱和状态 饱和操作具体步骤如下： 

4.6.1将标记变量modified初始化为假。 

4.6.2反自反操作。遍历抽象状态 中每个指针变量x₁，从 中通过某个指针域f_i路由距离为0的指针别名集中删除指针x₁。如果某个指针别名集被修改了，将modified置为真。 

4.6.3对称操作。遍历抽象状态 中每个指针变量x₂，从 中通过某个指针域f_i路由距离为0的指针别名集中任意取出某个指针变量y₂，如果 中所有通过f_i路由距离为0的指针别名集不包含x₂，则将x₂加入 中到通过f_i路由距离为0的指针别名集。如果某个指针别名集被修改了，将modified置为真。 

4.6.4传递操作。遍历抽象状态 中每个指针变量x₃，从 中通过某个指针域f_i路由距离为某个值d₁的指针别名集中任意取出某个指针变量y，在 中通过某个指针域路由距离为某个值d₂得到指针别名集Q₂，如果指针别名集Q₂中某个指针变量z不在 中通过f_i路由距离为d₁+d₂的指针别名集中，则将z加入到 中通过f_i路由距离为d₁+d₂的指针别名集中。如果某个指针别名集被修改了，将modified置为真。 

4.6.5判断modified的值，如果为假，状态 达到饱和状态 转4.7步；否则转4.6.1步。 

4.7如果饱和状态 与原始状态 不同，则将饱和状态 作为新的原始状态 并且将饱和状态 和后继语句s’加入到W中，转4.3。 

第5步，对堆操作程序进行过程间的内存泄漏检测，方法是： 

5.1获取过程调用语句e＝f(e₁，e₂，...，e_k)的初始化信息。被调用过程名为：f，形式参数为：p₁，p₂，...，p_k，实际参数为：e₁，e₂，...，e_k，其中：p_h代表形式参数，e_h为p_h相对应的实际参数，下标h的范围为1≤h≤k，返回值为：ret_f，局部指针变量集为：LVar_f， 全局指针变量集为：GVar_f，执行函数调用语句前的堆内存抽象状态为 

5.2在堆内存抽象状态 下执行调用语句的状态迁移，得到被调用函数的堆内存初始状态 过程如下： 

5.2.1将状态 中全局指针变量集GVar_f中任意全局指针变量g的扩展类型传递给被调用过程，即：状态 中g的 等于状态 中g的 

5.2.2将状态 中实际参数e_h的 传递给形式参数p_h，作为被调用入口处p_h的 即：状态 中 的值为状态 中 的值。 

5.2.3状态 中局部指针变量集LVar_f中的任意局部指针变量l的扩展类型 初始化为空。 

5.3将函数f和初始状态 作为参数，采用第4步前向数据流迭代方法对函数f进行过程内内存泄漏检测，得到函数出口处堆内存新的抽象状态 

5.4将堆内存状态 传递给调用过程，得到新的抽象状态 按照如下步骤： 

5.4.1将状态 中指针类型返回值ret_f的扩展类型传递给调用过程，作为状态 下指针e的扩展类型。 

5.4.2状态 中全局指针变量g的扩展类型 传递给调用过程时不变，作为状态 下g的 

5.4.3其他局部指针变量的扩展类型在过程调用前后不变，即：状态 中其他局部指针变量的扩展类型的值为状态 中的相应局部指针变量扩展类型的值。 

第6步，统计堆操作程序内存泄漏检测结果数据。 

6.1根据控制流图上各个程序点中关于堆内存抽象状态的信息，输出各个程序点的入口语句的堆内存抽象状态和出口处的堆内存抽象状态。 

6.2根据内存泄漏队列heapleakListF的内容，输出所有可能发生内存泄漏的程序语句s和状态 并统计内存泄漏的数目。 

6.3筛选可能的内存泄漏错误，统计出检测的误报数，并得到误报率。由于一个内存泄漏错误代表在当前指针扩展类型下的指针赋值，在前向迭代检测过程中以抽象状态和 指针赋值语句对的形式汇报这些错误，能够辅助确认真实错误。 

6.4根据编译平台和系统运行时信息，得到内存泄漏检测方法消耗系统资源的情况，比如：内存消耗量、各个检测阶段的消耗时间等等。 

与现有技术相比，采用本发明可以达到下列技术效果： 

(1)本发明在第2步中指针扩展类型定义的基础上，提出了一种面向堆操作的内存泄漏检测方法，然后使用扩展指针类型记录指针变量间局部的内存排列关系以支持堆内存的局部推理，来检测堆操作程序中的内存泄漏错误，兼顾了效率和精度，在静态分析的精度和效率间找到了一个较好的平衡点。 

(2)本发明提出基于指针扩展类型来描述指针的别名关系，与传统的基于统一的(unification-based)指向别名分析的内存泄漏检测方法相比，不但表示了指针的别名信息，而且表示了指针所指向结点中所有指针域的别名信息，是一种域敏感的内存泄漏静态检测方法，与其他内存泄漏检测方法相比，提高了检测精度。 

(3)本发明第3步给出了基于指针扩展类型的堆内存局部抽象表示，与经典的指向图相比，基于指针扩展类型的堆内存局部抽象状态表示简单、高效，直接面向指针赋值语句的操作语义，无需计算指针表达式的左值和右值，就能得到指针的别名信息和具体值，提高了检测的效率。 

(4)本发明第4步内存泄漏检测采用前向数据流迭代算法，通过不动点迭代过程求得各个程序点关于堆内存局部抽象状态的集合，能够考虑各种可能的指针别名情况，另一方面，程序中堆内存局部抽象状态的数目是有限的，能够保证迭代算法的终止性，合并操作能够减少状态的存储开销，加速迭代算法的终止。 

(5)具有很好的扩展性。由于程序终止性在理论上是不可判定的，上下文敏感的过程间调用环境的数目是无穷的，因此，要做到完全的上下文敏感是不可能的。本发明第5步在处理上下文敏感的过程间检测时，使用一种记录历史信息增量式的检测方法：如果被调用过程的初始状态不包括当前的抽象状态时，则检测过程被调用，并将检测的结果加入到被调用过程中；否则不进入检测被调用过程。该方法可以提高检测的效率，尤其是随着检测代码规模的增大和某些相同过程被多次反复调用时，这种优势体现得极其明显。 

附图说明

图1是本发明的总体流程图。 

图2是本发明第4步过程内检测的流程图。 

图3是本发明第5步过程间检测的流程图。 

具体实施方案

图1本发明的总体流程图。输入是程序的源代码，输出时程序源代码中可能引发内存泄漏的语句与抽象状态、各种统计信息。 

本发明包括以下几个步骤： 

1.首先利用编译器平台对程序源代码进行语句分析和词法分析，生成中间文件，包括：抽象语法树、控制流图和过程调用图。 

2.预处理，包括：切片和转换。 

3.根据程序中指针变量的扩展类型的定义得到堆内存抽象状态。 

4.过程内检测。 

5.过程间检测。 

6.检查和统计内存泄漏检查检测的结果。 

图2是本发明第4步过程内检测的流程图，包括以下步骤： 

4.1初始化函数中每个程序点i的堆内存抽象状态和队列W。 

4.2将函数的人口语句和抽象状态加入到队列中。 

4.3判断队列W是否为空，如果为空则转第6步，如果不为空则执行4.4。 

4.4从队列中弹出某项，根据语句的类型转换抽象状态得到新的抽象状态。 

4.5将新的抽象状态和后继语句的初始状态通过合并操作合并成新的抽象状态。 

4.6将合并后的堆抽象状态采用饱和操作达到饱和状态。 

4.7如果饱和状态与原始状态不同，则将饱和状态作为新的原始状态，并且将饱和状态和后继语句加入到W中，然后跳转到第4.3步。 

图3是本发明第5步过程间检测的流程图，包括以下步骤： 

5.1获取过程调用语句的初始化信息。 

5.2在堆内存抽象状态下执行调用语句的状态迁移，得到被调用函数的堆内存初始状态。 

5.3采用第4步前向数据流迭代算法对函数进行过程内内存泄漏检测，得到函数出口处堆内存新的抽象状态。 

5.4将堆内存状态传递给调用过程，得到新的抽象状态。