文献标识码： A
DOI：10.16157/j.issn.0258-7998.191091
中文引用格式： 荆琛，傅晓彤，董伟，等. 基于Q-学习算法的有状态网络协议模糊测试方法研究[J].电子技术应用，2020，46(4)：49-52，56.
英文引用格式： Jing Chen，Fu Xiaotong，Dong Wei，et al. Research on fuzzing method of stateful network protocol based on Q-learning algorithm[J]. Application of Electronic Technique，2020，46(4)：49-52，56.
0 引言
协议漏洞挖掘是保证网络通信安全的重要手段，传统漏洞挖掘技术主要包括逆向分析[1-2]和模糊测试[3]。其中，模糊测试具有准确率高、不要求源代码、适用性高等优点，是目前最常用的协议漏洞挖掘方法。有状态网络协议模糊测试技术的主要发展历程如下。
最初，使用传统的模糊测试方法对包括有状态网络协议在内的所有网络协议进行测试，通过变异或生成的方法产生大量测试用例，将其作为协议实体程序的输入，期望这些不寻常的输入能引发协议实体异常，从中找到协议的安全漏洞[4-5]。这种测试方法对于有状态网络协议来说，当测试用例与协议实体状态不匹配时，测试用例可能会被协议实体直接丢弃，测试用例有效性低[6]。
于是，研究人员提出了根据协议状态机构造测试序列的有状态网络协议模糊测试方法[7-9]，主要包括3个步骤：(1)通过正常的报文交互，将协议实体引导至某个待测状态，这些正常交互报文所构成的序列称为前置引导序列；(2)向协议实体输入报文类型与被测状态相对应的测试用例，检测是否存在异常，如果检测到协议实体在处理测试用例后出现系统崩溃或者停止响应等异常情况，则保存错误现场以待进一步分析；(3)若未检测到异常，还需按照特定顺序输入正常报文将协议实体引导至终止状态，准备下一轮测试，这些正常报文所构成的序列被称为回归序列。这种测试方法提高了测试用例有效性，但前置引导序列和回归序列这些辅助报文在测试过程中的重复交互降低了测试效率，且因是根据协议实体所处的协议状态输入报文类型相对应的测试用例，导致无法发现由报文异常输入顺序所引出的协议缺陷。
因此，本文针对有状态网络协议提出了一种基于Q-学习算法的模糊测试方法，不需要引导状态的辅助类型报文，且能在确保一定的测试用例有效性前提下，引入报文异常输入顺序测试。
1 关于有状态网络协议的模糊测试
1.1 有状态网络协议
根据输入报文相互之间是否存在关联，网络通信协议可分为无状态协议和有状态协议两类[10]。无状态协议是指报文发送方输出的各个报文之间没有关联性，而对于有状态协议，协议实体会记录所接收到的报文信息，在处理报文后可能会出现协议状态的变化。有状态网络通信协议通常采用确定有限状态机(Deterministic Finite Automation，DFA)[11]作为协议交互的形式化描述模型。
将DFA定义为一个六元组M=(S，I，O，δ，β，T)，其中：S={s0，s1，…，sn}是有限状态集合，其中s0表示为M的初始状态，且在任意时刻，M只能处于某一状态si，有限状态机由s0状态开始接收输入；I={i1，i2，…，im}是有限输入符号集合；O={o1，o2，…，om}是有限输出符号集合；δ：S×I→S是状态迁移函数；β：S×I→O是状态输出函数；T是终结状态集合。当DFA应用于网络协议描述时，I表示协议实体可接受并正常处理的输入报文类型集合，O表示协议实体输出的报文类型集合，以M表示协议状态机。
以FTP协议[12]状态机为例，其输入输出报文类型的抽象符号如表1所示，M包括8个状态，状态集合S={s0，s1，s2，s3，s4，s5，s6，s7}。状态机M如图1所示，其中s0到s1的迁移表示为i1/o1，它表示协议实体处于s0状态时，如果接收USER类型报文(用i1表示)，将输出331类型报文(用o1表示)，同时协议实体状态迁移至s1状态。
1.2 关于有状态网络协议的模糊测试
在实施模糊测试时，协议实体对每个测试用例会给出相应的反馈信息[13]，例如当测试用例不能被正确地接收处理时，协议实体会通过响应报文的形式告知。当协议实体处于状态si，输入报文im，根据协议状态机将协议在状态si处理报文im后输出的响应报文on称为由状态si与输入im确定的期望响应报文，如果得到的输出不是响应报文on，则称之为由状态si与输入im确定的非期望响应报文；若根据协议状态机，状态si与报文im并无对应关系，则将得到的任何响应报文都称为由状态si与输入im确定的非期望响应报文。另外，在测试时，若在设定时间阈值内未返回任何报文，也视为得到的是非期望响应报文。关于有状态网络协议的模糊测试，测试用例可以分为以下4类：
(1)第一类测试用例导致协议实体崩溃；
(2)第二类测试用例能够被程序正确接收处理，可以引发协议实体状态跳转并输出期望响应报文；
(3)第三类是导致协议实体输出非期望响应报文的被协议实体直接丢弃的测试用例，没有进行程序执行过程，不会引发协议实体程序异常和状态的转换；
(4)第四类是导致协议实体输出非期望响应报文的引出协议实体缺陷的测试用例。
对网络协议的模糊测试过程主要是为了发现能够触发协议实体异常的测试用例，对于确定的测试用例集，如何能让这些测试用例在模糊测试过程中达到最佳效果？考虑降低第三类测试用例的出现率，提高第一、四类测试用例的出现率。关于一个测试用例，它是触发协议实体异常的第一、四类测试用例，还是被程序正确处理的第二类测试用例，或是被丢弃的第三类测试用例？这与输入该测试用例时协议实体所处的状态密切相关。因此，考虑在测试时根据协议实体状态选取测试用例。对协议实体的状态推断主要依据于协议实体的响应报文。对于在si状态下输入由im变异生成的测试用例，如果协议实体的响应报文是协议状态si和输入im所对应的期望响应报文，那么表明测试用例为第二类测试用例，被协议实体正常接收处理，协议实体状态已经处于sj状态，可以根据状态sj选取测试用例进行下一步测试。如果协议实体的响应报文属于协议状态si和输入im所对应的非期望响应报文，那么协议实体可能仍处于si状态，也可能由于测试用例的作用，跳转到状态si之外的状态。在这种情况下，需要输入与状态si相对应的正常输入报文in，观察协议实体的响应，如果响应报文是状态si和输入in所对应的期望响应报文，那么表明测试用例为第三类测试用例且此时协议实体已经被引导至sq状态，继续输入根据状态sq选取的测试用例进行测试；如果响应报文是状态si和输入in所对应的非期望响应报文，那么在输入报文in之前，协议实体可能出现异常，表明测试用例为第四类测试用例，需要保存输入数据以待进一步分析。
2 基于Q-学习算法的模糊测试方法
2.1 强化学习
强化学习是一种从环境状态映射到动作的学习，目标是使智能体在与环境的互动过程中获得最大累积奖赏[14]。强化学习把学习看作试探评价过程，如图2所示，智能体根据环境状态st选择一个动作at作用于环境，环境在动作at的作用下转移到状态st+1，同时产生一个奖赏rt反馈给智能体，智能体再根据奖赏rt与状态st+1选择下一个动作，选择原则是使奖赏最大化。
强化学习的目的是寻找一个策略π：S→A，使得每个状态s的值函数Vπ(s)或状态-动作值函数Qπ(s，a)达到最大。“值函数”与“状态-动作值函数”分别表示指定“状态”上以及指定“状态-动作”上的累积奖赏[15]。
Q-学习算法[16]是一种异策略时序差分强化学习算法，Q-学习算法中状态-动作值函数采用实际Q值增量式更新，对于状态-动作对(s，a)的值函数Q(s，a)，根据每次采样得到的立即奖赏r进行一次更新：
2.2 基于Q-学习算法的有状态网络协议模糊测试方法
在1.2小节，已经提出根据协议实体状态选取测试用例的思想。由于主要是想通过输入报文类型与被测状态不对应的测试用例引入报文异常输入顺序测试，提高漏洞挖掘能力，因此，考虑根据协议实体状态选择报文类型，然后根据报文类型选取测试用例进行测试。那么，应该以何种策略来根据协议实体状态选择报文类型，以使得在引入报文异常输入顺序测试后仍能确保一定的测试用例有效性呢？这一问题可以通过制定恰当的奖赏规则转化为强化学习中寻找策略π的问题来加以解决，下面就通过Q-学习算法来解决该问题。
(1)状态集合
S={s0，s1，…，sn}，即协议的状态集合。
(2)动作集合
A={a1，a2，…，am}={i1，i2，…，im}，即协议的输入报文类型集合。
(3)动作探索策略
Q-学习通过探索-利用过程发现最优奖赏，“利用”过程选择最大Q值所对应的输入报文类型，“探索”过程则是随机选择输入报文类型以防止发现不了最优奖赏。本文采用“
-贪婪探索策略”，在协议状态s下以小概率
随机选择输入报文类型，以概率1-
选择具有最大Q值的输入报文类型。
(4)立即奖赏
在协议状态s下选择报文类型为a的测试用例进行测试后，根据测试用例的类别确定状态-动作对(s，a)的立即奖赏r。
根据协议实体状态s，依据“
-贪婪探索策略”选择报文类型为a的测试用例对协议实体进行测试。输入测试用例后，通过观察协议实体是否崩溃判断测试用例是否为第一类测试用例；通过响应报文分析协议实体状态并区分第二、三、四类测试用例。根据测试用例的类别确定状态-动作对(s，a)的立即奖赏r，通过奖赏r更新Q值与策略π，降低第三类测试用例的出现率，提高第一、四类测试用例的出现率。基于Q-学习算法的有状态网络协议模糊测试方法描述如下：
(1)建立状态空间S和动作空间A；
(2)初始化Q值表和策略π；
(3)初始化协议实体状态至s0；
(4)依据“
-贪婪探索策略”，根据协议实体当前状态s选择报文类型为a的测试用例输入协议实体；
(5)在协议实体处理测试用例后，观察协议实体反馈信息，分析协议实体当前状态，判断测试用例类别，确定状态-动作对(s，a)的立即奖赏r；
(6)更新Q值表；
(7)更新策略π；
(8)若测试用例为第一、四类测试用例，记录异常后跳转至步骤(3)；若协议实体当前状态为协议终结状态，跳转至步骤(3)；否则跳转至步骤(4)。
3 实验与分析
3.1 实验建立
Sulley[17]是目前较为成熟的模糊测试框架，有对有状态网络协议进行模糊测试的完整测试方案。本文方法Q-Fuzzing 将与Sulley按照以下描述场景进行仿真实验对比：以FTP协议实体作为测试对象，两种方法均采用由Sulley变异策略生成的测试用例，测试用例的漏洞挖掘效力相当。
3.2 实验结果分析
3.2.1 测试效率评估
测试效率是指单位时间输入的测试用例数量，用向被测协议实体输入的测试用例个数与发送报文的总数的比值
值来衡量测试效率，
值的数学表达式为：
=∑A/∑m，其中，∑A表示输入的测试用例总数，∑m表示发送报文的总数。∑A一定时，
值越大，说明发送辅助类型的报文越少，单位时间输入的测试用例数量越高，测试效率越高。在测试过程中，Q-Fuzzing与Sulley的
值与输入的测试用例总数∑A的关系如图3所示。
Sulley采用完善的引导机制，随着测试路径的深入，前置引导序列等辅助报文的比重越来越大，
值越来越低。Q-Fuzzing虽在分析协议实体状态时存在一定的辅助报文交互，但是该方法不需要引导状态的辅助报文，辅助报文的比重较低，
值相对较高。
3.2.2 测试用例有效性评估
假设输入的某个测试用例没有被协议实体直接抛弃，而是进行程序执行过程，那么称该测试用例为有效完成测试的测试用例(简称为有效测试用例)。测试用例有效性是指一个测试用例为有效测试用例的概率，以有效测试用例个数与输入的测试用例总数的比值φ表示测试用例有效性，φ的数学表达式为：φ=∑Ac/∑A，其中，∑Ac表示有效测试用例总数，∑A表示输入的测试用例总数。在测试过程中，Q-Fuzzing与Sulley的测试用例有效性φ与输入的测试用例总数∑A的关系如图4所示。
Sulley采用完善的引导机制，使得测试用例可以在协议实体处于对应状态时进行输入，测试用例有效性较高。Q-Fuzzing在测试初期，输入报文时盲目性较大，存在很多被抛弃的测试用例，测试用例有效性低，但随着在测试过程中实践学习，测试用例有效性逐步提高，最终趋于稳定。
3.2.3 漏洞挖掘能力
漏洞挖掘能力是指在模糊测试正常执行条件下挖掘漏洞的数目。两种方法挖掘漏洞数目如表2所示。
在漏洞挖掘能力方面，Q-Fuzzing效果好于Sulley。对于FTP 协议实体中存在的3个漏洞：(1)当协议实体状态转换序列为s0->s1->s2->s3->s4时，输入变异的i5报文后，协议实体崩溃；(2)当协议实体状态转换序列为s5->s4->s5时，输入与s5状态并不对应的i12的变异报文后，协议实体崩溃；(3)当协议实体状态转换序列为s0->s1->s2->s3->s4->s5时，输入变异的i7报文，协议实体出现状态异常迁移，协议实体既不处于s5状态也不处于s6状态。Q-Fuzzing挖掘出漏洞1、2、3，Sulley仅挖掘出漏洞1，未能挖掘出漏洞2、3。
根据测试效率与挖掘漏洞能力比较，相比于Sulley测试方法，本文测试方法Q-Fuzzing具有明显的优势，达到了预期的测试效果。
4 结论
本文提出了一种基于Q-学习算法的有状态网络协议模糊测试方法，通过反馈信息分析协议实体状态，根据协议实体状态和Q值选取测试用例进行测试。实验结果表明，该方法不需要引导状态的辅助类型报文，且能在确保一定的测试用例有效性下，进行报文异常输入顺序测试，显著提高了测试效率和漏洞挖掘能力。在该方法中，协议状态机的完整性以及学习算法中参数的设定对测试结果的影响很大, 因此，下一步有必要对协议状态机以及参数的调节进行深入的研究。
参考文献
[1] 程必成，刘仁辉，赵云飞，等.非标工业控制协议格式逆向方法研究[J].电子技术应用，2018，44(4)：126-129.
[2] 魏骁，刘仁辉，许凤凯.基于静态二进制分析的工控协议逆向分析[J].电子技术应用，2018，44(3)：126-130.
[3] 张雄，李舟军.模糊测试技术研究综述[J].计算机科学，2016，43(5)：1-8，26.
[4] SUTTON M，GREENE A，AMINI P.Fuzzing：brute force vulner-ability discovery[M].[S.l.]：Pearson Education，2007.
[5] 王颖，杨义先，钮心忻，等.基于控制流序位比对的智能Fuzzing测试方法[J].通信学报，2013，34(4)：114-121.
[6] MUNEA T L，LIM H，SHON T.Network protocol fuzz testing for information systems and applications: a survey and taxonomy[J].Multimedia Tools & Applications，2016，75(22)：14745-14757.
[7] ZHAO J，CHEN S，LIANG S，et al.RFSM-fuzzing a smart fuzzing algorithm based on regression FSM[C].Eighth International Conference on P2P，Parallel，Grid，Cloud and Internet Computing.IEEE，2013：380-386.
[8] CUI B，LIANG S，CHEN S，et al.A novel fuzzing method for Zigbee based on finite state machine[J].International Journal of Distributed Sensor Networks，2014，2014(3)：1-12.
[9] 康红凯，吴礼发，洪征，等.一种基于FSM的BGP-4协议模糊测试方法[J].计算机工程与应用，2017，53(6)：111-117.
[10] 张宝峰，张翀斌，许源.基于模糊测试的网络协议漏洞挖掘[J].清华大学学报(自然科学版)，2009(s2)：2113-2118.
[11] NARAYAN J，SHUKLA S K，CLANCY T C.A survey of automatic protocol reverse engineering tools[J].ACM Computing Surveys，2015，48(3)：1-26.
[12] GASCON H，WRESSNEGGER C，YAMAGUCHI F，et al.Pulsar：stateful black-box fuzzing of proprietary network protocols[M].Security and Privacy in Communication Networks.Springer International Publishing，2015：330-347.
[13] 张洪泽，洪征，周胜利，等．基于协议状态机遍历的模糊测试优化方法[J]．计算机工程与应用，2020，56(4)：82-91.
[14] SUTTON R S，BARTO A G.Reinforcement learning：an introduction[M].Cambridge，USA：MIT Press，1998.
[15] 周志华.机器学习[M].北京：清华大学出版社，2016.
[16] WATKINS C J C H.Learning from delayed rewards[J].Robotics & Autonomous Systems，1989，15(4)：233-235.
[17] GitHub.Sulley[EB/OL].(2013-06-11)[2015-06-29]. https：//github.com/OpenRCE/sulley.
作者信息:
荆 琛1，2，傅晓彤1，董 伟2，赵云飞2
（1.西安电子科技大学 网络与信息安全学院，陕西 西安710071；2.华北计算机系统工程研究所，北京102209）