TY - JOUR
T1 - The complexity of synchronous notions of information flow security
AU - Cassez, Franck
AU - van der Meyden, Ron
AU - Zhang, Chenyi
PY - 2016/6/6
Y1 - 2016/6/6
N2 - The paper considers the complexity of verifying that a finite state system satisfies a number of definitions of information flow security. The systems model considered is one in which agents operate synchronously with awareness of the global clock. This enables timing based attacks to be captured, whereas previous work on this topic has dealt primarily with asynchronous systems. Versions of the notions of nondeducibility on inputs, nondeducibility on strategies, and an unwinding based notion are formulated for this model. All three notions are shown to be decidable, and their computational complexity is characterised.
AB - The paper considers the complexity of verifying that a finite state system satisfies a number of definitions of information flow security. The systems model considered is one in which agents operate synchronously with awareness of the global clock. This enables timing based attacks to be captured, whereas previous work on this topic has dealt primarily with asynchronous systems. Versions of the notions of nondeducibility on inputs, nondeducibility on strategies, and an unwinding based notion are formulated for this model. All three notions are shown to be decidable, and their computational complexity is characterised.
KW - Security
KW - Information flow
KW - Computational complexity
UR - http://www.scopus.com/inward/record.url?scp=84977957822&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2016.03.011
DO - 10.1016/j.tcs.2016.03.011
M3 - Article
AN - SCOPUS:84977957822
SN - 0304-3975
VL - 631
SP - 16
EP - 42
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -