Static program analysis

Definition

Static analysis (SA) happens when any partial execution of program code happens. That is, the code is treated as having different semantics, only partially matching what the compilation/interpretation (C/I) process is extracting from it.

Neither executable translation artifacts (object files and executables from compilation) nor behavioral effects (in the case of immediate interpretation) are usually produced by SA. However, similar to C/I, diagnostics may be shown. It is a way to communicate to human how the SA “understands” certain moments in the code.

Sometimes these rules applied by the SA are clearly derived from or are extending the rules of the language standard. I.e. SA can target itself to detecting incompletely defined behavior allowed by some languages.

However, SA rules may be very disconnected from analysing program behavior. At first sight even completely unrelated to static program analysis (of how most people define it). But we still should treat such tools or processes to be SA, because they share a lot of methodology around them.

Examples of situations when SA is happening

Let me give a few examples.

1. When your compiler performs type checking. Remember that types of variables are not present in the final binary. They are stripped at compilation from their variables after having been verified to be correct. The exact semantics of an input program e.g. int a = 6; int b = 7; int c = a+b; are replaced with something more generic: “any value of type int is added to any value of type int. The expected result of the operation is stated to be type int. Can this be always correct, and if not, when a violation will happen?”

2. When you apply a static code analyzer, such as gcc -fanalyzer, Clang’s scan-build or any third-party tool of the same purpose, to your code. The main goal of these tools is to find places in code that expose erroneous behavior allowed by the input language. The “understanding” of the source program performed by them is still very close to what a compiler has. But the focus shifts from “to convert correct source code to correct binary code” to “to detect source code that cannot be unambiguously converted to correctly behaving binary”.

3. When you spell check your program. The partial execution model of the application in this is: “These textual strings will probably be shown at some point at runtime to a human. Are we certain that they are correctly spelled?” This is an extremely simplified interpretation of any program’s behavior. Surely, we cannot prove that any of these spellchecked words will be shown at all. But it is a useful and rather cheap analysis that can be done instantaneously and presented in IDE as you type. Similar checks are performed by tools which inspect the binaries for intellectual property or trademark leaks. Their model of execution is also very simple: “This binary will land in hands of the customers. Does it possibly contain text that they are not supposed to see?”

4. When you read your code with your human eyes during e.g. a code review. That’s right, humans “execute” code in their head too. Or rather, they do SA unless it is a literal interpretation with a pen and paper. Compared to what is important to a compiler, very different aspects of the source code become important. Examples: too long functions, inconsistent style and misleading comments make the program incomprehensible to a human. The inability to understand code is “diagnostic” often reported at code review. Note how indifferent a compiler would be to these issues. The human mental model of program’s semantics may be completely inadequate to what the language standard says (which often means something is overly complicated with the language syntax, or the human’s qualification is low). But reading the code is still partial execution, the analysis is still performed.

5. When you apply a linter, critic, code debt or vulnerability scanner. It is an automated code review of sorts. But it is much more consistent because it is done by a machine. A human may give up attempting to understand an overly complex piece of code and decide to simply skip it, trusting that it has no issues. A machine does not tire itself. It will get the job done. But a machine will only look for what it was told to search. You cannot fully automate human code reviews, but you can greatly enhance them with such tools.

Do I need more than one SA tool?

You do need, and you are likely already using more than one. E.g. if you compile your code and do code reviews, that is two SA passes. If you use your IDE to complete function arguments for you as you type, you benefit from an SA done on the fly. If several people read the code, each of them performs their own SA with different mental model of the language and the code.

More SA tools will help you to find more issues early.

Can SA be enough?

By the definition, SA does not check the actual behavior. The only way to check program behavior is to trigger it in a live program. And the best way to do that is by preparing a fast, well focused test aimed to stimulate just the required scenario to happen.

Similarly, tests are powerless to expose aspects of the program that are not easily triggerable or have no associated behavior to check for. Relying only on runtime tests is equally limited. You would need both approaches.

The main goal of SA is to produce diagnostics. But any SA has a mismatching understanding of the program to what a compiler “thinks” of it. There are inevitably “false positives” to be reported by any SA tool. A sound strategy to deal with them is required. Usually it is some sort of a database of previously reported known diagnostics which should be ignored and not reported in consequent SA executions.

It is vitally important for a success of any regular SA process to maintain high signal-to-noise ratio.

Written by Grigory Rechistov in Uncategorized on 29.10.2022. Tags: static analysis, compilation,