Bro: A System for Detecting Network Intruders in Real-Time

* This work was supported by the Director, Office of Energy Research, Office of Computational and Technology Research, Mathematical, Information, and Computational Sciences Division of the United States Department of Energy under Contract No. DE-AC03-76SF00098. This paper appears in the Proceedings of the 7th USENIX Security Symposium, San Antonio, TX, January 1998. This revision of the paper corrects an error in the original version, which in § 7 overstated the traffic level on the FDDI ring by a factor of two.

Vern Paxson
Network Research Group
Lawrence Berkeley National Laboratory*
Berkeley, CA 94720
vern@ee.lbl.gov

LBNL-41197

Revised January 14, 1998

Abstract

We describe Bro, a stand-alone system for detecting network intruders in real-time by passively monitoring a network link over which the intruder's traffic transits. We give an overview of the system's design, which emphasizes highspeed (FDDI-rate) monitoring, real-time notification, clear separation between mechanism and policy, and extensibility. To achieve these ends, Bro is divided into an ``event engine'' that reduces a kernel-filtered network traffic stream into a series of higher-level events, and a ``policy script interpreter'' that interprets event handlers written in a specialized language used to express a site's security policy. Event handlers can update state information, synthesize new events, record information to disk, and generate real-time notifications via syslog. We also discuss a number of attacks that attempt to subvert passive monitoring systems and defenses against these, and give particulars of how Bro analyzes the four applications integrated into it so far: Finger, FTP, Portmapper and Telnet. The system is publicly available in source code form.

1 Introduction

With growing Internet connectivity comes growing opportunities for attackers to illicitly access computers over the network. The problem of detecting such attacks is termed network intrusion detection, a relatively new area of security research [MHL94]. We can divide these systems into two types, those that rely on audit information gathered by the hosts in the network they are trying to protect, and those that operate ``stand-alone'' by observing network traffic directly, and passively, using a packet filter. In this paper we focus on the problem of building stand-alone systems, which we will term ``monitors.'' Though monitors necessarily face the difficulties of more limited information than systems with access to audit trails, monitors also gain the major benefit that they can be added to a network without requiring any changes to the hosts. For our purposes---monitoring a collection of several thousand heterogeneous, diversely-administered hosts--- this advantage is immense.

1 Or at least appear, according to their product literature, to do the same things---we do not have direct experience with any of these products. A somewhat different sort of product, the ``Network Flight Recorder,'' is described in [RLSSLW97, Ne97].
Our monitoring system is called Bro (an Orwellian reminder that monitoring comes hand in hand with the potential for privacy violations). A number of commercial products exist that do what Bro does, generally with much more sophisticated interfaces and management software [In97, To97, Wh97], 1 and larger ``attack signature'' libraries. To our knowledge, however, there are no detailed accounts in the network security literature of how monitors can be built. Furthermore, monitors can be susceptible to a number of attacks aimed at subverting the monitoring; we believe the attacks we discuss here have not been previously described in the literature. Thus, the contribution of this paper is not at heart a novel idea (though we believed it novel when we undertook the project, in 1995), but rather a detailed overview of some experiences with building such a system.

Prior to developing Bro, we had significant operational experience with a simpler system based on off-line analysis of tcpdump trace files. Out of this experience we formulated a number of design goals and requirements:

High-speed, large volume monitoring
For our environment, we view the greatest source of threats as external hosts connecting to our hosts over the Internet. Since the network we want to protect has a single link connecting it to the remainder of the Internet (a ``DMZ''), we can economically monitor our greatest potential source of attacks by passively watching the DMZ link. However, the link is an FDDI ring, so to monitor it requires a system that can capture traffic at speeds of up to 100 Mbps. In addition, the volume of traffic over the link is fairly hefty, about 20 GB/day.

No packet filter drops
If an application using a packet filter cannot consume packets as quickly as they arrive on the monitored link, then the filter buffers the packets for later consumption. However, eventually the filter will run out of buffer, at which point it drops any further packets that arrive. From a security monitoring perspective, drops can completely defeat the monitoring, since the missing packets might contain exactly the interesting traffic that identifies a network intruder. Given our first design requirement---high-speed monitoring---then avoiding packet filter drops becomes another strong requirement.

It is sometimes tempting to dismiss a problem such as packet filter drops with an argument that it is unlikely a traffic spike will occur at the same time as an attack happens to be underway. This argument, however, is completely undermined if we assume that an attacker might, in parallel with a break-in attempt, attack the monitor itself (see below).

Real-time notification
One of our main dissatisfactions with our initial off-line system was the lengthy delay incurred before detecting an attack. If an attack, or an attempted attack, is detected quickly, then it can be much easier to trace back the attacker (for example, by telephoning the site from which they are coming), minimize damage, prevent further break-ins, and initiate full recording of all of the attacker's network activity. Therefore, one of our requirements for Bro was that it detect attacks in real-time. This is not to discount the enormous utility of keeping extensive, permanent logs of network activity for later analysis. Invariably, when we have suffered a break-in, we turn to these logs for retrospective damage assessment, sometimes searching back a number of months.

Mechanism separate from policy
Sound software design often stresses constructing a clear separation between mechanism and policy; done properly, this buys both simplicity and flexibility. The problems faced by our system particularly benefit from separating the two: because we have a fairly high volume of traffic to deal with, we need to be able to easily trade-off at different times how we filter, inspect and respond to different types of traffic. If we hardwired these responses into the system, then these changes would be cumbersome (and error-prone) to make.

Extensible
Because there are an enormous number of different network attacks, with who knows how many waiting to be discovered, the system clearly must be designed in order to make it easy to add to it knowledge of new types of attacks. In addition, while our system is a research project, it is at the same time a production system that plays a significant role in our daily security operations. Consequently, we need to be able to upgrade it in small, easily debugged increments.

Avoid simple mistakes
Of course, we always want to avoid mistakes. However, here we mean that we particularly desire that the way that a site defines its security policy be both clear and as error-free as possible. (For example, we would not consider expressing the policy in C code as meeting these goals.)

The monitor will be attacked
We must assume that attackers will (eventually) have full knowledge of the techniques used by the monitor, and access to its source code, and will use this knowledge in attempts to subvert or overwhelm the monitor so that it fails to detect the attacker's break-in activity. This assumption significantly complicates the design of the monitor; but failing to address it is to build a house of cards. We do, however, allow one further assumption, namely that the monitor will only be attacked from one end. That is, given a network connection between hosts A and B, we assume that at most one of A or B has been compromised and might try to attack the monitor, but not both. This assumption greatly aids in dealing with the problem of attacks on the monitor, since it means that we can trust one of the endpoints (though we do not know which).

In addition, we note that this second assumption costs us virtually nothing. If, indeed, both A and B have been compromised, then the attacker can establish intricate covert channels between the two. These can be immeasurably hard to detect, depending on how devious the channel is; that our system fails to do so only means we give up on something extremely difficult anyway.

A final important point concerns the broader context for our monitoring system. Our site is engaged in basic, unclassified research. The consequences of a break-in are usually limited to (potentially significant) expenditure in lost time and re-securing the compromised machines, and perhaps a tarnished public image depending on the subsequent actions of the attackers. Thus, while we very much aim to minimize break-in activity, we do not try to achieve ``airtight'' security. We instead emphasize monitoring over blocking when possible. Obviously, other sites may have quite different security priorities, which we do not claim to address.

In the remainder of this paper we discuss how the design of Bro attempts to meet these goals and constraints. First, in § 2 we give an overview of the structure of the whole system. § 3 presents the specialized Bro language used to express a site's security policy. We turn in § 4 to the details of how the system is currently implemented. § 5 discusses attacks on the monitoring system. § 6 looks at the specialized analysis Bro does for four Internet applications: FTP, Finger, Portmapper, and Telnet. § 7 gives the status of the implementation, a brief assessment of its performance, its availability, and thoughts on future directions. Finally, an Appendix illustrates how the different elements of the system come together for monitoring Finger traffic.

2 Structure of the system

Figure 1: Structure of the Bro system
Bro is conceptually divided into an ``event engine'' that reduces a stream of (filtered) packets to a stream of higher-level network events, and an interpreter for a specialized language that is used to express a site's security policy. More generally, the system is structured in layers, as shown in Figure 1. The lower-most layers process the greatest volume of data, and hence must limit the work performed to a minimum. As we go higher up through the layers, the data stream diminishes, allowing for more processing per data item. This basic design reflects the need to conserve processing as much as possible, in order to meet the goals of monitoring highspeed, large volume traffic flows without dropping packets.

2.1 libpcap

From the perspective of the rest of the system, just above the network itself is libpcap [MLJ94], the packet-capture library used by tcpdump [JLM89]. Using libpcap gains significant advantages: it isolates Bro from details of the network link technology (Ethernet, FDDI, SLIP, etc.); it greatly aids in porting Bro to different Unix variants (which also makes it easier to upgrade to faster hardware as it becomes available); and it means that Bro can also operate on tcpdump save files, making off-line development and analysis easy.

Another major advantage of libpcap is that if the host operating system provides a sufficiently powerful kernel packet filter, such as BPF [MJ93], then libpcap downloads the filter used to reduce the traffic into the kernel. Consequently, rather than having to haul every packet up to userlevel merely so the majority can be discarded (if the filter accepts only a small proportion of the traffic), the rejected packets can instead be discarded in the kernel, without suffering a context switch or data copying. Winnowing down the packet stream as soon as possible greatly abets monitoring at high speeds without losing packets.

The key to packet filtering is, of course, judicious selection of which packets to keep and which to discard. For the application protocols that Bro knows about, it captures every packet, so it can analyze how the application is being used. In tcpdump's filtering language, this looks like:

   tcp port finger or tcp port ftp or
   tcp port telnet or port 111

That is, the filter accepts any TCP packets with a source or destination port of 79 (Finger), 21 (FTP), or 23 (Telnet), and any TCP or UDP packets with a source or destination port of 111 (Portmapper). In addition, Bro uses:

   tcp[13] & 7 != 0
to capture any TCP packets with the SYN, FIN, or RST control bits set. These packets delimit the beginning (SYN) and end (FIN or RST) of each TCP connection. Because TCP/IP packet headers contain considerable information about each TCP connection, from just these control packets one can extract connection start time, duration, participating hosts, ports (and hence, generally, the name of the application), and the number of bytes sent in each direction. Thus, by capturing on the order of only 4 packets (the two initial SYN packets exchanged, and the final two FIN packets exchanged), we can determine a great deal about a connection even though we filter out all of its data packets.

When using a packet filter, one must also choose a snapshot length, which determines how much of each packet should be captured. For example, by default tcpdump uses a snapshot length of 68 bytes, which suffices to capture linklayer and TCP/IP headers, but generally discards most of the data in the packet. The smaller the snapshot length, the less data per accepted packet needs to copied up to the user-level by the packet filter, which aids in accelerating packet processing and avoiding loss. On the other hand, to analyze connections at the application level, Bro requires the full data contents of each packet. Consequently, it sets the snapshot length to capture entire packets.

2.2 Event engine

The resulting filtered packet stream is then handed up to the next layer, the Bro ``event engine.'' This layer first performs several integrity checks to assure that the packet headers are well-formed. If these checks fail, then Bro generates an event indicating the problem and discards the packet.

If the checks succeed, then the event engine looks up the connection state associated with the tuple of the two IP addresses and the two TCP or UDP port numbers, creating new state if none already exists. It then dispatches the packet to a handler for the corresponding connection (described shortly). Bro maintains a tcpdump trace file associated with the traffic it sees. The connection handler indicates upon return whether the engine should record the entire packet to the trace file, just its header, or nothing at all. This triage trades off the completeness of the traffic trace versus its size and time spent generating the trace. Generally, Bro records full packets if it analyzed the entire packet; just the header if it only analyzed the packet for SYN/FIN/RST computations; and skips recording the packet if it did not do any processing on it.

We now give an overview of general processing done for TCP and UDP packets. In both cases, the processing ends with invoking a handler to process the data payload of the packet. For applications known to Bro, this results in further analysis, as discussed in § 6. For other applications, analysis ends at this point.

TCP processing. For each TCP packet, the connection handler (a C++ virtual function) verifies that the entire TCP header is present and validates the TCP checksum over the packet header and payload. If successful, it then tests whether the TCP header includes any of the SYN/FIN/RST control flags, and if so adjusts the connection's state accordingly. Finally, it processes any data acknowledgement present in the header, and then invokes a handler to process the payload data, if any.

Different changes in the connection's state generate different events. When the initial SYN packet requesting a connection is seen, the event engine schedules a timer for T seconds in the future (presently, five minutes); if the timer expires and the connection has not changed state, then the engine generates a connection_attempt event. If before that time, however, the other connection endpoint replies with a correct SYN acknowledgement packet, then the engine immediately generates a connection_established event, and cancels the connection attempt timer. On the other hand, if the endpoint replies with a RST packet, then the connection attempt has been rejected, and the engine generates connection_rejected. Similarly, if a connection terminates via a normal FIN exchange, then the engine generates connection_finished. It also generates several other events reflecting more unusual ways in which connections can terminate.

UDP processing. UDP processing is similar but simpler, since there is no connection state, except in one regard. If host A sends a UDP packet to host B with a source port of pA and a destination port of pB, then Bro considers A as having initiated a ``request'' to B, and establishes pseudo-connection state associated with that request. If B subsequently sends a UDP packet to A with a source port of pB and destination pA, then Bro considers this packet to reflect a ``reply'' to the request. The handlers (virtual functions) for the UDP payload data can then readily distinguish between requests and replies for the usual case when UDP traffic follows that pattern. The default handlers for UDP requests and replies simply generate udp_request and udp_reply events.

2.3 Policy script interpreter

2 There is a subtle design decision involved with processing all of the generated events before proceeding to read the next packet. We might be tempted to defer event processing until a period of relatively light activity, to aid the engine with keeping up during periods of heavy load. However, doing so can lead to races: the ``event control'' arrow in Figure 1 reflects the fact that the policy script can, to a limited degree, manipulate the connection state maintained inside the engine. If event processing is deferred, then such control may happen after the connection state has already been changed due to more recently-received traffic. So, to ensure that event processing always reflects fresh data, and does not inadvertently lead to inconsistent connection state, we process events immediately, before moving on to newly-arrived network traffic.
After the event engine has finished processing a packet, it then checks whether the processing generated any events. (These are kept on a FIFO queue.) If so, it processes each event until the queue is empty, as described below. It also checks whether any timer events have expired, and if so processes them, too. 2

A key facet of Bro's design is the clear distinction between the generation of events versus what to do in response to the events. These are shown as separate boxes in Figure 1, and this structure reflects the separation between mechanism and policy discussed in § 1. The ``policy script interpreter'' executes scripts written in the specialized Bro language (detailed in § 3). These scripts specify event handlers, which are essentially identical to Bro functions except that they don't return a value. For each event passed to the interpreter, it retrieves the (semi-)compiled code for the corresponding handler, binds the values of the events to the arguments of the handler, and interprets the code. This code in turn can execute arbitrary Bro scripting commands, including generating new events, logging real-time notifications (using the Unix syslog function), recording data to disk, or modifying internal state for access by subsequently invoked event handlers (or by the event engine itself).

Finally, along with separating mechanism from policy, Bro's emphasis on asynchronous events as the link between the event engine and the policy script interpreter buys a great deal in terms of extensibility. Adding new functionality to Bro generally consists of adding a new protocol analyzer to the event engine and then writing new event handlers for the events generated by the analyzer. Neither the analyzer nor the event handlers tend to have much overlap with existing functionality, so for the most part we can avoid the subtle interactions between loosely coupled modules that can easily lead to maintenance headaches and buggy programs.

3 The Bro language

As discussed above, we express security policies in terms of scripts written in the specialized Bro language. In this section we give an overview of the language's features. The aim is to convey the flavor of the language, rather than describe it precisely.

Our goal of ``avoid simple mistakes'' (§ 1), while perhaps sounding trite, in fact heavily influenced the design of the Bro language. Because intrusion detection can form a cornerstone of the security measures available to a site, we very much want our policy scripts to behave as expected. From our own experience, a big step towards avoiding surprises is to use a strongly typed language that detects typing inconsistencies at compile-time, and that guarantees that all variable references at run-time will be to valid values. Furthermore, we have come to appreciate the benefits of domain-specific languages, that is, languages tailored for a particular task. Having cobbled together our first monitoring system out of tcpdump, awk, and shell scripts, we thirsted for ways to deal directly with hostnames, IP addresses, port numbers, and the like, rather than devising ASCII pseudo-equivalents. By making these sorts of entities first-class values in Bro, we both increase the ease of expression offered by the language and, due to strong typing, catch errors (such as comparing a port to an IP address) that might otherwise slip by.

3.1 Data types and constants

Atomic types. Bro supports several types familiar to users of traditional languages: bool for booleans, int for integers, count for non-negative integers (``unsigned'' in C), double for double-precision floating point, and string for a series of bytes. The first four of these (all but string) are termed arithmetic types, and mixing them in expressions promotes bool to count, count to int, and int to double.

Bro provides T and F as bool constants for true and false; a series of digits for count constants; and C-style constants for double and string.

Unlike in C, however, Bro strings are represented internally as a count and a vector of bytes, rather than a NULterminated series of bytes. This difference is important because NULs can easily be introduced into strings derived from network traffic, either by the nature of the application, inadvertently, or maliciously by an attacker attempting to subvert the monitor. An example of the latter is sending the following to an FTP server:

   USER nice\0USER root
where ``\0'' represents a NUL. Depending on how it is written, the FTP application receiving this text might well interpret it as two separate commands, ``USER nice'' followed by ``USER root''. But if the monitoring program uses NUL-terminated strings, then it will effectively see only ``USER nice'' and have no opportunity to detect the subversive action.

Similarly, it is important that when Bro logs such strings, or prints them as text to a file, that it expands embedded NULs into visible escape sequences to flag their appearance.

Bro also includes a number of non-traditional types, geared towards its specific problem domain. A value of type time reflects an absolute time, and interval a difference in time. Subtracting two time values yields an interval; adding or subtracting an interval to a time yields a time; adding two time values is an error. There are presently no time constants, but interval constants can be specified using a numeric (possibly floating-point) value followed by a unit of time, such as ``30 min'' for thirty minutes.

The port type corresponds to a TCP or UDP port number. TCP and UDP ports are distinct (internally, Bro distinguishes between the two, both of which are 16-bit quantities, by storing port values in a 32-bit integer and setting bit 17 for UDP ports). Thus, a variable of type port can hold either a TCP or a UDP port, but at any given time it is holding exactly one of these.

There are two forms of port constants. The first consists of an unsigned integer followed by either ``/tcp'' or ``/udp.'' So, for example, ``80/tcp'' corresponds to TCP port 80 (the HTTP protocol used by the World Wide Web). The second form of constant is specified using an identifier that matches one of the services known to the getservbyname library routine. (Probably these service names should instead be built directly into Bro, to avoid problems when porting Bro scripts between operating systems.) So, for example, ``telnet'' is a Bro constant equivalent to ``23/tcp.''

This second form of port constant, while highly convenient and readable, brings with it a subtle problem. Some names, such as ``domain,'' on many systems correspond to two different ports; in this example, to 53/tcp and 53/udp. Therefore, the type of ``domain'' is not a simple port value, but instead a list of port values. Accordingly, a constant like ``domain'' cannot be used in Bro expressions (such as ``dst_port == domain''), because it is ambiguous which value is intended. We return to this point shortly.

Values of type port may be compared for equality or ordering (for example, ``20/tcp > telnet'' yields true), but otherwise cannot be operated on.

Another networking type provided by Bro is addr, corresponding to an IP address. These are represented internally as unsigned, 32-bit integers, but in Bro scripts the only operations that can be performed on them are comparisons for equality or inequality (also, a built-in function provides masking, as discussed below). Constants of type addr have the familiar ``dotted quad'' format, A1.A2.A3.A4, where the Ai all lie between 0 and 255.

More interesting are hostname constants. There is no Bro type corresponding to Internet hostnames, because hostnames can correspond to multiple IP addresses, so one quickly runs into ambiguities if comparing one hostname with another. Bro does, however, support hostnames as constants. Any series of two or more identifiers delimited by dots forms a hostname constant, so, for example, ``lbl.gov'' and ``www.microsoft.com'' are both hostname constants (the latter, as of this writing, corresponds to 13 distinct IP addresses). The value of a hostname constant is a list of addr containing one or more elements. These lists (as with the lists associated with certain port constants, discussed above) cannot be used in Bro expressions; but they play a central role in initializing Bro table's and set's, discussed in § 3.3 below.

Aggregate types. Bro also supports a number of aggregate types. A record is a collection of elements of arbitrary type. For example, the predefined conn_id type, used to hold connection identifiers, is defined in the Bro run-time initialization file as:

   type conn_id: record {
       orig_h: addr;
       orig_p: port;
       resp_h: addr;
       resp_p: port;
};

The orig_h and resp h elements (or ``fields'') have type addr and hold the connection originator's and responder's IP addresses. Similarly, orig_p and resp_p hold the originator and responder ports. Record fields are accessed using the ``$'' operator.

For specifying security policies, a particularly useful Bro type is table. Bro tables have two components, a set of indices and a yield type. The indices may be of any atomic (non-aggregate) type, and/or any record types that, when (recursively) expanded into all of their elements, are comprised of only atomic types. (Thus, Bro tables provide a form of associative array.) So, for example,

   table[port] of string
can be indexed by a port value, yielding a string, and:
   table[conn_id] of ftp_session_info
is indexed by a conn_id record---or, equivalently, by an addr, a port, another addr, and another port---and yields an ftp_session_info record as a result.

Closely related to table types are set types. These are simply table types that do not yield a value. Their purpose is to maintain collections of tuples, expressed in terms of the set's indices. The examples in § 3.3 clarify how this is useful.

Another aggregate type supported is file. Support for files is presently crude: a script can open files for writing or appending, and can pass the resulting file variable to the print command to specify where it should write, but that is all. Also, these files are simple ASCII. In the future, we plan to extend files to support reading, ASCII parsing, and binary (typed) reading and writing.

We also note that a key type missing from Bro is that of pattern, for supporting regular expression matching against text. We plan to add patterns in the near future. Finally, above we alluded to the list type, which holds zero or more instances of a value. Currently, this type is not directly available to the Bro script writer, other than implicitly when using port or hostname constants. Since its present use is primarily internal to the script interpreter (when initializing variables, per § 3.3), we do not describe it further.

3.2 Operators

Bro provides a number of C-like operators (+, -, *, /, %, !, &&, ||, ?:, relationals like <=) with which we assume the reader is familiar, and will not detail here. Assignment is done using =, table and set indexing with [], and function invocation and event generation with (). Numeric variables can be incremented and decremented using ++ and --. Record fields are accessed using $, to avoid ambiguity with hostname constants. Assignment of aggregate values is shallow---the newly-assigned variable refers to the same aggregate value as the right-hand side of the assignment expression. This choice was made to facilitate performance; we have not yet been bitten by the semantics (which differ from C). We may in the future add a copy operator to construct ``deep'' copies.

From the perspective of C, the only novel operators are in and !in. These infix operators yield bool values depending on whether or not a given index is in a given table or set. For example, if sensitive_services is a set indexed by a single port, then

   23/tcp in sensitive_services
returns true if the set has an element corresponding to an index of TCP port 23, false if it does not have such an element. Similarly, if RPC_okay is a set (or table) indexed by a source address, a destination address, and an RPC service number (a count), then
   [src_addr, dst_addr, serv] in RPC_okay
yields true if the given ordered triple is present as an index into RPC_okay. The !in operator simply returns the boolean negation of the in operator.

Presently, indexing a table or set with a value that does not correspond to one of its elements leads to a run-time error, so such operations need to be preceded by in tests. We find this not entirely satisfying, and plan to add a mechanism for optionally specifying the action to take in such cases on a per-table basis.

Finally, Bro includes a number of predefined functions to perform operations not directly available in the language. Some of the more interesting: fmt provides sprintf-style formatting for use in printing or manipulating strings; edit returns a copy of a string that has been edited using the given editing characters (currently it only knows about single-character deletions); _ddr takes an addr and returns another addr corresponding to its top n bits; open and close manipulate files; network_time returns the timestamp of the most recently received packet; getenv provides access to environment variables; skip_further_processing marks a connection as not requiring any further analysis; set_record_packets instructs the event engine whether or not to record any of a connection's future packets (though SYN/FIN/RST are always recorded); and parse_ftp_port takes an FTP ``PORT'' command and returns a record with the corresponding addr and port.

3.3 Variables

Bro supports two levels of scoping: local to a function or event handler, and global to the entire Bro script. Experience has already shown that we would benefit by adding a third, intermediate level of scoping, perhaps as part of a ``module'' or ``object'' facility, or even as simple as C's static scoping. Local variables are declared using the keywork local, and the declarations must come inside the body of a function or event handler. There is no requirement to declare variables at the beginning of the function. The scope of the variable ranges from the point of declaration to the end of the body. Global variables are declared using the keyword global and the declarations must come outside of any function bodies. For either type of declaration, the keyword can be replaced instead by const, which indicates that the variable's value is constant and cannot be changed.

Syntactically, a variable declaration looks like:

   {class} {identifier} [':' {type}] ['=' {init}]
That is, a class (local or global scope, or the const qualifier), the name of the variable, an optional type, and an optional initialization value. One of the latter two must be specified. If both are, then naturally the type of the initialization much agree with the specified type. If only a type is given, then the variable is marked as not having a value yet; attempting to access its value before first setting it results in a run-time error.

If only an initializer is specified, then Bro infers the variable's type from the form of the initializer. This proves quite convenient, as does the ease with which complex tables and sets can be initialized. For example,

   const IRC = { 6666/tcp, 6667/tcp, 6668/tcp };
infers a type of set[port] for IRC, while:
   const ftp_serv = { ftp.lbl.gov, www.lbl.gov };
infers a type of set[addr] for ftp_serv, and initializes it to consist of the IP addresses for ftp.lbl.gov and www.lbl.gov, which, as noted above, may encompass more than two addresses. Bro infers compound indices by use of [] notation:
   const allowed_services = {
      [ftp.lbl.gov, ftp], [ftp.lbl.gov, smtp],
      [ftp.lbl.gov, auth], [ftp.lbl.gov, 20/tcp],
      [www.lbl.gov, ftp], [www.lbl.gov, smtp],
      [www.lbl.gov, auth], [www.lbl.gov, 20/tcp],
      [nntp.lbl.gov, nntp]
};
results in allowed_services having type set[addr,port]. Here again, the hostname constants may result in more than one IP address. Any time Bro encounters a list of values in an initialization, it replicates the corresponding index. Furthermore, one can explicitly introduce lists in initializers by enclosing a series of values (with compatible types) in []'s, so the above could be written:
   const allowed_services: set[addr, port] = {
      [ftp.lbl.gov, [ftp, smtp, auth, 20/tcp]],
      [www.lbl.gov, [ftp, smtp, auth, 20/tcp]],
      [nntp.lbl.gov, nntp]
   };

The only cost of such an initialization is that Bro's algorithm for inferring the variable's type from its initializer currently gets confused by these embedded lists, so the type now needs to be explicitly supplied, as shown.

In addition, any previously-defined global variable can be used in the initialization of a subsequent global variable. If the variable used in this fashion is a set, then its indices are expanded as if enclosed in their own list. So the above could be further simplified to:

   const allowed_services: set[addr, port] = {
      [ftp_serv, [ftp, smtp, auth, 20/tcp]],
      [nntp.lbl.gov, nntp]
};

Initializing table values looks very similar, with the difference that a table initializer includes a yield value, too. For example:

   global port_names = {
      [7/tcp] = "echo",
      [9/tcp] = "discard",
      [11/tcp] = "systat",
   ...
   };
which infers a type of table[port] of string.

We find that these forms of initialization shorthand are much more than syntactic sugar. Because they allow us to define large tables in a succinct fashion, by referring to previously-defined objects and by concisely capturing forms of replication in the table, we can specify intricate policy relationships in a fashion that's both easy to write and easy to verify. Certainly, we would prefer the final definition of allowed_services above to any of its predecessors, in terms of knowing exactly what the set consists of.

Along with clarity and conciseness, another important advantage of Bro's emphasis on tables and sets is speed. Consider the common problem of attempting to determine whether access is allowed to service S of host H. Rather than using (conceptually):

   if ( H == ftp.lbl.gov || H == www.lbl.gov )
      if ( S == ftp || S == smtp || ... )
   else if ( H == nntp.lbl.gov )
      if ( S == nntp )
   ...
we can simply use:
   if ( [S, H] in allowed_services )
      ... it's okay ...

The in operation translates into a single hash table lookup, avoiding the cascaded if's and clearly showing the intent of the test.

3.4 Statements

Bro currently supports only a modest group of statements, which we have so far found sufficient. Along with C-style if and return and expression evaluation, other statements are: print a list of expressions to a file (stdout by default); log a list of expressions; add an element to a set; delete an element from a set or a table; and event, which generates a new event.

In particular, the language does not support looping using a for-style construct. We are wary of loops in event handlers because they can lead to arbitrarily large processing delays, which in turn could lead to packet filter drops. We wanted to see whether we could still adequately express security policies in Bro without resorting to loops; if so, then we have some confidence that every event is handled quickly. So far, this experiment has been successful. Looping is still possible via recursion (either functions calling themselves, or event handlers generating their own events), but we have not found a need to resort to it.

Like in C, we can group sets of statements into blocks by enclosing them within {}'s. Function definitions look like:

   function endpoint_id(h: addr, p: port): string
      {
      if ( p in port_names )
         return fmt("%s/%s", h, port_names[p]);
      else
         return fmt("%s/%d", h, p);
      }

Event handler definitions look the same except that function is replaced by event and they cannot specify a return type. See Appendix A for an example. Functions are invoked the usual way, as expressions specified by the function's name followed by its arguments enclosed within parentheses. Events are generated in a similar fashion, except using the keyword event before the handler's name and argument list. Since events do not return values (they can't, since they are processed asynchronously), event generation is a statement in Bro and not an expression.

Bro also allows ``global'' statements that are not part of a function or event handler definition. These are executed after parsing the full script, and can of course invoke functions or generate events. The event engine also generates events during different phases of its operation: bro_init when it is about to begin operation, bro_done when it is about to terminate, and bro_signal when it receives a Unix signal.

One difference between defining functions and defining event handlers is that Bro allows multiple, different definitions for a given event handler. Whenever an event is generated, each instance of a handler is invoked in turn (in the order they appear in the script). So, for example, different (conceptual) modules can each define bro_init handlers to take care of their initialization. We find this considerably simplifies the task of creating modular sets of event handlers, but we anticipate requiring greater control in the future over the exact order in which Bro invokes multiple handlers.

4 Implementation issues

We implemented the Bro event engine and script interpreter in C++, currently about 22,000 lines. In this section we discuss some of the significant implementation decisions and tradeoffs. We defer to § 5 discussion of how Bro defends against attacks on the monitoring system, and postpone application-specific issues until § 6, as that discussion benefits from notions developed in § 5.

Single-threaded design. Since event handling lies at the heart of the system, it is natural to consider a multi-threaded design, with one thread per active event handler. We have so far resisted this approach, because of concerns that it could lead to subtle race conditions in Bro scripts.

An important consequence of a single-threaded design is that the system must be careful before initiating any activity that may potentially block waiting for a resource, leading to packet filter drops as the engine fails to consume incoming traffic. A particular concern is performing Domain Name System (DNS) lookups, which can take many seconds to complete or time out. Currently, Bro only performs such lookups when parsing its input file, but we want in the future to be able to make address and hostname translations on the fly, both to generate clearer messages, and to detect certain types of attacks. Consequently, Bro includes customized non-blocking DNS routines that perform DNS lookups asynchronously.

3 Some systems, such as DIDS and CSM, orchestrate multiple monitors watching multiple network links, in order to track users as they move from machine to machine [MHL94, WFP96]. These differ from what we envision for Bro in that they require each host in the network to run a monitor.
We may yet adopt a multi-threaded design. A more likely possibility is evolving Bro towards a distributed design, in which loosely-coupled, multiple Bro's on separate processors monitor the same network link. Each Bro would watch a different type of traffic (e.g., HTTP or NFS) and communicate only at a high level, to convey current threat information. 3

Managing timers. Bro uses numerous timers internally for operations such as timing out a connection establishment attempt. It sometimes has thousands of timers pending at a given moment. Consequently, it is important that timers be very lightweight: quick to set and to expire. Our initial implementation used a single priority heap, which we found attractive since insert and delete operations both require only O(log(N)) time if the heap contains N elements. However, we found that when the heap grows quite large--- such as during a hostile port scan that creates hundreds of new connections each second---then this overhead becomes significant. Consequently, we perceived a need to redesign timers to bring the overhead closer to O(1). To achieve this, Bro is now in the process of being converted to using ``calendar queues'' instead [Br88].

A related issue with managing timers concerns exactly when to expire timers. Bro derives its notion of time from the timestamps provided by libpcap with each packet it delivers. Whenever this clock advances to a time later than the first element on the timer queue, Bro begins removing timers from the queue and processing their expiration, continuing until the queue is empty or its first element has a timestamp later than the current time. This approach is flawed, however, because in some situations---such as port scans---the event engine may find it needs to expire hundreds of timers that have suddenly become due, because the clock has advanced by a large amount due to a lull in incoming traffic. Clearly, what we should do instead is (again) sacrifice exactness as to when timers are expired, and (1) expire at most k for any single advance of the clock, and (2) also expire timers when there has been a processing lull (as this is precisely the time when we have excess CPU cycles available), without waiting for a packet to finally arrive and end the lull. These changes are also part of our current revisions to Bro's timer management.

Interpreting vs. compiling. Presently, Bro interprets the policy script: that is, it parses the script into a tree of C++ objects that reflect an abstract syntax tree (AST), and then executes portions of the tree as needed by invoking a virtual evaluation method at the root of a given subtree. This method in turn recursively invokes evaluation methods on its children.

Such a design has the virtues of simplicity and ease of debugging, but comes at the cost of considerable overhead. From its inception, we intended Bro to readily admit compilation to a low-level virtual machine. Execution profiles of the current implementation indicate that the interpretive overhead is indeed significant, so we anticipate developing a compiler and optimizer. (The current interpreter does some simple constant folding and peephole optimization when building the AST, but no more.)

Using an interpreter also inadvertantly introduced an implementation problem. By structuring the interpreter such that it recursively invokes virtual evaluation methods on the AST, we wind up intricately tying the Bro evaluation stack with the C++ run-time stack. Consequently, we cannot easily bundle up a Bro function's execution state into a closure to execute at some later point in time. Yet we would like to have this functionality, so Bro scripts have timers available to them; the semantics of these timers are to execute a block of statements when a timer expires, including access to the local variables of the function or event handler scheduling the timer. Therefore, adding timers to Bro will require at a minimum implementing an execution stack for Bro scripts separate from that of the interpreter.

Checkpointing. We run Bro continuously to monitor our DMZ network. However, we need to periodically checkpoint its operation, both to reclaim memory tied up in remembering state for long-dormant connections (because we don't yet have timers in the scripting language; see above), and to collect a snapshot for archiving and off-line analysis (discussed below).

Checkpointing is currently a three-stage process. First, we run a new instance of Bro that parses the policy script and resolves all of the DNS names in it. Because we have nonblocking DNS routines, Bro can perform a large number of lookups in parallel, as well as timing out lookup attempts whenever it chooses. For each lookup, it compares the results with any it may have previously cached and generates corresponding events (mapping valid, mapping unverified if it had to time out the lookup, or mapping changed). It then updates the DNS cache file and exits.

In the second stage, we run another instance of Bro, this time specifying that it should only consult the DNS cache and not perform lookups. Because it works directly out of the cache, it starts very quickly. After waiting a short interval, we then send a signal to the long-running Bro telling it to terminate. When it exits, the checkpointing is complete.

We find the checkpointing deficient in two ways. First, it would be simpler to coordinate a checkpoint if a new instance of Bro could directly signal an old instance to announce that it is ready to take over monitoring. Second, and more important, currently no state survives the checkpointing. In particular, if the older Bro has identified some suspect activity and is watching it particularly closely (say, by recording all of its packets), this information is lost when the new Bro takes over. Clearly, we need to fix this.

Off-line analysis. As mentioned above, one reason for checkpointing the system is to facilitate off-line analysis. The first step of this analysis is to copy the libpcap save file and any files generated by the policy script to an analysis machine. Our policy script generates six such files: a summary of all connection activity, including starting time, duration, size in each direction, protocol, endpoints (IP addresses), connection state, and any additional information (such as username, when identified); a summary of the network interface and packet filter statistics; a list of all generated log messages; summaries of Finger and FTP commands; and a list of all unusual networking events.

Regarding this last, the event engine identifies more than 50 different types of unusual behavior, such as incorrect connection initiations and terminations, checksum errors, packet length mismatches, and protocol violations. For each, it generates a conn_weird or net_weird event, identifying the behavior with a predefined string. Our policy script uses a table[string] of count to map these strings to three different values, ``ignore,'' ``file,'' and ``log,'' meaning ignore the behavior entirely, record it to the anomaly file, or log it (real-time notification) and record it to the file. Some anomalies prove surprisingly common, and on a typical day the anomaly file contains on the order of 1,000 entries, even though our script suppresses duplicate messages.

All of the copied files thus form an archival record of the day's traffic. We keep these files indefinitely. They can prove invaluable when we discover a break-in that first occurred weeks or months in the past. In addition, once we have identified an attacking site, we can run it through the archive to find any other hosts it may have attacked that the monitoring failed to detect (quite common, for example, when the attacker has obtained a list of passwords using a passwordsniffer).

In addition, after each checkpoint the analysis machine further studies the traffic logs, looking for possible attacks, the most significant being port scans and address sweeps. We intend to eventually move this analysis into the real-time portion of the system; for now, it waits upon adding timers to Bro so we can time out connection state and avoiding consuming huge amounts of memory trying to remember every distinct port and address to which each host has connected.

Finally, the off-line analysis generates a traffic summary highlighting the busiest hosts and giving the volume (number of connections and bytes transferred) due to different applications. As of this writing, on a typical day our site engages in about 600,000 connections transferring 20 GB of data. The great majority (75--80%) of the connections are HTTP; the highest byte volume comes from HTTP, FTP data, NNTP (network news), and, sometimes, X11, with the ordering among them variable.

5 Attacks on the monitor

In this section we discuss the difficult problem of defending the monitor against attacks upon itself. We defer discussion of Bro's application-specific processing until after this section, because elements of that processing reflect attempts to defeat the types of attacks we describe here.

As discussed in § 1, we assume that such attackers have full access to the monitor's algorithms and source code; but also that they have control over only one of the two connection endpoints. In addition, we assume that the cracker does not have access to the Bro policy script, which each site will have customized, and should keep well protected.

While previous work has addressed the general problem of testing intrusion detection systems [PZCMO96], this work has focussed on correctness of the system in terms of whether it does indeed recognize the attacks claimed. To our knowledge, the literature does not contain any discussion of attacks specifically aimed at subverting a network intrusion detection system, other than the discussion in [PZCMO96] of the general problem of the monitor failing to keep up due to high load.

For our purposes, we classify network monitor attacks into three categories: overload, crash, and subterfuge. The remainder of this section defines each category and briefly discusses the degree to which Bro meets that class of threat.

5.1 Overload attacks

We term an attack as an overload if the goal of the attack is to overburden the monitor to the point where it fails to keep up with the data stream it must process. The attack has two phases, the first in which the attacker drives the monitor to the point of overload, and the second in which the attacker attempts a network intrusion. The monitor would ordinarily detect this second phase, but fails to do so---or at least fails to do so with some non-negligible probability---because it is no longer tracking all of the data necessary to detect every current threat.

It is this last consideration, that the attack might still be detected because the monitor was not sufficiently overwhelmed, that complicates the use of overload attacks; so, in turn, this provides a defensive strategy, namely to leave some doubt as to the exact power and typical load of the monitor.

Another defensive strategy is for the monitor to shed load when it becomes unduly stressed (see [CT94] for a discussion of shedding load in a different context). For example, the monitor might decide to cease to capture HTTP packets, as these form a high proportion of the traffic. Of course, if the attacker knows the form of load-shedding used by the monitor, then they can exploit its consequent blindness and launch a now-undetected attack.

For Bro in particular, to develop an overload attack one might begin by inspecting Figure 1 to see how to increase the data flow. One step is to send packets that match the packet filter; another, packet streams that in turn generate events; and a third, events that lead to logging or recording to disk.

The first of these is particularly easy, because the libpcap filter used by Bro is fixed. One defense against it is to use a hardware platform with sufficient processing power to keep up with a high volume of filtered traffic, and it was this consideration that lead to our elaborating the goal of ``no packet filter drops'' in § 1. The second level of attack, causing the engine to generate a large volume of events, is a bit more difficult to achieve because Bro events are designed to be lightweight. It is only the events for which the policy specifies quite a bit of work that provide much leverage for an attack at this level, and we do not assume that the attacker has access to the policy scripts. This same consideration makes an attack at the final level---elevating the logging or recording rate---difficult, because the attacker does not necessarily know which events lead to logging.

Finally, to help defend against overload attacks, the event engine generates a net_stats_update event every T seconds. The value of this event gives the number of packets received, the number dropped by the packet filter due to insufficient buffer, and the number reported dropped by the network interface because the kernel failed to consume them quickly enough. Thus, Bro scripts at least have some basic information available to them to determine whether the monitor is becoming overloaded.

5.2 Crash attacks

Crash attacks aim to knock the monitor completely out of action by causing it to either fault or run out of resources. As with an overload attack, the crash attack has two phases, the first during which the attacker crashes the monitor, and the second during which they then proceed with an intrusion.

Crash attacks can be much more subtle than overload attacks, though. By careful source code analysis, it may be possible to find a series of packets, or even just one, that, when received by the monitor, causes it to fault due to a coding error. The effect can be immediate and violent.

We can perhaps defend against this form of crash attack by careful coding and testing. Another type of crash attack, harder to defend against, is one that causes the monitor to exhaust its available resources: dynamic memory or disk space. Even if the monitor has no memory leaks, it still needs to maintain state for any active traffic. Therefore, one attack is to create traffic that consumes a large amount of state. When Bro supports timers for policy scripts, this attack will become more difficult, because it will be harder to predict the necessary level of bogus traffic. Attacks on disk space are likewise difficult, unless one knows the available disk capacity. In addition, the monitor might continue to run even with no disk space available, sacrificing an archival record but still producing real-time notifications, so a disk space attack might fail to mask a follow-on attack.

Bro provides two features to aid with defending against crash attacks. First, the event engine maintains a ``watchdog'' timer that expires every T seconds. (This timer is not a Bro internal timer, but rather a Unix ``alarm.'') Upon expiration, the watchdog handler checks to see whether the event engine has failed to finish processing the packet (and subsequent events) it was working on T seconds before. If so, then the watchdog presumes that the engine is in some sort of processing jam (perhaps due to a coding error, perhaps due to excessive time spent managing overburdened resources), and terminates the monitor process (first logging this fact, of course, and generating a core image for later analysis).

This feature might not seem particularly useful, except for the fact that it is coupled with a second feature: the script that runs Bro also detects if it ever unduly exits, and, if so, logs this fact and then executes a copy of tcpdump that records the same traffic that the monitor would have captured. Thus, crash attacks are (1) logged, and (2) do not allow a subsequent intrusion attempt to go unrecorded, only to evade realtime detection. However, there is a window of opportunity between the time when the Bro monitor crashes and when tcpdump runs. If an attacker can predict exactly when this window occurs, then they can still evade detection. But determining the window is difficult without knowledge of the exact configuration of the monitoring system.

5.3 Subterfuge attacks

In a subterfuge attack, an attacker attempts to mislead the monitor as to the meaning of the traffic it analyzes. These attacks are particularly difficult to defend against, because (1) unlike overload and crash attacks, if successful they do not leave any traces that they have occurred, and (2) the attacks can be quite subtle. Access to the monitor's source code particularly aids with devising subterfuge attacks.

We briefly discussed an example of a subterfuge attack in § 3.1, in which the attacker sends text with an embedded NUL in the hope that the monitor will miss the text after the NUL. Another form of subterfuge attack is using fragmented IP datagrams in an attempt to elude monitors that fail to reassemble IP fragments (an attack well-known to the firewall community). The key principle is to find a traffic pattern interpreted by the monitor in a different fashion than by the receiving endpoint.

To thwart subterfuge attacks, as we developed Bro we attempted at each stage to analyze the explicit and implicit assumptions made by the system, and how, by violating them, an attack might successfully elude detection. This can be a difficult process, though, and we make no claims to have found them all! In the remainder of this section, we focus on subterfuge attacks on the integrity of the byte stream monitored for a TCP connection. Then, in § 6.4, we look at subterfuge attacks aimed at hiding keywords in interactive text.

To analyze a TCP connection at the application level requires extracting the payload data from each TCP packet and reassembling it into its proper sequence. We now consider a spectrum of approaches to this problem, ranging from simplest and easiest to defeat, to increasingly resilient.

Scanning the data in individual packets without remembering any connection state, while easiest, obviously suffers from major problems: any time the text of interest happens to straddle the boundary between the end of one packet and the beginning of the next, the text will go unobserved. Such a split can happen simply by accident, and certainly by malicious intent.

Some systems address this problem by remembering previously-seen text up to a certain degree (perhaps from the beginning of the current line). This approach fails as soon as a sequence ``hole'' appears: that is, any time a packet is missing---due to loss or out-of-order delivery---then the resulting discontinuity in the data stream again can mask the presence of key text only partially present.

The next step is to fully reassemble the TCP data stream, based on the sequence numbers associated with each packet. Doing so requires maintaining a list of contiguous data blocks received so far, and fitting the data from new packets into the blocks, merging now-adjacent blocks when possible. At any given moment, one can then scan the text from the beginning of the connection to the highest in-sequence byte received.

Unless we are careful, even keeping track of noncontiguous data blocks does not suffice to prevent a TCP subterfuge attack. The key observation is that an attacker can manipulate the packets their TCP sends so that the monitor sees a particular packet, but the endpoint does not. One way of doing so is to transmit the packet with an invalid TCP checksum. (This particular attack can be dealt with by checksumming every packet, and discarding those that fail; a monitor needs to do this anyway so that it correctly tracks the endpoint's state in the presence of honest data corruption errors, which are not particularly rare [Pa97].) Another way is to launch the packet with an IP ``Time To Live'' (TTL) field sufficient to carry the packet past the monitoring point, but insufficient to carry it all the way to the endpoint. (If the site has a complex topology, it may be difficult for the monitor to detect this attack.) A third way becomes possible if the final path to the attacked endpoint happens to have a smaller Maximum Transmission Unit (MTU) than the Internet path from the attacker's host to the monitoring point. The attacker then sends a packet with a size exceeding this MTU and with the IP ``Don't Fragment'' header bit set. This packet will then transit past the monitoring point, but be discarded by the router at the point where the MTU narrows.

By manipulating packets in this fashion, an attacker can send innocuous text for the benefit of the monitor, such as ``USER nice'', and then retransmit (using the same sequence numbers) attack text (``USER root''), this time allowing the packets to traverse all the way to the endpoint. If the monitor simply discards retransmitted data without inspecting it, then it will mistakenly believe that the endpoint received the innocuous text, and fail to detect the attack.

A defense against this attack is that when we observe a retransmitted packet (one with data that wholly or partially overlaps previously-seen data), we compare it with any data it overlaps, and sound an alarm (or, for Bro, generate an event) if they disagree. A properly-functioning TCP will always retransmit the same data as originally sent, so any disagreement is either due to a broken TCP (unfortunately, we have observed some of these), undetected data corruption (i.e., corruption the checksum fails to catch), or an attack.

We have argued that the monitor must retain a record of previously transmitted data, both in-sequence and out-ofsequence. The question now arises as to how long the monitor must keep this data around. If it keeps it for the lifetime of the connection, then it may require prodigious amounts of memory any time it happens upon a particularly large connection; these are not infrequent [Pa94]. We instead would like to discard data blocks as soon as possible, to reclaim the associated memory. Clearly, we cannot safely discard blocks above a sequencing hole, as we then lose the opportunity to scan the text that crosses from the sequence hole into the block. But we would like to determine when it is safe to discard in-sequence data.

Here we can make use of our assumption that the attacker controls only one of the connection endpoints. Suppose the stream of interest flows from host A to host B. If the attacker controls B, then they are unable to manipulate the data packets in a subterfuge attack, so we can safely discard the data once it is in-sequence and we have had an opportunity to analyze it. On the other hand, if they control A, then, from our assumption, any traffic we see from B reflects the correct functioning of its TCP (this assumes that we use antispoofing filters so that the attacker cannot forge bogus traffic purportedly coming from B). In particular, we can trust that if we see an acknowledgement from B for sequence number n, then indeed B has received all data in sequence up to n. At this point, B's TCP will deliver, or has already delivered, this data to the application running on B. In particular, B's TCP cannot accept any retransmitted data below sequence n, as it has already indicated it has no more interest in such data. Therefore, when the monitor sees an acknowledgement for n, it can safely release any memory associated with data up to sequence n.

6 Application­specific processing

We finish our overview of Bro with a discussion of the additional processing it does for the four applications it currently knows about: Finger, FTP, Portmapper, and Telnet. Admittedly these are just a small portion of the different Internet applications used in attacks, and Bro's effectiveness will benefit greatly as more are added. Fortunately, we have in general found that the system meets our goal of extensibility (§ 1), and adding new applications to Bro is---other than the sometimes major headache of robustly interpreting the application protocol itself---quite straight-forward, a matter of deriving a C++ class to analyze each connection's traffic, and devising a set of events corresponding to significant elements of the application.

6.1 Finger

The first of the applications is the Finger ``User Information'' service [Zi91]. Structurally, Finger is very simple: the connection originator sends a single line, terminated by a carriage-return line-feed, specifying the user for which they request information. An optional flag requests ``full'' (verbose) output. The responder returns whatever information it deems appropriate in multiple lines of text, after which it closes the connection.

Bro generates a finger_request event whenever it monitors a complete Finger request. A handler for this event looks like:

   event finger_request(c: connection,
                        user: string, full: bool)

Our site's policy for Finger requests includes testing for possible buffer-overflow attacks and checking the user against a list of sensitive user ID's, such as privileged accounts. See Appendix A for a discussion of how the Finger analysis is integrated into Bro.

Bro currently does not generate an analogous finger_reply event. Two reasons for this are (1) we view the primary threat of Finger to come from the originator and not the responder, so adding finger_reply has had a lower priority, and (2) manipulating multi-line strings in Bro is clumsy at present, because Bro does not have an iteration operator for easily moving through a table[count] of string.

A final note: if the event engine finds that the policy script does not define a finger_request handler, then it does not bother creating Finger-specific analyzers for new Finger connections. In general, the event engine tries to determine as early as possible whether the user has defined a particular handler, and, if not, avoids undertaking the work associated with generating the corresponding event.

6.2 FTP

The File Transfer Protocol [PR85] is much more complex than the Finger protocol; it also, however, is highly structured and easy to parse, so interpreting an FTP dialog is straight-forward.

For FTP requests, Bro parses each line sent by the connection originator into a command (first word) and an argument (the remainder), splitting the two at the first instance of whitespace it finds, and converting the command to uppercase (to circumvent problems such as a policy script testing for ``store file'' commands as STOR or stor, and an attacker instead sending stOR, which the remote FTP server will happily accept). It then generates an ftp_request event with these and the corresponding connection as arguments.

FTP replies begin with a status code (a number), followed by any accompanying text. Replies also can indicate whether they continue to another line. Accordingly, for each line of reply the event engine generates an ftp_reply with the code, the text, a flag indicating continuation, and the corresponding connection as arguments.

As far as the event engine is concerned, that's it---100 lines of straight-forward C++. What is interesting about FTP is that all the remaining work can be done in Bro (about 300 lines for our site). The ftp_request handler keeps track of distinct FTP sessions, pulls out usernames to test against a list of sensitive ID's (and to annotate the connection's general summary), and, for any FTP request that manipulates a file, checks for access to sensitive files. Some of these checks depend on context; for example, a guest (or ``anonymous'') user should not attempt to manipulate userconfiguration files, while for other users doing so is fine.

A final analysis step for ftp_request events is to parse any PORT request to extract the hostname and TCP port associated with an upcoming transfer. (The FTP protocol uses multiple TCP connections, one for the control information such as user requests, and others, dynamically created, for each data transfer.) This is an important step, because it enables the script to tell which subsequent connections belong to this FTP session and which do not. A site's policy might allow FTP access to particular servers, but any other access to those servers merits an alarm; but without parsing the PORT request, it can be impossible to distinguish a legitimate FTP data transfer connection from an illicit, non-FTP connection. Consequently, the script keeps track of pending data transfer connections, and when it encounters them, marks them as ftp-data applications, even if they do not use the well-known port associated with such transfers (the standard does not require them to do so).

We also note that, in addition to correctly identifying FTP-related traffic, parsing PORT requests makes it possible to detect ``FTP bounce'' attacks. In these attacks, a malicious FTP client instructs an FTP server to open a data transfer connection not back to it, but to a third, victim site. The client can thus manipulate the server into uploading data to an arbitrary service on the victim site, or to effectively portscan the victim site (which the client does by using multiple bogus PORT requests and observing the completion status of subsequent data-transfer requests). Our script flags PORT requests that attempt any redirection of the data transfer connection. Interestingly, we added this check mostly because it was easy to do so; months later, we monitored the first of several subsequent FTP bounce attacks.

For ftp_reply events, most of the work is simply formatting a succinct one-line summary of the request and its result for recording in the FTP activity log. In addition, an FTP PASV request has a structure similar to a PORT request, except that the FTP server instead of the client determines the specifics of the subsequent data transfer connection. Consequently our script subjects PASV replies to the same analysis as PORT requests. Finally, there is nothing to prevent a different remote host from connecting to the data transfer port offered by a server via a PASV reply. It is hard to see why this might actually occur, but putting in a test for it is simple (unfortunately, there are some false alarms due to multi-homed clients; we use heuristics to reduce these); and, indeed, several months after adding it, it triggered, due to an attacker using 3-way FTP as (evidently) a way to disguise their trail.

6.3 Portmapper

Many services based on Remote Procedure Call (RPC; defined in [Sr95a]) do not listen for requests on a ``well-known'' port, but rather pick an arbitrary port when initialized. They then register this port with a Portmapper service running on the same machine. Only the Portmapper needs to run on a well-known port; when clients want access to the service, they first contact the Portmapper, and it tells them which port they should then contact in order to reach the service. This second port may be for TCP or UDP access (depending on which the client requests from the Portmapper).

Thus, by monitoring Portmapper traffic, we can detect any attempted access to a number of sensitive RPC services, such as NFS and YP, except in cases where the attacker learns the port for those services some other way (e.g., port-scanning).

The Portmapper service is itself built on top of RPC, which in turn uses the XDR External Data Representation Standard [Sr95b]. Furthermore, one can use RPC on top of either TCP or UDP, and typically the Portmapper listens on both a well-known TCP port and a well-known UDP port (both are port 111). Consequently, adding Portmapper analysis to Bro required adding a generic RPC analyzer, TCPand UDP-specific analyzers to unwrap the different ways in which RPCs are embedded in TCP and UDP packets, an XDR analyzer, and a Portmapper-specific analyzer.

This last generates six pairs of events, one for each request and reply for the six actions the Portmapper supports: a null call; add a binding between a service and a port; remove a binding; look up a binding; dump the entire table of bindings; and both look up a service and call it directly without requiring a second connection. (This last is a monitoring headache because it means any RPC service can potentially be accessed directly through a Portmapper connection.)

Our policy script for Portmapper traffic again is fairly large, more than 200 lines. Most of this concerns what Portmapper requests we allow between which pairs of hosts, particularly for NFS access.

6.4 Telnet

The final application currently built into Bro is Telnet, a service for remote interactive access [PR83a]. There are several significant difficulties with monitoring Telnet traffic. The first is that, unlike FTP, Telnet traffic is virtually unstructured. There are no nice ``USER xyz'' directives that make it trivial to identify the account associated with the activity; instead, one must employ a series of heuristics and hope for the best. This problem makes Telnet particularly susceptible to subterfuge attacks, since if the heuristics have holes, an attacker can slip through them undetected.

Our present goal is to determine Telnet usernames in a robust fashion, which we discuss in the remainder of this section. Scanning Telnet sessions for strings reflecting questionable activity is of course also highly interesting, but must wait for us to first add regular expression matching to Bro.

Recognizing the authentication dialog. The first facet of analyzing Telnet activity is to accurately track the initial authentication dialog and extract from it the usernames associated with both login failures and successes. Initially we attempted to build a state machine that would track the various authentication steps: waiting for the username, scanning the login prompt (this comes after the username, since the processing is line-oriented, and the full, newline-terminated prompt line does not appear until after the username has been entered), waiting for the password, scanning the password prompt, and then looking for an indication that the password was accepted or rejected (in which case the process repeats). This approach, though, founders on the great variety of authentication dialogs used by different operating systems, some of which sometimes do not prompt for passwords, or re-prompt for passwords rather than login names after a password failure, or utilize two steps of password authentication, or extract usernames from environment variables, and so on. We now are working on a simpler approach, based on associating particular strings (such as ``Password:'') with particular information, and not attempting to track the authentication states explicitly. It appears to work better, and its workings are certainly easier to follow.

The Telnet analyzer generates telnet_logged_in upon determining that a user has successfully authenticated, telnet_failure when a user has failed to authenticate, authentication_skipped if it recognizes the authentication dialog as one specified by the policy script as not requiring further analysis, and telnet_confused if the analyzer becomes confused regarding the authentication dialog. (This last could, for example, trigger full-packet recording of the subsequent session, for later manual analysis.)

Type-ahead. A basic difficulty that complicates the analysis is type-ahead. We cannot rely on the most-recently entered string as corresponding to the current prompt line. Instead, we keep track of user input lines separately, and consume them as we observe different prompts. For example, if the analyzer scans ``Password:'', then it associates with the prompt the first unread line in the user type-ahead buffer, and consumes that line. The hazard of this approach is if the Telnet server ever flushes the type-ahead buffer (due to part of its authentication dialog, or upon an explicit signal from the user), then if the monitor misses this fact it will become out of sync. This opens the monitor to a subterfuge attack, in which an attacker passes off an innocuous string as a username, and the policy script in turn fails to recognize that the attacker in fact has authenticated as a privileged user. One fix to this problem---reflecting a strategy we adopt for the more general ``keystroke editing'' problem discussed below---is to test both usernames and passwords against any list of sensitive usernames.

Unless we are careful, type-ahead also opens the door to another subterfuge attack. For example, an attacker can type-ahead the string ``Password:'', which, when echoed by the Telnet server, would be interpreted by the analyzer as corresponding to a password prompt, when in fact the dialog is in a different state. The analyzer defends against these attacks by checking each typed-ahead string against the different dialog strings it knows about, generating possible_telnet_ploy upon a match.

Keystroke editing. Usernames can also become disguised due to use of keystroke editing. For example, we would like to recognize that ``rb<DEL>oot'' does indeed correspond to a username of root, assuming that <DEL> is the singlecharacter deletion operator. We find this assumption, however, problematic, since some systems use <DEL> and others use <BS>. We address this problem by applying both forms of editing to usernames, yielding possibly three different strings, each of which the script then assesses in turn. So, for example, the string ``rob<DEL>;<BS><BS>ot'' is tested both directly, as ``ro<BS><BS>ot'', and as ``root''.

Editing is not limited to deleting individual characters, however. Some systems support deleting entire words or lines; others allow access to previously-typed lines using an escape sequence. Word and line deletion do not allow an attacker to hide their username, if tests for sensitive usernames check for any embedded occurrence of the username within the input text. ``History'' access to previous text is more problematic; presently, the analyzer recognizes the operating system that supports this (VMS) and, for it only, expands the escape sequence into the text of the previous line.

Telnet options. The Telnet protocol supports a rich, complex mechanism for exchanging options between the client and server [PR83b] (there are more than 50 RFCs discussing different Telnet options). Unhappily, we cannot ignore the possible presence of these options in our analysis, because an attacker can embed one in the middle of text they transmit in order to disguise their intent---for example, ``ro<option>ot''. The Telnet server will dutifully strip out the option before passing along the remaining text to the authentication system. We must do the same. On the other hand, parsing options also yields some benefits: we can detect connections that successfully negotiate to encrypt the data session, and skip subsequent analysis (rather than generating telnet_confused events), as well as analyzing options used for authentication (for example, Kerberos) and to transmit the user's environment variables (some systems use $USER as the default username during subsequent authentication).

7 Status, performance, and future directions

Bro has operated continuously since April 1996 as an integral part of our site's security system. It initially included only general TCP/IP analysis; as time permitted, we added the additional modules discussed in § 6, and we plan to add many more.

Presently, the implementation is about 22,000 lines of C++ and another 1,900 lines of Bro (about 1,650 lines of which are ``boilerplate'' not specific to our site). It runs under Digital Unix, FreeBSD, IRIX, SunOS, and Solaris operating systems. It generates about 40 MB of connection summaries each day, and an average of 20 real-time notifications, though this figure varies greatly. While most of the notifications are innocuous (and if we were not also developers of the system, we would suppress these), we not infrequently also detect break-in attempts. Operation of the system has resulted so far in 4,000 email messages, 85 incident reports filed with CIAC and CERT, a number of accounts deactivated by other sites, and a couple incidents involving law enforcement.

The system generally operates without incurring any packet drops. The FDDI ring it runs on is moderately utilized: a recent trace of a 2-3PM busy hour reflects a traffic level of 8,800 packets/sec (25 Mbps) sustained for the full hour, with peaks of 15,000 packets/sec. However, the packet filter discards a great deal of this, both due to filtering primarily on SYN, FIN, or RST control bits, and because only about 20% of the traffic belongs to networks that we routinely monitor (the link is shared with a large neighbor institution). During a busy hour, the monitor may receive 300,000 packets matching the filter, with peaks of 200/sec.

In order to make a preliminary assessment of the system under stress, we ran it for a thirty-minute period without the ``interesting networks'' filter, resulting in a much higher fraction of traffic accepted by the packet filter. During this period, the filter accepted an average of 640 packets/sec, with peaks over 800/sec. However, the filter also reported 364 dropped packets. (We note that the hardware platform used is no longer state-of-the-art.)

In addition to developing more application analysis modules, we see a number of avenues for future work. As discussed above, compiling Bro scripts and devising mechanisms to distribute monitoring across multiple CPUs have high priority. We are also very interested in extending BPF to better support monitoring, such as adding lookup tables and variable-length snapshots. Another interesting direction is to add some ``teeth'' to the monitoring in the form of actively terminating misbehaving connections by sending RST packets to their endpoints, or communicating with intermediary routers. This form of ``reactive firewall'' might fit particularly well to environments like ours that need to strike a balance between security and openness.

Finally, Bro is publicly available in source-code form (see http://www-nrg.ee.lbl.gov/bro-info.html for release information). We hope that it will both benefit the community and in turn benefit from community efforts to enhance it.

8 Acknowledgements

We gratefully acknowledge Digital Equipment Corporation's Western Research Laboratory for contributing the Alpha system that made developing and operating Bro at high speeds possible. I would particularly like to thank Jeff Mogul, who was instrumental in arranging this through WRL's External Research Program.

Many thanks, too, to Craig Leres. Bro has benefited greatly from many discussions with him. Craig also wrote the calendar queue and non-blocking DNS routines discussed in § 4.

My appreciation to Scott Denton and John Antonishek for alpha-testing Bro and contributing portability fixes and other enhancements.

Finally, this work would not have been possible without the support and enthusiasm of Mark Rosenberg, Van Jacobson, Stu Loken and Dave Stevens---much appreciated!

A Example: tracking Finger traffic

In this appendix we give an overview of how the different elements of Bro come together for monitoring Finger traffic. For the event engine, we have a C++ class FingerConn, derived from the general-purpose TCP_Connection class. When Bro encounters a new connection with service port 79, it instantiates a corresponding FingerConn object, instead of a TCP_Connection object as it would for an unrecognized port.

FingerConn redefines the virtual function BuildEndpoints, which is invoked when a connection object is first created:

   void FingerConn::BuildEndpoints()
      {
      resp = new TCP_Endpoint(this, 0);
      orig = new TCP_EndpointLine(this, 1, 1, 0);
      }

Here, resp, corresponding to the responder (Finger server) side of the connection, is initialized to an ordinary TCP_Endpoint object, because Bro does not (presently) look inside Finger replies. But orig, the Finger client side, is initialized to a TCP_EndpointLine object, which means Bro will track the contents of that side of the connection, and, furthermore, deliver the contents in a line-oriented fashion to FingerConn's virtual NewLine function:

int FingerConn::NewLine(TCP_Endpoint* /* s */,
                   double /* t */, char* line)
   {
   line = skip_whitespace(line);
 
   // Check for /W.
   int is_long = (line[0] == '/' &&
                  toupper(line[1]) == 'W');
 
   if ( is_long )
      line = skip_whitespace(line+2);
 
   val_list* vl = new val_list;
   vl->append(BuildConnVal());
   vl->append(new StringVal(line));
   vl->append(new Val(is_long, TYPE_BOOL));
 
   mgr.QueueEvent(finger_request, vl);
   return 0;
}

NewLine skips whitespace in the request, scans it for the ``/W'' indicator (which requests verbose Finger output), and moves past it if present. It then creates a val_list object, which holds a list of generic Bro Val objects. The first of these is assigned to a generic connection-identifier value (see below); the second, to a Bro string containing the Finger request, and the third to a bool indicating whether the request was verbose or not. The penultimate line queues a new finger_request event with the corresponding list of values as arguments; finally, return 0 indicates that the FingerConn is all done with the memory associated with line (since new StringVal(line) made a copy of it), so that memory can be reclaimed by the caller.

The connection identifier discussed above is defined in Bro as a ``connection'' record:

type endpoint: record {
   size: count; state: count;
};
type connection: record {
   id: conn_id;
   orig: endpoint; resp: endpoint;
   start_time: time;
   duration: interval;
   service: string;
      # if empty, service not yet determined
   addl: string;
   hot: count;
      # how hot; 0 = don't know or not hot
};

The id field is a conn_id record, discussed in § 3.1. orig and resp correspond to the connection originator and responder, each a Bro endpoint record consisting of size (the number of bytes transferred by that endpoint so far) and state, the endpoint's TCP state (e.g., SYN sent, established, closed). This latter would be better expressed using an enumerated type (rather than a count), which we may add to Bro in the future.

The start_time field reflects when the connection's first packet was seen, and duration how long the connection has existed. service corresponds to the name of the service, or an empty string if it has not been identified. By convention, addl holds additional information associated with the connection; better than a string here would be some sort of union or generic type, if Bro supported such. Finally, by convention the policy script increments hot whenever it finds something potentially suspicious about the connection.

Here is the corresponding policy script:

global hot_names = { "root", "lp", "uucp" };
global finger_log =
   open(getenv("BRO_ID") == "" ?
      "finger.log" :
      fmt("finger.%s", getenv("BRO_ID")));

event finger_request(c:connection,
                     request: string,
                     full: bool)
   {
   if ( byte_len(request) > 80 ) {
      request = fmt("%s...",
                    sub_bytes(request, 1, 80));
      ++c$hot;
   }
   if ( request in hot_names )
      ++c$hot;

   local req = request == "" ?
      "ANY" : fmt("\"%s\"", request);
   if ( c$addl != "" )
      # This is an additional request.
      req = fmt("(%s)", req);
   if ( full )
      req = fmt("%s (/W)", req);
   local msg = fmt("%s > %s %s",
                   c$id$orig_h,
                   c$id$resp_h,
                   req);
   if ( c$hot > 0 )
      log fmt("finger: %s", msg);
   print finger_log,
      fmt("%.6f %s", c$start_time, msg);
   c$addl = c$addl == "" ?
            req : fmt("*%s, %s", c$addl, req);
   }

The global hot_names is a Bro set of string. In the next line, finger log is initialized to a Bro file, either named ``finger.log'', or, if the BRO_ID environment variable is set, to a name derived from it using the built-in fmt function.

The finger_request event handler follows. It takes three arguments, corresponding to the values added to the val_list above. It first checks whether the request is excessively long, and, if so, truncates it and increments the hot field of the connection's information record. (The Bro builtin functions used here are named in terms of ``bytes'' rather than ``string'' because they make no assumptions about NUL-termination of their arguments; in particular, byte_len returns the length of its argument including a final NUL byte, if present.)

Next, the script checks whether the request corresponds to any of the entries in the hot_names set. If so, it again marks the connection as ``hot.''

We then initialize the local variable req to a quoted version of the request; or, if the request was empty (which in the Finger protocol indicates a request type of ``ANY''), then it is changed to ``ANY''.

The event handler stores the Finger request in the connection record's addl field (see below), so the next line checks to see whether this field already contains a request. If so, then we are seeing multiple requests for a single Finger connection. This is not allowed by the Finger protocol, but that doesn't mean we won't see them! In particular, we might imagine a subterfuge attack in which an attacker queries an innocuous name in their first request, and a sensitive name in their second, and depending on how the finger server is
4 We do indeed see occasional multiple requests. So far, they have all appeared fully innocuous.
written, it may well respond to both.4 This script will still catch such use, since it fully processes each request; but it needs to be careful to keep the global state corresponding to the connection (in the addl field) complete. To do so, it marks additional requests by enclosing them in parentheses, and also prepends an asterisk to the entire addl field for each additional request, so that in later visual inspection of the Finger logs these requests immediately stand out. The msg local variable holds the basic description of the Finger request. The fmt function knows to format the IP addresses c$id$orig_h and c$id$resp_h as ``dotted quads.''

Next, if the connection has been marked as ``hot'' (either just previously, or perhaps by a completely different event handler), then the script generates a real-time notification. In any case, it also records the request to the finger_log file. Finally, it updates the addl field to reflect the request (and to flag multiple requests, as discussed above).

Entries in the log file look like:

880988813.752829 171.64.15.68 >
                 128.3.253.104 "feng"
880991121.364126 131.243.168.28 >
                 130.132.143.23 "anlin"
880997120.932007 192.84.144.6 >
                 128.3.32.16 ALL
881000846.603872 128.3.9.45 >
                 146.165.7.14 ALL (/W)
881001601.958411 152.66.83.11 >
                 128.3.13.76 "davfor"
(though without the lines split after the ``>''). The real-time notifications look quite similar, with the keyword ``finger:'' added to avoid ambiguity with other types of real-time notification.

References

[Br88] R. Brown, ``Calendar Queues: A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem,'' Communications of the ACM, 31(10), pp. 1220-1227, Oct. 1988.
[CT94] C. Compton and D. Tennenhouse, ``Collaborative Load Shedding for Media-Based Applications,'' Proc. International Conference on Multimedia Computing and Systems, Boston, MA, May. 1994.
[In97] Internet Security Systems, Inc., RealSecureTM , http://www.iss.net/prod/rs.html, 1997.
[JLM89] V. Jacobson, C. Leres, and S. McCanne, tcpdump, available via anonymous ftp to ftp.ee.lbl.gov, Jun. 1989.
[MJ93] S. McCanne and V. Jacobson, ``The BSD Packet Filter: A New Architecture for User-level Packet Capture,'' Proc. 1993 Winter USENIX Conference, San Diego, CA.
[MLJ94] S. McCanne, C. Leres and V. Jacobson, libpcap, available via anonymous ftp to ftp.ee.lbl.gov, 1994.
[MHL94] B. Mukherjee, L. Heberlein, and K. Levitt, ``Network Intrusion Detection,'' IEEE Network, 8(3), pp. 26-41, May/Jun. 1994.
[Ne97] Network Flight Recorder, Inc., Network Flight Recorder, http://www.nfr.com, 1997.
[Pa94] V. Paxson, ``Empirically­Derived Analytic Models of Wide-Area TCP Connections,'' IEEE/ACM Transactions on Networking, 2(4), pp. 316-336, Aug. 1994.
[Pa97] V. Paxson, ``End­to­End Internet Packet Dynamics,'' Proc. SIGCOMM '97, Cannes, France, Sep. 1997.
[PR83a] J. Postel and J. Reynolds, ``Telnet Protocol Specification,'' RFC 854, Network Information Center, SRI International, Menlo Park, CA, May 1983.
[PR83b] J. Postel and J. Reynolds, ``Telnet Option Specifications,'' RFC 855, Network Information Center, SRI International, Menlo Park, CA, May 1983.
[PR85] J. Postel and J. Reynolds, ``File Transfer Protocol (FTP),'' RFC 959, Network Information Center, SRI International, Menlo Park, CA, Oct. 1985.
[PZCMO96] N. Puketza, K. Zhang, M. Chung, B. Mukherjee and R. Olsson, ``A Methodology for Testing Intrusion Detection Systems,'' IEEE Transactions on Software Engineering, 22(10), pp. 719-729, Oct. 1996.
[RLSSLW97] M. Ranum, K. Landfield, M. Stolarchuk, M. Sienkiewicz, A. Lambeth and E. Wall, ``Implementing a generalized tool for network monitoring,'' Proc. LISA '97, USENIX 11th Systems Administration Conference, San Diego, Oct. 1997.
[Sr95a] R. Srinivasan, ``RPC: Remote Procedure Call Protocol Specification Version 2,'' RFC 1831, DDN Network Information Center, Aug. 1995.
[Sr95b] R. Srinivasan, ``XDR: External Data Representation Standard,'' RFC 1832, DDN Network Information Center, Aug. 1995.
[To97] Touch Technologies, Inc., INTOUCH INSA, http://www.ttisms.com/tti/nsa www.html, 1997.
[Wh97] WheelGroup Corporation, NetRangerTM, http://www.wheelgroup.com, 1997.
[WFP96] G. White, E. Fisch and U. Pooch, ``Cooperating Security Managers: A Peer-Based Intrusion Detection System,'' IEEE Network, 10(1), pp. 20-23, Jan./Feb. 1994.
[Zi91] D. Zimmerman, ``The Finger User Information Protocol,'' RFC 1288, Network Information Center, SRI International, Menlo Park, CA, Dec. 1991.