Comparing the Notions of Opacity for Discete-Event Systems

Jiří Balun, Tomáš Masopust

Opacity is an information flow property characterizing whether a system reveals its secret to a passive observer. Several notions of opacity have been introduced in the literature. We study the notions of language-based opacity, current-state opacity, initial-state opacity, initial-and-final-state opacity, K-step opacity, and infinite-step opacity. Comparing the notions is a natural question that has been investigated and summarized by Wu and Lafortune, who provided transformations among current-state opacity, initial-and-final-state opacity, and language-based opacity, and, for prefix-closed languages, also between language-based opacity and initial-state opacity. We extend these results by showing that all the discussed notions of opacity are transformable to each other. The transformations are computable in polynomial time, preserve the number of observable events, and determinism. Besides a deeper insight into the differences among the notions, the transformations have applications in complexity results. Namely, we improve the algorithmic complexity of deciding language-based opacity, infinite-step opacity, and K-step opacity, and provide a complete and improved complexity picture of the verification of the discussed notions of opacity.

Knowledge Graph



Sign up or login to leave a comment