A Temporal Logic Based Theory of Test Coverage and Generation

Hyoung Seok Hong, Insup Lee, Oleg Sokolsky, Hasan UralTACAS 2002 · OpenReview

Abstract

This paper presents a theory of test coverage and generation from specifications written in EFSMs. We investigate a family of coverage criteria based on the information of control flow and data flow and characterize them in the branching time temporal logic CTL. We discuss the complexity of minimal cost test generation and describe a method for automatic test generation which employs the capability of model checkers to construct counterexamples. Our approach extends the range of applications of model checking from formal verification of finite state systems to test generation from finite state systems.

Introduction

Testing systems modeled as Extended Finite State Machines (EFSMs)—which augment standard state machines with variables and operations—is a notoriously difficult task. Because EFSMs can theoretically have an infinite number of executions, testers rely on coverage criteria (e.g., ensuring every transition is fired at least once) to select a finite, manageable set of tests.

Traditionally, two primary methods have been used:

  1. Unfolding: Converting the EFSM into a giant, ordinary FSM by enumerating all possible variable values. This often leads to "state explosion."
  2. Flow Graphs: Abstracting the data flow, which is more scalable but frequently generates "ghost" tests that are logically impossible to execute.

This paper proposes a middle ground: treating test generation as a model checking problem to ensure that generated tests are both executable and formally sound.

Methodology: Mapping EFSMs to Formal Logic

The core innovation lies in mapping an EFSM into a Kripke structure, a formal model compatible with model checkers. By doing so, standard testing goals can be translated into Computation Tree Logic (CTL) formulas. For instance, covering a specific state $s$ is equivalent to finding a path that satisfies the formula $EF(s \wedge EF(exit))$. When a model checker verifies such a property, it produces a "witness"—a specific execution path that serves as a valid, executable test case.

Figure 1: The Coffee Vending Machine EFSM used as a running example.

Data Flow Analysis and Coverage Criteria

For more complex data flow criteria, such as "affect relations" (how an input variable eventually influences an output through a chain of assignments), standard CTL is insufficient. The authors extend the theory using least fixpoints of predicate transformers to characterize these long-distance dependencies. This allows for the formal definition of criteria like All-def, All-use, and All-input/output pairs. The Coffee Vending Machine example (Figure 1) demonstrates how these definitions and uses are extracted from transitions to build these pairs.

Figure 2: Table defining the DEF, USE, and DA (Definition-Affect) sets for each transition in the vending machine model.

Complexity and Optimization

Since a single test case can satisfy multiple coverage goals, the paper addresses the problem of finding the smallest possible test suite. The authors prove that finding the absolute minimum number of tests (Minimal Number Test Generation, MNTG) or the minimum total length (Minimal Length Test Generation, MLTG) is NP-complete, linking it to the classic Hitting Set problem. To address this, they propose a greedy heuristic algorithm that iteratively selects uncovered goals and prunes redundant witnesses, providing a practical path to automated test generation.

Conclusion and Future Work

This research bridges the gap between formal verification and software testing by repurposing model checkers to find witnesses rather than just counterexamples. While symbolic model checking helps mitigate state explosion, challenges remain for very large systems and non-deterministic models. Future work suggests that the $\mu$-calculus might provide a more uniform framework for characterizing all coverage criteria, and further engineering is needed to integrate these theories into industrial toolchains for languages like SDL or Statecharts.

Summary updated

Abstract

This paper presents a theory of test coverage and generation from specifications written in EFSMs. We investigate a family of coverage criteria based on the information of control flow and data flow and characterize them in the branching time temporal logic CTL. We discuss the complexity of minimal cost test generation and describe a method for automatic test generation which employs the capability of model checkers to construct counterexamples. Our approach extends the range of applications of model checking from formal verification of finite state systems to test generation from finite state systems.
BibTeX
@inproceedings{hong2002temporal,
  author = {Hyoung Seok Hong and Insup Lee and Oleg Sokolsky and Hasan Ural},
  title = {{A Temporal Logic Based Theory of Test Coverage and Generation}},
  booktitle = {TACAS},
  year = {2002},
  url = {https://openreview.net/forum?id=Pq_KAUDQgh},
}
Figure