Princeton University Computer Science Department

Computer Science 592 Seminar in Computer Systems Liviu Iftode and Kai Li

Spring 2006

Course Summary

The goal of this seminar is to provide a snapshot of recent research in computer systems community by reading and discussing selected papers in recent systems conferences such as ASPLOS, FAST, HotNets, ISCA, NSDI, OSDI, SIGCOMM, SOSP, WWW, and others. 

The seminar has tentatively selects some papers on the following topics: machine virtualization, new data structures for search and clustering, intrusion detection and recovery, trust computing, reliable systems, evolution and intelligent design of software systems, large-scale reliable services, next-generation storage systems, web data and queries, systems and programming in sensor networks, and programming multi-core processors.  Each week, students or faculty members will present papers on a specific topic and lead discussions. 

Students who are taking the course for credits are required to give one presentation on and to work on a small research project.  This course satisfies the programming requirement.

Note that COS598B has been cancelled and Prof. Larry Peterson will give a lecture to discuss some of the topics in his original seminar.

Administrative Information

Class meet: Friday 930am-1200noon, Room: 302, Computer Science Building

Professors:

• Liviu Iftode - 409 CS Building -258-4627 liv@cs.princeton.edu
• Kai Li - 321 CS Building - 258-4637 li@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu

Tentative Syllabus

Week 1 (2/10): Organization

Week 2 (2/17): Machine Virtualization

Presenter: Arati Baliga, Marc Fiuczynski

Readings

1. M Rosenblum and T. Garfinkel. Virtual Machine Monitors: Current Technology and Future Trends. IEEE Computer, 38/5, May 2005.
2. S. King, G. Dunlap and P. Chen. Operating System Support for Virtual Machines. Usenix 2003.
3. A. Whitaker, M. Shaw and S. Gribble. Scale and Performance in the Denali Isolation Kernel. OSDI, 2002.
4. 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. SOSP 2003.
5. R. Chandra, N. Zeldovich, C. Sapuntzakis, M. S. Lam. The Collective: A Cache-Based System Management Architecture. NSDI, 2005.

Additional Papers

1. P. Chen and B. Noble. When Virtual is Better than Real, HotOS 2001.
2. J. Sugerman, G. Venkitachalam and B-H. Lim. Virtualizing I/O Devices on VMware workstation's host VMM. Usenix 2001.
3. J.E. Smith and R. Navi. The Architecture of Virtual Machines. IEEE Computer, 38/5, May 2005.

Week 3 (2/24): New Data Structures for Search and Clustering

Presenters: Christine Lv, Zhe Wang

Readings

1. R. Panigrahy. Entropy based Nearest Neighbor Search in High Dimensions.  SODA, 2006.
2. K. Grauman and T. Darrell.  Efficient Image Matching with Distributions of Local Invariant Features. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition, San Diego, CA,  June 2005.
3. Mayank Bawa, Tyson Condie, Prasanna Ganesan. LSH Forest: Self-Tuning Indexes for Similarity Search.  WWW 2005.

Additional Papers

1. K. Grauman and T. Darrell. Fast Contour Matching Using Approximate Earth Mover's Distance.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Washington DC, June 2004.
2. A. Gionis, P. Indyk, R. Motwani.  Similarity Search in High Dimensions via Hashing. VLDB,. 1999.

Week 4 (3/3): Intrusion Detection and Recovery

Presenters: Arati Baliga, Martin Makowiecki

Readings

1. A. Joshi, S. King, G. Dunlap and P. Chen. Detecting Past and Present Intrusions through Vulnerability-Specific Predicates. SOSP 2005.
2. M. Costa, J. Crowcroft, M. Castro, A. Rowstron, L Zhou, L. Zhang and P. Barham. Vigilante: End-to-End Containment of Internet Worms. SOSP 2005.
3. D. Gao, M. Reiter and D. Song. Behavioral Distance for Intrusion Detection. RAID 2005.
4. A. Smirnov and T-C. Chiueh. DIRA: Automatic Detection, Identification and Repair of Control-Hijacking Attacks. NDSS 2005.

Additional Papers

1. S. King and P. Chen. Backtracking Intrusions. SOSP 2003.
2. A. Goel, K. Po, K. Farhadi, Z. Li and E de Lara. The Taser Intrusion Recovery System. SOSP 2005.
3. S. Singh, C. Estan, G. Varghese and S. Savage. Automated Worm Fingerprinting. OSDI 2004.
4. A. Pennington, J. Strunk, J. Griffin. C. Soules, G. Goodson and G. Ganger. Storage-based Intrusion Detection: Watching Storage Activity for Suspicious Behavior. Usenix Security 2003.

Week 5 (3/10): Trusted Computing

Presenters: Prof. Tore Larsen

Readings

1. E. Shi, A. Perrig and L. Van Doorn. BIND: A Fine-Grained Attestation Service for Secure Distributed Systems. IEEE Symposium on Security and Privacy, 2005.
2. A Seshadri, M. Luk, E. Shi, A. Perrig , L. Van Doorn and P. Khosla. Pioneer: Verifying Code Integrity and Enforcing Untampered Code Execution on Legacy Systems. SOSP 2005.
3. R. Sekar, V. Venkatakrishnan, S. Basu, S. Bhatkar, D. DuVarney. Model-Carrying Code: A Practical Approach for Safe Execution of Untrusted Applications. SOSP 2003.
4. P. Efstathopoulos, K. Krown, S. VanDeBogart, C. Frey, D. Ziegler, E. Kohler, D. Mazieres, F. Kaashoek and R. Morris. Labels and Event Processes in the Asbestos Operating System. SOSP 2005.

Additional Papers

1. D. Lie, C. Thekkath and M. Horowitz. Implementing an Untrusted OS on Trusted Hardware. SOSP 2003.
2. T. Garfinkel, B. Pfaff, J. Chow, M. Rosenblum and D. Boneh. Terra: A virtual Machine-Based Platform for Trusted Computing. SOSP 2003.
3. R. Sailer, T.Jaeger, X. Zhang and L. van Doorn. Design and Implementation of a TCG-based integrity measurement architecture. , Usenix Security, 2004.
4. G.E. Suh, J. Lee, D. Zhang and S. Devadas. Secure Program Execution via Dynamic Information Flow Tracking. ASPLOS 2004

Week 6 (3/17): Evolution and Intelligent Design of Software Systems

Presenter: Prof. Larry Peterson

Readings

1. L. Peterson, S. Shenker and J. Turner.  Overcoming the Internet Impasse Through Virtualization.  HotNet-III, 2004.
2. L. Peterson and T. Roscoe.  The Design Principles of PlanetLab, OSR, 2006. 
3. D.D. Clark, J. Wroclawski, K.R. Sollins, and R. Braden, Tussle in Cyberspace: Defining Tomorrow's Internet, SIGCOMM, 2002.

Additional Papers

Spring Break (3/18-3/26)

Week 7 (3/31): Reliable Systems

Presenters: Wei Dong and Yaping Zhu

Readings

1. M. Swift, M. Annamalai, Brian Bershad, and H. Levy. Recovering Device Drivers OSDI 2004.
2. J. Yang, P. Twohey, D. Engler and M. Musuvathi. Using Model Checking to Find Serious File System Errors OSDI 2004.
3. P. Zhou, W. Liu, F Long. S. Lu, F. Qin, Y. Zhou, S. Midkiff and J. Torrellas. AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-based Invariants. Micro 2004.
4. F. Qin, J. Tucek, J. Sundaresan and Y. Zhou. Rx: Treating Bugs As Allergies -- A Safe Method to Survive Software Failures SOSP 2005.

Additional Papers

1. M. Swift, B. Bershad and H. Levy. Improving the Reliability of Commodity Operating Systems. SOSP 2003.
2. M. Rinard, C. Cadar, D. Dumitran, D. Roy, T. Leu and W. Beebee Jr. Enhancing Server Availability and Security Through Failure-Oblivious Computing. , OSDI 2004.
3. F. Sultan, A. Bohra, P. Gallard, I. Neamtiu, S. Smaldone, Y. Pan and L. Iftode. Recovering Internet Service Sessions from Operating System Failures. IEEE Internet Computing, 2005.

Week 8 (4/7): Large-Scale Reliable Services

Presenters: Grant Wallace

Readings

1. L. Barroso, J. Dean and U. Hoelzle. Web Search for a Planet: The Google Cluster Architecture. IEEE MICRO, 2003.
2. S. Ghemawat, H. Gobioff, S-T. Leung. The Google File System. SOSP 2003
3. J. Dean and S. Ghemawat MapReduce: Simplified Data Processing on Large Clusters OSDI 2004.
4. X. Long and T. Suel. Three-Level Caching for Efficient Query Processing in Large Web Search Engines. WWW. 2005.

Additional Papers

1. R. Pike, S. Dorward, R. Griesemer and S. Quilan. Interpreting the Data: Parallel Analysis with Sawzall Submitted for publication.

Week 9 (4/14): New Generation Storage Systems

Presenters: Wei Dong and Yaiping Zhu

Readings

1. W Schlosser, J. Schindler, S. Papadomanolakis, M. Shao, A. Ailamaki, C. Faloutsos and G. Ganger. On Multidimensional Data and Modern Disks. Fast 2005.
2. M. Abd-El-Malek, W. Courtright II, C. Cranor, G. Ganger, J. Hendricks, A. Klosterman, M. Mesnier, M. Prasad, B. Salmon, R. Sambasivan, S. Sinnamohideen, J. Strunk, E. Thereska, M. Wachs and J. Wylie. Ursa Minor: Versatile Cluster-based Storage. Fast 2005.
3. C. Soules and G. Ganger. Connections: Using Context to Enhance File Search. SOSP 2005.
4. P. Maniatis, M. Roussopoulos, TJ Giuli, D. Rosenthal, M. Baker and Y. Muliadi. LOCKSS: A Peer-to-Peer Digital Preservation System. ACM TOCS, 2005.

Additional Papers

1. E. Nightingale, P. Chen and J. Flinn. Speculative Execution in Distributed File System. SOSP 2005.

Week 10 (4/21): No class meet due to Eurosys Conference

Week 11 (4/28): Systems and Programming in Sensor Networks

Presenters: Lars Ailo Bongo

Readings

1. P. Levis, S. Madden, D. Gay, J. Polastre, R. Szewczyk, A. Woo, E. Brewer and D. Culler. The Emergence of Networking Abstractions and Techniques in TinyOS. , NSDI 2004.
2. P. Levis, D. Gay and D. Culler. Active Sensor Networks. NSDI 2005.
3. K. Whitehouse, C. Sharp, E. Brewer and D. Culler. Hood: A Neighborhood Abstraction for Sensor Networks. , Mobisys 2004.
4. M. Welsh and G. Mainland. Programming Sensor Networks Using Abstract Regions. , NSDI 2004.

Additional Papers

1. J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler and K. Pister. System Architecture Directions for Networked Sensors. ASPLOS 2000.
2. C. Borcea, C. Intanagonwiwat, P. Kang, U. Kremer and L. Iftode. Spatial Programming using Smart Messages: Designand Implementation. , ICDCS 2004.
3. Y. Ni, U. Kremer, A. Stere and L. Iftode. Programming Ad-Hoc Networks of Mobile and Resource-Constrained Devices . , PLDI 2005.
4. H. Liu, T. Roeder, K. Walsh, R. Barr and E. G. Sirer. Design and Implementation of a Single System Image Operating System for Ad-Hoc Networks. Mobisys 2005.

Week 12 (5/5): Utility Computing and Server Resource Management

Presenters: Martin Makowiecki

Readings