Java指针分析综述

近年来静态程序分析已成为保障软件可靠性、安全性和高效性的关键技术之一.指针分析作为基础程序分析技术为静态程序分析提供关于程序的一系列基础信息,例如程序任意变量的指向关系、变量间的别名关系、程序调用图、堆对象的可达性等.介绍了Java指针分析的重要内容：指针分析算法、上下文敏感、堆对象抽象、复杂语言特性处理、非全程序指针分析,特别是对近年来指针分析的研究热点选择性上下文敏感技术进行了梳理和讨论.     

基于指向更新的优先权指针分析算法

指针分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础。在基于包含的指针分析算法研究的基础上,对 Narse 优先权约束评估算法中存在的冗余约束评估和优先权评估模型计算开销较大的问题进行分析,以指针的指向集更新信息确定约束评估的候选集,提出了基于指向更新的约束评估算法。采用约束语句间的解,引用依赖和标量依赖构建约束依赖图,通过依赖关系确定约束评估的优先权,提出了基于约束依赖图的优先权算法,简化了既有算法中复杂的优先权评估模型,进一步给出了优化后算法的整体框架。在基准测试集 SPEC 2000/SPEC 2006上进行实验,其结果表明,该算法与Narse优先权算法相比,在时间开销和存储开销上都有明显的性能提升。     

从变量的初始化中获取指针指向信息

从变量的初始化中获取指针指向信息完整的指针分析不可缺少的一个重要环节,它有助于提高其它数据流分析的准确性,文中提出了一个实用的从变量的初始化中获取指针同信息的方法,在此方法中,变量的初始化首先被转换成语义等价的语句序列,然后在指针分析的过程中融入对这些语句序列的分析而求取出相关的指针指向信息,这个方法被实现天复旦大学并行处理研究开发的Ｃ程序分析工具Ａｇａｓｓｉｚ系统内,实验数据说明是非常有效。     

基于包含的指针分析优化技术综述

指针分析是程序分析和编译优化的基础,针对基于包含的指针分析算法的改进一直是指针分析领域研究的热点之一.文中从该指针分析算法改进的两类技术来总结近二十年来相关的研究工作,包括在线优化技术如约束图上的强连通分量的检测和消除等和离线优化技术如变量替换等.通过实验对比了7种较有影响力的分析算法和三种离线优化算法,并从性能、内存...     

一种混合式的指针分析算法

指针的指向分析在检测C语言多线程程序的数据竞争中占有重要的地位。Steensgaard提出的流非敏感上下文非敏感的指针别名分析算法,因其执行效率极高的优点被广泛的应用于快速的指针指向分析。但该算法计算结果精度不高,得到的指针指向集往往有误差。针对该不足,引入了Vineet Kahlon的用求最大更新序列来求指针别名的思想,对Steensgaard算法计算出的结果进行了修正。并通过一个实例证明了改进后的算法比先前的算法更精确。     

面向对象程序的上下文敏感指针分析研究

指针分析是编译优化、程序静态分析中的基础,很多应用都需要基于指针分析,低精度的指针分析会给这些应用带来高误报率和漏报率,通过添加上下文敏感信息是提高指针分析的精度的一个重要手段.自从面向对象的概念被提出来之后,该概念得到了广泛的应用,Java、C++、.NET、C#等主流语言都支持面向对象的特性,面向对象程序的指针分析...     

关于指针数组与指向指针的指针教学研究

指针是C语言中的一个重要的概念,也是C语言的一个重要特色,正确而灵活地运用它可以使程序简洁、紧凑、高效,这对软件设计十分必要.但是指针概念比较复杂,应用也比较灵活且容易出错,学习者较难掌握,是C语言教学的难点,特别是指针与数组结合使学习者理解起来更加困难,本文从概念表示到应用分析由浅入深地讨论了指针数组与指向指针的指针.阐述了学习方法与教学经验.     

面向软件可信性的可信指针分析技术综述*

对可信指针分析技术的定义和描述、指针分析对软件可信性的保障、可信指针分析属性以及该领域主要研究成果等方面进行了综述。通过对现有可信指针分析技术的分析和比较,详细讨论了面向软件可信性的可信指针分析的关键技术;此外,重点介绍了流敏感指针分析及上下文敏感指针分析的方法和理论;最后对进一步研究工作的方向进行了展望。     

过程间流敏感的指针分析技术研究

指针分析技术是一种基础的静态程序分析技术,也是软件安全方向的研究热点之一,在软件缺陷检测、恶意代码分析、程序验证、编译器优化等应用场景中发挥着重要的作用,指针分析的精度在这些应用场景中至关重要。流敏感分析和过程间分析是提高指针分析精度最有效的两种技术。文中对现有的提高过程间流敏感指针分析精度的技术进行总结,从为提高精度所消除的信息入手,将分析方法分为两大类：一类是消除分析中的虚假信息,以避免指向信息沿虚假的返回路径或是虚假调用关系传播;另一类是消除分析中保守的指向关系,在每个程序点处根据设置的规则尽可能确定指针的唯一指向,而不是笼统地计算指针的多个可能指向。据此,详细比较了过程间流敏感指针分析技术的异同,并对指针分析技术未来的研究方向进行了展望。     

基于Open64的可信指针分析框架研究

提出保障程序可信性的指针分析基础架构,为上层提供通用和丰富的接口及数据信息,不仅能够完成高效精确的指针分析,同时还为上层软件检测提供可信支持。该框架采用一种高效的流敏感、上下文敏感的可信指针分析技术,该方法充分利用扩展SSA形式,采用稀疏存储形式,提高了流敏感的分析效率。同时将需求驱动的分析策略引入到可信指针分析框架中来,能够有效地避免盲目的程序分析,使可信指针分析更具针对性,大大提高了分析的性能。最后通过实验验证了该框架进行可信指针分析的高效性和准确性。     

A constraint-weaving approach to points-to analysis for AspectJ

Points-to analysis is a static code analysis technique that establishes the relationships between variables of references and allocated objects. A number of points-to analysis algorithms have been proposed for procedural and object-oriented languages like C and Java, while few of them can be used for AspectJ as we know so far. One main reason is that AspectJ is an aspect-oriented language which implements the separation of crosscutting concerns by advices, pointcuts, and inter-type declarations, while a points-to analysis of AspectJ programs may be imprecise because any aspect woven into the base code may change the points-to relations in the program and thus a conservative analysis has to be taken in order to handle the aspects. In this paper, we propose a context-sensitive points-to analysis technique called AJPoints for AspectJ. Similar to the weaving mechanism for AspectJ, AJPoints obtains the constraints and templates on the points-to relations for the base code and the aspects, respectively, but weaves and solves them in an iterative manner in order to cross the boundary between the base code and the aspects. We have implemented AJPoints on abc AspectJ compiler and evaluated it by using twelve AspectJ benchmark programs. The experimental results show that our technique can achieve a high precision about points-to relations in AspectJ programs.     

SUIF2平台下MOD分析算法的设计与实现

MOD问题是指在进行过程调用时哪些信息可能在被调用的过程中被修改。针对C语言,本文提出了一种基于流敏感、上下文敏感指针分析结果的MOD分析算法。该算法通过计算表达式在指向图中的左值,得到所有可能被修改的内存位置,从而计算出所有可能在被调用过程中被修改的表达式。我们在SUIF2平台下实现了该算法,得到了预期的实验结果。     

C代码API一致性检验中的等值分析

在实际中对C代码进行API一致性检验的过程中发现,API(application programming interface)规范大都涉及以数值为论域的时序性质,与在静态分析过程中所能获取的以变量符号为占位符的独立语义之间存在分析上的缺口.在仔细考察C代码变量符号间等值关系的基础上,给出基于值等价类空间的等值分析方法.这种流相关的分析方法不仅可以在API一致性检验的过程中维护变量符号域和数值域之间的对应关系,而且由于能够屏蔽等值关系以外的其他信息,还可以为后继分析的优化提供有力的支持.     

上下文敏感的纵向传播算法

通过基于包含的指针分析在线优化技术中的纵向传播方法,改进基于调用图上下文敏感指针分析的环消除技术,提出一种上下文敏感的纵向传播算法。初始化约束图,在约束图中进行环探测及其合并,执行差异传播并循环处理复杂约束,直到一次调用纵向传播例程后图中所有结点指向集不变为止,从而得到图中各结点到其指向集的映射。应用CIL工具的实验结果表明,该算法能有效地对源程序进行上下文敏感的指针分析,与环消除技术相比,在分析大规模程序时具有更高的时间效率。     

基于指向与数值抽象的带指针算术程序的分析方法

带指针算术的程序往往包含数组越界、缓冲区溢出等运行时错误。单纯的指针分析技术和数值分析技术都无法有效处理指针算术。为了将指针分析与数值分析相结合,首先提出一种新的指针内存模型,然后基于该模型设计了一个刻画指针指向关系和指针偏移量的抽象域。最后在抽象解释框架下,设计并实现了一个面向带指针算术C程序的静态分析工具原型PAA。实验结果表明,PAA能够有效地分析指针程序的指向关系和数值性质,并能够在效率和精度间取得合理的权衡。     

基于抽象解释的函数内联过程间分析优化方法

分析实际程序时往往需要分析程序中函数的调用, 一般使用过程间分析来实现全程序分析.函数内联是一种最为精确、易于实现的过程间分析方法.通过函数内联, 可以使得已有过程内分析方法和工具支持包含函数调用的程序的分析.但是, 函数内联后代码的规模急剧增加, 同时将产生大量中间变量, 增加程序分析的变量维度, 导致程序分析过程时空开销大大增加.本文考虑基于抽象解释框架下函数内联过程间分析的一些不足, 并提出相应优化方法.基于抽象解释的程序分析关注自动推导程序变量之间的不变式约束关系, 因此程序变量构成的程序环境大小(即各程序点处须考虑的相关变量集合)对分析的时空开销具有重要影响.为了减少函数内联后程序分析的开销, 本文提出了面向内联函数块的程序环境降维优化方法.该方法针对内联函数后的程序代码, 分析确定不同程序点处需维护的程序环境(即相关变量集合), 而不是所有程序点共享同一全局程序环境, 从而实现程序状态的降维.详细描述了基于该方法所实现的工具DRIP (Dimension Reduction for analyzing function Inlined Program) 的架构、模块及算法细节.并在WCET Benchmarks测试集开展了分析实验, 实验结果表明: DRIP在变量消除上取得的效果良好, 甚至在某些测试集上能减少一半以上的变量, 并在一定程度上降低了分析过程的时空开销.     

大规模源代码增量式资源泄漏检测方法

资源泄漏是影响软件质量和可靠性的一种重要软件缺陷,存在资源泄漏的程序长时间运行会由于资源耗尽而发生异常甚至崩溃.静态代码分析是进行资源泄漏检测的一种有效的技术手段,能够基于源代码或者二进制代码有效地发现程序中潜在的资源泄漏问题.然而,精确的资源泄漏检测算法的复杂性会随着程序规模的增加呈指数级增长,无法满足生产中即时对缺陷进行分析检测的实际应用需求.面向大规模源代码提出了一种增量式的静态资源泄漏检测方法,该方法支持过程间流敏感的资源泄漏检测,在用户编辑代码的过程中,从变更的函数入手,通过资源闭包、指向分析过滤等多种技术手段缩小资源泄漏检测范围,进而实现了大规模代码的即时缺陷分析与报告.实验结果表明：该方法在保证准确率的前提下,90%的增量检测实验可以在10s内完成,能够满足在用户编辑程序过程中对缺陷进行即时检测和报告的实际应用需求.