Abstract:
Wireless sensor networks have proved to be useful in several applications, such as environment monitoring and perimeter surveillance. In a large sensor network, in-network data
aggregation (i.e., combining partial results at intermediate nodes during message routing)
significantly reduces the amount of communication and energy consumption. Recently, the
research community has proposed a robust aggregation framework called synopsis diffusion
which combines multi-path routing schemes with duplicate-insensitive algorithms to accurately compute aggregates (e.g., Count, Sum) in spite of message losses resulting from node
and transmission failures. However, this aggregation framework does not address the problem of false sub-aggregate values contributed by compromised nodes resulting in large errors
in the aggregate computed at the base station, which is the root node in the aggregation
hierarchy. This is an important problem since sensor networks are highly vulnerable to node
compromises due to the unattended nature of sensor nodes and the lack of tamper-resistant
hardware.
In this dissertation, we make the synopsis diffusion approach secure against attacks in
which compromised nodes contribute false sub-aggregate values. In particular, we present
two classes of algorithms to securely compute Count or Sum. First, we propose a lightweight
verification algorithm which enables the base station to determine if the computed aggregate
includes any false contribution. Second, we present attack-resilient computation algorithms
which can be used to compute the true aggregate by filtering out the contributions of compromised nodes in the aggregation hierarchy. Thorough theoretical analysis and extensive
simulation study show that our algorithms outperform other existing approaches.
This dissertation also addresses the security issues of in-network computation of Median
and presents verification algorithms and attack-resilient computation algorithms to securely
compute an approximate estimate of this aggregate. To the best of our knowledge, prior to
this dissertation there was no other work related to the security of in-network computation
of Median. We evaluate the performance and cost of our algorithms via both analysis and
simulation. The results show that our approach is scalable and efficient.
