Tahiry Razafindralambo
email: tahiry.razafindralambo@insa-lyon.fr

Nathalie Mitton
email: nathalie.mitton@inria.fr

Analysis of the Impact of Hello Protocol Parameters over a Wireless Network Self-Organization

Keywords: C.2.1 [Computer-Communication Networks]: Wireless communication Clustering, MAC, Algorithms, Analysis, Simulations, Wireless Networks

The neighborhood discovery and its maintenance are very important in wireless networks for any applications, especially for routing and every self- * algorithm. Neighbor nodes are usually discovered thanks to the use of the HELLO protocol. This makes this HELLO protocol very important for wireless networks especially for selforganizing the network. Most of layer-3 protocols assume an ideal MAC layer. In such a case, HELLO protocol parameters have no impact over the self-organization. But this is not the case when considering realistic MAC and physical layers. In this paper, we investigate the impact of the parameters of such a protocol over a self-organization structure when considering realistic a MAC layer. We analyze theoretically and by simulations, the joint effect of the HELLO protocol parameters and of the MAC layer characteristics over several network self-organizations.

INTRODUCTION

Ad hoc networks or wireless sensor networks (wireless multihop networks) are composed of devices that communicate via wireless interfaces. They require no fixed infrastructure and no human intervention. Many layer-3 protocols have been proposed in the literature for wireless ad hoc and sensor networks. They range from routing protocols such [START_REF] Perkins | Ad hoc On-demand Distance Vector Routing[END_REF][START_REF] Clausen | Optimized Link State Routing Protocol[END_REF] to clustering protocols [START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF][START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF][START_REF] Mitton | Self-organization in large scale ad hoc networks[END_REF] by going through localization protocols [START_REF] Viana | Self-organization in spontaneous networks: the approach of DHT-based routing protocols[END_REF]. All that protocols assume that nodes have and maintain exact knowledge about specially nearby network nodes (called their neighbors). This knowledge is acquired thanks to small beacon messages (the well-known HELLO messages). The principle is rather simple and may be described as follows. Each network node regularly sends such a HELLO message to advertise its presence. Due to the broadcast nature of radio communications, each sufficiently close host receives this message and may infer that it is a neighbor of the sender. All nodes maintain a neighborhood table, and any localized protocol may make decisions based on this table. Self-organization often relies on a specific partition of the network, called clustering: the terminals are gathered into clusters according to some criteria, each cluster is identified by a special node called cluster-head. Many clustering algorithms have been proposed in the literature. Most of them are based on a metric which allows each node to elect its cluster-head. This metric can be for instance the node identifier [START_REF] Ephremides | A design concept for reliable mobile radio networks with frequency hoping signaling[END_REF][START_REF] Amis | Max-Min d-cluster formation in wireless ad hoc networks[END_REF], the node degree [START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF][START_REF] Chen | Connectivity-based k-hop clustering in wireless networks[END_REF][START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF], a mobility value [START_REF] Basu | A mobility based metric for clustering in mobile ad hoc networks[END_REF], a balanced sum of all of them [START_REF] Chatterjee | WCA: A weight based distributed clustering algorithm for mobile ad hoc networks[END_REF] or a link density value [START_REF] Mitton | Self-organization in large scale ad hoc networks[END_REF]. Among all these clustering heuristics, oldest ones [START_REF] Ephremides | A design concept for reliable mobile radio networks with frequency hoping signaling[END_REF][START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF][START_REF] Basu | A mobility based metric for clustering in mobile ad hoc networks[END_REF][START_REF] Chatterjee | WCA: A weight based distributed clustering algorithm for mobile ad hoc networks[END_REF] build overlapping 1-clusters, e.g. where every node is at most 1 hop away from its cluster-head. However, overlapping 1-clusters offer a structure very weak towards mobility and link instability. Later, protocols building k-clusters have been proposed. Some of them just extend a protocol building 1-clusters like in [START_REF] Chen | Connectivity-based k-hop clustering in wireless networks[END_REF]. Therefore, clusters are still overlapping and remain unstable. Most of these protocols constrain clusters in terms of radius [START_REF] Amis | Max-Min d-cluster formation in wireless ad hoc networks[END_REF][START_REF] Chen | Connectivity-based k-hop clustering in wireless networks[END_REF] or number of nodes [START_REF] Ohta | An adaptive multihop clustering scheme for highly mobile ad hoc networks[END_REF]. As far as we know, only two of them let clusters adapt the underlying topology [START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF][START_REF] Mitton | Self-organization in large scale ad hoc networks[END_REF] and produce unbounded clusters. This makes them more robust towards the topology changes.

Nevertheless, to the best of our knowledge, none of these layer-3 protocols, either for routing or clustering, have taken into account the importance of the reliability of these neighborhood tables on which they all rely. Indeed, even in a static environment, some HELLO packets may be lost because of collisions and delay occurring at the MAC layer level. Therefore, the choice of the MAC layer, the HELLO packet frequency and the time data are kept in memory have importance in order to provide the nodes with a view of their neighborhood as close to the physical one as possible. So, neighborhood tables are not always reliable and since layer-3 protocols mainly rely on them, routing or clustering results are also impacted.

In this paper, we are interested in investigating the impact of realistic MAC and physical layers over a network self-organization. We analyze how the parameters of the HELLO protocol, the choice of the MAC layer protocol and the metric used for clustering may overcome or worsen the effects of the propagation errors. To do so, we study two clustering algorithms proved self-stabilizing, which only differ by the metric used: DDR [START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF] and the density-based algorithm [START_REF] Mitton | Self-organization in large scale ad hoc networks[END_REF]. We study their behavior over two different MAC layer approaches: IEEE 802.11 1 and MadMac [START_REF] Razafindralambo | Increasing fairness and efficiency using the MadMac protocol in ad hoc networks[END_REF]. We provide a theoretical analysis based on stochastic geometry and queue theory to establish the more suitable parameters for the HELLO protocol (HELLO message frequency and data lifetime). We show that these parameters can strongly impact the behavior of the clustering protocols. We highlight that in a network without data communications, changing the MAC protocol does not affect the chosen parameters of the HELLO protocol, contrarily to the metric used for self-organizing the network, which can help to smooth down the link failures occurring at the MAC layer.

The remaining of the paper is organized as follows. Section 2 briefly details the MAC protocols and the clustering algorithms we use. Section 3 provides a theoretical analysis of the HELLO parameters. Section 4 describes our simulations and shows the results. At last, Section 5 concludes by giving future works.

BACKGROUND

Models and Notations

For the sake of simplicity, let's first introduce some notations. We classically model a multi-hop wireless network, by a graph G = (V, E) where V is the set of mobile nodes (|V | = n) and e = (u, v) ∈ E represents a bidirectional wireless link between a pair of nodes u and v if and only if they are within communication range of each other. When two nodes share a bi-directional link, we say that they are neighbors. d(u, v), u, v ∈ V2 denotes the distance in G (in number of hops) between nodes u and v. We note H(u) the cluster-head of node u and

Γ k (u) the set of k-neighbors of u, e.g the set of nodes v such that d(u, v) ≤ k. δ(u) = |Γ(u)| = |Γ1(u)| is the degree of u.

Periodic HELLO Protocol

The HELLO protocol was first described in OSPF version 2 [START_REF] Moy | OSPF -Open Shortest Path First[END_REF]. It works as follows. Each node regularly sends a HELLO message to signal its presence to close nodes and maintains an internal neighborhood table. The frequency of these messages is noted fHELLO. When a node u receives such a message from a node v, u adds v to its neighborhood table, or updates the timestamp of the entry if v was already there. HELLO messages may include several kinds of information (see Section 3) but must contain at least the identifier of the sender. Since a neighbor may move or disappear, deprecated entries of the table are regularly removed thanks to a timer. An entry is deprecated when its associated timestamp is too old (it is higher than a threshold AGEMAX ): this happens when a neighbor has not signaled itself recently, or when the message HELLO it sent has not been received.

MAC Layers

The two MAC layers we study are IEEE 802.11 and MadMac 2 . We study the network self-organization over IEEE 802.11 because it is the widespread technology in the field of wireless ad hoc networks. Most of current wireless cards use the IEEE 802.11 MAC protocol. Nevertheless, IEEE 802.11 has originally been designed to be used with a base station. Thus its use in ad hoc environment leads to some anomalies [START_REF] Chaudet | Experiments of some performance issues with IEEE 802.11b in ad hoc networks[END_REF][START_REF] Heusse | Performance anomaly of 802.11b[END_REF]. Therefore, some alternative MAC layers have been proposed to IEEE 802.11 like MadMac [START_REF] Razafindralambo | Increasing fairness and efficiency using the MadMac protocol in ad hoc networks[END_REF]. In order to fairly study the impact of the MAC layer over the HELLO protocol and then over the self-organization, we need also to evaluate the network behavior over an alternative MAC layer to IEEE 802.11.We thus evaluate the network self-organization over a Mad-Mac layer too. MadMac has been shown to be fairer and less aggressive than 802.11.

802.11 and MadMac are both based on CSMA access method. Before transmitting a data packet, each node listens whether the radio channel is free. If so, the transmission can occur, otherwise, it is deferred. The main difference between MadMac and 802.11 relies in the time a node has to wait before triggering a transmission. This time is much higher in MadMac when nodes are overloaded or undergone collisions, that makes the protocol less aggressive. It is worth noting that in both protocols, the broadcast packet are not acknowledged at the MAC layer.

Self-Organization

In this section, we briefly describe the clustering algorithms we study.For more details, please refer to the corresponding references.

DDR and the density-based algorithms are very similar. They use the same construction algorithm and only differ in the metric they use to take clustering decision. The algorithm they use has been theoretically proved to be self-stabilizing [START_REF] Mitton | Self-stabilization in self-organized multihop wireless networks[END_REF]. It builds non-overlapping k-clusters in a distributed fashion by needing only local information (up to 2 hops away). Furthermore, the resulting clusters are not constrained regarding their size neither in terms of number of nodes nor in terms of cluster diameter. They simply adapt the underlying topology. These features allow us to analyze whether a metric can smooth lower layers errors down. Our idea is that when building overlapping clusters or/and 1-clusters, the structure will be impacted faster and it will be more difficult to distinguish the contribution of such or such metric.

DDR uses the node degree as the metric decision. The densitybased clustering algorithm is based on a metric called density. This link density (noted ρ(u)) considers the ratio between the number of links and the number of nodes in Γ(u) :

ρ(u) = |{e = (v, w) ∈ E | w ∈ {u} ∪ Γ(u) and v ∈ Γ(u)}| δ(u)
Both algorithms run as follows. Each node periodically computes its degree (for DDR) or its density value (for the densitybased algorithm) and broadcasts it to its 1-neighbors e.g., using HELLO packets. Each node is thus able to compare its metric (degree or density) to its 1-neighbors' and decides by itself whether it joins one of them (the one with the highest value) or it wins and elects itself as cluster-head. In case of ties, the node with the lowest identifiers3 wins. In this way, two neighbors can not be both cluster-heads. If node u has joined node w, we say that w is node u's parent in the clustering tree (noted P(u) = w). A node's parent can also have joined another node and so on. A cluster then extends itself until it reaches another cluster.

MOTIVATIONS AND ANALYSIS

HELLO Packets Format

Each protocol of the literature assumes an ideal MAC layer and consider the Unit Disk Graph model [START_REF] Clark | Unit Disk Graphs[END_REF], i.e. nodes u and v are neighbors if and only if the Euclidean distance from u to v (noted |uv|) is lower than R, where R is the transmission range. Links are thus bi-directional. But, when considering a realistic MAC layer, links are not always bi-directional and/or may flap. In our study, since clustering algorithms are designed for bi-directional links, nodes need to only consider bi-directional links. To make every node aware of the bi-directionality of links, HELLO messages must contain the neighborhood tables of the node. Indeed, if node u receives a HELLO message from node v which does not include node u in the neighbor list, link (u, v) is uni-directional.

Moreover, including the neighborhood table in the HELLO messages in mandatory to compute the link density. Indeed, this allows each node to know the neighbors of its neighbors and thus its 2neighborhood. By this way, a node discovers links between two of its neighbors and then is able to compute its density value. Last, in order to build clusters, HELLO packets sent by node u must also contain the degree or the density value of u, u's parent (P(u)) and u's cluster-head (H(u)). Table 1 gives the format of a HELLO packet. This format is thus the same for both clustering protocols.

Motivations

When considering an ideal MAC layer as every clustering scheme of the literature does, parameters such the HELLO packet frequency and the time data is stored do not have any importance. Nevertheless, in a realistic environment, we have to take them into account and measure their impact. Indeed, even in a static environment, some HELLO packet may be lost because of interferences, fading, shadowing and collisions occurring at the MAC layer level. Therefore, the HELLO packet frequency (fHELLO) and the time an entry can remain in the neighborhood table without been refreshed (AGEMAX ) have importance in order to provide a node u with a view of its neighborhood as close to the physical one as possible.

Sending too few HELLO messages leads to obsolete tables while sending too many of them may saturate bandwidth to the detriment of data traffic. Estimating the value of AGEMAX is also a difficult task. In most of the literature [START_REF] Perkins | Ad hoc On-demand Distance Vector Routing[END_REF][START_REF] Clausen | Optimized Link State Routing Protocol[END_REF], a node v is generally removed from the neighborhood table of a node u if node u has not received any HELLO packet from node v for 3 * 1 f HELLO s. If AGEMAX is too short, node u consider less neighbors than in reality whereas if the time out is too long, nodes remain in the neighborhood table of node u while they might have disappeared or moved away from yet a long time. In both cases, node u has a wrong view of its environment. Moreover, in wireless ad hoc networks, nodes generally have limited memory size. Thus, if AGEMAX is too high, node memory may quickly be saturated. Hence, both AGEMAX and fHELLO are very important parameters.

Clustering Analysis in the Ideal Case

In the ideal case, at each round, every node has successfully received a HELLO packet from every of its neighbors. For the ideal case, we consider the Unit Disk Graph model [START_REF] Clark | Unit Disk Graphs[END_REF]. Therefore, in a static environment and by considering an ideal MAC layer, parameters such AGEMAX and fHELLO do not have any impact on the clustering scheme.

At the bootstrap step, every node is its own parent and its own cluster-head. Its density value is 1, its degree is 0. Upon reception of a HELLO packet, a node u updates these values. Its density and degree are re-computed. Its parent is chosen among its neighbors and node u takes as cluster-head the cluster-head of its parent.

At the end of the first round, every node knows its neighborhood. At the end of the second round, every node learns its 2neighborhood. From it, it is able to detect whether links are bidirectional and deduces its density value and its degree. At the end of the third round, every node knows the density of their neighbors and is thus able to elect its parent. It will then updates it clusterhead as being the cluster-head of its parent. Before getting the right cluster-head value, each node has to wait k -1 more rounds where 2 sums up these informations.

Neighbor Discovery Analysis

In this section, we provide a theoretically analysis in order to better understand the relation between each parameter of the HELLO protocol. For it, we fist need to compute the probability for a node to be discovered by its neighbors. Since, we run simulation under the NS2 simulator, we compute this probability under the assumptions of NS2 model. Nevertheless, the model we propose and introduce in Section 3.4.2 holds for any model, as soon as the probability of detection is computed according to the assumptions of the model.

Probability of detection

We first compute the probability for a node to be discovered by its neighbors and deduce from it the mean degree of a node in our simulation environment. First, let's introduce some notations. Let's denote by Bv, the ball centered in v and of radius R. Let St be the set of emitting node at time t. Let Pv(u) be the power received at node v from node u. The analysis we perform in this paper are evaluated over the NS2 simulator4 in its 2.27 version. Therefore, let's describe how NS2 simulates collisions and interferences at a node. In NS2, Pv(u) is such that Pv(u) = Pe |uv| α where Pe is the sending power and |uv| is the Euclidean distance between nodes u and v. Every node of the network sends a message with the same emission power Pe. A node v correctly receives a message from node u at time t if one of the following conditions holds:

• Bv ∩ St = {u} u is the only sending node in Γ(v). • ∀w ∈ Bv ∩ St, Pv (u)
Pv (w) > K where K is a constant.

Let's consider the scenario illustrated on Fig. 1. Nodes u, v and w are such that |uv| = r < R (so u ∈ Γ(v)), w ∈ Γ(v) ∩ Γ(u). In such case, if both nodes u and w send a message to v, node v will successfully receive the message from A iff

Pv (u) Pv (w) > K ⇔ |wv| |uv| > α √ K (1)
Since HELLO packets are broadcast 5 and of small size, they are sent without activating the RTS/CTS mechanism. Moreover, a broadcast packet is not acknowledged so when a broadcast packet is lost because of collisions or interferences, the sending node has no clue about it and will not send the packet again. When a node needs to send a message, it draws a random backoff time in [0, 32]. Thus, the probability that two neighbor nodes draw the same backoff value is: P11 = 1 33 . In order to avoid a totally synchronized network, in NS2, a node triggers the transmission of its HELLO packet within the time interval [1/fHELLO -0.25, 1/fHELLO + 0.25] s. If two nodes u and Id(u) δ(u) or ρ(u) P(u) H(u) Neighbor List bi-directional 1-neighbors + 2-neighbors its bi-directional degree + its density Round 3 bi-directional 1-neighbors + 2-neighbors + its neighbors' density/degree its parent Round k -1 its parent's cluster-head its cluster-head Table 2: Sum up of exchanged information in the ideal case v trigger their respective transmissions at time tu and tv, where tv > tu, node v will hear u's message on the carrier and will not send its own message (CSMA principle). Before triggering the HELLO packet transmission the time in NS2 is sampled every 0.05s. Therefore the probability that two nodes choose the exact same time is: P12 = 1 11 . All this implies that any two HELLO packets collide with the probability P1 (probability that two neighbor nodes send their HELLO packet exactly at the same time):

P1 = P11 × P12 = 1 363 (2)
We are interested in the number of neighbors actually detected in NS2. Therefore, we do not consider the whole network but only a "typical point" located at the origin of the plane and its 1-neighborhood. Our model is similar to the one implemented in NS2. Let be a Poisson point process on B(0, R) of intensity λ > 0. We consider a point 0 at the origin for which we study the detected neighborhood (Palm distribution [START_REF] Stoyan | Stochastic geometry and its applications[END_REF]). Let u be a point at distance r (r ≤ R) from the origin. We fix the two points 0 and u and we distribute the Poisson point process in B(0, R) independently of these two points. From it, we study the probability P(r) that node u is detected by node 0. Let's introduce a random variable X which counts the number of the points of the Poisson Point Process lying in B(0, R). Then, the number of neighbors E o detected detected by node 0 after one exchange of HELLO packet is:

E o detected = R 0 λ2πrP(r)dr (3)
We have :

P(r) = P1 * P2(r) (4)
where P1(r) is the probability that node u and node 0 do not send a message at the same time, P2(r) is the probability that node u is not disturbed by a communication in node 0's neighborhood. As already mentioned, according to NS2 assumptions (2), P1 is such that:

P1 = 1 -P1 = 362 363 (5)
As no RTS/CTS neither ACK mechanisms are used, probabilities for drawing a backoff time are independent and the same for each node. P2(r) is the probability that node u is not disturbed by a communication in node 0's neighborhood. This holds if no other node w ∈ Γ(0) emits at the same time than u or if at least a node w ∈ Γ(0) emits at the same time than node u but P0(w) is not strong enough to disturb node u. The probability there is another neighbor of node 0 which emits at the same time than node u will depend on X. Thus:

P2(r) = ∞ n=0 P2 n (r)P[X = n] (6)
where P2 n (r) is the probability that a node at distance r from 0 is detected by 0 knowing that X = n.

As shown by [START_REF] Amis | Max-Min d-cluster formation in wireless ad hoc networks[END_REF], if a node w emits at the same time than node u, node u will not be detected only if

w is such that |w0| > α √ K * |u0|. So, that means that, if d(u, 0) > R α √ K , node u can be detected only if no other node in Γ(0) emits at the same time than itself. So, if X = n, for r > R α √ K : P2 n (r) = P n 1 . Otherwise, if r < R α √
K , node u is detected even if k nodes in B(0, R) send a message at the same time, as soon as each of these k nodes w is such that

|0w| > α √ K * r. We thus have, if X = n, for r < R α √ K : P2 n (r) = n k=0 n k P n-k 1 (1 -P1) k πR 2 -π( α √ Kr) 2 πR 2 k = (1 -P1) 1 - ( α √ Kr) 2 R 2 + P1
n Then, we have :

P2 n (r) = (1 -P1) 1 -( α √ Kr) 2 R 2 + P1 n if r < R α √ K P n 1 otherwise.
Since nodes are distributed according to a Poisson Point Process of intensity λ:

P[X = n] = (λπR 2 ) n n! e -λπR 2
We can now compute P2(r).

If r < R α √ K , P2(r) = ∞ n=0 (1 -P1) 1 - ( α √ Kr) 2 R 2 + P1 n (λπR 2 ) n n! e -λπR 2 = e -λπ( α √ Kr) 2 (1-P 1 ) And if r > R α √ K , P2(r) = ∞ n=0 P n 1 (λπR 2 ) n n!
e -λπR 2 = e -λπR 2 (1-P 1 ) . Thus:

P2(r) = e -λπ( α √ Kr) 2 (1-P 1 ) if r < R α √ K e -λπR 2 (1-P 1 )
otherwise.

Finally, we can compute the mean number of neighbors a node 0 detects: and the probability P for a node to be detected by its neighbor:

E o detected = R 0 2λπrP1P2(r)dr = R α √ K 0 2λπrP1e -λπ( α √ Kr) 2 (1-P 1 ) dr + R R α √ K 2λπrP1e -λπR 2 (1-P 1 ) dr = P1 1-e -λπR 2 (1-P 1 ) (1-P 1 )( α √ K) 2 + λπR 2 e -λπR 2 (1-P 1 ) (1 - 1 α √ K 2 )
P = E o detected [λ] λπR 2 = P1 1-e -λπR 2 (1-P 1 ) (1-P 1 )( α √ K) 2 (λπR 2 ) + e -λπR 2 (1-P 1 ) (1 - 1 α √ K 2 ) (8)
Fig. 2 and 3 plot the theoretical results for K = 16 and α = 4 (default parameters of NS2). One can notice that the higher the nuber of neighbors to discover, the higher the imprecision. Nevertheless, like already claimed, links can be uni-directional because of propagation errors. The node degree δ only counts bidirectional links and thus is the number of nodes detected by node 0 and which have also detected 0.

δ = R 0 2λπrP(r) 2 dr = P 2 1 1-e -2λπR 2 (1-P 1 ) (1-P 1 )(2 α √ K) 2 + λπR 2 e -2λπR 2 (1-P 1 ) (1 - 1 α √ K 2 )
Fig. 4 compares the node degree in an ideal case with the one observed theoretically with MadMac or IEEE 802.11. Results clearly show that a realistic MAC layer impacts the neighbor discovery and the bi-directionality of wireless links.

Evaluating the parameters

In this section, based on the probability detection and the mean effective node degree provided by Section 3.4.1, we try to theoretically capture the dynamic evolution of the neighborhood table of each node based on HELLO packet parameters fHELLO and AGEMAX . To do so, we model the neighborhood table of a node with a M/M/c/c Markov chain by considering the Erlang formulas for birth and death process with c servers [START_REF] Bose | An Introduction to Queueing Systems[END_REF]. Let λ f be the frequency of HELLO packet reception at a node (note that when propagation is error-free, λ f = fHELLO), and µv the removal rate of information for node 0 neighborhood (i.e. 1/AGEMAX).

A M/M/c/c chain captures the evolution of informations contained in the neighborhood table of a typical node. We consider The arrival rate of a HELLO packet is represented by a Poisson Process of parameter λ f . The departure rate of the information contained in a HELLO packet in the neighborhood table follows an exponential law with parameter µv. We chose an exponential law for the sake of simplicity and tractability. The steady state probability distribution of a M/M/c/c Markov chain is similar to a M/G/c/c probability distribution [START_REF] Bose | An Introduction to Queueing Systems[END_REF]. In the latter one, the departure distribution function can be a constant, that is similar to the regular removal of entries in the neighborhood table. Our system contains c servers (the information received from each neighbor of node 0 is considered by node 0 like a client in the system). We assume that the number of physical neighbors that has to be discovered is known. When the system is full (every node is known), each new arrival does not bring any new information, so the packet is not useful. Thus, our system has a queue of length 0. Even if the number of neighbors is known, we do not consider a finite population size. As there is no preemption in the queue policy management, we make the assumption that each received packet (when the system is not full) brings additional information to the observed node. This assumption holds because we cannot distinguish the nodes. This model assumes that there is no preemption when a packet is received. In other words, when node 0 receives a packet from node u, the information is stored in the node 0's table during 1/µv and can not be refreshed. Fig. 5 shows the graphical representation of our chain. Such a chain represents the state of the neighborhood table of node 0. If the system (node 0) is in state i, that means that node 0 has discovered i nodes out of its c neighbors. Note that as in every Markov chain, the probability of simultaneous events is 0, thus receiving simultaneous HELLO packets is impossible. At steady state, the probability to be in state k is given by:

f λ µ v f λ µ v µ v µ v µ v f λ f λ f λ c-1 c i 2 1 0 c.
π (k) = p k . c k .π (0)
where, p = λ f µv and π

(0) = 1 1 + c i=1 p i . c i .
We are interested in the probability for the system to remain in state c, i.e., the probability π (c) . π (c) is the probability for a given node to have a complete knowledge of its neighborhood at a given point of time. π (c) is such that:

π (c) = c c c! . p c c i=0 p i . 1 c!
λ f is the correct packet arrival rate at node 0 (rate of successful reception of a HELLO packet) and can be written as:

λ f = fHELLO × P
where P is the probability of successful reception at node 0 (see Section 3.4.1). Fig. 6 and 7 plot the probability for the Markov chain to be in state π (i) , depending on the number of neighbors.

The different curves show the influence of p (and so of the HELLO protocol parameters). As expected, an increasing value of p increases the probability to be in state π (c) . We can also see that even for a high value of p, the probability for a node to have the full knowledge of its neighborhood is not 1. For a higher degree, the probability to have a complete knowledge is the same as with a low degree for a fixed value of p. These values constitute a lower bound, because of the non preemptive update of information in the Markov chain, but they give a good intuition of the evolution of the neighborhood table and of the impact of the HELLO protocol parameters. One has also to notice that an increasing degree also decreases the value of P and thus reduces the value of p. Therefore, in order to maintain the same probability π (c) , when the degree changes, one has to increase the HELLO packet frequency and/or to increase the value of AGEMAX . Fig. 8 shows the comparison between theoretical results and simulations by plotting the probability π (i) for fHELLO = 1 and µv = 1/3, considering the probability P (8). For the simulations, we run 100 simulations of 50 seconds each and we observed the evolution of the neighborhood table of a given node. Figures show the accuracy of the proposed model for different intensities and for the observed node. From these results, we can say that to behave correctly, protocols relying on the neighborhood discovery have to deal with the inconsistent state of the neighborhood table at each point of time. It is worth noting that this inconsistent state is worsen by mobility and increasing the value of p is not suitable for mobility handling. The next step of this analysis is to include mobility handling.

RESULTS

Simulation Model and Parameters

All simulations are performed over the NS2 simulator in its 2.27 version. The simulator has been modified to reflect the 802.11b DSSS parameter. We have also modified the communication range of each node to reflect 802.11b card based on the specification of wireless card. Nodes are randomly deployed using a Poisson Point Process in a 1000m×1000m square with various levels of intensity λ. In such processes, λ represents the mean number of nodes per surface unit. The communication range R is set to 150m in all tests. Simulation are run during 30s. The results obtained are within a 95% -confidence interval. No mobility pattern is used.

Both clustering algorithms are evaluated over a 802.11 MAC layer and a MadMac layer for each node distribution. Each result is compared to the results obtained with the use of an ideal MAC layer. The ideal MAC layer refers to a Unit Disk Graph model with no interferences, no packet collisions, each message sent is immediately and successfully received by each node within communication range. Each association of protocols MAC-clustering is evaluated for three values of fHELLO: 1/f1 = 1s, 1/f2 = 2s, 1/f3 = 3s (where when 1/fHELLO = x a node sends a HELLO packet every x seconds). For each combination (M AC -Clustering -fHELLO), we removed entries in data base older than AGEMAX by using three values for AGEMAX: AGE1 = Contrarily to the ideal MAC layer, links may become uni-directional when using a realistic MAC layer. Since the clustering algorithms require bi-directional links, a node will not consider uni-directional link when computing its density.

Model Validation

To validate our NS2 code, we use a simple scenario depicted in Fig. 9. In this scenario the lines represent the wireless links between nodes. Table 3 gives the value computed by the nodes during the simulation. Results validate our model.

Simulations Results

This section presents the simulation results of our proposed implementation.

Neighbor discovery

As claimed earlier, the use of realistic MAC and physical layers greatly impacts the neighbor discovery. In this section, we run simulations in order to validate the theoretical analysis provided in Section 3.4.1. Fig. 10 plots the mean node degree, i.e. the mean number of bi-directional neighbors for R = 150m and different values of λ after one round of HELLO messages exchange. Results perfectly match.

The influence of the timeout for data refresh

We show how the time data are stored influences the clustering protocols. Fig. 11 and 12 plot the number of clusters for the two different clustering protocols as a function of the time with fHELLO = f1. Results are plot here for λ = 100 but the clustering behaviors are similar whatever the number of nodes. We only present results for fHELLO = f1. But, results for fHELLO = f2 and fHELLO = f3 present the same oscillations. The lower the frequency, the more the system oscillates, the longer it needs to stabilize, as we will show later in Section 4.3.3. Results plotted here are thus the better behavior we can expect.

One can notice that depending on how fresh the data considered are, the clustering algorithms converge toward different values, but never aims at the one obtained in the ideal case. This can be explained by the theoretical analysis of Section 3.4. Indeed, as shown by this analysis, the probability to detect every neighbor node in only one round is very low, indeed, when AGEMAX = AGE1, none node has an exact view of its neighborhood at any time. And, to compute the degree or the density value, nodes need not only their own neighborhood but also the neighborhood of their neighbors. This explains that, when AGEMAX is close to the frequency of HELLO packets, we observe a kind of oscillation in the number of clusters and algorithms have difficulty to self-stabilize. The neighborhood table and data used for computing the density/degree value computation changes frequently. We can see that this behavior appears for both MAC layer protocols. In fact, the delay introduced at the MAC layer modifies the status of each node. When assuming a perfect but not instantaneous transmission of messages, for example a TDMA scheduling where no collision occurs, every message transmission has the same delay and the jitter is equal to 0. This behavior does not appear here, transmissions are thus not perfect and some HELLO packets are lost. While considering a random access method, the jitter varies because of contention. In 802.11 and MadMac, this aspect is worsen by the random backoff algorithm used and this oscillation appears because there exists a high probability that a HELLO packet sent by node u is not received by all nodes in Γ(u) before the end of the AGEMAX period. Increasing the frequency of HELLO packet or increasing the AGEMAX of data validity is thus the solution to this problem. Indeed, this amounts to increasing the value of µv in the analysis.

Fig. 11 and 12 show that having AGEMAX equal to twice the fHELLO (thus p = 2 P from Section 3.4) is enough to avoid this oscillation problem, whatever the clustering protocol and whatever the network density. This confirms the theoretical results of Section 3.4. By increasing the AGEMAX period, the clustering protocol behavior tends toward the ideal case. Moreover, we can notice that the density-based algorithm oscillates less strongly than DDR. This shows that the density metric allows to smooths the small topology changes down and so, that the metric used in layer-3 protocols may be useful to overcome the imperfections of the lower layers. We can also notice that oscillations are stronger when using 802.11 when AGEMAX = AGE1 as a MAC layer rather than MadMac, whatever the clustering algorithm. This is due to the fact that MadMac is fairer than 802.11 and that in average it allows more nodes to access the channel. If at round 1, node u cannot send its HELLO message, it is more likely to send its HELLO packet at round 2 with MadMac than with 802.11.

The influence of HELLO frequency

In this section, we evaluate the influence of the HELLO frequency. For it, we evaluate the different scenarii for several values of fHELLO and by fixing AGEMAX . Fig. 13 and 14 show the evolution in time of the number of clusters depending for AGE3 and λ = 100. We can see that when the HELLO packet frequency decreases, the convergence time of the algorithm increases, which was expected since the more often data are sent, the faster each node updates its neighborhood table. We can see, as expected, that the time needed for the algorithm to converge is roughly proportional to the HELLO frequency. This behavior is the same whatever the MAC layer protocol and whatever the metric used for clustering. Because of page restriction, we only show here the behavior of the system for AGE3 and λ = 100 but results are the same for other AGEMAX values and other intensity values. These observations confirm the analytical results where the value of p impacts the network. Thus, for a fixed value of AGEMAX, the HELLO packet frequency only influences the convergence time.

CONCLUSION AND FUTURE WORKS

In this paper, we analyzed the impact of a realistic protocol stack over a self-organization depending of several parameters. We showed that the choice of the MAC layer impacts only in small measures the self-organization even if using MadMac instead of IEEE 802.11 as MAC layer protocol allows to discover nodes a little bit quicker. We also showed that using the density metric instead of the degree smooths local link failures down and gives more stability to the self-organization. The main disturbance comes from the setting of the neighbor discovery protocol. Indeed, we showed theoretically and by simulation that even in the best case, a node never discovers all its neighbors. We give a theoretical way to set the HELLO protocol parameters according to the discovery probability required. The packet frequency fHELLO and the time information is stored if not refreshed AGEMAX are linked and the parameter to set up is the ratio of both of them. These first results show that studying the HELLO protocol parameters is important when the informations in the HELLO packet are necessary for some other protocols. The next step of this work is to optimize the HELLO protocol for a specific (clustering, MAC) combination.

As future works, we intend to lead similar analysis when considering node mobility and the presence of traffic. We present some preliminary results on the simple topology given in Fig. 9. In this scenario, we try to include a saturated data traffic from node 1 to 0. The results of a 30s simulation is given in Table 4 with a frequency of HELLO packets equal to 1.s -1 and a valid data age of 3s.. Theoretical results are the same as in Table 3. It is worth noting that this does not mean that the clustering algorithm has converged correctly. At this point, nothing can be concluded except that when some traffic is present in the network the clustering algorithm can be strongly affect. More simulations and theoretical analysis are needed to conclude anything and to understand the network behavior in such cases. Indeed, introducing any kind of self-organization into a network aims at bringing more advantages to the network and just consists in a basis. If having some regular traffic totally disturbs the self-organization, we have to study in what measures the self-organization is useful to the network and does not harm it and what the limits of the self-organization are.

Figure 1 :

 1 Figure 1: Scenario 1

Figure 2 :Figure 3 :

 23 Figure 2: Probability for a node u to be detected by node 0 as a function of d = |u0|

Figure 4 :

 4 Figure 4: Comparison of the number of real neighbors and the number of the ones discovered by a node in NS2

Figure 5 :

 5 Figure 5: M/M/c/c queue

Figure 6 :

 6 Figure 6: c = 10

Figure 7 :

 7 Figure 7: c = 30

Figure 8 :

 8 Figure 8: Comparison between analysis and simulation for fHELLO = 1 and µv = 1/3

1 f HELLO , AGE2 = 2 f

 12 HELLO and AGE3 = 3 f HELLO .

Figure 9 :

 9 Figure 9: Validation scenario

Figure 10 :

 10 Figure 10: Mean node degree by theory and simulation as a function of λ for R = 150

Figure 11 :

 11 Figure 11: Number of clusters obtained for λ = 100 and fHELLO = f1 when using the density-based algorithm

Figure 12 :

 12 Figure 12: Number of clusters obtained for λ = 100 and fHELLO = f1 when using DDR

Figure 13 :

 13 Figure 13: Number of clusters, for λ = 100 and AGE3 when using the density-based algorithm

Figure 14 :

 14 Figure 14: Number of clusters, for λ = 100 and AGE3 when using the DDR algorithm

Table 1 : Format of a HELLO packet

 1

		What a node u learns from its neighbors	What it can then compute
	Round 1	uni-directional 1-neighbors	neighborhood table
	Round 2

Table 3 :

 3 Validation

		δ(u)	ρ(u)	H(u)	P(u)
	Node	Theo.	Simul.	Theo.	Simul.	Theo.	Simul.	Theo.	Simul.
	0	4	4	8/4	2.00	0	0	0	0
	1	3	3	5/3	1.66	0	0	0	0
	2	3	3	5/3	1.66	0	0	0	0
	3	3	3	5/3	1.66	0	0	0	0
	4	3	3	5/3	1.66	0	0	0	0

Table 4 : Node values

 4

			ρ(u)	H(u)	P(u)
	Node	802.11	MadMac	802.11	MadMac	802.11	MadMac
	0	1	2.00	0	0	1	0
	1	1.66	1.66	1	0	1	0
	2	1	1.66	0	0	0	0
	3	1.66	1.66	3	0	3	0
	4	1	1.66	0	0	1	0

http://www.ieee802.org/11/

In this section we only give a simplified definition of these protocols. Please refer to 802.11 standard and[START_REF] Razafindralambo | Increasing fairness and efficiency using the MadMac protocol in ad hoc networks[END_REF] for more details.

Identifiers are supposed unique within the network.

http://www.isi.edu/nsnam/ns/

In IEEE 802.11, broadcast packet are sent without RTS/CTS.


Marcel Hollenstein
email: marcel.hollenstein@pasteur.fr

David Naccache
email: david.naccache@ens.fr

Peter B Rønne
email: peter.roenne@uni.lu

A Ryan

Robert Weil
email: robert.weil@upmc.fr

Ofer Yifrach-Stav

Preservation Of DNA Privacy During The Large Scale Detection Of Covid-19

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

1 Introduction and motivation 1.1 Privacy issues related to The current COVID-19 (Coronavirus Disease 2019) pandemic is rapidly spreading, significantly impacting healthcare systems. The disease is caused by the novel corona virus, also called SARS-COV-2 [Gor20]. SARS-COV-2 is a positive-sense single-stranded RNA virus. Stay-at-home and social distancing orders enforced in many countries are supporting the control of the disease's spread, while causing turmoil in the economic balance and in social structures [BBD + 20]. Recently, we witness trends of resistance to abiding by lock-down policies, and particularly to obligatory mask-wearing in public [Pra20]. While in the United States some citizens claim that mandatory mask wearing is a violation of civil rights [And20], more than 70 countries have declared a "State of Emergency", increasing the governments' power. In some countries, such as Thailand [TNT20], Spain [KMG20] and Canada [Wil20] the state of emergency has been extended. In the attempt to control the virus' spread, mobile software applications (tracing apps) have been developed. These apps use digital tracking that monitor contact between individuals, so as to easily identify possible exposure to the virus. Some of these apps are based on tracking the geographical location of app users, thus raising privacy concerns.

The scientific debate concerning privacy of the COVID-19 tracing efforts has been intense, especially regarding the choice between centralised and decentralised tracing apps [Vau20], and it has had political implications, such as Germany changing to a decentralised approach [Sch20b]. Oddly, the privacy concerns regarding COVID-19 testing, however, .have not received as much attention even though the privacy at stake is arguably even higher, potentially compromising the privacy of one's DNA.

Testing for COVID-19 Infection

Rapid detection of cases and contacts is an essential component in controlling the pandemic's spread. In the US, the current estimation is that at least 500,000 COVID-19 tests will need to be performed daily to successfully reopen the economy [LVLM20].

There are currently two types of COVID-19 tests:

-Molecular diagnostic tests that detect the presence of SARS-COV-2 nucleic acids in human samples:

A sample is taken using a narrow swab that is placed in the patient's nose or mouth. It is generally recommended to collect upper respiratory samples (nasopharyngeal swabs, oropharyngeal swabs, nasopharyngeal washes, and nasal aspirates), but when the patient exhibits productive cough, lower respiratory samples (sputum, BAL fluid, and tracheal aspirates) are sometimes used [UKK + 20].

Polymerase chain reaction (PCR) is a process that causes a very small well-defined segment of DNA to be amplified, or multiplied many hundreds of thousands of times, so that there is enough of it to be detected and analyzed. Since the SARS-COV-2 virus does not contain DNA but only RNA, reverse transcription is used to convert the extracted RNA into DNA. The resulting DNA product is then subjected to a real-time PCR to determine whether sequences corresponding to the SARS-COV-2 RNA are present in the sample. The amplification of DNA is monitored in real time as the PCR reaction progresses using a fluorescent dye or a sequence-specific DNA probe labeled with a fluorescent molecule and a quencher molecule. The process is repeated for about 40 cycles until the viral cDNA can be detected [CGS + 20]. -Serological diagnostic tests that identify antibodies to SARS-COV-2 in clinical specimens [WKLT20].

The current standard test for COVID-19 detection, qPCR is quick, sensitive and reliable, but can only tell if a person is currently infected. Detecting antibodies to SARS-COV-2 can tell a clinician if a patient has been infected with COVID-19 either currently, or in the past, depending on the type of immunoglobulins detected (IgM, IgG or both), and if the patient is immunized and thus protected against a second infection. In addition, identifying populations who have antibodies can facilitate research on the use of convalescent plasma in the development of a cure for COVID-19 [FA20].

The DNA Privacy Problem

In both types of tests, the collected specimen contains the tested person's DNA. DNA is the molecule that carries the genetic instructions of all living organisms. Screening of vast populations for the presence of the virus, inevitably means providing the testing agencies (clinics, governments, airlines, etc.) with sensitive genetic information on a considerable number of individuals. Even if the sample contains a very small amount of DNA, PCR can be used to amplify the DNA and reveal the genome [KYK + 11]. A USB portable device, the MinION, developed by Zaaijer et al. [ZGS + 17] can accurately identify human cells ("DNA re-identification") by comparing an unknown DNA sample to a collection of known DNA profiles, with 99.9% confidence, within three minutes of DNA sequencing. DNA samples collected as part of COVID-19 tests are not supposed to be analyzed, and in any case, sensitive medical information is expected to be kept confidential. However, it is common practice to preserve medical samples to be used in further research or for prognosis monitoring.

Often times, tested individuals do not know how these samples will be used in the future. For example, in 2009, it was discovered that Texas had been collecting and storing blood and DNA samples taken from millions of newborns without the parents' knowledge or consent. These samples were used by the state for genetic experiments and for the set up of a database [Wal10].

DNA databases, or biobanks, are being maintained in many countries in the world [Wil18] and they are being used for forensic [KDK11] and research purposes. An analysis from 2012 indicates that there is no consensus on the the need for consent to use information in biobanks [MNMC12]. Despite the matter's sensitivity, the information can be accessed. In a research conducted in 2016, 95.7% of 46 biobanks surveyed by [CAD + 16] gave other researchers permission to access their samples. Despite laws and regulations intended to prohibit the re-identification of anonymized data, such as Privacy Rule from HIPAA (Health Insurance Portability and Accountability Act of 1996), the Common Rule from the DHHS (Department of Health and Human Services), and the Human Subject Protection Regulations and 21st Century Cures Act from the FDA [Lee00], there have been numerous incidents of data breaches (including database hacks and ransomware attacks) in healthcare systems [Pec17, Mon17, CBC16].

DNA samples stored in databases are usually coded so as to reduce their identifiability. However, it is not impossible to track down the individual "behind" the DNA. For example, Malin and [START_REF] Malin | Determining the identifiability of dna database entries[END_REF][START_REF] Malin | Re-identification of dna through an automated linkage process[END_REF] [MS00, MS01] demonstrated that even if kept confidential, and without being linked to identifying personal or demographic details, DNA information can be traced to the tested patients using inferences drawn from the DNA information.

The fact that stored DNA can be linked to the person is especially problematic given the possible use there could be for this information. Knowing a person's DNA provides information about racial features, potential diseases or life span expectancy. This information can attribute to genetic discrimination. For example, an employer may refuse to hire someone based on the likelihood that they will become ill. Similarly, exposing one's genetic information may impact their eligibility to life or health insurance, or to increase their premia [BC + 98]. In this sense, the potential transfer of sensitive genetic information to a third party raises significant ethical and legal issues [CT04]. Moreover, the collection of DNA into databases can "raise human rights concerns, including potential misuse of government surveillance (for example, identification of relatives and non-paternity) and the risk of miscarriages of justice" [Can16].

Beyond the discrimination against individuals based on their genetic profiles, human rights activists have been protesting against the mass collection of DNA samples from citizens by governments. In the past years, China has been collecting DNA samples from citizens as part of mandatory medical examinations [Fen17]. Human Rights Watch activists are worried about the use of this information for "surveillance of persons because of ethnicity, religion, opinion or other protected exercise of rights like free speech" [Haa17].

The gathering of DNA information by countries has raised concern regarding the way this information can be used to impact populations based on genetic characteristics. Moreover, this information may be deployed not only domestically, but internationally [Mos19a]. DNA information can be used to attack strategically identified persons, such as diplomats, politicians, high-ranking federal officials, or military leadership, or even to bio-engineer a disease that would be fatal to some races but not to others [Mos19b].

Refusal to undergo medical tests or procedures because of the fear of exposing genetic information to hostile entities may hinder medical and scientific attempts to treat diseases and learn about them for the sake of mankind. Recently, for example, it has been reported that Israel revoked a deal with a company selling COVID-19 testing equipment out of concern about granting the company access to Israelis' genetic information [Sch20a]. Especially now, when COVID-19 tests are prevalent and may become mandatory in different settings (e.g. at airports) [Cri20], the need to find a way to conduct these tests without compromising our genetic information's safety arises. The fact that test samples are often sent to be analyzed in another country, e.g. [BBC20], reinforces the need to form a testing method that ensures that the samples sent do not contain identifiable DNA traces.

The rest of the paper is organized as follows: in the next section, we describe a theoretical safety model inspired by the cryptographic notion of Indistinguishability under Chosen Plaintext Attack. In Section 3, we describe a testing scheme applying the theoretical safety model to create privacy preserving medical tests, and elaborate on different approaches that could be applied. Finally, Section 4 concludes the paper.

Suggested Solution -Theoretical Model

Before describing the solution, let us provide the intuition behind our idea.

We aim to develop a DNA privacy-preserving test, or in other words, a test method that would yield the same results, but that the DNA in the specimen tested, or in any residue of the specimen collected, will be undetectable. We hence wish to develop a test procedure T such that:

T (DNA V ) = {positive, res positive (DNA,V )} and T (DNA) = {negative, res negative (DNA)}
The positive and negative denote the virus' presence or absence, respectively (the test's result). denotes mixing substances6 . res denotes the test's residue, i.e. whatever is left after the test procedure has been completed. While some protocols may require this residue to be treated as bio-hazardous waste and be destroyed, residues are often preserved for future research or other purposes. Therefore, res is where unwanted DNA may be present, and is our main concern.

In COVID-19 tests, the sequence of operations is independent of the virus' presence. However, in other types of tests, the virus' presence may influence the sequence of operations done during the test, hence in all generality we distinguish two types of residues in our model. In any case, the residue will differ by the remains of the virus (or lack thereof). A 's advantage is defined as: In other words, 0 ≤ Adv ≤ 1. The higher the advantage, the more powerful A is. We define T as IND-C.DNA.A7 secure8 if Adv < 10 -3 .

Adv = 2| Pr[b = b ] - 1 2 | When A has
3 How to Build IND-C.DNA.A Tests?

We assume that the test procedure needs to be built in such a way that the tested person can trust that once the specimen is collected, the DNA will not be identifiable. Therefore, we suggest to add a testing procedure, step T 0 , which will be performed in the patient's presence. We suggest two approaches in which this step can be done: Mixing and Destroying.

DNA Mixtures

We suggest to use a testing kit containing a mixture m of DNA samples, thus making it more difficult to analyze, or profile.

The complexity of a DNA mixture is determined by the number of people who contributed DNA to the mixture, the amount of DNA that each of them contributed, and the level of DNA degradation. More contributors make a mixture more complex, and therefore, more difficult to interpret [Pre19]. DNA profiling requires the comparison of short segments of DNA, called alleles, which vary from person to person. As part of the DNA profiling process, the DNA is amplified and the alleles are represented on a graph showing peaks. The positions of those peaks indicate which alleles are present, and thus the graph is a visual representation of the DNA in question. The DNA profiling task is based on the comparison of the pattern of those peaks. Small amounts of DNA derived from various contributors add "noise", called drop-in, which makes the comparison process more complicated. The greater the number of contributors is, the more complicated the task of identifying which peaks go with which contributor. In addition, the PCR process during copying reaction by the DNA polymerase creates small peaks, called stutter products, which are sometimes the same lengths as PCR products. This can make the determination of whether a small peak is a real peak from a minor contributor or a stutter products.

We propose, therefore, to increase this complexity by adding a DNA mixture to the specimen collected. Any analysis performed will be done on the mixture, and not on the individual DNA sample, thus making it more difficult to profile the DNA.

There are four possible scenarios in attempting to identify the DNA in the mixture:

A The DNA of the victim x is known, and the composition of the mixture m is also known. The challenge is to determine if x is in the mixture m x or not. B The DNA of the victim x is known, but the composition of the mixture m is unknown. The challenge is to determine if x is in the mixture m x or not. C The DNA of the victim x is unknown, but the composition of the mixture m is known. The challenge is to isolate the DNA of the victim, x. D The DNA of the victim x is unknown, and the composition of the mixture m is also unknown. The challenge is to profile (separate) all the m + 1 DNAs in the mixture m x so as to learn the DNA of the victim x with probability 1 m +1 .

As is the case in cryptology, the above scenarii could be generalized and refined. For instance, one may consider a scenario where A is allowed to perform v (potentially adaptive) experiments with different mixtures m 0 , . . . , m v-1 and an identical target DNA x etc. Whilst interesting in theory, we did not consider such extensions very relevant to "real world" settings. Scenarios A and B represent a situation where the DNA of the individual is already known, and the challenge is to authenticate its presence in the mixture. Authentication methods are commonly used in the forensics field, where DNA found in a crime scene is compared to that of a suspect. For example, Homer et. al [HSR + 08] have demonstrated that it is possible to identify the presence of genomic DNA of specific individuals within a series of highly complex genomic mixtures, including mixtures where an individual contributes less than 0.1% of the total genomic DNA.

In this paper, we address the option of attempting to identify the DNA of the individuals in the mixture when they are unknown to the attacker (scenarii C and D ). Identification methods are intended to reveal the identity of one contributor in a mixture. Currently, these methods are achieved by comparing DNA samples to known profiles in a database. We propose solutions to prevent the possibility of identifying the genetic profile of an individual by an attacker.

Before we proceed, we would like to introduce a subtle distinction between the equality relationship (=) in mathematics and the chemical relationship consisting in comparing two molecular mixtures.

We denote by a = b an exact equality between the chemical components a and b. However, a b will denote the fact that a cannot be distinguished from b using current laboratory equipment with very high probability (e.g. 99%).

Dilution (scenario C ):

The idea behind this technique is to add the sample into a pre-prepared mixture containing other samples or other DNAs, thus making DNA less identifiable: mislead A by reducing his advantage, exploiting the difference between = and . The most plausible way to do so consists in adding to T , a fixed mixture of k (e.g. k = 20) human DNAs taken from existing DNA samples, or animal DNA. Adding the DNA sample to a fixed mixture of DNA would make the process of identification significantly more complicated. However, using a fixed mixture of DNA grants a few possible advantages to A . First, if the composition of the mixture is known to A , identification of the added sample would be a relatively simple task. Second, even without being familiar with the mixture's composition, the characteristics of the contributors need to be taken into consideration to avoid easy identification. For example, race factors can influence the ease with which a sample can be identified. Thus, using a fixed DNA mixture will make the distinguishing of the DNA of the victim x more complicated, but not impossible.

Randomizing (scenario D ): Another workaround, frequently used in cryptology, consists in adding randomness to T . The idea behind randomizing is using a random mixture of DNA into which the sample is added. By doing so, any fixed DNA defines the distributions of residues D positive,DNA = {res positive (DNA,V )} and D negative,DNA = {res negative (DNA)} obtained by testing this specific fixed DNA over and over again using T .

We design T in such a way that ∀ DNA, the following distributions are indistinguishable:

res positive (DNA,V ) ∼ res positive and res negative (DNA) ∼ res negative This mixture is not known to A , and even the number of contributors comprising the mixtures varies. This prevents A from learning through repeated experimentation. Randomizing makes the profiling task more complicated, because A will have no prior knowledge about the DNA characteristics. In DNA profiling, this is referred to as lack of Framework of Circumstances, [FSR18], which is one of the factors that hinder DNA profiling.

The model here assumes that when m is manufactured, each individual test kit is randomized (e.g. by the addition of a different random assortment of DNA material) so that different tests of the same patient will yield residues that do not leak information about the patient's DNA.

Current profiling methods in use in forensics allow analyzing a mixture of DNA and determining the number of DNA samples mixed into the mixture. However, separating an individual DNA from a mixture of an unknown number of contributors of unknown DNA profiles is a much more complicated task. In order to profile complex DNA mixtures, a software is used for computing the probability distribution for the number of contributors [TBB14]. If the number of contributors is unknown, the computational load will be considerably higher. Therefore, the Randomizing method could be applied to mask DNA and achieve our goal.

Another way of masking the DNA in question by adding randomization to the solution is to add an allelic ladder directly to the sample solution. An allelic ladder is an artificial mixture of the common alleles present in the human population, and it is commonly used to identify alleles in genetic profiles by comparison with peaks.

Destruction (all scenarii):

Another way to ensure that an attacker cannot access the DNA is to destroy it, thus making it unidentifiable. We start by observing that IND-C.DNA.A cannot exist if ∃DNA 0 , DNA 1 such that: res positive (DNA 0 ,V ) res positive (DNA 1 ,V ) or res negative (DNA 0 ) res negative (DNA 1 ) Simply because A can run the test by himself and compare the resulting residue to the challenger's residue, it follows that T 0 must destroy human DNA while allowing subsequent testing of V .

To ensure that no DNA traces remain in the sample we suggest to destroy the DNA, leaving the RNA intact for the test. We propose, therefore, a model in which all human DNA is destroyed before the rt-PCR amplification. This can be done by treating the samples with DNase, an enzyme that selectively degrades DNA [ST14]. DNase eliminates DNA from RNA preparations prior to sensitive applications, such as rt-PCR. Within 10 to 20 minutes [HFK96, Bio20] there will be no identifiable DNA. To ensure that viral RNA remains intact, the DNase then needs to be inactivated by inclusion of removal reagents [Amb] or by using heat inactivation [WRSS00].

Following this process, we suggest a verification of the DNase's effectiveness. This verification process can be done by inducing reaction causing a colour change which could be visible by the patient. One way of doing so could be by applying gold nano-particles (AuNPs) interconnected by DNA duplexes. Without DNase activity, the AuNPs tend to cluster, displaying a blue colour. When DNase is present, it cleaves these duplexes, causing them to spread, which leads to a colour change from blue to red [HCPT17, BPE + 08, XHM07]. Another method that could be applied is using a fluorophore-quencher system [SZZ + 13]. In the absence of DNase, the fluorophore is in close proximity of the quencher and hence no fluorescence is visible. In the presence of DNase, DNA is hydrolyzed and the fluorophore is free to circulate in the solution, creating a fluroscentic reaction which can be easily monitored and detected as an output signal. The patient can witness the change in colour and be convinced that all DNA has been removed. Once this step is complete, the patient is free to go, and the sample is ready for testing.

Before we conclude, we have to consider the case of mutually distrusting parties. In this scenario, the tester wants to ensure that the test provides accurate information (i.e. that the virus will be detected, if present), while the patient may not trust the tester or the test kit. Theoretically speaking, we could have the patients provide their own DNase. Putting aside the practical logistic difficulties and unlikelihood of this solution, this solution poses a risk of a patient intentionally using a chemical killing both DNA and virus (for example, in a scenario of being virus-free as a condition to board a flight or enter a country). On the other hand, if the DNase is provided by the testing agency, the patient may suspect that another chemical is used that simply emulates the colour change. To solve this dilemma, we can have the patient be sampled twice using a classical "cut-&-choose" approach. To both samples the DNase and supplementary chemicals are added. The tested person then chooses one of the samples randomly, and adds his own chemical to verify the presence of DNase. The other sample is then used for testing. This allows the tested person to detect a maliciously generated test kit with probability 1 2 , and of course these odds can be improved, but at the cost of multiplying the number of samples used.

To ensure the integrity of the process, a positive process control method could be integrated. This could be done, for example, by identifying, at the end of the process, a specific reagent or a a known human target which will be deposited at the beginning of the analytical process. The presence of the target at the end of the process will allow concluding that a negative result obtained is stemming from absence of the virus, and not from a malfunction in the the reaction or process.

Note that we could also audit test kits in general, but this relies on trusted third parties, or a public procedure.

Discussion

This paper described a methodology in which biological specimens containing DNA taken from patients can be processed while securing the safety and confidentiality of the DNA information contained in the specimen. Our model relieves the patient of the expectation to trust the testing entity. While the medical system is still based on the patients' confidence and trust in the clinician, in the past years there has been a shift towards more informed patients expecting to have more involvement and control over processes and decision-making [RC06].

Mass COVID-19 testing performed all over the world nowadays highlights the needs for more secure types of tests. The model proposed in this paper can be applied not only for COVID-19 , but for other types of tests where DNA is extracted but not necessary to obtain test results. As DNA is present in any specimen collected from the human body, every lab test has the potential of exposing one's sensitive genetic information. The idea described in this paper will need to be adapted so as to provide protection to other types of tests.

While public awareness regarding the need to protect genetic information grows, the ability to perform successful profiling using smaller amounts of DNA increases. The recent developments in the field of DNA profiling now allows to analyze even minute amounts of DNA, called trace DNA or touch DNA. Small amounts of DNA can be found on any surface; people shed DNA on any object or surface they touch. In this sense, one may claim that protecting DNA information is impossible. However, it is important to note the difference between analyzing trace amounts of DNA, and analyzing the content of a test tube containing body fluids or mucosa. Let us consider a hypothetical case in which an attacker is interested in the DNA of a specific person. An attacker could try to retrieve trace DNA from objects touched by that person, a cup the person drank from etc., but the amount of DNA retrieved would be much smaller, and the process of analyzing this DNA would be significantly more difficult. In addition, it is important to note that since, in the case of medical tests, the specimen is sent for analysis in a lab, the likelihood of the DNA to be profiled increases, thus increasing the risk.

At this stage, we only offer a theoretical blueprint. Future work will include laboratory experiments demonstrating that the validity of the test is not negatively impacted by the added security phase T 0 (i.e. DNA mixture or DNA destruction).

  The attacker's definition (A ) is inspired by the cryptographic notion of Indistinguishability under chosen-plaintext attack (IND-CPA): A selects two DNA samples DNA 0 and DNA 1 and submits them to a challenger C . C picks a random b ∈ {0, 1} and manufactures the samples: σ b,positive = DNA b V and σ b,negative = DNA b C runs T on σ b,positive , σ b,negative and gets: T (σ b,positive ) = {positive, res positive } and T (σ b,negative ) = {negative, res negative } A gets {positive, res positive }, {negative, res negative }, performs any state of the art analyses and outputs a guess b .

  no advantage in learning DNA information, his only strategy is to guess b at random. In that case, Pr[b = b] = 1 2 and hence Adv = 0. When A always correctly determines b , we have Pr[b = b] = 1, i.e. Adv = 1. Note that when A is always wrong, we have Pr[b = b] = 0 and hence Adv = 1. Such an A is effectively as powerful as an A who always finds the correct answer as it suffices to negate his response to get a perfect adversary.

Figure 1 .

 1 Figure 1. Testing following DNA destruction: 1 Sample is taken from the patient using swab ⇒ 2 DNase is applied to the sample, destroying DNA ⇒ 3 A colourimetric method is applied ⇒ 4 This demonstrates that no DNA traces are present (Blue indicates DNA traces, red means that DNA was properly destroyed) ⇒ 5 The patient is now convinced that the sample can be analyzed without risk of exposing his DNA.

Table 1 .

 1 Attack and protection scenarii.

	scenario victim DNA x hiding mixture m attacker's goal
	A	known	known	confirm x
	B	known	unknown	confirm x
	C	unknown	known	learn x
	D	unknown	unknown	learn 9 x

e.g. water CO 2 = soda

Indistinguishable under Chosen DNA Attack.

The limit can be changed according to the test's acceptable level.

with probability 1 m +1 .

Acknowledgements

This work was supported by the Luxembourg National Research Fund (FNR) project SmartExit (14729565). The authors thank Thibaut Heckmann, Head of Data Extraction Unit, and Audrey Gouello, DNA Expert, of the IRCGN (Institut de recherche criminelle de la gendarmerie nationale) for their enriching remarks.