1、引言

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

　　2、不可達(dá)指令的判定

　　2.1 算法提出的前提條件

　　程序塊

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

　　定義2 入口語(yǔ)句是指：1) 程序的個(gè)語(yǔ)句；2) 或者能夠由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句；3) 或者緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。

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

　　2.2 不可達(dá)指令的判定算法基本思想

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

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

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

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

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

　　6）將分別存有不同項(xiàng)的三個(gè)數(shù)組B1，B2，B3進(jìn)行比較，找出其交集，其交集中的元素即為不可達(dá)指令語(yǔ)句號(hào)。

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

　　算法實(shí)現(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;i<n;i++)

　　For(j=0;j<n;j++)

　　If(A[i]!=A1[j])

　　{ B1[k]=A1[j];

　　k++;}//找出執(zhí)行上限值時(shí)沒(méi)有執(zhí)行到的指令序列號(hào)

　　l=len(B1);

　　k=0;

　　For(i=0;i<n;i++)

　　For(j=0;j<n;j++)

　　If(A[i]!=A2[j])

　　{ B2[k]=A2[j];

　　k++;}//找出執(zhí)行下限值時(shí)沒(méi)有執(zhí)行到的指令序列號(hào)

　　k=0;

　　m=len(B2);

　　For(i=0;i<n;i++)

　　For(j=0;j<n;j++)

　　If(A[i]!=A3[j])

　　{ B3[k]=A3[j];

　　k++;}//找出執(zhí)行中間值時(shí)沒(méi)有執(zhí)行到的指令序列號(hào)

　　n=len(B3);

　　for(i=0;i<l;i++)

　　for(j=0;j<m;j++)

　　for(k=0;k<n;k++)

　　if(B1[i]==B2[j]&&B2[j]==B3[k])

　　{B[p]=B1[i];

　　P++;

　　Printf(“不可達(dá)指令語(yǔ)句號(hào)=%d,”,B[p]); }

　　Pringf(“\n”);

　　}

　　3、算法驗(yàn)證

　　下面以一個(gè)簡(jiǎn)單的匯編源程序來(lái)驗(yàn)證算法。

　　1）根據(jù)判定算法，首先把源程度塊的所有語(yǔ)句序列號(hào)存入數(shù)組A

　　A={1，2，3，4，5，6，7，8，9，10，11，12}

　　2）把X=12（大于0的數(shù)）時(shí)所執(zhí)行的語(yǔ)句序列號(hào)存入數(shù)組A1

　　A1={1，2，3，4，5，6，7，10，11，12}

　　3）把X=-3（小于0的數(shù)）時(shí)所執(zhí)行的語(yǔ)句序列號(hào)存入數(shù)組A2

　　A2={1，2，3，4，9，10，11，12}

　　4）把X=0（等于0的數(shù)）時(shí)所執(zhí)行的語(yǔ)句序列號(hào)存入數(shù)組A3

　　A3={1，2，3，4，5，10，11，12}

　　5）分別求出A1、A2、A3的補(bǔ)集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}

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

　　4、算法復(fù)雜度分析

　　此種算法源于程序塊內(nèi)，程序結(jié)構(gòu)全部為順序結(jié)構(gòu)和簡(jiǎn)單分支結(jié)構(gòu)，因此遍歷過(guò)程算法復(fù)雜度均為O（n），判定交集算法復(fù)雜度為O（n2）。因?yàn)榇怂惴ㄖ皇沁M(jìn)行兩種運(yùn)算，因此算法綜合復(fù)雜度為O（n2）。

　　5、結(jié)論

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