NSC:一种新型的垃圾邮件过滤器-上海联兵环保免费电话：400-600-5030

摘 要:借鉴生物免疫系统能有效的区别自体与非自体防御外部病源体入侵的工作机制,结合用户行为特征模式,提出了一种基于免疫机制的垃圾邮件过滤器模型NSC.在该模型中,给出了自体、非自体、抗体和抗原的定义与实现方式,建立了抗体的克隆选择、学习机制和生命周期模型.详细的描述了模型的训练与检测过程.试验结果表明,基于免疫机制的过滤器不仅有效的提高了检测率,而且还表现出良好的自学能力与自适应性.
关键词:人工免疫;垃圾邮件;负向选择;克隆
中图分类号:TP309
文献标识码:A
文章编号:1000-1220(2008)01-0158-04
1 引 言
随着计算机与通信技术的发展,电子邮件已经成为现代人之间一个不可缺少的、重要的通讯方式.但随之而来的垃圾邮件的泛滥让整个Internet不堪重负,阻碍网络正常信息的传递,浪费电子邮件用户的时间与精力,甚至有些垃圾邮件对网络安全构成威胁.因此控制垃圾邮件的泛滥成为目前技术研究的热点之一.
目前国内外采用的垃圾邮件过滤方法主要有三种:安全认证方法,基于规则的方法与基于统计的方法[1].安全认证方法,如change/response,这种方法要求发信方在发送邮件之前必须在接受方的邮件服务器注册获取授权,否则,邮件服务器将拒绝接收邮件.这种方法具有较高的安全性,但电子邮件的易用性却受到很大的影响.基于规则的方法根据用户自己的兴趣爱好预先制定一系列规则,凡是不符合规则的邮件,将不会提交给用户,典型应用有黑名单与白名单.虽然这种方法有很大的灵活性,但用户的兴趣随时随地都在改变,需要用户随时的更新规则,对用户要求较高,时效性较差.基于统计的方法,采用标记权重的方法,对标定垃圾邮件与非垃圾邮件的语料进行统计计算,产生过滤规则,判定垃圾邮件的准确性有较大的提高,但需要用户干预,不适应增量式的反馈学习[2-4].
生物免疫系统是目前已知的最精妙复杂的抵御外部有害物质的系统,它犹如一支训练有素的精锐部队,捍卫人体的健康[5-6].免疫系统可以使生物体免于病毒、细菌、污物物资及疾病的攻击,同时免疫细胞能对入侵者产生免疫记忆,当下次同样的抗原入侵时,免疫细胞能迅速识别并消灭该抗体.反垃圾邮件系统与生物免疫系统具有惊人的相似性,两者都要在不断变化的环境中识别非自体或垃圾邮件,并将之清除,同时免疫系统具有良好的多样性、耐受性、免疫记忆性与分布式并行处理.所以本文借鉴生物免疫系统工作机理,提出了一种基于免疫机制的垃圾邮件过滤器模型NSC,在该模型中,给出了自体、非自体、抗体和抗原的定义与实现方式,建立了抗体的克隆选择、学习机制以及生命周期模型.详细的描述了模型的训练与检测过程.试验结果表明,基于免疫机制的过滤器不仅有效的提高了检测率,而且还表现出良好的自学能力与自适应性.
2 模型实现
2.1 概 述
基于免疫机制的垃圾邮件过滤器模型可以用一个四元组来描述.
S=(E,P,N,F) (1)
式中,E为输入到过滤器中待检测的邮件,N为经过过滤器过滤输出的非正常邮件,F为输入邮件与输出邮件之间的关系函数.P为基于免疫机制垃圾邮件过滤器内部组成,可以表示成
P=(apc,toleance,clone) (2)
其中,apc为抗原提呈模块,tolerance为耐受模块,clone则为克隆模块.apc的作用是将半结构化的电子邮件转变成系统可以识别的形式.耐受模块负责将未成熟的抗体训练成为成熟的抗体.克隆模块则负责邮件的检测以及在现有记忆抗体的基础上生成适应度更好的抗体.
表1 生物免疫系统与基于免疫的垃圾邮件过滤模型映射关系

为了更加清楚地阐述论文,表1给出了生物免疫系统与基于免疫的垃圾邮件过滤器模型的映射关系.
2.2 抗原提呈
在生物免疫系统存在一种叫做吞噬细胞的免疫细胞,由它对吞入的抗原进行加工处理,然后将抗原信息提呈给T细胞,T细胞再提呈给B细胞发生免疫应答.与之类似,对于基于免疫机制的垃圾邮件过滤器而言,它并不具备人类的智能,能够阅读邮件.所以,要实现垃圾邮件过滤,必须要将待检测的邮件转变成计算机可以识别的形式,即抗原提呈.
根据“贝叶斯假设”,可以使用文本中出现的字或词的集合代替文本.虽然这样会丢失大量的关于文章内容的信息,不过这种方式可以使文本的表示与处理形式化.由GerardSalton提出的向量空间模型(Vector Space Model VSM)[7]是目前最好的文档表示模型.该模型以特征项(Feature)作为文档表示的基本单位,特征项由字,词和短语组成,每个文档表示为一个范化的特征向量V=(t1,t2,…,tn),其中ti为特征词.
电子邮件是一种半结构化的特殊文档,由信头与信体两部分组成.信头包括发信者的IP地址、邮件地址和邮件标题等信息.正文则是该邮件的全部内容.
对于信头而言,抗原提呈模块仅提取发送者地址,主题与第一个邮件服务器地址.邮件的标题一般概括了其主要内容,发送者地址则包含邮件发送者的相关信息,这两部分信息是过滤模型判断邮件是否为垃圾邮件的重要依据.取第一个邮件服务器地址的原因是因为发送者的E-mail可以伪造,第一个邮件服务器可以可靠的反映垃圾邮件发送者的部分信息.信头的其它部分如路由信息对于邮件类型的判别没有太大的帮助,可以忽略掉.
信体部分采用词带法[8-9]表示,根据特征词的位置与权值选取若干特征词用来代表某一个文本.每个特征词的权值由公式(3)确定:

2.3 自体耐受
定义1.自体与非自体:系统监控的邮件可以抽象为一个由维度不定的特征词串组成的特征向量集合E.集合E分为两个子集:自体集合(正常邮件)S,非自体集合(垃圾邮件)T.S和T满足下面两个关系:E=S∪T和S∩T=Ф.
定义2.抗体与抗原:定义抗原集合为对待检测邮件进行抗原提呈后得到的特征向量集A={a a=<发件人地址,第一个邮件服务器地址,主题,特征词1,特征词2,…特征词n>}.定义抗体集合D={d d=,s∈E,age,count,id∈N},每个抗体为一个四元组,其中s为抗体的特征向量,age为抗体的年龄,count为抗体的累计亲和力,即该抗体匹配到的抗原数目,id用于唯一表示抗体,N为自然数集合.抗体与抗原的匹配采用基于特征词的海明距离匹配
算法,算法详细过程描述如下.
算法1.基于特征词的海明距离匹配算法
输入:抗原,抗体特征向量
输出:抗原与抗体特征向量的亲和力
Step 1.分别计算抗原与抗体特征向量的维度leng,lenb;
Step 2.根据特征串的长度将抗原与抗体向量分别赋值给strshort与strlong;
Step 3.计算短特征串包含的特征词出现在长特征串中的个数,并将此赋值给变量count;
Step 4.用count除以长特征串的维度,此值即为亲和力;
Step 5.将计算出来的亲和力值返回给函数调用者.
定义3.基因库:由垃圾邮件包含的特征词构成的词库.模型中包含两个词库.一个用于存储信头部分的特征词,另一个由表征信体部分的特征词构成.
为了防止抗体匹配到自体,由基因库中随机抽取基因新生成的抗体必须通过自体耐受才能与抗原匹配,对新生成的抗体ab可以用公式(4)进行自体耐受,其中1表示通过自体耐受,0表示没通过自体耐受,ab∈D.

通过自体耐受的抗体成为成熟抗体,开始担负起检测邮件的任务.一旦被检控的邮件集合中有邮件与成熟细胞的亲和力超过匹配阈值,系统认为该邮件为垃圾邮件,将该邮件发送到可疑邮件夹中并同时附上检测出该邮件的抗体id信息.成熟抗体如果其累计亲和力超过一定的阈值θ,就会被激活成为记忆抗体.记忆抗体的工作与成熟抗体完全相同,但与成熟抗体相比,记忆抗体拥有更长的生命周期[10-11].
在模型中,无论是记忆抗体还是成熟抗体检测出的抗原都只是被移送到可疑邮件夹中,而不是真正的对其进行物理删除.这么做的目的是因为,对于用户而言,用户宁愿接受更多的垃圾邮件,也不愿错失一封被错判的邮件.

当用户处理可疑邮件夹时,系统根据用户的行为模式完成对抗体的动态更新.如果用户阅读可疑邮件的时间超过给定的阈值,模型认为用户对这种类型的邮件感兴趣,将该邮件判定为垃圾的抗体不再有效,系统根据附加到该邮件上的抗体的id将对应的抗体删除.对于通过成熟抗体与记忆抗体的邮件,如果用户没有阅读或阅读的时间少于过给定的阈值就删除的邮件,模型认为其为垃圾邮件,直接将该邮件添加到成熟抗体集合中,并对其抗原提呈,将提取的特征词添加到对应的基因库中.模型的检测流程如图1所示.
为了防止模型中抗体的规模随着检测流不断膨胀,以及保证过滤算法的动态性,如图1所示,模型中的所有抗体都有一定的生命周期.抗体的生命周期可以保证无效的抗体不再浪费系统的资源,同时将节省出来的资源提供给新的有效的抗体.公式(5)-(7)描述了成熟抗体与记忆抗体的生命周期模型.


克隆基因变异操作采用的是基因位多点变异.变异的位数由抗体累计亲和力决定.亲和力越低,变异的位数越多,反之,亲和力越高,变异的位数越少.模型根据计算出的变异位数从基因库中随机选取对应的基因替换抗体的变异基因位,以产生出亲和力更优的抗体.
经过克隆变异的抗体,有可能会产生比父体更优的抗体,但也有可能产生亲和力不如父体的抗体,甚至产生匹配自体的抗体.所以,变异后的抗体必须要经过自体耐受,匹配阈值低于父体的抗体将会被系统杀死,这个过程就是免疫选择.
3 试验与分析
3.1 试验评测标准
为了方便与其它算法进行对照,本文采用信息检索领域的查准率(precision)与查全率(recall)来作为衡量模型的主要标准.
设L为待检测邮件集合,S为邮件集合中的垃圾邮件的子集合,S+为垃圾滤过器实际检测出的垃圾邮件集,则查准率和查全率定义如下:
定义4.查准率:表示检测出的垃圾邮件数占实际垃圾邮件总数的比例,precision= S+ / S .
定义5.查全率:表示检测出的垃圾邮件数占整个检测邮件总数的比例,recall= S+ / L .
3.2 试验过程与结果分析
试验采用的是由Hopkins、Reeber等人提供的spambase语料[12],来源于提供者在一段时间内收到的真实邮件,去掉了HTML格式的tag、附件等,保留了邮件正文的纯文本内容.spambase将每一封邮件都表示为向量的形式,每个向量都是57维.语料库中共有4601封邮件,包含1813封垃圾邮件、2788封非垃圾邮件.将4601封邮件均分为10份,随机从10份中选取5份用作训练,剩下的5份用于实际测试,如此重复10次,计算出来的平均查准确率与平均查全率即为模型的查准确率与查全率.试验中涉及的各种参数设置如表2所示.

为了验证模型的效率,本文在同等条件下与基于贝叶斯的垃圾模型[13-14]进行对比试验,如图2所示,基于免疫机制的模型NSC较基于贝叶斯方法的模型在查准率提高的基础上,查全率大幅提高.而且随着检测进程的推移,基于免疫机制的模型的查全率与查准率相对而言比较稳定,而基于贝叶斯的方法检测率起伏相对而言比较大.

究其原因是因为基于贝叶斯的方法采用先验概率来预测结果,如果该方法在检测阶段检测的邮件包含了太多训练阶段未曾遇到的新词,基于贝叶斯的模型需要一段较长时间的学习过程.而本文提出的模型NSC,在训练阶段产生的初始的抗体,在检测的过程中通过克隆操作保留优势抗体,通过克隆变异进化抗体,通过克隆选择保证抗体的有效性.同时,模型结合用户的行为模式动态的更新抗体.使模型呈现出检测的准确性,学习的快速性与抗体的多样性.
4 结 论
反垃圾邮件的难点在于:垃圾邮件发送者经常变换发信地址、伪造发信地址、利用程序随机挑选变换邮件内容,这些都给垃圾邮件的治理设置了技术障碍.而目前反垃圾邮件采用的技术手段几乎是静态的方法,过滤器无法适应不断变化垃圾邮件,缺乏自适应性与自学习能力,检测率较低.
本文借鉴生物免疫机制,结合用户处理邮件的行为模式,提出了一种新型的垃圾邮件过滤模型,该模型不但有效的提高了检测垃圾邮件的准确率与查全率,而且表现出良好的自适应性与自学习性.

上海联兵环保科技有限公司
地址：上海市松江区工业区茸北分区茸阳路69号
总机：021-51691929
传真：021-57784244
免费电话：400-600-5030
技术支持：13641659499
E-mail：zhanglianbing@126.com
http://www.shlbhb.com