A New Development for Coverity and Heartbleed(blog.regehr.org)
blog.regehr.org
A New Development for Coverity and Heartbleed
http://blog.regehr.org/archives/1128
6 comments
>first run was 99% false positives but one of the real bugs we found was in a system-level crypto module.
Thinking of it as a false positive seems like the wrong perspective. The static analyzer is a tool that flags usages that are not proven to be correct. The fact that it turned out to be valid isn't the issue, the issue is that your code did not prove it valid to the satisfaction of the analyzer. This isn't necessarily a failing of the analyzer, but an indication that your code should be written in a different way, or provided more "evidence" that its correct (i.e. if guards/size checks).
The goal should be to write code in such a way that whatever tool you're using can prove it correct. Sure, the better the tool the easier this process is. But we really need to fundamentally rethink how we approach this problem.
Thinking of it as a false positive seems like the wrong perspective. The static analyzer is a tool that flags usages that are not proven to be correct. The fact that it turned out to be valid isn't the issue, the issue is that your code did not prove it valid to the satisfaction of the analyzer. This isn't necessarily a failing of the analyzer, but an indication that your code should be written in a different way, or provided more "evidence" that its correct (i.e. if guards/size checks).
The goal should be to write code in such a way that whatever tool you're using can prove it correct. Sure, the better the tool the easier this process is. But we really need to fundamentally rethink how we approach this problem.
I was once talking to someone with a lot of experience in this field and he said that false positives were one of their biggest problems. If you have too many false positives programmers end up deciding the analyzer is full of crap and either dismiss the results entirely or gloss past many ultimately useful results.
A static analyzer that will actually be used can't have too many false positives, and this is the big challenge with these things. He said that allowing some false negatives (to cut down on false positives) made the tools more effective in actually solving problems.
That said, with something like openSSL, you do sort of just wish the programmers would deal with it. Language design should include elements to make these sorts of static analyses easier.
A static analyzer that will actually be used can't have too many false positives, and this is the big challenge with these things. He said that allowing some false negatives (to cut down on false positives) made the tools more effective in actually solving problems.
That said, with something like openSSL, you do sort of just wish the programmers would deal with it. Language design should include elements to make these sorts of static analyses easier.
That's an interesting idea, to have a language and a static analyzer created for each other simultaneously. Constructs that are hard for a static analyzer to reason about would be left out (or relegated to an "unsafe" context). I wonder if there's any work regarding seeing how well rust holds up to the state of the art in static analysis?
I think it works even better if you can get help from the type system. For example, the SafeHtml interface in GWT [1] gives you some safety from Java's type checking and can also make additional static analysis easier. (Then it becomes an exercise in making sure the API is used as intended.)
Perhaps something similar could be done using typedefs in C?
[1] http://www.gwtproject.org/javadoc/latest/com/google/gwt/safe...
Perhaps something similar could be done using typedefs in C?
[1] http://www.gwtproject.org/javadoc/latest/com/google/gwt/safe...
Typedefs in C are just aliases, so given `typedef int foo;` one can freely use `int`s and `foo`s interchangeably, i.e. no checking by the compiler.
That said, one could use actual wrapper structs around the various types.
That said, one could use actual wrapper structs around the various types.
There's also sparse[0]'s address space annotation, which Linux uses for annotating data from userspace.
[0] https://git.kernel.org/cgit/devel/sparse/sparse.git/
[0] https://git.kernel.org/cgit/devel/sparse/sparse.git/
> additional locations in OpenSSL are also flagged by this analysis, but it isn’t my place to share those here.
Why do I get the feeling that we're going to see three months of new OpenSSL vulnerabilities, like we saw with Rails last year? I'm sure Heartbleed plus all the bad press about code quality means a lot of people are suddenly looking. Assuming there is more to find, does anyone have any advice for how we might prepare for it?
Why do I get the feeling that we're going to see three months of new OpenSSL vulnerabilities, like we saw with Rails last year? I'm sure Heartbleed plus all the bad press about code quality means a lot of people are suddenly looking. Assuming there is more to find, does anyone have any advice for how we might prepare for it?
In case you want to try out static analysis on your own code-base, here's a link with the list of most popular tools in this field, grouped by language: http://en.wikipedia.org/wiki/List_of_tools_for_static_code_a...
Visual Studio now ships with a reasonably good static analyzer built in. We're using it more than our aging copy of PC-Lint.
(Carmack's review: http://www.altdevblogaday.com/2011/12/24/static-code-analysi...)
(Carmack's review: http://www.altdevblogaday.com/2011/12/24/static-code-analysi...)
Can you tell VS by now to ignore warnings in 3rd-party libs? Everything that's in Qt's headers is pretty much out of my control but those were by far the most common warnings (or at least I didn't see many real warnings amidst them). At least that's how it's in VS 2010 and it kept me from turning code analysis on more often.
VC++ analysis is useful aside from the fact that it mistakenly thinks every pointer usage is a potential null pointer, but I've gotten better results with clang static analysis.
Every pointer is potentially null, until proven otherwise (which in the general case means solving the halting problem).
I configured jshint inspection in a pre-commit hook on my team's code repository. Yesterday I checked the logs and in the last 10 days it prevented 15 commits, a few of which were actual bugs. For me static analysis is a no-brainer. The only challenge is finding the right set of settings that you don't get too many false positives.
Coverity also has a free trial you can do online with your own code: http://softwareintegrity.coverity.com/free-trial-coverity.ht...
It's super cool to see the power of advanced static analysis these days. Props to the Coverity team for using the Heartbleed trainwreck to motivate new research on these problems.
That said, are there other ways to fix this class of problem? We have choices. We can continue to build ever-more-advanced tools for patching over the problems of C and C++, or we can start using languages that simply do not have those problems.
There will always be a need for C and C++ in device drivers, microcontrollers, etc. But there's no compelling reason why SSL implementations in 2014 should use languages designed to run on mainframes in 1973.
That said, are there other ways to fix this class of problem? We have choices. We can continue to build ever-more-advanced tools for patching over the problems of C and C++, or we can start using languages that simply do not have those problems.
There will always be a need for C and C++ in device drivers, microcontrollers, etc. But there's no compelling reason why SSL implementations in 2014 should use languages designed to run on mainframes in 1973.
> There will always be a need for C and C++ in device drivers, microcontrollers, etc. But there's no compelling reason why SSL implementations in 2014 should use languages designed to run on mainframes in 1973.
Except that safer systems programming languages are older than C with bounds checking by default, having compilers that allowed to disable them if really really required[1]:
Algol (1960)
PL/I (1964)
Modula-2 (1978)
Mesa (1979)
Even VAX, B6500 and 68000 assembly have support for doing bounds checking.
[1] Not the first version of Algol though, as according to Hoare Turing Award speech, customers didn't want unsafe features:
<quote> A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interest of efficiency on production runs. Unanimously, they urged us not to—they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law. </quote>
Except that safer systems programming languages are older than C with bounds checking by default, having compilers that allowed to disable them if really really required[1]:
Algol (1960)
PL/I (1964)
Modula-2 (1978)
Mesa (1979)
Even VAX, B6500 and 68000 assembly have support for doing bounds checking.
[1] Not the first version of Algol though, as according to Hoare Turing Award speech, customers didn't want unsafe features:
<quote> A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interest of efficiency on production runs. Unanimously, they urged us not to—they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law. </quote>
Well, usually this stuff is written in C because other languages come with big runtimes that make them unsuitable for utility libraries that need to be callable by everyone and from everywhere.
That said, we're of course working on changing that with Rust. But I should note that memory safety without garbage collection is just hard: it requires the entire language design to be balanced on a delicate precipice. It's not surprising that it's taken a long time to get there.
That said, we're of course working on changing that with Rust. But I should note that memory safety without garbage collection is just hard: it requires the entire language design to be balanced on a delicate precipice. It's not surprising that it's taken a long time to get there.
> But I should note that memory safety without garbage collection is just hard: it requires the entire language design to be balanced on a delicate precipice.
I was thinking about this recently and I think a large part of the problem is that C arrays are too weakly typed. Array should be a different type than pointer and they shouldn't be convertible. In particular, you shouldn't be able to subscript a pointer, and the in-memory representation of an array should begin with its length. At that point the compiler can include a runtime bounds check for every array access that it can't prove is safe at compile time.
I was thinking about this recently and I think a large part of the problem is that C arrays are too weakly typed. Array should be a different type than pointer and they shouldn't be convertible. In particular, you shouldn't be able to subscript a pointer, and the in-memory representation of an array should begin with its length. At that point the compiler can include a runtime bounds check for every array access that it can't prove is safe at compile time.
Sadly, bounds checking is the easy part; making sure that pointers can't become dangling is the hard one. Unfortunately, use-after-free is an extremely common security vulnerability in the wild (though it wasn't Heartbleed). We solved use-after-free in Rust, at least technically, although there were quite a few tradeoffs we had to make and the usability of the borrow checker is something we're going to need to work on post 1.0.
The more I read about Rust, the more excited I am about it. When I wrote the great-grandparent comment I had Rust in mind.
It isn't hard to do this manually in C, it is just that standard libraries still don't. Partly that is because there is often oneish way to do things that is general and often unsafe and a variety of ways to do things that are safe but more specific to a particular usage pattern. IMO this is also why floating point is popular; it is rarely the best solution to any particular situation but one solution that works ok is often considered better than 10 solutions that work better in partiular cases. Not that this is a good excuse in the case of bounds checking...
>runtime bounds check
The reason people use c, is to get higher speed by avoiding those kinds of checks. A real solution most avoid slowdowns.
The reason people use c, is to get higher speed by avoiding those kinds of checks. A real solution most avoid slowdowns.
If the reason was to avoid those checks, then people really don't know better.
Turbo Pascal => {$R-}
Ada => pragma Suppress (Index_Check);
Modula-3 => cm3 -A
D => dmd -fnoboundscheck / array.ptr[index] in @system code
Just a few examples. Additionally there are lots of research how to remove bounds checking in compiler optimizations
http://citeseer.uark.edu:8080/citeseerx/showciting;jsessioni...
What C has going for it is the symbiotic relationship with UNIX, 40 years of optimizations in most compilers and the historical baggage of being around for so long.
Other better languages suffered from having been shown the door as UNIX spread into the enterprise, but there was a time when C compilers didn't generate better code as the other ones.
Turbo Pascal => {$R-}
Ada => pragma Suppress (Index_Check);
Modula-3 => cm3 -A
D => dmd -fnoboundscheck / array.ptr[index] in @system code
Just a few examples. Additionally there are lots of research how to remove bounds checking in compiler optimizations
http://citeseer.uark.edu:8080/citeseerx/showciting;jsessioni...
What C has going for it is the symbiotic relationship with UNIX, 40 years of optimizations in most compilers and the historical baggage of being around for so long.
Other better languages suffered from having been shown the door as UNIX spread into the enterprise, but there was a time when C compilers didn't generate better code as the other ones.
You can encode the length of an array in the type in C++, at compile time.
Trevor Perrin (of TACK fame) wrote TLS Lite in Python.
I submitted a link to TLS Lite a few days ago, but, alas, showed poor judgement in timing:
https://news.ycombinator.com/item?id=7564740
Direct link: http://trevp.net/tlslite/
I'm actually rather anxious to hear the knowledgeable crowd discuss this fine project.
I submitted a link to TLS Lite a few days ago, but, alas, showed poor judgement in timing:
https://news.ycombinator.com/item?id=7564740
Direct link: http://trevp.net/tlslite/
I'm actually rather anxious to hear the knowledgeable crowd discuss this fine project.
It's fantastic if you want to build TLS testing tools, or if you want a codebase to reason about TLS with.
A stamp of approval if ever there was one.
Thank you.
What, however, hinders adoption as a "working man's" TLS library? Neglecting performance and variety of cipher support, would or should anything prevent me from using Tiny TLS to secure channels between "inner circle machines" (that talk to a set of well-known participants)?
What, however, hinders adoption as a "working man's" TLS library? Neglecting performance and variety of cipher support, would or should anything prevent me from using Tiny TLS to secure channels between "inner circle machines" (that talk to a set of well-known participants)?
My advice is not to use obscure TLS libraries in production. Look at the recent Frankencerts paper to see what goes wrong: only OpenSSL, NSS, and Bouncycastle (the mainstream libraries) properly rejected pathological X.509 certificates.
If you're trying to deploy pure-Python applications, I like tlslite. Of course, I have to say that, because Trevor is much smarter than me.
Personally, I think your realistic production choices are OpenSSL or NSS.
If you're trying to deploy pure-Python applications, I like tlslite. Of course, I have to say that, because Trevor is much smarter than me.
Personally, I think your realistic production choices are OpenSSL or NSS.
Vacillating between floating away on my recently-inflated feeling of
self-worth and trying to keep you engaged on a very uneven playing field
(as in my not knowing Adam from Eve, so to speak), I'll simply opt for
another Thank you.
Apropos nothing else: tlslite and Adam Langley's golang/crypto/tls are the two best codebases on the Internet to (a) learn TLS from and (b) build tools with. They are both extremely great projects.
The TLS library that our company uses for its applications is http://www.yassl.com/yaSSL/Home.html. Not sure if it's considered obscure or not.
Now you just need agl and pbsd to come along and tlslite will hit the HN crypto-trifecta.
You can fix almost any issue in C and use almost any programming paradigm. Some people consider this a bug but I consider it a feature. There is no reason a SSL implementation written in C should be vulnerable to buffer overflow. Since c99's anonymous data allocation it is even possible to have a string plus length struct and a single macro to convert C strings to that structure that can be used in function arguments. It is true that C at best doesn't help correct behavior and sometimes actively encourages incorrect behavior and I think this is a serious issue in the language. However, other languages take a "let me do things right for you" approach that works well as long as your definition of right sufficiently matches the language. But as paradigms come and go it is easy to hit corner cases in such languages while C still works or can be adapted fairly easily, which makes it a good choice for core functionality if not everything.
IMO, C fails at being sufficiently low level to do this as well as it could. I don't think C will ever be replaced by a higher level language; it will be replaced with a lower level language that is better at incorporating static analysis of particular usage patterns into the language. To put it another way: C makes you do a bunch of "extra" work compared to other languages without really helping you do that work; other popular languages I know of try to not make you do that "extra" work, which is often a good thing but not always. A true replacement for C will need to still make you do all the "extra" work but help you make sure that work is correct.
E.g.memory allocation: it is not that manual memory allocation and deallocation is necessarily unreliable, but that there is no single way to make it reliable that works well for all programs. But there is also no way to do automatic memory managment that works well for all programs.
I would never recommend C++, but my sense is that current popularity of C++ might be connected to templates which are flexible and powerful in a different way than C or any other language I know of.
(also C was designed for "minicomputers" not mainframes, so not really all that different from its modern usage)
IMO, C fails at being sufficiently low level to do this as well as it could. I don't think C will ever be replaced by a higher level language; it will be replaced with a lower level language that is better at incorporating static analysis of particular usage patterns into the language. To put it another way: C makes you do a bunch of "extra" work compared to other languages without really helping you do that work; other popular languages I know of try to not make you do that "extra" work, which is often a good thing but not always. A true replacement for C will need to still make you do all the "extra" work but help you make sure that work is correct.
E.g.memory allocation: it is not that manual memory allocation and deallocation is necessarily unreliable, but that there is no single way to make it reliable that works well for all programs. But there is also no way to do automatic memory managment that works well for all programs.
I would never recommend C++, but my sense is that current popularity of C++ might be connected to templates which are flexible and powerful in a different way than C or any other language I know of.
(also C was designed for "minicomputers" not mainframes, so not really all that different from its modern usage)
> c99's anonymous data allocation
I googled that phrase, and came up empty handed. Could you give an example?
I googled that phrase, and came up empty handed. Could you give an example?
Sorry, I always forget what they are officially called, which is compound literals. You can do ((struct foo){...}). GCC had a different syntax for this before c99 but the only standard way to do such allocations was in a new block, which doesn't help for a function argument.
Edit: also worth mentioning that some of the early implementations of this were very inefficient so you might see complaints from that time, but this is not an issue with modern compilers.
Edit: also worth mentioning that some of the early implementations of this were very inefficient so you might see complaints from that time, but this is not an issue with modern compilers.
Thanks for pointing this out. I also tried and failed to find "anonymous data allocations". Although (having just read about them) I fail to see how I'd use your proposed string structure to retro-fit an existing codebase using good old char* strings.
The basic idea is to wrap all use of arrays with wrapper functions or macros that take the structure with length and have those wrappers access the array after performing bounds checking. So you would want to never pass a raw array as a function argument, but before compound literals there was fundamentally no good way to change a string literal to such a structure in a function argument that wouldn't violate other basic programming principles. There are still a variety of implementation choices and it is by no means an easy retrofit, but the result can be entirely reasonable. Interacting with 3rd party and standard library code can be awkward and depends on implementation choices (e.g. '\0' termination or not and the related how much of libc do you rewrite). There have been a number of string libraries over the years making various implementation choices, but no general implementation has become all that popular and it seems like most implementations are project specific.
[deleted]
Is this implemented in Coverity by a local model? (There is reference to a model being applied) Or was the actual product modified to support this? Can Coverity customers get ahold of this now?
The "model" makes reference of the model injection for memcpy.
The modification made by the team is referenced in John's blog post "Their insight is that we might want to consider byte-swap operations to be sources of tainted data".
As Andy said (and quoted), that's a modification that we need to evaluate overall to look at its impact in term of false positives (FP). It will probably be made available however under some options if it doesn't pass our acceptance tests for FP rate though... a bit too early to say.
The modification made by the team is referenced in John's blog post "Their insight is that we might want to consider byte-swap operations to be sources of tainted data".
As Andy said (and quoted), that's a modification that we need to evaluate overall to look at its impact in term of false positives (FP). It will probably be made available however under some options if it doesn't pass our acceptance tests for FP rate though... a bit too early to say.
Thanks, I was just curious if customers could play with these kind of experiments if they understood the FP potential. I really like Coverity's output and always like new ways to tease out potential bugs.
Taint analysis is notoriously prone to false positives; as well as the reasons listed in this post, there are many situations where relations between variables mean that tainted data doesn’t cause problems. [For example, the size of the memcpy target (bp) is known to be greater than payload; so even though payload is tainted, there isn't a risk of a write overrun.] But even noisy warnings can be very useful — when we first implemented simple taint analysis in PREfix a decade ago, the first run was 99% false positives but one of the real bugs we found was in a system-level crypto module. So with the increased attention to these kinds of bugs after Heartbleed, seems like a great time for more attention to these classes of bugs.