做 libantixunlei 扯出来的无聊技术之二

这回是如何高效地判断出迅雷的FTP指令序列。
这里所说的FTP指令序列是指，一个FTP会话从连接开始，到开始下载文件前，发送给服务器的FTP指令的序列。另外，指令参数是不算入指令序列里面的。
一个典型的FTP指令序列就是：USER->PASS->SIZE->PASV->RETR。

在最早版本的GSSXI中，我采用的方法非常糟糕，每收到一个指令，就把这个指令用strcat函数加到一个用来保存指令序列的字符串去，并在每个指令之间以*区分。于是上面的指令序列在我的字符串里就是：USER*PASS*SIZE*PASV*RETR*
然后，每修改一次用来保存指令序列的字符串后，我就用strcmp函数将当前的指令序列字符串和预先定义好的迅雷的指令序列做比较。这样每收到一个指令都要进行一次字符串比较，这个效率显然是不怎么样的。

于是现在我就想出了一个高效的办法。
基本的思想是，建立一个单向链表，链表的节点依次保存指令序列的一个指令。为每个FTP会话创建一个指针，连接创建时这个指针指向链表头。
接下来，每接收到一个FTP指令，就把这个指令和当前会话指针指向的链表节点中的FTP指令做比较。如果指令相同，则指针指向下一个节点，并等待下一个指令；如果指令不相同，则可以判定这个会话不是由迅雷发起的会话。而最后，如果指针指到了链表尾，就说明这个会话所发送的指令序列和链表中的指令序列是一致的，于是就可以判定这个会话是由迅雷发起的了。接下来，就断开这个链接，想封IP的话就封IP，或者严重一点的，给迅雷发送脏数据吧。

虽然这样做已经可以达到比较高的效率了，但是迅雷的指令序列不止一个，这样就要同时维护几个链表。虽然说维护多个链表并不会对效率有多大影响，但是感觉不怎么方便的样子。同时为了进一步提高效率，我弄出了一个比较像二叉树的数据结构。好吧我不知道这个数据结构之前有没有用出现过，或者说已经出现过了，但是偶不知道这个数据结构叫做什么东西。
这个数据结构是这样的，首先其基本结构就是一棵二叉树。叶子节点保存一个FTP指令和一个标志，该标志用于确定当前会话是否是迅雷，有三种状态，分别是“是迅雷”和“不是迅雷”以及“未知”。
在会话建立时，还是和链表的情况相似，给每个会话分配一个指针，指向根节点。接着，在接收到FTP指令的时候，将接收到的指令和当前指针指向的叶子节点中保存的指令相比较。对比较结果的处理就和链表的数据结构有点不同了。如果指令相同，就把会话指针指向右边的孩子；如果指令不同，就把会话指针指向左边的孩子，并继续按照此规则，将当前的FTP指令和左孩子的FTP指令相比较，直到指令相符，或者会话指针指向的叶子节点的标志位为“是迅雷”或“不是迅雷”为止。
当会话指针指向的节点的标志位为“是迅雷”或者“不是迅雷”后，就可以确定这个会话是不是迅雷的会话了。

这样设计以后，创建一个FTP指令序列的二叉树就是，右孩子是当前叶子指令的下一条指令，左孩子是状态为“不是迅雷”的空指令，然后给最后一个右孩子加上一个右孩子，设置其标记为“是迅雷”。
接着，设计出几个指令序列的二叉树以后，只要把其中一颗树的根节点作为另一棵树的根节点的左子树，组合得到一棵新的树，然后再将这棵新的树作为另一棵树的根节点的左子树，以此类推，直到所有的树都组合成一棵树，这棵树就是我们需要的FTP指令序列树了。

实际上对于迅雷的指令序列来说，现在只有两套指令序列，而且非常相似。两套指令序列相比只是有一套指令序列比另一套指令序列多了一条指令，其他部分相同。对于这样的情况，我们可以先创建指令树比较多的那套指令序列的指令树，然后把那条多出来的指令的左孩子指向右孩子，就可以用这棵指令树判断两套指令序列了。


无图无真相，无图理解困难，过几天画了图再放上来。

相关文章：

1. 做 libantixunlei 扯出来的无聊技术之一
2. 自己制作sola的蓝天伞