目錄：

1. Motivation
2. 指針分析介紹
3. 影響指針分析的關(guān)鍵要素
4. 分析哪些語句

重點：

什么是指針分析？影響指針分析的關(guān)鍵因素是什么？指針分析要分析哪些指令？

1.Motivation

指針分析必要性：

6-1-PTA-motivation.png

2.指針分析

目標(biāo)：分析程序指針可以指向哪些內(nèi)存。對于Java等面向?qū)ο笳Z言，主要分析指針指向哪個對象。

說明：指針分析屬于may analysis，分析的結(jié)果是某指針?biāo)锌赡苤赶蚰男ο?，是個over-approximation集合。

示例：面向?qū)ο笳Z言中的指針指向問題。對于setB()函數(shù)，this指向new A()，因為是調(diào)用者是a.setB()；setB()中的b是x傳過來的，所以b指向new B()，A.b指向 new B()。

6-2-1-PTA示例.png

區(qū)別：

• 指針分析：分析指針?biāo)锌赡苤赶虻膶ο蟆?/li>
• 別名分析：分析兩個指針是否指向相同的對象，可通過指針分析來推導(dǎo)得到。

應(yīng)用：基本信息（別名分析/調(diào)用圖），編譯優(yōu)化（嵌入虛擬調(diào)用），漏洞（空指針），安全分析（信息流）。

3.影響指針分析的關(guān)鍵要素

指標(biāo)：精度（precision）& 效率（efficiency）。

影響因素：本課程，我們主要分析分配點的堆抽象技術(shù)、上下文敏感/不敏感、流不敏感、全程序分析。

（1）堆抽象（內(nèi)存建模）

問題：程序動態(tài)執(zhí)行時，堆對象個數(shù)理論上是無窮無盡的，但靜態(tài)分析無法處理這個問題。所以為保證指針分析可以終止，我們采用堆抽象技術(shù)，將無窮的具體對象抽象成有限的抽象對象。也即，將有共性的對象抽象成1個靜態(tài)對象，從而限制靜態(tài)分析對象的個數(shù)。

// 示例
for (...) {
    A a = new A();
}

技術(shù)概覽：

6-3-1-堆抽象技術(shù)概覽.png

我們只學(xué)習(xí)Allocation-Site技術(shù)，最常見也最常被使用。

Allocation-Site原理：將動態(tài)對象抽象成它們的創(chuàng)建點（Allocation-Site），來表示在該點創(chuàng)建的所有動態(tài)對象。Allocation-Site個數(shù)是有限的。

示例：循環(huán)創(chuàng)建了3個對象，我們用O₂來抽象表示這3個動態(tài)對象。

6-3-2-堆抽象示例.png

（2）上下文敏感 Context Sensitivity

問題：考慮是否區(qū)分不同call-site對同一函數(shù)的調(diào)用。

• Context-sensitive：根據(jù)某函數(shù)調(diào)用上下文的不同，多次分析同一函數(shù)。

• Context-insensitive：每個函數(shù)只分析一次。

  
  
  6-3-3-上下文敏感示例.png

（3）流敏感 Flow Sensitivity

問題：考慮語句順序（控制流）的影響 vs 把程序當(dāng)做無序語句的集合。

方法：流敏感會在每個程序點都保存一份指針指向關(guān)系映射，而流不敏感則對整個程序保存一份指向關(guān)系映射。

說明：目前流敏感對Java提升不大，不過在C中很有效，本課程分析的是Java，所以重點討論流不敏感技術(shù)。

指針分析示例：

6-3-4-流敏感示例.png

（4）分析范圍 Analysis Scope

問題：分析程序的哪一部分？

• Whole-program 全程序：分析全程序的指向關(guān)系。
• Demand-driven 需求驅(qū)動：只分析影響特定域的指針的指向關(guān)系。

4.分析哪些語句

問題：哪些語句會影響指針指向，那就只分析這些語句。

Java指針類型：

1. Lacal variable: x

2. Static field:C.f （有時稱為全局變量）——不分析

3. Instance field: x.f （對象的field）

4. Array element: array[i] ——不分析，因為靜態(tài)分析無法確定下標(biāo)，所以將array中所有成員映射到一個field中，等價于Instance field，所以不重復(fù)分析。如下圖所示：
   

   6-4-1-數(shù)組處理.png

影響指針指向的語句：

1. New: x = new T()
2. Assign：x = y
3. Store： x.f = y
4. Load： y = x.f
5. Call： r = x.k(a,...)
   • Static call： C.foo()
   • Special call： super.foo() / x.<init>() / this.privateFoo()
   • Virtual call：x.foo()

復(fù)雜的內(nèi)存訪問可以通過引入臨時變量，轉(zhuǎn)化為三地址代碼：

x.f.g.h = y;
// 轉(zhuǎn)化為
t1 = x.f;
t2 = t1.g;
t2.h = y;

參考

軟件分析筆記4：指針分析