針對(duì)事件驅(qū)動(dòng)軟件的測(cè)試集排序準(zhǔn)則

張圣迪，高建華

（上海師范大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海200234）

0 引 言

事件驅(qū)動(dòng)軟件是軟件的一個(gè)重要分支，GUI軟件與Web軟件是其中最典型的例子。它們都在測(cè)試方面面臨著巨大的挑戰(zhàn)和困難。這兩類軟件的測(cè)試難度主要在于：其一，它們是基于事件驅(qū)動(dòng)的，圖形化用戶界面可以為用戶提供大量的輸入事件，要完全測(cè)試這些狀態(tài)則需要大量的測(cè)試，同時(shí)，這些輸入事件之間還可能會(huì)有一定的關(guān)聯(lián)性；其二，它們都具有以用戶為中心的性質(zhì)，它們?cè)陂_發(fā)維護(hù)的過程中經(jīng)常要發(fā)生改變，而這又將帶來更多的測(cè)試需求。測(cè)試集排序準(zhǔn)則可以對(duì)測(cè)試集排序，使得可以以最少量的代價(jià)來最大程度的進(jìn)行軟件測(cè)試。雖然WEB 軟件和GUI軟件在各自的領(lǐng)域都有不少的研究學(xué)者對(duì)它們的測(cè)試進(jìn)行研究，包括測(cè)試?yán)碚摗⒛Ｐ?、方法，但將GUI軟件和WEB軟件整合在一起的研究卻非常少，缺少合適的研究工具以及合適的模型是主要的因素。Sreedevi等［1］對(duì)于缺少模型的問題作了一系列的研究，他們提出了一個(gè)將GUI軟件和WEB軟件整合在一起研究的簡(jiǎn)單模型，并且他們還提出了一些基于這個(gè)模型的測(cè)試集排序準(zhǔn)則。本文針對(duì)這幾種準(zhǔn)則進(jìn)行了擴(kuò)展，提出了3種同時(shí)用于GUI軟件和WEB 軟件的測(cè)試集排序準(zhǔn)則，并以一個(gè)實(shí)驗(yàn)來驗(yàn)證其有效性。

1 WEB軟件測(cè)試與GUI軟件測(cè)試的特點(diǎn)和共性

1.1 GUI軟件與GUI軟件測(cè)試

GUI軟件包含了軟件的前端圖形化界面以及后臺(tái)的代碼。它從一個(gè)固定的事件集中接受輸入并產(chǎn)生確定的輸出。用戶通過觸發(fā)相應(yīng)的事件來與軟件交互，事件通常以某些方式被綁定在前端的某些控件上，當(dāng)用戶對(duì)控件實(shí)行特定的操作就觸發(fā)了相應(yīng)的事件，而程序則改變自身的狀態(tài)來進(jìn)行回應(yīng)。

事件綁定機(jī)制使得用戶的輸入變得不確定，一方面用戶可以隨意觸發(fā)本狀態(tài)下可以觸發(fā)的所有事件；另一方面即使是同一個(gè)事件，所傳遞的參數(shù)不同，軟件程序執(zhí)行結(jié)果和路徑就不同。不僅如此，有些事件之間還具有關(guān)聯(lián)性，它們的執(zhí)行順序也會(huì)影響程序的執(zhí)行結(jié)果。由于用戶輸入的不確定性以及事件之間所具有的關(guān)聯(lián)性直接導(dǎo)致了GUI軟件測(cè)試的困境。研究結(jié)果表明，GUI軟件的錯(cuò)誤與它所隱含的業(yè)務(wù)邏輯有關(guān)［2］。大量可能的事件使得測(cè)試的成本巨大且效率低下，而以用戶為中心的性質(zhì)和用戶觸發(fā)事件的隨意性也使得自動(dòng)化測(cè)試難以實(shí)現(xiàn)。

GUI軟件測(cè)試的研究成果主要有基于模型的測(cè)試用例生成、執(zhí)行、回歸測(cè)試［3］。有研究將基于代碼覆蓋的測(cè)試集排序準(zhǔn)則和基于模型的測(cè)試集排序準(zhǔn)則進(jìn)行對(duì)比，得出通過基于模型的測(cè)試集排序準(zhǔn)則排序的測(cè)試集能更快發(fā)現(xiàn)軟件中的錯(cuò)誤的結(jié)論［4］。

1.2 WEB軟件與WEB軟件測(cè)試

WEB軟件包含了一個(gè)頁面的集合，用戶可以通過瀏覽器借助網(wǎng)絡(luò)訪問它們。WEB軟件接收事件作為輸入，并改變自身狀態(tài)?，F(xiàn)在的WEB軟件前端通常使用圖形化用戶界面來與用戶交互，所以其與GUI軟件有共通之處。WEB軟件的頁面呈現(xiàn)可以是靜態(tài)的編寫，也可以通過服務(wù)端代碼獲取數(shù)據(jù)后填充而形成動(dòng)態(tài)頁面。事件的綁定和觸發(fā)也與GUI軟件類似，但WEB軟件通常基于URL 的方式來進(jìn)行請(qǐng)求。WEB軟件分成客戶端和服務(wù)端兩部分，它們各自可以由很多種語言來實(shí)現(xiàn)，WEB軟件的語言構(gòu)成可以比較復(fù)雜，因此它的測(cè)試難度也就比較高。

WEB軟件測(cè)試的主要研究成果有：基于用戶會(huì)話的測(cè)試用例排序和刪減［5，6］，這些準(zhǔn)則基于測(cè)試長(zhǎng)度、請(qǐng)求序列的出現(xiàn)頻率以及參數(shù)值對(duì)的覆蓋情況進(jìn)行排序；基于代碼覆蓋的回歸測(cè)試排序和刪減［7，8］；基于方法覆蓋率作的測(cè)試集排序準(zhǔn)則［9］。

WEB軟件測(cè)試目前的測(cè)試工具大多基于捕捉／回放機(jī)制的測(cè)試軟件，捕捉測(cè)試者與程序的交互并將其重放［10］。與GUI軟件類似，用戶輸入的不確定性以及事件之間所具有的約束性和事件執(zhí)行的不同順序使得WEB軟件的測(cè)試也面臨著巨大的挑戰(zhàn)。

1.3 WEB軟件與GUI軟件的共性

WEB軟件與GUI軟件都使用圖形化用戶界面，所以它們的前端有很多相似的地方，這一點(diǎn)Sreedevi Sampah等已經(jīng)做了研究并且歸納出了一個(gè)模型［1］。而同作為事件驅(qū)動(dòng)軟件的兩大分支，它們后臺(tái)也有很多的相似之處。

（1）它們通常都采用面向?qū)ο蟮木幊谭绞?，?shí)例化對(duì)象并調(diào)用它們的方法來完成功能。

（2）它們的后臺(tái)代碼都采用分層的模式來逐層調(diào)用，基本不允許跨層調(diào)用以及下層調(diào)用上層方法。

（3）它們方法的復(fù)雜度和它們潛在的業(yè)務(wù)邏輯或是功能的復(fù)雜性成正比，功能或業(yè)務(wù)邏輯越復(fù)雜，方法的復(fù)雜度就越高。

（4）一個(gè)事件對(duì)應(yīng)一個(gè)入口，通過入口就可以找出事件的調(diào)用路徑。通過靜態(tài)掃描步驟得到調(diào)用路徑時(shí)，并不能準(zhǔn)確判斷調(diào)用路徑，對(duì)于一個(gè)事件掃描得到的調(diào)用方法數(shù)量會(huì)多于實(shí)際情況。

2 測(cè)試集排序準(zhǔn)則的理論

2.1 需要優(yōu)先測(cè)試的方法

一個(gè)GUI和WEB 軟件中所用到的方法非常多，從中定義出需要優(yōu)先測(cè)試的方法則是比較重要的。一般有兩種：

（1）程序的業(yè)務(wù)核心方法。業(yè)務(wù)核心方法是指完成程序核心業(yè)務(wù)流程所必須經(jīng)過的方法，特點(diǎn)是使用頻繁。這種方法可以通過使用次數(shù)來辨別，根據(jù)使用日志等方法生成的測(cè)試用例中此類方法的調(diào)用次數(shù)都明顯多于其它方法。另外根據(jù)使用次數(shù)也可以篩選出測(cè)試集中期望重點(diǎn)測(cè)試的方法，因?yàn)槠谕攸c(diǎn)測(cè)試的方法往往會(huì)在測(cè)試集生成時(shí)被賦予較大的比重。業(yè)務(wù)流程中核心實(shí)體依據(jù)業(yè)務(wù)邏輯會(huì)發(fā)生的多種狀態(tài)轉(zhuǎn)換，狀態(tài)轉(zhuǎn)換通常有嚴(yán)格的限制使得核心實(shí)體之間具有復(fù)雜的相互依賴。它們的業(yè)務(wù)邏輯和軟件中許多其它的模塊都有牽連。這樣的方法實(shí)現(xiàn)的過程中容易產(chǎn)生出錯(cuò)和疏漏，甚至?xí)嬖谠O(shè)計(jì)缺陷導(dǎo)致軟件中斷和數(shù)據(jù)異常從而造成損失。這樣的方法具有危害性大影響面廣的特點(diǎn)。既為了軟件質(zhì)量也為了用戶體驗(yàn)，這種方法應(yīng)該被優(yōu)先測(cè)試。

（2）程序中實(shí)現(xiàn)復(fù)雜的方法。這種方法實(shí)現(xiàn)復(fù)雜，大多承擔(dān)著數(shù)據(jù)類型轉(zhuǎn)換、文件格式轉(zhuǎn)換、圖表統(tǒng)計(jì)導(dǎo)等高級(jí)功能，在實(shí)現(xiàn)之中不僅數(shù)據(jù)的處理容易發(fā)生錯(cuò)誤，類型的轉(zhuǎn)換也容易發(fā)生異常。編碼中往往會(huì)留有一些漏洞使得程序存在安全隱患，這樣的方法也應(yīng)該被優(yōu)先測(cè)試。

2.2 事件入口

事件入口在本文中指與事件綁定的處理事件的后臺(tái)方法。GUI軟件和WEB軟件都是事件驅(qū)動(dòng)的，每一個(gè)事件都對(duì)應(yīng)一個(gè)事件入口。如JSP 的WEB 軟件中的表單 （form）有一個(gè)action屬性，通過配置這個(gè)屬性可以為form 綁定事件，圖1 中 的form 指 定 的action 為 “findFinOrder”則form 綁定了事件 “findFinOrder”。圖2配置事件 “findFin－Order”由finFinOrder（）方法處理，提交form 就觸發(fā)了事件 “findFinOrder”，而finFinOrder（）方法就是事件 “find－FinOrder”的事件入口。通過finFinOrder（）方法就可以得到其調(diào)用路徑上的所有方法加以測(cè)試。對(duì)于GUI軟件則是觸發(fā)綁定在控件上的事件即可，后臺(tái)會(huì)有監(jiān)聽器 （Liste－ner）監(jiān)聽并交給對(duì)應(yīng)的方法處理，此對(duì)應(yīng)方法就是事件入口。事件入口在文本中作為調(diào)用路徑的起點(diǎn)。

2.3 調(diào)用路徑

調(diào)用路徑指的是事件所對(duì)應(yīng)的事件入口所可能調(diào)用的方法組成的樹形結(jié)構(gòu)，它可以對(duì)軟件代碼進(jìn)行靜態(tài)掃描得到。本文中事件的調(diào)用路徑用于統(tǒng)計(jì)測(cè)試用例調(diào)用了哪些方法以及方法在測(cè)試集中被調(diào)用的次數(shù)，本文提出的測(cè)試集排序準(zhǔn)則將方法在測(cè)試集中的被調(diào)用的次數(shù)作為排序依據(jù)之一。

靜態(tài)掃描得到的調(diào)用路徑有以下特點(diǎn)：

（1）它包含的節(jié)點(diǎn)數(shù)可能多于單次實(shí)際調(diào)用的方法數(shù)量。由于不帶參數(shù)的靜態(tài)掃描無法精確定位程序的調(diào)用路徑，故會(huì)將如分支結(jié)構(gòu)中if和else會(huì)執(zhí)行的方法都納入統(tǒng)計(jì)，導(dǎo)致得到的調(diào)用路徑的節(jié)點(diǎn)數(shù)量會(huì)多于實(shí)際。

（2）以事件入口為根節(jié)點(diǎn)，以事件入口所可能調(diào)用的方法為子節(jié)點(diǎn)，并根據(jù)它們的調(diào)用關(guān)系構(gòu)成樹形結(jié)構(gòu)。由于GUI軟件和WEB 軟件都采用逐層調(diào)用的方式編碼，上層調(diào)用下層的方法完成功能，并基本不允許跨層以及反向調(diào)用，故調(diào)用路徑可以以樹形結(jié)構(gòu)描述。

如圖3為調(diào)用路徑的圖示，調(diào)用方式為逐層調(diào)用。

圖1 部分JSP代碼

圖2 Struts2配置

圖3 調(diào)用路徑

2.4 圈復(fù)雜度

圈復(fù)雜度是描述方法復(fù)雜度的指標(biāo)，它基于控制流程圖計(jì)算，分支和循環(huán)越多，對(duì)應(yīng)的圈復(fù)雜度越高。圈復(fù)雜度數(shù)量上表現(xiàn)為獨(dú)立路徑條數(shù)，即合理的預(yù)防錯(cuò)誤所需測(cè)試的最少路徑條數(shù)。根據(jù)方法的圈復(fù)雜度可以找出實(shí)現(xiàn)復(fù)雜的方法，因?yàn)閷?shí)現(xiàn)復(fù)雜的方法通常都會(huì)有較多的分支和循環(huán)來組成，其圈復(fù)雜度也就比較高?？梢哉f圈復(fù)雜度是最接近方法復(fù)雜程度本質(zhì)的度量方式。本文中的測(cè)試集排序準(zhǔn)則將方法的圈復(fù)雜度作為排序的依據(jù)之一，找出實(shí)現(xiàn)復(fù)雜的方法并給予高優(yōu)先級(jí)。

方法的圈復(fù)雜度基于控制流程圖進(jìn)行計(jì)算，如圖4所示，圈復(fù)雜度在本文中應(yīng)用計(jì)算方法：V（G）＝e－n＋2p。e是控制流圖中邊的數(shù)量，n是代表其中節(jié)點(diǎn)的數(shù)量，p代表其中組件數(shù)，由于控制流程都是連通的所以p為1。圈復(fù)雜度為V（G）＝6－5＋2＝3。

圖4 方法的控制流程

已有工具可以計(jì)算出每個(gè)方法的復(fù)雜度如，Maven的JAVANCSS插件，在多數(shù)代碼質(zhì)量管理軟件中圈復(fù)雜度都是一項(xiàng)重要指標(biāo)。

2.5 測(cè)試集排序準(zhǔn)則

測(cè)試集排序準(zhǔn)則定義如下，給定一個(gè)任意測(cè)試集T，T中所有測(cè)試用例可能的排序集合P 以及P 到實(shí)數(shù)集的映射f，測(cè)試集排序準(zhǔn)則的目標(biāo)是要找出P’∈P，使得對(duì)于任意的P’’∈P 且P’≠P’’的 情 況 下，f（P’）≥f（P’’）成立。

f是一個(gè)估值函數(shù)，決定以什么標(biāo)準(zhǔn)確立測(cè)試優(yōu)先級(jí)的高低。測(cè)試優(yōu)先級(jí)的高低可以以覆蓋率、測(cè)試代價(jià)等標(biāo)準(zhǔn)確立。

3 排序算法與測(cè)試集排序準(zhǔn)則

本文提出的排序算法基于貪心算法，以一個(gè)未經(jīng)過排序的測(cè)試集作為輸入，對(duì)測(cè)試集中所有測(cè)試用例進(jìn)行排序，并輸出排序完成的測(cè)試集。

在該排序方法中會(huì)調(diào)用的方法：

（1）coverage（）接受單個(gè)測(cè)試用例t為輸入，輸出t中測(cè)試集排序準(zhǔn)則所關(guān)心的元素。例如以覆蓋方法數(shù)量作為衡量標(biāo)準(zhǔn)排序，coverage（t）返回t所覆蓋的方法的集合。coverage（）可依據(jù)測(cè)試集排序準(zhǔn)則的需求去除重復(fù)元素。

（2）allcoverage（）接受測(cè)試集T 為輸入，返回測(cè)試集T 中每個(gè)測(cè)試用例t中測(cè)試集排序準(zhǔn)則所關(guān)心的元素之合。例如以覆蓋方法數(shù)量作為衡量標(biāo)準(zhǔn)，輸入測(cè)試集中有 ｛t1，t2｝兩個(gè)測(cè)試用例，那么返回的就是t1與t2覆蓋方法集合的合。該方法同樣可以依據(jù)測(cè)試集排序準(zhǔn)則的需求去除重復(fù)元素，除去重復(fù)元素后，結(jié)果相當(dāng)于對(duì)測(cè)試集中的每個(gè)測(cè)試用例運(yùn)行coverage（）并取并集。而對(duì)于不關(guān)心重復(fù)元素的測(cè)試集排序準(zhǔn)則，allcoverage（）通常返回空集合。此方法的輸入測(cè)試集T 一般為已被選擇優(yōu)先測(cè)試的測(cè)試用例的集合，主要目的是引入反饋機(jī)制，對(duì)已經(jīng)被覆蓋過的方法做出權(quán)值遞減等處理。

（3）score（）接收coverage（）和allcoverage（）的返回值作為參數(shù)。計(jì)算測(cè)試用例的評(píng)分，評(píng)分是排序的最終依據(jù)。

3.1 排序算法Order Test Suite

步驟：

（1）接收未排序的測(cè)試集T 為輸入，其中的測(cè)試用例記為t1……tn；

（2）構(gòu)造一個(gè)空的集合R 來存放輸出排序完成后的測(cè)試集；

（3）統(tǒng)計(jì)測(cè)試集中所有方法的圈復(fù)雜度以及測(cè)試集中事件的調(diào)用路徑；

（4）設(shè)置標(biāo)志變量p為MININT；

（5）對(duì)于R 運(yùn)行allcoverage（）方法，對(duì)于某些不關(guān)心重復(fù)元素的測(cè)試集排序準(zhǔn)則，allcoverage（）返回空集合；

（6）對(duì)于測(cè)試集T 中的測(cè)試用例t運(yùn)行coverage（）方法；

（7）將coverage（t）的返回值以及allcoverage（R）的返回值傳遞給score（）運(yùn)算；

（8）將score（）返回值v與p比較，若v大于p則將s賦值給p并將測(cè)試用例t作為候選測(cè)試用例記為s，若已有s則用t替換原來的s。若v小于p則不做處理。若v＝p則隨機(jī)決定是否將t作為候選測(cè)試用例；

（9）重復(fù) （5）～ （8）直到所有T 中的測(cè)試用例都被評(píng)分，將測(cè)試用例s插入到R 的尾部，并將s從T 中移除；

（10）重復(fù) （4）～ （9）直到T 中所有測(cè)試用例都被移除，即所有測(cè)試用例都被排序，輸出R。

3.2 測(cè)試集排序準(zhǔn)則

3.2.1 APSFuncation準(zhǔn)則

這種測(cè)試集排序準(zhǔn)則引入方法被調(diào)用的次數(shù)，來確定哪些方法是業(yè)務(wù)上比較重要的，覆蓋這些重要方法的測(cè)試用例應(yīng)該被優(yōu)先執(zhí)行。對(duì)于事件驅(qū)動(dòng)軟件，均有必須實(shí)現(xiàn)的核心功能，在軟件運(yùn)作中會(huì)被經(jīng)常使用。這些功能往往都牽涉到很多的類和數(shù)據(jù)庫中的表，這樣的功能往往業(yè)務(wù)邏輯是比較復(fù)雜的，比較容易出錯(cuò)。

對(duì)于這個(gè)測(cè)試集排序準(zhǔn)則，需要使用事件的調(diào)用路徑，根據(jù)事件調(diào)用路徑統(tǒng)計(jì)測(cè)試集中所有被覆蓋的方法被調(diào)用的次數(shù)，存放在一個(gè)以Java實(shí)現(xiàn)的列表中，每個(gè)統(tǒng)計(jì)出的方法信息以 ｛method，testcase，value｝形式存放，其中method是方法，testcase是調(diào)用method最多的測(cè)試用例，若有相同調(diào)用次數(shù)的測(cè)試用例則隨機(jī)選取，value是method在整個(gè)測(cè)試集中被調(diào)用的總次數(shù)。如M8方法被調(diào)用5次，其中t1調(diào)用M8次數(shù)最多，則記為 ｛M8，t1，5｝。coverage（t）會(huì)在列表中尋找testcase為測(cè)試用例t的記錄，并尋找其中value值最大的記錄并返回value值。此測(cè)試集排序準(zhǔn)則allcoverage（）返回空集合所以score（）對(duì)coverage（）的返回值不做任何處理直接返回，并將其作為測(cè)試用例的評(píng)分。

3.2.2 WeightedFunction準(zhǔn)則

這個(gè)測(cè)試集排序準(zhǔn)則引入方法的圈復(fù)雜度來找出實(shí)現(xiàn)復(fù)雜的方法，測(cè)試用例所覆蓋的方法的圈復(fù)雜度的總和越高，它所被給予的測(cè)試優(yōu)先級(jí)越高。

這個(gè)測(cè)試集排序準(zhǔn)則需要使用事件的調(diào)用路徑以及測(cè)試集中方法的圈復(fù)雜度，測(cè)試集中方法的圈復(fù)雜度以列表形式儲(chǔ)存，其中的每一個(gè)元素都是 ｛method，cycle｝形式，method是方法，cycle是方法的圈復(fù)雜度。coverage（t）獲取測(cè)試用例t所調(diào)用的各個(gè)方法的復(fù)雜度信息，將測(cè)試用例t調(diào)用方法的圈復(fù)雜度作為權(quán)值，將其相加作為返回值。

此測(cè)試集排序準(zhǔn)則allcoverage（）返回空集合，sorce（）將coverage（）的返回值作為測(cè)試用例評(píng)分返回。

3.2.3 WeightedFunctionWithFeedback （WFFB）準(zhǔn)則

前兩節(jié)提出的測(cè)試集排序準(zhǔn)則從兩個(gè)不同的方法對(duì)測(cè)試集進(jìn)行排序，但是兩者都有一些共同的缺點(diǎn)：

（1）前兩節(jié)提出的測(cè)試集排序準(zhǔn)則都專注于一個(gè)單一屬性在測(cè)試集中的覆蓋率對(duì)測(cè)試集進(jìn)行排序。這樣的測(cè)試集排序準(zhǔn)則針對(duì)性強(qiáng)，但通常并不能非常好的應(yīng)對(duì)所有測(cè)試集。對(duì)于某些測(cè)試集排序效果很好的測(cè)試集排序準(zhǔn)則可能對(duì)于另一些測(cè)試集效果并不佳。生成測(cè)試集的策略和項(xiàng)目本身的性質(zhì)等都可能影響排序測(cè)試集排序準(zhǔn)則的效果。如對(duì)于圈復(fù)雜度相近的方法組成的測(cè)試集中，圈復(fù)雜度作為排序依據(jù)的效果會(huì)大大降低，反之亦然。

（2）前兩種方法的另一個(gè)主要缺點(diǎn)是沒有反饋機(jī)制。由于測(cè)試用例執(zhí)行有先后，同一個(gè)方法在測(cè)試集中可能會(huì)被執(zhí)行多次。而因?yàn)樗囊徊糠执a在前一次或幾次的執(zhí)行中已經(jīng)被測(cè)試了，所以一個(gè)已經(jīng)被執(zhí)行過的方法的重要性應(yīng)比它未執(zhí)行時(shí)低。而前兩種方法對(duì)于已被執(zhí)行過的方法并未做出處理。

本節(jié)提出的WFFB 準(zhǔn)則在WeightedFunction的基礎(chǔ)上與APSFunction結(jié)合，將圈復(fù)雜度和方法被調(diào)用的次數(shù)結(jié)合共同作為排序依據(jù)。不依據(jù)單一屬性排序可以增加測(cè)試集排序準(zhǔn)則效果的穩(wěn)定性，更適用于普遍情況，以此來一定程度彌補(bǔ)缺點(diǎn) （1）。

同時(shí)，本節(jié)提出的WFFB準(zhǔn)則將會(huì)引入反饋機(jī)制來解決缺點(diǎn) （2）。當(dāng)有測(cè)試用例被選擇優(yōu)先執(zhí)行時(shí)，這些測(cè)試用例所覆蓋的方法在接下來的排序中的權(quán)值會(huì)降低。權(quán)值降低的公式為

式中：C——方法的圈復(fù)雜度，Y——方法在測(cè)試集中總共被覆蓋的次數(shù)，X——方法在先前被選擇的測(cè)試用例中被覆蓋的次數(shù)，W——得到的新權(quán)值。式 （1）可以確保重復(fù)執(zhí)行時(shí)方法的權(quán)值遞減，同時(shí)又可以根據(jù)測(cè)試集的情況自動(dòng)調(diào)節(jié)。覆蓋高調(diào)用次數(shù)以及高復(fù)雜度的方法的測(cè)試用例優(yōu)先級(jí)最高，而覆蓋高復(fù)雜度低調(diào)用次數(shù)的方法的測(cè)試用例和覆蓋低復(fù)雜度高調(diào)用次數(shù)的方法的測(cè)試用例則相對(duì)持平。從而補(bǔ)足了依據(jù)單一屬性的不足。

該測(cè)試集排序準(zhǔn)則同樣需要使用事件調(diào)用路徑以及測(cè)試集中方法的圈復(fù)雜度。在WeightedFunction 的基礎(chǔ)上，算法在每一輪排序中，將現(xiàn)有的排序結(jié)果集R 作為輸入?yún)?shù)傳入allcoverage（）中，返回R 中覆蓋的方法，統(tǒng)計(jì)這些方法被覆蓋的次數(shù)X。對(duì)于每個(gè)測(cè)試用例t，score（）對(duì)每個(gè)其覆蓋的方法，將X 與方法總共被調(diào)用的次數(shù)Y 以及方法的圈復(fù)雜度C 代入公式，更新方法在這一輪中的權(quán)值。將t所覆蓋的每個(gè)方法的權(quán)值相加作為測(cè)試用例的評(píng)分。

4 示 例

表1所示，t代表測(cè)試用例，t1、t2、t3組成了一個(gè)測(cè)試集T。M 代表方法。t1包含兩個(gè)事件E1、E2，兩個(gè)事件的入口分別是M1和M3；t2包含事件E3，入口為M6；t3包含事件E4，入口為M8。圖5表達(dá)了各個(gè)方法間的調(diào)用情況，M1會(huì)調(diào)用M2和M4，M3會(huì)調(diào)用M4等。M 邊上的數(shù)字代表其圈復(fù)雜度，在表2中列出。本文的方法的圈復(fù)雜度由方法的控制流程圖基于McCable方法計(jì)算得到，即V（G）＝e－n＋2p。

表1 示例包含的事件和事件入口

圖5 示例各個(gè)事件可能調(diào)用的方法樹

表2 各個(gè)方法的圈復(fù)雜度

4.1 APSFuncation排序示例

對(duì)于示例，由事件調(diào)用路徑統(tǒng)計(jì)得到的方法在測(cè)試集中被調(diào)用的次數(shù)見表3，對(duì)于方法M5，t2和t3擁有相同的調(diào)用次數(shù)故使用隨機(jī)來決定，假設(shè)隨機(jī)結(jié)果為t2，由于與t1相關(guān)的最大值是3所以coverage（t1）返回3，同理coverage（t2）＝2，coverage（t3）＝1，此測(cè)試集排序準(zhǔn)則allcoverage（）返回空集合而sorce（）對(duì)coverage（）的返回值不作處理，所以排序結(jié)果為t1，t2，t3。

表3 各個(gè)方法被調(diào)用的情況

4.2 WeightedFunction排序示例

對(duì)于示例，方法的圈復(fù)雜度見表2，所以對(duì)于各個(gè)測(cè)試用例評(píng)分結(jié)果見表4。

表4 WeightedFunction排序過程

此測(cè)試集排序準(zhǔn)則allcoverage（）返回空集合而sorce（）對(duì)coverage（）的返回值不作處理，所以排序結(jié)果是t1，t2，t3。

4.3 WFFB排序示例

對(duì)于示例，方法的圈復(fù)雜度見表2，所以對(duì)于各個(gè)測(cè)試用例第一輪的測(cè)試用例評(píng)分見表5。

表5 WFFB的第一輪排序

第一輪評(píng)分的結(jié)果是t1 被選為優(yōu)先測(cè)試的測(cè)試用例，將t1放入R 中。隨后開始第二輪測(cè)試用例評(píng)分。

如表6所示，由于M1、M2、M3、M4在t1中已被覆蓋過，故它們?cè)诘诙喌脑u(píng)分中權(quán)值有所降低。以M4 為例，查表3可知，M4 在測(cè)試集中總共被調(diào)用3 次故Y 為3，而M4在已被選擇的t1中被覆蓋2次故X 為2，M4的圈復(fù)雜度為10故C為10，代入式 （1），本輪M4的權(quán)值為10＊ ［（3－2）／3］＝3.3，為原來的1／3。第二輪評(píng)分的結(jié)果是t3被選為優(yōu)先測(cè)試的測(cè)試用例，將t3放入R 中。最后的排序結(jié)果為t1，t3，t2。

表6 WFFB的第二輪排序

5 實(shí) 驗(yàn)

表7中是 “BBS系統(tǒng)”的一部分，對(duì)這部分進(jìn)行實(shí)驗(yàn)來研究一個(gè)問題：以上3個(gè)測(cè)試集排序準(zhǔn)則的有效性如何？

表7 GAMEBBS的情況

測(cè)試評(píng)判標(biāo)準(zhǔn)我們使用APFD （average percentage of faults detected），APFD 是Rothermel定義的一個(gè)用來評(píng)估測(cè)試集排序準(zhǔn)則效力的標(biāo)準(zhǔn)。公式如下

其中，n是測(cè)試集T 中測(cè)試用例的數(shù)量，m 是總共被測(cè)試出的錯(cuò)誤數(shù)量，F(xiàn) 是所有被T 檢測(cè)出的錯(cuò)誤的集合。TFi是檢測(cè)出的軟件錯(cuò)誤i的測(cè)試用例在T 中的排序位置。TFi越小APFD 就越大，所以排序在前的測(cè)試用例檢測(cè)出的錯(cuò)誤越多，那么APFD 就越大，測(cè)試集排序準(zhǔn)則的效果就越好。

圖6表示了GAMEBBS的部分方法調(diào)用圖，將其導(dǎo)入到排序算法，再導(dǎo)入GAMEBBS中的各個(gè)方法的圈復(fù)雜度。最后，根據(jù)測(cè)試集的事件入口來獲取對(duì)應(yīng)的調(diào)用路徑得到方法被調(diào)用的次數(shù)，依據(jù)方法被調(diào)用的次數(shù)信息和圈復(fù)雜度信息對(duì)測(cè)試集進(jìn)行排序。使用的測(cè)試用例基于使用記錄日志得到，工程中的錯(cuò)誤由人工錄入。

圖6 GAMEBBS部分調(diào)用

此處引入了兩個(gè)測(cè)試集排序準(zhǔn)則進(jìn)行輔助比較：GBest貪心最佳準(zhǔn)則，給予發(fā)現(xiàn)最多錯(cuò)誤的測(cè)試用例高測(cè)試優(yōu)先級(jí)；Random 隨機(jī)排序。

運(yùn)行程序，得到的AFPD 情況如圖7所示。

APFD 值列表，見表8。

從圖7和表8中可以看出，由于WFFB綜合考慮了方法在測(cè)試集中被調(diào)用的次數(shù)以及方法自身的圈復(fù)雜度，故WFFB的結(jié)果相比較于其它的測(cè)試集排序準(zhǔn)則略優(yōu)一些。而由于測(cè)試集中有一些復(fù)雜的導(dǎo)入和報(bào)表生成方法，并在其中布的錯(cuò)誤數(shù)相對(duì)較多，所以WeightedFunction排第二。實(shí)驗(yàn)的測(cè)試集在各個(gè)調(diào)用數(shù)量上差距并不非常明顯，所以APSFunction僅在Random之前。也印證了依據(jù)單一屬性排序的測(cè)試集排序準(zhǔn)則對(duì)于測(cè)試集的特性依賴較大。今后將進(jìn)行更大量的實(shí)驗(yàn)以對(duì)這些測(cè)試集排序準(zhǔn)則有一個(gè)更精確的研究結(jié)果。

圖7 各個(gè)測(cè)試集排序準(zhǔn)則的APFD

表8 APFD 統(tǒng)計(jì)

6 結(jié)束語

本文從后臺(tái)代碼角度分析了：①GUI軟件和WEB軟件在實(shí)現(xiàn)以及調(diào)用方式上的共性。②事件和事件入口以及調(diào)用路徑之間的聯(lián)系。③圈復(fù)雜度、方法被調(diào)用的次數(shù)與測(cè)試優(yōu)先級(jí)的關(guān)系。借由此提出和實(shí)現(xiàn)了3 種可以適用于GUI和WEB的測(cè)試集排序準(zhǔn)則。通過實(shí)例闡述排序方式并通過實(shí)現(xiàn)驗(yàn)證其有效性。

然而，仍有未解決的問題：①對(duì)于依據(jù)復(fù)合屬性排序的測(cè)試集排序準(zhǔn)則探索不夠全面深入，應(yīng)更多的探索復(fù)合準(zhǔn)則的可能性。②實(shí)現(xiàn)的代碼泛用性不足，并且自動(dòng)化程度不夠，應(yīng)加以改進(jìn)，使其能夠適用于更多的測(cè)試集排序準(zhǔn)則，并提高自動(dòng)化程度。③實(shí)驗(yàn)量不夠，對(duì)測(cè)試集排序準(zhǔn)則的有效性的展現(xiàn)不夠充分。應(yīng)加大實(shí)驗(yàn)量，更精確的研究制定的測(cè)試集排序準(zhǔn)則的效力，特別是依據(jù)復(fù)合屬性排序的測(cè)試集排序準(zhǔn)則的效力。今后將就以上三點(diǎn)作為主要研究方向。

［1］Bryce R，Sampath S，Memon M.Developing a single model and test prioritization strategies for event－driven software ［J］.IEEE Transactions on Software Engineering，2011，37 （1）：48－64.

［2］Brooks P，Robinson B，Memon AM.An initial characterization of industrial graphical user interface systems ［C］／／Proc IEEE Int’l Conf Software Testing，Verification，and Validation，Edmonton，2009：11－20.

［3］Yuan Xun，Cohen Myra B，Memon AM.Interaction testing：Incorporating event context ［J］.IEEE Transactions on Software Engineering，2011，37 （4）：559－574.

［4］Bogdan Korel.George koutsogiannakis experimental comparison of code－based and model－based test prioritization ［C］／／International Conference on Conference：Software Testing，Veri－fication and Validation Workshops，2009：77－84.

［5］Sampath S，Bryce R，Viswanath G，et al.User－session－based test cases for web application testing ［C］／／Proc IEEE Int’l Conf Software Testing，Verification，and Validation，Lillehammer，2008：141－150.

［6］Sreedevi Sampath，Renee C Bryce，Sachin Jain，et al.A tool for combinatorial－based prioritization and reduction of user－session－based test suites［C］／／IEEE International Conference on Software Maintenance，2011：574－577.

［7］Arpad Beszedes，Tamas Gergely，Lajos Schrrettner，et al.Code－coverage－based regression test selection and prioritization in WebKit［C］／／IEEE International Conference on Software Maintenance，2012：47－55.

［8］Dusica Marijan，Arnaud Gotlieb，Sagar Sen.Test case prioritization for continuous regression testing：An industrial case study ［C］／／IEEE International Conference on Software Maintenance，2013：541－543.

［9］Hong Mei，Dan Hao，Lingming Zhang，et al.A static approach to prioritizing JUnit test cases［J］.IEEE Transactions on Software Engineering，2012，38 （6）：1258－1275.

［10］Rick Hower.Web site test tools and site management tools［EB／OL］.［2014－04－09］.http：／／www.softwareqatest.com／qatweb1.html.