Amrit Kumar
email: amrit.kumar@inria.fr

Cédric Lauradoux
email: cedric.lauradoux@inria.fr

A Survey of Alerting Websites: Risks and Solutions

Keywords: Data leakages, Phishing, Private Set Intersection, Private Information Retrieval, Bloom filter

In the recent years an incredible amount of data has been leaked from major websites such as Adobe, Snapchat and LinkedIn. There are hundreds of millions of usernames, email addresses, passwords, telephone numbers and credit card details in the wild. The aftermath of these breaches is the rise of alerting websites such as haveibeenpwned.com, which let users verify if their accounts have been compromised. Unfortunately, these seemingly innocuous websites can be easily turned into phishing tools. In this work, we provide a comprehensive study of the most popular ones. Our study exposes the associated privacy risks and evaluates existing solutions towards designing privacy-friendly alerting websites. In particular, we study three solutions: private set intersection, private set intersection cardinality and private information retrieval adapted to membership testing. Finally, we investigate the practicality of these solutions with respect to real world database leakages.

Introduction

In the recent years, we have witnessed an increasing number of data leaks from major Internet sites including Adobe, Snapchat, LinkedIn, eBay, Apple and Yahoo ! (see bit.ly/19xscQO for more instances). While in most of the cases passwords' files have been targeted; database of identifiers, phone numbers and credit card details have also been successfully exfiltrated and published. These leakages dealt a substantial blow to the trust of people in computer security.

The aftermath of these leakages has led to three pivotal developments. First, the bad security policies of major websites have been exposed, and better policies have been proposed to survive leakages (see [START_REF] Parno | CLAMP: Practical Prevention of Large-Scale Data Leaks[END_REF], [START_REF] Kontaxis | SAuth: protecting user accounts from password database leaks[END_REF], [START_REF] Juels | Honeywords: making password-cracking detectable[END_REF]). In [START_REF] Parno | CLAMP: Practical Prevention of Large-Scale Data Leaks[END_REF], Parno et al. design an architecture to prevent database leakage. At CCS 2013, Kontaxis et al. propose SAuth [START_REF] Kontaxis | SAuth: protecting user accounts from password database leaks[END_REF], an authentication scheme which can survive password leakage. At the same conference, Juels and Rivest present the Honeywords [START_REF] Juels | Honeywords: making password-cracking detectable[END_REF] to detect if a passwords' file has been compromised.

Second, security community has obtained datasets to study the password habits of users. In [START_REF] Das | The Tangled Web of Password Reuse[END_REF], Das et al. consider several leaked databases to analyze password reuse. De Carnavalet et al. [START_REF] De | From Very Weak to Very Strong: Analyzing Password-Strength Meters[END_REF] use these datasets to test the effectiveness of password meters.

Third, a new kind of websites has appeared: alerting website. Users can check through these sites whether their accounts have been compromised or not. In order to check whether a user is a victim of data leakage, alerting websites ask for an identifying data such as username or email address and sometimes even password. These websites are maintained by security experts such as haveibeenpwned.com by Troy Hunt, security companies e.g., LastPass, and even government institutions like the German Federal Office for Information Security (Bsi): sicherheitstest.bsi.de.

On one hand, these websites are very useful in alerting users, while on the other hand, they are real "booby traps". The problem is the following: when a user submits a username or an email address or a password, the site searches whether it exists or not in the leaked database. If it exists, the user is warned and the website has accomplished its purpose. However, if it is not present in the database, the site owner learns for free a username/email address/password.

Most of these sites advert to the users that they do not indulge in phishing activities but this is the only guarantee available to the user. The goal of alerting websites is to reduce the effect of data leakage but not amplify it! Considering the risks of using alerting websites, we naturally raise the following question: How to design alerting websites which cannot be turned into a phishing trap? The user must have a guarantee that it is not possible for the database owner to collect his information during a search query.

With the increasing frequency of data leakages, these websites are fast becoming a sine qua non for the victims of data leakages. Consequently, an analysis of these websites and their service is necessary. Our work presents a comprehensive study of alerting websites from two angles: the associated privacy risks and possible solutions to improve the service.

Contribution. The contribution of the paper is threefold:

1. We examine 17 popular alerting websites (Section 2) and analyze their working mechanism, and their approach to deal with privacy. Our findings reveal that several of these websites have huge phishing potential and hence users should be careful while visiting any of these websites. 2. We evaluate existing solutions for designing privacy-friendly alerting websites. Two different scenarios have been considered depending on whether or not the database is public. In case of private database (Section 4), private set intersection protocol and its variant private set intersection cardinality protocol yield an immediate solution. The scenario of public database (Section 5) requires us to adapt private information retrieval protocol for membership testing. This is achieved by combining it with Bloom filters (Section 5.1). These protocols subsumed under the name of Private Membership Query protocols ensure user's privacy in the honest-butcurious model. 3. Finally, we experimentally analyze the merits of these solutions with respect to real world data leakages (Section 6).

Alerting Websites: Risks

Users can be alerted on the fact that their account or personal information has been leaked. We discuss the characteristics of these websites which evidently offer opportunities for sophisticated phishing attacks.

Websites alerting users about their account or data leakage can be divided into three types according to their sources of information. In the sequel, we categorically discuss our findings.

Single-source (S). Some websites are associated with a single data leakage. This is the case for adobe.cynic.al, bit.ly/1by3hd9, lucb1e.com/credgrep and adobe. breach.il.ly. These websites are related to the Adobe data leakage of 153 million accounts which occurred in October 2013. The last three websites were successfully tested on 22/12/2014 but cannot be accessed anymore. Other websites for instance snapcheck.org,1 findmysnap.com, and lookup.gibsonsec.org are similarly associated with the SnapChat leakage (4.6 million usernames, phone numbers and city exposed in January 2014).

Aggregator (A). We observe that 5 of these websites search through several databases to inform users if their data has been exposed. For instance, shouldichangemypassword. com (bit.ly/1aJubEh for short) allegates to use 3346 leaked databases while only 194 are officially known. The remaining four are maintained by private companies: lastpass.com, bit.ly/1fj0SqV, bit.ly/1aJubEh and dazzlepod.com/disclosure. The last remaining site haveibeenpwned.com is designed and maintained by security expert Troy Hunt.

Harvester (H). Three sites claim to have created their own databases from harvested data. Two of these are maintained by famous security companies hacknotifier.com and pwnedlist.com/query. The last site is maintained by the German Federal Office for Information Security (Bsi).

The rue89.nouvelobs.com site is slightly different from the others. In September 2014, this French news website bought on the Darknet 20 million French email addresses for 0.0419 bitcoins (see article bit.ly/1lKAxsB). The article offers the opportunity to check if the reader's addresses are included in the leak. We have reviewed 17 alerting sites and our findings are summarized in Table 1. To measure if a user can trust the service offered by these sites, we have considered four criteria:

-The usage of a secure connection through HTTPS.

-The existence or not of a security/privacy statement.

-The fact that the site responds or not with an answer.

-A technical description of all the operations performed on the data.

From Table 1, we observe that ten of these sites do not use HTTPS which means that the traffic towards them can be easily eavesdropped. Single-source alerting sites are the least trustworthy of all because most of them do not have a privacy statement. The website bit.ly/1by3hd9 is a notable exception. Aggregator sites in general perform better. Most of them use HTTPS and have a statement concerning privacy or phishing. The website haveibeenpwned.com even has a description of how it works.

The harvesters are more controversial: hacknotifier.com claims that "we use a 256-bit secured and encrypted SSL connection", but does not use HTTPS or any encryption. 2 The website pwnedlist.com/query claims that "this is not a phishing site", but they also state (pwnedlist.com/faq) that "Over the past years we've built an advanced data harvesting infrastructure that crawls the web 24/7 and gathers any potentially sensitive data ...".

Four sites do not give any answer: either they are not working anymore (like lucb1e. com/credgrep) or they are real phishing traps.

Almost all the sites receive account information in clear. However, there are two notable exceptions lastpass.com and dazzlepod.com/disclosure. The former uses cryptographic hash functions and truncation to obfuscate the query and seems to be the most transparent and trustworthy of all. Table 2 presents a summary of our observations on lastpass.com. The latter source, dazzlepod.com/disclosure only recommends to truncate the email address. With pwnedlist.com/query, it is also possible to submit the SHA-512 digest of the email address instead of the address itself. Cryptographic hash functions, e.g. MD5, SHA-1 or SHA-3 are however not enough to ensure the privacy of passwords, identifiers or email addresses: these data do not have full entropy. Email addresses were recovered from Gravatar digests [START_REF] Bongard | De-anonymizing Users of French Political Forums[END_REF] as well as passwords (see [START_REF] Narayanan | Fast dictionary attacks on passwords using time-space tradeoff[END_REF] for instance). Apple's Unique Device IDs aka UDIDs are no exceptions. They are computed by applying SHA-1 on a serial number, IMEI or ECID, the MAC address of WiFi and the MAC address of Bluetooth. The values used to produce a UDID can be guessed and LastPass asks only for the first 5 characters of UDID. It reduces the amount of information submitted to the site but the user is not warned if he provides more than 5 characters.

As a general conclusion, the measures taken by these websites are clearly not adequate to ensure the privacy of users' queries. In the remainder of the paper, we evaluate how existing cryptographic and privacy preserving primitives can solve the problems associated to alerting websites. These privacy-friendly solutions should guarantee that the websites cannot harvest any new data from a user's query.

Privacy-Friendly Solutions: Private vs. Public Database

As previously discussed, the existing alerting websites in general do not respect the privacy of a user and entail huge phishing potential. The need of the hour is to design privacy-friendly alerting websites. These websites would rely on what we refer as Private Membership Query protocols -allowing a user to privately test for membership in a given set/database. Such a protocol would guarantee that no new data can be harvested from a user's query.

To this end, two different privacy objectives can be defined depending on the privacy policy of the database owner. One that we henceforth refer as Private Membership Query to Public Database, and the other as Private Membership Query to Private Database. This classification arises due to the fact that most of these leaked databases are available on the Internet (as hackers have acquired the database dump) and hence can be considered as public in nature. However, even though they are public in terms of availability, an ethical hacker might want to ensure that the leaked information is not used for malicious purposes and hence the database cannot be accessed in a public manner to consult private information corresponding to other users. Rendering the database private could also be of interest for government agencies such as bsi sicherheitstest.bsi.de.

We highlight that a private membership query protocol provides a direct solution to the problem of designing privacy-friendly alerting websites. A user wishing to know whether his data has been leaked would be required to invoke the private membership protocol with the database owner and learns whether he is a victim of the breach. Thanks to the user's privacy provided by the protocol, no new data can then be harvested by the website. Consequently, in the rest of this work, we concentrate on evaluating solutions for private membership query problem. In the sequel, we formalize the privacy policies and examine viable solutions in the two database scenarios.

Solutions for Private Databases

The scenario of private membership query to private database involves a private database DB and a user U. The database DB = {y 1 , . . . , y n }, where y i ∈ {0, 1} consists of n bit-strings each of length . User U owns an arbitrary string y ∈ {0, 1} . Private membership query to DB consists in knowing whether or not user's data y is present in the database while keeping y private to the user and DB private to the database.

Adversary model: The client and the database-owner are supposed to be honestbut-curious i.e. each follows the protocol but tries to learn information on the data held by the other player.

The above problem is very closely related to the problem of Private Set Intersection, hence we examine its applicability to designing privacy-friendly alerting websites.

Private Set Intersection (PSI). PSI protocol introduced by Freedman et al. [START_REF] Michaelj | Efficient Private Matching and Set Intersection[END_REF] considers the problem of computing the intersection of private datasets of two parties. The scenario consists of two sets U = {u 1 , . . . , u m }, where u i ∈ {0, 1} and DB = {v 1 , . . . , v n }, where v i ∈ {0, 1} held by a user and the database-owner respectively. The goal of the user is to privately retrieve the set U ∩ DB. The privacy requirement of the scheme consists in keeping U and DB private to their respective owner. Clearly, the private membership query to private database problem reduces to PSI for m = 1.

There is an abounding literature on novel and computationally efficient PSI protocols. The most efficient protocols are the ones by De Cristofaro et al. [START_REF] De | Practical Private Set Intersection Protocols with Linear Complexity[END_REF], Huang et al. [START_REF] Huang | Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?[END_REF] and Dong et al. [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF]. The general conclusion being that for security of 80 bits, protocol by De Cristofaro et al. performs better than the one by Huang et al., while for higher security level, the latter protocol supersedes the former. The most efficient of all is the protocol by Dong et al. as it primarily uses symmetric key operations. We however note that the communication and the computational complexity of these protocols is linear in the size of the sets.

Private Set Intersection Cardinality (PSI-CA). PSI-CA is a variant of PSI where the goal of the client is to privately retrieve the cardinality of the intersection rather than the contents. While generic PSI protocols immediately provide a solution to PSI-CA, they however yield too much information. While several PSI-CA protocols have been proposed [START_REF] Michaelj | Efficient Private Matching and Set Intersection[END_REF], [START_REF] Kissner | Privacy-Preserving Set Operations[END_REF], [START_REF] Hohenberger | Honest-Verifier Private Disjointness Testing Without Random Oracles[END_REF], [START_REF] Vaidya | Secure set intersection cardinality with application to association rule mining[END_REF], we concentrate on PSI-CA protocol of De Cristofaro et al. [START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF], as it is the most efficient of all. We also note that PSI-CA clearly provides a solution to the membership problem: if the size of the intersection is 0, then the user data is not present in the database.

Solutions for Public Databases

This scenario is modeled using a public database DB and a user U. The database as in the previous scenario is DB = {y 1 , . . . , y n }, where y i ∈ {0, 1} . User U owns an arbitrary string y ∈ {0, 1} not necessarily in DB. Private membership query consists in knowing whether or not user's data y is present in the database while keeping y private to the user.

The difference to the previous problem (Section 4) is that the database in this context is public. This leads to a trivial solution ensuring absolute privacy consisting in sending the database to the user, who using the available resources performs a search on the database. With huge databases of order GB, the trivial solution is not the most desirable one for low memory devices. In this scenario, a user would wish to securely outsource the search to the database-owner. In the following we present tools which provide a solution in the public database case.

Tools

In the first place we present a protocol called Private Information Retrieval [START_REF] Chor | Private Information Retrieval[END_REF], which is the closest to our needs. In the sequel we present Bloom filter and finally show that combining these tools allows us to obtain a protocol for private membership query to public database.

Private Information Retrieval (PIR). PIR first introduced in the seminal work by

Chor et al. [START_REF] Chor | Private Information Retrieval[END_REF] is a mechanism allowing a user to query a public database while keeping his intentions private. In the classical setting of PIR [START_REF] Chor | Private Information Retrieval[END_REF], a user wants to retrieve the bit at index 1 ≤ j ≤ n in a database DB = {y 1 , . . . , y n }, where y i ∈ {0, 1}, but does not want the database to learn j.

Adversary model: The database owner is supposed to be honest-but-curious. Since the work by Chor et al., several variants of PIR have been studied which include Private Block Retrieval (PBR) scheme -where the goal is to retrieve a block instead of a bit and PrivatE Retrieval by KeYwords (PERKY) [START_REF] Chor | Private information retrieval by keywords[END_REF] -where the user only holds a keyword kw instead of an index j. While PIR may either be built on single or replicated database copies, most of the latter only consider the more realistic single database scenario. These works improve on the communication complexity [START_REF] Cachin | Computationally Private Information Retrieval with Polylogarithmic Communication[END_REF][START_REF] Chang | Single Database Private Information Retrieval with Logarithmic Communication[END_REF], [START_REF] Gentry | Single-Database Private Information Retrieval with Constant Communication Rate[END_REF], [START_REF] Kushilevitz | Replication is Not Needed: Single Database, Computationally-private Information Retrieval[END_REF][START_REF] Lipmaa | An Oblivious Transfer Protocol with Log-Squared Communication[END_REF]. The current best bound of O(log 2 n) is independently achieved in [START_REF] Lipmaa | An Oblivious Transfer Protocol with Log-Squared Communication[END_REF], [START_REF] Gentry | Single-Database Private Information Retrieval with Constant Communication Rate[END_REF]. In this work, we only consider single database protocols. The principle reason being that in our context a user interacts with only one website.

Bloom Filter. Bloom filter [START_REF] Burton | Space/time trade-offs in hash coding with allowable errors[END_REF] is a space and time efficient probabilistic data structure that provides an algorithmic solution to the set membership query problem, which consists in determining whether an item belongs to a predefined set.

Classical Bloom filter as presented in [START_REF] Burton | Space/time trade-offs in hash coding with allowable errors[END_REF] essentially consists of k independent hash functions {h 1 , . . . , h k }, where {h i : {0, 1} * → [0, m -1]} k and a bit vector z = (z 0 , . . . , z m-1 ) of size m initialized to 0. Each hash function uniformly returns an index in the vector z. The filter z is incrementally built by inserting items of a predefined set S. Each item x ∈ S is inserted into a Bloom filter by first feeding it to the hash functions to retrieve k indices of z. Finally, insertion of x in the filter is achieved by setting the bits of z at these positions to 1.

In order to query if an item y ∈ {0, 1} * belongs to S, we check if y has been inserted into the Bloom filter z. Achieving this requires y to be processed (as in insertion) by the same hash functions to obtain k indexes of the filter. If any of the bits at these indexes is 0, the item is not in the filter, otherwise the item is present (with a small false positive probability).

The space and time efficiency of Bloom filter comes at the cost of false positives. If |S| = n, i.e., n items are to be inserted into the filter and the space available to store the filter is m bits, then the optimal number of hash functions to use and the ensuing optimal false positive probability f satisfy:

k = m n ln 2 and ln f = - m n (ln 2) 2 . ( 1
)
Membership Query to Bloom Filter: 2-party setting. Let us assume that Alice wants to check if her value y is included in the Bloom filter z held by Bob. The easiest way to do so consists for Alice to send y to Bob. Bob queries the filter on input y. He then sends 0 or 1 to Alice as the query output. If the canal between Alice and Bob has limited capacity, another strategy is possible and is described in Fig. 1.

Alice cannot send y due to some channel constraints but she can send a i = h i (y), for 1 ≤ i ≤ k. We suppose that Alice and Bob first agree on the hash functions to be used. Then Alice sends a i to Bob. In reply, Bob returns the bit at index a i of z to Alice A Bob B y z count=0 for i ∈ {1, . . . , k} ai = hi(y) her. If she only receives 1, y is included in z (with a small false positive probability f ) otherwise it is not.

a i ---------→ ri = za i if ri = 1 then count++ r i ← --------- if count=k then YES else NO
Remark 1. A possible private membership query protocol in the case of private database can be built by combining PSI/PSI-CA and Bloom filter. The idea would be to build a Bloom filter corresponding to the database entries and generate the set DB = supp(z), where supp(z) represents the set of non-zero coordinate indices of z. The client on the other hand generates U = {h 1 (y), . . . , h k (y)} for a data y. Finally, the client and the database owner invoke a PSI/PSI-CA protocol to retrieve the intersection set/cardinality of the intersection respectively. However, this solution is less efficient than a PSI/PSI-CA protocol on the initial database itself. The reason being the fact that, with optimal parameters the expected size of supp(z) = m/2 = 2.88kn (see [START_REF] Mitzenmacher | Compressed bloom filters[END_REF] for details) . Hence, the number of entries of the database in PSI/PSI-CA when used with Bloom filter is greater than the one of the original database.

We note that despite the similarity of the two problems: PIR and private membership to public database, PIR stand-alone does not provide a solution to our problem. Nevertheless, we show that when combined with a Bloom filter, PIR behaves as a private membership query protocol. Details are given in the following section.

Membership Query Using PIR

To start with, we note that classical PIR per se cannot be applied to our context since the user holding a data (email address, password, etc.) present in a database does not know its physical address in the database. Furthermore, PIR does not support nonmembership queries as the database is constructed in a predefined manner and has only finite entries, while the set of all possible queries is infinite. PERKY resolves the problem of physical address as it only needs kw, and not the index. However, standalone it still suffers from the non-membership issue for the same reason as that in case of PIR.

Despite these issues, we can still design a private membership query protocol using PIR as a subroutine and by changing the database representation to Bloom filters which support non-membership queries as well. The idea then is to invoke PIR on each query to the filter.

The protocol explained below requires that the database owner builds a bloom filter z using the entries and a user queries the filter and not the database.

-Database owner builds the Bloom filter z using k hash functions {h 1 , . . . , h k }.

-User for a data y generates {h 1 (y), . . . , h k (y)}.

-For each 1 ≤ i ≤ k, the user invokes a single-server PIR on index h i (y) and retrieves z hi(y) . -If z hi(y) = 0 for any i, then y is not in the database, else if all the returned bits are 1, then the data is present (with a false positive probability f ).

The only difference with the classical use of Bloom filter (Fig. 1) in the protocol is that the bit is retrieved using PIR.

Remark 2. As in the case of PIR, the database owner in our scenario is honest-butcurious. This attack model for instance does not allow the database owner to return a wrong bit to the user. Under this adversary model, the above protocol modification is private (i.e., keeps user's data private), if the underlying PIR scheme is private. PIR hides any single query of the user from the database owner. Therefore, any k different queries of the user are also hidden by PIR.

Extension with PBR Protocol

The adapted protocol in its current form requires a bit retrieval PIR scheme. Nevertheless, it can be easily modified to work even with a block retrieval aka PBR protocol. The essential advantage of using a PBR protocol instead of a classical PIR protocol would be to increase the throughput i.e. decrease the number of bits communicated to retrieve 1 bit of information. In fact, the most efficient PIR schemes [START_REF] Gentry | Single-Database Private Information Retrieval with Constant Communication Rate[END_REF], [START_REF] Lipmaa | An Oblivious Transfer Protocol with Log-Squared Communication[END_REF] are block retrieval schemes. The modification required to incorporate PBR would consist in using a Garbled Bloom filter (see [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF]) instead of a Bloom filter. We briefly explain below the garbled Bloom filter construction, and later we present the modification required.

Garbled Bloom Filter. At a high level Garbled Bloom Filter (k, m, H k , λ) GBF [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF] is essentially the same as a Bloom filter. The parameter k denotes the number of hash functions used, while H k is a family of k independent hash functions as in a Bloom filter. The size of the filter is denoted by m, and λ is the size of the items to be included in the filter. The difference with respect to a Bloom filter is that at each index in GBF, a bit string of length λ is stored instead of just storing the bit 1. In order to include an item y ∈ {0, 1} λ , one randomly generates k shares {r y 1 , . . . , r y k }, where r y i ∈ {0, 1} λ such that y = ⊕ i r y i . As in a Bloom filter, one then generates the k indices i y 1 , . . . , i y k by computing the hashes as i y j = h j (y) and truncating them by taking modulo m. Finally, at index i y j of the filter, the bit string r y j is stored. Collisions on two values y and y for a certain hash function h j are handled by choosing the same r j for both the values.

To check if a given item is in GBF, one computes the truncated hashes and retrieves the shares stored at these indices in GBF. If the XOR of these shares is the same as the given item, then the item is in the filter, or else not. More details on the probability of collisions and the probability of false positives can be found in [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF].

Private Membership Query using PBR. This protocol essentially follows the same principle as the one which combines PIR and a Bloom filter. The database owner now builds a GBF (k, m, H k , λ) using the entries and a user queries the GBF instead of the database. Again k PBR invocations are required to retrieve the k random shares. This adapted protocol is private if the underlying PBR scheme is private, i.e., does not reveal the user's queries.

Remark 3. At this juncture, we have two solutions for private membership query to public database: 1) k invocations of single server PIR/PBR to Bloom filter/GBF, 2) Send the complete filter for a local query. On one hand, any PIR based solution only provides computational privacy, has a communication cost, the best being O(log 2 m) and involves cryptographic computations and hence entails a significant time complexity. While on the other hand sending the filter ensures absolute privacy, but has a larger communication complexity m bits (still much better than the trivial PIR i.e., sending the initial database) but has a very low time complexity (has to invoke the protocol in Fig. 1 locally). Since the size of the database gets drastically reduced with Bloom filter, this solution provides a competitive alternative to trivial PIR even for low memory devices.

Practicality of the Solutions

We reiterate that a private membership query protocol provides an immediate solution for designing privacy-friendly alerting websites. For the sake of practicality, any realistic privacy-friendly alerting websites should provide response to a user's query in real time. It is hence highly important to evaluate the practicality of the underlying protocol.

We first discuss the practicality of the solutions based on PIR/PBR and Bloom filter in case of public database and in the sequel we discuss the practicality of PSI/PSI-CA protocol in case of private database.

Since Bloom filter is highly efficient in space and time, the practicality of PIR/PBR based protocol depends on the practicality of the underlying PIR/PBR scheme. Hence we first discuss its practicality as perceived in the literature and later by experimentally evaluating PIR/PBR protocols.

For experimental evaluation, the tests were performed on a 64-bit processor desktop computer powered by an Intel Xeon E5410 3520M processor at 2.33 GHz with 6 MB cache, 8 GB RAM and running 3.2.0-58-generic-pae Linux. We have used GCC 4.6.3 with -O3 optimization flag.

Applicability of PIR

Sion and Carbunar [START_REF] Sion | On the Practicality of Private Information Retrieval[END_REF] evaluate the performance of single database PIR scheme. The authors show that the deployment of non-trivial single server PIR protocols on real hardware of the recent past would have been orders of magnitude less time-efficient than trivially transferring the entire database. The study primarily considers the computational PIR protocol of [START_REF] Kushilevitz | Replication is Not Needed: Single Database, Computationally-private Information Retrieval[END_REF]. The authors argue that a PIR is practical if and only if per-bit server side complexity is faster than a bit transfer. With a normal desktop machine, trivial transfer (at 10MBps) of the database is 35 times faster than PIR. This ultimately restricts the use of PIR protocols for low bandwidths (tens of KBps).

Olumofin and Goldberg [START_REF] Olumofin | Revisiting the Computational Practicality of Private Information Retrieval[END_REF] refute the general interpretation [START_REF] Sion | On the Practicality of Private Information Retrieval[END_REF] that no PIR scheme can be more efficient that the trivial one. Authors evaluate two multi-server information-theoretic PIR schemes by Chor et al. [START_REF] Chor | Private Information Retrieval[END_REF] and by Goldberg [START_REF] Goldberg | Improving the Robustness of Private Information Retrieval[END_REF] as well as a single-server lattice-based scheme by Aguilar-Melchor and Gaborit [START_REF] Melchor | A fast private information retrieval protocol[END_REF]. The later scheme is found to be an order of magnitude more efficient over the trivial scheme for situations that are most representative of today's average consumer Internet bandwidth. Specifically, for a database of size 16 GB, the trivial scheme outperforms the lattice based scheme only at speeds above 100 Mbps. intersection protocols perform better than PIR protocols: 1) the computational cost in PSI/PSI-CA protocols is reduced at the cost of communication overhead, 2) the size of the security parameter is independent of the size of the database. More precisely, the communication cost of the most efficient PSI/PSI-CA protocols [START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF][START_REF] De | Practical Private Set Intersection Protocols with Linear Complexity[END_REF], [START_REF] Huang | Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?[END_REF], [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF] is linear while the goal of PIR protocols is to achieve sub-linear or poly-logarithmic complexity. This indeed comes at a cost, for instance the size of RSA modulus in PSI [START_REF] De | Practical Private Set Intersection Protocols with Linear Complexity[END_REF] for 80 bits of security is 1024 bits and hence independent of the size of the sets involved. While in case of PIR [START_REF] Cachin | Computationally Private Information Retrieval with Polylogarithmic Communication[END_REF], the size of the modulus used is log 3-o(1) (n) bits. Hence for a million bit database, the modulus to be considered is of around 8000 bits, which leads to a very high computational cost.

Conclusion

In this work, we examined websites alerting users about data leakage. With the current rate of leakage, these websites will be needed for a while. Unfortunately, it is currently difficult to determine whether or not these websites are phishing sites since they do not provide any privacy guarantee to users. Our work exposes the privacy risks associated to the most popular alerting websites. We further evaluate how state-of-the-art cryptographic primitives can be applied to make private query to an alerting site possible. Two different scenarios have been considered depending on whether the database is public. While PSI/PSI-CA protocols provide a straightforward solution in the private database scenario, a tweak using Bloom filter transforms PIR/PBR into private membership protocols for public database.

Our experimental evaluation shows that PSI/PSI-CA protocols perform much better than PIR/PBR based protocol. This is an encouraging result for the ethical hacking community or security companies. Yet the cost incurred by these ad hoc solutions is considerable and hence there remains the open problem of designing dedicated and more efficient solutions.

Fig. 1 .

 1 Fig. 1. Verification on a constraint channel.

Table 1 .

 1 Analysis of 17 alerting websites (* result as on 22/12/2014).

	Websites Type Database(s) https Statement Answer Descrip.
	rue89.nouvelobs.com S	Unknown
	adobe.cynic.al S
	bit.ly/1by3hd9 * S lucb1e.com/credgrep * S	Adobe
	adobe.breach.il.ly * S
	snapcheck.org S
	findmysnap.com S	SnapChat
	lookup.gibsonsec.org S
	didigetgawkered.com S	Gawker
	lastpass.com A	6
	haveibeenpwned.com A	9
	bit.ly/1fj0SqV A	12
	dazzlepod.com/disclosure A	28
	bit.ly/1aJubEh A	3346/194
	hacknotifier.com H	Unknown
	pwnedlist.com/query H	Unknown	/
	sicherheitstest.bsi.de H	Botnets

Table 2 .

 2 Detailed analysis of lastpass.com.

	Victim Query	Policy	Privacy method
	Adobe	Email	non-storage	None
	LinkedIn password non-storage and non-logging SHA-1
	Snapchat user name non-storage and non-logging SHA-1
	Apple	UDID		Truncation
	Last.fm	password non-storage and non-logging MD5
	eHarmony password non-storage and non-logging MD5

The database cannot be accessed anymore (10/12/2014).

Actually, subscribing for the hacknotifier.com watchdog is also not secure.

Acknowledgements

This research was conducted with the partial support of the Labex persyval-lab(anr-11-labx-0025) and the project-team SCCyPhy.

Experimental Analysis

We have implemented two PIR/PBR protocols: 1) Cachin et al. [START_REF] Cachin | Computationally Private Information Retrieval with Polylogarithmic Communication[END_REF], which is the most efficient (in terms of communication) bit retrieval scheme 2) Aguilar-Melchor and Gaborit [START_REF] Melchor | A fast private information retrieval protocol[END_REF] (implemented in parig-gp 3 ) which is the most computationally efficient PBR protocol. We have also implemented RSA-OPRF PSI protocol of De Cristofaro et al. [START_REF] De | Practical Private Set Intersection Protocols with Linear Complexity[END_REF] and PSI-CA protocol of De Cristofaro et al. [START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF]. The existing implementation 4 of protocol by Dong et al. [START_REF] Dong | When private set intersection meets big data: an efficient and scalable protocol[END_REF] seems not to execute correctly. Even after correcting the initial compilation errors, the code seems not to be executing the protocol till the end. We hence do not consider it for our evaluation. Public Database. The cost of using PIR-based schemes reduces to the cost of building the filter combined with the cost of k PIR invocations on the filter. We present the time required to build a Bloom filter for the leaked databases corresponding to Snapchat, LinkedIn and Adobe in Table 3. The filter is constructed using SHA-1 which generates 20 bytes' digest.

From Table 3, we can observe that the filter size grows slowly and that the computational time of the filter is reasonable. Initially, all the computations are performed in a sequential manner. We have then distributed the computation on 4 computers (with similar characteristics). Parallelizing the creation of the Bloom filter is straightforward and we nearly achieved a 4× speedup (50 mins). With a few computers, it is possible to reduce the computational time for creating the filter to a desired threshold. We further note that building a Bloom filter involves only a one-time cost.

Despite the space and time efficiency of Bloom filter, the huge cost of PIR invocation (using the existing primitives) makes such protocols impractical. The protocol [START_REF] Cachin | Computationally Private Information Retrieval with Polylogarithmic Communication[END_REF] takes over 6 hours in case of Snapchat database for one invocation. If the probability of false positive is 2 -32 i.e. k ≈ 32, the estimated time for 32 PIR invocations is over 32 × 6 hours i.e. over 8 days. The PBR protocol [START_REF] Melchor | A fast private information retrieval protocol[END_REF], takes around 2 hours for 1 PBR invocation on Snapchat garbled Bloom filter. The security level considered here is of 3 pari.math.u-bordeaux.fr/ 4 Available at bit.ly/1k75nu6 100 bits. However, considering the household network bandwidth of 10 Mbps, the time to download the filter would take 20 seconds. The time efficiency of the trivial PIR with Bloom filter seems unmatchable.

Private Database. Table 4 presents results obtained for the PSI protocol by De Cristofaro et al. [START_REF] De | Practical Private Set Intersection Protocols with Linear Complexity[END_REF] for 80 bits of security.

Table 4. Cost for PSI protocol [START_REF] De | Practical Private Set Intersection Protocols with Linear Complexity[END_REF] with 80 bits of security using SHA-1.

Database Cost (mins)

Snapchat 48 LinkedIn 68 Adobe 1600

Table 5. Cost for PSI-CA protocol [START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF] with 80 bits of security using SHA-1.

Database Cost (mins)

As the user's set has only one data, his computational cost is negligible. To be precise, a user's computational cost consists in computing a signature and n comparisons. The authors in [START_REF] De | Experimenting with Fast Private Set Intersection[END_REF] claim that the result of the server's computation over its own set can be re-used in multiple instances. Hence, the server's cost can be seen as a one-time cost, which further makes it highly practical.

Table 5 presents results obtained using PSI-CA protocol by De Cristofaro et al. [START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF]. Recommended parameters of |p| = 1024 and |q| = 160 bits have been chosen.

Clearly, PSI-CA outperforms PSI by a factor of 5. The reason behind this performance leap is that the exponents in modular exponentiations are only 160 bits long in PSI-CA as opposed to 1024 bits in PSI. Table 6 summarizes the results obtained on Snapchat database for f = 2 -32 . Clearly, in the public database case, sending the Bloom filter is the most computationally efficient solution. While, in the private database scenario, PSI-CA provides a promising solution. Comparing the two cases, we observe that the private database slows down the query time by a factor of 9.

We highlight that PSI/PSI-CA protocols perform much better than PIR/PBR protocols. This is counter-intuitive, as in case of PIR the database is public while in PSI the database is private. A protocol on private data should cost more than the one on public data. With a theoretical stand-point, there are two reasons why private set


Fran De Aquino

Method for Obtaining Quantum Vacuum

Keywords: Quantum Vacuum, Universal Quantum Fluid, Continuous Universal Fluid, Gravity Control Cells. Key w

The possibility of obtention of quantum vacuum in laboratory is shown in this work. The method consists in ward off air atoms from the surface of a solid material plate. The clearance can reach up to several nanometers, thus producing a region where there are no elementary particles.

Even in the densest matter found in the Earth, the atoms are not together. There are spaces among them, configuring a domain region around each atom. On the bidimensional viewpoint, this region is defined for an area, , around each atom. We can calculate, , starting from the atoms density of the material, n ,

φ ρ φ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = = = ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 7
q r q q F + + Δ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = = + + Δ = = = φ ρ φ ρ πε πε πε
The equilibrium occurs when . Under this circumstance, the air close to the plate is maintaining at a distance This distance is insufficient to configure a region of quantum vacuum because it is much smaller than the diameter of one atom (1-3Å). Under these circumstances, the zone between the plate and the air close to the plate practically does not exist, because some atoms can penetrate partially the zone, preventing the formation of the quantum vacuum (See Fig. 3 (a)).

However, if The result is approximately the same in the case of Beryllium (Be) . 10

- - m kg 2]
. This ultra-low density strongly facilitates the construction of the Gravity Control Cells (GCCs), mentioned in a previous paper [START_REF] De Aquino | Gravity Control by means of Electromagnetic Field through Gas at Ultra-Low Pressure[END_REF]. Thus, the possibility of to obtain layers quantum vacuum in practice, is highly relevant for the construction of the GCCs. For example, consider the device shown in Fig. 4 (a). When the air internal pressure is 0.76 Torr, two layers of quantum vacuum are formed in the internal faces (I and II) of the device. Thus, by applying an electric or magnetic field in these layers of quantum vacuum, the device becomes a double GCC. On the other hand, if the internal face (I) of the device is coated with a plastic material, then the layer of quantum vacuum at the neighborhood of this face disappears. Consequently, by applying an electric or magnetic field in the layer of quantum vacuum, the device becomes a simple GCC (See Fig.

=

  s number; ρ is the matter density (in kg/m ) and A is the atomic mass. 3 Then, the amount of front atoms in a volume atom Sφ (plane surface area, , and thickness S atom φ (diameter of a front atom)) of a material with density of atoms, is given by n atom nSφ . Therefore, we can write that If we could see the front atoms in the surface S , we would see that behind each the area , there are (See Fig.1). If each one of these atoms has only one electron in its electronic external layer, then the number of electrons, , in the area is . Thus, considering the

  e

Fig. 1 -.

 1 Fig.1 -Elementary domain area, A S , in a plane area (S). -The amount of front atoms in a volume

  Plane area SElementary domain area, S A , of the front atom (in black at the triangle center). Behind the area S A there are N atoms (circles in white) .

Fig

  Fig.2 -The forces e

  For any type of solid plate we have . For electrons in ( )

  is sufficient to configure a region of quantum vacuum (See Fig.3(b)).

Fig. 3 -

 3 Fig.3 -Quantum vacuum formation. (a) If the distance x Δ is smaller than the diameter of an atom (1-3Å) the zone between the plate and the air close to the plate practically does not exist, because some atoms can penetrate partially the zone, preventing the formation of the quantum vacuum. (b) Only if x Δ is

Fig. 4 -

 4 Fig.4 -Double and Simple Gravity Control Cell


Emmanuelle Saillard

Patrick Carribault

Denis Barthou

MPI Thread-Level Checking for MPI+OpenMP Applications

Keywords: Static verification, OpenMP, MPI, MPI Thread level

come

Introduction

To address the challenges of exascale systems, MPI evolves to be mixed with shared-memory approaches like OpenMP. E. Lusk and A. Chan report for instance some successful use cases of OpenMP threads exploiting multiple cores per node with MPI communicating among the nodes [START_REF] Lusk | Early Experiments with the OpenMP/MPI Hybrid Programming Model[END_REF]. But combining models does not facilitate the debugging task and requires special care for MPI calls [START_REF] Gropp | Thread Safety in an MPI Implementation: Requirements and Analysis[END_REF]. Indeed, in an MPI+OpenMP program, not only the correctness of MPI should be ensured but also the multi-threaded model should not interfere with MPI. As an example, within a process, the same communicator may not be concurrently used by two different MPI collective calls. This means MPI collective operations may not be called by multiple parallel threads. The MPI-2 standard defines four thread-safety levels to indicate how MPI should interact with threads. According to the MPI standard, it is the user responsibility to prevent races when threads within the same application post conflicting communication calls ( [START_REF]Message Passing Interface Forum[END_REF], p. 482). This should be checked above all for the fully multithreaded case (MPI THREAD MULTIPLE). This paper presents a static analysis to verify MPI Thread-level compliance required by an MPI+OpenMP application. Fig. 1 illustrates some of the possible issues related to MPI communications in a multithreaded context through three examples. MPI Allreduce in Listing 1.1 is called in a single block, MPI THREAD SERIALIZED then corresponds to the minimum level of compliance. However if the function f is called itself in a parallel construct, the collective is then executed in a nested parallel region, possibly leading to more than one concurrent call to this collective. This erroneous situation always occurs unless only one thread is created in the first parallel region or in both regions. Listing 1.2 illustrates a more complex case: two MPI Reduces are executed in single constructs in the same OpenMP parallel region. As the first construct contains a nowait clause, both MPI Reduce can be executed concurrently by different threads. This requires a thread-level equal to MPI THREAD MULTIPLE, assuming the communicators used by the two collectives are different. If they are identical, the code is incorrect. In Listing 1.3, function f is compliant with the MPI THREAD FUNNELED level. However, if the master directive is replaced by a single directive, the MPI THREAD SERIALIZED level is the minimum thread-level required. Thus, these examples illustrate the difficulty for a developer to ensure that MPI calls are correctly placed inside an hybrid MPI+OpenMP application whatever the required thread-level support.

This paper proposes a static analysis that helps the application developer to check which thread-level support is required for a specific code. For this purpose, we suppose the programs are SPMD (Single Program Multiple Data) MPI programs. It means that every MPI rank calls the same functions in the same order. This covers a large amount of scientific simulation applications for High-Performance Computing. We integrated our analysis in the GCC plugin PAR-COACH [START_REF] Saillard | PARCOACH:Combining Static and Dynamic Validation of MPI Collective Communications[END_REF][START_REF] Saillard | Static/Dynamic Validation of MPI Collective Communications in Multi-threaded Context[END_REF] and we designed it to be compatible with other dynamic tools. Our paper makes the following contributions:

-Analysis to check the conformance of MPI+OpenMP codes with any MPI thread level (including MPI THREAD MULTIPLE level) defined in the MPI-2 standard and code transformation to verify the non-compliance at runtime. -Full implementation inside a production compiler (GCC).

-Experimental results on multiple benchmarks and production applications.

-Functional integration with existing dynamic debugging tools (our approach is designed to be complementary to existing dynamic PMPI-based debugging tools like MUST [START_REF] Hilbrich | Runtime MPI Collective Checking with Tree-based Overlay Networks[END_REF])

This paper is organized as follows: Section 2 summarizes the related work on debugging of MPI and hybrid MPI+OpenMP applications, focusing on MPI thread-level compliance. Section 3 describes the basis of our approach. Then Section 4 exposes our static analysis detecting the thread-level compliance. Section 5 illustrates our approach on experimental results and finally Section 6 concludes.

Related Work

As most HPC applications are parallelized with MPI, a lot of work has been done to help programmers to debug MPI applications (TASS [START_REF] Siegel | Automatic Formal Verification of MPI Based Parallel Programs[END_REF], DAMPI [START_REF] Vo | A Scalable and Distributed Dynamic Formal Verifier for MPI Programs[END_REF], MPI-CHECK [START_REF] Luecke | MPI-CHECK: a tool for checking Fortran 90 MPI programs[END_REF], Intel Message Checker [START_REF] Desouza | Automated, Scalable Debugging of MPI Programs with Intel Message Checker[END_REF], Marmot [START_REF] Krammer | MARMOT: An MPI Analysis and Checking Tool[END_REF], Umpire [START_REF] Vetter | Dynamic Software Testing of MPI Applications with Umpire[END_REF], MUST [START_REF] Hilbrich | Runtime MPI Collective Checking with Tree-based Overlay Networks[END_REF], MPICH [START_REF] Falzone | A Portable Method for Finding User Errors in the Usage of MPI Collective Operations[END_REF]). Existing tools, static or dynamic, are able to detect the line in the source code where an error occured but rarely the line responsible for this situation. Although the compile-time offers the possibility to detect and correct possible errors earlier than at runtime, few tools rely on purely static analysis because of the combinatory aspect of methods used. We have developed in previous work a GCC plugin named PARCOACH [START_REF] Saillard | PARCOACH:Combining Static and Dynamic Validation of MPI Collective Communications[END_REF][START_REF] Saillard | Static/Dynamic Validation of MPI Collective Communications in Multi-threaded Context[END_REF], to statically detect MPI collective errors in MPI and MPI+OpenMP programs. It combines compile-time code analysis with an instrumentation to prevent the application from deadlocking. This approach avoids systematic instrumentation, highlights conditionals that can lead to a deadlock and issues warnings with precise information.

One of the MPI challenges is its interoperability with other programming models. Even if it is now possible to profile and visualize profiles and traces for MPI+OpenMP programs, debugging tools especially those detecting thread levels compliance are practically non-existent. To our knowledge, Marmot [START_REF] Hilbrich | Detection of Violations to the MPI Standard in Hybrid OpenMP/MPI Applications[END_REF] is the only tool that provides a support for detecting violations in MPI+OpenMP programs. Marmot uses the MPI profiling interface (PMPI) to introduce artificial data races only occuring when some constraints are violated and detect them with the Intel Thread Checker tool. The authors define five restrictions for hybrid MPI applications based on the definition of the thread levels mentioned in the MPI standard. The fifth restriction is the non-violation to the provided thread level. However, as Marmot only relies on profiling, it may find for one run that the program is non compliant to a given thread level, and for another run find its compliance (so defining a compliance per run). The same happens for bugs, where detection may require many runs in a profile-only approach. On the contrary, PARCOACH finds statically the possible non-compliance of the code, pinpointing non-compliant code fragments and situations. The runtime instrumentation only checks whether these situations occur.

Our static analysis verifies the thread-level compliance of hybrid applications. The analysis proposed does not depend on one particular run and finds all possible situations of non-compliance to a given thread level. As it is conservative, it can be complemented by an instrumentation phase that checks the occurence of these situations. An essential part of the static analysis consist in determining the multithreaded context in which MPI calls (Point-to-point and collectives) are performed. The method described in this section computes a parallelism word to characterize this context in each point of the function analyzed.

Parallelism Words Construction

The analysis operates on the code represented as an intermediate-code form. We consider the program is represented as a control-flow graph (CFG), built in almost all compilers. The compile-time verification then consists in a static analysis of the CFG for each function of a program. The CFG is defined as a directed graph with artificial entry and exit nodes. Each node corresponds to a basic block and has a set of successors and predecessors. The CFG is augmented to highlight nodes containing MPI calls (collectives and P2P). As for the GCC compiler, OpenMP directives are put into separate basic blocks. Hence new nodes are added for explicit and implicit thread barriers. For sake of clarity, implicit thread barriers at the end of parallel regions are denoted by end parallel. To highlight the thread context in which an MPI call is performed, we extend the notion of parallelism words defined in [START_REF] Saillard | Static/Dynamic Validation of MPI Collective Communications in Multi-threaded Context[END_REF], taking into account the needs of a thread level compliance analysis. The parallelism word of a basic block is the sequence of OpenMP parallel constructs (pragma parallel, single, . . . ) surrounding this block and the barriers traversed from the beginning of a function to the block. Parallel regions containing the block are denoted by P i , with i the id of the basic block with the OpenMP construct. Similarly, regions executed by the master thread are denoted by M i and other single threaded regions are denoted S i . Finally, barrier corresponds to B. OpenMP defines a perfectlynested parallelism, thus the control flow has no impact on the parallelism word. Each node (basic block) n is associated to a parallelism word denoted pw [n]. With a depth-first search starting at the entry node, each node then sets its parallelism word depending on its predecessor and the OpenMP directives it contains. P is added when a parallel region is encountered, S is added when a single, section or task region is traversed, M is added when a master construct is traversed and B is added when an implicit or explicit thread barrier is met. Figure 2 shows examples of CFG with their associated parallelism words.

Parallelism Words Analysis

The automaton Figure 3 defines the possible parallelism words. Nestings forbidden by the OpenMP specification (SS, M S,...) are not considered by the automaton. If the target obtains such forbidden nested regions, our analysis returns the error message: invalid state, error. The language of accepted parallelism words will depend on the specified thread level. As we check each function independently, the level of parallelism in which a function is called is unknown.

To provide an accurate picture of the level of thread parallelism in which function occurrence is called, the statistics on the NAS Parallel Benchmarks multizone (NASPB-MZ) using class B [18] have been collected and are shown in Table 1 per thread, in each process. We notice that functions are mainly called within one level of multithreading. Thus to consider all possible initial conditions, each callsite is instrumented in order to capture the initial parallelism word of each function. This word corresponds to a prefix P i for all basic blocks of the called function and defines an initial state in Automaton Figure 3 (all states are possible initial states). The user can choose the initial state at compile-time. The following section describes the analysis checking the thread-level compliance based on the parallelism words of the basic blocks containing MPI communications.

Thread-Level Compliance Checking

This section describes how the non-compliance of thread levels can be detected at compile-time. For that purpose we use parallelism words introduced in the previous section to check the placement of MPI calls within a process.

Static Analysis and Interface to Dynamic Checkings

For each possible thread level we define a language of valid parallelism words based on the automaton Fig. 3. For a given basic block, its parallelism word consists in the prefix (obtained from the callsite of the function or user-defined) and the word computed from previous analysis. The analysis verifies if nodes containing MPI calls (P2P and collectives) are associated with an accepted word. Thread barriers can be safely ignored as they do not influence the level of thread parallelism. In case of the detection of a possible error, a warning related to the initial level with the name of the call is returned to the programmer. Alg. 1 takes as input the CFG and the language L of correct parallelism words and outputs the sets S and S ipw . These sets respectively contain the nodes violating the input language and the nodes that dominate these nodes before the execution/control flow changes. This set will be given as one of the input parameters of the dynamic analysis. In the algorithm, line 5, the node u corresponds to the node preceeding n in the CFG and that is the immediate successor of a control flow node (with two successors) or of a pragma node (changing the parallelism word). The nodes in the set S ipw correspond to execution points where compliance should be tested at runtime, in order to handle possible false-positives detected statically. A unique parallelism word is computed at runtime and updated after each OpenMP construct. Compared to the compile-time parallelism words, parallel regions created with only one thread correspond to the parallelism word . This implies that such region has no impact on the current multithreaded context. The insertion of such computations and checks can be conducted in tools such as MUST [START_REF] Hilbrich | Runtime MPI Collective Checking with Tree-based Overlay Networks[END_REF], Marmot [START_REF] Krammer | MARMOT: An MPI Analysis and Checking Tool[END_REF] or following the techniques proposed in [START_REF] Saillard | Combining static and dynamic validation of MPI collective communications[END_REF].

Algorithm 1 Detection of parallelism words for multithreaded regions

1: function Multithreaded regions(G = (V, E), L) G: CFG, L: language 2:
Sipw ← ∅ , S ← ∅ 3:

for each n ∈ V |n contains a MPI call do 4:

if pw[n] ∈ L then 5:

u ← Node that dominates n before execution/control flow changement 6:

S ← S ∪ {n}, Sipw ← Sipw ∪ u 7:

end if 8:

end for 9:

Output nodes in S as warnings 10: end function

MPI THREAD SINGLE

By setting the MPI THREAD SINGLE level, the user ensures only one thread will execute MPI calls ( [START_REF]Message Passing Interface Forum[END_REF], p. 486). This means all MPI calls should be performed outside multi-threaded regions. Thus all nodes of the CFG containing a MPI call must be associated with an empty parallelism word. The language L of accepted parallelism words is then defined by L = { }. Algorithm 1 with L = { } returns the non-compliant MPI calls (set S).

MPI THREAD FUNNELED

The use of MPI THREAD FUNNELED level means the process may be multithreaded but the application must ensure that only the thread that initialized MPI can make MPI calls ( [START_REF]Message Passing Interface Forum[END_REF], p. 486). For this level, State 3 in Automaton 3 is the accepting state and the language L = (P B * M ) + describes the accepted words. With Algorithm 1 and L, our analysis detects MPI calls that are not executed in a master region.

MPI THREAD SERIALIZED

The MPI THREAD SERIALIZED level means the process may be multi-threaded but only one thread at a time can perform MPI calls ( [START_REF]Message Passing Interface Forum[END_REF]). The accepting states in Automaton 3 are states 2 and 3. Thus, the language L = (P B * S|P B * M ) * describes the accepted words. This language contains parallelism words ending by S or M without a repeated sequence of P . Critical sections and locks are not supported here and is part of our future work.

To verify the compliance of this level, Algorithm 1 is used to make sure all MPI calls are performed in a monothreaded context. Different MPI calls in the same monothreaded region are sequentially performed as only one thread executes it. However, calls in different monothreaded regions may be called simultaneously if monothreaded regions are executed in parallel (no thread synchronization between monothreaded regions). Special care is requested for MPI collective operations. All MPI processes should execute the same sequence of MPI collective operations in a deterministic way. That means there is a total order between MPI collective calls. Algorithm 2 shows the detection of concurrent calls. It takes as input the CFG and outputs two sets: S and S cc . When nodes containing a MPI call with the same number of B are detected these nodes are put in the set S and the nodes that begin the monothreaded regions are put in the set S cc for the dynamic analysis. A warning is issued for nodes in S.

Algorithm 2 Detection of potential concurrent calls

1: function Concurrent calls(G = (V, E)) G: CFG 2: Scc ← ∅, S ← ∅ 3:
Remove loop back edges 4:

if ∃ u, v ∈ nodes in concurrent monothreaded regions then 5:

i, j ← nodes immediate successors of nodes creating monothreaded regions 6:

S ← S ∪ {u, v}, Scc ← Scc ∪ {i, j} 7:

end if 8:

Output nodes in S as warnings 9: end function To dynamically verify the total order of MPI collective sequences in each MPI process, validation functions are inserted in nodes in the sets S ipw and S cc generated by Algorithms 1 and 2: CC ipw and CC cc . Function CC ipw detects incorrect execution parallelism words and Function CC cc detects concurrent collective calls. In Figure 2, nodes 4 and 6 have the same number of thread barriers in their parallelism words (node 4: P 2 S 3 , node 6: P 2 S 5 ) so the collective operations involved are potential concurrent collective calls. Indeed, the nowait clause remove the implicit barrier at the end of the first single region. The algorithm outputs a warning for collective calls located nodes 4 and 6 (S = {4, 6}) and flags nodes 4 and 6 for dynamic checks (S cc = {4, 6}). CC cc functions are then inserted in nodes 4 and 6.

MPI THREAD MULTIPLE

This level is the least restrictive level. It enables multiple threads to call MPI with no restriction ( [START_REF]Message Passing Interface Forum[END_REF], p. 486). However MPI calls should be thread safe, meaning that when two concurrently running threads make MPI calls, the outcome will be as if the calls executed sequentially in some order. The verification of this level follows the same analyses as for the MPI THREAD SERIALIZED level.

Experimental results

This section is intended to show the impact of our analysis on the compilation time. For that purpose we present experimental results obtained on the NAS Parallel benchmarks multizone (NAS-MZ v3.2) using class B [18], five MPI+OpenMP Coral benchmarks [19] (AMG2013, LULESH, HACC, SNAP, miniFE) and a production test case named HERA [START_REF] Jourdren | HERA: A hydrodynamic AMR Platform for Multi-Physics Simulations[END_REF], which is a large multiphysics 2D/3D AMR hydrocode platform. To highlight the functionality of our analysis, we created a microbenchmark suite called BenchError containing five hybrid programs that violate thread level constraints (coll single, coll funneled, coll serialized, p2p multiple) and contain MPI collective (coll deadlock) errors. All compilation experiments were conducted on the Tera-100 supercomputer (peak performance of 1.2 PFlops) and computed with BullxMPI 1.1.16.5.

Functionnalities of the Analysis

We extended PARCOACH, a GCC plugin located in the middle end of the compilation chain after the CFG generation and before OpenMP directives transformation. Hence the plugin is language independent allowing the verification of programs written in C, C++ and Fortran. Our analysis is therefore simple to deploy in existing environment as it does not modify the whole compilation chain. The analysis issues warnings at compile-time with potential error information (lines of MPI calls, line where the dynamic check is inserted,...). The following example shows what a user can read on stderr when compiling the program coll serialized corresponding to Listing 1.2. In this example, MPI Reduce calls were done on different communicators. As our analysis does not check communicators, both single regions are instrumented to check if the non-compliance of the thread level is confirmed at runtime. In comparison, the error message returned by Marmot at runtime is the following:

Marmot finds that the code should be executed within the MPI THREAD FUNNELED thread level whereas PARCOACH finds the level MPI THREAD MULTIPLE. The reason comes from the fact that Marmot detects conformance w.r.t. one execution, and in particular to one parallel schedule. During the execution monitored by Marmot, the single constructs are executed by the master thread leading to a serialized sequence of these constructs. However, from a conformance point of view, this is incorrect and the thread level MPI THREAD MULTIPLE as analyzed by PARCOACH should be chosen.

Static Analysis Results

Table 2 shows the language and the number of lines of each benchmark we tested. The 4 th and 5 th columns depict the thread level provided (level actually returned to the user, might be lower than the desired level, depending on the MPI implementation) and the minimum thread level required by the application (thread-level the user should use). The last column displays the compliance our analysis returned. Our analysis was able to find the thread-level non-compliance in our microbenchmark suite. Notice that the MPI THREAD MULTIPLE level was not supported by the MPI implementation we used. For each benchmark, the overhead obtained at compile-time (serial compilation) is presented Figure 4. This overhead is acceptable as it does not exceed 6%. PARCOACH issues warnings for potential MPI collective errors within an MPI process and between processes. The type of each potential error is specified (collective mismatch, concurent calls in an MPI process,...) with the names and lines in the source code of MPI collective calls involved. Table 3 shows the number of static MPI collective calls and the number of nodes in the set S found by PARCOACH (algorithms 1 and 2 of our analysis). The 4th column depicts the percentage of the benchmarks functions instrumented. We notice a good impact of the static analysis on the selective instrumentation. The two last columns give the number of expected errors and the number of errors actually found.

Conclusion and Future Work

Augmenting MPI applications with OpenMP constructs is one possible approach to face exascale systems. But the development of such hybrid applications requires effective debugging methods to assist programers. In this paper, we presented a compiler analysis to verify the MPI thread-level compliance of C/C++ and Fortran MPI+OpenMP codes. The analysis proposed finds the right MPI thread level to be used and identifies code fragments that may prevent conformance to a given level. We have shown a small impact on compilation-time with an overhead lower than 6%. For future work, our analysis could be extended to include critical sections and locks. Furthermore, it could be integrated into existing tools like Marmot or MUST to cover other errors like calls arguments (e.g., communicators) or to report warnings concerning the execution path responsible for bugs related to thread-level MPI compliance.

Listing 1. 1 .

 1 v o i d f ( ) { #p r a g m a o m p p a r a l l e l { / * * * / #p r a g m a o m p s i n g l e { M P I _ A l l r e d u c e ( . . )

1 v o i d f ( ) { 2 #p r a g m a o m p p a r a l l e l 3 { 4 #p r a g m a o m p s i n g l e \ 5 n o w a i t 6

 246

Fig. 1 .

 1 Fig. 1. MPI+OpenMP examples showing different uses of MPI calls.

3 5: 3 Fig. 2 .

 332 Fig. 2. Control Flow Graph and parallelism words of Listings 1.2 and 1.3

Fig. 3 .

 3 Fig.3. Automaton of possible parallelism words. Nodes 0, 2 and 3 correspond to code executed by the master thread or a single thread. Nodes 1 and 4 correspond to code executed in a parallel region, and 5 and 6 to code executed in nested parallel region.

  in function 'f': Warning: PARCOACH: possible non-compliance of MPI_THREAD_SERIALIZED level. Potential concurrent coll. calls within a process : MPI_Reduce l.11 may be called simultaneously with MPI_Reduce l.6 PARCOACH: Minimum thread-level required: MPI_THREAD_MULTIPLE PARCOACH inserted a check after the single directive l.4 | the single directive l.9

Fig. 4 .

 4 Fig. 4. Overhead of average compilation time

Table 1 .

 1 Level of threads parallelism at function entries for NASPB-MZ

	Benchmark # function calls	# calls in state 0,2,3	# calls in state 1,4	# calls in state 5,6
	BT-MZ	396,918,403	45,379	396,873,024	0
	SP-MZ	15,479,425	116,161	15,363,264	0
	LU-MZ	3,017,513	40,745	2,976,768	0

Table 2 .

 2 Compliance Results

	Benchmark	Language	Lines of code	Thread level Thread level Compliant provided required
	BT-MZ | SP-MZ	Fortran 6,779 | 4,862	SINGLE	SINGLE	yes
	LU-MZ	Fortran	6,542	SINGLE	SINGLE	yes
	AMG2013 | LULESH	C	75,000 | 5,000	SINGLE	SINGLE	yes
	miniFE | HACC	C++ 50,000 | 35,000	SINGLE	SINGLE	yes
	SNAP	Fortran	3,000	SINGLE	SINGLE	yes
	HERA	C++	500,000	SERIALIZED SERIALIZED	yes
	coll single	C	29	SINGLE	FUNNELED	no
	coll funneled	C	36	FUNNELED SERIALIZED	no
	coll serialized	C	47	SERIALIZED MULTIPLE	no
	coll deadlock	C	38	FUNNELED	FUNNELED	yes
	p2p multiple	C	45	SERIALIZED MULTIPLE	no

Table 3 .

 3 Debugging Results

	Benchmark	# collective # nodes in % instrumented # expected # errors calls S functions errors found
	BT-MZ | SP-MZ	15	7	8,57%	0	0
	LU-MZ	20	7	8,82%	0	0
	AMG2013	86	75	13.33%	0	0
	LULESH | miniFE	3 | 4	1 | 6	1.44% | 2.56%	0	0
	HACC | SNAP	26 | 9	11 | 13	1.41% | 10%	0	0
	HERA	574	375	<1%	0	0
	coll single | coll funneled	1	1	100%	1	1
	coll serialized	2	2	100%	1	1
	coll deadlock	1	1	100%	1	1
	p2p multiple	0	2	100%	1	1