Mathematics textbook for program analysis

Question

Im going to do a course on program analyis (dataflow analysis, abstract interpretation etc).

What mathematics textbook will cover all the prerequisite math for this topic?

Answer 1

Program analysis covers a pretty broad spectrum of ideas, some of which are very mathematical, some of which are more related to computer science. I'd be surprised if you find a single book which covers this field thoroughly.

As a disclaimer, my interest in this area is focused on analysis of hard real-time programs.

• The simplest approach to modeling software is as a directed graph of basic blocks and jumps. Most good math and algorithms books tend to have a reasonable coverage of suitable network and graph algorithms. Your best bet is something comprehensive like Introduction to Algorithms. Whatever you pick, make sure that it covers Integer Linear Programming, and algorithms for generating dominator graphs.

• Obviously the basis for any program analysis is founded in a strong understanding of program structure. It's worth spending some time studying compilers, interpreters, code generators. There is a whole category of material on stackoverflow related to this. Apart from an obvious recommendation of the dragon book, my text of choice is Modern Compiler Design which includes good coverage of dataflow analysis and is very readable. I also found the MIT 6.035 Computer Language Engineering videos to be enlightening.

• Some of the most accessible work on modeling execution time behavior of software was published by Puschner and Schdel, Computing Maximum Task Execution Times -- A Graph-Based Approach. I think this is worthwhile reading for anyone starting out in this field because of the simplicity of the presentation and the quality of the notation.

• If you're interested in abstract interpretation you may be interested in the works of Christian Ferdinand, whose work ended up forming the basis of aIT, a commercial tool used by the likes of Boeing and the car manufacturers for validating worst case execution time performance.

• If you need to validate the program models you produce, you'll need to move into the realm of cycle accurate simulators like PTLsim or SimpleScalar. Or, if you're interested in stochastic validation of algorithms, Stewart Edgar's thesis, Estimation of Worst-Case Execution Time Using Statistical Analysis and a good book on extremal value statistics will be helpful. If you are more interested in validation through measurement on a real platform, Stefan M. Petter's publications may be of interest.

Edit:

• Whilst I haven't looked at it myself, Principles of Program Analysis and the associated Program Analyzer Generator tool PAG may interest you.

Answer 2

Look up "Principles of Program Analysis".