基于FSM的Web应用测试用例生成研究

陈亚龙，江国华

(南京航空航天大学计算机科学与技术学院，江苏南京 210016)

在Web工程中，基于Web系统的测试、确认和验收是一项重要的工作。首先，Internet是一个无集中控制、并且在不断发展的系统，它由大量的局部自治系统组成，并具有多方面的异构性以及系统状态的不确定性。其次，由于Web应用的多层体系架构，客户端、硬件和服务器之间相互联系，导致故障源难以排查。另外，由于浏览器可能引起的兼容问题，服务器、数据库负载能力对系统性能的影响，并发用户对系统交互行为的干扰等，使得Web系统的测试变得异常困难。因此，研究Web应用测试技术具有现实意义。Web测试主要涉及:功能测试、性能测试、浏览器兼容性测试、可用性测试、回归测试等。

目前，国内外对Web应用的测试研究已经取得一些研究成果。在模型构造方面，有D.C.Kung等人提出的面向对象的Web应用测试模型;Filippo Ricca等人提出了采用 UML模型方法描述 Web应用;A.A.Andraws等人在前人的基础上提出了分层聚集FSM。在工具方面，有记录/回放工具，自动化测试框架等工具，但这些工具都具有明显的缺点［1－2］。

基于FSM对Web应用建模，论文提出一种改进的最小测试成本迁移覆盖准则，并在此覆盖准则之上，提出并实现了一种有效的测试用例生成算法——模拟退火遗传算法。

1 软件测试及Web测试技术

1.1 Web应用程序的结构

Web应用具有分布、并发、异构以及平台无关性等特点。目前Web应用通常采用3层体系结构，如图1所示，客户端浏览器负责用户界面解析、显示以及接受用户的输入信息。Web服务器进行通信和交互。Web服务器是主要的事务计算和处理单元，属于商业逻辑层，根据不同用户的请求做出对应的处理。数据库服务器是数据服务层，以一定的逻辑规则存放着与应用程序相关的数据，并进行数据增、删、改、查、维护等工作。

图1 Web应用结构

1.2 主流的4种提取用例方法

按照Web测试用例生成方法所采用的技术，把Web测试用例的生成方法归结为4类:(1)记录/回放法，基于Capture/Replay技术产生测试用例。(2)源代码分析法，分析服务器端的源代码，产生测试用例。(3)User session法，基于用户会话产生测试用例。(4)Html分析法，分析客户端Html代码，建立模型，从模型产生测试用例。其中，记录/回放法需要耗费大量的人力来产生测试用例;源代码分析法通用性不强，需要处理不同的Web编程语言;User session法需要有访问数据积累，在应用投入使用之前，无法用该方法测试，并且很难调试没有使用过的功能;Html分析法与平台实现技术无关，并且能方便地在客户端完成测试，所以采用Html分析法提取模型。

2 基于FSM的Web应用模型的研究

2.1 FSM 模型

有限自动机(FSM)简称自动机，它表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。它提供一种方便的建模方法，并且它可以很好地避免与实现相关联的问题。利用自动机的思想，结合Web应用的特点，建立出有效的Web应用模型。它主要包括:一个有限状态集合，用于描述系统中的不同状态;一个输入集合，用于表征系统所接受的不同输入信息;一个状态转移规则集合，用于表述系统在接受不同输入的情况下，从一个状态转移到另一个状态的规则。

2.2 具有Web特性的FSM

FSM定义为

其中，Q表示状态集合:Web应用所有的状态;∈表示输入符号集合:从一个页面状态转移到下一个页面状态需要接受的输入的集合;δ表示转移函数:每一条迁移就是一个转移，变迁的类型分为两种:(1)链接类型。(2)表单提交类型;q表示初始状态集合:Web应用的入口页面，等入度为0的结点;F表示接受状态集合:无法继续扩展的页面以及核心页面。

2.3 提出改进的Html法

2.3.1 Html解析结合源代码分析

(1)Html分析。利用Html分析法，从Html提取出链接、表单等元素信息。

(2)源代码分析。如果在Web应用里存在重定向页面，而重定向页面对于用户并不可知，所以为了建模的准确性，除了分析Html，还需要分析源代码，跳过重定向页面。保证自动机状态变迁与用户实际操作状态变迁相一致。

2.3.2 自动填充表单

如果一个迁移的起始状态需要提交表单至目标状态，那么就需要对起始状态中表单进行自动填充。对于表单里的每一种类型元素，系统自动生成输入值，模拟提交这些数据，如果能正常提交到目标状态，保存当前的提交数据。否则，根据Web应用响应重新生成数据。在尝试一定次数仍无法达到满意输入值后，则该表单需要人工填写数据。

2.3.3 解析

Html法解析可以分为两种:广度优先算法，深度优先算法。两者在效率，以及结果上均没有显著影响，文中采用广度优先算法。2.3.3.1 基本数据结构

(1)link结点。包含链接的名称以及跳转页面。(2)form元素。form表单中的元素信息，包括名称，类型，值。(3)form结点。包含form的跳转页面，传输类型，以及form元素信息。(4)urls链表。解析的所有url地址，并且url地址都标识是否解析过。(5)邻接表。邻接表的头结点为FSM的状态标识，表结点为link结点和form结点。

2.3.3.2 Html法解析流程

Html法解析流程图，如图2所示。

图2 Html分析法解析流程

2.3.3.3 邻接表的建立

(1)将当前解析页面的页面标识作为邻接表中的头结点。

(2)将1中解析出的link，form装箱成结构体，作为表结点链接在头结点之后。

3 Web应用的覆盖准则

3.1 常见的3种覆盖准则

(1)状态覆盖。测试用例集TS使FSM中的每一个状态至少被访问一次。FSM中的每个状态是可达的，因而每一个状态被访问一次很容易。(2)迁移覆盖。测试用例集TS使FSM中的每一个迁移至少被激活一次。(3)迁移对覆盖。测试用例集TS使FSM中的每一对相邻迁移t1和t2的交互至少测试一次。迁移对覆盖检查的是状态之间的接口。

3.2 最小测试成本迁移覆盖准则

刘攀等人［3］在提出的优化迁移覆盖算法基础之上继续改进提出了最小测试成本迁移覆盖准则。符号说明:ran表示值域操作符号，#表示集合长度操作符号。

3.2.1 最小测试成本迁移覆盖

定义 给定 M的一个迁移覆盖 Aid，若∀TSi，TSj∈Aid，都有 ran TSi∩ran TSj= ∅，且∀TS∈Aid都满足#(ran TS)=#TS，即集合ran TS的大小等于序列TS的长度，则称Aid为M的独立迁移覆盖。

定义 对于M的一个迁移覆盖Ap，满足下面两个条件:

1)Ap是M的一个独立迁移覆盖。2)对于M的任意一个独立迁移覆盖Aid，都有#Ap≤#Aid。

3.2.2 优化迁移覆盖算法

1)将M中所有自迁移序列加入到输出集合SS中，并从迁移集合T中删除所有自迁移。

2)从迁移集合T中取一个单迁移t，令序列TS=＜t＞及T=T ，若使得TS～＜ti＞为有效连接操作，则TS=TS～＜ti＞及T=T i，直到T中不存在这样的ti;

3)若TS可与SS中的迁移序列进行有效连接操作，则对他们进行有效连接操作，否则，将单迁移序列TS加入到SS中;

4)若T不空，则转到步骤2)。

3.2.3 最小测试成本迁移覆盖

定义 在M中，对于任意两条迁移序列TS1和TS2，若TS1和TS2中的迁移包含了某些共同状态，则称迁移序列TS1和TS2为相交序列，这些共同状态为TS1和TS2的相交点;否则，称TS1和TS2为不相交序列。

定义 在M中，Aid为M的独立迁移序列覆盖，若∀TS∈Aid，TS=〈t1，…，tk〉，t1=(s1，i1，sl)和 tk=(si，ik，sj)，满足条件 s1=sj，则称迁移序列TS为回路。

最小测试成本迁移覆盖算法合并准则:

准则1 若 M 中迁移序列 TS1，TS2∈ Aid，TS1和TS2相交，且满足TS=TS1～TS2或TS=TS2～TS1为M的迁移序列，则用迁移序列 TS替代迁移序列 TS1和TS2。

准则2 假设M中迁移序列TS1，TS2∈Aid，TS1=〈t1，t2，…，ti－1，ti，…，tk〉与 TS2=〈tm，tm+1，…，tj－1，tj，…，tn〉的相交点为 si，其中，迁移 ti－1=(si－1，ii－1，si)和tj=(si，ij，sj)，且 TS2是回路，则迁移序列 TS1和 TS2合并成迁移序列 TS=〈t1，t2，…，ti－1，tj，…，tn，tm，tm+1，…，tj－1，ti，…，tk〉。

3.2.4 最小测试成本迁移覆盖有效性

最终生成的测试序列可能不是由初始状态到达，因此，其中这些测试序列是无效的测试片段。寻找从初始状态至到达该片段起始点的最短路径序列，与测试序列组合得到新的完整测试用例序列。由于新添的序列影响了覆盖准则评价，所以最小测试成本迁移覆盖算法的效果无法达到覆盖准则的要求。

3.3 Web应用最小测试成本迁移覆盖准则

3.3.1 基本概念

定义 Web应用中从一个页面状态跳转到另外一个页面状态，完成跳转需要的操作代价。点击链接，填充表单单个元素权值设置为1。

定义 迁移 t=(si，x，c，sj)。其中，f(si，x)=sj，x∈I，c∈N，si为迁移 t的前状态，sj为迁移 t的后状态，x是状态si到状态sj的输入，c是输入x的操作成本。

3.3.2 Web应用最小测试成本迁移覆盖准则

$集合的成本符号，$Ap表示集合Ap的迁移成本。对于M的一个迁移覆盖Ap，满足:1)Ap是M的一个独立迁移覆盖。2)对于M的任意一个独立迁移覆盖 Aid，都有$Ap≤$Aid。

4 基于模拟退火遗传算法的用例生成

4.1 FSM的遍历

FSM可以使用状态图表示，也可以用状态转移表表示。基于此，用例的生成就是依据提出的Web应用最小测试成本迁移覆盖准则，对邻接表表现形式的图的遍历。

4.2 FSM模型状态约简

当一个状态的前续状态和后继状态都有且仅有一个，那么这个状态就称为可约简状态。可约简状态不会对路径造成影响，为缩小模型规模，在分析时考虑。

4.3 传统方法及其缺点

对每一个完整的测试用例，都是从初始状态到达接受状态，传统的深度优先或广度优先遍历方法并不能满足该要求;最小测试成本迁移覆盖算法在非启发式搜索算法中效率较高，但它的结果也难以接近最优解。所以提出一个新的基于遗传算法和模拟退火算法的启发式搜索算法用于解决FSM的遍历问题。

定义 对于一个问题，如果它的解是一条序列，则称问题的解为“一维解”。如果它的解是一组序列，并且路径相互独立，则称问题的解为“二维解”。

维度越高，生成越复杂。每一个合法的解需要满足覆盖准则要求，而二维解比一维解更难满足。解决普通NP问题时，模拟退火算法里是利用简单的置换，互换等手段产生新解，然而，由于维度的提高，这样的方式无法用在当前问题。所以问题需要一种新的新解产生方式。

4.4 人工智能启发式搜索

4.4.1 遗传算法

遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律演化而来的随机化搜索方法。由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域［4－6］。

4.4.2 模拟退火算法

模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Monte－Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能，目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

4.4.3 模拟退火遗传算法

模拟退火进化是由参数问题t控制的，然后通过一定的操作产生新的解，根据当前解的优劣和温度参数t确定是否接受当前的新解。遗传算法主要由选择、交叉和变异等操作组成，通过种群进行进化。

模拟退火是采用单个个体进行进化，遗传算法是采用种群进行进化。模拟退火一般新解优于当前解才接受新解，并且还需要通过温度参数t进行选择，并通过变异操作产生新个体。而遗传算法新解是通过选择操作进行选择个体，并通过交叉和变异产生新个体。两者都是采用进化控制优化的过程。

将两者结合具有以下优点:首先，它们基本思想都是采用进化控制优化的过程，模拟退火采用单个个体进行优化，在当前问题下，很适合。其次，遗传算法在产生新个体时提供较多的手段，将交叉和变异结合到优化过程中，可以很好地解决当前问题。

4.4.4 模拟退火遗传算法实现

4.4.4.1 相关定义

定义1 入度、出度都≥2的结点为交叉点。

定义2 解状态中一直存在，不可修改，删除，唯一的迁移序列，为元序列。

找出初始解里的交叉点，把每个用例都在交叉点处拆分开，得到的迁移序列称之为元序列。

4.4.4.2 模型思想

(1)初始化:初始温度T，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L。(2)对k=1，…，L做第(3)至第6步。(3)产生新解S'。(4)计算增量Δt'=C(S')－C(S)，其中C(S)为评价函数。(5)若Δt'＜0则接受S'作为新的当前解，否则以概率 exp(－Δt'/T)接受S'作为新的当前解。(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。(7)T逐渐减少，且T－＞0，然后转第(2)步。

4.4.4.3 新解构造

解状态:包括当前解、前段解集合、后段解集合。不同的解状态共享元序列。

(1)拆分当前解。从FSM的状态集合中提取出交叉点集合，从交叉点集合中随机选取一个，拆分当前解，得到序列集合，分为前段解集合，后段解集合。

(2)序列组合。从后段解集合中随机选取一条序列，以概率p与前段解集合的序列结合，以1－p的概率与元序列集合结合。其中p值取0.7。若此时前段解集合为空，p值取0。最终可以得到一条完整的序列。

(3)新解产生。序列组合得到的序列就是新解中的序列。在后段解集合全部组合完成:

1)若前段解集合也已经为空，则新解为组合后的序列集合，新解构造结束。2)若前段解集合不为空，且其元素不为元序列，则将剩余的前段解集合中每个元素与元序列集合结合，结合后的序列做为新解中的一条序列。

4.4.4.4 评价函数

C(S)为评价函数，C(S)=SN(S)+LN(S)+FM(S)。其中，LN(S)为统计S里的链接变迁个数;FM(S)为统计S里的表单提交变迁个数*权值;SN(S)为统计S里用例的条数*权值。

5 基于FSM的Web应用功能测试实例

现在有一个Web应用为招聘信息发布系统，并且已经提取出模型。

5.1 Web应用FSM模型

模型如图3所示，表2对图中每个状态进行了说明，表3对每个变迁进行说明。

图3 应用的FSM模型

表1 状态说明表

FSM模型的变迁说明，如表2所示。

表2 变迁说明表

5.2 用例生成

5.2.1 最小测试成本迁移覆盖算法生成用例

按照优化迁移覆盖算法和最小测试成本迁移覆盖算法，得到用例如下:

5.2.2 模拟退火遗传算法生成用例

利用模拟退火遗传算法可以优化得出成本更低的用例:

5.2.3 总结

虽然该系统结构比较简单，但通过模拟退火遗传算法优化，其测试用例成本已经明显降低。因而，在覆盖准则下，模拟退火遗传算法优化图路径是有效的。

6 结束语

本文完成了对Web应用建立FSM模型，实现了一个高效鲁棒的提取算法。提出一个新的最小成本迁移覆盖准则，在此覆盖准则约束下，Web应用可以生成高质量的用例。提出一种混合的启发式搜索算法，解决了在覆盖准则约束下，从FSM模型到测试用例的高质量转换。Web领域发展日新月异，未来工作重点主要集中在:(1)需要对Web应用中引入的特性等分析，对FSM模型需要继续深入研究。(2)模拟退火遗传算法中产生新解过程耗费较多计算资源，还需要继续优化、探索。

［1］彭树深，顾庆，陈道蓄.Web应用测试用例生成研究［J］.计算机科学，2010，37(6):159 －163.

［2］ANNELIESE A，ANDREWS J，OFFUTT R T.Testing Web applications by modeling with fsms［J］.Software Systems and Modeling，2005，4(3):326 －345.

［3］刘攀，缪淮扣，曾红卫，等.确定性有限状态机的最小测试成本迁移覆盖准则［J］.软件学报，2011，22(7):1457 －1474.

［4］MIAO H K，LIU P，MEI J，et al.A new approach to automated redundancy reduction for test sequences［C］.IEEE Computer Society Press，shanghai:PRDC，2009:93 －98.

［5］ZHU B，MIAO H，ZENG H，et al.Generating test case from functional requirement of Web applications［C］.Nanchang:2009 Second International Symposium on Electronic Commerce and Security，ISECS，2009:465 －468.

［6］冯雅丽.基于有限状态机理论的Web功能自动化测试技术研究［D］.上海:华东师范大学，2009.