面向錯誤檢測的指針分析技術(shù)研究.pdf

1、指針分析是一種靜態(tài)程序分析技術(shù)，它的目標是靜態(tài)確定一個指針變量能夠指向哪些地址（變量或函數(shù)的存儲位置），也就是靜態(tài)確定一個指針變量在程序運行時所有可能的值。指針分析以程序源代碼（或某種中間代碼表示）作為輸入，輸出該程序所包含的指針指向信息。由于指針（引用）在C/C++(Java)程序中被廣泛使用，許多靜態(tài)程序分析技術(shù)需要根據(jù)指針指向信息來解析程序中包含的間接引用，指針分析的結(jié)果直接影響其它靜態(tài)程序分析技術(shù)的有效性，指針分析作為許多靜態(tài)程

2、序分析技術(shù)的使能技術(shù)一直是一項重要的議題。對于動態(tài)性較弱、使用指針較少、規(guī)模較小的程序，現(xiàn)有的指針分析技術(shù)已經(jīng)較為成熟，可以很好地分析處理這些程序。然而，對于規(guī)模更大、動態(tài)性更強的程序，如大規(guī)模程序和并發(fā)程序，現(xiàn)有的指針分析算法還存在許多問題，需要進一步地研究:(1)如何在不影響指向信息精度的條件下，提高指針分析算法的效率和可擴展性;(2)如何提高指針分析算法的精度，同時盡可能地保證算法的效率和可擴展性;(3)如何設(shè)計適用于并發(fā)程序的指

3、針分析算法等。
　　錯誤檢測是軟件工程的研究熱點之一。對于C/C++程序，為了檢測程序中普遍存在的內(nèi)存錯誤，如內(nèi)存泄露(memory leak)、同一塊內(nèi)存空間的多次釋放和空指針解引用(null pointer dereference)等，錯誤檢測算法需要根據(jù)指針指向信息來解析程序中包含的間接引用，錯誤檢測算法的有效性直接依賴底層指針分析算法的精度、效率和可擴展性。與順序程序類似，對于并發(fā)程序，為了檢測程序中普遍存在的錯誤，如數(shù)據(jù)

4、爭用(data race)等，錯誤檢測算法同樣需要根據(jù)指針指向信息來解析程序中包含的間接引用。對錯誤檢測算法來說，理想的目標是借助于一個指向信息精度好、算法效率高和可擴展性好的指針分析算法去解析程序中包含的間接引用信息。
　　考慮到錯誤檢測的需求，本文對指針分析進行了深入研究，研究內(nèi)容主要包含兩個方面:基于包含的流不敏感指針分析算法和多線程指針分析算法。對基于包含的流不敏感指針分析算法的研究主要是圍繞如何設(shè)計有效的在線循環(huán)檢測技術(shù)

5、，因為在線循環(huán)檢測技術(shù)能夠在不影響指向信息精度的條件下，顯著地提高基于包含的指針分析算法的效率和可擴展性。本文針對現(xiàn)有的在線循環(huán)檢測技術(shù)LCD(lazycycle detection)存在的不足進行改進，提出了三種在線循環(huán)檢測技術(shù)（ELCD、BootCD和ADD）;對多線程指針分析算法的研究主要是在因果數(shù)據(jù)流分析的基礎(chǔ)上，設(shè)計了一種基于Petri網(wǎng)的多線程指針分析技術(shù)。
　　論文的主要成果表現(xiàn)在以下幾個方面:
　　(1)針對

6、LCD算法存在的不足，對LCD的循環(huán)效果進行改進，提出了ELCD(extended lazy cycledetection)算法;與LCD相比，ELCD基于更精細的循環(huán)效果來檢測約束圖中潛在的循環(huán)，它定義的循環(huán)效果不僅依賴一條有向邊的兩個結(jié)點的指向集信息，同時還依賴這條邊的目的結(jié)點的后繼結(jié)點的指向集信息?；诟毜难h(huán)效果，ELCD算法能夠明顯減少LCD算法觸發(fā)的那些循環(huán)檢測結(jié)果是約束圖中不存在循環(huán)的循環(huán)檢測過程的數(shù)目。實驗結(jié)果表明E

7、LCD算法能夠在不影響LCD算法的指向信息精度的情況下提高LCD算法的效率。
　　(2)為了進一步地提高LCD循環(huán)檢測的質(zhì)量（即減少LCD算法觸發(fā)的那些循環(huán)檢測結(jié)果是約束圖中不存在循環(huán)的循環(huán)檢測過程的數(shù)目），提出了BootCD（bootstrapped online cycle detection）算法;BooCD算法基于bootstrapping這樣一個想法，首先利用一種高效的但不精確的指針分析算法進行一次指針分析，然后基于這些

8、指針指向信息輔助后續(xù)指針分析算法進行在線循環(huán)檢測，從而提高了后續(xù)指針分析算法的效率。具體來說，BootCD混合Steensgaard指針指向信息，定義并構(gòu)造了一個新的有向圖，稱為bootstrapping約束圖，它是andersen約束圖的超圖，BootCD借助bootstrapping約束圖中的循環(huán)邊集信息在andersen約束圖中進行在線循環(huán)檢測。實驗結(jié)果表明，與LCD相比，BootCD顯著地提高了在線循環(huán)檢測的質(zhì)量，減少了整個分析

9、時間，提高了基于包含指針分析的效率。
　　(3)提出了兩種新的概念——bootstrapping約束圖（bootstrapping constraint graph）和約束等價（constraint equivalence），同時設(shè)計了bootstrapping約束圖的構(gòu)造方法和約束等價的變量對信息的求解方法;bootstrapping約束圖是BootCD算法的基礎(chǔ)，而約束等價的作用是:(a)能夠簡化bootstrapping約束

10、圖（即減少bootstrapping約束圖中的結(jié)點和有向邊）;(b)能夠優(yōu)化bootstrapping約束圖的構(gòu)造過程，這顯著地減少了BootCD離線分析的時間開銷和內(nèi)存耗費（即構(gòu)造bootstrapping約束圖和計算bootstrapping約束圖的循環(huán)邊集所需的時間開銷和內(nèi)存耗費），有助于提高BootCD算法的有效性和效率。
　　(4)為了進一步地提高LCD在線循環(huán)檢測的效率，提出了一種新的在線循環(huán)檢測技術(shù)ADD(ances

11、tor_descendant_dominator);與BootCD相比，ADD同樣是基于bootstrapping這樣一個想法;ADD與BootCD的區(qū)別是用于bootstrap在線循環(huán)檢測的信息不同;BootCD利用bootstrapping約束圖及其循環(huán)邊信息來boostrapping，而ADD使用離線約束圖（offiine constraint graph）的結(jié)構(gòu)信息來bootstrapping。具體來說，ADD首先構(gòu)造離線約束圖

12、，計算并合并離線約束圖中包含的循環(huán);此時，離線約束圖變成一個有向無環(huán)圖(DAG);然后，在這個DAG中，為每個結(jié)點定義并計算Ancestor集和Descendant集，這些信息被用于輔助后續(xù)指針分析過程進行在線循環(huán)檢測;最后，基于離線約束圖中包含的必經(jīng)結(jié)點信息，ADD能夠識別指針等價的頂層變量對信息;合并這些頂層變量對信息能夠減少后續(xù)在線分析過程中結(jié)點間指向信息傳播的開銷，有助于進一步提高ADD的效率。初步的實驗結(jié)果表明，與LCD相比，

13、ADD明顯地提高了在線循環(huán)檢測的效率，減少了整個分析時間，提高了基于包含指針分析的效率。
　　(5)在因果數(shù)據(jù)流分析的基礎(chǔ)上，設(shè)計了一種基于Petri網(wǎng)的多線程指針分析技術(shù);具體來說，首先使用1-safe petri網(wǎng)來表示程序的并發(fā)控制流結(jié)構(gòu)，然后研究petri網(wǎng)的偏序執(zhí)行(partially orderedexecution)，其中指針指向信息沿著具有因果關(guān)系的事件進行傳播;多線程程序的指針分析問題被轉(zhuǎn)化成petri網(wǎng)的標識覆