Secure file system versioning at the block level

ABSTRACT

In typical file systems, valuable data is vulnerable to being accidentally or maliciously deleted or overwritten. Versioning file systems protect data from accidents by transparently retaining old versions, but do less well in protecting data from malicious attack. These systems remain vulnerable to attackers who gain unauthorized access to prune old file versions, who bypass the file system to directly manipulate storage, or who exploit bugs in any part of the operating system.

This paper presents VDisk, a secure, block-level versioning system that adds file-grain versioning to a standard, unmodified file system. VDisk consists of a set of untrusted user-mode tools and a trusted, secure kernel that is implemented within an isolated Xen virtual machine domain. The secure kernel is designed to be simple and thus trustworthy. This kernel logs file-system updates to a secure log, exports a read-only view of the log to the rest of the system and securely removes unwanted versions from the log. Secure cleaning is implemented in a two-level manner. An untrusted, user-mode cleaner selects log entries for reclamation and submits cleaning requests to the trusted VDisk kernel along with a proof that the request satisifies the device's version-retention policy. The secure kernel verifies the proof and updates the log.

References

1. MySQL, http://www.mysql.com.
2. M. G. Baker, J. H. Hartman, M. D. Kupfer, K. W. Shirriff, and J. K. Ousterhout. Measurements of a distributed file system. In SOSP '91: Proceedings of the thirteenth ACM Symposium on Operating Systems Principles, pages 198--212. ACM Press, 1991.
3. P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield. Xen and the art of virtualization. In Symposium on Operating Systems Principles, pages 164--177, New York, NY, USA, 2003. ACM Press.
4. S. Chutani, O. T. Anderson, M. L. Kazar, B. W. Leverett, W. A. Mason, and R. N. Sidebotham. The Episode File System. In Proceedings of the USENIX Winter 1992 Technical Conference, pages 43--60, San Fransisco, CA, USA, 1992.
5. B. Cornell, P. Dinda, and F. Bustamante. Wayback: A user-level versioning file system for linux. In USENIX Annual Technical Conference, FREENIX Track, 2004.
6. G. W. Dunlap, S. T. King, S. Cinar, M. A. Basrai, and P. M. Chen. ReVirt: Enabling intrusion analysis through virtual-machine logging and replay. SIGOPS Operating Systems Review, 36(SI):211--224, 2002.
7. D. Ellard. Trace-based analyses and optimizations for network storage servers. PhD thesis, Harvard Computer Science Technical Report TR-11-04, May 2004.
8. D. Ellard, J. Ledlie, P. Malkani, and M. Seltzer. Passive NFS tracing of email and research workloads. In Second Annual USENIX File and Storage Technologies Conference (FAST'03), pages 203--216, March 2003.
9. D. R. Engler, M. F. Kaashoek, and J. O. Jr. Exokernel: An operating system architecture for application-level resource management. In Symposium on Operating Systems Principles, pages 251--266, 1995.
10. M. D. Flouris and A. Bilas. Clotho: Transparent data versioning at the block I/O level. 12th NASA/IEEE Conference on Mass Storage Systems and Technologies, 2004.
11. T. Garfinkel, B. Pfaff, J. Chow, M. Rosenblum, and D. Boneh. Terra: A virtual machine-based platform for trusted computing. In Proceedings of the 19th ACM Symposium on Operating Systems Principles, pages 193--206, 2003.
12. T. J. Gibson and E. L. Miller. Long-term file activity patterns in a UNIX workstation environment. In The Fifteenth IEEE Symposium on Mass Storage Systems, March 1998.
13. D. K. Gifford, R. M. Needham, and M. D. Schroeder. The cedar file system. Communications of the ACM, 31(3):288--298, 1988.
14. D. Grune. Concurrent Versions System, A Method for Independent Cooperation. IR 113, Vrije Universiteit, 1986.
15. D. Hitz, J. Lau, and M. Malcolm. File system design for an NFS file server appliance. In Proceedings of the USENIX Winter 1994 Technical Conference, pages 235--246, San Fransisco, CA, USA, 17--21 1994.
16. J. E. Johnson and W. A. Laing. Overview of the Spiralog File System. Digital Technical Journal of Digital Equipment Corporation, 8(2):5--14, 1996.
17. S. T. King and P. M. Chen. Backtracking intrusions. In Symposium on Operating Systems Principles, pages 223--236, 2003.
18. E. K. Lee and C. A. Thekkath. Petal: Distributed virtual disks. In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, pages 84--92, Cambridge, MA, 1996.
19. J. MacDonald, P. N. Hilfinger, and L. Semenzato. PRCS: The project revision control system. Lecture Notes in Computer Science, 1439:33+, 1998.
20. K. McCoy. VMS File System Internals. Digital Press, 1990.
21. C. B. Morrey III and D. Grunwald. Peabody: The time travelling disk. In IEEE Symposium on Mass Storage Systems, pages 241--253, 2003.
22. J. H. Morris, M. Satyanarayanan, M. H. Conner, J. H. Howard, D. S. Rosenthal, and F. D. Smith. Andrew: a distributed personal computing environment. Communications of the ACM, 29(3):184--201, 1986.
23. K. Muniswamy-Reddy, C. P. Wright, A. Himmer, and E. Zadok. A versatile and user-oriented versioning file system. In Third USENIX Conference on File and Storage Technologies (FAST 2004), San Francisco, CA, USA, March/April 2004. USENIX Association.
24. J. K. Ousterhout, H. D. Costa, D. Harrison, J. A. Kunze, M. Kupfer, and J. G. Thompson. A trace-driven analysis of the UNIX 4.2 BSD file system. In SOSP '85: Proceedings of the tenth ACM symposium on Operating systems principles, pages 15--24. ACM Press, 1985.
25. H. Patterson, S. Manley, M. Federwisch, D. Hitz, S. Kleiman, and S. Owara. SnapMirror: File-system-based asynchronous mirroring for disaster recovery. In First USENIX Conference on File and Storage Technologies, 2002.
26. Z. Peterson and R. Burns. Ext3cow: a time-shifting file system for regulatory compliance. ACM Transactions on Storage, 1(2):190--212, 2005.
27. D. Presotto, R. Pike, K. Thompson, and H. Trickey. Plan 9: A distributed system. In Sprint 1991 EurOpen, May 1991.
28. D. Roselli, J. Lorch, and T. Anderson. A comparison of file system workloads. In USENIX 2000 Technical Conference, pages 41--54, 2000.
29. M. Rosenblum and J. K. Ousterhout. The design and implementation of a log-structured file system. ACM Transactions on Computer Systems, 10(1):26--52, 1992.
30. D. S. Santry, M. J. Feeley, N. C. Hutchinson, A. C. Veitch, R. W. Carton, and J. Ofir. Deciding when to forget in the Elephant File System. In Symposium on Operating Systems Principles, pages 110--123, 1999.
31. M. Sivathanu, L. N. Bairavasundaram, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau. Life or death at the block-level. In Symposium on Operating Systems Design and Implementation, pages 379--394, 2004.
32. M. Sivathanu, V. Prabhakaran, A. Arpaci-Dusseau, and R. Arpaci-Dusseau. Improving storage system availability with D-GRAID. In Third USENIX Conference on File and Storage Technologies (FAST 2004), pages 15--30, March 2004.
33. C. A. N. Soules, G. R. Goodson, J. D. Strunk, and G. Ganger. Metadata efficiency in versioning file systems. In Second USENIX Conference on File and Storage Technologies (FAST 2003), San Francisco, CA, USA, 2003.
34. J. D. Strunk, G. R. Goodson, M. L. Scheinholtz, C. A. Soules, and G. R. Ganger. Design and implementation of a self-securing storage device. In Symposium on Operating Systems Design and Implementation, pages 165--179, October 2000.
35. W. F. Tichy. RCS: A system for version control. Software---Practice and Experience, 15(7):637--654, 1985.
36. A. Warfield, R. Ross, K. Fraser, C. Limpach, and S. Hand. Parallax: Managing storage for a million machines. In The 10th USENIX Workshop on Hot Topics in Operating Systems (HotOS-X), June 2005.
37. A. Whitaker, R. S. Cox, and S. D. Gribble. Using time travel to diagnose computer problems. In Symposium on Operating Systems Design and Implementation, pages 77--90, 2004.
38. A. Whitaker, R. S. Cox, M. Shaw, and S. D. Gribble. Constructing services with interposable virtual hardware. In First Symposium on Networked Systems Design and Implementation, pages 169--182, 2004.
39. Q. Yang, W. Xiao, and J. Ren. TRAP-array: A disk array architecture providing timely recovery to any point-in-time. In ISCA '06: Proceedings of the 33rd International Symposium on Computer Architecture, pages 289--301, 2006.

Index Terms

• Information systems

  • Information storage systems

    • Storage management

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management