{'fraction_non_alphanumeric': 0.04092558180691974, 'fraction_numerical': 0.0035395097778957614, 'mean_word_length': 4.352356144920672, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Network Coding in the Presence of Untrusted Nodes

While network coding can be an efficient means of information dissemination in networks, it is highly susceptible to"pollution attacks,"as the injection of even a single erroneous packet has the potential to corrupt each and every packet received by a given destination. Even when suitable error-control coding is applied, an adversary can, in many interesting practical situations, overwhelm the error-correcting capability of the code. To limit the power of potential adversaries, a broadcast transformation is introduced, in which nodes are limited to just a single (broadcast) transmission per generation. Under this broadcast transformation, the multicast capacity of a network is changed (in general reduced) from the number of edge-disjoint paths between source and sink to the number of internally-disjoint paths. Exploiting this fact, we propose a family of networks whose capacity is largely unaffected by a broadcast transformation. This results in a significant achievable transmission rate for such networks, even in the presence of adversaries.


I. INTRODUCTION
Network coding [1] is a promising approach for efficient information dissemination in packet networks. Network coding generalizes routing, allowing nodes in the network not only to switch packets from input ports to output ports, but also to combine incoming packets in some manner to form outgoing packets. For example, in linear network coding, fixed-length packets are regarded as vectors over a finite field F q , and nodes in the network form outgoing packets as F q -linear combinations of incoming packets. For the single-source multicast problem, it is known that linear network coding suffices to achieve the network capacity [2], [3].
attacks can be catastrophic. Indeed, the injection of even a single erroneous packet somewhere in the network has the potential to corrupt each and every packet received by a given sink node. This problem was first investigated from an edgecentric perspective [4], where a number of packet errors could arise in any of the links in the network. Alternatively, under a node-centric perspective, it is assumed that an adversarial node may join the network and transmit corrupt packets on all its outgoing links, but the other links in the network remain free of error.
One approach, investigated in [5], [6], for dealing with the pollution problem is to apply cryptographic techniques to ensure the validity of received packets, permitting corrupted packets to be discarded by each node, and therefore preventing the contamination of other packets. This approach typically requires the use of large field and packet sizes, which leads to computationally expensive operations at the nodes and possibly to significant transmission delay. These requirements may be acceptable in the large-file-downloading scenario, but may be incompatible with delay-constrained applications such as streaming-media distribution.
Another approach (and the one followed in this paper) is to look for end-to-end coding techniques that require little or no intelligence at the internal nodes. Jaggi et al. [7] show that, if C is the network capacity (per transmission-generation) and z is the min-cut from the adversary to a destination, then a rate of C − 2z packets per generation is achievable. The same rate can also be achieved using the subspace approach introduced by Kötter and Kschischang [8], [9]. A higher rate C − z can be achieved using a scheme proposed in [7] (see also [10]) if the source and sink nodes are allowed to share a secret (i.e., if they have common information not available to the adversary).
In all of the end-to-end techniques mentioned above, we observe that the min-cut from the adversary to a sink node has a significant impact on the achievable rates. If z is large-for instance, if z = C-then the adversary can jam the network with no hope of recovery. It is important, therefore, to conceive of protocols that induce per-generation network topologies that can perform well, even in the presence of adversaries.
The central question of this paper is the following: In this paper, we introduce the concept of a broadcast transformation, which essentially constrains potential adversaries to sending the same packet on all its outgoing links. In the case of a single malicious node, this effectively enforces z = 1. In order for such a transformation to be possible, we introduce the concept of a trusted node that performs the role of broadcasting traffic. A beneficial side-effect of a broadcast transformation is to lower the encoding complexity, since each node only needs to compute a single outgoing packet in each round of communication.
In practice, such a broadcasting feature could be implemented at trusted network gateways. For example, in overlay network applications, it could be implemented by ISPs at their gateways, through the use of deep packet inspection or similar technologies. Note that the broadcast constraint is effectively enforced if all packets in the same generation 1 from the same user have identical payload (although with different headers corresponding to different destination addresses). Thus, for each user/generation pair, the network gateway could simply store the payload of the first packet it receives and drop any subsequent packets that have different payloads (while also flagging such a user as "suspicious"). It is worth mentioning that, for wireless networks, this constraint is automatically satisfied due to the broadcast nature of wireless communication [12], so the results of this paper are also naturally applicable in this case.
In general, a broadcast transformation can reduce capacity (significantly, in some cases), unless the network has special connectivity properties. We will show that the maximum number of internally-disjoint paths between source and sink, rather than edge-disjoint paths, becomes the key parameter. This result implies that robustness to node failures and robustness to adversarial attacks are closely related concepts. We then examine a class of networks, which we call d-diverse networks, that have excellent robustness properties. This class of networks is strongly inspired by the work of Jain, Lovász and Chou in [13] on robust and scalable network topologies. We show that, under certain conditions, no loss in capacity is incurred when performing broadcast conversion in such ddiverse networks.
The remainder of this paper is organized as follows. In Sec. II we review some basic concepts of graph theory and network coding. In Sec. III we introduce an adversarial model for communication over untrusted networks. In Sec. IV we introduce the broadcast transformation and characterize the achievable rates of broadcast-constrained networks by relating it to parameters of the original network. In Sec. V we introduce d-diverse networks and study their robustness properties. In Sec. VI we present our conclusions.

A. Graph Theory
In this paper, a graph always means a directed multigraph, i.e., all edges are directed and multiple edges between nodes 2 are allowed. If G is a graph, then V(G) and E(G) denote its vertex set and edge set, respectively. Let Z + = {1, 2, 3, . . .}. We assume that E(G) ⊆ V(G) × V(G) × Z + , where the third component is used to distinguish among multiple edges between the same nodes. For Let |S| denote the cardinality of a set S. For nodes u and v, We use Γ − (v) and Γ + (v) to denote, respectively, the set of all parents and the set of all children of a node v.
Let A path is a sequence of vertices such that from each vertex there is an edge to the next vertex in the sequence. The first and last vertices in a finite path are called end vertices, and the other vertices are called internal vertices.
For distinct nodes s and t, a set S ⊆ V(G) \ {s, t} is called an s, t-vertex cut if G − S has no path connecting s and t. Note that for an s, t-vertex cut to exist, t cannot be a child of s. In that condition, let κ(s, t) denote the minimum size of an s, t-vertex cut.
Two paths are called edge-disjoint if they have no edges in common, and are called internally-disjoint if they have no internal nodes in common. Let λ ′ (s, t) denote the maximum number of pairwise edge-disjoint paths from a node s to a node t and let λ(s, t) denote the maximum number of pairwise internally-disjoint paths from s to t.
We will frequently refer to the edge and vertex versions of Menger's Theorem on directed graphs [14] (the former is also known as the Max-flow Min-cut Theorem).

B. Network Coding
A (single-source) multicast network N = (G, s, T ) consists of a (directed multi)graph G with a distinguished source node s and a set of sink nodes T ∋ s. In a multicast problem, each sink node requests the same message that is observed at the source node.
Each link in the network is assumed to transport, free of errors, a packet of a certain fixed size. A packet in a link entering a node is said to be an incoming packet to that node, and similarly a packet in a link leaving a node is said to be an outgoing packet from that node.
When network coding is used, the source node produces each of its outgoing packets as an arbitrary function of the message it observes. Also, each non-source node produces each of its outgoing packets as an arbitrary function of its incoming packets. The set of functions applied by all nodes in the network specifies a network code. If each sink node, by observing its incoming packets, is able to correctly identify the source message, then we say that the decoding is successful.
Let q be the size of the set from which packets are selected and let Ω be the set from which the source message is selected. The rate of communication is defined as which is the amount of information, measured in packets, that can be conveyed by the source message.
A rate R is said to be achievable for a network N if, for any ǫ > 0, there exist q and Ω with R(Ω, q) ≥ R, along with a corresponding network code, such that the probability of unsuccessful decoding is smaller than ǫ.
For a multicast network N = (G, s, T ), define A key result in [1] is that a rate R is achievable for N if and only if R ≤ C(N ).
For this reason, C(N ) is referred to as the capacity of a multicast network N .

III. UNTRUSTED MULTICAST NETWORKS
In this section we describe a node-centric adversarial model for networks that can be subject to pollution attacks. This model will be used in the remainder of the paper for the computation of achievable rates.
We start with the definition of an untrusted multicast network. Consider a multicast network. A node is said to be trusted if it is guaranteed to behave according to a specified network coding protocol; otherwise, it is said to be untrusted. In particular, a trusted node cannot be controlled by an adversary, while an untrusted node may (or may not) be so. An untrusted multicast network N = (G, s, T , U) is a multicast network (G, s, T ) with a specified set of untrusted nodes U ⊆ V(G) \ {s} such that all nodes in V(G) \ U are trusted.
An adversarial model for communication over an untrusted multicast network may be specified as follows. The adversary chooses a set of adversarial nodes A ⊆ U with |A| ≤ w prior to the beginning of the session. The set A is unknown to source and sink nodes, but remains fixed during the whole session. The adversary controls the nodes in A, which are allowed to transmit any arbitrary packets on their outgoing links and also to cooperate with each other. Since an adversarial node cannot be counted as a sink node, we say that decoding is successful if each node in T \A can correctly recover the source message.
Several end-to-end error control schemes have been proposed to ensure reliable communication over an untrusted network [7]- [10], [15]. The rates achievable by these schemes depend on further assumptions on the system model. In this paper, we focus on the two most basic of these models. The omniscient adversary (OA) model refers to the case where no constraints are imposed on the knowledge or computational power of the adversary. If an additional assumption is made that common randomness is available between the source and sink nodes, then resulting scenario is called the shared secret (SS) model.
Achievable rates under these models are often stated from an edge-centric perspective, i.e., assuming that the adversary controls a certain number of edges. Below we restate these results from a node-centric perspective.

Theorem 3 ( [7]
, [9]): Let N = (G, s, T , U) be an untrusted multicast network with at most w adversarial nodes. Under the shared secret model, it is possible to achieve the rate where Theorem 4 ( [7], [10], [15]): Let N = (G, s, T , U) be an untrusted multicast network with at most w adversarial nodes. Under the omniscient adversary model, it is possible to achieve the rate where We will use (1) and (2) as benchmarks to evaluate the effective throughput of a multicast network in the presence of adversaries.
Note that when there is no adversary, both expressions reduce to the capacity of the underlying network, i.e., From Theorems 3 and 4 we observe that, for an adversarial set A and a sink node t, the quantity mincut(A, t) can have a severe impact on the achievable rate of the untrusted network. If mincut(A, t) is large compared to mincut(s, t), then the adversary can overwhelm the system with corrupt packets, preventing successful decoding.

IV. BROADCAST TRANSFORMATION
In this section, we propose an approach to restrict the min-cut between adversarial nodes and sink nodes, which can lead to potentially higher achievable rates over untrusted networks. The idea is to force each adversarial node to transmit only copies of the same packet, effectively constraining its outdegree to be at most 1. As we do not know beforehand which nodes are adversarial, the constraint must be enforced on every untrusted node. This operation can be represented graphically by introducing a new node u + , as described in Fig. 1. Here, u + is a trusted node that only replicates the packet received. The overall operation, which we refer to as a broadcast transformation, is formally defined below.
Proof: Let (Ĝ, s, T , U) = β(N ). The pair of inequalities follows immediately from Definition 1 and Theorems 3 and 4 by noticing that mincutĜ(A, t) ≤ |A| for any A ⊆ U and any t ∈ T \ A.
For the case U = V(G) \ {s}, let t ∈ T be any node satisfying mincutĜ(s, t) = C(β(N )). Note that t must have at least C(β(N )) distinct parents in G, all of which are untrusted. Take any w of such parents to form a set A. Then mincutĜ(A, t) = w, which shows that both inequalities can be met with equality.
In general, applying a broadcast transformation may reduce C(β(N )), the multicast capacity of the resulting network.
Still, the reduction in the jamming capability of the adversary may compensate for this loss and yield a higher achievable rate. This trade-off, which is captured by Proposition 5, will be shown to be indeed favorable in certain meaningful situations. More specifically, we are interested in studying networks for which C(β(N )) is equal or approximately equal to C(N ). If this is the case, we will say that N is a robust network.
In the remainder of the paper, we restrict attention to the case U = V(G)\{s}, where all non-source nodes are untrusted. This case not only has analytical advantages, but also seems to be the case of most practical relevance.
For a multicast network N = (G, s, T ), define The following theorem shows that the multicast capacity of a broadcast-transformed network has a nice graph-theoretical characterization in terms of the original network. Proof: The proof is closely related to the standard argument used to derive Theorem 2 from the Max-flow Min-cut Theorem.
Let β(N ) = (Ĝ, s, T , U). Since U = V(G) \ {s}, the broadcast transformation replaces each non-source node by a node followed by an edge followed by a node, as illustrated in Fig 1. Thus, if two paths in G are internally-disjoint, then they will also be internally-(and therefore edge-) disjoint inĜ. Conversely, if two paths in G are not internally-disjoint, i.e., they share a node v, then they will also share the two nodes v and v + and the edge (v, v + , 1) inĜ, and therefore will not be edge-disjoint inĜ. Thus, for any t ∈ T , the maximum number of internally-disjoint paths from s to t in G must be equal to the maximum number of edge-disjoint paths from s to t in G, i.e., λ G (s, t) = λ ′Ĝ (s, t) = mincutĜ(s, t). The result now follows from the definitions of Λ(N ) and C(β(N )).
We now give some examples of robust and non-robust networks.

Example 2:
To make the network in Fig. 2 robust, we can increase the diversity of internally-disjoint paths to v 5 and v 6 by letting v 5 and v 6 have multiple parents. This may result in a network N as shown in Fig. 3. Now, for all i, we have mincut(s, v i ) = 3 and λ(s, v i ) = 3. Thus C(N ) = 3 and C(β(N )) = Λ(N ) = 3. Therefore, N is a robust network.

V. d-DIVERSE NETWORKS
In this section, we study a special class of networks, which we call d-diverse networks, that have simultaneously good capacity and robustness properties. This class of networks   is motivated by the notion of parent diversity illustrated in Example 2.

Definition 2:
Let N = (G, s, T ) be an acyclic multicast network. The (parent) diversity of a non-source node v ∈ V(G) \ {s} is defined as The (parent) diversity of N is defined as For any node that is nonadjacent to the source node, the parent diversity is exactly the cardinality of its parent set. For a node that is adjacent to the source node, this interpretation remains true if we replace each edge coming from the source node by an edge followed by a node followed by an edge. This slight twist in the definition is required due to the special role that a source node has in a network problem.
The following is the main result of this section. In particular, if indegree(t) = d(N ) for some t ∈ T , then Theorem 7 shows that, for large enough d, a d-diverse network not only has good multicast capacity but is also robust. In particular, when designing a network, one might focus solely on achieving high parent diversity, obtaining good capacity and robustness as natural consequences. It is important to note that, while C(N ) and Λ(N ) are global parameters of the network, the diversity d(N ) (or rather d(v) for each node v) is a parameter that depends only on local information available at a node. Therefore, it should be relatively easy to construct a d-diverse network by enforcing d(v) ≥ d at each node. This is indeed the case for the class of JLC networks, as discussed later in Example 3.
In order to prove Theorem 7, we start with a lemma that characterizes minimal vertex cuts in a graph. We can now give a proof of Theorem 7.
Proof of Theorem 7: Let t ∈ T . First, suppose t is not adjacent to s. Let [S,S] be some s, t-edge cut achieving the minimization in (3). Since the graph G is directed acyclic, it has at least one topological ordering. Let u be the first node inS according to some topological ordering, i.e., u ∈S is a node whose parents are all in S. We have where (4)   Returning to the original network, we have From the above arguments, it follows that Λ(N ) ≥ d(N ). The special case follows immediately since Λ(N ) ≤ C(N ) ≤ indegree(t), for all t ∈ T .
As an application of Theorem 7, consider the case of a network in which all non-source nodes are sink nodes with diversity exactly d, and such that there are no parallel edges between nodes, except possibly emanating from the source node. Then the multicast capacities both before and after broadcast transformation are exactly equal to d. Note that, as the indegree of any non-source node is exactly d, any removed edge would result in a smaller capacity. Thus, we may conclude that, given a fixed number of edges, the network capacity is maximized by having nodes select incoming edges from distinct parents rather than from the same parent. This result holds even if all non-source nodes are untrusted, provided a broadcast transformation is performed.

Example 3 (JLC networks):
We now describe a class of networks that has not only good theoretical properties but also potential for practical applications. The protocol for constructing and operating these networks has been proposed by Jain, Lovász and Chou [13] as a scalable and robust solution to peer-to-peer data dissemination with network coding. We refer to any network constructed according to their protocol as a JLC network.
An example of a JLC network is depicted in Fig. 4. The network is acyclic, and all non-source nodes are sinks. Initially, the network contains only the source node (or server), which has k (potential) outgoing links. Here, each link represents a stream of unit bandwidth. At any time, the server maintains a list of k available links for download. When a new node joins the network, it requests from the server d download links. The server randomly picks d links from the pool of available links, and updates its list with d potential links originating from the new node. Therefore, the network always has k links (i.e., streams of unit bandwidth) available for download.
It is easy to ensure that a JLC network is d-diverse by performing a simple protocol modification. When a new node joins the network, rather than choosing the d upstream links completely at random from the k available links (thereby allowing the possibility of fewer than d distinct parents), the server simply needs to provide the new node with d links from d distinct parents. Note that, in practice, k ≫ d 2 , so the k available links come from at least l = ⌈k/d⌉ ≫ d parents. Hence, the modification can be done easily.

VI. CONCLUSIONS
We have introduced the broadcast transformation of a network, which restricts the influence of potential adversaries by limiting them to a single transmission opportunity per generation. For networks with a sufficient diversity of internally-disjoint paths from source to sink(s), the multicast capacity may not be greatly affected by this transformation. In particular, for a class of networks called d-diverse networks, the full capacity is maintained when d is sufficiently large. Combined with error control for network coding, the proposed approach may be an effective means of dealing with adversaries, particularly in application scenarios such as realtime media streaming, where alternative (e.g., cryptographic) methods may be cost-prohibitive.