# Combinatorics Seminar

When: Sunday, June 25, 10am

Where: Schreiber 309

Speaker: Rani Hod, Bar-Ilan University

Title: Optimal backup strategies against cyber attacks

## Abstract:

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.

redesigned by barak soreq