A few years ago, an international group of scientists from the universities of Massachusetts, Pennsylvania, and Munich in Germany conducted research on the effectiveness of traditional proxies as a tool for combating censorship. As a result, the researchers proposed a new method for bypassing blocks based on game theory. We have prepared an adapted translation of the main points of this work.
Introduction
The approach of popular bypass tools, such as Tor, is based on the private and selective distribution of proxy IP addresses among clients from regions subject to blocks. Consequently, clients must remain unnoticed by organizations or authorities imposing the blocks. In the case of Tor, such proxy distributors are called bridges.
A key problem with such services is the insider attack. Agents involved in blocking can themselves use proxies to discover their addresses and block them. To minimize the likelihood of proxy detection, bypass tools employ various address assignment mechanisms.
In this context, an ad hoc heuristic approach is used, which can be bypassed. To address this issue, the researchers decided to represent the struggle between blocking services and the tools for circumventing them as a game. By utilizing game theory, they developed optimal strategies of behavior for each party – in particular, this allowed for the formulation of a proxy distribution mechanism.
How traditional bypass systems work
Bypass tools, such as Tor, Lantern, and Psiphon, use a number of proxies from outside the restricted region, which are used to redirect user traffic from these regions and deliver it to blocked resources.
If censors become aware of the IP address of such a proxy – for instance, after they have used it themselves – it can easily be blacklisted and blocked. Therefore, in reality, the IP addresses of such proxies are never revealed, and the assignment of users to particular proxies occurs through various mechanisms. For example, Tor has a bridge system.
The main task is to provide users access to blocked resources and minimize the likelihood of revealing the proxy address.
Solving this task in practice is quite difficult — it is very challenging to distinguish regular users from censoring agents who are concealing their identity. Heuristic mechanisms are used to hide information. For instance, Tor limits the number of bridge IP addresses available to clients to three within a single request.
This did not prevent the authorities in China from identifying all Tor bridges in a short time. The implementation of additional restrictions would significantly impact the usability of the circumvention system, meaning some users would be unable to access the proxy.
How Game Theory Solves This Problem
The method described in this paper is based on the so-called 'college admissions game'. Additionally, it is assumed that censoring internet agents can communicate with each other in real-time and use sophisticated tactics — for example, not blocking proxies immediately or doing so instantly depending on various conditions.
How College Admissions Work
Assume we have n students and m colleges. Each student creates their list of preferences among educational institutions based on certain criteria (meaning only colleges where applications have been submitted are ranked). On the other hand, colleges also rank students who have submitted applications based on their own preferences.
First, the college eliminates those who do not meet the admission criteria — they will not be accepted even in the case of under-enrollment. Then, accepted students are selected based on an algorithm that takes into account the necessary parameters.
There can exist 'unstable admissions' — for instance, if there are two students 1 and 2 who have been accepted into colleges a and b respectively, but the second student would prefer to attend college a. In the described experiment, only stable connections between objects were considered.
The Deferred Acceptance Algorithm
As mentioned, there is a certain number of students whom the college will not accept under any circumstances. Therefore, in the deferred acceptance algorithm, it is assumed that these students are not allowed to apply to this university. In this case, all students attempt to enroll in the colleges they prefer the most.
The educational institution with a capacity of q students places q individuals with the highest ranking on the waiting list based on its criteria, or all if the number of applicants is less than the number of available spots. Others are rejected, and these students apply to the next university on their list of preferences. This college also selects q students with the highest ranking from both those who applied immediately and those who were not accepted into the first college. Again, some individuals do not qualify.
The procedure ends when each student is either on the waiting list of some college or has been rejected by all educational institutions they could apply to. Ultimately, colleges finalize enrollment for all students on their waiting lists.
What's the proxy for?
Analogous to students and colleges, researchers assigned each client a specific proxy. This resulted in a game called the proxy assignment game. Clients, including potential censor agents, act as students wanting to know the address of the proxies, which play the role of colleges – they have a predetermined final capacity.
In the described model, there are n users (clients) A =
{a1, a2, …, an}, who request access to proxies to bypass blocks. Thus, ai is the identifier of the "total" client. Among these n users, m are censor agents, denoted as J = {j1, j2, …, jm}, while the rest are regular users. All m agents are controlled by a central authority and receive instructions from it.
It is also assumed that there is a set of proxies P = {p1, p2, …, pl}. After each request, the client receives from the distribution object information (IP address) about k proxies. Time is divided into interval stages, denoted as t (the game starts at t=0).
Each client uses a scoring function to evaluate the proxies. Researchers used the function. 
, to denote the score that the AI user assigned to the proxy px at stage t. Similarly, each proxy utilizes a function to evaluate clients. That is, 
– the score that the proxy px assigned to the client ai at stage t.
It is important to remember that the entire game is virtual, meaning that both the proxy and the clients are played by the 'distributor'. For this, it is not necessary to know the type of client or their preferences regarding proxies. At each stage, a game occurs, and a delayed acceptance algorithm is also employed.
Results
Based on simulation results, the method using game theory demonstrated higher efficiency compared to known bypass systems.
Comparison with the VPN service rBridge
In this context, researchers highlighted several important factors that can affect the performance quality of such systems:
- Regardless of the censors' strategies, the bypass system must continuously be updated with new proxies; otherwise, its effectiveness will decline.
- If censors have significant resources, they can enhance blocking efficiency by adding geographically distributed agents to search for proxies.
- The speed of adding new proxies is critical to the effectiveness of the bypass system.
Useful links and resources from :
Source: habr.com
