Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection

Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection Milan ˇ Ceˇska, Vojtˇech Havlena, Luk´aˇsHol´ık, Ondˇrej Leng´al(B), and Tom´aˇs Vojnar FIT, IT4Innovations Centre of Excellence, Brno University of Technology, Brno, Czech Republic [email protected] Abstract. We consider the problem of approximate reduction of non-deterministic automata that appear in hardware-accelerated network intrusion detection systems (NIDSes). We define an error distance of a reduced automaton from the original one as the probability of packets being incorrectly classified by the reduced automaton (wrt the probabilistic distribution of packets in the network traffic). We use this notion to design an approximate reduction procedure that achieves a great size reduction (much beyond the state-of-the-art language preserving techniques) with a controlled and small error. We have implemented our approach and evaluated it on use cases from Snort, a popular NIDS. Our results provide experimental evidence that the method can be highly efficient in practice, allowing NIDSes to follow the rapid growth in the speed of networks. 1 Introduction The recent years have seen a boom in the number of security incidents in computer networks. In order to alleviate the impact of network attacks and intrusions, Internet providers want to detect malicious traffic at their network’s entry points and on the backbones between sub-networks. Software-based network intrusion detection systems (NIDSes), such as the popular open-source system Snort [1], are capable of detecting suspicious network traffic by testing (among others) whether a packet payload matches a regular expression (regex) describing known patterns of malicious traffic. NIDSes collect and maintain vast databases of such regexes that are typically divided into groups according to types of the attacks and target protocols. Regex matching is the most computationally demanding task of a NIDS as its cost grows with the speed of the network traffic as well as with the number and complexity of the regexes being matched. The current software-based NIDSes cannot perform the regex matching on networks beyond 1 Gbps [2,3], so they cannot handle the current speed of backbone networks ranging between tens and hundreds of Gbps. A promising approach to speed up NIDSes is to (partially) c The Author(s) 2018 D. Beyer and M. Huisman (Eds.): TACAS 2018, LNCS 10806, pp. 155–175, 2018. https://doi.org/10.1007/978-3-319-89963-3_9 156 M. ˇ Ceˇska et al. offload regex matching into hardware [3–5]. The hardware then serves as a prefilter of the network traffic, discarding the majority of the packets from further processing. Such pre-filtering can easily reduce the traffic the NIDS needs to handle by two or three orders of magnitude [3]. Field-programmable gate arrays (FPGAs) are the leading technology in highthroughput regex matching. Due to their inherent parallelism, FPGAs provide an efficient way of implementing nondeterministic finite automata (NFAs), which naturally arise from the input regexes. Although the amount of available resources in FPGAs is continually increasing, the speed of networks grows even faster. Working with multi-gigabit networks requires the hardware to use many parallel packet processing branches in a single FPGA [5]; each of them implementing a separate copy of the concerned NFA, and so reducing the size of the NFAs is of the utmost importance. Various language-preserving automata reduction approaches exist, mainly based on computing (bi)simulation relations on automata states (cf. the related work). The reductions they offer, however, do not satisfy the needs of high-speed hardware-accelerated NIDSes. Our answer to the problem is approximate reduction of NFAs, allowing for a trade-off between the achieved reduction and the precision of the regex matching. To formalise the intuitive notion of precision, we propose a novel probabilistic distance of automata. It captures the probability that a packet of the input network traffic is incorrectly accepted or rejected by the approximated NFA. The distance assumes a probabilistic model of the network traffic (we show later how such a model can be obtained). Having formalised the notion of precision, we specify the target of our reductions as two variants of an optimization problem: (1) minimizing the NFA size given the maximum allowed error (distance from the original), or (2) minimizing the error given the maximum allowed NFA size. Finding such optimal approximations is, however, computationally hard (PSPACE-complete, the same as precise NFA minimization). Consequently, we sacrifice the optimality and, motivated by the typical structure of NFAs that emerge from a set of regexes used by NIDSes (a union of many long “tentacles” with occasional small strongly-connected components), we limit the space of possible reductions by restricting the set of operations they can apply to the original automaton. Namely, we consider two reduction operations: (i) collapsing the future of a state into a self-loop (this reduction over-approximates the language), or (ii) removing states (such a reduction is under-approximating). The problem of identifying the optimal sets of states on which these operations should be applied is still PSPACE-complete. The restricted problem is, however, more amenable to an approximation by a greedy algorithm.The algorithm applies the reductions state-by-state in an order determined by a precomputed error labelling of the states. The process is stopped once the given optimization goal in terms of the size or error is reached. The labelling is based on the probability of packets that may be accepted through a given state and hence over-approximates the error that may be caused by applying the reduction at a given state. As our experiments show, this approach can give us high-quality reductions while ensuring formal error bounds. Approximate Reduction of Finite Automata 157 Finally, it turns out that even the pre-computation of the error labelling of the states is costly (again PSPACE-complete). Therefore, we propose several ways to cheaply over-approximate it such that the strong error bound guarantees are still preserved. Particularly, we are able to exploit the typical structure of the “union of tentacles” of the hardware NFA in an algorithm that is exponential in the size of the largest “tentacle” only, which is indeed much faster in practice. We have implemented our approach and evaluated it on regexes used to classify malicious traffic in Snort. We obtain quite encouraging experimental results demonstrating that our approach provides a much better reduction than language-preserving techniques with an almost negligible error. In particular, our experiments, going down to the level of an actual implementation of NFAs in FPGAs, confirm that we can squeeze into an up-to-date FPGA chip real-life regexes encoding malicious traffic, allowing them to be used with a negligible error for filtering at speeds of 100 Gbps (and even 400 Gbps). This is far beyond what one can achieve with current exact reduction approaches. Related Work. Hardware acceleration for regex matching at the line rate is an intensively studied technology that uses general-purpose hardware [6–14]as well as FPGAs [3–5,15–20]. Most of the works focus on DFA implementation and optimization techniques. NFAs can be exponentially smaller than DFAs but need, in the worst case, O(n) memory accesses to process each byte of the payload where nis the number of states. In most cases, this incurs an unacceptable slowdown. Several works alleviate this disadvantage of NFAs by exploiting reconfigurability and fine-grained parallelism of FPGAs, allowing one to process one character per clock cycle (e.g. [3–5,15,16,19,20]). In [14], which is probably the closest work to ours, the authors consider a set of regexes describing network attacks. They replace a potentially prohibitively large DFA by a tree of smaller DFAs, an alternative to using NFAs that minimizes the latency occurring in a non-FPGA-based implementation. The language of every DFA-node in the tree over-approximates the languages of its children. Packets are filtered through the tree from the root downwards until they belong to the language of the encountered nodes, and may be finally accepted at the leaves, or are rejected otherwise. The over-approximating DFAs are constructed using a similar notion of probability of an occurrence of a state as in our approach. The main differences from our work are that (1) the approach targets approximation of DFAs (not NFAs), (2) the over-approximation is based on a given traffic sample only (it cannot benefit from a probabilistic model), and (3) no probabilistic guarantees on the approximation error are provided. Approximation of DFAs was considered in various other contexts. Hyper-minimization is an approach that is allowed to alter language membership of a finite set of words [21,22]. A DFA with a given maximum number of states is constructed in [23], minimizing the error defined either by (i) counting prefixes of misjudged words up to some length, or (ii) the sum of the probabilities of the misjudged words wrt the Poisson distribution over Σ∗. Neither of these approaches considers reduction of NFAs nor allows to control the expected error with respect to the real traffic. 158 M. ˇ Ceˇska et al. In addition to the metrics mentioned above when discussing the works [21–23], the following metrics should also be mentioned. The Cesaro-Jaccard distance studied in [24] is, in spirit, similar to [23] and does also not reflect the probability of individual words. The edit distance of weighted automata from [25] depends on the minimum edit distance between pairs of words from the two compared languages, again regardless of their statistical significance. None of these notions is suitable for our needs. Language-preserving minimization of NFAs is a PSPACE-complete problem [26,38]. More feasible (polynomial-time) is language-preserving size reduction of NFAs based on (bi)simulations [27–30], which does not aim for a truly minimal NFA. A number of advanced variants exist, based on multi-pebble or look-ahead simulations, or on combinations of forward and backward simulations [31–33]. The practical efficiency of these techniques is, however, often insufficient to allow them to handle the large NFAs that occur in practice and/or they do not manage to reduce the NFAs enough. Finally, even a minimal NFA for the given set of regexes is often too big to be implemented in the given FPGA operating on the required speed (as shown even in our experiments). Our approach is capable of a much better reduction for the price of a small change of the accepted language. 2 Preliminaries We use a, bto denote the set {x∈R|a≤x≤b}and Nto denote the set {0,1,2,...}. Given a pair of sets X1and X2,weuseX1X2to denote their symmetric difference, i.e., the set {x|∃!i∈{1,2}:x∈Xi}.Weusethe notation [v1,...,v n] to denote a vector of nelements, 1to denote the all 1’s vector [1,...,1], Ato denote a matrix, and Afor its transpose, and Ifor the identity matrix. In the following, we fix a finite non-empty alphabet Σ.Anondeterministic finite automaton (NFA) is a quadruple A=(Q, δ, I, F ) where Qis a finite set of states, δ:Q×Σ→2Qis a transition function, I⊆Qis a set of initial states, and F⊆Qis a set of accepting states. We use Q[A],δ[A],I[A], and F[A] to denote Q, δ, I,andF, respectively, and qa −→ qto denote that q∈δ(q,a). A sequence of states ρ=q0···qnis a run of Aover a word w=a1···an∈Σ∗ from a state qto a state q, denoted as qw,ρ q,if∀1≤i≤n:qi−1 ai −→ qi, q0=q,andqn=q. Sometimes, we use ρin set operations where it behaves as the set of states it contains. We also use qw qto denote that ∃ρ∈Q∗:qw,ρ q and qqto denote that ∃w:qw q.Thelanguage of a state qis defined as LA(q)={w|∃qF∈F:qw qF}and its banguage (back-language) is defined as L A(q)={w|∃qI∈I:qI w q}. Both notions can be naturally extended to a set S⊆Q:LA(S)=q∈SLA(q)andL A(S)=q∈SL A(q). We drop the subscript Awhen the context is obvious. Aaccepts the language L(A) defined as L(A)=LA(I). Ais called deterministic (DFA) if |I|=1and∀q∈Qand ∀a∈Σ:|δ(q,a)|≤1, and unambiguous (UFA) if ∀w∈L(A):∃!qI∈I,ρ ∈ Q∗,q F∈F:qI w,ρ qF. Approximate Reduction of Finite Automata 159 The restriction of Ato S⊆Qis an NFA A|Sgiven as A|S=(S, δ ∩(S× Σ×2S),I ∩S, F ∩S). We define the trim operation as trim(A)=A|Cwhere C={q|∃qI∈I,qF∈F:qIqqF}. For a set of states R⊆Q,weuse reach(R) to denote the set of states reachable from R, formally, reach(R)={r| ∃r∈R:rr}. We use the number of states as the measurement of the size of A, i.e., |A|=|Q|. A (discrete probability) distribution overasetXis a mapping Pr : X→0,1 such that x∈XPr(x)=1.Ann-state probabilistic automaton (PA) over Σis a triple P=(α,γ,{Δa}a∈Σ) where α∈0,1nis a vector of initial weights, γ∈0,1nis a vector of final weights,andforeverya∈Σ,Δa∈0,1n×n is a transition matrix for symbol a. We abuse notation and use Q[P] to denote the set of states Q[P]={1,...,n}. Moreover, the following two properties need to hold: (i) {α[i]|i∈Q[P]}= 1 (the initial probability is 1) and (ii) for every state i∈Q[P] it holds that {Δa[i, j]|j∈Q[P],a∈Σ}+γ[i] = 1 (the probability of accepting or leaving a state is 1). We define the support of Pas the NFA supp(P)=(Q[P],δ[P],I[P],F[P]) s.t. δ[P]={(i, a, j)|Δa[i, j]>0}I[P]={i|α[i]>0}F[P]={i|γ[i]>0}. Let us assume that every PA Pis such that supp(P)=trim(supp(P)). For awordw=a1...a k∈Σ∗,weuseΔwto denote the matrix Δa1···Δak.Itcan be easily shown that Prepresents a distribution over words w∈Σ∗defined as PrP(w)=α·Δw·γ. We call PrP(w)theprobability of win P. Given a language L⊆Σ∗, we define the probability of Lin Pas PrP(L)=w∈LPrP(w). If Conditions (i) and (ii) from the definition of PAs are dropped, we speak about a pseudo-probabilistic automaton (PPA), which may assign a word from its support a quantity that is not necessarily in the range 0,1, denoted as the significance of the word below. PPAs may arise during some of our operations performed on PAs. 3 Approximate Reduction of NFAs In this section, we first introduce the key notion of our approach: a probabilistic distance of a pair of finite automata wrt a given probabilistic automaton that, intuitively, represents the significance of particular words. We discuss the complexity of computing the probabilistic distance. Finally, we formulate two problems of approximate automata reduction via probabilistic distance.Proofsof the lemmas can be found in [43]. 3.1 Probabilistic Distance We start by defining our notion of a probabilistic distance of two NFAs. Assume NFAs A1and A2and a probabilistic automaton Pspecifying the distribution 160 M. ˇ Ceˇska et al. PrP:Σ∗→0,1.Theprobabilistic distance dP(A1,A 2) between A1and A2wrt PrPis defined as dP(A1,A 2)=Pr P(L(A1)L(A2)). Intuitively, the distance captures the significance of the words accepted by one of the automata only. We use the distance to drive the reduction process towards automata with small errors and to assess the quality of the resulting automata. The value of PrP(L(A1)L(A2)) can be computed as follows. Using the fact that (1) L1L2=(L1\L2)(L2\L1) and (2) L1\L2=L1\(L1∩L2), we get dP(A1,A 2)=Pr P(L(A1)\L(A2)) + PrP(L(A2)\L(A1)) =Pr P(L(A1)\(L(A1)∩L(A2))) + PrP(L(A2)\(L(A2)∩L(A1))) =Pr P(L(A1)) + PrP(L(A2)) −2·PrP(L(A1)∩L(A2)). Hence, the key step is to compute PrP(L(A)) for an NFA Aand a PA P.Problems similar to computing such a probability have been extensively studied in several contexts including verification of probabilistic systems [34–36]. The below lemma summarises the complexity of this step. Lemma 1. Let PbeaPAandAan NFA. The problem of computing PrP(L(A)) is PSPACE-complete. For a UFA A,PrP(L(A)) can be computed in PTIME. In our approach, we apply the method of [36] and compute PrP(L(A)) in the following way. We first check whether the NFA Ais unambiguous. This can be done by using the standard product construction (denoted as ∩)for computing the intersection of the NFA Awith itself and trimming the result, formally B=trim(A∩A), followed by a check whether there is some state (p, q)∈Q[B] s.t. p=q[37]. If Ais ambiguous, we either determinise it or disambiguate it [37], leading to a DFA/UFA A, respectively.1Then, we construct the trimmed product of Aand P(this can be seen as computing A∩supp(P) while keeping the probabilities from Pon the edges of the result), yielding a PPA R=(α,γ,{Δa}a∈Σ).2Intuitively, Rrepresents not only the words of L(A) but also their probability in P.Now,letΔ=a∈ΣΔabe the matrix that expresses, for any p, q ∈Q[R], the significance of getting from pto qvia any a∈Σ. Further, it can be shown (cf. the proof of Lemma 1in [43]) that the matrix Δ∗, representing the significance of going from pto qvia any w∈Σ∗,canbe computed as (I−Δ)−1. Then, to get PrP(L(A)), it suffices to take α·Δ∗·γ. Note that, due to the determinisation/disambiguation step, the obtained value indeed is PrP(L(A)) despite Rbeing a PPA. 1In theory, disambiguation can produce smaller automata, but, in our experiments, determinisation proved to work better. 2Ris not necessarily a PA since there might be transitions in Pthat are either removed or copied several times in the product construction. Approximate Reduction of Finite Automata 161 3.2 Automata Reduction Using Probabilistic Distance We now exploit the above introduced probabilistic distance to formulate the task of approximate reduction of NFAs as the following two optimisation problems. GivenanNFAAand a PA Pspecifying the distribution PrP:Σ∗→0,1,we define –size-driven reduction: for n∈N, find an NFA Asuch that |A|≤nand the distance dP(A, A) is minimal, –error-driven reduction: for ∈0,1, find an NFA Asuch that dP(A, A)≤and the size |A|is minimal. The following lemma shows that the natural decision problem underlying both of the above optimization problems is PSPACE-complete, which matches the complexity of computing the probabilistic distance as well as that of the exact reduction of NFAs [38]. Lemma 2. Consider an NFA A,aPAP, a bound on the number of states n∈N, and an error bound ∈0,1.ItisPSPACE-complete to determine whether there exists an NFA Awith nstates s.t. dP(A, A)≤. The notions defined above do not distinguish between introducing a false positive (Aaccepts a word w/∈L(A)) or a false negative (Adoes not accept awordw∈L(A)) answers. To this end, we define over-approximating and under-approximating reductions as reductions for which the additional conditions L(A)⊆L(A)andL(A)⊇L(A) hold, respectively. Ana¨ıve solution to the reductions would enumerate all NFAs Aof sizes from 0uptok(resp. |A|), for each of them compute dP(A, A), and take an automaton with the smallest probabilistic distance (resp. a smallest one satisfying the restriction on dP(A, A)). Obviously, this approach is computationally infeasible. 4 A Heuristic Approach to Approximate Reduction In this section, we introduce two techniques for approximate reduction of NFAs that avoid the need to iterate over all automata of a certain size. The first approach under-approximates the automata by removing states—we call it the pruning reduction—while the second approach over-approximates the automata by adding self-loops to states and removing redundant states—we call it the self-loop reduction. Finding an optimal automaton using these reductions is also PSPACE-complete, but more amenable to heuristics like greedy algorithms. We start with introducing two high-level greedy algorithms, one for the sizeand one for the error-driven reduction, and follow by showing their instantiations for the pruning and the self-loop reduction. A crucial role in the algorithms is played by a function that labels states of the automata by an estimate of the error that will be caused when some of the reductions is applied at a given state. 162 M. ˇ Ceˇska et al. 4.1 A General Algorithm for Size-Driven Reduction Algorithm 1. A greedy size-driven reduction Input :NFAA=(Q, δ, I, F), PA P,n≥1 Output:NFAA,∈Rs.t. |A|≤nand dP(A, A)≤ 1V←∅; 2for q∈Qin the order A,label (A,P )do 3V←V∪{q};A←reduce(A, V ); 4if |A|≤nthen break ; 5return A,=error(A, V, label(A, P)); Algorithm 1 shows a general greedy method for performing the size-driven reduction. In order to use the same high-level algorithm in both directions of reduction (over/under-approximating), it is parameterized with three functions: label,reduce,and error. The real intricacy of the procedure is hidden inside these three functions. Intuitively, label(A, P) assigns every state of an NFA Aan approximation of the error that will be caused wrt the PA Pwhen a reduction is applied at this state, while the purpose of reduce(A, V )istocreateanew NFA Aobtained from Aby introducing some error at states from V.3Further, error(A, V, label(A, P)) estimates the error introduced by the application of reduce(A, V ), possibly in a more precise (and costly) way than by just summing the concerned error labels: Such a computation is possible outside of the main computation loop. We show instantiations of these functions later, when discussing the reductions used. Moreover, the algorithm is also parameterized with a total order A,label(A,P )that defines which states of Aare processed first and which are processed later. The ordering may take into account the precomputed labelling. The algorithm accepts an NFA A,aPAP,andn∈Nand outputs a pair consisting of an NFA Aof the size |A|≤nand an error bound such that dP(A, A)≤. The main idea of the algorithm is that it creates a set Vof states where an error is to be introduced. Vis constructed by starting from an empty set and adding states to it in the order given by A,label (A,P ), until the size of the result of reduce(A, V ) has reached the desired bound n(in our setting, reduce is always antitone, i.e., for V⊆V, it holds that |reduce(A, V )|≥|reduce(A, V )|). We now define the necessary condition for label,reduce,anderror that makes Algorithm 1 correct. Condition C1 holds if for every NFA A,PAP,andasetV⊆Q[A], we have that (a) error(A, V, label(A, P)) ≥dP(A, reduce(A, V )),(b)|reduce(A, Q[A])|≤ 1,and(c)reduce(A, ∅)=A. C1(a) ensures that the error computed by the reduction algorithm indeed over-approximates the exact probabilistic distance, C1(b) ensures that the algorithm can (in the worst case, by applying the reduction at every state of A)for any n≥1 output a result |A|of the size |A|≤n,andC1(c) ensures that when no error is to be introduced at any state, we obtain the original automaton. Lemma 3. Algorithm 1 is correct if C1 holds. 3We emphasize that this does not mean that states from Vwill be simply removed from A—the performed operation depends on the particular reduction. Approximate Reduction of Finite Automata 163 4.2 A General Algorithm for Error-Driven Reduction Algorithm 2. A greedy error-driven reduction. Input :NFAA=(Q, δ, I, F ), PA P,∈0,1 Output:NFAAs.t. dP(A, A)≤ 1←label(A, P); 2V←∅; 3for q∈Qin the order A,label (A,P )do 4e←error(A, V ∪{q},); 5if e≤then V←V∪{q}; 6return A=reduce(A, V ); In Algorithm 2, we provide a high-level method of computing the error-driven reduction. The algorithm is in many ways similar to Algorithm 1; It also computes a set of states V where an error is to be introduced, but an important difference is that we compute an approximation of the error in each step and only add qto Vif it does not raise the error over the threshold . Note that the error does not need to be monotone, so it may be advantageous to traverse all states from Qand not terminate as soon as the threshold is reached. The correctness of Algorithm 2 also depends on C1. Lemma 4. Algorithm 2 is correct if C1 holds. 4.3 Pruning Reduction The pruning reduction is based on identifying a set of states to be removed from an NFA A, under-approximating the language of A. In particular, for A= (Q, δ, I, F), the pruning reduction finds a set R⊆Qand restricts Ato Q\R, followed by removing useless states, to construct a reduced automaton A= trim(A|Q\R). Note that the natural decision problem corresponding to this reduction is also PSPACE-complete. Lemma 5. Consider an NFA A,aPAP, a bound on the number of states n∈N, and an error bound ∈0,1.ItisPSPACE-complete to determine whether there exists a subset of states R⊆Q[A]of the size |R|=nsuch that dP(A, A|R)≤. Although Lemma 5shows that the pruning reduction is as hard as a general reduction (cf. Lemma 2), the pruning reduction is more amenable to the use of heuristics like the greedy algorithms from Sects. 4.1 and 4.2. We instantiate reduce,error,andlabel in these high-level algorithms in the following way (the subscript pmeans pruning): reducep(A, V )=trim(A|Q\V),errorp(A, V, ) = min V∈Vp{(q)|q∈V}, where Vpis defined as follows. Because of the use of trim in reducep,for a pair of sets V,V s.t. V⊂V, it holds that reducep(A, V ) may, in general, yield the same automaton as reducep(A, V ). Hence, we define a partial order pon 2Qas V1pV2iff reducep(A, V1)=reducep(A, V2)andV1⊆V2,and use Vpto denote the set of minimal elements wrt Vand p. The value of the 170 M. ˇ Ceˇska et al. Table 2. Results for the http-attacks regex, size-driven reduction, |Aatt|= 142, |ARed att |= 112, time(Reduce)=7.9s, time(label2 sl )= 28.3min, time(Exact) = 14.0–16.4 min. k|AApp att | |A att |Error bound Exact error Traffic error 0.1 11 (1.1 s) 5(0.4s)1.0 0.9972 0.9957 0.2 22 (1.1 s) 14 (0.6 s) 1.0 0.8341 0.2313 0.3 33 (1.1 s) 24 (0.7 s) 0.081 0.0770 0.0067 0.4 44 (1.1 s) 37 (1.6 s) 0.0005 0.0005 0.0010 0.5 56 (1.1 s) 49 (1.2 s) 3.3e–06 3.3e–06 0.0010 0.6 67 (1.1 s) 61 (1.9 s) 1.2e–09 1.2e–09 8.7e–05 0.7 78 (1.1 s) 72 (2.4 s) 4.8e–12 4.8e–12 1.2e–05 0.9 100 (1.1 s) 93 (4.7 s) 3.7e–16 1.1e–15 0.0 Table 2presents the results of the size-driven self-loop reduction for NFA Aatt describing httpattacks regexes. We can observe that the error bounds provide again a very good approximation of the real probabilistic distance. On the other hand, the difference between the probabilistic distance and the traffic error is larger than for Amal. Since all experiments use the same probabilistic automaton and the same traffic, this discrepancy is accounted to the different set of packets that are incorrectly accepted by ARed att . If the probability of these packets is adequately captured in the traffic model, the difference between the distance and the traffic error is small and vice versa. This also explains an even larger difference in Table 3(presenting the results for Abd constructed from http-backdoor regexes) for k∈0.2,0.4. Here, the traffic error is very small and caused by a small set of packets (approx. 70), whose probability is not correctly captured in the traffic model. Despite this problem, the results clearly show that our approach still provides significant reductions while keeping the traffic error small: about a 5-fold reduction is obtained for the traffic error 0.03 % and a 10-fold reduction is obtained for the traffic error 6.3 %. We discuss the practical impact of such a reduction in Sect. 5.3. Performance of the Approximate Reduction Table 3. Results for http-backdoor,sizedriven reduction, |Abd|=1,352, time(label2 sl )= 19.9min, LUTs(ARed bd )=2,266. k|AApp bd | |A bd |Error bound Traffic error LUTs 0.1 135 (1.2 m) 8(2.6s) 1.0 0.997 202 0.2 270 (1.2 m) 111 (5.2 s) 0.0012 0.0631 579 0.3 405 (1.2 m) 233 (9.8 s) 3.4e–08 0.0003 894 0.4 540 (1.3 m) 351 (21.7 s) 1.0e–12 0.0003 1063 0.5 676 (1.3 m) 473 (41.8 s) 1.2e–17 0.0 1249 0.7 946 (1.4 m) 739 (2.1 m) 8.3e–30 0.0 1735 0.9 1216 (1.5 m) 983 (5.6 m) 1.3e–52 0.0 2033 In all our experiments (Tables 1, 2and 3), we can observe that the most time-consuming step of the reduction process is the computation of state labellings (it takes at least 90 % of the total time). The crucial observation is that the structure of the NFAs fundamentally affects the performance of this step. Although after Reduce, the size of Amal is very similar to the size of Aatt, computing label2 sl takes more time (28.3 min vs. 38.7 s). The key reason behind this slowdown is the determinisation (or alternatively disambiguation) process required by the product construction underlying the state labelling computation (cf. Sect. 4.4). For Aatt, the process results in a significantly larger product when compared to the product for Amal. The size of the product directly determines the time and space complexity of solving the linear equation system required for computing the state labelling. Approximate Reduction of Finite Automata 171 As explained in Sect. 4, the computation of the state labelling label2 sl can exploit the “tentacle” structure of the NFAs appearing in NIDSes and thus can be done component-wise. On the other hand, our experiments reveal that the use of Reduce typically breaks this structure and thus the component-wise computation cannot be effectively used. For the NFA Amal, this behaviour does not have any major performance impact as the determinisation leads to a moderate-sized automaton and the state labelling computation takes less than 40 s. On the other hand, this behaviour has a dramatic effect for the NFA Aatt. By disabling the initial application of Reduce and thus preserving the original structure of Aatt, we were able to speed up the state label computation from 28.3 min to 1.5 min. Note that other steps of the approximate reduction took a similar time as before disabling Reduce and also that the trade-offs between the error and the reduction factor were similar. Surprisingly, disabling Reduce caused that the computation of the exact probabilistic distance became computationally infeasible because the determinisation ran out of memory. Due to the size of the NFA Abd, the impact of disabling the initial application of Reduce is even more fundamental. In particular, computing the state labelling took only 19.9 min, in contrast to running out of memory when the Reduce is applied in the first step (therefore, the input automaton is not processed by Reduce in Table 3; we still give the number of LUTs of its reduced version for comparison, though). Note that the size of Abd also slows down other reduction steps (the greedy algorithm and the final Reduce reduction). We can, however, clearly see that computing the state labelling is still the most time-consuming step. 5.3 The Real Impact in an FPGA-Accelerated NIDS Further, we also evaluated some of the obtained automata in the setting of [5] implementing a high-speed NIDS pre-filter. In that setting, the amount of resources available for the regex matching engine is 15,000 LUTs5and the frequency of the engine is 200 MHz. We synthesized NFAs that use a 32-bit-wide data path, corresponding to processing 4 ASCII characters at once, which is— according to the analysis in [5]—the best trade-off between the utilization of the chip resources and the maximum achievable frequency. A simple analysis shows that the throughput of one automaton is 6.4 Gbps, so in order to reach the desired link speed of 100 Gbps, 16 units are required, and 63 units are needed to handle 400 Gbps. With the given amount of LUTs, we are therefore bounded by 937 LUTs for 100 Gbps and 238 LUTs for 400 Gbps. We focused on the consumption of LUTs by an implementation of the regex matching engines for http-backdoor (ARed bd )andhttp-malicious (ARed mal ). –100 Gbps: For this speed, ARed mal can be used without any approximate reduction as it is small enough to fit in the available space. On the other hand, ARed bd 5We omit the analysis of flip-flop consumption because in our setting it is dominated by the LUT consumption. 172 M. ˇ Ceˇska et al. without the approximate reduction is way too large to fit (at most 6 units fit inside the available space, yielding the throughput of only 38.4 Gbps, which is unacceptable). The column LUTs in Table 3shows that using our framework, we are able to reduce ARed bd such that it uses 894 LUTs (for k= 0.3), and so all the needed 16 units fit into the FPGA, yielding the throughput over 100 Gbps and the theoretical error bound of a false positive ≤3.4×10−8 wrt the model PHTTP . –400 Gbps: Regex matching at this speed is extremely challenging. The only reduced version of ARed bd that fits in the available space is the one for the value k=0.1 with the error bound almost 1. The situation is better for ARed mal .Inthe exact version, at most 39 units can fit inside the FPGA with the maximum throughput of 249.6 Gbps. On the other hand, when using our approximate reduction framework, we are able to place 63 units into the FPGA, each of the size 224 LUTs (k= 0.6) with the throughput over 400 Gbps and the theoretical error bound of a false positive ≤8.7×10−8wrt the model PHTTP . 6 Conclusion We have proposed a novel approach for approximate reduction of NFAs used in network traffic filtering. Our approach is based on a proposal of a probabilistic distance of the original and reduced automaton using a probabilistic model of the input network traffic, which characterizes the significance of particular packets. We characterized the computational complexity of approximate reductions based on the described distance and proposed a sequence of heuristics allowing one to perform the approximate reduction in an efficient way. Our experimental results are quite encouraging and show that we can often achieve a very significant reduction for a negligible loss of precision. We showed that using our approach, FPGA-accelerated network filtering on large traffic speeds can be applied on regexes of malicious traffic where it could not be applied before. In the future, we plan to investigate other approximate reductions of the NFAs, maybe using some variant of abstraction from abstract regular model checking [42], adapted for the given probabilistic setting. Another important issue for the future is to develop better ways of learning a suitable probabilistic model of the input traffic. Data Availability Statement and Acknowledgements. The tool used for the experimental evaluation in the current study is available in the following figshare repository: https://doi.org/10.6084/m9.figshare.5907055.v1. We thank Jan Koˇrenek, Vlastimil Koˇsaˇr, and Denis Matouˇsek for their help with translating regexes into automata and synthesis of FPGA designs, and Martin ˇ Z´adn´ık for providing us with the backbone network traffic. We thank Stefan Kiefer for helping us proving the PSPACE part of Lemma 1and Petr Peringer for testing our artifact. The work on this paper was supported by the Czech Science Foundation project 16-17538S, the IT4IXS: IT4Innovations Excellence in Science project (LQ1602), and the FIT BUT internal project FIT-S-17-4014. Approximate Reduction of Finite Automata 173 References 1. The Snort Team: Snort. http://www.snort.org 2. Becchi, M., Wiseman, C., Crowley, P.: Evaluating regular expression matching engines on network and general purpose processors. In: Proceedings of ANCS 2009, pp. 30–39. ACM (2009) 3. Koˇrenek, J., Kobiersk´y, P.: Intrusion detection system intended for multigigabit networks. In: Proceedings of DDECS 2007. IEEE (2007) 4. Kaˇstil, J., Koˇrenek, J., Leng´al, O.: Methodology for fast pattern matching by deterministic finite automaton with perfect hashing. In: Proceedings of DSD 2007, pp. 823–829. IEEE (2009) 5. Matouˇsek, D., Koˇrenek, J., Puˇs, V.: High-speed regular expression matching with pipelined automata. In: Proceedings of FPT 2016, pp. 93–100. IEEE (2016) 6. Kumar, S., Dharmapurikar, S., Yu, F., Crowley, P., Turner, J.S.: Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Proceedings of SIGCOMM 2006, pp. 339–350. ACM (2006) 7. Tan, L., Sherwood, T.: A high throughput string matching architecture for intrusion detection and prevention. In: Proceedings of ISCA 2005, pp. 112–122. IEEE (2005) 8. Kumar, S., Turner, J.S., Williams, J.: Advanced algorithms for fast and scalable deep packet inspection. In: Proceedings of ANCS 2006, pp. 81–92. ACM (2006) 9. Becchi, M., Crowley, P.: A hybrid finite automaton for practical deep packet inspection. In: Proceedings of CoNEXT 2007. ACM (2007) 10. Becchi, M., Crowley, P.: An improved algorithm to accelerate regular expression evaluation. In: Proceedings of ANCS 2007, pp. 145–154. ACM (2007) 11. Kumar, S., Chandrasekaran, B., Turner, J.S., Varghese, G.: Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia. In: Proceedings of ANCS 2007, 155–164. ACM (2007) 12. Yu, F., Chen, Z., Diao, Y., Lakshman, T.V., Katz, R.H.: Fast and memory-efficient regular expression matching for deep packet inspection. In: Proceedings of ANCS 2006, pp. 93–102. ACM (2006) 13. Liu, C., Wu, J.: Fast deep packet inspection with a dual finite automata. IEEE Trans. Comput. 62(2), 310–321 (2013) 14. Luchaup, D., De Carli, L., Jha, S., Bach, E.: Deep packet inspection with DFAtrees and parametrized language overapproximation. In: Proceedings of INFOCOM 2014, pp. 531–539. IEEE (2014) 15. Mitra, A., Najjar, W.A., Bhuyan, L.N.: Compiling PCRE to FPGA for accelerating SNORT IDS. In: Proceedings of ANCS 2007. ACM (2007) 127–136 16. Brodie, B.C., Taylor, D.E., Cytron, R.K.: A scalable architecture for highthroughput regular-expression pattern matching. In: Proceedings of ISCA 2006, pp. 191–202. IEEE (2006) 17. Clark, C.R., Schimmel, D.E.: Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns. In: Y. K. Cheung, P., Constantinides, G.A. (eds.) FPL 2003. LNCS, vol. 2778, pp. 956–959. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45234-8 94 18. Hutchings, B.L., Franklin, R., Carver, D.: Assisting network intrusion detection with reconfigurable Hardware. In: Proceedings of FCCM 2002, pp. 111–120. IEEE (2002) 19. Sidhu, R.P.S., Prasanna, V.K.: Fast regular expression matching using FPGAs. In: Proceedings of FCCM 2001, pp. 227–238. IEEE (2001) 174 M. ˇ Ceˇska et al. 20. Puˇs, V., Tobola, J., Koˇsaˇr, V., Kaˇstil, J., Koˇrenek, J.: Netbench: framework for evaluation of packet processing algorithms. In: Proceedings of ANCS 2011, pp. 95–96. ACM/IEEE (2011) 21. Maletti, A., Quernheim, D.: Optimal Hyper-Minimization. CoRR abs/1104.3007 (2011) 22. Gawrychowski, P., Je˙z, A.: Hyper-minimisation made efficient. In: Kr´aloviˇc, R., Niwi´nski, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 356–368. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03816-7 31 23. Gange, G., Ganty, P., Stuckey, P.J.: Fixing the state budget: approximation of regular languages with small DFAs. In: D’Souza, D., Narayan Kumar, K. (eds.) ATVA 2017. LNCS, vol. 10482, pp. 67–83. Springer, Cham (2017). https://doi. org/10.1007/978-3-319-68167-2 5 24. Parker, A.J., Yancey, K.B., Yancey, M.P.: Regular Language Distance and Entropy. CoRR abs/1602.07715 (2016) 25. Mohri, M.: Edit-distance of weighted automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 1–23. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-44977-9 1 26. Malcher, A.: Minimizing finite automata is computationally hard. Theor. Comput. Sci. 327(3), 375–390 (2004) 27. Hopcroft, J.E.: An N.logN Algorithm for Minimizing States in a Finite Automaton. Technical report (1971) 28. Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973–989 (1987) 29. Bustan, D., Grumberg, O.: Simulation-based minimization. ACM Trans. Comput. Log. 4(2), 181–206 (2003) 30. Champarnaud, J., Coulon, F.: NFA reduction algorithms by means of regular inequalities. Theor. Comput. Sci. 327(3), 241–253 (2004) 31. Mayr, R., Clemente, L.: Advanced automata minimization. In: Proceedings of POPL 2013, pp. 63–74. ACM (2013) 32. Etessami, K.: A hierarchy of polynomial-time computable simulations for automata. In: Brim, L., Kˇret´ınsk´y, M., Kuˇcera, A., Janˇcar, P. (eds.) CONCUR 2002. LNCS, vol. 2421, pp. 131–144. Springer, Heidelberg (2002). https://doi.org/ 10.1007/3-540-45694-5 10 33. Clemente, L.: B¨uchi automata can have smaller quotients. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 258–270. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22012-8 20 34. Vardi, M.Y.: Automatic verification of probabilistic concurrent finite state programs. In: Proceedings of SFCS 1985, pp. 327–338. IEEE (1985) 35. Baier, C., Kiefer, S., Klein, J., Kl¨uppelholz, S., M¨uller, D., Worrell, J.: Markov chains and unambiguous B¨uchi automata. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9779, pp. 23–42. Springer, Cham (2016). https://doi.org/ 10.1007/978-3-319-41528-4 2 36. Baier, C., Kiefer, S., Klein, J., Kl¨uppelholz, S., M¨uller, D., Worrell, J.: Markov Chains and Unambiguous B¨uchi Automata. CoRR abs/1605.00950 (2016) 37. Mohri, M.: A disambiguation algorithm for finite automata and functional transducers. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol. 7381, pp. 265–277. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31606-7 23 38. Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22(6), 1117–1141 (1993) Approximate Reduction of Finite Automata 175 39. Carrasco, R.C., Oncina, J.: Learning stochastic regular grammars by means of a state merging method. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS, vol. 862, pp. 139–152. Springer, Heidelberg (1994). https://doi.org/10.1007/3-54058473-0 144 40. Thollard, F., Clark, A.: Learning stochastic deterministic regular languages. In: Paliouras, G., Sakakibara, Y. (eds.) ICGI 2004. LNCS (LNAI), vol. 3264, pp. 248– 259. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30195-0 22 41. Mayr, R., et al.: Reduce: A Tool for Minimizing Nondeterministic Finite-Word and B¨uchi Automata. http://languageinclusion.org/doku.php?id=tools. Accessed 30 Sept 2017 42. Bouajjani, A., Habermehl, P., Rogalewicz, A., Vojnar, T.: Abstract regular (Tree) model checking. STTT 14(2), 167–191 (2012) 43. ˇ Ceˇska, M., Havlena, V., Hol´ık, L., Leng´al, O., Vojnar, T.: Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection. Technical report. CoRR abs/1710.08647 (2017) 44. ˇ Ceˇska, M., Havlena, V., Hol´ık, L., Leng´al, O., Vojnar, T.: Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection. Figshare (2018). https://doi.org/10.6084/m9.figshare.5907055.v1 45. Hartmanns, A., Wendler, P.: TACAS 2018 Artifact Evaluation VM. Figshare (2018). https://doi.org/10.6084/m9.figshare.5896615 Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.