Distributed execution of a network vulnerability scan

• US 10,721,260 B1
• Filed: 03/22/2017
• Issued: 07/21/2020
• Est. Priority Date: 03/22/2017
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Schlarp, Charles, Williams, Joshua
• Primary Examiner(s): Feild, Lynn D
• Assistant Examiner(s): Almamun, Abdullah
• Application Number:
  US15/466,772
• Time in Patent Office: 1,217 Days
• Field of Search: 726 25
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: H04L 63/1433 Vulnerability analysis

Abstract

Systems for performing a network scan of one or more targets are provided. The systems select, from functions related to performing a network scan of a target, a first group of functions that are ready to execute at a first time. The first group of functions may be executed by a distributed computing system in parallel to generate first and second results. A third function may then be identified as ready to execute based on the first result, and a fourth function may be excluded from the network scan based on the second result.

Claims

1. A system, comprising:

an electronic data store configured to store a plurality of results received during a network scan;

and a network scanning system in communication with the electronic data store and comprising one or more hardware computing devices configured to execute specific computer-executable instructions that upon execution cause the network scanning system to;

receive information identifying a plurality of functions each implementing a corresponding test of a plurality of tests, the plurality of functions including;

a first function corresponding to a first test of the plurality of tests;

a second function corresponding to a second test of the plurality of tests, the second test identifying a first condition and a first result, of the first test, that satisfies the first condition;

a third function corresponding to a third test of the plurality of tests; and

a plurality of dependent functions that require execution of the third function in order to be ready for execution, wherein to be ready for execution, the third function requires a second condition to be satisfied, the second condition being dependent upon the first result;

select, from the plurality of functions, a first group of functions that are ready to execute, the first group of functions including the first function;

cause a network accessible services system to execute the first group of functions in parallel to perform a first portion of the network scan on a first target, the first result being produced by executing the first function and being stored in the electronic data store;

obtain the first result;

determine that the first result satisfies the first condition;

determine, based on the first result satisfying the first condition, that the second function is ready to execute;

select, from the plurality of functions subsequent to execution of the first group of functions, a second group of functions that are ready to execute, the second group of functions including the second function;

cause the network accessible services system to execute the second group of functions in parallel;

determine that the first result does not satisfy the second condition; and

determine that the third function and the plurality of dependent functions are not required to be executed to complete the network scan for the first target.

2. The system of claim 1, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the network scanning system to:

determine, prior to execution of the first function, that the first result is related to the first condition;

create a first dependency relationship between the first function and the second function;

determine, prior to execution of the second function, that the second test produces a second result related to a second condition; and

create a second dependency relationship between the second function and a fourth function corresponding to a fourth test of the plurality of tests, the fourth test identifying the second condition, wherein the second dependency relationship indicates that the fourth function depends on the second function; and

generate a directed acyclic graph comprising;

a first node associated with the first function, a second node associated with the second function, and a third node associated with the fourth function; and

a first edge pointing from the first node toward the second node and a second edge pointing from the second node toward the third node.

3. The system of claim 2, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the network scanning system to:

select the first group of functions by selecting a first group of nodes from the directed acyclic graph that have no edges pointing toward them;

subsequent to the first group of functions being executed, remove from the directed acyclic graph a second group of nodes corresponding to functions that have been executed and a third group of nodes corresponding to functions for which a corresponding condition was not satisfied; and

select the second group of functions by selecting a fourth group of nodes from the acyclic graph that have no edges pointing toward them.

4. The system of claim 2, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the network scanning system to:

determine, based on the second result, that a fifth function of the plurality of functions is not required to execute to complete the network scan;

remove a fifth node representing the fifth function from the directed acyclic graph; and

remove at least one node of the plurality of nodes connected to the fifth function by an outgoing edge of the fifth node from the directed acyclic graph.

5. The system of claim 1, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the network scanning system to, subsequent to causing the network accessible services system to execute the second group of functions:

determine that a fourth function in the second group of functions did not execute to completion;

select a third group of functions that are ready to execute, the third group of functions including the fourth function; and

cause the network accessible services system to execute the third group of functions.

6. A system, comprising one or more hardware computing devices configured to execute specific computer-executable instructions that upon execution cause the one or more hardware computing devices to:

select, from a plurality of functions implementing a network scan of a target, a first group of functions that are ready to execute, the first group of functions including a first function and a second function;

cause a distributed computing system to execute the first group of functions in parallel, wherein execution of the first function generates a first result, and execution of the second function generates a second result;

determine, based on the first result, that a third function of the plurality of functions is ready to execute;

cause the distributed computing system to execute the third function;

determine that a fourth function of the plurality of functions cannot be executed as part of the network scan based on the second result; and

in response to determining that the fourth function cannot be executed as part of the network scan, inhibit the fourth function from being executed in connection with performing the network scan.

7. The system of claim 6, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the one or more hardware computing devices to:

determine that the target is unavailable at a time that the third function is ready to execute;

wait to cause the third function to be executed until the target becomes available; and

cause, subsequent to the target becoming available, the third function to be executed by the distributed computing system.

8. The system of claim 6, wherein the third function is dependent on the first function based on the presence of a first condition that must be satisfied before the third function is ready to execute, and wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the one or more hardware computing devices to determine that the first condition has been satisfied based on the first result.

9. The system of claim 8, wherein each function of the plurality of functions is represented by a node of a plurality of nodes in a directed acyclic graph with a one to one correspondence between the plurality of functions and the plurality of nodes, and an edge pointing from a first node representing the first function to a third node representing the third function represents the first condition that must be satisfied before the third function is ready to execute.

10. The system of claim 9, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the one or more hardware computing devices to determine that the first function and the second function have no edges pointing toward them in the directed acyclic graph, and that the first function and the second function are ready to execute based on the absence of incoming edges to the first node and the second node.

11. The system of claim 9, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the one or more hardware computing devices to:

identify a first group of nodes of the plurality of nodes without incoming edges; and

select the first group of functions based on nodes in the first group of nodes.

12. The system of claim 9, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the one or more hardware computing devices to:

determine, based on the second result, that a fifth function of the plurality of functions is not required to execute to complete the network scan;

remove a fifth node representing the fifth function from the directed acyclic graph; and

remove at least one node of the plurality of nodes connected to the fifth function by an outgoing edge of the fifth node from the directed acyclic graph.

13. The system of claim 9, wherein the one or more hardware computing devices are further configured to execute specific computer-executable instructions that upon execution cause the one or more hardware computing devices to:

remove the first node and one or more outgoing edges of the first node from the directed acyclic graph after the first function has been executed; and

remove a second node corresponding to the second function and one or more outgoing edges of the second node from the directed acyclic graph after the second function has been executed.

14. A method, comprising:

selecting, from a plurality of functions related to performing a network scan of a target, a first group of functions that are ready to execute at a first time, including a first function and a second function;

causing a distributed computing system to execute the first group of functions in parallel, wherein execution of the first function causes information to be sent to the target and generates a first result, and execution of the second function generates a second result;

determining that a third function of the plurality of functions is ready to execute based on the first result, wherein the third function was not ready to execute at the first time;

determining that the target is unavailable at a time when the third function is ready to execute;

in response to determining that the target is unavailable, waiting to cause the third function to be executed until the target becomes available;

causing, subsequent to the target becoming available, the third function to be executed by the distributed computing system;

determining that a fourth function of the plurality of functions cannot be executed as part of the network scan based on the second result;

in response to determining that the fourth function cannot be executed as part of the network scan, inhibiting the fourth function from being executed in connection with performing the network scan.

15. The method of claim 14, wherein the third function is dependent on the first function based on the presence of a first condition that must be satisfied before the third function is ready to execute, and determining that the third function of the plurality of functions is ready to execute further comprises determining that the first condition has been satisfied based on the first result.

16. The method of claim 15, wherein:

each function of the plurality of functions is represented by a node of a plurality of nodes in a directed acyclic graph with a one to one correspondence between the plurality of functions and the plurality of nodes, and an edge pointing from a first node representing the first function to a third node representing the third function represents the first condition that must be satisfied before the third function is ready to execute;

the first function and the second function have no edges pointing toward them in the directed acyclic graph at the first time, and

selecting the first group of functions further comprises determining that the first function and the second function are ready to execute based on the absence of incoming edges.

17. The method of claim 16, wherein the method further comprises identifying a first group of nodes of the plurality of nodes without incoming edges, and selecting the first group of functions further comprises selecting the first group of functions based on nodes in the first group of nodes.

18. The method of claim 16, further comprising:

removing a fourth node representing the fourth function from the directed acyclic graph, and

removing at least one node of the plurality of nodes connected to the fourth function by an outgoing edge of the fourth node from the directed acyclic graph.

19. The method of claim 16, further comprising:

determining, based on the second result, that a fifth function of the plurality of functions is not required to execute to complete the network scan;

removing a fifth node representing the fifth function from the directed acyclic graph; and

removing at least one node of the plurality of nodes connected to the fifth function by an outgoing edge of the fifth node from the directed acyclic graph.

20. The method of claim 16, further comprising:

removing the first node and one or more outgoing edges of the first node from the directed acyclic graph after the first function has been executed; and

removing a second node corresponding to the second function and one or more outgoing edges of the second node from the directed acyclic graph after the second function has been executed.