Francis Dolière

Nataliia Somé

Tamara Bielova
email: nataliia.bielova@inria.fr

Rezk

Control What You Include! Server-Side Protection against Third Party Web Tracking

Keywords:

 contain third party content that is tracking its users across the web. Website developers often need to include third party content in order to provide basic functionality. However, when a developer includes a third party content, she cannot know whether the third party contains tracking mechanisms. If a website developer wants to protect her users from being tracked, the only solution is to exclude any third-party content, thus trading functionality for privacy. We describe and implement a privacypreserving web architecture that gives website developers a control over third party tracking: developers are able to include functionally useful third party content, the same time ensuring that the end users are not tracked by the third parties.

Introduction

Third party tracking is the practice by which third parties recognize users accross different websites as they browse the web. In recent years, tracking technologies have been extensively studied and measured [START_REF] Eckersley | How Unique Is Your Web Browser?[END_REF][START_REF] Englehardt | Online tracking: A 1-million-site measurement and analysis[END_REF][START_REF] Krishnamurthy | Privacy diffusion on the web: a longitudinal perspective[END_REF][START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF][START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF][START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF] -researchers have found that third parties embedded in websites use numerous technologies, such as third-party cookies, HTML5 local storage, browser cache and device fingerprinting that allow the third party to recognize users across websites [START_REF] Soltani | Flash Cookies and Privacy[END_REF] and build browsing history profiles. Researchers found that more than 90% of Alexa top 500 websites [START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF] contain third party web tracking content, while some sites include as much as 34 distinct third party content [START_REF] Lerner | Internet jones and the raiders of the lost trackers: An archaeological study of web tracking from 1996 to 2016[END_REF].

But why do website developers include so many third party content (that may track their users)? Though some third party content, such as images and CSS [START_REF]Cascading Style Sheets[END_REF] files can be copied to the main (first-party) site, such an approach has a number of disadvantages for other kinds of content. Advertisement is the base of the economic model in the web -without advertisements many website providers will not be able to financially support their website maintenance. Third party JavaScript libraries offer extra functionality: though copies of such libraries can be stored on the main first party site, this solution will sacrifice maintenance of these libraries when new versions are released. The developer would need to manually check the new versions. Web mashups, as for example applications that use hotel searching together with maps, are actually based on reusing thirdparty content, as well as maps, and would not be able to provide their basic functionality without including the third-party content. Including JavaScript libraries, content for mashups or advertisements means that the web developers cannot provide to the users the guarantee of non-tracking.

Except for ethical decision not to track users, from May 2018 the website owners will have a legal obligation as well. The ePrivacy directive (also know as 'cookie law') will be updated to the regulation, and will make website owners liable for third party tracking that takes place in their websites. This regulation will be applied to all the services that are delivered to the natural persons located in the European Union. This regulation will apply high penalties for any violation. Hence, privacy compliance will be of high interest to all website owners and developers, and today there is no automatic tool that can help to control third party tracking.To keep a promise of non-tracking, the only solution today is to exclude any third-party content 1 , thus trading functionality for privacy.

In this paper, we present a new web application architecture that allows web developers to gain control over certain types of third party content. Our solution is based on the automatic rewriting of the web application in such a way that the third party requests are redirected to a trusted web server, with a different domain than the main site. This trusted web server may be either controlled by a trusted party, or by a main site owner -it is enough that the trusted web server has a different domain. A trusted server is needed so that the user's browser will treat all redirected requests as third party requests, like in the original web application. The trusted server automatically eliminates third-party tracking cookies and other technologies.

In summary our contributions are: -A classification of third party content that can and cannot be controlled by the website developer. -An analysis of third party tracking capabilities -we analyze two mechanisms: recognition of a web user, and identification of the website she is visiting 2 . -A new architecture that allows to include third party content in web applications and eliminate stateful tracking. -An implementation of our architecture, demonstrating its effectiveness at preventing stateful third party tracking in several websites.

Background and Motivation

Third party web tracking is the ability of a third party to re-identify users as they browse the web and record their browsing history [START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF]. Tracking is often done with the purpose of web analytics, targeted advertisement, or other forms of personalization. The more a third party is prevalent among the websites a user interacts with, the more precise is the browsing history collected by the tracker.

Tracking has often been conceived as the ability of a third party to recognize the web user. However, for successful tracking, each user request should contain two components:

User recognition is the information that allows tracker to recognize the user; Website identification is the website which the user is visiting.

For example, when a user visits news.com, the browser may make additional requests to facebook.com. As a result, Facebook learns about the user's visit to news.com. Figure 1 shows a hypothetical example of such tracking where facebook.com is the third party.

Consider that a third party server, such as facebook.com hosts different content, and some of them are useful for the website developers. The web developer of another website, say mysite.com, would like to include such functional content from Facebook, such as Facebook "Like" button, an image, or a useful JavaScript library, but the developer does not want its users to be tracked by Facebook. If the web developer simply includes third party Facebook content in his application, all its users are likely to be tracked by cookie-based tracking. Notice that each request to facebook.com also contains an HTTP Referrer header, automatically attached by the browser. This header contains the website URL that the user is visiting, which allows Facebook to build user's browsing history profile.

The example demonstrates cookie-based tracking, which is extremely common [START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF]. Other types of third party tracking, that use client-side storage mechanisms, such as HTML5 LocalStorage, or cache, and device fingerprinting that do not require any storage capabilities, are also becoming more and more popular [START_REF] Englehardt | Online tracking: A 1-million-site measurement and analysis[END_REF].

Web Developer Perspective. A web developer may include third party content in her webpages, either because this content intentionally tracks users (for example, for targeted advertising), or because this content is important for the functioning of the web application. We therefore distinguish two kinds of third party content from a web developer perspective: tracking and functional. Tracking content is intentionally embedded by website owner for tracking purposes. Functional content is embedded in a webpage for other purposes than tracking: for example, JavaScript libraries that provide additional functionality, such as jQuery, or other components, such as maps. In this work, we focus on functional content and investigate the following questions:

-What kind of third party content can be controlled from a server-side (web developer) perspective? -How to eliminate the two components of tracking (user recognition and website identification) from functional third party content that websites embed?

Browsing Context

Browsers implement different specifications to securely fetch and aggregate third party content. One widely used approach is the Same Origin Policy (SOP) [START_REF]Same Origin Policy[END_REF], a security mechanism designed for developers to isolate legacy content from potentially untrusted third party content. An origin is defined as scheme, host and port number, of the URL [21] of the third party content. When a browser renders a webpage delivered by a first party, the page is placed within a browsing context [START_REF]Browsing Contexts[END_REF]. A browsing context represents an instance of the browser in which a document such as a webpage is displayed to a user, for instance browser tabs, and popup windows. Each browsing context contains 1) a copy of the browser properties (such as browser name, version, device screen etc), stored in a specific object; 2) other objects that depend on the origin of the document according to SOP. For instance, the object document.cookie gives the cookies related to the domain and path of the current context.

In-Context and Cross-Context Content. Certain types of content embedded in a webpage, such as images, links, and scripts, are associated with the context of the webpage, and we call them in-context content. Other types of content, such as <iframe>, <embed>, and <object> tags are associated with their own browsing context, and we call them cross-context content. Usually, cross-context content, such as <iframe> elements, cannot be visually distinguished from the webpage in which they are embedded, however they are as autonomous as other browsing contexts, such as tabs or windows. Table 1 shows different third party content and their execution contexts. The Same Origin Policy manages interactions between different browsing contexts. In particular, it prevents in-context scripts from interacting with cross-context iframes in case their origins are different. To communicate, they may use inter-frame communication APIs such as postMessage [START_REF]PostMessage -Cross-Origin Iframe Secure Communication[END_REF].

Third Party Tracking

In this work, we consider only stateful tracking technologies -they require an identifier to be stored client-side. The most common storage mechanism is cookies, but others, such as HTML5 LocalStorage and browser cache can also be used for stateful tracking. Figure 2 presents the well-known stateful tracking mechanisms. We distinguish two components necessary for successful tracking: user recognition and website identification. For each component, we describe the capabilities of in-context and cross-context. We also distinguish passive tracking (through HTTP headers) and active tracking (through JavaScript or plugin script). In-Context Tracking. In-context third party content is associated with the browsing context of the webpage that embeds it (see Table 1).

Passively, such content may use HTTP headers to recognize a user and identify the visited website. When a webpage is rendered, the browser sends a request to fetch all third party content embedded in that page. The responses from the third party, along with the requested content, may contain HTTP headers that are used for tracking. For example, the Set-cookie HTTP header tells the browser to save third party cookies, that will be later on automatically attached to every request to that third party in the Cookie header. Etag HTTP header and other cache mechanisms like Last-Modified and Cache-Control HTTP headers may also be used to store user identifiers [START_REF] Soltani | Flash Cookies and Privacy[END_REF] in a browser. To identify the visited website, a third party can either check the Referer HTTP header, automatically attached by the browser, or an Origin header 3 .

Actively, in-context third party content cannot use browser storage mechanisms, such as cookies or HTML5 Local Storage associated to the third party because of the limitations imposed by the SOP (see Section 2.1). For example, if a third party script from third.com uses document.cookie API, it will read the cookies of the main website, but not those of third.com. This allows tracking within the main website but does not allow tracking cross-sites [START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF]. For website identification, third party active content, such as scripts, can use several APIs, for example document.location.

Cross-Context Tracking. Cross-context content, such as iframe, is associated with the browsing context of the third party that provided this content.

Passively, the browser may transmit HTTP headers used for user recognition and website identification, just like in the case of in-context content. Every thirdparty request for cross-context content will contain the URL of the embedding webpage in its Referer header.

Requests to fetch third party content further embedded inside a cross-context (such as iframe) will carry, not the URL of the embedding webpage, but that of the iframe in their Referer or Origin headers (in the case of CORS requests). This prevents them from passively identifying the embedding webpage.

Actively, cross-context third party content can use a number of APIs to store user identifiers in the browser. These APIs include cookies (document.cookie), HTML5 LocalStorage (document.localStorage), IndexedDB, and Flash Local Stored Objects (LSOs). For website identification, document.referrer API can be used -it returns the value of the HTTP Referrer header transmitted in the request to the cross-context third party.

Combining In-Context and Cross-Context Tracking. Imagine a third party script from third.com embedded in a webpage -according to the context and to the SOP, it is in-context. If the same webpage embeds a third party iframe from third.com (cross-context), then because of SOP, such script and iframe cannot interact directly. However, the can still communicate through inter-frame communication APIs such as postMessage [START_REF]PostMessage -Cross-Origin Iframe Secure Communication[END_REF].

On one hand, the in-context script can easily identify the website using APIs such as document.location. On the other hand, the cross-context iframe can easily recognize the user by calling document.cookie. Therefore, if the iframe and the script are allowed to communicate, they can exchange those partial tracking information to fully track the user.

For example, a social widget, such as Facebook "Like" button, or Google "+1" button, may be included in webpages as a script. When the social widget script is executed on the client-side, it loads additional scripts, and new browsing contexts (iframes) allowing the third party to benefit from both in-context and cross-context capabilities to track users.

Privacy-preserving Web Architecture

For third party tracking to be effective, two capabilities are needed: 1) the tracker should be able to identify the website in which it is embedded, and 2) recognize the user interacting with the website. Disabling only one of these two capabilities for a given third party already prevents tracking. In order to mitigate stateful tracking (see Section 2), we make the following design choices:

1. Preventing only user recognition for in-context. As show in Table 2, in-context content cannot perform any active user recognition. We are left with passive user recognition and (active and passive) website identification. Preventing passive user recognition for such content (images, scripts, forms) is possible by removing HTTP headers such as Cookie, Set-cookie, ETag that are sent along with requests/responses to fetch those content. Note that it is particularly difficult to prevent active website identification because trying to alter or redefine document.location or window.location APIs, will cause the main page to reload. Therefore, in-context active content (scripts) can still perform active website identification. Nonetheless, since we remove their user recognition capability, tracking is therefore prevented for in-context content. 2. Preventing only website identification for cross-context. We prevent passive website identification by instructing the browser not to send the HTTP Referer header along with requests to fetch a cross-context content. Therefore, when the cross-context content gets loaded, the tracker is unable to identify the website in which it is embedded in. Indeed, executing document.referrer returns an empty string instead of the URL of the embedding page.

Because of the limitations of the SOP, a website owner has no control over cross-context third party content, such as iframes. Therefore, active and passive user recognition can still happen in third party cross-context. We discuss other possibilities to block some active user recognition APIs in Section 4.1. Nonetheless, since website identification is not possible, tracking is therefore prevented for cross-context third party content. 3. Prevent communication between in-context and cross-context content. Our architecture proposes a way to block such communications that can be done by postMessage API. We discuss the limitations of this approach in Section 4.1.

To help web developers keep their promises of non-tracking and still include third-party content in their web applications, we propose a new web application architecture. This architecture allows web developers to 1) automatically rewrite the URLs of all in-context third party content embedded in a web application, 2) redirect those requests to a trusted third party server which 3) remove/disable known stateful tracking mechanisms (see Section 2) for such content; 4) rewrite and redirect cross-context requests to the trusted third party so as to prevent website identification and communication with in-context scripts.

Figure 3 provides an overview of our web application architecture. It introduces two new components fully controlled by the website owner.

Rewrite Server (Section 3.1) acts like a reverse proxy [START_REF]Reverse Proxy[END_REF] for the original web server. It rewrites the original web pages in such a way that all the requests to fetch all the third party content that they embed are redirected through the Middle Party Server before reaching the intended third party server.

Middle Party Server (Section 3.2) is at the core of our solution since it intercepts all browser third party requests, removes tracking, then forwards them to the intended third parties. From every response from a third party, the server removes tracking information and forwards the response back to the browser. For

Rewrite Server

The goal of the Rewrite Server is to rewrite the original content of the requested webpages in such a way that all third party requests will be redirected to the Middle Party Server. It consists of three main components: static HTML rewriter for HTML pages, static CSS rewriter and JavaScript injection component. Into each webpage, we load a JavaScript code that insures that all dynamically generated third party content are redirected to the Middle Party Server as well.

HTML and CSS Rewriter rewrites the URLs of static third party content embedded in original web pages and CSS files in order to redirect them to the Middle Party Server. For example, the URL of a third-party script source http://third.com/script.js is written so that it is instead fetched through the Middle Party Server: http://middle.com/?src=http://third.com/script.js. The HTML Rewriter component is implemented using the Jsdom HTML parser [START_REF]HTML Parser for Node[END_REF], and CSS Rewriter, using the CSS parser [START_REF]CSS Parser for Node[END_REF] module for Node.js.

JavaScript Injection. The Rewrite Server also injects a script in all original webpages after they are rewritten. This script controls APIs used to dynamically inject content inside a webpage once the webpage is rendered in a browser. It is available at https://webstats.inria.fr/sstp/dynamic.js. Table 2 shows APIs that can be used to dynamically inject third party content within a webpage. They are controlled using the injected script.

A Content Security Policy (CSP) [START_REF] West | Content Security Policy Level[END_REF] is injected in the response header of each webpage in order to prevent third parties from bypassing the rewriting

Middle Party

The main goal of the Middle Party is to proxy the requests and responses between browsers and third parties in order to remove tracking information exchanged between them. It functions differently for in-context and cross-context content.

In-Context content are scripts, images, etc. (see Table 1). Since a third party script from http://third.com/script.js is rewritten by the Rewrite Server to http://middle.com/?src=http://third.com/script.js, it is fetched through the Middle Party Server. This hides the third party destination from the browser, and therefore prevents it from attaching third party HTTP cookies to such requests. Because the browser will still attach some tracking information to the requests, then when the middle party receives a request URL from the browser, it takes the following steps. Remove Tracking from request that are set by the browser as HTTP headers. Among those headers are Etag, If-Modified-Since, Cache-Control, Referer. Next, it makes a request to the third party in order to get the content of the script http://third.com/script.js. Remove Tracking from response returned by the third party. The headers that the third party may send are Set-Cookie, Etag, Last-Modified, Cache-Control. CSS Rewriter rewrites the response if the content is a CSS file, in order to also redirect to the Middle Party Server any third party content that they may embed. Finally, the response is returned back to the browser.

Cross-context content are iframes, links, popups, etc. (see Table 1). The Middle Party Server prevents website identification for cross-context content and communication with in-context scripts. This is done by loading cross-context content from another cross-context controlled by the Middle Party Server as illustrated by Figure 4.

For instance, a third party iframe from http://third.com/page.html is rewritten to http:// middle.com/?emb=http://third.com/page.html. When the Middle Party Server receives such a request URL from the browser, it takes the following actions: URL Rewriting. Instead of fetching directly the content of http://third.com/page.html, the Middle Party Server generates a content in which it puts the URL of the third party content as a hyperlink <a href = "http://third.com/page.html" rel = "noreferrer noopener"></a>. The most important part of this content is in the rel attribute value. Therefore, noreferrer noopener instructs the browser not the send the Referer header when the link http://third.com/page.html is followed client-side. JavaScript Injection module adds a script to the content so that the link gets automatically followed once the content is rendered by the browser. Once the link is followed, the browser fetches the third party content directly on the third party server, without going through the Middle Party server anymore. Nonetheless, it does not include the Referer header for identifying the website. Therefore, the document.referrer API also returns an empty string inside the iframe context. This prevents it from identifying the website. The third party server response is placed within a new iframe nested within a context that belongs to the Middle Party, and not directly within the site webpage. This prevents in-context scripts and the cross-context content from exchanging tracking information as illustrated by Figure 4.

HTTPS Content. We recommend deploying the Middle Party Server as an HTTPS server. Therefore, third party content originally served over HTTPS (before rewriting) still get served over HTTPS even in the presence of the Middle Party Server . Moreover, third party content originally served over HTTP would get blocked by current browsers according to the Mixed Content policy [START_REF] West | Mixed Content[END_REF]. With an HTTPS Middle Party, HTTP third party requests will not be prevented from loading since they are fetched over HTTPS through the Middle Party.

Multiple Redirections. A third party may attempt to circumvent our solution by performing multiple redirections. This is commonly used in advertisements (though ads are not in scope of this paper).

When a (third party) web server wants to perform a redirection to another server, it usually does so by including in the response, a special HTTP Location that indicates the server to which the next request will be sent. The Middle Party Server prevents such circumvention by rewriting the Location header so that the browser sends the next redirection request to the Middle Party Server again. As a result, all the redirections pass via the Middle Party.

Implementation

We have implemented both the Rewrite Server and the Middle Party Server as full Node.js [10] web servers supporting HTTP(S) protocols and web sockets. Implementation details are available at https://webstats.inria.fr/sstp/.

Rewrite Server. In our implementation, we deploy the Rewrite Server on the same physical machine as the original web application server. In order to do so, we moved the original server on a different port number, and the Rewrite Server on the initial port of the original server. Therefore, requests that are sent by browsers reach first the Rewrite Server. It then simply forwards them to the original server, which handles the request as usual and return a response to the Rewrite Server. Then, HTML webpages, and CSS files are rewritten using the HTML Rewriter and CSS Rewriter components respectively. To handle dynamic third party content, we inject a script. And in order to prevent malicious third parties from bypassing the redirection, we inject a CSP (See Section 3.1).

Middle Party. All requests to load third party contents embedded in a website deploying our architecture will go through the Middle Party Server. In-Context and cross-context contents are handled differently.

In-Context Contents are simply stripped off tracking information that they carry from the browser to the third parties and vice versa. See Section 3 for the list of tracking information that are removed from third party requests and responses. In particular, third party CSS responses are rewritten, using the CSS Rewriter component, to redirect to the Middle Party Server any third party content that they may further embed. As in the case of the Rewrite Server, this component is implemented using a CSS parser [START_REF]CSS Parser for Node[END_REF] for Node.js Cross-Context contents are handled in a way that the original website identity is not leaked to them. They are also prevented from communicating with any in-context third party content to exchange tracking information. If the crosscontext URL was http://third.com/page.html, instead of making a request to third.com, the Middle Party Server returns to the browser a response consisting of rewriting the URL to 1 <a href= " http: // third.com / page.html " rel= " noreferrer noopener " > < / a > .

and injecting the following script: Overall, when this response is rendered, the browser will not the Referer header to the third party, and the third party is prevented from communicating with in-context content, as explained in Section 3.2.

Discussion and Limitations

Our approach suffers from the following limitations. First, our implementation prevents cross-context and in-context contents from communicating with each other using postMessage API. However, in-context third party script can identify the website a user visits via document.location.href API. Then the script can include the website URL, say http://main.com, as a parameter of the URL of a third party iframe, for example http://third.com/page.html?ref=http://main.com and dynamically embed it in the webpage. In our architecture, this URL is rewritten and routed to the Middle Party. Since, the Middle Party Server does not inspect URL parameters, this information will reach the third party even though the Referer is not sent with cross-context requests.

Another limitation is that of dynamic CSS changes. For instance, changing the background image via the style object of an element in the webpage is not captured by the dynamic rewriting script injected in webpages. Therefore, if the image was a third party image, the CSP will prevent it from loading.

Performance Overhead. There is a performance cost associated with the Rewrite Server, which can be evaluated as the cost of introducing any reverse proxy to a web application architecture (See Section 3.1). Rewriting contents server-side and browser-side is also expensive in terms of performance. We believe that server-side caching mechanisms, in particular for static webpages, may help speed up the responsiveness of the Rewrite Server.

The Middle Party Server may also lead to performance overhead especially for webpages with numerous third party contents. Therefore, it can be provided as a service by a trusted external party, as it is the case for Content Distribution Networks (CDNs) serving contents for many websites.

Extension to Stateless Tracking. Even though this work did not address stateless tracking, such as device fingerprinting, our architecture already hides several fingerprintable device properties and can be extended to several others: 1) The redirection to the Middle Party anonymizes the real IP addresses of users;

2) Some stateless tracking APIs such as window.navigator, window.screen, and HTMLCanvasElement can be easily removed or randomized from the context of the webpage to mitigate in-context fingerprinting.

Possibility to Blocking Active User Recognition in Cross-Context. With the prevalence of third party tracking on the web, we have shown the challenges that a developer will face towards mitigating that. The sandbox attribute for iframes help prevent access to security-sensitive APIs. As tracking has become a hot concern, we suggest that similar mechanisms can help first party websites tackle third party tracking. The sandbox attribute can for instance be extended with specific values to tackle tracking. Nonetheless, the sandbox attribute can be used to prevent cross-context from some stateful tracking mechanisms [START_REF]Iframe Sandbox Attribute[END_REF].

Evaluation and Case Study

Demo website. We have set up a demo website that embeds a collection of third party content, both in-context and cross-context. In-context content include images, HTML5 audio and video, and a Google Map which further loads dynamic content such as images, fonts, scripts, and CSS files. A Youtube video is embedded as cross-context content in an iframe. The demo website is deployed at https://sstp-rewriteproxy.inria.fr. With the deployment of our solution, there is no change from a user perspective on how the demo website is accessed. Indeed, it is still accessible at https://sstp-rewriteproxy.inria.fr. However from the server-side, it is the Rewrite Server which is now running at https://sstp-rewriteproxy.inria.fr instead of the original server. It then intercepts user requests and forwards them to the original server which has been moved on port 8080 (http://sstp-rewriteproxy.inria.fr:8080), hidden from users and the outside.

The Middle Party Server runs at https://sstp-middleparty.inria.fr. With our architecture deployed, all requests to fetch third party content embedded in the demo website are redirected to the Middle Party Server. For in-context content, its removes any tracking information in the requests sent by the browser. Then it forwards the requests to the third parties. Any tracking information set by the third parties in the responses are also removed before being forwarded to the browser. For the cross-context content (Youtube Video in our demo), it is not directly loaded as an iframe inside the demo page. Instead, an iframe from the Middle Party Server is created and embedded inside the demo webpage. Then the Youtube video is automatically loaded in another iframe inside this first iframe which context is that of Middle Party Server. During this process, the Referer header is not leaked to Youtube (Section 3.2), preventing it from identifying the demo website in which it is included. In the Appendix, we show a screenshot of redirection requests to the Middle Party Server.

Real websites. Since we did not have access to real websites, we could not install the Rewrite Server and evaluate our solution on them. We therefore implemented a browser proxy based on a Node.js proxy [11], and included all the logic of the Rewrite Server within the proxy. The proxy was deployed at https://sstp-rewriteproxy.inria.fr:5555 and acts like the Rewrite Server for real websites intercepting and forwarding requests to them, and rewriting the responses in order to redirect them to our Middle Party Server deployed at https://sstp-middleparty.inria.fr.

We then evaluated our solution on different kinds of websites: a news website http://www.bbc.com, an entertainment website http://www.imdb.com, and a shopping website http://verbaudet.fr. All three websites load content from various third party domains. Visually, we did not notice any change in the behaviors of the websites. We also interacted with them in a standard way (clicking on links on a news website, choosing products and putting them in the basket on the shopping website) and the main functionalities of the websites were preserved.

Overall, these evaluation scenarios have helped us improve the solution, especially rewriting dynamically injected third party content. We believe that this implementation will get even mature in the future when we will be able to convince some website owners to deploy it.

Limitations of the evaluation on real websites.

The evaluation on the real websites may break some features or introduce performances issues. Here, we discuss such problems and how to prevent them.

Third party identity (OpenID) providers such as Facebook or Google need to use third party cookies in order to be able to authenticate users to websites embedding them. Therefore, stripping off cookies can prevent users from successfully logging in to the related websites. In a deployment scenario, we make it possible for the developer to instruct the Rewrite Server not to rewrite such third party identity provider content so that users can still log in. Furthermore, it is common for websites to rely on Content Distribution Networks (CDNs), from which they load content for performance purposes. Therefore, rewriting and redirecting CDNs requests to the Middle Party Server can introduce performance issues. In this case also, a developer can declare a list of CDNs which requests should not be rewritten by the Rewrite Server.

Finally, as one may have noticed, the real websites we have considered in our evaluation scenario are all HTTP websites. We could not evaluate our solution on real HTTPS websites because HTTPS requests and responses that arrive at the browser proxy are encrypted. Therefore, we could not be able to rewrite third party content that are embedded in such websites.

Related Work

A number of studies have demonstrated that third party tracking is very prevalent on the web today and analyzed the underlying tracking technologies [START_REF] Englehardt | Online tracking: A 1-million-site measurement and analysis[END_REF][START_REF] Krishnamurthy | Privacy diffusion on the web: a longitudinal perspective[END_REF][START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF][START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF]. Lerner et al. [START_REF] Lerner | Internet jones and the raiders of the lost trackers: An archaeological study of web tracking from 1996 to 2016[END_REF] analyzed how third party tracking evolved for a period of twenty years. Trackers have been categorized according to either their business relationships with websites [START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF], their prominence [START_REF] Englehardt | Online tracking: A 1-million-site measurement and analysis[END_REF][START_REF] Krishnamurthy | Privacy diffusion on the web: a longitudinal perspective[END_REF] or the user browsing profile that they can build [START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF]. Mayer and Mitchell [START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF] grouped tracking mechanisms in two categories called stateful (cookie-based and super-cookies) and stateless (fingerprinting). It is rather intuitive to convince ourselves about the effectiveness of a stateful tracking, since it is based on unique identifiers that are set in users browsers. Nonetheless, the efficacy of stateless mechanisms has been extensively demonstrated. Since the pioneer work of Eckersley [START_REF] Eckersley | How Unique Is Your Web Browser?[END_REF], new fingerprinting methods have been revealed in the literature [START_REF] Abgrall | XSS-FP: browser fingerprinting using HTML parser quirks[END_REF][START_REF] Acar | The web never forgets: Persistent tracking mechanisms in the wild[END_REF][START_REF] Acar | FPDetective: dusting the web for fingerprinters[END_REF][START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF][START_REF] Cao | cross-)browser fingerprinting via os and hardware level features[END_REF][START_REF] Englehardt | Online tracking: A 1-million-site measurement and analysis[END_REF][START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF][START_REF] Starov | Extended tracking powers: Measuring the privacy diffusion enabled by browser extensions[END_REF][START_REF] Takei | Web browser fingerprinting using only cascading style sheets[END_REF]. A classification of fingerprinting techniques is provided in [START_REF] Upathilake | A classification of web browser fingerprinting techniques[END_REF]. Those studies have contributed to raising public awareness of tracking privacy threats. Mayer and Mitchell [START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF] have shown that users are very sensitive to their online privacy, thus hostile to third party tracking. Englehardt et al. [START_REF] Englehardt | Cookies that give you away: The surveillance implications of web tracking[END_REF] have demonstrated that tracking can be used for surveillance purposes. The success of anti-tracking defenses is yet another illustration that users are concerned about tracking [START_REF] Merzdovnik | Block me if you can: A large-scale study of tracker-blocking tools[END_REF].

There are a number of defenses that try to protect users against third party tracking. First, major browser vendors do natively provide mechanisms for users to block third party cookies or browse in private/incognito mode for instance. More and more browsers even take a step further, considering privacy as a design principle: Tor Browser [17], TrackingFree [START_REF] Pan | I do not know what you visited last summer: Protecting users from stateful third-party web tracking with trackingfree browser[END_REF], Blink [START_REF] Laperdrix | Beauty and the beast: Diverting modern web browsers to build unique browser fingerprints[END_REF], CLIQZ [START_REF] Cliqz | [END_REF].

But the most popular defenses are browser extensions. Being tightly integrated into browsers, they provide additional privacy features that are not natively implemented in browsers. Well known privacy extensions are Disconnect [START_REF]Disconnect[END_REF], Ghostery [START_REF] Ghostery | [END_REF], ShareMeNot [START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF], which is now part of PrivacyBadger [START_REF] Badger | [END_REF], uBlock Origin [20] and a relatively new MyTrackingChoices [START_REF] Achara | Mytrackingchoices: Pacifying the ad-block war by enforcing user privacy preferences[END_REF]. Merzdovnik et al. [START_REF] Merzdovnik | Block me if you can: A large-scale study of tracker-blocking tools[END_REF] provide a large-scale evaluation of these anti-tracking defenses. Well known trackers such as advertisers, which businesses heavily depend on tracking, have also been taking steps towards limiting their own tracking capabilities [START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF]. The W3C is pushing forward the Do Not Track standard [18,19] for users to easily express their tracking preferences so that trackers may comply with them. To the best of our knowledge, we are the first to investigate how a website owner can embed third party content while preventing them from accidentally tracking users. The idea of proxying requests within a webpage is inspired by web service workers API [START_REF]Service Worker API[END_REF], though this API is still a working draft which is currently being tested in Mozilla Firefox and Google Chrome.

Conclusions

Most of the previous research analyzed third party tracking mechanisms, and how to block tracking from a user perspective. In this work, we classified third party tracking capabilities from a website developer perspective. We proposed a new architecture for website developers that allows to embed third party content while preserving users privacy. We implemented our solution, and evaluated it on real websites to mitigate stateful tracking.

Appendix

Screenshots of the demo website map console.

Fig. 1 .

 1 Fig. 1. Third Party Tracking

Fig. 2 .

 2 Fig. 2. Stateful tracking mechanisms

Fig. 3 .

 3 Fig. 3. Privacy-Preserving Web Architecture in-context content such as images and scripts, the Middle Party Server prevents user recognition and website identification, while for cross-context content such as iframes, it prevents website identification and communication with other incontext scripts.

Fig. 4 .

 4 Fig. 4. Prevent Combining in-context and cross-context tracking

Fig. 5 .

 5 Fig. 5. A demo page displaying a Google Maps

Table 1 .

 1 Third Party Content and Execution Context.

		HTML Tags	Third Party Content
		<link>	Stylesheets
		<img>	Images
	in-context	<audio>	Audios
		<video>	Videos
		<form>	Forms
		<script>	Scripts
	cross-context	<(i)frame>, <frameset>, <a> <object>, <embed>, <applet> Plugins and Web pages Web pages

Table 2 .

 2 Injecting Dynamic Third Party Content

	API	Content
	document.createElement inject content from Table 1
	document.write	any content
	window.open	Web pages(popups)
	Image	images
	XMLHttpRequest	any data
	Fetch, Request	any content
	EventSource	stream data
	WebSocket	websocket data

Origin header is also automatically generated by the browser when the third party content is trying to access data using Cross-Origin Resource Sharing[START_REF]Cross-origin-resource sharing[END_REF] mechanism.


Nahuel A Villa

Pierre-Brice Wieber

Model Predictive Control of Biped Walking with Bounded Uncertainties

A biped walking controller for humanoid robots has to handle together hard constraints, dynamic environments, and uncertainties. Model Predictive Control (MPC) is a suitable and widely used control method to handle the first two issues. Uncertainties on the robot imply a non-zero tracking error when trying to follow a reference motion. A standard solution for this issue is to use tighter constraints by introducing some hand tuned safety margins, for the reference motion generation to ensure that the actual robot motion will satisfy all constraints even in presence of the tracking error. In this article, we find bounds for the tracking error and we show how such safety margins can be precisely computed from the tracking error bounds. Also, a tracking control gain is proposed to reduce the restrictiveness introduced with the safety margins. MPC with these considerations ensure the correct operation of the biped robot under a given degree of uncertainties when it is implemented in open-loop. Nevertheless, the straightforward way to implement an MPC closed-loop scheme fails. We discuss the reasons for this failure and propose a robust closed-loop MPC scheme.

I. INTRODUCTION

Walking depends on contact forces between the feet and the ground. The unilateral nature of this interaction (feet can only push on the ground) limits the motion that a legged robot can realize and plays a crucial role in its stability. When walking on a flat ground, this corresponds to having the Center of Pressure (CoP) stay within the support polygon [START_REF] Wieber | Modeling and control of legged robots[END_REF]. Model Predictive Control (MPC) is one of few suitable methods to handle such constraints [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF], and has been used therefore extensively for the control of legged robots. This allows generating walking motions online with automatic footstep placement [START_REF] Herdt | Online walking motion generation with automatic footstep placement[END_REF], taking into account visual feedback [START_REF] Dune | Vision based control for humanoıd robots[END_REF], avoiding collisions in a crowd [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF], undertaking physical collaborations with humans [START_REF] Agravante | Walking pattern generators designed for physical collaboration[END_REF].

In a complex system such as a humanoid robot, sources of uncertainties abound: noisy sensors, imperfect actuators, unmodeled dynamics, inaccurate models of the environment, etc. These sources of uncertainty can always be reduced with more precise (and more expensive) hardware or we can try to estimate them, but only up to a point: there always remains a certain amount of uncertainty. And as a result, there always remains a certain amount of tracking error when trying to follow a reference motion [START_REF] Choi | On the walking control for humanoid robot based on the kinematic resolution of com jacobian with embedded motion[END_REF], [START_REF] Feng | Optimizationbased full body control for the darpa robotics challenge[END_REF], [START_REF] Englsberger | Bipedal walking control based on capture point dynamics[END_REF], [START_REF] Wieber | Modeling and control of legged robots[END_REF], [START_REF] Kerrigan | Robust constraint satisfaction: Invariant sets and predictive control[END_REF]. In order to satisfy all constraints in the presence of such tracking error, the usual approach is to introduce hand tuned safety margins [START_REF] Wieber | Trajectory free linear model predictive control for stable walking in the presence of strong perturbations[END_REF]. The first contribution of this paper is to show how such safety margins can be computed precisely based on the tracking error produced by a given set of uncertainties.

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP*, LJK, 38000 Grenoble, France nahuel.villa@inria.fr; pierre-brice.wieber@inria.fr.

The reference motion is usually generated with an MPC scheme independently from the actual robot motion [START_REF] Feng | Optimization based full body control for the atlas robot[END_REF]. We will refer to this approach as Open Loop MPC (OL-MPC). There are situations, however, where it is necessary to generate a reference motion taking into account the actual state of the robot [START_REF] Feng | Robust dynamic walking using online foot step optimization[END_REF], such as when there is a strong perturbation. A classical approach is to generate the reference motion starting directly from the actual state of the robot. We will refer to this approach as Closed Loop MPC (CL-MPC). Unfortunately, we are going to see that this approach can fail. In an approach discussed in [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF], the initial state of the reference motion is actually chosen to take into account the actual state of the robot but also ensure explicitly robustness. We will refer to this approach as Robust Closed Loop MPC (RCL-MPC).

Robust control is an approach to controller design that explicitly deals with uncertainty. One possible aim is to reduce the probability of failure [START_REF] Agravante | Walking pattern generators designed for physical collaboration[END_REF], [START_REF] Dai | Planning robust walking motion on uneven terrain via convex optimization[END_REF], [START_REF] Del Prete | Robustness to joint-torque-tracking errors in task-space inverse dynamics[END_REF]. But here, we aim at ensuring the correct operation of the system for any uncertainty between certain bounds.

Section II briefly introduces the dynamics of walking. Section III proposes an analysis of tracking error under bounded uncertainties, and introduces the key concept of Robust Positive Invariant (RPI) set. Section IV discusses how to optimize tracking control gains in order to minimize the necessary safety margins. Section V introduces different combinations of Model Predictive Control (MPC) scheme and higher-frequency tracking control that can be found in the literature. Section VI demonstrates with simple simulations how some of these schemes can fail while others succeed.

II. POINT MASS MODEL WITH BOUNDED UNCERTAINTIES

Let us consider the Center of Mass (CoM) c of a biped robot walking on a flat horizontal ground. From Newton and Euler equations of the whole robot, we obtain the Center of pressure (CoP) [START_REF] Wieber | Modeling and control of legged robots[END_REF] as:

p x,y = c x,y - mc z cx,y + S Lx,y m(c z + g z ) -v x,y , (1)
with L the angular momentum, g z the vertical acceleration due to gravity, m the robot mass, S = 0 -1 1 0 a rotation matrix and v represents a bounded uncertainty:

v ∈ W. (2)
Because contact forces with the ground are unilateral (the robot can push but not pull on the ground), the CoP is bound to lie in the support polygon P:

p ∈ P. (3)
This dynamics is traditionally reformulated as follows in order to emphasize the linear relationship between the horizontal motion of the CoM and the CoP [START_REF] Englsberger | Bipedal walking control based on capture point dynamics[END_REF], [START_REF] Agravante | Walking pattern generators designed for physical collaboration[END_REF], [START_REF] Wieber | Trajectory free linear model predictive control for stable walking in the presence of strong perturbations[END_REF], [START_REF] Sugihara | Standing stabilizability and stepping maneuver in planar bipedalism based on the best com-zmp regulator[END_REF], [START_REF] Choi | On the walking control for humanoid robot based on the kinematic resolution of com jacobian with embedded motion[END_REF], [START_REF] Feng | Online hierarchical optimization for humanoid control[END_REF], dropping coordinate indices x and y :

c = ω 2 (c -p -n -v), (4)
where ω2 = g z /c z and

n = c ω 2 - mc z c + S L m(c z + g z ) . ( 5
)
We can bound the values of n as discussed in [START_REF] Brasseur | A robust linear mpc approach to online generation of 3d biped walking motion[END_REF], [START_REF] Serra | A newton method with always feasible iterates for nonlinear model predictive control of walking in a multi-contact situation[END_REF]:

-n ∈ N .

Assuming that p, n and v are constant over time intervals of length τ , typically 5(ms), we can obtain a linear timeinvariant discrete-time system following a standard procedure [START_REF] Ogata | Discrete-time control systems[END_REF]:

x + = Ax + B(p + n + v), (7)
with

A = cosh(ωτ ) ω -1 sinh(ωτ ) ω sinh(ωτ ) cosh(ωτ ) , B = 1 -cosh(ωτ ) -ω sinh(ωτ ) , x = c ċ ∈ X , (8)
where x + is the successor state. Here, we introduce the state constraint X to take into account maximum leg length.

III. ROBUST POSITIVE INVARIANT SET

Let us consider a reference motion x ref following the nominal, undisturbed linear dynamics

x + ref = Ax ref + Bp ref . (9)
Because of uncertainties v and model errors n in the dynamics [START_REF] Del Prete | Robustness to joint-torque-tracking errors in task-space inverse dynamics[END_REF], we have to consider a (linear) tracking control law (with compensation of n)

p = p ref -n + K(x -x ref ) (10)
to properly follow this reference motion. With this control law, the tracking error

δ = x -x ref (11)
follows the closed-loop dynamics

δ + ∈ (A + BK)δ + BW. (12)
Iterating this closed-loop dynamics N times, the tracking error becomes:

δ +N ∈ (A + BK) N δ + N -1 i=0 (A + BK) i BW, ( 13
)
where ⊕ is the Minkowski sum1 . If the gain K stabilizes the matrix A + BK (eigenvalues inside the unit circle), then when N → ∞ the first term vanishes:

(A + BK) N δ → 0 (14)
and δ +N → Z, where

Z = ∞ i=0 (A + BK) i BW. ( 15
)
When there is no uncertainty, W = {0}, the tracking error converges to the origin, Z = {0}, as desired. But if there are uncertainties, what we see here is that the tracking error δ will converge to a bigger set Z, which depends on W . We can observe from ( 15) that

(A + BK)Z ⊕ BW = Z, (16)
what implies, following the closed-loop dynamics [START_REF] Feng | Optimizationbased full body control for the darpa robotics challenge[END_REF], that

∀δ ∈ Z, ∀v ∈ W, δ + ∈ Z. ( 17
)
Once the tracking error reaches Z, it stays in Z. This set is Robust Positively Invariant (RPI) [START_REF] Rakovic | Invariant approximations of the minimal robust positively invariant set[END_REF], and can serve as a bound on tracking error in steady-state. It can be shown that the set Z defined above is actually the minimal RPI (mRPI) set (in the sense of being a subset of any RPI set of ( 12)) [START_REF] Rakovic | Invariant approximations of the minimal robust positively invariant set[END_REF], so it provides the smallest bound possible on tracking error. Naturally, when δ ∈ Z, Kδ ∈ KZ. In that case, in order to satisfy the constraints ( 3) and ( 8) with the tracking error [START_REF] Feng | Optimization based full body control for the atlas robot[END_REF] and the control law [START_REF] Feng | Online hierarchical optimization for humanoid control[END_REF], the reference motion must clearly satisfy

x ref ∈ X Z, (18)
p ref ∈ P N KZ, (19)
where is the Pontryagin difference 2 . Here, Z and KZ play respectively the role of state and control safety margins for the design of the reference motion x ref .

IV. OPTIMAL TRACKING CONTROL GAINS

It can be interesting to use a tracking control gain K that minimizes the safety margins Z and KZ. In our case the CoP p is the most constrained element in the dynamics. Therefore, we choose to minimize more specifically

KZ = ∞ i=0 K(A + BK) i BW. ( 20
)
Note that if

K(A + BK) = 0, (21)
all terms with i > 0 vanish and the above sum becomes KZ = KBW . We show in the Appendix that this happens with

K = k 1 ω -1 and k = e ωτ e ωτ -1 . ( 22
)
Velocity tracking error ċ -ċref (m.s -1

) We confirmed numerically by computing KZ for the entire range of stabilizing gains, that this choice of K actually minimizes the safety margin KZ.

Position tracking error c -c ref (m) δ (A + BK)δ (A + BK)δ + BW [ 1 ω -1 ] δ =
Introducing the Capture Point (CP)

ξ = c + ω -1 ċ = 1 ω -1 x, (23)
we can observe from ( 21) and ( 22) that for any tracking error δ,

1 ω -1 (A + BK)δ = 0, (24)
so the CP tracking error is driven to 0 in one sampling period. Such a dead-beat control of the CP was already proposed in [START_REF] Englsberger | Bipedal walking control based on capture point dynamics[END_REF] for different reasons as uncertainties were not considered. It corresponds also to "the best regulator" proposed in [START_REF] Sugihara | Standing stabilizability and stepping maneuver in planar bipedalism based on the best com-zmp regulator[END_REF].

The set Z corresponding to this choice of gain K, using parameters provided in Table I, can be seen in Fig. 1, together with the typical behavior of the closed-loop dynamics [START_REF] Feng | Optimizationbased full body control for the darpa robotics challenge[END_REF] of the tracking error. With this choice of gain, the control safety margin becomes

KZ = KBW = -e ωτ W. (25)
As a result, the maximal set of uncertainties such that KZ ⊆ P, so that the constraint [START_REF] Ogata | Discrete-time control systems[END_REF] is nonempty (Neglecting N ), is W max = -e -ωτ P.

For example assuming a source of uncertainties in the form of an external horizontal force f acting on the CoM of the robot,

v = - f mω 2 , (27)
parameters in Table I would lead to a maximal force f max = 48(N). It is standard practice to include a saturation in the control law [START_REF] Feng | Online hierarchical optimization for humanoid control[END_REF] with respect to the constraint (3), either explicitly limiting its value [START_REF] Englsberger | Bipedal walking control based on capture point dynamics[END_REF], [START_REF] Sugihara | Standing stabilizability and stepping maneuver in planar bipedalism based on the best com-zmp regulator[END_REF] or in an optimization problem [START_REF] Wieber | Trajectory free linear model predictive control for stable walking in the presence of strong perturbations[END_REF]. This usually increases significantly the region of attraction of the control law [START_REF] Atkeson | Notes on Saturation and Region of Attraction[END_REF]. But this leads to a piecewise linear dynamical behavior, which is more demanding to analyze. In this article, we will limit our analysis to the linear behavior where the saturation is not reached, considering only sets of uncertainties W ⊆ W max . Our results are therefore conservative, not considering the improvements due to saturation.

V. MPC SCHEME FOR BIPED WALKING

Humanoid robots are supposed to adapt to dynamically changing environments [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF], [START_REF] Agravante | Walking pattern generators designed for physical collaboration[END_REF], [START_REF] Dune | Vision based control for humanoıd robots[END_REF], so the reference walking motion introduced in Section III must be computed online and adapted accordingly. This is usually done with some form of MPC in order to make sure that constraints [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF] and [START_REF] Ogata | Discrete-time control systems[END_REF] are satisfied. We usually want this reference motion to follow some desired trajectory for the CoM and CoP, minimizing an objective function

α 1 p ref -p d 2 + α 2 c ref -c d 2 + α 3 ċref -ċd 2 , ( 28
)
where α 1 , α 2 and α 3 are predefined weights. To maintain stability and recursive feasibility, we consider a capturability condition as terminal constraint [START_REF] Sherikov | Balance preservation and task prioritization in whole body motion control of humanoid robots[END_REF], taking into account the safety margin KZ:

ξ +N ref ∈ P N KZ. ( 29
)
While the tracking control law (10) is sampled every τ = 5(ms), the reference walking motion is classically recomputed only every T = 100(ms) [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF]. Each time it is recomputed, the initial reference state x 0 ref for the prediction can be chosen in different ways. Following the analysis in section III, we know that if the initial tracking error δ 0 is in the set Z,

δ 0 = x 0 -x 0 ref ∈ Z, (30)
where x 0 is the current state of the robot, then the safety margins in ( 18) and ( 19) ensure that the control and state constraints (3) and ( 8) are correctly satisfied. The reference motion is usually generated with an MPC scheme independently from the actual robot motion [START_REF] Feng | Optimization based full body control for the atlas robot[END_REF]. In that case, since the set Z is robust invariant, condition (30) is recursively satisfied and robust recursive feasibility is ensured for all v ∈ W (see prop.2 in [START_REF] Langson | Robust model predictive control using tubes[END_REF]). We are going to see, however, that this choice is too restrictive and can fail tracking desired trajectories even when there are no uncertainties. We will refer to this approach as Open Loop MPC (OL-MPC).

There are situations, anyway, where it is necessary to generate a reference motion taking into account the actual state of the robot [START_REF] Feng | Robust dynamic walking using online foot step optimization[END_REF], such as when there is a strong perturbation. A classical approach is to generate the reference motion starting directly from the actual state of the robot:

x 0 ref = x 0 . ( 31
)
That clearly satisfy the condition ( 30), but we are going to see that this choice is actually still too restrictive, as desired trajectory tracking can fail even when there are no uncertainties. And when there are uncertainties, recursive feasibility [START_REF] Kerrigan | Robust constraint satisfaction: Invariant sets and predictive control[END_REF] is lost since the initial state (31) may not satisfy constraints ( 18) or ( 29), and the controller can diverge.

We will refer to this approach as Closed Loop MPC (CL-MPC).

In an approach discussed in [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF], the initial state of the reference motion x 0 ref is optimally chosen to take into account the actual state of the robot satisfying ( 18), ( 29) and (30) as constraints. Robust recursive feasibility for all v ∈ W is ensured in this case (see prop.3 in [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF]). We will refer to this approach as Robust Closed Loop MPC (RCL-MPC).

VI. SIMULATIONS

We are going to consider now three different scenarios, all involving exclusively lateral motion of the robot, with potential uncertainty v up to ±0.05 (m), which is significant with respect to the 0.14 (m) wide feet of the robot, in order to illustrate as clearly as possible the differences in behavior obtained with these different MPC schemes. Simulation parameters are provided in Table I.

In the first scenario, the robot is standing still on one foot, without any uncertainty, starting from desired positions of the CoP and CP on the boundary of the control safety margin:

p d = ξ d = 0.019(m).
During the simulation, these desired positions are switched to the middle of the foot: p d = ξ d = 0(m). In this case, in order to move the CP to the middle of the foot, the CoP would have to enter the control safety margin. With both the OL-MPC and the CL-MPC schemes, the reference motion is prohibited to do so. As a result, it can't follow the desired position, and stays stuck instead in its initial position, as shown in Fig. 2. With RCL-MPC, the reference motion is free to start from a different position, slightly away from the boundary of the control safety margin. As a result, the reference motion is able to follow the desired position without problem, as shown in Fig. 3. In the second scenario, the robot is again standing still on one foot, starting from desired positions of the CoP and CP on the boundary of the control safety margin: p d = ξ d = 0.019(m). This time, however, these desired positions are kept constant, and uncertainties are applied instead to the system. After some initial time without uncertainties, a constant, maximal uncertainty is applied for some time, before changing randomly every T = 0.1(s), and then every τ = 0.005(s). As soon as the first uncertainty appears, the state of the system is immediately driven slightly inside the control safety margin. At that moment, the terminal constraint in the CL-MPC scheme becomes instantaneously infeasible. If we relax this terminal constraint (as done for example in [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF] for a different reason), the state of the system quickly diverges, as shown in Fig. 4. On the contrary, with both the OL-MPC and the RCL-MPC schemes, the reference motion is kept stationary, and safely tracked by the control law [START_REF] Feng | Online hierarchical optimization for humanoid control[END_REF] as shown in Fig. 5. A zoom on the behavior of the CP is also provided, to show that it stays within bounds

ξ -ξ ref ∈ 1 ω -1 Z (32)
as expected.

The third scenario involves walking nine consecutive steps before stopping on one foot, and summarizes all the behaviors demonstrated earlier. After a couple steps are realized in place, the desired position is shifted 0.5 (m) on the side. After four more steps are realized, a constant uncertainty is applied.

With the OL-MPC scheme (top of Fig. 6), we can observe a significant tracking error (actually an overshoot) with respect to the desired position on the fifth step. With the CL-MPC scheme (middle of Fig. 6), the overshoot is still present, and divergence shortly after the uncertainty is introduced. With the RCL-MPC scheme, both the overshoot and the divergence are avoided (bottom of Fig. 6).

The RCL-MPC scheme clearly shows a much improved behavior over both the CL-MPC and the OL-MPC schemes.

VII. CONCLUSIONS

We analyzed the tracking error dynamics in biped robots affected by bounded uncertainties, and we found the smallest bound possible for the tracking error (the mRPI set) [START_REF] Kerrigan | Robust constraint satisfaction: Invariant sets and predictive control[END_REF]. In order to ensure the robot motion recursively satisfies constraints (3) and ( 8), the reference motion has to be generated Fig. 6: With the OL-MPC scheme (top), we can observe a significant overshoot with respect to the desired position on the fifth step. With the CL-MPC scheme (middle), the overshoot is still present and divergence shortly after the uncertainty is introduced. With the RCL-MPC scheme, both the overshoot and the divergence are avoided (bottom). satisfying tighter constraints that consider the tracking error, as shown in [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF], [START_REF] Ogata | Discrete-time control systems[END_REF] and (29).

In [START_REF] Brasseur | A robust linear mpc approach to online generation of 3d biped walking motion[END_REF] and [START_REF] Serra | A newton method with always feasible iterates for nonlinear model predictive control of walking in a multi-contact situation[END_REF] it is proposed a robust approach to handle bounded model errors. The reference motion is optimized to satisfy the system constraints for any possible value of error within these bounds. The present work extends this approach to consider also a tracking error produced by bounded uncertainties.

We proposed a tracking control gain [START_REF] Sherikov | Balance preservation and task prioritization in whole body motion control of humanoid robots[END_REF] to reduce safety margin size and handle bigger uncertainties. Using parameters corresponding to HRP2 (Table I), and assuming a source of uncertainties in the form of an external horizontal force f , applied on the CoM, the maximal uncertainty supported corresponds to f max = 48(N).

OL-MPC scheme is normally used in biped robots [START_REF] Feng | Online hierarchical optimization for humanoid control[END_REF] since the correct walking dynamics is ensured for the considered set of uncertainties. In the case of the closed-loop MPC schemes, if the reference motion is generated at each sample time directly from the actual state of the robot (CL-MPC), the controller may fail. This problem is fixed generating the reference motion to satisfy [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF], ( 29) and (30) as constraints (RCL-MPC).

Fig. 1 :

 1 Fig.1: With the choice of gain[START_REF] Sherikov | Balance preservation and task prioritization in whole body motion control of humanoid robots[END_REF], the minimal Robust Positive Invariant (mRPI) set Z is a parallelogram. Any tracking error δ (blue circle) is driven by the closed-loop matrix A + BK onto the line [1 ω -1 ]δ = 0 (dashed line). An uncertainty is then added from the set BW (red segment).

Fig. 2 :Fig. 3 :

 23 Fig. 2: With both the CL-MPC and the OL-MPC schemes, the CP (black line) and the CoP (blue line) are stuck on the boundary of the control safety margin and can't follow the desired position (blue dashed line) to the middle of the foot.

Fig. 4 :Fig. 5 :

 45 Fig.4: With the CL-MPC scheme, the CP (black line) quickly diverges as soon as the first uncertainty appears.

APPENDIX

  Let us consider a tracking control gain of the form K = k 1 λ and look for values k and λ such thatK(A + BK) = KA + KBK = k cosh(ωτ ) + λω sinh(ωτ ) ω -1 sinh(ωτ ) + λ cosh(ωτ ) + k 2 (1 -cosh(ωτ ) -λω sinh(ωτ )) 1 λ = 0.Multiplying on the right by λ -1 we obtain that λ 2 ω 2 = 1, the positive solution is λ = ω -1 . Replacing this value in the previous expression gives k = e ωτ e ωτ -1 .

TABLE I :

 I Numerical Values

	Parameter	Symbol	Value	Unit
	CoM Height	c z	0.8	(m)
	Robot Mass	m	58	(kg)
	Gravity Acceleration	g	9.81	(m.s -2 )
	Natural Frequency	ω	3.5	(s -1 )
	Support Polygon	P	[-0.07, 0.07]	(m)
	Set of Uncertainties	W	[-0.05, 0.05]	(m)
	Tracking Sample Period	τ	0.005	(s)
	Tracking Gain (22)	k	57.6	(-)
	Control Safety Margin	KZ	[-0.051, 0.051]	(m)
	MPC Sampling Period	T	0.1	(s)
	MPC Horizon length	N	16	(-)

Given sets A and B, A ⊕ B := {a + b | a ∈ A, b ∈ B}.

Given sets A and B, A B := {x | x + B ⊆ A}.

ACKNOWLEDGMENT

This work has been funded by the PSPC Romeo 2 project and EU H2020 Comanoid Research and Innovation Action (RIA). The authors would like to thank Prof. Chris Atkeson for sharing personal notes on saturation and regions of attraction.