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.
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".
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.
9 comments
[ 3.7 ms ] story [ 36.8 ms ] thread[1] https://en.wikipedia.org/wiki/Semmle?wprov=sfla1
[2] https://semgrep.dev/
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.
> But ML cannot prove the absence of vulnerabilities.
Basic computer science fundamentals say that thelis impossibility applies with any technique.
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.
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."
I'm teaching assistant for a compilers course at University of Buenos Aires.