1.簡(jiǎn)介

別名分析是編譯器理論中的一種技術(shù)，用于確定存儲(chǔ)位置是否可以以多種方式訪問(wèn)。如果兩個(gè)指針指向相同的位置，則稱這兩個(gè)指針為別名。但是，它不能與指針?lè)治龌煜羔樂(lè)治鼋鉀Q的問(wèn)題是一個(gè)指針可能指向哪些對(duì)象或者指向哪些地址，而別名分析解決的是兩個(gè)指針指向的是否是同一個(gè)對(duì)象。指針?lè)治龊蛣e名分析通常通過(guò)靜態(tài)代碼分析來(lái)實(shí)現(xiàn)。

別名分析在編譯器理論中非常重要，在代碼優(yōu)化和安全方面有著非常廣泛且重要的應(yīng)用。編譯器級(jí)優(yōu)化需要指針別名信息來(lái)執(zhí)行死代碼消除（刪除不影響程序結(jié)果的代碼）、冗余加載/存儲(chǔ)指令消除、指令調(diào)度（重排列指令）等。編譯器級(jí)別的程序安全使用別名分析來(lái)檢測(cè)內(nèi)存泄漏和內(nèi)存相關(guān)的安全漏洞。

2.別名分析分類

別名分析種類繁多，通常按如下屬性進(jìn)行分類：域敏感度（field-sensitivity）、過(guò)程內(nèi)分析（Intra-Procedural）v.s.過(guò)程間分析（Inter-Procedural）、上下文敏感度（context-sensitivity）和流敏感度（flow-sensitivity）。

2.1 域敏感（Field-Sensitivity）

域敏感度是對(duì)用戶自定義類型進(jìn)行分析的一種策略（亦可以處理數(shù)組）。在域敏感維度共有三種分析策略：域敏感（field-sensitive）、域非敏感（field-insensitive）、域基礎(chǔ)分析（field-based）。以下面代碼為例：

structTest{
intfield1;
intfield2;
}

Testa1;
Testa2;

Note：field這里為結(jié)構(gòu)體或者類的數(shù)據(jù)成員。

域非敏感：對(duì)每個(gè)對(duì)象建模，而對(duì)對(duì)象中的成員不進(jìn)行處理；其建模后的結(jié)果如下圖，僅有a1.*和a2.*的區(qū)別：

域基礎(chǔ)分析：僅對(duì)結(jié)構(gòu)體中的成員進(jìn)行建模，而不感知對(duì)象。其建模后的結(jié)果如下圖，僅有*.field1和*.field2：

域敏感：既對(duì)對(duì)象建模，又對(duì)成員變量進(jìn)行處理。其建模后的結(jié)果如下圖，有a1.field1、a1.field2、a2.field1、a2.field2：

處理數(shù)組時(shí)，相同的原則亦適用。以C整數(shù)數(shù)組為例：int a[10]，域非敏感分析僅使用一個(gè)節(jié)點(diǎn)建模：a[*]，而域敏感分析創(chuàng)建10個(gè)節(jié)點(diǎn)：a[0]、a[1]、...、a[9]。

總結(jié)：域敏感別名分析準(zhǔn)確性高，但是當(dāng)存在嵌套結(jié)構(gòu)或者大數(shù)組時(shí)，節(jié)點(diǎn)數(shù)量會(huì)迅速增加，分析成本也會(huì)陡然上升。

2.2 過(guò)程內(nèi)分析（Intra-Procedural）v.s.過(guò)程間分析（Inter-Procedural）

過(guò)程內(nèi)分析僅分析函數(shù)體內(nèi)部的指針，并沒有考慮與其他函數(shù)之間的相互影響。需要特別指出的是，過(guò)程內(nèi)分析當(dāng)處理包含指針入?yún)⒌暮瘮?shù)或者返回指針的函數(shù)時(shí)，其分析可能不夠準(zhǔn)確。相反，過(guò)程間分析會(huì)在函數(shù)調(diào)用過(guò)程中處理指針的行為。

過(guò)程內(nèi)分析不易于擴(kuò)展，精度較低。相比過(guò)程間分析，過(guò)程內(nèi)分析更容易實(shí)現(xiàn)，且過(guò)程內(nèi)/間分析與上下文敏感度分析高度相關(guān)，因?yàn)橐粋€(gè)上下文敏感分析必定是一個(gè)過(guò)程間分析。

2.3 上下文敏感度（Context-Sensitivity）

上下文敏感度用來(lái)控制函數(shù)調(diào)用該如何分析。有兩種分析方法：上下文敏感（context-sensitive） 和上下文非敏感（context-insensitive）。上下文敏感在分析函數(shù)調(diào)用的目標(biāo)（被調(diào)用者）時(shí)考慮調(diào)用上下文（調(diào)用者）。以如下代碼為參考[1]：

1publicstaticvoidmain(String[]args){
2Stringname1=getName(3);//Tainted
3Stringsql1="select*fromuserwherename="+name1;
4sqlExecute(sql1);//TaintSink
5
6Stringname2=getName(-1);//NotTainted
7Stringsql2="select*fromuserwherename="+name2;
8sqlExecute(sql2);
9}
10
11privatestaticStringgetName(intx){
12if(x>0){
13returnSystem.getProperty("name");
14}else{
15return"zhangsan";
16}
17}

如上所示，getName()方法基于入?yún)⒌牟煌?，?huì)返回不同的結(jié)果，在第2行和第6行，獲取到的name1和name2的污點(diǎn)信息不同，當(dāng)入?yún)?時(shí)，返回的是一個(gè)從環(huán)境變量中獲取的污染的數(shù)據(jù)，導(dǎo)致sql注入，而當(dāng)入?yún)?1時(shí)，返回的是一個(gè)常量，不是污染數(shù)據(jù)，不會(huì)有問(wèn)題。在上下文敏感的分析中，在第4行應(yīng)該報(bào)一個(gè)sql注入問(wèn)題，而在第8行則不應(yīng)該報(bào)sql注入問(wèn)題。而上下文非敏感的分析中，不考慮傳入?yún)?shù)的不同，getName()方法則全部返回一個(gè){System.getProperty("name")}∨{zhangsan}，從而導(dǎo)致第4行和第8行都會(huì)報(bào)一個(gè)sql注入的問(wèn)題。

上下文敏感別名分析需要有一種方法，為函數(shù)getName創(chuàng)建抽象描述，以便每次調(diào)用它時(shí)，分析器都可以將調(diào)用上下文應(yīng)用于抽象描述。

總結(jié)：上下文敏感分析比較準(zhǔn)確，但是增加了復(fù)雜度。

2.4 流敏感度（Flow-Sensitivity）

流敏感度是一種是否考慮代碼順序的原則。有兩種方法：流敏感（flow-sensitive）和流非敏感（flow-insensitive）。

流非敏感不考慮代碼順序，并為整個(gè)程序生成一組別名分析結(jié)果，而流敏感考慮代碼順序，計(jì)算程序中每個(gè)指針出現(xiàn)的位置的別名信息。以如下代碼為例：

1inta,b;
2int*p;
3p=&a;
4p=&b;

流非敏感的分析結(jié)果是針對(duì)整個(gè)代碼塊，其結(jié)果應(yīng)該是：指針p可能指向變量a或者變量b。流敏感生成的別名信息是，在第3行，指針p指向變量a，在第4行以后指針p指向變量b。

Note：當(dāng)程序具有許多條件語(yǔ)句、循環(huán)或遞歸函數(shù)時(shí)，流敏感分析的復(fù)雜性會(huì)大大增加。要執(zhí)行流敏感分析，需要完整的控制流圖。因此，流敏感分析非常精確，但對(duì)于大多數(shù)情況來(lái)說(shuō)，它的分析成本過(guò)高，無(wú)法在整個(gè)程序上執(zhí)行。

3.別名分析常見算法介紹

常見的別名算法共有三種：Andersen's指針?lè)治鏊惴āteensgaard's指針?lè)治鏊惴ê蛿?shù)據(jù)結(jié)構(gòu)分析算法。

Andersen's指針?lè)治鍪且环N流非敏感和上下文非敏感的分析算法。Andersen's指針?lè)治鏊惴◤?fù)雜度較高，實(shí)踐應(yīng)用性較差，其時(shí)間復(fù)雜度為，其中n為指針節(jié)點(diǎn)個(gè)數(shù)。

Steensgaard's指針?lè)治鏊惴ㄒ彩且环N流非敏感，上下文非敏感且域非敏感的別名分析算法。其時(shí)間復(fù)雜度較低，實(shí)現(xiàn)相對(duì)簡(jiǎn)單，實(shí)踐應(yīng)用廣，其時(shí)間復(fù)雜度為，其中無(wú)限接近于1，但是其別名分析的準(zhǔn)確性較低。

數(shù)據(jù)結(jié)構(gòu)分析算法是一種流非敏感，上下文敏感和域敏感的算法。其時(shí)間復(fù)雜度較低，為O(n * log(n)) ，應(yīng)用性較好，但是由于不支持MustAlias（參考“AliasAnalysis Class概覽”章節(jié)），導(dǎo)致其應(yīng)用有局限性。

4.別名分析在LLVM中的應(yīng)用與實(shí)現(xiàn)

4.1 應(yīng)用

別名分析在代碼優(yōu)化和安全方面有著非常重要且廣泛的應(yīng)用，以下面C代碼為例，來(lái)簡(jiǎn)單介紹別名分析在代碼優(yōu)化方面的應(yīng)用[2]。

intfoo(int__attribute__((address_space(0)))*a,
int__attribute__((address_space(1)))*b){
*a=42;
*b=20;
return*a;
}

__attribute__屬性指定了變量a指向地址0，變量b指向地址1。我們知道在ARM架構(gòu)中，地址0和地址1是完全不同的，修改地址0中的內(nèi)存永遠(yuǎn)不會(huì)修改地址1中的內(nèi)存。以下為該函數(shù)可能生成的LLVM IR信息：

definei32@foo(i32addrspace(0)*%a,i32addrspace(1)*%b)#0{
entry:
storei3242,i32addrspace(0)*%a,align4
storei3220,i32addrspace(1)*%b,align4
%0=loadi32,i32*%a,align4
reti32%0
}

第一個(gè)store將42存儲(chǔ)到變量a指向的地址，第二個(gè)store指令將20存儲(chǔ)到變量b指向的地址。%0 = ... 指向的行將變量a中的值加載到一個(gè)臨時(shí)變量0中，并在最后一行返回該臨時(shí)變量0。

上述代碼是未對(duì)foo函數(shù)進(jìn)行優(yōu)化的情況，下面我們考慮對(duì)foo函數(shù)進(jìn)行優(yōu)化。

我們優(yōu)化后的代碼可能如下：刪除了load指令對(duì)應(yīng)的行，最后一行直接返回了常量42。

definei32@foo(i32addrspace(0)*%a,i32addrspace(1)*%b)#0{
entry:
storei3242,i32addrspace(0)*%a,align4
storei3220,i32addrspace(1)*%b,align4
reti3242
}

然而，我們進(jìn)行優(yōu)化的時(shí)候需要仔細(xì)一些，因?yàn)樯鲜鰞?yōu)化僅在a和b指向的地址不會(huì)相互影響時(shí)有效。例如：當(dāng)我們給foo函數(shù)傳遞的指針相互影響時(shí)：

inti=0;
intresult=foo(&i,&i);

在未開啟優(yōu)化的版本中，變量i將先被設(shè)置為42，然后被設(shè)置為20，最后返回20。然而，在優(yōu)化版本中，雖然我們執(zhí)行了兩次store操作依次將42、20賦值給變量i，但是返回值是42，而不是20。因此優(yōu)化版本破壞了foo函數(shù)本身的行為。

如果應(yīng)用了別名分析，編譯器能夠合理地執(zhí)行上述優(yōu)化。在執(zhí)行優(yōu)化前判斷入?yún)和b是否為別名，如果是別名，則不執(zhí)行刪除load指令對(duì)應(yīng)行的操作，否則執(zhí)行刪除操作。

4.2 實(shí)現(xiàn)

本文以LLVM16.0.0版本為參考，從代碼接口入手，帶領(lǐng)大家學(xué)習(xí)別名分析的代碼實(shí)現(xiàn)。

LLVM AliasAnalysis類是LLVM系統(tǒng)中客戶使用和別名分析實(shí)現(xiàn)的主要接口，或者說(shuō)一個(gè)“基類” 。除了簡(jiǎn)單的別名分析信息外，這個(gè)類還聲明了Mod/Ref信息，從而使強(qiáng)大的分析和轉(zhuǎn)換能夠很好地協(xié)同工作。

源碼參考鏈接：AliasAnalysis.h[3]、AliasAnalysis.cpp[4]。

4.2.1 基礎(chǔ)知識(shí)

MemoryLocation：LLVM中對(duì)內(nèi)存地址的描述，主要應(yīng)用在別名分析中，我們需要掌握該類中三個(gè)屬性：

其中，Ptr表示內(nèi)存開始地址，Size表示內(nèi)存大小，AATags是描述內(nèi)存位置別名的metadata節(jié)點(diǎn)集合 。

4.2.2 AliasAnalysis Class概覽

AliasAnalysis類定義了各種別名分析實(shí)現(xiàn)應(yīng)該支持的接口。這個(gè)類導(dǎo)出兩個(gè)重要的枚舉:AliasResult和ModRefResult，它們分別表示別名查詢或mod/ref查詢的結(jié)果。

1、關(guān)鍵代碼如下，AliasAnalysis為AAResults類別名：

2、AliasResult關(guān)鍵代碼如下：

其中NoAlias表示兩個(gè)內(nèi)存對(duì)象沒有任何重疊區(qū)域；MayAlias表示兩個(gè)指針可能指向同一對(duì)象；PartialAlias表示兩個(gè)內(nèi)存對(duì)象對(duì)應(yīng)的地址空間有重疊；MustAlias表示兩個(gè)內(nèi)存對(duì)象總是從同一位置開始。

3、ModRefResult關(guān)鍵代碼

其中NoModRef表示訪問(wèn)內(nèi)存的操作既不會(huì)修改該內(nèi)存也不會(huì)引用該內(nèi)存；Ref表示訪問(wèn)內(nèi)存的操作會(huì)可能引用該內(nèi)存；Mod表示訪問(wèn)內(nèi)存的操作可能會(huì)修改該內(nèi)存；ModRef表示訪問(wèn)內(nèi)存的操作既可能引用該內(nèi)存也可能修改該內(nèi)存。

alias接口

其接口定義如下：

別名方法是用于確定兩個(gè)MemoryLocation對(duì)象是否相互別名的主要接口。它接受兩個(gè)MemoryLocation對(duì)象作為輸入，并根據(jù)需要返回MustAlias、PartialAlias、MayAlias或NoAlias。與所有AliasAnalysis接口一樣，alias方法要求其入?yún)⒌膬蓚€(gè)MemoryLocation對(duì)象定義在同一個(gè)函數(shù)中，或者至少有一個(gè)值是常量。

其接口實(shí)現(xiàn)如下：

getModRefInfo 接口

getModReInfo方法返回關(guān)于給定的指令執(zhí)行是否可以讀取或修改給定內(nèi)存位置的信息。Mod/Ref信息具有保守性：如果一條指令可能讀或?qū)懸粋€(gè)位置，則返回ModRef。其接口定義眾多，我們以如下接口為例來(lái)進(jìn)行學(xué)習(xí)。

其接口實(shí)現(xiàn)如下：

從上述代碼可知，處理共分為四步：

（1）遍歷AAs，如果發(fā)現(xiàn)其任一結(jié)果是NoModRef，則直接返回，對(duì)應(yīng)代碼行228-234；

（2）調(diào)用節(jié)點(diǎn)（call）操作中是否訪問(wèn)了一個(gè)在LLVM IR中無(wú)法訪問(wèn)的地址，如果是的話，直接返回NoModRef，否則獲取其調(diào)用節(jié)點(diǎn)的ModRefInfo信息，對(duì)應(yīng)代碼行239-240；

（3）處理調(diào)用節(jié)點(diǎn)中指針入?yún)⒌腗odRefInfo信息，如果發(fā)現(xiàn)是NoModRef，則直接返回NoModRef，否則將ModRefInfo信息和之前的結(jié)果合并，對(duì)應(yīng)代碼行247-266；

（4）如果getModRefInfo函數(shù)中的入?yún)oc指定的內(nèi)存地址具有常量屬性并且ModRefInfo信息包含Mod，則調(diào)用節(jié)點(diǎn)一定不會(huì)修改Loc內(nèi)存，因此需要將Ref屬于與之前的結(jié)果做邏輯與操作，對(duì)應(yīng)代碼行271-272。

4.2.3 LLVM中已經(jīng)實(shí)現(xiàn)的別名分析

-basic-aa pass

-basic-aa pass是一種激進(jìn)的本地分析，它提供許多重要的事實(shí)信息[5]：

不同的全局變量、堆棧分配和堆分配永遠(yuǎn)不能別名。

全局變量、棧分配的變量和堆分配變量永遠(yuǎn)不會(huì)和空指針別名。

結(jié)構(gòu)體中的不同字段不能別名。

同一數(shù)組，索引不同的兩個(gè)對(duì)象不能別名。

許多通用的標(biāo)準(zhǔn)C庫(kù)函數(shù)從不訪問(wèn)內(nèi)存或只讀取內(nèi)存。

-globals-aa pass

這個(gè)pass實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的對(duì)內(nèi)部全局變量（該變量的地址沒有被獲取過(guò)）進(jìn)行上下文敏感的mod/ref分析和別名分析。如果某個(gè)全局變量的地址沒有被獲取，則該pass可以得出如下結(jié)論：沒有指針作為該全局變量的別名。該pass還會(huì)識(shí)別從不訪問(wèn)內(nèi)存或從不讀取內(nèi)存的函數(shù)。這允許某些指定的優(yōu)化(例如GVN)完全消除調(diào)用指令。

這個(gè)pass的真正威力在于它為調(diào)用指令提供了上下文敏感的mod/ref信息。這使優(yōu)化器清楚的了解到對(duì)于某些函數(shù)的調(diào)用不會(huì)破壞或讀取全局變量的值，從而允許消除加載和存儲(chǔ)指令。

Note：該pass在使用范圍上有一定限制，僅支持沒有被取過(guò)地址的全局變量，但是該pass分析速度非?？臁?/p>

除了上述pass外，LLVM中還實(shí)現(xiàn)了cfl-steens-aa、cfl-anders-aa、tbaa、scev-aa。目前LLVM中O1，O2，O3優(yōu)化默認(rèn)開啟的別名分析是basic-aa，globals-aa和tb-aa。

5.寫在最后

編譯器技術(shù)從20世紀(jì)50年代起，已經(jīng)發(fā)展了近70年的歷史，但是編譯器技術(shù)發(fā)展到今天，依然是一個(gè)非常熱門的技術(shù)，各大硬件廠商都在開發(fā)自己的編譯器，包括因特爾推出的Inter C++、ARM公司推出的armclang以及華為推出的畢昇編譯器等，且上述三款編譯器都是基于LLVM開發(fā)。

編譯器技術(shù)是一門龐大且繁雜的技術(shù)，對(duì)于初學(xué)者來(lái)說(shuō)，這條學(xué)習(xí)之路道阻且長(zhǎng)，盼那些熱愛這門技術(shù)的趕路人能夠行而不輟，未來(lái)可期。