Seminar on Program Analysis

ECS 289C (Programming Languages and Compilers)

Winter 2015

General Information

Instructor: Cindy Rubio-González
Time and Location: TR 1:40p-3:00p, 146 Robbins
Contact E-mail: crubio AT ucdavis DOT edu
Phone Number: (530) 752-7069
Office Hours: TR 5:00p-6:00p or by appointment
Office: Kemper Hall 3039
Credits: 4 credits

Course Overview

This course will explore research in the area of programming languages, with particular emphasis on program analysis. Program analysis is the process of automatically analyzing the behavior of computer programs to discover facts. Topics include static analysis (dataflow analysis, model checking, type inference), dynamic analysis (software testing, automated debugging, automatic program repair), and hybrid approaches. We will cover a wide variety of application domains, and languages. This course is intended for graduate students interested in starting research in the area of programming languages, or graduate students whose ongoing research could benefit from program analysis.

Syllabus [PDF]
Preliminary Reading List [PDF]

Course Schedule

Date Topic Readings Presenter
1/6 Course Overview Cindy Rubio
1/8 Research Skills How to Read an Engineering Research Paper by William G. Griswold
    Writing Good Software Engineering Research Papers by Mary Shaw [ICSE'03]
    No paper reviews due for this lecture
Cindy Rubio [PDF]
1/13 Pointer Analysis No reading assignments due Cindy Rubio
1/15 Pointer Analysis Points-to Analysis in Almost Linear Time [POPL'96]
    The Ant and the Grasshoper: Fast and Accurate Pointer Analysis for Millions of Lines of Code [PLDI'07]
    Paper review due 11:59pm Wed Jan 14th
Martin Velez [PDF]
    Saheel Godhane [PDF]
1/20 Program Slicing Interprocedural Slicing Using Dependence Graphs [PLDI'88]
    Dynamic Program Slicing [PLDI'90]
    Paper review due 11:59pm Mon Jan 19th
Daniel DeFreez [PDF]
    Casey Casalnuovo [PDF]
1/22 Test Generation DART: Directed Automated Random Testing [PLDI'05]
    KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex System Programs [OSDI'08]
    Paper review due 11:59pm Wed Jan 21st
Wei Fang [PDF]
    Nima Joharizadeh [PDF]
1/27 Model Checking No reading assignments due
    Project Proposal due 11:59pm Tue Jan 27th
Cindy Rubio
1/29 Model Checking
Lazy Abstraction [POPL'02]
    Finding and Reproducing Heisenbugs in Concurrent Programs [OSDI'08]
    Paper review due 11:59pm Wed Jan 28th
Kashyap Thimmaraju [PDF]
    Dingbao Xie [PDF]
2/3 Concurrency Learning from Mistakes: A Comprehensive Study of Real World Concurrency Bug Characteristics [ASPLOS'08]
    RacerX: Effective, Static Detection of Race Conditions and Deadlocks [SOSP'03]
    Paper review due 11:59pm Mon Feb 2nd
Vehbi Bayraktar [PDF]
    Yuechao Pan [PDF]
2/5 Debugging Simplifying and Isolating Failure-Inducing Input [TSE'02]
    Scalable Statistical Bug Isolation [PLDI'05]
    Paper review due 11:59pm Wed Feb 4th
Ting Su [PDF]
    Benjamin Mishkanian [PDF]
2/10 Performance Understanding and Detecting Real-World Performance Bugs [PLDI'12]
    Go with the Flow: Profiling Copies to Find Runtime Bloat [PLDI'09]
    Paper review due 11:59pm Mon Feb 9th
Cindy Rubio [PDF]
    Wei Fang [PDF]
2/12 JavaScript and
    Web Apps
Jalangi: A Selective Record-Replay And Dynamic Analysis Framework for JavaScript [FSE'13]
    Dynodroid: An Input Generation System for Android Apps [FSE'13]
    Paper review due 11:59pm Wed Feb 11th
Daniel DeFreez [PDF]
    Nima Joharizadeh [PDF]
2/17 Compilers and
    Error Handling
Finding and Understanding Bugs in C Compilers [PLDI'11]
    Error Propagation Analysis for File Systems [PLDI'09]
    Paper review due 11:59pm Mon Feb 16th
    Milestone #1 due 11:59pm Tue Feb 17th
Martin Velez [PDF]
    Cindy Rubio [PDF]
2/19 Error Handling Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures [OSDI'14]
    Automatic Detection of Floating-Point Exceptions [POPL'13]
    Paper review due 11:59pm Wed Feb 18th
Casey Casalnuovo [PDF]
    Saheel Godhane [PDF]
2/24 Floating Point Precimonious: Tuning Assistant for Floating-Point Precision [SC'13]
    Efficient Search for Inputs Causing High Floating-Point Errors [PPoPP'14]
    Paper review due 11:59pm Mon Feb 23rd
Cindy Rubio [PDF]
    Yuting Chen [PDF]
2/26 Program Generation Program Generation for Compiler Validation and End-User Programming
    No reading assignments due
Vu Le
3/3 OpenCL OpenCL-based Design Methodology for Application-Specific Processors [SAMOS'10]
    Paper review due 11:59pm Mon Mar 2nd
Vehbi Bayraktar [PDF]
3/5 Automatic
    Program Repair
Automatically Finding Patches Using Genetic Programming [ICSE'09]
    Automated Atomicity-Violation Fixing [PLDI'11]
    Paper review due 11:59pm Wed Mar 4th
    Milestone #2 due 11:59pm Thu Mar 5th
Benjamin Mishkanian [PDF]
    Yuechao Pan [PDF]
3/10 Guest Lecture Detecting and Localizing Inconsistent Code
    Martin Schäf (SRI International)
    No reading assignments due
3/12 Security
    Project Presentation
Finding User/Kernel Pointer Bugs with Type Inference [Usenix'04]
    A Multi-GPU Implementation of Inclusion-based Points-to Analysis Using Gunrock
    No reading assignments due
Kashyap Thimmaraju [PDF]
    Yuechao Pan
3/19 Final Final Project Presentation 12:00pm-3:00pm Thu Mar 19th
    Final Project Report due 11:59pm Thu Mar 19th