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

Olivier Ruas
email: olivier.ruas@inria.fr

François Taïani
email: francois.taiani@irisa.fr

Nobody cares if you liked Star Wars: KNN graph construction on the cheap

K-Nearest-Neighbors (KNN) graphs play a key role in a large range of applications. A KNN graph typically connects entities characterized by a set of features so that each entity becomes linked to its k most similar counterparts according to some similarity function. As datasets grow, KNN graphs are unfortunately becoming increasingly costly to construct, and the general approach, which consists in reducing the number of comparisons between entities, seems to have reached its full potential. In this paper we propose to overcome this limit with a simple yet powerful strategy that samples the set of features of each entity and only keeps the least popular features. We show that this strategy outperforms other more straightforward policies on a range of four representative datasets: for instance, keeping the 25 least popular items reduces computational time by up to 63%, while producing a KNN graph close to the ideal one.

Introduction

K-Nearest-Neighbors (KNN) graphs play a crucial role in a large number of applications, ranging from classification [START_REF] Nodarakis | Rapid aknn query processing for fast classification of multidimensional data in the cloud[END_REF] to recommender systems [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Levandoski | Lars: A location-aware recommender system[END_REF][START_REF] Linden | com recommendations: Item-to-item collaborative filtering[END_REF]. In a KNN graph, every entity (or node) is linked to its k closest counterparts, based on a given similarity metric. Despite being one of the simplest model of machine learning, computing an exact KNN graph4 is unfortunately a highly time consuming task. A simple brute force approach for instance has a quadratic complexity in the number of entities. For applications for which data freshness is more valuable than the exactness of the results, such as news recommenders, such computation time is prohibitive. To overcome these costs, most applications therefore compute an approximate KNN graph by using preindexing mechanisms [START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF][START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF] or by exploiting greedy incremental strategies [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] to reduce the number of similarity computations. However, it seems hard to lower even further that number.

In this paper we focus on an orthogonal approach, and leverage sampling as a preliminary pruning step to accelerate the time to compute similarities between two entities. Our proposal stems from the observation that many KNN graphs computations are performed on entities (users, documents, molecules) linked to items (e.g. the web pages an user has viewed, the terms of a document, the properties of a molecule). In these KNN graphs, the similarity function is expressed as a set similarity between bags of items (possibly weighted), such as Jaccard's coefficient or cosine similarity. The goal of sampling is to limit the size of these bags of items and thus the time to compute the similarity.

Sampling might however degrade the resulting approximated KNN graph to a point where it becomes unusable, and must therefore be performed with care.

In this paper we propose to sample the bags of items associated with each entity to a common fixed size s, by keeping their s least popular items. Our intuition is that less popular items are more discriminant when comparing entities than more popular or random items. For instance, the fact that Alice enjoys the original 1977 Star Wars movie tells us less about her tastes than the fact she also loves the 9 hour version of Abel Gance's 1927 Napoléon movie.

We compare this policy against three other sampling policies: (i) keeping the s most popular items of each entity, (ii) keeping s random items of each entity, and (iii) sampling the universe of items, independently of the entities. We evaluate these four sampling policies on four representative datasets. As a case study, we finally assess the effects of these strategies on recommendation, an emblematic application of KNN graphs. Our evaluation shows that our sampling policy clearly outperforms the other policies in terms of computation time and resulting quality: keeping the 25 least popular items reduces the computational time by up to 63%, while producing a KNN graph close to the ideal one. The recommendations done by using the resulting KNN graphs are moreover as good as the one relying on the exact KNN graph on all datasets.

The rest of this paper is organized as follows. In Section 2 we formally define the context of our work and our approach. The evaluation procedure is described in Section 3. Section 4 presents our experimental results. The related work is discussed in Section 5 and we conclude in Section 6.

2 Problem Statement: reduce KNN computation time.

System model and problem

For ease of exposition, we will speak about users rather than entities, but our approach remains applicable to any entity-item dataset. We consider a set of users U = {u 1 , .., u n } in which each user u is associated with a set of items (the movies this user has liked, the pages she has viewed), termed her profile, and noted P u . We note I the universe of all items: I = ∪ u∈U P u .

A k-nearest neighbor (KNN) graph associates each user u with the set of k other users knn(u) ⊆ U which are closest to u according to a given similarity metric on profiles:

sim : U × U → R (u, v) sim(u, v) = f sim (P u , P v ).
Thus computing the KNN graph results in finding knn(u) for each u such that

knn(u) ∈ argmax S∈P(U \{u}):|S|=k v∈S sim(u, v), (1)
where P(X) is the powerset of a set X. We focus in this work on Jaccard similarity, a commonly used similarity metric, but our work can be applied to others. The Jaccard similarity between two users u and v is expressed as the size of the intersection of their profiles divided by the size of the union of their profiles:

f sim (P u , P v ) = J(P u , P v ) = |P u ∩ P v | |P u ∪ P v | (2)
Since

|P u ∪P v | = |P u |+|P v |-|P u ∩P v |
, and since we can store |P u | for every user, computing the size of the intersection is the only non-trivial operation required to compute the Jaccard similarity.

Gance's Napoléon tells us more than Lucas's Star Wars

Computing the intersection P u ∩ P v is time consuming for large sets and is the main bottleneck of Jaccard's similarity. To reduce the complexity of this operation, we propose to sample each profile P u into a subset P u in a preparatory phase applied when the dataset is loaded into memory, and to compute an approximated KNN graph on the sampled profiles. Although simple, this idea has surprisingly never been applied to the computation of KNN graphs on entity-item datasets. Sampling carries however its own risks: if the items that are most characteristic of a user's profile get deleted, the KNN neighborhood of this user might become irremediably degraded. To avoid this situation, we adopt a constant-size sampling that strives to retain the least popular items in a profile.

The intuition is that unpopular items carry more information about a user's tastes than other items: if Alice and Bob have both enjoyed Abel Gance's Napoléon-a 1927 silent movie about Napoléon's early years-they are more likely to have similar tastes, than if they have both liked Star Wars: A New Hope-the 1977 first installment of the series, enjoyed by 96% of users5 .

Our approach: Constant-Size Least Popular Sampling (LP)

More formally, if the size of the profile of an user u is larger than a parameter s, we only keep its s least popular items

P u ∈ argmin S∈P s u i∈S pop(i), (3)
where P s u is the set of subsets of P u of a given size s, i.e. P s u = {S ∈ P(I) : |S| = s ∧ S ⊆ P u }, and pop(i) is the popularity of item i ∈ I over the entire dataset:

pop(i) = |{u ∈ U : i ∈ P u }|. (4)
If the profile's size is below s, the profile remains the same:

P u = P u .
In terms of implementation, we compute the popularity of every item when reading the dataset from disk. We then use Equ. [START_REF] Beygelzimer | Cover trees for nearest neighbor[END_REF] to sample the profile of every user in a second iteration. The sampled profiles are finally used to estimate Jaccard's similarity between users when the KNN graph is constructed:

J(P u , P v ) = J( P u , P v ) = | P u ∩ P v | | P u | + | P v | -| P u ∩ P v | (5)
3 Experimental Setup

Baseline algorithms and competitors

Our Constant-Size Least Popular sampling policy (LP for short) can be applied to any KNN graph construction algorithm [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF][START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF]. For simplicity, we apply it to a brute force approach that compares each pair of users and keeps the k most similar for each user. This choice helps focusing on the raw impact of sampling on the computation time and KNN quality, without any other interfering mechanism.

We use full profiles for our baseline, and compare our approach with three alternative sampling strategies: constant-size most popular, constant-size random, and item sampling.

Baseline: no sampling We use our brute force algorithm without sampling as our baseline. This approach yields an exact result, which we use to assess the approximation introduced by sampling, and provide a reference computing time.

Constant-size most popular sampling (MP) Similarly to LP, MP only keeps the s most popular items of each profile P u :

P u ∈ argmax S∈P s u i∈S pop(i). (6)
As with LP, we do not sample the profile if its size is lower than s.

Constant-size random sampling (CS) This sampling policy randomly selects s items from P u , with a uniform probability. As above, there is no sampling if the size of the profile is lower than s. In terms of implementation, this policy only requires one iteration over the data. Fig. 1. CCDF of user profile sizes on the datasets used in the evaluation (positive ratings only). Between 77% (movielens1M) and 53% (AmazonMovies) of profiles are larger than the default cut-off value 25 (marked as a vertical bar).

Item Sampling (IS) This last policy uniformly removes items from the complete dataset. More precisely, each item i ∈ I is kept with a uniform probability p to construct a reduced item universe Î (i.e. ∀i ∈ I :

P(i ∈ Î) = p).
The sampled profiles are then obtained by keeping the items of each profile that are also in Î: P u = P u ∩ Î. On average, the profile of all users is reduced by a factor of 1 p , but this policy does not adapt to the characteristics of individual profiles: small profiles run the risk of losing too much of their content to maintain good quality results.

Datasets

We use four publicly available datasets containing movie ratings (Table 1): 3 datasets from the MovieLens project, and one from Amazon. Ratings range from disliking (0.5 or 1) to liking [START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF]. To apply Jaccard similarity, we binarize the datasets by keeping only ratings that reflect a positive opinion (i.e. > 3), before performing any sampling. Figure 1 shows the resulting Complementary Cumulative Distribution Functions (CCDF) of profile sizes for each dataset. For instance, more than 66% of users have profiles larger than 25 in movielens10M (ml10M). This means that a constant-size sampling with s = 25 on movielens10M removes more than 3 millions ratings (-69.23%).

The three Movielens datasets movielens1M (ml1M for short), movielens10M (ml10M) and movielens20M (ml20M) originate from GroupLens Research [START_REF] Harper | The movielens datasets: History and context[END_REF].

They contain movie reviews by on-line users from 1995 to 2015, and only consider users with more than 20 ratings.

The AmazonMovies dataset (AM) [START_REF] Mcauley | From amateurs to connoisseurs: modeling the evolution of user expertise through online reviews[END_REF] aggregates movie reviews received by Amazon from 1997 to 2012. To avoid users with very few ratings (the so-called cold start problem), we only consider users with at least 20 ratings.

Evaluation metrics

We measure the effect of sampling along two main metrics: (i) their computation time, and (ii) the quality ratio of the resulting KNN graph.

The time is measured from the beginning of the execution of the algorithm, until the KNN graph is computed. It does not take into account the preprocessing of the dataset, which is evaluated separately in Section 4.2.

When applying sampling, the resulting KNN graph is an approximation of the exact one. In many applications such as recommender systems, this approximation should provide neighborhoods of high quality, even if those do not overlap with the exact KNN. To gauge this quality, we introduce the notion of similarity ratio, which measures how well the average similarity of an approximated graph compares against that of an exact KNN graph. Formally we define the average similarity of an approximate KNN graph G KNN as

avg sim( G KNN ) = E (u,v)∈U 2 :v∈ knn(u) f sim (P u , P v ), (7)
i.e. as the average similarity of the edges of G KNN , and we define the quality of G KNN as its normalized average similarity

quality( G KNN ) = avg sim( G KNN ) avg sim(G KNN ) , (8)
where G KNN is an ideal KNN graph, obtain without sampling.

A quality close to 1 indicates that the approximate neighborhoods of G KNN present a similarity that is very close to that of ideal neighborhoods, and can replace them with little loss in most applications, as we will show in the case of recommendations in our evaluation.

Throughout our experiments, we use a 5-fold cross-validation procedure which creates 5 training sets composed of 80% of the ratings. The remaining 20%, i.e. the training sets, are used for recommendations in Section 4.4. Our results are the average on the 5 resulting runs.

Experimental setup

We have implemented the sampling policies in Java 1.8. We ran our experiments on a 64-bit Linux server with two Intel Xeon E5420@2.50GHz, totaling 8 hardware threads, 32GB of memory, and a HHD of 750GB. We use all 8 threads. Our code is available online 6 . In our experiments, we compute KNN graphs with k set to 30, which is a standard value.

Experimentations

Reduction in computing time, and quality/speed trade-off

The baseline algorithm (without sampling) produces an exact KNN graph, with a quality of 1. To compare the different sampling policies (LP, MP, CS and IS) on an equal footing, we configure each of them on each dataset to achieve a quality of 0.9. The resulting parameter s ranges from 15 (LP on AM) to 75 (MP on movielens1M), while p (for IS) varies between 0.35 (on AmazonMovies) and 0.68 (on movielens20M). Table 2 summarizes the computation times measured on the four datasets with the percentage time reduction obtained against the baseline (∆ columns), while Figure 2 shows the results on movielens10M. LP outperforms all other policies on all datasets, reaching a reduction of up to 63%.

Because they reduce the size of profiles, sampling policies exchange quality for speed. To better understand this trade-off, Figure 3 3. Preprocessing time (seconds) for each dataset, and each sampling policy, with parameters set so that the resulting KNN quality is 0.9. The preprocessing times are negligible compared to the computation times.

For clarity, we only display points with a quality above 0.7, corresponding to the upper values of s and p. The dashed vertical line on the right shows the computation time of the baseline (producing a quality of 1), while the dotted horizontal line shows the quality threshold of 0.9 used in Table 2 and Figure 2.

Lines closer to the top-left corner are better. The figures confirm that our contribution, LP, outperforms other sampling policies on all datasets. There is however no clear winner among the remaining policies: IS performs well on movielens1M, but arrives last on the other datasets, and MP and CS show no clear order, which depends on the dataset and the quality considered.

Preprocessing overhead

As is common with KNN graph algorithms [START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF][START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF], the previous measurements do not include the loading and preprocessing time of the datasets, which is typically dominated by I/O rather than CPU costs. Sampling adds some overhead to this preprocessing, but Table 3 shows that this extra cost (∆ columns) remains negligible compared to the computation times of Table 2. For instance, LP adds 3.4s to the preprocessing of movielens20M, which only represents 0.07% of the complete execution time of the algorithm (4865s + 11.95s = 4877s). IS even decreases the preprocessing time on 3 datasets out of 4, by starkly reducing the bookkeeping costs of profiles while introducing only a low extra complexity.

Influence of LP at the user's level

Constant size sampling has a different influence on each user, depending on this user's profile's size. Profiles whose sizes are below the parameter s remain unchanged while larger profiles are truncated, thus losing information.

Figure 4 investigates the impact of this loss with our approach, LP, on movielens10M with s = 25 (corresponding to a quality of 0.9). Figure 4a plots the distribution of the similarity error = |J(P u , P v ) -J( P u , P v )| introduced by sampling when is computed for each pair of users (u, v). The figure shows that 35% of pairs experience no error ( = 0), and that 96% have an error below 0.05 (dotted vertical line), confirming that our sampling only introduces a limited distortion of similarities.

Figure 4b represents the impact of LP on the quality of users' neighborhoods, according to the initial profile size of users. For every user u with an initial profile size of |P u |, we compute the average similarity of u's approximated neighborhood knn(u), and normalize this similarity with that of u's exact neighborhood knn(u). The closest to 1 the better. We then average this normalized similarity for users with the same profile size {u ∈ U : |P u | = P }. These points are displayed as a scatter plot (in black, note the log scale on the x axis), and using a moving average of width 50 (red curve). The first dashed vertical line is the value of the truncation parameter s (x = 25). The points after the second vertical line (at x = 1553) represent 24 users (out of 69816) and thus are not statistically significant. As expected, there is a clear threshold affect around the truncation value s = 25, yet even users with much larger profiles retain a high neighborhood quality, that remains on average above 0.75.

Recommendations

We want to evaluate the impact of the loss in quality on a practical use of the KNN graphs. To do so we perform item recommendations using the exact KNN graphs and the approximated graphs produced with LP. We recommend the items that an user u is more likely to like. This likelihood is expressed as a weighted average of the ratings the items received by the neighbors of u, weighted by the similarity of u with them. We use the real profiles, without sampling nor binarization, to compute these predicted ratings. After computing the score of every item, we recommend to u a set R u composed by 30 items with the highest scores:

R u ∈ argmax

R⊆I\Pu:|R|=30 i∈S v∈knnu sim(u, v) * r v,i , (9)

Dataset

Base where r v,i is the rating made by the user v on the item i. We use the same 5-fold cross-validation as used for the KNN graph computation. We consider a recommendation successful when a recommended item is found within the 20% removed ratings (the testing set) with a rating above 3 (r u,i > 3). The quality of the recommendation is measured using recall, the proportion of successful recommendations among all recommendations.

Table 4 shows the recall we obtain by using the exact KNN graphs obtained with the baseline and with LP using when the KNN quality is set to 0.9. In spite of its approximation, LP introduces no loss in recall, and even achieves slightly better scores than the baseline, which shows that our sampling approach can be used with little impact in concrete applications.

Related work

For small datasets, some specific data structures can be used to compute the KNN graphs very efficiently [START_REF] Beygelzimer | Cover trees for nearest neighbor[END_REF][START_REF] Liu | An investigation of practical approximate nearest neighbor algorithms[END_REF][START_REF] Moore | The anchors hierarchy: Using the triangle inequality to survive high dimensional data[END_REF]. On the other hand, these solutions do not scale and computing efficiently exact KNN graphs with large datasets remains an open problem.

For large datasets, an approximation of the KNN graph, called approximate nearest-neighbor (ANN) graph, is computed instead, by decreasing the number of comparisons between users. Locally Sensitive Hashing [START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF][START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF] hashes users into buckets and only users within the same buckets are compared. Depending on the chosen similarity, different hashing functions are used [START_REF] Broder | On the resemblance and containment of documents[END_REF][START_REF] Broder | Syntactic clustering of the web[END_REF][START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF]. Despite being very efficient for KNN queries, the preprocessing is too expensive to compete with other ANN graph algorithms. KIFF [START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF] first assigns to every user the users with which she shares at least one item. Since the Jaccard similarity is null if two users do not share any item, the neighbors research is limited to these ones. This algorithm performs particularly well on sparse datasets. Hyrec [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF] and NNDescent [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] rely on the assumption that the neighbors of the neighbors are more likely to be also neighbors than random users to decrease drastically number of similarity computed.

However it seems that lowering even further the number of similarities is no longer possible. An orthogonal strategy is to speed-up the similarity computation itself by compacting the users' profiles. b-bit minwise hashing [START_REF] Bachrach | Sketching for big data recommender systems using fast pseudo-random fingerprints[END_REF][START_REF] Li | Theory and applications of b-bit minwise hashing[END_REF] relies on a similar approach than LSH to compact users' profiles in order to approximate the Jaccard similarity. It is space efficient but at the expense of a high preprocessing time. In [START_REF] Cui | Exploring bit-difference for approximate knn search in high-dimensional databases[END_REF] the profiles are compacted by using bit arrays: each bit represents a feature, which value has been rounded. This does not scale and cannot be used in our case where the items are the features. To avoid such a problem [START_REF] Gorai | Employing bloom filters for privacy preserving distributed collaborative knn classification[END_REF] uses constant-sized Bloom filters to encode the profiles. Then the Jaccard's similarity is approximated by a bitwise AND operation. Despite its privacy properties and its speed-up, there is a substantial loss in precision.

As far as we know, sampling has never been used to compact the users' profiles, even though it is used in information filtering systems such as collaborative filtering. It can be used to find association rules [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF], to reduce the size of the items' universe to recommend [START_REF] Linden | com recommendations: Item-to-item collaborative filtering[END_REF] and to change the distribution of the training points [START_REF] Mani | knn approach to unbalanced data distributions: a case study involving information extraction[END_REF][START_REF] Pan | One-class collaborative filtering[END_REF]. The popularity is used to solve the cold-start problem [START_REF] Rashid | Getting to know you: learning new user preferences in recommender systems[END_REF] by finding items the new user is likely to rate, but not to represent its profile in a compact manner.

Conclusion

In this paper, we have proposed Constant-Size Least Popular Sampling (LP) to speed up the construction of KNN graphs on entity-item datasets. By keeping only the least popular items of users' profiles, we make them shorter and thus faster to compare. Our extensive evaluation on four realistic datasets shows that LP outperforms more straightforward sampling policies. More precisely, LP is able to decrease the computation time of KNN graphs by up to 63%, while providing a KNN graph close to the ideal one, with no observable loss when used to compute recommendations.

In the future, we plan to investigate more advanced sampling policies, and to explore how sampling could be combined with orthogonal greedy techniques to accelerate KNN graph computations [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF][START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF].

Fig. 2 .

 2 Fig.2. Computation time and KNN quality of the baseline and the sampling policies on movielens10M, when quality is set to 0.9. LP yields a reduction of 44.2% in computation time, outperforming other sampling policies.

  plots the evolution of the computation time and the resulting quality when s ranges from 5 to 200 for LP, MP, and CS (s ∈ {5, 10, 15, 20, 30, 40, 50, 75, 100, 200}), and p ranges from 0.1 to 1.0 for IS (p ∈ {0.1, 0.2, 0.4, 0.5, 0.75, 0.9, 1.0}).

  Fig. 3. Trade-off between computation time and quality. Closer to the top-left corner is better. LP clearly outperforms all other sampling policies on all datasets.

  CCDF of the similarity's error. Only 4% of the users have their similarities changed by more than 0.05. Quality per user as a function of a user's profile size (note the log scale for x).

Fig. 4 .

 4 Fig.[START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF]. Influence on the similarity and the quality of sampling with LP with s = 25 on movielens10M (total KNN quality equal to 0.9).

Table 1 .

 1 The datasets used in our experiments

	Dataset	Users Items Scale Ratings > 3	|Pu|	|Pi| Density
	ml1M [13]	6,038	3,533	1-5		575,281 95.28 162.83 2.697%
	ml10M [13] 69,816 10,472 0.5-5	5,885,448 84.30 562.02 0.805%
	ml20M [13] 138,362 22,884 0.5-5	12,195,566 88.14 532.93 0.385%
	AM [20]	57,430 171,356	1-5	3,263,050 56,82 19.04 0.033%
			1			ml1M
		P(|UP|≥x)	0.4 0.6 0.8			ml10M ml20M AM
			0.2
			0
			1	10	100	1000	10000
				User profile size

Table 2 .

 2 Computation time (s) of the baseline and the 4 sampling policies. The parameters were chosen to have a quality equal to 0.9. LP reduces computation time by 40% (ml1M) to 63% (AM), and outperforms other sampling policies on all datasets.

	Dataset Base.	LP ∆ (%)	MP ∆ (%)	CS ∆ (%)	IS ∆ (%)
	ml1M	19	11 -40.5	14.3	-24.7	14.2	-25.3	12.9	-32.1
	ml10M	2028 1131 -44.2 1416.6	-30.1 1461.6	-27.9 1599.8	-21.1
	ml20M	8393 4865 -42.0 5766.0	-31.3 5965.0	-28.9 6535.3	-22.1
	AM	1862 687 -63.1 817.8	-56.1 748.1	-59,8 850.0	-54.4

  3. Trade-off between computation time and quality. Closer to the top-left corner is better. LP clearly outperforms all other sampling policies on all datasets.

	Dataset Base.	LP ∆ (s) MP ∆ (s)	CS ∆ (s)	IS ∆ (s)
	ml1M	0.36 0.50 +0.14 0.49 +0.13 0.46 +0.10 0.33 -0.03
	ml10M	4.03 5.49 +1.46 5.67 +1.64 4.99 +0.96 3.98 -0.05
	ml20M	8.55 11.95 +3.40 12.35 +3.80 11.05 +2.50 8.71 +0.16
	AM	3.42 4.90 +1.48 4.70 +1.28 4.32 +0.90 2.41 -1.01
	Table

Table 4 .

 4 Recommendation recall without sampling (Base.) and using the Least Popular (LP) policy (total KNN quality set to 0.9).

		.	LP	∆
	movielens1M	0.218 0.220 +0.002
	movielens10M	0.273 0.275 +0.002
	movielens20M	0.256 0.258 +0.002
	AmazonMovies 0.595 0.596 +0.001

We focus here on the computation of the whole graph, which is different from the related but distinct problem of answering KNN queries.

https://www.rottentomatoes.com/m/star_wars, accessed 21 Feb. 2018

https://gitlab.inria.fr/oruas/SamplingKNN

Acknowledgments

This work was partially funded byt the PAMELA project of the French National Research Agency (ANR-16-CE23-0016), the Web-Alter-Ego Google Focused Award, the ANR-DFG joint project DISCMAT (ANR-14-CE35-0010) and the DeSceNt project granted by the Labex CominLabs excellence laboratory of the French Agence Nationale de la Recherche (ANR-10-LABX-07-01).


Da Mathieu
email: mathieu.da-silva@lirmm.fr

Emanuele Silva
email: emanuele.valea@lirmm.fr

Marie-Lise Valea

Sophie Flottes
email: flottes@lirmm.fr

Giorgio Di Dupuis
email: dupuis@lirmm.fr

Bruno Natale
email: dinatale@lirmm.fr

Rouzeyre
email: rouzeyre@lirmm.fr

Encryption of test data: which cipher is better?

Keywords: Test and Security, Test data encryption, Block cipher, Stream cipher

Testing is a mandatory step in the Integrated Circuit (IC) production because it ensures the required quality of the devices. The most common solution for easing IC testing is the scan chain insertion. This way, a tester can control and observe the internal states of the circuit through dedicated pins. However, a malicious user can exploit this infrastructure in order to extract secret information stored inside the chip. This is the case for cryptographic circuits where partially encrypted results can be observed by shifting out the scan chain content and exploited to retrieve secret keys. Existing countermeasures consist in encrypting the scan content, ensuring the confidentiality of the exchanged messages between the circuit and the tester. The encryption techniques that have been proposed so far rely on the use of two different ciphers: stream ciphers and block ciphers. In this paper, we present pros and cons of both solutions in terms of security and performance. The purpose is to provide an overview of the state-of-the-art in test data encryption and to give elements of comparison between the two ciphers.

I. INTRODUCTION

Steady advances in the semiconductor technology have resulted in devices with hundreds of millions of transistors. The consequence is an increasing probability of physical defects in manufactured Integrated Circuits (ICs), each possibly leading to the failure of the system. Typical defects are shorts or opens involuntarily created during IC manufacturing. All ICs are thus tested after production in order to sort out faulty devices. The circuits that pass the manufacturing test are then packaged. A second test is performed on the packaged devices to eliminate those that may have been damaged during the packaging process or assembled into faulty packages. Finally, other tests are performed after the assembly of ICs on boards. They are used to ensure the final quality of the IC before going to market. Testing is therefore an important step along the IC production, representing half of the cost of the final product. Test costs include development costs (test sequence computation), implementation costs (design practices for high testability) and application costs (time needed to test every single IC), the latter representing a recurrent cost since every single IC must be tested before shipping.

Design-for-Testability (DfT) is a domain of paramount importance. Its goal is to maximize the capability in detecting faults at test time, possibly to perform diagnosis, while minimizing the test time and the required number of additional pins. The most popular DfT technique for dealing with sequential circuits is the scan chain insertion. It consists in replacing the Flip-Flops (FFs) of the IC by Scan Flip-Flops (SFFs). These SFFs are serially connected to form one or several shift-registers, the so-called scan chain(s). In mission mode, the SFFs behave as regular FFs while in test mode they can be serially written or read through scan-in and scan-out pins. Doing so, a tester can control the internal states of the IC by shifting-in test vectors into the scan chain(s), and it can observe internal states stored into the scan chain(s) by shiftingout test responses. An Automatic Test Pattern Generator (ATPG) is used to produce test vectors depending on the target fault models, expected fault-free responses are computed as well. The test procedure consists in serially shifting the test vectors inside the scan chain, and collecting the corresponding responses. The tester compares then the actual test responses with the expected ones in order to identify the presence of faults within the circuit.

Note that the scan-based test procedure introduces numerous cycles for each test data since test patterns and test responses must be serially propagated in the scan chain(s). Fortunately, while a test response is shifted out for observation, a new test vector can be concurrently scanned-in the same scan chain. Test time is thus financially affordable thanks to the simultaneous scan-in and scan out operations.

Unfortunately, scan chains jeopardize the security of the data processed by the IC. The observability feature provided by the test infrastructures can indeed be a source of information leakage, useful to retrieve secret keys of devices implementing cryptographic primitives, such as the Advanced Encryption Standard (AES) [START_REF] Daemen | The Design of Rijndael[END_REF]. The target of the attack in that case is the AES round register that store partial encrypted results. The scan attack consists in scanning out the content of this round register after the execution of the first AES round. It has been shown in [START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF] that the scan attack to retrieve the whole 128-bit secret key of an AES crypto-processor can be completed applying on average 512 plaintexts.

Attacks performed on the scan chains are called "scanbased attacks" [2]- [START_REF] Subidh | New scan-based attack using only the test mode[END_REF]. These hardware attacks do not require any invasive handling nor sophisticated equipment. On the other hand, a countermeasure consisting in disconnecting test IOs after manufacturing is not entirely satisfactory as it restrains debug and diagnostic during the IC life cycle.

Beside the security threat involving the scan chains, standard test interfaces can also be maliciously exploited. The IEEE 1149.1 [START_REF] Committee | IEEE Standard Test Access Port and Boundary-Scan Architecture[END_REF] standard, named JTAG, was originally used for testing printed circuit boards. With the increasing number of cores implemented inside System-on-Chips (SoCs), the IEEE 1500 [START_REF]IEEE Standard Testability Method for Embedded Core-based Integrated Circuits[END_REF] standard was proposed to facilitate their testing. Nowadays, complex ICs integrate a great variety of instruments to ease test and diagnosis. Interfacing this large number of embedded instruments with the user is a challenge that has been addressed by introducing Reconfigurable Scan Networks (RSNs). The RSNs have been standardized in the IEEE Std. 1687 [START_REF]IEEE Standard for Access and Control of Instrumentation Embedded within a Semiconductor Device[END_REF], named also IJTAG. They provide a flexible and scalable access to the instruments. These test infrastructures usually allow the access to the scan chains after IC packaging, since the dedicated pads on the die are only accessible during manufacturing test. Moreover, standardized infrastructures are not strictly limited to test purposes, they also allow the access to the circuit for debugging. An attacker can use these structures to steal the contents of on-chip memories or to modify the firmware. The test infrastructure usually requires also the connection of the devices to a network, organized in a daisy chain structure. This represents another threat inside the chip. Indeed, if a malicious device is connected to the test daisy chain, this device can read and/or modify the test data shifted through it, in order to steal confidential data, or to force the device into an illegal behavior. In order to prevent misuse of these test infrastructures, several countermeasures have been proposed in the literature, protecting the access to the scan chains as well as the debugging features.

One of these countermeasures consists in the encryption of test data shifted to and from the test interface. An authorized user encrypts the test vectors off-chip using the established secret key. The encrypted test vectors are shifted in the circuit through the test interface. On-chip decryption is performed before the test vectors are applied to the circuit. The resulting test responses are then encrypted before scanning them out of the circuit. The authorized tester collects the encrypted test responses, and decrypts these data in order to compare them with the expected ones. This solution has the advantage to preserve testing and debugging facilities, while preventing malicious users from accessing the test infrastructure. Since the test communication is encrypted, a user with no knowledge of the secret key is not able to set the circuit in an undesired state, nor to read its internal states. Another advantage of the test data encryption is to not affect the fault coverage achieved with classical scan design, since the same test data are applied and collected once the encryption/decryption is processed.

The test communication encryption is performed by a symmetric cipher. A cipher transforms a plain message into a ciphered version using a secret key. In the same manner, the inverse transformation is performed in order to retrieve the plaintext from the ciphertext, by using the same secret key.

Two ciphers can be used in the test infrastructures, the stream cipher and the block cipher. The stream cipher performs a bit-to-bit encryption of a serial bitstream, while the block cipher encrypts an 𝑛-bit block of plaintext into a ciphertext block of 𝑛 bits.

In this paper, we give an overview of the existing countermeasures based on test data encryption. We also compare the solutions based on stream ciphers with the ones based on block ciphers.

The remainder of this paper is organized as follows. In Section II we provide a background on block and stream ciphers, as well as the state-of-the-art on the encryption for securing the test infrastructures. In Section III we compare the test data encryption based on stream cipher with the one based on block cipher. Section IV finally draws some conclusions.

II. BACKGROUND

We give in this Section a brief overview on both stream and block ciphers. We introduce then the existing countermeasures based on these ciphers, in order to compare them in the next Section.

A. Ciphers

A cipher ensures the confidentiality of a communication, executing an encryption function 𝐸 on a message 𝑚, to produce a ciphertext 𝑐 using a secret key 𝑘, such that 𝐸(𝑚, 𝑘) = 𝑐. Only a receiver knowing the key 𝑘 can properly apply the inverse function 𝐷 to retrieve the original message, i.e. 𝐷(𝑐, 𝑘) = 𝑚.

1) Stream ciphers

The stream cipher performs a bitwise XOR operation between the plaintext and a pseudo-random bitstream, called keystream, generated from a seed. In some stream ciphers (e.g. TRIVIUM [START_REF] De Canniere | TRIVIUM Specifications[END_REF] cipher), the seed is composed of the key 𝑘 and the initial value IV. The key needs to be secret, while the 𝐼𝑉 can be public, but it is supposed to be different for each encryption session. The generated keystream is denoted as 𝑆(𝑘, 𝐼𝑉). The encryption and decryption functions (𝐸, 𝐷) of the stream cipher are thus respectively defined as 𝐸(𝑚, 𝑘) = 𝑚⨁𝑆(𝑘, 𝐼𝑉) = 𝑐, and 𝐷(𝑐, 𝑘) = 𝑐⨁𝑆(𝑘, 𝐼𝑉) = 𝑚.

The first requirement that must be fulfilled in order to consider a stream cipher secure is to produce an unpredictable keystream. This way, it is impossible to retrieve the plaintext from the ciphertext without knowing the keystream. The second requirement is to never use the same keystream more than once. In the case where two different plaintexts 𝑚 1 and 𝑚 2 are encrypted with the same keystream 𝑆(𝑘, 𝐼𝑉), an attacker can exploit the XOR of the two respective ciphered messages 𝑐 1 and 𝑐 2 . Indeed, this operation leads to remove the encryption:

𝑐 1 ⨁𝑐 2 = (𝑆(𝑘, 𝐼𝑉)⨁𝑚 1 )⨁(𝑆(𝑘, 𝐼𝑉)⨁𝑚 2 ) = 𝑚 1 ⨁𝑚 2 . The XOR between two messages can then be exploited in a differential attack, such as it is the case for scan attacks [START_REF] Daemen | The Design of Rijndael[END_REF][START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF][START_REF] Darolt | Scan Attacks and Countermeasures in Presence of Scan Response Compactors[END_REF][START_REF] Da Rolt | Are advanced DfT structures sufficient for preventing scan-attacks?[END_REF]. That's why it is important to use a different seed, i.e. a different IV and/or secret key, to initialize the stream cipher between different encryption sessions.

2) Block ciphers

The block cipher executes iterative transformations based on substitutions and permutations on fixed-length groups of bits, called blocks. The transformation function depends on a secret key. The block encryption results in the diffusion and confusion of the plaintext on the ciphertext at each iteration of the execution. The iterations performed by the block cipher are called rounds.

The most used block cipher is defined by a standard, named AES [START_REF] Daemen | The Design of Rijndael[END_REF]. Nevertheless, AES may induce a large area overhead to the device under test (see Tab. 1). For this reason, lightweight block ciphers implying a lower area cost have been studied, such as PRESENT [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF]. This block cipher guarantees a lower security level than AES, but cryptoanalysis studies show that it is enough for most applications. The encryption is performed on block size of 64 bits in 31 rounds with two possible lengths for the secret key, 80 bits or 128 bits.

B. Test data encryption

Several countermeasures to the scan attacks have been reported in the literature [START_REF] De Canniere | TRIVIUM Specifications[END_REF]- [START_REF] Silva | Experimentations on scan chain encryption with PRESENT[END_REF] to ensure the confidentiality of the exchanged test data between the tester and the circuit, while preserving the use of the test interface for authorized users. These solutions are applied to the existing test infrastructure by inserting two ciphers in the circuit. One is placed at the serial input of the test interface in order to decrypt the encrypted test data sent by the user. The other is placed at the serial output in order to encrypt the test responses before being shifted out of the circuit.

The decryption performed at the scan-in of the test interface takes the controllability of the circuit away from an unauthorized user, who is unable to apply chosen data. The encryption performed at the scan-out of the test interface prevents him/her from observing the plain scan content. An attacker is thus not able to perform scan attacks, nor illegally debugging the circuit. The confidentiality established between the protected circuit and the tester ensures also a protection from threats placed inside the chip, such as malicious devices connected to the test daisy chain. The encryption prevents these devices from making sense of the sniffed encrypted data, or from modifying them in a controlled way.

The encryption of test data proposed in the literature is based on stream ciphers as well as on block ciphers. The stream cipher used to encrypt the test communication is the TRIVIUM [START_REF] De Canniere | TRIVIUM Specifications[END_REF], because of its low silicon footprint. The pseudo-random sequence, used as keystream, is generated with a Non-Linear Feedback Shift Register (NLFSR) from an 80-bit secret key and an 80-bit IV. The TRIVIUM stream cipher encrypts the test interfaces of JTAG in [START_REF] De Canniere | TRIVIUM Specifications[END_REF], IEEE 1500 in [START_REF] Rosenfeld | Security-aware SoC test access mechanisms[END_REF] and IJTAG in [START_REF] Kan | Echeloned IJTAG data protection[END_REF], while the PRESENT block cipher is used to encrypt the scan chain in [START_REF] Silva | Scan chain encryption for the test, diagnosis and debug of secure circuits[END_REF] [START_REF] Silva | Experimentations on scan chain encryption with PRESENT[END_REF]. We will see the pros and cons of each encryption method in the next section.

III. COMPARISON: STREAM VS BLOCK ENCRYPTION

We evaluate the stream-based countermeasures and the block-based ones according to several cost functions: the area and power overheads, the impact on the testing cost and the provided security level.

A. Area and power consumption overhead

Tab. 1 shows the area and power consumption for the AES [START_REF] Daemen | The Design of Rijndael[END_REF], the PRESENT [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF] block cipher with 128-bit secret key, and for the TRIVIUM [START_REF] De Canniere | TRIVIUM Specifications[END_REF] stream cipher.

Stream ciphering is the technique that has been preferred so far in the literature [START_REF] De Canniere | TRIVIUM Specifications[END_REF]- [START_REF] Kan | Echeloned IJTAG data protection[END_REF]. The choice of the stream cipher is motivated by the lower impact on area and power costs. Block ciphers imply the usage of a larger area footprint than stream ciphers, as is the case for the AES block cipher. However, some modified versions of the AES have been designed to be lightweight, such as PRESENT. PRESENT block cipher and TRIVIUM stream cipher have similar costs in terms of area and power consumption, as shown in Tab. 1.

A more realistic estimation of area and power costs takes into account the number of ciphers that have to be implemented. In fact, depending on whether the encryption is performed with block or stream ciphers, a different number of ciphers must be placed inside the circuit. The block-based solution [14][15] requires two ciphers, one dedicated to the decryption of the test patterns, the other dedicated to the encryption of the test responses (both test vector in and test response out are concurrent operations).

Conversely, the stream-based solutions [START_REF] De Canniere | TRIVIUM Specifications[END_REF]- [START_REF] Kan | Echeloned IJTAG data protection[END_REF] can use only one stream cipher to generate both the decryption and encryption keystream. Therefore, if a lightweight block cipher is used, which has a cost comparable to the stream cipher, the block-based solutions implies twice more area and power overhead, due to the duplication.

B. Testing cost

The impact on test coverage is also important to evaluate the countermeasures applied to the test infrastructure. The set of faults that are detected by the test sequences, originally generated by the ATPG, must not decrease because of the insertion of the security countermeasure. The encryption of test data assures this condition. The content of the applied test vectors and the produced responses is not disrupted by the additional encryption/decryption steps. Concerning the test of the ciphers themselves, authors in [START_REF] Silva | Scan chain encryption for the test, diagnosis and debug of secure circuits[END_REF] [START_REF] Silva | Experimentations on scan chain encryption with PRESENT[END_REF] showed that the extra logic introduced for encryption is tested in the same time as the test data are processed. Therefore, there is no impact on the original test coverage even with the implementation of the ciphers.

Nevertheless, the decryption/encryption of the test data shifted through the test interface adds a cost in terms of test time. It is important to increase as less as possible the test time, since this overhead has an impact on the cost of each sample of the circuit. If this is not taken into account, the time to test an entire product chain can increase significantly.

Concerning the stream cipher, an additional initialization time is required. This overhead is 1152 clock cycles for the TRIVIUM, representing a marginal cost compared to the millions of clock cycles needed to test an entire SoC. Moreover, since both the testing interface and the stream cipher have a serial access, no additional timing overhead is required. Contrariwise, the parallel interface of the block cipher requires padding the test data acquired serially into a multiple of the block size. The padding of test data results in additional clock cycles to complete the shifting operations, implying a test time overhead on each pattern. This results in higher overhead than the stream-based solutions. However, an optimization is proposed in [START_REF] Silva | Scan chain encryption for the test, diagnosis and debug of secure circuits[END_REF] [START_REF] Silva | Experimentations on scan chain encryption with PRESENT[END_REF], based on an alternative DfT approach that makes the scan chain length multiple of the block size. Block ciphers have thus to be adapted to cope with the serial interface of the testing infrastructures.

Ciphers

C. Security

As shown in Section II.B, the state-of-the-art countermeasures based on the test communication encryption protect against the aforementioned threats. However, the stream-based solutions [START_REF] De Canniere | TRIVIUM Specifications[END_REF]- [START_REF] Kan | Echeloned IJTAG data protection[END_REF] show a vulnerability due to the mismanagement of the seed generating the keystream. In this case, the attacker has the possibility to provoke the generation of the same keystream to encrypt different test data. The requirement on the use of the stream cipher, stated in Section II.A.1), is therefore not respected, circumventing the encryption in the case of differential scan attacks [START_REF] Daemen | The Design of Rijndael[END_REF][START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF][START_REF] Darolt | Scan Attacks and Countermeasures in Presence of Scan Response Compactors[END_REF][START_REF] Da Rolt | Are advanced DfT structures sufficient for preventing scan-attacks?[END_REF]. This security flaw is not present on the block-based countermeasures, representing therefore a more secure encryption solution than the stream-based ones. Tab. 2 resumes the pros and cons of both solutions.

The security of the stream-based countermeasures can be improved, making sure that the stream cipher does not generate the same keystream for multiple encryptions. To produce a different keystream, the stream cipher has to change its seed between each cipher initialization, i.e. the secret key and/or the initial value IV. A possible solution is to generate a random IV at each circuit reset. As a result, the stream cipher is initialized with a different seed between each encryption. The differential scan attacks [START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF]- [START_REF] Subidh | New scan-based attack using only the test mode[END_REF] are thus no longer feasible. However, the issue with this solution is to share the random IV to the authorized users in order to perform the encryption/decryption of the test data.

IV. CONCLUSION

Granting access to the internal states of the ICs is fundamental for testing during production, as well as for debugging and diagnosis in the field. Test infrastructures composed of scan networks meet these needs, but compromise the security at the same time. To prevent attacks that exploit the scan side-channel, several countermeasures exist. Some of them are based on the encryption of the test data. Two types of ciphers can be used to encrypt the test communication: the stream and the block cipher. From our study, it comes out that stream ciphers can be preferred due to their smaller overhead and their easy adaptation to the serial test interface. Nevertheless, as implemented in [START_REF] De Canniere | TRIVIUM Specifications[END_REF]- [START_REF] Kan | Echeloned IJTAG data protection[END_REF], the stream-based solutions present a vulnerability, due to a misuse of the stream cipher, while the block-based solutions prove to be secure in all cases.

ACKNOWLEDGMENT

This project has been funded by the French Government (BPI-OSEO) under grant FUI#20 TEEVA (Trusted Execution EVAluation).


Da Mathieu
email: mathieu.da-silva@lirmm.fr

Emanuele Silva

Marie-Lise Valea
email: valea@lirmm.fr

Sophie Flottes
email: flottes@lirmm.fr

Giorgio Di Dupuis
email: dupuis@lirmm.fr

Bruno Natale
email: dinatale@lirmm.fr

Rouzeyre
email: rouzeyre@lirmm.fr

A new secure stream cipher for scan chain encryption

Keywords: Scan attacks, Stream Cipher, Two Times Pad, Scan chain encryption

The accessibility to the internal IP cores of Systems on Chip (SoC) provided by the testing infrastructures is a serious security threat. It has been known for many years that the scan chains can be exploited to retrieve secret keys of cryptoprocessors. Encryption of the scan chain content is one of the proposed techniques to overtake this threat. Many proposals are based on stream ciphers, due to their moderate area cost compared to that of block ciphers. Stream ciphers encrypt data serially with a keystream generated from an Initialization Vector (IV) and a secret key. Stream ciphers have a crucial limitation concerning the encryption of different data with the same keystream, called two times pad. Not enough caution in the IV and secret key management has been exercised in previous proposed works. In this paper, we show how the existing implementations can be exploited to perform a scan attack bypassing the encryption of the scan data. We also present a new implementation of scan chain encryption with a stream cipher, based on the IV generation by a True Random Number Generator (TRNG). Finally, we show that this new implementation is robust against the aforementioned attack.

I. INTRODUCTION

The ongoing breakthrough of the semiconductor industry relies on the shrinking of the technology node. For this reason, the complexity of Integrated Circuits (IC) grows exponentially. Alongside, the probability of encountering faults on silicon dies is not negligible; testing every single die after manufacturing is thus mandatory. Design for Testability (DfT) is used to improve fault coverage and reduce test costs. Scan design is the most popular DfT approach to deal with sequential circuits.

The use of scan chains gives external users amplified controllability and observability on the internal resources of the ICs. This precious feature for testing purposes jeopardizes however the security of the system. The most known attack that exploits the scan chains involves crypto-cores implementing the Advanced Encryption Standard (AES) [START_REF] Daemen | The Design of Rijndael[END_REF]. If the internal registers of the core are linked to the scan chain, the intermediate results of the encryption can be observed through the test infrastructure. An attacker simply needs to feed the AES core with a series of plaintexts and observe the content of one of the internals registers (i.e. the round register) after the first step of each computation. These attacks, known as scan attacks, have been extensively studied in the literature [START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF][START_REF] Da Rolt | Scan Attacks and Countermeasures in Presence of Scan Response Compactors[END_REF][START_REF] Da Rolt | Are advanced DfT structures sufficient for preventing scan-attacks?[END_REF][START_REF] Ali | New scan-based attack using only the test mode[END_REF]. Authors show in [START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF] for instance that it is possible to retrieve the whole 128-bits secret key of an AES core by applying 512 chosen plaintexts on average and scanning out the content of the round register after the first round, thus breaking the security of the whole system.

To overcome this antagonism between test and security several countermeasures have been proposed in the literature. The encryption of the test data shifted to or from the scan chain is one of them. It has the advantages of not impacting the fault coverage achieved with traditional scan design and preserving test and diagnostic facilities. The input test vectors are encrypted off-chip by the tester using a secret key. Inside the chip, the decryption is performed using the same key so that initial test patterns are applied to the logic under test. Test responses stored back to the scan chain are encrypted before being shifted out from the scan chain. The tester must then use the test response encryption key to decrypt the responses offchip. Doing so, an attacker who does not know the secret key is not able to manage the test encryption. Consequently, he/she will not be able to control the IC to a specific state nor to make sense out of the collected data.

Stream ciphers have traditionally been the preferred solution for such test data encryption. This is due to their smaller area footprint and their easier management for serial encryption compared to block ciphers [START_REF] Silva | Scan chain encryption for the test, diagnosis and debug of secure circuits[END_REF] [START_REF] Silva | Experimentations on scan chain encryption with PRESENT[END_REF].

All the countermeasures based on stream ciphers proposed in literature rely on the Trivium cipher [START_REF] De Canniere | TRIVIUM Specifications[END_REF]. The input of the cipher is a seed, which is used to initialize a Non-Linear Feedback Shift Register (NLFSR) that produces a pseudorandom keystream. The keystream is then XORed with the input plaintext. The result is the ciphertext that, from an external point of view, is undistinguishable from a random bitstream.

A requirement of stream ciphers is that the same seed must be used only once. When several data are encrypted with the same keystream, the encryption loses indeed its security and attacks can be performed (two times pad attack).

We show in this paper how the existing countermeasures based on a stream cipher can be attacked. More specifically, we show how the scan chain attack on the AES becomes even easier exploiting this vulnerability. We also present a new implementation of the scan chain encryption with a stream cipher. The proposal is characterized by a new management of the initialization seed that is robust against the attack described in this paper.

The remainder of this paper is organized as follows. In Section II, we provide a background on some key concepts: 1) the scan chain attack on the AES, 2) the state-of-the-art on the stream-based encryption for securing the test infrastructures, 3) the vulnerability that characterizes the existing countermeasures. In Section III, we describe the proposed solution. In Section IV, the results in terms of performance and security are presented. Section V draws some conclusions.

II. BACKGROUND

A. Scan attack on the AES

The AES [START_REF] Daemen | The Design of Rijndael[END_REF] encryption is performed in multiple rounds of computation (e.g. 10 rounds for the 128-bits AES). In each round, the input text is processed through substitution and permutation operations. After several rounds, these operations ensure confusion and diffusion properties. At the end of each round, the text under encryption is stored into a round register.

The scan attack targets the result of the first round of the computation. It consists in scanning out the content of the round register for observation at the end of the execution of the first round. Here follows a description step by step of the differential scan attack procedure to retrieve one key byte [START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF], and being two 128-bits plaintexts that differ on only one byte B such that ( ) = ( ) + 1:

1) The plaintext m1 is given as input to the AES core;

2) The circuit is switched to test mode after the first round is completed;

3) The content of the round register c1 is shifted out through the scan chain;

4) The system is switched back to normal mode; 5) A plaintext m2 is given to the AES core and the same procedure as before is performed to retrieve another result c2;

6) The Hamming distance between the two results is computed.

If the Hamming distance between two partially ciphered text and is equal to specific values, it is possible to derive one byte of the secret key. The strategy used by the attacker is thus to try many plaintexts couples out, until one of these specific values is hit. On average, the attacker needs to try 32 plaintexts out before being able to figure the key out. This procedure is iterated until the whole secret key is computed. According to the experiments performed in [START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF], 512 plaintexts on average are enough to be able to retrieve a 128 bits key.

More advanced scan chain structures [START_REF] Barnhart | OPMISR: The foundation for compressed ATPG vectors[END_REF], such as partial scan and insertion of response compactor for X-masking, make the previous scan attack ineffective since the round register of the AES is not entirely observable. However, improved scan attacks [START_REF] Da Rolt | Scan Attacks and Countermeasures in Presence of Scan Response Compactors[END_REF][4] can deal with these advanced test infrastructures. Experimental data show that only 64 plaintexts on average are sufficient to retrieve the 128-bit secret key of an AES.

In the previous attacks, the plaintexts are applied when the circuit is in normal mode. A simple countermeasure consists in forcing the reset of the circuit as soon as it is switched to test mode. The scan attack described in [START_REF] Ali | New scan-based attack using only the test mode[END_REF] is carried out entirely in test mode, circumventing this simple countermeasure. The differential scan attack is performed shifting the required plaintexts into the circuit through the scan chain.

B. Securing the scan chain with a stream cipher

The scan chain encryption techniques based on stream ciphers that have been proposed in the literature so far rely all on the Trivium stream cipher. The Trivium [START_REF] De Canniere | TRIVIUM Specifications[END_REF] stream cipher is based on an NLFSR that takes a seed as input and produces a pseudo-random keystream as output. The seed is made by an 80-bit secret key and an 80-bit Initialization Vector (IV). While the key is secret, the IV can be public. The only condition is that the same IV should not be used more than once.

Scan chain encryption techniques have been proposed for several test infrastructures. When dealing with SoCs, each IP core has its own scan chain infrastructure. Connecting IPs to a bigger infrastructure compliant to a specific standard makes them reachable by an external user. For instance, the device may embed a test interface that is compliant with the IEEE Std. 1149.1 [START_REF] Committee | IEEE Standard Test Access Port and Boundary-Scan Architecture[END_REF] (JTAG), known as Test Access Port (TAP). Single IP cores are then wrapped with a test wrapper compliant with the IEEE Std. 1500 [START_REF]IEEE Standard Testability Method for Embedded Core-based Integrated Circuits[END_REF]. IP cores can also be reachable by the reconfigurable network compliant with the IEEE Std. 1687 [START_REF]IEEE Standard for Access and Control of Instrumentation Embedded within a Semiconductor Device[END_REF] (IJTAG). Each element attached to the network is gated by a Segment Insertion Bit (SIB) that can be opened or closed according to the desired configuration. K. Rosenfeld and R. Karri propose in [START_REF] Rosenfeld | Attacks and defenses for JTAG[END_REF] an encryption technique that targets the JTAG infrastructure. The IV of the Trivium cipher is hardwired on the device using fuses. The configuration of the fuses is established at manufacturing time and never changes during the device lifetime. The secret key is established before each encryption session with a challengeresponse protocol. The user sends a challenge to the device. The device sends the expected challenge response to the key input of the Trivium. The stream cipher is run in order to produce the first 80 bits of the keystream. These bits are the final key that is used as secret key during the encryption session. If only trusted users know the configuration of the fuses for the IV, they are the only ones who can predict the key used during the session.

In [START_REF] Rosenfeld | Security-aware SoC test access mechanisms[END_REF] the same approach is used for securing the test procedure of IEEE Std. 1500 compliant IP cores. The encryption is performed with the Trivium stream cipher. The management of the IV is not specified by the authors. The secret key is chosen randomly by the user and loaded into the cipher through a dedicated scan chain designed in order to avoid that other IP cores sniff the key. [START_REF] Kan | Echeloned IJTAG data protection[END_REF] the encryption of the IJTAG reconfigurable network. The Trivium stream cipher is also used for that purpose. The proposed implementation for the secret key and the IVs is either with fuses or with Physical Unclonable Functions (PUFs).

S. Kan et al. propose in

C. Exploitation of the two times pad

The stream cipher is considered secure as far as the used keystream is unpredictable from the attacker. The same keystream has also to be used only once. If this condition does not hold, an attack, called two times pad, is possible.

Let assume two texts and encrypted using the same keystream ( , ). If the attacker is able to retrieve the two resulting ciphertexts, the following operation is possible:

( ⊕ ( , )) ⊕ ( ⊕ ( , )) = ⊕
The XOR operation between two ciphertexts results in a XOR operation between the two original plaintexts.

Considering again the scan attack on the AES crypto-core and assuming that and are two test results scanned out of the AES scan chain, the two times pad attack allows to obtain directly the Hamming distance used to retrieve the AES secret key.

Assuming that the stream cipher can be reset between two test sessions, the attack will be carried out as follows:

1) A plaintext is sent as input to the AES block;

2) After the first round of computation, the test response to is stored in the scanned round register and the circuit is switched to test mode;

3) The content of the scanned round register is shifted out of the scan chain and is encrypted by the stream cipher before being delivered to the circuit output;

4) The circuit is reset, in order to force the stream cipher to generate the same keystream again;

5) The same procedure from points 1) to 3) is performed using a second plaintext related to as detailed in section II.A;

6) The two encrypted test responses are XORed.

The obtained result is equivalent to the Hamming distance of the two unencrypted test responses. This means that the encryption of the test responses is totally useless for protecting the AES engine from the scan attack.

The three implementations of the stream-based encryption presented in Section II.B for securing scan chains can all be exploited to perform the two times pad attack.

The technique in [START_REF] Rosenfeld | Attacks and defenses for JTAG[END_REF] allows the key to be controlled by the user (via a challenge-response procedure) and the IV is fixed. This means that if the user sends the same challenge twice to the device (no matter the content of the challenge), he is sure that the same key is used twice. Therefore, the same keystream is produced twice and the attack can be performed.

The proposal described in [START_REF] Rosenfeld | Security-aware SoC test access mechanisms[END_REF] allows the user to directly set the stream cipher key (no challenge-response to set the key). The two times pad attack is easily performed in that case by keeping the key constant during the scan attack.

The countermeasure presented in [START_REF] Kan | Echeloned IJTAG data protection[END_REF] is based on a stream cipher whose secret key and IV are either hardwired with fuses, or given by a challenge-response procedure based on PUFs. The set of secret keys and IVs are unique for each device. Otherwise, the authors do not discuss about changing the values of the keys or the IV between encryption sessions.

The scan attack can thus be applied without any consideration to the encryption done on the test responses.

III. PROPOSED SOLUTION

We propose a new stream-based test data encryption approach for preventing scan attacks. Firstly, we present the principle of the solution and how the secret key and the IV initializing the stream cipher are managed. We describe then the global architecture of the countermeasure with the Trivium implementation.

A. Principle

We assume that the original circuit embeds at least one crypto-core, a secure storage for all the secret keys, and a Secret Key Management Unit (SKMU). We also assume that the circuit implements a scan chain and that at least some Flip-Flops (FFs) of the crypto-core are in the scan network. Otherwise the scan attack on the crypto-core cannot be considered, but neither can be the test of that core. Fig. 1 describes the countermeasure consisting in adding stream ciphers at the input and the output of the scan chain. An attacker unaware of the secret key used for encryption of the test data is not able to set the circuit to a desired state, nor to plainly read the circuit state. Only users with the knowledge of the secret key can access the scan content for debugging purpose.

The secret key of the stream ciphers is stored and managed by the SKMU of the protected crypto-core. By re-using the key management of the original circuit, the solution does not introduce new issues for handling the secret key. The SKMU delivers a dedicated key to authorized users for encrypting the scan content. The IV used to initialize the stream cipher is generated by a TRNG. The random IV is delivered to the external tester via the scan output for the tester to be able to properly encrypt test patterns. The IV is totally random and different after each circuit reset, but does not represent a secret. The key represents the secret, known only by authorized testers.

By initializing the stream ciphers with a different IV, the same keystream is not generated twice to encrypt different data. The proposed solution does not present thus the two times pad limitation presented in Section III.B, preventing an attacker to carry out differential scan attacks. The first step consists in generating test vectors for the original Core Under Test (CUT) and computing the expected test responses by simulation. Before any scan operation, the stream cipher is initialized by generating a random number used as IV. The tester encrypts the test vectors off-chip with the random IV scanned out of the circuit. Once the stream cipher initialization is finished, the tester can perform the CUT testing by scanning in the encrypted vectors. Each encrypted test vector is first decrypted with the keystream generated by the stream cipher at scan input. After that, it is shifted in the scan chain of the CUT. The test vectors are applied to the circuits in order to obtain the CUT test responses. During the shift out operation, the test responses are encrypted with the keystream generated by the stream cipher at scan output. The encrypted test responses are scanned out of the circuit in order to be decrypted off-chip by the tester. Once decrypted, the CUT test responses can be compared with the expected ones.

B. Implementation

We propose to encrypt the scan chain with the Trivium stream cipher, generating a keystream from an 80-bits secret key and an 80-bits IV. First, this stream cipher presents a low cost implementation. Secondly, an alternative implementation allows increasing the keystream throughput (see Fig. 2). Instead of implementing one stream cipher at scan-in and another at scan-out, the implementation of one Trivium is sufficient to generate two different keystreams for a marginal additional cost of 3 AND gates and 11 XOR gates [START_REF] De Canniere | TRIVIUM Specifications[END_REF].

One Trivium stream cipher generates thus the keystream for the decryption process of the test vectors at scan input and the keystream for the encryption process of the test responses at scan output.

The proposed solution has an initialization process, which implies a test time overhead at the beginning of the test procedure. First, the TRNG must have sufficient entropy before generating any random bit, implying a first test time overhead noted . Secondly, once the randomness of the generated bits is ensured, the IV is shifted into the register and, at the same time, scanned out to the tester. The second test time cost, noted ! " , is due to the time to shift the IV. Finally, the last test time overhead #$ % & is due to the initialization of the stream cipher with the IV, generated beforehand, and the secret key, securely stored in the circuit.

Concerning the Trivium stream cipher,

! " = 80 clock cycles since the IV is 80 bits long, and #$ % & = 1152 clock cycles. Once the initialization process is completed, the stream cipher generates the two keystreams to encrypt test data and there is no more test time overhead during the application of the whole test sequence composed of several test vectors.

The global architecture of the proposed solution is represented in Fig. 2. The scan chain encryption is composed of a TRNG, a shift register containing the IV, the stream cipher and the control unit. The control unit manages the initialization process and the encryption performed by the stream cipher.

After a circuit reset, the control unit starts the initialization as soon as the circuit switches from normal mode to test mode. During the entire initialization process, the scan chain is kept inaccessible since the stream cipher does not generate the keystreams. Both the scan input SI and the scan output SO are connected to the TRNG, thanks to the implemented multiplexers. This way, an attacker is not able to send desired data, since the circuit scan chain is connected to the random bitstream generated by the TRNG. An attacker is also not able to observe the internal states of the circuit. He observes the bitstream generated by the TRNG, including the IV value. The IV is firstly stored in the shift register, before initializing the stream cipher. Once the stream cipher setup is finished, the multiplexers are switched to the SI and SO. The stream cipher generates then the two keystreams. The keystream is XORed bit-to-bit to the data (test vectors) at scan input and the keystream is XORed bit-to-bit to the test responses of the circuit. The control unit manages the stream cipher encryption during test mode. If the circuit switches to normal mode, the control unit stops the scan encryption. As soon as the test mode is asserted again, the stream cipher resumes the keystreams generation.

Next section presents the experimental results with the implementation of the Trivium stream cipher. However, any stream cipher can be plugged in the presented solution. If a better stream cipher is proposed in terms of security and/or performance, it can replace the Trivium in the proposed solution.

IV. EXPERIMENTS

The proposed countermeasure requires the implementation of a TRNG, a shift register, a stream cipher and a control unit. We have resumed the area cost of these different submodules in Tab. 1, as well as the time to initialize them. The cost of the TRNG is evaluated to 15 000 Gate Equivalent (GE) from the Synopsys DesignWare IP library [START_REF]DesignWare True Random Number Generator Core[END_REF]. The other submodules imply an area cost of 2 600 GE: 300 GE for the IV shift register, 2 048 for the Trivium stream cipher generating 2 keystreams, and 252 GE for the control unit. Concerning the test time overhead, the TRNG initialization to ensure a good randomness of the bitstream is not specified in the specifications. The IV shifting and the stream cipher setup have an initialization time of 1 232 clock cycles.

The most expensive part of the solution is the TRNG. However, if the circuit already embeds a TRNG (this is almost always the case as far secure circuits are concerned), this one can be used in test mode by our proposed solution. In this case, the TRNG will not introduce any area overhead. We consider thereafter only the cost introduced by the proposed solution without implementing a dedicated TRNG.

Experiments are conducted on for the protection of 5 circuit examples: a Triple-DES core, two pipelined AES cores in the 128 bits and 256 bits versions, a RSA-1024 core and a LEON3 processor. The synthesis has been performed using a 65nm library with Design Compiler [START_REF]Design Compiler[END_REF]. The test coverage has been evaluated with the ATPG tool TetraMAX [START_REF] Synopsys | [END_REF].

A. Area cost

Without considering the TRNG implementation, the proposed solution with Trivium stream cipher implies a total area of 532 combinational cells and 382 FFs. This area cost represents an overhead of 5 409 µm².

Tab. 2 reports the area of each original circuit after regular scan insertion and the overhead introduced by the scan encryption with the Trivium stream cipher. For the smallest circuit, the Triple-DES core, the area cost represents an overhead of 2.88%. For the LEON3 processor, the largest circuit, the proposed solution induces only 0.28% area overhead.

B. Test time cost

The test time overhead introduced by the proposed solution is just due to the initialization time at the beginning of the test procedure. Without considering the TRNG initialization, the scan encryption with Trivium stream cipher requires 1 232 clock cycles of initialization.

Tab. 2 reports the test time overhead of the proposed solution on each original circuit. The row tagged as "Test Cov." reports the test coverage of the circuit. The row "Test Time" reports the test time to apply the whole test sequence and the overhead introduced when the stream cipher encryption is applied. For each circuit, the ATPG has generated the test patterns to achieve 100% of stuck-at fault coverage, except for the LEON3 processor. In that case, the test pattern generation has been stopped at 70% of fault coverage due to limitation of the ATPG tool in terms of memory allocation.

The test time overhead induced by the initialization of the proposed countermeasure represents a marginal cost compared to the entire sequence needed to test a circuit.

The scan encryption does not affect the fault coverage of the original circuit since the test sequence applied on the scan chain of the CUT is the one generated by the ATPG.

The architecture of the scan encryption needs also to be tested. The regular scan chain insertion cannot be applied on the architecture. Otherwise, the internal states of the stream cipher could be analyzed and the secret key revealed. The test of the testing infrastructure is performed in a different way than the classical scan insertion. The stream cipher is tested functionally with the test patterns of the original circuit, which are decrypted at the scan input, and with the test responses encrypted at the scan output. Since the Trivium stream cipher is based on a shift register, a potential fault is easily propagated on the keystreams. Therefore, during the decryption/encryption of the test data, the proposed solution is tested simultaneously with the original circuit.

We have validated this assertion on the circuit examples (Triple-DES, AES-128, AES-256, RSA and LEON3). The test sequence of each circuit is applied to the scan chain encryption based on the Trivium stream cipher. The CUT test patterns are processed by the keystream at scan-input and the CUT test responses are processed by the keystream at scanoutput. As expected, while the sequence detects in the first instance the CUT faults, the sequence covers also 100% stuckat faults in the original circuit and the additional Trivium circuitry. No additional test patterns are needed to test the proposed countermeasure.

C. Security

Compared to the previous countermeasures based on a stream cipher in [START_REF] Rosenfeld | Attacks and defenses for JTAG[END_REF][START_REF] Rosenfeld | Security-aware SoC test access mechanisms[END_REF][START_REF] Kan | Echeloned IJTAG data protection[END_REF], the generation of the keystream is different at each circuit reset due to the random IV, preventing differential scan attacks [START_REF] Yang | Secure scan: a design-for-test architecture for crypto chips[END_REF][START_REF] Da Rolt | Scan Attacks and Countermeasures in Presence of Scan Response Compactors[END_REF][START_REF] Da Rolt | Are advanced DfT structures sufficient for preventing scan-attacks?[END_REF][START_REF] Ali | New scan-based attack using only the test mode[END_REF]. All the test data passing through the scan chain are encrypted with the secret key shared only to authorized users. The scan content is therefore not observable and controllable for an attacker outside or inside the circuit. Even during the initialization process, the controller disables the connection to the scan chain, preventing any clear bitstream to be scanned in or out.

Regarding the security of the Trivium stream cipher, the cryptanalysis is presented in [START_REF] De Canniere | TRIVIUM Specifications[END_REF]. It presents no correlation between the keystream bits. Even if an attacker is able to discover a part of the keystream, he will not be able to retrieve the secret key, nor to predict the future keystream, nor to discover the previous generated keystream. In others terms, even if an attacker resets the scan chain content and shifts out the generated keystream, he will not be able to recover the secret key from the keystream. Moreover, the revealed keystream is not useful to decrypt encrypted test data obtained in another encryption session since a different keystream is used. The cryptanalysis shows also that attacks to guess and determine the internal states of the stream cipher are very complex due to the non-linearity introduced in the keystream generation.

Submodules

A limitation of the stream cipher is the keystream period. The Trivium stream cipher has a finite period of 2 23 bits before re-generating the same keystream. The limit is reached after the encryption of 1 million Terabytes. Even if the attacker is able to run the stream cipher at 1 GHz, corresponding to a frequency far too high for scan chains, it will take 317 years before reaching the period. This limitation is therefore not a security concern.

V. CONCLUSION

Scan chains are a potential threat for circuits embedding a secret, such as crypto-cores. In this paper, we have highlighted a vulnerability presented in previous countermeasures based on stream ciphers. The use of the same IV and the same secret key to encrypt several test data leads to a lack of security against differential scan attacks.

We have proposed a new countermeasure based on stream ciphers, taking into account this weakness by generating a random IV at each circuit reset. The stream cipher generates thus always a different keystream, making ineffective the differential scan attacks. The solution allows to use the scan chains for both testing and debugging/diagnosis only by authorized users. Experiments have been conducted with the Trivium stream cipher. They report a marginal cost in area and test time.

Circuit

Triple

Fig. 1

 1 Fig. 1 Principle of the proposed solution based on stream cipher. A TRNG produces the IV that is used to seed the stream cipher together with the secret key.

Fig. 2

 2 Fig. 2 Architecture of the scan chain encryption based on stream cipher

  Cost of the scan chain encryption with TRIVIUM stream cipher on multiple circuits

			-DES	Pipelined AES128	Pipelined AES256	RSA 1024	LEON3
		Scanned	Scan Encrypt.	Scanned		Scanned		Scanned		Scanned
		Circuit	Overhead (%)	Circuit		Circuit		Circuit		Circuit
	Cell Area	187 494	+2.88	367 926	+1.47	669 193	+0.81	468 415	+1.15	1 902 095	+0.28
	(µm²)
	Test Cov.		100%	100%		100%		100%		70%
	Test Time	687 101	+0.18	1 944 877 +0.06	4 559 845 +0.03 39 405 239 +0.003 11 612 051	+0.01
	(clock cycles)
	Encrypt.		100%		100%		100%		100%		100%
	Test Cov.
	Tab. 2

ACKNOWLEDGMENT

This project has been funded by the French Government (BPI-OSEO) under grant FUI#20 TEEVA (Trusted Execution EVAluation).