垃圾邮件的识别和过滤方法详解.docx
- 文档编号:8965682
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:13
- 大小:237.10KB
垃圾邮件的识别和过滤方法详解.docx
《垃圾邮件的识别和过滤方法详解.docx》由会员分享,可在线阅读,更多相关《垃圾邮件的识别和过滤方法详解.docx(13页珍藏版)》请在冰点文库上搜索。
垃圾邮件识别和过滤的方法
谈兆年
北京理工大学计算机学院07111301班,北京100081
(1120131743@)
MethodsforIdentifyingandFilteringJunkMailorSpam
Tan Zhaonian
(Class07111301,SchoolofComputerScience,BeijingInstituteofTechnology,Beijing100081)
Abstract IdentifyingandFilteringSpamisanimportantresearchsubjectincomputernetwork.Inthisthesis,Ihavestudiedthehistoryofspamfilteringtechnology,whichmainlyincludesthefirstgenerationofrule-basedfilteringtechnology,thesecondgenerationofcontent-basedfilteringtechnologyandthethirdgenerationofbehavior-basedfilteringtechnology.1.Rule-basedfilteringincludesIPaddressbasedfiltering,mailheaderbasedfiltering.2.Content-basedfilteringincludesBayesianfiltering,Memory-basedmethod,decisiontree,Boostingmethod,SupportVectorMachine(SVM),etc.3.Behavior-basedfilteringincludesEmaildatastreambasedfiltering,mailheaderbasedfiltering,senderreputationbasedfiltering,mailfingerprintbasedfiltering,behavioralcharacteristicsweightedbasedfiltering,etc.Thespammers’commonspuriousmethodsaresummarized.Throughthereferencetolargeamountofanti-spamdocumentsanddatafromhomeandbroad,ananalysisismadeonexistinganti-spamtechniquesandinparticularthecontent-basedspamfilteringmethods.
Keywords spamfiltering;rule;content;textcategorization;NaïveBayes;behavior
摘要 垃圾邮件识别和过滤是计算机网络领域的一个重要研究课题。
垃圾邮件识别和过滤目前已经发展出了三代技术,第一代过滤技术是基于规则的,例如:
基于IP地址、基于邮件头的过滤技术。
第二代过滤技术是基于内容的,例如:
贝叶斯分类算法、Memory-Based方法、决策树、Boosting方法、支持向量机等方法。
第三代过滤技术是基于行为的,例如:
基于邮件数据流、基于邮件头信息、基于发送方信誉、基于邮件指纹、基于行为特征加权的决策树等过滤方法。
本文归纳总结了当前垃圾邮件发送者经常采用的欺骗手段和方法,并参阅国内外大量反垃圾邮件文献和数据,对已有的垃圾邮件技术作出分析和总结,尤其是对基于内容的垃圾邮件过滤方法进行了研究。
关键词 垃圾邮件过滤;规则;内容;文本分类;简单贝叶斯;行为
随着互联网的发展,垃圾邮件常常让人头痛不已,最新报告称美国为垃圾邮件第一大国,中国排名第三(图1)[1]。
垃圾邮件问题如今已经成为一个社会热点,近些年来,研究人员们提出了很多垃圾邮件识别和过滤的方法。
这些方法的发展经历了三代,第一代过滤技术是基于规则的,例如:
基于IP地址、基于邮件头的过滤技术。
第二代过滤技术是基于内容的,例如:
贝叶斯分类算法、Memory-Based方法、决策树、Boosting方法、支持向量机等方法。
第三代过滤技术是基于行为的,例如:
基于邮件数据流、基于邮件头信息、基于发送方信誉、基于邮件指纹、基于行为特征加权的决策树等过滤方法。
本文归纳总结了当前垃圾邮件发送者经常采用的欺骗手段和方法,并参阅国内外大量反垃圾邮件文献和数据,对已有的垃圾邮件技术作出分析和总结,尤其是对基于内容的垃圾邮件过滤方法进行了研究。
图 1 世界垃圾邮件最多国家排名
Fig.1CountryRankingonSpam
1基于规则的垃圾邮件过滤
1.1 基于IP地址的垃圾邮件过滤方法
基于IP地址的过滤技术是目前使用最为广泛的一种过滤技术,包括基于网络的IP地址过滤技术,如BGP和路由器访问控制列表;基于主机的IP地址过滤技术,如TCP Wrappers和主机路由表的过滤;以及目前最常用的IP地址黑、白名单的过滤[2]。
黑白名单技术基于这样的界定:
白名单中的任何邮件都是合法邮件,而黑名单中的任何邮件都是垃圾邮件。
故通常会收集一个黑白名单的列表,这个列表里的内容可以是电子邮件地址或邮件服务器的域名、IP地址等,收到邮件时进行实时检查,将符合黑名单的邮件放入垃圾文件夹中。
黑白名单一般由权威的组织提供,如中国互联网协会等。
个人也可以根据需要调整自己的黑白名单。
基于IP地址的过滤技术实现起来简单方便,可以应用与多个层次。
但是缺点是可能会伤及无辜,因为有一些垃圾邮件是通过别人的服务器来转发的,这样就会将别人无辜的服务器给屏蔽掉。
所以,黑白名单具有一定的局限性。
1.2基于邮件头的垃圾邮件过滤方法
基于邮件头的过滤技术主要是使用正则表达式对邮件头进行关键字的匹配,检查发件人的信息是否符合过滤要求,根据匹配结果决定阻塞或者接收具有特定单词或短语的邮件。
注意理解以下几点有助于识别含有伪造内容的信头。
(1)收件人地址和发件人地址
一般的MUA是从用户在SMTP的DATA命令后输入的数据中提取From、To等字段的内容的,但是如果发件人的MUA不是按照这个逻辑工作,或者发件人故意让这两个字段的内容与SMTP会话时使用的MAIL FROM和RCPT TO的内容不一致时,就会发生发件人是自己的名字或者收件人不是自己的名字等情况。
(2)关于Open Relay
如果发件人使用的不是自己的服务器,而是使用别人的服务器的OpenRelay的漏洞,这样就会给追踪邮件的真实来源带来困难。
如果一个邮件服务器和发件人、收件人都不属于同一个域,就应该怀疑是否使用了OpenRelay。
(3)Received信息
邮件头中的Received信息是由SMTP服务器自动加入的,发送者无法干预,因此,通过比较Received域,特别是第一次经过的邮件服务器的Received域,可以识别出伪造的发件人地址。
但是,规则匹配的方法也有不妥之处,其缺点是规则是人工指定的,需要花费时间和精力去收集信息,更新信息,这无疑是一项持久繁琐的工作。
2基于内容的垃圾邮件过滤
由于上述基于规则的过滤方法的缺陷,故发展出一套新的方法:
基于内容的垃圾邮件过滤方法。
对电子邮件的内容(如正文)进行分析,识别出垃圾邮件。
这就将垃圾邮件过滤和文本分类和信息过滤联系起来了,将文本分类和信息过滤中常用的方法引入垃圾邮件过滤任务中。
这种内容过滤技术提供了更为准确的邮件过滤方法,可以自动获取垃圾邮件的特征,并即时捕捉到垃圾邮件特征的变化[3]。
2.1 垃圾邮件过滤与文本分类
文本分类的首要任务是根据预先确定好的类别体系,将待分类文本分到对应的类别中去,具体来说,就是将邮件分为合法邮件和垃圾邮件。
我们可以将电子邮件经过处理获取其正文的文本内容,利用文本分类的算法识别垃圾邮件。
但是垃圾邮件分类与一般的文本分类也有很多不同之处。
主要有:
(1)对文本分类,每个类别的内容一般不会经常改变。
比如说,一个文本属于科技类,将来也还会属于科技类。
而垃圾邮件的类别是跟用户的个性化需求相关的,用户对于垃圾邮件的判别可能会随着时间的推移而改变的。
同时,垃圾邮件的形式和内容也在不断地变化,因此垃圾邮件过滤中要向用户提供自学习、反馈的机制,以便适应新情况。
(2)无论对于邮件服务器还是对用户客户端,垃圾邮件过滤对时效性的要求比较高,因此要求必须采用高效的分类算法。
(3)在垃圾邮件过滤中我们最不愿看到的就是将合法邮件误判为垃圾邮件,这就要求过滤算法具有较高的准确率。
2.2垃圾邮件过滤与信息过滤
信息过滤(InformationFiltering)是从动态的信息流中找出与用户兴趣需求相关的信息的过程[4]。
以文本过滤为例,将新到达的文档与用户的兴趣相匹配,把系统认为与用户相关的文档推送给用户,用户给予反馈,说明被推送的文档中有哪些是他感兴趣的,哪些是不感兴趣的。
系统从反馈中自动更新用户的兴趣。
文本分类可以看做是一个反馈学习的二值分类问题。
信息过滤系统的一般组成为图2所示。
图 2 信息过滤系统
Fig.2InformationfilteringSystem
可以认为垃圾邮件内容过滤是这样的一个信息过滤问题:
初始时,提供一定的垃圾邮件和非垃圾邮件给过滤系统学习,得到过滤模型;过滤的信息源是动态的邮件流;用户可以指定自己的垃圾邮件集和非垃圾邮件,供系统反馈学习,建立新的过滤模型。
2.3文本分类简介
文本分类的任务是:
在给定的类别体系下,根据文本的内容,将其自动映射到指定的类别中去。
类别体系一般由人工按照应用需求构造。
基于内容的文本分类需要指导,即一定数量的已分类好的训练文本或者实例,分类系统从训练文本中获取必要的信息,构造分类器。
因此文本分类一般都由训练过程和分类过程两阶段构成(图3)。
文本分类技术的应用很广泛,如新闻网页的分类、电子图书的分类等等。
图 3 文本分类器的一般模型
Fig.3ModelofTextCategorization
在文本处理领域,通常采用向量空间模型(VSM,Vector SpaceModel)表示文本,一篇文本可以表示为一个维文本向量(w1,w2,…,wn),其中,wi(i=1,2,…,n)表示第i个特征项的权重,n是特征项的个数,特征项可以是字、词、短语或某种概念,本文中采用词作为特征项。
权重有多种计算方法,最简单的是布尔权重,即权重为1(该特征项在文本中出现)或者0(该特征项没有在文本中出现)。
更通常的情况下,VSM中的权重计算采用词频(TF,Term Frequency,表示该特征词在文本中出现的次数)和文档频次(DF,DocumentFrequency,表示出现该特征词的文档数量)的某种组合。
解决了文本表示问题之后,我们可以将文本分类抽象为一般的描述:
设类别总数为|C|,cj表示第jj=1,2,…,|C|类,提供给分类器的训练集(训练集中的文本都已经过人工分类)包含|D|篇文本,特征空间(t1,t2,…,tn),n为特征数量,每篇文本表示成di=(wi1,wi2,…,win),i=1,2,…,|D|。
一篇待分类文本泛化表示为dx=(wx1,wx2,…,wxn),任务是将dx分到相应的类别中去。
2.4 特征选择方法
训练集中包含了大量的词汇,如果把这些词都作为特征,将带来一系列问题。
首先是向量的维数太大,给计算带来了非常大的压力,存储空间大、处理速度慢。
其次是这些词中实际上有很大一部分是与类别无关的,对分类作用不大。
因此,我们要降低向量的维数,选择那些有代表意义的词作为特征。
先对文本进行预处理,去掉那些常用的对分类用处不大的词(称为停用词,stopword),然后采用某种特征选择方法对所有的词排序,选出排在前面的一定数量的词作为特征。
常用的特征选择方法有[5]:
2.4.1文档频次
文档频次(DF)是出现特征项的文档数量。
通常认为DF太小的词没有代表性,而DF太大的词又没有区分度,所以基于DF的特征选择方法只留下那些DF介于中间的词作为特征。
2.4.2互信息
互信息即MutualInformation,简称MI,定义如下:
MIt=i=1|C|P(ci)logP(t|ci)P(t)
Pci表示第i类文本在训练文本集合中出现的概率,P(t) 表示t在训练集合中出现的概率,P(t|ci)表示在第i类文本中t的出现概率。
MI越大,词和类的共现程度越大。
2.4.3信息增益
信息增益即InformationGain,简称IG,定义如下:
IGt=-i=1CPcilogPci+Pti=1CPcitlogPcit+Pti=1|C|P(ci|t)logP(ci|t)
IGt反映了该词为整个分类所提供的信息量。
上式中,Pt表示词t不出现的概率,Pcit表示词t出现的情况下文本属于ci类的概率,P(ci|t)表示词t不出现的情况下文本属于ci类的概率,下面的公式中相应变量的含义与此相同。
2.4.4 χ2统计量
χ2t,ci=N×(AD-BC)2(A+C)×(B+D)×(A+B)×(C+D)
χ2avgt=i=1CP(ci)χ2t,ci
A、B、C、D均表示文本数量,如表1所示,N=A+B+C+D。
表1 文本种类划分
Table 1 DivisiononTextCategorization
ci类文本集合
非ci类文本集合
t出现
A
B
t不出现
C
D
χ2统计量度量词和类别独立性的缺乏程度,χ2越大,独立性越小,相关性越大。
χavg2表示对所有类别求平均的χ2统计量。
2.4.5相对熵
CEt=i=1|C|P(ci|t)logP(ci|t)P(ci)
也称为KL距离(Kullback-Leiblerdivergence),反映了文本类别的概率分布和在出现了某个词的条件下文本类别的概率分布之间的距离,该值越大,词对文本类别分布的影响也大。
2.4.6优势率
即OddsRatio,用于二类分类问题:
ORt=logP(t|c1)(1-P(t|c0))(1-P(t|c1))P(t|c0)
2.5垃圾邮件内容过滤中应用的文本分类方法
以下介绍已经应用于垃圾邮件内容过滤的一些算法。
多种分类方法和机器学习理论都可以应用于垃圾邮件过滤[6],包括贝叶斯分类器(Bayesian Classifiers)、Memory-Based方法、决策树(Decision Trees)、Boosting方法、支持向量机(Support VectorMachine,SVM)等等。
2.5.1贝叶斯分类算法
贝叶斯分类器是一类常用的分类器,最基本的形式是简单贝叶斯(NaïveBayes,也称为朴素贝叶斯)分类器。
其原理是计算文本dx属于某个类别的概率P(cj|dx),将文本分配到概率最大的类别中去。
计算P(cj|dx)的时候,利用了贝叶斯公式:
P(cj|dx)=P(cj)P(dx|cj)P(dx)
P(cj)是类的先验概率,P(dx|cj)是类条件概率。
对同一篇文本,P(dx)不变,设dx表示为特征集合(t1,t2,…,tn),n为特征个数,假设特征之间相互独立,则有:
Pdxcj=Pt1cj*Pt2cj*…*Ptncj=i=1nPticj
P(cj)和Pticj都可以利用训练集估计。
简单贝叶斯分类器是垃圾邮件内容过滤中广泛应用的文本分类方法[7][8]。
利用这种方法,可以根据训练集自动训练,训练的结果反映了训练集的性质。
因此邮件用户可以提供一定数量的垃圾邮件和非垃圾邮件,训练自己的垃圾邮件过滤器,从而反映用户自己的个性需求。
Sahami等人提出了一种多特征融合的贝叶斯过滤方法。
特征选择时,一般是从训练集中提取一定数量的词汇作为特征,而他们除了选择词汇特征之外,还将一些“非文本”的特征加入到特征空间中,如邮件标题中包含特定的短语“free、only$、beover18、…”以及邮件发送者的域名信息等等。
加入这些特征后,与词汇特征一起处理,应用贝叶斯分类算法。
2.5.2Memory-Based方法
Memory Based也叫Instanced Based,是基于实例的方法。
我们以k近邻(kNN,k-NearestNeighbor)方法为例说明这种方法的基本原理。
k近邻是Memory-Based的一种,它直接利用训练集分类:
计算待分类文本与每一篇训练文本的距离,找出最相近(最相似)的k篇文本,然后根据文本所属类别划分这k篇文本,将待分类文本分到包含文本数最多的那一类中去。
计算文本之间的相似度有多种方法,最常用的就是计算两个文本向量之间的夹角余弦值。
Androutsopoulos等人将MemoryBased方法应用在垃圾邮件过滤上[8],取得了较好的结果。
2.5.3决策树
决策树(Decision Tree)方法的实质是从训练集中学习得到以决策树的形式表示的分类规则。
分类时,将待分类的文本按照属性值自树根向下逐步比较判断,到叶子结点时,就可以确定文本所属类别。
一棵最简单的决策树结构如图4所示。
树的内部结点表示属性或者属性的集合,分支上的权值表示属性的取值,叶子结点是类别。
图中,实例空间分为三类:
1、2和3,如,当属性A的取值为a2,属性B的取值为b2,属性C的取值为c1时,属于类别1。
决策树实际上就是一系列规则的形式化表示,如“如果属性A取值为a2,属性B取值为b2,属性C取值为c1,则属于类别1”。
训练的过程就是从样本中学习决策树或者说是学习规则,分类的时候就是沿着决策树往下走到叶子,找到类别归属。
图 4 决策树
Fig.4DecisionTree
2.5.4Boosting方法
先介绍两个概念:
定义“强规则(或强假设)”为准确率很高的分类规则(或假设),“弱规则(或弱假设)”为准确率不高,仅比随机猜测略好的分类规则(或假设)。
最简单的弱假设 h(x)可以这样定义:
hx=+1,如果x满足某个断言p-1,x不满足p
弱规则比较好寻找,而强规则较难。
一个很自然的想法就是通过一定的训练方法逐步将一系列弱规则集合提升为强规则,这就是Boosting方法的由来。
Boosting方法的基本思想是:
给每个训练样本都赋予一个权重,进行T次迭代,每次迭代后,对分类错误的样本加大权重,使得下一次的迭代更加关注这些样本。
Boosting方法有多种形式,如AdaBoost、AdaBoost.M1、AdaBoost.MH等。
下面以AdaBoost为例介绍Boosting方法。
考虑某个类别(对于多个类别,可以训练出多个分类器),将训练集表示为S=X1,Y1,X2,Y2,…,XN,YN,其中,Xi(i=1,2,…,N)是文本表示,N是训练集中的样本数量Yi=1表示Xi属于某个类别,等于0表示不属于这个类别。
AdaBoost学习算法描述如图5所示:
Boosting开始时,每个样本的权重都初始化为1/N。
每一步t中,使用弱规则对样本的类别作出预测,计算错误率εt和弱规则的权重系数αt,然后分别更新预测正确和错误的样本权重。
Zt是标准化变量,使样本的权重和为1。
T为Boosting的次数。
最后,输出分类规则H。
图中,规则H是各个弱规则的线性组合的符号函数。
图 5 AdaBoost学习算法
Fig.5AdaBoostAlgorithm
2.5.5支持向量机
支持向量机(SupportVectorMachine,简称SVM,也叫做支撑向量机)是在二十世纪90年代以来发展起来的一种统计学习方法,在解决小样本学习、非线性及高维模式识别问题中表现较好。
如图6所示,图中的实心点和空心点分别表示两类的训练样本,考虑线性可分的情况,即通过一条直线H可以把两个类别无错误的分开,H1和H2分别为过各类样本中离分类线最近的点且平行于分类线H的直线,H1和H2之间的距离叫做两类的分类空隙或分类间隔(margin)。
最优分类线定义为:
该分类线不但能将两类样本分开,而且要使两类的分类间隔最大。
直线H1、H2上的训练样本叫做支持向量(SupportVectors),因为它们支撑了最优分类面。
图5中的分类线H是最优分类线。
推广到高维空间,最优分类线就成为最优分类面。
图 6最优分类面
Fig.6OptimalSeparatingPlane
对于线性不可分的情形,可以构造一个变换,将问题转换到一个新的空间,在这个新空间中线性可分。
支持向量机的基本思想可以概括为:
首先将输入空间变换到一个新空间,然后在这个新空间中求取最优线性分类面。
Drucker、Androutsopoulos等人在垃圾邮件过滤中使用支持向量机方法[9]。
3基于行为的垃圾邮件过滤
行为模式是指程序执行或者用户操作过程中体现出的某种规律,行为模式通常反映出用户的身份和习惯[10]。
行为识别技术根据邮件发送过程中表现出来的行为特征来判断邮件是合法邮件还是垃圾邮件。
行为模式识别能在邮件传输代理阶段,针对垃圾邮件在通信过程中表现出来的特征在其投放到邮件发送队列之前进行判断和处理,如“频繁发送、动态IP、Received域与发件人域不相同”等,这些特征都是垃圾邮件表现出来的行为特征。
行为模式识别不需要对整个邮件内容进行判断,只需要在邮件传输阶段进行检测,这大大提高了服务器过滤垃圾邮件的速度,减小网络负荷和流量,同时也不会解析用户的邮件,对用户的隐私起到了很好的保护作用[11]。
目前基于行为识别模式的垃圾邮件过滤已经成为垃圾邮件过滤技术领域的主要研究方向,国内外针对垃圾邮件的行为识别技术已有较多的研究与应用。
下面简要介绍几种方案:
3.1基于邮件数据流的过滤方法
恶意邮件跟踪系统是一款由哥伦比亚大学研发的基于行为识别的电子邮件系统[12]。
该系统通过对用户的邮件数据流和发送接收行为建立模型,使用模型来检测异常电子邮件行为,包括垃圾邮件和传播病毒的电子邮件行为。
每封邮件的附件均会由系统生产一个唯一标识符,如果某个标识符所代表的的附件被判定为垃圾邮件属性,其相对应的行为信息将被系统记录。
整套系统由一个运行在邮件服务器的客户端和一个运行在中央服务器的服务器端组成,客户端记录邮件附件的行为信息及其数据流,服务器端分析由客户端上传的数据。
3.2基于邮件头信息的过滤方法
目前采用提取电子邮件头信息,然后分析其每个字段特征来识别垃圾邮件,根据各个字段之间关系来判断邮件分类的方法很多。
例如张耀龙[13]采用决策树算法生成垃圾邮件决策树判定模型来识别垃圾邮件,主要是提取发件人域名、IP、各个字段
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 垃圾邮件 识别 过滤 方法 详解