Network Working Group Tao Zijin Internet Draft Gong Zhenghu Lu Zexin Wang Baosheng Wang Hong Li Sudan Liu YaPing National University of Defense Technology, China Bi Jun Wu JianPing Tsinghua University,China Intended status: Informational Expires: April 20, 2012 November 14, 2011 OSPFv3-based Intra-Domain Source-Address Validation Implementation draft-tao-savi-savo-01 Abstract This memo describes SAVO SAVI, a source address validation mechanism for IPv6 networks based on the OSPFv3 protocol within Intra-Domain field. The proposed mechanism is intended to complement ingress filtering techniques to provide a higher granularity on the control of the forged source addresses and it can deal with the asymmetric routing for which the common uRPF scheme ([RFC2827]) may fail. The proposed SAVO mechanism does not need any additional communication between the routers in which the SAVO mechanism has been implemented and deployed. It can be incrementally deployed by the network manager and when it is only partially deployed it still helps to restrict the effect of the source address forging. It provides proactive incentives for the users who deploy it for they will be able to filter the packets with forged source address to a certain range, especially when the forged addresses are in the range of OSPF route prefixes. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, and it may not be published except as an Internet-Draft. This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, except to publish it as an RFC and to translate it into languages other than English. Tao Zijin Expires April 20, 2012 [Page 1] Internet-Draft SAVO SAVI October 2011 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. 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/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on February 20, 2012. Copyright Notice Copyright (c) 2011 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. Tao Zijin Expires April 20, 2012 [Page 2] Internet-Draft SAVO SAVI October 2011 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. Table of Contents 1. Introduction ................................................ 3 2. SAVO SAVI specification...................................... 8 2.1. The SAVO Basic Algorithm for Calculating the Possible Valid Incoming Interface (BA-VII) of a certain router in a area..... 8 2.2. Calculating the Incoming Interfaces for Source Addresses in intra-area route prefix..................................... 11 2.3. Calculating the Incoming Interfaces for source address in inter-area route prefix..................................... 12 2.4. Calculating the Incoming Interfaces for source addresses in AS-external route prefix.................................... 13 3. Routing Policy Considerations............................... 14 4. Security Considerations..................................... 14 5. Deployment Considerations................................... 14 6. References ................................................. 15 6.1. Normative References................................... 15 6.2. Informative References................................. 15 Appendix A. SAVO Related Algorithms............................ 16 A.1. Equal-Cost Parent-Vertex Search Algorithm(ECPS) for a known vertex in a SPF tree........................................ 16 A.2. Basic Algorithm of the Valid Incoming Interfaces for a given router(BVIIA) .............................................. 17 7. Conventions used in this document........................... 19 1. Introduction This memo describes SAVO SAVI, a source address validation mechanism for IPv6 networks based on the OSPFv3 protocol within Intra-Domain field. The proposed mechanism is intended to complement ingress filtering techniques to provide a higher granularity on the control of the forged source addresses and it can deal with the asymmetric routing for which the common uRPF scheme ([RFC2827]) may fail. The filtering rules constructed by SAVO are completely based on the OSPF protocol, their aims are to filter the packets with invalid or Tao Zijin Expires April 20, 2012 [Page 3] Internet-Draft SAVO SAVI October 2011 forged source addresses and their keywords to match are the source address prefixes which are the same as the OSPF route prefixes. The OSPF is one of the most widely used Intra-Domain routing protocols in Internet nowadays. For the next generation Internet, the main network layer protocol is IPv6, and OSPFv3 [1] is proposed as a substitute for OSPFv2[2] in IPv6 routing. OSPF is an IGP, used within an AS which is divided into areas, the topology of an area is hidden from the rest of the Autonomous System, and in the area the SPF technology is used as the routing means. In OSPF, the main consideration is on how to get an optimal route (i.e. nexthop) to a designated destination. In the routing calculation of OSPF, the destination address can be converted to its associated routers or links, hence the best route (nexthop) to the destination can be got by searching the corresponding Router-id or Link-id in the shortest path tree. In this draft, on the contrary, the main point is on how to get all the possible incoming interfaces for designated source addresses which are in the current OSPF routing table of the router. If the packets with the forged source addresses which are in the OSPF route prefixes come from the unintended interfaces, they can be filtered by the SAVO router. In OSPF, each router is identified by a certain router-id which is unique in the domain. The OSPF routes are advertised by each router via a certain type of Link State Advertisement (LSA). For OSPFv3, the intra-area route prefix is advertised by intra-area-prefix-LSAs (Type 9), The inter-area route prefix is advertised via the inter-area- prefix-LSA (Type 5), and the AS-external route prefix is advertised via the AS-external-LSA (Type 7). As the route prefix is advertised by one or more certain router(s) with a unique router-id, the route prefix is associated with the associated router. From the source address validation's perspective, the valid (OSPF) source address prefix must be the address prefix advertised by the OSPF router. So if a router learned a route prefix, and the route prefix, which can be seen as a source address prefix, must come from one or more router(s) associated with the prefix. Here the word 'associated' router means the router either has advertised the prefix (as the DR or BDR of the link) or has a link which has the corresponding address prefix configured but not necessarily has advertised the route prefix. Tao Zijin Expires April 20, 2012 [Page 4] Internet-Draft SAVO SAVI October 2011 From the routing perspective, the router searches and constructs the shortest path from itself to all other routers in the domain by the topology information received and stored in its link-state database. The result of the shortest path constructing is an appropriate nexthop or multiple equal-cost nexthops which the router selects to be the first hop of the shortest path. In OSPF, to the intra-area route prefix, the nexthop is the first hop of the shortest path to the destination in the area; to the inter- area prefix, the nexthop is the first hop of the shortest path to the border-router(only for Cisco's implementation of the OSPF, which is distinct from the original specification of the OSPF); to the external route prefix, the nexthop is first hop of the shortest path to the advertising router which may be intra-area or inter-area due to its relative position in the domain. From the source address validation perspective, the router analyses and constructs all the possible paths by which another router in the domain may choose to get to it. The SAVO router considers all the previous hops of the possible paths standing at the position of another router. The way considering the possible paths is just the reverse of the way considering the shortest path, the only difference is just between 'all' and 'one'---from the source address validation perspective, all the possible shortest paths should be taken in account and included, which can be expressed as n-->n, while from the routing perspective only the shortest one of them is considered to be useful without considering the equal-cost paths, which can be expressed as n-->1. After the SAVO router has completed the OSPF route calculation and writing the route to the IPv6 route table, it can compute the valid incoming interfaces of those routes according to the collected LSDB information which is also used by the route computation. The filtering rules for certain source address prefixes can be constructed by the valid incoming interfaces of those prefixes. The filter rules can be implemented as the Access Control List (ACL) or IPTable rules. The basic assumption of SAVO is as follows: o The router is the agent or representative of the routing prefix, every networking host or device should connect to the network by accessing the routers, the address prefixes of routers' links are the real address prefixes of the networking hosts or devices; o the identity of a router is identified by a Router-id which is unique in the network; Tao Zijin Expires April 20, 2012 [Page 5] Internet-Draft SAVO SAVI October 2011 o The LSDBs of all routers in a area are synchronized; o The inter-area route of every router is determined by selecting the best route from its border route table. In Figure 1, to router RT7, the route (nexthop) to network N1 can only be RT3, while the packets with the source address prefix N1 may come from RT3 or RT6. To network N2, there are two routers (RT8 and RT9) on the link, the packets with the source address prefix N2 may come from any one of them, but there may be only one of them which is the Designated Router (DR) of the link has advertised it to router RT7, and router RT7 can get the valid incoming interfaces of N2 from the corresponding Router LSA and Network LSA about the network N2. ,' N3 o `. / | \ ; | : | Area 3 10 | : | ; \ RT9 o / `. | ,' `. 10 ,' _.------. `----+--' ,-'' `-- +------------. ; | ,' / RT6`. RT1-'' RT2|- . / RT5 N1 / o--+--48---,'o-----48-----o---`;-10---o----10-----o / | \ / | | |\ / | \ ; |N4 | : : / Area 2 10 \ | 10 Area 0 1 \| Area 1 + | : : | | `. | RT7| | \ | | RT4 / '--. _.- | o----1-+---`.o-----30-----o ,' `------'' | /| | RT3--. _.-' | / | ;| `------'' | ," 1 | `. / | , | 1 RT8| | | / o | | ," | , | / | | | o----------| / | RT9 N2 | / `-. | ," `-._ o / `-.-----------+ Figure 1 A sample Autonomous System Tao Zijin Expires April 20, 2012 [Page 6] Internet-Draft SAVO SAVI October 2011 In Figure 1, to router RT2 and RT4, the route to network N4 is via RT1 and RT3 separately, but from the source address validation perspective, both the RT1 and RT3 are the valid source routers for source address N4. SAVO satisfies the basic source address validation principles which are hierarchical architecture (multi-fence solutions), solutions for IPv6 first, proactive protection, incrementally deployable (incomplete deployment is still beneficial), provide incentive for deployment. The most important feature of SAVO may lies in that the user can deploy the SAVO independently to get the info of all the possible incoming paths of the OSPFv3 route prefix without any communication with other routers. SAVO SAVI is designed to provide a calculation method of all the valid incoming interfaces of certain OSPF route prefixes only based on local OSPF Link State (LS) information. This deployment model is at the level of intra-AS source address validation in the SAVA Testbed [RFC5210]. Even with partial deployment, SAVO can proactively limit an attacker's ability to spoof packets. This design allows the user to determine which interfaces the packets of certain source address should arrive by its own route information without additionally communicating with other routers. So, if a router which has deployed SAVO, it can filter the packets with source addresses matched with the OSPF route prefix and coming from the invalid incoming interfaces calculated by SAVO at the ingress side while allowing the same packets coming from other valid interfaces. The filter method used by the router may be Access Control List (ACL), iptables (for Linux), or others. As the SAVO belongs to Ingress Filtering, it is natual to compare SAVO with Reverse Path Forwarding [RFC2827]. The main advantage of SAVO over RPF is that it can deal with the asymmetric routing, which will lead to improperly discarding packets with valid source addresses when RPF is used. Another advantage may be at the level of filtering granularity, to the RPF, when there is a default route, the RPF may accept the packets with spoofed source when the router can not find the completely matched incoming interface, but to the SAVO, the matching operation is much more accurate for the filtering rules are much more concrete and address pertinent. The main idea of SAVO comes from the iDPF which is proposed by Z. Duan et al in a paper named "Controlling IP Spoofing through Interdomain Packet Filters", where the iDPF is mainly proposed to deal with the source address forging in the inter-domain cases, where the BGP protocol is used as the main routing protocol. Tao Zijin Expires April 20, 2012 [Page 7] Internet-Draft SAVO SAVI October 2011 To SAVO and iDPF, every router judge the reality of source addresses by its own routing information, and to do the verification by filtering the packets with the forged source address. The filtering rules formed by SAVO do not depend on any extra communication but the OSPF itself. SAVO tries to find all the valid source routers for the indicated source address prefixes, but in some cases SAVO can not assure the unique incoming source of some source address prefixes, that is to say the SAVO router may pass the packets with truly spoofed source addresses but can't filter the packets with valid source addresses. 2. SAVO SAVI specification 2.1. The SAVO Basic Algorithm for Calculating the Possible Valid Incoming Interface (BA-VII) of a certain router in a area The SAVO Basic Algorithm (BA-VII) is used to calculate the possible VII for a certain router in a area. The VII of a source address prefix can be indirectly got by the SBA with the associated router of the prefix in a designated area. As the OSPF uses the shortest path algorithm proposed by Dijkstra to calculate a route to a certain router, for the SAVO router to calculate the possible valid incoming interface (VII) from another router to itself is just equal to finding the last hop of itself in the reverse shortest reaching path (RSRP) of that router. Appendix A gives an equal-cost parent-vertex (the lasthop of the current router in the Reverse Shortest Path Tree) search algorithm and the detailed process of BA-VII. The reverse shortest reaching path (RSRP) is just the shortest path by which another router used to reach the current router in a area. From the current router's perspective, the RSRP is a shortest path with another router as root, instead of itself. The RSRP may also have multiple equal-cost paths which is the same as that in OSPF [RFC2328]. The best way to get the RSRP is to calculate the Reverse Shortest Path Tree using the destined router as the root by the LSDB information stored in the OSPF router, which is the same as that used in getting the SPT with the current router as root. As you know, every route prefix is associated with an original router via which the host send its packets with the source address in that prefix into the network. To a route prefix of a calculating router learned from other routers and stored in its routing table, the word 'original' means all the routers which have advertised the same route prefix of the type of intra-area, inter-area or AS-external. For the intra-area route prefix, it is associated with a Router-ID or Tao Zijin Expires April 20, 2012 [Page 8] Internet-Draft SAVO SAVI October 2011 Network-ID. For the inter-area route prefix, it is associated with a Router-ID. For the AS-external route prefix, the situation is a little complicated as the advertiser of the route may be inter-area and the associated router is determined by the location of the 'forwarding address' field in the AS-external LSA. As the router calculates the route to a certain destination route prefix in a area using the shortest-path tree with itself as the root and each router in a area has an identical link-state database [RFC2328], it is natural to use the information in the existing shortest-path tree (SPT) to speculate the reverse shortest reaching path of a certain router. If every link's cost in a area, which is defined as 'associated with the output side of each router interface' in [RFC2328] is the same (called Symmetric Link, SL) to each attached router, then the area is defined to be an Symmetric Area (SA), otherwise the area is defined to be an Asymmetric Area(ASA). In a SA, a router's Shortest Path (SP) to another router is the same as the Reverse Shortest Reaching Path (RSRP) from that router. In an ASA, the SP may be distinct from the RSRP and the router has to calculate the RSRP with the target router as root using the link- state information stored in its database, just as the computing of shortest path tree with itself as root. Since each participating router in a area has an identical and complete link-state database, it is possible to do the RSRP computation for all routers in the area. At the same time, as the symmetry and/or asymmetry of an area may vary due to some newly received router LSA and Network LSA, the symmetry of the area MUST be checked when the topology have changed. Figure 2 expresses the actions to be taken after a SAVO router has received a new Router LSA or Network LSA. If the network topology changes frequently, the ACCURATE mode may lead the router not able to keep with the quick change of the route but the SIMPLE mode only need the symmetry information of a certain area which is much easier to get than to get every router's RSPT in the area. So, there exists two ways to calculate the possible incoming interfaces of a packet that one is using the SPT of itself, the other is calculating the RSRP with the role of another router. The first way is SIMPLE, but may be wrong when there are asymmetric links. The second way is ACCURATE but lead to a higher calculation burden. Two RSRP calculation modes are proposed here: one is SIMPLE mode, which uses the SPT of the router with itself as root to compute the possible incoming interfaces of a certain source address (prefix), Tao Zijin Expires April 20, 2012 [Page 9] Internet-Draft SAVO SAVI October 2011 which may be wrong when there are one or more asymmetric link(s) the other is ACCURATE mode, which uses the link-state information to calculate the target router's shortest path to itself, which may introduce extra computation load. The ACCURATE mode is based on the indicated router's RSRP which can be calculated by the same link- state information used to calculate the SPT. As the name of ACCURATE mode has indicated, it can speculate the valid incoming interfaces of certain source address prefixes accurately. When the ACCURATE mode is implemented and used in a SAVO router, an extra calculation thread different from the current OSPF routing calculation thread may be introduced to reduce the performance impact on the routing process. +-------------------------------------+ | Received Network LSA or Router LSA | +---+--------------+------------------+ | +------------------+------------------+ | (Re)Compute the SPT with itself as | | the root in the corresponding area| +-----------------+-------------------+ | _,.+.__ __..--'' `'`--...__ No (SIMPLE mode) ,.,-'' ACCURATE mode ? `i=..._________ `--.._ _,.--' | `'--.._ _,.--' | `'-+'' | |Yes | +-----------------------------------+ +-----------------+ | (Re)Compute the Reverse SPT with | | (Re)Compute the | | every other router as the root | | symmetry of | | in the cooressponding area | | of the area | +-----------------------------------+ +-----------------+ | __.--' | __.--' | __.--' +-----------------------+--'----------------------------+ | (Re)Compute the Valid Incoming Interfaces of the | | corresponding source address prefix using the new RSPT| | or area symmetry | +-------------------------------------------------------+ Figure 2 Actions after newly received a Network LSA or Router LSA Although the SIMPLE mode is not so accurate as the ACCURATE mode and may be wrong when there are asymmetric links, it is much more efficient in calculation than the ACCURATE mode. When there are asymmetric links in a area, the remedy to correct the mistake of the SIMPLE mode can be adding all links of that area in the current router as the possible incoming interfaces in that area. Tao Zijin Expires April 20, 2012 [Page 10] Internet-Draft SAVO SAVI October 2011 When calculating the valid incoming interfaces for the SIMPLE mode, the only work that is need to do is to judge whether an area is symmetric or not, and if any one link of the area is not symmetric then the area is not symmetric anymore and no any other computation is needed, so the computation burden is light to the SAVO router and the SIMPLE mode can adapt to the change of the network topology quickly. If the area is symmetric, the result of SIMPLE mode is the same as ACCURATE mode but to the asymmetric area, its result is not so accurate that there may be more cases that the packets of spoofed source addresses are passed without being filtered than that of ACCURATE mode and the probability of falsely passing that kind of packets is dependent on the number of interfaces in a area. The extra computation load introduced by the ACCURATE mode depends on the number of routers and links in a area and for each router except the calculating router itself the Dijkstra shortest path algorithm has to be run again if the router-LSAs or network-LSAs in a certain area have been changed. So the running times of Dijkstra algorithm in a SAVO router with ACCURATE mode is at least accumulation of the number of routers in each area decreased by one, which may be a high computation burden on the router. For an area with n nodes, the SAVO router needs to compute the Reverse Shortest Path Tree (RSPT) for n-1 times and the SPT for 1 time. As the algorithm complexity of Dijikstra is O(n^2), the complexity of the ACCURATE mode is O(n^3), which is a rank higher than that of the SIMPLE mode. The ACCURATE and SIMPLE mode forms the basics of the SAVO algorithm, and all the other algorithms used to calculate the incoming interfaces of the three types of route which will be introduced below is based on the basic algorithm of the valid incoming interfaces (BA- VII). 2.2. Calculating the Incoming Interfaces for Source Addresses in intra- area route prefix This section explains how to calculate the valid incoming interfaces for the source address in intra-area route prefix. Since the intra-area route is calculated by the intra-area-prefix- LSAs, it is natural to analyze the possible incoming interfaces of a intra-area route from the intra-area-prefix-LSAs stored in the LSDB. From the OSPF specification, if the router has received all the intra-area-prefix-LSA, inter-area-prefix-LSA, AS-external-LSA which are of the same prefix, then the router should set the route type to intra-area because the intra-area route type is preferred over the other two types. The following steps are the process to analyze the Tao Zijin Expires April 20, 2012 [Page 11] Internet-Draft SAVO SAVI October 2011 possible incoming interface when the router has just got an intra- area route and at the last step the algorithms to calculate the VII of the inter-area route and AS-external route are used to analyze the exceptional cases when there are LSAs of the type of inter-area or AS-external and have advertised the same route prefix, and the other two algorithms will be introduced below. (1) Search all the valid intra-area-prefix-LSAs that match the route prefix in all area's LSDB; (2) If the corresponding LSA is found, then look up what type of LSA is the current LSA referred to, which may be Network LSA or Router LSA; (3) If the referred LSA is of Network Type, then find what routers are the corresponding Network LSA associated to and the associated routers is the possible source router of that route prefix except the current router itself. The attached routers of a network link must be associated routers but the associated routers may not be the attached routers since the associated routers may be introduced indirectly by the DR who has advertised the Network LSA; (4) If the referred LSA is of Router Type, then the corresponding router is the associated router; (5) Get the VII of the associated routers by the Basic Algorithm of the Valid Incoming Interfaces for a given router(BVIIA), and the input parameter of the BIIA are the router id of the associated router, the corresponding area and the router id of myself; (6) Further more, consider the exceptional cases which may exist when the router has received some inter-area-prefix-LSAs and/or AS- external LSA with the same prefix just as there are the routes with the same prefix which type is inter-area or AS-external. The corresponding methods to deal with these two kinds of LSAs may be described below. 2.3. Calculating the Incoming Interfaces for Source Addresses in Inter- Area Route Prefix As in the previous intra-area cases, when the router has got a inter- area route there may exist some AS-external LSAs advertising the same prefix as the inter-area route, since the inter-area-prefix-LSAs are preferred over the AS-external LSAs. The following steps are the process to analyze the possible incoming interfaces when the router has just got an inter-area route and at Tao Zijin Expires April 20, 2012 [Page 12] Internet-Draft SAVO SAVI October 2011 the last step the algorithm to calculate the VII of the AS-external route are used to analyze the exceptional case when there are some AS-external LSAs with the same prefix, and the algorithm for the AS- external route will be introduced as follows. (1) Search all the valid inter-area-prefix-LSAs that match the route prefix in all area's LSDB and can be used to generate that route; (2) If the corresponding LSA has been found, then the advertiser of that LSA is the associated router; (3) Get the VII of the associated router by Basic Algorithm of the Valid Incoming Interfaces for a given router(BVIIA), and the input parameter of the BIIA are the router id of the associated router, the corresponding area and the router id of myself; (4) Furthermore, consider the exceptional case which may exist when the router has received some AS-external LSA with the same prefix just as there are the routes with the same prefix which type is AS- external. The corresponding methods to deal with this kind of LSAs may be described below. 2.4. Calculating the Incoming Interfaces for Source Addresses in AS- External Route Prefix The VII algorithm for the AS-external route is a little more complicated than that of the other two types of route, for which the reason is that the AS-external route depends on the location of the advertised router or the forwarding router listed in the LSA, which may be intra-area or inter-area depending on whether or not the router has received some inter-area-router-LSAs. From OSPF specification, it is known if the router does not have any route information of the forwarding router, the AS-external LSA should be ignored. So if the router has got an AS-external route, it must exist some route information of the forwarding router in the SPF tree of one area or the top-level border-router table. The VII algorithm of the AS-external route is as follows. (1) Search the router's top level LSDB to find the proper AS-external LSA which match the AS-external route prefix; (2) According to the OSPF specification, if the forwarding router field of the found LSA is zero, then the forwarding router is the advertising router of the LSA, or the forwarding router is indicated by this field value. So first search the forwarding router in each area's SPF tree to see if the router id of the forwarding router is in it and if found, then calculate the VII of the forwarding router Tao Zijin Expires April 20, 2012 [Page 13] Internet-Draft SAVO SAVI October 2011 by the Basic Algorithm of the Valid Incoming Interfaces for a given router(BVIIA); (3) Search in each area's LSDB to find if there are some matched inter-area-router-LSAs which destination router id field describes the inter-area route to the forwarding router, and if it exists such LSAs, then the advertising routers of those LSAs should be the associated routers and calculate the VII of those routers in the corresponding area by the BA-VII. 3. Routing Policy Considerations In general, most current routing policies of OSPF is about how to deal with the formed routes, such as whether it is allowed to redistribute a certain route into the OSPF. With the current experience there are no routing policies set to deal with the received LSAs nowadays. When the formed route matches a route policy rule (route-map), it is dealt with as the rule has indicated. From the perspective of accuracy and correctness of the routing and SAVO rules' calculation, the routing policy does not affect the calculation result directly. On the other hand, SAVO calculation only needs the OSPF's LSDB info and does not depends on the routing policy. If needed, the network administrator may add some source address validation rules to permit or deny the indicated incoming interfaces for some source addresses according to the special situation of the current network. 4. Security Considerations First of all, it should be noted that the function of the SAVO solution heavily depends on the security of the OSPF protocol itself. It is assumed that all the OSPF protocol packets are authenticated and believable, so the router's link state information is credible. In particular, according to OSPFv3 specification, the security of the OSPF can be achieved by the IP Authentication Header (see [IPAUTH]) and the IP Encapsulating Security Payload (see [IPESP]). Since SAVO does not generate and send any protocol packets, the SAVO itself does not need any additional security scheme. 5. Deployment Considerations Though the SAVO can be deployed arbitrarily, the network manager can select the most appropriate sites to deploy SAVO to decrease the calculation cost and at the same time to achieve the best prevention effects as the AS is under a unified management. The desired goal of Tao Zijin Expires April 20, 2012 [Page 14] Internet-Draft SAVO SAVI October 2011 SAVO is try to deploy it in less number of sites but to achieve the same coverage ratio and the same effectiveness as SAVO was deployed widely. From the OSPF specification, we know that the whole network has a backbone area (which is denoted as Area 0) and every inter-area route must transit through area 0 and the related area-border routers. In SAVO specification, if the source address prefix is intra-area, the VII can be calculated by the RSRP or SPT directly. So the most appropriate deployment sites may lie in all the area-border routers as the area-border routers knows more intra-are route than other routers. When all the area borders have deployed SAVO, they can form a source address forging prevention circle as the forged packets can not transit through the area border into the backbone. The prototype of SAVO has been implemented in the OSPF6 software package of Quagga Routing Suite in Linux by this draft's proposers. 6. References 6.1. Normative References [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC5340] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", RFC 5340, December 1999. [RFC2827] Ferguson, P. and D. Senie, "Network Ingress Filtering: Defeating Denial of Service Attacks which employ IP Source Address Spoofing", BCP 38, RFC 2827, May 2000. 6.2. Informative References [DPF] K. Park and H. Lee, On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets, in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001. [iDPF] Z. Duan, X. Yuan, and J. Chandrashekar, "Controlling IP Spoofing through Interdomain Packet Filters," IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, vol. 5, pp. 22-36, 2008. Tao Zijin Expires April 20, 2012 [Page 15] Internet-Draft SAVO SAVI October 2011 Appendix A. SAVO Related Algorithms A.1. Equal-Cost Parent-Vertex Search Algorithm(ECPS) for a known vertex in a SPF tree If we have got the Reverse SPF tree and want to know from which interface will the root node come to the current node, it can not be got directly from the Reverse SPF tree as from the SPF tree because there is no direct nexthop information in the Reverse SPF tree. So the incoming interfaces of a certain vertex in the Reverse SPF tree can only be got indirectly from its parent vertex which can be calculated by the following code. Further more, if we have got the parent vertex information, we can get the incoming interfaces from the router's LINK LSDB. The following code is described in C-like code, and each vertex is represendted as a structure of ospf6_vertex, the root node is v and has a child list for each vertex in the SPF tree and the vertex to be searched is represented as search_vertex_id. void equal_cost_parent_vertex( struct prefix search_vertex_id, struct ospf6_vertex *v, struct ospf6_vertex **prev, int prev_vertex_num) { struct listnode *node, *nnode; struct ospf6_vertex *c; for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c)) { if(prefix_same(&c->vertex_id, search_vertex_id) && (*prev_vertex_num) < NUM_EQUAL_COST_PARENT_VERTEX) { /* have found the matched vertex */ if(*prev_vertex_num == 0) { /* have found the first one, only record */ prev[*prev_vertex_num] = c->parent; /*record the parent vertex */ Tao Zijin Expires April 20, 2012 [Page 16] Internet-Draft SAVO SAVI October 2011 (*prev_vertex_num) ++; vertex_cost = c->cost; }else if(c->cost < vertex_cost) { prev[0] = c->parent; (*prev_vertex_num) = 1; vertex_cost = c->cost; }else if(c->cost == vertex_cost) // equal-cost vertex { prev[*prev_vertex_num] = c->parent; (*prev_vertex_num) ++; vertex_cost = c->cost; } } equal_cost_parent_vertex (search_vertex_id, c, prev, prev_vertex_num); } A.2. Basic Algorithm of the Valid Incoming Interfaces for a given router(BVIIA) If the router wants to calculate all the possible incoming interfaces for a given router in an area, then the BVIIA is to be used. The BVIIA is the basic of the whole SAVO scheme, so it is named 'basic'. The input parameter of the BVIIA is the current router id, the router id of the router to be calculated and the given area; the output results are the valid incoming interfaces of the destination router. The SPF tree of the area with the destination router as the root is known beforehand, and the ACCURATE and SIMPLE modes are both considered in the BVIIA. The resulted duplicate incoming interfaces are to be ignored when they had been added to the router before. Tao Zijin Expires April 20, 2012 [Page 17] Internet-Draft SAVO SAVI October 2011 The whole process of the BVIIA is listed as follows. (1) To determine if the area is symmetric or not, for that the area is symmetric if and only if all links in the area are symmetric. A link is symmetric when the two cost of each direction of the link are equal; (2) If the area is symmetric, the router looks up the SPF tree of the area with itself as the root to get the nexthop and output interface's index (ifindex) information for the destination router and the information can be used as the valid input interfaces for the destined router. For the equal-cost multi-path cases, there may be multiple equal-cost nexthops and output interfaces for the destined router; (3) After we have got the valid incoming interface's ifindex value, the ifindex(s) can be added the router's access control system if no duplicate ifindex value had been added before; (4) If the area is not a symmetric area, then the router has to differentiate between the ACCURATE mode and the SIMPLE mode. If the current working mode of SAVO is SIMPLE, then all interfaces in the area are considered to be valid. Else, the router has to look up the reverse SPF tree which root is the destined router to find the valid incoming previous hop information for the current router by the BVIIA; (5) If the router has got the valid previous hop information, then it need to match the previous hop(s) with the Link LSAs stored in each area's link LSDB to get the valid incoming interface's ifindex value; (6) Step (3) will be needed again to add the desired ifindex value to the access control system. According to the OSPF specification, if the forwarding router field of the found LSA is zero, then the forwarding router is the advertising router of the LSA, or the forwarding router is indicated by this field value. First, it is to search the forwarding router in each area's SPF tree to see if the router id of the forwarding router is in it and if found, then calculate the VII of the forwarding router by the Basic Valid Incoming Interface Algorithm (BVIIA). (3) Search in each area's LSDB to find if there are some matched inter-area-router-LSAs which destination router id field describes the inter-area route to the forwarding router, and if it exists such LSAs, then the advertising routers of those LSAs should be the associated routers and calculate the VII of those routers in the corresponding area by the BIIA. Tao Zijin Expires April 20, 2012 [Page 18] Internet-Draft SAVO SAVI October 2011 7. Conventions Used in This Document 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]. In this document, these words will appear with that interpretation only when in ALL CAPS. Lower case uses of these words are not to be interpreted as carrying RFC-2119 significance. In this document, the characters ">>" preceding an indented line(s) indicates a compliance requirement statement using the key words listed above. This convention aids reviewers in quickly identifying or finding the explicit compliance requirements of this RFC. Authors' Addresses Tao Zijin National University of Defense Technology DeYa Road 47 Changsha, Hunan Province 410073 CHINA Phone: 86 731 84574844 Email: taozj888@163.com URI: http://www.nudt.edu.cn Tao Zijin Expires April 20, 2012 [Page 19]