第5卷第3期 智能系统学报 Vol.5 No.3 2010年6月 CAAI Transactions on Intelligent Systems Jun.2010 doi:10.3969/j.issn.1673-4785.2010.03.001 反垃圾电子邮件方法研究进展 谭营12，朱元春12 (1.北京大学机器感知与智能教育部重，点实验室，北京100871：2.北京大学信息科学技术学院，北京100871) 摘要：随着垃圾电子邮件对互联网技术的威胁日益严峻，反垃圾电子邮件研究已成为当今的研究热点，综述了反 垃圾电子邮件研究的历史、现状和最新进展.首先介绍并分析了3种类型的邮件特征提取方法一基于文本、图片 和行为的特征提取方法.然后，在此基础上，详细论述了当前的反垃圾邮件技术一法律手段、简单方法和智能型处 理技术，接着，介绍了反垃圾邮件系统性能评估准则和标准数据集.最后，对反垃圾电子邮件现状进行了分析和总 结，并指明了未来反垃圾电子邮件研究的发展方向，包括改进邮件特征提取技术、完善相关法案和引入新的智能反 垃圾邮件方法。 关键词：反垃圾电子邮件：特征提取：智能检测技术：性能评估 中图分类号：TP393文献标识码：A文章编号：1673-4785(2010)03-0189-13 Advances in anti-spam techniques TAN Ying'2,ZHU Yuan-chun'.2 (1.Key Laboratory of Machine Perception (MOE),Peking University,Beijing 100871,China;2.School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China) Abstract:As the threat of spam on the Internet grows increasingly severe,anti-spam techniques have become a hotspot for researchers.The authors reviewed the history,current situation,and latest advances in research on spam control.First,we introduced and analyzed three different types of feature extraction methods for email.These were text-based,image-based,and behavior-based approaches.Then,current anti-spam techniques were described and discussed.These included laws,simple methods,and intelligent approaches.After that,performance evalua- tion methods and standard data sets were discussed.Finally,we summarized the current research on anti-spam techniques and pointed out directions for future research,including improvements to e-mail feature extraction tech- niques,improvements to laws,and new intelligent anti-spam approaches. Keywords:anti-spam;feature extraction;intelligent detection technique;performance evaluation 随着信息技术的持续发展和互联网的日益普为国内外研究的热点，具有必要性和重大意义 及，电子邮件(E-mail)已成为人们日常通讯交流的 在反垃圾电子邮件技术研究中，学者们相继提出 重要方式之一.然而，垃圾电子邮件(unsolicited bulk 众多的邮件特征提取方法和垃圾邮件检测过滤方法， email-一UBE,or Spam)的涌入，给电子邮件通讯带 本文是对反垃圾邮件技术和方法研究现状的综述，重 来诸多不便，引发了日益严重的问题.垃圾电子邮件 点介绍以下内容：垃圾电子邮件的现状、用于垃圾邮 不仅会耗费通信带宽、网络资源，而且消耗人们大量 件检测的邮件特征提取方法、现有的反垃圾邮件技术 的处理时间，造成生产力浪费，使公司蒙受巨大经济 以及反垃圾邮件系统评估准则和标准数据库 损失.因此，垃圾邮件检测技术和方法的研究，已成 1垃圾电子邮件现状 收稿日期：2009-1120 1.1定义 基金项目：国家“863”计划资助项目(2007AA01Z453):国家自然科学 基金资助项目(60673020,60875080). 在反垃圾电子邮件技术研究中，一些专家学者 通信作者：谭营.E-mail:ytan@pku.ed.cm. 和研究机构给出不同的垃圾电子邮件定义
·190. 智能系统学报 第5卷 Cranor等人将其定义为：“未经请求的大量 件所引发的这些严重社会问题，近年来，反垃圾电子 电子邮件(unsolicited bulk email,UBE)”.垃圾电子 邮件策略受到了前所未有的关注 邮件还被定义为21：“未经请求的商业电子邮件 United States 15.7% Brazil 10.7%mcdooo (unsolicited commercial email,UCE)”.中国互联网 China(lncluding Hong Kong)6.0% 协会将垃圾电子邮件定义为]：收件人事先没有提 South Korea 4.3% Rnssia 3.5% 出要求或者同意接收的广告、电子刊物、各种形式的 Poland 3.4% Spain 3.2% 宣传品等宣传性的电子邮件；收件人无法拒收的电 Argentina 2.6% 子邮件；隐藏发件人身份、地址、标题等信息的电子 邮件；含有虚假的信息源、发件人、路由等信息的电 emany United Kingdom 2.0% 子邮件；含有病毒、恶意代码、色情、反动等不良信息 Chile1.8%题 France 1.6% 或有害信息的邮件。 Thailand 1.4% Mexico 1.2% 0hr21.6%22 以上3种定义尽管不同，却有着一个共同点：未 经请求.这是垃圾电子邮件与正常电子邮件的本质 图1各国家垃圾电子邮件数量比例 区别.正常电子邮件是人们正常通讯、交流的媒介， Fig.1 The proportion of spam-relaying of different countries 包含着交互信息的需求.而垃圾电子邮件往往包含 70 56.70 58.21 57.89 57.87 57.52 收件人不感兴趣的内容，且在未经许可的情况下发 60 50 送给收件人.垃圾电子邮件一般包含商业广告信息， 0 且成批量发送，这也是定义其为UBE、UCE的原因. 30 同时，垃圾电子邮件发送者为逃避对电子邮件的反 20 10 向追踪，会刻意伪造发件人、路由、信息源等信息.故 在多数情况下，这3种定义是一致的 2008.Q1 2008.Q22008.Q32008.Q42009.Q】 季度 1.2垃圾电子邮件的规模与影响 图2中国网民平均每周收到垃圾电子邮件的比例 根据Symantec公司的统计报告，2008年全球范 Fig.2 Weekly average ratio of spam received by cyberciti- 围垃圾电子邮件的平均比例已经占到了总邮件数的 zens in China 8O%左右.依据Ferris Research的研究估计s) 2009年垃圾电子邮件将耗费全球1300亿美元的开 2邮件特征提取方法 销，其中，劳动力浪费引起的开销占总开销的85%. 对于垃圾邮件检测系统来说，邮件特征提取是 这将比2007年的估计增长30%，而比2005年的数 极其关键的环节，甚至比模式识别方法的选择、分类 据增长100%.根据Sophos公司最新调查结果显 器的设计与使用更为重要.邮件特征提取方法的准 示6，中国的垃圾电子邮件的数量继美国、巴西之 确性、可区分性、稳定性和自适应性将会直接影响到 后，位列第3位.图1显示出各国家的垃圾电子邮件 系统整体的分类效果与性能.据中国互联网协会 数量比例. 2008年第四季度中国反垃圾邮件调查统计[8]，用户 中国互联网协会2009年第一季度中国反垃圾 收到垃圾邮件的正文格式主要是3种：图片+文本 电子邮件调查结果指出，中国网民平均每周收到 格式、纯文本格式和纯图片格式.本节将综述经典的 17.68封垃圾电子邮件，与去年同比增加0.04封， 基于文本的邮件特征提取方法、基于图片的邮件特 占邮件总数的57.52%.图2给出中国网民在2008 征提取方法和基于行为的邮件特征提取方法， 年第一季度至2009年第一季度平均每周收到垃圾 2.1基于文本内容的邮件特征提取方法 电子邮件的比例.调查报告还指出，处理这些垃圾电 基于文本内容的邮件特征提取方法一般包含2 子邮件将耗费中国网民平均每周12.35min.仅考虑 个阶段：1)词筛选(terms selection):依据词的重要 浪费时间的因素，2009年第一季度垃圾电子邮件致 性（可区分度）对特征词进行排序，选择可区分度好 使中国损失人民币339.59亿元，与2007年同比增 的特征词进人下一阶段；2)特征提取与表示：提取 长151.19亿元，涨幅为80.25%.鉴于垃圾电子邮 出邮件特征并表示成统一的形式
第3期 谭营，等：反垃圾电子邮件方法研究进展 ·191· 2.1.1文本词筛选方法 法，文档频率值大于预设阈值的词将被选择，而文档 当邮件库中的邮件经历切词阶段后，大量的单 频率值小于该阈值的词将被舍弃，单词：的文档频 词被获取，如果不经过词筛选过程，会导致特征维度 率被定义如下： 过高，引发维度灾难.词筛选一方面可以降低特征维 D(t)=|{mImy∈M,t∈mI. 度和计算复杂度，另一方面还可以减小噪声（区分 式中：M表示整个训练集，m表示M中的一封邮件 度差的单词)的不良影响.下面介绍几种常用的词 文档频率法认为低频单词所含的类别信息量较 筛选方法： 少，移除它们不会影响整体分类性能.文献[11]指 1)信息嫡 出，当移除90%的低信息量单词时，文档频率方法 在信息论中，信息嫡(IG)又被称为Kullback 与信息嫡和x统计量方法的性能相当.文档频率方 Leibler距离9.它能够度量2个概率分布P(x)和 法的主要优点是，计算复杂度低，与训练样本的数量 Q(x)的距离。在垃圾邮件检测技术研究中，它被用于 成线性比例增长 度量单词的优良度（区分度）.根据该方法，可以计算 4)其他词筛选方法， 出，当知道给定单词：是否在邮件中出现时，所能获得 词筛选方法在垃圾邮件检测系统中起着重要的 的邮件类型信息的量.单词t:的信息熵被定义如下： 作用.为了更好地理解词筛选方法，下面列出3种其 P(T,C) 1e)=Σ，{P(T,C)logp(TP(C) 他的常用方法的计算式3町。 Celesg]Te(fi) a)x2统计量(CH): 式中：C表示邮件类型，c.和91分别表示邮件类型是 X(t,c）= 垃圾邮件(spam)和正常邮件(legitimate email),t: 表示单词在邮件中出现，而：表示单词t:未在邮 I MI (P(ti,c)P(t,c)-P(,c)P(t,c))2 P(t)P()P(c)P(c) 件中出现.式中的概率可以根据训练集数据进行估 b)比值比(odds ratio): 计.根据该式，每个单词的信息熵值将被计算出来， P(tI c)1-P(tI c) 信息熵值大的单词将被选择进人下一阶段， x(,c)=1-P(tc) P(til e)i 2)词频方差 c)术语强度(terms strength): Koprinska等人[io研究出词频方差法(term fre- S(t)=P(t∈yl tiex), quency variance,TFV),来选取具有高词频方差的 式中：c∈{c.,G}表示给定的邮件类型，相应的c∈ 词.他们认为词频方差大的词包含更多的信息量.依 {c.,G/c,x和y表示训练集中类型相同的任意2封 据该方法，那些倾向于出现在某一种类型邮件（垃 不同邮件 圾邮件或正常邮件)的词将被选择，而那些在2种 2.1.2文本特征提取方法 类型邮件中出现频率相当的词将被移除.在反垃圾 1)词汇袋法 邮件技术研究领域中，词频方差被定义如下： 词汇袋法(bag-of-words,BoW)也被称为向量空 T)=,Σ[T(,C)-T5()]2. 间模型，是垃圾邮件检测技术研究领域应用最广泛 式中：T(,C)表示单词t:在类型为C的邮件中的 的方法之一「2]，通过观察特征词是否在邮件中出 出现频率，T(:)表示单词：在2种类型邮件中出 现，将每封邮件转换成一个d维的特征向量,其中每维特征值x:可以看作是特征词 文献[10]指出在多数情况下，词频方差方法性能 :的函数.对于x,有2种常用的类型表示方法：布尔 优于信息熵方法.具有最大信息熵值和最大词频方差 型和频率型4]，在布尔型表示下，x:按下列方式赋 的前100个词的对比显示，这些词具有以下特征：a)在 值：若：在邮件中出现，那么给x:赋值1，否则给其赋 内容为语言学相关的正常邮件中频繁出现；b)在垃圾 值0.如果采用频率类型表示，那么：则表示为该邮 邮件中频繁出现，却在正常邮件中极少出现。 件中特征词t:的词频.Schneider的实验显示，这2种 3)文档频率 类型的表示法性能相当5 文档频率(document frequency,DF)指的是某 2)稀疏二元多项式哈希， 一特定的单词t:所出现过的邮件的数量.依据该方 稀疏二元多项式哈希(sparse binary polynomial
·192 智能系统学报 第5卷 hashing,SBPH)运用滑动窗口方法，能够从邮件中 基因库，否则将其添加到正常邮件基因库.然后，根 提取出大量的不同特征16.它使用一个长度为N 据邮件中单词在2个基因库中的出现情况计算出每 个单词的滑动窗口依次滑过邮件中的单词，窗口移 封邮件的“自己浓度”和“异己浓度”.这2个浓度值 动步长为1个单词.在每次窗口的滑动中，都将按以 共同构成邮件的二维特征向量 下方式提取21个特征：最新进入窗口的单词被保 2.2基于图片的邮件特征提取 留，而窗口中的其他单词被选择保留或删除，选择之 为了避开垃圾邮件检测系统的过滤，垃圾邮件 后，整个窗口被整体映射为一个特征.对于窗口中的 发送者有时会采用图片型邮件来发送广告信息.检 N-1个单词，存留选择有2-1种，故可映射成2- 测这类垃圾邮件的关键在于提取有效的图片特征， 个不同的特征.然后，每个特征将被计算为一个特定 目前，基于图片的特征提取研究仍处于初步，常用的 的哈希值，特征提取之后可以根据前面介绍的词筛 图片特征包括以下方面： 选方法进行特征筛选，以降低特征维度.该方法的分 1)图像属性特征 类准确度较高，但因为特征数量的庞大计算复杂度 这些特征包括图片类型、大小、颜色、饱和度等. 很高 垃圾邮件发送者往往倾向选择高压缩率的图像格 3)正交稀疏双词 式，从而能够在较短时间内发送出大量的垃圾邮件 为了降低SBPH方法的冗余度和复杂度，Sief 故可以选取图片的类型作为其中一个特征，来检测 kes等人I7]提出正交稀疏双词法(orthogonal sparse 图片型垃圾邮件01.图像的这些属性均包含了一定 bigrams,.OSB)来提取一个较小的特征集合.该方法 的类别信息，广告图片的这些属性值往往与正常邮 同样使用长度为V个单词的滑动窗口提取特征，与 件有一定的差异 SBH方法不同的是，只有具有共同单词的单词对 2)边缘特征. 被提取作为特征.对于每个窗口来说，最新进入窗口 相对正常邮件来说，垃圾邮件图像中往往包含更 的单词被保留，并作为共用单词.然后，从剩下的 多的文字信息.而包含大量文字的图片会具有不同的 N-1个单词中选择1个与其组成单词对，如此每个 边缘特性.因此可以利用边缘特性，如：方向性、边缘强 窗口可以构造出N-1个单词对，映射出W-1个特 度、边缘轮廓形状，来有效地检测垃圾邮件2】」 征.与SPBH方法相比，这样做大大减少了特征的数 3)文字特征. 量.文献[17]中的实验表明OSB性能略优于SBPH 可以利用文字识别工具将图片中的文字提取出 方法 来，然后对文字进行语言分析、关键词匹配，也可以 4)基于人工免疫系统 采用基于文本的特征提取方法，从而有效检测垃圾 Oda等人[181设计出一种反垃圾邮件免疫模型， 邮件 运用正则表达式构造抗体（检测器）.正则表达式的 4)其他特征 运用，使得每个抗体都能够匹配大量的抗原（垃圾 除了上述特征外，可以利用图片的纹理特征、异 邮件)，这样能有效降低抗体（特征）集合.模仿生物 质特征、噪声特征等有效地对邮件类型进行区分，对 免疫系统(biological immune system,BIS)的功能，他 垃圾邮件进行过滤 们给每个抗体赋予不同的权重.算法初期，所有的抗 2.3基于行为的邮件特征提取方法 体权重被初始化为一个缺省值，经过一段时间的运 基于行为的垃圾邮件检测技术是一种新型过滤 行，那些匹配垃圾邮件较多的抗体的权重将被增加， 垃圾邮件的手段，通过提取垃圾邮件与正常邮件有 而那些与正常邮件匹配的抗体的权重将被降低.当 区分的行为特征，来过滤垃圾邮件.本节对常用的基 抗体的权重低于预设阈值时，该抗体将从系统模型 于行为的反垃圾邮件技术进行综述，从4个方面阐 中被移除。 述常用的邮件行为特征：基于邮件头部信息及系统 Ruan等人[9]提出一种基于免疫浓度的特征构 日志的行为特征、基于附件的行为特征、基于网络的 造方法.该方法根据单词的倾向性构建出2个基因 行为特征以及基于用户行为的特征， 库.若一个单词在垃圾邮件中出现频率高（倾向在 2.3.1基于邮件头部信息及系统日志的行为分析 垃圾邮件中出现)，那么将该单词添加到垃圾邮件 正常情况下，邮件的头部信息能反映邮件传送
第3期 谭营，等：反垃圾电子邮件方法研究进展 ·193 信息及发信人的基本意图：发件人、收件人、抄送、发 节省资源.文章采用贝叶斯分类方法，实验效果在时 送时间等.一般情况下，正常的邮件在这些条目中将 间性能和资源耗用上优于其他的一些算法 用正确的格式填入完整的信息.但为了避开一些常 文献[27]对发送人P地址、SMTP ID序列、 用的反垃圾邮件机制，垃圾邮件发送者往往在这些 URL连接和回复邮件地址进行分析，对其按照设定 条目中填人伪造的数据和错误的格式， 的公式计算相应邮件的评分，然后用人工免疫系统 文献[22]针对这种行为模式提出一种基于行 对处理过的数据进行分类.该机制具有可靠性、有效 为的反垃圾邮件机制：首先，该文献在头部信息中选 性和可扩充性 取最能区分出垃圾邮件的7个条目，如From field、 文献[28]针对P和域名，发送者、接收者的对 To field、.Reply-To field等；然后，基于这些基本的特 应关系，发送者、接收者邮件地址的长度，以及发送 征，从他们的交叉比对组合中选出10个特征，如 频率等信息为特征，用决策树进行分类. From-To、From-Reply-To等：接着针对各条目的数据 2.3.2基于附件的行为分析 正确、错误、伪造类型分别定义出相应的类别，并进 文献[29-30]分析邮件的附件行为用于发现带 行编码，得到113维的特征向量：最后，作者使用支 病毒的可疑垃圾邮件.文中MET客户端(malicious 持向量机、贝叶斯和决策树3种分类方法对特征化 email tracking)采用MD5哈希技术给每个附件赋予 后的邮件数据库进行分类.实验中，支持向量机在各 一个特定标识，并保存一个相关记录（标识、时间 数据集上的性能优于其他2种方法，但决策树有较 戳、附件有无病毒、发件人地址、收件人地址).MET 高的准确度.相对于基于内容的机制来说，该机制拥 服务器端接收MET客户端的信息，并根据附件的特 有较高的准确度、较低的特征维度和较低的时间复 征进行分析处理一病毒事件、附件产生率、病毒生 杂度 命周期、病毒事件频率、病毒死亡率、病毒流行程度、 文献[23-24]在此基础上加入系统日志中的一 病毒威胁、病毒传播等.当MET客户端发现某一附 些条目信息作为特征，并利用一种增强型的BP神 件的产生率或流行率大于给定的阈值时，将会对其 经网络对特征化后的邮件数据进行分类，根据各特 他的特征进行进一步分析，来确定是否为病毒.如果 征的重要程度赋予各个特征不同的权重.文献[25] 是病毒，就将此报告给中心服务器.中心服务器将会 指出，有190多个头部信息条目和23个系统日志条 基于其他客户端关于此附件的报告来作出最终决 目可以被邮件用户代理/邮件传送代理(mail user 定，判明其是否为病毒.若为病毒，则将相关标识、病 Agent/mail transfer Agent,.MUA/MTA)使用.文献 毒死亡率、该种病毒发生频率等信息发给客户端，来 [23]研究探讨了多达13种形态24种类型的垃圾 避免将来的感染.如果客户端提供了邮件地址和P 邮件行为形态，选取32个基本条目及38个交叉比 地址，那么就可以根据信息追踪出病毒的制造者. 对条目提取特征.并且还进行实验验证交叉比对条 文献[31]提到将邮件携带附件的类型（图片、 目的重要性.文献[24]观察得出，MUA/MTA并没有 二进制文件、文本文件等)，以及附件的数量作为区 使用所有的头部信息和系统日志条目，文中选出6 分垃圾与非垃圾邮件的行为特征 个最有意义的头部信息条目和4个最有意义、最高 2.3.3基于网络的行为分析 出现频率的系统日志条目，以及基于此选择出16个 1)基于社会网络的特征提取 交叉比对条目进行研究实验 文献[30,32]分析邮件传送过程中的簇行为特 文献[26]提出基于行为的分阶段过滤垃圾邮 征，即用邮件经常交流的一些人形成特定的簇，邮件 件技术，在过滤的过程中，该机制不仅分析处理到目 发送行为一般发生在簇内部.比如说，一般情况下， 前阶段为止的所有行为信息，而且还特定分析处理 一个用户不会将同一个邮件信息同时发送给他的配 新增的行为信息.根据STP协议，它将处理分为4 偶、上司、朋友等，这种概率非常小.然而一个对用户 个阶段：HELO、FROM、RCPT TO和DATA,利用各 地址簿的攻击者显然不知道这些社会关系模式，当 个阶段中的属性信息进行分类处理.如果邮件在前 他试图给地址簿中的所有人发送邮件时就会违反正 一个阶段中被确定分类为垃圾邮件，那么邮件就会 常邮件的簇行为特征.从概念上来说，有2种簇模 被直接拒绝掉，而不会进入下一个阶段，这样做能够 式：用户簇模式和群落簇模式
·194 智能系统学报 第5卷 用户簇模式通过对单个用户帐户的邮件历史分 关系.该文献通过研究P地址空间分布特征，来分 析计算得到.对于某一邮件来说，收件人列表（收件 析垃圾邮件发送者、垃圾邮件僵尸网络和正常邮件 人、抄送、密送)中的所有帐户看作一个簇关系.为 发送者的网络分布.大多情况下，正常邮件与垃圾邮 了避免簇的数量过大，以及冗余现象，只选定那些最 件分布大致相同，大多数的邮件都来自一小部分P 大化的簇，即所选定的每个簇都不是其他簇的子集。 地址空间.但有一小部分例外的情况，在地址段 例如，有3个收件人列表：[A,B,C],[A,B]和[A, 80*~90.*中，绝大多数邮件都是垃圾邮件，在地址 B,D],则会选择2个作为簇—[A,B,C]和[A,B, 段60*~70*中，绝大多数邮件都是正常邮件.这表 D].若某一邮件的收件人列表不是任何用户簇的 明可以将P地址作为一个区分特征.该文献还分析 子集，那么称其为不一致簇行为.这种方法往往要与 了僵尸网络的行为特征，分析得出：绝大部分的垃圾 其他模型结合使用，以处理特殊的收件人列表情况. 邮件是从Windows操作系统中发出的，并且有很大 如果用户曾发过一个全体收件人列表的广播邮件， 比例(25%)的垃圾邮件来自僵尸网络.65%的已感 那么该机制就会失效.然而，这种情况较少发生，一 染的P地址仅发送了一次垃圾邮件，且其中75% 般情况下，用户只会给地址簿中少于10%的帐号同 发送时间短于2min.由于这些P地址生命周期短， 时发送邮件. 这种情况使得黑名单方法失效.研究还表明，每个僵 群落簇模式通过2个用户间的邮件交流数量建 尸网络节点在整个周期发送的垃圾邮件数量少于 立相应的联系.若两帐户间交换的邮件数量超过给 100封.垃圾邮价发送者利用大量的僵尸网络节点 定阈值，那么就认为这两帐户间存在联系.然后，利 发送垃圾邮件，且对每个节点来说，只利用很短的时 用层次算法，逐步建立大小为n的簇.例如，当前层 间，发送少量的邮件因此，基于黑名单和发送数量 次为2，存在AB、AC、AD、BC、BD、CE6个簇.只有 的方法对这种情况都会失效.文献还分析了边界网 当只是最后一个成员不同时，2个簇才能进行融合， 关协议(border gateway protocol,BGP),用路由广播 以避免重复.例如，AB、AC形成候选簇ABC,但是 传播垃圾邮件.该机制使用了大量的P地址空间， AB、BC不再融合.当所有候选簇形成完毕后，要对 并且发送者在空间中分散分布，使得不容易被察觉. 其合法性进行检查.只有当前层次中同时存在AB、 目前使用这种机制发送的垃圾邮件比例还很小，大 AC、BC时，候选簇ABC才是合法的.最后，要将那 约为1%~10% 些是其他簇的子集的簇去掉，如AB、AC、BC将会被 2.3.4基于用户行为的技术 去除.如此进行下去，形成大小为n的群落簇， 文献[35]分析用户的行为特征，用户查收邮件 文献[33]定义3种类型的图，来描述邮件的发送 可以归纳为以下几类行为：在远程邮件箱中将认为无 行为：有向图、无向图和差分图.在有向图中，节点代 用的邮件删除；打开邮件并且阅读时间超过给定阈值 表至少进行了一次发送或接收行为的电子邮件用户， N;打开邮件但在低于N将邮件删除；将邮件移存至 有向图的边表示一用户从另一用户那里接收或向其 邮件箱目录；回复、转发邮件；将发件人加入通讯簿 发送了一封邮件.无向图中，节点代表至少进行了一 通过收集这些用户处理邮件的行为信息，该方法将其 次与另一用户发送和接收行为的那些邮件用户，边代 作为垃圾邮件检测系统的反馈信息，将处理的信息反 表两用户间交换了信息.差分图是基于2个有向图建 馈给反垃圾邮件网关.网关可以将界定的垃圾邮件作 立的，用于表示那些存在某一图中，而不存在于另一 为其他过滤器的训练或学习样本，提交共享黑名单 图中的那些边.基于此，算法共分为3个阶段：a)基于 等.另外，还应清除邮件系统中某些用户收件箱中未 服务器的系统日志，建立3种类型的图；b)利用有向 阅读的但已被其他用户界定的垃圾邮件 图和无向图，对邮件发送者进行初步分类，列入黑名 文献[30]提出使用模型来描述用户发送邮件 单、白名单或灰名单；c)利用差分图，对b)阶段的分 的特征.它统计出每个用户在每个小时段的发送行 类结果进行调整，得到最终分类结果， 为（向外发送邮件的数量、附件数量、邮件大小、收 2)邮件的网络分布特征 件人数量)，建立柱状图.通过将当前阶段的行为特 文献[34]分析垃圾邮件发送的网络层次行为， 征柱状图与历史行为特征柱状图进行对比分析，来 是首次分析垃圾邮件、僵尸网络和网络路由的相互 发现异常行为（垃圾邮件）
第3期 谭营，等：反垃圾电子邮件方法研究进展 ·195· 者只要在收录邮件地址时加上一些简单的识别代 3 反垃圾邮件技术 码，依旧可以提取出真实的邮件地址.目前通过字典 3.1法律手段 攻击，邮件地址收集程序可以推算出邮件服务器中 为了应对垃圾邮件带来的巨大损失，一些国家 的账号，还可以提取网上非页面文档（如DOC、 制定出相应的法律来规范邮件发送行为，力图减少 JPEG、PDF、XLS、RTF、PPT等)中的邮件地址， 垃圾邮件的数量.美国在2003年制定出反垃圾邮件 2)关键词过滤。 法案—非请求色情及广告信息攻击控制法案 关键词过滤技术通过检测每封邮件中是否存在 (controlling the assault of non-solicited pornography 预先定义的关键词，例如发票、促销、Viagra等，来判 and marketing act,.CAN-SPAM Act))[36].该法案明确 断邮件的类型21.最初只采用完全匹配的方法，“Vi 禁止邮件头信息伪造、邮件地址骗取和邮件地址攻 agra”只能与“Viagra”匹配，而不能匹配“Viiaagra” 击等行为.该法案同时还要求商业性邮件必须有退 这样很容易被垃圾邮件制造者通过小改动，规避这 订链接.然而，文献[2,37]指出该法案对垃圾邮件 些关键词. 数量的控制不具有明显的效果，退订链接的存在反 之后，基于正则表达式的模式匹配方法逐渐被 而有助于垃圾邮件制造者确认有效邮件地址. 采纳.特定模式“V*i*a*g*r*a”可以与“V-i 澳大利亚的电信法案第107条，针对个人、公司 gra”、“Viaagra”、“Viagra'”等关键词进行匹配.这种 分别制定了不同的规定2，).只有得到了收件人的 模式匹配方法能够有效地减小关键词库的大小，并 允许，才能向个人发送垃圾邮件（包括商业邮件，以 能在一定范围内适应垃圾邮件的小改动 及收件人数超过50人的邮件).而它对发送给公司 3)黑名单和白名单 的邮件的限制要宽松一些，允许向公司发送包含退 这2种方法均基于对发件人身份的简单识别，当 订链接的垃圾邮件。 身份信息被伪造时，这2种方法将会失去效用) 欧洲议会在2002年6月通过了隐私和电子通 黑名单方法指的是通过拒绝来自特定P地址、 讯法律规章13]，禁止在未征得收件人同意的情况 TCP连接，或域名的邮件，从而过滤掉垃圾邮件发送 下，向其发送垃圾邮件. 者发送的垃圾邮件.但是这些包含在邮件头部中的 这些法律条文的制定与实施，能够在一定程度 信息有时会被垃圾邮件发送者伪造成其他人的地址 上缓解垃圾邮件问题，然而，这些法律不能彻底杜绝 发送，这样会使得无辜的人的电子邮件被过滤掉. 垃圾邮件的产生.因此，必须将其与其他技术手段相 白名单方法指的是只接收来自特定P地址、 结合，才能更好地过滤垃圾邮件，保障电子邮件通讯 TCP连接或域名的邮件，而拒绝其他所有来源的邮 的便捷通畅。 件.白名单方法使用起来不是很方便，2个人刚开始 3.2简单方法 联系时需要发送请求确认邮件 在反垃圾邮件研究初期，人们通过对垃圾邮件 4)灰名单和激励-响应， 基本特征和垃圾邮件制造者基本手段的观察，人工 灰名单方法会对服务器中未记录的邮件给出暂 制定出一些简单的对策.这些方法在早期的反垃圾 时失败的响应[o].对正常邮件来说，正确配置的 邮件工作中起到了重要的作用 MTA收到该响应后会再次发送该邮件.当服务器在 1)地址保护 一定时间内再次收到该邮件时，会将其成功传送.而 文献[39]提出一种比较简单的反垃圾邮件技 对于垃圾邮件来说，邮件往往是通过开放转发 术，通过改变公开的邮件地址形式来防范垃圾邮件. (open-relay)的方式发送，不会因为错误响应而再次 例如，将邮件地址username@domain.com改变为 被发送，故无法成功到达收件人.该方式的缺点是会 username#domain.com username AT domain.com 给正常邮件的发送带来少量的延迟 等形式，有时进一步地将“.”改写为DOT.这样做可 激励-响应(challenge-response)在白名单的基 以在一定程度上防止垃圾邮件制造者通过爬虫技术 础上增加了激励响应策略4].该方法同样维护一个 获取网页上的邮件地址 白名单列表，来自白名单列表中地址的邮件会被成 但是，这种技术的防护能力很弱.垃圾邮件发送 功发送.而列表之外的邮件地址进行发信时，服务器
·196 智能系统学报 第5卷 会返回给发件人一个“图灵测试”，如果发件人通过 Naive Bayse. 了测试，邮件将会被成功传送，而相应的发件人地址 4)支持向量机 将被添加到白名单列表中.垃圾邮件制造者一般会 文献[50-52]中对该方法进行了深入的讨论 采用伪造的发件人地址，来逃避反向追踪，也就收不 Drucker等人Is3实现了一个基于SVM的过滤器，他 到返回的测试. 们的研究表明SVM过滤器和Boosting Trees过滤器 这2种方法的设计基于正常邮件和垃圾邮件发 均能够达到最低的错误率(error rates),但是Boos 送时所能作出的不同反应，利用垃圾邮件无法正确 ting Trees花费了更多的训练时间. 作出响应的不足，对邮件类型进行判别.这2种方法 5)Ripper. 的不足是，响应会给正常邮件的发送带来延迟，也会 和其他分类方法不同，Rippers41并不需要特征 占用网络带宽， 向量，它从训练样本集中归纳出分类的规则，通过一 3.3智能型垃圾邮件检测技术 系列相与或者相或关系的f-then规则组成， 1)质朴贝叶斯. 6)Rocchio. 该方法简便、有效，是商业软件中一种最常用的 这种类型的分类器5556]使用规范化的T℉-DF 方法，大量的工作表明这种方法是处理垃圾邮件最 来表示训练样本的向量.这种方法的优点是在训练 有效的方法之一，并且它能够取得较高的精确率 和测试中具有较快的速度，缺点是在训练集上搜索 (precision)和召回率(recal)[24].一些研究表明使 最优阚值(optimum threshold)以及最优B时会消耗 用多项式模型能够比使用多元伯努利(Bernoul山i)模 掉额外的训练时间，并且这些参数在测试集上的泛 型获得更高的正确率(accuracy)5).在传统的质朴 化特性也较弱 贝叶斯(naive Bayes)方法之上，衍生出了很多变体. 7)文本聚类 R.Shrestha等人[利用不同位置出现的同一关键 M.Sasaki等人[s提出基于特征空间模型的文 字的内部关联特性进行分类，计算关键字的协同权 本聚类方法，使用spherical k-means算法[s8]来自动 重(co-weighting）,并取得了性能上的提高.Li等 计算出不同的clusters,并对抽取出的质心向量 人【s提出了基于用户反馈的改进的naive Bayes方 （centroid vector)分配类别标记，通过计算新邮件向 法，获得了相对较低的丢失率(false positive)和较好 量和质心向量的距离来完成分类.该方法在Lng 的性能， Spam corpus数据库获得了较好的测试性能. 2)k-近邻方法. 8)元启发(Meta-heuristics). Sakkis等人[61将k-近邻方法（一种经典的惰性 C.Y.Yeh等人2针对关键字变化对基于关键 学习方法)应用于垃圾邮件检测领域.他们通过实 字的机器学习方法所造成的性能上的影响，提出了 验方法研究了领域大小(k的大小)、特征维数，以 使用spammers的行为作为区分特征，来进行邮件的 及训练集大小对检测器性能的影响.文中实验表明， 分类.这些行为特征通过Meta-heuristics来描述，在 k-近邻方法的平均性能优于贝叶斯方法， 给定的Meta-heuristics下，共抽取出了113个新的特 3)Boosting Trees. 征.实验结果显示这种方法要优于基于关键字的过 Schapire和Singer首先将该方法应用于文本 滤方式，并且训练时间也有了显著的降低 分类领域，通过组合多个基本假设(base hypotheses) 9)人工神经网络 来处理多类别(muli-class)以及多标签(muli-label) J.Clak等人[91利用人工神经网络自动分类邮 的分类问题.Carreras和Marquez]实现了AdaBoost 件，他们开发的系统Linger在Ling-Spam corpus数 算法用于反垃圾邮件的邮件过滤，在基于2个公共 据库获得了较高的正确率、召回率以及精确率.在 数据集(PU1 corpus和Ling-Spam corpus)实验的基 PU1 corpus上系统所获得的性能略有下降.I.Stuart 础上，他们得出Boosting Trees的方法在性能上要优 等人[6]基于词和消息的描述性特征，使用人工神经 于Naive Bayes、Decision Trees和k-NN算法.然而， 网络的方法对邮件进行分类，实验结果表明该方法 Nicholas49]认为使用decision stumps的Boosting 还需要对特征集作适当地扩充或者修改以获得性能 Tress以及AdaBoost在正确率和速度方面都要差于 上的提高
第3期 谭营，等：反垃圾电子邮件方法研究进展 ·197· 10)人工免疫系统 式中：n。表示被正确分类的垃圾邮件的数量，而 A.Secker等人「61]提出基于免疫的邮件分类算 n。1表示垃圾邮件被错误分类为正常邮件的数量。 AISEC(artifical immune system for e-mail classifi- 2)垃圾邮件精确率. cation).该算法旨在区分出用户感兴趣的邮件和不 该标准评估出系统检测垃圾邮件的精确性：度量 感兴趣的邮件.在不需要进行重新训练的前提下，算 被系统分类为垃圾邮件的邮件中，分类正确的比例.这 法能够连续地对e-mail进行分类处理，并能够及时 个标准另一方面也能够反映出被系统错误分类的正常 地追踪用户兴趣的变化. 邮件所占的比例.系统垃圾邮件精确率(spam preci- T.Oda等人[2]将人工免疫模型应用于垃圾邮 sio)越高，被系统错误分类的正常邮件的数量也就越 件处理，主要利用免疫中自己/异己(self/non-self) 少.垃圾邮件精准率计算方法如下所示： 的检测原理和检测器(dector)的概念.在实现的邮 P。= 几gw 件过滤系统中，首先从多样的来源中构建基因库，这 nm+n 些来源包括语言中的词汇、所收集的邮件中的词汇 式中：1表示正常邮件被错误分类为垃圾邮件的数量， 和词组、垃圾邮件中的联系信息和邮件头信息等.在 3)正常邮件召回率和正常邮件精确率 系统初始化的过程中，使用随机的方法从基因库中 由于垃圾邮件检测是关于两类邮件的（正常邮 生成抗体(antibody)及其关联的淋巴细胞(lympho- 件和垃圾邮件)，这2种标准与垃圾邮件召回率和 cyte).在构建的过程中，不允许相似抗体的重复产 精准率是对称的，计算式也可以对称地推导出来 生，每个淋巴细胞除了具有抗体属性外，还有msg 4)准确率. matched和pam_matched2个属性与其关联，分别 该标准能够反映邮件过滤系统的整体性能.它 用于表示淋巴细胞所匹配的邮件的数目和垃圾邮件 能够表示被正确分类的邮件（包括正常邮件和垃圾 的数目.在对淋巴细胞的训练过程中，对发生匹配的 邮件)的比例，被定义如下： 淋巴细胞修改其msg_matched和spam_matched这2 A=乃+乃 个属性的值.在系统的运行过程中，使用了带权平均 n+na 值的评价方法对邮件的类别进行判断，在这种评价 式中：n1表示被正确分类的正常邮件的数量，m1和 方法下，匹配次数多的淋巴细胞在评分中具有较大 n.分别表示正常邮件和垃圾邮件的总体数量. 的权重。 5)加权准确率。 研究人员观察得出，正常邮件的丢失（被系统 4性能评估方法及标准数据集 错误过滤掉)意味着人们会错过生活中的重要信 垃圾邮件检测技术仍是现今国内外研究热点之 息，比垃圾邮件的错误分类要严重得多.为了反映出 一，大量的相关工作不断涌现出来.为了便于人们比 正常邮件的重要性，研究人员在准确率的基础上，定 较和选择合适的垃圾邮件过滤方法，研究人员提出 义出如下加权准确率： 一些评估标准来对比不同过滤方法、系统的性 能21).本节主要介绍并分析几种常见的性能评估 A.=htmd An+n 方法，并给出一些标准数据集， 式中：入是反映正常邮件重要性的参数，它的值越 4.1性能评估方法 大，说明正常邮件在该情景下的重要性越强，一般可 1)垃圾邮件召回率. 以取值9、99或999.若将入赋值为999，则表明正常 该标准能够度量出被算法模型正确检测、分类 邮件在该情景下极为重要.当入取1时，加权准确率 的垃圾邮件的比例.垃圾邮件召回率(spam recall) 与准确率标准等价 高的系统模型能够更好地将垃圾邮件过滤掉，更有 6)Fg度量. 效减少垃圾邮件对人们生活的妨碍.下式给出垃圾 垃圾邮件召回率与精确率只能分别反映系统的 邮件召回率的计算方法， 单一方面，不能够反映系统整体的性能.为了解决这 R。= T几。e 一问题，F。度量被定义为这2种标准的融合，如下式 n,格十乃ga 所示：
·198 智能系统学报 第5卷 RP。 适应性). FB=(1+B) BP。+R。 Z1数据集是中文邮件数据集「66]，其中的邮 式中：β表示精确度的权重，反映精确度相对召回率 件已进行过中文分词处理，处理后的单词被映射为 的重要性.在大多数研究中B取值1，该情况下，称该 整数，以保护邮件所有者的隐私.该数据集包含 标准为F度量. 1633封邮件，其中正常邮件428封，垃圾邮件比例 4.2标准数据集 为73.79%.数据集中正常邮件平均长度为819.06 2000年，Androutsopoulos等人[4s]整理发布了 个单词 LingSpam数据集4]，该数据集是早期的经典邮件分 类数据集之一：该数据集共包含2893封邮件，其中 5总结及展望 正常邮件2412封，垃圾邮件比例为16.63%.该数 在现有的反垃圾电子邮件技术方法中，智能型反 据集中的邮件都经过了预处理，所有头信息（标题 垃圾邮件技术方法仍然是最有效、最有前景的方法.法 除外)、HTML标记均已被去除.该数据集的不足是， 律手段和简单方法只能对部分符合定义特征的垃圾电 正常邮件的内容大多与语言学话题有关.用该数据 子邮件起一定作用，且这2种方法不具备自适应性，不 集评估邮件检测系统会带来过于乐观的估计. 能有效过滤垃圾邮件的变种.在智能型反垃圾邮件技 2004年，Androutsopoulos等人I4经过收集、整 术方法中，邮件特征提取方法起着至关重要的作用，将 理又发布了PU系列经典数据集，该数据集被广泛 直接影响反垃圾邮件系统的各项性能. 应用于现今各种垃圾邮件过滤系统的性能评估.PU 邮件特征提取是反垃圾邮件系统的核心部分， 系列数据集中包含着4个独立的数据集： 对系统的分类性能起着决定性作用.目前，绝大多数 1)PU1:该数据包含1099封邮件，其中垃圾邮 邮件集中于文本、图片类型.基于文本、图片的邮件 件481封.该数据集中的正常邮件和垃圾邮件均为 特征提取方法有着良好的应用前景，是当今的研究 英语书写的邮件.正常邮件是文中的第1位作者4] 热点.基于行为的邮件特征提取方法，是一种与邮件 在36个月的时间里收集到的，而垃圾邮件是他在 类型无关的特征提取方法，该方法通过区分垃圾邮 22个月的时间内收集的. 件、正常邮件发送过程中表现出的不同行为，过滤垃 2)PU2:该数据集包含721封邮件，其中有142 圾邮件，是一种有效、鲁棒性强的方法，非常值得进 封垃圾邮件.与PU1相似，该数据集中的邮件也都 一步地研究与探讨.新的邮件特征提取方法的研究， 是英语邮件.文中作者的一位同事在22个月的时间 将极大地推进反垃圾邮件系统的发展 内收集保存了这些邮件， 现有的反垃圾邮件相关法律，对垃圾邮件发送行 3)PU3:该数据集包含4139封邮件，其中有 为进行了一定的限制.然而，现有的相关法律，并不能 1826封垃圾邮件.与PU1、PU2不同，该数据集同时 从根本上解决垃圾邮件问题，需要反垃圾邮件技术的 包含英语邮件和非英语邮件.数据集中的正常邮件 协同支持.现有的相关法案也急需进一步完善 是文中的第2位作者收集的，而垃圾邮件来自其他 智能型反垃圾邮件技术是在简单反垃圾邮件方 邮件数据集， 法的基础上，发展出的新型反垃圾邮件技术.该技术 4)PUA:该数据集包含1142封邮件，其中572 在提取邮件特征的基础上，运用现代机器学习方法 封垃圾邮件.与PU3相似，该数据集也包含部分非 等各种智能方法对邮件类型（是否为垃圾邮件）进 英语邮件，垃圾邮件同样来自其他数据集，数据集中 行分类，以过滤垃圾邮件.新的智能型方法的提出及 的正常邮件是文中作者的另一位同事收集提供的. 其在反垃圾邮件领域的应用将是未来的研究方向， 另外，Medlock[6a]也整理发布了一个大规模邮 具有很大的发展前景 件数据集GenSpam[64]:该数据集由3部分组成：训 练集（包含8018封正常邮件，31235封垃圾邮件）、 参考文献： 测试集（包含754封正常邮件，797封垃圾邮件）、自 [1]CRANOR L F,LAMACCHIA B A.Spam![J].Communi 适应集（包含300封正常邮件，300封垃圾邮件，该 cations of the ACM,1998,41(8):74-83. 部分集合用于测试垃圾邮件过滤系统的动态性、自 [2]GANSTERER W,ILGER M,LECHNER P,et al.Anti-