面向错误检测的指针分析技术研究

摘要

指针分析是一种静态程序分析技术，它的目标是静态确定一个指针变量能够指向哪些地址（变量或函数的存储位置），也就是静态确定一个指针变量在程序运行时所有可能的值。指针分析以程序源代码（或某种中间代码表示）作为输入，输出该程序所包含的指针指向信息。由于指针（引用）在C/C++(Java)程序中被广泛使用，许多静态程序分析技术需要根据指针指向信息来解析程序中包含的间接引用，指针分析的结果直接影响其它静态程序分析技术的有效性，指针分析作为许多静态程序分析技术的使能技术一直是一项重要的议题。对于动态性较弱、使用指针较少、规模较小的程序，现有的指针分析技术已经较为成熟，可以很好地分析处理这些程序。然而，对于规模更大、动态性更强的程序，如大规模程序和并发程序，现有的指针分析算法还存在许多问题，需要进一步地研究:(1)如何在不影响指向信息精度的条件下，提高指针分析算法的效率和可扩展性;(2)如何提高指针分析算法的精度，同时尽可能地保证算法的效率和可扩展性;(3)如何设计适用于并发程序的指针分析算法等。
　　错误检测是软件工程的研究热点之一。对于C/C++程序，为了检测程序中普遍存在的内存错误，如内存泄露(memory leak)、同一块内存空间的多次释放和空指针解引用(null pointer dereference)等，错误检测算法需要根据指针指向信息来解析程序中包含的间接引用，错误检测算法的有效性直接依赖底层指针分析算法的精度、效率和可扩展性。与顺序程序类似，对于并发程序，为了检测程序中普遍存在的错误，如数据争用(data race)等，错误检测算法同样需要根据指针指向信息来解析程序中包含的间接引用。对错误检测算法来说，理想的目标是借助于一个指向信息精度好、算法效率高和可扩展性好的指针分析算法去解析程序中包含的间接引用信息。
　　考虑到错误检测的需求，本文对指针分析进行了深入研究，研究内容主要包含两个方面:基于包含的流不敏感指针分析算法和多线程指针分析算法。对基于包含的流不敏感指针分析算法的研究主要是围绕如何设计有效的在线循环检测技术，因为在线循环检测技术能够在不影响指向信息精度的条件下，显著地提高基于包含的指针分析算法的效率和可扩展性。本文针对现有的在线循环检测技术LCD(lazycycle detection)存在的不足进行改进，提出了三种在线循环检测技术（ELCD、BootCD和ADD）;对多线程指针分析算法的研究主要是在因果数据流分析的基础上，设计了一种基于Petri网的多线程指针分析技术。
　　论文的主要成果表现在以下几个方面:
　　(1)针对LCD算法存在的不足，对LCD的循环效果进行改进，提出了ELCD(extended lazy cycledetection)算法;与LCD相比，ELCD基于更精细的循环效果来检测约束图中潜在的循环，它定义的循环效果不仅依赖一条有向边的两个结点的指向集信息，同时还依赖这条边的目的结点的后继结点的指向集信息。基于更精细的循环效果，ELCD算法能够明显减少LCD算法触发的那些循环检测结果是约束图中不存在循环的循环检测过程的数目。实验结果表明ELCD算法能够在不影响LCD算法的指向信息精度的情况下提高LCD算法的效率。
　　(2)为了进一步地提高LCD循环检测的质量（即减少LCD算法触发的那些循环检测结果是约束图中不存在循环的循环检测过程的数目），提出了BootCD（bootstrapped online cycle detection）算法;BooCD算法基于bootstrapping这样一个想法，首先利用一种高效的但不精确的指针分析算法进行一次指针分析，然后基于这些指针指向信息辅助后续指针分析算法进行在线循环检测，从而提高了后续指针分析算法的效率。具体来说，BootCD混合Steensgaard指针指向信息，定义并构造了一个新的有向图，称为bootstrapping约束图，它是andersen约束图的超图，BootCD借助bootstrapping约束图中的循环边集信息在andersen约束图中进行在线循环检测。实验结果表明，与LCD相比，BootCD显著地提高了在线循环检测的质量，减少了整个分析时间，提高了基于包含指针分析的效率。
　　(3)提出了两种新的概念——bootstrapping约束图（bootstrapping constraint graph）和约束等价（constraint equivalence），同时设计了bootstrapping约束图的构造方法和约束等价的变量对信息的求解方法;bootstrapping约束图是BootCD算法的基础，而约束等价的作用是:(a)能够简化bootstrapping约束图（即减少bootstrapping约束图中的结点和有向边）;(b)能够优化bootstrapping约束图的构造过程，这显著地减少了BootCD离线分析的时间开销和内存耗费（即构造bootstrapping约束图和计算bootstrapping约束图的循环边集所需的时间开销和内存耗费），有助于提高BootCD算法的有效性和效率。
　　(4)为了进一步地提高LCD在线循环检测的效率，提出了一种新的在线循环检测技术ADD(ancestor_descendant_dominator);与BootCD相比，ADD同样是基于bootstrapping这样一个想法;ADD与BootCD的区别是用于bootstrap在线循环检测的信息不同;BootCD利用bootstrapping约束图及其循环边信息来boostrapping，而ADD使用离线约束图（offiine constraint graph）的结构信息来bootstrapping。具体来说，ADD首先构造离线约束图，计算并合并离线约束图中包含的循环;此时，离线约束图变成一个有向无环图(DAG);然后，在这个DAG中，为每个结点定义并计算Ancestor集和Descendant集，这些信息被用于辅助后续指针分析过程进行在线循环检测;最后，基于离线约束图中包含的必经结点信息，ADD能够识别指针等价的顶层变量对信息;合并这些顶层变量对信息能够减少后续在线分析过程中结点间指向信息传播的开销，有助于进一步提高ADD的效率。初步的实验结果表明，与LCD相比，ADD明显地提高了在线循环检测的效率，减少了整个分析时间，提高了基于包含指针分析的效率。
　　(5)在因果数据流分析的基础上，设计了一种基于Petri网的多线程指针分析技术;具体来说，首先使用1-safe petri网来表示程序的并发控制流结构，然后研究petri网的偏序执行(partially orderedexecution)，其中指针指向信息沿着具有因果关系的事件进行传播;多线程程序的指针分析问题被转化成petri网的标识覆盖(marking coverability)问题。基于Petri网的多线程指针分析为深入研究多线程程序的指针分析提供了一种可能的思路。

目录

声明

摘要

第一章 绪论

1．1 选题依据

1．2 国内外研究现状

1．2．1 流敏感性

1．2．2 上下文敏感性

1．2．3 域敏感性

1．2．4 指针指向信息的存储表示

1．2．5 堆模型

1．2．6 其它

1．3 主要研究内容

1．3．1 基于包含的流不敏感指针分析算法

1．3．2 多线程指针分析算法

1．4 论文结构

第二章 基本概念与方法

2．1 输入程序的中间代码表示

2．2 基于合并的流不敏感指针分析

2．3 基于包含的流不敏感指针分析

2．4 在线循环检测技术

2．5 本章小结

第三章 ELCD：扩展的在线循环检测技术

3．1 引言

3．2 背景

3．2．1 IBPAC算法

3．2．2 LCD算法

3．3 ELCD算法

3．4 实验评估

3．4．1 实验框架

3．4．2 实验结果

3．4．3 实验分析

3．5 相关工作

3．6 本章小结

第四章 混合Steensgaard指向信息的在线循环检测技术

4．1 引言

4．2 背景

4．3 BootCD(bootstrapped cycle detection)

4．3．1 LCD产生的误报(false-positives)

4．3．2 LCD产生的漏报(false-negative)

4．3．3 BootCD算法背后的insight

4．3．4 BootCD算法

4．3．5 约束等价(constraint equivalence)

4．3．6 域敏感性的讨论

4．4 实验评估

4．4．1 质量与性能(Quality and Performance)

4．4．2 约束等价

4．5 相关工作

4．5．1 在线循环检测算法

4．5．2 基于bootstrapping的分析算法

4．5．3 基于等价的指针分析算法

4．6 本章小结

第五章 基于离线约束图的高效在线循环检测技术

5．1 引言

5．2 ADD算法的策略

5．2．1 ADD用于循环检测的策略

5．2．2 ADD用于识别指针等价的顶层变量对信息的策略

5．3 ADD算法

5．4 实例分析

5．5 本章小结

第六章 基于Petri网的多线程指针分析技术

6．1 引言

6．2 背景知识

6．2．1 Petri网

6．2．2 Mazurkiewicz trace

6．3 基于Petri网的多线程指针分析技术

6．3．1 多线程语言PML定义

6．3．2 PML程序的petri网模型

6．3．3 基于Petri网的多线程指针分析技术

6．4 实例分析

6．5 本章小结

第七章 论文总结和未来工作

7．1 论文总结

7．2 未来工作

参考文献

致谢

攻读博士学位期间完成的论文列表