一种基于字典树剪枝搜索的协议关键字识别方法

摘要

一种基于字典树剪枝搜索的协议关键字识别方法，首先获取需要识别的数据流，将数据流中数据存入循环队列buffer，对buffer中字符串记进行扫描，生成字典树中分支，在每次字典树中分支生成过程中，当满足剪枝条件时计算各个节点的剪枝阈值进行字典树剪枝，最后获取精炼比例PurifyRate，根据精炼比例PurifyRate得到关键字，完成关键字识别。本发明方法通过引入字典树剪枝算法，解决了使用传统字典树算法进行协议关键字识别时使用的存储空间过大的缺陷，具有提高了计算机的空间利用效率的优点，具有较好的使用价值。

权利要求

1.一种基于字典树剪枝搜索的协议关键字识别方法，其特征在于包括如下步骤：

(1)获取需要进行协议关键字识别的数据流，建立长度为24的循环队列buffer，将迭代器index定位在数据流第1位，建立变量DataCount记录扫描过的数据流长度，建立变量NodeNum记录字典树中节点数量，建立字典树root， 其中，DataCount的初值为0，NodeNum的初值为0；

(2)将以index为起点的数据流中的24位数据存入循环队列buffer，将buffer中存放的数据字符串记为A(a1a2...a24)，从a1开始扫描字符串，将当前扫描的字符记为ai，若字典树root中某个节点存放的字符与ai相同，则将当前节点的计数值count加1，并将该字符赋值给当前节点，然后继续扫描字符串A(a1a2...a24)，若字典树root中任何节点对应的字符都与ai不同，i＝1，2，3…24，则将aiai+1…a24中的字符分别作为24-i+1个节点，并连接在字符为ai-1的节点上，包括字符aj的节点的深度depth为j、计数值count为1，NodeNum＝NodeNum+(24-i+1)，j＝i，i+1，…24，其中，存储字符为a0的节点为根节点；

(3)index＝index+1，DataCount＝DataCount+1；

(4)判断变量NodeNum、DataCount，如果NodeNum>MaxNodeNum或者DataCount％CycleTime＝0，则转入步骤(5)，否则转入步骤(2)，直至DataCount+24等于数据流长度，转入步骤(7)；其中，符号％代表求模运算；

(5)计算得到深度为depth的节点的剪枝阈值MinCountList[depth]＝DataCount/(2^depth)*10；

(6)从字典树的根节点开始遍历字典树，将当前遍历到的节点temp的深度记为deptht、计数值记为countt，如果countt小于MinCountList[deptht]，则将temp节点、temp节点的所有子节点从字典树中删除，否则继续遍历字典树直至遍历完毕，并转入步骤(2)；

(7)用字符串列表StrList记录协议关键字，获取精炼比例PurifyRate，从根节点开始遍历字典树，将当前遍历到节点记为temp，节点temp的深度记为deptht、计数值记为countt，节点temp的直接父节点记为parent，节点parent深度记为depthp、计数值记为countp，若countt/countp

2.根据权利要求1所述的一种基于字典树剪枝搜索的协议关键字识别方法，其特征在于：所述的CycleTime为数据流长度的二十分之一到十分之一。

3.根据权利要求1或2所述的一种基于字典树剪枝搜索的协议关键字识别方法，其特征在于：所述的MaxNodeNum的取值为1000000。

4.根据权利要求1或2所述的一种基于字典树剪枝搜索的协议关键字识别方法，其特征在于：所述的精炼比例PurifyRate取值为一个大于0小于1的实数。

说明书

一种基于字典树剪枝搜索的协议关键字识别方法

技术领域

[0001] 本发明涉及一种关键字识别技术，特别是一种基于字典树剪枝搜索的协议关键字识别方法。

背景技术

[0002] 协议逆向工程是指在不依赖于协议描述的情况下，通过对协议实体的网络输入输出、系统行为和指令执行流程等信息进行监控和分析，提取协议语法、语义和工作流程。协议逆向分为格式逆向和状态机逆向两大类。在格式逆向中，对协议中关键字的识别和提取是一项基本而重要的工作。协议的关键字是指在协议传输单元，即报文中，由协议规范所规定的对通信的控制起关键作用的信息，一般会频繁地出现在通信数据流中，现有的对协议关键字进行识别的方法主要有以下几种：

[0003] (1)基于多序列比对的协议关键字识别

[0004] 在协议格式逆向的工作中，Beddoe首先将生物信息学中的多序列比对(Multiple Sequence Alignment，MSA)算法引入到工程中，并尝试获得报文的结构信息。在生物信息学中，通过对多个DNA序列进行比对，可以发现某序列片段的功能、结构和进化信息。具体地说，多序列比对针对给定的多个字符串，通过对每个字符串分别添加、删除字母或加入空格，使它们具有最大的相似性。与此类似，通过比对相同格式的不同报文实例，可以识别报文中的不变字段与可变字段，从而初步获得报文结构信息。Beddoe等人利用构造系统树的启发式方法引导多序列比对的执行，有效地降低了算法的时间复杂度，提高了执行的效率。该方法的主要缺点在于，该方法对于紧凑、简单的报文识别效果较好，对于复杂、冗余字段较多的报文，其效率和准确度较低。

[0005] (2)基于报文内容变化分布特征的协议关键字识别

[0006] Trifilo等人提出了基于报文内容变化分布特征的报文格式挖掘方案。具体来说，首先以字节为单位获得每次会话过程中，每个字节在多个报文中取值的频率分布。然后以字节为单位获得多次会话过程中，每个字节的频率分布。根据频率分布推断出哪几个字节属于关键字或固定字段，哪几个字节属于参数字段。然而，这种方法存在两点不足：第一，有的字段宽度是变化的，如果在某个位置出现“错位”的情况，则后面的统计信息是没有意义的；第二，判断字段变化范围的阈值是经验值，缺乏客观性。

[0007] (3)基于字典树的协议特征字挖掘

[0008] 字典树又称单词查找树、Trie树，是一种树形结构，也是一种哈希树的变种。它常常被应用于统计，排序和保存大量的字符串，其查找效率优于哈希树，所以经常被搜索引擎系统用于文本词频统计。字典树的根节点不包含字符，除根节点外每一个节点都只包含一个字符，从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串，每个节点的所有子节点包含的字符都不相同。

[0009] 对数据流进行协议特征字挖掘时，传统的方法是设定一个固定大小的滑动窗口，将数据流开头的单词作为字典树的第一个单词，然后将窗口依次向后移动直到数据的结尾，将数据中出现的可能的单词全部存储在字典树中。在字典树建立好后，再次扫描整个数据，统计字典树中的所有单词出现的频率，将出现频率相对大的单词，即协议特征字作为可能的关键字，在接下来的分析过程中将这些协议特征字作为分析目标，最终挖掘出真正的协议关键字。采用传统的字典树对协议关键字进行挖掘存在两个重要的缺陷。

[0010] (1)存储空间占用过大：对于常见的二进制通信数据流，若采用长度为n的滑动窗口进行协议特征字挖掘，可能的单词组合最多有2的n次方种。随着协议特征字长度的增加，用于存储字典树的空间呈指数增加。在滑动窗口的大小n较大时，计算机的存储空间无法完整地存储整棵字典树。

[0011] (2)协议特征字长度固定：由于滑动窗口的大小是固定的，因此挖掘出的协议特征字的长度显然也是固定的。而对于实际的通信协议来说，协议关键字的长度往往是不可知的，有时甚至是不固定的。这种情况造成通过传统的字典树所挖掘出的协议特征字仅仅是真正的协议关键字的一部分，进而影响分析的准确性。

发明内容

[0012] 本发明解决的技术问题是：克服现有技术的不足，提供了一种基于字典树剪枝搜索的协议关键字识别方法，解决了现有的采用传统字典树对协议关键字进行挖掘带来的存储空间占用过大、协议特征字长度固定影响分析准确性的问题，提高协议关键字识别的效率和适用性。

[0013] 本发明的技术解决方案是：一种基于字典树剪枝搜索的协议关键字识别方法，包括如下步骤：

[0014] (1)获取需要进行协议关键字识别的数据流，建立长度为24的循环队列buffer，将迭代器index定位在数据流第1位，建立变量DataCount记录扫描过的数据流长度，建立变量NodeNum记录字典树中节点数量，建立字典树root其中，DataCount的初值为0，NodeNum的初值为0；

[0015] (2)将以index为起点的数据流中的24位数据存入循环队列buffer，将buffer中存放的数据字符串记为A(a1a2...a24)，从a1开始扫描字符串，将当前扫描的字符记为ai，若字典树root中某个节点存放的字符与ai相同，则将当前节点的计数值count加1，并将该字符赋值给当前节点，然后继续扫描字符串A(a1a2...a24)，若字典树root中任何节点对应的字符都与ai不同，i＝1，2，3…24，则将aiai+1…a24中的字符分别作为24-i+1个节点，并连接在字符为ai-1的节点上，包括字符aj的节点的深度depth为j、计数值count为1，NodeNum＝NodeNum+(24-i+1)，j＝i，i+1，…24，其中，存储字符为a0的节点为根节点；

[0016] (3)index＝index+1，DataCount＝DataCount+1；

[0017] (4)判断变量NodeNum、DataCount，如果NodeNum＞MaxNodeNum或者DataCount％CycleTime＝0，则转入步骤(5)，否则转入步骤(2)，直至DataCount+24等于数据流长度，转入步骤(7)；其中，符号％代表求模运算；

[0018] (7)计算得到深度为depth的节点的剪枝阈值MinCountList[depth]＝DataCount/(2^depth)*10；

[0019] (8)从字典树的根节点开始遍历字典树，将当前遍历到的节点temp的深度记为deptht、计数值记为countt，如果countt小于MinCountList[deptht]，则将temp节点、temp节点的所有子节点从字典树中删除，否则继续遍历字典树直至遍历完毕，并转入步骤(2)；

[0020] (7)用字符串列表StrList记录协议关键字，获取精炼比例PurifyRate，从根节点开始遍历字典树，将当前遍历到节点记为temp，节点temp的深度记为deptht、计数值记为countt，节点temp的直接父节点记为parent，节点parent深度记为depthp、计数值记为countp，若countt/countp＜PurifyRate，则将根节点到节点parent的分支上的所有节点记录的字符组成字符串，加入到StrList中，完成关键字识别。

[0021] 所述的检测周期CycleTime为数据流长度的二十分之一到十分之一。

[0022] 所述的MaxNodeNum的取值为1000000。

[0023] 所述的精炼比例PurifyRate取值为一个大于0小于1的实数。

[0024] 本发明与现有技术相比的优点在于：

[0025] (1)本发明通过引入字典树剪枝算法，解决了使用传统字典树算法进行协议关键字识别时使用的存储空间过大的缺陷，具有提高了计算机的空间利用效率的优点；

[0026] (2)本发明通过使用边建树边剪枝策略，解决了使用传统字典树算法进行协议关键字识别时搜索速度偏慢的缺陷，将不相关的模式串从字典树中剔除出去，具有使后序的统计和分析工作的效率显著提高的优点。

[0027] (3)本发明通过使用“关键字提炼”策略，解决了从字典树中提取候选协议关键字的问题，具有较好的使用价值。

附图说明

[0028] 图1为本发明一种基于字典树剪枝搜索的协议关键字识别方法原理流程图；

[0029] 图2为本发明方法中字符串加入字典树原理示意图；

[0030] 图3为本发明方法中剪枝过程原理示意图；

[0031] 图4为本发明方法中协议关键字提取原理示意图。

具体实施方式

[0032] 本发明针对现有技术的不足，提供了一种基于字典树剪枝搜索的协议关键字识别方法，解决了现有的采用传统字典树对协议关键字进行挖掘带来的存储空间占用过大、协议特征字长度固定影响分析准确性的问题，提高协议关键字识别的效率和适用性，如图1为本发明一种基于字典树剪枝搜索的协议关键字识别方法原理流程图，本发明方法包括如下步骤：

[0033] (1)获取需要进行协议关键字识别的数据流，建立长度为24的循环队列buffer，将迭代器index定位在数据流第1位，建立变量DataCount记录扫描过的数据流长度，建立变量NodeNum记录字典树中节点数量，建立字典树root其中，DataCount的初值为0，NodeNum的初值为0，字典树是一个多叉树结构，本发明方法中字典树root除根节点外，其余节点均记录一个字符c、深度depth、计数值count。

[0034] (2)如图2所示为本发明方法中字符串加入字典树原理示意图，将以index为起点的数据流中的24位数据存入循环队列buffer，然后将循环队列buffer中数据存入到字典树。

[0035] 将循环队列buffer中数据存入字典树的过程如下：若当前buffer中存放的字符串为A(a1a2...a24)，从a1开始扫描字符串，当前扫描到的字符为ai：若字典树中某个子节点存放的字符与ai相同，则将该子节点的计数值count加1，并将该字符赋值给当前节点，继续进行扫描字符串A(a1a2...a24)；若字典树中子节点中任何节点存放的字符都与ai不同，i＝1，2，3…24，则将ai到a24中的字符建立一条树枝接在字典树节点之上，即树枝的每个节点记录字符aj(i＜＝j＜＝24)，depth为j，计数值为1，NodeNum＝NodeNum+(24-i+1)。

[0036] (3)index＝index+1，DataCount＝DataCount+1。

[0037] (4)判断变量NodeNum、DataCount，如果NodeNum＞MaxNodeNum或者DataCount％CycleTime＝0，则转入步骤(5)，否则转入步骤(2)，直至DataCount+24等于数据流长度，当DataCount+24等于数据流长度时，转入步骤(7)；其中，符号％代表求模运算，即a％b等于以a为被除数，b为除数，a除以b所得的余数；检测周期CycleTime根据数据流长度来进行设置，一般情况下取值范围为数据流长度的二十分之一到十分之一之间。在某些特殊应用场景下可以根据实际需要对CycleTime的取值进行适当调整；MaxNodeNum的取值根据不同计算机系统的内存大小自行进行调整，默认取值为1000000。

[0038] (9)如图3为本发明方法中剪枝过程原理示意图，计算深度为depth的节点的剪枝阈值，使用数组MinCountList[1:24]记录每一个深度的节点的下限阈值，深度为depth的节点的剪枝阈值MinCountList[depth]＝DataCount/(2^depth)*10，0＜depth＜24。

[0039] (10)从root树根开始遍历字典树。对于当前遍历到的节点temp，temp的深度为deptht，计数值为countt：如果countt小于MinCountList[deptht]，则将temp节点和temp节点的所有子节点从字典树中删除；否则，不进行任何操作，若字典树遍历完毕，转入步骤(2)。

[0040] (7)如图4所示为本发明方法中协议关键字提取原理示意图，对字典树进行精炼，并提取协议关键字：用字符串列表StrList记录协议关键字。精炼比例为PurifyRate，从树根开始遍历字典树root，对于当前遍历到的节点temp，temp的深度为deptht，计数值为countt；temp的直接父节点为parent，parent深度为depthp，parent的计数值为countp：若countt/countp＜PurifyRate,则将字典树root根节点到parent的分枝上的所有节点记录的字符组成字符串，加入到StrList中，停止遍历temp的子树，完成关键字识别，其中，精炼比例PurifyRate取值为一个大于0小于1的实数，默认值为1/4。PurifyRate的具体取值可根据实际情况进行适当调整。

[0041] 本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。