基于蘊含關系的場景測試法路徑優化方法研究

嚴悍等

摘 要： 針對場景測試法中多場景切換代價優化問題，在復合狀態分析、邏輯蘊含概念基礎上，從測試場景結構分解的角度，給出狀態蘊含和場景蘊含關系的定義及推論，由場景蘊含形成場景蘊含圖SIG，然后采用圖論方法求解優化路徑。給出系統化處理方法，并與其他方法比較。最后實例驗證該方法的有效性。

關鍵字： 場景測試法； 蘊含關系； 路徑優化； 場景蘊含圖； 狀態蘊含

中圖分類號： TN911?34； TP311 文獻標識碼： A 文章編號： 1004?373X（2015）12?0118?05

0 引 言

場景測試法[1]（Scenario Test）也稱為用例測試法（Use Case Test），是一種軟件黑盒測試方法，廣泛用于復雜交互式軟件測試，尤其適用于嵌入式軟件的分布式測試。分布式測試中人員、設備和測試對象都具有特定的地理分布要求，導致測試場景的構建和撤銷代價較大。如何通過減少場景數量、避免重建場景、優化場景切換路徑來減少代價，提高測試效率，已成為一個重要且亟待解決的問題。場景測試法依據測試需求形成多個不同測試場景。測試實施中先建立場景、執行測試用例、撤銷場景，再建下一個場景，如此循環直到完成所有場景。對于多場景執行次序目前缺乏科學有效的定義和方法指導。多場景執行次序如果選擇不當，將導致重復建設和浪費。當測試失敗時往往需要重建多個場景后重測，代價更大。

Jacobson在文獻[2?3]中提出用例驅動的軟件工程思想，在此基礎上IBM Rational公司在RUP2000中提出場景測試法。該方法未說明多場景執行的次序。文獻[4]采用用例行為矩陣度量場景的優先級，通過該優先級對多個場景進行排序和路徑合并，從而減少測試代價。文獻[5]先依據用例事件流建立事件有向樹，然后對該樹進行路徑搜索，最后合并子路徑，提高場景重用率。文獻[6]依據業務流選擇部分場景優先測試，減少測試代價的同時保證功能可用性。以上研究大多側重于測試場景的行為特征，而忽視場景結構特性。本文通過研究測試場景結構、復合狀態分析、邏輯蘊含概念，通過狀態蘊含和場景蘊含關系，探索一種新思路來減少多場景切換代價。

1 測試場景的構成與場景蘊含

首先分析場景簡單切換的問題，給出狀態蘊含和場景蘊含的關系。

1.1 測試場景的簡單切換

在一般場景測試法中，測試一個場景s1前構建該場景，測試完成后需撤銷該場景。場景切換就是撤銷前一個場景并構建下一個場景的過程，如圖1所示。

圖1中假設場景s1的構建代價為b1，撤銷代價為d1，場景s2的構建代價為b2，撤銷代價為d2，那么在由s1切換到s2時，切換代價可量化為d1+b2，由s2切換到s1時，代價為d2+b1。這種切換稱為簡單切換。這種切換可能導致重復構建/撤銷。以s1切換到s2為例，如果s1中的部分對象在s2中也要使用，那么切換時就額外增加了撤銷和重建的代價。

簡單切換的好處是可在任意兩個場景之間進行切換，缺點是代價高。

將場景作為結點，簡單切換作為有向邊，切換代價作為邊權值，就可形成一個賦權有向圖，而且該圖是有向完全圖?；谠搱D選擇任何路徑都無法得到優化，原因是簡單切換邊不能表示場景之間內在的蘊含關系。

1.2 場景和狀態蘊含關系

定義1：測試場景。一個測試場景s是針對一個或幾個用例的測試需求，由一組語境對象組成的執行環境，這些對象具有特定的類型、個體及其狀態的要求。場景s的語境對象的集合記為c（s）。

圖2表示測試場景中的語境對象的性質。

圖2 測試場景的構成

圖2中一個測試場景包含一個或多個語境對象，而且每個語境對象都具有類型、個體及其狀態的限定。語境對象按類別可劃分為：測試人員、測試設備、測試對象。其中，測試對象可能是一套受測軟件，或者一組構件，或者一組對象，或者單個對象（最簡單場景）。

由定義1可知，兩個測試場景之間的差別就是其語境對象之間的差別，即對象類型、對象個體及其狀態的差別。下面分析對象狀態之間關系及其對測試用例（test case，下稱測例）執行的作用機制。

UML狀態機定義了一個對象的2個狀態s1s2之間可能具有子狀態的復合關系。假設s1是s2的一個子狀態，若處于s1態則必處于s2態，反之不然[7]。

定義2：狀態蘊含。設一個語境對象有狀態s1和s2，若s1是s2的一個子狀態，則s1s2有狀態蘊含關系，記作s1→s2。

直觀理解，若s1→s2，則s2態表示較簡單場景，s1態較復雜且具有更多屬性限制要求，即針對s1態測試的判定斷言比針對s2更多。

推論1：一個測例tc對s1s2態分別測試，有s1→s2，若s2測試失敗，則s1也失敗，記為fail（tc，s2）→fail（tc，s1）。

直觀理解，若較簡單場景測試失敗，則較復雜場景也失敗。

證明，因s1→s2，s1驗證需要比s2更多判定斷言，且增加的斷言（記為s1.newAssert）都以合取式出現。假設s2的斷言為s2.assert，那么s1的斷言式為s2.assert∧s1.newAssert。若s2測試失敗，則s2.assert為假，此時s1的斷言式也為假，故s1測試也失敗，證畢。

該推論的逆否形式也成立，若s1測試成功，則s2也成功，記為success（tc，s1）→succss（tc，s2）。

推論2：一個測例tc在s1s2兩個狀態分別測試，且有s1→s2，則應先創建s2場景測試，再切換到s1場景測試。

這是推論1的一個簡單延伸。先測試簡單場景s2，后測試較復雜場景s1。若s2測試成功，再測試s1。若s2測試失敗，由推論1知，s1也推定失敗而無需再切換到更復雜場景，從而減少代價。該推論為多場景測試提供了優化依據：從較簡單到復雜場景逐步測試，若測試成功則進入子狀態來測試更復雜場景，而未撤銷任何語境對象，直接減少代價；若測試失敗則可立即斷定從成功場景到失敗場景的新加斷言失敗，范圍小易分析原因，也減少測試代價。

推論3：設有兩個不同測例tc1，tc2，若tc1需測試狀態s1，tc2需測試狀態s2，且有s1→s2，則只需狀態s1就能滿足tc1和tc2的測試要求。

實際上，tc2測試s1與測試s2具有相同的判定斷言的結果。

證明：因tc2針對s2態測試，故tc2僅持有s2的判定斷言s2.assert。而tc1持有斷言為s2.assert∧s1.newAssert。由推理1，success（tc2，s1）→succss（tc2，s2），即tc2測試s1若成功，則測試s2也成功。若tc2測試s1失敗，則其斷言s2.assert判定為假，故此測試s2也失敗。兩者斷言判定結果相同，證畢。

由推論3可能將兩個測試場景合并為一個，能同時滿足多個測例需求，減少測試場景數量，也就減少測試代價。

1.3 場景蘊含關系

定義3：場景差。設s1，s2是2個測試場景，場景差是從場景s1切換到s2的語境對象的差別，記為c（s2）-c（s1）。

定義4：場景蘊含。設s1，s2是兩個測試場景，c（s2）-c（s1）=M，若M=[?]，或M非空，且M僅包含新建對象；或至少一個語境對象從場景s1到s2轉換為其一個子狀態，即有狀態蘊涵；前兩種情形兼有，則稱場景s2蘊含s1，記為s2→s1。

若c（s1）-c（s2）=[?]，表示2個場景具有相同的對象類別、數量和狀態，此時2個場景s1s2互相蘊含，語義上表示從測試等價類角度看，這2個場景屬于同一類。

直觀理解，兩個場景之間的蘊含關系有4種情形：

（1） 相互蘊含；

（2） 后場s2加入新對象；

（3） 后場s2中一個或多個語境對象轉入其子狀態，往往添加屬性值或關聯；

（4） 情形（2）、（3）并存。

推論4：場景蘊涵關系是一種偏序關系。

證明：

（1） 自反。對于任一個場景s1，s1蘊含s1，即s1→s1成立，證明略。

（2） 反對稱。對于任意2個不同場景s1和s2，若s1→s2，則s2→s1不成立。

證明：反證法，假設s1→s2成立時，s2→s1也成立，則由定義4可得c（s2）-c（s1）=M，c（s1）-c（s2）=M，則c（s1）=c（s2），s1與s2是相同場景，與前提矛盾，證畢。

（3） 傳遞性。對于任意3個不同場景s1、s2和s3，若s1→s2，s2→s3，則s1→s3。

證明：由定義4，可得c（s1）-c（s2）=M1，c（s2）-c（s3）=M2，兩式相加，得c（s1）-c（s3）=M1+M2，M1+M2滿足定義4中M的條件（子狀態的復合關系有傳遞性），故s1→s3成立。

2 路徑優化方法

定義5：場景蘊含圖SIG（Scenario Implication Graph）。一個場景蘊含圖G={V，E}是一個有向圖，其中V是場景集合，E是有向邊集合，若e=∈E，當且僅當s2→s1且s1≠s2成立。

場景蘊含圖中有向邊表示兩個場景之間的逆蘊含關系，直觀理解為從較簡單場景指向較復雜場景，但圖中取消了自反所導致的自回路。

推論5：場景蘊含圖不存在回路。

證明：由推論4，場景蘊含關系是一種偏序關系，在取消自回路的前提下，場景蘊含圖是哈斯圖，哈斯圖無回路[8]。

推論6：一個場景蘊含圖作為有向無環圖，若存在一條哈密爾頓路徑[8]（Hamilton Path，簡稱H路徑），則該路徑就是優化的場景切換路徑。

證明：

（1） 由H路徑定義可知，覆蓋所有場景一次且僅一次；

（2） H路徑從簡單場景到復雜場景，由推論2可知，沿該路徑測試無論成功或失敗，場景切換代價都可控制到最低。

一個場景蘊含圖不一定存在H路徑。若不連通則不存在H路徑。即便連通也不一定存在H路徑。對于一個有向無環圖，難以簡單求解H路徑。文獻[9]給出一種復雜的求解方法。

因此本文主張，對有向無環圖先求其最長路徑，嘗試覆蓋盡可能多的場景結點。若能覆蓋所有結點則得到一條H路徑；若不能覆蓋，所得到的最長路徑也可作為次優解。

推論7：場景蘊含圖中存在入度為0的場景結點。證明略。

選擇入度為0的一個或多個場景作為起始結點，尋求最長路徑，再判斷處理。

如果圖中只有一個入度為0的結點，則作為單源最長路徑求解；如果有多個入度為0的結點，則分別作為源結點求最長路徑，然后在多條路徑中選擇最長路徑。

下面算法是對無環有向圖求單源最長路徑，采用廣度優先搜索。然后找出最長路徑。算法如下：

（1） 根據廣度優先算法標記每一個結點到源結點的距離并按距離的大小形成隊列。具體過程略。

（2） 從距離最大的結點開始按距離遞減順序搜索父結點，直至到源結點，形成路徑。

輸入：排序后的場景隊列，按開始場景的距離降序排列；

輸出：最長路徑。

過程：path（R）

1. P ：= [?]

2. ENQUEUE（P，R.first）

3. d ：= R.first.d

4. for each vertex u in R

5. d ：= d-1

6. if u.d == d && u == P.last.super then

7. ENQUEUE（P，u）

8. end if

9. end for

10. return P

3 討論與比較

對一個場景蘊含圖G的系統化處理方法如下：

情形1，不連通。有2種方案可選：

方案1：子圖分割，形成多個連通子圖，再分別對各連通子圖按情形2處理。

方案2：在圖中添加第2.1節討論的簡單切換邊，每條邊添加邊權值，邊權值表示切換代價，蘊含邊的權值是新建對象和轉入子狀態操作的代價，形成一個賦權有向圖，再求解貨郎擔問題，即遍歷所有場景一次且僅一次，而且路徑邊權之和最小。

情形2，連通。求最長路徑P，然后在圖G中去掉P中結點和邊，剩下子圖若連通則繼續求最長路徑，若不連通則按情形1的子圖分割處理。

與其他相關方法進行比較見表1。

4 實例驗證

將該方法應用于一個軟件測試實例，被測功能是開發人員持續上傳新版本移動應用程序，使移動用戶能持續更新版本。

功能需求：對于一個移動應用程序，服務器僅保留最新版本，包括一個apk文件，一個xml文件記錄當前版本號以及版本說明。apk的版本號應與xml中版本號一致。開發人員上傳新版本時，應在頁面上輸入新版本號及版本說明，然后上傳apk文件。頁面輸入信息將記錄到xml文件中。

根據以上功能需求可識別該測試的基本流與備選流，描述如表2所示。

將基本流和備選流組合形成9個測試場景，如表3所示。分析場景間蘊含關系，形成場景蘊含圖，如圖3所示。為展示清楚，省略一些間接蘊含關系。對圖3計算最長路徑：場景6→場景5→場景7→場景1→場景4→場景8→場景9。該路徑未覆蓋場景3和2。根據第3節討論應構建賦權有向圖。

先確定權值量化規則如下：

（1） 添加或修改一個頁面屬性權值為1；

（2） 打包apk權值為5；

（3） 設置網絡權值為3。

然后構建賦權有向圖，如圖4所示。

對圖4再計算路徑：場景6→場景5→場景7→場景1→場景4→場景8→場景3→場景2→場景9，此路徑邊權和為37。若9個場景簡單隨機選擇，經計算其平均邊權和為106。此實例的優化率為[106-37106]=65%。采用文獻[5]的優化率為44%。

5 結 語

本文從測試場景的結構特征的角度，定義了場景蘊含關系，基于蘊含關系提出一種多場景測試路徑優化方法，并給出針對場景蘊含圖SIG的系統化解決方法。該方法適用于多場景測試，尤其是場景切換代價較大的嵌入式分布式系統測試。

參考文獻

[1] 杜慶峰.高級軟件測試技術[M].北京：清華大學出版社，2011.

[2] JACOBSON I. Object oriented software engineering： a use case driven approach [M]. USA： ACM Press， 1992.

[3] JACOBSON I. Basic use?case modeling [J]. The Road to the Unified Software Development Process， 2000， 18： 167?172.

[4] KIM Y， CARLSON C R. Scenario based integration testing for object?oriented software development [C]// Proceedings of 1999 Eighth Asian Test Symposium. [S.l.]： IEEE， 1999： 283?288.

[5] 潘建勇，陳邦興.基于場景的測試用例設計方法研究[J].通信技術，2012，44（12）：77?80.

[6] 劉春玲，雷海紅.基于場景的信息系統黑盒測試方法[J].信息與電子工程，2012，10（4）：509?512.

[7] 劉佳，尹治本.基于對象狀態的面向對象軟件測試方法研究[J].電腦知識與技術，2008，4（35）：2169?2170.

[8] 方世昌.離散數學[M].北京：高等教育出版社，2000.

[9] ADLEMAN L M. Molecular computation of solutions to combinatorial problems [J]. Science?AAAS?Weekly Paper， 1994， 266（5187）： 1021?1023.