"Shadow Guarding: Run-Time Checking You Can Afford" -- Technical Report

@TECHREPORT{SHADOW_GUARDING, TITLE = "Shadow {G}uarding: {R}un-time
Checking You Can Afford", AUTHOR = "Harish Patil and Charles Fischer",
INSTITUTION = "Computer Sciences department, University of Wisconsin",
YEAR = 1994, MONTH = "November", TYPE = "{TR} 1254", ADDRESS = "Madison,
Wisconsin", } ABSTRACT ======== With shared memory multiprocessors
becoming increasingly common, run-time checking techniques that exploit
multiple processors become attractive. Shadow guarding is a technique
that uses shared memory multiprocessors to check the validity of array and
pointer accesses. Current approaches to pointer access checking work
sequentially, typically slowing a computation 3-4 times. Such high
overheads make those approaches unsuitable for use with heavily-used
programs. After programs are fully developed and tested, running them with
embedded checks seems unacceptably slow. Most programmers turn off the
checks; trading reliability for speed. Shadow guarding offers an excellent
way out -- a shadow process works silently in the background watching for
run-time errors. Computations in the user program are performed by a main
process. Error-free runs of the main process are only slightly slower than
the original. Occasional erroneous runs lead to an elaborate, sometimes
delayed, error report from the shadow process. If the original program
crashes, an error report from the shadow points to the root cause of the
crash. Reports on errors which do not crash the original program can be
extremely helpful in correcting the program.


We have developed a prototype shadow guarding system which supports
full-size programs written in C. Our system instruments an executable user
program in C to obtain a "main process" and a "shadow process." The main
process performs computations from the original program, occasionally
communicating a few key values to the shadow process. The shadow process
follows the main process and performs run-time checking. The overhead to
the main process is very low -- almost always less than 10%. Further,
since the shadow process avoids repeating some of the computations from
the input program, it runs up to two times faster than a single process
performing both the computation and checking. Sometimes the shadow process
can even run ahead of the main process catching errors before they
actually occur. Our system has found a number of errors (15 so far) in
widely-used Unix utilities and SPEC92 benchmarks. We believe our approach
shows great potential in improving the quality and reliability of
application programs at a very modest cost.


===========================================================================
Instructions for Anonymous FTP of technical reports:


        1. Ftp to the host "ftp.cs.wisc.edu" using your ftp program.


        2. Use "anonymous" as the user name.


        3. At the password prompt, send your email address (email@host).


        4. cd /tech-reports


        5. Retrieve the file README for more instructions (typically with
              the "get" command)


        6. Reports are all under /tech-reports/reports/YY, where YY is the
              year.


              Reports are stored as compressed PostScript files, named trXXX.ps.Z,
              where XXX is the report number. If you can uncompress the files on
              your computer, use file type "binary" or "image" and fetch the report
              you want (how to do this depends on your ftp client software).


              If you cannot uncompress the report, the ftp server can do it for
              you before transmission of the file: leave off the ".Z" from the
              file name when giving the retrieve command.


        Files in /tech-reports you may want to look at:


README information about the archive
ALL_ABSTRACTS contains abstracts of all tech reports since Dec 1987.
ORDER_FORM for ordering tech reports not available via ftp.
OnLineList a list of all tech reports available for ftp
REPORT_LIST report numbers, titles, authors and publication
date for each report.


        If you have problems with the multi-line messages from the ftp server,
        connect again and try using a dash (-) as the first character of your
        password.


        If you have any problems with the ftp archive, please send electronic
        mail to "ftp@cs.wisc.edu".


Instructions for accessing technical reports via gopher:


        1. Connect to the gopher server on ftp.cs.wisc.edu. Choose the menu item
              "University of Wisconsin-Madison Computer Sciences Department"


        2. Choose the menu item "CS Technical Reports"


        3. Choose the appropriate menu items.


Instructions for accessing technical reports via afs:


        1. cd to /afs/cs.wisc.edu/public/tech-reports.


        2. look at the file README for more information.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.