Poison-path routing policy

In one embodiment a system, method, and related apparatus are described for a router which receives notice of a route including a hijacked prefix having a hijacked prefix netmask length, searches a set of routes with equal or shorter netmask lengths that cover the hijacked prefix in order to find at least one route which has no autonomous system (AS) in common with the particular route comprising the hijacked prefix, if a specific route is found with a netmask length equal to or shorter than the hijacked prefix netmask length, then the specific route which has been found is a determined alternative route, extracts the particular route comprising the hijacked prefix from the specific route if said specific route has a netmask length covering a larger address range than the hijacked prefix netmask length, inserts the determined alternative route in a routing table, and modifies attributes of the determined alternative route in the routing table according to the determined alternative route. Related systems, methods, and apparatus are also described.

TECHNICAL FIELD

The present disclosure generally relates to communication networks.

BACKGROUND

An autonomous system (AS) is a set of routers under a single technical administration, using an interior gateway protocol (IGP) and common metrics to determine how to route packets within the AS, and using an inter-AS routing protocol to determine how to route packets to other ASes. It has become common for a single AS to use several IGPs and sometimes several sets of metrics within the AS. The use of the term “Autonomous System” stresses the fact that, even when multiple IGPs and metrics are used, the administration of a first AS appears to other ASes to have a single coherent interior routing plan and presents a consistent picture of what destinations are reachable through the first AS.

The Border Gateway Protocol (BGP) is a standardized exterior gateway protocol designed to exchange routing and reachability information among ASes on the Internet. The protocol is often classified as a path vector protocol but is sometimes also classed as a distance-vector routing protocol.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

In one embodiment a system, method, and related apparatus are described for a router which receives notice of a route including a hijacked prefix having a hijacked prefix netmask length, searches a set of routes with equal or shorter netmask lengths that cover the hijacked prefix in order to find at least one route which has no autonomous system (AS) in common with the particular route comprising the hijacked prefix, if a specific route is found with a netmask length equal to or shorter than the hijacked prefix netmask length, then the specific route which has been found is a determined alternative route, extracts the particular route comprising the hijacked prefix from the specific route if said specific route has a netmask length covering a larger address range than the hijacked prefix netmask length, inserts the determined alternative route in a routing table, and modifies attributes of the determined alternative route in the routing table according to the determined alternative route. Related systems, methods, and apparatus are also described.

Example Embodiments

Reference is now made toFIG. 1, which is a simplified pictorial illustration of an exemplary communication network100comprising a plurality of autonomous systems (AS, referred to herein in the plural as “ASes”)105,110,115,120,125,130,140constructed and operative in accordance with an embodiment of the present invention. Each of the plurality of ASes105,110,115,120,125,130,140comprises at least one router (not shown) on which Border Gateway Protocol (BGP) is implemented. It is appreciated that although the present disclosure focuses on BGP routers, any network appliance such as a switch, a router, etc., on which the BGP protocol is implemented, may comprise an embodiment of the of the present disclosure, as described herein. Network paths which are in use between the ASes of the plurality of ASes105,110,115,120,125,130,140are also indicated inFIG. 1. The term “router” as used herein, in all of its various grammatical forms, refers to a device that forwards data packets along networks. A router is connected to at least two networks, commonly two local area networks (LANs) or wide area networks (WANs) or a LAN and its internet service provider's network. Routers are located at gateways, the places where two or more networks connect.

BGP routers exchange and propagate route information amongst themselves. BGP routing is described in detail in RFC 4271, available on the Internet at www.rfc-base.org/txt/rfc-4271.txt. Each BGP router has a plurality of route entries used in matching to determine a preferred route for traffic destined for an IP address. In each BGP router, traffic destined for an IP address is matched to the route entry with the most specific IP address prefix (longest match) that covers the destination IP address and forwarded to the first AS of the route entry's AS path as the next AS hop.

One particular threat that this routing infrastructure faces is so called “prefix hijacking” attacks. It is possible for a BGP router which has been hijacked (i.e. a “rogue BGP router”) or BGP router that is not functioning properly to announce a false AS level route towards a prefix. If a BGP router is polluted by this announcement and replaces the legitimate route entry for this prefix with the false route in its routing table, any future Internet Protocol (IP) data traffic destined for any IP address within a victim prefix will be forwarded along this false route, causing such traffic being unrightfully intercepted, manipulated, or dropped—a result often referred to as IP traffic being “hijacked.” The term “routing table”, as used herein, is understood to refer to a set of rules, often viewed in table format, that is used to determine where data packets traveling over an IP network will be directed. Routing tables are typically found in routers or other IP-enabled networking devices.

As noted above, ASes, such as the plurality of ASes105,110,115,120,125,130,140communicate using the BGP. BGP Routers in the various ASes105,110,115,120,125,130,140maintain respective tables of IP networks or prefixes, which designate network reachability among the various ASes105,110,115,120,125,130,140. Reference is now briefly made toFIG. 2A, which depicts an exemplary routing path210between a first AS110and a second (i.e. target) AS115via intermediate AS125and intermediate AS120.

Reference is now made toFIG. 2Bwhich is a simplified pictorial illustration of the exemplary communication network ofFIG. 1, depicting a hijacked routing path220between a hijacking AS105(now depicted with dotted lines, indicative of its status as a hijacking A1S), and the a second (i.e. target) AS115. The term “hijacking AS105” is understood to mean that a hijacker located in AS105has committed an act of IP address prefix hacking. Accordingly, and by contrast to the first exemplary routing path210depicted inFIG. 2A, if the hijacker located in AS105has committed an act of IP address prefix hacking, then routing path220, between the hijacking AS105, and the second (i.e. target) AS115is now the “hijacked routing path220”. It is noted that intermediate AS120is in both the first exemplary routing path210ofFIG. 2Aand the hijacked routing path220.

Reference is now made toFIG. 3, which depicts the exemplary communication network100ofFIG. 1, depicting a routing path210between the first AS110and the second (i.e. target) AS115via intermediate AS120, and intermediate AS125, where the routing path between two of the ASes120and115comprises a hijacked path220. The hijacked routing path220between the hijacker, i.e., hijacking AS105and the second (i.e. target) AS115, via AS120, is indicated with dotted arrows. It is noted that a routing sub-path310, comprises the hop between intermediate AS120and the second (i.e. target) AS115. The sub-path310is a sub-path of routing path210which extends between the first AS110and the second (i.e. target) AS115via AS125and AS120. The sub-path310also overlaps the path between hijacking AS105and the second (i.e. target) AS115. That is to say, routing sub-path310has been hijacked.

In order to prevent selection of routes via the routing sub-path310, a new routing-policy is implemented by the BGP routers. At a first stage, a hijacked route is detected. It is appreciated that the detection of the hijacked routing sub-path310is performed by means which are known in the art, and not described herein.

It is appreciated that an administrative network message can spread from BGP router to BGP router announcing a discovered hijacked path (i.e. hijacked routing path220). Accordingly, when the second (i.e. target) AS115receives routing updates from its neighbors, the routing update might include an announcement of the hijacked path.

Upon detection of the hijacked routing sub-path310, a new routing policy is invoked. The new routing policy finds an alternative route so that the alternative route does not have any hops in common with the hijacked route. As was noted above, hijacked routing sub-path310is common to the first exemplary routing path210and the hijacked routing path220. An acceptable alternative path is one in which there are not any ASes in common in the routing path between AS110and AS115and the hijacked routing path220. It is necessary to remove common ASes from the routing path, e.g. AS120, since a packet arriving at an AS with a routing path which is common to both the first exemplary routing path210and the hijacked routing path220will proceed along the path with the longer netmask i.e. the hijacked route.

In order to find a non-hijacked path, a processor comprised in the BGP router which is associated with the second AS (i.e. target)115and has the hijacked routing sub-path310in its routing tables, searches the routing table for a route that has no AS in common with the AS path of the hijacked route220and has a netmask length which is the same length as the netmask of the hijacked route220or a shorter netmask if there is no route with the same length netmask as the netmask of the hijacked route.

Reference is now made toFIG. 4, which is simplified pictorial illustration of the exemplary communication network100ofFIG. 1, depicting a first alternative path410to avoid the path hijacked by the hijacking AS105ofFIG. 3. By way of example, the first AS110is depicted as having a network prefix of 198.51.100.0/22. The hijacking AS105is depicted as having a more specific, and therefore preferred network prefix of 198.51.101.0/24. The first alternative path410, depicted inFIG. 4, is via intermediate AS125which has a network prefix of 198.51.102.0/22. Since the intermediate AS125and first AS110have the same netmask length (i.e. /22), and a path from the second (i.e. target) AS115to first AS110exists via intermediate AS125and via AS130, the new policy implements the path from the first AS110to the second (i.e. target) AS115via the intermediate AS125and fourth AS130, thereby avoiding sub-path310via AS120.

Accordingly, the BGP router of second AS (i.e. target)115finds a path to use to route packets to the first AS110using a less specific /22 netmask route in preference to a /24 netmask route. A processor of the BGP router of second AS (i.e. target)115extracts the /24 netmask route from the /22 netmask route, and passes the new /24 netmask route (which has been subjected to the extraction) to network forwarding hardware. Specifically, the /24 netmask route, originating at the hijacking AS105, is the hijacker's route. The /24 netmask route passes through intermediate AS120the next hop of which, routing sub-path310, comprises a hijacked path. The BGP router of the second (i.e. target) AS115therefore must find a route utilizing a /24 netmask that points to fourth AS130in order to avoid routing over intermediate AS120. That is to say, the new route which utilizes a /24 netmask should avoid intermediate ASes which are affected by the hijacking, Just dropping the hijacked route alone from the BGP routing tables is a necessary but not sufficient precaution. In simpler terms, the overlapping, hijacked paths are removed from the routing.

Once the BGP router of first AS110finds a path to use to route packets to the second (i.e. target) AS115using the less specific /22 netmask route in preference to the /24 netmask route, as detailed above, the new route is created in the routing table. The new route will have the same prefix and netmask as the hijacked route, as well as the same BGP attributes as the first route. BGP attributes include, by at not limited to certain well-known mandatory attributes, such as AS-path, the autonomous systems that routing information passed through to get to a specified route, and used to prevent routing loops in BGP; next-hop; and so forth. Additionally, certain attributes are well-known discretionary attributes, and optional attributes. Other exemplary attributes include local preference, i.e. the preferred route for a given path; and Multi-Exit Discriminator (MED), an optional nontransitive BGP attribute, which provides a hint to external neighbors about the preferred path into an autonomous system (AS) that has multiple entry points. The MED is also known as the external metric of a route. A lower MED value is preferred over a higher value. Other BGP attributes are known to persons of skill in the art.

If, for whatever reason, a route used to create a new route is deleted from BGP routing tables, then the newly created routes in the BGP tables need to be removed. By way of example, at some point, subsequent routing updates may occur which require changing routing, which may cause the new route to be deleted from BGP routing tables. In such a case a new route may be created, i.e., alternative path410, with a longer (i.e. less specific) netmask between first AS110and the second (i.e. target) AS115. In order to implement the update, the BGP table in the BGP router of the second (i.e. target) AS115is updated in order to add an indication to the alternative path410in the BGP table that the alternative path410was created with a longer netmask. Entering said indication in the BGP table provides a fallback so that if the alternative path410in the BGP table is deleted, the BGP router is able to revert back to the original poisoned route, routing sub-path310and to then find a new alternative routing path. An indication that the alternative path410is the /24 route derived from the /22 route is stored, so that if and when the original route (i.e. the /22 route) is deleted, the new /24 route (i.e. the alternative path410) will also be deleted. The BGP router performs the steps described above to find the new alternative routing path at the time of deletion.

Additionally, the poisoned route is put into a new, separate routing table, stored as a poisoned route table, so that if a better alternative route becomes available (i.e. a route with a longer netmask), the BGP router of first AS110may switch to the better alternative route and while still avoiding the poisoned route. It is appreciated that switching to the better alternative is not urgent, so that the BGP router may episodically walk the poisoned route table and determine if the better alternative route is presently available. It is also appreciated that if for some reason the poisoned route is no longer poisoned (for instance the rouge BGP router which was been hijacked is no longer hijacked), it may be desirable to restore the original route which is now no longer poisoned.

Reference is now made toFIG. 5, which is a simplified flowchart diagram depicting a method for one embodiment of the poison-path routing policy in the exemplary communication network ofFIG. 1. The method describes a method for invoking a new route at a BGP router in order to avoid a hijacked route. At step610, notice is received at the BGP router of a route comprising a hijacked prefix having a first netmask length. The term “notice” as used in the present disclosure and claims, in all of its various grammatical forms, refers to messages sent over a network by networking devices indicating network information and other associated information, such as, but not limited to, routing updates. Such notices and messages are often sent at regular intervals, or after a change in network topology.

By way of example, and with reference toFIG. 3, the BGP router of first AS110receives notice that the route to the second (i.e. target) AS115comprises a hijacked hop, sub-path310. As was noted above in the discussion ofFIG. 3, the notice may be received as part of a routing update received from neighboring BGP routers.

In step620, a set of routes with shorter netmasks that cover the hijacked prefix are searched in order to find at least one route which has no common autonomous system (AS) in the hijacked route. If a route, such as alternative path410(FIG. 4) is found with a netmask length equal to or shorter than the first netmask length of the hijacked prefix, then the route which has been found is the determined alternative route. In step630, the route comprising the hijacked prefix is removed from the routing tables of the BGP router if a route is found with a netmask length covering a larger address range than the first netmask length.

In step640the determined alternative route is inserted in a Border Gateway Protocol (BGP) table at the BGP router. Finally, at step650attributes of the determined alternative route in the BGP table at the BGP router are modified according to the invoked new route.

It is appreciated that software components of the present invention may, if desired, be implemented in ROM (read only memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques. It is further appreciated that the software components may be instantiated, for example: as a computer program product or on a tangible medium. In some cases, it may be possible to instantiate the software components as a signal interpretable by an appropriate computer, although such an instantiation may be excluded in certain embodiments of the present invention.

It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. Rather the scope of the invention is defined by the appended claims and equivalents thereof: