前言
 

    在当今高速大容量的Internet情形中，内容清静是网络清静的主要组成部分
。关于网络治理来说，最主要的就是识别和区分网络流量，通过协议识别可以对网络举行流量控制、网络计费、内容过滤、以及流量治理
。
 

    古板的协议识别接纳的是端口识别，这种识别能抵达较高的速率，可是现在大宗的应用层协议为了阻止识别，逃避防火墙的检查，不使用牢靠的端口举行通讯.这不但包括众多近年新泛起的P2P协议，并且包括了越来越多的古板协议，好比BitTorrent、eMule等P2P协议，其接纳动态端口举行通讯；Skype、QQ等协议则共用80端口
。越来越多诸云云类协议的爆发，使得端口识别已无能无力，因此近年来许多的研究事情都致力于开发新的要领来识别应用层协议
。
 

    DPI（Deep Packet Inspection，深度包检测）手艺是近年来泛起的一种协议识别手艺， DPI手艺在剖析包头的基础上，增添了对应用层的剖析，是一种基于应用层的流量检测和控制手艺，当IP数据包、TCP或UDP数据流经由基于DPI手艺的网络装备时，DPI引擎通过深入读取IP包载荷的内容来对OSI 7层协议中的应用层信息举行重组，从识别出IP包的应用层协议
。
 

DPI手艺
 

    古板的IP包流量识别和QoS控制手艺，仅对IP包头中的“5Tuples”,即“五元组”信息举行剖析，来确定目今流量的基本信息，古板IP路由器也正是通过这一系列信息来实现一定水平的流量识别和QoS包管的，但其仅仅剖析IP包的四层以下的内容，包括源地点、目的地点、源端口、目的端口以及协议类型，随着网上应用类型的一直富厚，仅通过第四层端口信息已经不可真正判断流量中的应用类型，更不可应对基于开放端口、随机端口甚至接纳加密方法举行传输的应用类型
。
 

    DPI手艺手艺在剖析包头的基础上，增添了对应用层的剖析，是一种基于应用层的流量检测和控制手艺，当IP数据包、TCP或UDP数据流经由基于DPI手艺的带宽治理系统时，该系统通过深入读取IP包载荷的内容来对OSI7层协议中的应用层信息举行重组，从而获得整个应用程序的内容，然后凭证系统界说的治理战略对流量举行整形操作
。
 

    差别的应用通；峤幽刹畋鸬男，而种种协议都有其特殊的指纹，这些指纹可能是特定的端口、特定的字符串或者特定的Bit序列
；谔卣髯值氖侗鹗忠，正是通过识别数据报文中的指纹信息来确定营业所承载的应用
。凭证详细检测方法的差别，基于特征字的识别手艺又可细分为牢靠特征位置匹配、变换特征位置匹配和状态特征字匹配三种分支手艺
。通过对指纹信息的升级，基于特征字的识别手艺可以利便的扩展到对新协议的检测
。
针对差别的识别手艺，DPI可以分为以下两大类：
 

    •使用特征字与掩码相团结的协议识别
 

    •使用正则表达式库的协议识别
 

使用特征字与掩码相团结的协议识别

    使用特征字符串举行协议识别，先统计协议现实交互历程中泛起频率高的字符作为匹配串，DPI引擎在线检查全报文以匹配多个串，往往适用于少量协议，效率一样平常，但其准确性有待提高，并且，关于一些变长填充的协议这种方法会显得无能为力
。
 

    使用特征字与掩码相团结的字符串匹配方法实现较量简朴，往往可以接纳硬件的方法来实现，例如某DPI厂商就接纳交流机的ACL芯片来实现基于特征字与掩码相团结的DPI识别引擎
。
 

使用正则表达式库的协议识别
 

    最近业界越来越趋向接纳正则表达式来举行匹配，实践批注，相关于古板的五元组识别和字符串识别，使用正则表达式对应用层协议举行识别的准确性有很大提高
。
 

    正则表达式(Regular Expression)形貌了一种字符串匹配的模式，可以用来检查一个串是否含有某种子串、将匹配的子串做替换或者从某个串中取出切合某个条件的子串等
。
 

    一些DPI厂商接纳只检测包头16字节或牢靠长度的特征值来实现DPI，可是我们以为这种模式不敷无邪，特殊是一些协议的特征值在包的尾部，或者特征值之间间杂着动态长度的随机填充字节，这些协议，用牢靠的DPI检测就无法识别
。
 

    经由对主流协议的研究，我们以为接纳正则表达式（regular expression）的方法举行协议特征值的匹配是效果最好的，由于基于正则表达式的DPI识别引擎从原理上来说可以识别绝大部分协议
。可是由于正则表达式的重大性，通例的正则表达式引擎相当消耗系统资源，效率较量低，故而直接接纳通用的正则表达式算法会严重的影响装备的性能
。因此关于接纳基于正则表达式的DPI引擎的厂商来说，怎样解决DPI引擎的性能问题，是一件很是主要的事情
。
 

    经由我们研发职员的起劲，我们开发了一套高性能的正则表达式算法，该算法接纳以空间换时间的方法大大的提高了正则表达式匹配的性能，凭证我们设计的算法的原理与我们现实测试的数据，该算法实现了性能与正则表达式的长度和数目无关，这也就代表装备的性能与装备所加载的协议特征码（现实上是一系列的正则表达式）的数目无关
。
 

    我们在此正则表达式算法的基础上实现了55世纪DPI算法，从性能上来说基本上与牢靠长度的DPI算法相差无几，可是却大大提高了其无邪性
。
 

DPI引擎

    我们接纳了基于正则表达式的DPI引擎，在最初的版本中，DPI引擎中的正则表达式算法接纳的是NFA算法，在最近的版本中，为了提高整个DPI引擎的性能，我们接纳DFA算法取代了NFA算法
。
 

NFA与DFA的区别
 

    NFA（Non-deterministic finite automaton，不确定有穷自念头），是基于表达式的（Regex-Directed）；而DFA（Deterministic finite automaton，确定的有穷自念头）是基于文本的（Text-Directed）
。
 

    举例来说，关于正则表达式 to(nite|knight|night)，NFA在匹配最最先两个字符（to）之后，剩下的三个组件（component）是 nite, knight 和 night，于是正则算法会依次实验这三个选择分支（每次实验一个）；而DFA在匹配最最先两个字符之后，会将剩下的三个选择拆分作字符，并行实验，也就是说，匹配 to 之后，先匹配 k 或者 n ，若是 k 不可匹配，则放弃knigth 所在的分支，再匹配 i ，再匹配 t 或 g ……这样继续下去，直到匹配竣事
。
 

    DFA 引擎在恣意时刻一定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，以是，NFA引擎必需纪录所有的可能路径（trace multiple possible routes through the NFA），NFA之以是能够提供Backtrack的功效，缘故原由就在这里
。从理论上说，若是我们不需要Backtrack，或者仅仅需要很小级别的Backtrack，完全可以从NFA结构出等价的DFA，再举行匹配，这样能大大提高速率——价钱是，DFA需要更多的空间
。
 

    NFA 由于不确定，以是限制比DFA要少，结构起来也较量利便一点，但匹配速率较慢.而DFA依次匹配并纪录匹配历程中每个字符的位置，因此每个字符最多被匹配一次，其匹配速率比NFA要高许多
。虽然要把正则表达式先转化为NFA，再把NFA转换为DFA，其转换时间相对要长，可是只需在匹配报文前对正则表达式编译一次，因此匹配报文的总体时间要比NFA的匹配引擎快许多
。
 

正则表达式特征库至DFA的转换
 

    我们接纳扩展的正则表达式对应用层协议的特征举行形貌，这个协议特征形貌的荟萃被称之为特征库
。
 

    特征库到DFA的转换历程需要通过以下办法：
 

正则表达式->NFA
 

    给出一个正则串的输入，获得一个NFA的输出
。被普遍接纳的是Thompson Algorithm，也就是所谓的子集算法
。该算法的实现和算术表达式的求值很是的类似，需要一个符号栈存放操作符，一个自念头栈存放天生的自念头
。算法竣事后，可以从自念头栈中获得一个最终的效果
。
 

    我们给出右线性文法：
 

    S 0S | 1S | 1A | 0B
    A 1C | 1
    B 0C | 0
    C 0C | 1C | 0 | 1
 

    右线性文法特点：终结符＋非终结符， 通过右线性文法结构NFA：
 

    1）  每个非终结符在图中对应一个结点，文法最先符号体现图中的初态结点，添加一终态结点 Z 
。
 

    2）  对形如 A cB 的爆发式，画一 A 到 C 的弧，标记为 c 
。
 

    3）  对形如 A c 的爆发式，画一 A 到 Z 的弧，标记为 c 
。

NFA->DFA

    一个 NFA 在读入符号串之后，并不确切地知道自念头的下一个状态是什么
。但可以一定的是，下一个状态一定处于某个状态集中
。无妨该状态集记做  {q1,q2,…qk} 
。而一个等价的DFA 读入同样的符号串一定处于某个确定的状态上
。
 

    这样，都是读入同样的w，  DFA  抵达某一个状态，而  NFA  抵达某一个状态集
。由  w  的恣意性，可将  NFA  的所有的状态集和  DFA  的状态逐一对应起来
。这种对应的条件就是能识别同样的输入串
。即  L(M1)=L(M2)  
。
 

    以是可以看出，我们要做的就是将 NFA 状态荟萃并为 DFA 中的状态
。着实质是将结点的跳转转化为结点集之间的跳转
。由初始结点 S 出发，找出其闭包组成的荟萃，在本例中， 由于不含ε路径，S的闭包荟萃就是 {S}
。然后由{S}出发，找出通过差别的路径所能抵达的荟萃
。
 

    为清晰起见，将选择图中一个荟萃跳转，重新标上颜色，和下表对应
。

最小化DFA
 

    有穷自念头分为确定的有穷自念头DFA和不确定的有穷自念头NFA两种
。
 

    界说1DFA ：一个确定的有穷自念头，M是一个五元组，M=( K,Σ, f , S , Z)，其中:K是一个有穷集,其元素称为状态；Σ是一个有穷字母表,其元素称为输入符号；S∈K,称为初态;ZÌ K，是终态集；f是转换函数，是K×Σ→K上的映射，f(ki,a)=kj,(ki∈K,kj∈K)体现状态ki，输入符为a时，转换为状态kj
。
 

    界说2无用状态：从自念头的最先状态出发,任何输入串也不可抵达的谁人状态;或者从这个状态没有通路抵达终态的状态
。
 

    界说3等价状态：若是说两个状态s 和t 是等价的, 应知足如下条件:(a) 一致性条件：s 和t 必需同时为终态或为非终态;(b) 伸张性条件：关于所有输入符号，状态s 和t 必需转换到等价的状态里
。
 

    一个DFAM可以通过消除无用状态和合并等价状态而转化为一个最小化的与之等价的DFAM’
。该历程称为DFA的最小化
。最小化的头脑是在不改变 DFA 识别的语言的条件下，合并响应的结点，使合并后的 DFA 与合并前的 DFA 等效，而结点数目镌汰
。
 

    但在实现上，接纳是从合到分的要领
。先从最精简的结构出发，即，整个系突页窘个荟萃，所有的终态结点并为一个结点，所有的非综态结点合并为一个结点 
。
 

    然后看这种划分是否可行，如不可行，再剖析出更多的荟萃
。而合并可行的依据就是荟萃中的每个元素通过统一条弧抵达统一个目的荟萃
。 

    如上图，首先将所有的非综态结点合并为 I0 ，
。将综态结点合并为 I1 
。划分考察两个荟萃
。关于 I0 ，通过 0 弧，有如下跳转： S0 S1 ， S2 S1 ， S1 S3 
。而 S1 ∈ I0 ， S3 ∈ I1 ，据此， S1 和 S0 、 S2 要脱离位于差别荟萃
。
 

    现假定 I0={ S0 ,S2} ， I1={ S3 ,S4} ， I2 ＝ { S1 } 
？疾 I0 ，同样是通过 1 弧，则有如下跳转：
S0 S2 、 S2 S4 ，而 S2 ∈I 0 ,S4∈I 1 
。故， S2 与 S4 脱离
？梢钥闯，只要发明一条弧不知足上述条件，就可以将其疏散
。并非要考察完每条弧
。
 

    再来考察 I1 ，通过 0 弧可得： S3 S3 ∈ I1 ， S4 S3 ∈ I1 
。通过 1 弧可得： S3 S4 ∈ I1 ， S3 S4 ∈ I1 
。显然， I1 不可再分
。
 

    云云重复，直到每个荟萃 Ii ( I=0,1,…) 均不可再分为止
。
 

最小化后的状态转换图如下：

 

数据包匹配模式

单包匹配方法
 

    当一个会话的每个报文抵达时都举行DPI引擎匹配，直到匹配乐成或者抵达每个会话的最大匹配包数（特征值基本上都泛起在一个会话的最初几个包中，后续的包中的特征不显着，甚至会导致协议的误判），则后续的报文不再举行匹配
。
 

    匹配乐成的会话会被打上协议标签，未匹配乐成的会话则被打上Others的标签
。
 

    单报文匹配方法匹配速率快，并且准确性高，基本不保存误判
。
 

有选择的多包匹配方法
 

    当DPI引擎发明某个报文切合一定的特征，则自动进入多包匹配方法，这种模式在针对类HTTP协议会很有资助，DPI引擎会匹配某个会话的多个报文，举行更准确的协议识别
。

    这两种数据包匹配手艺划分适用于差别类型的协议，相互之间无法替换，只有综合的运用这两大手艺，才华有用的无邪的识别网络上的种种应用，从而实现有用的控制
。

DFA匹配方法
 

    在DFA下有两种匹配扫描算法：
 

    One-Pass Scan算法（单遍扫描算法）
 

    Repeated Scan算法（多遍扫描算法）
 

    One-Pass算法只扫描一次，从一个位置最先扫描，若是有匹配，则竣事搜索，返回效果，直至扫描竣事；Repeated Scan算法从一个位置最先扫描，若是没有匹配，则从下一个位置重新最先扫描，匹配历程中，需要对输入举行重复搜索
。
 

    我们首先接纳One-Pass Scan算法对有Leading标记的特征值举行匹配，若匹配乐成则竣事匹配，若匹配不乐成，则用Repeated Scan对非Leading的特征值举行匹配
。
 

综述
 

    通过DPI对网络数据的快速识别与分类，不但为用户提高效劳质量(QoS)、分层效劳等提供手艺支持，也可以为网络数据上的内容羁系(如恶意代码识别、病毒防御)提供手艺包管
。
 

    深层包检测DPI手艺易于明确、升级利便、维护简朴，是现在运用最有用的流量识别要领
。现在，产品支持600多种协媾和应用的自动识别，涵盖了P2P、IM（即时通讯）、视频/流媒体、VoIP协议、网络游戏、炒股软件、企业内部焦点应用等应用和协议，基本笼罩了现在主流的网络协媾和应用类型，可为用户提供周全的、有用的协议支持
。
 

    接纳DPI手艺的优点包括：准确性高、结实性好、具有分类功效等
。准确性高是由于该要领执行准确特征匹配，因此少少保存误判问题
。结实性好是由于可以处置惩罚数据包丧失、重组等，因此能顺应现在重大的网络应用
。具有分类功效是由于深层数据包检测手艺可以依据差别应用的载荷特征来准确分类各网络应用，因此可以为实验流量羁系战略提供准确的信息
。