Java 指針分析綜述

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

1（南京大學計算機科學與技術系 南京 210023）

2（計算機軟件新技術國家重點實驗室（南京大學）南京 210023）

3（西北工業大學軟件學院 西安 710129）

指針分析（pointer analysis），又稱指向分析（pointsto analysis）或別名分析（alias analysis），是計算程序中的指針（或變量、引用）在運行時所能指向的內存位置（或對象）的一種靜態程序分析技術.指針分析的結果通常可表示為指針與內存位置之間的指向關系（points-to relation）或每個指針的指針集（points-to set）.指針分析提供了程序中基礎的數據流信息，對于一系列技術如編譯優化[1-3]、故障檢測[4-6]、安全分析[7-11]、程序理解[12-13]、程序驗證[14-15]等具有重要作用.作為公認的最基礎的靜態分析技術之一[1,16]，指針分析這一研究領域已有超過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 程序的分析需求，因此需要利用在第2～4 節介紹的進階技術對程序行為進行更有效的抽象與模擬.

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

Java 作為典型的面向對象語言，運行時會在堆上創建大量對象，因此研究人員引入堆對象抽象技術，在指針分析中對動態運行時的對象進行合理的抽象以保證指針分析的有效性.第3 節介紹堆對象抽象的主要技術.

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

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

1 指針分析算法

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

1.1 Java 中的指針

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

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

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

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

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

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

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

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

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種方法調用：靜態調用（static invocation）、特殊調用（special invocation）和虛調用（virtual invocation）.其中虛調用的處理最為復雜，而靜態調用與特殊調用的處理邏輯均可視為虛調用處理邏輯的簡化.因此本文關注虛調用的處理.

1.3 算 法

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

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

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

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

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

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

Table 3 Rules for Pointer Analysis表3 指針分析規則

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

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

算法1.指針分析算法.

輸入：程序入口方法mentry；

輸出：指向關系pt，調用圖CG.

Solve（mentry）是整個算法的主函數，它的輸入mentry是程序的入口方法（對應Java 程序的main 方法）.Solve（）首先初始化5 個貫穿算法始終的數據結構：

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

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

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

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

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

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

對于對象創建語句，算法使用Heap（i）函數，將程序中的對象創建點（allocation site）i映射成對應的抽象對象（abstract object）oi，得到oi后，算法將其作為新發現的變量x的指向關系加入WL中.

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

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

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

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

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

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

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

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

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

2 上下文敏感

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：程序入口方法mentry；

輸出：指向關系pt，調用圖CG.

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

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

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

2.2 傳統上下文敏感

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

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

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

2）對象敏感.2002 年，Milanova 等人針對面向對象語言的特征，提出對象敏感（object sensitivity）技術[42-43].具體地說，對象敏感技術使用調用點的接收者對象作為上下文，相應的Select（）函數定義為：

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

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

3）類型敏感.作為面向對象程序，許多Java 程序會創建大量對象，因此使用對象敏感技術分析這類程序且上下文層數大于1 時，容易產生過多上下文，導致指針分析開銷過大.對此，Smaragdakis 等人[44]在對象敏感的基礎上提出類型敏感（type sensitivity）技術以提升指針分析效率與可擴展性，對應的Select（）函數定義為：

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

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

2.3 選擇性上下文敏感

給定一個程序，傳統上下文敏感技術將對該程序的所有方法應用上下文，這種方式一般在上下文層數大于1 的情況下（例如2 層的調用點敏感或對象敏感技術），難以在合理的時間（例如幾個小時）內完成對較大規模或復雜程序的分析，我們也稱這種分析不具備良好的可擴展性（scalability）.為了使得指針分析能夠對那些較大規模或復雜的程序取得良好精度的同時具備更好的可擴展性（即有效的精度與效率之間的平衡），選擇性上下文敏感技術（selective context sensitivity）被提出，并成為近年來針對Java 指針分析的研究熱點.可以從2 個角度來理解“選擇性”，一個是對程序的每一個方法選擇出對其有效的上下文元素來構建其上下文；另一個是最主流且成效最明顯的，它只針對程序中的一部分被選擇出來的方法應用上下文，其它方法不用上下文（或者對不同方法應用不同種類的上下文）.本節按照這2 種類別分別闡述不同的選擇性上下文敏感技術.

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

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

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

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

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

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

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

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

值得一提的是，如文獻[20,51]中所描述，識別精度關鍵方法的理論解釋模型（3 種流和流的組合）實際上是識別出方法中具體哪些程序變量是需要在分析中應用上下文的（即靜態時這些流覆蓋的變量），這使得方法（Zipper 與Zippere）天然可以在變量或對象的粒度（相較于其實驗中基于程序方法的粒度更細）上應用上下文敏感技術.

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

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

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

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

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

3 堆對象抽象

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

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

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

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

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

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

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

4 復雜語言特性處理

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

4.1 反 射

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

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

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

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

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

4.2 本地代碼

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

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

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

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

4.3 異 常

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

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

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

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

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

4.4 invokedynamic 與Lambda 表達式

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

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

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

5 非全程序指針分析

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

5.1 需求驅動分析

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

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

Yan 等人[80]提出了過程內可達性摘要技術，減少了分析時的重復計算，提升了傳統的基于CFL 可達性需求驅動別名分析的效率.具體而言，該工作使用 符號指向圖（symbolic points-to graph，SPG）[81]作為其程序表示，一個方法的SPG 包含其內部的指向關系，并使用占位的符號節點來代表方法外創建的對象.基于此程序表示，該工作設計了一個算法能夠在線地分析出過程內可達性摘要，并將其應用到別名分析中，減少了對于頻繁分析方法的重復計算.實驗結果表明，該工作相比于基于精化的需求驅動指針分析[79]在相同的運行時間限制下擁有更好的精度，并且使用過程內摘要技術能提升一定的運行效率.

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

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

5.2 增量分析

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

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

6 總結

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

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

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