{"id":34367,"date":"2019-10-31T21:57:56","date_gmt":"2019-10-31T18:57:56","guid":{"rendered":"https:\/\/prohoster.info\/blog\/issledovanie-sozdanie-ustojchivogo-k-blokirovkam-proksi-servisa-s-pomoshhyu-teorii-igr\/"},"modified":"2019-10-31T21:57:56","modified_gmt":"2019-10-31T18:57:56","slug":"issledovanie-sozdanie-ustojchivogo-k-blokirovkam-proksi-servisa-s-pomoshhyu-teorii-igr","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/issledovanie-sozdanie-ustojchivogo-k-blokirovkam-proksi-servisa-s-pomoshhyu-teorii-igr","title":{"rendered":"Research: Building a lock-free proxy service using game theory","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Research:<\/a><\/noindex><\/p>\n

A few years ago, an international group of scientists from the universities of Massachusetts, Pennsylvania, and Munich in Germany conducted<\/a><\/noindex> 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.<\/a><\/noindex><\/p>\n

Introduction<\/h2>\n

\nThe 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. <\/p>\n

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.<\/p>\n

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 \u2013 in particular, this allowed for the formulation of a proxy distribution mechanism.<\/p>\n

How traditional bypass systems work<\/h2>\n

\nBypass 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.<\/p>\n

If censors become aware of the IP address of such a proxy \u2013 for instance, after they have used it themselves \u2013 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. <\/p>\n

The main task is to provide users access to blocked resources and minimize the likelihood of revealing the proxy address.<\/p>\n

Solving this task in practice is quite difficult \u2014 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. <\/p>\n

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. <\/p>\n

How Game Theory Solves This Problem<\/h2>\n

\nThe 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 \u2014 for example, not blocking proxies immediately or doing so instantly depending on various conditions.<\/p>\n

How College Admissions Work
\n<\/h3>\n

\nAssume 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.<\/p>\n

First, the college eliminates those who do not meet the admission criteria \u2014 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. <\/p>\n

There can exist 'unstable admissions' \u2014 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.<\/p>\n

The Deferred Acceptance Algorithm<\/h3>\n

\nAs 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.<\/p>\n

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. <\/p>\n

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.<\/p>\n

What's the proxy for?<\/h3>\n

\nAnalogous 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 \u2013 they have a predetermined final capacity. <\/p>\n

In the described model, there are n users (clients) A =
\n{a1, a2, …, an}, which request access to proxies to bypass restrictions. Thus, ai is the identifier for the total number of clients. Among these n users, m are censorship 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. <\/p>\n

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 distribution object. Time is divided into intervals\/stages, denoted as t (the game starts at t=0). <\/p>\n

Each client uses a scoring function to evaluate the proxies. Researchers used the function. \"Research:, 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, \"Research: \u2013 the score that the proxy px assigned to the client ai at stage t.<\/p>\n

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. <\/p>\n

Results<\/h2>\n

\nBased on simulation results, the method using game theory demonstrated higher efficiency compared to known bypass systems.<\/p>\n

\"Research:
\n
\nComparison with the VPN service rBridge<\/i><\/p>\n

In this context, researchers highlighted several important factors that can affect the performance quality of such systems:<\/p>\n