«上一篇
文章快速检索     高级检索
下一篇»
  哈尔滨工程大学学报  2020, Vol. 41 Issue (6): 884-891  DOI: 10.11990/jheu.201901013
0

引用本文  

赵瑞莲, 郭小红, 王微微, 等. 面向Web服务器端敏感路径的客户端扩展有限状态机测试生成[J]. 哈尔滨工程大学学报, 2020, 41(6): 884-891. DOI: 10.11990/jheu.201901013.
ZHAO Ruilian, GUO Xiaohong, WANG Weiwei, et al. Client-side extended finite state machine test case generation based on the server-side sensitive path coverage for web applications[J]. Journal of Harbin Engineering University, 2020, 41(6): 884-891. DOI: 10.11990/jheu.201901013.

基金项目

国家自然科学基金项目(61672085,61472025,61702029)

通信作者

尚颖, E-mail:shangy@mail.buct.edu.cn

作者简介

赵瑞莲, 女, 教授, 博士生导师; 尚颖, 女, 副教授

文章历史

收稿日期:2019-01-05
网络出版日期:2020-04-14
面向Web服务器端敏感路径的客户端扩展有限状态机测试生成
赵瑞莲 , 郭小红 , 王微微 , 尚颖     
北京化工大学 信息科学与技术学院, 北京 100029
摘要:为对Web应用进行有效的测试,本文提出了一种面向Web应用服务器端敏感路径覆盖的客户端扩展有限状态机测试用例生成方法。针对Web应用客户端扩展有限状态机模型,以Web应用服务器端的敏感路径覆盖为目标,利用Memetic演化算法实现客户端扩展有限状态机模型的测试用例自动生成,对Web应用进行测试。同时,为解决由模型生成的抽象测试用例不可直接执行的问题,提出了一种基于Selenium的测试脚本自动构建方法,通过分析扩展有限状态机模型迁移的特征,利用谱聚类算法实现迁移聚类,依据映射规则将聚类之后的迁移映射为测试脚本,形成迁移脚本库,将抽象测试用例转换为可执行的测试用例。实验结果表明:基于Selenium的测试脚本自动构建能有效地将抽象测试用例转化为可执行的测试脚本;面向Web服务器端敏感路径的客户端扩展有限状态机测试用例生成方法能有效地实现Web服务器端敏感路径的覆盖,对服务器端的敏感路径进行测试。
关键词软件测试    Web敏感路径    路径覆盖    扩展有限状态机模型    Memetic算法    聚类    测试用例生成    测试脚本生成    
Client-side extended finite state machine test case generation based on the server-side sensitive path coverage for web applications
ZHAO Ruilian , GUO Xiaohong , WANG Weiwei , SHANG Ying     
School of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China
Abstract: To enable an effective security test for web applications, we propose a client-side extended finite state machine (EFSM) test case generation approach based on the server-side sensitive path coverage for web applications. According to the EFSM model of clients, this approach takes the server-side sensitive path coverage as a goal and uses the memetic evolutionary algorithm to realize the automatic generation of abstract test cases for web application. Moreover, to solve the unexecutable problem of abstract test cases generated by the model, an automatic construction method of test scripts based on Selenium is proposed. This method proposes an automatic test-script construction method based on Selenium. It employs the spectral clustering algorithm to realize group transitions by analyzing the feature of transitions on the EFSM model. Then, the transition after grouping is mapped onto a test script, forming a script library. As a result, abstract test cases can be converted into actual executable test cases. Experimental results show that the selenium-based automated test-script construction method can solve unexecutable abstract test cases, and the test case generation approach can effectively achieve the server-side sensitive path coverage.
Keywords: software testing    web sensitive path    path coverage    extended finite state machine (EFSM) model    memetic algorithm    clustering    test case generation    test script generation    

随着互联网普及与快速发展,Web应用已成为人们生活中不可或缺的一部分。但Web应用极易受到攻击。因此,对Web应用进行有效的安全测试极为重要。

目前,关于Web应用安全测试的研究主要针对客户端模型或服务器端代码,多以模型自身的状态、迁移覆盖为目标,探讨其测试用例自动生成[1-2]。缪淮扣等[3]设计了一个基于模型的Web应用程序测试系统,以FSM作为被测Web应用程序的形式化测试模型;Schur等[4]从商业Web应用程序中挖掘用户行为模型,并通过分析用户行为模式建立模型,然后利用模型进行回归测试用例生成;赵瑞莲等[5]提出了基于用户轨迹的Web客户端扩展有限状态机建模方法,通过对Web应用客户端源代码进行插装,在用户动态执行Web应用过程中获取用户的行为轨迹,利用用户行为轨迹建立Web应用的扩展有限状态机模型。Alshahwan等[6]将搜索算法应用于Web应用程序测试中, 随后更多的研究者尝试采用包括遗传算法、禁忌搜索算法、模拟退火算法等在内的启发式搜索算法来解决扩展有限状态机测试数据生成问题[7-9]。Jan等[10]针对XML注入漏洞,利用遗传算法实现测试用例的自动生成,该方法受限于已有的恶意输入。研究者针对PHP Web应用程序的XSS漏洞,给出了以遗传算法为主的测试用例生成方法[11-13]。通常一种算法只能在某一方面表现出较好的性能。混合搜索Memetic算法[14-15]则能通过将多种搜索算法有机结合起来,实现算法性能的进一步提高。

为此,本文将Web应用客户端扩展有限状态机模型的测试用例生成与服务器端的敏感路径覆盖结合起来,以服务器端安全脆弱点敏感路径覆盖为目标,利用Memetic演化算法将全局搜索的高效性和局部搜索的精准性相结合,实现客户端扩展有限状态机模型的测试用例自动生成,为Web应用软件安全测试提供一种新的、有效的解决途径。

基于扩展有限状态机模型生成的抽象测试用例不能在Web应用中直接执行,需转为驱动Web应用执行的测试脚本。若对每一个抽象测试用例编写测试脚本或借助工具录制测试脚本,将增加测试成本,降低测试效率。因此,测试脚本的自动生成是本文研究的另一个关键问题。Selenium是一个具有丰富应用程序编程接口的Web测试工具,可以在浏览器上模拟用户操作。本文利用Selenium生成测试脚本,即通过分析提取扩展有限状态机模型迁移的特征,根据特征信息对迁移进行聚类,再依据Selenium语法规范及映射规则,将聚类结果转为可执行的测试脚本,形成迁移脚本库,为抽象测试用例的可执行化提供服务。

1 面向Web服务器端敏感路径的客户端扩展有限状态机测试生成方法 1.1 基本概念

面向Web服务器端敏感路径的客户端扩展有限状态机测试生成涉及的基本概念定义如下:

定义1  Web服务器端敏感路径。假设程序P的一条语句执行序列为 < s1, s2, …, sn>,若语句s1可接收外部输入数据,语句sn为关键操作语句,如:访问数据库语句、输出语句等,且语句s2sn-1都不是安全验证与过滤机制语句,则称语句序列 < s1, s2, …, sn>为程序P的一条敏感路径,s1称为源点(source),sn为脆弱敏感点(sink)。

定义2  Web客户端扩展有限状态机模型。用来表征Web应用客户端行为的扩展有限状态机模型,其状态和迁移含义如下:

状态s  定义为Web应用软件网页的URL地址及其当前的DOM结构。

迁移t  定义为Web应用软件网页地址或DOM结构发生改变的过程,用一个五元组〈Src(t),Tgt(t),Event(t),Cond(t),Action(t)〉表示,表示迁移t在状态Src(t)下,若事件Event(t)触发,且迁移条件Cond(t)满足,则引发操作Action(t),并将状态转换到Tgt(t)状态。其中,Event(t)对应可驱动客户端代码执行,改变当前网页的DOM结构的事件,包含事件的类型(Etype)、事件绑定的DOM元素、该DOM元素的定位方式(DL)及事件上的输入参数(CIN)和参数的定位方式(CDL)等信息;Cond(t)对应事件处理函数中涉及的谓词条件;Action(t)对应事件处理函数的参数变化及服务器端返回的消息。

定义3   Selenium原子操作。原子操作指不可再分的最小Selenium语法规范,可用三元组 < Cmd,Target,Value>表示,其中Cmd表示一个GUI操作命令,如点击;Target是Cmd的操作对象;若Cmd未输入类命令,Value用来表示接收的用户输入数据,若是非输入类命令,则Value为空。

一个迁移表示用户对Web应用的一次交互,由一个或由几个操作组成。如一个交互可能是用户的1次登录操作,该交互包括输入用户名、密码和点击登录按钮3个子操作。若只触发输入操作而不触发点击操作,则不会引发Web应用的响应,该交互不能作为一个迁移,只有能引发Web应用响应的交互,才能作为迁移。因此,迁移可由多个Selenium原子操作组成。例如,迁移t(user, pwd)为用户的1次登录操作,由输入用户名、输入密码和点击登录3个Selenium原子操作组成,即 < Send_key, user, value1>、< Send_key, pwd, value2>、h click, link=“登录”>。

1.2 面向Web服务器端敏感路径的客户端扩展有限状态机测试生成

面向Web服务器端敏感路径的客户端扩展有限状态机测试生成,是从客户端和服务器端2个方面着手,进行Web应用安全测试用例自动生成的研究,其整体框架如图 1所示,主要包含2部分:1)基于服务器端敏感路径的扩展有限状态机测试用例集Memetic演化生成,2)基于Selenium的测试脚本自动构建。扩展有限状态机测试用例集Memetic演化生成是本文的核心。针对构建的Web应用客户端扩展有限状态机模型,以服务器端敏感路径覆盖为目标,利用Memetic演化算法,实现Web应用客户端扩展有限状态机测试用例集的自动生成。针对扩展有限状态机模型测试用例不可直接执行问题,本文通过提取扩展有限状态机模型中迁移信息特征,进行聚类,根据聚类结果为每一类迁移构建测试脚本,形成迁移脚本库,为抽象测试用例转化为可执行的测试脚本提供支持。

Download:
图 1 面向Web服务器端敏感路径的客户端扩展有限状态机测试用例生成方法框架 Fig. 1 The overview of server-side sensitive path coverage-oriented client-side EFSM test case generation
1.2.1 基于服务器端敏感路径的EFSM测试用例集Memetic演化生成

由Web客户端发出请求,服务器端响应处理的特性可知,Web服务器端的一条敏感路径对应客户端的一次请求操作,而客户端扩展有限状态机模型上的一个迁移表示客户端的一次请求操作。因此,Web服务器上的一条敏感路径对应客户端扩展有限状态机模型的一个迁移。所以,若要覆盖服务器端的某条敏感路径,则需要覆盖该敏感路径对应的迁移。此外,外部输入数据通常是通过POST、GET等请求方法与事件一起提交Web服务器处理,敏感路径源点是接收外部输入数据的语句,由此该迁移事件对应于该敏感路径源点,覆盖该迁移即可覆盖了该敏感路径源点。基于Web客户端构建的扩展有限状态机模型,其迁移上谓词条件只涉及客户端触发事件的谓词条件,没有包含服务器端敏感路径上的谓词条件。所以,扩展有限状态机迁移序列覆盖敏感路径对应的迁移,只能保证该序列覆盖敏感路径的源点,不一定能完全覆盖该敏感路径。因此,在覆盖敏感路径的源点后,需要调整迁移序列上的测试输入,使其能够覆盖敏感路径。

综上,为覆盖服务器端的敏感路径,在生成Web客户端扩展有限状态机测试用例时,可通过全局搜索大幅地调整迁移序列,使之能覆盖对应敏感路径源点的迁移,然后通过局部搜索调整迁移序列上的测试输入,生成能覆盖敏感路径的测试用例。此过程中,本文将敏感路径的实时覆盖信息作为搜索的启发信息,来指导扩展有限状态机模型测试用例的自动生成。因此,本文将遗传算法(genetic algorithm, GA)和模拟退火算法(simulated annealing algorithm, SAA)有机结合,利用GA实现全局搜索生成覆盖敏感路径源点的测试用例,以SA作为局部搜索,对GA生成的测试用例进行校正。2种搜索算法结合使用,直到生成覆盖敏感路径集的测试用例集。演化流程如图 2所示。在扩展有限状态机模型上,随机生成若干条迁移序列及其测试输入,构造初始种群。因从扩展有限状态机模型生成的测试用例是抽象的,所以需对每一个个体生成相应的测试脚本,通过执行测试脚本实现抽象测试用例的执行。

Download:
图 2 EFSM测试用例集Memetic演化流程 Fig. 2 The process of Memetic evolution

同时,服务器端的插桩程序记录各条敏感路径的覆盖情况,通过提取覆盖信息可计算个体对各条敏感路径的覆盖程度f,并构造种群对敏感路径集的评估矩阵M,获取种群对所有敏感路径源点的覆盖情况。若所有敏感路径的源点都被覆盖,则敏感路径源点的覆盖标志cover_flag为True,否则为False。

在迭代过程中,当种群未能覆盖所有敏感路径的源点时,应用GA实现全局搜索,即根据适应度值选择个体进行交叉变异操作以产生新个体。遗传操作产生的所有新个体与当前种群一起参与种群的更新。在更新过程中,若某个个体覆盖新的敏感路径或新的敏感路径的源点,则该个体被添加到测试用例集中。同时,该个体所覆盖的敏感路径从敏感路径集中剔除,后续演化生成只针对未被覆盖的敏感路径。重复上述过程,直到覆盖所有敏感路径的源点或达到最大迭代次数。

此时,可能会出现以下3种情况:1)测试用例集不仅覆盖到所有敏感路径的源点,而且完全覆盖了敏感路径集,则测试用例集生成结束;2)测试用例集仅能覆盖敏感路径的源点而未能完全覆盖敏感路径,启动SA进行局部搜索;3)达到最大迭代次数但仍有敏感路径未被覆盖,重新启动基于GA的测试生成过程。

在SA局部搜索阶段,对每一条未被完全覆盖的敏感路径,从GA生成的测试用例集中选出所有对该敏感路径覆盖程度f在(0, 1]之间的个体(f越小,个体对路径的覆盖程度越高),并按f值从小到大排序构成候选集。然后对f最小的候选个体利用SA搜索生成覆盖该敏感路径的测试数据。若达到终止温度,仍没有找到符合要求的数据,则依次对下一候选个体进行局部搜索,直到该敏感路径被完全覆盖或所有候选个体都不能生成测试输入使其完全覆盖该敏感路径,则考虑下一条未被完全覆盖的敏感路径。若演化搜索达到最大迭代次数仍未能完全覆盖所有敏感路径,则SA搜索结束。

1) 个体表示。

基于Web客户端EFSM模型产生的测试用例包括迁移序列及序列上的测试数据。本文个体是一个测试用例,因此,也由2个部分组成,都采用字符编码。

2) 个体覆盖敏感路径的评价指标。

根据个体执行对敏感路径的覆盖信息,采用通用的approach_level和branch_distance来计算当前个体对敏感路径的覆盖程度fit。fit值越小,说明当前个体对敏感路径的覆盖程度越高。当fit=0时,说明敏感路径完全被覆盖。

$ {\rm{fit}} = {\rm{approach}}\_{\rm{level}} + {\rm{branch\_distance}} $ (1)
$ f = {\rm{ Normalized }}\left( {{\rm{fit}}} \right) $ (2)

式中:approach_level用来衡量当前个体执行路径与目标路径之间的距离;branch_distance用来衡量当前个体执行路径与目标路径不同时,第1个不同分支处谓词条件从假变为真的距离。本文根据变量类型的不同采用不同的计算方法,即对于谓词E1 op E2(op是关系运算符),若E1E2是数值型变量,分支距离为distance(a, b)=|a-b|;若E1E2是字符串型变量,分支距离为2个字符串间的编辑距离。式(2)对fit进行归一化处理,使fit在[0, 1]范围内。

3) 评估矩阵M

矩阵M记录各个个体对所有敏感路径的覆盖程度值f。搜索初始默认敏感路径都未被覆盖,其f置为2。当个体到达某一条敏感路径的源点时,计算该个体对该敏感路径的覆盖程度,并修改M中该路径的f值。从M的行可以得到某一个体对所有敏感路径的覆盖情况,从M的列可以得到所有个体对某一条敏感路径的覆盖情况。

$ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{p_1}}&{{p_2}}&{{p_3}}& \cdots &{{p_k}} \end{array}}\\ {\begin{array}{*{20}{c}} {{\rm{T}}{{\rm{C}}_1}}\\ {{\rm{T}}{{\rm{C}}_2}}\\ \cdots \\ {{\rm{T}}{{\rm{C}}_n}} \end{array}\left[ {\begin{array}{*{20}{c}} 0&{0.540\;9}&{0.985\;3}& \cdots &{0.651\;2}\\ 0&0&2& \cdots &0\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ {0.258\;6}&2&{0.456\;7}& \cdots &{0.156\;1} \end{array}} \right]} \end{array} $

4) 全局搜索适应度函数。

Memetic演化搜索的目标是生成能覆盖所有敏感路径的个体集合,全局搜索的目标是生成能覆盖所有敏感路径源点的个体集合,演化搜索的目标包含全局搜索的目标。因此,可将个体完全覆盖的敏感路径数作为全局适应度值来指导整个种群的进化。个体覆盖的敏感路径数越多,越难再进化出覆盖其他敏感路径的个体,且极有可能在进化过程中失去原本具有的优良基因片段。因此,本文优先挑选覆盖敏感路径数量少的迁移序列参与进化操作。对于那些覆盖敏感路径数的个体则加入最终测试集,同时,被覆盖的敏感路径从目标路径集中剔除。f=0表示个体能完全覆盖某敏感路径,Count(f=0)是此个体完全覆盖的敏感路径的数量。若Count(f= 0)为0,则表明该个体未完全覆盖任何敏感路径,f值越小,说明该个体越逼近某敏感路径。因此,全局适应度值Fglobal设置为:

$ {F_{{\rm{global }}}} = \left\{ {\begin{array}{*{20}{l}} {{\mathop{\rm Count}\nolimits} (f = 0), }&{{\rm{ Count }}(f = 0) \ne 0}\\ {\min (f), }&{{\rm{ 其他 }}} \end{array}} \right. $ (3)

Fglobal越少,个体覆盖的敏感路径数越少或越逼近敏感路径,此个体越好。

5) 局部搜索适应度函数。

局部搜索的目标是寻找能完全覆盖敏感路径的测试数据,因此采用式(2)的f值进行个体评估,即局部搜索的适应度函数flocalf

测试用例集Memetic演化生成算法输入为Web客户端扩展有限状态机模型,敏感路径集P(p1, p2, …, pk);输出为覆盖服务器端敏感路径的测试用例集TS,描述为:

pop=Generate-Initial-Population(EFSM,N)

//随机生成初始种群

while iteration < =max and | Listuncover_path |!=0

M=Executor(pop)//执行个体,得到覆盖矩阵M

cover_flag=setFlag(M, P)

//标记敏感路径源点是否全部覆盖

if cover_flag=True then

//pop覆盖所有敏感路径源点,局部搜索

if | Listuncover_path |=0 then return TS=pop

//覆盖了所有敏感路径,返回生成结果

else

for each p in Listuncover_path do{

Ind=Local-SA-Search(pop,Mp)

//调整个体数据以完全覆盖敏感路径

pop=Update_Individual(pop, Ind)

until | Listuncover_path |=0 return TS=pop else

//pop未覆盖所有敏感路径源点,全局搜索

Fglobal=Global_fitness_Evaluation(pop,M)

Listuncover_path =getUncoverPath(M, P(p1, p2, …, pk))

while size(NewInds) < N do Indi, Indj=Select-Operator (pop, Fglobal)

Indi, Indj=Crossover-Operator(pc, Indi, Indj)

Indi, Indj=Mutation-Operator(pm, Indi, Indj)

NewInds←Indi,Indj

end while

for each Ij in NewInds do

if (isfeasible(Ij)) then NewIndfeasibleIj

M=M∪Executor(NewIndfeasible)

pop=Elite_Update (NewIndfeasible, pop, Fglobal)

iteration++

end while

1.2.2 基于Selenium的测试脚本自动构建

一个迁移的测试脚本不仅应能模拟客户端的用户操作,还应能处理服务器端的反馈信息,如提示、确认弹框等。这些操作都反映在迁移的Event(t)和Action(t)信息中,直接影响到测试脚本需要哪些Selenium指令。因此,本文根据Event(t)和Action(t)信息粗粒度的将迁移划分为4类,如表 1所示。例如,若Event(t)上有输入变量,则在生成测试脚本时,需要生成输入类Selenium指令;若Action(t)有弹窗的提示信息,则在生成测试脚本时,需要生成处理弹窗的Selenium指令。

表 1 迁移的粗粒度分类 Table 1 Coarse-grained classification of transition

另一方面,一个迁移代表的交互操作可由多个Selenium原子操作组成,基于Selenium原子操作可以生成完整的Selenium指令。因此,测试脚本构建可先通过分析提取扩展有限状态机模型上所有迁移的特征;然后根据迁移特征聚类,结合粗粒度,确定映射规则,为每一类迁移构建对应的测试脚本,形成迁移脚本库。

1) 迁移特征分析及提取。

对于2个迁移,当它们的事件类型、事件绑定的DOM元素的定位方式、事件上的输入参数个数、参数的定位方式及引发的后续操作响应这5方面的信息一致时,这2个迁移具有相同的操作行为,可共用同一个迁移测试脚本。因此,选取以上信息作为迁移特征。

2) 迁移聚类。

聚类可以将操作行为相似的迁移分为一类,可以共用一段测试脚本,因此,不需要为每个迁移都写一段测试脚本。迁移特征量化后的数据样本是稀疏、离散的。与传统聚类算法相比,谱聚类算法能在任意数据样本空间上进行聚类并收敛于全局最优解,聚类效率高。因此,本文采用谱聚类算法进行迁移聚类。

相似度计算是聚类的关键。若将全部特征看成字符串采用常规的距离公式(如编辑距离)进行计算,则极有可能因模糊特征本身的意义而导致分类的准确程度降低。例如按照 < Etype,DL,Action,CDL,CIN>的格式,3个迁移TiTjTk的特征信息分别为Ti= < click,link,alert,name,1>,Tj= < click,link,alert,name,2>,Tk= < click,link,alert,name,3>。若采用编辑距离计算,则迁移TiTjTk两两之间的编辑距离值均为1,导致聚类时3个需要不同测试脚本的迁移会被分为同一类。

为此,本文设计如下公式来计算迁移特征间的相似程度S(Ti, Tj):

$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;S\left( {{T_i}, {T_j}} \right) = \\ \left\{ {\begin{array}{*{20}{c}} {0, }&{{T_i}({\rm{CIN}}) \ne {T_j}({\rm{CIN}})}\\ {\frac{{2{\rm{LCS}}\left( {S\left( {{T_i}} \right), S\left( {{T_j}} \right)} \right)}}{{{\rm{TL}}}}, }&{其他} \end{array}} \right. \end{array} $ (4)

式中:S(Ti)表示迁移Ti的特征,是由表示Etype、DL、Action、CDL特征信息构成的字符串,TL是S(Ti)与S(Tj)的字符串总长,LCS表示2个字符串的最长公共子串的长度。

当2个迁移的输入参数个数CIN不同时,这2个迁移对应的Selenium原子操作个数也不同,S(Ti, Tj)=0;反之,通过特征字符串的最长公共字串来计算2个迁移之间的相似度。当2个迁移的特征字符串没有公共子串时,二者相似程度为0;当2个迁移的特征字符串完全一样时,二者的相似程度为1。根据相似度公式构建迁移之间的相似矩阵S,用于谱聚类算法,可得到聚类结果。

3) 测试脚本自动生成方法。

测试脚本自动生成的映射规则包含2部分:第1层是粗粒度的,根据迁移的T.CIN和T.Action信息确定要调用的Selenium指令;第2层是细粒度的,将迁移的特征信息T.Etype、T.DL、T.CIN、T.CDL映射到Selenium原子操作命令语句的相关部分,通过字符串拼接的方式与Selenium的部分命令语句构成完整的Selenium命令,从而构成迁移测试脚本。测试脚本还需要引用一些Selenium模块信息才能执行,也需将这部分信息写入迁移测试脚本库中。

测试脚本生成算法:输入为迁移类别CResult,模板信息Template,每一类迁移的特征信息 < EtypeDlocator,Action,PlocatorPnum>;输出为:迁移测试脚本库TransitionScriptLib;其中:Cstr, ACstr为不完整的selenium命令;DEstr为函数名标识(一类迁移脚本封装在一个函数中)。描述如下:

TransitionScriptLib=∅; ScriptContent=∅;

Cstr=“a=driver.find_element_by”;

ACstr=“driver.switch_to_alert().accept()”;

DEstr=”def TFunction%s(driver,object)”;

for each TCResult do

TestScriptLib ←DEstr;

if T.Pnum= 0 and T.Action $ \not\subset $ AlertMessage//类别1

ScriptContent=Function C1();

if T.Pnum= 0 and T.Action ⊆ AlertMessage//类别2

ScriptContent=Function C2();

if T.Pnum!=0 and T.Action $ \not\subset $ AlertMessage//类别3

ScriptContent=Function C3();

if T.Pnum!=0 and T.Action ⊆ AlertMessage//类别4

ScriptContent=Function C4();

TransitionScriptLib ←Template,ScriptContent;

return TransitionScriptLib;

Function C1()

StrA=Cstr+T.DL;

StrB=“a.”+T.Etype;

ScriptContent ← StrA,StrB;

return ScriptContent

Function C2()

text=Function C1();

ScriptContent←text,ACstr;

Function C3()

for each i ∈T.CIN do

StrA=Cstr+T.DL(i); .send_keys(di));

StrB=Cstr+T.DL;

StrC=“a.”+T.Etype;

end for

ScriptContent ← StrA,StrB,StrC;

return ScriptContent

Function C4()

text=Function C3();

ScriptContent ←text,ACstr;

当2个迁移的输入参数个数CIN不同时,这2个迁移对应的Selenium原子操作个数也不同,S(Ti, Tj)=0;反之,通过特征字符串的最长公共字串来计算2个迁移之间的相似度。当2个迁移的特征字符串没有公共子串时,二者相似程度为0;当2个迁移的特征字符串完全一样时,二者的相似程度为1。根据相似度公式构建迁移之间的相似矩阵S,用于谱聚类算法,可得到聚类结果。

3) 测试脚本自动生成方法

测试脚本自动生成的映射规则包含2部分:第1层是粗粒度的,根据迁移的T.CIN和T.Action信息确定要调用的Selenium指令;第2层是细粒度的,将迁移的特征信息T.Etype、T.DL、T.CIN、T.CDL映射到Selenium原子操作命令语句的相关部分,通过字符串拼接的方式与Selenium的部分命令语句构成完整的Selenium命令,从而构成迁移测试脚本。测试脚本还需要引用一些Selenium模块信息才能执行,也需将这部分信息写入迁移测试脚本库中。测试脚本生成算法如算法2所示。

2 实验及结果分析

为评估所提方法的有效性,本文通过以下3个问题进行实验研究。

RQ1:迁移测试脚本库构建方法是否可行?

RQ2:本文方法在Web应用程序的测试用例生成中的效果如何?

RQ3:本文方法与其他方法相比测试生成的效率如何?

本文以开源Web应用SchoolMate、Webchess和FAQforge作为实验对象,相关信息见表 2表 3

表 2 实验程序 Table 2 Web applications of under test
表 3 实验程序的模型及敏感路径信息 Table 3 Information for client-side EFSM model
2.1 测试脚本自动构建可行性验证

迁移聚类的准确程度直接影响得到生成的测试脚本是否有效,而迁移聚类的核心是迁移之间的相似度性度量。为回答RQ1,本实验以手工统计结果为基准,比较不同相似度的谱聚类精确度AclusterAcluster为能正确分类的迁移数量(#CCTrans)除以迁移总数。本文与使用较为广泛的编辑距离进行对比实验,聚类精度结果如表 4所示。

表 4 基于不同相似度公式的聚类精度结果 Table 4 Cluster accuracy for two similarity formulas

结果表明,采用本文相似度(SF-our)的谱聚类结果与基准结果相同,并且明显优于采用编辑距离(SF-edit)的谱聚类结果。

2.2 面向Web服务器端敏感路径的扩展有限状态机测试用例生成的有效性验证

为回答RQ2和RQ3,本文方法(MyGA+MySA)与其他2种组合方法,即本文的遗传算法与爬山算法(MyGA+HC),传统遗传算法与爬山算法(GA+HC)进行对比实验。与本文所提GA相比,在以路径作为覆盖目标的优化问题上,传统GA将目标敏感路径与执行路径之间的距离作为个体的适应值,并且不包含本文提到的更新策略。

实验结果如表 5所示,在3个被测程序中,GA+HC方法的全局搜索代数分别为334、361、28,大于另外2种使用MyGA的组合方法,说明MyGA能比GA更快地搜索到能覆盖所有敏感路径源点的个体集合。MyGA+MySA与MyGA+HC在SchoolMate和Webchess中全局搜索代数比较接近,分别为51、53和63、65,但在局部搜索上,MySA优于HC,说明MySA能比HC更快地搜索到完全覆盖敏感路径所需的测试数据。

表 5 测试用例生成的搜索代数比较 Table 5 Iterations comparison of test case generation

时间开销由搜索个体和执行个体2部分时间组成。由表 6可以看出,本文方法在需要执行的个体数量和时间开销上显著少于其他2种方法,并且个体执行时间对总时间的占比均为95%以上,说明实际搜索个体的时间很少。

表 6 测试用例生成的时间开销情况 Table 6 The time cost of test case generation

图 3可以看出,3种测试生成方法经过反复迭代最终都可以覆盖Web应用中的所有敏感路径。随着搜索代数的增加,3种方法生成的个体集合对敏感路径集的覆盖率逐渐提高,其中MyGA+MySA和MyGA+HC上升较快,而本文方法(MyGA+MySA)能较早地覆盖所有敏感路径。

Download:
图 3 3种测试生成方法在3个被测程序搜索过程中对敏感路径的覆盖情况 Fig. 3 Coverage of sensitive paths by the three test generation methods during three search processes

由此可见,对于3个被测程序,本文方法在总搜索代数,执行个体数量及时间开销上优于于其他两种方法。此外,测试用例生成的结果表明本文方法可以生成满足要求的测试用例,这意味着从客户端行为模型扩展有限状态机上生成的抽象测试用例可以转换为测试脚本并执行,进一步验证了本文所提出的测试脚本自动生成方法是可行和有效的。

3 结论

1) 基于Selenium的测试脚本自动构建方法,能有效解决由模型生成的抽象测试用例不可直接执行问题。

2) Memetic进化搜索能从Web应用客户端EFSM生成测试用例覆盖服务器端敏感路径;并且在搜索过程中,以敏感路径的覆盖信息作为启发信息设计的全局和局部适应度函数能够加速演化过程,在总搜索代数,执行个体数量及时间开销上优于其他2种方法。

针对测试用例自动生成,在后续的工作中将考虑根据更多的过滤机制来生成多样化的恶意数据,增加测试用例的故障检测效果。

参考文献
[1]
DOČAN S, BETIN-CAN A, GAROUSI V. Web application testing:a systematic literature review[J]. Journal of systems and software, 2014, 91: 174-201. (0)
[2]
LEE T K, WEI K T, GHANI A A A. Systematic literature review on effort estimation for Open Sources (OSS) Web application development[C]//Proceedings of 2016 Future Technologies Conference. San Francisco, 2016: 1158-1167. (0)
[3]
缪淮扣, 陈圣波, 曾红卫. 基于模型的Web应用测试[J]. 计算机学报, 2011, 34(6): 1012-1028.
MIAO Huaikou, CHEN Shengbo, ZENG Hongwei. Model-based testing for Web applications[J]. Chinese journal of computers, 2011, 34(6): 1012-1028. (0)
[4]
SCHUR M, ROTH A, ZELLER A. Mining workflow models from web applications[J]. IEEE transactions on software engineering, 2015, 41(12): 1184-1201. (0)
[5]
WANG Weiwei, GUO Junxia, LI Zheng, et al. EFSM-oriented minimal traces set generation approach for web applications[C]//Proceedings of 2018 IEEE 42nd Annual Computer Software and Applications Conference. Tokyo, 2018: 12-21. (0)
[6]
ALSHAHWAN N, HARMAN M. Automated web application testing using search based software engineering[C]//Proceedings of 2011 26th IEEE/ACM International Conference on Automated Software Engineering. Lawrence, KS, USA, 2011. (0)
[7]
ZHAO Ruilian, LYU M R, MIN Yinghua. Automatic string test data generation for detecting domain errors[J]. Software testing verification & reliability, 2010, 20(3): 209-236. (0)
[8]
LI Yuanfang, DAS P K, DOWE D L. Two decades of Web application testing-a survey of recent advances[J]. Information systems, 2014, 43(3): 20-54. (0)
[9]
任君, 赵瑞莲, 李征. 基于禁忌搜索算法的可扩展有限状态机模型测试数据自动生成[J]. 计算机应用, 2011, 31(9): 2440-2443, 2452.
REN Jun, ZHAO Ruilian, LI Zheng. Automatic generation of test data for extended finite state machine models based on Tabu search algorithm[J]. Journal of computer applications, 2011, 31(9): 2440-2443, 2452. (0)
[10]
JAN S, NGUYEN C D, ARCURI A, et al. A search-based testing approach for XML injection vulnerabilities in web applications[C]//Proceedings of 2017 IEEE International Conference on Software Testing, Verification and Validation. Tokyo, 2017: 356-366. (0)
[11]
郭俊霞, 郭仁飞, 许南山, 等. 基于Session的Web应用软件EFSM模型构建方法研究[J]. 计算机科学, 2018, 45(4): 203-207, 214.
GUO Junxia, GUO Renfei, XU Nanshan, et al. Study on construction of EFSM model for Web application based on Session[J]. Computer science, 2018, 45(4): 203-207, 214. (0)
[12]
AHMED M A, ALI F. Multiple-path testing for cross site scripting using genetic algorithms[J]. Journal of systems architecture, 2016, 64: 50-62. (0)
[13]
MARASHDIH A W, ZAABA F. Web security:detection of cross site scripting in php web application using genetic algorithm[J]. International journal of advanced computer science and applications, 2017, 8(5): 64-75. (0)
[14]
HARMAN M, MCMINN P. A theoretical and empirical study of search-based testing:local, global, and hybrid search[J]. IEEE transactions on software engineering, 2010, 36(2): 226-247. (0)
[15]
FRASER G, ARCURI A, MCMINN P. A memetic algorithm for whole test suite generation[J]. Journal of systems and software, 2015, 103(2): 311-327. (0)