Patent Publication Number: US-11658818-B2

Title: Systems and methods for privacy preserving accurate analysis of network paths

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of U.S. application Ser. No. 16/161,005, filed Oct. 15, 2018 (the &#39;005 application), which claims the benefit of U.S. provisional application No. 62/572,846, filed Oct. 15, 2017 (the &#39;846 application). The &#39;005 application and the &#39;846 application are both hereby incorporated by reference as though fully set forth herein. 
    
    
     BACKGROUND OF THE INVENTION 
     The present subject matter relates generally to network security. More specifically, the present invention relates to systems and methods for anonymizing IP address configuration files prior to transmission to, and use by, remote-based services to preserve the privacy of the sensitive information typically found in IP configuration files. 
     Misconfiguration of access policy implementation within firewalls or other local security mechanisms is a major source of security vulnerability and compliance issues. The complex interactions between distributed and layered policy implementation can lead to subtle errors and can mask problems that a tedious manual review of configuration file would certainly miss. Accordingly, it is important to routinely perform comprehensive analysis of firewall, router, and switch configurations to determine connectivity and identify any deviation from security policies, standards, and best-practices as an important line of defense for networks. 
     Software tools exist to perform such analysis. These tools take as input the native configuration files of firewalls, router forwarding tables, and a baseline access policy description and compute all permitted flows, and, in particular, those flows that deviate from baseline policy. 
     A potential market exists for access to such tools as a cloud-based (or otherwise remote) service, but a significant barrier exists: the identities of the IP subnetworks (and to a lesser extent the particular ports used for specialized services) are often viewed as sensitive information, as may be the text strings used to name elements of a network topology. 
     Collectively, the IP addresses provide a roadmap that a cyber-attacker may use to infiltrate the networks. Accordingly, network operators are understandably reluctant to expose their configurations outside their installations. Operators of critical infrastructures (e.g., the electric power grid) are especially reluctant to expose their native configurations. 
     This appropriate reluctance has made it problematic to use remote-based analysis services that perform comprehensive analysis of firewall, router, and switch configurations to determine connectivity and identify any deviation from security policies, standards, and best-practices. However, it is well-known that there are circumstances in which cloud-based services offer considerable cost-savings. 
     While it is safe to assume that a user (e.g., network operator) would encrypt configurations prior to transmission to the remote-based analysis service, protection of the configurations in motion is not the problem of interest. The previously unaddressed threat comes from an observer capable of accessing the decrypted configurations while they are being processed in the cloud. Moreover, from this point of view, the cloud-based service itself is an unaddressed threat as it has direct access to the decrypted configurations. 
     Accordingly, there is a need to provide systems and methods through which cloud-based services can be used while protecting sensitive IP address configuration information. 
     BRIEF SUMMARY OF THE INVENTION 
     To meet the needs described above and others, the subject matter disclosed herein provides systems and methods for anonymizing IP address configuration files prior to transmission to, and use by, remote-based services to preserve the privacy of the sensitive information. The systems and methods combine anonymization of the IP address, port, and protocol information with specialized analysis techniques to preserve privacy of the sensitive information. In a primary embodiment, the systems and methods employ an algorithm that anonymizes a collection of ranges so as to preserve “range-intersection” over that collection, the key property needed for performing connectivity analysis. This makes it possible for a user to anonymize all the ranges in configuration files and transmit the anonymized configurations to the remote-based service. There, the connectivity computation is performed, oblivious to the anonymization, yielding results whose IP and port ranges are encoded, as are user provided names (which frequently reference geographic identity) and protocol identities. These are transmitted back to the user and de-anonymized, to obtain exactly the same results as would have been found performing the analysis on the original configuration files. 
     Using the systems and methods provided herein, remote-based analysis services that perform comprehensive analysis of firewall, router, and switch configurations to determine connectivity and identify any deviation from security policies, standards, and best-practices can be implemented such that the engine that performs the connectivity analysis is oblivious to the anonymization of the data. In other words, the engine processes an anonymized configuration just like it processes a non-anonymized one. 
     Accordingly, the objectives and advantages of the present subject matter can be accomplished by implementing algorithms on the client side that anonymize the network information found in the configurations, then send the anonymized configuration to the cloud-based server for analysis, which analyzes the anonymized configuration and then returns the anonymized results to client-side system where the anonymized results are de-anonymized. In such an implementation, the cloud-based server has no knowledge of the pre-anonymized IP address, port, and protocol information. 
     In some examples, the anonymization can be transparent to the user, except for providing a key upon which the anonymization depends. 
     To support cloud-based storage of anonymized configurations and combining already anonymized system descriptions into a larger anonymized system, the present disclosure also provides algorithms that merge two anonymized system representations using only public information about the systems being merged, while protecting the anonymizations. 
     As described above, the systems and methods provided herein, remote-based analysis services that perform comprehensive analysis of firewall, router, and switch configurations to determine connectivity and identify any deviation from security policies, standards, and best-practices. Connectivity analysis is focused on ranges, i.e., contiguous sequences of IP addresses, and contiguous sequences of port numbers. The basic operation in the analysis is to take a selected subnetwork as the source and selected subnetwork as the destination and find all flows the configurations permit from the source to the destination. A source range represents a set of potential hosts, as does the destination range. A variation is to use a wildcard for the destination and find all flows from the source to anywhere else. A wildcard is a range that allows anything to pass through, and appears in most positions of the IP header in the initial meta-packet. The source and destination subnets are usually represented as CIDR blocks, but the systems and methods provided herein view the source and destination subnets as ranges of integers. The analysis takes a source-range/destination-range pair and creates a meta-packet where addresses and port numbers are ranges (or wildcards) and the protocol is specified (or a set of protocols is specified) and “pushes” that through the system, starting from the source network. The logic applied to meta-packets is similar to logic applied to individual packets (e.g. passing through access control rules, being routed, having NAT transformations applied), but each of these steps may fragment a meta-packet into multiple meta-packets (whose address and port ranges are subsets of the original), each of which is pushed along individually towards the destination network. The result of the computation is a set of meta-packets that actually reach the destination, each of which we call a “path”. 
     Oblivious analysis is possible when path-discovery computation is performed on an anonymized meta-packet and produces a set of paths such that de-anonymization of the ranges in those paths produces exactly the same set of paths as are computed from the same non-anonymized meta-packet, and each path begins at exactly the same source subnet, follows exactly the same sequence of devices, passes through exactly the same set of access control rules, has exactly the same routing decisions made and exactly the same NAT rules applied, and reaches exactly the same subnetworks. 
     One key to the systems and methods described herein is the observation that the rules applied to IP packet headers are based on whether the source IP address falls within some range of IP addresses, whether the source port address falls within some range of port numbers, whether the destination IP address falls within some range of IP addresses and whether the destination port number falls within some range of port numbers. For access control, for routing, and for network address translation, the determination of whether a rule applies, or which rule applies, to the header depends on the inclusion, or not, of the header&#39;s individual numbers in the rules&#39; match ranges. Applied to meta-packets, the system can determine what subset of meta-packets are matched by a given rule by taking the intersection of the meta-packet&#39;s source IP range with the source IP range specified by the rule, the intersection of the meta-packet&#39;s source port range with the source port range specified by the rule, the intersection of the meta-packet&#39;s destination range with the destination range of the rule, the intersection of the meta-packet&#39;s destination port range with the destination port range of the rule, and check whether the protocol identified by the rule matches the set of protocols carried by the meta-packet. If every intersection and comparison is non-empty, then the meta-packet defined by those intersections (and protocol match) identifies all the packets from the meta-packet that are matched by the rule. Therefore, anonymization that preserves the structure of intersections (i.e., range-intersection preserving anonymization) is important to the integrity of the systems and methods provided herein. Accordingly, the primary object of the subject matter provided herein is to structure the connectivity analysis in such a way that de-anonymization of paths produces the desired result. 
     Those skilled in the art will recognize the range of embodiments in which the present subject matter may be employed. For purposes of illustrating the scope and range of the systems and methods to those skilled in the art, two main examples are provided. 
     In a first example, the native configurations representing a system are first converted into a system representation and the system representation is anonymized. The conversion of native configurations into system representation is done on the client (private) side of the system and the anonymization is then performed on the system representation. In the second example, the native configurations are directly anonymized (on the client side), and the transformation of anonymized configurations into an anonymized system representation is performed on the server side. The technical advantage of the second embodiment is that considerably less code is needed on the client side to anonymize individual configuration files, leaving more of the overall system in the cloud for maintenance and updates that require no interaction with the client user. Each of these examples is described in further detail below with respect to the figures. 
     In one embodiment of the invention, an anonymizing system includes a native configurations database including a set of configurations, a key management database including a plurality of private keys, a processor in communication with the native configurations database and the key management database, and a memory coupled to the processor configured to store program instructions executable by the processor. The set of configurations includes one or more ranges, wherein each range includes a contiguous sequence comprised of IP addresses, port numbers, or IP addresses and port numbers. The processor is configured to retrieve the set of configurations from the native configurations database, wherein the set of configurations includes a plurality of objects, and retrieve a private key from the key management database, wherein the private key is associated with the set of configurations. The processor is further configured to assign a unique cryptographically secure identity to each object, each identity derived from the private key, and anonymize the plurality of objects based on the cryptographically secure identities and the private key. 
     In some embodiments, each range includes one or more of a set of potential hosts, a destination IP address, a source port, and a destination port. Further, in some embodiments, the step of anonymizing the representation includes assigning a rule-table to the set of configurations, wherein the rule-table includes a plurality of rules that are position-insensitive. In still some embodiments, each range of the anonymized representation includes the same number of members as the corresponding original range. The plurality of ranges may be fragmented. 
     In other embodiments, the step of anonymizing the representation includes the steps of creating a list of range endpoints, sorting the list of range endpoints, and computing, for each endpoint, a set of ranges that contain the endpoint but do not begin or end at the endpoint. Further, in some embodiments, the anonymizing system may apply an offset to the set of ranges. In some embodiments, the processor is configured to generate a public key that describes the range sizes of each object based on the object&#39;s cryptographically secure identity. 
     In another embodiment of the present invention, the anonymizing system further includes a remote anonymized systems database, and the processor is configured to build a representation including a plurality of objects, assign a unique cryptographically secure identity to each object in the representation, each identity derived from the private key, and transmit the anonymized representation to the remote anonymized systems database. 
     The anonymization system may include a remote anonymized analysis results database and a remote oblivious analysis engine in communication with remote anonymized systems database and the remote database of anonymized analysis results, with a further processor configured to receive user input to generate an anonymized analysis of the anonymized representation, retrieve, by the remote oblivious analysis engine, the anonymized representation from the remote anonymized systems database, analyze the anonymized representation to develop anonymized analysis results, and store the anonymized analysis results in the remote anonymized analysis results database. 
     In a further embodiment, the anonymizing system may further include a remote anonymized configurations database, wherein the processor is configured to transmit the anonymized plurality of objects to the remote anonymized configurations database. The system may also include a remote anonymized analysis results database and a remote oblivious analysis engine in communication with remote anonymized systems database and the remote database of anonymized analysis results, with a further processor configured to receive user input to generate an anonymized analysis of the anonymized representation, retrieve, by the remote oblivious analysis engine, the anonymized plurality of objects from the remote anonymized configurations database, build a representation based on the anonymized plurality of objects, assign a unique cryptographically secure identity to each object in the representation, each identity derived from the private key; and transmit the anonymized representation to the remote anonymized systems database. The processor may be programmed with computer instruction that cause it to retrieve the anonymized representation from the remote anonymized systems database, analyze the anonymized representation to develop anonymized analysis results, and store the anonymized analysis results in the remote anonymized analysis results database. 
     Finally, the anonymizing system of the present application may include further program instructions that cause the processor to generate a de-anonymization key and store the de-anonymization key in the key management database. Further, the processor may be configured to receive user input to de-anonymize the anonymized analysis results, receive, from the remote anonymized analysis results database, the anonymized analysis results and the de-anonymization key from the key management database, invert the anonymization performed on the representation, and present the de-anonymized results to the user. 
     Additional objects, advantages and novel features of the examples will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following description and the accompanying drawings or may be learned by production or operation of the examples. The objects and advantages of the concepts may be realized and attained by means of the methodologies, instrumentalities and combinations particularly pointed out in the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The drawing figures depict one or more implementations in accord with the present concepts, by way of example only, not by way of limitations. In the figures, like reference numerals refer to the same or similar elements. 
         FIG.  1    is a schematic representation of an example of components of a first anonymizing system. 
         FIG.  2    is a schematic representation of the anonymizing system of  FIG.  1    anonymizing a system representation. 
         FIG.  3    is a schematic representation of the anonymizing system of  FIG.  1    performing an oblivious analysis of the anonymized system representation. 
         FIG.  4    is a schematic representation of the anonymizing system of  FIG.  1    de-anonymizing the results of the oblivious analysis of the anonymized system representation. 
         FIG.  5    is a schematic representation of the anonymizing system of  FIG.  1    performing an oblivious merge of two anonymized systems into a larger aggregate system. 
         FIG.  6    is a schematic representation of an example of components of a second anonymizing system. 
         FIG.  7    is a schematic representation of the anonymizing system of  FIG.  6    anonymizing a configuration. 
         FIG.  8    is a schematic representation of the anonymizing system of  FIG.  6    creating an anonymized system representation. 
         FIG.  9    is a schematic representation of the anonymizing system of  FIG.  6    performing an oblivious analysis of the anonymized system representation. 
         FIG.  10    is a is a schematic representation of the anonymizing system of  FIG.  6    de-anonymizing the results of the oblivious analysis of the anonymized system representation. 
         FIG.  11    is a schematic representation of the anonymizing system of  FIG.  6    performing an oblivious merge of two anonymized systems into a larger aggregate system. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       FIGS.  1 - 5    illustrate components of an anonymization system  100 . In the schematic shown in  FIG.  1   , the anonymization system  100  includes a client-side system  102  and a remote server system  104  that communicate via the internet  106 , although any suitable communication means may be used. 
     Generally, all contiguous ranges of IP addresses and contiguous ranges of ports referenced in the file can be identified by analyzing a configuration or system representation. The anonymization technique of the anonymization system (described in greater detail below) identifies all connected ranges, and then constructs a translation of each connected range by finding an integer value used to shift the range, which can be easily inverted. By describing the matching of a rule-table to an IP packet header in terms of intersections, it is easily shown that a given IP packet header matches the rangers described in a rule if and only if the values of the packet header, when anonymized, match the ranges described in the rule under the same anonymization. 
     In the illustrated embodiment, the anonymization system  100  includes a native configurations database  108  including a set of configurations, a key management database  110  including a plurality of private keys, and a remote anonymized systems database  112 . A processor  114  is in communication with the native configurations database  108  and the key management database  110 , and includes a memory  116  configured to store program instructions executable by the processor  114  that, when executed cause the processor  114  to undertake certain steps to anonymize a set of data. 
     More specifically, the anonymizing system  100  performs a method of anonymizing data. Referring to  FIG.  2   , the system  100  first retrieves a set of configurations  118  from the native configurations database  108  and a private key  120  from the key management database  110 . In the illustrated embodiment, a system representations module  122  retrieves the set of configurations  118  and the private key  120  in order then build a representation  124  comprised of a plurality of objects and assigns a unique cryptographically secure identity to each object in the representation  124 , each identity being derived from the private key. In the illustrated embodiment, the representation  124  is transmitted to a system anonymizer module  126 , which then anonymizes the representation  124  based on the cryptographically secure identities and the private key. The system  100  finally transmits the anonymized representation  128  to the remote anonymized systems database  112 . The system anonymizer also generates a de-anonymization key  130  that is stored in the key management database  110  and used by a de-anonymization module  131  to de-anonymize the final results. 
     The remote server system  104  includes the anonymized systems database  112 , an oblivious analysis engine  132 , an anonymized analysis results database  134 , and an oblivious systems merger  136 . The remote server system  104  may also include a second processor  138  and a second memory  140  including program instructions executable by the second processor  138 . 
     Referring to  FIG.  2   , the system representations module  122  retrieves a set of set of configurations  118  from the native configurations database  108  and a private key  120  from the key management database  110  upon receipt of instructions  142  from a user via a graphical user interface  144  within the client-side system  102 . The set of configurations  118  may include a plurality of ranges including one or more of a set of potential hosts, a destination IP address, a source port, and a destination port. In some embodiments, the plurality of ranges may be fragmented. The systems representation module  122  builds a representation  124  of the set of configurations  118 , the representation  124  including a plurality of objects. Each object in the representation  124  is provided a unique cryptographically secure identity derived from the object specification and private key  120 . The representation  124  is transmitted to the system anonymizer module  126 , which anonymizes the representation  124  based on the cryptographically object identities and the relevant private key  120 . 
     By analyzing a configuration  118  or system representation  124 , all contiguous ranges of IP addresses and contiguous ranges of ports referenced in the file can be identified. A range includes contiguous sequences of IP address and contiguous sequences of port numbers. The system  100  identifies a selected source subnetwork or host and finds all flows the configuration allows whose origin is in the source subnetwork. Therefore, a source range includes a set of potential hosts, typically Classless Inter-Domain Routing blocks, which can be viewed as a range. The system generates a meta-packet based on a source subnetwork description, where the source IP address is the range of IP addresses in the originating subnetwork, and wild-card integer ranges for the destination IP address, the source port, and the destination port. In some embodiments, special cases of IP ranges that have special meaning and should not be anonymized, such as well-known private address spaces and multicast address spaces. 
     As the meta-packets are pushed through the network description, the logic applied is similar to logic applied to individual packets. However, each step may fragment a meta-packet into multiple meta-packets that include address and port ranges that are subsets of the original ranges. Each meta-packet that reaches the destination is referred to as a “flow.” 
     For an anonymization of a meta-packet that produces a set of flows, the de-anonymization of the ranges in those flows will produce exactly the same set of flows as are computed from the same non-anonymized meta-packet, which each flow having followed exactly the same sequence of devices, having been admitted by exactly the same set of access control rules, and having had exactly the same routing decisions made and have exactly the same NAT rules applied. 
     The routing of packet information typically involves the application of a rule-table to an IP packet header. The IP packet header specifies integer values for the source and destination IP addresses, the source and destination port numbers, and the protocol. Each firewall applies a rule-table to the IP packet header in order to determine whether to admit the packet and transform part of the packet through Network or Port Address Translation. Similarly, each router applies a rule-table to determine whether to route the packet. For a five-dimensional IP packet header, a rule-table includes five-dimensional matching conditions. The matching conditions can be exact values or ranges in terms of specifying a union of intervals. Example applications of rule-tables to two IP packet headers are provided below to illustrate matching and non-matching conditions. 
     
       
         
           
               
               
               
             
               
                   
               
               
                 packet header 
                 condition 
                 matching? 
               
               
                   
               
             
            
               
                 (130.126.151.36, 21790, 
                 (*, *, 192.17.90.0/24 443, 6) 
                 match 
               
               
                 192.17.90.136, 443, 
               
               
                 (130.126.151.36, 21790, 
                 (*, *, 192.17.90.0/24, 110, 6) 
                 no match 
               
               
                 192.17.90.136, 443, 
               
               
                   
               
            
           
         
       
     
     The range field of a meta-packet resulting from a match is marked as “shaped” if the range in that field of the rule is from a known space is and is not a wildcard. The distinction is important in the logic for computing precisely which flows are presented to a rule. For a list of rules R1, R2, . . . Rn, and a meta-packet P, the logic is to take the intersection of P&#39;s fields with R1&#39;s fields, and siphon off the meta-packet which intersects R1 in all dimensions. The residual flow P/R1 (i.e., P excluding R1) is logically the set of meta-packets which are intersected with R2. These reflect the exclusion of R1, and the set of meta-packets presented to R3 will represent the exclusion of both R1 and R2. To support anonymization, the exclusions applied to unshaped ranges are not computed, but instead are carried along symbolically. When a meta-packet is discovered to be a path, one or more of its dimensions may be unshaped. If there are exclusions, these are necessarily from known (anonymized) space and are represented symbolically, which means that to correctly identify the ranges of unknown space represented as a course or destination, de-anonymization needs to be applied only to the exclusions. 
     The action applied to a packet depends on which rules match, their position in the table, and sometimes the size of the ranges encoded in the rule&#39;s matching conditions. For example, in many firewalls the action applied to a packet is that action associated with the rule among all possible matches which appears earliest in a sequential representation of the rule-table. In some other cases such as a BSD firewall, it is the last rule among all possible matches in the table that determines the action, unless there is a match with an earlier rule designated as being “quick.” In the case of a router&#39;s forwarding table, the matching rule which defines the routing applied may be the rule whose matching condition is smallest. 
     In the anonymization system  100 , the rule which defines the action applied to the packet is (1) among a set of matching rules whose matching conditions have non-empty intersection with the packet in the corresponding dimensions, and (2) the algorithm for selecting among all matching rules depends in no way on the specific values of the ranges in those rule&#39;s matching conditions. Therefore, each rule-table and the algorithm for selecting among matching rules is position-insensitive. For example, if P is a computer program whose inputs include ranges of integers and I is a subset of those ranges, P is “position-insensitive” on I if any branching decision that depends on I is the same for multiple positionings of the range in the domain. 
     Within the IP space, a range [a, b] is related to range [c, d] if those ranges have a non-empty intersection. Ranges may be aggregated into disjoint “connected” sets where all ranges in a connected set are related by the transitive closure of the “intersects” relations. A connected set can be described by a “super-range” [A, B] where any member of the connected set is a subset of [A, B]. Obviously, if each of [a, b] and [c, d] is contained in [A, B], then the intersection of [a, b] and [c, d] will be either empty or be in [A, B]. By definition, the connected sets do not intersect. Therefore, if [a, b] is in one connected set and [c, d] is in a different connected set, their intersection is empty. 
     In some cases, the native configurations contain object group names that are suggestive of geographic region or role of the IP addresses in the group. These group names can be anonymized by using a key to initialize a cryptographically secure random number generator, and either to create completely randomized strings as anonymizations, or to use the random number stream to draw without replacement from a very large dictionary of words (initially randomized itself). The private de-anonymization key provides the inverse mapping. 
     The anonymizing steps of the present anonymizing system  100  are all position-insensitive, at least with respect to IP ranges being consistent with CIDR alignment. The decisions involved in matching access control rules, routing decisions, and application of NAT transformations are determined by taking intersections of IP and/or port ranges in a position-insensitive fashion. In this way, the anonymization preserves the structure of intersections. 
     In one embodiment, the anonymization system  100  draws elements from a domain D to anonymize. While a conventional domain D may include non-negative integer representation of IP addresses, it is presumed that all elements of D are ordered with respect to the numerical values of the IP addresses they represent. To define a range on D, Let a, b∈D. Define [a, b] as a range on D:
 
[ a,b ]={ x∈D|a≤x≤b} 
 
     Not every element in D needs to be anonymized. A subset of ranges I={[s 1 , t 1 ], [s 2 , t 2 ], . . . , [s n , t n ]} have been extracted or inferred from the configuration to be anonymized, and their union is D I . The anonymization system will anonymize only those x∈D I . 
     Presuming an anonymization function ϕ: D I →D on individual elements, ranges on D I  can be mapped into subsets of D, by defining
 
 A   φ ([ u,v ])={φ( x )| for all  x ∈[ u,v ]}
 
     In order to anonymize ranges, analyze the anonymized ranges, and de-anonymize the results, the anonymization range must have the same structure as the original range. More specifically, the image under anonymization is itself a range and has exactly the same number of members as the original. These conditions are necessary for the anonymization steps to be position-insensitive, as the anonymization system and modules within are expecting the structure of ranges and may make control decisions based on the number of elements in that range (even if decisions are not based on the specific values in that range). In this way, the anonymization function φ preserves structure. 
     More specifically, the anonymization function φ preserves structure if it is one-to-one, and for every [u, v] on D I ,
 
 A   φ ([ u,v ])=[φ( u ),φ( v )] and card([ u,v ])=card([φ( u ),φ( v )])
 
where card([s, t])=v(t)−v(s)+1 is the cardinality function.
 
     A consequence of an anonymization function φ preserving structure is that ranges which do not overlap in D I  have images under φ which do not overlap. Otherwise φ would not be one-to-one. Furthermore, preservation of structure implies that ranges which are nested in D I  have images that are nested. That is, if [s, t]⊂[u, v], then
 
 A   φ ([ s,t ])=[φ( s ),φ( t )]⊂[φ( u ),φ( v )]= A   φ ([ u,v ])
 
     This means the effect of φ can be viewed globally, in terms of its effect on canonical ranges. In one example, [s, t] on D I  is said to be canonical if there exists no s I ∈D I  with S I &lt;s such that [s I , t] is a range on D I , nor is there any t I ∈D I  with t&lt;t I  such that [s, t I ] is a range on D I . A canonical range is “as big as possible” in D I . Where φ changes a canonical range, it changes every one of its subranges. If φ preserves structure, its effect on D I  has to be that of shifting the canonical ranges around in D so that they do not overlap. 
     According to one theorem, I is a set of ranges on set D and D I  is their union. R(D I ) is the set of canonical ranges on D I , and the anonymization function φ: D I →D preserves structure. Then, for each E RUM, there exists an integer such that:
 
φ( x )= v− 1( v ( x )+β i ) for all  x   [ si,ti ]
 
     To prove the theorem, choose any [s i , t i ]∈R(D I ), and define β i =v (φ(s i ))−v(s i ). Now: 
     
       
         
           
             
               v 
               ⁡ 
               
                 ( 
                 
                   φ 
                   ⁡ 
                   
                     ( 
                     si 
                     ) 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   v 
                   ⁡ 
                   
                     ( 
                     
                       s 
                       ⁢ 
                       i 
                     
                     ) 
                   
                 
                 + 
                 
                   v 
                   ⁡ 
                   
                     ( 
                     
                       φ 
                       ⁡ 
                       
                         ( 
                         si 
                         ) 
                       
                     
                     ) 
                   
                 
                 - 
                 
                   v 
                   ⁡ 
                   
                     ( 
                     si 
                     ) 
                   
                 
               
               = 
               
                 
                   v 
                   ⁡ 
                   
                     ( 
                     
                       s 
                       ⁢ 
                       i 
                     
                     ) 
                   
                 
                 + 
                 
                   β 
                   ⁢ 
                   i 
                 
               
             
           
         
       
     
     Since v is one-to-one, v −1  is applied to both sides of this equation to see that:
 
 v   −1 ( v (φ( s   i )))= v   −1 ( v ( s   i )+β i ),
 
or equivalently φ(s i )=v −1  (v(s i )+β i ). Now choose any x∈[s i , t i ] with s i &lt;x. Because φ preserves structure, A φ ([s i , x])=[φ(s i ), φ(x)]. Furthermore, v(φ(x))−v(φ(s i ))=v(x)−v(s i ) because the image of [s i , x] under φ is a range with the same number of elements as [s i , x]. It follows that:
 
                     v   ⁡     (     φ   ⁡     (   x   )       )       =       ⁢       v   ⁡     (   x   )       +     (       v   ⁡     (     φ   ⁡     (   si   )       )       -     v   ⁡     (     s   ⁢   i     )         )                   =       ⁢       v   ⁡     (   x   )       +     β   i                   
Applying v −1  to both sides gives φ(x)=v −1 (v (x)+β i ) as required. □
 
     As shown above, any anonymization function that preserves structure necessarily has the form of “shifting” canonical ranges within D. If [s i , t i ]∈R(D I ) is shifted by an offset β i , the numerical range [v(s i ), v(t i )] is shifted by |β i | values, meaning forward if β i  is positive and backward if β i  is negative. 
     This proves that if one is going execute the same computer program on anonymized ranges as one would with original ranges, this form is a necessary condition for the anonymization. To be a sufficient condition for proper execution and ability to de-anonymize, the structure preserving anonymization must also preserve range intersections. This means that the anonymization of intersections is the same as the intersection of anonymizations. 
     Given that φ: D I →D is an anonymization function, φ preserves range intersections if, for every pair of ranges [s, t], [u, v] on D I ,
 
 A   φ ([ s,t ]∩[ u,v ])= A   φ ([ s,t ])∩ A   φ ([ u,v ]),
 
taking A φ (∅)=∅.
 
     The importance of the idea is clear that when A φ  is one-to-one, the anonymization is invertible. Presume that ranges on DI are initially anonymized and, in the course of things, take the intersection B=A φ ([s, t])∩A φ ([u, v]). If φ is range-intersection preserving, then we can recover from the expression of B what the intersection of the pre-anonymized ranges would be, by A φ   −1 (B)=A φ   −1 (A φ ([s, t]∩[u, v]))=[s, t]∩[u, v]. This property enables us to de-anonymize the results that the position-insensitive computation on the anonymized ranges produced. The next step is to show that if φ preserves structure, then it also preserves range intersection. 
     According to a second theorem, if φ: D I →D is an anonymization function which preserves structure, then φ preserves range intersection. 
     To proof this theorem, let [s, t] and [u, v] be ranges on D I . If [s, t] and [u, v] have non-empty intersection values, they must be subranges of the same canonical range. Since φ preserves structure there must exist β such that φ shifts all members of the image of the canonical range under v by β. The elements of D are globally ordered, and the shifting of the numerical values corresponding to [s, t] and [u, v] can be envisioned as shifting elements of D along that global ordering, by |β| units, towards larger values if β is positive, towards smaller values if β is negative. With respect to that order, A φ ([s, t]) shifts [s, t] and A φ ([u, v]) shifts [u, v] exactly |β| positions on D. Likewise, if [x, y]=[s, t]∩[u, v], then A φ ([x, y]) shifts [x, y] exactly |β| positions to align exactly with A φ ([s, t])∩A φ ([u, v]), as required. Now if [s, t] and [u, v] are in the same canonical range but do not intersect, by the same logic, shifting them both in D by the same shift offset β implies they will not intersect. Finally, if [s, t] and [u, v] come from different canonical ranges, then because φ necessarily keeps the images of canonical ranges from overlapping, the intersection of their respective anonymizations is also empty. 
     If D I  is anonymized in such a way that the computer program operating on the anonymized ranges can be insensitive to the anonymization, the anonymization must preserve structure, otherwise the anonymized ranges differ in attributes other than just value. Since the anonymization preserves structure, it has a particular form, of shifting canonical ranges about without overlap. It also preserves range intersections, meaning that the results produced by the position-insensitive computation can be de-anonymized. Any anonymization such that the results of position-insensitive computation can be precisely de-anonymized must have the shifting form. 
     D may comprise an integer or a natural number representation of IP addresses. 
     In the anonymization of range sets, anonymization consists of assigning offsets β i  to the canonical ranges. The offsets are selected to ensure that the anonymized canonical ranges remain separated and leak no information about the values of the pre-anonymized canonical ranges. 
     Given a set of ranges I, the canonical ranges can be identified in time proportional to n log n, where n is the number of ranges, as follows:
         1. In linear time create a list L of range endpoints, r 1 , r 2 , . . . , r m , where a set B i  of ranges which begin with r i  and a set T i  of ranges that terminate at r i  are associated with each i.   2. Sort L. As there are no more than 2n endpoints, this is accomplished in O(n log n) time.   3. With a linear scan of sorted L that uses the B i  and T i  sets to track precisely which ranges encompass each endpoint r, compute the set of ranges C(r) that contain r but do not begin or end at r for each r∈L. Using a range tree data structure, the computation at each r is O(log n).   4. A canonical range is found as [s, t] where C (s) and C (t) are both empty, but C(r) is not empty for every r∈L with s&lt;r&lt;t.       

     Certain details of the algorithm depend on whether the anonymization offsets β i  are constrained (as they are with CIDR block addresses) or unconstrained. 
     In an unconstrained anonymization, taking D to be the natural numbers, let N be the largest value in the IP space to be anonymized (e.g. N=2 32 −1 for IPv4 and N=2 64 −1 for a user domain space under IPv6), let I be a set of ranges on D to anonymize, and let k be the number of canonical ranges on D I . 
     Without loss of generality, the least value to which an address can be mapped is 0. There may well be a minimum value below which assignment should not be made, but the descriptions below are easily amended to accommodate this constraint. The goal is to pack all of the canonical ranges starting at the low end of [0,N] in such a way that provides no indication to an observer of what the original location may have been. If canonical ranges were packed in order of their pre-anonymized appearance, the observer would have knowledge that the native position of a canonical range could not appear earlier than its anonymized position. To defeat that kind of information leakage, the canonical ranges may be randomly permutated, with each permutation having the same probability 1/k! of being chosen. Using the Knuth shuffle, this is accomplished in O(k) time. Re-indexing the range endpoints to reflect the permutation, the first canonical range [s 1 , t 1 ] is mapped to [0, (t 1 −s 1  s 1  with anonymization offset β 1 =−s 1 . This defines φ(s 1 )=0 and φ(t 1 )=(t 1 −s 1 ). The second t range [s 2 , t 2 ] is mapped to [φ(t 1 )+1, φ(t 1 )+1+(t 2 −s 2 )] with offset β2=φ(t 1 )+1−s 2 , so that φ(s 2 )=φ(t 1 )+1 and φ(t 2 )=φ(s 2 )+(t 2 −s 2 ), and so on. 
     In an unconstrained anonymization, IPv4 address ranges usually derive from a CIDR block (e.g. 172.80.8.0/24), and are expressed in the device configurations as CIDR blocks, or as IP addresses with net-masks which are semantically equivalent to CIDR blocks. This constrains the possible anonymization offsets. To anonymize the configuration itself, then a “/24” network in the configuration needs to be transformed into a “/24” network under the anonymization. All CIDR blocks must be remapped to locations that accommodate them, because the starting address of a/d network must have zeros in its 32−d least significant bits. The larger the network, the more zeros the first address must have. With a canonical range, the system finds the CIDR blocks of largest size and ensures that the canonical range is placed to accommodate them. Therefore, if the largest CIDR block with a canonical range is a/d network, then the starting address for the anonymized placement of that CIDR block must have 0 in its 32−d least significant bits. Since the canonical range is a contiguous sequence of IP addresses, ensuring that one of the largest blocks is properly aligned ensures that all the blocks of largest size are aligned and that any smaller blocks are also aligned. 
     To avoid placing smaller networks in ways that inhibit the placement of larger networks, networks are placed in decreasing severity of constraint. Within a set of canonical ranges with the same maximal CIDR block size, the order of their placement is uniformly at random. Once all constrained placements are made, any remaining unconstrained placements are then made.
         1. Classify each canonical range as being constrained if any of its constituent ranges is a CIDR block (two or more addresses), or otherwise unconstrained.   2. Order the constrained canonical ranges in decreasing size of largest constituent CIDR block, and group together canonical ranges whose largest constituent CIDR blocks have the same size. Denote by G n  a group whose defining CIDR block is a /n network.   3. In order of increasing i, randomly permute the members of G i , and pack them one-by-one onto [0,N], beginning at the bottom, in such a way that a network from G i  is aligned so that its /i CIDR sub-ranges are mapped to addresses whose least significant 32−i bits are zero.   4. Left now with only the unconstrained canonical ranges, use the unconstrained algorithm described earlier, packing the unconstrained canonical ranges beginning with the end of the packed constrained canonical ranges.       

     Anonymization and de-anonymization is very efficient, each operation taking only O(log k) time where k is the number of canonical ranges. Space requirements are also low, just O(k). 
     In one embodiment, the anonymization key for the anonymization function φ includes a table with two columns, with as many rows as there are canonical ranges. The ranges may appear in order in the table. To anonymize a value or a subrange, one uses binary search on the rows to efficiently find the canonical range which contains it. The second column gives the shift offset for that canonical range, and the anonymization is simply the addition of the offset to the value or to the endpoints of the range. 
     The de-anonymization is similar, although using a separate key. There number of rows in this key corresponds to the number of canonical ranges, and the anonymized positions of the ranges are given in the first column of each row. Those rows are sorted with respect to those anonymized values. For a given row, the second column is the negated value of the shift offset for the associated canonical range. To determine the de-anonymization of a value or a range, a binary search is performed on the first column to find the corresponding canonical range, then add the negated offset in the second column to the anonymized value, or endpoints of the anonymized range. 
     A path is represented in terms of the source and destination IP ranges, the source and destination port ranges, set of protocols, and sequence of devices and rules which define the path. All of the ranges involved in the path are either from known space or are unshaped with exclusions from known space. To de-anonymize a range from known space, the anonymizing system retrieves the de-anonymization key for the anonymized range of the connected range that must contain it. The shift offset is associated with the connected range, which when negated and added to the endpoints of an anonymized range translates the anonymized range back to the original range. 
     Protocols are identified by well-known identifications in an IP header. In some embodiments, a protocol may be substituted with another integer and de-anonymized by reversing the substitute. 
     The possible state of an observer&#39;s knowledge about the non-anonymized ranges with an a priori joint probability distribution. Denoted by γ i , the original starting location for the i th  range observed in the anonymized configurations. The joint distribution is the set of non-zero probabilities:
 
 Pr ( a   1   ,a   2   , . . . p   n )= Pr{γ   1   =a   1 ,γ 2   =a   2 , . . . ,γ n   =a   n }.
 
     Denote by δ i  the starting position of the i th  anonymized range, and define Δ=(δ 1 , δ 2 , . . . , δ n ). The question of how knowledge of A impacts the posterior probability of where the canonical ranges are located in the original configurations can be answered by Bayes Theorem. 
     
       
         
           
             
               
                 
                   
                     P 
                     ⁢ 
                     
                       r 
                       ⁡ 
                       
                         ( 
                         
                           
                             a 
                             1 
                           
                           , 
                           
                             a 
                             2 
                           
                           , 
                           … 
                           ⁢ 
                           
                               
                           
                           , 
                           
                             
                               p 
                               n 
                             
                             | 
                             Δ 
                           
                         
                         ) 
                       
                     
                   
                   = 
                     
                   ⁢ 
                   
                     
                       Pr 
                       ⁢ 
                       
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     Δ 
                                     | 
                                     
                                       γ 
                                       1 
                                     
                                   
                                   = 
                                   
                                     a 
                                     1 
                                   
                                 
                                 , 
                                 
                                   
                                     γ 
                                     2 
                                   
                                   = 
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   a 
                                   2 
                                 
                                 , 
                                 
                                     
                                 
                                 ⁢ 
                                 … 
                                 ⁢ 
                                 
                                     
                                 
                                 , 
                                 
                                   
                                     γ 
                                     n 
                                   
                                   = 
                                   
                                     a 
                                     n 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         Pr 
                         ⁡ 
                         
                           ( 
                           
                             
                               a 
                               1 
                             
                             , 
                             
                                 
                             
                             ⁢ 
                             
                               a 
                               2 
                             
                             , 
                             … 
                             , 
                             
                               p 
                               n 
                             
                           
                           ) 
                         
                       
                     
                     
                       P 
                       ⁢ 
                       
                         r 
                         ⁡ 
                         
                           ( 
                           Δ 
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     Pr 
                     ⁡ 
                     
                       ( 
                       
                         
                           a 
                           1 
                         
                         , 
                         
                             
                         
                         ⁢ 
                         
                           a 
                           2 
                         
                         , 
                         
                             
                         
                         ⁢ 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           p 
                           n 
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
     because Pr(Δ|γ 1 =a 1 , γ 2 =a 2 , . . . , γ n =a n )=Pr(Δ). This last equivalence follows because placement of the anonymized canonical ranges depend only on their size of their constituent ranges (and this only in the case of constrained ranges); the anonymization is completely independent of the original range&#39;s placement. This shows that the anonymization yields no more information about the pre-anonymized ranges beyond what would otherwise be know about their likely distributions. 
     In the course of anonymizing the representation, a de-anonymization key is created and stored in the key management component. The de-anonymization key identifies for each range object in the original range of integers and the transformed range of integers. A public key that describes the range sizes of each object, indexed by its cryptographically secure identity, is also stored for later use. 
     Referring back to  FIG.  2   , the anonymized representation  128  is transmitted to the remote anonymized systems database  112  on the remote server system  104  once the representation  124  is anonymized. Referring to  FIG.  3   , input data  146  received by the client-side GUI  144  triggers the specification of the system  100  and other parameters to be analyzed by the oblivious analysis engine  132 , which obtains the specific anonymized representation  128  from the remote anonymized systems database  112 . The oblivious analysis engine  132  computes the analysis and stores an anonymized analysis results  148  in the anonymized analysis results database  134 . 
     To de-anonymize the results  148  as shown in  FIG.  4   , a command  150  is received from the user GUI  144  to perform the de-anonymization. The results de-anonymizer module  131  on the client-side system  102  retrieves the anonymized system representation  128  from the remote anonymized systems database  112 , the anonymized analysis results  148  from the anonymized analysis results database  134 , and the private de-anonymization key  130  associated with the system representation  124  from the key management database  110 . Using the de-anonymization key  130 , the results de-anonymizer module  131  inverts the anonymization performed on the ranges of that system representation  124  and presents the de-anonymized results  151  to the user via the GUI  144 . 
     In a further embodiment, the anonymizing system  100  merges two anonymized systems into a larger aggregate system. Upon the receipt of instructions  152  to merge two systems from the GUI, the first and second private keys  154 ,  156  of first and second sets of configurations, respectively, are merged to produce a private anonymization key  158  for the merged system and a public key  160  that identifies the size of each object. The instructions emitted from the GUI also include a command  162  to an oblivious systems merger module  136  to merge the first and second anonymized representations of the first and second sets of configurations, respectively. The oblivious systems merger module  136  retrieves the first and second anonymized representations  163  and the public key  160  from the key management database  110  and produces a merged anonymized system  164  that is stored on the remote anonymized systems database. 
       FIGS.  6 - 11    illustrate a further embodiment of the anonymized system  200  including a client-side system  202  and a remote server side system  204  communicating through the internet  206  or other suitable system. In contrast to the anonymized system  100 , the anonymized system  200  directly anonymizes the set of configurations  218  on the client-side server  202 , and the step of generating the system representation occurs on the remote server system  204  instead of the client-side system  202 . For ease of reference, like reference numbers are used with respect to the embodiment of  FIGS.  1 - 5    and the embodiment of  FIGS.  6 - 11   . 
     Similar to the client-side system  102  within the anonymized system  100 , the client-side system  202  includes a native configurations database  208 , a key management database  210 , a results de-anonymizer module  231 , and a first processor  214  as shown in  FIG.  6   . The client-side server  202  also includes a configuration anonymizer module  226 , which retrieves a set of configurations  218  from the native configurations database  208  and a private key  220  from the key management database  210 , as shown in  FIG.  7   . The configuration anonymizer module  226  creates cryptographically secure range object identities (similar to the system anonymizer module  126  of the anonymizing system  100 ) and applies the transformation directly to the object identities to generate an anonymized configuration  229 . The anonymized configuration  229  is transmitted to an anonymized configuration database  227  on the remote server system  104 . The configuration anonymizer module  226  also generates a de-anonymization key  230  for storage in the key management database  210 . 
     The remote server system  104  includes a system representation module  222 , an anonymized configurations database  227 , an anonymized systems database  212 , an oblivious analysis engine  232 , an anonymized analysis results database  234 , and an oblivious systems merger module  236 . The remote server system  204  may also include a second processor  238  and a second memory  240  including program instructions executable by the second processor  238 . 
     In  FIG.  8   , the anonymized system  200  generates an anonymized system representation  228  for a set of anonymized configurations  229 . Upon receipt of instructions  242  from the graphical user interface  244  on the client-side server  202 , the system representation module  222  on the remote server system  204  retrieves the anonymized configuration  229  from the anonymized configurations database  227  and builds an anonymized representation  228  based on the anonymized configuration  229  using object identities that are obtained from the meta-data associated with the anonymized configurations  229 . The anonymized system representation  228  is then stored in the anonymized systems database  212  on the remote server system  204 . 
       FIG.  9    illustrates the steps undertaken to anonymize the analysis of the anonymizing system  200 . Input data  246  received by the client-side GUI  244  triggers the specification of the system  200  and other parameters to be analyzed by the oblivious analysis engine  232 , which obtains the specific anonymized representation  228  from the remote anonymized systems database  212 . The oblivious analysis engine  232  computes the analysis and stores an anonymized analysis results  248  in the anonymized analysis results database  234 . 
     To de-anonymize the results  248  as shown in  FIG.  10   , a command  250  is received from the user GUI  244  to perform the de-anonymization. The results de-anonymizer module  231  on the client-side system  202  retrieves the anonymized system representation  228  from the remote anonymized systems database  212 , the anonymized analysis results  248  from the anonymized analysis results database  234 , and the private de-anonymization key  230  associated with the anonymized configuration  229  from the key management database  210 . Using the de-anonymization key  230 , the results de-anonymizer module  231  inverts the anonymization performed on the ranges of the anonymized configuration  229  and presents the de-anonymized results  251  to the user via the GUI  244 . 
     In a further embodiment, the anonymizing system  200  merges two anonymized systems into a larger aggregate system. Upon the receipt of instructions  252  to merge two systems from the GUI, the first and second private keys  154 ,  156  of first and second sets of configurations, respectively, are merged to produce a private anonymization key  258  for the merged system and a public key  260  that identifies the size of each object. The instructions emitted from the GUI also include a command  262  to an oblivious systems merger module  236  to merge the first and second anonymized representations of the first and second sets of configurations, respectively. The oblivious systems merger module  236  retrieves the first and second anonymized representations  263  and the public key  260  from the key management database  110  and produces a merged anonymized system  264  that is stored on the remote anonymized systems database  212 . 
     It is the nature of the anonymized configuration or system representation that the sizes of ranges are publically known. A netmask for an IP address identifies a CIDR block of a given size containing the IP address. The anonymization system includes an offset that shifts native ranges without creating overlaps. Information about the original offsets is contained if, for example, it is known that if [a,b] is strictly less than [c,d] and the anonymized [a,b] is strictly less (or strictly greater) than the anonymized [c,d]. Information leakage about the original set of range values will be minimized if knowledge of relative positions of the anonymized ranges gives no better information than random chance about the position of the original range. The cryptographically secured identification of an object range gives no better information than random about the original location of the range, which implies that a placement of connected range that is deterministic function of the identifications of the objects it contains will not leak original position information. Cryptographically secure random permutations may also be used. 
     Aspects of the systems and methods provided herein encompass hardware and software for controlling the relevant functions. Software may take the form of code or executable instructions for causing a processor or other programmable equipment to perform the relevant steps, where the code or instructions are carried by or otherwise embodied in a medium readable by the processor or other machine. Instructions or code for implementing such operations may be in the form of computer instruction in any form (e.g., source code, object code, interpreted code, etc.) stored in or carried by any tangible readable medium. 
     It should be noted that various changes and modifications to the presently preferred embodiments described herein will be apparent to those skilled in the art. Such changes and modifications may be made without departing from the spirit and scope of the present invention and without diminishing its attendant advantages.