13
$\begingroup$

I'm looking for resources on getting started with program analysis.

The only book I've found on the topic is the Nielson & Nielson book.

Other than that, it seems like there are only "compiler" books where "program analysis" would be a chapter, or something along those lines.

Do people know of any other resources?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Hard to beat Nielson and Nielson for getting started. Google for survey papers. Look at recent proceedings of Static Analysis Symposium (SAS). Then google particular analyses you are interested in. $\endgroup$
    – Dave Clarke
    Commented Mar 22, 2013 at 22:19
  • $\begingroup$ Note that we don't quite like list questions. Luckily, this seems to have attracted a good answer, but please refrain from asking such questions. Google yourself and then ask about the stuff in the resources you find. $\endgroup$
    – Raphael
    Commented Jul 30, 2013 at 10:21

4 Answers 4

Reset to default
8
$\begingroup$

Unfortunately there aren't many textbooks on the topic. I think the best way to learn program analysis today is to survey different courses that are available, play with a few implementations and then look at a few research papers for your specific needs. What follows is a very small sampling of what's out there. Since you specifically mentioned compiler-oriented analyses were easy to find, I will not cover such material below.

Web-based resources These are articles that emphasise the use of static analysis outside a compilation context.

  1. A Reverse Engineering Reddit discussion on program analysis has many useful links.

  2. Mozilla Wiki on abstract interpretation.

  3. Deploying Static Analysis, a Dr. Dobbs article by Flash Sheridan

  4. A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World, Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, Dawson Engler in Communications of the ACM.

University courses on program analysis

  1. Anders Møller at Arhus University teaches a course that covers object-oriented and web technology.
  2. Bor-Yuh Evan Chang at University of Colorado Boulder has a foundational course that involves an OCaml implementation and a graduate course.
  3. Ben Hardekopf at the University of California Santa Barbara used to have a great set of assignments, but they are no longer available online. Some students who took his course seem to have made a Python implementation available.
  4. Markus Müller-Olm has a graduate course on analysis of Android.
  5. Reinhard Wilhelm at the University of Sarbruecken teaches a graduate course that covers static analysis applications such as timing analysis, cache behaviour prediction, and some shape analysis.
  6. Sumit Gulwani from MSR taught a nice course on statically estimating resource consumption of programs (time/memory) at the Oregon Summer School on Programming Languages.
  7. Koushik Sen at the University of California at Berkeley teaches a course that focuses on bug finding and whose topics cover concolic execution and software model checking.
  8. Jeffrey Foster at the University of Maryland teaches a course that covers type systems, model checking, alias analysis and a lot of the other usual material.
  9. Patrick Cousot spent a year at MIT and taught a comprehensive, foundational course on abstract interpretation. The assignments include an OCaml implementation which go from concrete collecting semantics to some algorithmically non-trivial ideas.
  10. A graduate course on abstract interpretation taught by some leaders in the field is a good place to catch up on even more theory.
  11. Patrick Cousot taught a short course on abstract interpretation at the Oregon Summer School on Programming Languages in 2009.

Tools to play with

I am not listing a lot of research tools here. There are many of those but I have tried to list a few that you can download and play with to understand the area better.

  1. Interproc is a very educational tool to play with to learn about numerical static analysis.

  2. The Apron Numeric Abstraction library if you are really into numeric analysis.

  3. Slayer is a shape analysis tool from Microsoft Research.

  4. jStar is an analyzer for Java that is based on separation logic.

  5. Microsoft Research has numerous groups developing numerous tools, many of which are available for download or have web-demos. I cannot list everything here and suggest you play with them.

There is a lot more, but that's probably enough to keep you busy for a while.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Wow, now that's a comprehensive answer! Thanks a lot! $\endgroup$
    – abeln
    Commented Mar 24, 2013 at 21:49
  • $\begingroup$ @Vijay thank you for your answer! I wonder if you could add a few pointers for Compiler analysis for me? $\endgroup$
    – AnneTheAgile
    Commented Jul 10, 2013 at 22:27
  • $\begingroup$ @AnneTheAgile, I think that extension merits a separate question and answer. So please ask the question and I'm happy to provide the answer. $\endgroup$
    – Vijay D
    Commented Jul 13, 2013 at 21:30
  • $\begingroup$ @VijayD, thank you! I have written it ; cs.stackexchange.com/questions/13392/… $\endgroup$
    – AnneTheAgile
    Commented Jul 22, 2013 at 16:57
  • $\begingroup$ I am too slow replying, and my post was deleted. @VijayD perhaps you can IM me or add here? What I am interested in is the basics. I am not sure how best to find the "compiler-oriented analyses" which "were easy to find"? I am new to the field and want to get started the right way. ty! $\endgroup$
    – AnneTheAgile
    Commented Aug 14, 2013 at 20:30
2
$\begingroup$

This field is extremely broad... look for proofs of program correctness (there are a few tools around, like Klee). Then there are all sorts of "program checkers" of varying sophistication (see for example splint or flawfinder for a sampling of the range), programs that check for "programming guidelines compliance". Even Linux' smatch falls into this category.

For dynamic tools, there are all sorts of performance/test coverage tools around, and stuff for memory checking like valgrind.

Narrow the range of interest, then drill down.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. The ones you mention are tools, but what about books or surveys, say on static program analysis? $\endgroup$
    – abeln
    Commented Mar 22, 2013 at 20:21
1
$\begingroup$

There are two research focuses in program analysis: dynamic and static program analysis.

To have a first taste of program analysis, I recommend to read Chapter 4, 6, 9 in the Dragon book if you have background in compilers.

Or if at least you know basic graphs, it would be better to follow a graduate-level course, such as MIT 6.820 and CMU 17-355/17-665/17-819.

The above are about static program analysis. If you care more about dynamic program analysis, program profiling is a good point to start.

Improve this answer
$\endgroup$
1
$\begingroup$

Nielson and Nielson have come out with another book called Program Analysis - An Appetizer which is supposed to be much more elementary compared to Principles of Program Analysis. It might be a good starting point. You can find it here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.