Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: ## Summary

The authors investigate relational adversaries, adversarial attacks that
lie in a reflexive-transitive closure of logical relation. The authors
focus on such attacks as they are motivated by attacks that are not
necessarily bound to small lp-norms (typical of security application
domains). The authors analyze the condition of robustness required in
this context and propose normalize-and-predict, a learning framework
with provable robustness guarantees. The authors further compare their
approach against adversarial training, which helps them to propose a
unified theoretical framework. While relational adversary attacks seem
successful against adversarial training models, the authors' framework
enhances their robustness.

## Strengths

+  Adversarial ML attacks that are not necessarily bounded by small
lp-norms are interesting and still not widely studied
+  Interesting intuition around the concept of normalization

## Weaknesses

-  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?
   
-  Likely experimental bias in the malware experiments?

## Comments

I found the paper well-written and motivated. I particularly liked the
fact the authors focus on adversarial attacks those that are not
necessarily bounded by small lp-norms (e.g., adversarial attacks "in the
problem space" [1]).

The authors explore an interesting problem that's been often neglected
but that plays a fundamental role in specific application domains (e.g.,
security). It would have been interesting to see how the authors' work
compared against a recently-published work [1] that reasons along the
same line. In particular, I wonder whether the theoretical framework in
[1], which reformulate adversarial ML attacks at test-time in the
problem space would overlap the authors' contributions or would
represent an orthogonal contribution.

The normalize-and-predict learning framework relies on the ability of
identifying semantics-preserving transformations, embedded in logical
relation. How hard is it to find such semantics-preserving
transformation? Are you assuming those are known/available to the
attacker? Would these transformations include side-effects depending on
the abstraction (program analysis) one relies on to extract features of
interest? Overall, I am quite intrigued by the benefits of the authors'
unified framework that normalizes over relations that preserve semantics
and adversarially train over the rest. However, from a practical
perspective, one would need to consider several other constraints when
reasoning on specific application domains (e.g., malware). Although I
value the authors' theoretical findings, I am unsure whether the
experiments support such claims thoroughly. I'd be more at ease if the
authors had reasoned on the robustness of the semantics-preserving
transformation they propose (besides the fact these really depend on the
underlying program analysis abstraction the classifier relies on), as
outlined further in [1].

Don't get me wrong: this is an interesting paper that explores the
effectiveness of the authors' defense. However, I believe it's worth
understanding whether the attack the authors propose is realistic or
there are any loose ends that are better formalized in [1]. If so, it
would be more appropriate to understand how the authors' defense is
robust against adversarial ML attacks at test-time in the problem space
(realizable attacks). More importantly, tho, I am concerned about the
practicality of the approach. It is clear that if an object x and its
corresponding adversarial object x_adv share the same normal form, the
prediction will be robust (as the authors rightly point out in Section
4.2). But how easy is it to find such a normalizer? This is strictly
dependent on the set of semantics-preserving transformation attackers
have at their disposal. In a way, this is exactly what [1] points out
and consider as robustness to pre-processing. 

The authors may want to see [2] to make sure to remove any spatial bias
that may inflate the end results (in the security domain, it is common to expect
class imbalance as it is representative of real-world settings).

[1] https://s2lab.kcl.ac.uk/projects/intriguing/ (IEEE S&P 2020)

[2] https://www.usenix.org/system/files/sec19fall_pendlebury_prepub.pdf (USENIX Sec 2019)

## Edit after discussion

I 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.
review_title: ICLR 2021 Conference Paper157 AnonReviewer4 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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). 

Strengths: 
1. The relation adversary perspective is (relatively) novel in studying adversarial robustness
2. The same framework can apply to very different modalities, such as malware and image

Weaknesses:
1. The numerical results (especially on image classification) should be expanded to better support the robustness claim
2. The normalize-and-predict part sometimes lacks clarity, and it's unclear how to select the normalization function

Detailed Comments:
Overall, 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. 

I have some concerns about the current version, which are detailed below.

1. 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. 

2. 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?

[R1] Adversarial Training and Robustness for Multiple Perturbations, NeurIPS 2019
[R2] Adversarial Robustness Against the Union of Multiple Perturbation Models, ICML 2020

3.  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.




review_title: New framework and angle to study adversarial robustness; more empirical evidence needed

final_score: rating: 7: Good paper, accept
review_content: 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.

Overall, 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).

Pros:
1. 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.
2. 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.
3. This paper provide experiments on two real world tasks to corroborate with their theory. The performance of their framework is good.

Cons:
1. I have some questions about the proof of Theorem 1 in A.5. 
- 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?
- 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?
- 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.

2. There are some questionable inaccuracies in the proof of Claim 2 in A.4.
-  what does the symbol $\vee_{i\in U}$ in Definition 4 mean? Taking a maximum over $i\in U$? 
- 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.
- Can the authors explain more details on why the classifier must satisfy (5), (6), (7) and (8)? 

3. 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?


Some typos:

In the last four line of second paragraph of Section 2, “against to”-> “against”.

In the last line of Page 12, “Observation 2”-> “Proposition 2”.

In Theorem 2, $\\{0, 1\\}^n$-> $\\{0, 1\\}^d$.

In the second line of A.7 in Page 15, “bizzare”->”bizarre”.
review_title: Official Blind Review #3 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

In 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.

Writing 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.
review_title: Interesting formulation to defend against adversarial attacks

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