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

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

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

　　關(guān)鍵詞：內(nèi)存自檢；影子內(nèi)存；靜態(tài)源碼分析；動態(tài)二進制分析

0引言

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

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

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

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

1主要內(nèi)存相關(guān)軟件錯誤

　　本文討論的軟件開發(fā)過程中主要的內(nèi)存相關(guān)的軟件錯誤包括以下9種：

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

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

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

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

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

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

　　(7)系統(tǒng)調(diào)用參數(shù)錯誤：操作系統(tǒng)內(nèi)部需要做參數(shù)檢測，防止應(yīng)用程序提供錯誤的參數(shù)，從而引起系統(tǒng)的崩潰。

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

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

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

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

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

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

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

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

2動態(tài)二進制分析方法

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

　　本文動態(tài)二進制分析采用的主要技術(shù)如下。

　　2.1影子內(nèi)存

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

　　影子內(nèi)存具體有多種實現(xiàn)方式，下面是兩種最簡單的方式。

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

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

　　影子內(nèi)存的狀態(tài)位表示對應(yīng)存儲的使用狀態(tài)。

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

　　(2)V位：寄存器或者內(nèi)存的每一個字節(jié)的每個位（bit）都有一個V位（Validity），用來標明該位的值是已經(jīng)定義了的。V＝0 表示已經(jīng)定義位，V=1表示未定義位?？梢詸z測未初始化存儲錯。

　　圖1是本文實現(xiàn)的檢測工具影子內(nèi)存的具體實現(xiàn)情況。

　　圖1中，采用二級表實現(xiàn)影子內(nèi)存管理。表目PM［1］和PM［2］對應(yīng)已被寫入的64 KB內(nèi)存區(qū)，這些已被寫入的內(nèi)存區(qū)有自己的影子內(nèi)存。剩余的PM條目仍指向NoAccess DSM區(qū)。

　　2.2狀態(tài)管理

　　在采用影子內(nèi)存的檢測技術(shù)中，通常采用圖2所示狀態(tài)圖管理存儲區(qū)的狀態(tài)。

　　圖2中，系統(tǒng)內(nèi)存中的每個字節(jié)（如果采用位級的影子內(nèi)存，則是每個位）存在4個狀態(tài)。

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

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

　　(3)當釋放函數(shù)作用于黃色存儲區(qū)時，存儲區(qū)回到紅色存儲區(qū)狀態(tài)。

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

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

　　2.3類型檢測

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

　　3利用動態(tài)二進制方法實現(xiàn)自動內(nèi)存檢測

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

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

　　以此工具為基礎(chǔ)，本文采用影子存儲保存存儲區(qū)的分配狀態(tài)和存儲的類型信息，在目標程序運行時檢查這些信息，以檢測它支持的存儲相關(guān)錯誤。實現(xiàn)的內(nèi)存自動檢測實驗結(jié)果如圖3所示。

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

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

4結(jié)論

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

參考文獻

　?。?］ 肖如良. 虛擬計算環(huán)境的運行時資源監(jiān)控與內(nèi)存泄漏檢測技術(shù)［M］. 北京：電子工業(yè)出版社，2015.

　?。?］ JONES R, HOSKINGntony. 垃圾回收算法手冊:自動內(nèi)存管理的藝術(shù)［M］. 王雅光，譯.北京：機械工業(yè)出版社，2016.

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

　?。?］ 吳民,涂奉生. 內(nèi)存泄漏的動態(tài)跟蹤分析［J］. 計算機工程與應(yīng)用, 2005,45(14): 1820.

　?。?］ 夏超,邱衛(wèi)東.二進制環(huán)境下的緩沖區(qū)溢出漏洞動態(tài)檢測［J］. 計算機工程, 2008,34(22): 187191.

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