Emmanuel Castanier

Coletta Remi

Patrick Valduriez

Christian Frisch
email: christian.frisch@data-publica.com

Public Data Integration with WebSmatch *

Integrating open data sources can yield high value information but raises major problems in terms of metadata extraction, data source integration and visualization of integrated data. In this paper, we describe the demonstration of WebSmatch, a flexible environment for Web data integration, based on a real, end-to-end data integration scenario over public data from Data Publica 1 . WebSmatch supports the full process of importing, refining and integrating data sources and uses third party tools for high quality visualization. We use a typical scenario of public data integration which involves problems not solved by currents tools: poorly structured input data sources (XLS files) and rich visualization of integrated data.

Introduction

Recent open data government initiatives, such as data.gov, data.gov.uk, data.gouv.fr promote the idea that certain data produced by public organizations should be freely available to everyone to use and republish as they wish. As a result, a lot of open data sources are now available on public organization's web sites, in various formats.

Integrating open data sources from different organizations can yield high value information. For instance, matching gas emission data with climatic data for a given country or city can be valuable to better understand pollution. This rich local and targeted pool of information can also be leveraged to build new innovative services or, as a new source of business intelligence, to put in perspective business information with data such as weather, traffic, density of economic activities or touristic information in order to better understand current market dynamics and adapt product and services.

A large share of the available open data comes from large institutions (such as Eurostat, World bank, UN....) using structured data formats such as SDMX for statistical datasets or RDF for linked open data. However, the majority of the data that can be found on open data portals is available as unstructured data (such as spreadsheets). To integrate these sources or deliver data that web applications or mobile services can leverage, raw open data files must be structured through a processing workflow and delivered through APIs (Application Programming Interfaces). This workflow will ultimately transform "human usable information" such as spreadsheets into "computer usable data", drastically increasing the value of the open data published.

Based on this observation, Data Publica, a french company, provides added value over the public data sources they crawl, such as visualization of data sources or production of integrated data. Achieving this goal raises the followings problems:

Metadata extraction. Although structured formats exist to share and publish data, most of the public data available on the Web are Excel spreadsheets, with no difference between data and metadata. Detecting the metadata in such data sources is a mandatory step before performing data integration. To address this problem, we exploit computer vision techniques to deal with complex tabular representations of spreadsheets and machine learning techniques that take advantage of past human effort to automatically detect metadata in the next spreadsheets.

Data sources integration. In order to produce added value information over the public data sources, it is necessary to integrate data sources together. For this purpose, we need to perform schema matching, in order to match metadata structures. In the context of open data, schema matching is harder than in traditional data integration in distributed database systems [START_REF] Özsu | Principles of Distributed Database Systems[END_REF], mainly because important metadata which are considered as implicit by document's authors, are simply missing. In terms of matching capabilities, we rely on YAM++ [START_REF] Ngo | YAM++ results for OAEI[END_REF], a powerful tool for schema matching and ontology alignment 2 .

Visualization. To ease users's access to public data requires visualizing with high quality graphical representation. In Data Publica, the visualization task is delegated to Google Data Explorer, a powerful collection of visualization tools. However, Google Data Explorer imposes strict restrictions on input formats, such as separating data and metadata into different files and labeling metadata with some Google predefined concepts. Therefore, using Google Data Explorer requires metadata extraction and integration as preliminary steps.

To perform these tasks, Data Publica uses WebSmatch http://websmatch.gforge.inria.fr/ , an environment for Web data integration with a service-oriented architecture with much flexibility for users and developers. Most tools for metadata integration are implemented as heavy clients and hard-coded with their own graphical interfaces. They need to be downloaded and installed, which make them hard to use with other independent tools (even if sources are provided) and reduce their dissemination. In contrast, WebSmatch is an open environment to be used as a Rich Internet Application (RIA).

In this paper, we describe the demonstration of WebSmatch based on a real-life, end-to-end data integration scenario over public data-sources.

The paper is organized as follows. Section 2 introduces the scenario of the demonstration in terms of inputs (poorly structured files) and outputs (rich visualization of integrated data). Section 3 presents WebSmatch metadata detection and integration services through the motiving example. Section 4 concludes.

Demonstration scenario

In this section, we describe our demonstration scenario by giving the inputs and outputs of the data integration process with WebSmatch.

Data Publica provides more than 12 000 files of public data. [START_REF] Bancilhon | Size and structure of the french public sector information[END_REF] However, even though data formats become richer and richer in terms of semantics and expressivity (e.g. RDF), most data producers do not use them much in practice, because they require too much upfront work, and keep using simpler tools like Excel. As an example, Data Publica has started to crawl public data available from the French administration, and found only 369 RDF files, compared with 148.509 .xls files. Unfortunately, no integration tool is able to deal in an effective way with spreadsheets. As far as we know, only two recent initiatives, OpenII [START_REF] Seligman | OpenII: an open source information integration toolkit[END_REF] and Google Refine3 deal with Excel files. However, their importers are very simple and make some strict restrictions over the input spreadsheets. For instance, they require to have exactly one table per sheet and all the attributes have to be in columns, at the first line of the sheet. Unfortunately, people do not use Excel in such proper way. And these importers proved to be useless on real spreadsheets from Data Publica. Thus, extracting metadata from such sources remains an open problem [START_REF] Hermans | Automatically extracting class diagrams from spreadsheets[END_REF]. To illustrate this problem in the emonstration, we use the following spreadsheet files as input.

Input files

For simplicity purposes, the scenario of this demo involves only 2 data sources. To be representative of real-life public data, we choose two spreadsheet files: http://www.data-publica.com/publication/1341 is an Excel file. It contains data from the Climatic Research Unit (http://www.cru.uea.ac.uk/ ) about the temperature evolution in the world over the last decades. This file is quite well formed, it only contains some blank lines and comments.

http://www.data-publica.com/publication/4736 is the Excel file depicted at the beginning of the video. It contains data from OECD ( http://www.oecd.org/ ) about gas emissions in the world. The file contains the evolution on the last 20 years on several countries and 4 OECD geographic zones 4 . This spreadsheet is much more complex: it involves several sheets, with several tables per sheet. It contains several blank lines and comments, making it hard to automatically detect the table. In addition, it involves bi-dimensional tabular structures and some column names are missing. For instance, the author of this file probably has in mind that the line containing {1995, 2000} should be labelled by "year", which is not obvious in the context of automatic integration.

Expected results

Video presents the charts, maps and additional animations with timelines obtained after extraction of metadata and integration of the inputs described above.

To perform visualization, Websmatch exports the integrated data in Data Set Publishing Language (DSPL) format https://developers.google.com/public-data/) . DSPL is used by Google Public Data Explorer and Data Publica's own API and visualisation engine. Such format assumes the input data source to be precisely described. In particular, data and metadata need be distinguished. The metadata (source, title, author, header) are described in an XML file whereas the data are in Comma-Separated Values (CSV) files. In addition, metadata need to be tagged by some DSPL predefined concepts (hierarchy including times or geographical entities). Such format is too strict to be usable by a large public, and quite difficult to manipulate, even for computer scientists. Thus, although Google Data Explorer provides a powerful collection of visualization tools, it requires much upfront work from the user, in particular, with public spreadsheets like the ones described above.

Demonstration

WebSmatch is a Rich Internet Application (RIA), meaning that any third party is able to use it remotely, as a Web service, without any installation. To use all the WebSmatch components (integration, matching, clustering and export), one simply needs to put some redirection from his back office. The integration of WebSmatch and Data Publica is depicted in Figure 1. It involves the following flow:

Metadata Detection

After the Crawl, the user is redirected to the WebSmatch RIA. It is important to note that Excel files (such as .xls, for which there is no XML version) are not structured at all. As can be seen in the video, they can contain lots of artifacts such as blank lines, blank columns, titles, comments, and not only a simple table. To get all the metadata and data, the chosen file is parsed and then, two processes are applied to it. The first process relies on a combination of computer vision algorithms. Using the jexcelapi 5 library as a wrapper, the spreadsheet is first translated into a 0/1 bitmap (0 for void cell / 1 for non empty cell). In this bitmap, we run a connected component detection algorithm. Algorithm 1 takes as input a function indicating the color of a point in a bitmap (in our case, a datatype of a cell) and within a one step linear parse of the matrix, assigns a connected component to each cell.

Algorithm 1: Table Detection with Connected Component input : type(i,j): a function returning the datatype of each cell output: cc(i,j) : a function returning the connected component of each cell

foreach 0 < i < n do foreach 0 < j < m do if cc(i -1, j) = null then cc(i, j) ← cc(i -1, j) else cc(i -1, j -1) = null cc(i, j) ← cc(i -1, j -1) else if cc(i, j -1) = null then cc(i, j) ← cc(i, j -1) else if cc(i -1, j + 1) = null then cc(i, j) ← cc(i -1, j + 1) else if type(i, j) = void then cc(i, j) ← new ConnectedComponent()
Algorithm 1 allows us to partition the spreadsheet into regions. We then use more sophisticated computer vision approaches, such as morphologic transformation [START_REF] Haralick | Computer and Robot Vision[END_REF] and erode / dilate functions to refine the result of the connected component detection: remove too small connected components, merge connected components that have been splitt due to a single void line, etc... In the graphical interface (see video), the detected tables are drawn within a frame.

To decide whether data are line-or column-oriented, we exploit the following idea: if data are presented in lines, the datatypes of cells for each line are homogeneous, but the datatypes of cells for each column may be heterogeneous. We then compute the discrepancy in terms of cell datatypes for each line (1) and for each column [START_REF] Haralick | Computer and Robot Vision[END_REF]. If (1) > (2), then the metadata are probably on the first lines, on the first columns otherwise.

X 0<i<n ( max t∈{string,int,...} ( X 0<j<m (type [i,j] = t))) (1)
X 0<j<m ( max t∈{string,int,...} ( X 0<i<n (type [i,j] = t))) (2)
The end of the process relies on machine learning [START_REF] Mitchell | Machine Learning[END_REF]. Using past experience and based on several criterions: the discrepancy measures, the datatype of a cell, the data type of the neighborhood of a cell, WebSmatch detects each important component in the spreadsheet file such as: titles, comments, table data, table header. Machine learning is able to capture several spreadsheet users habits, such as: "cells on the very first line of a connected component, having the string datatype and bellow cells having a numeric datatype are often metadata" or "cells having the string datatype and void neighborhood and behind a table often are a title". The important feature is that such rules have not been designed by the user, but observed on several documents. They can be updated when new spreadsheets are performed by the user.

Matching

WebSmatch relies on YAM++ [START_REF] Ngo | YAM++ results for OAEI[END_REF] to perform Figure 2: Result of integration the matching task. YAM++ combines 14 different matching techniques, divided in 3 main groups: string matchers, dictionary and thesaurus matchers based on Wordnet 6 and instance-based matchers. Instance-based matcher is the generic name for matchers, which deals both with metadata and data. Such matchers are very useful when the column names are not informational enough, which is often the case in public data. The instance-based matcher implemented in YAM is very powerful and one of the main reasons for YAM++ excellent results at the 2011 competition of the Ontology Alignment Evaluation Initiative (http://oaei.ontologymatching.org: first position at the Conference track and second position at the Benchmark track [START_REF] Ngo | YAM++ results for OAEI[END_REF].

In the video, we observe that the cell "année" (i.e. year in french), which has been previously detected as metadata, is detected as "time:year" concept by applying the instance-based matcher on its data collection {1990, 1991, . . .}. Figure 2 depicts all the discovered matches over the two files of the scenario and the DSPL concepts we previously imported into the tool.

Notice that the line of the second spreadsheet contains a line within a collection of years but with a void cell as first column. Despite it is void, this cell is detected by WebSmatch to be a metadata. Indeed, it is at the first line and first column of the detected table and our machine learning algorithm detects the metadata to be placed in the first column. By applying the instance-based matcher, WebSmatch suggests this cell to be labelled with the "time:year" concept.

Visualization

By detecting the blank cell, we are able to convert the bi-dimensionnal table from the initial spreadsheet into a classical (SQL-like) flat table (Figure 2). Thanks to the matching process, we are also able to identify concepts (from DSPL) over the data sources and to detect common attributes in order to produce integrated data.

At this step, we have distinguished data and metadata from the initial Excel files, and flatted bidimensionnal tables. We can easily generate an XML file describing the metadata (title, header, concepts) and the .csv files containing the data to fit the strict DSPL input format. As a result, we can take advantage of the powerful capabilities of Google Data Explorer in terms of visualization, or the cleaned sources can be exported to feed mash-up applications (such as http://pipes.yahoo.com/pipes/). The structured data can also be loaded into Data Publica's database as shown in Section 2.

Conclusion

In this paper, we described the demonstration of WebSmatch, a flexible environment for Web data integration, based on a real data integration scenario over public data from Data Publica. We chose a typical scenario that involves problems not solved by currents tools: poorly structured input data sources (XLS files) and rich visualization of integrated data. WebSmatch supports the full process of importing, refining and integrating data sources and uses third party tools for high quality visualization and data delivery. The demonstration will provide additional scenarios, involving more data sources and including data source recommendation using the clustering service. The attached video of the whole demo is also available at http://www.youtube.com/watch?v=sqeU1lkXW A. Furthermore, it can be played with a test account at http://websmatch.gforge.inria.fr.

Figure 1 :

 1 Figure 1: Data Integration process

YAM++ was recently ranked first at the Conference track of the OAEI competition over 15 participants. See the results at http://oaei.ontologymatching.org/2011/ for more details.

http://code.google.com/p/google-refine/

See http://stats.oecd.org/glossary/ for more details about these zones.

http://jexcelapi.sourceforge.net/

http://wordnet.princeton.edu/


Ali Hasnain
email: ali.hasnain@deri.org

Mustafa Al-Bakri
email: mustafa.al-bakri@imag.fr

Luca Costabello
email: luca.costabello@inria.fr

Zijie Cong
email: zijie.cong@urjc.es

Ian Davis

Tom Heath
email: tom.heath@talis.com

Spamming in Linked Data

Keywords: Linked Data, Spam, Spam Vectors 7

The rapidly growing commercial interest in Linked Data raises the prospect of "Linked Data spam", which we define as "deliberately misleading information (data and links) published as Linked Data, with the goal of creating financial gain for the publisher". Compared to conventional technologies affected by spamming, e.g. email and blogs, spammers targeting Linked Data may not be able to push information directly towards consumers, but rather may seek to exploit a lack of human involvement in automated data integration processes performed by applications consuming Linked Data. This paper aims to lay a foundation for future work addressing the issue of Linked Data spam, by providing the following contributions: i) a formal definition of spamming in Linked Data; ii) a classification of potential spamming techniques; iii) a sample dataset demonstrating these techniques, for use in evaluating anti-spamming mechanisms; iv) preliminary recommendations for anti-spamming strategies.

Introduction

Adoption by organisations such as the BBC 7 , New York Times 8 and BestBuy 9 demonstrates a rapidly growing commercial interest in Linked Data. Initiatives such as schema.org 10 further increase the financial incentives to participate in a Web of Data by boosting the publisher's prominence in search engine results. These factors increase the likelihood of rogue users attempting to pollute the Web with malicious data that brings them some financial gain, creating a form of "Linked Data spam". In the Linked Data context we define spam as "deliberately misleading information (data and links) published as Linked Data, with the goal of creating financial gain for the publisher".

The emphasis of Linked Data, on publishing and interconnecting machinereadable data on the Web, means spam in this context differs from that found in traditional channels such as wikis and blog comments. Those environments provide convenient mechanisms for publishers to push information towards consumers, a process which does not have direct analogues in the Linked Data paradigm. However, as an open environment, the Web of Data allows any party to publish their own data, therefore seek to subvert the mechanisms of Linked Data consumption to exploit end users.

In tandem with ongoing challenges such as performance, reliability and security [START_REF] Moller | Learning from linked open data usage: Patterns & metrics[END_REF], applications consuming Linked Data may be severely impacted by the discovery, integration and usage of spam data from the Web. Spamming may take the form of undermining the trust assumption between datasets, introducing malicious triples or modifying existing content, determining undesirable behaviour in end-user applications.

To date, the Linked Data and Semantic Web research community has not systematically addressed the issue of Linked Data spam. As applications consuming Linked Data become more widespread this need must be addressed. This is the goal of the work presented here. While harmful attacks can be performed on other layers of the Internet infrastructure (e.g. DNS spoofing, DoS attacks), the scope of this work is limited to spam that exploits Linked Data specifications. The contributions of this work include: i) definition of spamming in Linked Data; ii) classification of possible spamming techniques; iii) sample dataset for demonstrating spamming techniques and evaluating anti-spamming mechanisms; iv) preliminary recommendations for anti-spamming strategies in Linked Data.

The remainder of this paper is organized as follows: Section 2 presents related work at the intersection of research into spam and Linked Data. Section 3 presents and classifies spammer goals in Linked Data before outlining a number of spamming techniques. In Section 4 we describe a novel sample dataset that embodies the attack techniques presented, while Section 5 proposes preliminary anti-spamming strategies in Linked Data.

Related Work

Efforts have been done for assessing the quality of the data available on the Web. We classify the related work in two categories namely spamming in traditional Web and spamming in Linked Data. For Spamming in LD there are two further relevant types of studies, Data Provenance for Quality Assessment and Data Quality Assessment using Heuristics.

In the area of spamming in the traditional web, Zoltan et al. [START_REF] Gyongyi | Web Spam Taxonomy[END_REF] systematically study spamming techniques targeting the web and organize different web spamming techniques into a taxonomy with two major types, namely 1) Boosting Techniques relying on text fields in which spamming occurs and 2) Link Spamming Techniques, based on incoming and outgoing links. The authors also claim that their work can provide a framework for fighting spamming on the Web and propose a spam taxonomy used to define countermeasures. We-bID 11 , an early initiative by Brickley and Berners-Lee, aims at uniquely identify a person, a company, or any agent or organisation on the Web relying on the FOAF+SSL authentication scheme 12 . This unique ID might help identifying malicious attacks or spamming activity. Machine learning techniques, such as Bayesian classifiers [START_REF] Zdziarski | Ending spam: Bayesian Content Filtering and the Art of Statistical Language Classification[END_REF][START_REF] Dong | Bayesian Chinese Spam Filter Based on Crossed N-Gram[END_REF] and neural networks [START_REF] Rothwell | Intelligent SPAM Detection System Using an Updateable Neural Analysis Engine[END_REF][START_REF] Wu | Behavior-based Spam Detection Using a Hybrid Method of Rule-Based Techniques and Neural Networks[END_REF][START_REF] Stuart | A Neural Network Classifier for Junk e-mail[END_REF] are employed with users' feedback and potential spam content as inputs. Taudgian [START_REF] Trudgian | Spam Classification Using Nearest Neighbour Techniques[END_REF] discusses email spam classification methods such as neural networks, Support Vector Machine (SVM)classifiers, Nave Bayesian (NB) classifiers and J48 classifiers. Spam blocking in blogs is discussed by Mishne et al. [START_REF] Mishne | Blocking Blog Spam with Language Model Disagreement[END_REF].

Spamming in Linked Data faces additional challenges compared to the traditional Web. In a blog post titled "Linked Data Spam Vectors" 13 , Davis discusses a number of attack vectors for spammers in Linked Data (see Section 3). In [START_REF] Hartig | Using Web Data Provenance for Quality Assessment[END_REF] Hartig and Zhao propose a strategy for using provenance of Web data for assessing its quality. Their three-staged approach for assessment consists of 1) provenance element collection, 2) decision of influence of elements on the assessment and 3) function application for quality calculation. Provenance elements collected at first stage and their relationships amongst each other are useful for finding the provenance information for example "whether specific provenance element is created by the actual creator of specific data item or not" [START_REF] Hartig | Using Web Data Provenance for Quality Assessment[END_REF]. In their work they consider information quality (IQ) as collective value of multiple information quality criteria, e.g accuracy, completeness and timeliness as proposed by [START_REF] Naumann | Quality-Driven Query Answering for Integrated Information Systems[END_REF]. In the domain of information quality criteria, Lee et al. [START_REF] Lee | AIMQ: a Methodology for Information Quality Assessment[END_REF] propose a quality assessment methodology that measures IQ whereas Bobrowski et al [START_REF] Bobrowski | A Homogeneous Framework to Measure Data Quality[END_REF] propose an assessment strategy using questionnaires. Detecting malicious data can be difficult when a large amount of triples from a spammer seem to be useful. Motro and Rakov propose an automated method to access the evaluation of reliability and completeness of different data sources [START_REF] Motro | Estimating the Quality of Databases[END_REF]. A prediction algorithm used to find and calculate the response times of Web data sources is proposed by Gruser et al. [START_REF] Gruser | Learning Response Time for Websources Using Query Feedback and Application in Query Optimization[END_REF]. Ballou et al. introduce a quantitative method for assessing the measurement and calculation for the timeliness of data which is based on provenance-related knowledge [START_REF] Ballou | Modeling Information Manufacturing Systems to Determine Information Product Quality[END_REF]. The WIQA 14 Information Quality Assessment Framework proposed by Bizer et al., is a collection of software components that deliver quality assessment guidelines for filtering information available on the Web. The WIQA framework is developed to fulfill three ba-sic requirements namely 1) flexible representation of information together with quality-related meta-information, 2) support for different information filtering policies, and 3) explaining filtering decisions. W3C established the Provenance Incubator Group 15 to create an up-to-date roadmap in the area of provenance in Semantic Web for standardization efforts. The group discusses the importance of provenance and defines the requirements for provenance in the Web architecture.

Bizer et al. [START_REF] Bizer | Quality-driven Information Filtering Using the WIQA Policy Framework[END_REF] classify Data Quality Assessment using Heuristics into three main categories based on the type of information used as quality indicators, namely 1) Content-based Heuristics which use information to be assessed itself, 2) Context-based Heuristics which rely on meta-information along with the circumstances and conditions in which information was originated and 3) Ratingbased Heuristics which rely on number of factors including ratings about information, sources of information, and/or the credibility of data providers. Heath and Bizer [START_REF] Heath | Linked data: Evolving the Web Into a Global Data Space[END_REF] discuss the problem of accessing and improving quality on the client side and suggest that, after data quality on the web has been assessed based on any of the aforementioned heuristic, it can be ranked, fused or filtered according to the requirements.

Type of Attacks

In this section we analyse hypothetical spam attacks to the Web of Data. Although we do not provide a comprehensive assessment of threats, we raise awareness on spamming, as the issue might play a relevant role in the uptake of Linked Data. We start by listing spammer goals in the context of Linked Data. We then provide a list of "spam vectors" 13 , i.e. techniques to introduce spam at RDFlevel. Finally, we describe how spammers might introduce these vectors in the Web of Data infrastructure.

Spammer Goals in Linked Data

The ongoing evolution of the Web of documents into the the Web of Data preserves two fundamental features that might ease the task of Linked Data spammers: first, the open world assumption still holds and second, the cost of the infrastructure to publish and consume triples has not significantly raised. The ultimate goal does not change either, as spammers still aim at providing unsolicited content to users. Our assumption is that, being Linked Data part of the Web, spammer goals replicate well-known observed and studied patterns. We thus adapt and extend the taxonomy proposed in [START_REF] Gyongyi | Web Spam Taxonomy[END_REF] for the context of spam in Linked Data: Application pollution. Linked Data applications use the Web of Data as information source. If spammers infect this dataspace, application results might be polluted with malicious content, thus delivering spam to end users directly inside applications.

Improve ranking. Spammers focus on improving the ranking of malicious resources on search engines, by creating triples containing malicious literal values (to influence term-based metrics), or by creating fake external links to the resource, thus trying to influence algorithms that compute scores according to link information. Hiding. Spammers must hide malicious content, trying to outsmart spam protection techniques.

Spam Vectors

To achieve the objectives described above, Semantic Web spammers necessarily need to deal with the RDF datamodel and Linked Data patterns. Triple-level and HTTP-related operations are therefore required to introduce pollution and achieve the desired results. A number of these Linked Data Spam Vectors have already been described 13 . We categorize these spam vectors in three groups and discuss their implications on Linked Data actors. Besides, we add four new attacks, misleading dataset description, inverse-functional property cloning, presentation knowledge pollution and malicious subclassing.

1. Content contamination vectors. Spammers might pollute Linked Data by introducing malicious information at triple level, typically exploiting popular properties of well-known vocabularies. The most relevant threats might origin from the following attacks:

False labelling. It consists in adding rdfs:label triples containing spam in literals. The rdfs:label property provides a user-friendly label meant to be displayed by applications. Spammers exploit this common practice, to take control of prominent areas of Linked Data application UIs, thus increasing spam effectiveness. A similar attack could target rdfs:comment property, thus leading to "False commenting".

example : Motorola rdfs : label " BUY CHEAP GRAVIA " @en .

Listing 1.1: False labeling example

Misattribution. The dc:creator property might be used to associate malicious statements to unaware authors (that could be people, organizations or services), as in Example 1.2.

: q1 a bibo : Quote ; bibo : content " I buy REPLICA WATCHES on replicaking . com "; dc : creator " Tim Berners -Lee ".

Listing 1.2: Misattribution example

Schema pollution In this case instances are not polluted and contain therefore clean data. Spammers add spurious content inside the schema declaration. For instance, a spammer might publish a polluted copy of a well known vocabulary, publish it with a deceiving URI and pollute with the latter services such as prefix.cc 16 . The attack directly targets application UIs, as spammers use it to pollute triple representation. The example in Figure 1.3 contains a portion of a polluted FOAF schema.

The spammer created a semantically identical schema, and added spam inside rdfs:labels. Listing 1.6: The Fresnel format :nameFormat overrrides foaf:name label with spam while :knowsFormat appends a spam string after each contact.

Link poisoning vectors. A certain number of spam techniques in Linked

Data rely on links to external resources.

Identity assumption consists in associating a malicious resource to misleading owl:sameAs properties, thus associating spam to informative entities. Applications that heavily rely on equivalence links might be polluted during the identity resolution phase. Heuristics must be introduced to mitigate the issue on the client side.

example : Amazon owl : sameAs < http : // 85 . 12 2. 5. 6 5/ gravia >.

Listing 1.7: Identity assumption example.

Inverse-functional property cloning Using owl:sameAs is not the only way to determine that two URIs identify the same real-world resource.

Inverse functional properties, coupled with simple reasoning determine the same result (e.g. ISBN code for a book, social security ID for people, etc.). Spam might be introduced in datasets by associating copies of inverse-functional properties to malicious resources. These resources will be considered identical to the original entity by reasoners and entity smushing heuristics (Example 1.8).

timbl : i a foaf : Person ; foaf : homepage < http :// www . w3 . org / People / Berners -Lee > ; foaf : name " Tim Berners -Lee ".

ex : person_id3423 a foaf : Person ; foaf : homepage < http :// www . w3 . org / People / Berners -Lee > ; foaf : name " Buy GRAVIA at graviamaster . com ".

Listing 1.8: Inverse-functional property cloning.

Misdirection. This type of attack is one of the simplest: spammers change URIs in triples, pointing to malicious content. As seen for other attacks, popular properties might be affected (see Example 1.9). Resource interlinking via the rdfs:seeAlso property can be polluted, too, thus perturbing link traversal operations such as follow-your-nose navigation or introducing undesired triples while crawling the Web of Data.

timbl : i foaf : depiction < http :// i . imgur . com /15 dr2 . jpg > .

Listing 1.9: Misdirection example.

Data URI Embedding Spammers may include malicious data in triples exploiting the data URI scheme19 in literals. At rendering time, applications will decode the base64-encoded content and display malicious messages. The example in Figure 1.10 includes a malicious link gravia that will be included in the HTML rendering of the triple.

example : Amazon rdfs : seeAlso < data : text / html ; charset = utf -8; base64 ,

P G E g a H J l Z j 0 i a H R 0 c D o v L 2 d y Y X Z p Y W 1 h c 3 R l c i 5 j b 2 0 i P m d y Y X Z p Y T w v Y T 4 = >
Listing 1.10: Data URI Embedding example.

3. Non-triple-based attacks Threats might origin from Linked Data features beyond RDF triples, such as resource dereference mechanism and reasoning.

Bait and switch This attack exploits content negotiation mechanism to serve spam. An attacker might provide clean content or spam according to the value of the Accept: HTTP header (e.g. spam when RDF is needed and good data when HTML is requested, or vice-versa). This attack shows that application developers must never take for granted that HTML triple representation matches RDF serializations.

Table 1 summarises the impact of spam vectors on common operations performed by applications that consume Linked Data. Although all attacks are aimed at delivering spam to users (therefore all impacting on the user interface), the table includes only direct impacts. The generic term "link traversal" includes follow-your-nose browsing, crawling and on-the-fly resource dereferencing. Identity resolution include smushing heuristics.

Linked Data Infrastructure Aggressions

Spammers must introduce the spam vectors described in Section 3.2 in the Web of Data. Such operation might be achieved either with well-known techniques (e.g. DNS spoofing), or with aggressions specifically tailored to Web of Data actors, from dataset providers to end-user applications. The non-exhaustive list of attacks below describes the latter category of aggressions:

Hub pollution. It consists in registering fake URIs for well-known schemas on hubs such prefix.cc, schemapedia.com, LOV20 , etc. Polluting services such sameas.org or semantic web search engines 21,22 is another realist threat.

Proposed Strategies

We propose three categories of anti-spam techniques for Linked Data:

Techniques that require actions by data creators. The anti-spam process starts from the creator of the data. When data creators follow some simple precautions, they protect their published data from unauthorized modifications. Examples of these precautions:

-Ensuring data quality. Spamming in Linked Data is highly related with the wider issue of data quality. For example, the use of "dummy" URIs (for example http://examples.com/Paris) can cause harmful problems for data consumers, as spammers might register similar domain names, leading users to malicious sites. -Signing data. Declaring the data author can help a lot in detecting spam. This declaration can be done using the Named Graph data model [START_REF] Carroll | Named Graphs[END_REF]. Using digital signatures with this declaration prevents attackers from modifying the data or impersonating the author through the identity assumption techniques. Techniques that require actions during data delivery. Adopted at delivery time, these strategies help detect illegal modifications on data. Some examples of strategies that can be applied at this level:

-Rating-based techniques for calculating reputation. Using provenance information combined with ratings from users could help providers detecting the trustworthiness of data sources. Many techniques compute trust values that benefit from provenance information. For example, the EigenTrust Algorithm [START_REF] Sepandar | The Eigentrust Algorithm for Reputation Management in P2P Networks[END_REF] is a well-known distributed algorithm for calculating trust based on PageRank. Such distributed techniques also help cooperation between data providers and favour the exchange of information about malicious data sources, thus giving cleaner results to users. -Link content analysis techniques. These techniques are used for separating useful web pages from spam in the traditional web by calculating the similarity between the content of the page that contains the link and the refereed page. Such techniques can be used in Linked data to detect spam that uses misdirection spamming techniques. Techniques that require actions by data consumers. These techniques are used when consumers query or use triples and they are embedded in Linked Data applications. In addition to client-side anti-spamming techniques designed for the traditional web, the following strategies can be used:

-Subjective Rating-based techniques for calculating trust. Reputation calculation techniques that we suggested for data providers can only detect obvious malicious behaviour, i.e. universally recognized spam. Content might be interpreted as spam according to the user and the current context whereas in specific contexts, spam might be considered as good content by some users. Thus, mechanisms that calculate subjective and local trust values are more suitable. As an example, "Alignment-Based Trust" [START_REF] Atencia | Alignment-Based Trust for Resource Finding in Semantic P2P Networks[END_REF] is a mechanism for calculating subjective and local trust values depending on provenance in addition to alignments and user feedback. -Context-based heuristic techniques. These techniques, suggested in [START_REF] Heath | Linked data: Evolving the Web Into a Global Data Space[END_REF], rely on triple meta-information (e.g circumstances in which the data was created). This data is used to decide whether to trust the triples. Heuristics include, for example, preferring product information released by the manufacturer rather than the vendor.

Conclusion

As the adoption of Linked Data by end user applications becomes a reality, the Semantic Web community begins to face "real world" issues such as performance, dataset reliability, data quality, peak load, etc. Spamming might become a nontrivial problem to tackle. In this paper we analyse the risk of spam in the Web of Data. Having provided a formal definition of spam in the Web of Data, we discuss a taxonomy of Linked Data attacks, showing how spammers might profit from the Web of Data paradigm. We list techniques that spammers could use to pollute Linked Data with undesired content and we provide examples in a spam dataset published online, before proposing strategies to protect linked datasets from spamming attacks. More specifically, we underline the need for further work on trust and provenance in the Web of Data. Future work would target an assessment of the current state of spam in Linked Data, in order to establish a baseline against which any increases in spam can be measured. This may in turn reveal additional spam vectors for which mitigating strategies should be proposed. Implementing the suggested best practises for spam protection will also lead to further analysis and refinements.

  Misleading dataset description. VoID descriptions 17 associated to datasets favour data discovery and help users and applications identify the right data. Deceiving VoID descriptions might be associated to malicious datasets, thus cheating Linked Data consumers. The attack undermines data discovery, if this procedure relies on dataset metadata. Link traversal is affected, as techniques might rely on choosing target datasets on the fly, according to VoID descriptions. The example below states that the :graviaMaster dataset contains triples about computer science publications.

	be the dataset provider, application developers or third-party providers.
	(Example 1.6). Applications adopting Fresnel might end up with pol-
	luted results, even if instances and schemas are not, as the attack is
	performed at presentation level.
	: nameFormat rdf : type fresnel : Format ;
	fresnel : p r o p e r t y F o r m a t D o m a i n foaf : name ; foaf : Person a owl : Class ; rdfs : label " Buy GRAVIA at graviamaster . com "; fresnel : label " This person buys GRAVIA on graviamaster . com ".
	: knowsFormat rdf : type fresnel : Format ; Listing 1.3: Schema pollution example fresnel : p r o p e r t y F o r m a t D o m a i n foaf : knows ;
	fresnel : prop ertyForm at
	[ fresnel : contentAfter " loves graviamaster . com !"].
	Presentation knowledge pollution. RDF resources might be associated
	to presentation-level information. Fresnel 18 rendering engines are backed
	by a vocabulary including presentation-level concepts for RDF. In Fres-
	nel, Lens components select and filter information while Formats define
	how to present data. Spammers might create malicious Fresnel declara-
	tions and associate this data to meaningful triples, since Fresnel spec-
	ification does not explicitly say who must provide this data -it could

: graviaMaster a void : Dataset ; foaf : homepage < http :// www4 . wiwiss . fu -berlin . de / dblp / all >; dcterms : subject < http :// dbpedia . org / resource / Computer_science >; dcterms : subject < http :// dbpedia . org / resource / Proceedings >.

Listing 1.4: Misleading dataset description example.

Malicious subclassing. Simple reasoning processes might generate undesired results due to RDFS/OWL-based attacks. Attackers explicitly targeting reasoning services might design polluted inference chains, e.g. associating to malicious classes a number of regular classes, thus determining reasoning pollution (Example 1.5).

gm : GraviaBuyer a owl : Class ; foaf : homepage < http :// graviamaster . com / >; rdfs : label " A class for premium GRAVIA customers ".

foaf : Person rdfs : subClassOf gm : GraviaBuyer .

Listing 1.5: Malicious subclassing example.

Table 1 :

 1 Spam vectors implications on Linked Data application tasks.Crawler pollution. Linked Data applications that rely on locally-stored, precrawled data might be affected by malicious content fetched from the Linked Data Cloud. Crawlers can be deceived by fetching data from malicious seeds, as spam can be added to the cloud by adding polluted seeds to services such as Ping the Semantic Web 23 . Thus, crawlers requesting a list of recently updated resources, will end up fetching spam. Malicious RDFa content. As seen in Section 3.1, influencing search engine ranking is a primary goal for spammers, that might stockpile malicious RDFa metadata in pages, to deceive search engine algorithms. SPARQL injection As for SQL injection, poorly conceived Linked Data applications (or SPARQL client libraries) might suffer from this kind of attack if query sanitation is not implemented.We provide a sample dataset 24 containing malicious triples that could be used to evaluate the resilience of Linked Data applications or to train spam filters.The dataset is the polluted version of a fraction of the Billion Triple Challenge 2012 Dataset 25 . More specifically, we chose the 1-hop expansion "Timbl crawl", a crawl seeded with Tim Berners Lee's foaf profile, and we applied the spam vectors described in Section 3.2. The resulting dataset contains approximately 16k triples (spam triples account for 4% of dataset size). The dataset includes samples of Content contamination vectors and Link poisoning vectors. Extract of the datasets are shown in the examples included in Section 3.2.

		Link traversal	Identity resolution	Vocabulary matching	Reasoning	Data discovery	UI
	False Labeling						X
	Misattribution						X
	Schema pollution			X			X
	Misleading VoID	X				X
	Malicious subclassing				X
	Presentation knowledge						X
	pollution
	Identity assumption	X	X
	IFP cloning		X		X
	Misdirection	X
	Data URI Embedding						X
	Bait and switch						X
	Gaining control of popular namespaces. Attacks let spammers gain con-
	trol of popular namespaces, thus introducing malicious content during given
	time windows only.
	4 Linked Data Spam: A Sample Dataset

http://www.w3.org/wiki/WebID

http://www.w3.org/wiki/Foaf\%2Bssl

http://blog.iandavis.com/2009/09/21/linked-data-spam-vectors/

http://www4.wiwiss.fu-berlin.de/bizer/wiqa/

http://www.w3.org/2005/Incubator/prov/

http://prefix.cc

http://semanticweb.org/wiki/VoID

http://www.w3.org/2005/04/fresnel-info/manual/

http://tools.ietf.org/html/rfc2397

http://labs.mondeca.com/dataset/lov/

http://sindice.com

http://watson.kmi.open.ac.uk/WatsonWUI


Paola Goatin
email: paola.goatin@inria.fr

Matthias Mimault
email: matthias.mimault@inria.fr

THE WAVE-FRONT TRACKING ALGORITHM FOR HUGHES' MODEL OF PEDESTRIAN MOTION *

Keywords: Macroscopic pedestrian flow models, conservation laws, eikonal equation, wavefront tracking, finite volume schemes. AMS subject classifications. 35L65

We code the wave-front tracking algorithm for Hughes' model of pedestrian motion with generalized running cost. This model displays a non-classical dynamic at the splitting point between the two directions of motion. The wave-front tracking scheme provides us with reference solutions to test numerically the convergence of classical finite volume schemes, which do not treat explicitly the dynamics at the turning point.

1. Introduction. We consider a generalization of the macroscopic pedestrian flow model introduced by Hughes [START_REF] Roger | A continuum theory for the flow of pedestrians[END_REF]. The pedestrian density ρ = ρ(t, x) is assumed to evolve according to the following system consisting in a scalar conservation law expressing mass conservation coupled with an eikonal equation giving the preferred direction depending on the density profile, which in the one dimensional case read:

ρ t -ρv(ρ) φ x |φ x | x = 0, (1.1a
)

|φ x | = c(ρ), (1.1b)
in the spatial domain Ω = ]-1, 1[. The above equations must be completed with homogeneous (weak) Dirichlet boundary conditions at x = ±1, which represent the exits locations ρ(t, -1) = ρ(t, 1) = 0, (1.2a) φ(t, -1) = φ(t, 1) = 0, (1.2b) and an initial density profile ρ(0, •) = ρ 0 ∈ BV(R). Above, x ∈ Ω is the space variable, t ≥ 0 is the time, ρ = ρ(t, x) ∈ [0, 1] is the (normalized) crowd density, c = c(ρ) is the cost function, v(ρ) = (1 -ρ) is the mean velocity and we set f (ρ) = ρv(ρ) = ρ(1 -ρ). We assume that c : [0, 1[ → [1, +∞[ is a smooth function such that c(0) = 1 and c ′ (ρ) ≥ 0 for ρ ∈ [0, 1[. Recall that the literature usually proposes the choice

c(ρ) = 1 v(ρ) (1.3)
as in [START_REF] Di Francesco | On the Hughes' model for pedestrian flow: the one-dimensional case[END_REF][START_REF] Roger | A continuum theory for the flow of pedestrians[END_REF][START_REF]The flow of human crowds[END_REF]. We observe that (1.1a) can be rewritten as ρ t -(f (ρ) sgn(φ x )) x = 0, (1.4) and the unique viscosity solution to the Dirichlet problem (1.1b), (1.2b) is given by the value function of the corresponding control problem with discontinuous coefficient c(ρ), i.e.

φ(t, x) =        x -1
c (ρ(t, y)) dy if x ≤ ξ(t),

1 x c (ρ(t, y)) dy if x ≥ ξ(t), (1.5)
where ξ(t) is implicitly defined by the identity

ξ(t) -1 c (ρ(t, y)) dy = 1 ξ(t)
c (ρ(t, y)) dy.

(1.6) Therefore, equation (1.1a) can be written as a scalar conservation law with discontinuous space-time dependent flux:

ρ t + F (t, x, ρ) x = 0, (1.7)
where F (t, x, ρ) = sgn (x -ξ(t)) f (ρ). Observe that the position of the discontinuity is not a priori fixed, as assumed in previous results on conservation laws with discontinuous fluxes (see for example [START_REF] Karlsen | Convergence of the Lax-Friedrichs scheme and stability for conservation laws with a discontinous space-time dependent flux[END_REF] and references therein), but depends non-locally on ρ itself. Therefore, known convergence results for finite volume schemes do not apply in this setting.

From the mathematical point of view, problem (1.1) presents a non trivial coupling between a scalar conservation law and an eikonal equation, that poses several challenging questions concerning existence, uniqueness, numerical approximation and construction of the solutions. Some preliminary results concerning properties of solutions have been obtained recently in [START_REF] Amadori | The one-dimensional Hughes model for pedestrian flow: Riemann-type solutions[END_REF][START_REF] El-Khatib | On entropy weak solutions of Hughes' model for pedestrian motion[END_REF]. In particular, they provide a notion of entropy weak solutions, a discussion on their qualitative behavior, and an algorithm to construct locally in time a self-similar solution in a neighborhood of the turning point x = ξ(t) (see [START_REF] Amadori | The one-dimensional Hughes model for pedestrian flow: Riemann-type solutions[END_REF]Theorem 1]).

Here we are interested in computing numerically the weak solutions of the (nonregularized) hyperbolic problem (1.1). As remarked above, classical finite volume techniques for discontinuous fluxes do not apply here due to the fact that the discontinuity location is not a-priori fixed, but depends non-locally on the solution itself. Nevertheless, it appears that a direct application of classical shemes allows to recover the exact solutions. Since these are not known explicitly, the convergence of the finite volume schemes is numerically tested on accurate approximations of entropy weak solutions computed using the wave-front algorithm (for a detailed review of the method we refer to [START_REF] Holden | Front tracking for hyperbolic conservation laws[END_REF]).

2. Basic properties of solutions. For sake of simplicity, we refer to the initialboundary value problem

ρ t + F (t, x, ρ) x = 0, |φ x | = c(ρ), x ∈ Ω , t > 0, ρ(0, x) = ρ 0 (x), x ∈ Ω ρ(t, -1) = ρ(t, 1) = 0, φ(t, -1) = φ(t, 1) = 0, t > 0, (2.1)
Following [START_REF] El-Khatib | On entropy weak solutions of Hughes' model for pedestrian motion[END_REF], we look for the following class of solutions. Definition 2.1. (Entropy Weak Solutions).

A function ρ ∈ C 0 R + ; L 1 (Ω) ∩BV (R + ×Ω; [0, 1]
) is an entropy weak solution of the initial-boundary value problem (2.1) if the following Kružkov-type entropy inequality holds for all k ∈ [0, 1] and all test functions

ψ ∈ C ∞ c (R × Ω; R + ): 0 ≤ +∞ 0 1 -1 (|ρ -k|ψ t + Φ(t, x, ρ, k)ψ x ) dx dt+ 1 -1 |ρ 0 (x) -k|ψ(0, x) dx + sgn(k) +∞ 0 (f (ρ(t, 1-)) -f (k)) ψ(t, 1) dt + sgn(k) +∞ 0 (f (ρ(t, -1+)) -f (k)) ψ(t, -1) dt + 2 +∞ 0 f (k)ψ (t, ξ(t)) dt. (2.2)
Above, Φ(t, x, ρ, k) = sgn(ρ -k) (F (t, x, ρ) -F (t, x, k)) and the boundary conditions are intended in weak form as in [START_REF] Bardos | First order quasilinear equations with boundary conditions[END_REF]. In particular, the traces of the solution at the boundary points must satisfy

f (ρ(t, -1+)) ≥ f (k), for all k ∈ [0, ρ(t, -1+)], f (ρ(t, 1-)) ≥ f (k), for all k ∈ [0, ρ(t, 1-)].
This in particular implies ρ(t, -1+) ≤ 1/2 and ρ(t, 1-) ≤ 1/2. Besides, by taking suitable test functions ψ vanishing along x = ξ(t), it is easy to recover the Rankine-Hugoniot condition

f ρ + + f ρ -= ξ(t) ρ + -ρ -, (2.3)
where we have denoted by ρ + = ρ + (t) = ρ (t, ξ(t)+) and ρ -= ρ -(t) = ρ (t, ξ(t)-) the right and left traces of ρ at x = ξ(t). We remark here that if ρ(t, •) is continuous at x = ξ(t), then (2.3) gives f (ρ (t, ξ(t))) = 0 and therefore ρ (t, ξ(t)) ∈ {0, 1}.

For further properties of entropy weak solutions, such as maximum principle, we refer the reader to [START_REF] El-Khatib | On entropy weak solutions of Hughes' model for pedestrian motion[END_REF].

3.

The Riemann solver at the turning point. The argument proposed in [START_REF] Amadori | The one-dimensional Hughes model for pedestrian flow: Riemann-type solutions[END_REF] is based on the observation that, due to finite wave propagation speed, for every fixed t ≥ 0 the solution ρ(t, x) is well defined away from the turning point ξ = ξ( t) for t > t sufficiently small, say on [-1, ξ -δ) ∪ ( ξ + δ, 1] for some δ > 0. Therefore, the following quantity is well defined

1 ξ+δ - ξ-δ -1 ∂ t [c(ρ(t, y))]dy =: Ψ * .
Moreover, let us assume that the the function ρ( t, x) is constant in a left and right neighbors of ξ, let's say

ρ( t, x) = ρ L if ξ -2δ < x < ξ, ρ R if ξ < x < ξ + 2δ. (3.1)
Assuming Ψ * to be constant for small times t > t, the solution around the turning point will be self-similar, behaving as a solution of a Riemann problem. This assumption is met when there are no interacting patterns in the whole interval [-1, 1].

Therefore, for small times t > t we have

Ψ[ρ] = Ψ * + ξ+δ ξ(t) - ξ(t) ξ-δ ∂ t [c(ρ(t, y))]dy. (3.2)
The term Ψ * depends on ρ( t, •) in a non-local way and may range all over R, independently of ρ L and ρ R . The solution around ξ will be classified according to the value of Ψ * .

Theorem 3.1. (Riemann Solver at ξ = ξ( t)). Assume that (3.1) and (3.2) hold, then a self-similar solution around ( t, ξ) is defined locally in time as follows:

1

. If ρ L > ρ R , the following cases occur. 1a) If Ψ * < f (ρ R ) + f (ρ L ) ρ R -ρ L [c(ρ R ) + c(ρ L )], (3.3)
then there exists a unique intermediate value ρ M , with ρ L > ρ M > ρ R , such that the solution is given by the turning curve ξ followed by a rarefaction between ρ M and ρ R . 1b) If

f (ρ R ) + f (ρ L ) ρ R -ρ L [c(ρ R ) + c(ρ L )] ≤ Ψ * ≤ -v(ρ L )(1 + c(ρ L )) -v(ρ R )(1 -c(ρ R )), (3.4
)

then a unique intermediate value ρ M ∈ [0, ρ R
] exists, such that the solution is given by the turning curve ξ followed by a shock between ρ M and ρ R . If the equality holds in the r.h.s. of (3.4), then ρ M = 0: vacuum appears between the turning point and the shock.

1c) If -v(ρ L )(1 + c(ρ L )) -v(ρ R )(1 -c(ρ R )) < Ψ * < v(ρ R )(1 + c(ρ R )) + v(ρ L )(1 -c(ρ L )), (3.5)
then the solution is given by a shock of speed ρ L -1 followed by ξ and by a shock of speed 1 -ρ R , the intermediate state around

ξ being ρ M = 0. 1d) Finally if Ψ * ≥ v(ρ R )(1 + c(ρ R )) + v(ρ L )(1 -c(ρ L )), (3.6)
then the solution is given by a shock between ρ L and ρ M ∈ [0, ρ R ] followed by ξ. If the equality holds in (3.6),

then ρ M = 0, otherwise ρ M > 0. 2. If ρ L < ρ R , the following cases occur. 2a) If Ψ * ≤ -v(ρ L )(1 + c(ρ L )) -v(ρ R )(1 -c(ρ R )), (3.7)
then a unique intermediate value ρ M ∈ [0, ρ L ] exists, such that the solution is given by ξ followed by a shock between ρ M and ρ R . If the equality holds in (3.7), then ρ M = 0: vacuum appears between the turning point and the shock.

2b) If -v(ρ L )(1 + c(ρ L )) -v(ρ R )(1 -c(ρ R )) < Ψ * < v(ρ R )(1 + c(ρ R )) + v(ρ L )(1 -c(ρ L )), (3.8)
then the solution is given by a shock of speed ρ L -1 followed by ξ and by a shock of speed 1 -ρ R , the intermediate state being

ρ M = 0. 2c) If v(ρ R )(1 + c(ρ R )) + v(ρ L )(1 -c(ρ L )) ≤ Ψ * ≤ f (ρ R ) + f (ρ L ) ρ R -ρ L [c(ρ R ) + c(ρ L )], (3.9)
then the solution is given by a shock between ρ L and ρ M ∈ [0, ρ L ], followed by the turning curve ξ. If equality holds in the l.h.s. of (3.9), then

ρ M = 0, otherwise ρ M > 0. 2d) Finally if Ψ * > f (ρ R ) + f (ρ L ) ρ R -ρ L [c(ρ R ) + c(ρ L )], (3.10)
then there exists a unique intermediate value ρ M , with ρ R > ρ M > ρ L , such that the solution is given by a rarefaction between ρ L and ρ M followed by the turning curve ξ.

If ρ

L = ρ R = ρ * , the following cases occur. 3a) If Ψ * ≤ -2v(ρ * ), (3.11)
then a unique intermediate value ρ M ∈ [0, ρ * ] exists, such that the solution is given by the turning curve ξ followed by a shock between ρ M and ρ R . If the equality holds in (3.11), then ρ M = 0: vacuum appears between the turning point and the shock.

3b) If -2v(ρ * ) < Ψ * < 2v(ρ * ), (3.12)
then the solution is given by a shock of speed ρ * -1 followed by ξ and by a shock of speed 1 -ρ * , the intermediate state across

ξ being ρ M = 0. 3c) Finally if Ψ * ≥ 2v(ρ * ), (3.13)
then the solution is given by a shock between ρ L and ρ M ∈ [0, ρ R ] followed by ξ. If equality holds in (3.13), then ρ M = 0, otherwise ρ M > 0. The proof follows closely the one of [1, Theorem 1] and it is therefore omitted.

Numerical schemes.

4.1. The wave-front tracking scheme. The wave-front tracking technique for classical scalar conservation laws consists in constructing piece-wise constant exact solutions of an approximated problem with piecewise constant initial datum and piecewise linear flux f ν , coinciding with f = ρv(ρ) on the mesh

M ν = {ρ ν i } 2 ν i=0 ⊂ Ω defined by M ν = 2 -ν N ∩ [0, 1]
for ν ∈ N, ν > 0. We refer the reader to [START_REF] Bressan | Hyperbolic systems of conservation laws[END_REF][START_REF] Holden | Front tracking for hyperbolic conservation laws[END_REF] for further details. We describe here the extension of the method to the case of the coupled problem (1.1).

Let ρ ν 0 be a piecewise constant function defined by

ρ ν 0 = j∈Z ρ ν 0,j χ ]xj-1,xj ] with ρ ν 0,j ∈ M ν ,
which approximates ρ 0 in the sense of the strong L 1 topology, that is

lim ν→∞ ρ ν 0 -ρ 0 L 1 (Ω) = 0,
and such that TV(ρ ν 0 ) ≤ TV(ρ 0 ). Above, we set x 0 = ξ 0 , which is calculated from the cost balance equation (1.6) at t = 0:

ξ0 -1 c (ρ ν 0 (y)) dy = 1 ξ0 c (ρ ν 0 (y)) dy,
that reduces to j≤0 ρ ν 0,j (x j -x j-1 ) = j>0 ρ ν 0,j (x j -x j-1 ).

Observe that we may have ρ ν 0,0 = ρ ν 0,1 . For small times t > 0, a piecewise approximate solution (ρ ν , ξ ν ) to (2.1) is constructed piecing together the solutions to the Riemann problems

       ∂ t ρ + ∂ x (sgn(x -ξ 0 )f ν (ρ)) = 0, ρ(0, x) = ρ 0 if x < ξ 0 , ρ 1 if x > ξ 0 , ξ(ρ + -ρ -) = Ψ[ρ],        ∂ t ρ + ∂ x (sgn(x j -ξ 0 )f ν (ρ)) = 0, ρ(0, x) = ρ j if x < x j , ρ j+1 if x > x j , j = 0. (4.1)
Solving the problem by front tracking replaces the regular rarefaction fronts by rarefaction fans of constant values ρ ν j , j = l 1 , . . . , l Nν , such that ρ ν j -ρ ν j-1 = 2 -ν , separated by jump discontinuities moving with speeds λ j = 1 -ρ ν j -ρ ν j-1 , see Fig. 4.1. Note that the solution to the Riemann problem in (4.1), left, is constructed by means of the Riemann solver described previously in Theorem 3.1, where the theoretic value of the intermediate state ρ M is approximated by the closest point of the mesh M ν . This introduces an error in the resolution of the linearized problem, but guarantees that the approximate solution keeps lying on M ν . The (piece-wise constant) speed of the approximated turning curve ξ ν is then computed using the Rankine-Hugoniot equation (2.3). The piecewise constant approximate solution ρ ν constructed above can be prolonged up to the fist time t > 0, where two discontinuities collide, or a discontinuity hits the turning curve ξ ν . In both cases, a new Riemann problem arises and its solution, obtained in the former case with the classical Riemann solver and in the latter by means of Theorem 3.1, allows to extend ρ ν , ξ ν further in time. We point out that the absorbing boundary conditions (1.2a) are taken into account by simply dropping the waves hitting the left and right boundaries. This procedure will provide us with a reference solution to numerically test the convergence of classical finite volume schemes. Even if the theoretical convergence of wave-front tracking approximations to exact solutions of (2.1) makes the object of on-going research, numerical evidence of this convergence can be found in the tests reported in Section 5.2.

The Matlab code used for the numerical tests presented in Section 5 can be downloaded at the following URL: http://www-sop.inria.fr/members/Paola.Goatin/wft.html.

Finite volume schemes.

In this section, we describe the algorithm used in [START_REF] El-Khatib | On entropy weak solutions of Hughes' model for pedestrian motion[END_REF] for numerical simulations of the model (1.1). Finite volume schemes are commonly used to compute numerically solutions of the 2D version of the model, see for example [START_REF] Huang | Revisiting Hughes' dynamic continuum model for pedestrian flow and the developement of an efficient solution algorithm[END_REF][START_REF] Jiang | A reactive dynamic continuum user equilibrium model for bidirectional pedestrian flows[END_REF] and references therein for more details and results.

Here we aim at investigating the behavior of classical schemes near the turning curve, and whether they manage to capture correctly the behavior of the solution constructed via the wave-front tracking algorithm.

Given an initial datum ρ(0, x) = ρ 0 (x) and homogeneous Dirichlet boundary conditions (1.2), we solve (1.1) in an iterative manner at each time step, i.e.

1. Given ρ, solve the eikonal equation (1.1b) by the fast sweeping method, see Section 4.2.1. 2. Given φ, solve the non-linear conservation law (1.1a) using Godunov or Rusanov scheme. The domain [-1, 1] is divided into N uniform cells I j = [x j-1/2 , x j+1/2 ] with centers at points x j = j∆x, with ∆x = 2/N . The explicit algorithm used to generate the approximations ρ n j was introduced by Towers in [START_REF] Towers | Convergence of a difference scheme for conservation laws with a discontinuous flux[END_REF] and is written in conservation form

ρ n+1 j = ρ n j - ∆t n ∆x k n j+ 1 2 h n j+ 1 2 -k n j-1 2 h n j-1 2 , (4.2)
where ∆t n = t n+1 -t n is chosen to satisfy the following CLF condition ∆t n < 0.5 ∆x

max max j f ′ (ρ n j ) , | ξn | .
In the above formula, the coefficient 0.5 is chosen to avoid interactions of ξ with the cell boundaries, and | ξ| is estimated at each time step by deriving the implicit expression (1.6), which gives

ξ(t) c(ρ -) + c(ρ + ) = - ξ(t) -1 c(ρ(t, y)) t dy + 1 ξ(t)
c(ρ(t, y)) t dy.

From the above identity we recover the (sharp) upper bound

| ξn | ≤ 1 2 j (1 -ρ n j -ρ n j+1 ) c(ρ n j ) -c(ρ n j+1 ) .
In (4.2), we set k n j±1/2 = sgn φ n x (x j±1/2 ) , where

φ n x (x j+1/2 ) ≃ φ n (x j+1 ) -φ n (x j ) ∆x .
The numerical flux h n j+1/2 = h(ρ n j , ρ n j+1 ) is chosen to be monotone and consistent, i.e. h(ρ, ρ) = f (ρ) = ρv(ρ). In order to maintain the monotonicity of the scheme, we transpose the arguments when k j+1/2 changes sign, i.e.

h j+ 1 2 =    h (ρ j , ρ j+1 ) if k j+ 1 2 ≥ 0, h (ρ j+1 , ρ j ) if k j+ 1 2 < 0. (4.3)
4.2.1. The Fast Sweeping algorithm [START_REF] Zhao | A fast sweeping method for eikonal equations[END_REF]. Discretization. The method uses a Godunov upwind difference scheme to discretize the partial differential equation at interior points of the domain:

[(φ h j -φ h xmin ) + ] 2 = c(ρ i ) 2 h 2 , j = 2, ..., N -1, (4.4)
where φ h j ≃ φ(x j ) and φ h xmin = min(φ h j-1 , φ h j+1 ) and

(x) + = x, x > 0, 0, x ≤ 0.
Initialization. We assign exact values at boundary grid points x = ±1 to enforce boundary condition φ(±1) = 0. We assign sufficiently large positive values at all other grid points. These points will be updated later.

Iterations. At each grid point x j whose value is not fixed during the initialization, compute the solution of (4.4), denoted by φ, from the current values of its neighbors φ h j±1 and then update φ h j to be the smaller one between φ and φ h j , i.e. φ new j = min(φ old j , φ). We sweep the whole domain with two alternating orderings repeatedly:

(1) j = 1 : N, (2) j = N : 1, and we stop when the fixed error threshold is met.

4.2.2. Godunov scheme. The Godunov scheme [START_REF] Godunov | A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics[END_REF] for a conservation law of type u t + F (u) x = 0 is classically obtained by using the exact solution with piecewise constant initial data. The numerical flux is h(u, v) = F (R(0; u, v)), where R(0; u, v) is the solution of the Riemann problem with left and right states u and v evaluated at x = 0, where a jump on the initial data occurs. The Godunov flux is given by

h(u, v) = min [u,v] F (w) if u ≤ v, max [u,v] F (w) if u ≥ v. (4.5)
We remark that in the case of problem (1.1) an explicit Riemann solver at the sign change interface would require to code all the possible cases detailed in Theorem 3.1, and would be very expensive. Aiming to have just a qualitative representation of the solution, in our computations we force ξ(t n ) to be at the middle of the cell it belongs to at each time step, i.e. ξ(t n ) = x j , for j such that sgn(φ x (x j-1/2 )) > sgn(φ x (x j+1/2 )).

4.2.3. Rusanov scheme. In [START_REF] Towers | Convergence of a difference scheme for conservation laws with a discontinuous flux[END_REF], the author proves convergence of Engquist-Oscher scheme for conservation laws with discontinuous flux. These results can be used in the second step to solve the conservation law. For our simulations we have used a variant introduced by Rusanov [START_REF] Rusanov | The calculation of the interaction of non-stationary shock waves with barriers[END_REF], whose flux is given by

h(u, v) = 1 2 (f (u) + f (v)) + 1 2 max {|f ′ (u)|, |f ′ (v)|} (u -v) , (4.6)
and is known to be robust.

Convergence results.

In this section we provide some numerical tests showing the convergence of the wave-front tracking and finite volumes schemes described in the previous Sections 4.1, 4.2. To this end, we choose an initial datum ρ 0 that gives a non-trivial behavior at the turning curve. In fact, if the solution ρ of (2.1) is continuous at x = ξ(t), that is, ρ(t, ξ(t)-) = 0 = ρ(t, ξ(t)+), we deal with classical solutions on each side of the turning curve, and the convergence is standard.

In the following, we consider the Riemann-type initial datum

ρ 0 (x) = 0 if -1 < x < 0, 0.9 if 0 < x < 1, (5.1)
and the cost function c(ρ) = 1/v(ρ) = 1/(1 -ρ). We run simulations up to time T = 3, so that the whole mass lefts the domain Ω and ρ(T, x) ≡ 0, see Fig.

5.1. Data processing. Wave-front tracking solutions are not defined on a standard cartesian grid in space and time, but rather as constant values on polygonal regions delimited by wave fronts (see Fig. 5.1). In order to compare the approximate solutions obtained via wave-front tracking at different mesh sizes, and finite volume approximations with the wave-front tracking reference solution, we have to convert these data sets to values defined on a reference cartesian grid.

In what follows we denote by X W F T the data obtained from the wave-front tracking procedure, by X W F T the processed data and by X F V those obtained from finite volumes schemes. Values for ρν W F T are obtained by taking the corresponding values of ρ ν W F T at the cartesian grid nodes, see Fig. 5.1. Finally, we operate a L 1 -norm comparison, according to the following formula :

Err(ν, ∆x) = T 0 1 -1 |ρ ν W F T -ρ F V |dxdt = N n=1 J j=1 (ρ ν W F T ) n j -(ρ F V ) n j ∆x∆t n ,
where ν refers to the wave-front tracking mesh size and ∆x denotes the space-mesh size of the cartesian grid used for the finite volume scheme. We remark that the above procedure introduces an approximation error in the computation of the L 1 -error, since

T 0 1 -1 |ρ ν W F T -ρ F V |dxdt = T 0 1 -1 |ρ ν W F T -ρ F V |dxdt.

Convergence of Wave Front

Tracking. The theoretical proof of existence and uniqueness of solutions of (2.1) by means of the wave-front tracking method is currently under investigation. Meanwhile, we can produce numerical evidence of the 5.1. Definition of ρW F T at the point (t F V , x F V ) of the reference cartesian grid: after finding the last interaction time t m ≤ t V F in ρ W F T , one has to compare the positions of the corresponding interfaces x i (t F V ) = x m i + s i (t F V -t m ) with respect to x F V , where s i = 1 -ρ i -ρ i+1 are the speeds of the wave-fronts. Here ρW

x m-1 1 x m-1 2 x t m-1 t m x m 1 x m 2 ρ m-1 1 ρ m-1 2 ρ m-1 3 ρ m-1 4 ρF V x F V t F V t Fig.
F T = ρ m 2 = ρ m-1 2 .
convergence of WFT scheme by showing that the L 1 -error between two subsequent discretization meshes 2 -ν and 2 -ν-1

ǫ ν = ρν+1 W F T -ρν W F T L 1
decreases to zero as ν increases. 1.755e -3 10 2 -10 2.091e -3 11 2 -11 4.305e -4 12 2 -12 4.347e -4 Table 5.1 L 1 -error ǫν for wave-front tracking method between two subsequent discretization meshes 2 -ν and 2 -ν-1 . The comparison is done on a cartesian grid with ∆x = 10 -3 and ∆t = 0.5∆x.

Convergence of finite volume schemes.

Once assessed the convergence of the wave-front tracking scheme, we take as reference "exact" solution the one obtained with density mesh size ε = 2 -ν = 2 -10 , and we compare it to the approximations computed by Godunov and Rusanov schemes for different space mesh sizes, computing the L 1 -norm of the difference. The following Table 5.1 and Fig. 5.3 report the values of the L 1 -error computed on the time interval [0, T ] with T = 1.2, in order to focus on the non-classical behavior of the solution. Indeed, at T = 1.2 vacuum has appeared around the turning point ξ, and the solution has become classical. For a set of space meshes ranging from ∆x = 1/50 to ∆x = 1/1500, we see a clear linear decreasing in logarithmic scale, showing numerically a convergence order of about 0.67 for both Godunov and Rusanov schemes, without an explicit treatment of the solution's behavior at x = ξ(t). Fig. 5.4 shows the profiles of the three numerical approximations in a neighborhood of the turning point. We observe that Godunov scheme displays small oscillations close to x = ξ(t). 5.4. More general initial data. We provide here the results of simulations performed considering a more general initial datum. We have taken as in [START_REF] Di Francesco | On the Hughes' model for pedestrian flow: the one-dimensional case[END_REF]Figure 6] in order to simulate the behavior of three mixed-density groups. We can see that the two finite volume simulations are evolving like the wavefront tracking one, modeling two turning phenomena. We can also observe that the diffusion of Rusanov counterbalances severely Godunov's oscillations.

ρ 0 =        0.8 if -0.8 ≤ x ≤ -0.5, 0.6 if -0.3 ≤ x ≤ 0.3, 0.9 if 0.4 ≤ x ≤ 0.75, 0 elsewhere, (5.2)

Conclusions.

A crowd evacuating a corridor can be modeled by a system of partial differential equations in one space-dimension, coupling a scalar conservation law describing conservation of mass and an eikonal equation assigning the direction of motion depending on the density profile. The system can be rewritten as a scalar conservation law with space-discontinuous flux function, for which the discontinuity location depends non-locally on the density profile.

Since exact entropy weak solutions cannot be computed theoretically for general initial data, we have coded an adapted wave-front tracking scheme, which is reasonably assumed to give a good approximation of problem's solutions. These wave-front tracking approximations are used as reference solutions to show numerically the convergence of classical finite volume schemes, which do not treat explicitly the dynamic at the turning point.

These results offer a sound basis to the use of classical finite volumes schemes for the computation of solutions of Hughes' model in two space dimensions, see for example [START_REF] Huang | Revisiting Hughes' dynamic continuum model for pedestrian flow and the developement of an efficient solution algorithm[END_REF][START_REF] Jiang | A reactive dynamic continuum user equilibrium model for bidirectional pedestrian flows[END_REF].

Fig. 4 . 1 .

 41 Fig. 4.1. Wave-front tracking solution of (2.1) with ρ 0 (x) = 0 for x ∈ ] -1, 0[ and ρ 0 (x) = 0.9 for x ∈ ]0, 1[, and mesh size ∆ρ = 2 -10 . The white curve is the trajectory x = ξ(t).

Fig. 4 . 2 .

 42 Fig.4.2. Density profile at time t = 0.8 with initial density ρ 0 (x) = 0 for x ∈ ] -1, 0[ and ρ 0 (x) = 0.9 for x ∈ ]0, 1[, computed using wave-front tracking scheme with mesh size ∆ρ = 2 -10 . The position of the turning point x = ξ(t) coincides with the first jump discontinuity from the left.

Fig. 5 . 2 .

 52 Fig.5.2. L 1 -error ǫν between two subsequent discretization meshes 2 -ν and 2 -ν-1 , for ν = 5, . . . , 12, corresponding to the initial datum given by (5.1).

Fig. 5 . 3 .Fig. 5 . 4 .

 5354 Fig. 5.3. L 1 -norm of the error in logarithmic scale for mesh sizes ∆x = 1/50, . . . , 1/1500, for Godunov and Rusanov schemes corresponding to the initial datum given by (5.1).

Fig. 5 . 5 .

 55 Fig. 5.5. Wave-front tracking (top), Godunov (middle) and Rusanov (bottom) schemes for ρ 0 given by 5.2. The wave-front tracking mesh is ∆ρ = 2 -10 and the finite volume space step is ∆x = 10 -3 .

Table 5 .

 5 1 and Fig. 5.2 show that the sequence {ρ ν W F T } is a Cauchy sequence in L 1 .

	ν ∆ρ	ǫ ν
	5 2 -5	4.280e -2
	6 2 -6	2.164e -2
	7 2 -7	6.141e -3
	8 2 -8	5.048e -3
	9 2 -9

Table 5 .

 5 2 L 1 -norm of the error for Godunov and Rusanov schemes for (5.1) depending on the space step ∆x, and corresponding convergence order. Above, Err G stands for the error in Godunov scheme, Err R indicates the error for Rusanov flux.

	∆x	Err G	ln(Err G )/ ln(∆x) Err R	ln(Err R )/ ln(∆x)
	1/50	7.24e -2 -0.66	7.44e -2 -0.67
	1/100 4.56e -2 -0.66	4.68e -2 -0.67
	1/250 2.49e -2 -0.66	2.55e -2 -0.67
	1/500 1.52e -2 -0.67	1.55e -2 -0.67
	1/1000 9.03e -3 -0.68	9.12e -2 -0.68
	1/1500 6.66e -3 -0.69	6.62e -3 -0.68

* This research was supported by the ERC Starting Grant 2010 under the project "TRAffic Management by Macroscopic Models"


S B Q Tran

Philippe Marmottant

Pierre Thibault

Fast acoustic tweezers for the two-dimensional manipulation of individual particles in microfluidic channels

Fast acoustic tweezers for the two-dimensional manipulation of individual particles in microfluidic channels S.B.Q. Tran, P. Marmottant, * and P. Thibault † CNRS / Université Grenoble 1, LIPhy UMR 5588, Grenoble, F-38401, France (Dated: November 13, 2012) This paper presents a microfluidic device that implements standing surface acoustic waves in order to handle single cells, droplets and generally particles. The particles are moved in a very controlled manner by the two-dimensional drifting of a standing wave array, using a slight frequency modulation of two ultrasound emitters around their resonance. These acoustic tweezers allow any type of motion at velocities up to few ×10 mm/s while the device transparency is adapted for optical studies. The possibility of automation provides a critical step in the development of lab-on-a-chip cell sorters and it should find applications in biology, chemistry and engineering domains.

The recent progresses in lab on chip technologies have opened numerous possibilities for medical diagnosis and biological tests. One issue is the adaptation of current technologies to microscale for higher integration, cost reduction and parallel processing capabilities, as illustrated by the efforts to develop micro fluorescent activated cell sorters (µFACS) [1,2]. Another issue is the manipulation of individual cells for in situ diagnostics and optical characterization. Surface acoustic wave (SAW) techniques are particularly promising for particle handling as they allow, when combined with a polydimethylsiloxane (PDMS) microfluidic channel, optical access, local actuation and fast response time capabilities.

In this Letter, we describe a device that can move particles down to the size of cells and precisely control their positions in a two-dimensional (2D) acoustic cage. We show that the characteristics of these acoustic tweezers are to be fast (×10 mm/s) and to exert forces that are strong enough to counteract friction from wall, or drag from hydrodynamic flows of reasonable velocities. We present measurements of the particle trajectories obtained for an oscillatory driving motion, so as to understand the dynamics of slippage from the acoustic trap above a threshold velocity. Last, we propose an insight into the forces acting on particles in a microchannel under the action of SAW emission, providing evidence of their 3D action.

Friend et al. [3] have recently drawn a full panorama of the potential offered by acoustic microfluidics based on SAW emission in the case of standing waves (SSAW), propagating waves (PSAW) or both. Using PSAW, Franke et al. have demonstrated the deviation of a continuous flow containing cells at high frequency [2], and of droplets in a water in oil emulsion [4]. Note that when using these pushing forces the final position is not directly controlled because it depends on the surrounding fluid velocity. Using SSAW, Shi et al. were able to force bovine red blood cells particles to form lines [5] and ob- * URL:

http://www-liphy.ujf-grenoble.fr/equipe/dyfcom/ marmottant/Philippe_Marmottant † Electronic address: Pierre.Thibault@ujf-grenoble.fr tained point-wise concentrations [6] of latex beads and E. Coli cells with two interdigitated transducers (IDTs) in an orthogonal arrangement. In this case, it is believed that the observed patterns result from acoustic forces due to SAW leakage in the liquid. These forces pushing the particle towards the pressure nodes, this leads to a situation analog to bulk acoustic wave experiments [7,8]. Wood et al. have also shown line wise [9] and point wise [10] alignments of latex particles using opposite pairs of IDTs, the visualization of particles being obtained through a glass superstrate. In contrast with these experiments where the particles cannot be moved at will on predetermined locations, Meng et al. [11] have described a device where micro-bubbles and breast cancers cells can be transported at will across the width of a microfluidic channel. The major improvement is the use of some phase shift between the two IDTs located on both part of to microfluidic channel to move the standing wave pattern, and hence the particles. Recently Ding et al. [12] have proposed to implement chirped electrodes with a broadband response (in between 18.5 MHz and 37 MHz) to change the wavelength of a 2D standing wave pattern in both directions, and thus entrain particles.

In the present work, we have designed a device that cumulates the advantages of a 2D standing wave pattern to trap particles in some nodal positions and the continuous control of a small phase shift to displace them, staying at the resonance frequency of the device. The experimental setup is schematized on figure 1. The piezoelectric is a 2", 500 µm thick LiNbO 3 single crystal wafer, with X-cut section and Z as the main propagation direction (K 2 = 5.9% in Z direction, and 3.1% in Y direction [13]). Electrodes forming the IDTs are produced by successive metal depositions (Ti/Au, 15 nm/100 nm) on the LiNbO 3 wafer with a standard lift-off process. They comprise 40 fingers electrode pairs with a constant pitch λ of 100 µm. The microfluidic channel, 50 µm deep, is fabricated in PDMS with soft-lithography using moldreplica techniques. It contains a flow focusing geometry [14] used to produce droplets, a main channel and a side branch 100 µm wide leading to the main acoustic chamber 1 mm×1 mm. As the flow exerts an extra force on the particles to be counterbalanced by the IDT emission, it is aligned along Z. The channel is assembled under microscope on the piezoelectric wafer, after it has been exposed for 10 s to an ozone plasma to promote adhesion between PDMS and LiNbO 3 [15]. The whole setup is heated to 65 • C for two hours and clamped between plexiglas plates and two aluminum disks to avoid the premature detachment of the channel. Visualization is made using a standard microscope (Macroscope Leica Z6) and particle trajectories are recorded using a fast camera (Phantom Miro 4, Vision Research) and treated using ImageJ software (NIH, Bethesda, MD).

Two categories of particles are presented to illustrate the efficiency of the tweezers: oil in water droplets, and human red and white blood cells (hRBCs and hWBCs). The oil droplets are generated in situ by injecting 50 cSt silicone oil (Sigma Aldrich) and de-ionized water with 10% dishwashing surfactant (Dreft, Procter and Gamble) in the flow focus [16]. The cells are obtained by successive concentrations using centrifugation and dilution in a buffer solution (PBS) for plasma removing. The IDTs are excited by a set of arbitrary waveform generators each connected to 40 or 50 dB amplifiers (Amplifier Research, model 75A250A and ENI, Models 320L, 325LA, 411LA). A calibration of the performance of each IDT as a function of frequency is initially performed by observing the deviation of some particles. The maxima are found at fre-quencies F in the range 34.5-37 MHz as expected from the ratio between the velocity of the Rayleigh wave of the water loaded LiNbO 3 to the IDT pitch [17]. A 1D or 2D standing wave pattern is created by exciting the IDT pairs at the same frequency and amplitude, for which the two counter-propagating waves compensate.

Particle motion is achieved by the low frequency modulation of one IDT respective to its opposite. Periodic trajectories were obtained by using modulations of the form F mod = F + ∆F g(2πf m t) where ∆F represents some frequency deviation and f m the modulation frequency in the periodic function g. Note that ∆F (of the order of Hz) is much smaller than F , so that the device stays at resonance. This type of excitation automatically creates a dynamic phase shift ϕ(t) with respect to the other electrode such that φ = 2π∆F g(2πf m t) and thus a drift of the interference pattern at the velocity v d = φ/2π × λ/2. This contrasts with other works [11] where the motion was obtained by the progressive adjustment of the static relative phase between the two IDTs, or by an important modification of the frequency of both electrodes to change the wavelength [12]. Figure 2 illustrates the results obtained with oil droplets that move under the action of two sine function modulations along the two directions Y and Z (see also Supplementary Material [18]). The various droplets, differing by their diameters (40 µm and 10 µm for the smallest) follow identical elliptical trajectories corresponding to Lissajous patterns. As a function of time, a very good fit is obtained from the following parameter free model: z = z 0 + L cos(2πf m t) and y = y 0 + L sin(2πf m t + θ) with L = λ∆F/4πf m half the amplitude of the course and θ some initial phase at the starting time of the SAW actuation. The figure also shows the trajectories of WBCs (diam. ∼ 14 µm) with a modulation function programmed to describe a 'house' shape. The control is still good, though some discrepancies can be seen. For RBCs, which sizes are smaller (6-8 µm), the control gets more difficult at higher velocities and may depend on the remaining flow direction.

In order to determine the limit velocities at which particles can be moved, the distances traveled by the particles along (and transverse to) the main flow have been plotted in figure 3 as a function of the typical drift velocity v d for the sinusoidal modulation. Up to 25 mm/s, oil droplets have positions exactly predictable showing that the two degrees of freedom are independent. At larger velocities, the drifting amplitude is damped, since the viscous forces become comparable to the acoustic ones. For RBCs, this maximum obtained velocity reaches 7 mm/s in the flow transverse direction and is reduced to 1.5 mm/s along the main flow.

The motion of the object can be predicted from the balance of forces at low Reynolds number:

F rad sin[4π(y -y 0 (t))/λ] + 6πηR ẏ = 0 (1)
where the first term is the radiation force on a object located at the position y(t) in a standing wave (in the Y or Z direction) whose nodes move according to the position y 0 (t) = L sin(2πf m t), and where the second term is the Stokes drag at velocity ẏ in a fluid of viscosity η.

The time integration of ẏ gives an amplitude of displacement very close to that of figure 3, with a sharp drop in displacement efficiency when the drifting velocity exceeds v max = F rad /6πηR, provided the radiation force is fitted by F rad = 2.5 nN for the 10 µm droplets (and F rad = 0.1 nN and 0.6 nN along the Z and Y direction for the RBCs, assuming a diameter of 8 µm). We can predict the acoustic pressure P a associated with theses forces to be 7.1 × 10 5 Pa (4.5 × 10 5 and 9.8 × 10 5 Pa for RBCs in Z and Y directions). These values for the pressures are obtained using the expression by Yosioka [19] for the radiation force as a function of acoustic pressure: F rad = πP 2 a V Φ/2λρc 2 , with V = 4πR 3 /3 and Φ a parameter that depends on the acoustic properties of objects and water [START_REF]Φ = (5ρ1 -2ρ)/(2ρ1 +ρ)-ρc 2 /ρ1c 2[END_REF]. These predictions are of the order of magnitude expected for nanometric vibrations amplitudes of the substrate [START_REF] Shilton | [END_REF] (as can be computed using P a = ρcAω, with ρ the density of water, c the sound velocity, A the vibration amplitude and ω the pulsation).

In an attempt to identify the parameters that influence the efficiency of the tweezers, we multiplied the experiments by varying particle sizes, particle composition, flow velocities, SAW amplitude and direction of emission. We observed that the proximity of the lateral channel walls (seen on Fig. 2(b)) could interfere with the particles motion due to undesired standing waves, that originate from the reflexion of the incoming waves and that are fixed respective to the moving standing wave pattern. It was also found that the acoustic threshold necessary to initiate motion depended both on the particle size and its composition. For a given size, the threshold is less for bubbles than for droplets, itself less than for cells. When the composition is fixed, the manipulation of smaller particles requires larger acoustic amplitudes. These observations are compatible with a mechanism where the forces at the origin of the acoustic tweezers are given by the gradient of acoustic pressure [19]. However, some excessive acoustic amplitudes can also result in a decrease of the particle mobility as we now discuss. As sketched on figure 4, the creation of a standing wave from two counter propagating waves on the piezoelectric wafer also gives rise to a propagative component normal to the piezoelectric surface, which pushes the particles toward the PDMS walls. For objects whose dimensions exceed the channel height (large bubbles or droplets), this results in an increase of the friction forces at large acoustic powers. Dewetting of the thin film in between the object and the PDMS top surface can even be observed for objects at rest, when the disjoining pressure is not large enough to counterbalance the acoustic forces. For objects smaller than the gap height the mobility is also decreased, to an extent that depends on the top wall proximity and therefore on the amplitude of the radiation forces. This idea was verified by directly observing under a microscope the accumulation of RBCs against the PDMS. As a consequence, the search of an optimal acous- FIG. 4: Sketch of the 3D motion of a particle actuated by SAW propagation. The acoustic wave inside the liquid is at the same time a standing wave in a plane parallel to the surface (YZ plane), and propagating along the perpendicular direction (X), since it is a superposition of two leaky waves, i.e. sin(kz + kF sin θR x -ωt) + sin(-kz + kF sin θR x -ωt) = 2 cos(kz) sin(kF sin θR x -ωt), where k is the SAW wavevector, θR the Rayleigh angle, and kF = k/ cos θR the acoustic wavevector in the liquid.

tic power to manipulate particles with SAW involves the consideration of the 3D nature of the forces that are created.

In conclusion, we have developed and characterized acoustic tweezers that induce fast motion and precise positioning of single particles made of various materials. We found that the action of the SSAW also involves normal radiative forces, and we have evidenced their effect on the particle mobility. Eventually, we hope this work will contribute to the rapid development of efficient acoustic tweezers for cell manipulations, since it helps to adjust the amplitude of the acoustic force necessary to trap particles, depending on the desired drifting velocity.

FIG. 1 :

 1 FIG. 1: a) Scheme of the acoustic device geometry. The flow direction is indicated by the arrow. A first pair of interdigitated transducers emits along the crystal strong axis Z which coincides with the main flow direction. A second pair emits along the perpendicular direction (Y axis). b) Principle of frequency modulation to move particles. c) Image of two oil droplets trapped in the acoustic chamber 1 mm wide and 50 µm high.

FIG. 2 :

 2 FIG. 2: a) Frequency versus time of the modulation function. Left: 'elliptical' motion, ∆F =5 Hz, fm=0.5 Hz. Right 'house', ∆F =32 Hz, fm=1 Hz. The trajectories corresponding to modulations sequences A and H are shown by the arrows. b) Superimposed images of particles motions. IDT pairs frequency for the standing waves: FZ =36.8 MHz, FY =34.5 MHz. Left: Silicone oil droplets. Right: White blood cells. c) Time evolution of the position of a silicone oil droplet position along flow (Z-axis) and transverse to the flow (Y-axis) and comparison with the model with fitting parameters L = 79.6 µm and fm=0.5 Hz.

FIG. 3 :

 3 FIG.3: Total amplitudes of the periodic trajectories travelled by hRBCs and 10 µm silicone oil droplets along the flow (∆Z) and transverse to the flow (∆Y ) direction as a function of the maximum calculated drift velocity (2πfmL). The values are normalized from the amplitude of the total standing wave displacement 2L. The continuous line showing plateaus corresponds to the numerical integration of Eq. (1) for oil droplets.

The authors gratefully acknowledge financial support from ANR Microacoustics Grant ANR-08-JCJC-014-01.