本发明公开一种批处理包过滤防火墙的实现方法，包括：规则库的分类、规则的协议类型的压缩处理、规则的端口号的压缩处理、符号OBDD刻画、数据包头信息的预处理、数据包头信息与规则库的匹配。本发明通过对规则和传入数据包的预处理，使得二者可以节省存储空间并更高效和有针对性的进行匹配，使得防火墙在过滤数据包时花费更少的节点比较次数，达到节省内存和加快匹配的效果。
1.批处理包过滤防火墙的实现方法，其特征在于，包括步骤：
步骤B.将规则库中的规则按照协议类型的不同分类；即
步骤B2.将协议类型为TCP、UDP和ICMP的规则，依据其协议类型分为TCP、UDP和ICMP三类；
步骤B3.将协议类型为其他类型的规则，使用线性列表列在一起；
步骤B4.将步骤B1协议类型为通配符的规则同时归入TCP、UDP和ICMP类中，并同时将其存入其他类型的线性列表中；
步骤C.将协议类型为TCP、UDP、ICMP和通配符的规则的源端口和目的端口进行压缩处理；
步骤D.将压缩后的规则库刻画为有序二叉决策图和线性列表混合结构；即步骤D1.将协议类型为TCP、UDP、ICMP和通配符的规则刻画为有序二叉决策图；
步骤D2.对步骤D1生成的所有有序二叉决策图，将其两两析取合成为1个新的有序二叉决策图；
步骤D3.将步骤D2生成的所有新的有序二叉决策图，将其两两析取合成为1个更新的有序二叉决策图；
步骤D4.反复执行步骤D3，直到将协议类型为TCP、UDP、ICMP和通配符的规则析取合成为1个整的有序二叉决策图；
步骤D5.将协议类型为TCP、UDP、ICMP和通配符的规则所形成的有序二叉决策图与协议类型为其他类型的规则所形成的线性列表，共同组成有序二叉决策图和线性列表混合结构；
步骤E.依据步骤A-D相同的处理方式，让进入防火墙的数据的包头信息等同于规则库中的规则，将进入防火墙的数据的包头信息批次地处理为有序二叉决策图或线性列表；
步骤F.将进入防火墙的数据的包头信息的有序二叉决策图和/或线性列表分别与对应的规则库中的有序二叉决策图和线性列表混合结构进行合取和匹配，根据结果采取相应的动作，即允许数据或拒绝数据通过防火墙。
2.根据权利要求1所述的批处理包过滤防火墙的实现方法，其特征在于：步骤E具体包括步骤：步骤E1.分批次缓存传入防火墙的数据的包头信息；
步骤E31.将协议类型为通配符的包头信息，单独列出来；
步骤E32.将协议类型为TCP、UDP和ICMP的包头信息，依据其协议类型分为TCP、UDP和ICMP三类；
步骤E33.将协议类型为其他类型的包头信息，使用线性列表列在一起；
步骤E34.将步骤E31协议类型为通配符的包头信息同时归入TCP、UDP和ICMP类中，并同时将其存入其他类型的线性列表中；
步骤E4.将协议类型为TCP、UDP、ICMP和通配符的包头信息的源端口和目的端口进行压缩处理；
步骤E5.将压缩后的包头信息库刻画为有序二叉决策图和线性列表混合结构；即步骤E51.将协议类型为TCP、UDP、ICMP和通配符的包头信息刻画为有序二叉决策图；
步骤E52.对步骤E51生成的所有有序二叉决策图，将其两两析取合成为1个新的有序二叉决策图；
步骤E53.将步骤E52生成的所有新的有序二叉决策图，将其两两析取合成为1个更新的有序二叉决策图；
步骤E54.反复执行步骤E53，直到将协议类型为TCP、UDP、ICMP和通配符的包头信息析取合成为1个整的有序二叉决策图。
3.根据权利要求1或2所述的批处理包过滤防火墙的实现方法，其特征在于：步骤A具体包括步骤：步骤A1.将规则库中的每条规则中的元素即协议类型、源IP地址、源端口、目的IP地址和目的端口进行排序；
步骤A2.使用8位布尔变量表示协议类型，使用32位布尔变量表示源IP地址，使用16位布尔变量表示源端口，使用32位布尔变量表示目的IP地址，使用16位布尔变量表示目的端口。
4.根据权利要求3所述的批处理包过滤防火墙的实现方法，其特征在于：步骤A1中，每条规则的元素按照协议类型，源IP地址，源端口，目的IP地址和目的端口进行依次排序。
5.根据权利要求1或2所述的批处理包过滤防火墙的实现方法，其特征在于：步骤C具体包括步骤：步骤C1.当规则的协议类型为TCP、UDP和ICMP时，则将该规则的协议类型压缩为用2位布尔变量表示；
步骤C2.当规则的协议类型为通配符时，则将该规则的协议类型压缩为用2位通配符表示；
步骤C3.将协议类型为TCP、UDP、ICMP和通配符的规则的源端口和目的端口的布尔变量使用11位布尔表达式表示。
6.根据权利要求1或2所述的批处理包过滤防火墙的实现方法，其特征在于：步骤D中，对协议类型为通配符的规则所对应的有序二叉决策图进行合成时，需要跳过该规则的协议类型这一元素，直接从下一个元素开始析取合成。
7.根据权利要求1或2所述的批处理包过滤防火墙的实现方法，其特征在于：步骤D中，当上一次迭代的有序二叉决策图的个数为奇数时，则将上一次迭代余下的那个有序二叉决策图与本次迭代的任意一个有序二叉决策图析取合成为1个新的有序二叉决策图。
8.根据权利要求1或2所述的批处理包过滤防火墙的实现方法，其特征在于：步骤F具体包括步骤：步骤F1.将生成有序二叉决策图的包头信息与规则库中的有序二叉决策图和线性列表混合结构中的有序二叉决策图部分进行合取操作；得到的结果中指向“1”叶子节点的数据为决策通过，即允许该数据通过防火墙；得到的结果中指向“0”叶子节点的数据为决策拒绝，即拒绝该数据通过防火墙；
步骤F2.将生成线性列表中的包头信息与规则库的有序二叉决策图和线性列表混合结构中的线性列表部分进行匹配操作；如果有与之匹配的规则，根据规则的决策采取相应动作，若决策为允许则允许该数据通过防火墙，若决策为拒绝则拒绝该数据通过防火墙；如果没有与之匹配的规则，则直接拒绝该数据。
批处理包过滤防火墙的实现方法
技术领域
[0001] 本发明涉及网络安全技术领域，具体涉及一种批处理包过滤防火墙的实现方法。
背景技术
[0002] 计算机防火墙是指在外部网络和用户计算机之间设置防火墙。计算机防火墙也可以是用户计算机的一部分。计算机防火墙检测接口规程、传输协议、目的地址和/或被传输的信息结构等，将不符合规定的进入信息剔除。计算机防火墙对用户计算机输出的信息进行检查，并加上相应协议层的标志，用以将信息传送到接收用户计算机(或网络)中去。
[0003] 随着Internet的迅速发展和广泛应用，持续增加的网络攻击(包括无意识行为和恶意行为)使得防火墙技术成为网络安全领域的研究热点之一。与其他类型的防火墙相比，包过滤防火墙具有更易实现、过滤速度快、对用户和应用程序透明、开发成本低等优势，所以包过滤防火墙的应用十分的广泛。包过滤技术实质上是一种数据包分类技术，通过传入防火墙的数据包的包头信息和规则库的规则匹配进而决策接受或者拒绝该数据包。然而，随着对网络安全的要求越来越高，防火墙的规则库条目的不断增多，对防火墙技术提出了新的要求。目前包过滤防火墙的研究集中在优化规则库的结构和改进数据包的过滤方式上。
[0004] 目前就包过滤防火墙的规则库结构有：
[0005] (1)基于线性列表方法：规则库中的规则按顺序的方式连续存储，对传入的数据包过滤时规则库对传入的数据包头信息按照顺序依次匹配，直到匹配到对应的数据包并执行相应的操作(接受或者拒绝)。若匹配完所有的规则没有与之匹配的规则，则采用默认操作(一般为丢弃该数据包)。该方法存在不确定性，若数据包命中过多规则库排序靠后的规则会导致匹配效率降低。
[0006] (2)基于动态线性列表方法：在基于线性列表方法的基础上加入了动态排序，按照规则匹配的命中率对规则库重新排列，减少了规则的匹配时间，提高了匹配效率。该方法在一定程度上缓解了基于线性列表方法的缺陷，但随着规则条目的增多，更新规则库也会带来很大的开销。
[0007] (3)基于OBDD方法：使用符号技术重新设计了规则库的结构，在位级别消除了规则的冗余，降低了存储空间，并减少了节点比较的次数，提高了匹配效率。该方法引入了OBDD，但其104位的深度使得匹配的效率优待提高，并且单个数据包的过滤方式也限制的OBDD的优势，进一步限制了匹配的效率。
发明内容
[0008] 本发明所要解决的技术问题是提供一种批处理包过滤防火墙的实现方法，其基于OBDD-LIST(Order Binary Decision Diagram-LIST，有序二叉决策图与列表的混合结构)，其能够压缩一般OBDD结构的规则库的深度，同时可以批处理进入防火墙的数据包。
[0009] 为解决上述问题，本发明是通过以下技术方案实现的：
[0010] 批处理包过滤防火墙的实现方法，包括步骤：
[0011] 步骤A.将规则库中的规则使用布尔变量表示；
[0012] 步骤B.将规则库中的规则按照协议类型的不同分类；即
[0013] 步骤B1.将协议类型为通配符的规则，单独列出来；
[0014] 步骤B2.将协议类型为TCP、UDP和ICMP的规则，依据其协议类型分为TCP、UDP和ICMP三类；
[0015] 步骤B3.将协议类型为其他类型的规则，使用线性列表列在一起；
[0016] 步骤B4.将步骤B1协议类型为通配符的规则同时归入TCP、UDP和ICMP类中，并同时将其存入其他类型的线性列表中；
[0017] 步骤C.将协议类型为TCP、UDP、ICMP和通配符的规则的源端口和目的端口进行压缩处理；
[0018] 步骤D.将压缩后的规则库刻画为有序二叉决策图和线性列表混合结构；即[0019] 步骤D1.将协议类型为TCP、UDP、ICMP和通配符的规则刻画为有序二叉决策图；
[0020] 步骤D2.对步骤D1生成的所有有序二叉决策图，将其两两析取合成为1个新的有序二叉决策图；
[0021] 步骤D3.将步骤D2生成的所有新的有序二叉决策图，将其两两析取合成为1个更新的有序二叉决策图；
[0022] 步骤D4.反复执行步骤D3，直到将协议类型为TCP、UDP、ICMP和通配符的规则析取合成为1个整的有序二叉决策图；
[0023] 步骤D5.将协议类型为TCP、UDP、ICMP和通配符的规则所形成的有序二叉决策图与协议类型为其他类型的规则所形成的线性列表，共同组成有序二叉决策图和线性列表混合结构；
[0024] 步骤E.依据步骤A-D相同的处理方式，让进入防火墙的数据的包头信息等同于规则库中的规则，将进入防火墙的数据的包头信息批次地处理为有序二叉决策图和/或线性列表；
[0025] 步骤F.将进入防火墙的数据的包头信息的有序二叉决策图和/或线性列表分别与对应的规则库中的有序二叉决策图和线性列表混合结构进行合取和匹配，根据结果采取相应的动作，即允许数据或拒绝数据通过防火墙。
[0026] 所述步骤E，包括步骤：
[0027] 步骤E1.分批次缓存传入防火墙的数据的包头信息；
[0028] 步骤E2.将包头信息使用布尔变量表示；
[0029] 步骤E3.将包头信息按照协议类型的不同分类；即
[0030] 步骤E31.将协议类型为通配符的包头信息，单独列出来；
[0031] 步骤E32.将协议类型为TCP、UDP和ICMP的包头信息，依据其协议类型分为TCP、UDP和ICMP三类；
[0032] 步骤E33.将协议类型为其他类型的包头信息，使用线性列表列在一起；
[0033] 步骤E34.将步骤E31协议类型为通配符的包头信息同时归入TCP、UDP和ICMP类中，并同时将其存入其他类型的线性列表中；
[0034] 步骤E4.将协议类型为TCP、UDP、ICMP和通配符的包头信息的源端口和目的端口进行压缩处理；
[0035] 步骤E5.将压缩后的包头信息库刻画为有序二叉决策图和线性列表混合结构；即[0036] 步骤E51.将协议类型为TCP、UDP、ICMP和通配符的包头信息刻画为有序二叉决策图；
[0037] 步骤E52.对步骤E51生成的所有有序二叉决策图，将其两两析取合成为1个新的有序二叉决策图；
[0038] 步骤E53.将步骤E52生成的所有新的有序二叉决策图，将其两两析取合成为1个更新的有序二叉决策图；
[0039] 步骤E54.反复执行步骤E53，直到将协议类型为TCP、UDP、ICMP和通配符的包头信息析取合成为1个整的有序二叉决策图。
[0040] 所述步骤A，包括步骤：
[0041] 步骤A1.将规则库中的每条规则中的元素即协议类型、源IP地址、源端口、目的IP地址和目的端口进行排序；
[0042] 步骤A2.使用8位布尔变量表示协议类型，使用32位布尔变量表示源IP地址，使用16位布尔变量表示源端口，使用32位布尔变量表示目的IP地址，使用16位布尔变量表示目的端口。
[0043] 步骤A1中，每条规则的元素按照协议类型，源IP地址，源端口，目的IP地址和目的端口进行依次排序。
[0044] 所述步骤C，包括步骤：
[0045] 步骤C1.当规则的协议类型为TCP、UDP和ICMP时，则将该规则的协议类型压缩为用2位布尔变量表示；
[0046] 步骤C2.当规则的协议类型为通配符时，则将该规则的协议类型压缩为用2位通配符表示；
[0047] 步骤C3.将协议类型为TCP、UDP、ICMP和通配符的规则的源端口和目的端口的布尔变量使用11位布尔表达式表示。
[0048] 步骤D中，对协议类型为通配符的规则所对应的有序二叉决策图进行合成时，需要跳过该规则的协议类型这一元素，直接从下一个元素开始析取合成。
[0049] 步骤D中，当上一次迭代的有序二叉决策图的个数为奇数时，则将上一次迭代余下的那个有序二叉决策图与本次迭代的任意一个有序二叉决策图析取合成为1个新的有序二叉决策图。
[0050] 所述步骤F，包括步骤：
[0051] 步骤F1.将生成有序二叉决策图的包头信息与规则库中的有序二叉决策图和线性列表混合结构中的有序二叉决策图部分进行合取操作；得到的结果中指向“1”叶子节点的数据为决策通过，即允许该数据通过防火墙；得到的结果中指向“0”叶子节点的数据为决策拒绝，即拒绝该数据通过防火墙；
[0052] 步骤F2.将生成线性列表中的包头信息与规则库的有序二叉决策图和线性列表混合结构中的线性列表部分进行匹配操作；如果有与之匹配的规则，根据规则的决策采取相应动作，若决策为允许则允许该数据通过防火墙，若决策为拒绝则拒绝该数据通过防火墙；如果没有与之匹配的规则，则直接拒绝该数据。
[0053] 与现有技术相比，本发明具有如下特点：
[0054] 1.利用规则库的特征将协议类型和端口号的位数压缩，有效降低了OBDD的深度，降低了存储的空间；
[0055] 2.防火墙规则库的结构为符号OBDD与线性列表的混合结构(OBDD-LIST)，优化了规则库的结构，降低了OBDD的宽度和深度，提高了匹配的效率；
[0056] 3.过滤方式采用了批处理的思想，将批量数据包刻画为OBDD-LIST再与规则库匹配，有效降低了节点比较次数。
附图说明
[0057] 图1为基于OBDD-LIST的批处理包过滤算法的流程图。
[0058] 图2为本发明的基于符号OBDD的包过滤防火墙规则库的一个示例模型。
[0059] 图3为本发明的数据包头信息的预处理流程图。
具体实施方式
[0060] 为了使本发明的技术方案及优点更加清楚明白，结合附图及实施例，对本发明进一步的详细说明。应当理解，此处所描述的具体实施例仅仅用于解释本发明，并不用于限定本发明。
[0061] 一种批处理包过滤防火墙的实现方法，包括步骤：
[0062] 阶段I.将规则库刻画为OBDD-LIST结构。
[0063] 步骤A.将规则库中的规则使用伪布尔函数表示；
[0064] 步骤B.将规则库中的规则按照协议类型的不同分类；
[0065] 步骤C.将协议类型和端口号进行压缩处理；
[0066] 步骤D.将压缩后的规则库刻画为有序二叉决策图和线性列表的混合结构(OBDD-LIST，Order Binary Decision Diagram)；
[0067] 阶段II.将传入的数据包批处理的刻画为OBDD-LIST结构。
[0068] 步骤E.将进入防火墙的数据包头信息批次地处理为OBDD-LIST结构；
[0069] 阶段III.将处理后的包头信息与规则库进行匹配，得出结果。
[0070] 步骤F.预处理后的包头信息与规则库进行匹配，得出相应的操作结果。
[0071] 所述步骤A，具体包括步骤：
[0072] 步骤A1.将规则库中规则元素排序为<协议类型，源IP地址，源端口，目的IP地址，目的端口>；
[0073] 步骤A2.使用8位布尔变量表示协议类型，使用32位布尔变量表示源IP地址，使用16位布尔变量表示源端口，使用32位布尔变量表示目的IP地址，使用16位布尔变量表示目的端口；
[0074] 步骤A3.将处理过的规则库保存在相应文件中等待进一步处理。
[0075] 所述步骤B，具体包括步骤：
[0076] 步骤B1.依据协议类型为TCP,UDP,ICMP将相应的规则分类；
[0077] 步骤B2.协议类型为通配符(WildCard)的规则单独列出来；
[0078] 步骤B3.协议类型为其他类型的使用线性列表列在一起；
[0079] 步骤B4.将协议类型为通配符的规则分别放入存放TCP,UDP,ICMP和其他类型的线性列表。
[0080] 所述步骤C，具体包括步骤：
[0081] 步骤C1.将协议类型为TCP,UDP,ICMP的布尔变量压缩为两位布尔变量表示；
[0082] 步骤C2.将协议类型为通配符的使用**表示，在生成OBDD-LIST结构时直接跳过前两位，从第三位开始析取合成；
[0083] 步骤C3.将源端口和目的端口的布尔变量使用11位布尔表达式表示，其中前十位布尔表达式代表的范围表示公用端口，剩下的表示动态端口范围。
[0084] 所述步骤D，具体包括步骤：
[0085] 步骤D1.将协议类型为TCP,UDP,ICMP和通配符的规则刻画为OBDD结构；步骤D2.将第1条规则与第2条规则析取生成OBDD结构，第3条规则与第4条规则析取生成OBDD结构，依次类推；
[0086] 步骤D3.在一次生成后，将第1个OBDD与第2个OBDD析取生成新的OBDD结构，第3个OBDD与第4个OBDD析取生成新的OBDD结构，依次类推；
[0087] 步骤D4.反复执行步骤D3，直到将规则库析取为一个OBDD结构；
[0088] 步骤D5.线性列表中储存协议类型为其他类型(非TCP,UDP,ICMP)的规则，与步骤D4生成的OBDD结构共同组成OBDD-LIST结构。
[0089] 所述步骤E，具体包括步骤：
[0090] 步骤E1.缓存传入防火墙的10000个数据包头信息(由<协议类型，源IP地址，源端口，目的IP地址，目的端口>组成)；
[0091] 步骤E2.将传入的包头信息使用布尔表达式表示(参考步骤A)；
[0092] 步骤E3.将包头信息按照协议类型的不同分类为TCP,UDP,ICMP,通配符(WildCard)和其他类型(参考步骤B)；
[0093] 步骤E4.将TCP,UDP,ICMP的布尔表达式进行压缩(参考步骤C)；
[0094] 步骤E5.将源端口和目的端口的布尔表达式进行压缩(参考步骤C)；
[0095] 步骤E6.将处理好对应协议类型的信息生成OBDD结构(参考步骤D)；
[0096] 步骤E7.将对应协议类型的包头信息储存在线性列表中(参考步骤D)；
[0097] 所述步骤F，具体包括步骤：
[0098] 步骤F1.将生成的OBDD结构的包头信息与规则库中的OBDD部分进行合取操作，得出结果；
[0099] 步骤F2.将线性列表中的包头信息与规则库的线性列表中的规则依次进行匹配，得出结果。
[0100] 本发明公开了一种基于符号OBDD-LIST(有序二叉决策图和线性列表的混合结构)的批处理包过滤防火墙的实现方法，包括：规则库的分类、规则的协议类型的压缩处理、规则的端口号的压缩处理、符号OBDD刻画、数据包头信息的预处理、数据包头信息与规则库的匹配。本发明通过对规则和传入数据包的预处理，使得二者可以节省存储空间并更高效和有针对性的进行匹配，使得防火墙在过滤数据包时花费更少的节点比较次数，达到节省内存和加快匹配的效果。
[0101] 下面通过一个具体的实例对本发明进行进一步详细说明：
[0102] 本实例需输入规则列表…，其中包含元素<协议类型，源IP地址，源端口，目的IP地址，目的端口>，将规则列表表示为布尔表达式，然后生成对应的OBDD-LIST结构，传入防火墙的若干数据包头信息<…>采取同样的操作，最后与规则库匹配操作，输出过滤结果。
[0103] 图1为本发明基于符号OBDD-LIST的批处理包过滤防火墙的实现方法的实施例流程图。参照图1，本发明提出的实现方法包括如下三个阶段，具体步骤为：
[0104] 阶段I，将规则库刻画为OBDD-LIST结构。
[0105] 表1为本发明的基于符号OBDD的包过滤防火墙规则库使用布尔变量表示的一个示例模型。图2为表1所对应的OBDD图。
[0106] 表1使用布尔变量表示
[0107]
[0108] 步骤1，对于规则各域重新排序，变量序重排为<协议类型，源IP地址，源端口，目的IP地址，目的端口>；
[0109] 步骤2，使用布尔变量表示规则，第一条规则中TCP协议号为6，整条规则表示为布尔表达式为P0＝x0′·x1′·x2′·x3′·x4′·x5·x6·x7′·x8·x9·x10′·x11′·x12·x13′·x14·x15′·x16·x17′·x18′·x19′·x20′·x21·x22·x23·x24′·x25·x26′·x27′·x28′·x29′·x30′·x31·x32′·x33′·x34·x35′·x36·x37·x38′·x39′·x40′·x41′·x42′·x43′·x44′·x45′·x46′·x47′·x48′·x49·x50′·x51·x52′·x53′·x54′·x55′·x56·x57′·x58′·x59′·x60·x61·x62·x63·x64′·x65′·x66·x67·x68·x69′·x70′·x71′·x72′·x73′·x74′·x75·x76·x77′·x78·x79′·x80′·x81·x82·x83·x84′·x85′·x86′·x87′·x88′·x89′·x90′·x91′·x92′·x93′·x94′·x95′·x96·x97′·x98′·x99·x100·x101·x102′·x103′或<00000110110010101000011101000001001011000000000001010000100011110011100000011010011100000000000010011100>,其他规则以此方式表示；
[0110] 步骤3，读取规则的前八位布尔变量，查看是否为PTCP＝x0′·x1′·x2′·x3′·x4′·x5·x6·x7′(TCP),若是则将其压缩为00表示，并将该规则存储到OBDD的文件中；
[0111] 步骤4，读取规则的前八位布尔变量，查看是否为P0＝x0′·x1′·x2′·x3·x4′·x5′·x6′·x7(UDP),若是则将其压缩为01表示，并将该规则存储到OBDD的文件中；
[0112] 步骤5，读取规则的前八位布尔变量，查看是否为P0＝x0′·x1′·x2′·x3′·x4′·x5′·x6′·x7(ICMP),若是则将其压缩为10表示，并将该规则存储到OBDD的文件中；
[0113] 步骤6，读取规则的前八位布尔变量，查看是否为********(通配符),若是则将其压缩为**表示，并将该规则存储到OBDD的文件中；
[0114] 步骤7，读取规则的前八位布尔变量，查看是否为x0′·x1′·x2′·x3′·x4′·x5·x6·x7′(TCP)或者x0′·x1′·x2′·x3·x4′·x5′·x6′·x7(UDP)或者x0′·x1′·x2′·x3′·x4′·x5′·x6′·x7(ICMP),若都不是则将其存储到线性列表的文件中；
[0115] 步骤8，读取规则的源端口的布尔变量，将其从16个压缩到11个，即使用11个布尔变量表示原来的端口号；
[0116] 步骤9，读取规则的目的端口的布尔变量，将其从16个压缩到11个；
[0117] 步骤10，将OBDD文件中的规则逐步刻画为OBDD结构，例如第一条规则刻画为OBDD结构：第一个值为0，根节点指向左分支，第二个值为0则继续指向其左分支；若接下来值为1，则指向其右分支，终结点指向决策，若该条规则决策为允许，则指向右分支的叶子节点1；
若该条规则决策为拒绝，在指向左分支的叶子节点0；
[0118] 步骤11，将规则库中的所有规则析取为一个整的OBDD结构。即：
[0119] 1)将所有规则逐步析取，第一条规则与第二条规则析取，第三条规则与第四条规则析取，依次类推，将第n-1条规则与第n条规则析取生成一个OBDD结构；其中n为规则库中规则的条数；
[0120] 2)完成上一个过程后，新的第一个OBDD与第二个OBDD析取，依次类推,将第m-1个OBDD结构与第m个OBDD结构析取生成1个新的OBDD结构；其中m为经过前一次迭代生成的新的OBDD结构的个数；
[0121] 3)重复迭代步骤2)，依次析取，直到将规则库析取为一个整的OBDD结构。
[0122] 步骤12，如此新的规则库就由OBDD文件中的OBDD图和列表文件中的线性列表组成，称为OBDD-LIST规则库；至此，阶段I结束。
[0123] 阶段II，将传入的数据包批处理的刻画为OBDD-LIST结构。
[0124] 步骤13，将传入的数据包头信息缓存入缓存器；
[0125] 步骤14，将传入的数据包头信息进行预处理，参考步骤1-11，至此阶段II结束。
[0126] 阶段III，预处理后的包头信息与规则库进行匹配，得出结果。
[0127] 步骤15，预处理的包头信息的OBDD模块与规则库中的OBDD模块合取操作，得到的结果中指向“1”叶子节点的为决策通过数据包，指向“0”叶子节点的为拒绝数据包；
[0128] 步骤16，预处理的数据包头信息的线性列表模块与防火墙规则库的线性列表模块线性匹配，如果有与之匹配的规则，根据规则的决策采取相应动，若决策为允许则允许数据包通过防火墙，若决策为拒绝则拒绝数据包；如果没有与之匹配的规则，则直接拒绝该数据。
[0129] 图3为本发明实施例关于传入防火墙的数据包的预处理的流程图，其过程与阶段I较为类似，本发明选取10000条数据包进行预处理，实际应用中不限于此数量，可参考实际运算速度设置。
[0130] 本发明的基于OBDD-LIST的批处理包过滤防火墙的实现方法，可以降低规则库的图形深度并简化节点存储，批处理数据包可以加快匹配速度，提高算法的性能。
[0131] 本说明书采用递进的方式描述，对每个方法及每个阶段依次详细地按步骤进行了说明。专业人员可以进一步意识到，结合本文中所公开的实施例各个阶段的算法步骤，能够以电子硬件、计算机软件或者二者结合的方式来实现。通过结合附图对本发明具体实施例的描述，本发明的其他方面及特征对本领域的技术人员而言是显而易见的。
[0132] 以上对本发明的具体实施例进行了描述和说明，这些实施例应被认为只是示例性的，并不用于对本发明进行限制，本发明应根据所附的权利要求进行解释。
