09-04-2014, 03:24 PM
Secure Hierarchical In-Network Aggregation in Sensor Networks
Hierarchical In-Network .pdf (Size: 180.03 KB / Downloads: 11)
ABSTRACT
In-network aggregation is an essential primitive for performing
queries on sensor network data. However, most aggregation algo-
rithms assume that all intermediate nodes are trusted. In contrast,
the standard threat model in sensor network security assumes that
an attacker may control a fraction of the nodes, which may misbe-
have in an arbitrary (Byzantine) manner.
We present the first algorithm for provably secure hierarchical
in-network data aggregation. Our algorithm is guaranteed to detect
any manipulation of the aggregate by the adversary beyond what is
achievable through direct injection of data values at compromised
nodes. In other words, the adversary can never gain any advan-
tage from misrepresenting intermediate aggregation computations.
Our algorithm incurs only O(∆ log2 n) node congestion, supports
arbitrary tree-based aggregator topologies and retains its resistance
against aggregation manipulation in the presence of arbitrary num-
bers of malicious nodes. The main algorithm is based on perform-
ing the SUM aggregation securely by first forcing the adversary to
commit to its choice of intermediate aggregation results, and then
having the sensor nodes independently verify that their contribu-
tions to the aggregate are correctly incorporated. We show how to
reduce secure MEDIAN, COUNT, and AVERAGE to this primitive.
INTRODUCTION
Wireless sensor networks are increasingly deployed in security-
critical applications such as factory monitoring, environmental mon-
itoring, burglar alarms and fire alarms. The sensor nodes for these
applications are typically deployed in unsecured locations and are
not made tamper-proof due to cost considerations. Hence, an adver-
sary could undetectably take control of one or more sensor nodes
and launch active attacks to subvert correct network operations.
Such environments pose a particularly challenging set of constraints
for the protocol designer: sensor network protocols must be highly
energy efficient while being able to function securely in the pres-
ence of possible malicious nodes within the network.
In this paper we focus on the particular problem of securely and
efficiently performing aggregate queries (such as MEDIAN, SUM
and AVERAGE) on sensor networks. In-network data aggregation is
an efficient primitive for reducing the total message complexity of
aggregate sensor queries. For example, in-network aggregation of
the SUM function is performed by having each intermediate node
forward a single message containing the sum of the sensor readings
of all the nodes downstream from it, rather than forwarding each
downstream message one-by-one to the base station. The energy
savings of performing in-network aggregation have been shown to
be significant and are crucial for energy-constrained sensor net-
works [9, 11, 20].
Network Assumptions
We assume a general multihop network with a set S = {s1 , . . . , sn }
of n sensor nodes and a single (untrusted) base station R, which is
able to communicate with the querier which resides outside of the
network. The querier knows the total number of sensor nodes n,
and that all n nodes are alive and reachable.
We assume the aggregation is performed over an aggregation
tree which is the directed tree formed by the union of all the paths
from the sensor nodes to the base station (one such tree is shown
in Figure 1(a)). These paths may be arbitrarily chosen and are not
necessarily shortest paths. The optimisation of the aggregation tree
structure is out of the scope of this paper—our algorithm takes the
structure of the aggregation tree as given. One method for con-
structing an aggregation tree is described in TaG [11].
RELATED WORK
Researchers have investigated resilient aggregation algorithms to
provide increased likelihood of accurate results in environments
prone to message loss or node failures. This class of algorithms
includes work by Gupta et al. [7], Nath et al. [15], Chen et al. [3]
and Manjhi et al. [14].
A number of aggregation algorithms have been proposed to en-
sure secrecy of the data against intermediate aggregators. Such al-
gorithms have been proposed by Girao et al. [5], Castelluccia et
al. [2], and Cam et al. [1].
Hu and Evans [8] propose securing in-network aggregation against
a single Byzantine adversary by requiring aggregator nodes to for-
ward their inputs to their parent nodes in the aggregation tree. Jadia
and Mathuria [10] extend the Hu and Evans approach by incorpo-
rating privacy, but also considered only a single malicious node.
Several secure aggregation algorithms have been proposed for
the single-aggregator model. Przydatek et al. [17] proposed Se-
cure Information Aggregation (SIA) for this topology. Also for the
single-aggregator case, Du et al. [4] propose using multiple wit-
ness nodes as additional aggregators to verify the integrity of the
aggregator’s result. Mahimkar and Rappaport [13] also propose
an aggregation-verification scheme for the single-aggregator model
using a threshold signature scheme to ensure that at least t of the
nodes agree with the aggregation result. Yang et al. [19] describe
a probabilistic aggregation algorithm which subdivides an aggre-
gation tree into subtrees, each of which reports their aggregates
directly to the base station. Outliers among the subtrees are then
probed for inconsistencies.
CONCLUSION
In-network data aggregation is an important primitive for sensor
network operation. The strong standard threat model of multiple
Byzantine nodes in sensor networks requires the use of aggrega-
tion techniques that are robust against malicious result-tampering
by covert adversaries.
We present the first optimally secure aggregation scheme for ar-
bitrary aggregator topologies and multiple malicious nodes. This
contribution significantly improves on prior work which requires
strict limitations on aggregator topology or malicious node multi-
plicity, or which only yields a probabilistic security bound. Our al-
gorithm is based on a novel method of distributing the verification
of aggregation results onto the sensor nodes, and combining this
with a unique technique for balancing commitment trees to achieve
sublinear congestion bounds. The algorithm induces O(∆ log2 n)
node congestion (where ∆ is the maximum degree in the aggre-
gation tree) and provides the strongest security bound that can be
proven for any secure aggregation scheme without making assump-
tions about the distribution of data values.