We examine networks that employ net-by reducing the transmission rate to below the min-cut of work coding and are subject to Byzantine attacks. the network, and using the redundancy to protect against We assume that an appropriate network error cor-errors. One such technique, using subspaces to code inforrecting scheme is employed that is able to correct (up mation was proposed in [3]. In this approach, the source to a certain number of) Byzantine errors. Given this sends a basis of the subspace corresponding to the messetup, we formulate the problem of locating these ma-sage. In the absence of errors, the linear operations of licious nodes that insert errors. We utilize the sub-the intermediate nodes do not alter the sent subspace, space properties of (randomized) network coding to and hence the receiver decodes the message by collectdevelop algorithms to locate the Byzantine attackers. ing the basis of the transmitted subspace. A malicious attacker inserts vectors that do not belong in the transmitted subspace. Therefore, if the message codebook uses Over the past few years, network error correcting codes, subspaces that are "far enough" apart (according to an that are capable of correcting errors inserted in the net-appropriately defined distance measure), then one can work, have been developed [3, 6, 7, 8, 9, 10]. These correct these errors [3]. Note that in this technique, we schemes are therefore capable of delivering information do not need any knowledge of the network topology for despite the presence of Byzantine attacks in the network, the error correction mechanism. All that is needed is that as long as the number of such attacks is limited. There the intermediate nodes do not alter the transmitted subhave been codes proposed for the detection and correc-space (which can be done if they do linear operations [4, 5], where Other than the new problem formulation, our contriit was shown that using subspace properties of random butions in this paper are the following. For the case of the network coding, one can in many cases infer the network single adverserial node, we present simple algorithms that topology. Therefore, in this paper, we ask the question allow to identify the adversary within an uncertainty of of whether we can locate the Byzantine attackers, using at most two nodes. When there are multiple adversaries, properties of the network code, and the knowledge of the we discuss a number of algorithms, and their respective topology. capabilities to identify adversaries. Though these are preHence, in some sense, we are here interested in the dual liminary ideas, we believe this is a promising line of reaspect of the network error correction problem: once a search Byzantine attack is detected, we would like to identify Note that for the development of the ideas in this pawhich of the network node(s) has (have) launched the at-per, we will assume that subspace network error correcttack. This would allow us to isolate the malicious attacker ing codes are used. However, the approach we will defrom the network, and thus avoid the computational com-scribe could also apply to the more traditional network plexity of correcting errors as well as prevent a possible error correction, where a coding vector is appended to escalation of the attack. each transmitted packet, and intermediate nodes perform In a network coded system, the adverserial nodes in the randomized network coding. We note that for such netnetwork disrupt the normal operation of the information work error correcting the intermediate nodes in the netflow by inserting erroneous packets into the network. This work (including the malicious ones) do not need to know can be done by inserting spurious data packets into their the position of the coding vectors within the packet, since outgoing edges. One way in which these erroneous pack-they simply need to apply the same operations to all symets can be prevented from disrupting information flow is bols in the packet. Thus corrupting a packet will corrupt 978-1-4244-1689-9/08/$25.00O
Jafarisiavoshani et al. REF leveraged the subspace properties of random network coding to approximately identify the location of attackers.