Problem Statement of SAVI Beyond the First Hop
draft-bi-savi-problem-02

SAVI                                                               J. Bi
Internet-Draft                                                    B. Liu
Intended status:  Informational                           Tsinghua Univ.
Expires:  August 3, 2012                                January 31, 2012

             Problem Statement of SAVI Beyond the First Hop
                        draft-bi-savi-problem-02

Abstract

   IETF Source Address Validation Improvements (SAVI) working group is
   chartered for source address validation within the first hop from the
   end hosts, i.e. preventing a node from spoofing the IP source address
   of another node in the same IP link.  For source address validation
   beyond the first hop (SAVI-BF), Ingress Filtering [BCP38]/[BCP84] is
   the best current practice.  However Ingress Filtering may drop
   legitimate packets (false positive) or fail to recognize spoofing
   packets (false negative) in case of asymmetric routing, which is not
   rare under SAVI-BF scenario.

   This document states the possible scenarios in which Ingress
   Filtering may have problems (false positive or false negative).  We
   claim that the reason of the problems is that the routers are lack of
   sufficient routing information to predict the incoming direction of a
   packet, since source address validation beyond the first hop should
   act consistently with the behavior of the routing system.  We also
   discuss the availability of the needed routing information under
   different routing environments.

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
   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 August 3, 2012.

Copyright Notice

Bi & Liu                 Expires August 3, 2012                 [Page 1]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

   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 & Liu                 Expires August 3, 2012                 [Page 2]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 4
   2.  Problems of Ingress Filtering . . . . . . . . . . . . . . . . . 5
     2.1.  Ingress Access Lists  . . . . . . . . . . . . . . . . . . . 5
     2.2.  Strict Reverse Path Forwarding  . . . . . . . . . . . . . . 5
     2.3.  Feasible Reverse Path Forwarding  . . . . . . . . . . . . . 5
     2.4.  Loose Reverse Path Forwarding . . . . . . . . . . . . . . . 6
     2.5.  Loose Reverse Path Forwarding Ignoring Default Routes . . . 6
   3.  The Availability of Required Routing Information  . . . . . . . 6
     3.1.  Pure Link-state Routing Environment . . . . . . . . . . . . 6
     3.2.  Other Routing Schemas . . . . . . . . . . . . . . . . . . . 7
     3.3.  Other Challenges  . . . . . . . . . . . . . . . . . . . . . 7
   4.  Acknowledgment  . . . . . . . . . . . . . . . . . . . . . . . . 7
   5.  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7
   6.  Security Considerations . . . . . . . . . . . . . . . . . . . . 8
   7.  Informative References  . . . . . . . . . . . . . . . . . . . . 8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 8

Bi & Liu                 Expires August 3, 2012                 [Page 3]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

1.  Introduction

   Ingress Filtering [BCP38]/[BCP84] is now the only practical source
   address validation technique beyond the frist hop from the end hosts.
   According to the report [ARBOR] by ARBOR Networks in 2009, of the 132
   network operators as the survey respondents, only about 35% deployed
   [BCP38] at dedicated customer edge, about 35% deployed it at
   broadband edge, and about 45% deployed it at peering edge.  And the
   measurement by MIT ANA Spoofer project [Spoofer] shows that 31% of
   the test clients were able to successfully spoof an arbitrary,
   routable source address, while 77% of clients otherwise unable to
   spoof could forge an address within their own /24 subnetwork, and no
   mitigation improvement against spoofing over four years of
   measurement.

   The difficulties ISP met in deploying Ingress Filtering implies the
   intrinsic problems of Reverse Path Forwarding (RPF).  Detailed in
   [BCP84], Ingress Filtering has five ways of implementation.  The
   first one is Ingress Access Lists, which are typically manually
   maintained and thus difficult to be practical in dynamic environment.
   Strict Reverse Path Forwarding (Strict RPF) and Feasible Path Reverse
   Path Forwarding (Feasible RPF) take advantage of the Reverse Path
   Forwarding (RPF) technique, and they share the same flaw with RPF,
   i.e. droping legitimate packets (false positive) under asymmetric
   routing.  Loose Reverse Path Forwarding (Loose RPF) and Loose Reverse
   Path Forwarding Ignoring Default Routes (Loose RPF Ignoring Default
   Routes) check the existence of a route instead of where the route
   points to.  These two ways of implementation, of course, have lower
   false positive, but they in a lot of cases cannot recognize spoofing
   packets (false negative) and thus are known as very inefficient.

   The reason of the problems of Ingress Filtering, is the lack of
   routing information, because the behavior of a SAVI-BF solution
   should be consistent with the routing system.  If the routing
   information on routers is asynchronous, a router may fail to predict
   the inbound direction of an incoming packet from other routers when
   the route is asymmetric.  We will show that the routing information
   required by source address validation beyond the first hop (SAVI-BF)
   is not available in all the routing schemas.  Specifically, this
   information is available in a pure link-state routing protocol
   environment, but unavailable or incomplete in other routing schemas.

   In Section 2, we state the problems of Ingress Filtering.  In Section
   3, we discuss the availabiltiy of the routing information required by
   SAVI-BF under different routing environments.

Bi & Liu                 Expires August 3, 2012                 [Page 4]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

2.  Problems of Ingress Filtering

   In this section, we examine the five modes Ingress Filtering as
   defined in [BCP84], and explore possible practical problems.

2.1.  Ingress Access Lists

   Ingress Access Lists are typically maintained manually, and it is
   only applicable where the number of prefix is small and the routing
   is stable over time.  However, in a dynamic routing evironment (where
   dynamic routing protocols, like BGP and OSPF, are used), routing will
   oscillate in case of link failure, new link creation or
   reconfiguration.  In these cases Ingress Access Lists may filter out
   valid packets (false positive) or let spoofing packets pass (fase
   negative).

2.2.  Strict Reverse Path Forwarding

   The procedure of Strict RPF is that the source address is looked up
   in the Forwarding Information Base (FIB) - and if the packet is
   received on the interface which would be used to forward the traffic
   to the source of the packet, it passes the check.

   Since RPF estimates the incoming path of a packet by reversely using
   the forward forwarding path towards the source address of the packet,
   it makes mistakes when the route is asymmetric, i.e. the path used
   towards the address is not the one used from that address.
   Unfortunately, routing asymmetry is not rare in the network beyond
   the first hop from the end hosts.  To properly predict the incoming
   direction of a packet, a router should use the routing information to
   compute the reverse paths from other routers to itself.  We will
   discuss the availability of such information under different routing
   schemas in the next section.

2.3.  Feasible Reverse Path Forwarding

   Feasible RPF extends Strict RPF by inserting alternative routes (if
   any) into FIB, instead of just inserting one best route.  A well-
   known implementation of Feasible RPF is RPF check considering equal-
   cost multi-path (ECMP) [ECMP].  ECMP installs multiple best routes
   into FIB.  All the ECMP out-interfaces are considered valid as the
   in-interfaces of the given source address prefix.

   Ideally, Feasible RPF should be able to store all ECMPs.  However, in
   practice, there can be many (tens of) ECMPs for a prefix, but the
   implementation of a router can only store several (e.g. 4 or 8) of
   them.  Thus the ECMPs for the prefix installed in FIB may be
   different in different routers, which eventually causes asymmetric

Bi & Liu                 Expires August 3, 2012                 [Page 5]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

   routing and fails Feasible RPF.

2.4.  Loose Reverse Path Forwarding

   Loose RPF is algorithmically similar to strict RPF, but differs in
   that it checks only for the existence of a route.  The obvious
   drawback is that Loose RPF could be very inefficient, because any
   routable source prefix could be accpeted regardless of its incoming
   direction, which results in high false negative.  In a more rigorous
   case, a slightly smarter attacker can use only routable source
   addresses to launch spoofing based attacks, and this can nullify the
   efficacy of Loose RPF completely.  Even without "smarter attack",
   randomly selected source addresses have the probability higher than
   50% to pass Loose RPF, because in the current Internet, more than 50%
   of the address span is routable [BGP-Table].

2.5.  Loose Reverse Path Forwarding Ignoring Default Routes

   The Loose RPF Ignoring Default Routes is similar to Loose RPF except
   that the default route is excluded, i.e. the source prefixes matching
   (in terms of longest prefix matching) the default route will be
   discarded.  Therefore, the technique is mostly usefull in scenarios
   where default routes are used only to catch traffic with bogus source
   addresses, with an extensive (or even full) list of explicit routes
   to cover legitimate traffic.  If applied in other scenarios, this
   technique will cause false positive because of the routing asymmetry.
   If no default route is configured, this technique shares the same
   false negative with Loose RPF.

3.  The Availability of Required Routing Information

   As discussed in the previous sections, SAVI-BF needs sufficient
   routing information to compute the reverse forwarding path (the path
   used from the source address towards the router), rather than just
   reversely use the forward forwarding path.  In this section, we
   discuss the availability of the required routing information under
   different routing schemas.  We also discuss some challenges to
   SAVI-BF, such as ECMP and fast reroute.

3.1.  Pure Link-state Routing Environment

   In a link-state routing protocol, like OSPF and IS-IS, the state of
   every link is propogated through the network.  So a route has
   sufficient routing information to compute the forwarding paths from
   other nodes (including routers and subnets) towards itself.

   If a link-state routing protocol is used together with other routing

Bi & Liu                 Expires August 3, 2012                 [Page 6]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

   mechanism, e.g. static routing, the routing information may become
   asynchronous.  The information on some routers may become incomplete
   to compute the reverse forwarding paths.

3.2.  Other Routing Schemas

   In other routing schemas, such as distance-vector routing protocols
   (RIP, EIGRP, BGP, etc.), static routing scheme, or the mix of them,
   the routing information on an individual router may not be sufficient
   to compute the reverse forwarding paths, since the complete routing
   inforamtion is not propogated in the network.

3.3.  Other Challenges

   ECMP and fast reroute remain challenges to SAVI-BF.  ECMP, as a
   special case of "other routing schemas", locally chooses one or
   multiple routes from the equally best routes and loads them to the
   forwarding plane (FIB), without propogating this choice to the
   network.  So if another router cannot hold all the ECMPs (e.g. due to
   limited hardware or software capacity), the route it computes may not
   be consistant with the route used by the source.

   Fast reroute [Fast-Reroute-Framework]/[Fast-Reroute-MPLS] is used to
   protect against link or router failure.  On link or router failure,
   the router immediately switch the exit of the packets to another
   locally computed next hop.  Fast reroute challeges SAVI-BF in two
   dimensions.  First, the backup route is computed locally without
   propogated to the network (as stated in "other routing schemas").
   Second, the time to switch to the backup route is very short, and the
   other routers couldn't react that fast.  So some legitimate packets
   may be dropped since they suddenly arrive from an unexpected
   direction, which offsets the effect of fast reroute.

4.  Acknowledgment

   The authors would like to thank Fred Baker and Joel M. Halper for
   their review and comments.

   This document was generated using the xml2rfc tool.

5.  IANA Considerations

   This memo asks the IANA for no new parameters.

   Note to RFC Editor:  This section will have served its purpose if it
   correctly tells IANA that no new assignments or registries are

Bi & Liu                 Expires August 3, 2012                 [Page 7]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

   required, or if those assignments or registries are created during
   the RFC publication process.  From the authors' perspective, it may
   therefore be removed upon publication as an RFC at the RFC Editor's
   discretion.

6.  Security Considerations

7.  Informative References

   [ARBOR]    McPherson, D., Dobbins, R., Hollyman, M., Labovitz, C.,
              and J. Nazario, "Network Infrastructure Security Report",
              February 2009.

   [BCP38]    Paul, P. and D. Senie, "Network Ingress Filtering:
              Defeating Denial of Service Attacks which employ IP Source
              Address Spoofing", RFC 2827, BCP 38, May 2000.

   [BCP84]    Baker, F. and P. Savola, "Ingress Filtering for Multihomed
              Networks", RFC 3704, BCP 84, March 2004.

   [BGP-Table]
              Huston, G., "AS6447 BGP Routing Table Analysis Report",
              November 2011.

   [ECMP]     Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
              Multicast Next-Hop Selection", RFC 2991, November 2000.

   [Fast-Reroute-Framework]
              Shand, M. and S. Bryant, "IP Fast Reroute Framework",
              RFC 5714, January 2010.

   [Fast-Reroute-MPLS]
              Pan, P., Swallow, G., and A. Atlas, "Fast Reroute
              Extensions to RSVP-TE for LSP Tunnels", RFC 4090,
              May 2005.

   [Spoofer]  Beverly, R., Berger, A., Hyun, Y., and k. claffy,
              "Understanding the Efficacy of Deployed Internet Source
              Address Validation Filtering", August 2009.

Bi & Liu                 Expires August 3, 2012                 [Page 8]
Internet-Draft        SAVI Problem Beyond First Hop         January 2012

Authors' Addresses

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

   Email:  junbi@tsinghua.edu.cn

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

   Email:  liuby@netarchlab.tsinghua.edu.cn

Bi & Liu                 Expires August 3, 2012                 [Page 9]