Sampling-based Decentralized Monitoring for Networked Embedded Systems

Ezio Bartocci

TL;DR

This paper addresses the challenge of real-time decentralized monitoring in networked embedded systems by proposing a timed model in UPPAAL. It tackles the issue of inconsistent sampling times between components, a limitation of previous theoretical work, and demonstrates its approach with a case study on a hardware platform.

What Problem Does This Paper Address?

Modern embedded systems, found in everything from cars to air traffic control, are inherently distributed. Verifying their correct behavior at runtime often requires monitoring their global properties. Traditional centralized monitoring, where all data is sent to a single point, is often infeasible due to communication overhead and component limitations. Decentralized monitoring (DM) offers an alternative, where each component infers global properties from its local observations.

While theoretical work exists for decentralized LTL (Linear Temporal Logic) monitoring, a key assumption has been that computation and communication are instantaneous. This is unrealistic for real-time systems. The critical challenge this paper addresses is how to ensure that local traces, collected at different sampling times across distributed components, are consistent enough to accurately monitor global properties. Without synchronized or consistent sampling, local inferences can be misleading, leading to incorrect property satisfaction or violation detection.

Methods

The core contribution of this paper is the development of a timed model for decentralized monitoring using UPPAAL, a tool for modeling and analyzing real-time systems based on timed automata. This timed model explicitly incorporates the time aspects of the system, including:

  • Sampling time and granularity: The model accounts for how often local events are sampled.
  • Communication delays: The time taken to send messages between components is considered.
  • Worst-Case Execution Time (WCET): The maximum time required for tasks like sampling, monitoring, and communication is factored in.

The authors leverage timed automata to represent each component's behavior, including its states, transitions, clocks (for time tracking), and invariants (conditions that must hold in a state). They model the network using broadcast channels (synch and send) to simulate multicast communication. The model also includes a fault parameter to represent fault-tolerance mechanisms like N-modular redundancy (NMR).

The paper then uses this UPPAAL model to verify several important properties:

  • Liveness: Ensuring that certain states are eventually reached.
  • Synchronous Sampling: Guaranteeing that all components sample local events at the same time.
  • Sampling Frequency: Analyzing the rate at which samples are collected.

Datasets

Not discussed in the paper. The paper focuses on modeling and theoretical verification rather than empirical evaluation on large datasets.

Key Insights and Ideas

  • The critical role of time in decentralized monitoring: The paper strongly emphasizes that ignoring time in decentralized monitoring leads to unrealistic assumptions and potential inaccuracies in real-time systems.
  • Timed automata as a powerful modeling tool: UPPAAL and timed automata provide a formal framework to capture the complex interplay of discrete events and continuous time in distributed systems, enabling rigorous analysis.
  • Synchronous sampling is achievable and crucial: The model demonstrates that synchronous sampling across distributed components is a verifiable property, which is essential for consistent decentralized monitoring.
  • WCET as a key parameter for synchronization: The paper highlights how WCET values directly influence the timing behavior and synchronization of components, making their accurate estimation vital.

Key Results

  • The paper successfully models a decentralized monitoring scenario for networked embedded systems using UPPAAL, incorporating realistic timing constraints.
  • They formally verify properties like liveness and synchronous sampling, demonstrating that their timed model can capture and analyze these crucial aspects.
  • A sampling frequency function is derived, showing how it depends on various WCET parameters and the number of components.
  • A case study on a hardware platform with four micro-controllers is presented, implementing both automata-based and formula-progression monitoring approaches. This case study validates the model's applicability to real-world scenarios.

Limitations and Future Work

  • Synchronous communication overhead: The authors acknowledge that synchronous communication can become computationally expensive as the number of components increases.
  • WCET estimation: Measuring WCET is generally an intractable problem (equivalent to the halting problem). While they discuss methods for over-approximation, precise WCET determination remains a challenge.
  • Future Work:
    • Developing an asynchronous decentralized monitoring model based on Lamport's notion of global time to address the cost of synchronous communication.
  • Extending the monitoring capabilities to handle more sophisticated temporal logics, such as Metric Interval Temporal Logic (MITL), which deals with dense-time properties.

Summary updated

Abstract

:Decentralized monitoring (DM) refers to a monitoring technique, where each component must infer, based on a set of partial observations if the global property is satisfied. Our work is inspired by the theoretical results presented by Baurer and Falcone at FM 2012, where the authors introduced an algorithm for distributing and monitoring LTL formulae, such that satisfaction or violation of specifications can be detected by local monitors alone. However, their work is based on the main assumption that neither the computation nor communication take time, hence it does not take into account how to set a sampling time among the components such that their local traces are consistent. In this work we provide a timed model in UPPAAL and we show a case study on a networked embedded systems board.
BibTeX
@inproceedings{bartocci2013sampling,
  author = {Ezio Bartocci},
  title = {{Sampling-based Decentralized Monitoring for Networked Embedded Systems}},
  booktitle = {HAS},
  year = {2013},
  url = {https://openreview.net/forum?id=2jF5sT0C4T},
}

Loading related content...

Figure