RESTler：有状态的REST API模糊化

引用

V. Atlidakis, P. Godefroid and M. Polishchuk, "RESTler: Stateful REST API Fuzzing," 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), 2019, pp. 748-758, doi: 10.1109/ICSE.2019.00083.

摘要

本文介绍了第一个有状态的 REST API 模糊器——RESTler。RESTler 分析云服务的 API 规范，并生成请求序列，通过其 API 自动测试服务。RESTler 通过以下方式生成测试序列:(1)推断规范中声明的请求类型之间的生产者-消费者依赖关系(2)分析来自先前测试执行期间观察到的响应的动态反馈，以便生成新的测试。

我们给出的实验结果表明，这两种技术对于彻底执行测试中的服务是必要的，同时可以修剪可能的请求序列的大搜索空间。我们使用 RESTler 测试了开源服务 GitLab，以及几个微软 Azure 和 Office365 云服务。截止目前，RESTler 在 GitLab 中发现了 28 个 bug，在 Azure 和 Office365 云服务中各发现几个 bug，并且服务所有者已经确认并修复了这些错误。

1 引言

在过去的十年中，我们看到托管软件应用程序(软件即服务)、构建分布式服务和数据处理(平台即服务)以及提供通用计算基础设施(基础设施即服务)的云服务激增。如今，大多数云服务，如亚马逊网络服务(AWS)和微软 Azure 提供的云服务，都是由第三方应用程序和其他服务通过 REST API 以编程方式访问的。与此同时，Swagger 可以说已经成为 REST APIs 最流行的接口描述语言。

目前已有一些工具可以通过 REST APIs 来自动测试云服务，并检查这些服务是否可靠和安全，但是这些工具仍然处于初级阶段。由于这些 REST APIs 测试工具都是最新的，尚未得到广泛的应用，因此它们在发现 bug 方面的效果如何，以及这些 bug 的安全性有多重要，在很大程度上还是个未知数。

本文介绍了第一个自动有状态的 REST API 模糊化工具 RESTler。模糊化意味着自动以发现安全漏洞为目标的测试生成和执行。与其他 REST API 测试工具不同，RESTler 对整个 Swagger 规范执行轻量级静态分析，然后生成并执行测试，以有状态的方式运行相应的云服务。我们所说的有状态，是指 RESTler 试图探索只有使用多个请求序列才能到达的服务状态。使用 RESTler，每个测试都被定义为一系列请求和响应。RESTler 通过以下方式生成测试:

1.推断 Swagger 规范中声明的请求类型之间的依赖关系

2.分析来自在先前测试执行期间观察到的响应的动态反馈，以便生成新的测试

我们提供的经验证据表明，想要彻底测试服务，这两种技术是必要的。RESTler 还实现了几种搜索策略，我们在对 GitLab 进行模糊化时比较了它们的有效性。本文的贡献如下:

1.我们介绍了 RESTler，这是 REST APIs 的第一个自动的、有状态的模糊化工具，它分析一个 Swagger 规范，自动推断请求类型之间的依赖关系，并根据服务响应的反馈动态生成测试。

2.我们给出了详细的实验证据，表明 RESTler 中使用的技术对于有效的自动化有状态 REST API 模糊化是必要的。

3.我们给出了使用三种不同策略搜索由所有可能的请求序列定义的大搜索空间的实验结果，并讨论了它们的优缺点。

4.我们用一个大型流行的开源自托管 Git 服务 GitLab 展示了一个详细的案例研究，并讨论了到目前为止发现的几个新 bug。

5.我们讨论了使用 RESTler 进行测试的初步经验

图 1： 博客 post 服务的 Swagger 规范

2 处理 API 接口规格

在本文中，我们考虑通过用 Swagger 规范描述的 REST APIs 来访问服务。Swagger 规范描述了如何通过其 REST API 访问服务。给定一个 Swagger 规范，开源 Swagger 工具可以自动生成一个网络用户界面，允许用户通过网络浏览器查看文档并与应用编程接口交互。

一个网络用户界面形式的样本 Swagger 规范如图 1 所示。这个规范描述了一个简单的 post 托管服务的应用编程接口。

根据这样的规范，RESTler 自动构建测试生成语法，如图 2 右侧所示。这个语法是用可执行的 python 代码编码的。它由生成 HTTP 请求的代码(在这种情况下为 POST 类型)和处理该请求的预期响应的代码组成。

图 2：Swagger 规范和自动导出的 RESTler 语法

该响应预计将返回一个名为 id 的整数类型的新动态对象。使用左边显示的模式，RESTler 自动生成右边显示的函数 parse_posts。

通过类似地分析本 Swagger 规范中描述的其他请求类型，RESTler 将自动推断出，此类 POST 请求返回的 id 对于生成图 1 所示的最后三种请求类型的格式良好的请求是必要的，每种请求类型都需要一个 id。这些生产者-消费者依赖关系是由 RESTler 在处理 Swagger 规范时提取的，稍后将用于测试生成。

3 测试生成算法

RESTler 使用的测试生成的主要算法如图 3 中类似 python 的符号所示。它开始(第 3 行)处理一个 Swagger 规范，如前一节所述。这一处理的结果是一组请求类型，在图 3 中表示为 reqSet，以及它们的依赖关系。

该算法计算一组请求序列，从 Swagger 推断，表示为 seqSet，最初包含一个空序列。如果请求序列中的每个响应都有一个有效的返回代码(这里定义为 200 范围内的任何代码)，则请求序列有效。在主循环(第 8 行)的每次迭代中，从 n = 1 开始，算法计算长度为 n 的所有有效请求序列 seqSet，然后移动到 n+1，以此类推，直到达到用户指定的最大长度。计算 seqSet 分两步完成。

首先，长度为 n-1 的有效请求序列集被扩展(第 9 行)，创建长度为 n 的新序列集。函数 DEPENDENTS(第 39 行)检查是否满足指定请求的所有依赖关系。当每个作为请求的必需参数的动态对象(由 CONSUMERS(req)表示)都是由对它前面的请求序列(由 PRODUCTs(seq)表示)的某个响应产生的时候，情况就是这样。如果满足所有的依赖性，长度为 n 的新序列被保留(第 19 行)；否则将被丢弃。

其次，如 RENDER 函数(第 23 行)中所述，每个依赖关系得到满足的新扩展的请求序列被逐个渲染(第 10 行)。对于每个新挂起的请求(第 26 行)，计算请求中所有可模糊化的原语类型的列表(第 27 行)(在图 2 右侧所示的代码中，这些类型由 restler_fuzzable 标识)。然后，请求中的每个可模糊化的原语类型被具体化，这将替换从有限的、用户可配置的值字典中取出的该类型的一个具体值。RENDER 函数生成所有可能的这种组合(第 28 行)。因此，每个组合都对应于一个完全定义的请求 newReq(第 29 行)。然后，函数 RENDER 执行这个新的请求序列(第 31 行)，并检查它的响应。

更准确地说，函数 EXECUTE 按顺序逐一执行每个请求，每次检查响应是否有效，提取和记忆动态对象(如果有)，如果需要，按依赖分析确定的顺序在后续请求中提供这些对象；函数 EXECUTE 在第 31 行返回的响应是指序列中最后一个新追加的请求的响应。请注意，如果一个请求序列产生一个以上的给定类型的动态对象，函数 EXECUTE 将记住所有这些对象，但是当后续请求需要时，将按照它们产生的确切顺序提供它们；换句话说，EXECUTE 函数不会尝试这类对象的不同排序。如果一个动态对象被作为参数传递给后续请求，并在该请求后被“销毁”，即它在以后变得不可用，当尝试重用该不可用对象时，RESTler 将通过接收无效状态代码(在 200 范围之外)来检测到这一点，然后将丢弃该请求序列。

因为 n 在第 8 行主循环的每次迭代中递增，所以整个算法在由所有可能的请求序列定义的搜索空间中执行广度优先搜索(BFS)。另外，我们还报告了使用另外两种搜索策略进行的实验:BFS-Fast 和 RandomWalk。

图 3：RESTler 中使用的主要算法

BFS-Fast。在函数 EXTEND 中，不是将每个请求附加到每个序列，而是将每个请求最多附加到一个序列。这导致较小的集合 new SeqSet，其覆盖每个请求，但不生成所有有效的请求序列。像 BFS 一样，BFS-Fast 仍然在第 8 行主循环的每次迭代中练习每种可执行请求类型:它仍然提供完整的语法覆盖，但请求序列更少，这使得它比 BFS 更快地深入。

RandomWalk。在 EXTEND 函数中，取消了 17 号线和 18 号线的两个环路；相反，该函数现在返回一个新的请求序列，其依赖关系得到满足，并通过随机选择 seqSet 中的一个请求序列 seq 和 reqSet 中的一个请求来生成。(该函数随机选择这样的一对，直到满足该对的所有依赖性。)因此，这种搜索策略将比 BFS 或 BFS-Fast 更快、更深地探索可能的请求序列的搜索空间。当 RandomWalk 不能再扩展当前请求序列时，它会从一个空的请求序列从头开始。

4 实现

我们已经在 3151 行模块化 python 代码中实现了 RESTler，这些代码分为:解析器和编译器模块、核心模糊化运行时模块和垃圾收集器(GC)模块。解析器和编译器模块用于解析 Swagger 规范，并生成描述如何模糊目标服务的 RESTler 语法。核心模糊化运行时模块实现图 3 的算法及其变体。垃圾收集器作为一个单独的线程运行，跟踪动态对象随时间的创建，并定期删除超过用户定义限制的老化对象。

目前，RESTler 不支持对带有服务器端重定向的 API 端点的请求。此外，RESTler 目前只能找到定义为意外 HTTP 状态代码的 bug。尽管有这些限制，RESTler 已经在生产规模的开源应用程序和几个微软 Azure 和 Office365 服务中发现了已确认的错误。

5 评估

我们给出了使用 RESTler 获得的实验结果，回答了以下问题:

Q1：推断请求类型之间的依赖关系和分析动态反馈对于有效的自动化 REST API 模糊化是必要的吗？

Q2：随着序列长度的增加，RESTler 生成的测试是否运用了更深入的服务端逻辑？

Q3：在 RESTler 中实现的三种搜索策略在各种 API 之间是如何比较的？

我们使用带有 REST API 的简单博客 post 服务来回答第一个问题(Q1)。我们回答(Q2)和(Q3)使用 GitLab。

A.实验设置

博客 post 服务。我们使用一个简单的博客 post 服务来回答(Q1)。

为了模拟一个想象中的细微错误，在博客 post 的每次更新(带有正文和校验和的 PUT 请求)时，服务会检查请求中提供的校验和是否与当前博客 post 的记录校验和匹配，如果匹配，则会引发一个未捕获的异常。因此，只有在测试生成过程中考虑到跨请求共享的动态对象的依赖性，才会触发和检测到这个错误。

GitLab。我们回答(Q2)和(Q3)使用 GitLab，一个开源的网络服务。对于我们的部署，我们应用了以下配置设置:我们使用 Nginx 来代理 web 服务器，物理内存上限为 2GB 我们将 postgreSQL 用于持久存储；我们对 sidekiq 队列和 redis 使用 GitLab 的默认配置。

模糊字典。对于本节中的实验，我们使用以下字典来表示可模糊化的原语类型。string 可能有 “sampleString”和“”（空字符串）两个值；整数可能有“0”和“1”两个值；布尔值可能有“true”和“false”两个值。

B. 有效的 REST API 接口模糊技术

在这一部分中，我们使用博客 post 服务报告结果，以确定(1)推断请求类型之间的依赖关系和(2)分析动态反馈对于有效的自动化 REST API 模糊化(Q1)是否是必要的。我们选择一个简单的服务，以便清楚地测量和解释被评估的两个核心技术的测试能力。这些能力通过测量服务代码覆盖率和客户端可见的 HTTP 状态代码来评估。

代码覆盖率。首先，我们观察到，如果不考虑请求类型之间的依赖关系(图 4，左上)，代码覆盖率被限制在 130 行以内，并且随着时间的推移没有增加，尽管请求序列的长度增加了。

其次，我们看到，如果不考虑动态反馈来修剪搜索空间中的无效请求序列(图 4，顶部中心)，生成的测试数量会快速增长，即使对于简单的 API 也是如此。

HTTP状态代码。我们做两个观察。首先，关注 40X 状态代码，我们注意到在忽略动态反馈时有大量的 40X 响应(图 4，底部中间)。这表明，如果不考虑服务端动态反馈，可能的无效请求序列的数量会快速增长。

其次，当忽略请求类型之间的依赖关系时，我们看到没有检测到 500 状态代码(图 4，左下角)，而 RESTler 在使用请求类型之间的依赖关系时发现了少数 500 个状态代码(见图 4，左下角和右下角)。

总的来说，这些实验说明了利用请求类型之间的依赖性和使用动态反馈之间的互补性，并表明两者对于有效的 REST API 模糊化都是必需的。

C. 更深入的服务探索

在本节中，我们使用 GitLab 来确定 RESTler 生成的测试是否随着序列长度的增加而执行更深入的服务端逻辑(Q2)。我们在六组与常规操作相关的 GitLab APIs 上执行单独的实验，包括提交、分支、问题和注释、存储库和存储库文件、组和组成员以及项目。

图 4：博客 post 服务代码覆盖率和 HTTP 状态代码随时间的变化

表 1 显示了 6 个目标 API 组中每个 API 组的请求总数，并展示了使用 BFS 的图 3 测试生成算法获得的实验结果。

表 1：用 RESTler 测试通用的 GitLab 应用程序接口。

代码覆盖率。我们通过配置 Ruby 的钩子来跟踪 GitLab 代码覆盖率数据。表 1 显示了在执行了 RESTler 为每个序列长度生成的所有请求序列之后，或者直到 5 小时超时到期为止，所实现的累积代码覆盖率。

表 2：随着时间的推移，BFS、BFS-Fast 和 RandomWalk 的对比。

测试、序列集和动态对象。除了代码覆盖率之外，表 1 还显示了执行的测试数量的增加，RENDER 函数返回后 seqSet 的大小(图 3 的第 10 行)，以及 RESTler 创建的动态对象的数量。

D.搜索策略

我们现在比较 BFS、BFS-Fast 和 RandomWalk 搜索策略的实验结果。对于每种搜索策略，表 2 显示了最大序列长度、1 小时、3 小时和 5 小时后覆盖的代码行数的增加以及达到 5 小时超时时 seqSet 的大小。对于 RandomWalk 搜索策略，重新启动的总数也显示在括号中。

首先，我们将 BFS 与 BFS-Fast 进行比较。我们观察到，五个小时后，BFS 在提交、分支和重新发布方面取得了比 BFS-Fast 更好的覆盖率。

我们现在把 BFS 和 RandomWalk 进行比较。通过构造，RandomWalk 不能保证完全的语法覆盖，因为它在每一代中将每个请求附加到一个随机序列中。此外，在 5 个小时后，RandomWalk 探索了与 BFS 相比更深层次的请求序列。

表 3：BFS、BFS-Fast 和 RandomWalk 在五小时后发现的 bug。

另一方面，我们观察到在 5 小时的 RandomWalk 探索长度为 16 的序列后，覆盖率增加了 847 行。在同一时间段内，BFS 探测长度为 3 的序列，但覆盖率增加了 1163;BFS- fast 探测长度为 5 的序列，覆盖率增加了 1570。issue 平均有 82 个可行的请求渲染。这是相对较大的，在这种情况下，对于许多可行的请求渲染，RandomWalk 实现的搜索广度很小。因此，搜索仍然集中在一个非常有限的子空间，这反映了覆盖范围很差。

E.Bug 分桶

在讨论使用 RESTler 发现的真正错误之前，我们引入了一个分桶方案来聚集类似的 500 个“内部服务器错误”。当模糊化时，同一 bug 的不同实例经常被重复发现。

在我们的上下文中，我们将 bug 定义为在执行请求序列后收到的 500 个 HTTP 状态代码。因此，发现的每个 bug 都与为找到它而执行的请求序列相关联。

当使用 BFS 或 BFS-Fast 时，这种分桶方案将通过找到它所需的最短序列来识别 bug。

表 3 显示了五个小时后，在每个 GitLab API 组中，每个搜索策略找到的 bug 分桶集。最后两列显示了 bug 分桶的交集和并集。在这些实验的背景下，RESTler 在每个 API 组上运行每个搜索策略 5 小时后，发现了 22 个新的独特 bug。

RandomWalk 通过发现最多的 bug 而在表 3 中脱颖而出:21 个，而 BFS 和 BFS-Fast 分别为 16 个和 13 个。5 个小时后，在提交中，RandomWalk 发现的 bug 和 BFS 一样多，比 BFS-Fast 还多。与此同时，RandomWalk 提供的代码覆盖率比 BFS 和 BFS-Fast 都要低 (见表二)。类似地，RandomWalk 在问题中发现 1 个 bug，而 BFS 没有发现，BFS-Fast 也发现了一个。然而，同样，RandomWalk 实现的代码覆盖率比 BFS 和 BFS 的都要低。

总的来说，在我们实验的 5 个小时内，RandomWalk 发现了比 BFS 或 BFS-Fast 更多的 bug，尽管事实上它并不总是提供最好的覆盖率。不清楚这如何推广到更长的模糊化会话或其他 API。然而，很明显，覆盖范围的增加不应该总是决定搜索策略的选择，因为不同的搜索策略在大的搜索空间内可能是互补的。

总结

RESTler 是第一个通过 REST APIs 对云服务进行有状态模糊化的自动工具。虽然还处于早期开发阶段，但 RESTler 能够在 GitLab 中发现 28 个 bug，并在迄今为止测试的四个 Azure 和 Office365 云服务中的每一个中发现几个 bug。事实上，与二进制格式解析器中的缓冲区溢出、网络浏览器中的免费使用错误或网页中的跨站点脚本攻击不同，目前还不清楚 REST APIs 背后可能隐藏着哪些安全漏洞。尽管过去针对云服务的人力密集型测试工作提供了此类漏洞确实存在的证据，但这一证据仍然不够充分。需要像 RESTler 这样的新的自动化工具来获得更系统的答案。

致谢

本文由南京大学软件学院 2021 级硕士曾鹏程翻译转述。