Kuize Zhang

Kuize Zhang

We point out three inaccuracies in paper [M.V. Moreira, T.C. Jesus, and J.C. Basilio. Polynomial time verification of decentralized diagnosability of discrete event systems. IEEE Transactions on Automatic Control, 56(7):1679-1684, July 2011]. First, the authors wrongly claimed that their algorithm for verifying (co-)diagnosability of labeled finite-state automata (LFSAs) did not depend on assumptions. We give an LFSA that is not deadlock-free or divergence-free such that their algorithm cannot correctly verify its diagnosability. Because diagnosability is a special case of co-diagnosability, their algorithm cannot correctly verify co-diagnosability either when LFSAs are not deadlock-free or divergence-free. Second, they wrongly claimed that adding at each dead state an unobservable self-loop can help verifying diagnosability for an LFSA that is not deadlock-free or divergence-free, but this is wrong, because such a modification sometimes changes the diagnosability of an LFSA. Third, they wrongly claimed that their algorithm for verifying co-diagnosability ran in polynomial time. A polynomial-time algorithm unlikely exists, because the problem of verifying co-diagnosability of LFSAs is PSPACE-hard.

Kuize Zhang

In this paper, we formulate a scenario that an agent can never be sure that another agent can uniquely determine the state of a finite-state automaton based on its observations to the automaton at the current and any past time as the property of order-2 bygone-state opacity. Based on our concurrent composition and the classical observer, we derive a tool to verify this property in doubly exponential time. The interest of this result lies in that we extend inference of finite automata from a single agent to two ordered agents.

Kuize Zhang

Discrete-event systems usually consist of discrete states and transitions between them caused by spontaneous occurrences of labelled (aka partially-observed) events. Due to the partially-observed feature, fundamental properties therein could be classified into two categories: state/event-inference-based properties (e.g., strong detectability, diagnosability, and predictability) and state-concealment-based properties (e.g., opacity). Intuitively, the former category describes whether one can use observed output sequences to infer the current and subsequent states, past occurrences of faulty events, or future certain occurrences of faulty events; while the latter describes whether one cannot use observed output sequences to infer whether some secret states have been visited (that is, whether the DES can conceal the status that its secret states have been visited). Over the past two decades these properties were studied separately using different methods. In this review article, for labeled finite-state automata, a unified concurrent-composition method is shown to verify all above inference-based properties and concealment-based properties, resulting in a unified mathematical framework for the two categories of properties. In addition, compared with the previous methods in the literature, the concurrent-composition method does not depend on assumptions and is more efficient.

Xiaoguang Han, Kuize Zhang, Jiahui Zhang et al.

Opacity, as an important property in information-flow security, characterizes the ability of a system to keep some secret information from an intruder. In discrete-event systems, based on a standard setting in which an intruder has the complete knowledge of the system's structure, the standard versions of current-state opacity and initial-state opacity cannot perfectly characterize high-level privacy requirements. To overcome such a limitation, in this paper we propose two stronger versions of opacity in partially-observed discrete-event systems, called \emph{strong current-state opacity} and \emph{strong initial-state opacity}. Strong current-state opacity describes that an intruder never makes for sure whether a system is in a secret state at the current time, that is, if a system satisfies this property, then for each run of the system ended by a secret state, there exists a non-secret run whose observation is the same as that of the previous run. Strong initial-state opacity captures that the visit of a secret state at the initial time cannot be inferred by an intruder at any instant. Specifically, a system is said to be strongly initial-state opaque if for each run starting from a secret state, there exists a non-secret run of the system that has the same observation as the previous run has. To verify these two properties, we propose two information structures using a novel concurrent-composition technique, which has exponential-time complexity $O(|X|^4|Σ_o||Σ_{uo}||Σ|2^{|X|})$, where $|X|$ (resp., $|Σ|$, $|Σ_o|$, $|Σ_{uo}|$) is the number of states (resp., events, observable events, unobservable events) of a system.