Re: [Lit.] Buffer overruns

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 02/03/05 

Date: Thu, 3 Feb 2005 07:55:50 +0000 (UTC)

>Here's a reduction from the halting problem to checking for buffer
>overflows: Say you've got a function f(x) and you want to see if it
>halts. Now add the following function:
>
> void g(whatever x) {
> int b[2];
> f(x);
> b[2] = 0;
> }
>
>You get a buffer overflow on b[] iff f(x) returns (halts).
>
>Maybe that's a silly example, but it shows the undecidability of
>determining whether a program has a buffer overflow.

Solution: You build a conservative tool. In case of doubt (i.e., if
you cannot prove the program/construct safe), you output a warning.
You might get false positives -- indeed, for buffer overrun analysis
of large C programs, you will surely get false positives, and lots of
them -- but you don't have the undecidability problem any further.

For instance, a conservative tool would output a warning about a possible
buffer overrun in the code you gave, unless it could prove that f(x)
never returns.

It turns out that there is a general theorem, called Rice's theorem,
which roughly speaking says that checking any non-trivial property
is undecidable. (The definition of non-trivial is pretty broad, and
primarily serves to exclude properties that are either true for all
programs or false for all programs.) This is sometimes jokingly known
as the "full-employment theorem for programming language folks". The way
you get around undecidability is almost always the same; you allow to err
in one direction or the other. For instance, almost any kind of program
optimization is undecidable; nonetheless, a good optimizer will only apply
the optimization if it can prove that the optimization won't alter program
behavior, and otherwise won't apply the optimization in case of doubt.

Relevant Pages

  • Re: [Lit.] Buffer overruns
    ... >>determining whether a program has a buffer overflow. ... > you get around undecidability is almost always the same; ... > optimization is undecidable; nonetheless, a good optimizer will only apply ... So maybe there's a useful subset of C that can be accurately ...
    (sci.crypt)
  • Re: Direct Copying To Share Memory In NDIS ProtocolReceive
    ... WaitXXX() functions that involve user-to-kernel transition before they can ... access the buffer. ... and see how it all works - I wold start thinking about optimization ...
    (microsoft.public.development.device.drivers)
  • Re: Is there a STL equivalent of sprintf
    ... number of conversions. ... Have you considered ostrstream or istrstream with a fixed size buffer? ... I've played around with various optimization before and I think I've tested fix buffers too. ... Since sprintf is used internally in stringstreams I don't see a performance advantage to prefer the stream library for string conversion of integers. ...
    (microsoft.public.vc.stl)
  • Re: Performance of lists vs. list comprehensions
    ... buffer after its last expansion and no saved tuple). ... As near as I can determine, the CPython optimization you are referring to ... The optimization patch is here: ... algorithm is, ...
    (comp.lang.python)