Русский
Русский
English
Статистика
Реклама

Клики

Перевод Беспорядок встречается в более крупных графах, чем считалось ранее

24.11.2020 16:19:42 | Автор: admin

Давид Конлон и Асаф Фербер подняли нижнюю границу для значений многоцветных чисел Рамсея. Эти числа говорят о том, насколько можно увеличивать граф, пока в нём не начнут появляться неизбежные закономерности




Одни из самых упрямых чисел математики, после более 70 лет сопротивления, наконец, начинают поддаваться.

В опубликованном в сентябре четырёхстраничном доказательстве Давид Конлон и Асаф Фербер дали наиболее точную оценку многоцветным числам Рамсея. Эти числа описывают размер графов, до которого они могут вырасти перед тем, как в них начнут неизбежно проявляться определённые закономерности.

В нашей Вселенной абсолютных случайностей нет, сказала Мария Аксенович из Технологического института Карлсруэ в Германии. Всегда где-то есть скопления порядка, и числа Рамсея оценивают его количественно.

Графы это наборы точек (вершин), соединённых линиями (рёбрами). Особенно математиков интересует вопрос, сколько вершин и рёбер можно добавить в граф перед тем, как в нём начнут появляться различные подструктуры.

Если ваш граф достаточно большой, то значительная его часть будет хорошо упорядочена, сказала Мария Чудновски из Принстонского университета. Красоту сложно объяснить словами, однако это явление принято считать красивым.

Числа Рамсея относятся к определённой последовательности, монохромной клике. Это набор вершин, которые будут соединены друг с другом рёбрами одного и того же цвета после определенной процедуры раскрашивания.


Асаф Фербер из Калифорнийского университета в Ирвине

Числа Рамсея разнятся в зависимости от размера искомой клики и количества цветов, в которые вы раскрашиваете граф. Большую часть чисел Рамсея математики подсчитать не могут, поскольку почти все графы, кроме самых простых, оказывается слишком сложно анализировать напрямую.

Лучшее, на что обычно способны математики задать диапазон возможных значений чисел Рамсея. Как если бы вы хотели узнать, где находится в данный момент ваш друг, но всё, что вам удалось установить это что он где-то южнее Москвы и севернее Сочи.

Новое доказательство позволяет определить диапазон значений чисел Рамсея гораздо точнее любого результата с тех пор, как эти числа впервые начал изучать Пал Эрдёш в 1930-х и 40-х годах. Конлон из Калифорнийского технологического института и Фербер из Калифорнийского университета в Ирвине обнаружили новую нижнюю границу для многоцветных чисел Рамсея. Она получилась экспоненциально более точная, чем лучшая из предыдущих оценок. Их результат даёт математикам новый способ понять имеющую чрезвычайную важность для них схему взаимодействия порядка и случайности в графах.

Это потрясающий результат, сказала Аксенович. Мне он очень понравился.

Цветные связи


Суть чисел Рамсея, придуманных британским учёным-универсалистом Фрэнк Рамсей в 1920-х, проще всего понять на примере. Начнём с графа, состоящего из пяти вершин. Соединим каждую вершину со всеми остальными получится, как говорят математики, полный граф. Можно ли раскрасить все рёбра в синий или красный цвет так, чтобы в графе не нашлось трёх вершин, соединённых друг с другом попарно рёбрами одного цвета? В данном случае да.

Но если мы начнём с полного графа из шести вершин, раскрасить его рёбра двумя цветами, не порождая монохромную клику из трёх или более вершин, не получится. Иначе говоря, для двух цветов и размера клики 3 число Рамсея будет равным 6 (в графе должно быть не менее 6 вершин).

Числа Рамсея меняются в зависимости от количества цветов и размера искомой монохромной клики. Но в целом их сложно вычислять точные значения известны математикам только в небольшом числе случаев. Даже для небольших клик размером 5 и двух цветов лучше, что могут сказать математики по поводу числа Рамсея что оно находится в промежутке от 43 до 48.

Неловкая ситуация, сказал Ювал Уигдерсон, аспирант из Стэнфорда. Мы работаем над этой задачей уже почти 100 лет, и так ничего и не узнали.


Соедините пять вершин, сформировав полный граф. Такой граф можно раскрасить двумя цветами так, чтобы не появилось трёх вершин, соединённых рёбрами одного цвета.
Но перейдя к графу из шести вершин, уже невозможно избежать появления трёх таких вершин.


Числа Рамсея сложно подсчитать потому, что сложность графа быстро растёт с ростом количества вершин. Для графа из шести вершин и двух цветов все варианты можно перебрать вручную. Для графа из 40 вершин существует 2780 способов раскрасить рёбра в два цвета.

Приходится проверять слишком много, сказала Аксенович.

У математиков, изучающих числа Рамсея, есть байка, создание которой обычно приписывают Эрдёшу. Она описывает, насколько быстро эти вычисления становятся слишком сложными. Представьте, что на Землю вторглись инопланетяне. Они предлагают пощадить нашу планету, если мы сможем выдать правильные значения чисел Рамсея. Если они попросят нас назвать число Рамсея для случая с двумя цветами и кликами размера 5, нам нужно будет бросить все ресурсы человечества на решение этой задачи. Если же они попросят нас посчитать число Рамсея для клик размера 6, нам проще будет сразу готовиться к сражению.

Если они попросят у нас число Рамсея для [клик размера] 6, то лучше сразу атаковать, сказала Аксенович.

Изучая случайность


Поскольку подсчитать точное значение чисел Рамсея, по большому счёту, невозможно, математики вместо этого предпочитают постепенно ограничивать их значения. Они доказывают, что число больше некоего нижнего предела, и меньше верхнего предела. Новая работа улучшает эту точность для нижних пределов, но ничего не говорит о верхних.

В 1935 году Пал Эрдёш и Дьёрдь Секереш установили первую такую границу. Они применили короткое доказательство того, что числа Рамсея для двух цветов должны быть меньше, чем 4t, где t размер интересующей вас монохромной клики. Они также обнаружили, что числа Рамсея для трёх цветов должны быть меньше 27t. Через 10 лет, в 1947 году, Эрдёш подсчитал первую нижнюю границу для этих чисел: для двух цветов это (2)t вершин, а для трёх (3)t.

Между (2)t и 4t есть большая разница, особенно при очень больших значениях t. Этот разрыв отражает нечёткое понимание чисел Рамсея математиками. Однако форма границ то, как размер нужного графа выражается через размер нужной клики намекает на то, что больше всего интересно математикам.

Что мне очень хотелось бы понять это то, как растут эти числа Рамсея с ростом размера клики, сказала Лиза Сауэрман, постдок в Институте передовых исследований в Принстоне.

Поэтому самым долгоживущим вкладом Эрдёша в изучение чисел Рамсея оказались не сами границы, а метод их подсчёта. Вот, как он считал нижнюю границу.

Представьте, что у вас есть полный граф с 10 вершинами и 45 рёбрами. Представьте, что вам нужно узнать, возможно ли раскрасить рёбра тремя цветами, не создавая монохромную клику определённого размера допустим, 5 (5 вершин, соединённых 10 рёбрами).

Можно начать, как сделал Эрдёш, со случайного раскрашивания рёбер. Для каждого ребра бросим что-то вроде трёхгранного кубика и раскрасим тем цветом, который выпадет случайно. Эрдёш знал, что легко подсчитать вероятность того, что любое подмножество из 10 рёбер окажется одного цвета. Нужно просто перемножить вероятность того, что одно из рёбер будет, допустим, красным, с вероятностью того, что другое ребро будет красным, и так далее для всех десяти рёбер (то есть, 1/310). Затем он умножил то число на три, чтобы учесть тот факт, что нужную монохромную клику может породить любой из трёх разных цветов.

Потом Эрдёш посмотрел на общее количество разных клик из пяти вершин в графе. Всего их может быть 252. Наконец, он взял вероятность того, что одна из них выдаст монохромную клику, и добавил её к вероятностям того, что любая из оставшихся 251 вершины выдаст такую клику. Это т.н. подсчёт границы объединения, который даёт вероятность получения монохромной клики при случайном раскрашивании рёбер.

Пока граница объединения остаётся меньше 1, вы знаете, что метод случайной раскраски не гарантирует появления заданной монохромной клики. В нашем примере граница равна 0,0128. Это очень далеко от гарантированного появления монохромной клики в 5 вершин, а значит, для данного примера число Рамсея больше 10 вершин.

Математики называют такой подход вероятностным методом. Это гениальный обходной манёвр для решения трудных задач. Вместо того, чтобы искать примеры раскрасок, не содержащие монохромных клик различных размеров, Эрдёш просто доказал, что такие бескликовые раскраски должны существовать (поскольку граница объединения меньше 1). То есть, число Рамсея должно быть больше количества вершин графа, который мы раскрашиваем случайным образом.


Пал Эрдёш изобрёл вероятностный метод подсчёта чисел Рамсея.
1) Начинаем с полного графа из 10 вершин. При раскраске рёбер тремя цветами всегда ли можно найти 5 вершин, соединённых 10 рёбрами одного цвета?
2) Вероятность того, что конкретное ребро красное (а не синее или жёлтое) равна 1/3
3) Вероятность того, что 10 рёбер красные, равна (1/3)10
4) Всего монохромную клику могут породить три цвета.
5) Общее количество разных клик из 5 вершин равно 252.
(1/3)10 * 3 * 252 = 0,0128 вероятность получить монохромную клику при случайной раскраске рёбер.


Мы можем доказать существование чего-то, не демонстрируя его напрямую, сказал Уигдерсон.

В последовавшие 70 лет математики улучшили нижнюю границу Эрдёша для двух и трёх цветов всего однажды в 1975 году инкрементальное её улучшение провёл Джоэл Спенсер. Многие работали над этой задачей, но никому не удалось найти способа для подсчёта чисел Рамсея лучше, чем вероятностный метод. Проблема заключалась в том, чтобы попытаться обойти это [ограничение], возникающее из-за случайной выборки, сказал Конлон.

Именно это и удалось сделать Конлону и Ферберу этой осенью.

Включение порядка


Новое доказательство улучшает нижнюю границу чисел Рамсея для трёх и более цветов.

До этой работы нижняя граница для трёх цветов равнялась (3)t (примерно 1,73 t). Конлон и Фербер улучшили её до 1,834t. Для четырёх цветов они подняли нижнюю границу с 2t до 2,135t. Оба эти результата гигантские шаги вперёд. Увеличивая основание, возводимое в степень t, Конлон и Фербер доказали существование экспоненциально больших графов, раскрашенных в три и четыре цвета, у которых нет монохромных клик. Иначе говоря, показали, что беспорядок встречается в более крупных графах, чем считалось ранее.

Целью Конлона и Фербера было раскрасить полный граф, не создавая крупные монохромные клики. Они придумали для этого способ эффективного распределения одного цвета (допустим, красного) по фиксированному правилу перед тем, как применять все остальные цвета случайным образом. Этот гибридный метод дал им контроль над структурой графа, которым не обладал Эрдёш.


Давид Конлон из Калифорнийского технологического института

Фиксированное правило подразумевало распределение вершин в особом геометрическом пространстве, в котором каждая из вершин определялась набором координат. Потом они применяли двухэтапный процесс, решая, какие рёбра красить в красный цвет.

Сначала они брали координаты каждой вершины, возводили их в квадрат и складывали, получая сумму квадратов. Из-за особенности этого геометрического пространства сумма квадратов давала одну из двух величин, 0 или 1. Затем они оставляли только те вершины, чья сумма давала 0, и подсчитывали скалярное произведение пар вершин (стандартная операция для линейной алгебры). Потом они окрашивали ребро в красный, если оно соединяло пару вершин, скалярное произведение которых равнялось определённой величине.

Завершив детерминистскую часть алгоритма, Конлон и Фербер переходили к случайной. Для всех остальных рёбер они подбрасывали монетку как делал бы Эрдёш чтобы определить, будет ли оно зелёным или синим.

Этот подход оказался прекрасным способом избегать появления монохромных клик с ростом графа. Так и было задумано: парочка специально разработала детерминистский этап так, чтобы красные рёбра равномерно распределялись по всему графу. На первый взгляд они выглядели так, будто распределялись случайным образом. В самом деле, Конлон и Фербер называют эту раскраску рёбер псевдослучайной.

Псевдослучайное распределение красных рёбер достигает двух целей. Первая: разбрасывая красные рёбра по всему графу, мы гарантируем, что в нём не появятся большие красные клики (именно этого мы пытаемся избежать, желая увеличить нижнюю границу). Вторая: разбросанные по всему графу красные рёбра разбивают его на части, оставляя меньше пустых мест, которые случайно могли бы заполнить монохромные клики другого цвета.

Мы хотели убедиться, что первый цвет, который мы использовали детерминистически, уменьшал количество потенциальных клик, сказал Фербер.

Математики быстро отреагировали на новое доказательство. Уже через несколько дней после выхода Уигдерсон опубликовал следующую за этой работу, где их метод использовался для ещё одного повышения нижней границы чисел Рамсея для случая с четырьмя и более цветами. После десятилетий неподвижности, плотина чисел Рамсея была, наконец, прорвана.

Наши знания по этой теме не менялись с 40-х годов, со времён Эрдёша. Поэтому всё, что даёт нам новый подход к подобного типа вопросам, вызывает живой интерес, сказал Уигдерсон.
Подробнее..

Перевод Как в Runescape ловят пользователей ботов, и почему они не поймали меня

19.04.2021 18:14:05 | Автор: admin

Автоматизация игроков всегда была большой проблемой в глобальных многопользовательских онлайновых ролевых играх (MMORPG), таких как World of Warcraft и Runescape, и этот вид взлома игр значительно отличается от традиционных читов, например в стрелялках. Однажды в выходные я решил взглянуть на системы обнаружения, созданные компанией Jagex для предотвращения автоматизации игроков в Runescape и вот что из этого вышло.


Использование ботов

Последние несколько месяцев игрок с учётной записью sch0u играл в World 67 круглосуточно, выполняя обычные задачи, такие как убийство мобов или сбор ресурсов. На первый взгляд игрок с этой учётной записью выглядит так же, как и любой другой игрок, но есть одно ключевое отличие это бот.

Я запустил этого бота ещё в октябре, чтобы протестировать возможности системы обнаружения ботов. Я попытался найти в Интернете информацию о том, как компания Jagex борется с создателями таких ботов, и нашёл только видео коммерческих ботов, создатели которых хвастались тем, что их системы перемещения мыши неотличимы от людей.

Поэтому единственный вывод, который мне удалось сделать, заключается в том, что движение мыши имеет значение.

Эвристика!

Я начал с анализа клиента Runescape, чтобы подтвердить эту теорию, и быстро заметил глобально вызываемую переменную hhk, которая задаётся вскоре после запуска.

const auto module_handle = GetModuleHandleA(0);hhk = SetWindowsHookExA(WH_MOUSE_LL, rs::mouse_hook_handler, module_handle, 0);

В результате на мышь устанавливается низкоуровневая hook-точка, добавляя её к общесистемной цепочке hook-точек. Это позволяет приложениям в Windows перехватывать все события мыши, независимо от того, связаны они с вашим приложением или нет. Низкоуровневые hook-точки часто используются клавиатурными шпионами, однако есть и законные случаи использования, такие как эвристика, подобная вышеупомянутой hook-точке мыши.

Обработчик мыши Runescape довольно прост по своей сути (следующий псевдокод красиво переписан вручную):

LRESULT __fastcall rs::mouse_hook_handler(int code, WPARAM wParam, LPARAM lParam){  if ( rs::client::singleton )  {      // Call the internal logging handler      rs::mouse_hook_handler_internal(rs::client::singleton->window_ctx, wParam, lParam);  }  // Pass the information to the next hook on the system  return CallNextHookEx(hhk, code, wParam, lParam);}void __fastcall rs::mouse_hook_handler_internal(rs::window_ctx *window_ctx, __int64 wparam, _DWORD *lparam){  // If the mouse event happens outside of the Runescape window, don't log it.  if (!window_ctx->event_inside_of_window(lparam))  {    return;  }  switch (wparam)  {    case WM_MOUSEMOVE:      rs::heuristics::log_movement(lparam);      break;case WM_LBUTTONDOWN:case WM_LBUTTONDBLCLK:case WM_RBUTTONDOWN:case WM_RBUTTONDBLCLK:case WM_MBUTTONDOWN:case WM_MBUTTONDBLCLK:  rs::heuristics::log_button(lparam);  break;  }}

С учётом пропускной способности эти функции rs::heuristics::log_* используют простые алгоритмы для пропуска данных событий, которые похожи на предыдущие зарегистрированные события.

Эти данные события позже анализируются функцией rs::heuristics::process, которая вызывается каждым фреймом в основном цикле рендеринга.

void __fastcall rs::heuristics::process(rs::heuristic_engine *heuristic_engine){  // Don't process any data if the player is not in a world  auto client = heuristic_engine->client;  if (client->state != STATE_IN_GAME)  {    return;  }  // Make sure the connection object is properly initialised  auto connection = client->network->connection;  if (!connection || connection->server->mode != SERVER_INITIALISED)  {    return;  }  // The following functions parse and pack the event data, and is later sent  // by a different component related to networking that has a queue system for  // packets.  // Process data gathered by internal handlers  rs::heuristics::process_source(&heuristic_engine->event_client_source);  // Process data gathered by the low level mouse hook  rs::heuristics::process_source(&heuristic_engine->event_hook_source);}

Вдали от клавиатуры?

Двигаясь в обратном направлении, я прилагаю усилия, чтобы узнать, насколько релевантна рассматриваемая функция, в первую очередь путём создания и применения hook-точек или патчей для рассматриваемой функции. Обычно заключение о релевантности функции можно получить, сделав её бесполезной и наблюдая за состоянием программного обеспечения. Эта методология приводит к интересному наблюдению.

Запретив игре вызывать функцию rs::heuristics::process, я сразу ничего не заметил, но ровно через пять минут вышел из игры. По-видимому, Runescape принимает решение о неактивности игрока просто по эвристическим данным, отправленным клиентом на сервер, хотя вы можете просто отлично играть в эту игру. Это породило новый вопрос: если сервер не считает, что я играю, то считает ли он, что я использую бота?

В результате я потратил несколько дней на реконструкцию сетевого слоя игры и смог использовать бота для выполнения почти всех действий при помощи только сетевых пакетов.

Чтобы доказать свою теорию, я использовал бот двадцать четыре часа в сутки, семь дней в неделю, даже не шевеля мышкой. Прошли тысячи часов, и я могу с уверенностью заявить, что обнаружение ботов компанией либо опирается на отправленные клиентом эвристические данные событий, либо запускается только тогда, когда игрок не находится в состоянии вдали от клавиатуры. Любого игрока, которому удаётся играть, не двигая мышью, следует немедленно забанить, то есть нынешний контроль имеет смысл пересмотреть.

Уязвимостей полно не только в играх, а с ростом цифровизации различных отраслей, многие недостатки безопасности вышли наружу и требуют серьезного внимания, а значит, растёт востребованность специалистов в сфере информационной безопасности, для обучения которых мы сделали специальный курс Этичный хакер. Если вам по душе искать пробелы в защите и получать за это вознаграждение добро пожаловать.Узнай, как прокачаться и в других областях работы с данными или освоить их с нуля:

Другие профессии и курсы

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru