Monitoring Assumptions in Assume-Guarantee Contracts

Oleg Sokolsky, Teng Zhang, Insup Lee, Michael McDougall

TL;DR

This paper introduces a method to automatically generate monitors from application source code that verify the assumptions of assume-guarantee contracts at runtime. This approach bridges the gap between static verification and dynamic execution by ensuring that the component's internal view of its environment aligns with the contract's assumptions, even when I/O libraries transform the input.

What Problem Does This Paper Address?

Software components are often specified using assume-guarantee contracts (A ⇒ G), where 'A' represents assumptions about the environment and 'G' is the component's guarantee. While 'G' can be verified statically, 'A' must be checked at runtime, especially in open environments where the environment is not fully known beforehand. A common approach is to complement static verification with runtime monitoring. However, directly monitoring the contract assumption 'A' is challenging because the component interacts with its environment through I/O libraries, which can alter the input format. This transformation creates a "semantic gap" between the contract's assumption and what the application code actually "sees." This paper addresses how to construct monitors that bridge this gap by extracting them directly from the application code and verifying their correctness against the contract assumption.

Methods

The core of the paper's method involves two main steps:

  1. Monitor Skeleton Extraction: The authors leverage static analysis of the component's source code, specifically its control flow graph. Calls to I/O API functions are identified and replaced with "skeleton fragments" representing the data items they consume. This process generates a state machine skeleton.
  2. Internal Assumption EFSM Construction: The skeleton is then augmented with state variables, guards, and updates to form an Extended Finite State Machine (EFSM) representing the "internal assumption." This EFSM captures the semantic constraints of the input as perceived by the application code, taking into account how I/O APIs might transform or obscure certain aspects of the input format (e.g., skipping whitespace).

Crucially, the paper also discusses how to model the effects of I/O APIs, such as scanf (which skips whitespace) and getline/sscanf (which handles input differently), by extending the skeleton fragments. The generated internal assumption EFSM is then verified against the contract's assumption EFSM to ensure that inputs satisfying the contract's assumption do not trigger false alarms in the monitor.

Datasets

Not discussed in the paper. The paper uses a case study of a GPS coordinate calculator for demonstration purposes.

Key Insights and Ideas

  • Bridging the Semantic Gap: The most significant insight is the explicit recognition and handling of the "semantic gap" introduced by I/O libraries. The paper shows that monitors extracted from code can account for these transformations, making them more relevant to the component's actual behavior.
  • Code-Driven Monitoring: Extracting monitors directly from source code offers a more automated and potentially more accurate way to generate runtime checks compared to manually writing them based on requirements alone.
  • I/O API Effects Matter: The paper highlights how different I/O APIs can have vastly different effects on what the application code "sees," leading to components being robust to some input deviations while vulnerable to others. This necessitates careful modeling of API semantics.
  • Two-Tier Verification: The approach involves both extracting the monitor from the code and then verifying this extracted monitor against the original contract assumption. This two-step process is key to ensuring the monitor's correctness.

Key Results

The paper demonstrates its approach using a case study of a simple distance calculator. It shows how different implementations of the same functionality can lead to monitors that are robust to different types of input deviations. For instance, one implementation was robust to the removal of line breaks but vulnerable to the addition of new fields, while another implementation showed the opposite behavior. The paper's method allows for the construction of monitors that can detect deviations and, in some cases, provide a stream of alarms indicating a systematic problem.

Limitations and Future Work

  • Detection Power: The authors acknowledge that monitors extracted from code cannot detect "structural violations" (i.e., when the monitor state machine doesn't expect a certain event). They can only detect violations of semantic constraints. If these constraints are too weak, deviations might go undetected.
  • Characterizing Deviations: A key limitation is the difficulty in precisely characterizing which deviations are harmful and which are not, and which deviations can be detected by the monitor. The paper suggests analyzing the language difference between the component assumption and the internal assumption EFSM to identify undetected deviations.
  • Manual Effort: While the skeleton extraction is automated, adding semantic constraints to form the EFSM is described as a manual process.
  • Future Work: The authors propose automating the characterization of the semantic gap to identify critical deviations missed by the monitor. They also suggest exploring alternative instrumentation strategies, such as instrumenting the I/O library itself, which could provide a more direct view of input data but at a lower level of abstraction.

Summary updated

BibTeX
@inproceedings{sokolsky2016monitoring,
  author = {Oleg Sokolsky and Teng Zhang and Insup Lee and Michael McDougall},
  title = {{Monitoring Assumptions in Assume-Guarantee Contracts}},
  booktitle = {PrePost@IFM},
  year = {2016},
  url = {https://openreview.net/forum?id=3M7MZ-ZQ1BY},
}
Figure