Software Reliability via Run-Time result Checking

Manuel Blum, Hal Wasserman
International Computer Science Institute
Berkeley, CA
http://citeseer.nj.nec.com/59449.html

Assuring software reliability

For certain computations, the running time of the computation is considered bigger than the time to verify the results.

Simple checkers

Let f be a function with running time greater than T(n). A simple checker for f is an algorithm with I/O specifications:

Self-correctors

A self-corrector for f is an algorithm with I/O specifications:

Debugging via checkers

Concerns:

Checks