A few years ago, an international team of scientists from the Universities of Massachusetts, the State of Pennsylvania and German Munich study of the effectiveness of traditional proxies as an anti-censorship tool. As a result, scientists have proposed a new method for bypassing blocking based on game theory. We have prepared an adapted translation of the main points of this work.
Introduction
The approach of popular ban evaders like Tor is based on the private and selective distribution of proxy IP addresses among clients from regions subject to bans. As a result, clients should remain undetected by organizations or authorities that impose blocking. In the case of Tor, these proxy distributors are called bridges.
The key problem in the case of such services is the insider attack. Blocking agents can use proxies themselves to find out their addresses and block them. To minimize the likelihood of proxy calculation, blocking bypass tools use various address assignment mechanisms.
In this case, the approach of the so-called ad hoc heuristics is used, which can be bypassed. To solve this problem, scientists decided to present the struggle of services involved in blocking and services to bypass them as a game. Using game theory, they developed optimal behavior strategies for each of the parties - in particular, this made it possible to develop a mechanism for distributing proxies.
How traditional lock bypass systems work
Block bypass tools like Tor, Lantern, and Psiphon use a number of proxies outside the restricted region that are used to divert user traffic from those regions and deliver it to blocked resources.
If censors become aware of the IP address of such a proxy - for example, after they use it themselves - it is easy to blacklist and block it. Therefore, in reality, the IP addresses of such proxies are never disclosed, and the assignment of one or another proxy to users occurs using various mechanisms. For example, Tor has a bridge system.
That is, the main task is to provide users with access to blocked resources, and minimize the likelihood of disclosing the proxy address.
Solving this problem in practice is not so easy - it is very difficult to distinguish ordinary users from censors disguised from them with high accuracy. Heuristic mechanisms are used to hide information. For example, Tor limits the number of bridge IP addresses available to clients to three per request.
This did not stop the Chinese authorities from figuring out all the Tor bridges in a short time. The introduction of additional restrictions will seriously affect the usability of the lock bypass system, that is, some users will not be able to access the proxy.
How does game theory solve this problem?
The method described in the paper is based on the so-called college admissions game. In addition, it is assumed that Internet censoring agents can communicate with each other in real time and use complex tactics - for example, do not block proxies immediately, or do it instantly, depending on various conditions.
How college admission works
Suppose we have n students and m colleges. Each student makes his own list of preferences among educational institutions based on some criteria (that is, only colleges where documents are submitted are ranked). On the other hand, colleges also rank student applicants based on their own preferences.
First of all, the college cuts off those who do not meet the selection criteria - they will not be accepted even in case of a shortfall. Then the applicants are selected according to an algorithm that takes into account the necessary parameters.
There may be "unstable admissions" - for example, if there are two students 1 and 2 who were accepted to colleges a and b, respectively, but the second student would like to study at university a. In the case of the described experiment, only stable connections between objects were taken into account.
Delayed Acceptance Algorithm
As already mentioned, there is a certain number of students that the college will not accept under any circumstances. Therefore, the delayed acceptance algorithm assumes that these students are not allowed to apply to this institution. In this case, all students try to get into the colleges they like best.
An institution with a capacity of q students puts on a waiting list the q highest ranked person based on its criteria, or all if the number of applicants is less than the number of available places. The rest are refused, and these students apply to the next university from their list of preferences. This college also selects q highest ranked students from those who applied immediately and those who were not accepted to the first college. Also, again, a certain number of people do not pass.
The procedure ends if each student was on the waiting list of a college or he was denied in all educational institutions where he could enter. As a result, colleges finally enroll all of their waiting lists.
What's with the proxy
Similar to students and colleges, the scientists assigned a specific proxy to each client. The result was a game called proxy assignment game. Clients, including possible censor agents, act as students who want to know the address of proxies that play the role of colleges - they have a finite bandwidth known in advance.
In the described model, there are n users (clients) A =
{a1, a2, ..., an}, which request access to a proxy to bypass locks. Thus ai is the identifier of the "total" client. Among these n users, m are censor agents, denoted as J = {j1, j2, β¦, jm}, the rest are ordinary users. All m agents are controlled by the central authority and receive instructions from it.
It is also considered that there is a set of proxies P = {p1, p2, β¦, pl}. After each request, the client receives information (IP address) about k proxies from the distributor object. Time is divided into intervals-stages, denoted as t (the game starts at t=0).
Each client uses the scoring function to evaluate the proxy. The scientists used the function 
to mark the score that user ai assigned to proxy px at stage t. Likewise, each proxy uses a feature to score clients. That is is the score assigned by proxy px to client ai at stage t.
It is important to remember that the whole game is virtual, that is, the βdistributorβ plays it on behalf of the proxy and clients. To do this, he does not need to know the type of client, their preferences regarding the proxy. At each stage, a game takes place, and a delayed acceptance algorithm is also used.
The results
According to the results of simulations, the method using game theory showed higher efficiency compared to known systems for bypassing locks.
Comparison with rBridge VPN Service
At the same time, scientists have identified several important points that can affect the quality of such systems:
- Regardless of the strategy of the censors, the blocking overcoming system must be constantly replenished with new proxies, otherwise its effectiveness will fall.
- If censors have significant resources, they can increase blocking efficiency by adding geographically dispersed proxy lookup agents.
- The speed at which new proxies are added is critical to the effectiveness of the block traversal system.
Useful links and materials from :
Source: habr.com