Crawling AJAX by Inferring User Interface State Changes (2008) (тематика web-краулеров), страница 2

As can be seen, a div element (line 3) can have anonclick event attached to it so that it becomes a clickable element capable of changing the internal DOM stateof the application when clicked. The necessary event handlers can also be programmatically registered in A JAX. ThejQuery3 code responsible (lines 9–11) for attaching the required functionality to the onClick event handlers using theclass attribute of the elements can also be seen.Finding these clickables at run-time is another nontrivial task for a crawler. Traditional crawlers as used bysearch engines will simply ignore all the elements (not having a proper href attribute) except the one in line 4, sincethey rely on JavaScript only.3 A Method for Crawling A JAXThe challenges discussed in the previous section willmake it clear that crawling A JAX based on static analysisof, e.g., the HTML and JavaScript code is not feasible.

Instead, we rely on a dynamic approach, in which we actuallyexercise clicks on all relevant elements in the DOM. Fromthese clicks, we reconstruct a state-flow graph, which tellsus in which states the user interface can be. Subsequently,we use these states to generate static, indexable, pages.An overview of our approach is visualized in Figure 3.As can be seen, the architecture can be divided in two parts:(1) inferring the state machine, and (2) using the state machine to generate indexable pages.In this section, we first summarize our state and stateflow graph definition, followed by a discussion of the mostimportant steps in our approach.3.1 User Interface StatesIn traditional multi-page web applications, each state isrepresented by a URL and the corresponding web page.

InA JAX however, it is the internal structure change of theDOM tree on the (single-page) user interface that represents a state change. Therefore, to adopt a generic approach3 http://jquery.comTUD-SERG-2008-022S_4<onmouseover, xpath://SPAN[2]/A[2]>Index2.5 Elements Changing the Internal State<onclick, id:c_3>S_1<onmouseover, id:c_9>S_2S_3<onclick, xpath://DIV[3]/IMG[1]>Figure 2.

The state-flow graph visualization.for all A JAX sites, we define a state change as a changeon the DOM tree caused either by server-side state changespropagated to the client, or client-side events handled by theA JAX engine.3.2 The State-flow GraphThe user interface state changes in A JAX can be modeledby recording the paths (events) to these DOM changes to beable to navigate the different states. For that purpose wedefine a state-flow graph as follows:Definition 1 A state-flow graph for an A JAX site A is a 3tuple < r, V , E > where:1. r is the root node (called Index) representing the initialstate after A has been fully loaded into the browser.2. V is a set of vertices representing the states. Eachv ∈ V represents a run-time state in A.3. E is a set of edges between vertices.

Each (v1 , v2 ) ∈ Erepresents a clickable c connecting two states if andonly if state v2 is reached by executing c in state v1 .Our state-flow graph is similar to the event-flow graph[18], but different in that in the former vertices are states,where as in the latter vertices are events.As an example of a state-flow graph, Figure 2 depicts thevisualization of the state-flow graph of a simple A JAX site.It illustrates how from the start page three different statescan be reached. The edges between states are labeled withan identification (either via its ID-attribute or via an XPathexpression) of the element to be clicked in order to reachthe given state.

Thus, clicking on the //DIV[1]/SPAN[4]element in the Index state leads to the S 1 state, from whichtwo states are reachable namely S 3 and S 4.3.3 Inferring the State MachineThe state-flow graph is created incrementally. Initially,it only contains the root state and new states are created andadded as the application is crawled and state changes areanalyzed.The following components, also shown in Figure 3 participate in the construction of the state flow graph:3SERGMesbah et. al.

– Crawling AJAX by Inferring User Interface State ChangesRobotUIclickgenerate clickBrowserupdate eventDOMeventCrawljax ControllerupdategeneratesitemapupdateAjaxEnginegeneratemirrorInferring the State MachineStateMachineGenerating Indexable PagesLegendSitemapGeneratorMirror siteGeneratorlinkupLinkertransformSitemapXMLMulti-pageHTMLAccessControl flowDOM to HTMLTransformerEvent invocationData componentProcessing componentStatic fileOutputFigure 3.

Processing view of the crawling architecture.• Embedded Browser: Our approach is based on an embedded browser interface (with different implementations: IE, Mozilla) capable of executing JavaScript andthe supporting technologies required by A JAX (e.g.,CSS, DOM, XMLHttpRequest).• Robot: A robot is used to simulate user input (e.g.,click, mouseOver, text input) on the embeddedbrowser.• Controller: The controller has access to the embedded browser’s DOM and analyzes and detects statechanges. It also controls the Robot’s actions and isresponsible for updating the State Machine when relevant changes occur on the DOM. After the crawlingprocess is over, the controller also calls the Sitemapand Mirror site generator processes.• Finite State Machine: The finite state machine is a datacomponent maintaining the state-flow graph, as well asa pointer to the current state.The algorithm used by these components to actually infer the state machine is shown in Algorithm 1.

The startprocedure (lines 1-8) takes care of initializing the variouscomponents and processes involved. The actual, recursive,crawling procedure starts at line 10: the main steps are explained below.43.4 Detecting ClickablesThere is no direct way of obtaining all clickable elementsin a DOM-tree, due to the reasons explained in Section 2.Therefore, our algorithm makes use of a set of candidateelements, which are all exposed to an event type (e.g., click,mouseOver). We use the click event type to present ouralgorithm, note, however, that other event types can be usedjust as well to analyze the effects on the DOM in the samemanner.We distinguish three ways of obtaining the candidate elements:• In a Full Auto Scan mode, the candidate clickablesare labeled as such based on their HTML tag elementname.

For example, all elements with a tag div, a,span, input are considered as candidate clickable.This is the mode that is displayed in Algorithm 1.• In the annotation mode, we allow the HTML elementsto have an attribute crawljax="true". This givesusers the opportunity to explicitly mark certain elements as to be crawled, or elements to be excludedfrom the process by setting the attribute to false. Notethat this mode requires access to the source code of theapplication for applying the annotations.• In the configured mode, we allow a user to specify bymeans of a domain-specific language which elementsTUD-SERG-2008-022SERGMesbah et. al.

– Crawling AJAX by Inferring User Interface State ChangesAlgorithm 1 Full Auto Scan1: procedure S TART (url, Set tags)2: browser ← initEmbeddedBrowser(url)3: robot ← initRobot()4: sm ← initStateMachine()5: crawl(null)6: linkupAndSaveAsHTML(sm)7: generateSitemap(sm)8: end procedure9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:24:25:26:27:28:29:30:31:32:33:34:35:36:procedure C RAWL (State ps)cs ← sm.getCurrentState()∆update ← diff(ps, cs)Set C ← getCandidateClickables(∆update, tags)for c ∈ C dorobot.fireEvent(c, ‘click’)dom ← browser.getDom()if distance(cs.getDom(), dom) > τ thenxe ← getXpathExpr(c)ns ← State(c, xe, dom)sm.addState(ns)sm.addEdge(cs, ns, c, ‘click’)sm.changeState(ns)crawl(cs)sm.changeState(cs)if browser.history.canBack thenbrowser.history.goBack()elsebrowser.reload()List E ← sm.getShortestPathTo(cs)for e ∈ E dorobot.fireEvent(e.getXpathExpr(), ‘click’)end forend ifend ifend forend procedureshould be clicked (explained in more detail in Section 3.8).

This allows the most precise control overthe actual elements to be clicked.Note that, if desirable, these modes can be combined. After the candidate elements have been found, the algorithmproceeds to determine whether these elements are indeedclickable. For each candidate element, the crawler instructsthe robot to execute a click (line 15) on the element (or otherevent types, e.g., mouseOver), in the browser.3.5 Creating StatesAfter firing an event on a candidate clickable, the algorithm compares the resulting DOM tree with the DOM treeTUD-SERG-2008-022as it was just before the event fired, in order to determinewhether the event results in a state change.For this purpose the edit distance between two DOMtrees is calculated (line 17) using the Levenshtein [15]method.

A similarity threshold τ is used under which twoDOM trees are considered clones. This threshold (0.0−1.0)can be defined by the developer. A threshold of 0 means twoDOM states are seen as clones if they are exactly the samein terms of structure and content. Any change is, therefore,seen as a state change.If a change is detected according to our similarity metric,we create (line 19) a new state and add it to the state-flowgraph of the state machine (line 20).

In order to recognizean already met state, we compute a hashcode for each DOMstate and which we use to compare every new state to thelist of already visited states on the state-flow graph. Thus,in line 19 if we have a state containing the particular DOMtree already, that state is returned, otherwise a new state iscreated.Furthermore, a new edge is created on the graph (line 21)between the state before the event and the current state. Theelement on which the event was fired is also added as partof the new edge.