On Combinatoric Approach to Circumvent Internet Censorship Using Decoy Routers

The Internet is often referred to as an information highway since it offers a great mean for the general public to access the almost unlimited amount of information. At the same time, this communication technology poses a great threat to the system in those countries that wish to control the information flow. As a result, the Internet is subject to be under censorship, which is, however, a great privacy issue. Deploying decoy routers is one emerging approach to tackle this issue, since it helps each packet whose destination is a prohibited server to hide its ultimate destination from the censorship authority also known as warden. The recent report by Schuchard et al. shows an existence of an efficient approach to detect and isolate active decoy routers from the public. As a countermeasure, they propose to deploy decoy routers surrounding a target country such that isolating the decoy routers will result in isolating the the country from the rest of the Internet. Based on our observation that this problem in fact is with two opposite optimization goals, minimizing the number of decoy routers and maximizing the confinement rate, we introduce two polynomial time algorithms which handle this deployment problem under the presence of uncooperative ASes. We also conduct simulations to compare and analyze the performance of our algorithms.