Vitaly Shmatikov

Research interests: computer security and privacy, formal methods for analysis of secure systems and protocols

Teaching   -   Students   -   Papers   -   Fly!   -   3,627 snapshots   -   Contact

---

Teaching

• CS 378: Network Security and Privacy (Spring 2012)
• CS 380S: 0x1A Great Papers in Computer Security (last taught Fall 2011)
  • Previously Theory and Practice of Secure Systems (last taught Fall 2009)
• CS 345: Programming Languages (last taught Fall 2010)
• CS 178H: Introduction to CS Research-Honors (last taught Spring 2009)
• CS 395T: Design and Analysis of Security Protocols (last taught Fall 2004)
• CS 259 (Stanford): Security Analysis of Network Protocols (last taught Winter 2004)

---

Students

• Arvind Narayanan (PhD, May 2009)
  Thesis: Database Privacy: the Non-Interactive Setting
• Justin Brickell (PhD, May 2009)
  Thesis: Privacy-Preserving Computation for Data Mining

---

Research papers   (see in reverse chronological order)

Software and network security

• S. Jana, V. Shmatikov. Memento: Learning Secrets from Process Footprints. S&P (Oakland) 2012 - best student paper award.   [abstract, PDF, PS]
• S. Jana, V. Shmatikov. Abusing File Processing in Malware Detectors for Fun and Profit. S&P (Oakland) 2012.   [abstract, PDF, PS]
• V. Srivastava, M. Bond, K. McKinley, V. Shmatikov. A Security Policy Oracle: Detecting Security Holes Using Multiple API Implementations. PLDI 2011.   [abstract, PDF, PS]
• S. Son, K. McKinley, V. Shmatikov. RoleCast: Finding Missing Security Checks When You Do Not Know What Checks Are. OOPSLA 2011.   [abstract, PDF, PS]
• S. Jana, D. Porter, V. Shmatikov. TxBox: Building Secure, Efficient Sandboxes with System Transactions. S&P (Oakland) 2011.   [abstract, PDF, PS]
• S. Son, V. Shmatikov. SAFERPHP: Finding Semantic Vulnerabilities in PHP Applications. PLAS 2011.   [abstract]
• S. Jana, V. Shmatikov. EVE: Verifying Correct Execution of Cloud-Hosted Web Applications. HotCloud 2011.   [abstract, PDF, PS]
• E. Wong, V. Shmatikov. Get Off My Prefix! The Need for Dynamic, Gerontocratic Policies in Inter-domain Routing. DSN 2011.   [abstract]
• S. Son, V. Shmatikov. The Hitchhiker's Guide to DNS Cache Poisoning. SecureComm 2010.   [abstract, PDF, PS]
• M. Bond, V. Srivastava, K. McKinley, V. Shmatikov. Efficient, Context-Sensitive Detection of Real-World Semantic Attacks. PLAS 2010.   [abstract]
• R. Chang, G. Jiang, F. Ivančić, S. Sankaranarayanan, V. Shmatikov. Inputs of Coma: Static Detection of Denial-of-Service Vulnerabilities. CSF 2009.   [abstract]
• V. Shmatikov, M-H. Wang. Secure Verification of Location Claims with Simultaneous Distance Modification. ASIAN 2007.   [abstract, PDF, PS]
• V. Shmatikov, M-H. Wang. Security Against Probe-Response Attacks in Collaborative Intrusion Detection. LSAD 2007.   [abstract, PDF, PS]
• E. Wong, P. Balasubramanian, L. Alvisi, M. Gouda, V. Shmatikov. Truth in Advertising: Lightweight Verification of Route Integrity. PODC 2007.   [abstract]
• A. Mahimkar, J. Dange, V. Shmatikov, H. Vin, Y. Zhang. dFence: Transparent Network-based Denial of Service Mitigation. NSDI 2007.   [abstract, PDF, PS]
• A. Narayanan, V. Shmatikov. Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff. CCS 2005.   [abstract, PDF, PS]

Privacy

• J. Calandrino, A. Kilzer, A. Narayanan, E. Felten, V. Shmatikov. "You Might Also Like:" Privacy Risks of Collaborative Filtering. S&P (Oakland) 2011.   [abstract]
  
  • Blogs: Economist, Freedom to Tinker, 33 Bits of Entropy.
• A. Narayanan, V. Shmatikov. Myths and Fallacies of "Personally Identifiable Information". CACM (June 2010).
• I. Roy, S. Setty, A. Kilzer, V. Shmatikov, E. Witchel. Airavat: Security and Privacy for MapReduce. NSDI 2010.   [abstract]
• A. Narayanan, V. Shmatikov. De-anonymizing Social Networks (full version). S&P (Oakland) 2009.   [abstract, PDF, PS]
  
  • FAQ about this paper.
  • Media: BBC, Technology Review, New Scientist, InformationWeek, PC World (via IDG News), Austin Business Journal.
  • Blogs, etc.: Slashdot, Ars Technica, Schneier, Online Media Daily, Behavioral Insider, BizReport.
  • Foreign media: 20 Minuten, Die Presse, ma.hu, OSnews.pl, Gryziemy.net, Вебпланета, RBC Daily.
• J. Brickell, V. Shmatikov. Privacy-Preserving Classifier Learning. Financial Crypto 2009.   [abstract]
• J. Brickell, V. Shmatikov. The Cost of Privacy: Destruction of Data-Mining Utility in Anonymized Data Publishing. KDD 2008.   [abstract]
• A. Narayanan, V. Shmatikov. Robust De-anonymization of Large Sparse Datasets (How to Break Anonymity of the Netflix Prize Dataset). S&P (Oakland) 2008.   [abstract, PDF, PS]
  
  • FAQ about this paper.
  • Winner of the 2008 PET Award (press release).
  • Media: CNN, Slashdot, Wired, SecurityFocus, Spiegel, New Scientist.
• S. Jha, L. Kruger, V. Shmatikov. Towards Practical Privacy for Genomic Computation. S&P (Oakland) 2008.   [abstract, PDF, PS]
• J. Brickell, D. Porter, V. Shmatikov, E. Witchel. Privacy-Preserving Remote Diagnostics. CCS 2007.   [abstract, PDF, PS]
• S. Jarecki, V. Shmatikov. Efficient Two-Party Secure Computation on Committed Inputs. EUROCRYPT 2007.   [abstract]
• J. Brickell, V. Shmatikov. Efficient Anonymity-Preserving Data Collection. KDD 2006.   [abstract]
• P. Porras, V. Shmatikov. Large-Scale Collection and Sanitization of Network Security Data: Risks and Challenges. NSPW 2006.   [abstract, PDF, PS]
• A. Narayanan, V. Shmatikov. Obfuscated Databases and Group Privacy. CCS 2005.   [abstract, PDF, PS]
• J. Brickell, V. Shmatikov. Privacy-Preserving Graph Algorithms in the Semi-Honest Model. ASIACRYPT 2005.   [abstract, PDF, PS]
• S. Jarecki, V. Shmatikov. Probabilistic Escrow of Financial Transactions with Cumulative Threshold Disclosure. Financial Crypto 2005.   [abstract, PDF, PS]
• P. Lincoln, P. Porras, V. Shmatikov. Privacy-Preserving Sharing and Correlation of Security Alerts. USENIX Security 2004.   [abstract, PDF, PS]
• S. Jarecki, V. Shmatikov. Handcuffing Big Brother: an Abuse-Resilient Transaction Escrow Scheme. EUROCRYPT 2004.   [abstract, PDF, PS]
• D. Hughes, V. Shmatikov. Information Hiding, Anonymity and Privacy: A Modular Approach. J. Computer Security, 2004.   [abstract, PDF, PS]
  This paper was also presented at MFPS 2003 and supercedes:
  • V. Shmatikov, D. Hughes. Defining Anonymity and Privacy. WITS 2002.
• S. Jarecki, P. Lincoln, V. Shmatikov. Negotiated Privacy. ISSS 2002.   [abstract, PDF, PS]

      Mix networks:

• V. Shmatikov, M-H. Wang. Measuring Relationship Anonymity in Mix Networks. WPES 2006.   [abstract, PDF, PS]
• V. Shmatikov, M-H. Wang. Timing Analysis in Low-Latency Mix Networks: Attacks and Defenses. ESORICS 2006.   [abstract, PDF, PS]
• R. Dingledine, V. Shmatikov, P. Syverson. Synchronous Batching: From Cascades to Free Routes. PET 2004.   [abstract, PDF, PS]

Formal methods for security protocols

• P. Gupta, V. Shmatikov. Security Analysis of Voice-over-IP Protocols. CSF 2007.   [abstract, PDF, PS]
• R. Chang, V. Shmatikov. Formal Analysis of Authentication in Bluetooth Device Pairing. FCS-ARSPA 2007.   [abstract]
• G. Norman, V. Shmatikov. Analysis of Probabilistic Contract Signing. J. Computer Security, 2006.   [abstract, PDF, PS]
  This paper supercedes:
  • G. Norman, V. Shmatikov. Analysis of Probabilistic Contract Signing. FASec 2002.
• P. Gupta, V. Shmatikov. Key Confirmation and Adaptive Corruptions in the Protocol Security Logic. FCS-ARSPA 2006.   [abstract, PDF, PS, full version]
• P. Gupta, V. Shmatikov. Towards Computationally Sound Symbolic Analysis of Key Exchange Protocols. FMSE 2005.   [abstract, PDF, PS, full version with proofs]
• A. Datta, A. Derek, J.C. Mitchell, V. Shmatikov, M. Turuani. Probabilistic Polynomial-Time Semantics for a Protocol Security Logic. ICALP 2005.   [abstract, PDF, PS]
• A. Mahimkar, V. Shmatikov. Game-Based Analysis of Denial-of-Service Prevention Protocols. CSFW 2005.   [abstract, PDF, PS]
  The paper in the CSFW proceedings contains a bug in the verification conditions. This is the corrected version.
• J. Millen, V. Shmatikov. Symbolic Protocol Analysis with an Abelian Group Operator or Diffie-Hellman Exponentiation. J. Computer Security, 2005.   [abstract, PDF, PS]  
  Warning: Contains serious bugs in the proofs; corrections coming eventually.
  This paper supercedes:
  • J. Millen, V. Shmatikov. Symbolic Protocol Analysis with Products and Diffie-Hellman Exponentiation. CSFW 2003.
• A. Datta, R. Küsters, J.C. Mitchell, A. Ramanathan, V. Shmatikov. Unifying Equivalence-Based Definitions of Protocol Security. WITS 2004.   [abstract, PDF, PS]
• V. Shmatikov. Probabilistic Model Checking of an Anonymity System. J. Computer Security, 2004.   [abstract, PDF, PS]
  This paper supercedes:
  • V. Shmatikov. Probabilistic Analysis of Anonymity. CSFW 2002.
• R. Chadha, J.C. Mitchell, A. Scedrov, V. Shmatikov. Contract Signing, Optimism, and Advantage. CONCUR 2003.   [abstract, PDF, PS]
  Revised journal version containing all proofs:
  • R. Chadha, J.C. Mitchell, A. Scedrov, V. Shmatikov. Contract Signing, Optimism, and Advantage (with proofs). J. Logic and Algebraic Programming, 2005.
• V. Shmatikov. Decidable Analysis of Cryptographic Protocols with Products and Modular Exponentiation. ESOP 2004.   [abstract, PDF, PS]
• H. Comon-Lundh, V. Shmatikov. Intruder Deductions, Constraint Solving and Insecurity Decision in Presence of Exclusive or. LICS 2003.   [abstract, PDF, PS]
• H. Comon, V. Shmatikov. Is It Possible to Decide Whether a Cryptographic Protocol Is Secure Or Not?. J. Telecommunications and Information Technology, 2002.   [abstract, PDF, PS]
• V. Shmatikov, J.C. Mitchell. Finite-State Analysis of Two Contract Signing Protocols. Theoretical Computer Science, 2002.   [abstract, PDF, PS]
  This paper supercedes the following three papers:
  • V. Shmatikov, J.C. Mitchell. Analysis of Abuse-Free Contract Signing. Financial Crypto 2000.
  • V. Shmatikov, J.C. Mitchell. Analysis of a Fair Exchange Protocol. NDSS 2000.
  • V. Shmatikov, J.C. Mitchell. Analysis of a Fair Exchange Protocol. FLOC Workshop on Formal Methods and Security Protocols, 1999.
• J. Millen, V. Shmatikov. Constraint Solving for Bounded-Process Cryptographic Protocol Analysis. CCS 2001 - "test of time" award by CCS 2011.   [abstract, PDF, PS]
• V. Shmatikov, U. Stern. Efficient Finite-State Analysis for Large Security Protocols. CSFW 1998.   [abstract, PDF, PS]
• J.C. Mitchell, V. Shmatikov, U. Stern. Finite-State Analysis of SSL 3.0. USENIX Security 1998.   [abstract, PDF, PS]
  This paper supercedes:
  • J.C. Mitchell, V. Shmatikov, U. Stern. Finite-State Analysis of SSL 3.0 and Related Protocols. DIMACS Workshop on Design and Formal Verification of Security Protocols, 1997.

Trust management

• V. Shmatikov, C. Talcott. Reputation-Based Trust Management. J. Computer Security, 2005.   [abstract, PDF, PS]
  This paper supercedes:
  • V. Shmatikov, C. Talcott. Reputation-Based Trust Management. WITS 2003.

Foundations of programming languages

• V. Bono, A. Patel, V. Shmatikov. A Core Calculus of Classes and Mixins. ECOOP 1999.   [abstract, PDF, PS]
  
• V. Bono, A. Patel, V. Shmatikov, J.C. Mitchell. A Core Calculus of Classes and Objects. MFPS 1999.   [abstract, PDF, PS]
  

---

Contact information

Department of Computer Science
The University of Texas at Austin
1 University Station D9500
Austin, TX   78712   U.S.A.

email: first five letters of last name AT cs.utexas.edu
phone: +1-512-471-9530 (voicemail not checked)
office: CSA 1.114

---

The face was drawn, the eyes haggard, the general appearance that of one who has searched for the leak in life's gaspipe with a lighted candle.
      -- P.G.Wodehouse, "The Old Reliable"