IP分片重组算法_RFC815_的实现及其改进.docx

ip 首部包含了分片和重组所需的信息identifi cat ion r d m fragment o ffsetf f16 3 13图 1 ip 首部包含了分片和重组所需的信息ip 分片重组算法（rfc815） 的实现及其改进林绍太， 张会汀， 郑力明( 暨南大学 信息科学技术学院，广东 广州 510632)要：分片与重组是 ip 机制之一。ip 数据报可以在网关处被分片，各分片分别送达。目的主机的 ip 层将接收到的摘所有分片重装成一个完整的数据报。介绍了 ip 分片重组的原理，在此基础上介绍了 rfc815 算法的实现，并对重组算法做了优化改进，在保证安全性的同时提高算法的效率。关键词：网络安全； 分片重组； rfc815； tcp/ip 协议中图法分类号：tp393.08文献标识码：a文章编号：1000-7024 (2005) 04-0911-03implementation and improvement of ip datagram reassembly algorithms (rfc815)lin shao-tai,zhang hui-ting,zheng li-ming(college of information on science and technology, jinan university, guangzhou 510632, china) abstract：one of the mechanisms of ip is fragmentation and reassembly. ip packets can be fragmented at the gateway, and then be sent to the destinaion. the ip layer at the receiving host must accumulate these fragments to completely reconstitute the original datagram. the concept of ip datagram assembly is described, based on which the implementation of rfc815 is introduced, and then on the premiseof security, efficiency is improved by ameliorating management of hole descriptor.key words：network security; ip fragmentation and reassembly;rfc815; tcp/ip protocol数据，都必须完成数据包的分片或重组。1引言分片是分组交换的思想体现，也是 ip 协议解决的两个主 要问题之一。在 ip 协议中的分片算法主要解决异种网最大 传输单元 (mtu) 的不同，但是分组在传输过程中不断地分片 和重组会带来较大的工作量并引入不安全因素。ip 碎片经常 被用来 dos 攻击，典型的例子便是 teardrop 和 jolt2。碎片攻 击不仅会攻击操作系统，由于许多网络工具，如防火墙、入侵 检测系统（ids）也在内部做了分片组装，如果处理不当，也同 样会遭受攻击，如著名的 checkpoint 的防火墙 fw-1 某些版本（最新的已经改正了）便同样会受到碎片 dos 攻击。所在分 片重组算法的实现直接影响到网络系统的安全性。 r：保留未用；df：dont fragment,“不分片”位，如果将这一比特置 1，ip 层将不对数据报进行分片；mf：more fragment, “更多的片”，除了最后一片外，其它每个组成数据报的片都要 把比特置 1；fragment offset：该片偏移原始数据包开始处的位 置。偏移的字节数是该值乘以 8。3rfc815 算法的实现现在大多数操作系统对 ip 分片的重组仍使用一般的排 序算法，就是对每一个 ip 分片根据它的偏移量和长度在分片 序列中进行排序。这种算法不仅效率低下，而且安全性不够。 首先，它必须要记录所有的分片，这本身就是一个很麻烦的工 作；其次，当一个新的分片到来时，它必须将这个分片与已收 到的分片合到一起。这是一个非常复杂的工作，因为这样的 话有很多种情况要考虑，如或许这个分片正好是某两个分片 之间缺的那一个，或者与现存的某个分片有重叠之处，甚至与 某个现存的分片一样，或者位于两个分片之间，但并没有完全2ip 分片算法的原理分片重组是 ip 层一个最重要的工作，其处理的主要思想 是：当数据包从一个网络进入另一个网络时，若原网络 的数据包长度大于新网络所允许的最大数据包长度, 必须 进行分片。 因而在数据包的报头有若干标识域注明分 片包的共同标识号、分片的偏移量、是否最后一片及是否允许 分片。传输途中的网关利用这些标识域进行分片，目的主机 把收到的分片进行重组以恢复数据。因此，分片包在经过网 络监测设备、安全设备、系统管理设备时，为了获取信息、处理收稿日期：2 004-05-18。 基金项目：广东省科技计划基金项目 （200 3c1010 38）。作者简介：林绍太 （198 0-），男，广东湛江人，硕士，研究方向为计算网络安全； 张会汀 （19 43-），男，广东梅州人，教授，研究方向为多媒 体通信与信息系统； 郑力明 （1 971-），男，讲师，研究方向为多媒体网络通信和网络安全。 911 ：；填补这两个分片之间的内容。因此这种分片算法必须考虑相当多的情况，非常容易出现漏洞而给黑客们以可乘之机。其 实 ietf 对分片重组已有了推荐的算法 rfc815（ip data- gram reassembly algorithms）。rfc815 的描述的重 组算法相当简单，在rfc815 算法中使记录分片的工作量减少 到了最少。而且不论这些分片有什么情况、以什么顺序到达， 只需要一个大小等于分片前数据包大小的存储区。为了说明这种算法，有必要定义一些术语。我们把重组 缓冲区中空的数据区称之为“洞”，每一个这样的“洞”包括两 个元素：洞头，洞的第 1 个字节的序号；洞尾，洞的最后一个字 节的序号。我们把这一对变量称为“洞描述符”，我们把一个 数据报所有的“洞描述符”称为“洞描述符链表”。当一个新的分片到达时，它有可能填充一个或多个这样 的洞。我们将检查“洞描述符链表”的每一项看是否有洞被刚 来的分片所填充。如果是的话，就从链表中去除这一项。最 后一个分片到来将消除链表中的每一项。这时，数据包就可 以完全被重组，并交给上一层协议做进一步的处理。rfc815 算法分两段来描述：第 1 部分指明当一个分片到 来时，为了确定有无洞被这个分片填充时所采用的步骤；第 2 部分将描述一个管理“洞描述符”简单算法。3.1 分片处理算法一个新到的分片可以有很多方式填充现存的洞：最简单 的是它把一个洞完全填充；或者，它在洞头或者洞尾留下空 间；或者最后该分片处于洞的中间，在洞头和洞尾都留下一小 段空间。该算法要将每一个洞与新到的分片值进行 4 次测试。我们以最早到达的分片作为算法的开始。创建一个空的数据缓冲区并在洞描述链表中建立一项，这一项表明数据包 完全没有开始重组。其中，洞头为零，洞尾为无穷大（这里的 无穷大是指一个非常大的整数，大于 576，具体的数目可根据 实现情况而定）。下面的 8 个步骤被用来将每一个新到的分片插入到重组 后的数据包所用的存储区内。新来的分片由片头 （fragment. first） 分片的第 1 个字节序号和片尾（fragment.last） 分 片的最后一个字节序号来描述。的数目由实现者确定) 的洞。最后，我们将收到的数据包的最后一个分片。这时，从缓冲区的最后一个字节到无穷大的这个 洞描述符可以被去掉。通过 ip 首部叫做“more fragment”这个 标志位来表明这种情况。对这一步的测试可以防止我们建立 一个从数据包的最后一个字节到无穷大的洞描述符。) 返回步骤如果洞描述符链表为空的话，那么数据包的重组也完成了，将它传递给上一层协议做进一步的处理，否则返回。洞描述符链表的管理上述 8 个步骤中最复杂的不是进行算法测试，而是从洞 描述符链表中增加或删除链表中的元素。有一个很简单的方 法来管理这些洞描述符。就是把洞描述符放到每一个洞开始 的字节里。注意通过重组算法的定义，每一个分片最小是 8 个字节。存放洞头、洞尾各需要两个字节，另外两个字节被用 来在洞描述符列表中连结其它的元素之用。这样还留有两个 字节来处理实现特征。对于这种存储策略只有一个明显的缺点。就是在从分片 中拷贝数据到重组缓冲区之前要进行上述 8 个步骤。如果先 拷贝数据，那么就会破坏一个或多个洞描述符。一旦这种算 法开始，所有以后要删掉的洞描述符就已经被全部地废弃了。在整个重组缓冲区中分散的这些洞描述符必须排成某种 链表使它们自己可以被查找到。这就意味着必须有一个指针 指向链表的首部。在许多情况下，这个指针可以被存储在与 每一个重组缓冲区相联系的描述符块区域中。如果这样的缓 冲区也没有的话，一个不好但有效的办法是将链表头存在重 组缓冲区中 ip 首部不再使用的字段，最典型的如校验和字段。3.3 关于 ip 首部的可选项部分上述描述只是一个对 815 算法简单的描述。它已经假定 在数据包重组的过程中没有 ip 选项起作用。关于选项的困难 之处在于直到收到数据包的第 1 个分片(这里的第 1 个分片包 是指包含原始数据包零字节的分片，不一定是接收顺序中的 第 1 个) 才知道 ip 首部有多大。这是因为由于某些选项被相 同地复制到数据包的每一个分片，而其它的选项，如“记录路 由”，只是被放到第 1 个分片。只有知道了首部有多大才能知道从分片中的哪里开始复制数据到缓冲区。如果最早到达的分片正好是第 1 个分片，那么这一切都 没有问题。否则，有两种解决办法：一种办法是在重组缓冲区 内给 ip 首部留出最大可能的长度空间，事实上最大长度并不 大，为 64 个字节；或者可以简单地赌第 1 个分片没有可选项， 如果当第 1 个分片最后到达时发现有可选项，就将数据在缓 冲区内移动足够的空间来容纳可选项。在拷贝数据时惟一的 危险是会废掉将洞描述符连在一起的指针。3.28 个步骤从洞描述链表中选择下一个洞，如果没有洞，则执行步骤 ； 如果片头大于洞尾，执行步骤 ； 如果片尾小于洞头，执行步骤 ；(如果上面两步都为真的话，那么这 个新到的分片根本就不覆盖这个洞，我们对这个洞可以不予处 理。选择下一个洞进行检查作为算法的开始。) 从洞描述符 链表中删除当前项；(既然上述两个步骤都不为真，那么这个新 来的分片肯定与这个洞有着某种关联。因此，当前的描述符将 不再有效，删掉它，并在以下的两个步骤中决定是否有必要创 建新的描述符。) 如果片头大于洞头，那么创建一个新的洞描 述符，它的洞头等于原来的洞头，它的洞尾等于片头减 1；(如 果步骤 为真，那么这个洞的开始部分没有被这个分片覆盖， 我们对这个小洞创建了一个洞描述符。) 如果片尾小于洞尾， 而且 ip 首部的“more fragment”字段为真的话，我们将创建一个 新的洞描述符，其中洞头等于片尾加上 1，洞尾等于原来的洞 尾；(这一步基本上是步骤 的镜像。最开始，我们不知道重组 后的数据包有多大，因此我们创建了一个从零到无穷大 (具体4对 rfc815 算法的改进上面就是 rfc815 算法的主要思想。我们必须承认这种解决问题的方式是相当新颖的。但是，该算法是在 1982 年 7 月 制定的，那时估计还没有黑客这个概念，因此对一些情况考虑 得不是很周到，比如它对分片有重叠的这种情况没有予以足够 的重视。而且该算法中对洞描述符的存放地方比较晦涩难懂。 因此，在了解了算法的核心思想后我们在实践中针对“洞描述 912 片头 片尾洞 已到达分片 洞头 洞尾图 2 分片重叠示意图符”的管理做了一些改进，采用了较为容易的链表方式来处理。首先，我们对分片的情况做了限制。上述算法中片头大 于洞头和片尾小于洞尾这两种情况是分开的。这样的话对于 分片重叠的情况是采用覆盖的方式，比如片头大于洞头而且 片尾大于洞尾，就是分片重叠，把下一个分片的首部给覆盖 了，示意图如图 2 所示。unsigned char unsigned int unsigned int；protocol;saddr;daddr;对于一个合法的分片，首先在洞描述符链表中进行操作，完成“洞”的增加和减少等工作。然后再在数据链表中创建一 个节点，指向分片数据部分,分片仍保持内核中的结构体形式。 同时，在 ip_frage_queue 结构体中将 data_length 进行累加，如果 分片中的偏移量为零，则对 iph_len 赋值。这个 iph_len 才是真 正的 ip 首部长度，解决了对 ip 首部中可选字段的处理。这样 的话，一旦洞描述符链表为空，那么就可以根据数据链表来一 个一个地把数据复制到一个完整的缓冲区里，该缓冲区的长 度为 data_length + iph_len，解决了上述算法中对 ip 首部中可选 项的处理。同时，为了考虑到 ip 首部的长度的变化和复制数 据的高效，在数据链表的结构体中加入了head_len、data_len 和 frage_off，其中 head_len 是该 ip 分片的首部长度，data_len 是该 分片中的数据长度，frage_off 是该分片在原来 ip 包中的偏移 量。这样的话在复制数据时可以不用从第 1 个分片开始复制， 开始地址为*(data + head_len * sizeof(char)，长度为 data_len，复 制的目的地址为*(data_buffer + frage_off * sizeof(char)*8)，按照 分片到来的顺序即可，减少了一次对分片数据进行排序的过 程。当 frage_off 等于零时就要复制 ip 首部了，地址为*data，复 制的数据长度为 data_len + head_len，目的地址为*(data_buffer)。在完成上述算法改进后，还进行了大量的测试工作。由 另外一台主机向进行重组的主机发送大量的分片，经过反复测试，程序运行正常，说明该优化改进的算法是正确和有效的。本文在实现时限制为片头大于等于洞头且片尾小于等于洞尾，这样排列组合只有 4 种情况，不允许有分片重叠情况。 改进最大的是对“洞描述符”的管理。算法中对“洞描述 符”的处理是放在“洞”的开始字节里，若是按照算法中那样做 的话会浪费宝贵的内存。因为该算法是先分配一块内存，然 后把接收到了的 ip 分片不断地往里面写。但是谁也不知道分 片前 ip 包有多大，所以算法中对该内存大小是无穷大，实际 上这个无穷大也最多只能是 64k，要考虑到最坏的情况。这 样对于只有几 k 或者十几 k 的 ip 包而言就属于浪费了。在 实际中我们是单独创建了一个“洞描述符链表”来存放这些 “洞描述符”，同时也创建了一个数据链表用来联系各个分片 中数据的位置，达到了将“洞”和数据分开来存放的效果。这 样在所有的分片到达后再根据具体大小分配内存存放ip 数据 包数据，在效率不变的情况下减少了内存的浪费。具体的结构体定义（包括控制这些重组缓冲区的结构体）如下：struct holeunsigned short int first; unsigned short int last; struct hole *next;struct hole *prev;struct frage_data5结束语本文对 ip 碎片重组算法 rfc815 进行了优化改进，使得重组算法在提高效率的同时减少了内存的浪费，并且还容易 理解和实现。应用这种优化改进的重组算法，在我们的课题基于专用协议栈的流过滤网络防火墙的研制的研究中，取 得了良好的效果。参考文献:1richard stevens. tcp/ip 详解m. 第 2 卷. 北京: 机械工业出社, 2000. 218-237.yawl. ip 分片重组的分析和常见碎片攻击 v0.2eb/ol. /jiaoxue/jiao8/jiaoc962.htm.anonymous. 最高安全机密m. 北京: 机械工业出版社出版,2002.137-150.朱雁辉