張華強(qiáng)1，喻勝2，王繼剛1，閻波3
（1. 中興通訊成都研究所，四川 成都 610041； 2. 四川精藝防偽科技有限公司，四川 成都 610041；3. 電子科技大學(xué) 通信與信息工程學(xué)院，四川 成都 611731）
摘要：內(nèi)存相關(guān)程序錯(cuò)誤的自動(dòng)檢測技術(shù)能夠幫助程序員盡早發(fā)現(xiàn)程序中的內(nèi)存相關(guān)錯(cuò)誤，從而提高軟件開發(fā)效率，增強(qiáng)軟件運(yùn)行的可靠性。探討了采用前沿的動(dòng)態(tài)二進(jìn)制分析技術(shù)檢測軟件中與內(nèi)存相關(guān)錯(cuò)誤，為程序員定位錯(cuò)誤位置、查找錯(cuò)誤、消除錯(cuò)誤原因提供準(zhǔn)確的信息的方法，為致力于內(nèi)存程序錯(cuò)誤檢測技術(shù)的研究人員提供參考。在C/C++軟件中的內(nèi)存錯(cuò)誤檢測實(shí)例驗(yàn)證了本文方法的有效性。
關(guān)鍵詞：內(nèi)存自檢；影子內(nèi)存；靜態(tài)源碼分析；動(dòng)態(tài)二進(jìn)制分析
0引言
軟件開發(fā)過程中，與內(nèi)存相關(guān)的程序錯(cuò)誤(BUG)造成程序不能正常工作的情況非常多。通常都采用程序員手工檢查方式消除這類錯(cuò)誤。然而，程序員手工檢查方式既低效又不完備，而且與程序員的業(yè)務(wù)能力相關(guān)。因此，與內(nèi)存相關(guān)的BUG在軟件開發(fā)過程中對項(xiàng)目開發(fā)的影響非常大。
近年來，內(nèi)存相關(guān)BUG的自動(dòng)檢測技術(shù)有了很大的發(fā)展，可以幫助程序員盡早發(fā)現(xiàn)程序中的內(nèi)存相關(guān)BUG，從而提高軟件開發(fā)效率，增強(qiáng)軟件運(yùn)行的可靠性［12］。這類工具主要檢測軟件中與內(nèi)存相關(guān)BUG，為程序員定位BUG位置、查找BUG、消除BUG原因提供準(zhǔn)確的信息。
當(dāng)前在內(nèi)存自動(dòng)檢測的所有方法中，根據(jù)分析的時(shí)機(jī)可以分類為靜態(tài)分析和動(dòng)態(tài)分析方法。這一分類方法的分界點(diǎn)為程序執(zhí)行，在程序執(zhí)行前分析稱為靜態(tài)分析，在程序執(zhí)行中分析為動(dòng)態(tài)分析［34］。另一方面，根據(jù)分析操作的對象又可分為源代碼分析和二進(jìn)制目標(biāo)代碼分析［5］。其中，靜態(tài)分析方法更復(fù)雜，由于要分析所有的執(zhí)行路徑而更完備。靜態(tài)分析的最大問題是誤報(bào)太多；而動(dòng)態(tài)分析方法簡單一些，通常只分析單一的執(zhí)行路徑。由于動(dòng)態(tài)分析方法在分析時(shí)各個(gè)變量采用的是程序的真實(shí)運(yùn)行值，因此，檢查精度更高一些，誤報(bào)相對少得多。同時(shí)，源代碼分析與二進(jìn)制分析方法也是互補(bǔ)的，源代碼分析依賴于目標(biāo)程序的編程語言而與平臺（處理器體系結(jié)構(gòu)、操作系統(tǒng)）獨(dú)立，在分析過程中可以得到程序的高級信息，例如可以定位錯(cuò)誤到具體的源代碼行。二進(jìn)制分析方法剛好相反，是依賴于目標(biāo)程序的平臺而獨(dú)立于編程語言，在分析過程中可以操縱程序的低級信息，例如控制寄存器的分配等。二進(jìn)制分析的最大好處是分析第三方庫時(shí)，可以不需要第三方庫的源代碼就能分析，而源代碼分析對此就無能為力了。
本文重點(diǎn)討論通過動(dòng)態(tài)二進(jìn)制分析技術(shù)實(shí)現(xiàn)內(nèi)存自動(dòng)檢測的相關(guān)技術(shù)和具體實(shí)現(xiàn)，研究了如何利用動(dòng)態(tài)插入內(nèi)存檢測技術(shù)的二進(jìn)制級別的內(nèi)存自動(dòng)檢測方法，使程序員能夠更方便地實(shí)現(xiàn)內(nèi)存相關(guān)BUG的自動(dòng)檢測實(shí)現(xiàn)。
1主要內(nèi)存相關(guān)軟件錯(cuò)誤
本文討論的軟件開發(fā)過程中主要的內(nèi)存相關(guān)的軟件錯(cuò)誤包括以下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)越界訪問：如果指向某個(gè)存儲區(qū)的指針在進(jìn)行指針?biāo)阈g(shù)、類型轉(zhuǎn)換、賦值操作時(shí)，該指針指向另外的存儲區(qū)，造成操作的操作數(shù)發(fā)生錯(cuò)誤。
(4)未初始化存儲：沒有進(jìn)行初始化操作，其他的內(nèi)容是隨機(jī)的。因此，讀未初始化存儲區(qū)中的數(shù)據(jù)是無意義的，常常引起程序的異常行為。
(5)內(nèi)存泄漏:如果程序不停地向系統(tǒng)申請存儲空間，最終將耗盡進(jìn)程的虛擬地址空間，內(nèi)存泄漏通常都是分配了動(dòng)態(tài)存儲區(qū)，而程序沒有釋放所致。
(6)存儲區(qū)重疊操作：兩個(gè)不同的指針指向的內(nèi)存區(qū)出現(xiàn)了部分或者全部重疊,在多線程訪問操作時(shí)會出現(xiàn)數(shù)據(jù)不一致的錯(cuò)誤。
(7)系統(tǒng)調(diào)用參數(shù)錯(cuò)誤：操作系統(tǒng)內(nèi)部需要做參數(shù)檢測，防止應(yīng)用程序提供錯(cuò)誤的參數(shù)，從而引起系統(tǒng)的崩潰。
(8)存儲操作匹配:在C++中，如果用malloc、calloc、realloc、valloc和memalign函數(shù)進(jìn)行動(dòng)態(tài)存儲分配，則必須用free函數(shù)釋放分配的存儲。如果存儲分配用new［］，則必須用delete［］釋放，分配用函數(shù)new，釋放操作必須用delete函數(shù)。這些操作在Linux下可以混用，但是在其他一些操作系統(tǒng)下可能出現(xiàn)問題，例如Windows與Solaris。
(9)廢代碼：完全不能執(zhí)行到代碼路徑上的代碼。
針對以上常見內(nèi)存錯(cuò)誤，評價(jià)一種內(nèi)存自動(dòng)檢測技術(shù)的檢測目標(biāo)指標(biāo)主要包括：
(1)誤報(bào)（false positives）：在無錯(cuò)的情況下分析過程報(bào)錯(cuò)，這是靜態(tài)分析的最大問題。
(2)漏報(bào)（false negatives）：發(fā)生錯(cuò)誤沒報(bào)，這是所有分析過程的關(guān)鍵問題，怎樣找出程序中的所有問題是分析過程的目標(biāo)。
(3)路徑敏感（pathsenitive）：程序中的某些變量在一定值的范圍內(nèi)有些執(zhí)行路徑不可能進(jìn)入，在分析過程中，排除這些不可能執(zhí)行路徑的分析稱為路徑敏感分析，這是一種分析優(yōu)化技術(shù)，減少分析過程中的誤報(bào)。
(4)上下文敏感（context-senitive）：某個(gè)函數(shù)中的變量值和其調(diào)用者相關(guān)，在分析時(shí)能綜合考慮這些因素稱為上下文敏感。
(5)過程間分析（Interprocedual）：幾個(gè)函數(shù)都操作同一變量，分析過程能處理這種情況的，稱為過程間分析。與之相對應(yīng)的過程內(nèi)分析（Intraprocedual）只在單個(gè)函數(shù)內(nèi)分析變量的訪問。
2動(dòng)態(tài)二進(jìn)制分析方法
內(nèi)存檢測的動(dòng)態(tài)分析方法是在源代碼中插入分析代碼、狀態(tài)檢測代碼，在運(yùn)行時(shí)，這些代碼檢測存儲區(qū)的狀態(tài)，并且分析程序的行為，從而發(fā)現(xiàn)程序中的BUG。目前，內(nèi)存動(dòng)態(tài)分析技術(shù)的實(shí)現(xiàn)主要是在動(dòng)態(tài)堆管理庫中添加檢測代碼來實(shí)現(xiàn)。庫替換可以在編譯時(shí)替換，也可以在目標(biāo)程序動(dòng)態(tài)鏈接時(shí)替換，還有其他一些特殊的檢測代碼插入方法。動(dòng)態(tài)二進(jìn)制分析和動(dòng)態(tài)源代碼分析的主要區(qū)別在于，動(dòng)態(tài)二進(jìn)制分析是在指令級插入檢測代碼，動(dòng)態(tài)源代碼分析是在庫級、函數(shù)級插入代碼。
本文動(dòng)態(tài)二進(jìn)制分析采用的主要技術(shù)如下。
2.1影子內(nèi)存
在目標(biāo)代碼的指令中動(dòng)態(tài)插入檢測代碼，檢測代碼跟蹤存儲區(qū)中每個(gè)字節(jié)（可以有字級、字節(jié)級）的可尋址性或存儲區(qū)的每個(gè)字節(jié)（可以有字級、字節(jié)級、位級）或寄存器的有效性，這些存儲區(qū)的存儲狀態(tài)信息保存在影子存儲中。當(dāng)目標(biāo)程序有數(shù)據(jù)移動(dòng)、數(shù)據(jù)操縱等操作時(shí)，檢測代碼檢查影子存儲中該字節(jié)的狀態(tài)，從而檢測存儲相關(guān)問題。
影子內(nèi)存具體有多種實(shí)現(xiàn)方式，下面是兩種最簡單的方式。
(1)將用戶態(tài)的地址空間分為2個(gè)部分，一部分程序使用，另一部分作為影子內(nèi)存。存儲空間的開銷大，地址映射關(guān)系簡單，查找效率高。
(2)采用動(dòng)態(tài)分配的存儲作為影子內(nèi)存，未分配存儲空間就不需要影子內(nèi)存從而優(yōu)化對存儲空間的需求。
影子內(nèi)存的狀態(tài)位表示對應(yīng)存儲的使用狀態(tài)。
(1)A位：每一個(gè)內(nèi)存字節(jié)都有一個(gè)A 位（Addressability），用來表示客戶程序?qū)ζ湓L問的合法性。A＝0 表示不可尋址的字節(jié)， A＝1表示可以尋址的字節(jié)，分配存儲空間時(shí)置位，釋放時(shí)清0；可以檢測堆緩沖溢出、指針越界等。
(2)V位：寄存器或者內(nèi)存的每一個(gè)字節(jié)的每個(gè)位（bit）都有一個(gè)V位（Validity），用來標(biāo)明該位的值是已經(jīng)定義了的。V＝0 表示已經(jīng)定義位，V=1表示未定義位。可以檢測未初始化存儲錯(cuò)。
圖1是本文實(shí)現(xiàn)的檢測工具影子內(nèi)存的具體實(shí)現(xiàn)情況。
圖1中，采用二級表實(shí)現(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)存中的每個(gè)字節(jié)（如果采用位級的影子內(nèi)存，則是每個(gè)位）存在4個(gè)狀態(tài)。
(1)程序啟動(dòng)時(shí)，所有可用存儲區(qū)都是unallocated和uninitialized，即在影子內(nèi)存中對應(yīng)存儲區(qū)的A位和V位都置為無效，本文將此類存儲區(qū)記為為紅色狀態(tài)，訪問紅色存儲區(qū)發(fā)出未分配存儲訪問錯(cuò)。
(2)存儲區(qū)分配函數(shù)作用于紅色存儲區(qū)、藍(lán)色存儲區(qū)時(shí)，存儲區(qū)進(jìn)入圖2“Allocated But UnInitialized”狀態(tài)，即黃色狀態(tài)存儲區(qū)。訪問黃色存儲區(qū)發(fā)出未初始化存儲訪問錯(cuò)。
(3)當(dāng)釋放函數(shù)作用于黃色存儲區(qū)時(shí)，存儲區(qū)回到紅色存儲區(qū)狀態(tài)。
(4)在黃色存儲區(qū)進(jìn)行寫操作時(shí)，存儲區(qū)進(jìn)入圖2的“Allocated And Initialized”狀態(tài)，即綠色存儲區(qū)狀態(tài)，訪問該存儲區(qū)是合法的。
(5)當(dāng)釋放函數(shù)作用于綠色存儲區(qū)時(shí)，存儲區(qū)進(jìn)入圖2的“Freed But Still Uninitialized”狀態(tài)，即藍(lán)色存儲區(qū)狀態(tài)，訪問藍(lán)色存儲區(qū)狀態(tài)發(fā)出為分配存儲訪問錯(cuò)。
2.3類型檢測
類型檢測方法解釋編譯后的二進(jìn)制文件，跟蹤所有存儲器變量和寄存器的類型值，當(dāng)存儲訪問發(fā)生類型不匹配錯(cuò)誤時(shí)，發(fā)出警告信息。本文類型檢測工具可以檢測存儲訪問錯(cuò)和類型錯(cuò)等兩種錯(cuò)誤方式。存儲訪問錯(cuò)指存儲訪問操作訪問無效的存儲區(qū)（無效的存儲區(qū)包括讀寫未分配存儲區(qū)，訪問未初始化存儲區(qū)等）。類型錯(cuò)指存儲訪問操作的操作數(shù)和操作本身不一致（例如：指針變量和實(shí)數(shù)相加、調(diào)用函數(shù)的參數(shù)數(shù)量或類型錯(cuò)誤、將一個(gè)整型變量作為一個(gè)指針等）。
3利用動(dòng)態(tài)二進(jìn)制方法實(shí)現(xiàn)自動(dòng)內(nèi)存檢測
Valgrind是一個(gè)動(dòng)態(tài)二進(jìn)制指令插入（Dynamic Binary Instrumentation，DBI）框架，能夠?qū)崿F(xiàn)運(yùn)行時(shí)（動(dòng)態(tài)）在目標(biāo)程序中添加檢測代碼［6］。因此，可以在動(dòng)態(tài)二進(jìn)制指令插入框架上建立動(dòng)態(tài)二進(jìn)制分析器，在目標(biāo)程序運(yùn)行時(shí)從機(jī)器指令級上分析目標(biāo)程序。
Valgrind采用模塊化的設(shè)計(jì)方式，系統(tǒng)體系結(jié)構(gòu)基本上可以看成由“Valgrind核心＋工具插件”組成，核心提供一個(gè)動(dòng)態(tài)二進(jìn)制指令插入的基礎(chǔ)設(shè)施，而各個(gè)工具插件提供具體功能的實(shí)現(xiàn)。Valgrind核心采用即時(shí)編譯技術(shù)（JustInTime，JIT）（二進(jìn)制變換）的虛擬機(jī)技術(shù)，目標(biāo)程序不直接從實(shí)際處理器上運(yùn)行，而是運(yùn)行在Valgrind的JIT虛擬機(jī)上。
以此工具為基礎(chǔ)，本文采用影子存儲保存存儲區(qū)的分配狀態(tài)和存儲的類型信息，在目標(biāo)程序運(yùn)行時(shí)檢查這些信息，以檢測它支持的存儲相關(guān)錯(cuò)誤。實(shí)現(xiàn)的內(nèi)存自動(dòng)檢測實(shí)驗(yàn)結(jié)果如圖3所示。
圖3的例程中，先向union寫入一個(gè)指針值，然后從中讀一個(gè)整型值。當(dāng)程序在x.p上存儲&i的值時(shí)，類型檢測器標(biāo)識union中存儲的是指針值（union的類型信息由機(jī)器指令lea指令(計(jì)算&i)中推導(dǎo)出來）。當(dāng)程序在取x.k的值進(jìn)行乘法運(yùn)算時(shí)，類型檢測器檢測出操作類型不匹配，從而發(fā)出警告消息。該例子同時(shí)也表明，在不需要編譯器和調(diào)試器支持的情況下，能進(jìn)行類型檢查。
圖4內(nèi)存自動(dòng)檢測的數(shù)組越界錯(cuò)誤檢測實(shí)驗(yàn)又如，在圖4所示的程序代碼中，存在數(shù)組越界錯(cuò)誤，采用傳統(tǒng)內(nèi)存分析方法不容易檢測出來。y.a［10］賦值操作語句中數(shù)組已經(jīng)越界，通過本文類型檢測可以發(fā)現(xiàn)該類越界訪問錯(cuò)誤。
4結(jié)論
靜態(tài)程序分析誤報(bào)率、漏報(bào)率非常高，在當(dāng)前的所有自動(dòng)檢測方法中，實(shí)用性不強(qiáng)，目前還沒有靜態(tài)分析工具能保證程序的健壯性，通常都作為一種調(diào)試手段在使用。動(dòng)態(tài)檢測方法可以在程序運(yùn)行時(shí)檢測，因此，可以在發(fā)布的產(chǎn)品中附帶動(dòng)態(tài)檢測工具，當(dāng)在軟件實(shí)現(xiàn)運(yùn)行過程中出現(xiàn)問題時(shí)，方便開發(fā)人員快速定位BUG的位置，從而消除BUG。因此，動(dòng)態(tài)檢測方法可以有效地降低程序BUG所造成的損失。本文在動(dòng)態(tài)二進(jìn)制內(nèi)存自動(dòng)檢測框架的基礎(chǔ)上，通過狀態(tài)管理和類型檢測等方法實(shí)現(xiàn)了常見軟件內(nèi)存錯(cuò)誤的自動(dòng)檢測。研究結(jié)果表明，該自動(dòng)檢測方法能夠在不需要編譯器和調(diào)試器支持的情況下實(shí)現(xiàn)高效的內(nèi)存錯(cuò)誤自動(dòng)檢測，為更好地研究自動(dòng)內(nèi)存管理提供了幫助。
參考文獻(xiàn)
［1］ 肖如良. 虛擬計(jì)算環(huán)境的運(yùn)行時(shí)資源監(jiān)控與內(nèi)存泄漏檢測技術(shù)［M］. 北京：電子工業(yè)出版社，2015.
［2］ JONES R, HOSKINGntony. 垃圾回收算法手冊:自動(dòng)內(nèi)存管理的藝術(shù)［M］. 王雅光，譯.北京：機(jī)械工業(yè)出版社，2016.
［3］ 楊宇,張健. 程序靜態(tài)分析技術(shù)與工具［J］. 計(jì)算機(jī)科學(xué), 2004,31(2): 171174.
［4］ 吳民,涂奉生. 內(nèi)存泄漏的動(dòng)態(tài)跟蹤分析［J］. 計(jì)算機(jī)工程與應(yīng)用, 2005,45(14): 1820.
［5］ 夏超,邱衛(wèi)東.二進(jìn)制環(huán)境下的緩沖區(qū)溢出漏洞動(dòng)態(tài)檢測［J］. 計(jì)算機(jī)工程, 2008,34(22): 187191.
［6］ 潘竹生，童維勤， 周正. 基于Valgrind的嵌入式應(yīng)用程序調(diào)試技術(shù)［J］.微計(jì)算機(jī)信息， 2009, 25(22):5860.