点击上方“程序员大咖”,选择“置顶公众号”
关键时刻,第一时间送达!
以前在做漏洞Fuzz爬虫时,曾做过URL去重相关的工作,当时是参考了seay法师的文章以及网上零碎的一些资料,感觉做的很简单。近来又遇到相关问题,于是乎有了再次改进算法的念头。
首先,针对URL本身的去重,可以直接对整块URL进行处理。在参考网上的一些文章时,发现它们大多采用了 URL 压缩存储的方法。不过使用这些算法在数据量较大的时候,能大幅减小存储的空间:
基于磁盘的顺序存储。
基于Hash算法的存储。
基于MD5压缩映射的存储。
基于嵌入式Berkeley DB的存储。
基于布隆过滤器(Bloom Filter)的存储。
对于 URL 直接去重,主要涉及的是存储优化方面,对于本文不是重点,这里不再细说。
而对于 URL 逻辑上的去重,则需要更多地追求数据的可用性,这是做测试工作需要去考量的。
这里先给出 seay 文章中的相似度去重算法,大致是下面这样的:
def urlsimilar(url): hash_size=199999 tmp=urlparse.urlparse(url) scheme=tmp[0] netloc=tmp[1] path=tmp[2][1:] query=tmp[4] #First get tail if len(path.split('/'))>1: tail=path.split('/')[-1].split('.')[-1] #print tail elif len(path.split('/'))==1: tail=path else: tail='1' #Second get path_length path_length=len(path.split('/'))-1 #Third get directy list except last path_list=path.split('/')[:-1]+[tail] #Fourth hash path_value=0 for i in range(path_length+1): if path_length-i==0: path_value+=hash(path_list[path_length-i])%98765 else: path_value+=len(path_list[path_length-i])*(10**(i+1)) #get host hash value netloc_value=hash(hashlib.new("md5",netloc).hexdigest())%hash_size url_value=hash(hashlib.new("md5",str(path_value+netloc_value)).hexdigest())%hash_size return url_value
这段函数的大概作用是,最后它会根据算法返回一个hash值,这个hash值也就是该URL的hash相似度。如果两个URL计算出的hash值最后比较相等,我们则可以判断两个URL是具有较高的相似度的。
但是这个函数应该是seay举例时随手提出的(这里强调下,免得被喷,后文不再细说),只是简单做了demo,并没有进行细化检验。在比较粗糙的情况下,该算法确实能剔除一些简单的参数重复的情况,但一旦参数复杂或者url不规范,是不太能很好的进行去重的。
那么在针对URL获取的过程中,我们还可以做的小优化有哪些呢?
日期时间命名
首先,我们可以根据日期来去重。我们知道,在爬取一些Blog和和门户等系统时,经常会遇到以日期命名的目录。
这些目录大概归纳起来,存在类似下面的形式:
2010-11-11
10-11-11
20101111
当然,还有些文件会以时间+随机值命名,也可能是用unix时间戳命名,这些可能是根据上传和编辑时间来定义的。
笔者建议是,使用redis或者memcache之类等缓存型数据库,将其直接存储;或者在数据量较大的时候,考虑将其作临时存储,需要的时候再进行对比。
比如,一旦出现日期时间命名的目录或静态文件,我们可以考虑将其存储为下面的格式:
目录层级
命名格式
URL地址(或压缩过的hash值)
有人可能说,在前面seay提出的那个案例里,好像是可以解决类似日期相似度的问题。那我们先看看下面的例子,此处输出仍然基于上面那个函数:
print urlsimilar('http://www.baidu.com/blog/2010-10-11/')print urlsimilar('http://www.baidu.com/blog/2010-10-13/')print urlsimilar('http://www.baidu.com/blog/2010-9-13/')print urlsimilar('http://www.baidu.com/whisper/2010-10-11/')
输出结果如下:
110086
110086
37294
4842
我们可以看到,在普通情况下,确实于相同父级目录下,相似度算法是可以判断正确的。 但是一旦日期格式不规范,或者父级目录存在一定的差异,这里是不能很好的判断的。
当然,我们也可以通过机器学习来完成去重的工作。不过就简化工作而言,还是可以使用一些小Tips,根据规则匹配来做到。
静态文件的去重
我们知道,在爬取URL的过程中,也会遇到许多静态文件,如shtml、html、css等等。这些文件在大多数的情况下,是没有太大意义的。除非测试者倾向于使用“宁可错杀一百,绝不放过一个”的全量采集手法。
这时候,我们可以配置黑名单,建立文件后缀规则库进行过滤。
当然,在这些静态后缀的URL链接,也可能带上参数混淆的情况。 个人建议是,用于回调的json、xml等URL,里面可能储存敏感内容,尽量别动;其他类型的静态文件,仍然采取将参数分离的方式,最后对URL进行去重存储。
特定情况的过滤
在爬取特定网站时,我们可以预先做好配置,指定过滤一些目录和页面,以节省大量时间资源。
反过来,我们也可以指定只爬取指定目录下的页面,定向获取我们想要的内容。
敏感页面的感知
在前面seay提出的demo算法中,在这种情况下是有一定局限的。比如我们需要在敏感目录下,尽可能多的拿到文件信息。比如我们爬取到了后台管理目录,可能会遇到下面的情况:
print urlsimilar('http://www.baidu.com/blog/admin/login.php')print urlsimilar('http://www.baidu.com/blog/admin/manage_index.php')print urlsimilar('http://www.baidu.com/blog/admin/test.css')
输出结果如下:
40768
40768
40768
很明显有问题不是么?
当然,我们可以通过对敏感页面关键词进行监控;或者也可以指定后缀文件,进行白名单监控。
但是一旦这样做,而且还想采用前面的hash算法的话,大家自行定义的过滤函数的优先级,肯定需要大于该算法。并且,我们在这样做的过程中,也应该考虑过滤成本的问题,建议采用选择性启用。
高频敏感目录的优待
可能在爬取的过程中,部分爬虫是兼用了目录爆破的手段的。如果采用了这种手法并且匹配成功后,我们可以将该目录下的内容单独使用一份过滤规则,从而避免去重算法的误判。
响应页面的过滤
对于某些网站来讲,可能有不少页面因为链接是失效的,会被冠以404页面和50x错误。另外,在无权访问的时候,可能网站会做30x跳转和403目录限制。
这些页面没有实质性内容,在大多数时候是没有意义的,我们可以在配置文件里对需要爬取的这类页面做白名单,比如保留403页面,或者存取30x跳转前(后)的页面。
WAF(警告)页面过滤
某些网站可能被装上了WAF,在访问频率过快时,可能会得到一个WAF的警告页面。而在CMS本身就做了限制的情况下,会以20x的响应码展示一些没有不存在的页面。
当然,我们可以通过分布式换代理的方式,去解决部分这样的问题,这里先不多做讨论。
这时候,我们可以配置相应的次数阈值,如果某些页面出现的次数过多,可以将其标记为警告(WAF)页面,进而做出过滤处理。这里对某页面的识别,可以通过黑名单关键字标记;或者尝试计算页面hash值,比如下面这样:
content = urllib2.urlopen('http://www.test.com/').read()md5_sum = hashlib.md5()md5_sum.update(content)print md5_sum.hexdigest()
当然,我们在实际计算页面hash值和做关键字监控时,也可能由于反爬虫机制的存在(如添加随机值),需要适时调整相似度来计算hash值或者采用其他手段。当然这也会消耗更多的时间和机器资源。但某些特定的情况下,可能也会带来意想不到的收获。
无意义参数页面去重
我们在采集页面的过程中,同样有可能会遇到一些毫无意义的、高频出现的多参数页面。这类页面可能是回调页面,也可能是临时渲染的随机页面。
在这里,大家可以通过前面处理WAF(警告)的方法进行过滤。当然,使用前面的hash算法也是可以应对大部分情况的。毕竟网站的这类的URL有限,不必为了几种特型去消耗更多的资源,这样得不偿失。
JS代码中的URL
在我们提取js代码,也就是遇到ajax之类的交互情况时,可能会遇到需要拼接的GET请求,或者直接可以取用的POST请求。
这类的URL地址,最好是结合phantomjs等webkit,更方便地进行动态拼接。
它们会显得比较特殊,可能仅仅返回状态码,也可能会返回实质性的敏感内容。这种情况,就需要根据爬取者的要求,对爬取的过滤规则进行适应性调整。
总结
笔者这里旨在提出一些对相似URL去重的小优化,可能效果有限,也可能存在未尽人意之处。
欢迎大家提出建议,希望少一些爱喷的童鞋,多一点讨论的大牛,与诸君共勉。
-
来自:FreeBuf.COM-dawner
-
www.freebuf.com/articles/others-articles/151173.html
-
程序员大咖整理发布,转载请联系作者获得授权
始发于微信公众号:程序员大咖
这篇文章还没有评论