Method and apparatus for AI-driven automatic test script generation

• US 10,552,299 B1
• Filed: 08/14/2019
• Issued: 02/04/2020
• Est. Priority Date: 08/14/2019
• Status: Active Grant

• Current Assignee: Appvance Inc.
• Original Assignee: Appvance Inc.
• Inventors: Surace, Kevin, Lara Lopez, Luis Carlos, Mora Corrales, Oscar Gerardo
• Primary Examiner(s): Chowdhury, Ziaul A
• Application Number:
  US16/540,992
• Time in Patent Office: 174 Days
• CPC Class Codes: G06F 11/3672 Test management
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149

Abstract

Models of certain groups of graphical user interface (GUI) objects (e.g., menu objects, product objects, title objects, etc.) are created. A website is then modeled as a state machine (also called a blueprint), in which states are used to model webpages of the website. Identifying characteristics of the states are specified based on the models of the GUI objects. Certain scanning options are used to reduce the complexity of the state machine and accelerate the state machine creation process, known as the “one per page” and “once per app” scanning options. After the state machine model of the website has been created, test cases are generated as traversals through the state machine. In one embodiment, user logs direct the generation of test cases so that the test cases resemble past user behavior.

Claims

1. A method for generating a test script to test a web application based on a user log of past user interactions with the web application and a blueprint that models the web application, wherein the blueprint includes a state machine, in which states of the state machine correspond to at least one of (i) application pages of the web application or (ii) actions that are performed to transition from one of the application pages to another one of the application pages, and edges of the state machine correspond to transitions between the states of the state machine, the method comprising:

creating, by a processor, a data structure with a root node corresponding to a root node of the blueprint, and setting a current node equal to the root node of the data structure;

receiving, by the processor, a first request from the user log;

computing, by the processor, a similarity score between the first request and each candidate action/request pair in the blueprint, wherein each candidate action/request pair includes an action from the state machine that is paired with a corresponding request from the state machine;

for non-zero ones of the similarity scores, adjusting, by the processor, the similarity score based on a number of steps to reach the candidate action/request pair associated with the similarity score from a node of the blueprint corresponding to the current node of the data structure, wherein a determination of the steps to reach the candidate action/request pair takes into account candidate action/request pairs that have been depleted from the node of the blueprint corresponding to the current node of the data structure;

eliminating, by the processor, candidate action/request pairs in the blueprint by comparing the adjusted similarity score to a threshold;

for each of the remaining candidate action/request pairs, storing, by the processor, the remaining candidate action/request pairs as terminal nodes from the current node in the data structure;

determining, by the processor, whether there are remaining requests in the user log;

if there are remaining requests in the user log, (i) receiving a next request from the user log, (ii) computing a similarity score between the next request and each candidate action/request pair in the blueprint, and (iii) for each of the terminal nodes in the data structure, setting the current node equal to the terminal node and repeating the method starting with the adjusting step; and

otherwise, if there are no remaining requests in the user log, determining, by the processor, a traversal through the data structure with a highest aggregate similarity score, and constructing, by the processor, the test script based on the determined traversal through the data structure and the blueprint.

2. The method of claim 1, wherein the first request includes one or more of an Internet protocol (IP) address, a method, a URL and a hint.

3. The method of claim 1, wherein the user log comprises sequentially recorded requests that are transmitted from a common Internet protocol (IP) address.

4. The method of claim 1, wherein the similarity score between the first request and each candidate action/request pair in the blueprint is computed as a linear combination of local similarity scores, wherein each of the local similarity scores measures a similarity between a portion of a URL of the first request and a portion of a URL of a respective candidate action/request pair that corresponds to the portion of the URL of the first request.

5. The method of claim 4, wherein each of the local similarity scores is computed as a Jaro-Winkler distance between the portion of the URL of the first request and the portion of the URL of the respective candidate action/request pair that corresponds to the portion of the URL of the first request.

6. The method of claim 1, further comprising storing the remaining candidate action/request pairs in the data structure.

7. The method of claim 1, further comprising, for each of the remaining candidate action/request pairs, storing, in the data structure, the adjusted similarity score associated with the remaining candidate action/request pair.

8. The method of claim 1, further comprising, for each of the remaining candidate action/request pairs, storing, in the data structure, a sequence of steps from the node of the blueprint corresponding to the current node of the data structure to reach the remaining candidate action/request pair.

9. The method of claim 1, wherein constructing the test script based on the determined traversal through the data structure and the blueprint comprises determining a traversal through the blueprint based on the traversal through the data structure, and recording actions in the test script specified by edges or states traversed by the traversal through the blueprint.

10. The method of claim 9, wherein the actions recorded in the test script include one or more of user experience (UX) level actions and application programming interface (API) level actions.

11. The method of claim 1, wherein the test script includes one or more of a user experience (UX) level test script or an application programming interface (API) level test script, wherein the UX level test script includes a sequence of user actions to be performed on the web application, and wherein the API level test script includes a sequence of hypertext transfer protocol (HTTP) requests to be transmitted to a server hosting the web application.

12. A non-transitory machine-readable storage medium for generating a test script to test a web application based on a user log of past user interactions with the web application and a blueprint that models the web application, wherein the blueprint includes a state machine, in which states of the state machine correspond to at least one of (i) application pages of the web application or (ii) actions that are performed to transition from one of the application pages to another one of the application pages, and edges of the state machine correspond to transitions between the states of the state machine, the non-transitory machine-readable storage medium comprising instructions that, when executed by a processor of the computing system, cause the processor to:

create a data structure with a root node corresponding to a root node of the blueprint, and setting a current node equal to the root node of the data structure;

receive a first request from the user log;

compute a similarity score between the first request and each candidate action/request pair in the blueprint, wherein each candidate action/request pair includes an action from the state machine that is paired with a corresponding request from the state machine;

for non-zero ones of the similarity scores, adjust the similarity score based on a number of steps to reach the candidate action/request pair associated with the similarity score from a node of the blueprint corresponding to the current node of the data structure, wherein a determination of the steps to reach the candidate action/request pair takes into account candidate action/request pairs that have been depleted from the node of the blueprint corresponding to the current node of the data structure;

eliminate candidate action/request pairs in the blueprint by comparing the adjusted similarity score to a threshold;

for each of the remaining candidate action/request pairs, store the remaining candidate action/request pairs as terminal nodes from the current node in the data structure;

determine whether there are remaining requests in the user log;

if there are remaining requests in the user log, (i) receive a next request from the user log, (ii) compute a similarity score between the next request and each candidate action/request pair in the blueprint, and (iii) for each of the terminal nodes in the data structure, set the current node equal to the terminal node and repeat the method starting with the adjusting step; and

otherwise, if there are no remaining requests in the user log, determine a traversal through the data structure with a highest aggregate similarity score, and construct the test script based on the determined traversal through the data structure and the blueprint.

13. The non-transitory machine-readable storage medium of claim 12, further comprising instructions that cause the processor to store the remaining candidate action/request pairs in the data structure.

14. The non-transitory machine-readable storage medium of claim 12, further comprising instructions that cause the processor to, for each of the remaining candidate action/request pairs, store, in the data structure, a sequence of steps from the node of the blueprint corresponding to the current node of the data structure to reach the remaining candidate action/request pair.

15. The non-transitory machine-readable storage medium of claim 12, wherein constructing the test script based on the determined traversal through the data structure and the blueprint comprises determining a traversal through the blueprint based on the traversal through the data structure, and recording actions in the test script specified by edges or states traversed by the traversal through the blueprint.

16. The non-transitory machine-readable storage medium of claim 15, wherein the actions recorded in the test script include one or more of user experience (UX) level actions and application programming interface (API) level actions.

17. A computing device for generating a test script to test a web application based on a user log of past user interactions with the application and a blueprint that models the application, wherein the blueprint includes a state machine, in which states of the state machine correspond to at least one of (i) application pages of the web application or (ii) actions that are performed to transition from one of the application pages to another one of the application pages, and edges of the state machine correspond to transitions between the states of the state machine, the computing device comprising:

a processor; and

a memory storing instructions that, when executed by a processor of the computing system, cause the processor to;

create a data structure with a root node corresponding to a root node of the blueprint, and setting a current node equal to the root node of the data structure;

receive a first request from the user log;

compute a similarity score between the first request and each candidate action/request pair in the blueprint, wherein each candidate action/request pair includes an action from the state machine that is paired with a corresponding request from the state machine;

for non-zero ones of the similarity scores, adjust the similarity score based on a number of steps to reach the candidate action/request pair associated with the similarity score from a node of the blueprint corresponding to the current node of the data structure, wherein a determination of the steps to reach the candidate action/request pair takes into account candidate action/request pairs that have been depleted from the node of the blueprint corresponding to the current node of the data structure;

eliminate candidate action/request pairs in the blueprint by comparing the adjusted similarity score to a threshold;

for each of the remaining candidate action/request pairs, store the remaining candidate action/request pairs as terminal nodes from the current node in the data structure;

determine whether there are remaining requests in the user log;

if there are remaining requests in the user log, (i) receive a next request from the user log, (ii) compute a similarity score between the next request and each candidate action/request pair in the blueprint, and (iii) for each of the terminal nodes in the data structure, set the current node equal to the terminal node and repeat the method starting with the adjusting step; and

otherwise, if there are no remaining requests in the user log, determine a traversal through the data structure with a highest aggregate similarity score, and construct the test script based on the determined traversal through the data structure and the blueprint.

18. The computing device of claim 17, further comprising instructions that cause the processor to store the remaining candidate action/request pairs in the data structure.

19. The computing device of claim 18, further comprising instructions that cause the processor to, for each of the remaining candidate action/request pairs, store, in the data structure, a sequence of steps from the node of the blueprint corresponding to the current node of the data structure to reach the remaining candidate action/request pair.

20. The computing device of claim 18, wherein constructing the test script based on the determined traversal through the data structure and the blueprint comprises determining a traversal through the blueprint based on the traversal through the data structure, and recording actions in the test script specified by edges or states traversed by the traversal through the blueprint.