March 2008

I am a researcher in the Networking Research Group within Microsoft Research. My current research focus is the Cloud Services Infrastructure Project. I have previously been associated with the Distributed Systems and Security Group, the Theory Group and the Systems Management Group.

My CV is available here.

In May of 2002, I completed my PhD in Applied Mathematics at the Massachusetts Institute of Technology. My work was in algorithms under the supervision of Professor Santosh Vempala. We spent a lot of our time in the Laboratory for Computer Science which has a very collegial Theory of Computation Group.

I am not currently seeking any internship candidates. If you are interested in applying for an internship to Microsoft Research, please use this tool.

My recent work:

• Characterizing Botnets from Spam:

  Characterizing Botnets from Email Spam Records Appeared in Workshop on Large-Scale Exploits and Emergent Threats (LEET) 2008. Joint work with Li Zhuang, Daniel R. Simon, Helen J. Wang, Ivan Osipkov, Geoff Hulten and J. D. Tygar.

• Investigating PC Unresponsiveness:

  Why Did My PC Suddenly Slow Down? Appeared in Workshop on Tackling Computer Systems Problems with Machine Learning Techniques (SysML) 2007. Joint work with Sumit Basu and Greg Smith.

• Solving Systems of Linear Equations:

  Iteratively Constructing Preconditioners via the Conjugate Gradient Method. To appear in Symposium on Theory of Computing (STOC) 2007. Joint work with Nicholas J. A. Harvey.

• Infrastructure for Analyzing Network Protocols:

  Generic Application-Level protocol Analyzer and its Language. Appeared in Network and Distributed System Security (NDSS) 2007. Joint work with David Brumley, Nikita Borisov, Helen Wang, Pallavi Joshi and Chuanxiong Guo.

• Protecting Web Browsers using JavaScript Virtualization:

  BrowserShield: Vulnerability-Driven Filtering of Dynamic HTML. Appeared in Operating Systems Design and Implementation (OSDI) 2006. Joint work with Charlie Reis, Helen Wang, Opher Dubrovsky, and Saher Esmeir.

• Measuring Shellcode Polymorphism:

  Finding Diversity in Remote Code Injection Exploits. Appeared in Internet Measurement Conference (IMC) 2006. Joint work with Justin Ma, Helen Wang, Stefan Savage, and Geoffrey Voelker.

• Applying Machine Learning to Analyzing Network Protocols:

  Automatically Extracting Fields from Unknown Network Protocols. Appeared in Systems and Machine Learning Workshop (SysML) 2006. Joint work with Karthik Gopalratnam, Sumit Basu, and Helen Wang.

• Security Access Tracing:

  A Black-Box Tracing Technique to Identify Causes of Least-Privilege Incompatibilities. Appeared in Network and Distributed System Security Symposium (NDSS) 2005. Joint work with Shuo Chen, Chad Verbowski, and Yi-Min Wang.

• Failure Detection and Notification:

  FUSE: Lightweight Guaranteed Distributed Failure Notification.  Appeared in Operating Systems Design and Implementation (OSDI) 2004. Joint work with Nicholas J. A. Harvey, Michael B. Jones, Dejan Kostic, Marvin Theimer, and Alec Wolman.  

• Channel Hopping Strategies for Wireless Networks:

  SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks. Appeared in International Conference on Mobile Computing and Networking (Mobicom) 2004. Joint work with Ranveer Chandra and Victor Bahl. This and related technologies are discussed in more detail on the MultiNet home page and the MSR Networking Research Group's software page.

• Black-box Troubleshooting:

  STRIDER: A Black-box, State-based Approach to Change and Configuration Management and Support. Appeared in Usenix Large Installation System Administration Conference (LISA) 2003 (Best Paper). Joint work with Yi-Min Wang, Chad Verbowski, Yu Chen, Helen J. Wang, Chun Yuan, and Zheng Zhang.

• Patch Management:

  Towards A Self-Managing Software Patching Process Using Black-Box Persistent State Manifests. Appeared in International Conference on Autonomic Computing (ICAC) 2004. Joint work with Roussi Roussev, Brad Daniels, Aaron Johnson, Chad Verbowski, and Yi-Min Wang.

• Peer-to-peer Overlay Networks:

  SkipNet: A Scalable Overlay Network with Practical Locality Properties. Appeared as Microsoft Research Technical Report. Joint work with Nicholas J. A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer, and Alec Wolman.

• Overlay Multicast Trees:

  Subscriber/Volunteer Trees: Polite, Efficient Overlay Multicast Trees.  Appeared as Microsoft Research Technical Report. Joint work with Nicholas J. A. Harvey, Michael B. Jones, Marvin Theimer, and Alec Wolman.  

• Experience Implementing a Peer-to-peer System

  Engineering Realities of Building a Working Peer-to-Peer System.  Appeared as Microsoft Research Technical Report. Joint work with Michael B. Jones.  

My earlier work in algorithms:

• Outliers:

  Optimal Outlier Removal in High-Dimensional Space. Invited to appear in Journal of Computer and System Sciences (JCSS). Joint work with Santosh Vempala.

  An older version of this paper appeard in Symposium on Theory of Computing (STOC) 2001. The current version corrects some statements from the older version.

• Linear Programming:

  "Smoothed Analysis of the Perceptron Algorithm for Linear Programming. Joint work with Avrim Blum. Appeared in Symposium on Discrete Algorithms (SODA) 2002, and invited to appear in Journal of Algorithms.

  Smoothed Analysis of the Renegar's Condition Number for Linear Programming. Appeared in SIAM Conference on Optimization (SIOPT) 2002. Joint work with Dan Spielman and Shang-Hua Teng.

  A Polynomial-time Rescaling Algorithm for Solving Linear Programs. Appeared in Symposium on Theory of Computing (STOC) 2004, and then in the journal Mathematical Programming: Series A. Joint work with Santosh Vempala.

• Thesis Work:

  A Geometric Theory of Outliers and Perturbation. The thesis contains most of the work in the the paper on outliers and the two papers on smoothed analysis of linear programming plus some additional discussion.

• Approximation Algorithms:

  On Euclidean Embeddings and Bandwidth Minimization. Appeared in Workshop on Randomization and Computation (RANDOM) 2001. Joint work with Santosh Vempala.

John Dunagan
Microsoft Research
One Microsoft Way
Redmond WA 98052
jdunagan@microsoft.com