上下文敏感的橫向傳播方法?

鄧朝日 劉鵬輝 顧夢(mèng)園

（中國(guó)電子科技集團(tuán)公司第三十二研究所 上海 201808）

1 引言

指針分析是最基礎(chǔ)的靜態(tài)分析，解答了一個(gè)指針可能指向哪個(gè)對(duì)象的問題。上下文無關(guān)指針分析方法能夠區(qū)分不同調(diào)用點(diǎn)的相同函數(shù)，合并所有調(diào)用。基于包含的指針分析方法［1］是其中一類重要的分析方法。二元決策圖［2］在處理高度上下文敏感的指針分析時(shí)體現(xiàn)出較好的性能，但沒有執(zhí)行預(yù)定義約束，所以在進(jìn)一步可擴(kuò)展性分析［3～4］中沒有體現(xiàn)出優(yōu)越性。而Woongsik Choi等［5］發(fā)表的在調(diào)用圖之上進(jìn)行的上下文敏感指針分析和環(huán)消除算法（環(huán)消除算法）除了在時(shí)間分析效率上仍有改進(jìn)空間之外，能夠兼顧高上下文敏感性和高可擴(kuò)展性。慶幸的是近二十年來出現(xiàn)很多基于包含的指針分析改進(jìn)算法［6］，其中Fahndrich［7］、Pearce［8～9］、Harderkopf［10］、Pereira［11］陸續(xù)發(fā)表了不同的基于約束圖進(jìn)行的環(huán)消除算法。尤其Pereira［11］的橫向傳播（Wave Propagation，WP）最優(yōu)秀，能大大提高分析的時(shí)間和空間效率。因而，本文將直觀準(zhǔn)確地表述上下文敏感橫向算法并提出更有效實(shí)現(xiàn)環(huán)消除算法上下文敏感的WP算法。最后在CIL［12］下用OCaml語(yǔ)言實(shí)現(xiàn)分析，并對(duì)代碼行范圍20.000～290.000的6個(gè)程序進(jìn)行分析，分析結(jié)果表明，上下文敏感的橫向傳播算法時(shí)間效率優(yōu)于環(huán)消除算法。

2 約束圖及約束圖初始化

2.1 新的約束圖

一方面，所有結(jié)點(diǎn)都有屬性ct和cs：其中ct的值為上下文集，表示在該集下該變量被另一變量所指向，以上變量均為上下文無關(guān)；cs值為false時(shí)，結(jié)點(diǎn)所對(duì)應(yīng)的變量上下文無關(guān)，相反上下文敏感。例a? ｛ρb｝，若b具備上下文無關(guān)性，a具備上下文敏感性，則圖中有結(jié)點(diǎn)a（cs為true，ct為空）和b（false和ρ分別是cs和ct的值），既在上下文ρ下，b被a所指向。白色圓圈代表該變量上下文敏感，黑色圓圈代表該變量上下文無關(guān)。

另一方面，邊分為三種類型：普通邊（實(shí)線箭頭）；返回邊（調(diào)用返回用虛線箭頭表示），表示接收返回變量值的變量的邊被返回變量所指向；調(diào)用邊（函數(shù)被調(diào)用用實(shí)線箭頭表示），即形參的邊的邊被實(shí)參所指向。邊E（v，w，γ，ρ）上的標(biāo)識(shí)為ρ（ρ為?時(shí)邊上無標(biāo)識(shí)）。v、w分別為邊頭和尾結(jié)點(diǎn)；γ為類別：普通邊值為1，調(diào)用邊值為2、返回邊值為3；若變量v要被變量w包含（在ρ下），則1為γ的值，且上下文集為ρ；若該邊為函數(shù)調(diào)用（在點(diǎn)m處），則2為γ的值，m為ρ的值，其中實(shí)參為v、形參為w；若調(diào)用返回為該邊類型，則3為γ的值，m為ρ的值，其中返回變量為v、獲取其值的變量為w。如（b，a，1，ρ）為普通邊，對(duì)應(yīng)于a?ρb；（b，f。，2，ι）為調(diào)用邊，（f·，a，3，ι）為返回邊，均對(duì)應(yīng)于a? （fb）1。

2.2 初始化約束圖

上下文敏感是指，a既不是被取地址的局部變量，或全局變量，也不是堆變量。上下文無關(guān)是指a是被取地址的局部變量、或全局變量，再或者堆變量。假設(shè)函數(shù)的指針以及函數(shù)的調(diào)用圖［5］已經(jīng)被上下文無關(guān)指針分析求出，變量無重名。

?即為初始的約束集中值的上下文標(biāo)識(shí)，也是初始的約束集中變量約束的上下文標(biāo)識(shí)，ρι=（ι，?，⊥）是一個(gè)上下文，其對(duì)應(yīng)每個(gè)調(diào)用點(diǎn)ι。ρ1=（1，?，⊥）是點(diǎn)1的上下文、ρ2=（2，?，⊥）是點(diǎn)2的上下文。y，x，q，p均為上下文無關(guān)，w，v，d，s，c，a，e，b，t，均為上下文敏感。

圖1（a）用相同名字的結(jié)點(diǎn)代替集中的所有變量，所有結(jié)點(diǎn)的cs屬性被初始化；值約束將繼而被設(shè)置，其右側(cè)變量的屬性將被設(shè)置相應(yīng)的值，例如?為b中ct的值，該結(jié)果是由a??b導(dǎo)致的；后為每個(gè)變量約束添一邊到圖，此邊的屬性將被初始化，例如（e，c，1，?）的增加是由c??e所導(dǎo)致；函數(shù)調(diào)用約束繼而被增加，例如，邊（t，v，3，1）、（a，s，2，1）和（b，t，2，1）的增加是由v?（fa，b）1所導(dǎo)致。

當(dāng)?為右下標(biāo)為x的ct屬性值時(shí)（例如指向集中的xρ），在指向集中x是結(jié)點(diǎn)x的表示方式。

3 橫向傳播（具備上下文敏感性）

文中未說明符號(hào)同文獻(xiàn)［5］、文獻(xiàn)［11］。

3.1 新的橫向傳播方法框架

新WP方法如Algorithm 1，其為條件始終為真的while循環(huán)：輸入為一原始約束圖G=（V，E），輸出為圖中各結(jié)點(diǎn)到其指向集的映射；先調(diào)用Algo?rithm2在圖中探索并合并環(huán)；再調(diào)用Algorithm4進(jìn)行差異傳播［6］；后調(diào)用Algorithm5處理復(fù)雜約束以添加新邊，如無新邊添加終止循環(huán)。

Algorithm1

1：while true

2：｛Algorithm 2；Algorithm4；Algorithm5

3：if no edge has been added

4：break｝

3.2 環(huán)探測(cè)和消除

Algorithm3結(jié)合文獻(xiàn)［5］中的探測(cè)環(huán)方法：探測(cè)只由ρ值為?的普通邊組成的環(huán)（第2行條件）。

Algorithm2 Input：G=（V，E）

1：I←0

2：for all v such that D（v）≠⊥

3：Algorithm 3

4：for all v such that R（v）≠v

5：unify（v，R（v））

如圖1（b），探測(cè)出由（e，c，1，?）（c，e，1，?）組成的環(huán)，合并c，e為c，則c，e指向集為q?。

unify合并環(huán)的觸發(fā)條件：環(huán)內(nèi)每個(gè)結(jié)點(diǎn)的cs賦為false的前提是，環(huán)內(nèi)有上下文無關(guān)的節(jié)點(diǎn)數(shù)量為一個(gè)及其以上；每個(gè)結(jié)點(diǎn)源的指向集共同組成環(huán)內(nèi)節(jié)點(diǎn)的指向集；選一結(jié)點(diǎn)為代表。

Algorithm3.Input：a node v。

3.3 差異傳播

Algorithm4（差異傳播）結(jié)合規(guī)則［5］trans1、trans2、param1、param2、ret1、ret2、ret3，其對(duì)不同邊及變量的cs屬性等其他條件而采用對(duì)應(yīng)操作。如Algorithm4第8～13行處理普通邊，第6～9行處理規(guī)則trans1。

圖1（b）經(jīng)差異傳播后如圖1（c）。因（a，s，2，1）為調(diào)用邊且s的cs值為true，則其上差異傳播由Al?gorithm4第17～19行處理（param1），后｛pρ1｝為s的指向集；類似的，通過在（d，t，2，2）、（c，s，2，2）、（b，t，2，1）上進(jìn)行差異化傳播，｛xρ1，yρ2｝和｛pρ1，qρ2｝分別是t和s的指向集。因t的值等于true，同樣v的cs值也等于true且（t，v，3，1）是返回邊，又由于x.ct|1=ρ1|1=（1，?，⊥）|1=?（Restriction操作［5］），則據(jù)Algo?rithm4第27～29行處理（ret1），后v指向集為｛x?｝；在（t，w，3，2）上差異傳播后，w指向集為｛y?｝。

Algorithm4第35～38行：在w、v均不上下文敏感的情況下，trans2、ret3呈現(xiàn)出：要v指向w，則需要置ct等于?；在w是上下敏感的且v是上下文無關(guān)的情況下，v可直接指向w指向的變量。

3.4 復(fù)雜約束的處理

算法5（即Algorithm5）結(jié)合ret1～3［5］和load1～2，用來處理復(fù)雜約束（除函數(shù)調(diào)用外）。

如處理復(fù)雜約束*s?t后，圖1（c）變?yōu)閳D1（d）。｛pρ1，qρ2｝為s的指向集，如圖1（c）所示。例如，因?yàn)閜ρ1中t的cs值是true，且圖1（c）中無（t，p，1，ρ 1），所以按照算法5（既Algorithm5）第6～8行處理，添加該邊并在此邊上執(zhí)行一次差異傳播，如Algo?rithm5第15行，后p的指向集為｛x?｝；

圖1 示例源程序的分析示例

因處理復(fù)雜約束*s?t后，再執(zhí)行一次Algo?rithm 1while循環(huán)后，已無新邊可添加，分析結(jié)束。

4 實(shí)驗(yàn)

因新算法用WP方法［11，15］改進(jìn)環(huán)消除算法［5］，WP方法不影響被改進(jìn)方法的精度，其目的是提高分析的效率。因此新算法的時(shí)效數(shù)據(jù)是實(shí)驗(yàn)要重點(diǎn)進(jìn)行驗(yàn)證的指標(biāo)項(xiàng)。

為了驗(yàn)證新算法的時(shí)間和環(huán)消除效率，測(cè)試方法與文獻(xiàn)［4］保持一致。其中實(shí)驗(yàn)環(huán)境如下：主機(jī)內(nèi)存12GB；CPU為Intel Core i7，主頻為3.91GHz；實(shí)驗(yàn)代碼用OCaml語(yǔ)言和BuBDDy［14］的hash-consing實(shí)現(xiàn)，并在CIL［12］下分析，實(shí)驗(yàn)數(shù)據(jù)為為先后6次分別對(duì)sqlite、python、tar、named、povray、make等程序開展的分析結(jié)果數(shù)據(jù)進(jìn)行平均計(jì)算，測(cè)試結(jié)果如表2給出了6次分析的平均值及其波動(dòng)范圍。

其中，表1各列含義如下。

第3列為為程序中所有可能上下文；

第4列為上下文敏感變量數(shù)量；

第5列為上下文無關(guān)變量數(shù)量；

第6列代碼行數(shù)（預(yù)處理后）。

另外，通過依次對(duì)同一個(gè)源程序進(jìn)行環(huán)消除算法和新算法分析，并對(duì)比各自所消耗的時(shí)間記錄于表2。經(jīng)過分析，新算法的時(shí)間效率相比于環(huán)消除算法有所提升。

表1 實(shí)驗(yàn)源程序列表

表2 分析時(shí)間

5 結(jié)語(yǔ)

本文通過結(jié)合WP方法和環(huán)消除算法提出一新算法。測(cè)試說句體現(xiàn)環(huán)消除效率以及時(shí)間效率被新算法改善，同時(shí)能夠保證換消除技術(shù)的精確性。未來將致力于在專業(yè)領(lǐng)域中實(shí)踐該新算法。