Lagrange multipliers and maximum information leakage in different observational models

ABSTRACT

This paper explores two fundamental issues in Language based security. The first is to provide a quantitative definition of information leakage valid in several attacker's models. We consider attackers with different capabilities; the strongest one is able to observe the value of the low variables at each step during the execution of a program; the weakest one can only observe a single low value at some stage of the execution.

We will provide a uniform definition of leakage, based on Information Theory, that will allow us to formalize and prove some intuitive relationships between the amount leaked by the same program in different models.

The second issue is Channel Capacity, which in security terms amounts to answering the questions: given a program and an observational model, what is the maximum amount that the program can leak? And which input distribution causes the maximum leakage?

To answer those questions we will introduce techniques from constrained non-linear optimization, mainly Lagrange multipliers and we will show how they provide a workable solution in all observational models considered. In the simplest setting, i.e. under minimal constraints, we will show that channel capacity is achieved by any input distribution which induces a uniform distribution on the observables.

REFERENCES

• 1: ?hele Boreale: Quantifying Information Leakage in Process Calculi. ICALP (2) 2006: 119--131
• 2: K. Chatzikokolakis, C. Palamidessi, P. Panangaden. Anonymity Proto?ols as Noisy Channels, in: Postpro?eedings of the Symp. on Trustworthy Global Computing, Le?ture Notes in Computer Science, Springer, 2006,
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: David Clark , Sebastian Hunt , Pasquale Malacaria, A static analysis for quantifying information flow in a simple imperative language, Journal of Computer Security, v.15 n.3, p.321-371, August 2007
• 5: David Clark, Sebastian Hunt, Pasquale Mala?aria: Quantified interference for a while language. Electronic Notes in Theoretical Computer Science 112, Page 149--166, Elsevier, 2005
• 6: David Clark, Sebastian Hunt, Pasquale Mala?aria: Quantitative Analysis of the leakage of confidential data.Electronic Notes in Theoretical Computer S?ien?e 59, 2002
• 7: Dorothy Elizabeth Robling Denning, Cryptography and data security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 8: Dorothy E. Denning, A lattice model of secure information flow, Communications of the ACM, v.19 n.5, p.236-243, May 1976 [doi>10.1145/360051.360056]
• 9: Han Chen , Pasquale Malacaria, Quantitative analysis of leakage for multi-threaded programs, Proceedings of the 2007 workshop on Programming languages and analysis for security, June 14-14, 2007, San Diego, California, USA [doi>10.1145/1255329.1255335]
• 10: James W Gray III: Toward a methematical foundataion for information flow security. Pro?. 1991 IEEE Symposium on Security and Privacy. Oakland, California, May 1991.
• 11: S. Kullba?k:Information Theory and Statistics. Dover Publications. 1997.
• 12: Joseph Y. Halpern , Kevin R. O'Neill, Anonymity and information hiding in multiagent systems, Journal of Computer Security, v.13 n.3, p.483-514, May 2005
• 13: J.Heusser and P. Mala?aria: Measuring Insecurity of Programs. Manuscript 2007.
• 14: John M?lean: Security models and information flow. Proc. 1990 IEEE Symposium on Security and Privacy. Oakland, California, May 1990.
• 15: Pasquale Malacaria, Assessing security threats of looping constructs, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 16: Jonathan Millen: Covert Channel capacity. Proc. 1987 IEEE Symposium on Research in Security and Privacy.
• 17: Flemming Nielson , Hanne R. Nielson , Chris Hankin, Principles of Program Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 18: Andrei Sabelfeld and Andrew C. Myers: Language--Based Information--Flow Security. IEEE Journal on Selected Area in Communications, Volume 21, No. 1, January 2003
• 19: Andrei Sabelfeld , David Sands, Probabilistic Noninterference for Multi-Threaded Programs, Proceedings of the 13th IEEE workshop on Computer Security Foundations, p.200, July 03-05, 2000
• 20: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 21: D. G. Weber: Quantitative hookup security for covert channel analysis. Proc. 1988 Workshop on the Foundations of Computer Security, Fanconia, New Hampshire, U.S.A., 1988.
• 22: T. Wittbold:Network of covert channels. Proc. 1990 Workshop on the Foundations of Computer Security, 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Information flow controls

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

General Terms:
Languages, Security, Theory

Keywords:
information theory, lagrange multipliers, security