A Mathematical Theory of Self-Checking, Self-Testing and Self-Correcting Programs (Thesis)

TitleA Mathematical Theory of Self-Checking, Self-Testing and Self-Correcting Programs (Thesis)
Publication TypeTechnical Report
Year of Publication1990
AuthorsRubinfeld, R.
Other Numbers618

Suppose someone gives us an extremely fast program P that we can call as a black box to compute a function f. Rather than trust that p works correctly, a self-testing/correcting pair for f allows us to: (1) estimate the probability that P(x) is not equal to f(x) when x is randomly chosen; (2) on any input x, compute f(x) correctly as long as P is not too faulty on average. Furthermore, both (1) and (2) require only a small multiplicative overhead (usually constant) over the running time of P. A program result checker for f (as introduced by Manuel Blum) allows us to check that on particular input x, P(x) = f(x).We present general techniques for constructing simple to program self-testing/correcting pairs for a variety of numerical functions. The self-testing/correcting pairs introduced for many of the problems are based on the property that the solution to a particular instance of the problem can be expressed as the solution to a few random instances of the same size. An important idea is to design self-testing/correcting pairs for an entire library of functions rather than for each function individually.We extend these notions and some of the general techniques to check programs for some specific functions which are only intended to give good approximations to f(x). We extend the above models and techniques of program result checking and self-testing/correcting to the case where the behavior of the program is modeled as being adaptive, i.e., the program may not always give the same answer on a particular input. These stronger checkers provide multi-prover interactive proofs for these problems.The theory of checking is also extended to parallel programs [Rubinfeld]. We construct parallel checkers for many basic problems in parallel computation.We show that for some problems, result checkers that are much more efficient can be constructed if the answers are checked in batches, i.e., many answers are checked at the same time. For these problems, the multiplicative overhead of checking the result can be made arbitrarily small.

Bibliographic Notes

ICSI Technical Report TR-90-054

Abbreviated Authors

R. Rubinfeld

ICSI Publication Type

Technical Report