Computer Science:

Mathematics:  I was advantaged in that I did my undergraduate degree in the subject. Here's what I can recommend, given eleven years' worth of hindsight studying program analysis:

  • You run into abstract algebra a lot in program analysis as well as in cryptography, so it's best to begin with a solid foundation along those lines. There's a lot of debate as to what the best text is. If you're never touched the subject before, Gallian is very approachable, if not as deep and rigorous as something like Dummit and Foote .
  • Order theory is everywhere in program analysis. Introduction to Lattices and Order is the standard (read at least the first two chapters; the more you read, the better), but I recently picked up Lattices and Ordered Algebraic Structures and am enjoying it.
  • Complexity theory. Arora and Barak is recommended.
  • Formal logic is also everywhere. For this, I recommend the first few chapters in The Calculus of Computation (this is an excellent book; read the whole thing).
  • Computability, undecidability, etc. Not entirely separate from previous entries, but read something that treats e.g. Goedel's theorems, for instance The Undecidable .
  • Decision procedures. Read Decision Procedures.
  • For an extensive treatment of SAT solvers and their applications, read Handbook of Satisfiability.  For something math-ier, try Introduction to the Mathematics of Satisfiability.
  • I wish I had studied set theory sooner in my program analysis career. Many concepts from set theory recur in abstract interpretation -- and they're harder in set theory, so if you study that first, you will have a solid background for reading abstract interpretation. A good treatment of set theory will utilize partial orderings, descending and ascending chain conditions, ordinal theory, definition by transfinite recursion, and some fixedpoint theorems. I used Set Theory and the Continuum Problem, and recommend it for its exposition (while lamenting its many typographical errors).

Program analysis, the "accessible" variety.

Program analysis, the "serious" variety. 

  • Principles of Program Analysis is an excellent book, but you'll find it very difficult even if you understand all of the above. Similarly, Cousot's MIT lecture course is great but largely unapproachable to the beginner. I highly recommend Value-Range Analysis of C Programs , which is a rare and thorough glimpse into the development of an extremely sophisticated static analyzer. Although this book is heavily mathematical, it's substantially less insane than Principles of Program Analysis. I also found Gogul Balakrishnan's Ph.D. thesis , Johannes Kinder's Ph.D. thesis , Mila Dalla Preda's Ph.D. thesis, Antoine Mine's Ph.D. thesis, and Davidson Rodrigo Boccardo's Ph.D. thesis useful.
  • If you've gotten to this point, you'll probably begin to develop a very selective taste for program analysis literature: in particular, if it does not have a lot of mathematics (actual math, not just simple concepts formalized), you might decide that it is unlikely to contain a lasting and valuable contribution. At this point, read papers from CAV, SAS, and VMCAI. Some of my favorite researchers are the Z3 team, Mila Dalla Preda, Joerg Brauer, Andy King, Axel Simon, Roberto Giacobazzi, and Patrick Cousot.
  • Although I've tried to lay out a reasonable course of study hereinbefore regarding the mathematics you need to understand this kind of material, around this point in the course you'll find that the creature we're dealing with here is an octopus whose tentacles spread in every direction. In particular, you can expect to encounter topology, category theory, tropical geometry, numerical mathematics, and many other disciplines. Program analysis is multi-disciplinary and has a hard time keeping itself shoehorned in one or two corners of mathematics.
  • After several years of wading through program analysis, you start to understand that there must be some connection between theorem-prover based methods and abstract interpretation, since after all, they both can be applied statically and can potentially produce similar information. But what is the connection? Recent publications by Vijay D'Silva et al (1, 2, 3, 4, 5) and a few others (1 2 3 4) have begun to plough this territory.

Final bit of advice: you'll notice that I heavily stuck to textbooks and Ph.D. theses in the above list. I find that jumping straight into the research literature without a foundational grounding is perhaps the most ill-advised mistake one can make intellectually. To whatever extent that what you're interested in is systematized -- that is, covered in a textbook or thesis already, you should read it before digging into the research literature. Otherwise, you'll be the proverbial blind man with the elephant, groping around in the dark, getting bits and pieces of the picture without understanding how it all forms a cohesive whole. I made that mistake and it cost me a lot of time; don't do the same.