WIXLIB

with many other privileged Unix processes. All of our datato date have been generated on Sun SPARCstatiions runningunpatched versions of SunOS 4.1.1 and 4.1.4, using the included sendmail. The strace package, version 3.0,was used to gather information on system calls.4.1 Building a normal databaseAlthough the idea of collecting traces of normal behaviorsounds simple, there are a number of decisionis that mustbe made regarding how much and what kind of normalbehavior is appropriate. Specifically, should we geineratean artificial set of test messages that exercises; all normalmodes of sendimail or should we monitor real user mailand hope that it covers the full spectrum of normal (morein the spirit of our approach)? This question is especiallyrelevant for sendmai 1because its behavior is so varied.If we fail to capture all the sources of legal variations, thenit will be easier to detect intrusions and be an unfair testbecause of false positives. We elected to use a suite of112 artificially constructed messages, which includled asmany normal variations as possible. These 112 messagesproduced a a combined trace length of over 1.5 millionsystem calls. For a window size of 6, the 112 messagesproduced a database with 1500 entries, where one entrycorresponds to a single pair of system calls with a lookaheadvalue (e.g., read is a legal successor to open at positialn 1).Once the normal database is defined, the next decision ishow to measure new behavior and determine if it is nonmal orabnormal. The easiest and most natural measure is simply tocount the number of mismatches between a new itrace and thedatabase. We report these counts both as a raw numbler andas a percentage of the total number of matches performed inthe trace, which reflects the length of the trace. Ideally, wewould like these numbers to be zero for new examples ofnormal behavior, and for them to jump significantly whenabnormalities occur. In a real system, a threshold valuewould need to be determined, below which a behavior issaid to be normal, and above which it is deemed anomalous.In this study, we simply report the numbers, because we arenot taking any action or making a binary decision based onthem. Because our normal database covers most variationsin normal, any mismatches are in principle significant.Returning to our earlier questions, the size of the normal database is of interest for two reasons. First, if thedatabase is small then it defines a compact signature for therunning process that would be practical to check in real-timewhile the process is active. Conversely, if the database islarge then our approach will be too expensive to use foron-line monitoring. Second, the size of the normal databasegives an estimate of how much variability there is in thenormal behavior of sendmai 1. This consideration is crucial because too much variability in normal would precludeI--Type of Behavior - ## of msgs.message lengthnumber of messagesmessage contentsubjectsenderheceiverdifferent mailersforwardingbounced mailqueuingvacationb:otal12706244444I2112Table 1. Types and number of mail messagesused to generate the normal database forsendmail.detecting anomalies. In the worst case, if all possible sequences of length 6 show up as, legal normal behavior, thenno anomalies could ever be detected. A related question ishow much normal behavior should be sampled to providegood coverage of the set of alllowable sequences. We usedthe following,procedure to build the normal database:2-1. Enumer,ate potential sources of variation for normalsendmini1operation.2. Generatle example mail messages thatsendmail to exhibit these variations.cause3. Build a inormal data base from the sequences producedby step 2.4. Continue generating normal mail messages, recordingall mismatches and adding them to the normal databaseas they occur.We considered variations in message length, numberof messages, message content (text, binary, encoded, encrypted), message subject line, senderheceiver and mailers.We also look.ed at the effects of forwarding, bounced mailand queuing. Lastly, we considered the effects of all thesevariations in the cases of remote and local delivery. For eachtest, we generated three databases, one for each differentwindow size (5, 6 and 11). Each database incorporates allof the features described above, producing zero mismatchesfor mail with any of these features.Table 1 shows how many messages of each type wereused to generate the normal daiabases. We began with message length and tried 12 different message lengths, rangingfrom 1 line lo 300,000 bytes. From this, we selected the'We followeld a similar procedure it0 generate the normal database forl p r and obtained a database of 534 normal pattems.123

shortest length that produced the most varied pattern of system calls (50,000 bytes), and then used that as the standardmessage length for the remaining test messages. Similarly,with the number of messages in a sendmail run, we firstsent 1 message and traced sendmail then we sent 5 messages, tracing sendmail,and so forth, up to 20 messages.This was intended to test sendmail ’ s response to burstsof messages. We tested message content by sending messages containing ascii text, uuencoded data, gzipped data,and a pgp encrypted file. In each case, a number of variations was tested and a single default was selected beforemoving on to the next stage. These messages constitutedour corpus of normal behavior. We reran this set of standard messages on each different OS and sendmail cfvariant that we tried, thus generating a normal database thatwas tailored to the exact operating conditions under whichsendmail was running. Of the features considered, thefollowing seemed to have little or no effect: the number ofmessages, message content, subject line, sendersheceivers,mailers and queuing. Two more unusual features, forwardedmail and bounced mail, affected remote traces far less than%oca1traces.5ProcesssendmailIs1s -1Is -aPSps .528.825.44.3611%#%#00.0238.9239 32.18.323358.3458.1214.956 14.2450 31.51522 1823931824#Table 2. Distinguishing sendmail from otherprocesses. Each column lists two numbers:the percentage of abnormal sequences (labeled %) and the number of abnormal sequences (labeled #) in one typical trace ofeach process (when compared against thenormal database for sendmail). The columnslabeled 5, 6 and 11 refer to the sequencelength (window size) used for analysis. Thesendmail data show no misses, becausesendmail is being compared against its owndatabase.Figure 1 shows how new patterns are added to thedatabase over time during a normal sendmail run. Thedata shown are for 10,000 system calls worth of behavior,but we have also performed runs out to 1.5 million systemcalls (data not shown), with essentially zero mismatches.Overall, the variability in the behavior of sendmai1at thesystem call level is much smaller than we expected.4.2 Distinguishing Between ProcessesTo determine how the behavior of sendmai1compareswith that of other processes, we tested several common processes against the normal sendmail database with 1500entries. Table 2 compares normal traces of several common processes with those of sendmail.These processeshave a significant number of abnormal sequences, approximately, 5-32% for sequences of length 6, because the actions they perform are considerably different from thoseof sendmail. We also tested the normal database forl p r and achieved similar results (data not shown). l p rshows even more separation than that shown in Figure 2,presumably because it is a smaller program with more limited behavior. These results suggest that the behavior ofdifferent processes is easily distinguishable using sequenceinformation alone.Finally, we ask what percentage of the total possiblepatterns (for sequences of length 6) is covered by the normal database. For example, if the database is completelyfull (all possible patterns have been recorded as normal)by 3000 system calls, then it would hardly be surprisingthat no new patterns are seen over time. However, as wediscussed earlier, such variability would be useless for identifying anomalous behavior. Consequently, the goal is tofind a database that is small with respect to the space ofpossible patterns. Our initial data here are encouraging. Weestimate that the sendmai1database described above covers about 5 x lop5%of the total possible patterns of systemcalls (that is, sequences built from all possible system calls,about 180 for Unix, not just those invoked by sendmail),an extremely small fraction. This figure is somewhat misleading, however, because it is unlikely that the sendmai1program is capable of generating many of these sequences.The most accurate comparison would be against a databasethat contained all the patterns that sendmai1could possibly produce. This would require a detailed analysis of thesendmail source code, an area of future investigation.4.3 Anomalous BehaviorWe generated traces of three types of behavior that differ from that of normal sendmail: traces of successful sendmai1 intrusions, traces of sendmai1 intrusion124

030004130050006000700080013900010000# of System CallsFigure 1. Building a normal database. The graph shows how rnany new patterns are added to thedatabase over time. By running our artificially constructed set alf standard messages, a wide varietyof normal behavior is seen in the early pairt of the run (out to about 3000 system calls). After thistime, virtually no new patterns are enc:ountreredunder normal sendmail conditions. These data are aconcatenation of the logs used to generate our normal database.attempts that failed, and traces of error conditions. Ineach of these cases, we compared the trace with the: normal sendmail database and recorded the number of mismatches. In addition, we tested one successful 1pr intrusionand compared its trace with a normal database for l p r . Table 3 shows the results of these comparisons. Each row inthe table reports data for one typical trace. In most cases, wehave conducted multiple runs of the intrusion with identicalor nearlv identical results.in sendmai 1,replacing part of the sendmail's runningimage with the attacker's machine code. The new code isthen executed, causing the standard U 0 of a root-owned shellto be attached1to a port. The attacker may then attach to thisport at her leisure. This attack can be run either locally orremotely, andl we have tested both modes. We also variedthe number of commands issued as root after a successfulattack.To date, we have been able to execute and trace: fourattacks: sunsendmailcp [l], a syslog attack script l[2,7],a decode alias attack, and lprcp [3].In older sendmai 1 installations, the alias databasecontains an entry called "decode," which resolves touudecode, a UNIX program that converts a binary fileencoded in plain text into its original form and name.uudecode respects absolute filenames, so if a file "bar.uu"says that the (originalfile is "/home/foo/.rhosts,"then whenuudecode is givenit will attempt to create.rhosts fik.sendmail will generally run uudecodeas the semi-privilegeduser daemon, so email sent to decodecannot overwrite any file on the: system; however, if a file isworld-writable, the decode alias entry allows these files tobe modified by a remote user.The sunsendmailcp Script uses a special COmmandline option to cause sendmail to append an email messageto a file. By Using this Script O n a file such as / rhost s ,a local user may obtain root access.fooVsThe syslog attack uses the syslog interface to overllow abuffer in sendmail. A message is sent to the isendmailon the victim machine, causing it to log a very long, speciallycreated error message. The log entry overflows a lbuffer125

65Anomalysunsendmailcpsyslog:remote 1remote 2local 1local 2decodelPrcPsmS65asmSxforwardloop#95%#5.22153.9 361 4.2 4701.4 111 1.5 1373.0 235 4.2 3984.1 307 3.4 309240.321 0.31.17 1.4120.427 0.4361.4 110 1.7 157581.6 43 53138%3.8#72%4.1behavior. In general, it would be desirable if error conditionsproduced less deviation from normal than intrusions butwere still detectable. For the one case we have studied, alocal forwarding loop, this is what we observed (excludingthe decode and Ipr exploits). A forwarding loop occurs whena set of HOME/ . forward files form a logical circle. Weconsidered the simplest case, with the following setup:11Although forwarding loops are not malicious, they can adversely affect machine performance, as hundreds of messages are bounced from machine to machine. Results arereported in Table 3. They differ from normal by a small, yetclear, percentage (2.3%).Table 3. Detecting Anomalies. The tableshows the results of tracing sendmail and Iprduring various anomalous situations: successful intrusions (sunsendmailcp, syslog,decode, and Sprcp), unsuccessful intrusions,(sm565a and sm5x), and abnormal errors (forward loop). The data for the syslogd attack show the results of tracing sendmail(rather than tracing syssogd itself). The %column indicates the percentage of abnormalsequences in one typical intrusion, and the# column indicates the number of abnormalsequences.5DiscussionThese preliminary experiments suggest that short sequences of system calls define a stable signature that candetect some common sources of anomalous behavior insendmail and lpr.Because our measure is easy to compute and is relatively modest in storage requirements, itcould be plausibly implemented as an on-line system, inwhich the kernel checked each system call made by processes running as root. Under this scheme, each site wouldgenerate its own normal database, based on the local softwarehardware configurationand usage patterns. This couldbe achieved either with a standard set of artificial messages,such as those we use to build our normal database, or itcould be completely determined by local usage patterns. Itis likely that some combination of the two would be mosteffective.The data reported in this paper are preliminary. In addition to testing other processes, especially those that arecommon routes for intrusion, we would like to extend oursendmai 1 experiments in several ways. These include:testing additional sendmai1exploits, conducting systematic runson common sendmail and sendmail.cf variants, and testing the effect of other system configurations onthe normal behavior of sendmail. Another area for further study is the database of normal behavior, for example,how do we choose what behavior to trace? This is especially relevant for sendmail because its behavior is sovaried. If we fail to capture all the sources of legal variation, then we will be subject to false positives. On the otherhand, if we allow different databases at different sites, thensome variation would be desirable both as customizationsto local conditions and to satisfy the uniqueness principlestated earlier. Finally, we would like to study the normalbehavior of sendmail running on a regularly used mailserver. Such real-world data would help confirm the natureThe lprcp attack script uses lpr to replace the contentsof an arbitrary file with those of another. This exploit usesthe fact that older versions of lpr use only 1000 differentnames for printer queue files, and they do not remove theold queue files before reusing them. The attack consists ofgetting Ipr to place a symbolic link to the victim file in thequeue, incrementing lpr’scounter 1000 times, and thenprinting the new file, overwriting the victim file’s contents.The results for these four attacks are shown in Table3. The sunsendmailcpexploit is clearly detected with5.2% anomalous sequences (for length 11). Likewise, thesyslog attack is clearly detected in every run, with theanomalous sequence rate varying between 1.7% and 5.3%,for a sequence window of 6. The decode attack is lessdetectable at 0.3%,and the lpr attack is detected at 2.2%.A second source of anomalous behavior comes from unsuccessful intrusion attempts. We tested two remote attackscripts, called sm565a and sm5x [5, 61. SunOS 4.1.4 haspatches that prevent these particular intrusions. The resultsare shown in Table 3. Overall, the percentage of abnormal sequences is on the low end of the range for successfulattacks.Error conditions provide a third source of anomalous126

of sendmai1 ’ s normal behavior in practice, especiallythe two we have used, especiaI1:y in an on-line system, wherethe length of the trace would be indefinitely long. A relatedquestion is the choice of pattern matching rule. We currentlymonitor only the presence or absence of patterns, not theirrelative frequency. However, thlere are many other matchingcriteria that could be tried. For example, we could representthe possible sequences of legal system calls as a Markovchain and define a criterion based on expected frequencies.Returning to the larger question of how to build an artificial immune system for a computer, the work reported hereconstitutes an initial step in this direction. We have identified a signature for self that is stable across a wide variety ofnormal behavior and sensitive to some common sources ofanomalies. Further, the definition provides a unique signature, or identity, for different kinds of processes. A secondform of identity is possible because the method used to collect normal tiraces allows for a unique database at each site.Thus, a successful intrusion at one site would not necessarily be successful at all sites running the same software, andit would increase the chance off at least one site noticing anattack. Networks of computers are currently vulnerable tointrusions at least in part because of homogeneities in thesoftware the:y run and the methods used to protect them.Our behavioral notion of ideniity goes well beyond a simple checksum, login, password, or IP address, because itconsiders dynamic patterns of ,activityrather than just staticcomponents.However, the current system is a long way from havingthe capabilities of a natural immune sys

privileged processes. Monitoring privileged processes has several advantages over monitoring user profiles[ 141. Root processes are more dangerous ithan user processes because they have access to more parts of the computer system. They have a limited range of behavior, and their behavior is relatively stahle over time.