Optimal payoff to ensure opacity in Discrete-Event Systems

Abstract

Opacity is a property of systems which guarantees that an outside observer cannot distinguish some behaviour of the system (secrets) from other behaviours (non-secrets). Many companies and government agencies like to make some aspects of their processes opaque to any observer while still needing to reveal some information. To enforce opacity, discrete-event systems have been employed and many algorithms are proposed. One naive way of achieving opacity is to hide everything. However, in many applications this is not possible either due to legal obligations or due to the requirement of sharing as much information as possible with other companies or with the public. Some algorithms have been developed that reveal as much information as possible while keeping a system opaque. However, these algorithms are very computationally complex and they treat all the revealed transitions equally (which might not be a reasonable assumption in real-world applications). Thus, to solve the complexity problem we propose using a dynamic programming approach, which relies on the solution to the longest common subsequence problem. This approach can lower the complexity of the solution at least for some cases (namely, systems with no loops). Secondly, we propose to add utilities for revealing transitions and provide algorithms that enforce weak opacity while guaranteeing a maximum payoff. The correctness of the algorithms are proven and their computational complexities are computed.