Optimal Backup Strategies Against Cyber Attacks

Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, Adi Shamir

Abstract

Online checkpointing is a critical technique for fault tolerance in long-running computations and security against stealthy cyber attacks. This work settles a 50-year-old open problem regarding the efficiency of online checkpointing algorithms when memory is limited to $k$ snapshots. We prove that the asymptotic efficiency limit is exactly $\ln 4 \approx 1.386$ and provide a recursive geometric algorithm that achieves this bound. Furthermore, we identify provably optimal strategies for small $k$ and demonstrate practical applications in cryptographic collision finding and system recovery.

Introduction

Imagine running a massive simulation or a complex scientific computation that takes weeks to complete. If the system crashes or a bug is discovered, restarting from the beginning is prohibitively expensive. Instead, systems save "checkpoints"—snapshots of the state—at various intervals to allow for "rolling back" to a recent point.

The fundamental challenge arises when memory is finite. If a system can only store $k$ checkpoints, which ones should be kept? As the computation progresses, the algorithm must decide which old checkpoint to delete to make room for a new one at the current time. The goal is to keep these $k$ checkpoints as evenly spread as possible across the entire timeline $[0, T]$, even though the end time $T$ is unknown in advance.

The online checkpointing update process: an old checkpoint ($T_2$) is moved to the current time ($T=t_i$) to maintain a set of $k$ snapshots as the computation progresses.

Methodology

The research team, including Adi Shamir, combined rigorous mathematical proofs with computational optimization to solve this "pebbling game."

Linear Programming (LP) Framework

The authors modeled checkpointing constraints as a system of linear inequalities. To find optimal strategies for small $k$, they utilized a Python-based solver (GLPK via CVXOPT) to search for "blocking sets"—sequences of update actions that prove a certain efficiency level is impossible to beat.

Recursive Geometric Algorithm

A new class of algorithms was introduced where the decision of which checkpoint to replace is determined by a recursive pattern. This allows the checkpoints to maintain a "multi-scale" distribution that remains efficient as the timeline grows exponentially.

Lower Bound Proofs

Using a technique involving "truncated bounding expressions," the researchers proved that no algorithm, regardless of complexity, can achieve an efficiency better than $\ln 4$ for large $k$. Efficiency ($q$) is defined as the ratio between the longest gap between checkpoints in the online version versus the ideal, perfectly uniform spacing achievable with prior knowledge of the end time.

Key Results

The Magic of $\ln 4$

The paper provides the definitive answer to the asymptotic limit of this problem: $q_k \to \ln 4 \approx 1.386$ as $k \to \infty$. This closes a significant gap in the literature, where previous bounds ranged from 1.30 to 1.59.

Small $k$ Optimality

The authors identified exact optimal efficiencies for small systems. For instance, for $k=2$, the best efficiency is $1.5$; for $k=10$, it is approximately $1.467$. Notably, the intuitive "round-robin" strategy—replacing the oldest checkpoint every time—is only optimal for $k \leq 3$. For larger $k$, a more sophisticated mix of old and new snapshots is required.

Practical Applications

Beyond standard fault tolerance, the paper identifies two novel applications:

  1. Cryptographic Collisions: Using $k$ pointers with an optimal checkpointing strategy significantly speeds up the search for hash function collisions, reducing computational waste by approximately 20% compared to standard doubling methods.
  2. Cyber Security (Stealthy Attacks): In ransomware or stealthy corruption scenarios, an attacker may infect a system long before striking. Optimal checkpointing ensures a defender always has a relatively recent "clean" backup, regardless of when the infection occurred.

Conclusion and Future Work

While this work provides the theoretical limit for worst-case gaps, finding the exact optimal pattern for very large $k$ (e.g., $k=100$) remains computationally challenging. Future research may explore average-case rollback times, which could offer different insights for specific hardware failure profiles. Nonetheless, the recursive geometric algorithm provides a mathematically optimal framework for modern high-stakes computing environments.

Summary updated

BibTeX
@article{baron2018optimal,
  author = {Achiya Bar-On and Itai Dinur and Orr Dunkelman and Rani Hod and Nathan Keller and Eyal Ronen and Adi Shamir},
  title = {{Optimal Backup Strategies Against Cyber Attacks}},
  journal = {ACM Transactions on Algorithms},
  year = {2018},
}
Figure