Monitoring Assumptions in Assume-Guarantee Contracts

Oleg Sokolsky, Teng Zhang, Insup Lee, Michael McDougall

TL;DR

When verifying software components using assume-guarantee contracts, we often rely on runtime monitors to ensure the environment behaves as expected. This paper reveals a critical "semantic gap" introduced by black-box I/O libraries (like standard C library functions) that can blind these monitors to environment violations, and proposes a method to construct and verify code-level monitors that account for these I/O effects.

What Problem Does This Paper Address?

In component-based software engineering, developers often use assume-guarantee contracts ($A \implies G$) to verify components in isolation. This contract states: if the environment satisfies an assumption $A$ (e.g., "inputs will always be sorted by timestamp"), then the component promises to fulfill a guarantee $G$.

While the guarantee can be verified before deployment, the assumption depends entirely on the deployment environment and must be checked at runtime using a monitor. Typically, developers build these monitors by instrumenting the component's application code.

However, application code rarely interacts with the raw environment directly; it uses I/O libraries (like scanf or getline). Because these libraries are often treated as black boxes, they can alter or filter the data stream—for instance, silently consuming whitespaces or newlines. This creates a discrepancy between the contract assumption (what the system specification expects) and the internal assumption (what the code actually observes). If a monitor is built purely from the code's perspective without accounting for these I/O transformations, it might miss critical environment violations or raise false alarms.

Methods

The authors propose a framework to extract, enrich, and verify runtime monitors against contract assumptions:

  1. Monitor Skeleton Extraction: Using static analysis, the framework analyzes the application's control flow graph. It replaces I/O API calls with basic type-labeled transitions (e.g., int, float) to create a baseline state machine skeleton.
  2. Adding Semantic Constraints: Because code structure alone doesn't capture all rules, developers manually enrich this skeleton with state variables, guards, and updates to form an Extended Finite State Machine (EFSM) representing the internal assumption.
  3. Modeling I/O API Effects: The authors explicitly model how different I/O utilities transform data. For example, a scanf call is modeled with self-loops that allow it to skip newlines, whereas a getline pattern is modeled to explicitly expect a newline terminator.
  4. Pre-deployment Verification: To ensure correctness, they perform a language inclusion check between the contract assumption EFSM and the newly constructed internal assumption EFSM. This ensures the monitor won't trigger false alarms on valid inputs.
Figure 2: Extracting internal assumption from code: (a) state machine skeleton (b) EFSM with semantic constraints

Datasets

Not discussed in the paper. The authors evaluate their approach qualitatively using a simple GPS travel distance calculator case study.

Key Insights and Ideas

  • The I/O API Dictates Detection Power: The choice of your I/O library fundamentally limits what your runtime monitor can see. If your library hides newlines, your monitor is structurally blind to line-break violations.
  • Structural Blindness: Because these monitors are extracted directly from the application code, they cannot detect structural violations from the code's own perspective (i.e., the monitor won't encounter an "unexpected" event because the code itself doesn't have a path to read it). It can only detect violations of semantic constraints (like a latitude value exceeding 90 degrees).
  • Accidental Robustness vs. Vulnerability: Code can be robust to certain environmental shifts purely because of its I/O library, while being dangerously vulnerable to others.

Key Results

The paper illustrates its findings by comparing two different implementations of the GPS distance calculator:

  • Implementation 1 (scanf): This version is robust to missing line breaks because scanf treats newlines as generic whitespace. However, if the environment introduces an unexpected extra data field (e.g., adding an altitude reading), scanf misaligns all subsequent reads, causing a cascade of semantic violations that the monitor promptly catches.
  • Implementation 2 (getline + sscanf): This version is robust to extra data fields because sscanf simply ignores unlisted fields at the end of a line. However, it is highly vulnerable to missing line breaks; if newlines are removed, it reads multiple data points as a single line, resulting in silent data loss and incorrect calculations without ever triggering the monitor.

Limitations and Future Work

  • Manual Enrichment: Transforming the raw code skeleton into a semantic EFSM is currently a manual process, as many constraints are implicit and not explicitly written in the source code.
  • Simplified Type Modeling: The framework currently only handles basic types (int, float) and does not account for implicit type conversions performed by I/O routines.
  • Quantifying the Semantic Gap: The authors note that future work will focus on automatically calculating the exact language difference between the contract assumption and the internal assumption to explicitly map out which environmental deviations will be missed by the monitor.

Summary updated

Abstract

Pre-deployment verification of software components with respect to behavioral specifications in the assume-guarantee form does not, in general, guarantee absence of errors at run time. This is because assumptions about the environment cannot be discharged until the environment is fixed. An intuitive approach is to complement pre-deployment verification of guarantees, up to the assumptions, with post-deployment monitoring of environment behavior to check that the assumptions are satisfied at run time. Such a monitor is typically implemented by instrumenting the application code of the component. An additional challenge for the monitoring step is that environment behaviors are typically obtained through an I/O library, which may alter the component's view of the input format. This transformation requires us to introduce a second pre-deployment verification step to ensure that alarms raised by the monitor would indeed correspond to violations of the environment assumptions. In this paper, we describe an approach for constructing monitors and verifying them against the component assumption. We also discuss limitations of instrumentation-based monitoring and potential ways to overcome it.
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