System and method for automatic retrieval of structured online documents

[00002] The present application claims the benefit from U.S. Provisional Patent Application Ser. No. 60/235,058 filed Sep. 25, 2000, entitled “SYSTEM AND METHOD FOR RECORDING STRUCTURED ONLINE DOCUMENT NAVIGATION AND FORM SUBMISSION COMMANDS AND AUTOMATIC REPLAYING OF THE RECORDED COMMANDS FOR DYNAMICALLY GENERATED ONLINE DOCUMENTS,” the entire disclosure of which is incorporated herein by reference.

[00003] The present invention relates to automatic retrieval of a document linking to a starting document that has a static address on a data network, and more particularly, to recording a sequence of commands that causes a browser in a computer system to navigate from a starting document to a target document on a data network.

[heading-00004] Terminology

[00005] Terminology related to the invention is explained in the following.

[00006] Navigation Command

[00007] Basic instructions that perform navigation from one document (web page) to another, or prepare data for such navigation. The command may be one of: (i) hyperlinks embedded in the page; (ii) form fields contained in online forms; (iii) submission of basic authentication credentials; (iv) clicks of HTML element to cause invocation of client-side JavaScript embedded in the web page.

[00008] Script.

[00009] A recorded or otherwise created sequence of navigation commands.

[00010] Starting Document.

[00011] The first document (web page) in a sequence of documents (web pages) visited under the control of a script. The starting document is identified by a static web address, such as URL. For password-protected session-based documents, this is usually the page where user ID and password is entered.

[00012] Target Document.

[00013] The last document (web page) in a sequence of documents (web pages) visited under the control of a script. If a script has more than one command in it, then the target document is dynamically generated and will have a dynamic address.

[00014] Control Element.

[00015] Control elements represent a command or a group of commands. Control element of a online document may be clicked to cause navigation from one online document to another online document, or from one control element to another. Control elements can be one of: (i) hyperlinks, (ii) form Submit button, (iii) clickable HTML element that cause navigation JavaScript to run, (iv) etc.

[00016] Logical Tree (Document Tree).

[00017] The data structure that describes the structure of an online document or relationships between control elements. A logical tree consists of nodes and nodes are connected by edges. If there is an edge leading from node a to node b, it means that node b represents the part of online document that is a subset of the part of the document represented by node a such that b covers the biggest element that still is a subset of a. One node that has no edge directed to it is called a root node of the tree. A logical tree can be obtained for each control element in an online document, such as hyperlinks, form submit button, clickable HTML element that cause navigation JavaScript to run, etc., describing the relationship between the control element and other control elements and online documents.

[00018] Document Object Model (DOM).

[00019] A standardized way of representing online document as a tree. In DOM, every HTML tag is represented by a tree node and the top-level HTML tag is represented by the document tree root. More details are provided below.

[00020] Structured online documents, such as HTML and XML documents are widely available on the World Wide Web (WWW). While some web pages are linked using static online addresses, such as URL (Universal Resource Locator), some pages are linked to a starting page using dynamic addresses. These pages are dynamically generated by a server computer and as such, every page received by a browser has a unique address and a unique set of links in it. Such documents usually contain data that may be periodically updated, wherein such update does not substantially change the format of presentation of such data.

[00021] These documents are usually dynamically generated by web servers. Data contained in the documents may be introduced from certain data sources, such as online databases. The documents may contain dynamic data, whose content changes from time to time. However, since these documents are automatically generated by computers, the document structure remains substantially the same for a relatively long period.

[00022] Oftentimes, documents that contains dynamic data or are security-sensitive are not identified by a static (does not change with time) online address, such as Universal Resource Locator or URL. Instead, a computer user must start from a starting document that has static address and go through several intermediate documents linking to the starting document before the user can finally retrieve the target document from the server. On some of these intermediate documents, the user must enter authentication data, such as a user ID and password. On some other intermediate documents, users must make choices presented to him as a variety of links or as an online form that collects data needed to continue navigation.

[00023] In many cases, servers deliberately generate web pages with globally unique addresses and links in these pages in order to increase the security of online transactions and make the regenerate attacks hard or impossible. As a result, every time users want to access the target document, they must navigate through a series of documents and enter numerous commands before they can access the target document.

[00024] Examples of online documents as described above include (1) shipment tracking information provided by couriers: users typically have to start from the starting document that contains a tracking request form, fill out the tracking request form, submit required information, and further link to several pages before reaching the page containing tracking results. (2) Bank account balance for an individual or corporation from its bank web site: users typically are asked to enter User ID and Password on the starting page, and then brought to the Welcome page. The users are then requested to make an account selection and brought to the page that contains the selected account details. (3) Stock trading accounts provided by online stock brokerage firms: users typically are asked to login with User ID and Password on the starting page. Then the users are brought to the Welcome Page and then to the Stock Trade page, where the users are asked to fill out an online form that describes his desired transaction. The users are then brought to the confirmation page and asked to confirm the transaction.

[00025] These browsing procedures are often troublesome. Therefore, there is a need for retrieving target documents by automatic generation of navigation command sequences. There is also a need to automatically regenerate the sequence of online document navigation commands that lead from a starting document that has static address to a desired target document that is dynamically generated and has dynamically generated addresses.

[heading-00026] Another need exists for generating navigation command sequences in an unattended mode and in a non-GUI environment. For instance, a user may use a wireless device such as a cell phone to instruct a server to run a bank account extraction or stock trade script (sequence of commands) for him. There is another need to eliminate the need to re-enter verification information, such as User IDs and Passwords, every time a user wishes to retrieve a target document. There is also a need to automate the navigation steps and validation information entries.

[00027] These and other needs are addressed by the present invention. The present invention relates to recording of command sequences and retrieval of a document linking to a starting document that has a static address on a data network. A sequence of commands that cause a browser in a computer system to navigate from a starting document to a target document on a data network is recorded using structured document trees. The recorded sequence of commands causes the browser to navigate from the starting document though a sequence of intermediate documents to the refreshed version of a target document. The invention allows recording and regenerating of the navigation command sequences even when the online documents are dynamically generated by a server computer and thus have dynamic online addresses that change every time the documents are regenerated.

[00028] A system according to the present invention records control elements, such as hyperlinks or form submission buttons, clicked by a user in a logical tree of a document on which the hyperlink or the button are embedded. Although addresses of intermediate and target web pages may change, the linkage structure remains the same. By recording the document tree structure and regenerating the hyperlink or button that is located in the same document tree, the same target page will be retrieved.

[00029] Therefore, a system according to the present invention records and later regenerates a sequence of navigation commands that leads the browser from the page that has a static address to the target page.

[00030] A method for automatic retrieval of a target document that links to a starting document having a static address, comprising the steps of: (a) recording at least one control element selected by a user to link from the starting document to the target document; (b) identifying a logical tree for each control element; (c) recording the logical tree identified in step (b); and (d) generating commands represented by the at least one control element to link from the starting document to the target document; wherein one of the control elements represents a dynamic address of the target document. In one aspect, step (a) further comprises recording input data submitted by the user. In another aspect, step (d) further comprises submitting the input data that was submitted by the user.

[00031] A method for creating a script for automatic retrieval of a target document that links to a starting document having a static address, comprising the steps of: (a) recording at a control element selected by a user during linking from the starting document to the target document; (b) identifying a logical tree for the control element; (c) recording the logical tree identified in step (b); (d) determining whether the target document is retrieved; and (e) repeating steps (a) to (d) in response to the target document not having been retrieved. In one aspect, step (a) further comprises recording input data submitted by the user. In another aspect, the steps of creating the script end in response to a control signal indicating that the target document has been retrieved.

[00032] A machine-readable medium bearing instructions for automatic retrieval of a target document that links to a starting document having a static address, the instructions being arranged to cause a data processing system upon execution thereby to perform the steps of: (a) recording at least one control element selected by a user to link from the starting document to the target document; (b) identifying a logical tree for each control element; (c) recording the logical tree identified in step (b); and (d) generating commands represented by the at least one control element to link from the starting document to the target document; wherein one of the control elements represents a dynamic address of the target document.

[00033] A data processing system for automatic retrieval of a target document that links to a starting document having a static address, comprising: a processor for processing data;

• • [00034] a memory; a data storage device for storing data; an input device for inputting data;
  • [00035] a communication interface configured for coupling to the data transmission network; a bus coupling to the input device, the memory, the data storage device, the communication interface, and the processor; the data storage device bearing instructions to cause the data processing system upon execution of the instructions by the processor to perform the steps of: (a) recording at least one control element selected by a user to link from the starting document to the target document in the data storage device; (b) identifying a logical tree for each control element; (c) recording the logical tree identified in step (b) in the data storage device; (d) generating commands represented by the at least one control element to link from the starting document to the target document; and (e) submitting control signals via the communication interface based on the commands generated in step (d); wherein one of the control elements represents a dynamic address of the target document.

[00036] Still other objects and advantages of the present invention will become readily apparent from the following detailed description, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.

[00041] An exemplary system for automatic retrieval of structured online documents is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

[00042] FIG. 1 is a block diagram that illustrates a computer system 100 upon which an embodiment of the invention may be implemented. Computer system 100 includes a bus 102 or other communication mechanism for communicating information, and a processor 104 coupled with bus 102 for processing information. Computer system 100 also includes a main memory 106, such as a random access memory (RAM) or other dynamic storage device, coupled to bus 102 for storing information and instructions to be executed by processor 104. Main memory 106 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 104. Computer system 100 further includes a read only memory (ROM) 108 or other static storage device coupled to bus 102 for storing static information and instructions for processor 104. A storage device 110, such as a magnetic disk or optical disk, is provided and coupled to bus 102 for storing information and instructions.

[00043] Computer system 100 may be coupled via bus 102 to a display 112, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device 114, including alphanumeric and other keys, is coupled to bus 102 for communicating information and command selections to processor 104. Another type of user input device is cursor control 116, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 104 and for controlling cursor movement on display 112. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

[00044] The invention is related to the use of computer system 100 for automatic retrieval of structured online documents. According to one embodiment of the invention, access of a remote server or computer and communication therebetween is provided by computer system 100 in response to processor 104 executing one or more sequences of one or more instructions contained in main memory 106. Such instructions may be read into main memory 106 from another machine-readable medium, such as storage device 110. Execution of the sequences of instructions contained in main memory 106 causes processor 104 to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in main memory 106. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

[00045] The term “machine-readable medium” as used herein refers to any medium that participates in providing instructions to processor 104 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as storage device 110. Volatile media include dynamic memory, such as main memory 106. Transmission media include coaxial cables, copper wire and fiber optics, including the wires that comprise bus 102. Transmission media can also take the form of acoustic or light waves, such as those generated during radio frequency (RF) and infrared (IR) data communications. Common forms of machine-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, DVD, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave as described hereinafter, or any other medium from which a computer can read.

[00046] Various forms of machine-readable media may be involved in carrying one or more sequences of one or more instructions to processor 104 for execution. For example, the instructions may initially be borne on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 100 can receive the data on the telephone line and use an infrared transmitter to convert the data to an infrared signal. An infrared detector coupled to bus 102 can receive the data carried in the infrared signal and place the data on bus 102. Bus 102 carries the data to main memory 106, from which processor 104 retrieves and executes the instructions. The instructions received by main memory 106 may optionally be stored on storage device 110 either before or after execution by processor 104.

[00047] Computer system 100 also includes a communication interface 118 coupled to bus 102. Communication interface 118 provides a two-way data communication coupling to a network link 120 that is connected to a local network 122. For example, communication interface 118 may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 118 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 118 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

[00048] Network link 120 typically provides data communication through one or more networks to other data devices. For example, network link 120 may provide a connection through local network 122 to a host computer 124 or to data equipment operated by an Internet Service Provider (ISP) 126. ISP 126 in turn provides data communication services through the worldwide packet data communication network, now commonly referred to as the “Internet” 128. Local network 122 and Internet 128 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 120 and through communication interface 118, which carry the digital data to and from computer system 100, are exemplary forms of carrier waves transporting the information.

[00049] Computer system 100 can send messages and receive data, including program code, through the network(s), network link 120, and communication interface 118. In the Internet example, a server 130 might transmit a requested code for an application program through Internet 128, ISP 126, local network 122 and communication interface 118. The received code may be executed by processor 104 as it is received, and/or stored in storage device 110, or other non-volatile storage for later execution.

[00050] The computer systems as discussed above may communicate with other systems by using a lower level protocol called TCP/IP (Transmission Control Protocol/Internet Protocol). TCP/IP allows communication between interconnected networks or computers having diverse hardware architectures and various operating systems. On an application level, the computer systems may use Hypertext Transmission Protocol (HTTP) to conduct data transfer between systems on the World Wide Web (WWW). A server is a data processing system equipped with software capable of handling HTTP requests, such as a request from a Web browser. Structured online documents, such as HTML and XML documents, are widely available on the World Wide Web.

[00051] After a computer is connected to a data network, such as the internet, users typically use a web browser, such as Microsoft Internet Explorer, to retrieve documents contained in remote servers connected to the data network. Certain online documents, such as an account summary page, may have dynamic addresses embedded in hyperlinks or buttons linking to the target documents. This is to prevent unauthorized retrieval of documents by reproducing the links and to support a notion of relatively short-lived session created for the user when he logs in to the secure web site.

[00052] However, aside from the changes in content and hyperlink addresses, the structure of online documents remains substantially the same because they are generated by server computers automatically. Server computers use a fixed page template and attach the numbers to this template from a database. Session IDs are added to the link addresses from the online session management system.

[00053] A system according to the present invention fully automates the regeneration of a command sequence that a user uses a browser to retrieve a target document starting from a starting document. The system identifies the structure of the online documents and control elements, and records the sequence of command the user uses during navigation of the documents. For example, the logical relationship of control elements, such as hyperlinks, buttons, or other clickable elements, contained in a document is identified. The control elements that were clicked by the user are identified and recorded. During regeneration of the command sequence, the system simply identifies the control elements that have the same logical relationship in the new online document, and clicks the identified control elements, or regenerates the commands represented by the control elements, to cause reproduction of the process of navigation.

[00054] When recording a navigation sequence, the relative position of a control element in a hierarchy that represents the page on which the control element was clicked is recorded. When regenerating the navigation step on a newly downloaded document, the control element that has the same position in the structure of the new document as the position recorded for the original document is located.

[00055] Several techniques are used to record position of a control element in a hierarchy representing the online document:

• • [00056] 1. Recording the path from the root element of the DOM tree to the node that represents the clicked control element.
  • [00057] 2. Recording the index of form in which Submit method was invoked.
  • [00058] 3. Recording the index of form in which control element was clicked and the position of the clicked element in a DOM tree that represents the form internals.
    Logical Tree and DOM

[00060] A logical tree representation of online documents is used in creating a navigation script according to the present invention. In the document tree, each logical unit (or element) of the document (such as paragraph, table, heading) is represented by a node. Node A is a child on node B if and only if the document fragment represented by node A is directly embedded into document fragment represented by node B. See FIG. 2.

[00061] The most popular implementation of the online document tree model for HTML and XML online documents is the Document Object Model (DOM). Document Object Model can be used to navigate the content of an online document represented as a tree of nodes.

[heading-00062] Document Object Model is implemented in browsers such as Microsoft Internet Explorer ver 4 or Netscape Navigator ver. 6. Other embodiments of this invention can use different tree models for representing online documents.

[00063] FIG. 4 shows a partial DOM tree 410 of the online document (web page) 310 from FIG. 3 (complete tree is too big to show it in one page). The root of the tree is the node 420 with “HTML” tag, it represents the whole document. The node 430 with tag “INPUT” on FIG. 4 represents HTML element “INPUT” that corresponds to the “ENTER” button 330 on FIG. 3. This button when clicked causes navigation to the next page, typically the Welcome Page.

[heading-00064] Creating the Script

[00065] A script that controls a computer system to navigate through a sequence of online documents is created in the following manner. A starting document, such as the front page of a web site or a log-in page, often has a static URL address. Therefore, a user can retrieve the starting argument by specifying the specific address and use the web browser to retrieve the corresponding document. After the starting document is retrieved, the Starting Document is displayed in the browser window. The user enters the recording phase by generating a “Record” command, such as keying a command or clicking on a “Record” button.

[00066] In the recording phase, the user simply clicks the control elements, such as buttons, hyperlinks, etc., on web pages and submits alpha-numeric form inputs as required when navigating from one page to another. Sequence and contents of navigation clicks and form submissions are recorded in a script in a manner specified below. When the user navigates to the desired Target Document, he invokes a command indicating the end of the recording.

[00067] When the user wishes to retrieve the target document for the second time, the user can send a command to the computer system requesting access to the target document. In response to the command, the computer system accesses the recorded script. Based on the contents and the sequence of the control elements and the inputs recorded in the transcript, the browser retrieves the Starting Page and regenerates all clicks and submits all inputs recorded by in the script. Thus, upon execution of the scripts, the computer system is controlled to retrieve the desired Target Document without human intervention.

[00068] The recorded navigation may include: (i) clicking hyperlinks, (ii) filling and submitting forms, (iii) entering basic authentication credentials, (iv) clicking the JavaScript-controlled document elements that cause navigation by command in client-side JavaScript.

[heading-00069] Recording the Script Algorithm

[00070] An example of the recording algorithm is shown as follows. Please note that this invention is not limited by this specification of this algorithm. The algorithm merely illustrates one example of this application. Other similar algorithms may be used to implement this invention.

[00071] This algorithm is run every time when a user clicks a control element at the time of recording:

[00072] Input: tree node for clicked-element, is a part of the current web page document tree.

[00073] Output: the script fragment that regenerates the click of clicked-element.

• • [00074] 1. Add “Click This” command to the script fragment.
  • [00075] 2. Variable e refers in the current tree node. Set e to the clicked-element.
  • [00076] 3. Do until e is not NULL
  • [00077] 4. If e. tag is equal to “BODY” or e has no parent Then Exit this loop
  • [00078] 5. Create “Go To Child Number ix” command object.
  • [00079] 6. Tree node p=parent of e
  • [00080] 7. Compute integer ix which is equal to index of node e in the node p. Index of the first child is 0, index of the second child is 1, and so on.
  • [00081] 8. Store ix in the command.
  • [00082] 9. Add command before the first command at the script.
  • [00083] 10. EndDo
    Regenerating the Script

[00085] The user can instruct the computer to run the created script or alternatively run a script loaded from a file. The system according to the present invention then executes the sequence of commands contained in the script and causes the browser to navigate from the Starting Page to the Target Page.

[00086] When script is regenerated, all commands are read sequentially from the script and executed one by one. This is the algorithm that finds the element to be clicked. It is applied to the new version of a page downloaded at the time of regenerate:

• • [00087] Input: fresh online document tree, and the script to be played.
  • [00088] Output: the node to be clicked on this page.
  • [00089] 1. Set the pointer to tree node e to the root of the online document tree.
  • [00090] 2. For every command in a script Do
  • [00091] 3. If command is “Go to Nth Child” Then
  • [00092] 4. e :=Nth child of node e
  • [00093] 5. Else If command is “Click This” Then
  • [00094] 6. Click the node e
  • [00095] 7. Endlf
  • [00096] 8. EndDo

[00097] Every time an online document is loaded, there is no guarantee that the document will be the same as the previously loaded document or that it will even be close to the previously loaded document. Many things can change even in the relatively stable documents generated from online databases: (1) Advertising banners that appear on most web pages change every time the page is loaded, and they may have complicated internal structure that is different for every ad that is displayed; (2) Certain non-advertising items may substantially change too. For instance, account balances may change on the Account Summary page, but their position of the page would remain the same.

[00098] Therefore, in order to be able to find the user-clicked control element in the changed online document, we need to rely on a document model such that an algorithm of finding the user-selected fragment on a new version of the page will be the least affected by changes in the other parts of the document. The Document Tree is the document model that was selected for use in the present invention, because it provides good degree of independence of the navigation script from the document changes.

[00099] Tree nodes and their children that are not on the path from the root to the user-clicked node may change and their change will not affect the path to the user-clicked element, so the script that locates this element will still work.

[heading-00100] Summary of Benefits

[00101] The present invention brings the following benefits to its user:

• • [00102] 1. Users do not to have to manually click through a long sequence of online documents that leads him to the desired Target Document. Additionally, users do not have to re-enter required alpha/numeric inputs (e.g., User IDs and Passwords) in order to retrieve the desired Target Document. Users only need to record the retrieval process once and then the system can regenerate this sequence automatically.
  • [00103] 2. Automatic document retrieval and command regeneration can occur in non-GUI server environment.
  • [00104] 3. The ability of the user to regenerate navigation scripts in a non-GUI, unattended mode allows a user to execute multiple transactions without having to manually perform the navigation steps required for the multiple transactions.

[00105] While this invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.