用于控制器保护的防火墙规则的三叉树算法

傅一帆,刘小树,刘 跃,黄 玲

（杭州和利时自动化有限公司,浙江 杭州310018）

在分布控制系统DCS中曾发生过网络风暴袭击控制器的事件。控制器是分布控制系统的核心，一旦遭遇故障，将会造成重大的生命财产损失。因此如何防止网络的攻击是一个必须考虑的因素。

1 控制网络的应用特点与分析

分布控制系统中的控制器的网络环境与一般互联网有所不同：

(1)控制网络管理相对较严，但是一旦发生攻击，瞬间会造成停机等事故。一个强度仅6 000 pps(Packet Per Second)的攻击会在几百毫秒之内就使某些控制器复位。

(2)在控制应用中降低设备功耗对系统可靠性极其重要,工作温度越高，寿命越短，约每增高 10℃，寿命降低一半，低功耗和易于自然散热是设计考虑的重要因素。

(3)控制系统对可靠性设计有严格的要求。国际上的IEC 61508标准提出了安全完整性等级的概念，最高为4级，对于相对安全的第3级，要求系统每小时出现故障的可能性在10-7(h-1)以下,平均故障间隔时间在1 142年以上。对软件设计也提出了相应的规定[1]，如不能动态申请内存（非动态变量）、迭代的有限使用等，尤其对程序的确定性执行时间提出了严格的要求。其中控制系统至少要达到3级标准，安全保护系统要达到4级，这些都使一些原有防火墙应用的方法受到了限制。

在传统的防火墙规则匹配方法中,基于硬件的CAM（Content-Addressable Memory）[2]和 TCAM（Ternary Content Addressable Memory）方法[3]实现了线速处理，是防火墙规则处理中性能最好的。但该方法需要增加硬件模块，使成本增高，热功耗增加，TCAM的每比特的能量消耗，是SRAM的150倍[3]。基于哈希表的BSOL(Binary Search On Leaves)是一个优秀的算法[4]，其算法复杂度为 O(log(∑wi)),其中w表示防火墙规则空间的域长，wi表示第i维的域长,BSOL的处理效率在理论上与规则数无关。还有在BSOL算法基础之上,提出一种改进的高维报文分类算法 MCBF(Multi Cuttings and Bloom Filters)[5],运用 ASIC的并行处理，减少对哈希表的访问次数，但这些都需要与 Bloom Filter相配才能获得很好的效果[6],而对于 Bloom Filter，如用软件实现，计算量大；而在工业控制中，增加硬件模块，就增加功耗，同时哈希表的应用也使计算负荷不稳定。

本文利用控制器本身的计算能力构建防火墙过滤功能,遵循IEC 61508安全完整性等级SIL3等标准，提出了面向集合的三叉树算法,在对包过滤有确定性处理时间的前提上,获得log3级的查找时间复杂度，稳定了控制器在循环周期内的处理负荷，对所占空间有准确的上限，避免了使用动态内存。

2 面向集合运算的三叉树

定义规则时，往往会用到一段连续的空间，如一个IP网段、一段端口号等，如果在这连续的空间有着统一的处理要求，就可把这一集合当做一个树节点来处理。对于IP源地址、目的地址、端口号等构成的多维空间的规则匹配，可用逐步降维的方法转化为面向集合的三叉树搜索来解决这个问题。

对集合的分类查找采用三叉树的方法，前提条件是要查找的集合已被处理成为在空间上连续的闭区间，代表这个集合树结点的关键字不再是一个键值，而是由2个键分别表示这个集合的闭区间的上、下界端点值，称为这个集合结点的右键和左键。例如,在IP源地址空间上有3个网 段 集 ：128.0.0.11-128.0.0.16，128.0.0.40-128.0.0.45和128.0.0.51-128.0.0.53,这3个结点如图1表示。

表1 一个防火墙规则表例子

使用三叉树查找,获得log3级的查找时间复杂度，且每步处理开销小,但要根据安全规则构建成规则树，需解决规则冲突问题。

IP源、IP目的、IP协议、传输层端口号等组成多维欧氏空间,一条防火墙规则在多维欧氏空间构成一个超多面体，用网络包匹配规则的过程就是看它被包含在哪条规则构成的超多面体内。检查防火墙规则是否冲突，就是检查这些规则构成的超多面体之间有无相交、包含的问题。对规则表中要去除矛盾的规则，可简化成对规则表中的任两条规则进行分析。如果两条规则发生冲突,对相交的空间进行分割,分割后的空间划归为优先级高的规则。

下面以一个有两条规则的例子说明解决规则冲突的方法,如表1所示。假定规则序号越低优先级越高,经分析后逐维表示，如图2所示。

在多维空间上，两条规则不相冲突的充要条件是至少存在某个维，它们的规则集合互不相交。规则序号1和规则序号2所形成的空间域有相交的情况，在IP源地址的[b,c]区间、IP目的地址的[f,g]区间、协议号 6、目的端口号的[k,l]区间相交，无法确定其行动。根据优先级保证规则1的区间，在这4个区间内，调整任一个都可消除冲突，因此有多个调整方案，可在IP源地址空间上把[b,c]区间从规则 2中划出，使其IPsrc2的区间变为[c+,d](在这里，c+=c+1，c点划归 IPsrc1集合),两条规则互不相交,调整后的规则2的IP源地址空间如图2 IPsr2′所示。

在消除了规则冲突后,逐维生成规则树的次序是：IP源地址→IP目的地址→协议号→目的端口号。

规则树生成算法描述如下：

(1)选择IP源地址空间做第1维,根据规则集R={r1,r2,…,rN}划分在该维若干个区间x(i,1)，x(i,2),…x(i,N′)，其中区间x(i,j)的第一个下标i表示所在的维数序号，初始化时i=1，第二个下标表示在该维内相应的区间序号，区间x(i,j)是将要生成的面向集合的三叉树的节点,N表示规则个数,N′表示规则集在该维形成的区间个数。

(2)依次取第 1维第j个区间x(i,j),(初始化时i=1，j=1），找出与区间x(i,j)相关的所有规则集R(i,j)(其中第一个下标i表示所在的维数序号，第二个下标表示在该维内相应的区间序号），直至第1维所有区间相关的所有规则集R(1，1），R(1，2），…R(1,N′)都生成。

(3)在第1维生成平衡的面向集合的三叉树，其树的根节点即是整个规则树的根节点，所有在第1维空间由三叉树的节点表示的区间x(1，j)(j=1,2,…,N′)的出口都是进入下一维空间生成子树结构的根节点。

(4)i=1。

(5)在第i维取x(i,j)节点相关的规则集R(i,j)，根据R(i,j)做向第(i+1)维空间的映射，如此重复直至完成在第i维所有的x(i,j)节点向第（i+1）维空间的映射；

(6)对第（i+1）维空间，根据第i维空间的x(i,j)节点相关的规则集R(i,j)，划分在该第（i+1）维若干个区间x(i+1,1)，x(i+1,2),…x(i+1,N′′)， 如 此 重 复 直 至 完 成 在第i维所有的x(i,j)节点相关的规则集R(i,j)对第(i+1)维空间的划分。

(7)对第(i+1）维空间，依次就新划分的区间(i+1,k)，k=1，2,…,N′′， 在第i维空间相关的规则集R(i,j)基础上，找出映射到第(i+1）维空间的区间x(i+1,k)相关的所有规则，形成新规则集R(i+1，k)；k=1,2,…,如此重复直至第（i+1）维所有划分的区间都形成了新规则集。

(8)在第i维空间，以x(i,j)节点进入下一维的出口作为第(i+1）维生成子树的根，在第(i+1）维空间生成平衡的面向集合的三叉树，如此重复直至所有第(i+1）维在步骤(6)划分的区间都生成平衡的面向集合的三叉树。

(9)进入下一维，i=i+1，如果i＜4,则转步骤(5)；否则转步骤(10)。

(10)树已生成，根据在第i维空间的叶节点x(i,j)，找到相应的规则集R(i,j)，对叶节点x(i,j)设置行动属性值，如此重复直至所有第i维空间的叶节点都设置行动属性值，算法结束。

表2 网络包处理性能比较

3 比较分析

三叉树算法在单维空间，N条规则最多可划分2N+1个区间，生成的节点数最大为2N-1个,尚若N足够大,1可忽略,三叉树查找规则的时间复杂度为O(「log32N),在IP源地址、目的地址，目的端口号三维空间的规则匹配,单维最坏情况的时间复杂度为∑log32N，N为规则数，在三维空间最坏情况的时间复杂度为log38N3。

在查找速度上,与硬件实现的内容可寻址存储器CAM(Content-Addressable Memory)芯片 MCM69C232相比较[2,7],结果如表2所示。

MCM69C232芯片的匹配时间为 160 ns,在每秒有2 440连接处理时，匹配周期时间最小为200 ns，三叉树方法为797 ns，在处理64和1 514 B长度的网络包要比CAM分别增加6%和1.6%的时间开销，有一定的性能差距。但随着网络连接数的增多，到每秒10 000个连接时，MCM69C232芯片的匹配周期时间到800 ns以上[7]，而三叉树方法匹配周期时间不变，从成本和减少耗电等因素考虑，三叉树方法更适于嵌入式实时控制应用。

在SUN的SPARC平台上与顺序查找算法在100 Mb/s网络上的吞吐率相比较，检查处理能力与规则数的关系，三叉树算法，1条规则时，吞吐率为 99.4 Mb/s，顺序查找算法吞吐率为 99.2 Mb/s，两者相差不大，三叉树算法，配置到 43 815条规则时，仍有 99.2 Mb/s的吞吐率，而顺序查找算法在配置499条规则时吞吐率就降到了34.7 Mb/s，显示了在处理规则数量多时的性能优势。

三叉树算法所占据的空间与规则数相关，在每一维最多划分出2N-1个节点区间(N为规则数)，在 3维空间，经优化后的有向图的节点数小于6N。

总之，本文提出面向集合的三叉树算法，匹配规则速度较快，占用内存规模适度，运行期间不用动态申请内存，易于可靠性分析与验证，适于高可靠性要求的控制应用。

[1]International Electrotechnical Commission.Functional safety of electrical/electronic/programmable electronic safety-related System-Part3:Software Requirements.IEC 61508-3[S].Switzerland:IEC Central Office,2010.

[2]Luo Huiqian,Liu Kai.A firewall system based on contentaddressable memory and ARM[J].Computer Security,2008(5):36-38.

[3]TAYLOR D E.Survey and taxonomy of packet classification Techniques[J].ACM Computing Surveys,2005,37(3):238-275.

[4]Lu Haibin,SAHNI S.O(logW)multidimensional packet classification[J].IEEE Transactions on Networking,2007,15(2):462-472.

[5]Li Lin.Research on key techniques of firewall rule set[D].Chengdu:University of Electronic Science and Technology of China,2009.

[6]袁志坚，陈颖文，缪嘉嘉,等.典型Bloom过滤器的研究及其数据流应用[J].计算机工程，2009,35（7）：5-7.

[7]Motorola,Inc.MCM69C232 Advance Information 4K×64 CAM.REV 3[R].Denver:Motorola,Inc.,1998.