idnits 2.17.1 draft-zhang-idr-decoupling-06.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 document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 291: '... A router MAY determine the quaranti...' RFC 2119 keyword, line 372: '...s transitive and SHOULD be passed on t...' RFC 2119 keyword, line 503: '...ment of multiple DAS_PATHs MAY help to...' RFC 2119 keyword, line 509: '... process MAY have been finished, the...' RFC 2119 keyword, line 607: '...rying to cope with SHOULD be prevented...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 25, 2012) is 4138 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'OList' is mentioned on line 193, but not defined == Unused Reference: 'Olist' is defined on line 691, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'PGBGP' -- Possible downref: Non-RFC (?) normative reference: ref. 'SBGP' -- Possible downref: Non-RFC (?) normative reference: ref. 'SoBGP' -- Possible downref: Non-RFC (?) normative reference: ref. 'SPV' -- Possible downref: Non-RFC (?) normative reference: ref. 'BGP4' Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT Mingui Zhang 3 Intended Status: Proposed Standard Huawei 4 Expires: June 28, 2013 Bin Liu 5 Tsinghua University 6 Dacheng Zhang 7 Huawei 8 Beichuan Zhang 9 The University of Arizona 10 December 25, 2012 12 Secure Extension of BGP by Decoupling Path Propagation and Adoption 13 draft-zhang-idr-decoupling-06 15 Abstract 17 This draft proposes a novel mitigation scheme to protect the inter- 18 domain data delivery during false routing announcements. A new path 19 attribute is defined to Decouple propagation of a path and adoption 20 of a path for data forwarding in BGP (DBGP). DBGP does not use 21 suspicious paths for data forwarding, but still propagates them in 22 the routing system to facilitate attack detection. It can extensively 23 protect data delivery from routing announcements of false sub- 24 prefixes, false origins, false nodes and false links, and works well 25 with ongoing attack detection and prevention systems. 27 Status of this Memo 29 This Internet-Draft is submitted to IETF in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF), its areas, and its working groups. Note that 34 other groups may also distribute working documents as 35 Internet-Drafts. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 The list of current Internet-Drafts can be accessed at 43 http://www.ietf.org/1id-abstracts.html 45 The list of Internet-Draft Shadow Directories can be accessed at 46 http://www.ietf.org/shadow.html 48 Acknowledgements 49 The helpful comments of the following are hereby acknowledged, in 50 alphabetic order: Alvaro Retana, Xiaohu Xu. 52 Copyright Notice 54 Copyright (c) 2012 IETF Trust and the persons identified as the 55 document authors. All rights reserved. 57 This document is subject to BCP 78 and the IETF Trust's Legal 58 Provisions Relating to IETF Documents 59 (http://trustee.ietf.org/license-info) in effect on the date of 60 publication of this document. Please review these documents 61 carefully, as they describe your rights and restrictions with respect 62 to this document. Code Components extracted from this document must 63 include Simplified BSD License text as described in Section 4.e of 64 the Trust Legal Provisions and are provided without warranty as 65 described in the Simplified BSD License. 67 Table of Contents 69 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 70 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 4 71 3. False Routing Announcements . . . . . . . . . . . . . . . . . . 4 72 3.1. Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 4 73 3.2. Countermeasures . . . . . . . . . . . . . . . . . . . . . . 5 74 3.2.1. Prevention . . . . . . . . . . . . . . . . . . . . . . 5 75 3.2.2 Detection . . . . . . . . . . . . . . . . . . . . . . . 5 76 3.2.3. Traditional Mitigation . . . . . . . . . . . . . . . . 7 77 3.3. Paradox of Blocking Suspicious Updates and Attack 78 Detection . . . . . . . . . . . . . . . . . . . . . . . . . 7 79 4. DBGP's Mitigation: Decoupling Path Propagation and Adoption . . 8 80 4.1. Quarantine Time . . . . . . . . . . . . . . . . . . . . . . 8 81 5. Protocol Descriptions . . . . . . . . . . . . . . . . . . . . . 9 82 5.1. DAS_PATH Attribute . . . . . . . . . . . . . . . . . . . . 10 83 5.2. Identification of Suspicious Paths . . . . . . . . . . . . 11 84 5.3. Propagating DAS_PATHs with Updates . . . . . . . . . . . . 12 85 5.4. Choosing Alternative Paths . . . . . . . . . . . . . . . . 13 86 5.5 Releasing Quarantined Paths . . . . . . . . . . . . . . . . 14 87 6. Clarifications . . . . . . . . . . . . . . . . . . . . . . . . 14 88 6.1. Individual Historical Database . . . . . . . . . . . . . . 14 89 6.2. Difference from "add-path" . . . . . . . . . . . . . . . . 14 90 6.3 Detection Facilitation . . . . . . . . . . . . . . . . . . . 14 91 6.4. Cooperation with Prevention . . . . . . . . . . . . . . . . 15 92 6.5. Discontiguous Deployment . . . . . . . . . . . . . . . . . 15 93 7. Security Considerations . . . . . . . . . . . . . . . . . . . . 15 94 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 15 95 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 96 9.1. Normative References . . . . . . . . . . . . . . . . . . . 16 97 9.2 Informative References . . . . . . . . . . . . . . . . . . 16 98 Appendix A: Empirical Evaluation . . . . . . . . . . . . . . . . . 17 99 Author's Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 101 1. Introduction 103 False routing announcements cause serious security issues to the 104 inter-domain routing system, which can lead to widespread service 105 disruptions. A special case is prefix hijacking, in which a network 106 announces an IP prefix that belongs to another network. Existing 107 works such as Pretty Good BGP (PGBGP)[PGBGP] block suspicious routing 108 updates to protect data delivery. However, such an approach has the 109 side effect of blocking the view of detection systems at the control 110 plane and data plane. As a result, an attack will not be detected, 111 and operators will not be alerted to take actions to stop the attack. 112 This draft proposes an extension of BGP, to solve this paradox by 113 decoupling path propagation and adoption in BGP. 115 In current BGP, the path a router adopts for data forwarding is the 116 same path being propagated to neighbors. That is why upon receiving a 117 suspicious path, a router has to either accept it (no mitigation but 118 good detection) or reject it (good mitigation but no detection). Our 119 idea is for a router to use trusted paths for data forwarding, but 120 still inform its neighbors about the suspicious path. The suspicious 121 paths will be carried in an optional transitive attribute in BGP 122 updates, while the routers still use trusted paths for data 123 forwarding. This way the data traffic is protected while false 124 routing announcements are being propagated to detection systems. 126 2. Terminology 128 DBGP: Decoupling path propagation and adoption in BGP 130 3. False Routing Announcements 132 3.1. Problem 134 False routing announcements can be caused by either inadvertent mis- 135 configurations or malicious attacks. For the ease of exposition, we 136 use "attacker" to refer to the network (or Autonomous System, AS) 137 that makes the false routing announcements regardless of the 138 intention. Based on which part of the routing path is false, such 139 announcements can be classified into five types, each of which has 140 different severity: 142 o Prefix origin: The attacker originates someone else's prefix. 143 Depending on where a network is in the Internet topology, some 144 will choose paths leading to the true origin and some will 145 choose paths leading to the false origin. 147 o Intermediate node: The attacker does not forge the prefix or 148 its origin, but inserts itself into the path as an intermediate 149 AS. Similar to the case of false origin, some networks will 150 choose the correct paths and some the false paths. But usually 151 fewer networks will choose the false path since it is longer 152 than that of false origin attack. 154 o Intermediate link: The attacker forges a new link to bypass 155 some of the ASes to get a shorter path. The shortened path is 156 expected to attract more networks' traffic. 158 o Sub-prefix: The attacker originates a sub-prefix of someone 159 else's prefix. Due to the longest match in routing lookup, a 160 false sub-prefix will win over the original prefix. Thus, all 161 traffic destined to the sub-prefix range will be forwarded to 162 the attacker. 164 o Super-prefix: Theoretically the attacker can also announce a 165 false super-prefix, but that will not attract any traffic 166 unless part of the prefix range is unused by the real owner, in 167 which case it is equivalent to announcing a false origin of the 168 unused prefix range. 170 3.2. Countermeasures 172 The current strategies proposed for the problem of false 173 announcements fall in three categories: prevention, detection and 174 mitigation. 176 3.2.1. Prevention 178 Prevention schemes (e.g., [SBGP], [SoBGP], and [SPV]) use 179 cryptographic mechanisms to protect the routing updates and let 180 routers reject any forged announcement. Unfortunately no prevention 181 scheme has seen much deployment on the Internet due to the lack of 182 incentives for those first movers. Since crypto-based schemes add 183 significant computational load to routers and require upgrade on 184 software or hardware, individual ISPs need to see immediate benefits 185 to justify the deployment. On the current Internet, however, the 186 first mover's routing announcements will be accepted by other 187 networks without authentication, and adding authentication does not 188 bring any immediate benefit. 190 3.2.2 Detection 192 The representative detection systems proposed in recent years include 193 [Cyclops], [PHAS], [MyASN], [IAR], [iSPY], [NWatch], [OList], and 194 [LWeight]. Such systems are designed to detect false routing by 195 examining routing updates, probing data paths, cross-checking with 196 registry databases, or a combination of these techniques. Once a 197 false routing case is detected, the owner of the prefix will be 198 notified, and it is expected that the owner will take actions to 199 resolve the problem, which, in today's Internet, usually involves 200 contacting the offending network or its upstream provider to stop the 201 false routing announcements. This process of detection, notification 202 and resolution takes time, ranging from an hour to a day in some past 203 incidents and varying from network to network [NWatch][RIPE]. In the 204 meantime, the damage to data traffic has already been made and 205 malicious attackers may have already achieved their objectives. 207 3.2.3. Traditional Mitigation 209 A mitigation schemes attempts to protect the data traffic while an 210 attack is going on. The common approach is to somehow identify 211 abnormal routing updates and block them. As proposed in [PGBGP] and 212 [PGBGP++], a router can examine the content of incoming updates. If 213 an AS path contains unexpected prefix origin or links, it will be 214 suppressed from propagating for a period of time to wait for the 215 network operator's validation. The length of the time is configurable 216 by the network operators. Instead, an alternative path (via trusted 217 prefix origin and links) will be employed for data delivery in the 218 suppression period. After this period, if the path is not proved to 219 be illegal, the router will adopt and announce this new path. PGBGP 220 gives operators certain reaction time to resolve potential false 221 announcements while protecting data delivery in the meantime. When a 222 real attack is detected and resolved, the corresponding false 223 announcement will be withdrawn from the routing system, whereas 224 legitimate announcement will stay in the routing system and 225 eventually be accepted. 227 But blocking false routing announcements can get in the way of 228 detection systems. For instance, on September 22, 2008, a Russian ISP 229 AS8997 hijacked a large number of prefixes as it leaked an entire 230 table [ASN8997]. However, since the upstream ISP of AS8997 blocked 231 the routing updates, detection systems such as MyASN and IAR did not 232 pick up this incident. The attack mainly affected ISPs and users 233 within Russia but largely went unnoticed by prefix owners. 235 Each existing solution has its drawbacks, and none is sufficiently 236 effective by itself. In future, there may be several different 237 solutions deployed on the Internet at the same time, complementary to 238 each other, forming a multi-line defense to protect routing and data 239 delivery before, during, and after attacks. 241 3.3. Paradox of Blocking Suspicious Updates and Attack Detection 243 It has been realized that a mitigation mechanism and a detection 244 system that complement each other well can be integrated into an 245 effective routing defense solution. For instance, the mitigation 246 mechanism can help the detection system to confine the damage caused 247 by an attack, as the affected data traffic may be vulnerable for 248 hours before the attack can be actually detected by the detection 249 mechanism and be eventually stopped. Also, the mitigation mechanism 250 can also obtain benefit from the detection system because a 251 mitigation mechanism normally cannot identity false routing 252 information accurately with its limited knowledge, resource and time. 253 The output from the detection system can be used to correct the many 254 false positives generated by the mitigation mechanism and also inform 255 the prefix owner to resolve the attack. 257 However, there is a dilemma: the mitigation mechanism tries to render 258 the attack ineffective while the detection system needs the attack to 259 be effective in order to detect it. 261 4. DBGP's Mitigation: Decoupling Path Propagation and Adoption 263 The suspicious paths are serially blocked hop by hop for validation 264 in traditional mitigation schemes, which gets in the way of detection 265 systems. In order to solve this dilemma, this document proposes a 266 solution which decouples path propagation and path adoption. The 267 basic idea of this solution is to extend BGP's update message with a 268 new optional transitive path attribute so that a router can inform 269 its neighbor routers about the suspicious path and meanwhile the 270 router uses another trusted path for data forwarding. In order to 271 achieve this, a new BGP attribute, DAS_PATH, is defined in Section 5. 272 Compared to the traditional mitigation schemes, the propagation of 273 suspicious paths through DAS_PATHs in DBGP enables the parallel 274 validation, which accelerates the adoption process of suspected 275 legitimate paths (the false positive). 277 4.1. Quarantine Time 279 Based on operating experiences, a false routing announcement can be 280 detected and corrected in a certain period (e.g., one day) after it 281 is launched, and so an announcement will be trusted if it is not 282 withdrawn in a pre-defined period. Therefore, in mitigation schemes, 283 when a new path is identified as a suspicious one, it will be 284 quarantined (or blocked) from being used for a period of time, which 285 is called the quarantine time and noted as T_q. If a new path has 286 stayed in a router's Adj-RIBs-In for more than T_q, it will be 287 trusted by this router. If this path is the most preferred from the 288 Adj-RIBs-In, the router will use this path for data delivery and 289 announce this path to its neighbors. 291 A router MAY determine the quarantine time itself. Assume there are 292 two routers, R1 and R2. R1 is the downstream of R2, and the 293 quarantine time of R1 and R2 is T1 and T2 respectively. The 294 suspicious path is PATH at R1. There are two possibilities. 296 o T1 is shorter than T2. When T1 expires, PATH becomes trusted by 297 R1 and R1 begins to use it for data delivery. R1 will announce 298 R1-PATH as a legitimate AS path to R2. However, at this time, 299 the path R1-PATH is still being quarantined by R2. 301 o T1 is longer than T2. When T2 expires, R1-PATH becomes trusted 302 by R2. However, R2 cannot use this path for data delivery as R1 303 has not announced R1-PATH as an AS path. It will be cached in 304 the Adj-RIBs-In until the downstream router R1 has announced it 305 as an AS path when T1 expires. 307 5. Protocol Descriptions 309 Take Figure 5.1 for example. A, B, C, and O are DBGP routers residing 310 in different ASes, , X is the attacker and p is the prefix of 311 interest. Before the attack, the preferred path for traffic is ABCO. 312 Here, we use the notation "R1R2...Rn-p" to denote the AS path which 313 is destined to prefix "p" via routers R1, R2, ..., Rn. When X makes a 314 false announcement of X-p to B, B will regard this new path as 315 suspicious because it would divert traffic to an AS(X) that 316 previously was not on the data path (BCO). B will store the 317 suspicious path in its Adj-RIBs-In (The routing tables of an AS 318 router is comprised of three sub-tables: Adj-RIBs-In, Loc-RIB and 319 Adj-RIBs-Out [BGP4]), but keep using the existing path in its Loc-RIB 320 for data forwarding. At the same time, B re-announces its path (BCO) 321 in an update message to A, and encapsulates the new, suspicious path 322 (BX) as an optional transitive attribute which is defined in Section 323 5.1. After receiving the update message, router A learns this 324 suspicious path, stores it, and propagates it further to its 325 neighbors using the optional attribute in the same way. Therefore, 326 the suspicious path is propagated to the Internet while not adopted 327 for data forwarding. This approach enable the detection systems to 328 intercept the suspicious path and notify the prefix owner to take 329 actions. Once the attack is stopped, the false announcements will be 330 withdrawn from the routing system, i.e., deleted or replaced in the 331 Adj-RIBs-In of the involved routers. However, a router realizes that 332 the quarantine time has been expired and the suspicious path is still 333 in the Adj-RIBs-In, the router regards the path as a legitimate one. 334 Hence the DBGP router will install the path in its Loc-RIB for data 335 forwarding and re-announce the path using the regular ASPATH 336 attribute in the update message. For example, if BX-p has been 337 validated as legitimate, B will announce it to A as its AS_PATH. The 338 rest of this section will discuss the design details in new BGP 339 attribute definition, identifying suspicious paths, choosing 340 alternative paths for data forwarding, propagating the paths, and 341 releasing quarantined paths. 343 [X]->p 344 ^ 345 | 346 [A]->[B]->[C]->[O]-p 348 Figure 5.1: Attack Example 1 350 The rest of this section will discuss the design details in the 351 definition of the new DAS_PATH Attribute, identifying suspicious 352 paths, choosing alternative paths for data forwarding, propagating 353 the paths, and releasing quarantined paths. 355 5.1. DAS_PATH Attribute 357 +-+-+-+-+-+-+-+-+ 358 | Attribute Type| (2 bytes) 359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 360 | Attribute Length | (1 or 2 bytes) 361 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 362 | Attribute Value | (variable length) 363 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 365 Figure 5.2: The DAS_PATH Attribute 367 DAS_PATH (Decoupled AS_PATH) is defined as a new optional transitive 368 Path Attribute (Figure 5.2) to be included in BGP's UPDATE messages. 370 The first bit of the Attribute Type is set (1), therefore the 371 attribute is optional. The second bit of Attribute Type is set (1), 372 therefore the attribute is transitive and SHOULD be passed on to 373 other BGP peers. The third and fourth bits are Partial bit and 374 Extended Length bit respectively, which has already been defined in 375 [BGP4]. The Attribute Type code is assigned by the IANA (Internet 376 Assigned Numbers Authority). The definition of Attribute Length is 377 the same as that in [BGP4]. 379 The Attribute Value is composed of a sequence of DAS path segments. 380 Each DAS path segment is encoded as a triple . 383 The path segment type is a 1-octet field with the following two 384 allowable values: 386 Value Segment Type 387 1 DAS_SET unordered set of ASs a route in the 388 UPDATE message has traversed 389 2 DAS_SEQUENCE ordered set of ASs a route in the 390 UPDATE message has traversed 392 The path segment length field is 1-octet long field and contains the 393 number of ASs in the path segment value field. 395 The path segment value field contains one or more AS numbers, each 396 encoded as a 2-octets long field. 398 When a DAS_PATH is propagated across the network, the operations on 399 DAS_PATH follows the well-known AS_PATH attribute only that DAS_PATH 400 is non-mandatory. If a router which does not deploy DBGP receives the 401 update messages containing DAS_PATH attribute, i.e., does not 402 understand this attribute, it will just pass it on to the next 403 router. If its downstream router is a DBGP router, it will be able to 404 pick up the information from this attribute and continue DBGP 405 operations. Therefore DBGP can be incrementally deployed over the 406 Internet. 408 5.2. Identification of Suspicious Paths 410 For a given prefix p, a path is trusted if it has been staying in the 411 Adj-RIBs-In continuously for the required quarantine time, T_q. All 412 the nodes, links, and origins that appear in trusted paths are 413 trusted components, and the set of them is denoted by trusted(p). 414 This set of trusted components is derived from current contents of 415 all Adj-RIBs-In without using a database to store historical 416 information like PGBGP does. Nodes, links, and origins that do not 417 belong to trusted(p) are said to be suspicious components for this 418 particular prefix p. A new path is suspicious if it contains any 419 suspicious component for its prefix. However, not all suspicious 420 paths need to be explicitly quarantined. DBGP quarantines paths that 421 satisfy the following condition: 423 o A new path is quarantined if and only if it is suspicious, more 424 preferred than other alternative paths, and contains an AS that 425 is not in the current data forwarding path. 427 If the new path is not better than alternative paths, it will not be 428 able to divert any traffic. One may suggest that the attacker can 429 first announce a less preferred path so that DBGP routers will take 430 it as a backup path without suspicion, and then make the primary path 431 fail to trick the router to use the false backup path. But in this 432 case, if the attacker has the control of the primary path, it can 433 already get the traffic without doing this. If the attacker does not 434 have control of the primary path, it will not know when the primary 435 path may fail and which backup path the router will choose, thus the 436 attack will not be effective. 438 If the new path does not introduce any new AS on the data path, it is 439 not quarantined since it does not divert any traffic. In Figure 5.3, 440 when X launches an attack by announcing X-p, this path is not 441 quarantined by B since B already sends its traffic to X. B will 442 accept this path and announces it to A. Assuming ABX-p is more 443 preferred than ACO-p, A will quarantine ABX-p since this new path 444 would divert A's traffic to a new place, AS X, and X is a suspicious 445 origin to A. 447 To reduce the potential false positives in quarantining paths, we 448 introduce an optimization rule. If the current best path is replaced 449 by a suspicious path (i.e., the same neighbor that sent the best path 450 previously sends another path to replace it), then the current best 451 path is cached for a short time period. This rule is used to 452 accommodate some unstable prefixes, which may get announced and 453 withdrawn or oscillate between two paths frequently. With this rule, 454 quick re-announcement of a path will not be treated as suspicious. 455 Previous measurement work has shown that (1) most prefixes are 456 stable, and only a small number of prefixes are very unstable; (2) 457 the most popular prefixes are stable; and (3) the most preferred 458 paths are being used by routers for most of the time 459 [BGPpop][Stable][BGPHA]. Therefore, DBGP's criterion for suspicious 460 paths will not generate excessive false positives in reality. The 461 majority of the rest prefixes is only suspicious infrequently. 463 +---------------+ 464 | | 465 | v 466 [A]->[B]->[X]->[C]->[O]-p 467 | 468 p 470 Figure 5.3: Attack Example 2 472 5.3. Propagating DAS_PATHs with Updates 474 DBGP uses the new BGP attribute, DAS_PATH, to carry a suspicious path 475 in an update. In certain cases DBGP router may need to select a 476 DAS_PATH from multiple ones to announce. For example, in Figure 5.4, 477 assume C does not deploy DBGP and accepts the false announcement of 478 X-p. When B receives BCX-p, B quarantines this new path and switches 479 to its backup BDO-p. The update from B to A will have BDO as the 480 AS_PATH, and BCX as the DAS_PATH attribute. However, since BDO is 481 suspicious to A as well, A will quarantine BDO and switch to AEFO. 482 Thus the update from A can contain either ABCX or ABDO. A router's 483 neighbors may simultaneously send updates containing the DAS_PATH to 484 it, which also makes the router have multiple DAS_PATHs to choose. 485 There are two possible choices for DBGP implementations. 487 1. Dominate a router to select the best DAS_PATH from the 488 multiple ones to announce, which is similar to the traditional 489 AS_PATH selection process. 491 2. Encapsulate all the DAS_PATH attributes in tandem and sort 492 them by their priorities. The priorities are determined 493 according to the rules used in the AS_PATH selection process. 495 The first rule works well due to the following two facts. First, 496 during attacks, the best DAS_PATH is most likely the bogus path 497 aiming to attract data traffic. Second, during false positives, the 498 best DAS_PATH will most likely become the best AS_PATH when the 499 quarantine time ends. 501 The second rule allows an AS router to provide more information to 502 its upstream, which is helpful for diagnose and correctness of 503 attacks. Moreover, the announcement of multiple DAS_PATHs MAY help to 504 reduce the convergence time. Take Figure 5.4 for example, A announces 505 two DAS_PATHs, i.e., ABDO-p and ABCX-p, to its upstream node, says U. 506 When U receives the additional DAS_APTH: ABDO-p, it will begin the 507 validation process of this suspicious path. After A determines that 508 BDO-p is legitimate and installs it to its Loc-RIB, the validation 509 process MAY have been finished, therefore U can immediately start to 510 use ABDO-p. 512 For the second rule, the number of DAS_PATHs in an update depends on 513 the topology and policy of the network. Generally speaking, the 514 number of DAS_PATHs in an update increases with the AS hop count of 515 the AS_PATH. However, given AS paths are usually 4 to 5 hops and 516 rarely goes to more than 10 hops, we do not expect the announcement 517 of multiple DAS_PATHs will make DBGP message too large. 519 [X]->p 520 ^ 521 | 522 [A]->[B]->[C]->[O]-p 523 | | ^ 524 | | /| 525 | +-->[D]-+ | 526 | | 527 +------->[E]->[F] 529 Figure 5.4: Attack Example 3 531 5.4. Choosing Alternative Paths 533 When a new path is the most preferred but suspicious, DBGP routers 534 will use an alternative path for data delivery. The question is which 535 alternative path to be chosen. First, if the existing path that is 536 being used for data forwarding is still the best, then the router can 537 stick to that path without any changes. Second, if the existing path 538 in use will have been replaced by the suspicious path, then the 539 router needs to pick an alternative. For example, in Figure 5.4, 540 suppose C does not deploy DBGP and blindly accepts the false 541 announcement X-p. B's existing path BCO-p will be replaced by a 542 suspicious path BCX-p, therefore B needs to temporarily switch to a 543 backup path BDO-p from its Adj-RIBs-In. Third, if there is no 544 alternative path or all alternative paths are labeled as suspicious, 545 then the router err on data delivery by adopting a suspicious path to 546 forward packets. 548 5.5 Releasing Quarantined Paths 550 If the quarantined paths are false announcements, it is likely that 551 within T_q, the attack will be stopped and these paths being 552 withdrawn from the routing system. In this case, there is no explicit 553 release of the quarantined path. Just the upstream router will send 554 an update with empty DAS_PATH attribute. If T_q has passed and the 555 quarantined path is still in the Adj-RIBs-In, then it is more likely 556 that this is a legitimate path. The router will treat the path as a 557 regular path and make it go through the path selection process. If 558 the path turns out to be the most preferred one, it will be used for 559 data forwarding and trigger routing updates to neighbor routers. 561 6. Clarifications 563 6.1. Individual Historical Database 565 When DBGP is implemented in an AS router, the router does not have to 566 purchase additional memory to store the trusted paths as that in 567 [PGBGP]. By default, a DBGP router uses the simple rules defined in 568 Section 5.2 to filter suspected components of an AS path based on the 569 information stored in its Adj-RIBs-In. All a router need to do is to 570 add a new column to its Adj-RIBs-In to record the elapse time after 571 an AS path entered a Adj-RIB-In. 573 6.2. Difference from "add-path" 575 DBGP solution is different from the ongoing work of advertising 576 multiple BGP paths in [add-path] where AS routers are also allowed to 577 export multiple AS paths in one update. All advertised AS paths are 578 available to upstream AS routers in [add-path]. Despite that DBGP 579 allows multiple paths to be advertised in one update, except the AS 580 path, all the other paths are actually unavailable. In other words, 581 these paths only remain in Adj-RIBs-In of the AS router. They will 582 not be put into either the Loc-RIB or Adj-RIBs-Out. 584 6.3 Detection Facilitation 586 Traditional mitigation mechanisms block the propagation of suspicious 587 paths, which undermines the effectiveness of detection systems. DBGP 588 is proposed to address this shortage. In DBGP, the data traffic is 589 protected while the false routing announcements are spread out to be 590 monitored by detection systems. If the first rule in Section 5.4 is 591 adopted, the capacity of propagating suspicious paths in DBGP is the 592 same as that in BGP. If the second rule is adopted, this capacity is 593 enhanced by DBGP instead. 595 6.4. Cooperation with Prevention 597 As a mitigation scheme, DBGP routers validate AS paths based on the 598 limited information stored in local Adj-RIBs-In. This would cause 599 some legitimate paths to be identified as suspicious and blocked from 600 being used for data delivery (high false positive). If a down stream 601 router would like their paths be adopted quickly rather than be 602 suspected, it can include certificates in the update messages. For 603 example, if AS routers adopt the solution in [pfx-va], the AS number 604 claiming to originate an address prefix will be validated by the 605 prefix holder. The authorized origin will not be suspected by DBGP 606 routers. Further, if the validation can cover the whole AS path, all 607 kinds of attacks that DBGP is trying to cope with SHOULD be prevented 608 in the first place. In all, the deployment of DBGP actually creates 609 the incentive for deploying prevention systems. 611 6.5. Discontiguous Deployment 613 DBGP does NOT require contiguous deployment in order to be effective. 614 The key purpose of DBGP is to recognize and propagate the suspicious 615 path segment via the DAS-PATH. When the AS router at the far side 616 obtain the UPDATE message with the DAS-PATH missing some intermediate 617 AS numbers, it doesn't matter. This AS router can still use this path 618 segment for detection/validation purpose. Let's use the example in 619 Figure 5.1 to explain. The starter AS router of the DAS-PATH must 620 have deployed DBGP. In this figure, "B" is the starter. "B" can 621 recognize "X" as suspicious node and propagates this via DAS-PATH to 622 "A". We suppose "A" has not deployed DBGP. When A's upstream AS 623 router receives A's update message, it will find that the AS-PATH is 624 "ABCO" and the DAS-PATH is "BX". The detection system just uses "BX" 625 as the input. 627 It is not recommended to complement the DAS-PATH according to the 628 primary path contained in the same UDPATE message. One will easily 629 find this kind of trick is in vain. 631 7. Security Considerations 633 The entire document is about security consideration. 635 8. IANA Considerations 637 The attribute type code of DAS_PATH should be assigned by the IANA, 638 which identifies the attribute uniquely from all others. 640 9. References 642 9.1. Normative References 644 [PGBGP] J. Karlin, S. Forrest, and J. Rexford, "Pretty Good BGP: 645 Improving BGP by Cautiously Adopting Routes," in 646 Proceedings of IEEE ICNP, 2006. 648 [SBGP] S. Kent, C. Lynn, and K. Seo, "Secure Border Gateway 649 Protocol (SBGP)," IEEE Journal on Selected Areas in 650 Communications, vol. 18, no. 4, pp. 582-592, 2000. 652 [SoBGP] J. Ng, "Extensions to BGP to Support Secure Origin BGP," 653 April 2004, ftp://ftp-eng.cisco.com/sobgp/drafts/draft- 654 ng-sobgp-bgp-extensions-02.txt. 656 [SPV] Y.-C. Hu, A. Perrig, and M. Sirbu, "SPV: Secure Path 657 Vector Routing for Securing BGP," in Proceedings of ACM 658 SIGCOMM, 2004. 660 [BGP4] J. W. Stewart, BGP4: Inter-Domain Routing in the 661 Internet. Boston,MA, USA: Addison-Wesley Longman 662 Publishing Co., Inc., 1998. 664 [pfx-va] P. Mohapatra, J. Scudder, D. Ward, R. Bush, R. Austein, 665 "BGP Prefix Origin Validation", draft-ietf-sidr-pfx- 666 validate-01, working in progress. 668 9.2 Informative References 670 [Cyclops] Y.-J. Chi, R. Olivera, and L. Zhang, "Cyclops: the as- 671 level connectivity observatory," SIGCOMM Comput. Commun. 672 Rev., vol. 38, no. 5, pp. 5-16, 2008. 674 [PHAS] M. Lad, D. Massey, D. Pei, B. Zhang, and L. Zhang, "PHAS: 675 A Prefix Hijack Alert System," in 15th USENIX Security 676 Symposium, 2006, pp.153-166. 678 [MyASN] "RIPE myASN System," http://www.ris.ripe.net/myasn.html. 680 [IAR] [Online]. Available: http://iar.cs.unm.edu/ 682 [iSPY] Z. Zhang, Y. Zhang, Y. C. Hu, Z. M. Mao, and R. Bush, 683 "iSPY: Detecting IP Prefix Hijacking on My Own," in 684 Proceedings of ACM SIGCOMM, 2008. 686 [NWatch] G. Siganos and M. Faloutsos, "Neighborhood Watch for 687 Internet Routing: Can We Improve the Robustness of 688 Internet Routing Today?" in Proceedings of IEEE INFOCOM, 689 2007. 691 [Olist] X. Zhao, D. Pei, L. Wang, D. Massey, A. Mankin, S. Wu, 692 and L. Zhang,"Dection of Invalid Routing Announcement in 693 the Internet," in Proceedings of the IEEE DSN, June 2002. 695 [LWeight] C. Zheng, L. Ji, D. Pei, J. Wang, and P. Francis, "A 696 Light-weight Distributed Scheme for Detecting IP Prefix 697 Hijacks in Real-time," in Proceedings of ACM SIGCOMM, 698 2007. 700 [RIPE] [Online]. Available: http://www.ripe.net/news/study- 701 youtubehijacking.html 703 [ASN8997] "Prefix hijack by ASN 8997." [Online]. Available: 704 http://www.merit.edu/mail.archives/nanog/2008- 705 09/msg00704.html 707 [BGPpop] J. Rexford, J. Wang, Z. Xiao, and Y. Zhang, "BGP Routing 708 Stability of Popular Destinations," in Proceedings of ACM 709 IMC 2002, pp. 197-202. 711 [Stable] K. Butler, P. McDaniel, and W. Aiello, "Optimizing BGP 712 Security by Exploiting Path Stability," in Proceedings of 713 ACM CCS, Alexandria, VA, United States, 2006, pp. 298- 714 310. 716 [BGPHA] R. V. Oliveira, R. Izhak-Ratzin, B. Zhang, and L. Zhang, 717 "Measurement of Highly Active Prefixes in BGP," in 718 Proceedings of IEEE Globecom,2005. 720 Appendix A: Empirical Evaluation 722 The following aspects of DBGP are tested on the SSFNet-2.0 simulation 723 platform which has implemented BGP4. 724 o The ability to counter different types of attacks 725 o The ability to rectify the false positives 726 o The memory and message overhead 727 The evaluation proves that DBGP can be used to mitigate all types of 728 attacks. Compared with previous mitigation approaches [PGBGP], it 729 reduces the delay of legitimate announcements significantly, only 730 incurs a small amount of messages and memory overhead. 732 Author's Addresses 734 Mingui Zhang 735 Huawei Technologies Co.,Ltd 736 Huawei Building, No.156 Beiqing Rd. 737 Z-park ,Shi-Chuang-Ke-Ji-Shi-Fan-Yuan,Hai-Dian District, 738 Beijing 100095 P.R. China 740 Email: zhangmingui@huawei.com 742 Bin Liu 743 Tsinghua University 744 East Main Building RM9-416 745 Tsinghua University, Hai-Dian District, 746 Beijing, 100084 P.R. China 748 Email: lmyujie@gmail.com 750 Dacheng Zhang 751 Huawei Technologies Co.,Ltd 752 Huawei Building, No.156 Beiqing Rd. 753 Z-park ,Shi-Chuang-Ke-Ji-Shi-Fan-Yuan,Hai-Dian District, 754 Beijing 100095 P.R. China 756 Email: zhangdacheng@huawei.com 758 Beichuan Zhang 759 University of Arizona 760 Computer Science Department, 761 The University of Arizona 762 Tucson, AZ 85721 U.S.A. 764 Email: bzhang@arizona.edu