[發明專利]一種基于控制流圖的內存泄漏自動修復方法

在審

• 申請號: 201310728361.3
• 申請日: 2013-12-26
• 公開（公告）號: CN104750563A
• 公開（公告）日: 2015-07-01
• 發明（設計）人: 高慶;熊英飛;張路;謝冰;梅宏
• 申請（專利權）人: 北京大學
• 主分類號: G06F11/07
• 分類號: G06F11/07
• 代理公司: 北京萬象新悅知識產權代理事務所(普通合伙) 11360
• 代理人: 朱紅濤

技術領域

本發明涉及基于控制流圖的技術，具體為一種能夠自動修復C語言內存泄漏的錯誤的方法，屬于軟件測試領域。

背景技術

（一）錯誤修復相關技術

近年來有很多關于錯誤修復的研究。例如，一些研究人員^[1,2,3]試圖利用一些方法自動修復一般類型的錯誤。所使用的方法通常使用所違反的正確條件，修改代碼以滿足這些條件。該正確條件來源于測試用例^[2,3]，或諸如前置條件和后置條件的斷言^[1]。在所述正確條件被說明后，通常使用演化算法來給出修復。例如，在Arcuri和Yao的工作^[2]中，計算機程序和測試用例同時演化，并相互影響。Weimer等人^[3]使用遺傳算法的一種擴展形式來演化程序變體。另外，Weiet等人^[1]在狀態圖中基于類的布爾查詢來使用狀態的抽象表示。以上這些技術使用的正確條件通常是不適當的，并且很少保證正確性。另外，說明修復內存泄漏的正確條件（如測試用例或斷言）也是困難的。

還存在一些修復特定類型錯誤的方法。例如，Jin等人^[4,5]的方法自動修復多種并發性錯誤。這些方法中沒有關于內存泄漏的修復。

修復可能是不好的，并引入新的錯誤。Gu等人^[6]形式化了不佳修復的問題，并且定義了修復的兩個維度。“覆蓋”維度衡量了正確修復所有錯誤的廣度，而“破壞”維度衡量修復后的計算機程序與原有行為的偏差。在本發明中，我們能夠確保修復的正確性，也就是避免了“破壞”這個維度，同時盡可能提高“覆蓋”維度。

（二）內存泄漏相關技術

有靜態和動態兩種方法來處理內存泄漏。靜態方法主要用于內存泄漏的檢測^{[7,8,9,10,11,12,13]}。大多數檢測算法只報告內存泄漏發生的位置。因為在大多數情況下，分配內存和發生內存泄漏的位置分布在完全不同的位置，開發人員要進行修復仍然需要很多工作。即便在Fastcheck^[10]中，它給出了內存分配的泄漏路徑，這個信息仍然不足以提供修復。而且，所有這些方法都有假陽性錯誤，這讓開發人員很難依賴這些方法來自動修復內存泄漏。

另外一種處理內存泄漏的靜態方法是關于Java的內存管理^[14,15,16]。這些方法在Java字節碼中插入專門的釋放語句，以減少需要被垃圾回收器掃描的引用的數量并提高運行時性能。這些方法與本發明有相似之處，即通過靜態分析插入釋放語句。但是，很難把這些方法應用于C語言。這是因為，首先，在C語言中，必須保證沒有雙重釋放，而在Java中不存在這個問題。而且，不能僅僅通過在這些技術中增加功能來解決雙重釋放的問題，因為雙重釋放與搜索策略緊密相關，必須重新設計算法。其次，現有技術都是直接修改Java字節碼，而在C語言中必須修改源代碼，因而可讀性是一個重要的方面。因此，現有工作中的很多技術不能被使用。例如，頻繁地插入臨時變量在源代碼級別是不能被接受的。最后，Java有垃圾回收器，任何未被釋放的內存可以被其安全回收。而在C語言中，每個錯誤都是潛在重要的錯誤，而且報告是否完全修復是重要的。上述技術都沒有提供這些功能。

處理內存泄漏使用最廣泛的動態方法是垃圾回收機制^{[17,18,19,20]}，它給運行時帶來開銷。也有動態檢測內存泄漏的方法^{[21,22,23,24,25,26]}，它提供了在運行時泄漏的內存分配的位置。然而，類似于靜態檢測技術，這些技術都無法提供幫助快速修復的有用信息。

一些研究人員意識到修復內存泄漏的重要性，并嘗試從多個方面解決這個問題。LEAKPOINT^[27]試圖提供幫助定位修復位置的信息，該信息不僅報告內存分配的位置，它也報告內存引用丟失的位置或被最后一次使用的位置。然而，修復泄漏需要考慮所有路徑，這個信息并不足以保證自動生成修復。Rayside和Mendel^[28]使用對象所有權的分析來尋找和修復垃圾（內存被引用但從未被使用）。但是，正像名稱所指出的，這個技術只能給出統計報告，并不是自動修復。Xu等人^[29]提出了使用三個不同等級的知識來幫助不了解計算機程序的開發人員快速發現錯誤的根源。這份工作也不能自動修復內存泄漏。上述方法均依賴動態分析，引入了運行時開銷。