Heartbleed and Static Analysis

http://blog.regehr.org/archives/1125

by pascal_cuoq • 12 years ago

134 36 12 years ago

blog.regehr.org

willvarfar• 12 years ago

I presume, from their silence, that competing products also fail to find this bug?

jetru• 12 years ago

There are numerous reasons for this, as Regehr points out. None of these products are "sound". In other words, they aren't guaranteed to find everything. Most of the time, these are tradeoffs to reduce the number of false positives and to speed up the analysis, which come with the risk of false negatives, as is the case here.

aidenn03• 12 years ago

Indeed, trading off sensitivity for specificity is always a win when trying to sell static analysis to people.

Considering that any non-trivial piece of software has a fairly large number of bugs, you can dial the sensitivity way down and still find some bugs, and the high specificity looks really impressive "Most of what it labelled as bugs really were!"

Consider the hypothetical situation where your piece of software has 40 bugs in it (but you don't know that).

If you see a report of 10 bugs and 6 of them are real, that looks more impressive than a report of 100 bugs where 20 of them are real, despite the fact that the latter actually found more bugs. In fact there is a non-trivial chance that the first 5 or 10 bugs you look at in the latter will be false-positives.

Obviously if your specificity goes too low, the payoff of inspecting each report starts to become questionable, but I think that to successfully market an analysis took, you need to sacrifice more sensitivity for specificity than merited by a rational analysis of the cost/benefit of detecting the bugs early.

ScottBurson5• 12 years ago

I can confirm that HP Fortify SCA does not find this bug.

(I am the architect for the SCA team.)

malanj• 12 years ago

Static analysis (and other "expensive" techniques) should really be standard on something as critical as OpenSSL.

If I compare the effort we've had to go through building things that are allowed into a banking environment the OpenSSL project is very underfunded. Somehow we have to solve this "tragedy of the commons" problem in open source. OpenSSL must be worth millions of dollars to so many companies, but almost no-one cares about it. It seems very strange that the project is not getting BIG corporate sponsorship, given the value of the data it helps to protect.

ScottBurson5• 12 years ago

The problem is that it's worth a relatively small amount of money to each of a huge number of people. We don't have a good way to pool funds for maintaining open source software in such a situation.

Crowdfunding seems to be the obvious solution. But I asked in a previous Heartbleed discussion whether people would be willing to try it for OpenSSL, and got no response.

Someone else commented that maybe Google will take over OpenSSL, or at least become a major contributor to it. It probably is in their interests to make sure this doesn't happen again -- maybe it's worth a large enough amount of money to them to justify dedicating a couple of engineers to it for a couple of years, which is what it seems to need.

unwind• 12 years ago

Very interesting article!

A small typo, there's a sentence after the Frama-C code block that ends "[...] and that a subsequent memcpy() of the two regions will return zero" which should have a s/memcpy/memcmp/. Quite obvious, but in an article such as this it's best to be precise of course.

WalterBright5• 12 years ago

It's interesting that these sorts of problems with memcpy, etc., always boil down to the same thing - C arrays are lowered to simple pointers when they are passed as function arguments. This means they lose their array bounds, frustrating attempts at overflow detection. This has caused endless bugs and endless workaround schemes of varying complexity. I wrote about it as "C's Biggest Mistake" a while back:

http://www.drdobbs.com/architecture-and-design/cs-biggest-mi...

and offered a simple adjustment to C to fix it. I quote from the article:

All it needs is a little new syntax:

    void foo(char a[..])

meaning an array is passed as a so-called "fat pointer", i.e. a pair consisting of a pointer to the start of the array, and a size_t of the array dimension. Of course, this won't fix any existing code, but it will enable new code to be written correctly and robustly.

rwmj• 12 years ago

This is basically what Bounds Checking GCC[1] did. Except instead of changing the syntax or using fat pointers, it kept a map of (pointer -> bounds), allowing memcpy to check the bounds of any arbitrary runtime pointer, and to interwork with code that isn't compiled with the -fbounds-checking flag.

[1] https://www.doc.ic.ac.uk/~phjk/BoundsChecking.html

chalst• 12 years ago

Your analysis of the issue of not being able to pass arrays as arguments is compelling, but I'm not so sure about "All it needs is a little new syntax" as a solution: you say how to keep backwards compatibility with existing C standards you need a #if cpp-directive: that's already a code health and maintenance problem that isn't going to go away.

Regehr's suggestion of using assertions hidden in code avoids that: isn't it better? You could have just a comment directive like

     @ arraycast char* a \represents char a[..]

and then you wouldn't need any cpp-directives.

Serow225• 12 years ago

I've always been curious why C was designed this way, was it thought to offer any advantages or just done to make the compiler writer's job easier?

Someone• 12 years ago

Unix and C were written in an agile fashion. C was a step up from a macro assembler, to be used for writing an operating system. String manipulation is rare in operating systems, certainly in those days (even if you felt a need, you don't have much room to create new strings in if your system and its applications must run in 64 kilobytes of RAM (144 kB for the PDP 11/45; see http://cva.stanford.edu/classes/cs99s/papers/ritchie-thompso...)

The filesystem was about the only place where strings got manipulated and there, filenames were stored in fixed-size (14 bytes) buffers. Since all code could know strings were at most 14 bytes, having a complex type (pointer,length) was deemed a waste of memory and performance there. Everything else followed from that.

emmelaich• 12 years ago

It would have made C a profoundly different language. C is what it is; a portable assembler. I believe K&R had a strong sense of minimalism; fancier string s would be seen as something that belonged in a library not the language.

This has its benefits; _anything_ fancier would have embedded a whole set of assumptions about typical string handling usage for which the design had optimised.

That no safer string handling library became popular can be seen as a indictment of C or a tribute to their tasteful restraint.

Peaker2• 12 years ago

It would help, but it wouldn't get rid of the errors.

It would convert corruption/security bugs into other, much safer runtime errors.

To get rid of the runtime error altogether, we need a stronger type system or a different form of static analysis, as mentioned here.

Also, the extra bounds checking might be somewhat expensive in some scenarios, especially as the fat pointers would consume many more cache lines than thin pointers.

pcwalton• 12 years ago

Cyclone [1] did this, among many other things. They actually got C provably memory-safe, though they sacrificed a fair amount of performance doing so.

[1] http://cyclone.thelanguage.org/

pjmlp• 12 years ago

Having grown with safe languages back when C was a UNIX only thing I always consider that FUD from C people.

Back then, C optimizers were not better than Object Pascal/Modula-2 ones and similar languages. It was all down to profiling and switching off bounds checking in specific code sections.

Of course, with time compilers got better, while at the same time safer languages lost to UNIX widespread into the industry creating this idea in younger generations only C can have fast code.

ScottBurson5• 12 years ago

C's second biggest mistake, IMO, is NUL-terminated strings. The combination of these two mistakes is much worse than either of them alone. Since you don't know where a string ends without scanning it, and nothing prevents you from writing off the end of the allocated space, the familiar 'strcpy' etc. are loaded guns with hair triggers.

WalterBright5• 12 years ago

I'd argue that the nul-terminated strings is a direct consequence of arrays decaying to pointers when passed to functions.

Ono-Sendai• 12 years ago

I think this is a good demonstration of the limitations of static analysis - for a language like C, there will always be bugs that can't be found statically.

Peaker2• 12 years ago

Unless you're willing to move the burden to the programmer, to prove correctness.

Bugs can always be found statically, but there may always be bugs that evade all the static analysis you happened to do.

joosters• 12 years ago

Presumably, the static analysis won't find this bug because the 'out of bounds' memory that heartbleed accesses isn't necessarily out of bounds?

As has been explained elsewhere, OpenSSL has a wrapper around malloc() and free() so that it re-uses allocations. This means that the 64k of buffer used to send the heartbeat response is data that has never been free()d and has previously been written to by the process.

To make the static analysis spot this kind of thing, I'd guess you'd have to mark/label the OpenSSL allocators as being 'like' malloc. Likewise, valgrind would also not spot the faults without extra knowledge.

platz2• 12 years ago

Also of note was Leslie Lamport's recent talk on how Amazon uses TLA+ to verify algorithms.

bojblaz• 12 years ago

Googled to no avail... link please?

platz2• 12 years ago

http://channel9.msdn.com/Events/Build/2014/3-642

Heartbleed and Static Analysis

Related Stories