中科院软件所张俊林
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系统设计原则的.

图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值.其打分公式如下:

可以看出,其基本原理和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的补充和初始集合的获取手段,利用这些方法找到一些作弊网页作为BADRANK的初始种子然后逐步扩大查找范围.

所以在设计搜索引擎ANTI-SPAM方法时候应该采取如下措施:

整体框架采用TRUSTRANK+BADRANK+SANDBOX

TRUSTRANK:识别哪些页面肯定不是作弊页面;

BADRANK:识别哪些页面肯定是作弊页面;

SANDBOX:不能有效的识别哪些是作弊或者不作弊页面,但是可以通过这种行为有效的打压SEO市场.

人工举报和具体ANTI-SPAM方法:帮助建立更加全面的SPAM POOL资源.

3.2.进一步实施措施

进一步的实施措施集中在如下几个方面:

1. 具体ANTI-SPAM方法全面实施,将目前常见的以及不常见的ANTI-SPAM方法逐步实施,这样BADRANK可以发挥更大的作用.

2. 通用ANTI-SPAM方法的改进.通用方法可以在以下两个方面进行改进:一个是如何判断精英页面,改进的方向是更加自动化减少手工劳动,更加精确化,避免作弊者寻找漏洞.另外一个改进方向是页面传播关系的研究,探讨更好的页面传播关系来更加有效地确定哪些是SPAM哪些不是SPAM页面.

3. SANDBOX的改进方法.目前SANDBOX由于原理泄漏,有可能SEO会想相应的策略避免惩罚,采取二次SANDBOX或者其它改进办法,核心是增加排名的不确定性,避免SEO能够给用户确定的承诺(比如半年内排到前几名),以此来打击SEO市场.

4. 在人工举报方面.改进思路是如何吸引举报者来尽可能多地进行举报,可以通过奖励措施比如如果举报有效可以部分提高举报者的网站排名等奖励措施来增加举报者的积极性.

3.3 深层研究方向

深层研究方向可以在以上介绍的5个方面全面实施,寻找更加优秀的替代算法,通过科研投入达到优秀的ANTI-SPAM效果.

从目前学术界状况来看，在未来地最近几年内，在通用ANTI-SPAM方面很难出现全新的理论框架，如果这方面有成果的话，应该是提出类似思路的方法或者对于现有方法细节的补充，今后大量的研究工作会集中在具体的ANTI-SPAM方法方面，尤其是随着新种类的SPAM方式不断出现，如何对于新类型SPAM进行发现和防治将是学术界的主流，但是这样很难从根本上解决问题。

四. 结论

搜索引擎ANTI-SPAM是目前比较迫切需要解决的问题,本文通过如何构造一个有效的ANTI-SPAM系统这一主题在设计原则,系统整体结构,每个技术的实施细节以及实施步骤等方面进行了探讨,希望能够成为有效设计优秀ANTI-SPAM系统的技术指南和路线规划说明.