Patent Description:
Typical computer networks are subject to frequent configuration changes in daily use. These changes can include adding or removing physical or virtual devices (such as gateways, routers, switches, and the like), modifying interfaces, and the like. In many existing networks, and particularly in software-defined networking (SDN), this process is performed manually using resource provisioning programs. For example, administrators can provide input to a provisioning program, which carries out the actual configuration changes required to satisfy the user's intent. In some systems, networks use intent-based configurations, where administrators specify the desired outcome (e.g., "what" the network should do) while the provisioning programs implement that intent (e.g., determine "how" to achieve the outcome). Network configuration is also becoming increasingly automated, and resource provisioning programs that require manual interaction are being replaced with automated systems. In order to operate as intended, these automated systems must be able to identify and understand the manually-configured intents and configurations that exist in the network. Typically, this requires users to manually specify the previous configuration changes. This process is expensive, requires significant time investment, and is error prone, especially as network administrators may no longer recall the changes (or may no longer be available). <CIT> discloses intent specification checks for inconsistencies.

Embodiments of the present disclosure enable identification of manual configuration changes and intent, in a way that allows automated configuration systems to take ownership of these configurations. In an embodiment, if a configuration change was implemented consistently with a resource provisioning system or program, this change can be identified as a "valid" configuration that should be ingested and implemented/controlled by the automation system. In contrast, if the configuration was implemented without use of the established provisioning systems (e.g., as a one-off tweak), some embodiments of the present disclosure can flag the change as suspect, unverified, invalid, or otherwise requiring additional review. That is, because the change was not made using the established program(s) or process(es), the automated system cannot ingest and take ownership of it, because there is no understanding of the inputs used or the desired intent. Additionally, because the change was made without the defined provisioning software, the changes may violate norms or preferences that define how the network should be configured.

In one embodiment, the system described herein applies constraint solving to configuration trees to effectively execute the provisioning code in reverse, in order to identify the inputs originally applied by administrators to arrive at the current configuration. Although service provisioning code (and indeed, most software) is not reversible in the general case, given typical network configurations and software, this problem is highly tractable and embodiments of the present disclosure can reliably handle realistic use cases. In some embodiments of the present disclosure, the configurations of computer networks are modeled as trees, such as using eXtensible Markup Language (XML). Additionally, in embodiments of the present disclosure, service provisioning and/or intent-based networking is implemented as a Domain-Specific Language (DSL) on these trees. In an embodiment, the configuration trees are recursively matched against templates (e.g., constraints), such that if the matching is to fail at any point in the tree, the matching reliably will fail at the first (e.g., highest) level in the tree where the constraint(s) are violated. That is, the system can analyze each node of the configuration tree (beginning at the highest level of the tree) separately, and need not analyze the entire tree simultaneously. If the matching will fail at a given node, the system can potentially identify this failure at a relatively higher level of the tree. Further, in some embodiments, if matching fails at a node, the system need not analyze any children of the failing node, which further improves efficiency and resource usage of the currently described system.

In an embodiment, a configuration tree can be described by a schema, where each schema node in the schema has zero or more instances in the configuration tree, and each configuration node in the configuration tree corresponds to at least one node in the schema. In an embodiment, the schema describes the structure of the provisioning software (e.g., hierarchy, inheritance, data types, and the like). For example, a schema tree may have a "device" node, with child nodes corresponding to flags, interfaces, descriptions, and the like. In an embodiment, the service provisioning code is a schema-aware program P such that for a given schema node S, the program P can be specialized as PS such that given input I, PS(I) yields N, where N is a valid node in the configuration tree for the network. In some embodiments of the present disclosure, the algorithm is applied recursively to each node in the schema, the specialized program, and/or the corresponding node(s) in the configuration, to identify potential inputs representing previously-configured intents. In some embodiments of the present disclosure, the network is configured using intent-based systems. In such an embodiment, administrators can define the desired outcomes (e.g., what they would like the network to do), and the resource provisioning programs can implement those intents by determining precisely how to achieve the desired goal.

In some embodiments, candidates are created based in part on the configuration tree, where each candidate is a set of potential inputs to the service provisioning program. Further, constraints are generated based in part on the service provisioning program, where each constraint represents a limitation or requirement that the input/configuration should comply with, as defined in the provisioning program. If a candidate is incompatible with a constraint, it is eliminated from further consideration. In one embodiment, these eliminated candidates represent configuration changes that cannot be made using the provisioning program. That is, if such an invalid candidate is found in the actual configuration, it must have been made informally (e.g., without use of the provisioning system), rendering the nature of the configuration uncertain and unaccounted for. In one embodiment, these failed candidates are referred to as "invalid" candidates. Although referred to as "invalid," these candidates may, of course, represent desired configuration nodes in the network. These candidates or nodes are referred to as "invalid" only to indicate that they were not created using the defined provisioning software, and thus cannot be verified, explained, or ingested into an automated system.

In an embodiment, if a candidate is compatible with the constraints, it is a valid input for the program, meaning that it can be provided to the provisioning system to generate an output configuration that actually exists in the network. In embodiments, these valid candidates are identified as manually configured intents that were carried out "properly" (e.g., using the provisioning software). These configuration changes can then be ingested into the automated provisioning system, and implemented in the network as desired. Further, in some embodiments, if a candidate ambiguously satisfies a constraint, it is split to generate new candidates. For example, if there are two (or more) values (e.g., sets of inputs) that cause the candidate to satisfy the constraint (and yield configurations that actually exist in the network), two (or more) candidates are generated to reflect these potential inputs.

<FIG> illustrates a workflow <NUM> for identification of manually configured intents that can be ingested into an automated resource provisioning system. In the illustrated workflow <NUM>, Administrators <NUM> interact with one or more Service Provisioning Program(s) <NUM>, in order to generate configurations for one or more networks. As illustrated, this configuration can be represented as a Configuration Tree <NUM>. Additionally, in the illustrated embodiment, the configuration may also be modified externally (e.g., manually and without use of the defined Service Provisioning Programs <NUM>), as indicated by the Other Input <NUM>. In some embodiments, it is preferable to use the Service Provisioning Program(s) <NUM> to make configuration changes, as these programs typically ensure the configuration is consistent and adheres to preferred guidelines, definitions, and the like. However, as is common in existing networks, administrators may also directly modify the configuration, such as to correct a one-off issue that is unique to a particular context. Although this manual configuration is not preferred, it is nevertheless common.

In embodiments of the present disclosure, the Configuration Analysis Application <NUM> analyzes the Configuration Tree <NUM> to classify each portion of the configuration as either "valid" or "legal," indicating that it was implemented using the provisioning software, or "invalid" or "illegal," indicating it was implemented externally to these programs. In the illustrated embodiment, the Configuration Analysis Application <NUM> receives the code for the Service Provisioning Program(s) <NUM>, as well as the Configuration Tree <NUM>. In some embodiments, the Configuration Analysis Application <NUM> also receives the schema used to describe the configuration. In one embodiment, if the schema is not available (or does not exist), the Configuration Analysis Application <NUM> analyzes the Service Provisioning Program(s) <NUM> and/or the Configuration Tree <NUM> to infer and generate the corresponding schema.

In the illustrated embodiment, based on this input, the Configuration Analysis Application <NUM> segregates the Valid Inputs <NUM> from the Invalid Node(s) <NUM>. In one embodiment, Valid Inputs <NUM> correspond to candidates that satisfied each of the generated constraints such that, given the input, the Service Provisioning Program(s) <NUM> will generate one or more nodes that actually exist in the Configuration Tree <NUM>. Similarly, in an embodiment, Invalid Nodes <NUM> correspond to portions of the Configuration Tree <NUM> that cannot have been generated using the Service Provisioning Program(s) <NUM>, and thus were created or modified using other means. As illustrated embodiment, in some embodiments, the Valid Inputs <NUM> are ingested into the Automated Provisioning System <NUM>, such that the underlying configurations can be implemented automatically. In one embodiment, the Automated Provisioning System <NUM> allows the network configuration to be automated while co-existing with human administrators. For example, the Automated Provisioning System <NUM> can be deployed to learn previously-configured intents, and can therefore recreate these intents should the need arise, without requiring administrators to manually configure them again.

In contrast, the Invalid Nodes <NUM> are flagged for Additional Processing <NUM>. In various embodiments, Additional Processing <NUM> may include, for example, review by a human in order to determine the underlying intent, or to make a decision regarding how the configuration should be implemented in the Automated Provisioning System <NUM>. In other embodiments, the Additional Processing <NUM> may include one or more other algorithms, use of heuristics, and the like. In existing systems, all configuration changes must undergo this tedious and error-prone process. However, embodiments of the present disclosure enable the "valid" configurations to be automatically identified and implemented.

<FIG> illustrates a workflow <NUM> showing the operations of an automated Configuration Analysis Application <NUM> in identifying manual changes in a network configuration, according to one embodiment disclosed herein. In the illustrated embodiment, the Service Provisioning Program <NUM> and Provisioning Program Schema <NUM> are provided as inputs to a Constraint Generator <NUM>, which is included in the Configuration Analysis Application <NUM>. In an embodiment, the Constraint Generator <NUM> identifies each schema node in the Provisioning Program Schema <NUM>, and identifies the corresponding portion(s) of the Service Provisioning Program <NUM> that relate to this schema node. In this way, the Constraint Generator <NUM> can generate a set of one or more Constraints <NUM> for each schema node. In an embodiment, each Constraint <NUM> generally indicates a restriction or limitation on valid configuration nodes (e.g., inputs that yield a valid configuration node as output). Nodes in the Configuration Tree <NUM> can then be analyzed in view of these Constraints <NUM> to identify valid and invalid nodes.

As an example, suppose a "flag" node exists in the Provisioning Program Schema <NUM>, and the Service Provisioning Program <NUM> includes a line of code that sets this flag to a constant value. In such an embodiment, the Constraint Generator <NUM> can generate a "constant" constraint, indicating that the only valid value for this "flag" node in the Configuration Tree <NUM> is that identified constant value. Stated differently, for every instance of the "flag" node in the Configuration Tree <NUM>, the value must be equal to the constant specified in the Service Provisioning Program <NUM>. If a given node differs, that node was not generated using the Service Provisioning Program <NUM> (or it was subsequently modified). Instead, it was manually created or modified by a user, without use of the defined programs. Because of this, the automated system may be unable to absorb or ingest that particular node or configuration. In embodiments, the failed node(s) may be reviewed subsequently by a system administrator, or using one or more heuristics or other algorithms.

In the illustrated embodiment, the Provisioning Program Schema <NUM> is also provided to a Candidate Evaluator <NUM>, along with the Configuration Tree <NUM>. In the illustrated embodiment, the Candidate Evaluator <NUM> iteratively and recursively applies the generated Constraints <NUM> for each schema node to the Configuration Tree <NUM> to generate (and modify, narrow, or eliminate) Candidates <NUM>. For example, continuing the above example, if the schema node being analyzed is a "flag," the Candidate Evaluator <NUM> identifies all instances of this particular "flag" node in the Configuration Tree <NUM>. In the illustrated embodiment, the Configuration Analysis Application <NUM> can generate a set of one or more Candidates <NUM>, based on the values observed in the Configuration Tree <NUM>. For example, if the Configuration Tree <NUM> includes three different values for the "flag" node, the Candidate Evaluator <NUM> can generate three separate Candidates <NUM>, one for each discovered value.

As illustrated, these Candidates <NUM> are recursively and iteratively fed back into the Candidate Evaluator <NUM> to continue applying the Constraints <NUM> to the Candidates <NUM>. In an embodiment, as discussed above, if a given Candidate <NUM> fails at least one Constraint <NUM>, it is eliminated from further consideration and is classified as an Invalid Node <NUM>. In some embodiments, the rest of the branch (e.g., all child nodes of the Invalid Node <NUM>) in the Configuration Tree <NUM> are similarly classified as invalid. For example, if an "interface" node is found invalid, all child nodes (such as a "description" node for the interface) are also invalid. In one embodiment, if a given Candidate <NUM> unambiguously satisfies all applicable Constraints <NUM>, it is classified as a Valid Input <NUM>, indicating that the corresponding configuration nodes covered by the Candidate <NUM> are "valid" nodes in the tree. Further, if a given Candidate <NUM> ambiguously satisfies a Constraint <NUM> (e.g., because there are two or more ways the candidate could satisfy the constraint), it is split into multiple Candidates <NUM> for further analysis.

In some embodiments, Candidates <NUM> are modified during the process, such that each Candidate <NUM> can potentially accumulate information each time it passes through the evaluator. That is, in an embodiment, as additional Constraints <NUM> are applied, the Candidate <NUM> can be narrowed or constrained based on the requirement(s) imposed by the Constraint <NUM> and/or the Configuration Tree <NUM>. For example, if a particular Constraint <NUM>, together with the Configuration Tree <NUM>, requires a specific value, the Candidate(s) <NUM> can be modified to include this value. In one embodiment, the Candidate Evaluator <NUM> analyzes all schema nodes in the Provisioning Program Schema <NUM>, and each Candidate <NUM> is then analyzed. In some embodiments, rather than analyzing the entire tree simultaneously, the Configuration Analysis Application <NUM> iteratively and recursively analyzes each schema node in turn. In an embodiment, if a configuration node is found invalid, the Configuration Analysis Application <NUM> ceases consideration of the corresponding branch of the Configuration Tree <NUM>. For example, if the highest-level node in the Provisioning Program Schema <NUM> is a "device" node, the Configuration Analysis Application <NUM> first generates candidates and analyzes each identified device node in the Configuration Tree <NUM>. If any are found invalid at this level of the schema, they are discarded and their child nodes (e.g., interfaces) are ignored.

In contrast, for each device node found valid in the configuration (e.g., if the corresponding candidate covering the device node satisfies the relevant constraints), the Configuration Analysis Application <NUM> can proceed to the next level down the Provisioning Program Schema <NUM> (e.g., an "interface" node) and similarly generate candidates for analysis. In embodiments, this operation can be conducted using a breadth-first search and/or a depth-first search, depending on the particular implementation. For example, in a depth-first system, the Configuration Analysis Application <NUM> may analyze each "device" node entirely (iterating through all of its child nodes, the child nodes of those child nodes, and so on) until the "device" node is found to be valid or invalid (e.g., a Valid Input <NUM> or valid node, or an Invalid Node <NUM> or invalid input). The Configuration Analysis Application <NUM> then iterates through each such device node. In contrast, using a breadth-first search, the Configuration Analysis Application <NUM> analyzes each "device" node, followed by child nodes at a first level of the hierarchy for each device node, and so on, iterating through progressively deeper levels of the tree.

<FIG> illustrates an example Service Provisioning Program <NUM>, Provisioning Program Schema <NUM>, and Configuration Tree <NUM>, according to one embodiment disclosed herein. In the illustrated embodiment, the Service Provisioning Program <NUM>, Provisioning Program Schema <NUM>, and Configuration Tree <NUM> are used as simple examples to aid understanding. Of course, in practice, the Service Provisioning Program <NUM>, Provisioning Program Schema <NUM>, and Configuration Tree <NUM> are likely to be significantly more complex. As illustrated, the example Service Provisioning Program <NUM> receives two inputs, "device" and "interface," and generates a configuration for a device (e.g., in a SDN).

As illustrated, the Provisioning Program Schema <NUM> defines the structure of the Service Provisioning Program <NUM> and Configuration Tree <NUM>, and the nodes that are possible in the ultimate configuration. Specifically, there can be zero or more "device" nodes, each of which can have zero or more child nodes. As illustrated, each "device" node should specify a "device," which is provided as an input to the program. Further, any child nodes of each device node can either be a "FlagA" node, or an "interface" node. In one embodiment, the "FlagA" node has an integer value, and does not have children. Similarly, as illustrated, each "interface" node includes a list of interface(s), and each such node in the Configuration Tree <NUM> can have zero or more child nodes, where each child node is an instance of a "description" node. The description node includes a string. In some embodiments, the Configuration Tree <NUM> cannot include nodes that are not defined in the Provisioning Program Schema <NUM>. In another embodiment, if a node is identified in the Configuration Tree <NUM> without a corresponding node in the Provisioning Program Schema <NUM>, the system can determine that the identified node is "invalid," in that it could not have been produced using the Service Provisioning Program <NUM>.

In some embodiments, if the Provisioning Program Schema <NUM> is not available, the Configuration Analysis Application <NUM> generates one based on the Service Provisioning Program <NUM> and/or the Configuration Tree <NUM>. For example, in one embodiment, the Configuration Analysis Application <NUM> identifies all nodes in the Configuration Tree <NUM>, groups nodes with a shared structure (e.g., "device" nodes, "interface" nodes, and the like) and generates the schema. In another embodiment, the Configuration Analysis Application <NUM> reviews the Service Provisioning Program <NUM> to identify output that it can create (e.g., nodes in the tree).

In the illustrated embodiment, the Service Provisioning Program <NUM> and Provisioning Program Schema <NUM> can be used to generate constraints on the valid inputs for the network configuration. In some embodiments, the constraints are generated on a per-schema node basis. For example, for the device schema node, the Constraint Generator <NUM> can identify the corresponding section(s) of the Service Provisioning Program <NUM>. That is, the Constraint Generator <NUM> identifies all portions of the Service Provisioning Program <NUM> that create or modify "device" nodes. In the illustrated embodiment, the only applicable constraint to the "device" node (as defined in the Service Provisioning Program <NUM>) is an equality constraint specifying that the value must be a list of one or more "devices," which are input by the user. That is, the equality constraint forces the existing candidates to take the value(s) found in the Configuration Tree <NUM>. Similarly, for the "interface" schema node, the Constraint Generator <NUM> can refer to the Service Provisioning Program <NUM> to generate an equality constraint stating that the node, if present, must include a list of one or more "interfaces" supplied by the user.

Turning to the "flagA" schema node, in an embodiment, the Constraint Generator <NUM> can determine that the only valid value is a constant "<NUM>," based on the Service Provisioning Program <NUM>. Further, the "description" node, if present, should include a string that states "Interface for " followed by the same "device" that was used in the corresponding device node for the interface (e.g., the parent). In this manner, the Constraint Generator <NUM> can generate a series of constraints that are applied to each node in the Configuration Tree <NUM> and each candidate, in order to determine whether the node is a valid output of the Service Provisioning Program <NUM>.

As illustrated, the Configuration Tree <NUM> has three device nodes. In an embodiment, the Candidate Evaluator <NUM> begins at the highest level of the schema, and iteratively and/or recursively analyzes subsequently deeper levels. In such an embodiment, the Candidate Evaluator <NUM> begins the analysis with the "device" node in the Provisioning Program Schema <NUM>. As discussed above, the corresponding constraint for the "device" node in the schema is an equality constraint, that forces the remaining candidates to have a value equal to the value(s) found in the Configuration Tree <NUM>. Based on the illustrated Configuration Tree <NUM>, which includes three distinct values for "device," the Candidate Evaluator <NUM> can generate three candidates: {device = "X"}, {device = "Y"}, and {device = "Z"}. Stated differently, in one embodiment, an initial candidate can be imagined that includes all nodes in the configuration (e.g., with no defined input values). Because the first constraint is an equality constraint that forces the candidate(s) to take a value equal to the value(s) in the configuration, application of this constraint splits the initial candidate into three candidates: one for each identified value. These candidates then collectively cover the entire Configuration Tree <NUM> (because no candidates have yet been eliminated).

Thus, at this first level, three candidates are generated, and each remains "valid. " The analysis then continues for the next schema node. In an embodiment, the Candidate Evaluator <NUM> then selects a child node of the "device" node in the schema (e.g., the "flagA" node), and identifies the corresponding constraint. In the illustrated embodiment, this constraint is a constant constraint. In one embodiment, the constant constraint does not modify the candidates (e.g., by taking the value specified in the Configuration Tree <NUM>), but forces them to have the defined constant value. All candidates covering nodes that do not have this value are eliminated. In another embodiment, the constant constraint narrows the candidate by adding the specified value to the candidate's definition. In the illustrated embodiment, the candidates {device = "Y"} and {device = "Z"}, which correspond to the devices Y and Z in the Configuration Tree <NUM>, satisfy this constraint, and are thus considered "constrained" and remain valid. In contrast, the candidate {device = "X"}, corresponding to the device X, fails, because the corresponding value in the Configuration Tree <NUM> for the flagA node belonging to the device X is "<NUM>.

Thus, in an embodiment, the Candidate Evaluator <NUM> can determine that the first candidate, {device = "X"}, is invalid, as is the corresponding branch of the Configuration Tree <NUM>. In one embodiment, the candidate is thus removed from further processing. In some embodiments, this candidate is flagged for review by a human, or for other additional processing.

Continuing with the illustrated example, the Candidate Evaluator <NUM> may then turn to the next node in the Provisioning Program Schema <NUM>: the "interface" node. As discussed above, the corresponding constraint for this schema node is another equality constraint, that narrows each remaining candidate based on the value(s) found in the Configuration Tree <NUM>. In the illustrated embodiment, for the {device = "Y"}, candidate, the Candidate Evaluator <NUM> identifies a value of "If0," and thus constraints or narrows the candidate to be {device = "Y"; interface = "If0"}. For the candidate {device = "Z"}, the constraint does not unambiguously apply. That is, because the Configuration Tree <NUM> includes two interface nodes with differing values for the interface schema node for the candidate {device = "Y"}, the Candidate Evaluator <NUM> splits this candidate into two new ones: {device = "Y"; interface = "If0"} and {device = "Y"; interface = "If1"}.

Continuing to the "description" schema node, the Candidate Evaluator <NUM> once again identifies the corresponding constraint, which is another equality constraint that requires the candidates to have a string matching the one found in the Configuration Tree <NUM>. As a reminder, based on the Service Provisioning Program <NUM>, this constraint further requires that the string value in the configuration node is "Interface for ", followed by the "device" listed in the candidate. If the string does not match, the candidate is eliminated. In the illustrated embodiment, the candidate {device = "Y"; interface = "If0"} thus fails, and is eliminated. That is, the candidate specifies {device = "Y"}, and the description node specifies {description = "Interface for X"}. Because this fails the constraint, the candidate is eliminated and/or flagged for further review.

Similarly, the candidate {device = "Z"; interface = "If1"} fails, because the corresponding string does not match the requirements imposed by the Service Provisioning Program <NUM>. In contrast, the candidate {device = "Z"; interface = "If0"} satisfies this constraint, and remains valid. Because there are no remaining schema nodes to be evaluated, the Candidate Evaluator <NUM> can thereby label this candidate as valid, and absorb the corresponding input into the automated provisioning system.

<FIG> is a block diagram illustrating a Configuration Analysis Device <NUM> configured to automatically identify manual intents in a network, according to one embodiment disclosed herein. As illustrated, the Configuration Analysis Device <NUM> includes a Processor <NUM>, a Memory <NUM>, Storage <NUM>, and a Network Interface <NUM>. In the illustrated embodiment, Processor <NUM> retrieves and executes programming instructions stored in Memory <NUM> as well as stores and retrieves application data residing in Storage <NUM>. Processor <NUM> is representative of a single CPU, multiple CPUs, a single CPU having multiple processing cores, and the like. Memory <NUM> is generally included to be representative of a random access memory. Storage <NUM> may be a disk drive or flash-based storage device, and may include fixed and/or removable storage devices, such as fixed disk drives, removable memory cards, or optical storage, network attached storage (NAS), or storage area network (SAN). Via the Network Interface <NUM>, the Configuration Analysis Device <NUM> can be communicatively coupled with one or more other devices including devices used by administrators, network devices, and the like.

In the illustrated embodiment, the Storage <NUM> includes source code for one or more Service Provisioning Programs <NUM>, corresponding Provisioning Program Schema(s) <NUM> for one or more of the Service Provisioning Programs <NUM>, and a Configuration Tree <NUM>. Although illustrated as residing in Storage <NUM>, in embodiments, the Service Provisioning Program(s) <NUM>, Provisioning Program Schema(s) <NUM>, and Configuration Tree <NUM> may reside in any suitable location. In embodiments, the Service Provisioning Program(s) <NUM> are software used by network administrators to configure and modify the configuration of a network. In one embodiment, the Service Provisioning Program(s) <NUM> are used to configure a software-defined network (SDN), such as by creating and modifying physical and virtual devices, ports, interfaces, forwarding tables, and the like. Generally, the Service Provisioning Program(s) <NUM> are configured to receive user input (such as a name for an interface, or the endpoints of a connection), and modify the configuration of the network based on this input (e.g., by creating a new interface or establishing a connection).

In embodiments, there may be any number of Service Provisioning Programs <NUM> used to configure the network and provision services and resources. In an embodiment, in order to analyze the Configuration Tree <NUM>, the user can provide the Configuration Analysis Application <NUM> with access to the Service Provisioning Program(s) <NUM> and/or their source code. In the illustrated embodiment, each Provisioning Program Schema <NUM> indicates the structure of the corresponding Service Provisioning Program <NUM> (e.g., objects, data types, and the like). In an embodiment, each node in a given Provisioning Program Schema <NUM> can have zero or more instances in the Configuration Tree <NUM>. That is, a given schema node (such as an "interface" node) may or may not be found in the actual configuration, and may have multiple instances in the configuration. In an embodiment, each corresponding configuration node(s) for a given schema node may be associated with one or more particular values (such as a name, description, and the like).

In one embodiment, there is a Provisioning Program Schema <NUM> for each relevant Service Provisioning Program <NUM>. In some embodiments, one or more of the Service Provisioning Programs <NUM> may not be associated with a defined schema. In one embodiment, a user or administrator can define the schema based on the code. In another embodiment, the Configuration Analysis Application <NUM> can analyze the code and/or the configuration to infer the schema. In the illustrated embodiment, the Configuration Tree <NUM> is a tree structure that represents the current configuration of a given network, at a given moment in time. In one embodiment, the Configuration Tree <NUM> includes every element of the network configuration that is of interest to the automated system. In some embodiments, for each configuration node in the Configuration Tree <NUM>, there is a corresponding schema node in one or more of the Provisioning Program Schema(s) <NUM>. In another embodiment, if a configuration node is not found in any of the relevant schemas, the Configuration Analysis Application <NUM> can determine that the configuration node is "invalid" or otherwise unexplained. That is, the node cannot have been created using the available Service Provisioning Program(s) <NUM>. In such a case, the node was either manually created or modified without such software, or there is at least one Service Provisioning Program <NUM> that the Configuration Analysis Application <NUM> is not aware of.

In the illustrated embodiment, the Memory <NUM> includes a Configuration Analysis Application <NUM>. Although illustrated as software residing in memory, in embodiments, the functionality of the Configuration Analysis Application <NUM> can be implemented using hardware, software, or a combination of hardware and software. As illustrated, the Configuration Analysis Application <NUM> includes a Constraint Generator <NUM> and a Candidate Evaluator <NUM>. Although depicted as discrete components for illustration, in embodiments, the operations of the Constraint Generator <NUM> and Candidate Evaluator <NUM> may be combined or divided across any number of components. In an embodiment, the Constraint Generator <NUM> analyzes Service Provisioning Program(s) <NUM> and/or Provisioning Program Schema(s) <NUM> to determine relevant constraints on the Configuration Tree <NUM>. For example, these constraints may include that a given node must have a particular value. Of course, in practice, the constraints are likely to be significantly more complex.

In an embodiment, the Candidate Evaluator <NUM> iteratively and recursively generates candidates, applies the constraints to each candidate, and eliminates or modifies the candidate based on the result of this analysis. Once each relevant constraint has been applied, the Candidate Evaluator <NUM> can determine if any candidates remain. If so, these are valid candidates that reflect legitimate configurations in the network. In one embodiment, each candidate corresponds to a particular node and/or branch in the Configuration Tree <NUM>. In some embodiments, each candidate includes a set of input values that can be applied to one or more Service Provisioning Program(s) <NUM> to create the corresponding node(s) and/or branch(es) in the Configuration Tree <NUM>. In one embodiment, the candidates/nodes that are eliminated (e.g., determined to be invalid) correspond to node(s) and/or branch(es) in the Configuration Tree <NUM> that were not created using the Service Provisioning Program(s) <NUM> (or were modified without use of the programs).

<FIG> is a flow diagram illustrating a method <NUM> of analyzing service provisioning programs and schemas to generate constraints on validly-configured network configuration nodes, according to one embodiment disclosed herein. In the illustrated embodiment, the method <NUM> begins at block <NUM>, where a Constraint Generator <NUM> receives code for one or more resource provisioning programs used to configure a network. At block <NUM>, the Constraint Generator <NUM> similarly receives (or generates) one or more schemas for each of the one or more provisioning programs. The method <NUM> then proceeds to block <NUM>, where the Constraint Generator <NUM> selects a schema node in the received schema(s). The method <NUM> then continues to block <NUM>.

At block <NUM>, the Constraint Generator <NUM> identifies the corresponding program node(s) in the received provisioning program(s). In one embodiment, identifying the corresponding program nodes includes identifying any portions of the program that can modify or establish a value for the schema node. For example, for a "device" node, the corresponding program section would be any portions of the program that create or modify "devices. " Similarly, for an "interface" schema node, the Constraint Generator <NUM> identifies sections of the program that create or modify "interfaces. " The method <NUM> then proceeds to block <NUM>, where the Constraint Generator <NUM> generates one or more constraint(s) that are applicable to the selected schema node, based on the identified program portions.

For example, if the program specifies that a value for a particular flag is always a constant value, the Constraint Generator <NUM> can generate a constraint forcing this value. In various embodiments, there may be any number of constraints generated for a particular schema node. In embodiments, these constraints can include, for example, equality constraints, constant constraints, and the like. Another example of a constraint is an inequality constraint that forces the candidate(s) to have a value that is not equal to the one specified in the constraint. Similarly, in some embodiments, comparator constraints can be utilized (e.g., greater than, greater than or equal to, less than, less than or equal to). In one embodiment, applying a "greater than" constraint can cause each candidate to be split into two candidates: one where the value is "greater than" the specified value, and the other where the value is "less than or equal to" the specified value. In embodiments, the constraints can include any programmatic requirement (such that a value be prime, such that a particular character in a string must match the defined value, and the like). The method <NUM> then continues to block <NUM>, where the Constraint Generator <NUM> determines whether there is at least one additional schema node to be analyzed. If so, the method <NUM> returns to block <NUM>. Otherwise, the method <NUM> terminates at block <NUM>, where the generated constraints are stored for subsequent use.

<FIG> is a flow diagram illustrating a method <NUM> of automatically identifying manually-configured intents in a network configuration, according to one embodiment disclosed herein. In one embodiment, the method <NUM> utilizes the constraints generated by the Constraint Generator <NUM> (e.g., using the method <NUM>) to iteratively and recursively evaluate the Configuration Tree <NUM>. The method <NUM> begins at block <NUM>, where a Candidate Evaluator <NUM> selects a schema node for analysis. As discussed above, in one embodiment, the Candidate Evaluator <NUM> begins at the highest-level node (e.g., the "device" node) in the schema, and recursively iterates through subsequent levels of the schema until all nodes have been considered.

At block <NUM>, the Candidate Evaluator <NUM> retrieves the constraint(s) that are applicable to the selected schema node. The method <NUM> then proceeds to block <NUM>, where the Candidate Evaluator <NUM> selects one of the candidates that are currently considered valid. In one embodiment, the Candidate Evaluator <NUM> generates the initial set of candidates by identifying the relevant configuration node(s) for the top-level schema node, and generates a candidate for each such configuration node (or for each unique value in the configuration nodes). In another embodiment, the Candidate Evaluator <NUM> initially uses a generic candidate that covers the entire configuration tree, and applies the initial constraint(s) to determine whether it should be constrained or otherwise modified. For example, if the top-level schema node is "device," the Candidate Evaluator <NUM> may first use a candidate corresponding to {device = "*"}, where * is a wild card, indicating that the candidate covers all device nodes in the configuration. Application of an equality constraint, as discussed above, would then split this candidate into a number of candidates equal to the number of unique values for "device" found in the configuration.

At block <NUM>, the Candidate Evaluator <NUM> applies the relevant constraint(s) to the selected candidate. In an embodiment, applying the constraint can differ depending on what the underlying constraint is and/or the current contents of the candidate. For example, a "constant" constraint can enforce a constant value for that node in the configuration tree, such that candidates that cover nodes with different values are eliminated. As another example, suppose a constraint requires a parameter P be less than five. If a candidate does not yet have a value for P, the Candidate Evaluator <NUM> can simply record that P < <NUM> in the candidate. Suppose instead that the candidate includes P = <NUM> (e.g., because of a previously-evaluated constraint). In an embodiment, this candidate can remain unchanged because it already satisfies the constraint (and is more specific than the constraint). Alternatively, if the candidate includes P = <NUM>, this candidate is eliminated because it is incompatible with the constraint.

Additionally, in embodiments, there may be multiple constraints for a given parameter. For example, in addition to P < <NUM>, there may also be a P > <NUM> constraint, which further narrows the allowable candidates to ones where <NUM> < P < <NUM>. In this manner, the candidates continue to accumulate information as they are processed. Note that in some embodiments, there is no guarantee for unambiguous results. In practice, however, unambiguous results can be typically expected because actual configurations are being processed (as opposed to hypothetical corner-cases), and because simpler constraints like equality are extremely common. Returning to <FIG> as an example, suppose the currently selected candidate is {device = "X"}. In the illustrated embodiment, this candidate covers the "device X" node in the Configuration Tree <NUM>, and all child nodes for that device node. Thus, when applying the constant constraint (indicating that flagA must be "<NUM>"), the Candidate Evaluator <NUM> will determine that the candidate {device = "X"} fails this constraint, because its corresponding flagA node has an incorrect value.

Continuing to block <NUM>, if the Candidate Evaluator <NUM> determines that the constraint(s) are violated, the method <NUM> proceeds to block <NUM>, where the candidate is removed and flagged as invalid. Continuing the above example, the candidate {device = "X"} is eliminated, and the corresponding portion of the Configuration Tree <NUM> (the "device X" block, as well as its child elements) are removed from further consideration. In some embodiments, these eliminated configuration nodes are flagged for review by a human or other algorithm. For example, a human may need to review internal documentation or other available data to determine why that portion of the network was configured in a way that conflicts with the resource provisioning code. In some embodiments, the system utilizes fuzzy matching and machine learning techniques to identify configurations that appear to be mistakes. For example, if a device has hundreds of parameters that are set according to the template and one that is not compatible, this one node may be due to a mistake by a human. The method <NUM> then continues to block <NUM>.

Returning to block <NUM>, if the Candidate Evaluator <NUM> determines that the constraint(s) are not violated, the method <NUM> proceeds to block <NUM>, where the Candidate Evaluator <NUM> determines whether the constraint(s) were unambiguously satisfied. For example, returning to the example discussed in relation to <FIG>, for the candidate {device = "Z"}, the candidate does not unambiguously satisfy the equality constraint relevant to the "interface" schema node. As discussed above, in an embodiment, the equality constraint forces the candidate to take the value(s) specified in the configuration node(s) that are included in the candidate. Thus, for the candidate {device = "Z"}, this constraint would force the candidate to be narrowed to include {interface = "If0"}, as well as {interface = If1"}. Because there are two valid options, however, the candidate {device = "Z"} ambiguously satisfies the constraint, but does not unambiguously do so.

At block <NUM>, if the Candidate Evaluator <NUM> determines that the constraint is ambiguously satisfied, the method <NUM> proceeds to block <NUM>, where the Candidate Evaluator <NUM> splits the selected candidate into the valid options. In this example, the candidate {device = "Z"} is split into {device = "Z"; interface = "If0"}, and {device = "Z"; interface = "If1"}. The method <NUM> then proceeds to block <NUM>. Returning to block <NUM>, if the constraint is unambiguously satisfied, the method <NUM> also continues to block <NUM>.

At block <NUM>, the Candidate Evaluator <NUM> determines whether there is at least one additional candidate that has not yet had the current constraints applied. If so, the method <NUM> returns to block <NUM> to iteratively consider each candidate. If no such candidates remain to be analyzed, the method <NUM> proceeds to block <NUM>. At block <NUM>, the Candidate Evaluator <NUM> determines whether there is at least one additional schema node that has not yet been applied or considered. If so, the method <NUM> returns to block <NUM>. In this way, the Candidate Evaluator <NUM> recursively analyzes each schema node, beginning at the highest level and proceeding towards the leaves of the schema tree.

If no such schema nodes remain, the method <NUM> terminates at block <NUM>, where the Candidate Evaluator <NUM> marks any remaining candidates as valid. That is, if any candidates remain that have not yet been eliminated, and there are no additional constraints that must be applied, the remaining candidates represent portions of the Configuration Tree <NUM> that were "validly" configured using the resource provisioning software. In an embodiment, each remaining candidate indicates the input(s) that yield these nodes. For example, returning to the example discussed in relation to <FIG>, the candidate {device = "Z"; interface = "If0"} is valid, and indicates that the corresponding inputs for "device" and "interface" yield a configuration that is found in the Configuration Tree <NUM>. In an embodiment, these valid inputs can be ingested into the automated system, such that the system can automatically implement this configuration. However, in an embodiment, "invalid" configurations cannot be included in the automated system, because it is unclear why or how they were created.

<FIG> is a flow diagram illustrating a method <NUM> of automatically identifying and ingesting manual intent into an automated configuration system, according to one embodiment disclosed herein. The method <NUM> begins at block <NUM>, where a Configuration Analysis Application <NUM> receives resource provisioning code used to provision resources in a network. The method <NUM> then proceeds to block <NUM>, where the Configuration Analysis Application <NUM> generates a set of constraints based on the resource provisioning code, wherein the set of constraints define valid network configurations. At block <NUM>, the Configuration Analysis Application <NUM> receives a configuration tree for the network, wherein the configuration tree defines a hierarchical arrangement of configuration elements in the network. Additionally, at block <NUM>, the Configuration Analysis Application <NUM> generates a set of candidates for the network based at least in part on the configuration tree, wherein each candidate in the set of candidates corresponds to one or more nodes in the configuration tree. At block <NUM>, upon determining that a first candidate of the set of candidates satisfies the set of constraints, the Configuration Analysis Application <NUM> records the first candidate as a first manual intent. Finally, the method <NUM> proceeds to block <NUM>, where the Configuration Analysis Application <NUM> integrates the first manual intent into an automated configuration system for the network.

In summary, techniques for automated analysis and classification of network configurations are provided. Resource provisioning code used to provision resources in a network is received, and a set of constraints is generated based on the resource provisioning code, where the set of constraints define valid network configurations. A configuration tree for the network is received, and a set of candidates is generated for the network based at least in part on the configuration tree. Upon determining that a first candidate of the set of candidates does not fail any constraint in the set of constraints, the first candidate is recorded as a manual intent. The manual intent is integrated into an automated configuration system for the network.

In the current disclosure, reference is made to various embodiments. When elements of the embodiments are described in the form of "at least one of A and B," it will be understood that embodiments including element A exclusively, including element B exclusively, and including element A and B are each contemplated. Furthermore, although some embodiments disclosed herein may achieve advantages over other possible solutions or over the prior art, whether or not a particular advantage is achieved by a given embodiment is not limiting of the scope of the present disclosure. Thus, the aspects, features, embodiments and advantages disclosed herein are merely illustrative and are not considered elements or limitations of the appended claims except where explicitly recited in a claim(s). Likewise, reference to "the invention" shall not be construed as a generalization of any inventive subject matter disclosed herein and shall not be considered to be an element or limitation of the appended claims except where explicitly recited in a claim(s).

Claim 1:
A method (<NUM>) comprising:
receiving (<NUM>) resource provisioning code used to provision and configure resources in a network;
generating (<NUM>) a set of constraints based on the resource provisioning code, wherein the set of constraints define valid network configurations that can be implemented using the resource provisioning code;
receiving (<NUM>) a configuration tree (<NUM>) for the network, wherein the configuration tree defines a hierarchical arrangement of configuration elements in the network and includes one or more valid nodes (<NUM>) that were generated using the resource provisioning code and one or more invalid nodes (<NUM>) that were not generated using the resource provisioning code;
generating (<NUM>) a set of candidates for the network based at least in part on the configuration tree, wherein each candidate in the set of candidates corresponds to one or more nodes in the configuration tree, and wherein the set of candidates includes one or more valid nodes (<NUM>) and one or more invalid nodes (<NUM>); and
upon determining (<NUM>), by operation of one or more computer processors, that a first candidate of the set of candidates satisfies the set of constraints and is a valid node (<NUM>), recording the first candidate as a first manually configured intent; and
integrating (<NUM>) the first manually configured intent into an automated configuration system for the network.