Detectors for very large images, such as 4000×4000 aerial scenes, cannot process the whole frame at once. They cut it into overlapping tiles, run the network on each tile, and merge the boxes. One consequence of this design has gone unused for defense: a tile's predictions depend only on that tile's pixels. If an attacker plants an adversarial patch (a printed or pasted pattern built to make the detector miss nearby objects), the patch can only affect detections in tiles that contain it. The tiling grid is therefore a set of walls that adversarial influence cannot cross. Current pipelines use a fixed, public grid, so an attacker who knows where the walls are can always keep the patch on the same side as the target.
This note proposes that the defender randomize the partition and solve for the randomization rather than jittering uniformly. In each image the detector runs a small number $K$ of tilings with different offsets and tile sizes. The joint distribution over these $K$ tilings is computed as a Stackelberg mixed strategy: the defender commits publicly to the distribution, and an attacker who knows it chooses where to put the patch. If any pass contains the target whole in a tile with no patch pixels, that pass's prediction for the target equals the clean prediction exactly, whatever the patch contains. Taking the union of detections across passes therefore yields a probabilistic recall certificate that depends only on geometry and holds against fully adaptive attacks. The new element is not randomness itself. It is treating the redundancy that overlapping tiling already pays for as isolation redundancy, and showing that the distribution over the $K$ passes taken together, not the distribution of each pass separately, determines how strong the guarantee is.
Core Claim
The suppression attacks of Benchmarking Adversarial Patch Against Aerial Detection build patches with a transformation layer for physical realism and a loss on average objectness. They place the patch next to the target rather than on it, and reduce detector AP by up to 87.86% white-box and 85.48% black-box on DOTA and RSOD. These attacks need the patch and the target to fall inside the same receptive field. With tiled inference, that receptive field is the tile. We claim that a partition mixed strategy computed for a fixed compute budget of $K$ passes can provably recover targets separated from the patch by a gap $d$ at much smaller $d$ than independent uniform jitter can, and that it removes the blind spots any deterministic grid has.
A one-dimensional calculation shows the core effect. Let $W$ be the tile size and $d$ the gap between patch and target. One uniformly shifted grid places a boundary inside the gap with probability $d/W$. With $K$ independent shifts, the probability that no pass separates the patch from the target is
$$P_{\text{indep}}(\text{fail}) = (1 - d/W)^K .$$
If instead the $K$ offsets form a lattice with spacing $W/K$, shifted together by a single uniform random amount, the separating events are disjoint, and
$$P_{\text{coord}}(\text{fail}) = \max(0,\ 1 - Kd/W),$$
which reaches zero at $d = W/K$. Independent jitter never reaches zero. A deterministic lattice gives zero failure only for $d \ge W/K$. Below that gap an informed attacker places the patch between fixed boundaries and fails the defense with certainty, and the random common shift is what removes that blind spot.
The real problem is two-dimensional and harder. Objects vary in size, a tile must contain the whole target to detect it (the bisection failure documented in The Power of Tiling for Small Object Detection), smaller tiles cost more compute, and some classes matter more than others. Under these constraints the equilibrium has no closed form. That is why the question becomes a game to be solved numerically rather than a fixed jitter recipe.
Relation to Prior Work
Two lines of work already randomize tile grids, both for image quality. Alleviating tiling effect by random walk sliding window moves the window origin by a random walk across passes and blends with a center-weighted map to remove seams in synthesized pathology slides. Any-Size-Diffusion shifts a non-overlapping latent grid at each denoising step, an "implicit overlap" that halves latency relative to explicit overlap. Both methods supply the mechanism we reuse, shifting partitions across passes. Neither has an attacker, and both draw each shift independently and uniformly. We change both features: the passes are coupled, and their distribution is optimized against an attacker who best-responds.
On the defense side, PuriDefense splits an image into a fixed grid and samples a purifier at random for each patch. It randomizes which model is used, while we keep the model fixed and randomize where the partition falls. Randomization matters proves that deterministic classifiers admit no pure Nash equilibrium against adversaries, and builds a two-model mixture (Boosted Adversarial Training) that improves adaptive-PGD accuracy on CIFAR-10 from 0.42 to 0.55. This motivates mixing, but its gains are empirical. Our spatial version gives a certificate because the isolation argument does not depend on what the patch contains. ARMOR supplies the commitment model: a defender who can be observed commits to a public mixed strategy computed by a Bayesian Stackelberg solver. We use the same structure with tile boundaries in the role of patrols. Double Oracle Neural Architecture Search supplies a way to solve games whose strategy space is too large to enumerate. We need it because the set of joint $K$-tuples of offsets and scales grows combinatorially.
On the reconstruction side, Continuous Patch Stitching shows that block-wise processing without padding can reproduce full-image computation bit for bit. That result constrains our design: if tiles shared context the way CPS reproduces full-image processing, the isolation property would disappear. The firewall exists only because tiles are processed independently, and we keep it that way on purpose.
The weighted blending methods of Benjdira et al. and Edirimuni, and the duplicate-box NMS used with DOTA, all assume every tile is honest. Score-based NMS lets an attacked pass with high-confidence false boxes override clean passes. This is why our fusion rule differs.
Research Program
The first component is the threat model and certificate. The attacker controls a contiguous region of at most $p \times p$ pixels whose position and content can be chosen after seeing the defender's distribution. The attacker may also optimize the patch with expectation over that distribution. For a ground-truth object $g$, defender configuration $c$ (a joint $K$-tuple of tile sizes and offsets), and patch placement $a$, define $\text{iso}(g, c, a)=1$ if some pass in $c$ has a tile that contains $g$ whole, contains no pixel of $a$, and detects $g$ on clean input. The certified recall of a mixed strategy $\pi$ is the expected value over configurations drawn from $\pi$, minimized over placements $a$ at gap at least $d$. Since $\pi$ has finite support, this quantity can be computed exactly by running the detector once per tile in the support. No attack optimization is needed to compute it.
The second component is equilibrium computation. Placements are discretized relative to each target (direction, gap, patch size), and configurations are discretized subject to a compute budget expressed as total tiled area processed. The defender's problem is a linear program: maximize the value-weighted worst-case isolation probability over $\pi$. For larger configuration spaces we run double oracle. The best-response oracle for the attacker is a search over placements, which is cheap because the payoff is geometric. The oracle for the defender proposes new $K$-tuples.
We will also try to prove that for a single object size, a single tile size, and translation-invariant payoffs, the shifted lattice is optimal among all $K$-pass strategies. The disjoint-events argument above suggests this, but it has not been proved. We then measure how far the solved equilibrium departs from the lattice once object sizes and the bisection constraint are added.
The third component is fusion. Union fusion keeps a box if any pass produces it, after clustering boxes that refer to the same object. It is certified against suppression and costs some false positives on clean images. We will report this cost and evaluate a variant that requires agreement between passes. The variant trades some of the suppression certificate for resistance to hallucinated boxes, since a patch can create false boxes in every pass that contains it.
Baselines
The naive reference point is the standard pipeline: a deterministic 25%-overlap grid as in The Power of Tiling for Small Object Detection, or DOTA's 1024×1024 overlapping crops (DOTA), with standard oriented NMS. On clean DOTA the reported oriented Faster R-CNN figure is 54.13% mAP (DOTA). On VisDrone2018 tiling raised Pelee mAP from 11% to 36%. We retrain our own detector, so we reproduce these pipelines rather than compare against the published numbers directly. The attack reference point is the AP-PA attack, which reduced AP by up to 87.86% white-box (Benchmarking Adversarial Patch Against Aerial Detection). The file contains no reported result for any defense evaluated against AP-PA on DOTA.
The strongest geometric competitor is a deterministic dense sliding window or a deterministic offset lattice with the same compute budget and the same union fusion. It obtains the full certificate for gaps at least $W/K$ at no extra cost, so it isolates exactly what randomizing the common shift adds. The strongest randomized competitor is $K$ independent uniform shifts in the style of the two diffusion and pathology methods, again with the same budget and fusion. It isolates what solving the game adds. The strongest model-hardening competitor is the same detector adversarially trained against AP-PA patches on DOTA tiles, with matched GPU hours. We also train a two-model Boosted Adversarial Training mixture following Randomization matters to represent randomization over models.
Two ablations complete the comparison. The first keeps the solved partition distribution but replaces union fusion with score-based NMS, which isolates the fusion rule. The second keeps the solver but restricts it to one tile size, which isolates mixing over scales.
All methods use the same backbone, training data, total inference area, and attack budget. Every randomized defense is attacked with expectation over its own published distribution. To count as beating a baseline, the solved strategy must achieve higher certified recall at every gap below $W/K$, at least match empirical robust AP under adaptive attacks, and lose no more than a pre-registered small margin of clean mAP.
Why not just…?
Why not just jitter the grid uniformly, as the diffusion and pathology methods already do? This is the closest alternative, and our own calculation partly answers it. Independent uniform shifts leave a failure probability of $(1-d/W)^K$, which stays positive at every gap, while coupled shifts reach zero at $W/K$. The comparison with independent jitter at matched $K$ settles the single-scale case. The real risk is that in two dimensions with mixed object sizes, the solved equilibrium turns out almost identical to a simple shifted lattice. In that case the honest conclusion is that coupling matters and solving the game does not, and we will report it that way.
Why not just adversarially train the detector? Adversarial training improves robustness against the attack families it was trained on, but it offers no guarantee against new patch content. Randomization matters reports standard adversarial training falling to 0.42 accuracy under adaptive PGD on CIFAR-10. The two approaches combine naturally: a hardened detector can sit inside our partition strategy. The experiment reports both alone and combined. If hardening alone matches our empirical robust AP, the contribution reduces to the certificate, and we will say so.
Why not just use a dense deterministic sliding window? Above the gap $W/K$ it certifies just as well. Below that gap, an attacker who knows the fixed boundaries can always find a placement that no boundary separates. The informed attacker's best response against the deterministic lattice therefore measures what the random common shift is worth.
This advantage depends on the attacker knowing the image coordinates. For physical patches photographed from drones whose pose varies, the grid is already effectively random relative to the scene. We therefore treat digital tampering, where the attacker edits a known image, as the main setting, and physical attacks as a secondary one.
Why not just use Vision Transformers? Adversarial attacks and adversarial robustness in computational pathology finds that ViTs keep an AUROC of 0.827 under PGD where ResNets fall to 0.429. Patch attacks still transfer to transformer detectors at an 85.48% black-box AP drop (Benchmarking Adversarial Patch Against Aerial Detection), and large scenes still require tiling. We include a transformer backbone so the comparison is architecture-neutral.
Decisive Checks
The experiments use DOTA (15 classes, more than 57% small instances) and VisDrone2018. We report clean mAP, empirical AP under AP-PA with expectation over the defender's distribution and placements chosen by the attacker, and certified recall as a function of the gap $d$ and patch size $p$ at compute budgets $K = 2, 4, 8$.
The first check concerns the gap between patch and target. If effective patches must essentially touch their targets, the certificate is empty at the gaps that matter. To test this, we measure AP-PA's suppression strength as a function of gap on a deterministic grid. If suppression collapses only below gaps smaller than achievable $W/K$, the defense is irrelevant against adjacent patches. That would be a clear negative result.
The second check is the comparison of coordinated against independent randomization at matched compute. The predicted ordering in certified recall follows from the two failure formulas above.
The third check measures how much clean mAP union fusion costs and how many false boxes a hallucination patch can add. These numbers determine whether the method is usable in deployment.
References
- Benchmarking Adversarial Patch Against Aerial Detection
- The Power of Tiling for Small Object Detection
- Alleviating tiling effect by random walk sliding window in high-resolution histological whole slide image synthesis
- Any-Size-Diffusion: Toward Efficient Text-Driven Synthesis for Any-Size HD Images
- PuriDefense: Randomized Local Implicit Adversarial Purification for Defending Black-box Query-based Attacks
- Randomization matters How to defend against strong adversarial attacks
- ARMOR Security for Los Angeles International Airport
- Double Oracle Neural Architecture Search for Game Theoretic Deep Learning Models
- Continuous Patch Stitching for Block-Wise Image Compression
- Streamlined Global and Local Features Combinator (SGLC) for High Resolution Image Dehazing
- IterativePFN: True Iterative Point Cloud Filtering
- DOTA: A Large-Scale Dataset for Object Detection in Aerial Images
- Adversarial attacks and adversarial robustness in computational pathology