Keywords: Diagnosis, fault tolerance, observability, ..., Verification, validation, test
Abstract: In the authors' previous work, two intersection-based architectures, named the normal-state-estimator-intersection-based architecture (N-SEI architecture) and the failure-state-estimator-intersection-based architecture (F-SEI architecture), were developed for decentralized diagnosis of discrete event systems. Then, the corresponding notion of codiagnosability was introduced for each of these architectures. These two notions of codiagnosability are incomparable with each other. In addition, they are incomparable with inference diagnosability for the inference-based architecture. In this paper, for each of the N-SEI and F-SEI architectures, a method for verifying the corresponding notion of codiagnosability effectively is presented.

Keywords: Diagnosis, fault tolerance, observability, ..., Identification
Abstract: The classical methods of fault diagnosis assume that the fault-free and the post-fault system behavior dynamics are known, which can be difficult to be obtained for complex and large systems. To overcome this problem, techniques for system identification with the objective of fault detection have been proposed in the literature. In this case, the main idea consists in computing a monolithic fault-free model by observing the input and output signals of the system controller. However, if the system information is decentralized, then it is necessary to implement a decentralized fault diagnosis architecture. In this paper, we adapt the classical decentralized fault detection architecture, which is based on the a priori knowledge of the complete system model, by considering that the local observation models are not known and are obtained by using identification techniques. We present a practical example to illustrate the proposed method and we show that, in this example, the decentralized fault detection of DES using identified models can be used without reducing significantly the fault detection efficiency.

Keywords: Diagnosis, fault tolerance, observability, ..., Verification, validation, test
Abstract: Recently, the problem of fault diagnosability of discrete-event systems has been extended to the class of time-interval discrete-event systems, a class of discrete-event systems in which a unique clock controls the time elapsed between event occurrences. The model formalism used to deal with systems whose behavior is expressed in terms of regular languages is the so-called time-interval automaton. In a previous work, we proposed a diagnosability verification method inspired by the diagnoser proposed by Sampath et al. (1995), therefore relying on the search for indeterminate cycles in the diagnoser and corresponding cycles of Y-certain and N-certain states, in the labeled automaton; therefore, such a diagnoser does not carry enough information to ascertain if an observed cycle of uncertain states is an indeterminate cycle. In addition, the computational complexity of finding cycles is worse than exponential in the number of states, which makes this previous approach rather limited. In this paper, we propose a new diagnoser-based test automaton to verify the diagnosability of time-interval discrete-event systems inspired by that proposed in Viana and Basilio (2019) which relies on the search for strongly connected components (SCC) and, thus, with computational cost linear in the number of the test automaton transitions in the worst case.

Keywords: Modeling tools: Petri nets, automata, ..., Diagnosis, fault tolerance, observability, ..., Performance evaluation, optimization
Abstract: This paper deals with the performance analysis of fault detectors for timed discrete event systems. Timed fault patterns that describe the faulty behaviours and logical alarm patterns that describe the detection function are explicitly separated from the system. The transformation of these components into clock interval automata and the manipulation of such automata thanks to two specific operators lead to the design of a performance analyser. The detection delay from the fault occurrence to its detection by the alarm pattern is computed thanks to the analyser. Such a delay is evaluated as a timed interval and measured in number of ticks in the clock interval automata.

Keywords: Modeling tools: Petri nets, automata, ..., Diagnosis, fault tolerance, observability, ..., Tools
Abstract: Fault diagnosis is a quite demanding research subject, in the literature on discrete event systems, many works explore it considering an event/action abstraction modeling approach, while some works explore it using a state abstraction approach. We propose an approach that considers partial observation of both actions and atomic propositions. To deal with this new approach, we redefine the equivalence of traces with respect to stuttering, considering partial observation of actions and atomic propositions. With this new definition of stuttering, we provide a new diagnosability definition. Finally, we provide an on-the-fly model-checking algorithm to verify the diagnosability using a unique LTL formula.

Keywords: Diagnosis, fault tolerance, observability, ..., Modeling tools: Petri nets, automata, ..., Algebraic approaches: process algebras, max/plus-algebra, ...
Abstract: In this paper, we propose a polynomial algorithm for conducting 𝐾-diagnosability analysis on both bounded and unbounded labeled Petri nets. More specifically, we formulate a sufficient condition for 𝐾-diagnosability by addressing the relaxation (in R) of an Integer Linear Programming (ILP) problem defined on a compacted horizon. In addition, if the model is 𝐾-diagnosable, the technique provides a value 𝐾𝑟𝑒𝑙𝑎𝑥, potentially lower than 𝐾, that ensures (𝐾𝑟𝑒𝑙𝑎𝑥-)diagnosability. To assess the performance and efficiency of the developed method, a Petri net model of a railway benchmark is investigated.

Keywords: Modeling tools: Petri nets, automata, ..., Diagnosis, fault tolerance, observability, ..., Cyber-security
Abstract: Coupled discrete event system have subsystems that share a common transition are subject to model deviation due to wear and tear of subsystem physical components. A fault due to model deviation can result in a fault in a corresponding physical system. Silent faults are faults that can propagate from one subsystem to another due to faults that are modeled as unobservable events. In this work, we investigate the problem of modeling silent faults in coupled discrete event systems with model deviations. Our goal is to introduce properties for subsystem to prevent the propagation of a silent fault. First, we provide a formal definition of deviation for coupled discrete event systems. Then, we provide the sufficient properties for deviation safety of the coupled discrete event system. Finally, using a case study, we show how using these properties can help a designer mitigate the occurrence of silent faults in cyber physical systems.

Keywords: Diagnosis, fault tolerance, observability, ..., Opacity, Cyber-security
Abstract: We investigate the diagnosability verification problem in the framework of discrete- event systems. Most of the existing works on this topic assume that faults are related to the internal behaviors of the system such as occurrences of particular events. In this work, motivated by information-flow security considerations, we model faults as some critical information leakages of the system to an intruder, which may have different observations from the system user. Specifically, we say that a fault occurs if the intruder knows that the system has passed by a secret state. We present a formal notion called epistemic diagnosability to capture whether or not the system user can always detect, based on its own observation, the critical information leakage to an intruder within a bounded delay. We show that this new notion subsumes the standard notion of event-based diagnosability. Furthermore, an effective algorithm is provided to verify this new notion.

Keywords: Cyber-security, Supervisory Control Theory, Diagnosis, fault tolerance, observability, ...
Abstract: In cyber-physical systems, due to attacks in the network, the controlled system may no longer be safe. This paper introduces a novel "Detection-Protection" (DP) mechanism for discrete-event systems to mitigate and prevent attacks. The DPM consists of a primary supervisor, a set of backup supervisors, and a decision module. Depending on the signals from the decision module, the active supervisor shifts from the primary supervisor to a backup supervisor that is resilient to attacks. We show that many existing attack prevention and mitigation strategies can be formulated within such a framework. Then, as an initial investigation, we consider only actuator enablement (AE) attacks and a specific DPM with only two supervisors. We assume that the primary supervisor and the decision module are given. Our goal is to synthesize an optimal backup supervisor that guarantees the plant's safety in the presence of AE-attacks. A method is proposed to synthesize the optimal backup supervisor.

Keywords: Cyber-security, Modeling tools: Petri nets, automata, ...
Abstract: This work addresses the problem of cyber attack synthesis in discrete event systems modeled by finite state automata. A malicious attacker may modify an observation outputted from the considered system to confuse an operator who receives either the original observation or the corrupted observation of the system. Particularly, we assume that the attacker has fewer observable events than the operator, resulting in an asymmetric observation setting. This means that the attacker can only deduce the state estimation of the system based on its own observable events, not the observable event set of the system. A relation is defined as a pair of state estimations consistent with the original observation and corrupted observation from the attacker’s perspective. A potentially harmful relation implies that the operator is confused in estimating the given critical states. This work aims to synthesize an attack to establish a potentially harmful relation while maintaining stealthiness. The attack synthesis problem is then considered as a two-player game structure between the operator and the attacker. Finally, an attack graph is constructed to illustrate all possible attack scenarios, and examples are provided to demonstrate the proposed attack strategy.

Keywords: Supervisory Control Theory, Cyber-security
Abstract: Sensor deception is a class of attacks in control systems where an attacker manipulates sensor readings to cause damage to the system. In this work, we investigate the problem of designing better and faster intrusion detection systems against sensor deception attacks. We study this problem in the context of stochastic supervisory control theory using the notion of epsilon-safety detection. The epsilon-safety notion ensures that a sensor deception attack can be detected due to changes in the probabilistic behavior in the control system, i.e., it leaves a probability footprint.

Keywords: Cyber-security, Supervisory Control Theory, Diagnosis, fault tolerance, observability, ...
Abstract: The connectivity requirements brought by Industry 4.0 pose new challenges for cyber-physical systems (CPS), such as the strengthening of their resilience against cyberattacks. In this paper, we use the discrete event systems (DES) formalism to develop an approach that aims to protect CPS from covert actuator attacks using event permutation maps. In this approach, properly selected controllable events are permuted on the plant's site so that attacks on actuators do not have the impact on the plant as expected by the intruder and unsafe states are avoided. Furthermore, a property termed AE-protectability is presented to characterize the necessary and sufficient conditions for the system to be protected against such attacks through event permutations. The proposed approach is applied to a case study where the identification of the attack is done without causing damage while maintaining the integrity of the system.

Keywords: Modeling tools: Petri nets, automata, ...
Abstract: This paper is about the representations of distributed timed discrete event systems with synchronisation events and time window constraints. A subclass of T-time Petri nets with time interval constraints and specific time semantics is first recalled as a reference model for the considered systems. Such a model is first reformulated according to distributed automata with time intervals, then it is transformed to clock interval automata that are manipulated as logical tick automata. A synchronous composition of such automata is then defined and we provide conditions such that the result of this composition abstracts the timed language of the original T-time Petri net.

Keywords: Modeling tools: Petri nets, automata, ..., Performance evaluation, optimization, Verification, validation, test
Abstract: This paper studies a class of problems in which we are given the model of a system, with an unknown (or partially known) initial state, and the goal is to apply a carefully chosen sequence of inputs so that, based on the observations (outputs) that are generated, one can determine exactly the current state of the system. The sequence of control inputs is adaptive in the sense that each input is chosen based on the sequence of outputs observed so far and the sequence of inputs previously applied. The main solution for this type of problems involves current-state estimation along with a game structure that tracks the interleaving of control actions and system responses. The ability to determine exactly the current state of the system can be key for a variety of tasks, such as taking special actions (e.g., resetting the system) or supervisory control strategies that aim at achieving various objectives (e.g., avoiding deadlocks).

Keywords: Modeling tools: Petri nets, automata, ..., Supervisory Control Theory
Abstract: In control engineering and computer science, different formalisms are used for the specification and subsequent analysis of timed extensions of discrete event systems. In this paper, the expressivity of timed discrete event systems and that of timed automata are compared for the purpose of modeling of discrete event systems involving time aspects. A behavior-preserving transformation from timed discrete event systems to timed automata is provided, and it is shown that a similar transformation from timed automata to timed discrete event systems is not possible under the assumption that the event sets of the system modeled remains the same.

Keywords: Verification, validation, test, Modeling tools: Petri nets, automata, ...
Abstract: Bisimulation is a powerful abstraction method, which can be used to perform model reduction, especially for modular transition systems. A unified formulation of strong, weak, stuttering, and branching bisimulation is presented. An ambiguity in branching bisimulation is also highlighted, and an equivalent reformulation is proposed where the ambiguity is avoided. A transitive and therefore an equivalence relation is also shown for the alternative formulation. A block transition-based description that is more natural from a model reduction perspective is also shown to be equivalent to the original relation-based bisimulations. All bisimulation formulations are based on general transition system models, which means that systems both including state and transition labels are handled in a unified way.

Keywords: Diagnosis, fault tolerance, observability, ..., Tools, Applications
Abstract: In the context of discrete-event systems (DES), the terms detection and diagnosis refer to two distinct stages of handling faults and anomalies. Both steps are critical for ensuring the reliable and safe operation of complex systems. In this paper, we propose the use of autoencoders for fault detection in an automated production system with sensors and actuators delivering discrete binary signals that can be modeled as DES. We train an autoencoder exclusively on data representing normal behavior. The model learns to encode typical patterns and reconstruct input data with low loss. A predetermined threshold, determined by the characteristics of the training data, is set for the reconstruction error. During normal behavior, the autoencoder is expected to achieve low reconstruction error below this threshold. When a fault occurs, the autoencoder strives to accurately reconstruct faulty data, leading to a higher error. The detection of a reconstruction error exceeding the threshold signals a potential fault in the system. The results of applying our method to the Factory IO software sorting system demonstrate the significant contribution and the interest of this method for detecting faults.

Keywords: Opacity, Verification, validation, test, Performance evaluation, optimization
Abstract: Motivated by the increasing interest of the Discrete Event Systems (DES) community in the theory of Boolean networks (BNs), this work undertakes a prototypical investigation of the notion of opacity in the BN modeling framework. More specifically, we (i) adapt a particular version of this concept to the BN semantics and dynamics; (ii) provide an algorithm that assesses the resulting opacity concept while taking advantage of the special structure of the BN state spaces; and (iii) develop a methodology for enforcing the sought opacity, in some optimal sense, on BNs that do not possess this property. The closing part of the paper briefly discusses how this prototypical study can be extended to other versions of opacity studied by the DES community.

Keywords: Algebraic approaches: process algebras, max/plus-algebra, ..., Performance evaluation, optimization, Modeling tools: Petri nets, automata, ...
Abstract: This paper addresses the multirobot path planning problem using Petri net (PN) models, integrating insights from linear integer programming with a focus on totally unimodular matrices. Initially, we establish theoretical foundations linking optimal solutions of linear integer problems to their relaxed counterparts. Subsequently, we adapt these findings to robot path planning. The core contribution lies in the introduction of an innovative algorithm designed to iteratively converge on the optimal solution by solving successive continuous linear problems. A key feature of this algorithm is its proven efficiency, which converges to the optimal solution of the integer problem within a theoretically established finite number of iterations. Empirical validation is achieved through the resolution of 300 different path planning scenarios, which include varying numbers of robots, maps, and missions. These cases, solved using both the proposed method and existing techniques, demonstrate the superiority of the proposed method in performance.

Keywords: Discrete approaches for hybrid systems, Modeling tools: Petri nets, automata, ..., Diagnosis, fault tolerance, observability, ...
Abstract: This paper considers a class of timed discrete event systems (DESs) with a single clock. The timing structure is characterized by a timing function and a clock resetting function, where the former restricts transitions to occur when the clock takes a value in a given time interval, and the latter indicates how the clock value is updated upon the occurrence of transitions. Given a set of current discrete states in which the system can be, we assume that no information on the occurrence of events is captured (all such information is destroyed or lost), and only the clock that measures the time is reliable. We propose a state observer, in terms of a deterministic finite automaton, which enables us to compute the set of states in which the system can be at a certain time instant. The proposed observer is the basic step towards the construction of an observer that considers both unobservable and observable evolutions. Thus it can be considered as a first step in solving various problems related to partial observation of timed DESs such as opacity verification, fault diagnosis and diagnosability analysis.

Keywords: Identification, Discrete approaches for hybrid systems
Abstract: System identification to a hybrid automaton is a complex and flourishing research field involving expertise in both continuous dynamics and discrete event system modeling. Current methodologies for hybrid automaton identification predominantly rely on a framework centered around the sequential resolution of local signal processing optimization problems. This paper seeks to enhance the existing framework by introducing a novel step designed to address certain limitations inherent in the non-global optimization aspect of a sequential resolution framework. The proposed approach enables each identification step not only to address its local optimization challenges but also to contribute to the optimization of a global cost function including, model distance, sequential fidelity, and automaton structure.

Keywords: Discrete approaches for hybrid systems, Algebraic approaches: process algebras, max/plus-algebra, ..., Modeling tools: Petri nets, automata, ...
Abstract: The goal of this paper is to advertise the tight links between the theory of Discrete-Event Systems and Path-Complete Lyapunov Functions. These are algebro-combinatorial stability criteria for hybrid systems, whose meta-parameters are an automaton and a template of candidate Lyapunov functions. To do this, we analyse a phenomenon recently observed in the literature, namely the statistical ordering of Path-Complete Lyapunov Functions, which is by far not well understood yet: Path-Complete Lyapunov functions can be endowed with a preorder structure with respect to their performance. It has been recently shown that the preorder corresponding to relative worst case performance can be characterized with tools from automata theory, but the ordering corresponding to statistical relative performance has remained elusive. We advocate for a Discrete-Event Systems approach to this problem and provide preliminary results in this direction.