Effective and efficient compromise recovery for weakly consistent replication

ABSTRACT

Weakly consistent replication of data has become increasingly important both for loosely-coupled collections of personal devices and for large-scale infrastructure services. Unfortunately, automatic replication mechanisms are agnostic about the quality of the data they replicate. Inappropriate updates, whether malicious or simply the result of misuse, propagate automatically and quickly. The consequences may not be noticed until days later, when the corrupted data has been fully replicated, thereby deleting or overwriting all traces of the valid data. In this sort of situation, it can be hard or impossible to restore an entire distributed system to a clean state without losing data and disrupting users.

Polygraph is a software layer that extends the functionality of weakly consistent replication systems to support compromise recovery. Its goal is to undo the direct and indirect effects of updates due to a source known after the fact to have been compromised. In restoring a clean replicated state, Polygraph expunges all data due to a compromise or derived from such data, retains as much uncompromised data as possible, and revives valid versions of subsequently compromised data. Our evaluation demonstrates that Polygraph is both effective, retaining uncompromised data, and efficient, re-replicating data only when necessary.

REFERENCES

• 1: Apple Inc. Time Machine. http://www.apple.com/macosx/features/timemachine.html, 2007.
• 2: Mary Baker , Mehul Shah , David S. H. Rosenthal , Mema Roussopoulos , Petros Maniatis , TJ Giuli , Prashanth Bungale, A fresh look at the reliability of long-term digital storage, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 3: Nalini Belaramani , Mike Dahlin , Lei Gao , Amol Nayate , Arun Venkataramani , Praveen Yalagandula , Jiandan Zheng, PRACTI replication, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.5-5, May 08-10, 2006, San Jose, CA
• 4: Carbonite, Inc. Remote backup online. http: //www.carbonite.com, 2007.
• 5: CNet.com. Biz travelers beware: Airport ad-hoc hot spots could be dangerous. http://news.cnet.com/8301-10784_3-9888021-7.html, 2007.
• 6: Eric Cronin , Sugih Jamin , Tal Malkin , Patrick McDaniel, On the performance, feasibility, and use of forward-secure signatures, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948130]
• 7: Decho Corporation. Online backup, data backup, and remote backup solutions. http://www.mozy.com, 2007.
• 8: P. Dvorak. Spike in laptop thefts stirs jitters over data. The Washington Post, June 22, 2006.
• 9: Paul England , Butler Lampson , John Manferdelli , Marcus Peinado , Bryan Willman, A Trusted Open Platform, Computer, v.36 n.7, p.55-62, July 2003 [doi>10.1109/MC.2003.1212691]
• 10: David Lomet , Zografoula Vagena , Roger Barga, Recovery from "bad" user transactions, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142512]
• 11: Microsoft Corporation. About Active Directory Domain Services. http://msdn.microsoft.com/en-us/library/aa772142(VS.85).aspx, 2008.
• 12: Microsoft Corporation. Live Mesh. https://www.mesh.com, 2008.
• 13: Andrew C. Myers , Barbara Liskov, A decentralized model for information flow control, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.129-142, October 05-08, 1997, Saint Malo, France
• 14: 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]
• 15: NetApp, Inc. Snap vault. http://www.netapp.com/us/products/protection-software/snapvault.html, 2008.
• 16: J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proc. of the Network and Distributed System Security Symposium, February 2005.
• 17: L. Novik, I. Hudis, D. Terry, S. Anand, V. Jhaveri, A. Shah, and Y. Wu. Peer-to-peer replication in WinFS. Technical Report MSR-TR-2006-78, Microsoft Research, June 2006.
• 18: Daniel Peek , Jason Flinn, EnsemBlue: integrating distributed storage and consumer electronics, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 19: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 20: Zachary Peterson , Randal Burns, Ext3cow: a time-shifting file system for regulatory compliance, ACM Transactions on Storage (TOS), v.1 n.2, p.190-212, May 2005 [doi>10.1145/1063786.1063789]
• 21: V. Ramasubramanian, T. Rodeheffer, D. Terry, M. Walraed-Sullivan, T. Wobber, C. Marshall, and A. Vahdat. Cimbiosys: A platform for content-based partial replication. Technical Report MSR-TR-2008-116, Microsoft Research, 2008. To appear in Proc. of the USENIX Symposium on Networked Systems Design and Implementation (NSDI '09).
• 22: Yasushi Saito , Marc Shapiro, Optimistic replication, ACM Computing Surveys (CSUR), v.37 n.1, p.42-81, March 2005 [doi>10.1145/1057977.1057980]
• 23: Jerome H. Saltzer, Protection and the control of information sharing in multics, Communications of the ACM, v.17 n.7, p.388-402, July 1974 [doi>10.1145/361011.361067]
• 24: Douglas S. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch , Ross W. Carton , Jacob Ofir, Deciding when to forget in the Elephant file system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.110-123, December 12-15, 1999, Charleston, South Carolina, United States
• 25: Mike J. Spreitzer , Marvin M. Theimer , Karin Petersen , Alan J. Demers , Douglas B. Terry, Dealing with server corruption in weakly consistent, replicated data systems, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.234-240, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262151]
• 26: Symantec Corporation. Symantec Backup. http://www.symantec.com, 2007.
• 27: Werner Vogels, Eventually Consistent, Queue, v.6 n.6, October 2008 [doi>10.1145/1466443.1466448]
• 28: Wikipedia. Polygraph. http://en.wikipedia.org/wiki/Polygraph, January 2008.
• 29: Edward Wobber , Martín Abadi , Michael Burrows , Butler Lampson, Authentication in the Taos operating system, ACM Transactions on Computer Systems (TOCS), v.12 n.1, p.3-32, Feb. 1994 [doi>10.1145/174613.174614]
• 30: Nickolai Zeldovich , Silas Boyd-Wickizer , Eddie Kohler , David Mazières, Making information flow explicit in HiStar, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

General Terms:
Algorithms, Design, Reliability, Security

Keywords:
compromise recovery, replication