鄭曉梅，錢正軒，李 剛，王天舒

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

0 引 言

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

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

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

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

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

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

1 方法概要

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

圖1 AFSLM方法整體框架

1.1 構(gòu)建ARP模型

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

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

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

1.2 圖遍歷

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

1.3 模型合并

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

2 方法實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.3 基于LSTM的相似度判斷

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

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

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

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

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

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

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

(1)

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

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

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

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

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

Input：兩個待比較的動作

Output：動作的相似度

(1) if 兩個動作都有交互區(qū)域 then

(2) 計算兩個動作交互區(qū)域的Jaccard Index

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

(4) return 1.0

(5) else

(6) returnJaccardIndex

(7) end

(8) else if 兩個動作均有交互事件 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)模型中一對狀態(tài)間可能有多個跳轉(zhuǎn)動作，在實際計算時，會對兩個跳轉(zhuǎn)動作列表中的每對跳轉(zhuǎn)動作分別計算相似度，結(jié)果取所有相似度的最大值。

2.3 實現(xiàn)圖遍歷

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

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

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

Output：匹配的子圖

(1)初始化隊列q, 將起始節(jié)點放入q;

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

(3) 初始化已訪問節(jié)點集合visited;

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

(5) 初始化隊列temp;

(6)visited←visited∪q;

(7) foreachnode∈qdo

(8) 將node加入G;

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

(10) 根據(jù)跳轉(zhuǎn)動作相似度與狀態(tài)相似度,調(diào)用算法3, 獲取下一跳的節(jié)點列表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使用一個隊列存儲當(dāng)前待處理的節(jié)點列表，并且在獲取下一跳的節(jié)點列表時會篩去已經(jīng)訪問過的節(jié)點，以確保結(jié)果圖是一個有向無環(huán)圖。算法2較為核心的是如何獲取下一跳節(jié)點列表的部分，該部分使用了上文提到的狀態(tài)相似度模塊與跳轉(zhuǎn)相似度模塊，獲取下一跳節(jié)點算法(算法3)的偽代碼如下所示：

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

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

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

(1)初始化列表next_nodes;

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

(3)foreachsucc∈succsdo

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

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

(6) 計算源節(jié)點與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)用時傳入，針對不同的相似度算法，本文給出了不同的相似度閾值。遍歷得到結(jié)果圖后，會從根節(jié)點出發(fā)遞歸進(jìn)行深度優(yōu)先搜索(depth-firstsearch，DFS)，由于結(jié)果圖是一個有向無環(huán)圖，這個遞歸過程一定能夠結(jié)束。算法使用一個棧驅(qū)動DFS，這個棧同樣保存了從根節(jié)點出發(fā)到當(dāng)前節(jié)點的路徑，當(dāng)遍歷到?jīng)]有后繼的節(jié)點時(即標(biāo)簽泛化算法推進(jìn)到最后一步時加入圖的節(jié)點)，便認(rèn)為得出了一條完整的路徑，會將此時的棧內(nèi)容保存下來，最終輸出一個路徑的集合。

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

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

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

Output：路徑集合

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

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

(3)foreachcandidate∈candidatesdo

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

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

(6) 篩去temp中長度小于1的路徑(即只有一個節(jié)點的路徑);

(7) paths ← paths∪temp;

(8)end

(9)returnpaths

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

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

圖3 AFSLM原型工具

3 實例研究

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

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

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

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

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

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

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

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

圖7 模型合并過程

4 實驗評估

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

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

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

表1 實驗數(shù)據(jù)

針對該數(shù)據(jù)，本文設(shè)計了兩組研究問題，通過實驗數(shù)據(jù)得出結(jié)論：

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

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

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

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

5 結(jié)束語

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

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