A parallel cluster intrusion detection system for backbone network

Abstract

The high traffic volume of backbone networks requires that the structure model of traditional intrusion detection systems must be changed and efficient intrusion detection technologies must be adopted for backbone network intrusion detection systems. On the basis of in-depth research on key technologies for backbone network intrusion detection systems, a rule-based intrusion detection system for backbone networks—BNIDS (Backbone Network Intrusion Detection System)—has been designed and implemented. The parallel cluster detection model, packet capture mechanism, and rule-based analysis engine of BNIDS are discussed. Experimental results show that the scalable BNIDS can perform real-time intrusion detection and analysis on backbone network traffic.

With the rapid development of the Internet, cyber attacks keep occurring. As a complementary measure to firewall, a cybersecurity protection tool, network intrusion detection systems are developing rapidly^[1]. In recent years, the ravages of worms such as RedCode, Nimda, and Dvldr, as well as the frequent occurrence of distributed attacks such as DOS/DDOS, have had a significant impact on the world’s economy and people’s lives. A significant feature of these attacks is that they tend to bring about significant anomalies in backbone network traffic, while such anomalies are difficult to observe in local subnets, so it is necessary to select backbone networks as an intrusion monitoring point. Due to the increasing network bandwidth, traffic in a backbone network usually reaches several Gbps or even tens of Gbps. In such a high-speed network environment, intercepting all network packets is difficult, not to mention doing complex intrusion detection analysis. Therefore, in order to realize backbone network–based real-time intrusion detection, it is necessary to change the structure model of traditional intrusion detection systems and adopt efficient intrusion detection technologies.

To this end, this paper designs and implements a high-performance Backbone Network Intrusion Detection System (BNIDS) on the basis of an in-depth study of efficient intrusion detection technologies.

1 Design and implementation of the BNIDS system architecture

At a backbone network monitoring point, when a single node is used to perform intrusion analysis on network data by means of monitoring, even if the computer uses SMP, the maximum amount of data traffic it can process is about 110 Mbps, so a single node can not adapt to the requirements of real-time intrusion detection in a high-speed backbone network. In this paper, a backbone network–based parallel cluster analysis and processing model is proposed by using load balancing techniques, and the cluster system is designed to be scalable by using the SPMD computational model. When the network traffic increases, the data processing capacity of the cluster detection system can be expanded by adding processing nodes and other methods. The system architecture model of BNIDS is shown in Figure 1. The load balancer is connected to the backbone network through an optical splitter to intercept the data streamer signal at the physical layer. In order to offload the incoming data to the sensors in the cluster system, the load balancer needs to be configured with 100 Mbps/1000 Mbps Ethernet ports to convert the data access from the backbone optical signal into the data access from the Ethernet card required by the intrusion detection system. In addition to the basic data offloading function, the load balancer can also perform simple data filtering according to the manager’s configuration policy to reduce the data load on sensors.

An abstract network diagram. At the top, nodes labeled Router1 and Router2 are both connected to the IDS Load Balancer. N lines emerge from the IDS Load Balancer that are connected to individual sensors (Sensor1, Sensor2, Sensor3, …, SensorN) inside a dotted box labeled N-Node Sensor Cluster. All the sensor nodes are then connected to a single Switch, which is connected to a single Manager. — Figure 1: System architecture model of BNIDS

Most of the traffic in the backbone network is based on TCP. For TCP traffic, an ideal load balancing algorithm should satisfy the following requirements: 1) Data is almost evenly distributed to each node to ensure load balancing among nodes; 2) Bidirectional data for any TCP connection is offloaded to the same node to ensure that there is no data dependency between nodes. However, the load balancing algorithm should not be overcomplex, as that would hinder the rapid offloading of data in a high-speed backbone network. For this reason, the load scheduler employs an algorithm based on connection rotation scheduling to perform reasonable, fine-grained offloading of network data at the granularity of connections. In TCP/IP, the 4-tuple (source IP address, destination IP address, source port, and destination port) uniquely identifies a connection. The connection rotation scheduling algorithm is described as follows: When the first packet (SYN packet) of the connection arrives, the load balancer takes the the most recently assigned node number mod N and adds 1 to it to get the shunt address of the new connection (N is the number of nodes), and sends the packet to the node. At the same time, the load balancer records the connection (in the form of a 4-tuple) and the corresponding node number in a hash table and updates the most recently assigned node number. In this way, when the next packet of the connection arrives, the address of the selected node can be obtained from the hash table, and the packet will continue to be sent to the same node. When the connection terminates or times out, the load balancer removes the connection from the hash table.

For other protocol types, the offloading address is obtained by performing a simple hash operation on the 2-tuple (source IP address, destination IP address). The formula is: destination node number = (source IP address ⊕ destination IP address) mod N, where N is the number of nodes in the cluster system. Sensors in BNIDS are used to capture Ethernet packets and perform protocol analysis, restoration, and rule-based matching. The manager receives alert events generated by the sensors, performs a comprehensive analysis, and displays the results. The implementation framework of sensors is shown in Figure 2.

A dotted line surrounds all elements of the diagram except for the Manager. At the bottom, a node labeled Network Traffic leads to a node labeled Packet Capture, which in turn leads to Protocol Analysis & Decode, then to Rule-Based Detection Engine. The Rule-Based Detection Engine has an input from the Rules Database on the right, and outputs to Alert on the left and Manager at the top. A line from Alert crosses the dotted box to lead to the Manager, and a line from Manager leads back inside the dotted box to Rules Database. — Figure 2: Sensor structure

1.1 Packet capture mechanism based on zero-copy techniques

Traditional network intrusion detection systems typically capture network link layer data frames by calling the packet capture library Libpcap^[2]. In a high-traffic network environment, a Libpcap-based packet capture mechanism is inefficient and often results in the loss of a large number of packets. The main reason for this phenomenon is that the transmission of packets is always done through the kernel of the operating system, which involves a number of critical paths such as system calls and data copying. A system call is equivalent to an interrupt with interrupt number 0x80, and the CPU time consumed by the system call for saving the interrupt site and switching processes can be quite significant when there is a lot of network traffic. Memory bandwidth is one of the main performance bottlenecks of the system. Multiple memory copy operations consume a lot of CPU cycles and memory resources, thus seriously increasing the processing overhead of the system.

In order to improve the packet capture performance of the intrusion detection system, it is necessary to reduce the intermediate links in the packet transmission process, bypass the kernel of the operating system, reduce or eliminate data copies, and reduce the consumption of limited system resources. To this end, we have designed an efficient packet capture mechanism based on zero-copy technique – Libcapture. Figure 3 compares Libcapture to the traditional packet capture mechanism libpcap. As can be seen from the figure, Libcapture consists of three parts: the Kernel Manager, the New NIC Driver, and the VNI (Virtual Network Interface). The VNI is located in the user state of the system and provides an API library for applications to access the network interface hardware. The other two parts are located in the kernel state of the system, where the Kernel Manager is responsible for virtual–physical address translation in userspace and the creation of a shared buffer ring. The Kernel Manager is only used when the virtual network interface is opened. The New NIC Driver interacts with the Kernel Manager to obtain the physical address translation table required for asynchronous DMA operation of the NIC, and initiates a DMA transfer of network packets directly between the user buffer and the network interface hardware.

The figure has two sub-figures: (a) Libpcap and (b) Libcapture. The (a) Libpcap figure is divided horizontally into three rows: User, Kernel, and one that is unlabeled indicating the external network. In the unlabeled row, there is only one node, Network Hardware Interface. This is connected by a broad white arrow to the Kernel row, which contains nodes Old NIC Driver, TCP/IP Protocol, and Raw Socket connected in series. Then this connects via a broad white arrow to the User row, where there is only a node Libpcap. The (b) Libpcapture figure is the same at the bottom with the Network Hardware Interface. Exiting the Network Hardware Interface, there is a broad white arrow that completely traverses the Kernel row and enters a Virtual Network Interface node in the User row. The Virtual Network Interface is connected by downward-pointing, thin black arrows to nodes labeled Kernel Manager and New NIC Driver in the Kernel row. New NIC Driver is connected by a bidirectional thin black arrow to Network Hardware Interface. — Figure 3: Comparison of Libpcap and Libcapture packet capture mechanisms

1.2 Rule-based detection engine design

The detection and analysis techniques commonly used in network intrusion detection systems include anomaly detection and misuse detection. The rule-based detection engine combines the advantages of misuse detection and anomaly detection, and improves the ability to detect unknown and polymorphic attacks while ensuring detection accuracy. A syntax similar to the rule description language in snort^[3] is used in the implementation of the BNIDS. A rule is divided into two parts: the rule header and the rule options. The rule header contains the source address, destination address, source port, and destination port, as well as the protocol to which it belongs, and the matching action. The rule options section uses a combination of keywords to characterize the attack. For example, the keyword content describes a string of characters in the packet payload that needs to be searched for patterns.

1.2.1 Efficient and flexible rule description language

The rule description language of BNIDS is capable of describing some common cyber attacks with as few elements as possible and in as simple a syntax as possible. In contrast to Snort rules, which can only describe packet-based feature matching, this rule language can describe not only patterns for misuse detection, but also normal profiles for anomaly detection.

For protocol analysis and status checking, the rule option tcp_flow:client_to_server,established is defined. This option indicates that the packet to be inspected is a client request and has been checked for TCP status.

The rule language is capable of describing the application-layer protocol specification so that an exception is considered to have occurred when the packet payload does not conform to the protocol specification described by the rule. For example, the rule language defines the keyword within to describe the distance between two different content matches in a packet. The rule alert tcp any any -> $HOME_NET 143 (content:"LOGIN"; content:!"|0a|"; within:100;) can be used to indicate that an alert is raised if a certain number of bytes (<=100) are found immediately after the command character LOGIN with no line terminators, indicating a new IMAP buffer overflow attack.

For DoS/DDoS attacks, the keyword counter can be defined to describe the number of packets of a certain type that appear over a period of time. The rule option counter: $THRESHOLD,$PERIOD indicates that the count of packets of a certain type exceeds the domain value $THRESHOLD within the specified $PERIOD of time.

1.2.2 Fast pattern matching algorithm with multiple rules

BNIDS employs a high-performance multi-rule detection engine for rule matching on packets. The detection engine is divided into two stages. The first stage is a multi-pattern matching search process based on the rule content; the second stage validates the other rule options after completing the rule content matching to determine if the rule actually matches the current packet.

The multi-pattern matching algorithm is the core of the rule-based detection engine, and its performance has a significant impact on the overall performance of the network intrusion detection system. Many researchers have conducted in-depth analysis of pattern matching algorithms in intrusion detection and proposed some high-performance multi-pattern matching algorithms. The Aho–Corasick^[4] algorithm is a parallel search matching algorithm using finite state automata. The AC–BM algorithm^[5] which combines the Aho–Corasick algorithm and the BM algorithm, makes use of the jump search method of the BM algorithm, but requires that patterns in the pattern set have a common prefix in order to achieve high performance. Mike Fisk^[6] et al. proposed the SBMH algorithm for searching pattern sets, showing that SBMH outperforms the Aho–Corasick algorithm when the number of rules are small. However, the Aho–Corasick algorithm outperforms the SBMH algorithm when the number of rules exceed 100.

With the continuous expansion of the attack signature database, the matching algorithm is required to have good scalability. An improved version of the Aho–Corasick algorithm is used in BNIDS. The algorithm uses multiple pattern strings to construct a finite state automaton and uses the automaton to find all pattern matches during a single scan of the text string. The improved Aho–Corasick algorithm is divided into two steps; First, it preprocesses the pattern strings in multiple rules for intrusion detection, and constructs the state of the finite state automata and the state transition function through these pattern strings; in the second step, it carries out the process of matching network packets, and when the matching search proceeds to a final state of the finite state automaton, it examines the list of matched pattern strings to determine whether their corresponding rule option matches the packet. The time complexity of the pattern matching process of the algorithm is O(n) (n is the packet length) and is independent of the number of rules.

2 Experimental results and analysis

Two machines are connected back-to-back, one as a high-traffic packet-sending machine and the other as a packet-capturing machine. (Configurations are as follows; CPU – PIII1G × 2, RAM – 2G, NIC – Intel Pro1000 Gigabit Ethernet card.) The packet capture performance of two different packet capture mechanisms, Libpcap and Libcapture, is tested for different packet sizes. The results are shown in Figure 4. As can be seen in Figure 4, the peak bandwidth of Libcapture increases as the length of the received packet increases due to the use of the zero-copy technique that eliminates the memory copy operation between the user layer and the kernel. The peak bandwidth of Libpcap does not vary much with packet size, which is a result of the use of the traditional kernel protocol stack. The peak bandwidth of Libcapture is much higher than that of Libpcap for the same packet size. This shows that Libcapture is a high-performance packet capture mechanism.

A line chart. The x-axis is labeled “Message Size/Byte” and ranges from 0 to 1600. The y-axis is labeled “Peak Throughput/Mbps” and ranges from 0 to 1000. There are two time series, Libpcap with squares and Libcapture with circles. There are data points representing message sizes of approximately 64, 128, 256, 512, 1024, and 1500 bytes. The Libpcap series stays flat at 100 Mbps for every message size. The Libcapture series increases from about 325 Mbps to 900 Mbps. — Figure 4: Packet capture performance of Libpcap versus Libcapture

Select a day’s worth of traffic data (Tcpdump file with a size of about 160 MB) using the 1998 Intrusion Detection Training Data provided by MIT Lincon Lab^[7]. Select 1000 rules from the Intrusion Detection System Rules Database. Test the amount of time taken for pattern matching for the whole dataset with different numbers of rules (experimental machine configuration: CPU – PIII1G × 2, RAM – 2G, Hard Disk – 18GSCSI, Operating System – Linux-2.4.10), as shown in Table 1. The results show that after using the improved Aho–Corasick algorithm, the amount of time taken for pattern matching in the intrusion detection system does not depend on the number of rules, which ensures that the system maintains good matching performance.

Table 1: Relationship between pattern matching time and number of rules
Number of rules	System uptime/s	Percentage of time taken for pattern matching/%	Pattern matching time/s
14	7.288	55.94	4.08
200	7.818	53.21	4.16
450	10.821	37.73	4.08
700	11.314	37.12	4.19
1000	17.193	23.54	4.04

3 Conclusion

The data analyzing and processing capacity of a single node is improved by adopting the offloading policy to reduce the processing load of a single node in the backbone network intrusion detection system, combined with the use of a packet capture mechanism based on the zero-copy technique and a fast matching algorithm with multiple rules, thus improving the cost-effectiveness of the backbone network intrusion detection system. Practice has shown that the scalable BNIDS is capable of performing real-time sophisticated intrusion analysis of backbone traffic.

References:

[1]

AXELSSON S. Intrusion detection systems: a survey and taxonomy[R]. Technical Report 99-15, Dept, of Computer Engineering, Chalmers University, 2000.

[2]

Libpcap [EB/OL]. http://www.tcpdump.org/release/libpcap-0.7.2.tar.gz.

[3]

ROESCH M. Snort-lightweight intrusion detection for network[A]. Proceedings of LISA’99: 13^th System Administration Conference[C]. Washington; Seattle, 1999.

[4]

AHO A V, CORASICK M J. Efficient string matching: an aid to bibliographic search[J]. Communications of the ACM, 1975, 18(6):333–340.

[5]

MCALERNEY J, COIT C, STANIFORD S. Toward faster pattern matching for intrusion detection[A]. DARPA Information Survivability Conference and Exposition[C]. [s.l.]:[s.n.],2001.

[6]

FISK M, VARGHESE G. Fast content-based packet handling for intrusion detection [R], Technical Report CS2001–0670, San Diego: Department of Computer Science and Engineering, 2001.

[7]

GRAF I, LIPPMANN R, CUNNINGHAM R, et al. Results of DARPA 1998 offline intrusion detection evaluation[EB/OL]. http://ideval.ll.mit.edu/results-html-dir, 1998.

(Edited by 王小唯 (Wang Xiaowei))