Research: Creating A Censorship-Resilient Proxy Tool Based On The Game Theory
Several years ago, an international group of scientists from the University of Massachusetts Amherst, Pennsylvania State University and Technical University of Munich published a research paper examining the effectiveness of traditional proxies as a tool for fighting censorship on the internet. As a result, researchers proposed a new method of bypassing the restrictions applied by censoring authorities.
Here is our breakdown of the main principles and ideas of the method.
Intro
Popular circumvention tools like Tor are based on the principle of private assignment of IP-addresses. These addresses are distributed among clients from censored regions to allow the bypassing of restrictions applied on the web resources in their locations. In the case of Tor, such private proxies are called bridges.
The fundamental problem of such circumvention tools is an insider attack. Proxies may be used not only by censored users but also by agents working for the censoring authorities as well. If these agents find out the addresses of proxies, they can quickly ban them. Therefore, proxy services should keep their IP-addresses private and use proxy assignment mechanisms.
Most of the modern proxies use the so-called ad hoc heuristics approach, which is easy to bypass. To solve this problem, the researchers decided to look at the censorship and anti-censorship fight as a game. Using game theory principles, they were able to develop optimal strategies for each party. The results were useful in the creation of a new proxy distribution mechanism.
How tradition circumvention systems work
Many modern circumvention tools like Tor, Lantern, and Psiphon use a range of proxies outside of the censored region. These proxies are used to relay the traffic of censored users to web resources and back again.
However, if a censorship authority finds out the IP address of such proxy, for example, by using it, there are no difficulties in blocking it. This the reason why, in reality, proxy services never disclose their real addresses. Instead, they use different proxy assignment mechanisms like bridges in Tor.
The main task of any proxy service is to allow censored users access to blocked websites and to minimize the probability of proxy address disclosure. It is hard to solve this puzzle: you can’t distinguish between a real user and a censor-owned agent with a high degree of accuracy. Instead, it is easier to hide the information that might be used to block a proxy by using heuristic mechanisms. For example, Tor allows the client to access only three bridge IP addresses within a single request.
Such methods have limited effectiveness. For example, Chinese authorities were able to find and block all Tor bridges very quickly. In turn, proxy owners can’t apply more and more restrictions as this harms the overall user experience and prevents some people from using the proxy.
How game theory is useful here
The method created by scientists is built around the college admissions game. Also, researchers supposed that censor-owned agents could communicate in real time and use complicated tactics: for example, block proxies immediately or postpone the block depending on different conditions.
What is the college admission process?
Let’s imagine that we have n students and m colleges. Each student creates his or her wish list of colleges based on certain criteria. Students only rate the colleges they really “applied to.” From their side, colleges also rate students based on their preferences.
The college first eliminates students who will not be admitted under any circumstances (i.e., they do not meet the admission criteria). These people will not be let in even in the case where there are not enough applicants to fill all open admission slots. Those who meet the required criteria are then ranked using a specialized algorithm and put on to the wish list.
There is a probability of “unstable” admissions when we have students 1 and 2 admitted to colleges a and b correspondingly, but student number 2 would like to go to college a. In this experiment, only stable connections were examined.
Deferred acceptance algorithm
As is said above, some students will not be admitted under any circumstances. This is why the deferred acceptance algorithm supposes that these students can’t apply to the specific college. So, students can submit applications to the colleges they like most and those they are allowed to submit applications to.
A college with a capacity of q students places the q students on a waiting list with the highest ranking, or all of the applicants if the overall number of applications is less than q. The remaining students get a rejection and can apply to the next college on their wish list. This new college also runs an admissions process and accepts q applicants with the highest rank from its wish list as well as those who were rejected by their previous choice of college. Again, there will be rejected applicants.
The process ends if every student manages to get accepted to a college or is rejected by all of them. After this process, colleges formally admit the students from their waiting lists formed during the admission process.
How this relates to proxies
Similar to college admission, researchers assigned each client a specific proxy. This led to a “proxy assignment game.” Clients, including censor-owned agents, served as “students” who needed to get into a “college,” i.e., to know the IP address of the proxy to connect to. Each proxy, similar to a college, had a specific capacity.
In the described model we have n users (clients) A = {a1, a2, …, an} that request access to a proxy to connect to blocked content. Among these clients there are m censor-owned agents, J = {j1, j2, …, jm}, while the rest are regular users. A central authority controls all m agents and receives instructions from them.
There is also a set of proxies P = {p1, p2, …, pl}. The client receives information about k proxies from the distributor after each request. The time is divided into stages t; the game starts when t=0.
Each client uses a scoring function to assess the proxy. To set up a score user ai has assigned to the proxy px at a stage t the function
is used. I.e., the score the proxy px has assigned to client ai at a stage t is
It is important to remember that the whole “game” is virtual; the distributor plays it on behalf of proxies and clients. To do this, it needs to know the type of client, and its preferences. At every stage of the game, the deferred admission algorithm is used.
Results
Simulations showed that the proxy distribution method based on the game theory could be more efficient than traditional circumvention techniques.
Game theory-based method comparison to rBridge VPN
Researchers have outlined several important factors that can affect the overall quality of circumvention systems:
- No matter what the censor’s strategy is, the circumvention system should always expand with new proxies, or its effectiveness will decrease.
- If censors possess significant resources, they can increase the effectiveness of their blocks by adding geo-distributed agents for finding proxies.
- The speed of adding new proxies is crucial for the circumvention system’s overall effectiveness.
