02242: Program Analysis

1. The Course

In this course, you, the student, will become familiar with different ways of deriving facts from programs, using both dynamic and static analyses. The course will focus on analyses for the JVM, but the students are encouraged to work on any language they want. The theoretical part of the course will be covered in the first half of the course; after which the students should write a proposal for a group project. Finally, the students will carry out experiments verifying their ideas, which they will write up in a paper and present orally.

1.1. Expectations and Didactic Contract

DTU sets the expected workload of one ETCS point to 28 hours. Since this is a 7.5 ETCS point course over 13 weeks + 1 week exam, one should expect to use 14 hours on this course a week, 4 of which are in class.

Participation in the class or doing the assignments are not mandatory. However, they are the primary way we convey the material of the class. It will be very hard to pass the course without engaging with the material.

1.2. Teaching Style and Philosophy

Personally, I've never found lectures or reading as a great way to learn. So my teaching philosophy is a little different than others. Essentially, it can be Core to my teaching philosophy is the phrase:

You only learn from your mistakes.

Essentially, no matter what a student is presented with, if will not be absorbed unless it is needed by the student to fill gabs in their understanding. The gabs in their understanding is only found through failure.

The goal of the teacher is to present the students with challenges to overcome, help them to learn when they fail, and support them when they give up.

1.3. The Learning Objectives

A student who has met the objectives of the course will be able to:

1.4. Feedback

This course is still in its infancy, feedback is therefore crucial to make it better for generations to come. You are welcome to send suggestions to chrg@dtu.dk or anonymously on this Google Form.

2. The Lectures

Because of my Teaching Philosophy, I like to focus on practical work and collaboration. The lectures are therefore structured different than what you might be used to.

2.1. The Groups

In the class there are going to be three group formations, the Feedback Group, the Work Group, and the Project Group.

• The Feedback Group is a group of 6 random students. The goal of this groups is to have a place to hear about alternative solutions to your current problems.
• The Work Group is a group of 2 - 3 students. The goal of this group is to solve the exercises in the class. You can almost freely choose who you will work with, but they cannot also be in your feedback group.
• The Project Group is a group of 4 - 6 students. The goal of this group is do the final project and defend it together orally. One approach is to join two work groups that wants to work on the same thing.

2.2. The Structure

Every lecture (except the first) is structure like so:

• In the beginning of the lecture you should sit with you feedback groups. Together with them you'll discuss your progress over the last week: what was easy and what was hard.
• We'll then summarize the feedback in class, hopefully resolving the biggest questions from the last week.
• Then the topic and problem of the day is introduced.
• Which you can work with your project groups on.
• Then we'll have a lecture about the problem of the day. Here we can cover any problems and questions that have come up during the Getting started section.
• Finally, you have time to work alone with help from the TA and sometimes the teacher.

2.3. The Schedule

The lectures are on Mondays at 13:00 to 17:00. This is a tentative list of topics and might change.

3. The Game

During the course we'll use different tools to try to solve the same problem, namely get the best score in the JPAMB benchmark suite, in the shortest amount of time.

The rules are available in the README of the project.

4. The Finals

Your final grade will be based on a paper handed in by your project group, by the end of the course, which is defended as a group at the oral presentation. The paper should describe the results of project done during the last half of the semester.

The project has the following timeline:

4.1. The Project

The first thing you should do is find an interesting topic. The topic should be centered around program analysis, and should demonstrate your understanding of the course. You can either do an application project which applies some the techniques you have learned into a novel domain, or an foundational project which explores and improves the techniques themselves.

Every project should:

• contain two different program analyses, or a base analysis with an extension;
• be rigorously evaluated on some benchmarks or use cases; and
• set in perspective to the course at large.

A list of interesting topics, but not limited to:

• A survey of existing program analyses for Java, and how they preform on the JPAMB.
• A static analysis tool that uses an LLM to analyse the code.
• A program analysis tool that can predict which unit-test that needs to be rerun after a change.
• An evaluation of different interger abstractions on the JPAMB.
• A decompiler for JVM bytecode.

If you can't come up with an interesting project, then you can always fallback on the following topic:

Implement a semantic or hybrid technique from the course, and extend it, and evaluate the extensions against the JPAMB.

4.2. The Proposal

Before starting on the project, you have to hand in a project proposal. The project proposal is 1 - 2 pages and correspond roughly to the introduction of your final paper. It should formatted using the ACM small format, and will be evaluated on the following parameters, on a score (4-0):

• Presentation: is it easy to read and formatted correctly?
• Motivation: is well motitivated interesting?
• Research Question: does the research question / hypothesis make sense in relation to the problem?
• Approach: does your approach seem sound and does it support your research question?
• Evaluation Strategy: do you plan to evaluate your research question?
• Plan: is the plan realistic?

You need to score at least 12 points and none of the parameters can be 0, to be able to hand in the final paper.

If your proposal are rejected you have to resubmit (even after the deadline). The proposals are graded as you submit them, so you do not have to wait to the last day.

4.3. The Paper

The paper should be at most 10 pages, excluding references. It must be formatted using the ACM format in acmsmall mode. To be sure to adhere to the format, and for hints about the structure you should use the template on learn.

Before you continue writing the paper, consider the advice in this lecture, by Simon Peyton Jones.

The final paper should contain the following sections (approximate page numbers in parentheses):

• An abstract, describing the paper.

• An introduction (1-2 pages), with

  • a good motivation and description of the problem you are trying to solve (consider using examples),
  • the problem stated as a research question,
  • a short description of your solution, and
  • a list of contributions with forward references, described in the lecture by Simon P. Jones.

• An example illustrating your approach (1-2 pages).

• An approach and theory section: high level description of the technique used to analyze (2-3 pages), with

  • a formal description of the approach;
  • a walkthrough of the theory needed to understand the technique; and
  • any theoretical guarantees of the approach.

• An evaluation section, describing the evaluation and the results (2-3 pages), with

  • an empirical evaluation of the approach,
  • compared against at least one other technique (or variations (optimizations) of your technique),
  • an analysis of the results, and
  • a discussion of the threats to validity.

• An related work section, discussion of the technique, and alternatives techniques to solve the same problem (1 - 2 pages), with

  • an explanation why other techniques from the lectures (and potentially the literature) were not used, and

• A conclusion (0 - 1/2 page), which is

  • A short recap of the paper.

4.4. The Proceedings

The papers will (on a voluntary basis) be collected in a proceedings, which is shared among all students and with the generations to come. Furthermore, every semester a paper will get the best paper award, which will be indicated in the proceedings.

4.5. The Oral Presentation

Finally, the projects are presented orally. The oral presentation follows the plan on DTU Learn. Each group gets 15 minutes to do presentation of their project, after which 2 minutes are allotted per group member for questions.

The questions can cover all of the course material, especially the questions asked in class, and the project.