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

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

Прелюдия

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

Stockfish

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

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

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

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

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

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

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

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

d

 +---+---+---+---+---+---+---+---+
 | r | n | b | q | k | b | n | r | 8
 +---+---+---+---+---+---+---+---+
 | p | p | p | p | p | p | p | p | 7
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 6
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 5
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 4
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 3
 +---+---+---+---+---+---+---+---+
 | P | P | P | P | P | P | P | P | 2
 +---+---+---+---+---+---+---+---+
 | R | N | B | Q | K | B | N | R | 1
 +---+---+---+---+---+---+---+---+
   a   b   c   d   e   f   g   h

Fen: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Key: 8F8F01D4562F59FB
Checkers: 

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

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

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

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

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

    setoption name Skill Level value 6
    set position fen rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
    d

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

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

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

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

    setoption name Skill Level value 6
    set position fen rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
    d
    go depth 5

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

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

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

Eval::NNUE::FeatureTransformer::UpdateAccumulator (c=BLACK, pos=..., this=0x7fffee800000) at nnue/nnue_feature_transformer.h:379
379               acc[k] = vec_add_16(acc[k], column[k]);

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

Эндшпиль

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

position fen 4kb1r/p2rqppp/5n2B2p1B1/4P3/1Q6/PPP2PPP/2K4R w - -
d
go searchmoves

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

Stockfish 291120 by the Stockfish developers (see AUTHORS file)
position fen 4kb1r/p2rqppp/5n2B2p1B1/4P3/1Q6/PPP2PPP/2K4R w - -
d

    +---+---+---+---+---+---+---+---+
    |   |   |   |   | k | b |   | r | 8
    +---+---+---+---+---+---+---+---+
    | B |   |   | p | q | B | p | p | 7
    +---+---+---+---+---+---+---+---+
    |   |   |   | P |   | n |   |   | 6
    +---+---+---+---+---+---+---+---+
    | Q |   |   |   |   |   |   |   | 5
    +---+---+---+---+---+---+---+---+
    | P | P |   |   | P | P | P |   | 4
    +---+---+---+---+---+---+---+---+
    |   | K |   |   |   |   | R | P | 3
    +---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   | 2
    +---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   | 1
    +---+---+---+---+---+---+---+---+
    a   b   c   d   e   f   g   h

Fen: 4kb1r/B2pqBpp/3P1n2/Q7/PP2PPP1/1K4RP/8/8 w - - 0 1
Key: 2CCEE92BEE2FC8B8
Checkers: f7
go searchmoves
info string NNUE evaluation using nn-62ef826d1a6d.nnue enabled
info depth 1 seldepth 1 multipv 1 score cp 801 nodes 31 nps 31000 tbhits 0 time 1 pv f7d5
info depth 2 seldepth 2 multipv 1 score cp 740 nodes 72 nps 72000 tbhits 0 time 1 pv f7d5 e7d6
info depth 3 seldepth 3 multipv 1 score cp 405 nodes 171 nps 171000 tbhits 0 time 1 pv f7d5 e7d6 h3h4 f6d5 e4d5
info depth 4 seldepth 4 multipv 1 score cp 556 nodes 206 nps 206000 tbhits 0 time 1 pv f7d5 e7d6 d5c4
info depth 5 seldepth 5 multipv 1 score cp 677 nodes 288 nps 144000 tbhits 0 time 2 pv f7d5 e7d6 a7e3
info depth 6 seldepth 7 multipv 1 score cp 787 nodes 442 nps 221000 tbhits 0 time 2 pv f7d5 e7d6 a7c5
info depth 7 seldepth 8 multipv 1 score cp 865 nodes 645 nps 322500 tbhits 0 time 2 pv f7d5 e7d6 a7c5
info depth 8 seldepth 12 multipv 1 score cp 990 nodes 1013 nps 337666 tbhits 0 time 3 pv f7d5 f6d5 d6e7
info depth 9 seldepth 12 multipv 1 score cp 912 nodes 3879 nps 646500 tbhits 0 time 6 pv f7d5 e7d6 a7c5 d6b8 d5c4 f8c5 a5c5 b8f4
info depth 10 seldepth 15 multipv 1 score cp 878 nodes 7305 nps 664090 tbhits 0 time 11 pv f7d5 e7d6 g3c3 d6b4 a5b4 f8b4 c3c8 e8e7 c8h8 b4d6 a7b8 d6c5 a4a5
info depth 11 seldepth 20 multipv 1 score cp 873 nodes 12643 nps 743705 tbhits 0 time 17 pv f7d5 e7d6 a7c5 d6c5 a5a8 e8e7 b4c5 f6d5 a8d5 h7h6 g3d3 e7f6 d5d4 f6g6 f4f5 g6h7
fish: Job 2, “./stockfish” terminated by signal SIGSEGV (Address boundary error)

Здесь нужно многое объяснить, поэтому давайте начнём с самого очевидного. Строка 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 291120 by the Stockfish developers (see AUTHORS file)
position fen 4kb1r/p2rqpp1Q6/PPP2PPP/2K4R w k
d

 +---+---+---+---+---+---+---+---+
 | Q |   |   |   | k | b |   | r | 8
 +---+---+---+---+---+---+---+---+
 | P | P |   | r | P | P | P |   | 7
 +---+---+---+---+---+---+---+---+
 |   | K |   |   |   |   | R | P | 6
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 5
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 4
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 3
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 2
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 1
 +---+---+---+---+---+---+---+---+
   a   b   c   d   e   f   g   h

Fen: Q3kb1r/PP1rPPP1/1K4RP/8/8/8/8/8 w k - 0 1
Key: A5C501AF3C69574F
Checkers: a7 
go searchmoves
.....
info depth 30 seldepth 8 multipv 1 score mate 4 nodes 25542 nps 1216285 tbhits 0 time 21 pv b6c6 d7d6 g6d6 e8f7 e7f8q h8f8 g7f8q
fish: Job 3, “./stockfish” terminated by signal SIGSEGV (Address boundary error)

Stockfish 291120 by the Stockfish developers (see AUTHORS file)
position fen 4kb1r/p2rqpp1Q6/PPP2PPP/2K4R b k
d

 +---+---+---+---+---+---+---+---+
 | Q |   |   |   | k | b |   | r | 8
 +---+---+---+---+---+---+---+---+
 | P | P |   | r | P | P | P |   | 7
 +---+---+---+---+---+---+---+---+
 |   | K |   |   |   |   | R | P | 6
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 5
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 4
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 3
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 2
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 1
 +---+---+---+---+---+---+---+---+
   a   b   c   d   e   f   g   h

Fen: Q3kb1r/PP1rPPP1/1K4RP/8/8/8/8/8 b k - 0 1
Key: 0530210BF5930C83
Checkers: e7 f7 a8 
go searchmoves
info string NNUE evaluation using nn-62ef826d1a6d.nnue enabled
info depth 0 score mate 0
bestmove (none)

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

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

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

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


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

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

Stockfish 291120 by the Stockfish developers (see AUTHORS file)
position fen 4kb1r/p1PPPppp/4RPPP/7K/8/8/8/8 b k - 0 1
d

 +---+---+---+---+---+---+---+---+
 |   |   |   |   | k | b |   | r | 8
 +---+---+---+---+---+---+---+---+
 | p |   | P | P | P | p | p | p | 7
 +---+---+---+---+---+---+---+---+
 |   |   |   |   | R | P | P | P | 6
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   | K | 5
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 4
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 3
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 2
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 1
 +---+---+---+---+---+---+---+---+
   a   b   c   d   e   f   g   h

Fen: 4kb1r/p1PPPppp/4RPPP/7K/8/8/8/8 b k - 0 1
Key: D16F5C3E2F9FABD3
Checkers: d7 
go searchmove
....
<b>bestmove e8d7 ponder e7e8q</b>

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

Stockfish 291120 by the Stockfish developers (see AUTHORS file)
position fen 4kb1r/p2rqppp/5PPP2PPP/2K4R b k
d

 +---+---+---+---+---+---+---+---+
 |   |   |   |   | k | b |   | r | 8
 +---+---+---+---+---+---+---+---+
 | p |   | P | P | P | p | p | p | 7
 +---+---+---+---+---+---+---+---+
 |   |   |   |   | R | P | P | P | 6
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   | K | 5
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 4
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 3
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 2
 +---+---+---+---+---+---+---+---+
 |   |   |   |   |   |   |   |   | 1
 +---+---+---+---+---+---+---+---+
   a   b   c   d   e   f   g   h

Fen: 4kb1r/p1PPPppp/4RPPP/7K/8/8/8/8 b k - 0 1
Key: D16F5C3E2F9FABD3
Checkers: d7 e7 

Обратите внимание, как наши зловредные входящие данные кодируются в изучаемую нами игру 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 с толку.

Эпилог

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

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

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

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

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

• Первоначальная в Twitter
• Атака #KingMe
• Название придумал Колм Маккарта

Атака Win by Segfault

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

position fen r1b2rk1pn1/7n/4o3/6Qq/2BB4/pPP2PPP/R5K1 b - - 1 0
d
+---+---+---+---+---+---+---+---+
| r |   | n |   |   | r | k |   | 8
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   | 7
+---+---+---+---+---+---+---+---+
| Q | q |   |   |   |   |   |   | 6
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   | 5
+---+---+---+---+---+---+---+---+
| P | P |   |   | B | B |   |   | 4
+---+---+---+---+---+---+---+---+
| K |   | p | P | P |   |   | P | 3
+---+---+---+---+---+---+---+---+
|   |   | R |   |   |   |   |   | 2
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   | 1
+---+---+---+---+---+---+---+---+
a   b   c   d   e   f   g   h

Fen: r1n2rk1/8/Qq6/8/PP2BB2/K1pPP2P/2R5/8 b - - 1 1
Key: 3E7AABA0F8324B04
Checkers:
go depth 10
info string NNUE evaluation using nn-62ef826d1a6d.nnue enabled
info depth 1 seldepth 1 multipv 1 score cp -666 nodes 302 nps 302000 tbhits 0 time 1 pv f8f4 a6b6 c8b6 e3f4 a8a4 a3b3
info depth 2 seldepth 2 multipv 1 score cp -794 nodes 352 nps 352000 tbhits 0 time 1 pv g8g7 a6b6
info depth 3 seldepth 3 multipv 1 score cp -903 nodes 491 nps 245500 tbhits 0 time 2 pv f8f7 a6b6 c8b6
info depth 4 seldepth 4 multipv 1 score cp -947 nodes 942 nps 471000 tbhits 0 time 2 pv b6c7 f4c7 a8a6
info depth 5 seldepth 5 multipv 1 score cp -911 nodes 1141 nps 570500 tbhits 0 time 2 pv g8h8 a6b6 c8b6

Thread 2 "stockfish" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7ffff722f700 (LWP 2540040)]
Eval::NNUE::FeatureTransformer::UpdateAccumulator (c=BLACK, pos=..., this=0x7fffee800000) at nnue/nnue_feature_transformer.h:379
379               acc[k] = vec_add_16(acc[k], column[k]);

Питер Бинделс выяснил, что к выведенной выше строке 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 является вполне правильной (хоть и маловероятной) конфигурацией доски.