Software reliability via run-time result-checking资料.pdfVIP

INTERNATIONAL COMPUTER SCIENCE INSTITUTE Center St Suite Berkeley California FAX I Software Reliability via RunTime ResultChecking  Manuel Blum y Hal Wassermanz TR Octob er Abstract We review the eld of resultchecking discussing simple checkers and self correctors We argue that such checkers could protably b e incorp orated in software as an aid to ecient debugging and reliable functionality We consider how to mo dify traditional checking metho dologies to make them more appropriate for use in real time realnumb er computer systems In particular we suggest that checkers should b e allowed to use stored randomness ie that they should b e allowed to generate prepro cess and store random bits prior to runtime and then to use this information rep eatedly in a series of runtime checks In a case study of checking a general realnumb er linear transformation for example a Fourier Transform we present a simple checker which uses stored randomness and a selfcorrector which is particularly ecient if stored randomness is allowed A preliminary version of this pap er app ears as Program resultchecking a theory of testing meets a test of theory Pr oc th IEEE FOCS y Computer Science Division University of California Berkeley CA blumcsb erkeleyedu This work was supp orted in part by NSF grant ccr and in part by a MICRO grant from Hughes Aircraft Corp oration and the State of California z Computer Science Division University of California Berkeley CA halwcsb erkeleyedu Supp orted by NDSEG Fellowship daahg ii Resultchecking an