無(wú)人機(jī)機(jī)載軟件測(cè)試用例優(yōu)先級(jí)排序技術(shù)研究

霍婷婷

（牡丹江師范學(xué)院 黑龍江·牡丹江 157012）

0 前言

目前，在無(wú)人機(jī)系統(tǒng)中，不管是系統(tǒng)控制軟件，還是導(dǎo)航系統(tǒng)軟件、機(jī)載軟件，都是以軟件技術(shù)作為核心的。所以，無(wú)人機(jī)機(jī)載軟件的可靠性保證了無(wú)人機(jī)系統(tǒng)運(yùn)行安全。同時(shí)，無(wú)人機(jī)系統(tǒng)軟件門(mén)類(lèi)很多，每款軟件都起著不同的作用。隨著無(wú)人機(jī)已經(jīng)廣泛應(yīng)用于農(nóng)作物植保、電力巡檢、測(cè)繪等領(lǐng)域，無(wú)人機(jī)系統(tǒng)軟件產(chǎn)品規(guī)模和復(fù)雜性的急劇增加，軟件產(chǎn)品質(zhì)量問(wèn)題日益突出，事故頻頻發(fā)生，軟件產(chǎn)品質(zhì)量問(wèn)題已成為人們?nèi)找骊P(guān)注的焦點(diǎn)。軟件測(cè)試作為發(fā)現(xiàn)軟件問(wèn)題的一種方法受到了廣泛關(guān)注。軟件測(cè)試是軟件開(kāi)發(fā)整個(gè)流程中必不可少的一環(huán)，也是保障軟件可靠性的重要手段。軟件測(cè)試從普通意義上講，就是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程，其根本目的是在軟件產(chǎn)品投入市場(chǎng)之前，通過(guò)發(fā)現(xiàn)并更正軟件中的錯(cuò)誤，使軟件中的錯(cuò)誤密度滿(mǎn)足可控要求。軟件測(cè)試需要在限定的人力、物力和時(shí)間內(nèi)，找出軟件中存在的缺陷，并對(duì)這些缺陷進(jìn)行修正，以此來(lái)提高軟件產(chǎn)品的質(zhì)量，降低軟件使用的風(fēng)險(xiǎn)。

眾所周知，在進(jìn)行軟件測(cè)試的過(guò)程中，軟件的復(fù)雜程度、開(kāi)發(fā)人員的自身素質(zhì)以及經(jīng)驗(yàn)、選擇的測(cè)試方法以及運(yùn)用的技術(shù)等等都會(huì)對(duì)軟件測(cè)試造成重大的影響，那么為了保證測(cè)試的質(zhì)量，人們提出一個(gè)新的名詞——測(cè)試用例。然而，軟件測(cè)試又是一個(gè)十分復(fù)雜的過(guò)程，其中軟件測(cè)試計(jì)劃的制定和相應(yīng)的測(cè)試用例的設(shè)計(jì)又是至關(guān)重要的環(huán)節(jié)，這兩個(gè)過(guò)程將需要投入大量的時(shí)間和人力，其結(jié)果將直接決定軟件測(cè)試的費(fèi)用、效率和質(zhì)量。如何對(duì)測(cè)試用例集進(jìn)行有效的優(yōu)化，對(duì)系統(tǒng)進(jìn)行充分有效的測(cè)試，是目前軟件測(cè)試研究領(lǐng)域的關(guān)鍵課題，也是迫切需要解決的課題之一。測(cè)試用例集優(yōu)化技術(shù)大致可以分為三類(lèi)：測(cè)試用例選擇(Test case selection，TCS)、測(cè)試用例約簡(jiǎn)(Test case reduction，TCR)和測(cè)試用例優(yōu)先級(jí)排序(Test case prioritization，TCP)。其中，TCS技術(shù)和TCR技術(shù)在回歸測(cè)試中會(huì)丟棄一些測(cè)試用例，而這些廢棄的測(cè)試用例也可能會(huì)發(fā)現(xiàn)軟件的缺陷，但TCP技術(shù)不會(huì)有添加、刪除、修改等不可逆操作，因此不會(huì)導(dǎo)致可能發(fā)現(xiàn)軟件缺陷的測(cè)試用例的丟失。

1 測(cè)試用例優(yōu)先級(jí)排序技術(shù)

TCP技術(shù)作為典型的回歸測(cè)試用例預(yù)優(yōu)化方法的一部分，其在提高回歸測(cè)試效率方面發(fā)揮著巨大作用，逐漸成為當(dāng)前軟件行業(yè)的研究熱點(diǎn)之一。

1.1 測(cè)試用例優(yōu)先級(jí)排序技術(shù)研究現(xiàn)狀

1998年TCP的思想被首次提出，該思想一經(jīng)提出就指出：首先對(duì)測(cè)試用例集進(jìn)行初步選擇，然后根據(jù)優(yōu)先級(jí)對(duì)選擇的測(cè)試用例進(jìn)行排序，并通過(guò)實(shí)驗(yàn)初步驗(yàn)證了該方法的有效性。然后文獻(xiàn)[4]給出了TCP的形式化定義，提出了總體策略和附加策略，并基于不同的覆蓋率驗(yàn)證了這兩種策略的有效性，同時(shí)文章還最早提出了平均缺陷檢測(cè)率（Average Percentage of Fault Detection，APFD）的概念，它是用來(lái)評(píng)價(jià)、比較不同測(cè)試用例優(yōu)先級(jí)排序技術(shù)有效性的度量法則。實(shí)踐表明，TCP技術(shù)可以幫助測(cè)試人員提高缺陷檢測(cè)率，從而盡快開(kāi)展軟件修復(fù)工作。

在無(wú)人機(jī)機(jī)載軟件的回歸測(cè)試中，測(cè)試用例同時(shí)受到多個(gè)排序標(biāo)準(zhǔn)的影響，因此很難按照單一的排序標(biāo)準(zhǔn)對(duì)測(cè)試用例進(jìn)行排序以滿(mǎn)足實(shí)際需要。因此，許多研究者開(kāi)始將多目標(biāo)測(cè)試用例優(yōu)先排序(Multi objective test case prioritization，MOTCP)，即將多目標(biāo)優(yōu)化與傳統(tǒng)TCP技術(shù)相結(jié)合，從而達(dá)到適應(yīng)于實(shí)際工程應(yīng)用的目的?，F(xiàn)有的MOTCP算法根據(jù)排序方法的不同可分為兩類(lèi)：加權(quán)法和Pareto最優(yōu)法，其中前者占大多數(shù)，后者的使用相對(duì)較少。加權(quán)法是在確定測(cè)試用例的優(yōu)先級(jí)時(shí)，將權(quán)重分配給多個(gè)優(yōu)化目標(biāo)，然后根據(jù)求和值對(duì)測(cè)試用例進(jìn)行排序。實(shí)際上，使用加權(quán)求和的加權(quán)法最終是把多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題進(jìn)行求解。而Pareto最優(yōu)法通過(guò)計(jì)算Pareto最優(yōu)解集，給出一組備選的最優(yōu)TCP方案，其研究算法主要集中在以NSGA-II算法為代表的群體智能算法領(lǐng)域。另外，有研究者將群體智能算法應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域，主要包括基于粒子群算法和蟻群算法的多目標(biāo)TCP技術(shù)等。

1.2 多目標(biāo)測(cè)試用例優(yōu)先級(jí)排序建模

多目標(biāo)TCP是在傳統(tǒng)排序方法的基礎(chǔ)上同時(shí)考慮多個(gè)排序準(zhǔn)則而出現(xiàn)的一種排序方法，根據(jù)參考文獻(xiàn)[5]給出的多目標(biāo)優(yōu)化的定義，可以用以下數(shù)學(xué)模型對(duì)該問(wèn)題進(jìn)行描述：

無(wú)人機(jī)機(jī)載軟件的回歸測(cè)試的主要目的是在短時(shí)間內(nèi)發(fā)現(xiàn)更多的軟件錯(cuò)誤，并能利用APFD作為度量準(zhǔn)則。對(duì)測(cè)試用例進(jìn)行排序后，APFD計(jì)算的結(jié)果表示測(cè)試用例集的缺陷檢測(cè)率，其中，d為代碼的缺陷數(shù)，第一個(gè)檢測(cè)到缺陷i的測(cè)試用例在執(zhí)行序列中的位置用TFi表示，則APFD的計(jì)算公式可表示為式（1）。

在無(wú)人機(jī)機(jī)載軟件的回歸測(cè)試過(guò)程中，如果測(cè)試用例還沒(méi)有被執(zhí)行，則APFD的值是未知的。因此，代碼覆蓋率(Code coverage)通常用來(lái)代替APFD值作為優(yōu)化目標(biāo)，而將APFD值作為衡量TCP效果的準(zhǔn)則。為了優(yōu)先考慮代碼覆蓋率高、執(zhí)行時(shí)間短的測(cè)試用例，本文以平均塊覆蓋率(Average Percentage of Block Coverage，APBC)為優(yōu)化目標(biāo)，計(jì)算方法如式（2）所示。在執(zhí)行測(cè)試用例之前，可以通過(guò)覆蓋率分析工具獲取測(cè)試用例的覆蓋率信息，因此可以在所有測(cè)試用例執(zhí)行之前使用APBC來(lái)指導(dǎo)TCP。

其中TBi是序列中發(fā)現(xiàn)的第一個(gè)錯(cuò)誤的用例的位置號(hào)，n是測(cè)試用例的數(shù)量，m是該測(cè)試用例集中發(fā)現(xiàn)的錯(cuò)誤的數(shù)量，并且是ETt測(cè)試用例t的執(zhí)行時(shí)間。由于APBC是測(cè)試用例序列塊覆蓋率(Percentage of Block Coverage，PBC)的平均值，值越大表示這個(gè)序列能盡早地達(dá)到更高的塊覆蓋率。如表1所示，其中A，B，C，D，E為測(cè)試用例，相應(yīng)的行表示這個(gè)測(cè)試用例覆蓋的塊。

表1：測(cè)試用例和PBC信息對(duì)應(yīng)表

假設(shè)測(cè)試用例序列Ts1=，Ts2=，其測(cè)試用例序列與塊覆蓋率之間的關(guān)系如圖1所示。測(cè)試用例序列Ts1=執(zhí)行完測(cè)試用例A后覆蓋了1塊，執(zhí)行完B后一共覆蓋了3塊，以此類(lèi)推。而測(cè)試用例序列Ts2=執(zhí)行完測(cè)試用例E后覆蓋了3塊，執(zhí)行完A后一共覆蓋了4塊，執(zhí)行完C后即覆蓋了全部程序塊。

圖1：測(cè)試用例序列與PBC之間的關(guān)系

2 無(wú)人機(jī)機(jī)載軟件測(cè)試用例優(yōu)先級(jí)排序的研究方向

盡管在近幾年，對(duì)測(cè)試用例優(yōu)先級(jí)排序這一課題的研究，研究人員逐漸提出多種技術(shù)方法以及度量準(zhǔn)則來(lái)指導(dǎo)快速有效的回歸測(cè)試。即使在相關(guān)研究領(lǐng)域已取得了豐碩的研究成果，但隨著無(wú)人機(jī)機(jī)載軟件規(guī)模以及種類(lèi)不斷地?cái)U(kuò)大，現(xiàn)有的TCP技術(shù)還將面臨更多的挑戰(zhàn)。首先要解決 TCP算法的復(fù)雜度問(wèn)題，因此一個(gè)重要的研究方向就是找出影響測(cè)試用例使用的各種因素，并綜合各種因素優(yōu)化TCP技術(shù)。其次，采用更靈活的TCP算法，并利用測(cè)試過(guò)程的實(shí)時(shí)反饋信息對(duì)它進(jìn)行動(dòng)態(tài)調(diào)整，使其不斷地適應(yīng)不同的測(cè)試環(huán)境，從而提高回歸測(cè)試的有效性。

3 結(jié)束語(yǔ)

無(wú)人機(jī)機(jī)載軟件與傳統(tǒng)領(lǐng)域中的銀行金融軟件一樣，本身有著高可靠性和高安全性的要求，在機(jī)載軟件回歸測(cè)試的過(guò)程中，適當(dāng)測(cè)試用例排序會(huì)使得測(cè)試人員及早發(fā)現(xiàn)源代碼中的錯(cuò)誤，因此可以使用TCP技術(shù)對(duì)測(cè)試用例集進(jìn)行優(yōu)化。隨著機(jī)載軟件的規(guī)模及種類(lèi)不斷地?cái)U(kuò)大，在多目標(biāo)TCP數(shù)學(xué)模型的基礎(chǔ)上，本文從算法復(fù)雜度及實(shí)時(shí)效果兩方面提出了無(wú)人機(jī)機(jī)載軟件測(cè)試用例優(yōu)先級(jí)排序可能的研究方向。