刘静静，袁耀东
（1.郑州大学信息工程学院，河南郑州450000；2.郑州澍青医学高等专科学校，河南郑州450064）
基于启发式搜索和分类树的网络协议模糊测试用例生成方法研究
刘静静1，2，袁耀东2
（1.郑州大学信息工程学院，河南郑州450000；2.郑州澍青医学高等专科学校，河南郑州450064）
模糊测试通过向目标系统注入大量的非预期输入找出系统漏洞，是安全检测和漏洞挖掘的有效方法。针对网络协议模糊测试的关键问题之一——测试用例生成方法进行研究，论述了网络协议模糊测试的意义、方法和关键问题，在启发式搜索算法和分类树思想的基础上提出了启发式网络协议模糊测试用例生成方法，分别选取模糊器Peach和FTP作为验证平台与目标协议，借助IDAPro工具提取启发算子并将其写入配置文件，用于指导目标协议测试用例的生成过程，通过测试结果分析验证了启发式网络协议模糊测试用例生成方法的可行性与有效性。
网络协议模糊测试；测试用例生成；启发算子；Peach
0 引言
随着现代软件产业的发展，软件规模不断扩大，其内部逻辑也变得更加复杂[1]。为了保证软件的质量，软件测试环节在软件生命周期中占据非常重要的地位，但仍然不可能彻底消灭软件中所有的逻辑缺陷。模糊测试通过向目标系统提供非预期的输入并异常监视结果发现软件漏洞，是安全检测和漏洞挖掘的有效方法，也是近年来信息安全领域的研究热点之一。网络协议模糊测试发现的漏洞通常具有非常高的危险程度，所以被认为是多数安全研究者最感兴趣的模糊测试类型[2]。在模糊测试的过程中，模糊测试数据生成和异常监视这两个关键环节需要研究者给予特别关注。本文对网络协议模糊测试用例生成方法[3]进行研究。
1 启发式网络协议模糊测试用例生成方法
1.1网络协议分类树的构建过程
一棵网络协议分类树可以用五元组PT=(P,F,A,V,R)表示。其中根节点P代表测试目标网络协议；F代表目标网络协议的协议域，F={field1,field2,field3,…,fieldn}；A代表协议域互不相交的属性，A=A1⋃A2⋃…⋃An={attribute11,attribute12,…,attribute1m1,…,attributen1, attributen2,…,attributenmn}；V代表协议域的属性值，V= V11∪V12∪…V1m1∪V21∪V22∪…∪Vn1∪Vn2∪…∪Vnmn={value| value∈Vij且i=1,2,…,n，j=1,2,…,mi}；R代表协议分类树中父节点和子节点之间的关系，包括目标协议P与协议域F之间的关系、协议域F与属性A之间的关系、属性A与属性值V之间的关系等，R= {relation1,relation2,relation3}，其中relation1={
1.2网络协议模糊测试数据生成过程
基于分类树的网络协议模糊测试数据生成过程可以概括为四个步骤：
（1）选定测试目标网络协议P，并根据其规范划分得到协议域集合F={field1,field2,field3,…,fieldn}，该目标协议可以用n元序组
（2）针对步骤（1）中得到的每个协议域的属性进行分类，得到描述协议域fieldi的属性集合Ai={attributei1，attributei2,…,attributeimi}，其中每个属性attributeij分别在离散的属性值集合Vij中取值(1≤i≤n,1≤j≤mi)。
（3）对每个协议域fieldi不同属性的属性值进行相互组合，得到面向该协议域的测试数据集合Si=Vi1×Vi2×…×Vimi(1≤i≤n)。
（4）依次从面向协议域fieldi的测试数据集合Si中取值，对描述目标协议的n元序组
1.3启发算子在网络协议分类树中的引入
启发式网络协议模糊测试用例生成方法基于分类树的网络协议模糊测试数据生成过程中加入了启发算子的定义，利用启发算子演变得到启发式规则，用于指导每个协议域的测试数据生成过程[4]。
结合文中给出的基于分类树的网络协议模糊测试数据生成的具体过程，需要在步骤（2）中增加获取启发算子的操作，用于对协议域属性值集合Vij的精简。由于应用启发算子后并未对步骤（1）产生影响，而且该步骤的实现难度比较小，通常只需要对协议规范进行解读便可以获取用于描述目标协议的n元序组
启发算子（Heuristic Operator）的定义可以用映射关系fh：Vij→V*ij描述。启发算子的定义可以源于协议分类树中父节点与子节点之间的关系集合R，也可以源于对目标网络协议的协议规范分析，或者可以借助第三方工具进行提取[5]。
1.4启发式网络协议模糊测试用例生成过程
启发式网络协议模糊测试用例生成过程需要利用启发算子h实现协议域属性值集合的精简，为了方便具体的实现过程，可以把启发算子写入相应的配置文件[6]。
在配置文件启发算子定义的基础上可以演变得到形如“if…，then…”的启发规则，用于剔除属性值集合Vij中的无效值，从而得到精简的属性值集合
面向协议域fieldi的测试数据集合Si的生成过程可以视作协议域的属性值集合，进行笛卡尔乘积运算的过程，即Si=Vi1×Vi2×…×Vimi(1≤i≤n)。属性值集合在应用启发算子进行精简之后元素个数减少，即(1≤i≤n,1≤j≤mi)。那么不难得出，精简后面向协议域fieldi的测试数据集合满足
任取mi元序组
2 模糊测试用例生成方法的实现
2.1验证平台网络协议模糊器的选取
根据各网络协议模糊器与验证平台选取标准的匹配结果可知，模糊器Peach和Sulley相对于SPIKE而言，更加符合本文对验证平台的选取标准。考虑到模糊器Peach相对于Sulley而言对测试执行前的准备工作要求更为简单，而其维护更新情况更加频繁，最终选取模糊器Peach作为启发式网络协议模糊测试用例生成方法的验证平台。
2.2启发式网络协议模糊测试用例生成
2.2.1目标协议与实施方案的选取
根据每个请求与之前的请求是否相关，可以把网络协议分为无状态协议（Stateless Protocol）和有状态协议（Stateful Protocol）[7]。无状态协议是指网络协议的相邻数据包之间没有上下文的关联性；有状态协议是指相邻的数据包之间具有上下文的关联性。
在实际运用中，有状态协议比无状态协议的应用更加普遍。本文选取有状态协议的典型代表FTP协议作为目标协议，对启发式模糊测试用例生成方法进行实例验证。FTP协议采用客户端/服务器的工作模式，在现实世界具有极为广泛的应用，选取FTP作为模糊测试目标协议不仅具有普遍的现实意义，同时还能与本文对启发式模糊测试用例生成方法的描述结合起来，避免出现针对相同步骤的多次重复分析[8]。
从客户端连接远程FTP服务程序的过程可以分为建立连接、传送数据、释放连接三个阶段，具体的通信过程可以描述为：
（1）首先建立TCP连接，客户端向FTP服务器发送USER命令表明身份；
（2）然后服务器要求客户端输入密码，客户端发送PASS命令将密码发送给服务器，服务器对客户端进行身份认证；
（3）身份认证通过后客户端可以传输其他FTP命令进行文件操作，需要结束此次连接时用QUIT命令退出。
FTP客户端与FTP服务器进行通信的过程中，首先生成一个TCP虚拟连接用于验证控制信息，然后再生成一个单独的TCP连接用于数据传输。具体如图1所示。
图1 FTP通信使用的两个TCP连接
2.2.2目标协议分类树的构建
FTP命令可以表示为三元序组
2.2.3启发算子的抽取与启发规则的定义
文中选取FTP作为目标协议对启发式网络协议模糊测试用例生成方法进行验证，实现启发算子的提取和定义之前，需要首先对FTP协议传输过程中的数据单位信息有所了解[9]。在计算机网络中，对等层之间传递的数据单位称为协议数据单元（Protocol Data Unit，PDU），OSI七层参考模型中的各层协议数据单元具体如表1所示。
表1 OSI七层参考模型中各层的协议数据单元
目标协议FTP属于OSI七层参考模型中的应用层协议，其协议数据单元是数据（Data），针对FTP协议的测试需要依托利用FTP协议进行通信的程序完成。本文借助IDA Pro工具实现针对测试目标程序的启发算子的提取。利用IDA Pro工具提取启发算子的具体操作步骤示意图如图2所示。
图2 利用IDA Pro工具提取启发算子的操作步骤示意图
2.2.4利用启发算子指导测试数据的生成
启发式网络协议模糊测试用例生成方法中，启发算子的引入是为了减小测试用例生成过程的搜索空间，实现网络协议模糊测试用例生成过程的优化[10]。启发算子配置文件constantList.conf和funcList.conf与具体的启发规则之间的关系如图3所示。
图3 启发算子及其配置文件与启发规则的关系示意图
在验证平台模糊器Peach完成对启发算子配置文件的处理之后，就可以开始利用具体的启发规则指导协议域测试数据的具体生成过程。启发式的协议域测试数据由格式化字符串、普通字符串、整型值、不同编码方式的字符串四个部分组成。
3 网络协议模糊测试用例生成方法的验证
3.1模糊测试方案与环境要求
启发式网络协议模糊测试用例生成方法的实例验证过程在Windows操作系统环境下进行。利用模糊器Peach2.3.8源码在Windows平台下执行模糊测试所依赖的工具或者库，主要包括网络封包抓取工具Winpcap、调试工具Windbg、Python扩展等，要求在测试开始之前完成相应的安装准备工作。
测试实施方案示意图如图4所示。从图4中可知，模糊器Peach扮演客户端的角色对FTP服务端程序的安全性进行测试，而模糊器所集成的监控模块在测试过程中用于收集测试目标的行为并分析判断测试目标是否出现异常。
图4 实例验证所采用的测试实施方案示意图
鉴于Open-FTPD1.2存在已知的安全漏洞，更适合作为模糊测试效果实例验证的测试目标程序。采用该FTP服务端程序作为测试目标程序，在模糊器Peach的平台上对启发式网络协议模糊测试用例生成方法的有效性进行验证。考虑到模糊测试的执行时间，实例验证过程只选择FTP命令中最常用的USER命令进行测试，以简化测试环节的处理。
利用模糊器Peach开始测试前，首先需要针对FTP服务端程序Open-FTPD定义相应的Pit文件openftp. xml，从而构造出完整的模糊器。Pit文件中DataModel元素用于对数据模型进行定义，包括数据结构和数据关系等，一个Pit文件中可以定义多个数据模型。
Pit文件中的Test元素用于定义测试配置信息，用于指定测试中所用的状态模型StateModel，Publisher等信息。其中状态模型用于描述如何与目标程序进行通信，而Publisher用于定义模糊器Peach的I/O连接，构造网络协议数据流或者文件流等。
Pit文件中的Agent元素用于定义代理和监视器信息，指定模糊器Peach在测试执行过程中用于监视测试目标程序异常的调试器。每个Pit文件中可以定义多个Agent元素，每个Agent元素中可以定义多个Monitor。
3.2实验验证与结果分析
3.2.1模糊测试效率分析
利用模糊器Peach的语法命令“peachcpeach_xml_file[run_name]”分别对应用启发式模糊测试用例生成方法前后所生成的测试用例数量进行计算。根据运行结果可知，改进前的测试用例为12 966个，而改进后的数量减少到2 532个，仅为原有测试用例总数的19.5%，证明启发式模糊测试用例生成方法有效地减少了用例生成的总数量。
模糊测试通过向目标程序注入大量的畸形数据试图发现测试目标中存在的漏洞，测试用例的数量直接关系到模糊测试的执行时间，亦即模糊测试的效率。根据实验结果可知，改进前的测试执行时间为10小时16分钟28秒，而改进后的执行时间降低到22分钟16秒，仅为改进前的测试执行时间的约3.6%，显著提升了模糊测试的效率。
3.2.2发现漏洞能力分析
针对OpenFTPD1.2执行模糊测试在应用启发式模糊测试用例生成方法前后，均捕获到的漏洞包括Tainted Data Controls Branch Selection和Tainted Data Passed To Function两种类型，证明改进后的测试用例的有效性并没有因为总数量的减少而削弱。
在能够触发测试目标程序异常的模糊测试用例数量方面，应用启发式模糊测试用例生成方法前模糊器Peach触发Tainted Data Controls Branch Selection异常的用例数量为2个，触发Tainted Data Passed To Function异常的用例数量为18个。
应用启发式模糊测试用例生成方法前模糊器Peach触发Tainted Data Controls Branch Selection异常的用例数量为12个，触发Tainted Data Passed To Function异常的用例数量为22个。
改进前触发测试目标程序异常的测试用例总数为20个，占测试用例总数量的比例为20/12 966≈0.15%；改进后触发测试目标程序异常的测试用例总数为34个，占测试用例总数量的比例为34/2 532≈1.34%，有效测试用例的比例约为改进前的9倍，证明了启发式模糊测试用例生成方法的有效性。
3.2.3测试用例详细分析
针对应用启发式模糊测试用例生成方法前后的有效测试用例做详细比较，可以把改动前后有效测试用例的存在情况分为三种情况，具体如表2所示。
表2 改动前后的有效测试用例的存在情况分类
4 结论
本文在启发式搜索算法和分类树思想的基础上提出了启发式网络协议模糊测试用例生成方法，并对该方法的可行性和有效性进行了实例验证。文中对启发式网络协议模糊测试用例生成方法的研究仍然存在很多不足之处，目前尚未对OSI参考模型中其他层的网络协议进行具体实现与验证，需要在后续的研究过程中进行更加深入的探讨，在具体实现和实例验证的基础上总结提取启发式算子的常用方法。
[1]李伟明，张爱芳，刘建财，等.网络协议的自动化模糊测试漏洞挖掘方法[J].计算机学报，2011，34（2）：242-255.
[2]李卓君.一种新的协议安全漏洞检测方法[J].计算机安全，2012（7）：79-82.
[3]张宝峰，张翀斌，许源.基于模糊测试的网络协议漏洞挖掘[J].清华大学学报（自然科学版），2009，49（z2）：2113-2118.
[4]李玉，钱雪忠.启发式遗传算法求解两两组合测试用例集[J].计算机工程与设计，2011，32（5）：1722-1724.
[5]潘晓英，陈皓.基于组织进化粒子群优化的测试用例自动生成[J].计算机应用研究，2012，29（6）：2065-2067.
[6]田江，高炽扬，李亚伟.基于智能算法的测试数据自动生成模型研究[J].信息安全与技术，2010（11）：27-29.
[7]崔应霞，李龙澍，姚晟.组合测试用例集的动态生成算法[J].电子科技大学学报，2011，40（7）：612-619.
[8]黄玉涵，曾凡平，潘能刚，等.基于搜索算法的测试用例优化问题研究[J].小型微型计算机系统，2011，32（5）：840-844.
[9]游亮，卢炎生.测试用例集启发式约简算法分析与评价[J].计算机科学，2011，38（12）：147-150.
[10]刘龙霞，吴军华.基于分类树和贪心算法的测试数据自动生成方法[J].计算机工程与设计，2011，32（8）：2734-2736.
Research on network protocol fuzzy test case generation method based on heuristic search and classification tree
LIU Jingjing1，2，YUAN Yaodong2
（1.School of Information Engineering，Zhengzhou University，Zhengzhou 450000，China；2.Zhengzhou Shuqing Medical College，Zhengzhou 450064，China）
The fuzzy test is an effective method of security detection and vulnerability mining，which can find out the system vulnerabilities by means of injecting massive unexpected inputs to the target system.The test case generation method as one of the key issues of the network protocol fuzzy test is studied.The significance，method and key issues of network protocol fuzzy test are discussed.The heuristic network protocol fuzzy test case generation method is proposed based on the heuristic search algorithm and classification tree thought.The Peach and FTP are selected as the verification platform and target protocol respectively.The tool IDA Pro is used to extract the heuristic operator，and write it into the configuration file to guide the test case generation process of target protocal.The test result verified the feasibility and effectiveness of fuzzy test case generation method of heuristic network protocol.
network protocol fuzzy test；test case generation；heuristic operator；Peach
TN915.04-34；TM417
A
1004-373X（2016）21-0036-04
10.16652/j.issn.1004-373x.2016.21.009
2016-01-04
刘静静（1982—），女，河南郑州人，在读硕士，讲师。主要研究方向为计算机网络、数据挖掘。
袁耀东（1984—），男，河南郑州人，硕士，讲师。主要研究方向为计算机网络及应用、虚拟化与云计算。
