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

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

引言

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

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

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

1 插樁技術概述

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

1.1 插樁方式比較

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

（1）目標代碼插樁的前提是對目標代碼進：

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

（2）源代碼插樁是在對源文件進行完整的：

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

2 程序插樁技術的研究

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

2.1 CodeTest 工具的插樁技術分析

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

（1）對源代碼進行預編譯；被測程序首先會通過CodeTest 的編譯驅動器調用程序的原編譯器進行預編譯，通常是進行宏替換。

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

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

2.2 程序插樁的切入點

CodeTest 作為一種商品，很多技術不對外公開 ，但是我們仍可以明白其插樁的原理，進而以此為參考對插樁技術做進一步的研究；在國內，雖有很多工具使用了插樁技術，但是都不夠高效， 為了方便研究我們選擇GCC 作為插樁技術研究的平臺。

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




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

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

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

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

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

2.3 插樁程序的設計

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

（1）插樁位置：

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

按照塊結構的劃分，探針的植入位置有以下幾種情況：

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

（2）插樁策略：

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

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

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

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

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

3 實驗

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

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

4 結束語

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