  We show that when taking into account also the image domain $[0,1]^d$,
established $l_1$-projected gradient descent (PGD) attacks are suboptimal as
they do not consider that the effective threat model is the intersection of the
$l_1$-ball and $[0,1]^d$. We study the expected sparsity of the steepest
descent step for this effective threat model and show that the exact projection
onto this set is computationally feasible and yields better performance.
Moreover, we propose an adaptive form of PGD which is highly effective even
with a small budget of iterations. Our resulting $l_1$-APGD is a strong white
box attack showing that prior work overestimated their $l_1$-robustness. Using
$l_1$-APGD for adversarial training we get a robust classifier with SOTA
$l_1$-robustness. Finally, we combine $l_1$-APGD and an adaptation of the
Square Attack to $l_1$ into $l_1$-AutoAttack, an ensemble of attacks which
reliably assesses adversarial robustness for the threat model of $l_1$-ball
intersected with $[0,1]^d$.
