HashTable应用实例-流还原&碎片重组

发表于

0x00 前言

在网络数据传输中，可能由于MTU等因素造成数据流本身被分成多个包，变得碎片化，很多协议都有类似的情况，例如ip的碎片，tcp的流还原，以及coap的block传输等等。
碎片重组和流还原本质上都是将一段一段的数据，合并或者说还原成期望的样子，而在这个还原操作中，常见的数据结构就是HashTable，这里不讨论具体语言实现中的一些HashTable的情况，例如线程是否安全等等，仅仅从数据结构本身的性质，记录一下关于它的实际应用-CAPWAP碎片还原。整个hashtable代码本身仅仅是从一个IDS里头看到的，自身实现的，比较简单的hashtable，解析capwap顺手用到了。

HashTable本身的数据结构啥样这里就不提了，我觉得碎片重组和流还原本身比较相似，所以下文中仅仅介绍碎片重组。

0x01 碎片重组基本思路

首先忽略CAPWAP协议本身的特征和各种标志位以及操作码等等，概括的描述一下，一个碎片包，如果需要重组，需要拥有什么信息，以及如何重组
需要拥有的信息：

  1. 五元祖，源目的ip/端口/传输层协议
  2. 标志位，标示该报文是碎片包，以及是否是最后一个碎片包等等
  3. 偏移量，标示该数据包的载荷，在最后还原的数据中的偏移位置
  4. 碎片ID，也叫标示符，不同的协议可能叫法不太一样，总的来说就是协议栈提供的，需要保证这一批碎片中，这个值是相等的，以此来保证他们

理论上来说有这些信息，就可以进行组合或者还原了
重组的方式也很简单，识别出来这条流之后（识别方式可以通过源目的端口以及ip等），根据偏移进行组装就可以了

0x02 识别流的方式

这里简单提一下，识别流的方式。

理论上部分网卡（ixgbe）本身是有这种功能的，实现的具体方式我也不清楚，具体来说就是pfring这种数据包捕获的方式，在有驱动一类东西支持的情况下，可以自行设置并发数，在里头会自行将对应的流放置与不同的并发的队列中。
代码中实现流识别的方式也比较简单，通过源目的ip和端口就可以了，不过之前看IDS的代码发现一个比较有意思的事情是，它是给每个流计算了一个ID的，ID的计算方式，就是通过源目的ip和端口一类的信息，但是一个流，是很可能有数据交互的情况的，即源目的ip端口相反的情况，因此在该IDS中，它在计算这个流ID的时候，会自动将ip这个值本身比较大的哪一组ip和端口，放置在计算id逻辑的前面。简单用伪代码标示就是：

1
2
3
4
5
6
7
8
9
IP1;
PORT1;
IP2;
PORT2;

if IP1>IP2:
  flow_id = IP1+IP2+PORT1+PORT2
else:
  flow_id = IP2+IP1+PORT2+PORT1

这样可以保证不管是源到目的的数据包还是目的给源返回的数据包，计算出来的id都是一致的，就可以识别成一条流。

0x03 碎片重组&HashTable

将上面的信息进一步抽象，其实可以将数据分为两部分

  1. id
  2. 数据载荷，即需要组合还原出来的数据

这个情况，用hashtable处理就非常合适，简单来说就是通过id进行一些hash计算，得到一个在hashtable中的索引，而这个索引本身对应一段存储空间，用于存储碎片数据的空间，在流还原中，这部分空间就可以是一个链表，根据数据包中的偏移信息，来进行排序。注意，这里的链表，并不是用于处理hash冲突的链地址法中使用的链表。

0x03.1关于hash冲突

我这里使用的hashtable时自己实现了这个处理冲突的算法，因为默认的不太好使，其实java里头也有，但是大部分情况下默认的就够了。

这里导致冲突的原因主要就是，在往hashtable中添加数据计算索引的时候，计算到了同一个值，我之前写的hash函数比较简单，就是直接将flow id与hashtable的大小进行余数运算，果不其然就碰上了，之前同事说可以带上碎片ID进行hash计算，但是后来想了想还是没有使用这种方法，主要原因是，重复是正常现象，说明这个hash重复的数据包，就是来自这条流中的，那就是需要进行重组的。但是还有一种情况是，hash冲突后，这个包并不是属于冲突这个碎片集合所属的流中的，真的就是hash冲突了，那么这个时候，碎片id就碰上用场了，也就是说，在hashcompare函数中，进一步进行碎片id的对比，就可以比较好的处理这个问题了。

整体来看可以通过一张图描述（用processon画的，凑合看看吧）

index代表hashtable的索引，bucket即为上文中提到的，链地址法处理hash冲突的体现，而在这个实际应用中，为了存储并还原数据，因此使用了链表来进一步存储碎片。

0x04 总结

hashtable这个，以前写andorid和用java的时候，都有使用到，但是后来整杂活之后，就比较少使用这个数据结构了，或者说没有这么直接的使用它，相对高级一些的语言，例如java、python等，这类语言对它都进行了比较好的封装，我这回使用的是c的，需要自己实现hash函数、释放函数、以及处理hash冲突的hashCompare函数。这回不知道为啥，觉得hashtable这个玩意，很亲切。。。

哎，太菜了，还是要多学学，之前因为一些各种各样的原因，客户的pcap直到临近交付才给到我们，结果发现我们使用的流量处理程序无法解析其中出现的CAPWAP隧道协议，加了一个周末的班，调研了各种方案，甚至到了抓包驱动那一层，后来感觉自己写也就那么回事。。