Internet DRAFT - draft-bi-savi-pisl

draft-bi-savi-pisl






SAVI                                                               J. Bi
Internet-Draft                                                  B. Zhang
Intended status:  Informational                                   B. Liu
Expires:  November 30, 2012                               Tsinghua Univ.
                                                                F. Baker
                                                                   Cisco
                                                            May 29, 2012


        Prevent IP Spoofing Based On Link State Database (pisl)
                         draft-bi-savi-pisl-00

Abstract

   The Internet is suffering from severe DoS and DDoS attacks, and IP
   spoofing is one common used method to do DoS and DDoS attacks.  IP
   spoofing refers to that attackers send packets with forged source IP
   addresses.  In this memo, we propose one new approach of preventing
   IP spoofing, which we name PISL.  The PISL-enabled router generates
   the incoming table for source addresses using link state database,
   which exists in two most widely used intra-domain protocols:  OSPF
   and IS-IS.  In this memo, we only describe PISL in the OSPF
   environment.  The PISL-enabled router determines that a packet is
   spoofed if the packet arrives at an invalid incoming interface.  PISL
   only uses the existing information and does not impose new control
   messages, so it is easy to be deployed.  We have conducted simple
   simulation, which shows the high effectiveness of PISL:  even if PISL
   is only deployed in 10% of all OSPF routers in a network, 80%~99% of
   spoofing cases in the network can be detected.

   Requirements

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
   NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
   this document are to be interpreted as described in RFC 2119
   [RFC2119].

Status of this Memo

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

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months



Bi, et al.              Expires November 30, 2012               [Page 1]

Internet-Draft                    PISL                          May 2012


   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on November 30, 2012.

Copyright Notice

   Copyright (c) 2012 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

   This document may contain material from IETF Documents or IETF
   Contributions published or made publicly available before November
   10, 2008.  The person(s) controlling the copyright in some of this
   material may not have granted the IETF Trust the right to allow
   modifications of such material outside the IETF Standards Process.
   Without obtaining an adequate license from the person(s) controlling
   the copyright in such materials, this document may not be modified
   outside the IETF Standards Process, and derivative works of it may
   not be created outside the IETF Standards Process, except to format
   it for publication as an RFC or to translate it into languages other
   than English.



















Bi, et al.              Expires November 30, 2012               [Page 2]

Internet-Draft                    PISL                          May 2012


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Calculating the incoming table under the directed graph
       model  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Calculating the incoming table under the real network  . . . .  6
   4.  Simulation Results . . . . . . . . . . . . . . . . . . . . . .  8
   5.  Discussions  . . . . . . . . . . . . . . . . . . . . . . . . .  9
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 10
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 10
   8.  Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . 10
   9.  Change Log . . . . . . . . . . . . . . . . . . . . . . . . . . 10
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
     10.1.  Normative References  . . . . . . . . . . . . . . . . . . 10
     10.2.  Informative References  . . . . . . . . . . . . . . . . . 11
   Appendix A.  The Reverse Dijkstra Algorithm  . . . . . . . . . . . 11
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12


































Bi, et al.              Expires November 30, 2012               [Page 3]

Internet-Draft                    PISL                          May 2012


1.  Introduction

   The Internet is suffering from severe DoS and DDoS attacks, and IP
   spoofing is one common used method to do DoS and DDoS attacks.  IP
   spoofing refers to that attackers send packets with forged source IP
   addresses.  To solve the IP spoofing problem, the source address
   validation architecture (SAVA) [RFC 5210] was put forward.  According
   to SAVA, three levels of source address validation are ought to be
   needed, and they are:  the local subnet level, the intra-AS level and
   the inter-AS level.  In this memo, we propose an anti-spoofing method
   based on link state database, which we name PISL.  PISL is an
   intra-AS source address validation mechanism.  PISL only uses the
   existing link state database (LSDB), which can be used to calculate
   the incoming table for prefixes.  The PISL-enabled router determines
   that a packet is spoofed if the packet arrives at an invalid incoming
   interface.  The key point of generating the incoming table for source
   addresses is to calculate the shortest paths to them.  We use section
   2 and section 3 to address this problem.

   In section 2, we consider how to generate the incoming table under
   the directed graph model.  It is the foundation of section 3.  LSDB
   can be abstracted in to a directed graph.  As is well-known, dijkstra
   algorithm can be used to calculate the shortest paths from one single
   source node to all the other nodes, i.e., the single-source shortest
   problem.  And calculating the shortest paths from all the other nodes
   to one single destination node are in actual the single-destination
   shortest path problem.  It has been proved by [4] that the single-
   destination shortest path problem can be reduced to the single-source
   shortest path problem by reversing the direction of each edge.  To
   avoid the extra memory cost for the reverse graph, we develop the
   reverse dijkstra algorithm as described in section 2 and the
   appendix.

   In section 3, we consider how to generate the incoming table under
   the real OSPF network.  In the real OSPF network, there are maybe
   multiple areas.  LSDB of a router only has the topology of its own
   area, but do not have topologies of other areas.  The link metrics
   are maybe asymmetric, so the incoming directions of inter-area
   prefixes and eternal-AS prefixes cannot be calculated out, but it is
   sure that inter-area prefixes must traverse area-border routers
   (ABRs), and external-AS prefixes must traverse area-border routers or
   AS-boundary routers (ASBRs).  The fraction of area-border and AS-
   boundary routers is small in general.  To avoid the false positive,
   we consider the incoming directions of all the ABRs as legal incoming
   directions for inter-area prefixes.  Similarly, we consider the
   incoming directions of all the ABRs and ASBRs as legal incoming
   directions for external-AS prefixes.  Though that will impose some
   extent of false negative, the imposed false negative ratio is low, as



Bi, et al.              Expires November 30, 2012               [Page 4]

Internet-Draft                    PISL                          May 2012


   shown in the simulation section.

   [SAVO] proposed another algorithm to calculate the incoming table
   based on LSDB.  However, the computational complexity of the
   algorithm in [SAVO] is O(n^3) at the worst case while the
   computational complexity of PISL is only O(n^2) at the worst case,
   where n is the number of routers in LSDB.  The reason that why the
   algorithm in [SAVO] has higher computational complexity is that the
   algorithm in [SAVO] runs the dijkstra algorithm on every node while
   PISL runs the reverse dijkstra algorithm only on the node of itself..


2.  Calculating the incoming table under the directed graph model

   In this section, we will introduce how to calculate the incoming
   directions of all the other nodes in the directed graph with
   nonnegative weights.  The incoming direction can be represented by
   the node that the destination node is next to on the shortest path.
   In the next section, we will introduce how to calculate the incoming
   interfaces for prefixes based on the link state database of OSPF.
   The algorithm of this section is the foundation of the next section.

   The key point of calculating the incoming directions of all the other
   nodes to itself is to calculate the shortest paths from all the other
   nodes to itself, i.e., the single-destination shortest path problem.
   As is well-known, dijkstra algorithm can be used to calculate the
   shortest paths from one single source node to all the other nodes,
   i.e., the single-source shortest problem.

   It has been proven by [4] that the single-destination shortest path
   problem can be reduced to the single-source shortest path problem by
   reversing the direction of each edge.  However, that needs extra
   memory cost for the reverse graph.  To avoid the memory cost, we can
   immediately modify the dijkstra algorithm to calculate all the equal-
   cost incoming directions from all the other nodes to the destination
   node using the original graph.  The modified dijkstra algorithm is
   called by us the reverse dijkstra algorithm.  The Reverse dijkstra
   algorithm also uses the greedy strategy, and chooses nodes one by one
   with increasing shortest paths.  That is the same as the dijkstra
   algorithm.  There are three steps in each iteration for the reverse
   dijkstra algorithm as follows.

   Step 1:  Choosing.  The Reverse dijkstra algorithm chooses the
   nearest node that has not been chosen.

   Calculating.  The Reverse dijkstra algorithm calculates the equal-
   cost incoming directions for the chosen node.  The set of equal-cost
   incoming directions is the union set of directions of nodes that are



Bi, et al.              Expires November 30, 2012               [Page 5]

Internet-Draft                    PISL                          May 2012


   the equal-cost next hops of the chosen node.

   Step3:  Relaxing.  The Reverse dijkstra algorithm relaxes the reverse
   edges of the chosen node while the dijkstra algorithm relaxes the
   forwarding edges of the chosen node.

   The reverse dijkstra algorithm still has the computational complexity
   of O(n^2), where n is the number of nodes.  The pseudo code of the
   reverse dijkstra algorithm is as shown in the appendix.


3.  Calculating the incoming table under the real network

   In the last section, we have introduced the reverse dijkstra
   algorithm, which can be used to calculate the incoming directions
   from all the other nodes to one single destination.  That is the
   foundation of this section.  In this section, we will introduce how
   to calculate the incoming interfaces for prefixes using link state
   database of the OSPF protocol.  The other link state protocols, such
   as IS-IS , are similar.  In this memo, we only consider the case of
   OSPF.  The link state database can be used to construct a topology,
   which can be abstracted into a directed graph with nonnegative
   weights, where the reverse dijkstra algorithm can be applied.  In
   subsection A, we will analyze the possible incoming interfaces for
   different types of prefixes.  In subsection B we will introduce the
   detailed scheme of calculating incoming interfaces for prefixes.

3.1.  The analysis of feasible incoming interfaces for different types
      of prefixes

   In the OSPF network, there are three types of prefixes that are ought
   to be differently treated.  They are intra-area prefixes, inter-area
   prefixes and external-AS prefixes.  Their feasible incoming
   interfaces are analyzed as follows.

3.1.1.  Intra-area prefixes

   Intra-area prefixes refer to prefixes extracted from router-LSAs and
   network-LSAs, i.e., prefixes originated from the local area.  Routes
   know the whole intra-area topology (adjacencies and bidirectional
   weights), so incoming interfaces of intra-area prefixes can be
   calculated by the reverse dijkstra algorithm, which has been
   introduced in the previous section.

3.1.2.  Inter-area prefixes

   Inter-area prefixes refer to prefixes extracted from type3-summary-
   LSAs, i.e., prefixes originated from other OSPF areas.  The



Bi, et al.              Expires November 30, 2012               [Page 6]

Internet-Draft                    PISL                          May 2012


   unidirectional cost can only be used to calculate the next hops to
   inter-area prefixes, and cannot be used to calculate the incoming
   interfaces of the inter-area prefixes.  Fortunately, it is sure that
   inter-area prefixes must traverse ABRs to the intra area, so we can
   consider the incoming interfaces of all the intra-area ABRs to be the
   incoming interfaces of inter-area prefixes.  The incoming interfaces
   of intra-area ABRs can be calculated by reverse dijkstra algorithm
   based on the intra-area topology knowledge.

3.1.3.  External-AS prefixes

   External-AS prefixes refer to prefixes extracted from AS-external-
   LSAs.  One type of external-AS prefixes are the real prefixes from
   external ASes, the other type of external-AS prefixes are the
   redistributed prefixes from other intra-domain routing protocols.
   For external-AS prefixes, they are similar with inter-area prefixes,
   are also learned from summary routes, and routers cannot calculate
   the strict incoming interfaces for them.  We also give loose incoming
   interfaces for AS-external prefixes.  For prefixes from external
   ASes, they must traverse ASBRs or ABRs to itself.  So we can consider
   the incoming interfaces of all the ASBRs and ABRs in the intra area
   to be the incoming interfaces of prefixes from external ASes.  For
   the redistributed prefixes in the intra-domain, they will not
   traverse real AS-boundary routers to itself.  However, the two types
   of external-AS prefixes are advertised by the same AS-external LSAs,
   we cannot distinguish them.  So we treat redistributed prefixes as
   the same as prefixes from external ASes.

3.2.  The scheme of calculating incoming interfaces for prefixes using
      LSAs

   There are five steps to generate the incoming table for prefixes as
   follows.

3.2.1.  Step 1: Constructing the topology view

   Router-LSA and network-LSA describe the local link state topology of
   the corresponding router or the transit network.  Router-LSA and
   network LSA flood in the whole intra area.  So the whole intra-area
   link state topology can be constructed, and the intra-area topology
   is a bidirectional graph.  Type3-summary-LSA, type4-summary-LSA and
   AS-external- LSA advertise prefixes or ASBRs outside the area.  The
   three kinds of LSA only carry the unidirectional weights to
   corresponding prefixes or ASBRs, but do not carry the weights of the
   opposite direction.






Bi, et al.              Expires November 30, 2012               [Page 7]

Internet-Draft                    PISL                          May 2012


3.2.2.  Step 2: Identifying all the ABRs and ASBRs in the area

   There are two bits, bit B and Bit E, in the router-LSA.  If bit B=1,
   then it indicates that the corresponding router is ABR, otherwise,
   the corresponding router is not ABR.  Similarly, if bit E =1, then it
   indicates that the corresponding router is ASBR, otherwise, the
   corresponding router is not ASBR.

3.2.3.  Step 3: Calculating the incoming interfaces for the intra-area
        routers and transit networks

   Having the knowledge of the bidirectional link state topology of the
   whole intra-area, the reverse dijkstra algorithm can be applied to
   calculate the incoming interfaces for the intra-area routers and
   transit networks.  The calculated incoming interfaces of the intra-
   area routers will be used in the next step.

3.2.4.  Step 4: Calculating the incoming interfaces for prefixes

   a) The intra-area stub prefixes are described in router-LSAs.  The
   incoming interfaces of stub prefixes are the incoming interfaces of
   the corresponding routers, i.e., the routers that originate the
   corresponding router-LSAs.

   b) The inter-area prefixes are described in type3-summay-LSAs.  As
   analyzed in the last subsection, the incoming interfaces of inter-
   area prefixes are the incoming interfaces of all the ABRs.

   c) The left prefixes are AS-external prefixes, which are described in
   AS-external-LSAs.  As analyzed in the last subsection, the incoming
   interfaces of AS-external prefixes are the incoming interfaces of all
   the ABRs and ASBRs in the area.  So all the AS-external prefixes have
   the same incoming interfaces.  To reduce the size of incoming table,
   the AS-external prefixes can be aggregated into the default prefix
   0.0.0.0/0.  And the incoming interfaces of prefix 0.0.0.0/0 are the
   incoming interfaces of all the ABRs and ASBRs in the area.

3.2.5.  Step 5: Loading the incoming table

   Loading the incoming table with the calculated incoming interfaces of
   the intra-are stub prefixes, intra-area transit network prefixes,
   inter-area prefixes and the default prefix 0.0.0.0/0.  The incoming
   table is used to determine whether packets are spoofed.


4.  Simulation Results

   We collected the topologies marked with ISP map from the project of



Bi, et al.              Expires November 30, 2012               [Page 8]

Internet-Draft                    PISL                          May 2012


   rocketfuel.  We assume that routers in the same AS run the OSPF
   protocol with only one single area.  All the bidirectional weights
   are 1.  We draw two conclusions as follows. (a) If PISL is only
   deployed in 10% of routers, 80%~99% of spoofed cases can be detected.
   (b) The false negative ratio due to loose incoming interfaces of AS-
   external prefixes is approximately equal to the percentage of ABRs
   and ASBRs.  Similarly, the false negative ratio due to loose incoming
   interfaces of inter-area prefixes is approximately equal to the
   percentage of ABRs.


5.  Discussions

5.1.  Deployment

   The router only needs to add an algorithm function and does not need
   extra communication cost if it wants to support PISL.  So PISL is
   easy to be deployed.  In addition, if PISL is only deployed partly in
   the network, it can prevent the source address spoofing in some
   extent.  The more deployed routers, the higher effectiveness PISL can
   perform.  Moreover, the router that has deployed the PISL can prevent
   spoofing cases from other routers.  A deployment limitation for PISL
   is that it can only be deployed in the OSPF-enabled routers at
   present.  We will extend PISL to work in other link state protocols,
   such as IS-IS.

5.2.  Static Route

   The static route is used in two scenarios.  In one scenario, the
   static route is configured to realize the interconnectivity between
   two networks.  In order to realize the interconnectivity, the routes
   of the other network will be distributed into the OSPF network, or an
   OSPF router announces the address space that covers the address space
   of the other network.  In that scenario, the static route does not
   conflict with the OSPF routing.  PISL can deal with it in the normal
   way.  In the other scenario, the static route is inconsistent with
   the OSPF routing.  That is dangerous.  The topology and routing
   information should be well known in order to avoid the routing loop.
   In that situation, the static route is dangerous, and is used rarely.
   Once the inconsistent static route is used, PISL can be configured
   manually to solve it.

5.3.  Fast Reroute

   Fast reroute refers to redirecting traffic to other feasible next
   hops after a using link is down and before the network is converged.
   So fast reroute traffic may be filtered by PISL.  The fast reroute
   packets filtered by PISL can be regarded as packet loss not due to



Bi, et al.              Expires November 30, 2012               [Page 9]

Internet-Draft                    PISL                          May 2012


   congestion.  After the network is converged, the filtered fast
   reroute packets can be retrieved by the Transmission Control
   Protocol.  Coping with fast reroute carefully, PISL can be configured
   to the alarming mode.  Spoofed packets detected are forwarded
   normally, but alarms are sent to the network managers, who determine
   whether those spoofed packets are filtered.


6.  IANA Considerations

   This memo includes no request to IANA.


7.  Security Considerations

   The memo does not introduce new security problem.  The security
   problems of this demo are the same as the security problems of the
   link-state-based protocols.  The most important security problem of
   this demo is the facticity of LSDB.  There is need to enhance the
   trustiness of LSAs between routers.


8.  Acknowledgment

   This document was generated using the xml2rfc tool.

   Thanks Guang Yao and Joel M. Halpern for their comments


9.  Change Log

   Initial version:  Tuesday May 29, 2012


10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", RFC 2119, March 1997.

   [RFC2328]  Moy, J., "OSPF Version 2", RFC 2328, April 1998.

   [RFC5210]  Wu, J., Bi, J., Li, X., Ren, G., Xu, K., and M. Williams,
              "A Source Address Validation Architecture (SAVA) Testbed
              and Deployment Experience", RFC 5210, June 2008.





Bi, et al.              Expires November 30, 2012              [Page 10]

Internet-Draft                    PISL                          May 2012


10.2.  Informative References

   [4]        Thomas, H., Charles, E., Ronald, L., and S. Clifford,
              "Introduction to Algorithms", 2001.

   [SAVO]     Tao, Z., Gong, Z., Lu, Z., Wang, B., Wang, H., Li, S.,
              Liu, Y., Bi, J., and J. Wu, "OSPFv3-based Intra-Domain
              Source-Address Validation Implementation", November 2011.


Appendix A.  The Reverse Dijkstra Algorithm

   Variables
   t:the single-destination node
   D[i]:the cost of the shortest path from node i to node t
   L[i]:the set of incoming directions of node i to node t.
     There are maybe multiple directions for a node in the situation
     of multiple equal-cost shortest paths, so L[i] is a set.
     The incoming direction is represented by the last hop of the
     shortest path (the destination hop is not included).
   e[i][j]:the cost (or weight) from node i to node j.
   rAdj[i]:the set of nodes that have reverse edges to node i.
   S:the set of nodes whose shortest paths to destination t have
     been found
   Q:the set of nodes that has not been included in S.


























Bi, et al.              Expires November 30, 2012              [Page 11]

Internet-Draft                    PISL                          May 2012


   Initialization
   D[t]=0
   D[other nodes]= infinite
   L[t]={NULL}
   L[other nodes]={}
   S={t}
   Q={all the nodes excluding t}

   Iteration
   While(Q!=empty)
   {
       u=i,where D[i]is minimum among the nodes in Q.
       for each vertex v in S
       {
           if(u==t) break;
           if(e[u][v]+d[v]==d[u])
           {
               if(L[v]=={NULL})
               {
                   L[u]=L[u]U{u}
               }
               else
               {
                   L[u]=L[u] U L[v];
               }
           }
       }
       for each vertex v in radj[u]
       {
           if(e[v][u]+d[u]<d[v])
           {
               d[v]=e[v][u]+d[u];
           }

       }
       Q=Q-{u};
       S=S U{u}
   }













Bi, et al.              Expires November 30, 2012              [Page 12]

Internet-Draft                    PISL                          May 2012


Authors' Addresses

   Jun Bi
   Tsinghua University
   Network Research Center, Tsinghua University
   Beijing  100084
   China

   Email:  junbi@tsinghua.edu.cn


   Baobao Zhang
   Tsinghua University
   Computer Science, Tsinghua University
   Beijing  100084
   China

   Email:  zbb@netarchlab.tsinghua.edu.cn


   Bingyang Liu
   Tsinghua University
   Computer Science, Tsinghua University
   Beijing  100084
   China

   Email:  liuby@netarchlab.tsinghua.edu.cn


   Fred Baker
   Cisco Systems
   Santa Barbara, CA  93117
   United States

   Email:  fred@cisco.com
















Bi, et al.              Expires November 30, 2012              [Page 13]