-
Notifications
You must be signed in to change notification settings - Fork 1
How Reach Analysis Works
This document attempts to explain in detail how Reach does what it does. The anticipated benefits of this document are: A) to help the creators of Reach to design and reflect on Reach's architecture, and B) to inform curious outsiders about Reach's unique implementation approach.
Reach is a tool that aims to determine what network communication is possible between two places of interest, particularly when this communication occurs across a network within a public cloud provider.
-
The user asks Reach if a "source" can communicate with a "destination" across a network. The source and destination are both referred to as "subjects".
-
Reach makes sure that what the user is specifying as "subjects" are actual points that exist on a network. Reach also makes sure that for at least one of the subjects, the user provided more than just an IP address or hostname. Reach needs at least one subject about which it can query for more information. For example, if Reach knows that one of the subjects is an EC2 instance in AWS, it can query AWS for more information about the EC2 instance, like its VPC, its security group rules, etc. If the user merely asked in a vacuum, "can 10.0.1.56 talk to 8.8.8.8?", Reach would have no context, and thus it couldn't proceed with its analysis steps.
-
Reach builds a local in-memory collection of all of the resources it might possibly need during its analysis. Starting with the subjects as the first resources in the collection, it recursively discovers related resources for all already-discovered resources until it runs out of resources to look up. It calls this chaining of related resources the "resource graph". This collection will be used later to look up information about resources during various analysis steps (specifically, while determining subject points, building network paths, and generating factors). Technical note: We'll talk more later about "resource domains", but a "domain" here means AWS vs. GCP vs. Azure, and so on. Reach also has a special domain called "generic", which is used when a subject is idenfitied only by its IP address or hostname. Reach builds resource graphs only for non-generic resources.
-
For each subject, Reach determines what, if any, "subject points" the subject has. Each subject point represents a unique IP address that can be used to address the associated subject. Important note: Reach's analysis is source-oriented. Subject points are calculated differently, depending on whether a given subject's role is the source or the destination, because the IP addresses used should be the possible values for source and destination addresses on IP packets at the time the traffic is initiated at the source. Source subject points are all IP addresses that are used directly by the source (e.g. by network interfaces attached to the source). IP addresses used as source IP addresses downstream from the source, like a public IP address used only after a NAT point, are not considered source subject points since the source itself does not use this IP address. Destination subject points are all IP addresses that the source can use to send traffic to the destination, regardless of if the destination uses a given IP address directly. Here again, the true test is whether or not IP traffic initiated by the source includes the destination IP address in question. Temporary decision: For now, it's up to the resource in question to generate subject points, in such a way that's aware of if the resource is acting as a source subject or destination subject during this analysis. For destination subjects, the resource should submit all potential IP addresses, including both public and private IP addresses (we can revisit this approach later if needed). It's theoretically possible that traffic can be routed to the destination over both public and private routes. If one or more of the submitted destination IP addresses are not actually routable by traffic originating at the source, that scenario will be handled during the analysis phase that tries to construct network paths.
-
Reach should now have one or more subject points for the source, and one or more subject points for the destination. It then creates all the possible pairings of a single source subject point to a single destination subject point. The number of pairings should be the product of the number of source subject points and the number of destination subject points.
-
For each pairing of subject points, Reach attempts to construct two "network paths" — a forward network path from the source to the destination, and a return network path from the destination to the source. A network path is composed of a series of hops, or "network points", through which network traffic flows. For any given network point, Reach should be able to compute the next network point, unless it has just completed a network path. If Reach cannot determine the next network point, and it hasn't finished building the current network path, it gives up on the current network path. It's possible for there to be more than one network path for any given pair of source and destination subject points (double check this). It's also possible for Reach to be unable to construct any network paths for a given pair of subject points. In this case, Reach determines that network traffic cannot be routed from source to destination using these subject points. If no pairs of subject points yielded any network paths, the analysis is over — there is no path for network traffic to flow from the source to the destination.
-
Each network path is comprised of one or more "network path segments", which collectively coincide with the network path. The definition of a network path segment resembles that of a network path: both are defined as a series of network points. As Reach is constructing the network path, it considers a new network path segment to have begun when a network point changes something about the network traffic's content other than IP addresses — basically, this means NAT/PAT occurs at the network point. This information is needed when calculating the "return traffic" allowed (i.e. from destination back to source). Open for discussion: It's possible that we don't need to create separate network paths for the forward and return directions. Given a single network path — that's been properly segmented — we'd be able to calculate forward traffic by ignoring the segments and return traffic by utilizing the segments. This reasoning holds true only if there is no need to consider a different path through the network for the return traffic than the forward traffic used.
-
For each network path, Reach examines each network point, and it generates one or more "factors" that describe what network traffic is allowed to flow through this point. After the whole network path has been traversed in this way, the result is a collection of factors. The method of generating each kind of factor is dependent on one or more domain-specific resources. Additionally, in order to generate a factor, Reach takes as input the current direction of flow being analyzed, as well as the current source and destination IP addresses used on IP packets (in this instance, we're referring to header values on IP packets, not the "source" and "destination" subjects).
-
Each factor contains a data structure called "traffic content", which is a multi-dimensional set of what kind of traffic is allowed. For example, the traffic content might represent "all network traffic", or "no network traffic", or "all UDP traffic", or "only TCP port 443 traffic", or "only UDP ports 50-100 and TCP ports above 1023", etc. Because a "traffic content" structure is a kind of set, traditionally set math operations can be performed on traffic contents. For example, you can intersect two traffic contents.
-
When all factors have been generated, Reach is ready to determine what traffic can flow from the source to destination, and then back to the source. The methods for assessing the forward direction and the return direction of traffic are different.
-
To assess connectivity for the forward network path, Reach takes the intersection of all factors' traffic contents associated with the network path. The result is a traffic content data structure that depicts what kinds of IP traffic can flow from the source to the destination (but not necessarily back).
-
To assess the ability for traffic to return from the destination to the source, which is required for most types of network communication, Reach takes a "map-reduce" approach. Reach maps each network path segment to a single traffic content by intersecting all factors' traffic contents for that network path segment. Reach also then maps each resulting traffic content to a "simplified traffic content". This data structure is drastically simpler than the full traffic content, because for each IP protocol, the data structure does not attempt to describe all possible states of the set space; instead, it states that the set space is fully occupied, partially occupied, or not at all occupied. This results in semantics like, "all TCP traffic", "some TCP traffic", and "no TCP traffic". Now that each network path segment has been mapped to a simplified traffic content, a reducing operation is applied to the set of simplified traffic contents. Each IP protocol is allowed to have its own logic for how you take a set of "all/some/none" values and produce a singular value to describe how certain the IP protocol could operate successfully, from the set of ["guaranteed success", "possible failure", and "guaranteed failure"].
-
At the end of analysis, Reach can tell the user every possible path there is for network traffic to flow from the source to the destination, and, for each of these paths, what kinds of network communication would be successful or not.
To be defined:
Resource
Subject
Source
Destination
Network Path
Network Point
Subject Point
Resource Collection
Resource Graph
Resource Domain
Resource Kind
Resource ID
Resource Provider