Checking
The study of program checkers, self-testing programs,
and self-correcting programs is a new approach to ensuring the correctness of program
results. The key idea is to allow one to use a program to compute a function without
having to trust a priori that it works correctly. This is accomplished by having a checker
determine whether the program gives the correct answer on a particular input.
Our work introduced two new concepts that are useful to the development of such checkers:
A self-tester determines whether a program is correct on most inputs, and a self-corrector
takes a program that is correct on most inputs and uses it to construct a new program that
is correct on every input with high probability. Program checking is particularly
interesting for problems that are easy to specify but for which efficient programs may be
very complicated. The goal of our research is to characterize which functions have fast
and simple checkers. We are conducting a number of investigations of checkers for a
variety of problems, including problems from algebra, graph theory, and computational
geometry. One particularly fruitful line of research concerns self-testers and
self-correctors based on properties satisfied by the function; for example, the function
f(x)=x is uniquely specified by the properties:
(1) for all x,y, f(x)+f(y)=f(x+y)
(2) for all x, f(x)+1=f(x+1).
We used these properties to construct self-testers and self-correctors for several classes
of functions, including linear functions, many trigonometric functions, and low degree
polynomial functions. We have recently shown that our results apply to the setting of
real-valued computation, where the output of the program is approximate instead of exact.
Our results borrow techniques from and have implications to the stability theory of
functional equations.
Recent papers:
1. Funda Ergun, S. Ravi Kumar, Ronitt Rubinfeld, ``Approximate Checking of
Polynomials and Functional Equations'', In Proc. 37th IEEE Conference on Foundations of
Computer Science, 1996.
2. Ronitt Rubinfeld, ``Robust Functional Equations and their Applications to Program
Testing.'' Preliminary version in Proc. 35th IEEE Conference on Foundations of Computer
Science, 1994.
3. Ronitt Rubinfeld, Madhu Sudan, ``Robust Characterizations of Polynomials and
their Applications to Program Testing.'' In SIAM J. of Computing, April 1996.
4. Ronitt Rubinfeld. ``Designing Checkers for Programs that Run in Parallel.'' In
Algorithmica, April 1996.
5. Blum, M., Luby, M., Rubinfeld, R., ``Self-Testing/Correcting with Applications to
Numerical Problems,'' In J. Comp. Sys. Sci. Vol. 47, No. 3, December 1993 (special issue
on STOC 1990). Preliminary abstract appears in Proc. 22th ACM Symposium on Theory of
Computing, 1990.
6. Rubinfeld, R., ``A Mathematical Theory of Self-Checking, Self-Testing and
Self-Correcting Programs'' , PhD Thesis, U.C. Berkeley, August 1990. ICSI Technical Report
No. TR-90-054. |
