Adversarial Turing Patterns from Cellular Automata

Nurislam Tursynbek, Ilya Vilkoviskiy, Maria Sindeeva, Ivan V. Oseledets

Introduction

Deep Neural Networks (DNNs) are notoriously vulnerable to adversarial perturbations—tiny, often imperceptible changes to an image that cause a model to misclassify it. A particularly dangerous subset is the Universal Adversarial Perturbation (UAP): a single noise pattern that, when added to any image, causes a high rate of misclassification across an entire dataset.

While researchers have developed various ways to craft these UAPs, a deep theoretical understanding of why they take specific geometric shapes has been lacking. Previous work noted that these perturbations often resemble the stripes and spots found in nature, known as Turing patterns. This paper, presented at AAAI-21, provides a mathematical bridge between biological pattern formation and artificial intelligence security.

The Theoretical Bridge: UAPs as Cellular Automata

The authors bridge the gap between two seemingly unrelated fields: Boyd Iteration (a standard method for crafting UAPs) and Cellular Automata (CA) (discrete models that generate complex patterns through simple local rules).

The core theoretical contribution is the proof that under realistic assumptions—specifically the "averaging out" of non-linearities like ReLU across large image batches—the complex iterative process of crafting a UAP simplifies into a convolutional update rule. This rule is mathematically identical to the one used by Cellular Automata to generate Turing patterns.

Comparison between constructed UAPs and biological Turing patterns.

One of the most surprising findings is that while individual neurons are highly non-linear, the expected value of their behavior across a large batch behaves like a linear convolution. This explains why UAPs end up looking like structured, repetitive patterns rather than random noise.

The Simple CA Attack

Using this insight, the researchers developed a Simple CA attack. Instead of calculating complex gradients for every pixel, they define a simple convolutional kernel $Y$ parameterized by just two numbers ($l_1, l_2$) representing the dimensions of a central rectangle. They then use an evolutionary algorithm (CMA-ES) to find the optimal parameters to maximize the "fooling rate" in a black-box scenario.

The researchers observed a direct relationship between network architecture and pattern structure: attacking deeper layers produces Turing patterns with larger "features" (thicker stripes), while attacking early layers produces finer, more detailed patterns.

Evolution and variety of patterns generated by the Cellular Automata approach.

Key Results and Performance

The efficiency of this approach is remarkable. A simple Cellular Automaton with only two parameters can generate a pattern that fools state-of-the-art networks over 80% of the time.

  • High Fooling Rates: In black-box settings, optimized Turing patterns achieved a fooling rate of ~90.6% on MobileNetV2 and ~75.6% on VGG-19.
  • Outperforming Baselines: When compared to the Single Fourier Attack (SFA), the CA method was significantly more potent. On VGG-16, it achieved an 81.2% fooling rate compared to SFA's 53.3%.
  • Robustness: Even "random" Turing patterns (without optimization) proved surprisingly effective, achieving over 50% fooling rates on several models.

Conclusion and Future Directions

By showing that adversarial vulnerabilities are essentially "biological" in their structure, this paper opens a new path for studying DNN robustness through the lens of mathematical biology. While the proof relies on certain assumptions regarding the Jacobian's diagonal matrices, the empirical results strongly support the theory. Future work may leverage this "convolutional structure" of vulnerabilities to develop better defense mechanisms, such as specialized spectral normalization.

Summary updated

BibTeX
@inproceedings{tursynbek2021adversarial,
  author = {Nurislam Tursynbek and Ilya Vilkoviskiy and Maria Sindeeva and Ivan V. Oseledets},
  title = {{Adversarial Turing Patterns from Cellular Automata}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i3.16372},
}
Figure