We are currently investigating a broad spectrum of topics in security, cryptography, and privacy. These topics range from fundamental research on privacy in the context of statistical databases to new systems mechanisms for realizing security in operating systems to mitigating and preventive measures against worms and viruses.

Martín Abadi, Andrew Birrell, Mihai Budiu, Cynthia Dwork, Frank McSherry, Ilya Mironov, Kunal Talwar, Ted Wobber, Yinglian Xie, Fang Yu, Lintao Zhang, Lidong Zhou

Community Information Management

Expanding on the notion of personal information management (PIM), the Community Information Management (CIM) project is exploring system support for loosely structured, semitrustful communities with common information needs. We propose a new security model for loosely-coupled distributed systems using invariant statements by trusted parties and logical proofs.

Database Privacy

Statistical databases such as are produced by the US Census contain a large volume of illuminating and potentially useful data. They also run the risk of revealing a great deal of specific information about the participants, which participants generally dislike. There is an inherent tradeoff between the utility that databases can offer and the privacy they afford their constituents. We are studying this tradeoff formally, attempting to understand the relationship between privacy and utilily, and thereby find a comfortable position between the extremes of fully disclosed and completely withheld data.

Gleipnir

The Gleipnir project is an investigation into security mechanisms that mitigate software vulnerabilities, i.e., without eliminating the underlying program errors make vulnerabilities difficult or impossible to exploit in a successful attack.One particular strategy we are exploring is a provably-correct security mechanism that can prevent powerful attackers from being able to execute machine code of their choice (so called code injection attacks). We are studying several efficient implementations of this strategy based on variants of Inlined Reference Monitors, or program instrumentation. We are also investigating runtime security mitigation mechanisms based on operating system modifications.

S-GPS

Spamming has been a growing problem in the Internet. This project focuses on spammer identification rather than spam identification, and we seek to identify zombie-based spammers. We explore host network properties (for example: proxy/NAT servers, dynamically assigned IP addresses), and correlate such fine-grained information with network telescope traces and spammimg activities. We emphasize that spammer identification at the network level is independent of spam content and is often straightforward to integrate with existing filtering frameworks.

Penny Black

The Penny Black project has investigated several techniques to reduce spam. In a nutshell, the idea is this: "If I don't know you, and you want to send me mail, then you must prove to me that you have expended a certain amount of effort, just for me and just for this message." The approach is fundamentally an economic one. Suppose we measure effort in CPU cycles. Since there are about 80,000 seconds in a day, a computational "price" of just ten seconds per message would limit a spamming computer to at most 8,000 messages daily. So spammers would have to invest heavily in hardware in order to send high volumes of spam.

Singularity

The Singularity project is focused on the construction of dependable systems through innovation in the areas of systems, languages, and tools. As part of the overall Singularity effort, we are defining a new security model and implementing it in the context of the Singularity prototype OS. In our design, we leverage the process isolation inherent in Singularity by statically limiting processes to resources that are specifically declared in application manifests. Where dynamic access control is necessary, Singularity security principals embody a flexible notion of authentication. They are compound principals that reflect the identities of the programs that have executed, even those of login programs. These identities are based on a naming tree. Our access control lists are patterns that recognize principals.

VEXE'DD

Virtual EXtension Environments for Device Drivers (or VEXE'DD for short) examines ways of using virtualization to provide reliability, security, and robust backward compatibility for extensible systems. The project uses the problem of supporting existing third-party Windows WDM device driver binaries as its motivating problem. The idea behind VEXE'DD is to execute potentially troublesome extensions in a virtual container that is separate and isolated from the rest of the system. In the original container, a generic proxy provides the desired functionality by using the virtual container as an oracle for requests that would have involved the extension.

Vigilante

Worm containment must be automatic because worms can spread too fast for humans to respond. Recent work has proposed network-level techniques to automate worm containment; these techniques have limitations because there is no information about the vulnerabilities exploited by worms at the network level. We propose Vigilante, a new end-to-end approach to contain worms automatically that addresses these limitations. Vigilante relies on collaborative worm detection at end hosts, but does not require hosts to trust each other. Hosts run instrumented software to detect worms and broadcast self-certifying alerts (SCAs) upon worm detection. SCAs are proofs of vulnerability that can be inexpensively verified by any vulnerable host. When hosts receive an SCA, they generate filters that block infection by analysing the SCA-guided execution of the vulnerable software. We show that Vigilante can automatically contain fast-spreading worms that exploit unknown vulnerabilities without blocking innocuous traffic.

• Yinglian Xie, Fang Yu, Kannan Achan, Eliot Gillum, Moises Goldszmidt, and Ted Wobber, How dynamic are IP addresses?  In Proceedings of the Conference on Computer Communications (Sigcomm), Kyoto, Japan, August 27-31, 2007, pages 301-312.
• Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar, Privacy, accuracy, and consistency too: a holistic solution to contingency table release, In Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Leonid Libkin (eds.), Beijing, China, June 11-13, 2007, pages 273-282.
• Cynthia Dwork, Frank McSherry, and Kunal Talwar, The price of privacy and the limits of LP decoding, In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), David S. Johnson and Uriel Feige (eds.), San Diego, California, USA, June 11-13, 2007, pages 85-94.
• Ulfar Erlingsson, Benjamin Livshits, and Yinglian Xie, End-to-End Web Application Security, In Usenix Workshop on Hot Topics in Operating Systems (HotOs), San Diego, CA, May 7-9, 2007.
• Ted Wobber, Aydan Yumerefendi,, Martín Abadi, Andrew Birrell, and Dan Simon,  Authorizing applications in Singularity, In European Conference on Computer Systems (EuroSys), Lisbon, Portugal, March 21-23, 2007.
• Galen Hunt, Chris Hawblitzel, Orion Hodson, James Larus, Bjarne Steensgaard, and Ted Wobber, Sealing OS processes to improve dependability and safety, In European Conference on Computer Systems (EuroSys), Lisbon, Portugal, March 21-23, 2007.
• Martín Abadi and Boon Thau Loo, Towards a Declarative Language and System for Secure Networking, In International Workshop on Networking Meets Databases (NetDB '07), Cambridge, MA, April 10, 2007.
• Nathan Keller, Stephen D. Miller, Ilya Mironov, and Ramarathnam Venkatesan, MV3: A new word based stream cipher using rapid mixing and revolving buffers, In Topics in Cryptology (CT-RSA 2007), Masayuki Abe (eds.), San Francisco, CA, February, 2007.
• Cynthia Dwork, Ask a Better Question, Get a Better Answer A New Approach to Private Data Analysis, In 11th International Conference on Database Theory (ICDT 2007), Thomas Schwentick and Dan Suciu (eds.), Barcelona, Spain, January 10-12, 2007, pages 18-27.
• Martín Abadi, Ricardo Corin, and Cédric Fournet, Computational Secrecy by Typing for the Pi Calculus, In Fourth ASIAN Symposium on Programming Languages and Systems (APLAS 2006), University of New South Wales, Sydney, Australia, November 8-10, 2006.
• Úlfar Erlingsson, Martín Abadi, Michael Vrable, Mihai Budiu, and George C. Necula, XFI: XFI: Software Guards for System Address Spaces, In Symposium on Operating System Design and Implementation (OSDI), Seattle, WA, November 6-8, 2006.
• Mihai Budiu, Úlfar Erlingsson, and Martín Abadi, Architectural Support for Software-Based Protection, In Workshop on Architectural and System Support for Improving Software Dependability (ASID), San Jose, CA, October 21, 2006, A version appeared as MSR-TR-2006-115.
• Avik Chaudhuri and Martín Abadi, Formal Analysis of Dynamic, Distributed File-System Access Controls, In Formal Techniques for Networked and Distributed Systems (FORTE 2006), Paris, France, September 26-29, 2006, pages 99-114.
• Martín Abadi, Access control in a core calculus of dependency, In International Conference on Functional Programming (ICFP), Portland, Oregon, September 18-20, 2006, 263 - 273 pages.
• Avik Chaudhuri and Martín Abadi, Secrecy by Typing and File-Access Control, In 19th IEEE Computer Security Foundations Workshop (CSFW), S. Servolo Island, Venice, Italy, July 5-7, 2006, pages 112-123.
• Galen C. Hunt, Mark Aiken, Paul Barham, Manuel Fähndrich, Chris Hawblitzel, Orion Hodson, James R. Larus, Steven Levi, Nick Murphy, Bjarne Steensgaard, David Tarditi, Ted Wobber, Brian D. Zill, Sealing OS Processes to Improve Dependability and Security , Technical Report MSR-TR-2006-51, Microsoft Research, April 2006.
• Martín Abadi, Mihai Budiu, Úlfar Erlingsson, and Jay Ligatti, Control-Flow Integrity, In ACM Conference on Computer and Communication Security (CCS), Alexandria, VA, November 7-11, 2005.
• Martín Abadi, Mihai Budiu, Úlfar Erlingsson, and Jay Ligatti, A Theory of Secure Control-Flow, In International Conference on Formal Engineering Methods (ICFEM), Manchester, UK, November 1-4, 2005.
• Galen Hunt, James R. Larus, Martín Abadi, Mark Aiken, Paul Barham, Manuel Fahndrich, Chris Hawblitzel, Orion Hodson, Steven Levi, Nick Murphy, Bjarne Steensgaard, David Tarditi, Ted Wobber, and Brian D. Zill, An Overview of the Singularity Project, Technical Report MSR-TR-2005-135, Microsoft Research, October 2005.
• Manuel Costa, Jon Crowcroft, Miguel Castro, Antony Rowstron, Lidong Zhou, Lintao Zhang, and Paul Barham, Vigilante: End-to-End Containment of Internet Worms, In ACM Symposium on Operating Systems Principles (SOSP), Brighton, UK, October 23-26, 2005.
• Cynthia Dwork, Moni Naor, and Hoeteck Wee, Pebbling and Proofs of Work, In Twenty-Fifth Annual International Cryptology Conference (CRYPTO 05), University of California, Santa Barbara, August, 2005.
• Lidong Zhou, Fred B. Schneider, and Robbert Van Renesse, APSS: proactive secret sharing in asynchronous systems, In ACM Transactions on Information System Security, Vol. 8, no 3, August, 2005, pages 259-286.
• Shuchi Chawla, Cynthia Dwork, Frank McSherry, and Kunal Talwar, On Privacy-Preserving Histograms, In Uncertainty in Artificial Intelligence, Edinburgh, Scotland, July, 2005.
• Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim, Practical Privacy: The SuLQ Framework, In 24th ACM SIGMOD International Conference on Management of Data / Principles of Database Systems, Baltimore (PODS 2005), Baltimore, Maryland, USA, June 13-16, 2005.
• Lidong Zhou, Michael A. Marsh, Fred B. Schneider, and Anna Redz, Distributed Blinding for Distributed ElGamal Re-encryption, In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS 2005), Columbus, OH USA, June 6-10, 2005, pages 815-824.
• Martín Abadi, Andrew Birrell, and Ted Wobber.  Access control in a world of software diversity.  In Proceedings of Tenth Workshop on Hot Topics in Operating Systems, Santa Fe, N.M., June 2005.
• Úlfar Erlingsson, Tom Roeder, and Ted Wobber. Virtual Environments for Unreliable Extensions.  Technical Report MSR-TR-2005-82, Microsoft Research,  June 2005.
• Martín Abadi, Mike Burrows, Mark Manasse, and Ted Wobber. Moderately Hard, Memory-bound Functions.  ACM Transactions on Internet Technology, 5(2): 299-327, May 2005.
• Lidong Zhou, Lintao Zhang, Frank McSherry, Nicole Immorlica, Manuel Costa, and Steve Chien, A First Look at Peer-to-Peer Worms: Threats and Defenses, In 4th International Workshop on Peer-To-Peer Systems (IPTPS '05), Ithaca, New York, USA, February, 2005.
• Shuchi Chawla, Cynthia Dwork, Frank McSherry, Adam Smith, and Hoeteck Wee, Toward Privacy in Public Databases, In Second Theory of Cryptography Conference, (TCC 2005), Joe Kilian (eds.), Cambridge, MA, USA, February 10-12, 2005, pages 363-385.
• Martín Abadi and Ted Wobber, A Logical Account of NGSCB,  In Proceedings of Formal Techniques for Networked and Distributed Systems -- Forte 2004, Madrid, Spain, September 2004.
• Cynthia Dwork and Kobbi Nissim, Privacy-Preserving Datamining on Vertically Partitioned Databases, In 24th Annual International Cryptology Conference (CRYPTO 2004), Matthew K. Franklin (eds.), Santa Barbara, California, USA, August 15-19, 2004, pages 528-544.
• Martín Abadi, Andrew Birrell, Mike Burrows, Frank Dabek, and Ted Wobber, Bankable Postage for Network Services, In Proceedings of the 8th Asian Computing Science Conference, Mumbai, India, December 2003.
• Cynthia Dwork, Andrew Goldberg, and Moni Naor, On Memory-Bound Functions for Fighting Spam, In Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO 2003), pages 426-444, Santa Barbara, CA, August 2003.