{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T05:21:42Z","timestamp":1670390502386},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1997,11]]},"abstract":"We review the field of result-checking, discussing simple checkers and self-correctors. We argue that such checkers could profitably be incorporated in software as an aid to efficient debugging and enhanced reliability. We consider how to modify traditional checking methodologies to make them more appropriate for use in real-time, real-number computer systems. In particular, we suggest that checkers should be allowed to use stored randomness: that is, that they should be allowed to generate, preprocess, and store random bits prior to run-time, and then to use this information repeatedly in a series of run-time checks. In a case study of checking a general real-number linear transformation (e.g., a Fourier Transform), we present a simple checker which uses stored randomness, and a self-corrector which is particularly efficient if stored randomness is employed.<\/jats:p>","DOI":"10.1145\/268999.269003","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"826-849","source":"Crossref","is-referenced-by-count":107,"title":["Software reliability via run-time result-checking"],"prefix":"10.1145","volume":"44","author":[{"given":"Hal","family":"Wasserman","sequence":"first","affiliation":[{"name":"Univ. of California, Berkeley"}]},{"given":"Manuel","family":"Blum","sequence":"additional","affiliation":[{"name":"City Univ. of Hong Kong, Kowloon, Hong Kong; and Univ. of California, Berkeley"}]}],"member":"320","published-online":{"date-parts":[[1997,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"The Probabilistic Method","author":"ALON N.","unstructured":"ALON , N. , SPENCER , J. , AND ERD 6 S, P . 1992. The Probabilistic Method . Wiley , New York . ALON, N., SPENCER, J., AND ERD6S, P. 1992. The Probabilistic Method. Wiley, New York."},{"key":"e_1_2_1_2_1","first-page":"786","volume-title":"Proceedings of the 25th Annual ACM Symposium on the Theory of Computing","author":"AR S.","year":"1993","unstructured":"AR , S. , BLUM , M. , CODENOTTI , B. , AND GEMMELL , P. 1993 . Checking approximate computations over the reals . In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing ( San Diego, Calif., May 16-18). ACM, New York , pp. 786 - 795 . 10.1145\/167088.167288 AR, S., BLUM, M., CODENOTTI, B., AND GEMMELL, P. 1993. Checking approximate computations over the reals. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 786-795. 10.1145\/167088.167288"},{"key":"e_1_2_1_3_1","first-page":"2","volume-title":"Proceedings of the 33rd Annual IEEE Symposium of Foundations of Computer Science. IEEE","author":"ARORA S.","year":"1992","unstructured":"ARORA , S. , AND SAFRA , S. 1992 . Probabilistic checking of proofs; a new characterization of NP . In Proceedings of the 33rd Annual IEEE Symposium of Foundations of Computer Science. IEEE , New York , pp. 2 - 13 . ARORA, S., AND SAFRA, S. 1992. Probabilistic checking of proofs; a new characterization of NP. In Proceedings of the 33rd Annual IEEE Symposium of Foundations of Computer Science. IEEE, New York, pp. 2-13."},{"issue":"1","key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","article-title":"Non-deterministic exponential time has two-prover interactive protocols","volume":"1","author":"BABAI L.","year":"1991","unstructured":"BABAI , L. , FORTNOW , L. , AND LUND , C. 1991 . Non-deterministic exponential time has two-prover interactive protocols . Comput. Comp. 1 , 1 , 3 - 40 . BABAI, L., FORTNOW, L., AND LUND, C. 1991. Non-deterministic exponential time has two-prover interactive protocols. Comput. Comp. 1, 1, 3-40.","journal-title":"Comput. Comp."},{"issue":"1","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01200057","article-title":"Arithmetization: a new method in structural complexity theory","volume":"1","author":"BABAI L.","year":"1991","unstructured":"BABAI , L. , AND FORTNOW , L. 1991 . Arithmetization: a new method in structural complexity theory . Comput. Comp. 1 , 1 , 41 - 46 . BABAI, L., AND FORTNOW, L. 1991. Arithmetization: a new method in structural complexity theory. Comput. Comp. 1, 1, 41-46.","journal-title":"Comput. Comp."},{"key":"e_1_2_1_6_1","first-page":"21","volume-title":"Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM","author":"BABAI L.","year":"1991","unstructured":"BABAI , L. , FORTNOW , L. , LEVIN , L. , AND SZEGEDY , M. 1991 . Checking computations in polylogarithmic time . In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM , New York , pp. 21 - 31 . 10.1145\/103418.103428 BABAI, L., FORTNOW, L., LEVIN, L., AND SZEGEDY, M. 1991. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 21-31. 10.1145\/103418.103428"},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Computer Science","first-page":"37","volume-title":"Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science","author":"BEAVER D.","unstructured":"BEAVER , D. , AND FEIGENBAUM , J. 1990. Hiding instances in multioracle queries . In Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science . Lecture Notes in Computer Science , vol. 415 , Springer-Verlag , New York , pp. 37 - 48 . BEAVER, D., AND FEIGENBAUM, J. 1990. Hiding instances in multioracle queries. In Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 415, Springer-Verlag, New York, pp. 37-48."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01276436"},{"key":"e_1_2_1_9_1","volume-title":"Programming Pearls","author":"BENTLEY J.","unstructured":"BENTLEY , J. 1986. Programming Pearls . Addison-Wesley, Reading , Mass . BENTLEY, J. 1986. Programming Pearls. Addison-Wesley, Reading, Mass."},{"key":"e_1_2_1_10_1","volume-title":"Designing programs to check their work","author":"BLUM M.","unstructured":"BLUM , M. 1988. Designing programs to check their work . International Computer Science Institute Tech . Report TR-88-009. BLUM, M. 1988. Designing programs to check their work. International Computer Science Institute Tech. Report TR-88-009."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01185212","article-title":"Checking the correctness of memories","volume":"12","author":"BLUM M.","year":"1994","unstructured":"BLUM , M. , EVANS , W. , GEMMELL , P. , KANNAN , S. , AND NAOR , M. 1994 . Checking the correctness of memories . Algorithmica 12 , 2 - 3 , 225-244. BLUM, M., EVANS, W., GEMMELL, P., KANNAN, S., AND NAOR, M. 1994. Checking the correctness of memories. Algorithmica 12, 2-3, 225-244.","journal-title":"Algorithmica"},{"key":"e_1_2_1_12_1","first-page":"86","volume-title":"Proceedings of the 21st Annual ACM Symposium on the Theory of Computing","author":"BLUM M.","year":"1989","unstructured":"BLUM , M. , AND KANNAN , S. 1989 . Designing programs that check their work . In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing ( Seattle, Wash., May 15-17). ACM, New York , pp. 86 - 97 . 10.1145\/73007.73015 BLUM, M., AND KANNAN, S. 1989. Designing programs that check their work. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, pp. 86-97. 10.1145\/73007.73015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.494097"},{"key":"e_1_2_1_15_1","volume-title":"Test Facility Working Group Conf.","author":"BOETT HER","year":"1995","unstructured":"BOETT c HER , C., AND MELLEMA , D.J. 1995 . Program checkers: Practical applications to real-time software . Test Facility Working Group Conf. BOETTcHER, C., AND MELLEMA, D.J. 1995. Program checkers: Practical applications to real-time software. Test Facility Working Group Conf."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.210303"},{"key":"e_1_2_1_17_1","first-page":"90","article-title":"A note on self-testing\/correcting methods for trigonometric functions","author":"CLEVE R.","year":"1990","unstructured":"CLEVE , R. , AND LUBY , M. 1990 . A note on self-testing\/correcting methods for trigonometric functions . International Computer Science Institute Tech. Report 90 - 032 . CLEVE, R., AND LUBY, M. 1990. A note on self-testing\/correcting methods for trigonometric functions. International Computer Science Institute Tech. Report 90-032.","journal-title":"International Computer Science Institute Tech. Report"},{"key":"e_1_2_1_18_1","first-page":"407","volume-title":"Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-Jun. 1). ACM","author":"ERGON F.","year":"1995","unstructured":"ERGON , F. 1995 . Testing multivariate linear functions: Overcoming the generator bottleneck . In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-Jun. 1). ACM , New York , pp. 407 - 416 . 10.1145\/225058.225167 ERGON, F. 1995. Testing multivariate linear functions: Overcoming the generator bottleneck. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-Jun. 1). ACM, New York, pp. 407-416. 10.1145\/225058.225167"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90199-8"},{"key":"e_1_2_1_20_1","series-title":"Lecture Notes in Computer Science","first-page":"57","volume-title":"Mathematical Foundations of Computer Science","author":"FREIVALDS R.","unstructured":"FREIVALDS , R. 1979. Fast probabilistic algorithms . In Mathematical Foundations of Computer Science . Lecture Notes in Computer Science , vol. 74 . Springer-Verlag , New York , pp. 57 - 69 . FREIVALDS, R. 1979. Fast probabilistic algorithms. In Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 74. Springer-Verlag, New York, pp. 57-69."},{"key":"e_1_2_1_21_1","first-page":"32","volume-title":"Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM","author":"GEMMELL P.","year":"1991","unstructured":"GEMMELL , P. , LIPTON , R. , RUBINFELD , R. , SUDAN , M. , AND WIGDERSON , A. 1991 . Self-testing\/ correcting for polynomials and for approximate functions . In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM , New York , pp. 32 - 42 . 10.1145\/103418.103429 GEMMELL, P., LIPTON, R., RUBINFELD, R., SUDAN, M., AND WIGDERSON, A. 1991. Self-testing\/ correcting for polynomials and for approximate functions. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 32-42. 10.1145\/103418.103429"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"e_1_2_1_23_1","first-page":"174","volume-title":"Proceedings of the 27th Annual IEEE Symposium on Foundation of Computer Science. IEEE","author":"GOLDREICH O.","year":"1986","unstructured":"GOLDREICH , O. , MICALI , S. , AND WIGDERSON , A. 1986 . Proofs that yield nothing but their validity and a methodology of cryptographic protocol design . In Proceedings of the 27th Annual IEEE Symposium on Foundation of Computer Science. IEEE , New York , pp. 174 - 187 . GOLDREICH, O., MICALI, S., AND WIGDERSON, A. 1986. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th Annual IEEE Symposium on Foundation of Computer Science. IEEE, New York, pp. 174-187."},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","first-page":"207","volume-title":"Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science","author":"LIPTON R.","unstructured":"LIPTON , R. 1990. Efficient checking of computations . In Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science . Lecture Notes in Computer Science , vol. 415 . Springer- Verlag , New York , pp. 207 - 215 . LIPTON, R. 1990. Efficient checking of computations. In Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 415. Springer- Verlag, New York, pp. 207-215."},{"key":"e_1_2_1_26_1","first-page":"191","article-title":"New directions in testing, distributed computing and cryptography","volume":"2","author":"LIPTON R.","year":"1991","unstructured":"LIPTON , R. 1991 . New directions in testing, distributed computing and cryptography . DIMACS Series Disc. Math. Theoret. Comput. Sci. 2 , 191 - 202 . LIPTON, R. 1991. New directions in testing, distributed computing and cryptography. DIMACS Series Disc. Math. Theoret. Comput. Sci. 2, 191-202.","journal-title":"DIMACS Series Disc. Math. Theoret. Comput. Sci."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_29_1","unstructured":"NISAN N. 1989. Co-SAT has multi-prover interactive proofs e-mail message. NISAN N. 1989. Co-SAT has multi-prover interactive proofs e-mail message."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-60692-0_53","volume-title":"Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science.","author":"RAVIKUMAR S.","year":"1995","unstructured":"RAVIKUMAR , S. , AND SIVAKUMAR , D. 1995 . On self-testing without the generator bottleneck . In Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science. pp. 248 - 262 . RAVIKUMAR, S., AND SIVAKUMAR, D. 1995. On self-testing without the generator bottleneck. In Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science. pp. 248-262."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90093-B"},{"key":"e_1_2_1_33_1","first-page":"288","volume-title":"Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"RUBINFELD R.","year":"1994","unstructured":"RUBINFELD , R. 1994 . On the robustness of functional equations . In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. IEEE , New York , pp. 288 - 299 . RUBINFELD, R. 1994. On the robustness of functional equations. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 288-299."},{"key":"e_1_2_1_34_1","first-page":"23","volume-title":"Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms. (Orlando, Fla., Jan. 27-29)","author":"RUBINFELD R.","year":"1992","unstructured":"RUBINFELD , R. , AND SUDAN , M. 1992 . Self-testing polynomial functions efficiently and over rational domains . In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms. (Orlando, Fla., Jan. 27-29) . ACM, New York , pp. 23 - 32 . RUBINFELD, R., AND SUDAN, M. 1992. Self-testing polynomial functions efficiently and over rational domains. In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms. (Orlando, Fla., Jan. 27-29). ACM, New York, pp. 23-32."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_37_1","first-page":"11","volume-title":"Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"SHAMIR A.","year":"1990","unstructured":"SHAMIR , A. 1990 . IP = PSPACE . In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science. IEEE , New York , pp. 11 - 15 . SHAMIR, A. 1990. IP = PSPACE. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 11-15."},{"key":"e_1_2_1_38_1","series-title":"Lecture Notes in Computer Science","first-page":"456","volume-title":"Proceedings of the 9th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"VAINSTEIN F.","unstructured":"VAINSTEIN , F. 1991. Error detection and correction in numerical computations by algebraic methods . In Proceedings of the 9th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes . Lecture Notes in Computer Science , vol. 539 . Springer-Verlag , New York , pp. 456 - 464 . VAINSTEIN, F. 1991. Error detection and correction in numerical computations by algebraic methods. In Proceedings of the 9th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Lecture Notes in Computer Science, vol. 539. Springer-Verlag, New York, pp. 456-464."},{"issue":"2","key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","volume":"8","author":"VALIANT L.","year":"1979","unstructured":"VALIANT , L. 1979 . The complexity of computing the permanent . Theoret. Comput. Sci. 8 , 2 , 189 - 201 . VALIANT, L. 1979. The complexity of computing the permanent. Theoret. Comput. Sci. 8, 2, 189-201.","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"e_1_2_1_41_1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","article-title":"New hash functions and their use in authentication and set equality","volume":"22","author":"WEGMAN M.","year":"1981","unstructured":"WEGMAN , M. , AND CARTER , J. 1981 . New hash functions and their use in authentication and set equality . J. Comput. Syst. Sci. 22 , 3 , 265 - 279 . WEGMAN, M., AND CARTER, J. 1981. New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22, 3, 265-279.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_42_1","first-page":"84","volume-title":"Proceedings of the 22nd AnnualACM Symposium on the Theory of Computing","author":"YAO A.","year":"1990","unstructured":"YAO , A. 1990 . Coherent functions and program checkers . In Proceedings of the 22nd AnnualACM Symposium on the Theory of Computing ( Baltimore, Md., May 14-16). ACM, New York , pp. 84 - 94 . 10.1145\/100216.100226 YAO, A. 1990. Coherent functions and program checkers. In Proceedings of the 22nd AnnualACM Symposium on the Theory of Computing (Baltimore, Md., May 14-16). ACM, New York, pp. 84-94. 10.1145\/100216.100226"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/268999.269003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T09:18:51Z","timestamp":1670318331000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/268999.269003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,11]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1997,11]]}},"alternative-id":["10.1145\/268999.269003"],"URL":"http:\/\/dx.doi.org\/10.1145\/268999.269003","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1997,11]]}}}