State Selection Algorithms and Their Impact on The Performance of Stateful Network Protocol Fuzzing
State Choice Mechanisms and Their Influence on the Effectiveness in Stateful Network Protocol Fuzzing
Published
IEEE第45届国际软件分析、改进与重构研讨会（2023）
Authors
背景
如图所示，可将被测试的服务器端系统或应用程序抽象为四个层次结构；对于大多数协议模糊测试而言，则主要包含在程序调用图（call graph）和控制流图（control flow graph）层面的探索算法研究，以期提高模糊测试的有效性和效率。具体而言，在路径（PATH）、函数（Function）、基本块（Basic Block）等方面进行深入研究。尽管顶层状态模型的研究具有重要意义，但目前相关工作常未给予充分重视。基于此，作者决定深入研究状态选择算法的相关问题。
在插入外链图片时出现转存失败的情况，请注意以下几点：首先，在上传前建议将图片保存至本地以备后续使用；其次，请确保目标平台的安全策略设置未被启用或已关闭防盗链机制设置。
AFLNET
AFLNET作为协议模糊测试较为杰出的一个工具，主要支持三种编译算法：
- FAVOR:该策略倾向于选取那些已知存在新增覆盖项或潜在漏洞的种子作为后续测试用例,以期通过重新激活这些状态与数据流来重新定位潜在的问题。
- RANDOM:该算法采用一种基于预设比例的概率模型来随机选取尚未被选用作测试用例的候选节点。
- ROUND-ROBIN:该方法通过循环遍历所有尚未被选用作测试用例的候选节点来实现公平分配机会。
可以看出这三种算法各自都有不同的优势AFLnet作为一种智能优化算法主要通过结合并动态地优化不同算法的特点能够在具有方向性测试的同时进行广泛的探索这种平衡机制有助于其在复杂问题中展现出更强的表现能力一旦发现新的覆盖情况或Crash事件出现时FAVOR机制会立即提高其概率从而加强单一路径的测试力度在常规测试过程中也会偶尔介入ROUND-ROBIN以及RANDOM策略以进一步探索新的程序路径和状态
接下来作者对这三种算法进行测试，测试结果如下：
ProFuzzBench 实验数据显示，在经过24小时运行后发现，在代码覆盖程度上这三种算法表现出高度一致的效果。进一步分析表明，在基准测试中各算法的平均分支覆盖率之间最高相差仅为1.15%
作者分析导致这几个算法出现这一结果的原因可能有两个：
*AFLNet 的状态机存在较大程度上的粗粒化问题,从而使得每个状态的潜力难以被准确评估。
在协议模糊性测试相关的脚本生成或用例设计中,探索(exploration)与利用(exploitation)之间的平衡十分关键;然而现有算法在这一权衡方面尚显不足。
具体而言:
- 探索指的是系统持续探索未知区域,通过尝试新输入值和新测试路径,以实现对程序新增覆盖区域及潜在漏洞的发现。
- 利用则指的是系统聚焦于已知的有效测试路径或输入模式,通过不断变异及重复使用这些资源来提高触发相似程序状态及漏洞的可能性。
因此作者提出，如果解决了这两个问题，AFLNET的覆盖率是否能有所提升？
状态机
该状态机模型用于描述系统的各种可能状态及其转换关系；由有限数量的状态节点以及连接这些节点的转移边构成有向图；在AFLNET系统中，则通过解析服务器返回的状态码信息来确定各个系统的当前运行状态；例如，“200 OK”表示成功返回；而“400 ERR”则表示返回错误信息。
蒙特卡罗搜索树
*Monte Carlo Tree Search (MCTS) algorithm[21] has been demonstrated to possess the capability of exploring vast search spaces.
- LEGION introduces an innovative MCTS-based methodology tailored for coverage-driven software testing. Its variant employs adaptive search strategies that learn from historical code coverage data to prioritize promising program states during each search iteration. By modeling the program's syntax tree as the search space and introducing four nuanced steps in the exploration phase, LEGION adapts conventional MCTS techniques to accommodate constraint execution.
- Selection: Starting from the root node of the MCTS search tree, nodes are sequentially selected until a simulation node is chosen. Simulation nodes are appended to each tree node to allow simulations to commence from parent program states, even at intermediate nodes.
- Simulation: The input for a selected path is generated by solving the constraint paths of its parent simulation nodes. Simulations begin at intermediate nodes.
- Expansion: For every new execution path identified during traversal, if it is novel, it is added to the tree and associated rewards are recorded.
- Propagation: The selection counts for all nodes along the chosen path are incremented by one. Rewards are added to the discovery counts of all nodes along executed paths. However, due to practical constraint solving inaccuracies, some execution paths may not retain their selection paths
方法
如图所示分别为AFLNET及其作者在此基础上提出的改进算法AFLNETLEGION的表现效果对比,其中,AFLNET由于其状态记录较为粗粒化特性,存在如下问题:即在其执行完MKD命令后,实际上应在执行完STOR命令后位于下一个目录,然而,观察到显示结果为NLST与初始状态下N=250时所获得的NLST值存在差异.尽管如此,在现有系统中,AFLNET仍将其视为同一状态,而本研究提出的改进算法则对此进行了区分处理,以克服上述方法对系统状态划分存在的不足.
在AFLNETLEGION中，每个节点都由根到自身的唯一响应代码列标识 。
如图所示为AFLNETLEGION运行流程的过程，并与之前所述的LEGON过程类似：
其中，在行尾处使用红色方括号标注：
- 空节点（圆形）标识可启动服务器的状态。
- 在行尾处设置模拟节点（正方形），用于从空节点发送模糊信号。
- 当一个请求在一个单元格中引发多个响应代码时，
- 最后一个状态码对应的服务器状态触发fuzzing扫描。
- 其余的状态码标记为冗余节点，并不影响模糊测试的结果。
为了解决状态选择中探索与利用的平衡问题，在引入UCT公式时，请参考以下内容。
对于节点计算来说，在此情境下D代表节点在过去所经历的选择次数；S则表示该节点在过去所做出的选择次数；而PS则是指其父节点在过去所做出的选择次数。
在种子评估过程中同样适用上述定义：D即为被选中的种子所积累的选择次数；S则对应于该种子在被评估过程中所经历的选择次数；PS则是与该特定模拟网络中与之相关的父节点的选择次数。
具体而言，在这种情况下过去的发现统计是基于对系统响应序列数量的一种度量；而过去的决策统计则反映了模糊化决策出现的情况。
效果
首先作者对ProFTPDf进行了精心筛选的测试用例的选取，并选取了一组预设的标准进行系统性验证。
测试用例：
测试结果
接下来作者在6个实际应用中的程序上进行测试，测试结果如下：
AFLNETLEGION _ UU 采用UCT策略选出最高分数的状态与种子
AFLNETLEGION _ UR 利用UCT策略进行状态选取，并随机决定种子
AFLNETLEGION _ RR 则采取随机方式同时确定状态与种子
AFLNET_RR RERandomly decide on both seed and state
对于OpenSSH，作者分析改进算法导致效果变差的原因如下：
OpenSSH违背了AFLNETLEGION关于获胜充分性的假设（即确定唯一的一组响应编码序列）。OpenSSH通常接收一组独特编码序列的概率低于1.2%，而另一方（AFLNET）的概率大约为2.5%。
通过每个状态未被选中的频率来决定其潜力，从而进一步降低中标概率
MCTS 在顺序决策方面的优势在这个特定的基准程序中是无用的
不足
综上所述，在改进算法方面所取得的进展仍然未能显著提升代码覆盖率的情况下，可能存在以下几点原因
对于有状态协议而言，在模糊测试场景下的吞吐量表现欠佳；生成的输入经质量评估显示不理想
这些问题阻碍了状态选择算法充分发挥其潜力。
贡献
- 先开展对该协议的状态选择算法应用模糊测试的研究
- 拓展了LEGION算法在协议状态选择方面的应用
- 并为其未来的深入研究提供了基础
- 拓展了LEGION算法在协议状态选择方面的应用
总结
但是，在数据分析的基础上可以看出, 作者的实际实验效果并不令人满意. 为了应对AFLNET对状态记录所采用的粗粒度方法, 作者建议采用与自身唯一的响应码来标识节点, 这一做法虽然能在一定程度上减少冗余, 但同样无法充分证明该方法能够有效解决AFLNET的状态处理粗粒度问题. 同时, 在执行状态记录过程中, 如果一个请求在同一行内触发多个代码, 作者仅记录最后一个代码以表示服务器的响应结果, 并放弃其他状态码. 根据OpenSSH的结果可以看出, 这种方法仍存在较大的误差.
作者采用节点与其自身唯一响应码进行记录，在某种程度上带来了冗余，并不能表明该方法能够有效解决AFLNET中对状态粗粒度处理的问题。此外，在进行状态记录过程中，当一个请求在同一行触发多个响应码时，作者仅记录最后一个响应码以表示服务器的回应，并丢弃其他状态码。通过OpenSSH的结果可以看出这一方法存在较大的误差。
针对作者指出的AFLNET中的第二个问题缺乏探索与利用之间的协调关系，该方法引入了一个数学公式。通过实验对比分析可知，该算法并未带来显著性能提升。因此实际上，并不能证明作者已经解决了他提出的两个问题