Seminar on Program Analysis

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

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]

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     Concurrency	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