基于爬虫的智能爬行算法研究

侯美静 崔艳鹏 胡建伟

(西安电子科技大学网络与信息安全学院 陕西 西安 710000)

0 引 言

基于Web系统的多层体系结构以及与其他不同类型的子系统之间的复杂交互，增加了可以被攻击者利用的安全漏洞的数量。正如开放式Web应用程序安全项目OWASP(Open Web Application Security Project)[1]所强调的那样，攻击者可能会沿着基础结构跟踪各种路径，以发现可能会导致严重后果的安全漏洞。我们就需要对Web应用执行例行巡检，采取必要的行动降低安全风险。软件开发人员通常使用Web应用巡检系统来自动检查其基于Web应用程序的安全性，并对许多不同的Web应用程序进行大规模安全分析[2-3]。

在Web应用巡检系统里，爬虫是按照一定的爬行策略，做站内的URL爬取，从而获得目标网站下所有的可视或不可视的URL信息。巡检系统对于所有的URL进行安全审计，但是对于同源网站来说，存在大量结构相似的URL和网页，对于此类URL和网页，重复地审计不会发现新的漏洞。现在的爬虫技术多采用URL相似性去重，雷佳伟[4]通过研究Scrapy爬虫框架，分析页面爬取及解析的过程，并研究了URL相似性去重，但是这种方法会将大量的非相似的网页去重，失误率过高。贺建英[5]针对搜索引擎提出了一种基于Rabin指纹算法进行URL去重、网页内容相似和相同去重，将网页文档进行定长分块，然后用Rabin指纹算法计算每个网页块的指纹，通过比对两个网页分块指纹的重复率来判定网页是否相似，这种方法只适用于网页结构绝对类似，网页内容相同的的情况。而其他人[6-7]关注更多的是爬虫的覆盖率，只是进行URL去重，并没有考虑网页相似的问题，而对参数进行模糊测试的方法查找漏洞。开发人员尽量避免在URL里显示明显的参数，所以已有的技术不能满足Web应用巡检系统的需求。

针对以上文献中的不足，本文针对智能巡检系统提出了一种基于URL去重和以网页相似度为基础的聚合式层次聚类的智能爬行算法，能有效地去除重复的URL和大量结构相似的网页，最大程度缩小巡检系统的测试目标，提高检测效率。

1 智能爬行策略

随着Web应用的发展，爬虫技术也在改进。从早期的通用爬虫到现在的主题爬虫[8]、深度爬虫[9]等等，满足了不同用户的不同需求。

通用爬虫的爬取过程比较简单，一般是从初始的URL开始爬取网页，将获得的URL放入待爬取的列表里，等初始页面爬完，再从待爬取列表里取出新的URL开始爬取，依次循环，直到待爬取列表为空或者满足设置的停止条件。这种方法简单，比较常用，但是这类爬虫只是针对URL进行单一爬取，不能满足用户额外的需求。

深度爬虫相对于通用爬虫来说比较复杂，对于获得的页面不光提取URL，还会进行解析，对URL进行去重，提高了爬行效率避免陷入死循环。

在深度爬虫的基础上，本文提出了一种智能爬虫策略。智能爬虫的爬取过程是：以一个初始URL为起点爬取相关的所有网页，然后利用智能爬行算法爬取网站，最后得到无重复的URL，且URL对应的网页结构都是不相似的。本文所提出的智能爬行算法，首先对URL去重丢弃重复的URL。下一步利用页面相似度公式依次计算两个URL对应页面的相似度值，具体是将页面解析成DOM树，根据节点的位置、DOM树的深度以及深度相同的节点数量，将权重分配给每个节点，再根据给定的公式计算网页的相似度。最后以相似度为基础，使用聚合式层次聚类思想将具有相似结构的网页聚为一组，只选取代表URL进行后续测试。

本文提出的智能爬行算法的计算过程分三个阶段，如图1所示。第一阶段需要对URL去重；第二阶段对网页解析并计算网页相似度；第三阶段将相似度满足设定阈值的网页进行聚类，并从每一类中选取一个URL作为代表进行后续检测。整个计算过程称为智能爬行算法。

图1 智能爬行算法图

2 智能爬行算法

2.1 URL去重

URL又称统一资源定位符，是对互联网上资源的位置和访问方法的一种简洁的表示，是互联网上标准资源的地址[10]。它可以理解为是互联网上资源的索引，通过它爬虫就可以找到新的资源，获取新的URL。但是并非所有的URL都是可用的，对于重复的、相似的、存在包含关系的URL要进行过滤，可以减少重复爬取的时间，提高智能巡检系统的整体效率。

URL的完整格式(其中带[]的为可选项)如图2所示。图3为URL分片对应图。

图3 URL分片对应图

图2 URL格式图

URL重复：两个URL的协议、主机名、端口、路径、参数名和参数值完全一样。

URL相似：两个URL的协议、主机名、端口、路径、参数名和参数个数都相同。

URL包含：两个URL记为A和B，协议、主机名、端口、路径都相同。若A的参数个数大于或等于B，且B的参数名列表与A的参数名列表存在包含关系。

在HTML中，URL主要会在下列常见的标签中产生，可以通过其相关的属性值来获取，如表1所示。

表1 存在URL的常见标签及属性

爬虫在爬取网页的过程中，总会出现很多重复的URL。重复的爬取不会发现新的URL链接，只会浪费计算资源和延长爬行时间甚至使爬行陷入死循环。因此，需要过滤这类URL，减少重复爬取。智能爬行算法的第一阶段就是基于Rabin指纹算法[4]对URL去重。基本步骤如下：

(1) 输入一个URL值作为参数。

(2) 构造一个初始值为0，长度为n的列表L用于存放指纹映射。再构造一个空列表U，用于存放爬取过的URL。

(3) 对该URL爬取出的所有url进行循环，循环包括：计算每个url的指纹值，将指纹值r映射到列表L中。判断列表中L[r]的值是否为0，若为0，则将L[r]置为1，并将此url存放入列表U中。若值为1，则舍弃。

2.2 页面相似度

对于同源网页，大量的网页结构是相似的，只是少量内容不同。在进行漏洞巡检时，会对每一个URL进行渗透测试，这样会做大量的无用工作，浪费时间。也有人通过比对URL的相似度，去除相似的URL，但是这种方式误差太大，可用性不强。本文提出的智能爬行算法通过比对网页结构的相似度，当相似度达到设定阈值后，才判定为相似，这种方法对于网页去重更精确，更具可行性。

智能爬行算法的第二阶段就是计算网页的相似度。这里采用一种基于平均分配权重的网页结构相似度测量方法。首先对网页构造DOM树[11]结构并预处理，将DOM树下的标签作为树的节点，对于文本内容则统一用text表示，只比较两个页面的结构相似度。再将权重平均分配给节点，具体步骤如下：

① 令整个DOM树的权重为1，对于深度为1的根节点，权重为1；对于深度为2的根的子节点，若数量为n，则每个子节点的权重为1/n。

② 将深度为2的节点的权重平均分给它的子节点。

③ 迭代分配，直到树的叶子节点。

④ 对于叶子节点a和b，如果a等于b，那么a和b的相似度就是它们所分配的权重，若不等于，那么相似度为0。对于非叶子节点a和b，如果a等于b，那么a和b的相似度就是它们的子节点的权重总和，若不等于，那么相似度为0。

⑤ 两棵DOM树的相似度就是它们根节点的相似度。

具体的计算过程，以两个简单的HTML页面为例，两个HTML页面的源代码如图4所示。

图4 两个HTML页面源码图

首先构建两个页面对应的DOM树，DOM树的节点就是HTML页面的标签，文本内容统一用text表示，如图5所示。

图5 两个HTML页面的DOM树图

整个DOM树的权重设为1，从根节点HTML开始依次平均下发到叶子节点，整棵树的权重分配如图6所示。

图6 两棵DOM树的权重分配图

根节点的权重为1，根节点下有两个子节点，平均分配，每个子节点的权重为1/2。依次循环，直到整棵树分配完毕，可以看出，所有叶子节点的权重相加等于1，所以，我们通过比较同一深度叶子节点的相似度，得到父节点的权重，即：所有相同的子节点的权重总和。但是如果父节点不相同的话，权重则为0。如DOM树1中，a标签是img标签的父节点；DOM树2中center标签是img标签的父节点，虽然两个叶子节点一样，但是父节点是不一样的，所以a标签和center标签的相似度为0。

计算过程可以描述为：

similar(D1,D2)=similar(D1X11,D2X11)

similar(D1Xnm,D2Xnm)=

式中：D是DOM树，X11,X21,X22,…,Xnm是树的节点，n是树的深度，根节点的深度是1，X11代表根节点，m是节点的序列号，Xnm代表深度为n的第m个节点，DiXnm代表第i个树的Xnm节点，Num(n)代表深度为n的节点的数量。

2.3 聚 类

智能爬行算法的第三阶段就是以网页相似度为基础，利用聚合式层次聚类思想，将结构相似的网页聚为一组，取出一个作为代表URL。

因为聚类的集群数量不确定，聚类的密度也高，只确定相似性的阈值大小，所以该算法对类似于K-means等需要在开始就确定集群数量的算法不太适用；对于基于密度的方法同样需要在开始时设置两个参数(半径和最小数量)，但我们无法准确地对两个参数进行设置；基于网格的方法通常适用于多维数据；基于模型的方法则需要根据数据集的特征构建模型。综合以上问题，本文选择基于层次的聚类思想实现网页聚类。层次聚类有两种思想[12]，一种是所有的文档为一个类，之后去做切分，每次可能就会多一个类，叫做分割式聚类；另一种是聚合式聚类，开始每个数据都单独成一类，之后根据相似度去比对阈值，然后聚类。

利用聚合式层次聚类的思想，以上面的网页相似度为基础，将相似度大于阈值的网页所对应的URL放在一个子集中；通过一系列的计算得到若干个子集；再从每个子集中取出一个作为代表URL。

算法步骤如下：

第一步：聚类的对象是去重后的URL列表，设定一个初始相似度阈值T1。

第二步：在列表中随机选择一个URL作为初始点，并计算初始点与列表中其他URL的相似度。

第三步：若网页之间的相似度大于阈值T1，则将两个网页划分到一个子集中，并将此网页的URL在列表中置为0；若距离小于阈值T1，则继续从列表中取值，直到此网页和剩余非0网页比较结束。

第四步：重复第二步和第三步，直到列表为空。

第五步：取代表URL。

3 测 试

3.1 实验环境

智能爬行策略实验是在kali虚拟机、内存2 GB的硬件环境下进行的，使用Python语言实现。

3.2 实验内容

利用现有技术的深度爬虫和本文的智能爬虫分别对网站进行爬取。

3.3 爬取结果分析

分别对三个网站进行了测试，爬取结果如表2所示。

表2 深度爬虫和智能爬虫对比结果

用深度爬虫对http://www.freebuf.com网站进行爬取，结果可达14万个，而智能爬虫的爬取结果只有2 367个，聚类效果明显，可大量节省Web应用巡检系统的审计时间。其他网站类似，对https://www.douban.com网站，深度爬虫爬取结果为138 655个，而智能爬虫的爬取结果为3 856。对于https://www.shiyanlou.com网站，深度爬虫的爬取结果为1 764，智能爬虫的爬取结果为122。

对于http://www.freebuf.com网站的深度爬虫爬取结果进行分析，如表3所示。

表3 http://www.freebuf.com网站深度爬虫爬取结果分析

对于https://www.douban.com网站的深度爬虫爬取结果进行分析，如表4所示。

表4 https://www.douban.com网站深度爬虫爬取结果分析

由表3、表4可知类似的URL有很多，它们对应的网页大多是结构相似的。而智能爬虫可以有效地将这些结构相似的网页进行聚类，减少后续巡检系统的测试工作。

为了更清晰地展示两种爬虫爬取的结果，我们展示部分爬取结果，图7是深度爬虫的部分爬取结果图。图8是智能爬虫的部分结果图。

图7 深度爬虫部分爬取结果图

图8 智能爬虫部分爬取结果图

表5是智能爬行算法在聚类过程中比对的相似度值和聚类过程。

表5 智能爬行算法聚类过程分析

从表中可以看出，智能爬行算法在聚类过程中，先随机选择一个URL(表中为URL1)，与剩余的其他URL进行相似度比对，若相似度大于阈值(阈值=0.8)则聚为一组，表中URL1、URL2、URL3、URL7、URL8聚为一组。剩余的URL4、URL5、URL6再重复上面的步骤，直到所有URL都完成分组，表中URL4、URL5、URL6聚为一组。智能爬行算法最后会在每组中取一个代表URL，图8就是爬行的结果。

从图7和图8的对比可以看出，深度爬虫会将所有的网页爬取出来，存在很多结构相似的网页。而智能爬虫可以有效地将结构相似的网页聚为一类，只取代表URL进行后续检测，极大地提高了巡检系统的效率。

4 结 语

本文提出了一种智能爬行算法，在爬行过程中采用基于Rabin指纹算法对URL去重，检索速度快，效率高，且避免爬虫在爬行过程中浪费不必要的时间，甚至陷入死循环；在计算网页相似度前对网页进行预处理，构建DOM树，并统一用text表示文本，只保留网页标签，简化了网页，并通过平均分配权重的方法计算网页结构相似度，使网页相似度计算更高效；采用聚合式层次聚类算法将相似性网页聚为一组，提高了巡检系统的效率。本文解决了网页结构大量相似的问题，提高了安全巡检的效率，而且本方法思路简单、易于实现、通用性强，对结构相似的网页识别率高，提高了爬虫的精确度。