AutoRestTest at the SBFT 2026 Tool Competition

Technical Summary: AutoRestTest at the SBFT 2026 Tool Competition

Problem Statement
Testing REST APIs presents significant challenges due to large input spaces and complex inter-operation dependencies. Most existing tools employ a black-box approach, utilizing OpenAPI Specifications (OAS) to exercise endpoints without access to source code. However, effectively navigating these vast input spaces to detect faults while maintaining efficiency remains a critical research gap. The SBFT 2026 REST League competition was established to provide a standardized benchmark featuring diverse services and robust evaluation criteria to distinguish leading tools in this domain.

Methodology
AutoRestTest addresses these challenges through a workflow that integrates three core components: a Semantic Property Dependency Graph (SPDG), a Multi-Agent Reinforcement Learning (MARL) system, and a Large Language Model (LLM)-driven value generation module.

1. Semantic Property Dependency Graph (SPDG): The system parses the OAS to construct a graph where API operations serve as vertices. Using a lightweight GloVe embedding model, it calculates semantic similarity between parameters, request bodies, and responses across operation pairs. Edges are added where similarity exceeds a configurable threshold, creating a weighted graph that captures parameter dependency strength. This graph is updated dynamically as testing progresses and new dependencies are discovered.
2. Multi-Agent Reinforcement Learning (MARL): The system employs four specialized agents, each maintaining a Q-table and selecting actions via an epsilon-greedy strategy:
   • Operation Agent: Selects the next endpoint to explore.
   • Parameter Agent: Uses stratified sampling to determine which parameters to include, ensuring all required parameters are present while balancing coverage for optional ones.
   • Value Agent: Determines data sources and assigns values. It draws from LLM-generated candidates, previously successful responses, or defaults.
   • Dependency Agent: Maintains the SPDG and tracks inter-operation dependencies.
   • Note: A header agent for bearer token authentication was supported but disabled for the contest.
3. LLM-Driven Value Generation: To minimize token usage, value generation occurs in a parallelized preprocessing phase. For each operation, the system queries an LLM to produce domain-aware parameter values. These are validated against the System Under Test (SUT). If validation fails, server responses inform a refined query, repeating up to three times. Validated values (or the final retry values) are stored in the value agent's action space for reuse.
4. Request Generation and Mutation: Once agents are initialized, they independently select actions to construct requests. The response status code drives a shared reward signal: 2xx responses are prioritized to build successful chains, 5xx responses are rewarded to encourage fault detection, and other responses are penalized to steer exploration. Additionally, the system applies mutations to payloads (e.g., parameter type alterations, boundary value substitutions) to uncover edge cases and internal server errors.

Key Contributions and Refinements
Since its initial presentation, AutoRestTest has been refined to improve efficiency and robustness:

• Parallelized LLM Preprocessing: Reduces setup time by processing operations concurrently.
• Enhanced Parameter Handling: Explicit inclusion of required parameters and stratified sampling for optional ones.
• Boundary Value Mutations: Targeted mutations (e.g., empty strings, extreme numeric values) to trigger server errors.
• Broadened Compatibility: Support for cheaper and open-source LLM providers and improved OAS parsing for diverse specifications.

Results
In the SBFT 2026 REST League, AutoRestTest competed against five other state-of-the-art black-box tools (CATS, EvoMaster, RESTest, RestTestGen, and Schemathesis) across 11 real-world REST APIs containing 317 operations. Each tool was executed 10 times per API with a one-hour time budget.

• Ranking: AutoRestTest achieved first place in all three evaluation categories: fault detection, overall efficiency, and overall effectiveness.
• Fault Detection: It detected an average of 67.09 unique server errors (5xx) per API, which is 2.7 times more than the next-best tool (24.65).
• Efficiency: It achieved a fault detection Area Under the Curve (AUC) of 151,490, which is 2.3 times higher than the closest competitor (66,761), indicating rapid generation of effective tests.
• Coverage: It covered an average of 17.27 successfully processed operations per API, demonstrating broad coverage.
• Cost: The system consumed approximately 9.6M input tokens and 2.2M output tokens across all runs, totaling roughly $1.83 in costs, or approximately $0.02 per run per service.

Significance and Limitations
The paper claims that AutoRestTest's success stems from the synergy of dependency-aware exploration (SPDG), adaptive test generation (MARL), and domain-aware input generation (LLM). The results suggest that this architecture is particularly effective in time-constrained environments, producing high-value tests quickly.

The authors acknowledge a specific limitation encountered during the competition: a crash on the flight-search API caused by an implicit UTF-8 encoding assumption in the response parser. They note that future versions will aim to handle diverse response encodings more gracefully. The tool is publicly available as open-source software.