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

鄧朝日 劉鵬輝 顧夢園

（中國電子科技集團公司第三十二研究所 上海 201808）

1 引言

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

2 約束圖及約束圖初始化

2.1 新的約束圖

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

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

2.2 初始化約束圖

上下文敏感是指，a既不是被取地址的局部變量，或全局變量，也不是堆變量。上下文無關是指a是被取地址的局部變量、或全局變量，再或者堆變量。假設函數的指針以及函數的調用圖［5］已經被上下文無關指針分析求出，變量無重名。

?即為初始的約束集中值的上下文標識，也是初始的約束集中變量約束的上下文標識，ρι=（ι，?，⊥）是一個上下文，其對應每個調用點ι。ρ1=（1，?，⊥）是點1的上下文、ρ2=（2，?，⊥）是點2的上下文。y，x，q，p均為上下文無關，w，v，d，s，c，a，e，b，t，均為上下文敏感。

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

當?為右下標為x的ct屬性值時（例如指向集中的xρ），在指向集中x是結點x的表示方式。

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

文中未說明符號同文獻［5］、文獻［11］。

3.1 新的橫向傳播方法框架

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

Algorithm1

1：while true

2：｛Algorithm 2；Algorithm4；Algorithm5

3：if no edge has been added

4：break｝

3.2 環探測和消除

Algorithm3結合文獻［5］中的探測環方法：探測只由ρ值為?的普通邊組成的環（第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），探測出由（e，c，1，?）（c，e，1，?）組成的環，合并c，e為c，則c，e指向集為q?。

unify合并環的觸發條件：環內每個結點的cs賦為false的前提是，環內有上下文無關的節點數量為一個及其以上；每個結點源的指向集共同組成環內節點的指向集；選一結點為代表。

Algorithm3.Input：a node v。

3.3 差異傳播

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

圖1（b）經差異傳播后如圖1（c）。因（a，s，2，1）為調用邊且s的cs值為true，則其上差異傳播由Al?gorithm4第17～19行處理（param1），后｛pρ1｝為s的指向集；類似的，通過在（d，t，2，2）、（c，s，2，2）、（b，t，2，1）上進行差異化傳播，｛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］），則據Algo?rithm4第27～29行處理（ret1），后v指向集為｛x?｝；在（t，w，3，2）上差異傳播后，w指向集為｛y?｝。

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

3.4 復雜約束的處理

算法5（即Algorithm5）結合ret1～3［5］和load1～2，用來處理復雜約束（除函數調用外）。

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

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

因處理復雜約束*s?t后，再執行一次Algo?rithm 1while循環后，已無新邊可添加，分析結束。

4 實驗

因新算法用WP方法［11，15］改進環消除算法［5］，WP方法不影響被改進方法的精度，其目的是提高分析的效率。因此新算法的時效數據是實驗要重點進行驗證的指標項。

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

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

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

第4列為上下文敏感變量數量；

第5列為上下文無關變量數量；

第6列代碼行數（預處理后）。

另外，通過依次對同一個源程序進行環消除算法和新算法分析，并對比各自所消耗的時間記錄于表2。經過分析，新算法的時間效率相比于環消除算法有所提升。

表1 實驗源程序列表

表2 分析時間

5 結語

本文通過結合WP方法和環消除算法提出一新算法。測試說句體現環消除效率以及時間效率被新算法改善，同時能夠保證換消除技術的精確性。未來將致力于在專業領域中實踐該新算法。