第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维的特征向量<1， 现的平均频率， x2,…,x>,其中每维特征值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种簇模 被直接拒绝掉，而不会进入下一个阶段，这样做能够 式：用户簇模式和群落簇模式