AutoRestTest at the SBFT 2026 Tool Competition

Source: arXiv:2607.01063 · Published 2026-07-01 · By Tyler Stennett, Myeongsoo Kim, Saurabh Sinha, Alessandro Orso

TL;DR

AutoRestTest addresses the challenge of black-box testing for REST APIs, where large input spaces and complex inter-operation dependencies hinder effective fault detection and coverage. It innovatively integrates a Semantic Property Dependency Graph (SPDG) to model parameter dependencies, multi-agent reinforcement learning (MARL) to coordinate specialized agents for operation, parameter, value, and dependency selection, and a large language model (LLM) to generate domain-aware parameter values efficiently. Evaluated on the SBFT 2026 REST League benchmark—consisting of 11 real-world APIs and 317 operations—AutoRestTest outperformed five state-of-the-art tools, ranking first across fault detection, overall efficiency, and overall effectiveness categories.

Key findings

• AutoRestTest detected an average of 67.09 unique 5xx server errors per API, 2.7 times more faults than the next best tool (24.65).
• Fault detection AUC over one-hour runs was 151,490 for AutoRestTest, 2.3 times higher than the next competitor's 66,761, indicating faster fault discovery.
• Operation coverage averaged 17.27 successfully processed operations per API, the highest among competing tools.
• The tool ran each API test with about 9.6 million input tokens and 2.2 million output tokens, at a cost of approximately $0.02 per test per service using the Gemini 2.5 Flash Lite LLM model.
• Parallelized LLM-driven value generation with up to three validation retries minized token usage while improving input relevance.
• Stratified sampling of parameters and boundary value mutations (e.g., empty strings, extreme numerics) helped trigger diverse server errors.
• Q-learning with epsilon-greedy action selection was employed in four specialized agents, balancing exploration and exploitation with epsilon decay from 1 to 0.2.
• Limitations included a single crash due to UTF-8 encoding assumptions on one API, suggesting need for more robust response parsing.

Threat model

The adversary is the REST API under test in a black-box scenario where the testing tool has access only to the OpenAPI specification and observes responses to test inputs. The API may return normal, erroneous, or edge-case responses, but cannot manipulate or interfere with the testing process outside normal server replies.

Methodology — deep read

The threat model assumes a black-box setting where the tester only has access to OpenAPI specifications (OAS) and no source code or internal implementation details. The adversary is effectively the REST API under test, possibly returning server errors or state-dependent responses, but cannot interfere with the test agent beyond normal API responses.

Data consists of 11 diverse real-world REST APIs used in the SBFT 2026 REST League benchmark, comprising 317 operations (approx. 29 per API). Each tool submission was evaluated on these APIs with 10 runs per API, each run limited to one hour. Results were averaged to account for nondeterminism.

The core architectural elements:

1. Semantic Property Dependency Graph (SPDG): Parses OAS documents to represent operations as graph vertices, edges weighted by semantic similarity of parameters, bodies, and responses using GloVe embeddings. The graph encodes inter-operation parameter dependencies and is dynamically updated as new dependencies emerge during testing.
2. Multi-Agent Reinforcement Learning (MARL): Four agents specialize in operation selection, parameter inclusion (applying stratified sampling), value assignment (choosing between LLM candidates, previous successful values, and defaults), and maintaining/updating the SPDG. Each agent uses a Q-table with epsilon-greedy strategies (exploration ε starting at 1 decaying to 0.2), learning rate α=0.1, discount γ=0.9.
3. LLM-driven value generation: Prior to test execution, the tool queries the Gemini 2.5 Flash Lite LLM to generate domain-aware parameter values in parallel for all operations. Values are validated against the System Under Test (SUT) with up to three refinement cycles leveraging server feedback.

The training regime consists of running MARL agents online during testing, updating Q-tables based on response codes (2xx rewarded for successful chains, 5xx rewarded for fault detection, other responses penalized). Mutation operators introduce boundary value and syntactic alterations to inputs to trigger edge cases.

Evaluation metrics include unique 5xx (server error) fault counts, operation coverage (number of operations exercised successfully), branch coverage, and area under the curve (AUC) over time for faults and coverage to capture efficiency. Comparisons were run against five other state-of-the-art black-box REST API testing tools.

Reproducibility is supported by the public release of AutoRestTest source code on GitHub. The SBFT 2026 benchmark APIs are real-world but not explicitly stated as publicly available in the paper. Exact random seeds or detailed hardware were not disclosed, but time budgets per run were standardized.

Technical innovations

• Semantic Property Dependency Graph (SPDG) that models inter-operation parameter dependencies using GloVe embeddings to guide exploration, improving effectiveness over naive or random testing.
• Multi-agent reinforcement learning system with four specialized agents coordinating operation, parameter, value selection, and dependency tracking, enhancing adaptive exploration compared to single-agent RL.
• LLM-driven domain-aware input value generation combined with iterative validation against the SUT to minimize token usage and improve input relevance, a novel blend of LLMs with reinforcement learning in API testing.
• Parallelized pre-processing of LLM queries for value generation, reducing setup time and enabling efficient reuse of validated inputs.

Datasets

• SBFT 2026 REST League benchmark — 11 APIs, 317 operations — real-world services used in competition, source not public

Baselines vs proposed

• Next best tool (unnamed): average unique server errors = 24.65 vs AutoRestTest = 67.09
• Next best tool: fault detection AUC = 66,761 vs AutoRestTest = 151,490
• Next best tool: average operation coverage < 17.27 vs AutoRestTest = 17.27

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.01063.

Fig 1: Overview of AutoRestTest [2].

Limitations

• A crash occurred on the flight-search API due to a UTF-8 encoding assumption, highlighting lack of robustness to diverse response encodings.
• No detailed adversarial evaluation beyond standard fault detection was reported.
• Evaluation limited to a fixed one-hour budget without analysis of performance under shorter or longer time constraints.
• Does not report explicit branch coverage metrics nor detailed internal state exploration beyond coverage counts.
• LLM model choice and configuration could affect cost and performance trade-offs; Gemini 2.5 Flash Lite was chosen for expense considerations.
• No ablation study isolating the individual impact of each component (SPDG, MARL, LLM) presented.

Open questions / follow-ons

• How would AutoRestTest perform under adversarial API responses designed to mislead the agents or reward signals?
• Can the MARL agents and SPDG be extended to support authenticated APIs or those requiring complex session management?
• How sensitive is fault detection and coverage to the choice of LLM model and its prompt engineering?
• Could richer reward signals incorporating semantic response analysis or response diversity improve exploration?

Why it matters for bot defense

Bot-defense and CAPTCHA engineers can draw several lessons from AutoRestTest's approach to systematically exploring large and dependent input spaces using a combination of semantic dependency graphs and adaptive reinforcement learning. Just as testing APIs requires understanding interdependent parameters and intelligently generating inputs, bot-defense must probe complex challenge-response schemes while optimizing resource constraints. The use of LLMs to generate domain-aware test inputs demonstrates a promising direction for more context-sensitive input crafting in adversarial settings.

Moreover, AutoRestTest’s balance of fault detection and efficient coverage within strict budgets illustrates the value of reinforcement learning with well-designed reward functions to discover corner cases quickly—an insight applicable to CAPTCHA robustness testing. The limitations around parsing non-standard responses also remind practitioners to anticipate varied and unexpected input/output encodings or behaviors in deployed systems.

Cite

@article{arxiv2607_01063,
  title={ AutoRestTest at the SBFT 2026 Tool Competition },
  author={ Tyler Stennett and Myeongsoo Kim and Saurabh Sinha and Alessandro Orso },
  journal={arXiv preprint arXiv:2607.01063},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.01063}
}

Read the full paper

• arXiv:2607.01063 (abstract)
• arXiv:2607.01063 (PDF)