Citation
Yi-Chin Wu, Stephane Lafortune. "Synthesis of Optimal Insertion Functions for Opacity Enforcement". IEEE Transactions on Automatic Control, 2014.

Abstract
Our prior work has studied the enforcement of opacity security properties using insertion functions. Given a system that is not opaque, the so-called All Insertion Structure (AIS) is a game structure, played by the system and the insertion function, that embeds all valid insertion functions. In this paper, we first propose a more compact AIS that can be constructed with lower computational complexity. We then introduce the maximum total cost and the maximum mean cost, and use them as quantitative objectives to solve for optimal insertion functions. Specifically, we first determine if an insertion function with a finite total cost exists. If such an insertion function exists, we synthesize an optimal total-cost insertion function. Otherwise, we construct an optimal mean- cost insertion function. In either case, we find an optimal strategy for the insertion function player on the AIS, with respect to the corresponding cost objective. The algorithmic procedures are adapted from results developed for minimax games and mean payoff games. The resulting optimal strategy is represented as a subgraph of the AIS that consists of all the system actions and the optimal insertion actions. Finally, we use this subgraph to synthesize an optimal insertion function that is encoded as an I/O automaton.

Electronic downloads

• https://www.src.org/library/publication/p071802/. (Link to paper on SRC website.)
• http://dx.doi.org/10.1109/TAC.2015.2440632

• HTML

  Yi-Chin Wu, Stephane Lafortune. <a
  href="http://www.terraswarm.org/pubs/356.html"
  >Synthesis of Optimal Insertion Functions for Opacity
  Enforcement</a>, <i>IEEE Transactions on
  Automatic Control</i>,  2014.

• Plain text

  Yi-Chin Wu, Stephane Lafortune. "Synthesis of Optimal
  Insertion Functions for Opacity Enforcement".
  <i>IEEE Transactions on Automatic Control</i>, 
  2014.

• BibTeX

  @article{WuLafortune14_SynthesisOfOptimalInsertionFunctionsForOpacityEnforcement,
      author = {Yi-Chin Wu and Stephane Lafortune},
      title = {Synthesis of Optimal Insertion Functions for
                Opacity Enforcement},
      journal = {IEEE Transactions on Automatic Control},
      year = {2014},
      abstract = {Our prior work has studied the enforcement of
                opacity security properties using insertion
                functions. Given a system that is not opaque, the
                so-called All Insertion Structure (AIS) is a game
                structure, played by the system and the insertion
                function, that embeds all valid insertion
                functions. In this paper, we first propose a more
                compact AIS that can be constructed with lower
                computational complexity. We then introduce the
                maximum total cost and the maximum mean cost, and
                use them as quantitative objectives to solve for
                optimal insertion functions. Specifically, we
                first determine if an insertion function with a
                finite total cost exists. If such an insertion
                function exists, we synthesize an optimal
                total-cost insertion function. Otherwise, we
                construct an optimal mean- cost insertion
                function. In either case, we find an optimal
                strategy for the insertion function player on the
                AIS, with respect to the corresponding cost
                objective. The algorithmic procedures are adapted
                from results developed for minimax games and mean
                payoff games. The resulting optimal strategy is
                represented as a subgraph of the AIS that consists
                of all the system actions and the optimal
                insertion actions. Finally, we use this subgraph
                to synthesize an optimal insertion function that
                is encoded as an I/O automaton.},
      URL = {http://terraswarm.org/pubs/356.html}
  }
  

Posted by Yi-Chin Wu on 2 Sep 2014.
Groups: services