Automatic Generation of Test Purposes for Testing Distributed Systems

Olaf Henniger, Miao Lu, Hasan UralFATES 2003 · DOI

TL;DR

This paper introduces an automated method for generating test purposes for distributed systems, represented as Message Sequence Charts (MSCs). By transforming system specifications into a non-interleaving model called a labeled event structure, the authors can systematically derive test scenarios that cover significant system behaviors, reducing manual effort and improving test suite quality.

What Problem Does This Paper Address?

Testing complex distributed systems is a significant challenge. Specifications for these systems, often modeled as communicating state machines, implicitly define an infinite number of possible execution sequences. Manually creating test cases to cover all meaningful behaviors is time-consuming, error-prone, and often leads to incomplete test suites. Existing automated methods either require extensive manual input for test purposes or are limited to simpler system models. This paper aims to bridge this gap by automatically generating test purposes from system specifications, making test generation more efficient and comprehensive.

Methods

The core of the paper's approach lies in transforming a system specification, initially modeled as asynchronously communicating Extended Finite State Machines (EFSMs), into a labeled event structure. This structure is a non-interleaving model that explicitly captures the partial ordering of events, thus avoiding the state-space explosion problem common with traditional reachability analysis.

Here's a breakdown of their method:

  • Unfolding EFSMs: The system of EFSMs is "unfolded" into a labeled event structure. This process captures all reachable behaviors without linearizing concurrent events.
  • Complete Prefix: A "complete prefix" of this labeled event structure is constructed. This prefix is sufficient to represent all reachable global states of the system.
  • Maximal Configurations: The algorithm identifies "maximal configurations" within this complete prefix. Each maximal configuration represents a significant system behavior that should be tested.
  • PCO Restriction: These maximal configurations are then restricted to events occurring at Points of Control and Observation (PCOs), which are the interfaces to the system's environment. This ensures that the generated test purposes are observable and controllable.
  • Inclusion Checking: To ensure a minimal set of test purposes, configurations that are subsets of others are eliminated.
  • MSC Generation: Finally, the restricted and filtered maximal configurations are formatted as Message Sequence Charts (MSCs), which serve as the test purpose descriptions. These can be either process-level or system-level MSCs.

Datasets

Not discussed in the paper. The paper uses a sliding-window protocol as a running example to illustrate its approach.

Key Insights and Ideas

  • Non-Interleaving Model for Concurrency: Using labeled event structures to model concurrency is a key insight. It allows for a more faithful representation of true concurrency compared to interleaving models, which can lead to an explosion of redundant states.
  • Automatic Test Purpose Generation: The ability to automatically generate test purposes (as MSCs) from a formal specification is a significant advancement. This automates a previously manual and labor-intensive step in test generation.
  • Bridging Explicit and Implicit Test Purposes: The approach combines the benefits of methods with explicit test purposes (flexibility, executable tests) and implicit test purposes (guaranteed coverage). By generating explicit MSCs, the approach provides input for tools that require explicit test purposes, while the generation process itself is implicit and systematic.
  • Focus on Observable Behavior: Restricting test purposes to PCO events is crucial for practical testing, ensuring that the generated tests are actually executable and verifiable.

Key Results

The paper presents a method and a prototype tool for generating test purposes. While specific quantitative results (e.g., reduction in test suite size, increase in fault detection rate) are not detailed, the key qualitative result is the successful generation of MSC-based test purpose descriptions from labeled event structures. The approach is claimed to alleviate the state-explosion problem, preserve true concurrency, and restrict the test suite size in a suitable way, ensuring executability.

Limitations and Future Work

  • Data Flow Aspects: The paper acknowledges that the current approach does not explicitly consider data flow aspects of the specification. While it mentions that data flow oriented test selection criteria can be transferred, the implementation of this is left for future work.
  • Test Case Generation from MSCs: The generated MSCs are described as test purpose descriptions. The paper notes that the direct generation of full MSC test cases (including verdicts and handling of alternatives) from labeled event structures is an area for future work.
  • TTCN-3 Integration: While the generated MSCs can be used as input for test generation tools, the paper mentions that the direct generation of TTCN-3 test cases is also a future research direction.
  • Minimality of Test Suite: While the approach aims to restrict test suite size, the paper notes that covering each maximal configuration once is sufficient for "all-nodes coverage" but doesn't necessarily guarantee all-transition coverage due to potentially untriggered transitions in the EFSMs.

Summary updated

BibTeX
@inproceedings{henniger2003automatic,
  author = {Olaf Henniger and Miao Lu and Hasan Ural},
  title = {{Automatic Generation of Test Purposes for Testing Distributed Systems}},
  booktitle = {FATES},
  year = {2003},
  doi = {10.1007/978-3-540-24617-6\_13},
}
Figure