面向條件篩選搜索系統的蛻變測試方法

韓育珍，陳軍華，高建華

(上海師范大學 計算機科學與技術系，上海 200234)

0 引 言

條件篩選搜索系統包含大量數據信息，用戶可以定制條件，以篩選并顯示滿足條件的數據信息，它需要承受大量用戶的服務請求，必須適應長期和高頻的訪問操作[1]，帶來保障服務可靠性的挑戰。傳統軟件測試技術可以有效檢測并糾正軟件中存在的故障和缺陷以應對這一挑戰，但它存在著兩大問題，即測試用例集的可靠性問題[2]和 Oracle 問題。其中，Oracle問題表示待測軟件的執行輸出結果復雜或者無法預知的情況[3]。蛻變測試(metamorphic testing)是一種有效緩解復雜系統Oracle問題的軟件測試方法[3,4]，其測試方法是檢查執行程序的多次輸入輸出是否滿足預期的蛻變關系(metamorphic relationship)。

學者們已使用蛻變測試對Oracle問題的緩解進行了初步探索，發現構建有效的蛻變關系可以幫助緩解Oracle問題[5,6]。Zhou等[6]提出通過檢查程序多次輸出之間的關系代替檢查程序的單次輸出執行測試。Segura等[3]提出了定義了等價性、等效性、子集、非交集、并集、差集6種蛻變關系輸出模式(metamorphic relationship output pattern)。Zhou等[7,8]提出了基于對稱(symmetry)的蛻變關系輸出模式。Sun等[9]提出了蛻變關系輸入模式的概念。Segura等[1]提出了輸入等價、洗牌、合并條件、析取條件、不相交的分區、完整分區和分區差異7種蛻變關系模式。

研究發現，條件篩選搜索系統降低了信息的認知負載，增加了多樣化的搜索模式。通過分析現有的蛻變關系模式在條件篩選搜索系統執行測試時檢測到的軟件設計故障及檢測效率，提出了兩種蛻變關系模式，有效提高了軟件設計的故障檢測效率。

本文的主要貢獻如下：

(1)在“合并條件”和“析取條件”兩種蛻變關系模式的基礎上提出了檢測效率更高的“IO組對稱相等”蛻變關系模式；

(2)根據條件篩選搜索系統中的多項選擇條件，提出了“交集等價”模式的概念；

(3)通過實驗驗證提出的兩種蛻變關系模式具有可操作性和適用性。

1 蛻變測試

當傳統軟件測試在遇到復雜系統Oracle問題而無法預估程序輸出結果或者程序輸出結果復雜時，測試人員難以判斷程序的輸出結果與預期結果是否一致，于是通過檢查程序多次輸入輸出之間的關系是否滿足預期構建的蛻變關系，從而驗證程序軟件設計的正確性，這種測試方法被稱為蛻變測試[10,11]。蛻變關系是源測試用例生成后續測試用例的前提，以便執行源和后續測試用例并檢查其輸出。因此，蛻變測試也被認為是一種有效的測試用例生成技術[2]。

自Chen等[12]提出檢查程序多次輸出之間的關系來執行蛻變測試以來，關于蛻變測試的應用研究不僅僅體現在搜索引擎方面[1,3,9]，而且也應用在生物信息學[13]、醫療系統[14]和機器學習[15]等領域。

蛻變測試過程如圖1所示。

圖1 蛻變測試

其中，SUT表示有a+1個輸入參數，b+1個輸出結果的待測軟件，I0表示使用傳統測試用例生成技術生成的源測試用例，Ii,i=[1,n] 是源測試用例根據蛻變關系修改輸入參數作為后續測試用例，Ij1,Ij2,…,Ija,j=[1,n] 表示源測試用例和后續測試用例的a+1個待輸入參數，O(I0) 和O(Ii) 為源測試用例和后續測試用例對應的n+1次輸出，Oj1,Oj2,…,Ojb表示O(Ij) 的b+1個輸出結果。蛻變測試是通過比較O(I0) 和O(Ii) 多個輸出結果之間的關系是否滿足構建的蛻變關系來驗證SUT的正確性。

一般地，函數f的蛻變關系表示為一系列函數輸入之間的關系I0,I1,…,In(n≥1) 及其對應的輸出值f(I0),f(I1),…,f(In) 之間的關系[16]，即蛻變關系

R={(I0,I1,…,In),(f(I0),f(I1),…,f(In))|n≥1}

其中，I0為源輸入，f(I0) 為源輸出，I1,I2,…,In為后續輸入，f(I1),f(I2),…,f(In) 成為后續輸出。

2 蛻變關系模式

蛻變測試中蛻變關系的構建和識別依賴于測試人員對程序的熟悉和了解，常規方法是檢查程序規范或者用戶文檔，并考慮如何修改程序輸入，進而在輸出中產生預期的變化[2]。但這個過程是一項手動操作過程，必須根據每個被測程序的預期功能從頭開始檢測和識別。為了減輕構建和識別蛻變關系的負擔，S. Segura等[1,3]提出了7種適用于傳統搜索引擎的蛻變關系模式：

等效性(shuffling)：表示源輸入和后續輸入相等，源輸出和后續輸出相同但是順序相等或不相等的關系。

等價性(input equivalence)：指的是源輸入和后續輸入等價，源輸出和后續輸出相同且順序也相等的關系。該關系模式是上一個關系模式的子集。

合并條件(conjunctive conditions)：表示在源輸入的基礎上，搜索條件不斷增加作為多次后續輸入，其對應的輸出都是前一次輸出的子集。

析取條件(disjunctive conditions)：表示在源輸入的基礎上，搜索條件不斷減少作為多次后續輸入，其相應的輸出關系可以概括為前一次輸出是后一次輸出的子集。該關系模式是在上一個關系模式的基礎上對稱定義的。

不相交的分區(disjoint partitions)：表示源輸入和后續輸入無交集，且對應的源輸出和后續輸出交集為空集的關系。

完整分區(complete partitions)：表示源輸入是所有后續輸入的并集，源輸出與所有后續輸出并集相等的關系。該關系模式與上一個關系模式的定義分別源自于關系代數中的交集與并集。

分區差異(partiton difference)：表示后續輸出之間兩兩不相交，但是都屬于源輸出子集的關系，在創建和更新的任務列表中比較常見。

通過對條件篩選搜索系統的了解和熟悉，分析改進了“合并條件”和“析取條件”模式，提出了“IO組對稱相等”模式，并且根據條件篩選搜索系統的多項選擇搜索模式在“等價性”和“完整分區”模式的基礎上提出了“交集等價”模式。接下來，引入改進提出的兩種蛻變關系模式，并使用數學關系表示，在下面的關系式中I0為源輸入，O為源輸出。Ii為后續輸入，Oi為后續輸出。

2.1 IO組對稱相等

IO組對稱相等模式是在“合并條件”和“析取條件”模式的基礎上改進的,將程序中的多次輸入作為一個源輸入組，將源輸入組中的多次輸入對稱得到一個后續輸入組，源輸出組和后續輸出組對稱等價。但源輸入組和源輸出組中的多次輸入輸出應該滿足“合并條件”模式指定的關系，后續輸入組和后續輸出組中的多次輸入輸出應滿足“析取條件”模式指定的關系。如式(1)所示，數學關系表示為

I0=I01、I02、…、I0n,I1=I11、I12、…、I1n，且I11=I0n，I12=I0(n-1)，…,I1n=I01?
O0=O01、O02、…、O0n,
O1=O11、O12、…、O1n，n≥1
且O11=O0n,O12=O0(n-1),…,O1n=O01

(1)

同時應滿足I01?I02?…?I0n，I11?I12?…?I1n，O01?O02?…?O0n，O11?O12?…?O1n。

例如：源輸入測試用例組中的3次輸入分別為I01=電腦、I02=筆記本電腦、I03=戴爾筆記本電腦，滿足I01?I02?I03, 對應的源測試用例組輸出結果為O01、O02、O03, 且應滿足O01?O02?O03， 后續輸入測試用例組的3次輸入分別為I11=戴爾筆記本電腦、I12=筆記本電腦、I13=電腦，滿足I11?I12?I13, 對應的后續測試用例組輸出結果為O11、O12、O13, 且應滿足O11?O12?O13， 同時源輸出組和后續輸出組之間的關系應滿足O01=O13，O02=O12，O03=O11， 或滿足其中任意一種關系，表示測試成功，反之測試失敗。

2.2 交集等價

交集等價模式的定義源自于關系代數中的交集運算，是在“等價性”和“完整分區”模式的基礎上提出的一種適用于多項選擇搜索功能的蛻變關系模式，它表示源輸入與所有后續輸入交集等價，且最后一次后續輸入是其它后續輸入的并集，源輸出等價于n-1次后續輸出之和減去第n次后續輸出的關系。如式(2)所示，數學關系表示為

I0=I1∩I2∩…∩In,In=I1∪I2∪…∪In-1?
O0=O1+O2+…+On-1-On，n≥1

(2)

例如：安居客搜索租房的相關房源信息，添加篩選條件“戶型”為“二室”作為I0，修改篩選條件為“一室&二室”生成I1、修改條件為“二室&三室”作為I2、修改條件為“一室&二室&三室”I3，滿足I3=I1∪I2。 判斷O0、O1、O2、O3之間的關系是否滿足O0=O1+O2-O3。

3 條件篩選搜索系統的蛻變測試

利用蛻變關系模式構建的蛻變關系，簡化了執行蛻變測試過程中蛻變關系的識別。下面將從理論和具體測試步驟兩個角度說明如何在條件篩選搜索系統中利用蛻變關系模式構建和識別蛻變關系執行蛻變測試，是一種面向最終用戶的軟件測試方法。蛻變關系模式表示源輸入輸出和后續輸入輸出之間的關系，是一種抽象模式；將抽象化的蛻變關系模式實例化即為構建蛻變關系的過程，利用傳統軟件測試方法生成源測試用例輸入，根據構建的蛻變關系修改源測試用例的輸入參數生成后續測試用例輸入，是抽象模式具體化的過程；執行源和后續測試用例輸入，并比較源測試用例輸出和后續測試用例輸出結果之間的關系是否違反了蛻變關系，是識別蛻變關系的過程。如果符合蛻變關系則測試通過，反之，測試不通過。如圖2所示。

圖2 蛻變關系模式構建和識別蛻變關系執行蛻變測試的過程

基于條件篩選搜索系統的具體蛻變測試步驟如下：

蛻變測試：識別條件篩選搜索系統多次輸出結果之間的蛻變關系

輸入：用戶根據需求自定義的搜索條件I,I={I0,I1,…,In|(n≥1)}

輸出：滿足搜索條件I的輸出數據集O,O={O0,O1,…,On|(n≥1)}

步驟1 在輸入框中Input并添加Select作為源測試用例輸入I0, 執行搜索得到的結果為源測試用例輸出O0。

步驟2 為待測搜索程序功能選擇合適的蛻變關系模式(MRP)。

步驟3 修改源測試用例的Input或者Select作為后續測試用例輸入Ii,i=1,2,…,n； 修改后的Ii與I0應該滿足MRP指定的輸入之間的關系。

步驟4 對后續測試用例輸入Ii,i=1,2,…,n執行搜索，得到的后續測試用例輸出結果分別為O1,…,On。

步驟5 比較源測試用例輸出O0和后續測試用例輸出O1,…,On是否滿足蛻變關系指定的輸出之間的關系，若滿足，表示測試通過；反之測試不通過，基于條件篩選的搜索系統存在軟件故障。

首先，確定待測條件篩選搜索系統的功能，并利用傳統軟件測試方式測試程序能否正確執行。若程序可以正確執行，則對程序進行蛻變測試。

其次，用戶根據待測條件篩選搜索系統的功能，利用傳統軟件測試方法自定義搜索條件和篩選條件生成源測試用例，選擇合適的蛻變關系模式，并且根據蛻變關系模式源輸入和后續輸入之間的關系修改源測試用例的輸入參數生成后續測試用例輸入。

最后，執行程序并記錄程序的源測試用例輸出與后續測試用例輸出結果，比較多次輸出結果之間的關系是否符合構建的蛻變關系。如果不違反蛻變關系，表示蛻變測試通過，若違反蛻變關系則表示測試不通過，意味著條件篩選搜索系統存在軟件設計故障。

4 實 驗

實驗以京東商城和安居客兩大網站的條件篩選搜索系統作為基礎實驗環境，兩者在中國擁有眾多的用戶，數據源類型和數量豐富，樣本數據真實可靠。研究顯示[17]，蛻變測試只需要平均3-6種不同的蛻變關系就可以揭示至少90%的Oracle能夠檢測到的故障。因此，實驗根據網站的搜索功能設計首先選用了現有方法中的等價性、等效性、合并條件、析取條件、不相交的分區、完整分區6種蛻變關系模式構建和識別蛻變關系執行蛻變測試，并記錄檢測結果。然后沿用了等價性、等效性、不相交的分區、完整分區4種蛻變關系模式并加入改進提出的交集等價和IO組對稱相等兩種蛻變關系模式共6種蛻變關系模式作為改進的方法構建蛻變關系執行蛻變測試作比較。最終指出兩個網站中存在的軟件設計問題以改進網站的設計質量。

實驗欲回答3個問題：

Q1：改進提出的兩種蛻變關系模式是否能夠幫助簡化蛻變測試，并提高檢測效率？

Q2：實驗過程中存在哪些潛在的有效性威脅？

Q3：改進方法中的6種蛻變關系模式在多大程度上優于現有方法中的6種蛻變關系模式？

4.1 實驗過程

鑒于Web網站中龐大的數據量，實驗選用了京東商城中圖書、美妝、運動、電腦和安居客中新房、二手房、租房、寫字樓8個具有代表性網頁的條件篩選搜索結果作為實驗數據，在對條件篩選搜索功能測試的過程中生成源測試用例，并通過蛻變關系模式實例化的蛻變關系，構建后續測試用例，執行蛻變測試。

利用現有方法中等價性、等效性、合并條件、析取條件、不相交的分區、完整分區6種蛻變關系模式構建的蛻變關系和測試次數數據見表1。

表1 前6種MRPS構建的蛻變關系與測試次數

采用等價性、等效性、IO組對稱相等、交集等價、不相交的分區和完整分區6種蛻變關系模式作為改進方法構建的蛻變關系和測試次數數據見表2。

表1和表2第一列表示兩個網站中的8個網頁，其余列分別是針對數據集的8個網頁利用蛻變關系模式生成的蛻變關系(MR)數量、執行蛻變測試的次數(Count)。網站中不同類型的搜索功能具有不同的篩選條件，因此根據不同的篩選條件為每種模式構建了2個-8個蛻變關系，總計473個蛻變關系，并利用這些關系執行至少兩次蛻變測試，以保證檢測的真實有效性。

表2 后6種MRPS構建的蛻變關系與測試次數

4.2 實驗結果與分析

實驗采用了精確率(Precision)和召回率(Recall)衡量檢測效果。精確率如式(3)所示，可以反應算法的查準率；召回率如式(4)所示，可以反應算法的查全率

(3)

(4)

其中，P表示精確率，R表示召回率，TP表示檢測到故障的相關數據量，FP表示未檢測到故障的相關數據，FN表示未檢測到故障的不相關信息量。實驗分析了現有方法中的等價性、等效性、合并條件、析取條件、不相交的分區、完整分區6種蛻變關系模式和結合本文改進提出的兩種蛻變關系模式組成的等價性、等效性、IO組對稱相等、交集等價、不相交的分區、完整分區6種蛻變關系模式下對京東商城和安居客兩個網站共8個網頁執行蛻變測試的檢測效果，根據式(3)和式(4)計算得出每個網頁基于改進前和改進后的6種蛻變關系模式執行蛻變測試的精確率和召回率(見表3)。

表3 不同關系模式下的精確率和召回率

根據實驗結果，可以回答實驗部分提出的3個問題。

針對Q1：改進提出的蛻變關系模式能夠幫助簡化蛻變測試。傳統的蛻變測試完全依賴于測試人員對于待測軟件各個功能的熟悉程度，識別每個蛻變關系都必須根據每個被測程序的預期功能從頭開始檢測和識別，降低了蛻變測試的可靠性。改進提出的蛻變關系模式將程序輸入輸出之間的關系抽象化，使用這種關系模式和測試步驟，將蛻變關系的識別變成一個程序化問題：只需要根據蛻變關系模式，為每個搜索功能添加符合關系模式指定源輸入和后續輸入之間關系的輸入條件，將其實例化即可。按照這個步驟，測試人員可以很容易地構建蛻變關系，檢查源測輸出和后續輸出之間的關系是否符合關系模式指定的輸出之間的關系可以很容易地識別蛻變關系。如第3章所述，每種模式定義了條件篩選搜索系統中輸入輸出類型之間的關系，包含了基于篩選條件搜索網站中的兩種篩選條件類型(單選和多選)。實驗部分利用蛻變關系模式對京東商城和安居客兩個網站分別構建蛻變關系(見表1和表2)，簡化了構建蛻變關系的過程。

針對Q2：實驗中存在的有效性威脅主要包括：①能否有效構建蛻變關系；②能否正確檢測軟件故障。

對于①，構建的蛻變關系的有效性取決于蛻變關系模式定義的質量好壞。因此，通過記錄兩個網站執行蛻變測試構建的蛻變關系及測試次數(見表1和表2)，結合表4記錄的基于改進前的6種蛻變關系模式和改進后的6種蛻變關系模式執行蛻變測試檢測到故障的數量，并且對比表3記錄的改進前方法和改進后方法的精確率和召回率，驗證了改進提出的兩種新型蛻變關系模式能夠幫助構建有效的蛻變關系。

表4 前6種MRPS和后6種MRPS執行蛻變測試檢測到的故障數量

對于②，研究顯示[17]，蛻變測試只需要平均3到6種不同的蛻變關系就可以揭示至少90%的Oracle能夠檢測到的故障。因此，首先在對兩個網站的前后兩次測試中都選用了6種不同類型的蛻變關系模式，幫助構建6種不同類型的蛻變關系，并且根據每個蛻變關系分別進行了至少兩次測試，然后分析了被違反的蛻變關系，直到故障能夠被重現，然后檢查故障是否被記錄，如果沒有記錄則在記錄中添加檢測到的問題以及該問題如何被人為重現。最后，指出用戶執行搜索的過程中可能出現的意外情況，保證記錄故障文檔的嚴謹有效以及軟件檢測的高質量。

針對Q3：通過表3，可見改進的方法在精確率和召回率方面均顯著優于改進前的方法。結合表4，易見性能提升的原因是改進的模式“IO組對稱相等”優于模式“合并條件”和“析取條件”，在“等價性”和“完整性”模式的基礎上提出的“交集等價”模式也更直接提高了蛻變測試的精確率。因此，在利用蛻變關系模式簡化蛻變測試執行的過程中，本文改進提出的兩種蛻變關系模式能夠有效地檢測出更多的軟件設計故障，提高蛻變測試的檢測效率，更全面地指導軟件設計問題以改進網站的設計質量。

5 結束語

通過分析現有蛻變關系模式中的“合并條件”和“析取條件”模式，提出了“IO組對稱相等”模式，并在“等價性”和“完整性”模式的基礎上提出了基于多項選擇篩選條件的蛻變關系模式，即“交集等價”模式?？偨Y現有的蛻變關系模式和改進提出的蛻變關系模式，并以此構建的蛻變關系，在簡化蛻變關系識別過程的同時可以顯著提高蛻變測試的故障檢測質量。

實驗部分以京東商城、安居客兩個網站中共8個網頁為對象，分別選擇改進前和改進后的6種蛻變關系模式構建蛻變關系，幫助生成測試用例，進而對網站中基于條件篩選搜索的功能執行測試。通過分析蛻變測試的精確率與召回率，驗證了改進提出的蛻變關系模式對條件篩選搜索系統執行蛻變測試的有效性。

未來的工作主要包括：識別更多新的并且有效的蛻變關系模式；將蛻變關系模式應用于更廣泛的科學領域中；識別和推斷蛻變關系以及創建有效的測試用例集。