Adi Shamir: Towards Quantitative Analysis of Cyber Security

Friday, April 27, 2018 - 10:30am to 12:00pm
Patil/Kiva G449
Adi Shamir, Weizmann
ABSTRACT:  Cyber security had become an extremely hot topic in the last few years, but almost all the research results published so far had been qualitative in nature: they do not formulate a precise mathematical model of the problem, do not numerically compare alternatives, and do not  try to find optimal solutions for cyber security problems. In this paper I will describe some initial attempts (developed jointly with Bar-On Dinur Dunkelman Hod Keller and Ronen)  to create such a quantitative theory of some particular subproblems in cyber security. In particular, I will consider the problem of how 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, and the strategies he can use resemble a pebbling game with k tokens which can be placed anywhere along the timeline. However, the optimal solution of this simple pebbling game is surprisingly complicated. In this talk I will describe concrete provably optimal backup strategies for all $k \leq 10$, and asymptotically optimal strategies for large k. Our results also solve a long standing open problem in fault tolerant computing called {\it optimal checkpointing}, which had been investigated in various forms for almost 50 years.