[en] We consider the problem of quantifying information flow in interactive systems, modelled as finite-state transducers in the style of Goguen and Meseguer. Our main result is that if the system is deterministic then the information flow is either logarithmic or linear, and there is a polynomial-time algorithm to distinguish the two cases and compute the rate of logarithmic flow. To achieve this we first extend the theory of information leakage through channels to the case of interactive systems, and establish a number of results which greatly simplify computation. We then show that for deterministic systems the information flow corresponds to the growth rate of antichains inside a certain regular language, a property called the width of the language. In a companion work we have shown that there is a dichotomy between polynomial and exponential antichain growth, and a polynomial time algorithm to distinguish the two cases and to compute the order of polynomial growth. We observe that these two cases correspond to logarithmic and linear information flow respectively. Finally, we formulate several attractive open problems, covering the cases of probabilistic systems, systems with more than two users and nondeterministic systems where the nondeterminism is assumed to be innocent rather than demonic.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
MESTEL, David ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Co-auteurs externes :
no
Langue du document :
Anglais
Titre :
Quantifying information flow in interactive systems
Date de publication/diffusion :
2019
Nom de la manifestation :
32nd IEEE Symposium on Computer Security Foundations (CSF 2019)
J. A. Goguen and J. Meseguer, "Security policies and security models," in 1982 IEEE Symposium on Security and Privacy. IEEE, 1982, pp. 11-20.
D. Mestel, "Widths of regular and context-free languages," CoRR, vol. abs/1709.08696, 2018. [Online]. Available: http://arxiv.org/abs/1709. 08696
P. Y. A. Ryan, J. McLean, J. Millen, and V. Gligor, "Non-interference, who needs it?" in Proc. 14th IEEE Computer Security Foundations Workshop (CSFW '01), 2001, pp. 237-238.
C. E. Shannon, "A mathematical theory of communication," The Bell System Technical Journal, vol. 27, no. 3, pp. 379-423, July 1948.
G. Smith, "On the foundations of quantitative information flow," in Proc. 12th Int. Conf. on Foundations of Software Science and Computational Structures (FOSSACS '09), 2009, pp. 288-302.
M. S. Alvim, K. Chatzikokolakis, C. Palamidessi, and G. Smith, "Measuring information leakage using generalized gain functions," in Proc. 25th IEEE Computer Security Foundations Symposium (CSF '12), June 2012, pp. 265-279.
C. Dwork, "Differential privacy," in Proc. 33rd International Conference on Automata, Languages and Programming (ICALP '06), 2006, pp. 1-12.
M. S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and G. Smith, "Additive and multiplicative notions of leakage, and their capacities," in Proc. 27th IEEE Computer Security Foundations Symposium (CSF '14), July 2014, pp. 308-322.
C. Braun, K. Chatzikokolakis, and C. Palamidessi, "Quantitative notions of leakage for one-try attacks," in Proc. 25th Int. Conf. on Mathematical Foundations of Programming Semantics (MFPS '09), 2009, pp. 75-91.
R. van der Meyden and C. Zhang, "A comparison of semantic models for noninterference," Theoretical Computer Science, vol. 411, no. 47, pp. 4123-4147, 2010.
D. Clark and S. Hunt, "Non-interference for deterministic interactive programs," in Formal Aspects of Security and Trust (FAST 2008), April 2009, pp. 50-66.
G. H. Mealy, "A method for synthesizing sequential circuits," Bell Labs Technical Journal, vol. 34, no. 5, pp. 1045-1079, 1955.
A. Roscoe, J. Woodcock, and L. Wulf, "Non-interference through determinism," in Proc. 3rd European Symposium on Research in Computer Security (ESORICS '94), 1994, pp. 31-53.
R. P. Dilworth, "A decomposition theorem for partially ordered sets," Annals of Mathematics, pp. 161-166, 1950.
D. Mestel, "Quantifying information flow," Ph.D. dissertation, University of Oxford, 2018.
P. Mardziel, M. S. Alvim, M. Hicks, and M. R. Clarkson, "Quantifying information flow for dynamic secrets," in 2014 IEEE Symposium on Security and Privacy, May 2014, pp. 540-555.
B. Köpf and D. Basin, "An information-theoretic model for adaptive side-channel attacks," in Proc. 14th ACM Conference on Computer and Communications Security (CCS '07), 2007, pp. 286-296.
M. Boreale and F. Pampaloni, "Quantitative information flow under generic leakage functions and adaptive adversaries," Logical Methods in Computer Science, vol. 11, no. 4, 2015.
M. Boreale, F. Pampaloni, and M. Paolini, "Asymptotic information leakage under one-try attacks," in Proc. 14th Int. Conf. on Foundations of Software Science and Computational Structures (FOSSACS '11), 2011, pp. 396-410.
M. E. Andrés, C. Palamidessi, P. van Rossum, and G. Smith, "Computing the leakage of information-hiding systems," in Proc. 16th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS '10), 2010, pp. 373-389.
M. S. Alvim, M. E. Andrés, and C. Palamidessi, "Quantitative information flow in interactive systems," Journal of Computer Security, vol. 20, no. 1, pp. 3-50, Jan. 2012.
Y. Kawamoto and T. Given-Wilson, "Quantitative information flow for scheduler-dependent systems," in Proc. 13th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL '15), 2015, pp. 48-62.
