非干涉測試中的數據流處理算法
2007-01-01 00:00:00王莉莉金惠華張炯尚利宏
計算機應用研究 2007年1期
摘要：嵌入式軟件非干涉測試(NIT)方法[1]是一種不在被測軟件中插樁的白盒測試方法，NIT以采集被測軟件運行時處理器總線數據得到的數據流為依據進行分析，實現對被測軟件的測試與評估[1]。NIT的關鍵問題在于如何實時分析處理器總線數據流，獲得其實際執行的指令序列。為此提出了一種通用的實時數據流分析算法——滑動窗口分析算法，并對該算法的正確性、復雜度和工程實現進行討論。
關鍵詞：非干涉測試； 嵌入式軟件測試； 數據流算法； 滑動窗口
中圖法分類號：TP311．5；TP301．6文獻標識碼：A
文章編號：1001－3695(2007)01－0127－04
1引言
在數字信息技術和網絡技術高速發展的后PC（PostPC）時代，嵌入式系統已廣泛地滲透到科學、工程、軍事以及人們日常生活的方方面面，嵌入式軟件測試已經成為一個重要的研究方向。通常的軟件測試方法沒有專注于嵌入式軟件測試[4]，可信賴性測試[2]和灰盒測試[3]都是針對嵌入式軟件的測試方法，但是都需要在被測軟件中插入測試代碼，因此會對被測軟件產生干涉效應。
NIT（NonInterference Test）是一種不在被測軟件中插樁的白盒測試方法，它采集被測軟件運行時處理器總線上的數據信號生成實時數據流，并通過對該數據流的分析獲取軟件的實際運行狀況（如過程執行次數、時間、分支覆蓋率；指令執行次數、數據訪問控制；過程的調用和被調用關系等），從而實現對被測軟件的測試與評估[1]。
但硬件采集得到的實時數據流并不理想：處理器通常為追求高的指令執行效率而采取指令預取、流水線等優化設計，即使對于沒有優化設計的簡單處理器也可能出現無效取指，因此總線上出現的數據不一定被處理器執行。NIT的關鍵問題是識別數據流中數據是否被處理器執行，記錄被執行數據的執行情況，拋棄未被執行的數據。為達到這一目的，必須分析數據流中的每個數據記錄。
通常意義的數據流系統通過查詢的方式訪問數據流，盡管可能是連續長期的查詢，但不要求對每個數據項都作分析[5]。NIT把原始數據流看作分析對象而非查詢對象，必須沒有遺漏地分析原始數據流中的每個數據記錄。目前的數據流連續查詢技術不能滿足NIT中分析原始數據流的需要[6~9]，為此本文提出一種通用的實時數據流分析算法——滑動窗口分析算法。
2原始數據流
由定義2可知，原始數據流即被測軟件運行時處理器的總線數據流。原始數據流中必須包含指令項，是否包含非指令項由測試要求決定。如果通過分析指令項可以滿足測試要求（如獲得被測程序的執行情況、代碼覆蓋率和分支覆蓋率等），則原始數據流中只需要包含指令項；否則原始數據流必須包含非指令項（如測試要求分析被測程序中數據訪問的情況）。
原始數據流具有兩個特點：
(1)完整性。任意被測軟件運行時總線數據都被采集進入原始數據流。
(2)有序性。原始數據流中的數據項是有序的，且與對應的總線數據出現的時序一致，即與處理器取指順序一致。
3原始數據流分析算法
3．1原始數據流分析
原始數據流分析的目標是獲得被測程序的實際執行情況，包括過程執行次數、時間、分支覆蓋率，指令執行次數、數據訪問控制，過程的調用和被調用關系等。通過分析原始數據流中的非指令項可以獲得數據訪問控制情況，其他執行情況都可以通過分析指令項獲得。由于非指令項表示處理器訪問的數據或執行的命令，即非指令項一定被處理器執行。因此如果原始數據流中的指令項都是處理器實際執行的指令，那么只需要逐一分析原始數據流中的數據項即可實現分析目標。但是由于處理器往往為了提高運算能力而采取指令預取或者流水線等優化設計，導致處理器總線上出現的指令不一定被執行，即使對于簡單的沒有優化的處理器，由于存在無效取指，總線上出現的指令也不一定被執行。
原始數據流分析的關鍵在于識別指令項是否被執行，分析被執行的指令項，拋棄未被執行的指令項。
設指令項D，定義函數
定義3有效指令。設指令項D，若Valid(D)，則稱D為有效指令。
定義4無效指令。設指令項D，若「Valid(D)，則稱D為無效指令。
設原始數據流S=<…，Di，Di+1，…， Di+n，…>，數據項Di對S的分析要求做到：
3．2滑動窗口分析算法
原始數據流中指令項的執行情況是由處理器的體系結構特征決定的，涉及到指令集設計、預取隊列設計、預取隊列清空策略、流水線設計、流水線命中和流水線清空策略等多方面因素。設完整指令流S=<…，Di，Di+1，…， Di+n，…>，Di(Di∈S∧Code（Di))，Valid(Di)的值必須參考與Di相近的指令項，假設Di介于一條轉移指令和其目標指令之間，那么如果轉移發生，則「Valid(Di)；否則Valid(Di)。滑動窗口算法的目的在于有效地識別指令的有效性。
3．2．1滑動窗口參數
從定義5、定義6可知，窗口寬度是滑動窗口中全部數據項的數目，有效寬度是窗口中指令項的數目，因此對于任意滑動窗口w(Di， n)，易知WSize(w)≥VSize(w)。
定義7執行窗口。設原始數據流S=<…，Di，Di+1，…， Di+n，…>，w(Di， n)是S上的滑動窗口，若Code(Di+n)，則定義窗口w(Di， n)為執行窗口，記作opt_w(Di， n)。
定理1設原始數據流S=<…，Di，Di+1，…， Di+n，…>，若已知數據項Di和常數N，N≥1，則可以構造S上的執行窗口opt_w(Di， n)，n≥N，滿足條件：VSize(opt_w)=N。
證明：因為Di已知，只要確定n即可。先令n=N，構造執行窗口opt_w(Di， n)，若VSize(opt_w)=N，則構造成功；若VSize(opt_w)＜N，則增大n，直到VSize(opt_w)=N。綜上所述，定理1得證。
設指令項D，定義函數
(1)對于存在指令預取或流水線結構的處理器，Di(Di∈S∧IsJmp(Di))，為Di構造執行窗口opt_wi(Di， n)，為滿足分析要求opt_wi(Di， n)中必須包含Di和預取隊列或流水線中的指令，考慮到處理器采取的指令優化策略的多樣性和復雜性，窗口還要根據特定處理器的體系結構特性增加或減少有效寬度。但是對于確定的處理器，增加和減少的量是確定的，即執行窗口的執行寬度是由處理器的體系結構特征決定的（包括指令集設計、流水線設計和預取隊列設計等因素）。設預取隊列或流水線完全充滿時包含指令數目為N，則對于確定的處理器，
其中α為調整量，對于確定的處理器α是常量。
(2)對于不存在指令預取和流水線等指令優化設計的簡單處理器，雖然沒有處理器緩存數據，但處理器可能在指令執行過程中讀取下一條指令，造成無效取指。Di(Di∈S∧IsJmp(Di))，為Di構造執行窗口opt_wi(Di， n)，為滿足分析要求opt_wi(Di， n)必須包含無效取指的指令項。設指令的最長執行周期為M，取指頻率為f，則對于確定的處理器：
其中α為調整量，對于確定的處理器α是常量。綜上所述，定理3得證。
下面以Intel 8086和MCS51處理器為例，討論執行窗口的有效寬度設置。
Intel 8086處理器采取指令預取隊列結構，取指與執行指令的功能分別由兩個獨立部件實現，即總線接口部件（BIU）和指令執行單元（EU）。EU與BIU并行工作，使指令的讀取與執行可以部分重疊。EU每節拍處理兩字節指令，BIU在保證EU與片外傳送操作數的前提下進行指令預取，預取隊列為6Bytes。當EU中指令執行完畢時，下一條指令只能位于預取隊列中或者BIU中，因此設Di為EU中執行的指令，為Di構造執行窗口opt_wi(Di， n)，opt_wi(Di， n)中包含的指令項應該能夠表示EU、預取隊列和BIU中指令。由于8086是16位處理器，根據式（2），N=6/2=3，α為EU和BIU中指令對應的指令項， α=2，則VSize(opt_wi)=5。
對于MCS51處理器，沒有預取和流水線設計，但是在指令周期大于取指周期時，ALE信號仍有效，地址總線進行無效取指。由于MCS51中最長指令周期為4（乘除指令），每個周期取指兩次，因此根據式（3），M=4， f=2，α=0，則
3．2．2滑動窗口分析算法
通過以上分析可以得到下面三個結論：
滑動窗口算法的思想在于：Di∈S我們構造滿足式（1）的執行窗口opt_w(Di， n)，使得VSize(opt_w)=N。下面以第3．1節中提出的要求為目標，在opt_w(Di， n)范圍內對Di進行分析，這里分情況討論：
考查算法的時間復雜度容易發現，滑動分析算法的復雜度為O(N)， 其中N為原始數據流長度，可預測該算法消耗的時間與處理數據流長度成正比關系。
4滑動窗口分析算法的工程實現
由于原始數據流具有實時性，因此對原始數據流的分析必須滿足實時性的要求。從第3.1節可知，對原始數據流的分析包括三部分：
(1)分析非指令項；
(2)識別并分析有效指令；
(3)識別并拋棄無效指令。
其中，部分（1）主要記錄數據項和控制項的信息，計算復雜性小；部分（2）和部分（3）主要實現指令譯碼和指令有效性的識別。因此分析過程中需要頻繁地進行指令譯碼。考慮到譯碼所需計算量相對較大，嚴重影響分析效率，從而降低分析的實時性，所以本文采取指令提前譯碼的方法來解決這一問題。
4．1提前譯碼
在被測程序運行之前對程序作靜態分析，對程序中出現的指令進行譯碼。譯碼結果以一維線性表的形式駐留內存，稱為快查表。為提高訪問效率，快查表使用指令地址進行索引。實踐驗證：分析原始數據流時，用查詢快查表代替指令譯碼，可極大提高分析效率，滿足實時分析的要求。
由于提前譯碼階段程序尚未運行，因此對個別轉移指令只能部分譯碼（無法獲得轉移目標地址）。但是部分譯碼的情況約只占轉移指令的1%，并且部分譯碼的結果對實時分析也有幫助。實時分析時可以通過判斷相鄰指令項地址是否連續來解決部分譯碼問題。
4．2滑動窗口算法的應用
采用滑動窗口分析算法的NIT系統已經成功應用到航天某研究院的非干涉嵌入式軟件測試系統中，目前支持處理器為Intel 8086和MCS51的兩種目標系統。
本文針對這兩種目標系統各選取一個匯編語言的測試用例進行實驗，實驗結果如表1所示。NIT運行環境為Intel Pentium 4 2．4GHz CPU，512MB內存。
表1測試用例描述和測試結果
下面通過兩個實驗進一步考查滑動窗口算法的時間特性。
實驗1。被測程序選用表1中的Intel 8086匯編程序，測試用滑動窗口算法分析不同數據量的原始數據流所消耗的時間，實驗結果如圖1所示（橫坐標表示原始數據量（MB），其中每個數據項為4Bytes，縱坐標表示消耗時間(s)）。可見算法消耗的時間呈規律的線性遞增趨勢，符合算法復雜度分析的結果。
實驗2。被測程序選用表1中的Intel 8086匯編程序，測試用滑動窗口算法分析定量（1 048 576個數據項）原始數據所用時間的變化情況，算法消耗時間均值為0．609s，實驗結果如圖2所示（橫坐標表示測試號，縱坐標表示消耗時間(s)）。
5結論
NIT是一種不在被測軟件中插樁的嵌入式軟件測試方法。本文分析了NIT的數據流特性和數據流處理要求，提出了一種實時的原始數據流分析算法——滑動窗口分析算法，并對算法進行完整的定義和論證。本文以Intel 8086和MCS51為目標系統實現該算法，并對其進行了全面的測試和分析。實踐證明，該算法能夠滿足NIT測試的要求和具有良好的實時性能。目前該算法已經成功應用于航天某研究院的非干涉嵌入式軟件測試系統中。
參考文獻：
［1］張炯，金惠華，尚利宏，等. 一種嵌入式系統軟件的非干涉測試方法[J]. 北京航空航大學學報，20-04，30(7)：666669.
［2］Karl R P HLeung， Joseph KY Ng， W L Yeung. Embedded Program Testing in Untestable Mobile Environment：An Experience of Trustworthiness Approach[C]. Proceedings of the 11th AsiaPacific Software Engineering Conference (APSEC)， IEEE， 20-04.430437.
［3］Andre’C，Lockheed Martin Missiles.Graybox Software Testing Method￣ology： Embedded Software Testing Technique[C]. Digital Avionics Systems Conference， IEEE， 1999.
［4］Phyllis Frankl， Dick Hamlet. Evaluating Testing Methods by Delive￣red Reliability[J].IEEE Trans. Software Engineering，1998，24(8)：586601.
［5］Golab L， OzsuMT. Issues in Data Stream Management[C]. ACM SIGMOD Record， 2003.514.
［6］Guha S， Koudas N. Approximating a Data Stream for Querying and Estimation： Algorithms and Performance Evaluation[C]. Proceedings of the 18th International Conference on Data Engineering (ICDE)， IEEE Computer Society， 2002.567576.
［7］Golab L， Ozsu MT. Processing Sliding Window Multijoins in Conti￣nuous Queries over Data Streams[A]. Proceedings of the 29th Int’l Conference on Very Large Data Bases[C]. Berlin： Morgan Kaufmann Publishers， 2003.500511.
［8］Viglas SD， Naughton JF， Burger J. Maximizing the Output Rate of Multiway Join Queries over Streaming Information Sources[A]. Proceedings of the 29th Int’l Conference on Very Large Data Bases[C]. Berlin： Morgan Kaufmann Publishers， 2003.285296.
［9］Hammad MA， Franklin MJ， Aref WG， et al. Scheduling for Shared Window Joins over Data Streams[A]. Proceedings of the 29th Int’l Conference on very Large Data Bases[C]. Berlin： Morgan Kaufmann Publishers， 2003.297308.
作者簡介：
王莉莉（1980），女，遼寧人，博士研究生，主要研究方向為嵌入式軟件測試技術；
金惠華（1938），男，黑龍江人，教授，博導，主要研究方向為容錯計算機和分布式系統、嵌入式計算機；
張炯（1976），男，陜西人，博士研究生，主要研究方向為嵌入式軟件測試技術；
尚利宏（1971），男，甘肅人，講師，博士，主要研究方向為嵌入式系統。
注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
