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

  摘要：代碼插樁是實(shí)現(xiàn)覆蓋測試的關(guān)鍵技術(shù)之一，而高效的插樁技術(shù)對于嵌入式軟件的測試來說又是至關(guān)重要的。文章在對CodeTeST 中插樁技術(shù)研究的基礎(chǔ)上，以GCC 作為開發(fā)平臺，應(yīng)用并實(shí)現(xiàn)了新的插裝器，采用增加一個詞法語法分析器的方法，提高了插樁的效率。經(jīng)過實(shí)驗(yàn)證明新的插裝器具有代碼膨脹率小，插樁速度塊的優(yōu)點(diǎn)，在一定程度上做到了高效插樁。

引言

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

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

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

1 插樁技術(shù)概述

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

1.1 插樁方式比較

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

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

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

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

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

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

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

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

Codetest 的插樁過程簡單來說分為兩步：

（1）對源代碼進(jìn)行預(yù)編譯；被測程序首先會通過CodeTest 的編譯驅(qū)動器調(diào)用程序的原編譯器進(jìn)行預(yù)編譯，通常是進(jìn)行宏替換。

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

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

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

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

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




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

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

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

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

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

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

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

（1）插樁位置：

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

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

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

（2）插樁策略：

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

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

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

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

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

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

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

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

4 結(jié)束語

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