dndw: cats and mice 1

A “cat and mouse game” is, “a contrived action involving constant pursuit, near captures, and repeated escapes.” It can be used to describe many adversarial systems, such as:

• Academic Dishonesty vs Academic Institutions
• Video Game Hackers vs Anticheats
• Malware vs Antivirus
• Any other similar adversaries

The “attacker” must continuously select novel winning strategies and the “defender” must continuously update their patches to cover the attackers.

objective

We’re going to mathematically prove that, ignoring external factors, that it is never going to be possible for the defender to “win” (permanently block the attacker).

the proof

We’ll begin by defining the system using a set of logical axioms:

1. The attacker’s goal is to defeat the defender by any means necessary
2. In one game, the attacker wins if their strategy is not blocked by the defender.
3. The attacker will develop new methods to win
4. The defender’s goal is to stop the attacker by any means necessary
5. The defender wins a game by blocking the attacker.
6. The defender has a nonzero chance of selecting the attacker’s strategy at random without being prompted by any previous game.
7. Each game, both sides cannot modify their strategy during the game.
8. Both the defender and the attacker are perfectly logical and innovative.
9. During the game, the defender is not able to apply an infinite number of defenses (the number of defenses they have active during the game must be bounded)
10. During the game, the attacker can only use one strategy.
11. Each game must end in exactly one of the parties winning.
12. The set of winning attacker strategies and the set of possible defenses are:
    • Countably Infinite
    • Equal in cardinality
    • Bijective (each possible defense prevents a corresponding strategy from winning).
13. There are an infinite number of games

definitions

Let $S = \{s_1, s_2, s_3, \dots\}$ represent the set of possible attacker strategies.

Let $D = \{d_1, d_2, d_3, \dots\}$ represent the set of possible defender strategies.

Let there be a bijection $f: S \rightarrow D$ that satisfies axiom 12 such that $f(s_i) = d_i$ represents that $d_i$ blocks strategy $s_i$.

In game $n \in \mathbb{N}$, the attacker selects $s_n \in S$ and the defender selects $D_n \subset D$. The attacker wins if $f(s_n) \notin D_n$ and the defender wins if $f(s_n) \in D_n$.

lemma 1

For game $n$, there exists infinitely many attacker strategies not covered in $D_n$.

$|D_n| \le k$, where $k$ is finite, meaning there are infinitely many defenses $d$ where $d \notin D_n$. Considering the bijection that $f(s_i) = d_i$, there must exist infinitely many elements $s_i$ such that $f(s_i) \notin D_n$.

lemma 2

The attacker can win infinitely many games.

By lemma 1, there exists an infinite number of strategies not covered, meaning that if the attacker selects a strategy at random, there is a nonzero probability of the attacker selecting a strategy not in $D_n$. Since this occurs over an infinite sample space, the attacker selecting a strategy $s$ such that $f(s) \notin D_n$ must occur infinite times.

The attacker, knowing that if he selects randomly he has a nonzero probability of winning, will elect to do so by axiom 8.

lemma 3

The defender can win infinitely many games.

Let the defender construct the sequence $(D_n)$ such that $\cup^\infty_{n=1}\:D_n \subseteq D$ and every defense $d_i \in D$ appears infinitely many times in the sequence. Considering the bijection $f$, every attack strategy $s$ has a blocker $f(s)$ that appears< infinitely often. Therefore, any strategy $s \in S$ is covered infinitely many times.

lemma 4

The attacker cannot go on an infinite winning streak.

• Assume that the attacker will win every game $n \in \mathbb{N}$ for $n \ge N$
• This means $f(s_n) \notin D_n$ for every $n \ge N$
• Lemma 3 contradicts this, as the defender can win infinitely many games.
• The premise is incorrect, proving lemma 4 by contradiction.

lemma 5

The defender cannot go on an infinite winning streak.

Trivial from lemma 2: the attacker can win infinitely many games, therefore, the set of attacker wins is unbounded.

proof

Therefore, by lemmas 2 and 3, the set of attacker wins and the set of defender wins are both unbounded. By lemmas 4 and 5, the cardinality of these sets are both equal to $\aleph_0$.

defender ~ illogical

We’ve proven that the attacker will always win an infinite number of times, and that the number of attacker and defender wins are equal in number.

Does this mean that it will always be illogical to play the defender? In the next post, we’ll discuss the motivations behind playing both sides.