Formal Test Automation: A Simple Experiment

Axel Belinfante, Jan Feenstra, René G. de Vries, Jan Tretmans, Nicolae Goga, Loe M. G. Feijs, Sjouke Mauw, Lex HeerinkIWTCS 1999 · OpenReview

Abstract

This study, originally published in 1999, explores the transition from manual software testing to automated, mathematically-backed conformance testing for reactive systems. The authors introduce ToRX, an open architecture designed to compare "on-the-fly" and "batch" testing methods across three formal languages: LOTOS, PROMELA, and SDL. Through an experiment involving a "Conference Protocol" and a suite of buggy implementations, the research demonstrates that automated formal testing can achieve high bug detection rates, though it faces challenges in diagnostic complexity and state-space management.

Introduction

In the development of complex reactive systems like network protocols, conformance testing is critical to ensure that a physical implementation adheres to its formal specification. Traditionally, this process has been manual, time-intensive, and prone to human error. A significant bottleneck exists in translating formal mathematical models into executable test suites. This paper addresses this challenge by evaluating two primary automation strategies:

  1. Batch Testing: Deriving a complete, comprehensive test suite upfront before execution.
  2. On-the-fly Testing: Simultaneously deriving and executing test steps in real-time, allowing the tester to react dynamically to the system's behavior.

The ToRX Architecture

To compare these strategies, the researchers developed the ToRX tool architecture. This modular environment is designed to be "plug-and-play," supporting various formal languages and tools.

The ToRX architecture supporting both on-the-fly and batch test derivation and execution.

The architecture separates the concerns of test derivation (handled by the Explorer and Primer) from test execution (handled by the Driver and Adapter). In the on-the-fly approach, the tool "lazily" explores the specification using the ioco (input-output conformance) relation, picking random valid inputs and verifying the implementation's responses. In contrast, the batch approach requires manual definition of "test purposes," which are then converted into formal test suites (TTCN).

Experimental Setup: The Mutant Testbed

The researchers evaluated ToRX using a "Conference Protocol"—a multicast chatbox system. They created a library of 28 distinct C-language implementations: one correct version and 27 "mutants" containing deliberately injected bugs, such as missing outputs or incorrect state updates.

Interaction diagrams for the Conference Protocol testbed, showing (a) joining and (b) data exchange scenarios.

The experiment utilized formal specifications written in LOTOS, PROMELA, and SDL. These specifications and the implementation library were made publicly available to serve as a benchmark for the research community.

Key Insights and Results

The study yielded several critical findings regarding the effectiveness of automated testing:

  • High Detection Rates: The on-the-fly testers successfully identified 25 out of 27 erroneous implementations. The two missed bugs were attributed to "modeling choices" where the specification was not granular enough to forbid the specific incorrect behaviors.
  • The "Lazy" Advantage: On-the-fly testing effectively avoids the "state-space explosion" problem by only calculating the next possible steps rather than the entire system graph. This allows for deeper testing of complex protocols compared to batch methods.
  • Performance and Language Choice: The choice of modeling language significantly impacted performance. The PROMELA-based tester was more memory-efficient and faster than the LOTOS-based version, largely due to superior internal hashing techniques.
  • Batch Limitations: The SDL-based batch approach detected only 6 bugs. This lower performance was due to the limited number of manually defined test cases and memory constraints when deriving large test suites.

Limitations and Future Work

While the results were promising, the authors identified several hurdles for widespread adoption:

  • Guidance vs. Randomness: Purely random on-the-fly testing can take thousands of steps to find specific bugs. Future work should focus on "test-purpose oriented" derivation to guide the tool toward high-risk areas.
  • Diagnostic Complexity: Identifying the root cause of a failure in a trace of 20,000 random steps is extremely difficult for human engineers, highlighting the need for better visualization tools.
  • The Adapter Burden: Although test derivation was automated, the "Adapter" code—which translates abstract actions into concrete network packets—still required manual development.

Summary updated

BibTeX
@inproceedings{belinfante1999formal,
  author = {Axel Belinfante and Jan Feenstra and René G. de Vries and Jan Tretmans and Nicolae Goga and Loe M. G. Feijs and Sjouke Mauw and Lex Heerink},
  title = {{Formal Test Automation: A Simple Experiment}},
  booktitle = {IWTCS},
  year = {1999},
  url = {https://openreview.net/forum?id=kVvVu1xhgp},
}
Figure