Prefix hijacking detection device and methods thereof

A method of placing prefix hijacking detection modules in a communications network includes selecting a set of candidate locations. For each candidate location, a detection coverage ratio with respect to a target Autonomous System is calculated. Based on the relative size of the coverage ratios, proposed locations for the prefix hijacking detection modules are determined.

FIELD OF THE DISCLOSURE

The present disclosure generally relates to communications networks, and more particularly relates to detecting prefix hijacking attacks in a communications network.

BACKGROUND

Communications networks, such as the Internet, are used increasingly to deliver a variety of services, including telephone communications, audio and video entertainment, financial transactions, and others. Such communications networks are subject to security risks, such as attempts by individuals or groups to inhibit the delivery of such services. Because of the number and amount of services delivered over communication networks, such security risks can have a large financial impact, both on service providers and their customers.

DETAILED DESCRIPTION OF THE DRAWINGS

FIG. 1shows a block diagram of a communications network100in accordance with one embodiment of the present disclosure. The communications network100includes a number of Autonomous Systems (ASes), including AS102, AS104, AS106, AS108, AS110, and AS112. As used herein, an Autonomous System refers to a set of network communications equipment, such as routers, servers, clients, and the like, such that the AS presents a common routing policy to the communication network. In an embodiment, an AS may be administrated by a single entity, such as a service provider or content provider. For example, an AS may be owned by an Internet Service Provider (ISP). In another embodiment, an AS may be owned by multiple entities that have agreed upon the common routing policy presented to the communications network. Because the allocation and distribution of Internet Protocol (IP) addresses from authorities are managed in address blocks in which IP addresses of the same block share the same address prefix, an AS may own one or more IP address prefixes to assign to equipments in the AS. Also because IP address prefix is used as index for organizing data routing entries by routers, the collection of network equipments that are assigned with IP addresses from the same IP address prefix form an individual routable network entity commonly referred to as a sub-network, and this common IP prefix hence becomes the address of the sub-network. In the illustrated embodiment, it is assumed that each of the ASes in the communication network100includes network communications equipment associated with a set of Internet Protocol (IP) addresses sharing one or more common prefixes. Thus, for example, AS102includes a set of communications equipment associated with a set of IP addresses having one prefix, while AS104includes a set of communications equipment associated with a set of IP addresses having a different prefix. For purposes of discussion, if an AS includes a set of communications equipment associated with a particular prefix, the AS is referred to as owning that prefix. It will be appreciated that an AS can own more than one prefix.

Each of the ASes is connected to other ASes via communication links between its routers and routers of the neighboring ASes. Routers that have such external connectivity are referred to as border routers and a pair of ASes that at least one border router of one AS has a direct communication link with at least one border of the other AS are referred to as neighboring ASes. Conceptually the inter-connectivity among ASes can be viewed as a communication backbone that allows communications between the neighboring ASes. However, in the illustrated embodiment, each AS is not directly connected to every other AS. Connected ASes can communicate with each other using an agreed protocol. For purposes of discussion, it is assumed that the ASes illustrated inFIG. 1communicate using the Border Gateway Protocol (BGP). Using BGP one AS can communicate using IP prefixes and the corresponding AS level path to reach the prefixes with each other. Such communications of prefixes are referred to as BGP updates. In one embodiment, ASes initially send BGP updates for prefixes of their own with the AS level path initialized to the corresponding sender AS to neighboring ASes. Upon receiving these BGP updates ASes update their routing tables and send the received BGP updates, with their own AS identifier appended to the corresponding AS level path of the BGP updates, to their neighboring ASes to propagate the knowledge. A BGP update can be illustrated with reference to an example, where AS102communicates an update to AS104, indicating that AS102owns a set of prefixes. In response, AS104can communicate the information to its routers and other communications equipment, which adjust their routing policies accordingly. In particular, if a network node at AS104originates a communication targeted to a network node associated with an IP address having one of the prefixes indicated by the update, the routers and other communications equipment ensures that the message is communicated from AS104to AS102. The communications equipment of AS102then routes the message to the target network node. To enhance communication efficiency, a BGP update can include information in addition to owned prefixes, such as suggested routing tables for messages targeted to a particular prefix. In one embodiment, BGP updates are communicated by routers at the edge of a particular AS. Such routers are referred to as a BGP router.

Because of the connections between ASes, the communication network100is subject to a security risk referred to as prefix hijacking, where a network node, such as a BGP router in an AS, provides a BGP update with a prefix that the AS does not own. In other words, prefix hijacking can occur when an AS indicates that it owns an AS that it does not, in fact, own. Prefix hijacking can occur intentionally or accidentally due to a BGP router malfunction. In either case, the hijacking can result in communications being misrouted. Communication of information that results, or could result, in a prefix hijacking is referred to herein as a prefix hijacking event. For example, communication of a BGP update having incorrect prefix information, indicating that an AS owns a prefix it does not in fact own, is a prefix hijacking event. Prefix hijacking events can also be referred to as prefix hijacking attacks.

To illustrate a prefix hijacking event, assume that AS104is the owner of prefix100, so that messages targeted to addresses having that prefix should be routed to AS104. AS106communicates a BGP update to AS102indicating that it is the owner of prefix100. This BGP update is a prefix hijacking event. If AS102considers that the route via AS106is better than the route via AS104for prefix100, routers of AS102will change the corresponding routing entries for prefix100to replace AS104with AS106as the next hop AS for forwarding packets. Accordingly, if a network node of AS102originates a communication targeted to an address associated with prefix100, it will be misrouted to AS106rather than to AS104. The misrouting can result in one or more of at least three possible outcomes: blackholing, interception, and imposture. If a misrouted message is blackholed, it is simply dropped by the AS that receives the misrouted message. A misrouted message can also be intercepted by a malicious entity, such as a hacker, for eavesdropping or recording. In addition, a malicious entity can become an impostor for the message target, responding to the source as if it were the proper target for the message. Any of these three outcomes can negatively impact network communications.

To inhibit prefix hijacking, it can be useful to detect when a hijacking event occurs. One way of detecting prefix hijacking is to insert devices at a network's ASes, where the devices are configured to detect network activity indicative of a prefix hijacking event. These devices are referred to herein as detection towers, or alternatively as hijack detection modules. Detection towers can detect prefix hijacking events in a number of ways. For example, in one embodiment a detection tower receives BGP updates from other ASes as if the tower were a BGP router. The detection tower can compare the BGP update to a database of known prefixes associated with different ASes and, based on the comparison, determine if the BPG update represents a prefix hijacking event. For example, if the BGP update associates an AS with a prefix that the database indicates is already associated with a different AS, the detection tower can determine that the BGP update represents a prefix hijacking event.

It is sometimes not feasible to locate a detection tower at each AS, due to cost or other considerations. Accordingly, as described herein, a computer device can be configured to select one or more locations for placement of detection towers to provide a designated amount of detection coverage for prefix hijacking events in the communications network100. This can be better understood with reference toFIG. 2.

FIG. 2shows a flow diagram illustrating a method of selecting locations for detection towers in a communications network in accordance with one embodiment of the present disclosure. At block202, a computer device, such as a desktop computer, laptop, server, workstation, or the like, accesses a data file representative of a network topology. As used herein, network topology refers to the arrangement of ASes in a network including the locations of the ASes relative to each other and the connections between ASes. It will be appreciated that a location in the network, including the location of a detection tower, may not refer to a physical location, but instead refer to the AS where the detection tower is located. A detection tower is located in an AS when it has access to the BGP updates or other routing information provided to that AS such that the detection tower is able to detect prefix hijacking events. In an embodiment, a detection tower is located in an AS when it is associated with a network address having a prefix owned by the AS. Thus, the location of a detection tower can indicate its location in the address space of a communications network, rather than the physical location of the device.

At block204, the computer device determines a set of candidate locations for placement of a detection tower. Each candidate location represents an AS where the detection tower could be located. The set of candidate locations can include all ASes in the network, or may be based on one or more heuristics. For example, the set of candidate locations can include only those ASes connected to a threshold number of other ASes.

At block206, a set of ASes that are not yet covered by detection towers is determined. An AS is not yet covered if a prefix hijacking event initiated at the AS and targeted to a designated AS will not be detected based on the current proposed locations of detection towers. Accordingly, if no locations for detection towers have been determined, all ASes of the network will not yet be covered and will be included in the set. If any prefix hijacking event launched from an AS and targeted to a designated AS will be detected by a detection tower located at a proposed location, the AS is covered with respect to the target AS.

At block208, the computer device determines detection coverage ratios for each of the candidate locations. The coverage ratio is based on the detection coverage for a candidate location. The detection coverage for a candidate location is number of ASes from which a detection tower located at the candidate location can detect an otherwise undetected hijacking event on a designated target AS. This can be illustrated by reference to an example illustrated atFIG. 3.

FIG. 3illustrates example detection coverage areas for the communication network100ofFIG. 1. The example ofFIG. 3assumes that the designated target of a prefix hijacking attempt is prefixes in AS104. Further, the example ofFIG. 3assumes that the candidate locations for the detection tower are AS102and AS110. The detection coverage is illustrated as area303, which includes AS102, AS106, and AS114, because a detection tower located at AS102can detect hijacking events targeted to AS104that originate from AS102, AS114, and AS106. In particular, a hijacking event originating from AS102, AS114or AS106and targeted to AS104would result in communication of a BGP update to a BGP router at AS102, resulting in detection of the hijacking event by the detection tower. Accordingly, the detection coverage for AS102with respect to a potential prefix hijacking event targeted at AS104is three ASes, referring to AS102, AS106, and AS114. The detection coverage area for AS110is illustrated as area311. Accordingly, the detection coverage for AS110is two ASes, because a detection tower located at AS110can detect hijacking events targeted to AS104that originate from AS110and AS112.

The detection coverage ratio for a candidate detection module location is determined by dividing the detection coverage for the candidate location by the number of ASes that can launch a hijacking event to the target AS. Thus, referring to the above example, it is assumed that ASes102,106,110,112, and114can all launch hijacking events with respect to the target AS104. It is further assumed that AS108cannot launch a hijacking event with respect to the target AS104, because a BGP update from AS108would only be provided to AS104, which would recognize the BGP update as a hijack attempt. Accordingly, the number of ASes that can launch a hijacking event to the target AS is five. Therefore, the detection coverage ratio for AS102is 3/5, while the detection coverage ratio for AS110is 2/5.

In an embodiment, the detection coverage ratio for the candidate locations is determined based on the number of uncovered ASes. In other words, if the computer device determines, based on the locations of detection towers, that a prefix hijacking event originating from a designated AS will be detected by the towers, the designated AS will not be included in the calculations of the coverage ratios. To illustrate using the above example, assume that detection towers have been placed such that a detection tower has been placed at AS112, such that a hijacking event originating from the AS112and targeted to AS104will be detected. Accordingly, the AS112is not considered when determining the detection coverage ratios with respect to AS104. Thus, the detection coverage ratio for AS102in this example will be 3/4, because AS112is not considered as an AS that can launch a potentially undetected hijacking event with respect to target AS104. Similarly, the detection coverage ratio for AS110will be 1/4.

At block210, the candidate location with the highest coverage ratio is added to the selected locations for placement of detection towers. At block212, the ASes covered by the selected detection tower locations for a designated target are determined, and these ASes are removed from the set of uncovered ASes. At block214, the candidate location that was selected for placement of a detection tower is removed from the set of candidate locations.

At block216, it is determined whether stopping criteria are met. In one embodiment, the stopping criteria are met after a threshold number of locations for detection towers have been selected. In another embodiment, the stopping criteria are met when it is determined that the gain in detection coverage from placing a detection tower at the most-recently selected candidate location is below a threshold. In still another embodiment, the stopping criteria are met when it is determined that the number of ASes in the set of uncovered ASes is below a threshold. In yet another embodiment, the stopping criteria is met when it is determined that the number of ASes in the set of uncovered ASes is zero.

If, at block216, it is determined that the stopping criteria have been met, the set of selected locations for detection towers is displayed at a display screen of the computer device, and is also stored at the computer device. The stored set of selected locations can subsequently be accessed, and detection towers placed in each of the ASes indicated by the stored set of locations.

If, at block216, it is determined that the stopping criteria have not been met, the method flow returns to block206and the set of candidate locations is again determined. Accordingly, the computer device iteratively selects detection tower locations that yield the larges detection coverage ratio on remaining uncovered ASes until the stopping criteria is met. In another embodiment, the method illustrated atFIG. 2can be repeated for each of a set of designated target ASes.

The above described method can be expressed mathematically, where the detection coverage of a tower v with respect to a target AS d is expressed as DC(v,d). Accordingly, the detection coverage of a set of towers V with respect to a target AS d is expressed as:

D⁢⁢C⁡(V,d)=⋃v∈V⁢D⁢⁢C⁡(v,d)
The detection coverage ratio can be computed by dividing DC(V,d) by the total number of ASes which can potentially hijack a prefix of the target AS d. Selection of locations for detection towers is a set cover problem. In particular, assume H represents the set of all possible uncovered ASes. Hv,dis the set of uncovered ASes from which a detection tower v can detect a hijacking event on target d. The family Z consists of all possible subsets of H. The set of locations for detection towers is the minimum subset Hv,dsuch that:

H=⋃Hv,d∈Z⁢Hv,d
The set covering problem is referred to as a non-deterministic polynomial (NP) complete problem. In the method described above, the set of uncovered ASes is equal to the set H. For each iteration, a detection tower v that yields the largest detection ratio on the set of remaining uncovered ASes is selected. The set of remaining uncovered ASes is then updated to remove the ASes covered by a detection tower located at the selected location. Iterations continue until stopping criteria are met.

FIG. 4shows an illustrative embodiment of a general computer system400in accordance with at least one embodiment of the present disclosure. The computer system400can include a set of instructions that can be executed to cause the computer system to perform any one or more of the methods or computer based functions disclosed herein. The computer system400may operate as a standalone device or may be connected, e.g., using a network, to other computer systems or peripheral devices.

The computer system400may include a processor402, e.g., a central processing unit (CPU), a graphics processing unit (GPU), or both. Moreover, the computer system400can include a main memory404and a static memory406that can communicate with each other via a bus408. As shown, the computer system400may further include a video display unit410, such as a liquid crystal display (LCD), an organic light emitting diode (OLED), a flat panel display, a solid state display, or a cathode ray tube (CRT). Additionally, the computer system400may include an input device412, such as a keyboard, and a cursor control device414, such as a mouse. The computer system400can also include a disk drive unit416, a signal generation device418, such as a speaker or remote control, and a network interface device420.

In a particular embodiment, as depicted inFIG. 4, the disk drive unit416may include a computer-readable medium422in which one or more sets of instructions424, e.g. software, can be embedded. Further, the instructions424may embody one or more of the methods or logic as described herein. In a particular embodiment, the instructions424may reside completely, or at least partially, within the main memory404, the static memory406, and/or within the processor402during execution by the computer system400. The main memory404and the processor402also may include computer-readable media. The main memory404can also store a data file425representing a network topology for performance of one or more of the methods described herein. The network interface device420can provide connectivity to a network426, e.g., a wide area network (WAN), a local area network (LAN), or other network.

The present disclosure contemplates a computer-readable medium that includes instructions424or receives and executes instructions424responsive to a propagated signal, so that a device connected to a network426can communicate voice, video or data over the network426. Further, the instructions424or the data file425may be transmitted or received over the network426via the network interface device420.

The above disclosed subject matter is to be considered illustrative, and not restrictive, and the appended claims are intended to cover all such modifications, enhancements, and other embodiments which fall within the true spirit and scope of the present disclosed subject matter. Thus, to the maximum extent allowed by law, the scope of the present disclosed subject matter is to be determined by the broadest permissible interpretation of the following claims and their equivalents, and shall not be restricted or limited by the foregoing detailed description.