Research and Advances
Architecture and Hardware

A Cop on the Beat: Collecting and Appraising Intrusion Evidence

Effective intrusion detection, like police work, requires prioritization and careful fusion of evidence from disparate sources.
Posted
  1. Introduction
  2. The Beat
  3. The Crimes
  4. The Evidence
  5. The Conscientious Cop
  6. Learning to Please the Judge and Jury
  7. Conclusions
  8. References
  9. Author
  10. Footnotes

There is little question that the ever-growing volume and diversity of information available over global and local networks has led to drastic improvements in the efficiency and effectiveness of institutions worldwide. However, this improved availability of information has also led to an increased dependency on these network resources to the point where disruptions in their availability can have dramatic negative effects on everyday operations. Given this situation, it is not at all surprising to see the topic of defensive information warfare attracting substantial interest.

In defending network resources any number of technologies might be applied. Firewalls, encryption technology, authentication devices, vulnerability checking tools, and other products can all offer improved security. But even when a computer system is equipped with stringent authentication procedures and firewalls, it is still susceptible to hackers who take advantage of system flaws and social engineering tricks (for example, impersonating a system administrator on the phone to acquire user passwords). Computer systems with no connection to public networks remain vulnerable to disgruntled employees or other insiders who misuse their privileges. Given these enduring threats, it is only sensible to establish a second line of defense in the form of an intrusion detection system.

The field of intrusion detection began close to 20 years ago. The majority of early systems were designed to detect attacks upon a single host. More recent systems consider the role of networks and look for evidence of intrusions by passively monitoring LAN traffic. Yet another set of intrusion detection systems is designed to collect and aggregate evidence from multiple sources in order to detect coordinated or multistage attacks on a network [5]. Such evidence fusion is an important capability since, in general, a network is vulnerable to attacks distributed across its hosts. Once an intruder establishes a foothold, it is substantially easier for him to attack peer hosts through a shared file system, shared accounts, or by other means. And by compromising multiple hosts and/or accounts an intruder may be able to hide his identity or disguise his attacks unless evidence is aggregated.

The most obvious conclusion that can be drawn from two decades of research is that there are no easy answers, no silver bullets. Effective intrusion detection capability remains elusive as computing environments become more complex and crackers continually adapt their techniques to overcome innovations in computer security. Additionally, network administrators have been slow to adopt intrusion detection technology due to, among other reasons, excessively high false alarm rates associated with existing tools. These false alarms require a high degree of human analysis, thus reducing existing intrusion detection systems to the status of simple evidence sources. Given this observation, further advances in automated intrusion detection will require the development of new means of exploiting available evidence.

In this article, we survey the field of intrusion detection and describe our approach to improving intrusion recognition capability and decreasing false alarm rates through the application of evidence fusion techniques. The driving force behind our research is the recognition that the most promising avenue to improving intrusion detection systems is to enable them to draw on diverse and redundant evidence sources in an intelligent manner. In developing our intrusion detection system, ICE (Intelligent Correlation of Evidence) [2], we have focused on the use of a machine learning-based approach to evidential reasoning that is robust in the face of imperfect or corrupt evidence. A good metaphor for describing the requirements of intrusion detection and our approach to improving on the state of the art is that of a beat cop (let us call him Joe) on patrol solving crimes.

Back to Top

The Beat

Where can and do intrusions occur? The answer to this question is that intrusions occur anywhere people have physical or network access to the computer resources of others. Research institutions, Fortune 500 companies, military institutions, and universities are all susceptible to a variety of threats ranging from a teenage hacker having a good time to disgruntled employees out to cause real damage.

Why is this significant? Because these varied institutions have drastically differing computing environments as described by, for example, their policies, hardware platforms, bandwidth requirements and security precautions. And these differences can drastically affect the threats they face and the applicability of particular intrusion detection paradigms. Despite the sales pitch by a number of intrusion detection system producers, there are no "one-size-fits-all" solutions. One must always balance the cost in dollars, resource overhead, and inconvenience against the need for security. Successful intrusion detection comes down to the availability of evidence in the computing environment and the ability of the chosen intrusion detection system to make the most of that potentially limited evidence.

Back to Top

The Crimes

In order to understand the collection and use of evidence by an intrusion detection system, it is first important to realize that threats to networked computer systems come in a number of forms. For our purposes, we form two simple attack classes:

  • Outsider attacks. This form of attack is launched by an unauthorized computer user. The attacker will use system vulnerabilities or misconfigurations, human engineering techniques, stolen or broken passwords to gain access to computers. The intruder may then engage in a wide variety of malicious activities.
  • Insider attacks. In this case, the intruder already has legitimate access to a computer system, but utilizes any of the previously mentioned techniques to gain additional privileges and/or to misuse or damage data the intruder may otherwise have legitimate access to. While such attacks receive less attention, they can be more pernicious and insidious than outsider attacks due to the information and system privileges available to legitimate users.

Both classes of attack may occur over a network connection or on-site. One special and particularly prevalent form of attack that may be launched by either an insider or an outsider is the denial of service attack where the intention is to dramatically decrease the availability of computing resources.

Intruders may be assisted in their work by computer programs that automate the attack. This includes the launching of worms (programs that propagate across a network using the resources of compromised hosts to attack other machines) or the implantation of Trojan horse programs (programs that are altered by an attacker for some malicious purpose such as collecting passwords) that may do the dirty work for the intruder without requiring direct oversight. Additionally, some attacks may take the form of coordinated multistep exploitations using parallel sessions in which the distribution of steps between sessions is designed to obscure the unified nature of the attack or to allow the attack to proceed more quickly. To detect such coordinated activity, an intrusion detection system must correlate evidence from multiple sources.

Back to Top

The Evidence

The types of evidence that can be drawn on during the intrusion detection process fall into two distinct classes, namely direct and indirect evidence. Returning to our beat cop metaphor, Joe may have eyewitness accounts of the execution of a crime, such as a bank robbery, which are examples of direct evidence. On the other hand, finding a black ski mask and pistol (indirect evidence) on the person of a suspect that fled from Joe for no apparent reason may spur Joe into further investigation.

In the realm of intrusion detection, direct evidence is termed "misuse behavior" and indirect evidence is referred to as "anomalous behavior." Misuse evidence takes the form of well-defined patterns of activity known to be malicious. Due to the fact that these patterns have been observed before and are, therefore, well documented, a purely rule-based detection system encapsulating the known information about the attack can be applied.

In the case of anomalous behavior, it is hoped that illegal, intrusive, or criminal activity can be detected as a result of pursuing a reasonable suspicion or hunch. Evidence leading to this increasing of suspicion (without necessarily increasing the belief in a particular threat) may come, for example, from observed deviations from historically normal behavior. Evidence sources for intrusion detection are described in the following paragraphs.

Audit trails. Early intrusion detection technology focused on the analysis of audit trails from individual hosts on a network. This audit data is essentially a chronological record of system activities that is sufficiently detailed to allow the reconstruction and review of the progression of events and resulting system states. The clear benefit of this form of evidence is its completeness. If an intrusion has occurred on a host that collects sufficiently detailed audit data and the intrusion detection system knows what it is looking for, then uncovering the attack may just be a matter of time.

Unfortunately, intrusion detection systems that rely on audit trails as their only evidence source have several substantial drawbacks. First, collecting audit trails can have a dramatic negative impact on system performance due to the sheer volume of data to be logged. Second, if the analysis is to be done on the host on which the data is collected, then performance on that host will be further degraded. On the other hand, if the analysis of the collected audit data is done at some central location, large amounts of data must be moved over the network, taking up valuable network bandwidth. A third problem with intrusion detection systems relying solely on audit trail data is that the correlation of evidence from multiple hosts can be difficult since network activity is not monitored and determining the relative timing of events can be troublesome. Finally, auditing mechanisms are not immune to attack themselves. Auditing tools may be disabled and stored data may be corrupted.

Network monitors. Network surveillance tools provide another widely used evidence source for intrusion detection. In fact, intrusion detection based on passively monitoring network traffic has had substantially more success detecting intruders than audit trail-based systems and has been labeled by many as the solution to network intrusion detection. There are a number of reasons why, at first glance, these techniques represent a very attractive intrusion detection solution. First, the types of threats that have received substantial attention in the press are the aforementioned "outsider" threats. Since these attacks occur over a network, one only need analyze the data stream, identify the signatures of unauthorized activity, and take action. Second, the installation of a network sniffer does not cause degradation to network performance. Finally, the data stream for potentially hundreds of hosts passes through the network devices, allowing a single control point for the intrusion detection system and alleviating the need to place additional processing loads on individual hosts. Avoiding the costs of installing individual intrusion monitors on a potentially diverse set of hosts makes the deployment of the intrusion detection system relatively simple.


Despite the sales pitch by a number of intrusion detection system producers, there are no "one-size-fits-all" solutions.


Network monitoring tools can play multiple intrusion detection roles. The first, and most obvious, is for the detection of known patterns of intrusive behavior. Alternatively, network monitors can be used to assist in tracking intruders after an attack has been detected, using a statistical profile of the users’ activity as a thumbprint [6] to determine the connections used during an attack. Other techniques can be used to observe global patterns of activity that are associated with certain forms of attack such as a worm. Finally, the analysis of network data can be used to detect anomalous activity.

Under ideal circumstances, network monitoring tools offer an easy to install and potentially flexible and effective means for intrusion detection. Unfortunately, conditions are seldom ideal. In the worst scenario, an intrusion will be launched by an insider with physical access to the host being attacked. In this situation the network monitor is of no help because nothing related to the attack is being transmitted over the network. In other situations, intrusion detection based solely on network traffic analysis is akin to our exemplar beat cop Joe attempting to detect a murder by walking down a street at night, watching shadows play off the curtains of houses he passes. Because the network monitor does not have access to the state of the machines that reside on the network and some network data packets may be missed, it can be very difficult to determine what is really happening. Further, recent studies suggest that network monitors are susceptible to a number of techniques that can allow savvy intruders to elude detection [4]. A final threat to network monitoring based intrusion detection systems is the widespread utilization of encryption, which would obscure the majority of the important evidence that is broadcast over the network.


Developers of intrusion detection systems should attempt to enumerate all the means for detecting an attack.


Tripwires. One inexpensive technique for intrusion detection is provided by the simple laying of "tripwires." These software programs take snapshots of certain file system characteristics that can be used to detect critical file additions, modifications, or deletions. Most intruding hackers will either install backdoor entry points, or unwittingly alter file system and directory characteristics while they are snooping. A detector monitoring for these changes can provide very helpful direct evidence of an intrusion.

Honey pots. Another technique that can be used in conjunction with any of the preceding techniques is the creation of "honey pot lures." These lures can be anything from documents that appear to contain sensitive information, to fake system administration accounts. The idea is to entrap and keep an intruder occupied long enough to determine the identity of the intruder.

Configuration checking tools. Otherwise called "vulnerability assessment tools," these programs can be used to detect insecure operating system, file system, or network configurations. While these tools are generally used separately from intrusion detection efforts, they can provide very useful information akin to that provided by tripwire systems. These systems can be particularly useful in uncovering suspicious patterns of system misconfiguration that may suggest malicious intent.

Operating system commands. Not to be overlooked in efforts to detect intrusions automatically are the very tools that system administrators use every day to manually detect and resolve security incidents. Looking for hidden processes, checking log files, and testing for known backdoor passwords are among the multitudes of manual techniques that system administrators may engage in via available system commands. For example, one can compare the outputs of similar programs such as top and ps in Unix to verify that one has not been replaced by an intruder’s version as a means of camouflaging his attack.

Anomaly detection systems. Anomaly detection has played a significant role in the history of intrusion detection. The goal with such systems is to develop profiles of users, host activity, network connections, or system programs in the hopes of detecting deviations from the norm indicating an intrusion. These techniques act as a complement to other intrusion detection techniques that seek to detect known malicious use patterns. The potential tools for this task vary greatly in both responsibility and complexity. One simple example is keystroke analysis, in which a program monitors the time interval between keystrokes and notes deviations from historic norms in the hopes of detecting a masquerader. Other systems for anomaly detection attempt to model the normal command usage for an individual as well as user groups in the hopes of either detecting masqueraders or users acting suspiciously. There is yet another set of systems being developed to detect when programs are acting in atypical fashion by observing system call patterns. Such unusual patterns may signify that an attacker is taking advantage of a program vulnerability or that the program in question is a Trojan horse.

Miscellaneous. There exist numerous other potential evidence sources that an intrusion detection system could draw on. These include: alert messages from separately administered networks, lists of known malicious users and/or their hosts of origin, empty log files (indicating an intruder attempting to cover his tracks), to name a few.

There remain a couple of important additional comments to be made about evidence sources. The first is that not all of the evidence sources will be applicable to a particular site all the time. It may not be feasible, for example, to collect audit trails in a research laboratory during work hours. It is similarly important to recognize that all of the aforementioned evidence sources are fallible. The device monitoring network activity might itself be attacked or otherwise fail, log files may be corrupted, the disk storing audit data may become full, programs may be replaced, and so forth. Further, it may simply be impossible to detect an attack without drawing on information from multiple sources. It is therefore important to recognize the need for redundancy. It is not sufficient to determine one method for detecting an attack. Rather, as is being done with ICE, the developers of intrusion detection systems should attempt to enumerate all the means for detecting that attack.

One simple example of the usefulness of drawing on multiple evidence sources is in the tracking of users and objects (files) as they move across the network. This activity may itself represent an attack if it involves unauthorized access to accounts. More importantly, experienced intruders may distribute their intrusive behavior over a number of hosts on a LAN in order to thwart single host intrusion detection techniques. Correlating data from several independent sources, including the network itself, is required to accurately recognize this type of behavior and to track an intruder’s activities [3].

Back to Top

The Conscientious Cop

In order for an intrusion detection system to be successful, it is important that it operates in a deliberative manner. Evidence must be gathered and analyzed in a timely fashion so as to improve the chances of detecting an intrusion before significant damage is done or before the trail left by the intruder becomes cold. The requirement for real-time effective intrusion alerts has represented a substantial challenge to date. Additionally, the failure of existing systems to accurately report varied intrusions without overwhelming the user of the system with spurious reports has led, in part, to the limited adoption of the technology.

In support of the requirements for accurate and efficient evidence collection and analysis, an intrusion detection system must be able to draw on the potentially diverse (and potentially limited) evidence sources that are made available to it. In order to do this thoughtfully, the capability to reason about the relative worth of evidence has been integrated into ICE. This means that given a possibly large number of active hypotheses about malicious activity, ICE balances: the value of the evidence in proving or refuting a particular hypothesis, the threat posed by the hypothesized attack, and the potential cost in time and computational resources of collecting data.

This process is again similar to the one faced by Joe, the beat cop. It is incumbent on the officer to determine what crimes and evidence are worth pursuing. In doing this, Joe must also keep in mind that he has limited resources available to him in conducting his investigation. He may be able to acquire help and do things in parallel, but time spent doing one thing means time not pursuing other leads or other crimes.

Another factor Joe must consider is the rights of the population of law-abidding citizens he serves. For example, it would not be a good decision on Joe’s part to pull over every car on the road, so that he may determine if the driver has been drinking. Not only is this a poor use of his time (banks may be being robbed), but it is also a terrible use of the time of the innocent drivers. Likewise, the use of computational resources for the random and intensive search for evidence is a poor methodology for an intrusion detection system. In fact, if intruders can convince an intrusion detection system to continually increase its use of computational resources for little or no gain, then the intruder has succeeded in a denial of service attack because the users of the monitored computers will be hampered in the execution of their everyday tasks.

Back to Top

Learning to Please the Judge and Jury

System administrators or computer security personnel are the ones who play the role of judge and jury when it comes to intrusion detection. These users will differ substantially in assets they have to protect, the policies they seek to enforce, the time they have available to devote to intrusion detection efforts, and their accountability to the users of the network they are protecting. Given these differences, it is important that an intrusion detection system be easily tailorable. Also important is the ability to incorporate whatever evidence sources are available at the time of operation. If an evidence source is unavailable or is not properly configured for the task, then the intrusion detection system must make do with the evidence at hand. In some circumstances (when there is sufficient warning), it may be beneficial to turn on or reconfigure an evidence source. Returning to our metaphor, Joe may turn on a microphone in order to collect evidence or change the orientation of a hidden surveillance camera in order to capture a drug deal on videotape.

ICE achieves these adaptive evidence collection and evaluation objectives through the use of Bayesian network-based evidential reasoning and associated machine learning techniques (see [1]). ICE starts from a causal theory of how executing an attack plan causes particular activities, and reasons from the observed effects of those activities to the underlying causes. By utilizing a priori knowledge about the monitored network’s state and dynamics (summarized by a conditional probability distribution), the attack recognizer can schedule evidence collection and use partial observations of user actions and state changes to evaluate attack hypotheses. The ability to utilize redundant evidence sources effectively allows ICE to operate in spite of particular evidence sources being disabled, corrupted, or spoofed.

The application of this approach allows ICE to reason about uncertainty and incomplete evidence, form hypothesis testing strategies, and learn how to suit the operator’s preferences. Of particular importance is the use of feedback from the intrusion detection system operator to automatically adjust: the internal ranking of threats, the evidence threshold at which the user wants to be notified and the relative weighting of evidence sources. Through this learning process, an intrusion detection system may well be able to avoid the excessively high false alarm rates that plague existing intrusion detection systems.

Back to Top

Conclusions

Intrusion detection research has now been conducted for nearly 20 years, yet it remains in its infancy. Existing intrusion detection systems do not perform well in the face of failing evidence sources and experienced hackers who can obscure their actions through a variety of sophisticated methods. Further, today’s intrusion detection systems are not capable of sufficiently verifying the presence of intrusions while avoiding excessively high false alarm rates. In this article we argued that these failings can be traced back to the fact that many intrusion detection systems draw on a single, fallible evidence source. We also argued that the effectiveness of intrusion detection systems can be improved, and their utilization facilitated, by the incorporation of machine learning techniques for the automatic tuning of the evidential reasoning system to suit the requirements of particular users and operating environments and the availability of evidence. Early experience in developing the Intelligent Correlation of Evidence system supports these hypotheses and suggests that intelligently selecting and fusing data from a body of complementary and redundant evidence sources can result in substantial improvements in effectiveness, accuracy, and robustness.

Back to Top

Back to Top

Back to Top

    1. Charniak, E. Bayesian networks without tears. AI Magazine 12, 4 (Winter 1991), 50–63.

    2. Goan, T. A New Integrated Approach to Intrusion Prevention, Detection, and Response. Tech. Rep. SHAI, San Mateo, California, 1998.

    3. Ko, C., Frincke, D., Goan, T., Heberlein, L.T., Levitt, K., Mukherjee, B., Wee, C. Analysis of an algorithm for distributed recognition and accountability. In Proceedings of the First ACM Conference on Computer and Communication Security. (Fairfax, VA, 1993), 154–164.

    4. Ptacek, T. and Newsham, T. Evasion and Denial of Service: Eluding Network Intrusion Detection. Tech. Rep., Secure Networks, Calgary, Alberta, Canada, 1998.

    5. Snapp, S., Brentano, J., Dias, G., Goan, T., Heberlein, L.T., Ho, C., Levitt, K., Mukherjee, B., Smaha, S., Grance, T., Teal, D., Mansur, D. DIDS (Distributed Intrusion Detection System)—Motivation, architecture, and an early prototype. In Internet Besieged: Countering Cyberspace Scofflaws, P.J. Denning and D.E. Denning, Eds. Addison-Wesley, 1997.

    6. Staniford-Chen, S. and Heberlein, L.T. Holding intruders accountable on the Internet. In Proceedings of the 1995 IEEE Symposium on Security and Privacy (Oakland, CA, 1995), 34–49.

    Support for this work was provided by the U.S. Air Force under contract F30602-98-C-0026.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More