一 前言

本文对linux的IP组装算法进行了分析，因为IP碎片经常用于DOS等攻击，在文章后面我结合了一些攻击方法进行了更进一步的说明。内核主要参考版本是2.2.16，另外简要的介绍了2.4.0-test3中的一些变化.

二 目录

1- 概述
2- 关键数据结构
3- 重要函数说明
4- 2.4系列的变化
5- 常见碎片攻击


1. 概述

在linux源代码中，ip分片重组的全部程序几乎都在都在\net\ipv4\ip_fragment.c文件中。其对外提供一个函数接口ip_defrag()。其函数原型如下：

struct sk_buff *ip_defrag(struct sk_buff *skb)

众所周知，网络数据报在linux的网络堆栈中是以sk_buff的结构传送的，ip_defrag()的功能就是接受分片的数据包(sk_buff)，并试图进行组合，当完整的包组合好时，将新的sk_buff返还，否则返回一个空指针。

此函数在其他文件中的调用如下：

ip层接收主函数为ip_rcv()(\net\ipv4\ip_input.c),任何IP包都需经过此函数处理。如果此包是发往本机，则调用ip_local_deliver()函数（\net\ipv4\ip_input.c）进行处理，一般的系统碎片只有在到达最终目的的时候才进行重组（尽管在传输过程中可能被进一步分成更小的片）。在ip_local_deliver()中我们可发现如下代码：

if (sysctl_ip_always_defrag == 0 && /*编译时未设置提前组装*/
(iph-〉frag_off & htons(IP_MF|IP_OFFSET))) { /*判断是否是分片包*/
skb = ip_defrag(skb); /*条件满足，进行组装*/
if (!skb) /*若组装好则进行下一步处理，出错
return 0; 或仍未组装完返回*/
iph = skb-〉nh.iph; /*重新定位ip头的指针*/
}

iph-〉frag_off只有在设置MF（more fragment）或offset!=0才意味着是分片包，因此此处的检验理所当然，但为什么判断sysctl_ip_always_defrag == 0呢？在看ip_rcv()时我们应该已经注意到在刚进行了版本号，长度，校验和等判断后，有如下一段代码：

if (sysctl_ip_always_defrag != 0 &&
iph-〉frag_off & htons(IP_MF|IP_OFFSET)) {
skb = ip_defrag(skb);
if (!skb)
return 0;
iph = skb-〉nh.iph;
ip_send_check(iph);
}

即如果sysctl_ip_always_defrag==1的话，ip_defrag()的调用位置将有变化，对任何进来的IP分片都要进行重组，可以想像，如果此机器作路由器的话，将对所有的分片组装好后，才会进行转发。此举一般是没有必要的。这个值可以通过sysctl命令动态设置，用sysctl -a可以看到在一般的系统中，此值被设为0：

#sysctl -a
......
net.ipv4.ip_always_defrag = 0
......


2. 关键数据结构（2.2系列）

每一个分片用ipfrag结构表示：

/* Describe an IP fragment. */
struct ipfrag {
int offset; /* offset of fragment in IP datagram */
int end; /* last byte of data in datagram */
int len; /* length of this fragment */
struct sk_buff *skb; /* complete received fragment */
unsigned char *ptr; /* pointer into real fragment data */
struct ipfrag *next; /* linked list pointers */
struct ipfrag *prev;
};

这些分片形成一个双向链表（在linux内核中，若需要使用链表，除非有特殊需要，否则推荐双向链表，见document\CodingStyle）,表示一个未组装完的分片队列（属于一个ip包）。
这个链表的头指针要放在ipq结构中：

/* Describe an entry in the "incomplete datagrams" queue. */
struct ipq {
struct iphdr *iph; /* pointer to IP header */
struct ipq *next; /* linked list pointers */
struct ipfrag *fragments; /* linked list of received fragments */
int len; /* total length of original datagram */
short ihlen; /* length of the IP header */
struct timer_list timer; /* when will this queue expire? */
struct ipq **pprev;
struct device *dev; /* Device - for icmp replies */
};

注意每个ipq保留了一个定时器（即struct timer_list timer;）。

ipq也会形成一个链表，它们是内核当前未组装完的所有IP包。为了便于查找，保留了一个
hash表：
#define IPQ_HASHSZ 64
struct ipq *ipq_hash[IPQ_HASHSZ];
#define ipqhashfn(id, saddr, daddr, prot) \
((((id) 〉〉 1) ^ (saddr) ^ (daddr) ^ (prot)) & (IPQ_HASHSZ - 1))

--------_____________
| 1 | |
-------- ----------- ------------ ------------
Hash表 | 2 | | ipq1 |----〉| ipfrag1 |-----〉| ipfrag2 |------〉.......
-------- ------------ ------------- ------------
...... |
-------- \/
| 63 | ------------ ------------- -----------
-------- | ipq2 |----〉| ipfrag1 |-----〉| ipfrag2 |------〉.......
------------ ------------- -----------
|
\/
------------ ------------- -----------
| ipq3 |----〉| ipfrag1 |-----〉| ipfrag2 |------〉.......
------------ ------------- -----------
|
\/
........

每个IP包用如下四元组表示：（id,saddr,daddr,protocol）,四个值都相同的碎片保留在一个IPQ中，即可组装成一个完整的IP包。

此结构在2.4内核中有了改动，具体将在下文中声明。

3. 重要函数说明（2.2系列）

3.1 ip_defrag()
ip_defrag()是整个流程的入口，下面我们首先对ip_defrag()作一定的说明。

(1)为了防止因保留分片而造成内存消耗过大，linux设置了界限来防止这种情况，如果超过了内存使用的上限，则清空内存中最老的队列（ipq）.所用内存的大小保存在变量ip_frag_mem中，当然，对它的读写都应是“原子”操作（atomic_sub，atomic_add，atomic_read，etc）。
其定义在文件ip_fragment.c前部：

atomic_t ip_frag_mem = ATOMIC_INIT(0); /* Memory used for fragments */

if (atomic_read(&ip_frag_mem) 〉 sysctl_ipfrag_high_thresh)
ip_evictor();

ip_evicator的具体操作将在下文中描述。

（2）以id, saddr, daddr, protocol为标志检索是否已经建立了相应的ipq，若发现，则返回ipq的指针，并重置定时器。

qp = ip_find(iph, skb-〉dst);

（3）此时有一个if/else对，其作用是：
如果ipq已经存在，则证明已经有同一个包的其他分片到达。检查此片是不是第一个分片（因为分片到达顺序可能错乱），若是，将ip头信息和头长度保留在ipq结构中（）；
if (offset == 0) {
/* Fragmented frame replaced by unfragmented copy? */
if ((flags & IP_MF) == 0)
goto out_freequeue;
qp-〉ihlen = ihl;
memcpy(qp-〉iph, iph, (ihl + 8));
}

如果不存在，当然要建立一个了：
qp = ip_create(skb, iph);
if (!qp)
goto out_freeskb;

ip_create便是分配出一块内存，初始化这个ipq，并在hash表中登记。

到此为止ipq已经肯定存在了，不管是已经存在的，还是我们刚才生成的。

（4）对包的长度进行检测，如果超过了ip包的最大范围，则报警，并丢弃此包。jolt2便是利用这点将window系统打瘫的。由于linux做了这种检查，所以基本免受其害。

（5）调节end值（数据的结尾位置），如果是最后一个包，则最终整个ip包的长度便可以知道了，为了组装时方便，将其记录到ipq中。
/* Determine the position of this fragment. */
end = offset + ntohs(iph-〉tot_len) - ihl;

/* Is this the final fragment? */
if ((flags & IP_MF) == 0)
qp-〉len = end;

（6）接下来很长一段代码（line481-line586）便是定位这份分片在整个数据包中的位置。如果分片之间有重合（恶意攻击和其他异常），则能归并便归并。这个问题我们将在后面（常见碎片攻击中）详谈。

（7）此时我们已经知道这个分片的具体位置了。我们要生成一份新的ipfrag结构，并将其放到
我们刚才找到的正确位置上去。
tfp = ip_frag_create(offset, end, skb, ptr);
if (!tfp)
goto out_freeskb;

/* Insert this fragment in the chain of fragments. */
tfp-〉prev = prev;
tfp-〉next = next;
if (prev != NULL)
prev-〉next = tfp;
else
qp-〉fragments = tfp;

if (next != NULL)
next-〉prev = tfp;

（8）ip_done函数检查是否所有的分片已经到齐，如果到齐，则将其组装成一个新的sk_buff（调用ip_glue）,并最终返回到调用ip_defrag的地方。

if (ip_done(qp)) { /*全部到齐了么？*/
/* Glue together the fragments. */
skb = ip_glue(qp);
/* Free the queue entry. */
out_freequeue:
ip_free(qp); /*原有的ipq结构已经不需要了，释放。*/
out_skb:
return skb; /*组装完成，可以返回了*/
}

如果没有到齐，则返回NULL.

至此全部组装过程结束。

3.2 ip_evictor（）

当分片所用的内存超过一定的上限时(sysctl_ipfrag_high_thresh)会调用ip_evicator以释放内存。
ip_evicator会找寻可清空的IPQ，并将其清空，直到到达到可用的下限（sysctl_ipfrag_low_thresh）
。

这个值在ip_fragment.c中按如下定义：
int sysctl_ipfrag_high_thresh = 256*1024;
int sysctl_ipfrag_low_thresh = 192*1024;

同样，用sysctl -a可可看到这两参数，同时可以动态修改。
＃sysctl -a
......
net.ipv4.ipfrag_low_thresh = 196608
net.ipv4.ipfrag_high_thresh = 262144
......

理论上ip_evicator应该采用LRU算法，将最古老的IPQ清除。但目前linux(包括2.4.0)没有实现此功能，只是将hash表按次序清空，这样的好处是简单易行。

3.3 ip_glue（）

ip_glue（）函数将负责将一个所有分片已经到齐的的IP包组合好。当这一步进行时，所有的分片已经按顺序排好，并解决了所有的重叠问题。因此其流程相应很简单。
首先生成一个足够大的（足以容纳所有的分片包长度的总和）新的skbuff：
skb = dev_alloc_skb(len);
if (!skb)
goto out_nomem;
调整一些必要的指针后，就在一个while循环中依次将原有分片的内容用memcoy拷贝到新的skbuff中。再进行一些指针调整后，过程结束，将新的skbuff返回。

3.4 ip_expire（）

前面已经提到，每个ipq保留了一个定时器，当一定时间以后组装还没有完成，将清空此队列。定时器的值保留在sysctl_ipfrag_time中：
int sysctl_ipfrag_time = IP_FRAG_TIME;
（在/include/net/ip.h中有#define IP_FRAG_TIME (30 * HZ) ）
此值也可以用sysctl设置。
定时器的具体实现机制的没有分析。

4. 2.4系列的变化

其实如果仔细看一下，2.4的分片组装代码的流程与2.2系列基本相同，不同的是将函数的分工变化了。由于原ipfrag结构保留的结构均可在skbuff中得到，在2.4中将此结构取消了，并对ipq结构做了一些修改。其他主要变化有：
1）ip_defrag分成了ip_defrag和ip_frag_queue两部分。
2）ip_glue换名成ip_frag_reasm,流程基本未动。
3）现在ipq中用meat保留现有的分片长度的累加值（已经解决重叠），如果此值到达总长度，则意味着所有的分片到达，因此取消了ip_done函数，不必每次遍历一次链表，因此在效率上有了较大的提高，抗小碎片攻击的能力得到加强。


5.常见碎片攻击

IP碎片经常被用来作DOS攻击，典型的例子便是teardrop和jolt2，其原理都是利用发送异常的分片，如果操作系统的内核在处理分片重组时没有考虑到所有的异常情况，将可能引向异常的流程，造成拒绝服务（DOS）。

我们首先要仔细考虑一下linux在处理分片重叠时的办法。
代码主要在ip_defrag中，首先要遍历链表，定位此分片的位置，具体就是给prev和next两指针赋上正确数值。然后处理与前面的重合,代码如下：

/* We found where to put this one. Check for overlap with
* preceding fragment, and, if needed, align things so that
* any overlaps are eliminated.
*/
if ((prev != NULL) && (offset 〈 prev-〉end)) {
i = prev-〉end - offset;
offset += i; /* ptr into datagram */
ptr += i; /* ptr into fragment data */
}

注意此处offset已经乘了8,即以byte为单位了。举个形象一点的例子，如果有这样两个分片：

offset1=0 end1=256
-------------------------
| Frag1(先到) |〈---------prev
-------------------------

offset2=64 end2=640
------------------------------------------
| Frag2（后到） |
------------------------------------------

处理后变为：

offset1=0 end1=256
-------------------------
| Frag1(先到) |〈---------prev
-------------------------

offset2=256 end2=640
-----------------------
| Frag2（后到） |
-----------------------

紧接着做与后面分片重叠的处理，代码如下：
/* Look for overlap with succeeding segments.
* If we can merge fragments, do it.
*/
for (tmp = next; tmp != NULL; tmp = tfp) {
tfp = tmp-〉next;
if (tmp-〉offset 〉= end)
break; /* no overlaps at all */

i = end - next-〉offset; /* overlap is ’i’ bytes */
tmp-〉len -= i; /* so reduce size of */
tmp-〉offset += i; /* next fragment */
tmp-〉ptr += i;

/* If we get a frag size of 〈= 0, remove it and the packet
* that it goes with.
*/
if (tmp-〉len 〈= 0) {
if (tmp-〉prev != NULL)
tmp-〉prev-〉next = tmp-〉next;
else
qp-〉fragments = tmp-〉next;

if (tmp-〉next != NULL)
tmp-〉next-〉prev = tmp-〉prev;

/* We have killed the original next frame. */
next = tfp;

frag_kfree_skb(tmp-〉skb);
frag_kfree_s(tmp, sizeof(struct ipfrag));
}
}

其中if (tmp-〉len 〈= 0)判断后面的是为了处理teardrop攻击的，将在后面描述。

我们继续用图表示，如果有这样两个分片：

offset1=128 end1=960
---------------------－－－－－－－－－－----
next-------〉| Frag1(先到) |
(tmp) -----------------------－－－－－－－－－－--

offset2=64 end2=320
-------------------------
| Frag2（后到） |
-------------------------

处理后将变为：

offset1=320 end1=960
--------－－－－－－－－－－----
next-------〉| Frag1(先到) |
(tmp) ----------－－－－－－－－－－--

offset2=64 end2=320
-------------------------
| Frag2（后到） |
-------------------------

更复杂的情况不再一一列举，下面我们便可看一下具体利用分片的攻击办法：

（1）Teardrop(CERT CA-97.29，bugtraq id 124)

许多老系统在处理分片组装时存在漏洞，发送异常的分片包会使系统运行异常，teardrop
便是一个经典的利用这个漏洞的攻击程序。其原理如下（以linux为例）：
发送两个分片IP包，其中第二个IP包完全与第一在位置上重合。如下图：

〈- len1 -〉
-------------------------
| Frag1 |
-------------------------
offset1 end1

〈- len2 -〉
-------------
| Frag2 |
-------------
offset2 end2

在linux(2.0内核)中有以下处理:
当发现有位置重合时（offset2改len2的值：
len2=end2-offset2;
注意此时len2变成了一个小于零的值，在以后处理时若不加注意便会出现系统崩溃的问题。
但具体到什么地方出现问题没有追踪过，毕竟这已经是陈年旧事了。
新的版本检查了这个值的大小，如果出现小于零的情况，则把这个分片丢掉。

（2）Jolt2(MS00-029)

jolt2是2000年五月份出现的新的利用分片进行的攻击程序，几乎可以造成当前所有的windows
平台（95,98,NT,2000）死机。原理是发送许多相同的分片包，且这些包的offset值
(8190*8=65520 bytes)与总长度(48 bytes)之和超出了单个IP包的长度限制（65536 bytes）。
如下图：

0 65535
------------......-------------
| Max normal Fragment |
------------......-------------

65520 65568(〉65535)
----------------
|Jolt2 Fragment|
----------------

在linux中这种几乎马上就会被丢掉，在ip_defrag中有：
/* Attempt to construct an oversize packet. */if((ntohs(iph-〉tot_len) + ((int) offset)) 〉 65535)goto out_oversize;
尽管在后面（out_oversize出）对报警信息已经做了net_ratelimit()处理，但在遭受攻击时,每5秒便打印一条信息还是很繁人，可以更改net_ratelimit()的间隔时间和干脆关掉此条警告。

对windows系统便不知道它是怎么处理的了，一打的话CPU便会达到100%。2000的SP1号称已解决了问题，但没有试过。

（3）bugtraq id 376 Linux IP Fragment Overlap Vulnerability

此种攻击对2.0.33内核有效，其实此攻击事实上并不是分片组装算法的问题，而是在在实现上出现了小的纰漏，在ip_glue中有：

if(len〉65535)
{
printk("Oversized IP packet from %s.\n", in_ntoa(qp-〉iph-〉saddr));
ip_statistics.IpReasmFails++;
ip_free(qp);
return NULL;
}

问题出现在printk上，如果对方一直用超大碎片（len〉65535），内核将会无节制的调用printk报警。而printk这种操作是相当耗费资源的，因此造成DOS。
在2.0.34版中改成了：
NETDEBUG(printk("Oversized IP packet from %s.\n", in_ntoa(qp-〉iph-〉saddr)));
而/include/net/sock.h中：
#if 1
#define NETDEBUG(x) do { } while (0)
#else
#define NETDEBUG(x) do { x; } while (0)
#endif
即只有在调试是才打开此功能，正常时不作任何事。

而后来的版本中加入了net_ratelimit（）函数，限制成最多5秒钟发出一次内核警告：
if (net_ratelimit())
printk(KERN_INFO
"Oversized IP packet from %d.%d.%d.%d.\n",
NIPQUAD(qp-〉iph-〉saddr));
这个问题不光在分片组装时用到，所有的网络部分的代码在打印调试信息时都要考虑大量日志造成拒绝服务的问题。目前的比较好且通用解决办法便是通过net_ratelimit（）函数。

（4）bugtraq id 543 Linux IPChains Fragment Overlap Vulnerability

ipchains在处理分片包，只处理第一个（offset==0&&MF=1）,因为只有这个包有TCP,UDP的头信息，其他后续的分片不作防火墙规则匹配，直接通过。假如防火墙之后的系统的IP分片组装类似如下做法：若有重叠，后来的包覆盖前面来的包。这样的话攻击者可以首先造一个可以通过防火墙规则的合法分片(如一个可访问的端口 )，再造一个与之重叠的分片，改掉前一个片中的信息（如一个不可访问的端口），这样最终的结果便是突破了防火墙的检测。

但此种方法只是理论上的，要依靠防火墙后面的主机的分片组装算法的具体实现。反正如果后面也是一台linux的话便无效，因为在处理重叠的时候linux不允许改变位置在自己之前的片的内容（详见上面的讨论）。
此方法在2.2.11以后的内核版本中更难实施，在ipchains处理分片时会检查分片的长度，如果过小则返回FW_BLOCK，即丢弃。

（5）其他

碎片攻击不光会攻击操作系统，由于许多网络工具，如防火墙，入侵检测系统（IDS）也在内部作了分片组装，如果处理不当，也同样会遭受攻击，如著名的checkpoint的防火墙FW-1某些版本（最新的已经改正了）便同样会受到碎片DOS攻击（可详见nsfocus第12期月刊《了解Check Point FW-1状态表》）.

碎片也可以用来逃避IDS检测，许多网络入侵检测系统的机理是单IP包检测，没有处理分片，即使是象ISS这样的公司也是在最新的5.0版本中才实现了组装功能，更不用说snort了，其IP组装插件经常造成core dump,因此大多数人都将此功能关闭了。

参考资料：

[1.] linux2.0.33,2.0.34,2.2.16,2.4.0-test3的源代码。
[2.] securityfocus的漏洞资料。
[3.] bugtraq上的一些邮件，数目众多，恕不一一列举