taibeihacker
Moderator
静态程序分析(一)
1 前言
1.1 静态程序的定位
静态程序分析是编程语言中应用層面下的一個細分領域，它是一個非常重要的核心內容。在理論部分，考慮的是如何設計一個語言的語法和語義，如何設計語言的類型系統等等問題；有了語言的語法、語義和類型系統之後，我們需要支撐語言的運行。因此，在環境部分，需要考慮如何為運行中的程序提供運行時環境——如何設計編譯器，在運行時需要怎樣的支持（如內存的分配管理）等等；應用部分則關注如何保證語言所寫出程序的效率、安全性和可靠性，主要考慮如何對程序進行分析，驗證和合成（如何自動合成一個程序）。
一句話概括靜態分析：在保證正確性的前提下，在精度和速度上做平衡。
1.2 静态程序分析的应用
提高程序可靠性空指針引用與內存洩漏等
提高程序安全性
隱私信息洩漏：多存在於移動應用安全中
注入攻擊
編譯優化
死代碼消除：在編譯器的機器無關優化環節，將不會對程序執行結果產生影響的代碼（即死代碼）刪除。
循環不變量的代碼移動：在編譯器的機器無關優化環節，在保證不影響程序執行結果的情況下，將循環中的特定語句移動到循環外，使得程序運行時執行的語句數減少。
有助於程序理解
為集成開發環境的功能提供幫助：當你使用VS/Idea/Clion/Eclipse/Android Studio 等等IDE 時，將鼠標懸停在代碼上，IDE 能夠動態地分析並提示你所懸停對象的相關信息，背後使用的技術就是靜態程序分析。
1.3 Sound Complete
以上就是靜態程序分析所希望做的一些事情，但是實際上靜態分析發展至今，依舊不能完美地解決以上的問題。Any non-trivial property of the behavior of programs in a r.e. language is undecidable.
在一個即递归可枚举(recursively enumerable)語言中，任何程序行為的non-trivial屬性都是不可解釋的。non-trivial property指的是那些與程序運行行為有關的屬性。
——Rice’s Theorem也就是說，Rice 理論告訴我們，世界上並不存在一種完美的静态分析，可以完美地解決上文提到的那些問題。
由上圖可以直觀地看出，三者成包含關係，而完美的程序分析就是中間的Truth，一個既Sound 又Complete 的狀況，而我們正常的程序分析只能獲得要么sound 要么complete 的結果，一種useful 的結果。
簡單來說，sound 是一種過多的輸出，輸出的是全部的真實報錯和部分的虛假報錯；而complete 與之相反，輸出的是全是真是報錯，但是比truth 少了一部分的報錯。
由上可知，我們在實際使用場景中，自然是希望輸出是sound 的，也就是說可以有誤報但不要有漏報。
1.4 静态程序分析的核心
1.4.1 抽象：Abstract
以符號分析為例，將待分析的具體的變量取值抽象為：正、負、零、未知和錯誤。unknown 指的是，如果當前數值會因為變量改變而呈現為不同的狀態，則全部定義為unknown。
undefined 指的是經過判斷肯定不符合int 定義的，例如一個除以0 的數或者字符等。
1.4.2 近似：Over-approximation
1.4.2.1 转移函数：Transfer function
在靜態分析中，近似的核心是定義轉移函數（transfer function）。transfer function 是針對程序中的每一個語句，在抽象值上定義轉換規則。
transfer function 的規則是根據分析的具體問題與程序語義來定義的。
如上圖所示：這是針對符號分析定義的部分的轉換函數，前五個和第八個一目了然，不做解釋。
第六個因為除數是0，故結果是undefined。第七個是由於我們定義的轉換函數是抽象的，進行運算的目標也是抽像出來的，因此相加結果是unknown 的。舉個例子，即使我正數是1000，負數是-1，經過抽像後再經過轉換函數處理，得到的結果仍是unknown，這也是sound 的一種體現。
根據上述的轉換函數，可以對程序語句進行分析，最終得到的結果如下。
1.4.2.2 控制流：Control Flow
實際上，在程序分析的過程中，近似的過程中還要考慮程序的控制流。
右圖是左圖的運算流展示，在不同情況下y 會有值，而根據sound 原則，在最後一步的y 值只能是unknown。
在程序分析中，不可能與枚舉所有的路徑，因此flow merging （控制流的匯聚）作為一種近似，在靜態分析中十分常用。
2 中间表示：Intermediate Representation
2.1 编译器与静态分析器
首先介紹一下編譯器與靜態分析器的關係：
編譯器主要目的是為了將程序員寫的Source Code 轉換為機器可以理解的Machine Code，並在轉換過程中及時報錯。下面以英語的語法規則為例。
第一步，通過掃描器(Scanner) 對輸入進行掃描，根據正則表達式(Regular Expression) 進行詞法分析(Lexical Analysis)，主要是分析輸入的每個字母及單詞是否為合法字母及單詞，接著將通過檢測的內容轉換為Tokens 傳入下一步。
第二步，通過解析器(Parser) 對Tokens 進行掃描，根據上下文無關語法(Context-Free Grammar) 進行語法分析(Syntax Analysis)，主要分析幾個單詞的組合是否符合語法結構規則，接著將通過檢測的內容以抽象語法樹(AST) 的形式傳入下一步。其中使用上下文無關語法進行分析是為了加快分析效率。
第三步，通過類型檢查(Type Checker)，根據屬性語法(Attribute Grammar) 進行語義分析(Semantic Analysis)，理想的目的是為了識別像apples eat me 這種語法結構正確但是語義錯誤的情況，但是實際編譯器只能識別類如“不可進行int 除以string”之類的類型錯誤，故該步稱為類型檢測。生成進一步處理後的AST 傳入下一步。
第四步，為了進行靜態分析優化，要將Decorated AST 轉換為中間表示(IR)，一般轉換為三地址碼，再進行靜態分析。最後通過代碼生成器將優化後的代碼生成機器碼傳給機器。
2.2 IR
2.2.1 AST vs. IR
以一個循環為例來闡述AST 與IR 的區別。 AST 是一個語法樹的形式，是一個高層級的形式，更加接近程序的源代碼，語言相關的，適合做快速的類型檢測，但是缺少了控制流信息。IR 即為中間表示，圖中以三地址碼表示，是一個低層級的形式，接近機器編碼，語言無關的，結構緊湊，包含了控制流信息，因此更加適合用來做靜態分析。
AST
high-level and closed to grammar structure
usually language dependent
suitable for fast type checking
lack of control flow information
IR
low-level and closed to machine code
usually language independent
compact and uniform
contains control flow information
usually considered as the basis for static analysis
所以IR 更適合靜態分析
IR 沒有固定的定義，常用三地址碼
2.3 三地址码
三地址碼沒有形式化的定義，通常來說，三地址碼就是最多有三個地址(address) 的表達形式，並且由於這個性質，每個三地址碼最多只會有一個運算符。
在Java 中，可以利用soot 工具來生成三地址碼，在soot 中，被稱之為Jimple。下面以一個do-while循環為例，來分析其三地址碼。
1
2
3
4
5
6
7
8
9
10
package nju.sa.example;
public class DoWhileLoop3AC {
public static void main(String[] args) {
int[] arr=new int[10];
int i=0;
do {
i=i + 1;
} while (arr 10);
}
}
轉換後的三地址碼形式為：
再以Method Call 為例，介紹下面向對象環境下的三地址碼。
1
2
3
4
5
6
7
8
9
10
package nju.sa.example;
public class MethodCall3AC {
String foo(String para1, String para2) {
return para1 + ' ' + para2;
}
public static void main(String[] args) {
MethodCall3AC mc=new MethodCall3AC();
String result=mc.foo('hello', 'world');
}
}
Java 中的invoke 指令對應的方法調用情況：
invokespecial: call constructor, call superclass methods, call private methods
invokevirtual: instance method call
invokeinterface: cannot optimization, checking interface implementation
invokestatic: call static methods
2.4 控制流分析
控制流分析（Control Flow Analysis）通常指的是構建控制流圖（Control Flow Graph, CFG），並以CFG 作為基礎結構進行靜態分析的過程。2.4.1 控制流图
通常採用控制流圖進行控制流分析的表示控制流圖可以用來表示控制流的結構
控制流圖的節點可以是單個的三地址碼，不過通常是Basic Block(BB)，如下所示。
2.4.2 Basic Block
Basic Block 是具有以下属性的、最大長度的三地址碼組成的塊單元：只能從塊的第一條指令進入。
只能從塊的最後一條指令離開。
如何構建基本塊：
P 的第一條指令就是一個基本塊的leader
跳轉的目標指令是一個基本塊的leader
跳轉指令的後一條指令，也是一個基本塊的leader
一個基本塊就是一個基本塊的leader 及其後續直到下一個基本塊的leader 前的所有指令。
2.4.3 边的生成
除了基本塊，CFG 中還會有塊到塊的邊。塊A 和塊B 之間有一條邊，當且僅當：A 的末尾有一條指向了B 開頭的跳轉指令。
A 的末尾緊接著B 的開頭，且A 的末尾不是一條無條件跳轉指令。
注意到每個基本塊和開頭指令的標號唯一對應，因此很自然地，需要將跳轉指令的目標改為基本塊的標號而非指令標號：
有了這些定義，我們就可以了解一些概念：
若A - B，則我們說A 是B 的前驅（predecessor），B 是A 的後繼（successor）
除了構建好的基本塊，我們還會額外添加兩個結點，「入口（Entry）」和「出口（Exit）」
這兩個結點不對應任何IR
入口有一條邊指向IR 中的第一條指令
如果一個基本塊的最後一條指令會讓程序離開這段IR，那麼這個基本塊就會有一條邊指向出口。
這樣就完成了一個控制流圖的構建。
3 数据流分析
3.1 相关概念
近似方案1：忽略掉程序的條件判斷，認為所有的分析都有可能到達程序可以看成是**狀態（數據）和狀態之間的轉移（控制）**兩部分，因為狀態轉移的條件都被忽略了，核心分析的部分是狀態數據在轉移過程中的變化，所以叫做數據流分析。
近似方案2：不在路徑末尾做合併，在控制流匯合的所有位置提前做合併
數據流分析要保證Safe-approximation，即：
may analysis: over-approximation
must analysis: under-approximation
總之，不同的數據流分析有不同的數據抽象方法（應用不同），有不同的Safe-approximation 策略，有不同的轉移函數與控制流匯聚方式。
3.1.1 输入输出状态
每一條IR 的執行，都會使狀態從输入状态變成新的输出状态輸入/輸出狀態與語句前/後的program point相關聯。
在數據流分析中，我們會把每一個program point 關聯一個數據流值，代表在該點中可觀察到的抽象的程序狀態。數據流分析的目的是為所有語句的輸入輸出找到一組，基於控制流和轉換函數的，安全的近似約束的解決方案。
3.1.2 转移函数
分析數據流有前向和後向兩種：
3.1.2 控制流约束
每條語句s 都會使程序狀態發生改變。 B 的輸出自然是其輸入在經過多次轉換後得到的狀態。而B 的輸入要根據數據流分析的需求，對其前驅應用合適的meet operator 進行處理。後向分析時亦然。
3.2 应用
3.2.1 到达定值分析：Reaching Definitions Analysis
基本概念
假定x 有定值d (definition)，如果存在一個路徑，從緊隨d 的點到達某點p，並且此路徑上面沒有x 的其他定值點，則稱x 的定值d 到達(reaching) p。如果在這條路徑上有對x 的其它定值，我們說變量x 的這個定值d 被殺死(killed) 了
到達定值可以用來分析未定義的變量。例如，我們在程序入口為各變量引入一個dummy 定值。當程序出口的某變量定值依然為dummy，則我們可以認為該變量未被定義。
對於一條賦值語句D: v=x op y，該語句生成了v 的一個定值D，並殺死程序中其它對變量v 定義的定值。
理解到达定值分析
數據流值：程序中所有變量的定值。
可以用一個bit vector 來定義，有多少個賦值語句，就有多少個位。
D 即Definition，可以表示為：D：v=x op y
一個D 可以視為一行三地址碼，做了兩件事：
生成了一個定義D
在保持其他傳入程序不受影響的同時，kill 了程序中其它對變量v 的定義
轉移方程與控制流：
其中U 表示union，結合前文使用bit 字節表示的D，可以知道，IN 的輸入等於OUT[P1] 並OUT[P2]，意味著只要存在一條路徑可以reach，那麼就算作可以reach。
达定值分析的算法表示
這是一個經典的迭代算法：
首先讓所有BB 和入口的OUT 為空。因為你不知道BB 中有哪些定值被生成。
當任意OUT 發生變化，則分析出的定值可能需要繼續往下流動，所需要修改各BB 的IN 和OUT。
先處理IN，然後再根據轉移完成更新OUT