Comparing the Notions of Opacity for Discrete-Event Systems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F21%3A73608388" target="_blank" >RIV/61989592:15310/21:73608388 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/article/10.1007%2Fs10626-021-00344-2" target="_blank" >https://link.springer.com/article/10.1007%2Fs10626-021-00344-2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10626-021-00344-2" target="_blank" >10.1007/s10626-021-00344-2</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Comparing the Notions of Opacity for Discrete-Event Systems

Popis výsledku v původním jazyce

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. Besides a deeper insight into the differences among the notions, the transformations have applications in complexity results. In particular, the transformations are computable in polynomial time and preserve the number of observable events and determinism, and hence the computational complexities of the verification of the notions coincide. We provide a complete and improved complexity picture of the verification of the discussed notions of opacity, and improve the algorithmic complexity of deciding language-based opacity, infinite-step opacity, and K-step opacity.

Název v anglickém jazyce

Comparing the Notions of Opacity for Discrete-Event Systems

Popis výsledku anglicky

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. Besides a deeper insight into the differences among the notions, the transformations have applications in complexity results. In particular, the transformations are computable in polynomial time and preserve the number of observable events and determinism, and hence the computational complexities of the verification of the notions coincide. We provide a complete and improved complexity picture of the verification of the discussed notions of opacity, and improve the algorithmic complexity of deciding language-based opacity, infinite-step opacity, and K-step opacity.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LTAUSA19098" target="_blank" >LTAUSA19098: Verifikace a řízení síťových diskrétních systémů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS

ISSN

0924-6703

e-ISSN

—

Svazek periodika

31

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

30

Strana od-do

553-582

Kód UT WoS článku

000677919600001

EID výsledku v databázi Scopus

2-s2.0-85111379645