A gentle introduction to static analyzers for C
nrk.neocities.org
nrk.neocities.org
One often overlooked part is CompCert [1], a pretty-much-verified C compiler. All of the tools mentioned above prove properties on the semantics of the C code that is written. These properties are only conserved in practice if the translation of the C code to equivalent-semantic machine code is correct, and the execution of the machine code is correct with regards to its modeled semantics. The first part of this chain of trust is where CompCert slots in; for the second part, in practice, we are at the mercy of our silicon vendors.
Well, they don't necessarily know if it is or not...
When you're dealing with safety-critical software (DO-178, etc) where the cost of verification and validation can be easily 100x - 1000x the cost of writing the code, having traceability from C code to machine code be correct by proof instead of a manual process can be a lifesaver. Are a significant number of bugs actually excluded this way? That basically comes down to how much the defect rate has been reduced at the C code level by other activities, to determine significance.
It's hard for me to imagine working on DAL B or DAL A code and not at least seriously considering use CompCert just to reduce the scope of necessary verification activities a bit.
I could imagine even 0.01% being significant for e.g. space missions or (if we're being optimistic) lives are at stake.
Every so often our OS needed to read a memory mapped asynchronous timer, comparing values it emitted until they stopped changing to confirm that the various system clock demands were safely aligned and that the addition of a periodic tick was not rippling its way through the counter, before using the value. This time I ran at 32.768 kHz, but to see the glitch required reading the timer exactly as the adder rippled. Most of the time the CPU would read in between the ripples and it would work fine.
This driver had worked on several released products with an earlier version of the compiler, we upgraded the compiler slightly to take advantage of a new instruction set in the next chip.
The updated compiler would rarely assume sequential volatile reads from the same address had the same value.
Something like while(v!=v){} would become the equivalent of if(v!=v)while(1){};
This compiler fault meant that our previously working driver would lock up the machine between maybe an hour and a few days, whenever a particular IRQ occurred during the clock domains race.
Normally watchdogs would trap most infinite loops in the system, but it didn't I knew that it had to be this particular IRQ. Disassembled the whole thing, which only had one loop in it (this one). Took me forever to find because the loop structure was essentially correct except that it was branching just past one of the loads that needed redone. So instead of load x, load y, compare y,x, branch if difference to load x, it branches to load y, a difference of two bytes in the branch offset.
The compiler vendor confirmed this and corrected it in the next compiler version. The ticket number used to be on their website but they no longer publish the change log that far back.
"Real" static analyzers, which are more useful, are based on symbolic execution and abstract interpretation and they will uncover more interesting classes of errors, like double frees, out of bounds array access, etc.
Note that all analyzers will have FPs and FNs, because the underlying problem is uncomputable.
The best open source "real" static analyzer overall for C++ is the Clang static analyzer. There are many commercial analyzers available, and most C++ shops will use one or more of these.
E.g. quote from the documentation page (https://clang.llvm.org/extra/clang-tidy/):
clang-tidy has its own checks and can also run Clang Static Analyzer checks.The big problems in C are:
* How big is it?
* Who owns it?
* Who locks it?
Those are the problems which cause trouble after the program has first started to work at all.
These lints don't help with those problems.
And the clang static analyzer indeed does things like static ownership/lifetime tracking following the control flow as much as is possible at compile time. In code bases which haven't run through an analyzer yet it typically does need some handholding via asserts (for instance hinting that a pointer isn't expected to be null, otherwise you'll be swamped with false positives).
Clang analyzer basically tells you things like "this statement here will cause a null pointer access if this seemingly unrelated function over there at the other end of the project is called with this specific argument, and here's how I arrived at that conclusion (...followed by dozens of "calling function x with y...", "entering loop with loop count z", "taking this if-branch because x is greater than y" etc... - in Xcode this is accompanied with a nice control flow visualization over the source code which makes it a bit easier to follow).
Once a code base is static-analyzer-clean via "assert-hints", it will actually catch bugs at compile time which might be tricky to reproduce at runtime.
Of course static analyzers are still only part of the solution (the "compile time part"), for runtime checks there are the various clang sanitizers.
So. Maybe it qualifies as a "gentle introduction" since it's effectively step 1.
Granted they could have made the language better, but I guess in the spirit of UNIX, they decided to have the separate pass be yet another tool.
If someone is going with C, at very least they should already consider these, and eventually learn to adopt the real deal in terms of tooling for "safe" C.
So much of this enterprise software is junk, but it seems like the options much more basic. In this case, perhaps the simple version is worse.
I'm not as sure how these are designed either. Usually, this requires some fairly sophisticated management of the static test environment, and providing information to the tool.
Perhaps it's just embedded systems, but you also have to manage a custom preprocessor. I'm not sure if these tool have any good rulesets, either default or stuff geared towards eg. CERT-C and MISRA-C.
Anyway, I've played around with Unit test frameworks, too. I'm not sure if I found any that provide good coverage metrics. Also here, it seems in both cases you do get a basic suite of behavior
static: rules you can enable for static checks, logs/reports, etc
unit: framework, scripts, assert, test sequencing, etc
Anybody use anything "heavier weight"? It doesn't have to be "free free", but not for $6-50k+... say less than $2k.
see https://web.archive.org/web/20061206130312/http://gimpel.com... and https://web.archive.org/web/20061208002102/http://www.gimpel....
And for fun, see https://web.archive.org/web/20070204002103/http://www.gimpel...
Two commercial static analyzers I've heard of are Klocwork and Coverity. I know Coverity has a program to scan open source projects. So you can take a look at the output of their scans to see how they fare.
For PC-lint, it was relatively easy to integrate into the build process. Just a few changes in each makefile - probably less if you use something like ninja/cmake to drive the build process.
But adding static analysis to your build is similar to getting a home energy efficiency audit.
The auditor comes in and analyzes your house and points out where you can improve the house's energy efficiency (go from single to double/triple pane windows, fill in cracks around doors, don't use oil/coal to heat the house, etc.) But once they're done and you've adjusted the house accordingly, further audits won't bring up any new issues unless something in the house has changed.
Similar thing with static analyzer (and with turning on compiler warnings). First time you use that feature, you'll get a lot of issues - some of them you may modify, some you'll ignore. But further static analysis won't bring up many new issues, if at all, unless the code has changed.
Which means it's important to run the analysis when code is committed. Besides being cheaper/faster to fix problems before the commit, issues won't build up until the next time you run the static analyzer.
These tools don't eat, don't sleep, don't take vacation/sick days, won't get tired looking at the same code over and over again, and know much more about gotchas/footguns in the programming language than most programmers.
When I talked with a programmer who had worked on an enterprise-level commercial static analyzer, we agreed that these types of tools would find about up to 10% of bugs in a project - closer to 10% for the lower quality projects.
static void
get_foobar() ...
int n_bytes = ...;
[[nodiscard]]
[[reproducible]]
That's true, but mixing signed and unsigned integers opens a much bigger can of worms (for instance it's not unusual to add a negative quantity to an unsigned integer). It's often better to just stick to signed integer types which are big enough to cover the required positive range (e.g. you only loose one bit, and 63 bits ought to be enough for anybody).
...also an optimizing compiler will usually turn something like:
assert((index >= 0) && (index < size));
n_bytes could easily be negative if a byte offset, or as a sentinel.
This is why we have a type system, to express these things :)
Spewing out a list of potential bugs to stdout/stderr isn't enough. There needs to be a smooth workflow for the developer to quickly assess if a reported bug is an actual problem. Also the developer needs to be able to tell the tool to ignore the bug in the future, because getting a list of bugs that you know aren't problematic is annoying the next time around, but infuriating after the tenth time.
Commenters have referred to some linters/analyzers as lightweight, etc. IMHO the simple tools will analyze code on a per-function basis. No/little data-flow analysis is done across function boundaries. The more thorough tools will go the extra mile and analyze resources allocated/values used in one function and passed to others. These tools will require a database and several minutes/hours depending on the size of the codebase. They're not meant as a precondition for committing code - they're doing work that computers are meant for - boring, repetitive, exhaustive, dreary code analysis.
But most of the code where my tool found errors tended to reside in the uncommon code path, typically error handling code/uncommon cases.
You don't want to create an Apple-level face-palm-like bug - https://dwheeler.com/essays/apple-goto-fail.html
So turn on the highest level of compiler warning you can and/or pass the appropriate analyze flag to your compiler.
I appreciate modern languages, which just catch this at compile time, without making people jump through hoops. for example I can just run "go build", and this wont even compile:
package main
func main() {
println("Program run!")
i := 10 // i declared and not used
} int foo() {}
Of course modern languages don't have this insanity.
Took hours, perhaps even days to track down. I did it by spamming single-step until it stopped being able to find the line that was currently executing.
It depends on the compiler, for instance in Clang this is part of the default warning set:
However gcc does not have a warning that I'm supposed to write `int foo(void){}` (if we're talking about C) which is real issue.
Both GCC and MSVC don't care though.
The missing return type is still an issue though.
This should be the default of course, but this will just bring out the pitch forks because people have different opinions (for instance this innocent unused-variable-error in Go is currently by far the most controversial feature in Zig).
warning: ISO C forbids assignment between function pointer and `void *'
Okay, I'll put away my pitchfork now.
I wasn't aware of the GCC -fanalyzer flag, I think that approach is much better than clang. The warnings also seem to be much nicer.
I haven't used SPARK and Ada to be frank, so perhaps they are even superior in their ability to catch bugs with static analysis, I have heard great things. It's something I've been meaning to try.