[INET'99] [ Up ][Prev][Next]

A Method of Tracing Intruders by Use of Mobile Agents

Midori ASAKA <asaka@ipa.go.jp>
Information-Technology Promotion Agency

Shunji OKAZAWA <okazawa@sec.jri.co.jp>
Japan Research Institute

Atsushi TAGUCHI <a-tag@ipa.go.jp>
Information-Technology Promotion Agency

Shigeki GOTO <goto@goto.info.waseda.ac.jp>
Waseda University


A network intrusion detection system (IDA) retrieves information related to intrusions from target systems across the network by using mobile agents. Simultaneously, the agents trace the intruders. IDA detects intrusions based on information collected and the route of intrusion. This paper mainly describes how IDA retrieves the information and traces the intrusions.


1 Introduction

Computer break-ins are mainly divided into two types: break-ins from outside the local area network (LAN) and those from inside LAN. However, it is rare in either case that intruders directly attack the target host from their own hosts[1]. The reason for this is logical: intruders desire to conceal their origin. Intruders tend to attack the less-protected hosts first, gradually approaching hosts armed with stronger protection, ultimately working up to and reaching their target hosts. Commonly, administrators not only on the target hosts but also on the intermediate hosts do not notice the intrusion. Furthermore, the administrators cannot trace the origin of an intrusion after the network connection has closed even if the intrusion has been detected.

At the Information-technology Promotion Agency (IPA) in Japan, we have been developing a network intrusion detection system (IDS) called the Intrusion Detection Agent system (IDA), which employs mobile agents toward the goal of avoiding some of the problems experienced by conventional IDSs. IDA has a function by which mobile agents trace intruders, collecting information related only to the intrusion along the intrusion-route, and decide whether, in fact, an intrusion has occurred. These functions enable efficient information retrieval, and also make it possible to detect compromised intermediate hosts. Furthermore, IDA detects intrusions based on a new intrusion detection model, with features distinct from those of the conventional one. Consequently, IDA reduces the overhead of the system and detects some new and unknown forms of attack.

This paper describes how the mobile agents in IDA trace intrusions and gather information. We propose a method of information exchange and tracing intrusion by means of mobile agents. Section 2 describes the structure and action of IDA. Section 3 describes the bulletin board and message board by which mobile agents exchange information. Section 4 describes the implementation and evaluation of IDA. Section 5 outlines our conclusions and indicates the direction of our future work.

2 Intrusion Detection System (IDA)

2.1 Current intrusion detection systems

Many current intrusion detection systems are based on Denning's intrusion detection model[2,3], in which audit records, network packets, or any other observable activity serves as the basis for detecting abnormalities in the system or checking them with traces and signals of known intrusion patterns. The methodology by which intrusions are detected can be divided into the following two categories[4]:

An anomaly intrusion detection system records users' activities on the systems and builds statistical profiles of the activities from these records. It regards activities that differ remarkably from normal use as intrusions. Misuse intrusion detection refers to intrusions that follow well-defined intrusion patterns, and these can be written into the system in advance.

Since misuse intrusion detection will not work against new or unknown forms of attack, and anomaly intrusion detection is ineffective in detecting insider attacks, any intrusion detection system that employs only one of these methods will have a limited range of intrusions it can detect. Intrusion detection systems that intend to avoid these pitfalls usually involve concurrent employment of both misuse and anomaly techniques. However, the anomaly intrusion detection portion of the system is still large and slow; as a result, it is often impractical for an average site to use an IDS that employs both techniques. The current trend of research in IDS is not toward detecting many intrusions efficiently but toward detecting almost all intrusions precisely.

In developing IDA, we propose a new intrusion detection model in place of Denning's model. IDA will concomitantly reduce the overhead of the system and detect new or unknown forms of attack. Our goal is not to detect all intrusions precisely but to detect many intrusions efficiently. To accomplish this goal, IDA works by watching events that may relate to intrusions -- Marks Left by Suspected Intruder, referred to by the acronym MLSI in our model -- instead of analyzing all of the users' activities. If an MLSI is found, IDA will gather information related to the MLSI, analyze the information, and decide whether or not an intrusion has occurred. For example, IDA monitors whether or not critical files related to system security have been modified, since, in many cases, intruders tamper with them. However, because legitimate users may also change the files, the system cannot conclude solely on the basis of file modifications that an intrusion has occurred. IDA therefore gathers further information related to the modification of the file before deciding if an intrusion has occurred. We refer to the additional information gathered as "information related to MLSI."

2.2 Structure of IDA

In many conventional network intrusion detection systems, each target system transfers its system log to an intrusion-detection server, and the server analyzes the entire log in search of intrusions. Methods of this kind fall under the client/server paradigm. In a large-scale network deploying an intrusion detection system, network traffic will be extremely high, since the volume of the system logs that are routinely transferred is very large, though most of it has no information related to intrusions. Therefore, this type of intrusion detection system on a large-scale network does not fulfill its function efficiently. To solve this problem, we adopted a mobile-agent paradigm in developing IDA. Mobile agents autonomously migrate to target systems to collect only information related to intrusions, eliminating the need to transfer system logs to the server. We can deploy IDA on a local area network, the protocol of which is TCP/IP. IDA consists of a manager, sensors, bulletin boards, message boards, tracing agents, and information-gathering agents. The system details are as follows (Figure 1).

Figure 1: Structure of IDA


The manager analyzes information gathered by information-gathering agents (which are described below) and detects intrusions. It manages the mobile agents and bulletin boards (also described below) and provides an interface between administrators and the system. The manager accumulates and weighs the information entered by the mobile agents on the bulletin board, and if the weights exceed a set threshold, the manager concludes that an intrusion has occurred. One manager resides on each network segment.


The sensors, present on each target system, monitor system logs in search of MLSIs. If a sensor finds an MLSI, it reports this finding to the manager. The sensor also reports on the type of MLSI.

Tracing agent

The intrusion-route tracing agent, called simply the tracing agent, traces the path of an intrusion and identifies its point of origin: the place from which the user leaving an MLSI remotely logged onto the target host. En route to finding the origin, a tracing agent can find any intermediate nodes that may be compromised.

The manager, sensor, and tracing agent work together in the following way. First, the sensor detects an MLSI and reports it to the manager, then the manager launches a tracing agent to the target system. The tracing agent migrates autonomously from machine to machine and traces the intrusion independently, without the manager.

When many MLSIs are found by a single target system in different sessions over a short period of time, many tracing agents corresponding to the MLSIs are launched into the target system. A tracing agent makes no judgments about intrusions, and is not capable of deciding whether or not an intrusion has occurred. A tracing agent can migrate to any system in which IDA is installed.

Information-gathering agent

An information-gathering agent, which is mobile, gleans information related to MLSIs from a target system. Each time a tracing agent in pursuit of an intruder is dispatched into a target system, it activates an information-gathering agent in that system. Then the information-gathering agent gleans information depending on the type of MLSI, returns to the manager, and reports.

If the tracing agent migrates to another target system, it will activate another information-gathering agent, which will gather information on the next target system. Many information-gathering agents may be activated by many different tracing agents on the same target system. An information-gathering agent is not capable of deciding whether an intrusion has occurred.

Bulletin board and message board

The bulletin board and the message board are a common use area that can be accessed by tracing agents and information-gathering agents, and a means of information exchange. There is a message board on each target system, used by tracing agents for exchanging information; any tracing agent can know whether a track under its scrutiny has already been traced by other agents, and can use this information in deciding where to go. The bulletin board is on the manager-machine and is used for recording information gathered from target systems by information-gathering agents, as well as for integrating the information gathered about every tracing route.

2.3 Action of IDA

Here we outline how IDA works after a sensor detects an MLSI on a target system. IDA accumulates the data required by intrusion-route tracing (i.e., about network connection, the various processes running on the system, etc.) on each target system in advance.

  1. Each sensor on the target system seeks an MLSI from the system log.
  2. If the sensor detects an MLSI, it is reported to the manager.
  3. The manager dispatches a tracing agent to the target system where the MLSI was detected.
  4. The tracing agent arrives at the target system and activates an information-gathering agent.
  5. The information-gathering agent collects information related to the MLSI on the target system.
  6. After activating the information-gathering agent, the tracing agent investigates the point of origin of the MLSI in an effort to identify the user's remote site. The tracing agent can derive this from the accumulated data about network connection and processes running on the system.
  7. After collecting information, the information-gathering agent, independent of the tracing agent, returns to the manager, and enters the information on the bulletin board.
  8. The tracing agent moves to the next target system on the tracing route, and it activates a new information-gathering agent.
  9. If the tracing agent arrives at the origin of the route, or cannot move anywhere, or if other tracing agents have chased the route it could follow, it returns to the manager.

In cases where a sensor detects many MLSIs on a target system occurring over a short period of time, or if sensors detect MLSIs on many target systems, IDA works as described above for all MLSIs detected.

3 Information exchange by agents

3.1 Purpose of the bulletin board and the message board

In IDA, the manager dispatches a tracing agent to a target system and, because of the mobile agent's autonomy, subsequently has no concern with the migration of the tracing agent. Many tracing agents may therefore trace the same intrusion, since the manager does not centrally control their respective migration. To avoid this overlapping, tracing agents exchange information with each other regarding their respective pursuits. Tracing agents employ the message board on a target system for this exchange of information.

The bulletin board on the manager-machine, on the other hand, contains information brought to the manager by the information-gathering agents that have been activated by the tracing agents. Each information-gathering agent brings information to the manager independently, and, as a result, this information concentrated in the manager is not arranged by intrusion-route. The bulletin board on the manager-machine functions as a clearinghouse, where this unorganized mass of information can be arranged by intrusion-route for the manager's analysis.

3.2 The message board

As explained above, tracing agents employ the message board on the target system in order not to overlap their respective trace routes. A tracing agent begins to trace from the point in a target system where an MLSI is first detected. If a user who leaves the MLSI leaves another MLSI on his or her way to the target, another tracing agent will be dispatched. For example, suppose user X remotely logs onto target systems A, B, C, and D in this order: A - B - C - D. User X compromises the systems, and MLSIs are detected on targets D and B respectively. The sensors of D and B report to the manager independently, and the manager dispatches tracing agents to both targets D and B. The tracing agent Dag traces intrusions in the following order: D - C - B - A. Tracing agent Bag, on the other hand, traces in the following order: B - A. The two agents' tracings therefore overlap on B - A (Figure 2).

Figure 2: Overlap Trace

The tracing agents determine their paths and destinations by use of a message board as explained below.

  1. A tracing agent that is dispatched to a target system uses the process ID and user ID to trace a process that has left an MLSI.
  2. If the tracing agent detects that the user who has left MLSIs logs on to the target system remotely, then the agent determines its destination from information about the user's login session.
  3. The tracing agent refers to the message board on the target system.
  4. If there is no information on the message board pertaining to the login session that the agent intends to trace, the tracing agent then enters such information and moves onto the target system from which the user logged on.
  5. If there already exists on the message board information related to that session, meaning that another agent has already traced this particular user, then the tracing agent enters its reference on the message board and returns to the manager.
  6. If Step 4 (rather than Step 5) has been followed, and it turns out that the target system being traced is the origin of the intrusion, the tracing agent returns to the manager. If not, the agent repeats Steps 1 - 6.

The list below describes the information entered by tracing agents on the target system message board in order to avoid trace overlapping.

If the tracing agent decides to discontinue a trace, it enters its ID and the time stamp on the message board. In this case, when the agent returns to the manager, it brings a log of its tracing route and the reason for its return.

There are three possible reasons for a tracing agent's return.

If it turns out that another agent is tracing or has traced the intrusion, the tracing agent in question also brings the agent's ID and the name of the following system to the manager.

3.3 Integration of information

The manager judges whether or not an intrusion has occurred on the basis of information gathered by the information-gathering agents. The manager does this by evaluating the information entered onto the bulletin board on the manager-machine. It evaluates not only each bit of information but also the information on each intrusion-route as a whole. Below, the method by which a manager integrates information and categorizes it by intrusion-route is described.

  1. An information-gathering agent returns to the manager after it has completed its task of gathering information related to intrusions on a target system. The agent then checks the bulletin board on the manager for information gathered by other information-gathering agents that were activated by the same tracing agent.
  2. If no information has been gathered and posted by other information-gathering agents activated by the same tracing agent, the information-gathering agent in question enters its information on the bulletin board. When the agent enters the information, the manager weighs and evaluates the information.
  3. If any information has been gathered and posted by other information-gathering agents activated by the same tracing agent, the information-gathering agent enters its information onto the bulletin board and appends it to the other agents' information, in the order in which the tracing agents traced the intrusion (Figure 3). At this time, the manager again evaluates all information accumulated in the appended information-list, and decides whether an intrusion has occurred.

    Thus, information gathered by information-gathering agents activated by the same tracing agent will be integrated into a single set of information in the order it was found along the intrusion-route. Beyond this method, however, if many tracing agents trace the same intrusion, the manager integrates the information as described below.

    Figure 3: The Bulletin Board

  4. If a tracing agent X requests another tracing agent Y to trace an intrusion, X brings the information about Y to the manager. X appends the list of information gathered by the previous information-gathering agents that it activated (X's information-list) to Y's information-list (Figure 3). As a result, the two information-lists will be integrated, and the manager again evaluates all information in the appended, cumulative information-list.

The information entered by information-gathering agents in the bulletin board on the manager is as follows:

4 Implementation and evaluation

4.1 Implementation

4.1.1 Definition of MLSIs and information-gathering

We divided intrusions into two patterns: remote attacks and local attacks. A remote attack is any attack that is initiated against a machine to which the attacker does not currently have access. A local attack is any attack that is initiated against a machine to which the attacker already has access. We are now implementing IDA and have completed the local-attack detection mechanism in IDA.

Prior to implementation, we investigated patterns of Internet intrusions, and it was revealed that the patterns of most local attacks involve start up of an unauthorized root shell and modification of critical files related to system security. Therefore we define MLSIs as

  1. start up of root shell and
  2. modification of critical files such as /etc/passwd, /etc/shadow, /etc/hosts.equiv, and /.rhosts

in local-attack detection, and the sensors monitor these features on each target system.

Moreover, information-gathering on the target machine where the MLSI was left is based on the definition of MLSIs. Information-gathering for the first MLSI includes whether the user who caused the MLSI issued the "su" command or not, and that for the second MLSI includes the following:

From the event log, IDA detects an intrusion that occurred before the MLSI triggered. This means that after the MLSI the manager can detect intrusions without analyzing any event on the target systems.

4.1.2 Environment

Over the course of IDA development, the function of local-attack detection and intrusion-route tracing in local area networks has been completed. We created a developing environment of IDA as described below.

In IDA, mobile-agents are written by D'Agent, which offers PGP, and this is able to authenticate and encrypt the mobile agents[7].

4.2 Experiment and evaluation

4.2.1 Local-Attack detection

The goal of IDA is not to detect all intrusions but to detect as many as possible efficiently and with precise intrusion-route tracing. Since many Internet intrusions occur by means of cracking tools distributed on the Internet, it would be appropriate to evaluate the efficacy of IDA against these cracking tools. We obtained cracking tools aimed at local attacks on the Internet, and classified them, and simulated IDA attacks by use of these tools. Our classification (see below Figure 4) is a limited examination of the trend of cracking tools because we could not obtain all cracking tools available. We attack IDA by use of these tools, which can run on Sun Solaris 2.5.1, and found that, within the limits, IDA can detect a local attack with the tools tested 92.3% (12/13 simulations).

Figure 4: Classification of Cracking Tools

4.2.2 Mobile agent performance

To establish agent performance, it is important for the IDA to determine how many MLSI triggers occur, since the number of MLSIs should be the same as the number of tracing agents activated on the manager. We investigated the rate of MLSIs in our developing environment, and found that the MLSIs triggered at the rate of 0.024% in whole events (22/89742) per a day. The machine investigated is a mail server in an IDA project, also used in developing IDA, which has six users.

The average size of a tracing agent is 4.2K bytes, that of information-gathering agents without information is 2.1K bytes and 2.4K bytes with information. We measured the time period from when a sensor triggers to when the tracing agent related to that MLSI returns to the manager in each case of the number of target systems contained in an intrusion route. We measured this time period in the case of authenticating agents. With authenticating and encrypting, it takes about one and a half times as long as only authenticating. This time includes all processes of the tracing agent on each target system. The time period of an agent's transportation between targets is very short, often less than 0.1 second. The results are shown in the following Table 1.

Table 1: Time Period of Tracing Agent's Round Trip
Number of Machine Round-Trip Time (sec)
1 7.194
2 11.120
3 16.002
4 20.736
5 28.054

5 Conclusion and the direction of future work

We have described how mobile agents gather information and trace an intrusion in IDA. IDA does not indiscriminately gather information from the entire network, but gathers information only related to the MLSI by tracing the user who has left it behind. Therefore, information does not bombard a manager indiscriminately, but is already arranged by intrusion-route. As a result, the manager need not organize information. Given that IDA does not gather information unrelated to intrusions, the amount of information concentrated in the manager will be reduced by using this system. Moreover, if IDA cannot detect an intrusion in one of the target systems on an intrusion-route, e.g., target system A, but detects intrusions in other target systems along the same route, it will conclude that an intrusion has occurred in A. In other words, if IDA fails to detect an intrusion directly on a target, it may ultimately detect it indirectly from information gleaned from other targets on the same intrusion-route. In this way, IDA is able to detect intrusions on intermediate nodes along an intrusion-route.

The IDA project is currently in the implementation phase. Mobile agents in IDA are written in D'Agent, which is presently under development at Dartmouth College. At present, a local-attack-detection mechanism and intrusion-route tracing in LAN have been completed. Our next priority is to detect remote attacks, to trace intrusions on the Internet and to extend IDA's applicability to large-scale networks.

We will participate in Model City with Advanced Information System Development Project planned by MITI (Ministry of International Trade and Industry) and MPT (Ministry of Posts and Telecommunications), and will test the functions of IDA on the Internet. We will report the results of these experiments at INET '99.


Many thanks to Dr. Akio Tojo and Mr. Takashi Goto for their support of the IDA project. Thanks also to JRI developing members for their comments and discussions.


  1. W. R. Cheswick, and S. M. Bellovin, "Firewalls and Internet Security: Repelling the Wily Hacker,'' Addison Wesley Publishing Company, 1994.
  2. D. E. Denning, "An Intrusion-Detection Model,'' IEEE Transactions on Software Engineering, Vol. SE-13. No. 2, pp. 222-232, 1987.
  3. S. Kumar, "Classification and Detection of Computer Intrusions,'' Department of Computer Sciences, Purdue University, Ph.D. Dissertation, 1995.
  4. S. Kumar and E. Spafford, "An Application of Pattern Matching in Intrusion Detection,'' Technical Report 94-013, Purdue University, Department of Computer Science, 1994.
  5. R. Gray, D. Rus, and D. Kotz, "Transportable Information Agents,'' Technical Report TR96-278, Department of Computer Science, Dartmouth College, 1996. http://www.cs.dartmouth.edu/~agent/
  6. "SunSHIELD Basic Security Module Guide,'' Part No:802-1965-10, Revision A, Sun Microsystems,Inc.
  7. R.Gray, David Kotz, George Cybenko, and Daniela Rus, "Security in a multiple-language mobile-agent system,'' in Giovanni Vigna, editor, Lecture Notes in Computer Science: Mobile Agents and Security, 1998. To appear http://actcomm.dartmouth.edu/~rgray/#papers

[INET'99] [ Up ][Prev][Next]