  There has been emerging interest in using transductive learning for
adversarial robustness (Goldwasser et al., NeurIPS 2020; Wu et al., ICML 2020;
Wang et al., ArXiv 2021). Compared to traditional defenses, these defense
mechanisms "dynamically learn" the model based on test-time input; and
theoretically, attacking these defenses reduces to solving a bilevel
optimization problem, which poses difficulty in crafting adaptive attacks. In
this paper, we examine these defense mechanisms from a principled threat
analysis perspective. We formulate and analyze threat models for
transductive-learning based defenses, and point out important subtleties. We
propose the principle of attacking model space for solving bilevel attack
objectives, and present Greedy Model Space Attack (GMSA), an attack framework
that can serve as a new baseline for evaluating transductive-learning based
defenses. Through systematic evaluation, we show that GMSA, even with weak
instantiations, can break previous transductive-learning based defenses, which
were resilient to previous attacks, such as AutoAttack. On the positive side,
we report a somewhat surprising empirical result of "transductive adversarial
training": Adversarially retraining the model using fresh randomness at the
test time gives a significant increase in robustness against attacks we
consider.
