基于局部序列比对的漏洞挖掘技术研究

单路超，王建章，许德森，李东垣，赵 鹏，王国相，褚腾飞

(1.北京邮电大学, 北京 100876; 2.中华通信系统有限责任公司，北京 100070)

基于局部序列比对的漏洞挖掘技术研究

单路超1，王建章2，许德森2，李东垣2，赵 鹏2，王国相1，褚腾飞1

(1.北京邮电大学, 北京 100876; 2.中华通信系统有限责任公司，北京 100070)

针对网络协议漏洞挖掘系统在网络协议格式分析过程中使用全局序列比对技术效率不高的问题，结合网络漏洞挖掘背景，对序列比对技术进行深入分析，提出了一种更为有效的基于局部序列比对算法的Fuzzing漏洞挖掘新方法。在获取网络协议格式分析的过程中，提高漏洞挖掘效率。仿真结果表明，该方法较全局序列比对方法在执行效率上具有较为明显的优势。

漏洞挖掘；Fuzzing；局部序列比对；算法

0 引言

随着网络协议的发展，在网络应用中，网络漏洞会出现在系统的软件、硬件或协议中。这种漏洞的出现会给用户带来巨大的损失，因此漏洞挖掘被广泛应用在网络系统中。漏洞挖掘技术主要包括手动测试、Fuzzing算法分析[1]、静态分析、比较分析和运行时分析技术。其中，Fuzzing算法由于其优良的性能而被广泛应用在分布式网络中。在对数据进行检查时，运用的主要技术便是序列比对技术。序列比对，即按照实际需求，对某两个序列的相似性进行考察，具有非常大的现实意义[2]。根据比对范围，可以将序列比对划分为全局比对和局部比对。现在的漏洞挖掘系统中大量运用全局序列比对技术来进行数据检查。

Smith和Waterman利用动态规划思想，将Needleman—Wunsch算法进行改进，提出了Smith—Wateman算法[3]，两条序列中，整体的相似性往往都不是很大，可能只在某些局部区域有相似性，因此局部序列比对要比全局序列比对效率更高。

本文在Fuzzing网络漏洞挖掘技术的常用框架基础上，基于已有技术和整体框架，将部分序列比对算法应用于漏洞挖掘中的报文协议格式分析过程，最后针对本文提出的新型网络漏洞挖掘系统，完成实验环境的搭建和系统的配置，对改进后的网络漏洞挖掘系统性能进行对比测试。

图1 Fuzzing工作流程图

1 网络漏洞与Fuzzing技术

本文主要研究的漏洞挖掘中的模糊测试技术(Fuzzing)属于灰盒测试技术，通过向测试目标程序发送大量的半有效数据并观测输出结果，来发现目标系统中存在的漏洞[4]。

在利用Fuzzing技术进行漏洞挖掘[5]时，首先确定测试对象，产生非预期数据构造测试用例，启动模糊测试。然后对程序中出现的异常和错误进行检测和分析。最后对于检测出来的错误或异常，确定漏洞利用的可能性。Fuzzing的工作流程如图1所示。

2 网络协议部分分式漏洞挖掘技术的原理

通过构造网络协议漏洞挖掘测试器，经过搭建系统、配置环境、构造测试用例、生成请求等过程，完成会话控制脚本。首先对网络进行协议分析，构造测试用例保存在requests中，编写会话控制脚本，最后开始Fuzzing测试。

在实际网络协议漏洞挖掘[6]过程中，对网络协议格式进行解析是非常重要的一个环节。基于这种思想，本文对传统的模糊测试漏洞挖掘器进行改进，改进后的模糊测试漏洞挖掘器结构如图2所示。

图2 改进后的漏洞挖掘器结构图

目前应用的网络协议格式分析方法主要有两种：基于轨迹的分析方法和基于数据流的分析方法。基于轨迹的分析方法主要是通过动态污点分析技术对报文的解析过程进行跟踪。

本文主要对基于数据流的分析方法进行研究和改进。基于数据流的网络协议分析方法主要通过对测试对象发送和接收数据包的属性进行测试，得到网络协议信息并构造测试用例。本文中的网络协议格式分析过程包括4个子过程：采集数据流、初步处理、数据报文分类、协议格式分析。

在进行网络协议格式解析之前，先获取大量数据流，对数据流进行初步处理，获得初始报文序列。然后利用匹配规则将得到的序列按照相似性进行分组，用于格式分析。最后，通过改进后的局部序列比对技术，对报文格式进行分析。其中对网络数据流进行初步处理是网络协议分析的重要前提。数据报文分类过程是整个网络协议分析过程的第二个关键步骤，它分为3个子过程：报文分析、报文聚类、分类报文小组。网络协议格式分析的最后一个环节是网络协议格式获取，前面的几个步骤已经将输入的网络数据流分成不同的报文小组，通过对接收到的报文进行准确分类以及对比分析，最终可以得到报文的协议格式。在网络协议获取过程中，利用序列比对算法将数据报文对齐，对报文中含有的关键信息进行识别和分析，传递给Sulley框架，从而构造出测试用例，完成报文协议格式解析。

在网络协议漏洞挖掘系统中，局部序列比对算法可以十分精确地找到序列间的最大匹配子序列，这是全局比对算法无法做到的。因此，本文在已有的网络协议分析基础上，提出一种使用局部序列比对算法的网络协议格式获取过程，提高序列比对效率，从而加快网络协议格式的获取速度。

全局序列比对着眼于两个序列全长的最优比对，而局部序列比对则对序列之间的某个局部片段进行检测和比对。本文提出的改进型网络协议漏洞挖掘技术将Smith-Waterman动态规划算法[7]引入到网络协议格式分析过程中，并对改进后的漏洞挖掘系统性能进行研究和分析。

Smith-Waterman算法的主要思想为：对于给定的两个序列M=m1m2m3…mn和N=n1n2n3…nm，设序列M和序列N的相似度用之前设计好的计分函数σ(m,n)来表示，对插入、删除等操作赋予不同的分值[8]。对打分矩阵进行初始化，使矩阵首行和首列元素为0，即：

G(i,0)=G(0,j)=0

对于任意一个输入序列，都可以表示成k×1矩阵的形式。在进行插入或删除空格时，不能出现全为空格的一列。如果将对比之后的序列中的空格删去，则能恢复成原序列。

对于两个序列中的字母x、y，设字母取值于集合Z，在漏洞挖掘系统中，Z可以设置为A～Z字母集合。设计一个计分函数σ(x,y)，用来表示两个序列对比过程的得分。

根据设计好的计分函数，通过递归方法得到每次对比的分数，存于得分矩阵G的相应位置上，初始化和计算得分矩阵的过程可以用如下等式表示：

在上述计算得分矩阵G的等式中，(1)表示初始化过程；(2)表示元素替换所带入的计分函数数值，此时指针移动方向为指向右下方；(3)表示插入空格所对应的计分结果，此时指针移动方向为向下；(4)表示删除空格所对应的计分结果，此时指针方向为向右。在进行序列比对时，将要比对的序列M和N写在矩阵的两侧，根据设计好的计分函数，将序列M和N中的元素依次相互比较，将得分结果写在打分矩阵G对应的位置上，某个位置的得分取元素替换、插入、删除3种操作中的分值最大者，即按照左、上、左上3个来源方向结合计分函数σ(x,y)对同一个位置进行打分,分数最大值即为这个位置的得分。假设长度为i的序列，其插入损失为Wi，对变量1≤x≤|M|、1≤y≤|N|，打分矩阵的计分过程可以用如下公式表示：

Gi,j=max{Gi-1,j-1+σ(mi,nj)，max{Gi-x,j-Wx}，max{Gi,j-y-Wy}，0}

因为局部序列比对只是对两个完整序列的局部区域进行比较，因此在打分过程中，将负数记为0不会影响最后比对结果。

打分过程完成后，开始进行回溯过程，寻找相似子序列。同样因为局部序列没有对两个序列中的全部内容进行对比，因此回溯过程不需要从打分矩阵的最右下角处开始，只需要从得分最高的单元格开始即可。

回溯过程规则如下：

(1)从打分矩阵中的最高分单元格开始回溯，此处即为两个比对序列中的相似片段末端。

(2)回溯方向有3个：上、左上、左。回溯到这3个方向对应的下一个单元格中最大分数的位置。如果出现分数一样的情况，左上的优先级最高。

(3)重复执行(2)，直至无法找到下一个不为0的向上路径。此时，按照回溯路径写出的序列即为M、N的最大相似子序列。

图3 Smith-Waterman算法流程图

图3为Smith-Waterman算法的流程图[9]。

Smith-Waterman算法在填充打分矩阵时，先将第一行和第一列元素置为0，并且用0代替负分。在进行回溯时，从右下角最大正分值处开始，寻找打分矩阵中每个正分值处的返回指针，直至无法找到下一个不为0的向上路径为止，如图4所示。回溯完成后，根据回溯路径即可得到最优解。比如输入的两个序列为：ABCDEDC、EBDAEDB时，按照上述算法得到的比对结果为:BCD_ED;B_DAED。

图4 回溯示意图

3 算法的仿真和分析

为了验证在网络协议漏洞挖掘系统中采用局部序列对比技术比全局序列对比技术性能更好，本文在两台PC上搭建实验环境，一台提供服务器端和客户端，另一台与之进行通信交互。两台实验PC连接如图5所示。PC1又分为主机和虚拟机两部分，分别负责构造测试用例和系统服务器部分功能。PC2主要负责产生网络协议解析模块需要的网络数据流。实验环境搭建好后，将PC1与PC2进行正常交互，捕捉网络数据包，然后进行网络协议格式解析，构造测试用例并完成会话脚本。接着启动PC1中的虚拟机部分，进行相应的配置，开始模糊测试。本文设计的整个实验系统应用在网络协议FTP测试中，选用WarFTP服务器为测试对象，通过测量协议格式分析中进行序列对比的测试样本长度及系统运行时间，可以得到改进后的网络协议漏洞挖掘系统与传统漏洞挖掘系统性能对比结果。

图5 PC连接图

本文以输入序列程序运行时间作为判断网络协议漏洞挖掘系统性能的标准，对于输入的固定长度报文序列，分别使用本文对比方法和传统对比方法分析报文信息并构造测试用例，完成模糊测试。对于固定长度的相同报文序列，经过不同序列比对方式会导致整个漏洞挖掘系统的程序运行时间不同，对比结果如图6所示。

图6 对比结果图

由图6可以看出，本文提出的改进型网络协议漏洞挖掘系统运行效率比传统漏洞挖掘系统快，有效性和实用性更高。

4 结束语

本文介绍了现有网络协议漏洞挖掘技术的工作流程及模块结构，并对模糊测试的工作模式进行阐述。在此基础上，对网络协议漏洞挖掘过程中的网络协议格式解析进行优化，结合局部序列对比技术，提高了整个网络协议漏洞挖掘系统的工作效率，最后对改进的漏洞挖掘系统设计测试实验，验证了本文所提新型漏洞挖掘方法在执行效率上与传统漏洞挖掘方法相比有一定的提高。

[1] 史记, 曾昭龙, 杨从保,等. Fuzzing测试技术综述[J].信息网络安全, 2014(3):87-91.

[2] 王樱,李锡辉.多序列比对算法综述[J].中国新通信, 2014(5):92-93.

[3] LEE S T, LIN C Y, CHE L H. GPU-based cloud service for Smith-Waterman algorithm using frequency distance filtration scheme[J]. BioMed Research International, 2013, 2013(1):721738.

[4] 刘大光.基于模糊测试的网络协议自动化漏洞挖掘工具设计与实现[D]. 北京：北京大学, 2014.

[5] 裘志庆, 宦飞. 基于网络爬虫和Fuzzing的漏洞挖掘检测工具[J]. 微型电脑应用, 2016, 32(3):73-76.

[6] 潘道欣, 王轶骏, 薛质.基于网络协议逆向分析的远程控制木马漏洞挖掘[J]. 计算机工程, 2016, 42(2):146-150.

[7] LIU Y, HUANG W, JOHNSON J, et al. GPU accelerated Smith-Waterman[J]. Lecture Notes in Computer Science, 2006, 3994:188-195.

[8] GAO Y, HENDERSON M . Speeding up pairwise sequence alignments: a scoring scheme reweighting based approach[C]. Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering. Washington DC: IEEE Computer Society, 2007:1194-1198.

[9] IBRAHIM A, ELSIMARY H, ALJUMAH A. Novel reconfigurable hardware accelerator for protein sequence alignment using Smith-Waterman algorithm[J]. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences, 2016, 99(3):683-690.

[10] Zhang Saidan, Zhang Luyong. Vulnerability mining for network protocols based on fuzzing[C]. Systems and Informatics (ICSAI), 2014 2nd IEEE International Conference,2014:644-648.

The research of vulnerability mining technology based on local sequence alignment

Shan Luchao1, Wang Jianzhang2, Xu Desen2, Li Dongyuan2, Zhao Peng2, Wang Guoxiang1, Chu Tengfei1

(1. Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. China Communication System Co.,Ltd., Beijing 100070, China)

This paper studied the efficiency of Global sequence alignment technology in the network protocol vulnerabilities mining system, which is not very high when applied in the analytical process of network protocol format. Under the background of network vulnerability mining, this paper analyzed the sequences comparing technology and proposed a more effective method of vulnerability mining.Based on Fuzzing mining technology and the local sequence alignment,this new method improved the efficiency of vulnerability mining when analyzing the network protocol format.The simulation results showed that this new method has many obvious advantages in the execution efficiency compared with the traditional global sequence alignment method.Key words: vulnerability mining; Fuzzing; local sequence alignment; algorithm

TP309.2

A

10.19358/j.issn.1674- 7720.2017.03.001

单路超，王建章，许德森，等.基于局部序列比对的漏洞挖掘技术研究[J].微型机与应用，2017,36(3)：1-3，7.

2016-10-01)

单路超(1993-)，男，硕士研究生，主要研究方向：多协议网络。

王建章(1964-)，男，高级工程师，主要研究方向：多协议网络，云计算及大数据。

许德森(1957-)，男，研究员，主要研究方向：无线多协议网络，天线技术等。