一種內存錯誤的動態檢測方法

摘要：提出了一種內存錯誤的動態檢測方法，通過統一的內存錯誤檢測模型和接口，使內存錯誤檢測處理過程規范化，便于擴展。實驗表明，該方法可以方便地進行擴展，以增加內存錯誤的檢測能力。

關鍵詞：內存錯誤檢測；動態檢測；檢測擴展

中圖分類號：TP302文獻標志碼：A

文章編號：1001-3695(2008)05-1550-03

0引言

C/C++等語言的動態內存機制為程序設計提供了靈活和方便。但C/C++語言及其支持庫本質上是不安全的，動態內存的手工分配和管理，極易在程序中引入內存錯誤。在使用動態內存的軟件系統中，50％的軟件故障與內存的管理有關[1]。動態內存的相關錯誤有內存泄漏、內存的重復釋放、空指針引用、越界訪問和類型錯誤等[1~3]。這些錯誤會導致系統失效甚至崩潰，從而降低了系統運行過程中的可靠性。盡管這些錯誤在程序中普遍存在，但是采用傳統的白盒測試和黑盒測試都很難發現這些錯誤。

檢測內存錯誤的方法主要分為兩類，即動態方法和靜態方法。動態方法需要在程序運行過程中進行潛在錯誤的檢測。例如，Purify[4]、Lackey可以檢測程序中存在的內存泄漏問題;Memcheck主要能發現未定義值的錯誤[5]；Annelid可以發現越界訪問錯誤；Safe－c[6]和shadow processing[7]主要檢測某一類特定的錯誤；Redux是一個可視化的內存錯誤發現工具，其檢測錯誤的能力也有限。目前動態檢測方法通常只能檢測某（些）類內存錯誤，不容易進行擴展以檢測更多類型的內存錯誤。靜態方法[8，9]通過對程序結構的分析來檢測程序中隱藏的動態內存錯誤。例如，Lint、Splint等通過在源程序中添加注釋語句來檢測程序中潛在的內存錯誤，其檢錯效果與應用程序注釋工作量有關，即人工干預的工作量大，經常給出誤報。

目前，內存錯誤的檢測方法處理內存錯誤類型較為單一，未能有效利用內存使用信息，缺乏動態擴展能力。本文提出了一種內存錯誤的動態檢測方法，該方法利用了語言級信息，較為全面地獲取程序對內存使用的信息；利用擴展接口，可以方便地增加檢測多種類型內存錯誤的功能。

1體系結構描述

1．1系統總體結構

本方法通過設計擴展接口和利用語言級元數據，來解決現有方法存在的問題，建立解決多種類型內存錯誤的統一系統結構。通過擴展接口，將檢測特定內存錯誤的功能做成一個擴展模塊，可以在系統運行時動態加載，即檢測某類特定的內存錯誤時，需要加載相應的擴展模塊。通過擴展接口可以設置檢測規則以確定檢測任務，系統根據檢測規則定義進行相應的錯誤檢測。在系統運行時，根據檢測規則設置確定檢測內容，加載相應的檢測模塊。解析元數據模塊從二進制文件中解析出變量和函數等元數據，以獲取程序對內存的使用信息。利用這些元數據，系統可以根據檢測規則進行相應的檢測。這樣，通過擴展接口實現相應的擴展模塊，就可以達到統一解決多種類型內存錯誤的目的。動態檢測如圖1所示。

通過配置檢測規則和相應的擴展模塊，系統可以用來檢測多種類型的內存錯誤。目前已經配置了一個默認的擴展模塊，可以用來檢測越界訪問和內存泄漏等類型的內存錯誤。

系統工作時，程序載入模塊將二進制文件載入系統，等待運行；然后，元數據解析模塊解析二進制文件，獲得元數據，過濾器根據檢測規則和元數據生成相應的檢測點和需要檢測的內存錯誤；最后，由改寫模塊根據檢測規則動態地加載相應的擴展模塊。在這些準備工作完成后，由改寫模塊通知插入模塊和檢測翻譯模塊準備完成；檢測翻譯模塊啟動程序，并負責監控其運行。在檢測點處，檢測翻譯模塊通過插入模塊和改寫模塊調用相應的擴展模塊，擴展模塊負責在插入點處，插入檢測代碼；然后，再將程序的運行交給檢測翻譯模塊控制。利用插入代碼在檢測點處進行內存錯誤的檢測，在錯誤發生時，由檢測翻譯模塊生成相應的錯誤類型，并給出錯誤報告。

以下分別給出元數據、檢測規則和過濾器的描述。

1．2檢測規則定義

在檢測時，不需要對所有變量和函數都進行檢測，只需要對某些特定的變量和函數進行檢測。為了減輕系統的負擔，同時也能夠增加系統的擴展性，定義了如下的檢測規則。

定義1檢測對象(object)是指在程序運行過程中，要檢測的對象。一般指程序中的變量，是變量元數據中的部分信息。

變量元數據主要包含如下一些信息：變量名、類型、占內存大小、是否靜態和是否全局變量。變量名用來標志需要具體檢測的內存地址，其他信息可以用來檢測內存相關錯誤。

定義2檢測點(point)是指在程序運行過程中需要檢測的點。一般是在函數的入口(function－entrance)和退出點(function－exit)，通常是函數元數據的部分信息。

函數元數據主要包括如下信息：函數名、函數類型、函數參數、返回值信息和局部變量信息；函數類型用來標志函數是否靜態的或是全局的函數；函數參數主要記錄了參數的個數、參數的類型和參數的大小等信息；返回值信息主要記錄了函數返回值的類型和大小信息；局部變量信息記錄了在函數內部聲明的局部變量信息。

定義3元數據主要是指變量元數據和函數元數據。

定義4檢測屬性(property)是指在程序運行中，對檢測對象進行檢測的屬性。檢測屬性有對象的值(object－value)、對象的類型(object－type)和對象占用內存的大小(object－size)等。

定義5檢測規則（rule）。一條檢測規則中，至少有一個檢測對象、一個檢測屬性和一個檢測點，以及檢測時使用的擴展模塊。

rule::=〈object[property]，point[function_name]， extend_module〉

擴展模塊是與監檢測性密切相關的，檢測什么樣的屬性就要加載與之對應的擴展模塊。規則中如果沒有指定使用的擴展模塊，則系統使用默認的擴展模塊。

定義6檢測器（monitor）包括檢測規則的配置，monitor={rulei，i=1，…，n}。

1．3過濾器描述

過濾器是實現按照檢測規則進行監測的主要模塊之一。利用過濾器達到只檢測某些特定元數據的目的。

在本文中，把目標程序的執行抽象成有序的執行狀態的序列。執行狀態主要由變量與值的映射以及映射發生的時間戳構成。

2實現技術

本方法實現上有解析元數據、過濾器的設計以及改寫和插入模塊等技術要點。

解析元數據是一件繁瑣的事。解析一個函數元數據，首先從elf header中找到program header，再尋找到 symbol section，最后解析出函數元數據。變量元數據的解析也與此類似。在解釋過程中將變量元數據和相應的函數元數據組織在一起，按照一定的樹型結構存儲起來。解析元數據模塊主要借鑒了GNU Binutils包內的ELF文件分析工具Readelf。根據Readelf的工作原理設計實現了解析元數據模塊。

過濾器的設計難點是效率問題。首先把組織成樹型結構的元數據，按照哈希表的方式重新組織起來，然后利用哈希函數提高元數據的查找速度，進而提高了過濾器的效率。根據檢測規則構建變量的抽象隊列和值的抽象隊列，從元數據樹型結構的根節點開始，根據檢測規則按照過濾器的要求，利用哈希函數在樹型結構中查找需要的檢測點，將需要的檢測點加入到相應的隊列中。

改寫和插入模塊對所有的檢測屬性在內存中保留一個副本。在程序運行時，對檢測屬性的任何操作，也必須同步地對副本進行相應的操作。當程序執行到達一個檢測點時，將檢測屬性與其副本作比較，如果不一致，則說明有錯誤發生。改寫和插入模塊的實現借鑒了Memcheck的部分功能，并進行了相應的擴充，使之可以使用元數據和支持擴展接口以發現多種類型的內存錯誤。

為了進行動態的插入代碼和檢測，就必須有能夠控制目標程序運行的底層機制。Valgrind是一個二進制代碼分析的框架，支持動態的修改程序。在實現上利用Valgrind的功能，為本系統提供底層的支持。

3可擴展性分析

本方法具有較好的可擴展性，可以方便地擴展系統來處理新的內存錯誤。只需要編寫一個監控規則文件和一個相應的擴展模塊，就可以很方便地用來檢查一類新的內存錯誤。例如，有如下一段程序：

char badfunction(int a， int b，char *str) 

{

char buffer[16];

int retVal;

retVal=a>b?a:b;

strcpy(buffer，str);

return retVal;

}

函數中有可能存在字符串溢出的錯誤。在發生溢出的情況下，有可能會覆蓋掉函數的返回值。可以編寫如下檢測規則和相應的擴增模塊，檢測函數中的內存錯誤。

Rule1:=〈buffer[size]，Function entrance[badfunction]，Extend Module〉

Rule2:=〈retVal [value]，Function exit[badfunction]，Extend Mo-dule〉

Rule1用來檢測字符串溢出的錯誤；Rule2用來檢測函數的返回值是否正確。在extend module中實現帶有檢查溢出功能的strcpy函數。Extend module中的strcpy必須在完成正常工作時，記錄下源字符串和目的字符串的大小。按照如下算法判斷是否發生溢出；如果源字符開始地址小于目的字符串的開始地址，此時在源字符串結束地址大于目的字符串的開始地址時，發生溢出。如果目的字符串的開始地址小于源字符串的開始地址，此時在目的字符串的結束地址大于源字符串的開始地址時，發生溢出。根據檢測規則，動態的加載extend module，在檢測點處動態的替換strcpy函數，在執行到strcpy時就可以利用帶檢測功能的strcpy函數進行溢出檢測。過濾器根據Rule2在可能改變retVal值的地方和檢測規則規定的地方進行檢測。

目前已經實現了一個擴展模塊，可以用來檢測常見的內存錯誤，如內存泄漏、未使用未初始化、未分配的內存和數組越界等。對于這些類型的內存錯誤，不需要再編寫相應的擴展模塊。對于其他類型的錯誤，可以編寫相應的檢測規則和對應的擴展模塊。

為了測試性能，在top、sniffer－0.5和MD5程序中分別注入了三種類型的內存錯誤，然后分別利用Memcheck和本方法進行測試。測試結果：Memcheck只能發現其中的一種類型的內存錯誤，而本方法可以成功檢測三類錯誤;同時，與Memcheck相比，本方法的CPU和內存使用率增長不大（約5%）。

4結束語

目前本方法在尋找檢測對象和檢測規則的書寫方面還需要一定的手工干預。下一步工作是充分利用靜態信息確定需要檢測的對象，實現檢測規則的自動生成。同時，對本方法進行相應的擴展，使其使用更加靈活方便。

參考文獻：

[1]LEE W H，CHANG M，HASAN Y.A dynamic memory measuring tool for C++ programs[C]//Proc of the 3rd IEEE on Application－Speci-fic Systems and Engineering Technology.Washington DC:IEEE Compter Society，2000:155－163.

［2］AUSTIN T M，BREACH S E，SOHI G S.Efficient detection of all pointer and array errors[J].ACM SIGPLAN Notices，1994，29(6):290-301.

[3]HEINE D L，LAM M S.A practical flow sensitive and context sensitive C and C++ memory leak detector[J].ACM SIGPLAN Notices，2003，38(5):168－181.

[4]HASTING R，JOYCE B.Purify: Fast detection of memory leaks and access errors[C]//Proc of Winter Usenix Conference.San Francisco， California:[s.n.]，1992：125－136.

[5]SEWARD J，NETHERCOTE N.Using Valgrind to detect undefined value errors with bit－precision[C]//Proc of USENIX’05 Annual Technical Conference.Anaheim， California:USENIX Association Berkeley，2005:2.

[6]AUSTIN T，BREACH S，SOHI G.Efficient detection of all pointer and array access errors[C]//Proc of ACM SIGPALN’94 Conference on Programming Language Design and Implementation.1994:290-301.

[7]PATIL H，FISCHER C.Low－cost， concurrent checking of pointer and array accesses in C programs[J].Software Practice and Expe-rience，1997，27(27):87－110.

[8]HALLEM S，CHELF B，XIE Y，et al.A system and language for buil-ding system－specific， static analyses[J].ACM SIGPALN Notices，2002，37(5):69-82.

[9]BUSH W R，PINCUS J D，SIELAFF D J.A static analyzer for finding dynamic programming errors[J].Software Practice and Expe-rience，2000，30(7):775-802.

[10]GATES A Q，TELLER P J.A Integrated design of a dynamic software－fault monitoring system[J].Journal of Integrated Design Process Science，2000，14(3):63-78.

[11]NETHERCOTE N.Dynamic binary analysis and instrumentation or building tools is easy[D].Cambridge:Trinity College， University of Cambridge，2004.

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