Cybersecurity Systems such as network intrusion detection systems (NIDS) successfully use artificial intelligence technologies and other anomaly-based approaches to detect malicious activity. But only the signature approach allows you to completely eliminate recognition errors. This is especially relevant for critical infrastructure facilities. However, a significant drawback of signature-based tools is the high computational complexity: the NIDS has in real time to look through an intensive flow of incoming data against a lot of signatures -registered signs of known attacks. Therefore, the developers of such systems turn to hardware implementation, primarily on a reconfigurable platform, that is, using field programmable gate arrays (FPGA). The property of FPGAs to quickly reprogram their internal structure gives reconfigurable cybersecurity systems unprecedented flexibility, allowing them to adapt to external conditions. There are many different approaches to construct schemes to recognize patterns (which are parts of the signatures), as well their variations, modifications and improvements. Choosing the optimal technical solution for recognizing a specific set of patterns is not a trivial task. Besides having qualitative information about the variety of known schemes, it is strongly needed to be able to quickly quantify reconfigurable components to build on them optimized signature-based cybersecurity systems. This requires in turn to effectively handling the patterns that are important parts of FPGA-based schemes of NIDS' recognition components. The paper proposes a pattern set formalization description and a technique to order patterns that simplifies calculating quantitative characteristics of recognition schemes without performing expensive procedure of digital circuit synthesis using CAD tool.
The signature approach, due to the precise execution of the recognizing malicious activity, is still a
relevant technology used in such protection tools as network intrusion detection systems (NIDS) and
other cybersecurity tools. Due to the increase in the size of signature databases and the high
bandwidth of modern networks, traditional software solutions can no longer meet the demands placed
on the performance of such systems. Hardware approaches are increasingly used to speed up the
resource-intensive procedure of multi-pattern matching [
A comprehensive analysis of numerous studies from around the world was performed by author in
[
Here CAM – Content-addressable memory; TCAM – ternary CAM; DFA / NFA – deterministic /
nondeterministic finite automaton; H+R+Cmp – cascaded matching scheme based on hash-functions,
read-only memory and digital comparators [
Each of approaches has advantages and disadvantages. Researchers offer modifications to the basic circuits, use a variety of methods, tricks and techniques in an attempt to increase their efficiency and overcome the shortcomings of each approach.
There is a need for a tool to quantify the technical characteristics of each solution in order to work
with them productively. In [
In this paper, a technique for dealing with patterns of signature databases is proposed, which allows simplifying the procedures of estimation and comparison of various technical solutions of reconfigurable signature-based cybersecurity systems.
The rest of this paper is organized as follows. Section 2 briefly considers the approach to the building based on content-addressable memory and digital comparators. Section 3 discusses the ordering technique principles as a base for the formalization of pattern set properties. Section 4 introduces quantitative descriptions of hardware recognition schemes for making quick estimations of resource costs. Experiments to test the proposed technique are given in the 5th section. Section 6 concludes the research.
The survey on hardware solutions for signature-based security systems [
Let’s remind some moments about the approach based on content-addressable memory and digital
comparators analyzed in [
Content-addressable memory devices have been specifically designed to meet the needs of fast matching. They operate in the opposite manner to traditional random access memory (RAM) devices. If the RAM stores the given data at a certain address and finds it at this address, then the CAM, on the contrary, looks for the location (i.e. address, or cell number) of the data in the storage device by their content or indicates absence. Digital comparators (DCs) are the fast-acting basis of CAMs; therefore, further these two names are sometimes used as synonyms.
The easiest way to detect the presence of a suspicious pattern in a data stream is a set of DCs that compare the bytes of the input sequence with all the characters of this pattern. The Figure 2 a shows an example that is able to recognize "ABC" pattern. It contains input conveyor composed of 8-bit registers RGi, three digital comparators CMPi, – one for every character, and the "AND" gate. In common case the number of elements depends from pattern set parameters. This scheme has been called the Basic Content-Addressable Memory Scheme, or BsCAM Scheme.
BsCAM scheme provides very high performance. In fact, it is able to output the result in one clock cycle after the input data is fed. Its structure is regular, that is also an advantage. The main drawback of the scheme is the huge hardware costs. To create a BsCAM scheme, you need as many DCs as there are characters in the pattern dictionary. In addition, multi-input AND gates are needed to join the output signals from comparators.
To reduce the hardware costs of the CAM-based recognizing scheme the DCs can be reused. In the
extreme case only one DC is allocated for each character, and the resulting match signal is obtained
by joining digital delay circuits with help of AND gates, as shown in example in Figure 2 b. In this
figure, the delay circuits DEL1 and DEL2 provide one cycle and two cycle’s delays respectively.
Such a solution is called the Recognition Scheme Based on Decoded CAM or DCAM Scheme,
because the full set of DCs in fact composes a decoder [
Further research has made it possible to achieve a greater reduction in hardware costs with a partial
recognition scheme. Long patterns can be split into shorter pieces and matched sequentially. It is
enough to delay only the partial match signal instead of using many circuits of long delay for large
patterns. Figure 3 shows a 31-character pattern recognition scheme built according to this idea. This
solution has been called the Partially Decoded CAM Recognition Scheme or DpCAM Scheme [
Experience shows that DCAM and DpCAM schemes can reduce the consumption of FPGA hardware resources by about half compared to the basic scheme.
As we can see in the Figures 2 and 3, information that the pattern set contains actually "wired" in the structure of the recognition circuit. Therefore the parameters of the patterns significantly affect the properties of the hardware matching scheme. That is why it is very important to formalize these parameters in order to operate with them. And first of all it is necessary a technique to sort patterns in a set.
As we see in Figures 2 and 3, the information contained in the set of patterns is actually "hardwired" into the structure of the recognition scheme. Therefore, the peculiarities of pattern set significantly affect the properties of the hardware matching scheme. That is why it is very important to formalize these peculiarities in order to effectively operate with them, and first of all, a technique for sorting patterns in a set is needed.
Let's represent the set of patterns that the cybersecurity system matching module should recognize as an array of its members and a list of its parameters:
P p1, p2 , p3, ... pk , ... pσ σ, , mmin , mmax , δ, μ, μ z , ν, where p1, p2 , p3 , ... pk , ... pσ – the set of patterns itself, σ – the number of patterns in the set, – the total number of symbols in the set of patterns, mmin – the length of the shortest pattern in the set, mmax – the length of the longest pattern in the set, δ – the length distribution function, μ – the first self-similarity function, μ z – the first partial self-similarity function, ν – the second self-similarity function. Patterns are fixed sequences of symbols, each code of which belongs to a certain alphabet . In the case of encoding by bytes 0016 , 0116 , 0216 ,..., FF16 .
Self-similarity functions μ , μ z and ν are quantitative parameters of the pattern set that characterize the degree of similarity of patterns among themselves, determining the redundancy present in a set of patterns, which can be used to reduce the number of comparison operations when performing multi-pattern matching. These functions play an important role for quantifying the recognizing schemes, especially – for effective modifications of basic matching schemes grounded on CAMs and DCs. To provide quick quantification procedures, using self-similarity functions and length distribution function as well, it is necessary to formalize pattern sets of the NIDS’ signature database in order to have possibility to operate them in mathematically strict manner. Below, a technique for patterns handling is discussed, which is based on a proposed certain sorting order.
Let's sort all the patterns in the set P by increasing length, as shown in Figure 4. Columns made of squares here represent strings of characters.
Let's call "a package" a subset of patterns of the same length, ignoring how the patterns within this subset are ordered. Let's enter the index j such that it coincides with the length of the patterns in the package j = mmin, mmin +1, mmin +2, … mj, … mmax, and each subsequent value of this index must be necessarily one more than the previous one, that is, there are no gaps in the numbering. Then the length of each pattern in the set will be equal to the index of its package: mj = j.
The reverse statement is not true, since for some indices j there may not be patterns of correspondent length. Therefore, the total number of packets in the set of patterns P is generally less than the difference in the lengths of the extreme dimensions (mmax – mmin).
Let's define the length distribution function δ as a function of the index j equal to the number of patterns in the corresponding package: in the example in Figure 2 j = 3, 4, 5, … mmax, δ3 4 , δ4 1, δ5 0 , δ6 2 , δmmax 2 .
Using the length distribution function, it is convenient to calculate the number of non-zero packets and the total number of characters in the set. The total number of characters is equal to the sum of characters in each packet, which in turn is equal to the product of the length of the lines by their number in the packet:
Then the number of packets in the set P: mmax j m j jmmin mmax j j .
jmmin 0, x 0 NotZx 1, x 0 .
To count the number of packets in the set P, we need to define the zero inequality function: j mmin mmax NotZ j .
To estimate quantitative parameters of technical solutions for signature cybersecurity systems, it is also necessary to determine the self-similarity functions of the set of patterns P.
The first self-similarity function μ (s, l) of the set of patterns P is equal to the total number of symbols with the code s( s ), located at the l-th position of all patterns of this set (the numbering of the position j of the symbol in the pattern is carried out from the end of the pattern to the beginning). For example, for P = {"SHIP", "HIS", "HER", "IN"} μ ("S", 4) = 1; μ ("H", 3) = 3; μ ("I", 2) = 3; μ ("P", 1) = 1; μ ("S", 1) = 1; μ ("N", 4) = 0; μ ("N", 3) = 0; μ ("N", 2) = 0, where the image of the character in quotes indicates its code in the corresponding encoding.
It is difficult to write down the expression for the first self-similarity function μ in an analytical form; however, using the proposed technique, it is simply to calculate all its values algorithmically to use in the software implementation.
The first partial self-similarity function μ z (s, j) of the set of patterns P is equal to the total number of symbols with the code s( s ), located periodically at positions (j – 1) k z, j = 2, 3, 4, … (z – 1), k = 1, 2, 3, ... mj z of all patterns of this set (the numbering of the position of the j symbol in the pattern is also carried out from the end of the pattern to the beginning). For example, for z =4 and P = {"43214321", "HGFA4EDA4CBA", "555515555", "277727} μ z ("4", 4) = 4; μ z ("3", 3) = 2; μ z ("2, 2) = 4; μ z ("1", 1) = 3; μ z ("A", 1) = 3; μ z ("A", 3) = 0, where the image of the character in quotes also indicates its code in the corresponding encoding.
The first and second self-similarity functions make it possible to expose redundancy when
estimating quantitative characteristics of a recognition schemes based on decoded and partially
decoded CAM, respectively [
The second self-similarity function ν of the set of patterns P quantitatively determines the degree
of coincidence of fragments of different patterns of the signature database. It is also difficult to
formulate an analytical notation for the ν function, but it is implicitly present in signature databases
and plays an important role in estimating the quantitative characteristics of recognizing schemes
based on the Aho–Corasick algorithm [
In order to ensure the methodical rigor of the comparison of technical solutions, it is necessary to bring the calculation of resources of different types to some single conventional unit. Such a unit can be a primitive element of the FPGA internal structure, say, a Look Up Table (LUT). Then it can be assumed that all calculations are performed in conditional LUT (CLT). Using this approach, the value R of the resources required for the synthesis of any digital component will be written in the form: R L α F βB γM , (1) where L – amount of FPGA logics resources, which is required to synthesize this component (in LUTs), F – amount of distributed memory resources (in flip-flops), B – amount of block memory resources (in BRAM blocks), M – volume of on-board memory of reconfigurable accelerator (in Mb), α,β, γ – normalization coefficients of different type resources in relation to LUTs.
The hardware cost estimation function is defined as an expression that, for a given recognition scheme to be synthesized within a reconfigurable accelerator with given parameters, and a given set of patterns Pi to be recognized by this scheme, outputs a numerical estimate of the hardware costs Ri required to build this scheme. The EFs are constructed by direct calculation of all types of resources according to (1).
The work [
у 1 where x – the number of inputs of the LUT for a given FPGA, y – FAN-OUT property of internal 1, x 8 circuits of the given FPGA, x – a qualifier function to define number of LUTs 2, x 8 required to realize a 8-bit logic function depending on how many inputs the LUTs have.
As we can see, the formula (2) doesn’t contain any self-similarity function. I.e. BsCAM scheme doesn’t exploit redundancy available in pattern set. This indicates the low efficiency of the basic scheme in terms of resource consumption.
The expression of EF for the DCAM scheme (we omit intermediate calculations again) has a little more complex appearance:
mmax j 1 255 RDCAM 256x NotZμs, j j2 z 1 s0 mmax mmax δ j j 1 α 255 j2 jmmin x 1 s0
NotZμs, j μs, j 2 y 1 . (2) (3) (4)
Let's check the proposed technique of handling patterns on the example of the implementation of
the parallel combining method [
This method makes it possible to reduce the cost of building a pattern recognition module (PRM), which consists of several matching blocks (MBi), which are built on the basis of recognition schemes
The expression (3) already has a self-similarity function, namely, the first self-similarity function μ . This indicates the DCAM scheme is more effective in terms of resource consumption compared to the BsCAM scheme.
The EF for DpCAM scheme looks like even more complex:
z1 255 j 1 μ z1 s, j 1
RDpCAM 256 x j2 s0 z 1 NotZμ z1 s, j y 1 mmax j z δ j jmmin z 1 x z1 255 NotZμ z1 s, j 1 1 j modx(z 1) 1 s0 j2 y 1 .
Nevertheless, this recognizing circuit (which uses the first partial self-similarity function μ z ) is a little more effective compared to the DCAM scheme.
Expressions (3) and (4) look cumbersome, but they are calculated easily and quickly, because they contain mainly addition and rounding operations. The grate advance of using EF to quickly estimate hardware resources is that it is not necessary to perform time consuming procedures of synthesizing digital circuits using a CAD for FPGA project compilation. of different nature (Figure 5). It is possible to achieve saving of resources due to the distribution of patterns between recognition blocks in such a way that the advantages of each scheme are highlighted and the disadvantages are eliminated.
Assume that the PRM of a cybersecurity system consists of two MBs connected in parallel. Their input is concurrent with a stream of data that has to be checked for malicious content. The challenge is to optimally partition the pattern set so that the total amount of hardware required to generate the entire PRM is minimal.
To solve the task, the pattern set can be sorted by some characteristic, for example, by length. The first MB synthesizes to recognize patterns starting from the shortest to some with number j. The second MB constructs to recognize the remaining patterns. Sorting can also be done by the number of patterns of the same length. I.e. we assign the 1st portion of patterns to recognize MB1 is the largest group of patterns with the same number of characters. The 2nd part for MB1 is the closest packet in size, etc. You can also use a sort order that has the value of multiplying the length of the patterns by the number of them in the packet.
The Figure 6 shows the hardware costs minimization procedure under the following conditions:
Matching scheme of MB1 – BsCAM, MB2 – the Large Bloom Filter scheme (LBF); Method of ordering – by multiplication the length by quantity type; The pattern set – from free signature database "Community Ruleset" of the NIDS Snort, ver. 3.0, which contains = 4208 patterns from mmin = 1 to mmax = 364 character length, in total = 82081 characters; Reconfigurable accelerator – VC709 Evaluation Kit from Xilinx (Virtex-7 VX690T FPGA, Xilinx).
The abscissa shows the number of characters in the patterns that MB2 recognizes and MB1 doesn’t recognize. I.e. at the left edge of chart all patterns are matched by MB1 and none – by MB2; at the right edge – vice versa.
The ordinate axis shows the amount of hardware costs in CLTs is needed to build every of MBs or the entire PRM. The curve for the MB1 is depicted by dashed line; for MB2 – by dot-dash line, and for PRM – by solid line.
The Equipment cost line for PRM has an explicit minimum, at which the entire device requires 37% less resources than the component MB1 (when it processes all patterns alone), and 39% less than the component MB2 (when it does).
The Figure 7 depicts the experiment results under the same conditions, but MBi are built now using not basic, but modified matching schemes: MB1 created by DpCAM scheme based on CAM and comparators whereas the MB2 – by Simplified Bloom Filter (SBF) scheme.
As we can see, the cost curve for the second case, when the PRM constructed from more effective modifications of matching schemes, has a pronounced minimum as well. The entire device shows 31% less costs requirements than the MB1 (if it recognizes all the patterns), and 41% less than the component MB2. On the other hand, the absolute values of hardware costs are approximately two times less than for basic circuits.
The task of multi-pattern string matching that signature-based security systems perform is computational-intensive, and software solutions on traditional processors do not provide necessary performance already. Hardware accelerators using FPGA are suitable platform for this purpose. Content addressable memory based on digital comparators, Bloom filter based on hash-functions and Aho–Corasick algorithm implemented as a finite automaton are most promising approaches to building matching schemes. Researchers over the world have proposed a lot of modifications and improvements to the basic solutions of each approach. In fact, pattern set is "hardwired" into the structure of the recognition circuit. Therefore, its properties are very important and have to be formalized to effectively operate with matching schemes, and first of all. A technique for sorting patterns in a set is needed.
The contribution of this work is as follows. A pattern set description formalization and a technique to order patterns that simplifies calculating quantitative characteristics of recognition schemes are proposed. This allows applying more effective modifications of matching schemes to build pattern recognition modules for signature-based cybersecurity systems. Due to the use of estimation functions an expensive procedure of digital circuit synthesis using CAD tool can be eliminated.
This work was supported in part by the Informatization Program of the National Academy of Sciences of Ukraine for 2020-2024. [15] W. Jiang, Y. H. E. Yang, V. K. Prasanna, Scalable multi-pipeline architecture for high performance multi-pattern string matching, in: Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2010. doi:10.1109/IPDPS.2010. 5470374. [16] C. H. Lin, S. C. Chang, Efficient Pattern Matching Algorithm for Memory Architecture, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Article volume 19, 1 (January 2011) 33-41. doi:10.1109/tvlsi.2009.2028346. [17] I. Sourdis, D. Pnevmatikatos, Pre-decoded CAMs for efficient and high-speed NIDS pattern matching, in: Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Proceedings, 2004, pp. 258-267. doi:10.1109/fccm.2004.46.