Study On Network Intrusion Detection Systems Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Security is a big issue for all networks in todays enterprise environment. Hackers and intruders have made many successful attempts to bring down high-profile company networks and web services. Many methods have been developed to secure the network infrastructure and communication over the Internet, among them the use of firewalls, encryption, and virtual private networks.

Intrusion detection is a relatively new addition to such techniques. Intrusion Detection System or IDS is software, hardware or combination of both used to detect intruder activity. Using intrusion detection methods, the system administrator can collect and use information from known types of attacks and find out if someone is trying to attack the network or particular hosts. The information collected this way can be used to identity and recover the host or network from the attack.

1.1.1 Intrusion Avoidance Systems

Intrusion Avoidance Systems can be devised by combining of Intrusion Prevention Systems (IPS) and Intrusion Response Systems (IRS). The connection between the two is that IPSs are a subset of Intrusion Detection and Response Systems. Intrusion Prevention Systems are souped-up IDSs, with the ability to stop packets on the fly whenever an attack is discovered.

An IDS without any form for output would be useless. It is necessary to have some sort of output from an IDS in order to analyze and respond to the intrusion. Automatic response systems replace the administrator with a decision making device. This means that if an alert is raised by the IDS a response is issued immediately. Though it is an automatic response system it requires to be supervised by the administrator as is it not intelligent as a human administrator and therefore suspect to response inadequately or incorrectly.

1.1.2 Network Intrusion Detection Systems (NIDS)

Among the two major types of IDS, such as Host based IDS which is mainly for a single machine and Network based intrusion detection which is for computers connected through a network, NIDS needs to be concentrated more as it has to capture large amount of data packets traveling on the network media (cables, wireless) and match them to a database of signatures. Internet-based security attacks have proliferated in recent years, with buffer over-runs, cross-site scripting, and denial-of-service among the most prominent and damaging forms of attack (commonly called exploits). A successful attacker can then initiate follow-on exploits, such as compromising the local system to gain administrator-level access or initiating denial of service attacks against other machines. The most popular operating systems regularly publish security updates, but the combination of poorly-administered machines, uninformed users, a vast number of targets, and ever-present software bugs has allowed exploits to remain ahead of patches.

1.2 MOTIVATION

SNORT, an open source software is the most popular NIDS which identifies intrusion attempts by comparing every inbound and outbound packet against a ruleset. Rules in the set represent characteristics of known attacks, such as the protocol type, port number, packet size, packet content (both strings and regular expressions), and the position of the suspicious content. Each new type of attack leads to new rules, with rulesets growing rapidly and are stored in a database. The most recently-released freely-available SNORT rulesets have over 4000 rules.

The processing required by a network intrusion detection system such as SNORT is quite high, since the system must decode the data, reassemble network packets into streams, preprocess the data, scan the streams for matches against the specified string content and regular expressions, and log intrusions. These requirements limit SNORT to an average packet processing rate of about 699 Mb/s on a modern host machine.

The SNORT syntax features are highly complex, and also matching the whole SNORT database rules with every incoming packets consumes a lot of processing time to find out whether that packet is an infected one. This complexity motivates the packet pre-filtering design.

1.2.1. Packet Pre-Filtering

Packet pre-filtering is a process of matching only a small portion of all the SNORT rules with every incoming packet and then going for a complete match only if the partial match is positive. Thereby pre-filtering skips large number of rules that are normally being matched unnecessarily.

Based on the literatures that, if the rarest substring (a small portion of the string) of a pattern does not appear, then the whole pattern will definitely not match, Packet pre-filtering approach is a means to resolve, or at least alleviate the problems of processing delays. Pre-filtering can be hardware or software based. Since many of the IDS rules can have similar header information, matching only the header fields of the IDS rules with the incoming packets will not produce effective results. Therefore pre-filtering approach matches a small portion header + a small suffix/prefix of the payload from each IDS rule with the data packets in the first step of pattern matching. The result of this partial match is a small subset of rules that are candidates for a full match. Given this pruned set of rules that can apply to a packet, a second-stage, full-match engine can sustain higher throughput.

Since hardware based pre-filtering approaches has some limitation which are discussed in chapter 2, a program based pre-filtering has been chosen for this research.

Though, matching a minimum number of SNORT rules per packet could result in minimizing processing and improves the scalability of the system the candidate rules for full match are being matched sequentially to find out the infection. Again this motivates the parallel pre-filtering approach in this research to still reduce the processing time than sequential pre-filtering.

1.2.2. Parallelism in pattern matching

In this research, Parallelism is introduced in the complete pattern matching of the pre-filtering process which could effectively enhance the speed of matching process between incoming packet contents and the selected SNORT rule sets. The candidate rules which are coming out as the result of partial pattern matching, could be matched in parallel using threads in order to eliminate the sequential processing delays.

This thesis has contributions to address performance issues both by packet pre-filtering by means of software approach and parallelizing the full pattern matching in order to improving the processing speed considerably.

1.3. THESIS ORGANIZATION

This thesis is organized into the following chapters:

Chapter 1: Introduction. This chapter gives a general introduction about IDS, NIDS, SNORT, motivation for packet pre-filtering and parallelism and the organization of this thesis.

Chapter 2: Literature review. This insists the literature review done on pre-filtering and parallelism in pattern matching for this research.

Chapter 3: Background theory. This chapter discusses the background theory of this research which includes packet and SNORT rule set structure, different algorithms used for pattern matching and parallelism.

Chapter 4: Development and Implementation of parallel packet pre-filtering approach. This chapter includes the analysis and implementation of the chosen algorithms using parallel fashion of execution and graph based results for performance enhancement.

Chapter 5: Conclusion and Future work. Discusses the conclusion and the future research related to this work

CHAPTER 2

LITERATURE REVIEW

Many strategies and algorithms have been proposed in the literature, most of them on hardware based packet pre-filtering, parallelism in pattern matching, parallelism in NIDS performance using Ethernet cards using different simulators. To propose the hybrid approach where packet pre-filtering by software means and parallelism in pre-filtered candidate rules are combined to ensure a high performance and therefore saving processing time are considered carefully.

Ioannis Sourdis et al.[1] have presented Pre-filtering, a powerful hardware-based technique aimed to reduce the processing requirements for intrusion detection. They claimed that implementing the header matching portion of a NIDS system together with a small prefix match (in the range of 4-8 characters) can eliminate most of the rules and determine a handful of applicable rules, that can then be checked more efficiently by a full-match module. The technique is amenable to various kinds of parallelism at the full-match module whether implemented in hardware or in software. Their pre-filtering module is designed for reconfigurable hardware and therefore could update its supported IDS ruleset via reconfiguration.

In the past, pre-filtering techniques have been applied for static IDS pattern matching. In order to match multiple IDS patterns in software, Markatos et al. [2] use a two step approach that detects whether an incoming stream contains the entire pattern characters (possibly in arbitrary positions) and only then perform a full match of the search pattern.

More recently, Antonatos et al. [3] proposed Piranha, a pre-filtering algorithm which extends the first checking step with for 32-bit "rare" substrings that will enable fewer rules to be matched in the second step. The Piranha algorithm was based on the idea that if the rarest 4-byte substring of a pattern inside the packet payload is found, then it can be assumed that that pattern matches. Piranha itself can only handle patterns with length greater or equal to 4.

Baker and Prassana[4] employed a pre-filtering technique for reconfigurable IDS pattern matching. They modified their "shift-and-compare" design, reducing the area cost, adding some uncertainty and allowing false positives, to filter out streams that would not match their pattern set.

Most hardware-based techniques suffer from the limitation that they search the payload for all patterns in the entire ruleset while ignoring rule headers, i.e. packet header information. In essence, they search for thousands of patterns while the packet header might specify that the focus can be in only a few tens or so patterns. If some patterns are only one or two bytes long, one could easily create packets that cause hundreds of accurate yet in-consequential matches. Even normal traffic packets would often trigger invalid rules. If such pre-filtering methods are used stand-alone, they will often be ineffective. On the other hand, if used in conjunction with a higher-level software IDS they could be tricked into flooding it with false positive pattern matches, possibly causing it to waste more time "sorting through the garbage" than it would scanning the entire payload.

Software implementations of IDS, such as SNORT, can group the rules into different sets based on their rule headers. Specifically, TCP and UDP rules can be grouped based on their source and destination ports, ICMP rules based on their ICMP type and IP rules based on their protocol. This grouping creates sets of rules that are compatible and may be activated at the same time. This fact allows software IDS processing a packet to discover a single rule set that covers a large portion of possible attacks and perform a single pay-load scan for the patterns in that set [5].

V. Dimopoulos et al[6], describes that using merely the header description results in multiple applicable IDS rules, which can be up to several hundreds in the case of a SNORT- like IDS. However, when adding to the filter a few bytes of payload patterns, this candidate set of IDS rule can be significantly reduced. That is because it would be relatively rare for a single incoming packet to match payload search patterns of multiple rules.

While considering packet classification, there exist several opinions. Chunyan Li and Yongtian Yang [7], classified each packet into two fields: Header and Content, and they defined a packet filter as a rule set, since these rule sets determine which packets are allowed to pass and which are reject, when incoming packets are arrived, they inspect its header information, if it matches with one rule sets or not. In Addition, they divided packets filter into two policies: first policy is to allow all packets to pass except specific types of packets, second policy which is consider contrary of the first policy, is to reject all except specific types of packets. Thus, their algorithm is divided into two parts: first part is in charge of building the decision tree, while the second part is the searching part which is used to find the matching rule in the decision tree for an input packet.

While Yoshiyuki et al., [8] consider packet filter consist of two sequence procedures. The first procedure is to classify each incoming packet into one of three possibilities: access, drop or forward, according to the rules and content of the packet, the 2nd procedure is the action it will take according to the classification procedure.

When parallelism is concerned in packet payload filtering, Adnan A. Hnaif et a[9], parallelized the quick search algorithm using OpenMP and Pthread (Posix) and made a comparison between them; they have also determined the required number of threads according to many factors. Through this they managed to speed up the filtering process for more than 40%. They had also applied this method into NIDS to enhance the speed of matching process between incoming packet contents and SNORT rule sets.

CHAPTER 3

BACKGROUND THEORY

3.1 PACKET STRUCTURE

Figure 3.1 describes the structure of TCP packet.

Source Port

Destination Port

Sequence number

Acknowledgement number

Data offset

Reserved

Flags

Window

Checksum

Urgent pointer

Options(padding)

Data(Variable)

Figure 3.1: Structure of a TCP packet

Source Port and Destination Port-Identifies source and destination computers.

Sequence Number-Usually specifies the number assigned to divided data streams.

Acknowledgment Number-Contains the sequence number the sender of the packet expects to receive.

Data Offset-Indicates the number of 32-bit words in the TCP header.

Reserved-Remains reserved for future use.

Flags-Carries a variety of control information, including the SYN and ACK bits used for connection establishment, and the FIN bit used for connection termination.

Window-Specifies the size of the sender's receive window

Checksum-Indicates whether the header was damaged in transit.

Urgent Pointer-Points to the first urgent data byte in the packet.

Options-Specifies various TCP options.

Data-Contains upper-layer information.

3.2 SNORT IDS

SNORT is an open source NIDS that is commonly used in industry. SNORT contains a database of rules with several thousands of attack signatures. Each of SNORT's rules contains a header and several content fields. The header part consists of a packet identifier (protocol, source/destination IPs and ports), while the content part contains one or more patterns that may have some correlation between them. A rule is matched only if all of its patterns are matched with the expected correlation among them. The SNORT rule syntax is the de facto industrial standard. NIDS devices which are compliant with this standard have a great advantage - the same database can be transparently imported from one engine to another. As opposed to several hardware based NIPS devices, our solution is fully SNORT compatible. Internally, SNORT supports software based pattern matching algorithms.

3.2.1 Structure of a SNORT rule

The structure of a SNORT rule is shown in Figure 3.2,

Rule Header

Rule Option

Figure 3.2: Structure of a SNORT rule

All SNORT rules have two logical parts: rule header and rule options.

The rule header contains information about what action a rule takes.

The options part usually contains an alert message.

3.2.2 Structure of SNORT rule header.

The structure of the SNORT rule header is shown in Figure 3.3,

Action

Protocol

Address

Port

Direction

Address

Port

Figure 3.3: Structure of a SNORT rule header

The action part of the rule determines the type of action taken when a rule is exactly matched against a data packet.

The protocol part is used to apply the rule on packets for a particular protocol only. Some examples of protocols used are IP, ICMP, UDP etc.

The address parts define source and destination addresses. There are two address fields in the rule. Source and destination addresses are determined based on direction field. For example, if the direction field is "->", the Address on the left side is source and the Address on the right side is destination. The content is represented in hexadecimal. An example rule is as follows,

alert tcp 192.168.1.0/24 any -> ![192.168.1.0/24] any \

(content: "|47 45 54|"; msg: "GET matched";)

3.3 SNORT PACKET PRE-FILTERING

SNORT IDS rules include statements which, for example, define payload regions where specific patterns should be matched (depth, offset) or require a pattern to be matched within a number of bytes after matching another pattern (within, distance). The SNORT syntax features create fundamental difficulties in IDS implementation and motivate packet pre-filtering design.

Table 3.1 depicts some of the SNORT syntax features which make the IDS rules more complicated. Consequently, rules might specify the packet payload part where a pattern should be matched, relative either to the beginning or the end of a packet or relative to a previously matched pattern. In addition, commands such as byte test and byte jump select and test a byte payload field using several numerical or logical operators. Each SNORT rule might specify different payload constraints. Therefore, each rule would possibly require a separate FSM-like module to keep track of the satisfied conditions, specify the parts of the payload which are valid for each pattern to match, and store payload byte fields to be tested using the byte test and byte jump commands.

Table 3.1: Current SNORT syntax features which make IDS tasks more computationally intensive.

In software, the SNORT rule features might not affect the entire implementation of the detection engine, since the matching is presumably sequential in partial pre-filtering stage. On the other hand, in hardware, where the implementation needs to be in parallel (since performance is critical), these syntax extensions introduce significant cost and might also limit performance.

The key observation in packet pre-filtering is that matching a small part of each rule's payload combined with matching the header information (Source & Destination IP/Port and Protocol) can substantially reduce the set of the possibly matching rules compared to using only header matching as in previously proposed approaches. Using merely the header description results in multiple applicable IDS rules, which can be up to several hundred in the case of a SNORT like IDS. However, when adding to the filter a few bytes of payload patterns, this candidate set of IDS rule can be significantly reduced. That is because it would be relatively rare for a single incoming packet to match payload search patterns of multiple rules.

This IDS packet pre-filtering approach relies on minimizing the set of rules required to be matched per incoming packet. Figure 3.4 offers the block diagram of the packet pre-filtering design. The pre-filtering module is designed for algorithm based software approach and therefore can be implemented into SNORT. The top part of the figure 4 illustrates the overall system arrangement. Incoming packets are first filtered through the packet pre-filtering module (matches the first part of each rule i.e. header plus a few bytes of payload pattern); subsequently, only the remaining part of the candidate rules, reported by the pre-filtering, are fully matched in a separate hardware or software module/sub-system. This way, the flow of the incoming packets is not stalled, since the parts of the rules matched in the pre-filtering phase are not matched again.

Figure 3.4: Packet pre-filtering

The bottom part of figure 3.4 expands in detail the internals of the pre-filtering block. The incoming packets feed a field extractor module, which performs header delineation, field separation, and payload extraction. The packet header is sent to the Header Matching module that performs the necessary header classification and reports a bitmask of potential matching rules. The payload is sent to the partial Payload Match module which also reports a bitmask of potential matching rules. Depending on each rule's definition, the two bitmasks are combined to provide the logical AND of the two pieces of information (the AND gate in the figure) or can be used directly, i.e. in the case of rules with header constraints but without payload checks or the opposite. Using priority encoder the list of possible matches is reported to the full match module.

3.4 EXACT STRING MATCHING ALGORITHMS

A number of algorithms have been proposed for pattern matching in a NIDS. The performance of each algorithm may vary according to the case in which it is applied.

Aho and Corasick [10] proposed an algorithm for concurrently matching multiple strings. Aho-Corasick (AC) algorithm used the structure of a finite automation that accepts all strings in the set. The automation processes the input characters individually and tracks partially matching patterns. The AC algorithm has proven linear performance, making it suitable for searching a large set of rule signatures.

Markatos et al. [11] have designed an exclusion-based signature-matching algorithm known as ExB. ExB is based on a simple logic, that is, if pattern P contains at least one character not in text T, then Pis not in T. Every time a new payload arrives, the payload is preprocessed to construct an occurrence bitmap to record the occurrence of distinct characters within the payload. ExB then identify the patterns individually to check whether any characters appear in the pattern but not the payload. If such characters do exist then the pattern is skipped since matching is impossible.

The Boyer-Moore algorithm [12] is widely used because of its efficiency in single-pattern matching problems. The Boyer-Moore algorithm was designed for searching for a single pattern from a given text and performs well in this role. However, the current implementation of Boyer- Moore in SNORT is not efficient in seeking multiple patterns from given payloads.

Coit et al. [13] implemented Gusfield's version of the Commentz-Walter algorithm called AC BM, which uses suffix trees for the good suffix heuristic.The algorithm is a Boyer-Moore-like algorithm applied to a set of keywords held in an AC-like keyword tree overlaying the common prefixes of the keywords. AC BM searches multiple patterns simultaneously and operates from 1.02 to 3.32 times as fast as the Boyer-Moore implementation on SNORT. However, several unresolved issues have hampered their works with the full SNORT ruleset.

CHAPTER 4

ANALYSIS AND IMPLEMENTATION OF PARALLEL PACKET PRE FILTERING

4.1 THE BOYER-MOORE ALGORITHM

For this research, this algorithm is used for pattern matching because of its better average case performance. This algorithm uses two heuristics to reduce the number of character comparisons required for pattern matching. Both heuristics are triggered by mismatches. The first heuristic, commonly referred to as the bad character heuristic, works as follows: if the search pattern contains the mismatching character, the pattern is shifted so that the mismatching character is aligned with the rightmost position at which it appears in the pattern. Meanwhile, if the mismatching character does not appear in the search pattern, the pattern is shifted so that the first character in the pattern is one position later than that of the mismatching character in the given text. The second heuristic commonly referred to as the good suffixes heuristic, works as follows: if a mismatch is found in the middle of the pattern, the search pattern is shifted to the next occurrence of the suffix in the pattern.

BOYER_MOORE_MATCHER (T, P)

Figure 4.1 shows the steps in Boyer-Moore algorithm

Input:    Text with n characters and Pattern with m characters

Output: Index of the first substring of T matching P

Compute function last

i ← m-1

j ← m-1

Repeat

    If P[j] = T[i] then

        if j=0 then

            return i        // we have a match

        else

            i ← i -1

            j ← j -1

    else

        i ← i + m - Min(j, 1 + last[T[i]])

        j ← m -1

until i > n -1

Return "no match"

Figure 4.1 Boyer Moore String Matching Algorithm

4.2 PARALLEL THREAD ALGORITHM

Based on the Pthread algorithm a slightly modified Parallel thread algorithm has been constructed in order to be implement the parallel execution of candidate rules using threads in java platform.

Input: Candidate rules

Output: Match or Mismatch with rule set

Step 1: receive the candidate rule from partial pre-filtering

Step 2: start time

Step 3: create threads and start threads

Step 4: report in case of full match

Step 6: terminate threads

Step 7: stop time and calculate elapsed time.

Figure 4.2 shows the steps in Parallel thread algorithm

4.3 IMPLEMENTATION

Initially the incoming packets from a network are received by the SNORT IDS where packet classification could be done to separate the header and the payload portion. A database is maintained to store the necessary fields of the header and the payload information of sample SNORT rulesets. When the packet information is input, it is first matched partially and then completely if suspected with the records of the SNORT ruleset database. For this partial and complete pattern match, Boyer-Moore algorithm has been used for this research.

After the partial match the suspected rues have been taken separately to another table from where they are undergoing for compete match in parallel using parallel thread algorithm. The structure of the SNORT ruleset database is shown in table 4.1

Table 4.1 SNORT ruleset Table structure

Field Name

Data Type

Field Size

Description

RID

Number

5

Rule ID number

Action

Text

5

Action to be taken by the IDS

Protocol

Text

5

Name of the Protocol

SIP

Number

10

Source machine IP

SPORT

Number

5

Source Port number

DIP

Number

10

Destination machine IP

DPORT

Number

5

Destination Port number

Pattern

Text

255

Pattern string

MSG

Memo

>255

Message alert

Initial value of the SNORT ruleset database are shown in table 4.2

Table 4.2 SNORT ruleset

Table1

RID

ACTION

PROTOCOL

SIP

SPORT

DIP

DPORT

PATTERN

MSG

101

Alert

TCP

192.168.0.5

20

192.168.0.10

80

abcdef

Source IP is restricted

102

Alert

TCP

192.168.0.5

20

192.168.1.5

20

defghi

Destionation IP is restricted

103

Alert

ICMP

192.168.24.17

23

192.168.22.13

20

bcdibnr

ICMP is restricted

104

Alert

UDP

192.168.11.2

21

192.168.0.3

2474

xyxxyxy

Infected packet

If a partial analysis finds a match the candidate rules are extracted to another table from as shown in table 4.4. The structure of the candidate rule table is shown in table 4.3.

Field Name

Data Type

Field Size

Description

RID

Number

5

Rule ID number

Pattern

Text

255

Pattern string

Table 4.3 Structure of the candidate rule table

Table2

RID

PATTERN

101

abcdef

104

Xyxxyxy

Table 4.4 Candidate rules

The rules in the candidate rule table are given to threads in parallel and executed for the complete pre-filtering analysis.

4.4 ANAYSIS OF THE RESULTS OF PARALLEL PACKET PRE-FILTERING

Two types of analysis have been carried out in this research for the implementation of parallel packet pre filtering and tested using sample inputs.

Pre-filtering Analysis

Partial Analysis

In partial pre-filtering analysis the header fields and a substring of 3 characters from the pattern string of every rule in the SNORT database had been selected for testing and matched with the incoming packet. If a match is found at one or more locations in the packet, that rule had been selected completely and stored in table2 for complete analysis.

Complete Analysis

In compete analysis, the complete pattern of the selected rules had been matched with the packet using parallel execution and reported in case of a match.

Parallel execution of candidate rules

When the candidate rules would be extracted for another table, they had been given to threads for parallel execution.

Four scenarios are defined to evaluate the Pre-filtering Analysis that are as follows.

4.4.1 Evaluation of Pre-filtering Partial Analysis

Table 4.5 Pre-filtering Scenarios

Scenarios

Characteristics

Scenario 1

Header matches and payload does not matches

Scenario 2

Both Header and payload does not matches

Scenario 1: Header matches and payload does not matches

Figures 4.3 inputs given for scenario1.

Figure 4.3(a) Figure 4.3(b)

Figure 4.3(a) Figure 4.3(b)

Figure 4.3(c) Figure 4.3(d)

Figure 4.3(e) Figure 4.3(f)

Output for scenario1:

Figure 4.4: Output for scenario1

Scenario 2: Both Header and payload does not matches

Inputs: Table 4.6 inputs for scenario 2

Fields

Source IP

Source Port

Destination IP

Destination Port

Protocol

Pattern

Values

1

1

1

1

1

1

Output:

Figure 4.5: Output for scenario2

4.4.2 Evaluation of Pre-filtering Complete Matching Analysis

Pre-filtering analysis goes for a complete matching only when the partial matching of the IDS rules matches with the incoming packets. Complete match is necessary only when the following scenarios occur.

Scenario 3

Header does not matches and payload matches

Scenario 4

Both Header and payload matches

Scenario 3: Header does not matches and payload matches

Inputs: Table 4.7

Fields

Source IP

Source Port

Destination IP

Destination Port

Protocol

Pattern

Values

1

1

1

1

1

abcdefghxyxy

Output:

Figure 4.6: Output for scenario3

Scenario 4: Both Header and payload matches

Inputs: Table 4.8

Fields

Source IP

Source Port

Destination IP

Destination Port

Protocol

Pattern

Values

192.168.0.5

20

192.168.0.10

80

TCP

abcdefghxyx

Output:

Figure 4.7: Output for scenario 4

4.4.3 Parallel execution of candidate rules

Parallel executions of candidate rules are required only when the above scenario 3 occurs. When the pre-filtering analysis matches some rules partially, those partially matched candidate rules will be taken to a separate table in the database, from where they can be fully matched in parallel using threads. The following are the three different analysis performed in order to measure the performance effectiveness.

Analysis

Characteristics

Analysis 1

Actual pattern matching analysis without using pre-filtering and parallelism

Analysis 2

Using Pre-Filtering analysis

Analysis 3

Using Parallel Pre-Filtering analysis

Table 4.9 Different analysis based of parallel pre-filtering

Analysis 1: Actual pattern matching analysis without using pre-filtering and parallelism

Figure 4.8: Output of Actual pattern matching analysis without using pre-filtering and parallelism

Analysis 2: Using Pre-Filtering analysis

Figure 4.9: Output of Pre-filtering anaysis

Analysis 3: Using Parallel Pre-Filtering analysis

Figure 4.10: Output of Parallel Pre-filtering anaysis

4.5 RESUTS AND DISCUSSION

The processing times were calculated in each stage and the results were compared for improved performance by means of processing time. Therefore both pre-filtering algorithm and parallel pattern matching for candidate rules have been implemented and evaluated for the better performance of the intrusion detection.

Table 4.10 shows the evaluation report of the three analysis. Different number of rules are tested to prove the reduction in the execution time respectively in anaysis 1, 2 and 3.

Table 4.10 Evauation of Anaysis1, Anaysis 2 and Anaysis 3

No. of rules/Analysis

Anaysis 1

Anaysis 2

Anaysis 3

4 rules

0.034

0.022

0.01

15 rules

0.135

0.073

0.035

25 rules

0.206

0.116

0.045

50 rules

0.381

0.215

0.072

From the parameters given in table 4.10, an evaluation graph has been created to compare the performance improvement. Figure 4.11 shows that when the number of rules increases the parallel pre-filtering analysis gives a better performance result by reducing the processing time.

A sample of 50 SNORT rules had been tested for this research using normal complete pattern matching (Anaysis 1), pre-filtering by sequential complete matching (Analysis 2) and pre-filtering by parallel complete matching (Analysis 3). The number of rules are taken in X axis and the processing time (sec) are taken in Y axis.

Figure 4.11 Performance evaluation parallel pre-fitering

The graph shows the when the number of rules increases parallel pre-filtering improves the performance by reducing the processing time considerably.

Therefore from the above different analysis we can conclude that the processing time can be reduced considerably by pre-filtering analysis when compared to actual complete analysis, which can again be reduces by parallelizing the complete analysis of pre-filtering.

CHAPTER 5

CONCLUSION AND FUTURE WORK

In this research, a partial and complete pre-filtering and parallel pre-filtering in complete rule matching are presented and simulation was done using Java based programs for the high performance in Network Intrusion Detection Systems. SNORT version 2.8 had been used for rule set checking using Boyer-Moore algorithm for multi pattern matching. These pattern matching and parallel candidate rule matching algorithms were evaluated based on the header and payload patterns of SNORT IDS. in the implementation stage, various number of rules were taken for performance measurement and the results were produced in graphical format to prove the effective reduction in the execution time. The major objective of providing high performance by reducing the processing time has been assured due to the pre-filtering analysis and thread based parallelism in candidate rule matching.

For further research the optimum number of threads for parallel execution of candidate rules could be measured for fixed and variable size of data packets and SNORT rules. An improved architecture of Intrusion Response System can be designed for this particular Intrusion Detection framework. Also mathematical heuristic formulae could be generated to analyze the false positive and false negative nature of the IDS and to be improved based on this research. Real time NIDS environment could be set up to test this proposed agenda.

BIBLIOGRAPHY

[1] Ioannis Sourdis, Vasilis Dimopoulos, Dionisios Pnevmatikatos, Stamatis Vassiliadis "Packet Prefiltering for Network Intrusion Detection" ANCS'06, December 3-5, 2006, San Jose, California, USA. ACM 1595935800/06/0012

[2] E. Markatos, S. Antonatos, M. Polyhronakis, and K. G.Anagnostakis. "Exclusion-based signature matching for intrusion detection." In Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN), pages 146-152, November 2002.

[3] S. c, M. Polychronakis, P. Akritidis, K. D. Anagnostakis, and E. P. Markatos. "Piranha: Fast and memory-efficient pattern matching for intrusion detection." In Proceedings 20th IFIP International Information Security Conference (SEC 2005), May 2005.

[4] Z. K. Baker and V. K. Prasanna. A Methodology for Synthesis of Efficient Intrusion Detection systems on FPGAs. In IEEE Symposium on Field-Programmable Custom Computing Machines, April 2004.

[5] Sourcefire. SNORT rule optimizer. In www.sourcefire.com/whitepapers/sf SNORT20 ruleop.pdf, June 2002.

[6] V. Dimopoulos, G. Papadopoulos, and D. Pnevmatikatos. "On the importance of header classification in hw/sw network intrusion detection systems." In Proceedings of the 10th Panhellenic Conference on Informatics (PCI), November 11-13, 2005.

[7] Chunyan Li and Yongtian Yang. (2003). "Predictable packet Filtering based on decision Tree Classifies, IEEE". Pages 1345-1349.

[8] Yoshiyuki, Yamashita and mosato Tsuru. (2007). "Code Optimization for Packet filters." Proceedings of the 2007 international symposium on Applications and the internet workshops (SAINTW' 07) IEEE.

[9] Adnan A. Hnaif, Mohammad Alhalaiqah, Omar Abouabdalla, Sureswaran Ramadass, and Mohammed M. Kadhum, "Parallel Quick Search Algorithm to Speed Packet Payload Filtering in NIDS" International conference on Network application, Protocols and Services, Nov 2008.

[10] AHO, A. AND CORASICK, M. 1975. Efficient string matching: An aid to bibliographic search. Commun.the ACM, 18, 6, 333-343.

[11] ANAGNOSTAKIS ,K.G., MARKATOS, E. P., ANTONATOS, S., AND POLYCHRONAKIS,M. E2xB:Adomainspecific string matching algorithm for intrusion detection. Proceedings of the 18th IFIP International Information Security Conference (SEC2003).

[12] BOYER, R. S. AND MOORE, J. S. 1977. A fast string searching algorithm. Commun. the ACM, 20, 10, 762-772.

[13] C. J. Coit, S. Staniford and J. Mchlerney. (2001). Towards faster string matching for Intrusion Detection or Exceeding the speed of SNORT. IEEE, pp.367-373.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.