Research: creating a blocking proxy service using game theory

    A few years ago, an international team of scientists from the universities of Massachusetts, Pennsylvania and German Munich conducted a study of the effectiveness of traditional proxies as a tool to combat censorship. As a result, scientists have proposed a new method of bypassing locks based on game theory. We have prepared an adapted translation of the highlights of this work.


    The approach of popular blocking bypass tools, such as Tor, is based on the private and selective distribution of proxy IP addresses between clients from regions exposed to blocking. As a result, customers should go unnoticed by organizations or authorities that block. In the case of Tor, such proxy distributors are called bridges.

    The key problem with such services is an insider attack. Blocking agents can use proxies themselves to find out their addresses and block them. To minimize the likelihood of calculating proxies, lock bypass tools use various address assignment mechanisms.

    In this case, the approach of the so-called ad hoc heuristic is used, which can be circumvented. To solve this problem, scientists decided to present the struggle of the services involved in blocking and services to circumvent them, as a game. Using game theory, they developed optimal behavioral strategies for each of the parties - in particular, this made it possible to develop a proxy distribution mechanism.

    How traditional locking bypass systems work

    Blocking bypass tools like Tor, Lantern and Psiphon use a number of proxies outside the region with the restrictions introduced, which are used to switch the traffic of users from these regions and its delivery to blocked resources.

    If the 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 to users of a proxy occurs through 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 a proxy address disclosing.

    It is not so simple to solve this problem in practice - 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 within a single request.

    This did not stop the Chinese authorities from calculating all Tor bridges in a short time. The introduction of additional restrictions will seriously affect the usability of the bypass system, that is, some users will not be able to access the proxy.

    How game theory solves this problem

    The method described in the work is built on the so-called “college admissions game”. In addition, it is assumed that censoring Internet 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 does college entrance work?

    Suppose we have n students and m colleges. Each student compiles his 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 students who submit documents based on their own preferences.

    First of all, the college cuts off those who do not meet the selection criteria - they will not be taken even in case of shortage. Then, applicants are selected according to an algorithm that takes into account the necessary parameters.

    There may be “unstable income” - 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 relations between the objects were taken into account.

    Deferred Acceptance Algorithm

    As already mentioned, there are a certain number of students whom the college will not accept under any circumstances. Therefore, in the deferred acceptance algorithm, an assumption is made that these students are not allowed to submit documents to this university. In this case, all students try to enter the colleges that they like the most.

    An institution with a capacity of q students places a person with the highest rating on the waiting list q based on their criteria or all if the number of applicants is less than the number of free places. The others are denied, and these students apply to the next university from their list of preferences. This college also selects q students with the highest rating from among those who applied immediately and those who were not accepted to the first college. Again, a certain number of people do not pass.

    The procedure ends if each student is on the waiting list of a college or was denied all the educational institutions where he could go. As a result, colleges finally enroll all of their waiting lists.

    What does the proxy have to do with it

    By analogy with students and colleges, scientists assigned each client a specific proxy. The result is a game called proxy assignment game. Clients, including potential censorship agents, act as students who want to find out the address of proxies who play the role of colleges - they have a predetermined final throughput.

    In the described model, there are n users (clients) A =
    {a 1 , a 2 , ..., a n } who request access to the proxy to bypass locks. Thus, a i is the identifier of the “total” client. Among these n users, m are censorship agents, denoted as J = {j 1 , j 2 , ..., j m}, the rest are ordinary users. All m agents are controlled by a central authority and receive instructions from it.

    It is also believed that there is a proxy set P = {p 1 , p 2 , ..., p l }. After each request, the client receives information (IP address) about the k proxy from the distribution object. Time is divided into intervals-stages, denoted as t (the game starts at t = 0).

    Each client uses a scoring function to evaluate proxies. Scientists used the function to mark the score that user a i assigned proxies p x at stage t. Similarly, each proxy uses a function to evaluate clients. That is - the point that proxy p xassigned the client a i at stage t.

    It is important to remember that the whole game is virtual, that is, the "distributor" himself plays it on behalf of proxies and clients. To do this, he does not need to know the type of client, their preferences regarding the proxy. A game takes place at each stage, and a delayed adoption algorithm is also used.


    According to the results of the simulations, the method using game theory has shown higher efficiency in comparison with the known locking bypass systems.

    Comparison with rBridge VPN service Scientists

    have identified several important points that can affect the quality of work of such systems:

    • Regardless of the censors action strategy, the system for overcoming blockages should be constantly updated with new proxies, otherwise its effectiveness will drop.
    • If censors have significant resources, they can increase blocking efficiency by adding geographically distributed agents to search for proxies.
    • The speed of adding new proxies is critical for the effectiveness of a system to overcome locks.

    Useful links and materials from Infatica :

    Also popular now: