Static-analysis-assisted dynamic application crawling architecture

• US 10,152,488 B2
• Filed: 09/02/2015
• Issued: 12/11/2018
• Est. Priority Date: 05/13/2015
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Desineni, Kalyan, Sankaranarasimhan, Manikandan, Sarpasayanam, Vasanthakumar
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US14/843,929
• Publication Number:
  US 20160335348A1
• Time in Patent Office: 1,196 Days
• 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. An apparatus for automated acquisition of content from an application and improved searching of the content in response to a query from a user device, the apparatus comprising:

a memory; and

at least one processor performing static analysis, the at least one processor being configured to, using static analysis;

identify application state templates of the application, and

identify user interface elements that 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,

wherein the at least one processor performs graph creation, the at least one processor being further 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,

wherein the at least one processor performs link extraction, the at least one processor being further configured to;

execute the application, and

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

wherein the at least one processor performs scraping, the at least one processor being further 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 the memory of the apparatus, and

wherein the at least one processor is further configured to transmit search results in response to the query from the user device.

2. The apparatus of claim 1, wherein the at least one processor performs graph optimization, the at least one processor being further 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 at least one processor extracts links according to the optimized graph data structure.

3. The apparatus 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 apparatus 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 apparatus of claim 4, wherein the at least one processor is further 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 apparatus of claim 1, wherein extraction of links by the at least one processor includes the at least one processor being further 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 apparatus of claim 6, wherein extraction of links by the at least one processor includes the at least one processor being further 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 apparatus of claim 6, wherein extraction of links by the at least one processor includes the at least one processor being further 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 apparatus of claim 8, wherein scraping by the at least one processor includes the at least one processor being further 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 apparatus of claim 1, wherein the at least one processor is further configured to generate an updated graph data structure based on the graph data structure in response to real-time data from link extraction performed by the at least one processor, wherein the at least one processor is further configured to operate based on the updated graph data structure.

11. The apparatus of claim 10, wherein the at least one processor is further 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 apparatus of claim 1, wherein link extraction by the at least one processor includes the at least one processor being further configured to execute the application within an emulator.

13. The apparatus of claim 12, wherein scraping by the at least one processor includes the at least one processor being further configured to execute the instance of the application within a second emulator.

14. A search apparatus for improved acquisition of content and searching of the content in response to a query from a user device, the search apparatus comprising:

a memory; and

at least one processor performing static analysis, the at least one processor being configured to, using static analysis;

identify application state templates of the application, and

identify user interface elements that 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,

wherein the at least one processor performs graph creation, the at least one processor being further 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,

wherein the at least one processor performs link extraction, the at least one processor being further configured to;

execute the application, and

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

wherein the at least one processor performs scraping, the at least one processor being further 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 the memory of the search apparatus;

wherein the at least one processor performs set generation, the at least one processor being further configured to, in response to a query from a user device, select records from the memory to form a consideration set of records,

wherein the at least one processor performs set processing, the at least one processor being further configured to assign a score to each record of the consideration set of records,

wherein the at least one processor performs results generation, the at least one processor being further configured to respond to the user device with a subset of the consideration set of records to display results of the query on the user device, wherein the subset is selected based on the assigned scores, and

wherein the at least one processor is further configured to transmit search results in response to the query from the user device.

15. A method of automated acquisition of content from an application and improved searching of the content in response to a query from a user device, the method comprising:

using static analysis, performed by at least one processor of an apparatus for automated content acquisition and provision, the 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, performed by the at least one processor, identifying user interface elements that are configured to transition between states instantiated from different ones of the identified application state templates;

creating, using the at least one processor, 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, using the at least one processor 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, using the at least one processor, 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 memory of the apparatus,

wherein the at least one processor is further configured to transmit search results in response to the query from the user device.

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.

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

28. A method of operating a mobile application search apparatus and improved searching of content in response to a query from a user device, the method comprising:

using static analysis, performed by at least one processor of the mobile application search apparatus, the 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, performed by the at least one processor, identifying user interface elements that are configured to transition between states instantiated from different ones of the identified application state templates;

creating, using the at least one processor, 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, using the at least one processor, 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, using the at least one processor, text and metadata from application states corresponding to endpoints of the recorded paths;

storing information based on the extracted text and metadata in a memory of the mobile application search apparatus;

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, using the at least one processor, with a subset of the consideration set of records to display results of the query on the user device, wherein the subset is selected based on the assigned scores.