焦永强 王维扬 尚 颖

（1.中国航空综合技术研究所 北京 100028）（2.北京化工大学 北京 100029）

1 引言

随着互联网的飞速发展，Web应用以其易于开发与升级、扩展性好、系统灵活性强等优点，获得了越来越多企业的青睐。但Web应用程序相较于传统应用程序，拥有更独特的结构和功能，传统软件测试技术难以对Web应用进行有效的测试。

Web页面是构成Web应用的基本元素，是用户与Web应用交互的媒介。传统的Web应用为每个页面绑定了一个唯一的URL，因此，页面可以用URL表示。然而，在Web 2.0中，为丰富交互及响应，提升用户体验，JavaScript（JS）和 DOM（Docu⁃ment Object Model）广泛使用。因此，Web页面的改变不再由URL决定，而是由DOM的动态改变决定。即Web页面表示为DOM树，JS代码执行过程中动态改变DOM树，从而使得页面发生变化。A.Nederlof等的研究表明，在Web 2.0应用中，平均每个URL对应16个DOM页面［1］。由此可以看出，DOM微小变化可使Web页面急剧扩充，导致页面集合十分复杂与庞大，增大了Web应用测试的难度。

在Web应用测试过程中，由于一个Web应用中大量页面具有类似的DOM树结构［2～4］，而对这些相似Web页面单独生成测试用例进行测试降低了测试生成效率。为减少相似Web页面对测试生成的影响，大多采用Web页面聚类方法，即将相似页面聚为同类，类内页面作为一个页面进行测试，以减少测试的时间开销。

目前，Web页面聚类方法主要有三类：面向URL的页面聚类［5］、基于页面超链接的页面聚类［6］和基于DOM结构的页面聚类方法［7～11］。由于JS和Ajax技术的使用，页面超链接和URL不能很好地表示Web页面，因此，其对应的页面聚类方法应用领域有限。当前的研究主要集中在基于DOM的页面聚类方法。文献［7］最早提出基于DOM树的页面聚类方法，该方法利用树编辑距离来度量两页面之间的相似度，并基于此对页面进行聚类，然而树编辑距离的计算复杂度高，且该方法未考虑由于页面内容不同导致的相似Web页面，因此，聚类准确度不高。文献［8］提出了一种基于DOM结构和样式相结合的页面聚类方法，采用树编辑距离作为结构相似度的度量准则，同时考虑页面样式，如布局/颜色/字体等的相似度对页面进行聚类。该方法聚类准确度有所提升，但其计算复杂度很高。

文献［9］提出了Bag of Xpath模型，把页面表示为包含当前页面元素位置索引的Xpath集合，通过计算两个页面Xpath集合元素之间的差异来度量二者之间的相似度，进而实现页面聚类，该方法虽然降低了计算复杂度，但其聚类准确度不高。文献［10］通过深度遍历将两个页面的DOM结构转换成一个元素节点标签序列，比较两个页面的节点标签序列来计算页面之间的相似度，同样地，该方法的页面聚类准确度不太理想。

综上，目前Web页面聚类准确率较低而时间复杂度较高。分析其原因，是由于1）上述方法大多仅考虑DOM树结构之间的相似性。具有相同DOM结构的页面可能表征的功能不同，在Web应用功能测试时不应被划分至同一类；2）现有的页面之间相似性度量方法不能准确区分不同页面，且其相似性计算及聚类算法的时间复杂度较高。

此外，Web页面属性为页面元素定义属性（如id、name和class），实现页面元素样式渲染以及事件绑定，为Web应用程序提供了多种定制化服务。可以看出，页面属性与Web页面功能密切相关。换言之，为区分表征不同功能的页面，页面元素的属性必不可少。

因此，本文提出一种新的页面聚类方法，不仅考虑了DOM结构之间的相似性，而且考虑了页面属性之间的相似性，同时给出了一种新的页面相似性度量方法。在此基础上，改进了现有的页面聚类算法，实现Web页面聚类。该方法不仅能够描述复杂的Web页面，且具有较低的时间复杂度和较高的页面聚类准确度。

2 Web页面DOM结构与节点属性

Web页面是构成Web应用的基本元素，DOM将页面表达为树结构，称为DOM树，DOM树上的节点类型包括元素节点、属性节点和文本节点，分别表示页面中的元素、文本和属性。为了表述方便，下文将“元素节点”统称为“节点”，“属性节点”统称为“属性”，“文本节点”统称为“文本”。所有DOM节点相互包含组成的树形结构构成了Web页面的基本结构，也被称为DOM结构。

2.1 DOM

DOM将Web页面表达为树结构，定义了访问和操作页面节点、文本及属性的标准方法。Web页面以标签（tag）来标识DOM节点，如图1所示。图1的树形结构表示了一个简单Web页面的DOM树，表示某教师管理系统的用户管理页面，该页面实现对教师的增删改等操作，其中浅灰线为属性，点线为文本，其余为节点。

图1DOM树

2.2 节点属性

Web页面的每一个节点都拥有若干属性，在构建网页时，节点属性必不可少，且每个属性都具有其作用。根据W3C标准，id属性用来唯一标识网页中的元素，如果两个Web页面中的两个节点具有相同的id，则它们有极大的概率是相同的节点。class属性用来标识一类元素，这一类元素往往具有相同的样式，因为CSS通常采用class（类）名来为节点定制样式。Id和class属性都有一个最重要的特性，即能够绑定事件，因此，二者与Web应用的行为密切相关。name属性比较特殊，表示一个节点的名字，常常用于form节点中。在Web应用中form节点被大量的使用，而在Web测试中不同的form往往意味着与后台数据交互的不同，表示不同的功能，这对功能测试有很大的影响。

图2为某图书管理系统的书籍管理页面，实现对书籍借阅、查找、归还等操作。图1和2所示的两个DOM具有相同结构，但其div标签具有不同的id及name，且为不同的id绑定不同的事件。因此，即使这两个Web页面的DOM结构完全相同，也应被识别为不同的页面。

图2 与图1具有相同DOM结构的DOM2

显然，基于DOM结构的页面聚类方法对此类页面的聚类准确度较低。因此，为准确区分不同Web页面，在进行页面比较时，不仅需要考虑Web页面中DOM结构之间的相似性，属性之间的相似性比较在页面聚类中也十分重要。

3 Web页面相似性度量新方法

Web应用的页面中，具有相同DOM结构的页面可能表示不同的功能页，而在Web应用功能测试时不能被划分至同一类。因此，仅考虑DOM结构相似性的页面聚类方法会产生大量误报的情况。为提高页面聚类的准确性，本文同时考虑Web页面之间DOM结构和属性的差异，提出了新的页面相似度度量方法，并给出一种高效的改进树匹配算法来计算页面相似度。

本节首先定义页面之间的页面相似量定义；然后，给出改进树匹配算法计算页面相似量；最后，为比较多个Web页面之间的相似程度，基于页面相似量，给出页面之间相似度计算方法。

3.1 相似性度量指标

页面相似量用来度量两个Web页面，即两棵DOM树，之间的相似程度，由DOM树上各个节点之间的节点相似量求和得出。由上述分析可知，仅通过DOM结构之间的相似程度进行页面聚类是不充分的，页面属性也与Web应用功能密切相关，因此，本文同时考虑页面结构和属性之间的相似性，给出页面相似性度量方法，以准确识别相似页面。

为度量节点及属性之间的相似量，我们针对DOM树定义四种相似基量：Tag相似基量λtag、ID相似基量λid、Name相似基量λname和Class相似基量λclass，相似基量表示节点相似量度量时节点及属性的相似量权重。

两棵DOM树根节点标签tag值相似基量为式（1）。

节点各属性（id、name、class）的相似基量如式（2～4）。

其中 ||ID1和 ||ID2分别表示两个DOM树中具有id属性的节点个数，name和class同理， ||T1和 ||T2分别表示两个DOM树的节点总数。

算法一：两个Web页面DOM树T1和T2页面相似量计算

输入：两个Web页面DOM树T1和T2

输出：T1相对于 T2的相似量 F（T1，T2）

步骤1.分别对T1和T2进行深度遍历得到它们的总结点个数|T1|和|T2|，分别具有 id、name、class属性的节点个数|ID1|、|NAME1|、|CLASS1|、|ID2|、|NAME2|、|CLASS2|；

步骤2.通过式（2）～（4）计算各个属性的相似基量值λid、λname、λclass；

步骤3.设T1的当前根节点为N1，T2的当前根节点为N2，当前树的相似量为F（T1，T2）=0 ；

步骤6.转步骤3进行递归计算得出T1i相对于T2j的相似量为 F（T1i，T2j）；

步骤 7.j=j+1，判断如果 j>m，F（T1，T2）=F（T1，T2）+F（T1i，B），i=i+1，j=0 ；否则 F（T1i，B）=MAX（F（T1i，B），F（T1i，T2j）），转步骤6；

步骤8.判断如果i>n，算法停止，输出F（T1，T2）；否则转步骤6；

根据DOM特性，定义两个节点N1和N2之间的节点相似量：当tag值不同时，他们之间的节点相似量f（N1，N2）=0，相同时相似量如式（5）。

众所周知，沙特阿拉伯是美国在中东地区的重要盟友和战略支点。美沙之间不断发展的紧密联系，成为了美国在中东地区发挥影响力的重要支点。

其中当id值、name值相同时，Cid=Cname值为“1”，不相同时值为“0”；Cclass计算公式如下：

在节点相似量的基础上，给出页面相似量计算公式如下：假设两页面对应的两棵DOM树为T1和T2，其根节点分别为 N1和 N2，T1和 T2子树的集合为A=［T11，T12，T13，…，T1n］，B=［T21，T22，T23，…，T2m］，则定义T1相对于T2的页面相似量为式（7）：

式（1～7）定义了节点之间的节点相似量及DOM树之间的页面相似量度量公式。为计算两棵DOM树之间的页面相似量，我们在现有树匹配算法［12］的基础上，增加了对页面属性信息的度量，提出了改进的树匹配算法，如算法一所示。

3.2 相似度定义

页面相似量是一个绝对值，它在一定程度上能反映两个页面的相似程度，但是在多个网页之间并没有可比性，因此，本文将页面相似量进行归一化，记为页面相似度，并用相似度来进行Web页面间的差异性比较。对于给定的两个Web页面，它们对应的DOM树分别为T1和T2，|T1|和|T2|分别表示两者的节点个数，假设二者包含id属性的节点总个数为M，包含name属性的节点总个数为N，包含class数属性的节点总个数为K，则它们之间的相似度定义为式（8）：

其中 F（T1，T2），F（T2，T1）分别表示 T1相对于 T2的相似量及T2相对于T1的相似量，λid、λname和λclass的计算如式（2～4）。

4 标记聚类算法

Web页面集合庞大，页面多种多样且结构复杂，因此，无法预先判断最终聚类的个数，这使得一些传统的聚类算法如k-means不再适用于Web页面聚类［13］。凝聚层次聚类（Hierarchical Agglomera⁃tive Clustering，HAC）方法是一种常用的层次聚类算法，该方法无需预先设定类簇个数，常被应用于Web页面聚类中［14～15］。基础凝聚层次聚类HAC算法具有o（n3）的时间复杂度，改进的凝聚层次聚类算法［16］，能达到的最好的时间复杂度是o（n2）。本文在改进的HAC基础上，提出了标记聚类算法（Marked Clustering，MC），即在聚类的同时进行页面标记，在理想的情况下最低能达到o（n）的时间复杂度。

4.1 MC聚类算法基本思想

为了在保证聚类准确性的同时减少聚类所用的时间，本文基于Web页面的特性提出标记聚类算法。该算法的核心思想是在计算Web页面间相似度之后，对页面进行聚类标记，即当Web页面之间的相似度超过设定阈值，则将两个Web页面标记为同一类；针对已经标记的Web页面不再进行后续的Web页面比较；且各类仅取任一页面作为当前类中所有页面的代表，当判断其他Web页面是否归属于此类时，仅与类中的代表页面进行相似度比较即可。

4.2 算法描述

标记聚类MC主要有以下五个步骤，算法流程如图3所示。

图3 MC算法流程

1）初始化两个集合A、B，其中A是所有Web页面的集合，B=Ф；聚类标记k=0；

2）从A中选择一个元素a，将［a，k］添加到B中，然后从A中删除a；

3）从A中顺序选择一个元素b，通过改进树匹配算法计算a与b之间的页面相似度，如果相似度大于阈值则将［b，k］添加到B中，然后从A中删除b；否则进行下一步；

4）判断是否遍历A中所有元素，如果是进行下一步，否则转3）；

5）判断A是否为空，如果不为空则令k=k+1，转2）。

最终得到B集合即为聚类结果，B中每个元素均为二元组，表示Web页面及其所属的类簇的标号。

标记聚类MC算法的时间复杂度是o（n2），但是由于每一次循环都会减少下一次需要比较的页面数量，事实上程序运行时间会大大降低。且最终聚类的数量越少，该方法的时间复杂度越小。在理想的情况下最少能达到o（n）的时间复杂度。

5 实验

为了验证本文方法的有效性，我们提出了两个研究问题如下：

1）Web页面相似性度量方法的有效性如何？改进树匹配算法是否优于其他树匹配算法？

2）标记聚类算法MC是否能在不影响聚类结果的前提下提高聚类效率？

5.1 实验对象与环境配置

实验采用两个开源的Web应用e107和word⁃press作为被测程序。实验在Intel酷睿i5（3470 3.4GHZ）4核CPU、内存8GB、Win10操作系统、Py⁃thon 3.6.4和htmlParser环境下进行。本文选用常用的简单树匹配算法作为相似性对比算法，HAC作为聚类对比算法，设计了以下两个实验。

实验一：分别使用简单树匹配和本文提出的改进树匹配算法完成页面相似性度量，聚类方法均采用同一凝聚层次聚类方法进行页面聚类。

实验二：相似性度量采用本文提出的改进树匹配的算法，聚类方法分别使用凝聚层次聚类和本文提出的标记聚类进行比较。

5.2 实验结果

5.2.1 相似度算法结果

为了比较两种相似度算法（改进树匹配和简单树匹配）的优劣，本实验收集了两个开源Web应用的100张Web页面，并对其进行人工聚类，然后将每一类的页面与同一类的页面以及其他类的页面进行相似度计算，比较他们的相似度值。对于同类页面，两种算法均得到了大于0.9的相似度值，这说明对于相似页面，两种算法都能很好的比较其相似度。但对于不同类的页面，实验结果如图4所示。

从图4可以看出，本文提出的改进树匹配算法对于属于不同类的页面计算得到的相似度明显小于简单树匹配算法的结果，而且均小于0.9，这说明本文的改进树匹配算法区分不同类页面的能力强于简单树匹配算法。

图4 两种算法的页面相似度计算比较结果

表1 e107

表2 wordpress

为了直观展示两种相似度算法对聚类结果的影响，本部分还给出了分别使用两种相似度度量算法结合同一层次聚类算法得到的聚类结果，如表1，2所示，本文提出的改进树匹配算法准确率和召回率都明显优于简单树匹配算法。这是由于简单树匹配将大量的不属于同一类但是却有相似DOM结构的网页聚为一类，使得该算法的召回率极低。经过进一步的分析发现，由于Web应用中大量使用同一框架和form表单，这使得简单树匹配算法聚类失误，但本文提出的改进树匹配算法考虑了更多的属性信息，从而得到了更好的聚类效果。

5.2.2 聚类算法结果

为比较两种不同的聚类算法的效率，采用相同的页面相似性度量方法，即改进树匹配算法，不同的页面聚类算法对上述两个Web应用进行了页面聚类实验。其中凝聚层次聚类HAC算法中类之间的相似度采用如式（9）进行计算：

两种聚类算法对Web页面聚类的实验结果如表3和表4所示。

表3 e107聚类算法比较

表4 wordpress聚类算法比较

观察上表可以明显看出本文提出的标记聚类算法MC并没有影响聚类的结果，但是却明显减少了聚类时间，提高了页面聚类效率。具体来说，对于e107效率提升了3.4倍，而对于wordpress效率提升了5.6倍。因此，本文提出的标记聚类算法效率更高。

6 结语

在Web测试中，为解决现有方法在页面聚类时准确率低及效率不高的问题，本文提出了一种改进树匹配算法，不仅考虑Web页面结构信息还考虑部分属性信息，通过该算法来计算Web页面之间的相似度显著提高了聚类的准确性。同时为了解决传统聚类算法耗时长的问题，提出一种更为简单有效的标记聚类算法MC。实验证明，本文的聚类算法在不影响聚类的准确性的前提下显著地降低了聚类所用的时间。