Robustness against Relational Adversary
Authors: Yizhen Wang
Xiaozhu Meng
Mihai Christodorescu
Somesh Jha
Ke Wang
Venue:  (2021)
Keywords: Adversarial Machine Learning
Semantics-Preserving Attacks
Logic Relations
Normalization

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.


Under review as a conference paper at ICLR 2021
ROBUSTNESS AGAINST RELATIONAL ADVERSARY
Anonymous authors Paper under double-blind review
ABSTRACT
Test-time adversarial attacks have posed serious challenges to the robustness of machine-leaming models, and in many settings the adversarial perturbation need not be bounded by small f--nrms. Motivated by the semantics-pres pareaerrcs-pessrvingg attacks in vision and security domain, we investigate relational udversaries, a broad class of attackers who create adversarial examples that are in a reflexive- reflexive-rransitvve closure of a logical relation. We analyze the conditions for robustness and propose normalize-and cond-predict-- - learning framework with provable robustness guarantee. We compare our approach with adversarial training and derive unified framework that provides benefits of both approaches. Guided by our theoretical findings, we apply our framework to image classification and malware detection. Results of both tasks show that attacks using relational adversaries frequently fool existing models, but our unified framework can significantly enhance their robustness.
INTRODUCTION
The robustness of machine learning (ML) systems has been challenged by test-time attacks using adversarial examples (Szegedy et al., 2013). These adversarial examples are intentionally manipulated inputs that preserve the essential characteristics of the original inputs, and thus are expected to have the same test outcome as the originals by human standard; yet they severely affect the performance of many ML models across different domains (Moosavi- -ezzovi-Dezzoooli et al., 2016; Eykholt et al., 2018; Qin et al., 2019). As models in high-stake domains such as system security are also undermined by attacks (Grosse et al., 2017; Rosenberg et al., 2018; Hu & Tan, 2018), robust ML in adversarial test environment becomes an imperative task for the MI. community.
Existing work on test-time attacks predominately considers f,-norm bounded adversarial manip- ulation (Goodfellow et al., 2014; Carlini & Wagner, 2017). However, in many security-critical settings, the adversarial examples need not respect the fy-norm constraint as long as they preserve the malicious semantics. In malware detection, for example, a malware author can implement the same function using different APIs, or bind malware within benign softwares like video games or office tools. The modified malware preserves the malicious functionality despite the drastically different syntactic features. Hence, focusing on adversarial examples of small Gy-norm in this setting will fail to address a sizable attack surface that attackers can exploit to evade detectors.
In addition security threats, another rising concern on ML models is the spurious correlations they could have learned in a biased data set. Ribeiro et al. (2016) show that a highly accurate wolf-vs- husky-dog classifier indeed bases its prediction on the presence/absence of snow in the background. A reliable model, in contrast, should be robust to changes of this nature. Although dubbed as semantic perturbation or manipulation (Mohapatra
al.. 2020; Bhattad al., 2019), these changes do not alter the core of the semantics of input data, thus, we still consider them to be semantics prreerriii--ssevinngg pertaining to the classification task. Since such semanties- pratttiss-peeeriing changes often resulted in large lp fp-norms, they are likely to render the existing -n-mr based defenses incffeetive.
In this paper, we consider a general attack framework in which attackers create adversarial examples by transforming the original inputs via set of rules in a semantics-preserviei prior works (Rosenberg et al., 2018; Hu & Tan, 2018; Hosseini et al., 2017: Hosseini & Poovendran, 2018) which investigate specific adversarial settings, paper extends the scope of attacks to general logical transformation: we unify the threat models into a powerful relational adversary, which can readily incorporate more complex input transformations.
manner. Unlike the

---

Under review as a conference paper at ICLR 2021
From the defense perspective, recent work has started to look beyond bp Ep-norm constraints, including adversarial training (Grosse et al., 2017: Rosenberg et al., 2019; Lei et al., 2019), verification- loss regularization (Huang al., 2019) and invariance-ine induued regularization (Yang al., 2019). Adversarial training in principle can achieve high robust accuracy when the adversarial example in the training loop maximizes the loss. However, finding such adversarial examples is in general NP- hard (Katz et al., 2017), and we show in Sec that it is even PSPACE-hard for semantics- perranntiis-reeeviing attacks that are considered in this paper. Huang et al. (2019) and Yang al. (2019) add regularizers that incorporate model robustness as part of the training objective. However, such regularization can not be strictly enforced training, and neither can the model robustness. These limitations still cause vulnerability to semantics-preserving attacks.
This paper attempts to overcome the limitations of prior work by introducing learning framework that guarantees robustness by design. In particular, we target a relational adversary, whose admissible manipulation is specified by a logical relation. A logical relation is set of input pairs, each of which consists of a source and target of an atomic, semantics- semantics-preserving transformation. We consider a strong adversary who can apply an arbitrary number of transformations. Our paper makes the following contribution towards the theoretical understanding of robust ML against relational adversaries:
Normalize-and-Peei Predict Learning Framework
1. We formally describe admissible adversarial manipulation using logical relations, and characterize the necessary and sufficient conditions for robustness to relational adversaries.
2. We propose normalize-ande prrerpii--- (hereinafter abbreviated as N&P), a learning framework that first converts each data input to a well-defined and unique normal form and then trains and classifies over the normalized inputs. We show that our framework has guaranteed robustness, and characterize conditions to different levels of robusmess-accuraccy tradc-off.
3. We compare N&P to the popular adversarial training framework, which directly optimizes for accuracy under attacks. We show that N&P has the advantage in terms of explicit robustness guarantec and reduced training complexity, and certain cases yields the same model accuracy adversarial training. Motivated by the comparison, we propose a unified framework, which selectively normalizes over relations that tend to preserve the model accuracy and adversarially trains over the rest. Our unified approach gets the benefits from both frameworks.
We then apply our theoretical findings to malware detection and image classification. For the former, first, we formulate two types of common program transformation -onnnm-01 (1) addition of redundant libraries and API calls, and (2) substitution of equivalent API calls as logical relations. Next, we instantiate learning framework to these relations, and propose two generic relational adversarial attacks to determine the robustness of a model. Finally, we perform experiments over Sleipnir, a real-world WIN32 malware data set. Regarding image classification, we reused an attack method proposed by the prior work (Hosscini & Poovendran, 2018) - shifting of the hue in the HSV color space that can be deemed as a specific instantiation of our attack framework. We then compare the accuracy and robustness of ResNet-32 (He et al., 2016), common image classification model, trained with the unified framework against the standard adversarial training on CIFAR-10 (Krizhevsky et al., 2009). The results we obtained in both tasks show that:
1. Attacks using addition and substitution suffice to evade existing ML malware detectors.
2. Our unified approach using input normalization and adversarial training achieves highest robust accuracy among all baselines in malware detection. The drop in accuracy on clean inputs is small and the computation cost is lower than pure adversarial training.
3. When trained with the unified learning framework, ResNet-32 achieves similar clean accu- racy but significantly higher robust accuracy than adversarial training alone.
Finally, based on theoretical and empirical results, we conclude that input normalization is vital to robust learning against relational adversaries. We believe techniques that can improve the quality of normalization promising directions for future work.
2

---

Under review as a conference paper at ICLR 2021
2
RELATED WORK.
Test-time attacks using adversarial examples have been extensively studied in the past several years. Research has shown ML models are vulnerable such attack in variety of application domains (Moosavi-Dezfool) et al., 2016; Chen et al., 2017; Papernot et al., 2017; Eykholt et al., 2018: Ebrahimi et al., 2018; Qin et al., 2019; Yang et al., 2020) including system security where reliable defense is absolutely essential. For instance, Grosse et al. (2017) and Al-Dujaili et al. (2018) evade API/library usage based malware detectors by adding redundant API calls; Rosenberg et al. (2018). Hu & Tan (2018), and Rosenberg et al. (2019) successfully attack running-time behavior based detectors by adding redundant execution traces; Pierazzi et al. (2020) extend the attacks from feature-space to problem-spane saaee,, propose a framework to describe real-world attacker's s constraints and create realistic attack instances using automated software transplantation.
On the defense end, the work closest to ours in spirit is Yang et al. (2019), which adds invariance- induced regularizers to the training process. Their work however differs from ours in two major ways. First, their work considers a specific spatial transformation attack in image classification; our work considers a general adversary based on logic relations. Second, their regularizer may not enforce the model robustness on finite samples they primarily interested in enhancing the model accuracy. In contrast, our framework emphasizes robustness which is enforced by design. Grosse et al. (2017); Al-Dujaili et al. (2018); Rosenberg al. (2019) improve robustness via adversarial training; show such approach is hard to optimize. Incer et al. (2018); Kouzemtchenko (2018) enforce monotonicity over model outputs so that the addition of feature values always increase the maliciousness score. These approaches are limited to guarding against the addition attacks, thus lacks generality. Last, Xu al. (2017) use feature squeezing, which quantizes the feature values in order to reduce the number of adversarial choices. However, their defense is for b, noom adversaries and thus inapplicable for relational attacks.
Normalization is a technique to reduce the number of syntactically distinct instances. First introduced to network security the early 2000s in the context of intrusion detection systems (Handley et al., 2001), it was later applied to malware detection (Christodorescu et al., 2007; Coogan et al., 2011 I; Bichsel et al., 2016; Salem Banescu, 2016; Baumann et al., 2017). Our work addresses the open question whether normalization is useful for ML under relational adversary by investigating its impact on both model robustness and accuracy.
3 BACKGROUND
In this section, we first describe the learning task, then formalize the potential adversarial manipulation as logical relations, and eventually derive the notion of robustness relational adversaries.
Learning Task. We consider a data distribution D over input space X' and categorical label space D. We use bold face letters, e.g. x, for input vectors and for the label. Given hypothesis class H. the learner wants to learn a classifier f X' - y in H that minimizes the risk over the data distribution. In non-adversarial settings, the learner solves min JEH E(x,))/ E(J, x,y). where l is loss function. For classification, ((f, y) 1f((x) *).
Logical Relation. A relation R is a set of input pairs, where each pair (x, 2) specifies transformation of input to output We write x -7R iff (x, 2) E R. We write x + iff x z or there exists Zo. Z1, ... Zg (k > 0) such that x = Zμ, Z, -R Z;+1 (0 S i < k) and Z = z. In other words, + is the dellexive-transitie closure of RR We describe an example relation as follows:
Example (Hue Shifting). Let X4, Xs, x, denote the hue, saturation and value components of an image X. In hue shifting relation R, x -R iff 2₁. = (xx+5) % where d is a scalar, z, = xx,, 2n = =x,- Since X changes in a circle, i.e., hue of is equal to hue of 0. Hence, we compute the modulo of the hue component with 1 to map 2n. within [0, (Appendix B gives the background of HSV).
In this paper, we also consider unions of relations. Notice that a finite union R of m relations "1,".. R., is also a relation, and - iff x rR for any E (I,...,,)
3

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison of training objective and test output for standard risk minimization learning scheme, NaP and adversarial training; f is the minimizer of the training objective.
No Defense
Normalize-and-Pree
Adversarial Training
Train
min
Σ 8(S,x,))
min Σ ((),N(x):
min max Σ e(S v A() (x.
f
(x.))ED
(x.v)ED
Test
(x)
(N())
(*)
Threat Model. A test-time adversary replaces a clean test input with an adversarially manipulated input A(x), where A(-) represents the attack algorithm. We consider an adversary who wants to maximize the classification error rate: (xxx))> (f(A(x)) # y)-
We assume white-box attacks', i.e. the adversary has total access to f. including its structures, model parameters and any defense mechanism in place. To maintain the malicious semanties, the adversarial input A(x) should belong to a feasible set Txx). In this paper, we focus on T(x) that described by relation. We consider a logical relation R that is known to both the learner and the adversary, and define a relational adversary as the following.
Definition (relational adversary). An adversary is said to be R-relational if Tf = x 2). i.e. each element in R represents an admissible transformation, and the adversary can apply arbitrary number of transformation specified by R.
We can then define the robustness of classifier by how often its prediction is consistent under attack, and robust accuracy as the fraction of predictions that are both robust and accurate.
Definition (Robustness and robust accuracy). Let Q(R, f,x) be the following statement: V (z((x - z) = f(x) f(z)). Then, a classifier f is robust at if QR. f.x) is true, and the robustness of f to an R-relational adversary is: Ex~Dx xx) where ( indicates the truth value of a statement and D is the marginal distribution over inputs. The robust accuracy of f w.r.t
an R-relational adversary is then; Ex(xy)>D 1 x))_)/)))/(x==>
Notice that the robust accuracy of classifier is no more than the robustness in value because of the extra requirement of fxx y. Mcanwhile, classifier with the highest robustness accuracy may not always have the highest robustness and vice versa: an intuitive example is that a constant classifier is always robust but not necessarily robustly accurate. In See 4, we will discuss both objectives and characterize the trade-off between them.
4 N&P A PROVABLY ROBUST LEARNING FRAMEWORK
In this section, we introduce N&P, a learning framework which learns and predicts over normalized training and test inputs. We first identify the necessary and sufficient condition for robustness, and propose normalization procedure that makes NaP provably robust to R-relational adversaries. Finally, we analyze the performance of N&P: since NaP guarantees robustness, the analysis will focus on robustness-accuracy trade-off and provide in-depth understanding to causes of such trade-off.
4.1 AN OVERVIEW OF THE N&P FRAMEWORK
In N&P, the learner first specifies a normalizer N : X - X. We call (xx) ) the 'normal form' of input x. The learner then both trains the classifier and predicts the test label over the normal forms instead of the original inputs. Let D denote the training set. In the empirical risk minimization learning scheme, for example, the learner will now solve the following problem
min FEH
Σ (f.A(xx)))) (X.)ED
(I)
and use the minimizer f the classifier. During test-time, the model will predict f (N'())). Table 1 compares the N&P learning pipeline to normal risk minimization and adversarial training.
We consider strong white-box attacker avoid interference from security by obscurity, which is shown fragile in various other adversarial settings (Carlimi & Wagner, 2017).
4

---

Under review as a conference paper at ICLR 2021
Z
z
X
Z2
Figure. 1: Relations with different pobusttess-accurrae trade-off. Different node colors indicate different most likely labels. Appendix A.7 gives a detailed explanation on why semantics semantiss-reeservngg preserving transformation can still change the labels of data. Left: Na/ preserves natural accuracy; Middle: N&P preserves robust accuracy; Right: N&P causes suboptimal robust accuracy: suppose ju(x) 0.02, p(z)) = p((z)) 0.49 and 7) deterministic. N&P predict the same label and thus has accuracy at most 0.49, while the highest robust accuracy is 0.98 by predicting the true label for ž and Z2.
4.2 FINDING THE NORMALIZER
The normalizer N is crucial for achieving robustness: intuitively, if and its adversarial example Xade share the same normal form, then the prediction will be robust. Meanwhile, a constant / is robust, but has no utility as (-)( also constant. Therefore, we seek an N that perform only the necessary normalization for robustness and has minimal impact accuracy.
We first construct the relational graph GR = EV of R: the vertex set V contains all elements in X:; the edge set E contains edge (x iff (x, 2) R. Then, directed path exists from to iff x + z. We derive the following necessary and sufficient condition for robustness under N&P in Observation 1, and thus obtain normalizer N in Proposition that guarantees robustness.
Observation 1 (Condition for Robustness). Let Ct,'.. .... C2 denote the weakly connected components (WCC) in GR. A classifier f is robust for all x E C2 iff f(x) returns the same label for all x E C.. Proposition (Choice of Normalizer). Let N be a function that maps an input x E C₁ to any deterministic element in C.. Then f(N(-) is robust R-relational adversaries?
4.3 ROBUSTNESS-ACCURAN TRADE-OFF
Optimal Accuracy under N&P. Let u(x) denote the probability mass of The label of an input x may also be probabilistic in nature, therefore we use ()x11)=Ppp = ( to denote the probability that has label 1. Then the optimal robust accuracy using N&P, denoted by Accie, is Ec, maxtey Exec, (x)), which happens when f(N(x) = arg maxley Exec, ((x)n((xXI 1) for x E C.. Intuitively, f shall assign the most likely label of random samples C; to all E Cy.
Price of Robustness. In N&P, the optimal robust accuracy depends on R. We then observe the following fundamental robustness-accuracy trade-off:: as the relation becomes more complicated, we may lose accuracy for enforcing invariant model predictions, and such loss is the price of robustness.
Observation 2 (Robustness accuraacy trade-off). Let R' and R be two relations s.f. R' = R Ul((x,)), iee R' allows an extra transformation from GR that contains x, and le be the most likely label of imputs in a WCC C. Then Acc - Acct S 0 for all R. R' pairs, and the equality only holds when Ic2 lC2.R.
than R. Let Cx,R denote the WCC in
The intuition is that the extra edge on the relation graph may join two connected components which are otherwise separate. As a result, a model under N&P will predict the same label for the two components, thus the accuracy on one component will drop if two components have different labels.
We further characterize three different levels of trade-offs (Figure 1). First, two inputs x, z have the same most likely label D, then the optimal accuracy under N&P is the same as before normalization, in other words, robustness is obtained for free. Second, if both (x, z) and (z, x) are in R but x, have different most likely labels, then the model with the highest natural accuracy, which predicts the most likely label of x and respectively, do not have any robustness. In contrast, N&P achieves the optimal robust accuracy by predicting a single label - the most likely label of samples in {x, 2] for both x and z. Third, if x can only be way transformed to two inputs 21, 22 with different
Appendix C.I shows a decidable algorithm realizing such an N given GR- For example, ransomware and zip tool may have the same static feature vector The label of randomly drawn is probabilistic, and the prohability depends on the frequency that each software appears.
5

---

Under review as a conference paper at ICLR 2021
most likely labels, then NaP may have suboptimal robust accuracy. An absolutely robust classifier need to predict the same label for x, 21 and Z2, while the classifier with the highest robust accuracy should predict the mostly likely labels for 21 and Z2 if 21, 22 appear more frequently than
5 COMPARING AND UNIFYING N&P WITH ADVERSARIAL TRAINING
N&P differs from the adversarial training - the most widely acknowledged defense mechanism against test-time adversary in its objective and procedure. While each approach has its limitation against relational adversaries, we show that they can complement each other and be unified into one framework that enjoys the benefits from both worlds.
Comparative Advantages. The performance of adversarial training depends on the quality of the adversarial examples. However, we show in Proposition that the inner maximization problem is in general computationally infeasible for relational adversaries.
Proposition 2 (Hardness of Inner Maximization). The inner optimization problem of adversarial training is PSPACE-hard for relational adversaries.
Intuitively, the search space of relational adversary can grow combinatorially with the number of transformations, and the proposition follows the classical results of reachability analysis in model checking (Kozen, 1977). The N&P framework, in contrast, solves typical minimization problem, and thus reduces the computation complexity an efficient normalizer exists. Meanwhile, we show in Appendix A.4 that robust accuracy can be achieved with simpler model class on normalized inputs than on original inputs; reduced model complexity may also improve the sample efficiency of the underlying learning algorithm. On the other hand, N&P may incur excessive loss accuracy to enforce robustness, for example, the last scenario in Figure I, in which case, adversarial training will be a better choice for overall utility.
A Unified Framework. Motivated by the above observations, we propose a unified framework: for a relation R, we strategically select a subset R' R normalize inputs, and adversarially train on the normalized inputs. Let denote the normalizer for R', Formally, the learner solves
min max JEH A(-)
Σ e (Nxx (x.))ED
during training to obtain minimizer f*, and predicts ("VRR: (x)) at test-time. The classifier f* will robust to R'-relational adversary, and have potentially higher robust accuracy than using N&P alone. In particular, if R' is reversible by Definition 3, then unified framework preserves the optimal robust accuracy as shown in Theorem 1.
Definition 3. A relation R' is reversible iff R² implies RRR'- X and vice versa.
Theorem (Preservation of robust accuracy). Let f be the classifier that minimizes the objective of our unified framework over data distribution D, and let Jūdo minimize the objective of adversarial training over D. Then, in principle, (N(R)()) and fadd have the same optimal robust accuracy if R' is reversible.
The proof can be found in Appendix A.5. In essence, Theorem is a generalization of the second scenario in Figure 1, in particular, we extend the same principle applied to (x, z) to all possible pairs of inputs in the relational graph induced by R'. Note that reversible relation also common: if is x's adversarial example, then x is also likely to be an adversarial choice of z. Observation 2 and Theorem provide general guideline for selecting R': choose the reversible subset of R first, and then consider transformations that cause little drop in optimal robust accuracy.
Regarding the efficiency normalization, we show in Appendix A.6 that the strongest adversarial example satisfies the requirment of Proposition 1, and thus can be used as the normal form. Therefore, in theory, NaP is at least as efficient as the optimal adversarial training. practice, the normalizer we use in empirical evaluation are all more efficient than adversarial training.
6 EXPERIMENT
We now evaluate the effectiveness of our unified framework against relational attacks. particular, seek answers to the following questions:

---

Under review as a conference paper at ICLR 2021
Table 2: Malware Detection: False Negative Rate (FNR) and False Positive Rate (FPR) on Sleipnir.
Unified (Ours)
Adv-Trained
Al-Dujaili et al. (2018)
Natural
FNR(%)
FPR(%)
(NR(%)
FPR(%)
FNR(%)
FPR(S)
FNR(%)
FPR(%)
Natural Adversurial
5.0:0..4
11.9
5.8+0.9
12.1
6.4=0.5 89.9=7.8
10.7:+0.3
10.0+:0.6 100=0.00
6.2:10.6
0.5+0.5
1199112
27.9+8.2
12.1+1.2
10.7+0.3
10.0#0.6
1. Do relational attacks pose real threats to existing MI models?
2. How effective is our unified framework in enhancing robustness, and do the results corrobo- rate with the theory?
We investigate these aspects over two real world tasks - malware detection and image classification. For each task, we identify relations that do not alter the essential semantics of the inputs. Our result shows that the models obtained from our unified framework has the highest robust accuracy compared to adversarially trained models and unprotected models.
6.1 MALWARE DETECTION
We evaluate malware detection task on Sleipnir. data set containing Windows binary API usage features of 34,995 malware and 19,696 benign software, extracted from their Portable Exccutable (PE) files using LIEF (Thomas, 2017). The detection is exclusively based on the API usage of malware. There are 22,761 unique API calls in the data set, so each PE file is represented by a binary indicator vector x E {0, 1)"h. where m 22, 761. Note that this the same encoding scheme adopted by Al-Dujaili et al. (2018). We sample 19,000 benign PEs and 19,000 malicious PEs to construct the training (60%), validation (20%), and test (20%) sets.
Existing lp norm based attacks are not applicable for relational adversaries. Mcanwhile, exhaustive search over adversarial choices may be computationally prohibitive. Therefore, we propose two heuristic attack algorithms GREEDY B YGROUP and GREEDyByGRAN to validate models' robust accuracy. Both algorithms are greedy and iterative nature. Detailed algorithm descriptions are in Appendix C.2.
BREEDyByGROLE takes a test input vector x and a maximum number of iterations K. In each iteration, it partitions R into subsets of relations Ri.... Rm, and finds the instance within the transitive closure of each R2 that maximizes the loss. These instances from R,s are combined to create the new version of adv Notice the attack reduces to exact search if R is not partitioned.
GREEDY BAREDYByGRRY GRAD takes a test input vector x, a maximum number m of transformation to apply in each iteration, and maximum number of iteration K. In each iteration, it makes first-order approx- imation of the change in test loss caused by each transformation, and then applies the transformations with top m approximated increases in test loss to create the new version of add
Relation and Attacks. The goal of an adversary is to evade a malware detector. common strategy that (Al-Dujaili et al., 2018) also adopts is adding redundant API calls. This strategy be described by an additive relation: (x, z) E R. iff z is obtained by flipping some x's feature values from O 1. We also consider new attacking strategy, which substitutes API calls with functionally equivalent counterparts. This strategy can be described by an equivalence relation: (x, z) E R iff z is obtained by changing some of x's feature values from I to 0 in conjunction with some of x's other feature values changed from 0 to 1. With expert knowledge, we extract nearly 2.000 equivalent API groups described in Appendix C.3. We use three attack algorithms GREEDYBYGRAD. GREEDY B GGRUUP and the r ffsmm additive attack presented by Al-Dujaili et al. (2018) and consider the attack to be successful if any algorithm fools the detector.
Model and Baselines. We compare four ML detectors. The Unified detector is realized using our unified framework in Sec 5: we normalize over the equivalence relation based on the functionally equivalent API groups, and then adversarially trains over the additive relation. The Ady-Trained detector is adversarially trained with the best adversarial example generated using GREEDY B GRAD and the rfgsn_ k additive attack (Al-Dujaili et al., 2018) GREEDYB BYROUP is too computation- ally expensive to be included in the training loop. We also include the model proposed by Al- Al-Dujaili al. (2018), which is adversarially trained against only the rfgsm_k additive attack, and Natural
7

---

Under review as a conference paper at ICLR 2021
Table 3: Image Classification: Classification accuracy on CIFARIO, same relation in training and testing. The first column specifies the attack parameters used in test-time. The parameters are in the form of (le -norm, PGD step size, PGD steps, number of hue-shifts). The models are adversarially trained using (4/255, 2/255, 3, 20).
Unified (Ours)
Adv-Trained (Combined)
Adv-Trained (PGD only)
Natural
73.4
73.
78.6:10.7
(4/255, 3,
54.9
50.0:10.8
28.5:10.6
(4/255, 2/255,3.200
54.9+1.2
49.1
28.3+0.6
(4/255, 2/255,15,,2 20)
54.3#1.1
48.6=0.9
27.9
(4/255, 2/255,200,44
54.2++122
48.2+
27.8++0.6
(6/255, 2/255, 15, 20)
42.4+1.4
34.5+1.1
17.4++0.8
66/255, 2/255, 200, 200)
42.3
33.
17.240.8
Table 4: Image Classification: Classification accuracy CIFARIO, relation in training is subset of relation in testing. The attacker uses a 15-step PGD attack with f -nom 4/255 and step size 2/255, and randomly samples 500 combinations of hue, brightness and constrast adjustment factors.
Unified (Ours)
Ady-Trained (Combined)
Adv-Trained (PGD only)
Natural Adversarial
73.4
73.7
78.6 19.7
1..
41.7
model with no defense. We use the same network architecture Al-Dujaili et al. (2018), fully- connected neural net with three hidden layers, each with 300 ReLU nodes, to set up a fair comparison. We train each baseline to minimize the negative log-likelihood loss for 20 epochs, and pick the model with the lowest validation loss. We run five different data splits.
Results. As Table 2 shows, relational attacks overwhelmingly effective detectors that oblivious to potential transformations. Adversarial examples almost always (>99% FNR) evade the naturally trained model, and also evade the detector in Al-Dujaili et al. (2018) most of the time (>89% FNR) as does not consider API substitution. On the defense end, Unified achieves the highest robust accuracy: the evasion rate (FNR) only increases by 0.5% on average. Adv-Trained comes second but the evasion rate is still 22.1% higher. The evasion is mostly caused by GREEDY B GROUP, the attack that is too computationally expensive be included in the training loop. This result corroborates with the theoretical advantage of N&P: its robustness guarantee is independent of training algorithms. Last, all detectors using robust learning techniques have higher FPR compared to Natural, which expected because of the inevitable robustness-aceuran trade-off. However, the difference is much smaller compared the cost due to attacks, and thus the trade-off is worthwhile.
6.2 IMAGE CLASSIFICATION
We evaluate the effectiveness of our unified framework on CIFARIO containing 50,000 training and 10,000 test images of size 32x32 pixels. We randomly sample 5,000 images for validation and train on the remaining 45,000 images.
Relation and Attacks. We consider relation induced by hue shifting specified in Example 1. Due to the shape bias property (Landau et al., 1988), humans can still correctly classify most images after the adjustment of color hue. Therefore, we consider this relation be peranticsppreevviggg The attacker uses a combination of to and relational attacks: it first shifts the color hue of the image, and then generates fo adversarial example using PGD attack. For each image, the attacker tries different hue adjustments, which evenly split the hue space. In addition, can also adjust the brightness and contrast of the image by a factor [0.8, 1.2). . It tries 500 random combination of hue, brightness and contrast adjustments followed by PGD attack.
consider attacker that
Model and Baselines. The Unified classifier is obtained with our unified framework in Sec 5: we adjust hue of the input such that the pixel at the top-left corner has hue value 1, and then adversarially
8

---

Under review as a conference paper at ICLR 2021
train against the PGD attack. We also consider two adversarial training baselines: the first uses the combined attack (PGD and hue adjustment) in training, while the second only uses the PGD attack. We train ResNet32 network for 100 epochs in all configurations, and pick the model with the lowest validation loss. We also run five different data splits.
Results. Table 3 shows the results against attackers using hue-shift and foe perturbation. Although adversarial training against only the PGD attack has higher clean input accuracy, the combined attack heavily reduces its accuracy, indicating again the effectiveness of simple relational attack to unprotected models. Unified achieves the highest robust accuracy against the combined attack 4.8% higher compared to adversarial training with the combined attack over all attack parameters. This result shows the ad advantage of normalization over reversible relations, as projected by our analysis in Sec 5. addition, Table 4 shows the results against an attacker using more transformations than the ones normalized in training. Our unified approach still achieves the highest accuracy with substantial margin over the baselines. Although the attacker may use more transformations, normalization can still reduce the search space of adversarial examples and increase robustness.
7 CONCLUSION AND FUTURE WORK
In this work, set the first step towards robust learning against relational adversaries: theoreti- cally characterize the conditions for robustness and the sources of robustness-accuracy trade-off, and propose provably robust learning framework. Our empirical evaluation shows that combination of input normalization and adversarial training can significantly enhance model robustness. For future work, see automatic detection of semantics-presee preseeviig transformation promising addition to our current expert knowledge approach, and plan to extend the normalization approach to deal with other kinds of attacks beyond relational adversaries.
"Given an input image in RGB format, we first convert the image to HSV format, and then add scalar to the hue of all pixels. The scalar is determined by 1 (the hue of the pixel on the first row and first column). The hue values are then projected back to the [0.1] interval by taking the remainder over 1. Finally, we convert the image back RGB for classification.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Abdullah Al-Dujaili, Alex Huang, Erik Hemberg, and Una-May O'Reilly. Adversarial deep learning for robust detection of binary encoded malware. In 2018 IEEE Security and Privacy Workshops (SPW), pp. 76-82. IEEE, 2018.
Richard Baumann, Mykolai Protsenko, and Tilo Müller. Anti-proguard: Towards automated deobfus- cation of android apps. In Proceedings of the 4th Workshop on Security in Highly Connected IT Systems, SHCIS 17, pp. 7-12, New York, NY, USA, 2017. ACM. ISBN 978- 078-1-45003-527-44 doi: URL www.hhtp://oooo acm. org/ 10. 11 4044559399011 3099020.
22.1145/30990123099999
Anand Bhattad, Min Jin Chong, Kaizhao Liang, Bo Li, and David A Forsyth. Unrestricted adversarial examples via semantic manipulation. arXiv preprint arXiv: 1904.06344777 2019.
Benjamin Bichsel, Veselin Raychev, Petar Tsankov, and Martin Vechev. Statistical deobfuscation of android applications. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS " 16, pp. 343-355, New York, NY, USA, 2016. ACM. ISBN 978- 1-4503-4139-4. doi: 10.1145/29764499978848 2976749. 2978422. 22767...2978422.
URL http:://///oooo acm. ottmmoorg/1111.1
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Pin-Yr Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Mihai Christodorescu, Somesh Jha, Johannes Kinder, Stefan Katzenbeisser, and Helmut Veith. Software transformations to improve malware detection. Journal in Computer Virology, 3:253-265, 10 2007. doi: 10.1007/s1 1416-0077 6-000-0059-..
Kevin Coogan, Gen Lu, and Saumya Debray. Deobfuscation of virualizatiion-obfuscaee software: A semantics-bann based approach. In Proceedings of the 18th ACM Conference on Computer and Communications Security, CCS '1. pp. 275-284, New York, NY, USA, 2011. ACM. ISBN 978- 1-4503-0948-6. doi: 10.1 10.1145/204600... 20007666777.046799 2046739. URL http: doi.. acm. /ttgg/1..111. 2046707. 2046739.
Javid Ebrahimi. Anyi Rao, Daniel Lowd, and Dejing Dou. Hotflip: White-box adversarial exam- ples for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Pupers), pp. 31-36, 2018
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-worid attacks on deep learning visual classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1625-1634, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 1412.5522 2014.
Kathrin Grosse, Nicolas Papernot, Praveen Manoharan, Michael Backes, and Patrick McDaniel. Adversarial examples for malware detection. In European Symposium on Research in Computer Security, pp. 62-79. Springer, 2017.
Mark Handley, Vern Paxson, and Christian Kreibich. Network intrusion detection: Evasion, traffic normalization, and end-to-end protocol semantics. In Proceedings of the 10th Conference
USENIX Security Symposium Volume 10, SSYM'01, Berkeley, CA, USA, 2001. USENIX 1251336. K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 20/6 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Association. URL http: / d1l. acm. org/ ci t aatiiononn wftp:ccccmmiddmmfff
Hossein Hosseini and Radha Poovendran. Semantic adversarial examples. Proceedings of the IEFE Conference Computer Vision and Pattern Recognition Workshops, pp. 1614-1619, 2018.
10

---

Under review as a conference paper at ICLR 2021
Hossein Hosseini, Baicen Xiao, Mayoore Jaiswal, and Radha Poovendran. On the limitation of convolutional neural networks in recognizing negative images. In 2017 16th IEEE International Conference Machine Learning and Applications (ICMLA), pp. 358. IEEE, 2017.
Weiwei Hu and Ying Tan. Black-box attacks against rnn based malware detection algorithms. In Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Po-Sen Huang, Robert Stanforth, Johannes Welbi, Chris Dyer, Dani Yogatama, Sven Gowal, Krishna- murthy Dvijotham, and Pushmeet Kohli. Achieving verified robustness to symbol substitutions via interval bound propagation. pp. 4074 4084, 2019.
Inigo Incer, Michael Theodorides, Sadia Afroz, and David Wagner. Adversarially robust malware detection using monotonic classification. In the Fourth ACM International Workshop on Security and Privacy Analytics (/WSPA), Tempe, AZ, USA, Mar. 2018.
G. Katz, C. Barrett, D.I., Dill, K. Julian, and M.J. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, 2017.
A. Koschan, M. Abidi, and M.A. Abidi. Digital Color Image Processing. Wiley, 2008 ISBN 9780470147085.
Alex Kouzemtchenko. Defending malware classification networks against adversarial perturbations with non-negative weight restrictions. arXiv preprint arXiv: 180::000000933 2018
Dexter Kozen. Lower bounds for natural proof systems. In FOCS, 1977.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Barbara Landau, Linda B Smith, and Susan Jones. The importance of shape in early lexical learning. Cognitive development, 3(3):299-3222 1988.
Qi Lei, Lingfei Wu, Pin-Ye Yu Chen, Alexandros G Dimakis, Inderjit Dhillon, and Michael Witbrock. Discrete adversarial attacks and submodular optimization with applications to text classification. Systems and Machine Learning (SysML), 2019.
Jeet Mohapatra, Tsui- Wei Weng, Pin- Yu Chen, Sijia Liu, and Luca Daniel. Towards verifying robustness of neural networks against family of semantic perturbations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 244 242,,52,44 2020.
Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574-2582, 2016.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference computer and communications security, pp. 506-519, 2017.
Fabio Pierazzi, Feargus Pendlebury, Jacopo Cortellazzi, and Lorenzo Cavallaro. Intriguing properties of adversarial ml attacks in the problem space. In 2020 IEEE Symposium on Security and Privacy (SP), pp. 1308-1325.. IEEE Computer Society, 2020. doi: 10. 10.10099/944000002000.0000 https:: doi.
URL
10.
2020 00073.
Yao Qin, Nicholas Carlini, Garrisnn Cottrell, Ian Goodfellow, and Colin Raffel. Imperceptible, robust, and targeted adversarial examples for automatic speech recognition. In International Conference on Machine Learning, pp. 523 12240, 2019.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1 1135-1144 ACM, 2016.
Ishai Rosenberg, Asaf Shabtai, Lior Rokach, and Yuval Elovici. Generie black-box end-to-end attack against state of the art api call based malware classifiers. In International Symposium on Research in Attacks, Intrusions, and Defenses, pp. 490-510. Springer, 2018
11

---

Under review as a conference paper at ICLR 2021
Ishai Rosenberg, Asaf Shabtai, Yuval Elovici, and Lior Rokach. Defense methods against adversarial examples for recurrent neural networks. arXiv preprint 1.XX::19001009633, 2019.
Aleieldin Salem and Sebastian Banescu. Metadata recovery from obfuscated programs using machine learning. In Proceedings of the 6th Workshop Software Security, Protection, and Reverse Engineering, SSPREW '16, pp. 1:1-1:11, New York, NY, USA, 2016. ACM. ISBN 978-1- 4503-4841-6. doi: 10.114573015133330511338 URL http: /doi acm. hwtp/oo.o/......... 1145/ 3015135. 3015136.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint urXiv::312.6799 2013.
Romain Thomas. Lief library to instrument executable formats. https:/liee.quarsstbb.oom// April 2017.
Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. arXiv preprint 0rXiv:1704.01555 2017.
Fanny Yang, Zuowen Wang, and Christina Heinze-Deml. Invariance-inducing regularization using worst-case transformations suffices boost accuracy and spatial robustness. Advances Neural Information Processing Systems, pp. 14757-14768, 2019.
Puyudi Yang, Jianbo Chen, Cho-Jui Hsieh, Lane-Ling Wang, and Michael I Jordan, Greedy attack and gumbel attack: Generating adversarial examples for discrete data. Journal of Machine Learning Research, 21(43):1-3,, 2020.
12


Reviews:
[{"review_id": "dloPldWXBnQ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to define robustness against adversarial attacks using a binary relation over inputs. The binary relation R states which input examples should be classified the same way and each connected component defined by R needs to be assigned the same label leading to robust classification. The idea of using a relation to capture what information in the input can be exploited for classification seems simple but was insightful to this reviewer. The authors propose to combine this approach of normalizing the input with existing techniques to handle adversarial classification to propose a new way to derive a robust classifier. Experiments on malware data and image data show that it leads to the best trade-off between classification accuracy and robustness.\n\nIn the experiments, the normalizers used to train the classifier are the same ones used to manipulate the test input. Is this realistic? Shouldn't it be the case that different techniques be used to manipulate the inputs for testing? I mean in section 6.1 Unified detector is trained using functionally equivalent API calls and the same is also used to launch an attack. Similarly, in section 6.2 hue shifting is used to manipulate test inputs while Unified classifier normalizes by setting the top left corner pixel to unit hue. Assuming such perfect knowledge of the adversaries techniques and using it to train a robust classifier seems unrealistic. How do the proposed techniques apply in more realistic situations where we would not know the adversary's techniques? How do we choose a normalizer in such situations? IMHO these questions need to be answered in the paper to ensure applicability in the real world, otherwise it seems this formulation of robustness to adversarial attacks is simply of academic interest.\n\nWriting wise, the paper is an easy read. Proofs and other details are delegated to the appendix while the matter is made accessible by insightful, approachable, hand-holding discussions in the main body of the paper expressing the core ideas easily.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TT7Hc22WlVr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThe authors investigate relational adversaries, adversarial attacks that\nlie in a reflexive-transitive closure of logical relation. The authors\nfocus on such attacks as they are motivated by attacks that are not\nnecessarily bound to small lp-norms (typical of security application\ndomains). The authors analyze the condition of robustness required in\nthis context and propose normalize-and-predict, a learning framework\nwith provable robustness guarantees. The authors further compare their\napproach against adversarial training, which helps them to propose a\nunified theoretical framework. While relational adversary attacks seem\nsuccessful against adversarial training models, the authors' framework\nenhances their robustness.\n\n## Strengths\n\n+  Adversarial ML attacks that are not necessarily bounded by small\nlp-norms are interesting and still not widely studied\n+  Interesting intuition around the concept of normalization\n\n## Weaknesses\n\n-  Effectiveness of normalization is bound to the set of semantics-preserving transformations available to attackers. How easy is it to find a normalizer? How easy is it for attackers to find another set of semantics-preserving transformations that would void the normalizer?\n   \n-  Likely experimental bias in the malware experiments?\n\n## Comments\n\nI found the paper well-written and motivated. I particularly liked the\nfact the authors focus on adversarial attacks those that are not\nnecessarily bounded by small lp-norms (e.g., adversarial attacks \"in the\nproblem space\" [1]).\n\nThe authors explore an interesting problem that's been often neglected\nbut that plays a fundamental role in specific application domains (e.g.,\nsecurity). It would have been interesting to see how the authors' work\ncompared against a recently-published work [1] that reasons along the\nsame line. In particular, I wonder whether the theoretical framework in\n[1], which reformulate adversarial ML attacks at test-time in the\nproblem space would overlap the authors' contributions or would\nrepresent an orthogonal contribution.\n\nThe normalize-and-predict learning framework relies on the ability of\nidentifying semantics-preserving transformations, embedded in logical\nrelation. How hard is it to find such semantics-preserving\ntransformation? Are you assuming those are known/available to the\nattacker? Would these transformations include side-effects depending on\nthe abstraction (program analysis) one relies on to extract features of\ninterest? Overall, I am quite intrigued by the benefits of the authors'\nunified framework that normalizes over relations that preserve semantics\nand adversarially train over the rest. However, from a practical\nperspective, one would need to consider several other constraints when\nreasoning on specific application domains (e.g., malware). Although I\nvalue the authors' theoretical findings, I am unsure whether the\nexperiments support such claims thoroughly. I'd be more at ease if the\nauthors had reasoned on the robustness of the semantics-preserving\ntransformation they propose (besides the fact these really depend on the\nunderlying program analysis abstraction the classifier relies on), as\noutlined further in [1].\n\nDon't get me wrong: this is an interesting paper that explores the\neffectiveness of the authors' defense. However, I believe it's worth\nunderstanding whether the attack the authors propose is realistic or\nthere are any loose ends that are better formalized in [1]. If so, it\nwould be more appropriate to understand how the authors' defense is\nrobust against adversarial ML attacks at test-time in the problem space\n(realizable attacks). More importantly, tho, I am concerned about the\npracticality of the approach. It is clear that if an object x and its\ncorresponding adversarial object x_adv share the same normal form, the\nprediction will be robust (as the authors rightly point out in Section\n4.2). But how easy is it to find such a normalizer? This is strictly\ndependent on the set of semantics-preserving transformation attackers\nhave at their disposal. In a way, this is exactly what [1] points out\nand consider as robustness to pre-processing. \n\nThe authors may want to see [2] to make sure to remove any spatial bias\nthat may inflate the end results (in the security domain, it is common to expect\nclass imbalance as it is representative of real-world settings).\n\n[1] https://s2lab.kcl.ac.uk/projects/intriguing/ (IEEE S&P 2020)\n\n[2] https://www.usenix.org/system/files/sec19fall_pendlebury_prepub.pdf (USENIX Sec 2019)\n\n## Edit after discussion\n\nI thank the authors for the clarification. I still like the work and believe it is promising. However, I don't find too convincing the arguments around problem-space and malware experiments, I am afraid. Also, it seems there is still experimental bias in the evaluation (on malware), which hinders a bit the opportunity to assess the actual effectiveness of the authors' approach. I would really encourage the authors to reason about the points raised in the review in a more principled way.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Qi1I8r1H219", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work investigates relational adversary which creates adversarial examples by transforming the original inputs via a logical relation. The authors analyze the conditions for robustness to relational adversary and propose a learning framework which learns and predicts over normalized training and test inputs. Since their framework may incur excessive loss in accuracy, the authors then propose a unified framework by combining input normalization with adversarial training and claim that their unified framework can preserve the optimal robust accuracy. Empirical results show that their unified framework can enhance model robustness on two real-world tasks.\n\nOverall, I vote for accepting the paper. I like the idea of relational adversary and the technique of selecting a reversible relation for input normalization in their unified framework. My main concern is about the clarity of the paper, especially its proofs. (see cons below).\n\nPros:\n1. The paper considers relational adversaries which create adversarial examples in a semantics-preserving manner by a logical relation. I think this problem is practical and important to the adversarial learning community.\n2. The proposed normalization procedure which guarantees robustness against relational adversaries is promising and might be applied to other kinds of adversaries. The robustness-accuracy trade-off analysis is reasonable, and the design for combining $N$\\&$P$ with adversarial training is also interesting.\n3. This paper provide experiments on two real world tasks to corroborate with their theory. The performance of their framework is good.\n\nCons:\n1. I have some questions about the proof of Theorem 1 in A.5. \n- In the proof of Claim 3, the authors denote $z$ such that $N_{R’}(x)\\to_ {R\\\\R’}^* z$. Then they show that $N_{R’}(x)\\to_{R\\\\R’}^* z$ implies $x\\to_{R}^* z$. However from the assumption that f is not robustly accurate over $(x, y)$ under $R$, it can be directly derived that there exists $z$ such that $x\\to_{R}^* z$ and $f(z)\\neq y$. Why the authors use the extra step?\n- In the last three line of A.5, the authors state that “f* is at least as robustly accurate as f”. This statement is a little confusing. If I understand correctly, the authors want to say that f* has at least the same robust accuracy as f. Is that right? Moreover, why the statement “f* has at least the same robust accuracy as f” is true? Since it is actually not so obvious to the readers, can the authors provide rigorous proofs?\n- The notation $\\to_{R\\\\R’}^*$ is misleading. I guess what the authors want to say here is that $x\\to_{R\\\\R’}^* z$ iff $x\\to_{R}^* z$ and $x\\not \\to_{R’}^* z$. Moreover, the notation $A(\\cdot)$ used in the first formula of Theorem 3 is different from that of the second formula. It would be better if the authors can point it out.\n\n2. There are some questionable inaccuracies in the proof of Claim 2 in A.4.\n-  what does the symbol $\\vee_{i\\in U}$ in Definition 4 mean? Taking a maximum over $i\\in U$? \n- In Claim 2, the authors state that $x_1$ and $x_1’$ satisfy the equivalence relation in Definiton 4 (what is U here?). However, it seems that $x_1, x_1’, x_2, x_3, x_4$ are components of the d-dimensional vector $x$, that is, all $x_i$s are scalar. Moreover, the sentence “iff any of the following is true:” is confusing. This sentence seems not to fit in the context well.\n- Can the authors explain more details on why the classifier must satisfy (5), (6), (7) and (8)? \n\n3. In Proposition 4 in A.6, the symbol $y$ in $l(f, z, y)$ is misleading. The readers might think that $y$ depends on $x$. In fact, here $y$ should be fixed for all $x\\in C_i$, isn't it?\n\n\nSome typos:\n\nIn the last four line of second paragraph of Section 2, “against to”-> “against”.\n\nIn the last line of Page 12, “Observation 2”-> “Proposition 2”.\n\nIn Theorem 2, $\\\\{0, 1\\\\}^n$-> $\\\\{0, 1\\\\}^d$.\n\nIn the second line of A.7 in Page 15, “bizzare”->”bizarre”.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-uhwsnIxjE2", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new framework, relational adversary, to study adversarial robustness under multiple (sequential) data transformations. The authors also made robustness guarantees based on the Normalizle-and-Predict scenario. Improved robustness is numerically presented on two tasks: malware detection (under add/substitute attack) and image classification (under joint hue and Linfinity perturbation). \n\nStrengths: \n1. The relation adversary perspective is (relatively) novel in studying adversarial robustness\n2. The same framework can apply to very different modalities, such as malware and image\n\nWeaknesses:\n1. The numerical results (especially on image classification) should be expanded to better support the robustness claim\n2. The normalize-and-predict part sometimes lacks clarity, and it's unclear how to select the normalization function\n\nDetailed Comments:\nOverall, the relational adversary framework, in my opinion, adds some novel insights for studying adversarial robustness. The malware detector experiment setup and performance better demonstrates the utility compared to the image classification results. \n\nI have some concerns about the current version, which are detailed below.\n\n1. For image classification task against combined Linfinity pixel perturbation and hue shift attack, it appears that the authors use the same attack hyperparameters in training and testing. Will the advantage in the proposed method over adversarial training still exist for different train/test hyperparameter settings? Since there are only two attack types, I suggest the authors try different parameters on Linfinity threshold and hue changes when testing the robustness and report the robustness trend in the full spectrum. \n\n2. If I understood correctly, this relation adversarial setting also applies to the multiple-perturbation setting, where each perturbation type can be viewed as one \"relation\". There are several existing works on multiple-type attacks, such as simultaneous/sequential perturbation with different Lp norms [R1, R2]. How will the proposed framework perform in multiple Lp-norm perturbation setting, and how does it compare to existing works?\n\n[R1] Adversarial Training and Robustness for Multiple Perturbations, NeurIPS 2019\n[R2] Adversarial Robustness Against the Union of Multiple Perturbation Models, ICML 2020\n\n3.  It seems difficult or unclear to select a proper normalization function for a given task. For image classification, it was not clear what \"normalization\" means in this concept. It was clearly mentioned in the malware detection setting but not in image classification. Please clarity how a normalization function is determined and how easy the principle generalizes across different tasks.\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors and reviewers for the lively discussions about the paper. All reviewers indicated that the work has merits and novelty however there were concerns about showing the benefits of the proposed method experimentally specially on malware applications. Given all, I think the paper needs a bit more work to be accepted. 

- AC
Decision: Reject