A transformational framework for testing and model checking implicit-invocation systems

Hongyu Zhang2004 · DOI

TL;DR

This paper introduces a novel framework that unifies testing and formal model checking for implicit invocation (II) systems. By developing a dedicated language (IIL) and automated transformation tools, it bridges the gap between software artifacts used for testing and those required for model checking, simplifying the verification process for complex event-driven architectures.

What Problem Does This Paper Address?

Verifying and validating large, complex software systems is a growing challenge. Traditional methods like testing and model checking are powerful but often require different, manually created artifacts, leading to a "semantic gap." This gap can introduce errors if the model used for checking doesn't perfectly match the system being tested. Implicit invocation (II) systems, common in event-driven architectures, exacerbate this problem due to their inherent non-determinism, which can lead to overly large models for checking and unpredictable behavior during testing. The authors aim to bridge this gap by providing a unified approach for both testing and model checking II systems.

Methods

The core of the framework is the Implicit Invocation Language (IIL), a domain-specific language designed to express II systems more naturally. IIL simplifies the representation of components, events, event-method bindings, and delivery policies.

The framework employs a transformational approach using the TXL (Transformation Language) system. This involves two key automated transformations:

  1. IIL to Turing Plus: This transformation converts IIL programs into Turing Plus, a concurrent programming language. This allows for the execution and testing of II systems. The Turing Plus implementation models II using explicit event warehouses, a dispatcher, and component event warehouses, with a single thread per component synchronized by a monitor.
  2. IIL to XML: This transformation converts IIL programs into an XML intermediate representation. This XML representation is then further transformed into finite state machines (FSMs) for formal analysis using a standard model checker (Cadence SMV). This process automates the generation of verification artifacts, bridging the gap between the IIL source and the model checker's input.

Datasets

The paper evaluates the framework using three example systems:

  • Set-Counter: A small, illustrative example demonstrating the core features of IIL and the framework.
  • Active Badge Location System (ABLS): A real-world example.
  • Unmanned Vehicle Control System (UVCS): Another real-world example.

These examples are not presented as formal datasets but rather as case studies to demonstrate the framework's effectiveness and the size reduction achieved by using IIL.

Key Insights and Ideas

  • Bridging the Semantic Gap: The most significant insight is the successful automation of the transformation from a high-level, domain-specific language (IIL) to both executable code (Turing Plus) and formal models (XML -> FSM). This directly addresses the manual effort and potential errors associated with bridging the gap between testing and model checking artifacts.
  • Benefits of Domain-Specific Languages: The paper highlights how IIL, by being tailored to II systems, results in significantly smaller and more manageable representations compared to direct implementations in general-purpose languages or verbose intermediate formats like XML.
  • Unified V&V: The framework demonstrates that testing and model checking, often seen as separate activities, can be integrated through a common source language and automated transformations, potentially leading to more robust verification.
  • Synergies between Testing and Model Checking: The authors propose that this integrated approach can reveal synergies, such as using testing to validate model checker results or using model checking to assess test suite coverage.

Key Results

The evaluation shows that IIL programs are substantially smaller than their corresponding Turing Plus implementations and the XML/SMV representations. For instance, the Set-Counter example in IIL is 2KB, while its Turing Plus version is 13KB, and the SMV representation is 24KB – a significant size reduction. Similar trends are observed for ABLS and UVCS. The automatic transformations are shown to preserve the semantics of the II systems.

Limitations and Future Work

Limitations:

  • The paper notes that the initial XML representation development required user interaction, which this paper's approach aims to fully automate.
  • The current model checking approach is limited to LTL properties.

Future Work:

  • Investigating the relationship and synergies between testing and model checking more deeply, including how testing can simplify or optimize model checking, and vice-versa.
  • Exploring temporal logic properties in testing, such as run-time safety analysis.
  • Extending the framework to support more general publish-subscribe systems, including those with dynamic bindings and different concurrency models.
  • Further research into integrating temporal logic properties into the testing effort.

Summary updated

Abstract

With the growing size and complexity of software systems, software verification and validation (V&V) is becoming increasingly important. Model checking and testing are two of the main V&V methods. In this paper, we present a framework that allows for testing and formal modeling and analysis to be combined. More precisely, we describe a framework for model checking and testing implicit invocation software. The framework includes a new programming language - the Implicit-Invocation Language (IIL), and a set of formal rule-based transformation tools that allow automatic generation of executable and formal verification artifacts. We evaluate the framework on several small examples. We hope that our approach will advance the state-of-the-art in V&V for event-based systems. Moreover, we plan on using it to explore the relationship between testing and model checking implicit invocation systems and gain insight into their combined benefits.
BibTeX
@misc{zhang2004transformational,
  author = {Hongyu Zhang},
  title = {{A transformational framework for testing and model checking implicit-invocation systems}},
  year = {2004},
  doi = {10.1049/ic:20040392},
}
Figure