Study: Creating a lock-resistant proxy service using game theory

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

Introduction

The popular blocker bypass approach, like Tor, is based on the private and selective allocation of proxy IP addresses among clients from locking regions. As a result, customers must go unnoticed by organizations or bodies imposing blockages. In the case of Tor, such proxies are called bridges.
')
The key problem in the case of such services is an insider attack. The blocking agents can use the proxy themselves to find out their addresses and block them. In order to minimize the likelihood of a proxy computation, the lock bypass tools use various address assignment mechanisms.

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

How do traditional bypass systems work?

Locking bypass tools like Tor, Lantern and Psiphon use a number of proxies outside the region with restrictions imposed, which are used to switch users' traffic from these regions and deliver them to blocked resources.

If the censor becomes 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 one or another 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 disclosure of the proxy address.

To solve this problem in practice is not so simple - it is very difficult to distinguish between ordinary users and censors who mask themselves from them with high accuracy. Heuristic mechanisms are used to hide information. For example, Tor limits the number of bridge IPs available to clients to three per request.

This did not prevent the Chinese authorities from calculating all the Tor-breeches 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 paper is based 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 the proxy immediately or do it instantly depending on various conditions.

How is college entrance organized?

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 the documents are submitted are ranked). On the other hand, colleges also rank students who send 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 the event of a shortfall. Then, applicants are selected by an algorithm that takes into account the necessary parameters.

There may be “unstable incomes” - 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 a university a. In the case of the described experiment, only stable connections between the objects were taken into account.

Delayed acceptance algorithm

As already mentioned, there are a certain number of students whom the college will not accept under any circumstances. Therefore, the pending adoption algorithm makes the assumption that these students are not allowed to apply to this university. In this case, all students are trying to enroll in those colleges that they like the most.

The institution with a capacity of q students places on the waiting list q people with the highest rating based on their criteria or all if the number of applicants is less than the number of free places. The rest are refused, 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 taken to the first college. Also again some number of people does not pass.

The procedure ends if each student was on the waiting list of a college or was denied in all educational institutions where he could enroll. 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. It turned out a game called proxy assignment game. Clients, including potential censor agents, act as students who want to know the address of the proxy, which play the role of colleges — they have a predetermined final bandwidth.

In the described model there are n users (clients) A =
{a ₁ , a ₂ , ..., a _n }, which request access to the proxy to bypass the locks. Thus, a _i is the identifier of the “total” client. Among these n users, m are censor agents, denoted as J = {j ₁ , j ₂ , ..., j _m }, the rest are regular 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 proxy P = {p ₁ , p ₂ , ..., p _l }. After each request, the client receives information (IP-address) about the k proxy from the distributor object. Time is divided into interval-stages, denoted as t (the game starts at t = 0).

Each client uses the scoring function to evaluate the proxy. Scientists have used the function to mark the score that user a _i assigned to proxy p _x at stage t. Similarly, each proxy uses a feature to evaluate customers. I.e - the score that the proxy p _x assigned to the client a _i 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 the clients. To do this, he does not need to know the type of client, their preferences about the proxy. At each stage, a game takes place, a pending adoption algorithm is also used.

results

According to the results of simulations, the method using game theory showed a higher efficiency compared to the known blocking bypass systems.



Comparison with rbridge VPN service

At the same time, scientists have identified several important points that may affect the quality of work of such systems:

• Regardless of the censors' strategy, the system for overcoming locks must be constantly updated with new proxies, otherwise its effectiveness will fall.
• 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 the blocking system.

Useful links and materials from Infatica :

• The story of the fight against censorship: how does the flash proxy method created by scientists from MIT and Stanford
• How to understand when a proxy is lying: verification of the physical locations of network proxies using an active geolocation algorithm
• How to disguise on the Internet: compare server and resident proxies