Strong accountability for network storage

ABSTRACT

This article presents the design, implementation, and evaluation of CATS, a network storage service with strong accountability properties. CATS offers a simple web services interface that allows clients to read and write opaque objects of variable size. This interface is similar to the one offered by existing commercial Internet storage services. CATS extends the functionality of commercial Internet storage services by offering support for strong accountability.

A CATS server annotates read and write responses with evidence of correct execution, and offers audit and challenge interfaces that enable clients to verify that the server is faithful. A faulty server cannot conceal its misbehavior, and evidence of misbehavior is independently verifiable by any participant. CATS clients are also accountable for their actions on the service. A client cannot deny its actions, and the server can prove the impact of those actions on the state views it presented to other clients.

Experiments with a CATS prototype evaluate the cost of accountability under a range of conditions and expose the primary factors influencing the level of assurance and the performance of a strongly accountable storage server. The results show that strong accountability is practical for network storage systems in settings with strong identity and modest degrees of write-sharing. We discuss how the accountability concepts and techniques used in CATS generalize to other classes of network services.

REFERENCES

• 1: Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 2: Amazon.com, Inc. 2007. Amazon simple storage service (Amazon S3). http://www.amazon.com/gp/browse.html?node=16427261.
• 3: Aris Anagnostopoulos , Michael T. Goodrich , Roberto Tamassia, Persistent Authenticated Dictionaries and Their Applications, Proceedings of the 4th International Conference on Information Security, p.379-393, October 01-03, 2001
• 4: Ross J. Anderson, Why cryptosystems fail, Communications of the ACM, v.37 n.11, p.32-40, Nov. 1994 [doi>10.1145/188280.188291]
• 5: Bayer, R. and McCreight, E. M. 1972. Organization and maintenance of large ordered indices. Acta Informatica 1, 173--189.
• 6: Josh Benaloh , Michael de Mare, One-way accumulators: a decentralized alternative to digital signatures, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.274-285, January 1994, Lofthus, Norway
• 7: Ahto Buldas , Peeter Laud , Helger Lipmaa, Accountable certificate management using undeniable attestations, Proceedings of the 7th ACM conference on Computer and communications security, p.9-17, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352604]
• 8: Ahto Buldas , Peeter Laud , Helger Lipmaa , Jan Willemson, Time-Stamping with Binary Linking Schemes, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.486-501, August 23-27, 1998
• 9: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 10: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 11: Ferraiolo, D. and Kuhn, R. 1992. Role-Based access controls. In 15th National Computer Security Conference.
• 12: Kevin Fu , M. Frans Kaashoek , David Mazières, Fast and secure distributed read-only file system, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.13-13, October 22-25, 2000, San Diego, California
• 13: Yun Fu , Jeffrey Chase , Brent Chun , Stephen Schwab , Amin Vahdat, SHARP: an architecture for secure resource peering, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 14: Goodrich, M., Tamassia, R., and Schwerin, A. 2001. Implementation of an authenticated dictionary with skip lists and commutative hashing. In Proceedings of the DARPA Information Survivability Conference and Exposition, 68--82.
• 15: Mahesh Kallahalla , Erik Riedel , Ram Swaminathan , Qian Wang , Kevin Fu, Plutus: Scalable Secure File Sharing on Untrusted Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 16: Lampson, B. W. 2000. Computer security in the real world. In Proceedings of the Annual Computer Security Applications Conference.
• 17: Paul Laskowski , John Chuang, Network monitors and contracting systems: competition and innovation, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 18: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 19: Jinyuan Li , Maxwell Krohn , David Mazières , Dennis Shasha, Secure untrusted data repository (SUNDR), Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.9-9, December 06-08, 2004, San Francisco, CA
• 20: John MacCormick , Nick Murphy , Marc Najork , Chandramohan A. Thekkath , Lidong Zhou, Boxwood: abstractions as the foundation for storage infrastructure, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.8-8, December 06-08, 2004, San Francisco, CA
• 21: Umesh Maheshwari , Radek Vingralek , William Shapiro, How to build a trusted database system on untrusted storage, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.10-10, October 22-25, 2000, San Diego, California
• 22: Petros Maniatis , Mary Baker, Historic integrity in distributed systems, Stanford University, Stanford, CA, 2003
• 23: Petros Maniatis , Mary Baker, Enabling the Archival Storage of Signed Documents, Proceedings of the Conference on File and Storage Technologies, p.31-45, January 28-30, 2002
• 24: Petros Maniatis , Mary Baker, Secure History Preservation Through Timeline Entanglement, Proceedings of the 11th USENIX Security Symposium, p.297-312, August 05-09, 2002
• 25: David Mazières , Dennis Shasha, Building secure file systems out of byzantine storage, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571840]
• 26: Merkle, R. C. 1980. Protocols for public key cryptosystems. In Proceedings of the Sysmposium on Security and Privacy, 122--133.
• 27: Naor, M. and Nissim, K. 2000. Certificate revocation and certificate update. IEEE J. Select. Areas Commun. 18, 4, 561--570.
• 28: L. Pearlman , V. Welch , I. Foster , C. Kesselman , S. Tuecke, A Community Authorization Service for Group Collaboration, Proceedings of the 3rd International Workshop on Policies for Distributed Systems and Networks (POLICY'02), p.50, June 05-07, 2002
• 29: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 30: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 31: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 32: Bruce Schneier , John Kelsey, Cryptographic support for secure logs on untrusted machines, Proceedings of the 7th conference on USENIX Security Symposium, p.4-4, January 26-29, 1998, San Antonio, Texas
• 33: Bruce Schneier , John Kelsey, Secure audit logs to support computer forensics, ACM Transactions on Information and System Security (TISSEC), v.2 n.2, p.159-176, May 1999 [doi>10.1145/317087.317089]
• 34: Sean W. Smith , Elaine R. Palmer , Steve Weingart, Using a High-Performance, Programmable Secure Coprocessor, Proceedings of the Second International Conference on Financial Cryptography, p.73-89, February 23-25, 1998
• 35: Tamassia, R. and Triandopoulos, N. 2003. On the cost of authenticated data structures. Tech. Rep., Brown University.
• 36: Trusted Computing Group. 2007. Trusted platform module specification. https://www. trustedcomputinggroup.org/groups/tpm/.
• 37: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 38: Aydan R. Yumerefendi , Jeffrey S. Chase, Trust but verify: accountability for network services, Proceedings of the 11th workshop on ACM SIGOPS European workshop, p.37-es, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133585]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

General Terms:
Design, Security, Verification

Keywords:
Accountable services, accountability, accountable storage