How to Withstand Mobile Virus Attacks.
Rafail Ostrovsky, Moti Yung.
Abstract: We introduce a study of distributed adversarial model of computation in which faults are non-stationary and can move through the network, analogous to a spread of a virus or a worm. That is, our machine model is a synchronous distributed architecture in which a malicious, infinitely-powerful adversary injects/distributes computer viruses at a certain rate at every round. We assume that the detection (of infected sites) can proceed with the same rate as the infection. Thus, we allow up to a constant fraction of the machines to be infected at any single round, and allow all the machines to be eventually infected at different rounds. (We note that in practice, this is indeed a reasonable assumption to make.) In this model, we show how local computations (at each processor) and global computations can be made robust using a constant factor resilience and a polynomial factor redundancy in the computation.
comment: Appeared In Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC-91) August 1991, Montreal, Quebec, Canada, pp. 51-59.
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |