在上一篇文章《使用机器学习算法对流量分类的尝试——基于样本分类》（http://www.sdnlab.com/17324.html）中，我提供了一种使用朴素贝叶斯，借助流量的特征信息进行分类的思路和实践方法。然而那篇文章并没有提到如何找到我们用来抽取特征的包。
上一篇只是通过人工从wireshark抓包结果中找到关键的包。一方面，如果使用其他无GUI的工具或者抓包库直接抓包保存，而又不方便用图形界面找关键包该怎么办？另一方面，能够自动化的就应该自动化处理，节省人力成本。
本文通过查找应用的数据包交互特征实现关键包的发现，将会继续使用前文的例子和数据，根据实验目的，这次使用的算法是决策树。
本文的所有试验代码和数据都放在：https://github.com/Hochikong/ML-SDN/tree/master/TEST2
Decision Trees
决策树（Decision Trees）是一种简单、被广泛使用的分类算法，属于监督学习。通过提供样本进行训练，构建决策树，可以高效地对未知的数据进行分类。
优点
决策树有以下优点:
1.结构和二叉树类似，容易理解和人工分析。
如图，比如一个假想的女性择偶标准：
读者一定会觉得通过上面的图很容易理解这个择偶条件。
一棵决策树由根节点、分支节点和叶节点组成。根节点是决策树的起点，分支节点负责把数据划分到不同的子集中，叶节点储存结果、输出。
在上图中，“年龄”被称为根节点，其子节点和孙节点（绿色的）称为分支节点，橙色的为叶节点。
2.一次构建，反复使用，计算量不大于树的深度。
因为上图已经是一个成型的决策树，那么只要是针对同一个问题，就可以直接使用这个决策树对数据进行分类，以判断一个男性是否符合该女性的择偶标准。另外，如果读者使用自己实现的决策树算法，在python中还可以用shelve之类的工具把树保存起来，导入即可使用。
现在该女性王某在相亲，路人刘某（27岁，颜值中等，中等收入，非公务员）进了可视范围（别在意我的表达），通过上面的决策树，王某就可以判断刘某没门。以后再有可能的相亲对象，通过决策树就可以决定要不要见面。
3.计算简单，输出结果易于理解，对中间缺失值不敏感。
缺点
可能会出现过度匹配的问题，比如把单一特征（比如唯一ID）划作一个类别。
适用性
标称型或数值型均可
构建决策树
构建决策树的关键是属性划分，根据某一属性的不同划分构造分支节点，让节点中的数据信息熵尽可能低。本文中我们处理的是标称型数据，如果不是生成二叉树，则用属性的每一个划分建立分支；如果要求生成二叉树，就用属性划分的子集做测试，属于子集就一个分支，不属于的话又另一个分支。
但是关键是怎么划分，才能令分裂的各个子集中的元素处于同一类别？
这里用决策树的一种算法——ID3算法解释下这个过程：
一组尚未划分的数据是无序的，为了将无序的数据变得有序，可以采用多种方法来进行划分。ID3算法使用信息增益来进行划分。
1948年，克劳德·香农引入了信息熵的概念，定义为离散随机事件出现的概率（熵也即是“信息的期望值”），如果一个系统的熵越高，则系统越混乱：一堆牙签随意地撒在盘子里，盘子里的牙签是混乱、无序的，因而这个系统的熵高。熵越低则系统越稳定有序：把盘子里的牙签都收好，装在牙签筒里，牙签间紧密地“站”着，这个系统的熵就低。
信息增益为总的熵减去某个分类标准对应的熵，即信息的不确定性减少的程度，ID3算法选择信息增益（不确定性减少的程度大）最高的特征作为分类特征。
在划分数据之前，先对样本进行计算，计算整体的信息熵。下面通过具体例子计算一下：
上图中，样本被分为两类，豌豆甜与不甜，所以n=2（类别）。记豌豆为甜的概率为P(1),P(1)=2/4=1/2，记豌豆不甜的概率为P(2),P(2)=1/2。整体的熵可以通过此公式计算：
在Excel中编辑公式算出来熵为1:
S = -SUM(1/2*LOG(1/2,2),1/2*LOG(1/2,2)) = 1
现在，如果进行分类，可以通过颗粒或者颜色分类，也就是有两棵可能的决策树，如过用颗粒分类，可以分为这样：
如果是基于颜色分类：
从图像中很容易看出，基于颜色分类和没分过类其实是没区别的，因为样本0和1、2和3并不分别在同一个子集里而是单独作为一个节点，因此应该选择上面的基于颗粒分类的树。下面我们通过计算，解释为何选择基于颗粒进行分类。
先分别计算圆粒和黄色两种特征的熵，用上面计算样本的熵的公式计算：
用圆粒分类
在圆粒的分类中，有两个样本为圆，两个非圆，两个圆样本都属甜，两个非圆都不甜，因此应该这样计算：
A(圆) = -SUM(0,2/2*LOG(2/2,2)) = 0
B(非圆) = -SUM(2/2*LOG(2/2,2),0) = 0
因此选择用颗粒划分后的信息熵为每个子节点（圆粒和非圆粒）的信息熵所占比重的加权和：
E = 1/2*A + 1/2*B = 0
其实E的公式就是：
计算信息增益G的公式是：
因此选择基于颗粒分类的信息增益为G = (S-E) = 1
用颜色分类
在颜色的分类中，两个样本为黄色，两个样本非黄色，甜的豌豆一个黄色一个非黄，不甜的也一样，因此应该这样算：
C(黄) = -SUM(1/2*LOG(1/2,2),1/2*LOG(1/2,2)) = 1
D(非黄) = -SUM(1/2*LOG(1/2,2),1/2*LOG(1/2,2)) = 1
加权和：F = 1/2*C + 1/2*D = 1
信息增益为：G = (S-F) = 0
前面说过，ID3算法是根据信息增益大的特征进行划分，因此，ID3生成的决策树会是第一个树，基于颗粒进行划分的那棵树。
总结
一组数据可以通过计算算出整体的信息熵，然后根据可能的划分条件（比如颗粒和颜色）计算不同划分条件下的信息熵，然后用整体的信息熵减去特定条件下的信息熵即可求出对应的信息增益，ID3算法通过信息增益高的特征作为分类依据，这些特征会作为决策树的分支节点。
通过上面详细的例子，想必读者一定能充分理解决策树的原理了。
思路
既然上面都讲了那么多关于决策树原理的内容，接下来是该好好地思考下该怎么把它用在流量分类——挑选关键的包的用途上。
我们可以借助wireshark的图形界面分析下：
两图中，每一个应用的交互流程必然少不了TCP三次握手连接和四次分手断开，在libprotoident中这整个流程（创建连接到断开）称之为双向流。
注意：在第一幅图中，可以看到断开只有两个相关行（9和10），实际上是有点偏差的，实际上第七行就是断开的开始，读者可以找之前的数据exp.pcap查看7、8（python索引为6、7）行数据的TCP flag。
任何应用的数据传输都在双向流中，那么我们必须先找到双向流的开始（和终结）。因为在前文（http://www.sdnlab.com/17324.html）中，我们选取的关键包是紧接着TCP三次握手连接后的第一个数据传输包，那么关键就是如何找到一个双向流的开始，即三次握手。
假设在两个节点（A、B）间进行交互，B运行服务器，A运行客户端。当一组双向流开始（握手），第一个包的TCP flag为SYN，接下来的为ACK和SYN，第三个为ACK，第四个为PSH和ACK，用来做流量分类的关键是第四个包。
这就是双向流开始的特征。只要我们能找出开始特征，就能找到关键包的位置。具体知不知道结束在哪其实不算太重要，只要找到开始就能算出关键包在双向流的位置。
那么，怎么和决策树扯得上关系啊？
具体的操作思路就是：通过一个工具将pcap包的元数据抽取出来，数据含有编号、协议，flag和3个下文flag六个字段。
方向是个上下文相关的值，一般在三次握手中，把第一行的flag为SYN，第二行为SYN,ACK，第三行为ACK，第四行为PSH,ACK。至于其他比如DHCP、NBNS的协议就简单地把flag和下文flag设置为none（本实验的重点是如何找到前一篇文章中靠人手找的关键包，所以不考虑DHCP这些协议）
在本实验中，将会通过协议、flag、和下文三个flag进行判断分类，参见下面表格：
实际上，本表格是参照上面的wireshark截图的第二幅设置的分类，通过上面的表格的数据生成一棵决策树，将pcap元数据中每一行都进行归类。
上面这个表将会作为训练数据，使用pcap文件中每一行的flag和3个下文flag作为分类条件。
同样，我们需要对样本的字符串进行翻译，转为数字：
使用上面的表格把训练样本中的字符串翻译为对应的数字序列，几个flag所对应的值就是在scapy中查找flag返回的值，因此这里直接使用scapy中查的值而不是自己定义。
实践
我们需要从pcap中抽取所有行的元数据，即协议、四个flags，并按照上面的表格的字段顺序按行构建元数据。
抽取pcap元数据的工具为metaextra.py,抽取出来的数据按照前面说所的顺序（proto，flag，flag1，flag2，flag3）排列，下面使用工具抽取元数据：
root@test1:~/pcap/test2codes# python metaextra.py
WARNING: No route found for IPv6 destination :: (no default route?)
Enter the pcap file: exp.pcap
Enter the save path: meta.dat
root@test1:~/pcap/test2codes#
简单地看看这组元数据,数据有70组（exp.pcap文件有70行）；
{'res': [[10, 2L, 18L, 16L, 24L], [10, 18L, 16L, 24L, 16L]...}
上面的数据，10是协议，即TCP，而后面的带L的，是flag，第一行的[10, 2L, 18L, 16L, 24L]翻译为字符串就是[tcp,SYN,SYN/ACK,ACK,PSH/ACK]。
接着，我们通过读取Excel的xlsx文件，构建出训练数据、对应的标签和翻译字典并翻译，使用的工具是samtran.py（此samtran非前一篇文章的samtran）：
root@test1:~/pcap/test2codes# python samtran.py
Enter the xlsx file: work.xlsx
Enter the sample sheet number: 1
Enter the dictionary sheet number: 2
Enter the save path: sample.dat
root@test1:~/pcap/test2codes#
上面的工具要求输入样本所在的工作表和字典所在的工作表，所以编辑训练数据时需要把两部分数据分开不同的表存放。
查看下sample.dat,下面的是训练数据:
>>> b['res'][0]
[[10.0, 2.0, 18.0, 16.0, 24.0], [10.0, 16.0, 24.0, 16.0, 24.0], [10.0, 24.0, 16.0, 24.0, 16.0], [10.0, 16.0, 24.0, 16.0, 25.0], [10.0, 24.0, 16.0, 25.0, 16.0], [10.0, 16.0, 25.0, 16.0, 17.0], [10.0, 25.0, 16.0, 17.0, 16.0], [10.0, 16.0, 17.0, 16.0, 0.0], [10.0, 17.0, 16.0, 0.0, 0.0], [10.0, 16.0, 0.0, 0.0, 0.0], [20.0, 0.0, 0.0, 0.0, 0.0], [30.0, 0.0, 0.0, 0.0, 0.0]]
下面的是对应的标签：
>>> b['res'][1]
[u'TARGET', u'TCP OTHERS', u'TCP OTHERS';, u'TCP OTHERS', u'TCP OTHERS', u'TCP OTHERS', u'TCP OTHERS', u'TCP OTHERS', u'TCP OTHERS', u'TCP OTHERS', u'UDP OTHERS', u'NONSUPPORT']
当我们构建好数据后，就可以用diff.py找出用于对XMLRPC，SOAP和REST应用的流量进行分类的关键包位置：
root@test1:~/pcap/test2codes# python diff.py
Enter the train sample data path: sample.dat
Enter the sample metadata path: meta.dat
('The target packet location is lines: ', [4, 18, 34])
The decision tree pdf is tree.pdf
root@test1:~/pcap/test2codes#
可以看到这个工具输出了关键行，4，18和34，当然，这些数据是关键包在pcap文件中的真实编号，如果在python中使用还是要分别减一才能得到正确结果。
最后检查下分类出来的数据编号是否正确吧:
1.第4行:
2.第18行：
3.第34行:
可以看到我们的分类器成功地帮我们根据特征找到了用来进行流量分类的包
然后，检查下diff.py输出的决策树图解;
有兴趣的读者可以自己根据前面的excel表格计算下为何这棵树是这样的
思考和细节
OK，看了这么久，我们先整理下用于发现XMLRPC,SOAP和REST应用流量中的关键包的思路和相关考虑:
要点
通过wireshark的图形界面可以知道，在上一篇文章（http://www.sdnlab.com/17324.html）中用来作为分类依据的关键报文都是在三次握手后的第一个带PSH和ACK flag的报文。那么我们只要识别出三次握手，就可以推断出关键报文的位置。
使用的算法
基于熵的决策树。
用来量化子集纯度的常见方法有基尼不纯度和熵，默认情况下sklearn使用的是基尼不纯度，但是为了和前面介绍的ID3算法相呼应，因此在分类工具diff.py中使用了基于熵的树。
发现关键报文的整个流程
1.抽取目标pcap文件中的流量元数据（TCP flags）
2.使用特定的决策树，基于上下文定位三次握手的开始行
3.在三次握手的开始行加3即可算出关键报文的位置
下面我们通过分析代码，介绍下思路：
1.samtran.py
处理Excel的xlsx文件：
在这里我们只需要读取xlsx文件，所以程序导入xlrd库用来读取数据，在整个samtran.py中只有一个translate函数，作用是抽取数据兼翻译。尽管决策树可以基于字符串进行训练，但是sklearn必须使用数字作为训练数据，因此我们需要把字符串翻译为数字。
前面说到，训练数据和翻译字典要分表储存，因此，该函数要传入训练数据和字典的表格编号（从1开始）：
下面的代码用于抽取训练数据和标签，先获取样本数据的行数，去掉第一行的字段名，取第二行到结尾的数据。然后从每一行的最后一个位置拿出对应的标签，删掉标签，完成标签和训练数据的分割。对于翻译字典的构建，也采用类似的方式：
最后根据生成的字典把训练数据的字符串翻译为数字即可用shelve保存。
2.metaextra.py
抽取pcap元数据
我们需要借助scapy解析pcap。在这里我定义了三种传输层协议的数值，index用于抽取指定一行的3个下文flag：
下面的代码主要是针对每一行数据，如果传输层协议为TCP则先在临时数据中放置一个协议编号，然后放该行的flag，然后检测下面3行网包的传输协议是否为TCP，是的话则抽取相应行的TCP flag并追加到临时数据，如果不是TCP则把flag设为0；如果为UPD或者其他的传输协议，则在临时数据中放入相应的协议编号，后面的flag值全为0：
抽取出来的数据样例：
[10, 2L, 18L, 16L, 24L]
[20, 0, 0, 0, 0]
[30, 0, 0, 0, 0]
3.diff.py
这个程序读入训练数据和待分类数据，使用训练数据和标签训练决策树，创建一棵基于熵的树：
定义分类器函数，如果在分类中返回的是‘TARGET’标签，则返回‘one’，表示已经找到一行数据为三次握手的起点。
因为这一行是三次握手的起点，因此我们没必要对下面紧接着的三行进行分类了，所以使用while循环和一个外部索引，classifier函数每返回一次‘one’则在临时数据中放入一个索引加4的值代表关键包的位置，同时对索引加3，跳过下面3行的数据，在关键包下面的第四行继续进行分类以节省时间：
结语
本文作为《基于样本分类》的补充，先介绍了决策树的原理和构建方法，然后提出了上面的基于报文交互特征识别的关键报文发现技术，通过具体的代码做了实践，最后介绍了工具的细节。
笔者的这两篇文章主要针对的是流量的离线分析，因为流量也有可以挖掘的数据 ：），本实践为读者提供了一种发现关键报文的思路，如果读者有更加有趣的方法也不妨讨论下。
有人可能会问，为什么只用了决策树而不是其他算法？
我想说的是，决策树的生成和自己提供的训练数据有关，那么，当我们想灵活地拓展分类器的分类类别的时候，我们只要提供一份特定的训练样本即可：比如我现在不打算基于三次握手找关键包，而是通过比如协商包发现和特征进行关键包发现，我们也可以修改数据以生成相应的决策树。而分类器可以直接使用现成的（sklearn或者读者自己实现的通用分类器），而且如果使用自己实现的分类器，还可以通过pickle储存该决策树，只要训练一次就不用再训练了。这些理由就是我使用决策树的原因。
这里补充一篇关于香农和熵的文章供读者阅读：http://www.leiphone.com/news/201604/cMcVlHRnIyeVzykE.html?viewType=weixin
本人水平有限，如果有任何错误或疏漏之处，还请多多包涵。