Crawling for extracting a model of a GUI-based application

• US 9,652,360 B2
• Filed: 04/04/2014
• Issued: 05/16/2017
• Est. Priority Date: 04/04/2014
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Prasad, Mukul R.
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US14/245,741
• Publication Number:
  US 20150286355A1
• Time in Patent Office: 1,138 Days
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 11/3668 Software testing software testing in telephone exchanges H04M3/242, testing of hardware G06F11/22

Abstract

A method of crawling a graphical user interface (GUI) based application may include performing a first-time crawl of a first sequence of actions of the GUI-based application. The first-time crawl may be a first time that the first sequence of actions is crawled. Further, the first sequence of actions may be a prefix of a second sequence of actions that includes one or more additional actions than the first sequence of actions. The method may also include extending the first-time crawl by the one or more additional actions such that the second sequence of actions is crawled during the first-time crawl. Further, the method may include determining a first input/output sequence associated with the first sequence of actions based on the first-time crawl. Additionally, the method may include determining a second input/output sequence associated with the second sequence of actions based on the first-time crawl.

Claims

1. A method of crawling a graphical user interface (GUI) based application, the method comprising:

performing a first-time crawl of a first sequence of actions of a graphical user interface (GUI) based application, the first-time crawl being a first time that the first sequence of actions is crawled, the first sequence of actions being a prefix of a second sequence of actions that includes one or more additional actions that occur after the first sequence of actions, the actions included in the first sequence of actions and the second sequence of actions being inputs that cause the GUI-based application to move between states;

extending the first-time crawl by the one or more additional actions such that the second sequence of actions is crawled during the first-time crawl;

determining a first input/output sequence associated with the first sequence of actions based on the first-time crawl, the first input/output sequence including the first sequence of actions as a first input and including a first state as a first output;

determining a second input/output sequence associated with the second sequence of actions based on the first-time crawl, the second input/output sequence including the second sequence of actions as a second input and including, as a second output, a second state of the GUI-based application that is encountered during the first-time crawl in response to performance of the second sequence of actions; and

generating a model for the GUI-based application based on the first input/output sequence and the second input/output sequence.

2. The method of claim 1, further comprising:

determining that a state of the GUI-based application encountered during the first-time crawl of the first sequence of actions has not been previously observed; and

extending the first-time crawl based on the determination that the state has not been previously observed.

3. The method of claim 2, wherein extending the first-time crawl includes extending the first-time crawl by at least two actions based on the determination that the state has not been previously crawled such that the second sequence of actions includes at least two more actions than the first sequence of actions.

4. The method of claim 2, wherein determining that the first state has not been previously observed is based on encountering a screen that has not been previously observed.

5. The method of claim 1, further comprising:

executing an L* algorithm with respect to the GUI-based application;

obtaining a response to a query generated by the L* algorithm using one or more of the first input/output sequence and the second input/output sequence;

obtaining an output of the L* algorithm based on the response; and

generating the model as a deterministic finite-state machine model for the GUI-based application based on the output of the L* algorithm.

6. The method of claim 5, further comprising:

receiving a plurality of queries output by the L* algorithm, each of the plurality of queries including a sequence of actions of the GUI-based application;

determining that a first query of the plurality of queries is a prefix of one or more prefixes of a second query of the plurality of queries;

performing an on-demand crawl of the second query; and

determining a first-query input/output sequence of the first query and a second-query input/output sequence of the second query from the on-demand crawl and based on the determination that the first query is the prefix of the second query such that a first response to the first query and a second response to the second query are both generated from the on-demand crawl.

7. The method of claim 6, further comprising:

modifying an observation table of the L* algorithm based on one or more of the first-query input/output sequence and the second-query input/output sequence before crawling one or more other queries of the plurality of queries; and

executing the L* algorithm with respect to the GUI-based application using the modified observation table to determine whether the modified observation table is closed and consistent before crawling the one or more other queries of the plurality of queries.

8. The method of claim 5, further comprising:

receiving a plurality of queries output by the L* algorithm, each of the plurality of queries including a sequence of actions of the GUI-based application;

obtaining a response to a query of the plurality of queries;

modifying an observation table of the L* algorithm based on the response to the query before crawling one or more other queries of the plurality of queries; and

executing the L* algorithm with respect to the GUI-based application using the modified observation table to determine whether the modified observation table is closed and consistent before crawling the one or more other queries of the plurality of queries.

9. The method of claim 8, further comprising generating a new plurality of queries when the modified observation table is not closed and consistent.

10. A method of crawling a graphical user interface (GUI) based application, the method comprising:

receiving a plurality of queries for crawling a graphical user interface (GUI) based application, each of the plurality of queries including a sequence of actions of the GUI-based application, the actions included in the sequence of actions being inputs that cause the GUI-based application to move between states;

determining that a first query of the plurality of queries is a prefix of one or more prefixes of a second query of the plurality of queries, the first query including a first sequence of actions, the second query including a second sequence of actions, and the first query being a prefix of one or more prefixes of the second query in that the second sequence of actions includes the first sequence of actions and one or more additional actions that occur after the first sequence of actions;

performing an on-demand crawl of the second query without performing a separate on-demand crawl of the first query based on determining that the first query is a prefix of one or more prefixes of the second query; and

determining a first-query input/output sequence of the first query and a second-query input/output sequence of the second query from the on-demand crawl and based on the determination that the first query is the prefix of the second query such that a first response to the first query and a second response to the second query are both generated from the on-demand crawl, the first-query input/output sequence including the first sequence of actions as a first input and including, as a first output, a first state of the GUI-based application that is encountered during the on-demand crawl in response to performance of the first sequence of actions, the second-query input/output sequence including the second sequence of actions as a second input and including, as a second output, a second state of the GUI-based application that is encountered during the on-demand crawl in response to performance of the second sequence of actions.

11. The method of claim 10, further comprising:

generating the plurality of queries with an L* algorithm;

modifying an observation table of the L* algorithm based on one or more of the first-query input/output sequence and the second-query input/output sequence; and

executing the L* algorithm with respect to the GUI-based application using the modified observation table to determine whether the modified observation table is closed and consistent.

12. The method of claim 10, further comprising:

generating the plurality of queries with an L* algorithm;

modifying an observation table of the L* algorithm based on one or more of the first-query input/output sequence and the second-query input/output sequence; and

executing the L* algorithm with respect to the GUI-based application using the modified observation table to determine whether the modified observation table is closed and consistent before crawling one or more other queries of the plurality of queries.

13. One or more processors configured to execute computer instructions to cause a system to perform operations for crawling a graphical user interface (GUI) based application, the operations comprising:

performing a first-time crawl of a first sequence of actions of a graphical user interface (GUI) based application, the first-time crawl being a first time that the first sequence of actions is crawled, the first sequence of actions being a prefix of a second sequence of actions that includes one or more additional actions that occur after the first sequence of actions, the actions included in the first sequence of actions and the second sequence of actions being inputs that cause the GUI-based application to move between states;

extending the first-time crawl by the one or more additional actions such that the second sequence of actions is crawled during the first-time crawl;

determining a first input/output sequence associated with the first sequence of actions based on the first-time crawl, the first input/output sequence including the first sequence of actions as a first input and including a first state as a first output;

determining a second input/output sequence associated with the second sequence of actions based on the first-time crawl, the second input/output sequence including the second sequence of actions as a second input and including, as a second output, a second state of the GUI-based application that is encountered during the first-time crawl in response to performance of the second sequence of actions; and

generating a model for the GUI-based application based on the first input/output sequence and the second input/output sequence.

14. The one or more processors of claim 13, wherein the operations further comprise:

determining that a state of the GUI-based application encountered during the first-time crawl of the first sequence of actions has not been previously observed; and

extending the first-time crawl based on the determination that the state has not been previously observed.

15. The one or more processors of claim 14, wherein extending the first-time crawl includes extending the first-time crawl by at least two actions based on the determination that the state has not been previously crawled such that the second sequence of actions includes at least two more actions than the first sequence of actions.

16. The one or more processors of claim 14, wherein determining that the first state has not been previously observed is based on encountering a screen that has not been previously observed.

17. The one or more processors of claim 13, wherein the operations further comprise:

executing an L* algorithm with respect to the GUI-based application;

obtaining a response to a query generated by the L* algorithm using one or more of the first input/output sequence and the second input/output sequence;

obtaining an output of the L* algorithm based on the response; and

generating the model as a deterministic finite-state machine model for the GUI-based application based on the output of the L* algorithm.

18. The one or more processors of claim 17, wherein the operations further comprise:

receiving a plurality of queries output by the L* algorithm, each of the plurality of queries including a sequence of actions of the GUI-based application;

determining that a first query of the plurality of queries is a prefix of one or more prefixes of a second query of the plurality of queries;

performing an on-demand crawl of the second query; and

determining a first-query input/output sequence of the first query and a second-query input/output sequence of the second query from the on-demand crawl and based on the determination that the first query is the prefix of the second query such that a first response to the first query and a second response to the second query are both generated from the on-demand crawl.

19. The one or more processors of claim 18, wherein the operations further comprise:

modifying an observation table of the L* algorithm based on one or more of the first-query input/output sequence and the second-query input/output sequence before crawling one or more other queries of the plurality of queries; and

executing the L* algorithm with respect to the GUI-based application using the modified observation table to determine whether the modified observation table is closed and consistent before crawling the one or more other queries of the plurality of queries.

20. The one or more processors of claim 17, wherein the operations further comprise:

receiving a plurality of queries output by the L* algorithm, each of the plurality of queries including a sequence of actions of the GUI-based application;

obtaining a response to a query of the plurality of queries;

modifying an observation table of the L* algorithm based on the response to the query before crawling one or more other queries of the plurality of queries; and

executing the L* algorithm with respect to the GUI-based application using the modified observation table to determine whether the modified observation table is closed and consistent before crawling the one or more other queries of the plurality of queries.