4 ms·
Static Program Analysis [pdf]
- hyperpape 8y agoI haven't read it (it's on my list), but I'll pass along a recommendation by someone well suited to know: https://twitter.com/johnregehr/status/1037098838752784384 https://twitter.com/johnregehr/status/1037098838752784384
- michaelmior 8y agoThis is the same document the original post links to :)
- hyperpape 8y agoYes, I should've said that. I meant "this isn't some random link posted to HN, it is well regarded."
- pbiggar 8y agoI've a PhD in static analysis. I only glanced at the table of contents but it's really great. This is exactly the important stuff to cover if you're learning about static analysis, want to build a static analyzer, etc. The only thing it doesn't cover is SSA form, which I think is fine: if you get the fundamentals in this book, then SSA will be easy to learn. [Also, I remember reading the author's paper on Type analysis in JS: https://cs.au.dk/~amoeller/papers/tajs/paper.pdf https://cs.au.dk/~amoeller/papers/tajs/paper.pdf, and remember it being really good.)
- yazr 8y agoCan someone knowledgeable summarize the current state of Program Analysis state-of-the-art? Do we know how to do context sensitive / intra procedural analysis and scale it to millions of lines of code ?
- bos 8y agoYes, and in fact this can even be done incrementally and efficiently these days. One example is the open source tool Infer, which we run on very large bodies of native and Java code at Facebook. http://fbinfer.com http://fbinfer.com
- gnufx 8y agoDoes Infer actually provide anything for C which you don't get from the clang analyzer, for instance? That wasn't clear when I tried it a while ago.
- mynegation 8y agoI co-created one of the commercial program analysis tools used by many large customers on millions line of code. I have been out of this for a while but track what is going on every now and then. Our analysis was context-sensitive and inter-procedural (this is probably what you meant to ask about as intra-procedural analysis means "within one function/procedure" and I cannot imagine having a function with millions line of code). First of all: real bugs and security vulnerabilities can can be found and were found with these kind of tools. But state explosion is real. To deal with enormous computational complexity of sound program analysis, corners must be cut. Program analysis is usually defined as sound (i.e. all warnings you get are about real bugs, i.e. no false positives) or safe (if there is a bug, it is found, i.e. no false negatives). You can make analysis sound but it will not be safe, or you can make analysis safe, but it will not be sound. Both extremes are useless, because in the former case you end up with very few warnings (if any) that are definitely real, but you miss a lot of interesting cases, in the latter case you are inundated with a huge number of warnings the vast majority of which are false positives. All commercial tools and most open source tools that I know are neither safe nor sound but try to hit the sweet spot to be useful. I believe most progress in program analysis is done by migrating to safer languages (Rust) and runtimes (Java, Go) over time, where different aspects are eliminated or mitigated, like memory leaks with GC or deadlocks with co-routines in Go or message passing in Erlang. Proliferation of IDEs and ubuquity of lightweight static analysis tool (lint-like) during the development also helps.