1 Introduction↩︎

REST APIs are central to modern web services, making automated testing of these APIs a critical research area. Most of the tools in this space implement a black-box testing approach: they use the OpenAPI Specification (OAS) [1] to exercise endpoints without source code access. To evaluate and distinguish leading tools, the REST League competition [2] at SBFT 2026 provides a standardized benchmark featuring diverse services and robust evaluation criteria.

Competing against five other state-of-the-art black-box REST API testing tools, AutoRestTest achieved first place across all three evaluation categories—fault detection, overall efficiency, and overall effectiveness. Its success stems from three key components: a Semantic Property Dependency Graph (SPDG) that captures inter-operation dependencies, a multi-agent reinforcement learning (MARL) system with four specialized agents, and a large language model (LLM)-driven value generation module that produces domain-aware inputs. AutoRestTest is publicly available [3].

2 AutoRestTest↩︎

AutoRestTest’s workflow is depicted in Figure 1. Since its initial presentation [4], [5], AutoRestTest has been refined in several ways. LLM preprocessing is now parallelized across operations, reducing setup time. The parameter agent explicitly includes all required parameters and applies stratified sampling over optional parameters for balanced coverage. New boundary value mutations target edge cases (e.g., empty strings, extreme numeric values) to trigger server errors. Finally, broader LLM-provider compatibility supports cheaper and open-source models, and improved OAS parsing increases robustness across diverse specifications.

2.1 Semantic Property Dependency Graph↩︎

AutoRestTest parses the OAS and constructs a graph with each API operation as a vertex. Using a lightweight GloVe embedding model [6], it measures semantic similarity between parameters, request bodies, and responses across operation pairs, adding edges where similarity exceeds a configurable threshold. This weighted graph captures parameter dependency strength and is updated dynamically during testing as new dependencies are discovered.

2.2 REST Agents↩︎

AutoRestTest employs four specialized agents: the operation agent selects the next endpoint to explore, the parameter agent uses stratified sampling to choose which parameters to include, the value agent determines data sources and assigns values (from LLM-generated candidates, previously successful responses, or defaults), and the dependency agent maintains the SPDG and tracks inter-operation dependencies. While AutoRestTest also supports a header agent for basic bearer token authentication, it was disabled for the contest.

Each agent maintains a Q-table and selects actions via an epsilon-greedy strategy with a configurable learning rate and discount factor.

2.3 LLM-Driven Value Generation↩︎

To minimize token usage during testing, AutoRestTest performs LLM-based value generation in a parallelized preprocessing phase. For each operation, the tool queries the LLM to produce domain-aware parameter values and validates them against the System Under Test (SUT). If the validation fails, server responses inform a refined query; this process repeats for up to three attempts per operation. The successfully validated values—or, if all attempts fail, the values from the final retry—are stored in the value agent’s action space for efficient reuse across test generation.

2.4 Request Generation↩︎

With agents initialized and values preprocessed, AutoRestTest begins constructing requests. Each agent independently selects its action, and the resulting request is dispatched to the SUT. The response status code drives a shared reward signal: 2xx responses are prioritized to build successful request chains, while 5xx responses are rewarded to encourage fault detection. All other responses are penalized to steer agents toward productive exploration of the API state space, and Q-tables are updated accordingly.

Finally, to uncover edge cases and internal server errors, AutoRestTest applies mutations to refined request payloads. Mutations include parameter type alterations, name modifications, media type changes, and boundary value substitutions.

3 Evaluation in the REST League↩︎

We submitted AutoRestTest to the REST League [2] competition at SBFT 2026. The evaluation benchmark of the competition consists of 11 real-world REST APIs with 317 operations (approximately 29 per API). The competition organizers executed each tool 10 times per API with a one-hour time budget, averaging the results to account for non-determinism.

3.0.0.1 Configuration

We configured AutoRestTest with a semantic similarity threshold of 0.7, epsilon-greedy exploration starting at \(\epsilon=1\) and decaying to 0.2, learning rate \(\alpha=0.1\), discount factor \(\gamma=0.9\), and mutation probability of 0.2. For LLM-based value generation, we set the temperature to 1 to encourage diverse outputs, and used the low-cost Gemini 2.5 Flash Lite model [7] to manage expenses across runs in the absence of caching.

3.0.0.2 Evaluation Criteria

REST League defines three Z-score-normalized evaluation categories, termed challenges [2]: fault detection (unique 5xx errors), overall efficiency (AUC over time for faults, operations, and coverage), and overall effectiveness (combined end-of-execution fault detection, operation coverage, and branch coverage).

3.0.0.3 Results

AutoRestTest achieved the highest score in all three categories against CATS, EvoMaster, RESTest, RestTestGen, and Schemathesis. Most notably, it detected 2.7\(\times\) more faults on average (67.09) than the next-best tool in that category (24.65), and achieved a 2.3\(\times\) higher fault detection AUC (151,490) than the next-closest tool (66,761), indicating that its MARL architecture and epsilon-decay strategy produce effective tests quickly—critical for time-constrained environments. Beyond fault detection, AutoRestTest also covered the most operations on average (17.27), demonstrating breadth without sacrificing depth. Full results are detailed in the competition report [2].

Across all runs, AutoRestTest consumed approximately 9.6M input tokens and 2.2M output tokens, totaling about $1.83, or roughly $0.02 per run per service.

Despite strong overall performance, AutoRestTest encountered a crash on the flight-search API due to an implicit UTF-8 encoding assumption in its response parser. Future versions will handle diverse response encodings more gracefully.

4 Conclusion↩︎

We presented AutoRestTest and its performance at the SBFT 2026 REST League competition [2], where it ranked first in fault detection, overall efficiency, and overall effectiveness by combining dependency-aware exploration via the SPDG, adaptive test generation through MARL, and LLM-driven value generation—finding 2.7\(\times\) more faults than the next-best tool at roughly $0.02 per run per service. Future work will target more resilient response parsing and richer reward signals to improve robustness across diverse APIs. AutoRestTest is open source and publicly available [3].

References↩︎