Super Gravitron Leet Edition (SGLE) был одним из заданий PPC в Pwn2Win 2018. Этот вызов был доступен для конкурентов только через VPN.
Описание было следующее:
Do you know the Super Gravitron by VVVVVV? Yes, Terry Cavanagh is a genius! And the bavs tasked with recruiting new programmers made a version of this game that runs on the console, and use it in their recruitment program! We're trying to infiltrate their IT sector, so we need your programming skills to beat the game, by creating a bot that can last 137 seconds in it! Instructions: 1 - You can only move horizontally, as in the original game, using the directional keys (<- and ->); 2 - The objective is "just" to avoid the obstacles; 3 - When you hit an obstacle, it will be marked with an "X". Press or to exit; 4 - Press or " to close the game at any time;" 5 - The elapsed time and the position of the Jumper(I) are shown in the game screen; 6 - Run it in full screen mode to avoid problems; ssh [email protected] Id: sgle Total solves: 0 Score: 500 Categories: PPC
В описании также была ссылка на следующее видео:
В ходе конкурса задача не была решена, но сотрудники предоставили код сервера. В связи с этим в конце года я решил доработать свое решение и написать о нем.
Это адаптация одного уровня игры VVVVVV, который игрок (I) должен выжить в течение 137 секунд, отклоняясь от объектов, которые случайным образом появляются на экране.
Связь с сервером
В игре движение игрока (I) было непрерывным, и можно было инвертировать только горизонтальные направления, которые были модульными (одна сторона экрана выходит на другую), в то время как курсор непрерывно перемещается вверх или вниз по экрану.
Поскольку соединение использует SSH, решение должно автоматически работать с сервером (я пробовал вручную, но не смог получить больше 45 с).
Первая проблема, с которой я столкнулся (и я потерял много времени, пытаясь исправить), заключалась в том, что я отправлял на сервер неправильные ключи выхода. Я написал отрывок для захвата таких ключей:
import curses
screen = curses.initscr()
tela.addstr("Screen: ")
ans = ''
while True:
key = screen.getkey()
if key == "\n":
break
ans = ans + key
curses.endwin()
print repr(ans)
И нажав влево, а затем вправо, я получил бы следующее:
'\x1b[D\x1b[C'
Несмотря на этот метод, когда я отправлял эти ключи на сервер, иногда меня отключали. Позже (намного позже) я увидел в статье про Экран, что есть и другие клавиши перехода к тем же функциям.
'\x1b0D\x1b0C'
и только в «правильном» направлении это работает хорошо.
Поскольку содержимое, полученное с сервера, необходимо читать постоянно, я попробовал несколько подходов (сокеты, pexpect, pygui), и ни один из них не смог решить проблему нестабильности. что у меня было между командами чтения и отправки.
После разговора с другим конкурентом, который также был сосредоточен на этой задаче, он прокомментировал, что у него были те же проблемы, и для их исправления требуется некоторая хитрость в процессе получения данных.
Зная, что я не единственный, кто страдает от этого, я начинаю искать решение, которое непрерывно получает контент и записывает в файл, который я мог бы читать (неблокирующий) и после этого без проблем отправлять команды. Итак, я нашел сообщение о переполнении стека со следующим фрагментом:
# make stdin a non-blocking file
fd = sys.stdin.fileno()
fl = fcntl.fcntl(fd, fcntl.F_GETFL)
fcntl.fcntl(fd, fcntl.F_SETFL, fl | os.O_NONBLOCK)где sys - это открытый процесс, который может получать ввод от пользователя при чтении содержимого, отправляемого сервером. Таким образом можно было решить задачу, несмотря на то, что некоторые кадры терялись во время игры.
Решение
Одна из первых вещей, которые я заметил в игре, - это то, что объекты (враги) на экране всегда появлялись в одних и тех же координатах (иногда меняя несколько долей секунды, но всегда повторяя), указывая на эволюционное решение.
Таким образом, для решения задачи я реализовал упрощенную версию генетического алгоритма, который учился во время игры. Я не очень разбираюсь в эволюционных алгоритмах или искусственном интеллекте, но иногда вам нужно запачкать руки.
Генетический алгоритм (ГА) - это метод поиска приблизительных решений для задач оптимизации, имитирующих поведение биологической эволюции. Архитектура GA, которую я использовал в этом решении, включает следующие компоненты: целевая функция, индивидуум, популяция, генерация, мутация и выбор.
Целевая функция - это, по сути, игра, в которую нам нужно играть, чтобы достичь флага, который является целью игры.
Индивидуальный можно рассматривать как матч, в котором мы предварительно выбрали все движения, которые будут использоваться во время игры. Например, если в игре есть 137 секунд, и мы решаем выполнять один ход в секунду, индивидуум состоит из набора из 137 ходов («влево», «вправо» или «ничего»). Пример набора движений:
+---+---+---+---+---+---- | > | > | < | | > | ... +---+---+---+---+---+---- 0 1 2 3 4 5 ..
Таким образом, набор из n особей - это популяция, которая в начале алгоритма представляет собой набор особей со «случайным» перемещением.
Затем матчи разыгрываются для каждого индивидуума, и время каждого матча является счетом, который набирает индивидуум. Чтобы собрать время во время матча, я использовал следующее регулярное выражение (адаптированное для использования в Python):
currentime = re.findall('\[\d+:\d+\].*\[(\d+.\d+)\]', screen)
screen - это строка с содержимым экрана в момент игры (неблокирующее чтение). На экране следует отметить, что есть три важных вещи, которые необходимо отслеживать (во время игры):
- Время: время в момент чтения контента.
- «X»: означает, что игра окончена из-за столкновения.
- «CTF»: флаг (я предполагаю, как должен выглядеть флаг)
Раунд, в котором разыгрываются все игры (по одной на каждого человека), называется поколением. В конце поколения у каждого человека есть свой счет, который показывает, сколько секунд он выжил в игре. В счете указывается момент, когда произошло столкновение. Из-за этого алгоритм улучшается в каждом поколении с использованием мутации, которая отвечает за изменение некоторых движений у человека, пытаясь исправить возможные ошибки во время игры для следующего поколения.
Следующее поколение состоит из индивида с лучшим результатом и нескольких выбранных индивидов со следующими характеристиками: 60% - мутации лучшего индивида (включая лучшего индивида), 30% - мутации выборки. населения и 10% - новые особи.
Мутация от лучшего индивидуума изменяет только несколько движений рядом с позицией, в которой особь проиграла игру. Вот пример изменения последних двух позиций с момента потери:
Best Individual - Score: 5
+---+---+---+---+---+-|-+---+---+---+---+---+---+
| > | | < | > | < | > | > | | < | | < | > |
+---+---+---+---+---+-|-+---+---+---+---+---+---+
+
Position where the individual lost the game
Mutated Individual (from the best individual)
+---+---+---+---+---+---+---+---+---+---+---+---+
| > | | < | > | > | | > | | < | | < | > |
+---+---+---+---+-|-+-|-+---+---+---+---+---+---+
| |
Changed Positions
Мутация выбранной особи изменяет 10% всех движений. Алгоритм выборки смещен таким образом, чтобы выбрать человека, чья оценка была достаточно хорошей (подробности в коде).
Основная идея мутации состоит в том, что оценка лучшего человека в данном поколении должна быть равна или лучше, чем лучшая оценка предыдущего поколения, пока цель не будет достигнута (137 секунд).
Выполнение решения
Из-за неблокирующего чтения иногда ухудшалась оценка. Это произошло из-за того, что есть исполнения, в которых отправленное движение не соответствовало тому же кадру, захваченному при другом выполнении. И это асинхронное поведение несколько ухудшило время, из-за чего алгоритм иногда медленно или странно сходился к ожидаемому результату.
На конкурсе я варьировал процентное соотношение между мутациями и размерами мутации и выборки, но нестабильность методов связи, которые я прокомментировал ранее, не позволила алгоритму хоть как-то улучшить, и решение не превышало 40 секунд. В какой-то момент ВМ были доработаны сотрудниками и алгоритм сумел достичь 60 секунд, но конкуренция была уже близка к завершению.
В шоу в этой статье я запустил решение с популяцией из 8 человек. В новом поколении было 6 мутировавших особей из лучшей особи (элитного отряда), один выбранный из предыдущего поколения и новый особь. В элитном отряде два человека не мутировали. Я сделал это для того, чтобы не потерять лучшего человека в тех случаях, когда возникали какие-то проблемы с чтением кадров. Индивид 3 изменяет последние шесть движений, индивид 4 получает последние девять движений, индивид 5 получает последние двенадцать движений, а индивид 6 - последние пятнадцать движений. В следующем видео показаны эти казни, которые достигают цели через 47 поколений:
Вывод
Даже несмотря на некоторые трудности (с моей стороны), это был большой вызов и уникальная возможность применить на практике некоторые концепции, которых я не касался слишком долго.
Моей первой мыслью в этой задаче было написать параллельную версию этого решения, в которой каждый человек из поколения будет запускаться параллельно, чтобы ускорить время. Поскольку у меня были проблемы на сервере (которые были решены) и при локальном чтении контента с сервера (нестабильность фреймов чтения), мне пришлось отказаться от этой идеи.
Я многому научился в этом занятии, и знаний никогда не бывает слишком много. Спасибо всем ребятам, которые организовали Pwn2Win (одну из немногих, в которую я играл в 2018 году) за отличное соревнование и испытания, проведенные в 2018 году.
Ссылка на код решения: https://github.com/318BR/CTF-2018/tree/master/Pwn2Win/PPC-SGLE
