6.893 Readings

Memory errors

Sep. 10:

• Efficient detection of all pointer and array access errors by Todd M. Austin, Scott E. Breach, and Gurindar S. Sohi. PLDI '94.
  6.893 slides
• (Optional)
  Purify: A tool for detecting memory leaks and access errors in C and C++ programs, by Reed Hastings and Bob Joyce. Winter 1992 USENIX Conference.
• Static detection of dynamic memory errors by David Evans. PLDI '96.
  6.893 slides

Concept analysis

Sep 12:

• Reengineering of Configurations Based on Mathematical Concept Analysis by Gregor Snelting. ACM TOSEM 5(2), 1996.
  6.893 slides
• (Optional; a later paper making similar points)
  Understanding class hierarchies using concept analysis by Gregor Snelting and Frank Tip. ACM TOPLAS 22(3), 2000.
• The concept of dynamic analysis by Thomas Ball. ESEC/FSE '99.
  6.893 slides

6.893 critiques

Program analysis for software engineering

Sep 19:

• Program analysis for software engineering: new applications, new requirements, new tools by Daniel Le Métayer. ACM Computing Surveys 28(4es), 1996.

Dynamic invariant detection

Sep 19:

• (skim pages 12-18; read the rest more carefully)
  Dynamically Discovering Likely Program Invariants to Support Program Evolution by Michael D. Ernst, Jake Cockrell, William G. Griswold, and David Notkin. IEEE Transactions in Software Engineering 27(2), 2001.
  6.893 slides
• Quickly Detecting Relevant Program Invariants by Michael D. Ernst, Adam Czeisler, William G. Griswold, and David Notkin. ICSE 2000.
  6.893 slides

6.893 critiques

Sep 24:

• Automated Support for Program Refactoring using Invariants by Yoshio Kataoka, Michael D. Ernst, William G. Griswold, and David Notkin. ICSM '01.
  6.893 slides
• Automatic generation and checking of program specifications by Jeremy W. Nimmer and Michael D. Ernst. MIT-LCS-TR-823, 2001.
  6.893 slides

6.893 critiques

Proof-carrying code

Sep 26:
Presenter: Alan Donovan

• Proof-carrying code by George C. Necula. POPL '97.
• The design and implementation of a certifying compiler by George C. Necula and Peter Lee PLDI '98.

6.893 critiques

Static checking

Oct 1:

• Eliminating array bound checking through dependent types by Hongwei Xi and Frank Pfenning. PLDI '99.
  6.893 slides
• A static analyzer for finding dynamic programming errors by William R. Bush, Jonathan D. Pincus, and David J. Sielaff. Software -- Practice and Experience 30, 2000.
  This paper describes PREfix.
  6.893 slides

6.893 critiques

Usefulness of analysis features

Oct 3:

• Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses by Michael Hind and Anthony Pioli. IBM Research Report RC 21251 (94735), 1998.
  A shorter version appeared in SAS'98.
  6.893 slides
  Other, possibly more useful versions appeared in ISSTA'00 and PASTE'01.
• Context-insensitive alias analysis reconsidered by Erik Ruf. PLDI '95.
  6.893 slides

6.893 critiques

Efficient profiling

Oct 10:

• Continuous Profiling: Where Have All the Cycles Gone? by Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William E. Weihl. ACM Transactions on Computer Systems 15(4), 1997.
  6.893 slides
• Efficient Path Profiling by Thomas Ball and James R. Larus. MICRO '96.
  6.893 slides

6.893 critiques

Program spectra

Oct 17:
Presenter: David Alexander

• The Use of Program Profiling for Software Maintenance with Applications to the Year 2000 Problem [PostScript, PDF] by Thomas Reps, Thomas Ball, Manuvir Das, and James Larus. ESEC/FSE '97.
• An Empirical Investigation of Program Spectra by Mary Jean Harrold, Gregg Rothermel, Rui Wu, and Liu Yi. PASTE '98.

6.893 critiques

Race detection

Dynamic race detection

Oct 22:
Presenter: Michael Harder

• Eraser: A dynamic data race detector for multi-threaded programs by Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. SOSP '97.
• Efficient Detection of Determinacy Races in Cilk Programs by Mingdong Feng and Charles E. Leiserson. SPAA '97.
• (Optional follow-on to Feng and Leiserson)
  Detecting data races in Cilk programs that use locks by Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, and Andrew F. Stark. SPAA '98.

6.893 critiques

Static race detection

Oct 24:
Presenter: Richard Tibbets

• Type-based race detection for Java by Cormac Flanagan and Stephen N. Freund. PLDI '00.

6.893 critiques

Oct 29: no class

Type inference

Oct 31:
Presenter: Alex Rolfe

• Lackwit: A program understanding tool based on type inference by Robert O'Callahan and Daniel Jackson. ICSE '97.
• Inferring Program Specifications in Polynomial-Time by Robert Givan. SAS '96.

6.893 critiques

Nov 5 and 7: no class (work on your projects)

Nov 12: MIT holiday

Security

Nov 14:
Presenter: Jeremy Nimmer

• A lattice model of secure information flow by Dorothy E. Denning. Communications of the ACM, 19:5 (May 1976).
• Protecting Privacy using the Decentralized Label Model by Andrew C. Myers and Barbara Liskov. ACM TOSEM 9(4), 2000.

Nov 19:

• A Minimal Trusted Computing Base for Dynamically Ensuring Secure Information Flow [PostScript, PDF] by Jeremy Brown and Thomas F. Knight, Jr. Project Aries Technical Memo ARIES-TM-015, 2001.

6.893 critiques

Model checking

Nov 19:
Presenter: J.K. Srinivasan

• The Spin Model Checker by Gerard J. Holzmann. IEEE TSE 23(5), 1997.

6.893 critiques

Nov 21:

• Optimizing Symbolic Model Checking for Statecharts by William Chan, Richard J. Anderson, Paul Beame, David H. Jones, David Notkin, and William E. Warner. IEEE TSE 27(2), 2001.

6.893 critiques

Nov 26:

• Constructing compact models of concurrent Java programs by James C. Corbett. ISSTA '98.
• Using predicate abstraction to reduce object-oriented programs for model checking by William Visser, SeungJoon Park, and John Penix. Third Workshop on Formal Methods in Software Practice, 2000.

6.893 critiques

Meta-compilation

Nov 28 and Dec 3:
Presenter: Ken Takusagawa

• Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions by Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem. OSDI 2000.
• Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code by Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf. SOSP 01.

6.893 critiques

Debugging and Slicing

Dec 5:

• Isolating Failure-Inducing Input by Andreas Zeller. To appear in IEEE TSE.
• Hybrid slicing: An approach for refining static slices using dynamic information (PDF, PS) by Rajiv Gupta and Mary Lou Soffa. FSE 1995.

6.893 critiques

Last updated: May 23, 2006.

Back to the 6.893 webpage.