針對事件驅動軟件的測試集排序準則

張圣迪，高建華

（上海師范大學 計算機科學與工程系，上海200234）

0 引 言

事件驅動軟件是軟件的一個重要分支，GUI軟件與Web軟件是其中最典型的例子。它們都在測試方面面臨著巨大的挑戰和困難。這兩類軟件的測試難度主要在于：其一，它們是基于事件驅動的，圖形化用戶界面可以為用戶提供大量的輸入事件，要完全測試這些狀態則需要大量的測試，同時，這些輸入事件之間還可能會有一定的關聯性；其二，它們都具有以用戶為中心的性質，它們在開發維護的過程中經常要發生改變，而這又將帶來更多的測試需求。測試集排序準則可以對測試集排序，使得可以以最少量的代價來最大程度的進行軟件測試。雖然WEB 軟件和GUI軟件在各自的領域都有不少的研究學者對它們的測試進行研究，包括測試理論、模型、方法，但將GUI軟件和WEB軟件整合在一起的研究卻非常少，缺少合適的研究工具以及合適的模型是主要的因素。Sreedevi等［1］對于缺少模型的問題作了一系列的研究，他們提出了一個將GUI軟件和WEB軟件整合在一起研究的簡單模型，并且他們還提出了一些基于這個模型的測試集排序準則。本文針對這幾種準則進行了擴展，提出了3種同時用于GUI軟件和WEB 軟件的測試集排序準則，并以一個實驗來驗證其有效性。

1 WEB軟件測試與GUI軟件測試的特點和共性

1.1 GUI軟件與GUI軟件測試

GUI軟件包含了軟件的前端圖形化界面以及后臺的代碼。它從一個固定的事件集中接受輸入并產生確定的輸出。用戶通過觸發相應的事件來與軟件交互，事件通常以某些方式被綁定在前端的某些控件上，當用戶對控件實行特定的操作就觸發了相應的事件，而程序則改變自身的狀態來進行回應。

事件綁定機制使得用戶的輸入變得不確定，一方面用戶可以隨意觸發本狀態下可以觸發的所有事件；另一方面即使是同一個事件，所傳遞的參數不同，軟件程序執行結果和路徑就不同。不僅如此，有些事件之間還具有關聯性，它們的執行順序也會影響程序的執行結果。由于用戶輸入的不確定性以及事件之間所具有的關聯性直接導致了GUI軟件測試的困境。研究結果表明，GUI軟件的錯誤與它所隱含的業務邏輯有關［2］。大量可能的事件使得測試的成本巨大且效率低下，而以用戶為中心的性質和用戶觸發事件的隨意性也使得自動化測試難以實現。

GUI軟件測試的研究成果主要有基于模型的測試用例生成、執行、回歸測試［3］。有研究將基于代碼覆蓋的測試集排序準則和基于模型的測試集排序準則進行對比，得出通過基于模型的測試集排序準則排序的測試集能更快發現軟件中的錯誤的結論［4］。

1.2 WEB軟件與WEB軟件測試

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

WEB軟件測試的主要研究成果有：基于用戶會話的測試用例排序和刪減［5，6］，這些準則基于測試長度、請求序列的出現頻率以及參數值對的覆蓋情況進行排序；基于代碼覆蓋的回歸測試排序和刪減［7，8］；基于方法覆蓋率作的測試集排序準則［9］。

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

1.3 WEB軟件與GUI軟件的共性

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

（1）它們通常都采用面向對象的編程方式，實例化對象并調用它們的方法來完成功能。

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

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

（4）一個事件對應一個入口，通過入口就可以找出事件的調用路徑。通過靜態掃描步驟得到調用路徑時，并不能準確判斷調用路徑，對于一個事件掃描得到的調用方法數量會多于實際情況。

2 測試集排序準則的理論

2.1 需要優先測試的方法

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

（1）程序的業務核心方法。業務核心方法是指完成程序核心業務流程所必須經過的方法，特點是使用頻繁。這種方法可以通過使用次數來辨別，根據使用日志等方法生成的測試用例中此類方法的調用次數都明顯多于其它方法。另外根據使用次數也可以篩選出測試集中期望重點測試的方法，因為期望重點測試的方法往往會在測試集生成時被賦予較大的比重。業務流程中核心實體依據業務邏輯會發生的多種狀態轉換，狀態轉換通常有嚴格的限制使得核心實體之間具有復雜的相互依賴。它們的業務邏輯和軟件中許多其它的模塊都有牽連。這樣的方法實現的過程中容易產生出錯和疏漏，甚至會存在設計缺陷導致軟件中斷和數據異常從而造成損失。這樣的方法具有危害性大影響面廣的特點。既為了軟件質量也為了用戶體驗，這種方法應該被優先測試。

（2）程序中實現復雜的方法。這種方法實現復雜，大多承擔著數據類型轉換、文件格式轉換、圖表統計導等高級功能，在實現之中不僅數據的處理容易發生錯誤，類型的轉換也容易發生異常。編碼中往往會留有一些漏洞使得程序存在安全隱患，這樣的方法也應該被優先測試。

2.2 事件入口

事件入口在本文中指與事件綁定的處理事件的后臺方法。GUI軟件和WEB軟件都是事件驅動的，每一個事件都對應一個事件入口。如JSP 的WEB 軟件中的表單 （form）有一個action屬性，通過配置這個屬性可以為form 綁定事件，圖1 中 的form 指 定 的action 為 “findFinOrder”則form 綁定了事件 “findFinOrder”。圖2配置事件 “findFin－Order”由finFinOrder（）方法處理，提交form 就觸發了事件 “findFinOrder”，而finFinOrder（）方法就是事件 “find－FinOrder”的事件入口。通過finFinOrder（）方法就可以得到其調用路徑上的所有方法加以測試。對于GUI軟件則是觸發綁定在控件上的事件即可，后臺會有監聽器 （Liste－ner）監聽并交給對應的方法處理，此對應方法就是事件入口。事件入口在文本中作為調用路徑的起點。

2.3 調用路徑

調用路徑指的是事件所對應的事件入口所可能調用的方法組成的樹形結構，它可以對軟件代碼進行靜態掃描得到。本文中事件的調用路徑用于統計測試用例調用了哪些方法以及方法在測試集中被調用的次數，本文提出的測試集排序準則將方法在測試集中的被調用的次數作為排序依據之一。

靜態掃描得到的調用路徑有以下特點：

（1）它包含的節點數可能多于單次實際調用的方法數量。由于不帶參數的靜態掃描無法精確定位程序的調用路徑，故會將如分支結構中if和else會執行的方法都納入統計，導致得到的調用路徑的節點數量會多于實際。

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

如圖3為調用路徑的圖示，調用方式為逐層調用。

圖1 部分JSP代碼

圖2 Struts2配置

圖3 調用路徑

2.4 圈復雜度

圈復雜度是描述方法復雜度的指標，它基于控制流程圖計算，分支和循環越多，對應的圈復雜度越高。圈復雜度數量上表現為獨立路徑條數，即合理的預防錯誤所需測試的最少路徑條數。根據方法的圈復雜度可以找出實現復雜的方法，因為實現復雜的方法通常都會有較多的分支和循環來組成，其圈復雜度也就比較高。可以說圈復雜度是最接近方法復雜程度本質的度量方式。本文中的測試集排序準則將方法的圈復雜度作為排序的依據之一，找出實現復雜的方法并給予高優先級。

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

圖4 方法的控制流程

已有工具可以計算出每個方法的復雜度如，Maven的JAVANCSS插件，在多數代碼質量管理軟件中圈復雜度都是一項重要指標。

2.5 測試集排序準則

測試集排序準則定義如下，給定一個任意測試集T，T中所有測試用例可能的排序集合P 以及P 到實數集的映射f，測試集排序準則的目標是要找出P’∈P，使得對于任意的P’’∈P 且P’≠P’’的 情 況 下，f（P’）≥f（P’’）成立。

f是一個估值函數，決定以什么標準確立測試優先級的高低。測試優先級的高低可以以覆蓋率、測試代價等標準確立。

3 排序算法與測試集排序準則

本文提出的排序算法基于貪心算法，以一個未經過排序的測試集作為輸入，對測試集中所有測試用例進行排序，并輸出排序完成的測試集。

在該排序方法中會調用的方法：

（1）coverage（）接受單個測試用例t為輸入，輸出t中測試集排序準則所關心的元素。例如以覆蓋方法數量作為衡量標準排序，coverage（t）返回t所覆蓋的方法的集合。coverage（）可依據測試集排序準則的需求去除重復元素。

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

（3）score（）接收coverage（）和allcoverage（）的返回值作為參數。計算測試用例的評分，評分是排序的最終依據。

3.1 排序算法Order Test Suite

步驟：

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

（2）構造一個空的集合R 來存放輸出排序完成后的測試集；

（3）統計測試集中所有方法的圈復雜度以及測試集中事件的調用路徑；

（4）設置標志變量p為MININT；

（5）對于R 運行allcoverage（）方法，對于某些不關心重復元素的測試集排序準則，allcoverage（）返回空集合；

（6）對于測試集T 中的測試用例t運行coverage（）方法；

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

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

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

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

3.2 測試集排序準則

3.2.1 APSFuncation準則

這種測試集排序準則引入方法被調用的次數，來確定哪些方法是業務上比較重要的，覆蓋這些重要方法的測試用例應該被優先執行。對于事件驅動軟件，均有必須實現的核心功能，在軟件運作中會被經常使用。這些功能往往都牽涉到很多的類和數據庫中的表，這樣的功能往往業務邏輯是比較復雜的，比較容易出錯。

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

3.2.2 WeightedFunction準則

這個測試集排序準則引入方法的圈復雜度來找出實現復雜的方法，測試用例所覆蓋的方法的圈復雜度的總和越高，它所被給予的測試優先級越高。

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

此測試集排序準則allcoverage（）返回空集合，sorce（）將coverage（）的返回值作為測試用例評分返回。

3.2.3 WeightedFunctionWithFeedback （WFFB）準則

前兩節提出的測試集排序準則從兩個不同的方法對測試集進行排序，但是兩者都有一些共同的缺點：

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

（2）前兩種方法的另一個主要缺點是沒有反饋機制。由于測試用例執行有先后，同一個方法在測試集中可能會被執行多次。而因為它的一部分代碼在前一次或幾次的執行中已經被測試了，所以一個已經被執行過的方法的重要性應比它未執行時低。而前兩種方法對于已被執行過的方法并未做出處理。

本節提出的WFFB 準則在WeightedFunction的基礎上與APSFunction結合，將圈復雜度和方法被調用的次數結合共同作為排序依據。不依據單一屬性排序可以增加測試集排序準則效果的穩定性，更適用于普遍情況，以此來一定程度彌補缺點 （1）。

同時，本節提出的WFFB準則將會引入反饋機制來解決缺點 （2）。當有測試用例被選擇優先執行時，這些測試用例所覆蓋的方法在接下來的排序中的權值會降低。權值降低的公式為

式中：C——方法的圈復雜度，Y——方法在測試集中總共被覆蓋的次數，X——方法在先前被選擇的測試用例中被覆蓋的次數，W——得到的新權值。式 （1）可以確保重復執行時方法的權值遞減，同時又可以根據測試集的情況自動調節。覆蓋高調用次數以及高復雜度的方法的測試用例優先級最高，而覆蓋高復雜度低調用次數的方法的測試用例和覆蓋低復雜度高調用次數的方法的測試用例則相對持平。從而補足了依據單一屬性的不足。

該測試集排序準則同樣需要使用事件調用路徑以及測試集中方法的圈復雜度。在WeightedFunction 的基礎上，算法在每一輪排序中，將現有的排序結果集R 作為輸入參數傳入allcoverage（）中，返回R 中覆蓋的方法，統計這些方法被覆蓋的次數X。對于每個測試用例t，score（）對每個其覆蓋的方法，將X 與方法總共被調用的次數Y 以及方法的圈復雜度C 代入公式，更新方法在這一輪中的權值。將t所覆蓋的每個方法的權值相加作為測試用例的評分。

4 示 例

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

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

圖5 示例各個事件可能調用的方法樹

表2 各個方法的圈復雜度

4.1 APSFuncation排序示例

對于示例，由事件調用路徑統計得到的方法在測試集中被調用的次數見表3，對于方法M5，t2和t3擁有相同的調用次數故使用隨機來決定，假設隨機結果為t2，由于與t1相關的最大值是3所以coverage（t1）返回3，同理coverage（t2）＝2，coverage（t3）＝1，此測試集排序準則allcoverage（）返回空集合而sorce（）對coverage（）的返回值不作處理，所以排序結果為t1，t2，t3。

表3 各個方法被調用的情況

4.2 WeightedFunction排序示例

對于示例，方法的圈復雜度見表2，所以對于各個測試用例評分結果見表4。

表4 WeightedFunction排序過程

此測試集排序準則allcoverage（）返回空集合而sorce（）對coverage（）的返回值不作處理，所以排序結果是t1，t2，t3。

4.3 WFFB排序示例

對于示例，方法的圈復雜度見表2，所以對于各個測試用例第一輪的測試用例評分見表5。

表5 WFFB的第一輪排序

第一輪評分的結果是t1 被選為優先測試的測試用例，將t1放入R 中。隨后開始第二輪測試用例評分。

如表6所示，由于M1、M2、M3、M4在t1中已被覆蓋過，故它們在第二輪的評分中權值有所降低。以M4 為例，查表3可知，M4 在測試集中總共被調用3 次故Y 為3，而M4在已被選擇的t1中被覆蓋2次故X 為2，M4的圈復雜度為10故C為10，代入式 （1），本輪M4的權值為10＊ ［（3－2）／3］＝3.3，為原來的1／3。第二輪評分的結果是t3被選為優先測試的測試用例，將t3放入R 中。最后的排序結果為t1，t3，t2。

表6 WFFB的第二輪排序

5 實 驗

表7中是 “BBS系統”的一部分，對這部分進行實驗來研究一個問題：以上3個測試集排序準則的有效性如何？

表7 GAMEBBS的情況

測試評判標準我們使用APFD （average percentage of faults detected），APFD 是Rothermel定義的一個用來評估測試集排序準則效力的標準。公式如下

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

圖6表示了GAMEBBS的部分方法調用圖，將其導入到排序算法，再導入GAMEBBS中的各個方法的圈復雜度。最后，根據測試集的事件入口來獲取對應的調用路徑得到方法被調用的次數，依據方法被調用的次數信息和圈復雜度信息對測試集進行排序。使用的測試用例基于使用記錄日志得到，工程中的錯誤由人工錄入。

圖6 GAMEBBS部分調用

此處引入了兩個測試集排序準則進行輔助比較：GBest貪心最佳準則，給予發現最多錯誤的測試用例高測試優先級；Random 隨機排序。

運行程序，得到的AFPD 情況如圖7所示。

APFD 值列表，見表8。

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

圖7 各個測試集排序準則的APFD

表8 APFD 統計

6 結束語

本文從后臺代碼角度分析了：①GUI軟件和WEB軟件在實現以及調用方式上的共性。②事件和事件入口以及調用路徑之間的聯系。③圈復雜度、方法被調用的次數與測試優先級的關系。借由此提出和實現了3 種可以適用于GUI和WEB的測試集排序準則。通過實例闡述排序方式并通過實現驗證其有效性。

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

［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.