A Multi-Agent Approach for REST API Testing with Semantic Graphs and LLM-Driven Inputs

📄 arXiv: 2411.07098v2 📥 PDF

作者: Myeongsoo Kim, Tyler Stennett, Saurabh Sinha, Alessandro Orso

分类: cs.SE, cs.AI

发布日期: 2024-11-11 (更新: 2025-01-22)

备注: To be published in the 47th IEEE/ACM International Conference on Software Engineering (ICSE 2025)

💡 一句话要点

AutoRestTest：利用多智能体、语义图和LLM驱动输入进行REST API测试。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: REST API测试 多智能体强化学习 语义属性依赖图 大型语言模型 黑盒测试 API依赖关系 测试用例生成

📋 核心要点

  1. 现有黑盒REST API测试工具通常孤立地测试API、参数和值，导致测试覆盖率低，难以有效检测故障。
  2. AutoRestTest采用多智能体强化学习，结合语义属性依赖图和大型语言模型，协同优化API探索过程。
  3. 实验表明，AutoRestTest在代码覆盖率、操作覆盖率和故障检测方面优于现有工具，并在真实服务中发现独特错误。

📝 摘要（中文）

现代Web服务越来越依赖REST API，对其进行全面测试至关重要。随着OpenAPI Specification等REST API文档语言的出现，涌现了许多黑盒REST API测试工具。然而，这些工具通常孤立地关注单个测试元素（例如，API、参数、值），导致覆盖率较低，故障检测效果较差。为了解决这些限制，我们提出了AutoRestTest，这是第一个采用依赖嵌入的多智能体方法进行REST API测试的黑盒工具，它集成了多智能体强化学习（MARL）、语义属性依赖图（SPDG）和大型语言模型（LLM）。我们的方法将REST API测试视为一个可分离的问题，其中四个智能体——API智能体、依赖智能体、参数智能体和值智能体——协同优化API探索。LLM处理特定领域的价值生成，SPDG模型使用API操作之间的相似性评分简化了依赖关系的搜索空间，MARL动态优化智能体的行为。我们对12个真实REST服务进行的AutoRestTest评估表明，在代码覆盖率、操作覆盖率和故障检测方面，它优于四个领先的黑盒REST API测试工具，包括那些由RESTGPT（使用LLM生成逼真的测试输入）辅助的工具。值得注意的是，AutoRestTest是唯一能够在Spotify服务中触发内部服务器错误的工具。我们的消融研究表明，AutoRestTest的每个组件——SPDG、LLM和智能体学习机制——都有助于其整体有效性。

🔬 方法详解

问题定义：现有黑盒REST API测试工具在生成测试用例时，通常孤立地考虑API、参数和值，忽略了API之间的依赖关系，导致测试覆盖率不足，难以发现深层次的错误。此外，生成有效的测试输入也面临挑战，特别是对于具有复杂语义的参数。

核心思路：AutoRestTest的核心思路是将REST API测试分解为多个智能体协同完成的任务。通过引入API智能体、依赖智能体、参数智能体和值智能体，分别负责API选择、依赖关系探索、参数选择和值生成。利用多智能体强化学习（MARL）动态优化这些智能体的行为，从而实现更有效的API探索和测试。

技术框架：AutoRestTest的整体框架包括以下几个主要模块：1) SPDG构建模块：分析API文档，构建语义属性依赖图（SPDG），用于表示API之间的依赖关系。2) 智能体模块：包含API智能体、依赖智能体、参数智能体和值智能体，每个智能体负责特定的任务。3) MARL训练模块：使用多智能体强化学习算法训练智能体，使其能够协同完成API测试任务。4) LLM驱动的输入生成模块：利用大型语言模型（LLM）生成具有语义合理性的测试输入。

关键创新：AutoRestTest的关键创新在于：1) 提出了一种依赖嵌入的多智能体方法，能够更好地探索API之间的依赖关系。2) 结合语义属性依赖图（SPDG）和大型语言模型（LLM），简化了搜索空间，并生成更有效的测试输入。3) 使用多智能体强化学习（MARL）动态优化智能体的行为，提高了测试效率。

关键设计：SPDG使用API操作之间的相似性评分来简化依赖关系的搜索空间。LLM被用于生成特定领域的价值，例如，生成符合特定数据类型或格式的测试输入。MARL使用Q-learning算法训练智能体，奖励函数的设计旨在鼓励智能体探索更多的API和依赖关系，并发现更多的错误。

🖼️ 关键图片

fig_0

📊 实验亮点

AutoRestTest在12个真实REST服务上的评估表明，它在代码覆盖率、操作覆盖率和故障检测方面优于四个领先的黑盒REST API测试工具，包括RESTGPT。值得注意的是，AutoRestTest是唯一能够在Spotify服务中触发内部服务器错误的工具。消融研究表明，SPDG、LLM和智能体学习机制都对AutoRestTest的整体有效性做出了贡献。

🎯 应用场景

AutoRestTest可应用于各种Web服务的REST API测试，尤其适用于具有复杂依赖关系和需要语义理解的API。该工具能够提高测试覆盖率，发现潜在的错误，并提升Web服务的质量和可靠性。未来，该方法可以扩展到其他类型的API测试，例如GraphQL API。

📄 摘要（原文）

As modern web services increasingly rely on REST APIs, their thorough testing has become crucial. Furthermore, the advent of REST API documentation languages, such as the OpenAPI Specification, has led to the emergence of many black-box REST API testing tools. However, these tools often focus on individual test elements in isolation (e.g., APIs, parameters, values), resulting in lower coverage and less effectiveness in fault detection. To address these limitations, we present AutoRestTest, the first black-box tool to adopt a dependency-embedded multi-agent approach for REST API testing that integrates multi-agent reinforcement learning (MARL) with a semantic property dependency graph (SPDG) and Large Language Models (LLMs). Our approach treats REST API testing as a separable problem, where four agents -- API, dependency, parameter, and value agents -- collaborate to optimize API exploration. LLMs handle domain-specific value generation, the SPDG model simplifies the search space for dependencies using a similarity score between API operations, and MARL dynamically optimizes the agents' behavior. Our evaluation of AutoRestTest on 12 real-world REST services shows that it outperforms the four leading black-box REST API testing tools, including those assisted by RESTGPT (which generates realistic test inputs using LLMs), in terms of code coverage, operation coverage, and fault detection. Notably, AutoRestTest is the only tool able to trigger an internal server error in the Spotify service. Our ablation study illustrates that each component of AutoRestTest -- the SPDG, the LLM, and the agent-learning mechanism -- contributes to its overall effectiveness.