ࡱ > 7 ? bjbjUU 0 7| 7| l J J J J ~# ~# ~# # Q Q Q 8
R , 6R # >S T ( BT BT XT ky ky ky A C C C C C C $ h g ~# ky x ky ky ky g J J BT XT [$ | R ky J 2 BT ~# XT A ky A y + |! ~# XT 2S |Ih# @. Q G D 3 P % ε # # J J J J Agent Based Intrusion Analysis with Soft Evidence
V. Gowadia Csilla Farkas M. Valtorta
{gowadia, farkas, mgv}@cse.sc.edu
Information Security Laboratory
Department of Computer Science and Engineering
University of South Carolina
Columbia, SC 29205
Abstract.
In this paper we propose an agent encapsulated Bayesian network model for intrusion detection. We develop a cooperative, agent-based architecture, called Probabilistic Agent-Based Intrusion Detection (PAID), where each agent is autonomous and performs a specific task. We distinguish between three types of agents: system-monitoring, intrusion-monitoring, and registry agents. System-monitoring agents maintain log records and system resource information, and supply the requested data to the intrusion-monitoring agents. Intrusion-monitoring agents request information from system-monitoring agents and from other intrusion-monitoring agents. A unique property of our model is that we allow agents to share their beliefs. Agents that subscribe to beliefs published by other agents use the soft evidential update method. This property provides continuous scale for intrusion analysis and supports early detection even if the observations, called hard evidences, on the distributed components are not significant enough to raise an alarm. Registry agents maintain agent registry and provide dynamic information request. We propose an agent communication architecture that complies with FIPA specifications. A prototype of the proposed model is being implemented and our experimental results are included in this paper.
Keywords: intrusion analysis, detection, agent technology, Bayesian network, soft evidence, hard evidence, FIPA, JADE
1. Introduction
Even in the presence of sophisticated security safeguards, it is unrealistic to assume that a computer system is fully protected. Intrusions do occur and we need to be able to detect them. Frequent and serious occurrences of malicious attacks during the last decades led to extensive research on intrusion detection systems (IDS) [AFV95, CERT, LS98]. Recently, with the appearance of network-based intrusions, the need of building a cooperative and distributed intrusion detection system has emerged [SB91, CANN98, MST98]. Models and protocols for information sharing are among the current research topics of the IDS research community. Due to its dynamic and distributed nature, and the availability of development tools, agent-based technology is among the top candidates for developing collaborative intrusion detection systems [BGIS98, CHSP00, HWHM00].
For example, the system proposed by Helmer et al. [HWHM00] utilizes mobile agents to collect, integrate, and analyze data from different components of a distributed system. Findings of the agents are recorded in a database and/or reported to the users. However, while this approach supports integrated intrusion analysis, it has high communication cost and requires that agents must be trusted by the components. A more economical and popular solution is sharing only decisions among the agents. (Note that occasional data sharing still might be required for final decision but a much lower scale.) However, while decision sharing (i.e., intrusion detected) supports some level of interoperation, it does not provide quantitative information about the confidence in the reached decision. This confidence may be important for another component to achieve consistent analysis. For example, at a given stage, the local IDS agent may not be able to confirm an intrusion (i.e., the decision is no intrusion detected) but very close to the value needed for confirmation. This closeness to a compromised state may provide valuable information to another agent.
In this work we address the above shortcoming of current models by proposing a new intrusion analysis architecture. More specifically, we propose an agent-based, cooperative architecture, called Probabilistic Agent-Based Intrusion Detection (PAID), to analyze system information and estimate intrusion probabilities. PAID uses a multi-agent system, called Agent Encapsulated Bayesian Network (AEBN), where autonomous agents communicate their beliefs. From the security perspective, we distinguish two types of agents: system-monitoring agents and intrusion-monitoring agents. System-monitoring agents are responsible for collecting, transforming, and distributing intrusion specific data upon request and evoke information collecting procedures. Intrusion-monitoring agents request data from system-monitoring agents or beliefs from other intrusion-monitoring agents. Each intrusion-monitoring agent, represented as a single Bayesian network, performs belief update using both facts (observed values) and beliefs (generated values) using methods proposed in [VKV02]. Intrusion-monitoring agents generate probability distributions (beliefs), over intrusion variables that may be shared with other agents. Each belief is called a soft finding. IDS based on hard findings only are unable to detect variants of known intrusions. The variation in such intrusions is usually a modification in the hard evidence. A probabilistic representation of hard and soft findings makes our model capable of identifying variations of known intrusions. Soft findings indicate abnormal states of a system, which affect the probability of an intrusion even in the absence of certain hard findings. Soft-evidence propagation provides a continuous scale for taking decisions. This feature is very useful to support easy identification of complex and distributed intrusions, as we will describe in Sections 5, and 6.
Note, that although we present and implement our model as a misuse detection system, the underlying principles of AEBN also support anomaly-based intrusion detection. Clearly, based on the inherently more complex nature of modeling system behavior in contrast to modeling known intrusions, the task of building a Bayesian network to capture normal usage is more complicated. However, given agents to represent normal usage, our model can be applied to detect deviations.
Finally, we propose an agent communication model based on currently available technologies. Registry agents are responsible to maintain agent specific information. Our model conforms to the standardization given by FIPA. A prototype of the proposed system is under development using JADE. We are currently developing intrusion libraries and agent communication framework. Some of the experimental results are included in Section 5.
The organization of the paper is as follows. Section 2 contains the design considerations of our model. Section 3 gives a brief introduction to background information on Bayesian network and agent technology. Section 4 gives an overview of the proposed system architecture. In Section 5 we describe the proposed agent communication architecture. Section 6 contains detailed description of the Bayesian network models. Finally, we conclude and recommend future research in Section 7.
2. System Design Goals
The goal of our system is to support continuous intrusion classification. Intrusion probabilities are calculated on the scale of [0,1], where, 0 is the lowest probability for the existence of an intrusion and 1 represents the confirmation of an intrusion. Our model can be used either as a stand-alone system or to support and existing IDS. The proposed architecture of our model aims to satisfy the following objectives:
Provide measure of intrusion probability: Current IDSs generate alarms and warnings, without providing a measure of confidence in the alarms. Information about the probability of an intrusion in addition to the alarm may significantly affect another IDS component.
Flexibility: A site security officer (SSO) must be able to customize IDS sensitivity and selectivity according to the requirements of the site. When false alarms are costly, the SSO could trade off some sensitivity for increased selectivity. This would help in reducing number of false positives. Conversely, when a missed detection of an alarm is costly, the SSO could trade off some selectivity for increased sensitivity. This would help in reducing the number of false negatives.
Automated intrusion analysis & intrusion response: Automated support to the SSO for analyzing the log files and alarms generated and collected at different components on the network. This data may carry important information needed to identify the intruders intent, as well as it will decrease the respond time of the SSO.
Maintainability: It should be easy to add information about new intrusions, reconfigure the intrusions being monitored, and add or remove computers from the network with minimal disturbance to the working of intrusion detection system on other systems.
Scalability: Analysis of distributed attacks on a large network may require monitoring of numerous hosts and analyze and share large amount of data. Therefore, the IDS architecture should be of distributed nature that allows local analysis and information sharing.
Reliability: IDS should perform at an acceptable level even in the presence of intrusions. Information about the status of the links and the hosts will enable to apply heuristic techniques to provide survivability.
3. Background
3.1 Bayesian Networks
To assess the probability of an intrusion, we use Bayesian networks. Bayesian networks are probabilistic models that exploit the conditional independence properties present in a task domain to reduce both the space required to store the model and the time needed to compute posterior probabilities upon receipt of evidence. More formally, a Bayesian network is a pair composed of a multivariate probability distribution over n random variables in the set V = {V1, , Vn}, and a directed acyclic graph (DAG) whose nodes are in one-to-one correspondence with V1,, Vn. (For the sake of convenience, we do not distinguish nodes of graph from variables of the distribution.) The defining property of a Bayesian network is that the conditional probability of any node given any subset of non-descendants is equal to the conditional probability of that same node given the parents alone. The following property follows from the definition (which for simplicity we do not give in the most general form).
Theorem (Chain rule for Bayesian networks [Neapolitan90]). Let P(Vi | p(Vi)) be the conditional probability of Vi given its parents. (If there are no parents for Vi, let this be P(Vi).) If all the probabilities involved are nonzero, then EMBED Equation.3
The most common operation on a Bayesian network is the computation of marginal probabilities both unconditional and conditioned upon evidence. Marginal probabilities are also referred as beliefs in the literature [Pearl88]. This operation is called probability updating, belief updating, or belief assignment. By evidence we mean a collection of findings. A hard finding (or finding) on variable v is a specification of the value of v. A soft finding on variable v is a distribution on the values of v. These definitions of finding and of evidence may be generalized [CDLS99; VKV02], for example, by allowing specifications of impossible configurations of pairs of variables. However, applications rarely need the power of the generalized definitions, and most Bayesian network software tools support only the definition of (hard) evidence as a collection of (hard) findings given here.
Another common operation on Bayesian networks is the computation of the most likely configuration of a subset of the variables given evidence. This is known as the most probable explanation (MPE) problem if the subset includes all variables for which there is no evidence, and as the maximum a posteriori hypothesis (MAP) problem otherwise [Dechter96].
3.2 Agent Encapsulated Bayesian Networks
Our agent model is called the Agent-Encapsulated Bayesian Network (AEBN) Model [Bloemeke98]. Each agent in an AEBN model uses as its model of the world a single Bayesian network (which we also call an AEBN). The agents communicate via message passing. Each message is a distribution on variables shared between the individual networks.
The variables of each AEBN are divided into three groups: those about which other agents have better knowledge (input set), those that are only used within the agent (local set), and those of which the agent has the best knowledge, and which other agents may want (output set). The variables in the input set and the output set are shared, while those in the local set are not. An agent consumes (or subscribes to) zero or more variables in the input set and produces (or publishes) zero or more variables in the output set.
The mechanism for integrating the view of the other agents on a shared variable is to replace the agent's current belief (which is a probability distribution) in that variable with that of the communicating agent. The update of a probability distribution represented by Bayesian network upon receipt of a belief is called soft evidential update and is explained in detail in [VKV02]. In this project, we have used an algorithm for soft evidential update called the big clique algorithm, implemented in the BC-Hugin system [KVV02].
When a publisher makes a new observation, it sends a message to its subscribers. In turn, the subscribers adjust their internal view of the world and send their published values to their subscribers. Assuming that the graph of agent communication (which we simply call agent graph) is a directed acyclic graph (DAG), equilibrium is reached, and a kind of global consistency is assured, because the belief in each shared variable is the same in every agent. The restriction that one of the agents has oracular knowledge of a variable may seem excessive. However, it is permissible to have multiple views of a common variable. For example, in a multiagent system for interpretation, two agents may issue a report that corresponds to the same (unknown) physical quantity. Nothing prevents another agent from integrating the reports of these agents and effectively obtaining a new (and possibly more accurate) view of the same underlying quantity. As another example, it is possible for a subscriber agent to model known reporting errors or biases of the publisher.
3.3 Agent Communications Models
Agent communications can be divided into two categories, communication among agents at same host and communication among agents on different hosts. Communication methods for these situations have been studied in recent years [BFIS98, BPR99, FIPAOS].
Communication among agents on same host
Communication among agents residing on the same computer need not be transmitted through the network layer. They can communicate using other methods like pipes, message queues, shared memory. Balsubramaniyam et al. [BGIS98] analyzed these methods in the context of intrusion detection and identified their advantages and disadvantages. According to his findings, the most effective communication method among these agents is using shared memory. It allows large volume of data to be shared and is efficient for one to many communications. Other methods, like RPC, RMI, CORBA, DCOM, can also be used for agent communication.
Communication among agents over the network
The methods for sending and receiving messages over the network are same for each agent. Thus, to reduce cost, methods are not replicated for each agent. Rather, we propose a system where all agent communication are performed through an Agent Management System (AMS). The AMS used in our model has additional capabilities over the AMS used in FIPA-OS and JADE.
Fig. SEQ Fig. \n 1. Agent Communication Architecture
4. Probabilistic Agent-Based Intrusion Detection
First, we give a global view of the proposed architecture, called Probabilistic Agent-Based Intrusion Detection (PAID). The two main components of PAID are the Agent Communication Architecture and the AEBN. Figure 7 shows the interrelationship among these components. Detailed description of them is given in the subsequent sections.
Fig. SEQ Fig. \n 2. Probabilistic Agent-based Intrusion Detection (PAID)
The scalability of the proposed model depends on the performance of the belief update performed in the Bayesian network and the effectiveness of the agent communication architecture. Reference on Complexity and Scalability: Pearl [Pearl88] has shown that belief update can be performed in linear time in trees and (more generally) singly connected networks. Unfortunately, belief update in general Bayesian networks is NP-hard [Cooper90]. This negative result holds even for some notions of approximation and for many restrictions on the structure of the Bayesian network. Despite these negative theoretical results, update in most Bayesian network using the junction tree algorithm [LS88] is very fast, because most practical Bayesian networks compile into a junction tree where the largest clique is small [Neapolitan90].
Effectiveness of the agent architecture is bounded by performance and capacity of the agent registry. Our model provides scalability by supporting multiple registries. Each subnet may have its own agent-registry. The agent-registries can forward requests and replies to neighboring registries based on the IP address of the receiving agent. if the destination agent is not registered with them. Therefore, dynamic routing algorithms, such as [OSPF97, Perlman92], are applicable for this purpose. Within a subnet, an agent registry may still be a single point of failure. To improve reliability, redundant registries can be maintained at different locations in a subnet by taking snapshots of registry at regular intervals.
5. Agent Communication Architecture
In our model, we use agent graphs to model intrusion scenario. Agent at each node of the agent graph encapsulates a Bayesian network that represents knowledge about certain intrusion scenario, error modeling and method of incorporating multiple beliefs on input variables. Nodes of the Bayesian network represent beliefs of suspicious events or intrusions. Each agent is associated with a set of input variables, a set of output variables or beliefs, and a set of local variables. The input variables are beliefs published by other agents or monitoring data. A belief (node variable) can have any number of states. If the state of a belief is known exactly, it is said to be instantiated and is called hard finding. Else, the state of a node variable is described as a probability distribution calculated by the agent. This calculation incorporates the uncertainties and measurement errors. The probability distribution over the possible states the node variable is called soft finding.
The following types of agents are supported in our AEBN architecture:
System-monitoring agents: The system-monitoring agents process information from log files and communications with system resources. These agents publish their output variables, which can be utilized by other agents.
Intrusion-monitoring agents: These agents subscribe to valuesvariables and/or beliefs published by the system-monitoring agents and beliefs of other intrusion-monitoring agents as required. Information about the required input variables for an agent is obtained from the corresponding Bayesian network. Each intrusion-monitoring agent computes the probability for a specific intrusion type. The probability values are computed again on modification in the values of input variables or beliefs. The probability calculations are performed using the soft-evidential update algorithm for multi-agent systems. Their belief about the intrusion is published and can be used for alerting the SSO.
Registry agent: For each registered agent, our registry maintains information about the published variables and monitored intrusions. The registry also maintains the location and current status of all the registered agents. A registry is similar to the yellow pages. Agents use the registry to find information (e.g., name and location) about agents who may supply required data. Once location and the name of an agent providing required data are found, the registry need not be referred again unless one of the agents is restarted. This registry is different from the usual Agent Management System (AMS) registry in FIPA-OS and should not be confused with it.
5.1. Agent Communication
To share data and beliefs among various agents, our model uses a registry-based system. Agents in this system communicate among themselves by sending messages in XML [XML]. Various communication messages are described below and illustrated in Figure 6.
Agent registration: Each agent in the system registers with the registry agent by sending its agent-id, ip-address, published variables and their possible states, digital signature and its digital certificate in xml format. Corresponding xml-schema for a registration request is shown in Figure 1.
Fig. SEQ Fig. \n 3. XML schema for agent registration request
2. Searching agent: Input variables for an agent are determined by parsing the corresponding Bayesian networks .net [HNL] file. To search other agents capable of providing values of input variable, the agent sends a search request to the agent registry. The xml-schemas for search request and search results are shown in Figure 2 and 3 respectively.
Fig. SEQ Fig. \n 4. XML-schema for agent search request
Fig. SEQ Fig. \n 5. XML-schema for search results
3. Subscribing to beliefs of other agents: Agents can request other agents to send their belief on an input variable. A request consists of the variable name, the duration of subscription time, the desired time-interval between subsequent updates, timestamp of the request, and the digital signature of the requester. The XML-schemas of belief-request and belief update are illustrated in Figure 4 and 5 respectively.
Fig. SEQ Fig. \n 6. XML-schema for belief requests
Fig. SEQ Fig. \n 7. XML-schema for belief updates
5.2. Communication Security
Our system provides reliability and communication security by incorporates the following features:
Maintaining status of registered agents and network links: A registry agent monitors the status of the registered. This monitoring is performed by periodically probing system-monitoring agents. Response to the probing message carries information about the state of the probed agent. The status of a communication link between any two agents is determined by attempting a reliable UDP communication between them.
Authentication: Our model uses the PKI model to provide two-way authentication of messages and agents. All agents provide their digital certificates to the registry. These certificates are assigned to each agent in advance. This method prevents malicious agents from authenticating themselves to the registry. All messages sent among the agents are signed. Signature verification is done by obtaining the agents public key from the registry-agent.
Encryption & Decryption: Encrypted messages are sent among agents using secret key encryption method. PKI is used for key management.
6. Intrusion Analysis with Agent Encapsulated Bayesian Networks
In this section, we first explain intrusion analysis with an example of the Mitnick attack [SN99]. This example is sufficient to convince us that the traditional probability update methods for Bayesian networks as suggested in [DBDV99] are not applicable for updating the belief of an intrusion with the beliefs of other agents as input. We also conclude that the calculation of belief for certain state of a variable depends on factors such as:
1. Accuracy of measurement
2. Trust on the publishing agent
3. Conflicts among beliefs reported by various agents
In our model, if the agent-registry indicates the status of an agent as good, the agent is trusted completely. In sections 6.2 and 6.3 we present Bayesian network models for modeling errors and conflict resolution. Finally we discuss some knowledge engineering issues.
6.1 Mitnick Attack Example
Use of soft evidence in our model for calculation intrusion probability is illustrated with an example of the Mitnick attack. The Mitnick attack (see Figure 8) exploits the weakness of an IP based authentication system, for compromising the victim host. In the preparation of the attack, the intruder installs malicious programs (zombies) on many vulnerable computers over the Internet. These programs are used to launch a denial of service (DOS) attack against the trusted host at a specific time. The intruder performs some reconnaissance probes to gather sufficient information for guessing the future TCP sequence numbers of the victim host. When the trusted host is under a denial-of-service attack, it is unable to reply to packets sent by the victim host. Under such a situation, the intruder tries to open a TCP connection with the victim host by spoofing the IP address of the trusted host. The victim host sends a SYN-ACK packet as a reply to the trusted host. The trusted host due to the DOS attack drops this packet. The attacker sends another ACK packet to the victim with appropriate sequence number. On receipt of this packet, victim computer assumes that it is communicating with the trusted host. The attacker is now in a position to use the services provided by the victim host.
Mitnick attack is difficult to identify due to its distributed nature. The attack consists of few hard findings but a number of soft-findings that can be used to identify this attack. The events observed in the above situation are listed below.
Findings indicating IP spoofing are observed:
If the intruder is an insider and is spoofing packets from within the network, a network-interface in promiscuous mode may be detected. This observation is a hard finding and is not conclusive evidence to indicate IP spoofing.
The network firewall and/or routing nodes on a network may discover incoming IP-packets with local source IP address. This is a conclusive evidence for an IP spoofing attempt. We model it as a hard finding.
An IP spoofing incidence may lead to abnormal variations in the TTL value. This variation can be detected if a record of TTL value in the IP header of packets from a trusted host is kept. This observation is modeled as a soft finding.
Findings indicating a TCP-SYN DOS attack on Trusted host are:
In a situation when a server is under a TCP-SYN attack, it receives more number of SYN packets then the number of connections it can handle. The number of connections handled by the server can be found by monitoring the server program or by counting the number of SYN-ACK packets trusted host is sending. Evidence indicating a large extent of overload on the server increases probability of a TCP-SYN DOS attack and distinguishes it from normal busy hours of the day. Thus, this observation is modeled as a soft finding in this example.
A reduction in outgoing traffic compared to normal usage is another observation during a DOS attack. This observation is also modeled as a soft finding.
Finding at the victim machine:
Applications at victim host are not able to open new connections with the trusted host, but the victim host is still receiving packets with the source IP address of trusted host. The observation by itself may not be sufficient to make an inference about the attack, but is very useful when combined with other information. This observation is also as a soft finding.
We consider a simplified version of the above situation in further analysis of the example. Multi-agent system shown by agent graph in can be used to model the Mitnick attack.
The nodes shown in Figure 9 represent various intrusion-monitoring agents. The Mitnick-intrusion-agent subscribes to the beliefs of the IP-spoofing-agent and the dos-attack-agent. The IP-spoofing agent and dos-attack agent may further subscribe to beliefs or variables published by other agents. We do not show them in above figure for simplicity.
Fig. SEQ Fig. \n 8. Multi-agent system for Mitnick Attack
In above Bayesian network, S is a local variable inside the TCP-SYN agent and H is a local variable inside the IP Spoofing agent. The DOS agent subscribes to the variables number of SYNs (connection requests) received and number of SYN-ACKs (connections handled) sent in a fixed time interval. These values are used to calculate the value of S. S is calculated as percentages of connection requests that could not be handled in the time frame by the following formula:
S = | n(SYN) n(SYNACK) | / n(SYN)
Based on the value of S, belief about a DOS attack is computed. This belief has three different states, viz., low, medium and high. If all connection requests are handled S is equal to zero or has very small value. During peak hours or time when servers maximum capability is being utilized under normal conditions, S may have a medium value. When the system is under attack, many connection requests cannot be served and value of S is high. The values that define the different states of DOS attack can be determined from expert knowledge or historical data as described later. For our example we assume the following ranges.
StateRangeLow0.00 0.05Medium0.05 0.20High0.20 1.00Table SEQ Table \n 1. Possible states of S
In real life, these range values may be only be approximated from network data. Hence, the agent publishing belief on DOS cannot be completely certain. The published belief needs to incorporate measurement error. We describe a method to do so in subsequent sub-section.
Our prototype system to observe results in above scenario was developed and tested on an isolated security lab network. We use snort in packet-logger mode to log information for our agents. The system monitoring agents process the log data in real time to provide on-line analysis. The experiments carried modeled IP spoofing as a hard finding only. We observed that the attack probability increased from 0.4 % to values as high as 90.9% when a Mitnick attack was carried out in our lab.
The agents that provide measurements and beliefs required to determine probability of an intrusion may reside on same host or other systems. Each intrusion-monitoring agent in the system encapsulates a Bayesian network that is used to update the belief it is computing.
6.2. Modeling errors in measurement
If the publishing agent is not able to accurately determine a variable state, in our model the agent publishes a probability distribution over the possible states of the variable. This distribution is the soft finding for state of measured variable. The publishing agent determines this distribution by incorporating the measurement errors. Error in the measurement of a variable state can be modeled within an agent with help of Bayesian network shown in figure 5. This is achieved by representing the state of variable with a belief or soft finding. The parent node S represents the actual value of interest. The prior distribution of the actual values is P(S). The measured value is represented by variable Sobs. The measurement error is modeled by the conditional probability P(Sobs|S). When the actual value is propagated to parent node S, we get a probability distribution over different states of the variable. The agent can publish this distribution as its belief on the state of the measured variable.
Fig. SEQ Fig. \n 9. Incorporating error in measurement of variable
6.3. Conflict resolution
Conflict among beliefs on a state of variable can occur when multiple agents provide information on the same underlying quantity. It is possible to incorporate independently obtained multiple input beliefs as soft findings. We suggest a method of modeling conflict resolution with help of Bayesian networks in this section.
One of the advantages of using Bayesian network is that it can model situations when the input beliefs (nodes I1 and I2 in the example of Figure 6) for a certain node (node B in Figure 6) are affected by a common factor (node CR in Figure 6) other than the belief being modeled in the Bayesian network. The Bayesian network can be used to obtain correct results when the conditional probabilities P(I1|CR) & P(I2|CR) are provided.
Fig. SEQ Fig. \n 10. Conflict Resolution
This feature can be exploited to do conflict resolution. Again referring to the example of Figure 6, CR gives the context for I1 and I2. One needs to define the conditional probabilities P(I1|B,CR) and P(I2|B,CR), to resolve the conflict in belief propagation.
To make the example concrete, imagine that I1 and I2 both represent the amount of network traffic, and the difference between the measurements is that the two agents are running on different machines. The context may provides CR with the type of computers agents are running on; for example, the agents providing measurement I1 is running on a PC, while the agent providing measurement I2 is running on a SUN workstation. Hypothetically the measurement on a SUN is more reliable than in a PC. The conditional probabilities P(I1|B,CR) and P(I2|B,CR) can be set to give preference to measurement on the SUN machine when it is available. The context variable may be to represent other contextual information that would increase the sensitivity or selectivity of one of the measurements relative to the other.
6.4. Knowledge Engineering Issues
Bayesian network construction involves specification of structure (a directed acyclic graph) and parameters (the conditional probability tables). A brief survey of relevant issues, which we have not yet applied to the task domain described in this paper, follows.
Algorithms for structural learning have been applied with some success, even in missing (incomplete) data situations. We are partial to the CB algorithm [SV95]. See [MDV97] for an application in an incomplete data situation, and [Singh97] for a principled approach to structural learning from incomplete data.
Typically, it is simpler to elicit structure from experts and learn parameters from data. In the absence of good data, parameters are also elicited using decision analysis techniques [MC00]. A combination of these techniques, various tricks of the trade [Jensen01, Ch.2], sensitivity analysis [Jensen01, Ch.6], and adaptation [Neapolitan90, Ch. 10] usually leads to satisfactory results.
Conclusion
We have presented the architecture of a probabilistic agent based intrusion detection system (PAID) with several novel features. A proof of concept prototype of the system has been implemented using Java, C, and a prototypical implementation of a soft evidential update algorithm called BC-Hugin. A more complete version is currently under development.
Advantages
It is easy to explore the trade-off between sensitivity and selectivity with this architecture.
Novel intrusions: The current system focuses on intrusion analysis and measurement of intrusion probability. The problem is solved by combining information from various sources. Previous knowledge about the intrusion helps to easily identify the type of intrusion. The model also works for anomaly detection and is capable of detecting new types of intrusions.
As in most multiagent systems, there is no prominent single point of failure. This improves the reliability of the proposed PAID system. Also, computations are distributed. This improves the efficiency of the proposed PAID system.
Open Problems and Future Work
We have identified some limitations of the current model and we consider working on these problems in near future.
Agent Trust Management: The current reliability model has not incorporated trust management among various agents. Trust management is in itself a current research topic and we wish to develop some techniques that will work in an intrusion scenario.
Starting and Stopping Agents: There are instances when certain audit information needs to be collected only in presence of particular evidence. Our model provides the provision of dynamically starting and stopping agents by having a agent-manager at each host. Agent manager is itself an agent that registers variables with the registry on behalf of agents it is capable of starting. If an agent capable of providing the required information is not currently running, the agent manager can be requested to dynamically start that agent.
References
[AFV95] D. Anderson, T. Frivold, and A. Valdes. Next Generation Intrusion Detection Expert Systems (NIDES): A Summary. Technical Report SRI-CSL-95-07, SRI International, Menlo Park, CA, 1995
[AOTG99] M. Asaka, S. Okazawa, A. Taguchi, S. Goto. A Method of Tracing Intruders by Use of Mobile Agents, In Proc. INET'99, June 1999.
[ATP00] A. Seleznyov, V. Terziyan and S. Puuronen, Temporal-Probabilistic Network Approach for Anomaly Intrusion Detection, 12th Annual Computer Security Incident Handling Conference, Chicago, USA, 2000.
[BGIS98] J. Balasubramaniyan, J.O. Garcia-Fernandez, D. Isacoff, E.H. Spafford, and D.M. Zamboni. An Architecture for Intrusion Detection using Autonomous Agents. Technical Report, Dept. of Computer Science, Purdue Univ., West Lafayette, IN, 1998
[BRP99] F. Bellifemine, A. Poggi and G. Rimassa, JADE - A FIPA compliant Agent Framework. In Proc. of the 4th International Conference and Exhibition on The Practical Application of Intelligent Agents and Multi-Agents, London, 1999
[CANN98] J. Cannady. Artificial Neural Networks for Misuse Detection. In Proc. of the 21st National Information Systems Security Conf., VA, 1998, pp. 441-454
[CERT] Center for Emergency Response Team, http://www.cert.org, 2002
[CHSP00] C.A. Carver, J.M. Hill, J.R. Surdu, and U.W. Pooch. A Methodology for using Intelligent Agents to Provide Automated Intrusion Response. In Proc. of the IEEE Systems, Man, and Cybernetics Information Assurance and Security Workshop, West Point, NY, 2000
[DBDV99] D. Bulatovic and D. Velasevic, A Distributed Intrusion Detection System Based on Bayesian Alarm Networks, In Proc. of CQRE99, LNCS 1740, pp. 219228, 1999.
[Dechter96] Rina Dechter. Bucket Elimination: A Unifying Framework for Probabilistic Inference. Proceedings of the Twelth Conference on Uncertainty in Artificial Intelligence (UAI-96), pp.211-219.
[FIPAOS] FIPA-OS Developers Guide,http://fipa-os.sourceforge.net/docs/Developers_Guide.pdf
[HNL] The net Language, http://developer.hugin.com/documentation/net/
[HWHM00] G. Helmer, J. Wong, V. Honavar, and L. Miller. Lightweight Agents for Intrusion Detection.
[Jensen01] Finn V. Jensen. Bayesian Networks and Decision Graphs. Springer, 2001.
[JMKM99] W. Jansen, P. Mell, T. Karygiannis, and D. Marks. Applying mobile agents to intrusion detection and response. Technical report, NIST, October 1999
[LS88] Steffen L. Lauritzen and David J. Spiegelhalter. Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems. Journal of the Royal Statistical Society, Series B, 50 (1988), 2, pp.157-224.
[LS98] W. Lee and S.J. Stolfo. Data Mining Approaches for Intrusion Detection. In Proc. of the 7th USENIX Security Symp., San Antonio, TX, 1998, pp.79-94
[MC00] Stefano Monti and Giuseppe Carenini. Dealing with the Expert Inconsistency in Probability Elicitation. IEEE Transactions on Knowledge and Data Engineering, 12, 4 (July/August 2000), pp.499-508.
[MDV97] Subramani Mani, Suzanne McDermott, and Marco Valtorta. MENTOR: A Bayesian Model for Prediction of Mental Retardation in Newborns. Research in Developmental Disabilities, 18 (1997), 5, pp.303-318.
[MST98] M. Meneganti, F.S. Saviello, and R.Tagliaferri. Fuzzy Neural Networks for Classification and Detection of Anomalies. IEEE Trans. On Neural Networks, 9/5, 1998, pp. 848-861
[Neapolitan90] Richard E. Neapolitan. Probabilistic Reasoning in Expert Systems. Wiley, 1990.
[NP99] P.G. Neumann and P.A. Porras. Experiences with EMERALD to Date. In Proc. of the 1st USENIX Workshop on Intrusion Detection and Network Monitoring, Santa Clara, CA, 1999
[OSPF97] J. Moy. OSPF version 2. Internet Draft, RFC-2178, July 1997
[Pearl88] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan-Kaufmann, 1988.
[Perlman92] R. Perlman. Interconnections: Bridges and Routers. Addison-Wesley, 1992.
[RCHP00] D. Ragsdale, C. Carver, J. Humphries, and Udo Pooch. Adaptation Techniques for Intrusion Detection and Intrusion Response Systems, In Proc. of the IEEE International Conference on Systems, Man, and Cybernetics, Oct 2000, pp. 2344-2349
[SB91] S. Snapp, J. Brentano, . DIDS (Distributed Intrusion Detection System) - Motivation, Architecture, and an Early Prototype. In Proc. of the 1991 National Computer Security Conference, 1991
[Singh97] Moninder Singh. Learning Bayesian Networks from Incomplete Data. Proceedings of the 14th National Conference on Artificial Intelligence (AAAI-97).
[SN99] S. Northcutt, Network Intrusion Detection: An Analyst's Handbook, New Riders, 1999
[SV95] Moninder Singh and Marco Valtorta. Construction of Bayesian Networks from Data: A Brief Survey and an Efficient Algorithm. International Journal of Approximate Reasoning, 12, 2 (February 1995), pp.111-131.
[VKV02] Marco Valtorta, Young-Gyun Kim, and Jir Vomlel. Soft Evidential Update for Probabilistic Multiagent Systems. International Journal of Approximate Reasoning, 29, 1 (January 2002), pp.71-106.
[WD99] William DuMouchel. Computer Intrusion Detection Based on Bayes Factors for Comparing Command Transition Probabilities, Technical Report No. 91, Feb 99, National Institute of Statistical Sciences.
[WFP96] G.B. White, E.A. Fisher, and U.W. Pooch. Cooperative Security Managers: A Peer-based Intrusion Detection System. IEEE Network, 10/1, 1996, pp. 20-23
[XML] Extensible Markup Language Language 1.0 specification, http://www.w3.org/TR/2000/REC-xml-20001006, W3C Recommendation, October 2000
[XMLS] XML Schema Part 0: Primer, http://www.w3.org/TR/2001/REC-xmlschema-0-20010502/ W3C Recommendation, May 2001.
[BM98] M. Bloemeke. Agent Encapsulated Bayesian Networks. Ph. Thesis. Department of Computer Science. University of South Carolina, 1998.[KVV02]. Young-Gyun Kim, M. Valtorta, and J. Vomlel. A Prototypical System for Soft Evidential Update. In preparation.
PAGE 2
PAGE 3
Agent
Registry
Results
Intrusion
Monitoring
Agents
Register
Query-Reply
Register
Bayesian Network
System
Monitoring
Agents
Log Files
System Resources
Sobs
IP
DOS
Agent
S
S
IP
DOS
IP
Spoofing
Agent
H
DOS
MA
CR
I2
I1
B
Mitnick Attack Agent
AMS
AMS
A1
A2
A3
A6
A5
A4
Fig. SEQ Fig. \n 7. Mitnick Attack
+ N % 4 ?
I
| ` o b! ! ! ! n" y" W$ $ % % &