Protocol Informatics project分析

    Protocol Informatics project简称PI项目，由Marshall Beddoe在2004年启动并完成。实际上，这个项目并不算复杂，但是作者在一个月之内完成整个项目的设计和实现，甚至在一周内完成所有的编码工作，真的让人佩服！

    PI项目的目标是通过分析大量的网络流量，获取目标协议的结构信息。这里的协议可以是已知协议，也可以是未知协议。

    最近需要用到未知协议分析方面的知识，所以花了点时间看PI项目。PI项目的主体思想是通过类比生物学的一些算法，试图分析目标协议的结构信息。在生物学中，需要从DNS中寻找产生蛋白质的特定基因，而在网络中，需要从大量的网络数据流中找到具有特定含义的域。正是由于二者的这种相似性，所以我们就可以直接用生物学中的算法来解决网络协议的问题了。

算法思想：

    算法的整体思想是，首先收集大量的目标协议流量，经过处理，形成序列集。下面将对这些序列集进行分析。

1：使用局部序列比对算法计算序列间的距离矩阵。这里采用最常用的Smith Waterman算法，找出每两个序列之间的局部最佳比对，并计算它们之间的距离，形成距离矩阵。然后对这些距离矩阵进行处理，构造相对距离矩阵。

2：使用UPGMA算法，构造系统树(Phylogenetic trees)。之所以需要构造系统树，主要是因为直接进行多序列比对的时间复杂度太高(O(N*N))。因此需要通过启发式的方法引导多序列比对的执行。UPGMA算法实际上就是非加权成对群算术平均法。这是一种很常用的聚类分析方法，最早是用来解决分类问题的，通过UPGMA算法所产生的系统树可以说是物种树的简单体现。UPGMA算法比较简单，首先将距离最小的2个节点聚在一起，并形成一个最新的节点，然后计算新的节点之间的距离，如此反复，知道所有的节点都聚到一起，最终得到一个完整的系统树。

3：使用Progressive alignment算法，执行多序列比对。对每个Cluster，采用Progressive alignment引导完成多序列比对。这里的多序列比对算法采用Needleman Wunsch算法。Progressive alignment的执行规则如下：
        如果根节点root为空，则分别访问其左子树和右子树
        如果左子树非空，且右子树非空，则进行序列比对，并将比对结果存储到根节点root中
        将比对时的修改分别记录到左子树和右子树中

通过以上算法，可以将对序列时间复杂度降低，从而使协议域的划分具有可行性。

实现细节：

    PI项目的文档很少，也相关的介绍也是很模糊（至少我开始是没有看懂的），因此分析源码是唯一的选择。这里，我就简单介绍下源码的结构。算法思想已经介绍过了，所以看源码也比较方便。

Main.py：

dmx = distance.LocalAlignment(sequences)：使用Smith Waterman算法计算相对距离矩阵

phylo = phylogeny.UPGMA(sequences, dmx, minval=weight)：使用UPGMA算法完成系统树的构造并划分聚类(Cluster)

aligned = multialign.NeedlemanWunsch(cluster)：对每个Cluster使用progressive multiple alignment算法和Needleman Wunsch算法完成多序列比对

output.Ansi(seqs)：输出计算结果

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课