When: Sunday, June 25, 10am
Where: Schreiber 309
Speaker: Rani Hod, Bar-Ilan University
Title: Optimal backup strategies against cyber attacks
We introduce a new problem of finding the best way to protect a computer system against cyber and ransomware attacks by choosing an optimal backup scheme using k storage devices. While in standard backup schemes it is beneficial to backup as frequently as possible, in the case of sophisticated cyber attacks any attempt to connect a backup device to an already infected computer is likely to stealthily corrupt its data and thus make it unusable when the actual attack happens. Our formalization of the problem casts it as a special case of an online/offline optimization problem, in which the defender tries to minimize the maximal extra cost caused by his lack of knowledge about the time of the infection. Any backup scheme can be viewed as a very simple pebbling game, where in each step any one of the k backup pebbles can be moved to any point to the right of all the pebbles along the time axis, and the goal of the game is to keep the pebbles as evenly spread as possible at all times. However, its optimal solution is surprisingly complicated and leads to interesting combinatorial questions which are reminiscent of questions in discrepancy theory. We find provably optimal backup strategies for all k<10, and prove matching upper and lower bounds of ln(4) on the asymptotic efficiency of optimal backup schemes.
Joint work with A. Bar-On, I. Dinur, O. Dunkelman, N. Keller, E. Ronen and A. Shamir.
