PLEX86  x86- Virtual Machine (VM) Program
 Plex86  |  CVS  |  Mailing List  |  Download  |  Computer Folklore

Thou shalt have no other gods before the ANSI C standard 1600

Trevor L. Jackson, III

Thou shalt have no other gods before the ANSI C standard 1601
David Wagner ... snip ... But this is precisely what is already feasible (and done) in Pascal and Ada, where it is possible to declare sub-range types. As ever, the programmer can foul...

Yes, I think this is exactly it. I find this a very useful way to think about things. I was introduced to this style of thinking by Drew Dean, but I've never heard it articulated by anyone else.

Caveat: Buffer overruns can still be problematic even if they only give the adversary the ability to overwrite blue addresses. For instance, the attacker might be able to change the behavior of the program by tampering with some critical internal variable. Nonetheless, many buffer overruns today take the form of tampering with red addresses, and most of the time it seems sufficient to confine our thinking to detecting cases where the attacker gains the power to write to red addresses.

You may enjoy the following paper: David Wagner, Jeffrey S. Foster, Eric A. Brewer, and Alexander Aiken. A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. It reports experience with an attempt to use a form of interval analysis to detect, for every program variable, the maximum and minimum values that variable could take on. It then attempts to detect cases where a pointer can be used to write outside the memory object that it points into. We buttociate each memory object (e.g., any object allocated on the stack or heap, or any stretch of memory returned by a call to malloc()) with a variable that represents its length, and we look for accesses to memory objects that may violate bounds.

One major problem with the analysis described above is that leads to too many false alarms. It is unable to deal well with dynamically allocated memory objects. For instance, if we have the code snippet: char *p = malloc(n); ... pi ... then what we need to know to be sure that this is safe is to know that variables, not just the upper bound of either.

Thou shalt have no other gods before the ANSI C standard 1605
Jean-Marc Bourguet Usually I use source-line usage counters, as in the following Makefile target which exploits "ctrace": $(PCFILES): $(HFILES) $(CFILES) $(OBJS...

Another problem with the analysis described above is that it is unsound: it can miss bugs. This is because dealing with pointers and aliasing in C is very painful. The main source of the problem is the "strong update" problem. Consider the following snippet of code: int f(int *p, int *q) { *p = 5; *q = 7; return *p; } If you want to claim that f() returns 5, you need to know that p and q don't alias. Accurate aliasing information is hard to infer. And without accurate aliasing information, you're stuck with doing a "weak update", which means that whenever you see something like "*p = 0;", then each int variable that p could point to is updated to contain either the value it previously hard or 0 (we don't know which; both are possible). The above example looks artificial, but the "strong update" problems comes up all over the place in real code and is highly non-trivial to deal with.

I don't think I know how to build a tool to detect buffer overruns in legacy code that could be both sound (detect all bugs) and precise (not have too many false positives). But if you have any ideas on how to do that, such a tool would be terribly useflu.

Absolutely. CPU time is a lot cheaper than programmer time.

That all depends on how much work it is to interpret the results. If the output is essentially a list of all places in the program where any pointer write occurs, and the onus is on the human to check every single one manually, that would probably require so much effort that such a tool would have almost no impact. But if the tool was precise enough that its "real bug" to "false positive" rate was not too terribly (a ratio of 1:10 might be tolerable), then I think that would be extremely useful and most definitely worth building.

List | Previous | Next

Thou shalt have no other gods before the ANSI C standard 1601

Alt Folklore Computers Newsgroups

Thou shalt have no other gods before the ANSI C standard 1599