Topics in Programming Languages — CS 8561 - 001 — Spring 2010

Course Information

Course Overview

 This special topics course is a research seminar in software quality. The course will focus on active research areas in programming languages and software engineering, but the specific topics will be largely determined by a combination of instructor fiat and the interests of the students.

Entrance Quiz

 To ensure that the discussions are lively and fruitful, there will be a limit on the size of the class. If demand exceeds supply, interested students may be required to take a brief quiz to demonstrate the required background; admission to the class will be partially decided by quiz performance.

Structure & Presentations

 At the beginning of each paper discussion I will choose up to three students at random. Each student will give a five-minute presentation that at least (1) summarizes the work, (2) lists its strengths, and (3) lists ways in which it might be improved in a subsequent publication. Including other information, such as your opinion about the work, or its relation to other work you may be aware of, is also fine.

The goals of this approach are to encourage all participants to read the material thoroughly in advance, to provide jumping-off points for detailed discussions, and to allow me to evaluate participation.

There is no project component to this course — your primary responsibility is to prepare five minutes of cogent discussion for each paper.

Grading

Grading will be based entirely on participation. One sufficient condition for an "A" grade is to do a good job whenever you are called on to present a paper and to interject insightful comments into the discussions of other papers.

First Class Meeting

 The first meeting will take place on Monday, January 25th (at the usual time and place: 2pm in Olsson 236D). You are responsible for reading the first three papers. However, I will get the discussion rolling for Paper #1 (Producing wrong data ...), so you do not need to prepare a presentation for it. The discussion for it will probably be short.

I will begin randomly calling on students when we advance to Paper #2 and Paper #3. You should prepare your five minute discussions for those two papers.

Reading List

On average, we will discuss three papers a week (devoting perhaps 50 minutes to each paper). However, some papers may merit more or less discussion. You are responsible for reading at least two papers in advance for any given discussion.

    General Systems Research

  1. Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, Peter F. Sweeney: Producing wrong data without doing anything obviously wrong! ASPLOS 2009: 265-276

    Static Bug Detection

  2. Dawson R. Engler, David Yu Chen, Andy Chou: Bugs as Inconsistent Behavior: A General Approach to Inferring Errors in Systems Code. SOSP 2001: 57-72
  3. Nathaniel Ayewah, David Hovemeyer, J. David Morgenthaler, John Penix, William Pugh: Using Static Analysis to Find Bugs. IEEE Software 25(5): 22-29 (2008)
    [ Project Website ] [ Unrelated-But-Good Slides ]

    Automated Debugging

  4. Andreas Zeller: Yesterday, My Program Worked. Today, It Does Not. Why? ESEC / SIGSOFT FSE 1999: 253-267
    (ACM SIGSOFT 10 Year Impact Award) [ Keynote Talk Video ] [ Project Website ] [ Popular Free Implementation ]
  5. James A. Jones, Mary Jean Harrold: Empirical evaluation of the tarantula automatic fault-localization technique. ASE 2005: 273-282
    [ Project Website ]
  6. Gaeul Jeong, Sunghun Kim, Thomas Zimmermann: Improving bug triage with bug tossing graphs. ESEC/SIGSOFT FSE 2009: 111-120

    Program Repair

  7. David E. Lowell, Subhachandra Chandra, Peter M. Chen: Exploring Failure Transparency and the Limits of Generic Recovery. OSDI 2000: 289-304
  8. George C. Necula, Jeremy Condit, Matthew Harren, Scott McPeak, Westley Weimer: CCured: type-safe retrofitting of legacy software. ACM Trans. Program. Lang. Syst. 27(3): 477-526 (2005)
  9. Jeff H. Perkins, Sunghun Kim, Sam Larsen, Saman P. Amarasinghe, Jonathan Bachrach, Michael Carbin, Carlos Pacheco, Frank Sherwood, Stelios Sidiroglou, Greg Sullivan, Weng-Fai Wong, Yoav Zibin, Michael D. Ernst, Martin C. Rinard: Automatically patching errors in deployed software. SOSP 2009: 87-102
  10. Westley Weimer, ThanhVu Nguyen, Claire Le Goues, Stephanie Forrest: Automatically finding patches using genetic programming. ICSE 2009: 364-374
    (Best Paper Award)

    Dataflow Analysis

  11. Thomas W. Reps, Susan Horwitz, Shmuel Sagiv: Precise Interprocedural Dataflow Analysis via Graph Reachability. POPL 1995: 49-61
  12. Glenn Ammons, James R. Larus: Improving data-flow analysis with path profiles (with retrospective). Best of PLDI 1998: 568-582
    (Best Paper Award)
  13. Sumit Gulwani, George C. Necula: Precise interprocedural analysis using random interpretation. POPL 2005: 324-337
  14. Ben Hardekopf, Calvin Lin: The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. PLDI 2007: 290-299
    (Best Paper Award)

    Binary Analysis

  15. Peter B. Kessler: Fast breakpoints: design and implementation (with retrospective). Best of PLDI 1990: 390-397
    (Best Paper Award)
  16. Amitabh Srivastava, Alan Eustace: ATOM: a system for building customized program analysis tools (with retrospective). Best of PLDI 1994: 528-539
    (Best Paper Award)
  17. Junghee Lim, Thomas W. Reps: A System for Generating Static Analyzers for Machine Instructions. CC 2008: 36-52
    (Best Paper Award) [ Slides ]

    Test Case Generation

  18. Patrice Godefroid, Nils Klarlund, Koushik Sen: DART: directed automated random testing. PLDI 2005: 213-223
    [ Slides ]
  19. Cristian Cadar, Daniel Dunbar, Dawson R. Engler: KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. OSDI 2008: 209-224
    (Best Paper Award)
  20. Raul A. Santelices, Pavan Kumar Chittimalli, Taweesup Apiwattanapong, Alessandro Orso, Mary Jean Harrold: Test-Suite Augmentation for Evolving Software. ASE 2008: 218-227
    (Best Paper Award)

    Testing

  21. A. Rivers and M. Vouk. Resource-Constrained Non-Operational Testing of Software. ISSRE 1998: 154-163
    (Best Paper Award) [ link goes to Book Chapter, which has similar text to ISSRE paper ]
  22. Gregg Rothermel, Roland H. Untch, Chengyun Chu, Mary Jean Harrold: Prioritizing Test Cases For Regression Testing. IEEE Trans. Software Eng. 27(10): 929-948 (2001)
  23. Sara Sprenkle, Sreedevi Sampath, Emily Gibson, Lori L. Pollock, Amie L. Souter: An Empirical Comparison of Test Suite Reduction Techniques for User-Session-Based Testing of Web Applications. ICSM 2005: 587-596
    [ PDF Link ]
  24. Audris Mockus, Nachiappan Nagappan, and Trung T. Dinh-Trong. Test coverage and post-verification defects: A multiple case study. Empirical Software Engineering and Measurement 2009: 291-301
    [ Slides ]

    Proof-Carrying Code

  25. J. Gregory Morrisett, David Walker, Karl Crary, Neal Glew: From System F to Typed Assembly Language. POPL 1998: 85-97
    [ Project Website ]
  26. George C. Necula, Peter Lee: The design and implementation of a certifying compiler (with retrospective) Best of PLDI 1998: 612-625
    (Best Paper Award) [ Project Website ]

    Parallel Programs

  27. Charles Edwin Killian, James W. Anderson, Ranjit Jhala, Amin Vahdat: Life, Death, and the Critical Transition: Finding Liveness Bugs in Systems Code NSDI 2007
    (Best Paper Award)
  28. Cormac Flanagan, Stephen N. Freund: FastTrack: efficient and precise dynamic race detection. PLDI 2009: 121-133

    Program Synthesis

  29. Armando Solar-Lezama, Christopher Grant Jones, Rastislav Bodik: Sketching concurrent data structures. PLDI 2008: 136-148
  30. Saurabh Srivastava, Sumit Gulwani, Jeffrey S. Foster: From program verification to program synthesis. POPL 2010: 313-326

    Invariant Generation

  31. Michael D. Ernst, Jake Cockrell, William G. Griswold, David Notkin: Dynamically Discovering Likely Program Invariants to Support Program Evolution. IEEE Trans. Software Eng. 27(2): 99-123 (2001)
    [ Slides ] [ Project Website ]
  32. Ashutosh Gupta, Rupak Majumdar, Andrey Rybalchenko: From Tests to Proofs. TACAS 2009: 262-276
    (Best Paper Award)

    Run-Time Optimization

  33. Peter Lee, Mark Leone: Optimizing ML with run-time code generation (with retrospective). Best of PLDI 1996: 540-553
    (Best Paper Award)
  34. Matteo Frigo: A fast Fourier transform compiler (with retrospective). Best of PLDI 1999: 642-655
    (Best Paper Award)

    Grab Bag

  35. Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar: Symbolic Algorithms for Infinite-State Games. CONCUR 2001: 536-550
    (Best Paper Award)
  36. David F. Bacon, C. Richard Attanasio, Han Bok Lee, V. T. Rajan, Stephen E. Smith: Java without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector. PLDI 2001: 92-103
  37. Christian Bird, Nachiappan Nagappan, Premkumar T. Devanbu, Harald Gall, Brendan Murphy: Does distributed development affect software quality? An empirical case study of Windows Vista. ICSE 2009: 518-528
    (Appears in CACM Research Highlights)
  38. Paul Ammann, John C. Knight: Data Diversity: An Approach to Software Fault Tolerance. IEEE Trans. Computers 37(4): 418-425 (1988)