We present a class of Minimum Cost Blocking (MCB) problems in Wireless Mesh Networks (WMNs) with multi-path routing protocols. We establish the provable superiority of multi-path routing protocols over conventional protocols against blocking, node-isolation and network-partitioning type attacks. In our attack model, an adversary is considered successful if he is able to capture/isolate a subset of nodes such that no more than a certain amount of traffic from source nodes reaches the gateways. Two scenarios, viz. (a) low mobility for network nodes, and (b) high degree of node mobility, are evaluated. Scenario (a) is proven to be NP-hard and scenario (b) is proven to be #P-hard for the adversary to realize the goal. Further, several approximation algorithms are presented which show that even in the best case scenario it is at least exponentially hard for the adversary to optimally succeed in such blocking-type attacks. These results are verified through simulations which demonstrate the robustness of multi-path routing protocols against such attacks. To the best of our knowledge, this is the first work that theoretically evaluates the attack-resiliency and performance of multi-path protocols with network node mobility.

This paper demonstrates the provable superiority of multi-path routing protocols over other conventional protocols in Wireless Mesh Networks (WMNs) against blocking, node- isolation and network-partitioning type-attacks. Though the underlying network model is of a WMN with mobile nodes, the results in this paper are equally applicable to other types of wireless data networks. The adversarial objective is to isolate a subset of network nodes through minimal cost optimal blocking of certain number of paths in the network (or partitioning the network). If less than a certain threshold of traffic from such node(s) reaches the routers, the adversary is successful. Two scenarios viz. (a) low mobility for network nodes, and (b) high degree of node mobility, are evaluated. Scenario (a) is proven to be NP-hard and scenario (b) is proven to be #P-hard for the adversary to achieve the goal. Further, several approximation algorithms are presented which show that even in the best case scenario it is at least exponentially hard for the adversary to optimally succeed in such blocking-type attacks. Simulations verify the results and demonstrate the robustness of multi-path protocols against such attacks. The objective of this paper is to study the performance and feasibility of multi-path wireless protocols over conventional single-path protocols from a security angle. To the best of our knowledge, this is the first paper to theoretically evaluate the attack-resiliency and performance of multi-path protocols with network node mobility.