基于数据流前端检测的快速协议识别

詹成,张伟

摘  要： 信息战都追求高速反应机动，对网络协议识别提出了高效快速的要求。基于深度包检测DPI的协议识别方法识别准确率高，但是由于要对所有数据包进行检测，计算量很大。基于端口号的协议识别方法速度快，但识别准确率低。提出一种新的基于数据流前端检测的协议识别方法并进行了系统实现，结合了基于端口方法的快速简单和基于DPI的准确性的优点。实验表明，这种综合快速协议识别方法识别准确率高，与基于DPI的方法相比，识别时间减少将近80%。

关键词： 协议识别； 正则表达式； 数据流前端检测； DPI

中图分类号： TN911.7?34； TP393           文献标识码： A                        文章编号： 1004?373X（2014）23?0058?04

Abstract： With the demand of quick response capability in the information war， the network protocol identification needs to be efficient and quick. The protocol identification method based on deep packet inspection （DPI） can achieve high accuracy， however it brings about mass calculation because of inspection of all packets. The protocol identification method based on port inspection is fast， but its accuracy is low. A new protocol identification method based on data?flow front?end detection is proposed and the system implementation way is given in this paper. The simple fast advantage of port?based method and the accuracy advantage of DPI method are combined in this method. The experimental results show that the new protocol identification method can achieve high accuracy， and decrease the identification time by nearly 80% in comparison with the DPI methods.

Keywords： protocol identification； regular expression； data?flow front?end detection； DPI

0  引  言

现在信息战都追求高速反应，高速机动，要求对协议进行高效快速识别，以尽快达到对协议识别的高准确性。传统的协议识别技术是端口识别[1]，这种识别具有较高的效率。但是随着网络协议的发展，原有的基于端口映射的协议识别技术局限性越来越明显。特别是在信息化军事战场上，这种识别方式的应用性几乎为零。一种基于深度报文检测（Deep Payload Inspection，DPI）的方法[2]，可以通过分析报文中的内容，根据预先定义的大量模式（域值、关键字或者正则表达式），对报文中的内容进行匹配，寻找匹配项，并确定报文所属的应用层协议，从而判定整个数据流所属的协议类型。虽然DPI方法可以达到很高的识别准确性，但是也存在以下问题：计算量大，需要对数据流的所有数据包内容进行检测，从而使得采用DPI方法困难且价格昂贵；用户的隐私保护，由于DPI需要检测数据包的全部负载，导致用户的隐私数据内容泄露。

本文创新地结合两种方法提出一种综合快速协议识别算法并进行了系统实现，通过对数据流的前端数据包进行深度包检测来进行协议识别，不仅具有基于端口方法快速执行的特点，同时又具有DPI方法识别准确性的优势。在真实数据流上的实验结果表明，相比较完全基于深度包检测的方法，该方法可以达到类似的识别精度，而且识别时间减少了将近80%。

1  系统采用的识别方法

在基于深度包检测的方法中，数据流的所有数据包都要进行模式匹配，但协议匹配并非总发生在数据流的末端。通过一个实验分析来探测到底在一段数据流中检测深度需要多大，即需要检测多少个数据包才能识别应用层协议。实验采用从互联网下载的真实数据流负载，其中包括典型协议HTTP，FTP，POP3，DHCP，SMTP，MSN，BitTorrent等协议的数据包。协议识别系统采用基于深度包检测的协议识别方法[3?4]，添加一些调试语句来收集以下信息：数据包的协议匹配在什么地方发生，即匹配发生在数据流的哪个数据包上。通过实验分析得到了如图1所示的结果。其中横轴表示协议匹配成功完成时匹配数据包在数据流中的位置，纵轴表示所有的数据流上发生协议匹配的次数。

<；E：＼LIHUI＼12月＼12.4＼现代电子技术201423＼Image＼03t1.tif>；

图1 数据包匹配深度图

从图1中可以看到大部分协议匹配的完成只需检测数据流的前几个数据包就可以实现。这是因为协议运行的初期通常需要进行控制报文的交换，而这些交换报文通常是这种协议特有的，可以成为进行协议识别的特征。这个实验提出了一种新的协议识别方法，即通过检测网络应用中数据流最有意义的数据包，通常为数据流的前N个数据包，就可以成功地完成协议识别，在第3节讨论[N]的具体取值。对数据流的前端数据包进行深度包检测，具有以下优点：达到接近于基于端口号方法的快速协议识别速度；尽量保护隐私数据。

2  系统实现

2.1  数据流前端数据包检测

在协议识别系统实现中，只对数据流的前[N]个数据包进行深度包检测。由于在网络传输层以上的数据传输都是以数据流为单位，因此在网络数据流的基础上进行协议识别。在本系统中采用<；源IP，目的IP，端口号>；所定义的一组报文来描述数据流。协议识别在<；源IP，目的IP，端口号>；三元组所定义的数据流上进行，一条数据流属于某个协议或者不属于某个协议，协议识别采用基于正则表达式的字符串匹配来进行深度包检测，在第3节中会详细介绍。

当新的数据流报文出现时，协议识别系统将产生新的流标志来标识此数据流，完成对此数据流数据包检测后，记录该数据流识别状态，如已识别或尚未识别。当发现新的数据包属于旧有数据流，则判断数据流的识别标识，若该数据流已识别，则识别系统跳过后续报文；若尚未识别，识别系统将该数据流送至匹配引擎匹配，根据匹配结果确定协议分类；尚不能分类的数据流则需保留协议识别状态，以便后续报文到来时继续进行识别。对于暂时不能识别的数据流，可以保存识别状态，即记录当前数据流识别过程进行状态转移时转移到了哪个状态；当再次遇到该数据流的数据包时，可以将保存的状态恢复，继续进行识别。采用这种方法不必对数据流重新进行识别，可以节省协议识别时间。

数据流协议识别算法如下所示，其中对每段数据流，只检测前[N]个数据包。

1. while （新的数据包p到达）

2.  if <；p（源IP），p（目的IP），p（端口号）>；未知

3.     Con_id =  为<；p（源IP），p（目的IP），p（端口号）>；分配的连接号

4.     if  （能识别Con_id）

5.       return 协议类型

6.     else

7.       保存Con_id协议识别最新状态

8.  else

9.    Con_id =  已保存的<；p（源IP），p（目的IP），p（端口号）>；连接号

10.   恢复最新识别状态

11.   if  （能识别Con_id）

12.      return 协议类型

13.   else

14.     保存Con_id协议识别最新状态

数据流匹配算法只扫描一次数据流，随着数据包的输入，可以在输入的任何位置完成识别，而无需重复扫描数据包；对未识别的数据流，从当前识别状态而不是初始状态继续进行匹配，提高了整个协议识别速度。

2.2  基于正则表达式的数据包检测

协议特征提取可以通过对协议的相关文档的研究，找出协议交互过程中特有的且必定出现的固定字段。若协议中只有惟一的固定字段，就选取该字段作为协议的特征串；若存在多个固定字段，则对协议的实际报文进行统计，选取出现频率最高的字段作为协议的特征串。

正则表达式[5]是采用某种模式去匹配一类字符串的公式，主要用于文本搜索、程序语言编译器等领域。作为一种形式语言，正则表达式定义了一套自己的描述方式：完整的正则表达式是由两种字符构成的字符模式，其中特殊字符称为“元字符”，其他的普通ASCII字符称为“文字”。描述一组可匹配的字符串时不用明确地列举出所有的确切形式，而是通过元字符描述子串或者单个字节的特征。在正则表达式中，既可以使用ASCII字符，也可以使用十六进制数。基于正则表达式的模式匹配就是将这一字符模式与所搜索的字符串进行匹配。正则表达式比固定字符串具有更强的表达能力和更好的灵活性，因此采用正则表达式代替固定字符串表示协议的特征。

例如对于文件传输协议FTP，通常服务器会传输字符串“220”表示服务器已准备好，接下来会传输一段数据，其中包含字符串“FTP”，在“220”和“FTP”之间会有一些ASCII字符串。根据这些特性，可以将协议FTP的协议特征用正则表达式“^220*FTP”来表示。

2.3  基于正则表达式的字符串匹配

字符串匹配问题，就是在一个文本[T=t1t2…tn]中找出某个特定模式串[p=p1p2…pn]的所有出现位置。其中[T]和[p]都是有限字母表[Σ]上的字符序列。匹配算法使用一个固定长度的窗口来搜索模式串，在窗口内检验模式是否匹配，然后从左向右不断地移动窗口，直到扫描完整个文本。利用自动机进行字符串匹配[6]只需对每个文本字符检查一次，并且检查每个文本字符的时间为常数。因此对长度为[n]的文本，建立自动机后匹配算法的时间为[Θ（n）。]

图2为一个简单的两状态自动机，其状态集Q={0，1}，开始状态q0=0，输入字母表[Σ]={a，b}。状态1是仅有的接受状态，有向边表示转移。如从状态1到状态0，标有b的有向边表示状态转移函数δ（1，b）=0。输入abaaa，此状态机的状态序列（包括初始状态）为<；0，1，0，1，0，1>；，表示它接受了这个输入；输入abbaa，状态序列是<；0，1，0，0，1，0>；，表示它拒绝了这个输入。

<；E：＼LIHUI＼12月＼12.4＼现代电子技术201423＼Image＼03t2.tif>；

图2 简单的两状态自动机

每个模式[P]都存在一个字符串匹配自动机，必须在预处理阶段，根据模式构造出相应的自动机后，才能利用它来搜寻文本字符串。给定输入文本T[1，2，…，n]，寻找长度为m的模式[P]的出现位置，可以用下面的基于自动机的匹配算法进行求解。对于长度为[m]的模式[p]的字符串匹配自动机来说，假定状态集Q为{0，1，…，m}，初始状态为0，惟一的接收态是状态m。

自动机字符串匹配算法 （T， δ， m）如下：

1. [n← ] lengthT

2. [q← 0]

3. [for i← 1 to n]

4.   [do q← δ[q，T（i）]]

5.      [if q=m]

6.         [then 字符串匹配 ]

由匹配算法的简单循环结构可以看出，对于一个长度为[n]的文本字符串，它的匹配时间为Θ（n）。这一匹配时间没有包括计算变迁函数[δ]所需要的预处理时间。下面将给出如何生成有限状态机的预处理过程。

2.4  基于正则表达式的有限自动机DFA构造

有限自动机是正则表达式的自然形式表示，它分为确定型有限自动机（DFA）和非确定型有限自动机（NFA）两种。NFA和DFA的主要区别是NFA对同一个字符串输入完全有可能有多种理解方式，而DFA则只有惟一的一种理解方式；即DFA对每个输入只产生一个状态转移，而NFA对每个输入可能产生多个状态转移，并且有空转化边ε。

传统的正则表达式匹配技术主要是基于非确定型有限自动机（NFA）实现的，其匹配速度较慢。随着表达式规模不断扩大，基于NFA 的匹配技术性能急剧下降，已经不能满足应用的需求，因此通常使用匹配速度更快的基于DFA 的匹配技术[7]。正则表达式转换成DFA的过程，首先通过Thompson构造算法[8]将正则表达式转换成NFA，然后采用子集构造法[9]将NFA编译成DFA，最后将DFA最小化。

Thompson算法根据确定的规则将正则表达式的NFA片段连接在一起，以构成与整个正则式对应的NFA，其主要方法是将各个片段根据规则进行连接。利用Thompson算法构造NFA时，只需扫描一次正则表达式，其构造复杂性为O（l），其中l为正则表达式的长度。给定NFA，我们可以采用子集构造算法来构造有限状态自动机DFA。

最小子集构造算法如下，假定NFA=（S，[Σ，]δ，S0，A）：

（1） 定义状态集合I的ε?闭包[ε?clousure（I）]，为状态集合I中的任何状态S经过任意多条ε弧而能到达的状态集合；

（2） 状态集合I的a弧转换（move（I，a））：定义为状态集合J，其中J是所有可以从I的某一状态经过一条a弧而到达的状态的全体；

（3） 定义Ia=ε-clousure（J）：其中I为某个状态集合，J为状态集合I的a弧转换move（I，a），也就是说，从某一个状态集合中的任何一个状态S，经过一条a弧再经过任意多条[ε]弧所能到达的状态的全体为Ia；

（4） 由初始结点出发，找出其闭包构成的集合ε?clousure（S0）作为初始集合作为矩阵的第一行第一列，集合Ia作为第一行第二列，有穷输入集[Σ]中的每一个输入字符的Ix依次对应一列。如果这些集合未出现过，则把这些集合作为下一个初始集合，即下一行的第一列，Ia作为第二列，依次类推得出一个状态转换矩阵。对矩阵中的所有状态子集重新命名后，即得出DFA的状态转换矩阵。

3  性能评价

通过系统实验来比较综合协议识别方法和基于深度包检测方法的性能差异，系统由C++语言实现，运行在Inter Core 2 Duo CPU @3.16 GHz的计算机上。实验采用互联网中下载的真实数据流数据，其中包括HTTP，FTP，POP3，DHCP，SMTP，MSN，BitTorrent等协议的数据包。采用完全深度包检测的协议识别结果作为协议识别正确的判断标准，实验结果为200次实验求平均的结果。

图3（a）给出了协议识别时间随着数据流前端检测参数N的变化图，可以看到随着N的增大，系统识别时间增大，这是由于检测参数N反映了系统进行数据包的检测深度，N越大，系统需检测的数据包越多。完全的深度包检测需要时间5.453 s，而当N=15时，只需要1.17 s的检测时间，识别时间减少了78%。

<；E：＼LIHUI＼12月＼12.4＼现代电子技术201423＼Image＼03t3.tif>；

图3 数据流前端检测参数N对系统性能的变化

图3（b）反映了系统协议识别正确性随着数据流前端检测参数N的变化，随着N的增大，协议识别正确率增大。当N>；14后，系统的协议识别正确率维持为100%。这是由于协议特征通常通过数据流前端的一些控制数据包就可以确定，而不必对全部负载信息进行检测。在系统中，通常设置N=15。与深度包检测的方法相比，不但可以达到相同的协议识别正确率，识别时间也减少了78%。

4   结  论

本文提出一种基于数据流前端检测的协议识别方法并进行了系统实现，结合了基于端口方法的快速简单和基于DPI的准确性的优点。系统实验表明此种方法识别准确率高，相比传统方法识别时间减少将近80%。

参考文献

[1] KARAGIANNIS T， BROIDO A， BROWNLEE N， et al. Is p2p dying or just hiding？ [C]// Proceedings of IEEE Globecom. [S.l.]： IEEE， 2004， 3： 1532?1538.

[2] RISSO F， MORANDI O， BALDI M， et al. Lightweight， Payload?based traffic classification： An experimental evaluation [C]// Proceedings of ICC08. [S.l.]： IEEE， 2008： 5869?5875.

[3] CROTTI M， DUSI M， GRINGOLI F， et al. Traffic classification through simple statistical fingerprinting [J]. ACM SIGCOMM CCR， 2007， 37（1）： 7?16.

[4] LI Zhu， YUAN Rui?xi， GUAN Xiao?hong. Accurate classification of the internet traffic based on the svm method [C]// Proceedings of ICC. [S.l.]： [s.n.]， 2007： 1373?1378.

[5] GREGER H， FELDMANN A， MAL M， et al. Dynamic application?layer protocol analysis for network intrusion detection [C]// Proceedings of USENIX Security Symposium. [S.l.]： [s.n.]， 2006： 1125?1130.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms [M]. 2 ed. [S.l.]： [s.n.]， 2002.

[7] 陈曙晖.基于内容分析的高速网络协议识别技术研究[D].长沙：国防科技大学，2007.

[8] THOMPSON K. Regular expression search algorithm. [J]. Communications of the ACM， 1968， 11（6）： 410?422.

[9] HOPCROFT J E. ULLMAN J D. Introduction to automata theory， languages，and computation.  second edition [M]. Boston. Addison?Wesley， 2002.

4   结  论

本文提出一种基于数据流前端检测的协议识别方法并进行了系统实现，结合了基于端口方法的快速简单和基于DPI的准确性的优点。系统实验表明此种方法识别准确率高，相比传统方法识别时间减少将近80%。

参考文献

[1] KARAGIANNIS T， BROIDO A， BROWNLEE N， et al. Is p2p dying or just hiding？ [C]// Proceedings of IEEE Globecom. [S.l.]： IEEE， 2004， 3： 1532?1538.

[2] RISSO F， MORANDI O， BALDI M， et al. Lightweight， Payload?based traffic classification： An experimental evaluation [C]// Proceedings of ICC08. [S.l.]： IEEE， 2008： 5869?5875.

[3] CROTTI M， DUSI M， GRINGOLI F， et al. Traffic classification through simple statistical fingerprinting [J]. ACM SIGCOMM CCR， 2007， 37（1）： 7?16.

[4] LI Zhu， YUAN Rui?xi， GUAN Xiao?hong. Accurate classification of the internet traffic based on the svm method [C]// Proceedings of ICC. [S.l.]： [s.n.]， 2007： 1373?1378.

[5] GREGER H， FELDMANN A， MAL M， et al. Dynamic application?layer protocol analysis for network intrusion detection [C]// Proceedings of USENIX Security Symposium. [S.l.]： [s.n.]， 2006： 1125?1130.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms [M]. 2 ed. [S.l.]： [s.n.]， 2002.

[7] 陈曙晖.基于内容分析的高速网络协议识别技术研究[D].长沙：国防科技大学，2007.

[8] THOMPSON K. Regular expression search algorithm. [J]. Communications of the ACM， 1968， 11（6）： 410?422.

[9] HOPCROFT J E. ULLMAN J D. Introduction to automata theory， languages，and computation.  second edition [M]. Boston. Addison?Wesley， 2002.

4   结  论

本文提出一种基于数据流前端检测的协议识别方法并进行了系统实现，结合了基于端口方法的快速简单和基于DPI的准确性的优点。系统实验表明此种方法识别准确率高，相比传统方法识别时间减少将近80%。

参考文献

[1] KARAGIANNIS T， BROIDO A， BROWNLEE N， et al. Is p2p dying or just hiding？ [C]// Proceedings of IEEE Globecom. [S.l.]： IEEE， 2004， 3： 1532?1538.

[2] RISSO F， MORANDI O， BALDI M， et al. Lightweight， Payload?based traffic classification： An experimental evaluation [C]// Proceedings of ICC08. [S.l.]： IEEE， 2008： 5869?5875.

[3] CROTTI M， DUSI M， GRINGOLI F， et al. Traffic classification through simple statistical fingerprinting [J]. ACM SIGCOMM CCR， 2007， 37（1）： 7?16.

[4] LI Zhu， YUAN Rui?xi， GUAN Xiao?hong. Accurate classification of the internet traffic based on the svm method [C]// Proceedings of ICC. [S.l.]： [s.n.]， 2007： 1373?1378.

[5] GREGER H， FELDMANN A， MAL M， et al. Dynamic application?layer protocol analysis for network intrusion detection [C]// Proceedings of USENIX Security Symposium. [S.l.]： [s.n.]， 2006： 1125?1130.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms [M]. 2 ed. [S.l.]： [s.n.]， 2002.

[7] 陈曙晖.基于内容分析的高速网络协议识别技术研究[D].长沙：国防科技大学，2007.

[8] THOMPSON K. Regular expression search algorithm. [J]. Communications of the ACM， 1968， 11（6）： 410?422.

[9] HOPCROFT J E. ULLMAN J D. Introduction to automata theory， languages，and computation.  second edition [M]. Boston. Addison?Wesley， 2002.