Crawling of object model using transformation graph

• US 8,296,722 B2
• Filed: 10/06/2008
• Issued: 10/23/2012
• Est. Priority Date: 10/06/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yoshihama, Sachiko, Kawanaka, Shinya, Tateishi, Takaaki, Segal, Ory, Sharabani, Adi, Pistoia, Marco, Podjarny, Guy
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): Wang, Ben C
• Application Number:
  US12/246,065
• Publication Number:
  US 20100088668A1
• Time in Patent Office: 1,478 Days
• Field of Search: None
• US Class Current: 717/104
• CPC Class Codes: G06F 8/10 Requirements analysis; Specification techniques

Abstract

A transformation tree for an object model (OM) is defined. The transformation tree has nodes interconnected by edges, where each node is connected to at most one other tree node. Each node corresponds to a state of the OM; each edge corresponds to an event causing the OM to transition from the state of one node to the state of another node. A transformation graph for the OM is constructed by simulating the transformation tree. The transformation graph has nodes interconnected by edges, and is a directed graph in which each node is connected to one or more other nodes. Each node corresponds to a state of the OM; each edge corresponds to an event causing the OM to transition from the state of one node to the state of another node. Crawling-oriented actions are performed in relation to the OM by being performed in relation to the transformation graph.

Claims

1. A method executed by a processor and comprising:

defining a transformation tree for an object model, the transformation tree having a plurality of tree nodes connected to one another by a plurality of tree edges, the transformation tree being a directed acyclic graph in which each tree node is connected to at most one other tree node, each tree node corresponding to a state of the object model, each tree edge corresponding to an event causing the object model to transition from a state of one tree node to a state of another tree node;

constructing a transformation graph for the object model by simulating the transformation tree for the object model, the transformation graph having a plurality of graph nodes connected to one another by a plurality of graph edges, the transformation graph being a directed graph in which each graph node is connected to one or more other graph nodes, each graph node corresponding to a state of the object model, each graph edge corresponding to an event causing the object model to transition from a state of one graph node to a state of another graph node;

performing one or more crawling-oriented actions in relation to the object model by performing the crawling-oriented actions in relation to the transformation graph for the object model that has been constructed; and

,

displaying results of the crawling-oriented actions performed in relation to the object model,

wherein the transformation graph is different from the transformation tree.

2. The method of claim 1, wherein constructing the transformation graph for the object model comprises evaluating a state of the object model to which a graph node corresponds and returning a label representing characteristics of the state.

3. The method of claim 2, wherein constructing the transformation graph for the object model further comprises determining whether the characteristics of the state of a first graph node is similar to the characteristics of the state of a second graph node, where the state of the first graph node is similar to the state of the second graph node where one or more conditions are true, the conditions comprising:

active properties of a web page corresponding to the state of the object model represented by the first graph node are similar to active properties of a web page corresponding to the state of the object model represented by the second graph node;

a structure of the object model within the state of the first graph node is similar to a structure of the object model within the state of the second graph node;

the state of the first graph node resulted from script execution similar to script execution resulting in the state of the second graph node.

4. The method of claim 3, wherein constructing the transformation graph for the object model further comprises merging graph nodes representing similar states of the object model.

5. The method of claim 1, wherein constructing the transformation graph for the object model comprises constructing the transformation graph until a predetermined number of iterations of node generations of the transformation graph have been achieved.

6. The method of claim 1, wherein constructing the transformation graph for the object model comprises constructing the transformation graph until a predetermined number of states of the object model have been simulated.

7. The method of claim 1, wherein the object model is one of:

a document object model (DOM) representing a dynamic web site; and

,

a programming language model for a self-mutating computer program.

8. A non-transitory computer-readable medium having stored thereon:

computer-executable instructions for defining a transformation tree for a document object model (DOM) representing a dynamic web site, the transformation tree having a plurality of tree nodes connected to one another by a plurality of tree edges, the transformation tree being a directed acyclic graph in which each tree node is connected to at most one other tree node, each tree node corresponding to a state of the DOM, each tree edge corresponding to an event causing the DOM to transition from a state of one tree node to a state of another tree node;

computer-executable instructions for constructing a transformation graph for the DOM by simulating the transformation tree for the DOM, the transformation graph having a plurality of graph nodes connected to one another by a plurality of graph edges, the transformation graph being a directed graph in which each graph node is connected to one or more other graph nodes, each graph node corresponding to a state of the DOM, each graph edge corresponding to an event causing the DOM to transition from a state of one graph node to a state of another graph node; and

,

computer-executable instructions for performing one or more crawling-oriented actions in relation to the DOM by performing the crawling-oriented actions in relation to the transformation graph for the DOM that has been constructed, and for displaying results of the crawling-oriented actions performed in relation to the DOM,

wherein the transformation graph is different from the transformation tree.

9. The computer-readable medium of claim 8, wherein constructing the transformation graph for the DOM comprises evaluating a state of DOM to which a graph node corresponds and returning a label representing characteristics of the state.

10. The computer-readable medium of claim 9, wherein constructing the transformation graph for the DOM further comprises determining whether the characteristics of the state of a first graph node is similar to the characteristics of the state of a second graph node.

11. The computer-readable medium of claim 10, wherein constructing the transformation graph for the DOM further comprises merging graph nodes representing similar states of the DOM.

12. The computer-readable medium of claim 10, wherein the state of the first graph node is similar to the state of the second graph node where one or more conditions are true, the conditions comprising:

active properties of a web page corresponding to the state of the DOM represented by the first graph node are similar to active properties of a web page corresponding to the state of the DOM represented by the second graph node;

a structure of the DOM within the state of the first graph node is similar to a structure of the DOM within the state of the second graph node;

the state of the first graph node resulted from script execution similar to script execution resulting in the state of the second graph node.

13. The computer-readable medium of claim 8, wherein constructing the transformation graph for the DOM comprises constructing the transformation graph until a predetermined number of iterations of node generations of the transformation graph have been achieved.

14. The computer-readable medium of claim 8, wherein constructing the transformation graph for the DOM comprises constructing the transformation graph until a predetermined number of states of the DOM have been simulated.

15. The computer-readable medium of claim 8, wherein the event of each graph edge corresponds to a user-initiated JavaScript event and an intrinsic event such as a timer event.

16. The computer-readable medium of claim 8, wherein the crawling-oriented actions comprise testing security vulnerabilities of the dynamic web site.

17. A computerized system comprising:

hardware including one or more of a processor and a memory;

a simulation component implemented via the hardware to simulate a transformation tree for an object model, the transformation tree having a plurality of tree nodes connected to one another by a plurality of tree edges, the transformation tree being a directed acyclic graph in which each tree node is connected to at most one other tree node, each tree node corresponding to a state of the object model, each tree edge corresponding to an event causing the object model to transition from a state of one tree node to a state of another tree node; and

,

a construction component implemented via the hardware to construct a transformation graph for the object model based on the transformation tree for the object model being simulated by the simulation component, the transformation graph having a plurality of graph nodes connected to one another by a plurality of graph edges, the transformation graph being a directed graph in which each graph node is connected to one or more other graph nodes, each graph node corresponding to a state of the object model, each graph edge corresponding to an event causing the object model to transition from a state of one graph node to a state of another graph node,

wherein the transformation graph is different from the transformation tree.

18. The computerized system of claim 17, further comprising a performance component implemented via the hardware to perform one or more crawling-oriented actions in relation to the object model by performing the crawling-oriented actions in relation to the transformation graph for the object model that has been constructed, and to display results of the crawling-oriented actions performed in relation to the object model.

19. The computerized system of claim 17, wherein the construction component is to evaluate a state of the object model to which a graph node corresponds and to return a label representing characteristics of the state.

20. The computerized system of claim 19, wherein the construction component comprises a merging sub-component to determine whether the characteristics of the state of a first graph node is similar to the characteristics of the state of a second graph node, and to merge the first graph node with the second graph node where the first and the second graph nodes represent similar states of the object model.