Xie, Miao & Wang, Qing & Yang, Guowei & Li, Mingshu. (2017). COCOON: Crowdsourced Testing Quality Maximization Under Context Coverage Constraint. 316-327. 10.1109/ISSRE.2017.25.
介紹如今，智慧手機和平板電腦等移動裝置越來越受歡迎。每天都有數百個新的移動應用釋出，每週約有 7.5 億個來自 190 個不同國家的移動應用被下載。一個移動應用通常要在不同地點、不同螢幕設定和作業系統的多樣化裝置上執行，並跨越眾多的運營商和網路技術。每個新發布的應用都必須應對這些不同的操作環境。在最近的一項研究中，如果一個應用在下載後不久就兩次崩潰，近 90%的智慧手機使用者會拒絕使用該應用。因此，一款移動應用在釋出前需要在全方位的操作環境下進行測試，以確保高質量的使用者體驗。不幸的是，由於成本極高，在傳統的測試環境下，這種測試似乎是不可能的。
現有的移動應用測試方法可以分為兩大類。一類是進行有限規模的實地測試，例如基於小規模的測試版或內部版本，收集真實使用者的測試資料和日誌。然而，這些測試所涉及的有限規模的現場很難代表預期的操作環境。另一類則進行模擬測試，即利用現有的平臺模擬器在特定的 GPS 位置和網路型別（如 Wi-Fi）下測試應用。然而，模擬器通常不提供系統探索移動應用可能使用的代表性操作環境的方法。雖然一些模擬器和自動測試平臺已經被提出並旨在模擬真實場景，但模擬所有操作環境將非常昂貴。
受眾包概念的啟發，一種名為眾包測試的新測試方法在軟體工程界備受關注。很多具有不同背景的移動應用使用者在世界範圍內廣泛使用各種真實的移動裝置。眾包測試為移動應用提供商提供了一個便利的環境，可以聚集這樣大量的低成本人力資源來測試他們的移動應用。應用提供商可以釋出眾包任務來測試移動應用。在眾包測試平臺上註冊的使用者（即眾工）就可以選擇自己感興趣的測試任務，在自己的軟硬體環境中進行測試，並針對自己完成的任務提交測試報告。由於參與人數眾多，自然覆蓋了各種軟硬體環境，這就有可能實現較高的操作語境覆蓋率。
雖然眾包對於移動應用的測試來說似乎很划算，但主要由於參與者的自主性，仍然具有一定的挑戰性。應用提供者通常在被動等待參與者的同時釋出測試任務。現有的眾包測試平臺如 U-test 2、99tests 3、Mob4Hire 4、百度眾包測試平臺大多采用這種策略。與傳統的軟體眾包不同，眾包測試需要參與者的組合結果來滿足其要求，而不是單個個體的最佳結果。圖 1 顯示了一個眾包測試的真例項子，其描述和預期的測試情境在 U-test 中。由於參與者的自發性和其測試資源的潛在重疊性，任務的預期測試情境難以覆蓋。具體來說，主要有三個方面的挑戰。(1)很多工缺乏足夠的參與者來進行所有預期測試上下文的測試；(2)即使一個任務獲得了大量的參與者，他們的測試上下文也可能是重疊的，無法覆蓋所有的預期上下文，導致重複的 bug 報告和相關的分析這些 bug 報告的工作浪費；(3)由於參與者的自發性，測試質量難以推定。
解決方案為了解決這些難題，本文提出了眾包測試任務釋出者的主動解決方案，為任務發現合適的工作者，使其能夠達到預期的測試上下文覆蓋率，並在上下文覆蓋率的約束下獲得高的測試質量。具體來說，我們制定了一個新的研究問題，稱為上下文覆蓋約束下的眾包測試質量最大化（COCOON）。我們的研究問題是推薦一組規模為 k 的潛在合格工作者，使推薦的工作者共同擁有完成給定移動應用測試任務所需的資源，以達到較高的測試質量。在本文中，測試質量可以泛化為任何質量目標，而不限於 bug 報告的數量。利用百度眾包測試平臺的真實資料集，我們說明了這個研究問題的重要性。我們證明了這個問題的難度，然後引入了兩種線上貪婪方法，命名為 SCORE 和 PIGEON，有不同的優點來解決這個問題。實驗是為了評估我們的方法與一些基線相比的有效性和效率。我們的方法可以很容易地部署在任何眾包測試平臺中，作為眾包測試釋放者的線上服務，以尋找候選工人集來進行給定的測試。在找到目標工人後，測試釋放者可以使用激勵措施（如一些額外的獎勵）來激勵這些目標工人參與任務。考慮到吸引參與者的成本，推薦的工人集應該遠小於所有可用人群工人的通用集。
本文的主要貢獻如下：
1）我們制定了一個新型的組合最佳化問題，稱為上下文覆蓋約束下的眾包測試質量最大化（COCOON）。它的目的是在眾包測試中實現移動應用測試任務的預期測試上下文覆蓋率和上下文約束下的測試質量最大化。透過對一個真實工業資料集的研究，證明了這個問題的重要性。我們證明 COCOON 問題是 NP 完全的。
2）我們介紹了兩種實用的貪婪方法來解決 COCOON 問題。我們的方法推薦了一組工人，他們一起可以覆蓋所有預期的測試上下文，並實現高測試質量。這兩種方法可以靈活地用於支援許多測試質量的實際測量。
3）我們基於真實工業資料集的評估顯示了我們的方法在推薦目標工人完成給定測試任務方面的效率、有效性和靈活性。我們的方法足夠高效，可以作為測試任務釋出者尋找目標工人的線上服務進行部署。
評估我們評估了我們的兩種方法，使用百度眾包測試平臺中的 536 個測試任務評估 SCORE 和 PIGEON。在我們的資料集中，有 6 個類別的 3130 個不同的上下文，超過 3014 名工人，從參與工人那裡收到 48252 份測試報告，以及由測試任務釋出者確認的 32863 個 bug。我們主要探索了以下三個問題：
•
RQ1：所提出的兩種方法對解決 COCOON 問題是否有效（有效性）？
•
RQ2: 兩種建議的方法是否足夠高效，可以作為線上自動服務（效率）？
•
RQ3: 兩種方法是否靈活地支援不同的質量測量（靈活性）？
以上研究問題旨在評價 SCORE 和 PIGEON 方法的有效性、效率和靈活性，與當前主流方法進行比較。評價指標如下：
1）測試上下文覆蓋率（TC），是指推薦的一組工作者所覆蓋的測試上下文在所有預期測試上下文 E 中的百分比。
2）測試質量（σ(P)），是推薦工人集 P 在測試集中的質量得分。我們從資料集中隨機選取 20%的測試任務作為測試集，並根據這個測試集對推薦工人集的測試質量進行評價。其餘 80%的資料作為歷史訓練資料。對於測試集中給定的測試任務，如果測試集中不存在結果工人集的推薦工人，則該工人的測試質量設為零。
3）執行時間。
RQ1：所提出的兩種方法對解決 COCOON 問題是否有效（有效性）？
我們分別用不同數量的推薦工人 k 和不同數量的預期測試上下文|E|來比較所有方法的效能。我們選擇報告的 bug 數量作為一個工人的質量衡量標準，並使用求和符號作為 UnionOperator 來衡量一個工人集的測試質量。對於每個測試上下文，最大質量分數為 1，因為我們使用所有工人的統一分數作為測試質量。我們發現對於大多數測試任務來說，其預期測試上下文的數量在 10 到 30 之間。對於給定的 E，COCOON 希望 k 在覆蓋 E 的同時儘可能小，因此，我們設定 k=20（一個相對較小的值），並對 30 個不同的測試任務（查詢）分別從 10 到 30 變化|E|。圖 8(a)比較了不同預期測試上下文 E 數量的方法的平均測試上下文覆蓋率。首先，PIGEON 可以實現最好的測試上下文覆蓋率，在所有情況下都接近 100%。RANDOM 的效能最差。其次，RANKING 和兩種提出的方法之間有很大的差距，因為排名高的工作者的測試上下文通常是重疊的。第三，SCORE 和 MOEA 的測試上下文覆蓋率比 PIGEON 差，因為這兩種方法是為了追求測試質量和上下文覆蓋率之間的平衡。因此，它們很難實現對預期上下文的完全覆蓋。最後，當 k≥|E|時，PIGEON 可以獲得最好的測試上下文覆蓋率(100%)。圖 8(b)給出了同一查詢集的所有工作者中推薦工作者比例不同的測試上下文覆蓋率。我們使用|E| = 30 的查詢，並將 k 從 15 到 50 變化（k/|W|從 0.5%到 1.6%）。我們發現對於所有的方法來說，隨著推薦工作者數量的增加，測試上下文的覆蓋率都會提高，因為隨著 k 的增加，覆蓋預期測試上下文的可能性也會增加。雖然我們在一個小的數值範圍內改變 k，但 PIGEON 在所有情況下都獲得了近 100%的測試上下文覆蓋率。SCORE 和 MOEA 獲得了幾乎相同的次優上下文覆蓋率，比其他兩個更好。
圖 8(c)(d)比較了測試質量。我們可以看到 PIGEON 實現了最好的測試質量。它試圖推薦具有不同測試背景的工人，這可能會增加發現錯誤的可能性。雖然在某些情況下推薦的工人數量較少，但 PIGEON 總是取得了最好的測試質量和測試上下文覆蓋率。SCORE 和 MOEA 始終優於 RANKING，但前兩種方法的差距並不明顯。如果我們還考慮到效率（在 RQ2 中），SCORE 要比 MOEA 好很多。雖然 SCORE 不如 PIGEON，但它的得分函式對測試上下文覆蓋率和測試質量以外的目標支援的適應性更強。
RQ2: 兩種建議的方法是否足夠高效，可以作為線上自動服務（效率）？
圖 9 顯示了所有五種方法的執行時間。首先，我們的兩種方法可以在一秒內解決所有的案例，比 MOEA 快得多，所以它們的效率足以成為眾包測試平臺的線上服務。其次，正如預期的那樣，RANDOM 和 RANKING 的效率最高，而且不受 K 和|E|變化的影響。但是，如果我們考慮到它們的測試質量和上下文覆蓋率，它們並不是 COCOON 問題的良好解決方案。最後，雖然有一定的波動，但由於 PIGEON 的候選修剪能力較好，所以比 SCORE 更有效率。
RQ3: 兩種方法是否靈活地支援不同的質量測量（靈活性）？
我們評估了這兩種方法在不同質量度量下的效能。圖 10 顯示了當|E|變化時，兩種方法在三種不同質量度量下的效能。在圖 10 中，Score(A)和 Pigeon(A)分別代表 SCORE 和 PIGEON，UnionOperator=Average。對於(M+C)，我們用確認的 bug 數作為一個眾包工人的質量衡量標準，UnionOperator = Maximal。我們發現，這些方法所選取的工人的測試質量僅受不同質量測量方法的輕微影響。
結論我們在移動應用測試任務的眾包測試平臺中，首次系統性地根據歷史測試任務記錄從大量工作者中發現潛在工作者。據我們所知，這是第一個提出上下文覆蓋約束下眾包測試質量最大化（COCOON）問題的工作。我們證明了它的 NP 完全性，並介紹了兩種針對 COCOON 問題的方法。我們透過在中國最大的移動應用眾包測試平臺的真實資料集上進行大量的實驗，展示了我們的方法的有效性、高效性和靈活性。在未來我們將繼續制定其他型別的真實場景，以提高眾包測試的成功率。