Internet DRAFT - draft-bi-savi-pisl
draft-bi-savi-pisl
SAVI J. Bi
Internet-Draft B. Zhang
Intended status: Informational B. Liu
Expires: November 30, 2012 Tsinghua Univ.
F. Baker
Cisco
May 29, 2012
Prevent IP Spoofing Based On Link State Database (pisl)
draft-bi-savi-pisl-00
Abstract
The Internet is suffering from severe DoS and DDoS attacks, and IP
spoofing is one common used method to do DoS and DDoS attacks. IP
spoofing refers to that attackers send packets with forged source IP
addresses. In this memo, we propose one new approach of preventing
IP spoofing, which we name PISL. The PISL-enabled router generates
the incoming table for source addresses using link state database,
which exists in two most widely used intra-domain protocols: OSPF
and IS-IS. In this memo, we only describe PISL in the OSPF
environment. The PISL-enabled router determines that a packet is
spoofed if the packet arrives at an invalid incoming interface. PISL
only uses the existing information and does not impose new control
messages, so it is easy to be deployed. We have conducted simple
simulation, which shows the high effectiveness of PISL: even if PISL
is only deployed in 10% of all OSPF routers in a network, 80%~99% of
spoofing cases in the network can be detected.
Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC 2119
[RFC2119].
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
Bi, et al. Expires November 30, 2012 [Page 1]
Internet-Draft PISL May 2012
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 30, 2012.
Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
Bi, et al. Expires November 30, 2012 [Page 2]
Internet-Draft PISL May 2012
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Calculating the incoming table under the directed graph
model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Calculating the incoming table under the real network . . . . 6
4. Simulation Results . . . . . . . . . . . . . . . . . . . . . . 8
5. Discussions . . . . . . . . . . . . . . . . . . . . . . . . . 9
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
7. Security Considerations . . . . . . . . . . . . . . . . . . . 10
8. Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . 10
9. Change Log . . . . . . . . . . . . . . . . . . . . . . . . . . 10
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
10.1. Normative References . . . . . . . . . . . . . . . . . . 10
10.2. Informative References . . . . . . . . . . . . . . . . . 11
Appendix A. The Reverse Dijkstra Algorithm . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
Bi, et al. Expires November 30, 2012 [Page 3]
Internet-Draft PISL May 2012
1. Introduction
The Internet is suffering from severe DoS and DDoS attacks, and IP
spoofing is one common used method to do DoS and DDoS attacks. IP
spoofing refers to that attackers send packets with forged source IP
addresses. To solve the IP spoofing problem, the source address
validation architecture (SAVA) [RFC 5210] was put forward. According
to SAVA, three levels of source address validation are ought to be
needed, and they are: the local subnet level, the intra-AS level and
the inter-AS level. In this memo, we propose an anti-spoofing method
based on link state database, which we name PISL. PISL is an
intra-AS source address validation mechanism. PISL only uses the
existing link state database (LSDB), which can be used to calculate
the incoming table for prefixes. The PISL-enabled router determines
that a packet is spoofed if the packet arrives at an invalid incoming
interface. The key point of generating the incoming table for source
addresses is to calculate the shortest paths to them. We use section
2 and section 3 to address this problem.
In section 2, we consider how to generate the incoming table under
the directed graph model. It is the foundation of section 3. LSDB
can be abstracted in to a directed graph. As is well-known, dijkstra
algorithm can be used to calculate the shortest paths from one single
source node to all the other nodes, i.e., the single-source shortest
problem. And calculating the shortest paths from all the other nodes
to one single destination node are in actual the single-destination
shortest path problem. It has been proved by [4] that the single-
destination shortest path problem can be reduced to the single-source
shortest path problem by reversing the direction of each edge. To
avoid the extra memory cost for the reverse graph, we develop the
reverse dijkstra algorithm as described in section 2 and the
appendix.
In section 3, we consider how to generate the incoming table under
the real OSPF network. In the real OSPF network, there are maybe
multiple areas. LSDB of a router only has the topology of its own
area, but do not have topologies of other areas. The link metrics
are maybe asymmetric, so the incoming directions of inter-area
prefixes and eternal-AS prefixes cannot be calculated out, but it is
sure that inter-area prefixes must traverse area-border routers
(ABRs), and external-AS prefixes must traverse area-border routers or
AS-boundary routers (ASBRs). The fraction of area-border and AS-
boundary routers is small in general. To avoid the false positive,
we consider the incoming directions of all the ABRs as legal incoming
directions for inter-area prefixes. Similarly, we consider the
incoming directions of all the ABRs and ASBRs as legal incoming
directions for external-AS prefixes. Though that will impose some
extent of false negative, the imposed false negative ratio is low, as
Bi, et al. Expires November 30, 2012 [Page 4]
Internet-Draft PISL May 2012
shown in the simulation section.
[SAVO] proposed another algorithm to calculate the incoming table
based on LSDB. However, the computational complexity of the
algorithm in [SAVO] is O(n^3) at the worst case while the
computational complexity of PISL is only O(n^2) at the worst case,
where n is the number of routers in LSDB. The reason that why the
algorithm in [SAVO] has higher computational complexity is that the
algorithm in [SAVO] runs the dijkstra algorithm on every node while
PISL runs the reverse dijkstra algorithm only on the node of itself..
2. Calculating the incoming table under the directed graph model
In this section, we will introduce how to calculate the incoming
directions of all the other nodes in the directed graph with
nonnegative weights. The incoming direction can be represented by
the node that the destination node is next to on the shortest path.
In the next section, we will introduce how to calculate the incoming
interfaces for prefixes based on the link state database of OSPF.
The algorithm of this section is the foundation of the next section.
The key point of calculating the incoming directions of all the other
nodes to itself is to calculate the shortest paths from all the other
nodes to itself, i.e., the single-destination shortest path problem.
As is well-known, dijkstra algorithm can be used to calculate the
shortest paths from one single source node to all the other nodes,
i.e., the single-source shortest problem.
It has been proven by [4] that the single-destination shortest path
problem can be reduced to the single-source shortest path problem by
reversing the direction of each edge. However, that needs extra
memory cost for the reverse graph. To avoid the memory cost, we can
immediately modify the dijkstra algorithm to calculate all the equal-
cost incoming directions from all the other nodes to the destination
node using the original graph. The modified dijkstra algorithm is
called by us the reverse dijkstra algorithm. The Reverse dijkstra
algorithm also uses the greedy strategy, and chooses nodes one by one
with increasing shortest paths. That is the same as the dijkstra
algorithm. There are three steps in each iteration for the reverse
dijkstra algorithm as follows.
Step 1: Choosing. The Reverse dijkstra algorithm chooses the
nearest node that has not been chosen.
Calculating. The Reverse dijkstra algorithm calculates the equal-
cost incoming directions for the chosen node. The set of equal-cost
incoming directions is the union set of directions of nodes that are
Bi, et al. Expires November 30, 2012 [Page 5]
Internet-Draft PISL May 2012
the equal-cost next hops of the chosen node.
Step3: Relaxing. The Reverse dijkstra algorithm relaxes the reverse
edges of the chosen node while the dijkstra algorithm relaxes the
forwarding edges of the chosen node.
The reverse dijkstra algorithm still has the computational complexity
of O(n^2), where n is the number of nodes. The pseudo code of the
reverse dijkstra algorithm is as shown in the appendix.
3. Calculating the incoming table under the real network
In the last section, we have introduced the reverse dijkstra
algorithm, which can be used to calculate the incoming directions
from all the other nodes to one single destination. That is the
foundation of this section. In this section, we will introduce how
to calculate the incoming interfaces for prefixes using link state
database of the OSPF protocol. The other link state protocols, such
as IS-IS , are similar. In this memo, we only consider the case of
OSPF. The link state database can be used to construct a topology,
which can be abstracted into a directed graph with nonnegative
weights, where the reverse dijkstra algorithm can be applied. In
subsection A, we will analyze the possible incoming interfaces for
different types of prefixes. In subsection B we will introduce the
detailed scheme of calculating incoming interfaces for prefixes.
3.1. The analysis of feasible incoming interfaces for different types
of prefixes
In the OSPF network, there are three types of prefixes that are ought
to be differently treated. They are intra-area prefixes, inter-area
prefixes and external-AS prefixes. Their feasible incoming
interfaces are analyzed as follows.
3.1.1. Intra-area prefixes
Intra-area prefixes refer to prefixes extracted from router-LSAs and
network-LSAs, i.e., prefixes originated from the local area. Routes
know the whole intra-area topology (adjacencies and bidirectional
weights), so incoming interfaces of intra-area prefixes can be
calculated by the reverse dijkstra algorithm, which has been
introduced in the previous section.
3.1.2. Inter-area prefixes
Inter-area prefixes refer to prefixes extracted from type3-summary-
LSAs, i.e., prefixes originated from other OSPF areas. The
Bi, et al. Expires November 30, 2012 [Page 6]
Internet-Draft PISL May 2012
unidirectional cost can only be used to calculate the next hops to
inter-area prefixes, and cannot be used to calculate the incoming
interfaces of the inter-area prefixes. Fortunately, it is sure that
inter-area prefixes must traverse ABRs to the intra area, so we can
consider the incoming interfaces of all the intra-area ABRs to be the
incoming interfaces of inter-area prefixes. The incoming interfaces
of intra-area ABRs can be calculated by reverse dijkstra algorithm
based on the intra-area topology knowledge.
3.1.3. External-AS prefixes
External-AS prefixes refer to prefixes extracted from AS-external-
LSAs. One type of external-AS prefixes are the real prefixes from
external ASes, the other type of external-AS prefixes are the
redistributed prefixes from other intra-domain routing protocols.
For external-AS prefixes, they are similar with inter-area prefixes,
are also learned from summary routes, and routers cannot calculate
the strict incoming interfaces for them. We also give loose incoming
interfaces for AS-external prefixes. For prefixes from external
ASes, they must traverse ASBRs or ABRs to itself. So we can consider
the incoming interfaces of all the ASBRs and ABRs in the intra area
to be the incoming interfaces of prefixes from external ASes. For
the redistributed prefixes in the intra-domain, they will not
traverse real AS-boundary routers to itself. However, the two types
of external-AS prefixes are advertised by the same AS-external LSAs,
we cannot distinguish them. So we treat redistributed prefixes as
the same as prefixes from external ASes.
3.2. The scheme of calculating incoming interfaces for prefixes using
LSAs
There are five steps to generate the incoming table for prefixes as
follows.
3.2.1. Step 1: Constructing the topology view
Router-LSA and network-LSA describe the local link state topology of
the corresponding router or the transit network. Router-LSA and
network LSA flood in the whole intra area. So the whole intra-area
link state topology can be constructed, and the intra-area topology
is a bidirectional graph. Type3-summary-LSA, type4-summary-LSA and
AS-external- LSA advertise prefixes or ASBRs outside the area. The
three kinds of LSA only carry the unidirectional weights to
corresponding prefixes or ASBRs, but do not carry the weights of the
opposite direction.
Bi, et al. Expires November 30, 2012 [Page 7]
Internet-Draft PISL May 2012
3.2.2. Step 2: Identifying all the ABRs and ASBRs in the area
There are two bits, bit B and Bit E, in the router-LSA. If bit B=1,
then it indicates that the corresponding router is ABR, otherwise,
the corresponding router is not ABR. Similarly, if bit E =1, then it
indicates that the corresponding router is ASBR, otherwise, the
corresponding router is not ASBR.
3.2.3. Step 3: Calculating the incoming interfaces for the intra-area
routers and transit networks
Having the knowledge of the bidirectional link state topology of the
whole intra-area, the reverse dijkstra algorithm can be applied to
calculate the incoming interfaces for the intra-area routers and
transit networks. The calculated incoming interfaces of the intra-
area routers will be used in the next step.
3.2.4. Step 4: Calculating the incoming interfaces for prefixes
a) The intra-area stub prefixes are described in router-LSAs. The
incoming interfaces of stub prefixes are the incoming interfaces of
the corresponding routers, i.e., the routers that originate the
corresponding router-LSAs.
b) The inter-area prefixes are described in type3-summay-LSAs. As
analyzed in the last subsection, the incoming interfaces of inter-
area prefixes are the incoming interfaces of all the ABRs.
c) The left prefixes are AS-external prefixes, which are described in
AS-external-LSAs. As analyzed in the last subsection, the incoming
interfaces of AS-external prefixes are the incoming interfaces of all
the ABRs and ASBRs in the area. So all the AS-external prefixes have
the same incoming interfaces. To reduce the size of incoming table,
the AS-external prefixes can be aggregated into the default prefix
0.0.0.0/0. And the incoming interfaces of prefix 0.0.0.0/0 are the
incoming interfaces of all the ABRs and ASBRs in the area.
3.2.5. Step 5: Loading the incoming table
Loading the incoming table with the calculated incoming interfaces of
the intra-are stub prefixes, intra-area transit network prefixes,
inter-area prefixes and the default prefix 0.0.0.0/0. The incoming
table is used to determine whether packets are spoofed.
4. Simulation Results
We collected the topologies marked with ISP map from the project of
Bi, et al. Expires November 30, 2012 [Page 8]
Internet-Draft PISL May 2012
rocketfuel. We assume that routers in the same AS run the OSPF
protocol with only one single area. All the bidirectional weights
are 1. We draw two conclusions as follows. (a) If PISL is only
deployed in 10% of routers, 80%~99% of spoofed cases can be detected.
(b) The false negative ratio due to loose incoming interfaces of AS-
external prefixes is approximately equal to the percentage of ABRs
and ASBRs. Similarly, the false negative ratio due to loose incoming
interfaces of inter-area prefixes is approximately equal to the
percentage of ABRs.
5. Discussions
5.1. Deployment
The router only needs to add an algorithm function and does not need
extra communication cost if it wants to support PISL. So PISL is
easy to be deployed. In addition, if PISL is only deployed partly in
the network, it can prevent the source address spoofing in some
extent. The more deployed routers, the higher effectiveness PISL can
perform. Moreover, the router that has deployed the PISL can prevent
spoofing cases from other routers. A deployment limitation for PISL
is that it can only be deployed in the OSPF-enabled routers at
present. We will extend PISL to work in other link state protocols,
such as IS-IS.
5.2. Static Route
The static route is used in two scenarios. In one scenario, the
static route is configured to realize the interconnectivity between
two networks. In order to realize the interconnectivity, the routes
of the other network will be distributed into the OSPF network, or an
OSPF router announces the address space that covers the address space
of the other network. In that scenario, the static route does not
conflict with the OSPF routing. PISL can deal with it in the normal
way. In the other scenario, the static route is inconsistent with
the OSPF routing. That is dangerous. The topology and routing
information should be well known in order to avoid the routing loop.
In that situation, the static route is dangerous, and is used rarely.
Once the inconsistent static route is used, PISL can be configured
manually to solve it.
5.3. Fast Reroute
Fast reroute refers to redirecting traffic to other feasible next
hops after a using link is down and before the network is converged.
So fast reroute traffic may be filtered by PISL. The fast reroute
packets filtered by PISL can be regarded as packet loss not due to
Bi, et al. Expires November 30, 2012 [Page 9]
Internet-Draft PISL May 2012
congestion. After the network is converged, the filtered fast
reroute packets can be retrieved by the Transmission Control
Protocol. Coping with fast reroute carefully, PISL can be configured
to the alarming mode. Spoofed packets detected are forwarded
normally, but alarms are sent to the network managers, who determine
whether those spoofed packets are filtered.
6. IANA Considerations
This memo includes no request to IANA.
7. Security Considerations
The memo does not introduce new security problem. The security
problems of this demo are the same as the security problems of the
link-state-based protocols. The most important security problem of
this demo is the facticity of LSDB. There is need to enhance the
trustiness of LSAs between routers.
8. Acknowledgment
This document was generated using the xml2rfc tool.
Thanks Guang Yao and Joel M. Halpern for their comments
9. Change Log
Initial version: Tuesday May 29, 2012
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997.
[RFC2328] Moy, J., "OSPF Version 2", RFC 2328, April 1998.
[RFC5210] Wu, J., Bi, J., Li, X., Ren, G., Xu, K., and M. Williams,
"A Source Address Validation Architecture (SAVA) Testbed
and Deployment Experience", RFC 5210, June 2008.
Bi, et al. Expires November 30, 2012 [Page 10]
Internet-Draft PISL May 2012
10.2. Informative References
[4] Thomas, H., Charles, E., Ronald, L., and S. Clifford,
"Introduction to Algorithms", 2001.
[SAVO] Tao, Z., Gong, Z., Lu, Z., Wang, B., Wang, H., Li, S.,
Liu, Y., Bi, J., and J. Wu, "OSPFv3-based Intra-Domain
Source-Address Validation Implementation", November 2011.
Appendix A. The Reverse Dijkstra Algorithm
Variables
t:the single-destination node
D[i]:the cost of the shortest path from node i to node t
L[i]:the set of incoming directions of node i to node t.
There are maybe multiple directions for a node in the situation
of multiple equal-cost shortest paths, so L[i] is a set.
The incoming direction is represented by the last hop of the
shortest path (the destination hop is not included).
e[i][j]:the cost (or weight) from node i to node j.
rAdj[i]:the set of nodes that have reverse edges to node i.
S:the set of nodes whose shortest paths to destination t have
been found
Q:the set of nodes that has not been included in S.
Bi, et al. Expires November 30, 2012 [Page 11]
Internet-Draft PISL May 2012
Initialization
D[t]=0
D[other nodes]= infinite
L[t]={NULL}
L[other nodes]={}
S={t}
Q={all the nodes excluding t}
Iteration
While(Q!=empty)
{
u=i,where D[i]is minimum among the nodes in Q.
for each vertex v in S
{
if(u==t) break;
if(e[u][v]+d[v]==d[u])
{
if(L[v]=={NULL})
{
L[u]=L[u]U{u}
}
else
{
L[u]=L[u] U L[v];
}
}
}
for each vertex v in radj[u]
{
if(e[v][u]+d[u]<d[v])
{
d[v]=e[v][u]+d[u];
}
}
Q=Q-{u};
S=S U{u}
}
Bi, et al. Expires November 30, 2012 [Page 12]
Internet-Draft PISL May 2012
Authors' Addresses
Jun Bi
Tsinghua University
Network Research Center, Tsinghua University
Beijing 100084
China
Email: junbi@tsinghua.edu.cn
Baobao Zhang
Tsinghua University
Computer Science, Tsinghua University
Beijing 100084
China
Email: zbb@netarchlab.tsinghua.edu.cn
Bingyang Liu
Tsinghua University
Computer Science, Tsinghua University
Beijing 100084
China
Email: liuby@netarchlab.tsinghua.edu.cn
Fred Baker
Cisco Systems
Santa Barbara, CA 93117
United States
Email: fred@cisco.com
Bi, et al. Expires November 30, 2012 [Page 13]