Самобеглый Код 🙂

В игре CoreWars участники писали программы, которые сами клонировались в памяти и пытались затереть друг друга. Работало это в виртуальной машине с хитроумными инструкциями, которые позволяли создавать очень короткий код. Простейшая само-копирующаяся программа, «самобеглый MOV», выглядела вот так:

MOV 0, 1

Пояснение этой инструкции будет дано чуть ниже. Программа «бежит» по всему сегменту памяти, в котором происходит «битва» и затирает собою все ячейки последовательно. В языке RedCode используемом в игре эта инструкция занимает одну ячейку памяти.

Мне неизвестны реальные процессоры в которых были бы подобные «удобные» инструкции. И вот любопытно — насколько короткой можно сделать (а можно ли?) подобную «самобеглую» программу для какой-нибудь настоящей архитектуры. Ну хотя бы для 8086. Тем более что там сегменты обозримого размера — 64 килобайта.

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

Пояснение «самобеглого MOV»

В вышеупомянутой команде MOV 0, 1 сама мнемоника инструкции — это узнаваемая аббревиатура копирования данных, от слова «move». Параметров у неё два — откуда копировать (0) и куда копировать (1). Они в данной архитектуре (RedCode) обозначают адреса памяти, притом в относительной адресации, а не в абсолютной.

То есть 0 — это адрес относительно текущей выполняемой инструкции — как нетрудно догадаться, адрес ячейки где сама эта инструкция лежит. Ну а 1 — уже понятно, следующая ячейка памяти.

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

Здесь мы видим несколько особенностей RedCode которые позволили сделать этот трюк:

• инструкции оперируют над ячейками адресного пространства, не используя промежуточных каких-нибудь регистров

• адресация для данных относительна указателя на текущую инструкцию (такое в реальных процессорах бывает обычно для прыжков но не для данных)

• инструкция копирующая между адресами памяти умещается в одной ячейке (очевидно ячейка не крохотная — ведь туда должны 2 адреса поместиться и код инструкции)

Первый набросок

Итак, мы засучиваем рукава, берём ассемблер или лучше отладчик для 8086, например DEBUG.EXE и попробуем создать COM-файл который копирует свой код всё дальше и дальше. Напомню предшествующую статью которая служит инструкцией-демонстрацией к использованию этого инструмента.

Почему этот эксперимент мы делаем под «старый добрый DOS»? Да ведь в современных OS память организована во «flat memory model» обычно и с одной стороны сегменты у нас как минимум по 4 Гб, с другой программа точно не имеет доступа ко всем страницам в этом адресном пространстве.

Итак, план действий:

• получить текущий выполняемый адрес

• сделать цикл для копирования с текущего адреса на адрес больший на размер программы

• и всё? ну, пока всё…

Текущий адрес живёт в регистре IP (и меняется с каждой инструкцией). Нам бы скопировать его в регистр, который будет использоваться в качестве индекса-источника при копировании, вроде такого:

MOV SI,IP ; копируем IP в SI

заметим что в привычной для intel нотации «целевой» регистр пишется первым

К сожалению так не сделать — у процессора нет инструкций копирующих SI в другие регистры. Нужно воспользоваться тем, что при вызове подпрограммы адрес возврата копируется в стек — и из стека его вытолкнуть, например:

                   CALL next_instruction next_instruction:  POP SI                    SUB SI, 3

Сама инструкция вызова использует относительную адресацию, то есть даже после копирования в другое место кода она будет вызывать следующую инструкцию.

А в следующей инструкции мы вместо возврата из процедуры просто вытолкнем сохранённый адрес в SI — этот регистр как раз как индекс источника при копировании используется (source index).

Почему нужно вычесть 3 из него? Потому что CALL сохраняет в стек не свой собственный адрес, а адрес следующей инструкции (куда нужно вернуться) — сама инструкция занимает как раз 3 байта.

Дальше всё несложно (вроде)

Запишем в CX размер программы (сколько байт копировать) — этот регистр часто используется как счетчик цикла. А в DI поместим адрес куда копировать (destination index — он неспроста так называется) — это будет сумма SI и CX.

Сам цикл копирования можно немного по-разному написать — мы поступим так — будем использовать регистр BP как «добавку» к обоим индексам и увеличивать его на каждой итерации. Целиком это выглядит так:

Здесь XOR BP,BP — это «укороченный» способ записать 0 в BP, дальше следуют две инструкции — одна копирует из адреса [BP+SI] в AH один байт — а вторая из AH этот же байт переносит в [BP+DI — только копирование между двумя байтами памяти заняло 4 байта!

Следом идёт увеличение BP командой INC (инкремент) и волшебная команда цикла «с постусловием» — LOOP уменьшает число в CX и если оно не достигло 0 то переходит по указанному адресу.

А по этому адресу (110) как видим как раз та парочка инструкций копирования.

Последняя команда MOV SP, SI — перемещает указатель стека (на пространство перед началом текущей копии программы — адрес-то начала до сих пор в SI). Почему приходится это делать? Да ведь мы используем инструкцию CALL и значит стек должен быть «в рабочем состоянии» — а он по умолчанию живёт где-то по адресу FFFE — и когда мы туда добежим в своём копировании — мы его затрём!

Полный размер программы мы видим на этом этапе — 0x19 байт — его мы и занесем как параметр инструкции в 5й строчке (MOV CX, размер).

Вроде бы всё, но… Как это проверить?

Проверка показала…

Недолго думая, я добавил к программе несколько инструкций (не привожу их т.к. потом сделаем иначе), которые с помощью прерывания ОС (см. предыдущую статью) печатают старшие 5 бит из регистра SI (в котором мы каждый раз имеем текущий адрес) в виде одного символа (для читаемости к нему добавляется 0x40 — получаются в основном заглавные латинские буквы. Запустим и видим:

Сначала всё шло хорошо, адрес явно увеличивался (от символа «@» с кодом 0x40 до символа «_» с кодом 0x5F) — но дальше что-то пошло не так…

Немного поэкспериментировав приходим к выводу — здесь смешались 3 проблемы:

• программа из COM-файла не зря грузится с адреса 0x100 в текущем сегменте — предыдущие 256 байт используются ДОС-ом и если мы их затираем, то пользоваться системными функциями ДОС не следует

• наше упрощённое «передвигание» стека всё-таки не переживает «заворачивания» программы через границу сегмента

• если инструкция попадает на границу сегмента, происходит не то что хотелось

Последний пункт интересно пояснить подробнее, т.к. он касается архитектуры.

В реальном режиме у нас память организована в сегменты по 64 кб (65536 байт) — и сами эти сегменты идут «внакладку», через каждые 16 байт начинается следующий.

Что происходит если мы скопировали свою программу и оказалось что какая-то инструкция попадает своим началом на адрес FFFF (последний байт в сегменте) а её «хвост» уже закручивается на начало сегмента (адреса 0000, 0001, 0002…)

Это легко проверить. Например инструкция записи константы в регистр MOV AX,1234 кодируется 3 байтами B83412 — видно что первый байт это код самой инструкции — а дальше два содержат нужную константу (помним про LSB-порядок).

Отредактируем память начиная с адреса FFFF записав эти три байта, после чего установим IP на этот адрес и выполним один шаг:

видно что счётчик инструкций изменился корректно (стал 0002) да только вот 1234 в регистр AX не попало. Процессор считал команду из последовательной тройки байт не обращая внимания на границу сегмента (то есть два байта пришли из следующей области памяти, формально нам не доступной в данном сегменте).

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

Либо же выровнять размер программы так чтобы она умещалась в сегменте кратное количество раз. Например 32 или 64 байта. Ну мы так и поступим.

Рабочая версия

Чтобы обойти проблему с «повреждением» памяти используемой функциями ДОС мы просто не будем использовать их а станем визуализировать процесс прямо в видеопамяти.

А вот с проблемой «передвигания» стека возиться не хочется — уж очень костыльно выглядит всё что можно придумать. Поэтому обойдёмся без стека.

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

Мы записали 0x100 в SI, размер программы 0x40 (64 байта) поместили в CX, сложили одно с другим и результат устроили в DI как и раньше — и тут делаем маленький трюк!

DI — адрес будующей копии программы — записывается по адресу [SI+1] — то есть в параметр первой инструкции. Эту инструкцию мы уже выполнили к этому моменту, так что нам не повредит — зато когда она будет перенесена в новую копию, она окажется уже MOV SI, 0140 — и так далее будет увеличиваться с каждой копией…

Теперь насчет вывода в видеопамять. Она начинается с сегмента 0xB800 и каждый символ занимает 2 байта — в первом сам код символа — а во втором атрибуты (цвет, фон, мигание). Мы будем использовать регистр BX в качестве адреса внутри видеобуфера, увеличивая его каждый раз на 2 байта — а записывать туда будем попросту содержимое SI (адрес новой копии программы) — так что у нас будут меняться и символы и цвета.

Нужно только помнить что экран-то коротенький, 80*25 символов — то есть всего 4000 байт. Будем делить BX на эту величину и каждый раз брать остаток, чтобы наше «рисование» заворачивалось через границу экрана.

В общем этот довесок к коду выглядит теперь так:

Деление BX на 4000 (0xFAO) выполняется в первых пяти инструкциях. 8086 процессор требует поместить 32-битовое число в пару DX:AX, инструкция деления в качестве операнда указывает только один регистр — на который делим — а после этого частное попадает в AX и остаток в DX — он-то нам и нужен. Скопируем обратно в BX.

Дальше мы проставляем 0xB800 во вспомогательный сегментный регистр и запишем SI по дальнему адресу ES:[BX].

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

По адресам 130…134 у нас добавлен пустой цикл на 4096 итераций — просто задержка, чтобы визуализация наблюдалась на человеко-различимой скорости 🙂

Из прочего здесь NOP-ы которыми размер программы доведён до 0x40 байт (они идут всю дорогу до адреса 13F). И также попала инструкция CLI (запрет прерываний). Поскольку мы пользуемся только видеопамятью — хуже от неё не будет, а запретить актуально — стек-то мы точно сломаем.

Как это выглядит в результате — можно посмотреть в коротеньком видео:

https://vkvideo.ru/playlist/-20226217_-2/video-20226217_456239146

Ну а скриншот уже порадовал нас в качестве обложки к данной статье:

Заключение

В общем, реальные архитектуры явно не лучшее место для «самобеглых» программ, а уж реализации игр вроде CoreWars и Darwin конечно лучше реализовывать на искусственных ВМ — к тому же нужен и рефери-монитор.

Сам по себе «самобеглый» код у нас уместится и в 0x20 байт (всё равно нужен размер который «кратно» заполняет сегмент) — ну а с визуализацией стало примерно вдвое больше — хотя в результате довольно щедро насыпано NOP-ов.