Sensor-based intrusion detection for intra-domain distance-vector routing.
Detection of routing-based attacks is difficult because malicious routing behavior can be identified only in specific network locations. In addition, the configuration of the signatures used by intrusion detection sensors is a time-consuming and error-prone task because it has to take into account both the network topology and the characteristics of the particular routing protocol in use. We describe an intrusion detection technique that uses information about both the network topology and the positioning of sensors to determine what can be considered malicious in a particular place of the network. The technique relies on an algorithm that automatically generates the appropriate sensor signatures. This paper presents a description of the approach, applies it to an intra-domain distance-vector protocol and reports the results of its evaluation.
INTRODUCTION
Attacks against the IP routing infrastructure can be used
to perform substantial denial-of-service attacks or as a basis
for more sophisticated attacks, such as man-in-the-middle
and non-blind-spoofing attacks. Given the insecure nature
of the routing protocols currently in use, preventing these
attacks requires modifications to the routing protocols, the
routing software, and, possibly, the network topology itself.
Because of the critical role of routing, there is a considerable
inertia in this process. As a consequence, insecure routing
protocols are still widely in use throughout the Internet.
A complementary approach to securing the routing infrastructure
relies on detection of routing attacks and execution
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
CCS'02, November 18-22, 2002, Washington, DC, USA.
of appropriate countermeasures. Detecting routing attacks
is a complex task because malicious routing behavior can
be identified only in specific network locations. In addi-
tion, routing information propagates from router to router,
throughout the network. Therefore, the presence of malicious
routing information is not necessarily restricted to the
location where an attack is carried out.
We describe a misuse detection technique that uses a set
of sensors deployed within the network infrastructure. Sensors
are intrusion detection components equipped with a set
of signatures, which describe the characteristics of malicious
behavior. The tra#c that is sent on the network links is
matched against these signatures to determine if it is malicious
or not.
The use of multiple sensors for intrusion detection is a
well-established practice. The analysis of network tra#c at
di#erent locations in the network supports more comprehensive
intrusion detection with respect to single-point analysis.
The disadvantage of a distributed approach is the di#culty
of configuring the sensors according to the characteristics of
the protected network. This problem is exacerbated by the
nature of routing. The configuration of the sensors has to
take into account the network topology, the positioning of
the sensors in the network, and the characteristics of the
particular routing protocol in use. In addition, some attacks
can be detected only by having sensors communicate
with each other. As a consequence, the configuration of
the signatures used by the sensors is a time-consuming and
error-prone task.
The novel contribution of our approach is an algorithm
that, given a network topology and the positioning of the intrusion
detection sensors, can automatically determine both
the signature configuration of the sensors and the messages
that the sensors have to exchange to detect attacks against
the routing infrastructure. This paper introduces the general
approach and describes its application to the Routing
Information Protocol (RIP).
RIP is an intra-domain distance-vector routing protocol
[13]. At startup, every RIP router knows only its own addresses
and the links corresponding to these addresses. Every
RIP router propagates this information to its immediate
neighbors. On receiving the routing information, the neighbors
update their routing tables to add, modify, or delete
routes to the advertised destinations.
Routers add a route to a destination if they do not have
one. A route is modified if the advertised route is better
than the one that the router already has. If a router receives
a message from a neighbor advertising unreachability to a
certain destination and if the router is using that neighbor
to reach the destination, then the router deletes the route
to the destination from its routing table.
Under certain conditions, RIP might not converge. It may
exhibit the bouncing-e#ect problem or the count-to-infinity
problem [9]. These problems are partially overcome by using
the split-horizon technique, triggered-updates, and by
limiting the number of hops that can be advertised for a
destination 1 .
In order to decide whether a routing update is malicious
or not, a router needs to have reliable, non-local topology
information. Unfortunately, RIP routers do not have this
information. To support router-based intrusion detection it
would be necessary to modify both the RIP protocol and the
routing software. Therefore, our approach relies on external
sensors.
Sensor configurations are generated o#ine on the basis of
the complete network topology and the positions of the sensors
in the network. The configuration generation algorithm
determines every possible path from every router to every
other router. The configuration for an individual sensor is a
subset of this information based on the position of the sensor
in the network. Sensors need to be reconfigured if routers
and links are added to the topology. However, sensors do
not need to be reconfigured if the topology changes due to
link or router failures.
The remainder of this paper is organized as follows. Section
related work in the field. Section 3 introduces
an abstract reference model of the network routing
infrastructure. Section 4 presents an algorithm to generate
the configuration of intrusion detection sensors for the RIP
distance-vector protocol. Section 5 discusses how routing
attacks are detected. Section 6 describes the experimental
setup that was used to analyze the attacks and evaluate the
detection technique. Section 7 discusses the strengths and
weaknesses of the approach. Section 8 draws some conclusions
and outlines future work.
2. RELATED WORK
One of the earliest works on securing routing protocols is
by Radia Perlman [16]. Perlman suggests the use of digital
signatures in routing messages to protect against Byzantine
failures. The main drawback of this approach is that generating
digital signatures is a computationally intensive task.
Signature verification is usually not as expensive, but most
of the solutions that use digital signatures require that a
number of them be verified, leading to a considerable performance
overhead.
The use of digital signatures is also advocated by Murphy
et al. [14, 15] for both distance-vector and link-state
advertisements. Kent et al. [12, 11] describe an approach to
allow the recipient of a BGP [18] message to verify the entire
path to a destination. Smith et al. [19] introduce a scheme
to protect BGP using digital signatures and also describe a
scheme to secure distance-vector routing protocols by using
predecessor information [20].
Several other schemes have been proposed to reduce the
performance overhead associated with securing routing protocols
using digital signatures. Hauser et al. [7] describe two
techniques for e#cient and secure generation and processing
of updates in link-state routing. Zhang [24] describes
that routing messages can be protected by using one-time
1 Limiting the number of hops ensures that a route is declared
unusable, when the protocol does not converge and the number
of advertised hops exceeds the maximum number of allowed hops.
However, this also limits the diameter of the networks in which
RIP can be used.
signatures on message chains. In [6], Goodrich describes a
leap-frog cryptographic signing protocol that uses secret-key
cryptography.
While the research referenced so far focuses on preventing
attacks, a complementary approach to the problem of
securing the routing infrastructure focuses on detecting attacks
[1, 5, 8]. For example, Cheung et al. [3, 4] present
solutions to the denial-of-service problem for the routing
infrastructure using intrusion detection. Another example
is a protocol called WATCHERS described by Bradley et
al. [2]. The protocol detects and reacts to routers that drop
or misroute packets by applying the principle of conservation
of flow to the routers in a network. The JiNao project
at MCNC/NCSU focuses on detecting intrusions, especially
insider attacks, against OSPF. Wu et al. [21, 17, 23, 22, 10]
consider how to e#ciently integrate security control with
intrusion detection in a single system.
The approach described in this paper di#ers from other intrusion
detection approaches because it focuses on the topological
characteristics of the network to be protected and the
placement of the detection sensors. The approach relies on
topology information to automatically generate the signatures
used by sensors to detect the attacks. The details of
the algorithm and its application are described in the following
sections.
3. REFERENCE MODEL
An abstract reference model of the network is introduced
to describe the algorithm used to generate the signatures
and how these signatures are used to detect attacks against
the routing infrastructure. A network is represented by an
undirected graph E) where vertices
, vn} denote the set of routers. Positive weight edges
links connecting router
interfaces. An routers v i and v j . 2
A subnet is a range of IP addresses with the same network
mask. Every link e ij is associated with a subnet s ij .
{s1 , s2 ,    , sm} is the set of subnets corresponding to the
set of links E. We assume that e
Every vertex has an associated set
} # E that represents the set of edges connected to v j .
is the set of subnets corresponding to
the set of links E j . Every link e ij is associated with a cost
sensor placed on link e ij is identified
as sensor ij . A host p that is connected to link e ij is denoted
by h p
ij .
Consider the sub-graph Gsub # G shown in Figure 1. In
that context, routing problems can occur due to faults in
routers or due to malicious actions of both
the routers and the host h p
ij . Hosts or routers are termed
malicious when they have been compromised and are used
as a means to modify the normal operation of the network.
Both network failures and threats due to malicious intent
need to be included in the threat model because a sensor
cannot always di#erentiate between the two. The approach
described here is concerned with attacks involving injection,
alteration, or removal of routes to specific destinations, by
2 For the sake of simplicity, this model does not consider the possibility
of more than two routers being connected to a single link.
The model can be extended to support that possibility by assuming
graph G to be a hyper-graph.
3 The model does not consider the possibility of links being asym-
metric, i.e., having di#erent costs in di#erent directions. The
model can be extended to support asymmetric costs by assuming
graph G to be a directed graph
s ik
e ik

Figure

1: Threat Reference Model
malicious hosts or routers. Security threats, e.g., unauthorized
access to information, dropping and alteration of data
packets by routers, etc., are not addressed here. More pre-
cisely, we can describe our threat model with respect to Gsub
as follows:
1. v i fails. This will result in sub-optimal paths or no
paths at all from s ij to s ik and vice-versa.
2. v i is compromised and misconfigured to advertise a
sub-optimal or infinite-cost path to s ik . This will result
in sub-optimal paths or no paths at all from s ij
to s ik .
3. v j is compromised and misconfigured to advertise a
better than optimal path for s ik . This will result in
hosts from subnet s ij using v j to reach hosts in subnet
s ik even though v i has a better route to subnet s ik .
actually has no path to subnet s ik then packets
from subnet s ij will not reach subnet s ik .
4. h p
ij pretends to be v i with respect to v j or pretends
to be either v j or vk with respect to v i . h p
ij can then
advertise routes as in 2 and 3.
5. h p
renders v i unusable and pretends to be v i . h p
advertises the same information as v i but since v i is
unusable, packets do not get routed.
Gsub represents a segment of the network, represented by G,
where incorrect routing information is generated. If there is
a sensor present on every link of Gsub , the faulty or malicious
entity can be identified and a response process can be
initiated. In the absence of sensors on every link of Gsub ,
the incorrect routing information can propagate to the rest
of the network. In this case, the attack can still be detected,
but determining the origin of the attack requires an analysis
of the e#ects of the incorrect routing information. This
analysis is considerably di#cult to perform and is not in the
scope of the approach described here.
4. SENSOR CONFIGURATION
A sensor is configured on the basis of the network topology
and the sensor's position in the network. A sensor's
position in the network is specified by the link on which the
sensor is placed. A separate component, called the Sensor
Configurator, is given the network topology and the position
of all available sensors as inputs. The Sensor Configurator
uses an algorithm to generate the configuration of each sen-
sor. The configurations are then loaded into the appropriate
sensors.
The first step of the Sensor Configurator algorithm is
to find all paths and their corresponding costs from every
s
e
e

Figure

2: Sensor Configuration Example
router to every other router in the graph G. The results
are organized into a 2-dimensional vertex-to-vertex matrix.
The (i, th entry of the matrix points to a list of 2-tuples
ij )}. The list contains a tuple for each path between
vertices
ij is a set of vertices traversed to reach
v j from v i . c k
ij is the cost of the path p k
ij between vertices
. For example, consider Figure 2. v1 , v2 , v3 are
routers. e12 , e13 , e23 , e24 , e35 are links with associated sub-nets
respectively. The cost of all links
is equal to 1. Table 1 shows the vertex-to-vertex matrix for
the graph in Figure 2. The {(cost, path)} entry in row v1 ,
column v1 , is the set of possible paths and their corresponding
costs that vertex v1 can take to reach vertex v1 . The
entry {(0, (#))} means that vertex v1 can reach vertex v1 at
cost 0, through itself. The entry in row v1 , column v2 , means
that vertex v1 can reach vertex v2 at cost 1 through itself
or at cost 2 through vertex v3 . In the second step of the
algorithm, the vertex-to-vertex matrix is transformed into a
2-dimensional vertex-to-subnet matrix. Each column, representing
a vertex v j of the vertex-to-vertex matrix, is replaced
by a set of columns, one for each subnet directly connected
to the vertex, i.e., one for each member of S j . Consider
the set of columns S replacing column
. The set of paths in the vertex-to-subnet matrix is
i,jx is the k th path from router v i to subnet s jx in the
vertex-to-subnet matrix and p k
ij is the corresponding path in
the vertex-to-vertex matrix. The set of costs in the vertex-
to-subnet matrix is {(c k
i,jx is the cost of the k th path
from router v i to subnet s jx in the vertex-to-subnet matrix
and c k
ij is the corresponding cost in the vertex-to-vertex ma-
trix. c jx is the cost of the link e jx associated with subnet
s jx . This cost must be taken into account because c k
ij only
represents the cost of the path from router v i to v j . The cost
to reach subnet s jx from router v j should be added to c k
to get the total cost c k
i,jx . For example, the vertex-to-vertex
matrix shown in Table 1 is transformed into the vertex-to-
subnet matrix shown in Table 2. The {(cost, path)} entry in
row v1 , column s12 is the set of possible paths that vertex v1
can take to reach subnet s12 and their corresponding costs.
The entry {(1, (v1 ))} means that vertex v1 can reach subnet
s12 at cost 1, through v1 . The entry in row v1 , column s23 ,
means that vertex v1 can reach subnet s23 at cost 2 through
vertex v2 or at cost 3 through vertices v3 and v2 , and so on.
v1 {(0, (#))} {(1, (#)), (2, (v3 ))} {(1, (#)), (2, (v2 ))}
v2 {(1, (#)), (2, (v3 ))} {(0, (#))} {(1, (#)), (2, (v1 ))}
v3 {(1, (#)), (2, (v2 ))} {(1, (#)), (2, (v1 ))} {(0, (#))}

Table

1: Vertex-to-Vertex Matrix
v1 {(1, (v1 ))} {(1, (v1 ))} {(2, (v2 )), {(2, (v2 )), {(2, (v2 )), {(2, (v3 )), {(2, (v3 )), {(2, (v3 )),
(3, (v3 , v2 ))} (3, (v3 , v2 ))} (3, (v3 , v2 ))} (3, (v2 , v3 ))} (3, (v2 , v3 ))} (3, (v2 , v3 ))}
v2 {(2, (v1 )), {(2, (v1 )), {(1, (v2 ))} {(1, (v2 ))} {(1, (v2 ))} {(2, (v3 )), {(2, (v3 )), {(2, (v3 )),
(3, (v3 , v1 ))} (3, (v3 , v1 ))} (3, (v1 , v3 ))} (3, (v1 , v3 ))} (3, (v1 , v3 ))}
v3 {(2, (v1 )), {(2, (v1 )), {(2, (v2 )), {(2, (v2 )), {(2, (v2 )), {(1, (v3 ))} {(1, (v3 ))} {(1, (v3 ))}
(3, (v2 , v1 ))} (3, (v2 , v1 ))} (3, (v1 , v2 ))} (3, (v1 , v2 ))} (3, (v1 , v2 ))}

Table

2: Vertex-to-Subnet Matrix
The vertex-to-subnet matrix is in a format that is similar to
the one used by the routers themselves.
Once the vertex-to-subnet matrix has been computed for
the entire network, the portion of the vertex-to-subnet matrix
relevant to each sensor is extracted. Each sensor uses
its vertex-to-subnet matrix to validate the routing advertisements
that are sent on the link on which the sensor is
placed. More precisely, sensor ij , placed on link e ij , needs to
validate routing advertisements from routers v i and v j only. 4
Therefore, the vertex-to-subnet matrix for sensor ij has rows
from the common vertex-to-subnet matrix corresponding to
Some entries in a vertex-to-subnet matrix may not correspond
to actual routing information. Therefore, the matrix
can be further reduced by ignoring these entries. Consider
the vertex-to-subnet matrix for sensor ij on link e ij with
routers v i and v j . s ik is the subnet on
link e ik between routers v i and vk . sab is any other subnet.
In this context, the vertex-to-subnet matrix for sensor ij is
reduced according to the following rules:
1. For neighboring routers v i and vk , row v i , columns s ik
or ski , a {(cost, path)} tuple is ignored if the path is of
the form (vk ). For example, in Table 2, for row v1 , column
s31 , the {(cost, path)} tuple {(2, (v3 ))} is ignored
because subnet s31 is directly connected to router v1 .
Therefore, v1 will never advertise a route on link e12
for subnet s31 through router v3 at cost 2.
2. For any row, columns sab or sba , a {(cost, path)} tuple
is ignored if the path is of the form (   , va , v b ,    ) or
For example, in Table 2, for row v1 ,
column s23 , the {(cost, path)} tuple {(3, (v3 , v2 ))} is
ignored because router v1 can reach subnet s23 at cost
through router v3 . Therefore, v1 will not advertise a
route to subnet s23 through (v3 , v2 ) at cost 3.
3. For neighboring routers v i and v j , row v i , columns s ij
or s ji , a {(cost, path)} tuple is ignored. For example,
in

Table

2, for row v1 , column s12 , the {(cost, path)}
tuple {(2, (v2 ))} is ignored because both routers v1 and
v2 are directly connected to subnet s12 and have the
same cost to s12 . Router v2 will never use a longer
path through v1 to reach a directly connected subnet
4 A sensor needs to validate routing advertisements only from
routers connected to the link on which it is placed, because
distance-vector routers advertise routing information only on
links connected to them directly.
s12 . Therefore, v1 will never advertise such a route to
v2 .
4. For neighboring routers v i and v j , row v i , any column,
a {(cost, path)} tuple is ignored if the path is of the
form (v j ,    ). For example, in Table 2, for row v1 , column
s23 , the {(cost, path)} tuple {(2, (v2 ))} is ignored
because if in the route advertised by v1 for subnet s23
the first hop is router v2 , then v1 has learned that route
from v2 . This implies that v2 has a better route to s23
than v1 has and will never use v1 to reach s23 . There-
fore, v1 will never advertise such a route to v2 . The
split-horizon check in RIP ensures the same thing.
After the simplification of the vertex-to-subnet matrix for
sensor ij , with rows v i and v j , the term v i is actually replaced
by a tuple {v link
link
i is the link-level
address of the interface of router v i that is connected to
i is the corresponding IP address. Similarly, the
replaced by a tuple {v link
Finally, the information
regarding the position of other sensors is added
to the vertex-to-subnet matrix by marking the links where
the sensors are placed.
5. SENSOR DETECTION ALGORITHM
Once the o#ine process of generating the sensor configurations
is completed, the configurations are loaded into the
sensors. At run-time the sensors analyze the routing advertisements
that are sent on the corresponding link. They
match the contents of a routing advertisement with their
configuration to decide whether the routing advertisement
represents evidence of an attack or not.
Consider sensor ij , placed on link e ij . In addition to storing
link
link
sensor ij also stores e link bcast
ij and e ip bcast
ij , which are the link-level
and IP broadcast addresses for link e ij and rip linkmcast
and rip ipmcast , which are the link-level and IP multicast addresses
for RIP routers.
In its vertex-to-subnet matrix, sensor ij also stores {(cost,
path)} sets from router v i to subnet sab of the form {(c
is the optimal cost at which router v i can send data to subnet
sab , through path p
i,ab . There can be multiple optimal-cost
paths {p
i,ab ,    } with costs {c
i,ab ,    } from
router v i to subnet sab such that c
i,ab .
Router v i can also send data to subnet sab through a path
i,ab with a sub-optimal cost c s 1
i,ab . There can be multiple
sub-optimal-cost paths {p s 1
i,ab ,    } from router v i to subnet sab .
Next, consider a distance-vector routing advertisement m,
where m is of the type:
[Link-Level-Header [IP-Header [UDP-Header [Distance-Vector Routing
For routing advertisement m, m linksrc and m link dst are the
link-level source and destination addresses respectively, m ipsrc
and m ip dst are the IP source and destination addresses re-
spectively, m ttl is the time-to-live field in the IP header,
and m c ab is the cost advertised for subnet m s ab . By using
the information stored by the sensor and the information
contained in the routing message it is possible to verify
the correctness of link-level and network-level information,
the plausibility of the distance-vector information, the messages
that are needed to verify advertised routes, and the
frequency of routing updates. These four verifications are
described in the following sections.
5.1 Link-Level and Network-Layer Information
Verification
A legitimate routing advertisement must have the link-level
address and IP address of one of the routers connected
to the link 5 and have a time-to-live value equal to 1.
The following is a relation between the fields m linksrc ,
link dst , m ipsrc , m ip dst , m ttl , m c ab and m s ab , of a legitimate
routing advertisement m:
link
{(m link dst = v link
(m link dst = e link bcast
bcast
(m link dst = rip linkmcast V
ipmcast )}]
link
{(m link dst = v link
(m link dst = e link bcast
bcast
(m link dst = rip linkmcast
ipmcast )}]}
In the above relation, if the link-level and IP source addresses
of routing advertisement m are those of router v i ,
then the link-level and IP destination addresses of m should
be those of router v j , the broadcast address of link e ij , or
the multicast address of RIP routers. If m has originated
from router v j , the source link-level and IP addresses should
be those of router v j and destination link-level and IP addresses
should be those of router v i , the broadcast address
of link e ij , or the multicast address of RIP routers. The
time-to-live field of m should be 1. Note that link-level and
network-layer information can be spoofed. Therefore, this
verification alone is not enough to conclude that a routing
advertisement is not malicious.
5.2 Distance-Vector Information Verification
Routing advertisements for subnets that do not belong
to the local autonomous system indicate that the routing
advertisements are malicious. 6 A sensor scans a routing ad-
5 In distance-vector routing protocols, routing advertisements are
meant for a router's immediate neighbors only.
6 Routers running intra-domain routing protocols do not have
routes to every possible subnet. Usually, routes to subnets out-
sensor 34
sensor 12
sensor
sensor 67 sensor 89
e 34
e
e 78
e
e 67
e 26
e 59

Figure

3: Sensor Detection Example
vertisement for attacks by matching every advertised subnet
against the list of subnets that the sensor has in its config-
uration. If the sensor does not find a match, it declares the
routing advertisement to be malicious.
Next, a routing advertisement is analyzed to determine
whether the advertised cost is optimal, sub-optimal, or im-
possible. An optimal cost is the cost of one of the shortest
paths from a router to a destination advertised by the router.
A sub-optimal cost is the cost of one of the paths from a
router to a destination advertised by the router. This path
may not necessarily be the shortest. An impossible cost is
a cost not associated to any of the paths from a router to
a destination advertised by the router. Unreachability, i.e.,
where the advertised cost is 15, is considered sub-optimal
rather than impossible.
Consider a routing advertisement m, originating from router
v i on link e ij , advertising a cost m c ab for subnet m s ab . The
sensor configuration defines the following costs for reaching
sab from
optimal-cost
,    } sub-optimal-cost
impossible-cost
The above relation states that in a routing advertisement
m, advertised by router v i for subnet sab , the cost m c ab is
optimal if it belongs to the set of optimal costs; sub-optimal
if it belongs to the set of sub-optimal costs; impossible if it
does not belong to the set of optimal costs or sub-optimal
costs. Assuming that a sensor has the correct topological
information, an impossible-cost advertisement detected by
the sensor is considered malicious. Better-than-optimal-cost
routing advertisements can be detected by checking the routing
advertisements for impossible-cost advertisements. For
example, consider Figure 3. The costs of all links are equal
to 1. The set of optimal costs that router v2 can advertise
for subnet s45 , on link e12 , is {3}, using path {(v2 , v3 , v4 )}.
The set of sub-optimal costs that router v2 can advertise for
subnet s45 , on link e12 , is {5, 6, 6} with paths {(v2 , v6 , v7 , v8 ,
tively. No paths from router v1 are considered, since router
v2 will not advertise any paths that it has learned through
router v1 on link e12 . Costs advertised by router v2 on link
e12 for subnet s45 that are not 3, 5, or 6 are impossible costs.
side the autonomous system are only known to the border routers.
Non-border routers use default routes to the border routers for
external subnets.
5.3 Path Verification
The impossible-cost-advertisement verification cannot determine
the validity of an optimal-cost or sub-optimal-cost
advertisement. A malicious entity can advertise a sub-optimal
cost to a destination even though the corresponding
optimal-cost path is available for use. For example, in Figure
3, subnet s45 can be reached at cost 3 from router v2 but
a malicious entity on link e12 can pretend to be router v2 and
cost 6 for subnet s45 . This will result in router v1
using router v10 , instead of router v2 , to send data to subnet
s45 . A malicious entity can also advertise an optimal cost
when the optimal-cost path is not available. For example,
in

Figure

3, a malicious entity on link e12 can pretend to be
router v2 and advertise cost 3 for subnet s45 when subnet
s45 is no longer reachable using path {(v2 , v3 , v4 )}. In addi-
tion, a malicious entity can subvert a router and configure
it to drop data packets, or it may impersonate a router after
having disabled the router.
In all the above attacks, the advertised distance-vector
information is correct. Therefore, these attacks cannot be
detected by merely verifying the distance-vector informa-
tion. To detect such attacks, sensors use a path-verification
algorithm. Consider sensor ij on link e ij between routers v i
and v j . If sensor ij finds in a routing advertisement m the
cost m c ab advertised by router v i for subnet m s ab to be optimal
or sub-optimal, then for all costs c k
ab , the sensor searches
its configuration for all paths p k
i,ab that have cost c k
i,ab .
The set of sensors on path p k
i,ab is Sensor k
i,ab . sensor ij
verifies path p k
i,ab by sending a message to every sensoryz
i,ab . For example, consider Figure 3. In this case,
sensor12 on link e12 detects a routing advertisement from
router v2 for subnet s45 at cost 3. Therefore, sensor12
searches its configuration to find all paths that have cost 3.
sensor12 finds that path {(v2 , v3 , v4 )} has cost 3. In its con-
figuration, sensor12 also has the information that for path
links e34 and e45 have sensor34 and sensor45
on them. To validate the advertisement, sensor12 sends
messages to sensor34 and sensor45 . If the advertised cost
had been 5, sensor12 would have sent messages to sensor67 ,
sensor89 and sensor45 .
The path-verification algorithm can be more formally stated
as follows. sensor ij on link e ij verifies a routing advertisement
m from router v i , advertising an optimal or sub-optimal
cost m c ab for subnet sab , using the following steps:
1. If m c ab is the optimal cost c
i,ab from router v i to subnet
its configuration to find all paths
i,ab from router v i to subnet sab , corresponding to
cost c
i,ab , and the set of available sensors Sensor k
on those paths.
2. If Sensor k
there are no sensors on path
verify if a path from router
v i to subnet sab exists. If there are sensors on every
link of path p k
i,ab then the entire path can be verified.
If sensors are not present on every link of path p k
i,ab but
a sensor is present on eab then the intermediate path
cannot be verified but it can be verified that subnet sab
is reachable from router v i . If there is no sensor present
on eab then it cannot be verified whether subnet sab is
reachable from router v i or not.
3. If Sensor k
i,ab #} then sensor ij sends a message to
every sensoryz # Sensor k
i,ab for every path p k
i,ab .
4. Every path p k
i,ab is an available path for which every
i,ab replies to sensor ij . If there
are one or more available paths p k
a valid routing advertisement. If there are none,
declares m to be malicious.
5. If m c ab is a sub-optimal cost, sensor ij searches its configuration
to find paths p q k
i,ab from router v i to subnet
sab corresponding to every cost c q
i,ab such that c
c q
i,ab is the optimal cost from router v i to
subnet sab . sensor ij also determines the sets of available
sensors Sensor q k
i,ab corresponding to paths p q k
i,ab .
sends a message to every sensoryz # Sensor s k
for paths p s k
i,ab from router v i to subnet sab corresponding
to every cost c s
i,ab such that c
i,ab is the optimal cost from router v i to subnet
sab . Note that the only di#erence between p q k
i,ab and
i,ab is that the latter does not contain paths with costs
equal to m c ab . Therefore, p s k
i,ab and Sensor s k
i,ab .
7. Every path p s k
i,ab is an available path for which every
i,ab replies to sensor ij . If no available
exist, then sensor ij verifies paths p k
from router v i to subnet sab corresponding to cost
ab . Every path p k
i,ab for which every sensoryz #
i,ab replies to sensor ij is an available path. If
there are one or more available paths p k
routing
advertisement m with cost m c ab is considered a
valid routing advertisement. If there are no available
paths then sensor ij declares m to be malicious.
8. For every available path p s k
i,ab , i.e., where every sensoryz
i,ab replies to sensor ij , sensor ij waits for a
time-period t delay . For every available path p s k
sensor ij does not get a routing advertisement m # , with
cost c s k
i,ab , within t delay , then sensor ij declares routing
advertisement m to be malicious.
For example, consider Figure 3. sensor12 detects a routing
advertisement from router v2 for subnet s45 at cost 3.
sensor12 searches its configuration and finds 3 to be the
optimal cost from router v2 to subnet s45 . sensor12 finds
path {(v2 , v3 , v4 )} that has cost 3. Therefore, sensor12 sends
messages to sensors available on this path, i.e., sensor34
and sensor45 . If sensor12 does not get replies from both
sensor34 and sensor45 , it concludes that the path from
router v2 to subnet s45 is unavailable. If sensor12 gets a
reply from sensor45 but not from sensor34 , sensor12 can
conclude that subnet s45 is reachable from router v2 but
it cannot verify the path. If sensor12 gets a reply from
sensor34 but not from sensor45 , sensor12 cannot be sure if
subnet s45 is reachable from router v2 or not. If sensor12
gets a reply from both sensor34 and sensor45 , sensor12 can
be sure that subnet s45 is reachable from router v2 . For the
placement of sensors in Figure 3, sensor12 can never be sure
of the complete optimal path from router v2 to subnet s45 ,
since link e23 does not have a sensor on it.
Assume now that sensor12 detects a routing advertisement
from router v2 for subnet s45 at cost 5. The sensor
searches its configuration and finds 5 to be a sub-optimal
cost from router v2 to subnet s45 and identifies path {(v2 ,
v6 , v7 , v8 , v4 )} as the only path that has cost 5 from router
v2 to subnet s45 . In addition, the sensor looks for paths
that have costs greater than or equal to the optimal cost
and less than 5. The only such path in this case is the
path having the optimal cost 3. Therefore, sensor12 sends
messages to sensors available on the path having cost 3.
If sensor12 finds this path unavailable then sensor12 sends
messages to sensors available on the path having cost 5, i.e.,
sensor67 , sensor89 and sensor45 . If sensor12 gets replies
from all sensor67 , sensor89 and sensor45 , then the routing
advertisement for cost 5 is valid. However, it is not possible
to reliably determine if the path having cost 3 is unavailable.
In general, in a hostile environment a sensor can determine
availability of a path to a subnet but it cannot determine its
unavailability. By dropping or rerouting a message from the
requesting sensor or the replying sensor, a malicious entity
can make the requesting sensor believe that a path to a
subnet is unavailable. On the other hand, if a malicious
can drop or re-route packets on a path, the path is
unreliable and an unreliable path is as good as not being
available at all.
If sensor12 finds that the path having cost 3 is available
then it is possible that either the routing advertisement of
cost 5 is malicious or the routing advertisement is due to a
transitory change in the routing configuration. If the routing
advertisement is transitory and the path from v2 to subnet
s45 at cost 3 is available, then v2 should eventually advertise
a route to subnet s45 at cost 3. If sensor12 does not
see a routing advertisement at cost 3 then the routing advertisement
at cost 5 is malicious. If sensor12 sees a routing
advertisement at cost 3 then the sensor does not verify the
path having cost 5 any further.
5.4 Timing Verification
Routers advertise routing messages at certain intervals of
time. The interval of time at which RIP messages are advertised
is rip interval . A router can send more than one RIP
message in rip interval . 7 rip high
threshold is the maximum number
of packets that a sensor should ever see within rip interval .
A sensor maintains a counter rip i
counter and a timer rip i
timer
for each router v i that is connected to the link on which the
sensor is placed. The sensor initializes rip i
timer and sets
rip i
counter to 0. It sets the time-out value to rip interval .
The sensor increments rip i
counter for every RIP advertisement
that it sees from router v i . If rip i
counter is greater then
rip high
threshold when rip i
timer expires, then this is considered an
attack.
The sensor also maintains a value rip low
threshold , which is
the minimum number of packets that a sensor should see
within rip interval . If rip i
counter is less that rip low
threshold when
rip i
timer expires, it can be inferred that the router is not
working. This could be due to a denial-of-service attack
against the router or due to a failure. rip high
threshold and rip low
threshold
are implementation and topology dependent. These values
have to be experimentally or statistically determined for a
network.
6. EXPERIMENTAL VALIDATION
An experimental testbed network was built to test the
vulnerability of routing protocols. The testbed routers are
multi-homed PCs, equipped with the GNU Zebra routing
daemon, version 0.91a. The testbed contains five di#erent
autonomous systems. The autonomous systems exchange
7 RIP information from one router may be split and advertised in
multiple RIP messages.
routing information using BGP. The interior gateway protocol
used within the autonomous systems is either RIP or
OSPF.

Figure

4 is a schematic of the complete testbed topol-
ogy. The experiments presented in this paper only use autonomous
system 1. The other autonomous systems were
used to conduct experiments on OSPF and BGP. Those experiments
are not discussed in this paper.
The networks in the testbed have addresses in the range
192.168.x.x. Each network has a subnet mask of 255.255.-
255.0. In the following, subnet "x" is used to denote sub-net
192.168.x.0 and address "x.x" denotes the IP address
192.168.x.x.
The following sections discuss three very simple attacks
that were carried out on the testbed. These attacks are
proof-of-concepts to demonstrate the vulnerabilities in distance-vector
routing protocols and how the approach described
here is used to detect these attacks.
6.1 Routing Loop Attack
The Routing Loop Attack demonstrates how false routing
information generated by a remote host can propagate to
routers and, as a consequence, install wrong routes in the
routing tables.
Consider the network shown in Figure 4. A routing loop
for subnet 30 is created by spoofing routing advertisements.
Note that subnet 30 does not exist in Figure 4. The spoofed
routing advertisements are generated by host mike. The
source IP address of the spoofed routing advertisements is
set to be the address of router hotel. The destination of the
spoofed routing advertisements is router foxtrot. This particular
choice of source and destination addresses is dictated
by the particular topology of the network. Spoofed routing
advertisements with the source address of router golf are not
forwarded by golf. Therefore, the source of the spoofed routing
advertisement cannot be golf. In addition, routers accept
routing information only from their neighbors. Therefore,
the source of the spoofed routing advertisements has to be
hotel.
The spoofed routing advertisements from mike are routed
through golf to reach foxtrot. As a consequence, foxtrot adds
a route for subnet
this route to golf but not to hotel, because it believes that
hotel is the source of the route. After receiving the advertisement
from foxtrot, golf adds a route to subnet 30, through
foxtrot. Then, golf sends a routing advertisement for sub-net
to hotel. When the advertisement is processed by
hotel, a route to subnet through golf is added to hotel 's
routing table. This results in a routing loop. A traceroute
from host india for an address in subnet 30 shows the path
golf-foxtrot-hotel-golf-golf.
6.2 Faulty Route Attack
The Faulty Route Attack demonstrates how a malicious
can divert tra#c by advertising a route with a cost
that is lower that the optimal cost. Consider Figure 4. A
malicious host on the link between golf and foxtrot wants
to access incoming tra#c to subnet 25. To achieve this, the
attacker has to convince foxtrot that the best way to reach
subnet 25 is to route tra#c through golf instead of romeo.
The route associated with romeo has cost 2.
Therefore, the malicious host pretends to be golf and
sends a routing message to foxtrot advertising a route to
subnet 25 at cost 1. As a consequence, foxtrot modifies the
route to subnet 25 in its routing table. The new route goes
through golf instead of romeo.
bravo
alpha
charlie echo oscar
papa quebec
november
foxtrot
golf hotel
juliet
1.1 1.23.13.34.25.2
6.1 6.27.28.2
9.1 9.210.411.1
12.1 12.213.216.214.115.1 15.217.220.1
21.1 22.1AS3 AS423.2
AS2
OSPF
BGP
BGP
BGP
kilo
RIP
romeo
sierra24.2
AS5
25.2 25.1
tango
uniform26.127.228.2
BGP
BGP

Figure

4: Testbed Topology
6.3 Denial-of-Service Attack
In the Denial-of-Service Attack, malicious hosts on links
between foxtrot and golf, foxtrot and hotel and foxtrot and
romeo collaborate to make subnet 10 unreachable from fox-
trot. The malicious host on the link between foxtrot and
golf pretends to be golf and spoofs routing advertisements
to foxtrot advertising unreachability to subnet 10. On receipt
of the spoofed routing advertisements, foxtrot modifies
the route to subnet 10 in its routing table to go through hotel
instead of golf.
Next, the malicious host on the link between foxtrot and
hotel pretends to be hotel and spoofs a routing message to
foxtrot advertising unreachability to subnet 10. On receipt
of the spoofed routing advertisement, foxtrot modifies the
route to subnet 10 in its routing table to go through romeo
instead of hotel.
When romeo too advertises unreachability to subnet 10,
foxtrot removes the route to subnet 10 from its routing table
because it has no other way to reach subnet 10 except
through golf, hotel, or romeo. A traceroute from foxtrot to
returns a Network Unreachable error.
The malicious hosts keep sending spoofed routing updates
at a rate faster than the actual routing updates, thus
preventing the infrastructure from re-establishing correct
routes.
These experiments demonstrate how spoofed routing advertisements
from unauthorized entities can disrupt the distance-vector
routing infrastructure. A malicious entity can
advertise non-existent routes, advertise unreachability when
a route is actually present, or advertise better-than-optimal
routes to divert tra#c.
6.4 Detection
A preliminary experimental evaluation of the intrusion detection
approach is presented here. A detailed evaluation of
the approach is the subject of our current research. The current
objective is to establish a proof-of-concept by detecting
the attacks outlined in Section 6. Two sensors are placed
on the testbed of Figure 4. sensor gf is placed on the link
between routers golf and foxtrot. sensorgm is placed on the
link connecting golf to subnet 10. The sensor configurations
are generated following the algorithm presented in Section 4.
Consider the Routing Loop Attack. Routing advertisements
for subnet spoofed by mike are analyzed by sen-
sorgm on the link connecting golf to subnet 10. sensorgm
detects the source link-level and IP addresses of the routing
advertisements to be incorrect. The spoofed routing advertisements
have the source link-level and IP addresses of hotel
whereas the only possible routing advertisement on that link
should be from router golf. sensor gf also detects the spoofed
routing advertisements because subnet 30, advertised in the
spoofed routing message, does not exist in the domain.
Consider the Faulty Route Attack. sensorgf detects a
routing message that appears to come from router golf advertising
a route to subnet 25 at cost 1. Therefore, sensor gf
searches its configuration for possible paths from golf to sub-net
25 that do not have foxtrot as the first hop. The possible
paths are through either router uniform or router hotel but
none of the paths have cost 1. Therefore, sensor gf infers
that the advertised cost from golf to subnet 25 is an impossible
cost. As a consequence, the routing advertisement is
considered malicious.
Consider the Denial-of-Service attack. When sensor gf
receives a spoofed routing message, which appears to be
coming from router golf, it considers unreachability as a sub-
optimal-cost advertisement. Therefore, sensor gf sends a
message to sensorgm to validate whether the route to subnet
through golf is available or not. sensor gf receives a reply
from sensorgm . As a consequence, sensorgm concludes that
the routing message is malicious.
7. ALGORITHM EVALUATION
The experimental evaluation validates the fact that the
suggested approach can successfully detect malicious routing
advertisements. Nonetheless, our approach has a few
limitations, which are discussed here.
7.1 Computational Complexity
The all-pair/all-path algorithm is used to generate sensor
configurations. It finds all paths from every router to every
other router in the network. This algorithm has an exponential
lower bound. However, the algorithm is suitable
for medium-size sparse topologies. Several real topologies
that run RIP were analyzed. The all-pair/all-path algorithm
converged in acceptable time for all these topologies.
The algorithm should converge in acceptable time for most
topologies running RIP, since these topologies are not very
large or dense.
In addition, the sensor configurations are generated o#-
line. The configurations have to be regenerated if routers
and links are added to the topology. The sensors have to be
brought o#ine during this time. However router crashes or
link failures do not require that the sensor configurations be
regenerated.
7.2 Message Overhead
Another drawback of the approach is the additional tra#c
that is generated to validate optimal and sub-optimal routes.
The sensor tra#c increases as the number of sensors grows
and the required security guarantees become more stringent.
Consider a routing advertisement m from router v i , advertising
a path to subnet sab . If a sensor sensor ij determines
that the cost advertised in m is an impossible cost, sensor ij
can declare the routing advertisement to be malicious without
communicating with any other sensor. Therefore, there
is no tra#c overhead in this case.
determines that the cost advertised in m is an
optimal cost, sensor ij will search its configuration to find
all the optimal paths from router v i to subnet sab . Let the
set of optimal paths from router v i to subnet sab be {p
3 ,    } and the corresponding set of number of sensors
on each path be {n
3 ,    }. Now, the maximum
number of messages that sensor ij will generate to verify
m will be n
1 is the first
optimal path to be verified and p
1 is found to be a valid path
from router v i to subnet sab , sensor ij will only generate n omessages to verify m. If p
1 is the first path to be verified,
noptimal is the
number of messages that sensor ij will generate to verify
an optimal-cost advertisement received from router v i for
subnet sab . Assuming that every sensor replies to every
request, the total overhead is 2 # noptimal messages.
determines that the cost advertised in m is a
sub-optimal cost, sensor ij will search its configuration to
find the set of paths {p
, p a
} from router v i to subnet sab where p
1 is
an optimal path, p s 1
1 is a sub-optimal path, p a
1 is a path
corresponding to the advertised cost. {n
is the corresponding
set of number of sensors on each path. Now, the maximum
number of messages that sensor ij will generate to verify
that all paths from router v i to subnet sab with costs less
than the advertised cost are not available, is n<advertised
. If all
paths with less than advertised cost are found unavailable,
sensor ij will generate nadvertised messages to verify that at
least one path with the advertised cost is available where n a# nadvertised # n a
. In this case, the total
overhead is 2 # n<advertised nadvertised .
For a sub-optimal-cost advertisement, sensor ij might find
an available path to subnet sab from router v i with a cost
that is less than the advertised cost. Let the available path
e 34
e 45s
sensor 12
sensor

Figure

5: Message Overhead Example
be
. Now, the number of messages generated by sensor ij
is n<advertised
since no messages are generated to verify paths with the
advertised cost unless it is determined that all paths with
costs lesser than the advertised cost are unavailable. In this
case, the total overhead is 2 # n<advertised .
Path verification is done for every routing update that
advertises an optimal or sub-optimal cost. Every sensor that
detects a routing advertisement will generate an overhead of
noptimal for every optimal route and 2 # n<advertised
nadvertised for every sub-optimal route in the routing
advertisement. However, the overheads 2 # noptimal and 2 #
n<advertised nadvertised decrease as the proximity of a
sensor with the advertised destination increases.
Routing updates are generated every seconds. If we
assume the verification packet size to be 48 bytes (including
the headers), then every seconds, the verification of one
destination will result in an overhead of 48 # 2 # noptimal or
nadvertised bytes depending on
whether the advertised cost is optimal or sub-optimal.
For example, consider Figure 5. The cost of all links is
equal to 1. When router v4 advertises a route for subnet s45
at cost 1 on link e34 , sensor34 searches its configuration and
determines that an advertisement from v4 for s45 at cost 1
is an optimal-cost advertisement. Since there is only one
path {(v4 )} from v4 to s45 , and sensor45 is the available
sensor on that path, sensor34 sends a verification request
to sensor45 . sensor45 replies with a verification reply to
sensor34 . Since each verification message has a size of 48
bytes, this verification by sensor34 requires 96 bytes.
Next, v3 advertises a route for subnet s45 at cost 2 on link
e23 . Since e23 does not have any sensor on it, no verification
messages are generated. Next, when v2 advertises a route
for s45 at cost 3 on e12 , sensor12 searches its configuration
and determines that an advertisement from v2 for s45 at cost
3 is an optimal-cost advertisement. There is only one path
{(v2 , v3 , v4 )} from v2 to s45 , and two sensors (sensor34 and
sensor45 are available on that path. Therefore, sensor12
sends one message to sensor34 and one message to sensor45 .
Both sensor34 and sensor45 reply back. Therefore, the verification
by sensor12 requires 48 # bytes. The entire
verification process requires 96 bytes. This
is the amount of overhead that will be generated every
seconds.
The overhead due to path-verification might be tolerable
under normal circumstances. Under attack conditions, the
overhead will be the same as discussed above depending on
whether the advertised cost is impossible, optimal or sub-
optimal. A malicious entity might try to use the sensors to
do a denial-of-service attack by sending an excessive amount
of routing updates. However, this will result in the generation
of more routing updates than the sensor's threshold.
Under such a condition, the sensor will appropriately scale
back its path verification mechanism and raise an alert.
However, the overhead due to path-verification may be
unacceptable under conditions where a major part of the
network fails. If a link breaks, then every router that is using
a path that contains the broken link will send a routing up-date
to its neighbors. Every routing update will generate an
overhead as discussed above. Moreover, a link breakage will
result in sub-optimal cost advertisements or unreachability
advertisements, which are also treated as sub-optimal cost
advertisements. The overhead to verify a sub-optimal-cost
advertisement is more than that of verifying an optimal-cost
advertisement.
If a number of links fail, then routes to many destinations
will change or become unavailable, leading to many
routing updates. Consequently, there will be an increase in
the number of sensor verification messages. When links get
reconnected 8 , better paths might be advertised and as a
consequence, again, increase the number of sensor verification
messages.
The message overhead due to the path-verification protocol
can be reduced by reducing the number of sensors in the
network, reducing the frequency of path verification, or verifying
the advertisement selectively. However, all of these
approaches will lead to weaker security guarantees. Our
present work is focused on reducing the overhead due to path
verification without reducing the e#ectiveness of detection.
A possible way of reducing the overhead is by modifying the
path verification algorithm so that it does not try to verify
every path that corresponds to the advertised cost. Instead
of sending a verification message to every sensor on every
path having the advertised cost, the verifying sensor sends
just one message to an IP address in the destination subnet.
This message will traverse a certain path to reach the des-
tination. All sensors present on this path will send back a
reply to the verifying sensor. Based on the replies that are
sent back, the sensor decides whether there exists a path
with the advertised cost that has all the replying sensors on
it or not. This approach should reduce the path verification
overhead significantly.
7.3 Other Limitations
Our approach is not capable of detecting attacks under
certain conditions. Random dropping or modification of
data packets and unauthorized access to routers cannot be
detected. The verifying sensor uses probe packets to verify
that a path with a cost less than the advertised cost is
not available. Since, a malicious router present on the path
between the verifying sensor and the destination can drop
the probe packets, it is not possible to reliably determine
that. Consider there is a malicious router on every available
path, with a cost less than the advertised cost, from
the verifying sensor to the destination. If all these routers
drop probe packets, then the verifying sensor can be made
to believe that all paths with a cost less than the advertised
cost are unavailable. The verifying sensor will then consider
a sub-optimal path to be valid even though better paths are
present.
Attacks cannot be detected on links where sensors are not
present. A malicious entity can advertise false routing information
on links where there are no sensors without being
detected. The false routing information will be accepted
by the routers connected to the link and will be advertised
further. The e#ects of the false routing information will
propagate undetected until it reaches a link where a sensor
is present.
8 Again, we consider only those links that were a part of the topology
that was used to generate the sensor configurations.
The detection scheme might also generate false positives.
Sensors that do not have configurations based on the correct
network topology might generate false alarms. Incorrect
threshold values and timers also may cause false alarms. For
example, when a sensor sends a verification message, it sets
a timer within which it expects to receive a reply from the
other sensor. If the reply gets delayed due to some network
condition, then false alarms may be generated.
False alarms may also be generated when verifying sub-
optimal-cost advertisements. To verify a sub-optimal-cost
advertisement, a sensor first verifies that all optimal-cost
paths are unavailable. If the verifying sensor receives replies
from all the sensors associated with an optimal path, it will
infer that the optimal path is available. However, if sensors
are not placed on every link, there might be a broken link
after the last sensor used for the verification of the optimal
path. As a consequence, the verifying sensor will assume
that the optimal path is available and will generate a false
alarm indicating that the sub-optimal path is malicious.
8. CONCLUSION
This paper presented a novel approach to detect attacks
against the routing infrastructure. The approach uses a set
of sensors that analyze routing tra#c in di#erent locations
within a network. An algorithm to automatically generate
both the detection signatures and the inter-sensor messages
needed to verify the state of the routing infrastructure has
been devised for the case of the RIP distance-vector routing
protocol.
The approach described here has a number of advantages.
First, the implementation of our approach does not require
any modification to routers and routing protocols. Most
current approaches require routers and routing protocols be
changed. The high cost of replacing routers and the risk of
large-scale service disruption due to possible routing protocol
incompatibility has resulted in some inertia in the deployment
of these approaches. Our approach, on the other
hand, is deployable and provides a preliminary solution to
detecting attacks against the routing infrastructure.
Second, the detection process does not use the computational
resources of routers. There might be additional load
on the routers from having to forward the tra#c generated
by sensors. However, this additional load should not be as
much as it would be if a router had to perform public-key
decryption of every routing update that it received, which
is what most current schemes require.
Third, the approach supports the automatic generation of
intrusion detection signatures, which is a human-intensive
and error-prone task.
However, the approach has some drawbacks. First, the
complexity of the o#ine computation that generates sensor
configurations increases as the density of the network
graph increases. Our experience suggests that this will not
be a problem in the case of real-life topologies, but it could
become unmanageable for densely interconnected infrastruc-
tures. In addition, sensors generate additional tra#c to validate
routing advertisements. The amount of additional traffic
generated increases as the required security guarantees
become more stringent. Finally, attacks where subverted
routers modify the contents of data packets or drop packets
selectively, cannot be detected using this approach.
Our future work will be focused on extending the approach
described here to intra-domain link-state protocols
(e.g., OSPF) and inter-domain protocols (e.g., BGP). The
vulnerabilities associated with these protocols have already
been analyzed in our testbed network and a preliminary version
of the algorithm for both the OSPF and BGP protocols
has been devised. To address large-scale networks where
knowledge of the complete topology cannot be assured, we
are working on a model where intelligent decisions can be
made based on partial topology information.

Acknowledgments

We want to thank Prof. Richard Kemmerer for his invaluable
comments.
This research was supported by the Army Research Of-
fice, under agreement DAAD19-01-1-0484 and by the Defense
Advanced Research Projects Agency (DARPA) and
Rome Laboratory, Air Force Materiel Command, USAF,
under agreement number F30602-97-1-0207. The U.S. Government
is authorized to reproduce and distribute reprints
for Governmental purposes notwithstanding any copyright
annotation thereon.
The views and conclusions contained herein are those of
the authors and should not be interpreted as necessarily
representing the o#cial policies or endorsements, either expressed
or implied, of the Army Research O#ce, the Defense
Advanced Research Projects Agency (DARPA), Rome Lab-
oratory, or the U.S. Government.
9.



--R

Intrusion Detection Systems: A Taxomomy and Survey.
Detecting Disruptive Routers: A Distributed Network Monitoring Approach.

Protecting Routing Infrastructures from Denial of Service Using Cooperative Intrusion Detection.
Intrusion Detection for Network Infrastructures.

Reducing the Cost of Security in Link-State Routing
An intrusion-detection system for large-scale networks
Routing in the Internet.
Design and Implementation of a Scalable Intrusion Detection System for the Protection of Network Infrastructure.
Secure Border Gateway Protocol (Secure-BGP) - Real World Performance and Deployment Issues
Secure Border Gateway Protocol (Secure-BGP)
Rip version 2.
Presentation on Security Architecture of the Internet Infrastructure.
Digital Signature Protection of the OSPF Routing Protocol.
Network Layer Protocols with Byzantine Robustness.
Statistical Anomaly Detection for Link-State Routing Protocols
A border gateway protocol 4 (bgp-4)


On the Vulnerablity and Protection of OSPF Routing Protocol.
Design and implementation of a scalable intrusion detection system for the ospf routing protocol
Intrusion Detection for Link-State Routing Protocols

--TR
Routing in the Internet
Protecting routing infrastructures from denial of service using cooperative intrusion detection
Digital signature protection of the OSPF routing protocol
Reducing The Cost Of Security In Link-State Routing
Securing Distance-Vector Routing Protocols
On the Vulnerabilities and Protection of OSPF Routing Protocol
An efficient message authentication scheme for link state routing

--CTR
Marco Rolando , Matteo Rossi , Niccol Sanarico , Dino Mandrioli, A formal approach to sensor placement and configuration in a network intrusion detection system, Proceedings of the 2006 international workshop on Software engineering for secure systems, May 20-21, 2006, Shanghai, China
Yi-an Huang , Wenke Lee, A cooperative intrusion detection system for ad hoc networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia
Antonio Pescap , Giorgio Ventre, Experimental analysis of attacks against intradomain routing protocols, Journal of Computer Security, v.13 n.6, p.877-903, December 2005
routing security;intrusion detection;network topology