Towards Understanding the Robustness Against Evasion Attack on Categorical Data
Authors: Hongyan Bao
Yufei Han
Yujun Zhou
Yun Shen
Xiangliang Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: robustness certification
adversarial learning
categorical data

Abstract: Characterizing and assessing the adversarial vulnerability of classification models with categorical input has been a practically important, while rarely explored research problem. Our work echoes the challenge by first unveiling the impact factors of adversarial vulnerability of classification models with categorical data based on an information-theoretic adversarial risk analysis about the targeted classifier. Though certifying the robustness of such classification models is intrinsically an NP-hard combinatorial problem, our study shows that the robustness certification can be solved via an efficient greedy exploration of the discrete attack space for any measurable classifiers with a mild smoothness constraint. Our proposed robustness certification framework is instantiated with deep neural network models applied on real-world safety-critic data sources. Our empirical observations confirm the impact of the key adversarial risk factors with categorical input.

Published as a conference paper at ICLR 2022
TOWARDS UNDERSTANDING THE ROBUSTNESS AGAINST EVASION ATTACK ON CATEGORICAL INPUTS
Hongyan Bao"
Yufei Han
King Abdullah University of Science and Technology hongyan Nongyan.baoBkee www..bakkkks..... .ww.ssteddu... edu.
INRIA
yufei han
Yujun Zhou
Yun Shen
King Abdullah University of Science and Technology yujun. zhou@kaust. edu. sa
NetApp f
yun. swn.sheeeetpp.pcomm com
Xiangliang Zhang : University of Notre Dame xzhang33ed @endddecu
ABSTRACT
Characterizing and assessing the adversarial risk of classifier with categorical inputs has been a practically important yet rarely explored research problem. Conventional wisdom attributes the difficulty of solving the problem to its combinatorial nature. Previous research efforts tackling this problem are specific cases and heavily depend on domain knowledge. Such limitations prevent their general applicability in real-world applications with categorical data. Our study novelly shows that provably optimal adversarial robustness assessment is computationally feasible for any classifier with a mild smoothness constraint. We theoretically analyze the impact factors of adversarial vulnerability of classifier with categorical inputs via an information- terthhhoreticc adversarial risk analysis. Corroborating these theoretical findings with substantial experimental study over various real-worke categorical datasets, we can empirically assess the impact of the key adversarial risk factors over a targeted learning system with categorical inputs.
INTRODUCTION
Categorical data pervasively exist in real-world safety-critical Laaiine--aaninn-a---eee (MLaaS) applications, such as ML-driven intrusion detection and digital healthcare. The vulnerability to attacks by intentionally crafting categorical signatures raises concerns trust and utility of the ML- based analytic services. Characterizing and assessing adversarial robustness on categorical data can thus help evaluate the reliability of the core ML models and flag potential evading efforts. For a classifier f with categorical inputs x, the adversarial risk of f under evasion attack can be formulated as follows.
Definition f f- y denotes a classifier with categorical inputs x. Let Hx.y denote the joint distri- bution of (x.y). The expected adversarial risk of the classifier f under evasion attack is formulated as:
Radv
sup
((f(E).))
(x.y)-Pxxy) &0l
where is the misclassification loss function, x and & are an umperturbed and the generated adversarial sample respectively. denotes the attack budget of evasion attack. is correctly classified ( (f(x)= y)).
Intuitively, classifier is more robust against adversarial perturbations, if its adversarial risk is low given the attack budget limiting the number of changed categorical features. Unlike continuous data, categorical variable be valued with only categorical value among others. These categorical
"The first two authors contributed equally.
'hhe author contributed to this work while at
4 Corresoonding author. Dr. Zhang is also affiliated with King Abdullah University of Science and Technology

---

Published as a conference paper at ICLR 2022
values have no intrinsic ordering to the categories. Evasion attack manipulating categorical in inputs
is in nature an NP-hard knapsack problem. The discontinuous nature raises two fundamental yet rarely addressed questions to evaluate the adversarial risk categorical data in practice:
Q1 What are the key factors determining f"s adversarial risk Radv on categorical data? ? Q2 For general elassifier f, can assess the adversarial risk of f with categorical inputs with provably accuracy guarantee? ?
Despite recent efforts of adversarial vulnerability exploration with discrete data, both questions remain open for several reasons. First, the discontinuity of categorical space prevents the direct use of the progiess
progress on adversarial risk analysis with continuous data. The local subspace assumption of lpbounded ad adversarial attacks does not apply to the categorical features (Hein & Andrushchenko
2017 Wang al. 2018 Fawzi et... 2016 Gilmer et. 2018 DD. Yin atal. 2019]KKiim & Loh| 2018 Tu
et al. 2019). Second, most practices of discrete adversarial attack are domain specific and depend heav-
ily on domain knowledge. (Bojchevski & Günnemann 2019 Bojchevski & Günnemann, 2019 [uugner & Gunnemann 2019) focus on building differentiable surrogate functions to Graph Neural Networks to Facilitate searching for feasible poisoning edits over graph structures and node attributes. (Narodylska)
& Kasiviswanathan 2017 Croce& & Hein 2019) conduct Lo-norm perturbations only within local
image areas containing sensitive features for image classification. (Qi et al. 2019 Wang et al.) (2020) require non-negativity on the parameters of deep neural networks to deliver provably accurate greedy attacks via submodular function optimization. The non-negativity constraint is unnatural for real- world ML practices. It does harm the utility of the classifier. For more general classifier with categorical inputs, a provably optimal and domain- agnostic method for attack and ad odvessarial risk evaluation is yet establish. Using greedy search or the well-known Branch-and- and-Bound method on general knapsack problem provides no optimality guarantee of the solutions, thus can produce arbitrarily bad results.
Our study aims to address these two questions mentioned above from both theoretical and empirical perspectives. First, we derive an information-theon classifier. It unveils that the informativeness of the inpul categorical instance, the sensitivity of the perturbed categorical features and the information geomelry property of the targeted classifier are the three key factors jointly determining adversarial vulnerability of the classifier.
characterization of the adversarial risk of a
Second, our study adopts an assess- ussess-by-attace strategy. We show that assessing adversarial robustness of any measurable classifier with categorical inputs can be cast to a weakly submodular maximization problem, with a mild smoothness condition. can thus be solved using a simple yet efficient greedy attack strategy with provable approximation guarantees. The theoretical findings not only explain the empirical success of the greedy search strategy generate adversarial textual and image samples (Gong) et 2018 Yang el. 2018 Narodytska & Kasiviswanathan) 2017), but also pave the way to a domain- agnostic adversarial robustness assessment on categorical data with provable optimality guarantees.
Third, we instantiate the domain-agnostic adversarial risk characterization and assessment with a widely used DNN classifier, i.e. Long Short-Term Memory (LSTM) and three different categorical datasets in Section 4 These datasets are collected from various real- real-world applications. The experimen- tal results confirm the impact of the 3 risk factors over the adversarial vulnerability of the DNN classifier.
2 RELATED WORK
Tremendous efforts have been made to vulnerability measurement of classifier under evasion attack
(Hein & Andriushchenko 2017: Wang et al. 20188; Fawzi et al., 2016)) Gilmer et al. 2018 Weng
al. 2019 Sinha et [ Cohen et al.) 20197 et al. 2020 D. Yin al.) 2019 Khim & Loh 2018 Tu et al. 2019). Most of the previous works focus on evaluating robustness against / -norm perturbations on continuous data. They all assume adversarial samples locate within a smooth ball around an input instance, which doesn't 't hold for categorical data. In contrast, Tu et al. (2019) covers both numerical and categorical data. It bounds the adversarial risk with a local worst-case risk over a p- w-wsserrsttenn ball centered at the training data distribution. This work associates the adversarial risk of classifier with its rademacher complexity. Nevertheless, we argue that the adversarial vulnerability of classifier is determined by not only the characteristics of the classifier, e.g. model complexity, but also the properties of the training/testing data instances.
Pioneering works of evasion attacks with categorical inputs depend on domain-specifi knowledge to facilitate the attack exploration. Kuleshov et al. (2018); ( et al. (2016)) (2016)]MMyato et al. (2016);
Samanta & Mehta 2017); ) Gao et al. 2018 Yang et al. 2018): Gong al. (2018): Ebrahimi et al.
2

---

Published as a conference paper at ICLR 2022
(0018) Narodytska & Kasiviswanathan (017); Croce & Hein (2019) focus on replacing individual words/phrases to cheat text classifiers, or modifying pixel intensities to bias image classification results. These methods use heuristic semantic rules, e.g., replacing words with manually defined candidate synonyms and constraining the word change to preserve readability and semantic integrity. Narodytska & Kasiviswanathan (2017); CCoce & Hein (2019) narrow down the search range to the pixels with high pixel-wise sensitivity for image classification. Despite of the sounding empirical results, there no guarantee on a successful attack within the attack budget.
Bojchevski & Günnemann 2019); Bojchevski & Günnemann 2019); D.Zugner et al. (2019) D. Zügner
Günnemann 20 Akbarnejad & Günnemann (2019) adopt adge-flipping and node attribute perturbation to poison graph data mining pipelines, e.g., graph neural networks and graph embedding models. The key idea to introduce relaxed surrogate functions the combinatorial attack objective and then solve the relaxed optimization problem instead. Notably, [DZuugner et al. (2019); D. Zügner Günnemann (2018); Akharnejad & Günnemann (2019) define the attack objective as sum of smallest eigenvalues of the adjacency matrix of given graph. Though it is not explicitly claimed, it is intrinsically a submodular maximization problem.
Qi et al. 2 Wang al. 2020) unveil that simple greedy search can deliver provably effective attacks against DNN classifiers without comain-specific heuristics, if all the link weights between neurons non- -egaaivaee.. Non-negativity of the parameter guarantees striet submodularity of the attack objective. However, brings significantly deterioration of the classifier's accuracy, which not applicable for real-world learning tasks.
ROBUSTNESS CHARACTERIZATION AND ASSESSMENT
(x. of categorical attributes. Each x; takes any of m (m 2 1) categorical values. The classifier if outputs decision probabilities fyx (k 11,.3....., with respect to different class labels. In practicess, each categorical value x is cast to D-dimensional pre- trained embedding vector, e.g., ef ER a 1,2,,.... To represent an instance x with the embedding vectors of its category values, define binary variables b bb (b)),, b=bbb), j=1,2....,,m where by =1 when the j-th attribute value is present for x; and b/ =0 otherwise. An instance x can then be represented by R tensor with x (1.1.) =b/f/ Let b= (b/) indicate the adversarial modifications introduced into b. For a perturbed R, its b 4 Depending on the type of attacks to implement, e.g., insertion, deletion or substitution, b differs from in different ways. Without loss of generality, let уи denote the true class label of x and all the other yı (1,.,K.. 1}) are the potential targets of an evasion attack. The goal of attack is to make fyx (x, as low as possible and increase fyx (x.b) of a fixed k (targeted attack) or any of (1..... inon-targeted attack) as high as possible simultaneously. We focus non-targeted evasion attack, and leave the targeted scenario for future study.
We assume input instance x=
3.1 INFORMATION-
CHARACTERIZATIO OF ADVERSARIAL VULNERABILIN
Theorem For an instance (x.y) and training set S sampled from the same underlying distribution Hx,y. fEH is trained using with a deterministic training paradigm. The expected adversarial risk
Radv defined in Eq can be bounded as in 2
2 if the loss function E Radv adopts the zero-one loss.
21(x:y.S) - S)/y:S)/2+const
Radv 1
(2)
logk
1xx sup -((:,,)))
(d)
where const denotes a constant term. diff( indicates the set of categorical attributes modified in the attack. (xx:y,S) denotes the mutual information between the feature x and the pair of label y and training set S. Tix is the supremum of the difference between the mutual information before and after adversarial perturbation, noted by (S: and (f::y.S) respectively. I(fy:S denotes the mutual information between S and
Theorem I unveils the three impact factors jointly determining adversarial vulnerability of the targeted classifier o (for answering QI in Section[T] [T). The proof is given in Appendix[A] In Eq a lower mutual information (x: indicates higher adversarial risk, i.e., Radv has a higher lower bound. A lower
3

---

Published as a conference paper at ICLR 2022
(xxy denotes weaker consistency between the input instance (x,y) and the training set S. The clas- sifier trained by S thus produces weaker decision confidence for such (x.y). With (x.y) dropped to the ambiguous zone near the classification boundary, the classifier is more prone to adversarial perturbation.
A higher SS) leads to a higher adversarial risk according to Eq 2 The mutual information (() reflects the dependence between the classifier f and the training set S, which can be considered as a lower bound of the VC-dimension for countable hypothesis space f E ' (Xu & Raginsky 2017] Zhu al. 2020). A higher (y;))) thus denotes that / more likely suffer from being overfitted to 5. Model overliting is one of the causes of adversarial vulnerability (Tu et al. 2019). Resonating with the association between / (() and adversarial risk, three popularly used robustness enhancement methods controlling the classifier's ' complexity and overfiting risk can potentially adjust the ad adversarial
vulnerability of the classifier with categorical inputs. 1) Adversarial training (Miyato et al. 2016)
Sinha et al. 2018 Florian et al. 2018 Wang et al. 2019, Shafahi et al., 2019). The adversarially
retrained classifier i is less correlated with the original training set S compared to fa which reduces
(S) and may help mitigate the adversarial threat. 2) The addition of nuclear norm regularization over the classifier's s parameters in the training process (Ravi et al. 2019 Tu et al. 2019). The resultant regularized classifier has a controlled model complexity, which can potentially reduce the adversarial risk. 3) Random smoothing (Lee et al. 2019 Levine & Feizi, 2020; Dvijotham et al. 2020) [Boj ct al. 2020). Following (Cohen et al. 2019). 9). this defense method randomly selects and flips the input categorical features of the targeted classifier. The randomly perturbed classification output is less correlated with the training data S's distribution, which may reduce adversarial risk.
A higher yı in Eq indicates a higher loss of predicative information by changing x to &, and thus a higher adversarial risk. In this sense, the vulnerability of the classifier depends on the sensitivity of the attacked categorical features with respect the classification task.
3.2 Scoring Robustness via Set Function Optimization
We formulate the assessment of adversarial robustness level on categorical data as a set function maximization problem: we aim at finding a minimal set of categorical feature perturbations /=dif( b.b), with which the maximum gap between the classification confidence on any wrong label k and the correct label K is larger than a predefined threshold I'. The size of the minimal perturbation set is used to assessment adversarial robustness of f over the input instance. Within the perturbation budget e, a smaller/larger |4] provoking the alert indicates that the classifier's s output on the input x is more/less vul- nerable w.r.t. adversarial perturbation in the categorical feature space. We consider both the pessimistic (in Eg. (4) and optimistic scenario (in E from the defender's 's perspective for robustness scoring.
(1)=s(()=
max bi-1... bi-1.....ddg b.di
max (mJ)
S.J. my 2r, M1s
(4)
6/- 64-1...m
sopiim (1)=
min
max 6f-1...m
(m))
S.t. my 11. 11|se
(5)
b b.....n..ddf(bbbb
where f ke kc(l....KK- K-1)
(Fx (x,b)) (x,b) is the gap defined with input instancex. f {--1,0) max.
and my 2 0 correspond to correct and wrong classification respectively. I is a threshold reflecting different levels of tolerance to the perturbation of the classifier's 's output. my 2 I then triggers alert of potential adversarial attack. Safety-crities domains, such as cyber security, prefer a lower I to provoke alerts even with small yet suspicious input perturbations.
Observation 1 With the threshold - O, pess 2 O derived by solving the pessimistic assessment problem in E produces an empirical estimate of the expected adversarial risk of with an input instance (x.y) sampled from Mx.y.
We leave the derivation of this observation in Appendix B Eq. is a bi-level optimization problem. The inner level seeks the optimal change of the category value a given categorical feature, in order to produce maximum possible perturbation on the classifier's output. The outer level finds the optimal combination of different categorical features for maximizing my within the attack budget. [/] is thus a pessimistic robustness assessment with respect to knowledgeable adversary. The adversary can locate the most effective modification for both individual categorical features and the combination set of the categorical features.
In contrast, |/| to Eq. reflects an optimistic robustness assessment with respect to an oblivious adversary. In practices, an adversary can be limited by the knowledge about the targeted classifier
4

---

Published as a conference paper at ICLR 2022
and/or the query budget. Such an oblivious adversary can only locate the effective category values to attack for a given categorical feature, while can't 't find the optimal feature combinations to solve the outer-level optimization.
3.3 Provably Accurate Robustness Assessment via Weakly Submodular Maximization
Exactly solving Eq and Sjss still NP-hard. To answer Q2 in Section Theorem and Theorem 3 elaborate the optimality guarantee of solving both robustness assessment problems via computationally efficient greedy search, for any classifier meeting the smoothness condition in Definition 2
Definition Smoothness Condition of f. Let Q = (p.q), p.q E R" and f: RR be a Lipschitz- continuous and differentiable function. A function f is Mamsooh -smooth on 52, for any (p.q) e ma E and Ma E R 6
p) satisfies:
m2 2
1 10-pll - 11p-1.
(6)
Different from (Elenberg al., 2018). 6 controls only the fluctuation of the function value by varying the input from p to q and vice versa, regardless of convexity or concavity of f. It allows broader choices of the classifier's is architecture. With y-weak submodularity (Elenberg al. 2018
Santiago & Yoshida 2020) defined in Appendix we establish Theorem 2
Let Qu = ((b.6)) (diff( b.b) s &. Iifii b,b') S C. b,6') 5. 13, where and d' denote two sets of attribute changes. If the classifier fy. (x) (k=I.... follows the regularity condition given by (m..0g. MM..,,) )-..a..-smoooessss constraint on S2g, the pessimistic and optimistic robustness assessment (with Eq|A
Theorem 2
follows
Eq]Aand and 5 can be formulated respectively as monotone and non-monotone ye-weakly submodular maximization. Let Ex = =fy (x. (x.b) (V (x.b).B'-b), and fy denote the elements of J (x.b) corresponding to the difference between and b', where v dibi((bbbbb) The submodularity ratio pess for the pessimistic robustness assessment bounded as:
Y
pess
min k= I=1,...,K K
11,.fo (x,bl, 4.m,. K1// for EK 2 O, pess
2mL
where Ykek, 2
TkcK,< 2 IV (x, (1V (x. b)vll2
T8 (1.b))l2MMM,.... 1//2
2mig.
My.a, (51/2) for EK < 0, KK.6 2 T& (x.b),
Syv (x,b)vll2 - Mx,0, (112) (21/2)ooo for EK 2 0, and Y pess 2
[V (x.b)v l.b))ll 15172 for eg <0. Similarly, the submodularity ratio Y optim of the optimistic assessment is:
// (x.b), (b+mmx o 151/2
optin
min Fl..... K
(xx,
(8)
where
optin YEeK 2M (IV (x, (x, ma K (22 for ck 2 0, Y KEKK
optin
V bxx
fi (x,b), 12 12 1C1/2
Th (x,bl, M 1/2 for eg =0.
Y K.6
optim
Tv (lab).lllttxxx.... 1T/E for eK 2 O, and optim
19g. (x.b), lattmm 11/2
k 1M Wi (x.b), lle-m 11/22 for EK 0.
I (x.b).l
Enjoying the weak submodularity, the pessimistic and optimistic assessment be derived by greedy search with provable accuracy. We present a Forward Stepwise Greedy Search (FSGS) algorithm for deriving the pessimistic assessment (Eq(4). Due to the non-monotone objective function of the optimistic assessment (Eq a stochastic variant of the standard FSGS, namely Randomized FSGS (RandGS) is adopted, following the suggestion in (Buchbinder al. 2014). We give the pseudo codes of FSGS and RandGS in Algorithm. I and 2 in Appendix Compared to FSGS, the difference in RandGS to randomly select one of the top-ranked candidate features contributing with the largest marginal gain m to the objective function. Theorem 3 gives the approximation guarantee of the pessimistic and optimistic robustness assessment using FSGS and RandGS respectively.
Theorem 3 For a (mage-Ma M -smooth classifier f, the approximation quality of the solution I to Eq 4 and Eq is bounded respectively as
y (1]++
-t 5(1- 3l (ppess) (PessinisicAAssesmeen))
[mg (0)2
1
e -v
Im (1r (optin) (Optimistic Assessment)
optm
where pews and y optim are the submodularity ratio Eq. 7 and Eq. respectively. lpess and loptim are the true optimal solutions the two problems.
5

---

Published as a conference paper at ICLR 2022
With Theorem B the Q2 in Section I is fully addressed. Notably, any classifier with a finite Lipshitz constant meets the smoothness condition. For practical estimation, Ma₃ can be computed as local Lipshitz constant of if 0 in Definition 2 (or fx) <0). Furthermore, ma; can be calculated as the local strong convexity constant of [(x if > O in Definition (rr (x(x if E <0). Recent works (Fazlyab et al.] 2019) Jordan & Dimakis 2021 have shown that large number of neural networks are Lipschitz continuous, such as the fully- conneccode neural networks with ReLU, sigmoid, and tanh activation functions. The FSGS based robustness assessment method can thus be applied to most
DNN-based classifiers that are popularly adopted in real- world applications.
Theorem 3 also reveals that the role that the smoothness of fy plays in characterizing the solvability of the robustness assessment problem. As indicated by Eq. 7 and Eq. 8 smoother fx with smaller mg.0q
and My.ae has a higher submodularity ratio (y and Vk. optim) With a submodularity ratio closer to
1, both FSGS and RandGS can obtain better approximation quality to the underlying optimal result of the robustness assessment, according to Eq. 9 Comparing Eq. 7to 8 the submodularity ratio of the pessimistic assessment is higher than that of the optimistic opponent. The greedy search has lower approximation quality under the optimistic setting. The optimistic assessment is thus generally higher than the pessimistic assessment. It echos with the intuition that classifier is more vulnerable to knowledgeable adversary than an oblivious one.
3.4 ORTHOGONAL MATCHING PURSUIT GREEDY SEARCH FOR ROBUSTNESS MESESSMENT
Both FSGS and RandGS need to traverse all the combinations of candidate attributes and the subsets of the selected set of attributes. In the worst case, they require Σ (n-11) *m mm=2 objective function evaluations for 7' iterations, where n denotes of the number of categorical features in an instance x and each feature choose any of the m categorical values. Large and are usually witnessed in the real-world data. Both methods thus are costly in querying the oracle classifier in such real-world cases.
In (Wang et al. 2020), an orthogonal matching pursuit guided greedy searching strategy (OMPGS) is introduced to address the query bottleneck of primary greedy search in evasion attack on discrete data. In the context of attack, this method computes fyy (the gradient fy w.r.t. the binary indicators b of unmodified categorical features). The magnitude of the gradient measures the capability of each candidate feature in reducing the classification confidence of the correct label. In this sense, OMPGS narrows down the candidate attributes to those that best correlate with the orthogonal complement of the subset of the attributes already selected in greedy search. The query complexity of OMPGS is thus independent of n and m. Due to the space limit, the algorithm implementation of OMPGS are explained in Algorithm Appendix B
We apply OMPGS to speed up the solutions to both the pessimistic and optimistic assessment problems. The approximation guarantee of OMPGS given in (Wang et al. 2020) only explains the provably accuracy of using OMPGS in the pessimistic assessment. In this work, we further bound the approximation accuracy of OMPGS to derive the optimistic assessment in Theorem Comparing to 33 OMPGS achieves lower but similar approximation accuracy to the underlying optimal solution to the optimistic assessment (Eq.5).
the approximation quality of the optimistic assessment score |i] obtained by OMPGS is bounded as in the followings:
Theorem 4 Following the notations in Theorem 2 and Theorem 3
| (1)2 v
*Im Im (ooiim v = max (<x
S (x,b)y11
S (x.b))lll+m.ma 15/2
(10)
2M, (II - 12122)
IV (x.b)),)
In both of the pessimistic and optimistic assessment, the gradient magnitude used by OMPGS can be interpreted as an upper bound of the increase my by adding adversarial perturbation to a previously unmodified feature, as shown in Appendix E Notably, the gradient used in OMPGS is not taken directly with respect to the categorical features. Instead, the gradient taken with respect to the binary indicator variable b/ (see Section.3). We rank the categorical features according to the magnitudes of the gradients with respect to different b/- A higher gradient magnitude indicates that the corresponding categorical feature X, =x/ can contribute higher marginal gain of my. OMPGS narrows down range of greedy search. Only the top ranked candidate features are considered to modify.

---

Published as a conference paper at ICLR 2022
Table 1: Pessimistic and Optimistic Robustness Assessment IT/. lower/higher assessment score
indicates weaker/stronger robustness level. SR is the success rate of attack. OVF indicates SR=0.
Yelp
IPS
Splice
GreedySeearch
P/O
SK
Med (Avg)
SR
Med(Ave)
SR
Med(Avg)
-04
0.88
(1.55)
0.80
1(22)
0.91
(1177)
FSGS/
0.98
[d.9)
0.80
T(2))
0.91
T(T7)
RandG8
918.1)
0.35
102
OVF
0
0.09
12
0.35
T(1.))
0
OVF
GradAttack
P
0.4
0.84
13..5)
0.59
10.88
0.72
((3.7)
0.76
201.7)
0.59
T0.7)
0.72
335.7
0.4
0.98
((2.0)
0.91
((16)
0.74
2(2.1)
OMPGS/
2(2.5)
((..)
0.74
2(2.3)
RandOMPGS
-0.4
0.63
(6.9
0.35
(3344)
0
OVF
0.52
(7766)
0.35
(3.6)
0
OVF
EXPERIMENTAL STUDY
We instantiate the study with standard LSTM based classifiers trained on three multi-class datasets collected from real-world applications of Text analysis, Cyber security and Biomedicine.
Yelp-5 (elp)(Asghe
2016). The Yelp-5 reviews dataset obtained from the Yelp Dataset Chal- lenge in 2015. We use the reviews containing 650K training and 50K testing samples with the classes from 1 star 5 stars for learning classifier. Each word is categorical feature with 300-dim embedding.
Intrusion Prevention System Dataset (IPS) (Wang et al. 2020). The IPS dataset has 242,467 instances, each of which is 20-step attack sequence and represented by x e 2R2000100007 because each step can be a categorical value from 1,103 different malicious actions embedded in 70-dim space by word embedding. An x is classified with 3 labels: attack type 1, attack rype 2, and others.
Splice-junction Gene Sequences (Splice) (Noordewier et al. Each one a gene fragment of 60 categorical features with values in { ''A', 'G', 'C', 'T', 'N'). Learning an embedding for each value with 30-dim, one instance is given x 60055+30 The task predict each splice instance as an intro-exon boundary (IE), an exon-intro boundary (EV), or neither of them.
1991) 1. This dataset has 3,190 samples.
The LSTM-based classifiers with ReLu activation function and dropout achieve accuracy scores of 0.61, 0.92 and 0.95 respectively for Yelp. IPS and Splice. More details about the datasets and the experimental setting are given in Appendix [:I]] assessment framework, we also include additional results on binary- classifccsii datasets using Convolution Neural Networks (CNN) in Appendix
To strengthen the universality of the robustness
The experimental study is to address questions below:
1) What's 's the robustness assessment result of a targeted classifier? (Empirically evaluate the answer in Theorem 2,3 and 4 to Q2 in Section[4.]] For the classifier trained on each dataset, we first find the robustness assessment [Z] for each data instance. We report the median and mean value of all the |/| derived on the dataset. A lower/higher median value indicates weaker/stronger robustness of the classifier to the adversarial attack over the given data set. The tolerance threshold I' is tested on -0.4 and 0 to assess proposed assessment method with varied tolerance to adversarial threats in safety-critical applications. Different greedy search methods are compared on their assessment result. Besides FSGS and OMPGS (for solving Eq and RandGS and RandOMPGS (for solving Eq also include Gradient- prudient-basedaaa Attack (GradAnack) from QQi et al., 2019) in the evaluation. GradAntack tackles only the pessimistic assessment problem. The comparison with GradAtlac is to verify the merit of FSGS and its variants in solving the robustness assessment problem of a general classifier. For RandGS and OMPGS, empirically choose 10 candidate features in each iteration of greedy searct[]
2) Can the informationnthhoreee using the proposed robustness assessment? (Empirically evaluate the answer in Theorem Q1 in Section 4.2 and 4.3). We verify an increase of risk on Xi,, with lower mutual information, i.c., (x:y.S), and verify an increase of robustness by reducing ((fy:)). 3) We compare the time complexity of FSGS, OMPGS and GradArtack. Furthermore, we evaluate the averaged running time and the averaged iterations of the three methods over Yelp, IPS and Splice datasets. As shown, both FSGS and OMPGS stop early the search with less loops than GradAttack. OMPGS costs much fewer queries and less running time than FSGS. Compared GradArttcck OMPGS has better chance to select the really useful feature modifications, thus costing fewer loops. We provide the results Appendix F3 due to the space limit.
characterization of adversarial vulnerability in Theorem be verified
1(x7m, by
FSGS,OMPGS
Implementations available
7

---

Published as a conference paper at ICLR 2022
4.1 ROBUSTNESS ASSESSMENT WITH GREEDY SEARCH
Besides showing the median and mean of the assessment score [1] (Med(Avg)) of the testing instances, we also report attack success rate (noted as SR in the tables), i.e., the fraction of the testing instances on which the greedy methods can push f greater than the tolerance threshold within the one-hour time limit. With similar median/mean values of [/], a lower SR also indicates stronger robustness of the classifier. If the greedy search fails to push f to surpass the threshold I for all the testing instances within the time limit, we note this situation as OVF (an abbreviation for overflow) and SR = 0 in the tables. P/O denotes the pessimistic optimistic assessment respectively.
Table T shows several interesting findings. First, for both the pessimistic and optimistic robustness assessment, a lower tolerance threshold I results in lower scores over all the datasets. This observation is consistent with the intuition of setting the tolerance threshold. A lower tolerance threshold helps choose more worst-case resilient classifiers. Our study allows for the analysis with different vigilance levels. Second, as expected, the pessimistic robustness assessment scores are always significantly lower than those of the optimistic assessment, and the SR value is much lower on the optimistic assessment scenario. Due to lack of query capability and knowledge about f. it difficult for the oblivious adversary to locate the sensitive features.
OMPGS and RandOMPGS produce similar robustness assessment scores, compared to FSGS and RandGS. Compared to evaluate each candidate features as in FSGS/RandGS, OMPGS improves the search efficiency using the gradient based heuristic guidance. On IPS and Splice, FSGS// needs 217.65 and 123.51 seconds on average on each data sample for the pessimistic and optimistic assessment. In contrast, OMPGS/RandOMPP and optimistic assessment, more than 700 times faster than FSGS/RandGS. GradAttack, in contrast, produces much lower SR than FSGS and OMPGS in the pessimistic assessment setting. As discussed in Section[] 2 the greedy search in GradArtack ignores the combinatorial effect of the candidate features and the previously modified features, which leads to worse approximation quality and much less efficient attacks compared to FSGS and OMPGS. The results echo the theoretical analysis. With significantly lower SR, GradAttack can not provide an accurate answer the robustness assessment problem.
costs only 0.24 and 1.59 seconds for the pessimistic
We conduct one-factor-aa -t-oor--t---aee at-a-time sensitivity analysis on each dataset (Cambell et al. 2008) to measure the sensitivity of features in the classification task. Given a data instance, we change each feature while keeping all the others fixed. The averaged change of the classifier's s output over all the testing instances used as the feature- Srature-wise sensitivity measurement. A larger value indicates that the classifier's s output is more sensitive to the change over the corresponding feature. We find that the top-sensitive features also appear as the most frequently selected features by TSGG,,rrdAAtde and OMPGS. Details about the sensitivity analysis can be found in Appendix [F:4] The interesting overlapping between the attributes which are useful for attack and the top-ranked sensitive attributes confirms our intuition about the association between feature sensitivity and adversarial vulnerability of the classifier.
4.2 ROBUSTNESS VS FEATURE INFORMATIVENESS
According to the discussion in Theorem 1 a lower (x:y,S) indicates a higher adversarial risk on the input instance (x,y), implying a smaller robustness assessment score. To verify such impact of feature informativeness, we compare the robustness on x and on x that has a lower mutual information, i.e. [(x S) (S): The sample xim is constructed as those on the half-way of pushing the my of the original sample x to surpass I, For each dataset, we select the instances requiring at the least two modified features in order to deliver successful attack. These instances are treated original. There are 125, 414 and 324 original instances in Yelp, IPS, and Splice respectively. The results in Table(2cooffimm that the classifier becomes less robust to adversarial modifications over xt,,, samples in the ambiguous zone, i.e., higher SR and smaller [/] on the t/m samples than the original samples x.
4.3 ROBUSTNESS WITH DEFENSIVE TECHNIQUES
As discussed in Theorem 1 reducing I(fr:), the dependence of a classifier over the training set S, improves the classifier's s adversarial robustness. We tune classifier via adversarial training (AdvC), the nuclear-none based regularization (NuR) following (Ravi et al. 2019) and random smoothing by (RS) as suggested in (Boj. et al. (020) to reduce (S), and then evaluate if the pessimistic robustness assessment becomes higher, e.gg, descrese of SR. To adopt adversarial training, we solve Eq. 4 using
8

---

Published as a conference paper at ICLR 2022
Table 2: Robustness Assessment vs Feature Informativeness, reported at 0 results in higher adversarial risk (higher SR, smaller ((]) Xln than original x.
:y.5) (x))))))
Velp
IPS
Splice
GreedySeearch
P/O
Sample
SR
Med(Avg)
SR
Med[Avg)
SR
Med(Avg)
original x
0.98
1 (119)
0.80
(1.2)
0.91
1 (1.7))
P
ESGS/ RandGS
Mlui
1.00
(1.7)
0.95
((.1)
0.99
(1.2)
onginal
0.09
(2((1.8)
0.33
((13)
OVF
0
Myn
0.94
6(6.0)
0.65
1(1.2)
0
OVF
onginal
0.97
22.5)
0.91
(1..)
0.74
2(2.3)
P
OMPGS/ RandOMPGS
Mani
0.99
2(2.4)
0.93
((.3)
0.94
((.S)
original
0.97
(4.6)
0.35
(3.6)
0
OVF
1.00
(4.5)
0.57
(3.3)
0
OVF
Table 3: Pessimistic Robustness Assessment (T 0) after Robustness Enhancement by reducing I(fr:)). JSR is the the amount of SR decreasing comparing to the SR value with r== in Table
Yelp
IPS
Splice
Model
Algo.
SR
Med(Avg)
SR
sk
Med(Avg)
SR
jsk
Med(Avg)
AdvC
ESGS
0.84
0.13
((1.))
0.74
0.06
T(14)
0.85
0.06
2(2.1)
OMPGS
0.83
0.13
2(2.3)
0.60
0.31
2(2.2)
0.63
0.09
((2.8)
NuR
PSGS
0.72
0.25
1(1.9)
0.79
0.01
T0.1)
1
-0.09
T(14)
OMPGS
0.68
0.30
2(2.4)
0.63
0.28
((.0)
0.72
0.02
(2.5)
FSGS
0.76
0.21
(118))
1.00
-0.20
((14)
0.91
0
(1.9)
RS
OMPGS
0.74
0.24
2(2.2)
0.95
-0.04
T(1.))
0.78
-0.04
2(2.2)
SRS (Boj. at... 2020)
1.0
2
1.0
1.0
OMPGS until the value of my drops into the interval [-0.2,0.0]. The resultant modified instances are
used for adversarial training. The regularization parameter of the nuclear-norm regularized training method is chosen following (Ravi et 2019). The random smoothing is conducted by randomly flipping the values of input categorical features (RS) with p. 0.6 and p. = 0.01 as suggested in (Boj. et al. 2020 We also implement the original sparsity-aware random smoothing based certifiable robustness (SRS) (Boj. et al. 2020) as reference method of random smoothing based defense techniques. It performs first the same randomly flipping of categorical features as in RS. The least number of the features changed to trigger wrong classification, a.k.a. certifiable robustness, is then estimated via a dimmensinn-nneeeeddent evaluation based on the randomly flipped features. SRS (Boj] etal. 2020) is reported to be significantly more efficient and produce tighter robustness assessments than other random smoothing based methods (Lee al. 2019 Levine & Feizi 2020 Dvijotham et al. 20200).
Table illustrates the pessimistic robustness assessment scores of the tuned classifiers with the tolerance threshold 0= We skip the results of the optimistic robustness assessment and the results w as they present a similar variation tendency. Both adversarial training and nuclear-nore norm regularization help improve the classifier's ' robustness, leading to lower SR and higher |/| over all the three datasets in most of the cases. However, on Splice, the adversarial vulnerability reduction effect is much less visible than those observed on the other two datasets. We ascribe this phenomenon to the fact that the feature-wise sensitivity on Splice has a more skewed distribution than the other datasets. A few categorical features in Splice are significantly more sensitive than the others in the classification task, corresponding to important proteins dominating the molecules' properties (see feature sensitivity analysis in Section 4.1 and Appendix F.4) The existence of such highly sensitive features makes it difficult to enhance the targeted classifier's 's robustness without losing the classification utility. RS and SRS have higher SR than the other robustness enhanced models, showing that the random smoothing technique helps the least improve robustness or even make it more vulnerable to the attack, in the case where a fraction of categorical features are highly sensitive. As seen in Table highly sensitive features can be witnessed in many diversified applications. Firstly. flipping these sensitive features rather than providing robustness. Secondly, if random flipping misses
can lead to the sensitive features, the adversary can still target at these features to deliver a successful attack.
CONCLUSION
We unveil the key factors that jointly determine the adversarial vulnerability of a classifier with categorical inputs via information-theorett analysis. The characteristies of the categorical data and the functional property of the targeted classifier act as the external and internal cause of the adversarial threat. We further set a theoretical association between the smoothness of the targeted classifier and the solvability of both pessimistic and optimistic robustness assessment with categorical inputs. Despite of the NP-hard nature of the problem, we show that a provably accurate assessment is approachable for any classifier using simple yet efficient greedy search. Our study is useful for assessing the model robustness before deploying it to worldw safety-critice applications. Our future work will pursue to provide tighter quality bound for assessing adversarial robustness assessment on categorical data.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
The research reported in this publication was partially supported by funding from King Abdullah University of Science and Technology (KAUST).
REFERENCES
A. Akbarnejad and S. Günnemann. Adversarial attacks on node embedding via graph poisoning. In ICML, 2019.
N. Asghar. Yelp dataset challenge: Review rating prediction. arXiv preprint arXiv:1605.05362, 2016.
A. Boj., J. Klicpera, and S. Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In ICML, pp. 1003-1013, 2020.
A. Bojchevski and S. Günnemann. Certifiable robustness to graph perturbations. In NeurlPS, pp. 1519-8330, 2019.
A. Bojchevski and S. Günnemann. Adversarial attacks node embeddings via graph poisoning. In ICML, pp. 695-704, 2019.
N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz. Submodular maximization with cardinality constraints. In SODA, 2014.
J.E. Campbell, G.R. Carmichael, T Chai, M Mena- Carra-Coaaaoo,, Tang, DR Blake, N.J. Blake, S.A. Vay, G.J. Collatz, 1 Baker, al. Photosynthetic control of atmospheric carbonyl sulfide during the growing season. Science, 322(5904):
2008.
J. Cohen, E. Rosenfeld, and Z. Kolter. Certified adversarial robustness via randomized smoothing. In ICML, pp. 1310-1320, 2019.
F. Croce and M. Hein. Sparse and imperceivable adversarial attacks. In ICCV, pp. 4723-4731, 2019.
A. Akbarnejad D. Zügner and S. Günnemann. Adversarial attacks neural networks for graph data. In KDD, 2018.
K. D. Dvijotham. J. Hayes, B. Balle, Z. Kolter, C. Qin, A. Gyorgy, K. Xiao, and P. Gowal, S.and Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. ICLR, pp. 656-672, 2020.
D. Yin, K. Ramchandran, and P.Battlett. Rademacher complexity for adversarially robust generalization. In ICMI,, pp- pp- 7085-7094, 2019.
D. Zugner, A.Akbarnejad, and Gunnemann.. Adversarial attacks on neural networks for graph data. In IJCAI, 2019.
J. Ebrahimi, A. Rao, D. Lowd, and D. Dou. HotFlip: White-box adversarial examples for text classification. In ACL, 2018.
E.R. Elenberg, R Khanna, A. G. Dimakis, and S. Negahban. Restricted strong convexity implies weak submodularity. The Annals of Slatistics, 46(6B), 2018.
A. Fawzi, S.M. Moosavi-Dezffoll, and Frossard. Robustness of classifiers: From adversarial to random noise. In NIPS, pp. 1632-1640, 2016.
M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. NeurlPS, pp. 11423-11434 2019.
T. Florian, A. Kurakin, N. Papernot, D. Bonch, and P. McDaniel. Ensemble adversarial training: Attacks and defenses. ICLR, 2018.
Gao, J. Lanchantin, M. L. Soffa, and Y. Qi. Black-box generation of adversarial text sequences to evade deep learning classifiers. In SPW, pp. 50-56, 2018.
10

---

Published as a conference paper at ICLR 2022
J. Gilmer, L. Metz, F. Faghri, S. Schoenholz, M. Raghu, M. Wattenberg, and LJ. Goodfellow. Adversarial spheres. arXiv preprint
preprint arXiv:1801.02274, 2018.
Z. Gong. W. Wang, B. Li, D. Song, and W. Ku. Adversarial texts with gradient methods. ArXiv, fbss/1801.077555 2018.
M. Hein and M. Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. NIPS, pp. 2266-2276, 2017.
Z.Z. Htike and S. Win. Classification of cukaryotic splice-junction genetic sequences using averaged one-dependence estimators with subsumption resolution. Procedia Computer Science, 23:36-43, 2013.
M. Jordan and A. G. Dimakis. Exactly computing the local lipschitz constant of relu networks, 2021.
J. Khim and P.I. Loh. Adversarial risk bounds for binary classification via function transformation. arXiv preprint
20118..
V. Kuleshov, S. Thakoor, T. Lau, and S. Ermon. Adversarial examples for natural language classification problems. In ICLR, 2018.
G. Lee, Y. Yuan, S. Chang, and T. Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In NeurlPS, pp. 4910-4921, 2019.
A. Levine and S. Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In AAAI, pp. 4585 4593, 2020.
Ma, Gao, Q. Suo, Q. You, Zhou, and A. Zhang. Risk prediction on electronic health records with prior medical knowledge. In KDD, 2018.
C. Mack. Elements of Information Theory, 2nd Edition. Wiley, 2006.
Miyato, M. Dai, and IJJ. Goodfellow. Adversarial training methods for semi-supervised text classification. In ICLR, 2016.
N. Narodytska and S. Kasiviswanathan. Simple black- box adversarial attacks on deep neural networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 1310-1318, 2017.
M.O. Noordewier, G.G. Towell, and J.W. Shavlik. Training knowledge-based neural networks to recognize genes in dna sequences. In NIPS, pp. 530-536, 1991.
N. Papernot, D. McDaniel, A. Swami, and R. E. Harang. Crafting adversarial input sequences for recurrent neural networks. In MILCOM, 2016.
L. Qi, L. Wu, P. Chen, A. Dimakis, I. Dhillon, and M. Witbrock. Discrete attacks and submodular optimization with applications to text classification. In SysML, 2019.
S.N. Ravi, T.Dinh, V.S. Lokhande, and V. Singh. Explicitly imposing constraints in deep networks via conditional gradients gives improved generalization and faster convergence. In AAAI, 2019.
S. Samanta and S. Mehta. Towards crafting text adversarial samples. CoRR, abs/ 70011/077022222 12, 2017.
R. Santiago and Y. Yoshida. Weakly Submodular Function Maximization Using Local Submodularity Ratio. In ISAAC, volume 181, pp. 1-17, 1-17,2020 2020.
A. Shafahi, M. Najibi, M. A. Ghiasi, Z. Xu, J. Dickerson, C. Studer, L. S. Davis, G. Taylor, and T. Goldstein. Adversarial training for free! In NeurlPS, pp. 2358-3369, 2019.
Z.X. Shi, H. Zhang. K.W. Chang, M. Huang, and C.J. Hsich. Robustness verification for transformers. arXiv preprint arXiv:2002. 06622, 2020.
A. Sinha, H. Namkoong, and J. Duchi. Certifiable distributional robustness with principled adversarial training. In ICLR, pp. 4910-4921, 2018.
11

---

Published as a conference paper at ICLR 2022
Z. Tu, J. Zhang, and D. Tao. Theoretical analysis of adversarial learning: A minimax approach. In NeurIPS, pp. 12259-12269, 2019.
Y. Wang, S. Jha, and K. Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. In ICML, pp. 5133-5142, 2018.
Y. Wang, X. Ma, Bailey, Yi, B. Zhou, and Q. Gu. On the convergence and robustness of adversarial 2019.
training. In ICML, pp.
Y. Wang, Y. Han, H. Bao, Y. Shen, F. Ma, J. Li, and X. Zhang. Attackability characterization of adversarial evasion attack on discrete data. In KDD, 2020.
T.W. Weng, H. Zhang, H. Chen, Z. Song, C.J. Hsieh, D. Boning, S.Dhillioon, and L. Daniel. Towards fast computation of certified robustness for relu networks. In ICMI., pp. 4910-4921, 2019.
A. Xu and M. Raginsky. Information -horottion-theoreiic analysis of generalization capability of learning algorithms. In NIPS, pp. 2525 2534, 2017.
P. Yang, J. Chen, C. Hsieh, J. Wang, and M. I. Jordan. Greedy attack and gumbel attack: Generating adversarial examples for discrete data. ArXiv, abs/1805, 12316, 2018.
S.C. Zhu, X Zhang, and D Evans. Learning adversarially robust representations via worst-case mutual information maximization. In ICMLL, pp. 11609-11618, 2020.
D. Zugner and S. Gunnemann. Certifiable robustness and robust training for graph convolutional networks. In KDD, pp. 206,
12

---

Published as a conference paper at ICLR 2022
A PROOF FOR THEOREM
Lemma Supposing and B are two independent random variables and is given by PUAB=PABPPIARE
(U:))
(11)
Proof: Given the definition of mutual information (() ((X:))==(XX)--(((IX)) we need to prove:
((A)))++))
(12)
With the chain rule of conditional entropy:
H(A, ((AI))HHBAAA
(13)
It indicates that H(A,BUU) & H(AlU), as H (B]U) 2 O. Similarly, we can derive H(A.B(U)
(((UU)
as well. Combing both incquality relations, Eq [2 which turn proves Eq 11
Considering the markov chain in Figure 1 we assume class label Y and the training set are statistically independent. f depends on S as ( where R is the training paradigm (could be randomized). The generation of the adversarial example X' depends on both the clean feature vector X and the targeted classifier f. This consistent with the fact that generating adversarial samples needs to understand the local geometry property of the decision boundary of the targeted classifier. Once get the perturbed feature vector X', the classification output f(x).X)).
Y--00
Figure 1: Markov chain of adversarial attack
We derive the lower bound of the miss-classification probability with the perturbed categorical inputxx' following Fano inequality:
Radv =P( + (dff(bbbb) 2 I(Y';Y,S) +onstt
(14)
logk
where K denotes the number of the classes in the learning task. Based Data Processing Inequality illustrated in Chapter 2 (Mack 2006), we can further obtain:
Radv 1- ((X:YY +Const
logk (I(Y'Y)))&
(15)
21(X: 2nx
logK
where -x= (xx==((XX,))1(x(": denotes the mutual information difference between the unperturbed
X and the adversarially perturbed instance X'. By applying Lemma] D on a ((X',Y,S) in Eq 15 we have
Radv 21 21(X:Y,S) 22(X:)_5))221xx -IX:))))
logk
(16)
2 21(X:Y,5)- -(07)s))-2xx---- -1f- (Outarrressiggheeeppgggg////0//0
logK
B EXPLANATION TO OBSERVATION.1
First, we follow the III) assumption in the definition of the expected adversarial risk in Eq.1 1. We assume adopts the form of zero-one loss function. If f(i) y, ((f()) = =1. Otherwise, (= 0.
With this setting of the loss function, the expected adversarial risk of the classifier f can be formulated in Eq 17 This gives Eq.1 (the adversarial risk of f) in the main paper.
R advv
sup (s)
([(()
(17)
where P denotes the probability measurement. In this sense, the expected adversarial risk of Radv can be explained intuitively the maximum ciss-classification probability over adversarial sample with the underlying data distribution Hx.y and the attack budget limited by &.
Second, Theorem. provides the information-theoreee lower bound of Radv with respect to the data distribution Px,y- Indeed, for any given training data set sampled from the joint distribution Mx,y
13

---

Published as a conference paper at ICLR 2022
S can be considered as random variable. Similarly, given deterministic training paradigm A, the classifier f (S) (trained with using the training algorithm A) can be also treated as a random variable in the hypothesis space. For a testing imput (x.y) sampled from the same distribution Hx,y as S, deriving Theorem. I follows Fano's inequality information theory (Chapter 2 in (Mack) (006)):
For any x ~ My and (x.y) ~ Mx.y, following Fano's 's inequality, we can produce the lower bound of miss-classification probability the adversarial sample & generated from (based on the information of and f):
21x-1(((x)) (10 logk'
2 1-
(18)
where f(x)= y. The lower bound of the miss-classiiicationn probability is composed by three mutual information measurements among the random variables (x.y), S and f.
By definition, the following incquality holds:
Radv
sup
P(f(x)+f()) 2
X-Ms. 2)
(19)
2 21(xy 21x I(f:5)/2(const
logk
where (x.y) ~ Mx,y), Mxxy and fEH.
From this perspective, Theorem.1 establishes lower bound of the expected adversarial risk of f: Given a deterministic training paradigm A. for any training data set S and any testing input instance (x.y) sampled from the underlying data distribution yx,y, the misscllasifiiation probability of over the adversarial sample generated from x (based on and f) can be bounded by the three mutual information measurements [xx:y,S), 1Ix and I I(f:S), as Eq.2 2 and 3 of Theoree.. in the main paper.
Comparison with the adversarial risk bound proposed by (Tu et al., 2019). A relevant work of adversarial risk analysis can be found in (Tu al. 2019), where the expected adversarial risk of classifier of is measured by the maximum classification loss over the distribution of adversarial samples (Definition.) in (Tu et al. 2019)):
Radv
E sup (((()),)) x,y-Ax. (eN(()
(20)
where N(x) denotes the neighbor set of derived by modifying features in x. The coverage of the neighboring set (x) can be measured by Ip distance for continuous data or lo norm for discrete data. After that, Tu et al's work achieves two results. First, the expected adversarial risk bound can be bounded from above by the local worst-case risk of ff (noted as R Re.Ha..):
E Radv <R 8-pps-15" Bw (x)..)
{(f(t),)
(21)
where μı a distribution sampled from the p- Wassernstein ball (p 2 1) centered at μ and with a radius of E. (xx) Suz. Second, the expected adversarial risk Radv can be bounded by the upper bound of the local worst-case risk of consisting of the rademarcher complexity of f and the empirical risk of This upper bound holds with probability
f. according Theorem. and Remark.3 in (Tu al. 2019).
at least --ó:
log(1/6)
Radv S RRdd +2%, (W)))
2n
(22)
Radv max ((f())))))
Ri-JaR
where Radv denotes the adversarial empirical risk calculated using n IID samples from the adversarial data distribution μıs. Practically, Radv can be estimated by calculating the maximum classification loss reached by perturbing within the attack budget. denotes the maximum output value of f. R,, (v)() denotes the expected rademarche complexity of augmented function defined on f. The value of R,, (1 (f)) is independent from the empirical adversarial risk Radv The formulation of RA( (f) can be found Page 10 of eTuet al. 2019).
14

---

Published as a conference paper at ICLR 2022
Our work differs from the results in (Tu al. 2019) from the following perspective. The core contribution of (Tu et al. 2019) is to associate the Rademacher complexity of the classifier f with f's expected adversarial risk. Beyond that, for classifier adopted in a learning scenario, we believe both the characteristics of input data and the classifier's s complexity measurement determine its adversarial risk. As shown by the mutual information-based lower bound (Fq.2 and of Theorem. 1), the mutual information I( (ff:)) measures the dependence of a trained f over the training data S ssmpledd from Mx.y. I(f:S) can be considered as the lower bound of the VC-dimension of f (Xu & Raginsky Zhu et al. 2020), which encodes the classifier's 's complexity. The other two mutual information measurements / (x:y.S) and 17x relates the characteristies of the input data (x.y). Intuitively, (x:y,.)) measures the informativeness of x for classification. A lower y,) denotes weaker consistency between the input data instance (x,y) and the training data set S. fJx reflects the sensitivity of the modified categorical features during the evasion attack. A classifier with input data containing more sensitive features is more likely to be compromised by modifying intentionally the values of the sensitive feature dimensions.
2017
Relations to the proposed robustness measurement. Since is not feasible to directly compute the expected risk Radv we empirically evaluate the adversarial risk/robustness and presented the results in Table 2 and Table 3 in Section 4.2 and 4.3. The empirical evaluation of the adversarial risk evaluation of f over the data distribution μx, is computed sample average,
Radv === & (di
max
(+)()))))
(23)
To facilitate computing, we adopt smooth loss as surrogate function approximating the zero-one loss. In Eq. (23). sr, sos (((($t))))) to estimate the maximum classification loss of f over
max
the adversarial sample Ê,. which is generated by modifyyng at most categorical features of By its nature of set function maximization, Rody (f) is calculated in two difference settings: the pessimistic and optimistic robustness assessment defined in Eq.4 and Eq.5 in the main paper. When setting the threshold r = 0 in Eq.4 in the main paper, the pessimistic estimate Pess (defined by fyx fyx is proportional to the classification loss, and gives the miss- classification confidence of the target classifier x with the attack budget limited by this chiissclassiiicationn confidence" is the empirical estimator of the adversarial risk f has a given input x, or called robustness.
C PROOF FOR THEOREMS ON THE WEAK SUBMODULARITY
We introduce the notion of y-weak submodularity used in Theorem
Definition 3 Monotone and y-weakly submodular function (Santiago & Yoshida 2020). A set function gSS) monotone, for every CS, we have (S)) g()). Given set cardinality threshold k 2 1 and a scalar value y [0.1]. We define Yu of g() w.r.f. a a S as:,
{
Yk SCH & ((UA)))((S)
(24)
If g(S) is monotone and Yk y for any k. g(S) is y-submodular function. Otherwise, g(S) is y-submodular, if (S) is non-monotone but g( follows anr k: any
Σ - aeA
(25)
is easy to find, if (S) is monotone and y 1, gS)) is submodular.
Proof of deriving the robustness assessment score under the pessimistic scenario in Eq we first
formulate pessimistic scenario as a set function optimization.
S =mxx
(Cx)))))((((())
t,1.,,3....,
(S) = max fo (b)) ICS
(26)
Gk(S)= max ix (bi) IcS
15

---

Published as a conference paper at ICLR 2022
where by denotes the modification of etttrattorrooootoooooooooacatrae features indicated by the index set l. fx (bi)= (bi). For each E 1,2,3 E = - -VV (S) and GK (S) are monotonically non-decreasing set functions.
Supposing E 2 for each k E { (1.2.3..... by 1' are modified in addition to I, with [1'] Ç. For any b₁, biur and buyj denote the additional modification over the features indicated by 1' and by j respectively to increase the output of fx (increasing the miss-classification decision confidence) and fk (decreasing the confidence of correct classification). In the following analysis, we relax the discrete indicator b to the continuous domain, as each b, E [0.1]. fi (bj) denotes the gradient of the classifier function fx with respect the variable b at b = b1. Modifying from bi to biur or biuy follows the direction of gradient ascent, which gives (V fa bbur 0 and (V (bi),,bu))) 0, (V fK (bi).blur-bj and (V fK (bi).bruj-b,) 0.
1}. we assume further that the features indicated
Mr
(((b))))
bi)+
|lb -b:11
2
M
<IVV 112+
|51
(27)
Σ
-a Σ JeC
1k.00
| - b1ll2
2
mg.0
(i 112
We can derive the lower bound of the submodularity ratio yx.6 fk:
(bbu)((
(b1)gb1) me.
2
151
Yk fa(biur) f2 ( Mr.Pc 151
(28)
Supposing e <0 for each & & (1,2,3,..... K- --1}, we can derive:
mx.2c
b - -bil2
(b)e(b))
2
2m2.00
MR.au |
Σ (b fxbbi) Σ ((V JEL
(29)
2
Mx
2 VV 112
|g (eeddesss
2
Given the smoothness assumption on the targeted classifier (See Definition 2 there exits value of My.0, / > fi el2), which allows that V (bi) (b)))ll2 ll2 M |5] 2 holds. Therefore, we can derive the lower bound of the submodularity ratio of FÜ and -Gx. Ye,r (k=1,2.3.....):
(i fa
2mc.0
YR.Og
fa(biur) (b)
f&bb
-V
(30)
The submodularity ratio yı 22g in Eq 26 is yz
min
(x,,2
k=
Proof of deriving the robustness assessment score under the optimistic scenario Eq Following the setting of Eq 26] we can formulate the robustness assessment problem at the optimistic scenario (with an oblivious adversary):
= (Gx (S)+
k.1.,,3.....K (S)))
min
(A) ([))) (bı) IcS
(31)
Gx (S) (bi) Ics
Both (S) and (S) are non- non-increasing with hy (b))= Eq thus defines non-monotone set function maximization problem (See Definition We conduct the analysis as in Eq 27 and 29
Modifying by to byu and bruj follows the direction of gradient descent, which gives (V fx b,).
by) 0 and (V fr (bi), -b)) s0, (Vhe (hi), bı) and (V h2 (bi),brur- 50.
16

---

Published as a conference paper at ICLR 2022
Supposing e O, we can derive:
mK. fo
Iibiuj brll2
2
MK.0
fk((bu)) (bx) (V)
|lbalj (bluu--illž b11l2
(32)
mKK Ot
fx(biur) (y
|ib - -blll
2
Mx.00 06
fx((b fx (b)bbbb))
||biur -
2
and
m1.0
he (bi (bbb)))))))
[lbuuj - b1ll2
(bru)) h1. (b)) (Wh, (V)) MR.0r
2
(33)
Sx
- ( (Vh, b1)
||bjur- Abjur-billã b1ll2
hy (b (b)) (b) MR,0c
- bull2
From Eq 32 we conduct the similar analysis as in Eq. and 23, which gives the submodularity ratio at the optimistic case:
E (buu)))) Mk S 1-1
[VV
2
JeP
(34)
MR De 1s1
(x(brur)-sx(bi)
(bi)cll
2
Σ -he(brr))-h((h)) (bb)) Σ (Vhe bi)
Mr.0
1iluj-bill
MI.0.151
(Vhhabb))lll
2
2
jer
jer
mR.0%
-m1.0 151
hn(b)ur)=hx(b)) (Vhg((b).bbrrrrr bi)
blbiur
-1Vch(bb)<cll
2
2
(35)
Let YR (0,1) and
Ma.a, KC
14 (b1)c
1 76
-m 151
11hh(bb)) l12). The submodularity ratio
2
mp.ak Kgl
+11 (br) lla
of h4, yk S Mc., 141
(bi)
In the pessimistic scenario, assessing adversarial robustness can be formulated as a problem of monotone weakly submodular function maximization. Assuming that my (/) the solution / obtained by the FSGS method and my (!") is the optimal solution to Eq 4
Proofs to Theorem 3 (Eq
Based Theorem.3 in (Elenberg et al. 2018). can obtain:
1-Im Im (1) (1 (Im))
(36)
Therefore, we can derive the first inequality (the pessimistic scenario)
Eq
|m (1]++
<1-e -xE pess
mm (1*)
(37)
Assessing adversarial robustness in the optimistic scenario (Eq 55 is in nature a problem non- monotone weakly submodular function maximization. Assuming that my that
(l) is the greedy search based solution obtained by the RandGS (Randomized Greedy Search) and m (!*) is the optimal solution to Eq Applying Theorem 1.9 (Santiago & Yoshida 2020) directly, can obtain:
optim
|my (0)z Yt
Im (!")
(38)
opptmm"
The proof to the approximation gap of OMPGS in Eq followw the proof to Theorem 2.4 and Theorem 3 (Santiago& & Yoshida 2020).
17

---

Published as a conference paper at ICLR 2022
D ALGORITHM PSEUDO CODES FOR ESGS AND RANDGS BASED ROBUSTNESS ASSESSMENT
Algorithm 1 FSGS for the pessimistic robustness assessment
Input:
The candidate set H=(a; i==1...n of all modifiable features
Output: The maximum support set pushing yy (4) to violate the tolerance constraint in Eq
1: f
2: for:=0,1.2.....dd do
3: ze-zerovaluedd vectore
4: for each a; H/I,, do
5: =rgmmx my (sUaz) (Inner level Optimization)
sch-1
6: end for ā=argmax T(a;) (Outer level Optimization)
7:
di 1, 1ي
8:
9:
my (4))m U4))
10: if y (4) 2 then break
end for
Algorithm 2 RandGS for the optimistic robustness assessment
Input: The candidate set ==(a))==.... of all modifiable features
Output: The maximum support set I; pushing y (4,) to violate the tolerance constraint in Eq
1: 0
2: for for/=0,1,.....pdd do
zeleeoovalued vectore 4: for each ai E HH111111 do
3:
5:
=armmx m (sUa;) (Inner level Optimization)
scL-1
6: end for
7:
M c CH/4411 be subset size
8:
minimizing T(a) (Outer level Optimization) Let ā be uniformly random element from M
9:
10:
Let 3(ā) be the subset corresponding to 1il1--1Çā)
11:
12:
my (4:)emint (āUS(a)) (1i-1))
13:
if y (1,) I then break
14: end for
E ORTHOGONAL MATCHING PURSUIT GREEDY SEARCH
The poeudo-codes of OMPGS presented in Algorithm which explains how is adopted solve an| [5 In each iteration, for each subset of the previous support set 44-1, we compute the gradient of fy with respect to by (binary indicator matrix b with the entries in s changed). The top-k' attributes with the largest magnitudes in the gradient vector are selected to form candidate set š. We can then find out the optimal attribute j to extend for each subset and record the optimal attack objective value 8(4-1 j). In the outer iteration, we choose finally the attribute j* producing the largest marginal gain to add into 4-1-
The worst cost of objective function evaluation in each iteration of OMPGS is bounded by |(EE)))))) I)) We adjust k' to achieve trade-off between enlarging the search range of greedy search and the cost of function evaluation. Usually is much less than HH-114 especially when H is significantly large (e.g. H > 10k). Thus OMPGS runs significantly faster than FSGS.
We further illustrate the rationality using the orthogonal matching pursuit step in OMPGS to solve the weakly submodular maximization based assessment problem. In Eq. 39 unveil that the gradient
18

---

Published as a conference paper at ICLR 2022
Algorithm 3 Orthogonal Matching Pursuit based Greedy Search (OMPGS)
Input: The attack budget K, the set function based attack objective g(() and the H = ((i)).i
T...n.j=1....h of all the modifiable discrete attributes selected support set 42, with <4
Output: 8(4x) and the optimal subset of /g achieving the attack goal So -
1: for k= 1 do
2: T=0
3: for forsclk-1 do
4:
(y)))(b))
5:
$= (1112mm)))))
argmax <
je(H/l-ii
6:
jES
7:
7=TU((8(((-11ū))
8:
end for
9: j "=argmaxg(4=-111)
ja
10: 4. 4-400)10
end for
magnitude of fy with respect to the binary indicator variables b/ can be used as an estimator of the marginal gain of my in each iteration of the greedy search of OMPGS.
We assume that h and D' denote two sets categorical attribute changes. indicates the category value assignment of an unperturbed data instance [diff(b. bb) s z, [.] C. (diff((.bb)) | 5.5 The targeted classifier is denoted as fyx (x) (k=1,..,,K) in which K is the correct class label.
1
1/x (0.6") (8.b)) | S max
1y (x.b)v1l
2mx.6
(39)
(xx6) min!
IV 1
1
2MK.
where dddif((
F EXPERIMENTAL EVALUATION
We first introduce the evaluation datesets in section the complexity analysis and running time in section Besides the multi-class datasets Yelp, IPS and Splice, we also include another two binary classification datasets collected from Cyber Security and HealthCare in the experiments. We add the feature sensitivity with the multi-class datasets Yelp, IPS and Splice in F.4as as the supplementary information to the main text. We add the the robustness assessment with the binary-class datasets PEDec and EHR in F55) It includes the summarised table on the robustness assessment and the informatiinn-heorrtiic characterization of adversarial vulnerability verified in the experiment.
F. the experimental setup in section
F.2 and
F.1 DATASET INFORMATION
Yelp-5 (Yelp) ( Asghar 2016). We use the Yelp-5 provided in the torchtext package contains 650,000 training and 50,000 testing textual samples. the classifier training process. We learn a 300- dimensional embedding for each word. Thus, each sentence is encoded as R=0000 where n is the number of words. we treat every word as categorical feature and put this data into the L.STM model with five level rating classes of the reviews the labels. The task is to predict the 5-class rating of each review. After learning the classifier, we start to attack the categorical input with modifying the words with those semantic neighbor words, which can contain the sentence is semantically correct. Here not all the words have neighbors. Here we choose the 200 data from the testing data for attack.
Intrusion Prevention System Dataset (Wag al. 2020 An adversary of network intrusion performs a series of actions to compromise the targeted devices. We collect one day of IPS records via security service vendor from 242,467 endpoint devices. After removing repeated instances, the
19

---

Published as a conference paper at ICLR 2022
collected data set contains 4,101 time series of attack events. Each sequence instance is composed by 20 attack steps. On each attack step, the adversary can choose one of 1.103 different malicious actions registered as highly threatening ones. Thus one data instance of IPS data is given according to the definition given in Section.3. Each of the 1 103 attack actions is projected to a 70- dimensional embedding vector. In our study, each sequence instance is used as input to the classification system, which predicts the most likely attack operation conducted at the immediately successive step of the sequence. We randomly select 80% of each dataset for training and others for testing. Based on the prediction output, security analysts can proactively take prevention actions. We focus predicting the occurrence of the two most threatening actions related to recently uncovered vulnerability. We thus study a 3-class classification task: the 2 highly malicious actions and all the others as the third class. All the privacy-related information, such as names of the devices, TP addresses and hosting machines' domain names have been removed and anonymized.
E R 2001 103+70
Splice-junction Gene Sequences (Splice) (No- ordewier et al. 1991). Splice junctions are the points on a DNA sequence at which redundant DNA segments are removed during the process of protein creation. As shown in Figure Htike & Win 2013), precursor mRNA contains exons and introns. During splicing, introns get spliced out while exons get reunited. It then important to analyze the role of splice junction sequences in mRNA. The Splice dataset contains 3,190 sam- ples from Genbank release 64. 1. Each of the instance is a gene fragment of 60 categorical features, which consists of a window that covers 30 nucleotides respectively before and after each donor and acceptor site. Each categorical feature can take one among A',, 'G', 'C', 'T' or 'N' (stands for ambiguity). In our work, Each category is cast to a 30-dimension embedding. Then one data instance of the dataset is given x R60+5-30 The dataset defines a 3-class classification task. Each gene instance can be an intro-exon boundary (labelled as IE), an exon-intro boundary (labelled as El), or any other cases (labelled as N). There are 768 IE instances and 767 E/ instances in total. All the rest are N instances. In the published dataset, the data records are anonymized. We randomly select 80% of each dataset for training and others for testing.
Alol
Transiigho
Talted prorts
Figure 2: RNA synthesis and translation into pro- tein.
Windows PE Malware Detection (PEDec). We build a well-balanced dataset composed by full dynamic analysis reports of 20000 benign and malicious PE executables. This dataset is used for binary classification scenario of PE malware detection. We collect 1 10,972 malware samples of 152 families randomly selected from those submitted VirusTotal between 2018 and 2020. Each of the files https://www.w http://wwww.vvrreaa..coo wwereeaf.com/prrooee 21 antivirus engines. We further use AVClass to ensure that no malware families are over-represented in the collected data. For the benign samples, we choose the fresh installation packages of all the community-maine maintained packages of Chocolatey, where the package submissions go through strict review process to exclude malicious and pirated software. Therefore we obtain 9028 benign samples of third-party and Windows system files. Each executable the dataset is encoded into a binary feature vectors with 5000 signatures selected by human experts. Each signature covers presence or absence of specific windows API calls, URL access, registry table edits, file I/O operations and the status of IP ports. The ensemble of the signatures' binary states form a description of the file's behavior in execution within a sandbox. In our study, we use the 5000 binary codes directly as the features of a file instance. Simple as it is, the combination space of these signatures can still induce prohibitively expensive search cost, which prevent brute-force attacks. We randomly select 80% of each dataset for training and others for testing.
lef055ce928000 lecdee8is ecdeees classified as malicious by more than
Electronic Health Records (EHR) (a et al. 2018). The real-world EHR dataset consists of time- ordered medical visit records of 7314 patients. Each patient has from 200 medical visits. Each visit record is composed by subset of 4130 discrete ICD9 diagnosis codes? Each diagnosis code represents occurrence of a disease, symptom, or an abnormal finding. Using the historical EHR data of patients, we can predict the risk of patients suffering the target diseases. In this experiment, our target is a binary classification task: we forecast whether a patient will suffer heart failure disease in the future. In our experiments, a data instance of EHR data set is organized as a tensor e R 1100-1130+70 with
httpp://wwe cdddata......................... comm
20

---

Published as a conference paper at ICLR 2022
each of the 4130 diagnosis codes projected to 70-dimensional embedding vector. For the patients with less than 200 visits, we pad the empty observations by setting the corresponding by =0.
We split randomly each dataset into two non-overlapped subsets: 80% of them are used for training and the left 20% form testing set. In the testing set, we choose the correctly classified testing samples with the strongest probabilistic confidence provided by the classifier to perform evasion attack. There are thus 125, 500, 324, 3000 and 4 414 instances of Yelp, IPS, .PDec and EHR used in the evasion attack scenario. On PEDec and EHR data, since the discrete feature takes binary values, we focus on adversarial modification by simply flipping the codes. For Yelp, IPS and Splice, the adversarial attack is conducted by replacing the original category values of targeted discrete attribute with a new one.
F.2 EXPERIMENTAL SETUP
We instantiate the study of robustness characterization and assessment to the popularly deployed Convolution Neural Networks (CNN) and Long Short-Term Term Memory (LSTM) models. For PEDec dataset, we adopt a simple CNN model composed of one convolution layer followed by two linear layers. The rest datasets contain sequential instances, in the experiments. Without loss of generality, we use ReLu activation function in both the CNN and LSTM classifier with the dropout module. TTheoremzappliee in both cases. Both models define Lipschitz-conting continuous decision functions, which meets the smoothness constraint given in Definition 2 For the instances used for robustness assessment, the CNN and LSTM classifier achieve accurate classification over all the datasets. They achieve accuracy scores of 0.90, 0.95, 0.94, 0.93 and 0.62 respectively for the datasets IPS, Splice, PEDec, EHRand Yelp.
thus apply standard LSTM as the classifier
we demonstrate robustness assessment of the two classifiers over all the datasets with varied tolerance levels against adversarial perturbation. We set the robustness threshold I' to -0.4 and respectively. The former defines a low tolerance to the decision perturbation caused by adversarial attack. A minor fluctuation of the classifier's ' output triggers an alert of potential evasion attack. In contrast, the latter setting only raises alarm when the classifier produces an ambiguous decision close to the boundary or report a miss-classe classsslssiiictiionn incident. Furthermore, we show the derived robustness assessment scores with respect an oblivious adversary (hhe optimistic assessment) and an knowledgeable adversary (KA,th the pessimistic assessment). The purpose is to show that 1) our proposed robustness assessment method can adapt varied tolerance settings to adversarial threats in safety-critic applications; 2) we aim at confirming the impact of different query capabilities of the adversary over the robustness assessment scores, as revealed by Theorem 2 For the instances used for robustness assessment, we report the median and mean of the derived robustness assessment scores. Both FSGS/RandGS and OMPGS are used calculate the robustness assessment scores. They verify the effectiveness of greedy search for robustness assessment with categorical input. We implement the empirical study using the Python library PyTorrc and conduct all the experiments on Linux server with 2 GPUs (GeForce 1080Ti) and 16-core CPU (Intel Xeon). For RandGS and OMPGS, we empirically set the number of candidate attributes in each iteration of greedy search to be 10 globally for all the datasets.
In Section 4.1
F.3 TIME COMPLEXITY AND RUNNING TIME COMPARISON
We provide the time complexity analysis in Table 4 categorical features and each feature can choose any of the M categorical values. Furthermore, we assume FSGS, OMPGS and GradArtack all run T iterations. Table 4 shows the query complexity of these methods of iterations.
We assume data instance x containing N
In the table, Kompgs for OMPGS denotes the number of top-ranked candidate features in each iteration. OMPGS then selects one feature from the top K Kampgs candidate features. The selected feature achieves the best attack performance by combing this feature and any subset of the already modified features. Kgra for GradAttack denotes the number of the candidate features selected to modify in each iteration. As seen in Table 4 FSGS has the largest query complexity in each iteration. Enjoying the heuristics provided by the orthogonal matching pursuit step, OMPGS locates simultaneously the top-ranked candidate features and the categorical values of these candidate features that are likely to bring the most increase of my. Therefore, OMPGS can reduce the query complexity significantly compared to FSGS. GradAMack does not evaluate the gain of my on the combination of the candidate features and
21

---

Published as a conference paper at ICLR 2022
Table 4: Query complexity of FSGS, OMPGS and GradAttack
Assessment Methods
Query complexity
FSGS
[[N
OMPGS
21z0 (Koppes 2
GradAttack
k= Kynd *M*)
Table 5: Averaged running time of FSGS, OMPGS and GradAttack successfully attacked data instances (measured in seconds)
Greedy Search
Yelp
IPS
Splice
EHR
FSGS
1.62
263.8
13.7
446
OMPGS
0.82
0.43
0.08
27.44
GradAttack
0.18
10.60
1.07
4.05
Table 6: Average number of iterations of FSGS, OMPGS and GradAttack on successfully attacked data instances
Greedy Search
Yelp
IPS
Splice
EHR
FSGS
1.9
2.4
3.0
1.7
OMPGS
2.5
2.2
5.2
2.0
GradAttack
38.6
3.3
4.8
8.0
the subsets of the already modified features. The query complexity of GradAttack in each iteration only depends on Kgrad and M.
We also show the running- time evaluation of these methods in Table 5 and Table In both tables, we focus on the pessimistic robustness problem and set the threshold -0=00 in Eq 4 in the main paper. Table (rreord the averaged running time for computing robustness assessment results over the input data instances where the evasion attack is delivered successfully, i.e. my increases above O. Table 6 shows the average number of iterations required over the input instances to make m increase over 0.
As seen in the two tables, FSGS stops the loops of greedy search generally earlier than OMPGS and GradAracck, while costing the largest running time. The observation is consistent with the design of FSGS. On one hand, FSGS traverses all the candidate features and chooses the one that most improves the marginal gain. Compared OMPGS and GradAttack, FSGS has a better chance to achieve higher marginal gain of y in each iteration. Therefore, FSGS requires fewer loops in the greedy search and modifies less number of features to solve the robustness assessment problem. However, on the other hand, FSGS makes larger query costs in each iteration of the greedy search. The running time of FSGS thus higher than the other two methods.
On the contrary, GradArtack runs fast but needs significantly more iterations in the search loops. In each iteration, GradArtack only needs to evaluate the combinations of the Kgrad features selected from the candidate set and choose the combination contributing the best increase of m It requires much fewer queries than FSGS, as it only searches a subset of the combinations that FSGS looks into. However, GradAttack likely results in less optimal solutions each iteration. Therefore, GradAtack needs more loops to extend its search range.
OMPGS achieves the best trade-off in between. The orthogonal matching pursuit step adopted in OMPGS helps narrow down drastically the search range while guaranteeing the optimality of the features in the reduced search range. Compared to FSGS, OMPGS stops early the search with similar number of loops, yet costing much fewer queries and less running time than FSGS. Compared to GradAmtack. OMPGS has better chance select the really useful feature modifications, thus costing fewer loops.
F.4 FEATURE SENSITIVITY
To further understand the association between the feature sensitivity and the derived robustness assesment scores, we conduct mne-factor-at--tiiee sensitivity analysis (Campbell et al.) 2008) to measure the sensitivity of features. Given data instance, change each feature while keeping all the others fixed. The averaged change the classifier's 's output over all the testing instances used as the feature-wise sensitivity measurement, A larger value indicates that the classifier's output is more
22

---

Published as a conference paper at ICLR 2022
Table 7: The feature sensitivity of different datasets
Top3
Top5
DataSet
max
average
min
max
average
min
IPS
1.00
0.53
0.00
1.00
0.53
0.00
Splice
1.00
0.38
0.00
1.00
0.33
0.00
Table 8: Top sensitive features vs frequendy perturbed features Yelp
DataSet
IPS
Splice
Sensitive
not, but, could,They
19,0.17.18116
29.28.30.31.27
Perturbed
day,never, They.good.ng.
19,0,1,,117
29,28,30.11,22
sensitive to the change over the corresponding feature. In Table 7 we show the maximum, average and minimum decrease of the probabilistic output for IPS and Splice, induced by changing the top-3 and 5-ranked features.
First of all, we can find that the feature sensitivity of IPS lies in a narrow interval lower than all the other datasets. This resonates with the larger robust assessment scores in Table I and 2 Second, Splice also has narrow interval with high sensitivity values, indicating a potential high vulnerability. Third, within dataset IPS and Splice, the sensitivity levels vary strongly, between the max and min value. That implies, changing the top sensitive features only is enough to deliver a successful attack. In real-world applications, the existence of such highly sensitive yet sparse sensitive attributes is widely witnessed. For example in IPS, the top-5 ranked features are relevant to the key signatures of network traffic flows, and they are thus usually used by human security analysts filer out suspicious incidents. The rest of the features in IPS are not explicitly relevant with the network I/O behaviours, which are less informative in the classification task. In Splice, the top-5 sensitive features are found the gene segments around the spliced junctions. They are particularly sensitive to the gene types. The rest of the features show little physical significance in the gene splicing process.
We also find that the top-sensitive features also appear as the most frequently selected features by FSGS, GradA.akdA and OMPGS. We further count the frequency of appearance for each feature selected in the pessimistic robustness assessment and compare them with the top-sensitive features, as given by T For IPS, the top-3 sensitive features also appear in the list of the most frequently selected features. The top-4 sensitive features in Splice are also the most frequently selected 4 features. The interesting overlapping between the attributes which are useful for attack and the top-ranked sensitive attributes confirms our intuition about the association between feature sensitivity and adversarial vulnerabilitt of the classifier. On Splice, 4 of the most frequently attacked features (29,28,30 and 31 in T correspond to the junction of exons, which are also highly informative for gene categorization (tikee& & Win 2013). On /PS, 3 of the 5 most frequently attacked categorical features (19, 0 and 17) are the also informative indicators of unusual DNS requests and DDos activities. They are ranked the
most sensitive features according to Table g
Suppressing feature sensitivity helps improve adversarial robustness. However, these sensitive attributee are usually informative for classification in an adversary- scenario. Excluding the sensitive features causes accuracy loss. indicates the balance between classification utility and advirsary-reslliecce feature engineering in ML practices
F.5 ROBUSTNESS ASSESSMENT IN BINARY CLASSIFICATION
F.5.1 ROBUSTNESS ASSESSMENT WITH GREEDY SEARCH
Table/Isshow the results of robustness assessment for models built on binary-class datasets PEDec and EHR. We have the same findings in that with the multi-class datasets Yelp, IPS and Splice. In details, firstly for both the pessimistic and optimistic robustness assessment problems, a lower tolerance threshold results in lower scores over all the binary-class datasets. Secondly the pessimistic robustness assessment scores are always lower or equal to the optimistic assessment scores.
F.5.2 ROBUSTNESS VS FEATURE INEUUREENNORRR INFORMATIVENESS
We take the Xi,, samples from the 62, 43 original samples for the dataset PEDec, EHR respectively on the half-way of pushing the my of the original samples (OS) surpass I', In Table TO we verified
23

---

Published as a conference paper at ICLR 2022
Table 9: Pessimistic and Optimistic Robustness Assessment Score |1], reported with median and mean.
A lower/higher value at given percentile level indicates stronger//waker robustness of the classifier.
SR is the success rate of attack. OVF indicates SR=0.
PEDec
EHR
SreacySeearch
P/O
r
SR
Med(Avg)
SR
Med (Avg)
-0.4
0.92
(3.2)
0.98
(
P
0.87
(3.7)
0.94
((1.2)
FSGS
-0.4
0.46
(4.1)
0
OVF
0
0.42
(4.7)
OVF
-0.4
0,56
77.22
0.63
22.00
GradAttack
P
0.51
8 (6.1)
0.62
2
-0.4
0.87
6 (6.1)
0.95
(2.0)
P
0.82
6 (6.3)
0.94
22244)
OMPGS
-0.4
0.62
5 (6.1)
0.38
2
0.54
6 (6.8)
0.42
(2.5)
Table 10: Robustness Assessment vs Feature Informativeness, reporrt at 0 (N <(x:y))) results in higher adversarial risk (higher SR, smaller (/)) Ki,. than original
PEDec
EHR
GreedySeearch
P/O
sample
SR
Med(Avg)
SR
Med(Avg)
original.x
0.87
(3.7)
0.94
(1.2)
P
FSGS
Nini
0.96
(3.1))
I(I)
original x
0.42
(4.7)
0
O
Ximi original.
0.69
(3.2)
0.92
(2.2)
0.82
(6.3)
0.94
2 (2.4)
Xini 0.85
(6.1)
(1.9)
OMPGS
original x
0.54
(6.8)
0.62
(2.8)
Xlmi
0.71
6 (6.4)
0.94
(2.1)
Table 11: Pessimistic Robustness Assessment (I =0) after Model Robustness Enhancement by reducing I(fy;)). |SR is the SR decreased amount comparing to the corresponding SR value with I 0 in
Table
PEDec
EHR
Model
Algo.
SR
sSk
Med (Avg)
SR
SK
Med (Avg)
FSGS
0.65
0.22
(4.2)
0.94
0
2(2.17)
AdvC
OMPGS
0.58
0.24
(6.4)
0.92
0.02
2 (2.82)
FSGS
0.81
0.06
(2.9)
0.94
OVF
NuR
OMPGS
0.25
0.57
(6.1)
0
0.94
OVF
FSGS
0.93
-0.05
(3.2)
0.96
-0.02
(1.97)
RS
OMPGS
0.86
-0.04
4 (4.1)
0.91
0.03
(2.20)
SRS [Boj. et al. 2020)
1.0
1
1.0
the impact of feature informativeness on the robustness assessment scores [ = with the binary- class datasets PEDec and EHR. The table shows that the classifier becomes less robust to adversarial modifications over Xlm. with less predicative information.
F.5.3 ROBUSTNESS ASSESSMENT AFTER ROBUSTNESS ENHANCEMENT
From the parameter of the decreased SR Table model enhancement techniques. On PEDec, the most robustness assessment scores increase slightly. Notably, the decreased SR of AdvC and NuR are positive and brings the most robustness improvement. On EHR, NuR can prevent attack over all the testing instances. As seen in Table II] the robustness- enhancing techniques induce more visible impact on the pessimistic robustness assessment scores using OMPGS. This result meets the intuitive interpretations in the main paper.
study the robustness enhancement by different
24


Reviews:
[{"review_id": "Y2wd44R7KXj", "reviewer": "Reviewer_SsEb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "> In general I think this paper is clearly written. Discrete inputs' adversarial robustness problem is not well-studied in this community but they are prevalent in language and biomedicine. The authors consider both the pessimistic and the optimistic scenario, which is also an interesting perspective.\n\n> It seems to me that the theoretical results in this paper highly depend on the Lipschitz continuity of the model. This is not surprising and many prior works have shown the connection between adversarial robustness and the model's local Lipschitz. However, it is not clear to me how the Lipschitz number of models in the experiment looks like. I don't think currently we have a good method to accurately evaluate a DNN model's local Lipschitz. I think it would be great if the authors can provide some discussions on this.\n\n> I think it would be better to provide a time complexity analysis and running time comparison of the proposed method. Also, for the greedy approach, in practice, would the loop break early in most cases?", "summary_of_the_paper": "This paper studies the problem of assessing the adversarial robustness of a classifier with categorical inputs, instead of continuous inputs as in the literature. The authors claim that there exist provably optimality guarantees for Lipschitz-continuous classifiers, and proposed an impact factor based on an n information-theoretic analysis. Experimental studies are conducted to support the claims.", "summary_of_the_review": "The problem studied is important and not well-studied in the literature. Some theoretical results are developed, though with strong assumptions. In general, I think this paper is interesting, so I recommend a weak acceptance and would be curious to see other reviewers' opinions as well as the authors' rebuttal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UM1_fhvpoml", "reviewer": "Reviewer_W7KQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros: \n1. Different from the traditional analysis of continuous data, this paper focuses on the vulnerability of categorical data. This research has broad application scenarios for discrete data such as text analysis.\n2. In the method part, the influence of I(x;y,S) and I(f;S) on model robustness is confirmed through rigorous theoretical analysis, and the effect of such influence is confirmed through quantitative data in the experiment part.\n3. The theoretical derivation of the paper is rigorous. The authors set a theoretical association between the smoothness of the targeted classifier and the solvability of both pessimistic and optimistic robustness assessment with categorical inputs. In solving NP knapsack problem, provably accuracy is guaranteed.\n\nAfter reading the paper I have some concerns as follow:\n1. The author explains that the greedy search strategy is chosen because of its adaptability to different classifier architectures. However, I am still confused about the theoretical reasons for not using gradient method, after all, gradient method is more intuitive in solving problems. If the categorical input cannot be adapted through gradient calculation due to discrete data, what are the implementation details of gradient attack for Table 1? If gradient works, is the difference in performance due to the failure to find a better gradient attack, not necessarily the result of a greedy search strategy? \n2. In Table 3, the author uses three defensive measures to verify the effect of reducing model and data set dependency on improving robustness. It restricts the reduction range of I(f;S) by controlling the robustness score equal to 0, but is this control method reasonable? For example, for nuclear norm regularization method, regularizing the model parameters during training can reduce I(f;S), but it will also affect other factors. Relying solely on constraining the final impact threshold result instead of constraining I, can we use this method of comparison to fairly reflect the difference in results?\n", "summary_of_the_paper": "The paper mainly studies the adversarial vulnerability of a classifier with categorical inputs. It theoretically analyzes the key factors that determine the robustness of discrete input data and uses greedy strategy to solve the problem. In the experimental part, the importance of the key factors pointed out by the theory is verified, and the robustness scoring is used to conduct experiments under three defense measures.", "summary_of_the_review": "In summary, the paper is novel, and gives some insights to the adversarial robustness. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6pKsz1S6gAG", "reviewer": "Reviewer_FWFM", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The idea of the paper is somewhat interesting: can we efficiently measure the model robustness to changes in categorical features? The paper explores both the pessimistic and the optimistic measurements. The empirical attack result is in between, which makes sense.\n\nHowever, I have many questions regarding the paper organization and the impact of the results. The writing is really dense and lacks the link between the theoretical result and the experiment. Here are my main questions.\n\n1) Theorem 1 measures the robustness over a specific training set S. Given the randomness of S, why is the statement deterministic? I was expecting something like \"with high probability, the robustness given is random sample of S is at lease some value\". What is the robustness in Theorem 1 with respect to? The underlying distribution or just over the training set? \n\n2) The same question holds for other theorems too. Are the robustness measured on the training set or the data distribution?\n\n3) The optimistic and pessimistic calculation of robustness seems to be heuristics too. Can we assert that they are close to the theoretical value as samples size increases? Or in other words, how do we know how well these estimators are? What's the advantage of using these approximations than just using a practical attack to probe?\n\n4) Theorem 1 seems a bit off the big picture of the paper. There are definitely more important features than others. However, if a feature is really essential to determining the ground truth label, why would we expect robustness to perturbation over this feature? The semantics of the original input may have been changed already...\n\nPlease let me know your thoughts on these questions. Thank you.\n\nIn addition, please do not shrink the font size of an algorithm box unless you don't want the reviewers to read... The theory part is too dense unless they can be linked to finite sample cases.", "summary_of_the_paper": "The paper proposes new methods to gauge model robustness to perturbations in categorical data. The experiments show the effectiveness of such new estimators and corroborates the intuition over model robustness v.s. mutual information over features.\n\n=============================================\nI acknowledge that I've read the author response. The response clarified my questions. Thanks for clarifying that the paper is not centered around defense mechanism but rather robustness validation. That also resolved some of my doubts over the practical use of it. I'm raising my score to 8.", "summary_of_the_review": "Overall, I like the idea of gauging the robustness to changes in categorical features. However at this moment, I feel the setting is slightly artificial and the tightness of the gauge does not come across. (For example, can we estimate the value of $m_{\\Omega}$ and $M_{\\Omega}$?)\n\nI feel the paper can be greatly improved by dropping the mutual information part. It's not contributing to the core ideas. \n\nTherefore, I'm giving a score of 3 for now. I hope the authors can address my questions. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this manuscript, the authors study the relatively unexplored problem of how to characterize and assess the adversarial vulnerability of classification models with categorical input. Even certifying the robustness of such classification models is intrinsically an NP-hard combinatorial problem, the authors show that the robustness certification can be solved via an efficient greedy exploration of the discrete attack space for any measurable classifiers with a mild smoothness constraint. 
Overall, the theoretical analyses in this paper are rigorous, and reviewers seem to be satisfied with the responses from the authors.
Based on the three positive reviewers, this manuscript is recommended to be accepted.
Decision: Accept (Poster)