强化学习与自动化测试（第 1 部分）

我将通过一系列博客文章，分享我们过去将强化学习用于自动化测试的实验，用以追踪缺陷和发现漏洞。

我们最初的目标是构建一种通用的智能方法来识别移动应用中的漏洞，最初针对的是基于 Java 的 Android 应用和基于 LLVM bitcode 的 iOS 应用。实验过程让我们了解了强化学习，并将其用在了一个看起来能产生非常有意思结果的方向上。

对于不熟悉强化学习的读者来说，它是机器学习的一个分支，依靠输入循环来持续改进结果。

例如，AlphaGo 项目就使用了强化学习。它采用的是一种称为深度强化学习的特殊形式，顾名思义，这种形式使用了深度学习。

强化学习实际上相当简单直观。智能体执行一个动作并将其发送给环境，然后收集有关新状态和动作结果（称为奖励或惩罚）的信息，最后根据该输出计算出新的动作。该输入通过一种被称为策略（Policy）的算法计算得出。

据我所知，除了最近两篇自称是首次这样做的 2 篇学术论文之外，此前从未有人提到过将强化学习用于安全测试；但实际上，强化学习在一些安全测试工具中已经存在了相当长的时间，并且已被证明能产生惊人的结果。Michal Zalewsky 开发的 AFL 就是最好的例子，它发现的漏洞数量多得惊人。

AFL 通常被称为进化式模糊测试工具。它生成一个测试用例并传给一个经过插桩的程序，然后收集执行轨迹，并生成旨在提高被测程序代码覆盖率的新输入。

一般来说，进化式模糊测试需要解决 3 个问题：
1- 快速插桩
2- 智能的代码覆盖算法
3- 高效的漏洞识别

虽然第一个问题（快速插桩）和最后一个问题（高效的漏洞识别）与强化学习无关，但我觉得它们非常有意思，值得解释一番。

插桩就是追踪程序的执行过程，原理很简单，但实现起来却出了名的复杂。插桩可以有多种粒度级别：按函数调用、按基本块，甚至按指令。粒度越高，速度就越慢。 对程序进行插桩有以下几种方式： - 编译时插桩，即把添加插桩指令的任务交给编译器完成。最初这是最快的方法，因为编译器对程序有更好的理解，但最重要的是，编译器能够对插桩后的代码运行其优化。 - 基于软件的运行时插桩，这种方法适用于无法获取程序源代码的情况。这是迄今为止最慢的方法，因为它需要在被插桩代码和插桩代码之间不断跳转。它也非常容易出错，很难做对。 - 基于硬件的运行时插桩，这是我最喜欢的方法，因为它兼具两者之长：开销低，且不需要源代码。Intel 和 ARM 在其处理器中加入了对程序追踪的支持，开销非常低，例如 AFL 和 HonggFuzz 都支持使用基于硬件的插桩。

高效的漏洞识别是另一个复杂的课题。最初，大多数模糊测试工具依靠程序崩溃来作为潜在漏洞的迹象。然而，如果溢出太小、不足以覆盖任何有意义的数据，崩溃就可能不会发生。

更先进的方法是 sanitizer 所采用的方法。LLVM sanitizer 在编译时对程序进行修改，使漏洞被触发这一事实更加明显，例如对每一次内存分配都包裹内存保护区。

所有这些方法都只适用于底层语言，用于寻找底层漏洞，例如溢出或释放后使用。

进化式模糊测试工具的第 2 个组成部分是提高代码覆盖率的算法，而这正是强化学习发挥作用的地方。

AFL 使用遗传算法生成输入，并依靠基于基本块的插桩来判断某个输入是否能够触发程序中的新路径。

遗传算法旨在模拟自然选择，其过程包括生成输入、执行一组修改操作（交叉和变异），并从生成的种群中选出能够通过适应度函数的子集。

以 AFL 的遗传算法为例：
- 交叉操作例如包括在输入之间交换数据块；
- 变异操作例如包括位翻转；
- 适应度函数衡量是否发现了新的执行路径。

AFL 还通过优先选择能够触发新执行路径的输入，引入了好奇心元素或探索奖励。遗传算法和探索奖励在现代强化学习解决方案中很常用。

早于 AFL 遗传算法的其他方法则使用 SMT 和 SAT 求解器。这种方法需要非常细粒度的插桩，并尝试求解复杂的方程来发现新的执行分支。

近年来 SMT 求解器取得了巨大进步，但除了未公开的 SAGE 之外，还没有任何模糊测试工具报告过使用这种方法取得良好结果。

其他模糊测试工具则尝试结合多种技术，以综合发挥两种方法的优势。例如，在 DARPA Cyber Grand Challenge 中获得第 2 名的 Driller 就同时使用了 AFL、修改版的 Qemu 和 Z3 SMT 求解器。

在接下来的博客文章中，我将深入探讨这些方法的一些局限，并介绍如何使用强化学习来识别 SQLi、命令注入和 XXE 等高层漏洞。