Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-01-22T14:04:32.526Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantification of integrity†

Published online by Cambridge University Press:  10 November 2014

MICHAEL R. CLARKSON  and
FRED B. SCHNEIDER
MICHAEL R. CLARKSON
Affiliation:
Department of Computer Science, Cornell University, Ithaca, NY, 14853, USA Email: [email protected]
FRED B. SCHNEIDER
Affiliation:
Department of Computer Science, Cornell University, Ithaca, NY, 14853, USA Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Three integrity measures are introduced: contamination, channel suppression and program suppression. Contamination is a measure of how much untrusted information reaches trusted outputs; it is the dual of leakage, which is a measure of information-flow confidentiality. Channel suppression is a measure of how much information about inputs to a noisy channel is missing from the channel outputs. And program suppression is a measure of how much information about the correct output of a program is lost because of attacker influence and implementation errors. Program and channel suppression do not have interesting confidentiality duals. As a case study, a quantitative relationship between integrity, confidentiality and database privacy is examined.

Type
Special Issue: Quantitative Information Flow
Information
Mathematical Structures in Computer Science , Volume 25 , Issue 2: Quantitative Information Flow , February 2015 , pp. 207 - 258
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported in part by ONR grant N00014-09-1-0652, AFOSR grant F9550-06-0019, NSF grants 0430161, 0964409 and CCF-0424422 (TRUST), and a gift from Microsoft Corporation.

References

Adámek, J. (1991) Foundations of Coding, John Wiley and Sons, New York.Google Scholar
Alvim, M. S., Chatzikokolakis, K., Degano, P. and Palamidessi, C. (2010) Differential privacy versus quantitative information flow, Technical Report hal-00548214, INRIA. Available at http://hal.inria.fr/hal-00548214/en.Google Scholar
Backes, M. (2005) Quantifying probabilistic information flow in computational reactive systems. In: Proceedings European Symposium on Research in Computer Security 336–354.Google Scholar
Backes, M., Köpf, B. and Rybalchenko, A. (2009) Automated discovery and quantification of information leaks. In: Proceedings IEEE Symposium on Security and Privacy 141–153.Google Scholar
Barthe, G., D'Argenio, P. R. and Rezk, T. (2004) Secure information flow by self-composition. In: Proceedings IEEE Computer Security Foundations Workshop 100–114.Google Scholar
Barthe, G. and Köpf, B. (2011) Information-theoretic bounds for differentially private mechanisms. In: Proceedings IEEE Computer Security Foundations Symposium 191–204.Google Scholar
Bell, D. E. and LaPadula, L. J. (1973) Secure computer systems: Mathematical foundations, Technical Report 2547, Volume I, MITRE Corporation.Google Scholar
Biba, K. (1977) Integrity considerations for secure computer systems, Technical Report MTR-3153, MITRE Corporation.Google Scholar
Birgisson, A., Russo, A. and Sabelfeld, A. (2010) Unifying facets of information integrity. In: Proceedings International Conference on Information Systems Security 48–65.CrossRefGoogle Scholar
Braun, C., Chatzikokolakis, K. and Palamidessi, C. (2008) Compositional methods for information-hiding. In: Proceedings International Conference on Foundations of Software Science and Computation Structures 443–457.Google Scholar
Braun, C., Chatzikokolakis, K. and Palamidessi, C. (2009) Quantitative notions of leakage for one-try attacks. In: Proceedings Conference on Mathematical Foundations of Programming Semantics 75–91.Google Scholar
Chatzikokolakis, K., Palamidessi, C. and Panangaden, P. (2008a) Anonymity protocols as noisy channels. Information and Computation 206 (2–4)378–401.CrossRefGoogle Scholar
Chatzikokolakis, K., Palamidessi, C. and Panangaden, P. (2008b) On the Bayes risk in information-hiding protocols. Journal of Computer Security 16 (5)531–571.Google Scholar
Chen, H. and Malacaria, P. (2009) Quantifying maximal loss of anonymity in protocols. In: ACM Symposium on Information, Computer and Communications Security 206–217.Google Scholar
Chong, S., Liu, J., Myers, A. C., Qi, X., Vikram, K., Zheng, L. and Zheng, X. (2007a) Secure web applications via automatic partitioning. In: Proceedings ACM Symposium on Operating Systems Principles 31–44.Google Scholar
Chong, S., Vikram, K. and Myers, A. C. (2007b) SIF: Enforcing confidentiality and integrity in web applications. In: Proceedings USENIX Security Symposium 1–16.Google Scholar
Clark, D., Hunt, S. and Malacaria, P. (2002) Quantitative analysis of the leakage of confidential data. Electronic Notes in Theoretical Computer Science 59 (3)1–14.Google Scholar
Clark, D., Hunt, S. and Malacaria, P. (2005a) Quantified interference for a while language. Electronic Notes in Theoretical Computer Science 112 149–166.Google Scholar
Clark, D., Hunt, S. and Malacaria, P. (2005b) Quantitative information flow, relations and polymorphic types. Journal of Logic and Computation 18 (2)181–199.Google Scholar
Clark, D., Hunt, S. and Malacaria, P. (2007) A static analysis for quantifying information flow in a simple imperative language. Journal of Computer Security 15 (3)321–371.Google Scholar
Clark, D. D. and Wilson, D. R. (1987) A comparison of commercial and military computer security policies. In: Proceedings IEEE Symposium on Security and Privacy 184–194.Google Scholar
Clarkson, M. R., Myers, A. C. and Schneider, F. B. (2005) Belief in information flow. In: Proceedings IEEE Computer Security Foundations Workshop 31–45.Google Scholar
Clarkson, M. R., Myers, A. C. and Schneider, F. B. (2009) Quantifying information flow with beliefs. Journal of Computer Security 17 (5)655–701.Google Scholar
Clarkson, M. R. and Schneider, F. B. (2010) Quantification of integrity. In: Proceedings IEEE Computer Security Foundations Symposium 28–43.Google Scholar
Commission of the European Communities (1991) Information technology security evaluation criteria: Provisional harmonised criteria. Document COM(90) 314, Version 1.2.Google Scholar
Cover, T. M. and Thomas, J. A. (1991) Elements of Information Theory, John Wiley and Sons, New York.Google Scholar
Dean, J. and Ghemawat, S. (2004) MapReduce: Simplified data processing on large clusters. In: Proceedings USENIX Symposium on Operating System Design and Implementation 137–150.Google Scholar
Denning, D. (1982) Cryptography and Data Security, Addison-Wesley, Reading, Massachusetts.Google Scholar
Dwork, C. (2006) Differential privacy. In: Proceedings International Colloquium on Automata, Languages and Programming 1–12.Google Scholar
Dwork, C., McSherry, F., Nissim, K. and Smith, A. (2006) Calibrating noise to sensitivity in private data analysis. In: Proceedings Theory of Cryptography Conference 265–284.Google Scholar
Dwork, C., Naor, M., Pitassi, T. and Rothblum, G. N. (2010) Differential privacy under continual observation. In: Proceedings ACM Symposium on Theory of Computing 715–724.Google Scholar
Evfimievski, A., Gehrke, J. and Srikant, R. (2003) Limiting privacy breaches in privacy preserving data mining. In: Proc. ACM Symposium on Principles of Database Systems 211–222.Google Scholar
Fung, B. C. M., Wang, K., Chen, R. and Yu, P. S. (2010) Privacy-preserving data publishing: A survey on recent developments. ACM Computing Surveys 42 (4) 14:1–53.Google Scholar
Giacobazzi, R. and Mastroeni, I. (2004) Abstract non-interference. In: Proceedings ACM Symposium on Principles of Programming Languages 186–197.Google Scholar
Goguen, J. A. and Meseguer, J. (1982) Security policies and security models. In: Proceedings IEEE Symposium on Security and Privacy 11–20.CrossRefGoogle Scholar
Gray, J. W. III, (1990) Probabilistic interference. In: Proceedings IEEE Symposium on Security and Privacy 170–179.Google Scholar
Gray, J. W. III, (1991) Toward a mathematical foundation for information flow security. In: Proceedings IEEE Symposium on Security and Privacy 21–35.CrossRefGoogle Scholar
Halpern, J. Y. (2003) Reasoning about Uncertainty, MIT Press, Cambridge, Massachusetts.Google Scholar
Hamadou, S., Sassone, V. and Palamidessi, C. (2010) Reconciling belief and vulnerability in information flow. In: Proceedings IEEE Symposium on Security and Privacy 79–92.Google Scholar
Heusser, J. and Malacaria, P. (2009) Applied quantitative information flow and statistical databases. In: Workshop on Formal Aspects in Security and Trust 96–110.Google Scholar
Heusser, J. and Malacaria, P. (2010) Quantifying information leaks in software. In: Annual Computer Security Applications Conference 261–269.Google Scholar
International Organization for Standardization (1989) Information processing systems: Open systems interconnection – basic reference model, Part 2: Security architecture, ISO 7498-2.Google Scholar
International Organization for Standardization (2005) Common criteria for information technology security evaluation: Part 1: Introduction and general model, ISO 15408. CCMB-2006-09-001, Version 3.1, Revision 1. Available from http://www.commoncriteriaportal.org.Google Scholar
Jones, D. S. (1979) Elementary Information Theory, Clarendon Press, Oxford.Google Scholar
Joshi, R. and Leino, K. R. M. (2000) A semantic approach to secure information flow. Science of Computer Programming 37 113–138.Google Scholar
Kifer, D. and Gehrke, J. (2006) Injecting utility into anonymized datasets. In: Proceedings ACM Conference on Management of Data 217–228.Google Scholar
Köpf, B. and Basin, D. (2007) An information-theoretic model for adaptive side-channel attacks. In: Proceedings ACM Conference on Computer and Communications Security 286–296.Google Scholar
Kozen, D. (1981) Semantics of probabilistic programs. Journal of Computer and System Sciences 22 328–350.Google Scholar
Krohn, M., Yip, A., Brodsky, M., Cliffer, N., Kaashoek, M. F., Kohler, E. and Morris, R. (2007) Information flow control for standard OS abstractions. In: Proceedings ACM Symposium on Operating Systems Principles 321–334.Google Scholar
Lamport, L. (1985) Basic concepts: Logical foundation. In: Distributed Systems: Methods and Tools for Specification, An Advanced Course. Springer Lecture Notes in Computer Science 190 19–30.Google Scholar
Laud, P. (2001) Semantics and program analysis of computationally secure information flow. In: Proceedings European Symposium on Programming. Springer Lecture Notes in Computer Science 2028 77–91.Google Scholar
Li, P., Mao, Y. and Zdancewic, S. (2003) Information integrity policies. In: Workshop on Formal Aspects in Security and Trust 53–70.Google Scholar
Liu, J., George, M. D., Vikram, K., Qi, X., Waye, L. and Myers, A. C. (2009) Fabric: A platform for secure distributed computation and storage. In: Proceedings ACM Symposium on Operating Systems Principles 321–334.Google Scholar
Livshits, V. B. and Lam, M. S. (2005) Finding security vulnerabilities in Java applications with static analysis. In: Proceedings USENIX Security Symposium 271–286.Google Scholar
Lowe, G. (2002) Quantifying information flow. In: Proceedings IEEE Computer Security Foundations Workshop 18–31.Google Scholar
Machanavajjhala, A., Kifer, D., Gehrke, J. and Venkitasubramaniam, M. (2007) ℓ-diversity: Privacy beyond k-anonymity. ACM Transactions on Knowledge Discovery from Data. Available from http://dl.acm.org/citation.cfm?id=1217302.Google Scholar
Malacaria, P. (2007) Assessing security threats of looping constructs. In: Proceedings ACM Symposium on Principles of Programming Languages 225–235.Google Scholar
Mantel, H. (2000) Possibilistic definitions of security: An assembly kit. In: Proc. IEEE Computer Security Foundations Workshop, 185–199.Google Scholar
McCamant, S. and Ernst, M. D. (2008) Quantitative information flow as network capacity. In: Proceedings ACM Conference on Programming Language Design and Implementation 193–205.Google Scholar
McCullough, D. (1987) Specifications for multi-level security and a hook-up property. In: Proceedings IEEE Symposium on Security and Privacy 161–166.Google Scholar
McLean, J. (1990) Security models and information flow. In: Proceedings IEEE Symposium on Security and Privacy 180–189.Google Scholar
McLean, J. (1996) A general theory of composition for a class of ‘possibilistic' properties. IEEE Transactions on Software Engineering 22 (1)53–67.CrossRefGoogle Scholar
Millen, J. (1987) Covert channel capacity. In: Proceedings IEEE Symposium on Security and Privacy 60–66.Google Scholar
Murphy, R. (1996) An analysis of the distribution of birthdays in a calendar year. Available at http://www.panix.com/~murphy/bday.html, accessed Dec. 29, 2009.Google Scholar
Myers, A. C. (1999) JFlow: Practical mostly-static information flow control. In: Proceedings ACM Symposium on Principles of Programming Languages 228–241.Google Scholar
National Research Council (1991) Computers at Risk: Safe Computing in the Information Age. National Academy Press, Washington, D.C.Google Scholar
Newsome, J., McCamant, S. and Song, D. (2009) Measuring channel capacity to distinguish undue influence. In: Proceedings ACM Workshop on Programming Languages and Analysis for Security. Available from http://doi.acm.org/10.1145/1554339.1554349.Google Scholar
Newsome, J. and Song, D. (2005) Dynamic taint analysis for automatic detection, analysis and signature generation of exploits on commodity software. In: Proceedings Symposium on Network and Distributed System Security. Available from http://www.isoc.org/isoc/conferences/ndss/05/proceedings/papers/taintcheck.pdf.Google Scholar
Øhrn, A. and Ohno-Machado, L. (1999) Using Boolean reasoning to anonymize databases. Artificial Intelligence in Medicine 15 (3)235–254.Google Scholar
Pottier, F. and Simonet, V. (2003) Information flow inference for ML. ACM Transactions on Programming Languages and Systems 25 (1)117–158.Google Scholar
Rinard, M., Cadar, C., Dumitran, D., Roy, D. M., Leu, T. and Beebee, W. S. Jr. (2004) Enhancing server availability and security through failure-oblivious computing. In: Proceedings USENIX Symposium on Operating System Design and Implementation 303–316.Google Scholar
Roy, I., Setty, S. T. V., Kilzer, A., Shmatikov, V. and Witchel, E. (2010) Airavat: Security and privacy for MapReduce. In: Proceedings USENIX Symposium on Networked Systems Design and Implementation 297–312.Google Scholar
Sabelfeld, A. and Sands, D. (2001) A per model of secure information flow in sequential programs. Higher-Order and Symbolic Computation 14 (1)59–91.Google Scholar
Samarati, P. (2001) Protecting respondents' identities in microdata release. IEEE Transactions on Knowledge and Data Engineering 13 (6)1010–1027.Google Scholar
Samarati, P. and Sweeney, L. (1998) Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression, Technical Report SRI-CSL-98-04, Computer Science Laboratory, SRI International. Available from http://www.csl.sri.com/papers/sritr-98-04.Google Scholar
Schneider, F. B. (2000) Enforceable security policies. ACM Transactions on Information and System Security 3 (1)30–50.Google Scholar
Scripture, E. W. (1892) The need of psychological training. Science 19 (474) 127–128. Available from http://www.jstor.org/stable/1766918.Google Scholar
Shafer, G. (1976) A Mathematical Theory of Evidence, Princeton University Press, Princeton, NJ.Google Scholar
Shannon, C. E. (1948) A mathematical theory of communication. Bell System Technical Journal 27 379–423 and 623–656.Google Scholar
Smith, G. (2009) On the foundations of quantitative information flow. In: Proceedings Conference on Foundations of Software Science and Computation Structures 288–302.Google Scholar
Smith, G. and Volpano, D. (1998) Secure information flow in a multi-threaded imperative language. In Proceedings ACM Symposium on Principles of Programming Languages 355–364.Google Scholar
Suh, G. E., Lee, J. W., Zhang, D. and Devedas, S. (2004) Secure program execution via dynamic information flow tracking. In: Proceedings ACM Conference on Architectural Support for Programming Languages and Systems 85–96.Google Scholar
Sweeney, L. (2002a) Achieving k-anonymity privacy protection using generalization and suppression. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems 10 (5)571–588.Google Scholar
Sweeney, L. (2002b) k-anonymity: A model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems 10 (5)557–570.Google Scholar
Volpano, D. (2000) Secure introduction of one-way functions. In: Proceedings IEEE Computer Security Foundations Workshop 246–254.Google Scholar
Volpano, D. and Smith, G. (1999) Probabilistic noninterference in a concurrent language. Journal of Computer Security 7 (2,3)231–253.Google Scholar
Voydock, V. L. and Kent, S. T. (1983) Security mechanisms in high-level network protocols. Computing Surveys 15 (2)135–171.Google Scholar
Wall, L., Christiansen, T. and Schwartz, R. L. (1996) Programming Perl, 2nd edition, O'Reilly, Sebastopol, California.Google Scholar
Xu, W., Bhatkar, S. and Sekar, R. (2006) Taint-enhanced policy enforcement: A practical approach to defeat a wide range of attacks. In: Proceedings USENIX Security Symposium 121–136.Google Scholar
Zdancewic, S. and Myers, A. C. (2001) Robust declassification. In: Proceedings IEEE Computer Security Foundations Workshop 15–23.Google Scholar
Zdancewic, S., Zheng, L., Nystrom, N. and Myers, A. C. (2001) Untrusted hosts and confidentiality: Secure program partitioning. In: Proceedings ACM Symposium on Operating Systems Principles 1–14.Google Scholar
Zheng, L. and Myers, A. C. (2005) End-to-end availability policies and noninterference. In: Proceedings IEEE Computer Security Foundations Workshop 272–286.Google Scholar