UDP状态检测防火墙及实现算法.docx

第 37 卷 第 2 期2004 年 4 月武汉大学学报 (工学版) engineering journal of wuhan universityvol. 37 no. 2apr. 2004文章编号 :167128844 (2004) 022069205udp 状态检测防火墙及实现算法李俊娥 , 王婷 , 雷公武(武汉大学计算中心 ,湖北 武汉 430072)摘要 :分析了状态检测防火墙的工作原理 ,提出了一种能有效防御目前针对状态检测防火墙进行 dos 攻击的udp(user datagram protocol) 状态检测防火墙模型及其实现算法. 模型使用了动态设定虚连接生命期的方法 ,以 避免防火墙的状态表被填满而导致防火墙拒绝服务 ;在算法中利用哈希函数对 udp 虚连接进行管理 ,将算法平 均时间复杂度控制在 () ,空间复杂度控制在 ( n) , 在冲突较少的情况下 , 算法时间复杂度为 (1) , 使防火 墙具有较好的执行效率.关键词 :状态检测防火墙 ; udp ; dos ; 虚连接 ; hash中图分类号 : tp 393. 08文献标识码 :aimplementation algorithm of udp f iltering on statef ul2inspection fire wallli jun2e , wang ting , lei gong2wu(computer centre , wuhan university , wuhan 430072 , china)abstract : the principle of udp (user datagram protocol) packets inspection on stateful2inspection firewall is ana2 lyzed ; and a model , which could effectively prevent the dos attacks , and its implementation algorithm are presented. with the method of dynamic configuring the life cycle for udp virtual connections , the firewall can avoid exhausting its state2table resource. a hash table has been employed in the algorithm to manage udp virtual connections , of which theaverage time complexity is controlled at () ; the space complexity is controlled at ( n) ; and in situation of lesscollisions , the time complexity is (1) , which does not varied with the number of connections.key words : stateful2inspection firewall ; udp ; dos ; virtual connection ; hash自 checkpoint 公司提出状态检测 ( stateful2in2 spection) 的概念后 1 ,状态检测成为防火墙发展的 一种新技术. 传统的包过滤防火墙通过检测 ip 报 头的相关信息来决定单个数据包的放行与拒绝 ,而 状态检测技术采用一种基于连接的状态检测机 制 2 ,将属于同一连接的所有数据包组成的数据流 作为一个整体看待 ,并建立连接状态表 ,通过规则 表与状态表的共同配合 ,对表中的各个连接及其状 态加以识别 ,从而达到对数据流进行控制的目的. 因此 ,与传统包过滤防火墙的静态过滤规则表相比 ,它具有更好的灵活性和安全性.然而 ,最近出现了一些专门针对状态防火墙的 拒绝服务 (dos) 攻击和分布式拒绝服务 (ddos) 攻 击 ,如 c22flood 、syn2flood 和 udp2flood 等 3 . 针对 这些新的攻击 ,各防火墙厂商都在更新自己的产 品 ,设计新的算法努力使这些攻击造成的影响降到 最低 ,如 checkpoint 在 2002 年 4 月发布并于日前供 货的 smartdefense 开创了 active defense 产品的一 个新范畴 智能安全技术 ,这种技术的应用能有 效抵御 dos 攻击 ,但出于商业秘密 ,其采用的技术收稿日期 :2003208222作者简介 :李俊娥 (19662) ,女 ,副教授 ,主要研究方向为计算机网络体系结构与网络信息安全.基金项目 :国家电力公司青年科技促进费资助项目 (编号 :spqkj023) .70武汉大学学报 (工学版)2004细节和算法均高度保密. 鉴于上述情况 ,本文在讨 论状态检测防火墙如何处理 udp 数据包的基础 上 ,提出了一种能有效阻止 c22flood 和 udp2flood 攻 击的 udp 状态防火墙模型和针对该防火墙模型的 一种实现算法 ,并分析了算法的效率.1状态检测防火墙工作机制及概念 定义1. 1 状态检测防火墙的工作机制安全性是防火墙设计的主要目的. 状态检测 防火墙能监视每一个有效连接的状态 ,并根据这些 状态信息来决定在该连接上的数据包是否被允许 通过防火墙. 同时 ,状态检测防火墙对通信端口采 用动态管理技术 ,进一步提高了防火墙的安全性.防火墙的处理效率是其追求的另一个设计目 标. 状态检测防火墙截取到数据包时 ,首先检查其 是否属于某一有效连接 ,若是 ,则说明该包所属的 数据流已通过安全规则检查 ,从而不需要再进行规 则检查 ,而只需要检查其在数据流中的状态是否正 确即可. 只有当数据包不属于任何有效连接或状 态不匹配时 ,才对其进行规则检查. 这样 ,避开了 复杂的安全规则检查 ,可极大地提高防火墙的整体 效率.由上可知 ,状态检测防火墙的实现是基于连接 的 ,对于数据包自身含有状态信息的 tcp 服务来 说 ,其实现较为直观 ,然而 ,对于无连接的 udp 服 务 ,通常采用为 udp 服务建立虚拟连接的方法达 到上述目的.状态防火墙的处理流程如图 1 所示.图 1 状态防火墙处理数据包的流程示意图由于 tcp 是基于连接的 ,并且数据包自身包 含有状态信息 ,对 tcp 数据包的处理相对来说较为直观 ,本文主要讨论对 udp 数据包的处理算法 , 及如何预防基于 udp 数据包的 dos 和 ddos 攻击. 1. 2 概念定义为论述方便 ,下面给出本文涉及到的几个重要 概念的定义.定义 1virtual connection (虚连接) :udp 服务 从状态防火墙动态打开端口并为其建立连接状态、 交换数据到连接结束 ,关闭相应端口并删除其状态 信息的一次完整的通信过程称为一次虚连接.定义 2 item (状态项) : 一个状态项保存一次虚连接的状态信息 ,用六元组 item ( sa , da , sp , dp , timeout , n ) 来表示. 其中 : sa 、da 、sp 、dp 分别代表 该虚连接的源地址 、目的地址 、源端口号和目的端 口号 ,timeout 值为该虚连接保持的时间 , n 为通过 的与该状态项匹配的 udp 包数目.定义 3 max- sessions(状态表最大值) :状态表所能存储状态项的最大值.定义 4 packet key (数据包关键字) :标识通过 防火墙的 udp 数据包的信息 ,用四元组 packet ( sa , sp ,da ,dp) 来表示 ,其中 ,sa 、sp 、da 、dp 代表的意义同定义 2.定义 5 packet item (数据包与状态项匹配) : 如果 packet ( sa , sp , da , dp) = key ( sa , sp , da , dp) 或 packet ( sa , sp , da , dp) = key ( da , dp , sa , sp) , 则称该 udp 数据包与该状态项匹配 ,记为 packet item.2 udp 数据包状态检测模型2. 1 改进的 udp 数据包处理流程从状态防火墙的工作原理可以发现 ,如果没有 一定的监控机制 ,当状态匹配的 ip 数据包过多时 , 状态表就可能被充满 ,使得防火墙不能处理新到达 的数据包 , 这就是 c22flood 、syn2flood 、udp2flood 等攻击状态防火墙的基点. stephen gill 给出了针 对这类状态防火墙进行 dos 攻击所要满足的条 件 4 :dos packets/ s max- sessions/ timeout ,并指出 对于 netscreen 公司的 1000es 防火墙 ( tcp 和 udp 的 timeout 值为 60 s ,max- sessions 为 500 ,000) ,当正 常的 udp 数据包流量达到 2. 6 mb/ s 时 ,状态表就 会被充满 4 .因此 ,必须对状态防火墙进行一些改进 ,使其 在网络流量发生异常 (突然激增或达到一个上限) 时 ,能主动地采取措施来阻止状态表被填满. 从 stephen gill 总结的 dos 攻击关系式中可以看出 ,对第 2 期李俊娥等 :udp 状态检测防火墙及实现算法71于状态表中的 timeout 值 ,也应该随着网络流量的 变化而变化 ,使状态表能加快删除无效状态项的速 度 ,从而减小状态表被填满的可能性. 此外 ,当 dos 攻击发生后 ,防火墙应该发出警报 ,查找原因 ,在规 则库中添加新的过滤规则 , 从而有效地封锁非法 ip 数据包. 改进后的 udp 数据包处理流程如图 2 所示.并且状态项应该反映虚连接的状态变化. 本文将 状态项 item 作为一个对象来管理 ,每个对象有生 命周期 、属性和方法.item 的创建 :只要一个 udp 包通过防火墙并且 状态表中没有与之匹配的 item ,则新的 item 产生 ,同 时赋予生命周期 timeout ,并使记录值 n 加 1.item 的删除 : 如果在 timeout 时间内没有与之 匹配的后继 udp 包到达 ,则删除该状态项 ,表示对 应虚连接的结束.item 的状态 : item 反映当前虚连接的状态 ,从 创建到删除 ,它要经过 3 个状态变化 ,即从初始态 进入维持态再到终止态. 在本文中 ,根据 item 中的 记录值 n , 将维持状态又区分为 2 种 : n 4 和 n 5 ,用来对应不同的 udp 服务. item 的状态变迁如 图 3 所示.图 2 改进的 udp 数据包处理流程2. 2对 timeout 值的处理从上面的分析得知 ,udp 虚连接由状态表中各 项的 timeout 值来维持 ,同时 timeout 值的变化也反 应出该虚连接的状态变化 ,所以 timeout 值的设定 非常重要. 然而 ,很多状态防火墙的 timeout 值设 为固定值 ,比如 netscreen 公司的 1000es 防火墙对 tcp 和 udp 的 timeout 值都设为 60 s 5 ,这样在状 态表快充满时 ,防火墙仍然按该固定值分配新的状 态项 ,而不能提高删除无效状态项的速度 ,故容易 受到 dos 攻击. 在本方案中 ,timeout 的赋值可以因 udp 服务的不同而变化 ,如状态项建立时 timeout 均设为 40 s ,当对应虚连接的通信次数超过 4 次 , 即 n 5 时 ,其 timeout 值加 20 s(达到 60 s ,以后就 不再增加) ,这样处理可以区别对待长作业 ( n 5) 和短作业 ( n 4) 通信.以上措施能有效地防御一般的 dos 攻击 , 当 然 ,对于类似 c22flood 的攻击 ,要彻底解除 ,防火墙 还需要对数据包做进一步的深度检测 ,以便及时发 现高层 checksum 无效问题. 虽然目前让防火墙检 测每个 ip 包的高层 checksum 是否有效有一定的 难度 ,但它是今后防火墙发展的一个方向.3udp 虚连接的管理3. 1udp 虚连接对象前面已经定义 , 一个虚连接对应于一个状态 项 ,故对虚连接的管理就转换为对状态项的管理 ,图 3 item 状态变迁图图 3 注释如下 :为 udp 包通过防火墙的规则库匹配检查 ,为其在状态表中分配一个 item ;为 udp 包不能通过防火墙的规则库匹配检 查 ,丢弃 ;为 item. timeout = 0 ,删除该 item.为 item. n 5 ,表示该虚连接可能是长作业 服务.为当网络流量异常时 ,使 s1 状态的项 item. timeout = 20 s.item 的方法 : 如果进入防火墙的 udp 数据包满足 packet item ,就让其通过防火墙 ,改变 n 值 , 并根据 n 修改该 item 的 timeout 初始值 ,同时启动 计时器 ,否则让其与规则库进行匹配检查.该算法的关键在于状态项的匹配速率 ,其效率 的高低直接影响防火墙的整体效率. 为了加快匹 配速度 ,本文使用了一个哈希函数.72武汉大学学报 (工学版)20043. 2构造哈希函数从上面的分析可知 ,哈希函数应满足 : 对相同 的(sa ,da ,sp ,dp) 和 ( da ,dp , sa , sp) 经过哈希函数计 算后应该得到同一个值 , 设哈希函数的自变量为 packet (sa , sp , da , dp) , 按如下规则构造哈希函数 hash ( packet) 6 :(1) ip 地址 addr : addr = sa + da ,记为 addr 32 ,0 (共 33 位) ;(2) 端口号 port :port = sp + dp ,记为 port 16 , , 0 (共 17 位) ;addraddr port(3) 构造位数组 sum 59 , 0 = addr 32 ,0 ,0 10 ,port 16 ,0 (共 60 位) ;(4) 由于 sum 是一个 51 位的数 ,我们用哈希函 数中常用的折叠法 ,对 sum 59 , ,0 分 3 段进行 折叠移位异或操作 ,取结果为 rlt 19 , ,0 . 其等 效运算如图 4 所示.哈希函数的值域空间为 : 0 hash ( packet) 220 - 1 = 1m - 1 . 并且算法中的 (1) 、(2) 加法运算 和(4) 异或运算 ,对 cpu 来说为一次性计算 ,故该 算法有较高的执行效率. 此外 ,在 (4) 中 经过两次 异或运算后得到的索引值相关性小 ,具有很好的离 散性 ,产生冲突的可能性较小.a32a31a30a29a28a27a26a25a24a23a22a21a20a19a18a17a16a15a14a13a12a11a10a9a8a7a6a5a4a3a2a1a00000000000p16p15p14p13p12p11p10p9p8p7p6p5p4p3p2p1p0r19r18r17r16r15r14r13r12r11r10r9r8r7r6r5r4r3r2r1r0rlt图 4 哈希函数构造示意图3. 3哈希函数冲突解决策略尽管哈希函数的目标是使冲突减少 ,而实际上 冲突一般是无法避免的 ,故哈希函数的实现必须包 含某种形式的冲突解决策略. 本文采用开散列法 , 哈希函数的值域为 0 ,1m1 ,可以建立一个头指 针数组 hp 1m ,每个 hp i ( 0 i 1m - 1) 为一 个冲突链表的表头指针 ,其初值全为 null .添加 item :如果 hp hash ( packet) = null ,则 为以 hp hash ( packet) 为表头指针的冲突链分配 一个 节 点 node , 用 来 存 放 item ( sa , sp , da , dp , tiemout , n ) . 如果 hp hash ( packet) null ,同样 分配一个节点 node 存放 item ,并将该 node 插入以 hp hash( packet) 为表头指针的冲突链的末尾 ,作 为最后一个节点.删除 item :如果以 hp i 为表头的冲突链中某 个节点 node ,满足 item. timeout = 0 ,则删除该节点 ; 如果删除该节点后链表为空 ,则置 hp i = null .状态检测 :对于到达的 udp 包 ,如果 hp hash ( packet) = null ,则对该数据包进行规则匹配 ,通 过匹配检查则在状态表中为其添加一个 item ,否则 丢弃 ;如果 hp hash ( packet) null , 就在以 hp hash ( packet) 为头指针的链表中依次匹配每个节 点 node ,如果有 packet item ,就让其通过 ,否则丢 弃.采用上述动态添加和删除状态项的方法 ,udp状态表的容量是动态变化的 ,在系统资源充足的情 况下 ,也可以避免因状态表被填满而导致的拒绝服 务攻击 ;另一方面 ,还可以使防火墙在 udp 访问减 少时较少占用系统资源.4. 4 算法复杂度分析本算法中哈希函数有 1m 个索引项 , 对应着 1m 个冲突链表. 在最好的情况下 (无冲突 ,即每一 个 hp i 中最多有一个节点) ,只需要比较一次就 可以判断该 udp 包是否匹配 ,算法的时间复杂度 为 (1) , 匹配效率不受并发连接数量的影响 ;在最 坏的情况下 ( n 个节点全在以 hp i 为表头的链表 中 ,且要查找的节点为链表的最后一个节点) ,需要 比较 n 次 , 算法的时间复杂度为 ( n) . 而该哈希 函数的平均时间复杂度为 () . 如果各项分布合 理 ,任一次匹配过程不会比平均情况更糟.该哈希函数的目标空间为 1 m(即 20bit) ,每个 表头指针为 4 个字节 ,每个节点包括两个字段 (存 放 item 和指向下一个节点的指针) ,共占用 20 个字 节 ,则 n 条并发虚连接 (一个虚连接对应一个 item 项 ,一个 item 项对应一个节点) 对内存的需求量 (bytes) 为memtotal = 4 1m + 20 n = 4m + 20 n因此 ,算法的空间复杂度为 ( n) , 内存占用 随并发连接数量的增加而线性增加.第 2 期李俊娥等 :udp 状态检测防火墙及实现算法734结束语安全性和效率一直是防火墙产品设计追求的 主要目标. 状态检测技术可以极大地提高防火墙 的安全过滤能力 ,并在状态匹配算法设计合理的前 提下提高其执行效率. 本文给出了 udp 状态检测 防火墙的一种算法框架 ,设计了用于管理 udp 虚 连接的 hash 算法 ,并对其复杂性进行了分析. 所 提出的改进方案能够有效防止专门针对状态防火 墙的基于 udp 服务的 dos 攻击 ; 用于管理虚连接 对