毛群，王微微，尤楓，趙瑞蓮，李征

Android應(yīng)用的用戶行為模式挖掘及復(fù)用方法

毛群，王微微*，尤楓，趙瑞蓮，李征

（北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029）（ ? 通信作者電子郵箱wangww@mail.buct.edu.cn）

軟件測試是保障Android應(yīng)用質(zhì)量的有效手段，而理解Android應(yīng)用的功能作為Android測試過程的基礎(chǔ)，旨在深入探究應(yīng)用的業(yè)務(wù)邏輯并發(fā)現(xiàn)其功能問題，在測試中尤為重要。用戶行為模式可充分輔助測試人員理解Android應(yīng)用功能，從而提高測試效率?；凇跋嗨艫ndroid應(yīng)用共享用戶行為模式”的構(gòu)想，提出一種Android應(yīng)用的用戶行為模式挖掘及復(fù)用方法，以降低Android應(yīng)用測試成本并提高測試效率。具體而言，針對待測Android應(yīng)用，從其相似Android應(yīng)用挖掘出用戶行為模式；然后利用基于語義的事件模糊匹配策略為待測應(yīng)用尋找對應(yīng)事件，并基于用戶圖形界面（GUI）模型的最優(yōu)路徑選擇策略為待測應(yīng)用生成目標(biāo)事件序列，從而實(shí)現(xiàn)相似應(yīng)用間的用戶行為模式復(fù)用。針對三類應(yīng)用的32種用戶行為模式進(jìn)行實(shí)驗(yàn)，結(jié)果表明，87.4%的行為模式可在相似Android應(yīng)用上被完整復(fù)用，并且被復(fù)用的行為模式可有效覆蓋待測應(yīng)用中90.2%的重要狀態(tài)?？梢?，所提方法為Android應(yīng)用測試提供了有效支撐。

Android應(yīng)用；Android應(yīng)用測試；用戶行為模式；模式挖掘；模式復(fù)用

0 引言

智能手機(jī)和平板電腦的普及引起了開發(fā)人員對移動(dòng)應(yīng)用開發(fā)的極大興趣，隨著移動(dòng)平臺的蓬勃發(fā)展，移動(dòng)應(yīng)用的數(shù)量和功能復(fù)雜性也大幅提升。根據(jù)Gartner公司的調(diào)研報(bào)告［1］，截至2020年的第二季度，Android系統(tǒng)在智能手機(jī)市場的占有率達(dá)到了87%，是移動(dòng)市場的主流。相應(yīng)地，2020谷歌開發(fā)者大會表示，Google Play應(yīng)用商店中安卓應(yīng)用的下載量突破了485億。因此，如何保障Android應(yīng)用的質(zhì)量已成為開發(fā)和測試人員關(guān)注的重點(diǎn)。

軟件測試是驗(yàn)證Android應(yīng)用功能和可用性的重要手段，而理解應(yīng)用程序的功能作為軟件測試過程的基礎(chǔ)，旨在深入探究應(yīng)用的業(yè)務(wù)邏輯，發(fā)現(xiàn)其功能問題，在測試中尤為重要。理解應(yīng)用程序功能最直接的方式即為在實(shí)際使用場景下，用戶與應(yīng)用進(jìn)行真實(shí)交互，其交互序列稱為用戶軌跡。用戶軌跡雖可從用戶角度，給出應(yīng)用的功能業(yè)務(wù)邏輯，但未深入分析用戶軌跡之間的內(nèi)在關(guān)聯(lián)。為此，學(xué)者們又提出了用戶行為模式［2-4］，用以描述用戶軌跡之間的關(guān)聯(lián)關(guān)系，提取其行為共性，為應(yīng)用程序的功能測試提供了支撐。

在Web和Android應(yīng)用測試領(lǐng)域，均有借助用戶軌跡和用戶行為模式提高測試有效性的研究成果［5-13］發(fā)表。在Web應(yīng)用測試領(lǐng)域，Ermuth等［14］采用改進(jìn)的閉包序列模式挖掘技術(shù)CloSpan（Closed Sequential pattern mining）［15］，從Web應(yīng)用的用戶軌跡中推導(dǎo)其用戶行為模式，并結(jié)合隨機(jī)測試在應(yīng)用的模型上指導(dǎo)測試用例生成，以生成復(fù)雜且真實(shí)的事件序列。在Android應(yīng)用測試領(lǐng)域，Mao等［16］利用遺傳算法從眾包測試得到的用戶軌跡上學(xué)習(xí)通用的用戶行為模式，并將其用于基于多目標(biāo)搜索的測試序列生成及優(yōu)化［17］中，以提高Android應(yīng)用的Activity覆蓋率?？梢钥闯?，用戶軌跡和用戶行為模式通過借助人類經(jīng)驗(yàn)深入挖掘程序業(yè)務(wù)邏輯，可有效提高測試有效性。

若對于每個(gè)未知應(yīng)用，均采用用戶交互的方式理解應(yīng)用程序功能勢必會帶來極大的開銷，這不僅增加了人工成本，還會影響測試效率。近期研究［18-21］表明，相似Android應(yīng)用共享相似功能和工作流，即相似應(yīng)用共享用戶行為模式。用戶行為模式的復(fù)用不僅可節(jié)約人工成本，提高測試效率，還為理解應(yīng)用程序提供了一種新途徑。然而，現(xiàn)有研究大多關(guān)注用戶軌跡和用戶行為模式指導(dǎo)的測試用例生成，還尚未有Android應(yīng)用的用戶行為模式復(fù)用研究。

因此，本文提出一種Android應(yīng)用的用戶行為模式復(fù)用方法，即利用相似的已知應(yīng)用用戶行為模式，為待測應(yīng)用生成事件序列，以自動(dòng)理解待測應(yīng)用的功能，提高Android應(yīng)用的測試效率。Android應(yīng)用的用戶行為模式復(fù)用雖有理論依據(jù)，但仍面臨諸多挑戰(zhàn)：一是不同Android應(yīng)用的用戶圖形界面（Graphical User Interface， GUI）差異使得用戶行為模式復(fù)用時(shí)，事件難以直接匹配；二是不同Android應(yīng)用的工作流之間存在輕微差異，導(dǎo)致與用戶行為模式相匹配的待測應(yīng)用事件序列不連續(xù)。如何為相似的Android應(yīng)用自動(dòng)構(gòu)建事件映射關(guān)系，并為待測應(yīng)用生成可行連續(xù)的事件序列，是Android應(yīng)用用戶行為模式復(fù)用的關(guān)鍵問題。

考慮到相似Android應(yīng)用上實(shí)現(xiàn)相同功能的事件，其綁定的控件文本信息詞法不同但語義相似；且待測應(yīng)用的GUI模型可有效輔助可行連續(xù)的事件序列生成。因此，本文提出一種結(jié)合事件語義與GUI模型的Android應(yīng)用用戶行為模式挖掘及復(fù)用方法。具體而言，基于已知Android應(yīng)用的用戶軌跡，采用序列模式挖掘技術(shù)從中挖掘其用戶行為模式。在此基礎(chǔ)上，提出基于語義的事件模糊匹配策略和基于GUI模型的最優(yōu)路徑選擇策略，將用戶行為模式復(fù)用到相似待測Android應(yīng)用上，輔助待測應(yīng)用的功能理解，為Android應(yīng)用測試提供支持。

1 本文方法框架

本文方法主要分為Android應(yīng)用的用戶行為模式挖掘和相似Android應(yīng)用間的用戶行為模式復(fù)用兩個(gè)部分，其中，用戶行為模式復(fù)用又可分為事件匹配和序列生成兩個(gè)階段。本文方法的框架如圖1所示，包含以下3個(gè)模塊：

1）Android應(yīng)用的用戶行為模式挖掘。用戶軌跡和其用戶行為模式本質(zhì)上都是用戶交互產(chǎn)生的行為序列，可采用序列模式挖掘技術(shù)，從Android應(yīng)用的用戶軌跡中挖掘該應(yīng)用的用戶行為共性，形成用戶行為模式，進(jìn)而為后續(xù)的相似Android應(yīng)用間的用戶行為模式復(fù)用提供數(shù)據(jù)基礎(chǔ)。

2）基于語義的事件模糊匹配。從已知應(yīng)用的用戶行為模式和待測應(yīng)用的GUI模型中提取事件，分別得到源事件序列和目標(biāo)事件集合。對于源事件序列中的每個(gè)源事件，在目標(biāo)事件集合中尋找與之匹配的目標(biāo)事件加入候選事件集，由此得到與源事件序列對應(yīng)的候選事件集。

3）基于GUI模型的事件序列生成?；诤蜻x事件集，借助待測Android應(yīng)用的GUI模型，為不連續(xù)的候選事件間尋找最優(yōu)可行路徑，以生成連續(xù)可執(zhí)行的目標(biāo)事件序列。

圖1　用戶行為模式挖掘及復(fù)用方法框架

2 Android應(yīng)用的用戶行為模式挖掘及復(fù)用

2.1　Android應(yīng)用的用戶行為模式挖掘

本文利用動(dòng)態(tài)分析技術(shù)收集Android應(yīng)用的用戶軌跡，依據(jù)用戶軌跡的序列特性，提出一種基于序列模式挖掘技術(shù)的用戶行為模式挖掘方法。

Android應(yīng)用的用戶軌跡和用戶行為模式的相關(guān)定義如下：

定義3 用戶行為模式。用戶行為模式是在用戶軌跡集合中頻繁出現(xiàn)的子序列，且用戶行為模式之間不存在包含關(guān)系。給定用戶軌跡集合和最小支持度，則頻繁子序列集合記作：

用戶行為模式集合記作：

Android應(yīng)用的用戶行為模式挖掘問題可以表示為給定已知Android應(yīng)用的用戶軌跡集合和最小支持度閾值，挖掘得到支持度大于的用戶行為模式。

為收集用戶軌跡，需獲取用戶與Android應(yīng)用之間的動(dòng)態(tài)交互行為。Appium［22］是目前最強(qiáng)大的移動(dòng)應(yīng)用自動(dòng)化測試框架，可供用戶記錄事件序列的測試腳本。為獲取用戶軌跡，本文采用Appium記錄用戶與Android應(yīng)用之間的動(dòng)態(tài)交互行為。由于Appium只能捕獲事件信息，無法捕獲狀態(tài)信息，因此需要對錄制的測試腳本在事件前后插樁，并執(zhí)行插樁后的腳本以獲取用戶觸發(fā)的事件以及事件觸發(fā)前后的應(yīng)用狀態(tài)，從而構(gòu)成用戶軌跡。用戶對Android應(yīng)用的一次訪問過程為一條用戶軌跡，不同用戶的多次訪問共同構(gòu)成用戶軌跡集合，以用于用戶行為模式挖掘。

用戶軌跡是用戶與Andoird應(yīng)用交互產(chǎn)生的行為序列，故用戶行為模式挖掘問題與序列模式挖掘問題相似，可以采用序列模式挖掘技術(shù)解決用戶行為模式挖掘問題。CloFAST（Closed FAST sequence mining algorithm based on sparse id-lists）［23］是一種閉序列模式挖掘算法，可通過空間探索改善、支持度計(jì)數(shù)和搜索空間修剪來挖掘獲得更長的閉序列。由于用戶軌跡結(jié)構(gòu)復(fù)雜，在使用CloFAST對用戶軌跡集合挖掘用戶行為模式之前，需要對用戶軌跡進(jìn)行預(yù)處理，即識別相似的軌跡元素并用相同的標(biāo)記來表示它們。在此基礎(chǔ)上，利用CloFAST挖掘用戶行為模式。對于CloFAST的挖掘結(jié)果，由于閉序列模式存在冗余，本文將過濾被其他序列模式包含的序列模式，而保留較長的序列模式作為后續(xù)復(fù)用的用戶行為模式。

2.2　基于語義的事件模糊匹配

由于不同Android應(yīng)用上有實(shí)現(xiàn)相同功能的事件，其事件描述雖詞法不同但語義相似；因此，本文通過分析事件的語義特征，衡量事件之間的語義相似性，以實(shí)現(xiàn)相似應(yīng)用間的事件匹配。

由Android應(yīng)用事件的定義1可知，事件涉及的特征包括事件類型、事件觸發(fā)時(shí)所在的頁面以及事件綁定的GUI控件屬性。其中，事件的語義特征主要體現(xiàn)在和上。對于，它的語義來源于GUI控件的若干屬性值：1），開發(fā)人員對GUI控件的賦值通常能反映其提供的功能；2），一般顯示在GUI控件上，表示控件的名稱；3），指定GUI控件的文本描述，幫助用戶理解控件的功能；4）如果GUI控件沒有設(shè)置屬性和屬性，則需要從周圍一定范圍內(nèi)的GUI控件上獲取描述信息；5），編輯控件一般會設(shè)置此屬性，以顯示給用戶的提示信息；6），帶圖像的GUI控件設(shè)置此屬性為圖像文件名，以鏈接相應(yīng)的要顯示的圖像，由于圖像內(nèi)容通常會反映在圖像文件名中，因此也應(yīng)予以考慮。對于，其語義源于頁面的Activity組件名，其組件名通常能反映此頁面提供的主要功能，故需加以考慮。

為了建立源事件s和目標(biāo)事件t之間的匹配關(guān)系，需要先度量s和t之間的事件相似度。由于事件類型可以在粗粒度上區(qū)分事件，GUI控件的屬性值和事件所在頁面的Activity組件名可從語義上評估事件之間的功能相似性，因此，本文考慮1）事件類型、2）事件綁定的GUI控件的屬性和3）事件觸發(fā)時(shí)頁面的Activity組件名這3個(gè)方面，計(jì)算事件之間的相似度，公式如下：

其中：s和t分別是s和t的事件類型；semt（s，t）是s和t的屬性之間的語義相似度；act（s，t）是s和t的Activity組件名之間的語義相似度；和分別是公式中semt（s，t）和act（s，t）的權(quán)重，并且和之和等于1。

計(jì)算事件相似度之前，需要先計(jì)算兩個(gè)語義相似度semt（s，t）和act（s，t）。對于semt（s，t），相似事件綁定的GUI控件在語義上相似，且其語義有多個(gè)屬性來源，例如，TextView的反映其功能，而與之匹配的ImageView的圖像文件名反映其功能。因此，本文提出一種事件模糊匹配策略，該策略考慮不同屬性之間的交叉配對，以提高事件匹配的準(zhǔn)確度。

由于頁面的Activity組件名和GUI控件的屬性一樣，均可預(yù)處理為一組文本標(biāo)簽，act（s，t）的計(jì)算與屬性對（s，t）的語義相似度計(jì)算相似。在計(jì)算得到semt（s，t）和simact（s，t）之后，根據(jù)式（4），即可計(jì)算出s和t之間的事件相似度。對于用戶行為模式中的每個(gè)源事件s，將其與待測應(yīng)用上的所有目標(biāo)事件進(jìn)行相似度計(jì)算，相似度高于預(yù)設(shè)閾值的事件都作為s匹配的候選事件，以此作為后續(xù)目標(biāo)事件序列生成的基礎(chǔ)。

2.3　基于GUI模型的事件序列生成

在事件匹配階段，本文為用戶行為模式中的每個(gè)源事件構(gòu)建一個(gè)候選事件集，則可以得到一個(gè)與用戶行為模式的源事件序列對應(yīng)的候選事件集序列。由于相似Android應(yīng)用之間的工作流差異，導(dǎo)致待測應(yīng)用上的前后序候選事件之間不連續(xù)。本節(jié)旨在利用待測應(yīng)用的GUI模型建立候選事件之間的連續(xù)關(guān)系，擴(kuò)展生成可執(zhí)行的目標(biāo)事件序列。

定義4 GUI模型。Android應(yīng)用的GUI模型本質(zhì)上是有限狀態(tài)機(jī)（Finite State Machine， FSM），可由五元組（，0，，，）表示，是狀態(tài)集合，0是模型的初始狀態(tài)，是模型的終止?fàn)顟B(tài)集合，是事件集合，是遷移集合，其中每條遷移可表示為（s，，t），s和t分別是源狀態(tài)和目標(biāo)狀態(tài)，是觸發(fā)后致使s轉(zhuǎn)換成t的事件。

圖2　Android應(yīng)用的局部GUI模型

為了從候選路徑中選出最優(yōu)路徑以構(gòu)成目標(biāo)事件序列，本文提出一種最優(yōu)路徑選擇策略，即為候選路徑進(jìn)行優(yōu)先級排序，優(yōu)先級最高的候選路徑將被選擇作為目標(biāo)事件序列的片段。候選路徑的優(yōu)先級主要考慮兩方面：1）更接近源事件語義的候選事件應(yīng)被優(yōu)先選擇；2）實(shí)現(xiàn)相同功能的邏輯步驟在數(shù)量上接近，即連接候選事件的路徑應(yīng)盡可能短。因此，候選路徑的優(yōu)先級不僅取決于候選事件的語義相似性，還取決于候選路徑的長度。對于每條候選路徑，在事件相似度的基礎(chǔ)上引入路徑長度計(jì)算路徑優(yōu)先級，路徑優(yōu)先級計(jì)算公式如下：

在最優(yōu)路徑選擇策略的指導(dǎo)下，目標(biāo)事件序列生成的流程如下：對于用戶行為模式中源事件匹配得到的候選事件集，利用待測應(yīng)用的GUI模型生成當(dāng)前狀態(tài)到其中候選事件所在遷移的候選路徑，并選擇優(yōu)先級最高的候選路徑以擴(kuò)展目標(biāo)事件序列。然后執(zhí)行該候選路徑以驗(yàn)證其可行性，若該路徑是可執(zhí)行的，則繼續(xù)處理與下一個(gè)源事件匹配的候選事件；否則，該路徑將被標(biāo)記為不可行，且選擇次優(yōu)的候選路徑。若所有候選路徑都不可行，則將回溯到上一個(gè)源事件的候選事件集，并選擇另一條次優(yōu)可行的候選路徑加入目標(biāo)事件序列。重復(fù)此過程，直至用戶行為模式中所有源事件對應(yīng)的候選事件集都被遍歷，且最終得到一條可執(zhí)行的目標(biāo)事件序列。

2.4　復(fù)用算法復(fù)雜度分析

本文的用戶行為模式復(fù)用算法主要分為事件匹配和序列生成兩個(gè)階段。在事件匹配階段，需將用戶行為模式中的每個(gè)源事件與待測應(yīng)用上的所有目標(biāo)事件進(jìn)行事件相似度計(jì)算，因此，其時(shí)間復(fù)雜度為（*），是用戶行為模式中的源事件數(shù)量，是待測應(yīng)用上的目標(biāo)事件數(shù)量；在序列生成階段，假設(shè)候選事件集序列包含（≤）個(gè)候選事件集，每個(gè)候選事件集中包含個(gè)候選事件，對于每個(gè)候選事件，在GUI模型上可找到條從當(dāng)前狀態(tài)到該候選事件的候選路徑，由于算法為每個(gè)候選路徑計(jì)算路徑優(yōu)先級并排序驗(yàn)證路徑可行性，排序的時(shí)間復(fù)雜度是（log），因此在最好情況下（即不存在回溯），算法的時(shí)間復(fù)雜度為（*（*）*log（*）），在最壞情況下（即處理每個(gè)候選事件集都需要回溯），算法的時(shí)間復(fù)雜度為（！*（*）*log（*））。因此，在最壞情況下，相似Android應(yīng)用間的用戶行為模式復(fù)用方法算法的整體復(fù)雜度為（*+！*（*）*log（*））。

3 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文Android應(yīng)用的用戶行為模式挖掘與復(fù)用方法的有效性，從用戶行為模式挖掘方法的合理性、基于語義的事件模糊匹配策略的準(zhǔn)確性以及用戶行為模式復(fù)用方法的有效性三個(gè)方面出發(fā)，提出以下研究問題：

研究問題1 從Android應(yīng)用的用戶軌跡中挖掘得到的用戶行為模式是否可代表此類Android應(yīng)用的典型功能？

研究問題2 基于語義的事件模糊匹配策略能否準(zhǔn)確匹配事件？

研究問題3 本文用戶行為模式復(fù)用方法能否為待測Android應(yīng)用生成完整且有效的目標(biāo)事件序列？

針對上述研究問題，本文選取來自三種不同類型的12個(gè)開源Android應(yīng)用進(jìn)行實(shí)驗(yàn)，其詳細(xì)信息如表1所示。每種類型有4個(gè)Android應(yīng)用，其中，S1、N1和W1作為已知應(yīng)用，其余為待測應(yīng)用。為收集已知應(yīng)用的用戶軌跡，5個(gè)與本研究無關(guān)的人員使用Appium與其交互，他們對應(yīng)用的訪問過程完全依賴于其自身的使用習(xí)慣。另外，實(shí)驗(yàn)中最小支持度與用戶軌跡總數(shù)的比值（相對支持度）設(shè)為0.1，事件相似度閾值設(shè)為0.5，且事件相似度度量公式中的參數(shù)和分別設(shè)為2/3和1/3。

表1　實(shí)驗(yàn)中使用的Android應(yīng)用

3.1　評價(jià)指標(biāo)

為了評價(jià)基于語義的事件模糊匹配策略的準(zhǔn)確性，本文以事件匹配的精確率和召回率為評價(jià)指標(biāo)，其中精確率表示正確匹配的事件占所有實(shí)際匹配事件的比例，召回率表示正確匹配的事件占所有預(yù)期匹配事件的比例。事件匹配結(jié)果可細(xì)分為以下4種情況：1）正確匹配事件占比，即用戶行為模式中的源事件正確匹配到預(yù)期目標(biāo)事件的占比（即（True Positive））；2）錯(cuò)誤匹配事件占比，即用戶行為模式中的源事件沒有匹配到預(yù)期目標(biāo)事件，但匹配到了其他目標(biāo)事件的占比（即（False Positive））；3）正確未匹配事件占比，即用戶行為模式中的源事件沒有匹配到目標(biāo)事件，且待測應(yīng)用上不存在預(yù)期目標(biāo)事件的占比（即（True Negative））；4）錯(cuò)誤未匹配事件占比，即用戶行為模式中的源事件沒有匹配到目標(biāo)事件，但待測應(yīng)用上存在預(yù)期目標(biāo)事件的占比（即（False Negative））。用以上指標(biāo)計(jì)算事件匹配的精確率和召回率，其中：

為了評價(jià)用戶行為模式復(fù)用方法的有效性，本文考慮兩個(gè)方面，一是能否完整復(fù)用用戶行為模式，二是復(fù)用的用戶行為模式能否表征待測應(yīng)用的常用行為。

用戶行為模式復(fù)用的完整性主要反映在用戶行為模式被完整復(fù)用的占比（Completely-reused Rate）和被部分復(fù)用的占比（Partially-reused Rate）。具體而言，表示已知應(yīng)用的用戶行為模式在待測應(yīng)用上被完全重現(xiàn)的占比，而表示已知應(yīng)用的用戶行為模式在待測應(yīng)用上被部分重現(xiàn)的占比。

而復(fù)用的行為模式能否表征待測應(yīng)用的常用行為主要反映在生成的目標(biāo)事件序列是否可以覆蓋待測應(yīng)用的重要狀態(tài)。一般網(wǎng)絡(luò)中，介數(shù)中心性（Betweenness Centrality）可表征任意節(jié)點(diǎn)對之間的最短路徑需通過該節(jié)點(diǎn)的概率，標(biāo)志著該節(jié)點(diǎn)對節(jié)點(diǎn)間通信的控制能力。相應(yīng)地，在Android應(yīng)用的GUI模型中，本文認(rèn)為具有較高值的狀態(tài)更有可能被訪問，即該狀態(tài)在模型中的重要度更高。因此，本文采用狀態(tài)的介數(shù)中心性來表示該狀態(tài)的重要度。為了評價(jià)待測應(yīng)用的目標(biāo)事件序列，需計(jì)算待測應(yīng)用GUI模型上所有狀態(tài)的值，并按值從高到低將狀態(tài)排序。根據(jù)值將狀態(tài)分為3個(gè)重要度級別：級別1的范圍是狀態(tài)的前20%，級別2的范圍是狀態(tài)的前20%至50%，其余狀態(tài)被劃分為級別3。若目標(biāo)事件序列對重要度級別較高的狀態(tài)覆蓋更多，則表明本文的用戶行為模式復(fù)用方法可有效覆蓋待測應(yīng)用的常用行為。

3.2　用戶行為模式挖掘方法的合理性驗(yàn)證

用戶行為模式是Android應(yīng)用的常見用戶行為，標(biāo)志著該應(yīng)用的常用/典型功能。用戶行為模式挖掘方法的合理性在于，從應(yīng)用的用戶軌跡中挖掘得到的用戶行為模式能否代表該應(yīng)用的常用/典型功能。為了評估用戶行為模式挖掘方法的合理性，本文分析并概述了挖掘得到的用戶行為模式所涉及的功能。

表2為已知應(yīng)用的用戶軌跡和用戶行為模式挖掘的結(jié)果。

表2　用戶軌跡和用戶行為模式挖掘的結(jié)果

可以看出，對于已知應(yīng)用S1、N1和W1，分別從收集的用戶軌跡中挖掘出了13、5和14種用戶行為模式。以S1為例，通過分析該應(yīng)用的13種用戶行為模式，可以總結(jié)出它們代表的7種典型功能，分別是對特定列表或商品進(jìn)行添加、刪除和編輯操作，以及對列表中的商品進(jìn)行排序。顯然，這些功能在購物清單類應(yīng)用中普遍存在，很大程度上代表了此類應(yīng)用的典型功能。N1和W1的實(shí)驗(yàn)結(jié)果與S1一致，進(jìn)一步證實(shí)了用戶行為模式確實(shí)能代表同類型應(yīng)用的典型功能。需要注意的是，典型功能的數(shù)量不等于模式的數(shù)量，因?yàn)榇嬖谝环N常見情況，即使多種用戶行為模式的事件序列存在細(xì)微差異，但它們依然實(shí)現(xiàn)相同的功能。例如，S1中商品的刪除方式有兩種：一種是長按商品，然后點(diǎn)擊“刪除”操作；另一種是選中商品，打開選項(xiàng)菜單，然后點(diǎn)擊“刪除選中項(xiàng)目”操作。這兩種刪除方式都是實(shí)現(xiàn)商品刪除功能的常見用戶行為模式。

3.3　事件模糊匹配策略的準(zhǔn)確性驗(yàn)證

為了評估基于語義的事件模糊匹配策略的準(zhǔn)確性，本文在事件匹配階段分別對比了使用事件模糊匹配策略和不使用事件模糊匹配策略的結(jié)果，其事件匹配結(jié)果的詳細(xì)信息如表3所示。總體而言，在事件匹配階段使用事件模糊匹配策略平均達(dá)到了74.3%的精確率和94.7%的召回率，證明了事件模糊匹配策略的準(zhǔn)確性。具體來說，對于購物清單類應(yīng)用，事件模糊匹配策略平均將正確匹配事件占比提高了8.2個(gè)百分點(diǎn)，將錯(cuò)誤匹配事件占比降低了8.2個(gè)百分點(diǎn)；對于筆記類應(yīng)用，上述數(shù)值分別為12.8個(gè)百分點(diǎn)和3.9個(gè)百分點(diǎn)；對于天氣類應(yīng)用，上述數(shù)值分別為38.5個(gè)百分點(diǎn)和9.9個(gè)百分點(diǎn)。結(jié)果表明，事件模糊匹配策略能有效提高正確匹配的事件占比，降低有預(yù)期目標(biāo)事件卻未成功匹配的事件占比。進(jìn)而，對于購物清單類應(yīng)用，事件模糊匹配策略將事件匹配的精確率和召回率分別提高2.1個(gè)百分點(diǎn)和10.9個(gè)百分點(diǎn)；對于筆記類應(yīng)用，上述數(shù)值分別為10.5個(gè)百分點(diǎn)和8.6個(gè)百分點(diǎn)；對于天氣類應(yīng)用，上述數(shù)值分別為40.4個(gè)百分點(diǎn)和31.9個(gè)百分點(diǎn)。上述結(jié)果進(jìn)一步證明了事件模糊匹配策略對事件匹配準(zhǔn)確性的提升能力。

表3　使用和不使用模糊策略的事件匹配結(jié)果 單位：%

3.4　用戶行為模式復(fù)用方法的有效性驗(yàn)證

為了整體評估本文的用戶行為模式復(fù)用方法的有效性，本文統(tǒng)計(jì)了完整復(fù)用和部分復(fù)用的用戶行為模式數(shù)量，以及生成的目標(biāo)事件序列對待測應(yīng)用GUI模型的狀態(tài)覆蓋率。

圖3展示了用戶行為模式復(fù)用的完整性結(jié)果?？梢钥闯?，對于每個(gè)待測應(yīng)用，其與之和都為100%，說明實(shí)驗(yàn)中涉及的用戶行為模式均被復(fù)用?？傮w而言，和的平均值分別是87.4%和12.6%，這表明本文的用戶行為模式復(fù)用方法可以完整復(fù)用已知應(yīng)用的絕大多數(shù)用戶行為模式。

此外，通過分析生成的目標(biāo)事件序列，發(fā)現(xiàn)用戶行為模式中源事件的平均值為2.4%，相較于事件匹配階段的3.5%，降低了1.1個(gè)百分點(diǎn)，這說明在事件匹配階段的錯(cuò)誤未匹配事件在序列生成階段被成功復(fù)用。具體地，對比圖3中的與表3中的，可以發(fā)現(xiàn)，對于待測應(yīng)用N2，在事件匹配階段，有3.9%的源事件有預(yù)期目標(biāo)事件卻未在待測應(yīng)用上匹配到任何目標(biāo)事件，然而，經(jīng)過序列生成階段后，N2的達(dá)到了100%，說明在序列生成階段，錯(cuò)誤未匹配事件對應(yīng)的預(yù)期目標(biāo)事件被準(zhǔn)確補(bǔ)充至目標(biāo)事件序列中，從而使得用戶行為模式中的所有源事件被復(fù)用。由此可以證明，在目標(biāo)事件序列生成階段，借助待測應(yīng)用的GUI模型可以在序列中補(bǔ)充一些錯(cuò)誤未匹配事件的預(yù)期目標(biāo)事件，從而提升用戶行為模式的完整復(fù)用率。

圖3　用戶行為模式復(fù)用的完整性結(jié)果

表4展示了生成的目標(biāo)事件序列對目標(biāo)應(yīng)用的3個(gè)重要度級別的狀態(tài)覆蓋率。平均來說，生成的目標(biāo)事件序列對級別1、級別2和級別3的狀態(tài)覆蓋率分別是90.2%、73.0%和65.7%?？梢钥闯?，3個(gè)級別的狀態(tài)覆蓋率呈遞減關(guān)系，這表明生成的目標(biāo)事件序列更傾向于覆蓋重要度更高的狀態(tài)，即更可能被用戶訪問的狀態(tài)。因此，本文的用戶行為模式復(fù)用方法可有效生成覆蓋待測應(yīng)用常用行為的目標(biāo)事件序列。

表4　目標(biāo)事件序列對三個(gè)重要度級別的狀態(tài)覆蓋率 單位：%

4 結(jié)語

為了幫助用戶快速理解新應(yīng)用的功能，提升測試效率，本文提出一種Android應(yīng)用的用戶行為模式挖掘與復(fù)用方法。在模式挖掘階段，采用閉包序列模式挖掘技術(shù)CloFAST從已知應(yīng)用的用戶軌跡中挖掘用戶行為模式；在模式復(fù)用階段，利用基于語義的事件模糊匹配策略，實(shí)現(xiàn)相似Android應(yīng)用的事件匹配，利用基于GUI模型的最優(yōu)路徑選擇策略，建立候選事件之間的連續(xù)關(guān)系，為待測應(yīng)用生成連續(xù)可執(zhí)行的事件序列，實(shí)現(xiàn)相似Android應(yīng)用的用戶行為模式復(fù)用。實(shí)驗(yàn)結(jié)果表明，挖掘得到的用戶行為模式能代表同類型應(yīng)用的典型功能；基于語義的事件模糊匹配策略能夠有效提高事件匹配的準(zhǔn)確性，且絕大部分用戶行為模式可以被完整地復(fù)用，可有效覆蓋待測應(yīng)用的常用行為。

在未來工作中，我們計(jì)劃將Android應(yīng)用的用戶手勢納入研究，以擴(kuò)展更復(fù)雜的用戶交互場景；并且本文的研究成果可以與現(xiàn)有的Android自動(dòng)化測試方法結(jié)合使用，提升其測試效果及效率。

[1] Gartner， Inc. Gartner says global smartphone sales declined 20% in second quarter of 2020［EB/OL］. （2020-08-25） ［2021-02-12］.https：//www.gartner.com/en/newsroom/press-releases/2020-08-25-gartner-says-global-smartphone-sales-declined-20--in-.

[2] 劉洪輝，吳岳芬. 用戶行為模式挖掘問題的研究［J］. 計(jì)算機(jī)技術(shù)與發(fā)展， 2006， 16（5）：50-52， 55.（LIU H H， WU Y F. Research on user’s behavior pattern mining［J］. Computer Technology and Development， 2006， 16（5）： 50-52， 55.）

[3] 楊風(fēng)雷，閻保平. Web用戶行為模式挖掘研究［J］. 微電子學(xué)與計(jì)算機(jī)， 2008， 25（11）：146-149.（YANG F L， YAN B P. Research on Web usage mining［J］. Microelectronics and Computer， 2008， 25（11）： 146-149.）

[4] 姬浩博，王俊紅. 一種改進(jìn)的PrefixSpan算法及其在Web用戶行為模式挖掘中的應(yīng)用［J］. 計(jì)算機(jī)科學(xué)， 2016， 43（1）：25-29.（JI H B， WANG J H. Research on improved PrefixSpan algorithm and its application in Web user behavior patterns mining［J］. Computer Science， 2016， 43（1）： 25-29.）

[5] BROOKS P A， MEMON A M. Automated GUI testing guided by usage profiles［C］// Proceedings of the 22nd ACM/IEEE International Conference on Automated Software Engineering. New York： ACM， 2007： 333-342.

[6] LORENZOLI D， MARIANI L， PEZZè M. Automatic generation of software behavioral models［C］// Proceedings of the 30th International Conference on Software Engineering. New York： ACM， 2008： 501-510.

[7] WANG W W， GUO J X， LI Z， et al. EFSM-oriented minimal traces set generation approach for Web applications［C］// Proceedings of the IEEE 42nd Annual Computer Software and Applications Conference. Piscataway： IEEE， 2018： 12-21.

[8] WANG W W， GUO X H， Z. LI Z， et al. Test case generation based on client-server of Web applications by memetic algorithm［C］// Proceedings of the IEEE 30th International Symposium on Software Reliability Engineering. Piscataway： IEEE， 2019： 206-216.

[9] LINARES-VáSQUEZ M， WHITE M， BERNAL-CáRDENAS C， et al. Mining Android app usages for generating actionable GUI-based execution scenarios［C］// Proceedings of the IEEE/ACM 12th Working Conference on Mining Software Repositories. Piscataway： IEEE， 2015： 111-122.

[10] ERNST M D， COCKRELL J， GRISWOLD W G， et al. Dynamically discovering likely program invariants to support program evolution［J］. IEEE Transactions on Software Engineering， 2001， 27（2）： 99-123.

[11] ELBAUM S， ROTHERMEL G，KARRE S， et al.Leveraging user-session data to support Web application testing ［J］. IEEE Transactions on Software Engineering， 2005， 31（3）：187-202.

[12] MILANI FARD A， MIRZAAGHAEI M， MESBAH A. Leveraging existing tests in automated test generation for Web applications［C］// Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering. New York： ACM， 2014： 67-78.

[13] LIU P， ZHANG X Y， PISTOIA M， et al. Automatic text input generation for mobile testing［C］// Proceedings of the IEEE/ACM 39th International Conference on Software Engineering. Piscataway： IEEE， 2017： 643-653.

[14] ERMUTH M， PRADEL M. Monkey see， monkey do： effective generation of GUI tests with inferred macro events［C］// Proceedings of the 25th International Symposium on Software Testing and Analysis. New York： ACM， 2016：82-93.

[15] YAN X F， HAN J W， AFSHAR R. CloSpan： mining closed sequential patterns in large datasets［C］// Proceedings of the 3rd SIAM International Conference on Data Mining. Philadelphia， PA： Society for Industrial and Applied Mathematics， 2003： 166-177.

[16] MAO K， HARMAN M， JIA Y. Crowd intelligence enhances automated mobile testing［C］// Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. Piscataway： IEEE， 2017： 16-26.

[17] MAO K， HARMAN M， JIA Y. Sapienz： multi-objective automated testing for android applications［C］// Proceedings of the 25th International Symposium on Software Testing and Analysis. New York： ACM， 2016： 94-105.

[18] RAU A， HOTZKOW J， ZELLER A. Transferring tests across Web applications［C］// Proceedings of the 2018 International Conference on Web Engineering， LNCS 10845/LNISA 10845. Cham： Springer， 2018： 50-64.

[19] HU G， ZHU L J， YANG J F. AppFlow： using machine learning to synthesize robust， reusable UI tests［C］// Proceedings of the 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. New York： ACM， 2018： 269-282.

[20] LIN J W， JABBARVAND R， MALEK S. Test transfer across mobile apps through semantic mapping［C］// Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering. Piscataway： IEEE， 2019： 42-53.

[21] BEHRANG F， ORSO A. Test migration between mobile apps with similar functionality［C］// Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering. Piscataway： IEEE， 2019： 54-65.

[22] OpenJS Foundation. Appium： mobile app automation made awesome［EB/OL］. ［2020-08-25］.http：//appium.io.

[23] FUMAROLA F， LANOTTE P F， CECI M， et al. CloFAST： closed sequential pattern mining using sparse and vertical id-lists［J］. Knowledge and Information Systems， 2016， 48（2）：429-463.

[24] MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space［EB/OL］. （2013-09-07） ［2020-08-25］.https：//arxiv.org/pdf/1301.3781.pdf.

MAO Qun， born in 1997， M. S. candidate. Her research interest include software testing.

WANG Weiwei， born in 1990， Ph. D.， lecturer. Her research interests include Web application software testing， software modeling.

YOU Feng， born in 1963， M. S.， senior engineer. His research interests include software testing， software reliability， Web user behavior analysis.

ZHAO Ruilian， born in 1964， Ph. D.， professor. Her research interests include software testing， software reliability.

LI Zheng， born in 1974， Ph. D.， professor. His research interest include software regression testing.

Pattern mining and reuse method for user behaviors of Android applications

MAO Qun， WANG Weiwei*， YOU Feng， ZHAO Ruilian， LI Zheng

（，，100029，）

Software testing is an effective way to ensure the quality of Android applications. Understanding the functions of Android applications is the basis of the Android testing process. It aims to deeply explore the application’s business logic and reveal its functional defects， playing an important role in testing. User behavior patterns can assist testers in understanding an Android application’s functions， thereby improving test efficiency. Based on the idea “similar Android applications share user behavior patterns”， a user behavior pattern mining and reuse method was proposed to reduce the cost of Android application testing and improve the testing efficiency. Specifically， for the Android application under test， the user behavior patterns from a similar Android application were mined. Then， the semantic-based event fuzzy matching strategy was used to search the corresponding events for the application under test， and the Graphical User Interface （GUI） model based optimal path selection strategy was used to generate target event sequences for the application under test， thereby achieving user behavior pattern reuse across similar applications. The experiments were conducted on 32 user behavior patterns of three categories of Android applications. The results show that 87.4% of user behavior patterns can be completely reused on similar Android applications， and the reused user behavior patterns can effectively cover 90.2% of important states in applications under test. Thus， the proposed method provides effective support for the testing of Android applications.

Android application; Android application testing; user behavior pattern; pattern mining; pattern reuse

TP311.5

A

1001-9081（2022）07-2155-07

10.11772/j.issn.1001-9081.2021040652

The work is partially supported by National Natural Science Foundation of China （62077003， 61872026）.

2021?04?25；

2021?08?03；

2021?08?06。

國家自然科學(xué)基金資助項(xiàng)目（62077003， 61872026）。

毛群（1997—），女，湖南祁陽人，碩士研究生，主要研究方向：軟件測試； 王微微（1990—），女，河北滄州人，講師，博士，CCF會員，主要研究方向：Web應(yīng)用軟件測試、軟件建模； 尤楓（1963—），男，江蘇江都人，高級工程師，碩士，CCF會員，主要研究方向：軟件測試、軟件可靠性、Web用戶行為分析； 趙瑞蓮（1964—），女，山西忻州人，教授，博士，CCF會員，主要研究方向：軟件測試、軟件可靠性； 李征（1974—），男，河北清苑人，教授，博士，CCF會員，主要研究方向：軟件回歸測試。