Title: Robustness against Relational Adversary. Abstract: Test-time adversarial attacks have posed serious challenges to the robustness of machine-learning models, and in many settings the adversarial perturbation need not be bounded by small lp-norms.  Motivated by the semantics-preserving attacks in vision and security domain, we investigate relational adversaries, a broad class of attackers who create adversarial examples that are in a reﬂexive-transitive closure of a logical relation. We analyze the conditions for robustness and propose normalize-and-predict – a learning framework with provable robustness guarantee. We compare our approach with adversarial training and derive an uniﬁed framework that provides beneﬁts of both approaches. Guided by our theoretical ﬁndings, we apply our framework to malware detection and image classiﬁcation. Results of both tasks show that attacks using relational adversaries frequently fool existing models, but our uniﬁed framework can signiﬁcantly enhance their robustness.
