基于指針分析的內存泄露故障測試方法研究

摘 要：提出了一種新的指針分析方法，通過靜態分析程序中指針的映射關系來檢測內存泄漏故障；給出了指針映射代數系統的概念，在此基礎上分析了如何構造指針映射集，并詳細敘述了測試步驟；最后通過實例分析了該方法的應用效果，討論了需要進一步解決的問題。該方法還考慮了控制流圖和路徑條件，提高了測試結果的精度。

關鍵詞：內存泄漏； 軟件測試； 指針分析

中圖法分類號：TP302．8 文獻標識碼：A 文章編號：1001-3695(2006)10-0022-03

Research on Memory Leak Faults Testing Method Based on Pointer Analysis

ZHANG Wei，LU Qingling，LI Mei，GONG Yunzhan

(Dept. of Information Engineering， Academy of Armored Force Engineering， Beijing 100072， China)

Abstract:A new pointer analysis method is put forward which detects memory leak faults of software by analyzing static relationship of pointer mapping. The notion of pointer mapping algebraic system is proposed. On the basis of this， it analyzes how to construct pointer mapping sets and describes the detailed testing steps. At last， it brings forth the application effects through example and shows the problems need to be solved next step. This method takes into account the control flow graph and path condition， so it can increase the precision of result.

Key words： Memory Leak; Software Test; Pointer Analysis

許多重要的編程語言均通過指針操作來支持動態內存管理，以提高語言的表達能力，但擁有指針的編程語言也會引起大量的內存故障。檢測內存故障是非常困難的，也難以準確識別出程序中的故障源[1]。軟件中的內存泄漏故障通常會引起嚴重問題，它們會逐漸消耗內存資源，在程序長時間運行時更為嚴重。其表現就是應用程序運行速度變慢，嚴重時可能因沒有足夠的內存而崩潰。需要注意的是，內存泄漏故障不能由程序中的后續操作排除。

本文提出的方法基于指針分析，指針分析屬于靜態技術，通過分析源代碼發現程序運行時可能產生的故障。與運行時檢測相比，通過指針分析檢測，其內存故障代價要小得多。一些研究人員已經對指針分析技術進行了研究[2~4]，其基本思路就是開發特定的算法來檢測特定的內存問題（如空指針引用、內存泄漏、數組越界等）。這些算法不需要執行程序，也不需要借助程序注釋和程序文檔，其不足之處主要在于控制流模型不夠精確。

1 指針分析

1．1 指針映射代數系統

定義1 令S表示靜態變量的集合，V表示指針的集合，H表示所有堆地址的集合，Φ表示特殊地址單元NULL，則廣義指針映射集定義為(V∪Φ)×(H∪S∪Φ)={|x∈(V∪Φ)∧y∈(H∪S∪Φ)}，記作Ψ。

定義2 廣義指針映射集Ψ及定義在該集合上的運算△、☆和⊙稱為指針映射代數系統，記作<Ψ，△，☆，⊙>。其中運算定義如下：

△為動態分配運算，△<Φ，z>=，其中x∈V，y∈(H∪S∪Φ)， z∈H且x≠Φ。

☆為賦值運算，☆=，其中x1∈V，x2∈V，y1∈(H∪S∪Φ)，y2∈(H∪S∪Φ)且x1≠Φ。

⊙為釋放運算，⊙=，其中x∈V，y∈H且x≠Φ。

從定義1、定義2可以看出：

（1）指針只能指向靜態變量、堆地址單元或特殊地址單元Φ。

（2）△運算指調用內存分配函數的操作，C++程序設計語言提供的內存分配函數有new，strdup，malloc，calloc，realloc等。該運算實際上是將分配操作與賦值操作組合在一起，因為單純的分配操作沒有任何意義。例如，p=malloc(sizeof(int))可描述為△<Φ，z>，z即為動態分配的堆地址單元，運算結果為。

（3）☆運算即指針的賦值操作，改變指針所指向的內容。

（4）⊙運算是單目運算符，運算的結果是回收堆地址單元，并使指針指向特殊地址單元Φ。

性質1 指針映射代數系統<Ψ，△，☆，⊙>是封閉的。

性質2 指針映射代數系統<Ψ，△，☆，⊙>是不可交換的。

1．2 指針映射集

定義3 動態反映程序中指針映射關系的集合稱為指針映射集，記作T，TΨ。

指針映射集T是廣義指針映射集Ψ的子集，是在分析程序語句的過程中動態生成的，它反映了程序中的指針與內存地址之間的映射關系。本文通過指針映射集T來分析內存泄漏故障。

定義4 對指針映射集T進行操作的函數定義如下：

（1）Add()。添加元素到指針映射集T中，其中p∈V，h(i)∈H，由于檢測內存泄漏故障只需知道分配了一個存儲單元即可，而不必考慮該單元的具體地址，因此i的作用只在于區分不同的堆地址單元，可設置為一個遞增變量。

（2）Change(，)。將變換為，其中p1∈V，h(i)∈H，h(j)∈H。

（3）Delete()。從指針映射集T中刪除元素，其中p∈V，h(i)∈H。

（4）Get(p)。從指針映射集T中取p所指向的堆地址，其中p∈V。

2 測試算法

2．1 故障模型

指針映射集T的構造過程如下：

（1）初始值為空。

（2）內存分配操作。C++程序設計語言提供了幾個分配內存的函數，如new，strdup，malloc，calloc，realloc等，這里用new表示。令p∈V，h(i)∈H，如果p=new(h(i))，則Add()。

（3）內存釋放操作。C++程序設計語言提供了free，delete等內存釋放函數，這里用free表示。令∈T，如果free(p)，則Delete()。

（4）指針賦值操作。令p∈V，q∈V，如果p=q，則

①h(j)=Get(q)；

②如果∈T且h(i)≠h(j)，則Change(，<Φ，h(i)>)；

③Add()。

令p∈V，q∈V，如果p.link=q，則

①h(i)=Get(p)；h(j)=Get(q)；

②如果∈T且h(i)≠h(k)，則Change(，<Φ，h(k)>)；

③Add()。

（5）函數返回操作。函數返回包括函數正常結束或中間出現的Return語句，此時局部指針變量失效。

令p∈V，h(i)∈H，如果p失效且∈T，則Change(，<Φ，h(i)>)。通過構造的指針映射集T，可得內存泄漏故障模型。

在程序中Si點，當前指針映射集為T(Si)，如果<Φ，h(i)>∈T(Si)，h∈H，則在Si點存在內存泄漏故障FML。記作

<Φ，h(i)>∈T(Si)FML

根據指針映射集構造規則，<Φ，h(i)>∈T(Si)，則一定有動態分配操作，且沒有釋放操作，左變元為Φ，說明沒有指針指向堆地址單元h(i)，因此存在FML故障。

2．2 測試步驟

（1）預編譯。由于源程序中存在宏定義、文件包含和條件編譯等預處理命令，因此在進行詞法分析前必須進行預處理，將宏進行展開，這樣有利于變量的查找。

（2）詞法分析。將預編譯階段產生的中間代碼進行分解，形成各種符號表，為語法分析作準備。符號表的結構主要有標識符表、類型表、關鍵字表、常數表、運算符表和分界符表。

（3）語法分析。將輸入字符串識別為單詞符號流，并按照標準的C++語法規則對源程序作進一步分析，區分出變量定義、賦值語句、函數等。語法分析的結果是生成語法樹，并提供對外的接口。此外，通過語法樹可以生成程序的控制流圖和變量的定義使用鏈，為下一步的故障查找作準備。

（4）取控制流圖中的一條路徑。

（5）路徑中的各個節點，如果是與指針相關的操作，則修改指針映射集T。

（6）在路徑結束點檢測指針映射集T，如果<Φ，h(i)>∈T，則存在內存泄漏故障。

（7）返回步驟（4）直到所有路徑檢測完畢。

3 實例和結果分析

下面通過一個實際程序來分析一下測試過程，程序代碼如下：

s1 p=malloc(sizeof(int));

s2 q= malloc(sizeof(int));

s3 if (x=0)

s4 return;

s5 if (x=1)

s6 {p=x;

s7free(p);

s8free(q);

s9return; }

s10 free(p);

s11 free(q);

程序控制流圖如圖1所示。該程序有三條路徑L1，L2和L3，在各條路徑中，T的變化情況如下：

L1

s1 {}

s2 {，}

s12{<Φ，h(0)>，<Φ，h(1)>}

L2

s1 {}

s2 {，}

s6 {<Φ，h(0)>，，}

s7 {<Φ，h(0)>，}

s8 {<Φ，h(0)> }

L3

s1 {}

s2 {，}

s10{ }

s11{ }

從指針映射集T的變化可以看出，在路徑L1結束時，存在兩個序偶，且左操作數為Φ，因此有兩個內存泄漏故障。類似地，路徑L2存在一個內存泄漏故障，雖然在語句s7中有free(p)操作，但指針p的指向已經發生了變化，free(p)操作本身就是不正確的。路徑L3不存在內存泄漏故障。

采用本文所述的方法，對一個八萬行左右(不包括注釋)的C項目進行檢查，找出了86個檢查點(IP)，經人工確認，其中有26個故障；而Reasoning公司的同類測試工具找出了32個IP， 經人工確認，其中有10個故障。測試結果比較如表1所示。

表1 測試結果比較

比較IP故障誤報不定準確率本文所述方法8626283230.2%Reasoning工具321071531.2%從表1可以看出，兩者IP準確率非常接近，但采用本文所述方法找出的26個故障包含了Reasoning公司工具找出的10個故障，這說明漏報率較低。

4 結束語

本文提出了一種新的內存泄漏故障測試方法，該方法基于指針映射關系分析。通過構造指針映射集，建立了內存泄漏故障模型，并按照故障模型給出了測試算法。該算法可以自動檢測內存泄露故障，提高了測試效率。在分析過程中，還綜合應用了控制流圖和路徑條件，提高了測試結果的精度。下一步研究的主要目標是根據程序中的各種語法現象，擴展指針映射集的構造規則，以減少誤報率。此外，該方法目前只用于處理內存泄漏故障，如何應用于其他故障的檢測還有待進一步研究。

參考文獻：

［1］R Hastings， B Joyce. Purify： Fast Detection of Memory Leaks and Access Errors[C]. Proceedings of the Winter USENIX Conference， 1999. 125136.

［2］M Sagiv， T Reps， R Wilhelm. Solving Shapeanalysis Problems in Language with Destructive Updating[C].Florida:Symposium on Principles of Programming Languages， 1996.110118.

［3］W Landi， B G Ryder. Safe Approximate Algorithm for Interprocedural Pointer Aliasing[C]. ACM SIGPLAN Notices， 1992.235-248.

［4］R P Wilson， M S Lam. Efficient Contextsensitive Pointer Analysis for C Program[C]. California: Proceedings of the ACM SIGPLAN’95 Conference on Programming Language Design and Implementation(PLDI)， 1995.18-21.

［5］P Fradet， R Caugne， D L Metayer. Static Detection of Pointer Errors： An Axiomatisation and a Checking Algorithm[A]. H R Nielson. Programming Languages and Systems[C]. The 6th European Symposium on Programming， volume 1058 of LNCS， 1996.125-140.

［6］R Ghiya， L Hendren. Putting Pointer Analysis to Work[C]. Symposium on Principles of Programming Languages， 1998.45-53.

［7］Bernhard Scholz， Johann Blieberger， Thomas Fahringer. Symbolic Pointer Analysis for Detecting Memory Leaks[C]. ACM SIGPLAN Notices， 1999.104-113.

［8］M Emami， R Ghiya， L J Hendren. Contextsensitive Interprocedural Pointsto Analysis in the Presence of Function Pointers[C]. ACM SIGPLAN Notices， 1994.242-256.

［9］W R Bush， J D Pincus， D J Sielaff. A Static Analyzer for Finding Dynamic Programming Errors[J]. SoftwarePracticeand Experience， 2000， 30(7):775-802.

作者簡介：

張威(1968-)，男，副教授，博士研究生，主要研究方向為軟件工程和軟件測試；盧慶齡(1969-)，女，副教授，博士研究生，主要研究方向為軟件工程和人工智能；李梅(1969-)，女，碩士，主要研究方向為電信網絡管理、信息系統可靠性；宮云戰(1962-)，男，博導，主要研究方向為軟件工程、軟件測試和容錯技術。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文