Guo C, He T, Yuan W, et al. Crowdsourced requirements generation for automatic testing via knowledge graph[C]//Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2020: 545-548.
摘要眾包測試（Crowdsourced Testing）是一種應對 Android 系統碎片化（Fragmentation）問題的有效方式。與此同時，眾包測試還解決了 Android 測試面臨的應用場景多樣化問題。測試需求生成時眾包測試的重要步驟。但是，人工生成眾包測試需求通常十分繁瑣且乏味，同時需要參與者具有與待測安卓應用相關的領域知識，執行成本較高。為了解決這些問題，本文提出並實現工具 KARA（Knowledge Graph Aided Crowdsourced Requirements Generation for Android Testing），利用知識圖譜輔助眾包測試需求生成。首先，KARA 將分析待測 Android 應用程式的自動測試結果以獲取操作序列；然後，KARA 將以“即付即用”（Pay-as-You-Go）的方式構建知識圖譜；最後，KARA 將利用知識圖譜和自動測試結果來生成具備特定領域知識的眾包測試需求。實驗結果表明：KARA 能夠產生測試人員可理解的眾包測試需求，並且可以從一定程度上提高眾包測試的質量。
關鍵詞：眾包測試；需求自動生成；知識圖譜；安卓測試
1 引言安卓應用程式是現在市場上最為主流的移動應用型別。由於安卓平臺的品牌和系統版本多種多樣，安卓“碎片化”問題日趨嚴重。繁雜的應用場景和頻繁的版本迭代使得安卓測試變得十分困難。
安卓自動測試和眾包測試能夠有效應對安卓測試中的碎片化問題。安卓自動測試透過測試指令碼自動遍歷安卓應用的頁面元件，透過模擬使用者操作觸發各種互動事件（如點選、輸入、回退等），目的是儘可能多地探索應用程式中存在的程式狀態。從概念上來說，安卓自動測試是一種透過自動生成測試輸入來檢測程式中潛在異常的測試手段。雖然這類測試技術能夠從一定程度上幫助測試人員完成安卓測試，但是由於其測試生成的結果往往晦澀難懂，測試人員無法直接從中提取出有效的眾包測試需求。
眾包測試是一種群體智慧的應用形式。眾測任務通常由一個請求者發起，由多個來自不同地區的參與者，即眾包工人（Crowd Worker），共同完成。眾包工人需要在完成測試任務後提交測試報告。在傳統的眾包測試過程中，任務發起者需要首先指明測試目標並提出測試需求。參與測試任務的眾包工人則需要按照測試需求中的指示完成測試任務。因此，測試需求是眾包測試任務的基礎。然而不幸的是，測試需求的生成需要大量關於待測應用程式的領域知識。手動生成測試需求通常是一項單調且繁瑣的工作。
因此，為了解決面向安卓應用程式的眾包測試的測試需求生成問題，作者團隊引入知識圖譜（Knowledge Graph）來自動獲取待測應用程式的領域知識。作者團隊設計並實現了工具 KARA 用於眾包測試需求的自動化生成。首先，KARA 將圍繞待測應用程式構建具有領域知識的 GUI 模型和知識圖譜；然後，根據 GUI 模型，KARA 將透過搜尋演算法獲取發掘疑似漏洞（Suspicious Bug）的最短操作序列；最後，在知識圖譜和最短操作序列，KARA 將進一步生成眾包測試需求。藉助知識圖譜，KARA 有效地解決了自動化測試結果晦澀難懂的問題，能夠有效地生成易於理解和執行的測試需求。
2 方法KARA 的整體架構如圖 1 所示。首先，KARA 將對安卓自動測試結果進行分析，目的是獲取（應用程式介面間的）視窗轉換（Window Transition）；然後，KARA 圍繞待測應用程式構建 GUI 模型，並採用 Dijkstra 演算法計算從應用程式啟動介面到刻意錯誤介面的最短操作序列。與此同時，KARA 將透過對應用程式原始碼的靜態分析獲取控制元件資訊。透過結合 GUI 模型和空間資訊，KARA 將完成對待測應用程式知識圖譜的構建；最後，KARA 將透過結合最短操作序列和知識圖譜來生成眾包測試需求。
圖 1 KARA 架構
2.1 獲取操作序列作者團隊使用慕測平臺提供的安卓自動測試工具對待測應用程式進行自動化測試，同時應用 Dijkstra 演算法計算最短操作序列。操作序列獲取演算法如演算法 1 所示。
演算法 1 獲取操作序列
對應演算法每個子過程（Procedure），給出若干形式化定義如下：
1、正常視窗轉換（Normal Windows Transition）：安卓自動化測試會產生若干事件，表達了安卓應用 GUI 的轉換過程。本文使用有向圖 G = <V, E>形式化表示 GUI 的狀態變化，其中：頂點集合 V = <V1, V2, …, Vn>表示安卓應用程式所出現的所有視窗；邊集合 E = <E1, E2, …, En>表示所有可能的轉換條件。邊 Ei = <Vs, Vt, m, t, c, b, Pe>，其中：Vs 表示轉換前視窗，Vt 表示轉換後窗口，m 表示觸發視窗轉換的操作，t 表示觸發視窗轉換的時間，c 表示轉換事件的分類（預設值為 1，表示正常轉換；2 表示異常轉換）。當轉換過程中發生異常時，異常資訊應該被記錄下來，由 b 表示。此外，觸發之前轉換事件的截圖檔案將被記錄下來，由 Pe 表示。注意：雖然兩個視窗 Vs 和 Vt 可能存在多種轉換，即兩個點之間有多條同向的邊 Ex。但這些操作的具體情況不同，因此 Ex 記錄在 m 位中的資訊也會不同。
自動化測試工具將吧自動化測試過程中產生的截圖將儲存下來，形成截圖列表。一個截圖列表可由 P = <P1, P2, …, Pn>表示。對於任意截圖 Pi，都有 Pi = <n, t>。其中：n 表示檔名、t 則是截圖產生的時間戳。對於每一個截圖 Pi，一定存在一條邊 Ei 使其對應的時間大於且最接近時間戳 t。由此可以將 Pi 儲存在 Ei 的 Pe 位上，也就是完成了轉換和截圖間的對映。實現截圖對映的程式碼如演算法 1 中 1~8 行所示。
2、異常視窗轉換（Abnormal Windows Transition）：KARA 透過分析自動測試結果來生成異常日誌和視窗轉換對映關係。其中，異常日誌集合 L = <L1, L2, …, Ln>。對於任意異常日誌有 Li = <m, t>，t 表示日誌形成的時間戳，m 則是異常日誌 Li 的詳細資訊。在邊集合中必定存在一條邊 Ek（表示視窗轉換）使得它的發生時間 tk 小於且最接近 t。作者團隊利用這一關係建立了 Li 和 Ek 之間的對映並把 Li 的詳細資訊記錄在 Ek 的 bk 位上。Ek 的型別 ck 被設定為 2（表示異常）。
結合以上關於視窗轉換的定義，這裡給出安卓應用程式“JianShi”的部分 GUI 模型如圖 2 所示。對於每對視窗間的每個轉換方向，圖中各選取了一條邊用於展示。其中實線箭頭表示正常視窗轉換，虛線箭頭則表示異常視窗轉換。
圖 2 應用“JianShi”對應的部分 GUI 模型
3、獲取最短操作序列：利用 GUI 模型，KARA 可以獲取從應用程式入口到某一異常視窗轉換的操作（轉換）序列 S = <E1, E2, …, En>。KARA 使用 Dijkstra 演算法獲取最短操作序列 St = <E’1, E’2, …, Em>。其中，Em 表示 S 中的倒數第三個事件（如演算法 1 第 19~20 行所示，arcMap 是 G 的鄰接矩陣）。之後再將最後兩個事件 En-1 和 En 加到 St 中，構成最終的最短運算序列 S’ = <E’1, E’2, …, Em, En-1, En>（演算法 1 第 21 行）。當操作序列 S 的長度小於 3 時，從入口到達異常轉換的最短操作序列可以透過 Dijkstra 演算法直接得到（演算法 1 第 24 行）。
2.2 構建知識圖譜在傳統眾包測試實踐中，測試需求需要任務發起者手動生成。這是一項十分繁瑣的工作，需要任務發起者蒐集與待測應用程式相關的領域知識。KARA 引入知識圖譜以自動構建領域知識。知識圖譜由包含諸多屬性的實體和實體之間的關係組成。KARA 基於 GUI 模型和待測應用程式的原始碼來構造知識圖譜。利用 GUI 模型，KARA 可以獲取窗體間的轉換資訊並構造實體間的部分關係。而組成知識圖譜中實體的屬性則可以從原始碼中獲得。KARA 透過靜態程式分析提取視窗元件完成實體填充。綜上，KARA 可以利用 GUI 模型構造知識圖譜骨架，之後在利用原始碼完成屬性和實體的填充。
KARA 在知識圖譜中定義了 5 種實體、3 種關係和 3 種屬性。實體包括：（1）頭實體（Head Entity）：在操作執行前存在的實體；（2）尾實體（Tail Entity）。操作完成後出現的實體；（3）動作實體（Action Entity）。作為動作出現的實體；（4）主實體（Master Entity）。包含其他實體的實體；（5）從實體（Slave Entity）。附屬於某個確切主實體的實體；關係包括：BelongTo、Take 和 Result。BelongTo 描述控制元件和整體佈局的關係；Take 和 Result 則分別指向輸入和輸入，表示動作的因果關係；屬性描述特定情況下實體的特徵，包括（1）ID。實體的唯一識別符號；（2）描述（Description）：操作的詳細資訊；（3）型別（Type）：操作的型別，可以使 Click、Input 和 Slide。樣例 KARA 知識圖譜如圖 3 所示。
圖 3 KARA 知識圖譜舉例
2.3 生成測試需求利用最短操作序列和知識圖譜，KARA 能夠進一步生成眾包測試需求。利用最短操作序列 S’中每個事件（視窗轉換）E 包含的控制元件資訊 m，KARA 都能在知識圖譜中找到對應的實體，並從中提取出視窗轉換資訊。
圖 4 給出了一個眾包測試需求的示例。需求包括四個部分：（1）測試環境資訊（A 部分）。其中包括應用程式名稱、應用程式版本、裝置品牌和網路狀況的資訊。；（2）疑似漏洞資訊（B 部分），由日誌資訊和疑似漏洞的螢幕截圖組成；（3）需求步驟列表（C 部分），包含每個到達疑似漏洞的步驟以及對應的操作說明；（4）螢幕截圖列表（D 部分），包含對應需求步驟列表的一系列螢幕截圖。
圖 4 眾包測試需求示例
3 評估為了評估 KARA 生成的測試需求的可理解性和有效性，作者團隊設計並透過實驗以驗證了以下研究問題：
RQ1：KARA 產生的測試需求的可理解性如何？
RQ2：KARA 產生的測試需求是否能夠有效提高眾包測試的質量？
為了解決 RQ1，作者團隊設計了一套問卷並進行抽樣調查，收集並整理了 20 名參與者對 KARA 生成的測試需求可理解性的看法。統計結果顯示，超過 90%的參與者認為測試需求是可理解的、有效的，僅有小部分參與者持消極態度。作者團隊進一步對這些參與者進行了訪問，發現他們中大多數認為 KARA 生成的測試需求對於疑似漏洞的描述不夠充分，模稜兩可的描述會影響他們辨別真實的漏洞。作者團隊將在後續的研究中進一步改進。
為了解決 RQ2，作者團隊設計並執行了一組對照實驗。作者團隊選擇了十個安卓應用程式，如：JianShi、QQplayer 等，又選擇了十個在中國安卓市場上佔有率較高的安卓裝置，如：Huawei P30、Xiaomi 10Pro 等。該實驗共有 20 名參與者。作者團隊將參與者分為兩組：A 組為對照組，組內 10 人需要透過純手工完成對目標 APP 的眾測任務；B 組為實驗組，組內 10 人將是參考 KARA 生成的測試需求完成對目標 APP 的眾測任務。實驗參與者需要在 2 小時內儘可能多的發現並提交疑似 Bug；眾測任務的完成情況由提交 Bug 的數量（提交總數）和質量（有效 Bug 數量）共同決定。
表 1 針對 KARA 生成的測試需求的評估結果
實驗結果如表 1 所示，其中：Bc 表示提交總數，Be 表示有效 Bug 總數。在限時兩小時的情況下，A 組和 B 組提交錯誤的有效率（Be/Bc）分別為 52.6%和 80.9%。該結果顯示 KARA 生成的測試需求能夠有效地提高眾包測試的質量。