James E. Pace, Kirk Bradley, Chris Wee
Computer Security Research Laboratory
Department of Computer Science
University of California, Davis
Davis, CA 95616
February 12, 1997
The problem of securing the network infrastructure is difficult.
Audit is essential to a secure system. If an attack occurs, it is vital that a post-mortem analysis take place to determine the cause of the problem and to help locate the attackers. Audit logs are key in this analysis .
We propose to add auditing capability to network packet routers as a method to secure the networking infrastructure. A major benefit of this approach will be to detect routers that are acting maliciously and to logically remove them from the network.
To test this hypothesis, we will enhance the Maryland Routing Simulator (MaRS) to produce audit data and to simulate malicious routers. We will design and implement a detection engine which analyzes the data and determines whether or not a malicious router exists.
This approach is new. Currently, routers do not have adequate audit capability. Other attempts to solve the malicious router problem tend to alter the routing protocols to flood the network with control packets, or they rely on certain thresholds of "goodness", such as the number of packets dropped. Our method will work with existing routing protocols, and will add little traffic to the network. The method is also important since routers cannot spare valuable computation time analyzing data, looking for network attacks.
Success of this research will indicate that auditing is a valuable asset to router security.
Routers are vulnerable in many of the same ways that traditional hosts are vulnerable. Much of the literature on router security refers to securing the router itself; using strategies such as S/Key or refusing logins.
Recently, several denial of service attacks traditionally used against hosts have been shown effective against routers. They include the so-called Ping O' Death , under which an unacceptably long ICMP packet crashes or reboots a machine. This problem is caused by a vulnerability in the TCP/IP implementation and buffer management.
This host-style security is a crucial part of network security, but it is not sufficient. Routers also are vulnerable to another class of problems, which are specific to routers.
RIPForge  shows one of the common problems seen in routing protocols. This program allows a user who has root access on a machine to generate false routing updates. Thus, one can convince the network that there is no route to a host, causing a denial-of-service, or one can advertise false low-cost routes, which would bring most network traffic through one, possibly compromised, location.
There are current solutions to these router-specific problems . Unfortunately, these solutions are not practical for current router technology. Since the primary task of a router is to deliver data packets between source and destination, anything which significantly impacts the processing time and bandwidth utilization of a router is unacceptable.
Most routers currently have the ability to record debug information to a remote host , a la syslog. Unfortunately, this generates network traffic. In order to transmit sufficient audit data to detect malicious entities in a large network, much of the bandwidth would be used transmitting the data.
Our model contains a network of hosts and routers, all using the same routing protocol. This is an accurate model of an autonomous system (AS), which is "a set of routers and networks under the same administration" .
Each router will log all changes to its internal state. State information includes the routing table, network topology, link utilization, and number of packets processed, as well as a measure of the current time. Figure 1 shows a high-level view of the log format.
|Time||Router ID||Changes to Previous State|
A centralized detection engine will analyze the audit data and make a determination of whether a malicious router exists in the network.
This detection will take place periodically to minimize the threat of an attack while balancing the amount of network traffic generated and the amount of resources available at the router.
We have chosen to use a centralized detection method for several reasons. A distributed scheme would add redundant work to the already over-utilized routers. By minimizing the amount of work that each router does, we eliminate this performance loss. Also, a centralized method has all the available information of the network, whereas each router may only have partial information.
Several assumptions are implicit to the model:
We will add auditing features to a simulated network of routers and hosts which contains one or more routers that misbehave. We will analyze the network-generated audit data, and determine whether or not this data aided in the discovery of the malicious elements.
When research is completed, we will have a detection algorithm, a suite of attacks which we can detect, and a list of data that is necessary to record.
First, we will extend the MaRS code to produce audit data. MaRS was designed primarily as a performance simulator, so the current logging and debugging messages are not suited for our requirements.
Next, we will add the capability of a MaRS router to produce incorrect routing updates; that is, we will simulate a misbehaving router.
The most basic form of a misbehaving router is one which drops all packets given to it. This seems to be the natural place to begin simulation.
We will design an algorithm to detect the presence of malicious routers, which will use all available data.
Once the basic work has been done with this algorithm, it can be refined for a more elegant solution. Currently, Bradley  is working on more advanced audit-based detection algorithms.
We will design and implement a detection engine which implements the detection algorithm. The engine will gather the audit logs from all participating routers on a regular basis and will determine whether or not some router in the network is acting maliciously.
By adding audit data to routers, the security of the network infrastructure will be increased. With a small amount of additional network traffic, we can piece together a snapshot of the network at any given time and make observations about its routers.
Auditing has a large advantage over other proposed methods of securing network routers, such as Cheung's method . Since the log is stored locally, our method only uses additional network bandwidth when transmitting the logs to another site. The processing time added for logging should be small. The additional storage needed will be relatively small when proper care is taken with the data .
We also hope to demonstrate that this method performs well on an arbitrarily large AS, due to the detection algorithm's off-line nature.
We will know that this work has been successful if we are able to detect any sort of malicious device in a generalized network. Once we have completed our research and simulation, we will enumerate the attacks we have discovered for which this is a viable anomaly detection methodology.