33-Year-Old Unix Bug Fixed In OpenBSD

Ste sends along the cheery little story of Otto Moerbeek, one of the OpenBSD developers, who recently found and fixed a 33-year-old buffer overflow bug in Yacc. "But if the stack is at maximum size, this will overflow if an entry on the stack is larger than the 16 bytes leeway my malloc allows. In the case of of C++ it is 24 bytes, so a SEGV occurred. Funny thing is that I traced this back to Sixth Edition UNIX, released in 1975."

Comments

Time to patch

[Anonymous Coward]

Wouldn't want to let anyone take over your system with yacc. Seriously.

Re:Time to patch

[slew]

Wouldn't want to let anyone take over your system with yacc. Seriously.

But ./ is already taken over with yak. Seriously.

Re:Time to patch

[Anonymous Coward]

Who cares about OpenBSD yacc? BSD is dying and Netcraft confirms it. The world has moved to GNU/Linux and Bison.

Re:Time to patch

[msuarezalvarez]

So you are including bison in your own apps and its `bloatedness' becomes a problem? Maybe you should read the manpage...

Re:Time to patch

[setagllib]

Who cares? Like GCC versus TinyCC, being bloated means it can produce a more useful output. GNUware can be faulted for being heavy compared to traditional Unix tools, but the functionality and flexibility provided more than makes up for it.

Except for autotools. What the HELL were they thinking.

Re:Time to patch

[setagllib]

Ah, but it would be written as a J2EE application. And the input wouldn't be .y, it'd be an XML document. And the output wouldn't be C, it'd be another XML, passing through a terabyte of XSLT. Then you pass this compiled parser XML, only a gigabyte in size, and your language file to a parser web service and it returns even more XML representing the parse tree.

Ahh, progress.

Re:Time to patch

[TapeCutter]

Great post, I'm still laughing as I type.

Speaking of old bugs the guy who sits next to me at work hooked a 15yo mainfame bug a few months back. His stock comment whenever someone mentions it is: "Three more years and that one would have been old enough to vote!"

From back when

[Yold]

Unix beards were Unix stubble

bad omen

[spir0]

a 33 year old bug, plus a 25 year old bug (http://it.slashdot.org/article.pl?sid=08/05/11/1339228)....

if we keep going backwards, will the world implode? or will daemons start spewing out of cracks in time and space?

Re:bad omen

[je ne sais quoi]

Nah! What this means is that they are fixing bugs faster than they're making new ones. If they weren't, they'd spend all their time chasing the newest ones. :)

Re:bad omen

[exley]

a 33 year old bug, plus a 25 year old bug (http://it.slashdot.org/article.pl?sid=08/05/11/1339228)....

if we keep going backwards, will the world implode?

Well since time began only 38.5 years ago we should find out the answer very soon!

Re:bad omen

[Dunbal]

or will daemons start spewing out of cracks in time and space?

      I finally figured out what the UAC were doing on the Mars colony... and it had nothing to do with those artifacts!

      Thank god there's a division of Space Marines there...

Re:bad omen

[Dunbal]

It's just as possible people are wasting time fixing unimportant issues and ignoring more important ones.

      We're talking programmers here, not politicians...

Re:bad omen

[K. S. Kyosuke]

First it was a fourth of a century, then it was a third of a century. The only logical consequence is that the next bug they will find now will be a memory leak in McCarthy's Lisp intepreter from '59 or some strange corner case in the Fortran I compiler. (Oh, and after a careful consideration, I am leaving the *next* bug as an exercise to the reader.)

Re:bad omen

[menace3society]

The next bug will be in Boolean logic. After that, OpenBSD devs will start fixing structural engineering errors the Tower of Pisa.

Re:bad omen

[incripshin]

Well, they're not checking yacc for bugs for the hell of it. They're reimplementing malloc to be more efficient, but it broke buggy code. Is there any other option than to fix yacc?

Re:bad omen

[Jurily]

Sure. Break malloc even worse to allow for backwards compatibility.

See "Windows 95".

Re:bad omen

[laejoh]

In exactly 3.5 years , but I'm afraid the answer will disappoint you.

Great!

[Anonymous Coward]

Any word on when they're going to fix the even older "Too many arguments" bug?

Sorry, but any modern system where a command like "ls a*" may or may not work, based exclusively on the number of files in the directory, is broken.

Re:Great!

[The Master Control P]

I too was devastated to learn that my poor Linux box can only handle 128KB of command line arguments. How can I possibly finish typing in that uncompressed bitmap...

Re:Great!

[Dadoo]

While I'm sure you're trolling, I feel I should point out that, 1) I agree with you, and 2) this has apparently been fixed, on Linux:

        http://agnimidhun.blogspot.com/2007/08/vi-editor-causes-brain-damage-ha-ha-ha.html

Re:Great!

[Craig Davison]

If "ls a*" isn't working, it's because the shell is expanding a* into a command line >100kB in size. That's not the right way to do it.

Try "find -name 'a*'", or if you want ls -l style output, "find -name 'a*' -exec ls -l {} \;"

Re:Great!

[menace3society]

Burn the contents of the tar archive onto a CD. Mount the CD over the original directory structure. Use find(1)'s -fstype option to locate all the files that aren't on the CD, copy them to an empty disk image, then eject the CD. Remount the disk image over the original directory, delete all the files in the directory, then unmount the disk image. The files identical in name to those that were on the disk image (which are those that weren't on the CD) won't be deleted thanks to the peculiarities of mount(2).

You're welcome.

Re:Great!

[Just Some Guy]

if you want ls -l style output, "find -name 'a*' -exec ls -l {} \;"

Yeah, because nothing endears you with the greybeards like racing through the process table as fast as possible. Use something more sane like:

$ find -name 'a*' -print0 | xargs -0 ls -l

which only spawns a new process every few thousand entries or so.

Re:Great!

[Jeffrey Baker]

It's both. The kernel is responsible for setting up the execution environment, and in the past it used a fixed 32 pages for the arguments. 32 pages on an ordinary PC is 128KiB, which is the old limit. The new limit is that any one argument can be up to 32 pages, and all the arguments taken together can be 0x7FFFFFFF bytes, which is ~2GiB.

Here's the diff: http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=b6a2fea39318e43fee84fa7b0b90d68bed92d2ba;hp=bdf4c48af20a3b0f01671799ace345e3d49576da

After that, it was up to libc people to fix the globbing routines. Ulrich Drepper, taking some time off from his full-time job of being an asshole on mailing lists, managed to work this into glibc 2.8:

http://sourceware.org/ml/libc-alpha/2008-04/msg00050.html

Re:Great!

[maztuhblastah]

So Saturdays at your house must be a real blast, huh?

Yeah, it's probably you.

[Estanislao Mart�nez]

I bet you they're not talking about the system stack pointer. Remember, yacc is a parser generator; parsing algorithms always use some sort of stack data structure. So, the "stack pointer" in question is just a plain old pointer, pointing into a stack that yacc's generated code uses.

Re:Yeah, it's probably you.

[tomhudson]

From the link you cited:

By 1971, our miniature computer center was beginning to have users. We all wanted to create interesting software more easily. Using assembler was dreary enough that B, despite its performance problems, had been supplemented by a small library of useful service routines and was being used for more and more new programs. Among the more notable results of this period was Steve Johnson's first version of the yacc parser-generator [Johnson 79a].

The code for yacc was certainly not originally written in c - c didn't exist at that time.

In 1978 Brian Kernighan and I published The C Programming Language [Kernighan 78]. Although it did not describe some additions that soon became common, this book served as the language reference until a formal standard was adopted more than ten years later.

The "archaic behaviour" was never part of that standard - it was a mistake in early implementations while they were still "working out the details" of the language, well before K & R, as Ritchie says:

After the TMG version of B was working, Thompson rewrote B in itself (a bootstrapping step). During development, he continually struggled against memory limitations: each language addition inflated the compiler so it could barely fit, but each rewrite taking advantage of the feature reduced its size. For example, B introduced generalized assignment operators, using x=+y to add y to x. The notation came from Algol 68 [Wijngaarden 75] via McIlroy, who had incorporated it into his version of TMG. (In B and early C, the operator was spelled =+ instead of += ; this mistake, repaired in 1976, was induced by a seductively easy way of handling the first form in B's lexical analyzer.)

It wasn't an archaism in c - it was an archaism from b that was removed during the development of what became c. Small difference, and for all practical purposes, it gives the same result - previously-working code that wasn't reviewed as the language evolved towards a standard ended up with "implementation-dependent behaviour" - bugs ... The worst part is that the buggy code is syntactically correct, so no compiler warnings. Of course, if your conforming compiler doesn't give a warning, you assume that the code written with the experimental versions is still valid.

Was it really a bug back then?

[Just Some Guy]

Was this a bug when it was originally written, or is it only because of recent developments that it could become exploitable? For instance, the summary mentions stack size. I could imagine that a system written in 1975 would be physically incapable of the process limits we use today, so maybe the program wasn't written to check for them.

Does your software ensure that it doesn't use more than an exabyte of memory? If it doesn't, would you really call it a bug?

Re:Was it really a bug back then?

[QuantumG]

If you overflow a buffer then it's a bug, whether it is exploitable or not.

Re:Was it really a bug back then?

[russlar]

If you overflow a buffer then it's a bug, whether it is exploitable or not.

If you can overflow an exabyte-sized memory buffer, you deserve a fucking medal.

Re:Was it really a bug back then?

[AJWM]

/*Where's my medal?*/

You'll get it when the buffer overflows. If you're running it on a system that processes a billion of those loops per second, that should be in a bit over 31 years. Scale accordingly for your processor and memory speed.

Re:Other Unixes

[X0563511]

Yes. But OpenBSD fixed it, so they get credit for the fix. It's up to the maintainers of the other unix(ish) versions to implement the fix.

Re:You do realize..

[QuantumG]

yacc is not a compiler,

Excuse me?

Yet Another Compiler Compiler most definitely is a compiler.

Re:You do realize..

[wb8wsf]

OpenBSD still uses GCC, version 3.3.5 on i386. I can't say which version is used on the other platforms.

You are talking of PCC, which is being worked on by some of the OpenBSD developers, but I think its a parallel project, see http://pcc.ludd.ltu.se/
for more information.

Jem Matzen talked of this too, see http://www.thejemreport.com/mambo/content/view/369/

Re:You do realize..

[incripshin]

gcc still is the default. pcc isn't ready yet, and I don't expect it to be for at least a couple years, and I say that with zero confidence (I'm just an OpenBSD user; I have no idea how the progress is going on pcc).

Hilarious!

[BollocksToThis]

Funny thing is that I traced this back to Sixth Edition UNIX, released in 1975

My sides are completely split! Invite this guy to more parties.

The Problem is *why* it's the wrong way to do it

[billstewart]

You're correct that's it's not the right way to do it. The problem is *why* it's not the right way to do it. It's not the right way to do it because the arg mechanism chokes on it due to arbitrary limits, and/or because your favorite shell chokes on it first, forcing you to use workarounds. Choking on arbitrary limits is a bad behaviour, leading to buggy results and occasional security holes. That's separate from the question of whether it's more efficient to feed a list of names to xargs or use ugly syntax with find.

Now, if you were running v7 on a PDP-11, there wasn't really enough memory around to do everything without arbitrary limits, so documenting them and raising error conditions when they get exceeded is excusable, and if you were running on a VAX 11/780 which had per-process memory limits around 6MB for some early operating systems, or small-model Xenix or Venix on a 286, it's similarly excusable to have some well-documented arbitrary limits. But certainly this stuff should have been fixed by around 1990.