中国指挥与控制学会会刊 
随着互联网的快速发展,大量的私有协议和web服务层出不穷。为保证互联网安全,针对协议反向分析的协议逆向工程(protocol reverse engineering,PRE)[1]得到迅速发展。PRE方法大致分为未知协议实现的二进制分析[2]和未知协议流量的统计分析[3]。基于二进制解析的技术通常可以通过监控协议报文数据的具体处理过程来获得更复杂的目标协议规范,但在大多数网络对抗或管理场景中,为保护数据安全,通信终端没有访问协议二进制代码的权限。
基于网络跟踪的PRE过程包括报文聚类、标记化、关键字或特征提取以及未知协议格式的构建[4]。虽然有时聚类可以与其他进程一起执行,也可以单独执行,但一开始就将报文聚到不同的类,方便后续分析,特别是从不同的报文簇中提取格式[5]。因此,报文聚类,特别是针对协议格式的聚类[6],在基于网络跟踪的PRE中具有重要的作用。
本文提出一种基于格式匹配的未知协议报文聚类方法(unknown protocol packet clustering method, CUPFC),使用令牌格式距离(token format distance, TFD)和报文格式距离(message format distance, MFD)度量未知协议,通过设计TFD和MFD的形式化定义和计算方法,将增强巴科斯范式(Enhanced Barcos Paradigm, ABNF)规则应用到报文格式判定中,促进对未知协议报文格式特征的反向分析。为了提高聚类过程的自动化程度,本文使用无监督聚类模型指导参数的调整,减轻对人工赋值的依赖,并使用两个无监督聚类指标——轮廓系数和邓恩指数对模型进行优化。
1 PRE相关研究
面向报文格式是PRE中最常用的方法,通常采用格式标识、关键词或序列对齐方法来度量报文在格式方面的相似性,然后,结合聚类算法对报文格式聚类进行分类。
面向协议自动机状态的研究通常有类似的协议自动机逆向过程,包括报文分类、状态类型分类和状态机推断。文献[11]中,Comparetti等提出在进一步构建协议状态机之前,基于Jaccard系数测量报文特征的相似度,使用聚类中心(partitioning around medoids, PAM)算法对报文进行聚类。这些信息特征分别由针对报文的二进制分析和系统配置得到,并分别由K-S测试(柯尔莫可洛夫-斯米洛夫检验)检验特征的概率分布,从而确定的频率子序列表示。
ASAP算法通过构造由分隔符和n-gram派生的符号字母表,将报文有效载荷映射到向量,并使用矩阵分解来识别基本方向和坐标元组。通过贪婪算法将这些坐标元组重新映射为报文的语义表示,从而将元组连接到报文语义模板中。
综上所述,基于NW算法的聚类是最常用的未知协议报文分类方法,但仍存在依赖外部辅助、对格式考虑较少、聚类算法参数选择等不足。首先,通过人工定义属性和语义识别的方法在很大程度上依赖于人工参与以及系统或环境信息,例如,对格式区分符的识别,削弱了PRE在非合作条件下的能力。其次,在这些搜索中使用的NW算法通常基于令牌值的比较,很少考虑令牌格式的相似性,限制了报文格式区分的性能。最后,以往研究中使用的聚类算法通常存在参数选择问题,大大降低了PRE的自动化程度。基于以上讨论的面向报文格式和面向协议自动机状态的报文聚类,目前,没有理论证明自动机状态类型或报文语义与报文格式类型之间的映射关系,因此,基于自动机状态和面向语义模板的方法不适合PRE中的报文聚类。
本文从三个方面解决了上述问题。
(1)将token中的语法信息集成在一起,从报文内部内容中提取出格式属性相似度——TFD,从而减轻了外部依赖性。
(2)在TFD的基础上,使用MFD,从语法相似度的角度设计了一种新的NW算法——NWP,以测量报文距离,从而将报文的比较集中在格式上。
(3)引入Jaccard距离来指导参数的调优,通过基于密度的聚类算法分离未知协议报文,解决参数选择问题。
2 基于格式相似度的无监督聚类
本文的工作主要包括三个过程:令牌格式距离(TFD)和报文格式距离(MFD)的定义、测量以及基于MFD的无监督聚类,如图1所示。
首先,CUPFC方法提取混合未知协议包的有效载荷作为工作目标进行聚类。对于不进行任何分析的每条报文,内部数据根据ABNF被分成带有可能附加属性的字节令牌。基于令牌的属性集,CUPFC方法使用Jaccard系数来表示不同报文中令牌的相似性,即TFD。然后,在TFD的基础上,使用MFD从语法方面度量报文的相似性,并基于NW算法和LD算法(levenshtein distance,LD)设计了优化的报文令牌序列对齐算法。最后,以MFD矩阵作为输入,使用DBSCAN无监督聚类算法将报文按照不同的格式划分聚类。
2.1 令牌格式距离测量
根据网络通信协议的基本官方定义,本文将协议报文按字节划分为令牌,将协议的核心规则定义为基本单位。这些报文格式最小单元的核心规则在构成组合语法单元时,形成一系列值集,表示不同的值类型。对于来自未知协议的不同报文中的不同偏移量的值,可以将其识别为不同的语法元素,经过上下文语法推理,其属性将变得明确。
对于两个token m和n,它们的格式元素属性集为Am={a1,a2,…}和An={a1,a2,…}。如字符“P”被标记为{ALPHA, CHAR, OCTET, VCHAR},“/”被标记为{CHAR, OCTET, VCHAR}。通过这些标记可以测量它们的语法相似度。为了度量报文属性集的相似性,本文使用Jaccard系数和相应的Jaccard距离来表示相对语法属性的相似性和差异性。
A11={ai|ai∈Amandai∈An}
A10={ai|ai∈Amandai∉An}
A01={ai|ai∉Amandai∈An}
A00={ai|ai∉Amandai∉An}
因此,Jaccard系数Jaccard距离可用如下公式表示:
J(m,n)=
DJ(m,n)=1-J(m,n)=
通过Jaccard距离可以计算得到令牌m和n的TFD,从而对其语法差异进行度量,并以此来弥补相应的报文距离。
2.2 报文格式距离测量——NWP
参考自然语言处理中广泛使用的文本相似度度量LD算法,本文将迭代过程优化为:
(1)For j=0 or i=0, d[i][0]=i; d[0][j]=j;
(2)IF str1[i]==str2[j], then temp=0, else temp=1;
(3)D[i,j]=min{D[i-1,j-1]+TFD(ti,tj),D[i-1,j]+1,D[i,j-1]+1}
其中,ti和tj分别是每个报文令牌序列的第i和第j个令牌。
2.3 无监督聚类策略
针对未知报文格式距离的分布特征,采用基于密度的DBSCAN算法进行聚类,与基于分区或分层的聚类方法不同,DBSCAN的基本思想是寻找具有足够密度的元素或区域。该算法在寻找任何形状的聚类方面具有优势,只需元素是密度可达即可。当CUPFC处理未知协议报文的聚类问题时,这一优势非常重要,因为聚类的形状是不确定,而且元素的距离是在高维空间中计算的,而不是在大多数聚类算法中广泛使用的欧几里德空间。因此,本文选用轮廓系数和邓恩指数作为无监督聚类度量指标。
3 实验与分析
3.1 数据收集和预处理
表1 数据集1Tab.1 Dataset 1 |
| 报文标签 | 数量 |
|---|---|
| NBNS查询请求 | 98 994 |
| NTP头 | 84 439 |
| DNS | 59 097 |
| Skinny | 1 474 |
| PPTP | 771 |
| PPTP控制 | 421 |
| VXLAN | 32 |
| NBT会话报文 | 19 |
| NBNS查询响应 | 3 |
表2 数据集2Tab.2 Dataset 2 |
| 报文标签 | 数量 |
|---|---|
| DNS | 2 733 |
| SNMP | 58 |
| BOOTP | 53 |
| RADIUS | 11 |
数据集1中包含大量的DNS和NTP流量,表明网路中存在频繁的域名解析和时间同步活动。数据集2中DNS报文占比较多,其余类型的报文数量较少,因为大学网关拦截到的域名解析协议相对更多。
3.2 评估指标
为了衡量无监督聚类策略的性能,本文采用了最常用的指标:同质性和完备性。同质性表示每个簇只包含单个类的成员的紧密性,完备性表示给定类的所有成员分配给同一簇的数量,v测度是同质性和完备性的调和平均值,fmi定义为成对精度和召回率的几何平均值,以进行总体评价。
设G为消息集的基本真值标签,P为本文方法预测的标签,homogeneity(HOM)表示真实标签和预测标签的同质化程度,comleteness(COM)表示预测结果的可靠性:
HOM=1-
COM=1-
H(G|P)=- ·log
其中,H(G|P)为基础真标签集和预测标签集的条件熵,n为标签集的大小,g、p为基础真标签集和预测标签集中的每个标签号。fmi的计算公式如下:
fmi=
3.3 实验结果
消息格式聚类方法由令牌序列对齐和消息聚类两部分组成,本文将其与两种序列对齐NW算法(基于类型的NW和基于值的NW)和两种聚类算法——非加权对群法(Unweighted Pair Group Method with Arithmetic Mean,UPGMA)和PAM进行了比较。模型的分割度如表3所示。
表3 分割度Tab.3 segmentability |
| 方法 | HOM | COM | V | FMI | COV | |
|---|---|---|---|---|---|---|
| DBSCAN | 0.88 | 0.98 | 0.91 | 0.97 | 0.99 | |
| CUPFC | UPGMA | 0.88 | 0.93 | 0.87 | 0.96 | — |
| PAM | 0.82 | 0.69 | 0.66 | 0.82 | — | |
| DBSCAN | 0.87 | 0.98 | 0.91 | 0.97 | 0.99 | |
| v-NW | UPGMA | 0.86 | 0.74 | 0.70 | 0.83 | — |
| PAM | 0.79 | 0.66 | 0.65 | 0.83 | — | |
| DBSCAN | 0.39 | 0.93 | 0.42 | 0.84 | 0.99 | |
| t-NW | UPGMA | 0.69 | 0.88 | 0.72 | 0.92 | — |
| PAM | 0.89 | 0.53 | 0.58 | 0.72 | — |
在对比实验中,参数决策策略与本文使用的方法相似,最大限度地减少了人工干预的可能性。对于PAM,簇的数量由最优无监督度量sd来选择。UPGMA输出聚类结果的系统发生树高度也由最优sd决定,但在一个稳定的范围内,sd值不会影响系统发生树的高度。如果系统发生树的最大高度不大于2,则认为该子集中的消息具有高度相似性,并将其聚为一个类。从表3中可以看出,基于CUPFC方法的实验结果都优于其他组,只有少数值在v和fmi上非常接近。事实上,从语法的角度来看,MFD策略可以看作v-NW和t-NW之间的一种权衡,它们要么是细致的,要么是粗糙的。因此,CUPFC在测量来自未知协议的消息的语法距离方面表现出更强的适应性。
为了保证聚类的有效性,本文以MFD的平均值作为参考,对模型进行测试。图2显示了有监督度量和无监督度量曲线的相似性和本文方法的合理性。eps值为DBSCAN模型中的重要参数,与具体分布有关,代表了邻域的半径。eps为4.2时,模型性能达到最优,分割度为0.97。
4 结束语
本文开发了CUPFC方法,将来自未知协议的互联网消息区分为具有不同格式的类。CUPFC方法基于Needleman-Wunsch算法和Levenshtein距离的优化算法作为消息格式距离度量来定义消息令牌序列的格式相似性,在DBSCAN算法的基础上,引入无监督聚类策略,使用Silhouette系数和Dunn指数作为聚类评价指标,并结合参数选择策略,促进聚类过程的自动化。
通过与现有方法的比较,验证了CUPFC的优越性。对于同质性、完备性、v测度、覆盖率等度量指标,结合FMI进行检验,CUPFC方法在数据集上分别实现了平均0.8827、0.9808、0.9150、0.9724、0.9923的值。
ABNF规则作为一种广泛应用于协议格式开发的基本语法规则,在PRE中值得进一步研究和利用,如消息语法重构。理论上讲,本文中的令牌序列比较过程可以优化为提取消息之间相似的语法成分。将这一思想推广到多序列上的通用语法反转,具有相同格式的消息的语法结构有望反转。这些信息与本文的聚类结果吻合。