Opacity Issues in Games with Imperfect Information
Résumé
We study in depth the class of games with opacity condition, which are two-player games with imperfect information in which one of the players only has imperfect information, and where the winning condition relies on the information he has along the play. Those games are relevant for security aspects of computing systems: a play is opaque whenever the player who has imperfect information never "knows'' for sure that the current position is one of the distinguished "secret'' positions. We study the problems of deciding the existence of a winning strategy for each player, and we call them the opacity-violate problem and the opacity-guarantee problem. Focusing on the player with perfect information is new in the field of games with imperfect-information because when considering classical winning conditions it amounts to solving the underlying perfect-information game. We establish the EXPTIME-completeness of both above-mentioned problems, showing that our winning condition brings a gap of complexity for the player with perfect information, and we exhibit the relevant opacity-verify problem, which noticeably generalizes approaches considered in the literature for opacity analysis in discrete-event systems. In the case of blindfold games, this problem relates to the two initial ones, yielding the determinacy of blindfold games with opacity condition and their PSPACE-completeness.
Nous étudions en détail la classe des jeux à condition d'opacité, qui sont des jeux à deux joueurs à information imparfaite dans lesquels seul l'un des joueurs n'a pas information parfaite, et où la condition de gain dépend de l'information que celui-ci a au cours du jeu. Ces jeux sont liés à des aspects de sécurité des systèmes informatiques : une partie est opaque si le joueur à information imparfaite ne "sait" jamais avec certitude que la position courante est l'une des positions spéciales dites "secrètes". Nous étudions les problèmes de décision d'existence de stratégie gagnante pour chaque joueur, et nous les appellons opacity-violate problem et opacity-guarantee problem. Le fait de s'intéresser au joueur à information parfaite est nouveau en théorie des jeux à information imparfaite car lorsqu'on considère des conditions de gain classiques cela revient à considérer le jeu à information parfaite sous-jacent. Nous établissons que les deux problèmes sus-mentionnés sont EXPTIME-complets, montrant ainsi que notre condition de gain apporte un saut de complexité pour le joueur à information parfaite, et nous exhibons le problème opacity-verify qui, de manière intéressante, généralise des approches considérées dans la littérature pour l'analyse d'opacité des systèmes à événements discrets. Dans le cas des jeux en aveugle, ce problème se relie aux deux problèmes initiaux, de telle sorte que les jeux en aveugle à condition d'opacité sont déterminés et que les trois problèmes sont PSPACE-complets.
Origine : Fichiers produits par l'(les) auteur(s)