Untrusted hosts and confidentiality: secure program partitioning

ABSTRACT

This paper presents secure program partitioning, a language-based technique for protecting confidential data during computation in distributed systems containing mutually untrusted hosts. Confidentiality and integrity policies can be expressed by annotating programs with security types that constrain information flow; these programs can then be partitioned automatically to run securely on heterogeneously trusted hosts. The resulting communicating subprograms collectively implement the original program, yet the system as a whole satisfies the security requirements of participating principals without requiring a universally trusted host machine. The experience in applying this methodology and the performance of the resulting distributed code suggest that this is a promising way to obtain secure distributed computation.

REFERENCES

• 1: Martín Abadi , Anindya Banerjee , Nevin Heintze , Jon G. Riecke, A core calculus of dependency, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.147-160, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292555]
• 2: Johan Agat, Transforming out timing leaks, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.40-53, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325702]
• 3: D. E. Bell and L. J. LaPadula. Secure computer system: Unified exposition and Muitics interpretation. Technical Report ESD-TR-75-306, MITRE Corp. MTR-2997, Bedford, MA, 1975. Available as NTIS AD-A023 588.
• 4: K. J. Biba. Integrity considerations for secure computer systems. Technical Report ESD-TR-76-372, USAF Electronic Systems Division, Bedford, MA, April 1977.
• 5: Cryptix. http ://www. cryptix, org/products/cryptix31/.
• 6: Ivan Damgard, Joe Kilian, and Louis Salvail. On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. In Jacques Stern, editor, Advances in Cryptology - Proceedings of EUROCRYPT 99, LNCS 1592, pages 56-73. Springer, 1999.
• 7: 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]
• 8: Dorothy E. Denning , Peter J. Denning, Certification of programs for secure information flow, Communications of the ACM, v.20 n.7, p.504-513, July 1977 [doi>10.1145/359636.359712]
• 9: Department of Defense. Department of Defense Trusted Computer System Evaluation Criteria, DOD 5200.28-STD (The Orange Book) edition, December 1985.
• 10: Fred Douglis, John K. Ousterhout, M. Frans Kaashoek, and Andrew S. Tanenbaum. A comparison of two distributed systems: Amoeba and Sprite. ACM Transactions on Computer Systems, 4(4), Fall 1991.
• 11: S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. In R.L. Rivest, A. Sherman, and D. Chaum, editors, Advances in Cryptology: Proc. of CRYPTO 82, pages 205-210. Plenum Press, 1983.
• 12: Richard J. Feiertag. A technique for proving specifications a r e multilevel secure. Technical Report CSL-109, SRI International Computer Science Lab, Menlo Park, California, January 1980.
• 13: J. S. Fenton. Memoryless subsystems. Computing J., 17(2): 143-147, May 1974.
• 14: George Fink and Karl Levitt. Property-based testing of privileged programs. In Proceedings of the lOth Annual Computer Security Applications Conference, pages 154-163, 1994.
• 15: J. A. Goguen and J. Meseguer. Unwinding and inference control. In Proc. IEEE Symposium on Security and Privacy, pages 75-86, April 1984.
• 16: Jonathan K. Millen, A Logical Approach to Multilevel Security of Probabilistic Systems, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.164, May 04-06, 1992
• 17: Nevin Heintze , Jon G. Riecke, The SLam calculus: programming with secrecy and integrity, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.365-377, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268976]
• 18: Java secure socket extension (JSSE). http ://j ava. sun. com/product s/j sse/.
• 19: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 20: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 21: J. R. Lyle, D. R. Wallace, J. R. Graham, K. B. Gallagher, J. P. Poole, and D. W. Binkley. Unravel: A CASE tool to assist evaluation of high integrity software. IR 5691, NIST, 1995.
• 22: Heiko Mantel , Andrei Sabelfeld, A Generic Approach to the Security of Multi-Threaded Programs, Proceedings of the 14th IEEE Workshop on Computer Security Foundations, p.126, June 11-13, 2001
• 23: M. D. McIlroy , J. A. Reeds, Multilevel security in the UNIX tradition, Software—Practice & Experience, v.22 n.8, p.673-694, Aug. 1992 [doi>10.1002/spe.4380220805]
• 24: Jonathan K. Millen, Security Kernel validation in practice, Communications of the ACM, v.19 n.5, p.243-250, May 1976 [doi>10.1145/360051.360059]
• 25: Jonathan K. Millen. Information flow analysis of formal specifications. In Proc. IEEE Symposium on Security and Privacy, pages 3-8, April 1981.
• 26: Greg Morrisett , David Walker , Karl Crary , Neal Glew, From system F to typed assembly language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.527-568, May 1999 [doi>10.1145/319301.319345]
• 27: Andrew C. Myers, JFlow: practical mostly-static information flow control, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.228-241, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292561]
• 28: Andrew C. Myers , Barbara Liskov, Protecting privacy using the decentralized label model, ACM Transactions on Software Engineering and Methodology (TOSEM), v.9 n.4, p.410-442, Oct. 2000 [doi>10.1145/363516.363526]
• 29: Andrew C. Myers, Nathaniel Nystrom, Lantian Zheng, and Steve Zdancewic. Jif: Java information flow. Software release. Located at http://www.cs.cornell.edu/jif, July 2001.
• 30: George C. Necula, Proof-carrying code, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.106-119, January 15-17, 1997, Paris, France [doi>10.1145/263699.263712]
• 31: OMG. The Common Object Request Broker: Architecture and Specification, December 1991. OMG TC Document Number 91.12.1, Revision 1.1.
• 32: Platform for privacy preferences (P3P). http://www, w3. org/p3p.
• 33: Jens Palsberg , Peter Ørbæk, Trust in the lambda-Calculus, Proceedings of the Second International Symposium on Static Analysis, p.314-329, September 25-27, 1995
• 34: S. Pinsky, Absorbing covers and intransitive non-interference, Proceedings of the 1995 IEEE Symposium on Security and Privacy, p.102, May 08-10, 1995
• 35: François Pottier , Sylvain Conchon, Information flow inference for free, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.46-57, September 2000
• 36: M. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory, 1981.
• 37: Java remote method interface (RMI). http ://j ava. sun. com/products/jdk/rmi/.
• 38: John Rushby. Noninterference, transitivity and channel-control security policies. Technical report, SRI, I992.
• 39: Andrei Sabelfeld , David Sands, Probabilistic Noninterference for Multi-Threaded Programs, Proceedings of the 13th IEEE Computer Security Foundations Workshop (CSFW'00), p.200, July 03-05, 2000
• 40: Fred B. Schneider, Enforceable security policies, ACM Transactions on Information and System Security (TISSEC), v.3 n.1, p.30-50, Feb. 2000 [doi>10.1145/353323.353382]
• 41: Geoffrey Smith, A New Type System for Secure Information Flow, Proceedings of the 14th IEEE Workshop on Computer Security Foundations, p.115, June 11-13, 2001
• 42: Geoffrey Smith , Dennis Volpano, Secure information flow in a multi-threaded imperative language, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.355-364, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268975]
• 43: J.G. Steiner, C. Neuman, and J. I. Schiller. Kerberos: An authentication service for open network systems. Technical report, Project Athena, MIT, Cambridge, MA, March 1988.
• 44: Frank Tip. A survey of program slicing techniques. Journal of Programming Languages, 3:121-189, I995.
• 45: Dennis Volpano , Geoffrey Smith, Verifying secrets and relative secrecy, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.268-276, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325729]
• 46: Dennis Volpano , Cynthia Irvine , Geoffrey Smith, A sound type system for secure flow analysis, Journal of Computer Security, v.4 n.2-3, p.167-187, Jan. 1996
• 47: J. Todd Wittbold and Dale M, Johnson. Information flow in nondeterministic systems. In Proc. IEEE Symposium on Security and Privacy, pages 144-161, May 1990.
• 48: Tam Ylonen. SSH - secure login connections over the Interact. In The Sixth USENIX Security Symposium Proceedings, pages 37-42, San Jose, California, 1996.
• 49: Steve Zdancewic , Andrew C. Myers, Robust Declassification, Proceedings of the 14th IEEE Workshop on Computer Security Foundations, p.5, June 11-13, 2001
• 50: Steve Zdancewic , Andrew C. Myers, Secure Information Flow and CPS, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.46-61, April 02-06, 2001
• 51: Steve Zdancewic , Lantian Zheng , Nathaniel Nystrom , Andrew Myers, Secure Program Partitioning, Cornell University, Ithaca, NY, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.0 General
          Subjects: Protection mechanisms

General Terms:
Experimentation, Languages, Performance, Security