搜索引擎anti-spam系统设计指南

/*版权声明：可以任意转载，转载时请务必标明文章原始出处和作者信息 .*/

搜索引擎anti-spam系统设计指南

中科院软件所张俊林

TIMESTAMP:2006年5月20日

一. 设计原则与整体体系结构

1.1 设计原则

搜索引擎ANTI-SPAM作为一个新型的技术领域,目前逐渐引起学术届和搜索引擎市场的逐步重视.通过大量资料分析,我认为一个好的实用ANTI-SPAM系统应该遵循以下两个设计原则:

原则1.实用的搜索引擎ANTI-SPAM系统应该允许核心算法公布,并且在核心算法公布之后不会导致现有ANTI-SPAM系统的失效.

原则2.实用的搜索引擎ANTI-SPAM系统应该结合技术和非技术的手段形成一个综合防治系统.两者交互影响形成有效的互相促进作用.

其中原则1是为了避免提供搜索引擎服务的公司陷入以下疲于奔命的状态:核心算法被泄漏,SPAMER找到应付对策,搜索引擎服务公司更换核心算法,核心算法被泄漏…..

而原则2则是尽可能采取各种可能的手段更全面准确的判别网页.

1.2 体系结构

现有的ANTI-SPAM措施可以划分为以下5个类别:

类别1:针对某种具体的方式形成的ANTI-SPAM技术,比如识别LINK FARM的算法,识别内容的算法等.这些方法的特点是技术细节不可公开性以及由此导致的存在寿命短暂性.因为这些技术细节一旦公布,者会考虑相应的反制策略导致算法失效,这样会导致新的方式,而搜索引擎公司不得不研究新的ANTI-SPAM技术.所以根据设计原则1,这样的算法不能是ANTI-SPAM系统的主体框架,只能是一种辅助措施.

类别2:通用的ANTI-SPAM技术.比如HILLTOP算法,TRUSTRANK算法等.这些方法的特点是技术细节可公开性以及由此导致的长期有效性.即使这些技术细节公布,者也无能为力.所以根据设计原则1,这样的算法应该成为系统的主体框架.

类别3:类BADRANK方法.这类方法和类别2的算法是完全互补的两类算法.通用的ANTI-SPAM算法的出发点是寻找网页集合的子集,这些子集一定不是SPAM网页,其它网页根据与这个精英页面集合的关系来判断是否不是SPAM页面,而类BADRANK方法则从必定是SPAM页面的网页子集出发(可以看作是黑名单),从其它网页和这些黑名单页面的关系判断是否是SPAM页面.

类别4:人工举报.这种方法是切实可行的对BADRANK方法的补充手段.通过这种方式不断扩大黑名单的数量.

类别5:类SANDBOX方法.这种方法主要针对SEO市场,造成对于SEO市场的打压,以此避免大规模的出现,因为目前主要的者还是SEO市场造成的.

目前几乎所有的ANTI-SPAM技术可以归于以上5类技术之一,其中类别123是属于技术手段,而类别4和类别5属于非技术手段.通过两者结合来进行有效的ANTI-SPAM系统构造.

一个实用的ANTI-SPAM系统整体结构可以参考图1,图1将这5中技术手段有机的结合来构造综合的治理手段.可以看出系统技术手段围绕着两个核心互联网页面子集:SPAM POOL和NON-SPAM POOL.SPAM POOL代表了确认为是页面的集合,而NON-SPAM POOL代表了确认不是页面的集合.系统流程如下:

1. SPAM POOL可以通过以下三个手段构造:一个是通过人工举报形成黑名单,一个是通过针对具体某种方式采取的ANTI-SPAM技术来获得部分类型的页面并加入SPAM POOL中;另外一种方式是通过类BADRANK方式通过叠代计算来扩充黑名单的规模;这个过程可能需要进行人工确认过程以防治误判.

2. NON-SPAM POOL可以通过通用的ANTI-SPAM技术获得.

3. 类SANDBOX等非技术手段来打击SEO市场.

4. 可以看出系统中的核心技术手段是通用ANTI-SPAM方法以及类BADRANK方法,两者是互补的技术手段,处于系统的核心,人工举报和针对某种方式的ANTI-SPAM技术作为类BADRANK技术的辅助手段发挥作用,而SANDBOX则作为主要的非技术手段发挥作用.通过5种手段相互结合构造实用的ANTI-SPAM系统.可以看出这个系统模型是符合ANTI-SPAM系统设计原则的.

<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 414.75pt; HEIGHT: 310.5pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///E:/DOCUME~1/ZHANGJ~1/LOCALS~1/Temp/msoclip1/01/clip_image001.wmz"></imagedata></shape>

<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1033" style="WIDTH: 414.75pt; HEIGHT: 310.5pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///E:/DOCUME~1/ZHANGJ~1/LOCALS~1/Temp/msoclip1/01/clip_image001.wmz"></imagedata></shape>

图1. 搜索引擎anti-spam技术路线图

二. 组成部分详述

下面分别叙述构成ANTI-SPAM系统的5个部分的技术细节.

2.1通用的anti-spam方法

通用的ANTI-SPAM方法作为系统最重要的框架核心,目前的几种算法基本思想大同小异,其基本目的是确定所有互联网页面中哪些肯定不是SPAM页面.其基本思路都是如下考虑:

1. 首先从所有互联网页面中通过一定的技术手段找到部分精英页面子集.

2. 然后根据其它页面和精英页面子集的链接关系来确定哪些页面不是SPAM页面.

以下列出的三种主流方法基本思路如上所述,其区别无非在于判断精英页面的标准不同以及根据链接关系确定其它页面是否SPAM的技术细节不同.

2.1.1HILLTOP算法

HILLTOP是从检索模型本身出发,结合了相关排序以及anti-spam策略为一体的算法,已经被GOOGLE所采用.其基本假设和出发点是:网络中的权威页面和权威站点(EXPERT)所指向的页面一般来说不会是spam页面,而且被权威页面指向的页面排序应该提高.

所以其算法分解为以下两个步骤:

1. 如何从大量网页信息中识别权威页面;

首先识别Non-affiliated page,所谓Non-affiliated就是页面归属于不同组织的页面,因为基本假设是归属于同一组织的网站页面之间的链接其公信力是不高的.

然后寻找链接出度比较高的页面,如果这些页面所指向的页面都是Non-affiliated页面,那么这些页面可以作为权威页面.

权威页面单独进行索引,对于用户查询,首先在这个索引里面寻找,然后根据其它页面和权威页面的关系进行排序.

2. 根据选择的权威页面如何对其指向的页面排序进行评价;

如果是越多的权威页面指向的页面其权重越高.

2.1.2 TrusteRank方法

TrustRank方法的基本思路和HILLTOP算法类似,也是首先识别部分不可能是网页的站点,然后根据类似的假设来从中推导出好的非anti-spam页面.已经被AltaVista(YAHOO)搜索引擎采用.

1. 从所有站点随机选择若干站点.比如随机选择2000个站点.(也可以有其它类似的优化策略,比如选择知名度高的网站或者YAHOO等收录的网站作为优良网站的基点)

2. 从2000个站点里面人工判断哪些是优良的网站

3. 链接分析.基本假设是优良网站指向的网站也是优良的.此时可以采取不同的策略,比如优良网站经过K个链接所指向的都认为是优良的.也可以引入衰减因素,离初始优良网站越远的网站其优良性越小.

4. 对遍历过的网站优良性能做评价.此评价作为判断是否网页的依据.

2.1.3 SpamRank方法

SpamRank的基本思路与前面两个技术基本一致.它的基本假设是:对于非网页来说,指向其的链接页面一般来说PAGERANK值是不均匀分布的,而对于网页来说指向其的支持网页的PAGERANK值一般来说都是比较小的值.

1. 首先计算页面的支持页面的权重

2. 判断支持页面权重是否满足Power low 分布(这个分布是互联网的一个比较准确的估计)对于不满足该分布的页面判断为网页进行惩罚,降低其PAGERANK值.

2.2 类BADRANK方法

类BADRANK方法是通用ANTI-SPAM方法的有效补充. 它的目的是发现哪些网页肯定是SPAM页面. BadRank的技术思路如下:

1. 首先维持一个SPAM网页黑名单,这个黑名单可以通过用户举报或者采取一定的技术来获得,GOOGLE提供了举报SPAM页面,所以采用BadRank的方法可能性是很高的.

2. 给定黑名单的网页非常高的BadRank值E(x);

3. 考虑其它网页的BadRank值,打分依据是如果网页含有指向黑名单的链接,那么这个网页的BadRank值会很高,依次类推来获得其它页面的BadRank值.其打分公式如下:

<shape id="_x0000_i1034" style="WIDTH: 285.75pt; HEIGHT: 54pt" o:ole="" type="#_x0000_t75"><imagedata o:title="" src="file:///E:/DOCUME~1/ZHANGJ~1/LOCALS~1/Temp/msoclip1/01/clip_image003.png"><font face="Times New Roman"></font></imagedata></shape>

可以看出,其基本原理和PAGERANK是差不多的,区别在于BADRANK是倒着打分的,从已知的网页向未知的网页传播.

2. 3具体针对某种方式采取的anti-spam方法

针对具体某种方式的ANTI-SPAM方法可以作为辅助BADRANK构造SPAM POOL的辅助技术手段,这些技术花样繁多,基本没有一个统一的解决方案,目前常见的方法如下.

2.3.1 针对blog站点的honey pot类型的

Honey pot方式是网页作者发布有价值信息比如介绍某项技术的技术文章,但是在发布的信息里面隐含指向页面的隐藏链接,这样通过网页本身内容的价值来诱导其它网站增加指向该页面的链接从而间接增加页面的排名.比如往blog站点,BBS站点,留言簿或者wiki等可以任意发言的站点增加评论.在发表的评论里面增加指向目标页面的链接,这样会间接增加目标页面的pagerank排名.根据发表评论类型可以分为以下两种:一种是直接发广告性质的与主题无关评论,这个我们经常在BBS或者留言版上看到.一种是评论与主题相关,但是在评论中隐藏无法看到的链接信息.这种情况一般比较难以发现.

利用语言模型方法判断链接所指向的页面是否站点.首先通过评论的内容以及评论中链接指向页面内容构建每个评论的语言模型,然后依次和正文的语言模型进行比较,将差异比较大的看作是可能的站点.

2.3.2针对内容

l 比如针对标题,如果发现正文内容出现标题文字比例失调,比例太高或者没有出现过,则认为可能是网页.

l 而对于HTML页面的keyword内词汇,很多搜索引擎采取不索引keyword域的方法.

2.3.3针对信息隐藏

l 如果发现页面内部大量文本采用和背景相同的颜色设置,则判断为页面.

l 对于链接跳转的页面进行惩罚,以防治通过页面自动重定向来隐藏页面.

2.3.4针对多个域名DNS解析到同一IP地址.

者通过建立若干不同的域名但是是同一IP地址来构建LINK FARM提高目标页面排名,并欺骗搜索引擎这些链接页面分属于不同拥有者.对于这种情况可以进行DNS解析分析, 大量不同域名映射到同一IP地址很有可能是网站.

2.3.5针对机器自动生成link farm

对于机器自动生成的页面进行特征分析和自动发现.比如机器生成的链接往往很长,包含很多数字和连接符号等.如果发现一个页面的大量链接有以上特征则判断为页面.

2.3.6针对网页的不正常数量联入链接(文章:Spam, Damn Spam, and Statistics)

发现网页的入度,根据分布规律,极少数的网页有非常大量的联入,所以这些大量联入页面如果不是知名网站则很可能是网站

2.3.7针对如何识别link spam

这个识别link farm spam方法的基本观察是:很多link farm spam的页面互相通过链接紧密联系,在farm里面往往存在以下特征页面:页面同时有进入和外出链接指向link farm其它页面.所以该方法首先通过一定方法从整个文档集合中确定一些种子页面,再通过其链接特征递归的发现满足链接特征的页面直到link farm无法继续扩张.此时对于这些页面进行惩罚性措施..

2.3. 8程序自动生成页面

页面内容通过随机从其它网站页面抽取拼合而成,而链接指向.其解决办法是判别网页更新速度,这类方式往往有过分快的更新速度,以此作为判别的某个根据.

2.3.9 TrackBack spam

定义:者增加指向某个知名blog的trackback链接但是在页面部分没有任何标记.

解决方案:目前还没有很好的方法.

2.3.10. tag spam

在社会软件比如yahoo的myweb2.0或者flickr中流行的方式,方式类似于传统的KEYWORDS方式,在用户定义某个条目的时候,允许自己增加若干TAG来对条目进行说明,而者通过在TAG中增加很多词汇来增加排名达到目的.

解决方案:目前还没有很好的方法.

2.3.11 fake weblogs

定义:两种方式

方式1. steals content from other sites

者建立blog,拷贝排名比较高的blog内容,这样能够尽快提高自己blog排名,然后在评论里面增加指向目标页面的链接或者做广告.

方式2. Porn sites hiding behind blogs

自动建立若干blog站点,但是用户点击会自动转向目标站点.类似于URL跳转方式.

2.4.人工举报

目前GOOGLE采用了人工举报的方法,其页面如下:

http://www.google.com/contact/spamreport.html

Type(s) of problem (check all that apply):
Hidden text or links
Misleading or repeated words
Page does not match Google's description
Cloaked page
Deceptive redirects
Doorway pages
Duplicate site or pages
Other (specify)

可以看出,GOOGLE目前所研究的anti-spam应该集中在以上几种spam,这也从某个角度说明以上几种是最常用的spam方式.

2.5 SANDBOX方法

长期以来，人们注意到一个现象，当新网站刚被 Google 收录时，在用关键词搜索时，往往会有相当好的排名。一般认为 Google给予新网站一些照顾，使它们有一个快乐辉煌的开端。然而好景不长，不久，新网站的排名就逐渐下降。很快地，竟可能在搜索时完全消失了。

人们把这个现象称之为沙箱效应，认为是具有普遍性的现象，是 Google在搜索算法里设置的一个阻尼过滤器，适用于所有的新网站。当新网站上网一段时间，不论网页评级高低内容多寡结构优劣有无链接，都会被过滤。短则九十天，多则四五个月，在搜索结果里即使还有排名，也多半放在最后。长期以来，这种现象使人大惑不解。因为绝大多数网站是没有的，没有理由被处罚。另外，沙箱效应只限于Google，其它搜索引擎没有类似现象。

沙箱现象可能是 Google 和层出不穷的手段斗争的一种策略。面对防不胜防的诡计，Google 将新网站屏蔽一段时间，心里有鬼的优化商无法判断是否被处罚，会修改网页。对于诚实的网站，这可能是一个好机会，去认真检查优化手段，建立健康链接，充实网页的内容。

SANDBOX:不能有效的识别哪些是或者不页面(其实就没有试图去识别,这不是SANDBOX的目的),但是可以通过这种行为有效的打压SEO市场.因为SEO市场是导致盛行的主要因素.因为有意图而且亲自去的人数还是少数,绝大多数还是有意图没办法,通过SEO来进行的,通过非技术手段打压SEO信用是另外一个治理问题的有效手段,

三. 实施步骤

具体实施一个实用并且好用的WEB ANTI-SPAM措施可以采取逐步实施的三步策略,通过初步实施策略构建初步实用的ANTI-SPAM系统,进一步的实施措施用来对于初步实施的系统进行进一步的完善,而第三步则是根据该研究领域的发展趋势进行深入的科研以获得比现有技术更好的ANTI-SPAM手段.

3.1初步实施措施

初步实施措施可以根据图1,首先实现以下几个部分:

1. TRUSTRANK算法(或者HILLTOP)

2. BADRANK算法

3. SANDBOX算法

4. 人工举报界面

5. 最常见的某种具体SPAM反制措施

可以看出,无论是HILLTOP或者是TrustRank抑或BADRANK,这种方法并没有利用者的特征值来进行判断,而是通过通用的方法来进行处理:首先识别优良页面集合或者不良页面集合,然后通过链接分析来计算这种传播关系.这种方法因为不利用特征分析,所以具有具体方法无关性,也就是说即使公布这个方法,者一般也没有办法采取反治措施.

而另外一类方法是特征相关的,比如分析某类SPAM有哪些内容特征或者页面结构特征,利用页面是否满足这些特征来进行识别,这样的方法是对于某些类型有效的,不具有通用性,另外存在的问题是公布方法后可能这个算法就失效了,因为者会采取另外的方法避免页面出现这些特征.

两者的关系如下:特征分析的方法可以作为BADRANK</f