The invasiveness of off-line memory checking

ABSTRACT

Memory checking is the task of checking the correctness of a sequence of "store" and "retrieve" operations. The operations are performed in a large unreliable memory. A checker using a much smaller but completely reliable memory tries to decide whether they were executed correctly. M. Blum, W. Evans, P. Gemmel, S. Kannan and M. Naor, has shown in 1991 that the off-line checking of a sequence of memory operations concerning a RAM consisting of n registers can be done, in a probabilistic sense, by a checker using only O(log n) reliable memory and a constant number of RAM operation per each "store" and "retrieve" operations (with log n word length), moreover no unproven cryptographic assumptions are needed in the proof. The probability of error will be polynomially small in n. The solution however requires the checker to store some extra information in the unreliable memory, that is, the checking protocol is invasive. (In this solution the time of each "store" operation must be stored together with the data and must be supplied to the checker at the time of the corresponding retrieve operation.) In this paper we prove that off-line memory checking, in the sense described above, is necessarily invasive, even if we make the problem somewhat easier for the checker to exclude trivial counter-examples. We show that even if the checker is allowed to read a constant number of registers from the large memory after each "store" or "retrieve" instruction, off-line non-invasive memory checking is not possible. Moreover for the case when the invasiveness consists of storing some extra information together with each piece of data and retrieving it together with the data we give a quantitative lower bound on the amount of extra "invasive" information stored in the memory. Namely, if the checker has O(log n) memory and the probability of error is polynomially small than the "invasiveness" of the mentioned method of [5] is optimal upto a constant factor. With other words the total number of extra bits that must be written in the memory is at least &egr;T log T, where T is the number of store and retrieve operations. In the lower bounds we do not restrict the computational power of the checker at all, in fact we only assume that the checker is an n-way branching program with O(log n) bits of memory.

REFERENCES

• 1: Miklós Ajtai, Determinism versus non-determinism for linear time RAMs (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.632-641, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301424]
• 2: S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. 33rd IEEE Symp. on Foundation of Computer Science, pages 13--22, 1992.
• 3: S. Arora and S. Safra. Probabilistic checking of proofs. a new characterization of np. In Proc. 33rd IEEE Symp. on Foundation of Computer Science, pages 2--12, 1992.
• 4: P. Beame , M. Saks , Xiaodong Sun , E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.169, November 12-14, 2000
• 5: Manuel Blum , Will Evans , Peter Gemmell , Sampath Kannan , Moni Naor, Checking the correctness of memories, Proceedings of the 32nd annual symposium on Foundations of computer science, p.90-99, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185352]
• 6: M. Fischlin. Incremental cryptography and memory checkers. In Advances in Cryptology - Eurocrypt '97, Lecture Notes in Computer Science, Vol. 1233, pages 393--408. Springer-Verlag, 1997.
• 7: M. Fischlin, Lower bounds for the signature size of incremental schemes, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.438, October 19-22, 1997
• 8: O. Goldreich, Towards a theory of software protection and simulation by oblivious RAMs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.182-194, January 1987, New York, New York, United States [doi>10.1145/28395.28416]
• 9: R. Ostrovsky, Efficient computation on oblivious RAMs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.514-523, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100289]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Algorithms, Experimentation, Performance, Theory