# On Lucas-Carmichael Integers

Sridhar T (1) and Subramani Muthukrishnan (2) (1) Indian Institute of
Information Technology, Design and Manufacturing, Kancheepuram, Chennai -
600127, INDIA  (2) Indian Institute of Information Technology, Design and
Manufacturing, Kancheepuram, Chennai - 600127, INDIA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this paper, we prove a sufficient and necessary condition for Lucas-
Carmichael integers. We also study some interesting properties of such
integers. Finally, we prove that there are infinitely many Lucas-Carmichael
integers assuming the Prime $k$-tuples Conjecture.

##  1\. Introduction

The classical Fermat’s Little theorem states that, if $p$ is a prime number,
then for any positive integer $a$ satisfies $a^{p}\equiv a\pmod{p}.$ In
particular, if $a$ is not divisible by $p$, then we have $a^{p-1}\equiv
1\pmod{p}.$ Fermat’s Little theorem is a primary distinguished primality test.
However, the converse of Fermat’s Little theorem is not true. For example,
$561=3\times 11\times 17$ is the least composite integer satisfies
$a^{561-1}\equiv 1\pmod{561}$ for every positive integer $a$ with
$gcd(a,561)=1.$ The following composite integers $1105,$ $1729,$ $2465$ are
satisfies converse of Fermat’s Little theorem.

######  Definition 1.1.

A composite positive integer $m$ is called a Carmichael number if the
congruence $a^{m-1}\equiv 1\pmod{m}$ holds for all integers $a$ co-prime to
$m.$

In $1899,$ Korselt [4] was the first to observe the following criteria for
Carmichael numbers. Carmichael [2, 3] showed some properties for Carmichael
numbers.

######  Theorem 1.1.

(Korselt’s criterion, $1899$). A composite number $m$ is a Carmichael number
if and only if $m$ is square-free and every prime divisor $p$ of $m$ satisfies
$p-1$ $|$ $m-1.$

######  Theorem 1.2.

(R. D. Carmichael, $1910$). Every Carmichael number $m$ is odd and square-free
and has at least three prime factors. If $p$ and $q$ are prime divisors of
$m,$ then

$(i)~{}p-1~{}|~{}m-1,~{}~{}~{}~{}~{}~{}(ii)~{}p-1~{}|~{}\frac{m}{p}-1,~{}~{}~{}~{}~{}~{}(iii)~{}p~{}\nmid~{}q-1.$

In 1994, W. R. Alford, Andrew Granville, and Carl Pomerance [5] proved that
the set of all Carmichael numbers is infinite. More precisely, they showed
that if $C(x)$ denotes the number of Carmichael numbers less than $x,$ then
$C(x)>x^{2/7}$ for sufficiently large $x.$

Recently, B. C. Kellner and J. Sondow [6] derived a new characterization for
Carmichael integers. For a positive integer $m,$ denote $S_{p}(m)$ the sum of
the base-$p$ digits. Then they proved that a positive integer $m$ is a
Carmichael integers if and only if it is square-free and each of its prime
factors $p$ satisfies both $S_{p}(m)\geq p$ and $S_{p}(m)\equiv 1\pmod{p-1}.$
In particular, a primary Carmichael integer $m$ is a Carmichael integer which
satisfies $S_{p}(m)=p$ for every prime factor $p$ of $m.$ B. C. Kellner and J.
Sondow [6] counted the Carmichael numbers and primary Carmichael numbers up to
$10^{10}.$ In 2022, Wagstaff [1] proved that the Prime $k$-tuples Conjecture
implies that there are infinitely many primary Carmichael numbers.

An elliptic curve $E$ over $\mathbb{Q}$ is a smooth projective curve that
satisfies the Weierstrass equation

$E:Y^{2}=X^{3}+aX+b,$

where $a,b\in\mathbb{Q}$ and discriminant $0\neq\Delta=4a^{3}+27b^{2}.$ Dan
Gordon [8] given the following primality test. For an elliptic curve $E$ with
complex multiplication by $\mathbb{Q}(\sqrt{-d}),$ let $P\in E(\mathbb{Q})$ be
a rational point of infinite order, $m$ be a positive integer such that
$gcd(m,6\Delta)=1$ and $(-d$ $|$ $m)=-1,$ where $(-d$ $|$ $m)$ is the Jacobi
symbol. If $m$ is prime, then

$[m+1]P\equiv\mathcal{O}\pmod{m}.$

If $m$ satisfies the above congruence, then $m$ is a probable prime by
Gordon’s primality test. Also, $m$ is composite number when $m$ does not
satisfies the above congruence relation.

######  Definition 1.2.

Let $m$ be composite number and $E$ be a $CM$-elliptic curve. If $m$ satisfies
the Gordon primality test then $m$ is called an $E$-elliptic Carmichael
number. A composite integer $m$ is said to be an elliptic Carmichael number if
$m$ is an $E$-elliptic Carmichael number for every $CM$-elliptic curve $E.$

Ekstrom et al. [9] give the smallest elliptic Carmichael number

$\displaystyle 617,730,918,224,831,720,922,772,642,$ $\displaystyle
603,971,311$ $\displaystyle=p(2p+1)(3p+2),$

where $p=468686771783.$ Also, they proved the following Elliptic Carmichael
Condition.

######  Theorem 1.3.

(Elliptic Carmichael Condition). Let $m$ be a square-free, composite positive
integer with an odd number of prime factors. Moreover, let $\alpha=8\cdot
3\cdot 7\cdot 11\cdot 19\cdot 43\cdot 67\cdot 163.$ Then $m$ is an elliptic
Carmichael number if for each prime $p$ $|$ $m,$ we have $\alpha$ $|$ $p+1$
and $p+1$ $|$ $m+1.$

In the above Elliptic Carmichael Condition, we note the following Korselt-like
criterion: $p+1$ $|$ $m+1$ whenever $p$ $|$ $m.$ Following this Elliptic
Carmichael condition, we have the Lucas-Carmichael integers as follows:

######  Definition 1.3.

A Lucas-Carmichael integer is a square-free positive composite integer $m$
such that $p+1$ $|$ $m+1$ whenever $p$ $|$ $m$.

Thomas Wright [7] proved that there are infinitely many Lucas-Carmichael
integers. In this paper, we derive a new characterization for Lucas-Carmichael
integers and prove that there are infinitely many Lucas-Carmichael integers
assuming the Prime $k$-tuples Conjecture. Also, we obtain some general form of
Lucas-Carmichael integers with odd number of prime factors and prove that
there are infinitely many Lucas-Carmichael integers with odd number of prime
factors assuming the Prime $k$-tuples Conjecture.

##  2\. Preliminaries

We start with an interesting and elementary result.

######  Lemma 2.1.

Let $m,n$ be two positive integers with $n>m$. Then, $S_{m+1}(n+1)\equiv
n+1\pmod{m}.$

###### Proof.

We write the integer $n+1$ with respect to the base $m+1$ as follows:

$n+1=n_{0}+n_{1}(m+1)+n_{2}(m+1)^{2}+n_{3}(m+1)^{3}+\cdots,$ (1)

where $0\leq n_{i}<m+1,$ for all $i$.

We can rewrite the equation (1) as:

$n+1=n_{0}+(m+1)\bigg{\lfloor}\frac{n+1}{m+1}\bigg{\rfloor}~{}~{}.$ (2)

Further, we also have

$~{}~{}\bigg{\lfloor}\frac{n+1}{(m+1)^{j}}\bigg{\rfloor}=n_{j}+(m+1)\bigg{\lfloor}\frac{n+1}{(m+1)^{j+1}}\bigg{\rfloor},$
(3)

for all $j\geq 1.$

Using equations (2) and (3), we have

$\displaystyle(n$
$\displaystyle+1)+\bigg{\lfloor}\frac{n+1}{m+1}\bigg{\rfloor}+\bigg{\lfloor}\frac{n+1}{(m+1)^{2}}\bigg{\rfloor}+\cdots$
$\displaystyle=(n_{0}+n_{1}+n_{2}+\cdots)+(m+1)\bigg{\\{}\bigg{\lfloor}\frac{n+1}{m+1}\bigg{\rfloor}+\bigg{\lfloor}\frac{n+1}{(m+1)^{2}}\bigg{\rfloor}+\cdots\bigg{\\}}$

Let
$\alpha=\Big{\lfloor}\frac{n+1}{m+1}\Big{\rfloor}+\Big{\lfloor}\frac{n+1}{(m+1)^{2}}\Big{\rfloor}+\cdots\in\mathbb{N}.$

Now, we have

$(n+1)+\alpha=(n_{0}+n_{1}+n_{2}+\cdots)+(m+1)\alpha\\\ $

Since, $S_{m+1}(n+1)=n_{0}+n_{1}+n_{2}+\cdots$, the above equation becomes,

$(n+1)+\alpha=S_{m+1}(n+1)+(m+1)\alpha\\\ .$

That is,

$\alpha=\frac{(n+1)-S_{m+1}(n+1)}{m}$

Therefore, we have the desired equation

$S_{m+1}(n+1)\equiv n+1\pmod{m}.$

∎

######  Corollary 2.1.

Let $n\geq 1$ be an integer. Then

$S_{d+1}(n+1)\equiv 1\pmod{d},$

for all divisors $d$ of $n.$

###### Proof.

Since, by Lemma 2.1, $S_{d+1}(n+1)\equiv n+1\pmod{d}$, and since $d\mid n$, we
have $S_{d+1}(n+1)\equiv 1\pmod{d}.$ ∎

##  3\. Lucas-Carmichael integers

In this section, we prove a necessary and sufficient condition for Lucas-
Carmichael integers and also prove few interesting properties.

######  Proposition 3.1.

An integer $n>1$ is a Lucas-Carmichael integer if and only if $n$ is square-
free and $S_{p+2}(n+2)\equiv 1\pmod{p+1}$ for every prime divisor $p$ of $n$.
That is,

$\mathcal{L_{C}}=\Big{\\{}n\in\mathcal{S}~{}:~{}p~{}|~{}n~{}\Longrightarrow~{}S_{p+2}(n+2)\equiv
1\pmod{p+1}\Big{\\}}.$

Here, $\mathcal{L_{C}}$ and $\mathcal{S}$ denote the set of all Lucas-
Carmichael integers and square-free integers respectively.

###### Proof.

Let $n>1$ be a Lucas-Carmichael integer. Then, by definition $n$ is square-
free, and by Corollary (2.1), $S_{p+2}(n+2)\equiv 1\pmod{p+1}$ whenever $p$
divides $n.$

Now, we prove the converse part. Assume that $n$ is a square-free integer
satisfying

$S_{p+2}(n+2)\equiv 1\pmod{p+1}$ (4)

for all prime divisor $p$ of $n$.

By Lemma 2.1, we have

$S_{p+2}(n+2)\equiv n+2\pmod{p+1}.$ (5)

Combining equations (4) and (5), it is clear that $p+1$ divides $n+1$ whenever
$p$ divides $n$.

∎

######  Proposition 3.1.

Every Lucas-Carmichael integer $n$ is odd and has at least three prime factors
and $p+1$ $|$ $\frac{n}{p}-1$ for every prime $p$ divides $n.$

###### Proof.

Since $p+1$ divides $n+1$, $n+1$ is even and thus $n$ is odd.

Suppose that there is a Lucas-Carmichael integer $n$ with exactly two distinct
prime factors $p$ and $q.$ That is, $n=pq$. Assume that $p>q.$

Since $p+1$ divides $n+1,$ let

$k:=\frac{n+1}{p+1}=\frac{pq+1}{p+1}\in\mathbb{N}.$

Then,

$\displaystyle k$ $\displaystyle=\frac{pq-p+p+1}{p+1}$
$\displaystyle=\frac{p(q-1)+(p+1)}{p+1}$ $\displaystyle=\frac{p(q-1)}{p+1}+1.$

This implies that, $p+1$ divides $q-1.$ This is not possible. Hence $n$ has at
lease three prime factors.

Now, we prove that $p+1$ $|$ $\frac{n}{p}-1$ for every prime $p$ divides $n.$
Let $n=p_{1}p_{2}\cdots p_{r},$ $r\geq 3$ be a Lucas-Carmichael integer. Since
$p_{i}+1$ divides $n+1$ for all $i$, we let

$k_{i}:=\frac{n+1}{p_{i}+1}=\frac{p_{1}p_{2}\cdots
p_{r}+1}{p_{i}+1}\in\mathbb{N}.$

Let $n_{i}=\frac{n}{p_{i}}$, and we write

$\displaystyle k_{i}$ $\displaystyle=\frac{p_{1}p_{2}\cdots
p_{r}+n_{i}-n_{i}+1}{p_{i}+1}$
$\displaystyle=\frac{n_{i}(p_{i}+1)-(n_{i}-1)}{p_{i}+1}$
$\displaystyle=n_{i}-\frac{(n_{i}-1)}{p_{i}+1}.$

This implies that, $\frac{(n_{i}-1)}{p_{i}+1}=n_{i}-k_{i}\in\mathbb{Z}.$ That
is, $p_{i}+1$ divides $n_{i}-1.$ This completes the proof. ∎

######  Corollary 3.1.

Every prime factor $p$ of a Lucas-Carmichael integer $n$ is strictly less than
$\sqrt{n}.$

###### Proof.

By Proposition 3.1, we have $p<\frac{n}{p}$ for every prime factor $p$ of $n.$
This implies, $p<\sqrt{n}.$ ∎

######  Proposition 3.2.

If $n=mqr$ is a Lucas-Carmichael integer where $m\in\mathbb{N}$ and $q,r$ are
primes with $q<r.$ Then $q<3m^{2}$ and $r<3m^{3}.$

###### Proof.

Since $q$ and $r$ are prime divisors of a Lucas-Carmichael integer $n$, we
have $q+1|n+1$ and $r+1|n+1$.

That is,

$mqr\equiv-mr\equiv-1\pmod{q+1}~{}\text{and}~{}mqr\equiv-
mq\equiv-1\pmod{r+1}.$

Now, define

$C:=\frac{mq-1}{r+1}~{}\text{and}~{}D:=\frac{mr-1}{q+1}.$

Since $mq-1<mr-1<mr+m$ and so $C<m.$

As $r-q\geq 1,$ we have $m-1<m\leq m(r-q).$ This implies that, $m+mq<mr+1$.
Then,

$\displaystyle mq+m-q-1$ $\displaystyle<mr+1-q-1$ $\displaystyle=mr-q$
$\displaystyle<mr-1$ $\displaystyle m(q+1)-(q+1)$ $\displaystyle<mr-1$
$\displaystyle(m-1)(q+1)$ $\displaystyle<mr-1$ $\displaystyle m-1$
$\displaystyle<\frac{mr-1}{q+1}=D.$

Therefore, we have $1\leq C<m\leq D.$ Consider,

$\displaystyle D(q+1)$ $\displaystyle=mr-1$
$\displaystyle=m\Big{(}\frac{mq-1}{C}-1\Big{)}-1$
$\displaystyle=\frac{m^{2}q-m-mC-C}{C}$ $\displaystyle CD(q+1)$
$\displaystyle=m^{2}q-m-mC-C$ $\displaystyle=m^{2}q+m^{2}-m^{2}-m-mC-C$
$\displaystyle(CD-m^{2})(q+1)$ $\displaystyle=-m^{2}-m-mC-C<0.$

This implies that,

$\displaystyle 0<(m^{2}-CD)(q+1)$ $\displaystyle=m^{2}+m+mC+C$ $\displaystyle
q+1$ $\displaystyle\leq m^{2}+m(C+1)+C.$

Since $C<m,$ we obtain $q+1<m^{2}+m^{2}+m<3m^{2}$ and hence $q<3m^{2}.$

Next, we prove the other inequality. Consider,

$r+1=\frac{mq-1}{C}<\frac{m(q+1)}{C}<\frac{m(3m^{2}))}{C}<3m^{3}.$

and hence the inequality $r<3m^{3}$ holds. ∎

In the following section, we explicitly describe a class of Lucas-Carmichael
integers.

##  4\. Some general form of Lucas-Carmichael integers

Recall from Proposition (3.1) an integer $n$ is a Lucas-Carmichael integer if
and only if $p+1$ divides $S_{p+2}(n+2)-1$ whenever $p$ divides $n$. In this
section, we study some general form of Lucas-Carmichael integers with odd
number of prime factors.

######  Definition 4.1.

An integer $n\in\mathcal{L_{C}}$ is called a Primary Lucas-Carmichael integer
if $S_{p+2}(n+2)=p+2$ for every prime $p$ divides $n$ and the set of all such
integers is denoted by $\mathcal{L_{C}}^{\prime}$.

######  Definition 4.2.

Let $n$ be a Lucas-Carmichael integer and let

$\alpha:=\max_{p|n}~{}\Bigg{\\{}\frac{S_{p+2}(n+2)-1}{p+1}\Bigg{\\}}$

The integer $\alpha$ is called the degree of $n$.

We note that primary Lucas-Carmichael integers has degree $1$.

######  Lemma 4.1.

Let $m$ be a positive integer and $p=6m-1,$ $q=12m-1,$ $r=18m-1,$ and write
$U_{3}^{\prime}(m)=n=pqr.$ Then

$\displaystyle n+2$ $\displaystyle=5(p+2)^{3}+(p-27)(p+2)^{2}+45(p+2)+(p-20)$
$\displaystyle n+2$ $\displaystyle=(9m-5)(q+2)^{2}-(9m+11)(q+2)+(6m-5)$
$\displaystyle n+2$ $\displaystyle=(4m-2)(r+2)^{2}+(6m+5)(r+2)+(8m-2).$

###### Proof.

We rewrite $n+2$ with the base $p+2$ as follows:

$\displaystyle n+2$ $\displaystyle=(216m^{2}-102m+23)(p+2)-22$
$\displaystyle=(36m-23)(p+2)^{2}+46(p+2)-22$
$\displaystyle=5(p+2)^{3}+(p-27)(p+2)^{2}+46(p+2)-22$
$\displaystyle=5(p+2)^{3}+(p-27)(p+2)^{2}+45(p+2)+(p-20).$

Similarly, we rewrite $n+2$ with the base $q+2$ as follows:

$\displaystyle n+2$ $\displaystyle=(108m^{2}-42m)(q+2)+(78m+1)$
$\displaystyle=9m(q+2)^{2}-5(q+2)^{2}+(9m+11)(q+2)+(6m-5)$
$\displaystyle=(9m-5)(q+2)^{2}+(9m+11)(q+2)+(6m-5).$

Next, we rewrite $n+2$ with the base $r+2$ as follows:

$\displaystyle n+2$ $\displaystyle=(72m^{2}-26m)(r+2)+(62m+1)$
$\displaystyle=4m(r+2)^{2}-2(r+2)^{2}+(6m+5)(r+2)+(8m-2)$
$\displaystyle=(4m-2)(r+2)^{2}+(6m+5)(r+2)+(8m-2).$

∎

######  Corollary 4.1.

With the same hypotheses as Lemma $\ref{lemma0.7},$ we have $S_{p+2}(n+2)=p+2$
or $2p+3,$ $S_{q+2}(n+2)=2q+3,$ and $S_{r+2}(n+2)=r+2.$

###### Proof.

Since $n+1=5(p+2)^{3}+(p-27)(p+2)^{2}+46(p+2)-22,$ we have
$S_{p+2}(n+2)=5+(p-27)+46-22=p+2.$ Also, we have
$n+2=5(p+2)^{3}+(p-27)(p+2)^{2}+45(p+2)+(p-20)$ and so
$S_{p+2}(n+2)=5+(p-27)+45+p-20=2p+3.$

Since $n+1=(9m-5)(q+2)^{2}+(9m+11)(q+2)+(6m-5),$ we have
$S_{q+2}(n+2)=(9m-5)+(9m+11)+(6m-5)=24m+1=2q+3.$

Since $n+1=(4m-2)(r+2)^{2}+(6m+5)(r+2)+(8m-2),$ we have
$S_{r+2}(n+2)=(4m-2)+(6m+5)+(8m-2)=18m+1=r+2.$ ∎

Now, we prove that there are infinitely many Lucas-Carmichael integers
assuming the Prime $k$-tuples Conjecture (defined below).

The Prime $k$-tuples Conjecture. Let $a_{1},\ldots,a_{k}$ be positive integers
and let $b_{1},\ldots,b_{k}$ be nonzero integers. For $m\geq 1,$ define
$f(m)=\prod_{i=1}^{k}(a_{i}m+b_{i}).$ Let $P(x)$ denote the number of positive
integers $m\leq x$ for which $a_{i}m+b_{i}$ is prime for each $i=1,\ldots,k.$
The Prime $k$-tuples Conjecture, states that if no prime divides $f(m)$ for
every $m,$ then there exists $c>0$ such that
$P(x)\sim\frac{cx}{\text{log}^{k}x}$ as $x\rightarrow\infty.$

######  Theorem 4.1.

The Prime $k$-tuples Conjecture implies that there are infinitely many Lucas-
Carmichael integers of degree two with exactly three prime factors.

###### Proof.

By the Prime $k$-tuples Conjecture, there are infinitely many positive
integers $m$ for which $U_{3}^{\prime}(m)$ has exactly three prime factors. By
lemma $\ref{lemma0.7},$ each of these numbers $U_{3}^{\prime}(m)$ with $m\geq
5$ are secondary Lucas-Carmichael integer.

∎

######  Theorem 4.2.

Every Lucas-Carmichael integer $n$ with three prime factors is of the form
$(2hr_{1}-1)(2hr_{2}-1)(2hr_{3}-1),$ where $h$ is a positive integer and
$r_{i}^{\prime}$s are pairwise co-prime integers.

###### Proof.

Let $n=p_{1}p_{2}p_{3}$ be a Lucas-Carmichael integer with three prime
factors. Write $p_{i}=r_{i}k-1,$ where $k$ is the $g.c.d.$ of $p_{i}+1$ for
$i=1,2,3.$ Since $n$ is a Lucas-Carmichael integer, we have

$(r_{1}k-1)(r_{2}k-1)(r_{3}k-1)\equiv-1\pmod{p_{i}+1},$

for $i=1,2,3.$

This implies that,

$(r_{1}r_{2}r_{3})k^{3}-(r_{1}r_{2}+r_{1}r_{3}+r_{2}r_{3})k^{2}+(r_{1}+r_{2}+r_{3})k-1\equiv-1\pmod{r_{i}k}.$

By simplifying, we obtain

$-(r_{1}r_{2}+r_{1}r_{3}+r_{2}r_{3})k+(r_{1}+r_{2}+r_{3})\equiv
0\pmod{r_{i}}.$

For $1\leq i\neq j\leq 3$, if $r_{i}$ and $r_{j}$ has common factor, then the
third one does and it contradict our assumption. Hence the $r_{i}$’s are
pairwise co-prime. Suppose $k$ is an odd, then $r_{i}$’s are even as $p_{i}$’s
are odd. Since $k$ is the $g.c.d.$ of $p_{i}+1,$ this is not possible.
Therefore, $k$ must be even and the theorem follows. ∎

######  Theorem 4.3.

Let $F_{l}^{\prime}$ be a Lucas-Carmichael integer with exactly $l$-odd
integer of prime factors $p_{1},p_{2},\ldots p_{l}.$ Let $k_{1}$ be the
$g.c.f.$ of $p_{i}+1,$ and $r_{i}=\frac{p_{i}+1}{k_{1}}.$ Also, let $R$ be the
$l.c.m.$ of $r_{i},$ $i=1,2,\ldots,l.$ Then
$U_{n}^{\prime}(m)=\prod_{i=1}^{l}(r_{i}Rm+p_{i})$ satisfies the congruence
relation

$U_{n}^{\prime}(m)\equiv-1\pmod{r_{i}Rm+p_{i}+1}$

for $i=1,2,\ldots,l.$

###### Proof.

Since $F_{l}^{\prime}=\prod_{i=1}^{l}(r_{i}k_{1}-1)$ is a Lucas-Carmichael
integer and $l$ is odd, we have
$\prod_{i=1}^{l}(r_{i}k_{1}-1)\equiv-1\pmod{r_{i}k_{1}}$ for $i=1,2,\ldots,l.$

This implies that,

$\frac{\prod_{i=1}^{l}(r_{i}k_{1}-1)+1}{k_{1}}\equiv 0\pmod{r_{i}},$

for $i=1,2,\ldots,l.$

Therefore,

$\frac{\prod_{i=1}^{l}(r_{i}k_{1}-1)+1}{k_{1}}\equiv 0\pmod{R}$

We observe that any $k\equiv k_{1}\pmod{R}$ is also a solution for the above
congruence. Write $k=Rm+k_{1}$ and substitute this $k$ for $k_{1},$ we obtain

$\frac{\prod_{i=1}^{l}(r_{i}(Rm+k_{1})-1)+1}{k}\equiv 0\pmod{R}.$

Since $p_{i}=r_{i}k-1$ and $r_{i}k=r_{i}Rm+r_{i}k_{1}=r_{i}Rm+p_{i}+1,$ we
have

$\prod_{i=1}^{l}(r_{i}Rm+p_{i})+1\equiv 0\pmod{r_{i}k}$

and

$U_{n}^{\prime}(m)=\prod_{i=1}^{l}(r_{i}Rm+p_{i})\equiv-1\pmod{r_{i}Rm+p_{i}+1}$

for every $i$ ranges over $1$ to $l.$ ∎

######  Theorem 4.4.

Suppose that there exists a Lucas-Carmichael integer $F_{l}^{\prime}$ with
exactly $l$-odd prime factors, then there are infinitely many Lucas-Carmichael
integers with exactly $l$-odd number of prime factors assuming the Prime
$k$-tuples Conjecture.

###### Proof.

Let $F_{l}^{\prime}$ be a Lucas-Carmichael integer with exactly $l$-odd number
of prime factors $p_{1},p_{2},\ldots p_{l}.$ Then by theorem $(\ref{thm4.3}),$
we have $U_{n}^{\prime}(m)=\prod_{i=1}^{l}(r_{i}Rm+p_{i})$ that satisfies the
congruence relation

$U_{n}^{\prime}(m)\equiv-1\pmod{r_{i}Rm+p_{i}+1}$

for $i=1,2,\ldots,l.$ Therefore, the Prime $k$-tuples Conjecture implies that
there are infinitely many Lucas-Carmichael integers with exactly $l$ prime
factors. ∎

We illustrate the theorem with the example below.

######  Example 4.1.

Let $F_{5}^{\prime}=5\cdot 7\cdot 17\cdot 23\cdot 43$ be a Lucas-Carmichael
integer. We have $k_{1}=2,$ $r_{1}=3,r_{2}=4,r_{3}=9,r_{4}=12,r_{5}=22$ and
$R=396.$ Let $U_{5}^{\prime}(m)=pqrst,$ where $p=1188m+5,$ $q=1584m+7,$
$r=3564m+17,$ $s=4752m+23,$ $t=8712m+43$ and $U_{5}^{\prime}(m)=n=pqrst.$ Then
by theorem $\ref{thm4.3},$ we have
$U_{5}^{\prime}(m)\equiv-1\pmod{396r_{i}+p_{i}+1}$ for every $i=1,2,3,4,5.$

Finally, we consider Lucas-Carmichael integers with exactly five prime
factors.

######  Lemma 4.2.

Let $m$ be a positive integer, $p=1188m+5,$ $q=1584m+7,$ $r=3564m+17,$
$s=4752m+23,$ $t=8712m+43$ and $U_{5}^{\prime}(m)=n=pqrst.$ Then

$\displaystyle n+2$
$\displaystyle=117(p+2)^{5}+(396m-875)(p+2)^{4}+(1056m+2593)(p+2)^{3}$
$\displaystyle\quad+(660m-3771)(p+2)^{2}+(132m+2724)(p+2)+(132m-775)$
$\displaystyle n+2$
$\displaystyle=27(q+2)^{5}+\Bigg{(}\frac{2117016}{1584}m-224\Bigg{)}(q+2)^{4}+\Bigg{(}\frac{1724976}{1584}m+758\Bigg{)}(q+2)^{3}$
$\displaystyle\quad+\Bigg{(}\frac{2273832}{1584}m-1199\Bigg{)}(q+2)^{2}+(1287m+958)(q+2)+(1188m-287)$
$\displaystyle n+2$
$\displaystyle=\Bigg{(}\frac{6133248}{3564}m+3\Bigg{)}(r+2)^{4}+\Bigg{(}\frac{2317392}{3564}m+32\Bigg{)}(r+2)^{3}$
$\displaystyle\quad+\Bigg{(}\frac{574992}{3564}m-65\Bigg{)}(r+2)^{2}+\Bigg{(}\frac{4373424}{3564}m+78\Bigg{)}(r+2)$
$\displaystyle\quad+\Bigg{(}\frac{12005136}{3564}m-11\Bigg{)}$ $\displaystyle
n+2$
$\displaystyle=\Bigg{(}\frac{2587464}{4752}m+1\Bigg{)}(s+2)^{4}+\Bigg{(}\frac{3606768}{4752}m+13\Bigg{)}(s+2)^{3}$
$\displaystyle\quad+\Bigg{(}\frac{14662296}{4752}m-10\Bigg{)}(s+2)^{2}+(1023m+38)(s+2)+(4092m+7)$
$\displaystyle n+2$
$\displaystyle=\Bigg{(}\frac{419904}{8712}m\Bigg{)}(t+2)^{4}+\Bigg{(}\frac{9191232}{8712}m+6\Bigg{)}(t+2)^{3}$
$\displaystyle\quad+\Bigg{(}\frac{41885424}{8712}m+20\Bigg{)}(t+2)^{2}+\Bigg{(}\frac{31403376}{8712}m+26\Bigg{)}(t+2)$
$\displaystyle\quad+\Bigg{(}\frac{68897952}{8712}m+37\Bigg{)}.$

######  Corollary 4.2.

With the same hypotheses as Lemma $\ref{lemma0.8},$ with $8712$ $|$ $m.$ Then,
we have $S_{p+2}(n+2)=2p+3,$ $S_{q+2}(n+2)=4q+5,$ $S_{r+2}(n+2)=2r+3,$
$S_{s+2}(n+2)=2s+3$ and $S_{t+2}(n+2)=2t+3.$

######  Theorem 4.5.

The Prime $k$-tuples Conjecture implies that there are infinitely many Lucas-
Carmichael integers of degree $4$ with exactly five prime factors.

###### Proof.

By the Prime $k$-tuples Conjecture, there are infinitely many positive
integers $m$ for which $U_{5}^{\prime}(m)$ has exactly five prime factors. By
lemma $\ref{lemma0.8},$ each of these numbers $U_{5}^{\prime}(m)$are Lucas-
Carmichael integers of degree $4.$

∎

Acknowledgements. The second author would like to acknowledge support from AWS
braket and Meity QCAL. Also, the second author would like to acknowledge
support from ICTP through the associate programme.

## References

  * [1] Samuel S. Wagstaff, Jr. _Primary Carmichael Numbers_ , Integers: $22$ $(2022).$
  * [2] R. D. Carmichael, _Note on a new number theory function,_ Bull. Amer. Math.Soc. $16$ $(1910),$ $232$-$238.$
  * [3] R. D. Carmichael, _On composite numbers $P$ which satisfy the Fermat congruence $a^{P-1}\equiv 1\pmod{P},$_ Amer. Math. Monthly $19(1912),$ $22$-$27.$
  * [4] A. Korselt, _Problème chinois,_ L’Intermédiaire Math. $6(1899),$ $142$-$143.$
  * [5] W. R. Alford, A. Granville, and C. Pomerance, _There are infinitely many Carmichael numbers,_ Ann. of Math. $(2),$ $139(3)$ $(1994),$ $703$-$722.$
  * [6] B. C. Kellner and J. Sondow, _On Carmichael and polygonal numbers, Bernoulli polynomials, and sums of base-p digits,_ Integers $21$ $(2021),$ $\\#A52,$ $1$-$21.$
  * [7] Thomas Wright, _There are infinitely many elliptic Carmichael numbers_ , Bulletin of the London Mathematical Society, $50$ $(2018),$ $791$-$800.$
  * [8] D. M. Gordon, _Pseudoprimes on elliptic curves,_ Théorie des nombres (Quebec, PQ, $1987$), $(1989),$ $290$-$305.$
  * [9] A. Ekstrom, C. Pomerance and D. S. Thakur, _Infinitude of elliptic Carmichael numbers,_ J. Aust. Math. Soc. $92$ $(2012),$ $45$-$60.$


# Revisiting Image Classifier Training for
Improved Certified Robust Defense against Adversarial Patches

Aniruddha Saha1,, Shuhua Yu2,∗, Arash Norouzzadeh3, Wan-Yi Lin3, Chaithanya
Kumar Mummadi3
1 University of Maryland, College Park 2 Carnegie Mellon University 3 Bosch
Center for AI Equal contribution. Work done during internship at BCAI,
Pittsburgh.

###### Abstract

Certifiably robust defenses against adversarial patches for image classifiers
ensure correct prediction against any changes to a constrained neighborhood of
pixels. PatchCleanser [32], the state-of-the-art certified defense, uses a
double-masking strategy for robust classification. The success of this
strategy relies heavily on the model’s invariance to image pixel masking. In
this paper, we take a closer look at model training schemes to improve this
invariance. Instead of using Random Cutout [5] augmentations like
PatchCleanser, we introduce the notion of worst-case masking, i.e. selecting
masked images which maximize classification loss. However, finding worst-case
masks requires an exhaustive search, which might be prohibitively expensive to
do on-the-fly during training. To solve this problem, we propose a two-round
greedy masking strategy (Greedy Cutout) which finds an approximate worst-case
mask location with much less compute. We show that the models trained with our
Greedy Cutout improves certified robust accuracy over Random Cutout in
PatchCleanser across a range of datasets and architectures. Certified robust
accuracy on ImageNet with a ViT-B16-224 model increases from 58.1% to 62.3%
against a 3% square patch applied anywhere on the image.

Figure 1: Better invariance to pixel masking improves certified robustness to
adversarial patches: (a) An illustration of PatchCleanser [32] double masking
strategy. (b) Images are hard to classify when masks occlude objects of
interest. Top row: Certification is not possible when mask completely occludes
the object. Bottom row: Random Cutout failed to enable certification in cases
of partial occlusion, whereas our _Greedy Cutout_ succeeds. (c) _Greedy
Cutout_ improves PatchCleanser certification by a large margin. Certified
robust accuracy on ImageNet with a ViT-B16-224 model increases from 52.5% to
57.7% against a 3% square patch ( $\approx 39\times 39$) applied anywhere on
the image with ${\mathbf{M}}$$3\times 3$.

##  1 Introduction

Deep learning based image classifiers are vulnerable to adversarial patches
applied to the input [1, 7], where image pixels bounded within a confined
connected region, usually square or circular, can be adversarially crafted to
induce misclassification. Patch attacks are formulated in this way to mimic
printing and placing an adversarial object in the scene. It is easier to
realize a patch attack in the physical world compared to full image
adversarial perturbation, as the latter might need a compromise in the compute
system. Therefore, adversarial patch attacks pose a significant threat to
real-world computer vision systems.

Defenses against patch attacks fall into two categories: empirical and
certified defense. Empirical defenses [25, 9, 22] often utilize robust
training which incorporates adversarial inputs generated from specific attacks
to improve robustness. But they are susceptible to attacks unseen during
training. On the other hand, certified defenses guarantee correct predictions
against any adaptive white-box attacker under a given threat model. Hence, the
certified robust accuracy for is the guaranteed lower bound of the model
performance. Prior works [13, 15, 21, 32] acknowledge this strong robustness
property of certified defense and propose different certification procedures
to improve the certified robustness. Note that, we consider a single
adversarial square patch applied on an image in our threat model in this work.

PatchCleanser [32] is the state-of-the-art certified defense method against
patch attacks. Similar to other certified methods, it assumes the defense has
a conservative estimate of the patch size (e.g. $3\%$ pixels) and thereby
designs a mask set - masks with certain size placed at reserved spatial
locations on an image. Fig 1 shows a mask set ${\mathbf{M}}$$3\times 3$ of $9$
masks, each with size $100\times 100$, that are applied on $224\times 224$
image. This mask set is designed to ensure that an adversarial patch of an
estimated size (e.g. $3\%$ pixels - $39\times 39$ patch) will be covered and
therefore neutralized by at least one of the masks. The method proposes two
round pixel masking defense and certifies an image if predictions of all its
double-masked images agree with the ground truth. An image is certified if all
the two-masked $9^{2}=81$ combinations get correctly classified. More details
about this method can be found in Sec 3.3.

PatchCleanser shows that a classifier trained on two-masked (or double-masked)
images using random Cutout [5] augmentation improves certification accuracy.
At training time, a two-masked image is obtained by applying random Cutout
twice on a clean image (see Fig 4). During certification, we observe that some
of the two-masked images are hard to classify as the masks completely occlude
the object of interest beyond recognition as shown in Fig 1 (top row). It is
not possible to certify such images with the considered mask set. Besides, we
made a visual observation that random Cutout trained classifiers even
misclassify some two-masked images with preserved semantic clues, see bottom
row of Fig 1. Misclassification on such images result in underestimating
classifier’s certified robustness. We consider that random Cutout augmentation
is not fully effective or invariant towards pixel masking and limits
classifier potential to leverage the defense. This observation motivates our
work to explore the training schemes that improve invariance to pixel masking
and thereby enhance classifer’s certified robustness through PatchCleanser.

We revisit image classifier training strategy to particularly target the
classifier’s failure modes during PatchCleanser certification. The masks of
misclassified images during certification would serve as possible worst-case
masks i.e. masks that induce image misclassification. Instead of Random Cutout
augmentation, we propose to choose worst-case masked images with high
classification loss for training. The worst-case masks are chosen from the
mask set that are used during certification. Finding such worst-case masks
from mask set ${\mathbf{M}}$$3\times 3$ and ${\mathbf{M}}$$6\times 6$
exhaustively requires $9\times 9=81$ and $36\times 36=1296$ two-mask forward
passes respectively, which is prohibitively expensive to do on-the-fly during
training. To this end, we propose a simple but effective greedy masking
strategy called _Greedy Cutout_ to approximate the worst-case masks with
$42\%$ and $96\%$ less computation overhead than the grid search on
${\mathbf{M}}$$3\times 3$ and ${\mathbf{M}}$$6\times 6$ respectively. We
propose to train the image classifiers on the _Greedy Cutout_ images and
demonstrate that such masking strategy improves certified robustness across
different datasets as shown in Fig 1.

We summarize our contributions as follows: We observe that training the
classifier with standard Cutout augmentation is not entirely effective for all
two-masked images. Therefore, we take a closer look at the invariance of image
classifiers to pixel masking with an objective to improve PatchCleanser
certification. We propose a simple _Greedy Cutout_ strategy to train the
classifier with worst-case masked images. We compare with various other
masking strategies like Random Cutout [5], Cutout guided by certification
masks, Gutout (Cutout guided by Grad-CAM) [3], Cutout with exhaustive search
(refer Sec. 4) and show that our training strategy improves certified
robustness over other baselines across different datasets and architectures.

##  2 Related Work

#### Certified defenses against patch attack:

Certified defenses against adversarial patch for image classifiers provide
guaranteed robust accuracy lower bound. Because patch attack has maximum
strength within the patch region, certified defenses either ensembles from
local regions [13][26][15] or use models with small receptive field and
masking [21][31] to reduce global influence of the patches. Current state-of-
the-art PatchCleanser [32] combines masking and ensembling by aggregating
predictions of specifically-designed masked copies and shows significant
improvement over previous methods. Our work follows the certification and
inference procedure of PatchCleanser [32]. However, we show that worst-case
mask augmentation can improve invariance to pixel masking and consequently the
certified robust accuracy of PatchCleanser.

#### Augmentation for adversarial robustness:

Data augmentations help in training smooth and generalizable models, and are
used to train adversarially-robust classifiers. Adversarial training [18],
[24] which augments input with gradient given a model has been established as
one of the most powerful approach for training robust models. Studies have
also shown that adversarial training improves generalizability of models [33,
19]. Gradient-free augmentation has shown improvements in model robustness:
[8] utilizes unconditional generative models to generate an additional
training dataset, and [14] proposed padding before cropping (PadCrop) for
augmentation to reduce robust overfitting. Cutout [5], randomly masks out
square regions of input images during training to improve clean accuracy. We
propose a variation to random Cutout augmentation scheme in our paper to
improve certified robustness. [30] proposed an adversarial training framework
using rectangular adversarial patches to improve robustness to patch-based
evasion attacks. Our Greedy Cutout augmentation instead aims to improve
certified robustness.

##  3 Method

###  3.1 Patch attack formulation

This paper focuses on adversarially-robust image classification. We use
$\mathcal{X}\subset[0,1]^{W\times H\times C}$ to denote an image, where each
image has width $W$, height $H$, number of channels $C$, and pixel values in
$[0,1]$. We use ${\mathcal{Y}}$ to denote the label set, and
$\mathbb{F}:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ denotes the image
classification model. Note that we do not make any assumptions about its
architecture, and thus the method we present is compatible with any popular
architecture.

We consider patch attack, denoted by ${\mathcal{A}}$, that can arbitrarily
manipulate the pixels within a square region covering up to 3% of image area.
We use $\mathbf{r}\in\\{0,1\\}^{W\times H}$ to denote the aforementioned
square region, where pixels within the region is set to 0 while others are set
to 1. Since the region can be placed in any location of an image, we can
denote all such square regions covering less than 3% of an image as
${\mathcal{R}}$. Formally, for an image $\mathbf{x}$ with true label $y$, the
patch attack ${\mathcal{A}}$ can generate a set of images under attack, i.e.,
${\mathcal{A}}_{\mathcal{R}}(\mathbf{x})=\\{\mathbf{r}\odot\mathbf{x}+(1-\mathbf{r})\odot\mathbf{x}^{\prime}\mid\mathbf{x}^{\prime}\in{\mathcal{X}},r\in{\mathcal{R}}\\}$,
where $\odot$ represents pixel-wise multiplication. Patch attack aims to find
an image $\hat{\mathbf{x}}\in{\mathcal{A}}_{\mathcal{R}}(\mathbf{x})$ such
that $\mathbb{F}(\hat{\mathbf{x}})\neq y$.

###  3.2 Defense objectives

The goal of certifiable defense is to build a robust model $\mathbb{F}$ such
that for image label pair $(\mathbf{x},y)$, we have
$\forall\hat{\mathbf{x}}\in{\mathcal{A}}_{\mathcal{R}}(\mathbf{x}),\mathbb{F}(\hat{\mathbf{x}})=y$,
then such $\mathbf{x}$ is defined as a certified image and the fraction of
certified images in test data is defined as certified robust accuracy. The
process to determine whether an image-label pair $(\mathbf{x},y)$ can be
certified follows [32]. Certified robust accuracy provides a lower bound on
model’s classification accuracy under patch attack.

On the other hand, we want to avoid deteriorated performance over clean data
free of patch attacks. Thus, the other metric we wish to maintain is the
fraction of image label pair $(\mathbf{x},y)$ satisfying
$\mathbb{F}(\mathbf{x})=y$ over test data, which we call clean accuracy.
Computing clean accuracy requires inference process sweeping over test data.

###  3.3 PatchCleanser

In this paper, we follow the inference and certification procedures of
PatchCleanser [32]. PatchCleanser achieves certified defense via double-
masking strategy. A mask $\mathbf{m}\in\\{0,1\\}^{W\times H}$ is defined as a
binary image with the same dimension as images in $\mathcal{X}$ where pixels
within the mask take value 0, and the rest take value 1, and thus a masked
image $\mathbf{x}\odot\mathbf{m}$ will exhibit an artificially occluded region
within the mask while other pixels remains unaffected. PatchCleanser crafts a
well-designed set of masks ${\mathbf{M}}$ and provides a provable
certification procure based on predicted classes over the set of masked images
$\\{\mathbf{x}\odot\mathbf{m}\mid\mathbf{m}\in{\mathbf{M}}\\}$.

PatchCleanser designs the mask set $\mathbf{M}$ satisfying
${\mathcal{R}}$-covering property, i.e., for any adversarial patch, there
exists at least one mask $\mathbf{m}\in\mathbf{M}$ would completely cover the
adversarial patch. Formally,
$\forall\mathbf{r}\in{\mathcal{R}},\exists\mathbf{m}\in{\mathbf{M}},\text{
s.t. }\mathbf{m}[i,j]\leq\mathbf{r}[i,j],\forall i,j$. PatchCleanser proves
that if an image label pair
$(\mathbf{x},y)\in{\mathcal{X}}\times{\mathcal{Y}}$ satisfies that
$\forall\mathbf{m}_{1},\mathbf{m}_{2}\in{\mathbf{M}}\times{\mathbf{M}},\mathbb{F}\big{(}\mathbf{x}\odot\mathbf{m}_{1}\odot\mathbf{m}_{2}\big{)}=y$,
then $(\mathbf{x},y)$ is certified. Therefore, improving the certified robust
accuracy reduces to maintain high classification accuracy for $\mathbb{F}$ on
masked images
$\mathbf{x}\odot\mathbf{m}_{1}\odot\mathbf{m}_{2},\mathbf{m}_{1},\mathbf{m}_{2}\in{\mathbf{M}}\times{\mathbf{M}}$.
To this end, PatchCleanser employs Cutout data augmentation [5] to finetune
model $\mathbb{F}$.

For inference, PatchCleanser first obtains all one-mask predictions
$\mathbb{F}(\mathbf{x}\odot\mathbf{m})$, $\forall\mathbf{m}\in\mathbf{M}$. If
the image $\mathbf{x}$ has no adversarial patch, then all one-mask predictions
should be the same as $\mathbb{F}(\mathbf{x})$, in this case it outputs the
agreed prediction as the predicted class for $\mathbf{x}$. If $\mathbf{x}$
contains an adversarial patch, since one of the one-masked copy does not have
visible adversarial patch, then at least one one-mask prediction should be
different from the rest. For each disagreed (minority) prediction with the
corresponding single-masked copy, this copy is further masked with the second-
round mask set and all two-masked copies are classified with $\mathbb{F}$. If
the single-masked copy has fully masked the adversarial patch, then all its
two-masked copies also fully masked the adversarial patch, then the
predictions of two-masked copies should be $\mathbb{F}(\mathbf{x})$. If none
or more than one disagreed case have unanimous two-masked predictions, then
none of the classes should be trusted, and the majority predicted class of the
single-masked copies is the predicted class of $\mathbf{x}$. Example masked
copies can be found in Figure 1. PatchCleanser shows that if an image-label
pair $(\mathbf{x},y)$ is certified, the above inference procedure will always
output the correct label $y$.

Figure 2: Illustration of two-round _Greedy Cutout_ masking: Each round
applies masks from the same mask set ${\mathbf{M}}$$k\times k$ ($k=3$ or $6$),
making the number of forward passes for both rounds to $(9\times 2)-1=17$ and
$(36\times 2)-1=71$ when $k=3$ and $6$ respectively, to find the masked image
with highest classification loss. The two-masked image $\mathbf{M}_{2}$
obtained from Round 2 is used for training the classifier.

###  3.4 Greedy Cutout

Recall that to raise the certified robust accuracy, the classifier
$\mathbb{F}$ should be fine-tuned to double-masked images
$\big{\\{}\mathbf{x}\odot\mathbf{m}_{1}\odot\mathbf{m}_{2}\mid\mathbf{m}_{1},\mathbf{m}_{2}\in{\mathbf{M}}\times{\mathbf{M}}\big{\\}}$
so it is less sensitive to presence of $\mathbf{m}\in{\mathbf{M}}$. For this
purpose, we resort to augmented training data with $(\mathbf{x}^{\prime},y)$
where $\mathbf{x}^{\prime}$ is obtain from applying masks or combination of
masks on $\mathbf{x}$. PatchCleanser uses Random Cutout augmentation [5],
i.e., applying two masks of size $128\times 128$ at random locations to
$224\times 224$ training images. In this work, we develop a systematic
approach to find $\mathbf{x}^{\prime}$ that are more empirically effective.
The main strategy is to use several inference rounds to identify worst-case
masks that lead to highest losses, then we apply these worst-case masks to
$\mathbf{x}$ to obtain augmented data point $(\mathbf{x}^{\prime},y)$ for
training.

Image and mask preparations: For datasets of high-resolution images such as
ImageNet and ImageNette, we resize and crop them to $224\times 224$ before
feeding them into model $\mathbb{F}$. For datasets with images with low-
resolution such as CIFAR-10, we resize them to 224×224 via bicubic
interpolation for a better classification performance. In this work, we
generate sets of masks following PatchCleanser[32]. Concretely, we use two
mask sets $\mathbf{M}_{3\times 3}$ and $\mathbf{M}_{6\times 6}$ (see the
leftmost part of Figure 2 for an illustration, where light gray blocks
represent image area and deep gray smaller blocks represent masks) that both
satisfy ${\mathcal{R}}$-covering property: $\mathbf{M}_{3\times 3}$ is a set
of $3\times 3$ masks with 9 masks in total, and each mask is of size
$100\times 100$; $\mathbf{M}_{6\times 6}$ is a set of $6\times 6$ masks with
36 masks, and every mask is in shape of $69\times 69$. Note that, due to the
careful choice of $\mathbf{M}_{3\times 3}$ and $\mathbf{M}_{6\times 6}$, each
mask in $\mathbf{M}_{3\times 3}$ can be fully covered by 4 masks in
$\mathbf{M}_{6\times 6}$. Empirically, $\mathbf{M}_{6\times 6}$ leads to
higher certified robust accuracy since two smaller masks have a smaller effect
on the prediction on $\mathbb{F}$ than the larger ones. However,
$\mathbf{M}_{6\times 6}$ has $\approx$ 8 times larger size than
$\mathbf{M}_{3\times 3}$ that requires more computation in both inference and
certification. Striking a delicate trade-off between computational cost and
accuracy is the core of our method.

Figure 3: Illustration of our multi-size two-round _Greedy Cutout_ masking:
Each round begins with applying larger masks from ${\mathbf{M}}$$3\times 3$
with $9$ forward passes, which narrow downs the search area for the smaller
masks from ${\mathbf{M}}$$6\times 6$ to just $4$ forward passes. With a total
of 25 unique forward passes, the approximated worst-case masked images
$\mathbf{M}_{2}$ and $\mathbf{M}_{22}$ from ${\mathbf{M}}$$3\times 3$ and
${\mathbf{M}}$$6\times 6$ are jointly used for training.

Greedy Cutout: We present a baseline version of Greedy Cutout (See Figure 2
for an illustration). We first define the prediction loss of $\mathbb{F}$ on
image label pair $(\mathbf{x},y)$. Suppose within the model of $\mathbb{F}$,
for each label $y^{\prime}\in{\mathcal{Y}}$, the confidence level for
$\mathbb{F}$ to predict $y^{\prime}$ is $p_{y^{\prime}}$, then we use the
cross entropy loss
$\ell(\mathbb{F}(\mathbf{x},y))=-\sum_{y\in{\mathcal{Y}}}c_{y^{\prime}}\log
p_{y^{\prime}}$, where $c_{y^{\prime}}=1$ for $y^{\prime}=y$ otherwise
$c_{y^{\prime}}=0$. For mask set $\mathbf{M}_{k\times k}(k=3\text{ or }k=6)$,
we could identify the worst-case mask combination
$\mathbf{m}_{1},\mathbf{m}_{2}\in\mathbf{M}_{k\times
k}\times\mathbf{M}_{k\times k}$ that incurs the largest loss
$\ell(\mathbb{F}(\mathbf{x}\odot\mathbf{m}_{1}\odot\mathbf{m}_{2},y)$ with
grid search, but inferencing over all ${k^{2}\choose 2}$ \+ $k^{2}$ ($45$ when
$k=3$, and $666$ when $k=6$) unique combinations would be computationally
prohibitive, thus motivating the Greedy Cutout strategy.

By Greedy Cutout, we find the worst-case mask in each individual masking
round. In the first round of, for each $\mathbf{m}_{1}\in\mathbf{M}_{k\times
k}$, we compute the loss $\ell(\mathbb{F}(\mathbf{x}\odot\mathbf{m}_{1}),y)$,
and denote the mask incurring the highest loss as $\mathbf{m}_{1}^{*}$. Then,
in the second round, for each $\mathbf{m}_{2}\in\mathbf{M}_{k\times
k},\mathbf{m}_{2}\neq\mathbf{m}_{1}$, we compute the loss
$\ell(\mathbb{F}(\mathbf{x}\odot\mathbf{m}_{1}^{*}\odot\mathbf{m}_{2}),y)$,
and find the $\mathbf{m}_{2}^{*}$ with the highest loss. Then, we empirically
use $\mathbf{M}_{2}:=\mathbf{m}_{1}^{*}\odot\mathbf{m}_{2}^{*}$ as the worst-
case mask combination. Although $\mathbf{M}_{2}$ may not be the exact worst-
case mask, $(\mathbf{x}\odot\mathbf{M}_{2},y)$ still provides a guidance for
fine-tuning. More importantly, with Greedy Cutout, we significantly reduce the
inference burden down to $2k^{2}-1(17,k=3;71,k=6)$ compared to grid search.
However, for $k=6$, this computation cost is still high but this mask set has
better accuracy over $\mathbf{M}_{3\times 3}$. We then further develop Multi-
size Greedy Cutout (See Fig 3) that benefits from the high accuracy of
$\mathbf{M}_{6\times 6}$ while keeping computation cost comparable with Greedy
Cutout with $\mathbf{M}_{3\times 3}$.

Multi-size Greedy Cutout: Round 1 - Given clean image $\mathbf{x}$, we first
apply each mask in $\mathbf{M}_{3\times 3}$ and inference on each image in
$\\{\mathbf{x}\odot\mathbf{m}\mid\mathbf{m}\in\mathbf{M}_{3\times 3}\\}$. We
then find the mask that incurs highest loss
$\ell(\mathbb{F}(\mathbf{x}\odot\mathbf{m}),y)$, and denote this mask as
$\mathbf{M}_{1}$. Then, we find the collection of 4 masks in
$\mathbf{M}_{6\times 6}$ that fully covers $\mathbf{M}_{1}$. We apply the
previous 4 masks from $\mathbf{M}_{6\times 6}$ on clean image $\mathbf{x}$ and
inference each masked image, then we store the mask incurs highest loss among
the four, denote this mask as $\mathbf{M}_{11}$.

Multi-size Greedy Cutout: Round 2 - We apply each
$\mathbf{m}\in\mathbf{M}_{3\times 3}$ on $\mathbf{x}\odot\mathbf{M}_{11}$, and
find the $\mathbf{m}_{3}^{*}$ that incurs largest highest loss among the 9
masks. Then we output our first mask
$\mathbf{M}_{2}=\mathbf{M}_{1}\odot\mathbf{m}_{3}^{*}$. For
$\mathbf{m}_{3}^{*}$, we identify the 4 masks from $\mathbf{M}_{6\times 6}$
that fully covers $\mathbf{m}_{3}^{*}$, and apply the 4 masks on
$\mathbf{x}\odot\mathbf{M}_{11}$ to find $\mathbf{m}_{6}^{*}$ that incurs
highest loss. We output the second mask
$\mathbf{M}_{22}=\mathbf{M}_{11}\odot\mathbf{m}_{6}^{*}$.

From the previous two rounds, we identify two worst-case masks
$\mathbf{M}_{2}$ and $\mathbf{M}_{22}$. We only use in total $9+4=13$
inferences in each round so only 26 inferences in total. In our experiments,
we show that this strategy uses similar amount of computation with baseline
Greedy Cutout for $k=3$, but achieves comparable performance of baseline
Greedy Cutout for $k=6$. We provide the pseudocode in the Algorithm 1 in the
appendix, where two procedures Round-1 and Round-2 echo the round 1 and round
2 described above. Running Algorithm 1 with input
$(\mathbf{x},\mathbb{F},\mathbf{M}_{3\times 3},\mathbf{M}_{6\times 6})$ will
lead to desired augmented data points $(\mathbf{x}_{1}^{\prime},y)$ and
$(\mathbf{x}_{2}^{\prime},y)$ that can be used for fine-tuning the vanilla
model $\mathbb{F}$.

##  4 Experiments

In this section, we describe our experimental setup, masking strategies and
present the results. We use five popular image classification datasets:
ImageNet[4], ImageNette[11], CIFAR-10[12], CIFAR-100[12], SVHN[23] and image
classifiers from three different architecture families: ResNet[10], ViT[6],
ConvNeXt[17]. In particular, ResNetV2-50x1, ViT-B16-224 and
ConvNeXt_tiny_in22ft1k pretrained models from timm library [28]. We finetune
these pretrained models on different datasets using the proposed masking
stratgies for 10 epochs with SGD optimizer at learning rate 0.01 for ResNet
and 0.001 for ViT, ConvNeXt and reduce the learning rate by a factor of 10
after 5 epochs. Images from all the datasets are resized to $224\times 224$.
We use batch size 128 for ImageNet and 64 for other datasets.

Figure 4: Illustration of different masking strategies: We explore various
strategies to improve the invariance of models towards pixel masking.

Adversarial patches: As in prior work [32, 2, 13, 20, 31], we report certified
defense accuracy for square patches covering 1%, 2% and 3% of the input image
for ImageNet, ImagNette and 0.4%, 2.4% for CIFAR-10, CIFAR-100, and SVHN. We
allow patch perturbations to be unbounded (within image range) and consider a
single square patch placed at any random location in the image.

Evaluation metrics: We report two metrics: clean accuracy - amount of clean
test images classified correctly by the PatchCleanser defense and certified
robust accuracy - amount of test images pass through certification process
i.e. a guaranteed lower bound on classifier robustness.

###  4.1 Improving invariance to pixel masking

The core idea of PatchCleanser[32] is to mask image pixels to occlude and
neutralize the adversarial patch. We visually observe that two masks that
completely occlude the object make images harder to certify (see Fig. 1).
However, masked images with partial occlusions and preserved semantic cues
stand a chance to get classified correctly. Hence, a crucial property that
governs the success of certification is the classifier’s _prediction
invariance to pixel masking_. Below we explain different train time masking
strategies that we investigate towards improving pixel masking invariance.

#### Random Cutout in PatchCleanser (PC-Cutout)

Random Cutout[5] to apply 2 masks of size $128\times 128$ at random locations
on a $224\times 224$ image during training (see Fig. 4). Here, masks may be
located partially beyond the image boundary. It is shown that the such Cutout
augmentation improves certification over vanilla classifiers. We hypothesize
that such Cutout strategy might not be fully effective to induce mask
invariance and propose further improvement.

#### Random Cutout with certification masks

Following random Cutout[5], we investigate whether training the classifier
with Cutout masks from certification mask sets improve robustness. We apply
two masks on the image that are randomly sampled from the either of the mask
sets ${\mathbf{M}}$$3\times 3$ or ${\mathbf{M}}$$6\times 6$ during training
(see Fig. 4). We refer _rand $3\times 3$_ as the masking strategy that trains
on mask set ${\mathbf{M}}$$3\times 3$, _rand $6\times 6$_ when using
${\mathbf{M}}$$6\times 6$. We further use masked images sampled from both the
mask sets jointly during training, that doubles the batch size and we refer it
as _rand_. The reason for our specific choice of mask sets will become clear
when discussing our _Greedy Cutout_ below.

Table 1: Clean and certified robust accuracy across different datasets:
Underlined and bold numbers represent highest robust accuracy obtained for an
architecture & across different architectures respectively. Results on
CIFAR-100 & SVHN can be found in Table 2.

Dataset | ImageNette | ImageNet | CIFAR-10
---|---|---|---
Patch size | 1% pixels | 2% pixels | 3% pixels | 1% pixels | 2% pixels | 3% pixels | 0.4% pixels | 2.4% pixels
Accuracy (%) | clean | robust | clean | robust | clean | robust | clean | robust | clean | robust | clean | robust | clean | robust | clean | robust
IBP [2] | - | - | - | - | - | - | - | - | - | - | - | - | 65.8 | 51.9 | 47.8 | 30.8
CBN [34] | 94.9 | 74.6 | 94.9 | 60.9 | 94.9 | 45.9 | 49.5 | 13.4 | 49.5 | 7.1 | 49.5 | 3.1 | 84.2 | 44.2 | 84.2 | 9.3
DS [13] | 92.1 | 82.3 | 92.1 | 79.1 | 92.1 | 75.7 | 44.4 | 17.7 | 44.4 | 14.0 | 44.4 | 11.2 | 83.9 | 68.9 | 83.9 | 56.2
PG-BN [31] | 95.2 | 89.0 | 95.0 | 86.7 | 94.8 | 83.0 | 55.1 | 32.3 | 54.6 | 26.0 | 54.1 | 19.7 | 84.5 | 63.8 | 83.9 | 47.3
PG-DS [31] | 92.3 | 83.1 | 92.1 | 79.9 | 92.1 | 76.8 | 44.1 | 19.7 | 43.6 | 15.7 | 43.0 | 12.5 | 84.7 | 69.2 | 84.6 | 57.7
BagCert [20] | – | – | – | – | – | – | 45.3 | 27.8 | 45.3 | 22.7 | 45.3 | 18.0 | 86.0 | 72.9 | 86.0 | 60.0
ViT-B [26] | – | – | – | – | – | – | 73.2 | 43.0 | 73.2 | 38.2 | 73.2 | 34.1 | 90.8 | 78.1 | 90.8 | 67.6
Certification with mask set ${\mathbf{M}}$$3\times 3$
PC-ResNet [32] | 99.3 | 94.0 | 99.4 | 92.8 | 99.2 | 91.6 | 80.9 | 52.3 | 80.9 | 48.7 | 80.8 | 45.8 | 97.3 | 81.3 | 96.9 | 73.0
ResNetrand | 99.1 | 94.2 | 99.2 | 92.5 | 99.2 | 91.3 | 81.2 | 51.2 | 81.2 | 47.1 | 81.0 | 45.1 | 97.5 | 80.1 | 96.8 | 71.0
ResNetgreedy (Ours) | 99.4 | 95.5 | 99.3 | 94.5 | 99.2 | 93.7 | 80.5 | 56.4 | 80.3 | 52.8 | 80.1 | 51.2 | 97.4 | 85.5 | 96.7 | 79.2
PC-ViT [32] | 99.4 | 96.2 | 99.4 | 95.1 | 99.4 | 94.0 | 82.8 | 58.5 | 82.5 | 55.2 | 82.4 | 52.5 | 98.5 | 89.0 | 98.0 | 83.5
ViTrand | 99.5 | 96.5 | 99.5 | 95.4 | 99.5 | 94.7 | 82.8 | 57.2 | 82.7 | 54.8 | 82.7 | 52.7 | 98.5 | 89.0 | 98.0 | 83.1
ViTgreedy (Ours) | 99.4 | 96.9 | 99.4 | 96.0 | 99.4 | 95.5 | 81.2 | 59.5 | 81.2 | 58.7 | 81.1 | 57.7 | 98.5 | 91.5 | 98.2 | 87.5
PC-ConvNeXt [32] | 99.5 | 96.1 | 99.5 | 95.1 | 99.3 | 94.4 | 81.6 | 55.6 | 81.5 | 52.5 | 81.6 | 49.8 | 97.9 | 85.0 | 97.4 | 77.9
ConvNeXtrand | 99.4 | 95.8 | 99.4 | 94.9 | 99.3 | 94.5 | 81.7 | 55.2 | 81.7 | 51.7 | 81.6 | 49.2 | 97.9 | 84.6 | 97.6 | 76.9
ConvNeXtgreedy (Ours) | 99.5 | 96.5 | 99.4 | 95.9 | 99.4 | 95.4 | 80.5 | 59.1 | 80.4 | 56.0 | 80.2 | 53.6 | 97.7 | 88.5 | 97.4 | 82.7
Certification with mask set ${\mathbf{M}}$$6\times 6$
PC-ResNet [32] | 99.7 | 96.6 | 99.6 | 95.2 | 99.4 | 93.9 | 81.3 | 59.2 | 81.2 | 54.3 | 81.1 | 50.9 | 97.7 | 86.1 | 97.5 | 77.8
ResNetrand | 99.7 | 96.5 | 99.5 | 95.0 | 99.4 | 93.8 | 81.6 | 58.6 | 81.6 | 53.1 | 81.5 | 50.3 | 97.9 | 86.8 | 97.6 | 77.1
ResNetgreedy (Ours) | 99.6 | 97.8 | 99.5 | 96.4 | 99.4 | 95.6 | 81.0 | 63.9 | 80.9 | 58.9 | 80.8 | 56.6 | 97.7 | 90.8 | 97.5 | 84.3
PC-ViT [32] | 99.7 | 97.9 | 99.6 | 97.0 | 99.6 | 96.6 | 83.4 | 65.2 | 83.2 | 61.2 | 83.1 | 58.1 | 98.8 | 93.4 | 98.6 | 87.9
ViTrand | 99.8 | 97.9 | 99.8 | 96.9 | 99.7 | 96.4 | 83.4 | 64.0 | 83.4 | 60.5 | 83.3 | 58.3 | 98.9 | 94.1 | 98.7 | 88.4
ViTgreedy (Ours) | 99.6 | 98.5 | 99.6 | 97.9 | 99.5 | 97.3 | 82.0 | 65.6 | 82.0 | 63.1 | 82.0 | 62.3 | 99.0 | 95.3 | 98.8 | 92.0
PC-ConvNeXt [32] | 99.8 | 98.3 | 99.8 | 97.3 | 99.7 | 96.5 | 82.1 | 63.1 | 82.2 | 58.3 | 82.1 | 55.0 | 98.2 | 90.7 | 98.0 | 82.8
ConvNeXtrand | 99.7 | 98.2 | 99.8 | 96.9 | 99.6 | 96.4 | 82.3 | 62.7 | 82.3 | 57.1 | 82.2 | 54.5 | 98.3 | 90.3 | 98.2 | 81.9
ConvNeXtgreedy (Ours) | 99.7 | 98.7 | 99.7 | 97.9 | 99.6 | 97.4 | 81.3 | 66.5 | 81.1 | 61.8 | 81.0 | 59.4 | 98.1 | 93.3 | 97.8 | 87.3
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

#### Gutout: Cutout guided by Grad-CAM

Instead of random Cutout, we examine the effectiveness of classifier training
on saliency guided Cutout. We use image explanation heatmaps from literature
to guide this process. Specifically, we use Grad-CAM [27] to find the most
salient region of the image and selectively mask out the region using
certification mask sets ${\mathbf{M}}$$3\times 3$ or ${\mathbf{M}}$$6\times 6$
in a two-round fashion (see Fig. 4 for illustration). We refer the masking
strategies as _gutout $3\times 3$_, _gutout $6\times 6$_ and _gutout_ when
training on the mask sets ${\mathbf{M}}$$3\times 3$, ${\mathbf{M}}$$6\times
6$, and both the mask sets. Such augmentation strategy was proposed in [3] and
we take inspiration from their implementation.

Table 2: Extension of Table 1: Clean and robust accuracy on CIFAR-100 and SVHN. Dataset | CIFAR-100 | SVHN
---|---|---
Patch size | 2.4% pixels | 2.4% pixels
Accuracy (%) | clean | robust | clean | robust
Certification with mask set ${\mathbf{M}}$$3\times 3$
PC-ResNet | 86.8 | 45.9 | 93.8 | 43.4
ResNetgreedy | 85.8 | 53.9 | 93.4 | 54.5
PC-ViT | 91.4 | 61.5 | 95.9 | 52.9
ViTgreedy | 90.9 | 66.0 | 95.8 | 63.3
Certification with mask set ${\mathbf{M}}$$6\times 6$
PC-ResNet | 87.6 | 52.6 | 95.2 | 55.5
ResNetgreedy | 86.7 | 61.0 | 95.3 | 67.5
PC-ViT | 92.4 | 69.1 | 97.2 | 67.5
ViTgreedy | 92.1 | 74.5 | 97.1 | 76.8
Table 3: Comparing certified robust accuracy of masking strategies at two
different mask set configurations ${\mathbf{M}}$$3\times 3$ and
${\mathbf{M}}$$6\times 6$ across different datasets: Certification pixels used
3% for ImageNette and ImageNet, and 2.4% for CIFAR-10, CIFAR-100 and SVHN.

| Method | #passes | Mask set ${\mathbf{M}}$$3\times 3$ | Mask set ${\mathbf{M}}$$6\times 6$
---|---|---|---|---
| ImageNette | ImageNet | CIFAR-10 | CIFAR-100 | SVHN | ImageNette | ImageNet | CIFAR-10 | CIFAR-100 | SVHN
ResNet | rand$3\times 3$ | 0 | 90.8 | 45.2 | 72.0 | 44.4 | 43.2 | 93.4 | 49.1 | 77.4 | 52.0 | 55.7
rand$6\times 6$ | 0 | 89.1 | 42.5 | 65.5 | 39.1 | 33.9 | 92.7 | 49.0 | 73.8 | 48.9 | 50.4
rand | 0 | 91.3 | 45.1 | 71.0 | 43.7 | 42.8 | 93.8 | 50.3 | 77.1 | 51.6 | 56.7
gutout$3\times 3$ | 4 | 92.2 | 47.0 | 74.4 | 48.4 | 40.1 | 94.0 | 50.5 | 79.1 | 55.1 | 54.4
gutout$6\times 6$ | 92.0 | 44.3 | 70.3 | 42.9 | 36.3 | 94.1 | 49.3 | 76.2 | 51.7 | 49.5
gutout | 92.3 | 46.9 | 75.1 | 48.1 | 42.9 | 94.3 | 51.1 | 79.6 | 55.0 | 55.8
| greedy$3\times 3$ | 17 | 93.4 | 51.6 | 79.4 | 54.1 | 53.4 | 95.4 | 55.0 | 84.1 | 60.2 | 64.1
| greedy$6\times 6$ | 71 | 93.5 | 50.0 | 78.5 | 52.0 | 52.7 | 95.6 | 57.6 | 84.9 | 61.8 | 69.5
| greedy (Ours) | 26 | 93.7 | 51.2 | 79.2 | 53.9 | 54.5 | 95.6 | 56.6 | 84.3 | 61.0 | 67.5
| grid$3\times 3$ | 45 | 93.7 | 51.6 | 79.7 | 54.2 | 52.8 | 95.7 | 54.9 | 84.0 | 60.1 | 62.6
| grid$6\times 6$ | 666 | 93.2 | - | 78.8 | 52.5 | 53.5 | 95.6 | - | 85.1 | 62.5 | 69.3
|  |  |  |  |  |  |  |  |  |  |  |

#### Cutout guided by exhaustive search

Besides occluding the image region, these masks introduce artifacts on the
image with long edges. The position of such artifacts interweaved with the
image content influence classifier predictions. Therefore, we hypothesize that
the two-masked images obtained from the saliency guided Cutout may not serve
as better training examples for the classifier to improve pixel masking
invariance. To this end, we sweep through the entire search area by evaluating
classifier performance on all possible two-masked image combinations from mask
sets ${\mathbf{M}}$$3\times 3$ or ${\mathbf{M}}$$6\times 6$ and find the
_worst-case masks_ that result in highest classification loss. We train
classifiers on the _worst-case masked images_ and refer this masking strategy
as _grid $3\times 3$_ and _grid $6\times 6$_ with with masks set
${\mathbf{M}}$$3\times 3$ or ${\mathbf{M}}$$6\times 6$ respectively. We
believe that this approach is close to an upper bound on the best masking
strategy. The downside is that it requires classifier evaluation on large
number of all possible two-masked images, $45$ unique two-masked images among
$9^{2}=81$ in ${\mathbf{M}}$$3\times 3$ and $666$ among $36^{2}=1296$ in
${\mathbf{M}}$$6\times 6$, thus makes this strategy computationally expensive.

#### Greedy Cutout (ours)

As mentioned above, the compute requirement of an exhaustive search for the
_worst-case masked images_ might be prohibitive to train the classifiers. On
the other hand, light weight masking strategy like random Cutout or a
heuristic like Gutout might not be fully effective for our objective. Our
proposed masking strategy _Greedy Cutout_ (Sec. 3.4) approximates the _worst-
case masked images_ with much less computation overhead, bringing the best of
both worlds. We propose to train the classifiers with the _worst-case masked
images_ obtained from this masking strategy. We refer the masking strategy of
our baseline version of _Greedy Cutout_ as _greedy $3\times 3$_ and _greedy
$6\times 6$_ with masks set ${\mathbf{M}}$$3\times 3$ or
${\mathbf{M}}$$6\times 6$ respectively. Note that _greedy $6\times 6$_
requires 71 classifier evaluations to find the worst-case masks, which is
still high in computation. We address this issue with our other variant of
greedy masking called _Multi-size Greedy Cutout_. As mentioned in Sec. 3.4,
this variant decomposes the larger mask $100\times 100$ mask from
${\mathbf{M}}$$3\times 3$ neatly into four $69\times 69$ masks belonging to
${\mathbf{M}}$$6\times 6$. Henceforth, this variant approximates the worst-
case masks from ${\mathbf{M}}$$6\times 6$ in just 26 classifier evaluations
which is $2.7\times$ faster than the former approach. We refer the masking
strategy from _Multi-size Greedy Cutout_ as _greedy_. The neat decomposition
of masks from ${\mathbf{M}}$$3\times 3$ to ${\mathbf{M}}$$6\times 6$ allow us
to use these two mask sets in our approach and therefore we adapt the same
masks sets in the above masking strategies for fair comparison.

Figure 5: Evaluation of ViT-B16-224 model by varying mask set size during
certification process across different datasets: Classifier trained with mask
set ${\mathbf{M}}$$3\times 3$ and ${\mathbf{M}}$$6\times 6$ in our _Greedy
Cutout_ provides improvements over unseen mask sets ${\mathbf{M}}$$4\times 4$
and ${\mathbf{M}}$$5\times 5$.

###  4.2 Results

We report our main results in Table 1 and compare the performance of our
method with various prior works.

Significant improvements in certified robust accuracy: PatchCleanser [32] is
the state-of-the-art method for certification against adversarial patches. It
has been shown that it improves certification performance compared to previous
methods [2, 34, 13, 31, 20] by a large margin. Table 1 shows that our proposed
_Multi-size Greedy Cutout_ masking strategy improves robust accuracy over the
PatchCleanser Random Cutout baseline across all three classifiers (ResNet,
ViT, ConvNeXt) and datasets (ImageNette, ImageNet, CIFAR-10), thus setting new
state-of-the-art certified robustness results. The performance gap is
noticeably increasing with increased certification pixels. Notably, certified
robust accuracy on ImageNet with a ViT-B16-224 model increases from 52.5% to
57.7% against a 3% square patch applied anywhere on the image (mask set size
of $3^{2}=9$). We also see large improvements for ImageNette and CIFAR-10
datasets. In Table 2, we see that certified robust accuracy on CIFAR-100 with
a ViT-B16-224 model increases from 69.1% to 74.5% against a 2.4% square patch
applied anywhere on the image (mask set size of $6^{2}=36$).

Performance of different masking strategies: Table 3 compares the performance
of different masking strategies discussed in Sec. 4.1:

We observe that _Greedy Cutout_ performs better than _Random Cutout with
certificaiton masks_ and also _Gutout_. Moreover, it is comparable with the
expensive _Grid search_. For example, Certified robust accuracy for _Multi-
size Greedy Cutout_ on ImageNet with a ResNetV2-50x1 model is 51.2% against a
3% square patch applied anywhere on the image (mask set size of $3^{2}=9$).
This is better than _Random Cutout_ at 45.1% and _Gutout_ at 46.9%. _Grid
search_ is slightly higher at 51.6%. Results for ViT model are provided in
Table A1 in the appendix.

Tradeoff between defense performance and compute time (_Multi-size Greedy
Cutout_): We also compare the number of extra forward passes needed during
training for each method. We see that the _Greedy Cutout_ requires lesser
compute than _Grid seach_ , e.g. 71 unique forward passes compared to 666 for
a $6\times 6$ mask set, but achieves comparable robust accuracy (Table 3).
Also, our _Multi-size Greedy Cutout_ is an efficient strategy to reduce
forward passes from 71 to only 26 but still achieve competitive certification
performance with a mask set of $6\times 6$.

We also plot the robust accuracy against certification mask set size in Fig 5.
We observe that robust accuracy increases when mask set size increases along
with number of forward passes. We can benefit from our _Multi-size Greedy
Cutout_ when mask set size increases during inference.

##  5 Conclusion

PatchCleanser [32] certification requires all the double masked image
combinations to be correctly classified for an image to be certified against
adversarial patches. An image classifier should be invariant to pixel masking
to leverage such a certification process. PatchCleanser trains models with
Random Cutout augmentation. In this paper, we show that training the
classifier with cutout applied at worst-case regions, i.e., regions which
produce the highest classification loss, improves certification accuracy over
PatchCleanser by a large margin. This indicates that our training strategy
improves classifier invariance to pixel masking over prior methods. We
investigate other masking strategies like Grad-CAM guided masking and
exhaustive grid search to find the worst-case mask regions. To reduce the
computational burden of exhaustive grid search, we introduce a two round
greedy masking strategy (Greedy Cutout) to find the worst-case regions. Greedy
Cutout trained models along with PatchCleanser certification sets the state-
of-the-art certified robustness against adversarial patches across different
models and datasets.

## References

  * [1] Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer.  Adversarial patch.  arXiv preprint arXiv:1712.09665, 2017.
  * [2] Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Goldstein.  Certified defenses for adversarial patches.  arXiv preprint arXiv:2003.06693, 2020.
  * [3] Esther Choi et al.  Gutout.  URL https://devpost.com/software/gutout, 2020.
  * [4] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [5] Terrance DeVries and Graham W Taylor.  Improved regularization of convolutional neural networks with cutout.  arXiv preprint arXiv:1708.04552, 2017.
  * [6] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [7] Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song.  Robust physical-world attacks on deep learning visual classification.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. IEEE, jun 2018.
  * [8] Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A Mann.  Improving robustness using generated data.  Advances in Neural Information Processing Systems, 34:4218–4233, 2021.
  * [9] Jamie Hayes.  On visible adversarial perturbations & digital watermarking.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 1597–1604, 2018.
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [11] Jeremy Howard et al.  Imagenette.  URL https://github. com/fastai/imagenette, 2020.
  * [12] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [13] Alexander Levine and Soheil Feizi.  (de) randomized smoothing for certifiable defense against patch attacks.  Advances in Neural Information Processing Systems, 33:6465–6475, 2020.
  * [14] Lin Li and Michael Spratling.  Data augmentation alone can improve adversarial training.  arXiv preprint arXiv:2301.09879, 2023.
  * [15] Wan-Yi Lin, Fatemeh Sheikholeslami, Leslie Rice, J Zico Kolter, et al.  Certified robustness against adversarial patch attacks via randomized cropping.  In ICML 2021 Workshop on Adversarial Machine Learning, 2021.
  * [16] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012–10022, 2021.
  * [17] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A convnet for the 2020s.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11976–11986, 2022.
  * [18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  arXiv preprint arXiv:1706.06083, 2017.
  * [19] Xiaofeng Mao, Yuefeng Chen, Ranjie Duan, Yao Zhu, Gege Qi, Shaokai Ye, Xiaodan Li, Rong Zhang, and Hui Xue.  Enhance the visual representation via discrete adversarial training.  arXiv preprint arXiv:2209.07735, 2022.
  * [20] Jan Hendrik Metzen and Maksym Yatsura.  Efficient certified defenses against patch attacks on image classifiers.  In International Conference on Learning Representations.
  * [21] Jan Hendrik Metzen and Maksym Yatsura.  Efficient certified defenses against patch attacks on image classifiers.  arXiv preprint arXiv:2102.04154, 2021.
  * [22] Norman Mu and David Wagner.  Defending against adversarial patches with robust self-attention.  In ICML 2021 Workshop on Uncertainty and Robustness in Deep Learning, 2021.
  * [23] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  2011\.
  * [24] Axi Niu, Kang Zhang, Chaoning Zhang, Chenshuang Zhang, In So Kweon, Chang D Yoo, and Yanning Zhang.  Fast adversarial training with noise augmentation: A unified perspective on randstart and gradalign.  arXiv preprint arXiv:2202.05488, 2022.
  * [25] Sukrut Rao, David Stutz, and Bernt Schiele.  Adversarial training against location-optimized adversarial patches.  In European Conference on Computer Vision, pages 429–448. Springer, 2020.
  * [26] Hadi Salman, Saachi Jain, Eric Wong, and Aleksander Madry.  Certified patch robustness via smoothed vision transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15137–15147, 2022.
  * [27] Ramprasaath R Selvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra.  Grad-cam: Why did you say that?  arXiv preprint arXiv:1611.07450, 2016.
  * [28] Ross Wightman.  Pytorch image models.  https://github.com/rwightman/pytorch-image-models, 2019.
  * [29] Ross Wightman, Hugo Touvron, and Hervé Jégou.  Resnet strikes back: An improved training procedure in timm.  arXiv preprint arXiv:2110.00476, 2021.
  * [30] Tong Wu, Liang Tong, and Yevgeniy Vorobeychik.  Defending against physically realizable attacks on image classification.  In International Conference on Learning Representations, 2020.
  * [31] Chong Xiang, Arjun Nitin Bhagoji, Vikash Sehwag, and Prateek Mittal.  Patchguard: A provably robust defense against adversarial patches via small receptive fields and masking.  In USENIX Security Symposium, pages 2237–2254, 2021.
  * [32] Chong Xiang, Saeed Mahloujifar, and Prateek Mittal.  $\\{$PatchCleanser$\\}$: Certifiably robust defense against adversarial patches for any image classifier.  In 31st USENIX Security Symposium (USENIX Security 22), pages 2065–2082, 2022.
  * [33] Mingyang Yi, Lu Hou, Jiacheng Sun, Lifeng Shang, Xin Jiang, Qun Liu, and Zhiming Ma.  Improved ood generalization via adversarial training and pretraing.  In International Conference on Machine Learning, pages 11987–11997. PMLR, 2021.
  * [34] Zhanyuan Zhang, Benson Yuan, Michael McCoyd, and David Wagner.  Clipped bagnet: Defending against sticker attacks with clipped bag-of-features.  In 2020 IEEE Security and Privacy Workshops (SPW), pages 55–61. IEEE, 2020.

Revisiting Image Classifier Training for Improved Certified Robust Defense
against Adversarial Patches

Appendix

Algorithm 1 Multi-size Greedy Cutout

1:Image label pair $(\mathbf{x},y)$, vanilla classifier $\mathbb{F}$, mask
sets $\mathbf{M}_{3\times 3},\mathbf{M}_{6\times 6}$

2:Augmented data $(\mathbf{x}_{1}^{\prime},y),(\mathbf{x}_{2}^{\prime},y)$

3:procedure Round-1($\mathbf{x},\mathbb{F},\mathbf{M}_{3\times
3},\mathbf{M}_{6\times 6}$)

4: loss $\leftarrow-1$.

5: for each $\mathbf{m}\in\mathbf{M}_{3\times 3}$ do

6: if $\ell(\mathbb{F}(\mathbf{x}\odot\mathbf{m},y)>\text{loss}$ then

7: $\mathbf{M}_{1}\leftarrow\mathbf{m}$ $\triangleright$ Mask with the largest
loss

8: end if

9: end for

10: $\widetilde{\mathbf{M}}\leftarrow$ $\\{$4 mask from $\mathbf{M}_{6\times
6}$ that covers $\mathbf{M}_{1}\\}$.

11: loss $\leftarrow-1$

12: for each $\mathbf{m}\in\widetilde{\mathbf{M}}$ do

13: if $\ell(\mathbb{F}(\mathbf{x}\odot\mathbf{m},y)>\text{loss}$ then

14: $\mathbf{M}_{11}\leftarrow\mathbf{m}$ $\triangleright$ Mask with the
largest loss

15: end if

16: end for

17: return $\mathbf{M}_{1},\mathbf{M}_{11}$

18:end procedure

19:

20:procedure Round-2($\mathbf{x},\mathbb{F},\mathbf{M}_{3\times
3},\mathbf{M}_{6\times 6}$)

21:
$\mathbf{M}_{1},\mathbf{M}_{11}\leftarrow\textsc{Round-1}(\mathbf{x},\mathbb{F},\mathbf{M}_{3\times
3},\mathbf{M}_{6\times 6})$

22: loss $\leftarrow-1$

23: for $\mathbf{m}\in\mathbf{M}_{3\times 3}$ do

24: if $\ell(\mathbb{F}\odot\mathbf{M}_{11}\odot\mathbf{m})>\text{loss}$ then

25: $\mathbf{m}_{3}^{*}\leftarrow\mathbf{m}$ $\triangleright$ Mask with the
largest loss

26: end if

27: end for

28: $\mathbf{M}_{2}\leftarrow\mathbf{M}_{1}\odot\mathbf{m}_{3}^{*}$

29: $\widehat{\mathbf{M}}\leftarrow$ $\\{$4 mask from $\mathbf{M}_{6\times 6}$
that covers $\mathbf{m}_{3}^{*}\\}$.

30: loss $\leftarrow-1$

31: for each $\mathbf{m}\in\widehat{\mathbf{M}}$ do

32: if $\ell(\mathbb{F}\odot\mathbf{M}_{11}\odot\mathbf{m})>\text{loss}$ then

33: $\mathbf{m}_{6}^{*}\leftarrow\mathbf{m}$ $\triangleright$ Mask with the
largest loss

34: end if

35: end for

36: $\mathbf{M}_{22}\leftarrow\mathbf{M}_{11}\odot\mathbf{m}_{6}^{*}$

37: $\mathbf{x}_{1}^{\prime}\leftarrow\mathbf{x}\odot\mathbf{M}_{2}$
$\triangleright$ Applying mask to augment data

38: $\mathbf{x}_{2}^{\prime}\leftarrow\mathbf{x}\odot\mathbf{M}_{22}$
$\triangleright$ Applying mask to augment data

39: return $(\mathbf{x}_{1}^{\prime},y),(\mathbf{x}_{2}^{\prime},y)$

40:end procedure

Datasets: We use five popular image classfication datasets ranging from low-
resolution to high resolution images.
(1) ImageNet: ImageNet is an image classification dataset [4] with 1000
classes. It has 1.3 million training images and 50k validation images.
(2) ImageNette: ImageNette [11] is a 10-class subset of ImageNet with 9469
training images and 3925 validation images.
(3) CIFAR-10: CIFAR-10 [12] is a benchmark dataset for low-resolution image
classification. The CIFAR-10 dataset consists of 60k 32x32 colour images in 10
classes, with 6k images per class. There are 50k training images and, 10k test
images.
(4) CIFAR-100: This dataset [12] is just like the CIFAR-10, except it has 100
classes containing 600 images each. There are 500 training images and 100
testing images per class. The 100 classes in the CIFAR-100 are grouped into 20
superclasses.
(5) SVHN: Street View House Numbers (SVHN) [23] is a digit classification
benchmark dataset that contains 600,000 32×32 RGB images of printed digits
(from 0 to 9) cropped from pictures of house number plates.

Models: We use image classifiers from three different architecture families.
(1) ResNet: ResNets [10] are deep neural networks which use skip connections.
This approach makes it possible to train the network on thousands of layers
without affecting performance. We use the ResNetV2-50x1 model from the timm
[29] library.
(2) Vision Transformers (ViT): Convolutional Nets are designed based on
inductive biases like translation invariance and a locally restricted
receptive field. Unlike them, transformers are based on a self-attention
mechanism that learns the relationships between elements of a sequence. We use
ViT-B16-224 model.
(3) ConvNeXt: ConvNeXt [17] is a pure convolutional model (ConvNet), inspired
by the design of Vision Transformers. The design starts from a standard ResNet
(e.g. ResNet50) and gradually “modernizes” the architecture to the
construction of a hierarchical vision Transformer (e.g. Swin-T [16]). We use
the ConvNeXt_tiny_in22ft1k model from timm. It is trained on ImageNet-22k and
fine-tuned on ImageNet-1k.

Table A1: Comparing certified robust accuracy of different masking strategies
at two different mask set configurations ${\mathbf{M}}$$3\times 3$ and
${\mathbf{M}}$$6\times 6$ across different datasets. Certification pixels used
3% for ImageNette and ImageNet, and 2.4% for CIFAR-10, CIFAR-100 and SVHN.
Note that training with the masking strategy _greedy $6\times 6$_ on ImageNet
is computationally costly and was not possible with available GPU resources.
Same for Table 3.

| Method | #passes | Mask set ${\mathbf{M}}$$3\times 3$ | Mask set ${\mathbf{M}}$$6\times 6$
---|---|---|---|---
| ImageNette | ImageNet | CIFAR-10 | CIFAR-100 | SVHN | ImageNette | ImageNet | CIFAR-10 | CIFAR-100 | SVHN
ViT | rand$3\times 3$ | 0 | 94.3 | 52.7 | 83.0 | 59.8 | 53.0 | 96.5 | 56.7 | 88.3 | 67.9 | 67.1
rand$6\times 6$ | 0 | 93.6 | 50.6 | 79.5 | 54.9 | 42.2 | 96.0 | 56.7 | 86.0 | 64.4 | 61.3
rand | 0 | 94.7 | 52.7 | 83.1 | 60.1 | 52.0 | 96.4 | 58.3 | 88.4 | 68.5 | 67.7
greedy$3\times 3$ | 17 | 95.1 | 58.3 | 87.9 | 66.6 | 62.5 | 97.2 | 61.2 | 92.2 | 74.2 | 73.8
greedy$6\times 6$ | 71 | 95.1 | 56.6 | 86.2 | 64.4 | 60.6 | 97.5 | 63.8 | 91.8 | 74.3 | 77.9
greedy (Ours) | 25 | 95.5 | 57.7 | 87.5 | 66.0 | 63.3 | 97.3 | 62.3 | 92.0 | 74.5 | 76.8
| grid$3\times 3$ | 45 | 95.3 | 57.9 | 88.0 | 67.3 | 62.7 | 97.3 | 60.5 | 92.2 | 74.6 | 74.0
| grid$6\times 6$ | 666 | 95.3 | - | 83.5 | 60.0 | 61.1 | 97.2 | - | 89.5 | 70.2 | 78.1
|  |  |  |  |  |  |  |  |  |  |  |

Table A2: Table listing the number of forward passes needed in each batch training for grid search and our _Greedy Cutout_ approach. Method | # forward passes/batch training
---|---
grid search$3\times 3$ | 45 unique among $9\times 9=81$
grid search$6\times 6$ | 666 unique among $36\times 36=1296$
greedy$3\times 3$ |  $9$ (round 1) + $8$ (round 2) = $17$
greedy$6\times 6$ |  $36$ (round 1) + $35$ (round 2) = $71$
greedy (Ours) |  $13$ (round 1) + $13$ (round 2) = $26$