4 ms·
"The analysis is rigorously intraprocedural, i.e., it is done one function at a time, using only the information available for that function in the translation
by Animats 4y ago
"The analysis is rigorously intraprocedural, i.e., it is done one function at a time, using only the information available for that function in the translation unit
defining it, which includes the annotations possibly provided
in function declarations."
So, in the examples, when something calls "read", what does the analyzer know about "read", and how much of its "char *" buffer it overwrites?
If you're going to do formal static analysis, the big wins come from automatically detecting that thing A is inconsistent with thing B way over on the other side of the project. That's the stuff humans miss. If you have to annotate everything to death, nobody will use your tool.
This is sort of an ad for the "ECLAR software verification platform", which is apparently some expensive tool. The site is all onboarding, no info, "ask for quote" B2B.
From the paper, you can't tell much about what they're doing. From the ECLAIR site, you can't tell much about what they're doing. So, no clue if this is a good idea or not.
[1] https://www.bugseng.com/eclair https://www.bugseng.com/eclair
- voxl 4y agoAh, thank you for pointing this out, it all makes a lot more sense to me now. The table in the paper alone was a giant red flag for me.
- jcranmer 4y agoI don't remember the original source, but there's some classic frustration with these kinds of tables in academic papers. It's a "look at us, we're good at everything!" selective cherry-picking that omits honest discussion about the limitations of the approach. Although honestly, the red flag for me was the mention of a "field-sensitive" analysis in C. My experience doing static analysis on C code is that it tends to be so reliant on type punning that field sensitivity ends up kind of not working, at least not without significant effort on detecting and handling type punning in some manner (to say nothing of all of the fun ways people figure out how to encipher pointers).
- uecker 4y agoI think showing with static analysis that existing C code is safe is very hard. But if you start with modern and cleanly written C and avoid certain techniques (such as type punning) I think it is clear that this can work. Rust fundamentally does nothing else.
- ttfkam 4y ago> But if you start with modern and cleanly written C I think I see a flaw in this plan. Everyone is on the curve, but not everyone will be as far along the curve as you or I would like. The advantage of Rust is that the compiler always enforced all the good practices unless you explicitly opt out, and frankly the error messages that come out of the Rust compiler are a lot more helpful than the ones from the C compiler. It's hard enough getting folks to treat compiler warnings as errors. Expecting every professional (let alone hobbyist) developer to conform to best practices overall may be expecting too much, and when it comes to security and reliability, we really are all in this together and need to make the best of what we've got.
- uecker 4y agoPeople who do not want to write safe code will also not use Rust. (Or then use unsafe Rust a lot). If you want your programmers to write safe code and are in a position to force this, it makes no difference whether you mandate the use of Rust or whether you mandate the use of a safe C subset enforced by a compiler flag.
- ttfkam 4y agoThere is an inherent difference between a language where safety is opt-out (safe by default) and opt-in (unsafe by default). Ignorance or forgetfulness leads to safety by default in Rust. A single failure of vigilance in C leads to the status quo of unsafety. This is no small difference. If someone doesn't want all the guardrails of Rust, there are still options like Nim and Zig that provide better options than C for greenfield systems projects today.
- heywhatupboys 4y agowhen the paper started the classic "I have no clue what typedef's actually are in C and what their interpretation is" I was like hmmm... glad this explains why it is just a terrible, biased article
- drewm1980 4y agoRE the point about catching mistakes involving far apart pieces of code, they are clear that it's "interprocedural", so the analysis is only within a single function at a time. Like with rust, there is a focus on annotating function inputs and outputs, with a lot of inference within functions. I am curious if there's a way to quantify how quickly the safety propagates as you do gradual typing. If you annotate 20% of the functions in a typical codebase, does 90% of the runtime data pass through an annotated function boundary at some point, catching 95% of the ownership bugs?
- fedux 4y agoIt's intraprocedural.
- drewm1980 4y agoIndeed. Embarrassing! I consciously avoid using "intra" or "inter" in English for this reason, and when I do because of someone else's jargon I also say what I mean to disambiguate. Unfortunately we can't deprecate english to avoid these mistakes... but maybe we can design a system of macros we can insert into our posts to statically check if our usage is correct.
- ttfkam 4y agoI always think of "international" as the baseline, because I know it means among multiple nations. Intra- is "the other one". Also, isn't "inter-" vs "intra-" a Latin idiom? It's present in all Romance languages. English got it through French. Luckily I think this is an area where tools like ChatGPT (and modern word processor tech) can help us all out.
- lelanthran 4y ago> If you have to annotate everything to death, Isn't this how rust works? People seem okay with annotating everything.
- pjmlp 4y agoNo, because of language semantics much of that is already in no need for the annotations, other than one needs to go away from the well behaved path.
- pron 4y agoTrue, but C programs that follow the same structure would require about the same amount of annotation. A language can force you to write programs in a way that makes some properties easy to prove, but if you write them in that way, they can be easy to prove in any language. The difference is that instead of rejecting a different kind of program, the analysis will fail to prove, at which point you can either add more annotation or restructure the code to make it easier to prove.
- pjmlp 4y agoThey need much more due to C´s semantics, that is why there are companies like the one on this thread selling verification services and tooling. It is also the reason why Microsoft has acknowledged their idea of lifetimes checker did not went as well as planned, and they had to rethink it, https://devblogs.microsoft.com/cppblog/high-confidence-lifetime-checks-in-visual-studio-version-17-5-preview-2/ https://devblogs.microsoft.com/cppblog/high-confidence-lifet...
- pron 4y agoFor arbitrary code, which is precisely my point. Code written in C in the same style as Rust is no harder to analyse than Rust code. What a new language can do is reject code that's not easy to analyse. It's code that's not written in that way in C that's hard and requires either more annotations or a restructuring (which may still be easier than a rewrite in another language).
- uecker 4y agoBut you can automatically derive a lot of information, e.g. after if (!x) return; you know that x is non-zero etc. Or after x = malloc() you can know that x is - at this point - a pointer that has exclusive ownership (if x is non-null). So I think it is a viable approach. I have a toy C front end that does something similar. While this project stalled due to lack of time, I think it is doable with a modest amount of annotations and not more pain than Rust.
- xavxav 4y agoMy personal experience has shown me that static analysis of this kind does not scale for C, the complexity of showing just the memory safety of even simple programs grows astonishingly fast. Proof overhead for memory safety can frequently be on the order of 5-10 lines of annotation per line of code.
- zozbot234 4y agoThis is exactly why the Rust folks chose the kind of analysis that they did for the borrow checker. It's quite co-extensive with the subset of memory-safety proofs that happen to scale up easily and compositionally to larger programs. That said, it would still be very helpful to have true first-class support for the GhostCell pattern in Rust, so as to be able to prove safety for somewhat more complex designs (including safe doubly-linked lists) albeit contained within a single module.
- pron 4y agoThat greatly depends on how many memory-safe programs you want to prove are memory safe. If it's the same subset of programs that a language like Rust can prove to be memory-safe, the annotation overload need not be higher. If you want to prove that an arbitrary memory-safe C program is memory-safe, then, indeed, you'll likely need many more annotations. Even in those situations, adding more annotations or restructuring the code may be cheaper than a rewrite in another language. Sound static analysis for C is already not uncommon in some important domains.
- 4y ago
- Someone 4y ago> “using only the information available for that function in the translation unit defining it, which includes the annotations possibly provided in function declarations.” > So, in the examples, when something calls "read", what does the analyzer know about "read", and how much of its "char " buffer it overwrites? As the text says: “the annotations possibly provided in function declarations.”* The PDF also says “the large part of the result is obtained without any annotation at all, thanks to the fact that the C Standard Library and the POSIX Library have been annotated once and for all (and the same can be done with any commonly used library).”
- posix86 4y agoHm but isn't that how all static analysis tools, including Rust'a compiler itself, work? I.e.: You know the function body is, according to some definition, let's say aliasing, consistent. You annotate the function signature, thereby expressing formal contracts for that function any caller has to fulfill; given the contracts are fulfilled, the function call will then be consistent. Meaning, you prove the function body is consistent, you annotate the function, and you then get the guarantee that the function is correct for any callsite that fulfills the contracts. If you want to prove this using a formal prover, you have to annotate the function, and annotate the callsite in such a way that the prover can prove that the contracts are kept, AT THE CALLSITE. Or am I missing your point?
- nickitolas 4y agoIsn't the difference in it being required, and opt-out (unsafe) in rust, but opt-in here? Also, my understanding is the rust compiler guarantees "soundness" in safe rust, so it checks and validates that the function signatures (with annotations like lifetimes) are correct
- ttfkam 4y agoAlso Rust's macros are logically part of Rust whereas the C preprocessor knows nothing about the C language. To say the C preprocessor complicates analysis is an understatement.