燕嘉誠，印凱歐

(南京航空航天大學計算機科學與技術學院，江蘇 南京 211100)

0 引 言

信息物理系統(tǒng)[1](Cyber-Physical System， CPS)是將計算、通信和過程控制技術緊密結(jié)合的自治系統(tǒng)，通過為物理對象配備與信息設備的接口，實現(xiàn)大型工程系統(tǒng)的實時感知、動態(tài)控制和信息服務。采用RESTful[2]風格定義信息物理系統(tǒng)中的接口，可以輕松實現(xiàn)跨平臺調(diào)用，讓使用不同編程語言的用戶都能夠訪問調(diào)用信息物理系統(tǒng)中的資源。

對于信息物理系統(tǒng)中的RESTful API[2]，通常會開發(fā)出一個測試套件來進行測試。但是隨著信息物理系統(tǒng)中RESTful API數(shù)量的增加，測試用例的數(shù)量也會隨之增加?？紤]時間和資源成本，實際上不可能執(zhí)行所有的測試用例。因此，有必要尋找一種解決方案，在執(zhí)行測試用例之前有效地最小化測試套件，以降低測試成本[3]。

測試套件最小化[3](Test Suite Minimization， TSM)存在2個潛在問題：1)最小化的測試套件可能不能夠覆蓋所有測試功能(即測試需求)；2)最小化的測試套件可能比原始測試套件具有更低的故障檢測能力。因此，在實際的測試工作中，需要基于各種成本(例如，測試用例的執(zhí)行時間)和有效性標準(例如，故障檢測能力)來篩選測試用例。測試用例選擇[4]的總體目標是選擇能夠在有限時間預算內(nèi)執(zhí)行的測試用例，同時最佳地滿足各種成本和效率目標。

基于搜索的軟件工程[4](Search-Based Software Engineering， SBSE)是傳統(tǒng)軟件工程和人工智能相結(jié)合的研究領域，SBSE運用元啟發(fā)式搜索優(yōu)化算法，在問題的候選解組成的空間中展開搜索，切實有效地解決軟件工程相關問題。在解決多目標優(yōu)化問題的時候，選取基于搜索的優(yōu)化算法，通過適應度函數(shù)的構(gòu)建來指導搜索，能夠?qū)ふ易顑?yōu)解或接近最優(yōu)的解，能夠自動化和智能化地解決問題。

由于RESTful API通常應用于Web端的設計，測試人員可以訪問代碼，所以大多采用白盒測試的方法。對于信息物理系統(tǒng)中RESTful API的測試，測試人員并不清楚程序內(nèi)部的編寫內(nèi)容，關注的更多是對功能需求的測試，必須采取黑盒測試方法，所以對于優(yōu)化目標的選取與傳統(tǒng)的測試優(yōu)化存在一定差異。

通過研究發(fā)現(xiàn)，用于測試信息物理系統(tǒng)中RESTful API的測試套件中通常存在冗余測試用例，消除冗余測試用例可以降低測試的執(zhí)行成本(測試最小化)。測試最小化需要同時滿足測試需求以及高故障檢測能力。因此面臨著一個挑戰(zhàn)，需要在保證測試套件的高故障檢測能力和功能覆蓋的同時減少測試成本和開銷。

基于上述挑戰(zhàn)，本文的目標問題是一個多目標優(yōu)化問題，多目標優(yōu)化算法可以被用來解決這一問題。本文首先根據(jù)信息物理系統(tǒng)的特性，定義了3個優(yōu)化目標：故障嚴重級別(Fault Severity Level)、平均故障檢測百分比(Average Percentage of Fault Detected)以及測試用例執(zhí)行時間(Test Case Execution Time)；其次，通過對比不同多目標優(yōu)化算法的適用條件，本文選擇使用NSGA-Ⅱ[5]算法對上述3個目標進行優(yōu)化；最后，本文通過一個真實案例研究，使用NSGA-Ⅱ[5]算法對測試套件進行最小化處理，比較了NSGA-Ⅱ和Random Search(RS)同時應用于測試套件時的性能。

本文的貢獻在于：1)針對信息物理系統(tǒng)中RESTful API的特性定義了3個優(yōu)化目標；2)基于案例研究，通過與Random Search對比，評估NSGA-Ⅱ用于測試套件最小化的性能表現(xiàn)。

1 相關工作

目前，大部分對于RESTful API的測試研究工作都是基于其在Web端的應用的，并沒有一種專門用來測試信息物理系統(tǒng)中RESTful API的方法。

測試Web服務中的RESTful API的方法有很多種，其中，Segura等人[6]主張采用蛻變測試的方法，提出了6個抽象關系，它們捕捉了RESTful網(wǎng)絡應用程序接口中發(fā)現(xiàn)的許多蛻變關系的形狀并稱之為蛻變關系輸出模式(MROPs)。然后，每個MROP可以被實例化為一個或多個具體的蛻變關系。該方法使用6個網(wǎng)絡應用程序接口中的真實錯誤進行評估。

Arcuri等人[7]提出了一種全自動的白盒測試方法，使用進化算法自動生成測試用例。該方法的優(yōu)化目標是語句的覆蓋度、代碼間分支的覆蓋度和不同API端口返回的HTTP狀態(tài)代碼，通過分析處理調(diào)用API后Web端返回的HTTP狀態(tài)碼，構(gòu)建適應度函數(shù)。測試用例的篩選排序是基于代碼覆蓋率和錯誤發(fā)現(xiàn)度量來進行的。

Dipesh等人[4]定義了一個適應度函數(shù)，包括一個成本度量：時間差(TD)和3個有效性度量：平均優(yōu)先級(MPR)、平均概率(MPO)和平均結(jié)果(MC)，評估了8種多目標搜索算法的性能。通過2組案例的評估，證明了基于搜索的測試用例優(yōu)化算法表現(xiàn)都要好于Random Search算法，這為本文的算法選擇提供了指引。

測試套件最小化技術的應用很廣泛，研究中最常見的測試集最小化技術是貪婪算法[8]的變體，該算法已被證明是有效的啟發(fā)式算法。貪婪算法的2個眾所周知的擴展[9]是Greedy Essential(貪婪本質(zhì))算法和Greedy Redundant Essential(貪婪冗余本質(zhì))算法。Chen和Lau[8]將這2個貪婪算法的變種與另一個啟發(fā)式算法HGS[10](Harrold-Gupta-Soffa)進行了比較。他們的結(jié)果表明，HGS算法可以在不嚴重影響測試集縮減程度的情況下，顯著提高減少測試集的故障檢測效率，相比GE和GRE算法效果明顯更好。

Zhang等人[11]提出了一個基于模型和搜索的測試用例生成和最小化框架(UncerTest)，用于測試不確定環(huán)境下的信息物理系統(tǒng)。UncerTest利用了不確定性理論和基于搜索的優(yōu)化技術，在此基礎上提出了一套創(chuàng)新的與不確定性相關的測試用例最小化策略。通過2個工業(yè)信息物理系統(tǒng)案例和8個常用的多目標搜索算法對UncerTest進行了評估，與其他測試策略相比，他們的測試策略能夠發(fā)現(xiàn)比平均多51%的由于未知不確定性來源而導致的不確定性。

Zhang等人[12]使用真實的JUnit測試套件研究Java程序的測試套件最小化技術，對4個現(xiàn)實中的Java程序的19個版本進行了實證研究，并發(fā)現(xiàn)在相同的項目上使用測試套件縮減時，故障檢測的損失很小。Wong等人[13]還發(fā)現(xiàn)，測試套件最小化對測試套件檢測故障能力的影響可以忽略不計，這對本文設定平均故障檢測百分比作為優(yōu)化目標提供了支持。

在本文的研究中，對信息物理系統(tǒng)中RESTful API的測試采取了黑盒測試的方法，使用了與Wang等人[14]相似的方法來精簡測試用例集。通過定義優(yōu)化目標對測試套件使用多目標優(yōu)化算法進行最小化處理。重點是將多目標優(yōu)化問題通過人為設置權(quán)重系數(shù)的方法轉(zhuǎn)化為一個單目標優(yōu)化問題，對3個優(yōu)化目標在最小化測試套件前后的性能進行比較分析。人為設置的權(quán)重系數(shù)來自其工業(yè)界合作伙伴的歷史數(shù)據(jù)，根據(jù)分析用戶的需求以及偏好得出數(shù)據(jù)，因此人為設置權(quán)重系數(shù)是可行的。由于本文的被測對象不存在歷史數(shù)據(jù)的參考，無法合理地人為設置各優(yōu)化目標的權(quán)重系數(shù)，且本文針對信息物理系統(tǒng)特性提出的3個優(yōu)化目標也與文獻[14]的不盡相同，故選擇采用基于支配關系的多目標優(yōu)化算法NSGA-Ⅱ?qū)y試套件進行最小化處理。

2 多目標優(yōu)化算法

現(xiàn)實世界中的優(yōu)化問題通常是多屬性的，一般是對多個目標的同時優(yōu)化。多數(shù)情況下，被同時優(yōu)化的多個目標之間是相互作用且相互沖突的，這就需要對相互沖突的子目標進行綜合考慮。多目標優(yōu)化算法就是用來解決多個目標之間的協(xié)同優(yōu)化問題的。

多目標優(yōu)化算法[15]大致可以分為3類：基于分解的多目標優(yōu)化算法、基于指標的多目標優(yōu)化算法和基于支配關系的多目標優(yōu)化算法。

2.1 基于分解的多目標優(yōu)化算法

在處理多目標優(yōu)化問題的時候，最直接的方法，也是比較早期所使用的方法就是聚集函數(shù)方法。這種方法對被優(yōu)化的所有子目標設置權(quán)重系數(shù)，再將它們組合或者聚集為一個單目標，從而將多目標優(yōu)化問題轉(zhuǎn)化為單目標的優(yōu)化問題。

Zhang等人[16]基于分解思想，提出了基于分解的多目標優(yōu)化算法，將數(shù)學規(guī)劃方法和進化算法相結(jié)合，把一個多目標優(yōu)化問題分解為一組單目標的子問題或多個多目標的子問題，利用子問題之間的鄰域關系，通過協(xié)作的方式優(yōu)化所有子問題。

2.2 基于指標的多目標優(yōu)化算法

基于指標的多目標優(yōu)化算法使用性能評價指標來引導搜索過程和對解的選擇過程。評價指標是用于評價不同多目標優(yōu)化算法性能的量化工具，可以分為收斂性、分布性和綜合性3大類。

Zitzler[17]于2004年提出了一個通用的基于指標的進化算法IBEA，算法思想是使用一個任意的指標來評價和比較一對候選解的性能。Basseur和Zitzler提出了一個用于解決不確定性問題的基于指標的模型，其中每個個體被賦予一個在目標空間中的概率值，在不確定環(huán)境中討論一些用來計算期望指標值的方法，并且提出和實證研究了一些基于指標模型的變種模型。

2.3 基于支配關系的多目標優(yōu)化算法

基于支配關系的多目標優(yōu)化算法的基本思路是利用基于Pareto的適應度分配策略，從當前的群體中尋找出所有的非支配個體。

在多目標優(yōu)化問題中，問題的最優(yōu)解稱為Pareto最優(yōu)解[18]。當一個優(yōu)化問題存在m個相互沖突的優(yōu)化目標時，優(yōu)化目標可以表示為：

f(x)=(f1(x)，f2(x)，…，fm(x))s.t.x∈Ω

(1)

其中，Ω為滿足多目標優(yōu)化中2個約束的可行解集，被稱為決策變量空間。

對于一個給定的多目標優(yōu)化問題maxf(x)，若x*∈Ω，且不存在其他的x∈Ω，使得fi(x*)≤fi(x)(i=1，2，…，m)成立，且其中至少一個是嚴格不等式，則稱x*是maxf(x)的Pareto最優(yōu)解。

在多數(shù)情況下，Pareto最優(yōu)解可能不止一個，而是一個包含所有Pareto最優(yōu)解的Pareto最優(yōu)解集。

NSGA-Ⅱ[5]算法是基于支配關系的多目標優(yōu)化算法，是Srinivas和Deb于2000年在NSGA的基礎上提出的，它比NSGA(Non-Dominated Sorting In Genetic Algorithm)算法性能更加優(yōu)越：NSGA-Ⅱ算法采用了快速非支配排序算法，其計算復雜度相比NSGA算法大大降低；采用了擁擠度和擁擠度比較算子，代替了需要指定的共享半徑shareQ，并在快速排序后的同級比較中作為勝出標準，使得準Pareto域中的個體能夠擴展到整個Pareto域，并均勻分布，保持了種群的多樣性；引入了精英策略，擴大了采樣空間，防止最佳個體的丟失，提高了算法的運算速度和魯棒性。

因為NSGA-Ⅱ算法在多目標優(yōu)化問題中被廣泛使用[19]，并且在無法確定信息物理系統(tǒng)中RESTful API優(yōu)化目標的權(quán)重系數(shù)和評價指標的時候，NSGA-Ⅱ算法相較于前2種優(yōu)化算法，采用精英保留策略，能夠根據(jù)優(yōu)化目標快速篩選出非支配解集，使得非支配解集兼顧各個優(yōu)化目標。故NSGA-Ⅱ算法適用于信息物理系統(tǒng)中RESTful API的測試用例的優(yōu)化篩選。

3 信息物理系統(tǒng)中RESTful API的優(yōu)化目標

信息物理系統(tǒng)中RESTful API的測試用例設計需要考慮到其應用場景的特性，對優(yōu)化目標的選取也需要對信息物理系統(tǒng)與傳統(tǒng)軟件的區(qū)別進行分析總結(jié)。

3.1 信息物理系統(tǒng)中RESTful API特性

針對信息物理系統(tǒng)中RESTful API與Web端中RESTful API的區(qū)別，其特性被總結(jié)歸納為以下5點：

1)RESTful API的編寫代碼不可見。對于Web端中RESTful API而言，其源碼獲取情況不明確。信息物理系統(tǒng)中RESTful API只能作為調(diào)用接口供開發(fā)測試人員使用，其內(nèi)部代碼不可訪問，無法獲取。

2)測試輸入形式不同。Web端中RESTful API的測試用例是根據(jù)Swagger UI編寫，測試輸入多為GET、POST等動作，不需要具體的輸入數(shù)據(jù)。信息物理系統(tǒng)中RESTful API的測試輸入可以是GET、POST等動作，也可以是具體數(shù)據(jù)。如測試車輛速度功能API時，測試輸入是隨機選取車輛速度限制范圍中的某一具體數(shù)值。

3)Test Oracle問題。信息物理系統(tǒng)中RESTful API的Test Oracle問題需要根據(jù)實際的測試輸入決定assertion語句的編寫。

4)時延。調(diào)用RESTful API需要連接實際目標，通信、響應以及信息物理系統(tǒng)的硬件反饋需要一定時間。

5)故障類型需要根據(jù)實際情況分類。測試信息物理系統(tǒng)中RESTful API時出現(xiàn)的故障與傳統(tǒng)軟件測試中發(fā)現(xiàn)的錯誤存在不同，如信息物理系統(tǒng)的故障可能是受其物理性能的限制，而日常的軟件測試工作中則不會出現(xiàn)這種類型的故障。

3.2 信息物理系統(tǒng)中RESTful API分級

信息物理系統(tǒng)中各RESTful API具備不同的功能和屬性，所有RESTful API的協(xié)同運作使得信息物理系統(tǒng)能夠正常運行。然而對于不同的RESTful API，其功能的重要性以及對信息物理系統(tǒng)的影響程度也是不盡相同的。需要具體分析每一個RESTful API的運行方式和實現(xiàn)邏輯，再對其劃分層級。

本文根據(jù)信息物理系統(tǒng)中RESTful API的功能，參考車輛測試大致將它們分為3個層級，分別是Strategic Level、Manoeuvring Level、Control Level。

具體分析3個層級的定義，其中Control Level屬于實現(xiàn)基礎控制功能的層級，處于RESTful API分級中的最底層。Manoeuvring Level屬于實現(xiàn)復雜操控功能的層級，處于RESTful API分級中的中間層。Strategic Level屬于實現(xiàn)策略控制功能的層級，處于RESTful API分級中的最高層。高層級中的RESTful API代表著其功能具有更復雜的實現(xiàn)邏輯，低層級中的RESTful API往往被視為組成信息物理系統(tǒng)的基礎。

圖1 RESTful API功能分級

3.3 優(yōu)化目標選取

傳統(tǒng)軟件測試中，并不存在對故障類型進行分級處理的先例，只有對實際系統(tǒng)進行測試時會評估故障的嚴重級別；平均故障檢測百分比和測試用例執(zhí)行時間則是比較常見的評估測試用例的指標。

基于上述問題，本文提出了信息物理系統(tǒng)中RESTful API的測試用例的3個優(yōu)化目標。

3.3.1 故障嚴重級別

在測試信息物理系統(tǒng)中的RESTful API時，執(zhí)行一個測試用例會多次產(chǎn)生多個測試結(jié)果。當測試結(jié)果與預期結(jié)果不一致時，將從測試用例結(jié)果中檢測到故障。面對這些故障，需要嘗試找出每個故障的原因，并分析其對信息物理系統(tǒng)運行的影響，然后對這些故障進行分類，以確定發(fā)生故障的嚴重性，并據(jù)此分析測試用例的優(yōu)先級。

由于信息物理系統(tǒng)與傳統(tǒng)軟件的測試存在差異，二者對于故障的分級也存在著不同。參考軟件測試中故障的嚴重級別劃分[20]，本文把信息物理系統(tǒng)中出現(xiàn)的故障大致分為4個級別,4個故障等級分別是致命故障、嚴重故障、一般故障和輕微故障，故障等級定義如下：

1)輕微故障。對信息物理系統(tǒng)的功能沒有影響或外部干擾導致的故障視為輕微故障。

2)一般故障。對信息物理系統(tǒng)的整體運行沒有影響，只對部分功能產(chǎn)生影響的故障視為一般故障。

3)嚴重故障。對信息物理系統(tǒng)的整體運行有一定影響且對部分功能產(chǎn)生影響的故障視為嚴重故障。

4)致命故障。對信息物理系統(tǒng)的整體運行產(chǎn)生重大影響，進而導致整個信息物理系統(tǒng)崩潰的故障視為致命故障。

結(jié)合實驗中的案例分析，案例中一共出現(xiàn)了5個故障類型，分別是環(huán)境影響、賦值類型錯誤、超出邊界值、API運行的充分條件不滿足以及其他API調(diào)用沖突，具體分析故障類型及故障產(chǎn)生原因如下：

1)環(huán)境影響。測試環(huán)境中出現(xiàn)的突發(fā)狀況或場地條件限制而導致故障。案例中表現(xiàn)為測試環(huán)境中突然出現(xiàn)的動物或行人影響車輛的功能實現(xiàn)。

2)賦值類型錯誤。測試用例中的賦值類型錯誤而導致故障。案例中表現(xiàn)為當調(diào)用某一API時賦值類型出錯會導致該API無法正常被調(diào)用。

3)超出邊界值。測試用例中的賦值超出API的數(shù)值范圍而導致故障。案例中表現(xiàn)為當調(diào)用某一API時給它的賦值超出該API的取值范圍，測試用例的斷言會報錯。

4)API運行的充分條件不滿足。某一API正常工作需要調(diào)用其他API運行，當被調(diào)用的API出現(xiàn)故障時導致該API無法正常工作而導致故障。案例中表現(xiàn)為定速巡航API需要調(diào)用前進API才能實現(xiàn)自身功能，當前進API出現(xiàn)故障時會導致定速巡航API也無法正常工作。

5)其他API調(diào)用沖突。調(diào)用某一API之前調(diào)用其他功能API導致出現(xiàn)沖突而導致故障。案例中表現(xiàn)為在調(diào)用前進API之前先調(diào)用后退API，當再次調(diào)用前進API時會出現(xiàn)車輛無法前進只能后退的嚴重故障，并且此時車輛的所有前進功能都被默認更改為后退。

將案例中信息物理系統(tǒng)中RESTful API出現(xiàn)的故障類型進行總結(jié)并分級如表1所示。

表1 故障類型及分級

3.3.2 平均故障檢測百分比

平均故障檢測百分比[14，21](Average Percentage of Fault Detected)是用來評判測試用例的故障檢測能力的重要參數(shù)。如果一個測試用例能夠在有限的執(zhí)行次數(shù)中多次檢測到故障，那么它被定義為成功；如果它沒有檢測到任何錯誤，那么它被定義為失敗。

測試用例的平均故障檢測百分比[14](APFD)可以用下面的方法來衡量：

(2)

其中，APFD是平均故障檢測百分比；NumSuctci給定執(zhí)行次數(shù)內(nèi)測試用例i的執(zhí)行成功的次數(shù)；NumFailtci給定執(zhí)行次數(shù)內(nèi)測試用例i的執(zhí)行失敗的次數(shù)。

例如，如果一個測試用例被執(zhí)行了100次，其中80次能夠發(fā)現(xiàn)故障，20次沒有發(fā)現(xiàn)故障，則該測試用例的平均故障檢測百分比就是80/100=80%。

3.3.3 測試用例執(zhí)行時間

由于信息物理系統(tǒng)的測試環(huán)境較為復雜且需要進行實物測試，需要大量的測試資源和開銷。但是實際中測試的時間成本有限，測試用例執(zhí)行時間[4]是非常重要的一個考量因素，可以用來評估一個測試用例的優(yōu)劣。若多個測試用例在執(zhí)行后均能發(fā)現(xiàn)同一故障，則其中執(zhí)行時間最短的測試用例會被視為性能較好的。

4 實驗及結(jié)果

本文的研究案例是Simplexity實驗室的智能車。該信息物理系統(tǒng)中的9個功能接口均使用RESTful風格定義，通過調(diào)用這9個RESTful API，測試人員能遠程對該信息物理系統(tǒng)進行測試、控制。實驗中涉及9個被測的RESTful API，具體功能和名稱如表2所示。

表2 API名稱、種類和功能

該案例中測試套件包含1000個測試用例，這1000個測試用例包含了上述全部9個RESTful API。其中，根據(jù)RESTful API功能優(yōu)先級不同，各個RESTful API的測試用例數(shù)量也存在差異。Control類的每個RESTful API存在70個測試用例，Manouvring類的每個RESTful API存在90個測試用例，Stragtegic類的每個RESTful API存在320個測試用例。本文通過在遠程的電腦端調(diào)用RESTful API的方法執(zhí)行測試用例，觀察實際車輛的表現(xiàn)和測試用例的反饋。

本實驗的目的是通過上文給出的3個優(yōu)化目標，使用NSGA-Ⅱ算法對測試套件進行優(yōu)化處理，最終從這1000個測試用例中篩選出性能相對更好的測試用例從而達到測試套件最小化的目標。

4.1 實驗環(huán)境

實驗采用在仿真環(huán)境中模擬與現(xiàn)實環(huán)境中測試相結(jié)合的方式，使用的是南京航空航天大學Simplexity實驗室的計算機集群以及Airsim仿真環(huán)境，實物車輛使用的是Simplexity實驗室的智能車。

4.2 算法設置

實驗采用了jMetalPy框架，并使用了其內(nèi)置的NSGA-Ⅱ算法。NSGA-Ⅱ算法的參數(shù)選擇使用了jMetalPy的默認設置，交叉操作的交叉率為1.0，變異操作的變異率為1.0?？紤]實驗運行的時間成本，本文將人口規(guī)模設置為100，初始種群是隨機選取的，子代數(shù)也設置為100。本文通過預實驗分析了NSGA-Ⅱ的性能趨勢，并得出結(jié)論，它大致收斂于第350代。因此，本文將適應性評估的數(shù)量固定為35000(100×350)作為終止標準。

本文選取Random Search(RS)作為比較基線，RS的適應性評估總數(shù)與NSGA-Ⅱ終止條件一致。由于其固有的隨機性，NSGA-Ⅱ和RS都各運行了30次。

NSGA-Ⅱ的實現(xiàn)流程如圖2所示。

圖2 NSGA-Ⅱ流程圖

編碼方式：種群采用二進制編碼方式，用0、1代表測試用例的選擇與否。例如，個體x1和x2分別包含9個測試用例T1～T9，編碼方式如圖3所示。

圖3 編碼方式

4.3 統(tǒng)計測試及評價標準

為了比較結(jié)果和給定的閾值，根據(jù)隨機算法的統(tǒng)計檢驗報告指南，本文使用了12和p-value方法[22]：

p-value：采用非參數(shù)U檢驗(The Mann-Whitney U test)計算p值，以此判斷2種算法是否存在顯著差異。本文選擇的顯著性水平為0.05，即p值小于0.05時存在顯著性差異。

為了評價實驗中采用NSGA-Ⅱ算法最小化前后測試套件的性能，本文根據(jù)3個優(yōu)化目標的選擇使用了3個評價指標，即故障嚴重值、故障檢測百分比以及測試用例執(zhí)行時間。

本文將4個故障嚴重級別按輕微故障、一般故障、嚴重故障和致命故障從低到高分別賦值，其中輕微故障的值為1；一般故障的值為2；嚴重故障的值為3；致命故障的值為4。

平均故障檢測百分比可以根據(jù)公式(2)計算得到，測試用例執(zhí)行時間根據(jù)每個測試用例的實際運行時間取整后得到數(shù)據(jù)。

反世代距離評價指標[23](Inverted Generational Distance, IGD)是一個綜合性能評價指標。它主要通過計算每個在真實Pareto前沿面上的點(個體)到算法獲取的個體集合之間的最小距離和，來評價算法的收斂性能和分布性能。值越小，算法的綜合性能包括收斂性和分布性能越好。

IGD的計算公式如下：

(3)

其中，P為均勻分布在真實Pareto面上的點集，|P|為分布在真實Pareto面上的點集的個體數(shù)。Q為算法獲取的最優(yōu)解集。而d(v,Q)為P中個體v到種群Q的最小歐幾里得距離。

4.4 實驗方法

本文采取上文中的算法設置和評價標準進行實驗處理及數(shù)據(jù)分析，實驗總體步驟如下：

1)將測試套件中的1000個測試用例每個執(zhí)行30次并收集數(shù)據(jù)。

2)根據(jù)收集的數(shù)據(jù)分析案例中測試用例執(zhí)行后產(chǎn)生的故障，并具體分級如表1所示。

3)根據(jù)收集的數(shù)據(jù)計算出測試用例執(zhí)行時間和平均故障檢測百比。

4)使用NSGA-Ⅱ算法對測試用例進行多目標優(yōu)化并篩選得到最小化后的測試套件。

5)根據(jù)3個優(yōu)化目標的數(shù)據(jù)對比評估原始測試套件、使用Random算法選取的測試套件與使用NSGA-Ⅱ最小化后的測試套件的性能差異。

其中，每個測試用例執(zhí)行30次可以避免出現(xiàn)由于環(huán)境因素等導致的偶然故障并收集更為準確的數(shù)據(jù)。

圖4所示為使用NSGA-Ⅱ?qū)y試套件最小化處理的總體框架。

圖4 測試套件最小化框架

4.5 實驗結(jié)果分析

采用4.4節(jié)中的實驗步驟，通過將案例中提供的1000個測試用例重復執(zhí)行30次后得到30000個執(zhí)行結(jié)果，計算出每個測試用例相應的執(zhí)行時間、平均故障檢測百分比，分析出故障嚴重級別，再通過NSGA-Ⅱ算法對3個優(yōu)化目標進行優(yōu)化，最后得到的測試用例構(gòu)成最小化后的測試套件。

本文首先將使用NSGA-Ⅱ最小化后的測試套件與原始套件在3項優(yōu)化目標中表現(xiàn)的平均值進行對比。

圖5 故障嚴重級別

對于信息物理系統(tǒng)中的每一個RESTful API，分別計算出原始測試套件發(fā)現(xiàn)故障嚴重級別的值以及使用NSGA-Ⅱ最小化后的測試套件發(fā)現(xiàn)的故障嚴重級別的平均值。將二者的數(shù)值進行對比，根據(jù)圖5可以直觀地發(fā)現(xiàn)：對于信息物理系統(tǒng)中的每一個RESTful API來說，最小化后的測試套件所發(fā)現(xiàn)的故障嚴重級別的最大值與原始測試套件相同，但無論是比較最小值或中位數(shù)，最小化后的測試套件的得分均明顯高于原始測試套件。這說明原始的測試套件在經(jīng)過最小化處理后，獲得了更強的發(fā)現(xiàn)高級別故障的能力。

通過計算出原始測試套件和使用NSGA-Ⅱ最小化后的測試套件的平均故障檢測百分比，將二者進行對比，可以發(fā)現(xiàn)如圖6所示：9個API的平均故障檢測百分比的最大值全部相同，均為100%；使用NSGA-Ⅱ最小化后的測試套件的平均故障檢測百分比在中位數(shù)和最小值等方面均高于原始測試套件，這就說明最小化后的測試套件具有更加優(yōu)異的故障檢測能力，能夠在有限的執(zhí)行次數(shù)內(nèi)盡可能多地檢測到故障。

圖6 平均故障檢測百分比

對比原始測試套件以及使用NSGA-Ⅱ最小化后的測試套件的平均測試用例執(zhí)行時間，如圖7所示，它們最小化后的測試套件的執(zhí)行時間的最大值、最小值以及中位數(shù)全部小于等于原始測試套件的表現(xiàn)。所以相對而言，最小化后的測試套件所需要的平均測試用例執(zhí)行時間比原始套件更短，能夠為測試工作降低大量的時間成本。

表3顯示了對測試套件使用不同算法的IGD數(shù)值。比較NSGA-Ⅱ和Random Search的表現(xiàn)，NSGA-Ⅱ的A12的值都高于0.5，而其p-value的值也都低于0.05。根據(jù)4.3節(jié)的描述，基于以上結(jié)果，本文可以得出結(jié)論，對信息物理系統(tǒng)中RESTful API的測試套件使用NSGA-Ⅱ優(yōu)化后得到的全新測試套件，其性能是遠遠好于RS選擇的測試套件。

圖7 測試用例執(zhí)行時間

表3 NSGA-Ⅱ和RS性能對比結(jié)果

案例中RESTful API的原始測試套件中包含了1000個測試用例，經(jīng)過本文使用NSGA-Ⅱ?qū)?個優(yōu)化目標進行處理后，最終得到最小化后的測試套件。對比最小化后的測試套件和原始套件的故障嚴重級別、平均故障檢測百分比和測試用例執(zhí)行時間，最小化后的測試套件的性能表現(xiàn)明顯是全面優(yōu)于原始測試套件。

本文又使用Random Search選取測試用例組成新的測試套件，將其與使用NSGA-Ⅱ最小化后的測試套件比較，這說明根據(jù)確定的優(yōu)化目標對信息物理系統(tǒng)中的RESTful API的測試套件，使用NSGA-Ⅱ算法進行優(yōu)化篩選測試用例能夠提高測試套件的性能。最小化后的測試套件具有更高的故障檢測能力，且所需要的時間成本和資源開銷也更少。

原始測試套件中可能存在大量冗余重復的測試用例，通過合理的優(yōu)化目標的設置和算法處理，能夠大幅度剔除掉這部分測試用例，使得精簡后的測試套件在保留一定的故障檢測能力的同時節(jié)約測試成本。對信息物理系統(tǒng)中RESTful API的測試套件使用NSGA-Ⅱ算法進行最小化處理，獲得了性能更優(yōu)越的，包含測試用例數(shù)更少的測試套件。

5 結(jié)束語

測試套件最小化是測試領域在有限的資源下提高測試效率的主要技術之一。對于信息物理系統(tǒng)中RESTful API的測試，3個優(yōu)化目標是通過參考傳統(tǒng)軟件測試并結(jié)合信息物理系統(tǒng)的特性選取的。

實驗結(jié)果表明，使用NSGA-Ⅱ算法對測試套件進行最小化處理能夠在提高測試用例的故障檢測率、發(fā)現(xiàn)更嚴重級別的故障、減少測試用例執(zhí)行時間的同時降低測試成本。后續(xù)工作將參考其他多目標優(yōu)化問題的優(yōu)化目標選取，定義更多的優(yōu)化目標，以更好地提高測試套件的質(zhì)量。