FIELD OF THE DISCLOSURE

The present disclosure relates generally to capturing the routing topology of a network (e.g., the Internet covering the entire IPv4 address space) and specifically, to data collection, data processing, and data storage techniques for capturing the routing topology of the network in an efficient manner.

BACKGROUND OF THE DISCLOSURE

Currently, the general physical topology of many large-scale networks, such as the Internet, is not known. The lack of knowledge limits an understanding of ongoing and potential risks in the network and also limits options for reducing and minimizing such risks. For example, cyber analysts are unable to identify attacks staged from routing infrastructure, as it is unknown which IP addresses are routers. There have been a number of high-profile incidents which involved attackers interfering with (e.g., taking over) routers in 2018, resulting in DHS CISA Alert (TA18-106A) “Russian State-Sponsored Cyber Actors Targeting Network Infrastructure Devices.”

SUMMARY OF THE DISCLOSURE

As explained above, the topology of many large-scale networks, such as the Internet, is not currently known. Thus, it would be beneficial to obtain information representing the topology of large-scale networks such as the Internet, including the identities of routers and the interconnectivity among the routers.

An exemplary computer-enabled method for obtaining a routing topology of a network, the method comprises: obtaining a first bit array indicative of a plurality of target IP addresses, wherein the plurality of target IP addresses is a subset of a plurality of IP addresses in the network, wherein the first bit array comprises a plurality of binary values corresponding to the plurality of IP addresses in the network, and wherein each binary value is indicative of whether a corresponding IP addresses is a target IP address; assigning a first subset of the plurality of target IP addresses to a first source device of a set of source devices by providing a first source-specific version of the first bit array to the first source device; assigning a second subset of the plurality of target IP addresses to a second source device of the set of source devices by providing a second source-specific version of the first bit array to the second source device; causing the first source device to transmit a first plurality of probing packets to the first subset of the plurality of target IP addresses and receive a first plurality of returned packets, causing the second source device to transmit a second plurality of probing packets to the second subset of the plurality of target IP addresses and receive a second plurality of returned packets, and based on the first plurality of returned packets and the second plurality of returned packets, generating a data structure representing a routing topology of the network.

In some embodiments, obtaining the first bit array indicative of the plurality of target IP addresses comprises: determining whether an IP address of the plurality of IP addresses is a reserved address; and updating a binary value corresponding to the IP address in the first bit array based on the determination.

In some embodiments, the first source-specific version of the first bit array comprises an instance of the first bit array and a value indicative of a portion of the first bit array.

In some embodiments, the first source-specific version of the first bit array comprises a modified instance of the first bit array, wherein a subset of the plurality of target IP addresses are indicated in the modified instance of the first bit array.

In some embodiments, the first source device comprises a scanning tool.

In some embodiments, the scanning tool is configured to transmit a first probing packet and a second probing packet of the plurality of probing packets to a target IP address of the first subset of the plurality of target IP addresses in a random order.

In some embodiments, the first probing packet and the second probing packet are associated with successive time-to-live values.

In some embodiments, the first probing packet and the second probing packet are ICMP packets.

In some embodiments, generating the data structure representing the routing topology comprises generating, based on the first plurality of returned packets and the second plurality of returned packets, a byte array representing one or more routing paths of the first plurality of first plurality of returned packets and the second plurality of returned packets.

In some embodiments, generating the data structure representing the routing topology comprises generating a second bit array based on the byte array, wherein the second bit array comprises a plurality of binary values corresponding to respective network nodes of one or more routing paths.

In some embodiments, the method further comprises displaying a visualization of the routing topology over a map interface.

In some embodiments, the method further comprises displaying a plurality of routers identified based on the routing topology.

An exemplary electronic device, comprises: one or more processors; a memory; and one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for: obtaining a first bit array indicative of a plurality of target IP addresses, wherein the plurality of target IP addresses is a subset of a plurality of IP addresses in the network, wherein the first bit array comprises a plurality of binary values corresponding to the plurality of IP addresses in the network, and wherein each binary value is indicative of whether a corresponding IP addresses is a target IP address; assigning a first subset of the plurality of target IP addresses to a first source device of a set of source devices by providing a first source-specific version of the first bit array to the first source device; assigning a second subset of the plurality of target IP addresses to a second source device of the set of source devices by providing a second source-specific version of the first bit array to the second source device; causing the first source device to transmit a first plurality of probing packets to the first subset of the plurality of target IP addresses and receive a first plurality of returned packets, causing the second source device to transmit a second plurality of probing packets to the second subset of the plurality of target IP addresses and receive a second plurality of returned packets, and based on the first plurality of returned packets and the second plurality of returned packets, generating a data structure representing a routing topology of the network.

An exemplary non-transitory computer-readable storage medium stores one or more programs, the one or more programs comprising instructions, which when executed by one or more processors of an electronic device, cause the electronic device to: obtain a first bit array indicative of a plurality of target IP addresses, wherein the plurality of target IP addresses is a subset of a plurality of IP addresses in the network, wherein the first bit array comprises a plurality of binary values corresponding to the plurality of IP addresses in the network, and wherein each binary value is indicative of whether a corresponding IP addresses is a target IP address; assign a first subset of the plurality of target IP addresses to a first source device of a set of source devices by providing a first source-specific version of the first bit array to the first source device; assign a second subset of the plurality of target IP addresses to a second source device of the set of source devices by providing a second source-specific version of the first bit array to the second source device; cause the first source device to transmit a first plurality of probing packets to the first subset of the plurality of target IP addresses and receive a first plurality of returned packets, cause the second source device to transmit a second plurality of probing packets to the second subset of the plurality of target IP addresses and receive a second plurality of returned packets, and based on the first plurality of returned packets and the second plurality of returned packets, generate a data structure representing a routing topology of the network.

An exemplary computer-enabled method for obtaining a routing topology of a network comprises transmitting, from a source device, a first probing packet and a second probing packet to a target IP address, wherein the first probing packet is associated with a first time-to-live value and wherein the second probing packet is associated with a second time-to-live value, receiving, at the source device, a first returned packet corresponding to the first probing packet and a second returned packet corresponding to the second probing packet; constructing a byte array based on the first returned packet and the second returned packet, wherein the byte array comprises a subarray, and wherein the subarray comprises a field indicative of the source device, a field indicative of an IP address associated with the first returned packet, and a field indicative of an IP address associated with the second returned packet; and based on the byte array, constructing a bit array, wherein the bit array comprises a plurality of binary values corresponding to a plurality of IP addresses in the network, and wherein each binary value is indicative of whether a corresponding IP addresses is a router.

In some embodiments, the source device is a first source device, the target IP address is a first target IP address, and the subarray is a first subarray, the method further comprising: transmitting, from a second source device, a third probing packet and a fourth probing packet to a second target IP address, receiving, at the second source device, a third returned packet corresponding to the third probing packet and a fourth returned packet corresponding to the fourth probing packet; wherein constructing the byte array is based on the third returned packet and the fourth returned packet, wherein the byte array comprises a second subarray, and wherein the second subarray comprises a field indicative of the second source device, a field indicative of an IP address associated with the third returned packet, and a field indicative of an IP address associated with the fourth returned packet.

In some embodiments, the method further comprises initializing the bit array as an array of a plurality of zeros.

In some embodiments, the method further comprises based on the IP address associated with the first returned packet as indicated in the byte array, updating a binary value corresponding to the IP address associated with the first returned packet in the bit array.

An exemplary electronic device comprises: one or more processors; a memory; and one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for: transmitting, from a source device, a first probing packet and a second probing packet to a target IP address, wherein the first probing packet is associated with a first time-to-live value and wherein the second probing packet is associated with a second time-to-live value, receiving, at the source device, a first returned packet corresponding to the first probing packet and a second returned packet corresponding to the second probing packet; constructing a byte array based on the first returned packet and the second returned packet, wherein the byte array comprises a subarray, and wherein the subarray comprises a field indicative of the source device, a field indicative of an IP address associated with the first returned packet, and a field indicative of an IP address associated with the second returned packet; and based on the byte array, constructing a bit array, wherein the bit array comprises a plurality of binary values corresponding to a plurality of IP addresses in the network, and wherein each binary value is indicative of whether a corresponding IP addresses is a router.

An exemplary non-transitory computer-readable storage medium stores one or more programs, the one or more programs comprising instructions, which when executed by one or more processors of an electronic device, cause the electronic device to: transmit, from a source device, a first probing packet and a second probing packet to a target IP address, wherein the first probing packet is associated with a first time-to-live value and wherein the second probing packet is associated with a second time-to-live value, receive, at the source device, a first returned packet corresponding to the first probing packet and a second returned packet corresponding to the second probing packet; construct a byte array based on the first returned packet and the second returned packet, wherein the byte array comprises a subarray, and wherein the subarray comprises a field indicative of the source device, a field indicative of an IP address associated with the first returned packet, and a field indicative of an IP address associated with the second returned packet; and based on the byte array, construct a bit array, wherein the bit array comprises a plurality of binary values corresponding to a plurality of IP addresses in the network, and wherein each binary value is indicative of whether a corresponding IP addresses is a router.

