匯編程序覆蓋測試中不可達指令檢測算法

1、引言

一般而言，匯編語言程序的執(zhí)行表現(xiàn)為一系列邏輯路徑的動態(tài)組合，測試時盡量覆蓋所有可能的路徑是軟件測試的目標之一，有關的工作叫做覆蓋測試。目前大多數(shù)測試工具是針對C/C++等高級語言的，針對匯編語言的測試工具相當少見。由于匯編語言非結構化的特點，其實現(xiàn)程序往往采用很多條件和無條件跳轉指令，使得程序結構復雜化，按照匯編語言程序執(zhí)行的一般方法，可以得到語句的執(zhí)行序列。如果當一段程序中包含有一些無論在任何情況下都不需要執(zhí)行或者根本執(zhí)行不到的指令時，一般的測試方法就很難將這些指令甄別出來并給出適當?shù)奶崾净蜻M行必要的排除。這些指令稱為不可達指令。為此，在研究匯編程序軟件測試的過程中，本文提出了一種判定匯編源程序不可達指令的算法。

2、不可達指令的判定

2.1 算法提出的前提條件

程序塊

定義1 程序塊是指程序中一個含有少量的語句序列，其中只有一個入口語句和一個或多個出口語句，執(zhí)行時只能從入口語句進入，從出口語句退出。對于一個給定的程序，可以把它劃分為一系列的程序塊。

定義2 入口語句是指：1) 程序的第一個語句；2) 或者能夠由條件轉移語句或無條件轉移語句轉移到的語句；3) 或者緊跟在條件轉移語句后面的語句。

定義3 出口語句是指：1) 下一條入口語句之前的那條語句；2) 或者程序的終止語句。

2.2 不可達指令的判定算法基本思想

1）首先將已經(jīng)劃分好的某個源程序塊的所有語句序列號存入一個預先定義好的數(shù)組A中；

2）取程序段執(zhí)行中可以認可的初始值的上限運行程序，將指令執(zhí)行的語句序列進行記錄，并存入一個預先定義好的數(shù)組A1中；

3）取程序段執(zhí)行中可以認可的初始值的下限運行程序，同樣將指令執(zhí)行的語句序列進行記錄，并存入一個預先定義好的數(shù)組A2中；

4）取程序段執(zhí)行中可以認可的初始值的中間值運行程序，同樣將指令執(zhí)行的語句序列進行記錄，并存入一個預先定義好的數(shù)組A3中；

5）將A1,A2,A3三個數(shù)組分別與源程序段的語句序列數(shù)組A進行逐項比較，并分別把不同項列出并存入數(shù)組B1，B2，B3中；

6）最后將分別存有不同項的三個數(shù)組B1，B2，B3進行比較，找出其交集，其交集中的元素即為不可達指令語句號。

2.3 不可達指令的判定算法實現(xiàn)

算法實現(xiàn)如下：

Void pleonasm( )
{
Int A[n],A1[n],A2[n],A3[n],B1[n],B2[n],B3[n],B[n];
Int I,j,k=0,p=0;
For(i=0;in;i++)
For(j=0;jn;j++)
If(A[i]!=A1[j])
{ B1[k]=A1[j];
k++;}//找出執(zhí)行上限值時沒有執(zhí)行到的指令序列號
l=len(B1);
k=0;
For(i=0;in;i++)
For(j=0;jn;j++)
If(A[i]!=A2[j])
{ B2[k]=A2[j];
k++;}//找出執(zhí)行下限值時沒有執(zhí)行到的指令序列號
k=0;
m=len(B2);
For(i=0;in;i++)
For(j=0;jn;j++)
If(A[i]!=A3[j])
{ B3[k]=A3[j];
k++;}//找出執(zhí)行中間值時沒有執(zhí)行到的指令序列號
n=len(B3);
for(i=0;il;i++)
for(j=0;jm;j++)
for(k=0;kn;k++)
if(B1[i]==B2[j]B2[j]==B3[k])
{B[p]=B1[i];
P++;
Printf(“不可達指令語句號=%d,”,B[p]); }
Pringf(“n”);
}

3、算法驗證

下面以一個簡單的匯編源程序來驗證算法。

1）根據(jù)判定算法，首先把源程度塊的所有語句序列號存入數(shù)組A
A={1，2，3，4，5，6，7，8，9，10，11，12}

2）把X=12（大于0的數(shù)）時所執(zhí)行的語句序列號存入數(shù)組A1
A1={1，2，3，4，5，6，7，10，11，12}

3）把X=-3（小于0的數(shù)）時所執(zhí)行的語句序列號存入數(shù)組A2
A2={1，2，3，4，9，10，11，12}

4）把X=0（等于0的數(shù)）時所執(zhí)行的語句序列號存入數(shù)組A3
A3={1，2，3，4，5，10，11，12}

5）分別求出A1、A2、A3的補集B1，B2，B3
B1= ={8，9}，
B2= ={5，6，7，8}，
B3= ={6，7，8，9}

6）求出B1，B2，B3的交集B
B=B1ΛB2ΛB3={8}

因此可以斷定語句8為不可達指令，從源程序塊中刪除后并不影響程序的正確性。

4、算法復雜度分析

此種算法源于程序塊內(nèi)，程序結構全部為順序結構和簡單分支結構，因此遍歷過程算法復雜度均為O（n），判定交集算法復雜度為O（n2）。因為此算法只是進行兩種運算，因此算法綜合復雜度為O（n2）。

5、結論

本文討論了一種判定匯編語言程序不可達指令的算法，并通過一個示例程序說明了算法的實現(xiàn)并驗證了其正確性。本文的工作為覆蓋測試更全面、更有效的進行做了必要的補充，下一步需要做的是研究高效的覆蓋測試算法，以提高測試的覆蓋率。