Analysis and verification of distributed applications

• US 9,146,829 B1
• Filed: 01/03/2013
• Issued: 09/29/2015
• Est. Priority Date: 01/03/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Allen, Nicholas Alexander
• Primary Examiner(s): Duncan, Marc
• Application Number:
  US13/733,731
• Time in Patent Office: 999 Days
• Field of Search: 714/33, 714/35, 714/38.1, 717/126
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3632 of specific synchronisation aspects
• CPC Class Codes: G06F 11/3668 Software testing software testing in telephone exchanges H04M3/242, testing of hardware G06F11/22
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 11/3692 for test results analysis

Abstract

Systems and methods are described for analyzing and verifying distributed applications. In one embodiment, an application program is parsed and a set of inputs is determined. The application program is executed as one or more independently executable components. During execution, non-deterministic events are modified in order to effectuate a deterministic result. Redundant portions of the set of inputs are aggregated, and the set of inputs is iteratively updated.

Claims

1. A computing system comprising at least one computing node and at least one data store in communication with the at least one computing node, the at least one data store having stored therein computer instructions that, upon execution by the at least one computing node, at least cause the system to:

receive an application program operable to execute in a distributed computing environment;

parse the application program in accordance with one or more verification constraints and based on the parsing;

divide the application program into a plurality of independently executable components; and

determine an initial set of test inputs to the independently executable components;

instantiate a plurality of virtual machines and execute the independently executable components in respective ones of the virtual machines;

modify a non-deterministic event in order to effectuate a deterministic result in accordance with one or more determinism policies in response to a determination that the non-deterministic event has occurred between at least two of the virtual machines;

in response to a determination that application data is to be communicated between at least two of the virtual machines;

generate a data packet that encapsulates the application data along with associated condition variables and data path information;

send the data packet to a destination for the data packet; and

aggregate application data and combine respective condition variable and data path information;

verify one or more verification objectives by using the aggregated application data to represent code execution paths; and

iteratively generate new test inputs based on the verifying until the one or more verification objectives are validated.

2. The computing system according to claim 1, wherein the new inputs are generated based on constraints for executing unexecuted portions of the application program.

3. The computing system according to claim 2, wherein the new inputs are generated based on a plurality of expressions satisfying or negating the constraints and solved to generate a search tree of test inputs.

4. The computing system according to claim 3, wherein the plurality of expressions are associated with nodes in the search tree and the nodes of the search tree are searched to determine identical behavior during an order of execution.

5. The computing system according to claim 1, wherein the non-deterministic event is modified to perform a fixed order of execution.

6. A computer-implemented method for verifying a property of a distributed application program, comprising:

parsing an application program in accordance with one or more constraints for application program conditions;

executing the application program as independently executable components resulting from division of the application program, wherein the independently executable components are executed using an initial set of inputs determined based on the parsing and symbolic evaluation of the independently executable components;

during the executing, modifying a non-deterministic event occurring between at least two of the independently executable components in order to effectuate a deterministic result; and

generating new inputs based on the executing.

7. The method of claim 6, further comprising iteratively generating additional inputs until one or more verification objectives are achieved.

8. The method of claim 6, further comprising aggregating redundant portions of the set of inputs based on the executing.

9. The method of claim 8, wherein the aggregating comprises generating a data packet that encapsulates application data to be communicated between at least two of the independently executable components.

10. The method of claim 9, wherein the data packet includes associated condition variables and data path information and said aggregating further comprises aggregating application data from multiple communication events.

11. The method of claim 8, further comprising applying a hash function to the non-deterministic events and comparing hash results to identify aliased inputs.

12. The method of claim 6, wherein the set of inputs are determined using an expert model.

13. The method of claim 6, further comprising instantiating a plurality of virtual machines and executing the independently executable components in the plurality of virtual machines.

14. The method of claim 6, wherein the non-deterministic events are modified in accordance with one or more determinism policies.

15. The method of claim 6, further comprising verifying one or more verification objectives by using aggregated inputs to represent code execution paths.

16. The method of claim 15, wherein the verifying is performed until a heuristic threshold is reached.

17. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to:

parse an application program in accordance with one or more constraints for application program conditions, wherein the application program is divided into independent components that can be executed as independent processes;

execute the independent components in independent execution environments, wherein the independent components are executed using an initial set of inputs determined based on symbolic evaluation of the independent components;

during execution, modify non-deterministic events in order to effectuate deterministic results; and

identify unexecuted portions of the components and generate new inputs.

18. The non-transitory computer-readable storage media of claim 17, further comprising executable instructions that, when executed by the one or more processors of the computer system, cause the computer system to iteratively generate additional inputs based on results of execution of the components in the independent execution environments.

19. The non-transitory computer-readable storage media of claim 18, wherein the set of inputs are iteratively updated.

20. The non-transitory computer-readable storage media of claim 17, further comprising executable instructions that, when executed by the one or more processors of the computer system, cause the computer system to aggregate redundant portions of the set of inputs.

21. The non-transitory computer-readable storage media of claim 20, further comprising executable instructions that, when executed by the one or more processors of the computer system, cause the computer system to use a hash function to identify aliased inputs.

22. A computing system comprising one or more computing nodes and one or more data stores in communication with the one or more computing nodes, the one or more data stores having stored thereon computer instructions that, upon execution by the one or more computing nodes, at least cause the computing system to:

parse an application program in accordance with one or more constraints for application program conditions;

cause execution of the application program as independently executable components resulting from division of the application program, wherein the independently executable components are executed using an initial set of inputs determined based on the parsing and symbolic evaluation of the independently executable components;

during the execution, modify a non-deterministic event occurring between at least two of the independently executable components in order to effectuate a deterministic result; and

generate new inputs based on the execution.