基于模型的移動(dòng)應(yīng)用功能場(chǎng)景自動(dòng)標(biāo)注方法

鄭曉梅，錢(qián)正軒，李 剛，王天舒

(1.南京中醫(yī)藥大學(xué) 人工智能與信息技術(shù)學(xué)院，江蘇 南京 210023；2.南京大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，江蘇 南京 210023；3.南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023)

0 引 言

隨著移動(dòng)應(yīng)用開(kāi)發(fā)逐漸成為現(xiàn)代軟件開(kāi)發(fā)的主流，移動(dòng)應(yīng)用模型的重要性也逐漸凸顯出來(lái)。移動(dòng)應(yīng)用的主要特點(diǎn)是事件驅(qū)動(dòng)的設(shè)計(jì)方式，應(yīng)用執(zhí)行流程取決于用戶產(chǎn)生的事件，場(chǎng)景對(duì)應(yīng)著應(yīng)用功能，場(chǎng)景的理解對(duì)測(cè)試和軟件演化至關(guān)重要。

在對(duì)移動(dòng)應(yīng)用進(jìn)行建模時(shí)，常見(jiàn)方法是人工對(duì)其進(jìn)行測(cè)試，觸發(fā)盡可能多的事件跳轉(zhuǎn)。人工測(cè)試模型符合用戶使用邏輯，且執(zhí)行腳本標(biāo)注場(chǎng)景信息，但是成本較高。

現(xiàn)在流行的很多自動(dòng)化測(cè)試工具，如UI Automator[1]、Monkey[2]、Appium[3]、Q-testing[4]等，它們接受人工編寫(xiě)的腳本文件或是調(diào)用框架提供的接口，驅(qū)動(dòng)在虛擬機(jī)或真機(jī)上運(yùn)行的應(yīng)用執(zhí)行跳轉(zhuǎn)。這些自動(dòng)化測(cè)試工具對(duì)移用應(yīng)用進(jìn)行建模會(huì)具有較高的探索度，模型的覆蓋度較高，但執(zhí)行序列較為包含過(guò)多冗余路徑，且無(wú)場(chǎng)景信息。

本文提出一種基于模型的移動(dòng)應(yīng)用功能場(chǎng)景自動(dòng)標(biāo)注方法AFSLM，通過(guò)構(gòu)造執(zhí)行路徑模型反映測(cè)試腳本的執(zhí)行過(guò)程，并基于該模型實(shí)現(xiàn)人工標(biāo)注信息的泛化。該方法首先根據(jù)移動(dòng)應(yīng)用的相關(guān)屬性及其運(yùn)行時(shí)的狀態(tài)信息，基于IFML(interaction flow modeling language)國(guó)際標(biāo)準(zhǔn)[5]構(gòu)建了一個(gè)平臺(tái)無(wú)關(guān)的、抽象的概念模型——應(yīng)用執(zhí)行路徑(app running path，ARP)，用以保持對(duì)移動(dòng)應(yīng)用測(cè)試腳本的對(duì)應(yīng)。以具有場(chǎng)景功能標(biāo)簽的人工測(cè)試模型為基準(zhǔn)，通過(guò)對(duì)布局文件進(jìn)行相似性計(jì)算，找出機(jī)器測(cè)試模型中具有同樣場(chǎng)景的路徑集合，并標(biāo)注相應(yīng)的功能場(chǎng)景標(biāo)簽，從而以較低的成本構(gòu)建擁有較多信息尤其包含完整的功能場(chǎng)景信息，同時(shí)具有一定規(guī)模的移動(dòng)應(yīng)用模型庫(kù)。

AFSLM方法屬于移動(dòng)應(yīng)用界面場(chǎng)景理解[6-10]，該工作主要應(yīng)用在測(cè)試腳本的重用和遷移、自動(dòng)化測(cè)試工具等工作中。很多功能場(chǎng)景在設(shè)計(jì)之初就是具有連接性和依賴性的，這些功能的關(guān)聯(lián)均是通過(guò)界面間固有的跳轉(zhuǎn)關(guān)系連接，因此在功能場(chǎng)景分類中引入跳轉(zhuǎn)關(guān)系是有必要的，而以往的相關(guān)研究工作所提出的測(cè)試框架[4，11，12]均未考慮跳轉(zhuǎn)關(guān)系。文獻(xiàn)[11]所提出的測(cè)試框架，通過(guò)利用機(jī)器學(xué)習(xí)技術(shù)將應(yīng)用程序界面分類成通用的功能場(chǎng)景，并重用這些通用功能場(chǎng)景的測(cè)試腳本以達(dá)到減輕手動(dòng)功能測(cè)試的負(fù)擔(dān)的目標(biāo)。文獻(xiàn)[12]同樣構(gòu)建了一個(gè)自動(dòng)化測(cè)試框架，該框架定義了一種新的測(cè)試腳本語(yǔ)言，該工作的亮點(diǎn)之一也是通過(guò)機(jī)器學(xué)習(xí)來(lái)對(duì)界面的功能場(chǎng)景劃分以確定界面的功能。該工作同樣認(rèn)為控件的類型、數(shù)量、所處的位置區(qū)域?qū)Ψ诸愔陵P(guān)重要，并沿用了文獻(xiàn)[11]的屏幕分區(qū)方式和拓展了其特征提取方式。除了僅僅統(tǒng)計(jì)布局文件3個(gè)區(qū)域中可以點(diǎn)擊、滑動(dòng)、編輯的控件數(shù)量之外，還增加了可聚焦的控件、類型為圖像文件的控件、可選中控件數(shù)量等，因此構(gòu)造成了包含16個(gè)特征的特征向量。經(jīng)過(guò)與Ariel的工作的對(duì)比實(shí)驗(yàn)，該工作驗(yàn)證了將拓展后的特征輸入到多類別的邏輯回歸分類器進(jìn)行功能場(chǎng)景分類能夠得到更高的準(zhǔn)確率。文獻(xiàn)[4]提出了一個(gè)基于強(qiáng)化學(xué)習(xí)的測(cè)試工具Q-testing，記錄測(cè)試過(guò)程中已經(jīng)探索過(guò)的界面狀態(tài)并且通過(guò)判斷兩個(gè)狀態(tài)是否屬于同一個(gè)功能場(chǎng)景來(lái)決定在探索過(guò)程的獎(jiǎng)勵(lì)，這就避免了在測(cè)試的一開(kāi)始就局限在幾個(gè)相同的功能場(chǎng)景測(cè)試，引導(dǎo)工具向未探索的功能方向探索，能夠有效解決其它工具測(cè)試代碼覆蓋度較低的問(wèn)題。

布局文件中提取控件的屬性信息是目前功能場(chǎng)景理解主要的方式，以往研究工作在場(chǎng)景判斷時(shí)主要通過(guò)的是單個(gè)UI的信息，而不同UI之間的跳轉(zhuǎn)關(guān)系并沒(méi)有得到充分利用。本文的研究工作增加了對(duì)UI跳轉(zhuǎn)關(guān)系的理解，進(jìn)一步挖掘了可以利用的語(yǔ)義信息。

1 方法概要

這部分介紹AFSLM方法的整體框架，整體框架如圖1所示。

圖1 AFSLM方法整體框架

1.1 構(gòu)建ARP模型

IFML是國(guó)際標(biāo)準(zhǔn)化組織OMG發(fā)布的一種圖形化建模語(yǔ)言，主要針對(duì)UI驅(qū)動(dòng)類軟件的交互過(guò)程進(jìn)行設(shè)計(jì)建模，其特點(diǎn)是以UI界面和交互元素為主要對(duì)象刻畫(huà)執(zhí)行過(guò)程。本文工作主要參考了IFML的建模方式，并針對(duì)移動(dòng)應(yīng)用軟件的特點(diǎn)進(jìn)行了定制，提出了ARP模型用于描述測(cè)試腳本所對(duì)應(yīng)的執(zhí)行路徑信息。

ARP模型刻畫(huà)了移動(dòng)應(yīng)用及其運(yùn)行時(shí)的狀態(tài)，使用如下信息進(jìn)行建模：①應(yīng)用的元信息，包含應(yīng)用的名稱、概要、版本、開(kāi)發(fā)者等信息；②應(yīng)用的狀態(tài)集合；③應(yīng)用的執(zhí)行路徑，執(zhí)行路徑是一系列跳轉(zhuǎn)關(guān)系 ； ④應(yīng)用的場(chǎng)景信息，即應(yīng)用功能，它對(duì)應(yīng)著一系列帶標(biāo)注的路徑集合，路徑是跳轉(zhuǎn)的集合，標(biāo)簽信息指示了該路徑屬于應(yīng)用某個(gè)具體的功能場(chǎng)景，標(biāo)簽信息也是本文方法需要自動(dòng)標(biāo)注(泛化)的對(duì)象。

構(gòu)建ARP模型部分將人工測(cè)試模型及自動(dòng)化測(cè)試模型，處理加工為統(tǒng)一格式的ARP模型便于后續(xù)進(jìn)一步的處理。

1.2 圖遍歷

圖遍歷部分主要實(shí)現(xiàn)標(biāo)簽泛化功能，其依賴兩個(gè)相似度判斷模塊，分別是針對(duì)狀態(tài)的狀態(tài)相似度模塊與針對(duì)狀態(tài)間跳轉(zhuǎn)的跳轉(zhuǎn)相似度模塊。在計(jì)算兩種相似度的前提下，圖遍歷模塊使用一種基于寬度優(yōu)先搜索(breadth-first search，BFS)的方法尋找與給定場(chǎng)景路徑所匹配的子圖，然后使用深度優(yōu)先搜索(depth-first search，DFS)得到子圖中的對(duì)應(yīng)相應(yīng)功能場(chǎng)景的所有路徑。

1.3 模型合并

模型合并部分接受ARP模型，將兩種來(lái)源的ARP模型合并為一個(gè)ARP模型，格式不變，對(duì)于不同來(lái)源的狀態(tài)會(huì)以不同的前綴進(jìn)行標(biāo)注區(qū)分，還會(huì)將圖遍歷模塊得出的場(chǎng)景路徑添加到合并后的新模型上。這些新的模型組成了移動(dòng)應(yīng)用有功能場(chǎng)景標(biāo)注的模型庫(kù)。將狀態(tài)集合合并后，對(duì)于跳轉(zhuǎn)模型，引入一個(gè)新的偽狀態(tài)作為合并后的ARP狀態(tài)入口點(diǎn)，在偽狀態(tài)和原本模型的入口狀態(tài)間添加跳轉(zhuǎn)關(guān)系。

2 方法實(shí)現(xiàn)

該部分介紹AFSLM具體實(shí)現(xiàn)的細(xì)節(jié)，相應(yīng)的工具原型是基于Python語(yǔ)言來(lái)編寫(xiě)的可執(zhí)行腳本。

2.1 實(shí)現(xiàn)構(gòu)建ARP模型

在具體實(shí)現(xiàn)時(shí)，各個(gè)狀態(tài)附帶的信息可以通過(guò)文件系統(tǒng)組織，使用時(shí)以讀取文件的形式將其內(nèi)容讀入內(nèi)存即可。對(duì)于模型的跳轉(zhuǎn)關(guān)系，其內(nèi)存形式本文選擇使用Python的第三方庫(kù)NetworkX實(shí)現(xiàn)，而持久化存儲(chǔ)則選擇JSON格式的文件。

圖2是一個(gè)有兩個(gè)節(jié)點(diǎn)的有向圖的JSON對(duì)象和Python代碼的表示方法，有向圖中有一條從狀態(tài)1指向狀態(tài)2的邊，其邊有兩個(gè)屬性：weight和time_sequence。

圖2 有向圖的兩種表示方法

構(gòu)建ARP模型時(shí)，本文將應(yīng)用狀態(tài)使用唯一序號(hào)進(jìn)行標(biāo)注，使用序號(hào)命名應(yīng)用所對(duì)應(yīng)的布局文件，然后將跳轉(zhuǎn)信息轉(zhuǎn)換成上述的JSON格式，狀態(tài)的序號(hào)作為圖的節(jié)點(diǎn)，跳轉(zhuǎn)關(guān)系作為圖的邊，而跳轉(zhuǎn)動(dòng)作作為邊的附加信息，如果一對(duì)狀態(tài)間有多個(gè)跳轉(zhuǎn)，則不同的跳轉(zhuǎn)動(dòng)作組織成一個(gè)列表。除此之外，本文還在預(yù)處理時(shí)篩去了跳轉(zhuǎn)模型中的自環(huán)，對(duì)于應(yīng)用元數(shù)據(jù)和場(chǎng)景路徑等信息，也同樣處理為JSON格式的文件進(jìn)行保存。工具運(yùn)行時(shí)將JSON格式的跳轉(zhuǎn)模型讀入內(nèi)存，轉(zhuǎn)換成Python中的字典格式，然后創(chuàng)建NetworkX有向圖對(duì)象。

該部分實(shí)現(xiàn)為一個(gè)單獨(dú)的腳本文件，調(diào)用后將原始數(shù)據(jù)轉(zhuǎn)換并輸出為預(yù)處理后的ARP模型，后續(xù)的工具主體將基于該輸出結(jié)果進(jìn)行處理，這樣設(shè)計(jì)的靈感來(lái)自于編譯器前后端分離的思路，該部分要處理多種不同來(lái)源的模型數(shù)據(jù)，需要針對(duì)不同的情況進(jìn)行修改或擴(kuò)展，這種特性決定了該部分和后續(xù)的合并主體不能有過(guò)高的耦合度。解耦后可以將多種不同的ARP構(gòu)建模塊與合并工具進(jìn)行組合，使用時(shí)只需鏈?zhǔn)秸{(diào)用即可。

2.2 實(shí)現(xiàn)相似度算法

移動(dòng)應(yīng)用UI使用XML文檔作為布局的描述格式，現(xiàn)在主流移動(dòng)應(yīng)用自動(dòng)化測(cè)試框架均提供工具用以在測(cè)試時(shí)動(dòng)態(tài)查看當(dāng)前的布局信息，并且可以將布局信息持久化為外存中的文件(通常同樣為XML格式)。持久化的動(dòng)態(tài)布局信息可以作為ARP模型狀態(tài)的布局信息。

此前已經(jīng)有不少工作探索了XML文檔的相似度計(jì)算，包括基于語(yǔ)義和結(jié)構(gòu)的XML文檔相似度計(jì)算[13]、基于樹(shù)編輯距離下界的相似度估計(jì)[14]、基于有效路徑權(quán)重的XML匹配算法[15]等。本文實(shí)現(xiàn)了其中一些算法，并且針對(duì)UI布局文件的特殊性做出了針對(duì)性的調(diào)整，也統(tǒng)一了相似度算法模塊的接口，使得狀態(tài)相似度算法可插拔可配置，不同的方法接受相同形式的輸入?yún)?shù)，輸出在[0，1]區(qū)間內(nèi)的相似度數(shù)值，這樣的設(shè)計(jì)使得無(wú)需修改泛化算法的其它部分即可方便地更換相似度算法。且只要封裝為統(tǒng)一的接口，就可以輕松地添加新的相似度算法。

另外，在ARP模型中，除了狀態(tài)本身附帶的信息，觸發(fā)狀態(tài)間跳轉(zhuǎn)動(dòng)作的信息也是十分重要的。在進(jìn)行場(chǎng)景標(biāo)注的過(guò)程時(shí)，僅僅考慮狀態(tài)間的相似程度是不夠完善的，一條場(chǎng)景功能路徑同樣需要考慮到狀態(tài)間跳轉(zhuǎn)動(dòng)作的匹配程度。本文提出并實(shí)現(xiàn)了一種較為簡(jiǎn)單直觀的跳轉(zhuǎn)相似度判斷算法，通過(guò)對(duì)比跳轉(zhuǎn)動(dòng)作的交互區(qū)域進(jìn)行相似度判斷。

2.2.1 基于語(yǔ)義和結(jié)構(gòu)的相似度判斷

文獻(xiàn)[13]所提出的基于語(yǔ)義和結(jié)構(gòu)的XML文檔相似度判斷方法，該算法整體分為3個(gè)層級(jí)：①基于語(yǔ)義相似度與編輯距離計(jì)算節(jié)點(diǎn)間相似度，②基于動(dòng)態(tài)規(guī)劃方法計(jì)算路徑的相似度，③將XML文檔分解成從根節(jié)點(diǎn)出發(fā)的路徑集合，基于路徑間的相似度計(jì)算路徑集合的相似度。本文針對(duì)布局文件的特殊性對(duì)于3個(gè)層級(jí)都做了相應(yīng)的修改。

首先是節(jié)點(diǎn)間相似度，原算法計(jì)算的對(duì)象是自然語(yǔ)言文本，算法會(huì)將文本分詞后計(jì)算其語(yǔ)義相似度，同時(shí)計(jì)算文本的字符編輯距離相似度，取二者的最大值作為節(jié)點(diǎn)的相似度。布局文件XML樹(shù)的節(jié)點(diǎn)是組件，其本身除了屬性并沒(méi)有其它內(nèi)容，組件屬性中text、content-desc、resource-id以及package幾個(gè)對(duì)相似度的判斷比較重要。計(jì)算節(jié)點(diǎn)相似度時(shí)，首先判斷兩個(gè)節(jié)點(diǎn)的class屬性與package屬性是否相同，如果不同則認(rèn)為兩個(gè)組件相似度為0，如果相同則將text，resource-id，content-desc這3個(gè)屬性的值拼接為一個(gè)字符串，使用字符編輯距離相似度作為節(jié)點(diǎn)的相似度。

在計(jì)算路徑相似度時(shí)，原算法提出了一種基于最大相似子序列(maximal similar subsequence，MSS)的路徑相似度定義。算法提出XML文檔中距離根節(jié)點(diǎn)更加近的節(jié)點(diǎn)往往更能反映文檔的結(jié)構(gòu)信息，因此在定義路徑相似度時(shí)加入了基于深度的衰減因子，然而對(duì)于布局文件來(lái)說(shuō)，距離根節(jié)點(diǎn)更近的組件通常是容器而非具體的控件，對(duì)于兩個(gè)狀態(tài)布局來(lái)說(shuō)，控件相比容器往往含有更多的信息，因此在實(shí)現(xiàn)路徑相似度算法時(shí)，本文去掉了這個(gè)衰減因子，使用最大相似子序列作為路徑相似度，具體實(shí)現(xiàn)采用動(dòng)態(tài)規(guī)劃的方法。

對(duì)于XML文檔得到的路徑集合的相似度，本文直接使用了原算法的方法，并沒(méi)有進(jìn)行額外的修改，最終輸出的相似度被歸一化至[0，1]區(qū)間內(nèi)。

2.2.2 基于樹(shù)編輯距離下界的相似度判斷

樹(shù)編輯距離(tree edit distance)是一種衡量樹(shù)結(jié)構(gòu)之間相似度的參數(shù)，與字符編輯距離類似，其定義為將一顆樹(shù)通過(guò)插入/刪除/替換轉(zhuǎn)換為另一顆樹(shù)所需要的最小操作次數(shù)。顯然樹(shù)編輯距離越小，兩棵樹(shù)越相似。文獻(xiàn)[14]提出可以通過(guò)多種方法估計(jì)樹(shù)編輯距離的下界，通過(guò)取這些方法得出的編輯距離的最大值，即可較好地逼近真實(shí)的樹(shù)編輯距離。

原算法首先提出可以通過(guò)將樹(shù)轉(zhuǎn)換為字符序列，然后以字符序列的編輯距離作為樹(shù)編輯距離的下界。由于樹(shù)編輯距離是以節(jié)點(diǎn)為單位進(jìn)行操作，因此在將樹(shù)轉(zhuǎn)換為字符序列時(shí)，每個(gè)節(jié)點(diǎn)需要對(duì)應(yīng)一個(gè)字符。其中text、resour-ceid、content-desc屬性并不是所有節(jié)點(diǎn)都有非空的值，package屬性取值范圍較小，而class屬性既能較好地反映布局的結(jié)構(gòu)，又具有有限的取值范圍，因此本文選擇將每個(gè)節(jié)點(diǎn)的class屬性映射為一個(gè)字符，得到一棵部分程度上反映布局組件嵌套結(jié)構(gòu)的樹(shù)，對(duì)這棵樹(shù)分別做前序遍歷與后序遍歷，得到的字符序列可以用于計(jì)算字符編輯距離，字符編輯距離的最大值即為樹(shù)編輯距離的一個(gè)下界。

除了上述基于字符編輯距離的方法，文獻(xiàn)中同樣提出3種基于直方圖的估算下界的方法，本文實(shí)現(xiàn)了其中基于葉距離直方圖和度直方圖的方法。本文同樣實(shí)現(xiàn)了文獻(xiàn)中提出的基于二叉距離的估算方法，該方法兼顧了樹(shù)的結(jié)構(gòu)信息和內(nèi)容信息。在判斷兩個(gè)界面之間相似度的方法上，本文參考了Q-testing[4]的方法，將代表界面結(jié)構(gòu)的layout樹(shù)形結(jié)構(gòu)文件內(nèi)容，編碼為214維向量，并使用文獻(xiàn)[4]中的LSTM預(yù)訓(xùn)練模型計(jì)算相似度，最后映射為一個(gè)[0，1]的值。

2.2.3 基于LSTM的相似度判斷

Q-testing[4]是一個(gè)基于強(qiáng)化學(xué)習(xí)策略的Android應(yīng)用自動(dòng)化探索的框架，其用馬爾可夫決策過(guò)程描述對(duì)Android應(yīng)用的探索過(guò)程，使用Q-learning的策略指導(dǎo)探索應(yīng)用的過(guò)程，可以在較短的時(shí)間內(nèi)達(dá)到較高的覆蓋度。Q-testing工具調(diào)用原生的UI Automator框架驅(qū)動(dòng)應(yīng)用和獲取應(yīng)用狀態(tài)信息。

在基于強(qiáng)化學(xué)習(xí)的自動(dòng)化測(cè)試工具Q-testing中使用狀態(tài)的相似度作為強(qiáng)化學(xué)習(xí)策略的獎(jiǎng)賞，驅(qū)動(dòng)工具盡可能探索更多不同的狀態(tài)。

Q-testing使用LSTM模型抽取狀態(tài)的特征，對(duì)于狀態(tài)的布局樹(shù)，其遍歷樹(shù)中的每個(gè)節(jié)點(diǎn)，將組件的屬性編碼為長(zhǎng)度214的向量，整棵樹(shù)會(huì)被編碼成214*100的矩陣(組件數(shù)不夠的用0做填充)作為L(zhǎng)STM的輸入，輸出一個(gè)長(zhǎng)為100的特征向量，計(jì)算向量的L1距離可以得到兩個(gè)狀態(tài)的相似度。

在判斷兩個(gè)界面之間相似度的方法上，本文參考了Q-testing[4]的方法，將代表界面結(jié)構(gòu)的layout樹(shù)形結(jié)構(gòu)文件內(nèi)容，編碼為214維向量，并使用文獻(xiàn)[4]中的LSTM預(yù)訓(xùn)練模型計(jì)算相似度，最后映射為一個(gè)[0，1]的值。

2.2.4 跳轉(zhuǎn)相似度判斷

本文提出的跳轉(zhuǎn)相似度判斷算法，較為簡(jiǎn)單直觀，通過(guò)比對(duì)跳轉(zhuǎn)動(dòng)作的交互區(qū)域進(jìn)行相似度判斷。

對(duì)于有交互區(qū)域的動(dòng)作，模型會(huì)記錄下兩個(gè)坐標(biāo)，分別代表交互區(qū)域的左上端點(diǎn)和右下端點(diǎn)。在比較兩個(gè)跳轉(zhuǎn)動(dòng)作時(shí)，算法會(huì)首先嘗試通過(guò)正則表達(dá)式匹配的方式提取交互區(qū)域坐標(biāo)，如果兩個(gè)動(dòng)作都是有交互區(qū)域的，則比較其交互區(qū)域的重疊程度，算法會(huì)首先根據(jù)截屏文件對(duì)應(yīng)的分辨率將兩個(gè)坐標(biāo)歸一化到[0，1]區(qū)間，然后計(jì)算兩個(gè)區(qū)域的Jaccard Index，如式(1)所示

(1)

兩個(gè)區(qū)域相交的面積除以兩個(gè)區(qū)域相并的面積，這是一個(gè)常用的集合相似度判斷方法。Jaccard Index 會(huì)輸出一個(gè)[0，1]區(qū)間的結(jié)果，越接近1說(shuō)明兩個(gè)區(qū)域重合程度越高。在實(shí)際實(shí)驗(yàn)時(shí)，本文發(fā)現(xiàn)在實(shí)驗(yàn)數(shù)據(jù)中會(huì)有兩個(gè)交互區(qū)域包含的情況，如果按照公式計(jì)算并不會(huì)得到很高的相似度分?jǐn)?shù)，但是在觀察原始數(shù)據(jù)后，本文發(fā)現(xiàn)這往往是同一個(gè)交互動(dòng)作，交互區(qū)域產(chǎn)生區(qū)別的原因是不同來(lái)源的建模數(shù)據(jù)會(huì)將同樣的操作定位到不同控件，一個(gè)常見(jiàn)的例子是點(diǎn)擊一個(gè)列表項(xiàng)，有些記錄會(huì)定位到外層的Linear-Layout，而有些記錄會(huì)定位到內(nèi)層的TextView。

為了處理這種情況，本文額外添加了規(guī)則，如果兩個(gè)區(qū)域成包含關(guān)系，則認(rèn)為其相似度為1.0。這也比較符合設(shè)計(jì)移動(dòng)應(yīng)用的原則與使用時(shí)的經(jīng)驗(yàn)，如果兩個(gè)交互區(qū)域包含，其通?？梢杂|發(fā)相同的交互動(dòng)作，一個(gè)比較典型的例子是大部分App的設(shè)置界面有可開(kāi)關(guān)的選項(xiàng)，點(diǎn)擊Switch控件/文字標(biāo)簽或是點(diǎn)擊該選項(xiàng)的容器部分都能切換功能的開(kāi)關(guān)。

對(duì)于沒(méi)有交互區(qū)域的動(dòng)作，這些動(dòng)作除了滑動(dòng)外基本都是系統(tǒng)事件，如Android的3個(gè)虛擬按鍵：menu、back、recent apps，對(duì)于這些動(dòng)作，本文選擇采用正則表達(dá)式將動(dòng)作類型提取出來(lái)，然后比較其是否相同，如果相同則認(rèn)為動(dòng)作相似度為1.0，否則為0.0。

跳轉(zhuǎn)動(dòng)作相似度算法(算法1)的偽代碼如下：

算法1：跳轉(zhuǎn)動(dòng)作相似度算法

Input：兩個(gè)待比較的動(dòng)作

Output：動(dòng)作的相似度

(1) if 兩個(gè)動(dòng)作都有交互區(qū)域 then

(2) 計(jì)算兩個(gè)動(dòng)作交互區(qū)域的Jaccard Index

(3) if兩個(gè)交互區(qū)域成包含關(guān)系then

(4) return 1.0

(5) else

(6) returnJaccardIndex

(7) end

(8) else if 兩個(gè)動(dòng)作均有交互事件 then

(9) if交互事件相同then

(10) return 1.0

(11) else

(12) return 0.0

(13) end

(14) else

(15) return 0.0

(16) end

由于跳轉(zhuǎn)模型中一對(duì)狀態(tài)間可能有多個(gè)跳轉(zhuǎn)動(dòng)作，在實(shí)際計(jì)算時(shí)，會(huì)對(duì)兩個(gè)跳轉(zhuǎn)動(dòng)作列表中的每對(duì)跳轉(zhuǎn)動(dòng)作分別計(jì)算相似度，結(jié)果取所有相似度的最大值。

2.3 實(shí)現(xiàn)圖遍歷

圖遍歷部分實(shí)現(xiàn)了一種基于寬度優(yōu)先搜索(breadth-first search，BFS)的圖遍歷算法，用于將人工測(cè)試路徑對(duì)應(yīng)的場(chǎng)景功能標(biāo)注泛化到ARP模型的無(wú)場(chǎng)景標(biāo)注的跳轉(zhuǎn)模型中。算法分為兩個(gè)部分，遍歷算法主體——標(biāo)簽泛化算法以及一個(gè)Wrapper。標(biāo)簽泛化算法接受一個(gè)圖中的結(jié)點(diǎn)作為輸入，輸出一個(gè)以該節(jié)點(diǎn)為根的有向無(wú)環(huán)圖，該圖中的路徑即是算法判斷與場(chǎng)景路徑相匹配的路徑，標(biāo)簽泛化算法(算法2)的偽代碼如下所示：

算法2：標(biāo)簽泛化算法

Input：起始節(jié)點(diǎn)，跳轉(zhuǎn)模型，場(chǎng)景路徑

Output：匹配的子圖

(1)初始化隊(duì)列q, 將起始節(jié)點(diǎn)放入q;

(2) 初始化結(jié)果圖G;

(3) 初始化已訪問(wèn)節(jié)點(diǎn)集合visited;

(4) fori∈[1,len(path)] do

(5) 初始化隊(duì)列temp;

(6)visited←visited∪q;

(7) foreachnode∈qdo

(8) 將node加入G;

(9) 獲取場(chǎng)景路徑從第i-1個(gè)狀態(tài)到第i個(gè)狀態(tài)的跳轉(zhuǎn)動(dòng)作;

(10) 根據(jù)跳轉(zhuǎn)動(dòng)作相似度與狀態(tài)相似度,調(diào)用算法3, 獲取下一跳的節(jié)點(diǎn)列表next_nodes;

(11)next_nodes←next_nodesvisited;

(12)foreachnext_node∈next_nodesdo

(13) 在G中加入邊(node, next_node);

(14) 將next_node放入temp;

(15)end

(16)end

(17) q←temp;

(18)end

(19)returnG

算法2使用一個(gè)隊(duì)列存儲(chǔ)當(dāng)前待處理的節(jié)點(diǎn)列表，并且在獲取下一跳的節(jié)點(diǎn)列表時(shí)會(huì)篩去已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，以確保結(jié)果圖是一個(gè)有向無(wú)環(huán)圖。算法2較為核心的是如何獲取下一跳節(jié)點(diǎn)列表的部分，該部分使用了上文提到的狀態(tài)相似度模塊與跳轉(zhuǎn)相似度模塊，獲取下一跳節(jié)點(diǎn)算法(算法3)的偽代碼如下所示：

算法3：獲取下一跳節(jié)點(diǎn)列表

Input：當(dāng)前節(jié)點(diǎn)，跳轉(zhuǎn)模型，源跳轉(zhuǎn)動(dòng)作，源節(jié)點(diǎn)，狀態(tài)相似度算法，相似度閾值

Output：下一跳節(jié)點(diǎn)列表

(1)初始化列表next_nodes;

(2)根據(jù)跳轉(zhuǎn)模型, 獲取當(dāng)前節(jié)點(diǎn)的所有后繼結(jié)點(diǎn)succs;

(3)foreachsucc∈succsdo

(4) 根據(jù)跳轉(zhuǎn)模型, 獲取從當(dāng)前節(jié)點(diǎn)到succ的跳轉(zhuǎn)動(dòng)作;

(5) 調(diào)用算法1, 計(jì)算源跳轉(zhuǎn)動(dòng)作與目的跳轉(zhuǎn)動(dòng)作的相似度action_sim;

(6) 計(jì)算源節(jié)點(diǎn)與succ的狀態(tài)相似度state_sim;

(7) similarity←action_sim+state_sim;

(8)ifsimilarity≥相似度閾值then

(9) 將succ加入next_nodes;

(10)end

(11)end

(12)returnnext_nodes

在算法3中將狀態(tài)相似度算法作為參數(shù)在調(diào)用時(shí)傳入，針對(duì)不同的相似度算法，本文給出了不同的相似度閾值。遍歷得到結(jié)果圖后，會(huì)從根節(jié)點(diǎn)出發(fā)遞歸進(jìn)行深度優(yōu)先搜索(depth-firstsearch，DFS)，由于結(jié)果圖是一個(gè)有向無(wú)環(huán)圖，這個(gè)遞歸過(guò)程一定能夠結(jié)束。算法使用一個(gè)棧驅(qū)動(dòng)DFS，這個(gè)棧同樣保存了從根節(jié)點(diǎn)出發(fā)到當(dāng)前節(jié)點(diǎn)的路徑，當(dāng)遍歷到?jīng)]有后繼的節(jié)點(diǎn)時(shí)(即標(biāo)簽泛化算法推進(jìn)到最后一步時(shí)加入圖的節(jié)點(diǎn))，便認(rèn)為得出了一條完整的路徑，會(huì)將此時(shí)的棧內(nèi)容保存下來(lái)，最終輸出一個(gè)路徑的集合。

除了遍歷結(jié)束后的DFS，遍歷前也需要確定起始節(jié)點(diǎn)，標(biāo)簽泛化Wrapper的功能就是在跳轉(zhuǎn)圖中選擇起始節(jié)點(diǎn)，并且對(duì)每個(gè)起始節(jié)點(diǎn)都運(yùn)行一次泛化算法，然后對(duì)得到的結(jié)果圖進(jìn)行遍歷得出路徑集合，最后將所有路徑的集合合并后輸出結(jié)果，標(biāo)簽泛化Wrapper算法(算法4)的偽代碼如下所示：

算法4：標(biāo)簽泛化wrapper

Input：跳轉(zhuǎn)模型，場(chǎng)景路徑

Output：路徑集合

(1) 初始化路徑集合 paths;

(2) 在跳轉(zhuǎn)模型中計(jì)算每個(gè)節(jié)點(diǎn)與場(chǎng)景路徑第一個(gè)節(jié)點(diǎn)的相似度, 取相似度從高到低前10個(gè)節(jié)點(diǎn)作為candidates;

(3)foreachcandidate∈candidatesdo

(4) 以 candidate 為起始節(jié)點(diǎn), 運(yùn)行標(biāo)簽泛化算法(算法2);

(5) 對(duì)得到的結(jié)果圖, 進(jìn)行DFS得到路徑集合 temp;

(6) 篩去temp中長(zhǎng)度小于1的路徑(即只有一個(gè)節(jié)點(diǎn)的路徑);

(7) paths ← paths∪temp;

(8)end

(9)returnpaths

由于場(chǎng)景路徑標(biāo)注是基于跳轉(zhuǎn)路徑的，因此會(huì)篩去結(jié)果中沒(méi)有形成路徑的輸出。在得到路徑集合后，會(huì)將場(chǎng)景標(biāo)注根據(jù)輸出結(jié)果添加到合并后的跳轉(zhuǎn)模型對(duì)應(yīng)路徑中。

基于以上方法，開(kāi)發(fā)了支撐命令行和API調(diào)用的原型工具，圖3展示了原型工具，用以支持批量數(shù)據(jù)處理和工具鏈的構(gòu)造。

圖3 AFSLM原型工具

3 實(shí)例研究

本文選擇開(kāi)源Android應(yīng)用WorldWeather作為研究對(duì)象，首先進(jìn)行人工測(cè)試，然后將測(cè)試數(shù)據(jù)構(gòu)建為ARP模型。在該模型中，本文選取了測(cè)試人員標(biāo)注的一條場(chǎng)景路徑：0-17-25-26，這條路徑代表的功能場(chǎng)景是調(diào)整應(yīng)用顯示溫度的單位(攝氏度/華氏度)(狀態(tài)0：起始狀態(tài)，狀態(tài)17：擴(kuò)展菜單，狀態(tài)25：設(shè)置界面，狀態(tài)26：溫度單位設(shè)置)，標(biāo)注的場(chǎng)景路徑如圖4所示。

圖4 人工標(biāo)注的場(chǎng)景路徑

接下來(lái)，AFSLM工具會(huì)同樣地將機(jī)器遍歷得到的路徑信息構(gòu)建為ARP模型，然后根據(jù)算法4得出需要遍歷的起始節(jié)點(diǎn)集合，如圖5所示。

圖5 獲取遍歷起始節(jié)點(diǎn)

在獲取了起始節(jié)點(diǎn)列表[62，16，0，1，8，58，59，15，23，49]后，工具會(huì)對(duì)列表中每個(gè)節(jié)點(diǎn)依次執(zhí)行算法2，這里本文以節(jié)點(diǎn)8作為例子，繼續(xù)演示工具的運(yùn)行流程。以節(jié)點(diǎn)8作為起始節(jié)點(diǎn)，工具會(huì)以寬度優(yōu)先搜索的形式開(kāi)始遍歷，由于給定場(chǎng)景路徑的長(zhǎng)度為4，故該遍歷會(huì)向外推進(jìn)3次。遍歷的過(guò)程中對(duì)于下一跳節(jié)點(diǎn)的選擇使用了相似度計(jì)算模塊的功能，具體細(xì)節(jié)參考算法1與算法3。為了避免遍歷結(jié)果圖產(chǎn)生環(huán)，本文在遍歷過(guò)程中記錄了已訪問(wèn)的節(jié)點(diǎn)集合。

如圖6所示，工具對(duì)每個(gè)起始節(jié)點(diǎn)都會(huì)進(jìn)行遍歷過(guò)程，得到機(jī)器跳轉(zhuǎn)模型的一個(gè)子圖，然后在子圖上進(jìn)行深度優(yōu)先搜索得到路徑集合。這里本文也挑選出一條路徑：8-5-6-25，展示其界面截屏與跳轉(zhuǎn)動(dòng)作。每個(gè)節(jié)點(diǎn)在遍歷后都會(huì)得到一個(gè)對(duì)應(yīng)的路徑集合，工具會(huì)篩去其中僅有一個(gè)狀態(tài)的路徑，然后將路徑集合合并至一個(gè)集合，輸出結(jié)果會(huì)傳遞給模型合并模塊，以在合并過(guò)程中進(jìn)行標(biāo)簽泛化。

圖6 圖遍歷模塊進(jìn)行功能場(chǎng)景標(biāo)簽泛化

模型合并部分讀取之前得到的兩個(gè)ARP模型，同時(shí)也讀取了圖遍歷模塊得出的場(chǎng)景路徑集合，然后將兩個(gè)ARP模型合并，并且將場(chǎng)景路徑標(biāo)簽泛化到合并后的模型上去。在實(shí)際運(yùn)行時(shí)一個(gè)人工模型會(huì)有不止一條標(biāo)注過(guò)的場(chǎng)景路徑，本文在構(gòu)建ARP模型后會(huì)對(duì)每條路徑進(jìn)行上述的泛化過(guò)程，并且用源路徑的功能標(biāo)簽和功能描述來(lái)標(biāo)注得出的路徑集合，最后再進(jìn)行模型合并，合并過(guò)程中將得出的所有結(jié)果路徑一次性泛化到合并的模型上。模型合并過(guò)程如圖7所示。

圖7 模型合并過(guò)程

4 實(shí)驗(yàn)評(píng)估

本文設(shè)計(jì)了實(shí)驗(yàn)用于測(cè)試所提方法的標(biāo)簽泛化效果，并且通過(guò)配置不同的相似度判斷算法，測(cè)試不同的算法在時(shí)間、泛化效果等方面的表現(xiàn)差異。

本文選擇開(kāi)源的Android用作為實(shí)驗(yàn)的對(duì)象，一共收集了5個(gè)不同類型App的模型數(shù)據(jù)，每個(gè)App有3個(gè)版本的模型，其中有兩個(gè)版本由測(cè)試人員手動(dòng)生成，測(cè)試人員使用Appium作為驅(qū)動(dòng)測(cè)試的框架，使用UIAutomatorViewer獲取App布局文件，并且根據(jù)布局信息編寫(xiě)相應(yīng)的Python測(cè)試腳本?；诓季治募鳛槟Ｐ偷臓顟B(tài)，基于測(cè)試腳本的定位和調(diào)用信息作為狀態(tài)間的跳轉(zhuǎn)。測(cè)試人員在測(cè)試的同時(shí)也給出了相應(yīng)的場(chǎng)景標(biāo)注信息，標(biāo)注信息由功能標(biāo)簽、功能描述以及對(duì)應(yīng)的場(chǎng)景路徑組成。除此之外，每個(gè)App還有一個(gè)無(wú)標(biāo)注的Q-testing工具探索模型。

將上述實(shí)驗(yàn)數(shù)據(jù)進(jìn)行預(yù)處理構(gòu)建ARP模型，得到了15個(gè)不同的ARP模型。在10個(gè)人工生成的模型中，篩選出32條功能各異的場(chǎng)景路徑，路徑長(zhǎng)度從2個(gè)狀態(tài)到6個(gè)狀態(tài)不等。實(shí)驗(yàn)時(shí)選擇對(duì)每個(gè)人工模型，將其與對(duì)應(yīng)的機(jī)器生成的模型合并，并且泛化該人工模型附帶的場(chǎng)景路徑標(biāo)注信息，一共得到 10個(gè)合并后的ARP模型。另，本文實(shí)現(xiàn)了3種不同的狀態(tài)相似度判斷算法，實(shí)驗(yàn)一共進(jìn)行了3組，用以對(duì)比不同算法的表現(xiàn)差異。為了能定量分析工具的泛化效果，本文定義了算法的匹配得分。對(duì)于一條有n個(gè)狀態(tài)的場(chǎng)景路徑：①如果其泛化的某條路徑有m個(gè)狀態(tài)與該場(chǎng)景匹配，則路徑的得分為m/n。②該場(chǎng)景路徑泛化的所有路徑得分的均值即為場(chǎng)景路徑的得分。③所有32條場(chǎng)景路徑得分的均值即為該算法的匹配得分。實(shí)驗(yàn)運(yùn)行環(huán)境為Windows10，IntelCorei5 2.5GHz，結(jié)果數(shù)據(jù)見(jiàn)表1。

表1 實(shí)驗(yàn)數(shù)據(jù)

針對(duì)該數(shù)據(jù)，本文設(shè)計(jì)了兩組研究問(wèn)題，通過(guò)實(shí)驗(yàn)數(shù)據(jù)得出結(jié)論：

(1)RQ1：面向場(chǎng)景的模型合并，AFSLM工具運(yùn)行的結(jié)果是否能夠擁有更多場(chǎng)景路徑信息標(biāo)注的模型？

以基于LSTM的相似度算法得出的數(shù)據(jù)為例，按照定義的評(píng)估標(biāo)準(zhǔn)，算法的匹配得分超過(guò)了0.8，且泛化后的路徑數(shù)有268條，遠(yuǎn)超原本人工模型作為輸入的32條路徑。在泛化的路徑中，超過(guò)四成是完全匹配，匹配程度過(guò)低的路徑占比不超過(guò)6%。據(jù)此可以看出，AFSLM有較好的效果，能夠?qū)F(xiàn)有模型的場(chǎng)景路徑標(biāo)記通過(guò)合并的方式泛化到規(guī)模更大的無(wú)標(biāo)注模型上去，得到含有更多場(chǎng)景標(biāo)注信息的模型。

(2)RQ2：相似度算法差異，不同的相似度算法在運(yùn)行時(shí)間，泛化效果等方面有怎樣的差異？

實(shí)驗(yàn)中更換不同的相似度比較算法，進(jìn)行了3組實(shí)驗(yàn)用于對(duì)比其效果差異，可以看出基于樹(shù)編輯距離下界的方法和基于 LSTM 的方法效果較好。在控制了泛化算法與跳轉(zhuǎn)相似度算法不變的情況下，本文改變了狀態(tài)相似度算法，比較了不同算法在各個(gè)維度的表現(xiàn)差異，這同樣也體現(xiàn)了AFSLM工具的靈活性，在未來(lái)可以實(shí)現(xiàn)更多的針對(duì)不同場(chǎng)景的算法，根據(jù)需要進(jìn)行配置使用。

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

本文針對(duì)移動(dòng)應(yīng)用功能場(chǎng)景識(shí)別的問(wèn)題進(jìn)行研究，提出了一種用于刻畫(huà)執(zhí)行過(guò)程特點(diǎn)的ARP模型，在此基礎(chǔ)上設(shè)計(jì)了度量功能場(chǎng)景相似度的模型匹配算法，并提出了相應(yīng)的功能場(chǎng)景自動(dòng)化標(biāo)注方法AFSLM，將人工標(biāo)注的模型泛化到自動(dòng)化工具探索的模型上，實(shí)現(xiàn)了對(duì)移動(dòng)應(yīng)用測(cè)試腳本中功能場(chǎng)景的自動(dòng)化標(biāo)注?；谒岢龇椒?，開(kāi)發(fā)了原型工具并進(jìn)行了相應(yīng)的實(shí)例研究及實(shí)驗(yàn)評(píng)估，展示出方法的有效性。本文的創(chuàng)新之處主要在于，通過(guò)建立反映移動(dòng)應(yīng)用程序執(zhí)行特點(diǎn)的ARP模型，并設(shè)計(jì)針對(duì)場(chǎng)景相似度的模型匹配算法，實(shí)現(xiàn)了對(duì)功能場(chǎng)景的識(shí)別和標(biāo)注。

本文方法的核心部分是功能場(chǎng)景相似度度量算法，在下一步的工作中，將結(jié)合計(jì)算機(jī)視覺(jué)技術(shù)，對(duì)UI界面的外觀特點(diǎn)進(jìn)行分析，用于提高度量算法的有效性，并選取更多的案例展開(kāi)實(shí)驗(yàn)。