Year: 2021

Abstract:
Characterizing and assessing the adversarial risk of a 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 to use 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 a classifier with categorical inputs via an information-theoretic adversarial risk analysis. Corroborating these theoretical findings with a substantial experimental study over various real-world categorical datasets, we can empirically assess the impact of the key adversarial risk factors over a targeted learning system with categorical inputs.

heading: 1 INTRODUCTION
text: Categorical data pervasively exist in real-world safety-critical Machine-Learning-as-a-Service (MLaaS) applications, such as ML-driven intrusion detection and digital healthcare. The vulnerability to attacks by intentionally crafting categorical signatures raises concerns on 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 5 with categorical inputs G, the adversarial risk of 5 under evasion attack can be formulated as follows.
Definition 1 5 :G→ H denotes a classifier with categorical inputs G. Let `G,H denote the joint distribution of (G,H). The expected adversarial risk of the classifier 5 under evasion attack is formulated as:
R03EY = E(G,H)∼`G,H sup |diff(G, Ĝ) |≤Y ℓ( 5 (Ĝ),H) (1)
where ℓ is the misclassification loss function, G and Ĝ are an unperturbed and the generated adversarial sample respectively. Y denotes the attack budget of evasion attack. G is correctly classified ( 5 (G)= H).
Intuitively, a classifier 5 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, a categorical variable can be valued with only one categorical value among others. These categorical values have no intrinsic ordering to the categories. Evasion attack manipulating categorical inputs is in nature an NP-hard knapsack problem. The discontinuous nature raises two fundamental yet rarely addressed questions to evaluate the adversarial risk on categorical data in practice:
• Q1 What are the key factors determining 5 ’s adversarial risk R03EY on categorical data ? • Q2 For a general classifier 5 , can we assess the adversarial risk of 5 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 previous progress on adversarial risk analysis with continuous data. The local subspace assumption
of ;?-bounded adversarial attacks does not apply to the categorical features (Hein & Andriushchenko, 2017; Wang et al., 2018; Fawzi et al., 2016; Gilmer et al., 2018; Yin et al., 2019; Khim & Loh, 2018; Tu et al., 2019). Second, most practices of discrete adversarial attack are domain specific and depend heavily on domain knowledge. (Bojchevski & Günnemann, 2019; Bojchevski & Günnemann, 2019; Zugner & 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. (Narodytska & Kasiviswanathan, 2017; Croce & Hein, 2019) conduct !0-norm perturbations only within local image areas containing sensitive features for image classification. (Qi et al., 2019; Wang et al., 2020a) 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 a more general classifier with categorical inputs, a provably optimal and domain-agnostic method for attack and adversarial risk evaluation is yet to establish. Using greedy search or the well-known Branch-and-Bound method on a 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-theoretic characterization of the adversarial risk of a classifier. It unveils that the informativeness of the input categorical instance, the sensitivity of the perturbed categorical features and the information geometry property of the targeted classifier are the three key factors jointly determining adversarial vulnerability of the classifier.
Second, our study adopts an assess-by-attack 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. It 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 to generate adversarial textual and image samples (Gong et al., 2018; Yang et al., 2018; Narodytska & Kasiviswanathan, 2017), but also pave the way to a domainagnostic 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-world applications. The experimental results confirm the impact of the 3 risk factors over the adversarial vulnerability of the DNN classifier.

heading: 2 RELATED WORK
text: Tremendous efforts have been made to vulnerability measurement of a classifier under evasion attack (Hein & Andriushchenko, 2017; Wang et al., 2018; Fawzi et al., 2016; Gilmer et al., 2018; Weng et al., 2019; Sinha et al., 2018; Cohen et al., 2019; Shi et al., 2020; Yin et 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 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 ?-wassernstein ball centered at the training data distribution. This work associates the adversarial risk of a classifier with its rademacher complexity. Nevertheless, we argue that the adversarial vulnerability of a 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-specific knowledge to facilitate the attack exploration. Kuleshov et al. (2018); Papernot et al. (2016); Miyato et al. (2016); Samanta & Mehta (2017); Gao et al. (2018); Yang et al. (2018); Gong et al. (2018); Ebrahimi et al. (2018); Narodytska & Kasiviswanathan (2017); 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); Croce & 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 is no guarantee on a successful attack within the attack budget.
Bojchevski & Günnemann (2019); Bojchevski & Günnemann (2019); D.Zugner et al. (2019); D. Zügner & Günnemann (2018); Akbarnejad & Günnemann (2019) adopt edge-flipping and node attribute perturbation to poison graph data mining pipelines, e.g., graph neural networks and graph embedding models. The key idea is to introduce relaxed surrogate functions to the combinatorial attack objective and then solve the relaxed optimization problem instead. Notably, D.Zugner et al. (2019); D. Zügner & Günnemann (2018); Akbarnejad & Günnemann (2019) define the attack objective as a sum of smallest eigenvalues of the adjacency matrix of a given graph. Though it is not explicitly claimed, it is intrinsically a submodular maximization problem.
Qi et al. (2019); Wang et al. (2020a) unveil that simple greedy search can deliver provably effective attacks against DNN classifiers without domain-specific heuristics, if all the link weights between neurons are non-negative. Non-negativity of the parameter guarantees strict submodularity of the attack objective. However, it brings significantly deterioration of the classifier’s accuracy, which is not applicable for real-world learning tasks.

heading: 3 ROBUSTNESS CHARACTERIZATION AND ASSESSMENT
text: We assume an input instance G = {G1,G2,G3,...,G=} of = categorical attributes. Each G8 takes any of < (< ≥ 1) categorical values. The classifier 5 outputs decision probabilities 5H: (: = 1,2,3,..., ) with respect to different class labels. In practices, each categorical value of G 9
8 is cast to a -dimensional pre-
trained embedding vector, e.g., 4 9 8 ∈R , 9 =1,2,...,<. To represent an instance G with the embedding vectors of its category values, we define binary variables 1= {1 9 8 }, 8=1,2,...,=, 9=1,2,...,<, where 1 9 8 =1 when the 9-th attribute value is present for G8 and 1 9 8 =0 otherwise. An instance G can then be represented by anR=∗<∗ tensor with G {8, 9 ,:} =1 9 8 4 9 8 . Let 1̂= {1̂ 9 8 } indicate the adversarial modifications introduced into 1. For a perturbed Ĝ, its 1̂ ≠ 1. Depending on the type of attacks to implement, e.g., insertion, deletion or substitution, 1̂ differs from 1 in different ways. Without loss of generality, let H denote the true class label of G and all the other H: (: = {1,..., −1}) are the potential targets of an evasion attack. The goal of attack is to make 5H (G,1̂) as low as possible and increase 5H: (G,1̂) of a fixed : (targeted attack) or any : of {1,..., −1} (non-targeted attack) as high as possible simultaneously. We focus on non-targeted evasion attack, and leave the targeted scenario for future study.

heading: 3.1 INFORMATION-THEORETIC CHARACTERIZATION OF ADVERSARIAL VULNERABILITY
text: Theorem 1 For any input instance (G, H) and a training set ( sampled from the same underlying distribution `G,H , 5 ∈ H is trained using ( with a deterministic training paradigm. The expected adversarial risk R03EY defined in Eq.1 can be bounded as in Eq.2, if the loss function ℓ in R03EY adopts the zero-one loss.
R03EY ≥1− 2 (G;H,()−2[G− ( 5H;()/2+const
log (2)
[G = BD? |diff(1,1̂) |≤Y
(G;H,()− (Ĝ;H,() (3)
where const denotes a constant term. diff(1,1̂) indicates the set of the categorical attributes modified in the attack. (G;H,() denotes the mutual information between the feature G and the pair of label H and training set (. [G is the supremum of the difference between the mutual information before and after adversarial perturbation, noted by (G;H,() and (Ĝ;H,() respectively. ( 5H;() denotes the mutual information between ( and 5 .
Theorem 1 unveils the three impact factors jointly determining adversarial vulnerability of the targeted classifier 5 (for answering Q1 in Section 1). The proof is given in Appendix.A. In Eq.2, a lower mutual information (G;H,() indicates higher adversarial risk, i.e., R03EY has a higher lower bound. A lower (G;H,() denotes weaker consistency between the input instance (G,H) and the training set (. The classifier trained by ( thus produces weaker decision confidence for such (G,H). With (G,H) dropped to the ambiguous zone near the classification boundary, the classifier is more prone to adversarial perturbation.
A higher ( 5H ;() leads to a higher adversarial risk according to Eq.2. The mutual information ( 5H ;() reflects the dependence between the classifier 5 and the training set (, which can be considered as
a lower bound of the VC-dimension for countable hypothesis space 5 ∈H (Xu & Raginsky, 2017; Zhu et al., 2020). A higher ( 5H ;() thus denotes that 5 is more likely to suffer from being overfitted to (. Model overfiting is one of the causes of adversarial vulnerability (Tu et al., 2019). Resonating with the association between ( 5H;() and adversarial risk, three popularly used robustness enhancement methods controlling the classifier’s complexity and overfiting risk can potentially adjust the 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 5̂ is less correlated with the original training set ( compared to 5 , which reduces ( 5H ;() and may help mitigate the adversarial threat. 2) The addition of nuclear norm regularization over the classifier’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. et al., 2020). Following (Cohen et al., 2019), 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 distribution, which may reduce adversarial risk.

heading: A higher [G in Eq.3 indicates a higher loss of predicative information by changing G to Ĝ, and thus
text: a higher adversarial risk. In this sense, the vulnerability of the classifier depends on the sensitivity of the attacked categorical features with respect to 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 ;=diff(1,1̂), with which the maximum gap between the classification confidence on any wrong label : and the correct label is larger than a predefined threshold Γ. The size of the minimal perturbation set ; is used to assessment adversarial robustness of 5 over the input instance. Within the perturbation budget Y, a smaller/larger |; | provoking the alert indicates that the classifier’s output on the input G is more/less vulnerable w.r.t. adversarial perturbation in the categorical feature space. We consider both the pessimistic (in Eq. 4) and optimistic scenario (in Eq. 5) from the defender’s perspective for robustness scoring.
kpess (;)= max 1̂8=1...= ,;=diff(1,1̂) max 1̂ 9=1...< 8 (< 5 ) B.C. < 5 ≥Γ, |; | ≤ Y (4)
koptim (;)= min 1̂8=1...= ,;=diff(1,1̂) max 1̂ 9=1...< 8 (< 5 ) B.C. < 5 ≥Γ, |; | ≤ Y (5)
where< 5 = max :∈{1,..., −1} { 5H: (G,1̂)}− 5H (G,1̂) is the gap defined with an input instance G. < 5 ∈ [−1,0) and < 5 ≥ 0 correspond to correct and wrong classification respectively. Γ is a threshold reflecting different levels of tolerance to the perturbation of the classifier’s output. < 5 ≥Γ then triggers an alert of potential adversarial attack. Safety-critical domains, such as cyber security, prefer a lower Γ to provoke alerts even with small yet suspicious input perturbations.
Observation 1 With the threshold Γ = 0, k?4BB ≥ 0 derived by solving the pessimistic assessment problem in Eq.4 produces an empirical estimate of the expected adversarial risk 5 with an input instance (G,H) sampled from `G,H .
We leave the derivation of this observation in Appendix.B. Eq. 4 is a bi-level optimization problem. The inner level seeks the optimal change of the category value of 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< 5 within the attack budget. |; | is thus a pessimistic robustness assessment with respect to a 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. 5 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 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 find the optimal feature combinations to solve the outer-level optimization.
3.3 Provably Accurate Robustness Assessment via Weakly Submodular Maximization
Exactly solving Eq.4 and Eq.5 is still NP-hard. To answer Q2 in Section 1, Theorem 2 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 2 Smoothness Condition of 5 . Let Ω = (?,@), ?,@ ∈ R= and 5 : R=→R be a Lipschitzcontinuous and differentiable function. A function 5 is (<Ω,"Ω)-smooth onΩ, if for any (?,@) ∈Ω, <Ω ∈R and "Ω ∈R+, n = 5 (@)− 5 (?)−〈∇ 5 (?),@−?〉 satisfies:
<Ω
2 ‖@−?‖22 ≤ |n | ≤
"Ω
2 ‖@−?‖22. (6)
Different from (Elenberg et al., 2018), Eq.6 controls only the fluctuation of the function value by varying the input from ? to @ and vice versa, regardless of convexity or concavity of 5 . It allows broader choices of the classifier’s architecture. With W-weak submodularity (Elenberg et al., 2018; Santiago & Yoshida, 2020) defined in Appendix C, we establish Theorem 2.
Theorem 2 LetΩZ = {(1̂,1̂′) : |diff(1,1̂) | ≤ Z, |diff(1,1̂′) | ≤ Z, |diff(1̂,1̂′) | ≤ Z,Z ≥ 1}, where 1̂ and 1̂′ denote two sets of attribute changes. If the classifier 5H: (G) (k=1,..., ) follows the regularity condition given by (<:,ΩZ ,":,ΩZ )-smoothness constraint on ΩZ , the pessimistic and optimistic robustness assessment (with Eq.4 and Eq.5) can be formulated respectively as monotone and non-monotone WZ -weakly submodular maximization.
Let n: = 5H: (G, 1̂′) − 5H: (G, 1̂) − 〈∇ 5H: (G, 1̂), 1̂′ − 1̂〉, and ∇ 5H (G, 1)a denote the elements of ∇ 5H (G, 1) corresponding to the difference between 1̂ and 1̂′, where a=diff(1̂,1̂′). The submodularity ratio Wpess
Z
for the pessimistic robustness assessment is bounded as: W
pess Z
= min :=1,...,
{Wpess :,Z } (7)
where Wpess :< ,Z ≥ ‖∇ 5H: (G,1)a ‖2+<:,Ω1 |Z |/2‖∇ 5H: (G,1)a ‖2+":,ΩZ |Z |/2 for n: ≥ 0, W pess :< ,Z ≥ 2<:,ΩZ ‖∇ 5H: (G,1)a ‖ 2 2 (‖∇ 5H: (G, 1)a ‖2 − ":,Ω1 |Z |/2) for n: < 0, W pess ,Z ≥ 2< ,ΩZ
‖∇ 5H (G,1)a ‖ 2 2 (‖∇ 5H= (G, 1)a ‖2 − " ,Ω1 |Z |/2) for n ≥ 0, and
W pess ,Z ≥ ‖∇ 5H (G,1)a ‖2+< ,Ω1 |Z |/2‖∇ 5H (G,1)a ‖2+" ,ΩZ |Z |/2 for n <0. Similarly, the submodularity ratio W optim Z of the optimistic assessment is: W
optim Z
= min :=1,...,
{Woptim :,Z } (8)
where Woptim :< ,Z
≤ ‖∇ 5H: (G,1)a ‖ 2 2
2":,ΩZ ( ‖∇ 5H: (G,1)a ‖2−<:,Ω1 |Z |/2) for n: ≥0, W
optim :< ,Z ≤ ‖∇ 5H: (G,1)a ‖2+<:,ΩZ |Z |/2 ‖∇ 5H: (G,1)a ‖2+":,Ω1 |Z |/2 for n: <0,
W optim ,Z ≤ ‖∇ 5H (G,1)a ‖2+< ,ΩZ |Z |/2 ‖∇ 5H (G,1)a ‖2+" ,Ω1 |Z |/2 for n ≥0, and Woptim ,Z ≤ ‖∇ 5H (G,1)a ‖ 2 2 2" ,ΩZ ( ‖∇ 5H (G,1)a ‖2−< ,Ω1 |Z |/2) for n <0.
Enjoying the weak submodularity, the pessimistic and optimistic assessment can 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.5), a stochastic variant of the standard FSGS, namely Randomized FSGS (RandGS) is adopted, following the suggestion in (Buchbinder et al., 2014). We give the pseudo codes of FSGS and RandGS in Algorithm.1 and 2 in Appendix.D. Compared to FSGS, the difference in RandGS is to randomly select one of the top-ranked candidate features contributing with the largest marginal gain < 5 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 (<ΩZ ,"ΩZ )-smooth classifier 5 , the approximation quality of the solution ; to Eq.4 and Eq.5 is bounded respectively as
|< 5 (;) |+4−W pess Z ≤ (1−4−W pess Z ) |< 5 (;∗?4BB) | (Pessimistic Assessment)
|< 5 (;) | ≥ 1
W optim Z
4 −Woptim Z |< 5 (;∗>?C8<) | (Optimistic Assessment)
(9)
where Wpess Z and Woptim Z are the submodularity ratio in Eq. 7 and Eq. 8, respectively. ;∗?4BB and ; ∗ >?C8< are the true optimal solutions to the two problems.
With Theorem 3, the Q2 in Section.1 is fully addressed. Notably, any classifier with a finite Lipshitz constant meets the smoothness condition. For practical estimation, "ΩZ can be computed as local Lipshitz constant of 5 if n >0 in Definition.2 (or − 5 (G) if n <0). Furthermore,<ΩZ can be calculated as the local strong convexity constant of 5 (G) if n >0 in Definition.2 (or − 5 (G) if n <0). Recent works (Fazlyab et al., 2019; Jordan & Dimakis, 2021) have shown that a large number of neural networks are Lipschitz continuous, such as the fully-connected 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 5H plays in characterizing the solvability of the robustness assessment problem. As indicated by Eq. 7 and Eq. 8, a smoother 5: with smaller<:,ΩZ and ":,ΩZ has a higher submodularity ratio (W pess :,Z and Woptim :,Z
). 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. 7 to 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 a classifier is more vulnerable to a knowledgeable adversary than an oblivious one.

heading: 3.4 ORTHOGONAL MATCHING PURSUIT GREEDY SEARCH FOR ROBUSTNESS ASSESSMENT
text: 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 ∑) C=0 ((=−C)∗<∗2C ) objective function evaluations for ) iterations, where = denotes of the number of categorical features in an instance G and each feature can choose any of the< 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., 2020a), 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 ∇ 5H (G)1̂ (the gradient of 5H w.r.t. the binary indicators 1̂ 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 = and<. Due to the space limit, the algorithm implementation of OMPGS are explained in Algorithm.3 in Appendix.E.
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., 2020a) 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 4. Comparing to Theorem 3, OMPGS achieves a lower but similar approximation accuracy to the underlying optimal solution to the optimistic assessment (Eq. 5).
Theorem 4 Following the notations in Theorem 2 and Theorem.3, the approximation quality of the optimistic assessment score |; | obtained by OMPGS is bounded as in the followings:
|< 5 (;) | ≥ 1 k 4−k |< 5 (;∗>?C8<) |, k=max{i: }(: =1,2,3,..., )
i: =max{ ‖∇ 5H: (G,1)a ‖22 2"k,ΩZ (‖∇ 5H: (G,1)a ‖2−<:,Ω1 |Z |/2) , ‖∇ 5H: (G,1)a ‖2+<:,ΩZ |Z |/2 ‖∇ 5H: (G,1)a ‖2+":,Ω1 |Z |/2 } (10)
In both of the pessimistic and optimistic assessment, the gradient magnitude used by OMPGS can be interpreted as an upper bound of the increase of< 5 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 is taken with respect to the binary indicator variable 1 9
8 (see Section.3). We rank the categorical features according to the magnitudes of
the gradients with respect to different 1 9 8 . A higher gradient magnitude indicates that the corresponding categorical feature G8 =G 9 8 can contribute higher marginal gain of< 5 . OMPGS narrows down range of greedy search. Only the top ranked candidate features are considered to modify.

heading: 4 EXPERIMENTAL STUDY
text: 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 (Yelp)(Asghar, 2016). The Yelp-5 reviews dataset was obtained from the Yelp Dataset Challenge in 2015. We use the reviews containing 650K training and 50K testing samples with the classes from 1 star to 5 stars for learning classifier. Each word is a categorical feature with 300-dim embedding.
Intrusion Prevention System Dataset (IPS) (Wang et al., 2020a). The IPS dataset has 242,467 instances, each of which is a 20-step attack sequence and represented by G ∈R20∗1103∗70, because each step can be a categorical value from 1,103 different malicious actions embedded in 70-dim space by word embedding. An G is classified with 3 labels: attack type 1, attack type 2, and others.
Splice-junction Gene Sequences (Splice) (Noordewier et al., 1991). This dataset has 3,190 samples. Each one is 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 as G ∈R60∗5∗30. The task is to predict each splice instance as an intro-exon boundary (IE), an exon-intro boundary (EI), or neither of them.
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 F.1. To strengthen the universality of the robustness assessment framework, we also include additional results on binary-classification datasets using Convolution Neural Networks (CNN) in Appendix.F.5
The experimental study is to address questions below: 1) What’s the robustness assessment result of a targeted classifier? (Empirically evaluate the answer in Theorem 2,3 and 4 to Q2 in Section 4.1). For the classifier trained on each dataset, we first find the robustness assessment |; | for each data instance. We report the median and mean value of all the |; | derived on the dataset. A lower/higher median value indicates a weaker/stronger robustness of the classifier to the adversarial attack over the given data set. The tolerance threshold Γ is tested on −0.4 and 0 to assess our 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.4) and RandGS and RandOMPGS (for solving Eq.5) , we also include Gradient-based Attack (GradAttack) from (Qi et al., 2019) in the evaluation. GradAttack tackles only the pessimistic assessment problem. The comparison with GradAttack is to verify the merit of FSGS and its variants in solving the robustness assessment problem of a general classifier. For RandGS and OMPGS, we empirically choose 10 candidate features in each iteration of greedy search1. 2) Can the information-theoretic characterization of adversarial vulnerability in Theorem 1 be verified using the proposed robustness assessment? (Empirically evaluate the answer in Theorem 1 to Q1 in Section 4.2 and 4.3). We verify an increase of risk on G;<8 with lower mutual information, i.e., (G;<8 ;H,() < (G;H,(), and verify an increase of robustness by reducing ( 5H;(). 3) We compare the time complexity of FSGS,OMPGS and GradAttack. 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 to GradAtttack, OMPGS has a better chance to select the really useful feature modifications, thus costing fewer loops. We provide the results in Appendix.F.3 due to the space limit.

heading: 4.1 ROBUSTNESS ASSESSMENT WITH GREEDY SEARCH
text: Besides showing the median and mean of the assessment score |; | (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< 5 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< 5 to surpass the threshold Γ 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. %/$ denotes the pessimistic or optimistic assessment respectively.
1Implementations are available at https://github.com/XYZ211923Y/-RobustXXXXX.
Table 1 shows several interesting findings. First, for both the pessimistic and optimistic robustness assessment, a lower tolerance threshold Γ 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 5 , it is 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/RandGS needs 217.65 and 1123.51 seconds on average on each data sample for the pessimistic and optimistic assessment. In contrast, OMPGS/RandOMPGS costs only 0.24 and 1.59 seconds for the pessimistic 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 GradAttack 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 to the robustness assessment problem.
We conduct one-factor-at-a-time sensitivity analysis on each dataset (Campbell 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 output over all the testing instances is used as the feature-wise sensitivity measurement. A larger value indicates that the classifier’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 FSGS,GradAttack 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.

heading: 4.2 ROBUSTNESS VS FEATURE INFORMATIVENESS
text: According to the discussion in Theorem 1, a lower (G;H,() indicates a higher adversarial risk on the input instance (G,H), implying a smaller robustness assessment score. To verify such impact of feature informativeness, we compare the robustness on G and on G;<8 that has a lower mutual information, i.e., (G;<8 ;H,() < (G;H,(). The sample G;<8 is constructed as those on the half-way of pushing the < 5 of the original sample G to surpass Γ. For each dataset, we select the instances requiring at the least two modified features in order to deliver a successful attack. These instances are treated as original. There are 125, 414 and 324 original instances in Yelp, IPS, and Splice respectively. The results in Table 2 confirm that the classifier becomes less robust to adversarial modifications over G;<8 samples in the ambiguous zone, i.e., higher SR and smaller |; | on the G;<8 samples than the original samples G.

heading: 4.3 ROBUSTNESS WITH DEFENSIVE TECHNIQUES
text: As discussed in Theorem.1, reducing ( 5H;(), the dependence of a classifier over the training set (, improves the classifier’s adversarial robustness. We tune a classifier via adversarial training (AdvC), the nuclear-norm based regularization (NuR) following (Ravi et al., 2019) and random smoothing by (RS) as suggested in (Boj. et al., 2020) to reduce ( 5H ;(), and then evaluate if the pessimistic robustness assessment becomes higher, e..g, descrese of SR. To adopt adversarial training, we solve Eq. 4 using
OMPGS until the value of< 5 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 al., 2019). The random smoothing is conducted by randomly flipping the values of input categorical features (RS) with ?− = 0.6 and ?+ = 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 a 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 a wrong classification, a.k.a. certifiable robustness, is then estimated via a dimension-independent evaluation based on the randomly flipped features. SRS (Boj. et al., 2020) is reported to be significantly more efficient and produce tighter robustness assessments than other random smoothing-based methods (Lee et al., 2019; Levine & Feizi, 2020; Dvijotham et al., 2020).
Table 3 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 with Γ=−0.4 as they present a similar variation tendency. Both adversarial training and nuclear-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 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.1, highly sensitive features can be witnessed in many diversified applications. Firstly, flipping these sensitive features can lead to miss-classification rather than providing robustness. Secondly, if random flipping misses the sensitive features, the adversary can still target at these features to deliver a successful attack.

heading: 5 CONCLUSION
text: We unveil the key factors that jointly determine the adversarial vulnerability of a classifier with categorical inputs via information-theoretic analysis. The characteristics 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 real-world safety-critical applications. Our future work will pursue to provide tighter quality bound for assessing adversarial robustness assessment on categorical data.

heading: A PROOF FOR THEOREM 1
text: Lemma 1 Supposing and are two independent random variables and U is given by %* =% %* | :
(*; )+ (*; ) ≤2 (*; , ) (11)
Proof: Given the definition of mutual information (-;. )= (-)− (- |. ), we need to prove: 2 ( , |*) ≤ ( |*)+ ( |*) (12)
With the chain rule of conditional entropy:
( , |*)= ( |*)+ ( | ,*) (13) It indicates that ( , |*) ≤ ( |*), as ( |*) ≥0. Similarly, we can derive ( , |*) ≤ ( |*) as well. Combing both inequality relations, Eq.12 holds, which in turn proves Eq.11.
Considering the markov chain in Figure.1, we assume a class label Y and the training set ( are statistically independent. 5 depends on S as 5 =A((), whereA is the training paradigm (could be randomized). The generation of the adversarial example - ′ depends on both the clean feature vector - and the targeted classifier 5 . This is consistent with the fact that generating adversarial samples needs to understand the local geometry property of the decision boundary of the targeted classifier. Once we get the perturbed feature vector - ′, the classification output. ′= 5 (- ′).
We can derive the lower bound of the miss-classification probability with the perturbed categorical input G ′ following Fano inequality:
R03EY =%(H′≠ H | |diff(1,1̂) | ≤ Y) ≥ 1− (. ′;.,()+const
log (14)
where denotes the number of the classes in the learning task. Based on Data Processing Inequality illustrated in Chapter 2 (Mack, 2006), we can further obtain:
R03EY ≥ 1− (- ′;.,()+const
log ( (. ′;.,() ≤ (- ′;.,())
=1− 2 (-;.,()−2[-− (- ′;.,()+const
log
(15)
where [- = (-;.,()− (- ′;.,() denotes the mutual information difference between the unperturbed - and the adversarially perturbed instance - ′. By applying Lemma.1 on (- ′;.,() in Eq.15, we have
R03En ≥1− 2 (-;.,()−2[-− (- ′;()/2
log
≥1− 2 (-;.,()−2[-− ( 5 ;()/2 log
(DataProcessingInequality, ( 5 ;() ≥ (- ′;()) (16)

heading: B EXPLANATION TO OBSERVATION.1
text: First, we follow the IID assumption in the definition of the expected adversarial risk in Eq.1. We assume ℓ adopts the form of zero-one loss function. If 5 (Ĝ) ≠ H, ℓ( 5 (Ĝ) ≠ H)) = 1. Otherwise, ℓ = 0. With this setting of the loss function, the expected adversarial risk of the classifier 5 can be formulated as in Eq.17. This gives Eq.1 (the adversarial risk of 5 ) in the main paper.
R03EY = sup G∼`G , |diff(G, Ĝ) |≤Y %[ 5 (G)≠ 5 (Ĝ)] (17)
where % denotes the probability measurement. In this sense, the expected adversarial risk of R03EY can be explained intuitively as the maximum miss-classification probability over an adversarial sample Ĝ, with the underlying data distribution `G,H and the attack budget limited by Y.
Second, Theorem.1 provides the information-theoretical lower bound of R03EY with respect to the data distribution `G,H . Indeed, for any given training data set ( sampled from the joint distribution `G,H ,
( can be considered as a random variable. Similarly, given a deterministic training paradigmA, the classifier 5 =A(() (trained with ( using the training algorithmA) can be also treated as a random variable in the hypothesis space. For a testing input (G,H) sampled from the same distribution `G,H as (, deriving Theorem.1 follows Fano’s inequality in information theory (Chapter 2 in (Mack, 2006)):
• For any G ∼ `G and (G, H) ∼ `G,H , following Fano’s inequality, we can produce the lower bound of miss-classification probability over the adversarial sample Ĝ generated from G (based on the information of H and 5 ):
%( 5 (G)≠ 5 (Ĝ) | G∼`G ,|diff(G,Ĝ) | ≤ Y) ≥ 1− 2 (G;H,()−2[G− ( 5 ;()/2+const
log (18)
where 5 (G)= H. The lower bound of the miss-classification probability is composed by three mutual information measurements among the random variables (G,H), ( and 5 .
• By definition, the following inequality holds:
R03EY = sup G∼`G , |diff(G, Ĝ) |≤Y %[ 5 (G)≠ 5 (Ĝ)] ≥ %( 5 (G)≠ 5 (Ĝ) | G∼`G ,|diff(G,Ĝ) | ≤ Y)
≥1− 2 (G;H,()−2[G− ( 5 ;()/2+const log
(19)
where (G,H) ∼`G,H , (∼`G,H and 5 ∈H .
From this perspective, Theorem.1 establishes a lower bound of the expected adversarial risk of 5 : Given a deterministic training paradigmA, for any training data set ( and any testing input instance (G, H) sampled from the underlying data distribution `G,H , the miss-classification probability of 5 over the adversarial sample generated from G (based on H and 5 ) can be bounded by the three mutual information measurements (G;H,(), [G and ( 5 ;(), as in Eq.2 and 3 of Theorem.1 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 et al., 2019), where the expected adversarial risk of a classifier 5 is measured by the maximum classification loss over the distribution of adversarial samples (Definition.1 in (Tu et al., 2019)):
R03E = E G,H∼`G,H [ sup Ĝ∈# (G)
ℓ( 5 (G ′),H)] (20)
where # (G) denotes the neighbor set of G derived by modifying features in G. The coverage of the neighboring set # (G) can be measured by ;? distance for continuous data or ;0 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 5 (noted as RY,`G,H ):
R03E ≤Rn ,`G,H = E Ĝ∼`Ĝ ,`Ĝ∼B,? (`G ,Y) ℓ( 5 (Ĝ),H) (21)
where ` Ĝ is a distribution sampled from the ?-Wassernstein ball (? ≥ 1) centered at `G and with a radius of Y. # (G) ⊆ ` Ĝ . Second, the expected adversarial riskR03EY can be bounded by the upper bound of the local worst-case risk of 5 consisting of the rademarcher complexity of 5 and the empirical risk of 5 , according to Theorem.1 and Remark.3 in (Tu et al., 2019). This upper bound holds with probability at least 1−X:
R03E ≤ R̂03E%= +2<= (k( 5 ))+" √ ;>6(1/X)
2=
R̂03E%= = 1 = =∑ 8=1 max Ĝ8∼`Ĝ ℓ( 5 (Ĝ8 ,H8)) (22)
where R̂03E %= denotes the adversarial empirical risk calculated using = IID samples from the adversarial data distribution ` Ĝ . Practically, R̂03E%= can be estimated by calculating the maximum classification loss reached by perturbing G within the attack budget. " denotes the maximum output value of 5 . <= (k( 5 )) denotes the expected rademarche complexity of an augmented function defined on 5 . The value of <= (k( 5 )) is independent from the empirical adversarial risk R̂03E%= . The formulation of <= (k( 5 )) can be found on Page 10 of (Tu et al., 2019).
Our work differs from the results in (Tu et al., 2019) from the following perspective. The core contribution of (Tu et al., 2019) is to associate the Rademacher complexity of the classifier 5 with 5 ’s expected adversarial risk. Beyond that, for a classifier adopted in a learning scenario, we believe both the characteristics of input data and the classifier’s complexity measurement determine its adversarial risk. As shown by the mutual information-based lower bound (Eq.2 and 3 of Theorem.1), the mutual information ( 5 ;() measures the dependence of a trained 5 over the training data ( sampled from `G,H . ( 5 ;() can be considered as the lower bound of the VC-dimension of 5 (Xu & Raginsky, 2017; Zhu et al., 2020), which encodes the classifier’s complexity. The other two mutual information measurements (G;H,() and [G relates to the characteristics of the input data (G,H). Intuitively, (G;H,() measures the informativeness of G for classification. A lower (G;H,() denotes weaker consistency between the input data instance (G, H) and the training data set (. [G 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.
Relations to the proposed robustness measurement. Since it is not feasible to directly compute the expected riskR03EY , 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 5 over the data distribution `G,H is computed as a sample average,
R̂03E ( 5 )= 1 = =∑ 8=1 max Ĝ8 , |diff( Ĝ8 ,G8) |≤Y ℓ( 5 (Ĝ8),H8). (23)
To facilitate computing, we adopt a smooth loss ℓ as a surrogate function approximating the zero-one loss. In Eq.(23), max
Ĝ8 , |diff( Ĝ8 ,G8) |≤Y ℓ( 5 (Ĝ8),H8) is to estimate the maximum classification loss of 5 over
the adversarial sample Ĝ8 , which is generated by modifying at most Y categorical features of G8 . By its nature of set function maximization, R̂03E ( 5 ) 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 Γ = 0 in Eq.4 in the main paper, the pessimistic estimate k?4BB (defined by 5H: − 5H ) is proportional to the classification loss, and gives the miss-classification confidence of the target classifier at G with the attack budget limited by Y. this “miss-classification confidence” is the empirical estimator of the adversarial risk 5 has a given input G, or called robustness.

heading: C PROOF FOR THEOREMS ON THE WEAK SUBMODULARITY
text: We introduce the notion of W-weak submodularity used in Theorem 2.
Definition 3 Monotone and W-weakly submodular function (Santiago & Yoshida, 2020). A set function 6(() is monotone, if for every) ⊂ (, we have 6(() ≥6()). Given a set cardinality threshold : ≥1 and a scalar value W ∈ [0,1]. We define W: of 6(.) w.r.t. a set ( as:,
W: = <8= (⊆ , : | | ≤:,(∩ =∅ ∑ 0∈ 6((∪0)−6(() 6((∪ )−6(() (24)
If 6(() is monotone and W: > W for any : , 6(() is a W-submodular function. Otherwise, 6(() is W-submodular, if 6(() is non-monotone but 6(() follows for any ::∑
0∈ 6((∪0)−6(() ≥ {W(6((∪ )−6(()),1/W(6((∪ )−6(())} (25)
It is easy to find, if 6(() is monotone and W≥1, 6(() is submodular.
Proof of deriving the robustness assessment score under the pessimistic scenario in Eq.7: we first formulate pessimistic scenario as a set function optimization,
(∗=max ( { max :=1,2,3,..., −1 { : (()}+( (())}
: (()=max ;⊂( 5: (1;)
(()=max ;⊂( 5̃ (1;)
(26)
where 1; denotes the modification of categorical features indicated by the index set ;. 5̃ (1;)=− 5 (1;). For each : ∈ 1,2,3,..., , n: = 5: (@) − 5: (?) − 〈∇ 5: (?),@− ?〉. : (() and (() are monotonically non-decreasing set functions.
Supposing n: ≥ 0 for each : ∈ {1,2,3, ..., − 1}, we assume further that the features indicated by ; ′ are modified in addition to ;, with |; ′ | ≤ Z . For any 1; , 1;∪;′ and 1;∪ 9 denote the additional modification over the features indicated by ; ′ and by 9 respectively to increase the output of 5: (increasing the miss-classification decision confidence) and − 5 (decreasing the confidence of correct classification). In the following analysis, we relax the discrete indicator 1 to the continuous domain, as each 18 ∈ [0,1]. ∇ 5: (1;) denotes the gradient of the classifier function 5: with respect to the variable 1 at 1 = 1; . Modifying from 1; to 1;∪;′ or 1;∪ 9 follows the direction of gradient ascent, which gives 〈∇ 5: (1;),1;∪;′−1; 〉 ≥0 and 〈∇ 5: (1;),1;∪ 9−1 9 〉 ≥0, 〈∇ 5̃ (1;),1;∪;′−1; 〉 ≥0 and 〈∇ 5̃ (1;),1;∪ 9−1 9 〉 ≥0.
5: (1;∪;′)− 5: (1;) ≤ 〈∇ 5: (1;),1;∪;′−1;〉+ ":,ΩZ
2 ‖1;∪;′−1; ‖22
≤ ‖∇ 5: (1;)Z ‖2+ ":,ΩZ 2 |Z |∑ 9∈Z 5: (1;∪ 9 )− 5: (1;) ≥ ∑ 9∈Z 〈∇ 5: (1;),1;∪ 9−1;〉+ <:,Ω1 2 ‖1;∪ 9−1; ‖22
≥ ‖∇ 5: (1;)Z ‖2+ <:,Ω1
2 |Z | ( 5: isnon-decreasing)
(27)
We can derive the lower bound of the submodularity ratio W:,Z of 5: :
W:,ΩZ = ∑ 9∈Z 5: (1;∪ 9 )− 5: (1;) 5: (1;∪;′)− 5: (1;) ≥ ‖∇ 5: (1;)Z ‖2+ <:,Ω1 2 |Z |
‖∇ 5: (1;)Z ‖2+ ":,ΩZ 2 |Z | (28)
Supposing n: <0 for each : ∈ {1,2,3,..., −1}, we can derive:
5: (1;∪;′)− 5: (1;) ≤ 〈∇ 5: (1;),1;∪;′−1;〉− <:,ΩZ
2 ‖1;∪;′−1; ‖22 ≤ 1 2<:,ΩZ ‖∇ 5: (1;)Z ‖22∑ 9∈Z 5: (1;∪ 9 )− 5: (1;) ≥ ∑ 9∈Z {〈∇ 5: (1;),1;∪ 9−1;〉− ":,Ω1 2 ‖1;∪ 9−1; ‖22}
≥ ‖∇ 5: (1;)ΩZ ‖2− ":,Ω1
2 |Z | ( 5:8Bnon-decreasing)
(29)
Given the smoothness assumption on the targeted classifier (See Definition.2), there exits a value of ":,Ω1 |Z |/2≤ ‖∇ 5: (1;)Z ‖2, which allows that ‖∇ 5: (1;)Z ‖2− ":,Ω1 2 |Z | ≥ 0 holds. Therefore, we can derive the lower bound of the submodularity ratio of : and − , W:,Z (k=1,2,3,...,K):
W:,ΩZ = ∑ 9∈Z 5: (1;∪ 9 )− 5: (1;) 5: (1;∪;′)− 5: (1;) ≥ 2<:,ΩZ ‖∇ 5: (1)a ‖22 (‖∇ 5: (1)a ‖2−":,Ω1 |Z |/2) (30)
The submodularity ratio WZ onΩZ in Eq.26 is WZ = min :=1,2,3,..., {W:,ΩZ }.
Proof of deriving the robustness assessment score under the optimistic scenario in Eq.8. Following the setting of Eq.26, we can formulate the robustness assessment problem at the optimistic scenario (with an oblivious adversary) :
(∗=max ( { (()+ min :=1,2,3,..., −1 {̃: (()}}
̃: (()=min ;⊂( ℎ: (1;)
(()=min ;⊂( 5 (1;)
(31)
Both : (() and ̃: (() are non-increasing with ℎ: (1;)=− 5: (1;). Eq.31 thus defines a non-monotone set function maximization problem (See Definition.3). We conduct the analysis as in Eq.27 and Eq.29. Modifying 1; to 1;∪;′ and 1;∪ 9 follows the direction of gradient descent, which gives 〈∇ 5 (1;),1;∪ 9− 1;〉 ≤0 and 〈∇ 5 (1;),1;∪;′−1;〉 ≤0, 〈∇ℎ: (1;),1;∪ 9−1;〉 ≤0 and 〈∇ℎ: (1;),1;∪;′−1;〉 ≤0.
Supposing n ≥0, we can derive:
5 (1;∪ 9 )− 5 (1;) ≥ 〈∇ 5 (1;),1;∪ 9−1;〉+ < ,Ω1 2 ‖1;∪ 9−1; ‖22
5 (1;∪ 9 )− 5 (1;) ≤ 〈∇ 5 (1;),1;∪ 9−1;〉+ " ,Ω1 2 ‖1;∪ 9−1; ‖22 5 (1;∪;′)− 5 (1;) ≥ 〈∇ 5 (1;),1;∪;′−1;〉+ < ,ΩZ
2 ‖1;∪;′−1; ‖22
5 (1;∪;′)− 5 (1;) ≤ 〈∇ 5 (1;),1;∪;′−1;〉+ " ,ΩZ
2 ‖1;∪;′−1; ‖22
(32)
and
ℎ: (1;∪ 9 )−ℎ: (1;) ≤ 〈∇ℎ: (1;),1;∪ 9−1;〉− <:,Ω1 2 ‖1;∪ 9−1; ‖22
ℎ: (1;∪ 9 )−ℎ: (1;) ≥ 〈∇ℎ: (1;),1;∪ 9−1;〉− ":,Ω1 2 ‖1;∪ 9−1; ‖22 ℎ: (1;∪;′)−ℎ: (1;) ≤ 〈∇ℎ: (1;),1;∪;′−1;〉− <:,ΩZ
2 ‖1;∪;′−1; ‖22
ℎ: (1;∪;′)−ℎ: (1;) ≥ 〈∇ℎ: (1;),1;∪;′−1;〉− ":,ΩZ
2 ‖1;∪;′−1; ‖22
(33)
From Eq.32, we conduct the similar analysis as in Eq.22 and 23, which gives the submodularity ratio at the optimistic case: ∑
9∈;′ 5 (1;∪ 9 )− 5 (1;) ≥
< ,Ω1 |Z | 2 −‖∇ 5 (1;)Z ‖2
5 (1;∪;′)− 5 (1;) ≤ " ,ΩZ |Z |
2 −‖∇ 5 (1;)Z ‖2
(34)
∑ 9∈;′ ℎ: (1;∪ 9 )−ℎ: (1;) ≥ ∑ 9∈;′ 〈∇ℎ: (1;),1;∪ 9−1;〉− ":,Ω1 2 ‖1;∪ 9−1; ‖22 ≥− ":,Ω1 |Z | 2 −‖∇ℎ: (1;)Z ‖2
ℎ: (1;∪;′)−ℎ: (1;) ≤ 〈∇ℎ: (1;),1;∪;′−1;〉− <:,ΩZ
2 ‖1;∪;′−1; ‖22 ≤ −<:,ΩZ |Z | 2
−‖∇ℎ: (1;)Z ‖2 (35)
Let W: ∈ (0,1) and− ":,Ω1 |Z | 2 −‖∇ℎ: (1;)Z ‖2 ≥ 1 W: ( −<:,ΩZ |Z | 2 −‖∇ℎ: (1;)Z ‖2). The submodularity ratio of ℎ: , W: ≤ <:,ΩZ |Z | 2 +‖∇ℎ: (1;)Z ‖2
":,Ω1 |Z | 2 +‖∇ℎ: (1;)Z ‖2
.
Proofs to Theorem.3 (Eq.9). In the pessimistic scenario, assessing adversarial robustness can be formulated as a problem of monotone weakly submodular function maximization. Assuming that < 5 (;) is the solution ; obtained by the FSGS method and < 5 (;∗) is the optimal solution ;∗ to Eq.4. Based on Theorem.3 in (Elenberg et al., 2018), we can obtain:
1−|< 5 (;) | ≥ (1−|< 5 (;∗) |) (1−4−W ?4BB
Z ) (36) Therefore, we can derive the first inequality (the pessimistic scenario) in Eq.9
|< 5 (;) |+4−W ?4BB Z ≤ (1−4−W ?4BB Z ) |< 5 (;∗) | (37)
Assessing adversarial robustness in the optimistic scenario (Eq.5) is in nature a problem of nonmonotone weakly submodular function maximization. Assuming that< 5 (;) is the greedy search based solution obtained by the RandGS (Randomized Greedy Search) and< 5 (;∗) is the optimal solution to Eq.5. Applying Theorem 1.9 (Santiago & Yoshida, 2020) directly, we can obtain:
|< 5 (;) | ≥ 1
W >?C8<
Z
4 −W>?C8< Z |< 5 (;∗) | (38)
The proof to the approximation gap of OMPGS in Eq.10 follows the proof to Theorem 2.4 and Theorem 3 (Santiago & Yoshida, 2020).

heading: D ALGORITHM PSEUDO CODES FOR FSGS AND RANDGS BASED ROBUSTNESS ASSESSMENT
text: Algorithm 1 FSGS for the pessimistic robustness assessment Input: The candidate set ={08}8=1...= of all modifiable features Output: The maximum support set ;8 pushing< 5 (;8) to violate the tolerance constraint in Eq. 4 1: ;0←∅ 2: for C=0,1,2,...,d do 3: )←zero-valued vector∈R= 4: for each 08 ∈ /;C−1 do 5: ) (08)=argmax
B⊂;C−1 < 5 (B∪08) (Inner level Optimization)
6: end for 7: 0̃=argmax
08
) (08) (Outer level Optimization)
8: ;8←;8−1∪{0̃} 9: < 5 (;8)←< 5 (;8−1∪0̃)
10: if< 5 (;8) ≥Γ then break 11: end for
Algorithm 2 RandGS for the optimistic robustness assessment Input: The candidate set ={08}8=1...= of all modifiable features Output: The maximum support set ;8 pushing< 5 (;8) to violate the tolerance constraint in Eq. 5 1: ;0←∅ 2: for C=0,1,2,...,d do 3: )←zero-valued vector∈R= 4: for each 08 ∈ /;C−1 do 5: ) (08)=argmax
B⊂;C−1 < 5 (B∪08) (Inner level Optimization)
6: end for 7: " ⊂ /;C−1 be a subset of size g 8: minimizing ∑ 08 ∈") (08) (Outer level Optimization)
9: Let 0̃ be a uniformly random element from " 10: Let B̃(0̃) be the subset corresponding to 0̃ 11: ;8←;8−1∪{0̃} 12: < 5 (;8)←<8={< 5 (0̃∪ B̃(0̃)),< 5 (;8−1)} 13: if< 5 (;8) ≥Γ then break 14: end for

heading: E ORTHOGONAL MATCHING PURSUIT GREEDY SEARCH
text: The pseudo codes of OMPGS is presented in Algorithm 3, which explains how it is adopted to solve Eq.4 and Eq.5. In each iteration, for each subset B of the previous support set ;:−1, we compute the gradient of 5H with respect to bB (binary indicator matrix b with the entries in B changed). The top-: ′ attributes with the largest magnitudes in the gradient vector are selected to form a candidate set B̂. We can then find out the optimal attribute 9 ∈ B̂ to extend for each subset B and record the optimal attack objective value 6(;:−1∪ 9). In the outer iteration, we choose finally the attribute 9∗ producing the largest marginal gain to add into ;:−1. The worst case cost of objective function evaluation in each iteration of OMPGS is bounded by $ ((∑:−18=1 8: )) |: ′ |. We adjust : ′ to achieve a trade-off between enlarging the search range of greedy search and the cost of function evaluation. Usually : ′ is much less than | |− |;: |, especially when is significantly large (e.g. >10k). Thus OMPGS runs significantly faster than FSGS.
We further illustrate the rationality of using the orthogonal matching pursuit step in OMPGS to solve the weakly submodular maximization based assessment problem. In Eq. 39, we unveil that the gradient
Algorithm 3 Orthogonal Matching Pursuit based Greedy Search (OMPGS) Input: The attack budget , the set function based attack objective 6(;) and the set = {(8, 9),8 =
1...=, 9 =1...<} of all the modifiable discrete attributes selected support set ;: , with |;: | ≤ ; Output: 6(;: ) and the optimal subset of ;: achieving the attack goal (0←∅ 1: for : =1,2,..., do 2: ) =∅ 3: for B⊂ ;:−1 do 4: A←∇ 5H (bB) 5: B̂= { 91, 92,..., 9:′}← argmax
9∈{ /;:−1 } |<4 9 ,A > |
6: 9̃←argmax 9∈B̂ 6(;:−1∪{ 9}) 7: ) =)∪{( 9̃ ,6(;:−1∪ 9̃))} 8: end for 9: 9∗←argmax
9∈) 6(;:−1∪{ 9})
10: ;:←;:−1∪{ 9∗} 11: end for
magnitude of 5H with respect to the binary indicator variables 1 9 8 can be used as an estimator of the marginal gain of< 5 in each iteration of the greedy search of OMPGS.
We assume that 1̂ and 1̂′ denote two sets of categorical attribute changes. 1 indicates the category value assignment of an unperturbed data instance Ĝ. |diff(1,1̂) | ≤ Z, |diff(1,1̂′) | ≤ Z, |diff(1̂,1̂′) | ≤ Z,Z ≥ 1. The targeted classifier is denoted as 5H: (G) (k=1,...,K), in which K is the correct class label.
| 5H: (Ĝ,1̂′)− 5H: (Ĝ,1) | ≤<0G{ 1
2<:,Z ‖∇ 5H: (G,1̂)a ‖22, ‖∇ 5H: (G,1̂)a ‖2+":,ΩZ |Z |/2}
| 5HK (Ĝ,1̂′)− 5HK (Ĝ,1̂) | ≥<8={ 1
2"K,Z ‖∇ 5HK (G,1̂)a ‖22, ‖∇ 5HK (G,1̂)a ‖2+<:,ΩZ |Z |/2}
(39)
where a=diff(1̂,1̂′).

heading: F EXPERIMENTAL EVALUATION
text: We first introduce the evaluation datesets in section F.1, the experimental setup in section F.2, and the complexity analysis and running time in section F.3. 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.4 as the supplementary information to the main text. We add the the robustness assessment with the binary-class datasets PEDec and EHR in F.5. It includes the summarised table on the robustness assessment and the information-theoretic characterization of adversarial vulnerability verified in the experiment.

heading: F.1 DATASET INFORMATION
text: 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. In the classifier training process. We learn a 300- dimensional embedding for each word. Thus, each sentence is encoded as G ∈R=∗300, where = is the number of words. we treat every word as a categorical feature and put this data into the LSTM model with five level rating classes of the reviews as 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 (IPS)(Wang et al., 2020a). An adversary of network intrusion performs a series of actions to compromise the targeted devices. We collect one day of IPS records via a security service vendor from 242,467 endpoint devices. After removing repeated instances, the
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 as x ∈ '20∗1103∗70 according to the definition given in Section.3. Each of the 1103 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 on 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, IP addresses and hosting machines’ domain names have been removed and anonymized.
Splice-junction Gene Sequences (Splice) (Noordewier 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 2 (Htike & Win, 2013), a precursor mRNA contains exons and introns. During splicing, introns get spliced out while exons get reunited. It is then important to analyze the role of splice junction sequences in mRNA. The Splice dataset contains 3,190 samples 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 as x∈'60∗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 EI), or any other cases (labelled as N). There are 768 IE instances and 767 EI 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.
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 a binary classification scenario of PE malware detection. We collect 10,972 malware samples of 152 families randomly selected from those submitted to VirusTotal between 2018 and 2020. Each of the files https://www.overleaf.com/project/5f81ef055ce9280001ecdee8is classified as malicious by more than 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-maintained packages of Chocolatey, where the package submissions go through a strict review process to exclude malicious and pirated software. Therefore we obtain 9028 benign samples of third-party and Windows system files. Each executable of 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.
Electronic Health Records (EHR) (Ma et al., 2018). The real-world EHR dataset consists of timeordered medical visit records of 7314 patients. Each patient has from 4 to 200 medical visits. Each visit record is composed by a subset of 4130 discrete ICD9 diagnosis codes2. Each diagnosis code represents occurrence of a disease, a 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 x∈'200∗4130∗70 with
2http://www.icd9data.com/
each of the 4130 diagnosis codes projected to a 70-dimensional embedding vector. For the patients with less than 200 visits, we pad the empty observations by setting the corresponding 1 9
8 =0.
We split randomly each dataset into two non-overlapped subsets: 80% of them are used for training and the left 20% form a 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 414 instances of Yelp, IPS, Splice,PEDec 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 a targeted discrete attribute with a new one.

heading: F.2 EXPERIMENTAL SETUP
text: We instantiate the study of robustness characterization and assessment to the popularly deployed Convolution Neural Networks (CNN) and Long Short-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, we thus apply standard LSTM as the classifier in the experiments. Without loss of generality, we use ReLu activation function in both the CNN and LSTM classifier with the dropout module. Theorem.2 applies in both cases. Both models define Lipschitz-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.
In Section 4.1, we demonstrate robustness assessment of the two classifiers over all the datasets with varied tolerance levels against adversarial perturbation. We set the robustness threshold Γ to −0.4 and 0 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 an alarm when the classifier produces an ambiguous decision close to the boundary or report a miss-classification incident. Furthermore, we show the derived robustness assessment scores with respect to an oblivious adversary (OA,the optimistic assessment) and an knowledgeable adversary (KA,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 to 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 PyTorch 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.

heading: F.3 TIME COMPLEXITY AND RUNNING TIME COMPARISON
text: We provide the time complexity analysis in Table.4. We assume a data instance G containing # categorical features and each feature can choose any of the " categorical values. Furthermore, we assume FSGS, OMPGS and GradAttack all run) iterations. Table.4 shows the query complexity of these methods of) iterations.
In the table, ompgs for OMPGS denotes the number of top-ranked candidate features in each iteration. OMPGS then selects one feature from the top ompgs candidate features. The selected feature achieves the best attack performance by combing this feature and any subset of the already modified features. grad 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< 5 . Therefore, OMPGS can reduce the query complexity significantly compared to FSGS. GradAttack does not evaluate the gain of< 5 on the combination of the candidate features and
Table 4: Query complexity of FSGS, OMPGS and GradAttack
Greedy search Query complexity FSGS
∑)
C=0 ((#−C)∗"∗2
C ) OMPGS ∑) C=0 ( ompgs∗2
C ) GradAttack ) ∗∑
:=0 ( : grad ∗": )

heading: Greedy Search Yelp IPS Splice EHR
text: the subsets of the already modified features. The query complexity of GradAttack in each iteration only depends on grad and " .
We also show the running-time evaluation of these methods in Table.5 and Table.6. In both tables, we focus on the pessimistic robustness problem and set the threshold Γ=0 in Eq.4 in the main paper. Table.5 records the averaged running time for computing robustness assessment results over the input data instances where the evasion attack is delivered successfully, i.e. < 5 increases above 0. Table.6 shows the average number of iterations required over the input instances to make< 5 increase over 0.
As seen in the two tables, FSGS stops the loops of greedy search generally earlier than OMPGS and GradAttack, 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 to OMPGS and GradAttack, FSGS has a better chance to achieve higher marginal gain of< 5 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 is thus higher than the other two methods.
On the contrary, GradAttack runs fast but needs significantly more iterations in the search loops. In each iteration, GradAttack only needs to evaluate the combinations of the 6A03 features selected from the candidate set and choose the combination contributing the best increase of< 5 . 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 in each iteration. Therefore, GradAttack 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 a similar number of loops, yet costing much fewer queries and less running time than FSGS. Compared to GradAtttack, OMPGS has a better chance to select the really useful feature modifications, thus costing fewer loops.

heading: F.4 FEATURE SENSITIVITY
text: To further understand the association between the feature sensitivity and the derived robustness assesment scores, we conduct one-factor-at-a-time sensitivity analysis (Campbell et al., 2008) to measure the sensitivity of features. Given a data instance, we change each feature while keeping all the others fixed. The averaged change of the classifier’s output over all the testing instances is used as the feature-wise sensitivity measurement. A larger value indicates that the classifier’s output is more
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 1 and 2. Second, Splice also has a 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 to 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 as 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,GradAttack 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 Table 8. 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 vulnerability of the classifier. On Splice, 4 of the most frequently attacked features (29,28,30 and 31 in Table 8) correspond to the junction of exons, which are also highly informative for gene categorization (Htike & Win, 2013). On IPS, 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 as the most sensitive features according to Table 8.
Suppressing feature sensitivity helps improve adversarial robustness. However, these sensitive attributes are usually informative for classification in an adversary-free scenario. Excluding the sensitive features causes accuracy loss. It indicates the balance between classification utility and adversary-resilience feature engineering in ML practices.

heading: F.5 ROBUSTNESS ASSESSMENT IN BINARY CLASSIFICATION

heading: F.5.1 ROBUSTNESS ASSESSMENT WITH GREEDY SEARCH
text: Table 9 shows 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.

heading: F.5.2 ROBUSTNESS VS FEATURE INFORMATIVENESS
text: We take the G;<8 samples from the 62, 43 original samples for the dataset PEDec, EHR respectively on the half-way of pushing the< 5 of the original samples (OS) to surpass Γ. In Table 10, we verified
the impact of feature informativeness on the robustness assessment scores at Γ = 0 with the binaryclass datasets PEDec and EHR. The table shows that the classifier becomes less robust to adversarial modifications over G;<8 with less predicative information.

heading: F.5.3 ROBUSTNESS ASSESSMENT AFTER ROBUSTNESS ENHANCEMENT
text: From the parameter of the decreased SR in Table 11, we study the robustness enhancement by different 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 11, the robustnessenhancing techniques induce more visible impact on the pessimistic robustness assessment scores using OMPGS. This result meets the intuitive interpretations in the main paper.

heading: G Response to Reviewer FWFM
text: We appreciate the constructive suggestions and valuable comments from all three reviewers. Please find our responses to each reviewer below. We also update accordingly the submitted paper to address your comments.
Reviewer FWFM, Question 1: 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 a 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?
Response: We thank the comment and appreciate the opportunity given to us to clarify the statement. The short answer is: Theorem.1 provides the information-theoretical lower bound ofR03EY with respect to the data distribution `G,H , not a specific training set.
To improve the intelligibility, we re-state Theorem 1 in the submission with an updated Definition 1 of R03EY . Next, we give a detailed explanation about the Theorem 1. We appreciate your patience for reading. We start with the Definition.1 of the expected adversarial risk of a classifier 5 , which is defined on data instances following a distribution.
Definition 4 Let 5 : G→ H denotes a classifier with categorical inputs G. We assume all the data instances (including training and testing data of 5 ) are generated from a joint probability distribution (G,H) ∼`GH . Let `G be the marginal distribution of G. The adversarial risk of 5 under evasion attack is formulated as:
R03EY = E G∼`G sup |diff(G, Ĝ) |≤Y ℓ( 5 (Ĝ)≠ H) (40)
where ℓ is the miss-classification loss function, G and Ĝ are an unperturbed data instance and its adversarially modified opponent respectively. Y denotes the attack budget of evasion attack. We assume G is correctly classified, giving 5 (G)= H.
Note: We follow the IID assumption in the definition. We assume ℓ adopts the form of zero-one loss function. If 5 (Ĝ) ≠ H, ℓ( 5 (Ĝ) ≠ H) = 1. Otherwise, ℓ = 0. With this setting of the loss function, the expected adversarial risk of the classifier 5 can be formulated as in Eq.(41). This gives Eq.1 (the adversarial risk of 5 ) in the original submitted paper.
R03EY = sup G∼`G , |diff(G, Ĝ) |≤Y %[ 5 (G)≠ 5 (Ĝ)] (41)
where % denotes the probability measurement. In this sense, the expected adversarial risk of R03EY can be explained intuitively as the maximum miss-classification probability over an adversarial sample Ĝ, with the underlying data distribution `G,H and the attack budget limited by Y.
Following Definition.1, Theorem.1 provides the information-theoretical lower bound of R03EY with respect to the data distribution `G,H . Indeed, for any given training data set ( sampled from the joint distribution `G,H , ( can be considered as a random variable. Similarly, given a deterministic training paradigm A, the classifier 5 = A(() (trained with ( using the training algorithm A) can be also treated as a random variable in the hypothesis space. For a testing input (G,H) sampled from the same distribution `G,H as (, deriving Theorem.1 follows Fano’s inequality in information theory (Chapter 2 in Mack (2006)):
• For any G∼`G and (G,H) ∼`G,H , following Fano’s inequality, we can produce the lower bound of miss-classification probability over the adversarial sample Ĝ generated from G (based on the information of H and 5 ):
%( 5 (G)≠ 5 (Ĝ) | G∼`G ,|diff(G,Ĝ) | ≤ Y) ≥1− 2 (G;H,()−2[G− ( 5 ;()/2+const
log (42)
This lower bound of the miss-classification probability is composed by three mutual information measurements among the random variables (G,H), ( and 5 .
• By definition, the following inequality holds:
R03EY = sup G∼`G , |diff(G, Ĝ) |≤Y %[ 5 (G)≠ 5 (Ĝ)]
≥%( 5 (G)≠ 5 (Ĝ) | G∼`G ,|diff(G,Ĝ) | ≤ Y)
≥1− 2 (G;H,()−2[G− ( 5 ;()/2+const log
(43)
From this perspective, Theorem.1 establishes a lower bound of the expected adversarial risk of 5 : Given a deterministic training paradigmA, for any training data set ( and any testing input instance (G,H) sampled from the underlying data distribution `G,H , the miss-classification probability of 5 over the adversarial sample generated from G (based on H and 5 ) can be bounded jointly by the three mutual information measurements (G;H,(), [G and ( 5 ;(), as in Eq.2 and 3 of Theorem.1 in the submitted paper.
The mutual information ( 5 ;()measures the dependence of a trained 5 over the training data ( sampled from `G,H . ( 5 ;() can be considered as the lower bound of the VC-dimension of 5 (Xu & Raginsky, 2017; Zhu et al., 2020), which encodes the classifier’s complexity. The other two mutual information measurements (G;H,() and [G relate to the characteristics of the input data (G,H). Intuitively, (G;H,() measures the informativeness of G for classification. A lower (G;H,() denotes weaker consistency between the input data instance (G,H) and the training data set (. The [G 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.
Theorem 1 and the robustness measurement results in Table 2 and Table 3 Since it is not feasible to directly compute the expected risk R03EY , 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 5 over the data distribution `G,H is computed as a sample average,
R̂03E ( 5 )= 1 = =∑ 8=1 max Ĝ8 , |diff( Ĝ8 ,G8) |≤Y ℓ( 5 (Ĝ8),H8). (44)
To facilitate computing, we further adopt a smooth loss ℓ as a surrogate function approximating the zero-one loss. In Eq.(44), max
Ĝ8 , |diff( Ĝ8 ,G8) |≤Y ℓ( 5 (Ĝ8),H8) is to estimate the maximum classification loss
of 5 over the adversarial sample Ĝ8 , which is generated by modifying at most Y categorical features of G8 . By its nature of set function maximization, R̂03E ( 5 ) is calculated in two different settings: the pessimistic and optimistic robustness assessment defined in Eq.4 and Eq.5 in the submitted paper. Especially, when setting the threshold Γ=0 in Eq.4 in the submitted paper, the pessimistic estimate k?4BB (defined by 5H: − 5H ) is proportional to the classification loss, and gives the miss-classification confidence of the target classifier at G with the attack budget limited by Y. This “miss-classification confidence” provides the empirical estimator of the adversarial risk 5 (Eq.44) with a given input G, or called robustness. The results in Table.2 (and Table.10 in appendix) in the submitted paper confirm the statement in Theorem 1: a lower (G;H,() indicates a higher adversarial risk on the input instance (G,H), implying a smaller robustness assessment score. The results in Table.3 (and Table.11 in appendix) also confirm the statement in Theorem 1: reducing ( 5H;(), the dependence of a classifier over the training set (, improves the classifier’s adversarial robustness.
Reviewer FWFM, Question 2: The same question holds for other theorems too. Are the robustness measured on the training set or the data distribution?
Response: As we clarify and explain above, the robustness / the adversarial risk is assessed over the underlying data distribution of both training and testing instances.
Reviewer FWFM, Question 3.1: 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?
Response: There are two approximation problems in evaluating the adversarial risk 5 in our study.
• Approximating the expected adversarial risk with the empirical risk. According to the upper bound established in Tu et al. (2019) (the Rademacher complexity-based bound) the gap
between the expected and the empirical adversarial risk shrinks when the number of instances increases in empirical evaluation. Therefore, with increasingly more data instances sampled from `G,H , we can derive a more accurate estimation of the expected adversarial risk.
• The approximate calculation of the empirical adversarial risk. The exact computation the empirical adversarial risk of 5 at a given input instance G (shown in Eq.(44) defined above) is an NP-hard knapsack problem, as G is a vector of categorical features. Solving it with the well-known Branch-and-Bound (BnB) method has an exponential time complexity in the worst case. Our study proposes to evaluate the empirical risk approximately using a greedy search approach.
Since the first approximation problem is simply solvable by using more samples, our study focuses on addressing the second approximation problem: how accurate our greedy search-based solutions are? We made the pessimistic assessment in the scenario with an omniscient adversary, and the optimistic assessment to consider the threat model with an oblivious adversary (the difference between the pessimistic and optimistic settings can be found in Section 3.2 of the submission.) We clarify the rationality of our estimators on two perspectives:
• Both estimators in Eq.4 and 5 in the submitted paper are knapsack problems. Solving them with BnB can induce prohibitively expensive computational costs. More importantly, BnB doesn’t provide any guarantee to the accuracy of the solution to the underlying optimal solution of Eq.4 and 5.
• The greedy search scheme can provide a solution to the knapsack problem with polynomial time complexity. However, solving both assessment problems with a greedy search for a general 5 may result in solutions that are arbitrarily bad. Our work unveils that the greedy search-based method (FSGS and OMPGS) can derive provably accurate solutions to Eq.4 and 5, if 5 follows the smoothness constraint given in Definition.1. With such a classifier 5 , the pessimistic and optimistic assessment enjoys the merit of weak submodularity. The provable accuracy guarantee of the greedy search-based solutions to the pessimistic and optimistic assessment is established in Theorem.3 and 4 in the submitted paper.
Reviewer FWFM, Question 3.2: What’s the advantage of using these approximations than just using a practical attack to probe?

heading: Response:
text: The merits of using the greedy search based methods can be summarised as following points:
1) Both FSGS and OMPGS can provide provably accurate and computationally efficient robustness assessment (see Theorem 3 and 4 establishing the approximation bound of these greedy search methods). In contrast, the well-known Branch-and-Bound based solution can provide arbitrarily bad solutions as it provides no feasibility guarantees, and it has an exponential complexity in the worst case.
2) These two greedy search based methods are domain-agnostic. They can be used as generally applicable solutions to the robustness assessment problem in a variety of applications. In Kuleshov et al. (2018); Papernot et al. (2016); Miyato et al. (2016); Samanta & Mehta (2017); Gao et al. (2018); Yang et al. (2018); Gong et al. (2018); Ebrahimi et al. (2018); Narodytska & Kasiviswanathan (2017); Croce & Hein (2019), trial-and-error based search is used to conduct !0 attacks. Simple as they are, they need domain-specific heuristics, such as semantic/grammar rules and sensitive image contents, to narrow down the search range. Otherwise, they can produce arbitrarily bad approximation quality, as these methods provide no guarantee on the approximation accuracy of the solution to the knapsack problem.
3) When necessary, both methods are flexible to integrate domain-specific rules to limit the search range to generate solutions consistent with the domain-specific constraints, such as preserving semantic integrity of modified texts.
4) In addition, compared to other variants of greedy search, FSGS and OMPGS can provide more accurate solutions to the robustness assessment problem. To confirm that, we provide additional experimental results involving stochastic greedy search (noted as SGS) (Hassidim & Singer, 2017). Similarly to FSGS and OMPGS, SGS can be also considered as a greedy-search guided attack method with categorical inputs. The difference is SGS randomly selects one of the top-ranked candidate features to modify, unlike FSGS (always choosing the top-ranked one among all candidate features) and OMPGS (choosing the top-ranked feature from a constrained set of candidates). According to
(Hassidim & Singer, 2017; Wang et al., 2020b), SGS has a lower theoretical approximation accuracy solving weakly submodular knapsack problems, compared to FSGS and OMPFS. In our additional empirical evaluation presented in Table.4, we confirm the superior performance of FSGS and OMPFS over SGS .
Table.12 measures the success rate (SR) and the average number of changed features (Avg) of SGS over Yelp, IPS, Splice and EHR datasets. With similar values of SR, a significantly lower/higher Avg value indicates weaker/stronger robustness of the classifier against attack. Otherwise, a lower / higher SR indicates weaker / stronger robustness of the classifier. Table.12 compares SGS to the proposed FSGS and OMPGS methods, as well as GradAttack originally proposed in (Qi et al., 2019) in the pessimistic assessment scenario with threshold Γ=0. The superior performance of FSGS and OMPFS over SGS and GradAttack are discussed as follows.
• SGS has a lower SR and higher Avg value compared to both FSGS and OMPGS on Yelp, IPS and EHR. Especially on EHR, SGS’s SR/Avg is significantly lower/higher than all the other methods. On Splice, though SGS’s SR (0.86) is higher than OMPGS (0.74), the Avg value of SGS (3.10) is obviously higher than that of OMPGS (2.30) and FSGS (1.70). In general, compared to FSGS and OMPGS, SGS produces a loose evaluation of robustness assessment. This confirms the fact that a higher theoretical approximation accuracy guarantees more accurate empirical robustness assessment.
• GradAttack lacks the theoretical guarantee of approximation accuracy, but it works well empirically on Yelp as reported in (Qi et al., 2019). Compared to GradAttack, SGS can provide better attacks solutions / tighter robustness evaluations on Yelp, IPS and Splice. But its performance becomes much worse than GradAttack on EHR. From this angle, we can find a lower theoretical approximation accuracy indicates more unpredictable variations of the empirical performances. It causes practically more loose robustness assessment as a result.
• Compared to GradAttack, both FSGS and OMPGS can get better attack results, thus more accurate robustness assessment. It illustrates the necessity of establishing the theoretical approximation accuracy. A higher or lower theoretical approximation accuracy is an indicator of tighter or more loose robustness assessment in practice. With categorical inputs, the theoretical bound of approximation accuracy can help practitioners evaluate tightness of the robustness assessment results and choose proper methods to compute the assessment.
Reviewer FWFM, Question 4: 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 determine 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.
Response: In Theorem.1, we discuss the impact over a target classifier without any defensive mechanism deployed, i.e. a unprotected target classifier. The perturbed Ĝ is an evasion attack instance sent to the unprotected target classifier 5 . We don’t expect a “robust” 5 since it is not protected. In Theorem.1, we analyze the “robustness level” of this unprotected classifier. We show that the “robustness level” of 5 depends on not only the property of the classifier, e.g. the model complexity or smoothness but also the characteristics of data instances involved in the learning task, e.g. feature informativeness and sensitivity. The unveiled association between feature sensitivity and the adversarial robustness in Theorem.1 helps design better defensive mechanisms.
After presenting Theorem.1 in section 3.1, we discuss how three popularly used robustness enhancement strategies resonate with our findings in Theorem.1. To verify the resonance, we evaluated the model robustness level by adopting defensive mechanisms to the unprotected classifier, such as adversarial training, nuclear-norm regularization, and random smoothing. We compare the robustness level of an
unprotected classifier to those of a classifier enhanced with the defensive mechanisms. The results in Table.3 in the submitted paper confirm empirically the impact of ( 5 ;() on the adversarial robustness of the classifier, as unveiled in Theorem 1.
Although we are not standing at a defensive position (we evaluate the model robustness level for verifying the factors in Theorem1), it is interesting to discuss the change of semantics of the perturbed instance. Practical attack techniques, e.g., the greedy search-based methods, do not necessarily perturb the highly sensitive features, especially when sanitary checks are deployed by administrators / data owners of data analytic systems. The adversaries can embed domain-specific eligibility constraints, like grammar / semantic rules, to avoid modifying features harming the semantic integrity and encourage adversarial samples consistent with the constraints. Notably, the greedy search-based methods, FSGS and OMPGS can use the constraint by setting up a list of uneditable features before searching feasible adversarial perturbations. In machine learning practices, any feature of a properly defined feature representation can always present a certain level of sensitivity associated with ground truth labels, unless it is completely irrelevant. According to Theorem.1, attack methods can modify the relevant but not extremely sensitive features to deliver attacks without changing the semantic integrity of data. In this setting, the adversary may need more attack budgets, i.e. changing more features that are less sensitive to ground truth labels. The adversary can thus preserve the semantics, and the conducted attack becomes more stealthy.
Reviewer FWFM, Question 5: How to compute<Ω and "Ω?
Response: For practical estimation, "ΩZ can be computed as local Lipshitz constant of 5 if n > 0 in Definition.2 of the submitted paper (or the local Lipschitz constant of − 5 (G) if n < 0). We can follow Jordan & Dimakis (2021); Scaman & Virmaux (2018) to estimate the local Lipschitz constant practically. Furthermore,<ΩZ can be calculated as the local strong convexity constant of 5 (G) if n >0 in Definition.2 of the submitted paper (or of the local strong convexity constant of− 5 (G) if n <0)Elenberg et al. (2018). We can compute<ΩZ following Bach (2014).
Thank you for your comments and your time on re-evaluating of our work. It would be very kind of you to raise the current score if you find our answers to the questions are reasonable.

Review summaries:
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.  ============================================= I 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.

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.

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.