[TUHS] Bugs in V6 'dcheck'

[TUHS] Bugs in V6 'dcheck'

[Doug McIlroy]

> 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

[TUHS] Bugs in V6 'dcheck'

[Kevin Schoedel]

At 7:24 ?pm -0400 2014/05/31, Doug McIlroy wrote:
>Does anybody
>remember who published that deep new insight and/or where?

Probably this:
B.P. Miller, L. Fredriksen, So, B. "An Empirical Study of the Reliability
of UNIX Utilities", Communications of the ACM 33, 12 (December 1990)


-- 
Kevin Schoedel <schoedel at kw.igs.net> VA3TCS

[TUHS] Bugs in V6 'dcheck'

[scj]

Doug is quite right that we were much more relaxed about security then. 
THe academic world was very much inspired at the time by the idea that one
could prove programs correct using mathematics.  I remember having some
very spirited arguments on this topic with some academics.  My argument
was roughly "Proving programs is stupid.  Look at Unix.  It's insanely
useful, but most programs can't be proved correct because they aren't!". 
Buffer overflow was one of the bugs I had in mind.  It was embarrassing in
later years to read about all the hackers exploiting these bugs.

In our defence, with only <= 64KB for programs and data and the slow
machines of the day, dynamic allocation and subscript checking were often
impractical...

Steve



> At 7:24 ?pm -0400 2014/05/31, Doug McIlroy wrote:
>>Does anybody
>>remember who published that deep new insight and/or where?
>
> Probably this:
> B.P. Miller, L. Fredriksen, So, B. "An Empirical Study of the Reliability
> of UNIX Utilities", Communications of the ACM 33, 12 (December 1990)
>
>
> --
> Kevin Schoedel <schoedel at kw.igs.net> VA3TCS
> _______________________________________________
> TUHS mailing list
> TUHS at minnie.tuhs.org
> https://minnie.tuhs.org/mailman/listinfo/tuhs
>

[TUHS] Bugs in V6 'dcheck'

[A. P. Garcia]

On May 31, 2014 6:25 PM, "Doug McIlroy" <doug at cs.dartmouth.edu> wrote:
>
> > 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

yeah, that's not really sporting. I've always wondered about something
else, though: 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? Was he a gadfly, or just some kook you decided to
ignore? The fathers of Unix have been strangely silent on this topic for
many years. Maybe nobody's ever asked?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20140601/e6c13cc8/attachment.html>

[TUHS] Bugs in V6 'dcheck'

[Ronald Natalie]

Some UPSTART named RMS in his whole odipherous spledor couldn't even spell LINUX.     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.   Despite his disingenous propaganda, he didn't invent LINUX (or any other UNIX clone).
RMS didn't even enter onto the UNIX scene until after he had been burned by LMI/Symbolics/MIT over contributions he made to the Lisp Machine that he assumed would always be freely available.     I was a rather late comer to UNIX, having not started on it until 1977,   RMS wasn't anywhere around until over a decade later.

I was happy that Ken and Dennis and the folks were coming up with the design pattern and not worrying about every single bug in the system.   This was RESEARCH.     Those of us in the direct trenches at the places that got UNIX under the "scrap metal" provisions got to make our own contribution by increasing robustness and performance as well as extended the underlying paradigm.
> yeah, that's not really sporting. I've always wondered about something else, though: 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? Was he a gadfly, or just some kook you decided to ignore? The fathers of Unix have been strangely silent on this topic for many years. Maybe nobody's ever asked?
> 
> _______________________________________________
> TUHS mailing list
> TUHS at minnie.tuhs.org
> https://minnie.tuhs.org/mailman/listinfo/tuhs

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20140601/c8486838/attachment.html>

[TUHS] Bugs in V6 'dcheck'

[A. P. Garcia]

On Jun 1, 2014 8:11 PM, "Ronald Natalie" <ron at ronnatalie.com> wrote:
>
> Some UPSTART named RMS in his whole odipherous spledor couldn't even
spell LINUX.

This I've always found ironic, that he's sore because people call the os
linux and don't give gnu credit, when gnu itself was simply a unix ripoff.

Trying to empathize with the creators of unix, I think I would've felt like
someone was stealing things I'd worked hard to produce. But I don't know.
Like you said, he wrote manifestos and rants, so I might just as well have
dismissed him as a nut. You could also take the magnanimous view that he
was actually helping spread your ideas, albeit while putting his own
political spin on things. I'm sorry, I wasn't trying to troll or start a
flame war. RMS is something of an enigma to me.

<snip>

> RMS didn't even enter onto the UNIX scene until after he had been burned
by LMI/Symbolics/MIT over contributions he made to the Lisp Machine that he
assumed would always be freely available.     I was a rather late comer to
UNIX, having not started on it until 1977,   RMS wasn't anywhere around
until over a decade later.

I think he likes to throw 1984 around as the year he wrote the 'gnu
manifesto'.

> I was happy that Ken and Dennis and the folks were coming up with the
design pattern and not worrying about every single bug in the system.
This was RESEARCH.     Those of us in the direct trenches at the places
that got UNIX under the "scrap metal" provisions got to make our own
contribution by increasing robustness and performance as well as extended
the underlying paradigm.

And it's a beautiful design that has adapted remarkably well to new
technologies for decades.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20140601/cd1648ae/attachment.html>

[TUHS] Bugs in V6 'dcheck'

[Nelson H. F. Beebe]

Doug McIlroy <doug at cs.dartmouth.edu> wrote on Sat, 31 May 2014
19:24:57 -0400:

>> ...
>> 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?
>> ...

I suspect that two relevant papers that Doug is recalling are these (I
routinely use their fuzz-test code on my own software):

@String{j-CACM                  = "Communications of the ACM"}

@Article{Miller:1990:ESR,
  author =       "Barton P. Miller and Lars Fredriksen and Bryan So",
  title =        "An empirical study of the reliability of {UNIX}
                 utilities",
  journal =      j-CACM,
  volume =       "33",
  number =       "12",
  pages =        "32--44",
  month =        dec,
  year =         "1990",
  CODEN =        "CACMA2",
  ISSN =         "0001-0782 (print), 1557-7317 (electronic)",
  ISSN-L =       "0001-0782",
  bibdate =      "Wed Sep 25 09:24:48 2002",
  bibsource =    "ftp://ftp.ira.uka.de/pub/bibliography/Misc/IMMD_IV.bib;
                 http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/cacm1990.bib",
  note =         "This is a fascinating paper on what happens when
                 random input streams are fed into important UNIX
                 utilities on several commercial UNIX systems. In some
                 cases, the tests were able to crash the entire
                 operating system. In 1995, a (sadly, unpublished)
                 followup study showed that many of the failures
                 diagnosed in 1990 still had not been repaired in the
                 commercial systems, and that the GNU implementations
                 were generally more robust. Both 1990 and 1995 papers,
                 and the fuzz-generating software, are available at the
                 authors' FTP site at
                 \path|ftp://grilled.cs.wisc.edu/technical_papers/fuzz.ps|
                 and
                 \path|ftp://grilled.cs.wisc.edu/technical_papers/fuzz-revisited.ps|.",
  URL =          "ftp://grilled.cs.wisc.edu/technical_papers/fuzz-revisited.ps;
                 ftp://grilled.cs.wisc.edu/technical_papers/fuzz.ps;
                 http://www.acm.org/pubs/toc/Abstracts/0001-0782/96279.html",
  acknowledgement = ack-nhfb,
  journal-URL =  "http://portal.acm.org/browse_dl.cfm?idx=J79",
  keywords =     "design; reliability; security",
  note2 =        "[25-Sep-2002]: The fuzz software archive has been
                 moved to
                 \path|ftp://ftp.cs.wisc.edu/pub/paradyn/fuzz/|, and the
                 technical reports to
                 \path|ftp://ftp.cs.wisc.edu/pub/paradyn/technical_papers/fuzz*|.",
  subject =      "{\bf D.4.5}: Software, OPERATING SYSTEMS, Reliability.
                 {\bf D.4.0}: Software, OPERATING SYSTEMS, General,
                 UNIX. {\bf D.4.9}: Software, OPERATING SYSTEMS, Systems
                 Programs and Utilities. {\bf D.2.5}: Software, SOFTWARE
                 ENGINEERING, Testing and Debugging.",
}

@String{j-OPER-SYS-REV          = "Operating Systems Review"}

@Article{Miller:2007:ESR,
  author =       "Barton P. Miller and Gregory Cooksey and Fredrick
                 Moore",
  title =        "An empirical study of the robustness of {MacOS}
                 applications using random testing",
  journal =      j-OPER-SYS-REV,
  volume =       "41",
  number =       "1",
  pages =        "78--86",
  month =        jan,
  year =         "2007",
  CODEN =        "OSRED8",
  DOI =          "http://doi.acm.org/10.1145/1228291.1228308",
  ISSN =         "0163-5980 (print), 1943-586X (electronic)",
  ISSN-L =       "0163-5980",
  bibdate =      "Fri Jun 20 17:15:27 MDT 2008",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/opersysrev.bib",
  abstract =     "We report on the fourth in a series of studies on the
                 reliability of application programs in the face of
                 random input. Over the previous 15 years, we have
                 studied the reliability of UNIX command line and
                 X-Window based (GUI) applications and Windows
                 applications. In this study, we apply our fuzz testing
                 techniques to applications running on the Mac OS X
                 operating system. We continue to use a simple, or even
                 simplistic technique: unstructured black-box random
                 testing, considering a failure to be a crash or hang.
                 As in the previous three studies, the technique is
                 crude but seems to be effective in locating bugs in
                 real programs. We tested the reliability of 135
                 command-line UNIX utilities and thirty graphical
                 applications on Mac OS X by feeding random input to
                 each. We report on application failures --- crashes
                 (dumps core) or hangs (loops indefinitely) --- and, where
                 source code is available, we identify the causes of
                 these failures and categorize them. Our testing crashed
                 only 7\% of the command-line utilities, a considerably
                 lower rate of failure than observed in almost all cases
                 of previous studies. We found the GUI-based
                 applications to be less reliable: of the thirty that we
                 tested, only eight did not crash or hang. Twenty others
                 crashed, and two hung. These GUI results were
                 noticeably worse than either of the previous Windows
                 (Win32) or UNIX (X-Windows) studies.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM SIGOPS Operating Systems Review",
  journal-URL =  "http://portal.acm.org/browse_dl.cfm?idx=J597",
  keywords =     "fuzz; random testing",
}

-------------------------------------------------------------------------------
- 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 at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------

[TUHS] Bugs in V6 'dcheck'

[Nelson H. F. Beebe]

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 at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------

[TUHS] Bugs in V6 'dcheck'

[emanuel stiebler]

On 2014-06-02 05:34, Noel Chiappa wrote:

> 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!

IIRC, we had a list of people somewhere on TUHS/PUPS, which still can 
read & write tapes. We had this service for people, who couldn't pull 
the whole archive through the net, so we send out tapes ...

Cheers

P.S. Sorry, can't find a link for it at the moment

[TUHS] Bugs in V6 'dcheck'

[arnold]

>     > "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.

IIRC it's reproduced in Knuth's book "Literate programming" which is
well worth ownding and reading. A soft copy might actually come with
TeX itself.

Arnold

[TUHS] Bugs in V6 'dcheck'

[Mary Ann Horton]

I would also love to find a way to read 9 track tapes back in. Everyone 
has ditched the hardware.   I have several 4BSD and System V tapes as 
well as personal tapes I'd love to read in.  (Anyone remember IBM 
"picture tapes"?)

On 06/01/2014 08:34 PM, Noel Chiappa wrote:
>      > From: norman at 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 at 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 at 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
> _______________________________________________
> TUHS mailing list
> TUHS at minnie.tuhs.org
> https://minnie.tuhs.org/mailman/listinfo/tuhs

[TUHS] Bugs in V6 'dcheck'

[Noel Chiappa]

    > From: norman at 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 at 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 at 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

[TUHS] Bugs in V6 'dcheck'

[Noel Chiappa]

    > From: "Ron Natalie" <ron at 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 at 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

[TUHS] Bugs in V6 'dcheck'

[John Cowan]

Michael Spacefalcon scripsit:

> 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?  

The record is quite clear on that.  How the 50 fixes tape got out of Bell
Labs may not be as puzzling as the song the Sirens sang or who blew up
Mallow Bridge, but likewise the question is not beyond all conjecture.
Ken wanted those diffs out there, the more so because they didn't all
come from inside the Labs.

See the seventh page of
<http://cla.calpoly.edu/~lcall/354/kelty_two_bits_ch4.pdf> for details.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
'Tis the Linux rebellion / Let coders take their place,
The Linux-nationale / Shall Microsoft outpace,
We can write better programs / Our CPUs won't stall,
So raise the penguin banner of / The Linux-nationale.  --Greg Baker

[TUHS] Bugs in V6 'dcheck'

[Michael Spacefalcon]

A. P. Garcia <a.phillip.garcia at 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 at 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

[TUHS] Bugs in V6 'dcheck'

[Clem Cole]

btw.  there is a v6 version of fsck floating around.  CMU was still running v6 when Ted did his OYOC.  he later moved it to unix/TS (aka v7) which was the release mechanics out side of BTL.   I'm wonder if I can find a readable copy. 


funny I remember the first time fsck saved our butts     we had had power failure and corrupted two file systems on the EE dept 11/34 I was running Icheck/dcheck and the like trying patch the system and getting it running a gaining.  this new grad student (tjk) says he has something he wanted to try that he wrote over the summer /he had started writing at michiga.     the machine was dead Ted had it on a tape and getting it on to an rk05 was a trick  - we ended up doing it on the IUS system in CS.  

once it was running we were in awe   man that program migrated to all the CMU pdp11s within hours

Clem
> On May 31, 2014, at 9:15 AM, jnc at mercury.lcs.mit.edu (Noel Chiappa) wrote:
> 
> 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
> _______________________________________________
> TUHS mailing list
> TUHS at minnie.tuhs.org
> https://minnie.tuhs.org/mailman/listinfo/tuhs

[TUHS] Bugs in V6 'dcheck'

[Tim Newsham]

There are bugs to be found, and it can be a fun hunt
(though not too much of a challenge).  Here are some
more (security related, as thats my inclination):

  http://marc.info/?l=bugtraq&m=108627540130457&w=2
  http://minnie.tuhs.org/pipermail/unix-jun72/2008-May/000126.html
  http://minnie.tuhs.org/pipermail/unix-jun72/2008-May/000250.html

Tim


On Sat, May 31, 2014 at 3:15 AM, Noel Chiappa <jnc at mercury.lcs.mit.edu> wrote:
> 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
> _______________________________________________
> TUHS mailing list
> TUHS at minnie.tuhs.org
> https://minnie.tuhs.org/mailman/listinfo/tuhs



-- 
Tim Newsham | www.thenewsh.com/~newsham | @newshtwit | thenewsh.blogspot.com

[TUHS] Bugs in V6 'dcheck'

[John Cowan]

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 at 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

[TUHS] Bugs in V6 'dcheck'

[Ron Natalie]

>   OK, so I was wrong! 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.


> '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.

Yes, and in the version 7 version of icheck
(http://www.tuhs.org/Archive/PDP-11/Trees/V7/usr/src/cmd/dcheck.c) they
appear to have fixed it.
It is set to zero before both the pass1 and pass2 loops.

I'm pretty sure whoever added the feature to check more than one file system
at a time didn't test it very well in V6.   

[TUHS] Bugs in V6 'dcheck'

[John Cowan]

Norman Wilson scripsit:

> (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.)

I agree that "The Errors of TeX" was an excellent article.  Mr. Pike is
well-known to be, mmmm, easily bored.  On the other hand, his sense of
humor isn't to everyone's taste, either.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
Even the best of friends cannot attend each others' funeral.
        --Kehlog Albran, The Profit

[TUHS] Bugs in V6 'dcheck'

[Noel Chiappa]

    > From: jnc at 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

[TUHS] Bugs in V6 'dcheck'

[Noel Chiappa]

    > From: Ronald Natalie <ron at 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 at 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

[TUHS] Bugs in V6 'dcheck'

[Norman Wilson]

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

[TUHS] Bugs in V6 'dcheck'

[Ronald Natalie]

If I understand what you are saying, it only occurs when you run dcheck with mutliple volumes at one time?
I can't say I EVER did that back in the pre-fsck days.

We did icheck and then dcheck on each disk in sequence.
I don't even think we had a shell script.    It was incumbent on the operator to check each of the system disks and any user volumes that were mounted at the time the system crash.

Bugs are entirely not uncommon.     This is why BSD and JHU and UT had their own distributions.       Having been a V6 UNIX systems programmer at a university back in the day as we had students who found it an extracurricular activity (nobody took computing seriously back then) to break security or just plain crash the system.    Tons of worse bugs than dcheck issues.    

I actually spent some time before they elevated me to system programmer doing some exploration in to problems (authorized by the staff).
I decided to test all the setuid programs against vulnerabilities of playing with the file descriptors before invoking them.      I found a half a dozen problems and mailed of the details before I decided to give up and go home.    The next morning our log had a message about the first eight characters of the system accounting file being corrupted.   I told the guys recovering from that that I might know how that had happened.    They said they figured I would because it was my user  name that was found overwritten on the file.

[TUHS] Bugs in V6 'dcheck'

[Noel Chiappa]

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