Scaling Program Analysis to Big Code CS-7575

Syllabus

One of the aims of modern software engineering is to automate the process of understanding software artifacts. This course focuses on techniques for analyzing programs to find bugs and vulnerabilities. You will gain a working knowledge of program analysis and its theoretical foundations rooted in abstract interpretation. The class starts with lectures on key concepts of program analysis including data flow analysis, constraint-based analysis and abstract interpretation. Applications to security and bug finding will be used as motivation. Topics in dynamic analysis will be covered to explore the tradeoff between soundness and scalability. The second part of the course focuses on reading, presenting and validating research papers.

Workload

We meet once a week for several hours. Between meetings you will read the book abd papers selected for the week. For the first half of the course, the expected workload is one day a week, mostly reading. The second half of the course will be either research or coding.

Grading will be based on one of the following options:

•   Presentation of a research paper.
•   Written exam on the book.
•   Reproduction of a research result.
•   Implementation of a static analysis algorithm.

In other words: You pick what you want to do and how you want to be graded. The most boring option is to be graded on the readings, but that means you don’t have to present or code anything. The next level up, is to prepare a lecture on one research paper that we agree upon. The quality of the lecture would be your grade. Then you could also try to see if you can reproduce the results of the paper using any available artifacts. Or you can implement something relevant to the course topics. Ideas will be hashed out in the first weeks.

While grades are besides the point in a research class, they are required and the expectation is for them to fall the range [B, B+, A-, A], where a B is below average, B+ and A- mean expectations were met, and A+ means awesome.

Textbook

The textbook is Principle of Program Analysis (PPA) by F. Nielson, H.R. Nielson and C. Hankin. (An old version of the text is on ResearchGate here. The newest edition has 476 pages.)

Papers

Some paper ideas:

Testing

• QuickChecking Static Analysis Properties STVR 2017.
• DART: Directed Automated Random Testing PLDI 2005.

Dynamic Analysis

• Systematic Approaches for Increasing Soundness and Precision of Static Analyzers SOAP 2017.
• Active Learning of Points-To Specifications PLDI 2018.
• Concerto: A Framework for Combined Concrete and Abstract Interpretation POPL 2019.
• Principles of Staged Static+Dynamic Partial Analysis SAS 2022.

Bug finding

• ExceLint: Automatically Finding Spreadsheet Formula Errors OOPSLA 2018.
• ZENIDS: Introspective Intrusion Detection for PHP Applications ICSE 2017.

Static Analysis

• Modular static analysis of string manipulations in C programs SAS 2018.
  
• Static analysis of Java enterprise applications: frameworks and caches, the elephants in the room PLDI 2020
• Abstract interpretation repair PLDI 2022.
• Incorrectness logic POPL 2020.
• Sound and reusable components for abstract interpretation POPL 2019.
• A Multilanguage Static Analysis of Python Programs with Native C Extensions PhDThesis 2021.

Big Code

• To Type or Not to Type: Quantifying Detectable Bugs in JavaScript ICSE 2017.
• Learning a Static Analyzer from Data CAV 2017.
• Predicting program properties from ‘big code’ POPL 2015.
• Using Data Mining for Static Code Analysis of C ADMA 2012

Meetings

We meet on Wednesday 10:15 EST, on Zoom.

Reviews

“Jan Vitek is the most horrible professor I’ve ever met. […] he made students read and learn all by themselves. […] He kind of enjoys watching students working so hard over night and night”