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]