Approximate search in misuse detection based IDSIntrusion detection systems are useful to detect and alert an operator about attacks and security policy breaches on a network. Misuse detection-based intrusion detection systems are a class of intrusion detection systems that queries signature databases for known attack patterns. Intrusion detection systems needs to inspect data in real-time and therefore needs to finish the database queries as fast as possible in order to be able to inspect all traffic. This can cause a problem since signature databases are large and increases even further in size for each new attack that is discovered. Approximate search is a method where the content in the database is organized by similarity and the search query is only checked against a reduced set of similar items based on approximation. In this thesis we will look at how approximate search techniques can be applied to reduce the time needed to inspect traffic. We will implement and perform an efficiency evaluation of the various methods. We will also try to further improve existing methods to increase the performance in intrusion detection querying. As a result we hope to find the better and more efficient method for querying signature databases in misuse detection-based intrusion detection systems.
The purpose of this thesis is to look at how various approximate search methods can be applied for improving the performance in misuse detection-based intrusion detection signature database querying. We will implement the various search methods and measure their performance against the Snort signature database in order to see how intrusion detection systems can benefit from these methods. We will also try to define an improved approximate search method to further reduce the delay of the querying and include this in our performance measurement. The results will be used to compare the efficiency of the different methods and see which method is the better for intrusion detection.
Intrusion detection, intrusion detection system, intrusion prevention system, misuse detection, IDS, IPS, performance analysis, algorithms, algorithm design and analysis, performance evaluation of algorithms, data structures, approximation, similarity measures, graph and tree search strategies, indexing methods, index generation, query processing, search process, performance evaluation.
By using an intrusion detection system, operators can detect attacks against their networks. The most commonly used type of intrusion detection systems are misuse detection-based. Misuse detection-based intrusion detection systems searches a signature database for known attack patterns to identify and alert the operator about attacks in the content of network traffic. In such systems every data packet needs to be compared in real-time against each known attack pattern in order to guard against each and every possible known attack that the operator wishes to detect. The problem with this approach is that the size of the signature database, and therefore also the time needed to search it, increases with time as new attacks are identified. As the size of the database increases, the time needed to search it will also increase. In addition to new attacks, different variations of existing attacks need individual entries in the database when patterns are checked only against an exact match and therefore also increases the size of the database further. New network equipment with higher transfer rates also adds to this problem since the interval between packets may become significantly lower and therefore give the system less time to finish the search before a new packet needs to be inspected. If the time needed to search the database for a pattern exceeds the interval between incoming packets, then packets may be ignored by the intrusion detection and as a result lead to false negatives where the intrusion detection system do not alert about an attack.
Various improvements to search algorithms in order to reduce the needed run-time of database searches have been proposed by researchers for use in document and Internet searches. Among these are approximate search methods where the content in the database is organized by similarity and the search query is only checked against a reduced set of similar items based on approximation. These methods may also be applied to intrusion detection in order to reduce the problem with search complexity. We will look at how these methods can be applied in intrusion detection and try to find which method is better for use with misuse detection signature databases.
Intrusion detection and prevention systems are an important part of the security for many different computer networks and domains. However, across all these networks the intrusion detection performance issues remains the same. At a certain point the intrusion detection systems will reach its capacity limitations and it will start dropping packets, and therefore lead to false negatives where attacks may go unnoticed by the operators.
The solution for this problem today may be to choke the network transfer rates so that the amount of traffic will not cause the intrusion detection system to misbehave, to let certain types of traffic pass without inspection, or to leave out certain attacks from the search.
Finding ways to reduce this problem will affect the entire network. If the intrusion detection systems can handle higher transfer rates then the users, operators and owners of the network may get the advantages that follows such an increase in bandwidth. Furthermore, if the intrusion detection systems can cover a larger set of attack signatures the users, operators and owners may feel confident that their networks are protected against known attacks. The perhaps largest advantage is the possibility of reducing the number of, or completly mitigate, false negatives as the attacks the intrusion detection system is configured to detect actually will be detected. From a business point of view, both increase in speed and the better coverage of attacks can be highly beneficial. We hope to provide research that will help intrusion detection and prevention system developers to create systems that can handle these performance issues better and by this also benefit all the users of such systems.
To find out which approximate search method is better for intrusion detection and prevention, the following research questions needs to be answered:
The planned contributions from this project will be our research on how approximate search algorithms can be applied to improve the performance of intrusion detection systems. Our main contribution will be an efficiency comparison of the various approximate search algorithms for use with misuse detection. The performance results will be presented as a evaluation report that can be used as reference for later research, design, development or evaluation of intrusion detection and prevention systems.
We will also try to define a new algorithm called constrained q-gram distance which may work as an alternative fast approximate search algorithm for intrusion detection. If it is possible to define such an algorithm we will also include this in our efficiency evaluation.
