idnits 2.17.1 draft-bi-savi-pisl-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([RFC2119]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet has text resembling RFC 2119 boilerplate text. == The document seems to contain a disclaimer for pre-RFC5378 work, but was first submitted on or after 10 November 2008. The disclaimer is usually necessary only for documents that revise or obsolete older RFCs, and that take significant amounts of text from those RFCs. If you can contact all authors of the source material and they are willing to grant the BCP78 rights to the IETF Trust, you can and should remove the disclaimer. Otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (May 29, 2012) is 4350 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'RFC 5210' is mentioned on line 106, but not defined == Unused Reference: 'RFC2328' is defined on line 418, but no explicit reference was found in the text == Unused Reference: 'RFC5210' is defined on line 420, but no explicit reference was found in the text Summary: 1 error (**), 0 flaws (~~), 6 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 SAVI J. Bi 3 Internet-Draft B. Zhang 4 Intended status: Informational B. Liu 5 Expires: November 30, 2012 Tsinghua Univ. 6 F. Baker 7 Cisco 8 May 29, 2012 10 Prevent IP Spoofing Based On Link State Database (pisl) 11 draft-bi-savi-pisl-00 13 Abstract 15 The Internet is suffering from severe DoS and DDoS attacks, and IP 16 spoofing is one common used method to do DoS and DDoS attacks. IP 17 spoofing refers to that attackers send packets with forged source IP 18 addresses. In this memo, we propose one new approach of preventing 19 IP spoofing, which we name PISL. The PISL-enabled router generates 20 the incoming table for source addresses using link state database, 21 which exists in two most widely used intra-domain protocols: OSPF 22 and IS-IS. In this memo, we only describe PISL in the OSPF 23 environment. The PISL-enabled router determines that a packet is 24 spoofed if the packet arrives at an invalid incoming interface. PISL 25 only uses the existing information and does not impose new control 26 messages, so it is easy to be deployed. We have conducted simple 27 simulation, which shows the high effectiveness of PISL: even if PISL 28 is only deployed in 10% of all OSPF routers in a network, 80%~99% of 29 spoofing cases in the network can be detected. 31 Requirements 33 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL 34 NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 35 this document are to be interpreted as described in RFC 2119 36 [RFC2119]. 38 Status of this Memo 40 This Internet-Draft is submitted in full conformance with the 41 provisions of BCP 78 and BCP 79. 43 Internet-Drafts are working documents of the Internet Engineering 44 Task Force (IETF). Note that other groups may also distribute 45 working documents as Internet-Drafts. The list of current Internet- 46 Drafts is at http://datatracker.ietf.org/drafts/current/. 48 Internet-Drafts are draft documents valid for a maximum of six months 49 and may be updated, replaced, or obsoleted by other documents at any 50 time. It is inappropriate to use Internet-Drafts as reference 51 material or to cite them other than as "work in progress." 53 This Internet-Draft will expire on November 30, 2012. 55 Copyright Notice 57 Copyright (c) 2012 IETF Trust and the persons identified as the 58 document authors. All rights reserved. 60 This document is subject to BCP 78 and the IETF Trust's Legal 61 Provisions Relating to IETF Documents 62 (http://trustee.ietf.org/license-info) in effect on the date of 63 publication of this document. Please review these documents 64 carefully, as they describe your rights and restrictions with respect 65 to this document. Code Components extracted from this document must 66 include Simplified BSD License text as described in Section 4.e of 67 the Trust Legal Provisions and are provided without warranty as 68 described in the Simplified BSD License. 70 This document may contain material from IETF Documents or IETF 71 Contributions published or made publicly available before November 72 10, 2008. The person(s) controlling the copyright in some of this 73 material may not have granted the IETF Trust the right to allow 74 modifications of such material outside the IETF Standards Process. 75 Without obtaining an adequate license from the person(s) controlling 76 the copyright in such materials, this document may not be modified 77 outside the IETF Standards Process, and derivative works of it may 78 not be created outside the IETF Standards Process, except to format 79 it for publication as an RFC or to translate it into languages other 80 than English. 82 Table of Contents 84 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 85 2. Calculating the incoming table under the directed graph 86 model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 87 3. Calculating the incoming table under the real network . . . . 6 88 4. Simulation Results . . . . . . . . . . . . . . . . . . . . . . 8 89 5. Discussions . . . . . . . . . . . . . . . . . . . . . . . . . 9 90 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 91 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 92 8. Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . 10 93 9. Change Log . . . . . . . . . . . . . . . . . . . . . . . . . . 10 94 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 95 10.1. Normative References . . . . . . . . . . . . . . . . . . 10 96 10.2. Informative References . . . . . . . . . . . . . . . . . 11 97 Appendix A. The Reverse Dijkstra Algorithm . . . . . . . . . . . 11 98 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 100 1. Introduction 102 The Internet is suffering from severe DoS and DDoS attacks, and IP 103 spoofing is one common used method to do DoS and DDoS attacks. IP 104 spoofing refers to that attackers send packets with forged source IP 105 addresses. To solve the IP spoofing problem, the source address 106 validation architecture (SAVA) [RFC 5210] was put forward. According 107 to SAVA, three levels of source address validation are ought to be 108 needed, and they are: the local subnet level, the intra-AS level and 109 the inter-AS level. In this memo, we propose an anti-spoofing method 110 based on link state database, which we name PISL. PISL is an 111 intra-AS source address validation mechanism. PISL only uses the 112 existing link state database (LSDB), which can be used to calculate 113 the incoming table for prefixes. The PISL-enabled router determines 114 that a packet is spoofed if the packet arrives at an invalid incoming 115 interface. The key point of generating the incoming table for source 116 addresses is to calculate the shortest paths to them. We use section 117 2 and section 3 to address this problem. 119 In section 2, we consider how to generate the incoming table under 120 the directed graph model. It is the foundation of section 3. LSDB 121 can be abstracted in to a directed graph. As is well-known, dijkstra 122 algorithm can be used to calculate the shortest paths from one single 123 source node to all the other nodes, i.e., the single-source shortest 124 problem. And calculating the shortest paths from all the other nodes 125 to one single destination node are in actual the single-destination 126 shortest path problem. It has been proved by [4] that the single- 127 destination shortest path problem can be reduced to the single-source 128 shortest path problem by reversing the direction of each edge. To 129 avoid the extra memory cost for the reverse graph, we develop the 130 reverse dijkstra algorithm as described in section 2 and the 131 appendix. 133 In section 3, we consider how to generate the incoming table under 134 the real OSPF network. In the real OSPF network, there are maybe 135 multiple areas. LSDB of a router only has the topology of its own 136 area, but do not have topologies of other areas. The link metrics 137 are maybe asymmetric, so the incoming directions of inter-area 138 prefixes and eternal-AS prefixes cannot be calculated out, but it is 139 sure that inter-area prefixes must traverse area-border routers 140 (ABRs), and external-AS prefixes must traverse area-border routers or 141 AS-boundary routers (ASBRs). The fraction of area-border and AS- 142 boundary routers is small in general. To avoid the false positive, 143 we consider the incoming directions of all the ABRs as legal incoming 144 directions for inter-area prefixes. Similarly, we consider the 145 incoming directions of all the ABRs and ASBRs as legal incoming 146 directions for external-AS prefixes. Though that will impose some 147 extent of false negative, the imposed false negative ratio is low, as 148 shown in the simulation section. 150 [SAVO] proposed another algorithm to calculate the incoming table 151 based on LSDB. However, the computational complexity of the 152 algorithm in [SAVO] is O(n^3) at the worst case while the 153 computational complexity of PISL is only O(n^2) at the worst case, 154 where n is the number of routers in LSDB. The reason that why the 155 algorithm in [SAVO] has higher computational complexity is that the 156 algorithm in [SAVO] runs the dijkstra algorithm on every node while 157 PISL runs the reverse dijkstra algorithm only on the node of itself.. 159 2. Calculating the incoming table under the directed graph model 161 In this section, we will introduce how to calculate the incoming 162 directions of all the other nodes in the directed graph with 163 nonnegative weights. The incoming direction can be represented by 164 the node that the destination node is next to on the shortest path. 165 In the next section, we will introduce how to calculate the incoming 166 interfaces for prefixes based on the link state database of OSPF. 167 The algorithm of this section is the foundation of the next section. 169 The key point of calculating the incoming directions of all the other 170 nodes to itself is to calculate the shortest paths from all the other 171 nodes to itself, i.e., the single-destination shortest path problem. 172 As is well-known, dijkstra algorithm can be used to calculate the 173 shortest paths from one single source node to all the other nodes, 174 i.e., the single-source shortest problem. 176 It has been proven by [4] that the single-destination shortest path 177 problem can be reduced to the single-source shortest path problem by 178 reversing the direction of each edge. However, that needs extra 179 memory cost for the reverse graph. To avoid the memory cost, we can 180 immediately modify the dijkstra algorithm to calculate all the equal- 181 cost incoming directions from all the other nodes to the destination 182 node using the original graph. The modified dijkstra algorithm is 183 called by us the reverse dijkstra algorithm. The Reverse dijkstra 184 algorithm also uses the greedy strategy, and chooses nodes one by one 185 with increasing shortest paths. That is the same as the dijkstra 186 algorithm. There are three steps in each iteration for the reverse 187 dijkstra algorithm as follows. 189 Step 1: Choosing. The Reverse dijkstra algorithm chooses the 190 nearest node that has not been chosen. 192 Calculating. The Reverse dijkstra algorithm calculates the equal- 193 cost incoming directions for the chosen node. The set of equal-cost 194 incoming directions is the union set of directions of nodes that are 195 the equal-cost next hops of the chosen node. 197 Step3: Relaxing. The Reverse dijkstra algorithm relaxes the reverse 198 edges of the chosen node while the dijkstra algorithm relaxes the 199 forwarding edges of the chosen node. 201 The reverse dijkstra algorithm still has the computational complexity 202 of O(n^2), where n is the number of nodes. The pseudo code of the 203 reverse dijkstra algorithm is as shown in the appendix. 205 3. Calculating the incoming table under the real network 207 In the last section, we have introduced the reverse dijkstra 208 algorithm, which can be used to calculate the incoming directions 209 from all the other nodes to one single destination. That is the 210 foundation of this section. In this section, we will introduce how 211 to calculate the incoming interfaces for prefixes using link state 212 database of the OSPF protocol. The other link state protocols, such 213 as IS-IS , are similar. In this memo, we only consider the case of 214 OSPF. The link state database can be used to construct a topology, 215 which can be abstracted into a directed graph with nonnegative 216 weights, where the reverse dijkstra algorithm can be applied. In 217 subsection A, we will analyze the possible incoming interfaces for 218 different types of prefixes. In subsection B we will introduce the 219 detailed scheme of calculating incoming interfaces for prefixes. 221 3.1. The analysis of feasible incoming interfaces for different types 222 of prefixes 224 In the OSPF network, there are three types of prefixes that are ought 225 to be differently treated. They are intra-area prefixes, inter-area 226 prefixes and external-AS prefixes. Their feasible incoming 227 interfaces are analyzed as follows. 229 3.1.1. Intra-area prefixes 231 Intra-area prefixes refer to prefixes extracted from router-LSAs and 232 network-LSAs, i.e., prefixes originated from the local area. Routes 233 know the whole intra-area topology (adjacencies and bidirectional 234 weights), so incoming interfaces of intra-area prefixes can be 235 calculated by the reverse dijkstra algorithm, which has been 236 introduced in the previous section. 238 3.1.2. Inter-area prefixes 240 Inter-area prefixes refer to prefixes extracted from type3-summary- 241 LSAs, i.e., prefixes originated from other OSPF areas. The 242 unidirectional cost can only be used to calculate the next hops to 243 inter-area prefixes, and cannot be used to calculate the incoming 244 interfaces of the inter-area prefixes. Fortunately, it is sure that 245 inter-area prefixes must traverse ABRs to the intra area, so we can 246 consider the incoming interfaces of all the intra-area ABRs to be the 247 incoming interfaces of inter-area prefixes. The incoming interfaces 248 of intra-area ABRs can be calculated by reverse dijkstra algorithm 249 based on the intra-area topology knowledge. 251 3.1.3. External-AS prefixes 253 External-AS prefixes refer to prefixes extracted from AS-external- 254 LSAs. One type of external-AS prefixes are the real prefixes from 255 external ASes, the other type of external-AS prefixes are the 256 redistributed prefixes from other intra-domain routing protocols. 257 For external-AS prefixes, they are similar with inter-area prefixes, 258 are also learned from summary routes, and routers cannot calculate 259 the strict incoming interfaces for them. We also give loose incoming 260 interfaces for AS-external prefixes. For prefixes from external 261 ASes, they must traverse ASBRs or ABRs to itself. So we can consider 262 the incoming interfaces of all the ASBRs and ABRs in the intra area 263 to be the incoming interfaces of prefixes from external ASes. For 264 the redistributed prefixes in the intra-domain, they will not 265 traverse real AS-boundary routers to itself. However, the two types 266 of external-AS prefixes are advertised by the same AS-external LSAs, 267 we cannot distinguish them. So we treat redistributed prefixes as 268 the same as prefixes from external ASes. 270 3.2. The scheme of calculating incoming interfaces for prefixes using 271 LSAs 273 There are five steps to generate the incoming table for prefixes as 274 follows. 276 3.2.1. Step 1: Constructing the topology view 278 Router-LSA and network-LSA describe the local link state topology of 279 the corresponding router or the transit network. Router-LSA and 280 network LSA flood in the whole intra area. So the whole intra-area 281 link state topology can be constructed, and the intra-area topology 282 is a bidirectional graph. Type3-summary-LSA, type4-summary-LSA and 283 AS-external- LSA advertise prefixes or ASBRs outside the area. The 284 three kinds of LSA only carry the unidirectional weights to 285 corresponding prefixes or ASBRs, but do not carry the weights of the 286 opposite direction. 288 3.2.2. Step 2: Identifying all the ABRs and ASBRs in the area 290 There are two bits, bit B and Bit E, in the router-LSA. If bit B=1, 291 then it indicates that the corresponding router is ABR, otherwise, 292 the corresponding router is not ABR. Similarly, if bit E =1, then it 293 indicates that the corresponding router is ASBR, otherwise, the 294 corresponding router is not ASBR. 296 3.2.3. Step 3: Calculating the incoming interfaces for the intra-area 297 routers and transit networks 299 Having the knowledge of the bidirectional link state topology of the 300 whole intra-area, the reverse dijkstra algorithm can be applied to 301 calculate the incoming interfaces for the intra-area routers and 302 transit networks. The calculated incoming interfaces of the intra- 303 area routers will be used in the next step. 305 3.2.4. Step 4: Calculating the incoming interfaces for prefixes 307 a) The intra-area stub prefixes are described in router-LSAs. The 308 incoming interfaces of stub prefixes are the incoming interfaces of 309 the corresponding routers, i.e., the routers that originate the 310 corresponding router-LSAs. 312 b) The inter-area prefixes are described in type3-summay-LSAs. As 313 analyzed in the last subsection, the incoming interfaces of inter- 314 area prefixes are the incoming interfaces of all the ABRs. 316 c) The left prefixes are AS-external prefixes, which are described in 317 AS-external-LSAs. As analyzed in the last subsection, the incoming 318 interfaces of AS-external prefixes are the incoming interfaces of all 319 the ABRs and ASBRs in the area. So all the AS-external prefixes have 320 the same incoming interfaces. To reduce the size of incoming table, 321 the AS-external prefixes can be aggregated into the default prefix 322 0.0.0.0/0. And the incoming interfaces of prefix 0.0.0.0/0 are the 323 incoming interfaces of all the ABRs and ASBRs in the area. 325 3.2.5. Step 5: Loading the incoming table 327 Loading the incoming table with the calculated incoming interfaces of 328 the intra-are stub prefixes, intra-area transit network prefixes, 329 inter-area prefixes and the default prefix 0.0.0.0/0. The incoming 330 table is used to determine whether packets are spoofed. 332 4. Simulation Results 334 We collected the topologies marked with ISP map from the project of 335 rocketfuel. We assume that routers in the same AS run the OSPF 336 protocol with only one single area. All the bidirectional weights 337 are 1. We draw two conclusions as follows. (a) If PISL is only 338 deployed in 10% of routers, 80%~99% of spoofed cases can be detected. 339 (b) The false negative ratio due to loose incoming interfaces of AS- 340 external prefixes is approximately equal to the percentage of ABRs 341 and ASBRs. Similarly, the false negative ratio due to loose incoming 342 interfaces of inter-area prefixes is approximately equal to the 343 percentage of ABRs. 345 5. Discussions 347 5.1. Deployment 349 The router only needs to add an algorithm function and does not need 350 extra communication cost if it wants to support PISL. So PISL is 351 easy to be deployed. In addition, if PISL is only deployed partly in 352 the network, it can prevent the source address spoofing in some 353 extent. The more deployed routers, the higher effectiveness PISL can 354 perform. Moreover, the router that has deployed the PISL can prevent 355 spoofing cases from other routers. A deployment limitation for PISL 356 is that it can only be deployed in the OSPF-enabled routers at 357 present. We will extend PISL to work in other link state protocols, 358 such as IS-IS. 360 5.2. Static Route 362 The static route is used in two scenarios. In one scenario, the 363 static route is configured to realize the interconnectivity between 364 two networks. In order to realize the interconnectivity, the routes 365 of the other network will be distributed into the OSPF network, or an 366 OSPF router announces the address space that covers the address space 367 of the other network. In that scenario, the static route does not 368 conflict with the OSPF routing. PISL can deal with it in the normal 369 way. In the other scenario, the static route is inconsistent with 370 the OSPF routing. That is dangerous. The topology and routing 371 information should be well known in order to avoid the routing loop. 372 In that situation, the static route is dangerous, and is used rarely. 373 Once the inconsistent static route is used, PISL can be configured 374 manually to solve it. 376 5.3. Fast Reroute 378 Fast reroute refers to redirecting traffic to other feasible next 379 hops after a using link is down and before the network is converged. 380 So fast reroute traffic may be filtered by PISL. The fast reroute 381 packets filtered by PISL can be regarded as packet loss not due to 382 congestion. After the network is converged, the filtered fast 383 reroute packets can be retrieved by the Transmission Control 384 Protocol. Coping with fast reroute carefully, PISL can be configured 385 to the alarming mode. Spoofed packets detected are forwarded 386 normally, but alarms are sent to the network managers, who determine 387 whether those spoofed packets are filtered. 389 6. IANA Considerations 391 This memo includes no request to IANA. 393 7. Security Considerations 395 The memo does not introduce new security problem. The security 396 problems of this demo are the same as the security problems of the 397 link-state-based protocols. The most important security problem of 398 this demo is the facticity of LSDB. There is need to enhance the 399 trustiness of LSAs between routers. 401 8. Acknowledgment 403 This document was generated using the xml2rfc tool. 405 Thanks Guang Yao and Joel M. Halpern for their comments 407 9. Change Log 409 Initial version: Tuesday May 29, 2012 411 10. References 413 10.1. Normative References 415 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 416 Requirement Levels", RFC 2119, March 1997. 418 [RFC2328] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 420 [RFC5210] Wu, J., Bi, J., Li, X., Ren, G., Xu, K., and M. Williams, 421 "A Source Address Validation Architecture (SAVA) Testbed 422 and Deployment Experience", RFC 5210, June 2008. 424 10.2. Informative References 426 [4] Thomas, H., Charles, E., Ronald, L., and S. Clifford, 427 "Introduction to Algorithms", 2001. 429 [SAVO] Tao, Z., Gong, Z., Lu, Z., Wang, B., Wang, H., Li, S., 430 Liu, Y., Bi, J., and J. Wu, "OSPFv3-based Intra-Domain 431 Source-Address Validation Implementation", November 2011. 433 Appendix A. The Reverse Dijkstra Algorithm 435 Variables 436 t:the single-destination node 437 D[i]:the cost of the shortest path from node i to node t 438 L[i]:the set of incoming directions of node i to node t. 439 There are maybe multiple directions for a node in the situation 440 of multiple equal-cost shortest paths, so L[i] is a set. 441 The incoming direction is represented by the last hop of the 442 shortest path (the destination hop is not included). 443 e[i][j]:the cost (or weight) from node i to node j. 444 rAdj[i]:the set of nodes that have reverse edges to node i. 445 S:the set of nodes whose shortest paths to destination t have 446 been found 447 Q:the set of nodes that has not been included in S. 449 Initialization 450 D[t]=0 451 D[other nodes]= infinite 452 L[t]={NULL} 453 L[other nodes]={} 454 S={t} 455 Q={all the nodes excluding t} 457 Iteration 458 While(Q!=empty) 459 { 460 u=i,where D[i]is minimum among the nodes in Q. 461 for each vertex v in S 462 { 463 if(u==t) break; 464 if(e[u][v]+d[v]==d[u]) 465 { 466 if(L[v]=={NULL}) 467 { 468 L[u]=L[u]U{u} 469 } 470 else 471 { 472 L[u]=L[u] U L[v]; 473 } 474 } 475 } 476 for each vertex v in radj[u] 477 { 478 if(e[v][u]+d[u]<d[v]) 479 { 480 d[v]=e[v][u]+d[u]; 481 } 483 } 484 Q=Q-{u}; 485 S=S U{u} 486 } 488 Authors' Addresses 490 Jun Bi 491 Tsinghua University 492 Network Research Center, Tsinghua University 493 Beijing 100084 494 China 496 Email: junbi@tsinghua.edu.cn 498 Baobao Zhang 499 Tsinghua University 500 Computer Science, Tsinghua University 501 Beijing 100084 502 China 504 Email: zbb@netarchlab.tsinghua.edu.cn 506 Bingyang Liu 507 Tsinghua University 508 Computer Science, Tsinghua University 509 Beijing 100084 510 China 512 Email: liuby@netarchlab.tsinghua.edu.cn 514 Fred Baker 515 Cisco Systems 516 Santa Barbara, CA 93117 517 United States 519 Email: fred@cisco.com