The Warwick Research Archive Portal (WRAP) makes this work by researchers of the University of Warwick available open access under the following conditions. Copyright © and all moral rights to the version of the paper presented here belong to the individual author(s) and/or other copyright owners. To the extent reasonable and practicable the material made available in WRAP has been checked for eligibility before being made available. Copies of full items can be used for personal research or study, educational, or not-for profit purposes without prior permission or charge. Provided that the authors, title and full bibliographic details are credited, a hyperlink and/or URL is given for the original metadata page and the content is not changed in any way. This is the accepted version of the following article: Jhumka, A., Bradbury, M. and Leeke, M. (2014), Fake source-based source location privacy in wireless sensor networks. Concurrency and Computation, which has been published in final form at: http://dx.doi.org/10.1002/cpe.3242 . The version presented here may differ from the published version or, version of record, if you wish to cite this item you are advised to consult the publisher's version. Please see the 'permanent WRAP url' above for details on accessing the published version and note that access may require a subscription.  The development of novel wireless sensor network (WSN) applications, such as asset monitoring, has led to novel reliability requirements. One such property is source location privacy (SLP). The original SLP problem is to protect the location of a source node in a WSN from a single distributed eavesdropper attacker. Several techniques have been proposed to address the SLP problem, and most of them use some form of traffic analysis and engineering to provide enhanced SLP. The use of fake sources is considered to be promising for providing SLP, and several works have investigated the effectiveness of the fake sources approach under various attacker models. However, very little work has been done to understand the theoretical underpinnings of the fake source technique. In this paper, we: (i) provide a novel formalisation of the fake sources selection problem (ii) prove the fake sources selection problem to be NP-complete, (iii) provide parametric heuristics for three different network configurations, and (iv) show that these heuristics provide (near) optimal levels of SLP, under appropriate parameterisation. Our results show that fake sources can provide a high level of SLP. Our work is the first to investigate the theoretical underpinnings of the fake source technique. . For critical applications, dependability is important. In particular, privacy, which can generally be described as the guarantee that information can only be observed or deciphered by those intended to observe or decipher it [3], will be an important property. As WSNs operate in a broadcast medium, attackers can easily intercept messages and subsequently launch attacks. The security threats that exist for WSNs can be classified along two dimensions, content-based privacy threats and context-based privacy threats. The privacy threats against the content relate to threats that are based on the contents of messages, i.e., the attacks are against the data generated by the higher network layers -data generated either at the application level (values sensed by sensors) or lower-layer levels (e.g., time-stamps). In such attacks, attackers try to capture data to learn about the status of the network so that relevant attacks can be launched. Much research has addressed content-based attacks [4] . On the other hand, context-based privacy threats are those Context is a multi-attribute concept that captures several aspects, some of which are environmental, associated with sensed data such as location, and time so that the proper semantics is given to the data. While content-based threats have been widely addressed [4], context-based threats are becoming increasingly popular. For content-based threats, nodes launching attacks are often modelled as Byzantine nodes [5] [6], with cryptographic techniques often being used to address these problems [4] [5] [7] . However, cryptographic techniques cannot help with handling contextbased threats. New techniques must be introduced to handle context-based threats. One important problem for asset monitoring applications is the problem of source location privacy (SLP). In this problem, a WSN is monitoring an asset, say an endangered wild animal. Then, when nodes detect the presence of the asset, which we call the source nodes, those source nodes will periodically send messages, over a certain duration, to a dedicated node, called a sink, for data collection. If the location(s) of the source node(s) is compromised, directly or inferred, then an attacker can easily capture the asset. It is possible to infer message location information through various techniques, depending on the power of the attacker. For example, Mehta et al. [8] assumes that an attacker has a small wireless network, which we term an attacker network, of his own that captures messages and shows how the attacker network can infer the location of nodes after it intercepts messages. On the other hand, Kamat et al. [3] assume a single attacker, who uses the routing protocol to infer the location of the source. For example, in a military environment, soldiers out on a surveillance mission may relay information to a sink. An attacker can intercept these messages, and trace them back to the soldiers, thereby compromising the safety of the soldiers. Several possible techniques to handle the SLP problem have been proposed [3] [8] [9] [10] [11] . In this paper, we focus on the fake source technique, first proposed in a seminal work in [3] . When applying this technique, a set of nodes are chosen to act as a decoy for the real source, i.e., to act as fake sources. When the set of nodes is the whole network, maximum SLP is achieved [8] . However, this is not practical due to the large amount of energy needed, and this will severely affect the lifetime of the network. The fake sources generate messages to engineer network traffic in such a way so as to confuse an attacker. Despite the intuitive nature of the approach, little work has been done to understand the detailed working of the fake source technique. Recently, two algorithms were proposed that address the tradeoffs between privacy and energy usage [12] , where these algorithms were shown to provide a balance between privacy and energy consumption. However, little work has focused on the development of systematic approaches for selecting fake sources. More importantly, it was observed in [3] that permanent fake sources outperform shortlived, i.e., temporary, fake sources, although at the cost of greater energy expenditure. Thus, it becomes important to develop approaches that allow selection of permanent and/or temporary fake sources, depending on the application requirements. In this context, there is a tradeoff to be made whereby, having permanent fake sources enable having higher levels of SLP but at the expense of higher energy usage, compared with temporary fake sources, which provide lower levels of SLP but at lower energy cost. To this end, in this paper, a hybrid technique is proposed, where both temporary and permanent fake sources are used to address the SLP problem. To enable this technique, temporary and permanent fake sources are modelled as fake sources with varied duration. The problem of selecting temporary and permanent fake sources is then directly addressed. In this paper, we provide a formalisation of the FSS problem, allowing us to identify two important parameters that underpin the efficiency of algorithms that provide SLP; fake message rates and fake source duration. Under this formalisation, we show the FSS problem to be NP-complete. We subsequently propose a set of heuristics to address FSS, parameterised with the above two parameters, and evaluate their efficiency in providing SLP in various network configurations. Our results show that, under certain parameterisation, it is possible to obtain optimal privacy, i.e., the real source is never captured.
The fake source selection problem has been shown to be NP-complete, with a parameterised network-wide approach proposed to overcome the problem REF .
Fake source-based source location privacy in wireless sensor networks
Concurr. Comput. Pract. Exp.
Concurr. Comput. Pract. Exp.
Computer Science