（信号与信息处理专业论文）web漏洞扫描系统中的智能爬虫技术研究.pdf

杭州电子科技大学硕士学位论文 摘要 针对w e b 安全问题，目前最常用的技术是采用w e b 漏洞扫描系统进行检测。网络爬虫是 w e b 漏洞扫描器重要组成部分，负责抓取站点的页面信息，为w e b 漏洞扫描器提供数据源及 扫描入口。网络爬虫是一个智能抓取网页的程序，论文主要研究网络爬虫技术。 所做的主要工作包括以下几部分： 1 ) 介绍了网络爬虫及其采用的爬行策略，论述了通用爬虫、聚集爬虫、深层爬虫三种典 型网络爬虫技术，详述了聚集爬虫使用的几个重要网页分析算法，分析了已有的基于爬虫技 术的w e b 漏洞扫描系统。 2 ) 通过对扫描对象特点的分析，提出了一种基于属性标签的w e b 数据挖掘的算法。即利 用网页的所有标签，构造带有属性标签的d o m 树；通过属性标签对子树做比较，发现标签 序列的重复模式；制定了三个规则排出干扰模式，找到数据区域，用向量记录包含有用数据 的重复模式；通过向量提取出数据记录。验证该方法有效性的实验对象是卓越网各类目，从 实验的数据可以发现，该方法可以卓越网页中提取出大约9 0 的数据，正确率与覆盖率都很 高。 3 ) 基于属性标签的w e b 数据挖掘的方法可以挖掘很多网页的重复数据，但对重复模式只 具备相似性不具备一致性的网页不起作用。针对这个问题，提出了一种基于编辑距离的w e b 数据挖掘算法。把树编辑距离转化为字符串编辑距离的计算，利用字符串编辑距离评价树的 相似度，进而找到网页中的重复模式，提取数据。通过针对不同重复模式特征的网页的实验 说明，该算法不仅能挖掘具有特征一的网页的数据，也能挖掘具有特征二的网页的数据，能 把2 0 个百度贴吧网页包含的1 0 0 0 个数据都提取出来。 4 ) 最后设计并实现了一个智能爬虫程序。详述了各个模块功能，绘制了各个模块的流程 图。根据流程图用j a v a 编程实现，并用实验证明模块达到预定的功能。该爬虫将论文提出的 新算法运用于爬虫策略制定，能很好地从交互性强的站点如电子商务、贴吧、论坛等抓取出 网页。 关键词：w e b 安全；网络爬虫；数据挖掘；重复模式；编辑距离 杭州电子科技人学硕十学位论文 a b s t r a c t a tp r e s e n t ，n em o s tc o m m o n l yu s e dt e c h n i q u ei st h eu s eo f w e b v u l n e r a b i l i t ys c a n n e rf o r d e t e c t i n gv u l n e r a b i l i t i e sa g a i n s tw e bs e c u r i t yp r o b l e m s w e bc r a w l e ri sa ni m p o r t a n tp a r to fw e b v u l n e r a b i l i t ys c a n n e r ，w h i c hi sr e s p o n s i b l ef o rg r a b b i n gt h ei n f o r m a t i o no ft h ew e b s i t e sp a g e st o p r o v i d ed a t as o u r c ea n ds c a n n i n ge n t r a n c ef o rw e _ bv u l n e r a b i l i t ys c a n n e r w e bc r a w l e ri sas m a r t p r o g r a mf o rc r a w l i n gp a g e s a n dt h i sp a p e rm a i n l yr e s e a r c h e sw e bc r a w l e rt e c h n o l o g y t h em a j o rw o r kd o n ei n c l u d e ss e v e r a la s p e c t sa sf o l l o w s ： f i r s t l y ，t h r e et y p i c a lw e bc r a w l e r s a r es t u d i e da n dt h e i r c r a w l i n gs t r a t e g i e s a r e l e a r n e d s e v e r a li m p o r t a n ta l g o r i t h m sa r ed i s c u s s e d ，t h ee x i s t i n gw e b v u l n e r a b i l i t ys c a n n e r sb a s e d o nw e bc r a w l e rt e c h n o l o g ya r ea n a l y z e d ，f o u rf e a t u r e so f t h es c a n n i n go b j e c ta l es u m m a r i z e d s e c o n d l y ，am e t h o dt oe x t r a c tt h ew e bd a t ab a s e do na t t r i b u t et a go fw e b p a g e st h r o u g ht h e a n a l y s i so ft h ef e a t u r e so fs c a n n i n go b j e c t i tu s e st a g so fw e b p a g e st oc o n s t r u c tad o m t r e ew i t h t h ea t t r i b u t e t a g ；c h i l dt r e e sa r ec o m p a r e db ya t t r i b u t et a g st of i n dt a gs e q u e n c e sr e p e a t i v ep a t t e r n s ； m a k i n gt h r e er u l e si st or e m o v ed i s t r u b e dp a a e r n sa n di d e n t i f yd a t ar e g i o n s ，a n dt h ev e c t o ri su s e d t or e c o r dr e p e a t i v ep a t t e r n ；d a t a sa r ee x t r a c t e dt h r o u g ht h ev e c t o r e x p e r i m e n t sa r ed o n et ov e r i f y t h ee f f e c t i v e n e s so f t h em e t h o d ，a n dt h ee x p e r i m e n to b j e c ti sc o m m o d i t i e so f a m a z o n a c c o r d i n gt o t h ee x p e r i m e n td a t a ，t h i sm e t h o dc a ne x t r a c ta b o u t9 0 o ft h ed a t ai na m a z o nw e b p a g e s b o t h a c c u r a c ya n dc o v e r a g e a r e v e r yh i g h t h i r d l y ，t h em e t h o dt oe x t r a c tt h ew e bd a t ab a s e do na t t r i b u t et a go f w e bp a g e sc a ne x t r a c tt h e d a t af r o mm o s tw e b p a g e s ，b u ti td o e s n tw o r kw h e nr e p e a t i v ep a a e mi sj u s ts i m i l a rb u tn o t s a m e t h ew e bd a t am i m n g a l g o r i t h mb a s e do ne d i td i s t a n c ei sp r o p o s e dt os o l v et h i sp r o b l e m i t c o m p u t e st r e ee d i td i s t a n c et h r o u g hs t r i n ge d i td i s t a n c e ，u s e ss t r i n ge d i td i s t a n c et oa c c e s ss i m i l a r i t y b e t w e e no n et r e ea n da n o t h e r ，t h e nf i n d sr e p e a t i v ep a t t e r n si nw e b p a g e sa n dm i n e sd a t a s i ti s d e m o n s t r a t e db yt h ee x p e r i m e n t sd o n ef o rw e b p a g e sw i t ht h ed i f f e r e n tf e a t u r e so fr e p e a t i v e p a t t e r n ，t h a tt h i sa l g o r i t h mn o to n l ym i n e st h ed a t af r o mw e b p a g e so ff e a t r u eo n eb u ta l s ot h ed a t a f r o mw e b p a g e so f f e a t r u et w o i te x t r a c e sa l lo f t h e1 0 0 0d a t a sf r o m2 0b a i d u t i e b aw e b p a g e s f i n a l l y ，a l li n t e l l i g e n tc r a w l e ri sd e s i g n e da n di m p l e m e n t e d i t sm o d u l e sa r ed e s c r i b e da n dt h e f l o wc h a r to fe a c hm o d u l ei sd r a w e d n ec r a w l e ri sp r o g r a m e di nj a v aa n de x p e r i m e n t s p r o v et h a t e v e r ym o d u l et oa c h i e v et h ei n t e n d e df u n c t i o n t h ec r a w l e r ，w h i c ha p p l i e sn e wa l g o r i t h m s p r o p o s e db yt h i sp a p e rt ot h ef o r m u l a t i o no fc r a w l i n gs t r a t e g y ，c a ng r a bw e b p a g e sw e l lf r o m w e b s i t e sw i t hs t r o n gi n t e r a c t i v i t ys u c ha se l e c t r o n i cc o m m e r c ew e b s i t e s ，t i e b a ，b b sa n ds oo n k e yw o r d s ：w e bs e c u r i t y ；w e bc r a w l e r ；d a t am i n i n g ；r e p e a t i v ep a t t e m ；e d i td i s t a n c e u 杭州电子科技大学硕士学位论文 1 1 选题的背景 第一章绪论 1 9 9 7 年，w 曲2 0 概念首次由d a l ed o u g h e r t y 和c r a i gc l i n e 在共同合作的b r a i ns t o r m i n g 会议上提出。w e b2 0 不是一个技术的标准，它仅仅是一个用来阐述技术转变的术语，是一种 新的互联网方式，通过w e b 应用促进网络上人与人间的信息交换和协同合作，其模式更加以 用户为中心【l 】。2 0 0 4 年以后，人们迎来了真正的w e b2 0 时代，互联网上出现了很多w e b2 0 应用技术，例如博客、r s s 、社交网络服务、即时通信、百科全书等，新近出现的a j a x 技术 也是w e b2 0 应用的新技术之一。各种w e b2 0 应用技术的出现极大地改变了人们的上网方式。 在w e b1 0 模式下，网站把所有信息都保存在服务器端，在互联网上发布，用户通过浏览器 获取服务器端信息，这是一种单向的信息发布模式。与w e b1 0 不同，w e b2 0 更加注重用户 的交互性，用户既是网页内容的浏览者也是网页内容的提供者，用户将有更多机会参与到创 造网页内容当中。 w e b2 0 应用的交互性丰富了人们网上冲浪的方式，使人们上网更加人性化，然而，由此 带来的w e b 安全问题也越来越型2 1 。w e b2 0 应用技术大大增加了w e b 应用程序的安全隐患， 它使程序开发更加复杂和繁琐，也使x s s 、s q l 注入等攻击变得更加容易。 o w a s p ( o p e l lw e ba p p l i c a t i o ns e c u r i t yp r o j e c t ) 是世界上权威的非营利性w e b 应用安全 组织，它提供有关计算机和互联网应用程序的公正、实际、有成本效益的信息，致力于w e b 应用安全研究。o w a s p 最知名的项目之珈w a s pt o p1 0 项目，它列出1 0 项最严重的 w 曲应用程序安全风险，供网站安全评估人员参考，最新一次发布的版本是2 0 1 0 年版本1 3 训。 表1 1 对应着2 0 1 0 年与2 0 0 7 年颁布的1 0 大安全风险。从表中可以看到，和2 0 0 7 版本相比， 有的风险排序上升，有的下降，还有新增加的风险，排在前两位的依然是注入漏洞1 5 7 j 与跨站 脚本漏洞博d 。 伴随着w e b2 0 时代一系列新型互联网产品的出现，w e b 安全问题同益凸显。黑客利用 网站操作系统漏洞和w e b 服务程序漏洞等得到w e b 服务器的控制权限，轻则篡改网页内容， 重则窃取重要内部数据，更为严重的则是在网页中植入恶意代码，使得网站访问者受到侵害。 人们开始关注w e b 应用安全问题，寻找解决方案来提高w e b 应用安全。在这种背景下，人们 开发了各种各样的w 曲漏洞扫描工具，用以检测w e b 应用程序漏洞玉1 3 j 。 w e b 漏洞扫描器通过网络爬虫抓取u r l 链接，分析站点信息，找出所有站点中的相关文 件和可输入点，并对这些发现的网页对象发起大量渗透测试。渗透测试过程可以对w e b 服务 器的多种项目进行测试，根据不同网站安全类型做针对性的检测，例如跨站脚本测试、s q l 注入测试、会话管理测试、认证测试、数据验证测试等。抓取过程在扫描过程中是至关重要 杭州电子科技大学硕士学位论文 的一步，w e b 漏洞扫描器需要抓取站点的所有对象和输入点，这一关键步骤由网络爬虫来实 现。 表1 12 0 1 0 与2 0 0 7 十大安全威胁对比 o w a s p t o p1 0 - 2 0 1 0 o w a s p t o p10 2 0 0 7 a 1 注入 跨站脚本( ) 【s s ) a 2 跨站脚本( x s s ) 注入漏洞 a 3 失效的身份认证和会话管理 恶意文件执行 a 4 不安全的直接对象引用不安全的直接对象引用 a 5 跨站请求伪造( c s r f )跨站请求伪造( c s r f ) a 6 安全配置错误 信息泄露和不恰当的错误处理 a 7 不安全的加密存储失效的身份认证和会话管理 a 8 没有限制u r l 访问不安全的加密存储 a 9 传输层保护不足 不安全的通信 a 1 0未验证的重定向和转发 没有限制u r l 访问 网络爬虫是w e b 漏洞扫描器重要组成部分，负责抓取站点的页面信息，为w e b 漏洞扫描 器的渗透测试过程提供数据源及扫描入口。网络爬虫是一个智能抓取网页的程序，在队列中 事先给定一些种子链接，网络爬虫通过链接对应的页面抓取新链接放到队列中，继续抓取更 多的链接，重复这一周而复始的过程，直到满足一定条件为止。网络爬虫抓取每一个页面后 将采取算法分析页面内容，提取有用的u r l 链接供w e b 漏洞扫描器测试检测是否存在安全 漏洞。可以说，网络爬虫的性能好坏直接决定w e b 漏洞扫描系统的好坏。论文主要研究w e b 漏洞扫描系统中的网络爬虫技术。 1 2 国内外研究现状及意义 1 2 1 研究现状 w e b 漏洞扫描器的历史要追溯到2 0 世纪9 0 年代，当时i n t e r n e t 刚刚起步并在各大学校 园中得到迅速发展，c e r t 也很快建立并运作起来，g o p h e r 在万维网中仍然处于研究阶段。 1 9 9 2 年，计算机科学系的学生c h r i sk l a u s 开发了第一个w e b 漏洞扫描工具一n t e n l e t s e c u r i t ys c a n n e r ( i s s ) ，该工具可以远程探测u n i x 系统的各种通用漏洞【1 4 】。i s s 是i n t e m e t 上 用来进行远程安全评估扫描的最早的工具之一，它能辨别出几十种常见的安全漏洞，并将这 些漏洞做上标记以便日后解决。虽然有些人担心该工具的强大功能可能会被用于非法目的， 但多数管理员对这个工具却很欢迎。 几年以后，d a nf a r m e r 和w i e t s ev e n e m a 编写了一个类似的工具，称为s a t a n ( s e c u r i t y a d m i n i s t r a t o r t o o lf o r a n a l y z i n g n e t w o r k s ，系统管理员网络分析工具) 【i5 1 。s a t a n 可以帮助 系统管理员自动地扫描系统，通过网络发现各种已知的漏洞。s a t a n 由p e r l 语言编写，通过 浏览器提供用户界面，它不仅报告漏洞，也能搜集网络信息，如主机是哪种类型的及提供什 么样的服务。s a t a n 本质上与i s s 相同，但有一些优点，即具有一个更加成熟的扫描引擎、 2 杭州电子科技人学硕士学位论文 基于w e b 的界面，并能进行分类检查。然而与i s s 不同的是，s a t a n 的发布引起了媒体的极 大关注：1 9 9 5 年4 月该产品发布时，时代杂志发表了一篇关于s a t a n 和d a nf a r m e r 的 文章，c e r t 还评论了该工具的能力。许多人甚至担心s a t a n 的发布会给i n t e r n e t 带来混乱。 从那时起，安全评估工具开始不断地发展并日趋成熟。迄今为止，业晁已经出现了数百 种扫描器，每种都有其优点，也有其弱点，但自从i s s 和s a t a n 问世以来，相关的理论和概 念却没有改变多少。 1 9 9 8 年，n e s s u s 的创办人r e n a u dd e r a i s o n 展开了一项名为“n e s s u s 的计划，其计划 目的是希望能为因特网社群提供一个免费、威力强大、更新频繁并简易使用的远端系统安全 扫描程序【1 6 】。n e s s u s 很快成为了漏洞扫描领域的l i n u x 。在开放源代码运动的推动下，n e s s u s 从数年前名不见经传的小工具发展成为可以与商业工具相媲美的著名扫描器。n e s s u s 还引进 了一种可扩展的插件模型，使人们可以随意添加扫描模块，这也给了n e s s u s 足够的发展空间， 它无法完成的检查可以由别人按照自己的需要自由进行补充、创建。n e s s u s 采用了一种控制 引擎模型，在这种模型中，控制程序可以与扫描引擎驻留在同一台机器上，也可以不在同一 台机器上。这种分布式的结构提供了极大的弹性，身边即使没有扫描引擎也可以完成漏洞扫 描工作。n e s s u s 已经探测出了5 0 0 多种漏洞，其中有些漏洞连商业工具也无法扫描出来。 自开源软件n e s s u s 出现后，又涌现了大批的开源漏洞扫描工具。比较著名的有n i k t o ， n i k t o 由c h r i ss u l l o 与d a v i dl o d g e 两人共同开发，能在1 2 0 0 多种过时版本和2 7 0 多种特定 版本服务器上扫描出6 4 0 0 多种有潜在危险的文件或c g i 及其它问题，可以扫描指定主机的 w e b 类型、主机名、特定目录、c o o k i e 、特定c g i 漏洞、返回主机允许的h t t p 模式等【l 7 1 。 另一款开源工具w i k t o ，它和n i k t o 类似，但是添加了很多其它功能，拥有一个整合了g o o g l e 的后台发掘器【l 引。w i k t o 由c 样编写，需要n e t 框架才能正常工作。w h i s k e r 同样是开源的工 具，它是基于l i b w h i s k e r 的扫描器。 进入2 1 世纪以后，有很多的公司和组织参与到w 曲漏洞扫描工具的开发，他们开发了 很多商业级扫描工具。r a t p r o x y 是g o o g l e 公司的工程师迈克尔扎勒维斯基( m l c h a lz a l e w s k i ) 开发的网站安全检测工具，它能够检测x s s 、c s r f 等网站安全问题，用于评估基于w e b 的 应用程序的安全性，于2 0 0 8 年发布i l 圳。s k i p f i s h 是扎勒维斯基开发的另一款网站安全检测工具， 于2 0 1 0 年发布【2 们。它完全实现了全自动化操作，所以不需要人工干预，这一点上比r a t p r o x y 要好用一些，当然在功能上也强大更多了。s k i p f i s h 通过h r r p 协议处理且占用较低的c p u 资源，因此它的运行速度比较快，每秒钟可以轻松处理2 0 0 0 个请求，采用先进的逻辑安全， 这将有助于减小产生误报的可能性。由o w a s p 推出的扫描工具w e b s c a r a b 主要是一款代理 软件【2 1 】。w e b s c a r a b 的h t r p 代理提供了预期的功能( 包括h t t p s 拦截，不过和p a r o s 一 样有认证报警) 。w e b s c a r a b 也提供了一些花哨的功能，比如s s l 客户认证支持，十六进制或 u r l 编码参数的解码，内置的会话i d 分析和一键式“完成该会话以增加效率等。就基本 功能而言，w e b s c a r a b 和p a r o s 差不多，但w e b s c a r a b 为更懂技术的用户提供了更多的功能， 并提供了对隐藏的底层更多的访问。 3 杭州电子科技大学硕士学位论文 国外有更多的公司和个人投入精力来开发w e b 漏洞扫描工具，相比国外，国内参与研究 w e b 漏洞扫描工具的公司与个人要少很多。比较有名的工具主要是由几个安全公司开发的产 品，如杭州安恒信息技术有限公司开发的明鉴w e b 应用弱点扫描器( m a t r i x a y ) 2 2 】，绿盟 科技自主研发了绿盟极光远程安全评估系统【2 3 1 ，及北京智恒联盟科技有限公司开发的一款可 以检测多种攻击的产品w e b p e c k e l l 2 4 1 。 1 2 2 研究意义 为了应对w e b 越来越严重的安全问题，无论是信息安全公司，其他互联网公司，还是一 些爱好者个人都开发出了各种不同的w e b 漏洞扫描工具。网络爬虫是w e b 漏洞扫描系统中必 不可少的一部分，网络爬虫的性能好坏直接决定w e b 漏洞扫描系统的好坏。 网络爬虫技术最先在搜索引擎中使用，用来从w o r l dw i d ew e b 上抓取网页，它是搜索引 擎中一个重要的组成部分。人们逐渐把网络爬虫应用到w e b 漏洞扫描系统中，并成了扫描系 统不可缺少的一部分。有w e b 漏洞扫描系统的开发者就是来自商用搜索引擎公司，比如 r a t p r o x y 与s k i p f i s h 开发者是谷歌公司的一个工程师。w 曲漏洞扫描系统用网络爬虫抓取网 页中的u r l 地址，对u r l 进行渗透测试，u r l 对应一个网页，所以也是对网页进行渗透测 试，发现其中的漏洞。搜索引擎与w e b 漏洞扫描系统都是通过网络爬虫在给定种子页面后抓 取更多的网页。但它们有一个区别，搜索引擎需要的是网页包含的内容，抓取后通过某种方 式保存下来，而w e b 漏洞扫描系统是对网页进行测试，保存测试的结果。 w e b 漏洞扫描系统与搜索引擎在使用网络爬虫的原理上相同，但它们由于目的不同，对 网络爬虫技术的需求也不一样。本文研究的意义在于，通过已有的网络爬虫技术的研究，找 到一种符合w e b 漏洞扫描系统需求的网络爬虫，花费较小的代价，设计一种性能优秀的网络 爬虫，用于w e b 漏洞扫描系统。 1 3 论文的主要内容与组织结构 在论文主要研究w e b 漏洞扫描系统中的智能爬虫技术，探索符合w e b 漏洞扫描系统需求 的网络爬虫。主要内容如下： 1 介绍了网络爬虫的基本概念及其采用的爬行策略作，分别论述了通用爬虫、聚集爬虫、 深层爬虫三种典型网络爬虫技术，详述了聚集爬虫使用的几个重要网页分析算法，分析了已 有的基于爬虫技术的w 曲漏洞扫描系统。 2 根据扫描对象的特点，提出了一种基于属性标签的w e b 数据挖掘的方法，用于挖掘 网页中的重复数据，提取u r l 。利用网页的所有标签，构造带有属性标签的d o m 树；通过 属性标签对子树做比较，发现t a g 序列的重复模式；制定了三个规则分别是t a g 个数、文本标 签、链接数，排出干扰模式，找到数据区域，用向量记录包含有用数据的重复模式；通过向 量提取出数据记录。通过实验验证该方法的有效性，从实验的数据可以发现，该方法可以卓 4 杭州电子科技大学硕士学位论文 越网页中提取出大约9 0 的数据，有很高的正确率与覆盖率。该部分研究成果总结为论文基 于属性标签的w e b 数据挖掘，已被计算机应用与软件录用。 3 基于属性标签的w e b 数据挖掘的方法不能挖掘相似性重复模式，提出了基于编辑距 离的w e b 数据挖掘。基于属性标签的w e b 数据挖掘的方法对很多网页都有效，但对一些重复 模式只具备相似性不具备完全一致性的网页不起作用，如百度贴吧就具备这个特征。为了解 决这个问题，把编辑距离应用于w e b 数据挖掘，提出了一种基于编辑距离的w e b 数据挖掘算 法。把树编辑距离转化为字符串编辑距离的计算，利用字符串编辑距离评价树的相似度，进 而找到网页中的重复模式，提取数据。通过针对不同重复模式特征的网页的实验说明，基于 编辑距离的w e b 数据挖掘算法不仅能挖掘具有特征一的网页的数据，也能挖掘具有特征二的 网页的数据。基于编辑距离的w e b 数据挖掘算法对于具有特征一与特征二的网页的数据都能 提取，解决了基于属性标签的w e b 数据挖掘的方法的问题。有很高的正确率与覆盖率。该部 分研究成果总结为论文基于编辑距离的w e b 数据挖掘，已投稿于计算机工程与科学。 4 分析了树编辑距离算法与字符串编辑距离算法，比较了两算法的优劣。树编辑距离算 法更加精确，但时间复杂度与空间复杂度都很高，而字符串编辑距离算法时间复杂度与空间 复杂度低的多。选择字符串编辑距离用于计算重复模式的相似度，在网页结构的比较中可以 取得很好的效果。 5 设计实现了一个智能爬虫程序。把两个算法应用于网络爬虫，利用它们分析网页中的 u r l ，并把需要w e b 漏洞系统测试的u r l 抓取出来，设计了智能爬虫系统的框架及各个模 块。根据流程图用j a v a 编程实现，并用实验证明模块达到预定的功能。该爬虫对交互性强的 网页有很好的抓取效果。 论文共分六个章节，组织结构如下： 第二章介绍了网络爬虫的相关技术，总结了w e b 漏洞扫描系统扫描的对象的四个特点。 第三章探索了符合扫描系统需求的智能爬虫策略，提出了基于属性标签的w e b 数据挖掘 算法。 第四章提出了基于编辑距离的w e b 数据挖掘算法，该方法可以挖掘网页相似的重复模式。 第五章设计并实现了一个智能爬虫，验证了提出的算法的有效性。 第六章为总结与展望。 杭州电子科技大学硕士学位论文 2 1 网络爬虫基本概念 第二章网络爬虫相关技术 网络爬虫( w e bc r a w l e r ) 又称为网络蜘蛛( w e bs p i d e r ) ，网络机器人( w e br o b o t ) ，是一个智 能抓取网页的程序，网络爬虫最初设计用于搜索引擎中，成为搜索引擎不可缺少的组成部分 2 5 - 2 8 】。给定一些种子链接放到爬虫队列中，网络爬虫通过链接对应的页面抓取新链接放到队 列中，继续抓取更多的链接，重复这一周而复始的过程，直到满足爬虫设定的终止条件为止。 如果把网页看成一个点，一个网站由众多网页组成，相当于很多点的集合，网站的内部 网页相互链接，网站之间也通过彼此指向的链接联系在起，网页与网页之间又指向对方， 那么w e b 可以看成是一个巨大的有向图，网络爬虫则通过图遍历算法爬行图中的每个点。如 图2 1 所示，是一个把w e b 当作图的例子，假设爬虫已经爬取了页面a 、页面e ，现在如何决 定访问下一个页面? a 可以链接到b 、c 、e ，而e 可以链接到d 和f ，爬虫下一个对象候选者 有b 、c 、d 、f 如何选择下一个页面取决于爬虫事先制定的策略。 2 2 网页抓取策略 图2 1w e b 看作图的例子 类似图的遍历方式，网页的抓取策略可以分为三种，即深度优先策略( d e p t hf i r s t ) 、广度 优先策略( b r e a d c hf i r s t ) 和最佳优先策略( b e s tf i r s t ) 2 9 1 。 2 2 1 深度优先策略 深度优先是从开始顶点起，沿着一条路径尽可能的向前搜索，直到不能再向前所有邻接 节点都有被访问过时就往回退，也称为回溯。回溯时沿着与访问相反的方向走，当回到仍有 未被访问的邻接点的一个顶点是，把这个点当成起始点，再找一条路径继续向前搜索，反复 6 杭州电子科技人学硕士学位论文 这个过程，直到所有顶点都被访问过为止。 深度优先策略是一种在开发爬虫早期使用较多的方法【3 0 1 。它的目的是要达到被搜索结构 的叶结点( 即那些不包含任何超链接的h t m l 文件) 。优点是能遍历整个站点或深层嵌套的 文档集合，缺点是因为w e b 链接错综复杂，有可能从某条路径进去后再也出不来的情况发生。 所以现在的网络爬虫不大使用深度优先策略。 2 2 2 广度优先策略 广度优先又称为宽度优先，类似于树的层次遍历。广度优先首先将起始顶点作为候选顶 点，访问候选顶点，然后与候选顶点相邻接的尚未被访问的所有顶点又作为下一批候选顶点， 继续这个过程，接着访问下一个候选顶点，与该候选顶点相邻接的尚未被访问的所有顶点再 作为下一批的候选顶点，直到访问完所有的顶点。 在给一个或几个u r l 后，完成初始页面的抓取，提取出新的u r l ，新的u r l 不分先后 顺序继续抓取下一页面。广度优先对u r l 没有选择，导致抓取的网页很多是无用的，会使网 络爬虫的效率变的低下。综合性搜索引擎为了网页覆盖率会采取这种策略。 2 2 3 最佳优先策略 最佳优先策略更像是在广度优先策略基础上改进的结果【3 1 1 。最佳优先对初始u r l 完成抓 取后提取出u r l ，但不是把所有u r l 都放入队列中作为候选u r l 等候下载，而是按照某种 分析算法，预测新的u r l 是否与想要获得的主题相关，然后赋给每个候选u r l 一个权值， 从高到低排列，选取权值高的u r l 放入下载队列中，继续这一过程直到达到停止条件。最佳 优先策略能够很好的排除爬行过程中的无用u r l ，提高爬虫的效率，让爬虫抓取的网页正确 率大大提高。爬虫用到的网页分析算法的性能优劣直接决定了爬虫的效率高低，差的分析算 法导致错误过滤有多有用的网页。 2 3 网络爬虫分类 按照爬虫的功能不同、结构差异、爬行策略以及实现技术的不同，网络爬虫可以划分为 三大类：通用爬虫( g e n e r a lc r a w l e r ) 、聚焦爬虫( f o c u s e dc r a w l e r ) 、深度爬虫( d e e pc r a w l e r ) 。 2 3 1 通用爬虫 通用爬虫采用广度优先策略【3 2 彤1 ，从给定的一个或几个页面开始，完成初始页面的抓取， 提取出新的u r l ，新的u r l 不分先后顺序放入队列中继续抓取，一直向整个w e b 扩展，直 到满足预设的停止条件为止。通用爬虫采用的策略对u r l 没有进行分析，导致抓取的网页很 多是无用的，使网络爬虫的效率下降。但通用爬虫的价值还是很高的，很多商用搜索引擎都 7 杭州电子科技大学硕士学位论文 会使用它，比如著名的搜索引擎谷歌、雅虎、百度等。综合性搜索引擎为了使搜索的结果更 加全面，网页覆盖率更高，会牺牲掉网络爬虫的一些效率，通过使用内存大、存储空间大、 运算快的计算机来弥补效率的不足，并使用分布式计算、增加爬虫数量来提高效率。 通用爬虫的体系结构如图2 2 所示，主要有有四部分：初始u r l 、u r l 队列、爬行模块、 重复链接过滤模块。爬行模块抓取给定的初始u r l 对应的页面，重复链接过滤模块负责把访 问过的链接过滤掉，过滤后的u r l 添加到u r l 队列中，重复这一过程。 图2 2 通用爬虫体系结构 第一个爬虫出现时间大约在1 9 9 3 年，它的结构是非常简单的，简单地使用广度优先策略 抓取网页，主要因为当时互联网的规模非常小。它就是一个通用爬虫。在1 9 9 3 年末到1 9 9 4 年初，w e b 的整体规模还很小，主要是美国几个研究所和教育机构建立的有限的站点，站点 总数大约6 0 0 0 个。由于站点数量有限，网络爬虫对爬行策略没有做很多的研究，但足以抓取 到所有站点的页面。 第一个爬虫正常运行6 个月后出现了问题。随着w e b 的爆炸式增长，爬虫出现了很多问 题：容错能力差，更新的规模赶不上w e b 的增长，不方便监管，更新的速度不及时。后来的 网络爬虫都注意在爬行策略的选择上更加谨慎。 2 3 2 聚焦爬虫 聚焦爬虫，与主题爬虫是同一个概念，抓取网页后并提取出网页包含的新u r l ，它不会 立即放入到队列中，而是经过某种网页分析算法对链接进行分析，过滤掉与预设主题不相关 的网页，选择与预设主题相关度高的网页继续抓取【3 6 删。聚焦爬虫使用的是最佳优先策略。 由于对网页进行了提取过滤，下载的网页都是针对主题的相关网页，可以避免下载无用网页 带来的网络时延，减少存储无用网页需要的硬盘空间，使爬行的效率大大提高。如图2 3 所 示，聚焦爬虫相比通用爬虫，增加了网页分析模块，包括初始u r l 、u r l 队列、爬行模块、 网页分析模块、重复链接过滤模块。 聚焦爬虫的性能取决于网页分析算法，网页分析算法不好将导致不能很好的过滤无用网 页或与主题不相关的网页，过滤掉与主题相关的网页或过滤后的网页抓取后仍然是无用的网 8 杭州电子科技大学硕七学位论文 页。设计一个性能优越的网页分析算法、聚焦爬虫的爬行策略选择对聚焦爬虫至关重要。 图2 3 聚焦爬虫体系结构 ( 1 ) 基于超链接评价的策略 1 ) p a g e r a n k 算法 p a g e r a n k 是计算网页重要性的算法，而作为网页排名的要素之一，拉里佩奇( l a r r yp a g e ) 和谢尔盖布林于1 9 9 8 年在斯坦福大学发明了这项技术【4 l 】。 p a g e r a n k 是基于图的数学算法，它把整个互联网当成一个巨大的w e b 图，所有页面看成 图的节点，相互指引的超链接看成图的边。p a g e r a n k 值表明一个网页的重要程度。到一个页 面的超链接相当于对该页面投票，一个有很多高等级链入页面的页面会有较高的p a g e r a n k 值，反之，没有任何链入页面的页面p a g e r a n k 值为零。 p a g e r a n k 值计算公式如下： p a g e r a n k ( p ) = ( 1 - q 卜q 姜掣 ( 2 1 ) p l ，p 2 ，p n 是链入p 的页面，n 是链入p 页面的数量，l ( p i ) 是p i 链出页面的数量，q 是阻尼系数，定义为用户不断随机点击链接的概率，表示对用户访问网页行为的预测，一般 取值为0 8 5 。在计算的过程中，首先给所有网页赋一个相同的初始值，通过公式2 1 计算各 个网页的p a g e r a n k 值，需要公式反复迭代，直到每个网页的p a g e r a n k 值趋于平稳。 这个公式引入了随机浏览的概念，即有人随机打开一些页面，点击一些链接。一个页面 的p a g e r a n k 值也影响了它被随机浏览的概率。为了便于理解，这里假设上网者不断点网页上 的链接，最终到了一个没有任何链出页面的网页，这时候上网者会随机到另外的网页开始浏 览。 2 ) h i t s 算法 h i t s 算法是在1 9 9 8 年由由康奈尔大学的j o nk l e i n b e r g 提出的一种分析网页重要性的算 法【4 2 】。h i t s 算法最重要的两个概念是内容权威度( a u t h o r i t y ) 和链接权威度( h u b ) 。将每 一个网页对应的内容权威度和链接权威度区别对待，在对网页的a u t h o r i t y 与h u b 分别作出评 价，再综合考虑两个方面来确定网页的重要性。a u t h o r i t y 值大小与网页提供内容信息的质量 9 杭州电子科技人学硕士学位论文 相关，网页被越多网页所指向( 入度) ，其a u t h o r i t y 值越大；h u b 值大小与网页提供的超链 接页面的质量相关，网页指向越多高质量页面的网页( 出度) ，其h u b 值越大。 对于所有网页p ，a u t h o r i t y 值计算如下： j l a u t h ( p ) 5 h u b ( p i )( 2 2 ) i s l 其中p i 指向页面p 的一个页面，n 表示指向页面p 所有页面的总数，页面p 的a u t h o r i t y 值等于指向p 的所有页面的h u b 值之和。 对于所有网页p ，h u b 值计算如下： j l h u b ( p ) 2 a u t h ( p i )( 2 - 3 ) i - l 其中页面p i 表示被页面p 指向的页面中的一个，n 表示所有被p 指向的页面总数，页面p 的h u b 值等于p 指向的所有页面的a u t h o r i t y 值之和。 在计算的初始化阶段，令a u t h ( p ) = l ，h u b ( p ) = 1 ，为了计算a u t h o r i t y 值与h u b 值，需要 反复利用上面两个公式进行迭代，k 次算法就是利用公式迭代了k 次计算出的结果。 这两种基于超链接评价的策略是很典型的两种，其他相似算法都是在两种算法的基础上 改进而来的。基于超链接评价的策略的缺点是忽略了网页内容与主题的相关度，纯粹在超链 接上增加考察的权值，权值越大页面的重要程度越高。 ( 2 ) 基于页面内容评价的策略 1 ) f i s hs e a r c h f i s hs e a r c h 算法是由d eb r a 与p o s t 提出的动态搜索页面的算法，类似于在深度优先策略 基础上加以改进【4 3 1 。深度优先可能导致从一条路径进去以后就陷进去的危险，f i s hs e a r c h 算 法则j 下好解决了陷进去后如何退出来的问题。 f i s hs e a r c h 算法又叫鱼群算法，就像鱼群在觅食一样，哪里食物丰富，鱼群就往哪里游， 当食物被吃光了，鱼群游到其他地方继续觅食。给定一些种子链接，相当于鱼群的初始“食物”， f i s hs e a r c h 算法以深度优先方式找到更多链接，这些链接有的与主题相关，是鱼群的“新食物”， 鱼群觅食“新食物”发展壮大，继续往深度方向挖掘链接；有些链接与主题不相关，证明不是 鱼群的“食物”，鱼群将放弃这些链接；沿着一条路径进行深度搜索，某些链接开始的阶段与 主题相关，但经过几次链接后与主题不相关了，鱼群就会离开这条路径，这样避免了陷入的 问题。 f i s hs e a r c h 算法的关键是动态的维护队列中的u r l 优先级，考虑了网页与主题的相关度。 2 ) s h a r ks e a r c h f i s hs e a r c h 算法在深度搜索方向上有它的优势，能挖掘深度的相关主题页面，在不相关 页面的路径上可以及时跳出。但它还是有不足，在时问限制的情况下，它不能挖掘足够多的 相关主题页面。1 9 9 8 年m i c h a e lh c r s o v i c i 等人提出了一种改进算法，即s h a r ks e a r c h