Gideon Smeding

Gregor Gössler

A Correlation Preserving Performance Analysis for Stream Processing Systems

For the design of real-time embedded systems, analysis of performance and resource utilization at an early stage is crucial to evaluate design choices. Network Calculus and its variants provide the tools to perform such analyses for distributed systems processing streams of tasks, based on a max-plus algebra. However, the underlying model employed in Network Calculus cannot capture correlations between the availability of different resources and between the arrivals of tasks, leading to overly conservative performance bounds for some frequently used system topologies. We present a model based on timing constraints relative to pairs of streams, endowed with an analysis technique that can handle such correlations.

I. INTRODUCTION

Modern stream-processing systems, such as multimedia applications and embedded automatic control systems, are often realized on heterogeneous, multi-processor architectures. Such architectures have a large design space, due to the choice in processors, the networks to connect them, the partitioning of software on the hardware, and the choice of scheduling regimes to allocate resources. As development progresses, architecture changes become increasingly expensive. It is therefore essential to evaluate the feasibility of a design at an early stage. In particular, the performance characteristics of a design, such as the throughput and required buffer sizes needed to fulfill the system requirements.

Let us review two illustrative examples, that, by the end of the paper, we will be able to fully analyse. For now, we will only informally introduce them. The exact meaning of the components in the examples will be introduced in the sequel.

The first example, depicted in Figure 1, models a multimedia decoder that decodes audio and video parts of an incoming multimedia stream separately and then joins the decoded streams at the output.

Each double arrow in the diagram represents a lossless channel with FIFO semantics (a stream). The PJD and BD denote sources of streams and resources, respectively. The GPC component denotes the actual decoding of audio or video streams consuming processor resources and producing a stream of decoded frames. The AND component synchronously joins the two streams by combining incoming audio and video frames in the output.

A second example, depicted in Figure 2, shows a server that is connected to the outside world by a bus. The server responds to update requests that arrive over a bus and returns a reply over the very same bus. Conflict-free access to the bus from both sides is achieved through a time-division, multiple-access (TDMA) policy. That is, exclusive access to the bus is given periodically to the requester and the server. The server has a certain delay before it responds. If this delay corresponds to the TDMA period, then the bus does not introduce any additional delay since the reply to a received request can immediately be transmitted. Two new components are used here: the TDMA component that splits a resources according to a fixed schedule, and the DEL component that imposes a fixed delay on a stream. In this example, the GPC components do not model processors or decoders, but the transmission of messages over the bus.

The performance of systems as the ones sketched above can be analyzed by different approaches. Simulation-based techniques are efficient but in general non exhaustive, and therefore may not reveal corner cases. On the other hand, formal analytical methods can offer strong guarantees for safety-critical systems. In this paper we present such an analytical method to discover absolute performance bounds.

Existing formal verification techniques for real-time systems are based on model-checking of timed automata [START_REF] Hendriks | Timed automata based analysis of embedded system architectures[END_REF], algebraic techniques like Network calculus [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF] and real-time calculus [START_REF] Chakraborty | A general framework for analysing system properties in platform-based embedded system designs[END_REF], scheduling theory [START_REF] Harbour | A Practitioner's Handbook for Real-Time Analysis[END_REF], or combinations thereof [START_REF] Henia | System level performance analysis the SymTA/S approach[END_REF].

In network calculus streams of events, such as the arrival of consecutive frames of data to be processed or the periodic activation of a task, are modelled as a cumulative function R over time. While one such function represents one concrete execution trace, a "curve" α characterizes an abstract event stream of all behaviors R, such that for all time instants t and

u where t ≤ u R(t) -R(u) ≤ α(t -u)
The availability of a resource is modelled by a similar cumulative function C and abstraction β such that

β(t -u) ≤ C(t) -C(u).
Given a processor with the resource characterized by a curve β that handles tasks characterized by α that arrive over a FIFO queue, network calculus shows that delay is bounded by the maximum horizontal distance between α and β and backlog, i.e., the maximum number of queued tasks at any time during execution, is bounded by their vertical distance. Moreover, it permits us to calculate the curve α that characterizes the stream of output events that correspond to the completion of tasks. This forms the basis of a compositional analysis for networks of processing components.

Unfortunately, the abstraction of streams can lead to pessimistic bounds for some systems, as is the case for our examples.

In the multimedia decoder of Figure 1, the application of network calculus, with an AND component as described in [START_REF] Haid | Complex task activation schemes in system level performance analysis[END_REF], will overestimate the needed buffer space, in particular the inputs x and y of the AND component. This originates in the model of streams: while the maximum number of arrivals of each individual stream are exact, the model does not show that peaks in the number of arrivals occur simultaneously in x and y. The AND component's inputs are considered only independently, thus leading to a pessimistic estimate of the output's variability.

In the example of Figure 2, even if the arrivals and resources are constant, network calculus will overestimate the needed buffer size between the server and the bus, because the causeeffect relation of the request and response in combination with the strict schedule of the TDMA cannot be modelled.

We propose an analysis based on a relative event model, where events and resource availability are modelled by functions that give the cumulative number of events at the time of each occurrence of another event. This leads to an event model that preserves correlations between events, and allows a natural integration of an abstraction similar to network calculus' curves, with bounds that model causal relations such as data-flow constraints.

A. Contributions

The main novelty presented in this paper is an event model based on a combination of two kinds of bounds on relative counter functions: simple clock bounds to model e.g. data-flow dependencies and drift bounds that limit relative variability to model e.g. burstiness of a flow. We derive general properties of such bounds and properties associated with the processing components, leading to an analysis method based on a fixpoint algorithm. Finally, we provide experimental evidence that our relative-time framework can find better bounds for the needed buffer space in the above examples.

B. Previous Work

Data-flow networks are represented naturally through relational constraints. The first such a notion is synchronic distance [START_REF] Petri | Interpretations of net theory[END_REF] for Petri nets. The synchronic distance is the maximum number of times a transition may fire before another must be fired. If the Petri net models a data-flow system, typically modelled by conflict-free nets, the synchronous distance of a producer from a consumer (both modelled by transitions) corresponds to the maximum buffer occupation between them.

The affine clock calculus used in the validation and compilation of real-time applications [START_REF] Smarandache | Validation of mixed SIGNAL-ALPHA real-time systems through affine calculus on clock synchronisation constraints[END_REF] programmed with a combination of SIGNAL and ALPHA, The calculus relates two clocks through a base clock. Typically, the arrival of complex tasks is related to their completions through a system clock that determines execution speed. These relations are expressed by affine transformations over the occurrence-times of events. The calculus then serves to determine synchronizability of two event streams.

The more recent work on n-synchrony [START_REF] Albert Cohen | N-synchronous Kahn networks: a relaxed model of synchrony for real-time systems[END_REF] develops a similar concept to verify synchronizability of programs written in a synchronous data-flow language extended with statically scheduled sample (a periodic selection of elements in a flow) and merge (a combination of two flows defined by a static schedule) operations and buffers with FIFO semantics. The verification is based on a type-system and determines whether the system can be executed with finite buffer sizes. The clock envelopes introduced in [4] further develop this system, using clock abstractions called envelopes that permit more efficient verification at the cost of some over-estimated buffer sizes.

The clock bounds, introduced in this paper, express the same essential relations as the data-flow relations of the mentioned work. The formalization of the relations as bounds on relative counter functions however, is new. And it is precisely this formalization that allows us to combine clock bounds with drift bounds. Clock bounds are more general than the synchronic distance on conflict-free nets, affine relations and clock envelopes, all of which can be represented by linear clock bounds in our model. Clock bounds are equal in expressiveness to the basic model of n-synchrony.

Drift bounds are essentially a relational variant of network calculus' arrival and resource curves. The problem of correlating variability of event streams, such as coincident bursts of arrival streams, has been studied before in various incarnations of network calculus.

In [START_REF] Rox | Modeling Event Stream Hierarchies with Hierarchical Event Models[END_REF], [START_REF] Perathoner | Modeling structured event streams in system level performance analysis[END_REF] the case where streams are transported over a network as a single, joined stream, to be separated at arrival, is treated by tracking the correlations between sub-streams and the aggregated stream. The event count curves of [START_REF] Perathoner | Modeling structured event streams in system level performance analysis[END_REF] are a special case of our drift bounds: a bound on a sub-stream with respect to the aggregate stream.

Correlated streams are also used in [START_REF] Huang | Performance analysis of multimedia applications using correlated streams[END_REF] for the analysis of a fork-join scenario, where the load of a single event stream is split over several processing components and then merged in a scenario similar to the multimedia decoder of Figure 1. However, [START_REF] Huang | Performance analysis of multimedia applications using correlated streams[END_REF] distribute frames over the processors for load distribution, like splitting traffic over two lanes and then merging it again, rather than the synchronous split join of our example.

Finally [START_REF] Wandeler | Characterizing workload correlations in multi processor hard real-time systems[END_REF] exploits correlations between the workload imposed by a task traversing a chain, which occur e.g. for tasks with variable payloads sizes that traverse a chain of processors: tasks that require many resources on the first processor because of a large payload, will also require more work for the next and vice versa. None of the above approaches uses a general relational model as presented in this paper.

II. A RELATIVE MODEL OF CLOCKS

This section introduces the behavioral model of systems, which, like network calculus, is based on cumulative functions. Then it introduces a first abstraction that relates all clocks to each other rather than to real-time.

In the model streams of periodically recurring events as clocks. For example, the arrival of audio frames in a multimedia stream is represented by a clock that ticks once for each arriving frame. If a resource is a processor, then each clock tick corresponds to a cycle that would be used to process a task. If the resource is a bus, each tick corresponds to the transfer of a task. The behavior of clocks is described by counter functions.

Definition 1 (Counter function (χ)). Let χ ∈ R → N be a counter functions such that it • starts at zero (χ(0) = 0); • is non-decreasing (t ≤ u =⇒ χ(t) ≤ χ(u)); and • is surjective (range(χ) = N).
Equivalently, we could choose to describe clocks by dater functions that give the time at which each tick occurs.

Definition 2 (Dater function). The dater functions η ∈ N → R corresponding to the counter function χ is defined as Figure 3 shows two counter functions and the corresponding dater functions. It also shows in a table how the dater function provides a trace of timestamps for each successive tick.

η(n) = min{t ∈ R | χ(t) ≥ n}
η i (n) η j (n) n η i (n) η j (n) 0 0.00 0.00 1 1.00 7.

Lemma 1 (Properties of dater functions). The dater function

η starts at zero (η(0) = 0), is strictly increasing (n < m =⇒ η(n) < η(m)), is total (domain(η) = N) and diverges (lim n→∞ η(n) = ∞).
Proof: As zero is an eliminator for minimization over the domain of positive numbers, the dater function must also start at zero. By contradiction it must be strictly increasing; if there were some n < m such that η(n) ≥ η(m), then we arrive at the contradiction that χ is decreasing. Totality is a consequence of the surjectivity of the counter function, which can be shown through contradiction. Finally, the dater function diverges, because the minimum also diverges if the time and the tick count go to infinity.

The dater function is not a proper inverse of the counter function because in general, η • χ = id. However, we do have the inequalities η(χ(t)) ≤ t, η(χ(t) + 1) ≥ t, and χ(η(n)) = n for all times t. This can be understood from the informal description of counter and dater functions: χ(t) gives the number of ticks of i up to, and including, time t, and η(n) gives the time when the n-th tick occurs.

In our model we concentrate on the logical behavior of clocks, as opposed to the temporal behavior. That is, how ticks of different clocks interleave with one-another. To this end, the clocks are modelled by the relations between them, concentrating on the relative order of events rather than their absolute timing.

Given two clocks i and j described by their counter functions χ i and χ j , their relative clock X i/j (n) gives the tick count of i at the n-th tick of j. Figure 4 depicts the relative counter function R i/j as well as R j/i from the counter and dater functions depicted in Figure 3. Definition 3 (Relative counter function (X i/j )). Let χ i and η j respectively be the counter and dater functions of two clocks i and j, then the relative counter function X i/j ∈ N → N is defined as

X i/j (n) = (χ i • η j )(n)
As the notation already gives away, the behavior of a whole system, consisting of a set K of clocks, is described by a column vector χ ∈ (R → N) K×1 and the corresponding row vector of dater functions η ∈ (N → R) 1×K . Thus we naturally obtain a matrix X ∈ (N → N) K×K of relative counter functions:

X =    χ 1 . . . χ n    • (η 1 • • • η n ) =    χ 1 • η 1 • • • χ 1 • η n . . . . . . . . . χ n • η 1 • • • χ n • η n   
The diagonal of the relative counter function matrix, consists of identity functions since X i/i (n) = χ i (η i (n)) = n for all clock i. A note on notation: anywhere where X i/j is used, it can be replaced directly by the composition χ i • η j .

Relative counter functions inherit most of the counter functions' properties. The most important difference being that relative counter functions can increase by more than one in a single step. For example, in Figure 4 X i/j jumps from 4 to 7, because i ticks three times between the second and third ticks of j.

We can also see that only the (non-strict) order of ticks is preserved, in the sense that if e.g. X i/j (2) = 4 we do not know if the fourth tick of i occurred simultaneously with the second tick of j, or if it preceded the second tick of j.

Lemma 2 (Properties of relative counter functions). Like normal counter functions, relative counter functions start at zero (X i/j (0) = 0), are non-decreasing (n ≤ m =⇒ X i/j (n) ≤ X i/j (m)) and diverge.

Proof: That X i/j (0) = 0 can be calculated directly. Divergence and non-decreasingness are both preserved by the composition of the non-decreasing and divergent counter and dater functions.

As a relative counter function X i/j characterizes the behavior of χ i with respect to χ j , we can compute a pseudo-inverse X -1 i/j characterizing the behavior of χ j with respect to χ i . Definition 4 (Pseudo-inverse). The pseudo-inverse X -1 i/j ∈ N → N of a relative counter function X i/j ∈ N → N is defined as

X -1 i/j (n) = min{m ∈ N | X i/j (m + 1) ≥ n}
We define the pseudo-inverse X -1 of a matrix as the pointwise pseudo-inversion and a transposition, i.e., [X -1 ] i/j = X -1 j/i . Subscription takes precedence over the inversion operator.

Lemma 3 (Properties of the pseudo-inverse). The pseudoinverse X -1 i/j has the same properties as a relative counter

X i/j (n) X j/i (n) X -1 i/j (n)
Fig. 4. The relative counter functions X i/j and X j/i created by composing the counter and dater functions of Figure 3, and the pseudo-inverse X -1 i/j . Note that X j/i (n) = X -1 i/j (n) + 1 occurs exactly when the clocks tick simultaneously.

function. That is, X -1 i/j goes through the origin, is nondecreasing and diverges. Furthermore, the inversion operator is symmetric (

[f -1 ] -1 = f ) and antitone (f (n) ≤ g(n) ⇐⇒ f -1 (n) ≥ g -1 (n) for monotonic f and g).
Furthermore, for any n ∈ N, (1)

X -1 i/j (X i/j (n)) < n, (2) X i/j (X -1 i/j (n)) < n for n > 0, (3) X -1 i/j (X i/j (n) + 1) ≥ n, and X i/j (X -1 i/j (n) + 1) ≥ n.
Intuitively we might expect the pseudo-inverse X -1 i/j to relate strongly to X j/i and maybe even be equal. The example in Figure 4 reinforces this, but it also shows that, for the few instances where the clocks i and j tick simultaneously, X -1 i/j = X j/i . As the following lemma shows equality almost holds, with a difference of one.

Lemma 4 (Inverse of relative counter function matrix). Let X be a matrix of relative counter functions, then X -1 ≤ X ≤ X -1 + 1.

Proof: We will prove this by deriving equal upper and lower bounds of the converse. First note that

X -1 i/j (n) = min{m ∈ N | (χ i • η j )(m + 1) ≥ n} = min{m ∈ N | η j (m + 1) ≥ η i (n)} because χ i (η i (n)) = n and η i (χ i (t)) ≤ t imply χ i (x) ≥ y ⇔ x ≥ η i (y). Then, since η j (χ j (t) + 1) ≥ t implies x ≥ χ j (y) ⇒ η j (x+1) ≥ y, we have the lower bound min{m ∈ N | η j (m + 1) ≥ η i (n)} ≤ min{m ∈ N | m ≥ (χ j • η i )(n)} = min{m ∈ N | m ≥ X j/i (n)} =X j/i (n) and, since χ j (η j (n)) = n implies η j (x) ≥ y ⇒ x ≥ χ j (y), min{m ∈ N | η j (m + 1) ≥ η i (n)} ≥ min{m ∈ N | m + 1 ≥ (χ j • η i )(n)} = min{m ∈ N | m ≥ X j/i (n) -1} =X j/i (n) -1
The most interesting property of relative counter functions is their transitivity: the relative counter functions X i/j , X i/k and X k/j of any three clocks i, j and k are not independent.

Lemma 5 (Transitivity of relative counter functions). The matrix X of relative counter functions is transitively closed, i.e., for all clocks i, j and k in K

X i/k • X k/j ≤ X i/j ≤ X i/k • (X k/j + 1)
Proof: The proof of the lower bound follows from the fact that function composition is associative and that

(η k • χ k )(t) ≤ t. Thus we derive X i/k • X k/j = χ i • η k • χ k • η j ≤ χ i • η j = X i/j
. The upper bound is proven similarly, but now η k (χ k (t) + 1) ≥ t, and therefore

X i/k (X k/j (n) + 1) = χ i (η k (χ k (η j (n)) + 1)) ≥ χ i (χ j (n)) = X i/j (n).

III. MODELING CLOCK VARIABILITY

Relative counter functions are a first step towards an abstract representation of streams. In this section we introduce bounds as a further abstraction to describe the behavior of clocks. More precisely we introduce two kinds of bounds: (1) clock bounds on the relative clocks to model for example dataflow dependencies between processes; and (2) drift bounds reminiscent of network calculus' curves, to model variability in the availability of resources or arrivals of tasks, for example the (relative) drift of processor's clocks or the availability of resources. We use clock and drift bounds as a finite representation of an infinite number of clock vectors.

A. Clock Bounds

Clock bounds limit the total number of ticks at every tick of another clock, e.g., the upper clock bound C u i/j (n) = m states that at the n-th tick of j, i may have ticked at most m times. For example, the BD component, that describes the availability of the bus and decoders in the examples, is represented by a pair of upper and lower bounds on the relative counter function X r/k as depicted in Figure 5.

Definition 5 (F). Let F be the set of functions f ∈ (N ∪ {∞}) → (N ∪ {∞}) s.t. f (0) = 0 and f is non-decreasing.

F is essentially the set of relative counter functions, extended with limits. Definition 6 (Clock bound matrix C). The matrices C l , C u ∈ F K×K are the lower resp. upper clock bounds of a clock vector χ of clocks K if for all clocks i and j, and n ∈ N,

C l i/j (n) ≤ X i/j (n) ≤ C u i/j (n)
Clock bounds can be used to model general difference bounds such as χ i (t) -χ j (t) ≥ B through C u i/j (n) = B + n as well as relative clock rates such as χ i (t) ≤ Rχ j (t) through C u i/j (n) = Rn, or combinations of both difference bounds and relative rates. Even rates or difference bounds that change over time can be modelled, as long as the behavior is eventually periodic.

In similar work, such as the clock envelopes [START_REF] Cohen | Abstraction of clocks in synchronous data-flow systems[END_REF] and the affine clock calculus [START_REF] Smarandache | Validation of mixed SIGNAL-ALPHA real-time systems through affine calculus on clock synchronisation constraints[END_REF], F is often restricted to linear or convex functions. The bounds in n-synchronous programming [START_REF] Albert Cohen | N-synchronous Kahn networks: a relaxed model of synchrony for real-time systems[END_REF], [START_REF] Cohen | Abstraction of clocks in synchronous data-flow systems[END_REF] including the clock envelope abstraction, have the additional restriction that f (n + 1) -f (n) ≤ 1, because clocks are only compared with their master clock in the clock hierarchy.

C u r/k (n) C u r/k (n) B d C l r/k (n) C l r/k (n) BD(d,

B. Drift Bounds

Clock bounds cannot model time-invariant properties such as a bound on bursts or jitter. For those, we introduce drift bounds. Drift bounds limit the increase of ticks of e.g. X i/j for different intervals of χ j (t). That is, the upper drift bound D u i/j on the relative counter function X i/j requires that i ticks at least D u i/j (∆) times for every ∆ ticks of j. Drift bounds limit the maximum incline for each interval, e.g., a bound D u i/j (∆) = m states that i may tick at most m times, between any ∆ consecutive ticks of j. The constraint imposed by a drift bound can be interpreted as a sliding window constraint, with multiple window-sizes. This allows us to model, for example, the PJD component also depicted in Figure 5, for an event stream that exhibits short term bursts and jitter, but is asymptotically stable. Moreover, it limits the time between each two consecutive events. Definition 7 (Drift bound matrix D). The matrices D l , D u ∈ F K×K is a lower resp. upper drift bound of a clock vector χ of clocks K if for all clocks i and j, n ∈ N, and all interval sizes ∆ ∈ N,

D l i/j (∆) ≤ X i/j (n + ∆) -X j/k (n) ≤ D u i/j (∆)
Although, as we will see in Section V, drift and clock bounds are not completely orthogonal, they capture different properties: clock bounds limit the relative tick count of clocks whereas drift bounds limit the variability of the relative tick count.

To our knowledge drift bounds have no parallel in models for data-flow constraints, they can only be compared to the arrival and resource curves of network calculus. The difference between our drift bounds and the curves of network calculus [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF] is found in the bounded quantity: not the counter functions in χ, but the relative counter functions in X are bounded. Because the domain of a relative counter function X i/j is not real-time but the logical time of η j , the domain of drift bounds is not the set of real-time intervals (t, r] but the set of logical time intervals (χ j (t), χ j (r)].

In the sequel we use (C, D) to denote a pair of lower and upper clock bounds C = (C l , C u ) and drift bounds D = (D l , D u ). We write χ |= (C, D) ("χ satisfies C and D") if the clock vector χ is bounded by the clock bounds C and drift bounds D.

C. Interpreting Bounds

The bounds can be studied to obtain bounds on the maximum number of items in a buffer, or the minimum resource utilisation. For example, in the case of an audio or video decoder we would be interested in three key figures: the maximum buffer occupancy (backlog) for each decoder, the time between arrival of a frame and the decoded result (delay), and the minimum resource utilization (throughput). This paper only considers backlog.

The number of tokens in the buffer is the difference between the number consumed tokens and the number of produced tokens at any time. This difference translates to the more general concept of backlog, which at any time, is the difference χ i (t) -χ o (t) between the number of arrivals at i and the number of departures at o. In the model of relative clocks, this translates to the maximum distance from the identity function, because X j/i (n) gives the number of ticks of the clock j the the n-th tick of i.

Lemma 6 (Backlog bound). Let (C, D) describe the behavior of some system, then the backlog b i/j for any behavior χ |= (C, D) is bounded by

b i/j ≤ max{n -C l j/i (n) | n ∈ N}
Proof: This follows from the observation that the difference χ i (t)-χ j (t) is greatest when i has just ticked, it therefore suffices to observe the difference at each time instant

η t (n) for all n ∈ N. Thus b i/j = max{X i/i (n) -X j/i (n)) | n ∈ R} ≤ max{n -C l j/i (n)) | n ∈ R}.

D. An Algebra of Relative Clock and Drift Bounds

Clock and drift bounds, as well as relative clocks, are ordered by the partial order defined by the point-wise comparison.

Definition 8 (≤). Let ≤ be the partial order over F (Definition 5) such that for all f, g ∈ F

f ≤ g ⇐⇒ ∀n ∈ N : f (n) ≤ g(n)
With the partial order, we also define the point-wise minimum ∧ and maximum ∨ for all f, g ∈ F such that

(f ∨ g)(n) = max(f (n), g(n)) (f ∧ g)(n) = min(f (n), g(n))
The inequality expressing the upper drift bound matrix can be rewritten using the min-plus convolution ⊗ which is defined, for f, g ∈ F as follows

(f ⊗ g)(n) = inf{f (n -∆) + g(∆) | 0 ≤ ∆ ≤ n}
The convolution f ⊗ g is often explained as the minimum of f and g when sliding g over f , i.e., (f ⊗g) = g+f (0)∧g+f (1)∧ g + f (2) ∧ ..., for a more thorough discussion we once again refer to [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF]. In our case, we use the operator to reformulate the upper bound condition without any quantifications:

X ≤ X ⊗ D u
Alternatively, we may rewrite the inequality in the definition, such that h(∆) ≥ f (n + ∆) -h(∆) for any n ∈ N and any interval ∆ ∈ N. This leads to the deconvolution operator, defined as

(f g)(∆) = sup{f (n + ∆) -g(n) | n ∈ N} This enables a third, equivalent expression of the upper bound condition X X ≥ D u
More generally, the deconvolution is the dual of the convolution, i.e, f ≤ g ⊗ h if, and only if, f g ≤ h for f, g, h ∈ F.

For the lower bounds both operators have their analogues in the max-plus convolution ⊗ and deconvolution , where the only difference is the interchange of the infimum and supremum, viz.,

(f ⊗g)(n) = sup{f (n -∆) + g(∆) | 0 ≤ n ≤ ∆} (f g)(n) = inf{f (∆ + n) -g(∆) | ∆ ∈ N}
These operators have many long established properties [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF]. To quickly recapitulate: all operators are associative and order-preserving (or reversing) and convolution, minimum and maximum are commutative and idempotent.

We liberally extend all operators to matrices where the minimum, maximum, convolution and deconvolution are all applied point-wise. For example given the matrices A and B of functions in F

[A ⊗ B] i/j = A i/j ⊗ B i/j
The exception is function composition which acts like matrix multiplication with either the minimum or the maximum as addition, giving for matrices A ∈ F P ×Q and B ∈ F Q×P

[A • B] i/j = {A i/k • B k/j | k ∈ Q}

IV. MODELING STREAM PROCESSING COMPONENTS

We model a system by composing basic components, each of which defines relations between streams. Stream components are connected by equating streams, e.g., the output of the PJD component that generates the multimedia stream is the input stream of the two GPCs that model the decoders. The components presented here are inspired by components of the MPA-RTC toolbox [START_REF] Chakraborty | A general framework for analysing system properties in platform-based embedded system designs[END_REF]. In this section we define the behavior of the components informally introduced above and derive bounds on the relative counter functions.

A. Constant bounds

The simplest bounds are constant bound components PJD, BD and TDMA, that directly model the arrivals of input streams, the availability of a resource or indeed the schedule of a resource shared with a TDMA policy. The constant bound components directly impose bounds. The PJD and BD components have already been introduced in Figure 5.

The TDMA component gives access to a resource according to a static schedule. In our case, access is given to one of two users by a simple periodic schedule. For a TDMA component as depicted below, the first p resource units of resource r are assigned to s, the next p units to r, then again p units to s, etc.

The periodic schedule of a TDMA component can in fact be modelled by clock bounds, as is depicted in Figure 6. The equal upper and lower bounds force the clock s to tick synchronously with r for three ticks, and then pause for the same duration while u is given access, etc. The bounds C u/r can then be defined as the remainder, i.e., C u u/r = C l u/r = id -C u s/r .

B. The greedy processing component

The most important component is the GPC which handles tasks according to the availability of a resource, producing the result as another stream. The GPC processes its input i as soon as resources r are available to produce output o.

GPC i o r

We formalize the behavior of the GPC, introduced in [START_REF] Thiele | Real-time calculus for scheduling hard real-time systems[END_REF], as a predicate over clock vectors. The original definition also provides a stream of remaining resources, which we have left out for simplicity. Definition 9 (GPC). Let GPC(i, o, r) be a predicate over a clock vector with input stream i, output stream o, and resources r, that holds if, and only if,

χ o (t) = min{χ i (u) + χ r (t) -χ r (u) | 0 ≤ u ≤ t}
Lemma 7 (GPC). For all clocks k and all behavior χ such that χ |= (C, D) and GPC(i, o, r)

C l i/r ⊗ id ≤X o/r ≤ C u i/r ⊗ id C l r/i ∧ id ≤X o/i ≤ C u r/i ∧ id
Proof: Let us translate the identity on χ o to an identity on relative counter function X o/r by substituting real-time parameter t for relative time η r (n). Next, we substitute u by η r (∆) which is possible, because the minimum must occur exactly at each tick of r. Finally, X r/r is the identity function.

X o/r (n) = min{χ i (u) + X r/r (n) -χ r (u) | 0 ≤ u ≤ η r (n)} = min{X i/r (∆) + X r/r (n) -X r/r (∆) | 0 ≤ ∆ ≤ n} = min{X i/r (∆) + id (n -∆) | 0 ≤ ∆ ≤ n} =X i/r ⊗ id
The upper and lower bounds then follow by substituting X by C u and C l respectively.

C. The synchronous join component

The purely logical AND component -logical, because it is not dependent on resources -synchronously joins two streams [START_REF] Wandeler | Modular performance analysis and interface-based design for embedded real-time systems[END_REF]. AND x y z Essentially the AND component takes one arriving task of each stream x and y and combines them into a single output task on stream z. Combining the tasks is instantaneous, so the total number of events in the outputs stream at any time is the minimum of the total number of events of the input streams.

Definition 10 (AND). Let AND(x, y, z) denote a predicate over clock vectors with input streams x and y and output stream z, such that it holds if, and only if, χ z (t) = min(χ x (t), χ y (t)).

Lemma 8 (AND)

. For all clocks k ∈ {x, y, z} and all behavior χ such that χ |= (C, D) and AND(x, y, z) holds for χ,

C l x/k ∧ C l y/k ≤ X z/k ≤ C u x/k ∧ C u y/k
Proof: First we derive a relation on relative counter functions by substituting t by η k (n), which yields X z/k = X x/k ∧ X y/k . The upper and lower bounds are then obtained by substituting X by its bounds.

D. The delay component

The DELAY component is a synchronous buffer [START_REF] Albert Cohen | N-synchronous Kahn networks: a relaxed model of synchrony for real-time systems[END_REF] that holds items for a number of ticks, thus it imposes a fixed delay. The following diagram represents the component that delays events of the input stream i for d ticks of the reference clock r resulting in the output clock o.

C l i/r (n -d) ≤ X o/r (n) ≤ C u i/r (n -d) Proof: Substituting t by η r (n) yields X o/r (n) = X i/r (n -d) ≤ C u i/r (n -d) because χ r (η r (n)) = n. V. INTRINSIC BOUND PROPERTIES
In this section, we identify a number of inequalities that are intrinsic properties of drift bounds; properties that hold for any bounds regardless of the modelled system. They arise from interactions between the different bounds. Later on, the properties will serve to find, given some bounds (C, D) more precise bounds (C , D ) that characterize the exact same behaviors. That is, bounds such that χ |= (C, D) ⇐⇒ χ |= (C , D ).

A. Interaction of Lower and Upper Bounds

We use the relation between X i/j and X -1 j/i of Lemma 4, to derive lower bounds C l i/j and D l i/j from the upper bounds C u j/i and D u j/i . This is a natural phenomenon: for example, if the clock i may have ticked at most thrice at the second tick of j, we can also conclude that j must have ticked at least twice at the third tick of i.

Theorem 1. Let (C, D) be a pair of bound matrices, then χ |= (C, D) implies [C u ] -1 ≤ X ≤ [C l ] -1 + 1 and X X ≤ [D l ] -1 + 1 and X X ≥ [D u ] -1
Proof: In case of the clock bounds, this is a straightforward application of Lemma 4. For the drift bounds, one also needs to apply that [f g] -1 ≥ g -1 f -1 and [f g] -1 ≤ g -1 f -1 .

B. Transitivity of Bounds

The next mapping derives directly from the transitivity of relative counter functions. Transitivity propagates bounds through the system.

Theorem 2 (Transitivity of Bounds). Let (C, D) be a pair of bound matrices then χ |= (C, D) implies

C l • C l ≤ X ≤ C u • (C u + 1) X X ≤ D u • (D u + 1) and X X ≥ D l • (D l -1)
Where • is a matrix multiplication with the point-wise minimum as addition for the upper bounds and point-wise maximum for the lower bounds.

Proof: Let K be the set of clocks, then application of 5 and subsequent substitution of X by C u yields X i/j ≤ X i/k • (X k/j + 1) ≤ C u i/k • (C u k/j + 1) for all k ∈ K and χ |= (C, D). Transitivity of the drift bound follows from the semidistributivity of function composition over the deconvolution (f • (g h) ≥ (f • g) (f • h)) and linear w.r.t. addition of a constant ((f + K) g = (f g) + K), viz. X i/j X i/j ≤ X i/k • (X k/j + 1) X i/j • X k/j ≤ X i/k • ((X + 1) X)) = X • ((X X) + 1) ≤ D u • (D u + 1) for all χ |= (C, D). Transitivity for the lower bounds is proven similarly.

C. Drift Bounds Strengthen Clock Bound

The drift bounds limit the incline of any relative counter function, therefore it also has an effect on the clock bound.

D l ⊗ C l ≤ X ≤ C u ⊗ D u
Proof: This is a consequence of the satisfaction criteria, namely that χ |= (C, D) implies X ≤ X ⊗ D u and X ≤ C u . Thus, substituting X for X ⊗ D u and subsequently C u , we have X ≤ X ⊗ D u ≤ C u ⊗ D u . Idem for the lower bound.

D. Clock Bounds strengthen Drift Bound

A drift bound is limited by the maximum incline that is possible for any relative clock that satisfies the clock bounds. In particular, if the upper and lower clock bounds are very close to one another, there is little room for bursts so the drift bound will resemble a straight line.

Theorem 4 (Clock bound on drift bound). Let (C, D) be a pair of bound matrices then χ |= (C, D) implies X X ≤ C u C l and X X ≥ C l C u Proof: This amounts to a simple substitution of X its bounds C l ≤ X ≤ C u , as χ |= (C, D) implies X ≤ C u and, by Lemma 4, X ≥ C l . Note that the deconvolution operator is monotone for its left operant, but antitone for its right operant, therefore we substitute the left operant by the upper bound and the right operant by the upper bound, which yields X X ≤ C u C l . The lower bound is proven analogously.

VI. A FIXPOINT ALGORITHM

The theorems and lemmas derived in the previous two sections all share a common shape: given some behavior delineated by bounds, they compute new bounds for the relative staircase functions and their drift. This section constructs a fixpoint algorithm based on those mappings, that allows us to compute ever tighter bounds and corresponding backlog bounds, for data-flow systems consisting of the introduced components.

Fig. 1 .

 1 Fig.1. The greedy processing components (GPC) model the decoding of the input stream i, arriving periodically with bounded jitter and minimum inter-arrival time (PJD), on two separate processors, utilizing resources r and s with fixed bandwidth and bounded delay (BD), and the AND component joins the decoded streams resulting the output stream o.

Fig. 3 .

 3 Fig.3. Two (partial) counter and corresponding dater functions and the exact times of each tick. Ticks 4 and 2 of respectively i and j occur simultaneously, as do the pairs[START_REF] Harbour | A Practitioner's Handbook for Real-Time Analysis[END_REF][START_REF] Davey | Introduction to Lattices and Order[END_REF], and (10, 7).

Fig. 5 .

 5 Fig. 5.Top: the clock bounds for the resource r resulting from a BD component with bandwidth B and delay d. Bottom: the drift bounds for an event stream o with period p, maximum jitter j and minimum inter-arrival time d.

Fig. 6 .

 6 Fig.6. The clock bound resulting from a TDMA that assigns access to resource r periodically to s with a period of p = 3.

Theorem 3 (

 3 Drift bound on clock bound). Let (C, D) be a pair of bound matrices then χ |= (C, D) implies

  The stream i of update requests passes a bus, represented by resource r, to arrive at a server, which, after a fixed delay (DEL), sends a reply y back over the bus. The resource is shared with a fixed TDMA schedule, over the resources t and s.

			BD
				r
			TDMA
	PJD request	i	GPC t	s	x	DEL server
	response	o	GPC		y
			bus
	Fig. 2.

  Definition 11 (DELAY). Let DELAY(i, o, d, r) denote a predicate over clock vectors with an input stream i, an output stream o and reference clock r, such that it holds if, and only if, χ o (t) = χ i (η r (χ r (t) -d)). For all clock vectors χ such that χ |= (C, D) and DELAY(i, o, d, r) holds for χ

		r
	i	DELAY(d)	o
	Lemma 9.

We have presented a calculus for stream processing systems that preserves correlations between streams. The joint use of clock bounds and drift bounds allows for an expressive modeling of timing constraints, such as bursty behavior and resource scheduling. We have implemented a prototype tool and shown that for some frequently encountered system topologies the proposed calculus yields significantly better estimates than conventional network calculus.

Future work will employ the presented calculus to distribute synchronous (deterministic) data-flow systems over loosely time-triggered architectures [1], so as to guarantee quality of service. We intend to use drift bounds to capture the bounded nondeterminism of communication between independently clocked processors.

A. A lattice of bounds

Informally, bounds (C , D ) are tighter than bounds (C, D) if the bounds (C, D) envelop the bounds (C , D ). The following bound lattice formalizes the tightness relation as a partial order on bounds.

Lemma 10 (Complete bound lattice). The partial order of bounds F ordered by the point-wise comparison ≤ is a complete lattice where the join and meet are the point-wise maximum ∧ and minimum ∨ respectively. The top and bottom ⊥ are then defined such that (0) = 0, (n) = ∞ for n > 0, and ⊥ (n) = 0 for all n ∈ N ∪ {∞}.

The partial order of bounds is extended first to matrices and then to bounds pairs (C, D) by point-wise applications of the comparison. By [START_REF] Davey | Introduction to Lattices and Order[END_REF]

B. Fixpoint of monotonic mappings

Because all mappings are constructed directly from the inequalities in the theorems, they yield the largest bounds that satisfy the inequalities. More precisely, for each equality we define a mapping M over bounds (C, D) and rewrite the inequality such that C l ≤ X ≤ C u , X X ≤ U u and X X ≤ U l for all χ |= (C, D) where (C , D ) = M (C, D). For example, the mapping for a delay delay i, o, d, r (C, D) = (C , D ) is defined as

for all clocks k = o or j = r. This guarantees that (C , D ) are the greatest bounds for which the inequalities of Lemma 9 hold and consequently, that all clock vectors that satisfy the delay predicate and bounds (C, D) satisfy the bounds (C , D ).

The BD, PJD and TDMA components are constant mappings.

The mappings are all order-and limit-preserving for they are compositions of monotonic operators. Proofs of monotonicity and continuity of the involved operators have been omitted but are similar to the proofs in [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF]. The consequence is (see [START_REF] Davey | Introduction to Lattices and Order[END_REF]) that the combined mapping Π(C, D) = (C, D) M 1 (C, D) M 2 (C, D) ... has a unique greatest fix-point where all the inequalities hold. The algorithm used for experimentation (see the next section), iteratively applies Π starting with the top drift bounds.

VII. EXPERIMENTAL RESULTS

We have implemented the mappings and resulting fix-point algorithm in a prototype programmed in Python. At the core, is a suite of operators on functions in F. More precisely, operators on eventually periodic functions that are represented by a finite transient part (the aperiodic introduction) and a periodic part with a finite period. The program consists of a few hundred lines of code, of which more than half is concerned with the operators. The implementation of the operators is based on [START_REF] Bouillard | An Algorithmic Toolbox for Network Calculus[END_REF] and [START_REF] Wandeler | Modular performance analysis and interface-based design for embedded real-time systems[END_REF].

In order to compare to conventional network calculus' analysis both systems were modelled with an additional clock that represented real-time. So all bounds on input streams and availability of resources were modelled with respect to the added real-time clock k.

The multimedia decoder of Figure 1 is described and analysed by the following code. The system consists of a list of mappings over bound matrices that correspond to the predicates introduced for the components in Section IV.

[k,i,x,y,o,r,s] = range(7) # identifiers # declare system components system = [ pjd(i, 4, 24, 1, k), bd(r, 0.3, 3, k), bd(s, 0.3, 3, k), gpc(i, x, r), gpc(i, y, s), and_join(x, y, o), ] bounds = solve(system) # fixpoint calculation print backlog_bound(bounds, x, o) Not visible in the above snippet, are the mappings described by the theorems in Section V, that handle the interaction between the bounds; the interaction between lower on upper bounds, transitivity, and the interaction of drift bounds and clock bound are applied by the solver implicitly because they are independent of the system's components.

The multimedia decoder is modelled with an input stream generated by a PJD component with period of 4, jitter of 24 and a minimum inter-arrival distance of 1. The two decoders had resources, generated by the BD components, with bandwidth of 0.3 units per time-unit and a drift of 3.

We calculate the buffer size using conventional network calculus using the curves for input stream i and resources r, s defined by the PJD and BD components with respect to the real-time clock k, e.g., for stream i the upper arrival input curve is α u i = D u i/k . Then we derive a bound max{α u

x (n) -α l y (n) | n ∈ N} for the buffer size of stream x, where α u x = (α u i ⊗ β u r ) β l r ∧ β u r and α l y = (α l i ⊗ β l s ). In this particular configuration our analysis calculated, in twelve iterations, an upper bound of 8 for the backlog of streams x and y, whereas the conventional method yields a bound of 18. We also confirmed that increasing the jitter of the input stream i has little effect on the estimated buffer size, while the conventional method's estimate grows quickly with jitter. Experiments on the second example, shown below, where a server responds to requests over a bus, showed that the analysis effectively handles the regular nature of requests received over the TDMA bus.

[k,i,x,y,o,r,t,s] = range(8) # identifiers # declare system components system = [ pjd(i, 9, 23, 1, r), bd(r, 0.33, 13, k), tdma(r, t, u, 9), gpc(i, x, t), delay(9, x, y, r), gpc(y, o, u), ] bounds = solve(system) # fixpoint calculation print backlog_bound(bounds, y, o)

Conventional analysis has no straightforward way to model this second example. The closest analysis we could make, again taking the drift bounds for input stream i and resource r, uses β u t = β u s = β u r ⊗tdma u ⊗id where tdma u (n) = 9 n/16 and β l t = β l s = β l r ⊗ tdma l ⊗ id where tdma l (n) = 9 (n+7)/16 for the upper (resp. lower) bounds for the shared bus resources. The delay is modeled according to [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF] such that α u y = α u x ⊗ delay where delay

Then we obtain a buffer size bound max{α u y (n) -β l s (n) | n ∈ N} With a TDMA period of 9 and matching delay our analysis consistently showed, after 14 iterations, a backlog bound of 2 between streams y and o, whereas the backlog bound calculated by the conventional method is 7. Here the improved precision of our approach is due to the combined use of clock and drift bounds.

Clearly conventional analysis has a much lower complexity because we model n streams with n 2 bounds, whereas conventional analysis needs only n bounds. There is room for improvement because the effect of most bounds is local, there is no need to track all n 2 relations; the implementation could exploit system topology to reduce the number of bounds involved in the calculation. It should also be noted that conventional analysis does not need a fix-point computation if there are no cyclic dependencies, as is the case for the examples.

Experience suggests that the computational cost is most affected by the choice of curves. Combining curves with many different prime factors can lead to very long periods, which affects all further operations on the curve.

VIII. DISCUSSION


Simple Authentication Schemes for the Asynchronous Layered Coding (ALC) and NACK-Oriented Reliable Multicast (NORM) Protocols

Keywords: ECC Digital, Group-Keyed, TESLA Message Digest, Elliptic, Algorithm Name [RFC4754], Size, Algorithm

This document introduces four schemes that provide per-packet authentication, integrity, and anti-replay services in the context of the Asynchronous Layered Coding (ALC) and NACK-Oriented Reliable Multicast (NORM) protocols. The first scheme is based on RSA Digital Signatures. The second scheme relies on the Elliptic Curve Digital Signature Algorithm (ECDSA). The third scheme relies on a Groupkeyed Message Authentication Code (MAC). Finally, the fourth scheme merges the Digital Signature and group schemes. These schemes have different target use cases, and they do not all provide the same service.

Introduction

Many applications using multicast and broadcast communications require that each receiver be able to authenticate the source of any packet it receives, to check its integrity. For instance, ALC [START_REF] Luby | Asynchronous Layered Coding (ALC) Protocol Instantiation[END_REF] and NORM [START_REF] Adamson | NACK-Oriented Reliable Multicast (NORM) Transport Protocol[END_REF] are two Content Delivery Protocols (CDPs) designed to reliably transfer objects (e.g., files) between a session's sender and several receivers.

The NORM protocol is based on bidirectional transmissions. With NORM, each receiver acknowledges data received or, in the case of packet erasures, asks for retransmissions. On the contrary, the ALC protocol defines unidirectional transmissions. With ALC, reliability can be achieved by means of cyclic transmissions of the content within a carousel, or by the use of proactive Forward Error Correction (FEC) codes, or by the joint use of these mechanisms. Being purely unidirectional, ALC is massively scalable, while NORM is intrinsically limited in terms of the number of receivers that can be handled in a session. Both protocols have in common the fact that they operate at the application level, on top of an erasure channel (e.g., the Internet) where packets can be lost (erased) during the transmission.

With these CDPs, an attacker might impersonate the ALC or NORM session sender and inject forged packets to the receivers, thereby corrupting the objects reconstructed by the receivers. An attacker might also impersonate a NORM session receiver and inject forged feedback packets to the NORM sender.

In the case of group communications, several solutions exist to provide the receiver some guaranties on the integrity of the packets it receives and on the identity of the sender of these packets. These solutions have different features that make them more or less suited to a given use case: o Digital Signatures [START_REF] Weis | The Use of RSA/SHA-1 Signatures within Encapsulating Security Payload (ESP) and Authentication Header (AH)[END_REF] (see Sections 3 and 4 of this document): This scheme is well suited to low data rate flows, when a packet sender authentication and packet integrity service is needed. However, Digital Signatures based on RSA asymmetric cryptography are limited by high computational costs and high transmission overheads. The use of ECC (Elliptic Curve Cryptography) [START_REF] Mcgrew | Fundamental Elliptic Curve Cryptography Algorithms[END_REF] significantly relaxes these constraints. For instance, the following key lengths provide equivalent security: a 1024-bit RSA key versus a 160-bit ECC key, or a 2048-bit RSA key versus a 224-bit ECC key. However, RSA puts more load on the signer but much less load on the verifier, whereas ECC puts more similar load on both; hence, with many verifiers, more CPU is consumed overall.

Roca Standards Track [Page 4]

All the applications built on top of ALC and NORM directly benefit from the source authentication and packet integrity services defined in this document. For instance, this is the case of the File Delivery over Unidirectional Transport (FLUTE) application [RMT-FLUTE], which is built on top of ALC.

The current specification assumes that several parameters (like keying material) are communicated out-of-band, sometimes securely, between the sender and the receivers. This is detailed in Sections 3.2, 4.2, 5.2, and 6.2.

1.1. Scope of This Document [START_REF] Roca | Use of Timed Efficient Stream Loss-Tolerant Authentication (TESLA) in the Asynchronous Layered Coding (ALC) and NACK-Oriented Reliable Multicast (NORM) Protocols[END_REF] explains how to use TESLA in the context of the ALC and NORM protocols.

The current document specifies the use of the Digital Signature based on RSA asymmetric cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA), and Group-keyed MAC schemes. The current document also specifies the joint use of Digital Signature and Group-keyed MAC schemes.

Unlike the TESLA scheme, this specification considers the authentication/integrity of the packets generated by the session's sender as well as those generated by the receivers (NORM).

Terminology, Notations, and Definitions

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. o n_m is the length of the truncated output of the MAC [RFC2104].

Only the n_m leftmost bits (most significant bits) of the MAC output are kept.

Authentication Scheme Identification with the ASID Field

As mentioned in Section 1, several authentication schemes MAY be used in the same ALC or NORM session, even on the same communication path (i.e., from a sender to a receiver, or vice versa). All the schemes mentioned in Section 1 (some of which are specified in this document) use the same HET=1 (EXT_AUTH) Authentication Header extension mechanism defined in [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF]. Therefore, the same 4-bit ASID field has been reserved in all the specifications (see Sections 3.1, 4.1, 5.1, and 6.1, as well as Section 5.1 of [START_REF] Roca | Use of Timed Efficient Stream Loss-Tolerant Authentication (TESLA) in the Asynchronous Layered Coding (ALC) and NACK-Oriented Reliable Multicast (NORM) Protocols[END_REF]). For a given ALC or NORM session, the ASID value contained in an incoming packet enables a receiver to differentiate the actual use and format of the contents of the HET=1 (EXT_AUTH) header extension.

Roca Standards Track [Page 7]

The association between the ASID value and the actual authentication scheme of a given ALC or NORM session is defined at session startup and communicated to all the session members by an out-of-band mechanism. This association is per ALC or NORM session, and different sessions MAY reuse the same ASID values for different authentication schemes.

With ALC, the ASID value is scoped by the {sender IP address; Transport Session Identifier (TSI)} tuple [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF] that fully identifies an ALC session. Since [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF] requires that "the TSI MUST be unique among all sessions served by the sender during the period when the session is active, and for a large period of time preceding and following when the session is active", there is no risk of confusion between different sessions. This is in line with Section 7.2.3.

With NORM, there is no session identifier within NORM packets. Therefore, depending on whether an Any Source Multicast (ASM) or Source Specific Multicast (SSM) group communication is used, the ASID value is scoped either by the {destination multicast address; destination port number} or {source IP address; destination multicast address; destination port number} tuple that fully identifies a NORM session [START_REF] Adamson | NACK-Oriented Reliable Multicast (NORM) Transport Protocol[END_REF]. Care should be taken that the above tuples remain unique, within a given scope and for a sufficient period of time preceding, during, and following when the session is active, to avoid confusion between different sessions. However, this is a recommendation for NORM sessions, rather than something specific to an authentication scheme. Note also that the ASID value is not scoped by the {source_id; instance_id} tuple, which uniquely identifies a host's participation in a NORM session, rather than the session itself (Section 7.2.2).

In any case, because this ASID field is 4 bits long, there is a maximum of 16 authentication schemes per ALC or NORM session.

3. RSA Digital Signature Scheme

Authentication Header Extension Format

The integration of Digital Signatures is similar in ALC and NORM and relies on the header extension mechanism defined in both protocols. More precisely, this document details the HET=1 (EXT_AUTH) header extension defined in [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF].

Roca Standards Track [Page 8]

Several fields are added, in addition to the HET (Header Extension Type) and HEL (Header Extension Length) fields (Figure 1). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The ASID identifies the source authentication scheme or protocol in use. The association between the ASID value and the actual authentication scheme is defined out-of-band, at session startup.

rsvd (Reserved) (3 bits):

This is a reserved field that MUST be set to zero and ignored by receivers.

AR (anti-replay) (1 bit):

The AR field, when set to 0, indicates that the anti-replay service is not used. When set to 1, it indicates that the anti-replay service is used.

SN (Sequence Number) (8 or 40 bits):

The SN field contains an optional Sequence Number. When AR = 0, this is an 8-bit field that MUST be set to zero. No anti-replay mechanism is used in that case. When AR = 1, this is a 40-bit field (32 bits + 8 bits), and all of the 40 bits MUST be considered by the anti-replay mechanism.

Roca Standards Track [Page 9]

Signature (variable size, multiple of 32 bits):

The Signature field contains a Digital Signature of the message.

If need be, this field is padded (with 0) up to a multiple of 32 bits.

Parameters

Several parameters MUST be initialized by an out-of-band mechanism.

The sender or group controller o MUST communicate its public key, for each receiver to be able to verify the signature of the packets received. For security reasons [START_REF] Ramsdell | Secure/Multipurpose Internet Mail Extensions (S/MIME) Version 3.2 Message Specification[END_REF], the use of key sizes between 1024 and 2048 bits inclusive is RECOMMENDED. Key sizes inferior to 1024 bits SHOULD NOT be used. Key sizes above 2048 bits MAY be used. As a side effect, the receivers also know the key length and the signature length, the two parameters being equal;

o MAY communicate a certificate (which also means that a PKI has been set up), for each receiver to be able to check the sender's public key;

o MUST communicate the signature-encoding algorithm. For instance, [START_REF] Jonsson | Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1[END_REF] defines the RSASSA-PKCS1-v1_5 and RSASSA-PSS algorithms that are usually used for that purpose;

o MUST communicate the One-way Hash Function --for instance, SHA-1, SHA-224, SHA-256, SHA-384, or SHA-512. Because of security threats on SHA-1, the use of SHA-256 is RECOMMENDED [START_REF] Polk | Security Considerations for the SHA-0 and SHA-1 Message-Digest Algorithms[END_REF];

o MUST associate a value to the ASID field of the EXT_AUTH header extension (Section 3.1); o MUST communicate whether or not the anti-replay service is used for this session.

These parameters MUST be communicated to all receivers before they can authenticate the incoming packets. For instance, it can be communicated in the session description, or initialized in a static way on the receivers, or communicated by means of an appropriate protocol. The details of this out-of-band mechanism are beyond the scope of this document.

Roca Standards Track [Page 10]

3.3. Processing

Signature Processing

The computation of the Digital Signature, using the private key, MUST include the ALC or NORM header (with the various header extensions) and the payload when applicable. The UDP/IP/MAC headers MUST NOT be included. During this computation, the Signature field MUST be set to 0.

Several signature-encoding algorithms can be used, including RSASSA-PKCS1-v1_5 and RSASSA-PSS. With these encodings, several one-way hash functions can be used, like SHA-256.

First, let us consider a packet sender. More specifically, as noted in [START_REF] Weis | The Use of RSA/SHA-1 Signatures within Encapsulating Security Payload (ESP) and Authentication Header (AH)[END_REF], Digital Signature generation is performed as described in Section 8.2.1 of [START_REF] Jonsson | Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1[END_REF] (RSASSA-PKCS1-v1_5) and in Section 8.1.1 of [START_REF] Jonsson | Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1[END_REF] (RSASSA-PSS). The authenticated portion of the packet is used as the message M, which is passed to the signature generation function. The signer's RSA private key is passed as K. In summary (when SHA-256 is used), the signature generation process computes a SHA-256 hash of the authenticated packet bytes, signs the SHA-256 hash using the private key, and encodes the result with the specified RSA encoding type. This process results in a value S, which is the Digital Signature to be included in the packet.

With RSASSA-PKCS1-v1_5 and RSASSA-PSS signatures, the size of the signature is equal to the "RSA modulus", unless the RSA modulus is not a multiple of 8 bits. In that case, the Digital Signature (also called the Integrity Check Value (ICV) in [START_REF] Weis | The Use of RSA/SHA-1 Signatures within Encapsulating Security Payload (ESP) and Authentication Header (AH)[END_REF]) MUST be prepended with between 1 and 7 bits set to zero such that the Digital Signature is a multiple of 8 bits [START_REF] Weis | The Use of RSA/SHA-1 Signatures within Encapsulating Security Payload (ESP) and Authentication Header (AH)[END_REF]. The key length, which in practice is also equal to the RSA modulus, has major security implications. [START_REF] Weis | The Use of RSA/SHA-1 Signatures within Encapsulating Security Payload (ESP) and Authentication Header (AH)[END_REF] explains how to choose this value, depending on the maximum expected lifetime of the session. This choice is beyond the scope of this document. validates that the appropriate encoding was applied. The two SHA-256 hashes are compared, and if they are identical, the validation is successful.

Anti-Replay Processing

Let us assume the anti-replay service is used. The principles are similar to the Sequence Number mechanism described in [START_REF] Kent | IP Encapsulating Security Payload (ESP)[END_REF], with the exception that the present document uses a 40-bit field that contains all the bits of the Sequence Number counter.

At the sender, the mechanism works as follows (Section 2.2 of [START_REF] Kent | IP Encapsulating Security Payload (ESP)[END_REF]). The sender's Sequence Number counter is initialized to 0 at session startup. The sender increments the Sequence Number counter for this session and inserts the value into the SN field. Thus, the first packet sent will contain an SN of 1. The SN value of the Authentication Header extension MUST be initialized before the signature generation process, in order to enable a receiver to check the SN value during the integrity verification process.

The sender SHOULD ensure that the counter does not cycle before inserting the new value in the SN field. Failing to follow this rule would enable an attacker to replay a packet sent during the previous cycle; i.e., it would limit the anti-replay service to a single SN cycle. Since the Sequence Number is contained in a 40-bit field, it is expected that cycling will never happen in most situations. For instance, on a 10-Gbps network, with small packets (i.e., 64 bytes long), cycling will happen after slightly more than 15 hours.

At the receiver, the mechanism works as follows (Section 3.4.3 and Appendix A2 of [START_REF] Kent | IP Encapsulating Security Payload (ESP)[END_REF]). For each received packet, the receiver MUST verify that the packet contains a Sequence Number that does not duplicate the Sequence Number of any other packets received during the session. If this preliminary check fails, the packet is discarded, thus avoiding the need for any cryptographic operations by the receiver. If the preliminary check is successful, the receiver cannot yet modify its local counter, because the integrity of the Sequence Number has not been verified at this point.

Duplicates are rejected through the use of a sliding receive window.

The "right" edge of the window represents the highest, validated Sequence Number value received on this session. Packets that contain Sequence Numbers lower than the "left" edge of the window are rejected. Packets falling within the window are checked against a list of received packets within the window (how this list is managed is a local, implementation-based decision). This window limits how far out of order a packet can be, relative to the packet with the highest Sequence Number that has been authenticated so far.

Roca Standards Track [Page 12]

If the received packet falls within the window and is not a duplicate, or if the packet is to the right of the window, then the receiver proceeds to integrity verification. If the integrity check fails, the receiver MUST discard the received packet as invalid; otherwise, the receive window is updated and packet processing continues.

In Practice

Each packet sent MUST contain exactly one Digital Signature EXT_AUTH header extension. A receiver MUST drop all the packets that do not contain a Digital Signature EXT_AUTH header extension.

All receivers MUST recognize EXT_AUTH but might not be able to parse its content, for instance, because they do not support Digital Signatures. In that case, the Digital Signature EXT_AUTH header extension is ignored.

If the anti-replay mechanism is used, each packet sent MUST contain a valid Sequence Number. All the packets that fail to contain a valid Sequence Number MUST be immediately dropped.

For instance, Figure 2 shows the Digital Signature EXT_AUTH header extension when using 128-byte (1024-bit) key Digital Signatures (which also means that the Signature field is 128 bytes long). The Digital Signature EXT_AUTH header extension is then 132 bytes long. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This document focuses on the Elliptic Curve Digital Signature Algorithm (ECDSA). However, [START_REF] Mcgrew | Fundamental Elliptic Curve Cryptography Algorithms[END_REF] describes alternative elliptic curve techniques, like KT-I signatures. The use of such alternatives is not considered in this document, but may be added in the future.

Authentication Header Extension Format

The integration of ECC Digital Signatures is similar to that of RSA Digital Signatures. Several fields are added, in addition to the HET and HEL fields, as illustrated in Figure 1.

The fields of the Digital Signature EXT_AUTH header extension are as follows:

ASID (4 bits):

The ASID identifies the source authentication scheme or protocol in use. The association between the ASID value and the actual authentication scheme is defined out-of-band, at session startup.

rsvd (3 bits):

This is a reserved field that MUST be set to zero and ignored by receivers.

AR (1 bit):

The AR field, when set to 0, indicates that the anti-replay service is not used. When set to 1, it indicates that the anti-replay service is used.

SN (8 or 40 bits):

The SN field contains an optional Sequence Number. When AR = 0, this is an 8-bit field that MUST be set to zero. No anti-replay mechanism is used in that case. When AR = 1, this is a 40-bit field (32 bits + 8 bits), and all of the 40 bits MUST be considered by the anti-replay mechanism.

Signature (variable size, multiple of 32 bits):

The Signature field contains a Digital Signature of the message.

If need be, this field is padded (with 0) up to a multiple of 32 bits. These parameters MUST be communicated to all receivers before they can authenticate the incoming packets. For instance, it can be communicated in the session description, or initialized in a static way on the receivers, or communicated by means of an appropriate protocol. The details of this out-of-band mechanism are beyond the scope of this document.

Processing

Signature Processing

The computation of the ECC Digital Signature, using the private key, MUST include the ALC or NORM header (with the various header extensions) and the payload when applicable. The UDP/IP/MAC headers MUST NOT be included. During this computation, the Signature field MUST be set to 0.

Several elliptic curve groups can be used, as well as several hash algorithms. In practice, both choices are related, and there is a minimum hash algorithm size for any key length. Using a larger hash algorithm and then truncating the output is also feasible; however,

Anti-Replay Processing

The anti-replay processing follows the principles described in Section 3.3.2.

In Practice

Each packet sent MUST contain exactly one ECC Digital Signature EXT_AUTH header extension. A receiver MUST drop all the packets that do not contain an ECC Digital Signature EXT_AUTH header extension.

All receivers MUST recognize EXT_AUTH but might not be able to parse its content, for instance, because they do not support ECC Digital Signatures. In that case, the Digital Signature EXT_AUTH header extension is ignored.

If the anti-replay mechanism is used, each packet sent MUST contain a valid Sequence Number. All the packets that fail to contain a valid Sequence Number MUST be immediately dropped.

Roca Standards Track [Page 16]

For instance, Figure 3 shows the Digital Signature EXT_AUTH header extension when using ECDSA-256 (256-bit) ECC Digital Signatures. The ECC Digital Signature EXT_AUTH header extension is then 36 bytes long. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HET (=1) | HEL (=9) | ASID | 0 |0| 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --

| | ^ 3 + + | 2 . . | . Signature (32 bytes) . | b . . | y | | | t + + | e | | v s +-

Authentication Header Extension Format

The integration of Group-keyed MAC is similar in ALC and NORM and relies on the header extension mechanism defined in both protocols. More precisely, this document details the HET=1 (EXT_AUTH) header extension defined in [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF].

Roca Standards Track [Page 17]

Several fields are added, in addition to the HET and HEL fields (Figure 4). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 The ASID identifies the source authentication scheme or protocol in use. The association between the ASID value and the actual authentication scheme is defined out-of-band, at session startup.

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

rsvd (3 bits):

This is a reserved field that MUST be set to zero and ignored by receivers.

AR (1 bit):

The AR field, when set to 0, indicates that the anti-replay service is not used. When set to 1, it indicates that the anti-replay service is used.

SN (8 or 40 bits):

The SN field contains an optional Sequence Number. When AR = 0, this is an 8-bit field that MUST be set to zero. No anti-replay mechanism is used in that case. When AR = 1, this is a 40-bit field (32 bits + 8 bits), and all of the 40 bits MUST be considered by the anti-replay mechanism.

Roca Standards Track [Page 18]

RFC 6584

Simple Authentication for ALC and NORM April 2012

Group-keyed MAC (variable size, multiple of 32 bits):

The Group-keyed MAC field contains a truncated Group-keyed MAC of the message. If need be, this field is padded (with 0) up to a multiple of 32 bits.

Parameters

Several parameters MUST be initialized by an out-of-band mechanism. o MUST communicate whether or not the anti-replay service is used for this session.

These parameters MUST be communicated to all receivers before they can authenticate the incoming packets. For instance, it can be communicated in the session description, or initialized in a static way on the receivers, or communicated by means of an appropriate protocol (this will often be the case when periodic re-keying is required). The details of this out-of-band mechanism are beyond the scope of this document.

Roca Standards Track [Page 19]

5.3. Processing

Signature Processing

The computation of the Group-keyed MAC, using the group key, includes the ALC or NORM header (with the various header extensions) and the payload when applicable. The UDP/IP/MAC headers are not included. During this computation, the weak Group-keyed MAC field MUST be set to 0. Then, the sender truncates the MAC output to keep the n_m most significant bits and stores the result in the Group-keyed MAC Authentication Header.

Upon receiving this packet, the receiver computes the Group-keyed MAC, using the group key, and compares it to the value carried in the packet. During this computation, the Group-keyed MAC field MUST also be set to 0. If the check fails, the packet MUST be immediately dropped.

[RFC2104] explains that it is current practice to truncate the MAC output, on condition that the truncated output length, n_m, be not less than half the length of the hash and not less than 80 bits. However, this choice is beyond the scope of this document.

Anti-Replay Processing

The anti-replay processing follows the principles described in Section 3.3.2.

In Practice

Each packet sent MUST contain exactly one Group-keyed MAC EXT_AUTH header extension. A receiver MUST drop packets that do not contain a Group-keyed MAC EXT_AUTH header extension.

All receivers MUST recognize EXT_AUTH but might not be able to parse its content, for instance, because they do not support Group-keyed MAC. In that case, the Group-keyed MAC EXT_AUTH extension is ignored.

If the anti-replay mechanism is used, each packet sent MUST contain a valid Sequence Number. All the packets that fail to contain a valid Sequence Number MUST be immediately dropped.

Roca Standards Track [Page 20]

Several fields are added, in addition to the HET and HEL fields (Figure 6). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

+-+-+ | HET (=1) | HEL | ASID | rsvd|A| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+R+ + |
anti-replay Sequence Number (SN) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6: Format of the Group-Keyed MAC EXT_AUTH Header Extension

+-+-+ | | ˜ ˜ | Signature | + +-+-+-+-+-+-+-+-+ | | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Group-keyed MAC | ˜ ˜ +-
The fields of the Group-keyed MAC EXT_AUTH header extension are as follows:

ASID (4 bits):

The ASID identifies the source authentication scheme or protocol in use. The association between the ASID value and the actual authentication scheme is defined out-of-band, at session startup.

rsvd (3 bits):

This is a reserved field that MUST be set to zero and ignored by receivers.

AR (1 bit):

The AR field MUST be set to 1, indicating that the anti-replay service is used (see Section 6.3).

SN (8 or 40 bits):

The SN field contains a Sequence Number. Since AR = 1, this is a 40-bit field (32 bits + 8 bits), and all of the 40 bits MUST be considered by the anti-replay mechanism.

Roca Standards Track [Page 22]

Signature (variable size, multiple of 32 bits):

The Signature field contains a Digital Signature of the message.

If need be, this field is padded (with 0) up to a multiple of 32 bits.

Group-keyed MAC (variable size, multiple of 32 bits, by default 32 bits):

The Group-keyed MAC field contains a truncated Group-keyed MAC of the message.

Parameters

Several parameters MUST be initialized by an out-of-band mechanism, as defined in Sections 3.2, 4.2, and 5.2.

Processing

In some situations, it can be interesting to use both authentication schemes. The goal of the Group-keyed MAC is to mitigate denial-ofservice (DoS) attacks coming from attackers that are not group members [START_REF] Perrig | Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction[END_REF], by adding a light authentication scheme as a front-end.

Signature Processing

Before sending a message, the sender sets the Signature field and Group-keyed MAC field to zero. Then, the sender computes the signature as detailed in Section 3.3 or in Section 4.3 and stores the value in the Signature field. Then, the sender computes the Group-keyed MAC as detailed in Section 5.3 and stores the value in the Group-keyed MAC field. The (RSA or ECC) Digital Signature value is therefore protected by the Group-keyed MAC, which avoids DoS attacks where the attacker corrupts the Digital Signature itself.

Upon receiving the packet, the receiver first checks the Group-keyed MAC, as detailed in Section 5.3. If the check fails, the packet MUST be immediately dropped. Otherwise, the receiver checks the Digital Signature, as detailed in Section 3.3. If the check fails, the packet MUST be immediately dropped. o It increases the size of the Authentication Headers. In order to limit this problem, the length of the truncated output of the MAC, n_m, SHOULD be kept small (see Section 9.5 of [START_REF] Baugher | The Secure Real-time Transport Protocol (SRTP)[END_REF]). In the current specification, n_m MUST be a multiple of 32 bits, and the default value is 32 bits. As a side effect, with n_m = 32 bits, the authentication service is significantly weakened, since the probability that any packet would be successfully forged is one in 2^32. Since the Group-keyed MAC check is only a pre-check that is followed by the standard signature authentication check, this is not considered to be an issue.

For a given use case, the benefits brought by the Group-keyed MAC must be balanced against these limitations.

Anti-Replay Processing

The anti-replay processing follows the principles described in Section 3.3.2. Here, an anti-replay service MUST be used. Indeed, failing to enable anti-replay protection would facilitate DoS attacks, since all replayed (but otherwise valid) packets would pass the light authentication scheme and oblige a receiver to perform a complex signature verification.

In Practice

Each packet sent MUST contain exactly one combined Digital Signature/ Group-keyed MAC EXT_AUTH header extension. A receiver MUST drop packets that do not contain a combined Digital Signature/Group-keyed MAC EXT_AUTH header extension.

All receivers MUST recognize EXT_AUTH but might not be able to parse its content, for instance, because they do not support combined Digital Signature/Group-keyed MAC. In that case, the combined Digital Signature/Group-keyed MAC EXT_AUTH extension is ignored.

Since the anti-replay mechanism MUST be used, each packet sent MUST contain a valid Sequence Number. All the packets that fail to contain a valid Sequence Number MUST be immediately dropped.

Roca Standards Track [Page 24]

significantly faster than checking a Digital Signature, there are practical limits on how many Group-keyed MACs can be checked per time unit. Therefore, it is RECOMMENDED that limiting the number of authentication checks per time unit be done when the number of incoming packets that fail the authentication check exceeds a given threshold (i.e., in the case of a DoS attack).

The RECOMMENDED action of limiting the number of checks per time unit under (presumed) attack situations can be extended to the other authentication schemes.

Dealing with Replay Attacks

Replay attacks involve an attacker storing a valid message and replaying it later. It is RECOMMENDED that the anti-replay service defined in this document be used with the signature and Group-keyed MAC solutions, and this anti-replay service MUST be used in the case of a combined use of signatures and Group-keyed MAC schemes (see Section 6.3.2).

The following section details some of the potential consequences of not using anti-replay protection.

Impacts of Replay Attacks on the Simple Authentication Schemes

Since all the above authentication schemes are stateless, replay attacks have no impact on these schemes.

Impacts of Replay Attacks on NORM

In this subsection, we review the potential impacts of a replay attack on the NORM component. Note that we do not consider here the protocols that could be used along with NORM --for instance, congestion control protocols.

First, let us consider replay attacks within a given NORM session.

As NORM is a stateful protocol, replaying a packet may have consequences.

NORM defines a "sequence" field that may be used to protect against replay attacks [RFC5740] within a given NORM session. This sequence field is a 16-bit value that is set by the message originator (sender or receiver) as a monotonically increasing number incremented with each NORM message transmitted. Using this field for anti-replay protection would be possible if there is no wrapping to zero, i.e., would only be possible if at most 65535 packets are sent; this may be true for some use cases but not for the general case. Using this

Roca Standards Track [Page 26]

field for anti-replay protection would also be possible if the keying material is updated before wrapping to zero happens; this may be true for some use cases but not for the general case. Now, let us consider replay attacks across several NORM sessions. A host participating in a NORM session is uniquely identified by the {source_id; instance_id} tuple. Therefore, when a given host participates in several NORM sessions, it is RECOMMENDED that instance_id be changed for each NORM instance. It is also RECOMMENDED, when the Group-keyed MAC authentication/integrity check scheme is used, that the shared group key be changed across sessions. Therefore, NORM can be made robust when confronted with replay attacks across different sessions.

Impacts of Replay Attacks on ALC

In this subsection, we review the potential impacts of a replay attack on the ALC component. Note that we do not consider here the protocols that could be used along with ALC --for instance, layered or wave-based congestion control protocols.

First, let us consider replay attacks within a given ALC session:

o Replayed encoding symbol: A replayed encoding symbol (coming from a replayed data packet) is detected, thanks to the object/block/ symbol identifiers, and is silently discarded.

o Replayed control information:

* At the end of the session, a "close session" (A flag) packet is sent. Replaying a packet containing this flag has no impact, since the receivers have already left the session.

* Similarly, replaying a packet containing a "close object" (B flag) has no impact, since this object is probably already marked as closed by the receiver.

* Timing information sent as part of a Layered Coding Transport (LCT) EXT_TIME header extension [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF] may be more sensitive to replay attacks. For instance, replaying a packet containing an ERT (Expected Residual Time) may mislead a receiver to believe an object transmission will continue for some time whereas the transmission of symbols for this object is about to stop. Replaying a packet containing a Sender Current Time (SCT) is easily identified if the receiver verifies that time progresses upon receiving such EXT_TIME header extensions.

Roca Standards Track [Page 27]

Replaying a packet containing a Session Last Changed (SLC) is easily identified if the receiver verifies the chronology upon receiving such EXT_TIME header extensions.

This analysis shows that ALC might be, to a limited extent, sensitive to replay attacks within the same session if timing information is used. Otherwise, ALC is robust when confronted with replay attacks within the same session. Now, let us consider replay attacks across several ALC sessions. An ALC session is uniquely identified by the {sender IP address; TSI} tuple. Therefore, when a given sender creates several sessions, the TSI MUST be changed for each ALC session, so that each TSI is unique among all active sessions of this sender and for a long period of time preceding and following when the session is active [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF]. Therefore, ALC can be made robust when confronted with replay attacks across different sessions. Of course, when the Group-keyed MAC authentication/integrity check scheme is used, the shared group key SHOULD be changed across sessions if the set of receivers changes.

Dealing with Attacks on the Parameters Sent Out-of-Band

This specification requires that several parameters be communicated to the receiver(s) via an out-of-band mechanism that is beyond the scope of this document. This is in particular the case for the mapping between an ASID value and the associated authentication scheme (Section 1). Since this mapping is critical, this information SHOULD be carried in a secure way from the sender to the receiver(s).

Acknowledgments

The author is grateful to the authors of [START_REF] Kent | IP Encapsulating Security Payload (ESP)[END_REF], [START_REF] Weis | The Use of RSA/SHA-1 Signatures within Encapsulating Security Payload (ESP) and Authentication Header (AH)[END_REF], [START_REF] Fu | IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)[END_REF], and [START_REF] Turner | Elliptic Curve Cryptography Subject Public Key Information[END_REF]; their documents inspired several sections of the present document. The author is also grateful to all the IESG members, and in particular to David Harrington, Stephen Farrell, and Sean Turner for their very detailed reviews.

Figure 1 :

 1 Figure 1: Format of the Digital Signature EXT_AUTH Header Extension The fields of the Digital Signature EXT_AUTH header extension are as follows: ASID (4 bits):

  Figure 2: Example: Format of the Digital Signature EXT_AUTH Header Extension Using 1024-Bit Signatures, without Any Anti-Replay Protection

-Figure 3 :

 3 Figure 3: Example: Format of the ECC Digital Signature EXT_AUTH Header Extension Using ECDSA-256 Signatures, without Any Anti-Replay Protection 5. Group-Keyed Message Authentication Code (MAC) Scheme

Figure 4 :

 4 Figure 4: Format of the Group-Keyed MAC EXT_AUTH Header ExtensionThe fields of the Group-keyed MAC EXT_AUTH header extension are as follows:ASID (4 bits):

  MUST communicate the length of the truncated output of the MAC, n_m, which depends on the Cryptographic MAC Function chosen. Only the n_m leftmost bits (most significant bits) of the MAC output are kept. Of course, n_m MUST be less than or equal to the key length;

	The sender or group controller
	o MUST communicate the Cryptographic MAC Function --for instance,
	HMAC-SHA-1, HMAC-SHA-224, HMAC-SHA-256, HMAC-SHA-384, or
	HMAC-SHA-512. As a side effect, with these functions, the
	receivers also know the key length and the non-truncated MAC
	output length. Because of security threats on SHA-1, the use of
	HMAC-SHA-256 is RECOMMENDED [RFC6194];
	o

o MUST communicate the group key to the receivers, confidentially, before starting the session. This key might have to be periodically refreshed for improved robustness;

o MUST associate a value to the ASID field of the EXT_AUTH header extension (Section 5.1);

 -----------------+-------------+-------------+---

For instance, Figure 5 shows the Group-keyed MAC EXT_AUTH header extension when using HMAC-SHA-256. The Group-keyed MAC EXT_AUTH header extension is then 16 bytes long. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5: Example: Format of the Group-Keyed MAC EXT_AUTH Header Extension Using HMAC-SHA-256, without Any Anti-Replay Protection 6. Combined Use of the RSA/ECC Digital Signatures and Group-Keyed MAC Schemes

Authentication Header Extension Format

The integration of combined RSA/ECC Digital Signatures and Group-keyed MAC schemes is similar in ALC and NORM and relies on the header extension mechanism defined in both protocols. More precisely, this document details the HET=1 (EXT_AUTH) header extension defined in [START_REF] Luby | Layered Coding Transport (LCT) Building Block[END_REF].

Roca Standards Track [Page 21]

It is RECOMMENDED that the n_m parameter of the group authentication scheme be small, and by default equal to 32 bits (Section 6.3).

For instance, Figure 7 shows the combined Digital Signature/ Group-keyed MAC EXT_AUTH header extension when using 128-byte (1024-bit) key RSA Digital Signatures (which also means that the Signature field is 128 bytes long). The EXT_AUTH header extension is then 140 bytes long. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | anti-replay Sequence Number (SN) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

s +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---|

Group-keyed MAC (32 bits) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --- Let us consider packets secured through the use of a Digital Signature scheme first. Because faked packets are easy to create but checking them requires computation of a costly Digital Signature, this scheme introduces new opportunities for an attacker to mount DoS attacks. More precisely, an attacker can easily saturate the processing capabilities of the receiver.

In order to mitigate these attacks, it is RECOMMENDED that the combined Digital Signature/Group-keyed MAC scheme (Section 6.3) be used. However, no mitigation is possible if a group member acts as an attacker. Additionally, even if checking a Group-keyed MAC is