Sacha Brisset
email: sacha.brisset@hotmail.fr

Romain Rouvoy
email: romain.rouvoy@univ-lille.fr

Lionel Seinturier
email: lionel.seinturier@inria.fr

Renaud Pawlak E A Mantu

Erratum: Leveraging Flexible Tree Matching to Repair Broken Locators in Web Automation Scripts

Keywords: Element locator, Locator repair, Robotic process automation, Tree matching, Web crawling, Web testing, Locator Repair, DOM-based Locators

Web applications are constantly evolving to integrate new features and x reported bugs. Even an imperceptible change can sometimes entail signicant modications of the Document Object Model (DOM), which is the underlying model used by browsers to render all the elements included in a web application. Scripts that interact with web applications (e.g. web test scripts, crawlers, or robotic process automation) rely on this continuously evolving DOM which means they are often particularly fragile. More precisely, the major cause of breakages observed in automation scripts are

element locators, which are identiers used by automation scripts to navigate across the DOM. When the DOM evolves, these identiers tend to break, thus causing the related scripts to no longer locate the intended target elements.

For this reason, several contributions explored the idea of automatically repairing broken locators on a page. These works attempt to repair a given broken locator by scanning all elements in the new DOM to nd the most similar one. Unfortunately, this approach fails to scale when the complexity of web pages grows, leading either to long computation times or incorrect element repairs. This article, therefore, adopts a dierent perspective on this problem by introducing a new locator repair solution that leverages tree

Introduction

The implementation of automated tasks on web applications (apps), like crawling or testing, often requires software engineers to locate specic elements in the DOM (Document Object Model) of a web page. To do so, software engineers or automation/testing tools often rely on CSS (Cascading Style Sheets) or XPath selectors to query the target elements they need to interact with. Unfortunately, such statically-dened locators tend to break along time and deployments of new versions of a web application. This often results in the failure of all the associated automation scripts (including test cases) that apply to the modied web pages.

While several existing works focus on repairing tests on GUI applications, there are surprisingly very few test repair solutions targeting web interfaces [START_REF] Imtiaz | A systematic literature review of test breakage prevention and repair techniques[END_REF]. These solutions either propose to i) generate locators that are robust to changes (so-called robust locator problem), or ii) repair locators that are broken by the changes applied to the web pages (so-called locator repair problem). Unfortunately, most of the existing solutions in the literature fail to accurately relocate a broken locator, thus leaving all the related web automation scripts as broken [START_REF] Hammoudi | Why do record/replay tests of web applications break?[END_REF]. More specically, state-of-the-art solutions to the locator repair problem, WATER [START_REF] Choudhary | Water: Web application test repair[END_REF] and VISTA [START_REF] Stocco | Visual web test repair[END_REF], tend to rely on the intrinsic properties of the element whose locator needs repairing to locate its matching element on the modied page. However, this approach fails to leverage the element position and relations with the rest of the DOM, thus ignoring valuable contextual insights that may greatly help to repair the locator.

In this article, we adopt a more holistic approach to the locator repair problem: instead of focusing on the element whose locator is broken individually, we leverage a tree matching algorithm to match all elements between the two DOM versions. Intuitively, using a holistic approach to repair a broken locator should signicantly improve accuracy by reducing the search space of candidate elements in the new version of the page: for example, if the parent of the element whose locator is broken is easily identiable (e.g., the item of a menu) a tree matching algorithm will use this information to relocate the target element in the modied page with better accuracy. Additionally, if more than one locator is broken on a given web page, our approach will repair all of them consistently at once. The holistic solution we propose, named Erratum, 1 more specically leverages an ecient Similarity-based Flexible Tree Matching (SFTM) algorithm to repair all broken locators by matching all changes in a web page with high accuracy, compared to the state-of-the-art solutions. SFTM is a tree matching algorithm providing fast computation times and high accuracy when compared to other generic tree matching solutions. To do so, SFTM builds on a distinctive characteristic of DOM trees: the labels of the nodes (i.e., node attributes and tags) contain a high amount of information that can be leveraged to prune the space of possible matchings between two trees.

Evaluating solutions to both robust locator and locator repair problems requires to build a dataset of web page versionsi.e., (original page, modied page) pairs. Unfortunately, previous works assessed their contributions on hardly-reproducible benchmarks of limited sizes (never beyond a dozen of websites). In this article, we rather evaluate the robustness of our approach against the state of the art by introducing an open benchmark, which covers a wider range of changes that can be found in modern web apps. Concretely, our open benchmark considers over 83k+ locators on more than 650 web apps. It combines i) a synthetic dataset generated from random mutations applied to popular web apps and ii) a realistic dataset replaying real mutations observed in web apps from the Alexa Top 1K, 2 which ranks the most popular websites worldwide. When evaluated on both datasets, our results demonstrate that Erratum outperforms the state-of-the-art solution, namely WATER [START_REF] Choudhary | Water: Web application test repair[END_REF], both in 1 Erratum stands for "rEpaiRing bRoken locATors Using tree Matching " 2 https://www.alexa.com/topsites accuracy (67% improvement on average) and performances, when more than 3 locators require to be repaired in a web page.

Concerning the potential applications of Erratum, while we introduce and evaluate our solution within the well-studied context of locator repair, we also discuss a novel resilient architecture centered around Erratum allowing to entirely replace all locator-based interactions. This architecture intends to support much more interactive and robust script editions in the context of web testing, web crawling, and robotic process automation.

Summary. Overall, the key contributions of this article consist of:

1. proposing a solution to the locator repair problem leveraging the principles of Flexible Tree Matching (FTM), 2. implementing and integrating an ecient algorithm, named Erratum, to repair broken locators, 3. providing a novel, reproducible, large-scale benchmark dataset to evaluate both the robust locator and locator repair problems, 4. reporting on an empirical evaluation of our approach when solving the locator repair problem, 5. proposing a novel script edition architecture centered on Erratum.

Outline. The remainder of this article is organized as follows. Section 2 introduces the state-of-the-art approaches in the domain of robust locators and locator repair, before highlighting their shortcomings. Section 3 formalizes the locator problem we address in this article. Section 4 introduces our approach, Erratum, which leverages an ecient exible tree matching solution that we identied. Section 5 describes the locator benchmark we designed and implemented. Section 6 reports on the performance of our approach compared to the state-of-the-art algorithms. Finally, Section 7 presents some perspectives for this work, while Section 8 concludes.

Background & Related Work

We deliver a novel contribution to the locator repair problem, which has been initially studied in the domain of web testing. In this section, we thus introduce the required background and we describe state-of-the-art approaches to repair broken locator, and in particular the literature published in the domain of web test repair.

Introducing Web Element Locators

To detect regressions in web applications, software engineers often rely on automated web-testing solutions to make sure that end-to-end user scenarios keep exhibiting the same behavior along changes applied to the system under test. Such automated tests usually trigger interactions as sequences of actions applied on selected elements and followed by assertions on the updated state of the web page. For example, "click on button e 1 , and assert that the text block e 2 contains the text 'Form sent'". To develop such test scenarios, a software engineer can 1. manually write web test scripts to interact with the application, or 2. use record/replay tools [START_REF] Burg | Interactive record/replay for web application debugging[END_REF][START_REF] Sen | Jalangi: a selective recordreplay and dynamic analysis framework for javascript[END_REF][START_REF] Mickens | Mugshot: Deterministic capture and replay for javascript applications[END_REF] to visually record their scenarios. In both cases, the scenario requires to identify the target elements on the page [e 1 , e 2 ] in a deterministic way, which is usually achieved using XPath, a query language for selecting elements from an XML document. For example, let us consider the following HTML snippet describing a form: <form method= " post " action= " index.php "> <input type= " text " name= " username " /> <input type= " submit " value= " send " /> </form>

The following XPath snippets describe 3 dierent queries, which all result in selecting the submit button: /form/input [START_REF] Hammoudi | Why do record/replay tests of web applications break?[END_REF], /form/input[@value=" Send"], input[@type="submit"]. In the literature, such element queries or identiers are named locators [START_REF] Leotta | Reducing web test cases aging by means of robust xpath locators[END_REF].

In practice, automated tests are often subject to breakages [START_REF] Hammoudi | Why do record/replay tests of web applications break?[END_REF]. It is important to understand that a test breakage is dierent from a test failure [START_REF] Stocco | Visual web test repair[END_REF]: a test failure successfully exposes a regression of the application, while a test is said to be broken whenever it can no longer apply to the application (e.g., the test triggered a click on a button e, but e has been removed from the page). While there can be many causes to test breakage, [START_REF] Hammoudi | Why do record/replay tests of web applications break?[END_REF] reports that 74 % of web tests break because one of the included locators fails to locate an element in a web page.

Generating Web Element Locators

The fragility of locators remains the root cause of test breakage, no matter they have been automatically generated (e.g., in the case of record/replay tools), or manually written. To tackle this limitation, several studies have focused on generating more robust locators. This includes ROBULA [START_REF] Leotta | Reducing web test cases aging by means of robust xpath locators[END_REF], ROBULA+ [START_REF] Leotta | Robula+: An algorithm for generating robust xpath locators for web testing[END_REF], which are algorithms that apply successive rening transformations from a raw XPath query until it yields an xPath locator that exclusively returns the desired element. Leotta et al. [START_REF] Leotta | Meta-heuristic generation of robust xpath locators for web testing[END_REF][START_REF] Leotta | Sidereal: Statistical adaptive generation of robust locators for web testing[END_REF] also propose Sideral, a graph-based algorithm to generate xPath locators. Sideral requires to specically train on each application in order to learn what properties are most likely safe to rely on when building xPath locators. While these methods all use ancestors of a given elements as anchor to generate a locator, [START_REF] Nguyen | Generating and selecting resilient and maintainable locators for web automated testing[END_REF] uses siblings instead, arguing that they make more reliable anchors.

Another work by Yandrapally et al. leveraged contextual clues to generate locators [START_REF] Yandrapally | Robust test automation using contextual clues[END_REF]. These clues rely mostly on the content surrounding the element to locate which may be problematic in case the content changes. LED [START_REF] Bajaj | Synthesizing web element locators (t)[END_REF] uses a SAT solver to select several elements at once, but is never evaluated on dierent DOM versions. Finally, some works combine several locator generators with a voting mechanism to locate a single element with more robustness [START_REF] Leotta | Using multi-locators to increase the robustness of web test cases[END_REF][START_REF] Zheng | A method of optimizing multilocators based on machine learning[END_REF][START_REF] Long | Webrr: self-replay enhanced robust record/replay for web application testing[END_REF]. However, all these approaches, which consider a limited set of locator generators, strongly depend on the accuracy of individual algorithms to agree upon a single and relevant locator.

While automatically generating locators can speed up the denition of test cases, it becomes a keystone for visually-generated test cases based on record/replay tools. In the end, the reliability of test cases built using such a tool depends mostly on the quality of the locators it automatically generates [START_REF] Hammoudi | Why do record/replay tests of web applications break?[END_REF].

Repairing Web Element Locators

While some solutions to the robust locator problem, as presented above, aim to prevent locators from breaking, others focus on repairing broken locators. In this context, the repair tool considers a) the descriptor of the locator, b) the last version of the page on which the locator was still functional (D), c) the new version of the page on which the locator is broken (D ′ ).

Property Based. In this area, WATER [START_REF] Choudhary | Water: Web application test repair[END_REF] and COLOR [START_REF] Kirinuki | Color: correct locator recommender for broken test scripts using various clues in web application[END_REF] provide algorithm to x broken tests using intrinsic properties of the element to relocate. The process of repairing a test involves several steps: 1. running the test, 2. extracting the causes of failure and, 3. repairing the locator, if broken. The last part is particularly challenging. To relocate a locator from one version to another, WATER and COLOR scan all elements in the new version and return the most similar one to the element in the original version with regards to intrinsic properties (e.g., absolute XPath, classes, tag). Hammoudi et al. [START_REF] Hammoudi | Waterfall: An incremental approach for repairing record-replay tests of web applications[END_REF] Select elements further studied the locator repair part of WATER and found that repairing tests over ner-grained sequences of change (typically commits) contributes to improving accuracy.

Write Test

Generate

Vision Based. Using a completely dierent approach, VISTA [START_REF] Stocco | Visual web test repair[END_REF] is a recent technique that adopts computer vision to repair locators. VISTA falls within the category of computer vision-aided web tests [START_REF] Chang | Gui testing using computer vision[END_REF][START_REF] Leotta | Pesto: Automated migration of dom-based web tests towards the visual approach[END_REF][START_REF] Alegroth | Jautomate: A tool for system-and acceptance-test automation[END_REF]. However, while using computer vision succeeds in repairing most of the invisible changes, such solutions tend to fail when the content, the language, or the visual rendering of the website changes. Furthermore, visual-based solutions fail to locate dynamic elements that only appear through user interactions (e.g., a dropdown menu). Finally, J.Imtiaz et al [START_REF] Imtiaz | An automated model-based approach to repair test suites of evolving web applications[END_REF] developed a test repair solution that integrates to several dierent capture replay tools. While we focus specically on the locator repair problem, they used and evaluated a more comprehensive testrepair strategy involving the classication of the test script and detected breakages and the extension of the UML Testing Prole specications to capture more interaction details.

Locator Problem Statement

Figure 1 summarizes the steps to follow when writing or repairing a locator in a web test script. When a test breaks, the repairing process generally includes three main steps: 1. extract the cause of the breakage 2. if a locator caused the breakage, the element is rst relocated then 3. a new locator is generated/written. Beyond automated tests, this problem can also arise in more general web automation scripts covering web content crawling and Robotic Process Automation (RPA), which heavily rely on locators to automate the navigation across web applications.

In this section, we formalize the description of two locator-related problems highlighted in Figure 1, namely the robust locator (in blue) and locator repair (in green) problems for the general case of web automation scripts.

Problem Notations

We consider that a given web page can change for various reasons, such as 1. content variation, 2. page rendered for dierent regions/languages, or 3. release of the web application. No matter the cause, we distinguish D and D ′ as two versions of the same web page observed before and after a change, respectively. More specically, we dene the following similarity notations:

1. D ≈ D ′ if scripts written for D are expected to apply on D ′ ; 2. Given 2 web elements e ∈ D and e ′ ∈ D ′ , e ≈ e ′ if e and e ′ refer to semantically equivalent elements (e.g., the same menu item observed in pages D and D ′ ); 3. By extension of (2), given a set of elements E = e 1 ...e n ⊂ D and

E ′ = e ′ 1 ...e ′ n ′ ⊂ D ′ , E ≈ E ′ if n = n ′ and, for each i ∈ [1..n], e i ≈ e ′ i .
Based on the above similarity notation, we provide the following denitions: Denition 3.1. Given a page D, and a set of elements E = e 1 ...e n , the pair (loc E,D , eval) is a locator of E with regard to D if:

eval(loc E,D , D) = E (1)
where loc E,D is a descriptor of E and eval an evaluation function that returns a set of web elements from a descriptor and an evaluation context (e.g., a web page).

In the case of XPath-based locators, the descriptor loc E,D refers to an XPath query describing the elements E in the page D and eval the XPath solver. Denition 3.2. Let mut be a mutation function that transforms the page D into another page D ′ , such as

mut(D) = D ′ . mut is said to be a mutation of D if D ≈ D ′ . Denition 3.3. Given a locator L = (loc E,D , eval), L is robust to a muta- tion function mut if: eval(loc E,D , mut(D)) ≈ E (2)
Finally, we note λ(e) the label of the node e in the DOM tree. The label of a node comprises the tag, the attributes and their values and the textual content. However, in the context of Erratum, we willingly ignore the content as described in section 4.3.

Problem Statement

Given the above denitions, we can formalize the locator problem statement along with the two following research questions. RQ 3.1. Robust Locator. For any subset of elements on a given page D, how to automatically generate locators that are robust to mutations of D?

When evaluating a locator on a new page D ′ , the only available information to describe the targeted element is the descriptor loc E,D , which often remains insucient (cf. state-of-the-art techniques).

On the other hand, in the context of locator repair, the original page D from which loc E,D was built is available. Thus, using denition 3.1, this piece of information allows to locate the originally selected elements eval(loc E,D , D) = E. To the best of our knowledge, existing solutions to both robust locator and locator repair focus on the restricted case of |E| = 1.

Once the locator repair problem is solved (i.e., E ′ are correctly located), we need to generate new locators, which brings us back to the situation of the robust locator problem (cf. RQ. 3.1).

In this article, we thus present a novel approach to solve the locator repair problem.

Repairing Locators with Erratum

The previous section formalized both robust locator and locator repair problems. The approach we report in this article, Erratum, therefore matches the DOM trees of 2 versions of a web page to solve the locator repair problem. Several tree matching solutions exist in the literature, such as Tree Edit Distance (TED) [START_REF] Tai | The tree-to-tree correction problem[END_REF] or tree alignment [START_REF] Jiang | Alignment of treesan alternative to tree edit[END_REF]. This section therefore motivates and explains how Erratum leverages tree matching to repair locators, before discussing the choice of a tree matching implementation tting Erratum's requirements.

Applying Tree Matching to Locator Repair

Embedding tree matching allows Erratum to leverage the tree structure in the same way an XPath-based solution would, while oering the exibility of a more statistic-based solution. Intuitively, a tree matching algorithm should consider all easily identiable elements on a page (elements with rare tags, unique classes, ids, or other attributes) as anchors to relocate less easily identiable elements.

Figure 2 illustrates the benets of a more holistic approach using tree matching. In the example, the locator of element a (in blue) breaks because the mutations between D and D ′ entails a change in its absolute XPath (/body/div/a). Attempting to repair such a broken locator by relying on the properties of the original element alone (state-of-the-art approaches like [START_REF] Choudhary | Water: Web application test repair[END_REF][START_REF] Stocco | Visual web test repair[END_REF]) is often challenging and can easily lead to a mismatch. By using tree matching (cf. right-bottom of Figure 2), matching the parent of the element to locate (div#menu) brings instead a strong contextual clue to accurately relocate the element a 1 ' whose locator was broken [START_REF] Brisset | SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching[END_REF].

Formally, given a pair of page versions D and D ′ , we: 1. parse D and D ′ into DOM trees T and T ′ . Consequently, nodes(T ) is the set of elements in the DOM tree T ; 2. apply tree matching to T, T ′ yielding a matching M ⊂ nodes(T ) × nodes(T ′ ). If the resulting matching M is accurate, then ∀(e, e ′ ) ∈ M, e ≈ e ′ ; 3. use the resulting matching M to repair the broken locator(s). Regarding the test repair process illustrated in Figure 1, our approach thus ts in the block "relocate element" (in green) by matching the elements of D in D ′ and reporting the relocated element. Thus, once the element is relocated using tree matchingi.e. Erratum found e ′ ∈ D ′ |e ≈ e ′ we only need to generate a new locator loc e ′ ,D ′ to achieve the test repair process. This task can be performed using solutions to the robust locator problem, like ROBULA [START_REF] Leotta | Reducing web test cases aging by means of robust xpath locators[END_REF], and is therefore considered as out of the scope of this article.

Integrating a Scalable Tree Matching Algorithm

The state-of-the-art approach to match two trees is Tree Edit Distance (TED) [START_REF] Tai | The tree-to-tree correction problem[END_REF]. When comparing two trees T and T ′ , TED-based approaches rely on nding the optimal sequence of relabels, insertions and deletions that transforms T into T ′ . Unfortunately, TED might be unsuitable to match real-life web pages due to two core restrictions [START_REF] Kumar | Flexible tree matching[END_REF] e ′ are matched, the descendants of e can only match with the descendants of e ′ , and 2. the order of siblings must be preserved. Furthermore, TED is computationally expensive (O(n 3 ) for the worst-case complexity [START_REF] Bringmann | Tree edit distance cannot be computed in strongly subcubic time (unless apsp can)[END_REF]) and, more practically, our preliminary experimentation has shown that applying the state-of-the-art implementation of TED, named APTED [START_REF] Pawlik | Tree edit distance: Robust and memory-ecient[END_REF], on the YouTube page takes several minutes. We believe that, in addition to qualitative restrictions, such computation times are not acceptable when periodically repairing locators on real websites. Further studies of TED proposed to improve computation times [START_REF] Jiang | Alignment of treesan alternative to tree edit[END_REF][START_REF] Valiente | An ecient bottom-up distance between trees[END_REF][START_REF] Zhang | A constrained edit distance between unordered labeled trees[END_REF], but at the cost of even more restrictive constraints on the produced matching (e.g., the tree alignment problem [START_REF] Jiang | Alignment of treesan alternative to tree edit[END_REF] restricts the problem to transformations where insertions are performed before deletions).

To the best of our knowledge, the only contribution that provides a solution to the general (restriction-free) tree-matching problem is the Flexible Tree Matching (FTM) algorithm [START_REF] Kumar | Flexible tree matching[END_REF]. FTM models tree matching as an optimization problem: given two trees T and T ′ how to build a set of pairs (e, e ′ ) ∈ T × T ′ such that the similarity between all selected node pairs is maximal. The similarity used by FTM combines both the labels and the topology of the tree. However, as shown in [START_REF] Brisset | SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching[END_REF], the theoretical complexity of FTM is high (O(n 4 )) and the implementation of FTM was shown to take more than an hour to match a web page made of only 58 nodes, while the average number of nodes on a web page observed in our dataset is 1, 507. Consequently, we believe that such computation times make FTM unpractical in the context of locator repair.

Matching DOM Trees by Similarity

Given the limitation of FTM, Erratum integrates a Similarity-based Flexible Tree Matching (SFTM) algorithm, which is an extension of state-ofthe-art FTM to improve the computation times of FTM without any restriction on the resulting matching [START_REF] Brisset | SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching[END_REF].

In the context of Erratum, the SFTM algorithm assumes that, given a web page, several elements are easily identiable by considering their intrinsic properties. The algorithm rst assigns scores to all possible matches between nodes from the two trees based on their label and only then uses the topology of the trees to adjust these scores.

Almost all existing tree matching algorithms rely rst and foremost on the topology of the trees. Conversely, SFTM relies mostly on the labels of the trees and only makes use of topology in a second step, to ne-tune the already computed scores. Intuitively, matching two sets of labels is signicantly easier than trying to match trees, which is the reason why SFTM achieves such competitive performances. The only trade-o of this approach is that it requires the labels of the trees to be highly dierentiating (i.e., carry a lot of information). Fortunately, this is the case for the great majority of web pages.

We walk through the key steps of the SFTM algorithm we integrated in Erratum by using HTML snippets reported in Figure 3. The gure provides two versions (D and D ′ ) of a simplied HTML code sample extracted from the homepage of the famous search engine duckduckgo.com. In this example, our purpose is to relocate a 1 ∈ D with a ′ 1 ∈ D ′ . Unlike the state-of-the-art matching algorithms, SFTM rst tries to match elements in D ′ whose labels are similar to D, before using these matched elements to adjust the similarity of surrounding elements in the tree. For example, the similarity scores of the tuple (a 1 , a ′ 1 ) links will increase as their direct parents (div 3 , div ′

3 ) are matched with condence. Figure 4 summarizes the SFTM algorithm's key steps and the remainder of this section provides an overview of its integration in Erratum (cf. green box in Figure 1). The interested reader can refer to our technical report [START_REF] Brisset | SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching[END_REF] for an exhaustive description of our SFTM algorithm, whose applications go beyond the context of repairing broken locators.

Step 1: Node Similarity. Elements of DOMs D and D ′ are compared. The rst step consists in computing an initial similarity s 0 : D × D ′ → [0, 1]. For each pair of nodes (e, e ′ ) ∈ D × D ′ , s 0 (e, e ′ ) measures how similar the labels of e and e ′ are. In HTML pages, the label of a node e ∈ D that we use is the set of tokens obtained from applying a tokenizer to the HTML code describing e. This may include the type of the HTML element, its attributes, and eventually the raw content associated to this elementi.e., thus ignoring the content from the child elements.

Example 4.1. The label computed for div 1 (cf. Figure 3) includes the following tokens: {div, class, content-info__item}.

To compute s 0 , SFTM rst indexes the labels of each node of D. The idea of this step is to prune the space of possible matches by pre-matching nodes with similar labels. When indexing, to improve the accuracy of s 0 , we apply the Term Frequency-Inverse Document Frequency (TF-IDF) [START_REF] Jones | A statistical interpretation of term specicity and its application in retrieval[END_REF] formula to take into account how rare each token is. < div class =" content -info__item " > div 1 Example 4.2. Following our previous Example 3, when considering the match (div 1 , div ′ 1 ): 1. token div will yield very few similarity points, since it is included in the labels of almost all the nodes, 2. token content-info__item will increase the score signicantly, as it only appears once in both documents.

< div class =" item__title " > ... </ div > div 2 < div class =" item__subtitle " > div 3 ... <a href ="/ plugins " > Plugins </ a > a 1 </ div > </ div > (b) Updated document D ′ from D. < div class =" items -wrap " > div ′ 4 < div class =" item " > div ′ 1 < div class =" item__title " > ... </ div > div ′ 2 < div class =" item__subtitle " > div ′ 3 ... <a href ="/ extensions " > Extensions </a > a ′ 1 </ div > </ div > < div > div ′ 5 ... <a href ="/ newsletter " > Newsletter </a > a ′ 2 </ div > </ div >
In general, very common tokens bring very few information to the relevance of a given match, while they cause a signicant increase of potential matches to consider. That is why, in order to reduce the computation times, the algorithm rules out most common tokens.

Step 2: Similarity Propagation. The initial similarity s 0 only takes into account the labels of nodes. In this second step, the idea is to enrich the information contained in s 0 by leveraging the topology of the trees D and D ′ . Example 4.3. In Example 3, it is hard to choose the correct match m 1 = (a 1 , a ′ 1 ) over the incorrect one m 2 = (a 1 , a ′ 2 ) by only considering labels, since all three elements share the same set of tokens: {a, href}. In the similarity propagation step, we leverage the fact that the parents of a 1 and a ′ 1 are similar to increase the similarity between a 1 and a ′ 1 , thus preferring m 1 over m 2 .

In general, for each considered match (e, e ′ ) ∈ D × D ′ , the parents of e and e ′ gets more similarity points if e and e ′ are similar and inversely, s(e, e ′ ) is increased if the parents of e and e ′ are similar (with regard to s 0 ). We call s the nal similarity produced by this step.

Step 3: Optimization. Producing the optimal matching with regards to the computed similarity means selecting the full set of matches such that each element of D is matched with at most one element of D ′ and the sum of similarity scores of the selected matches is maximum.

In order to approximate the optimal set of matches, SFTM implements the Metropolis algorithm [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF]. The idea is to randomly walk through several possible congurations (set of matches) to converge towards the optimal one.

At the end of the optimization step, the SFTM algorithm yields a full matching M ⊂ D × D ′ comprising matches between nodes of D and D ′ . These matches can be analyzed by Erratum to locate broken locators and x them by generating new locators in the target document D ′ .

... Best and worst case scenarios. The greatest strength of Erratum's approach is to handle variations of labelse.g., renaming a class, adding an id, removing an attribute. This is because of the fuzzy nature of the rst similarity steps of SFTM: as long as two elements' label share enough rare tokens, they will match. For elements that have few information in their label (e.g., a bare div tag with no attributes) the algorithm will still be able to rely on the parents and children of the node whose label may contain more discriminative information. The worst case scenario happens when making structural changes around nodes with with labels containing few information. For example, if the content of a bare div node is moved to another div node, matching the rst div node accurately will become very challenging. More than that, since the node that was moved contains high amount of information, the matching of this node will propagate to its new parents, thus increasing the chances of mismatch in the surrounding of the moved node.

The Robust Locator Benchmark

In the context of this article, we are interested in covering the following research questions: This section, therefore, describes the benchmark we propose to assess these questions.

Evaluated Locator Repair Solutions

We compare two solutions: 1. Erratum, our approach to repair broken locators by leveraging exible tree matching, and 2. WATER, the reference implementation of a locator repair technique applied to web test scripts [START_REF] Choudhary | Water: Web application test repair[END_REF].

The original algorithm of WATER analyses a given test case, nds the origin of the test breakage, and suggests potential repairs to the developer. In the context of this article, we are interested in the most challenging part of the algorithm: the part that repairs broken locators, if needed. Given the originally located element e ∈ D, WATER attempts to nd e ′ ∈ D ′ such that e ′ ≈ e by scanning over all elements in D ′ such that tag(e ′ ) = tag(e) and selecting the elements most similar to e. The similarity between two elements e 1 , e 2 used by WATER mostly consists in computing the Levenshtein distance between the absolute XPaths of both elements (Levenshtein(XP ath(e 1 ), XP ath(e 2 ))) combined with other element properties similarity (e.g., visibility, z-index, coordinates). In our evaluation, we re-implemented this part of the WATER algorithm to compare its performance to Erratum.

We initially considered VISTA [START_REF] Stocco | Visual web test repair[END_REF] as a baseline, even though the approach they use (computer vision) is radically dierent from Erratum and WATER. However, despite our eorts, we failed to run their implementation and received no answer when trying to contact the authors.

Note that, in this evaluation, we focus on single-element locator cases of the locator repair problem (we only try to repair single-element locators).

The reasons for this decision are: 1. The state-of-the-art solutions to both repair and robust locator problems only treat this case and in particular, WATER can only repair locators locating a single element, 2. Erratum reasons on the whole trees, so locating several independent elements is done the same way as locating a group of elements.

Versioned Web Pages Datasets

In the remainder of this article, we propose two datasets to compare Erratum and WATER against potential evolutions of web pages. Given two versions of the same page D, D ′ , and a set of elements E ⊂ D, the locator repair problem consists in locating a set of elements E ′ ⊂ D ′ , such that E ′ ≈ E. To evaluate the performance of a locator repair tool, we thus need what we call a DOM versions dataset: a dataset of pairs (D, D ′ ),

such that D ≈ D ′ .
A DOM version dataset is also required to evaluate solutions to the robust locator problem. To build such a dataset, previous works on locator repair [START_REF] Leotta | Robula+: An algorithm for generating robust xpath locators for web testing[END_REF][START_REF] Leotta | Reducing web test cases aging by means of robust xpath locators[END_REF] and robust locator [START_REF] Stocco | Visual web test repair[END_REF][START_REF] Choudhary | Water: Web application test repair[END_REF][START_REF] Hammoudi | Waterfall: An incremental approach for repairing record-replay tests of web applications[END_REF] manually analyzed dierent versions of a few open source applications (like Claroline, AddressBook or Joomla). These evaluations are signicantly limited in size (never beyond a dozen of websites considered) and hard to reproduce since the exact versions of the open source applications used are often not provided or available.

In our study, we therefore introduce the rst large-scale, reproducible, real-life DOM versions dataset that can be used to assess locator repair solutions, and is composed of two parts:

1. A Mutation dataset [START_REF] Brisset | SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching[END_REF] The two datasets we provide are complementary. Since the Mutation dataset is generated by mutating elements from an original DOM D, the ground truth matching between D and its associated mutation D ′ is known to easily evaluate the solution on a very large amount of version pairs. However, since the versions are articially generated, this dataset is synthetic and, as such, might not entirely reect the actual distribution of mutations happening along a real-life website lifecycle.

Then, the Wayback dataset is composed of real website versions mined from the Wayback API: an open archive that crawls the web and saves snapshots of as many websites as possible at a rate depending on the popularity of the website. 3 In the Wayback dataset, mutations between D and D ′ are not synthetic, but as a result, the ground truth matching between D and D ′ is unknown. In our evaluation, we thus had to manually label a sample of the results obtained on this dataset, which limits the scalability of the experiment compared to the Mutation dataset.

The following sections provide more details on how both datasets were built.

Building the Mutation dataset.

We extend the technique we introduced to generate a Mutation dataset in [START_REF] Brisset | SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching[END_REF]. The mutation dataset is built by applying a random amount of random mutations to a set of original web pages: for each original DOM D, 10 mutants are created by applying mutations to D. Since the mutations applied to D to construct each mutant D ′ are known, the ground truth matching between D and D ′ is also known. Knowing the ground truth matching on the mutation dataset allows us to evaluate our locator repair solution on a very large dataset. Table 2 describes the set of DOM mutations that can be observed along evolution of a web page.

The original websites from which mutants were generated were randomly selected from the Top 1K Alexa. Figure 5 This dataset was built with an automation tool that we made available along with its source code 8. From a given list or source URLs, our tool creates a dataset of randomly mutated web pages following the above-described approach.

Buidling the Wayback dataset.

This dataset encloses a list of (D, D ′ ) DOM pairs where D and D ′ are two versions of the same page (e.g., google.com between 01/01/2013 and 01/02/2013). Two versions can be separated by dierent gaps in time. In this section, we explain how we used the Wayback API to build this dataset. The Wayback API can be used to explore past versions of websites. The two endpoints we used to build the dataset can be modeled as the following functions:

versionsExplorer ::

(url, duration) → timestamp[] versionResolver ::

(url, timestamp) → document

The versionsExplorer retrieves the list of available snapshots between two dates, while the versionResolver returns the snapshot of a given url at the requested timestamp. Using these endpoints, for each website URL considered, we:

1. retrieved the timestamps of all versions between 2010 and today using the VersionExplorer, 2. generated a list of all pairs of timestamps with one of following dierences in days (±10%): [START_REF] Mickens | Mugshot: Deterministic capture and replay for javascript applications[END_REF][START_REF] Leotta | Using multi-locators to increase the robustness of web test cases[END_REF][START_REF] Jiang | Alignment of treesan alternative to tree edit[END_REF]60,120,240, 360], 3. picked up to 1, 000 random elements from the list of timestamps pairs, 4. resolved each selected timestamp pair using the versionResolver.

Similarly to the Mutation dataset, the URLs we fed to our algorithm were taken from the Top 1K Alexa. Since both datasets are based on the same set of URLs (taken from Alexa), the distribution of the Wayback dataset is very similar to the Mutation one (cf. Figure 6).

Selecting the elements to repair.

Erratum and WATER operate in dierent ways. Erratum takes two trees (D, D ′ ) and returns a matching between each element of the trees, thus solving any possible broken locator between D and D ′ . The algorithm extracted from WATER is a more straightforward solution to the locator repair problem as formally described (cf. Section 3.2): it takes a pair of DOM versions (D, D ′ ) and an element e ∈ D as input and returns an element e ′ ∈ D ′ (or null if it fails to nd any candidate for the matching).

Consequently, in the case of the WATER algorithm, the following question arises: given a pair (D, D ′ ) taken from the DOM version dataset, which elements of D should be picked for repair? Ideally, we would try to locate every element of D in D ′ to obtain a comprehensive comparison with Erratum. Unfortunately, the computation times of WATER make it impractical to locate every single element from D in D ′ . Selecting realistic targets for locators is a non-obvious task since many elements in the DOM would not be targeted in a test script (e.g., large container blocks, invisible elements, aesthetic elements). Therefore, for each version pair, we randomly select up to 15 clickable elements from D. We focus on clickable elements as this is the most common use case for web UI testing (to trigger interactions), and WATER has specic heuristics to enhance its accuracy on links. By considering clickable elements, we 1. make sure to choose realistic elements, and 2. compare to WATER on its most typical use case.

Regarding the sample size, considering 15 elements per web page leads to selecting 34,000+ elements in both datasets. As the average number of nodes per web page in each dataset is around 1, 500, this means that there are more than 3.6M candidate locators for repair in each dataset. Therefore, the condence interval at 95 % of the measurements applied to the 34K sample of located elements is 0.5 %.

Evaluating of the Matched Elements

On the Mutation dataset, the signatures attributes are preserved after mutations (but ignored when applying either locator repair solution), thus providing the ground truth matching between the DOMs of a version pair.

For the Wayback dataset though, this information is not available. For each version pair (D, D ′ ), the evaluation of both solutions yields to a list of suggested matching (e, e ′ ERRAT U M ) and (e, e ′ W AT ER ) where e ∈ D and e ′ ERRAT U M , e ′ W AT ER ∈ D ′ . In both cases, e ′ may be null in case no matching was found. Given the above situation, the labeling process consists of determining whether the matching element of e is e ′ ERRAT U M , e ′ W AT ER , or neither. In many cases, e ′ ERRAT U M = e ′ W AT ER (consensus). We choose to focus our manual labeling eort on cases where WATER and Erratum disagree and assume that both solutions are right otherwise.

Thus, to label the disagreements between Erratum and WATER, we developed a web application (cf. Figure 7) to display the identied elements on both versions of the DOM version pair and label the matching as either correct or wrong.

When we dened the similarity equivalence between two elements (cf. Denition 3.1), we mentioned the potential subjective part of the measure. To lessen this subjective part and label the proposed matchings as objectively as possible, we systematically recommended the following guidelines:

1. Sometimes, matched elements are not visible (it happens when the visibility of some parts of the page is triggered dynamically). In this case, if elements in both versions are not visible, the locator is skipped, otherwise, the matching is considered as mismatch;

2. Sometimes, a link appears in dierent locations on the website (often sign-in links). Matching two such links from dierent locations is considered as wrong even though the two links might be assumed to have a similar semantic value. Therefore, we always consider the surrounding of the located element to judge whether the matching is correct or mismatch.

Empirical Evaluation

This section evaluates locator repair solutions along with two criteria, accuracy and performance, to answer our research questions.

Evaluation of Repair Accuracy

In this section we answer RQ. Repair accuracy on the Mutation dataset. Figure 8 summarizes the distribution of the accuracy of Erratum and WATER as a violin plot over the 3, 291 version pairs of our Mutation dataset. For each version pair (D, D ′ ), the reported accuracy ratio corresponds to the ratio of the 15 selected elements from D that are accurately located in D ′ . The gure shows There are two ways a repair solution can fail to locate an element e ∈ D in D ′ : 1. a mismatch, when the original element e ∈ D has been matched to the wrong element e ′ ∈ D ′ , or 2. a no-match, when the algorithm does not manage to locate e in D ′ . In case of failure, a no-match is always preferred to a mismatch, since a no-match alerts the developer about failure. Thus, considering the two classes of errors on the Mutation dataset, Table 3 summarizes the ratio of no-match and mismatch reported by both solutions.

In particular, the data shows a signicant advantage in favor of Erratum when it comes to reducing locator mismatches, compared to WATER. To further understand which factors inuence the accuracy of Erratum and WATER (RQ.5.2), we studied the evolution of accuracy according to three factors: 1. the type of mutations applied, 2. the size of the DOM (number of nodes) of the original page D, and 3. the mutation ratio applied to the original page D to obtain the mutant D ′ .

First, to assess the impact of the mutation type on the accuracy of Erratum and WATER, we used a constrained version of the Mutation dataset with only one mutation operation applied for each mutant. In the original Mutation dataset, a mutant D ′ of a page D is obtained by picking a random number l of random nodes n 1 , n 2 ...n l ∈ D and applying a random mutation type (cf. Table 2) to each node. In the constrained version, we use the same original pages D, but select a single random mutation operation per mutant D ′ . We then apply the mutation operation to l randomly selected nodes: n 1 , n 2 ...n l . For each original page D, the result is a list of mutants such that each mutant D ′ was obtained using only one mutation operation on a random amount of random nodes. Figure 9 depicts the sensitivity of both locator repair solutions on this alternative dataset. The vertical lines on top of each bar represent the condence interval. The gure highlights that Erratum is almost exclusively sensitive to structural mutations. In particular, the average accuracy of Erratum is not sensitive to content mutations on the page, which is expected since the algorithm ignores the content of the nodes by default. The very low sensitivity of Erratum to attributes related mutations is more surprising as attributes account for a major part of the similarity metric of the algorithm. For this reason, we believe that the mutation of attributes might have more impact when combined with structural mutations, which does not happen in the constrained Mutation dataset.

Then, regarding the impact of the size of the DOM, our analysis concludes that WATER loses accuracy when the number of nodes increases (cf. Figure 10), while Erratum exhibits a more stable performance. The Spearman correlation coecient between the error ratio of WATER and the size of the DOM is ρ = 0.41 compared to 0.28 for Erratum. Interestingly, while Erratum correlates rather strongly (ρ = 0.46) with the percentage of mutation between the two DOM versions, WATER shows almost no correlation with the same variable (ρ = 0.12). It means WATER is surprisingly not impacted by the amount mutations between the versions. The dependency to the mutation ratio of Erratum is easily explainable: for each match, Erratum indirectly relies on structural and textual similarities in the whole DOM which means mutations anywhere in the DOM could theoretically impact the scores on which Erratum relies to compute a matching. Conversely, WA-TER approach is fundamentally more local to the element to match. We believe these are key insights in understanding the limitation of WATER when compared to Erratum. For each element e ∈ D to locate, WATER searches through all same-tag elements in D ′ (the candidates) and picks the closest one to D, with respect to WATER's chosen similarity metric. We believe that the sensitivity of WATER to the number of nodes comes from the fact that the number of candidate matchings for a given element e tends to grow with the size of the DOM, which increases the complexity of the ordering-by-similarity task. Conversely, additional nodes provide more "anchor" points to Erratum, partially compensating the increase in possible combinations.

Finally, regarding the impact of the mutation ratio ( #mutations #nodes ), Figure 11 reports on how Erratum and WATER's errors evolve when increasing the number of mutations (#mutation) on the original page D. The gure contains more information than most common box plots, in particular: the stars indicate the average ratio, the horizontal orange lines, the medians whose values also appear above the boxes. As expected, both solutions lose accuracy when the mutation ratio increases, but one can still observe that Erratum demonstrates a signicant advantage over WATER, no matter the mutation ratio, and exhibiting only 20% of errors on average (against 67% for WATER) when the ratio of mutation exceeds 20% of the nodes.

Repair accuracy on the Wayback dataset. Since the Wayback dataset does not provide any ground truth matching, we had to manually label the results of the evaluation. We ran both algorithms on the same 34,421 elements. For each element e ∈ D, Erratum and WATER returned e ′ S and e ′ W ∈ D ′ ∪ ∅, respectively. In 49.0% of cases, Erratum and WATER agreed on a matching element (e ′ S = e ′ W ̸ = ∅). In 13.6% of cases, no solution found a matching element (e ′ S = e ′ W = ∅). In 37.4% of cases, Erratum and WATER disagreed on the matching element (e ′ S ̸ = e ′ W and (e ′ S , e ′ W ) ̸ = (∅, ∅)). A sample of 366 matchings out of the 14, 784 disagreements where labelled by web testing experts, which corresponds to a 5% condence interval at 95%. Table 4 reports on the results of the manual labeling (for disagreements), thus assuming that both WATER and Erratum are correct whenever they agree.

We further investigated the causes of no-match cases reported by Erratum to assess if these specic cases could be matched by experts. As part of the Wayback experiment, we thus included Erratum's no-match cases in our labelling application (cf. Figure 7) and requested the participants to eventually propose a matching element if a no-match was reported by Erratum. The result of this evaluation, summarized in Figure 12, highlights that a majority of no-match are accurately labeled as such by To assess the accuracy of Erratum on both datasets, we study the nature of the changes occurring between two versions of a given page in the Wayback dataset. The changes applied along versions of pages available in the Wayback dataset are not labeled, thus lacking a ground truth. The robust locator benchmark (cf. Section 5) assumes the input datasets as the ground truth to evaluate Erratum on the locator repair problem. Conversely, this section assumes the matching algorithm exploited by Erratumi.e., SFTMto be correct and uses it to label the mutations observed in the Wayback dataset. To do so, we estimate the number and types of mutations between each pair of web pages (D, D ′ ) by leveraging the resulting matching M = sf tm(D, D ′ ). The following table lists the considered mutation types, considering ∀e ∈ D and ∀e single element at a time, Erratum matches all elements at once. One can observe that WATER is thus faster at locating a single element than Erratum is at locating all elements. However, when the number of locators to repair grows, the computation time of WATER evolves proportionally, while the computation time of Erratum remains the same. More specically, we compare the evolution of the performance coecient (α) when increasing the number of locators to repair in a web page. Figure 17 plots these coecients for Erratum and WATER, so that we can establish that Erratum becomes more ecient than WATER as soon as there are more than 3 locators to repair in a web page.

Threats to Validity

As described in Section 5.3, the Wayback dataset does not include a ground truth (perfect matching). This is why we had to manually label a representative sample of the matchings obtained on this dataset, which might have introduced some bias. To mitigate this bias, we recommended systematic and consistent decisions to label the data (cf. Section 5.3).

All our experiments with Erratum adopt the default FTM parameters, as recommended by [START_REF] Kumar | Flexible tree matching[END_REF]. Nonetheless, a thorough parameter sensitivity study would probably result in further improving the accuracy of Erratum. Given the results we obtain on a wide diversity of web pages evolutions, we believe that this parameter tuning would only positively and marginally impact the accuracy of Erratum.

In terms of repair time, we discussed the absolute value of repair time for both solutions. However, these values highly depend on the way each tool was implemented and the machines on which the simulations were run. To limit this bias, both solutions were executed on the same Node.js runtime version deployed in the same environment to ensure a proper comparison.

Applying Erratum

We have studied how Erratum can help in solving the existing locator repair problem, which is a common problem in web automation scripts. In this section, we envision a more interactive development process made possible by Erratum.

When developing a web automation script, a developer typically opens the page under test in the browser, visually locates the element to interact with and then encodes (or generates) a locator for this element. The locator is then used in the web automation script to select the target element and interact with it. Based on the results achieved by Erratum, the perspectives for this work include a new layer of abstraction to the target selection. In this new layer, web automation scripts no longer need to explicitly locate elements on the page directly, but only locate elements using a back-end service H:

1. each web page D under automation is registered in H, 2. for each registered web page D, H exposes a visual interface allowing the developer to visually select an element e and generate a unique identier e id (e.g UUID), 3. in the web automation script, instead of using a manually encoded (or generated) XPath or CSS locator to select the target element e, the developer sends (D, e id ) to H's API, which returns an absolute XPath selecting the target element e, 4. when a web page D registered in H evolves into a new version D ′ , Erratum is automatically used to relocate all registered elements e id in D with their matching elements in D ′ , 5. whenever Erratum fails (or lacks condence) to relocate an element, the developer is notied and invited to visually relocate the broken locator. This approach diers from the test repair approach described in the original WATER article. In the test repair approach, the locator repair is triggered by the failure of one of the test scripts. Once such a test script fails, the test repair solution attempts to determine the cause of the breakage and if it is a locator, repair the locator. The approach we suggest in this section does not include the analysis of any automation script, as locators are updated whenever the page changes.

In many cases, the locator breakage occurs silently (the locator is mismatched and the consequences happen only later in the test script) [START_REF] Stocco | Visual web test repair[END_REF]. In these situations, it is harder to locate the origin of the breakage from the test script. The silent breakage problem happens because when using xPath locators to relocate e in D ′ , the xPath query either succeed or fail. There is no indication on the condence of the relocation that would help to detect a mismatch. On the opposite, Using Erratum, every individual match between two elements e and e ′ has an associated cost s(e, e ′ ) that can be used as a condence level to avoid mismatch.

In addition to the obvious gain in time that having a visual-based breakage and repair solution provides, the Erratum-based notication process described above would thus help to detect possible breakage before the scripts are even run, thus diminishing the chances for a "silent breakage" to occur.

Conclusion

In this article, we considered the situation in which the evolution of a web page causes one of its associated automation scripts to break. In the domain of automated web testing, this situation accounts for 74% of test breakages, according to past studies [START_REF] Hammoudi | Why do record/replay tests of web applications break?[END_REF]. Our analysis of the state-of-the-art approaches on this topic contributed to formalize the key steps involved in preventing or xing such a kind of test breakage.

While existing solutions to the locator repair problem treats broken locators individually, we rather propose to apply a holistic approach to the problem, by leveraging an ecient tree matching algorithm. This tree matching approach thus allows Erratum, our solution to repair all broken locators by mapping all the elements contained in an original page, to accurately relocate each of them in its new version at once. To assess Erratum, we created and shared the rst reproducible, large-scale datasets of web page locators, combining synthetic and real instances, 4 which has been incorporated in a comprehensive benchmark of Erratum and WATER, a state-of-the-art competitor. 5 Our in-depth evaluation highlights that Erratum outperforms WATER, both in accuracyby xing twice more broken than WATERand performancesby providing faster computation time than WATER when repairing more than 3 locators in a web test script.

Finally, we worked with the development team of a widely used open source test framework called Cerberus6 to integrate 7 the Erratum approach into the test creation part of the software.

RQ 3 . 2 .

 32 Locator Repair. Given two pages D, D ′ , such that D ≈ D ′ and a set of elements E ∈ D, how to locate the elements E ′ ≈ E in D ′ ?

  (a) Original document D.

Figure 3 :

 3 Figure 3: Two versions of an HTML snippet extracted from the homepage of duckduckgo.com.

Figure 4 :

 4 Figure 4: Key steps followed by our Similarity-based Flexible Tree Matching (SFTM) algorithm.

RQ 5 . 1 .

 51 How does Erratum perform in solving the locator repair problem (cf. RQ. 3.2) when compared to state-of-the-art solutions? RQ 5.2. What are the factors inuencing the accuracy of WATER and Erratum? RQ 5.3. How quickly can Erratum repair broken locators when compared to state-of-the-art solutions?

  depicts the distribution of DOM sizes in this synthetic dataset.

Figure 5 :

 5 Figure 5: Distribution of DOM sizes (in number of nodes) in the Mutation dataset.

Figure

  Figure Distribution of DOM sizes (in number of nodes) in the Wayback dataset.

Figure 7 :

 7 Figure 7: Labeling a given element matched by Erratum on two versions of the Linkedin homepage. The screenshot comes from the visual matching application we created to manually label disagreements between Erratum & WATER.

5 . 1 :

 51 How does Erratum perform in solving the locator repair problem (RQ. 3.2) when compared to state-of-the-art

Figure 8 :

 8 Figure 8: Accuracy distribution of Erratum and WATER on the Mutation dataset.

Figure 9 :

 9 Figure 9: Error percentage according to the mutation type.

Figure 10 :

 10 Figure 10: Errors rate evolution according to DOM size.

Figure 16 :

 16 Figure 16: Repair time evolution according to DOM size.

Figure 17 :

 17 Figure 17: Performances of Erratum and WATER.

Table 1 :

 1 Then, for each pair (D, D ′ ) in the dataset, our experiments consist of selecting a set of elements to locate in D and in comparing both Erratum and WATER trying to nd the corresponding element on D ′ . Description of the Mutation & Wayback datasets.

	Dataset	Mutation Wayback
	# Unique URLs	650	64
	# Version pairs	3,291	2,314
	# Located elements	49,305	34,421

generated by applying random mutations to a given set of web pages (see Section 5.2.1), 2. A Wayback dataset collects past versions of popular websites from the Wayback API (see Section 5.2.2). Table 1 describes both datasets in terms of:

1. # Unique URLs: the number of unique URLs among the total of version pairs in the dataset. The duplication is due to the fact that there can be several mutations or successive versions of the same web page. In the case of the Wayback dataset, more popular websites are more represented (see Section 5.2.2); 2. # Version pairs: the number of considered pairs of web pages (D, D ′ ), 3. # Located elements: the number of elements e ∈ D that any solution should locate in D ′ .

Table 2 :

 2 Mutations applied in the Mutation dataset[START_REF] Brisset | SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching[END_REF].

	Type Mutation operators
	Structure remove, duplicate, wrap, unwrap, swap
	Attribute remove, remove words
	Content replace with random text, change letters,
	remove, remove words

Table 3 :

 3 Errors distribution of Erratum and WATER on the Mutation dataset.

	Erratum	WATER
	correct 42, 876 (87.0%) 20, 740 (42.1%)
	mismatch 4, 420 (9.0%) 26, 820 (54.4%)
	no-match 2, 009 (4.0%) 1, 745 (3.5%)
	Total: 49, 305 (100%) 49, 305 (100%)

  Erratum,

					No-match analysis
					Confirmed Failed
	Correct	78%	13%	No-match	68%
		9%
				Mismatch
					32%
	Figure 12: Analysis of matches labeled as no-match by Erratum.

and the distribution of real-life mutations.

Table 5 :

 5 Accuracy summary across datasets.

	Mutation Wayback Erratum 87.0% 78.3 ± 5% WATER 42.1% 51.9 ± 5%
	6.2. Mutations in the Wayback Dataset

https://archive.org/help/wayback_api.php

Dataset available from https://zenodo.org/record/3800130#.XrQb02gzY20

Benchmark available from https://zenodo.org/record/3817617#.XrWdqGgzaoQ

https://cerberus-testing.com/

https://github.com/cerberustesting/cerberus-source/commit/0a70d4cc0d70a797901652fd2b97d501bb7fa511

since the participants could not propose a matching element in the target web page. For the few cases where the participants proposed a matching element, we observed that the structure of the DOM tree where subject to many mutations, thus misleading Erratum as already observed in Figure 9.

Comparison of repair accuracy. Interestingly, as shown in Table 5, the accuracy of Erratum on the Wayback dataset (78.3 % ± 5 %) is 8.7% inferior to the accuracy obtained on the Mutation dataset (87.0%), while the accuracy of the WATER algorithm is better on the Wayback dataset (51.9 % ± 5 %) than on the Mutation dataset (42.1 %) by 9.8 %. We believe the dierence observed between the two datasets is because real-life mutations might not be uniformly distributed. In particular, regarding our sensitivity analysis with regards to types of tree mutations (cf. Figure 9), one can guess that real-life websites are more subject to content and attribute-related mutations than structure-based mutations (cf. (a) one of the versions can be an error page or a redirection page, (b) the website may shown "in construction" or may have closed between the two snapshots. For this reason, we apply two heuristics to prepare the dataset by removing all the pairs where:

1. one the two versions has less than 30 nodes, reecting one of the above inconsistencies. For example, even a minimalist web page, like Google, contains more than 250 nodes; 2. the absolute ratio of sizes between the two versions exceeds 40% which selects approximately 90% of the dataset (see Figure 13). When this ratio is large, comparing the two pages is likely to be conceptually irrelevant. While the initial Wayback dataset contains 19, 161 pairs of web pages, the application of the above rules leads to a consolidated dataset of 8, 641 pairs. Figure 13 reports on the distribution of ratios of web page versions in the consolidated Wayback dataset. Mutation Frequency. Figure 14 further analyzes the above dataset by reporting on the ratio of mutations by category occurring between two versions of a web page.

As expected, the mutation ratio increases with the gap between the versions. Most importantly, the average mutation ratio in the Wayback dataset is 60%, i.e. in average, 60% of the nodes have mutated between two versions D and D ′ from the Wayback dataset. This mutation ratio is signicantly higher than the average amount of mutations in the Mutation dataset: 20%. This dierence is probably an important factor justifying the dierences of accuracy measured on both datasets. Comparing versions with large gaps is practical because it ensures there will be dierences between the versions. In addition, it provides interesting insights about the frequency of changes on popular web pages. However, in the context of web testing, the mutation ratio between two consecutive versions is unlikely to reach 60%, in particular when adopting test-driven developments.

Mutation Labels. Figure 15 further describes the distribution of mutation labels in the Wayback dataset. The gure highlights that relabel is the most common mutation, while move is quite rare. This result can be explained by the following observations: 1. when a subtree is moved, only one move is accounted even if the visual change may appear as important, and 2. the SFTM algorithm is particularly robust to relabels, which could also be a factor explaining the observed ratio.

Repair Time Evaluation

In Figure 16, we compare the computation times of Erratum and WA-TER. The results have been obtained by running both algorithms on the same server containing 252 GB of RAM and an Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60 GHz.

Erratum works dierently than WATER: while WATER matches one