Main

PL Course

Practical Programming Language Tools for Low-level Programs

In this course we will explore practical techniques for analyzing and extending the C programming language. In particular, we will focus on the steps and tools necessary for generating useful analysis and extensions that can aid the working C programmer in creating safer, more efficient code. Though the emphasis of this course is on analyzing and extending C, thinking more deeply about language semantics and getting a broader sense of the techniques available for systems programming will help students become better and more versatile programmers.

Through a series of small programming tutorials, students will learn how to use tools from among the following: AST visitors, dataflow analysis, flow-insensitive analysis, call graph analysis, program instrumentation, and extensions to C's syntax, type-system, and runtime. Additionally, students will work in teams of two on a project aimed at developing a tool that eases the creation of fast and safe C code through static analysis, language extensions, or a custom runtime library. Time permitting; we will also cover more recently developed techniques that combine static analysis, symbolic execution, and dynamic analysis.

This course is aimed at advanced bachelor students and above. Interested students should be very familiar with programming in C, and should be acquainted with a functional programming language. A compilers course is not a prerequisite, as we will cover the necessary topics as they come up.

To accomplish these goals we will use the C Intermediate Language(CIL) library for OCaml. It is easiest to obtain and run these tools on the various distributions of Linux (I have been using Ubuntu without any major issues). It should also be possible to use CIL and OCaml on recent versions of Mac OS X, but Windows support may be limited (read: if you want to use Windows, you are on your own.)

Don't worry if you are unfamiliar with OCaml. I will be available to help you get up-to-speed, whether this means talking about OCaml in lecture in the case of general confusion, or one-on-one during office hours.

Spring '12 Organization

This course will be organized similarly to graduate-level elective courses taught in various CS departments in the US. In particular, my goal for this course is to expose you to a set of tools that you can use to effectively pursue your own interests in the form of a project, as described above. You will be evaluated based on the progress made on your project, which will include a written proposal, and a presentation and demo at the end of the semester. The requirements for the project, and some ideas for topics will be discussed below. A portion of the evaluation will also depend on class participation

We are scheduled to meet for a lecture from 10-12 on Mondays in CAB G56. The schedule also shows a discussion period from 1-2pm, also on Monday in CAB G59. It is unlikely that the lecture period will run for the full two hours. Also, I am planning on using the discussion period primarily to answer questions and give advice about the project component of the course, so it will only be used on an as-needed basis.

Schedule

This schedule is subject to change. Topics may be added or removed according to people's interests.

  • 20.02 -- Course introduction (Slides)
  • 27.02 -- Project overview (Slides)
  • 05.03 -- The AST and instrumentation (Slides)
  • 12.03 -- Adding new statements, overriding functions (Slides)
  • 19.03 -- Type qualifiers (Slides)
  • 26.03 -- Type qualifiers con't (Slides)
  • 02.04 -- Implementing a DSL (Slides)
  • 09.04 -- No class; Easter holiday
  • 16.04 -- Dataflow analysis (Slides)
  • 23.04 -- Program Verification (Slides)
  • 30.04 -- Automated Test Generation (Slides)
  • 07.05, 14.05, 21.05 -- Additional topics, project presentations/demos

Office Hours

Fridays 10-11am, or by appointment

Resources

Project Ideas

  1. Read-Copy Update language extension
  2. Add language features to make tricky API use correct-by-construction
  3. Language features supporting process shared memory
  4. Store analysis results in a database
  5. Extend Google's protocol buffer library
  6. Debugging via detailed, targeted state snapshots
  7. Replay Pthreads Programs
  8. Local data-race detection
  9. Automatic Differentiation
  10. Type qualifiers for scientific units
  11. XML or SQL integration
  12. Analysis and/or extension for safe handling of error return codes
  13. Studying Makefiles
  14. Large scale studies of C code
  15. Literate Programming for C
  16. Transform heap allocation into stack allocation
  17. Parallel analysis framework