Metis: Understanding and Enhancing In-Network Regular Expressions
Authors: Zhengxin Zhang
Yucheng Huang
Guanglin Duan
Qing Li
Dan Zhao
Yong Jiang
Lianbo Ma
Xi Xiao
Hengyang Xu
Venue: NeurIPS 2023 poster (2023)
Keywords: Network Security; Regular Expression; Knowledge Distillation; Machine Learning; Programmable Switch
TL;DR: We propose a novel solution to deploy REs on network devices efficiently.

Abstract: Regular expressions (REs) offer one-shot solutions for many networking tasks, e.g., network intrusion detection. However, REs purely rely on expert knowledge and cannot utilize labeled data for better accuracy. Today, neural networks (NNs) have shown superior accuracy and flexibility, thanks to their ability to learn from rich labeled data. Nevertheless, NNs are often incompetent in cold-start scenarios and too complex for deployment on network devices. In this paper, we propose Metis, a general framework that converts REs to network device affordable models for superior accuracy and throughput by taking advantage of REs' expert knowledge and NNs' learning ability. In Metis, we convert REs to byte-level recurrent neural networks (BRNNs) without training. The BRNNs preserve expert knowledge from REs and offer adequate accuracy in cold-start scenarios. When rich labeled data is available, the performance of BRNNs can be improved by training. Furthermore, we design a semi-supervised knowledge distillation to transform the BRNNs into pooling soft random forests (PSRFs) that can be deployed on network devices. To the best of our knowledge, this is the first method to employ model inference as an alternative to RE matching in network scenarios. We collect network traffic data on our campus for three weeks and evaluate Metis on them. Experimental results show that Metis is more accurate than original REs and other baselines, achieving superior throughput when deployed on network devices.

Metis: Understanding and Enhancing In-Network Regular Expressions
Zhengxin &h Ei Yucheng Huang "Ri, Gunaglin Duan *8t Qing Liti, Dan Zhao
Yong Jiang', Lianbo Ma', Xi Xiao Hengyang Xu Tsinghua University, *Peng Cheng Laboratory, Northeastern University Tsinghua Shenzhen International Graduate School, Tencent zhang-22 chang-zx211 @mails. tsinghua. edu.
Abstract
Regular expressions (REs) offer one-shot solutions for many networking tasks, e.g., network intrusion detection. However, REs purely rely on expert knowledge and cannot learn from massive ubiquitous network data for automatic management. Today, neural networks (NNs) have shown superior accuracy and flexibility, thanks to their ability to learn from rich labeled data. Nevertheless, NNs are often incom- petent in cold-start scenarios and too complex for deployment on network devices. In this paper, we propose Metis, a general framework that converts REs to network device affordable models for superior accuracy and throughput by taking advantage of REs" expert knowledge and NNs' learning ability. In Metis, we convert REs to byte-level recurrent neural networks (BRNNs) without training. The BRNNs preserve expert knowledge from REs and offer adequate accuracy in cold-start scenarios. When rich labeled data is available, the performance of BRNNs can be improved by training. Furthermore, distillation to transform the BRNNs into pooling soft random forests (PSRFs) that can be deployed center for three weeks and evaluate Metis on them. Experimental results show that Metis is more accurate than original REs and other baselines, achieving superior throughput when deployed on network devices.
design semi semi-supent supervised knowledge
network devices. We collect network traffic data on a large data
1 Introduction
Symbolic rules indispensable and widely used in network scenarios (Wang & Zhang 2021). As one of the most representative forms of symbolic rules, regular expressions (REs) are long- eatg--ssablsshed in natural language processing (NLP) and network tasks, e.g. pattern matching (Hosoya & Pierce Zhang & He| 2018). network measurement and anomaly detection (Kumar & Dharmapurikar
2001:
2006 Sherry & Lan 2015 Hypolite al. 2020). RE-based systems constructed based on expert
knowledge and do not require labeled data for training. Therefore, RE-based systems are well-suited RE-based systems are also obvious. First, RE-based systems rely on experts to construct and update, making them hard to maintain. Second, RE-based systems cannot learn from labeled data, which usually contains underlying implications of the concerned problems beyond experts' subjective perception. Meanwhile, by exploiting labeled training data, many neural networks (NNs) models outperform RE-based systems on various tasks. For example, NNs achieve higher accuracies than RE-based systems in network intrusion detection (Fu al. 2021) and application classification Yu al. 2020). However, many network scenarios,
for zero-shot scenarios. However, the disadvantages
"Equal contribution. Corresponding author: Qing Li (liq @ @pc.acccc)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

obtaining labeled data is challenging (Mirsky et al. 2018 Li et al. 2022), and the computational capabilities of network devices are limited, making it difficult to deploy NNs.
Recently, Diang & Zhao (2020) tries to combine the advantages of symbolic rules and neural networks. They transform multi-string matching patterns into trainable recurrent neural network (RNN), which can benefit from the high accuracy of RNN while being deployable in cold-start scenarios. However, multi-string matching patterns can only match simple strings, which is not sufficient to represent complex text patterns. Regular expression matching is a more versatile tool than multi-string matching for matching complex text patterns, thanks to the representation capacity offered by its syntaxes such as Kleene star (e.g., "*'), counting constraint (e.g.. "(N, M)"), character class (e.g.. "[a-fA-FO 90-99,, and hexadecimal numbers (e.g.. "Ixff"). As such. jointly exploiting the advantages of REs and NNs offers new opportunities for network device affordable solutions with high accuracy and throughput. Nevertheless, two challenges need to be addressed to achieve this high-level goal: 1) how to preserve expert knowledge from REs and develop learning models with adequate accuracy in cold-start scenarios; and 2) how to produce learning models that fit the network devices while retaining good performance. Since network devices have limited computation and memory resources, deploying complex learning models transformed from regular expressions, e.g., NNs, in these devices is often difficult or even impossible.
In this paper, we propose Metis]] an intelligent and general framework that converts RE-based systems into learning models, which offer superior accuracy and throughput when deployed on network devices. Our codes are available at Githut Metis preserves expert knowledge in RE-based systems for adequate cold-start performance and exploits NNs' ability to further improve performance using rich labeled data. First, we extract bytes from network packets as input features and construct byte-level deterministic finite-state automata (DFAs) from network rules, i.e., REs. Second, the DFAS are transformed into byte-level RNNs (BRNNs). Without training data, the BRNNs preserve the accuracy of RE-based systems for adequate performance in cold-start scenarios. When enough labeled data is collected, BRNNs' performance can be further improved by training with data. Third, we train pooling soft random forests (PSRF)) under the instruction of BRNNs using semi-supervised knowledge distillation (SSKD). Through the SSKD, we transfer the superior learning capability of BRNNs to PSRFs, which can be easily deployed on network devices for line-speed processing, i.c., 100 Gbps. To the best of our knowledge, this is the first method to explore the use of model inference as alternative to RE matching in network scenarios. The key contributions of this paper are as follows: 1) We propose Metis, an intelligent general framework that converts RE-based systems to learning models deployable network devices. 2) We develop method for converting complex REs into DFA and subsequently into trainable BRNNS. This method allows us to maintain the accuracy of the RE-based system while leveraging the flexibility and capabilities of NNs. 3) We propose a novel semi-supervised distillation algorithm SSKD, and a student model PSRF for RE matching to achieve lightweight deployment of RE- based systems in network devices. 4) We collect network traffic data from a large data center for three weeks that reflects real network conditions. Experiments on the datasets demonstrate that Metis outperforms original RE-based systems and other baselines.
2 Related Work
In this section, we introduce the network rules and modern network devices, highlight the problems of the state-of-the-art in these fields, and discuss the opportunities provided by knowledge distillation.
Network rules. Network rules serve as a fundamental building block for many network security applications, e.g., network intrusion systems (Roesch) 1999 Project (022). application identification
systems (ntop 2022), web firewalls (Trustwave 2022) and some network censorship systems (Hoang & Niaki 2021 ). REs are one of the most representative and useful forms of network rules. In many network security applications, such as Snort (Roesch) 1999) and Suricata (Foundation) 2022). REs are used to inspect whether the payload of packet matches any predefined network rules. With high interpretability and no requirement for training phase, RE-based systems can be quickly deployed with decent performance in network scenarios. However, the matching speed of regular expressions usually becomes a bottleneck since the pattern matching has to inspect every byte of a packet against
Metis is a goddess of wisdom in Greek mythology. httpss//iiiibboooooooooouucscstt
2

---

set of rules Wang & Zhang (202T). Moreover, RE-based systems cannot boost their accuracy by training on labeled data and thus often underperform learning-basd based models in data-rich scenarios.
Machine learning in-network. Learning algorithms, especially deep learning ones, have been employed in the network field to leverage their superior learning abilities, e.g., network traffic classification (Barradas & Santos 2021). malicious traffic detection (Fu & Li, (021) and flow size prediction (Poupart Chen 2016). As the network bandwidth grows dramatically, it has been increasingly difficult for network applications to keep up with the high traffic volume (Cisco 2021). Unfortunately, existing model-basee systems are unable to process aightthrouhhpu traffic, due to their processing overhead. Although deploying more servers could achieve higher throughput, doing so would increase the capital costs drastically, which is not symmetric to the rapid growth of network bandwidth and network traffic nowadays.
Modern commodity network hardware devices, e-g., programmable switches (PS) (Barefoot Networks 2021 Yang et al., 2022) and smart network interface card (NIC) (Lin et al. 2020 provide hardware programmability. They have comparable power consumption and capital costs as traditional fixed- function network devices, which enables orders of magnitude cost reduction compared to commodity CPU or other hardware alternatives (e.g., GPU and FPGA). However, as programmable network devices only come with limited computational and memory resources, deploying learning models directly on them often infeasible.
Knowledge distillation. Knowledge distillation (KD) is widely adopted in model compression, transferring the knowledge of unwieldy teacher model, which is hard to deploy on resource- constrained devices, into a lightweight student model (Gou et al. 2021). According to the definition
of knowledge, existing KD methods be classified into three types: response- based KD (Hinton
et al. 2015, Chen et al. 2017). feature-based KD (Romero et al. 2014; Chen & Mei 2021). and
relation-based KD (Yim et al. 2017). Response-based KD methods have been applied network scenarios since they support training a student model with a different structure from a teacher model to adapt to network devices. The main idea of the response- based KD is let the student model mimic the prediction of the teacher model. Frosst & Hinton (2017) propose a soft decision tree that is transformed from NNs using response- baseed-bbdddeeee KD. Xie et al. (2022) propose Mousika that leverages the response- bassed based KD methods to convert the deep learning models into decision trees, and extract the flow table entries for direct deployment on programmable switches. This opens up new horizons for bringing learning models into network devices. However, existing KD response-based methods rely on abundant labeled data, which not available in network scenarios.
3 Metis
Rule2DFA POR-- COR.-.......
DFA2BRNN MAW.............................
BRNN2PSRF
Reguler Expression
Soft Label
Hard Label
Rules Sets
RE
BRNN (Trained)
10-170
0:00ico 4F
Num Labe
Num Label
100
chat
p2p
Vi
W
thp
DFA Extractor
3 chat
else
Pooling
30-11
30-31
50
4F
3d
35 4F
2A
36 10
22
Labeled Dataset
Training
SSKD
OC
Online
5
BRNN (Cald Start)
PSRF.
Offline
Tbm224220
Network Packets
I1b0101011125
D4
Al
Figure 1: Metis framework.
3

---

In this section, we describe the Metis framework as shown in Figure ! first process the network traffic and construct DFAs with bytes from network rules. Then, we convert DFAs into BRNNs. Finally, we propose SSKD to train our PSRF under the instruction of BRNN. For the online inference, we deploy the PSRF on network devices to process traffic in line-speed.
For the offline training, we
3.1 Rule to DFA
In the field of NLP, the input is usually natural language text. Often, the input text is naturally tok- enized by word delimiters, e.g., spaces in English text. Then, by using pre-trained word embeddings, dimension reduction can be easily conducted on features extracted from the tokenized text. However, the inputs in network scenarios are bit streams extracted from packets of network traffic.
In Metis, we utilize byte-level tokenization for network bit streams and network rules, The benefits of byte-level tokenization are two-fold. First, we can reduce the input vocabulary size to 2 256. Second, byte-level tokenization facilitates the deployment of the final PSRF in network devices since network devices typically process packets in bytes. For the incoming bit streams, we divide them into bytes and then convert bytes to hexadecimal numbers.
Network security applications, e.g., Snort (Roesch 1999) and Suricata (Foundation) 2022), usually adopt Perl-compatible regular expression syntax (PCRE) (Philip Hazel 2022) to construct network rules. PCRE includes more representative features than REs, such as counting constraints, character classes, and hexadecimal numbers. The syntaxes supported in this paper are shown in Appendix A Note that (Jiang & Zhao, 2020) only supports the first five syntaxes. Taking "(222cvv'' x23[00 9 {3, ")", ". a simple rule in Snort to identify policy, as an example. Hexadecimal numbers will only bit stream. So we first convert the rule to ". \,266cv' x33 9] [3.44..", where '.' is the wildcard that can match any character. 's' the Kleene star operator match the preceding subexpression zero or more times. Characters inside the brackets (e.g., "[0 - 9]") form a character class module which ORs the characters included in character class. To make the rule consistent with the input data format (i.e., bytes), we convert each character in the rule except character classes, wildcard, and counting constraint operators into its corresponding ASCII code, using only one byte per character. So the final converted rule is * 0x26 0z63 76 7. 0z3d [0- [3 4}
appear after "²,=". Note that this rule can appear anywhere
Next, we construct deterministic finite-state automata (DFA) for the converted rules. Finite-state au- tomata (FA) are mathematical models of computation characterizing transitions among a finite number of states. An RE can be converted into an FA using Thompson's 's construction algorithm (Thompson 1968). We can construct a unique FA with minimum number of states and deterministic transitions (DFA) for an RE by the DFA construction algorithm (Rabin & Scott, 1959) and DFA minimization algorithm (Hopcroft 1971). Formally, a DFA is defined as 5-tuple A = (E, S, T, ao, Qoo)), whose el- ements are defined as: Σx the input vocabulary. In the byte-level input process, [Σ] ===V== 2 = 256; S: finite set of states. [S] K; T E IR V Kx xK, transition weights. T(o, 8;, sy] is the weight of transferring S; to 8, according to the input a. In DFA, To 8t, sy] is 1 indicates s; can transfer to 8j otherwise O; ogg E RRK initial weights of S. anli] is the initial weight of 8; when time / = 0: O:s0 E R final weights of S. [1) is the final weight of 8 after reading the whole input. Consider an input sequence X = {x1, ..., .NN and path p [uI, u2,..., UN+1). where u; is the index of state considering x;. The score B(A.p) of path p is defined as
V
N
B(A,p) = ao [ur]
T [eo ui Masal) ax (uN41]-
Let (A') be the set of all possible paths starting from So and ending at Soo, where Sn is the set of start states and Sx is the set of final states. The sum of path scores, B X'), can be computed by the Forward algorithm Baum & Petrie (1666):
N [IT(())
Biw (A,
Σ B(A,p) a. (2T(
mi)) a..0
As mentioned above, we can build DFA using the converted rules. Note that transitions in our DFA consist of bytes. To construct the DFA more concisely, when constructing the transformation matrix, we treat wildcards and character classes special words in the input vocabulary for quick processing.

---

3.2 DFA to BRNN
Our DFA parameterized by θ =< T, ou, aso >. Let h4 E R be the forward score considering the first words {I1, F2, ... Fe) of X. We rewrite the forward score into a recurrent form:
T ha ao,
(3)
h h4-1 T [my] IStSN,
(4)
Bi (A, = hx -lzo.
(5)
Here, we treat matching on RE as a binary classification task. which can suit most network applica- tions. To this end, we expand Br (A, (') to vector [1, 0J when (A, X¹) is O, and [0, 1] otherwise. can be easily generalized to multi-classification tasks as well. Recall that the calculation of the hidden states in the forward propagation of the RNN is formulated by h2 a (Un² Wh b). where a is the activation function. When U = 0, b 0. W = T, and a is the identity function, the forward score caleulation of DFA (E.q. + is similar to the forward propagation of RNN. Therefore, we convert the DFA with byte-format transitions into an RNN with θ called BRNN. In practice, fine-grained classification may be desired, which considers the different combinations of final states, i.e., different terminal state combinations correspond to different output categories. In this case, we can use MLP after BRNN the aggregation layer. The BRNN converted from DFA can retain the performance of the original RE and be put into production immediately without waiting for data collection. When enough labeled data is collected, the performance of the BRNN can be further improved through training.
3.3 BRNN to PSRF
The BRNN is often difficult to deploy on network devices directly. To promote easy deployment on network devices, we further convert BRNN into pooling soft random forest (PSRF) using semi- supervised knowledge distillation (SSKD).
Existing knowledge distillation approaches (c.g.. Mousika) face two major problems when applied in network scenarios. First, labeled data only accounts for very small proportion of the massive network traffic. It is challenging to distill student model with high accuracy in such data-scarce scenarios. Second, due to the limited computation resources, memory, and supported operations of network devices, there are stringent restrictions on the selection of student models. Specifically, only tree-based models (e.g., the decision tree and the random forest) can be deployed. However, tree-based models are not suitable for unaligned and sequential features (payloads of network packets), making network tasks challenging, such as RE matching.
In Metis, we propose SSKD and PSRF, which overcome the Above-mentionee problems with two key ideas. First, we introduce the semi-supervised learning strategy into the knowledge distillation. Attributing to the cold-start characteristic of our BRNN, the BRNN can effectively preserve the expert knowledge from the RE-based system and hence offers adequate accuracy without training data. As a result, we jointly utilize the ground truth of labeled data and inference results of BRNN on both labeled and unlabeled data to train the student model. Second, we select the PSRF as the student model instead of the soft decision tree. To exploit the context information within the sequence features, we introduce the pooling operation before training. Since the matched pattern in payloads may shift, leveraging context information can alleviate overfitting and boost accuracy.
SSKD aims to train the PSRF, consisting of several pooling soft trees (PST). The training phase of SSKD includes three steps. First, we perform times of sampling with a replacement on all data (including both labeled data and unlabeled data) to obtain sample set U = {U1, U2, Uz...., U.}. where U. = {(11 31), (I22, y2)...., (In, ), i 1,... ,t. is the sample subset for the i-th tree, is the number of trees in the random forest. Note that for labeled samples, y (1, or y (0. 1). and for unlabeled samples y = (-1.- 1).. Although SSKD focuses on the binary classification task in this paper, it can be easily generalized to multi-classification tasks. The input feature is composed of the decimal form of the bytes, i.e. integers ranging from 0 to 255. Second, we calculate the mixed label yi and modify each item's label in the sample subset Um. e.g., (2i, ye) to (#t, whair)) where 0 < m E I. and S S n. Specifically, the mixed label is calculated as
(6) where a a hyperparameter ranging from 0 to 1, hard is the hard label of sample (a tuple including true false), and sost represents the soft label (a tuple composed of BRNN output probability). For
y min = a y hard + (1 a) y
5

---

unlabeled data, y is effectively the output of the BRNN. For labeled data, y ym mixes the ground truth and the output of the BRNN, which helps the student model learn the classification ability of the teacher model. Finally, we use each sample subset S; to train a PST. Our PSRF consists of all the trained PST's and predicts output by majority vote. We can deploy PSRF on network devices by converting rules to general match action table entries.
Before training, we introduce the max pooling operation to leverage the context information. We do not apply mean pooling since mean pooling leads to an increase in feature complexity. We define the window as w and the stride as s. For each incoming feature sequences x = [f1. fz, fs..... fmazlen]. maz(fi+e... (fi+e: fw.s),...l, where f repre- sents the feature of x and mazlen is the maximum length of payload sequences. However, the implementation of pooling operation is non-trivial in network devices due to their lack of support for complex float computing. To implement Metis on network devices, we first extract the packet bytes to the packet header vector through the parser. Then in the ingress pipeline, we use the match-action unit to perform a pooling operation on the packet header vector based on the ALU in parallel. Details of technical work can be referred to the technique report. The training process of each PST is similar to the CART decision tree (Breiman et al. 2017) which utilizes purity to split nodes. The purity after splitting the node via feature A is defined as
the feature sequence is transformed to [maz(fi. ..... f: maz
IDAA D
DA Gini( DA),
P(D, A)
Gimi(Di)) +
D
where D is the sample set of the parent node, and D and D are the sample sets of the left child and right child split by feature A, respectively. The feature with the smallest P(D, A) will be used for node split. Note that different from the calculation method of the Gini index for hard labels, we calculate Gini(D) as
Gini(D) -immnn
0o [D] y2 y- -- )
(8)
[D]
where y y= (²) The detailed training process and end conditions of the PST are consistent with the CART decision tree. We mainly consider two hyperparameters: the number of features to consider when looking for the best split (# split features) and the minimum number of samples required to he at a leaf node (minimum samples). To deploy PSRF on network devices efficiently, we heuristically aggregates table entries into clusters based on the similarity among features represented by table entries so that each cluster only requires more compact table.
4 Experiment
4.1 Experiment Setup
Although there are several existing datasets collecting the real traces, e.g., CAIDA (Caida 2019) and MAWI (Kenjiro Cho 2200)) most of them do not contain the payload of network traffic to protect user privacy, which makes them unsuitable for evaluating Metis. To evaluate Metis in realistic and diverse network scenarios, we collect packet-level traces at gateways of a large data center, which belongs to one of the largest public cloud providers. The data center serves tens of Tbps traffic for customers with diverse cloud access requirements. The collected traces are labeled by the advanced attack detection system and application identification system deployed in the data center. We use 10 minutes of traffic traces collected in different time periods of three weeks. We construct 11 categories of the dataset based on Snort (Roesch) 1999) rules, including "chat", "ftp", "games", "malware", "misc", "netbios", "p2p". "policy". "teinet", "ufpp, and "client". Each category of the dataset consists of set of network rules and 200, 000 labeled data. We label the data 0 if it does not match any of the network rules in this category. Otherwise, we label it as 1. As such, our task is a binary classification task. We split each category of the dataset into the training set, test set, and validation set with a ratio of 7 2:
Dataset.
Baselines. For DFA2BRNN, we compare it with LSTM (Hochreiter & Schmidhuber 1997), a 4-yayer CNN (Kim 2014) and a 4-layer DAN (lyyer & Manjunatha 2015) which are widely applied text classification. For BRNN2PSRF, we compare it with a CART decision tree (DT) (Breiman et al.) 2017), a random forest (RF) (Breiman) (00T). a hard DT, a hard RF, and soft random forest (SRF). We use BRNN to tag unlabeled data and combine them with the ground truth to train models which

---

are called Hard DT and Hard RF. Compared to PSRF, SRF does not include the pooling operation to verify the pooling effect.
Implementation. We conduct our experiments on a server with two 16-core CPUs (Intel(R) (R) Gold 5218 CPU @ 2.30GHz), 64GB DRAM memory, and six GeForce RTX 2080 SUPER GPUs. For DFA2BRNN, we set the learning rate to 10 batch size to 500, and hidden state to 200 for each model. We use the cross-entropy loss as the objective function. We train each model for 200 epochs and use early stopping to avoid overfitting. For BRNN2PSRE, we set f to 7, a to 0.3, # split features to and minimum samples to 15. We run each experiment under three different random seeds and report the standard deviation. We implement our PSRF hardware prototype based on Tofino switch using the P4 language. The P4 code compiled by Barefoot P4 Studio Software Development Environment We use the traffic generator KEYSIGHT XGSI2 12- to generate high-speed traffic. We enable the Intel DPDK library on the server for high-performant traffic replay.
Ethical considerations. All data analysis had been approved by our cooperation units. We did not investigate human behavior, surface or any individual flows or IP addresses, nor store any traffic or individual records to disk. To protect user privacy, all packets in the collected traces are anonymized. We restricted all analysis network statistics directly output by Metis. We only collected the mirrored traffic to avoid impacting network users.
4.2 Main Results
Table I: DFA2BRNN main results on classification accuracy. Note that # TD is the number of training data for simplicity.
Method
TD
chat
App
games
malware
mise
netbios
p2p
policy
tolnct
t0p
clicat
averaae
RE
85,3
$3.2
91.7
$7.1
81.8
$4.9
36.6
87.2
84.1
84.6
83,1
85.4
0%
55.6205
52.0.04
49.62a5
57.0g0
50.3.0.
5000.00
49.8
52.5
53
49
$4.9...
52.3
1STM
10%
15%
92.9
88.5 6.4
96.4
51.6 13
91.3.a4
88.1 18.
96
92.0.0.
90.5 6.5
96.5-08
95.0gas
89.8 833
64
86.0.05
91
86.2 6.4
98
90.2
98.3255
82.8 6.5
88.8
84.8
93.8
100%
98.8
95.5.60
98.7
98.6.08
98.7_6.
98.5
97.9
98.3_66
98.7
97.5 98.7
98.5
0%
5000
52.1.6s
49.7
49.7 49.7.05
49.9..5
49.9
49.0
502_..7
53.211
50.1
49.9_c.
50.4
CNN
10%
1%
96.1
88.7 16.5
96.6.4.
96.1 20.4
92.8.633
95 95.6g.8
95.7 95.726
90.9
95.9
96.2_6.
94.7 6.1
94.3 94.3g88
80.5 60.
9188.63
93.7
95.1
92.7 0.4
98.7
96.8 96.8209
95. 16.
95.6ga5
94. 1 |c.5
95.5
93.0
100%
98.9
99.0_..1
98.9
98.9
98.9 _..
96.9.8
98.8_03
98.8
99.0ga.
98.9
98.8
98.7
0%
50.4
29.8
48.7
509 49.6
50.2
51.0gna
49.9..7
51:2
g0.5
_0.1_e.
50.2
DAN
10%
1%
72.7
74.0 3.6
$4.0 2.0
76.5.s.7
13.1
53.3
72.2
67.0 4
$7.0=6.
82.3 6.6
$0.2
78.8
53.4.0
80.3
$0.4
72.7 1.6
88.1
13.1
77.7u24
71.3
52.8 4.3
64.0
64.8
75.7
100%
88.2
a..
83.7
86.3_6.
81.6.88
80.7
84.5_6.
90.6ga.
73.7_tm 2..
82.7
0%
85.3gna
83:2.oe
91.7aaa
87.1gn
81.8.6a
84.9ga
86.6gn
$7.2_6.
$4.1gaa
84.6gan
83.1_e.
85.4
BRNN
10%
1%
98.7 26.7
95.0 6.2
99.4...1
97.7 97.7_6.1
99.0 99.6.a2
96.8
95.3
99.1 99.1
94.2 6.
94.5
98.
97.4 97.4.03
91.1
92.4 0.2
98.7
99.7 99.7
98.8
98.9
90.7ga1
98.6 98.6-6.1
93.4 c..
94.6
98.8
100%
99.8
99.9_..
99.9
99.7
99.8
99.8
99.8
99.8
99.9.am
99.8
99.9_..1
99.8
As shown in Table I for DFA2RNN, we compare BRNN with baseline models trained with 0%. 1%, 10%, 100% training data, and the RE-based system. BRNN achieves the same accuracy of 83.1% ~ 91.7% REs in shot scenarios (i.c., 0% training data). On the contrary, other baselines literally perform random guesses, i.c., only having around 50% accuracies, in zero-shot scenarios. In few-shot scenarios (i.e., 1% and 10% training data), BRNN also demonstrates superior accuracy over baselines. With 1 1% and 10% training data, BRNN is already able to further boost the accuracies over different categories to 90. 70.7% 98.8% and 98.1% ~ 99. 7%, respectively. Among the baselines, DAN performs the worst, only obtaining accuracies of 52.8% 82.3% and 53.3% ~ 88.1% 1% over different categories, when given 1% and 10% training data, respectively. The berf-pero one among the baselines, i.e., CNN, also underperforms our BRNN in most categories, especially with 10% training data. For full training, LSTM and CNN achieve 98% accuracy. DAN only achieves 80% accuracy. BRNN achieves 99.8% accuracy over all categories. In word, BRNN achieves competitive accuracy both in data-scarce and data-rich scenarios, while the bascline models suffer from poor accuracy in data-scarce scenarios. This lays solid foundation for the following SSKD to train better student models.
For BRNN2PSRF, we compare PSRF with baselines trained with 0%. 1% 10%, 100% training data. The results are shown in Table Note that DT and RF can not be trained using SSKD when it comes to zero-shot scenarios. In zero-shot scenarios, SRF degrades to Hard RF due to the lack of soft labels. PSRF improves accuracy compared with SRF thanks to the pooling operation. In few-shot scenarios, semi-supervised based models such Hard DT, Hard RF, SRF, and PSRF demonstrate improved
7

---

Table 2: BRNN2PSRF main results classification accuracy.
Mothod
4TD
chat
Up
games
malware
mise
notbios
pdp
policy
telnet
Upp
clien
averagee
1%
70.3a
7500
75.7a1.
74.0a1.
73.8
77.5
32.7an
61.521a
74.3
33.7an9
67.9
72.7
10%
2077
81.5
K1.S10a
85.7
82.0.0
75.5
82.
20.
27.3
K1.2
100%
91.740.
89.
90.3
89.3,oa
900
88.7.06
84.8,0.5
91,4,4.
88.3,07
86.50n
89.0
1%
77.3 21
K3.0
81.8
820
7033
79.4.07
72.4.00 22.4.0
78.4
RF
10%
86.8
89.8 89.8.00
86.8
87.7 a7.7
87.0
87.5
87.2
81 61.3104
282
86.3
86.3
82.2.0.
86.4
1005
88 Man.
91.1
88.0
40.0
89 49.4
89.0ga
89.0
84.4.0.
90.7.0.
88.0 28.0
83.4
88.5
2
27.1
24.7
020.7
75.
21.7.00.
29.0
25.9
29.4
7800.n.
79.0
Hard DT
10%
1%
Daux
90.3 220.
91 4..
29.0
89.9 a..
88. 28.
80.8
89.0
87.6
a9.9
87.0 27.0
K1.7208
84.9.06
90.5
91.2ac.
88.3 88.32
85,2205
86.4.0.7
83.
87.2
88.9
100%
88. an.
91.720.3
89.5
90.6an
89.3
89.9.0.4
39.0
85.0g0.
91.7a5.4
88.6.077
86.5
89.1
0%
78.88 78.8
77.3
84.9.1.2
80.
81.3
76.5
81.5a1.
a8.2
79.3
Hard
10%
1%
86. 7:
88.1 2
20.0
60.6
26.9
87.9
2uu
Pans
87 840.7
9407
87.8
28.2
2.0.
81. K1.7
K2.7204
29.2.c.4
89.5
87.3
82.5
83,920
86.5
87.6
100%
88.0gn5
80
28
83 8
88.5
28.3
83.0
29.7
87.3
83.8
87.7
0%%
77.3
84.9
80:1 g0.
81.3100
26.3
81.5.00
79
24.6
29.5.0
18.2
79.3
SRF
1%
92.2..0.
94.220.
98.1=8.
94.2
94.9203
93.7ao.
94.5.0.
89.3s04
94,4
90.8a0.
20.5
92.9
10%
91.3au.
24.3
94.0=a4
95.3ans
96.3494
94.6
95.5
92.5auu
95.1es.
91.8-20
92.5
94.5
100%
94.9au.
94 San.
94.2
95. 7
96 96442m2
96.7
96.0 26.0
92.7am
95.1
45.2207
42.6gux
94.7
0%
84.0uu
82 6
9144
86.7.u
81 $1.3
86.2
87.0gu
83.8
84.3
85.1
PSRF
10%
1%
97.7
95.6100
96.420a
98.9
99.2.a.3
96.6
97.6.n1
94.8,0
98.4
96.4207
97.0
94.9
98.8.n
97.0
95.4
93.7207
96.5.4.
24.2.0.
97.2.02
95.5200
96.4
92.6209
97.5
95.2
100%
99.3
g9.5
18.
99.0goa
97.3
19.1
96.8
98.4
98.7
98 98.31013
98.5
accuracy compared to models trained on original labeled data, like DT and RF, highlighting the significance of semi-supervised learning. Additionally, attributing to the pooling operation and soft labels introduced by SSKD, PSRF demonstrates the most exceptional accuracy, with an improvement of 9% ~ 25% over other baselines. Furthermore, when compared to RE-based systems, PSRF shows an improvement of around 8% ~ 17% in accuracy. Even when provided with full training data, PSRF maintains its superiority in terms of accuracy compared to other baselines. Our system can easily identify normal traffic, which comprises over 99% of total traffic because it does not match RE patterns. By analyzing the traffic, the PDF and CDF of matched abnormal packet segment lengths are illustrated in Figure in Appendix|Bi Although our traffic is collected from the real world and sampled over different time periods, we find that the RE patterns in the traffic relatively fixed, and are only a subset of the Snort. This is why the accuracy of the haseline scheme increases rapidly from 0% to 1 %% # training data, but not much from 1% to 100% # training data. For abnormal traffic, PSRF can effectively detect abnormal traffic containing short RE patterns (shorter than 50), which takes up over 95% of abnormal traffic as shown in Figure 5 in Appendix B Though PSRF may struggle with long RE patterns due to both its inherent design Togic and hardware limitation (e.g.. the input length of PSRF cannot exceed 128 bytes, as restricted by the maximum width supported by the switch matching table), such patterns rarely appear and thus has very limited impact: PSRF can still achieve an accuracy higher than 99%. We also show average F1-Scores of DFA2BRNN and BRNN2PSRF with normal/abnormal traffic ratios of 99% % and 50%/50% in Appendix C Besides, we conduct experiments on network intrusion detection using UNB ISCX IDS 2012 2 dataset (Moustafa & Slay] 2015), and the results are shown in Appendix D
4.3 Sensitivity Analysis
Effect of s and w. In Figure 2(a) and 2(b) the accuracy decreases when 8 increases, while the accuracy is stable when w exceeds 2. The increase of significantly reduces the number of features and ignores partial context information, which impairs the accuracy. The change of w is related to the contextual perspective of the feature and slightly affects accuracy. Note that when = 1, the pooling operation does not function effectively, resulting in a significant drop in accuracy. This highlights the importance and effectiveness of the pooling operation. Therefore, we set to 1 and w to 3.
Effect of # split features and minimum samples. As shown in Figure 2(c) when minimum samples rise, the accuracy of PSRF decreases slightly. However, decreasing the minimum samples will increase the depth of the tree, which will affect the speed of inference and may cause overfitting. Therefore, we set the minimum samples to 15. As shown in 2(d) we find that the accuracy grows slightly and then even decreases as # split features grows. The decrease results from overfitting. To improve the training speed and accuracy, we set # split features to 8.
8

---

65
114
100%
++- 66
114
100%)
100
100
95
95-
Accurscy (%)
95
Accuracy
Accuracy
90
85
85
80
80
5
10
15
20
25
30
min samples
(a) Effect of s on accuracy
(b) Effect of w on accuracy
(c) Effect of min samples
100
100
2.0
Accuracy (%)
95
Accuracy (%)
95
entriies (x10*)
1.5
1.0
85
85
0.5
80
10 12
0.0
split features
(d) Effect of # split features
(c) Rffect of on accuracy
(f) Effect of t on # entries
Figure 2: Sensitive analysis on PSRF.
Effect of t. As shown in Figure 2 and 2(f) with the increase of f, the accuracy and the # entries of PSRF also increase. There exists a tradeoff between accuracy and efficiency. Therefore, in our implementation,
set t 9, which maintain both high accuracy and high efficiency.
Effect of a. We conduct experiments on a using PSRF and the results are shown in Figure In the zero-shot scenario, the soft labels are the same the hard labels, thus the accuracy remains the same. For other scenarios, we find that PSRF performs well when a in the range [0.2, 0.4). This because PSRF considers both information inherited in the BRNN and the original label. When is O, PSRF only considers the logits of the BRNN and when a is 1, PSRF mainly considers the original label while ignoring the information in the logits of the BRNN. We found the PSRF performs best when a is around 0.3, so we set a to 0.3 in our experiments.
4.4 Experiment on Network Devices
We first conduct experiments on # entries con- sumed by different student models on pro- grammable switches (PS). As shown in Table # entries in PSRF are less than that in SRF and RF, indicating the lightweightness of the PSRE. Note that columns represent # TD. Although DT achieves fewer # entries compared with SRF, it suffers from poor accuracy illustrated in Table Therefore, PSRF is the best choice for the student model in terms of accuracy and resource efficiency.
Method
0%
1%
10%
100%
DT
410
407
411
RF
2145
2162
2129
SRF PSRF
1973
1834
1756
1694
1640
1513
1538
1474
Table 3: # entries consumed by different student models on PS.
Since network devices have limited computation and memory resources, is difficult to deploy RE- based systems on them directly. To demonstrate the superiority of Metis for processing network traffic practical deployment, we deploy PSRF on PS and compared it with common RE-based systems deployed on CPUs. We use multi-core parallel processing to boost the throughput of RE-based systems. We compare the number (processed) packets per second (PPS) achieved by PSRF on PS and by RE-based systems (with 1, 2, 4, 8, 16, and 32 cores) in Figure show the difference in their throughputs. It is obvious that PSRF deployed on PS achieves significantly higher throughput, which is 74 times that of the RE-based system with 32 cores.

---

98
10"
RE
Throughput (PPS 103)
96
PSRF
Accuracy (%)
10"
92
90
10'
2.45
4.55
86
1.31
10"
0:69
0.2
0.4
1.0
12
16x
Figure 3: Effecc of a accuracy.
Figure 4: Experiment Programmable Switches.
Disscussion
Limitations. 1) Due to the limitation of hardware resources (the maximum width supported by the switch matching table is limited, c.g., 128 bytes), the input length of PSRF cannot exceed 128 bytes. In future work, we will consider using feature compression (such as using an autoencoder) as an attempt to support long REs. Though introduce the pooling operation into device-friendly model PSRF, its ability to model sequence features still has room for improvement (compared to BRNN, PSRF after SSKD drops 2%-3% in accuracy). In future work, will try to other student models, such as binary neural networks, to improve the accuracy. 3) We only test single-phrase RE matching. In practice, some rules may be composed of multi-phrase REs. We implement multi-phase REs by adding aggregation operations on the results of single-phrase RE matching. This will be part of our future work.
Societal impact on AI community. In the Al community, though many amazing NN works have been proposed, NNs only be deployed powerful devices (CPU, GPU), which undoubtedly limits the scope of their practical applications. In many domains, there exist a large number of less-powerful devices, which cannot take advantage of the excellent performance of NNs, including switches, network cards, intelligent gateways, and loT devices. In mainstream large-scale data centers, 80% of the switches have been replaced with programmable switches. However, NNs contain complex foating-poin and nonlinear operations, making it impossible to directly deploy them on programmable switches. Therefore, network community, and security community), so that more devices can take advantage of NN's superior performance improve the quantity of service (QoS), and facilitate people's 's daily lives.
work endeavors bring NNs into wider community (e.g.,
Conclusion
In this paper, we propose Metis, an intelligent and general framework to understand and enhance regular expressions in-network by utilizing learning models. We utilize byte-level tokenization extract RE from network rules and process bit streams of network traffic. Then we design SSKD to transform the BRNNs into PSRFs that can be deployed on network devices to process online network traffic in line-speed. We collect network traffic on large data center for the evaluation of Metis. Experimental results show that Metis more accurate than original REs and other baselines, while also achieving superior throughput when deployed on network devices. We contribute Metis source code and datasets to the Al community to stimulate the following research.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous NeurlPS reviewers for their thorough comments and feedback that helped improve the paper. This work supported by the National Key Research and Development the Major Key Project of PCL under grant
Program of China under grant No. 2022YFB3 No. PCL22033S5-11 and the Shenzhen Key Lab of Software Defined Networking under grant No. ZDSYS201 40509999999,999999999
10

---

References
Barefoot Networks. Tofino switch, 2021.
/ http///...broootttttrrrrrss com/
proouctss/brief-tofff
Barradas, D. and Santos, N. Flowlens: Enabling efficient flow classification for ml-based network security applications. In 28th Annual Network and Distributed System Security Symposium, NDSS 2021, 2021.
Baum, L. E. and Petrie, T. Statistical Inference for Probabilistic Functions of Finite State Markov Chains. The Annals of Mathematical Statistics, 37(6):1554 1563, 1966.
Breiman, L. Random forests. Machine learning, 45(1):5-32, 2001.
Breiman, I.,, Friedman, H., Olshen, R. A., and Stone, J. Classification and regression trees. Routledge, 2017.
Caida. Anonymized 2019 internet traces. http::/www. www.caaaaa.ooooooo http://wwaaaadr.rrr/aaatt/rrrr/r 2019.
Chen, D. and Mei, J.-P. Cross-layer distillation with semantic calibration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7028-7036, 2021.
Chen, G., Choi, W., Yu, X., Han, T., and Chandraker, M. Learning efficient object detection models with knowledge distillation. Advances in neural information processing systems, 30, 2017.
Cisco. High capacity 400g data center networking, 2021. URL //tp://tttts////...b....ooo us/ massooutions data- senter/high capacccyaapppaaaaaaoco < data- hataaaaeettt-eetttoooiiiiiieeee html.
en/
Foundation, O. S. Suricata: Open source ids, 2022. htt///tt/////rrcaaaiiid....
Frosst, N. and Hinton, G. E. Distilling a neural network into a soft decision tree. In Proceedings of the First International Workshop on Comprehensibility and Explanation in Al and ML 2017 co-located with 16th International Conference of the Italian Association for Artificial Intelligence (AI*IA 2017), volume 2071. 2017.
Fu, C. and Li, Q. Realtime robust malicious traffic detection via frequency domain analysis. In CCS '1: 202/ ACM SIGSAC Conference Computer and Communications Security, pp. 3431-3446.
ACM, 2021.
Fu, C.,, Li, Q., Shen, M., and Xu, K. Realtime robust malicious traffic detection via frequency domain analysis. In CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 3431-3446 2021.
Gou, J., Yu, B., Maybank, S. J., and Tao, D. Knowledge distillation: A survey. International Journal of Computer Vision, 129(6) 2021.
Hinton, G. E., Vinyals, O., and Dean, Distilling the knowledge in a neural network. CoRR, abs/1503.00 100.05533,,531, 2015. (ttp:: http://aaiiv..r/abb///eeeee wtt.aa////11....5. 02531
Hoang, N. P. and Niaki, A. A. How great is the great firewall? measuring china's DNS censorship. In Bailey, M. and Greenstadt, R. (eds.), 30th USENIX Security Symposium, USENIX Security 2021, pp. 3381-3399 2021.
Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural Comput., 9()):1335-1780. 1997.
Hopcroft, J. An nlogn algorithm for minimizing states in a finite automaton. In Theory of Machines and Computations, pp. 189-196. Academic Press, 1971.
Hosoya, H. and Pierce, B. C. Regular expression pattern matching for XML. In Conference Record of POPI. 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 67-80. ACM, 2001.

---

Hypolite, J., Sonchack, J., and Hershkop, S. Deepmatch: practical deep packet inspection in the data plane using network processors. In CoNEXT '20: The 16th International Conference on emerging Networking EXperiments and Technologies, pp. 336-350. ACM, 2020.
lyyer, M. and Manjunatha, V. Deep unordered composition rivals syntactic methods for text clas- sification. In Proceedings of the 53rd Anmual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, pp. 1681-1691, 2015.
Jiang, C. and Zhao, Y. Cold-start and interpretability: Turning regular expressions into trainable recurrent neural networks. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, pp. 3193-3207, 2020.
Kenjiro Cho, K. M. Traffic data repository the wide project. In USENIX FREENIX Track, 2000.
Kim, Y. Convolutional neural networks for sentence classification. CoRR, abs/ 408.5882, 2014.
Kumar, S. and Dharmapurikar, S. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In Proceedings of the ACM SIGCOMM 2006 Conference Appli- cations, Technologies, Architectures, and Protocols for Computer Communications, pp. 339-350. ACM, 2006.
Li, R., Li, Q., Huang, Y., Zhang, W., Zhu, P., and Jiang, lotensemble: Detection botnet attacks on internet of things. In Computer ESORICS 2022: 27th European Symposium on Research in Computer Security, Copenhagen, Denmark, September 26-30, 2022, Proceedings, Part II, pp- 569-588. Springer, 2022.
Lin, J., Patel, K., and Stephens, B. E. PANIC: A figh-performance programmable NIC for multi- tenant networks. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2020, pp. 243-259, 2020.
Mirsky, Y., Doitshman, T., Elovici, Y., and Shabtai, A. Kitsune: an ensemble of autoencoders for online network intrusion detection. arXiv preprint 1rXiv:/802.09008 2018.
Moustafa, N. and Slay, J. Unsw-nb15: comprehensive data for network intrusion detection systems (unsw-nb15 network data set). In 2015 military communications and information systems conference (MiICIS), pp. 1-6. IEEE, 2015.
ntop. ndpi, 2022. URL https: www. .topporg/
Philip Hazel. Pere perl compatible regular expressions. http://www.pcre orrg 2022.
Poupart, P. and Chen, Z. Online flow size prediction for improved network routing. In 24th IEEE International Conference on Network Protocols, ICNP 20/6, pp. 1-6, 2016.
Project, T. Z. Zeek, 2022. URL httpss://eekk.... org/
Rabin, M. O. and Scott, D. S. Finite automata and their decision problems. IBM J. Res. Dev., 3(2): 114-125, 1959.
Roesch, M. Snort: Lightweight intrusion detection for networks. Proceedings of the 13th Conference Systems Administration (LISA-99), pp. 229-238. USENIX, 1999.
Romero, A., Ballas, N., Kahou, E., Chassang, A., Gatta, C., and Bengio, Y. Fitnets: Hints for thin deep nets. arXiv preprint arXiv:1412.6550) 2014.
Sherry, J. and Lan, C. Blindbox: Deep packet inspection over encrypted traffic. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, SIGCOMM 2015, pp. 213-226. ACM, 2015.
Thompson, K. Programming techniques: Regular expression search algorithm. Commun. ACM, 11 (6):4194422, jun 1968.
Trustwave. Modsecurity, 2022. URL httph::t////tte httpp:://nossecuritty/
12

---

Wang, S. and Zhang, M. Making multi-string pattern matching scalable and cost eestcefficient with pro- grammable switching asics 40th IEEE Conference on Computer Communications, INFOCOM 2021, pp. 1-10. IEFE, 2021.
Xie, G., Li, Q. Dong, Y., and Duan, G. Mousika: Enable general in-network intelligence in programmable switches by knowledge distillation. In JEEE INFOCOM 2022 IEEE Conference Computer Communications, pp. 1938-1947. IEEE, 2022.
Yang, M., Baban, A., Kugel, V., Libby, J., Mackie, S., Kananda, S. S. R., Wu, C.-H., and Ghobadi, M. Using trio-juniper networks' programmable chipset-for emerging in-network applications. 2022.
Yim, J., Joo, D., Bac, J., and Kim, J. A gift from knowledge distillation: Fast optimization, network minimization and transfer learning. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 33334111, 2017.
Yu, L.., Luo, B., Ma, J., Zhou, Z., and Liu, Q. You are what you broadcast: Identification of mobile and iot devices from (public) wifi, In 29th USENIX Security Symposium, USENIX Security 2020, pp. 55-72, 2020.
Zeng. Y., Gu, H., Wei, W., and Guo, Y. deep full range: deep learning based network encrypted traffic classification and intrusion detection framework. IEEE Access, 7:45182-451901 2019.
Zhang, S. and He, L.. Regular expression guided entity mention mining from noisy web data. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 1991-2000. Association for Computational Linguistics, 2018
13

---

A
PCRE syntaxes supported in our paper
Table 4: PCRE syntaxes supported in this paper.
Syntax
Description
Matches a single character.
a3
CONCAT operation. Matches oz3,
o|8
OR ()) operation. Matches o B.
Kleene (+) star. Matches zero more times.
Wildcard. Matches any character.
0+
PLUS (+) operation. Matches one more times.
Matches only appears beginning of the string.
Matches only appears the ending of the string.
[a [8]
Character class, character class uses OR operation to match a character included character class.
a1,8.63
Range Matching. Matches subexpression / to times.
(13))
AtLeast Matching, Matches a subexpression or more times.
{1})
Exactly Matching. Matches a subexpression 3 times.
/d
Matches any number, equivalent to [0 - 9).
WD
Matches any non non-number
Yar
Matches any letter, equivalent to 2.- Z/.
W
Matches any non-letter.
Matches any non-whitespace character.
Matches any whitespace character.
B
The PDF and CDF of matched abnormal packet segment lengths
0.07
1.0
0.06
0.8
0.05
PDF
0.04
0.6
0.03
0.4
0.02
0.2
0.01
0.00
0.0
50
100
150
200
0
50
100
150
200
Length
Length
(a) PDF
(b) CDF
Figure 5: Matched abnormal packet segment lengths statistics.
C
The average F1-Scores of DFA2BRNN and BRNN2PSRF
Table The average Fl-Sco DFA2BRNN with a ratio of normal/abnormal traffic of 99%/1%.
Method
0%
1%
10%
100%
LSTM
51.04
83.29
91.95
96.84
CNN
48.50
91.81
94.19
97.47
DAN
49.92
63.24
75.06
82.30
BRNN
85.19
94.33
98.42
99.35
Table 5 and Table show the average F1-Scores DFA2BRNN and BRNN2PSRF with ratio of normal/abnormal traffic of 99%/1% %, respectively, Note that columns represent # TD. Our BRNN and
14

---

Table 6: The average FI FI-Scores of BRNN2PSRF ratio of normal/abnormal traffic of 99%/19 9
Method
0%
1%
10%
100%
DT
69.32
78.59
86.10
RF
77.20
84.93
87.41
Hard DT
76.74
85.88
86.30
87.15
Hard RF
77.46
85.79
86.58
87.00
SRF 77.46
90.94
91.12
92.28
PSRF
84.38
94.75
95.90
97.83
PSRF achieve 99.35 and 97.83 FI-Score, respectively. This is because only very small portion of real-world traffic contains long RE patterns. As such, BRNN and PSRF can detect most of the patterns in real-world traffic.
Table 7: The average F1-Scores of DFA2BRNN with ratio of normal/abnormal traffic of 50%/50%.
Method
0%
1%
10%
100%
LSTM
49.73
81.67
90.67
95.12
CNN
50.28
90.55
92.64
95.79
DAN
49.16
62.09
73.84
80.78
BRNN
84.47
94.01
98.30
98.26
Table 8: The average FI-Scores of BRNN2PSRF with a ratio normal/abnormal traffic of 50%/50%
Method
0%
1%
10%
100%
DT RF
68.01
77.12
85.05
75.78
83.56
86.20
Hard DT
75.32
84.11
84.19
85.07
Hard RF
76.22
84.46
85.30
85.63
SRF 76.22
88.31
89.91
91.03
PSRF 83.94
93.22
94.55
97.37
Table 7 and Table 8 show the average Fl-Scores DFA2BRNN and BRNN2PSRF with ratio of normal/abnormal traffic of 50%/50%, respectively. Note that columns represent # TD. We find that our BRNN and PSRF achieve similar F1-Score 98. 26 and 97.37 compared with the results of former experiments, respectively. The reason is that the RE patterns in the real-world traffic are relatively fixed, and are only a subset of the Snort.
D Experiment results on network intrusion detection
Table 9: The accuracy of DFR and PSRF on network intrusion detection.
Method
0%
1%
10%
100%
RE
77.84
77.84
77.84
77.84
DFR
49.62
71.05
81.19
98.71
PSRF
75.96
78.41
83.55
98.37
Table 9 shows the accuracy of DFR (Zeng et al. 2019) and PSRF on network intrusion detection using the UNB ISCX IDS 2012 dataset. Note that columns represent TD. PSRF achieves 77.84% accuracy while DFR only performs random guesses in the zero-shot scenario. In few-shot scenarios, PSRF also demonstrates superior accuracy over DFR. full training, PSRF achieves 98.37% accuracy while DFR 98.7 7 1% accuracy.
15


Reviews:
[{"review_id": "vHi7YHe0Lo", "reviewer": "Reviewer_wpui", "summary": "In this paper, the authors propose a solution to classify network’s paquets that benefits from both human expert knowledge and data-centric deep learning and that can be deployed on edge devices. \nTo this end, the authors implemented a method called « Metis ». First, they take a set of regular expression (RE) rules made by human experts and convert them into a deterministic finite-state automata (DFA) that is then converted to a recurrent neural network (RNN). This RNN doesn’t need to be trained to classify paquets as it keeps the exact same performances as the RE, but the authors show that it can benefit from training data and scale accordingly. Then, in order to deploy the learned classifier on an edge device (smart switches), the authors distill this RNN into a Soft Random Forest that keeps most of the performances of the RNN but that can work on high-frequency networks at a fraction of the cost.\nIn conclusion the authors have 3 claims:\n1. A network’s paquets classification model that works with resource-constrained devices\n2. That get good accuracy with only few/no labels thanks to the RE expert knowledge\n3. That can get better with more labels thanks to the training of the RNN weights", "questions": "Questions and suggestions:\n- What is the impact of \\alpha for the soft labels ? An ablation on the distillation parameter \\alpha seem interesting\n\n- There are multiple datasets online for network payload classification, comparing against previous baselines on one of them would increase the strength of the paper by a great margin (https://www.unb.ca/cic/datasets/ddos-2019.html, https://research.unsw.edu.au/projects/unsw-nb15-dataset, https://pages.cs.wisc.edu/~tbenson/IMC10_Data.html, https://www.unb.ca/cic/datasets/ids.html). \n\n- Can you please add an « AVERAGE » column on table 1 and table 2 for easier comparison ?\n- Please add an explanation or a reference on which method you used to do the DFA -> RNN transformation\n- Can you please add the description of the baseline implementations and hyper-parameters (CNN, LSTM) in the core paper on in the supplementary materials as they are non-obvious\n- Could you please add the number of parameters of each baseline in Table 1 ?\n\nMinor typos:\n- Ref appear two times: « Fu, C., Li, Q., Shen, M., and Xu, K. Realtime robust malicious traffic detection via frequency domain analysis. »\n- Line 65: redundancy between contribution 1) and 2)", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Pros:\n- Clear explanation of the goal\n- Interesting combination of two methods (DFA to RNN and Random Forest distilllation)\n- Experimental setup is well described and code is available\n- « Real world » implementation on edge device with 74x higher throughput against baseline supporting claim #1\n- Good gains going from 0% to 1% labeled data with the proposed method supporting claim #2\n- Good gains going from 1% to 100% labeled data with the proposed method supporting claim #3", "weaknesses": "Cons:\n- While the dataset used for experiments has a lot of categories, they all seem to score in the same range and saturate a lot. They all get >99.7% test accuracy when the model is trained with all labels. This lack of diversity in the experimentation reduce the strength of the claims #2 and #3.\n\n- The CNN baseline is performing really well at 1% and 100% compared to the proposed DFA -> RNN method while being only made of one layer of convolutions and a MaxPool as the the only non-linearity, reducing the strength of claim #2. \n\n- We don’t have any insight on how the dataset was labeled (line 239) but the labels seem to be synthetically created. Thus the upper-line of this evaluation is the original « attack detection system » which is unknown and could just be a set of RE, explaining the >99% test accuracy.\n\n- Missing explanation on how the authors transform the DFA into a RNN\n\n- RNN distilled into Random Forests is not new and have already been applied on programable switches but there is a lack of comparison in the paper (Mousika: Enable General In-Network Intelligence in Programmable Switches by Knowledge Distillation, Guorui Tie et al.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Con 1**: Generally speaking, the proportion of normal traffic in real-world traffic is much higher than abnormal traffic, i.e., accounting for only much less than 1% among all traffic. Normal traffic can be easily identified by our system because it does not match RE patterns. By analyzing the traffic, the PDF and CDF of matched abnormal packet segments lengths are illustrated in **Figure 1** in the pdf of the **Global Response**. Although our traffic is collected from the real world and sampled over different time periods, we find that the RE patterns in the traffic are relatively fixed, and are only a subset of the Snort. This is why the accuracy of the baseline scheme increases rapidly from 0% to 1% # training data, but not so much from 1% to 100%  # training data.  PSRF can effectively detect abnormal traffic containing short RE patterns. But it may struggle with long RE patterns due to both its inherent design logics and hardware limitation (input length of PSRF cannot exceed 128 bytes, as restricted by the maximum width supported by the switch matching table). However, since the proportion of traffic containing long RE patterns in real-world traffic is very small, i.e., over 95% of traffic are shorter than 50, PSRF can still achieve an accuracy rate of more than 99%. Furthermore, the performances of ML methods using the CIC-Bell-DNS 2021 Dataset, ISCX VPN-nonVPN traffic dataset, and ISCX 2012 IDS dataset ( with a ratio of normal/abnormal traffic of 97%/3%) revealed in [1, 2, 3] are also over 99%, respectively.\n\n[1]S. Mahdavifar, N. \"Classifying Malicious Domains using DNS Traffic Analysis,\" 2021 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, 2021.\n\n[2]Y. Zeng, H. \" Deep−Full−Range  : A Deep Learning Based Network Encrypted Traffic Classification and Intrusion Detection Framework,\" in IEEE Access.\n\n[3]Ferrag, Mohamed Amine, et al. \"Deep learning for cyber security intrusion detection: Approaches, datasets, and comparative study.\" Journal of Information Security and Applications.\n\n**Con 2**: We use a 4-layer CNN methods proposed by [4]. Although the CNN baseline is performing really well at 1% and 100%, the BRNN improves about 2% and 1% in accuracy compared with CNN, respectively. Furthermore, BRNN can achieve a huge improvement (35%) over CNN in the zero-shot scenario, where CNN only achieves around 50% accuracy, which is literally random guess. This means we don’t need to wait for the labeled data, and can immediately train a PSRF and put PSRF into production. Besides, our BRNN can achieve incremental update. For the incremental update of BRNN, we reserve some spare states. When new Res are augmented, we can modify the parameters of the state transition weight T in BRNN according to the DFA corresponding to the new REs, so as to realize the adaptation to the new REs.\n\n[4] Kim, Y. Convolutional neural networks for sentence classification. CoRR, abs/1408.5882, 2014.\n\n**Con 3**: The data labels are generated by the “advance attack detection system and application identification system”, which is a commercial security system deployed in data centers.  This system is not simply relying on a set of rule engines, but it is an integrated system that may encompass a variety of detection techniques and methods that are continuously maintained and updated based on the latest threat landscape. Therefore, the labels generated are of very high accuracy. However, as it is a commercial system, the specific operational details and detection algorithms are confidential to avoid being hacked. \n\n**Con 4**:  We first convert REs into a DFA, which is parameterized by $\\Theta=<T, \\alpha_{0}, \\alpha_{\\infty}>$. Let $h_t \\in \\mathbb{R}^K$ be the forward score vector after considering the first $t$ words $\\{x_1,x_2,...,x_t\\}$ of $\\mathcal{X}$. We can rewrite the forward score into a recurrent form:\n\n$$ h_0 =\\alpha_{0}^T, $$$$ h_t =h_{t-1} \\cdot T\\left[x_{t}\\right], 1 \\leq t \\leq N, $$$$ \\mathcal{B}_{fw}(\\mathcal{A}, \\mathcal{X})=h_N \\cdot \\alpha \\infty . $$\n\nNext, consider the calculation of the hidden states in the forward propagation of the RNN\n\n$$h_t =tanh(Ux^t + Wh^{t-1} + b), 1 \\leq t \\leq N. $$\n\nWhen $U=0, b=0, W=T$, the forward score calculation method of DFA is similar to the forward propagation of RNN. Therefore, we can convert a DFA into a BRNN while retaining the expert knowledge T transition weights. It is equivalent to using the expert knowledge of REs to initialize the BRNN. \n\n**Con 5**: The DT in our experiments can be regarded as a student model distilled by Mousika. The main differences between our SSKD and Mousika are three-fold. First, Mousika relies on abundant labeled data, which is not available in zero-shot scenarios. We utilize the knowledge in REs to construct a BRNN, then distill it into PSRF without any labeled data. Therefore, we don’t need to wait for the labeled data, and can immediately train a PSRF and put it into production. Second, Mousika distills a single-tree model, While our SSKD distills an ensemble forest for better accuracy. Moreover, we propose a novel entry cluster algorithm that heuristically aggregates table entries into clusters based on the similarity among features represented by table entries so that each cluster only requires a more compact table. Since this algorithm is beyond the scope of NIPS, the details are not presented in the paper, but can be found in our code. Experiment results show that PSRF outperforms DT in all scenarios. Third, we propose a novel pooling strategy to improve the accuracy, whose implementation is non-trivial in network devices due to their lack of support for complex float computing. To realize the implementation, on the network devices, we first extract the packet bytes to the packet header vector through the parser. Then in the ingress pipeline, we use the match-action unit to perform a pooling operation on the packet header vector based on the ALU in parallel. Details of technical work can refer to our code. "}, {"review_id": "DOD6s5oEP5", "reviewer": "Reviewer_Jimb", "summary": "This work presents Metis, a framework to enhance user-defined regular expressions (RE) for networking applications when data is available. To this end, a RNN-equivalent model to the RE is first derived, then it can be further trained/finetuned using data gathered during operation.   With Metis, the classification accuracy is vastly superior to existing alternatives.  ", "questions": "Just a couple of questions (quite minor):\n\n* the title: how about replacing \"in Network\" with \"for Networking Task\" or put \"In-Network\" before \"Regular Expressions\". Just sharing my thoughts here because the way it's written seems more to refer to \"network\" as in NN. \n* For Figure 1, it would be better if the caption is self-contained (i.e. so readers know immediately what each stage 1-7 is doing)\n* See my comment in the limitations section.", "limitations": "In addition to the limitations presented by the Authors in Section 5, I believe one big one is missing: what are the implications from the Verification theory point of view of training/finetuning the model? I'm not that familiar with the Verification theory myself but this is something that I can vaguely see being an issue specially in this networking setting. To be clear, verification is an issue inherent to all other NN-based systems, but given the fact that Metis proposes going from fully deterministic RE-only rules to data-enhanced RE-like models, I think this topic should be at least mentioned. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "In my view, the main strength of this paper is brings a creative solution to a problem that, although not so mainstream in the ML community, it is indeed important. Not only that, the solution does perform fairly well and was formulated taking into consideration the hardware constrains where these workloads run.\n\n", "weaknesses": "I'm not that familiar with other works in the networking literature or NLP. So I haven't identified any significant weakness to this work.\n\n* As stated in line 63, the processing of the data stream could be 100Gbps. I understand a static RE set of rules could be implemented very efficiently (maybe even in hardware) and operate at very high throughputs. However, could the Authors comment on whether Metis can derived PSRFs that are as efficient/fast as the RE baseline? I'm thinking for instance, that the derived tree might not be balanced, or that maybe cannot be optimised further easily for instance, via quantization, because of the results of the training/finetuning. Any comments on this?  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: As stated in line 63, the processing of the data stream could be 100Gbps. I understand a static RE set of rules could be implemented very efficiently (maybe even in hardware) and operate at very high throughputs. However, could the Authors comment on whether Metis can derived PSRFs that are as efficient/fast as the RE baseline? I'm thinking for instance, that the derived tree might not be balanced, or that maybe cannot be optimised further easily for instance, via quantization, because of the results of the training/finetuning. Any comments on this?\n\n**A1**:  Many thanks for your comments! This is a very interesting question! \n\nFirst, it is difficult for RE to be directly deployed on network devices because after RE is converted into DFA, the number of states is related to the number and length of RE. The TCAM and SRAM resources in network devices are limited (can only support about 200 RE rules), and cannot support the deployment of the full set of RE , norspecial syntax such as Kleene star. Our approach opens new horizons for the deployment of RE on network devices. In Section 4.4, we compared the RE deployed on the CPU and the PSRF deployed on network devices. The throughput of PSRF is about 100 times that of RE. \n\nSecond, can Metis can derive PSRFs in an efficient/fast way? I would say the answer is yes. When deploying metis for the first time, we converted RE into BRNN and obtained PSRFs through SSKD. This process can be completed within minutes since it does not require training in a complex teacher model (BRNN). Our system is bifurcated into online and offline segments. In the online segment, we deploy the current version of the PSRFs on network devices for real-time detection, while simultaneously collecting data. During the offline segment, we leverage labeled data to fine-tune the BRNN, or when the rule set (Snort) is updated, we transform the new REs into state transitions of the BRNN, updating it accordingly. Subsequently, we distill the updated BRNN into a new version of PSRFs using SSKD and deploy these on the network devices, thereby completing an iteration. Finally, deploying PSRF on network devices needs to convert PSRF into table entries, which can usually be done within 1-2 minutes. Typically, the updating frequency is every two or three months. Therefore, the entire update time is negligible compared to the update frequency. \n\nThird, I think it is very interesting to consider the unbalance between the derived trees. In PSRF, each decision tree is trained independently and thus may vary in size (i.e., depth or number of nodes). This is because each decision tree is trained on a random subset of the dataset, and each node chooses the best-split feature from a random subset of features. This randomness can promote the diversity of the model and help improve the generalization ability of the PSRF. To accelerate the PSRF deployed on the hardware, we propose a novel entry cluster algorithm that heuristically aggregates table entries into clusters based on the similarity among features represented by table entries so that each cluster only requires a more compact table. This algorithm can reduce the table entries when converting each decision trees, and ultimately curb the increase in inference time caused by unbalanced trees. This may exceed the scope of NIPS, but details can refer to our code.\n\n**Q2**: the title: how about replacing \"in Network\" with \"for Networking Task\" or put \"In-Network\" before \"Regular Expressions\". Just sharing my thoughts here because the way it's written seems more to refer to \"network\" as in NN.\n\n**A2**: Many thanks for your comments! We will modify the title.\n\n**Q3**: For Figure 1, it would be better if the caption is self-contained (i.e. so readers know immediately what each stage 1-7 is doing)\n\n**A3**: Many thanks for your comments! We will add a detailed caption to Figure 1 to explain the progress of Metis.\n\n**Q4**: In addition to the limitations presented by the Authors in Section 5, I believe one big one is missing: what are the implications from the Verification theory point of view of training/finetuning the model? I'm not that familiar with the Verification theory myself but this is something that I can vaguely see being an issue specially in this networking setting. To be clear, verification is an issue inherent to all other NN-based systems, but given the fact that Metis proposes going from fully deterministic RE-only rules to data-enhanced RE-like models, I think this topic should be at least mentioned.\n\n**A4**: Thank you for your insightful comment. You raised a significant point regarding the implications from the Verification theory during the training and fine-tuning process. The Verification theory focuses on the correctness of models, which is indeed an important aspect when transitioning from fully deterministic RE-only rules to data-enhanced RE-like models. This topic involves complex issues that were not within the scope of our current study, but we acknowledge its importance and relevance to our work. We will consider this aspect in our future work, focusing on the implications and potential challenges it may present to our approach. This can help improve the robustness of our model and provide a more comprehensive understanding of its behavior and limitations."}, {"review_id": "S5d8NOVqWN", "reviewer": "Reviewer_W2tD", "summary": "This paper proposes a new framework, called Metis, for network traffic pattern matching. It combines the regular expression (RE) for the cold-start stage of a RNN-based neural network such that the cold-start stage of the training can be optimized, while the RNN can be further trained as more training data comes. Considering the limited computing capacities of network devices, the authors further propose to train a lightweight pooling soft random forest (PSRF) model with the supervision of limited human labels and the RNN predictions in a semi-supervised manner. Experimental results are provided to demonstrate the effectiveness and efficiency of the proposed approach.", "questions": "Could you provide end-to-end evaluation results between the Metis framework and the Jiang & Zhao 2020 work?", "limitations": "Yes, the limitations are discussed before the conclusion section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is technically novel and solid to me, and it solves an important problem in networking research by designing a proper learning framework. Combining the advantage of REs during the cold-start stage and the learning capabilities of NNs with more available data makes sense to me.\n2. The provided evaluations are systematic, comprehensive, and strong, while significant improvements are achieved compared to the baselines in each of the performed experiments.\n3. The presentation of the paper is generally easy to understand and follow.\n", "weaknesses": "I only have a few minor issues to mention.\n\n1. In the evaluation, the authors only separately compare the BRNN and PSRF to their respective baselines, would it be possible to compare the proposed approach with existing pattern-matching baselines in an end-to-end manner? For example, how does the proposed approach compare to multi-string matching approaches proposed by Jiang & Zhao 2020 as mentioned by the authors in line 36? How does the approach compare to conventional frequent mining approaches?\n\n2. It would be useful to report the proposed approach's training time since it introduces an extra distillation step than other learning-based approaches. Would it be fast enough to support frequent updates of the model?\n\n3. It seems the authors intentionally built a balanced dataset for each class, such that the random guess accuracy is around 50%. However, this might not match the practical distribution. How would the models perform under the practical distribution between positive and negative samples of each class?\n\n4. There are some presentation issues that should be fixed in the paper: First, the color coding in Table 1 and Table 2 was not introduced in the caption or in the text, and it might not be friendly to readers with printed papers. Second, it would be better to add a column in both Table 1 and Table 2 to summarize the overall accuracy covering all classes. Third, in Figure 1, the pink and blue colors are simultaneously used to represent online/offline phases and different RE categories, which is confusing to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: In the evaluation, the authors only separately compare the BRNN and PSRF to their respective baselines, would it be possible to compare the proposed approach with existing pattern-matching baselines in an end-to-end manner? For example, how does the proposed approach compare to multi-string matching approaches proposed by Jiang [1] as mentioned by the authors in line 36? How does the approach compare to conventional frequent mining approaches?\n\n**A1**: Many thanks for your comments! Jiang [1] converts multi-string rules into a trainable RNN, which cannot be directly deployed on network devices since the network device does not support complex floating operations. So it still required to be distilled to a lightweight, hardware-friendly model. Our work aims to extend the capabilities of existing multi-string matching approaches to support regular expression matching. Table 1 below shows the RE syntaxes we support, Jiang’s work only supports the first five syntaxes. We also conduct the experiment on the category of games to verify the method of Jiang. We set the same parameters in [1]. The results are shown in the following:\n\n|         | 0     | 1     | 10    | 100   |\n|---------|-------|-------|-------|-------|\n| RE      | 91.66 | 91.66 | 91.66 | 91.66 |\n| Jiang's | 59.50 | 87.48 | 96.25 | 97.74 |\n| BRNN    | 91.66 | 96.81 | 99.59 | 99.93 |\n\nNote that columns represent # training data. BRNN improves around 32% accuracy compared with Jiang’s method in the zero-shot scenarios. For few-shot and full training, BRNN still outperforms Jiang’s method.\n\nConventional frequent mining approaches [2,3,4] do not perform well in zero-shot scenarios because they cannot be initialized with expert knowledge of RE rules. And they still need to be distilled into a lightweight, hardware-friendly model. We also conduct an experiment compared with a novel method of intrusion detection called DRF using the UNB ISCX IDS 2012 dataset [5]. The results are shown as follow:\n\n|      | 0     | 1     | 10    | 100   |\n|------|-------|-------|-------|-------|\n| RE   | 77.84 | 77.84 | 77.84 | 77.84 |\n| DFR  | 49.62 | 71.05 | 81.19 | 98.71 |\n| BRNN | 77.84 | 80.93 | 87.94 | 99.47 |\n\nBRNN outperforms DFR in all scenarios. We add additional experiments in Appendix.\n\n[1]  Jiang, C, Y. Cold-start and interpretability: Turning regular expressions into trainable recurrent neural networks. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, pp. 3193–3207, 2020.\n\n[2] Chauhan. \"Survey on data mining techniques in intrusion detection.\" International Journal of Scientific & Engineering Research 2.7 (2011): 1-4.\n\n[3] Patel. \"A survey and comparative analysis of data mining techniques for network intrusion detection systems.\" International Journal of Soft Computing and Engineering (IJSCE) 2.1 (2012): 265-260.\n\n[4] Data Mining Machine Learning Techniques – A Study on Abnormal Anomaly Detection System. M. Sathya Narayana, B. V. V. S. Prasad,A. Srividhya,K. Pandu Ranga Reddy. Issue 6, September 2011, International Journal of Computer Science and Telecommunications.\n\n[5] https://www.unb.ca/cic/datasets/ids.html\n\n**Q2**: It would be useful to report the proposed approach's training time since it introduces an extra distillation step than other learning-based approaches. Would it be fast enough to support frequent updates of the model?\n\n**A2**: Many thanks for your comments! The process of our Metis is: when deploying metis for the first time, we converted RE into BRNN and obtained PSRFs through SSKD. This process can be completed within minutes since it does not require training in a complex teacher model (BRNN). Our system is bifurcated into online and offline segments. In the online segment, we deploy the current version of the PSRFs on network devices for real-time detection, while simultaneously collecting data. During the offline segment, we leverage labeled data to fine-tune the BRNN, or when the rule set (Snort) is updated, we transform the new REs into state transitions of the BRNN, updating it accordingly. Subsequently, we distill the updated BRNN into a new version of PSRFs using SSKD and deploy these on the network devices, thereby completing an iteration. Typically, the updating frequency of Metis is every two or three months according the update frequency of the RE set (e.g., the frequency of update of Snort is about three months). The process of transforming RE set to DFA and DFA to BRNN can be done in minutes (i.e., usually less than 2-3 minutes). The process of fully training a BRNN needs about 1~2 hours since the BRNN can be regard as a 1-layer RNN with small trainable parameters. And the process of distilling a BRNN to a PSRF can be done in 10 minutes. Finally, deploying PSRF on network devices needs to convert PSRF into table entries, and this process can usually be completed within 1-2 minutes. Therefore, the entire update time is negligible considering the update frequency. We will add the cost of time in Appendix.\n\n**Q3**: It seems the authors intentionally built a balanced dataset for each class, such that the random guess accuracy is around 50%. However, this might not match the practical distribution. How would the models perform under the practical distribution between positive and negative samples of each class?\n\n**A3**: The distribution between the positive and negatives of each class in our dataset which is collected from the real-world is about 99:1. For LSTM, CNN, and DAN, we randomly initialize its parameters at the beginning. In zero-shot scenarios, we do not have labeled data to train these methods, so the logits they output are random. Therefore, we observed that their accuracy is around 50%.\n\nWe will explain the meaning of the color in the caption, add the average column in Tables 1 and 2, and modify the color in Figure 1."}, {"review_id": "1yVYgIAL56", "reviewer": "Reviewer_38Wo", "summary": "This paper proposes Metis, an approach to converts regular expressions into byte-level recurrent neural networks without training. The benefit of this is to preserve the expert knowledge from the regular expressions and perform well in code-start. The proposed approach has been evaluated with network traffic data collected in the real-world. ", "questions": "- What is the cost of running the proposed approach on devices? e.g. in terms of latency or other relevant metrics? \n- In the main results, are those reported number averaged? If so what would be the standard deviation? \n- Are the experiments using different training data performed with different random seeds? ", "limitations": "The authors have discussed the limitations and societal impact of the proposed work. The discussion makes sense and is relevant to the community. ", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The idea of converting RE into BRNN, and then use knowledge distillation to transform them into PSRF makes sense. \n- The proposed approach can work in a training free way, and when data is available it can improve its performance via training. \n- The proposed approach has been evaluated with data from the real world. \n", "weaknesses": "- It seems the proposed approach is a combination of existing methods, and therefore the novelty is limited. \n- The proposed approach claims to be able to deploy on network devices, but the evaluation is rather limited. \n- Some of the experimental details are missing. For instance, it is not clear what is the computational capability of the networked device used in this paper. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: It seems the proposed approach is a combination of existing methods, and therefore the novelty is limited.\n\n**A1**: Many thanks for your comments! This is the first method to employ model inference as an alternative to RE matching in network devices. Recently, Jiang is the latest work that combines RE and NN. It essentially provides a rule system-based model architecture and parameter initialization method, which can convert multi-string patterns into a trainable RNN without loss of accuracy. However, it faces two problems: 1) It specifically aims at NLP scenarios and cannot be applied to network scenarios. For example, the payload of network packets does not use words for tokenization, but bit or byte as the basic processing unit. 2) It only implements multi-string matching and simple extensions (such as OR operations), but not RE matching, which contains more complex syntaxes for better expressive power. Table 1 below shows the RE syntaxes we support, Jiang only supports the first five syntaxes. \n\n| Syntax                       | Meaning                                                                                                      |\n|-|-|\n| $\\alpha$                     | Matches a single character.                                                                                  |\n| $\\alpha\\beta$                | CONCAT operation. Matches $\\alpha \\beta$.                                                                    |\n| $\\alpha \\| \\beta$            | OR ($\\|$) operation. Matches $\\alpha$ or $\\beta$.                                                            |\n| $\\alpha*$                    | Kleene ($*$) star. Matches $\\alpha$ zero or more times.                                                      |\n| $.$                          | Wildcard. Matches any character.                                                                             |\n| $\\alpha+$                    | PLUS ($+$) operation. Matches $\\alpha$ one or more times.                                                    |\n| $\\hat{} \\alpha$              | Matches $\\alpha$ only appears at the beginning of the string.                                                |\n| $\\alpha$                   | Matches $\\alpha$ only appears at the ending of the string.                                                   |\n| $[\\alpha-\\beta]$             | Character class. The character class uses OR operation to match a character included in the character class. |\n| $\\alpha \\{ \\beta, \\delta \\}$ | Range Matching. Matches $\\alpha$ subexpression $\\beta$ to $\\delta$ times.                                    |\n| $\\alpha \\{ \\beta, \\}$        | AtLeast Matching. Matches $\\alpha$ subexpression $\\beta$ or more times.                                      |\n| $\\alpha \\{ \\beta\\}$          | Exactly Matching. Matches $\\alpha$ subexpression $\\beta$ times.                                              |\n| $\\backslash d$               | Matches any number, equivalent to $[0-9]$.                                                                   |\n| $\\backslash D$               | Matches any non-number.                                                                                      |\n| $\\backslash w$               | Matches any letter, equivalent to $[a-zA-Z]$.                                                                |\n| $\\backslash W$               | Matches any non-letter.                                                                                      |\n| $\\backslash s$               | Matches any non-whitespace character.                                                                        |\n| $\\backslash S$               | Matches any whitespace character.                                                                            |\n\nIn addition to BRNN, we also make the following contributions: 1) A novel semi-supervised distillation algorithm SSKD to transform the BRNN into a device-friendly model. 2) An effective student model PSRF which introduces the pooling operation to improve the representation capability of decision trees for contextual information in serialized data. The main differences between our SSKD and previous work (e.g., Mousika) are three-fold. The main differences between our SSKD and Mousika are three-fold. First, Mousika relies on abundant labeled data, which is not available in zero-shot scenarios. We utilize the knowledge in REs to construct a BRNN, then distill it into PSRF without any labeled data. Therefore, we don’t need to wait for the labeled data, and can immediately train a PSRF and put it into production. Second, Mousika distills a single-tree model, While our SSKD distills an ensemble forest for better accuracy. Moreover, we propose a novel entry cluster algorithm that heuristically aggregates table entries into clusters based on the similarity among features represented by table entries so that each cluster only requires a more compact table. Since this algorithm isbeyond the scope of NIPS, the details are not presented in the paper, but can be found in our code. Experiment results show that PSRF outperforms DT in all scenarios. Third, we propose a novel pooling strategy to improve the accuracy, whose implementation is non-trivial in network devices due to their lack of support for complex float computing. To realize the implementation, on the network devices, we first extract the packet bytes to the packet header vector through the parser. Then in the ingress pipeline, we use the match-action unit to perform a pooling operation on the packet header vector based on the ALU in parallel. Details of technical work can refer to our code. \n\nThe remaining questions will be answered in the discussion due to the word limit of the rebuttal."}, {"review_id": "PwOhKupezp", "reviewer": "Reviewer_qD4Y", "summary": "The paper proposes a novel methodology for network intrusion detection. Specifically, authors train RNN models to train on byte-level packet data from communication networks for intrusion detection. These models called Byte-Level Recurrent-Neural Networks (BRNN) can be viewed as knowledge-infused machine learning models wherein the model starts from a well-founded initial state guided by expert knowledge in the form of regular expression patterns which are a popular security mechanism in network intrusion detection. Primary novelty of this work is adapting methodology in [1] of converting symbolic expert knowledge (Regex) into RNNs and expanding it to more diverse form of regular expressions. Secondary contribution is they employ knowledge distillation (KD) techniques to obtain tiny soft random forest models from the larger BRNNs that can be deployed onto network devices. ", "questions": "Although the task of network-intrusion detection is well motivated for the current method, what are some adaptations that might need to be considered to apply the method to other applications in cyber-physical system security (e.g., non-network based) e.g., power system security? This is a question aimed at gaining better insight on the primary components of the method that will need to be re-designed for different applications.\n\n", "limitations": "The authors have highlighted the ethical considerations as well as the limitations of their method. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "# Strengths: \n\n- The paper is well written and easy to follow and is marginally novel in terms of the development of soft random forests as a knowledge distilled version of BRNNs. \n \n\n- The paper addresses a well-motivated and important application of network intrusion detection while utilizing the already existing domain knowledge (i.e., regular expression rules) in addition to any available training data.  \n \n\n- The major advantage of such expert knowledge guided machine learning is that they perform well under data paucity and are more generalizable and stable compared to purely data driven models. This is clearly demonstrated in Table 1. Generally, this paradigm of expert knowledge guided machine learning in general leads to less costly and more generalizable and stables ML models. Furthermore, BRNNs as opposed to explicit Regex matching leads to faster inference pipelines (demonstrated by Fig .3) \n \n\n- The proposed model can capture the original regular expressions they have been trained to emulate as evidenced by similar accuracy scores between RE and BRNN (with 0% training data) in Table 1. ", "weaknesses": "The proposed BRNN pipeline is a direct adaptation of the model proposed in [1] with minor extensions to more diverse regular expressions. However, despite this, due to the novelty of the application and the additional low-cost model development, I believe the overall contribution of the paper is still significant. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: The proposed BRNN pipeline is a direct adaptation of the model proposed in [1] with minor extensions to more diverse regular expressions. However, despite this, due to the novelty of the application and the additional low-cost model development, I believe the overall contribution of the paper is still significant.\n\n**A1**: Many thanks for your comments! This is the first method to employ model inference as an alternative to RE matching in network devices. Recently, Jiang is the latest work that combines RE and NN. It essentially provides a rule system-based model architecture and parameter initialization method, which can convert multi-string patterns into a trainable RNN without loss of accuracy. However, it faces two problems: 1) It specifically aims at NLP scenarios and cannot be applied to network scenarios. For example, the payload of network packets does not use words for tokenization, but bit or byte as the basic processing unit. 2) It only implements multi-string matching and simple extensions (such as OR operations), but not RE matching, which contains more complex syntaxes for better expressive power. Table 1 below shows the RE syntaxes we support, Jiang only supports the first five syntaxes. \n\n| Syntax                       | Meaning                                                                                                      |\n|-|-|\n| $\\alpha$                     | Matches a single character.                                                                                  |\n| $\\alpha\\beta$                | CONCAT operation. Matches $\\alpha \\beta$.                                                                    |\n| $\\alpha \\| \\beta$            | OR ($\\|$) operation. Matches $\\alpha$ or $\\beta$.                                                            |\n| $\\alpha*$                    | Kleene ($*$) star. Matches $\\alpha$ zero or more times.                                                      |\n| $.$                          | Wildcard. Matches any character.                                                                             |\n| $\\alpha+$                    | PLUS ($+$) operation. Matches $\\alpha$ one or more times.                                                    |\n| $\\hat{} \\alpha$              | Matches $\\alpha$ only appears at the beginning of the string.                                                |\n| $\\alpha$                   | Matches $\\alpha$ only appears at the ending of the string.                                                   |\n| $[\\alpha-\\beta]$             | Character class. The character class uses OR operation to match a character included in the character class. |\n| $\\alpha \\{ \\beta, \\delta \\}$ | Range Matching. Matches $\\alpha$ subexpression $\\beta$ to $\\delta$ times.                                    |\n| $\\alpha \\{ \\beta, \\}$        | AtLeast Matching. Matches $\\alpha$ subexpression $\\beta$ or more times.                                      |\n| $\\alpha \\{ \\beta\\}$          | Exactly Matching. Matches $\\alpha$ subexpression $\\beta$ times.                                              |\n| $\\backslash d$               | Matches any number, equivalent to $[0-9]$.                                                                   |\n| $\\backslash D$               | Matches any non-number.                                                                                      |\n| $\\backslash w$               | Matches any letter, equivalent to $[a-zA-Z]$.                                                                |\n| $\\backslash W$               | Matches any non-letter.                                                                                      |\n| $\\backslash s$               | Matches any non-whitespace character.                                                                        |\n| $\\backslash S$               | Matches any whitespace character.                                                                            |\n\nIn addition to BRNN, we also make the following contributions: 1) A novel semi-supervised distillation algorithm SSKD to transform the BRNN into a device-friendly model. 2) An effective student model PSRF which introduces the pooling operation to improve the representation capability of decision trees for contextual information in serialized data. The main differences between our SSKD and previous work (e.g., Mousika) are three-fold. The main differences between our SSKD and Mousika are three-fold. First, Mousika relies on abundant labeled data, which is not available in zero-shot scenarios. We utilize the knowledge in REs to construct a BRNN, then distill it into PSRF without any labeled data. Therefore, we don’t need to wait for the labeled data, and can immediately train a PSRF and put it into production. Second, Mousika distills a single-tree model, While our SSKD distills an ensemble forest for better accuracy. Moreover, we propose a novel entry cluster algorithm that heuristically aggregates table entries into clusters based on the similarity among features represented by table entries so that each cluster only requires a more compact table. Since this algorithm isbeyond the scope of NIPS, the details are not presented in the paper, but can be found in our code. Experiment results show that PSRF outperforms DT in all scenarios. Third, we propose a novel pooling strategy to improve the accuracy, whose implementation is non-trivial in network devices due to their lack of support for complex float computing. To realize the implementation, on the network devices, we first extract the packet bytes to the packet header vector through the parser. Then in the ingress pipeline, we use the match-action unit to perform a pooling operation on the packet header vector based on the ALU in parallel. Details of technical work can refer to our code. \n\nThe remaining questions will be answered in the discussion due to the word limit of the rebuttal."}, {"review_id": "gfPK4cVyeE", "reviewer": "Reviewer_Uzg2", "summary": "The paper proposes a framework called Metis that combines regular expressions (REs) and neural networks (NNs) to improve network intrusion detection and other networking tasks. Metis utilizes byte-level tokenization to extract RE from network rules and processes bit streams of network traffic. The RE is converted to Bidirectional Recurrent Neural Network (BRNN) and distilled into a device-friendly model called Packet Sampling Random Forest (PSRF) through semi-supervised knowledge distillation. Metis was evaluated on campus network traffic, achieving superior throughput while being more accurate than original REs and other baseline models.\n\n", "questions": "1.\tAs this paper proposed three novel modules, and what impact would it have on the algorithm if one of modules is removed or replaced with an alternative approach?", "limitations": "Limitations and societal impact on AI community are well discussed in this paper.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper proposes a novel method Metis to explore the use of model inference as an alternative to RE matching, which is a insightful and interesting perspective in network scenarios.\n2.\tThe proposed method, Metis, leverage the flexibility and capabilities of DNNs while maintaining the accuracy of the RE-based system, and e a novel semi-supervised d distillation algorithm are proposed to achieve lightweight deployment of RE-based systems in network devices.\n3.\tThe effectiveness of the proposed algorithm is proved by collecting real-world datasets and conducting sufficiently experiments.\n4.\tThis paper is well-written and easy to understand, and anonymously code is provided for researchers to reproduce the results conveniently.\n", "weaknesses": "1.\tDifferences in related works should be discussed more comprehensively.\n2.\tAblation experiments on critical modules and the analysis of performance improvement are lacking in the paper.\n3.\tAs this paper proposed three novel modules, and what impact would it have on the algorithm if one of modules is removed or replaced with an alternative approach?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Please review our work carefully！\n\nThank you for your comments.  But we wonder if you had read our paper carefully. You rated your confidence to **5**. But you **DO NOT EVEN** know the name of our model, **NOR DID** you appear to understand the model and experiment in our paper.  We think your comments and rating are very unfair to us.\n\nFor example, in the Summary, you said that “The RE is converted to **Bidirectional Recurrent Neural Network (BRNN)**.” However, in our paper, we mentioned more than once in the Abstract (Line 9-10), Introduction (Line 57-58) and Meits (Line 171-172) that we use **byte-level RNNs (BRNNs)** to preserve expert knowledge in byte-level DFAs. We **NEVER EVER** mention the **Bidirectional Recurrent Neural Network (BRNN)** in our work. Besides, in the Summary, you said that “we distilled into a device-friendly model called **Packet Sampling Random Forest (PSRF)** through semi-supervised knowledge distillation”. However, we also mentioned more than once in the Abstract (Line 14), Introduction (Line 60) and Metis (Line 180) that we distill the BRNNs to the **pooling soft random forests (PSRFs)**. We **NEVER EVER** mention the **Packet Sampling Random Forest (PSRF)** in our work.\n\nFor the weakness you mentioned, you said that “Ablation experiments on critical modules and the analysis of performance improvement are lacking in the paper.” and \"As this paper proposed three novel modules, and what impact would it have on the algorithm if one of modules is removed or replaced with an alternative approach?\". In our work, we propose Metis which utilizes Rule2DFA, DFA2BRNN, and BRNN2PSRF to convert REs to hardware-friendly lightweight models, which is a **non-separable process**. For example, if we don’t have the BRNN2PSRF module, how can we get hardware-friendly lightweight models? Also, if we don’t have Rule2DFA, how can we transform the REs into trainable RNNs? Furthermore, we discuss the performance improvement in Section 4.2 Main Results (Line 270-295)."}]

Author rebuttal:
We add the PDF and CDF of matched abnormal packet segment lengths in Figure 1 and the PCRE syntax supported in our paper. Both of them are in the attached pdf.

Meta-review: Reviewers recognized that the paper try to solves an important problem in networking research with an interesting approach. However some reviewers raise some minor point in their review which have been addressed in the rebuttal. We invite the authors to take these changes into account in the camera-ready version of the paper.

One of the members of the program committee pointed out that a potential issue with calling the method"Metis". The Métis are an Indigenous people in Canada and the northern United states. The authors may wish to consider a different name for their method to avoid confusion.
Decision: Accept (poster)