On Epistemic Properties in Discrete-Event Systems: A Uniform Framework and Its Applications

Xiang Yin (殷翔), Bohan Cui, Ziyue Ma, Shaoyuan Li, Xiang YinarXiv 2024 · DOI · arXiv

Abstract

This paper presents a formal framework for reasoning about nested knowledge in Discrete-Event Systems (DES). By modeling a hierarchy where a high-level agent observes the system to infer the knowledge state of a low-level agent, the authors unify various security and cooperation properties. We provide algorithmic structures for verification, demonstrating that high-order epistemic properties can often be checked with the same computational complexity as standard first-order properties.

Introduction

In Discrete-Event Systems (DES), such as manufacturing lines or robotic swarms, traditional analysis focuses on first-order properties: diagnosability (detecting faults) and opacity (hiding secrets). However, complex interactions require reasoning about "knowing what someone else knows." For instance, in a secure robotic system, it may be necessary to hide not just the robot's location, but also the fact that a base station has successfully localized the robot, preventing an adversary from inferring the system's readiness.

This research addresses the gap in high-order inference by moving from "What is the system doing?" to "What does Agent A think Agent B knows about the system?" This unified framework encompasses concepts like invisible attackers, knowledge security, and tacit cooperation.

The Two-Agent Knowledge Model

The core of the proposed framework is a hierarchical observer model.

The Two-Agent Knowledge Model architecture showing the relationship between the plant, low-level observer, and high-level observer.

As shown in the figure, the system consists of:

  1. Low-level observer ($H_o$): Observes system events to infer the current state (e.g., a system user or primary intruder).
  2. High-level observer ($H_a$): Independently observes the system to infer the knowledge state of the low-level observer.

To verify epistemic properties, the authors developed three algorithmic structures:

  • Double-Estimator: A general approach building an estimator of an estimator, though it faces doubly-exponential complexity.
  • Twin-Estimator: A more efficient construction for specific properties (e.g., certainty of the low-level observer), reducing complexity to a single exponential.
  • State-Pair-Estimator: An optimized version for distinguishability-based properties, focusing on pairs of states the low-level observer might confuse.

Case Study and Results

The framework's utility is demonstrated through synthetic DFA models and a robot path-planning case study.

Robot workspace and corresponding DFA model used to illustrate high-order opacity.

In the robot workspace example, the goal is to ensure "high-order opacity"—preventing an intruder from knowing when a user has successfully localized a robot within specific regions.

Key results include:

  • Verification Efficiency: For a wide class of security properties, verification is PSPACE-complete, matching the complexity of standard first-order opacity. This suggests that adding a layer of nested knowledge does not necessarily make the problem computationally harder in the worst case.
  • Formal Soundness: Rigorous proofs confirm that the Double-Estimator and Twin-Estimator constructions correctly decide epistemic properties.
  • Delayed Knowledge: The framework successfully extends to "Finite Epistemic Diagnosability," where the high-level observer's realization may occur after a finite delay.

Conclusion and Future Work

This work provides a robust foundation for epistemic reasoning in DES. While currently limited to a two-agent hierarchy, it paves the way for multi-agent systems with mutual knowledge. Future research will focus on control synthesis—automatically designing controllers to enforce these properties—and improving scalability through symbolic verification or abstraction techniques to handle larger state spaces.

Summary updated

Abstract

In this paper, we investigate the property verification problem for partially-observed DES from a new perspective. Specifically, we consider the problem setting where the system is observed by two agents independently, each with its own observation. The purpose of the first agent, referred to as the low-level observer, is to infer the actual behavior of the system, while the second, referred to as the high-level observer, aims to infer the knowledge of Agent 1 regarding the system. We present a general notion called the epistemic property capturing the inference from the high-level observer to the low-level observer. A typical instance of this definition is the notion of high-order opacity, which specifies that the intruder does not know that the system knows some critical information. This formalization is very general and supports any user-defined information-state-based knowledge between the two observers. We demonstrate how the general definition of epistemic properties can be applied in different problem settings such as information leakage diagnosis or tactical cooperation without explicit communications. Finally, we provide a systematic approach for the verification of epistemic properties. Particularly, we identify some fragments of epistemic properties that can be verified more efficiently.
BibTeX
@misc{2024epistemic,
  author = {Xiang Yin (殷翔) and Bohan Cui and Ziyue Ma and Shaoyuan Li and Xiang Yin},
  title = {{On Epistemic Properties in Discrete-Event Systems: A Uniform Framework and Its Applications}},
  year = {2024},
  eprint = {2409.06588},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.06588},
}
Figure