The invasiveness of off-line memory checking

摘要

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 ε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.