Java 指針分析綜述

譚 添 馬曉星 許 暢 馬春燕 李 樾

1（南京大學(xué)計算機科學(xué)與技術(shù)系 南京 210023）

2（計算機軟件新技術(shù)國家重點實驗室（南京大學(xué)）南京 210023）

3（西北工業(yè)大學(xué)軟件學(xué)院 西安 710129）

指針分析（pointer analysis），又稱指向分析（pointsto analysis）或別名分析（alias analysis），是計算程序中的指針（或變量、引用）在運行時所能指向的內(nèi)存位置（或?qū)ο螅┑囊环N靜態(tài)程序分析技術(shù).指針分析的結(jié)果通?？杀硎緸橹羔樑c內(nèi)存位置之間的指向關(guān)系（points-to relation）或每個指針的指針集（points-to set）.指針分析提供了程序中基礎(chǔ)的數(shù)據(jù)流信息，對于一系列技術(shù)如編譯優(yōu)化[1-3]、故障檢測[4-6]、安全分析[7-11]、程序理解[12-13]、程序驗證[14-15]等具有重要作用.作為公認的最基礎(chǔ)的靜態(tài)分析技術(shù)之一[1,16]，指針分析這一研究領(lǐng)域已有超過40 年的歷史[17]，至今仍是靜態(tài)程序分析學(xué)術(shù)研究的重點.

指針分析通過對程序中語句語義的分析來計算指針的指向信息，因此指針分析與被分析語言的語義緊密相關(guān)，導(dǎo)致針對不同程序設(shè)計語言的指針分析技術(shù)呈現(xiàn)出較大的差異性.目前，主流指針分析的研究主要有兩大流派，針對Java 語言[1,3,18-20]與C/C++語言[21-25]的指針分析研究.Java 作為一門典型的面向?qū)ο笳Z言，其程序中絕大部分數(shù)據(jù)分配在堆上；而C/C++程序中許多數(shù)據(jù)分配在棧上，通常棧上的數(shù)據(jù)僅限于其聲明的函數(shù)內(nèi)部使用.而相比之下，堆上的數(shù)據(jù)可以跨函數(shù)存在，一般具有更大的活動范圍和生存周期，因此更難以分析.此外，Java 具有反射、本地代碼調(diào)用等C/C++所沒有的語言特性，會給指針分析造成很大挑戰(zhàn).Java 語言具有廣泛的應(yīng)用生態(tài)，近十年針對Java 指針分析的研究工作也多于針對C/C++的.因此，本文關(guān)注Java 指針分析技術(shù).

衡量指針分析有效性有3 個關(guān)鍵指標：效率（efficiency）、精度（precision）和可靠性（soundness）.快速的指針分析運行時間較短，可以更容易部署到實際生產(chǎn)當中，為相關(guān)的應(yīng)用提供支撐；精準的指針分析，則可以提升相關(guān)應(yīng)用的準確度（例如精度更高的指針分析，能使得程序代碼在編譯時有更多機會被優(yōu)化，或使得以它為基礎(chǔ)的錯誤檢測工具具備更低的誤報率）；可靠性更好的指針分析能覆蓋更多程序行為（例如可使以它為基礎(chǔ)的安全漏洞檢測工具查出更多的安全問題）.因此，有效提升效率、精度和可靠性一直以來是指針分析領(lǐng)域的主要研究問題.本文將介紹指針分析提升這3 個關(guān)鍵指標的經(jīng)典技術(shù)以及近年來的主要研究進展.

具體而言，相比于已有Java 指針分析及其綜述工作[1,3]（最近的一篇綜述工作發(fā)表于2015 年），本文的主要貢獻包括3 個方面：

1）描述了更完整且簡潔易懂的Java 指針分析算法；

2）討論了更多關(guān)于Java 指針分析重要內(nèi)容的研究工作（例如關(guān)于堆抽象、新語言特性處理、增量分析等方面的最新工作）；

3）系統(tǒng)性地梳理并討論了近年來Java 指針分析的研究熱點——選擇性上下文敏感技術(shù).

本節(jié)接下來簡要介紹本文后續(xù)章節(jié)討論的指針分析技術(shù)所針對的問題，方便讀者理解這些研究的關(guān)聯(lián)性，并了解本文結(jié)構(gòu).

第1 節(jié)介紹Java 指針分析的基礎(chǔ)規(guī)則和算法.由于Java 程序的規(guī)模性以及Java 語言的復(fù)雜性，基礎(chǔ)的算法并不足以在效率、精度和可靠性方面滿足對現(xiàn)實世界Java 程序的分析需求，因此需要利用在第2～4 節(jié)介紹的進階技術(shù)對程序行為進行更有效的抽象與模擬.

Java 程序中的一個方法在運行時可能被多次調(diào)用，每次被調(diào)用時都處于不同的調(diào)用上下文（calling context）中，并可能具有不同的指向關(guān)系.第2 節(jié)介紹上下文敏感（context sensitivity）技術(shù).該技術(shù)本質(zhì)上是對程序運行時調(diào)用棧（call stack）的抽象，通過對調(diào)用棧中上下文進行細化地建模，以減少指向關(guān)系混淆，是提升Java 指針分析精度最主要的技術(shù).

Java 作為典型的面向?qū)ο笳Z言，運行時會在堆上創(chuàng)建大量對象，因此研究人員引入堆對象抽象技術(shù)，在指針分析中對動態(tài)運行時的對象進行合理的抽象以保證指針分析的有效性.第3 節(jié)介紹堆對象抽象的主要技術(shù).

第1～3 節(jié)介紹的技術(shù)主要針對Java 基礎(chǔ)特性，但Java 作為一門工業(yè)級語言，其具有復(fù)雜的語言特性，其中一些關(guān)鍵特性（如反射）對指針分析的結(jié)果，尤其是對可靠性會產(chǎn)生較大影響.第4 節(jié)介紹現(xiàn)有技術(shù)如何在指針分析中處理這些關(guān)鍵的復(fù)雜語言特性.

第1～4 節(jié)介紹的指針分析技術(shù)主要針對全程序指針分析，全程序指針分析一般開銷相對較大（尤其是對于復(fù)雜程序），但用戶通常希望能夠盡快獲得指針分析結(jié)果.研究人員發(fā)現(xiàn)在一些特定的實際應(yīng)用場景中，并不需要分析整個程序，因此提出非全程序指針分析技術(shù)，在只分析部分程序的前提下也能獲得滿足用戶需求的結(jié)果.第5 節(jié)介紹這一類技術(shù)的代表性工作.

1 指針分析算法

為了便于介紹Java 指針分析技術(shù)和詳細理解指針分析，本文設(shè)計了一套較為完整且易于理解的Java 指針分析算法.本節(jié)先介紹該算法分析的Java中的指針和語句，然后詳細介紹算法本身.

1.1 Java 中的指針

在指針分析中，我們主要關(guān)注引用類型（reference type）指針.由于原子類型（primitive type）變量與字段不能指向堆上的對象，因此它們通常不在指針分析所考慮的范圍內(nèi).Java 指針可分為4 類：

1）局部變量，如x，即聲明在方法內(nèi)部的變量.這也是程序中數(shù)量最多的一種指針.

2）靜態(tài)字段，如C.f，靜態(tài)字段的處理方式與局部變量類似（文獻[3]將其稱為全局變量（global variable））.為了簡化算法，本文接下來忽略靜態(tài)字段及其相關(guān)語句的處理.

3）實例字段，如x.f，Java 程序中可以寫出復(fù)雜的實例字段訪問表達式，如x.f.g.h，但這種復(fù)雜的表達式不易于分析，因此通常在分析前先引入臨時變量將程序轉(zhuǎn)換為三地址碼（如語句v=x.f.g會被轉(zhuǎn)換為t=x.f和v=t.g;）再進行分析.

4）數(shù)組元素，如a[i].由于許多情況下靜態(tài)分析無法獲取準確的數(shù)組長度以及索引值，因此指針分析通常會忽略數(shù)組長度，且不區(qū)分具體的索引值，并將數(shù)組對象建模為只有一個特殊實例字段arr的對象，且該字段指向所有被存入數(shù)組的元素，如表1 的例子所示.

Table 1 Comparison of Real Code and Array Modeling of Pointer Analysis表1 真實代碼與指針分析對數(shù)組建模的對比

指針分析對數(shù)組進行特殊的建模后，對數(shù)組元素的處理與實例對象一致，因此本文在算法中不再討論對數(shù)組元素及其相關(guān)語句的處理.

綜上所述，為了簡化算法，本文只考慮局部變量與實例字段.

1.2 影響指針的Java 語句

Java 有許多種語句，但在指針分析中，只需要關(guān)注直接影響指針的語句.當只考慮局部變量與實例字段時，影響指針分析的語句有5 種：

1）對象創(chuàng)建，如x=newT（）；

2）復(fù)制，如x=y；

3）字段存儲，如x.f=y；

4）字段讀取，如y=x.f；

5）方法調(diào)用，如r=x.m（a,…）.

這5 種語句最復(fù)雜的是方法調(diào)用語句.Java 有3種方法調(diào)用：靜態(tài)調(diào)用（static invocation）、特殊調(diào)用（special invocation）和虛調(diào)用（virtual invocation）.其中虛調(diào)用的處理最為復(fù)雜，而靜態(tài)調(diào)用與特殊調(diào)用的處理邏輯均可視為虛調(diào)用處理邏輯的簡化.因此本文關(guān)注虛調(diào)用的處理.

1.3 算 法

指針分析算法的輸入是一個Java 程序，輸出是程序中每個指針可能指向的對象集合，算法運行過程中在線地解析方法調(diào)用，因此運行結(jié)束后也輸出程序的調(diào)用圖.為了便于理解算法，本文在表2 中列出了算法中所用到的符號以及相關(guān)域.

Table 2 Notations and Domains Used in Pointer Analysis Algorithm表2 指針分析算法符號與域的說明

Pointer表示程序中指針的集合.本文關(guān)注變量與實例字段，因此Pointer由變量集合（V）與實例字段集合（O×F，即對象集合O與字段集合F的笛卡爾乘積）組成.本文用指向關(guān)系pt表示指針分析的結(jié)果，pt（p）表示指針p指向的對象集合，即p的指針集（points-to set）.此處 P（O）表示對象集合O的冪集.

本節(jié)介紹的指針分析是一種Andersen 風(fēng)格的指針分析[21]，即它是流不敏感（flow-insensitive）且基于子集約束（subset constraint）的指針分析.流不敏感意味著指針分析不考慮程序語句的執(zhí)行順序[26]，并將程序語句視為一個無序集合[1].子集約束指程序中的指針發(fā)生賦值時，指針分析將建立相應(yīng)指針間的子集約束關(guān)系，例如對于語句x=y，分析將建立約束pt（y）?pt（x）并保證分析結(jié)果滿足約束[3,21].此外，本節(jié)介紹的是上下文非敏感（context-insensitive）指針分析，即不區(qū)分每個方法在不同調(diào)用上下文（calling context）中指向信息的差別.本文在第3 節(jié)介紹如何將本節(jié)的算法擴展成上下文敏感（context-sensitive）指針分析從而提升精度.

1）指針分析規(guī)則.表3 給出了指針分析對1.2 節(jié)所述的影響指針語句的處理規(guī)則（下文將在描述算法時介紹表3 中的列4“PFG 邊”，此處讀者只需關(guān)注左邊3 列）.這套規(guī)則描述了標準的Java 指針分析規(guī)則，反映不同語句如何影響相應(yīng)指針的指針集，同時也描述了指針之間子集約束的建立，本質(zhì)上與文獻[1,3]中所描述的指針分析等價.

表3 中的規(guī)則大部分較為直觀，對于對象創(chuàng)建語句，本文定義Heap（i）函數(shù)，將程序中的對象創(chuàng)建點（allocation site）i映射成 對應(yīng)的 抽象對 象（abstract object）oi，Heap（）函數(shù)的具體實現(xiàn)對應(yīng)不同的堆抽象技術(shù)，本文在第3 節(jié)更詳細地討論了堆抽象.對于方法調(diào)用語句的分析規(guī)則相對復(fù)雜，本文定義輔助函數(shù)Dispatch（oi,k），根據(jù)對象oi的類型以及調(diào)用點k的方法簽名，計算出調(diào)用點l以oi作為接收者對象（receiver object）時具體的目標方法m.此過程遵循標準的類繼承結(jié)構(gòu)查找算法[1,27].得到m后，分析規(guī)則描述如何在l與m的相關(guān)變量之間傳遞對象，其中mret表示m中指向返回值的變量，mthis表示m的this 變量，mpj表示m的第j個形參.

Table 3 Rules for Pointer Analysis表3 指針分析規(guī)則

2）指針分析算法.本文設(shè)計的指針分析算法是表3 中指針分析規(guī)則的命令式風(fēng)格實現(xiàn)，而實現(xiàn)指針分析算法的關(guān)鍵在于如何滿足各相關(guān)指針間的子集約束關(guān)系.本文使用 指針流 圖（pointer flow graph,PFG）來表示指針間的子集約束關(guān)系，具體地說，PFG的每一個結(jié)點都對應(yīng)程序中的一個指針，若指針s與t存在約束關(guān)系pt（s）?pt（t），則算法在PFG 上添加邊s→t，并在分析過程中沿著s→t傳播指向關(guān)系，確保s指向的所有對象都被包含于pt（t）中.本質(zhì)上，PFG 類似于Andersen 風(fēng)格指針分析技術(shù)[21]中的約束圖（constraint graph）[28].表3 給出指針分析規(guī)則，其中在列4 給出了添加PFG 邊的規(guī)則.而指針分析算法的核心思路就是根據(jù)程序中的語句和表3 的規(guī)則構(gòu)造PFG，并在PFG 上傳播指向關(guān)系，直至算法到達不動點.

算法1 給出了本文設(shè)計的指針分析算法.該算法遵循上述思路，構(gòu)建PFG 并在此基礎(chǔ)上傳播和計算程序中各指針的指針集.此外，算法1 是一個全程序分析，在指針分析的過程中同步構(gòu)造出程序的調(diào)用圖.

算法1.指針分析算法.

輸入：程序入口方法mentry；

輸出：指向關(guān)系pt，調(diào)用圖CG.

Solve（mentry）是整個算法的主函數(shù)，它的輸入mentry是程序的入口方法（對應(yīng)Java 程序的main 方法）.Solve（）首先初始化5 個貫穿算法始終的數(shù)據(jù)結(jié)構(gòu)：

①WL，表示算法的工作列表（work list）.WL中的元素是指針與對象集合組成的對（pair），元素表示待處理的指向關(guān)系.例如WL中若存在元素〈n,pts〉，則表示算法發(fā)現(xiàn)集合pts中的對象應(yīng)當加入到指針集pt（n）中.注意，當算法發(fā)現(xiàn)新的指向關(guān)系時，并不是直接更新pt，而是將信息加入WL等待后續(xù)處理，這是因為對于新指向關(guān)系的處理并不只是更新pt，還包括沿著PFG 傳播新信息以及對以字段存儲/讀取、方法調(diào)用等相關(guān)語句的一系列處理，因此算法將所有新的指向信息加入WL，便于統(tǒng)一操作.

②PFG，表示指針流圖PFG 邊的集合.

③S，表示被程序的可達語句集合.

④RM，表示程序的可達方法（reachable method）集合.

⑤CG，表示程序的調(diào)用邊（call edge）集合，每條調(diào)用邊的源點是程序中的一個調(diào)用點（call site），終點是調(diào)用的目標方法.

Solve（）調(diào)用AddReachable（）函數(shù)并傳入入口方法mentry.當算法發(fā)現(xiàn)新的可達方法時，會調(diào)用AddReachable（）處理新方 法內(nèi)的語句.對于參數(shù)m，AddReachable（）首先檢查m是否已經(jīng)在可達方法集合RM中，如果是，說明m已經(jīng)處理過，可以直接返回從而避免冗余計算.對于此前未遇到過的方法m，AddReachable（）將其加入RM，并將m中的語句（Sm表示方法m中的語句集合）加入可達語句集合S.隨后處理m的對象創(chuàng)建以及復(fù)制語句.

對于對象創(chuàng)建語句，算法使用Heap（i）函數(shù)，將程序中的對象創(chuàng)建點（allocation site）i映射成對應(yīng)的抽象對象（abstract object）oi，得到oi后，算法將其作為新發(fā)現(xiàn)的變量x的指向關(guān)系加入WL中.

對于復(fù)制語句的處理很簡單，只需調(diào)用AddEdge（）函數(shù)添 加對應(yīng) 的PFG 邊即可.此處的AddEdge（s,t）函數(shù)用 于向集 合PFG中添加s→t的邊.由于算法添加邊s→t時，pt（s）可能已經(jīng)指向了一些對象，為了確保PFG 邊表示的約束成立，即pt（t）指向pt（s）中所有對象，算法在添加s→t時，也將〈t,pt（s）〉加入工作列表WL中.邊s→t添加之后，s指向的新對象將由Propagate（）函數(shù)傳播給t.

分析完入口方法之后，Solve（）進入主循環(huán)，反復(fù)地取出WL中的元素進行處理，處理的過程中也可能發(fā)現(xiàn)新的指向關(guān)系并加入WL，直至WL為空（不再有新的指向關(guān)系被發(fā)現(xiàn)）.對于從WL取出的元素〈n,pts〉，隨著算法進程的推進，pts很可能包含許多pt（n）已經(jīng)指向的對象，因此為了減少冗余傳播與計算，提升算法效率，Solve（）在處理〈n,pts〉時使用差異傳播（difference propagation）技術(shù)[18,29]，即在處理pts中的對象之前，先將其與pt（n）做差集，取出pt（n）此前未包含的對象并存入差集Δ，而Δ 中的對象才代表真正新的指向關(guān)系.在Solve（）接下來的部分都對通常規(guī)模更小的Δ（而非pts）進行操作.

得到Δ 之后，Solve（）調(diào)用Propagate（n,Δ）將Δ 中的對象全部加入到指針n對應(yīng)的指針集中（即pt（n）），并傳播至n在PFG 中的所有后繼.

若n表示一個變量x對應(yīng)的指針，則Solve（）需要處理與x相關(guān)的字段存儲/讀取,以及方法調(diào)用語句.本文基于指針流圖PFG 的設(shè)計使得算法對于字段存儲/讀取語句的處理相當簡單.以字段存儲語句為例，若可達語句集合S中存在語句x.f=y，且算法發(fā)現(xiàn)x指向?qū)ο髈i（oi屬于新發(fā)現(xiàn)的對象集合Δ），則算法只需調(diào)用AddEdge（y,oi.f）在PFG 上添加一條變量y到實例字段oi.f的邊，使得oi.f的指針集包含y所指向的對象.而對于字段讀取語句的處理與字段存儲對稱，也只需調(diào)用AddEdge（）即可.關(guān)于方法調(diào)用的處理相對復(fù)雜，算法用一個輔助函數(shù)ProcessCall（）實現(xiàn)相關(guān)邏輯.

ProcessCall（x,oi）處理與變量x以及其指向的對象oi相關(guān)的調(diào)用，當算法發(fā)現(xiàn)變量x指向新的對象oi時，ProcessCall（）枚舉變量x指向接收者對象的調(diào)用點（形如x.k（…）），并對每個調(diào)用點進行處理：

1）解析目標方法.本文定義輔助函數(shù)Dispatch（oi,k），根據(jù)對象oi的類型以及調(diào)用點k的方法簽名計算出以oi作為接收者對象的具體目標方法m.

2）傳遞接收者對象.將接收者對象oi傳入目標方法的this 變量中（mthis表示方法m的this 變量）.

3）處理調(diào)用邊.當ProcessCall（）在 第1 步通過Dispatch（）得到調(diào)用目標方法m時，實際上也分析出了程序的一條調(diào)用邊l→m（l表示調(diào)用點的標號）.ProcessCall（）首先檢查l→m是否已在調(diào)用邊集合CG中，如果是，說明l→m已經(jīng)處理過，可以直接返回從而避免冗余計算；若l→m是新發(fā)現(xiàn)的調(diào)用邊，則將其加入CG，并且m有可能是新發(fā)現(xiàn)的可達方法，因此調(diào)用AddReachable（m）對其進行處理.然后，算法使用AddEdge（）將調(diào)用點的實參傳入目標方法的形參（本文用ai表示調(diào)用點l的第i個實參，pi表示方法m的第i個形參），并將目標方法的返回值傳回調(diào)用語句的左值（本文用mret表示方法m中指向返回值的變量）.

算法結(jié)束后，可得到程序中各變量、實例字段的指針集（存放于pt）以及程序的調(diào)用圖（存放于CG）.

2 上下文敏感

Java 程序中的一個方法在運行時可能被多次調(diào)用，每次被調(diào)用時都處于不同的調(diào)用上下文（calling context）中，上下文敏感（context sensitivity）技術(shù)[30]就是研究如何在靜態(tài)分析（如指針分析）中對動態(tài)運行時的上下文進行建模和分析.上下文敏感可以區(qū)分同一方法在不同上下文中的數(shù)據(jù)流，從而減少數(shù)據(jù)流的混淆并提升精度.圖1 用一個例子解釋上下文敏感的思路及其作用.

在圖1 的代碼片段中，方法identity（）分別被foo（）和bar（）調(diào)用，foo（）調(diào)用identity（）時傳給其字符串“foo”作為參數(shù)，然后由變量r1接收其返回值，顯而易見，運行時變量r1指向字符串“foo”.bar（）與之類似，運行時r2將指向字符串“bar”.然而，若使用1.3節(jié)介紹的上下文非敏感指針分析算法分析這段程序，則identity（）中的變量s會指向{“foo”,“bar”}，且這2 個字符串會傳播給r1與r2，使得r1與r2都指向{“foo”,“bar”}，導(dǎo)致指針分析結(jié)果不精確（實際運行時，r1或r2不指向“bar”或“foo”）.

Fig.1 An example for illustrating context sensitivity圖1 解釋上下文敏感的例子

造成圖1 的例子中精度丟失的原因在于方法identity（）在運行時有2 個調(diào)用上下文（來自foo（）與bar（）），并且identity（）內(nèi)的變量s在2 個上下文中指向不同對象（分別為“foo”與“bar”）.然而上下文非敏感分析并不區(qū)分這2 個上下文，因此2 個上下文中的數(shù)據(jù)流在identity（）內(nèi)部混淆，并且傳遞給了r1與r2.而上下文敏感分析的思路是將identity（）的不同調(diào)用上下文加以區(qū)分并分別分析，從而避免數(shù)據(jù)流的混淆以提升精度.

目前，上下文敏感是提升Java 指針分析精度公認最有效的方法[20,31-34]，多年來一直是該領(lǐng)域的研究重點.2.1 節(jié)將1.3 節(jié)介紹的指針分析算法擴展成上下文敏感指針分析算法，2.2 節(jié)與2.3 節(jié)分別介紹傳統(tǒng)上下文敏感技術(shù)以及近年來的相關(guān)研究熱點，選擇性上下文敏感技術(shù).

2.1 上下文敏感指針分析算法

在上下文敏感指針分析中，程序中的每個方法會被冠以上下文，用c:m表示（c表示某個上下文），稱為上下文敏感方法.每個上下文可以被視為一個標識符，用于將該上下文中的方法（如c:m）與其它上下文中的同一方法（如c′:m）加以區(qū)分.此外，通常每個方法中的變量與創(chuàng)建出的對象也繼承該方法的上下文，成為上下文敏感變量與對象.不同上下文中的變量以及對象的實例字段可指向不同對象，從而達到實現(xiàn)對不同上下文數(shù)據(jù)流的區(qū)分.而具體上下文的生成取決于指針分析使用的上下文敏感技術(shù)，本文在2.2～2.3 節(jié)進行介紹.

表4 列出了上下文敏感指針分析算法用到的符號以及相關(guān)域.表4 與表2 相比的區(qū)別在于，上下文敏感分析中程序的方法、變量、對象被冠以上下文.相應(yīng)地，指向關(guān)系pt相關(guān)的 域，即指針集合（CSPointer）和對象集合中的元素也都帶有上下文.

1）指針分析規(guī)則.表5 給出了上下文敏感指針分析的規(guī)則.假設(shè)表中語句所在方法的當前上下文為c，則相關(guān)語句的變量的上下文都是c，如復(fù)制語句的變量x和y、字段存儲語句的變量x和y等，因為同一語句的變量必然聲明在同一方法內(nèi)，因此它們具有相同的上下文.表5 給出的分析規(guī)則與表3 的上下文非敏感指針分析在本質(zhì)上都可視為Andersen 風(fēng)格指針分析（描述了程序各指針之間如何建立子集約束），表5 與表3 的區(qū)別在于上下文敏感分析中的指針都帶有上下文，可以使不同上下文中的指向關(guān)系得以分開分析，從而提升精度.

Table 4 Notations and Domains Used in Context-Sensitive Pointer Analysis Algorithm表4 上下文敏感指針分析算法符號與域的說明

在上下文敏感指針分析中，方法調(diào)用的規(guī)則最為重要和復(fù)雜，因為它涉及到上下文的生成.具體地說，本文定義Select（c,l,c':oi）函數(shù)，根據(jù)調(diào)用點的信息（當前調(diào)用者上下文c，調(diào)用點標號l，接收者對象c':oi）生成目標方法m（與表3 中上下文非敏感分析一樣，由Dispatch 得到）的上下文ct.Select（）函數(shù)的具體實現(xiàn)對應(yīng)不同的上下文敏感技術(shù)，本文將在2.2～2.3節(jié)展開討論.得到目標方法的上下文ct后，指針分析規(guī)則在c中l(wèi)的變量與m在ct中的變量之間互相傳遞對象.由于m的ct是根據(jù)調(diào)用點的信息生成的，因此m也與當前調(diào)用建立了關(guān)聯(lián)，從而可以與m的其它上下文（例如由其它調(diào)用點發(fā)起的調(diào)用）區(qū)分開，從而避免不同上下文數(shù)據(jù)流混淆造成的精度丟失.

2）指針分析算法.本文設(shè)計的上下文敏感指針分析算法如算法2 所示.該算法是由算法1（上下文非敏感指針分析算法）擴展而成，算法的思路仍是構(gòu)建指針流圖PFG 用于表達子集約束關(guān)系，并沿著PFG 傳播指向關(guān)系直至到達不動點.表5 的列4 給出了添加PFG 邊的規(guī)則.在上下文敏感分析中，PFG 的結(jié)點都是帶有上下文的指針.由于算法2 的流程與算法1 一致，因此本文不再贅述.

接下來介紹算法2 中與上下文敏感相關(guān)的改動部分.與算法1 算法一樣，算法2 中的Solve（）首先初始化5 個關(guān)鍵數(shù)據(jù)結(jié)構(gòu).這些數(shù)據(jù)結(jié)構(gòu)起到的作用與算法1 一致，區(qū)別在于它們的元素（除了可達語句集合S）都帶有上下文，例如可達方法集合RM中的元素是上下文敏感方法（如c:m）.對于可達語句集合S中的元素（語句），其上下文信息可從該語句的變量或語句所在的方法中獲得，因此S中的語句無需攜帶上下文.然后，Solve（）調(diào)用AddReachable（）處理入口方法mentry.由于算法2 做上下文敏感分析，因此AddReachable（）的參數(shù)是帶上下文的方法，如c:m，這意味著同一個方法可能會在不同上下文中被AddReachable（）分析多次.此處mentry方法并沒有調(diào)用者，因此算法給予其空上下文“[ ]”.在AddReachable（c:m）內(nèi)部處理對象創(chuàng)建以及復(fù)制語句時，都會將方法的上下文c賦予相關(guān)的變量以及對象.然后Solve（）進入主循環(huán).算法2 使用的輔助函數(shù)AddEdge（）和Propagate（）與算法1 所定義的完全一致，因此就不再重復(fù)給出.在主循環(huán)的最后，算法調(diào)用擴展后的ProcessCall（）處理方法調(diào)用.

Table 5 Rules for Context-Sensitive Pointer Analysis表5 上下文敏感指針分析規(guī)則

算法2.上下文敏感指針分析算法.

輸入：程序入口方法mentry；

輸出：指向關(guān)系pt，調(diào)用圖CG.

ProcessCall（c:x,c':oi）總體邏輯與算法1中的ProcessCall（x,oi）相似，但多了一個關(guān)鍵步驟：上下文的生成.如上文所述，本文定義Select（c,l,c':oi）函數(shù)，根據(jù)調(diào)用點的信息，選擇目標方法的上下文.除了入口方法mentry，其余所有方法的上下文都在此處生成.生成上下文ct后，ProcessCall（）將其賦予目標方法m，添加相關(guān)調(diào)用邊，并根據(jù)表5 所列的規(guī)則在調(diào)用點和目標方法之間傳遞參數(shù)以及返回值.

算法2 結(jié)束后，可得到上下文敏感的指針分析結(jié)果（pt）以及上下文敏感的程序調(diào)用圖（CG）.

關(guān)于算法2 的更多實現(xiàn)細節(jié)，可參考Tai-e[35-36].Tai-e 是最新的通用型Java 程序分析框架（與Soot、WALA 類似）.本文將上述上下文敏感指針分析算法作為核心算法實現(xiàn)在Tai-e 的指針分析系統(tǒng)中.實驗結(jié)果表明[35]，Tai-e 指針分析系統(tǒng)的效率與可靠性均優(yōu)于已有指針分析工具[37-39].此外，本文為Tai-e 指針分析系統(tǒng)設(shè)計了一套插件機制，使其具有良好的擴展性，使得開發(fā)者能夠方便地開發(fā)需要與指針分析交互的分析技術(shù)（如反射分析、異常分析、污點分析等），關(guān)于指針分析插件機制的設(shè)計可以參考文獻[35].

2.2 傳統(tǒng)上下文敏感

本節(jié)介紹幾種Java 指針分析最常用的傳統(tǒng)上下文敏感技術(shù)，并將給出這些技術(shù)對應(yīng)的Select（c,l,c':oi）函數(shù)（見表5 與算法2）的具體定義.這些傳統(tǒng)上下文敏感技術(shù)也是2.3 節(jié)介紹的選擇性上下文敏感的基礎(chǔ).

1）調(diào)用點敏感.調(diào)用點敏感（call-site sensitivity）[30,40-41]，又稱調(diào)用串敏感（call-string sensitivity）或k-CFA，是最早誕生的上下文敏感技術(shù).調(diào)用點敏感的每個上下文由一串調(diào)用點組成（具體實現(xiàn)中，通常會給程序中的每個調(diào)用點賦予一個唯一的標號，并用標號表示相應(yīng)的調(diào)用點），當分析調(diào)用點l時，調(diào)用點敏感將l所在方法的上下文加上l自身，作為目標方法的上下文.對應(yīng)的Select（）函數(shù)定義為（下劃線表示無關(guān)的參數(shù)）：

因此，在調(diào)用點敏感中，一個方法的上下文由它的l和l所在方法的調(diào)用點等一系列調(diào)用點構(gòu)成，本質(zhì)上是模擬程序動態(tài)運行時每個方法的調(diào)用棧.然而，上述Select（）函數(shù)分析遞歸方法時會產(chǎn)生無窮無盡的上下文；此外，真實Java 程序運行時的調(diào)用棧往往很深，若Select（）函數(shù)模擬所有可能的調(diào)用棧，則會產(chǎn)生數(shù)量巨大的上下文，使得指針分析開銷過大，無法在合理時間內(nèi)完成.因此，為了解決這2 個問題，實際的調(diào)用點敏感會限制上下文的層數(shù)，稱為k限制（k-limiting），即選取最靠近目標方法的k個調(diào)用點作為上下文.例如，k=1 時，相 應(yīng)Select（）函數(shù)定義 為Select（_,l,_）=[l]，即只取最近一個調(diào)用點作為上下文.k限制損失了精度，但可以顯著提升指針分析的效率和可擴展性（scalability），因此本文介紹的其他上下文敏感技術(shù)也通常會采取這種方式.

2）對象敏感.2002 年，Milanova 等人針對面向?qū)ο笳Z言的特征，提出對象敏感（object sensitivity）技術(shù)[42-43].具體地說，對象敏感技術(shù)使用調(diào)用點的接收者對象作為上下文，相應(yīng)的Select（）函數(shù)定義為：

對象敏感技術(shù)的思想在于它捕捉了面向?qū)ο蟪绦虻囊粋€特征，即許多方法的行為都是對接收者對象（即this 變量指向的對象）狀態(tài)的修改（如setX（）方法）與訪問（如getX（）方法），而以接收者對象作為上下文，可以區(qū)分對于不同對象的操作，從而提升精度.與調(diào)用點敏感一樣，實際應(yīng)用中，對象敏感技術(shù)也使用k-limiting 的方式限制上下文層數(shù).當上下文層數(shù)限制k一致時，理論上調(diào)用點敏感與對象敏感的精度無法直接比較（即存在一些情況，調(diào)用點敏感更準確，也同時存在一些情況使得對象敏感可以獲得更高精度），但已有研究表明，在實際情況中，對于Java 程序，對象敏感的效率與精度都優(yōu)于調(diào)用點敏感[20,34,42-44].因此，對象敏感也是提升面向?qū)ο笳Z言指針分析精度的主要技術(shù).

對象敏感綜合表現(xiàn)優(yōu)于調(diào)用點敏感，但它處理Java 靜態(tài)方法調(diào)用（static method call）時，由于靜態(tài)方法沒有接收者對象，因此已有對象敏感通常只能使用調(diào)用者（caller）的上下文作為目標方法的上下文，不能根據(jù)調(diào)用點信息進一步區(qū)分上下文.對于這一問題，Kastrinis 等人[45]提出混合上下文敏感（hybrid context sensitivity）技術(shù)，對于實例方法調(diào)用使用對象敏感，而對于靜態(tài)方法調(diào)用使用調(diào)用點敏感，從而結(jié)合了這2 種上下文敏感技術(shù)獲得了更好的精度.

3）類型敏感.作為面向?qū)ο蟪绦颍S多Java 程序會創(chuàng)建大量對象，因此使用對象敏感技術(shù)分析這類程序且上下文層數(shù)大于1 時，容易產(chǎn)生過多上下文，導(dǎo)致指針分析開銷過大.對此，Smaragdakis 等人[44]在對象敏感的基礎(chǔ)上提出類型敏感（type sensitivity）技術(shù)以提升指針分析效率與可擴展性，對應(yīng)的Select（）函數(shù)定義為：

其中函數(shù)InType（oi）返回對象oi的創(chuàng)建點所在的類型.以圖2 的代碼片段為例，方法foo（）有2 個接收者對象o3與o5，因此使用對象敏感分析時會產(chǎn)生2 個上下文[o3]與[o5]；而使用類型敏感分析時，它的上下文是InType（o3）=InType（o5）=[X]，因此只有一個上下文.不難看出，類型敏感技術(shù)生成上下文時合并了同一個類內(nèi)創(chuàng)建出的對象，因此其本質(zhì)上是對象敏感的一種粗粒度抽象，生成的上下文數(shù)量通常也小于對象敏感，從而具有更快的速度.相應(yīng)的，類型敏感的精度也差于對象敏感.Smaragdakis 等人[1,44]認為使用一個對象創(chuàng)建點所在的類作為上下文，也能較好地保留使用該對象本身作為上下文時攜帶的信息，因此不會導(dǎo)致太多精度丟失.實驗結(jié)果表明，類型敏感的精度略差于對象敏感，而對于一些對象敏感難以分析的程序，類型敏感具有顯著更好的效率和可擴展性[20,44].

Fig.2 An example for illustrating type sensitivity圖2 解釋類型敏感的例子

2.3 選擇性上下文敏感

給定一個程序，傳統(tǒng)上下文敏感技術(shù)將對該程序的所有方法應(yīng)用上下文，這種方式一般在上下文層數(shù)大于1 的情況下（例如2 層的調(diào)用點敏感或?qū)ο竺舾屑夹g(shù)），難以在合理的時間（例如幾個小時）內(nèi)完成對較大規(guī)?；驈?fù)雜程序的分析，我們也稱這種分析不具備良好的可擴展性（scalability）.為了使得指針分析能夠?qū)δ切┹^大規(guī)?；驈?fù)雜的程序取得良好精度的同時具備更好的可擴展性（即有效的精度與效率之間的平衡），選擇性上下文敏感技術(shù)（selective context sensitivity）被提出，并成為近年來針對Java 指針分析的研究熱點.可以從2 個角度來理解“選擇性”，一個是對程序的每一個方法選擇出對其有效的上下文元素來構(gòu)建其上下文；另一個是最主流且成效最明顯的，它只針對程序中的一部分被選擇出來的方法應(yīng)用上下文，其它方法不用上下文（或者對不同方法應(yīng)用不同種類的上下文）.本節(jié)按照這2 種類別分別闡述不同的選擇性上下文敏感技術(shù).

1）選擇上下文元素.傳統(tǒng)的上下文敏感使用的都是連續(xù)的上下文元素，例如，如果是調(diào)用點敏感技術(shù)，l3會調(diào)用l2，l2會調(diào)用l1，那么[l3,l2,l1]就會作為3層上下文元素來被使用.然而，Tan 等人[46]發(fā)現(xiàn)連續(xù)上下文中的很多上下文元素在很多情況下并不能提升精度，而這些上下文元素由于占用了上下文資源，比如，如果只能用2 層上下文，那么該例中的l3如果是能夠幫助提升精度的上下文元素而l2不是，但是由于傳統(tǒng)方法的上下文元素是連續(xù)的，因此也只能舍棄l3.為了解決該問題，Tan 等人[46]提出了對象分配圖（object allocation graph），并將識別有效上下文元素的問題轉(zhuǎn)換為在對象分配圖上識別有效路徑的問題.如果使用同樣的上下文層數(shù)，該方法可以被證明總能取得相較于傳統(tǒng)方法更好的分析精度.

Jeon 等人[47]提出的上下文隧道的概念（context tunneling）就是使用機器學(xué)習(xí)的方法來改進文獻[46]工作，即選出對精度提升有效的上下文元素，使得上下文敏感下的指針分析不再無條件地隨著每次方法調(diào)用而更新上下文元素，從而避免了在上下文層數(shù)有限的情況下，重要的上下文元素會被不重要的上下文元素?zé)o條件覆蓋.與文獻[48]類似，文獻[47]工作中的啟發(fā)式規(guī)則是使用一系列程序特征來表述的通過機器學(xué)習(xí)算法搜索習(xí)得的規(guī)則.盡管基于機器學(xué)習(xí)的方法可解釋性差、預(yù)分析時間長且存在過擬合的情況，但實驗結(jié)果表明，應(yīng)用該技術(shù)指導(dǎo)的1 層上下文敏感指針分析在精度和可擴展性上都優(yōu)于同類型的2 層上下文敏感指針分析.

在后續(xù)工作中，Jeon 等人[49]提出了一種Obj2CFA技術(shù)，它將應(yīng)用上下文隧道技術(shù)的對象敏感指針分析轉(zhuǎn)變?yōu)橐环N精度更高的、應(yīng)用上下文隧道的調(diào)用點敏感指針分析.這一工作表明，對層數(shù)為k的上下文敏感指針分析，對象敏感的優(yōu)越性僅存在于傳統(tǒng)的強制使用最新k個上下文元素的情況下；而在應(yīng)用上下文隧道技術(shù)后，分析可以自由保留任意k個上下文元素序列作為上下文，此時通過Obj2CFA 技術(shù)幾乎可以用調(diào)用點敏感來完全模擬對象敏感，反之則不行.實驗表明，通過該技術(shù)從對象敏感的指針分析轉(zhuǎn)換得到的調(diào)用點敏感指針分析在精度和可擴展性方面更佳.

2）選擇程序方法.Smaragdakis 等人[50]為了能夠讓指針分析有更好的可擴展性，提出了自省式分析（introspective analysis），該方法人工選取6 種不同的程序指標（metrics）（例如，程序方法參數(shù)的指向集合的大?。?；通過運行上下文非敏感指針分析作為預(yù)分析將這些指標值算出；根據(jù)這些值和閾值的比較作為選擇哪些方法需要上下文敏感的判斷條件，其余方法用上下文非敏感來分析，這樣會節(jié)省計算和維護上下文信息的開銷.實驗數(shù)據(jù)顯示，該方法確實能夠使得一些之前難以分析的程序在合理時間內(nèi)分析出結(jié)果，且取得了良好的分析精度.

Jeong 等人[48]提出了一種依賴于機器學(xué)習(xí)得到的啟發(fā)式規(guī)則，并用該規(guī)則決定進行指針分析時程序中的各個方法應(yīng)當使用多少層上下文（包括使用0 層，即不應(yīng)用上下文）.在該工作中，1 個方法用25個原子特征來描述（例如方法中是否含有某類語句），并通過使用機器學(xué)習(xí)，執(zhí)行一種貪心算法來得到所需的啟發(fā)式規(guī)則，這一啟發(fā)式規(guī)則被表示為至多25個原子特征的析取式.該技術(shù)能夠使程序中僅有部分方法在上下文中被分析；且被啟發(fā)式規(guī)則認為對精度影響重要的方法將在更深層數(shù)的上下文中分析.這種基于機器學(xué)習(xí)的方法最后選取指標的可解釋性較差，比如“當某個方法沒有X和Y關(guān)鍵字和語句時，需要對其應(yīng)用上下文”，這很難讓人理解該選擇背后的邏輯.此外，機器學(xué)習(xí)方法在一定程度上有過擬合的嫌疑，因為其有效性可能部分來源于在學(xué)習(xí)階段分析了樣本程序依賴的Java 標準庫，而這在一定程度上會影響分析其它程序的結(jié)果（因為很多程序都大量依賴JDK 標準庫）.盡管如此，實驗數(shù)據(jù)表明，依賴于機器學(xué)習(xí)挑選出的程序方法，確實在很大程度上能夠提高指針分析的效率，同時取得良好的精度.

無論是上述的自省式分析還是機器學(xué)習(xí)方法，在可解釋性方面都不夠好，主要原因是這些方法實際上并沒有從本質(zhì)上出發(fā)解決選擇性上下文敏感的核心問題，即到底為什么有些程序方法可以得益于上下文敏感（Li 等人[51]將這些方法稱為精度關(guān)鍵方法（precision-critical methods），而有些方法即使應(yīng)用上下文敏感技術(shù)來分析也不會提高精度.

Li 等人[51]首次提出了一套系統(tǒng)的理論解釋模型用以回答此問題.該模型由3 種基本流（直通流、封裝流和拆裝流）以及這些流的組合構(gòu)成.給定任何一個程序，指針分析在上下文非敏感情況下精度丟失的原因（或上下文敏感情況下的精度提升的原因）都可以通過這些基于流的模型來準確解釋.此外，在文獻[51]中，Li 等人提出了Zipper 方法，它將上述理論解釋模型通過精度流圖來表達，并將識別精度關(guān)鍵方法的問題轉(zhuǎn)換為在精度流圖上的圖可達性問題.

受理論解釋模型的啟發(fā)，Li 等人的后續(xù)工作[20]在該模型基礎(chǔ)上做了進一步拓展，在識別精度關(guān)鍵方法的基礎(chǔ)上還能識別速度關(guān)鍵方法（scalabilitythreaten methods），提出了目前針對難以分析的Java程序在效率與精度平衡方面表現(xiàn)最佳的方法之一Zipper-Express（Zippere）.Zippere具有簡單、容 易理解且具有很強的可解釋性等特點，能夠平均26 倍加速已有精準指針分析（2 層的對象敏感），且對于已有文獻中（包括國際基準Java 測試集DaCapo 的程序）無法在3 小時內(nèi)分析出結(jié)果的程序，Zippere可以在平均11 分鐘分析出精確的結(jié)果；不僅如此，對于一些復(fù)雜程序，Zippere指導(dǎo)的上下文敏感指針分析的速度甚至比上下文非敏感指針分析還快，這是由于Zippere排除了速度關(guān)鍵方法，從而顯著提升了效率；在此基礎(chǔ)上又通過將上下文敏感應(yīng)用于精度關(guān)鍵方法，相比于上下文非敏感分析，減少了大量假指向信息的傳播，從而達到了比上下文非敏感指針分析更高的效率.這一技術(shù)也打破了過去上下文敏感指針分析效率無法超越上下文非敏感指針分析的認識.

值得一提的是，如文獻[20,51]中所描述，識別精度關(guān)鍵方法的理論解釋模型（3 種流和流的組合）實際上是識別出方法中具體哪些程序變量是需要在分析中應(yīng)用上下文的（即靜態(tài)時這些流覆蓋的變量），這使得方法（Zipper 與Zippere）天然可以在變量或?qū)ο蟮牧６龋ㄏ噍^于其實驗中基于程序方法的粒度更細）上應(yīng)用上下文敏感技術(shù).

Lu 等人[52-53]的工作也是在程序變量/對象的粒度應(yīng)用上下文敏感，不同的是，該工作識別這些變量/對象的方法是基于上下文無關(guān)語言可達性（context free language reachability，CFL-reachability）技術(shù)完成，并將其實現(xiàn)出來.具體而言，該方法首先將程序中的值的流動形 式化為 指針賦值圖（pointer assignment graph，PAG），然后基于PAG 將對象敏感的指針分析表達為一個新的CFL 可達性公式，并通過在圖上解CFL 可達性問題來選取出同時滿足存在值的流入和流出這一約束條件的節(jié)點，最后對這些節(jié)點（包括了變量與對象）應(yīng)用對象敏感進行指針分析.實驗結(jié)果表明該方法能夠在加速對象敏感指針分析的同時保持精度不變.

He 等人[54]提出了一種稱為Turner 的方法來取得對象敏感指針分析效率和精度的新的平衡.該工作在文獻[52]的基礎(chǔ)上，進一步減少需要應(yīng)用上下文的變量或?qū)ο?該技術(shù)首先通過定義并找到程序中的2 類對象：頂部容 器（top container）和底部容器（bottom container），并對這2 類對象不應(yīng)用上下文，繼而選擇出對因這2 類對象不應(yīng)用上下文而不再滿足值的流動約束條件的變量或?qū)ο?，并對這些變量或?qū)ο笠膊粦?yīng)用上下文.實驗表明，Turner 能夠在2 個現(xiàn)有指針分析工具Eagle[52]和Zipper[51]中取得新的效率與精度的平衡：在精度和Eagle 幾乎一致的同時快于Eagle；在精度高于Zipper 的同時，在一部分基準程序上快于Zipper.然而，文獻[54]的工作并沒有與Zippere[20]進行比較，但是通過與Zipper 的對比以及實驗所展示的數(shù)據(jù)不難看出，Turner 在分析精度略高于Zippere的同時，其分析效率相比于Zippere應(yīng)該還有很大差距（有不少Turner 無法在給定時間內(nèi)完成分析的程序，Zippere可以完成對這些程序的分析）.

針對如何利用選擇性上下文敏感指針分析確保分析的可擴展性的同時盡可能地利用內(nèi)存資源最大程度地提升分析精度，Li 等人[55]提出了Scaler 方法來解決這一問題.該方法將上下文敏感指針分析在不同上下文情況下的可能開銷與抽象出的內(nèi)存承載能力關(guān)聯(lián)起來，并基于文獻[46]中提出的對象分配圖提出了預(yù)估上下文敏感指針分析開銷的方法，Scaler方法可以為不同程序自動分配不同的上下文敏感元素和長度以充分利用內(nèi)存可承載的能力并最大化分析精度.實驗結(jié)果表明，Scaler 具備非常好的分析可擴展性以及良好的分析精度，且其分析精度與效率的平衡可根據(jù)實際情況由用戶方便地支配調(diào)節(jié).

上文提到的工作[20,46,51–52,56]都是先基于某種圖的結(jié)構(gòu)來進行預(yù)分析處理，然后根據(jù)各自的預(yù)分析結(jié)果指導(dǎo)后續(xù)的選擇性上下文敏感指針分析.Jeon 等人[57]將這些方法歸類為一種基于圖的啟發(fā)式方法（graph-based heuristics），并用機器學(xué)習(xí)的方法去挖掘圖中對于選擇性上下文敏感指針分析有用的信息.Jeon 等人[57]首先定義了一種特征語言來描述基于圖的結(jié)構(gòu)，這一語言用節(jié)點自身和前驅(qū)后繼的入度或出度信息來描述一個節(jié)點的特征；然后設(shè)計了一個機器學(xué)習(xí)算法來學(xué)習(xí)用該特征語言表述的啟發(fā)式規(guī)則.具體而言，該技術(shù)會基于程序的對象創(chuàng)建圖（object allocation graph，OAG）[46]和字段 指向圖（field points-to graph，F(xiàn)PG）[56]來分別學(xué)習(xí)2 種啟發(fā)式規(guī)則，并將這2 種啟發(fā)式規(guī)則分別用于指導(dǎo)指針分析的2個方面：決定一個方法應(yīng)該用何種上下文敏感（包括不使用上下文）以及決定一個堆對象應(yīng)當用創(chuàng)建點抽象還是基于類型的抽象.實驗結(jié)果表明使用該技術(shù)指導(dǎo)的指針分析優(yōu)于部分現(xiàn)有的采用人工設(shè)計的啟發(fā)式規(guī)則的技術(shù).

已有的選擇性上下文敏感指針分析工作在效率與精度平衡方面一般都側(cè)重于使得分析盡可能快的同時還能保持良好的精度，Tan 等人[34]的工作側(cè)重平衡的另一端，即如何取得高精度的指針分析.它提出了Baton，一個獲取高精度指針分析的元框架.針對任何程序P，給定任何一組選擇性上下文敏感技術(shù)作為輸入，只要這些方法能夠在合理時間內(nèi)分析完P(guān)，Baton 就可以被證明總能保證在完成分析的情況下輸出比任何方法都更精確的選擇性上下文敏感指針分析.Baton 由2 部分構(gòu)成：“團結(jié)”（Unity）組件與“接力”（Relay）組件，Unity 組件最大限度利用已有輸入方法提高分析精度，當Unity 無法在有限時間內(nèi)完成分析后，Relay 組件會通過“精度累積傳遞”的方式繼續(xù)提高分析精度.實現(xiàn)結(jié)果表明，在所有精度指標上，對于所有的待評估程序（包括已有文獻及基準測試集中公認的難以分析的程序），相比于已有工作，Baton 總能取得最好的精度且很多情況下精度的提升是非常顯著的.

3 堆對象抽象

Java 指針分析計算程序中的變量在動態(tài)運行時所能指向?qū)ο蟮募?，作為典型的面向?qū)ο笳Z言，Java 程序通常在運行時會創(chuàng)建大量對象，且由于循環(huán)和遞歸的存在，理論上一個Java 程序在動態(tài)運行時可創(chuàng)建無窮無盡的對象.因此指針分析需要對程序中的對象采取抽象的表示，以保證分析中只需處理有限數(shù)量的對象，這類技術(shù)被稱為堆對象抽象，或簡稱堆抽象（heap abstraction）[58].使用不同的堆抽象 技術(shù)可對指針分析的效率與精度帶來顯著的影響[18,56,58-59].

目前，Java 指針分析使用最廣泛的堆抽象技術(shù)是創(chuàng)建點抽象（allocation-site abstraction），它用程序中的每個創(chuàng)建點i（即對象創(chuàng)建語句，如i:x=newT（））表示動態(tài)運行時所有由i創(chuàng)建出來的對象.對應(yīng)Heap（）函數(shù)（見表3 與表5）的定義為Heap（i）=i.創(chuàng)建點抽象具有良好的精度，幾乎所有主流Java 指針分析框架都支持這種堆抽象[38-39,60].

雖然創(chuàng)建點抽象精度良好，但一些復(fù)雜的Java程序包含大量的創(chuàng)建點，使用創(chuàng)建點抽象會在指針分析過程中產(chǎn)生大量對象，造成很大的開銷.主流的指針分析框架[38-39,60]都會提供對一些特定對象按類型合并的功能，如對于StringBuilder 或StringBuffer 類型的對象、字符串常量等對象，將所有同類型的對象合并抽象成一個對象.這些對象在程序中通常有許多創(chuàng)建點，因此合并這些創(chuàng)建點對應(yīng)的對象之后可以對指針分析效率帶來一定提升.

然而，合并特定對象并不能通用地解決創(chuàng)建點抽象導(dǎo)致對象數(shù)量過多的問題.對此，Tan 等人[56]提出了一種新的系統(tǒng)性堆抽象技術(shù)Mahjong.Mahjong的核心思想是判斷任意2 個堆對象的所有嵌套字段指向?qū)ο蟮念愋褪欠裣嗤?，這需要枚舉字段指向圖（field points-to graph）所有可能的字段訪問路徑，這是具有指數(shù)級復(fù)雜度的操作.為了解決該問題，Mahjong 將程序的字段指向圖映射成時序自動機（sequential automata），一種六元組自動機，那么判斷2 個堆對象是否等價的問題就自然地轉(zhuǎn)換成判斷等價自動機的問題，該問題可以通過對判別一般自動機等價性的Hopcroft-Karp 算法[61]稍加修改而解決，最終能夠得到近似線性復(fù)雜度的判別算法.對于關(guān)注指針指向?qū)ο箢愋偷膽?yīng)用，Mahjong 甚至可以成百倍地加速已有精準指針分析（3 層的對象敏感技術(shù)），同時維持了傳統(tǒng)指針分析99.9%的精度.

在第2 節(jié)中可以看到，堆抽象技術(shù)可以與上下文敏感結(jié)合，將抽象對象進一步細分，形成上下文敏感堆抽象（context-sensitive heap abstraction）.例如創(chuàng)建點抽象對于創(chuàng)建點i產(chǎn)生一個對象oi，而假設(shè)i所在的方法有3 個上下文，則對應(yīng)的上下文敏感堆抽象可以將oi細分成3 個抽象對象（如c:oi，c′:oi，c′′:oi），分別表示不同上下文中創(chuàng)建出的對象.而這種更精細化的堆抽象也能帶來更好的分析精度.

除了創(chuàng)建點抽象（以及由其衍生出的相關(guān)技術(shù)）之外，還有一類差異較大的堆抽象技術(shù)，即基于訪問路徑（access path）的堆抽象，其中每個訪問路徑由1個變量跟隨0 個或多個字段組成，即形如x，x.f，x.f.g的指針表達式.基于訪問路徑的指針分析通常使用訪問路徑之間的別名關(guān)系表示堆的信息[1,58]，因此會在運行過程中同步計算并維護別名關(guān)系（例如分析語句x=y時，生成與變量x，y相關(guān)訪問路徑的別名，如{x,y}，{x.f,y.f}等）.

復(fù)雜的Java 程序會包含數(shù)量巨大的訪問路徑.此外，程序中的循環(huán)引用理論上可形成數(shù)量無限的訪問路徑，如語句x.f=x可使得x，x.f，x.f.f，x.f.f.f…都是有效的訪問路徑，導(dǎo)致指針分析無法窮舉.因此，實際使用訪問路徑時，通常也會采用類似上下文敏感的k-limiting 技術(shù)，即對訪問路徑中包含的字段數(shù)量設(shè)置一個上限k，長度超過k的訪問路徑則被合并到相同前綴的訪問路徑[58]，例如k=1 時，x.f*表示所有以x.f開頭的訪問路徑，包括x.f，x.f.g，x.f.h等.由于訪問路徑可以在一些情況下方便地做強更新（strong update），因此目前主要是一些流敏感分析[8,62]使用該技術(shù).

4 復(fù)雜語言特性處理

作為一門廣泛使用的工業(yè)級編程語言，Java 具有豐富的語言特性，隨著不斷地演化，Java 的語言特性也越來越多.然而其中的一些復(fù)雜語言特性給指針分析帶來了很大的挑戰(zhàn).如果指針分析不能妥善處理這些復(fù)雜語言特性，其結(jié)果的可靠性將受到嚴重的影響[63].本節(jié)介紹這些復(fù)雜語言特性如何影響指針分析以及處理這些特性的代表性工作.

4.1 反 射

Java 的反射（reflection）是一套功能強大的機制，允許Java 程序由動態(tài)信息（主要是字符串）指定其行為（如創(chuàng)建對象、讀寫字段、調(diào)用方法等），顯著提升了Java 這一靜態(tài)類型語言的靈活性.但反射的動態(tài)性也給靜態(tài)分析造成了很大困難，是公認最難以靜態(tài)分析的語言特性之一[64-66]，圖3 用一個反射的典型用例進行說明.其中行2 的Class.forName（）方法根據(jù)參數(shù)字符串clsName返回一個類（比如T）對應(yīng)的Class 對象，T 的類名就等于clsName.程序得到T 類的Class 對象之后，可以通過newInstance（）方法創(chuàng)建T 類的對象（行3）；或通過getMethod（）方法獲取T 類某個方法對應(yīng)的Method 對象（行4），而獲取的方法取決于getMethod（）的參數(shù)，即方法名（字符串mtdName）與方法的參數(shù)列表X.class.得到方法對象mtd后，程序可以通過invoke（）方法對相應(yīng)的目標方法發(fā)起調(diào)用（行6）.圖3 例子中決定反射行為的關(guān)鍵在于字符串clsName與mtdName的具體內(nèi)容.然而，許多情況下，Java 程序的字符串來自于外部輸入（如命令行、配置文件、網(wǎng)絡(luò)等），或經(jīng)過一系列字符串操作（如截取、拼接等），因此靜態(tài)無法得到準確的字符串分析結(jié)果，使得反射的副作用難以分析.

Livshits 等人[67]提出借助指針分析解析反射關(guān)鍵API（如Class.forName（）、Class.getMethod（））的 字符串參數(shù)進而分析出反射調(diào)用的副作用.具體而言，該反射分析與指針分析同時運行并互相依賴，在此過程中，反射關(guān)鍵API 字符串參數(shù)（如圖3 中的clsName與mtdName）的指針集發(fā)生變化時，指針分析會觸發(fā)反射分析，mtdName根據(jù)指針集中的字符串常量來分析反射調(diào)用的行為，并將其相應(yīng)的副作用反饋給指針分析.然而該分析只能處理反射參數(shù)指向字符串常量的情況，對于其它字符串非常量的情況均無法分析（唯一例外是Class.newInstance（）的返回值被立即進行向下類型轉(zhuǎn)換（downcasting）這一特定情形，該技術(shù)可以利用類型轉(zhuǎn)換的信息對Class.newInstance（）的副作用進行推導(dǎo)）.

Fig.3 A typical usage of Java reflection圖3 一個典型的Java 反射用例

Li 等人[68]研究了真實Java 程序中的反射使用情況，發(fā)現(xiàn)在絕大部分情況下，盡管反射調(diào)用的參數(shù)并非字符串常量（靜態(tài)無法分析），但在反射的調(diào)用點有許多可利用的信息可以用于分析反射（比如反射調(diào)用參數(shù)的類型、返回值的向下類型轉(zhuǎn)換等），并系統(tǒng)性地將這些信息總結(jié)為自推導(dǎo)屬性（self-inferencing property）.基于這一發(fā)現(xiàn)，Li 等人[68]提出一套新的靜態(tài)反射技術(shù)Elf，利用自推導(dǎo)屬性并結(jié)合Java 類型系統(tǒng)，在反射字符串參數(shù)并非常量的情況下也能推導(dǎo)反射調(diào)用的行為.實驗表明，Elf 能夠有效分析出非常多的、已有工作無法靜態(tài)解析出的真實反射調(diào)用行為，顯著提升了反射分析的可靠性（soundness），并同時取得良好的分析精度.

在Elf 的基礎(chǔ)上，Li 等人[69-70]提出集體推導(dǎo)（collective inference）與懶惰堆建模（lazy heap modeling）的技術(shù)，并形成新的反射分析Solar.集體推導(dǎo)在Elf的基礎(chǔ)上進一步增強了推導(dǎo)能力.懶惰堆建模用于分析由反射調(diào)用Class.newInstance（）或Constructor.newInstance（）創(chuàng)建但具體類型在創(chuàng)建點未知的堆對象.對于這類對象，Solar 將其傳播到程序中使用它們的位置，如向下類型轉(zhuǎn)換，或Method.invoke（）、Field.get（）、Field.set（）的反射調(diào)用點等，并更充分地利用程序中這些位置的類型信息以分析反射創(chuàng)建對象的具體類型.基于更強的反射分析能力，Solar 能夠識別出程序中未能被完整解析的反射調(diào)用點，首次在理論上實現(xiàn)了對于反射分析可靠性邊界的靜態(tài)推導(dǎo)；此外，Solar 也能識別出分析不準確的反射調(diào)用點，因此可以幫助用戶添加輕量級注解就可以滿足他們的在可靠性、分析效率等方面的需求.

4.2 本地代碼

Java 是一門運行在虛擬機（Java Virtual Machine）之上的語言，虛擬機封裝了不同平臺的功能并支持一套統(tǒng)一的Java 語言規(guī)范，這使得Java 程序具有良好的平臺無關(guān)性因而可以跨平臺執(zhí)行.然而，在一些情況下，例如Java 程序需要直接與底層平臺交互或?qū)崿F(xiàn)性能攸關(guān)的功能時，Java 程序也需要調(diào)用能直接運行在宿主平臺上的代碼，即本地代碼（通常由C/C++實現(xiàn)）.Java 提供了native 關(guān)鍵字，用于在Java程序中聲明本地方法（native method），例如java.lang.System 中的arraycopy（）方法：

它的具體實現(xiàn)并非Java 代碼，而是由C/C++代碼按照Java 本地接口（Java Native Interface，JNI）規(guī)范[71]完成的.由于本地代碼并非由Java 實現(xiàn)，因此上文介紹的Java 指針分析技術(shù)無法用于本地代碼的分析.但本地代碼可以對Java 程序進行諸多操作，如修改對象的字段、回調(diào)Java 方法等，因此如果不能妥善分析本地代碼，將會對指針分析結(jié)果的可靠性造成顯著影響.

目前主流Java 指針分析框架[38-39,60]處理本地代碼的方式是手動地在框架內(nèi)添加一些對指針分析影響較大的本地方法（如System.arraycopy（））的分析邏輯，當指針分析遇到這些本地代碼的調(diào)用時，會觸發(fā)相應(yīng)分析邏輯，模擬它們對程序中指針的副作用.

為了自動化地分析本地代碼回調(diào)Java 函數(shù)這一類行為，F(xiàn)ourtounis 等人[72]提出掃描本地代碼中的字符串常量并推測其對應(yīng)的Java 方法.具體來說，JNI[71]提供了一系列用于回調(diào)Java 方法的API，而Fourtounis 等人[72]注意到這些API 的參數(shù)往往是字符串常量，并且與具體回調(diào)的Java 方法的簽名緊密相關(guān)，進而在該工作中提出掃描本地代碼中的字符串常量，記錄JNI 調(diào)用的參數(shù)與字符串常量的對應(yīng)關(guān)系，結(jié)合傳統(tǒng)Java 分析工具對方法簽名的分析，推斷該JNI 調(diào)用回調(diào)的是哪個Java 方法.實驗結(jié)果表明，該工作可以快速有效地推測出XCorpus 基準程序庫和Chrome 等真實應(yīng)用中本地代碼的回調(diào)方法.

4.3 異 常

異常（exception）是Java 程序中重要而不可忽視的控制流[73].準確的異常分析需要得知程序的throw語句以及方法調(diào)用可能拋出異常的具體類型，這需要依賴于指針分析的結(jié)果，反之，異常分析的結(jié)果也能影響指針分析，下面用圖4 中的代碼片段進行說明.

Fig.4 An example for illustrating exception圖4 解釋異常的例子

圖4 中行3 與行5 都有可能拋出異常，一方面，對于行3 的調(diào)用語句，需要分析它的具體目標方法才可知它可能拋出的異常，對于行5 的throw 語句，則需要分析變量e指向的具體異常對象，而這些都需要依賴于指針分析.另一方面，指針分析若要準確分析行8 的調(diào)用，也需要異常分析對于行7 catch 語句的分析結(jié)果（即分析出變量ioe會捕獲的具體異常對象，該異?？赡苁怯烧{(diào)用o.m（）拋出，也可能由throw語句拋出）.由此可見，實際上指針分析與異常分析互相依賴于對方的結(jié)果.

針對指針分析與異常分析相互耦合的特點，Bravenboer 等人[74]提出將指針分析與異常分析結(jié)合進行的技術(shù).具體而言，異常分析處理throwe語句時使用指針分析對于變量e的結(jié)果；而異常分析處理catch 語句時，會推斷哪些異常對象被對應(yīng)的catch 語句捕獲，并將捕獲的異常對象注入到對應(yīng)catch 語句的異常形參變量的指針集中，反饋給指針分析.此外，指針分析在構(gòu)建調(diào)用圖時，也會觸發(fā)異常分析，使其能夠沿著調(diào)用邊向調(diào)用點傳播目標方法內(nèi)沒有被捕獲的異常.通過文獻[74]的方式，實現(xiàn)了指針分析與異常分析的協(xié)同式迭代計算.實驗顯示，與以往不精確的異常分析[19]相比，該技術(shù)對于try-catch 異常對象流的分析精度有顯著提升.

在文獻[74]提出的異常分析中，異常對象會大量流入或者流出程序中的各個方法，因此若將異常當作常規(guī)對象進行處理會產(chǎn)生大量開銷，同時由于異常分析往往并不關(guān)注異常對象本身內(nèi)部字段的信息，因此在文獻[74]的基礎(chǔ)上，Kastrinis 等人[75]提出了將相同類型的異常對象合并，并且使用這個類型合并后的代表對象（每個類型只有1 個）表示對應(yīng)的異常對象.實驗中，該方式使異常分析幾乎在不損失精度的情況下能夠顯著提升分析性能.

4.4 invokedynamic 與Lambda 表達式

Java 7 引入了新的字節(jié)碼調(diào)用指令invokedynamic，它與已 有的調(diào)用指令invokestatic，invokespecial，invokevirtual，invokeinterface 最大的區(qū)別在于，已有調(diào)用指令都是依照固定的規(guī)則解析出目標方法，而invokedynamic 允許用戶編寫代碼指定目標方法的解析規(guī)則，在動態(tài)時依據(jù)用戶代碼來決定調(diào)用點與目標方法的鏈接，而這種動態(tài)性對靜態(tài)分析造成了很大困難.Java 引入invokedynamic 指令的主要原因是為了使Java 虛擬機（JVM）能更方便地支持動態(tài)類型語言，但invokedynamic 指令也有其他應(yīng)用，其中最為重要的便是Lambda 表達式.Java 8 引入Lambda 表達式顯著地提升了Java 編程的便利性，這也是現(xiàn)代Java 編程中被頻繁使用的特性.如果指針分析不能妥善處理Lambda 表達式，將會缺失程序中的許多行為.然而Lambda 表達式是基于invokedynamic 實現(xiàn)的，并結(jié)合了動態(tài)代碼生成，因此對于Lambda 表達式的分析也是一個挑戰(zhàn).

Soot[39]是目前最流行的Java 分析框架之一，它選擇在前端生成中間代碼的過程中將程序內(nèi)與Lambda 表達式相關(guān)的invokedynamic 指令轉(zhuǎn)換為非invokedynamic 的調(diào)用語句，從而避免分析invokedynamic指令.然而這種方式損失了一部分原程序中的語義，并且Soot 的指針分析也不支持對于invokedynamic 指令的分析.

目前在指針分析中對 Lambda 表達式與invokedynamic 處理得最完善的是Fourtounis 等人提出的對invokedynamic 指令進行深度靜態(tài)建模的技術(shù)[76].該技術(shù)在模型中按照invokedynamic 的語義，識別并分析用戶編寫的目標方法解析邏輯.然而，由于invokedynamic 機制具有高度的動態(tài)性與開放性，該技術(shù)并不能處理所有invokedynamic 的使用場景.而且，與通用的invokedynamic 使用不同，Java Lambda表達式的實現(xiàn)邏輯雖然復(fù)雜，但其總體行為模式是固定且可預(yù)期的，因此該工作對Lambda 表達式進行額外的針對性建模，它包含了Lambda 表達式的識別、目標方法的解析、參數(shù)與返回值的傳遞、外部變量捕捉等一系列行為的分析邏輯，能夠準確地在指針分析中處理Lambda 表達式.

5 非全程序指針分析

現(xiàn)代Java 程序規(guī)模復(fù)雜，要進行一次全程序指針分析往往需要不小的開銷，使得全程序分析在一些時間、空間資源有限的應(yīng)用場景下不能很好地滿足用戶需求.因此研究人員也在探索如何在不運行全程序指針分析的前提下獲取到相應(yīng)指針的分析結(jié)果，而目前相關(guān)的技術(shù)主要有2 類：需求驅(qū)動分析（demand-driven analysis）與增量分析（incremental analysis）.

5.1 需求驅(qū)動分析

需求驅(qū)動分析[77]的使用場景是指指針分析的一些應(yīng)用（如編譯優(yōu)化、故障檢測、程序理解等）只需要了解程序中特定指針的指向關(guān)系，此時應(yīng)用就會向指針分析發(fā)起相應(yīng)的查詢（query），例如“A 類第10 行處變量x指向哪些對象？”，需求驅(qū)動指針分析只返回應(yīng)用所需指針的指向關(guān)系即可，而無需對全程序進行分析，從而節(jié)省分析的開銷.

Sridharan 等人[78]提出了一個基于CFL 可達性的需求驅(qū)動指針分析算法.該工作將程序轉(zhuǎn)換為一種圖表示，其中節(jié)點表示變量和對象，邊表示指針分析相關(guān)的程序語句（如復(fù)制語句x=y、字段存儲語句y=x.f）.在圖表示的基礎(chǔ)上，該工作將字段敏感的指針分析建模為 CFL 可達性問題，指針x指向?qū)ο髈的指向關(guān)系被視為程序中存在一條從x到o的數(shù)據(jù)流路徑，且該路徑上的字段寫入邊（field write），對應(yīng)左括號與字段讀取邊（field read），對應(yīng)右括號連接成的括號序列可構(gòu)成一個平衡的括號串.該工作提出的算法在處理“變量x指向哪些對象”的查詢時，從x對應(yīng)的節(jié)點開始，在圖上搜索CFL 可達的對象節(jié)點.為了提高算法的可擴展性，該工作將算法分為估算和精化2 個階段.估算階段會在CFL 可達性搜索時跳過一些可能不可行的路徑；若有足夠的時間預(yù)算，則在隨后精化階段中，算法會通過檢查在估算階段被跳過的部分來提升分析的精度.在后續(xù)工作中，Sridharan 等人[79]進一步將該方法結(jié)合上下文敏感技術(shù)，提升了分析的精度.

Yan 等人[80]提出了過程內(nèi)可達性摘要技術(shù)，減少了分析時的重復(fù)計算，提升了傳統(tǒng)的基于CFL 可達性需求驅(qū)動別名分析的效率.具體而言，該工作使用 符號指向圖（symbolic points-to graph，SPG）[81]作為其程序表示，一個方法的SPG 包含其內(nèi)部的指向關(guān)系，并使用占位的符號節(jié)點來代表方法外創(chuàng)建的對象.基于此程序表示，該工作設(shè)計了一個算法能夠在線地分析出過程內(nèi)可達性摘要，并將其應(yīng)用到別名分析中，減少了對于頻繁分析方法的重復(fù)計算.實驗結(jié)果表明，該工作相比于基于精化的需求驅(qū)動指針分析[79]在相同的運行時間限制下?lián)碛懈玫木?，并且使用過程內(nèi)摘要技術(shù)能提升一定的運行效率.

Shang 等人[82]提出了一個使用CFL 可達性摘要技術(shù)的需求驅(qū)動指針分析，它無需大開銷地全程序預(yù)處理分析.具體而言，該工作提出在過程內(nèi)進行字段敏感的部分指針分析，并將其作為過程內(nèi)分析的指向關(guān)系摘要；之后該摘要可以被重復(fù)利用到相同甚至不同上下文中，減少過程內(nèi)分析的重復(fù)計算.實驗結(jié)果表明，該工作相比于基于精化的需求驅(qū)動指針分析[79]，在類型轉(zhuǎn)換檢查、空指針檢查和工廠方法分析這3 種分析應(yīng)用中均能取得一定的效率提升.

Sp?th 等人[62]首次提出了一個能夠同時提供指向關(guān)系和別名關(guān)系信息的需求驅(qū)動、流敏感、上下文敏感指針分析.該工作在處理一次查詢時，首先會在程序控制流圖上從待查詢的變量開始逆向搜索，找出其可能指向的對象創(chuàng)建點；然后，從這些對象創(chuàng)建點開始正向搜索，找出其它可能指向同一對象的變量.在逆向和正向搜索2 個階段，該工作使用了IFDS 框架[83]實現(xiàn)流敏感和上下文敏感，并利用過程摘要提高算法的效率.實驗結(jié)果表明，該工作的性能和精度均優(yōu)于已有的技術(shù)[79-80].

5.2 增量分析

實際軟件開發(fā)過程中，軟件是由開發(fā)人員通過一次次更新與修改累積而成，而每次更新的部分通常只占程序中很小的一部分.針對軟件開發(fā)的這一特點，增量分析應(yīng)運而生.具體而言，增量分析通常需要先針對程序指定版本運行一次全程序分析，在此基礎(chǔ)上，當開發(fā)人員更新程序時，增量分析只針對程序變化的部分展開分析，分析變化部分自身指針集的變化以及它們對程序其他部分的影響，而對于未受影響的部分，可以直接復(fù)用之前指針分析的運行結(jié)果，從而節(jié)省了分析的開銷.

Lu 等人[84]提出了一個基于CFL 可達性的路徑依賴追蹤的增量指針分析算法.CFL 可達性分析將指向關(guān)系表示為一種圖可達性關(guān)系，該工作使用了一個輔助數(shù)據(jù)結(jié)構(gòu)，在運行圖可達性搜索的同時，記錄路徑上經(jīng)過的變量.在程序發(fā)生變化時，只會重新計算那些受到影響的路徑，即包含被修改變量的路徑，并更新CFL 可達性結(jié)果和路徑信息.該技術(shù)因為記錄所有路徑追蹤信息的內(nèi)存，開銷很大，因此文獻[84]提出了一種優(yōu)化追蹤策略，減少存儲程序中不經(jīng)常修改部分的追蹤信息的開銷.Liu 等人[85]提出了一個基于Andersen 指針分析算法的并行增量指針分析算法IPA.相比于之前的技術(shù)，該工作通過充分挖掘Andersen 指針分析算法的傳遞性質(zhì)，使用強連通分量優(yōu)化，減少了大量重復(fù)計算或者圖可達性分析，顯著提高了增量指針分析的性能.具體而言，Andersen 算法的傳遞性質(zhì)保證了對指針賦值圖（pointer assignment graph，PAG）進行強連通分量縮點優(yōu)化；并消除PAG 圖中的環(huán)之后，在刪除一條語句時，只需要檢查受影響節(jié)點的鄰居節(jié)點即可，而無需遍歷整個PAG.在傳遞性質(zhì)的基礎(chǔ)上，該工作繼續(xù)證明了增量指針分析算法的修改冪等性，即添加或刪除語句后，指向關(guān)系在PAG 上的傳播是一個冪等操作，從而設(shè)計了一個無同步（synchronization-free）的并行指針分析算法.實驗結(jié)果表明，該工作與之前基于圖可達性分析的技術(shù)[84]相比，有顯著的性能提升.在后續(xù)工作中，Liu 等人[86]進一步結(jié)合上下文敏感技術(shù)，提出了一種支持調(diào)用點敏感和對象敏感的增量指針分析算法.該工作解決了處理方法調(diào)用刪除時的重復(fù)計算，保證了在有上下文敏感的前提下處理添加、刪除語句的分析結(jié)果的可靠性.

6 總結(jié)

本文從指針分析的核心算法入手，分別在其基礎(chǔ)上就調(diào)用棧抽象（上下文敏感）與堆抽象技術(shù)展開介紹與討論.此外，想要有效地分析真實世界的Java程序，指針分析勢必要處理Java 的復(fù)雜語言特性，因此本文也介紹了主流的相關(guān)技術(shù).除了傳統(tǒng)的全程序指針分析，本文也介紹了另外2 種重要的指針分析，即，需求驅(qū)動分析與增量分析.

本文相比于已有的Java 指針分析綜述工作，補充了自2015 年之后的重要研究文獻，尤其是對近年來該方向的研究熱點——選擇性上下文敏感技術(shù)進行了系統(tǒng)性的梳理與討論.我們期待該文可以為國內(nèi)研究人員了解Java 指針分析研究工作提供便利的參考.

作者貢獻聲明：譚添、李樾負責(zé)撰寫論文；馬曉星、許暢和馬春燕負責(zé)修改論文.