基于事件交互图的算法与研究

高秀慧,高建华

(上海师范大学计算机科学与技术系,上海200234)

基于事件交互图的算法与研究

高秀慧,高建华

(上海师范大学计算机科学与技术系,上海200234)

图形用户界面的质量直接影响整个软件系统的有效性和实用性,一般采用提取模型的方法对图形用户界面进行测试,目前常用的模型为事件流图和事件交互图,但是事件流图转换成事件交互图的算法较为复杂,为此,提出一种转换算法,对图形用户界面事件进行明确划分,利用模态窗口事件的特殊性优化原有算法。测试实例结果表明,该算法可用于图形用户界面,且与Memon算法相比,能更高效地获得更准确的数据。

图形用户界面;事件交互分类;事件流图;事件交互图;测试实例

1 概述

图形用户界面(Graphical User Interface,GUI)的质量直接影响了整个软件系统的有效性和实用性,所以图形用户界面的测试一直是研究热点[1], GUI测试最大的难点在于生成正确的事件序列(一个事件序列代表一个用户交互,即用户的一个行为——例如点击鼠标按钮、触发应用程序的事件、应用程序通过执行对应代码响应事件),因此用户的交互空间是无限的。解决此问题最有效的方法是通过算法自动从GUI上提取模型,该模型可运用图遍历算法枚举访问过的事件,生成测试集(一个测试对应于一组事件序列,路径即事件序列,测试长度即该模型的事件数目)。当然,模型的提取并不是精确提取,生成的测试集还会存在不可行的问题,可以通过定义新的测试覆盖准则和优化测试集[2]来提高测试有效性。GUI测试可以通过基于模型的方法系统生成事件序列,再对测试集进行优化。基于模型的算法是将代表事件的节点和代表事件序列的路径模拟成流程图,路径上的事件序列可以用于生成GUI测试集。到目前为止,对于GUI应用程序的测试,国内外的一些研究学者已取得了一些成果,这些学者利用GUI应用程序基于事件的特点来开发GUI测试模型。其中,最具有影响力的是Atif M.Memon,长期以来在GUI测试用例生成策略方面做了诸多研究[3-4],开发出最简单有效的基于事件的GUI测试方法是事件流图(Event Flow Graph,EFG)[5]和事件序列图[6](Event Sequence Graph,ESG)。这2个方法都以事件为中心[7],EFG 可 以 使 用 GUI抓 取 技 术 (GUI ripping)[8]和逆向工程技术[9](reverse engineering)自动构建。在提取后EFG转换成EIG的过程中,文献[10]算法对事件类型的分类不够明确,文献[11]算法适用于只有单个模态窗口的GUI应用程序,并且生成的事件交互图还不够精简。

本文为了优化EFG转换成EIG的转换算法,以及分类GUI事件的交互关系,通过为图形用户界面建立一个事件交互模型的方法,对原有算法获得的数据结果及转换原理进行分析,通过对模态窗口中的事件进行分类选择来优化算法,提出一种事件流图转换成事件交互图的算法,并且利用事件之间的交互关系,总结6种可能会引起测试集终止的事件交互类型。

2 相关工作

用户通过执行某些部件上的事件,例如点击按钮、打开菜单项或者填充数据等行为与GUI交互。图1(a)为简单例举的GUI应用程序,GUI应用程序共有10个事件。点击按钮“编辑”,打开下拉菜单选项共有 3个事件,分别为“保存”、“另存为”、“替换”;点击“替换”,弹出替换窗口,共有3个事件,分别为“文件名为”、“确定”、“取消”,此时Demo窗口仍能使用;点击“另存为”,弹出相应对话框窗口,共有3个事件,分别为“查找内容”、“替换为”、“关闭”,此时隐藏了Demo窗口(即Demo窗口内4个事件不能使用),点击“取消”,退出对话框并恢复到Demo窗口,箭头表示2张图之间的转换。

图1 图形用户界面实例和对应的模型

2.1 GUI模型

在许多复杂的以事件为中心的模型中,改进EFG可以得到更多模型:(1)事件交互模型[10](Event Interaction Graph,EIG)代表了系统中的一组事件更实用、更具扩展性;(2)事件语义交互模型[12](Event Semantic Interaction Graph,ESIG)模拟了一组“事件语义交互”关系,代表在语义层面上的一组相互影响的事件。本文主要介绍EFG模型和EIG模型,提出一种EFG到EIG的改进算法,通过实验证明算法的优越性。

2.1.1 事件流图

事件流图(Event Flow Graph,EFG)是一个有向图,模拟所有在GUI上可能被执行的(大量)事件交互,它被直接用于快速测试,抽象地模拟事件序列。在EFG中,节点表示GUI中的事件,边代表事件间的关系。图1(b)为实例对应的事件流图(EFG),即GUI上用户可能执行的所有交互的描述,可以用于生成GUI测试集。从节点nx到节点ny的一条边意味着ny代表的事件可能直接在nx代表的事件之后被执行,这种关系称之为“跟踪”。事件流图中共有10个事件组成,10个节点代表10个事件,每条边代表“跟踪”关系。举例,事件“另存为”跟踪“编辑”,“编辑”为初始事件,即用户最初的行为。

事件流图是一个有向图,箭头对应的路径不可逆,对事件流图定义如下:

定义1 EFG代表GUI上事件节点的集合N和边的一组有序对 (ex,ey)的集合E,其中, {ex,ey}⊆N,表示EFG中的有向边,当且仅当ey在ex之后执行,则(ex,ey)∈E。

举例:(编辑,保存),(另存为,文件名为),(替换为,替换为)。

事件流路径代表GUI上可以执行的事件序列,对事件流路径定义如下:

定义2 当且仅当存在一条(可能为空的)节点序列(nj,nj+1,…,nj+k),{(nx,nj),(nj+k,ny)}⊆E, {(nj+i,nj+i+1),0≤i≤(k-1)}⊆E,则从节点nx到节点ny存在一条事件流路径。

举例:＜保存;编辑;另存为;取消＞和＜文件名为(1);取消;编辑;保存;编辑;替换＞。

EFG的节点由不同的语义和语法用于构建GUI,对GUI事件类型的定义如下:

定义3 可达事件(reachability event),代表用于打开窗口或菜单的事件。打开菜单事件用菱形表示,如图1(b)中的{编辑};打开窗口事件用双圈节点表示,如{另存为,替换}。其中,打开窗口事件可分为模态窗口的限制性聚焦事件和非模态窗口的非限制性聚焦事件。

定义4 模态窗口(modal window),代表限制性聚焦事件。当打开窗口时,用户的交互限制在本窗口内,必须先操作窗口内的事件,直至关闭当前窗口方可操作其他事件。模态窗口事件用双圈表示,如图1(b)中{另存为}打开的窗口。

定义5 非模态窗口(modeless window),代表非限制性聚焦事件。当打开窗口时,用户的交互没有限制在本窗口内,仍可以操作其他事件。非模态窗口事件用双圈,内圈为虚线表示,如图1(b)中{替换}打开的窗口。

定义6 终止事件(termination event),代表操作GUI结构的事件,一般指用于关闭窗口的事件。终止事件用矩形表示,如图1(b)中{确定,取消,关闭}事件。

定义7 系统交互事件(system-interaction event),代表不会操作GUI结构的事件,一般指与底层代码进行交互,除可达事件和终止事件之外的事件。系统交互事件用圆圈表示,如图1(b)中{保存,文件名为,查找内容,替换为}事件。

2.1.2 事件交互图

在一个典型的GUI中,20%～25%的事件被用来操作GUI结构,包括打开和关闭窗口或菜单,大部分事件与底层代码进行交互。打开和关闭窗口或菜单的事件代码较为直观,不与其他事件代码进行交互,因此,发现故障的几率较低。事件交互图(Event Interaction Graph,EIG)模型通过移除这些不常用的事件从而简化EFG模型,一般移除的事件类型为打开和关闭菜单事件、打开和关闭非模态窗口事件、打开模态窗口事件。

图2为实例对应的事件交互图(EIG),双向箭头表示事件之间可以互相“跟踪”,虚线代表仅单向“跟踪”。EIG模型中不包含可达事件和非模态窗口的终止事件。举例,EIG中不包含“编辑”、“另存为”、“替换”、“关闭”4个节点,简化后的模型更简单更具有效性。所以EIG模型是由终止事件和系统交互事件组成,其中终止事件仅为关闭模态窗口事件。

图2 图形用户界面实例对应的事件交互图

EFG可以通过算法自动转换成 EIG。Atif Memon提出的EFG到EIG的算法利用了图重构规则:(1)移除代表打开菜单事件“编辑”;(2)用(ex,ey)取代每一条与节点“编辑”相关的边(ex,编辑)和(编辑,ey);(3)对于所有ey,删除所有边(编辑,ey)并储存映射“ey→(编辑,ey)”用于测试,最后通过图遍历算法枚举访问过的节点,生成测试集。丰凯提出的EFG到EIG的算法[11]步骤如下:(1)移除EFG中所有的边(ex,ey);(2)删除所有可以打开窗口或菜单的节点ex;(3)对剩余的节点任意选择其中2个进行有序排列,重新生成边(ex,ey);(4)对于所有生成的边,判断假如ex的事件类型是模态窗口中的系统交互事件,ey不是模态窗口中的系统交互事件或终止事件,则去掉这条边。

2.1.3 事件语义交互图

在GUI上使用自动化测试集回放工具可以执行冒烟测试[13]。在执行测试集时,收集GUI部件运行时的状态,用于自动识别成对事件间的“事件语义交互”关系(Event Semantic Interaction,ESI)。这种关系捕捉了一个GUI事件如何改变软件的状态,从而导致影响其他事件的执行。ESI关系被用于自动构建新的GUI模型,称之为事件语义交互图(Event Semantic Interaction Graph,ESIG)。ESIG中的节点代表事件,从节点nx到节点ny的有向边表示nx代表的事件与ny代表的事件之间有ESI关系。ESIG被用于自动生成测试集,这些测试集有一个重要特性——每个事件与后续的事件是ESI关系。

3 基于EFG模型的EIG转换算法

本文提出了一种新的EFG到EIG的算法,文献[10]算法转换中对事件类型的分类不够明确,算法较为复杂。文献[11]算法适用于只有单个模态窗口的GUI应用程序,因为当ex事件类型为模态窗口中的系统交互事件时,没有考虑到多个模态窗口之间也需要移除ey是模态窗口中的系统交互事件或终止事件所对应的边;另外,对于非模态窗口中的终止事件也应该删去,这些事件在检测系统故障时发现故障的概率较低。所以,本文算法由终止事件和系统交互事件组成,其中终止事件仅为关闭模态窗口事件,此算法更高效地将EFG转换成EIG。

本文算法主要从 EIG的定义出发,从节点 nx(代表ex)到节点ny(代表ey)的一条边意味着ex与ey交互,根据事件间的交互关系创建模型。从EFG转换成EIG的算法如下:

本文算法的描述如下:

第1～3行:初始化阶段,由之前生成的EFG模型作为输入值,N作为一组节点。N为EIG节点集合,初始值为N;E为EIG边的集合,初始值为空集。

第4～6行:遍历EFG中的所有节点,从节点集合中去掉可达事件和非模态窗口中的终止事件(打开(关闭)窗口或菜单的事件)。

第7～12行:遍历EIG中的所有节点,假如nx的事件类型不是模态窗口中的系统交互事件,则将所有新的边(nx,ny)添加至EIG的边集合。

第8～11行:假如nx的事件类型是模态窗口中的系统交互事件,则判断ny事件类型是否是同一个模态窗口中的事件,即判断ny事件类型是否是同一模态窗口中的系统交互事件或终止事件,如果判断为同一个模态窗口的事件,则将所有新的边(nx,ny)添加至EIG的边集合;如果判断不符合添加要求,则会退到for循环,进行下一个ny判断。由于模态窗口的聚焦性定义,模态窗口中的系统交互事件只能和同一个窗口的事件交互,不能和其他窗口及其他菜单内的事件进行交互。

最后(N,E)为EIG的节点集合和边集合,从算法描述中可以发现EIG的事件比EFG事件少,但是模型的路径不一定会减少,主要原因在于系统交互事件之间的交互没有减少。

算法步骤如下:

步骤1 遍历EFG中所有节点,去掉可达事件和非模态窗口中的终止事件;

步骤2 判断nx的事件类型,若不是模态窗口中的系统交互事件,则生成(nx,ny);

步骤3 若nx是模态窗口中的系统交互事件,则判断ny的事件类型;

步骤4 若ny是同一个模态窗口中的事件,则生成(nx,ny);否则,继续循环;

步骤5 对步骤1中去掉的可达事件和非模态窗口中的终止事件进行映射,(可达事件,ny)、(终止事件,ny)用于测试阶段执行。

本文的优越性体现在:(1)文献[10]算法较为复杂,本文通过对GUI事件更详细的划分进行算法改进,过程更简单,不容易出错;(2)对于文献[11]算法而言,本文算法可以适用于多个模态窗口的情况;不用移除EFG和算法中生成的不正确的边;去掉非模态窗口中的终止事件,不影响测试集的生成但转换的EIG图更简单。所以,本文算法比之前提出的算法更高效。

4 实验结果与分析

实验选用了《一体化信用卡业务系统软件》系统,这款系统由上海师范大学与上海华腾软件系统有限公司共同合作设计,采用模块化设计思想,每项任务用一个功能模块支持,功能模块间相互独立。实验选用了其中最重要的客户管理模块,简化功能模块,提取重要功能点作为实验部分。

4.1 实验准备

图3为一个简单的图形用户界面,“客户管理模块”事件共有4个子事件,分别为“客余额查询”、“客户资料更新”、“客户添加账户”、“下一步”。 “客户余额查询”为非模态窗口,共有3个子事件,分别为“输入密码”、“查看”、“更新”。 “客户资料更新”为模态窗口,共有4个子事件,分别为“身份证号”、“出生日期”、“更新”、“取消”。 “客户添加账户”为模态窗口,共有3个子事件,分别为“添加账户”、“添加”、“关闭”。

图3 客户管理模块简单举例

4.2 事件流图实例

图4为客户管理模块对应的事件流图(EFG),表1为事件流图的实验数据,可以看出,实例中的可达事件共有4个,系统交互事件共有5个,终止事件共有6个。在事件交互图中,将去掉这4个可达事件和2个终止事件(“查看”、“返回”),分析系统交互事件和终止事件之间的关系。

图4 客户管理模块的事件流图

表1 事件流图的实验数据

4.3 事件交互图实例

图5为客户管理模块的事件交互图(EIG),可以明显看出,事件交互图中的路径数远高于事件流图中的路径数,因为实例中的系统交互较多,所以生成的事件交互图较为复杂。图中共9个事件,“输入密码”为非模态窗口事件“客户余额查询”的系统交互事件,(其中,“查看”、“返回”为非模态窗口事件“客户余额查询”的系统终止事件,已被删除);“出生日期”、“身份证号”为模态窗口事件“客户资料更新”的系统交互事件,“更新”、“取消”为模态窗口事件“客户资料更新”的系统终止事件;“添加账户”为模态窗口事件“客户添加账户”的系统交互事件,“关闭”、“添加”为模态窗口事件“客户添加账户”的系统终止事件。

图5 客户管理模块的事件交互图

表2为事件交互图的实验数据,由于模态窗口事件中的系统交互事件只和当前窗口中的事件交互,因此可以分析得出:模态窗口事件“客户资料更新”的系统交互数为2个,模态窗口事件“客户添加账户”的系统交互数为1个,总共3个。对于表2中第1～2行,事件的出度为9,代表所有的事件都可以作为它们下一个事件,入度为6是因为3个模态窗口中的系统交互事件执行后,不能直接执行这些事件。对于第3～4行,它们是模态窗口中的系统交互事件,所以它们下一个事件仅为该窗口中的所有事件,入度为8是因为不能在“添加账户”事件的下一个事件被执行。依此类推,所有的出度之和等于所有的入度之和。

表2 事件交互图实验数据

为了更好地说明算法的适用性,根据表1和表2的数据,分析得出表3事件交互图中没有连接的路径。表3数据与事件交互图的定义吻合,说明算法可以运用于图形用户界面。组合才会引起测试集终止。若将这些事件交互类型与EFG相结合,对EFG中的事件进行分类,是否属于会引起测试集终止的事件交互类型,判断属于哪一种类型。由于生成的测试集是根据EIG图的遍历及转换算法中的映射相结合,因此获得的事件及事件间的关系确保了足够的覆盖率。对于生成的测试集进行分析,判断该测试集中是否包含会引起测试集终止的事件交互类型,从而提高测试集的有效性和实用性,减少不可行测试集的输出。

表3 事件交互图中没有连接的路径

表4 事件交互类型分类情况

4.4 数据分析

GUI测试中常用的模型可以指导测试生成,并确保足够的覆盖率。但是通过多次实验证明,EFG模型的提取并不是精确提取,部分提取的信息可能只是为了特殊的执行路径,所以并不完整,生成的测试集因此会存在不可行的问题;另外,一个意外的窗口或者部件、按钮被禁用,事件不能触发等情况都会导致生成的测试集变得不可行,因为在基于模型的测试方法中,自动化测试缺少人类的认知能力,无法注意到一些会导致测试集失败的问题。这类问题是由于违反了事件交互序列的临时约束[13]。在GUI测试生成中,缺少这些约束意味着部分事件的交互会丢失,降低了故障检测率。为解决上述问题,必须提高从GUI中提取模型的精确度,改进所需的信息,以及测试有效性,优化测试集以获得更多可执行的测试序列。

本文研究并定义了6种可能会引起测试集终止的事件交互类型情况:禁用,连续,强依赖,弱依赖,排除,混合。表4为6种交互类型的情况说明及举例。

对常用的Office软件进行分析,禁用与强依赖2种事件的交互类型较多,因为它们仅需1个事件或2个事件便可引起测试集终止;弱依赖与排除2种事件的交互类型较少,因为它们通常是根据多个事件

5 结束语

本文通过事件流图和事件分类,提出了一种新的EFG转变成EIG的算法,经过实验证明,该方法可以适用于图形用户界面,并且获得的数据更准确、更高效。但EFG模型的提取并不是精确提取,生成的测试集会存在不可行的问题,本文通过实验部分的数据分析,总结了6种可能会引起测试集终止的事件交互类型情况分类,作为今后研究的方向,通过优化测试集从而提高测试的有效性。

[1] Arlt S,Podelski A,Bertolini C,et al.Lightweight Static Analysis for GUI Testing[C]//Proc.of the 23rd IEEE International Symposium on Software Reliability Engineering.Dallas,USA:[s.n.],2012:301-310.

[2] Huang Si,Memon A.Repairing GUI Test Suites Using a Genetic Algorithm[C]//Proc.of the 3rd International Conference on Software Testing,Verification and Validation.Paris,France:[s.n.],2010:245-254.

[3] Yuan Xun,Myra B C,Memon A M.GUI Interaction Testing:Incorporating Event Context[J].IEEE Transaction on Software Engineering,2011,27(4):559-574.

[4] Xie Qing,Memon A M.Using a Pilot Study to Derive a GUIModelfor Automated Testing[J].ACM Transactions on Software Engineering And Methodology, 2008,18(2):1-35.

[5] Memon A M,Soffa M L,PollackM E.Coverage Criteria for GUI Testing[C]//Proc.of the 8th European Software Engineering Conference Held Jointly with the 9th ACM SIGSOFT InternationalSymposium on Foundations of Software Engineering.New York,USA: ACM Press,2001:256-267.

[6] Belli F.Finite-state Testing and Analysis of Graphical User Interfaces[C]//Proc.of the 12th International Symposium on Software Reliability Engineering. [S.l.]:IEEE Press,2001:34-43.

[7] Belli F,Beyazit M,Memon A.Testing is an Eventcentric Activity[C]//Proc.of the 6th International Conference on Software Security and Reliability Companion.Gaithersburg,USA:IEEE Press,2012: 198-206.

[8] Memon A.GUIRipping:Reverse Engineering of Graphical User Interfaces for Testing[C]//Proc.of the 10th Working Conference on ReverseEngineering. [S.l.]:IEEE Press,2003:260-269.

[9] Memon A,Banerjee I,Nagarajan A.Reverse Engineering of Graphical User Interfaces Using Static Analyses [C]//Proc.of the 14th Working Conference on Reverse Engineering.Vancouver,Canada:[s.n.],2007:189-198.

[10] Memon A M,Qing Xie.Studying the Fault-detection Effectiveness of GUI Test Cases for Rapidly Evolving Software[J]. IEEE Transactions on Software Engineering,2005,31(10):884-896.

[11] 丰 凯,高建华.基于模型的图形用户界面事件交互图生成方法[J].计算机科学,2013,40(6A):184-187.

[12] Yuan Xun,Memon A M.Using GUI Run-time State as Feedback to Generate Test Cases[C]//Proc.of the 29th InternationalConference on Software Engineering. Minneapolis,USA:IEEE Press,2007:396-405.

[13] Cohen M B,Huang Si,Memon A M.AutoInSpec:Using Missing Test Coverage to Improve Specifications in GUIs[C]//Proc.of the 23rd International Symposium on Software Reliability Engineering.Dallas,USA:IEEE Press,2012:251-260.

编辑 任吉慧

Algorithm and Research Based on Event Interaction Graph

GAO Xiu-hui,GAO Jian-hua
(Department of Computer Science and Technology,Shanghai Normal University,Shanghai 200234,China)

The quality of Graphical User Interface(GUI)directly affects the reliability and usability of the entire software system.When testing the graphical user interface,it generally adopts the method of extracting model,and the frequently models based on the graphical user interface are Event Flow Graph(EFG)and Event Interaction Graph(EIG). However,the algorithm of EFG into EIG is complex,this paper proposes an algorithm.In this paper,the GUI events with a specific division and the use of the special nature of the modal window event optimize the original algorithm.It indicates the new algorithm can be used for GUI and the obtained data is more accurate and more efficient with the real cases than Memon in GUI.

Graphical User Interface(GUI);event-interaction classification;Event Flow Graph(EFG);Event Interaction Graph(EIG);test case

1000-3428(2014)10-0086-06

A

TP311.5

10.3969/j.issn.1000-3428.2014.10.017

国家自然科学基金资助项目(61073163);上海市引进技术的吸收与创新计划基金资助项目(2010CH-014)。

高秀慧(1989-),女,硕士研究生,主研方向:软件可靠性设计,软件测试技术;高建华,教授、博士。

2013-10-21

2013-12-20E-mail:veronica_gxh@hotmail.com

中文引用格式:高秀慧,高建华.基于事件交互图的算法与研究[J].计算机工程,2014,40(10):86-91,97.

英文引用格式:Gao Xiuhui,Gao Jianhua.Algorithm and Research Based on Event Interaction Graph[J].Computer Engineering,2014,40(10):86-91,97.