💻 computer science

Invariant-Driven Automated Testing

This paper addresses the lack of effective automated testing for microservice architectures by introducing APOSTL, a first-order logic-based annotation language for API specifications, and PETIT, a tool that leverages these annotations to automatically test microservices independently of their source code.

Original authors: Ana Catarina Ribeiro

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ana Catarina Ribeiro

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Problem: The "Black Box" Kitchen

Imagine a bustling restaurant where the kitchen is a Black Box. You (the customer) can see the menu and the waiter taking your order, but you cannot see inside the kitchen. You don't know if the chef is using fresh ingredients, if the stove is working, or if they are secretly serving you old food.

In the world of software, this is a Microservice. It's a tiny, independent program that does one specific job (like processing a payment or managing a user profile). Companies are building entire apps out of these tiny services.

The Issue:
Currently, the "menu" (the API specification) only tells you what the dish looks like (e.g., "We accept a name and a photo"). It doesn't tell you the rules of the kitchen.

Does the chef know that if you order a "Pizza," they can't also serve a "Salad" at the same time?
If you ask for a pizza that doesn't exist, does the chef politely say "Sorry," or do they crash the whole kitchen?

Without these rules, testing these services is a nightmare. Developers are currently doing it manually, like a food critic tasting one dish at a time, hoping to catch a mistake. It's slow, unreliable, and dangerous.

The Solution: The "Smart Menu" and the "Robot Critic"

The author, Ana Catarina, proposes a two-part solution to fix this: a Smarter Menu and a Robot Critic.

1. The Smarter Menu: APOSTL

The current menu (OpenAPI) is too simple. It lists ingredients but not the laws of physics in the kitchen.

The author invents a new language called APOSTL (API PrOperty SpecificaTion Language). Think of APOSTL as adding a "Contract" to the menu.

Pre-conditions (The "Before" Rules): "You can only order a Pizza if you haven't already ordered a Burger."
Post-conditions (The "After" Rules): "After you order a Pizza, the kitchen must have a Pizza in the oven."
Invariants (The "Always True" Rules): "The kitchen can never have more than 50 pizzas in the oven at once."

APOSTL turns a simple list of ingredients into a set of logical rules written in plain English (mostly). It tells the system exactly what should happen, not just what can happen.

2. The Robot Critic: PETIT

Once the menu has these smart contracts, the author built a tool called PETIT (aPi tEsTIng Tool).

Imagine a robot food critic that:

Reads the Contract: It looks at the APOSTL rules.
Generates Orders: It doesn't just order "Pizza." It orders "Pizza with no toppings," "Pizza with 100 toppings," and "Pizza when the oven is full." It creates thousands of unique, logical scenarios.
Places the Order: It sends the order to the Black Box kitchen (the microservice).
Checks the Result: It looks at what comes back.
- Did the kitchen crash?
- Did it serve a salad when it promised a pizza?
- Did it break the rule about the 50-pizza limit?

If the kitchen breaks a rule, the Robot Critic raises a red flag: "ERROR! The contract was violated!"

How It Works in Real Life (The Tournament Analogy)

To prove this works, the author used a "Tournament App" as a test case. Imagine a system that manages sports tournaments and players.

The Rules (APOSTL):
- Rule: You can't join a tournament if it's already full.
- Rule: You can't delete a player who isn't registered.
The Robot (PETIT) in Action:
- Scenario A (Success): The robot tries to join a player to an empty tournament. The kitchen accepts it. The robot checks: "Is the player now in the system?" Yes. Pass.
- Scenario B (Failure): The robot tries to join a player to a tournament that is already full. The kitchen rejects it. The robot checks: "Did it say 'No'?" Yes. Pass.
- Scenario C (The Bug): The author secretly broke the kitchen code so that when you try to delete a player, it deletes the wrong person.
  - The Robot tries to delete "Player A."
  - The kitchen deletes "Player B" instead.
  - The Robot checks the contract: "Did Player A disappear?" No. "Did Player B disappear?" Yes.
  - Result: FAIL. The Robot catches the bug immediately, even though the kitchen didn't crash.

Why This Matters

Before this paper, testing these tiny services was like trying to find a needle in a haystack by looking at the haystack once.

Old Way: Manual testing. Slow, expensive, and prone to human error.
New Way (PETIT + APOSTL): Fully automated. The robot generates the tests, runs them, and checks the results against the logical rules.

The Catch (Limitations)

The paper admits the robot isn't perfect yet:

Order Matters: If the robot tries to delete a player before it creates one, it might think the system is broken when it's actually just following the wrong sequence. The robot needs to be told the right order of operations (e.g., "Create first, then Delete").
Complexity: The "Smart Menu" language (APOSTL) is a bit simple right now. It can't handle extremely complex, nested rules (like "If the player is in a tournament, and the tournament is in a city, and the city is in a country...").

The Bottom Line

This paper gives us a blueprint for automating trust. By adding logical rules (contracts) to our software descriptions and building a robot to enforce them, we can stop guessing if our software works and start knowing it does. It turns the chaotic, dangerous migration to microservices into a safe, automated process where the "Robot Critic" ensures the kitchen is always cooking up the right dish.

1. Problem Statement

The rapid adoption of Microservice Architectures has introduced significant challenges in software testing. Unlike monolithic applications, microservices are often developed by different teams and deployed independently, frequently acting as black-box systems where source code is inaccessible to the consumer.

The core problems identified are:

Lack of Automated Testing: Industries are migrating to microservices without robust, automatic testing processes. Current practices rely heavily on manual testing or semi-automated tools that lack deep semantic understanding.
Insufficient API Specifications: Standard API description languages, such as OpenAPI Specification (OAS), describe data structures (types, schemas) and HTTP verbs but lack semantic information. They do not define logical conditions like preconditions, postconditions, or system invariants. Without these, automated tools cannot verify if a service behaves correctly according to its intended logic, only if it returns valid HTTP codes.
Ineffective Test Data Generation: Existing black-box testing tools often generate random data that may not satisfy the specific constraints of the microservice, leading to redundant tests or missed edge cases.

2. Methodology and Proposed Solution

The thesis proposes a fully automated, black-box, specification-based testing approach. The solution consists of two main components: a new specification language (APOSTL) and an automated testing tool (PETIT).

A. APOSTL (API PrOperty SpecificaTion Language)

APOSTL is an extension of the OpenAPI Specification designed to annotate APIs with formal contracts based on first-order logic. It leverages OAS's ability to add custom properties (prefixed with x-) to define:

Preconditions (x-requires): Logical conditions that must hold before an operation is executed.
Postconditions (x-ensures): Logical conditions that must hold after an operation completes.
Invariants (x-invariants): Global properties that must always hold true for the system state.
Data Generation Hints (x-regex): Regular expressions to guide the generation of valid test data for specific parameters.

Key Constraints: APOSTL restricts the use of pure operations (specifically GET requests) within its logical formulas to avoid side effects during verification. It supports quantifiers (universal for, existential exists) but currently limits them to avoid nested quantifiers or multi-variable quantifiers to maintain tractability.

B. PETIT (aPi tEsTIng Tool)

PETIT is the automated tool that executes the testing process. It takes an OAS document annotated with APOSTL and performs the following workflow:

Parsing: It parses the OAS document and the APOSTL formulas using ANTLR (Another Tool for Language Recognition).
Test Data Generation: It generates valid test data based on the OAS schemas and x-regex patterns. It employs an object pool mechanism to recycle valid data (e.g., reusing a created player ID for subsequent update/delete operations) to ensure consistency and reduce redundancy.
Operation Categorization: Operations are categorized into three types:
- Constructors (POST): Create resources.
- Mutators (PUT, DELETE): Modify or remove resources.
- Observers (GET): Retrieve resources.
Execution Strategy: The tool allows users to define the order of testing categories (e.g., CMO: Constructors $\to$ Mutators $\to$ Observers). This is crucial because Mutators and Observers depend on resources created by Constructors.
Verification:
- Pre-check: Verifies invariants and preconditions.
- Execution: Sends the HTTP request.
- Post-check: Verifies postconditions and invariants against the response.
- Oracle: Uses the APOSTL formulas to determine if the result is a pass, fail, or inconclusive.
Cleanup: Automatically reverts all changes made to the microservice database after the test run to ensure a clean state.

3. Key Contributions

APOSTL Specification Language: A domain-specific language that extends OpenAPI with formal logic (pre/post-conditions and invariants) tailored for testing, balancing expressiveness with usability for developers.
PETIT Tool: A fully automated testing framework that integrates specification parsing, intelligent test data generation, and contract verification without requiring access to source code.
Order-Dependent Testing Strategy: The introduction of operation categorization (Constructors, Mutators, Observers) and the ability to control execution order, which is critical for testing stateful microservices where operations depend on the existence of prior resources.
Data Recycling Mechanism: An algorithm that manages a pool of generated objects to ensure that Mutators and Observers are tested with valid, existing data, preventing "resource not found" errors that are artifacts of the test setup rather than implementation bugs.

4. Results and Evaluation

The solution was evaluated using a case study application involving Players and Tournaments APIs.

Correct Implementation: When tested against a correct implementation, PETIT successfully verified the system. However, the evaluation highlighted that a single execution order (e.g., CMO) might not cover all possible failure scenarios (e.g., attempting to delete a resource that was already deleted). The tool correctly identified "inconclusive" tests where preconditions were too permissive to distinguish between expected failures and bugs.
Faulty Implementation: Errors were intentionally injected into the application (e.g., failing to store a player, deleting the wrong player, returning null on deletion).
- Detection Rate: PETIT successfully detected all injected errors when the appropriate Order Strategy was used.
- Impact of Strategy: The evaluation demonstrated that the choice of strategy is critical. For instance, testing Mutators before Constructors (MCO) resulted in "expected failures" for Mutators because no resources existed yet, masking potential implementation bugs in the Mutators themselves.
- Error Localization: The tool provided detailed execution traces, pinpointing exactly which precondition or postcondition failed and why (e.g., "Player with NIF X not found").

5. Significance and Conclusion

This work addresses a critical gap in the microservice ecosystem: the lack of automated, semantic-aware black-box testing.

Shift from Structural to Semantic Testing: By extending OpenAPI with logical contracts, the thesis moves testing beyond simple schema validation to verifying business logic and state consistency.
Practical Applicability: The tool is designed to work in real-world scenarios where source code is unavailable, relying solely on the API contract.
Future Work: The author identifies areas for improvement, including:
- Enhancing APOSTL to support nested quantifiers for more complex invariants.
- Allowing multiple test iterations per operation to test numerical invariants (e.g., capacity limits) more thoroughly.
- Supporting other API description languages beyond OpenAPI (e.g., RAML).

In summary, the thesis presents a viable methodology for transforming static API documentation into dynamic, executable test artifacts, significantly improving the reliability and automation of microservice testing.