Interpreting Unsupervised Anomaly Detection in Security via Rule Extraction
Authors: Ruoyu Li
Qing Li
Yu Zhang
Dan Zhao
Yong Jiang
Yong Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: unsupervised anomaly detection
global explanation
rule extraction

Abstract: Many security applications require unsupervised anomaly detection, as malicious data are extremely rare and often only unlabeled normal data are available for training (i.e., zero-positive). However, security operators are concerned about the high stakes of trusting black-box models due to their lack of interpretability. In this paper, we propose a post-hoc method to globally explain a black-box unsupervised anomaly detection model via rule extraction.
First, we propose the concept of distribution decomposition rules that decompose the complex distribution of normal data into multiple compositional distributions. To find such rules, we design an unsupervised Interior Clustering Tree that incorporates the model prediction into the splitting criteria. Then, we propose the Compositional Boundary Exploration (CBE) algorithm to obtain the boundary inference rules that estimate the decision boundary of the original model on each compositional distribution. By merging these two types of rules into a rule set, we can present the inferential process of the unsupervised black-box model in a human-understandable way, and build a surrogate rule-based model for online deployment at the same time. 
We conduct comprehensive experiments on the explanation of four distinct unsupervised anomaly detection models on various real-world datasets. The evaluation shows that our method outperforms existing methods in terms of diverse metrics including fidelity, correctness and robustness.

Interpreting Unsupervised Anomaly Detection in Security via Rule Extraction
Ruoyu Li Qing Li Yu Zhang", Dan Zhao', Yong Jiang", Yong Yang Tsinghua University, China; 'Peng Cheng Laboratory, China
Tsinghua Shenzhen International Graduate School, China
Teencent Security Platform Department, China (liry19, , yu auu-zhang233)mm @mails, tsinghua. edu. cn; {liq, zhaod01 p@pc1. eeppcl.cc... ac. en jiangyesz. trinzzusinngu....a edu. cn; coolcyang@tencent. com
Abstract
Many security applications require unsupervised anomaly detection, as malicious data are extremely rare and often only unlabeled normal data are available for training (i.e., pero-positive). However, security operators are concerned about the high stakes of trusting black-box models due to their lack of interpretability. In this paper, we propose post-hoe method to globally explain a black-box unsupervised anomaly detection model via rule extraction. First, we propose the concept of dis- tribution decomposition rules that decompose the complex distribution of normal data into multiple compositional distributions. To find such rules, design an unsupervised Interior Clustering Tree that incorporates the model prediction into the splitting criteria. Then, propose the Compositional Boundary Exploration (CBE) algorithm to obtain the boundary inference rules that estimate the decision boundary of the original model each compositional distribution. By merging these two types of rules into a rule set, we can present the inferential process of the unsupervised black-box model in human- uummann-udderttadabblle way, and build a surrogate rule-based model for online deployment at the same time. We con- duct comprehensive experiments the explanation of four distinct unsupervised anomaly detection models on various real-world datasets. The evaluation shows that our method outperforms existing methods in terms of diverse metrics including fidelity, correctness and robustness.
Introduction
In recent years, machine learning (ML) and deep learning (DL) have revolutionized many security applications such as network intrusion detection [1+3] and malware identification [ that outper- form traditional methods in terms of accuracy and generalization. Among these works, unsupervised anomaly detection becomes more promising, which detects malicious activities by the deviation from normality. Compared to supervised methods, this type of method is more desirable in security domains as 1) it hardly requires labeled attack/malicions data during the training (i.e., pero-positive learning), which are typically much more sparse and difficult to obtain in contrast with benign data; 2) it does not fit any known threats, enabling better detection on unforeseen anomalies.
Due to the black-box nature of these models, ML/DL models usually not directly interpretable and understandable. Many local explanation methods [6-10] have attempted to interpret the models by presenting feature importance of the decision for single point. However, globally explaining black-box models, especially using rule extraction to characterize the whole decision boundaries, is particularly desirable in security systems since it can provide the following benefits:
"Corresponiing author: Qing Li.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Trust over High Stakes. To minimize the chance of errors and potential losses, security operators tend to trust uannaa-dddestaadaabl rules rather than unintuitive outputs such as labels and numeric values from complex and incomprehensible black-box models.
Online Defense. Interpreting black-box models into rules with high fidelity enables easy integration with the majority of defense tools that use rule-based expressions (e.g., iptables [T]. Snort [22). thus allowing for deployment of online defense with extraordinary efficiency (e.g., Tbps throughput (13).
Existing global ML/DL explanation approaches are mostly proposed for supervised models, Little research has been done explaining unsupervised anomaly detection, which faces several challenges:
Unlabeled One-class Data (CHI). Supervised explanation methods [1 need labeled data of both positive and negative classes to determine the decision boundaries of black-box models, This requirement goes against unsupervised anomaly detection's advantage of not requiring attack data.
Lack of Surrogate Models (CH2). Global methods typically use an inherently explainable model to mimic the black-box model, such as decision trees [15] [6] and linear models [17], which are all supervised models. However, there lacks a proper surrogate model that is unsupervised and can satisfy the properties of being self-explained and well-performed for high-stake security applications.
Accuracy Loss (CH3). A common problem with global methods is that the surrogate model suffers from the loss of accuracy since it simplifies the original model [18]. In this case, though these methods can provide model explanation, they cannot meet the need of online deployment which requires high detection accuracy in security applications.
We observe that an important reason why simple surrogate models are ineffective is that they cannot learn well about the complex data distribution in high-dimensional space. Specifically, even one-class data may be multimodal, i.c., the overall distribution consists of multiple compositional distributions. For example, the normal activities of host may consist of many services (e.g.. web, database) and are for various purposes, and they could present considerable differences in feature space.
In light of this, this paper proposes an accurate and efficient divide aiele-and-come and-conquer method to globally interpret unsupervised anomaly detection. First, we propose the concept of distribution decomposition rules that cut the feature space into multiple subspaces, each of which encloses a compositional distribution. To obtain such rules, we design a new tree model called Interior Clustering Tree that extends the CART decision tree in terms of splitting criteria and can fully work in an unsupervised manner. Second, we propose the Compositional Boundary Exploration algorithm to obtain the bound- ary inference rules that estimate the decision boundary of the original model on each compositional distribution. To accurately and efficiently find such rules, this algorithm starts from hypercube-shapedd rules and uses approximation for gradient ascent of model prediction to find the optimal direction of iterations. By merging the distribution decomposition rules and the boundary inference rules into a rule set, we can present the inferential process of the black-box model in a human- unnaanntnnnttteaballlle way, and build a surrogate rule-based model for online defense at the same time.
During the experiment, we use four different unsupervised anomaly detection models well trained on three benchmark datasets, and evaluate our method with five distinct explanation methods as baselines. The experiment shows that our method can extract interpretable and accurate rules from black-box models. The extracted rules outperform prior work in terms of diverse metrics including fidelity, robustness, true positive rate and true negative rate, meeting the demand of improving human trust in black-box models and maintaining high detection accuracy for online deployment. Our code is available at httpt::///ttiiiioo
com/Ruoyu Li/UAD- Rule- Extraction
2 Related Work
To combat persistent emergence of new attacks in cyberspace, recent security applications 3 19
21
make heavy use of unsupervised models to detect unknown anomalies, such as one-class classifiers
Isolation Forests 25 26), autoencoders and variational autoencoders [27]. Despite many unsupervised model-based approaches have achieved good detection rates, security operators are still concerned about the semantic gap between black-box model prediction and human understanding, considering the risks of the great cost incurred by bad decisions [I0]. To resolve such concerns, explainable AI (XAI) has been applied to anomaly detection [0 For example, Kauffmann et al.
22
propose a decomposition method to explain anomalies of one-class SVMs (28). Philipp et al. present

---

an explainable deep one-class classification method called Fully Convolutional Data Description 30]. However, these methods are specific to a limited range of models and not versatile enough to accommodate the vastly heterogeneous models of unsupervised anomaly detection.
Some prior work also incorporates popular model-agnostic explanation methods, such LIME [6] SHAP [7] and their variations g and applies them to explain unsupervised models 331-33 and security applications [ 34
35 [0] These methods typically use sparse linear models to interpret
predictions by estimating feature importance. Guo et al. propose a method named LEMNA that uses a fused lasso to explain malware classification [9]. Sipple uses Integrated Gradients 36 to attribute anomalies of IoT device failure [34]. Nonetheless, these methods can only interpret one data point at a time (i.e., local explanation) but not reveal the complete decision catiiiiinmmainggggg process of model.
To fully understand how black-hox models work and safely deploy them, the most appropriate method is model- model-agnostic global post-hoc explanation. It aims to match the predictions of any well-trained models with an inherently interpretable explainer, such as decision trees [.5 16). symbolic rules [14], sparse linear models [17] and decision lists [37]. In [15], the authors construct global explanations of complex black-box models in the form of a decision tree approximating the original model. Jacobs al. propose framework that takes an existing ML model and training dataset and generates tree models to interpret security-related decisions [16]. However, most of these methods are only suitable for interpreting supervised models that have labeled data of all classes, which are often unavailable. Though work like [38] can extract rules from unsupervised anomaly detection models, it still assumes that enough outliers exist in the training dataset judged by the black-box model so as to determine its decision boundary. This assumption may not hold in practice if model has great generalization and can achieve a low false positive rate on normal data (e.g.. I
Some recent studies aggregate several local explanation models into near-global explanation 419 However, this type of method is inherently computationally challenging when data volumes are large and has to make trade-off' between fidelity and coverage. While techniques like knowledge distillation can also realize model transformation reduce complexity and promote interpretability
42 43), the fundamental purpose of these efforts is to compress models while ensuring accuracy rather than explaining the original models with high fidelity.
3 Overview
3.1 Problem Definition
Let X C Rd be the variable space of d-dimensional features; and x;; denote data sample and the i-th dimension of the data sample. We give the following definitions for the rest of the paper:
Definition 1 (Unsupervised Anomaly Detection). Given unlabeled negative data (i.e., normal data) X sampled from a stationary distribution D for training, an unsupervised model estimates the probability density function f(x) se Px=D((x), and detects an anomaly via low probability fx) < p. where & >> O is a threshold determined by the model itself or by humans.
It is noted that the threshold yo is non-zero value, meaning that the model inevitably generates false positives, which a common setting in most of the works [ even though the false positive rate can be very low. Besides, the normal data may occasionally be contaminated or handled with errors. We consider the anomaly detection tolerant of noisy data, but their proportion in training dataset is small and we do not have any ground truth labels of the training data.
Definition (Global Explanation by Rule Extraction). Given a trained model f with its anomaly threshold >p and the training set X, we obtain an in in-distribution rule set C = =C,, C2.... that explains how the model f profiles the distribution of normal data. A rule C= =.... (x4 @ vx) A... A (2z @ vz) is conjunction of several axis axis-aligned constraints on a subset of the feature space, where ix is the bound for the i-th dimension and O E {s.>}.
Let æ E C' indicate that a data sample satisfies rule. From C, we can build a surrogate model he (z). whose inference is to regard data sample that cannot match any of the extracted rules as anomalous:
hc (a)) = -a E C1) A (a E C2) A... C, C.
Our Goal. We expect the extracted rules to have a high fidelity to the original model, that is, a similar coverage of normal data (i.c., true negative rate), and a similar detection rate of anomalies (i.c., true
3

---

po a
(a) The unlabeled data
(b) Compositional distribu- (c) Process of the CBE al- tions
(d) The final rule set
gorithm
Figure I: A high-level illustration of our method. The small circles are unlabeled normal data. The dashed curves are the decision boundary of the black-box model. The vertical/horizontal lines in (b) and (c) are the distribution decomposition rules.
positive rate). To this end, we formulate our objective follow:
arg arg min (x, (x=D(C,f.9))
(2)
3.2 Methodology Overview
To minimize the first item in Equation 2 suppose the training data X can well represent the distribution D, straightforward approach is find the bound of X rules, such as using hypercube to enclose the data samples which can easily achieve the minimization the partial loss CC, p) = O. However, as D is not prior distribution and do not have labeled abnormal samples, the second item (x= f, sp) is neither deterministic nor estimable unless we create sufficient random samples and query f. which is challenging given the high-dimensional space of X.
As prior studies 21 34 suggest, normal data are typically multimodal, i.e., the overall distribution is formed by multiple compositional distributions. For example, server supports multiple services such as web, email and database. The representations of these services can disparate and located in different regions in feature space with little transition between the regions, making it infeasible find a uniform rule set to accurately estimate the original model. An example is illustrated in Figure Ta
Based on this intuition, we propose divide-and-comee conquer approach. First, we propose an Interior Clustering Tree model (Section to find the distribution decomposition rules, which cut the feature space into subspaces so that each subspace contains data belonging to the same compositional distribution, as shown in Figure [b] Then, we design a Compositional Boundary Exploration algorithm (Section 5) to explore the decision boundary on each compositional distribution, as depicted Figure Ic Particularly, the algorithm starts from the minimal hypercube that encloses all data of the distribution, and finds the boundary by recursively extending the boundary following the optimal direction guided by gradient approximation. Upon obtaining the decision boundary of distribution, the corresponding boundary inference rule can be extracted. Last, the rule set that globally approximates the original model can be obtained by merging the distribution decomposition rule and the boundary inference rule of each compositional distribution, illustrated in Figure Id] We formally define the distribution decomposition rule and the boundary inference rule as follows.
Definition 3 (Distribution Decomposition Rule). Denoted by C that decomposes the overall
distribution of normal data D into K compositional distributions, i.e., Px~D(x) E du Px~D, (x) x Ct) where ou denotes the weight of each compositional distribution, so that a data sample x ~ Dj. has significantly small probability of belonging to other distributions.
Definition 4 (Boundary Inference Rule). Denoted by C that estimates the decision boundary of the original model for each distribution D,,, i.e., arg min LX-D. (CE, f. + Lx (CE f..))
CE
With the definition of these two types rules, we translate the objective in Equation 2 to the following objective our intuition indicates. We give proof of this proposition in the appendix.

---

Proposition 1. The original objective can be estimated by finding the union of the conjunction of distribution decomposition rules and boundary inference rules for each compositional distribution:
K
U 1=
arg (Ck.D, LXwD, (Ck, (), where C = C ^ C
(3)
4 Interior Clustering Tree
To obtain distribution decomposition rules, we first need to decide how to define compositional distribution p.. We notice that, though we do not have labeled data, we can use the output of the original model that estimates the overall distribution D criterion for decomposition.
Proposition 2. If two data samples (8) and x! belong to the same distribution Dx. the difference of their probabilities belonging to D will be less than e, where e a small constant.
Proof. Recall the definition of distribution decomposition rules and compositional distributions. Since the two data samples belong to the same distribution DR. the probability of belonging to other distributions Px-DD (2) is near to zero for I o k. Hence, the probability Px-D (2:), which is the weighted sum of the probability of belonging to all the compositional distributions, is approximately equal to P Px-D, (x) for both the data samples.
Based on this, we propose tree-based model dubbed Interior Clustering Tree (IC-Tree), which extends the CART decision tree (4.. The main difference between IC-Tree and CART is that, rather than splitting data based ground truth labels, IC-Tree uses the probability output by the original model as splitting criteria, enabling it to work in a completely unsupervised manner.
Node Splitting. Given the data N at a tree node, we first obtain the output of the anomaly detection model (x) for æ N. Similar to decision trees, the node of an IC-Tree finds a splitting point (i, b;) that maximizes the gain:
IN N
N T(N+), [N
arg max T(N)
T(N:)
(4)
where b; is the splitting value for the i-th dimension, N; and N, are the data split to the left and right child nodes, [N] denotes the number of data samples, and / a criterion function such as Gini index = 2p(1 p) for binary classification with the probability of Specifically, we let p be the average output of the anomaly detection model, which can be interpreted as the expectation of the probability that the data belong to the same distribution:
p = ExEN P (XXDD(x)] = NN
Σ{(x) #EN
(5)
An IC-Tree continues to split nodes until it satisfies one of the following conditions: i) the number of data samples at the node NN = 1; ii) for any two of the data samples at the node (z( x(()) E N, ()(x(() - (x)) < e; iii) reaches a maximum depth т, which is hyperparameter.
Distribution Decomposition Rule Extraction. A trained IC-Tree that has K leaf nodes (K < 27) represents K distributions separated from the overall distribution D. Suppose the k-tth leaf node has depth r'. A distribution decomposition rule that describes the k-th compositional distribution can be extracted by the conjunction of the splitting constraints from the root to the leaf node:
C = (I, 01 by|s1 = (i,b:) A A (I, Oy by|s,, = (j. by)),
(6)
where 2 is "<" the decision path goes left or ">" if the decision path goes right.
5 Compositional Boundary Exploration
To accurately find the decision boundary of a detection model within each compositional distribution, we propose the Compositional Boundary Exploration (CBE) algorithm (described in Algorithm [] The CBE algorithm uses the minimal hypereube that encloses the normal data of each compositional distribution starting point. Further, we refer to adversarial attacks [45] and propose a method to
5

---

approximate the optimal direction to explore the decision boundary, which makes the algorithm more efficient and accurate to estimate the decision boundary.
Starting from Hypercube (line 1). Let Xx denote the training data falling into the k-th leaf node of an IC-Tree that represents compositional distribution. Recall the definition of boundary inference rules that target min Lx-D, (C f. + Lx=D, (C& f. We use the minimal hypercube Ha as a starting point of boundary inference rules bound every dimension of the data samples in = O. The
X judged by the original model as normal, which obviously achieves X x f.
minimal hypercube is enclosed by 2 x d axis- aligned hyperplanes, which can be characterized by the following rule:
H = (uī S 21 S STT) A... S x Sat)
(7)
where u/- = min(z,)f(x)) > p, x E Xx) and 8.- = max(x;1f(x)) > p. Ex).
Explorer Sampling (line 4-6). The CBE algorithm explores the decision boundary of the original model by estimating the bound of one feature dimension at a time. For i-th dimension, we uniformly sample N₂ data points on each hyperplane of the hypercube, i.e., e ,..., ((N.) e(,),...,e((.))
H2 (x,
vi), vi E {vz , v }. which are called the initial explorers for this hyperplane. For an initial explorer e, we further sample N₂ auxiliary explorers near it from a truncated multivariant Gaussian distribution denoted by (ee, i) Particularly, the center of sampling is the explorer and the radius of sampling is constrained by the covariance matrix Σ diag(ple] a hyperparameter, and the sampling on i-th dimension is half- truncatedd to only keep the distribution outside the hypercube as we desire extend the boundary. With N₂ x N, auxiliary explorers in total, we query the original model and use Beam Search to select N₂ samples with the minimal probability of being normal as the candidate explorers for the next iteration.
Ii ..... p 1 Uu I), where p is
Gradient Approximation (line 7-9).. Though we have obtained N₂ candidate explorers in the previous step, using them directly for the next iteration does not guarantee the optimal direction of movement towards the decision boundary. To find the optimal direction,, we utilize the Fast Gradient Sign Method 445 that employs gradient ascent to find the direction of feature perturbation. However, we do not know the loss function of the original model in black-box scenarios. To deal with it, given selected auxiliary explorer è that is sampled around an initial explorer e the i-th dimension hyperplane, we approximate the i-th dimension of the model gradient (i.e., the partial derivative) by the slope of a linear model across the two data points, and the midpoint with its i-th dimension minus the approximation as the new explorer for the next iteration:
Ci,nezt e + é
17 sign (V,) 1),, where V. af(x) 0x,
S(e) (())
(8)
2
C é
sign(-) is the sign function, and 7) is hyperparameter to control the stride of one iteration. The iteration stops when i) an auxiliary explorer ēest that satisfies f(@rant) < yp is found, or ii) it reaches the maximum number of iterations.
Rule Acquisition (line 12). If the iteration stops due to the first condition, we produce a boundary constraint for each dimension using the coordinate of ēeer that extends the boundary of the hypercube. i.c., G = (I; O ē. where @ is "<" if êezt, is greater than v." or ">" if éewt, is less than v,- If the iteration stops due to the second condition, it means the algorithm encounters difficulties in moving towards the decision boundary by perturbing this feature dimension. We calculate the difference between the model prediction of the last auxiliary explorer and that of the initial explorers on the hyperplane. If the difference is smaller than a threshold ò, we decide that this feature dimension a contour line, i.e., has no significant correlation with the model prediction. In this case, we do not produce any constraints for this dimension. If the difference is greater than the threshold, we produce constraints the same way as those produced under the first condition. The final boundary inference rule is the disjunction of the hypercube and the constraints on each dimension.
6 Evaluation
6.1 Experimental Setup
Black-box Models and Datasets. We use four different types of unsupervised anomaly detection models widely used in security applications as the original black-box models, including autoencoder (AE, used by (., variational autoencoder (VAE, used by (46)). one-class SVM (OCSVM, used by

---

Algorithm 1: Compositional Boundary Exploration
Input: Data falling into the k-th leaf node X k, anomaly detector and its threshold yp Output: Boundary inference rule Cj on this leaf node such that C2 encapsulates normality
Hy t Minimallxypercube(XA..
2 for i-th dimension in X do
e(1), e(.)....,e! e(Ne) f- IntialExplorer(Ht)) on i-th dimension;
while True do
e(1) ,.., ((..),((.)) <- AuxiliaryExploreree for each initial explorer e:
Beam Search for N₂ candidate explorers from Ne x N, auxiliary explorers that have the minimal probability of being normal judged by f and yo;
pprodientAppro((e) for each candidate explorer selected from auxiliary explorers; ending condition satisfied then
- (x, + ε,) and break;
10
end while
11 end for
12 return CF = HA V A02.
47) and Isolation Forest (iForest, used by 48 We employ three benchmark datasets for network intrusion detection in the experiment, including CIC-IDS2017, CSE-CIC-IDS2018 [49] and TON-IoT [5). The representation of these datasets is tabular data, where each row is network flow record and each column is a statistical attribute, such as the mean of packet sizes and the inter-arrival time. The datasets are randomly split by the ratio of 6:2:2 for training, validation and testing. We use only normal data to train the anomaly detection models and calibrate their hyperparameters. The description of the datasets and the AUC score of the models the datasets are shown in Table
Baselines. We employ five prior explanation methods as baselines: 1) We use [38] that extracts rules from unsupervised anomaly detection (UAD); 2) For other global methods, we use the estimated greedy decision tree (EGDT) proposed by [1S], and Trustee [16] that specifically explains security applications; 3) We also consider one method LIME 66 that can use Submodular Pick algorithm to aggregate local explanations into global explanations, and a knowledge distillation (KD) method [43] that globally converts black-box model to self-explained decision tree. These methods, like ours, can only access normal data to extract explanations. More details about baselines are in the appendix.
Metrics. We refer to the metrics in 18 to evaluate the rule extraction. Due to limited space, we demonstrate the following four metrics in this section and present other results the appendix: 1) Fidelity (FD), i.e., the ratio of input samples on which the predictions of original models and surrogate models agree over the total samples, which indicates the extent to which humans can trust the explanations; 2) Robustness (RB), i.e, the persistence of the surrogate model to withstand small perturbations of the ínput that do not change the prediction of the original model; 3) True positive rate (TPR) and true negative rate (TNR), suggesting whether the detection capability meets the need of online defense and whether the extracted rules generate noticeable false alarms that cause "alert fatigue" [5I] in highly unbalanced scenarios of most security applications, respectively.
6.2 Quality of Rule Extraction
We extract rules from the four unsupervised anomaly detection models using the five baseline methods and our method, and test the performance of the extracted rules. The results on the three datasets are Table 2 We find that our method achieves the highest fidelity on all the detection models and datasets, and half of the scores are even over 0.99. It shows our method can precisely match the predictions of the black box models, which ensures the correctness of its global interpretation.
Table 1: Summary of datasets for network intrusion detection and AUC of trained models.
No.
Datasct
#Classes
#Features
#Normal
#Attack
AE
VAE
OCSVM
iPorest
CIC-IDS2017
6 attacks normal
80
687.565
288.404
0.9921
0.9901
0.9967
0.9879 0.9734
2
USE-CIC-IDS2018
14 attacks 1 nermal
80
693.004
202.556
0.9906
0.9767
0.9901
TON-1ol
9 attacks normal
30
309,086
893,006
0.9998
0.9998
0,9993
0.9877
7

---

Table 2: Performance of rule extraction on different datasets.
CIC- IDS2017 dataset
AE
VAE
OCSVM
iForest
Method
RB
TPR
TNR
FD
RB
TNR
FD
RB
TPR
TNR
FD
RB
TPR
TNR
UAD
0.1325
0.4991
0.0003
0.9792
0.1438
0.48.9
0.022
0.9988
0.0725
0.5000
0.00
1.00
0.1262
0.5000
0.0
1,00
BGDT
0.533
1.00
0,4354
0.9947
0.1437
1,00
0.022
0.996
0.9189
0,9994
0.9306
0.838
0.9729
0.9996
0,9417
0.9189
Trustee
0.4871
0,6412 0,3844
0.9981
0.1552
0,9857
0.0152 0.9988
0.539
0.6108
1.00
1.00
0.4543
0.5801 0,9795
0.4486
LIME
0.6918
0.9999
0.7889
0.0014
0.8232
1.00
0.9329
0.001
0
0.9999
0.0777
0.0241
0.8910
0.9998
0.8246
0,9913
KD
0,5776
0.9989
0.4792
0.9998
0,2010
0,9817
0.1016
0.9993
0,3620
1.00
0.3102
0.9995
0.1262
0.7016
0,00
1.00
1.00
0.9915
0.9620
0.9993
0.9964
1.00
1.00
0.9949
0.9843
CIC IDS2018 dataset
AE
VAE
OCSVM
iForest
Method
FD
RB
TPR
TNR
FD
RB
TPR
TNR
FD
RB
TPR
TNR
FD
RB
TPR
TNR
UAD
0.3796
0.3077
0.0004 0.7418
0,2697
0.2930
0.1490
0.4857
0.6051
0.3069
0.3004
0.9876
0.6811
0.4035
0.3539
0,9724
BGDT
0,5821
1.00
0.1432
0.9801
0,2197
0.9989
0.2308
0.9554
0,5106
1.00
1.00
0.9546
0.9546
0.7813
0.9888
0.8971
Trustee
0,5157
0,9006 0.1901 0.9857
0.3642
0,9752
0.0124 0.9636
0.3616
0.5955
1.00
0.4241
0.4700
0,9641
0.5162
LIME
0.5838
0.9997
0.7681 0.0255
0,6814
1.00
0.9402
0.0213
0.0560
1.00
0,9999
0,0186
0.8903
1.00
0,9884
0.8745
KD
0.5074
0,9999
0.3562
0.9979
0:4234
0,9989
0.1086
0.9925
0.3180
0.9967
0.4308
0.1510
0.3596
0.6834
0,0000
1.00
Ours
0.9954
0.9997
0.9998
0.9774
0.8962
0,9985
0.9997
0.8268
0.9929
0.9997
0.9983
0.9753
0.9947
0.9291
0.9988
0.9583
TON ToT dataset
AE
VAE
OCSVM
iForest
Method
FD
RB
TPR
TNR
FD
RB
TPR
TNR
FD
RB
TPR
TNR
FD
RB
TPR
TNR
UAD
0.1499
0.015
0.0258
0.908
0.2157
0.4010
0.1863
0.7787
0.0489
0.5000
0.00
1,00
0.0674
0.5000
0.00
1,00
BGDT
0.9750
1.00
0.9739
0.9943
0.7660
1.00
0.7538
0.9948
0.8139
0.9997
0.8051
0.9759
0.6345
0.9226
0,6247
0.9475
Trustee
0.4774
U,5722
0,4502
0.9971
0,3807
0.6689
0.3484
0.9975
0.7942
0,8430
1.00
1.00
0.7476
0.8145
0,9824
0.1943
LIME
0.6971
0.9999
0.7939
0.0027
0.8289
1.00
0.9379
0.0015
0.0687
0.9999
0.0787
0.0231
0.8963
0.9998
0.8296
0,9918
KD
0,0821
1.00
0.0341
0.9987
0.0591
0.9997
0.0099
0.9980
0.0494
1.00
0.0005
0.9994
0.0674
0.9955
0.00
1.00
1.00
0.9845
1.00
0.9831
0.9511
1.00
0.9881
0.9890
0.9715
Table 3: Fidelity of extracted rules under varying percentages of noisy training data.
Percentage
Random Nuise VAE
OCSVM
iForest
AE
Mislabeled Noise
VAE
VCSVM
iForest
0%
0.9829
0.9814
0.9729
0.9876
0.9997
0.9977
0.9975
0.9984
0.9824
0.9148
0.9940
0.9991
0.9992
0.9951
0.9876
0.9873
0.8960
0.9920
0.9991
0,9992
0.9952
0.9953
51
0.9855
0.9675
0.9511
0.7732
0.9914
0,9996
0.9992
0.9966
10%
0.9739
0.9881
0.9600
0.5148
0.9987
0.9983
0.9996
0.9978
Moreover, our method achieves the highest TPR on all the detection models and datasets; specifically, the TPR is equal to 1.00 for all the detection models on TON-IoT dataset. This result suggests that our rules can accurately detect various anomalous data, making possible to realize online deployment and defense using these rules. Our method also reaches high level of robustness (minimum 0.9890, maximum 1.00) and true negative rate (minimum 0.97 maximum 1.00). Therefore, it is concluded that method can obtain rules of high quality from different black-box unsupervised anomaly detection models using only unlabeled one-class data.
Considering that obtaining a "clean" training set requires huge manual effort in reality 52 we also assess the efficacy of our method under varying percentages of "noisy" data. We evaluate the fidelity of extracted rules using two approaches for the injection of noisy data: 1) random noise; 2) mislabeled data from other classes, i.e., attack data, The results are shown in Table We find that the impact of the noisy data proportion is not significant: 36 of 40 fidelity scores in the table preserve over 0.95, and the variation of fidelity scores is not obvious with the increase of noisy data for most of the models. This shows that our rule extraction method can retain similar performance to the black-box model that it extracts from. Nonetheless, the results of iForest also reveal that sufficiently large proportion of noisy data may cause a certain negative impact on the rule extraction for certain models.
6.3 Understanding Model Decisions
To demonstrate that the rules obtained by our method are in line with human understanding, we use the OCSVM as an example of black-box models to exhibit several explanations. We extract rules from the well-train model and use the rules to predict three typical types of attack data, including Distributed Cenial-of-Service (DDoS) attacks, scanning attacks, SQL injection, and backdoor attacks.
8

---

Table 4: Examples of explanation on four types of attacks.
Attack
Roles Normality
Atbak Value
Festure Menning
Homan Undensaading
po R_leea >- 101.68
57,33
Maan packet sizes
DDBS attacks use packets small sixes to achieve asymueetra resource cousumption on the victum side, and seud pickets a high mote to flord the vietim.
DDD8
lot mean > 01063
0,00003
Mcan of picket inter-rrival time
dur 12.61
0,00126
Duration of connection
Seanning
Pf_yar 2555.20
count > 120
0,0
IP packet count per connection
Variance packet
Scanning attacks send a constant probe packet to por. and the victim not reply the port closed.
SQL Injection
PS_ W__bod_mmann Lmnenn S. 415.58
435,80
Mean backward packet sizes
Unauthorized
additional data from websites, mssllly establish short connections une attack.
>
0.37
Duration connection
Backdoor
ps. 275.00 78
48.0
Maximum packet sizes
sends stralthy koepealive packets with so paylood (thos very small).
pervists comprumived
P4, min >> 41
40.0
Mininvam packet sizes
Table shows some features of the rules extracted from normal data that cannot be matched by the attack data, and exhibits how humans can interpret the model decisions] For example, the data of DDoS attacks cannot match the rules of three feature dimensions, including mean of packet sizes, mean of packet anter-arrival time, and duration of connection. It can be observed that the feature values of attacks are markedly lower than the bound of the rules. Such results are easy to interpret. Because the purpose of DDoS attacks is to overwhelm the resources of a victim, an attacker will realize asymmetric resource consumption between the victim and himself (i.e., using small packets), send packets at an extremely high rate (i.e., low inter-arrival time), and establish as many useless connections as possible (i.e., short duration of connections). These explanations are in line with how humans recognize the attack data. Hence, we can draw a conclusion that our method is able to provide precise insights into black-box anomaly detection models in a human- uudaandnderstandablee way.
6.4 Ablation Study
To evaluate the contribution of each component in our method, including the IC-Tree and the CBE algorithm, we conduct an ablation experiment by 1) replacing the IC- TreT with clustering algorithm K K-Means, 2) using only the CBE algorithm, and 3) replacing the CBE algorithm with directly using hypercubes as rules. In Table 5 we find that our method (IC-Tree + CBE) outperforms others in terms of fidelity on both datasets. Though using the K-Means can reach similar results, it cannot be expressed by axis-aligned rules with high interpretability and deployability as the IC-Tree can achieve. In summary, both components are helpful for the quality of rule extraction.
Table 5: Ablation study the components of our method.
Method
CIC-IDS2017
TON-JoT Comparisen
FD
Comparison
IC-Tree+ CBB (our method)
0,9856
0.9840
K. Means (k=10) CBE
0,9731
1.268%.
0.98012
0.386% I
K-Means (k=5) CBF
0.9735
1.228%]
0.9793
0,386%
Ouly CBE
0.9735
1.228%
0.9784
0.478%
IC-Tree + Hlpeerchee
0,9652
2.0699.
0.0647
93.43%. [
6.5 Computational Cost and Complexity
We also evaluate the computational cost of our method with respect training and prediction. Since CIC-IDS2017 dataset has 80 features in total, we train the model using the first 20, 40, 60, and 80 features of 4000 samples to investigate the influence of feature sizes. The results are shown in Table which demonstrate the average training and prediction time of our method. It can be seen that the training time is around minute, which is acceptable and practical for large-scale training. Besides, the training time increases basically linearly with the increase of feature sizes. This is because our method adopts a feature-by by-uur- strategy to explore the decision boundary of the model. For prediction time, our method is highly efficient, which only costs microsecond- inference. shows that as a rule-based approach, our method can achieve real-time execution for online use. Note that the runtime is measured purely based on Python. In practice, the prediction time of our method can be even less with more efficient code implementation.
overhead for one
NNoee that the "human understanding" was derived from the knowledge of the authors, and hence may be subjective and not reflect the wide population of security experts. We give more clarification of obtaining the content of Table the appendix, as well as potential reasons for the disagreement between humans and models.

---

Table 6: Average training and prediction time per sample for different feature sizes.
Training Time (ms)
Prediction Time (ms)
20
5.40
5.50 x 10
5.48
10 3
2.51 x 10
40
13.5 +
6.80 x 10
5.52
10
2.34
x 10
14.7
8.75
10
3.56
10
30.7
3.08
x 10
6.91
9.00 x 10
Metrics (9)
100.0
100.0
97.7
100.0
Metrics (9%
100.0
97.6 17.8
Metrics
Metrics
99.8
98.03
99.9
99.8
37.
99.8
97.0
TWa TM
97.5
99.7
27.5
93.8
TM
190
(a) Maximum tree depth
(b) #Explorers
(c) Sampling coefficient
(d) Iteration stride
Figure 2: Sensitivity experiments of hyperparameters.
We also theoretically analyze the time complexity of our algorithms. For training, the complexity of the IC-Tree is identical to CART: O(d log n2), where d is the feature size and is the sample number; the complexity of the CBE algorithm is O(K nodes of the IC-eree, and N₂ and N, are the number of initial explorers and auxiliary explorers. Therefore, the training time is theoretically linear to the feature size, which in line with the empirical results. For execution, the time complexity is O([C) d), where |C] is the number of extracted rules.
.Ne- NN,, where is the number leaf
6.6 Hyperparameter
We perform a sensitivity analysis of several hyperparameters on their influence on the rule extraction. We present four major hyperparameters in Figure including the maximum depth of an IC-Tree, Ne number of explorers, the coefficient p of sampling, and the factor rj that controls the stride of an iteration. Due to limited space, the analysis of other hyperparameters is placed in the appendix.
Maximum tree depth. A deeper IC-Tree has more leaf nodes, and can accordingly decompose more distributions that ease the difficulty of rule extraction. Mcanwhile, excessively fine- fine-grained splitting might cause overfitting. We find that r 15 achieves the best performance.
Number of Explorers. It is essentially the number of selected nodes per iteration in Beam Search, which considers multiple local optima improve greedy algorithms. But selecting too many nodes may also include more redundancy. Figure 26 shows that a value between 6 and 8 is recommended.
Coefficient of sampling. Figure 2c shows that higher value of the hyperparameter achieves better results. large coefficient decides a large radius of sampling from a multivariant Gaussian distribution, which helps the CBE algorithm quickly find the decision boundary of the original model.
Factor of iteration stride. In Figure 2d we find that a larger factor 1) can obtain rules of higher quality. As it decides the stride of finding the explorers for the next iteration, higher value of the hyperparameter might help the convergence of the iteration process.
7 Conclusion and Future Work
This paper proposes novel method to globally interpret black-box unsupervised anomaly detection, in which we introduce two types of rules and corresponding algorithms to extract these rules. The evaluation shows that our method outperforms prior work in terms of various metrics, boosting user confidence in complex models and facilitating their integration into high-stake security applications.
There are numerous meaningful directions for future work. First, new algorithms can be developed based on model interpretation to troubleshoot illogical inference processes in black-box models (e.g.. false positives) and realize the automation of precisely fixing errors. Moreover, researchers can investigate the integration of rule extraction with high-performance rule-based defense systems, such as P4 [13), to implement a more efficient security system. In addition, since the proposed method can be generic, the transfer to other areas of industry that also demand interpretable anomaly detection, such health, manufacturing and criminal investigation, can be further explored.
10

---

Acknowledgments and Disclosure of Funding
This work is supported by the National Key Research and Development Program of China under grant No. 3022YFB3105000 the Major Key Project of PCL under grant No. PCL2023AS5-1, the Shenzhen Key Lab of Software Defined Networking under grant No. DSSYS20140509) 17255999,,, and the research fund of Tsinghua University Tencent Joint Laboratory for Internet Innovation Technology.
References
[1] Y. Mirsky, T. Doitshman, Y. Elovici, and A. Shabtai, "Kitsune: An ensemble of autoencoders for online network intrusion detection," in Annual Network and Distributed System Security Symposium (NDSS), 2018.
[2] R. Tang, Z. Yang. Z. Li, W. Meng, H. Wang, Q. Li, Y. Sun, D. Pei, T. Wei, Y. Xu, and Y. Liu, "Zerowall: Detecting zero-day web attacks through encoder-decoder recurrent neural networks," in IEEE Conference Computer Communications (INFOCOM), 2020.
[3] C. Fu, Q. Li, M. Shen, and K. Xu, "Realtime robust malicious traffic detection via frequency domain analysis," in ACM SIGSAC Conference on Computer and Communications Security (CCS), 2021.
[4] R. Perdisci, W. Lee. and N. Feamster, "Behavioral clustering of http-based malware and signature generation using malicious network traces," in USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2010.
[5] E. C. R. Shin, D. Song, and R. Moazzezi, "Recognizing functions in binaries with neural networks," in USENIX Security Symposium, 2015.
[6] M. T. Ribeiro, S. Singh, and C. Guestrin, ""why should trust you?": Explaining the predictions of any classifier," in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016.
[7] S. M. Lundberg and S. Lee, "A unified approach to interpreting model predictions," in Annual Conference Neural Information Processing Systems (NeurIPS), 2017.
[8] M. T. Ribeiro. S. Singh, and C. Guestrin, "Anchors: High-precision aodel-agnostic explana- tions," in AAAI Conference on Artificial Intelligence (AAAI). 2018
[9] W. Guo, D. Mu, J. Xu, Su, G. Wang, and X. Xing, "Lemna: Explaining deep learning based security applications," in ACM SIGSAC Conference on Computer and Communications Security (CCS), 2018
[10] D. Han, Z. Wang, W. Chen, Y. Zhong, S. Wang, H. Zhang, J. Yang, X. Shi, and X. Yin, "Deepaid: Interpreting and improving deep learning-base based anomaly detection in security applications," " in ACM SIGSAC Conference on Computer and Communications Security (CCS). 2021.
[11] netfilter project, "iptables," http:///wwwwwittttrooooooon/onnh html 2023.
[12] snort, "Snort ids," hhtpss//www.snort.rrg// 2023.
[13] G. Xie, Q. Li, Y. Dong, G. Duan, Y. Jiang, and J. Duan, "Mousika: Enable general in ne-nekwork intelligence in programmable switches by knowledge distillation." in IEEE Conference on Computer Communications (INFOCOM), 2022.
[14] M. W. Craven and J. W. Shavlik, "Using sampling and queries to extract rules from trained neural networks," in International Conference on Machine Learning (ICML), 1994.
[15] O. Bastani, C. Kim, and H. Bastani, "Interpreting blackbox models via model extraction," " CoRR, vol. 0os//705.08504 2017.
[16] A. S. Jacobs, R. Beltiukov, W. Willinger, R. A. Ferreira, A. Gupta, and I. Z. Granville, "Ai/ml for network security: The emperor has no clothes," in ACM SIGSAC Conference on Computer and Communications Security (CCS), 2022.

---

[17] J. H. Friedman and B. E. Popescu, "Predictive learning via rule ensembles," " The Annals of Applied Statisties, vol. 2, no. 3, 2008.
[18) G. Vilone, L. Rizzo, and L. Longo, "A comparative analysis of rule-based, model-agnostic methods for explainable artificial intelligence," in Irish Conference on Artificial Intelligence and Cognitive Science, 2020.
[19] M. Du, F. Li, G. Zheng, and Srikumar, "Deeplog: Anomaly detection and diagnosis from system logs through deep learning." in ACM SIGSAC Conference Computer and Communi- cations Security (CCS), 2017.
[20] R. Li, Q. Li, J. Zhou, and Y. Jiang, "Adriot: An edge- assisted anomaly detection framework against iot-based network attacks," IEEE Internet of Things Journal, vol. 9, no. 13, pp. 176576 10587, 2022.
[21] R. Li, Q. Li, Y. Huang, W. Zhang, Zhu, and Y. Jiang, "lotensemble: Detection of botnet attacks internet of things," in European Symposium Research in Computer Security (ESORICS), 2022.
[22] B. Schölkopf, J. C. Platt, J. Shawe-Taylor A. J. Smola, and R. Williamson, "Estimating the support of high-dimensional distribution," Neural Comput., vol. 13, no. 7, pp. 1443-1471, 2001.
[23] L. Ruff, N. Görmitz, L. Deecke, S. A. Siddiqui, R. A. Vandermeulen, A. Binder, E. Müller, and M. Kloft, "Deep one-class classification," " in International Conference on Machine Learning (ICML), 2018.
[24] S. Itani, Lecron, and P. Fortemps, "A one-class classification decision tree based on kernel density estimation," Appl. Soft Comput., vol. 91, 106250, 2020.
[25] T. Liu, K. M. Ting, and Z. Zhou, "Isolation forest," in JEEE International Conference on Data Mining (ICDM), 2008
[26] H. Xu, G. Pang. Y. Wang, and Wang, "Deep isolation forest for anomaly detection," CoRR, vol. abs/2206.06602. 2022.
[27] D. Kingma and M. Welling, "Auto-encoding variational bayes," in International Conference on Learning Representations (ICLR), 2014.
[28] J. Kauffmann, K.-R. Müller, and G. Montavon, "Towards explaining anomalies: A deep taylor decomposition of one-class models," Pattern Recognition, vol. 101, p. 107198, 2020.
[29] D. Kazhdan, B. Dimanov, M. Jamnik, and P. Liò, "MEME: generating RNN model explanations via model extraction." CoRR, vol. abs/2012.06954, 2020.
[30] P. Liznerski, L. Ruff, R. A. Vandermeulen, B. J. Franks, M. Kloft, and K. Müller, "Explainable deep one-class classification," in International Conference on Learning Representations (ICLR), 2021.
[31] Z. Kong and K. Chaudhuri, "Understanding instance-based interpretability of variational auto- encoders," in Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
[32] Crabbé and M. van der Schaar, "Label-free explainability for unsupervised models," in International Conference on Machine Learning (ICML), 2022.
[33] O. Eberle, J. Büttner, Kräutli, K. Müller, M. Valleriani, and G. Montavon, "Building and interpreting deep similarity models," IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 3, pp. 1149-114 161, 2022.
[34] J. Sipple, "Interpretable, multidimensional, multimodal anomaly detection with negative sam- pling for detection of device failure," in International Conference on Machine Learning (ICMI.), 2020.
12

---

[35] L. Yang, W. Guo. Q. Hao, A. Ciptadi, A. Ahmadzadeh, X. Xing, and G. Wang, "CADE: detecting and explaining concept drift samples for security applications," in USENIX Security Symposium, 2021.
[36] M. Sundararajan, A. Taly, and Q. Yan, "Axiomatic attribution for deep networks," in Interna- tional Conference on Machine Learning (ICML), 2017.
[37] B. Letham, C. Rudin, T. H. McCormick, and D. Madigan, "Interpretable classifiers using rules and bayesian analysis: Building better stroke prediction model," CoRR, vol. abs/1511.00 51.01644, 2015.
[38] A. Barbado, O. Corcho, and R. Benjamins, "Rule extraction in unsupervised anomaly detection for model explainability: Application oneclass svm," " Expert Systems with Applications, vol. 189, p. 1 16100, 2022.
[39] I. van der Linden, H. Haned, and R. Kanoulas, "Global aggregations of local explanations for black box models," CoRR, vol. abs/1 tbs//190.00039, 2019.
[40] M. Setzu, R. Guidotti, A. Monreale, F. Turini, D. Pedreschi, and F. Giannotti, "Glocalx from local to global explanations of black box Al models," Artif. Intell., vol. 294, p. 103457,
[41] Q. Li, R. Cummings, and Y. Mintz, "Optimal local explainer aggregation for interpretable prediction," in AAAI Conference on Artificial Intelligence (AAAI), 2022.
[42] N. Frosst and G. E. Hinton, "Distilling a neural network into a soft decision tree," CoRR, vol. abs/1711.09784 2017.
[43] Y. Li, J. Bai, J. Li, X. Yang, Y. Jiang, and S. Xia, "Rectified decision trees: Exploring the landscape of interpretable and effective machine learning," CoRR, vol. abs/2008.09413, 2020.
[44] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone, Classification and Regression Trees Wadsworth, 1984.
[45] I. J. Goodfellow, J. Shlens, and C. Szegedy, "Explaining and harnessing adversarial examples," " in International Conference on Learning Representations (ICLR), 2015.
[46] X. Xu, J. Li, Y. Yang, and Shen, "Toward effective intrusion detection using log-cosh conditional variational autoencoder," IEEE Internet of Things Journal, vol. 8, no. 8, pp. 6187- 6196, 2021.
[47] A. Binbusayyis and Vaiyapuri, "Unsupervised deep learning approach for network intrusion detection combining convolutional autoencoder and one-class SVM," Appl. Intell., vol. 51, no. 10, pp. 7094-7108, 2021.
Li, [48] Y. Dong, Li, K. Wu, R. Li, D. Zhao, G. Tyson, J. Peng, Y. Jiang, S. Xia, and M. Xu, "Horuseye: Realtime iot malicious traffic detection framework with programmable switches," in USENIX Security Symposium, 2023.
[49] I. Liu, G. Engelen, T. M. Lynar, D. Essam, and W. Joosen, "Error prevalence in NIDS datasets: A case study on CIC-IDS-2017 and CSE-CIC-IDS-2018; in IEEE Conference on Communications and Network Security (CNS), 2022.
[50] T. M. Booij. I. Chiscop, E. Meeuwissen, N. Moustafa, and F. T. H. den Hartog, "Ton iot: The role of heterogeneity and the need for standardization of features and attack types in iot network intrusion data sets," IEEE Internet of Things Journal, vol. 9, no. 1, pp. 485-496, 2022.
[51] B. A. AlAhmadi. L. Axon, and I. Martinovic, "99% false positives: A qualitative study of SOC analysts' perspectives on security alarms," in USENIX Security Symposium, 2022.
[52] G. Apruzzese, P. Laskov, and A. Tastemirova, "Sok: The impact of unlabelled data in cyberthreat detection," in IEEE European Symposium on Security and Privacy (EuroS&P), 2022.
13

---

A Appendix
A.1 Proof of Proposition
Our Goal. We expect the extracted rules to have a high fidelity to the original model, that is, a similar coverage of normal data (i.e., true negative rate), and a similar detection rate of anomalies (i.c., true positive rate). To this end, we formulate our objective as follows:
arg min (C, LxwD(C,J.4))
The original objective can be estimated by finding the union of the conjunction of distribution decomposition rules and boundary inference rules for each compositional distribution:
Proposition 1.
Jargmin LX-D, S.9) LX=D, (. where C C CF. C2
(10)
k=1
We give the following lemma equivalent to Proposition I and prove it:
Lemma 1.1. the distribution decomposition rules and the inference boundary rules that minimize the loss on each of the compositional distributions are found. the sum of the minimum losses on each of the compositional distributions can estimate the minimum loss the overall distribution with significantly small error 1b i.e.,
min (C, I.x
min (C2, f. (p) L Lx (Cr, + +
(11)
where C = C. ^ C + 2 0.
Proof. The sum of the minimum losses each of the compositional distributions is calculated by an iteratively cumulative process. Let Ly be the sum of the minimum losses on each of the compositional distributions the j-th iteration, i.e.,
L,
min(CxxD,(Crr () + LxnDD (Cks S f)))..
Let X' ~ Uii= Dj represent variable belonging to any of the compositional distributions Dı...., Dy. We prove the Loop Invariant of Ly during the iteration, which always satisfies:
Lj CmiinCxxuut Du CR. CR. f.p)) + X DA U Cc,f +
Ü
(12)
A=1
k=1
1) For the first iteration, the equation L1 = min LX-D, (C1,,,)) LxeD, holds where di
obviously
2) Suppose the Equation 12 holds at the j-th iteration. For the (j + 1)-th iteration, we have the following derivations:
#+1
L8+1
Σ
min(Lx-D,CCk (CW, (14))
+ D. U Ck. +
De
k=1
k=
+ mmnn(Cx (CH+1. + LxMD, (C
H+1
J+1
=min(Cxx~iit Dr
U
Ch, L
U
Ch, (.:)) +
k=1
k=
j+l
i+l U Ca, f.4).
-x- DinD
U
Ck. f. + Cx~UL__ DanDji1
k=1
k=
14

---

where UR-1 DR n D1+1 represents the overlap area between the conjunction of the compositional distributions U Da and the (j + 1-tth compositional distribution D,-1. Recall the definition of the compositional distributions that a data sample belonging to one compositional distribution has a significantly small probability of belonging to other compositional distributions, meaning that the overlap area between the compositional distributions is significantly small. Therefore. the loss with respect the overlap area is also significantly small, given the data samples belonging to the area are significantly rare. Let
5+1
jt1
e + Cx-Uin PLND
Ck. xxwU DunD, U Ck...))
and we can get the final result of L3+1:
T1 min(C (xx-Utt UC (k, + XxaUtt De ( Ck. J, x)) + 1/, 1=1
1=1
which proves the loop invariant in Equation 12 At the last iteration when j = K, as the overall distribution equal the conjunction of the compositional distributions, i.e., D U Dk. prove Equation (T holds and Lemma 1.1 is correct.
A.2 Implementation of Our Method
Our implementation is primarily based on PyTorch (version 1.12.1) for the deep learning models, such as AE and VAE, Additionally, for data preprocessing. feature engineering, and model evaluation, we employ the versatile machine learning library scikit-learn (version 1.1.3). Python (version 3.9.15) serves as the programming language for our implementation, providing a rich ecosystem of libraries and tools for data manipulation and experiment orchestration.
Our experiments were conducted on a server equipped with the Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz (128GB RAM) and the GeForce RTX 2080 Super (8GB VRAM). Note that GPU is only used for the training of some DL-based anomaly detectors (e.g., AE, VAB), and our rule extraction method only requires the use of CPU.
A.3 Implementation of Baselines
In this section, delve into the details of the baseline methods used for evaluation in experi- ments, focusing on their implementation in the context of globally explaining unsupervised anomaly detection. The five baseline methods include Rule extraction from UAD, Estimated Greedy Decision Tree (EGDT), Trustee, Local Interpretable Model-agnostic Explanations (LIME), and a Knowledge Distillation (KD) method.
A.3.1 Rule Extraction from UAD
The Rule Extraction from UAD method was initially designed for one-class support vector machines (OCSVM) but is applicable to various types of unsupervised anomaly detection models. It uses feature scaling, anomaly detection, and clustering to produce rules from the input parameters X, In, Ic, d, m, I, where X refers to the input data frame with the features, In is list with the numerical columns, le is a list with the categorical columns, is a dictionary with the hyperparameters for OCSVM (kernel type, upper bound on the fraction of training errors and lower bound of the fraction of support vectors, v, and the kernel coefficient, 7)), m is a variable that defines the type of cluster algorithm, and is variable that specifies the type of approximation for obtaining the hypercubes.
The approach for obtaining rules depends on the type of cluster algorithm used and can involve iterative clustering and splitting of data points. The choice of kernel type in the OCSVM model can influence the rules obtained, with RBF kernel tending to enclose inliers and leave outliers outside, eventually forming hypercubes represent the rules.
A.3.2 Estimated Greedy Decision Tree (EGDT)
The EGDT method constructs a decision tree that approximates the black-box model. The algorithm generates new training data by actively sampling new inputs and labeling them with black-box
15

---

model. Based on these training data, EGDT constructs the decision tree T of size k similar to CART, in greedy manner and is pruned to improve interoperability. The algorithm takes into account the distribution of points that are routed to each leaf node in the decision tree to ensure that the label assigned to each leaf node is accurate.
A.3.3 Trustee
The model-agnostic DT extraction method Trustee, specifically focuses on interpreting security applications. The core idea is to construct an interpretable decision tree by minimizing the difference between the black-box model and the surrogate model. The algorithm creates several high-fidelity decision trees by executing an outer loop S times and an inner loop N times. In an unsupervised setting, we treat the predictions of the black-box model pseudo-labels and employ the same process as for the supervised case.
A.3.4 Local Interpretable Model-agnostic Explanations (LIME)
By learning an interpretable model locally around the prediction, LIME explains the predictions of any classifier in interpretable and faithful manner. LIME uses locally weighted square loss and an exponential kernel to approximate the black-box model. LIME trains sparse linear model on the local dataset to explain the prediction. The feature importance scores assist in identifying the most important features that contribute to the prediction, which can be used to gain insights into the model and improve LIME's trustworthiness.
In addition, this paper proposes "SP-LIME" that selects a set of representative instances with expla- nations to address the "trusting the model" problem, via submodular optimization. The submodular pickup method is used to select subset of instances that are representative of the entire dataset while reducing redundancy. This method allows for global perspective to ascertain trust in the model, in addition to explaining individual predictions. LIME can therefore be transformed from a local method to global method using the submodular pickup method, which makes it more useful in real scenarios.
The implementation of LIME in unsupervised settings is fairly straightforward. For a given input instance, we create a set of perturbations, predict their labels using the black-box model, and then fit an interpretable model (usually linear model) on this newly created dataset to approximate the local decision boundary.
A.3.5 Knowledge Distillation (KD) Method
In order to achieve interpretability and effectiveness simultancously, the KD method proposes knowledge distillation- baaalattio--baedd decision tree extension, called rectified decision trees (ReDT), and tries to transfer the knowledge from a complex model (the teacher) simpler (the student). ReDT extends the splitting criteria and the ending condition of the standard decision trees to allow training with soft labels distilled from well-trained teacher model while preserving the deterministic splitting paths. They recommend a jackknife-based distillation to obtain soft labels, which does not require backpropagation for the student model, and analyze the effectiveness of adopting soft labels instead of hard ones empirically and theoretically. In an unsupervised scenario, we employ the anomaly scores produced by the teacher model as pseudo-labels. The student model is then trained imitate these scores. This method's 's limitation lies in its strong reliance on the correctness of the teacher model's scores.
We need to note that these unsupervised adaptations of the baselines essentially introduce a supervised flavor to the learning process, with the black-box model's predictions serving the pseudo-labels. It is an important observation that these methods do not inherently work in an unsupervised manner and their application in such settings might be unreliable depending on the accuracy of the black- box model's 's predictions. On the other hand, our proposed method is fundamentally designed for unsupervised settings, making it more trustworthy choice for real-world applications.
is also worth mentioning that, except for LIME and Treste which use spen-source code, all other baseline methods were implemented in Python using the scikit-learn library, with default
16

---

parameters unless specified otherwise. Hyperparameters were set based on the initial grid search and then manually fine-tuned.
A.4
More Details in Experiments
A.4.1 More Metrics
We also examine other metrics in addition to the metrics given in the main article.
Precision (PR) measures the proportion of correctly predicted positive instances out of the total instances anticipated as positive. indicates the model's ability to avoid false positives. A lower rate of false positives is indicated by precision values that are higher.
Correctness (CR) evaluates the precision of the explanations provided by the IC-Tree method with respect to the underlying model. This can be quantified using the Jaccard similarity index, defined as Cr n. where is the number of correct outputs by the model.
Recall (RC) also known as sensitivity or true positive rate, quantifies the proportion of correctly predicted positive instances out of all actual positive instances. It indicates the model's ability to identify all positive instances without missing any. Higher recall values indicate lower rate of false negatives. It can be quantitatively assessed by the ratio TP TP4FN
RC
Fl score (F1) is the harmonic mean of precision and recall combined into single statistic, which provides a balanced measure of both precision and recall, capturing the overall performance of the model.
Besides the aforementioned metrics, in fact, we believe that the most appropriate way to assess "human's 's trust in anomaly detection models" should be employing trial in which human security experts are invited to inspect the rules of interpretation, measuring the consistency of understanding. Yet this is not easy task to conduct: eliminate the subjective influence of each expert, enough people must be invited to participate in the trial, which can be somewhat difficult to carry out. Despite the intrinsic limitations of lacking such metric, it is indeed common practice to employ only those commonly used metrics (e.g.. fidelity, Fl score) even in research works accepted to top venues, which may reveal an obvious gap between "research" and "practice".
The specifics of the performance metries of our proposed method in comparison to other baseline methods, including UAD. EGDT, Trustee, LIME, and KD, demonstrated in Table and Table In addition, we analyze the effects of several hyperparameters on our methodology, as shown in The performance metrics are categorized based different anomaly detection algorithms: Autoencoder (AE), Variational Autoencoder (VAE), One-Class SVM (OCSVM), and Isolation Forest (iForest) are shown in Table Precision (PR), Correctness (CR), Recall (RC), and F1 score (F1) are evaluated in this paper. Notably, our proposed method achieves the highest performance in almost all categories, with few significant instances where it ties with the best performer. This indicates the comprehensive superiority of our approach, as it consistently delivers exceptional performance across a wide range of models and metrics.
Table g
Table 7: Performance of rule extraction on CIC-IDS2017 dataset.
AE
VAE
OCSVM
iForest
Method
PR
CR
RC
F1
PR
CR
RC
F1
PR
CR
RC
F1
PR
CR
RC
Fl
UAD
0.5896
0.0659
0.1027
0.175
0.6104
0.0874
0.1126
0.1901
0.9912
0.067
0.999
0.9951
0.9993
0.067
0.9292
0.963
BODT
0,5729
0.4729
0,4729
0.8924
0.5613
0.873
0.6864
0.5462
0.9904
0.9244
0.8553
0.9179
0.9942
0.9402
0.9938
0.994
Trustee
0.8651
0.4255 0.6482
0.4255
0.812
0.831
0.7655
0.828
0.856
0.5509
0.6664
0.7494
0.954
0.4842
0.8676
0.8952
LIME
0.9998
0,7614 0.7569
0.8616
0.7091
0.7331
0.8641
0.9003
0.9892
0.741
0.9263
0.9567
0.8641
0.8305
0.8305
0.8751
KD
0,5141 0,5141
0.6871
0.5835
0.5612
0.1618
0.4516
0.5623
0.9157
0.3564
0.3748
0.5319
0.7863
0.067
0.8465
0.8461
Ours
0.9994 0.9488 0.9457
0.9718
0.9633
0.9633
0.9633
0.9645
0.9351
0.933
0.9653
0.933
0.9933
0.9354 0.9841
This extensive evaluation underlines the robustness and effectiveness of our method compared to established baselines. The superior performance, across varying metrics and under different detection models, signifies its potential as versatile solution for rule extraction in the TON-IoT dataset. This
17

---

Table 8: Performance of rule extraction on TON-IoT dataset.
AB
VAE
OCSVM
iForest
Method
CR
RC
F1
PR
CR
RC
F1
PR
CR
RC
F1
PR
CR
RC
F1
UAD
0.0058
0.085
0.1257
0.182
0,6155
0,216
0.3546
0.6845
0.9847
0.0501
0.0526
0.0998
0.9949
0.0501
0,1776
0,3014
EGDT
0.9749
0,9749
0.9854
0.9749
0,7659
0,7659
0.7856
0.8621
0.9979
0.8136 0.651
0.788
0.9964
0.6408 0,7977
0.886
Trustee
0.8475
0.4776 0.5465
0.4776
0,3809
0.3809
0.8416 0.3809
0.8482
0.7932
0.4147
0.557
0:9548
0.2338 0.6576
0,7525
LIME
0.7651
0,7664 0.6845
0.7561
0.9035
0.9053 0.8486 0.9053
0.7896
0.0749 0.7815
0.7512
0.7987
0.8354 0,8861 0,8354
KD
0,5765
0.0824
0.6548
0.3554
0,5648
0.0594
0.5486
0.5461
0. 0.8966
0.0505
0.1004
0.1805
0.5154
0.0501 0.8456 0.8465
Ours
0.9992 0.9992
0.9801
0.9992
0.9992
0.9861
0.9814
0.9345
0.9499
0.9743
0.99933
0.9933
0,9456 0.9968
demonstrates the practical utility of our proposed method, especially in a diverse and dynamic domain such as loT, which could significantly benefit from such adaptable and high-performing solutions.
As for the baseline methods, while some of them can achieve acceptable fidelity for certain models, they fail to maintain such results on other models, indicating that they cannot achieve qualified model-agnostic global explanations for unsupervised models. Further, most of their recall scores cannot meet the requirement of using their rules for online defense. is mainly because these methods either require labeled data to determine the boundary between normal and abnormal (e.g.. EGDT and LIME), or need sufficient outliers in the training data (e.g., UAD and KD), which can be unavailable in many security applications. In contrast, our method eliminates these requirements by the IC-Tree and CBE algorithm that explores the decision boundary in an unsupervised manner, and meanwhile realizes a high detection rate of anomalies.
Lastly, it is worth noting that while our method exhibits superior performance, do not imply the obsoleteness of other methods. Every method has its strengths and use cases, thus the selection of the method should always be context-dependent. Future work could involve fine-tuning our method to improve its performance further or be applied to other domains.
A.4.2 More Clarification of Human Understanding
We present a step-by-step description of obtaining the content in Table 4 in an ideal experiment, which takes data points as input and then shows the steps that come up with the explanations:
1. For a reported anomaly æ, we use the IC-Tree to pinpoint the rule of normality that judges x as anomalous. node. The rule is denoted by Cz.
realized by inputting æ into the tree and recursively finding the leaf
2. For each constraint of features in Ca, we compare the corresponding feature value of æ with the range of the constraint.
3. For the feature values outside the range of the constraints, the Rules of Normality, Feature Values, and Feature Meaning (i.e., the three columns in Table along with the raw data sample will be sent as the explanation to the security expert for further analysis.
4. The security expert will analyze the data sample to determine the type of attack (i.e., the Attack column T and give her/his understanding of the important attributes that make her/him identify the attack (i.e., the Human Understanding column in Table/4p.
5. If there is a huge gap between the provided explanation and expert understanding, it indicates that the anomaly detector is not trustworthy. The security expert may conduct further actions to improve the detector, such as retraining, fine-tuning, or reconsidering feature selection.
Note that such gap may not only occur when the anomaly detector makes erroneous decisions but also when the anomaly detector correctly detects an attack sample by unreasonable features. For example, the most obvious attribute of a Denial-of-Service (DoS) attack is typically its high rate of forwarding packets order to overwhelm the vietim. However, the provided explanation might suggest the IP address is an important feature for the anomaly detector to make this inference, which quite doubtful from the perspective of security expert. In practice, this may be due to "spurious correlation" or "shortcut learning []] Specifically, for the DoS example mentioned in our paper, unreliable decisions could be made due to inappropriate testbed settings for the collection of
'D. Arp, E. Quiring, et al.. "Dos and Don't 's of Machine Learning in Computer Security", in 31st USENIX Security Symposium, USENIX Security 2022.
18

---

training data, such as the DoS attack being launched from one separate host address while all other normal traffic is from other host addresses.
A.4.3 More Hyperparameter Analysis
The robustness of our method against changes in hyperparameters also needs to be evaluated. Sensi- tivity analysis analysis us to identify which parameters are most influential, thereby concentrating on tuning those to achieve optimal performance. In our study, we perform a sensitivity analysis on the hyperparameters:: Maximum Iteration, Auxiliary Explorer Sample Size (N₂),, Distribution Similarity Threshold (c), and Significance Threshold (6)).
Maximum Iteration represents the maximum number of iterations that the algorithm will run. In our analysis, as shown in T this parameter's variation from 0.01 to 0.5 has negligible effect on all the measured indicators. This displays the algorithm's 's resilience and robustness to changes in this hyperparameter, indicating that the model converges relatively rapidly.
Auxiliary Explorer Sample Size (N,) represents the number of samples gathered to assist the model's s exploration phase. The results indicate that our model effectively makes use of the available samples because an increase in Ns has little to no effect on the majority of the metrics. However, a slight increase in fidelity, correctness, and accuracy observed larger sample sizes, indicating that providing more samples can marginally enhance the model's 's performance.
Distribution Similarity Threshold (c) dictates how similar the proposed and baseline distributions should be for the tree's branches to accept the proposed distribution. Interestingly, whereas other metrics practically remain constant epsilon goes from 10 to 150, fidelity, correctness, and accuracy show a slight uptick. This suggests that our model exhibits an adaptable behavior to changes in distribution similarity thresholds.
Significance Threshold (6), which determines the minimum difference that should be deemed noteworthy, also shows a negligible effect all the performance indicators. This shows that the model is not sensitive to changes in 8 and supports the robustness of the proposed approach.
One noticeable aspect across all parameters is the TPR and TNR values. The TPR is consistently its maximum, showcasing the system's s excellent ability to identify positive instances. TNR also remains high, demonstrating the system's 's effectiveness in accurately identifying negative instances.
This sensitivity analysis underlines the robustness and adaptability of our proposed method. De- spite varying hyperparameters, our method consistently delivers high performance, emphasizing its potential as a versatile solution in diverse real-world scenarios. However, care should be taken to appropriately tune these parameters according to the specifics of the given context.
Future work might explore other influential hyperparameters and conduct similar sensitivity analysis. Moreover, utilizing methods like automatic hyperparameter tuning or evolutionary algorithms can lead to more efficient and optimal configuration settings.
Table 9: Performance of different hyperparameters.
Maximum
Iteration
Auxiliary Explorer Sample Size Distribution Similarity Threshold
Significance Threshold
Metric
0.01
0.05
0.1
0.5
50
100
150
350
10
50
100
150
0.001
0.005 0.01
0.1
Fidelity
0.9996
0.9996
0.9996
0.9995
0.9996
0.9996
0.9996
0.9995
0.9996
0.9998
0.9998
0.9998
0.9996
0.9996
0.9996
0.9995
Robustness
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1,0000
1.0000
1.0000
1.0000
1.0000
1,0000
1,0000
1.0000
1.0000
Correctness
0.9992
0,9992 0.9992 0.9992
0.9993
0.9992
0.9992
0.9992
0.9992
0.9995 0.9996
0.9996
0.9992
0.9992 0.9992 0.9992
Accuracy
0.9992 0.9992 0.9992 0.9992
0.9993
0.9992 0.9992
0.9992
0.9992
0.9995 0.9996
0.9996
0.9992
0.9992 0.9992 0.9992
TPR
1.0000
1,0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000
1.0000 1.0000 1.0000
TNR
0.9844
0.9845
0.9849
0.9842
0.9853
0.9846
0.9845
0.9841
0.9844
0.9909
0.9925
0.9920
0.9850
0.9847
0.9848 0.9841
A.5
Limitations
Though our method achieves global explanation with high fidelity, still has several limitations. First, our method works well with tabular data but might be inapplicable to raw image data. It is because our method treats every dimension of the feature space as a semantic feature, such as the average packet size of network connection, and extracts rules from each dimension of the feature space. In
19

---

contrast. raw image data are tensors of pixels. Their high-level semantics cannot directly derive from each of the pixels but usually need deep model with spatial awareness (e.g., CNN, ViT) extract feature maps, which are inconsistent with our method. Hence, this issue may limit the transferabilitty of the proposed method to other domains. Nonetheless, due to the typical trust expert knowledge over deep models in security domains, most security applications still rely on sophisticated feature engineering and use data representations with explicit semantics, suggesting that our method remains general in the field of security.
Second, recall that the rules extracted by our method are axis-aligned, which can be interpreted as a certain feature over/under a threshold and are human- sumaan-nddrrtandabl.. Though this format of rules significantly promotes interpretability, may limit its degree of fitting the decision boundary of the original model, which can be of various shapes in the sigh-dimensiona feature space for different models. Though our IC-Tree has mitigated this issue by splitting the distribution of normal data into multiple compositional distributions, which are more compact and more likely to be fitted using axis-aligned rules, there little guarantee that our method cannot encounter underfitting if the decision boundary of the original model is extremely irregular. It should be clarified that this is common limitation for all the global explanation methods that employ axis-aligned rules or decision trees as the surrogate expression. To this end, are also exploring other surrogate models and algorithms that can further balance the interpretability and fitting ability.
Lastly, as we mentioned above, we believe that the experiments on "human understanding and trust" can be significantly strengthened by introducing security practitioners to participate use test, finding if the interpretation provided by the proposed method is consistent with their expert knowledge of judging an anomaly. Currently, we are collaborating with the Tencent Security Platform Department, aiming to rectify this limitation by accounting for the opinions of real practitioners.
20


Reviews:
[{"review_id": "Uf7SqOiJZg", "reviewer": "Reviewer_mhUf", "summary": "The paper presents a technique to build a decision tree (DT) that uses the predictions from any unsupervised anomaly detection algorithm to split at the nodes when constructing the DT. This is named as the Interior Clustering Tree. The DT will be used to extract interpretable rules.", "questions": "1. What is the order of computational complexity or the execution time of the algorithm? Is the also affected by the curse of dimensionality?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The approach is useful for explainable anomaly detection and is an important problem domain.", "weaknesses": "1. Very similar to [1]. The difference is that in [1] the density is based on KDE, whereas, in the present work the density is based on the anomaly detector. So the technical novelty is less.\n\n2. Section 5: Lack of clarity; the procedure should be presented as algorithmic steps.\n\n3. We need more than just two datasets for empirical validity. These datasets also seem 'easy' since detection accuracy is very high for all anomaly detection algorithms. With easy datasets, the rules extracted would tend to be short and nicely interpretable. On the other hand, with harder datasets, the rules might be much more complex and difficult to interpret. I am interested in the types of rules extracted for the harder datasets.\n\nReferences:\n\n[1] Sarah Itani, Fabian Lecron, Philippe Fortemps, A one-class classification decision tree based on kernel density estimation, Applied Soft Computing, Volume 91, 2020 (https://arxiv.org/abs/1805.05021)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer mhUf for the detailed and constructive review. We will address all the expository comments in the final version of the paper.\n\n> Very similar to [1].\n\nThanks for your comment. We have thoroughly read the provided paper, which proposes the one-class decision tree (OC-Tree). Though it may have some similar design points to ours, we did not refer to this work at all, and there is great difference between the provided paper and our work in terms of both purposes and methods.\n\n**Different purposes.**\nThe OC-Tree is essentially a model for one-class classification (OCC), which is designed to find the distribution of the one-class data by enclosing the data within leaf nodes. Our work is different because our purpose is to extract interpretable rules from black-box anomaly detection models using one-class data. As an interpretation method, our focus is not on directly understanding the distribution of one-class data itself, but on explaining how the black-box model cognizes the distribution within the feature space, that is, how to replace the nonlinear decision boundary of the black-box model with interpretable rules, as suggested in Eq. (2) in our paper. This is also why an important evaluation metric for us is the fidelity of the black-box model, rather than just focusing on the accuracy of extracted rules for OCC.\n\n**Different methods.**\nOur method basically consists of the Interior Clustering Tree (IC-Tree) and the Compositional Boundary Exploration (CBE) algorithm. For IC-Tree, though it may have some similarities with OC-Tree in design, such as tree-based structure and new splitting mechanisms, it is significantly different from OC-Tree in that, as the reviewer indicates, OC-Tree relies on density estimation, while our IC-Tree uses the output of the anomaly detector as an indicator to partition feature space. A deeper understanding of this difference is that our IC-Tree does not come directly from the distribution of data in Euclidean space, but is guided by the black-box anomaly detector and tries to find the correlation between the decision-making logic of the black-box model and Euclidean space. Hence, our IC-Tree is different from OC-Tree from the starting point of the design. \n\nSecond, our CBE algorithm is a completely absent part of OC-Tree. This is also essentially due to the difference in purpose: OC-Tree only needs to find data distributions with a high density, while our method needs to continue to estimate the decision boundary of the black-box model on the basis of concentrated data distribution.\n\nIn summary, we think that our work and OC-Tree are still very different, and we believe that our approach still has innovative contributions to the community.\n\n> Section 5: Lack of clarity; the procedure should be presented as algorithmic steps.\n\nThanks for your valuable suggestion. Due to limited space, we didn’t include an overall algorithmic process for the CBE algorithm in the manuscript. We will add it to the paper. At this stage, we give a preliminary version of the algorithm using pseudocode as follows:\n\n---\n\nInput: data falling into k-th leaf node $X_k$, anomaly detector $f$ and its threshold $\\varphi$\n\nOutput: Boundary Inference Rule $C_k$ on this leaf node\n\n$H_k \\gets$ MinimalHypercube($X_k$);\n\nfor i-th dimension in $X_k$:\n\n$\\ \\ $while True:\n \n$\\ \\ \\ \\ $$e^{(1)},..., e^{(N_e)}\\gets$ InitialExplorer($H_k$);\n\n$\\ \\ \\ \\ $for each initial explorer $e$:\n\n$\\ \\ \\ \\ \\ \\ $$\\hat{e}^{(1)},...,\\hat{e}^{(N_s)}\\gets$ AuxiliaryExplorer($e$);\n\n$\\ \\ \\ \\ $Beam Search for $N_e$ number of auxiliary explorers with minimal probability of being normal judged by $f$ and $\\varphi$;\n\n$\\ \\ \\ \\ $$e\\gets$GradientApprox($\\hat{e}$) for each $\\hat{e}$ of the $N_e$ auxiliary explorers;\n\n$\\ \\ \\ \\ $if it satisfies ending condition:\n\n$\\ \\ \\ \\ \\ \\ $$c_i\\gets (x_i \\odot \\hat{e}_i)$; break;\n\nreturn $C_k\\gets H_k\\vee(c_1\\wedge c_2\\wedge ...)$;\n\n---\n\n> We need more than just two datasets for empirical validity. These datasets also seem 'easy' since detection accuracy is very high for all anomaly detection algorithms.\n\nThanks for your valuable comment. We would like to resolve your concerns with both clarification and additional experiments.\n\n**Clarification.**\nFirst, although we stated in the paper that only two datasets are used for evaluation, each of them actually consists of multiple datasets in which different types of network attacks are collected. For example, TON-IoT datasets contain 9 types of network attacks, including backdoor, DoS, DDoS, injection, man-in-the-middle, brute force login, ransomware, scanning, and cross-site scripting. To ease the demonstration, the results in Table 3 in the paper are the average values of different attack datasets. We have added the result of each attack dataset in the attachment of the global response.\n\nSecond, these datasets seem simple because security applications often rely heavily on feature engineering based on expert knowledge, so the features contained in the datasets have a high degree of discrimination. Other works published at top conferences, such as references [1-3] in the paper, also achieve very high anomaly detection accuracy (over 0.99). The characteristics of datasets may be somewhat different from those of other domains. For example, datasets in the CV domain typically only contain raw pixels.\n\n**Additional experiments.**\n\nWe have tried our best to add the evaluation on a new dataset that contains more features. Please refer to the global response. We are still conducting experiments on another dataset and will add the results in the paper.\n\n>What is the order of computational complexity or the execution time of the algorithm? Is the also affected by the curse of dimensionality?\n\nWe have added the evaluation to the global response.\n\nAgain, thank you for your comments, and we hope that this has addressed your concerns!"}, {"review_id": "qomSOfRGlR", "reviewer": "Reviewer_eS8h", "summary": "The authors propose and Distribution Decomposition Rules and Boundary\nInference Rules to make black boxes more interpretable.\n\nThey use Interior Clustering Tree IC-tree to find distribution\ndecomposition rules.  The IC-tree algorithm splits the data on a\nfeature value at each node recursively.  The feature value that\nmaximizes the gain in gini index before and after the split is chosen\nat each node.  Gini index is 2p(1-), where p be is the average output\nof the anomaly detection model f(x), which is the trained neural\nnetwork model.  The path to each leaf forms a distribution\ndecomposition rule and each leaf represents a data subset that is in\nthe same distribution.\n\nThe Compositional Boundary Exploration (CBE) algorithm finds a minimal\nhypercube that encloses the normal data in each distribution (leaf\nnode).  CBE uniformly samples data points on each hyperplane as initial\nexplores (centriods), then samples from a Gaussian distributions\npoints as auxiliary explorers near the centroids within some radius.\nThe samples are used to query the model to find samples with the\nlowest probability to be normal (negative examples), these are called\ncandidate explorers.  They use Fast Gradient Sign Method to perturb\nthe explorers.  Since the loss function is not known from the model,\nthey approximate the gradient by the gradient between the model\noutputs of an initial explorer and an auxiliary explorer with respect\nto the different in the samples.  The explores are perturbed until the\nf() indicates it is normal (less than threshold phi).  The\ncorresponding feature values forms the hyperplanes for the boundaries.\n\nThey evaluate 5 existing extraction methods with 4 black-box models and\n2 datasets.  In addition to TPR and TNR, they measure Fidelity (which\ncalculates agreement between the black-box model and their extracted\nrules) and Robustness (which estimates small input perturbations do not\nchange the model's output).  Their proposed method generally\noutperforms existing techniques.  Ablation studies were performed to\naccess the contribution of each component.\n\nI have read the authors' responses and commented on them.", "questions": "1.  line 220: What is the reasoning for the initial vs auxiliary explorers?    \n\n2.  line 227: What is the reasoning for \"minimal probability of being normal\"?\n     Why not choose candidates that are close to the threshold $\\varphi$ and then\n     try to get to the other side of the threshold?\n\n3.  line 227: Does each of the dimension/feature have two candidate\n    explorers so that they yield two boundary (axis-parallel\n    hyperplane) in each dimension?  How do you guarantee one boundary\n    on each side in one dimension?\n\n4.  line 239: should f() be greater than $\\varphi$ instead of less than?  I think\n     you try to go from low f() to high f() to cross $\\varphi$.\n\n5.  line 323: \"directly using hypercubes as rules\", how are these\n    hypercubes found?  Are they from the IC-tree?  A hypercube can\n    be found for instances in each leaf by finding the \"min and max\" value\n    of each feature/dimension via a fitted Gaussian.  If that is not what you did, adding\n    it as a comparison would be interesting.\n\n6.  line 325: \"Though using the K-Means can reach similar results, it\n    cannot be expressed by axis-aligned rules with high interpretability\n    and deployability as the IC-Tree can achieve.\"\n\n    Using CBE, axis-aligned rules can be found with clusters found by\n    K-means.  If I understand correctly, the IC-tree can be ignored\n    after the boundary rules are extracted by CBE.", "limitations": "Limitations of the proposed approach seem to be discussed as\ndirections in future work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  The proposed algorthms yield interpretables rules with high\n    fidelity of the black-box models.\n\n2.  Empirical results indicate the proposed algorithms generally\n    outperform existing ones.\n\n3.  The paper is generally well written.", "weaknesses": "1.  Some ideas could be clarified, see questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer eS8h for the detailed and constructive review, especially thanks for your recognition of our work. We will address all the expository comments in the final version of the paper.\n\n>line 220: What is the reasoning for the initial vs auxiliary explorers?\n\nThe initial explorers set the starting point for the search on each hyperplane. Since the range of some hyperplanes may be large, and we do not know from which point of the hyperplane we can find the decision boundary of the model the fastest, we evenly sample $N_e$ initial explorers on the hyperplane to increase the possibility that we can successfully explore the decision boundary.\n\nThe auxiliary explorers are further sampled near each initial explorer. Their role is to explore the decision boundary of the model using an initial explorer as a starting point. We will eventually find the $N_e$ points closest to the decision boundary from all the auxiliary explorers, through the output of the black-box model and the Beam Search method, and generate the next iteration of the initial explorers based on them.\n\n>line 227: What is the reasoning for \"minimal probability of being normal\"? Why not choose candidates that are close to the threshold $\\phi$ and then try to get to the other side of the threshold?\n\nThanks for your comment. In fact, your understanding is consistent with our approach, and probably it’s our expression that confuses you. In Definition 1, we abstract an unsupervised anomaly detection model to a probability density function of being normal. Therefore, a minimal model output that is close to the threshold is equivalent to a \"minimal probability of being normal\". We apologize for our confusing expressions and will give more clarification in the paper.\n\n>line 227: Does each of the dimension/feature have two candidate explorers so that they yield two boundary (axis-parallel hyperplane) in each dimension? How do you guarantee one boundary on each side in one dimension?\n\nYes, the boundary exploration will be conducted on each side of one dimension so that two boundaries (one upper bound and one lower bound) are expected to be obtained; your understanding is exactly correct. For your second question, though we expect to obtain one boundary on each side in one dimension, in fact, we do not guarantee the acquisition. As we stated in line 246, some of the dimensions might be a contour line for the output of the anomaly detection model, i.e., there is no correlation between model decisions and this specific feature. In this case, we just leave this dimension “open” and do not generate any constraint on this dimension.\n\n>line 239: should f() be greater than $\\varphi$ instead of less than? I think you try to go from low f() to high f() to cross $\\varphi$.\n\nThanks for your comment. Again, we think it’s our expression that confuses you. Due to our abstraction of an unsupervised anomaly detection model to a probability density function of being *normal*, the lower model output suggests more anomalous under this setting. This may indeed go against our common sense a bit, such as MSE as a model output when a higher value represents a more anomaly.\n\n>line 323: \"directly using hypercubes as rules\", how are these hypercubes found? Are they from the IC-tree? A hypercube can be found for instances in each leaf by finding the \"min and max\" value of each feature/dimension via a fitted Gaussian. If that is not what you did, adding it as a comparison would be interesting.\n\nYes, your understanding is exactly correct. A hypercube is found on each of the leaf nodes of the IC-Tree via the classic min/max approach as you mention. \n\n>Using CBE, axis-aligned rules can be found with clusters found by K-means. If I understand correctly, the IC-tree can be ignored after the boundary rules are extracted by CBE\n\nThanks for your valuable question. Indeed, as you point out, after obtaining the final rule set, the IC-Tree can be ignored. However, an issue here is that, as defined in Eq. (3), the final rules are the conjunction of distribution decomposition rules (obtained by IC-Tree) and boundary inference rules (obtained by CBE) for each compositional distribution. If we use clustering algorithms like K-Means to substitute IC-Tree, we cannot obtain axis-aligned rules anymore that can be combined with boundary inference rules obtained by CBE, which hinders the implementation of end-to-end axis-aligned rule extraction for better interpretability.\n\nAgain, thank you for your comments, and we hope that this addresses your concerns!"}, {"review_id": "x7e8NGgdT4", "reviewer": "Reviewer_AbmJ", "summary": "The paper deals with the problem of \"explainable\" unsupervised machine learning (ML) for anomaly detection (AD), with a focus of network intrusion detection (NID). The paper argues that while abundant effort focused on providing _supervised_ ML techniques that are explainable, this is not the case for _unsupervised_ ML methods---which are abundant in NID due to the lack of fine-grained labelled data. The paper hence seeks to rectify such shortage by proposing a novel solution that simultaneously (i) provides \"human-understandable\" explanations; and (ii) allows to derive some \"rules\" that can be used to improve the detection performance of the unlderying network intrusion detection system (NIDS). The proposed method leverages the intuition of \"slicing\" the (training) data into segments that represent a given group of (network) activities, e.g., web or database traffic; and then derive specific rules that describe these activities in an \"humanly understandable way\" and which can be used (if violated) to identify anomalies. The method is rigorously described and its effectiveness is assessed through various experiments on two well-known NID datasets, showing some advantages over existing baselines (which are mostly tailored for supervised ML).", "questions": "I thank the authors for submitting their paper to NeurIPS'23. Despite my stark criticism, I liked reading it. This is why I endorse the authors in answering the following questions to the best of their abilities: if provided with compelling evidence, I may be willing to raise my score.\n\n* Q1) Given that CIC-IDS17 is flaeed, how much time would it be necessary to re-do the experiments?\n* Q2) What is the runtime required to train/test the proposed method, and how does it compare to existing methods?\n* Q3) Are the details of the experimental platform correct?\n* Q4) What features have been used to train the models?\n* Q5) How was Table 4 derived?\n* Q6) Have the experiments been carried out multiple times to accout for bias?\n* Q7) Can the authors provide convincing evidence of the \"necessity\" of the proposed method _in practice_?\n* Q8) How is the \"robustness\" measured?\n* Q9) How long would it take to assess the efficacy of the proposed method under varying percentages of \"noisy\" data?\n* Q10) Does the method _require_ netflow data to work? And, if so, how would the resulting performance change if the flows are generated in a different way?\n\n\nPlease refer to the main review for additional information", "limitations": "The \"limitations\" are discussed in the supplementary material. Unfortunately, they do not mention that, e.g., the proposed method relies on overly optimistic assumptions (for real deployments), nor that the \"understanding\" is likely drawn by subjective intuitions. Also, I see no reason for mentioning that the proposed method does not work well on images, unless this data-type becomes prevalent in NID (and I do not see this happening anytime soon).\n\n==========\n\n# Update after rebuttal\n\nI have increased my score from a 3 (Reject) to a 5 (Borderline Accept); I have also increased the scores for Contribution and Soundness (from a 2 to a 3). The improvements are due to the paper now being much more truthful as to what it does, as well as by accounting for a \"non-flawed\" version of the considered datasets. Ultimately, I do not see any clear reason for \"rejection\", but I also do not feel strong reasons to accept this---aside from tackling a highly practical area of application of ML, which could serve as inspiration for future work.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ Evaluation on two NID datasets\n+ Ablation Study\n+ Rigorous description\n+ Some design choices \"make sense\"\n+ The method is rigorously described\n+ Some ideas are correlated with proofs (in the appendix)\n+ The paper tackles an open research problem (on the surface) for which limited research is available\n+ Evaluation considering various parameter settings\n+ The results show improvement over baselines\n\n\nThe paper addresses an intriguing research problem (\"explainable unsupervised machine learning\") which has high relevance in some real-world applications of ML (i.e., network intrusion detection). The proposed method is rigorously described: some intuitions are sensible, and for others there are proofs provided which increase the overall soundness of the proposed methodology. The evaluation (which is reproducible, since the code is disclosed and the datasets are publicly available) shows improvement over prior work (most of which, however, was not designed to work in the given setting).\n\nFinally, the main novelty of this paper resides in addressing an underexplored problem.", "weaknesses": "## High Level\n\n- Unconvincing motivation\n- Excessively optimistic assumptions\n- Flawed dataset and poor setup\n- Questionable metrics \n- Unclear \"understanding\" assessment\n\nDespite some strengths, the paper suffers from various issues which prevent me from recommending inclusion in NeurIPS'23 program. Specifically, though the paper seeks to address a \"real-world problem\" (i.e., how security operators deal with ML-NIDS that are not explainable), the proposed method relies on assumptions that can hardly be met in the real world---thereby decreasing the overall significance of the findings. \n\nAnother problem pertains the soundness of the experimental procedure, which casts doubts on the validity of the results and, hence, of the conclusions drawn from the paper. \n\nFinally, from a \"novelty\" perspective, the techniques used to address the problem tackled by this paper may be (somewhat) novel, but they can be redundant in light of some well-known considerations of the NID context.\n\n## Low Level\n\nI will provide an extensive description of the abovementioned weaknesses below. I will directly quote some statements made in the paper, and I will also attempt to provide suggestions and plenty of references to support my points.\n\n\n\n\n### Unconvincing motivation\n\nAlbeit I acknowledge that the goal of providing \"explainable ML\" is relevant, I do not see a strong incentive in providing \"explainable _unsupervised_ ML methods\". This is because practitioners are well-aware that such methods are bound to be inaccurate, since they assume a notion of \"normality\". In a sense, the \"explanation\" for a raised anomaly is that a given data-point deviates from such normality; even practitioners acknowledge this as a fact [D]. This of course leads to a huge amount of false positives, which must be manually triaged _regardless of the explanations_. \n\nIn light of this, I did not find a compelling argument (provided in the paper) in favor of focusing on unsupervised ML --- or, at least, not in the context assumed by this paper. Perhaps a potential avenue is using said explanations for \"attack attribution\" [H], but this is never made explicit.\n\n### Optimistic assumptions\n\nThe method makes some strong assumptions that are too optimistic in real settings. The problem is that the main contribution (allegedly) is addressed at real-world deployments of ML.\n\n> We consider the anomaly detection tolerant of noisy data, but their proportion in training dataset is small and we do not have any ground truth labels of the training data.\n\nThis is a bold assumption which almost trivialized the entire problem of anomaly detection. If one is confident of having a (large) training set containing \"certain\" benign samples, one can use it as basis for supervised ML by enriching it with malicious samples (e.g., [I]). Unfortunately, in reality, obtaining such a \"clean\" training set requires huge manual effort [D] (and so is determining the threshold which allows for a manageable amount of alerts in operational contexts). Do note that the experimental evaluation assumes a \"perfect\" labelling of the normal samples in the training data (there is no mention of \"noisy\" data).\n\nAlso, consider the following statement\n\n> For example, a server supports multiple services such as web, email and database. The representations of these services can be disparate and located in different regions in feature space with little transition between the regions, making it infeasible to find a uniform rule set to accurately estimate the original model\n\nIn theory, this is correct. In practice, however, addressing this problem is trivial: \"web\", \"email\" and \"database\" are all services that can be easily separated by looking at the source ports of the corresponding communications (potentially with an additional filter based on the IP address). Indeed, one must remember that these methods must be setup and deployed by network administrators---who are well aware of what services are running in their organization.\n\n(note that even though here I have criticized the specific example, the consideration above can be extended to any type of potential \"multimodality\" that arises from network data)\n\nIn light of this, I fail to see any practical reason in favor of the method proposed in the paper. Perhaps the authors can provide a clear use-case in which the \"multimodality\" of the data is truly problematic to model.\n\n### Flawed dataset (and poor experimental setup)\n\nThe proposed method is evaluated on two datasets for Network Intrusion Detection (NID), one being the CIC-IDS17. Unfortunately, this dataset is flawed [J, K]. Note that [J] came out in 2021, and it has already been well-received by the NID community, so it is concerning that this paper (which has been submitted to a top-venue such as NeurIPS) performs the experiments on the \"flawed\" variant of this dataset---especially given that a \"fixed\" version exists (provided in [J]). \n\nFurthermore, note that [J] clearly stated that some features in this dataset (both the original and fixed version) are redundant for NID purposes (this is especially the case for \"flow-based\" NID [I, L]): however, this paper does not provide any detail about whether precautions have been taken to clean the feature set from \"obvious\" features (note that this also entails the ToN-IoT dataset)\n\nFinally, it is unclear whether the experiments have been repeated a sufficient amount of times to derive statistically significant conclusions (as recommended in [B]). The paper states:\n\n> The datasets are randomly split by the ratio of 6:2:2 for training, validation and testing\n\nThe \"random split\" may bias the results. \n\nIn light of this, the experimental setup may not be sound, thereby questioning the overall results. I invite the authors to look into other datasets as well (the works referenced in this review provide plenty of suggestions).\n\n\n### Questionable evaluation metrics\n\nI was unable to find a link between the metrics used in the evaluation and the overarching goal of the paper.\n\nAccording to the Introduction:\n\n> we can present the inferential process of the black-box model in a human-understandable way, and build a surrogate rule-based model for online defense at the same time.\n\nHowever, there is nothing in the evaluation that allows one to measure whether the ```inferential process of the black-box model``` is presented in a ```human-understandable way```. This is because the evaluation appears to merely focus on the sheer detection performance of the \"surrogate\" model.\n\nTo re-quote a statement in the introduction (with which I fully agree!):\n\n> security operators tend to trust human-understandable rules rather than the unintuitive outputs such as labels and numeric values from the complex and incomprehensible models.\n\nThere is little in the evaluation that makes me believe that security operators would appreciate the explanations provided by the proposed method. \n\nI also have some concerns on the way these metrics are described:\n\n> Fidelity (FD), i.e., the ratio of input samples on which the predictions of original model and surrogate model agree over the total samples, which indicates the extent to which humans can trust the explanations\n\nI disagree: at best, FD denotes how much the surrogate and original models \"agree\". This says nothing about whether a human can \"trust\" the explanation in the general sense. Indeed, the quoted statement would be correct under the assumption that the original model's explanation are \"correct\". \n\n> Robustness (RB), i.e, the persistence to withstand small perturbations of the input that do not change the prediction of the model\n\nI am confused here: what is the ```model``` whose prediction should not change? I.e., is it the \"original\" or the \"surrogate\"?\n\n### Unclear method for \"understanding\"\n\nThis issue follows the previous one. The \"human-understandable way\" to interpret the rules generated by the proposed method is assessed in Section 6.3. However, there is a lack of details in this Section, and the \"conclusions\" appear to be drawn from purely subjective statements.\n\nConsider the following:\n\n> Such results are easy to be interpreted.\n\nHow is this determined?\n\n> These explanations are in line with how security experts recognize the attack data.\n\nNo reference is provided.\n\nPlus, there is a mismatch with Table 4 and the overall assumptions made in the paper. Specifically, the paper assumes an \"unsupervised\" AD task, wherein the specific attack is not known. In light of this, how can a human derive that, e.g., (taken from Table 4):\n\n> DDoS attacks use packets of small sizes to achieve\nasymmetric resource consumption on the victim side,\nand send packets at a high rate to flood the victim\n\n? At most, a human sees some rules (e.g., ```ps_mean > 101.68, iat_mean > 0.063, dur > 12.61```) which -- when not met -- trigger some anomalies. But from here to stating that these anomalies relate to \"DDoS attacks\" there is a long way. For instance, \"violation\" of these rules can very well be related to a port-scanning activity (which can very well be a benign event, e.g., a new host which scans the network after joining it).\n\n\n### Some bold statements in the Introduction\n\nBelow is a list of statements made in the Introduction for which I have serious concerns.\n\n\n> it requires no attack/malicious data during the training (i.e., zero-positive learning), which are typically much more sparse and difficult to obtain in contrast with benign data;\n\nActually, obtaining \"certain\" benign data can be even harder than acquiring malicious data (see [B]). As a matter of fact, real-world deployments of ML entail very coarse \"labelling\" schemes [A].\n\n> it does not fit any known threats, enabling better detection on unforeseen anomalies.\n\nBut this also means that some of the raised anomalies have nothing to do with attacks---leading to \"alert fatigue\" (see [C,D,E]).\n\n> being self-explained and accurate for high-stake security applications.\n\nPlease define \"accurate for high-stake security applications\". Even non-surrogate models have a huge margin of error [C].\n\n> Accuracy Loss (CH3). [...] In this case, though these methods can provide model explanation, they cannot meet the need of online deployment which requires high detection accuracy in security applications.\n\nI disagree. The \"surrogate\" model has a single objective: provide \"global\" explanations. Therefore, even though such surrogate model may have worse \"accuracy\", it is the \"larger\" model that is meant to be deployed, while the \"surrogate\" is only used for explanation tasks.\n\n> We observe that an important reason why simple surrogate models are ineffective is that they cannot learn well about the complex data distribution in high-dimensional space.\n\nOn what grounds is this \"observation\" made? Is it just an educated guess, does it derive from original experiments, or is it drawn from prior research?\n\n\n> The extracted rules outperform prior work in terms of diverse metrics including fidelity, robustness, true positive rate and true negative rate\n\nThis contradicts what was written at the beginning of the introduction: ```security operators tend to trust human-understandable rules rather than the unintuitive outputs such as labels and numeric values from the complex and incomprehensible models.```. In what way are the metrics mentioned above different from \"numeric values from the complex and incomprehensible models\"?\n\n> which meets the demand of improving human trust in black-box models and maintaining high detection accuracy for online deployment.\n\nThis is a self-claim: there is no evidence provided that ```fidelity, robustness, tpr, tnr``` meet the described ```demand``` (in terms of explainability).\n\n\n\n\n### Some additional issues:\n\nThe following is a list of miscellaneous issues I found in this submission; note that these issues are not necessarily \"minor\".\n\n* Some relevant works have not been considered. The extensive study carried out in [F] reveals, e.g., [G] -- which specifically focuses on providing \"explainable unsupervised models\".\n* ```furthur``` typo\n* I found the following statement to be misleading (and also unnecessary): ```we refer to adversarial attacks [44] and propose a method to approximate the optimal direction to explore the decision boundary```\n* ```Further, most of their true positive rates cannot meet the requirement of using their rules for online defense, as the sheer amount of attack data they miss can cause huge damages.``` please provide facts instead of writing vague statements such as \"can cause huge damages\". Even a single false negative can lead to \"huge damages\" [D].\n* I did not find any measure of the \"runtime\" used to train/test the proposed method. \n* Did the evaluation _really_ take place on a server having an RTX3090 with 8GB of VRAM? (given that the RTX3090 has 24GB of VRAM?)\n* Did the evaluation _really_ take place on a server having an Intel Xeon with only 8GB of RAM?\n* To my understanding, the method assumes that the data-points represent \"network flows\" (such is the data contained in the considered datasets). However, there is a huge variability in the ways such flows can be generated (see [I,M]). What would happen if the netflow generator is different? \n\n#### EXTERNAL REFERENCES\n\n[A]: Van Ede, Thijs, et al. \"Deepcase: Semi-supervised contextual analysis of security events.\" 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022.\n\n[B]: Apruzzese, Giovanni, Pavel Laskov, and Aliya Tastemirova. \"SoK: The impact of unlabelled data in cyberthreat detection.\" 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P). IEEE, 2022.\n\n[C]: Alahmadi, Bushra A., Louise Axon, and Ivan Martinovic. \"99% False Positives: A Qualitative Study of {SOC} Analysts' Perspectives on Security Alarms.\" 31st USENIX Security Symposium (USENIX Security 22). 2022.\n\n[D]: Apruzzese, Giovanni, et al. \"The role of machine learning in cybersecurity.\" Digital Threats: Research and Practice 4.1 (2023): 1-38.\n\n[E]: Hassan, Wajih Ul, et al. \"Nodoze: Combatting threat alert fatigue with automated provenance triage.\" network and distributed systems security symposium. 2019.\n\n[F]: Nadeem, Azqa, et al. \"Sok: Explainable machine learning for computer security applications.\" arXiv preprint arXiv:2208.10605 (2022) [to appear in EuroS&P'23]\n\n[G]: Wickramasinghe, Chathurika S., et al. \"Explainable unsupervised machine learning for cyber-physical systems.\" IEEE Access 9 (2021): 131824-131843.\n\n[H]: Nisioti, Antonia, et al. \"From intrusion detection to attacker attribution: A comprehensive survey of unsupervised methods.\" IEEE Communications Surveys & Tutorials 20.4 (2018): 3369-3388.\n\n[I]: Apruzzese, Giovanni, Luca Pajola, and Mauro Conti. \"The cross-evaluation of machine learning-based network intrusion detection systems.\" IEEE Transactions on Network and Service Management (2022).\n\n[J]: Liu, Lisa, et al. \"Error Prevalence in NIDS datasets: A Case Study on CIC-IDS-2017 and CSE-CIC-IDS-2018.\" 2022 IEEE Conference on Communications and Network Security (CNS). IEEE, 2022.\n\n[K]: Engelen, Gints, Vera Rimmer, and Wouter Joosen. \"Troubleshooting an intrusion detection dataset: the CICIDS2017 case study.\" 2021 IEEE Security and Privacy Workshops (SPW). IEEE, 2021.\n\n[L]: Arp, Daniel, et al. \"Dos and don'ts of machine learning in computer security.\" 31st USENIX Security Symposium (USENIX Security 22). 2022.\n\n[M]: Vormayr, Gernot, Joachim Fabini, and Tanja Zseby. \"Why are my flows different? a tutorial on flow exporters.\" IEEE Communications Surveys & Tutorials 22.3 (2020): 2064-2103.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Abmj for the detailed and constructive review. We are very glad to hear so much constructive advice from a security expert like you. Many of the references are very helpful for NIDS research, which we would like to cite in our paper. \n\n>Given that CIC-IDS17 is flawed, how much time would it be necessary to re-do the experiments?\n\nWe have tried our best to re-do the experiments on a new dataset as you suggest: CIC-IDS-improved. Please refer to the global response.\n\n>What is the runtime required to train/test the proposed method, and how does it compare to existing methods?\n\nWe have added this experiment and please refer to the global response.\n\n>Are the details of the experimental platform correct?\n\nWe are sorry for the mistakes in the experimental platform. Our server uses Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz (128GB) and GeForce RTX 2080 Super (8GB). Note that GPU is only used for the training of some DL-based anomaly detectors (i.e., AE, VAE), and our rule extraction only requires the use of CPU. Thanks for your correction!\n\n>What features have been used to train the models?\n\nWe use common flow-level features as shown in the following table, which consider both directions of 5-tuple flows and various flow statistics. Some of the original features are actually not used because 1) we find that they contain obvious errors, such as considerable numbers of NaN and infinity; 2) they are easy to create shortcut patterns due to specific testbed setup (i.e., spurious correlation mentioned in \"Dos and don'ts of machine learning in computer security\"), such as IP address. Considering that NeurIPS focuses on AI, we didn’t include too much details on network traffic in our paper. We will add more clarification in supplementary materials.\n\n|Attribute|Statistics|Direction|Number|\n|-|-|-|-|\n|packet count|-|forward, backward, bidirection|3|\n|packet size|mean/max/min/var|forward, backward, bidirection|12|\n|inter-arrival time|mean/max/min/var|forward, backward, bidirection|12|\n|flow duration|microsecond|bidirectional|1|\n|destination port|0-65535|forward|1|\n|L4 protocol|TCP,UDP,ICMP|-|1|\n\n>How was Table 4 derived?\n\nThe violation of certain rules explains why the model makes predictions for anomalies. However, it can only serve as the necessary but not sufficient condition for an anomaly to be judged as a certain attack. Our workflow of integrating the explanation method with a NIDS is similar to [b]. When an anomaly is detected, the security operator still needs to inspect anomalies and judge the attack type based on his/her expert knowledge (i.e., “human understanding” in Table 4). At this stage, our rules can give some hints about how the model judges the anomalies by the violation of rules. However, the operator may find that the violated rules are far from the important features for an attack. It means there is an inconsistency between model decision logic and expert knowledge. In many cases, as mentioned in [b], it may be due to the underspecification of the model, such as shortcut learning. This indicates the model decisions cannot be trusted, and some efforts to upgrade the model are imperative (e.g., retraining, fine-tuning).\n\n>Have the experiments been carried out multiple times to account for bias?\n\nYes, our experiments are actually done by 5-fold cross-validation. We first randomly split the dataset into 5 folds, and then pick up 3 folds for training, 1 fold for validation and 1 fold for testing (i.e., 6:2:2). With all possibilities of folds selected as training sets, each experiment is conducted by 10 times.\n\n>Can the authors provide convincing evidence of the \"necessity\" of the proposed method in practice?\n\nYes. Due to the word limit, we will answer this question once the discussion phase starts.\n\n>How is the \"robustness\" measured?\n\nFollowing [a], the robustness is defined as the persistence of the *surrogate* model to withstand small perturbations of the input that do not change the prediction of the *original* model”. It is calculated as $\\frac{\\sum_{n=1}^N g(x_n)-g(x_n+\\delta)}{N}$, where $g$ is the surrogate model (extracted rules) and $\\delta$ denotes the small perturbation . In our code, since the features are normalized, $\\delta$ is initially set to 0.01; if the addition of this perturbation changes the prediction of the original model, we will gradually decrease the value of $\\delta$ until it satisfies the condition. It evaluates the fidelity of the rules to the original model when the original model is resistant to perturbations.\n\n>How long would it take to assess the efficacy of the proposed method under varying percentages of \"noisy\" data?\n\nThanks for your suggestion. We are still making efforts on this experiment and aim to finish it within the next few days.\n\n>Does the method require netflow data to work? And, if so, how would the resulting performance change if the flows are generated in a different way?\n\nYes, netflow data contained in the considered datasets are used. We acknowledge that various flow generators exist, which may employ different flow definitions and expiry mechanisms. However, our method itself is not tied to a particular flow generator. As a model interpretation method, the flow data applied by the extracted rules is always consistent with the original anomaly detection model. If the flows are generated in a different way from what the anomaly detection model expects, our rules are also likely to fail since they maintain fidelity to the original model. Thus, we think it may not be very fair to evaluate our rules using a different way of flow generation.\n\nAgain, thank you for your comments. Due to the word limit, we will give more detailed feedback to answer other mentioned issues once the discussion phase starts!\n\n[a] Vilone, G. et al., A comparative analysis of rule-based, model-agnostic methods for explainable artificial intelligence, ICAC 2020\n\n[b] A. S. Jacobs et al., Ai/ml for network security: The emperor has no clothes, CCS 2022"}, {"review_id": "uh8BLZhnO1", "reviewer": "Reviewer_jw73", "summary": "This paper proposes a rule-set extraction method for a black-box anomaly detection model that is trained with only normal or unlabeled data.\nThere are many methods to interpret the learned model, but, this paper claims that there are few methods designed for anomaly detection.\nThe proposed method first extracts rules that decompose the complex distribution of normal data into multiple simple distributions and then, in each simple distribution, the decision rules that approximate the decision boundary of the pre-trained model are estimated. \nBy merging such rules, the proposed method can obtain a surrogate rule-based model of the trained anomaly detector.\n", "questions": "- This method is proposed as security-specific, but if I understand correctly, there is no security-specific part of the model. Is it better to present it as a more generic method since there are other areas of industry where rule sets are required?\n- The proposed method is mostly feature-by-feature processing, so can it be used for high dimensional data as well? The datasets with small feature sizes (30) were used in the experiments. Some discussion of the computational cost would be required.\n- Does Proposition 2 claim that the probabilities of the samples belonging to the same distribution $D_k$ are similar? If so, I think that the assumption is not satisfied, e.g., if $D$ is a Gaussian mixture distribution (i.e., $D_k$ is each Gaussian component). Please let me know if I have misunderstood.\n- In Eq. (4), although $I(N_l)$ and $I(N_r)$ depend on $N_l$ and $N_r$, it is unclear how $N_l$ and $N_r$ are used for caluculating the value of $I$. I also did not understand why the output of anomaly detection could be used to partition the distribution in Eq. (4).\n- In Eq. (8), It reads as the sum of a vector and scalar. Is the second term a vector?\n\nMinors\n- In section 1, this paper mentions one reason for using global explanatory methods is that forecasts are interpretable. However, I think that this property also be achieved by local explanation methods.\n- It is better to explain the meaning of each loss of Eq. (2) in Section 2.\n- In definition 3, $\\phi_k$ is not defined.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The problem tackled in this paper is important. There is a demand for interpretable anomaly detection in many industries, including security.\n- The proposed method is model-agnostic and thus can be applied in many applications.\n- The proposed method works well in the experiments.", "weaknesses": "- There is no discussion or comparison regarding computational costs.\n- There are several unclear points about the methodology. This may be because I am a non-expert in this area (rule-based methods). I would like to wait for the author's additional explanation in the rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer jw73 for the detailed and constructive review. We will address all the expository comments in the final version of the paper. \n\n**Major clarification.**\n\n>Is it better to present it as a more generic method since there are other areas of industry where rule sets are required?\n\nThanks for your comment, which we believe is constructive. Though we are not experts in other areas of industry, we do think our method can be applied to other areas that need rule-based decisions, as long as their data formats are tabular data where each column has explicit semantics. As we are more familiar with security applications that urgently need model interpretation, we use this as our starting point. Following your suggestions, we will add some examples of potential applications in other areas in the final paper and may conduct experiments in other areas in future work.\n\n>Can it be used for high-dimensional data as well?\n\nYes. We have added a runtime experiment with different dimensions of data. Please refer to the global response.\n\n>Does Proposition 2 claim that the probabilities of the samples belonging to the same distribution Dk are similar?\n\nWe are afraid that you may have misunderstood. This proposition actually states that if two data samples belong to the same compositional distribution $D_k$, the probability that they belong to the overall distribution of normal data ($D$) will not differ very much. Recall our definition of compositional distribution in Definition 3, the probability that a sample belonging to the compositional distribution $D_k$ belongs to other distributions is significantly small. As the probability of the overall distribution is equal to the weighted sum of the probability of each compositional distribution (also given in Definition 3), the sum of several values is close to 0 and $P_{X\\sim D_k}(x)$ is still close to $P_{X\\sim D_k}(x)$, which will not differ much for the two data samples belonging to $D_k$. This is indeed a bit similar to GMM as you mentioned, provided that different Gaussian components do not overlap with each other significantly.\n\n>It is unclear how $N_l$ and $N_r$ are used for calculating the value of $I$.\n\nSimilar to CART decision trees, here $I$ is a criterion function to represent data impurity. We take the Gini index as an example: $I=2p(1-p)$, where $p$ originally is the probability of being normal for binary classification. In CART, this probability is estimated by the frequency of normal samples by counting their labels, i.e., $p_{N}=|\\{ y\\in N;y=0 \\}| /|N|$. With the absence of labels in our scenario, we propose to use average output of anomaly detection to estimate this probability, as described in Eq. (5). For example, for $N_l$, the complete process of calculating $I(N_l)$ is: $ I(N_l)=2p_{N_l}(1-p_{N_l})$, where $p_{N_l}=\\frac{1}{|N_l|}\\sum_{x\\in N_l}f(x)$.\n\n>I also did not understand why the output of anomaly detection could be used to partition the distribution in Eq. (4).\n\nThe intuition behind our approach is that the original model is well-trained to understand the distribution of normal data well, and thus can output similar values for data from the same distribution. This intuition is a bit similar to knowledge distillation where the original model serves as a teacher. We let the output of the original model guide our partition of the data, and our goal is to find a partition of the space so that data points with similar output values from the original model are enclosed into one subspace.\n\n>In Eq. (8), It reads as the sum of a vector and scalar. Is the second term a vector?\n\nYes, the second term should be a vector, or the first term should be the i-th dimension of the explorers. Since we used the i-th dimension as an example in the entire Section 5, when writing Eq. (8), we initially wanted to focus on the calculation of the i-th dimension, so Eq. (8) was written in the current form, which can be somewhat confusing. Thanks for your correction and we will modify it in the paper!\n\n**Minor clarification.**\n\n>I think that this property also be achieved by local explanation methods.\n\nIndeed, local explanation methods can certainly interpret one decision at a time. However, as mentioned in [a], local methods limit their attention to only a subset of individual decisions; they are prone to providing misleading explanations depending on the subset of samples analyzed, which may not be the best option for high-state applications like security. \nBesides, we also argue that global methods are better for achieving efficient online defense, as the extracted rules can be easily integrated with the majority of defense tools using rule-based expressions (e.g., iptables).\n\n[a] A. S. Jacobs, R. Beltiukov, W. Willinger, R. A. Ferreira, A. Gupta, and L. Z. Granville, “Ai/ml for network security: The emperor has no clothes,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2022.\n\n>It is better to explain the meaning of each loss of Eq. (2) in Section 2.\n\nThanks for the suggestion. The two terms in Eq. (2) describe the fidelity of the extraction rule to the original model on normal data (i.e., $L_{X\\sim D}(C,f,\\varphi)$) and abnormal data (i.e., $L_{X\\nsim D}(C,f,\\varphi)$) respectively. Here $L(\\cdot)$ can be any loss function suitable for binary scenarios, such as binary cross entropy. We will add more explanations in the paper for clarification.\n\n>In definition 3, $\\phi_k$ is not defined.\n\nThanks for your reminder. $\\phi_k$ denotes the weight of each compositional distribution, and the overall distribution is obtained by the weighted sum of the compositional distributions. \n\nAgain, thank you for your comments, and we hope that this addresses your concerns!"}]

Author rebuttal:
We thank the reviewers for their careful reading and detailed and considerate feedback.

We are glad that reviewers agree that our paper tackles an important problem (“an important problem domain” by mhUf, “tackles an open research problem” by AbmJ, “problem tackled in this paper is important” by jw73) and the proposed method demonstrates good experimental results (“outperform existing ones” by eS8h, “show improvement over baselines” by AbmJ, “works well in the experiments” by jw73). 

The reviewers also mentioned that computational cost studies are necessary, and evaluation on other datasets would make the paper stronger. We are happy to report that we have conducted the majority of the suggested experiments (see attachments).

**Additional dataset.**
We have conducted additional experiments on an additional dataset (recommended by Reviewer AbmJ), which is an improved version of CIC-IDS dataset that we use in the paper. It consists of 80 features. Some of the flaws in the original CIC-IDS dataset are fixed (e.g., more accurate labeling), following the suggestions of Reviewer AbmJ. The average AUC scores of the four anomaly detection models on this dataset are as follow:

|AE|VAE|OCSVM|iForest|
|-|-|-|-|
|0.9906|0.9767|0.9901|0.9734|

As Table 1 in the attachment shows, our method still achieves the highest fidelity and TPR, for all anomaly detection models. Besides, our method also preserves a high level of robustness and TNR. The results indicate that our method can obtain rules of high quality from different black-box unsupervised anomaly detection models using only unlabeled one-class data.

**Computational cost.**
As suggested by reviewers, the discussions of computational costs and runtime performance are necessary to demonstrate the usability of the method, especially when the dimension of features is higher than the current feature numbers. Therefore, we add an experiment to measure the training time and prediction time. Since the improved CIC-IDS dataset has 80 features in total, we train the model using the first N features of 4000 samples, where N is set to 20, 40, 60, and 80. The results are shown in Table 2, which demonstrate the average training and prediction time of our method. It can be seen that the training time is around 1 minute, which is acceptable and practical for large-scale training. Besides, the training time increases basically linearly with the increase of feature numbers. This is because our method adopts a feature-by-feature strategy to explore the decision boundary of the model. For prediction time, our method is highly efficient, which only costs microsecond-level overhead for one inference. It shows that as a rule-based approach, our method can achieve real-time inference for online use.

We also compare the runtime performance to the baselines using the same data of 40 features, as shown in Table 3. We find that the training time of our method is basically at the same level as other methods. For prediction time, since all methods are rule-based, their execution is all at microsecond level, except for LIME which requires additional sampling for each inference. Note that the execution of our method is purely based on Python.  It is not yet optimized by C++ or Cython (as Trustee does). In practice, the prediction time of our method can be even higher with more efficient code implementation.

We also theoretically analyze the time complexity of our algorithms. For training process, the time complexity of the IC-Tree is identical to a CART: $O(d\cdot n\log n)$, where $d$ is the feature number and $n$ is the sample number; the time complexity of the CBE algorithm is $O(K\cdot d\cdot N_e\cdot N_s)$, where $K$ is the number of leaf nodes of the IC-Tree, $N_e$ and $N_s$ are the number of initial explorers and auxiliary explorers, respectively. Therefore, the training time is theoretically linear to the feature number, which is in line with the empirical results. For execution, the time complexity is $O(|C|\cdot d)$, where $|C|$ is the number of extracted rules. 

Again, thank you for your comments, and we hope that this addresses your concerns! If you still have any questions or concerns, we are very willing to answer your questions or add other experiments during the discussion phase!

Meta-review: This paper tackled an important question, explaining the decisions of complex anomaly detectors in a human-understandable way. The presented approach excited a deep discussion with reviewers and was able to convince even an initially very skeptical reviewer. As all reviewers eventually recommended the acceptance of this paper, the AC recommends acceptance.
Decision: Accept (poster)