[發(fā)明專利]一種面向堆操作程序的內(nèi)存泄漏檢測方法

有效

• 申請?zhí)枺?/td>: 201210041025.7
• 申請日: 2012-02-22
• 公開（公告）號: CN102662825A
• 公開（公告）日: 2012-09-12
• 發(fā)明（設(shè)計）人: 王戟;董龍明;陳立前;董威;劉萬偉;李仁見
• 申請（專利權(quán)）人: 中國人民解放軍國防科學(xué)技術(shù)大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 國防科技大學(xué)專利服務(wù)中心 43202
• 代理人: 郭敏

1.一種面向堆操作程序的內(nèi)存泄漏檢測方法，其特征在于包括以下步驟：

第1步，利用編譯器平臺對被檢測程序進行詞法分析、語法分析，生成被檢測程序的抽象語法樹、控制流圖、過程調(diào)用圖；

第2步，預(yù)處理：

2.1切片，即將那些沒有使用任何指針類型變量的賦值語句從程序中刪除，得到切片后的程序；

2.2將經(jīng)過切片后的程序中不符合標(biāo)準(zhǔn)形式的指針賦值語句按照轉(zhuǎn)換規(guī)則轉(zhuǎn)換成標(biāo)準(zhǔn)形式；

第3步，根據(jù)函數(shù)中每個指針變量的別名信息定義指針的擴展類型，得到程序的堆內(nèi)存抽象狀態(tài)；堆操作程序中，指針變量p的擴展類型定義?為：<f₁：<dist；2^PVar>；f₂：<dist，2^PVar>；...f_i：<dist；2^PVar>...；f_n：<dist；2^PVar>>，其中：f₁，f₂，...f_i，...，f_n分別表示p指向內(nèi)存單元中指針域的名字，1≤i≤n，即：p指向由n個指針域聚集的內(nèi)存單元，內(nèi)存單元又稱為內(nèi)存結(jié)點；變量dist表示堆中內(nèi)存結(jié)點距離指針p的值；2^PVar表示所有指向距離p所指向內(nèi)存結(jié)點值為dist的內(nèi)存結(jié)點構(gòu)成的指針變量集，稱為指針別名集；變量dist值的范圍為：0、1和2，其中：元素0和1表示堆內(nèi)存中距離p所指向的內(nèi)存結(jié)點精確值，值2是一個抽象值，表示通過某個指針域f_i兩次或兩次以上的路由次數(shù)，在堆內(nèi)存中這樣得到的內(nèi)存結(jié)點又稱摘要結(jié)點；指針集2^PVar中有兩個特殊的元素：空集?表示堆內(nèi)存中沒有任何指針變量指向該內(nèi)存單元，而該內(nèi)存單元在堆內(nèi)存中已經(jīng)被分配；⊥表示某個指針變量p或指針域f_i的值為null，表示該指針變量值為無效內(nèi)存地址，p或指針域f_i所指向的內(nèi)存單元在堆中還沒有被分配；堆操作程序HP的活性指針變量是程序片段中一類被使用或修改的指針變量，由謂詞LivePVar表示；堆內(nèi)存局部抽象狀態(tài)?是具有活性指針變量的擴展類型構(gòu)成的集合，即：?p_i表示任意一個具有活性的指針變量，?表示p_i的擴展類型；

第4步，從被檢測程序的過程調(diào)用圖中自頂向下選擇某個函數(shù)f，并將函數(shù)f入口處的抽象狀態(tài)?設(shè)置為空，根據(jù)前向數(shù)據(jù)流迭代方法進行過程內(nèi)內(nèi)存泄漏檢測，得到堆操作程序中基本語句關(guān)于堆內(nèi)存抽象狀態(tài)的遷移關(guān)系，前向數(shù)據(jù)流迭代方法是：

4.1初始化函數(shù)f中每個程序點i的堆內(nèi)存抽象狀態(tài)?置為空，并將隊列W置?為空，W是一個先進先出FIFO的隊列，基本元素為?對，s為語句，?為堆內(nèi)存局部抽象狀態(tài)；

4.2將函數(shù)f的入口語句s₀和抽象狀態(tài)?加入到隊列W；

4.3判斷隊列W是否為空，如果為空則轉(zhuǎn)第6步，如果不為空則執(zhí)行4.4；

4.4從隊列W中彈出項?根據(jù)語句s的類型轉(zhuǎn)換抽象狀態(tài)?得到新的抽象狀態(tài)?具體方法如下：

4.4.1如果語句s為基本指針賦值語句，則按7種指針賦值語句的類型轉(zhuǎn)換狀態(tài)?得到新的抽象狀態(tài)?并從控制流圖中語句s的后繼語句集Succ(s)中選擇某個元素s’，然后執(zhí)行4.5；按7種指針賦值語句的類型轉(zhuǎn)換?的方法是：

(1)指針賦值語句p＝null，轉(zhuǎn)換規(guī)則是：在狀態(tài)?中，首先從通過某個指針域f_i路由可達p指向內(nèi)存結(jié)點的指針別名集中刪除p，然后將?置為null，即：將?中所有通過f_i路由距離值為0、1和2的指針別名集置為⊥，得到新的抽象狀態(tài)?如果狀態(tài)?中指針p所指向的內(nèi)存結(jié)點存在且沒有被其他指針變量或堆內(nèi)存中其他內(nèi)存結(jié)點通過某個指針域路由可達，則發(fā)生內(nèi)存泄漏，將該語句s和抽象狀態(tài)?加入到內(nèi)存泄漏隊列heapleakListF中，heapleakListF是保存所有發(fā)生內(nèi)存泄漏的語句和狀態(tài)的隊列，基本元素為：語句和抽象狀態(tài)對?

(2)語句p-＞f_m＝null，轉(zhuǎn)換規(guī)則是：在狀態(tài)?中，指針變量x代表能夠通過某個指針域f_i路由可達p指向內(nèi)存結(jié)點的指針變量；首先，修改x的擴展類型：如果x與p別名，即：x到p的距離為0，則從?中將通過f_i路由距離值為1和2的指針別名集置為空；如果x到p的距離值為1或2，則從?中通過f_i路由距離為2的指針別名集中刪除?中通過f_i路由距離值為1和2的指針別名集；然后，將?中通過f_m路由距離值為1和2的指針別名集置為空，得到新的抽象狀態(tài)?如果狀態(tài)?中p指向內(nèi)存結(jié)點中的f_m指向的內(nèi)存結(jié)點存在且沒有被其他指針變量或其他內(nèi)存結(jié)點通過f_i路由可達，則發(fā)生內(nèi)存泄漏，將語句s和狀態(tài)?加入到內(nèi)存泄漏隊列heapleakListF中；

(3)指針拷貝語句p＝q，轉(zhuǎn)換規(guī)則是：首先，在狀態(tài)?下按照規(guī)則(1)執(zhí)行語句p＝null得到中間抽象狀態(tài)?然后在中間抽象狀態(tài)?下，將?賦值給?即將p?的指向修改為q指向的結(jié)點，得到新的抽象狀態(tài)?如果狀態(tài)?中p指向的內(nèi)存結(jié)點存在且沒有被其他指針變量或堆內(nèi)存中其他內(nèi)存結(jié)點通過某個指針域路由可達，則發(fā)生內(nèi)存泄漏，將語句s和狀態(tài)?加入到內(nèi)存泄漏隊列heapleakListF中；

(4)語句p＝q-＞f_m，轉(zhuǎn)換規(guī)則是：首先，在狀態(tài)?下按照規(guī)則(1)執(zhí)行語句p＝null得到中間抽象狀態(tài)?然后在中間抽象狀態(tài)?下，將?中通過f_m路由距離值為1的指針別名集賦值給與?中通過某個指針域f_i路由距離值為0的指針別名集，將p加入到?中通過f_i路由距離值為1的指針別名集中，得到新的抽象狀態(tài)?如果狀態(tài)?中p指向的內(nèi)存結(jié)點存在且沒有被其他指針變量或堆內(nèi)存中其他內(nèi)存結(jié)點通過某個指針域路由可達，則發(fā)生內(nèi)存泄漏，將語句s和狀態(tài)?加入到內(nèi)存泄漏隊列heapleakListF中；

(5)語句p-＞f_m＝q，轉(zhuǎn)換規(guī)則是：首先，在狀態(tài)?下按照規(guī)則(1)執(zhí)行語句p-＞f_m＝null得到中間抽象狀態(tài)?然后在中間抽象狀態(tài)?下，集合Q表示?中通過某個指針域f_i路由距離為0的指針別名集，指針變量x表示抽象狀態(tài)?中能夠通過f_i一次或多次路由到達p指向的內(nèi)存結(jié)點的指針；按照以下規(guī)則修改中間抽象狀態(tài)?首先，修改集合Q中指針變量y的擴展類型?將?中通過f_i路由距離為0的指針別名集加入到?中通過f_i路由距離為1的指針別名集中，將?中通過f_i路由距離為1和2的指針別名集添加到?中通過f_i路由距離為2的指針別名集中；然后，將通過f_i路由距離q值為0、1和2的指針別名集同q一起添加到?中通過f_i路由距離為2的指針別名集中，得到新的抽象狀態(tài)?如果狀態(tài)?中p指向的內(nèi)存結(jié)點中f_m指向的內(nèi)存結(jié)點存在且沒有被其他指針變量或堆內(nèi)存中其他內(nèi)存結(jié)點通過某個指針域路由可達，則發(fā)生內(nèi)存泄漏，將語句s和狀態(tài)?加入到內(nèi)存泄漏隊列heapleakListF中；

(6)內(nèi)存分配語句p＝malloc()，轉(zhuǎn)換規(guī)則是：首先，在狀態(tài)?下按照規(guī)則(1)執(zhí)行語句p＝null得到中間抽象狀態(tài)?然后在中間抽象狀態(tài)?下，新申請一個內(nèi)存結(jié)點并且將該內(nèi)存結(jié)點的地址賦值給指針p，即：將?中通過某個指針域f_i路由距離?為0的指針別名集置為空集?通過f_i路由距離為1和2的指針別名集置為⊥，得到新的抽象狀態(tài)?如果狀態(tài)?中p指向的內(nèi)存結(jié)點存在且沒有被其他指針變量或堆內(nèi)存中其他內(nèi)存結(jié)點通過某個指針域f_i路由可達，則發(fā)生內(nèi)存泄漏，將語句s和狀態(tài)?加入到內(nèi)存泄漏隊列heapleakListF中；

(7)內(nèi)存釋放語句free(p)，轉(zhuǎn)換規(guī)則是：在狀態(tài)?中，指針變量w表示活指針變量集LivePVar(HP)中除p所有其他指針變量，首先，從?中通過某個指針域f_i路由距離值為0、1和2的指針別名集中刪除?中通過f_i路由距離為0的指針別名集，然后將?中通過f_i路由距離值為0、1和2的指針別名集置為⊥，得到新的抽象狀態(tài)?如果狀態(tài)?中p指向內(nèi)存結(jié)點中某個指針域所指向的內(nèi)存結(jié)點存在沒有被其他指針變量或堆內(nèi)存中其他內(nèi)存結(jié)點通過某個指針域路由所可達，則發(fā)生內(nèi)存泄漏，將語句s和狀態(tài)?加入到內(nèi)存泄漏隊列heapleakListF中；

4.4.2如果語句s為switch條件選擇語句，則：首先在當(dāng)前堆內(nèi)存抽象狀態(tài)?下求解switch語句條件的真值，然后根據(jù)條件真值從Succ(s)中選擇下一條執(zhí)行語句s’，并將s’作為語句s的后繼語句，狀態(tài)?作為新的抽象狀態(tài)?執(zhí)行4.5；

4.4.3如果語句s為無條件跳轉(zhuǎn)語句，則：將目標(biāo)語句s’作為語句s的后繼語句，狀態(tài)?作為新的抽象狀態(tài)?執(zhí)行4.5；

4.4.4如果語句s為函數(shù)調(diào)用語句，則執(zhí)行第5步，得到新的抽象狀態(tài)?從Succ(s)中選擇某個元素s’，作為s的后繼語句；

4.4.5如果語句s是函數(shù)返回語句return?e，則在抽象狀態(tài)?下，將指針變量e的擴展類型作為函數(shù)返回值的擴展類型，全局指針變量的擴展類型不變，其他局部指針變量的擴展類型賦值置空，得到新的抽象狀態(tài)?并作為函數(shù)f的出口狀態(tài)?出口語句s’作為返回語句s的后繼語句，然后執(zhí)行4.5；

4.5將新的抽象狀態(tài)?與后繼語句s’的初始狀態(tài)?通過合并操作Join得到該程序點新的抽象狀態(tài)?執(zhí)行4.6步；合并操作是：當(dāng)且僅當(dāng)任意兩個抽象狀態(tài)?和?存在包括關(guān)系時才能合并，否則兩個抽象狀態(tài)分別作為合并操作的元素；兩個堆內(nèi)存抽象狀態(tài)?和?存在包含關(guān)系?當(dāng)且僅當(dāng)：狀態(tài)?中任意元素在狀態(tài)?中；?合并操作由公式表示為：

4.6將合并后的堆抽象狀態(tài)?采用飽和操作達到飽和狀態(tài)?飽和操作具體步驟如下：

4.6.1將標(biāo)記變量modified初始化為假；

4.6.2反自反操作：遍歷抽象狀態(tài)?中每個指針變量x₁，從?中通過某個指針域f_i路由距離為0的指針別名集中刪除指針x₁，如果某個指針別名集被修改了，將modified置為真；

4.6.3對稱操作：遍歷抽象狀態(tài)?中每個指針變量x₂，從?中通過某個指針域f_i路由距離為0的指針別名集中任意取出某個指針變量y₂，如果?中所有通過f_i路由距離為0的指針別名集不包含x₂，則將x₂加入?中到通過f_i路由距離為0的指針別名集，如果某個指針別名集被修改了，將modified置為真；

4.6.4傳遞操作：遍歷抽象狀態(tài)?中每個指針變量x₃，從?中通過某個指針域f_i路由距離為某個值d₁的指針別名集中任意取出某個指針變量y，在?中通過某個指針域路由距離為某個值d₂得到指針別名集Q₂，如果指針別名集Q₂中某個指針變量z不在?中通過f_i路由距離為d₁+d₂的指針別名集中，則將z加入到?中通過f_i路由距離為d₁+d₂的指針別名集中，如果某個指針別名集被修改了，將modified置為真；

4.6.5判斷modified的值，如果為假，狀態(tài)?達到飽和狀態(tài)?轉(zhuǎn)4.7步；否則轉(zhuǎn)4.6.1步；

4.7如果飽和狀態(tài)?與原始狀態(tài)?不同，則將飽和狀態(tài)?作為新的原始狀態(tài)?并且將飽和狀態(tài)?和后繼語句s’加入到W中，轉(zhuǎn)4.3；

第5步，對堆操作程序進行過程間的內(nèi)存泄漏檢測，方法是：

5.1獲取過程調(diào)用語句e＝f(e₁，e₂，...，e_k)的初始化信息，被調(diào)用過程名為：f，形式參數(shù)為：p₁，p₂，...，p_k，實際參數(shù)為：e₁，e₂，...，e_k，其中：p_h代表形式參數(shù)，e_h為p_h相對?應(yīng)的實際參數(shù)，1≤h≤k，返回值為：ret_f，局部指針變量集為：LVar_f，全局指針變量集為：GVar_f，執(zhí)行函數(shù)調(diào)用語句前的堆內(nèi)存抽象狀態(tài)為?

5.2在堆內(nèi)存抽象狀態(tài)?下執(zhí)行調(diào)用語句的狀態(tài)遷移，得到被調(diào)用函數(shù)的堆內(nèi)存初始狀態(tài)?過程如下：

5.2.1將狀態(tài)?中全局指針變量集GVar_f中任意全局指針變量g的擴展類型傳遞給被調(diào)用過程，即：狀態(tài)?中g(shù)的?等于狀態(tài)?中g(shù)的?

5.2.2將狀態(tài)?中實際參數(shù)eh的?傳遞給形式參數(shù)p_h，作為被調(diào)用入口處p_h的?即：狀態(tài)?中?的值為狀態(tài)?中?的值；

5.2.3狀態(tài)?中局部指針變量集LVar_f中的任意局部指針變量l的擴展類型?初始化為空；

5.3將函數(shù)f和初始狀態(tài)?作為參數(shù)，采用第4步前向數(shù)據(jù)流迭代方法對函數(shù)f進行過程內(nèi)內(nèi)存泄漏檢測，得到函數(shù)出口處堆內(nèi)存新的抽象狀態(tài)?

5.4將堆內(nèi)存狀態(tài)?傳遞給調(diào)用過程，得到新的抽象狀態(tài)?按照如下步驟：

5.4.1將狀態(tài)?中指針類型返回值ret_f的擴展類型傳遞給調(diào)用過程，作為狀態(tài)?下指針e的擴展類型；

5.4.2狀態(tài)?中全局指針變量g的擴展類型?傳遞給調(diào)用過程時不變，作為狀態(tài)?下g的?

5.4.3其他局部指針變量的擴展類型在過程調(diào)用前后不變，即：狀態(tài)?中其他局部指針變量的擴展類型的值為狀態(tài)?中的相應(yīng)局部指針變量擴展類型的值；

第6步，統(tǒng)計堆操作程序內(nèi)存泄漏檢測結(jié)果數(shù)據(jù)：

6.1根據(jù)控制流圖上各個程序點中關(guān)于堆內(nèi)存抽象狀態(tài)的信息，輸出各個程序點的入口語句的堆內(nèi)存抽象狀態(tài)和出口處的堆內(nèi)存抽象狀態(tài)；

6.2根據(jù)內(nèi)存泄漏隊列heapleakListF的內(nèi)容，輸出所有可能發(fā)生內(nèi)存泄漏的程序語句s和狀態(tài)?并統(tǒng)計內(nèi)存泄漏的數(shù)目；

6.3篩選可能的內(nèi)存泄漏錯誤，統(tǒng)計出檢測的誤報數(shù)，并得到誤報率；?

6.4根據(jù)編譯平臺和系統(tǒng)運行時信息，得到內(nèi)存泄漏檢測方法消耗系統(tǒng)資源的情況。