СиСА Вики

Appearance

PROJEKT: OVERFLOW RISC-V assembly board game ​

hack the planet

https://punkx.org/overflow/

Logo

ИГРА ​

Я создал эту игру, чтобы научить свою дочь тому, как работают переполнения буфера. Моя любимая часть в вычислениях — возможность относиться к программам как к чему-то, с чем можно играть, экспериментировать, изменять и делать их такими, какими вы хотите. Когда ваша микроволновка получает обновление и начинает зависать — вы можете её взломать. Или когда прошивка контроллера клавиатуры работает плохо — вы можете её взломать (привет, Vortex Pok3r). Сейчас ей 12 лет, но её навыки в ассемблере становятся всё лучше и лучше — надеюсь, однажды она сможет взломать свою собственную клавиатуру 😃

Игра заключается в создании небольшого шеллкода в памяти путём копирования существующих инструкций, а затем использовании переполнения буфера для перехода в него, чтобы вы могли перезаписать адрес возврата оппонента и заставить его перейти к функции game_over(). Есть и другие механики, а также дополнительные слои стратегии (например, установка обработчика исключений или «монкипатчинг»).

Все игроки используют одну и ту же память и выполняют одну и ту же программу, при этом совместно используют один процессор с операционной системой, реализующей вытесняющую многозадачность. Каждый ход игрок выполняет 10 инструкций, после чего процесс прерывается операционной системой, и наступает ход другого игрока. Указатель стека (stack pointer) каждого игрока начинается с разного адреса. Виртуальная память отсутствует.

Как выглядит игра, когда мы играем с друзьями (доказательство того, что люди действительно играют в эту игру, и также того, что у меня есть друзья):

Friends playing

С моей дочерью и собакой:

Playing with kid

Код компилируется следующей командой:

bash
riscv64-unknown-elf-gcc -fomit-frame-pointer -fno-inline-small-functions \
  -mno-shorten-memrefs -march=rv32g -mabi=ilp32 -ffreestanding -nostdlib \
  -nostartfiles -T code/link.ld -O0 -fverbose-asm -g -o game game.c

Скрипт линковщика link.ld содержит только смещения для конкретных функций, чтобы они хорошо помещались на игровом поле. Отсутствие оптимизации -O0 делает машинный код довольно многословным, но при этом понятным. Затем я использую:

bash
riscv64-unknown-elf-objdump -S -l -fd game

Паршу вывод, исправляю инструкции ▲ и ✎, конвертирую смещения переходов из шестнадцатеричного формата в десятичный, немного очищаю ассемблерный код, сопоставляю его с исходным кодом и генерирую SVG, который затем конвертирую в PDF с помощью Inkscape.

ПЕЧАТЬ ​

Предпросмотр игрового поля:

Left boardRight board

Требования к оборудованию ​

  • Принтер: предпочтительно A3, A4 тоже подойдёт, но будет немного мелко
  • Фишки: 1 фишка для свободной инструкции nop, одна фишка для адреса ловушки (trap), и по 2 фишки на игрока — одна для счётчика команд (program counter), одна для указателя стека (stack pointer). Я использую конденсаторы с обрезанными ножками или колпачки от велосипедных ниппелей
  • Карандаш и ластик

ПРАВИЛА ИГРЫ ​

✱ Настройка игрового поля:

  1. Оба игрока начинают со всеми регистрами, установленными в ноль, за исключением регистра адреса возврата (ra), который начинается со значения 1000.
  2. Указатель стека (sp) Игрока 1 инициализируется по адресу 2244.
  3. Указатель стека (sp) Игрока 2 инициализируется по адресу 3844.
  4. Фишка инструкции nop изначально не размещается на поле.
  5. Счётчики команд (pc) обоих игроков начинаются с адреса 1000 — начала функции main.
  6. Разместите фишку ловушки (trap) по адресу 1000.
  7. Все адреса памяти установлены в ноль, за исключением предварительно загруженной программы.

✱ Игровой процесс:

  1. Ходы за ход: Игроки обязаны выполнить 10 инструкций за свой ход.
  2. Выполнение инструкций: Игроки должны следовать за счётчиком команд и выполнить либо 10 инструкций, либо накопленное количество до 20. Все переходы (jal, beq и т.д.) должны соблюдаться.
  3. Приостановка выполнения: Игроки могут решить приостановить свой ход после выполнения хотя бы одной инструкции, сохранив оставшиеся инструкции для следующего хода. Максимальное накопленное количество — 20 инструкций.
  4. Монкипатч: После выполнения ровно одной инструкции в начале каждого хода игрок может переместить фишку инструкции nop на любой адрес в любой функции, которая в данный момент не выполняется игроками. Когда счётчик команд достигнет этого адреса, инструкция будет действовать как «нет операции» (nop). Перемещение фишки nop стоит игроку текущего и следующего хода, позволяя оппоненту выполнить до 20 инструкций в свой следующий ход. Механика монкипатча всё ещё несбалансирована — каждые несколько дней я немного меняю правило в попытке улучшить его, так что если у вас есть лучшая идея, дайте мне знать.

◉ Условия победы [СЛОЖНЫЙ РЕЖИМ]:

  1. Game Over: Игра заканчивается, когда один игрок успешно «взламывает» оппонента, заставляя его вызвать функцию game_over().
  2. Ничья: Возможно, игра зайдёт в состояние, когда никто не может заставить другого игрока перейти в game_over() — в этом случае игра заканчивается вничью.

⊙ Условия победы [ПРОСТОЙ РЕЖИМ]:

  1. Освобождение: Победителем становится первый игрок, вышедший из основного цикла (выполнивший ret в функции main).

✱ Специальные символы:

  1. ✎: Этот символ позволяет игрокам выбрать любое 12-битное число (от 0 до 4095) в качестве непосредственного значения в инструкции li.
  2. ▲: Этот символ позволяет игрокам выбрать значение для инструкции загрузки в пределах ±128 байт от их указателя стека. Например, если ваш sp равен 2180, вы можете выбрать значение между 2052 и 2308.

✱ Правила и ограничения:

  1. Незаконные действия: Перезапись адреса памяти ниже 1192, невыровненное чтение или запись (чтение/запись по адресу, не кратному 4) или выполнение незаконной инструкции приведёт к краху вашей программы.
  2. Обработка исключений: Крах вызывает обработчик исключений, который переходит по адресу ловушки (изначально 1000, но его можно перезаписать из функции set_trap()). После возникновения исключения счётчик команд устанавливается в указанное значение, и выполнение продолжается.
  3. Читерство/Ошибки: Если игрок читерит или допускает ошибку и его ловят, состояние его программы, включая память и регистры, сбрасывается.

Расширенные правила для большего количества игроков:

  1. Регистр указателя стека (sp) Игрока 3 устанавливается в 2116.
  2. Регистр указателя стека (sp) Игрока 4 устанавливается в 3716.
  3. Символ ▲ теперь позволяет записывать только на -128 байт от вашего указателя стека.
  4. Игра будет довольно нестабильной с более чем 2 игроками и быстро «повредится». Достичь условия победы будет сложнее, но игровой процесс станет более весёлым и хаотичным.

Подсказки и стратегии:

  1. Офензивные краши: Используйте краши как наступательную стратегию для нарушения игрового процесса оппонента.

  2. Модификация обработчика ловушек: Измените обработчик ловушек так, чтобы он указывал на функцию game_over — тогда первый игрок, получивший крах, проиграет. Внимание: фишка nop — чрезвычайно мощный инструмент, если ловушка установлена на game_over, потому что вы можете поместить её поверх ret в функции, которую в данный момент выполняет оппонент, и он проиграет.

  3. Перезапись адреса возврата: Используйте функцию bug(), чтобы перезаписать адрес возврата оппонента, переполнив индекс значением 400 или -400, что позволит получить доступ к стеку другого игрока. Например, чтобы перейти с адреса 3784 (buffer[0] с указателем стека 3780) на адрес 2184, требуется индекс -400, вычисляемый как (3784 - 2184) / 4 = 400.

  4. Создание шеллкода: Используйте функцию copy(), чтобы скопировать конкретные инструкции и сформировать компактный шеллкод в своей памяти, позволяющий произвольные записи. Используйте переполнение буфера в функции bug(), чтобы перейти в этот шеллкод. Пример простого шеллкода для произвольной записи:

    • li a4, ✎ (копировать с адреса 256, 268)
    • li a5, ✎ (доступно по адресам 136, 144, 1016 и т.д.)
    • sw a4, 0(a5) (доступно по адресам 264, 272)
    • ret (доступно по адресам 272, 200, 1060 и т.д.)

    Копирование инструкции ret приведёт к бесконечному циклу, так как адрес возврата будет установлен на начало шеллкода при переходе в него, вызывая непрерывное выполнение.

  5. Переход в память: Чтобы перейти в свою память, используйте переполнение буфера в функции bug(). Установив переменную index в значение 6, вы можете записать переменную value поверх сохранённого адреса возврата в стеке (28(sp)). При возврате из bug() программа копирует значение из 28(sp) в регистр адреса возврата. Поместите адрес созданного вами шеллкода в переменную value.

Примечание: Все переходы относительны к текущему счётчику команд, даже если они отображаются как абсолютные адреса в дизассемблере. Например, jal a4, 0 (машинный код 1903) на самом деле является бесконечным циклом при выполнении.

Список всех допустимых инструкций игры с машинным кодом от 0 до 4095 (RV32 JRI, работающие с a0, a4, a5, sp, ra)
0x00000013 (19)  addi zero, zero, 0
0x00000033 (51)  add zero, zero, zero
0x00000067 (103) jalr zero, zero, 0
0x0000006f (111) jal zero, 0
0x00000093 (147) addi ra, zero, 0
0x000000b3 (179) add ra, zero, zero
0x000000e7 (231) jalr ra, zero, 0
0x000000ef (239) jal ra, 0
0x00000113 (275) addi sp, zero, 0
0x00000133 (307) add sp, zero, zero
0x00000167 (359) jalr sp, zero, 0
0x0000016f (367) jal sp, 0
0x00000513 (1299) addi a0, zero, 0
0x00000533 (1331) add a0, zero, zero
0x00000567 (1383) jalr a0, zero, 0
0x0000056f (1391) jal a0, 0
0x00000593 (1427) addi a1, zero, 0
0x000005b3 (1459) add a1, zero, zero
0x000005e7 (1511) jalr a1, zero, 0
0x000005ef (1519) jal a1, 0
0x00000613 (1555) addi a2, zero, 0
0x00000633 (1587) add a2, zero, zero
0x00000667 (1639) jalr a2, zero, 0
0x0000066f (1647) jal a2, 0
0x00000713 (1811) addi a4, zero, 0
0x00000733 (1843) add a4, zero, zero
0x00000767 (1895) jalr a4, zero, 0
0x0000076f (1903) jal a4, 0
0x00000793 (1939) addi a5, zero, 0
0x000007b3 (1971) add a5, zero, zero
0x000007e7 (2023) jalr a5, zero, 0
0x000007ef (2031) jal a5, 0
Журнал изменений

0.0.6: заменено while(run) на while(*prun), чтобы оппонент мог намеренно вызвать краш, заставив выполнить невыровненную разыменовку; изменено правило NOP — теперь его можно размещать только в функциях, которые в данный момент не выполняются.

СИМВОЛЫ ​

Квадраты слева/справа содержат двоичное сообщение, закодированное в ASCII — попробуйте расшифровать его: белые квадраты — это 1, чёрные на чёрном — 0, используйте интервалы, чтобы понять, где находятся нули.

Цвета минимальны, чтобы люди могли печатать дёшево, и чтобы всё было чётко видно на чёрно-белых принтерах A3 и A4. Используются только цвета: красный (255,0,0), синий (0,0,255), чёрный (0,0,0) и белый (255,255,255).

Я не дизайнер, но текущий дизайн — это, возможно, 20-я итерация, и он появился после 5 часов прослушивания Making of a Cyborg из Ghost in the Shell.

Логотип проекта символизирует переполнение и сгенерирован случайным образом. Текущее случайное зерно вызвало у меня лёгкое беспокойство, поэтому я оставил его как есть.

Интервалы в логотипе и японском тексте немного смещены — это сделано для того, чтобы можно было сложить бумагу A3 пополам, не задевая текст.

Японский текст — это последние слова Короля Пиратов, Гол Д. Роджера: «Унаследованная воля, судьба эпохи и мечты людей. Пока люди продолжают стремиться к смыслу Свободы, эти вещи никогда не перестанут существовать!»

Без подсветки синтаксиса. Я не использую подсветку синтаксиса и не учу свою дочь её использовать. У меня нет сильных предпочтений, но подсветка заставляет думать, что определённые вещи в коде важнее других (в зависимости от темы). Без подсветки я могу сам решать, на чём сосредоточиться, и легко фокусироваться на том, что считаю важным.

БЛАГОДАРНОСТИ ​

Я хочу поблагодарить Питера, Уильяма, Шантану, Рареса и мою дочь, которые сыграли в 50 разных версий игры — все они были довольно плохими 😃, но они не сдались. Спасибо tn1, который очень помог мне с дизайном, особенно указывая на то, что не работает.

Также большая благодарность людям, работающим над шрифтом Terminus — это абсолютная красота.

Отдельное спасибо эмулятору tinyfive от OpenMachine, который я использовал для тестирования игры, пока не написал свой собственный для веб-версии.

Спасибо gamesounds.xyz за .wav-файлы для веб-версии, а также Карлу Кейси @ White Bat Audio за фоновую музыку.

И, конечно, огромная благодарность людям, работающим над RISC-V — с ним супер-весело работать.

Большое спасибо @matsuu за указание на опечатку в японском написании.

КОНТАКТЫ ​

Email: jackdoe@fastmail.com

Если у вас есть идея по поводу другого игрового поля или правил, или вы нашли ошибку в поле или онлайн-версии — пожалуйста, напишите мне. Также оказалось, что я могу играть в эту игру с дочерью и примерно двумя людьми из всего моего списка контактов 🥹, так что если вам понравилось играть — я буду рад услышать об этом.

РУКОВОДСТВО ПО АССЕМБЛЕРУ ​

Вы можете найти множество руководств по ассемблеру RISC-V, например:

И множество интерпретаторов, например:

И декодеры, например rvcodecjs от luplab — отличный декодер инструкций: введите туда 0x13 (инструкция nop) и посмотрите, как она декодируется.

Если у вас возникают трудности, вы также можете поискать на YouTube «risc v assembly tutorial» — там много действительно хороших видео. К сожалению, я не уверен, какое подойдёт именно вам, так что не унывайте и просто попробуйте несколько из них.

Я подготовил упражнения для своей дочери: каждый день я печатал несколько шаблонов памяти и несколько примеров кода ниже, и она просто выполняла инструкции. Иногда я менял код на лету или тратил больше времени на объяснение, например, приведения типов и структур. Но базовый ассемблер RISC-V она смогла понять довольно быстро.

Версия «Виселица» — это тот же обычный PDF, но некоторые инструкции ассемблера пропущены, и вам нужно их вписать:

Hangman example

Если вам нужно подтянуть знания по C, мы используем руководство Бижда: Beej's Guide to C Programming, особенно первые 7–8 глав. Но есть много других отличных ресурсов. Вы также можете использовать следующие примеры ассемблера, чтобы освежить знания по C — хороший пример: упражнение с указателями:

Pointers exercise

Когда вы печатаете упражнение и шаблон памяти, это выглядит так:

Printed example

Список выполненных упражнений:

Все изображения и ссылки сохранены в оригинальном формате. Для корректного отображения некоторых элементов (например, <details>) в вашем Markdown-просмотрщике может потребоваться поддержка HTML.

Контакты: bystrovno@basealt.ru

© 2025 – настоящее время, Никита Б. Разработано на VitePress.