INTERNET-DRAFT                                              Mingui Zhang
Intended Status: Proposed Standard                                Huawei
Expires: June 28, 2013                                           Bin Liu
                                                     Tsinghua University
                                                           Dacheng Zhang
                                                                  Huawei
                                                          Beichuan Zhang
                                               The University of Arizona
                                                       December 25, 2012


  Secure Extension of BGP by Decoupling Path Propagation and Adoption
                     draft-zhang-idr-decoupling-06

Abstract

   This draft proposes a novel mitigation scheme to protect the inter-
   domain data delivery during false routing announcements. A new path
   attribute is defined to Decouple propagation of a path and adoption
   of a path for data forwarding in BGP (DBGP). DBGP does not use
   suspicious paths for data forwarding, but still propagates them in
   the routing system to facilitate attack detection. It can extensively
   protect data delivery from routing announcements of false sub-
   prefixes, false origins, false nodes and false links, and works well
   with ongoing attack detection and prevention systems.

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as
   Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   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."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

Acknowledgements



Mingui Zhang, et al      Expires June 28, 2013                  [Page 1]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   The helpful comments of the following are hereby acknowledged, in
   alphabetic order: Alvaro Retana, Xiaohu Xu.

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.


Table of Contents

   1. Introduction  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3. False Routing Announcements . . . . . . . . . . . . . . . . . .  4
     3.1. Problem . . . . . . . . . . . . . . . . . . . . . . . . . .  4
     3.2. Countermeasures . . . . . . . . . . . . . . . . . . . . . .  5
       3.2.1. Prevention  . . . . . . . . . . . . . . . . . . . . . .  5
       3.2.2 Detection  . . . . . . . . . . . . . . . . . . . . . . .  5
       3.2.3. Traditional Mitigation  . . . . . . . . . . . . . . . .  7
     3.3. Paradox of Blocking Suspicious Updates and Attack
          Detection . . . . . . . . . . . . . . . . . . . . . . . . .  7
   4. DBGP's Mitigation: Decoupling Path Propagation and Adoption . .  8
     4.1. Quarantine Time . . . . . . . . . . . . . . . . . . . . . .  8
   5. Protocol Descriptions . . . . . . . . . . . . . . . . . . . . .  9
     5.1. DAS_PATH Attribute  . . . . . . . . . . . . . . . . . . . . 10
     5.2. Identification of Suspicious Paths  . . . . . . . . . . . . 11
     5.3. Propagating DAS_PATHs with Updates  . . . . . . . . . . . . 12
     5.4. Choosing Alternative Paths  . . . . . . . . . . . . . . . . 13
     5.5 Releasing Quarantined Paths  . . . . . . . . . . . . . . . . 14
   6. Clarifications  . . . . . . . . . . . . . . . . . . . . . . . . 14
     6.1. Individual Historical Database  . . . . . . . . . . . . . . 14
     6.2. Difference from "add-path"  . . . . . . . . . . . . . . . . 14
     6.3 Detection Facilitation . . . . . . . . . . . . . . . . . . . 14
     6.4. Cooperation with Prevention . . . . . . . . . . . . . . . . 15
     6.5. Discontiguous Deployment  . . . . . . . . . . . . . . . . . 15
   7. Security Considerations . . . . . . . . . . . . . . . . . . . . 15
   8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 15
   9. References  . . . . . . . . . . . . . . . . . . . . . . . . . . 16



Mingui Zhang, et al      Expires June 28, 2013                  [Page 2]


INTERNET-DRAFT                    DBGP                 December 25, 2012


     9.1. Normative References  . . . . . . . . . . . . . . . . . . . 16
     9.2  Informative References  . . . . . . . . . . . . . . . . . . 16
   Appendix A: Empirical Evaluation . . . . . . . . . . . . . . . . . 17
   Author's Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18















































Mingui Zhang, et al      Expires June 28, 2013                  [Page 3]


INTERNET-DRAFT                    DBGP                 December 25, 2012


1. Introduction

   False routing announcements cause serious security issues to the
   inter-domain routing system, which can lead to widespread service
   disruptions. A special case is prefix hijacking, in which a network
   announces an IP prefix that belongs to another network. Existing
   works such as Pretty Good BGP (PGBGP)[PGBGP] block suspicious routing
   updates to protect data delivery. However, such an approach has the
   side effect of blocking the view of detection systems at the control
   plane and data plane. As a result, an attack will not be detected,
   and operators will not be alerted to take actions to stop the attack.
   This draft proposes an extension of BGP, to solve this paradox by
   decoupling path propagation and adoption in BGP.

   In current BGP, the path a router adopts for data forwarding is the
   same path being propagated to neighbors. That is why upon receiving a
   suspicious path, a router has to either accept it (no mitigation but
   good detection) or reject it (good mitigation but no detection). Our
   idea is for a router to use trusted paths for data forwarding, but
   still inform its neighbors about the suspicious path. The suspicious
   paths will be carried in an optional transitive attribute in BGP
   updates, while the routers still use trusted paths for data
   forwarding. This way the data traffic is protected while false
   routing announcements are being propagated to detection systems.

2. Terminology

   DBGP: Decoupling path propagation and adoption in BGP

3. False Routing Announcements

3.1. Problem

   False routing announcements can be caused by either inadvertent mis-
   configurations or malicious attacks. For the ease of exposition, we
   use "attacker" to refer to the network (or Autonomous System, AS)
   that makes the false routing announcements regardless of the
   intention. Based on which part of the routing path is false, such
   announcements can be classified into five types, each of which has
   different severity:

      o  Prefix origin: The attacker originates someone else's prefix.
         Depending on where a network is in the Internet topology, some
         will choose paths leading to the true origin and some will
         choose paths leading to the false origin.

      o  Intermediate node: The attacker does not forge the prefix or
         its origin, but inserts itself into the path as an intermediate



Mingui Zhang, et al      Expires June 28, 2013                  [Page 4]


INTERNET-DRAFT                    DBGP                 December 25, 2012


         AS. Similar to the case of false origin, some networks will
         choose the correct paths and some the false paths. But usually
         fewer networks will choose the false path since it is longer
         than that of false origin attack.

      o  Intermediate link: The attacker forges a new link to bypass
         some of the ASes to get a shorter path. The shortened path is
         expected to attract more networks' traffic.

      o  Sub-prefix: The attacker originates a sub-prefix of someone
         else's prefix. Due to the longest match in routing lookup, a
         false sub-prefix will win over the original prefix. Thus, all
         traffic destined to the sub-prefix range will be forwarded to
         the attacker.

      o  Super-prefix: Theoretically the attacker can also announce a
         false super-prefix, but that will not attract any traffic
         unless part of the prefix range is unused by the real owner, in
         which case it is equivalent to announcing a false origin of the
         unused prefix range.

3.2. Countermeasures

   The current strategies proposed for the problem of false
   announcements fall in three categories: prevention, detection and
   mitigation.

3.2.1. Prevention

   Prevention schemes (e.g., [SBGP], [SoBGP], and [SPV]) use
   cryptographic mechanisms to protect the routing updates and let
   routers reject any forged announcement. Unfortunately no prevention
   scheme has seen much deployment on the Internet due to the lack of
   incentives for those first movers. Since crypto-based schemes add
   significant computational load to routers and require upgrade on
   software or hardware, individual ISPs need to see immediate benefits
   to justify the deployment. On the current Internet, however, the
   first mover's routing announcements will be accepted by other
   networks without authentication, and adding authentication does not
   bring any immediate benefit.

3.2.2 Detection

   The representative detection systems proposed in recent years include
   [Cyclops], [PHAS], [MyASN], [IAR], [iSPY], [NWatch], [OList], and
   [LWeight]. Such systems are designed to detect false routing by
   examining routing updates, probing data paths, cross-checking with
   registry databases, or a combination of these techniques. Once a



Mingui Zhang, et al      Expires June 28, 2013                  [Page 5]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   false routing case is detected, the owner of the prefix will be
   notified, and it is expected that the owner will take actions to
   resolve the problem, which, in today's Internet, usually involves
   contacting the offending network or its upstream provider to stop the
   false routing announcements. This process of detection, notification
   and resolution takes time, ranging from an hour to a day in some past
   incidents and varying from network to network [NWatch][RIPE]. In the
   meantime, the damage to data traffic has already been made and
   malicious attackers may have already achieved their objectives.










































Mingui Zhang, et al      Expires June 28, 2013                  [Page 6]


INTERNET-DRAFT                    DBGP                 December 25, 2012


3.2.3. Traditional Mitigation

   A mitigation schemes attempts to protect the data traffic while an
   attack is going on. The common approach is to somehow identify
   abnormal routing updates and block them. As proposed in [PGBGP] and
   [PGBGP++], a router can examine the content of incoming updates. If
   an AS path contains unexpected prefix origin or links, it will be
   suppressed from propagating for a period of time to wait for the
   network operator's validation. The length of the time is configurable
   by the network operators. Instead, an alternative path (via trusted
   prefix origin and links) will be employed for data delivery in the
   suppression period. After this period, if the path is not proved to
   be illegal, the router will adopt and announce this new path. PGBGP
   gives operators certain reaction time to resolve potential false
   announcements while protecting data delivery in the meantime. When a
   real attack is detected and resolved, the corresponding false
   announcement will be withdrawn from the routing system, whereas
   legitimate announcement will stay in the routing system and
   eventually be accepted.

   But blocking false routing announcements can get in the way of
   detection systems. For instance, on September 22, 2008, a Russian ISP
   AS8997 hijacked a large number of prefixes as it leaked an entire
   table [ASN8997]. However, since the upstream ISP of AS8997 blocked
   the routing updates, detection systems such as MyASN and IAR did not
   pick up this incident. The attack mainly affected ISPs and users
   within Russia but largely went unnoticed by prefix owners.

   Each existing solution has its drawbacks, and none is sufficiently
   effective by itself. In future, there may be several different
   solutions deployed on the Internet at the same time, complementary to
   each other, forming a multi-line defense to protect routing and data
   delivery before, during, and after attacks.

3.3. Paradox of Blocking Suspicious Updates and Attack Detection

   It has been realized that a mitigation mechanism and a detection
   system that complement each other well can be integrated into an
   effective routing defense solution. For instance, the mitigation
   mechanism can help the detection system to confine the damage caused
   by an attack, as the affected data traffic may be vulnerable for
   hours before the attack can be actually detected by the detection
   mechanism and be eventually stopped. Also, the mitigation mechanism
   can also obtain benefit from the detection system because a
   mitigation mechanism normally cannot identity false routing
   information accurately with its limited knowledge, resource and time.
   The output from the detection system can be used to correct the many
   false positives generated by the mitigation mechanism and also inform



Mingui Zhang, et al      Expires June 28, 2013                  [Page 7]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   the prefix owner to resolve the attack.

   However, there is a dilemma: the mitigation mechanism tries to render
   the attack ineffective while the detection system needs the attack to
   be effective in order to detect it.

4. DBGP's Mitigation: Decoupling Path Propagation and Adoption

   The suspicious paths are serially blocked hop by hop for validation
   in traditional mitigation schemes, which gets in the way of detection
   systems. In order to solve this dilemma, this document proposes a
   solution which decouples path propagation and path adoption. The
   basic idea of this solution is to extend BGP's update message with a
   new optional transitive path attribute so that a router can inform
   its neighbor routers about the suspicious path and meanwhile the
   router uses another trusted path for data forwarding. In order to
   achieve this, a new BGP attribute, DAS_PATH, is defined in Section 5.
   Compared to the traditional mitigation schemes, the propagation of
   suspicious paths through DAS_PATHs in DBGP enables the parallel
   validation, which accelerates the adoption process of suspected
   legitimate paths (the false positive).

4.1. Quarantine Time

   Based on operating experiences, a false routing announcement can be
   detected and corrected in a certain period (e.g., one day) after it
   is launched, and so an announcement will be trusted if it is not
   withdrawn in a pre-defined period. Therefore, in mitigation schemes,
   when a new path is identified as a suspicious one, it will be
   quarantined (or blocked) from being used for a period of time, which
   is called the quarantine time and noted as T_q. If a new path has
   stayed in a router's Adj-RIBs-In for more than T_q, it will be
   trusted by this router. If this path is the most preferred from the
   Adj-RIBs-In, the router will use this path for data delivery and
   announce this path to its neighbors.

   A router MAY determine the quarantine time itself. Assume there are
   two routers, R1 and R2. R1 is the downstream of R2, and the
   quarantine time of R1 and R2 is T1 and T2 respectively. The
   suspicious path is PATH at R1. There are two possibilities.

      o  T1 is shorter than T2. When T1 expires, PATH becomes trusted by
         R1 and R1 begins to use it for data delivery. R1 will announce
         R1-PATH as a legitimate AS path to R2. However, at this time,
         the path R1-PATH is still being quarantined by R2.

      o  T1 is longer than T2. When T2 expires, R1-PATH becomes trusted
         by R2. However, R2 cannot use this path for data delivery as R1



Mingui Zhang, et al      Expires June 28, 2013                  [Page 8]


INTERNET-DRAFT                    DBGP                 December 25, 2012


         has not announced R1-PATH as an AS path. It will be cached in
         the Adj-RIBs-In until the downstream router R1 has announced it
         as an AS path when T1 expires.

5. Protocol Descriptions

   Take Figure 5.1 for example. A, B, C, and O are DBGP routers residing
   in different ASes, , X is the attacker and p is the prefix of
   interest. Before the attack, the preferred path for traffic is ABCO.
   Here, we use the notation "R1R2...Rn-p" to denote the AS path which
   is destined to prefix "p" via routers R1, R2, ..., Rn. When X makes a
   false announcement of X-p to B, B will regard this new path as
   suspicious because it would divert traffic to an AS(X) that
   previously was not on the data path (BCO). B will store the
   suspicious path in its Adj-RIBs-In (The routing tables of an AS
   router is comprised of three sub-tables: Adj-RIBs-In, Loc-RIB and
   Adj-RIBs-Out [BGP4]), but keep using the existing path in its Loc-RIB
   for data forwarding. At the same time, B re-announces its path (BCO)
   in an update message to A, and encapsulates the new, suspicious path
   (BX) as an optional transitive attribute which is defined in Section
   5.1. After receiving the update message, router A learns this
   suspicious path, stores it, and propagates it further to its
   neighbors using the optional attribute in the same way. Therefore,
   the suspicious path is propagated to the Internet while not adopted
   for data forwarding. This approach enable the detection systems to
   intercept the suspicious path and notify the prefix owner to take
   actions. Once the attack is stopped, the false announcements will be
   withdrawn from the routing system, i.e., deleted or replaced in the
   Adj-RIBs-In of the involved routers. However, a router realizes that
   the quarantine time has been expired and the suspicious path is still
   in the Adj-RIBs-In, the router regards the path as a legitimate one.
   Hence the DBGP router will install the path in its Loc-RIB for data
   forwarding and re-announce the path using the regular ASPATH
   attribute in the update message. For example, if BX-p has been
   validated as legitimate, B will announce it to A as its AS_PATH. The
   rest of this section will discuss the design details in new BGP
   attribute definition, identifying suspicious paths, choosing
   alternative paths for data forwarding, propagating the paths, and
   releasing quarantined paths.

                                   [X]->p
                                    ^
                                    |
                         [A]->[B]->[C]->[O]-p

                      Figure 5.1: Attack Example 1

   The rest of this section will discuss the design details in the



Mingui Zhang, et al      Expires June 28, 2013                  [Page 9]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   definition of the new DAS_PATH Attribute, identifying suspicious
   paths, choosing alternative paths for data forwarding, propagating
   the paths, and releasing quarantined paths.

5.1. DAS_PATH Attribute

   +-+-+-+-+-+-+-+-+
   | Attribute Type|                 (2 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Attribute Length              | (1 or 2 bytes)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Attribute Value               | (variable length)
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                   Figure 5.2: The DAS_PATH Attribute

   DAS_PATH (Decoupled AS_PATH) is defined as a new optional transitive
   Path Attribute (Figure 5.2) to be included in BGP's UPDATE messages.

   The first bit of the Attribute Type is set (1), therefore the
   attribute is optional. The second bit of Attribute Type is set (1),
   therefore the attribute is transitive and SHOULD be passed on to
   other BGP peers. The third and fourth bits are Partial bit and
   Extended Length bit respectively, which has already been defined in
   [BGP4]. The Attribute Type code is assigned by the IANA (Internet
   Assigned Numbers Authority). The definition of Attribute Length is
   the same as that in [BGP4].

   The Attribute Value is composed of a sequence of DAS path segments.
   Each DAS path segment is encoded as a triple <path segment type, path
   segment length, path segment value>.

   The path segment type is a 1-octet field with the following two
   allowable values:

      Value   Segment              Type
       1      DAS_SET             unordered set of ASs a route in the
                                  UPDATE message has traversed
       2      DAS_SEQUENCE        ordered set of ASs a route in the
                                  UPDATE message has traversed

   The path segment length field is 1-octet long field and contains the
   number of ASs in the path segment value field.

   The path segment value field contains one or more AS numbers, each
   encoded as a 2-octets long field.

   When a DAS_PATH is propagated across the network, the operations on



Mingui Zhang, et al      Expires June 28, 2013                 [Page 10]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   DAS_PATH follows the well-known AS_PATH attribute only that DAS_PATH
   is non-mandatory. If a router which does not deploy DBGP receives the
   update messages containing DAS_PATH attribute, i.e., does not
   understand this attribute, it will just pass it on to the next
   router. If its downstream router is a DBGP router, it will be able to
   pick up the information from this attribute and continue DBGP
   operations. Therefore DBGP can be incrementally deployed over the
   Internet.

5.2. Identification of Suspicious Paths

   For a given prefix p, a path is trusted if it has been staying in the
   Adj-RIBs-In continuously for the required quarantine time, T_q. All
   the nodes, links, and origins that appear in trusted paths are
   trusted components, and the set of them is denoted by trusted(p).
   This set of trusted components is derived from current contents of
   all Adj-RIBs-In without using a database to store historical
   information like PGBGP does. Nodes, links, and origins that do not
   belong to trusted(p) are said to be suspicious components for this
   particular prefix p. A new path is suspicious if it contains any
   suspicious component for its prefix. However, not all suspicious
   paths need to be explicitly quarantined. DBGP quarantines paths that
   satisfy the following condition:

      o  A new path is quarantined if and only if it is suspicious, more
         preferred than other alternative paths, and contains an AS that
         is not in the current data forwarding path.

   If the new path is not better than alternative paths, it will not be
   able to divert any traffic. One may suggest that the attacker can
   first announce a less preferred path so that DBGP routers will take
   it as a backup path without suspicion, and then make the primary path
   fail to trick the router to use the false backup path. But in this
   case, if the attacker has the control of the primary path, it can
   already get the traffic without doing this. If the attacker does not
   have control of the primary path, it will not know when the primary
   path may fail and which backup path the router will choose, thus the
   attack will not be effective.

   If the new path does not introduce any new AS on the data path, it is
   not quarantined since it does not divert any traffic. In Figure 5.3,
   when X launches an attack by announcing X-p, this path is not
   quarantined by B since B already sends its traffic to X. B will
   accept this path and announces it to A. Assuming ABX-p is more
   preferred than ACO-p, A will quarantine ABX-p since this new path
   would divert A's traffic to a new place, AS X, and X is a suspicious
   origin to A.




Mingui Zhang, et al      Expires June 28, 2013                 [Page 11]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   To reduce the potential false positives in quarantining paths, we
   introduce an optimization rule. If the current best path is replaced
   by a suspicious path (i.e., the same neighbor that sent the best path
   previously sends another path to replace it), then the current best
   path is cached for a short time period. This rule is used to
   accommodate some unstable prefixes, which may get announced and
   withdrawn or oscillate between two paths frequently. With this rule,
   quick re-announcement of a path will not be treated as suspicious.
   Previous measurement work has shown that (1) most prefixes are
   stable, and only a small number of prefixes are very unstable; (2)
   the most popular prefixes are stable; and (3) the most preferred
   paths are being used by routers for most of the time
   [BGPpop][Stable][BGPHA]. Therefore, DBGP's criterion for suspicious
   paths will not generate excessive false positives in reality. The
   majority of the rest prefixes is only suspicious infrequently.

                       +---------------+
                       |               |
                       |               v
                       [A]->[B]->[X]->[C]->[O]-p
                                       |
                                       p

                      Figure 5.3: Attack Example 2

5.3. Propagating DAS_PATHs with Updates

   DBGP uses the new BGP attribute, DAS_PATH, to carry a suspicious path
   in an update. In certain cases DBGP router may need to select a
   DAS_PATH from multiple ones to announce. For example, in Figure 5.4,
   assume C does not deploy DBGP and accepts the false announcement of
   X-p. When B receives BCX-p, B quarantines this new path and switches
   to its backup BDO-p. The update from B to A will have BDO as the
   AS_PATH, and BCX as the DAS_PATH attribute. However, since BDO is
   suspicious to A as well, A will quarantine BDO and switch to AEFO.
   Thus the update from A can contain either ABCX or ABDO. A router's
   neighbors may simultaneously send updates containing the DAS_PATH to
   it, which also makes the router have multiple DAS_PATHs to choose.
   There are two possible choices for DBGP implementations.

      1.  Dominate a router to select the best DAS_PATH from the
         multiple ones to announce, which is similar to the traditional
         AS_PATH selection process.

      2.  Encapsulate all the DAS_PATH attributes in tandem and sort
         them by their priorities. The priorities are determined
         according to the rules used in the AS_PATH selection process.




Mingui Zhang, et al      Expires June 28, 2013                 [Page 12]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   The first rule works well due to the following two facts. First,
   during attacks, the best DAS_PATH is most likely the bogus path
   aiming to attract data traffic. Second, during false positives, the
   best DAS_PATH will most likely become the best AS_PATH when the
   quarantine time ends.

   The second rule allows an AS router to provide more information to
   its upstream, which is helpful for diagnose and correctness of
   attacks. Moreover, the announcement of multiple DAS_PATHs MAY help to
   reduce the convergence time. Take Figure 5.4 for example, A announces
   two DAS_PATHs, i.e., ABDO-p and ABCX-p, to its upstream node, says U.
   When U receives the additional DAS_APTH: ABDO-p, it will begin the
   validation process of this suspicious path. After A determines that
   BDO-p is legitimate and installs it to its Loc-RIB, the validation
   process MAY have been finished, therefore U can immediately start to
   use ABDO-p.

   For the second rule, the number of DAS_PATHs in an update depends on
   the topology and policy of the network. Generally speaking, the
   number of DAS_PATHs in an update increases with the AS hop count of
   the AS_PATH. However, given AS paths are usually 4 to 5 hops and
   rarely goes to more than 10 hops, we do not expect the announcement
   of multiple DAS_PATHs will make DBGP message too large.

                                   [X]->p
                                    ^
                                    |
                         [A]->[B]->[C]->[O]-p
                          |    |         ^
                          |    |        /|
                          |    +-->[D]-+ |
                          |              |
                          +------->[E]->[F]

                      Figure 5.4: Attack Example 3

5.4. Choosing Alternative Paths

   When a new path is the most preferred but suspicious, DBGP routers
   will use an alternative path for data delivery. The question is which
   alternative path to be chosen. First, if the existing path that is
   being used for data forwarding is still the best, then the router can
   stick to that path without any changes. Second, if the existing path
   in use will have been replaced by the suspicious path, then the
   router needs to pick an alternative. For example, in Figure 5.4,
   suppose C does not deploy DBGP and blindly accepts the false
   announcement X-p. B's existing path BCO-p will be replaced by a
   suspicious path BCX-p, therefore B needs to temporarily switch to a



Mingui Zhang, et al      Expires June 28, 2013                 [Page 13]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   backup path BDO-p from its Adj-RIBs-In. Third, if there is no
   alternative path or all alternative paths are labeled as suspicious,
   then the router err on data delivery by adopting a suspicious path to
   forward packets.

5.5 Releasing Quarantined Paths

   If the quarantined paths are false announcements, it is likely that
   within T_q, the attack will be stopped and these paths being
   withdrawn from the routing system. In this case, there is no explicit
   release of the quarantined path. Just the upstream router will send
   an update with empty DAS_PATH attribute. If T_q has passed and the
   quarantined path is still in the Adj-RIBs-In, then it is more likely
   that this is a legitimate path. The router will treat the path as a
   regular path and make it go through the path selection process. If
   the path turns out to be the most preferred one, it will be used for
   data forwarding and trigger routing updates to neighbor routers.

6. Clarifications

6.1. Individual Historical Database

   When DBGP is implemented in an AS router, the router does not have to
   purchase additional memory to store the trusted paths as that in
   [PGBGP]. By default, a DBGP router uses the simple rules defined in
   Section 5.2 to filter suspected components of an AS path based on the
   information stored in its Adj-RIBs-In. All a router need to do is to
   add a new column to its Adj-RIBs-In to record the elapse time after
   an AS path entered a Adj-RIB-In.

6.2. Difference from "add-path"

   DBGP solution is different from the ongoing work of advertising
   multiple BGP paths in [add-path] where AS routers are also allowed to
   export multiple AS paths in one update. All advertised AS paths are
   available to upstream AS routers in [add-path]. Despite that DBGP
   allows multiple paths to be advertised in one update, except the AS
   path, all the other paths are actually unavailable. In other words,
   these paths only remain in Adj-RIBs-In of the AS router. They will
   not be put into either the Loc-RIB or Adj-RIBs-Out.

6.3 Detection Facilitation

   Traditional mitigation mechanisms block the propagation of suspicious
   paths, which undermines the effectiveness of detection systems. DBGP
   is proposed to address this shortage. In DBGP, the data traffic is
   protected while the false routing announcements are spread out to be
   monitored by detection systems. If the first rule in Section 5.4 is



Mingui Zhang, et al      Expires June 28, 2013                 [Page 14]


INTERNET-DRAFT                    DBGP                 December 25, 2012


   adopted, the capacity of propagating suspicious paths in DBGP is the
   same as that in BGP. If the second rule is adopted, this capacity is
   enhanced by DBGP instead.

6.4. Cooperation with Prevention

   As a mitigation scheme, DBGP routers validate AS paths based on the
   limited information stored in local Adj-RIBs-In. This would cause
   some legitimate paths to be identified as suspicious and blocked from
   being used for data delivery (high false positive). If a down stream
   router would like their paths be adopted quickly rather than be
   suspected, it can include certificates in the update messages. For
   example, if AS routers adopt the solution in [pfx-va], the AS number
   claiming to originate an address prefix will be validated by the
   prefix holder. The authorized origin will not be suspected by DBGP
   routers. Further, if the validation can cover the whole AS path, all
   kinds of attacks that DBGP is trying to cope with SHOULD be prevented
   in the first place. In all, the deployment of DBGP actually creates
   the incentive for deploying prevention systems.

6.5. Discontiguous Deployment

   DBGP does NOT require contiguous deployment in order to be effective.
   The key purpose of DBGP is to recognize and propagate the suspicious
   path segment via the DAS-PATH. When the AS router at the far side
   obtain the UPDATE message with the DAS-PATH missing some intermediate
   AS numbers, it doesn't matter. This AS router can still use this path
   segment for detection/validation purpose. Let's use the example in
   Figure 5.1 to explain. The starter AS router of the DAS-PATH must
   have deployed DBGP. In this figure, "B" is the starter. "B" can
   recognize "X" as suspicious node and propagates this via DAS-PATH to
   "A". We suppose "A" has not deployed DBGP. When A's upstream AS
   router receives A's update message, it will find that the AS-PATH is
   "ABCO" and the DAS-PATH is "BX". The detection system just uses "BX"
   as the input.

   It is not recommended to complement the DAS-PATH according to the
   primary path contained in the same UDPATE message. One will easily
   find this kind of trick is in vain.

7. Security Considerations

   The entire document is about security consideration.

8. IANA Considerations

   The attribute type code of DAS_PATH should be assigned by the IANA,
   which identifies the attribute uniquely from all others.



Mingui Zhang, et al      Expires June 28, 2013                 [Page 15]


INTERNET-DRAFT                    DBGP                 December 25, 2012


9. References

9.1. Normative References

   [PGBGP]     J. Karlin, S. Forrest, and J. Rexford, "Pretty Good BGP:
               Improving BGP by Cautiously Adopting Routes," in
               Proceedings of IEEE ICNP, 2006.

   [SBGP]      S. Kent, C. Lynn, and K. Seo, "Secure Border Gateway
               Protocol (SBGP)," IEEE Journal on Selected Areas in
               Communications, vol. 18, no. 4, pp. 582-592, 2000.


   [SoBGP]     J. Ng, "Extensions to BGP to Support Secure Origin BGP,"
               April 2004, ftp://ftp-eng.cisco.com/sobgp/drafts/draft-
               ng-sobgp-bgp-extensions-02.txt.

   [SPV]       Y.-C. Hu, A. Perrig, and M. Sirbu, "SPV: Secure Path
               Vector Routing for Securing BGP," in Proceedings of ACM
               SIGCOMM, 2004.

   [BGP4]      J. W. Stewart, BGP4: Inter-Domain Routing in the
               Internet. Boston,MA, USA: Addison-Wesley Longman
               Publishing Co., Inc., 1998.

   [pfx-va]    P. Mohapatra, J. Scudder, D. Ward, R. Bush, R. Austein,
               "BGP Prefix Origin Validation", draft-ietf-sidr-pfx-
               validate-01, working in progress.

9.2  Informative References

   [Cyclops]   Y.-J. Chi, R. Olivera, and L. Zhang, "Cyclops: the as-
               level connectivity observatory," SIGCOMM Comput. Commun.
               Rev., vol. 38, no. 5, pp. 5-16, 2008.

   [PHAS]      M. Lad, D. Massey, D. Pei, B. Zhang, and L. Zhang, "PHAS:
               A Prefix Hijack Alert System," in 15th USENIX Security
               Symposium, 2006, pp.153-166.

   [MyASN]     "RIPE myASN System," http://www.ris.ripe.net/myasn.html.

   [IAR]       [Online]. Available: http://iar.cs.unm.edu/

   [iSPY]      Z. Zhang, Y. Zhang, Y. C. Hu, Z. M. Mao, and R. Bush,
               "iSPY: Detecting IP Prefix Hijacking on My Own," in
               Proceedings of ACM SIGCOMM, 2008.

   [NWatch]    G. Siganos and M. Faloutsos, "Neighborhood Watch for



Mingui Zhang, et al      Expires June 28, 2013                 [Page 16]


INTERNET-DRAFT                    DBGP                 December 25, 2012


               Internet Routing: Can We Improve the Robustness of
               Internet Routing Today?" in Proceedings of IEEE INFOCOM,
               2007.

   [Olist]     X. Zhao, D. Pei, L. Wang, D. Massey, A. Mankin, S. Wu,
               and L. Zhang,"Dection of Invalid Routing Announcement in
               the Internet," in Proceedings of the IEEE DSN, June 2002.

   [LWeight]   C. Zheng, L. Ji, D. Pei, J. Wang, and P. Francis, "A
               Light-weight Distributed Scheme for Detecting IP Prefix
               Hijacks in Real-time," in Proceedings of ACM SIGCOMM,
               2007.

   [RIPE]      [Online]. Available: http://www.ripe.net/news/study-
               youtubehijacking.html

   [ASN8997]   "Prefix hijack by ASN 8997." [Online]. Available:
               http://www.merit.edu/mail.archives/nanog/2008-
               09/msg00704.html

   [BGPpop]    J. Rexford, J. Wang, Z. Xiao, and Y. Zhang, "BGP Routing
               Stability of Popular Destinations," in Proceedings of ACM
               IMC 2002, pp. 197-202.

   [Stable]    K. Butler, P. McDaniel, and W. Aiello, "Optimizing BGP
               Security by Exploiting Path Stability," in Proceedings of
               ACM CCS, Alexandria, VA, United States, 2006, pp. 298-
               310.

   [BGPHA]     R. V. Oliveira, R. Izhak-Ratzin, B. Zhang, and L. Zhang,
               "Measurement of Highly Active Prefixes in BGP," in
               Proceedings of IEEE Globecom,2005.

Appendix A: Empirical Evaluation

   The following aspects of DBGP are tested on the SSFNet-2.0 simulation
   platform which has implemented BGP4.
      o  The ability to counter different types of attacks
      o  The ability to rectify the false positives
      o  The memory and message overhead
   The evaluation proves that DBGP can be used to mitigate all types of
   attacks. Compared with previous mitigation approaches [PGBGP], it
   reduces the delay of legitimate announcements significantly, only
   incurs a small amount of messages and memory overhead.







Mingui Zhang, et al      Expires June 28, 2013                 [Page 17]


INTERNET-DRAFT                    DBGP                 December 25, 2012


Author's Addresses


   Mingui Zhang
   Huawei Technologies Co.,Ltd
   Huawei Building, No.156 Beiqing Rd.
   Z-park ,Shi-Chuang-Ke-Ji-Shi-Fan-Yuan,Hai-Dian District,
   Beijing 100095 P.R. China

   Email: zhangmingui@huawei.com

   Bin Liu
   Tsinghua University
   East Main Building RM9-416
   Tsinghua University, Hai-Dian District,
   Beijing, 100084 P.R. China

   Email: lmyujie@gmail.com

   Dacheng Zhang
   Huawei Technologies Co.,Ltd
   Huawei Building, No.156 Beiqing Rd.
   Z-park ,Shi-Chuang-Ke-Ji-Shi-Fan-Yuan,Hai-Dian District,
   Beijing 100095 P.R. China

   Email: zhangdacheng@huawei.com

   Beichuan Zhang
   University of Arizona
   Computer Science Department,
   The University of Arizona
   Tucson, AZ 85721 U.S.A.

   Email: bzhang@arizona.edu

















Mingui Zhang, et al      Expires June 28, 2013                 [Page 18]