Antoine Boutet
email: antoine.boutet@insa-lyon.fr

Florestan De Moor
email: florestan.de-moor@ens-rennes.fr

Davide Frey
email: davide.frey@inria.fr

Rachid Guerraoui

Anne-Marie Kermarrec
email: anne-marie.kermarrec@mediego.com

Antoine Rault

Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter!

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

User-based collaborative filtering exploits the opinions of users (stored in a profile) to identify the correlations in terms of interests between users. Albeit other variants of collaborative filtering exist, user-based systems remain important due to their simplicity and their availability in a number of opensource machine learning frameworks [START_REF]Mahout[END_REF]. Moreover, their focus on users makes them particularly interesting in environments where the set of items to be recommended changes frequently, for example in news or media content. The ability to scale Knearest-neighbor (KNN) computations [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] (i.e., building the graph that captures the correlation in term of interests between users according to a similarity metric) also makes user-based CF a privileged tool to cope with this highly dynamic context.

Recent research has shown, however, that user-based collaborative filtering [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF], [START_REF] Castelluccia | Betrayed by your ads![END_REF] represents a preferred target for attackers that wish to learn sensitive information on users. In this paper, we investigate this issue by focusing on an attack introduced by [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF]. The attacker targets user-based collaborative filtering by creating a number of fake identities (i.e., Sybil attack) to extract information about a user's profile, starting from already available auxiliary information. In the domain of cross-company recommendations, for example, the attacker may be a company that wishes to learn user preferences on items managed by its competitors.

Even if it introduced the attack, [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF] did not evaluate it. In a recent paper, we carried out an analysis showing its limited effectiveness with a specific metric [START_REF] Frey | Collaborative filtering under a sybil attack: Analysis of a privacy threat[END_REF]. In this paper we partially correct the conclusions of [START_REF] Frey | Collaborative filtering under a sybil attack: Analysis of a privacy threat[END_REF] by showing that the attack is indeed effective, but that it can be counteracted by specific similarity metrics.

More precisely, we enrich the state-of-the-art on the attack of [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF] with two main contributions. First we carry out a thorough evaluation with a variety of similarity metrics on multiple data sets on Mahout [START_REF]Mahout[END_REF], an open-source machinelearning framework. We show that the effectiveness of the attack strongly depends on the similarity metric used to build the KNN graph. Moreover, we observe that existing similarity metrics exhibit an inherent trade-off between attack resistance and recommendation quality. Second, we start from this observation and propose a novel, generic, similarity metric that can turn existing metrics into attack-resistant ones. While our approach uses two phases, it uses them to compute similarity and therefore differs significantly from algorithms [START_REF] Zhao | Interest before liking: Two-step recommendation approaches[END_REF], [START_REF] Zhao | Improving diversity of userbased two-step, recommendation algorithm with popularity normalization[END_REF] that compute ratings in two steps. We apply our new generic metric to Cosine similarity, the best performing in terms of recommendation quality, and turn it into an attack-resistant metric without hampering recommendation quality. We show that our similarity-based protection allows no more than 60% of the Sybil users to succeed in a targeted attack with an ideal neighborhood, and outperforms a state-of-the-art privacypreserving recommender [START_REF] Lu | A security-assured accuracy-maximised privacy preserving collaborative filtering recommendation algorithm[END_REF] on a generic attack.

II. BACKGROUND

The collaborative nature of most recommendation systems [START_REF] Linden | Collaborative recommendations using item-to-item similarity mappings[END_REF], [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF], constitutes both a strength and a weakness. On the one hand, collaborative filtering can recommend complex objects that have no easily exploitable content associated with them. On the other hand, the fact that collaborative filtering combines the opinions of different users has raised concerns about the privacy threats it poses. As the data exploited by recommenders gets more and more into the personal sphere (e.g. medical data [START_REF] Hoens | Reliable medical recommendation systems with patient[END_REF]), collaborative filtering faces an inherent trade-off between accuracy and privacy [START_REF] Machanavajjhala | Personalized social recommendations: accurate or private[END_REF], [START_REF] Ramakrishnan | Privacy risks in recommender systems[END_REF], [START_REF] Jeckmans | Privacy in recommender systems[END_REF].

This has led to two main lines of research: identifying potential threats and attacks, and providing attack resistance.

a) Attacks against Recommenders: We can distinguish two types of attacks on recommenders: passive, and active. In the former, the attacker simply tries to learn information about other users through legitimate means. In the latter, the attacker carries out operations that go outside the standard behavior of a user like in the attack of this paper.

BlurMe [START_REF] Weinsberg | BlurMe: Inferring and obfuscating user gender based on ratings[END_REF] and [START_REF] Bhagat | Recommending with an agenda: Active learning of private attributes using matrix factorization[END_REF] present passive attacks that extract demographic information such as ethnicity or gender from the ratings in a recommender. BlurMe also proposes an obfuscation mechanism to limit the impact of such an attack. [START_REF] Castelluccia | Betrayed by your ads![END_REF] shows that targeted and personalized ads contain valuable information that allows accurate reconstruction of users' interest profiles. [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF] analyzes, instead, how auxiliary information, obtained from the system itself or from external sources, makes it possible to extract individual user preferences from otherwise aggregate information such as related-item lists or item-covariance matrices.

The attack we consider in this paper falls instead in the active category. In this context, [START_REF] Bhagat | Recommending with an agenda: Active learning of private attributes using matrix factorization[END_REF] develops an approach that maximizes the ability to learn new information by asking users to rate specific items. Pistis [START_REF] Li | Pistis: A privacypreserving content recommender system for online social communities[END_REF] considers an attacker that attempts to copy the profile of the target user and proposes a mechanism that limits its impact by expressing ratings on privacy-preserving groups of items. Sybil attacks employ several fake identities like Eclipse attacks in the Bitcoin network [START_REF] Heilman | Eclipse attacks on bitcoin's peer-to-peer network[END_REF]. Shilling attacks [START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF] adopt this approach to influence the output of the recommender, for example by biasing it towards a particular brand or product [START_REF] Gunes | Shilling attacks against memory-based privacy-preserving recommendation algorithms[END_REF], [START_REF] Seminario | Attacking item-based recommender systems with power items[END_REF]. The attack we consider in this paper instead uses it to implement a stronger version of the attack in [START_REF] Li | Pistis: A privacypreserving content recommender system for online social communities[END_REF]. This Sybil attack was initially introduced by [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF] and later partially evaluated by [START_REF] Frey | Collaborative filtering under a sybil attack: Analysis of a privacy threat[END_REF] with Cos-overlap. Our results go beyond the partial analysis of [START_REF] Frey | Collaborative filtering under a sybil attack: Analysis of a privacy threat[END_REF], highlight the tradeoff between privacy and recommendation quality, and provide a solution to it.

b) Privacy Protection in Recommenders: Protecting collaborative filtering from the above attacks constitutes a promising research direction [START_REF] Ozturk | From existing trends to future trends in privacypreserving collaborative filtering[END_REF]. The first attempts to provide privacy-preserving recommenders focused on decentralized solutions based on homomorphic encryption [START_REF] Canny | Collaborative filtering with privacy via factor analysis[END_REF], anonymization [START_REF] Boutet | Freerec: An anonymous and distributed personalization architecture[END_REF], or profile obfuscation [START_REF] Berkovsky | Enhancing privacy and preserving accuracy of a distributed collaborative filtering[END_REF]. In a centralized setting, [START_REF] Parameswaran | Privacy preserving collaborative filtering using data obfuscation[END_REF] evaluates the feasibility of applying several data obfuscation techniques. [START_REF] Agrawal | Privacy-preserving data mining[END_REF] and [START_REF] Polat | Svd-based collaborative filtering with privacy[END_REF] proposed injecting noise into user profiles, but they were later shown to be vulnerable to statistical attacks that filter out the random noise to reconstruct the missing information [START_REF] Rault | On the design and quantification of privacy preserving data mining algorithms[END_REF], [START_REF] Huang | Deriving private information from randomized data[END_REF], [START_REF] Kargupta | On the privacy preserving properties of random data perturbation techniques[END_REF]. Moreover, all the above solutions remain vulnerable to attacks that combine recommended items with auxiliary information available through external sources, like the one we study in this paper.

Systems that apply differential privacy only to neighborhood computation [START_REF] Zhu | Differential privacy for neighborhood-based collaborative filtering[END_REF] exhibit the same problem. But some authors have also proposed systems that incorporate randomization and ensure differential privacy when they generate recommendations [START_REF] Boutet | Privacypreserving distributed collaborative filtering[END_REF], [START_REF] Mcsherry | Differentially private recommender systems: Building privacy into the netflix prize contenders[END_REF]. In [START_REF] Boutet | Privacypreserving distributed collaborative filtering[END_REF], the authors demonstrate that their approach can effectively counteract a Sybil-based censorship attack. However, its effectiveness against an attacker equipped with external auxiliary information remains unclear.

[29] considers the same Sybil attack as studied in this paper and proposes PPNS. In [START_REF]An accuracy-assured privacy-preserving recommender system for internet commerce[END_REF] the same authors provide a different version of PPNS that should provide better attack resistance but lower recommendation quality. But in Section VII-F, we show that our approach significantly outperforms PPNS.

Finally, [START_REF] Resnick | The influence limiter: Provably manipulationresistant recommender systems[END_REF] proposes a reputation score that aims to count a new rating of a neighbor only if this user rated sufficiently many items in common with the targeted user. In this paper, we consider instead an adversary that clones a part of the profile of the target user. Consequently, [START_REF] Resnick | The influence limiter: Provably manipulationresistant recommender systems[END_REF] is complementary to our solution and not a concurrent approach.

III. SYSTEM MODEL

We consider a recommender based on user-based collaborative filtering, a scheme implemented in many machinelearning frameworks. For each user, u, the system maintains a user-profile data structure which collects the mapping between users, items, and the associated numerical scores (e.g. 1 to 5). A user-based collaborative-filtering system relies on a k-nearest-neighbor (KNN) algorithm [START_REF] Boutet | Being prepared in a sparse world: The case of knn graph construction[END_REF] that identifies for each user, the k most similar other users according to a similarity metric. We consider the commonly used similarity metrics in user-based collaborative filtering. After identifying u's neighbors, the system ranks the items these neighbors have rated and recommends to u the top-ranking ones to which she has not yet been exposed.

We consider an adversary targeting a single user and which aims to extract information from the recommender [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF]. Like [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF], we assume the adversary has access to a subset of the target user's ratings, which we name auxiliary information. As described by [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF], the adversary can obtain auxiliary information about the target in several ways. Many websites like Last.fm offer publicly available information about the browsing history of a user. Others, like Amazon.com, interface with social networks to post information like "I just bought item X". But an even more relevant threat arises for SMEs that offer recommendation services to multiple clients over different domains. Consider two client companies, for example online sport shops, that exploit the company's recommendation service. Each sport shop knows the ratings of its own customers on the items it sells, but it may be interested in knowing which items sold by the competitor are interesting for its own customers. The sport shop may thus play the role of an attacker whose auxiliary information consists of its own subset of the profile of a given customer. Existing work [START_REF] Castelluccia | Betrayed by your ads![END_REF] studies this kind of threat in the context of targeted advertisement.

The adversary has also the ability to create a number of fake identities (i.e., Sybils). In the real world, this may be made complex by the need to purchase items, confirm accounts, or perform other costly actions to fill Sybil profiles. In this paper, we simply assume that the adversary can give each of its fake identities a user-profile consisting of a subset of items and ratings associated with the target. Finally, we also assume that the adversary knows the value of k (i.e., the size of neighborhoods in the KNN algorithm) which allows her to create an appropriate number of Sybils.

We consider an attack successful when (i) Sybil nodes manage to obtain neighborhoods that consist only of the target node and other Sybil nodes, and/or (ii) they receive recommendations for items that appear in the target profile.

IV. EXPERIMENTAL PROTOCOL

We implemented the Sybil attack on top of Mahout [START_REF]Mahout[END_REF], a popular machine-learning framework developed by the Apache Foundation. This allows us to analyze the Sybil attack on a state-of-the-art user-based collaborative-filtering system.

In order to effectively implement the attacks, we slightly modified Mahout to model the behavior of Sybil users. Our modified Mahout implementation, as well as the code, and the scripts for running our experiments are publicly available [1]. We used publicly available anonymized real datasets exempt form ethical concerns.

A. Similarity Metrics

Section V evaluates the attack on seven similarity measures: the well-known cosine-similarity metric in three variants, two variants of the similarity measure from [START_REF] Boutet | WHATSUP: A decentralized instant news recommender[END_REF], the Jaccard index, and the Pearson correlation coefficient [START_REF] Tan | Introduction to data mining[END_REF]. Cosine similarity reflects the similarity between two profiles (i.e. vectors of tuples representing the scores associated with items) by measuring the cosine of the angle between them. Jaccard considers the size of the intersection divided by the size of the union of two profiles, regardless the score associated with items. Finally, Pearson correlation consists of the covariance of the two profiles divided by the product of their standard deviations and turns out to be equivalent to a cosine similarity applied to the profiles obtained after centering the scores around their averages. Pearson correlation produces outcomes between -1 and +1 inclusive, while Cosine and Jaccard give values in [0; +1]. Their formal definition are available in [START_REF] Frey | Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter![END_REF].

We also consider two variants of cosine similarity: Cosoverlap and CosineAvg. The former computes the norms of the two profiles by counting only the items that are common to both of them while the latter uses the average rating of a user for non-rated items.

Cos-overlap(u, n) = ru•rn i∈Iu,n (r u,i ) 2 × i∈Iu,n (r n,i ) 2 , CosineAvg(u, n) = i∈Iu∪In ru,i × rn,i ru rn ; rx,i = r x,i if i ∈ Ix rx if i ∈ Ix
where r u,i (resp. r n,i ) indicates the rating of user u (resp. n) on item i, r u (resp. r n ) the average of user u's (resp. n's) ratings, and I u,n the set of items rated by both u and n. Finally, we consider two variants of the asymmetric similarity measure proposed in [START_REF] Boutet | WHATSUP: A decentralized instant news recommender[END_REF]: WUP-u and WUP-n, from the name of the system in [START_REF] Boutet | WHATSUP: A decentralized instant news recommender[END_REF]. These restrict their attention to the items rated by both users for the scalar product and for the norm of one of the two profiles depending on the variant.

Given a user u and a potential neighbor n, the first variant, WUP-u, considers only the items rated by u that are also rated by n (I u,n ), and all the items rated by n (I n ).

WUP-u(u, n) = i∈Iu,n r u,i ×r n,i i∈Iu,n (r u,i ) 2 × i∈In (r n,i ) 2 ,
The second variant, WUP-n, considers all the items rated by u (I u ) and only the items rated by n that also are also rated by u (I u,n ) and can be obtained by exchanging u and n in the above. Finally, we introduce our novel metric in Section VI and evaluate the attack on it in Section VII.

B. Datasets

We ran our experiments on the three datasets listed in Table I. ML-100k (called ML-1 in the following) is a trace from the MovieLens [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF] online movie-recommendation service. Jester-1-1 is a trace from the Jester [START_REF] Goldberg | Eigentaste: A constant time collaborative filtering algorithm[END_REF] online jokerecommendation service. It is the first third of Jester's dataset-1. MovieTweetings (MT) is a collection of movie ratings from IMDb users expressed as well-structured tweets [START_REF]Movietweetings[END_REF]. We use the three parts of the dataset as one, and make our own splits where needed. We remove 23 erroneous ratings as they do not respect the expected 10-star rating format. Consequently, this also removes 3 users having only such erroneous ratings. ML-1 and Jester only contain information on subsets of users who rated at least 20 and 36 items respectively, which makes them less sparse than most real-world datasets. To investigate the impact of sparsity, we derive a number of variants from ML-1 with different levels of sparsity. Starting from ML-1, we progressively remove randomly chosen ratings and obtain four additional datasets (numbered ML-2 to ML-5). Table II details the number of ratings and the sparsity, expressed as the percentage of missing ratings in the useritem matrix, for each variant. For space reasons, we present plots only for ML and MT, and only discuss Jester in the text.

C. Auxiliary Information

The auxiliary information available to the adversary consists of a list of items and the associated ratings expressed by the target. We consider configurations with varying percentages of the target profile as auxiliary information. We observe that this is a relatively strong assumption on the prior knowledge held by the attacker. But it corresponds to the case of ratings available to a company in a cross-company recommendation system. In other cases, external available information is much less precise. For example, social networks may publish updates such as "Tom just saw Highlander" without specifying a rating.

The goal of the adversary consists in determining whether the target user liked a particular item, i.e. gave it a high-enough rating (≥ 3 in ML, ≥ 0 in Jester, and ≥ 6 in MT).

D. Assessment Metrics

We assess the Sybil attack according to three metrics. The first evaluates the ability of Sybils to build the ideal neighborhood associated with the target to carry out the attack. As discussed earlier, this consists of the target user and k -1 Sybils. More precisely, we measure the fraction of Sybils that obtain such an ideal neighborhood. The two other metrics, yield and accuracy evaluate the outcome of the attack. Each Sybil attacking the target receives 5 recommendations from its neighborhood, consisting of the items that receive the highest predicted rating ûi , according to the following formula.

rs,i = rs + n∈Ns (r n,i -rn)Sim(s, n) n∈Ns |Sim(s, n)| ,
N s being the nearest neighbors of Sybil s. We then define yield as the number of distinct items recommended to a given Sybil, and accuracy as the fraction of these items that actually exist in the target's profile. Finally, we measure recommendation quality using the Root Mean Square Error (RMSE). To this end, we run 10-fold cross validation with a 90%-10% split. We build the KNN of each user on the training set and we issue recommendations to predict the ratings in the testing set. The RMSE measures how close recommendations are to the actual ratings of users in the testing set. For a given user u, it is thus defined as follows.

RMSE = n i=1 (r u,i -r u,i ) 2 n ; ru,i = n∈Nu Sim(u, n) * r n,i n∈Nu Sim(u, n) V. RESULTS
In this section, we analyze how similarity measures impact the success of the attack. For instance, a measure which drastically segregates users even with few changes in their profiles leaves enough room for the adversary to place its Sybil users around the target. In contrast, a similarity measure that does not differentiate among a large set of users will tend to provide similar scores to a number of potential neighbors in the KNN structure. This will make it more difficult for the adversary to create Sybil users that have only the target and other Sybils as potential neighbors.

To illustrate these differences among similarities, we computed the Complementary Cumulative Distribution Function (CCDF) of the similarity between all pairs of users for different similarity measures. Results (not shown for space reasons) suggest that the behaviors of the similarity measures can vary considerably in ML-1. The MovieTweetings dataset also exhibits significant differences between similarities, while in Jester, all similarities except Jaccard exhibit similar behaviors. The information in Table II, suggests that this difference results from the high density of Jester, with a sparsity value of only 27.53%, as opposed to values above 90% for ML-1 and MovieTweetings.

A. Similarity Metrics vs Sybil Attacks

We now start evaluating the effectiveness of the Sybil attack on recommenders based on the seven similarity metrics described in Section IV-D. Our results show that the attack succeeds to varying degree except with Cos-overlap. For these experiments, the auxiliary items available to the attacker consist of a random subset of the target's profile.

Figures 1 through 3 highlight a high variability of the attack's effectiveness. Figure 1 shows the percentage of sybil nodes that obtain their desired neighborhoods as a function of the fraction of auxiliary items in their possession. In Figure 1a, we can distinguish three groups of metrics. For the first group-Cosine, Jaccard, and WUP-n-knowing 20% of the items in the target profile allows each Sybil node to obtain a neighborhood that consists exactly of the target and k -1 other Sybils. The second group-Pearson, WUP-u, and CosineAvg-require instead as many as 80% or 90% of the target's items in order to achieve the same result. When knowing 30% of the items, Pearson and WUP-u only allow respectively 80% and 60% of the Sybils to build their target neighborhoods, while CosineAvg only provides the desired neighborhood to about 5% of the Sybils. Finally, the third group consists only of Cos-overlap: with this metric, only a few Sybils manage to obtain an ideal neighborhood even when they have as much as 90% of the target items in their profiles.

Figure 1b shows similar relative success rates, even though with lower absolute values. The first group, Cosine, Jaccard, and WUP-n allows Sybils to obtain ideal neighborhoods in the largest number of cases. The second group is slightly more resilient to the attack, while Cos-overlap makes it very hard for Sybils to obtain their ideal neighborhoods. In Jester, not shown for space reasons, the attack succeeds even with Cosoverlap, while Jaccard yields the worst attack performance. The reason for this behavior lies in the high density of Jester.

Figures 2 and3 provide a different perspective on these results by depicting respectively the yield and accuracy obtained by the attack as a function of the fraction of the target's profile available as auxiliary items. To measure these, we have each Sybil request 5 recommendations from its neighborhood. With 10 Sybils this gives a maximum possible yield of 50. For ML-1 and MovieTweetings (Figures 2a and2b obtains a high yield. In Figure 2a all the remaining metrics achieve a yield of around 5%, while in Figure 2b yield values range from 0 to 25%.

Figure 3 shows that yield negatively correlates with accuracy. In Figures 3a and3b, Cos-overlap allows Sybil nodes to obtain good predictions for a very small number of items (only 10% in ML-1 and close to 0 in MovieTweetings). The remaining lines in each plot follow the trend of Figure 1 pretty closely. In all three plots, Sybils obtain higher accuracy as the fraction of auxiliary items increase. With very high percentages of auxiliary items, accuracy decreases only because there profiles contain fewer and fewer items to guess. Finally, we observe that in Jester (not shown) Sybils obtain very high accuracy for pretty all metrics due to the high dataset density.

B. Recommendation Quality

We continue our analysis by showing that, for all the considered metrics, recommendation quality positively correlates with the effectiveness of the attack. To this end, Figure 4 depicts the root mean squared error (RMSE) obtained with each metric for varying neighborhood sizes in each of the datasets. Lower values mean better recommendations.

The plots show significant variability in performance depending on the metric and on the dataset. For ML-1, as in earlier plots, we can identify three groups of similarity metrics characterized by increasing levels of recommendation performance. The first group consists only of Cos-overlap. The good resilience to censorship exhibited by this metric in Section V-A comes at the cost of much poorer recommendation quality. By considering only the items that belong to both profiles being considered, Cos-overlap completely ignores the important distinction between users with specific-and thus useful in terms of recommendation-interests, and hubs with very unspecific behaviors. The second group of metrics, consisting of Pearson, WUP-u, and CosineAvg, exhibits significantly better performance with a mean absolute error of about 0.85 and an RMSE of 1.1 with k = 50 neighbors. But the best results remain those of the last group of metrics: Cosine, Jaccard, and WUP-n.

In MovieTweetings, the relative differences between the metrics vary. Pearson exhibits particularly poor performance, Jaccard performs worse in Jester than in other datasets, while other metrics tend to reflect the relative differences highlighted in Figure 3. But, apart from any metric-specific remark, the main information we can extract from Figure 4 consists of its correlation with the data in Figures 1 through 3. For all metrics, high resistance to Sybil attacks results in poorer recommendation quality. This raises the research question of how to design a metric that can combine both benefits.

C. Impact of Sparsity

We have already observed how the results in our different datasets reflect their different sparsity levels. We confirm this hypothesis, by considering five variants of the ML-1 dataset with increasing levels of sparsity.

Figures 5a and5b depict, respectively, the proportion of expected Sybil neighborhoods and the attack's accuracy with varying sparsity levels and with 20% of auxiliary items. The figures show that the attack becomes less and less effective as sparsity increases. The fraction of expected neighborhoods drops drastically even for the metrics that tend to facilitate the attack in the base dataset (ML-1). Accuracy (Figure 5b) exhibits a similar behavior.

Figures 6a and6b present the same analysis but with Sybils equipped with 80% of the target's profile. In this case, sparsity has a weaker impact on the attack, but accuracy still decreases with all of the metrics. Finally, Figure 7 shows that recommendation quality worsens with sparsity. This confirms the negative correlation between recommendation quality and accuracy highlighted in Section V-B.

D. Choice of Auxiliary Information

We now examine the information impacts the success of the attack. To this end, we consider Cosine, as it is the most widely used metric due to its good recommendation performance, and see how the attack behaves in the following six scenarios for the choice of auxiliary information. Let t be the target profile sorted by rating, and let Aux be the set of auxiliary items and ratings. We consider six scenario: 1) Random where Aux constitutes a random subset of t, 2) BestRated where Aux comprises the best rated items in t, 3) WorstRated where Aux comprises the worst-rated items in t, 4) BestWorstRated where half of Aux comprises the best-rated items in t and the other half the worst rated, 5) RegularSampling where Aux consists of items picked at regular intervals from t, 6) MostPopular where Aux contains items from t that are also the most popular in the whole recommender. Based on these six scenario we can show the following lemma (proof is provided in the appendix).

Lemma 1. Let Aux scenario be a set of auxiliary items in a given scenario. We consider s Aux a Sybil user whose profile only consists of auxiliary information Aux scenario . The BestRated scenario maximizes the Cosine similarity of the Sybil with the target, i.e.

Aux bestRated = arg max Aux⊂t [cos(s Aux , t)]
Proof. The profile of the Sybil user is a subset of the target's profile. For each item in Aux, the ratings are the same in both profiles because of the attack definition. Thus, we obtain the following:

cos(s Aux , t) = s 2 i t × s 2 i = s 2 i t cos(s Aux , t
) is maximised by the bestRated scenario.

To complement this lemma, we also ran experiments on the ML-1 dataset: Figure 8 depicts the result. As expected BestRated maximizes the success of the attack, but Random, which we used in the previous sections, and RegularSampling perform almost as well. MostPopular achieves poorer performance, possibly because popular items are less discriminating, while WorstRated performs the worst.

E. Adaptive Sybils with Standard Metrics

We have so far considered a single round of attack. In a real setting, however, an attacker may iterate the attack while incorporating the new information he/she learned about the target. In Figure 9, we evaluate exactly this scenario in the ML1 dataset. Each Sybil requests one recommendation at a time. Once the Sybil receives the recommendation, we add the recommended item to the Sybil's profile with the score it has in the profile of the user that provided the recommendation. We then take this new item into account to compute a new neighborhood and obtain a new round of recommendations. We repeat the process for 10 rounds.

Results shows that, with most of the metrics, the performance of the attack remains constant throughout the recommendation rounds. However, Cos-overlap exhibits a dramatic increase in both the fraction of expected neighborhoods and accuracy, with a corresponding decrease in yield. The reason lies in the way Cos-overlap treats the items that appear in the Sybil's profile but not in that of the target, and on the assumptions we made on the attacker. When a Sybil receives a recommendation, this may come either from the target's profile, or from some other user's profile. However, Cosoverlap only considers items from the target user's profile. As a result, when a Sybil receives a recommendation that is not in the target profile, this does not penalize its similarity with the target. However, when it receives a recommendation for an item that is both in the profile of the target and in that of another user, our assumption that the Sybil can guess the profile of the target penalizes its similarity with the other user. This explains the increase in accuracy over successive rounds in the case of Cos-overlap.

VI. TOWARDS SYBIL RESISTANCE

Our analysis of the results in Sections V-A and V-B reveals a very clear trade-off between the quality of recommendation and Sybil resistance. In this section, we propose a new metric that minimizes the impact of this trade-off. To this end, we examine the peculiar performance of Cos-overlap on ML-1 and extract some guidelines for the design of our new metric.

A. Understanding Cosine-Overlap

The denominator of Cosine similarity discounts the scores of users with very large profiles thereby benefiting those that have more specific interests. But Cos-overlap entirely removes this behavior and considers only the ratings of items that appear in both user profiles and completely ignores those that appear in only one of them. This means that two users may have a similarity of 1 even if their item sets differ significantly. We indeed notice that a very large proportion of users have perfectly similar counterparts (i.e. other users with whom they have a similarity of 1) from the point of view of Cos-overlap.

The poor discriminatory power of Cos-overlap makes it hard for Sybils to distinguish the target and the other Sybils from the target's perfectly similar alter-egos. Figure 10 breaks down the data from Figure 1 and shows the fraction of perfect neighborhoods as a function of the number of perfectly similar counterparts of the target. Each line corresponds to a different amount of auxiliary knowledge made available to the attacker. The data for users that have no perfectly similar counterparts pretty much follows the behaviors of the other similarity metrics in Figure 1. The percentage of Sybils that get an ideal neighborhood strongly depends on the amount of available auxiliary knowledge. However, as soon as the target has at least 2 perfectly similar counterparts, none of the Sybils manages to obtain an ideal neighborhood, regardless of the amount of auxiliary knowledge they have. The results for prediction accuracy (not shown for space reasons) follow a similar pattern. Sybils can guess the profiles of users that are sufficiently unique, but can do little for users that have good alter-egos.

While the presence of perfectly similar counterparts constitutes an asset for Sybil resistance, it clearly hampers the system's ability to provide good recommendations. Consider a user, A, with two perfectly similar alter egos, B, and C. A and B share a single common rating on a single common item. A and C, on the other hand, share common ratings on a significant portion of their two profiles. Clearly, C will be a better candidate than B to provide recommendations to A. But Cos-overlap will consider B and C as equally good.

B. Two-step Similarity Metric

The above observations suggest that a metric should, on the one hand, discriminate good from bad profiles for recommendation, while, on the other, prevent Sybils from identifying the target and other Sybils.

We satisfy these requirements with two-step, a novel similarity metric with a composite structure. Given a user u, and a potential neighbor n, the first step may employ any existing similarity metric (e.g. Cosine), and post-processes its values so that all the potential neighbors that score beyond a certain threshold appear to be the same to u. Unlike focusing on a small subset of items as in the case of Cos-overlap, using a threshold makes it possible to coalesce users that are likely to provide similar results in terms of recommendation. This makes it difficult for a Sybil user to obtain a neighborhood that contains the desired target user.

The second step of the metric goes beyond the threshold and attempts to distinguish which of the top-scoring potential neighbors (those with a first step above the threshold) may be useful to compute recommendations for user u. The recommendation process consists in finding potentially interesting items in the profiles of u's neighbors. This implies that a neighbor that has no items that do not appear in u's profile brings nothing to the recommender and should therefore be discarded. Rather, a good neighbor should have at least some items that do not appear in u's profile.

The second step therefore differentiates the potential neighbors that score above the threshold by taking into account the number of items in their profiles that do not appear in the profile of u. Because the recommender computes the neighborhoods for all users, including the Sybils, this heuristic has the beneficial effect of discouraging the presence of other Sybils in the neighborhood of a Sybil user, thereby making the attack more difficult.

To summarize, the threshold makes it hard for a Sybil to differentiate the target, or another Sybil from other very similar nodes. The second step complements this feature by preferring legitimate users to Sybils. In the following, we describe the details of our two-step metric.

C. Two-step details

Let u be a user for which we have to evaluate the goodness of w as a neighbor. Both, u and w may be legitimate users or Sybils. Also, with some abuse of notation, let w -u denote the set of items that appear in w's profile but not in u's.

Let Sim be a similarity metric, for example Cosine. In the first of the two steps, we compute the similarity between u and w, Sim(u, w). If Sim(u, w) is less than a threshold th u then we use Sim(u, w) as the final similarity value. Otherwise we compute th u + f i,u (|w -u|), where (i) |w -u| is the number of items that appear in the profile of w but not in that of u, (ii) i is the total number of items in the system, and (iii), f i,u : N → [0, 1 -th u ] is a function defined as follows.

f i,u (x) = (1 -th u ) x i
This increasing function attempts to ensure that the neighbor's profile contains some items that are not in u's profile. By combining the two above steps, we obtain the following definition for our two-step metric.

2-step(u, v) = Sim(u, v) if Sim(u, v) < th u th u + f i,u (|v -u|) if Sim(u, v) ≥ th u

VII. EVALUATING TWO-STEP

We evaluate 2-step using the same metrics as in Section V. To set the metric's threshold, we make a pass on the entire user-item matrix before computing the nearest-neighbor graph. For each user u, we compute the similarity of u with all the other users. We then round similarity values to the nearest hundredth, sort them, remove all duplicate values, and set the threshold as the t th percentile of the resulting sorted sequence: we considered values of t ∈ {80, 90}. Figure 11 shows the RMSE score with ML-1. We have the same recommendation quality as with the cosine metric and significantly better recommendation quality than Cos-overlap. This is the first advantage of this metric: we ensure a very good recommendation quality, in terms of RMSE.

A. Basic Attack on Two-Step

Next, we evaluate how effectively 2-step protects users from Sybil attacks. To this end, we first consider the attack from [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF] we analyzed in previous sections. Figure 12 depicts its performance in terms of expected neighborhood and accuracy. The plot shows that none of the Sybils manages to obtain its expected neighborhood, while accuracy never exceeds 25%. Even this small number of correct guesses does not result from a truly successful attack, but from the presence of other nodes whose profiles resemble that of the target.

The plot also shows that accuracy decreases with the number of auxiliary items. This may appear counter-intuitive, but as the proportion of auxiliary items increases, these start to include more and more of the items that the target shares with its neighbors. Since the attacker never manages to have the target as a neighbor, the number of possible correct guesses based on other nodes' profiles decreases rapidly.

Although the above results appear very promising for 2-step, the basic attack does not specifically target this metric. In the following, we therefore extend the attack in order to evaluate the resistance of 2-step in the worst case.

B. An Attack Targeting Two-Step

The success of the Sybil attack relies on the ability (i) to gather all other Sybils in the attacker's neighborhood, and (ii) to have the target as a neighbor. In a system based on Cosine, giving all Sybils the same profile maximizes the chances of satisfying (i), while giving them as many items as possible from the target profile maximizes those of satisfying (ii).

In the case of 2-step, on the other hand, having the same profile does not suffice to satisfy (i), and gathering as many auxiliary items as possible can offer only limited benefits with Fig. 11: RMSE, using 10-fold cross validation (ML-1). Fig. 12: Fraction of Sybils with their expected neighborhood and accuracy (standard attack, 2-step, ML-1). Fig. 13: Expected neighborhoods score, with real and fake additional items (ML-1). respect to (ii). To obtain a high similarity value with 2-step, two users (real or Sybil users) must have a large enough common set of items, and a large enough non-shared set.

To explicitly target our 2-step metric, we therefore modify the basic attack from [START_REF] Calandrino | you might also like:" privacy risks of collaborative filtering[END_REF] by considering both of these two requirements. This yields a 2-step-specific attack with two parameters: a set auxiliary items taken from the target's profile, and a set of additional items. The presence of these two parameters, however, makes it more difficult for the attacker to identify a winning strategy. It becomes reasonable to wonder whether a strategy independent of the dataset actually exists.

To answer this question, we carry out a worst case analysis by varying both parameters through a range of values. To begin with, we consider the possible strategies for choosing auxiliary and additional items. Figure 13 shows the fraction of expected neighborhoods among the Sybils using Sybil profiles of the same size as the target profile, and increasing fractions of auxiliary items, for different choice strategies.

With respect to auxiliary items, the plot confirms BestRated as the best option for the attacker, and so the worst case scenario for the algorithm. The rest of the plot confirms the results of Figure 8, with RegularSampling, and Random performing slightly worse than best rated. For clarity, we do not show the remaining worse performing strategies.

With respect to additional items, the plot shows two strategies: real and fake. With the former each Sybil chooses a set of real items from the systems that are not in the target's profile and that have not been chosen by any other Sybil. With the latter, each Sybil generates and chooses a set of fake items. Fake consistently achieves better performance because they cannot be shared with any other node (Sybil or legitimate). This guarantees the maximum bonus for each Sybil node in the computation of 2-step.

Finally, the plot also shows an important difference with respect to Figure 8. With Cosine, the performance of the attack increases with the fraction of auxiliary items. But with 2-step, this no longer happens. Rather, each of the curves exhibits a different ideal fraction of auxiliary items, and all such ideal fractions correspond to very low values. To understand this behavior, Section VII-C deepens our analysis by searching for a worst-case set of parameters.

C. Searching for a Worst Case Scenario

To identify a worst-case scenario for 2-step, we consider the best configuration for the attacker: best-rated auxiliary items and fake additional items. We experimentally search for the worst-case scenario by varying the sizes of the sets of auxiliary and additional items: respectively Aux, and Add. Since the best number of additional items likely depends on the size of the target profile, we represent this number as a fraction. Let t be the size of the target profile, p the fraction of auxiliary items. We define the fraction q of additional items as q = Add (1-p)|t| . A fraction q = 1 therefore gives Sybils a profiles that has the same size as that of the target node.

Figure 14 shows the performance of the attack with varying values of both p and q in the form of 3D plots. Results confirm the difficulty of finding a very successful attack configuration on 2-step. Accuracy never exceeds 60% in the same dataset that yielded close to 100% accuracy in Figure 3a. As already shown in Figure 13, this 60% value is achieved for a very small value of p. But Figure 14a, shows that accuracy increases until q = 1 and then plateaus. The plot shows values of q ≤ 2, but we experimentally verified that accuracy further decreases for larger values of q with values below 0.3 for q ≥ 5.

To clarify this behavior, Figures 14c and14b show the distribution of the two conditions required to achieve a perfect neighborhood: having the target as a neighbor, and having all Sybils as neighbors. Figure 14b shows that increasing q always increases the probability to have all other Sybils as neighbors, while p exhibits the same point of maximum as in Figure 14a. On the other hand, the probability of having the target as a neighbor drops significantly when q ≥ 1. This explains the plateauing accuracy values in Figure 14a for q ≥ 1.

D. Attack Performance across Datasets

We now examine the effectiveness of the 2-step-specific attack on MT and Jester. Figure 15 depicts the results obtained on MT with a fraction of additional items, q = 1. The curves appear similar to those on the ML-1 dataset, but with a lower peak. At most, 25% of Sybil users obtain the ideal neighborhood, with a fraction of auxiliary items p = 0.3 (i.e., 30%). The plot also shows that the score for accuracy closely mimics that for the fraction of Expected Neighborhoods.

The results for Jester, not shown for space reasons, show instead that none of the Sybils obtain the expected neighborhood and that the target appears in the Sybil's neighborhood only in a very small fraction of cases (less than 1%). While this results correspond to an ineffective attack, accuracy still achieves very high values thanks to the density of the dataset. To test this conclusion, we also evaluated an attacker that selects k random users as neighbors, instead of a KNN search and even this completely random attack yielded high accuracy values.

Overall, the results for 2-step highlight the difficulty of identifying suitable parameters for a successful attack. The low scores make it hard for the attacker to know whether it is really observing a part of the target's profile.

E. Threshold Analysis

We have so far evaluated 2-step with two values of its percentile threshold. We now show that a wide range of values offers good recommendation quality while resisting to attacks. Figure 16a shows that 80% and 90% thresholds achieve the best recommendation performance in ML-1, giving as low an RMSE as cosine. Figure 16b confirms instead the expectation that the lower the threshold the worse the performance of the attack. This justifies the choice of an 80% threshold in Sections VII-A through VII-D.

Figure 17 completes our analysis of 2-step's threshold by showing the same plots for the MT dataset. Interestingly, a threshold of 70% performs equally well as cosine, while one of 60% performs even better for large neighborhood sizes.

F. Comparison with PPNS

We now show that our similarity-based defense mechanism outperforms state-of-the-art techniques by comparing its attack resilience with that of PPNS [START_REF] Lu | A security-assured accuracy-maximised privacy preserving collaborative filtering recommendation algorithm[END_REF]. PPNS seeks to protect userbased collaborative filtering from the same attack we consider in this paper by modifying the neighbor-selection process. For a given users, it partitions all other users in descending order of similarity in partitions of size k. It then extracts k neighbors from the top β partitions while maximizing recommendation accuracy subject to the constraint that at least one neighbor be extracted from the β-th one. The optimal solution consists in selecting k-1 neighbors from the first partition and 1 from the β-th one [START_REF] Lu | A security-assured accuracy-maximised privacy preserving collaborative filtering recommendation algorithm[END_REF]. We therefore experimented with this strategy.

In terms of RMSE, results on the ML-1 datasets appear indistinguishable from those in Figure 4a and, with k Sybil users, the attacker never manages to have the target in a Sybil's neighborhood, making the attack unsuccessful. However, we also tested a stronger version of the attack with β * k Sybils. In this case, the attacker can easily build neighborhoods that include not only Sybils but also the target node.

Figure 18 shows the results of the experiments with β * k Sybils in terms of expected neighborhoods and attack accuracy. To provide a conservative comparison, we also perform an attack on 2-step using the specific attack with β * k Sybils. The plot clearly shows that while 2-step provides practically the same protection as with k Sybils, PPNS becomes helpless with β * k Sybil nodes. Since the difficulty in orchestrating an attack with a large number of Sybil users remains limited, this experiments shows the superiority of our approach.

G. Adaptive Sybils with 2-Step

Finally, Figure 19 shows the result of adaptive Sybils with 2-step. The Expected neighborhoods score decreases over rounds. If the attacker includes a correct guess as an auxiliary item, then the Sybils will have a lower bonus at the second step during the following round. We conclude with a brief theoretical comparison of Cosine and 2-step in the context of binary ratings; an additional property of 2-step is available in [START_REF] Frey | Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter![END_REF].

Let t be a target user with |t| > 1 and let S be the set of all Sybil users generated by the attacker.

Assumptions 1. Let t be a user such that: (i) No other user has the same profile as t; (ii) there exists no user u with u ⊂ t and |t -u| = 1; and (iii) there exists no user u with |u | = |t| and |u ∩ t| = |t| -1.

Theorem 1. Let s aux be a Sybil user with a profile consisting of the auxiliary information aux. Given Assumptions 1, there exists aux that ensures: ∀u ∈ S, cos(s, t) > cos(s, u) Theorem 1 confirms the vulnerability of Cosine similarity observed in Section V. The proof is available in [START_REF] Frey | Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter![END_REF]. The next theorem shows that 2-step effectively protects the recommender from the basic attack.

Theorem 2. Given Assumptions 1, let aux be such that: aux ∈ t, |aux| = |t| -1, and ∀u ⊂ t =⇒ u ⊂ aux. Let s aux be the associated Sybil user. Let N v = #{u | cos(u, v) ≥ th v } be the number of users above the threshold for user v. Let C v = #{u | u ⊂ v} be the number of users with a profile which is a subset of v's profile. Then, if C t < N saux , we have: ∃u ∈ S, 2-step(s aux , t) ≤ 2-step(s aux , u) Proof. Among N saux , we have at most k users that are a Sybil or the target. Among C t , we have at least the k Sybils. Therefore, as C t < N saux , we can ensure there exists a user u ∈ S above the threshold th saux which does not verify u ⊂ t. We have cos(s aux , u) ≥ th saux .

If cos(s aux , t) < th saux then we deduce the result. Otherwise, because u is not a subset of t, we have |t ∩ u| < |u|. There exists at least one item in u but not in t and thus not in s aux . We have : |u -s| ≥ 1 = |t -s|. We deduce: 2-step(s aux , t) ≤ 2-step(s aux , u)

Even if it concentrates on the basic attack, the above theorem provides a hint about the difficulties associated with targeting 2-step. To generalize this result to the 2-stepspecific attack from Section VII-B, we collected, in Table III, the components of the computation of 2-step. The goal of the attacker consists in maximizing the values of 2-step(s, t) and 2-step(s, s ), while minimizing that of 2-step(s, u). By increasing the fraction of auxiliary items, the attacker can increase the Cosine component of both 2-step(s, t) and 2-step(s, u). The former will, in general, increase faster as |aux ∩ u| < |aux|, but ultimately both get capped at the same value, th s . If we look at the bonus column, on the other hand, we observe that an increase in aux causes a faster decreases in 2-step(s, t) than in 2-step(s, u). This means that too high values of aux will cause the target to exit from the attacker's neighborhood. This suggests that aux should be large enough to enable t to exceed the threshold but not too much to avoid too sharp a decrease in t's bonus.

A similar analysis holds for the number of additional items, add. By increasing it, the attacker can increase the bonus for 2 -step(s, s ), but it also reduces the corresponding Cosine component. Again, while a small increase can be beneficial, too large an increase will bring cos(s, s ) below the threshold, preventing Sybils from being in each other's neighborhood.

This reasoning shows that the best values of aux and add cannot be predetermined in advance, but depend on the specific dataset. This makes it particularly difficulty to attack 2-step.

IX. CONCLUDING REMARKS

We presented a comprehensive experimental analysis of the impact of similarity metrics on the Sybil resilience of existing user-based collaborative-filtering systems. Our results, obtained on a state-of-the-art recommendation framework highlight the limits of existing similarity metrics. We addressed these limits by proposing a novel Sybil-resistant similarity metric. We showed that our novel metric not only resists to the basic attack designed for standard metrics, but also to a specific attack designed to exploit its very structure, while outperforming existing solutions.

Exploring variants of the attack, for instance in a system that relies on dissimilarity metrics or on an item-based approach, would constitute interesting avenues for future work.

  Fig. 1: Fraction of Sybils with ideal neighborhoods for an isolated attack.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Yield for an isolated attack.

Fig. 4 :

 4 Fig. 4: RMSE using 10-fold cross validation.

Fig. 5 :Fig. 6 :Fig. 7 :

 567 Fig.5: Fraction of Sybils with their expected neighborhood, yield, and accuracy (20% of auxiliary items, ML-1).

Fig. 8 :

 8 Fig.8: Sybil attack with cosine similiary metric, ML-1 dataset and several auxiliary information scenarios.

Fig. 9 :Fig. 10 :

 910 Fig. 9: Adaptive Sybils on the ML-1 dataset. Sybils have 20% of auxiliary items.

Fig. 14 :Fig. 15 :Fig. 16 :

 141516 Fig.14: Sybil attack with ML-1 dataset, 2-step 80 similarity metric, bestRated scenario, and fake additional items

Fig. 17 :

 17 Fig. 17: Threshold Analysis with Movie Tweetings dataset, bestRated scenario, and fake additional items.

Fig. 18 :

 18 Fig. 18: Simple attack using PPNS (ML-1), compared with 2step80 specific attack (40 sybils).

Fig. 19 :

 19 Fig.19: Adaptive Sybil attack over 10 rounds with ML-1, 2-step-80, 4% aux. information, and fake additional items

TABLE I

 I

: Characteristics of the datasets in terms of number of users, number of items, number of ratings and rating type.

TABLE II

 II

: Sparsity of the original datasets and ML variants.

TABLE III :

 III Components of 2-step similarity between relevant pairs of nodes. t is the target; s and s are Sybils; and u ∈ RS \ {s, s , t}.

X. ACKNOWLEDGEMENTS

This work was partially funded by the Region of Brittany, France, by the French ANR projects Pamela (ANR-16-CE23-0016-04), by the Profile project granted by the Labex Comin-Labs excellence laboratory (ANR-10-LABX-07-01), and by the Google Focused Research Award Web Alter-Ego.


Diying Huang
email: dyhuang@nigpas.ac.cn

Chenyang Cai
email: cycai@nigpas.ac.cn

André Nel
email: anel@mnhn.fr

New damsel-dragonflies with "calopterygid"-like wing shape from the Middle Jurassic of China (Odonata: Isophlebioidea: Campterophlebiidae)

Keywords: Insecta, Odonata, Campterophlebiidae, nov. gen., nov. sp., Daohugou biota

The new damsel-dragonflies Zygokaratawia incompleta nov. sp. and Parazygokaratawia azari nov. gen., nov. sp., closely related to the campterophlebiid genus Zygokaratawia, are described from the Middle Jurassic locality of the Daohugou and Chentaizi villages respectively in Ningcheng County, Inner Mongolia, NE China. Parazygokaratawia and Zygokaratawia share a narrowly reduced cubito-anal area, unique synapomorphy in the Isophlebioptera.

Campterophlebiids with this character are only known from the Daohugou biota.

Introduction

The insect order Odonata is divided into two main clades Zygoptera (damselflies) and Epiproctophora, a clade that comprises several extinct clades and the living Epiophlebiidae (damsel-dragonflies) and the Anisoptera (true dragonflies) [START_REF] Bechly | Morphologische Untersuchungen am Flügelgeäder der rezenten Libellen und deren Stammgruppenvertreter (Insecta; Pterygota; Odonata), unter besonderer Berücksichtigung der Phylogenetischen Systematik und des Grundplanes der Odonata[END_REF]. The Isophlebioidea is one of the most diverse clades of Mesozoic damsel-dragonflies. Their oldest-known representatives are found in Late Triassic-Early Jurassic strata and the youngest in the Late Cretaceous. The family Campterophlebiidae is the largest family of this clade [START_REF] Nel | Les 'Anisozygoptera' fossiles. Phylogénie et classification (Odonata)[END_REF][START_REF] Bechly | Morphologische Untersuchungen am Flügelgeäder der rezenten Libellen und deren Stammgruppenvertreter (Insecta; Pterygota; Odonata), unter besonderer Berücksichtigung der Phylogenetischen Systematik und des Grundplanes der Odonata[END_REF]. Ten campterophlebiid genera are currently known from the Middle Jurassic-Lower Cretaceous of north China (see summary in [START_REF] Zheng | A new damsel-dragonfly from the Lower Jurassic of northwestern China and its paleobiogeographic significance[END_REF][START_REF] Zheng | The first damsel-dragonfly (Odonata: Isophlebioidea: Campterophlebiidae) from the Middle Jurassic of Shaanxi Province, northwestern China[END_REF]. Among them, one of the more curious is the genus Zygokaratawia [START_REF] Nel | A new genus of isophlebioid damseldragonflies with "calopterygid"-like wing shape from the Middle Jurassic of China (Odonata: Isophlebioidea: Campterophlebiidae)[END_REF], characterized by very narrow hindwings with narrow cubito-anal area. This particular shape of wings is looking like that of a modern Calopterygoidea. Here we describe two new taxa with similar wing shapes from the same locality of Daohugou in Inner Mongolia.

Material and methods

The type specimens were prepared with a steel needle under microscope. Photographs were taken using Nikon 5d2 camera. The type specimen of Zygokaratawia incompleta is preserved in a whitish tuffaceous shale associated with lots of conchostracans of the genus Euestheria, indicating that it comes from the Dadaogou Layer near the Daohugou Village where the outcrops are now covered by the Museum. It comes from an upper layer of the Daohugou beds.

The type specimen of Parazygokaratawia azari is preserved in a grayish tuffaceous shale associated with lots of cladocerans, indicating that it comes from the top most layers of the Daohugou beds near the Chengtaizi Village (Fig. 1).

The nomenclature of the odonatan wing venation used in this paper is based on the interpretations of [START_REF] Riek | A new interpretation of dragonfly wing venation based upon Early Carboniferous fossils from Argentina (Insecta: Odonatoidea) and basic characters states in pterygote wings[END_REF], as modified by [START_REF] Nel | Les 'Anisozygoptera' fossiles. Phylogénie et classification (Odonata)[END_REF] and [START_REF] Bechly | Morphologische Untersuchungen am Flügelgeäder der rezenten Libellen und deren Stammgruppenvertreter (Insecta; Pterygota; Odonata), unter besonderer Berücksichtigung der Phylogenetischen Systematik und des Grundplanes der Odonata[END_REF]. The higher classification of fossil Odonatoptera, as well as family and generic characters followed in the present work, are based on the phylogenetic system proposed by [START_REF] Bechly | Morphologische Untersuchungen am Flügelgeäder der rezenten Libellen und deren Stammgruppenvertreter (Insecta; Pterygota; Odonata), unter besonderer Berücksichtigung der Phylogenetischen Systematik und des Grundplanes der Odonata[END_REF]. Wing abbreviations are as follows: AA analis anterior; AP, analis posterior; Arc, arculus; Ax, primary antenodal crossvein; CuA cubitus anterior; CuP, cubitus posterior; d discoidal cell; IRx intercalary radial veins; MA median anterior; MP median posterior; N nodus; Pt pterostigma; RA radius anterior; RP radius posterior; sd subdiscoidal cell.

Systematic palaeontology

Order Odonata Fabricius, 1793 Superfamily Isophlebioidea [START_REF] Handlirsch | Die fossilen Insekten und die Phylogenie der rezenten Formen. Ein Handbuch für Paläontologen und Zoologen[END_REF] Family Campterophlebiidae [START_REF] Handlirsch | Geschichte, Literatur, Technik, Palaeontologie, Phylogenie, Systematik[END_REF] Remark. The list of campterophlebiid genera is available in the internet site Fossilworks. no anal angle but AP weakly curved (female specimen); no membranule; AA distally strongly bent towards posterior wing margin and nearly parallel with MP+CuA, distally fused with CuAb; median and submedian areas free; curved vein CuP just basal of Ax1; subdiscoidal area transverse, poste has hindwings very similarriorly closed, short and broad, with one crossvein, 1.4 mm long, 0.9 mm wide; discoidal cell basally closed, 0.7 mm long, 0.5 mm wide, free of crossveins, length of proximal side 0.4 mm; RP+MA separates at approximately a right angle from RA and strongly curved in arculus; RP separated from MA 0.3 mm distally; MA basally strong and divided into MAa and MAb 0.7 mm distally; MAb short, 0.8 mm long, aligned with distal free part of CuA; MP+CuA separated into MP and CuA at distal end of MAb; distal free part of CuA strong, separating from MP 5.4 mm from wing base and extends towards posterior wing margin for 0.5 mm; CuA distally divided into CuAa and CuAb, CuAb short, 0.4 mm long, extending towards basal wing margin and meeting main branch of AA; CuAa basally more or less parallel to posterior wing margin with only one row of cells between them; CuAa short, ending on posterior wing margin about 6.7 mm from its base, well before nodus level; area between CuAa and MP with one row of cells, 1.4 mm wide; distal of end of CuAa, area between MP and posterior wing margin very long and broad; MP nearly straight, reaching posterior margin well distal of nodus level, ca 22.0 mm from wing base; MAa parallel with MP, nearly straight in its basal part, postdiscoidal area 0.9 mm wide, with one row of cells; Ax1 0.35 mm basal of arculus, nearly perpendicular to ScP; Ax2 2.1 mm distal of arculus, oblique; no secondary antenodal crossveins between C and ScP, but seven secondary antenodal cross-veins between ScP and RA distal of Ax2; 12 cross-veins in area between RA and RP, between arculus and nodus; base of RP3/4 0.35 mm distal of arculus, closer to arculus than to nodus; base of IR2 close to that of RP3/4, 1.5 mm distally; no antefurcal crossvein in space between RP and MA basal of midfork (base of RP3/4), except for a very oblique crossvein between MAa and base of RP3/4; 12 postnodal cross-veins between C and RA; 11 postsubnodal cross-veins between RA and RP1 not aligned with postnodals; pterostigmal brace rudimentary, not oblique and not well-aligned with basal side of pterostigma; four crossveins below pterostigma; pterostigma sclerotized, 4.4 mm long, 0.65 mm wide; pterostigma rather basally recessed with 10 cells between C and RA distal of it; RP2 aligned with subnodus; 10 crossveins in Bqr space between RP, RP2, IR2 and first oblique vein "O"; oblique vein "O" 2.3 mm and four cells distal of base of RP2; RP2 nearly straight; base of IR1 five cells distal of base of RP2; IR1 basally weakly zigzagging but distally nearly straight, more or less parallel to RP1; area between MA and RP3/4 much wider distally, with 17 rows of cells along posterior wing margin; area between RP3/4 and IR2 as broad basally as distally, with basally one row of cells and two distally; area between IR2 and RP2 with one row of cells and distally seven rows near posterior wing margin; area between RP2 and IR1 progressively widened, with one zigzagging intercalary longitudinal vein and 2-3 rows of cells between them; area between IR1 and RP1 not distally widened, with 3-4 rows of cells between them.

Abdomen with only seven basal segments preserved, 2.1 mm wide, no secondary male genital apparatus on second segment.

Remarks: Zygokaratawia incompleta nov. sp. has hindwings very similar to those of the campterophlebiid Zygokaratawia reni [START_REF] Nel | A new genus of isophlebioid damseldragonflies with "calopterygid"-like wing shape from the Middle Jurassic of China (Odonata: Isophlebioidea: Campterophlebiidae)[END_REF], also from the same outcrop [START_REF] Nel | A new genus of isophlebioid damseldragonflies with "calopterygid"-like wing shape from the Middle Jurassic of China (Odonata: Isophlebioidea: Campterophlebiidae)[END_REF]). The differences between the two fossils are as follows: pterostigma more basally recessed in Z. incompleta than in Z. reni, with ten cells between C and RA distally in Z. incompleta against only four in Z. reni; 12 postnodals for Z. incompleta instead of ten for Z. reni; 12 crossveins in antesubnodal area in Z. incompleta instead of five in Z. reni; a strongly oblique crossvein between MAa and base of RP3/4 in Z. incompleta, absent in Z. reni; 10 crossveins in Bqr space of Z. incompleta instead of five in Z. reni.

Among the campterophlebiids with a venation relatively similar to that of Zygokaratawia, Z. incompleta differs from Sarytashia Pritykina, 1970 in RP2 without a pronounced distal curve and different shape of secondary veins between IR1 and RP1.

Adelophlebia Pritykina, 1980 is known by the forewing base but it differs from Zygokaratawia incompleta in the presence of two rows of cells in postdiscoidal area [START_REF] Pritykina | Triassic and Jurassic dragonflies of the Liassophlebiidae from Soviet Central Asia[END_REF][START_REF] Pritykina | New fossil Odonata from the Mesozoic of Central Asia[END_REF] Description: a fragment of thorax, with two forewings and one hindwing connected.

Forewing hyaline; 30.8 mm long, 6.0 mm wide; distance between base and arculus 4.0 mm, arculus and nodus 10.0 mm, nodus and pterostigma 12.4 mm, pterostigma and apex 3.2 mm; a short petiole 1.6 mm long, 1.0 mm wide; one row of cells between posterior wing margin and AA; AA parallel to MP+Cu; median and submedian areas free; a curved strong vein CuP between submedian and subdiscoidal areas, lying well basal of arculus; subdiscoidal space free of crossveins, rather transverse; discoidal space basally opened; RP+MA separated at nearly a right angle from RA in arculus, strongly curved; RP separated from MA 0.1 mm distally; RP and MA well parallel; MAb rather short, ca. 0.6 mm long, well aligned with distal free part of CuA; CuA separates from MP ca. 5.0 mm from wing base and directed towards posterior wing margin for 0.2 mm; distal free part of CuA strong, CuA distally fused with AA; CuA divided into a very short CuAb directed towards posterior wing margin and CuAa basally more or less parallel to posterior wing margin and distally delimitating a short and narrow cubito-anal area, with 1-2 posterior branches and 1-2 rows of cells at its broadest part; apex of CuA 1.5 mm basal of nodus level; area between CuA and MP with one row of cells; distal of apex of CuA, area between MP and posterior wing margin very long and broad; MP nearly straight, reaching posterior wing margin well distal of nodus level; MAa more or less parallel with MP, nearly straight in basal half but slightly zigzags distal of subnodus level; postdiscoidal area with one row of cells, 1.0 mm wide near discoidal cell and 0.8 mm at apex of MAa; Ax0 well-preserved very close to wing base; Ax1 0.6 mm basal of arculus, nearly perpendicular to ScP and R+MA, Ax2 well distal of arculus, also perpendicular to ScP and RA, 2.6 mm distal of Ax1; no secondary antenodal crossveins between C and ScP; six visible secondary antenodal crossveins between ScP and RA distal of Ax2; 10 postnodal crossveins between C and RA not aligned with 10 postsubnodal cross-veins between RA and RP1 basal of pterostigma; seven preserved crossveins in area between RA and RP, between arculus and nodus; base of RP3/4 3.0 mm distal of arculus, closer to arculus than to nodus; base of IR2 close to that of RP3/4, 0.5 mm distally; no visible antefurcal crossvein in space between RP and MA basal of midfork (base of RP3/4); subnodus oblique and well aligned with nodal crossvein Cr; RP2 three cells distal of subnodus; Bqr space between RP, RP2, IR2 and oblique vein "O" long and narrow, with one row of cells and six cross-veins; oblique vein "O" nearly perpendicular to RP2 and IR2, one cell distal of RP2 base; RP2 nearly straight in its preserved part; base of IR1 four cells distal of base of RP2; IR1 basally straight and distally curved, more or less parallel to RP1, with one row of cells between them till the apex of pterostigma; area between MA and RP3/4 much widened distally, with several long intercalary longitudinal veins; area between RP3/4 and IR2 widened distally with an intercalary longitudinal vein zigzagging between them; area between IR2 and RP2 very narrow, without any intercalary longitudinal vein between them; pterostigma 2.0 mm long, 0.6 mm wide, covering two cells; pterostigmal brace neither aligned with basal side of pterostigma or strongly oblique.

Hindwing hyaline; distinctly shorter than forewing, 26.0 mm long, 5.6 mm wide, widest part at level of nodus; distance between base and arculus ca. 2.5 mm (arculus not preserved), between arculus and nodus ca. 7.9 mm, nodus and pterostigma 10.3 mm, pterostigma and apex 3.2 mm; a very short petiole, 0.8 mm long, 0.5 mm wide; anal area not visible, but probably very narrow and triangular in shape, with one row of irregular cells between AA and AP; no anal angle (female specimen); no membranule; AA distally bent towards posterior wing margin and nearly parallel with MP+CuA, distally fused with CuAb; median and submedian areas and vein CuP not visible; subdiscoidal area rather transverse, posteriorly closed, short and broad, with one basal crossvein, 1.2 mm long, 0.6 mm wide; discoidal cell basally closed, 1.0 mm long, 0.6 mm wide, free of crossveins, length of proximal side, ca. MA divided into MAa and MAb ca. 1.1 mm distal of arculus; MAb short, 0.6 mm long, aligned with distal free part of CuA; MP+CuA separated into MP and CuA at distal end of MAb; distal free part of CuA strong, separates from MP 4.4 mm from wing base and extends towards posterior wing margin for 0.5 mm; CuA distally divided into CuAa and CuAb, CuAb short, 0.4 mm long, extends towards basal wing margin and meets main branch of AA; CuAa basally more or less parallel to posterior wing margin with 1-2 rows of cells between them; CuAa short, ending on posterior wing margin about 5.3 mm from its base; area between CuAa and MP with one row of cells, 0.5 mm wide; distal of end of CuAa, area between MP and posterior wing margin very long and broad; MP nearly straight, reaching posterior margin well distal of nodus level, 16.0 mm from wing base; MAa parallel with MP, nearly straight in its basal part and weakly zigzagging distal of level of nodus, postdiscoidal area 0.5 mm wide, narrower near posterior wing margin, with one row of cells; Ax1 not visible; Ax2 1.3 mm distal of arculus, nearly perpendicular to ScP; no secondary antenodal crossveins between C and ScP, but five secondary antenodal crossveins between ScP and RA distal of Ax2; eight crossveins in area between RA and RP, between arculus and nodus; base of RP3/4 2.1 mm distal of arculus, closer to arculus than to nodus; base of IR2 close to that of RP3/4, 0.6 mm distally; no visible antefurcal crossvein in space between RP and MA basal of midfork (base of RP3/4); nodal structures identical to those of forewing; nine postnodal crossveins between C and RA; eight postsubnodal crossveins between RA and RP1 not aligned with postnodals; pterostigmal brace rudimentary, not aligned with basal side of pterostigma; one crossvein below pterostigma; pterostigma sclerotized, 2.4 mm long, 0.5 mm wide; RP2 one cell distal of subnodus; four crossveins in Bqr space between RP, RP2, IR2 and oblique vein "O"; oblique vein "O" 2.4 mm and four cells distal of base of RP2; RP2 nearly straight; base of IR1 four cells distal of base of RP2; IR1 basally straight and distally curved, more or less parallel to RP1; area between MA and RP3/4 much wider distally, with 15 rows of cells along posterior wing margin; area between RP3/4 and IR2 slightly broader distally than basally, with basally one row of cells and four distally; area between IR2 and RP2 with one row of cells and distally six rows near posterior wing margin; area between RP2 and IR1 progressively widens, with two zigzagging intercalary longitudinal veins and four rows of cells between them; area between IR1 and RP1 not distally widen, with 2-3 rows of cells between them.

Remarks: Parazygokaratawia nov. gen. has nearly all the characters listed in the diagnosis of Zygokaratawia, i.e. hindwing subdiscoidal space small and posteriorly closed; cubito-anal and anal areas very narrow in both fore and hind wings (synapomorphy); a long basal part to CuA before its branches; area between MP and CuA as broad as postdiscoidal area, which is distally constricted; MP straight; MAa zigzags and becomes much weakened distally; CuAa short; pterostigma not basally recessed [START_REF] Nel | A new genus of isophlebioid damseldragonflies with "calopterygid"-like wing shape from the Middle Jurassic of China (Odonata: Isophlebioidea: Campterophlebiidae)[END_REF]. Thus it is probably closely related to this genus in the family Karatawiidae, with which it also shares the putative synapomorphy 'space between MAa and MP distally constricted by an opposite curvature of these two veins'.

Parazygokaratawia and Zygokaratawia differ from all or nearly all Isophlebioidea in the very narrow fore-and hindwing cubito-anal and anal areas [START_REF] Nel | Les 'Anisozygoptera' fossiles. Phylogénie et classification (Odonata)[END_REF][START_REF] Nel | A new genus of isophlebioid damseldragonflies (Odonata: Isophlebioptera: Campterophlebiidae) from the Middle Jurassic of China[END_REF]Pritykina, 2006, etc.). But information on these structures is lacking for some genera. Adelophlebia Pritykina, 1980 is based only on a forewing base; it differs from Parazygokaratawia and Zygokaratawia in the presence of two rows of cells between CuAa and MP [START_REF] Pritykina | New fossil Odonata from the Mesozoic of Central Asia[END_REF].

The forewings of Parazygokaratawia and Zygokaratawia are rather similar to that of Karatawia [START_REF] Martynov | To the knowledge of fossil insects from Jurassic beds in Turkestan[END_REF], with an important difference in that the CuA is longer and better defined distally, and also the hindwings of Karatawia have distinctly broader cubito-anal areas [START_REF] Li | Reassessment of the Jurassic damseldragonfly genus Karatawia (Odonata: Campterophlebiidae)[END_REF]. Sarytashia Pritykina, 1970 is based on the apical half of a wing. It differs from Parazygokaratawia and Zygokaratawia in that its pterostigma is distinctly basally recessed [START_REF] Pritykina | Triassic and Jurassic dragonflies of the Liassophlebiidae from Soviet Central Asia[END_REF].

Nevertheless, Parazygokaratawia has no distinct constriction in the area between RP3/4 and IR2 in all wings, unlike Zygokaratawia. On the contrary the area between these veins is rather widened along posterior wing margin in Parazygokaratawia. Parazygokaratawia also differs from Zygokaratawia in the base of RP2 not aligned with subnodus, IR1 basally straight, only one row of cells between IR1 and RP1 between its base and pterostigma, Ax2 perpendicular to ScP in hindwing, different number of antenodal, postnodal and antesubnodal crossveins. This set of characters is sufficient for an attribution to a different, new genus.

Conclusion

Parazygokaratawia comes from a higher layer of the same paleolake than the two Zygokaratawia species. Maybe it corresponds to a rather rapid local evolution within the same lineage, but this is delicate to show without a complete fossil record through all the strata of this outcrop. These two new discoveries show that the Campterophlebiidae with narrow wings are more diverse than previously supposed, even if they remain restricted to the Haifanggou Formation, in a palaeoenvironment of a high mountain lake [START_REF] Huang | Yanliao biota and Yanshan movement[END_REF].

Fig. 2

 2 Fig. 2 Derivation of name: named after the incomplete state of preservation of the type, as only hindwings are preserved. Holotype: Specimen NIGP167276 (a thorax with two hindwings and the two-third of the abdomen attached), stored at Nanjing Institute of Geology and Palaeontology, Chinese Academy of Sciences, China. Type locality: Near the Daohugou Village, Wuhua Township, Ningcheng County, Chifeng City, Inner Mongolia, NE China.

Figs 3 - 4

 34 Figs 3-4 Derivation of name: Named after our friend and colleague, Prof. Dany Azar. Holotype: Specimen NIGP167528 (imprint), Nanjing Institute of Geology and Palaeontology, Chinese Academy of Sciences, China. Type locality: Near the Chentaizi Village, Wuhua Township, Ningcheng County, Chifeng City, Inner Mongolia, NE China. Type horizon: Lowest Upper Jurassic, Haifanggou Formation (ca. 161-162 Ma); Ningcheng County, Inner Mongolia, NE China. Diagnosis: As for the genus. Six secondary antenodal crossveins between ScP and RA distal of Ax2; in forewing 10 postnodal crossveins between C and RA not aligned with 10 postsubnodal cross-veins between RA and RP1 basal of pterostigma.

Fig. 1 .

 1 Fig. 1. Log and map of fossil localities. a, Daohugou beds divided by fossil Branchiopoda, blue arrow: layer with Zygokaratawia incompleta nov. sp., red arrow: layer with Parazygokaratawia azari nov. gen., nov. sp.; b, map showing the fossil localities near Daohugou village, blue spot: location for Zygokaratawia incompleta nov. sp.; c, map of the Daohugou fossil bed outcrops,

Fig. 2 .

 2 Fig. 2. Zygokaratawia incompleta nov. sp., holotype NIGP167276. a, complete habitus; b, right hindwing, dry; c, right hindwing, under alcohol. Scale bars: 1 cm.

Fig. 3 .

 3 Fig. 3. Parazygokaratawia azari nov. gen., nov. sp., holotype NIGP167528. a, complete habitus; b, left and right forewings, dry. Scale bars: 1 cm.

Fig. 4 .

 4 Fig. 4. Parazygokaratawia azari nov. gen., nov. sp., holotype NIGP167528. Hindwing. Scale bar: 5 mm.

  Type horizon: Lowest Upper Jurassic, Haifanggou Formation (ca. 162-163 Ma); Inner Mongolia, NE China.

	Diagnosis: Hindwing pterostigma strongly basally recessed, with ten cells between C and RA
	distal of pterostigma; 12 postnodals; 12 crossveins in antesubnodal area; a strongly oblique
	crossvein between MAa and base of RP3/4; 10 crossveins in Bqr space.
	Description: Thorax large, 4.4 mm wide, 5.2 mm long, but compressed. Hind wing hyaline,
	33.3 mm long, 7.5 mm wide, widest part at level of nodus; distance between base and arculus
	4.4 mm, arculus and nodus 10.0 mm, nodus and pterostigma 11.2 mm, pterostigma and apex
	5.3 mm; a rather long petiole, 2.4 mm long, 1.4 mm wide; anal area very narrow, 3.1 mm long,
	0.7 mm wide, nearly triangular in shape, with one row of irregular cells between AA and AP;

Acknowledgements

We sincerely thank thre anonymous referees for their very useful comments on the first version of the paper. We are grateful to Li X-R for photography. This work was funded by the Ministry of Science and Technology (2016YFC0600406), the Strategic Priority Research Program of the Chinese Academy of Sciences (XDB18000000), the program Macroevolutionary Processes and Palaeoenvironments of Major Historical Biota (XDPB05) of the Chinese Academy of Sciences, and the National Natural Science Foundation of China (41688103 and 91514302). This study is a contribution to UNESCO-IUGS IGCP Project 632.