[TUHS] Bugs in V6 'dcheck'

[beebe@math.utah.edu (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/ -
-------------------------------------------------------------------------------