覆蓋測(cè)試中的高效代碼插樁技術(shù)

　　引言

　　在實(shí)現(xiàn)覆蓋測(cè)試的過(guò)程中，往往需要知道某些信息，如：程序中可執(zhí)行語(yǔ)句被執(zhí)行(即被覆蓋)的情況，程序執(zhí)行的路徑，變量的引用、定義等。要想獲取這類信息，需要跟蹤被測(cè)程序的執(zhí)行過(guò)程，或者是由計(jì)算機(jī)在被測(cè)程序執(zhí)行的過(guò)程中自動(dòng)記錄。前者需要人工進(jìn)行，效率低下且枯燥乏味;后者則需要在被測(cè)程序中插入完成相應(yīng)工作的代碼，即代碼插樁技術(shù)。如今大多數(shù)的覆蓋測(cè)試工具均采用代碼插樁技術(shù)。

　　在對(duì)普通應(yīng)用的軟件進(jìn)行測(cè)試時(shí)，由于現(xiàn)在電腦的配置越來(lái)越高，電腦的運(yùn)行速度越來(lái)越快，代碼插樁所引起的問(wèn)題還不是很明顯或者說(shuō)是在可以接受的范圍之內(nèi)。但是對(duì)于嵌入式軟件來(lái)說(shuō)這卻是致命的問(wèn)題。因?yàn)?a target="_blank">嵌入式軟件的系統(tǒng)資源有限(內(nèi)存較小、I/O 通道較少等)，過(guò)大的代碼膨脹率將使得程序不能在嵌入式系統(tǒng)中運(yùn)行;同時(shí)嵌入式軟件通常具有很強(qiáng)的實(shí)時(shí)性，程序的輸出只在有限的時(shí)間內(nèi)有效，遲到的“正確的”結(jié)果是無(wú)用的甚至?xí)兂慑e(cuò)誤的、有害的。

　　代碼插樁技術(shù)會(huì)破壞程序的時(shí)間特性等，導(dǎo)致軟件執(zhí)行的錯(cuò)誤。因此我們需要更高效的代碼插樁技術(shù)來(lái)完成覆蓋測(cè)試，尤其是嵌入式軟件的覆蓋測(cè)試。

　　1 插樁技術(shù)概述

　　程序插樁技術(shù)最早是由J.C. Huang 教授提出的, 它是在保證被測(cè)程序原有邏輯完整性的基礎(chǔ)上在程序中插入一些探針(又稱為“探測(cè)儀”)，通過(guò)探針的執(zhí)行并拋出程序運(yùn)行的特征數(shù)據(jù)，通過(guò)對(duì)這些數(shù)據(jù)的分析，可以獲得程序的控制流和數(shù)據(jù)流信息，進(jìn)而得到邏輯覆蓋等動(dòng)態(tài)信息，從而實(shí)現(xiàn)測(cè)試目的的方法。

　　1.1 插樁方式比較

　　由于程序插樁技術(shù)是在被測(cè)程序中插入探針，然后通過(guò)探針的執(zhí)行來(lái)獲得程序的控制流和數(shù)據(jù)流信息，以此來(lái)實(shí)現(xiàn)測(cè)試的目的。因此，根據(jù)探針插入的時(shí)間可以分為目標(biāo)代碼插樁和源代碼插樁。

　　(1)目標(biāo)代碼插樁的前提是對(duì)目標(biāo)代碼進(jìn)：

　　行必要的分析以確定需要插樁的地點(diǎn)和內(nèi)容。由于目標(biāo)代碼的格式主要和操作系統(tǒng)相關(guān)，和具體的編程語(yǔ)言及版本無(wú)關(guān)，所以得到了廣泛的應(yīng)用，尤其是在需要對(duì)內(nèi)存進(jìn)行監(jiān)控的軟件中。但是由于目標(biāo)代碼中語(yǔ)法、語(yǔ)義信息不完整，而插樁技術(shù)需要對(duì)代碼詞法語(yǔ)法的分析有較高的要求，故在覆蓋測(cè)試工具中多采用源代碼插樁。

　　(2)源代碼插樁是在對(duì)源文件進(jìn)行完整的：

　　詞法分析和語(yǔ)法分析的基礎(chǔ)上進(jìn)行的，這就保證對(duì)源文件的插樁能夠達(dá)到很高的準(zhǔn)確度和針對(duì)性。但是源代碼插樁需要接觸到源代碼，使得工作量較大，而且隨著編碼語(yǔ)言和版本的不同需要做一定的修改。在后面我們所提到的程序插樁均指源代碼插樁。

　　2 程序插樁技術(shù)的研究

　　眾多的覆蓋測(cè)試工具中都采用了程序插樁技術(shù)，但是各有各的優(yōu)缺點(diǎn)，而市場(chǎng)上認(rèn)為比較好的嵌入式測(cè)試工具有CodeTest，使用CodeTest工具插裝進(jìn)行測(cè)試對(duì)目標(biāo)程序的影響在1%到15%之間。下面對(duì)CodeTest 的插樁技術(shù)進(jìn)行的分析。

　　2.1 CodeTest 工具的插樁技術(shù)分析

　　Codetest 的插樁過(guò)程簡(jiǎn)單來(lái)說(shuō)分為兩步：

　　(1)對(duì)源代碼進(jìn)行預(yù)編譯;被測(cè)程序首先會(huì)通過(guò)CodeTest 的編譯驅(qū)動(dòng)器調(diào)用程序的原編譯器進(jìn)行預(yù)編譯，通常是進(jìn)行宏替換。

　　(2)對(duì)預(yù)編譯后的文件進(jìn)行插樁，生成插樁后的.C 文件和.IDB 的插樁符號(hào)數(shù)據(jù)庫(kù)文件;預(yù)編譯完成后，CodeTest的插裝器(即源代碼分析程序)據(jù)不同的參數(shù)對(duì)預(yù)編譯后的源代碼進(jìn)行相應(yīng)方式的自動(dòng)插樁，即在需要插樁的位置寫(xiě)入一條賦值語(yǔ)句(如：amc_ctrl=0x74100010),并把插入的標(biāo)記送入數(shù)據(jù)庫(kù)文件中生成一個(gè)符號(hào)數(shù)據(jù)庫(kù)暫存起來(lái)，為以后的分析時(shí)調(diào)用。然后，CodeTest的編譯驅(qū)動(dòng)器會(huì)調(diào)用原編譯器對(duì)插樁后的代碼進(jìn)行編譯生成可執(zhí)行目標(biāo)代碼送到目標(biāo)板上運(yùn)行。當(dāng)程序在目標(biāo)系統(tǒng)運(yùn)行到插樁點(diǎn)的位置時(shí)，目標(biāo)板的控制總線和地址總線上會(huì)出現(xiàn)相應(yīng)的控制信號(hào)和地址信號(hào)。當(dāng) CodeTest的輔助硬件(信號(hào)捕獲探頭)從控制總線和地址總線上監(jiān)視到符合以上條件的信號(hào)時(shí)，CodeTest會(huì)主動(dòng)地從數(shù)據(jù)總線上把數(shù)據(jù)捕獲回來(lái)送到CodeTest的內(nèi)存中暫存并對(duì)這些數(shù)據(jù)進(jìn)行預(yù)處理，然后將預(yù)處理后的數(shù)據(jù)通過(guò)局域網(wǎng)送到工作平臺(tái)上。通過(guò)與前面生成的符號(hào)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行比較，我們就此得知當(dāng)前程序的運(yùn)行狀態(tài)，借此完成對(duì)嵌入式軟件的性能分析，高級(jí)覆蓋率分析，內(nèi)存分析和大容量的代碼跟蹤。

　　CodeTest是一個(gè)硬件輔助軟件的測(cè)試與分析工具，它吸取軟件打點(diǎn)技術(shù)，并對(duì)這種技術(shù)進(jìn)行了改善，純軟件工具插入的是一個(gè)函數(shù)，而 CodeTest插入的是一條賦值語(yǔ)句，它在匯編級(jí)也是一條語(yǔ)句，所以它執(zhí)行的時(shí)間非常短，占用的空間也非常少，同時(shí)避免了被其它的中斷所中斷，所以它對(duì)目標(biāo)系統(tǒng)的影響非常小(1%-15%)。

　　2.2 程序插樁的切入點(diǎn)

　　CodeTest 作為一種商品，很多技術(shù)不對(duì)外公開(kāi) ，但是我們?nèi)钥梢悦靼灼洳鍢兜脑?，進(jìn)而以此為參考對(duì)插樁技術(shù)做進(jìn)一步的研究;在國(guó)內(nèi)，雖有很多工具使用了插樁技術(shù)，但是都不夠高效， 為了方便研究我們選擇GCC 作為插樁技術(shù)研究的平臺(tái)。

　　GCC 是一個(gè)高度優(yōu)化，高度可移植，且廣泛使用的編譯系統(tǒng)。它能處理多種語(yǔ)言，包括C/C++、Fortran、Java、Ada 等多種語(yǔ)言前端，而且后端幾乎支持所有的處理器結(jié)構(gòu)。同時(shí)GCC作為源碼開(kāi)放的軟件，可以自由修改和使用。

　　圖1 是GCC 增加插樁階段后的編譯流程。

　　GCC 編譯器的工作流程大致可以分為前端、中端和后端。中端Gimple 層是高版本GCC 中新增加的，是用來(lái)對(duì)經(jīng)過(guò)詞法、語(yǔ)法分析后的程序進(jìn)行優(yōu)化和整理的階段，我們這里可以暫時(shí)忽略這個(gè)階段。前端包括預(yù)處理和詞法、語(yǔ)法分析。

　　預(yù)處理通常是做宏替換處理。詞法、語(yǔ)法分析的輸入是預(yù)處理后的文件，輸出是AST ，AST 經(jīng)過(guò)優(yōu)化后產(chǎn)生Gimple Tree，然后交給RTL 模塊去處理。RTL(Register Transfer Language)是一種中間語(yǔ)言，作為編譯器工作的后端，是GCC內(nèi)部使用的一種能對(duì)實(shí)際體系結(jié)構(gòu)作抽象的，與硬件無(wú)關(guān)的語(yǔ)言。在GCC 中將生成的中間代碼表達(dá)式以一種雙向鏈表的形式組織起來(lái)的，在鏈表中有一些特殊的節(jié)點(diǎn)，這些節(jié)點(diǎn)記錄了程序的結(jié)構(gòu)信息。

　　GCC 編譯器前端的工作完成后，詞法語(yǔ)法分析器已經(jīng)識(shí)別完程序的所有特征，因此將詞法、語(yǔ)法分析至Gimple 這個(gè)階段作為代碼插樁的切入點(diǎn)是完全可行的。然后，GCC 利用中間代碼生成會(huì)匯編代碼時(shí)，如果掃描到RTL 中的特殊節(jié)點(diǎn)就會(huì)根據(jù)用戶的需要適當(dāng)?shù)牟迦胍恍┩瓿尚畔⒉杉δ艿膮R編代碼行，從而就可以實(shí)現(xiàn)代碼插樁。但是這種做法有兩個(gè)缺點(diǎn)：一是代碼的插樁和編譯器的結(jié)合很緊密，并且在匯編代碼的生成過(guò)程中需要針對(duì)不同的CPU 生成不同的匯編代碼，與CPU 的關(guān)聯(lián)性很強(qiáng)，不便于移植;而是，當(dāng)程序很大時(shí)，探針的植入會(huì)造成代碼的膨脹，及進(jìn)行信息采集的代碼的插入就需要很多時(shí)間。

　　由于代碼插樁技術(shù)中插樁點(diǎn)識(shí)別過(guò)程中的詞法、語(yǔ)法分析只需要識(shí)別有限的程序結(jié)構(gòu)特征即可，而對(duì)程序中所有的詞法語(yǔ)法進(jìn)行分析是因?yàn)橛芍虚g代碼生成匯編代碼時(shí)，需要以詞法語(yǔ)法分析作為基礎(chǔ)，識(shí)別出所有的程序結(jié)構(gòu)特征。由此可以知道滿足插樁技術(shù)要求的詞法語(yǔ)法分析器可以比中間代碼生成的詞法語(yǔ)法分析器簡(jiǎn)單。生成滿足插樁點(diǎn)識(shí)別的詞法語(yǔ)法分析器的詞法語(yǔ)法分析程序的輸入為預(yù)處理后的源代碼文件，輸出是插樁后的源代碼文件(如圖1 所示的灰色部分)。由于新增加的詞法語(yǔ)法分析程序僅僅是針對(duì)插樁所需識(shí)別的詞法、語(yǔ)法進(jìn)行分析，故而需要植入的探針比較少，代碼膨脹率自然減小，插樁速度加快，進(jìn)而整個(gè)編譯過(guò)程就會(huì)加快。

　　2.3 插樁程序的設(shè)計(jì)

　　探針的設(shè)計(jì)解決了插樁內(nèi)容的問(wèn)題，而插樁程序的設(shè)計(jì)是用來(lái)確定插樁位置和插樁策略的，即回答“在哪插”和“如何插”的問(wèn)題。

　　(1)插樁位置：

　　探針的植入要做到緊湊精干，才能保證在做到收集的信息全面而無(wú)冗余，減少代碼的膨脹率。因此，在確定插樁位置時(shí)，要將程序劃分，基本的劃分方法是基于“塊”結(jié)構(gòu)。

　　按照塊結(jié)構(gòu)的劃分，探針的植入位置有以下幾種情況：

　　a. 程序的第一條語(yǔ)句;b. 分支語(yǔ)句的開(kāi)始;c. 循環(huán)語(yǔ)句的開(kāi)始;d. 下一個(gè)入口語(yǔ)句之前的語(yǔ)句;e. 程序的結(jié)束語(yǔ)句;f. 分支語(yǔ)句的結(jié)束;g. 循環(huán)語(yǔ)句的結(jié)束;除此之外，根據(jù)覆蓋測(cè)試要求的不同，插樁的位置除了上面所說(shuō)的幾種情況外，也會(huì)隨著覆蓋測(cè)試要求的不同有所變化。

　　(2)插樁策略：

　　插樁策略是解決“如何插”的問(wèn)題。傳統(tǒng)的插樁策略是在所有需要插樁的位置插入探針，在程序運(yùn)行過(guò)程收集所有可能用到得程序信息，將其寫(xiě)入數(shù)據(jù)庫(kù)進(jìn)行分析和處理。這種方法對(duì)于大型的程序來(lái)說(shuō)，將會(huì)造成相當(dāng)大的工作量，效率很低，且會(huì)造成很大的代碼膨脹率。而我們會(huì)根據(jù)不同的測(cè)試要求，每次插入不同的探針，采用相應(yīng)的插樁策略，這樣就減少了代碼的膨脹率，保證了程序執(zhí)行的效率。下面簡(jiǎn)單介紹幾種探針的插樁策略。

　　語(yǔ)句覆蓋探針(基本塊探針)：在基本塊的入口和出口處，分別植入相應(yīng)的探針，以確定程序執(zhí)行時(shí)該基本塊是否被覆蓋。

　　分支覆蓋探針：C/C++語(yǔ)言中，分支由分支點(diǎn)確定。對(duì)于每個(gè)分支，在其開(kāi)始處植入一個(gè)相應(yīng)的探針，以確定程序執(zhí)行時(shí)該分支是否被覆蓋。

　　條件覆蓋探針：C/C++語(yǔ)言中，if, swich,while, do-while, for 幾種語(yǔ)法結(jié)構(gòu)都支持條件判定，在每個(gè)條件表達(dá)式的布爾表達(dá)式處植入探針，進(jìn)行變量跟蹤取值，以確定其被覆蓋情況。

　　根據(jù)不同測(cè)試要求采用不用的插樁策略，每次在不同的位置植入相應(yīng)的探針，使得每次只是植入有限的探針，這就更大大減少了代碼的膨脹率和插樁的速度。

　　3 實(shí)驗(yàn)

　　本文采用了一個(gè) 1000 行的程序作為被測(cè)程序，分別采用使用整體插樁的工具和我們自己開(kāi)發(fā)的工具進(jìn)行測(cè)試，結(jié)果發(fā)現(xiàn)前者插樁的時(shí)間和代碼膨脹率分別為3s 和35%，后者插樁的平均時(shí)間和平均的代碼膨脹率為1s 和8%，插樁時(shí)間得到明顯提升，代碼膨脹率明顯減少。

　　采用以上的程序插樁技術(shù)，除了常用的覆蓋測(cè)試策略外，我們還可以實(shí)現(xiàn)MC/DC 和LCSAJ 測(cè)試。

　　4 結(jié)束語(yǔ)

　　本文詳細(xì)介紹了覆蓋測(cè)試中的高效代碼插樁技術(shù)，由此可以看出在實(shí)際中覆蓋測(cè)試分析采用的覆蓋策略的多樣性決定了程序插樁時(shí)需要識(shí)別程序的特征的復(fù)雜性。同時(shí)在軟件覆蓋測(cè)試工具的開(kāi)發(fā)中，如果從軟件的分析開(kāi)始，就有合理的程序劃分、適當(dāng)?shù)倪x定插樁位置和插樁策略，就可以滿足多種測(cè)試要求，使得測(cè)試能夠合理又快速的實(shí)現(xiàn)。如果再加上自動(dòng)化測(cè)試工具的支持，那就可以大大提高測(cè)試的效率。