M. Blum
S. Kanna
ABSTRACT
A program correctness checker is an algorithm for checking the output of a computation. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class P of problems solvable in polynomial time. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Finally it characterizes the problems that can be checked.
- A.D. Angluin, "Lecture Notes on the Complexity of Some Problems in Number Tl~eory," Yale Technical Report #243 (1982).Google Scholar
- B1.R. Beigel, personal communication.Google Scholar
- B2.M. Blum, "Designing Programs to Check Their Work", submitted for publication in CACM.Google Scholar
- BA.T.A. Budd and D. Angluin, "Two Notions of Correcmess and Their Relation to Testing," Acta Informaflea, v. 18, 31-45 (1982).Google ScholarDigital Library
- BCG.E.R. Berlekamp, J.H. Conway, and R.K. Guy, "Winning Ways," Academic Press, (1982).Google Scholar
- BR.M. Blum and P. Raghavan, "Program Correctness: Can One Test for It?," IBM T.J. Watson Research Center Technical Report (1988).Google Scholar
- CFGMW.L. Carter, R. Floyd, J. Gill, G. Markowsky & M. Wegman, "Exact and Approximate Membership Testers" 10th ACM Symposium on Theory of Computing, 59-65 (t978). Google ScholarDigital Library
- F.R. Freivalds, "Fast Probabilistic Algorithms," Springer Vefiag Lecture Notes in CS #74, Mathematical Foundations of CS, 57-69 (1979).Google Scholar
- FHL.M. Furst, J.E. Hopcroft, E. Luks, "Polynomial-Time Algorithms for Permutation Groups," Proc. 21st IEEE Symposium on Foundations of Computer Science, 36-41 (1980).Google Scholar
- GJ.M.R. Garey and D.S. johnson, "Computers and Intractability," Freeman, San Francisco, CA (1979).Google Scholar
- GMR.S. Goldwasser, S. Micali, and C. Rackoff, "The Knowledge Complexity of Interactive Proof Systems,'' 17th ACM Symposium on Theory of Computing, 291-304 (1985). Google ScholarDigital Library
- GMW.O. Goldreich, S. Micali and A. Wigderson, "Proofs that Yield Nothing but their Validity and a Methodology of Cryptographic Design," Proc. 27th IEEE Symposium on Foundations of Computer Science, 174-187 (1986).Google Scholar
- GS.S. Goldwasser and M. Sipser, "Private Coins versus Public Coins in interactive Proof Systems," l gth ACM Symposium on Theory of Computing, 59-68 (1986). Google ScholarDigital Library
- H.C.M. Hoffmann, "Group-Theoretic Algorithms and Graph Isomorphism,'' V. 136 of the series "Lecture Notes in Computer Science," ed. by G. Goos and J. Hartmanis, Springer-Verlag, 311 pp. (1982).Google Scholar
- K1.R. Kannan, personal communication through S. Rudich.Google Scholar
- K2.S. Kannan, Ph.D. thesis to be submitred to the Computer Science Division of the University of Califomia at Berkeley.Google Scholar
- KR.R.M. Karp and M.O. Rabin, "Efficient randomized pattern matching algorithms", IBM Journal of Research and Development, 3 ! (2), 249-260. Google ScholarDigital Library
- L1.J. Leech, "Computer Proof of Relations in Groups," in "Topics in Group Theory and Computation," edited by M.P.J. Curran, Academic Press, 38-61 (1977).Google Scholar
- L2.J.S. Leon, "Computing Automorphism Groups of Combinatorial Objects," in "Computational Group Theory," edited by M.D. Atkinson, Academic Press, 321-335 (1984).Google Scholar
- L3.R. Lipton, personal communication.Google Scholar
- PR.G. Polya and R.C. Read, "Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds,'' Springer-Verlag (1987). Google ScholarDigital Library
- R.M.O. Rabin, "Probabilistic Algorithms,'' in "Algorithms and Complexity, Recent Results and New Directions," edited by J.F. Traub, Academic Press, 21-40 (1976).Google Scholar
- TW.M. Tompa and H. Woll, "Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information," Proc. 28th IEEE Symposium on Foundations of Computer Science, 472-482 (1987).Google Scholar
- W.W.j. Weyuker, "The Evaluation of Program-Based Software Test Data Adequacy Criteria," Communications of the ACM, v. 31, no. 6, 668- 675 (1988). Google ScholarDigital Library
- WC.M.N. Wegman and J.L. Caner, "New Hash Functions and Their Use in Authentication and Set Equality," J. of Computer and System Science, v. 22, no. 3, 265-279 (1981).Google Scholar
Index Terms
- Designing programs that check their work
Recommendations
Designing programs that check their work
A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that instance is correct. This paper ...
Designing programs to check their work (abstract)
Designing Programs to Check Their Work Professor Manuel Blurn Department of EECS UC Berkeley and International Computer Science Institute Berkeley, California Abstract Students, engineers, programmers... are all expected to check their work. Computer ...
Designing programs to check their work (abstract)
ISSTA '93: Proceedings of the 1993 ACM SIGSOFT international symposium on Software testing and analysisDesigning Programs to Check Their Work Professor Manuel Blurn Department of EECS UC Berkeley and International Computer Science Institute Berkeley, California Abstract Students, engineers, programmers... are all expected to check their work. Computer ...
Comments