Победа Segfault и другие эксплойты шахматных движков

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

Победа Segfault и другие эксплойты шахматных движков
Победа Segfault и другие эксплойты шахматных движков

Прелюдия

Universal Chess Interface (UCI) — это открытый коммуникационный протокол, позволяющий шахматным движкам общаться с интерфейсами пользователя. Он поддерживается практически каждым шахматным движком, и через этот интерфейс мы будем подключать наш «запутыватель» (фаззер, fuzzer).

Stockfish

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

Нотация Форсайта-Эдвардса (FEN)

Позиции в шахматных движках задаются через UCI при помощи команды position. Один из её вариантов — это команда position fen, использующая формат под названием нотация Форсайта-Эдвардса, сокращённо FEN (Forsyth–Edwards Notation).

Вот FEN для начальной позиции в стандартных шахматах:

Слева направо мы начинаем с позиции фигуры по горизонтали, начиная с 8 (пустые поля обозначаются числом), затем указывается активный цвет (в данном случае w — белый), после чего идут поля, относящиеся к рокировке и взятию на проходе, и, наконец, количество полуходов и полных ходов.

Отображение игрового состояния

В начале сессии UCI передача команды d приказывает движку отобразить текущую конфигурацию:

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

Начальные ходы

Приступить к запутыванию («фаззингу») UCI довольно просто. Большинство движков получает ввод по stdin, и большинство стандартных фаззеров поддерживают фаззинг по stdin. Можно начать с самого популярного сегодня фаззера afl.

Мы компилируем последнюю версию Stockfish из исходников, заменяем gcc/g++ на их аналоги из afl (это позволяет нам инструментировать приложение и повысить эффективность фаззинга; но вскоре мы увидим, что на самом деле это необязательно).

Создаём очень простой входной файл:

Даже при такой простой конфигурации мы почти сразу же можем найти крэши…

Миттельшпиль

Оказывается, что парсер FEN — довольно серьёзный источник уязвимости Stockfish. При передаче подвергнутых фаззингу входных данных FEN движок Stockfish часто вылетает. Однако большинство вылетов довольно неинтересны. Вылет движка ещё до начала игры не даёт нам никаких возможностей выиграть, и, как оказалось, мы можем добиться большего…

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

Команда go приказывает движку подумать о следующем ходе и придумать решение. У неё есть различные параметры, например, infinite и depth, позволяющие настроить длительность обдумывания и количество рассматриваемых ходов. Стоит также заметить, что фаззинг этого интерфейса может создать множество ложноположительных результатов (в частности, ложные баги unique hang, поскольку движок будет выполнять работу, а сессия фаззинга иногда путает её с тем, что программа ошибочно перешла в бесконечный цикл), но их можно спокойно игнорировать.

Мы снова занялись сессией фаззинга, и спустя множество часов обнаружили баг, который выглядел любопытнее — это был вылет, происходивший после вызова go.

Проверив его в gdb, мы увидели, что вылет происходит глубоко внутри NNUE.

NNUE (перевёрнутая EUNN, расшифровывающаяся как Efficiently Updatable Neural Network) — это часть ядра Stockfish, реализующая искусственный интеллект, благодаря которому движок стал таким сильным. Похоже, у нас появился путь к функциям вычислений в ядре Stockfish, и настало время проверить, сможем ли мы использовать их, чтобы получить преимущество над машиной.

Эндшпиль

Итак, какие же входящие данные проделали весь путь до нейросети Stockfish? (Примечание: эти входящие данные подчищены для устранения артефактов фаззинга, не относящихся к багу.)

Что происходит, когда эта информация передаётся Stockfish?

Здесь нужно многое объяснить, поэтому давайте начнём с самого очевидного. Строка FEN совершенно неправильна: position fen 4kb1r/p2rqppp/5n2B2p1B1/4P3/1Q6/PPP2PPP/2K4R w - -. Горизонталь 3 (5n2B2p1B1) кодирует 15 фигур!

Однако это интерпретируется как 4kb1r/B2pqBpp/3P1n2/Q7/PP2PPP1/1K4RP/8/8 w - - 0 1, что Stockfish считает достаточно правильным, чтобы продолжить изучение.

Внимательные читатели заметили, что, строго говоря, полученная нотация FEN недопустима — чёрным поставлен шах слоном на f7, поэтому ход не может быть за белыми. Однако вместо возврата отсутствия допустимых ходов Stockfish предлагает возможные ходы вплоть до указанной глубины, и на этом этапе вылет возникает глубоко внутри его нейронной сети.

Структура этого бага довольно проста: парсер FEN допускает слишком большие вольности, и это позволяет нам структурировать игры таким образом, чтобы запутать Stockfish. Наша следующая цель — увидеть, сможем ли мы развить этот эксплоит.

Разные игры в зависимости от того, чей ход

Рассмотрим входящие данные position fen 4kb1r/p2rqpp1Q6/PPP2PPP/2K4R w k и position fen 4kb1r/p2rqpp1Q6/PPP2PPP/2K4R b k. Это почти одинаковые (зловредные) позиции FEN, только в одной указано, что ход за белыми, а в другой — что за чёрными.

Что происходит, когда Stockfish интерпретирует эти входящие данные?

 

Несмотря на то, что полученная доска имеет одинаково недопустимую конфигурацию, поля шахов неодинаковы (и неверны). Как будто бы Stockfish использует фигуры в исходных (зловредных) входящих данных в своём анализе фигур, ставящих шах. В случае хода чёрных шах ставит фигура на e7, в случае хода белых фигуры, ставящей шах на a7, нет. Одинаковые входящие данные, две различные интерпретации и два разных результата.

Соединяем всё вместе

Теперь у нас есть все фрагменты пазла, чтобы попытаться создать достаточно реалистичную атаку на Stockfish — парсер FEN, принимающий широкий диапазон потенциально зловредных входящих данных, потенциально позволяющих нам создать игру специально для Stockfish. Эти входящие данные будут интерпретироваться Stockfish контролируемым нами способом, поскольку мы уже видели множество способов вызвать вылет внутри нейросети, когда Stockfish пытается вычислить следующий ход. Однако на самом деле мы можем сделать нечто более хитрое — убедить Stockfish, что допустимых ходов больше нет.

Давайте рассмотрим следующую позицию (ход чёрных): чёрным поставлен шах пешкой на d7, но они могут уйти из под шаха (Kxd7 или e8d7).

Победа Segfault и другие эксплойты шахматных движков

Такую игру можно закодировать как 4kb1r/p1PPPppp/4RPPP/7K/8/8/8/8 b k - 0 1, и эта игра допустима.

При обычных условиях Stockfish без проблем найдёт наилучший следующий ход для чёрных:

Теперь рассмотрим входящие данные position fen 4kb1r/p2rqppp/5PPP2PPP/2K4R b k.

Обратите внимание, как наши зловредные входящие данные кодируются в изучаемую нами игру 4kb1r/p1PPPppp/4RPPP/7K/8/8/8/8 b k - 0 1. Однако здесь есть одно серьёзное отличие — Stockfish считает, что чёрный король находится дважды под шахом, на d7 И на e7.

Когда мы пытаемся использовать Stockfish найти следующий наилучший ход, движку это сделать не удается:

go searchmove
info string NNUE evaluation using nn-62ef826d1a6d.nnue enabled
info depth 0 score mate 0
bestmove (none)

Мы успешно сбили Stockfish с толку.

Победа Segfault. Эпилог

Можно ли использовать что-нибудь из этого на практике? Можем ли мы применить какой-то из описанных здесь эксплойтов для победы в шахматной партии?

Для эксплуатации этих уязвимостей требуется, чтобы шахматный движок принимал в процессе игры состояние игры в формате FEN (или в каком-то другом формате, содержащем нашу «отравленную» строку FEN).

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

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

Другие примечания и ссылки

 

 

Атака Win by Segfault

Создав из шахматных задач более качественный корпус фаззинга, я получила пример атаки «отравленной» FEN: создаётся FEN, содержащая правильную комбинацию доски, которая при анализе приводит к segfault-ам. Вылет не всегда воспроизводится стабильно, но происходит примерно в половине случаев (в отладчике в 100% случаев. Segfault).

Питер Бинделс выяснил, что к выведенной выше строке FEN можно прийти через следующую последовательность ходов по правилам:

d3 c5
Bf4 d5
e3 e5
Qh5 g5
Qxg5 f5
Qxf5 c4
b4 c3
a4 Qe7
Qxe5 Bf5
Qxd5 Bh6
Qxf5 Qe6
Qxh7 Ne7
Qxh6 Nc8
Qg7 Nc6
Qxb7 Nd4
Qxa7 O-O
Qa6 Nxc2+
Kd1 Nd4
Be2 Nf3
Bxf3 Qb6
Be4 Qg6
Nd2 Qxg2
Kc2 Qxf2
Ngf3 Qxf3
Rhf1 Qxf1
Rc1 Qh3
Kb3 Qh6
Nc4 Qc6
Nb6 Qxb6
Rc2 Qc6
Ka3 Qb6
h3

Это показывает, что полученная строка FEN является вполне правильной (хоть и маловероятной) конфигурацией доски.

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

Источник

Original