零散二元多项式散列法（SBPH），及CRM114判别式

英文原文

译者电邮：liji@brandeis.edu

William S. Yerazunis，博士^[1]
三菱电子研究实验室^[2]
剑桥，麻省02139
版本：2003年1月20日

内容摘要：贝叶生统计学邮件过滤法将收到的邮件编入有效集和无效集，它已迅速成为单端式防垃圾过滤器的首选。在本次讲话中，我们将研究零散二元多项式散列法（SBPH）过滤技术。这是对贝叶生方法的一个推广，不仅用到单个词汇，还有变异词组。SBPH已被实施于GPL产品“CRM114判别式”中。在监控学习过程中，在不设黑白名单的情况下，并且是在仅有500K预设类别的例用文本的前提下，SBPH对现时邮件可达到99.9%的准确率。

内容介绍

电子邮件作为可靠的交流媒体的持续有用地位，被垃圾邮件所挑战。这是因为，人们既不期待也不想收到垃圾邮件（有时又称“不请自来的商业邮件”或“市场信息”），所以收到它们的自然反应就是删除。不幸的是，对未读邮件的快速删除，经常会导致一些想要的（重要的）电子邮件被意外遗失（即所谓“垃圾痉挛症状”）。

垃圾邮件有时会包含不是何接收环境的信息，好比在正式工作场合（这种地方有时会有防性骚扰条例）收到赤裸裸的性消息。别的垃圾邮件也会干扰到其他的工作环境，好比投资或赌博方面的信息。

垃圾邮件的几乎所有损害都是针对接收人的。平均算来，一个人要花两秒来删除一个几乎未读的垃圾邮件，用以小时$5.15的最低人工计，一百万个垃圾邮件总计要花接收人$2,800。（实际上的损失还要更大得多，因为大多数接收人挣的要多于联邦政府规定的最低收入。）

近来，垃圾邮件具有非零的IT费用。它们需要宽带来传输，需要机器来运作，还要一个储存空间来保存（和存档）。这些费用对很多用户和团体来说都非寻常，特别是对大型ISP来说。这可以被看成是对团体的计算资源的一种“服务抵消”（DoS）式攻击。

前人的抵制垃圾邮件方法

前人的抵制垃圾邮件，包括有对已知垃圾散发者及垃圾术语设黑名单，对已知垃圾信息（经常是以整个文档的零散签名方式）设黑名单，以及关键词搜索，启发式垃圾特征核对，和验证发送人系统（聪明白名单）等方法。

针对已知垃圾邮件团体站点的黑名单，已经从小的手工管制走到大型的TCP可到达数据库，例如ORBS, SPEWS，以及一些基于订阅的服务。这些黑名单使用“大榔头”范例，以便强制ISP去中止垃圾传播者的入侵，那整个ISP的地址栏都上黑名单，也就是说所有从那个ISP出来的用户都被从这个服务器上禁止。这样的黑名单经常挺管用，不过有一些已经被指责有政治审查企图，特别是用来针对那些对这个黑名单设置形式的反对意见。

针对文档而非对垃圾邮件团体的黑名单，是把整个垃圾邮件的杂乱信号编入数据库来完成。因为只有那些杂乱信息用来进行传输，一个由一百万垃圾邮件签名构成的数据库能用一个晚上轻松下载。任何改变签名的邮件变更方式都能把这种过滤法击溃，所以当下几乎所有的垃圾邮件散发者，都在每个垃圾邮件里加上一小段随机文字，来强迫生成一个新的电子签名。

另一种黑名单的方式是关键词搜索。这是把一些词语的集合定义成“垃圾邮件生成器”，然后在每个到来邮件里搜索之。任何包含了目标关键词的邮件都将被删除，不管它是不是真垃圾。垃圾邮件发送者对付这种过滤法的方法，是机巧地在黑名单关键词中间加进空白，错拼，HTML注释等。

启发式核对法的使用者，象SpamAssassin^[3]，是用人类专家来找出一些特征的集合，好比一些行，或者其他出现在数据库里的什么条件，然后用人工或者由中枢集那样的算法，这些特征被加上不同的权值。假如一个到来邮件超过了某个槛，它就被当成垃圾邮件拒收，否则就被认为是好的。这个特征集的基本，还是用人类专家来检测垃圾邮件和非垃圾邮件，找出其中的显著性质。这样就导致始终只有相对很少的特征（小几百左右）能被检测到。

这些黑名单系统的反面就是基于“白名单”的系统，好比说TMDA^[4]。在这些系统中，除非来自一个已知的善意发送人，或者包含有已知的良好通行信息，否则所有邮件都被预设成是垃圾邮件。高级点的白名单系统会给所有的不在白名单上的发送者发一个挑战信，假如这个发送人回答地适宜的花，过滤器就会自动把其加入白名单。

这个大家庭里的新来者是统计学过滤法^[5]，好比Bogofilter^[6]，spamfilt，等等。这些过滤法把单个词语出现的情况当作特定“特征”来考虑。文中提到过的CRM114就是用一个派生的贝叶生过滤法，加上更强大的特征析取：零散二元多项式散列法（SBPH)。

SBPH中的数学：

零散二元多项式散列法（SBPH)用的方法是，先自动从接收文件中生成大量特征，然后用统计法，根据这些特征的“垃圾/非垃圾”判断价值来决定其权值。这些特征自己，将成为所有不超过某个特定N阶的零散二元多项式应用到一个由词汇信号构成的流动窗口的结果。

我们调查了关于SBPH的以下实施过程。先是生成一个N词组成的流动窗口。为计算方便故，每个词都拆散成33－bit，然后这些信号被当作w_n的值到以下多项式：

Z_j = S₁^Nw_nc_j,n mod 2³²

第n个窗口第j个多项式的N阶系数c_j,n，是由以下算法生成的：

c_j,n = if n = 0: 1 (在n=0的情况下j无关紧要）

否则: (( 1<<(n-1 ) ) & j << 1) | 1 (j被当作位图来考虑)

等某个窗口位置的所有都Z_j被算出来后，我们就可以把信号值w_n给替换掉，好省得要重复计算很繁复的行信号。

现在，这个流动窗口的长度N＝5个词，所以系数c_j,n是这些（空格为零）：

挑选这些系数和生成公式是因为以下原因：每个词信号值w_n都应该影响到Z_j的所有32比特输出（因此必须在低阶比特位置上有一个1），同样一个词信号值w，在不同位置w_j上的效果应该是不一样的（因此必须在除低阶比特位置之外的至少一个比特位置上不同且非零），另外整个的计算过程必须是容易运作的（因为它要在每个输入文本里被多次操作）。

这些系数当然不是仅有的有用系数。我们另外还试了素数系数，在运行上没发现任何不同。我们现在用这些零散二元多项式系数的唯一原因是，这样可以方便写出生成信号，来对任意N计算这个零散二元多项式信号，然后好更容易地用不同的N值来作测试。

一旦这个Z-值流被制造出来，我们就可以或者研究这个数流的统计价值，或者根据以前的统计结果来把这个数流归类。

当研究时，在每对桶文件---一个给垃圾邮件，一个给非垃圾邮件_---里，我们把看见每个Z-值的时间次数累加起来。与其弄出两个特大的文件（每个用2³²计数之长），我们不如就用32-位的Z-值，把它模掉桶文件的长度叠起来。缺省设置是，桶文件有1兆加1字节的长度（这还是为来强制Z－值里的每个比特都对输入发生点作用。用个素数来作桶长将有完全相同的效果）。在当前的实施中，桶将被取消字节设置，然后在叠加过程中，我们需要采取措施，在255上停止两个桶的增加，并且不允许包围。

当归类时，关于输入文件是哪个桶里的代表的可能性，垃圾邮件和非垃圾邮件的桶之间的相对计数将被用于计算一个粗略的条件概率。贝叶生链式法则将被用于计算一个最终的类别归属概率。

贝叶生链式法则

SPBH算法的结果，是一系列的近似条件概率，用来猜测这个输入文件的类别归属。贝叶生链式法则将提供一个方法，来合并单个特征的条件概率成一个综合概率。

古典贝叶生链式法则（BCR），对种类C和特征F，是：

P (C|F) = P (F|C) P(C) / { P (F|C) P (C) + P (F|~C) P(~C) }

上面的除数是个古典条件概率的乘法，被除数是一个二级系统的重正化因子。不幸的是，贝叶生链式法则只当不同特征F在统计意义上相互独立的条件下成立。在用于垃圾邮件过滤法时，实践中这个条件几乎总不成立，所以BCR法则不是数学意义上正确的。幸运的是，一个打上“垃圾邮件”标签的邮件，几乎必然就是垃圾，所以这个不准确只体现在数目大小上，而不会导致类别错乱。

在那个数字下溢里的计算实施方案，在SBPH/BRC对IEEE－适应性浮点硬件的求值程序中，是容易得到的。一旦概率达到了1.0的10^－20附近，这个概率就同1.0在数字上难以区分了。为避免这个情况发生，我们的实施方案要分别计算并维持每个特征的P(C|F)和P(_~ C|F)，然后从小的概率里重新计算大的概率。这样就避免了重要性被下溢损害的事情出现。

第二个下溢事件会当大约在10^－318时发生，那是整个IEEE浮点的动态范围被用尽了。比这个更小的数值将无法同零区分。幸运的是，当这种下溢发生时，几乎总是这个收到文本已经被正确归类了。

CRM114语言

CRM114语言是特别为编写类属过滤器而创造的。CRM114里支持的唯一数据结构是某个指定的数行，它能单独出现，也能同其他指定的数行部分或全部地相互交迭。CRM114不直接支持数值或结构资料。CRM114最基本的操作是用来演示正规压缩（regex），以及对数行的SBPH/BCR匹配。程序是以块结构的方式出现，嵌套层次不确定，设置变量并给出其初始值，在遇到变量时将自动在一个整体层面上给出其数界。程序是单片集成的，不给局部范围的变量。没有子程序，但有一个强大的过程分叉设置，来取代子程序和函数的功能。

CRM114不用位置和基于关键词的语法，而是用一个变格的剖析器：文本中特定的一块的功用，是被那些包围它的引用符号来直接决定的；这是对编写“快餐式”过滤器的特别有意义的帮助，另外它作为一个编程助手也很管用。未被引用的文本成为命令，被冒号包围的词，好比:this:就是变量名称，而在"<,>"号里的词就是修正标记，"（）"里的变量被直接使用（或涉及），"[]"里的变量则将约束到这个命令的有效区域，任何"//"里的东西都是一个正规压缩。在命令词上，同一个综述表达里的引用行之间的次序则无关紧要。

CRM114是一个为制作过滤器而设计的预言。预设的是，所有CRM114程序在EOF之前都将读取他们的整个输入流，并且在程序操作开始之前把这变成一个单个的变量。在这个大缓冲器中，变量作为相互交迭的子行而存在。后来的变量或者是作为开始/范围偏移量被制造出来，或者就是单独独立的变量。

在CRM114过滤程序中，流程控制可以是下列五种中的任何一种：

变量改造可以是非手术的（用MATCH，然后把变量捆绑到一个预先存在数行的新局部上），也可以是手术的（实际上就是删除然后添加字节到这个变量行里）。手术性变更操作，对指定变量以及任何与之交迭的变量同时发生作用。CRM114另外还提供一个HASH函数，手术性地把一个变量的行空白替换成任何数行32位hash的十六进制表述。

SYSCALL表达允许以fork()的过程来调用一个任意的命令行程序，使之流入一个任意的数行来作为正规输入，并捕获其输出来作正规输出。这个被调用的家伙，可以在syscall回车之前被运行到完成，或者被允许继续作为一个独立过程，在无限交流以及不同步执行的情况下运行。

WINDOW表述则是用来把输入缓冲器，分割成长度无限制的输入行大小合适的块，好比象syslog。这个表述把相当于一个正规压缩的文本给从输入缓冲器的开端删除掉，然后把从正规输入里读取里相当于一个正规压缩的文本给加进输入缓冲器的结尾。INPUT和OUTPUT，运行输入/输出，然后ACCEPT表述再把当前的输入缓冲读进正规输出。

邮件过滤（Mailfilter)程序

Mailfilter.crm是一个程序，用CRM114语言编写，特别为运作RFC2822邮件－－即普通的网络SMTP邮件，在文本文件格式下－－而设计。Mailfilter能在几乎任何邮件传输和邮件阅读代理下运作，唯一的要求是，用户要能向他们自己发送一个这样的邮件：邮件里有一个将被分类的文本，还有一个鉴定口令。Mailfilter依序进行以下操作：

1. 这个邮件配有正常的命令/口令么？假如是，执行相应命令。（这表明一个用户如何能远程操作其白名单，黑名单，以及学会垃圾邮件的新形式）。假如否，则。。。

2. 这个邮件同某个优先行动名单、白名单或者黑名单中的某个单位匹配么？假如是，以合适方式发送这个文件的内容。否的话就。。。

3. 用SBPH/BCR算法以及事先生成的桶文件，对这个邮件的内容进行分类，然后根据分类结果把此文本进行发送。

Mailfilter.crm既能单独运行，也能以变更的方式作为辅助过滤器在procmail下运行。不管是哪种情况，它都是一个很有效的过滤器。经本文作者测试机诶国，在训练后，mailfilter.crm程序有超过99.9%的精确率。

特别地，在2002年11月1日到12月1日期间，一个经过事先训练的mailfilter.crm（编号为CRM114版本2002－11－26）处理了作者的现实收到文件流，总共有5849个邮件（1935个垃圾邮件，3914个非垃圾邮件），达到只有4个误收，0个误据，2个处理为“人类不能分类”。这是基于仅仅是SBPH/BCR分类法，没用到任何白名单或者黑名单。用一个Transmeta666兆处理器，处理速度达到约20千字节每秒，需要的内存低于5兆。在每个垃圾邮件和非垃圾邮件文本汇编中，约有400K字节的训练文本。每个汇编生成约400K个特征。比较说来，在第一关上，作为人类的作者，作为一个防垃圾邮件过滤器能达到的精确率约是99.84%。这个系统的ROC（接收者操作特性Reciever Operating Characteristic)曲线，本质上就是一个非常接近于原点[0,0]的单点，而与此同时，概率小于0.000000001或大于0.9999999999的标本邮件有远大于99%之多，并且这个算法中不包含任何“神奇的可调参数”。

作者现正参与一个重复试验，通过把SPBH/BCR保持在一个空白状态上，获得关于这个算法的认知率的实验数据。

目标：垃圾邮件散发者的商业操控模式

为了确实地解决垃圾邮件问题，一个现实问题是关于垃圾邮件散发着的商业模式。垃圾邮件的散发，不过是一种获得广告引导的非常便宜的方式，因为要把邮件发给接受者，这里面的几乎所有花费都来自接受者自己了。为了制止垃圾邮件，我们必须要使垃圾散发者的商业模式站不住脚。

典型来说，一百万个垃圾邮件的散发所获佣金是约$250到$500，而回复率是约一千分之一。同大批纸上信函相比，这个是非常省钱的。纸信能有约二十分之一的回复率，可是每个得花25美分。这就使垃圾邮件比零散纸信要便宜200倍左右（这是对发送者来说，也即是说，垃圾邮件几乎所有成本都来自非自愿的接收者/受害者）。

为了改变这种垃圾邮件成本方式，使之不再是“接收者支付”，我们要不得改变双向协议（意即网络“邮费”），要不就得用单端过滤器，来强迫使垃圾邮件的单回复花费率，从$250/1000个回复（或者，每个回复25美分）变成超过纸信的$.25/.05（或者，每回复$4.00）。这就要求过滤器有至少99.5%的准确率。SPBH/BCR能达到更好上五倍的效果（迫使单个的垃圾邮件回复成本达到每回复$20)。

需要注意的是，SBPH/BCR不是仅有的能达到这种准确率程度的过滤技术，有可能有很多法子都行。我们应该鼓励多种技术的研制和展开。因为不同的过滤法将会有不同的弱点，而避免垃圾邮件过滤法单一化，无疑是避免灾难性失守的良好防卫。

垃圾邮件过滤精确度的限度

在精确率限度上，除了过滤器精确率之外还有一个第二因素。通过在长时期内对一种典型垃圾邮件流的研究，我们不难发现垃圾邮件并非周而复始的：垃圾邮件话题以及垃圾散发者传播这些话题用的方法，都在随着时间而演变。随着垃圾邮件流同训练用的文件汇编越来越脱离开来，任何静态过滤器都将要终于开始失败。

关于对观测者来说新垃圾邮件（或者垃圾散发方式）不断生成的比率，我们提供一个非常粗略的经验式估计如下：

看到的新垃圾邮件（数目比上经过的时间）＝（每天的垃圾邮件数）^{0.001 乘以 经过天数}

或者，更经验式的讲，每天100个垃圾邮件，可预示每月一到三个全新垃圾邮件的出现。这样就给单个用户的垃圾邮件过滤器的可行性错误率设置了一个下界。通过在多个读者间共享垃圾邮件信息来相互合作的过滤器，可达到更低的每用户错误率，但这只不过是因为了接种效果：第一个用户看见一个特定的垃圾邮件，就教给其过滤器关于这种垃圾邮件，然后就把剩下的用户给保护了。

结论，担忧，及未来的工作

其一，好消息。有力的垃圾邮件过滤技术（SBPH/BCR或其他）能提供一个近乎没有垃圾邮件的邮件环境－－即是说，垃圾邮件的发生是如此偶然，以至于人们看见这一个，却想不起上次看见垃圾邮件时的准确时间。这就使支持垃圾邮件传播的商业模式整个无效了，继而使得甚至稍弱的过滤器也能工作得更有效。

其二，坏消息。SBPH/BCR可能在计算上过于昂贵，以至不能在缺钱的ISP那得到广泛的实施。更快的算法可能是必需的。垃圾邮件过滤技术，只不过是强力文本过滤的一个使用。如此有力的方法，也有可能成为审查制度，或其他其他社会性不合理情形的工具。

在将来，我们打算开发以下课题：

1. 加速SBPH/BCR

2. 提高概率估计运作的表现，特别是对那些可作证据性较低的特征来说。

3. 考虑比天真贝叶生链式算法更好的链算法。特别地，在天真贝叶生链式算法中，对特征间相互独立的错误假设，可能是导致某些不准确性的起源。chi-square估测法可能是更合适的。

4. 提高CRM114程序语言的性能和可行性，包括其8比特安全模式和近似匹配（通过与一个可用的GPL近似正规压缩引擎之间的整合）。