Static-Analysis-Assisted Dynamic Application Crawling Architecture

• US 20160335348A1
• Filed: 09/02/2015
• Published: 11/17/2016
• Est. Priority Date: 05/13/2015
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Quixey, Inc.
• Inventors: DESINENI, Kalyan, SANKARANARASIMHAN, Manikandan, SARPASAYANAM, Vasanthakumar
• Granted Patent: US 10,152,488 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06F 3/04847 Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]

Abstract

A system for automated acquisition of content from an application includes a static analysis module. Using static analysis (analyzing code of the application independent of executing the code), the static analysis module identifies application state templates of the application and identifies user interface elements that, when actuated by a user, transition between states instantiated from different ones of the identified state templates. A graph creation module creates a graph data structure including nodes corresponding to the identified state templates and edges connecting the nodes. The edges are transitions corresponding to the identified user interface elements. A link extractor module executes the application and determines and records paths to states within the executing application according to the graph data structure. A scraper module, within an executing instance of the application, extracts text and metadata from states corresponding to endpoints of the recorded paths.

Claims

1. A system for automated acquisition of content from an application, the system comprising:

a static analysis module configured to, using static analysis;

identify application state templates of the application and

identify user interface elements that, when actuated by a user, are configured to transition between states instantiated from different ones of the identified application state templates,

wherein the static analysis includes analyzing code of the application independent of executing the code;

a graph creation module configured to create a graph data structure including nodes and edges connecting the nodes, wherein the nodes correspond to the identified application state templates, and wherein the edges correspond to transitions between the identified application state templates corresponding to the identified user interface elements;

a link extractor module configured to;

execute the application and

determine and record paths to application states within the executing application according to the graph data structure; and

a scraper module configured to, within an executing instance of the application, extract text and metadata from application states corresponding to endpoints of the recorded paths, wherein information based on the extracted text and metadata is stored in a data store.

2. The system of claim 1 further comprising a graph optimization module configured to create an optimized graph data structure by (i) removing cycles from the graph data structure and (ii) removing redundant edges from the graph data structure, wherein the link extractor module operates according to the optimized graph data structure.

3. The system of claim 2 wherein the graph data structure includes a head node corresponding to a default application state template of the application and wherein, upon execution, the application presents a state instantiated from the default application state template.

4. The system of claim 3 wherein the edges are directed and each have a starting node and an ending node, wherein the starting node corresponds to an application state template having a user interface event configured to cause a transition to the ending node, and wherein none of the edges have the head node as the ending node.

5. The system of claim 4 wherein the graph optimization module is configured to create the optimized graph data structure such that:

each of the nodes of the graph data structure is present in the optimized graph data structure;

the optimized graph data structure retains edges from the graph data structure required for, for each node of the nodes that is not the head node, a shortest path from the head node to the node; and

the optimized graph data structure omits edges not required for the shortest paths.

6. The system of claim 1 wherein the link extractor module is configured to, for each path defined by the graph data structure, follow the path within the executing application and add application states reachable from an endpoint of the path to an application state list.

7. The system of claim 6 wherein the link extractor module is configured to, for each path defined by the graph data structure, add application states reachable from intermediate states along the path to the application state list.

8. The system of claim 6 wherein the link extractor module is configured to, for each application state in the application state list, record a series of user interface events used to reach the application state.

9. The system of claim 8 wherein the scraper module is configured to, for each application state in the application state list, (i) reach the application state by replaying the recorded series of user interface events to the executing application and (ii) extract text and metadata from the application state.

10. The system of claim 1 further comprising a guide update module configured to generate an updated graph data structure based on the graph data structure in response to real-time data from the link extractor module, wherein the link extractor module is configured to operate based on the updated graph data structure.

11. The system of claim 10 wherein the guide update module is configured to generate the updated graph data structure by, in response to a direct programming call being available to reach a first node of the nodes, creating a new edge directly from a head node of the nodes to the first node.

12. The system of claim 1 wherein the link extractor module is configured to execute the application within an emulator.

13. The system of claim 12 wherein the scraper module is configured to execute the instance of the application within a second emulator.

14. A search system comprising:

the system of claim 1;

the data store;

a set generation module configured to, in response to a query from a user device, select records from the data store to form a consideration set of records;

a set processing module configured to assign a score to each record of the consideration set of records; and

a results generation module configured to respond to the user device with a subset of the consideration set of records, wherein the subset is selected based on the assigned scores.

15. A method of automated acquisition of content from an application, the method comprising:

using static analysis, identifying application state templates of the application, wherein the static analysis includes analyzing code of the application independent of executing the code;

using static analysis, identifying user interface elements that, when actuated by a user, are configured to transition between states instantiated from different ones of the identified application state templates;

creating a graph data structure including nodes and edges connecting the nodes, wherein the nodes correspond to the identified application state templates, and wherein the edges correspond to transitions between the identified application state templates corresponding to the identified user interface elements;

executing the application;

determining and recording paths to application states within the executing application according to the graph data structure;

within an executing instance of the application, extracting text and metadata from application states corresponding to endpoints of the recorded paths; and

storing information based on the extracted text and metadata in a data store.

16. The method of claim 15 further comprising creating an optimized graph data structure by (i) removing cycles from the graph data structure and (ii) removing redundant edges from the graph data structure, wherein determining and recording is performed according to the optimized graph data structure.

17. The method of claim 16 wherein the graph data structure includes a head node corresponding to a default application state template of the application and wherein, upon execution, the application presents a state instantiated from the default application state template.

18. The method of claim 17 wherein the edges are directed and each have a starting node and an ending node, wherein the starting node corresponds to an application state template having a user interface event configured to cause a transition to the ending node, and wherein none of the edges have the head node as the ending node.

19. The method of claim 18 wherein:

each of the nodes of the graph data structure is present in the optimized graph data structure;

the optimized graph data structure retains edges from the graph data structure required for, for each node of the nodes that is not the head node, a shortest path from the head node to the node; and

the optimized graph data structure omits edges not required for the shortest paths.

20. The method of claim 15 wherein the determining and recording paths includes, for each path defined by the graph data structure, following the path within the executing application and adding application states reachable from an endpoint of the path to an application state list.

21. The method of claim 20 wherein the determining and recording paths includes, for each path defined by the graph data structure, adding application states reachable from intermediate states along the path to the application state list.

22. The method of claim 20 wherein the determining and recording paths includes, for each application state in the application state list, recording a series of user interface events used to reach the application state.

23. The method of claim 22 further comprising, for each application state in the application state list, reaching the application state by replaying the recorded series of user interface events to the executing application, wherein the text and metadata are extracted from the application state.

24. The method of claim 15 further comprising generating an updated graph data structure based on the graph data structure in response to real-time data from the executing application, wherein the determining and recording paths is performed based on the updated graph data structure.

25. The method of claim 24 wherein the generating the updated graph data structure includes, in response to a direct programming call being available to reach a first node of the nodes, creating a new edge directly from a head node of the nodes to the first node.

26. The method of claim 15 wherein the executing the application is performed within a first emulator.

27. The method of claim 26 wherein the extracting text and metadata is performed from within a second emulator executing the application.

28. A method of operating a mobile application search system, the method comprising:

the method of claim 15;

in response to receiving a query from a user device, selecting records from the data store to form a consideration set of records;

assigning a score to each record of the consideration set of records; and

responding to the user device with a subset of the consideration set of records, wherein the subset is selected based on the assigned scores.

29. A non-transitory computer-readable medium storing processor-executable instructions configured to perform the method of claim 15.