Quentin Bramas

Sayaka Kamei

Anissa Lamani

Sébastien Tixeuil

Stand-Up Indulgent Gathering on Lines

Keywords: Crash failure, fault-tolerance, LCM robot model

We consider a variant of the crash-fault gathering problem called stand-up indulgent gathering (SUIG). In this problem, a group of mobile robots must eventually gather at a single location, which is not known in advance. If no robots crash, they must all meet at the same location. However, if one or more robots crash at a single location, all non-crashed robots must eventually gather at that location. The SUIG problem was first introduced for robots operating in a two-dimensional continuous Euclidean space, with most solutions relying on the ability of robots to move a prescribed (real) distance at each time instant. In this paper, we investigate the SUIG problem for robots operating in a discrete universe (i.e., a graph) where they can only move one unit of distance (i.e., to an adjacent node) at each time instant. Specifically, we focus on line-shaped networks and characterize the solvability of the SUIG problem for oblivious robots without multiplicity detection.

Introduction

Context and Motivation

Mobile robotic swarms recently received a considerable amount of attention from the Distributed Computing scientific community. Characterizing the exact hypotheses that enable solving basic problems for robots represented as disoriented (each robot has its own coordinate system) oblivious (robots cannot remember past action) dimensionless points evolving in a Euclidean space has been at the core of the researchers' goals for more than two decades. One of the key such hypotheses is the scheduling assumption [START_REF]Distributed Computing by Mobile Entities, Current Researchin Moving and Computing[END_REF]: robots can execute their protocol fully synchronized (FSYNC), in a completely asynchronous manner (ASYNC), of having repeatedly a fairly chosen subset of robots scheduled for synchronous execution (SSYNC).

Among the many studied problems, the gathering [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF] plays a benchmarking role, as its simplicity to express (robots have to gather in finite time at the exact same location, not known beforehand) somewhat contradicts its computational tractability (two robots evolving assuming SSYNC scheduling cannot gather, without additional hypotheses).

As the number of robots grows, the probability that at least one of them fails increases, yet, relatively few works consider the possibility of robot failures. One of the simplest such failures is the crash fault, where a robot unpredictably stops executing its protocol. In the case of gathering, one should prescribe the expected behavior in the presence of crash failures. Two variants have been studied: weak gathering expects all correct (that is, non-crashed) robots to gather, regardless of the positions of the crashed robots, while strong gathering (also known as stand-up indulgent gathering -SUIG) expects correct robots to gather at the (supposedly unique) crash location. In continuous Euclidean space, weak gathering is solvable in the SSYNC model [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF][START_REF] Bouzid | Gathering of mobile robots tolerating multiple crash faults[END_REF][START_REF] Bramas | Wait-free gathering without chirality[END_REF][START_REF] Défago | Self-stabilizing gathering of mobile robots under crash or byzantine faults[END_REF], while SUIG (and its variant with two robots, stand up indulgent rendezvous -SUIR) is only solvable in the FSYNC model [START_REF] Bramas | Stabilization, Safety, and Security of Distributed Systems[END_REF][START_REF] Bramas | Stand Up Indulgent Gathering[END_REF].

A recent trend [START_REF]Distributed Computing by Mobile Entities, Current Researchin Moving and Computing[END_REF] has been to move from the continuous environment setting to a discrete one. More precisely, in the discrete setting, robots can occupy a finite number of locations, and move from one location to another if they are neighboring. This neighborhood relation is conveniently represented by a graph whose nodes are locations, leading to the "robots on graphs" denomination. This discrete setting is better suited for describing constrained physical environments, or environments where robot positioning is only available from discrete sensors [START_REF] Balabonski | Continuous vs. discrete asynchronous moves: A certified approach for mobile robots[END_REF]. From a computational perspective, the continuous setting and the discrete setting are unrelated: on the one hand, the number of possible configurations (that, the number of robot positions) is much more constrained in the discrete setting than in the continuous setting (only a finite number of configurations exists in the discrete setting), on the other hand, the continuous setting offers algorithms designers more flexibility to solve problematic configurations (e.g., using arbitrarily small movements to break a symmetry).

In this paper, we consider the discrete setting, and aim to characterize the solvability of the SUIR and SUIG problems: in a set of locations whose neighborhood relation is represented by a line-shaped graph, robots have to gather at one single location, not known beforehand; furthermore, if one or more robots crash anytime at the same location, all robots must gather at this location.

Related Works

In graphs, in the absence of faults, mobile robot gathering was primarily considered for ring-shaped graphs [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF][START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF][START_REF] Kamei | Gathering an even number of robots in an odd ring without global multiplicity detection[END_REF][START_REF] Izumi | Time-optimal gathering algorithm of mobile robots with local weak multiplicity detection in rings[END_REF][START_REF] D'angelo | AlfredoNavarra: Gathering on rings under the look-compute-move model[END_REF][START_REF] D'angelo | A unified approach for gathering and exclusive searching on rings under weak assumptions[END_REF]. For other topologies, gathering problem was considered, e.g., in finite grids [START_REF] D'angelo | Gathering of robots on anonymous grids and trees without multiplicity detection[END_REF], trees [START_REF] D'angelo | Gathering of robots on anonymous grids and trees without multiplicity detection[END_REF], tori [START_REF] Kamei | Asynchronous Gathering in a Torus[END_REF], complete cliques [START_REF] Cicerone | Gathering robots in graphs: The central role of synchronicity[END_REF], and complete bipartite graphs [START_REF] Cicerone | Gathering robots in graphs: The central role of synchronicity[END_REF]. Most related to our problem is the (relaxed) FSYNC gathering algorithm presented by Castenow et al. [START_REF] Castenow | Gathering anonymous, oblivious robots on a grid[END_REF] for grid-shaped networks where a single robot may be stationary. The main differences with our settings are as follows. First, if no robot is stationary, their [START_REF] Castenow | Gathering anonymous, oblivious robots on a grid[END_REF] robots end up in a square of 2 × 2 rather than a single node as we require. Second, when one robot is stationary (and thus never moves), all other robots gather at the stationary robot location, assuming a stationary robot can be detected as such when on the same node (instead, we consider that a crashed robot cannot be detected), and assuming a stationary robot never moves from the beginning of the execution (while we consider anytime crashes). Third, they assume that initial positions are neighboring (while we characterize which patterns of initial positions are solvable).

In the continuous setting, the possibility of a robot failure was previously considered. As previously stated, the weak-gathering problem in SSYNC [START_REF] Agmon | Fault-tolerant gathering algorithms for autonomous mobile robots[END_REF][START_REF] Bouzid | Gathering of mobile robots tolerating multiple crash faults[END_REF][START_REF] Bramas | Wait-free gathering without chirality[END_REF][START_REF] Défago | Self-stabilizing gathering of mobile robots under crash or byzantine faults[END_REF], and the SUIR and SUIG problems in FSYNC [START_REF] Bramas | Stabilization, Safety, and Security of Distributed Systems[END_REF][START_REF] Bramas | Stand Up Indulgent Gathering[END_REF] were previously considered. In particular, solutions to SUIR and SUIG [START_REF] Bramas | Stabilization, Safety, and Security of Distributed Systems[END_REF][START_REF] Bramas | Stand Up Indulgent Gathering[END_REF] make use of a level-slicing technique, that mandates them to move by a fraction of the distance to another robot. Obviously, such a technique cannot be translated to the discrete model, where robots always move by exactly one edge.

Works combining the discrete setting and the possibility of robot failures are scarce. Ooshita and Tixeuil [START_REF] Ooshita | On the self-stabilization of mobile oblivious robots in uniform rings[END_REF] considered transient robot faults placing them at arbitrary locations, and presented a probabilistic self-stabilizing gathering algorithm in rings, assuming SSYNC, and that robots are able to exactly count how many of them occupy a particular location. Castaneda et al. [START_REF] Castaneda | Fault-tolerant robot gathering problems on graphs with arbitrary appearing times[END_REF] presented a weaker version of gathering, named edge-gathering. They provided a solution to edge-gathering in acyclic graphs, assuming that any number of robots may crash. On the one hand, their scheduling model is the most general (ASYNC); on the other hand, their robot model makes use of persistent memory (robots can remember some of their past actions, and communicate explicitly with other robots).

Overall, to our knowledge, the SUIR and SUIG problems were never addressed in the discrete setting.

Our Contribution

In this paper, we initiate the research on SUIG and SUIR feasibility for robots on lineshaped graphs, considering the vanilla model (called OBLOT [START_REF]Distributed Computing by Mobile Entities, Current Researchin Moving and Computing[END_REF]) where robots are oblivious (that is, they don't have access to persistent memory between activations), are not able to distinguish multiple occupations of a given location, and can be completely disoriented (no common direction). More precisely, we focus on both of finite/infinite lines, and study conditions that preclude or enable SUIG and SUIR solvability. As in the continuous model, we first prove that SUIG and SUIR are impossible to solve in the SSYNC model, so we concentrate on the FSYNC model. It turns out that, in FSYNC, SUIR is solvable if and only if the initial distance between the two robots is even, and that SUIG is solvable if only if the initial configuration is not edge-symmetric. Our positive results are constructive, as we provide an algorithm for each case and prove it correct. As expected, the key enabling algorithmic constructions we use for our protocols are fundamentally different from those used in continuous spaces [START_REF] Bramas | Stabilization, Safety, and Security of Distributed Systems[END_REF][START_REF] Bramas | Stand Up Indulgent Gathering[END_REF], as robots can no longer use fractional moves to solve the problem, and can be of independent interest to build further solutions in other topologies.

The rest of the paper is organized as follows. Section 2 presents our model assumptions, Section 3 is dedicated to SUIR, and Section 4 is dedicated to SUIG. We provide concluding remarks in Section 5. Due to space constraints, additional proofs and results are presented in the appendix.

Model

The line consists of an infinite or finite number of nodes u 0 , u 1 , u 2 , . . . , such that a node u i is connected to both u (i-1) and u (i+1) (if they exist). Note that in the case where the line is finite of size n, two nodes of the line, u 0 and u n-1 are only connected to u 1 and u n-2 , respectively.

Let R = {r 1 , r 2 , . . . , r k } be the set of k ≥ 2 autonomous robots. Robots are assumed to be anonymous (i.e., they are indistinguishable), uniform (i.e., they all execute the same program, and use no localized parameter such as a particular orientation), oblivious (i.e., they cannot remember their past actions), and disoriented (i.e., they cannot distinguish left and right). We assume that robots do not know the number of robots k. In addition, they are unable to communicate directly, however, they have the ability to sense the environment including the positions of all other robots, i.e., they have infinite view. Based on the snapshot resulting of the sensing, they decide whether to move or to stay idle. Each robot r executes cycles infinitely many times, (i) first, r takes a snapshot of the environment to see the positions of the other robots (LOOK phase), (ii) according to the snapshot, r decides whether it should move and where (COMPUTE phase), and (iii) if r decides to move, it moves to one of its neighbor nodes depending on the choice made in COMPUTE phase (MOVE phase). We call such cycles LCM (LOOK-COMPUTE-MOVE) cycles. We consider the FSYNC model in which at each time instant t, called round, each robot r executes an LCM cycle synchronously with all the other robots, and the SSYNC model where a non-empty subset of robots chosen by an adversarial scheduler executes an LCM cycle synchronously, at each t.

A node is considered occupied if it contains at least one robot; otherwise, it is empty. If a node u contains more than one robot, it is said to have a tower or multiplicity. The ability to detect towers is called multiplicity detection, which can be either global (any robot can sense a tower on any node) or local (a robot can only sense a tower if it is part of it). If robots can determine the number of robots in a sensed tower, they are said to have strong multiplicity detection. In this work, we assume that robots do not have multiplicity detection and cannot distinguish between nodes with one robot and those with multiple robots.

As robots move and occupy nodes, their positions form the system's configuration C t = (d(u 0 ), d(u 1 ), . . . ) at time t. Here, d(u i ) = 0 if node u i is empty and d(u i ) = 1 if it is occupied.

Given two nodes u i and u j , a segment [u i , u j ] represents the set of nodes between u i and u j , inclusive. No assumptions are made about the state of the nodes in [u i , u j ]. Any node u ∈ [u i , u j ] can be either empty or occupied. The number of occupied nodes in [u i , u j ] is represented by |[u i , u j ]|. In Fig. 1, each node u i , where i ∈ {2, 3, . . . , 9}, is part of the segment [u 2 , u 9 ]. Note that |[u 2 , u 9 ]| = 3 since nodes u 2 , u 5 , and u 9 are occupied.

For a given configuration C, let u i be an occupied node. Node u j is considered an occupied neighboring node of u i in C if it is occupied and if |[u i , u j ]| = 2. A border node in C is an occupied node with only one occupied neighboring node. A robot on a border node is referred to as a border robot. In Fig. 1, when k = 4, nodes u 0 and u 9 are border nodes.

The distance between two nodes u i and u j is the number of edges between them. The distance between two robots r i and r j is the distance between the two nodes occupied by r i and r j , respectively. We denote the distance between u i and u j (resp. r i and r j ) dist(u i , u j ) (resp. dist(r i , r j )). Two robots or two nodes are neighbors (or adjacent) if the distance between them is one. A sequence of consecutive occupied nodes is a block. Similarly, a sequence of consecutive empty nodes is a hole.

An algorithm A is a function mapping the snapshot (obtained during the LOOK phase) to a neighbor node destination to move to (during the MOVE phase). An execution E = (C 0 , C 1 , . . . ) of A is a sequence of configurations, where C 0 is an initial configuration, and every configuration C t+1 is obtained from C t by applying A.

Let r be a robot located on node u i at time t and let

S + (t) = d(u i ), d(u i+1 ), . . . , d(u i+m ) and S -(t) = d(u i ), d(u i-1 ), . . . d(u i-m ′ ) be two sequences such that m, m ′ ∈ N.
Note that m = n -i -1 and m ′ = i in the case where the line is finite of size n, m = m ′ = ∞ in the case where the line is infinite. The view of robot r at time t, denoted V iew r (t), is defined as the pair {S + (t), S -(t)} ordered in the lexicographic order.

Let C be a configuration at time t. Configuration C is said to be symmetric at time t if there exist two robots r and r ′ such that V iew r (t) = V iew r ′ (t). In this case, r and r ′ are said to be symmetric robots. Let C be a symmetric configuration at time t then, C is said to be node-symmetric if the distance between two symmetric robots is even (i.e., if the axis of symmetry intersects with the line on a node), otherwise, C is said to be edge-symmetric. Finally, a non-symmetric configuration is called a rigid configuration.

Problem definition. A robot is said to be crashed at time t if it is not activated at any time t ′ ≥ t. That is, a crashed robot stops execution and remains at the same position indefinitely. We assume that robots cannot identify a crashed robot in their snapshots (i.e., they are able to see the crashed robots but remain unaware of their crashed status). A crash, if any, can occur at any round of the execution. Furthermore, if more than one crash occurs, all crashes occur at the same location. In our model, since robots do not have multiplicity detection capability, a location with a single crashed robot and with multiple crashed robots are indistinguishable, and are thus equivalent. In the sequel, for simplicity, we consider at most one crashed robot.

We consider the Stand Up Indulgent Gathering (SUIG) problem defined in [START_REF] Bramas | Stand Up Indulgent Gathering[END_REF]. An algorithm solves the SUIG problem if, for any initial configuration C 0 (that may contain multiplicities), and for any execution E = (C 0 , C 1 , . . . ), there exists a round t such that all robots (including the crashed robot, if any) gather at a single node, not known beforehand, for all t ′ ≥ t. The special case with k = 2 is called the Stand Up Indulgent Rendezvous (SUIR) problem.

Stand Up Indulgent Rendezvous

We address in this section the case in which k = 2, that is, the SUIR problem. We show that SSYNC solutions do not exist when one seeks a deterministic solution (Corollary 1), and that even in FSYNC, not all initial configurations admit a solution (Theorem 1). By contrast, all other initial configurations admit a deterministic SUIR solution (Theorem 2).

Theorem 1. Starting from a configuration where the two robots are at odd distance from each other on a line-shaped graph, the SUIR problem is unsolvable in FSYNC by deterministic oblivious robots without additional hypotheses.

Proof. Let us first observe that in any configuration, both robots must move. Indeed, if no robot moves, then no robot will ever move, and SUIR is never achieved. If one robot only moves, then the adversary can crash this robot, and the two robots never move, hence SUIR is never achieved.

In any configuration, two robots can either: (i) move both in the same direction, (ii) move both toward each other, or (iii) move both in the opposite direction. Assuming an FSYNC scheduling and no crash by any robot, in the case of (i), the distance between the two robots does not change, in the case of (ii), the distance decreases by two, and in the case of (iii), it increases by two. Since the distance between the two robots is initially odd, then any FSYNC execution of a protocol step keeps the distance between robots odd. As a result, the distance never equals zero, and the robots never gather. □ Corollary 1. The SUIR problem is unsolvable on a line in SSYNC without additional hypotheses.

Proof. For the purpose of contradiction, suppose that there exists a SUIR algorithm A in SSYNC. Consider an SSYNC schedule starting from a configuration where exactly one robot is activated in each round. Since any robot advances by exactly one edge per round, and that A solves SUIR, every such execution reaches a configuration where the two robots are at distance 2i+1, where i is an integer, that is, a configuration where robots are at odd distance from one another. From this configuration onward, the schedule becomes synchronous (as a synchronous schedule is still allowed in SSYNC). By Theorem 1, rendezvous is not achieved, a contradiction. □

By Theorem 1, we investigate the case of initial configurations where the distance between the two robots is even. It turns out that, in this case, the SUIR problem can be solved.

Theorem 2. Starting from a configuration where the two robots are at even distance from each other, the SUIR problem is solvable in FSYNC by deterministic oblivious robots without additional hypotheses.

Proof. Our proof is constructive. Consider the simple algorithm "go to the other robot position."

When no robot crashes, at each FSYNC round, the distance between the two robots decreases by two. Since it is initially even, it eventually reaches zero, and the robots stop moving (the other robot is on the same location), hence rendezvous is achieved.

If one robot crashes, in the following FSYNC rounds, the distance between the two robots decreases by one, until it reaches zero. Then, the correct robot stops moving (the crashed robot is on the same location), hence rendezvous is achieved. □

Observe that both Theorems 1 and 2 are valid regardless of the finiteness of the line network.

Stand Up Indulgent Gathering

We address the SUIG problem (k ≥ 2) on line-shaped networks in the following. Section 4.1 first derives some impossibility results, and then Section 4.2 presents our algorithm; finally, the proof of our algorithm appears in Section 4.3.

Impossibility Results

Theorem 3 ([20]). The gathering problem is unsolvable in FSYNC on line networks starting from an edge-symmetric configuration even with strong multiplicity detection.

Corollary 2. The SUIG problem is unsolvable in FSYNC on line networks starting from an edge-symmetric configuration even with strong multiplicity detection.

Proof. Consider a FSYNC execution without crashes, and apply Theorem 3. □

As a result of Corollary 2, we suppose in the remaining of the section that initial configurations are not edge-symmetric.

Lemma 1. Even starting from a configuration that is not edge-symmetric, the SUIG problem is unsolvable in SSYNC without additional hypotheses.

Proof. The proof is by induction on the number X of occupied nodes. Suppose for the purpose of contradiction that there exists such an algorithm A.

If X = 2, and if the distance between the two occupied nodes is 1, consider an FSYNC schedule. All robots have the same view, so either all robots stay on their locations (and the configuration remains the same), or all robots go to the other location (and the configuration remains with X = 2 and a distance of 1 between the two locations). As this repeats forever, in both cases, the SUIG is not achieved, a contradiction. If X = 2, and if the distance between the two occupied nodes is at least 2, consider a schedule that either (i) executes all robots on the first location, or (ii) executes all robots at the second location, at every round. So, the system behaves (as robots do not use additional hypotheses such as multiplicity detection) as two robots, initially on distinct locations separated by distance at least 2. As a result, the distance between the two occupied nodes eventually becomes odd. Then, consider an FSYNC schedule, and by Theorem 1, A cannot be a solution, a contradiction.

Suppose now that for some integer X, the lemma holds. Let us show that it also holds for X + 1. Consider an execution starting from a configuration with X + 1 occupied nodes. Since A is a SUIG solution, any execution of A eventually creates at least one multiplicity point by having a robot r 1 on one occupied node moved to an adjacent occupied node. Consider the configuration C b that is immediately before the creation of the multiplicity point. Then, in C b , all robots at the location of r 1 make a move (this is possible in SSYNC), so the resulting configuration has X occupied nodes. By the induction hypothesis, algorithm A cannot solve SUIG from this point, a contradiction.

So, for all possible initial configurations, algorithm A cannot solve SUIG, a contradiction. □ As a result of Lemma 1, we suppose in the sequel that the scheduling is FSYNC.

Algorithm A L

In the following, we propose an algorithm A L in FSYNC such that the initial configuration is not edge-symmetric. Before describing our strategy, we first provide some definitions that will be used throughout this section. In given configuration C, let d C be the largest even distance between any pair of occupied nodes and let U C be the set of occupied nodes at distance d C from another occupied node. If C is node-symmetric, U C consists only of the two border nodes (|U C | = 2). Then, let u and u ′ be nodes in U C . By contrast, if C is rigid, then |U C | ≥ 2 (refer to Lemma 2). Since each robot has a unique view in a rigid configuration, let u ∈ U C be the node that hosts the robots with the largest view among those on a node of U C and let u ′ be the occupied node at distance d C from u. Observe that if there are two candidate nodes for u ′ , using the view of the robots again, we can uniquely elect one of the two which are at distance d C from u (by taking the one with the largest view). That is, u and u ′ can be identified uniquely in C. We refer to [u, u ′ ] by the target segment in C, and denote the number of occupied nodes in

[u, u ′ ] by |[u, u ′ ]|. Finally, the set of occupied nodes which are not in [u, u ′ ] is denoted by O [u,u ′ ]
. Refer to Fig. 2 for an example.

We first observe that in any configuration C in which there are at least three occupied nodes, there exist at least two occupied nodes at an even distance.

Lemma 2. In any configuration C where there are at least three occupied nodes, there exists at least one pair of robots at an even distance from each other.

Proof. Assume by contradiction that the lemma does not hold and let u 1 , u 2 , and u 3 be three distinct occupied nodes such that u 2 is located between u 1 and u 3 . Assume w.l.o.g. that d 1 = dist(u 1 , u 2 ) and d 2 = dist(u 2 , u 3 ). By the assumption, both d 1 and d 2 are odd. That is, there exist q, q ′ ∈ N,

d 1 = 2q + 1 and d 2 = 2q ′ + 1. Hence, d 1 + d 2 is even since d 1 + d 2 = 2(q + q ′ + 1). A contradiction. □
We propose, in the following, an algorithm named A L that solves the SUIG problem on line-shaped networks. The main idea of the proposed strategy is to squeeze the robots by reducing the distance between the two border robots such that they eventually meet on a single node. To guarantee this meeting, robots aim to reach a configuration in which the border robots are at an even distance. Note that an edge-symmetric configuration can be reached during this process. However, in this case, we guarantee that not only one robot has crashed but also, eventually, when there are only two occupied adjacent nodes, the crashed robot is alone on its node ensuring the gathering. Let C be the current configuration. In the following, we describe robots' behavior depending on C: is closer to u than to u ′ . We address only the case in which dist(u, u v ) is odd. (Note that if dist(u, u v ) is even, the border nodes are at an even distance and |O [u,u ′ ] | = 0.) -If the number of occupied nodes is three and u v and u are two adjacent nodes, robots on both u and u ′ are the ones to move. Their destination is their adjacent node toward u v (refer to Fig. 4). -Otherwise, all robots are ordered to move. More precisely, robots on a node of [u, u ′ ] move to an adjacent node toward u v while the robots on u v move to an adjacent node toward u (refer to Fig. 5). (c) |O [u,u ′ ] | > 1. In this case, the robots that are in O [u,u ′ ] move toward a node of [u, u ′ ] (refer to Fig. 6).

Proof of the Correctness

We prove in the following the correctness of A L . Proof. Assume by contradiction that the theorem does not hold. Let C t be the current configuration. The following two cases are possible:

1. D is even. Let u 1 , u 2 , . . . , u m be the sequence of nodes between the two border robots such that u 1 and u m host a border robot. Note that the target segment is, in this case, [u 1 , u m ] and |O [u 1 ,um] | = 0. By A L , robots on u 1 and u m are the ones to move toward respectively u 2 and u m-1 . By moving, the distance between the border robots decreases by two and hence remains even. By A L , robots on u 2 and u m-1 are now the new borders and are the ones to move to, respectively, u 3 and u m-2 . As previously, the distance between the border robots decreases by two. By repeating the same process, after ⌊ D-1 2 ⌋ rounds, the border robots become at distance two from each other on respectively nodes uD 2 and u m-( D 2 +1) . After one additional round, all robots meet on u ( D 2 )+1 . Hence, the robots gather after D 2 rounds. A contradiction. 2. D is odd. By Lemma 2, we know that there is at least one pair of robots which are at an even distance from each other. Moreover, C t is not symmetric as we retrieve case 1 otherwise. Let u and u ′ be the two occupied nodes with respect to A L such that [u, u ′ ] is the target segment. Assume w.l.o.g. that v, the border robot in

O [u,u ′ ] , is closer to u. Let D ′ = dist(v, u). Two cases are possible: (a) |O [u,u ′ ] | > 1.
Then, all nodes in O [u,u ′ ] are on the same side of [u, u ′ ] by Lemma 3. By the assumption, they are closer to u. By A L , robots on the nodes in

O [u,u ′ ] in C t move toward the nodes of [u, u ′ ].
That is, after one round, v becomes at an even distance from u ′ , and we retrieve case 1. Hence, we can deduce that the gathering is achieved after

D-1 2 + 1 rounds. A contradiction. (b) |O [u,u ′ ] | = 1. By the assumption and w.l.o.g., dist(v, u) < dist(v, u ′ ). Let u v 0 , u v 1 , u v 2 , . . . u vx , . . . , u v ′
x be the sequence of nodes from u v 0 toward u such that u v 0 = v, u vx = u and u v ′ x = u ′ (refer to Fig. 7 for an example). Let D ′ = dist(u v 0 , u vx ) (in Fig. 7 -configuration C t 0 , u vx = u v 5 and D ′ = 5). By A L , two cases are possible: i. The number of occupied nodes is equal to three and u v 0 is adjacent to u vx then, the robots on

[u, u ′ ] ([u vx , u v ′ x ]) move toward u v 0 .
As there is no crashed robot, after one round, the border robots become at an even distance, and we retrieve case 1. Thus, the gathering is achieved in D-1 2 + 1 rounds. ii. Otherwise, all robots on a node in [u, u ′ ] move toward u v 0 while the robots on node u v 0 move toward u. Let C t 1 be the configuration reached once the robots move. Since there is no crashed robot by assumption, all the robots move and the distance between every robot on a node in [u, u ′ ] and those on u v decreases by two. Hence,

[u v x-1 , u v x ′ -1 ] become the target segment in C t 1 and dist(u, u ′ ) = dist(u v x-1 , u v x ′ -1 ) in C t1 . Moreover, dist(u v 0 , u) in C t is equal to dist(u v 1 , u v x-1 )-2 in C t 1 . By A L , the robots on a node in [u v x-1 , u v x ′ -1 ] move toward u v 1 while the robots on u v 1 move toward u v x-1 . In the configuration reached C t 2 , [u v x-2 , u v x ′ -2 ]
is the target segment. By repeating the same process, after ⌊ D ′ 2 ⌋ rounds, in configuration C t ⌊ x 2 ⌋ , the robots initially on u in C t become located on node u v ⌈ x 2 ⌉ , the ones on u v 0 on u v ⌊ x 2 ⌋ and the ones on u ′ on node u v x ′ -⌊ x 2 ⌋ (refer to Fig. 7 for an example). Again, as there is no

crashed robot, dist(u, u ′ ) in C t is equal to dist(u v ⌈ x 2 ⌉ , u v x ′ -⌊ x 2 ⌋ ) and [u v ⌈ x 2 ⌉ , u v x ′ -⌊ x 2 ⌋ ] is the target segment in C t ⌊ x
2 ⌋ . After one additional round, we retrieve case 1. We can deduce that the gathering is achieved after D-1 2 rounds, D ′ -1 2 rounds are needed for the borders to become at an even distance and then D-D ′ 2 rounds for the robots to gather. From the cases above, we can deduce that robots gather in O(D) rounds. □

We focus in the following on the case in which a single robot crashes. Proof. First observe that if the crashed robot is not collocated with a non-crashed robot, after one round the robots on the other border move towards the crashed robot location, and gathering is achieved after D rounds. Now assume that the crashed robot is collocated with at least one non-crashed robot. If D = 2, then after one round, all non-crashed robots are located at the same node, adjacent to the crashed robot location, and after one more round, gathering is achieved. If D > 3 is even, then after one round the crashed robot is alone, and the non-crashed robots form two multiplicity points and are the extremities of the target segment. So, after one more round, they both move towards the crashed robot location, and we reach a configuration with two occupied nodes, and the distance between them has decreased by two. By induction and the previous case, gathering is eventually achieved. If D = 3, then similarly, one can show that in three rounds, gathering is achieved. If D > 3 is odd, then similarly, one can show that after three rounds we reach configuration with two occupied nodes, and their distance has decreased by 3 (so, the distance is now even and we can apply one of the previous even cases). □ Lemma 6. Let C be a configuration where [u, u ′ ] is the target segment with O [u,u ′ ] = {v}, and w.l.o.g. u ′ is a border. Let D be the distance between the two border nodes u ′ and v. If u ′ hosts a crashed robot and dist(v, u) = 1, then gathering is achieved in O(D) rounds.

Proof. Thanks to Lemma 5, it is enough to prove that, in O(D) rounds, a configuration C ′ in which there are only two occupied nodes v and u ′ with dist(v, u ′ ) > 1 is reached. By A L , if the number of occupied nodes in C is more than three, the robots in [u, u ′ ] move toward v while the robots on v move toward a node toward [u, u ′ ]. That is, if there is a multiplicity on u ′ , all non-crashed robots move to their adjacent node toward u. Thus, after one round, u ′ hosts only a crashed robot. As u and v are neighbors, the robots on these nodes simply exchange their positions. However, note that [u, u ′ ] remains the target segment and the distance between the robots on u and nodes v ′′ ∈ [u, u ′ ] with v ′′ ̸ = u and v ′′ ̸ = u ′ decreases. In the reached configuration, the same robots are ordered to move. Hence, eventually, u becomes adjacent to two occupied nodes. After one round, |[u, u ′ ]| decreases. As u and v remain occupied and adjacent to each other, the robots in [u, u ′ ] continue to move toward u to eventually join it. Thus, by repeating this process,

|[u, u ′ ]| decreases until |[u, u ′ ]| = 2.
As the initial distance between the robots is less than D, after at most D rounds, a configuration in which there are three occupied nodes u, u ′ and v, is reached. In this special case, by A L , after one round, v and u ′ are the only occupied nodes. Observe that since [u, u ′ ] is a target segment, dist(u, u ′ ) ≥ 2 and hence dist(v, u ′ ) ≥ 3. After that, by A L , robots on v are the only ones to move. Hence the lemma holds. □ Proof. Recall that, since

v ∈ O [u,u ′ ] , dist(u ′ , v) is odd in C.
If the distance m between u and v is 1, the we apply Lemma 6, otherwise, by A L , the robots in v move to an empty node toward u, and all the other robots move towards v. Thus, after one round, we reach a configuration C 1 where the robots on v becomes at an even distance from u ′ , the crashed robot location. Since the robots on u are also ordered to move toward v, the distance between the robots at v and u decreases by two. Again, as u ′ hosts a crashed robot, after one more round, a configuration C 2 in which the borders are at an odd distance is reached again, and the distance between the robots at u and v is again decreased by two (or stay the same if they are adjacent in C 2 as they just swap their positions).

As the distance m between v and u is odd in C (otherwise, the border robots are at an even distance in C), we can repeat the same 2-round process (⌈m/4⌉ times) until we reach a configuration in which the robots at u and v are at distance 1 so, by Lemma 6, gathering is achieved. □ Lemma 8. Starting from a configuration C where the crashed robot is at a border, and the border robots are at an even distance D, by executing A L , after O(D) rounds, gathering is achieved.

Proof. The proof is by induction on D. As the borders are at an even distance, by A L , these robots are the ones to move. However, as the crashed robot does not move, after one round, the distance between the border robots D 1 becomes odd (D 1 ≥ 3). Observe that D 1 = D -1.

So if D = 2, in the reached configuration C ′′ , all the non-crashed robots are located at a node adjacent to the crashed robot location, and after one more round they all move towards the crashed robot location and the gathering is achieved.

If D > 2, in the reached configuration C ′′ , the following cases are possible:

1. The configuration C ′′ is edge-symmetric. By A L , the border robots are the ones to move and their destination is their adjacent node toward an occupied node. Hence, at the next round, all robots located at one border move to their adjacent node toward an occupied node. In the configuration, the distance between the two border robots D 2 is even and D 2 = D -2. 2. Otherwise. By Lemma 2, there exists a pair of occupied nodes that are at an even distance.

As C ′′ is neither node-symmetric (otherwise, the borders are at even distance) nor edgesymmetric (otherwise, case 1 holds), two occupied nodes u and u ′ are uniquely identified such that [u, u ′ ] is the target segment. Let u x be the node that hosts the crashed robot, two cases are possible: (a) u x ∈ {u, u ′ }. Assume w.l.o.g. that u x = u ′ . Let us first consider the case in which Proof. First, let us consider the case where D is even.

|O [u,u ′ ] | = 1 and let v ∈ O [u,u ′ ] . If dist(u, v) = 1,
1. If the crashed robot is at an equal distance from both borders, by A L , the border robots move toward each other. As they do, the distance between them remains even. Hence, the border robots remain the only ones to move. Eventually, all robots which are not co-located with the crashed robot become border robots and hence move. Thus, the gathering is achieved in D 2 rounds. 2. If the crashed robot is a border, by Lemmas 8, we can deduce that the gathering is achieved in O(D) rounds. 3. Otherwise, as the border robots move toward each other by A L , the crashed robot eventually becomes at the border. We hence retrieve case 2.

From the cases above, we can deduce that the gathering is achieved whenever a configuration in which the borders are at an even distance, is reached.

Let us now focus on the case where D is odd. By A L , two occupied nodes u and u ′ at the largest even distance are uniquely identified to set the target segment [u, u ′ ] (recall that C is, in this case, rigid, and each robot has a unique view since the initial configuration cannot be edge-symmetric). The robots behave differently depending on the size of O [u,u ′ ] , the set of occupied nodes outside the segment [u, u ′ ]. By Lemma 3, all nodes in O [u,u ′ ] are on the same side. Assume w.l.o.g. that for all u i ∈ O [u,u ′ ] , u i is closer to u than u ′ . Two cases are possible:

1. |O [u,u ′ ] | > 1. Let u f , u f ′ ∈ O [u,u ′ ] be the two farthest nodes from u such that dist(u, u f ) > dist(u, u f ′ ).
Note that u f is a border robot. Let u f +1 be u f 's adjacent node toward u ′ f . If u f does not host a crashed robot, then as the robots on u f move toward u and those on u ′ remain idle by A L , after one round, the border robots become at an even distance and we are done. By contrast, if u f hosts a crashed robot, then either u f hosts other non-crashed robots, and hence after one round, we retrieve a configuration C ′ in which [u f +1 , u ′ ] is the target segment and |O [u f +1 ,u ′ ] | = 1 or a configuration C ′ in which [u f ′ , u ′ ] is the target segment and |O [u f ′ ,u ′ ] | = 1 as robots on u f ′ also move toward u by A L . In both cases, we retrieve the following case. 2. |O [u,u ′ ] | = 1. Let u f be in O [u,u ′ ] and assume w.l.o.g. that dist(u, u f ) < dist(u ′ , u f ) (observe that u f is a border node). If u f hosts the crashed robot, then, after one round, the border robots are at an even distance as robots on u ′ move toward u f by A L . Similarly, if u ′ hosts the crashed robot, then by Lemmas 6 and 7 after O(D) rounds, a configuration in which the border robots are at an even distance is reached. If neither u f nor u ′ hosts the crashed robot, then when the border robots move by A L (other robots also move, but we focus for now on the border robots), either the distance between the two borders becomes even after one round (in the case where u f is adjacent to u as the robots simply exchange their respective positions) or the distance between the border robots remains odd but decreases by two. Observe that in the later case, the border robots keep moving toward each other by A L until one of them becomes a neighbor to a crash robot. Let C ′ be the configuration reached once a border robot becomes adjacent to a crashed robot. Let u b be the border node that is adjacent to crashed robot, and let u b be the other border node. We refer to the node that hosts the crashed robot by u From the cases above, we can deduce that the theorem holds. □

Fig. 1 .

 1 Fig. 1. Instance of a configuration in which the segment [u2, u9] is highlighted.

Fig. 2 .

 2 Fig. 2. Instance of a configuration in which [u, u ′ ] is the target segment. Nodes v and v ′ are both in O [u,u ′ ] .

Fig. 3 .

 3 Fig. 3. Instance of a configuration in which |O [u,u ′ ] | = 0. Robots at the border move toward an occupied node as shown by the red arrows.

Fig. 4 .

 4 Fig. 4. Instance of a configuration of the special case in which |O [u,u ′ ] | = 1 with only three occupied nodes. Robots on u and u ′ move to their adjacent node toward the node in O [u,u ′ ] , node uv, as shown by the red arrows.

Fig. 5 .

 5 Fig. 5. Instance of a configuration in which |O [u,u ′ ] | = 1. Robots in [u, u ′ ] move to their adjacent node toward the robot in O [u,u ′ ] while the robots in O [u,u ′ ] move toward the target segment as shown by the red arrows.

Fig. 6 .

 6 Fig. 6. Instance of a configuration in which |O [u,u ′ ] | > 1. Robots in O [u,u ′ ] move to their adjacent node toward the target segment as shown by the red arrows.

1 .

 1 C is edge-symmetric. The border robots move toward an occupied node. 2. Otherwise. Let [u, u ′ ] be the target segment in C, and let O [u,u ′ ] be the set of robots located on a node, not part of [u, u ′ ]. Robots behave differently depending on the size of O [u,u ′ ] : (a) |O [u,u ′ ] | = 0 (u and u ′ host the border robots). In this case, the border robots are the ones to move. Their destination is their adjacent node toward an occupied node (refer to Fig. 3 for an example). (b) |O [u,u ′ ] | = 1. Let u v be the unique occupied node in O [u,u ′ ] . Assume w.l.o.g. that u v

Fig. 7 .

 7 Fig. 7. Instance of an execution starting from a configuration in which |O [u,u ′ ] | = 1 and assuming no crashes.

Lemma 5 .

 5 Starting from a configuration C where there are only two occupied nodes at distance D > 1, one hosting the crashed robot, gathering is achieved in D rounds, where D denotes the distance between the two borders in C.

Lemma 7 .

 7 Let C be a configuration where [u, u ′ ] is the target segment, |O [u,u ′ ] | = 1 and w.l.o.g. dist(u, v) < dist(u ′ , v) where v ∈ O [u,u ′ ] .Let D be the distance between the two border nodes u ′ and v in C. If u ′ hosts a crashed robot, then gathering is achieved in O(D) rounds.

Lemma 9 .

 9 [u,u ′ ] | = 1. Let us now focus on the case in which |O [u,u ′ ] | = 1. By A L , all robots move toward u x if u 0 ̸ = u 1 . Hence, u 0 becomes occupied eventually. After one round, the distance between two border robots D 2 become even, D 2 = D -2, and we can use the induction hypothesis. □ Starting from a non-edge-symmetric configuration C with one crashed robot, all robots executing A L eventually gather without multiplicity detection in O(D) rounds, where D denotes the distance between the two borders in C.

  c . Since dist(u b , u c ) = 1 and dist(u b , u b ) is odd, dist(u b , u c ) is even. Hence, |O [u b ,uc] | = 1. Two cases are possible: -If C ′ hosts only three occupied nodes, then, after one round, the distance between the border robots becomes even, and we are done (recall that robots on u b and u c move toward u b by A L ). -If there are more than 3 occupied nodes and u c hosts also non-crashed robots in C ′ , then after one round, the distance between the border robots becomes even as the robots on u b move toward u c , those on u b move to u c and the non-crashed robots on u c move toward u b by A L . Hence, we are done. -Otherwise, after one round, the distance between the two borders remains odd as both borders move toward each other by A L . In the configuration reached C ′′ , u c becomes a new border occupied by a crashed robot and non-crashed robots. If there are only two occupied nodes in C ′′ , by A L , the border robots move toward each other. That is, in the next round, the border robots become at an even distance, and we are done. If there are more than two occupied nodes in C ′′ , by Lemmas 2 and 3, a configuration with a new target segment [o, o ′ ] which includes one border node is reached. Let us first consider the case in which u c ∈ [o, o ′ ]. If |O [o,o ′ ] | > 1, then after one round, the border robots become at an even distance, and we are done. By contrast, if |O [o,o ′ ] | = 1, then we are done by Lemmas 6 and 7. Next, let us consider the case where u c ̸ ∈ [o, o ′ ]. Let o f be the closest occupied node of u c . Without loss of generality, dist(o, u c ) < dist(o ′ , u c ) holds. If |O [o,o ′ ] | > 1, then after one round, a configuration in which [o ′ , o f ] is the target segment and u c ∈ O [o ′ ,o f ] is reached. After one additional round, we are done. Finally, if |O [o,o ′ ] | = 1, then robots on the nodes in [o, o ′ ] move toward u c , and we are done.

  Lemma 3. Let C be a non-edge-symmetric configuration, and let [u, u ′ ] be the target seg-ment. If |O [u,u ′ ] | > 1, then all nodes in O [u,u ′ ] are located on the same side of [u, u ′ ].Proof. Assume by contradiction that the lemma does not hold and assume that there exists a pair of nodesu 1 , u 2 ∈ O [u,u ′ ] such that u 1 and u 2 are on different sides of [u, u ′ ]. Assume w.l.o.g. that u 1 is the closest to u and u 2 is the closest to u ′ . Let dist(u 1 , u) = d 1 and dist(u 2 , u ′ ) = d 2 .If d 1 and d 2 are both even or both odd, dist(u 1 , u 2 ) is even. Since dist(u 1 , u 2 ) > dist(u, u ′ ), [u, u ′ ] is not the target segment, a contradiction. Otherwise, assume w.l.o.g. that d 1 is even andd 2 is odd, then dist(u 1 , u ′ ) is even. Since dist(u 1 , u ′ ) > dist(u, u ′ ), [u, u ′ ]is not the target segment, a contradiction. □ Lemma 4. Starting from a non-edge-symmetric configuration C, if no robot crashes, all robots gather without multiplicity detection in O(D) by executing A L , where D denotes the distance between the two borders in C.

  we are done by Lemma 6. By contrast, if dist(u, v) > 1 then, let u, u 1 , . . . u m , v be the sequence of nodes from u to v. By Lemma 7, after one round, a configuration C b) u x ∈ O [u,u ′ ] . Assume w.l.o.g. that dist(u, u x ) < dist(u ′ , u x ) holds. Let u 1 be the closest occupied node to u x , and u 0 be an adjacent node on the side of u 1 . Consider the case when |O [u,u ′ ] | > 1 holds.-If u x hosts a multiplicity, then after one round, the non-crashed robots move to u 0 and a configuration in which [u ′ , u 0 ] is the target segment is reached with|O [u ′ ,u 0 ] | = 1.-If u x hosts only a single robot (the crashed one), as only robots on u 1 are ordered to move toward u, after one round, a configuration in which [u ′ , u 1 ] is the target segment is reached with |O [u ′ ,u 1 ] | = 1. Hence, in both scenarios, we retrieve the case in which |O

′′′ Finally, if |O [u,u ′ ] | > 1, after one round, a configuration in which the borders are at an even distance D 2 = D -2 is reached and we apply the induction hypothesis.

(

From Lemmas 4 and 9, we can deduce: Theorem 4. Starting from a non-edge-symmetric configuration C, algorithm A L solves the SUIG problem on line-shaped networks without multiplicity detection in O(D) rounds, where D denotes the distance between the two borders in C.

Concluding Remarks

We initiated the research about stand-up indulgent rendezvous and gathering by oblivious mobile robots in the discrete model, studying the case of line-shaped networks. For both rendezvous and gathering cases, we characterized the initial configurations from which the problem is impossible to solve. In the case of rendezvous, a very simple algorithm solves all cases left open. In the case of gathering, we provide an algorithm that works when the starting configuration is not edge-symmetric. Our algorithms operate in the vanilla model without any additional hypotheses, and are asymptotically optimal with respect to the number of rounds to achieve rendezvous or gathering.

A number of open questions are raised by our work:

1. Is it possible to circumvent impossibility results in SSYNC using extra hypotheses (e.g., multiplicity detection)? 2. Is it possible to solve SUIR and SUIG in other topologies?


Huu Zujany Salazar

Nghia Nguyen

Wissam Mallouli

Ana R Cavalli

Edgardo Montes De Oca

5Greplay: a 5G Network Traffic Fuzzer -Application to Attack Injection

Keywords: 5G, Traffic Engineering, Nominal Traffic, Attack Injection, Fuzz Testing, DPDK

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

INTRODUCTION

The evolution of 5G mobile networks towards a service-based architecture (SBA) comes with the emergence of numerous new testing challenges and objectives. First, 5G deployment introduces a brand-new set of technologies, such as, the network function softwarization enabled by the software defined networking (SDN) and network functions virtualization (NFV), Mobile edge computing (MEC), and Network Slicing (NS). These require to be tested from a functional point of view; but, also from a non-functional point of view in order to determine the sanity of the system based on indicators such as data throughput performance, latency, scalability, robustness, etc. Finally, 5G SBA introduces new cybersecurity threats, with some of the previously adopted security and privacy mechanisms becoming ineffective or not applicable in 5G due to the changes in the architecture and the advent of new services [START_REF] Ahmad | Overview of 5G Security Challenges and Solutions[END_REF]. This requires the creation of new sets of security test cases and tools specifically targeting 5G security concerns.

The 3GPP standardization organism has proposed a wide set of test cases to check functional and non-functional requirements in 5G network products. For example, in the TS 33.117 catalogue [START_REF]3GPP TS 33.117 -Catalogue of general security assurance requirements[END_REF] of general 5G security assurance requirements, they propose a group of test cases to verify if network products providing externally reachable services are robust against unexpected inputs. The target of these tests are the 5G protocol stacks (e.g., Diameter stack). Other specifications, such as the TS 33.512 [START_REF]512 -5G Security Assurance Specification (SCAS); Access and Mobility management Function (AMF)[END_REF], concerning the security assurance of the Access and Mobility management Function (AMF), provides test cases to verify that this 5G component is properly protected against specific vulnerabilities.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

Regarding security testing, 5G issues have been the subject of numerous studies. Standardization organisms list collections of threats and vulnerabilities [7], also investigated by academia [START_REF] Ahmad | Overview of 5G Security Challenges and Solutions[END_REF][START_REF] Basin | A Formal Analysis of 5G Authentication[END_REF], and Industrial researchers [START_REF] Ericsson | A guide to 5G network security. Conceptualizing security in mobile communication networks -how does 5G fit in?[END_REF] [START_REF]5g Standalone Core Security Research[END_REF].

Several sources have studied the problematic of replay attacks in 5G networks, that could expose the system to Man-inthe-Middle (MiTM) or Denial-of-Service (DoS) attacks. Technology reports identify the possibility of malicious actors performing a DoS or MiTM attack by replaying Packet Forwarding Control Protocol (PFCP) messages that manage GPRS Tunnelling Protocol (GTP) tunnels. The ENISA organisation [START_REF]ENISA threat landscape for 5G Networks[END_REF] alerts that an AMF can be vulnerable to replay attacks of Non-Access Stratum (NAS) signaling messages between the UE and AMF on the N1 interface. Moreover, ENISA adds that the security of a network slice could be compromised if an attacker spoofs a genuine network manager by obtaining access to an insecure network management interface, or just by replaying or modifying a valid message.

In order to overcome these issues, numerous research has been done in the matter of detection and prediction of 5G cyber-attacks. Several Intrusion Detection Systems (IDSs) have been proposed [START_REF] Antonio Sotelo Monge | Traffic-flow analysis for source-side DDoS recognition on 5G environments[END_REF][START_REF] Moudoud | Prediction and Detection of FDIA and DDoS Attacks in 5G Enabled IoT[END_REF]. Nevertheless, to the best of our knowledge, there is a lack of open-source solutions that enable to manually create or edit existing 5G network protocol packets and injecting them in a network, allowing to easily test the proposed detection schemes.

Therefore, besides the significant amount of functional and non-functional proposed test cases, as well as the previously mentioned collections of 5G network threats and vulnerabilities and intrusion detection approaches, the testing of 5G network components and IDSs remains a challenge. This is in part due to the lack of publicly available labeled data sets containing realistic user behavior and up-to-date attack scenarios [START_REF] Ring | Flow-based network traffic generation using Generative Adversarial Networks[END_REF].

Open-source tools, such a Tcpreplay, aim solving this issue by enabling to replay malicious traffic patterns on IDSs.

More recent versions of the tool include the capability to replay traffic on web servers. Within the Tcpreplay suite, Tcpwrite allows editing, creating and replaying PCAP files in a network. However, it targets modifying IP, TCP and UDP attributes and fields. Other packet manipulation solutions such as Scapy are also not 5G-oriented.

Here, we propose 5Greplay, an open-source solution to perform fuzz testing of 5G networks. 5Greplay aims to facilitate the testing process of 5G virtual network functions and IDSs by allowing to forward network packets from one network interface card (NIC) to another with or without modifications. The tool supports the implementation of test cases by letting the users create specific scenarios using PCAP files that contain conventional 5G network traffic and execute them on a target network.

The preliminary experimentation shows that the traffic generated by the tool is correct with respect to the protocols' standardization and is accepted by open-source 5G frameworks, such as, open5GS, free5GC. The tool gives users the ability to alter 5G packets in a very flexible way to perform tests and attack scenarios. The experimental results also show the scalability of the tool to replay very high-bandwidth traffic.

The rest of the paper is structured as follows. Section 2 presents the tool's architecture and functionalities. It also presents possible use cases for performing 5G functional or non-functional tests. Section 3 presents technical details about the tool's implementation and the background information about the SDK library and rule engine used by the tool. Section 4 presents three experimental scenarios used to evaluate the tool's efficiency. And finally, the paper ends in Section 5 with the conclusion and possible future work.

5GREPLAY GENERAL OVERVIEW

5Greplay is an open-source solution entirely developed by the authors that allows forwarding network packets from one network interface card to another with or without modification. It can be considered as a one-way bridge between the input NIC and the output one. It can also take as input pre-captured packets that are saved in a PCAP-format file. Its behavior is controlled by user defined rules and completed by a configuration file. The user defined rules allow explicitly indicating which packets can be passed through the bridge and how a packet is to be modified in the bridge.

The configuration file allows specifying the default actions to be applied on the packets that are not managed by the rules, i.e., if they should be forwarded or not. 5Greplay's global architecture is depicted in Figure 1.

For each arriving packet, 5Greplay classifies the packet to identify its protocol, extracts the protocol attributes that are used in the rules, and checks whether each rule in the set of rules is satisfied or not. If no rules are satisfied, 5Greplay applies the default action that is defined in the configuration file. The default action is either: FORWARD to forward the packet to the output NIC without any modification, or DROP to drop the packet. Otherwise, if the packet satisfies a rule, 5Greplay will apply the action defined by the rule (see Section 2.1). If the action is FORWARD, then 5Greplay modifies the packet as defined in the rule before sending it to the output NIC.

In the following sections, we give technical details of 5G architecture. Section 2.1 describes the syntax of the rules that determine the behaviour of the tool, and Section 2.2 shows different configurations in which the tool can be use.

System requirements for running 5Greplay, usage instructions, and more detailed technical information, as well as the tool itself, can be found in the following Montimage dedicated url: http://5greplay.org.

Rules

5Greplay rules allow users to select specific packets in an incoming stream by using Deep Packet Inspection (DPI)

techniques to classify and extract protocol attributes. When defining a replay rule, users must indicate the following three elements in the rule: 1) which packet will be processed, 2) which action will be applied, and 3) how to modify the packet.

The rules are specified in XML format, Listing 1 presents the rule used in the scenario 2 (see Section 4.3). The objective of this rule is to created malformed Next Generation Application Protocol (NGAP) packets and replay them on the targeted 5G core network. First, the user defines the desired actions to take for the filtered packets in the if_satisfied attribute. In this example, the action is to change the Stream Control Transmission Protocol (SCTP) protocol identifier from 60, that corresponds to the NGAP protocol, to 0. Then, the user defines the conditions to filter the packets on which the actions will be performed. These conditions are listed as events that happen one after the other following the time limits specified by delay_units, delay_min, delay_max fields. In the example, the time between events must be more than 0ms and less than 1ms. Finally, the events are defined. Each event has an identifier event_id, a description, and a condition expressed in the boolean_expression field. In the example, there are two events, in other words, two filtering conditions. First, there must be a packet with a NAS message type equal to 93, corresponding to a NAS Security mode Command message. Then, if less than 1ms later there is a packet with NAS Security type equal to 4, corresponding to a NAS Security mode Complete message, this packet will be modified as specified by the if_satisfied attribute and forwarded to the address indicated in the 5Greplay configuration file. To perform the fuzzing operators defined in Table 1, 5Greplay can operate over SCTP, NAS-5G and NGAP protocols.

The tool incorporates a plugin architecture for the addition of new protocols and data structures; furthermore, if a specific test scenario requires parsing a protocol that is not currently supported, the addition of it is possible in a simple manner.

< property value = " THEN " delay_units = " ms " delay_min = " 0 " delay_max = " 1 " property_id = " 100 " type_property = " FORWARD " description = " Forwarding NAS security mode COMPLETE that answers to NAS security mode COMMAND " if_satisfied = " # update ( sctp_data . data_ppid , 0) " > < event event_id = " 1 " description = " NAS Security mode COMMAND " boolean_expression = " ( nas_5g . message_type == 93) " / > < event event_id = " 2 " description = " NAS Security mode COMPLETE " boolean_expression = " ( nas_5g . security_type == 4) " / > </ property > Listing 1. Forwarding a NAS security mode Complete message that answers to the NAS security mode Command message 2.2 Use cases 2.2.1 Classical Traffic Replay. 5Greplay is intended for providing a complementary solution to existing tools that support 5G network traffic. The use cases of 5Greplay can be classified into two categories, offline and online, depending if the input packets are coming from a pre-captured PCAP file or live streaming. When inputting a PCAP file, it can be considered as a classical traffic replay tool (e.g., Tcpreplay and Tomahawk). However, it differs from the existing tools, which usually replay pre-captured packets without altering them or only allow modifying them at the IP layer in a predefined manner, such as, Tcpreplay that allows increasing the IP source and destination fields after each iteration.

On the other hand, 5Greplay focuses on the modification of 5G protocols, such as, NAS-5G, NGAP. Moreover, the tool empowers the users to be able to alter arbitrary attributes in an arbitrary way.

Service

Chains. 5Greplay is able to alter 5G packets in real-time and can be easily combined with other tools. Its input is a network traffic stream that may be the output of other tools or services. We list some possible combinations of 5Greplay with existing tools in Figure 2. As shown, 5Greplay can be placed after another network replay tool, such as, Tcpreplay to be able to provide more capabilities for altering packets. For example, the TCP/IP layer can be managed by Tcpreplay, while our tool can take care of managing the 5G protocol layers.

MMT-5Greplay

Traffic The input of 5Greplay can also be a real network traffic stream, for instance in the Radio access network (RAN)

or Core networks. The tool will select some interesting packets to be altered, then output them to the output stream traffic_stream' that is then merged into the original traffic_stream to allow injecting the new altered packets into the legitimate network traffic. The same scenario can be applied on an experimental environment in which the real 5G traffic stream is generated by a simulator. In our evaluation experiments, we use UERANSIM to simulate the 5G-SA (5G Stand Alone) RAN network since there is yet no open-source solution available for the 5G-SA RAN network.

BACKGROUND

Fuzz testing and mutant operators

Mutation testing is a software testing method that aims detecting faults by generating numerous similar test cases.

It does this by changing a program P under test according to specific rules R to obtain a new syntactically correct program M. M is called a mutant of P, and R is referred to as the mutant operator [START_REF] Wong | Reducing the cost of mutation testing: An empirical study[END_REF].

5Greplay aims performing fuzz testing, a type of mutation testing that injects invalid, unexpected, or random inputs to evaluate the response of a test target, in this case 5G virtual network functions, IDSs, 5G applications, etc. It generates mutants of the network traffic by using mutant operators, in order to perform specified security and functional tests on a system, as well as generating many new test variants.

Let P denote a 5G network packet (e.g., the security mode command message that the AMF sends to the UE to initiate the SMC procedure) in a PCAP file or a specific real-time flow of network packets, Table 1 depicts the simplest operators that we consider necessary to mutate the network traffic, and that can be combined in order to generate complex mutants of the original traffic.

Atomic operator Description DEL_PKT(P) Delete a packet CH_ATTR(P)

Change a specific attribute on the header of a network protocol message ORD(P1, P2)* Exchange the order of two consecutive packets DUP_PKT(P) Duplicate packet

DPI -Deep Packet Inspection

DPI is an advanced technique used for classifying network traffic [START_REF] Valenti | Reviewing Traffic Classification[END_REF]. It aims at replacing the first generation of port-based classification methods that traditionally examine network packets by searching information in the packets' headers. The transport protocol and application ports are usually sufficient to identify the application protocol. With the emergence of port-independent, peer-to-peer and encrypted protocols, the task of identifying application protocols has become increasingly challenging. DPI examines the contents of packets passing through a given checkpoint and a set of signatures not only in the headers but also in the payloads in order to classify the packets more accurately. This is possible only if the payload is not encrypted, can be decrypted, or certain data can be extracted, such as statistical data, and analysed, for example using machine learning techniques, that can be used to categorize the packets or flows.

5Greplay relies on MMT-DPI, a C library that implements DPI techniques to analyse network traffic in order to classify the network protocol or application a packet belongs to, and to extract network and application based events, such as, protocols field values, network and application QoS parameters, and KPIs. MMT-DPI implements a plugin architecture to allow easily adding new protocols and analysis techniques. It provides a set of public APIs for integration with third party probes. The library has been developed by the authors and it is Montimage property, but the necessary part of it will be part of the 5Greplay open-source project.

EXPERIMENTAL EVALUATION

The main objectives of the preliminary experimentation are: i) to determine whether the altered packets generated by the tool are accepted by 5G services/components, ii) to verify that the traffic injection works correctly, and iii) to test the scalability of the tool. The following section will introduce four of the selected testing scenarios to evaluate these objectives. The scenarios are focused on altering 5G traffic in the N1 and N2 interfaces between the RAN and Core networks.

The fist scenario is a simple offline modification of a PCAP file. The second scenario aims modifying online packets.

The third scenario intends creating a replay attack against a simulated AMF. These scenarios test the traffic injection capability of 5Greplay, as well as check if the altered packets are accepted by an Intrusion Detection System, and the 5G core simulators. The last scenario is dedicated to evaluating the scalability of the tool by generating high-bandwidth traffic and, thus, to be able to perform a DoS attack (or stress testing) against a target component/service. 4.1.3 Result analysis. The traffic was successfully modified and replayed, and MMT triggered an alert to indicate the suspicious activity in the network. Figure 4 shows the notified alert, with the modification in the ngap.ran_ue_id attribute of the packet that should be 77 but is 22. From this scenario we can conclude that 5Greplay can modify PCAP files and replay them to a NIC, enabling the evaluation of rule-based IDSs using the fuzz operator CH_ATTR(P).

Scenario 2:

Sending malformed packets against open-source 5G cores in real-time 4.2.1 Description. This use case scenario evaluates the capability of 5Greplay to systematically create and send malformed packets to a 5G core network, in order to evaluate its robustness against unexpected entries at run-time.

Testbed

Setup. We performed this scenario against the two 5G core open-source solutions, free5GC and open5GS. In both cases we used the RAN simulator UERANSIM. Free5GC and UERANSIM are installed on two different virtual machines, connected via a private network, while open5GS and UERANSIM are installed on the same machine. To test the online forwarding functionality of 5Greplay, we configured 5Greplay to detect NGAP protocol messages sent by the UE during the authentication exchange, and replayed them to the AMFs, changing the SCTP protocol identifier from 60 to 0, in such a way that we could evaluate the robustness of the core services against malformed NGAP packets. We depict this scenario in the Figure 5.

Analysis of the results.

When replaying against free5GC, we got an AMF warning, but the simulator keep running and allowed new UE connections, as showed in the Figure 6. Therefore, we conclude that it is protected against this type of malformed NGAP packets. On the other hand, open5GS was not able to handle this packet and the simulator crashed, preventing new connections to the AMF, as depicted in Figure 7.

In this case, we evaluated the capability of 5Greplay to replay and modify 5G network packets in a online way, through a private network or in a same machine by using the fuzz operator CH_ATTR(P).

Scenario 3: NAS-5G SMC Replay attack

4.3.1 Description. This scenario evaluates the use of 5Greplay to perform security tests by modifying and injecting network traffic into a specif target. ENISA, in its threat landscape for 5G networks mentioned before, reported that AMFs are vulnerable to replay attacks of the NAS Security mode control (SMC) procedure messages. Moreover, the 3GPP TS33.512 specification for the AMF Security Assurance[9] proposes a test case to verify if an AMF is properly protected Before the establishment of the security context, the NAS messages are not encrypted. A malicious actor, with access to the NAS traffic in the interface N1, could intercept a NAS SMC Security Mode command clear message sent from the AMF to the UE, copy its NAS sequence number (NAS SQN), and use it to build a NAS SMC Security Mode complete message that is replayed to the AMF, or directly intercept a NAS SMC Security Mode complete message and replay it to the AMF.

If the AMF does not implement a proper protection against this type of attack, the network will not drop the replayed packet. Furthermore, a malicious actor could use this technique to impersonate an UE and force the system to reduce the security level by using a weaker security algorithm or turning the security off and, thus, compromise the system.

We depict this scenario in the Figure 3.

Testbed

Setup. We performed this security test scenario in a 5G open-source simulation platform based on free5Gc and UERANSIM. To test the online forwarding functionality of 5Greplay and the protection of the open5GS AMF against replay attacks, we configured the 5Greplay in order to detect the NAS SMC Security Mode complete messages sent by the UE after its authentication, and replay it twice to the AMF. Then, we checked the AMF logs, and we monitored the network to verify that the AMF actually received the same packet twice.

Analysis of the results.

As depicted in the free5Gc AMF log and shown in Figure 9, after the NAS SMC Security Mode Command message, the AMF received a legitimate NAS SMC Security Mode complete message, and two NGAP packets with the same UE NGAP ID as the legitimate user. The AMF identified this as not belonging to the same NGAP security context. These two packets corresponded to the replayed packets by 5Greplay and allow us to conclude that the free5Gc AMF is protected again this type of replay attack. Moreover, we proved the utility of 5Greplay to perform standardized security tests by using the fuzz operator CH_ATTR(P). 4.4.2 Testbed Setup. We replay a pre-captured PCAP file against a 5G core service. The PCAP file contains traffic of a complete UE session. To generate such traffic, we firstly start nr-gnb in UERANSIM to activate the gNodeB. We then start nr-ue in UERANSIM to connect to the open5GS. After that, we stop nr-ue and then nr-gnb. The PCAP file is then used by 5Greplay to inject its packets against the targeted core service. We repeat the test many times. 5Greplay has a parameter nb-copies that indicates the number of copies of a packet that must be created and injected into the network. We increase nb-copies by 10 for each successive replay. The test is stopped when we see an error in the execution log of the service. 2 resumes the tests on AMF services of open5GS and free5GC. When replaying network traffic against open5GS, we got an OGS_CLUSTER_8192_SIZE error when the number of copies reaches 1780, as depicted in Figure 10. The average replaying rate is about 509.5 pps and 834 kbps.

After looking into the issues tracker of open5GS, we found that open5GS AMF allocates its memory pool to be able to handle by default a maximum of 1024 UEs. We then changed the pool parameter of the AMF to increase the memory pool, so that the AMF can handle more. Nevertheless, AMF crashed again when we increased the nb-copies parameter of 5Greplay.

When evaluating free5GC we got the errors showed in Figure 11 when the number of copies is more than 3000.

When the number of copies is exactly 3000, 5Greplay generated an average traffic rate of 594.9 pps and 974 kbps. Since these rates are very low with respect to the ability of 5Greplay when using DPDK, we can conclude that 5Greplay can #packet copies Avg. packets/s Avg. kbit/s open5Gs 1780 509.5 834 free5GC 3000 594.9 974

Table 2. Endurance of 5G AMF services against traffic replaying Fig. 10. Error in open5GS AMF when replaying 1780 packet copies Fig. 11. Error in free5GC AMF when replaying 3000 packet copies be used to test the robustness of 5G core services when supporting a huge number of UEs by using in the fuzz operator DUP_PKT(P).

CONCLUSION

In this paper, we have introduced our 5G replay tool to address the lack of an open-source tool to perform security testing in 5G networks. To achieve such purpose, the tool provides a flexible way to modify 5G protocol packets before injecting them to the target services to be tested. We presented in the paper four scenarios to evaluate the tool, including for testing the scalability of the tool. The experimentation results show that the alternated packets are correctly formatted with respect to the 5G standard protocols, such as, NAS-5G, NGAP. These packets are accepted by the 5G core services. The tool even provoked crashes in the targeted services when performing DoS attacks.

For future works, we will extend the tool to take into account the rules that allow users to generate packets from scratch. We are also defining new 5G attacks that can be replayed by the tool, and investigating techniques to manage encrypted traffic. We plan to provide an easy way to replay a complete session, and intend to implement and test new ways to alter packets, such as changing the order of two packets. Furthermore, the experimental evaluation will be performed on other 5G interfaces.

  5Greplay parses most Internet protocols and applications. Regarding 5G dedicated protocols, the tool currently enables filtering 5G packets of Non-Access-Stratum protocol for 5G System (NAS-5G), NG Application Protocol (NGAP), GPRS Tunnelling Protocol version 2 (GTPv2), Stream Control Transmission Protocol (SCTP) and DIAMETER protocols.

Fig. 2 .

 2 Fig. 2. 5Greplay in Service chaining

Fig. 3 .

 3 Fig. 3. Offline Example -Sending modified network traffic between two virtual machines

4. 1

 1 Scenario 1: Modifying and injecting network traffic offline 4.1.1 Description. This use case scenario evaluates the capability of 5Greplay to modify packets from a pre-existing PCAP file and replaying it on a specific NIC. It tests if the altered packets can be processed by an Intrusion Detection System.

Fig. 4 .

 4 Fig. 4. MMT alert when detecting the modified traffic generated by 5Greplay

Fig. 5 .

 5 Fig. 5. Sending malformed NGAP packets against free5GC

Fig. 8 .

 8 Fig. 8. NAS-5G SMC Replay Attack

4. 4

 4 Scenario 4: High-bandwidth traffic generation 4.4.1 Description. The main objective of this scenarios is to validate the scalability of 5Greplay.For this, we configured the tool to replay the traffic as much as possible. The tool supports both libpcap and Data Plane Development Kit (DPDK). By using only one thread, the tool easily reaches the full-rate of 9.56 Gbps and 1.28 Mpps when testing on a Intel Ethernet Network Adapter X710. We profile the high performance of packet generation by performing what

Fig. 9 .

 9 Fig. 9. Free5Gc AMF log when replaying Security Mode Complete messages (SMC)

<

  property property_id = " 103 " type_property = " FORWARD " description = " Inject packets from UE to Core " > < event description = " From UE and NAS -5 G packets " boolean_expression = " ( ( # is_same_ipv4 ( ip . src , '127.0.0.1 ') ) & amp ;& amp ; (( sctp . dest_port == 38412 ) & amp ;& amp ;( sctp . ch_type == 0) ) ) " / > </ property > Listing 3. 5Greplay rule to forward packets to AMF services The packets being forwarded are selected by the rule in Listing 3. This is a simple rule having only one event. It selects any packets issued from 127.0.0.1 that is the IP address of the UERANSIM UE, and the SCTP destination port 38412 that is assigned by IANA to be used by the NGAP protocol[8]. The last condition, sctp.ch_type == 0, allows selecting only the SCTP data chunk, thus avoiding replaying SCTP HEARTBEAT packets that are used to maintain the SCTP connections.4.4.3 Analysis of the results. Table

Table 1 .

 1 5Greplay atomic operators. *Currently not implemented

© 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. Manuscript submitted to ACM

ACKNOWLEDGMENTS

This research is supported by the H2020 projects SANCUS N°952672, INSPIRE-5Gplus N°871808, and the French ANR project MOSAICO N°ANR-19-CE25-0012.