Computationally intelligent agents for distributed intrusion detection system and method of practicing same

[0001] The present invention relates to a computer-implemented intrusion detection system (IDS) and method for detecting computer network intrusions in real time.

[0002] Computer intrusions and cyber attacks are on the rise. Reports by research organizations and law enforcement agencies indicate, consistently, that the number of computer-security incidents has been increasing geometrically in the last few years. As a countermeasure, organizations have begun to employ intrusion detection systems, in addition to various access control mechanisms, firewalls, and virus scanners, for protection of computer networks and information assets. Current technologies for building IDSs include statistics-based analysis methods, expert systems, learning machines, and software agents.

[0003] There are serious drawbacks of currently available IDSs, including the following,

• • [0004] centralized detection: the computation required for intrusion detection is usually carried out by a single host, resulting in very limited bandwidth in processing traffic data
  • [0005] lacking real-time performance: as a consequence of the above, the IDS either fails to detect intrusions as they are occurring, or it slows down traffic and takes time to analyze packets for intrusion analysis, at the expense of quality of service provided to users
  • [0006] low detection accuracy: high rates of false positives (false alarms of intrusion, resulting in waste of resource, and inconvenience/annoyance to users) and false negatives (actual intrusions and attacks went undetected, resulting in financial loss and damage to information asset)
  • [0007] low pattern-scalability: the number of attack signatures that the IDS is capable of learning is limited
  • [0008] low network-scalability: the number of hosts on the network that can be protected is limited; further, the configuration of the network being protected may not be changeable
  • [0009] lacking response capability: the IDS can initiate only very limited, if any at all, response actions upon detecting intrusions
  • [0010] lacking attacker tracing capability: as a consequence of the above, the IDS is not equipped for tracing attacks and collecting data for forensics
  • [0011] low adaptability: the IDS is based on detection algorithms that do not allow adjustable thresholds; further, the (learning machine based) IDS needs to be retrained once new attack patterns are known
  • [0012] inapplicability to wireless networks: the IDS is designed for wired networks and has limited capability in serving networks that allow standard and/or ad-hoc wireless networking

[0013] It is therefore an object of the present invention to provide an improved computer-implemented intrusion detection system and method for detecting computer network intrusions, especially in real time.

[0018] The present invention provides an intelligent system for real-time computer intrusion detection and is aimed to overcome the drawbacks of current IDSs. The system utilizes intelligent mobile agents that are distributed throughout the network and that cooperate to monitor user activities for detecting intrusions. Three or more types of agents are used to perform the IDS functions, as shown in FIG. 2 where part of an enterprise network is depicted.

• • [0019] Peripheral Agents: these agents are responsible for device and user authentication, data collection, feature extraction, preliminary intrusion risk assessment, and intrusion response
  • [0020] Controller Agents: these agents are responsible for general intrusion determination, peripheral agents management, and intrusion response
  • [0021] Master Agents: these agents are responsible for managing controller agents, updating and modifying user profiles and attack signatures, intrusion determination of more complicated patterns, and intrusion response

[0022] The mobile agents are equipped with learning algorithms to be capable of intelligent behavior. The agents are further equipped with algorithms to perform vulnerability scanning.

[0023] The system utilizes intelligent mobile agents that are distributed throughout the enterprise network to collectively monitor user activities, build user profiles, evaluate intrusion risk, match user activities with known attack patterns and signatures, and perform intrusion determination (i.e., deciding whether an intrusion is really taking place). The system may also be equipped to provide real-time response to intrusions.

[0024] The system has the following unique characteristics,

• • [0025] adaptable: system may be installed to protect networks of different configurations
  • [0026] scalable: system may be deployed to protect networks of different size
  • [0027] high performance: system uses kernel-based learning algorithms (such as Support Vector Machines or SVMs) to perform intrusion determination, delivering real-time protection
  • [0028] intelligent: system may work by deploying mobile agents with learning capabilities to guard various entry points and locations within the network; these agents cooperate in data collection, feature extraction, intrusion determination, attacker tracing, and intrusion response
  • [0029] wireless capable: system may be installed to protect wired, wireless, and hybrid networks including ad hoc wireless subnets

[0030] Associated with the IDS design may be a feature selection algorithm that ranks the importance of each feature (in detecting each class of intrusion patterns), by first deleting that feature for consideration and training an IDS, then the performance of the IDS is compared to the original IDS that uses all available features. Those features whose deletion result in improved IDS performance are ranked important features; those features whose deletion result in degraded performance are ranked unimportant features; and those features whose deletion do not affect IDS performance are ranked secondary features.

[0031] It is important to note that we are not claiming to have invented the SVM and Intelligent Agent technologies. Rather, we are claiming to have uniquely applied them to the problem of intrusion detection.

[0032] The present invention has the following unique features:

• • [0033] 1. Kernel-based learning algorithm (e.g., SVMs) for intrusion classification
  • [0034] 2. Separate feature ranking algorithm to aid in feature selection for intrusion monitoring
  • [0035] 3. Multiple modules for class-specific intrusion determination
  • [0036] 4. Intrusion detection modules (IDMs) implemented in intelligent software agents
  • [0037] 5. IDS includes “sensitivity selector” to adjust intrusion threshold
  • [0038] 6. Additional agents generated and dispatched automatically when IDS-related computation increases
  • [0039] 7. Dynamic agents management (assignment/recall/modification)
  • [0040] 8. Intelligent software agents capable of learning new attack patterns
  • [0041] 9. Intelligent software agents capable of detecting system vulnerability
  • [0042] 10. Suitable for wireless network IDS
  • [0043] 11. Applicable to all OS and architecture platforms
  • [0044] 12. Applicable to all network configurations
  • [0045] 13. System capable of detecting anomalous patterns and misuse/attack patterns using IDMs
  • [0046] 14. IDS includes prevention and response mechanisms
  • [0047] 15. Increased scalability, accuracy, and real-time performance over current IDSs
    1. Kernel-Based Learning Algorithm for Intrusion Classification

[0048] Kernel-based learning algorithms employ kernel functions (mathematical functions) in conjunction with a class of learning machines known as support vector machines (SVMs) to perform pattern classification. SVMs have been investigated by the inventors for IDS applications and have been found to be superior to other learning machines in critical aspects of IDS performance including classification accuracy, running time, and scalability. Using different kernel functions leads to different SVM performance in pattern classification. For implementation details: Please refer to FIG. 1. A good example overview of how a Kernel-based learning algorithm is as follows:

• [0049] Step 1: A feature extraction algorithm will be utilized to extract the important features from the network and system activities.
  • [0050] Note: An analysis will or may be made to identify the features and only these will be extracted for identifying intrusions versus normal activities.
• [0051] Step 2: A suitable kernel based algorithm will or may be applied to identify whether the activity is normal or malicious.
  • [0052] Note: In our research thus far we have tried SVMs and Neural Networks. SVMs are far superior to Neural Networks in speed and accuracy. We are working on other classes of kernel based algorithms for future improvements over SVM speed and accuracy as well.
• [0053] Step 3: Here a sensitivity selector will or may be applied, depending on how closely you want to monitor activity
  • [0054] Example: On a normal day, I might want to set my sensitivity selector to “3” which means I will be monitoring only the important or alarming features.
  • [0055] But on a sensitive day, I might want to set my sensitivity selector to “5” which means I will be monitoring every feature in the network traffic.
• [0056] Step 4: Here the final analysis will or may be made, if the activity is found to be malicious; it will or may be directed to the system administrator or in the event of an automated system, the activity will or may be blocked and recorded.
  2. Feature Ranking Algorithm

[0057] Described below is a general, performance-based input ranking method: One input feature is deleted from the data at a time; the resultant data set is then used for the training and testing of the learning machine classifier. Then the classifier's performance is compared to that of the original classifier (based on all features) in terms of relevant performance criteria. Finally, the importance of the feature is ranked according to a set of rules based on the performance comparison. The procedure is described in computer pseudo-code as follows:

• • [0058] step 1: compose the training set and the testing set; for each feature do the following
  • [0059] step 2: delete the feature from the (training and testing) data;
  • [0060] step 3: use the resultant data set to train the classifier;
  • [0061] step 4: analyze the performance of the classifier using the test set, in terms of the selected performance criteria;
  • [0062] step 5: rank the importance of the feature according to the rules;

[0063] To rank the importance of the input features (for example, in the 1998 DARPA intrusion evaluation data, there are 41 features) in an IDS based on SVMs, we consider three main performance criteria: overall accuracy of classification; training time; and testing time. Each feature will be ranked as “important”, “secondary”, or “insignificant”, according to the following sample rules that are applied to the result of a performance comparison of the original 41-feature SVM and the 40-feature SVM. The following set of rules, provided as an example, is used to illustrate the procedure.

• [0064] 1. If accuracy decreases and training time increases and testing time decreases, then the feature is important
• [0065] 2. If accuracy decreases and training time increases and testing time increases, then the feature is important
• [0066] 3. If accuracy decreases and training time decreases and testing time increases, then the feature is important
• [0067] 4. If accuracy is unchanged and training time increases and testing time increases, then the feature is important
• [0068] 5. If accuracy is unchanged and training time decreases and testing time increases, then the feature is secondary
• [0069] 6. If accuracy is unchanged and training time increases and testing time decreases, then the feature is secondary
• [0070] 7. If accuracy is unchanged and training time decreases and testing time decreases, then the feature is unimportant
• [0071] 8. If accuracy increases and training time increases and testing time decreases, then the feature is secondary
• [0072] 9. If accuracy increases and training time decreases and testing time increases, then the feature is secondary
• [0073] 10. If accuracy increases and training time decreases and testing time decreases, then the feature is unimportant
  3. Multiple Modules for Class-Specific Intrusion Determination

[0074] FIG. 1 shows a sample design of the intrusion detection mechanism that utilizes five modules. Each module is responsible for detecting attacks belonging to a specific class. The drawing, as an example, is based on the 1998 DARPA intrusion evaluation data, where patterns are determined to be either normal or belonging to one of four classes of attack patterns. In the present invention, each module is or may be implemented as an agent. Currently, we have developed 5 categories of SVM-based modules that may be implemented as agents in this invention. We have also developed 22 individual types of attack instances, and these as well as the categories can be further defined as attacks are added in the future, or as the taxonomy changes in the future. The list of 5 categories includes an alerting module that detects “normal” activity. The other four modules are honed to deal with the four classes of DARPA attacks—Probe, Denial of Service, User to Root and Root to Local. This categorization is carried out in FIG. 1 and is not meant to be an exhaustive list of potential categories of modules.

4. Intrusion Detection Modules (IDMS) Implemented in Intelligent Software Agents

[0075] Referring to FIG. 1 again, each intrusion detection module is implemented as an intelligent software agent. Each module will determine whether the current input pattern under analysis belongs to the class of patterns for which it is responsible for detection, or not. If two or more modules reach affirmative conclusions, the agent that is responsible for the most serious class of attacks prevails. For example, both module 2 and module 3 report ‘YES’, indicating that the pattern represents a ‘Probe’ attack as well as a ‘DOS’ attack, then the ‘DOS’ decision prevails.

5. IDS Includes “Sensitivity Selector” to Adjust Intrusion Threshold

[0076] Each module in IDS has a sensitivity selector to adjust the threshold of detection. A set of different features from network packets are selected for intrusion detection purpose. Each module, responsible for a specific class of patterns, may use a distinct set of features as selected by the feature ranking algorithm. The module uses more features for low-threshold detection and uses less features for high-threshold detection. Low-threshold detection reduces false negatives and is used in situations where security concern is high; high-threshold detection reduces false positives and is used where and when security concern is low. The sensitivity selector has three settings: Low, Medium, and High. The number of features used for each setting is determined by the feature ranking algorithm.

6. Additional Agents Generated and Dispatched Automatically When IDS Computation Increases

[0077] The number of peripheral agents assigned to each host or device at any given time is or may be controlled dynamically by the master agent. For example, when a wireless device is seeking connection to network, a peripheral agent will first perform device authentication, followed by user authentication. The agent then extracts features from packets for preliminary intrusion determination. If the amount of network traffic data increases beyond what can be handled by a single agent, a second agent may be dispatched to share the data-gathering and feature extraction computation.

7. Dynamic Agents Management (Assignment/Recall/Modification)

[0078] Following data-gathering and feature extraction, an agent will determine if the current pattern is normal or not. If the agent determnes that the current pattern is not normal, the four agents corresponding to ‘Probe’, ‘DOS’, ‘U2R’, and ‘R2L’ detector modules are dispatched to analyze the pattern. If the pattern is determined to be an attack pattern, another agent may be dispatched to initiate a proper response. Finally, all agents may be recalled once the user/device ends the session and disconnects or log out.

8. Intelligent Software Agents Capable of Learning New Attack Patterns

[0079] For patterns determined to be ‘suspicious’ by the peripheral agents, the controller agent and/or master agent will perform further analysis and make final determination regarding pattern classification. When the controller and master agents determine that an intrusion is occurring or has occurred, the corresponding user activities that have been logged by the peripheral agents will be recognized as constituting a new attack pattern.

9. Intelligent Software Agents Capable of Detecting System Vulnerability

[0080] The functions performed by available commercial vulnerability scanners can be implemented in software agents. Customized scanners that check for specific vulnerabilities can be implemented in agents as well. Thus, the present invention of an agent-based distributed IDS provides the capability for system vulnerability scanning.

10. Suitable for Wireless Network IDS

[0081] As shown in FIG. 2 and FIG. 3, the present invention of an agent-based distributed IDS is applicable to networks including wireless access points that allow standard wireless networking and ad-hoc wireless networking of wireless devices of different types.

11. Applicable to All OS and Architecture Platforms

[0082] The present invention of agent-based, distributed IDS is or may be operating system (OS)-independent and architecture-independent. The only requirement is that the hosts on the network, and wireless devices seeking connection to the network, can support and run the software agents.

12. Applicable to All Network Configurations

[0083] As shown in FIG. 2 and FIG. 3, the present invention is applicable to all network configurations. The only limitations that affect the applicability of the present invention of an agent-based distributed IDS are the physical ones imposed by the hardware resource of the servers, hosts, and devices, including memory size, processor speed, and network bandwidth.

13. System Capable of Detecting Anomalous Patterns and Misuse/Attack Patterns Using IDMs

[0084] As explained in 1.-8. above, the misuse or attack detection function is implemented, in a distributed fashion, in the agents. In other words, the peripheral, controller, and master agents collaborate to detect misuse or attack patterns. The anomaly detection function of current IDSs can also be implemented in the collective agents. Hence, the present invention provides for the detection of both anomalous patterns and misuse/attack patterns.

14. IDS Includes Prevention and Response Mechanisms

[0085] The prevention mechanism is provided, for example, when peripheral agents detect suspicious activities from a group of users and respond by terminating their connections, thus preventing a distributed DOS attack from taking effect. The response mechanism is or may be provided, for example, when a controller agent detects with certainty that intrusion is occurring, a master agent then directs the connection to a honey pot while simultaneously generates and dispatches peripheral agents to start attack tracing.

15. Increased Scalability, Accuracy, and Real-Time Performance

[0086] The increased performance in pattern scalability, or the ability of the IDS to learn larger and larger numbers of attack patterns, is or may be provided by the SVMs using suitable kernel functions. The increased network scalability, or the ability of the IDS to protect a network with increasing number of hosts and devices, is or may be provided by the use of agents which are generated and dispatched dynamically, in accordance with the network size, intrusion-detection computation load, and traffic conditions. The real-time performance is provided by the use of a collection of agents that share the computation and make intrusion determination decisions collectively, thus eliminating bottlenecks that are likely created by a centralized IDS.

[0087] Referring now to the drawings in detail, FIG. 1 shows SVM-based intrusion detection modules (example based on 5-class of patterns), where each module is implemented as an agent. In particular, in the notional process in FIG. 1, packet features are monitored or extracted in real time by the mobile agents. The sampling rate of this monitoring is controlled by the Sensitivity Selector.

• • [0088] The first agent (or deployed feature ranking algorithm), known as SVM1, observes the features of the packet and based on prior experience determines whether or not the packet is normal/harmless or if it may possibly be a more harmful packet that falls into one of the four DARPA categories for malicious packets. If the packet is determined not to be normal, it will immediately summon SVMs 2-5 to assist it in determining what type of attack this packet may contain.
  • [0089] The second agent, known as SVM2, observes the features of the packet and based on prior experience determines whether or not the packet has characteristics associated with a Probe class of attack.
  • [0090] The third agent, known as SVM3, observes the features of the packet and based on prior experience determines whether or not the packet has characteristics associated with a Denial of Service (or DOS) class of attack.
  • [0091] The fourth agent, known as SVM4, observes the features of the packet and based on prior experience determines whether or not the packet has characteristics associated with a User to Root (or U2R) class of attack.
  • [0092] The fifth agent, known as SVM5, observes the features of the packet and based on prior experience determines whether or not the packet has characteristics associated with a Root to Local (or R2L) class of attack.
  • [0093] If SVMs 2-5 determine that the attack falls into a malicious category, they will report this back to the central controller agent and then carry out whatever reactions have been preprogrammed as an appropriate response. Appropriate responses might include terminating the connection, or increasing the monitoring and awareness of what the intruder is doing on the system in order to gain more time to collect data for possible criminal prosecution.

[0094] FIG. 2 shows an example of the architecture of a distributed IDS for a network that might include both wired and wireless components.

• [0095]  Peripheral Agents may have the following functionality:
  • [0096] Authentication (of wired & wireless devices and users)
  • [0097] Data collection and feature selection (for building user profiles, statistics monitoring, and intrusion detection purposes)
  • [0098] Preliminary intrusion risk assessment (rank user's risk as minimal/low/medium/high/severe, etc.)
  • [0099] Communication (share data with other agents)
  • [0100] Response (including terminate connection, notify other agents, start user tracing, etc.)
  • [0101] Perform vulnerability scanning
• [0102]  Controller Agents may have the following functionality:
  • [0103] Communication (receive data from Peripheral agents for intrusion determination, send instruction to peripheral agents, etc.); send/shared data with master agents
  • [0104] Intrusion determination (including port scan detection, statistics monitoring, DoS monitoring, signature matching, etc.)
  • [0105] Response (including honey potting, start attack tracing, etc.)
  • [0106] Perform vulnerability scanning
• [0107] ● Master Agents may have the following functionality:
  • [0108] Assign/Recall/Modify other agents
  • [0109] Update and maintain profiles and signatures
  • [0110] Intrusion determination (DDoS monitoring, attack pattern matching, etc.)
  • [0111] Response
  • [0112] Initiate/terminate vulnerability scanning

[0113] Both FIGS. 2 and 3 represent example implementations and the extreme flexibility that is made possible by the agent-based and SVM-based IDS system. These two drawings are made to convey that agents such as these can be deployed to:

• • [0114] Monitor a variety of platforms by deploying agents that are uniquely tailored to the type of device that is of interest (a PDA agent is quite different from a laptop agent, and so forth)
  • [0115] Monitor a network of widely varying components and size
  • [0116] Monitor activity on all types and protocols of wired and wireless network traffic
  • [0117] Monitor activity behind and in front of a variety of different firewalls
  • [0118] Monitor activity on a geographically isolated collection of subnets

[0119] The present invention is, of course, in no way restricted to the specific disclosure of the specification and drawings, but also encompasses any modifications within the scope of the appended claims.