论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　【摘要】:针对传统防火墙线性匹配算法匹配效率低、维护困难等问题，提出并实现了一种面向IP地址集过滤的高效、灵活的Netfilter扩展框架Salist。Salist包含一个基于内核虚拟文件的表管理模块，一个可自动对IP地址集进行去重、归并和排序的表内规则管理模块，_个基于Bsearch算法的高效的包匹配模块。通过理论分析和实际测试证明，Salist使包匹配算法时间复杂度由传统线性匹配的O(n)降低为O(logn),规则合并减少了规则表占用的内核内存空间10%以上，按文件分离的规则管理机制简化了对规则集进行维护的难度。结果表明Salist使用在核心网络设备中可极大提高包转发速率，降低规则的内存占用和管理难度。
　　【关键词】：网络防火墙;Netfilter/Iptables;包匹配;Bsearch
　　0引言
　　网络防火墙的性能极大影响网络上数据传输的速度，因为通过系统的所有数据报文都会被防火墙过滤。防火墙技术的核心功能即对网络数据包进行分类管理的包分类技术1。
　　包分类器（classifier)是一组对数据包进行分类的规则(rule)集合，规则（rule)通过包头中的特定字段（IP、port、protocal等）对包进行分类，文献2]总结了包分类器的性能度量指标:1)搜索速度（Time);2)空间占用（Space);3)规则快速更新（Update);4)灵活性，通用性（ScalabilityandFlexibility)〇
　　传统的Linux下的网络防火墙的线性匹配算法和表管理机制很难满足超大网络数据量、低延时和复杂多变的业务需求2-7]。20世纪90年代以来对数据包分类算法的相关研究已经有很多。文献3]的方案考虑了网络流量的非均匀性(skewness),动态调整匹配次数较多的规则到优先级高的位置。文献4-5提出一种一次解码\多次匹配的算法，通过暂存包解析结构避免多次匹配重复解析造成的开销。文献5-6]采用有向非循环图的概念来解决相关规则间的冲突以及相似规则间的合并问题。
　　上述方案各有侧重，但都充分考虑到框架的通用性，即适应不同匹配域（port、IP、protocol等）的能力，从而导致处理过程都相对复杂。经过分析，本文发现有相当比例的防火墙需求是对包含大量IP地址（段）的规则集进行匹配并执行相同target这种场景。针对这种需求，专注于提升上述1,2,3方面的性能，结合IP地址自身的结构特点，本文提出并实现了一种高效、灵活的Netfilter扩展方案Salist,其核心思想为预先对规则进行去重、排序等处理，将包匹配时的处理过程转移至预处理阶段，同时针对已排序IP列表采用高效的二分查找算法，从而大大提高了包匹配的速度和效率，同时减少了内存的占用。
　　1传统防火墙性能分析
　　1.1Netfiler/Iptables体系简介
　　Netfilter/Iptables是Linux操作系统下的一套防火墙框架。它通过在LinuxTCP/IP网络协议栈5个不同HOOK点上设置钩子函数,允许用户注册回调函数对经过的数据包进行处理。内核空间中的框架Netfilter用于报文处理，用户空间的应用程序Iptables用于插入、修改和删除信息包过滤表中的规则。
　　如图1所示，传统方式下，包过滤规则在Netfilter中按线性顺序存储于不同的table中，每条规则包括3个部分：ipt_entry、ipt_entry_matches和ipt_entry_target。ipt_entry保存标准匹配（五元组）的内容，pt_entry_match保存扩展匹配的内容,ipt_entry_target保存匹配后执行的动作。在ipt_entry结构中中还保存有与遍历规则相关的变量target_offset与next_offset,通过target_offset可以找到ipt_entry_target的位置，通过next_offset可以找到下一条规则的位置。
　　报文通过Linux网络协议栈内置的HOOK点时，系统根据其协议类型和HOOK点位置找到预先注册的回调函数，并按照函数注册的优先级执行ipt_do_tables(),ipt_do_tables依次遍历当前table中的所有规则对数据包进行匹配，直到命中然后执行相应的target。
　　1.2Netfiler/Iptables缺点分析
　　通过对以上流程简单分析可知，相比文献2]提出的性能度量指标，传统匹配方式有如下缺点：
　　1)时间复杂度高。线性匹配算法时间复杂度为OU)。对每个包的处理时间随着规则集的规模线性增长。
　　2)空间复杂度高。Netfilter/Iptables只对规则进行简单的合法性检验,不会对规则进行去重、合并等操作，当表项越来越多时，容易生成很多重复或者范围重叠的规则项。
　　3)维护难度大。一方面Iptables工具选项多且杂，即使专业用户也容易忘记或者混淆，一旦出错可能造成服务停止等严重后果。另一方面，当规则很多的时候，很难对规则进行动态增删等操作。用户需要进行非常复杂的字符串操作才可能对表项进行合理的维护，维护成本高，出错概率大。
　　2系统设计2.1设计思路
　　针对上述应用场景及传统防火墙的缺点，Salist实现了一种改进的防火墙规则管理机制和报文匹配算法：
　　1)将不同规则表置于不同的内核虚拟文件中分别维护，使策略和规则分离，同时将规则的更新模式由通过Iptables命令下发变为直接读写文件，降低维护难度。
　　2)在配置规则时通过算法自动对表内规则进行排序、去重和归并等预处理,最终形成一个经过排序的规则文件，减少规则存储所占用的内核内存空间。
　　3)针对已排序规则集优化规则匹配算法，采用时间复杂度为O(l〇gn)的Bsearch算法，减少匹配次数,提高防火墙转发速率。
　　图2为Salist的防火墙匹配流程，规则集单独存放于不同的内核虚拟文件中并通过扩展的match模块链入Netfilter/Iptables体系。
　　2.2系统整体设计
　　图3所示为系统整体结构，主要包含以下几个部分：
　　1)表管理模块（tablemanagement)。该模块实现在内核中增加/删除规则表的功能。
　　2)表内规则管理模块（add/delete/sort/merge)。提供向特定规则表添加、删除规则的接口，实现表内规则的添加、删除、排序、归并和去重等核心功能。
　　3)扩展Netfilter的匹配（match)模块。包括内核态和用户态两部分代码，内核模块提供数据包匹配函数（match),用户态代码提供Iptables新的命令行选项的共享库，用于配置策略。
　　3系统实现
　　3.1内核态程序设计3.1.1表管理模块
　　模块初始化时通过proc_mkdir新建proc_dir/proc/nf_salist,同时通过proc_create_data在该dir下新建一个控制文件control用于增删表文件。当向control文件中写入配置命令时调用相应的write函数，该函数解析参数并执行对应的操作，表管理命令自定义的协议为：
　　*buf[0]:+/-addordeleteatable
　　*buf[1]…:tablename
　　第一位字符"+/-"表示增/删表,后面的参数表示表的名字。使用示例：
　　echo"+hello">>/proc/nf_salist/control添加个表hello
　　echo"-hello">>/proc/nf_salist/control删除表hello
　　3.1.2规则表数据结构设计
　　Salist专注解决面向IP地址集的包分类问题，针对IP地址匹配这种情况设计了相应的规则表数据结构，其中核心规则条目为structipv4_range{u32start;u32end;},单IP地址或者IP地址段都可以转化为此种结构进行描述。
　　每个规则文件在内核中维护一个叫salist_table的结构，其数据结构如图5所示。其中：name表示该规则表的表名，同时也是/proc虚拟文件系统中的文件名，base为一个指针数组，指向存储IP地址段的数组,length为数组长度，初始化时为空。预处理阶段的算法主要就是围绕rule数组进行。
　　3.1.3表内规则管理模块
　　control接口在新建table虚拟文件的时候同时初始化了其相关操作函数。可在用户空间通过直接读写规则文件的方式来对规则集进行配置，在写入规则的时候，扩展模块读取配置后会进行预处理，实现校验、去重和排序的功能。规则配置处理流程为：
　　1)parse。解析用户输入数据，检查合法性，将规则加入规则集末尾。
　　2)sort。采用堆排序算法对所有规则进行排序。
　　3)merge。归并已排序规则集（图5),释放多余内存空