Java指针分析综述_谭添.pdf

Java 指针分析综述谭添1,2马晓星1,2许畅1,2马春燕3李樾1,21（南京大学计算机科学与技术系南京210023）2（计算机软件新技术国家重点实验室（南京大学）南京210023）3（西北工业大学软件学院西安710129）（）Survey on Java Pointer AnalysisTanTian1,2,MaXiaoxing1,2,XuChang1,2,MaChunyan3,andLiYue1,21（Department of Computer Science and Technology,Nanjing University,Nanjing 210023）2（National Key Laboratory for Novel Software Technology(Nanjing University),Nanjing 210023）3（School of Software,Northwestern Polytechnical University,Xian 710129）AbstractInrecentyears,staticprogramanalysishasbecomeoneofthekeytechniquestoensurethereliability,securityandefficiencyofsoftware.Asafundamentalprogramanalysistechnique,pointeranalysisprovidesaseriesoffundamentalinformationabouttheprogramforstaticprogramanalysis,suchasthepoints-torelationsofanyvariablesin the program,alias relations between variables,program call graph,and the reachability of heap objects.WeintroducetheimportantcontentsofJavapointeranalysis,includingpointeranalysisalgorithm,contextsensitivity,abstractionofheapobjects,handlingofcomplexlanguagefeatures,non-wholeprogrampointeranalysis,especiallywesort-outanddiscussselectivecontextsensitivity,whichistheresearchhotspotofpointeranalysisinrecentyears.Key wordspointeranalysis；aliasanalysis；Java；staticanalysis；contextsensitivity摘要近年来静态程序分析已成为保障软件可靠性、安全性和高效性的关键技术之一.指针分析作为基础程序分析技术为静态程序分析提供关于程序的一系列基础信息，例如程序任意变量的指向关系、变量间的别名关系、程序调用图、堆对象的可达性等.介绍了 Java 指针分析的重要内容：指针分析算法、上下文敏感、堆对象抽象、复杂语言特性处理、非全程序指针分析，特别是对近年来指针分析的研究热点选择性上下文敏感技术进行了梳理和讨论.关键词指针分析；别名分析；Java；静态分析；上下文敏感中图法分类号TP311指针分析（pointeranalysis），又称指向分析（points-toanalysis）或别名分析（aliasanalysis），是计算程序中的指针（或变量、引用）在运行时所能指向的内存位置（或对象）的一种静态程序分析技术.指针分析的结果通常可表示为指针与内存位置之间的指向关系（points-torelation）或每个指针的指针集（points-toset）.指针分析提供了程序中基础的数据流信息，对于一系列技术如编译优化1-3、故障检测4-6、安全分析7-11、程序理解12-13、程序验证14-15等具有重要作用.作为公认的最基础的静态分析技术之一1,16，指针分析这收稿日期：20221026；修回日期：20230111基金项目：国家自然科学基金项目（61932021，62025202，62002157）；航空科学基金项目（20185853038，201907053004）ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61932021，62025202，62002157),andtheAeronauticalScienceFund(20185853038，201907053004).通信作者：李樾（）计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202220901JournalofComputerResearchandDevelopment60（2）：274293，2023一研究领域已有超过 40 年的历史17，至今仍是静态程序分析学术研究的重点.指针分析通过对程序中语句语义的分析来计算指针的指向信息，因此指针分析与被分析语言的语义紧密相关，导致针对不同程序设计语言的指针分析技术呈现出较大的差异性.目前，主流指针分析的研究主要有两大流派，针对 Java 语言1,3,18-20与 C/C+语言21-25的指针分析研究.Java 作为一门典型的面向对象语言，其程序中绝大部分数据分配在堆上；而C/C+程序中许多数据分配在栈上，通常栈上的数据仅限于其声明的函数内部使用.而相比之下，堆上的数据可以跨函数存在，一般具有更大的活动范围和生存周期，因此更难以分析.此外，Java 具有反射、本地代码调用等 C/C+所没有的语言特性，会给指针分析造成很大挑战.Java 语言具有广泛的应用生态，近十 年 针对 Java 指 针 分 析 的 研 究 工 作 也 多 于 针 对C/C+的.因此，本文关注 Java 指针分析技术.衡量指针分析有效性有 3 个关键指标：效率（efficiency）、精度（precision）和可靠性（soundness）.快速的指针分析运行时间较短，可以更容易部署到实际生产当中，为相关的应用提供支撑；精准的指针分析，则可以提升相关应用的准确度（例如精度更高的指针分析，能使得程序代码在编译时有更多机会被优化，或使得以它为基础的错误检测工具具备更低的误报率）；可靠性更好的指针分析能覆盖更多程序行为（例如可使以它为基础的安全漏洞检测工具查出更多的安全问题）.因此，有效提升效率、精度和可靠性一直以来是指针分析领域的主要研究问题.本文将介绍指针分析提升这 3 个关键指标的经典技术以及近年来的主要研究进展.具体而言，相比于已有 Java 指针分析及其综述工作1,3（最近的一篇综述工作发表于 2015 年），本文的主要贡献包括 3 个方面：1）描述了更完整且简洁易懂的Java 指针分析算法；2）讨论了更多关于 Java 指针分析重要内容的研究工作（例如关于堆抽象、新语言特性处理、增量分析等方面的最新工作）；3）系统性地梳理并讨论了近年来 Java 指针分析的研究热点选择性上下文敏感技术.本节接下来简要介绍本文后续章节讨论的指针分析技术所针对的问题，方便读者理解这些研究的关联性，并了解本文结构.第 1 节介绍 Java 指针分析的基础规则和算法.由于 Java 程序的规模性以及 Java 语言的复杂性，基础的算法并不足以在效率、精度和可靠性方面满足对现实世界 Java 程序的分析需求，因此需要利用在第 24 节介绍的进阶技术对程序行为进行更有效的抽象与模拟.Java 程序中的一个方法在运行时可能被多次调用，每次被调用时都处于不同的调用上下文（callingcontext）中，并可能具有不同的指向关系.第 2 节介绍上下文敏感（contextsensitivity）技术.该技术本质上是对程序运行时调用栈（callstack）的抽象，通过对调用栈中上下文进行细化地建模，以减少指向关系混淆，是提升 Java 指针分析精度最主要的技术.Java 作为典型的面向对象语言，运行时会在堆上创建大量对象，因此研究人员引入堆对象抽象技术，在指针分析中对动态运行时的对象进行合理的抽象以保证指针分析的有效性.第 3 节介绍堆对象抽象的主要技术.第 13 节介绍的技术主要针对 Java 基础特性，但 Java 作为一门工业级语言，其具有复杂的语言特性，其中一些关键特性（如反射）对指针分析的结果，尤其是对可靠性会产生较大影响.第 4 节介绍现有技术如何在指针分析中处理这些关键的复杂语言特性.第 14 节介绍的指针分析技术主要针对全程序指针分析，全程序指针分析一般开销相对较大（尤其是对于复杂程序），但用户通常希望能够尽快获得指针分析结果.研究人员发现在一些特定的实际应用场景中，并不需要分析整个程序，因此提出非全程序指针分析技术，在只分析部分程序的前提下也能获得满足用户需求的结果.第 5 节介绍这一类技术的代表性工作.1指针分析算法为了便于介绍 Java 指针分析技术和详细理解指针分析，本文设计了一套较为完整且易于理解的Java 指针分析算法.本节先介绍该算法分析的 Java中的指针和语句，然后详细介绍算法本身.1.1Java 中的指针在指针分析中，我们主要关注引用类型（referencetype）指针.由于原子类型（primitivetype）变量与字段不能指向堆上的对象，因此它们通常不在指针分析所考虑的范围内.Java 指针可分为 4 类：1）局部变量，如 x，即声明在方法内部的变量.这也是程序中数量最多的一种指针.2）静态字段，如 C.f，静态字段的处理方式与局谭添等：Java 指针分析综述275部 变 量 类 似（文 献 3 将 其 称 为 全 局 变 量（globalvariable）.为了简化算法，本文接下来忽略静态字段及其相关语句的处理.3）实例字段，如 x.f，Java 程序中可以写出复杂的实例字段访问表达式，如 x.f.g.h，但这种复杂的表达式不易于分析，因此通常在分析前先引入临时变量将程序转换为三地址码（如语句 v=x.f.g 会被转换为t=x.f 和 v=t.g;）再进行分析.4）数组元素，如 ai.由于许多情况下静态分析无法获取准确的数组长度以及索引值，因此指针分析通常会忽略数组长度，且不区分具体的索引值，并将数组对象建模为只有一个特殊实例字段 arr 的对象，且该字段指向所有被存入数组的元素，如表 1 的例子所示.Table 1Comparison of Real Code and Array Modeling ofPointer Analysis表 1 真实代码与指针分析对数组建模的对比真实代码指针分析数组建模array=newString10;array0=x;array1=y;s=array0;array=newString;array.arr=x;array.arr=y;s=array.arr;指针分析对数组进行特殊的建模后，对数组元素的处理与实例对象一致，因此本文在算法中不再讨论对数组元素及其相关语句的处理.综上所述，为了简化算法，本文只考虑局部变量与实例字段.1.2影响指针的 Java 语句Java 有许多种语句，但在指针分析中，只需要关注直接影响指针的语句.当只考虑局部变量与实例字段时，影响指针分析的语句有 5 种：1）对象创建，如 x=newT（）；2）复制，如 x=y；3）字段存储，如 x.f=y；4）字段读取，如 y=x.f；5）方法调用，如 r=x.m（a,）.这 5 种语句最复杂的是方法调用语句.Java 有 3种方法调用：静态调用（staticinvocation）、特殊调用（specialinvocation）和虚调用（virtualinvocation）.其