張華強1，喻勝2，王繼剛1，閻波3

　?。?. 中興通訊成都研究所，四川 成都 610041； 2. 四川精藝防偽科技有限公司，四川 成都 610041；3. 電子科技大學 通信與信息工程學院，四川 成都 611731）

　　摘要：內存相關程序錯誤的自動檢測技術能夠幫助程序員盡早發現程序中的內存相關錯誤，從而提高軟件開發效率，增強軟件運行的可靠性。探討了采用前沿的動態二進制分析技術檢測軟件中與內存相關錯誤，為程序員定位錯誤位置、查找錯誤、消除錯誤原因提供準確的信息的方法，為致力于內存程序錯誤檢測技術的研究人員提供參考。在C/C++軟件中的內存錯誤檢測實例驗證了本文方法的有效性。

　　關鍵詞：內存自檢；影子內存；靜態源碼分析；動態二進制分析

0引言

　　軟件開發過程中，與內存相關的程序錯誤(BUG)造成程序不能正常工作的情況非常多。通常都采用程序員手工檢查方式消除這類錯誤。然而，程序員手工檢查方式既低效又不完備，而且與程序員的業務能力相關。因此，與內存相關的BUG在軟件開發過程中對項目開發的影響非常大。

　　近年來，內存相關BUG的自動檢測技術有了很大的發展，可以幫助程序員盡早發現程序中的內存相關BUG，從而提高軟件開發效率，增強軟件運行的可靠性［12］。這類工具主要檢測軟件中與內存相關BUG，為程序員定位BUG位置、查找BUG、消除BUG原因提供準確的信息。

　　當前在內存自動檢測的所有方法中，根據分析的時機可以分類為靜態分析和動態分析方法。這一分類方法的分界點為程序執行，在程序執行前分析稱為靜態分析，在程序執行中分析為動態分析［34］。另一方面，根據分析操作的對象又可分為源代碼分析和二進制目標代碼分析［5］。其中，靜態分析方法更復雜，由于要分析所有的執行路徑而更完備。靜態分析的最大問題是誤報太多；而動態分析方法簡單一些，通常只分析單一的執行路徑。由于動態分析方法在分析時各個變量采用的是程序的真實運行值，因此，檢查精度更高一些，誤報相對少得多。同時，源代碼分析與二進制分析方法也是互補的，源代碼分析依賴于目標程序的編程語言而與平臺（處理器體系結構、操作系統）獨立，在分析過程中可以得到程序的高級信息，例如可以定位錯誤到具體的源代碼行。二進制分析方法剛好相反，是依賴于目標程序的平臺而獨立于編程語言，在分析過程中可以操縱程序的低級信息，例如控制寄存器的分配等。二進制分析的最大好處是分析第三方庫時，可以不需要第三方庫的源代碼就能分析，而源代碼分析對此就無能為力了。

　　本文重點討論通過動態二進制分析技術實現內存自動檢測的相關技術和具體實現，研究了如何利用動態插入內存檢測技術的二進制級別的內存自動檢測方法，使程序員能夠更方便地實現內存相關BUG的自動檢測實現。

1主要內存相關軟件錯誤

　　本文討論的軟件開發過程中主要的內存相關的軟件錯誤包括以下9種：

　　(1)空指針：程序訪問變量的內存地址為0。

　　(2)內存釋放：包括釋放已釋放存儲（Free Freed Memory, FFM）、釋放未分配存儲（Freeing unallocated memory, FUM）、釋放地址不匹配（Freeing Mismatched Memory，FMM）、已釋放存儲區訪問(Freed Memory Access, FMA)，指程序讀、寫的存儲空間已在以前釋放了，該問題也稱為指針懸掛（dangling pointer）或者野指針。

　　(3)越界訪問：如果指向某個存儲區的指針在進行指針算術、類型轉換、賦值操作時，該指針指向另外的存儲區，造成操作的操作數發生錯誤。

　　(4)未初始化存儲：沒有進行初始化操作，其他的內容是隨機的。因此，讀未初始化存儲區中的數據是無意義的，常常引起程序的異常行為。

　　(5)內存泄漏:如果程序不停地向系統申請存儲空間，最終將耗盡進程的虛擬地址空間，內存泄漏通常都是分配了動態存儲區，而程序沒有釋放所致。

　　(6)存儲區重疊操作：兩個不同的指針指向的內存區出現了部分或者全部重疊,在多線程訪問操作時會出現數據不一致的錯誤。

　　(7)系統調用參數錯誤：操作系統內部需要做參數檢測，防止應用程序提供錯誤的參數，從而引起系統的崩潰。

　　(8)存儲操作匹配:在C++中，如果用malloc、calloc、realloc、valloc和memalign函數進行動態存儲分配，則必須用free函數釋放分配的存儲。如果存儲分配用new［］，則必須用delete［］釋放，分配用函數new，釋放操作必須用delete函數。這些操作在Linux下可以混用，但是在其他一些操作系統下可能出現問題，例如Windows與Solaris。

　　(9)廢代碼：完全不能執行到代碼路徑上的代碼。

　　針對以上常見內存錯誤，評價一種內存自動檢測技術的檢測目標指標主要包括：

　　(1)誤報（false positives）：在無錯的情況下分析過程報錯，這是靜態分析的最大問題。

　　(2)漏報（false negatives）：發生錯誤沒報，這是所有分析過程的關鍵問題，怎樣找出程序中的所有問題是分析過程的目標。

　　(3)路徑敏感（pathsenitive）：程序中的某些變量在一定值的范圍內有些執行路徑不可能進入，在分析過程中，排除這些不可能執行路徑的分析稱為路徑敏感分析，這是一種分析優化技術，減少分析過程中的誤報。

　　(4)上下文敏感（context-senitive）：某個函數中的變量值和其調用者相關，在分析時能綜合考慮這些因素稱為上下文敏感。

　　(5)過程間分析（Interprocedual）：幾個函數都操作同一變量，分析過程能處理這種情況的，稱為過程間分析。與之相對應的過程內分析（Intraprocedual）只在單個函數內分析變量的訪問。

2動態二進制分析方法

　　內存檢測的動態分析方法是在源代碼中插入分析代碼、狀態檢測代碼，在運行時，這些代碼檢測存儲區的狀態，并且分析程序的行為，從而發現程序中的BUG。目前，內存動態分析技術的實現主要是在動態堆管理庫中添加檢測代碼來實現。庫替換可以在編譯時替換，也可以在目標程序動態鏈接時替換，還有其他一些特殊的檢測代碼插入方法。動態二進制分析和動態源代碼分析的主要區別在于，動態二進制分析是在指令級插入檢測代碼，動態源代碼分析是在庫級、函數級插入代碼。

　　本文動態二進制分析采用的主要技術如下。

　　2.1影子內存

　　在目標代碼的指令中動態插入檢測代碼，檢測代碼跟蹤存儲區中每個字節（可以有字級、字節級）的可尋址性或存儲區的每個字節（可以有字級、字節級、位級）或寄存器的有效性，這些存儲區的存儲狀態信息保存在影子存儲中。當目標程序有數據移動、數據操縱等操作時，檢測代碼檢查影子存儲中該字節的狀態，從而檢測存儲相關問題。

　　影子內存具體有多種實現方式，下面是兩種最簡單的方式。

　　(1)將用戶態的地址空間分為2個部分，一部分程序使用，另一部分作為影子內存。存儲空間的開銷大，地址映射關系簡單，查找效率高。

　　(2)采用動態分配的存儲作為影子內存，未分配存儲空間就不需要影子內存從而優化對存儲空間的需求。

　　影子內存的狀態位表示對應存儲的使用狀態。

　　(1)A位：每一個內存字節都有一個A 位（Addressability），用來表示客戶程序對其訪問的合法性。A＝0 表示不可尋址的字節， A＝1表示可以尋址的字節，分配存儲空間時置位，釋放時清0；可以檢測堆緩沖溢出、指針越界等。

　　(2)V位：寄存器或者內存的每一個字節的每個位（bit）都有一個V位（Validity），用來標明該位的值是已經定義了的。V＝0 表示已經定義位，V=1表示未定義位。可以檢測未初始化存儲錯。

　　圖1是本文實現的檢測工具影子內存的具體實現情況。

　　圖1中，采用二級表實現影子內存管理。表目PM［1］和PM［2］對應已被寫入的64 KB內存區，這些已被寫入的內存區有自己的影子內存。剩余的PM條目仍指向NoAccess DSM區。

　　2.2狀態管理

　　在采用影子內存的檢測技術中，通常采用圖2所示狀態圖管理存儲區的狀態。

　　圖2中，系統內存中的每個字節（如果采用位級的影子內存，則是每個位）存在4個狀態。

　　(1)程序啟動時，所有可用存儲區都是unallocated和uninitialized，即在影子內存中對應存儲區的A位和V位都置為無效，本文將此類存儲區記為為紅色狀態，訪問紅色存儲區發出未分配存儲訪問錯。

　　(2)存儲區分配函數作用于紅色存儲區、藍色存儲區時，存儲區進入圖2“Allocated But UnInitialized”狀態，即黃色狀態存儲區。訪問黃色存儲區發出未初始化存儲訪問錯。

　　(3)當釋放函數作用于黃色存儲區時，存儲區回到紅色存儲區狀態。

　　(4)在黃色存儲區進行寫操作時，存儲區進入圖2的“Allocated And Initialized”狀態，即綠色存儲區狀態，訪問該存儲區是合法的。

　　(5)當釋放函數作用于綠色存儲區時，存儲區進入圖2的“Freed But Still Uninitialized”狀態，即藍色存儲區狀態，訪問藍色存儲區狀態發出為分配存儲訪問錯。

　　2.3類型檢測

　　類型檢測方法解釋編譯后的二進制文件，跟蹤所有存儲器變量和寄存器的類型值，當存儲訪問發生類型不匹配錯誤時，發出警告信息。本文類型檢測工具可以檢測存儲訪問錯和類型錯等兩種錯誤方式。存儲訪問錯指存儲訪問操作訪問無效的存儲區（無效的存儲區包括讀寫未分配存儲區，訪問未初始化存儲區等）。類型錯指存儲訪問操作的操作數和操作本身不一致（例如：指針變量和實數相加、調用函數的參數數量或類型錯誤、將一個整型變量作為一個指針等）。

　　3利用動態二進制方法實現自動內存檢測

　　Valgrind是一個動態二進制指令插入（Dynamic Binary Instrumentation，DBI）框架，能夠實現運行時（動態）在目標程序中添加檢測代碼［6］。因此，可以在動態二進制指令插入框架上建立動態二進制分析器，在目標程序運行時從機器指令級上分析目標程序。

　　Valgrind采用模塊化的設計方式，系統體系結構基本上可以看成由“Valgrind核心＋工具插件”組成，核心提供一個動態二進制指令插入的基礎設施，而各個工具插件提供具體功能的實現。Valgrind核心采用即時編譯技術（JustInTime，JIT）（二進制變換）的虛擬機技術，目標程序不直接從實際處理器上運行，而是運行在Valgrind的JIT虛擬機上。

　　以此工具為基礎，本文采用影子存儲保存存儲區的分配狀態和存儲的類型信息，在目標程序運行時檢查這些信息，以檢測它支持的存儲相關錯誤。實現的內存自動檢測實驗結果如圖3所示。

　　圖3的例程中，先向union寫入一個指針值，然后從中讀一個整型值。當程序在x.p上存儲&i的值時，類型檢測器標識union中存儲的是指針值（union的類型信息由機器指令lea指令(計算&i)中推導出來）。當程序在取x.k的值進行乘法運算時，類型檢測器檢測出操作類型不匹配，從而發出警告消息。該例子同時也表明，在不需要編譯器和調試器支持的情況下，能進行類型檢查。

　　圖4內存自動檢測的數組越界錯誤檢測實驗又如，在圖4所示的程序代碼中，存在數組越界錯誤，采用傳統內存分析方法不容易檢測出來。y.a［10］賦值操作語句中數組已經越界，通過本文類型檢測可以發現該類越界訪問錯誤。

4結論

　　靜態程序分析誤報率、漏報率非常高，在當前的所有自動檢測方法中，實用性不強，目前還沒有靜態分析工具能保證程序的健壯性，通常都作為一種調試手段在使用。動態檢測方法可以在程序運行時檢測，因此，可以在發布的產品中附帶動態檢測工具，當在軟件實現運行過程中出現問題時，方便開發人員快速定位BUG的位置，從而消除BUG。因此，動態檢測方法可以有效地降低程序BUG所造成的損失。本文在動態二進制內存自動檢測框架的基礎上，通過狀態管理和類型檢測等方法實現了常見軟件內存錯誤的自動檢測。研究結果表明，該自動檢測方法能夠在不需要編譯器和調試器支持的情況下實現高效的內存錯誤自動檢測，為更好地研究自動內存管理提供了幫助。

參考文獻

　　［1］ 肖如良. 虛擬計算環境的運行時資源監控與內存泄漏檢測技術［M］. 北京：電子工業出版社，2015.

　　［2］ JONES R, HOSKINGntony. 垃圾回收算法手冊:自動內存管理的藝術［M］. 王雅光，譯.北京：機械工業出版社，2016.

　?。?］ 楊宇,張健. 程序靜態分析技術與工具［J］. 計算機科學, 2004,31(2): 171174.

　　［4］ 吳民,涂奉生. 內存泄漏的動態跟蹤分析［J］. 計算機工程與應用, 2005,45(14): 1820.

　　［5］ 夏超,邱衛東.二進制環境下的緩沖區溢出漏洞動態檢測［J］. 計算機工程, 2008,34(22): 187191.

　?。?］ 潘竹生，童維勤， 周正. 基于Valgrind的嵌入式應用程序調試技術［J］.微計算機信息， 2009, 25(22):5860.