Static Program Analysis | Hacker News Reader

Static Program Analysis

cs.au.dk

78 pointsingve9 comments

It would be great to add query techniques that are assistive such as Semmle [1] and Semgrep [2]. Machine learning should also be addressed nowadays.

[1] https://en.wikipedia.org/wiki/Semmle?wprov=sfla1

[2] https://semgrep.dev/

I guess the ML techniques don't really belong here because they don't contribute to static analysis itself. They are ancillary techniques for improving the usability of a programming assistance / security tool, or they are techniques for heuristic pattern detection. That's important, but it's just fundamentally a different thing and not what static analysis is.

Static analysis is about producing a description of every possible execution of a program, with the application to software security being that if this description precludes a vulnerability, then the program can't have that vulnerability. In that sense, the job of static analysis is not to find vulnerabilities; it's to show the absence of vulnerabilities. As an artifact of failing to show the absence of vulnerabilities, you get a list of possible vulnerabilities.

ML techniques can help find certain kinds of issues, or help rank found issues. But ML cannot prove the absence of vulnerabilities.

Moreover, software security is not the only application of static analysis. So is program optimization. For that, the compiler absolutely needs to prove that a transformation is legal. 99.9% heuristic confidence doesn't cut it.

I appreciate the focus of this textbook on its subject.

ML could contribute a lot to this field: you can train models based on existing code issues with large codebases (e.g. GitHub)

> But ML cannot prove the absence of vulnerabilities.

Basic computer science fundamentals say that thelis impossibility applies with any technique.

Computer science says to such thing. Roughly speaking, the impossibility theorums you are likely thinking of say that "there are correct programs which are not provably so".

Exactly.

There is typically no algorithm to correctly decide yes/no on a vulnerability for any input program. But there are algorithms that can correctly report maybe/no. The trivial example: the algorithm that always reports "maybe".

The field of static analysis is about improving on the precision of this trivial algorithm so that it reports "no" whenever it can, within resource constraints.

There are no general algorithms that can report a "no" to general source code. The maybe is obviously not considered in the context of this discussion thread about ML. It is obvious that ML. A simple search on Internet could give you resources like this: https://arxiv.org/abs/2110.09610

> The maybe is obviously not considered in the context of this discussion thread about ML.

What do you mean by that statement? The only thing ML can do with a decision question is report "maybe" with some confidence. For example, "I am 98.3% sure this image has a cat in it, with respect to the data sets I was trained on" or "I am 77% confident this source code misuses a web request API, given the examples and non-examples of misuse that you have shown me."

Thank you so much for sharing this! I've been going through principles of Program Analysis (Nielson-Nielson-Hankin) and understanding 0 of it , this seems much more digestible and up to date.

I'm teaching assistant for a compilers course at University of Buenos Aires.

Ah I miss MIS, he left us far too young. I had some of his undergrad classes, a brilliant teacher. Semantics and static analysis are (were?) popular topics at Aarhus University CS dept.

Reply on news.ycombinator.com