I noted just as I sent my previous posting with two references to
fuzz-test papers that the abstract of the second mentions two earlier
ones.
I've just tracked them down, and added them to various bibliographies.
Here are short references to them:
Fuzz Revisited: A Re-examination of the Reliability of UNIX
Utilities and Services
ftp://ftp.cs.wisc.edu/pub/techreports/1995/TR1268.pdf
An Empirical Study of the Robustness of MacOS Applications
Using Random Testing
http://dx.doi.org/10.1145/1228291.1228308
-------------------------------------------------------------------------------
- Nelson H. F. Beebe Tel: +1 801 581 5254 -
- University of Utah FAX: +1 801 581 4148 -
- Department of Mathematics, 110 LCB Internet e-mail: beebe(a)math.utah.edu -
- 155 S 1400 E RM 233 beebe(a)acm.org beebe(a)computer.org -
- Salt Lake City, UT 84112-0090, USA URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------
> Ken and Dennis and the other guys behind
> the earliest UNIX code were smart guys and good programmers,
> but they were far from perfect; and back in those days we
> were all a lot sloppier.
The observation that exploits may be able to parlay
mundane bugs into security holes was not a commonplace
back then--even in the Unix room. So input buffers were
often made "bigger than ever will be needed" and left
that way on the understanding that crashes are tolerable
on outlandish data. In an idle moment one day, Dennis fed
a huge line of input to most everything in /bin. To the
surprise of nobody, including Dennis, lots of programs
crashed. We WERE surprised a few years later, when a journal
published this fact as a research result. Does anybody
remember who published that deep new insight and/or where?
Doug
> From: norman(a)oclsc.org (Norman Wilson)
> SP&E published a paper by Don Knuth discussing all the many bugs found
> in TeX, including some statistical analysis.
> From: John Cowan <cowan(a)mercury.ccil.org>
> "The Errors of TeX" was an excellent article.
Thanks for the pointer; it sounds like a great paper, but alas the only
copies I could fine online were behind paywalls.
> From: Clem Cole <clemc(a)ccc.com>
> btw. there is a v6 version of fsck floating around.
Yes, we had it at MIT.
> I'm wonder if I can find a readable copy.
As I've mentioned, I have this goal of putting the MIT Unix (the kernel was
basically PWB1, with a host of new applications) sources online.
I have recently discovered (in my basement!) two sets of full dump tapes
(1/2" magtape) of what I think are the whole filesystem, so if I can find a
way to get them read, we'll have the V6 fsck - and much more besides (such
as a TCP/IP for V6). So I think you may soon get your wish!
Noel
> From: "Ron Natalie" <ron(a)ronnatalie.com>
> The variable in question was a global static, 'ino' (the current inode
> number),
> Static is a much overloaded word in C, it's just a global variable.
Sorry; I was using 'static' in the general CS sense, not C-specific!
> in the version 7 version of icheck .. they appear to have fixed it.
Actually, they seem to have got all three bugs I saw (including the one I
hadn't actually experienced yet, which would cause a segmentation violation).
> From: Tim Newsham <tim.newsham(a)gmail.com>
> There are bugs to be found .. Here are some more (security related, as
> thats my inclination):
> ...
> http://minnie.tuhs.org/pipermail/unix-jun72/2008-May/000126.html
Fascinating mailing list! Thanks for the pointer.
Noel
A. P. Garcia <a.phillip.garcia(a)gmail.com> wrote:
> Were the original Unix authors annoyed when they learned that
> some irascible young upstart named Richard Stallman was determined to make
> a free Unix clone?
A deeper, more profound question would be: how did these original Unix
authors feel about their employer owning the rights to their creation?
Did they feel any guilt at all for having had to sign over all rights
in exchange for their paychecks?
Did Dennis and/or Ken personally wish their creation were free to the
world, public domain, or were they personally in agreement with the
licensing policies of their employer? I argue that this question is
far more important than how they felt about RMS (if they cared at all).
Ronald Natalie <ron(a)ronnatalie.com> wrote:
> [RMS] If you read his earlier manifesto rants he hated UNIX =
> with a passion.
> Holding out the TOPS operating systems as the be-all and end-all of user =
> interface.
I wish more people would point out this aspect of RMS and GNU. While
I wholeheartedly agree with Richard on the general philosophy of free
software, i.e., the *ethics* part and the Four Freedoms, when it comes
to GNU as a specific OS, in technical terms, I've always disliked
everything about it. I love UNIX, and as Ron pointed it out like few
people do, GNU was fundamentally born out of hatred for the thing I
love.
SF
So it turns out the 'dcheck' distributed with V6 has two (well, three, but
the third one was only a potential problem for me) bugs it.
The first was a fence-post error on a table clearing operation; it could
cause the entry for the last inode of the disk in the constructed table of
directory entry counts to start with a non-zero count when a second disk was
scanned. However, it was only triggered in very specific circumstances:
- A larger disk was listed before a smaller one (either in the command line,
or compiled in)
- The inode on the larger disk corresponding to the last inode on the smaller
one was in use
I can understand how they never ran across this one.
The other one, however, which was an un-initalized variable, should have
bitten them anytime they had more than one disk listed! It caused the
constructed table of directory entry counts to be partially or wholly
(depending on the size of the two disks) blank in all disks after the first
one, causing numerous (bogus) error reports.
(It was also amusing to find an un-used procedure in the source; it looks
like dcheck was written starting with the code for 'icheck' - which explains
the second bug; since the logic in icheck is subtly different, that variable
_is_ set properly in icheck.)
How this bug never bit them I cannot understand - unless they saw it, and
couldn't be bothered to find and fix it!
To me, it's completely amazing to find such a serious bug in such a critical
piece of widely-distributd code! A lesson for archaeologists...
Anyway, a fixed version is here:
http://ana-3.lcs.mit.edu/~jnc/tech/unix/ucmd/dcheck.c
if anyone cares/needs it.
Noel
Larry McVoy scripsit:
> I love Rob Pike, he's spot on on a lot of stuff. I'm a big fan of
> "if you think you need threads then your processes are too fat".
Oh, he's a brilliant fellow. I don't know him personally, but I know
people who do, and I don't think I'd love him if I knew him. Humanity has
always found it useful to keep its (demi)gods at arm's length at least.
--
John Cowan http://www.ccil.org/~cowan cowan(a)ccil.org
Barry thirteen gules and argent on a canton azure fifty mullets of five
points of the second, six, five, six, five, six, five, six, five, and six.
--blazoning the U.S. flag
> From: jnc(a)mercury.lcs.mit.edu (Noel Chiappa)
> the second (the un-initialized variable) should have happened every
> time.
OK, so I was wrong! The variable in question was a global static, 'ino' (the
current inode number), so the answer isn't something simple like 'it was an
auto that happened to be cleared for each disk'. But now that I look closely,
I think I see a way it might have worked.
'dcheck' is a two-pass per disk thing: it begins each disk by clearing its
'inode link count' table; then the first pass does a pass over all the inodes,
and for ones that are directories, increments counts for all the entries; the
second pass re-scans all the inodes, and makes sure that the link count in the
inode itself matches the computed count in the table.
'ino' was cleared before the _second_ pass, but not the _first_. So it was
zero for the first pass of the first disk, but non-zero for the first pass on
the second disk.
This looks like the kind of bug that should almost always be fatal, right?
That's what I thought at first... (and I tried the original version on one of
my machines to make sure it did fail). But...
The loop in each pass has two index variables, one of which is 'ino', which it
compares with the maximum inode number for that disk (per the super-block),
and bails if it reaches the max:
for(i=0; ino<nfiles; i =+ NIBLK)
If the first disk is _larger_ than the second, the first pass will never
execute at all for the second desk (producing errors).
However, if the _second_ is larger, then the second disk's first pass will in
fact examine the starting (nfilesSUBsecond - nfilesSUBfirst) inodes of the
second disk to see if they are directories (and if so, count their links).
So if the last nfilesSUBfirst inodes of the second disk are empty (which is
often the case with large drives - I had modified 'df' to count the free
inodes as well as disk blocks, and after doing so I noticed that Unix seems to
be quite generous in its default inode allocations), it will in fact work!
The fact that 'ino' is wrong all throughout the first pass of the second disk
(it counts up from nfilesSUBfirst to nfilesSUBsecond) turns out to be
harmless, because the first pass never uses the current inode number, it only
looks at the inode numbers in the directories.
Note that with two disks of _equal size_, it fails. Only if the second is
larger does it work! (And this generalizes out to N disks - as long as each
one is enough larger than the one before!) So for the config they were
running (rk2, dp0) it probably did in fact work!
Noel
Noel Chiappa:
To me, it's completely amazing to find such a serious bug in such a critical
piece of widely-distributd code! A lesson for archaeologists...
======
To me it's not surprising at all.
On one hand, current examples of widely-distributed critical
code containing serious flaws are legion. What, after all,
were the Heartbleed and OS X goto fail; bugs? What is every
version of Internet Explorer?
On the other hand, Ken and Dennis and the other guys behind
the earliest UNIX code were smart guys and good programmers,
but they were far from perfect; and back in those days we
were all a lot sloppier.
So surprising? No. Interesting? Certainly. All bugs are
interesting.
(To me, anyway. Back in the 1980s, when I was at Bell Labs,
SP&E published a paper by Don Knuth discussing all the many
bugs found in TeX, including some statistical analysis. I
thought it fascinating and revealing and think reading it
made me a better programmer. Rob Pike thought it was terribly
boring and shouldn't have been published. Decidedly different
viewpoints.)
Norman Wilson
Toronto ON
> From: Ronald Natalie <ron(a)ronnatalie.com>
> If I understand what you are saying, it only occurs when you run dcheck
> with mutliple volumes at one time?
Right, _both_ bugs have that characteristic. But the first one (the
fence-post) only happens in very particular circumstances; the second (the
un-initialized variable) should have happened every time.
> From: norman(a)oclsc.org (Norman Wilson)
> To me it's not surprising at all.
> On one hand, current examples of widely-distributed critical code
> containing serious flaws are legion.
What astonished me was not that there was a bug (which I can easily believe),
but that it was one that would have happened _every time they ran it_.
'dcheck' has this list of disks compiled into it. (Oh, BTW, my fixed version
now reads a file, /etc/disks; I am running a number of simulated machines,
and the compiled-in table was a pain.)
So I would have thought they must have at least tried that mode of operation
once? And running it that way just once should have shown the bug. Or did
they try it, see the bug, and 'dealt' with it by just never running it that
way?
Noel
