基于NSGA-II的信息物理系統(tǒng)RESTful API測(cè)試套件最小化

燕嘉誠(chéng)，印凱歐

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211100)

0 引 言

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于指標(biāo)的多目標(biāo)優(yōu)化算法使用性能評(píng)價(jià)指標(biāo)來(lái)引導(dǎo)搜索過(guò)程和對(duì)解的選擇過(guò)程。評(píng)價(jià)指標(biāo)是用于評(píng)價(jià)不同多目標(biāo)優(yōu)化算法性能的量化工具，可以分為收斂性、分布性和綜合性3大類。

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

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

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

在多目標(biāo)優(yōu)化問(wèn)題中，問(wèn)題的最優(yōu)解稱為Pareto最優(yōu)解[18]。當(dāng)一個(gè)優(yōu)化問(wèn)題存在m個(gè)相互沖突的優(yōu)化目標(biāo)時(shí)，優(yōu)化目標(biāo)可以表示為：

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 RESTful API功能分級(jí)

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

傳統(tǒng)軟件測(cè)試中，并不存在對(duì)故障類型進(jìn)行分級(jí)處理的先例，只有對(duì)實(shí)際系統(tǒng)進(jìn)行測(cè)試時(shí)會(huì)評(píng)估故障的嚴(yán)重級(jí)別；平均故障檢測(cè)百分比和測(cè)試用例執(zhí)行時(shí)間則是比較常見(jiàn)的評(píng)估測(cè)試用例的指標(biāo)。

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

3.3.1 故障嚴(yán)重級(jí)別

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

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

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

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

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

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

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

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

2)賦值類型錯(cuò)誤。測(cè)試用例中的賦值類型錯(cuò)誤而導(dǎo)致故障。案例中表現(xiàn)為當(dāng)調(diào)用某一API時(shí)賦值類型出錯(cuò)會(huì)導(dǎo)致該API無(wú)法正常被調(diào)用。

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

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

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

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

表1 故障類型及分級(jí)

3.3.2 平均故障檢測(cè)百分比

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

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

(2)

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

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

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

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

4 實(shí)驗(yàn)及結(jié)果

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

表2 API名稱、種類和功能

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

本實(shí)驗(yàn)的目的是通過(guò)上文給出的3個(gè)優(yōu)化目標(biāo)，使用NSGA-Ⅱ算法對(duì)測(cè)試套件進(jìn)行優(yōu)化處理，最終從這1000個(gè)測(cè)試用例中篩選出性能相對(duì)更好的測(cè)試用例從而達(dá)到測(cè)試套件最小化的目標(biāo)。

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 算法設(shè)置

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

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

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

圖2 NSGA-Ⅱ流程圖

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

圖3 編碼方式

4.3 統(tǒng)計(jì)測(cè)試及評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

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

反世代距離評(píng)價(jià)指標(biāo)[23](Inverted Generational Distance, IGD)是一個(gè)綜合性能評(píng)價(jià)指標(biāo)。它主要通過(guò)計(jì)算每個(gè)在真實(shí)Pareto前沿面上的點(diǎn)(個(gè)體)到算法獲取的個(gè)體集合之間的最小距離和，來(lái)評(píng)價(jià)算法的收斂性能和分布性能。值越小，算法的綜合性能包括收斂性和分布性能越好。

IGD的計(jì)算公式如下：

(3)

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

4.4 實(shí)驗(yàn)方法

本文采取上文中的算法設(shè)置和評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行實(shí)驗(yàn)處理及數(shù)據(jù)分析，實(shí)驗(yàn)總體步驟如下：

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

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

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

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

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

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

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

圖4 測(cè)試套件最小化框架

4.5 實(shí)驗(yàn)結(jié)果分析

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

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

圖5 故障嚴(yán)重級(jí)別

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

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

圖6 平均故障檢測(cè)百分比

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

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

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

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

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

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

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

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

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

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