  Neural networks' lack of robustness against attacks raises concerns in
security-sensitive settings such as autonomous vehicles. While many
countermeasures may look promising, only a few withstand rigorous evaluation.
Defenses using random transformations (RT) have shown impressive results,
particularly BaRT (Raff et al., 2019) on ImageNet. However, this type of
defense has not been rigorously evaluated, leaving its robustness properties
poorly understood. Their stochastic properties make evaluation more challenging
and render many proposed attacks on deterministic models inapplicable. First,
we show that the BPDA attack (Athalye et al., 2018a) used in BaRT's evaluation
is ineffective and likely overestimates its robustness. We then attempt to
construct the strongest possible RT defense through the informed selection of
transformations and Bayesian optimization for tuning their parameters.
Furthermore, we create the strongest possible attack to evaluate our RT
defense. Our new attack vastly outperforms the baseline, reducing the accuracy
by 83% compared to the 19% reduction by the commonly used EoT attack
($4.3\times$ improvement). Our result indicates that the RT defense on the
Imagenette dataset (a ten-class subset of ImageNet) is not robust against
adversarial examples. Extending the study further, we use our new attack to
adversarially train RT defense (called AdvRT), resulting in a large robustness
gain. Code is available at
https://github.com/wagner-group/demystify-random-transform.
