一种程序中指针别名分析方法

摘要

本发明公开了一种程序中指针别名分析方法，应用于程序分析领域。所述方法包括：在程序运行过程中维护一个存储程序中所有指针指向信息的全局数据结构；当指针被声明时，在所述全局数据结构中添加一条新记录；当指针被赋值引用时，根据赋值表达式的右值及其对应内存地址空间类型来动态更新所述全局数据结构中相应记录；在程序运行结束前或结束时，输出指定位置指定指针或所有指针的别名关系。本发明提出的方法能够提供程序运行过程中任意位置的指针别名关系，适用于过程内或过程间的指向堆或栈上变量的指针别名分析。

说明书

技术领域

本发明属于程序分析领域，特别涉及一种程序中指针别名分析的方法。

背景技术

随着计算机技术不断提高和待解决问题的益加复杂，计算机软件的规模越来越庞大，程序结构也变得越来越复杂，这对于软件开发和维护工作带来了更大的挑战。为了让程序开发人员更快地理解自己或他人所开发的软件，以便实现对现有软件优化、调试，或对遗留软件进行扩展、维护工作，需要对程序源代码进行必要的分析。程序分析涉及程序多方面的特征，而且由于指针数据类型在C/C++程序中的广泛使用，导致程序的并行性分析和优化工作变得更复杂。若预先不对指针变量的指向目标进行分析而采取保守的估计，会严重影响所获取程序信息的准确性，从而导致后续的程序调试、优化或维护工作无法顺利开展。因此，需要对程序中所有指针的指向信息进行分析。

C/C++程序中，可以借助于指针、引用、联合体、形参、数组等使得不同的变量指向同一块内存地址空间。另外，函数调用的存在会导致指针指向信息在调用函数和被调用函数之间传播和修改。因此，有必要对C/C++程序的指针别名关系进行分析，而且不仅要进行过程内的指针别名分析，还需要对跨过程的指针指向信息进行分析统计，即进行过程间指针别名分析。现有过程间指针别名分析方法，按照所求取信息的准确程度可分为上下文敏感的分析方法和上下文不敏感的方法。前者依据同一函数不同调用点指针指向模式的不同而产生不同的分析结果，而后者则对同一函数的不同调用只产生一个唯一的近似结果。毫无疑问，相比而言，进行上下文敏感的过程间指针别名分析所取得的结果将会比较精确。本发明提出的一种指针别名分析方法便是一种既可用于过程内指针别名分析，也可用于过程间指针别名分析的方法。

发明内容

本发明的技术解决问题：克服现有技术的不足，提供一种程序中指针别名分析方法，能够给出程序运行过程中任意位置的指针别名关系，适用于指向堆和栈上变量的指针别名分析，也适用于过程内和过程间指针别名关系的分析。

本发明提供了一种程序中指针别名分析方法，所述方法包括：

在程序运行过程中维护一个全局数据结构，用于存储程序中所有指针的指向信息。其中，所述全局数据结构是一个满足哈希函数关系f(x)的数据结构。在所述哈希函数关系f(x)中，输入参数x标识了指针指向的内存块的全局唯一编号，所述哈希函数关系f(x)的输出结果是所述全局数据结构中存储指针指向信息的地址，所述哈希函数关系f(x)指明了所述全局唯一编号与存储程序中所有指针的指向信息的数据结构的映射关系。

当指针被声明时，在所述指针指向表中添加一条新记录。其中，所述记录中包括指针名称，指针指向内存块类型，指针指向内存块的唯一编号。

当指针被赋值引用时，根据赋值表达式的右值及其对应内存地址空间类型来动态更新所述指针指向表中相应记录。其中，所述赋值表达式的右值对应的内存地址空间类型包括栈和堆两类。

在程序运行结束前或结束时，输出指定位置指定指针或所有指针的别名关系。其中，指针别名关系需要通过所述哈希函数关系f(x)计算得到，得到的指针别名关系是一个指针集合，所述指针集合表示的是同一时刻同时指向编号为x的内存块的指针集合。

本发明对应的技术方案包括如下步骤：

步骤一，在程序运行过程中维护一个全局数据结构，用于存储程序中所有指针的指向信息。

所述全局数据结构是一个满足哈希函数关系f(x)的数据结构，其中x是标识指针指向的内存块的全局唯一编号，哈希函数关系f(x)的输出结果是所述全局数据结构中存储指针指向信息的地址，所述哈希函数关系f(x)指明了所述全局唯一编号与存储程序中所有指针的指向信息的数据结构的映射关系；所述全局数据结构中存储了程序运行过程中所有已声明指针的指向信息。

步骤二，指针在声明时，在所述全局数据结构中添加一条新纪录。

所述记录中包括指针名称，指针指向内存块类型和指针指向内存块的唯一编号。

步骤三，指针被赋值引用时，根据赋值表达式的右值及其对应内存地址空间类型来动态更新所述全局数据结构中相应记录。

步骤四：不论程序运行结束与否，均可以在事先指定位置，输出指定指针或当前时刻所有指针的别名关系，以满足程序分析的需要。

这里的获得的指针别名关系需要通过哈希函数关系f(x)计算得到，得到的指针别名关系是一个指针集合，所述指针集合表示的是同一时刻同时指向编号为x的内存块的指针集合。

本发明与现有技术相比优点在于：

(1)本发明能够在程序运行过程中，给出任意位置的任意指针当前时刻与其他指针的别名关系。

(2)本发明不仅能够分析出指向堆内存地址空间的指针的别名关系，也能够分析出指向栈内存地址空间的指针的别名关系。

(3)本发明不仅能用于分析过程内指针别名关系，也能够用于分析过程间指针别名关系。

附图说明

图1为本发明实施例中指针别名分析方法的流程图；

图2为本发明实施例中指针指向表动态更新流程图。

具体实施方式

以下结合本发明实施例附图来对本发明实施例中的技术方案进行清楚、完整地描述，显然所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。

本发明的实施，能够满足程序分析过程任何可能需要用到指针别名关系的要求，能够在需要时，给出指定指针指定时刻在指定位置的别名关系，以便程序分析的顺利进行。

如图1为本发明实施例中指针别名分析方法的流程图，所述方法包括以下步骤：

步骤101，在程序运行过程中维护一个全局数据结构，用于存储程序中所有指针的指向信息。

所述全局数据结构是一个满足哈希函数关系f(x)的数据结构，其中x是标识指针指向的内存块的全局唯一编号；哈希函数关系f(x)的输出结果是所述全局数据结构中存储指针指向信息的地址，所述哈希函数关系f(x)指明了所述全局唯一编号与存储程序中所有指针的指向信息的数据结构的映射关系；所述全局数据结构中存储了程序运行过程中所有已声明指针的指向信息。

在具体选定用于存储程序中所有指针的指向信息的全局数据结构时，一个优选的方案是，取哈希函数f(x)＝x来存储相关数据，并取内存块对应的空间起始地址作为所述哈希函数f(x)的关键字码，即x的值为内存块对应的空间起始地址。

步骤102，指针在声明时，在所述全局数据结构中添加一条新纪录。

所述记录中包括指针名称，指针指向内存块类型和指针指向内存块的唯一编号。

步骤103，指针被赋值引用时，根据赋值表达式的右值及其对应内存地址空间类型来动态更新所述全局数据结构中相应记录。

其中，动态更新所述指针指向表中相应记录，参照图2，指针指向表动态更新流程图，包含以下步骤：

步骤201：判定指针赋值表达式的右值是否是一个函数调用；

步骤202：若指针赋值表达式的右值是一个函数调用，则跳转到被调用函数源码中，将实际运行过程中返回的值来更新被赋值指针的指向记录；更新时，需要将被调用函数实际返回值指向内存地址空间的类型及其指向内存地址空间的全局编号，以及该返回值的别名关系直接替换被赋值指针的指针指向表中的相应字段即可。

步骤203：若指针赋值表达式的右值非函数调用，则直接提取所述右值所对应的内存地址空间类型、指向内存地址空间全局编号及其所有别名关系替换被赋值指针的直至指向表中的相应字段。

步骤104：不论程序运行结束与否，均可以在事先指定位置，输出指定指针或当前时刻所有指针的别名关系，以满足程序分析的需要。

这里的获得的指针别名关系需要通过哈希函数关系f(x)计算得到，得到的指针别名关系是一个指针集合，所述指针集合表示的是同一时刻同时指向编号为x的内存块的指针集合。

本发明提出的指针别名分析方法能够提供程序运行过程中任意位置的指针别名关系，适用于过程内或过程间的指向堆或栈上变量的指针别名分析。

应该指出的是，以上所述仅为本发明的较佳实施案例而已，并不能因此而认为是对本发明的专利保护范围的限制，在不脱离本发明的核心思想的所有等效改进和润饰，均属于本发明的保护范围。