Методы модификации машинного кода: «селекция» vs. «генная инженерия»



    Про мифы касательно ГМО здесь уже писали. В дополнение к этому я хотел бы поделиться отличной аналогией с разбором реальных примеров из области реверс-инжиниринга и модификации машинного кода, что будет понятно и близко именно программистам.

    «Мутации» машинного кода


    В качестве примера возьмём приставку NES (известную у нас как Dendy), в которой используется процессор 6502. Система команд у него очень проста — опкод представлен всегда одним байтом, и каждый из 256 хоть что-то, да делает. Никаких «защит» от дурака не предусмотрено, и почти любой случайный набор байт будет выполняться без сопротивления со стороны процессора. Таким образом, мы можем взять ROM какой-нибудь игры, исправить в нём случайные биты (будем называть это «мутациями») — и после запуска наблюдать забавные глюки в разных неожиданных местах, но при этом в целом игра скорее всего будет работоспособной. Похоже, что на YouTube имеется целый жанр подобного видео. Полученный таким образом машинный код наверняка не очень корректен, но в большинстве случаев процессор сможет его выполнить и что-то сделать.

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

    «Генная инженерия» на машинном коде


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

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

    Понятное дело, что генетикам гораздо сложнее. Нет никакой официальной документации, которая могла бы пролить свет на все возникающие вопросы. Генетический код был «написан» волей случая и отобран по принципу «смогло ли оно выжить, приспособиться и дать потомство», поэтому наверняка он далёк от логичного и оптимального, скорее даже любая придуманная нами обфускация программного кода покажется просто детским лепетом. Тем не менее это не значит, что генетический код невозможно изучать и пробовать его изменять.

    Предыстория


    Для меня Dendy всегда была чем-то большим, чем просто приставкой. Я не только играл в неё, но и значительное время провёл внутри неё с паяльником в руках для некоторых простых модификаций. По дороге куда-нибудь я часто размышлял о том, как же создаются эти игры и как это работает внутри. Наверняка, многие из вас тоже когда-то задавались подобными вопросами, такова уж натура будущих IT-шников.

    Прошли годы. С некоторой периодичностью погружался в эму-тему, изучая всё новое на тематических сайтах, но я не решался окунуться в изучение ассемблера 6502 и архитектуры NES. Внутренний конфликт рационального и иррационального. Я долго убеждал себя, что мне не нужно тратить на это время, но… сорвался. Глядя на то, какие интересные вещи делают энтузиасты эму-сцены, я взялся за свою давнюю идею со светлой мыслью: «Я тоже смогу!».

    Наверняка многие из вас помнят картриджи типа «9999-in-1», которые были примечательны красивым меню с романтическим сюжетом у моря, летающими чайками и приятной музыкой (Unchained Melody). Я дизассемблировал это меню и сделал на его основе трибьют-демку Unchained Nostalgia.



    Основная идея — никакого списка игр, а слайды переключаются под музыку. В освободившемся небе я нарисовал осмысленные облака и звёзды; реализовал автоматическое переключение слайдов синхронно с музыкой и возможность ручного переключения; добавил автокоррекцию скорости воспроизведения и высоты звука для систем, отличных от Dendy (ведь это меню делалось именно для китайских фамиклонов, а они отличались от оригинальных NES, из-за чего оригинальное меню работает слишком быстро на NES NTSC, а на NES PAL получается слишком низкий звук); не устоял и перед соблазном добавления целого ряда любопытных пасхалок. То есть используемый подход ничем не ограничивает фантазию и позволяет в принципе вносить любые изменения за какое-то конечное время.

    Однако, похожие идеи приходят в голову разным людям


    Уже после релиза своей демки я обнаружил, что кто-то тоже пробовал реализовать эту же идею. Автор указал, что он использовал «corruptor», который обычно используется для создания испорченных версий игр с различными глюками.

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



    Слайды переключаются автоматически, примерно каждые 2 секунды (что слишком быстро). Ручного управления нет. При смене слайда экран почему-то мерцает дважды. Главное, что оно работает! Но каким образом?

    Следы хирургического вмешательства


    В картридже программный код и тайлы для графики хранятся раздельно. Код — в PRG ROM, тайлы — в CHR ROM. Второй может быть легко изменён с использованием стандартных инструментов, по этой причине для Dendy существует огромное количество графических хаков известных игр, где код оставлен абсолютно без изменений.

    Сравним CHR ROM оригинального меню и исследуемого хака:

    На лицо следы прямого «хирургического» вмешательства. По какой-то причине были вырезаны тайлы цифр, точки и маленькой чайки. Попробуем вернуть оригинальный CHR ROM и посмотрим, что именно было скрыто таким образом.



    Теперь стало немного понятнее. В программном коде был сломан ввод, из-за чего менюшка думает, что кнопка «вниз» всегда нажата. Также был сломан вывод названий игр. Видимо, сломать вывод номеров игр и маленькой чайки (это курсор, указывающий на выбранную игру) не получилось, поэтому их пришлось прятать вырезанием соответствующих тайлов в CHR ROM.

    … и немного магии!


    Копаем глубже. При помощи дизассемблера посмотрим, что именно делают «мутировавшие» в PRG ROM байты.
    Код оригинала Код хака
    NMI:
        PHA
        TXA
        PHA
        TYA
        PHA
        LDA $1E
        BEQ loc_C181
        JSR sub_C592
    loc_C181:
        LDA #0
        JSR sub_C428
    NMI:
        PHA
        TXA
        PHA
        TYA
        PHA
        LDA $1E
        BEQ loc_C181
        JSR sub_C592
    loc_C181:
        LDA #0
        JSR sub_C445
    Это обработчик прерывания NMI, который вызывается при начале отрисовки очередного кадра. Как видно, был исправлен адрес вызываемой функции. Оригинальная функция занималась считыванием состояния всех кнопок и записыванием их значений в один байт в виде битовой маски. Новый вызов выполняет только последнюю инструкцию в этой функции, которая сохраняет результат из регистра Y в переменную с маской нажатых в данный момент кнопок. Таким образом, используется мусорное значение регистра Y, которое осталось после выполнения предыдущего кода. В большинстве случаев тут оказывается мусорное значение 0x07, которое в двоичном виде выглядит как 00000111 и соответствует нажатым одновременно кнопкам «Вниз», «Влево» и «Вправо» (основной код игнорирует «Влево» и «Вправо», обрабатывая кнопку «Вниз»). Однако, сразу после переключения слайда в Y остаётся мусорное значение 0xFF, что означает, что все кнопки были нажаты одновременно, из-за чего в итоге вызывается отладочный код, который в оригинальном меню (по Left+Start+B) выводит номер ревизии на экран, что сопровождается отключением PPU на один кадр. Это и вызывает двойное мерцание экрана.
    Код оригинала Код хака
        LDA #0
        STA $2000
        STA $2001
        LDA #$22
        STA $2006
        LDA #$AC
        STA $2006
        LDA #0
        STA $2000
        STA $2001
        SBC #$22
        STA $2006
        LDA #$AC
        STA $2006
    Здесь сломан код вывода номера ревизии по Left+Start+B, поэтому хоть этот отладочный код и выполняется каждый раз из-за описанной выше проблемы, номера ревизии мы всё равно не видим на экране. Получилось это забавным образом: инструкция, что устанавливала в регистр A значение 0x22, была заменена на инструкцию, которая вычитает из регистра A число 0x22. Поскольку регистр A до этого всегда 0, получается число 0xDE. Оригинальный код устанавливал для PPU начало вывода по адресу 0x22AC в видеопамяти, что находится в пределах первой экранной страницы. Новый код, получается, устанавливает адрес 0xDEAC, что находится далеко за пределами доступной видеопамяти (максимальный разрешённый адрес — $3FFF), и в результате надпись выводится «в никуда».
    Код оригинала Код хака
        ASL A
        TAX
        LDA $EAB3,X
        STA $0A
        LDA $EAB4,X
        STA $0B
        LDY #0
    loc_C380:
        LDA ($0A),Y
        BEQ loc_C38B
        STA $2007
        INY
        JMP loc_C380
        ASL A
        TAX
        LDA $EAB3,X
        STA $FA
        LDA $EAB4,X
        STA $0B
        LDY #0
    loc_C380:
        LDA ($FA),Y
        BEQ loc_C38B
        STA $2007
        INY
        JMP loc_C380
    Здесь у нас был сломан код, который выводит названия игр. При записи указателя на выводимую строку младший байт 16-разрядного указателя записывается по адресу 0xFA вместо 0x0A, а старший байт пишется как и должен — по адресу 0x0B. Повезло, что 0xFA не использовалось, и это ничего дополнительно не сломало. Далее программа читает строку, на которую указывает пара байт 0xFA и 0xFB (0xFB всегда 0). По счастливому стечению обстоятельств, все получающиеся таким образом указатели указывают на заполненную нулями память, поэтому строки с названием игр не выводятся.

    Выводы


    Вы смогли прочувствовать, как всё «лихо закручено» в модификациях, созданных подобным «случайным» образом? Одна поломка подпирает другую поломку, и оно как-то в целом даёт результат, близкий к нужному. При этом появляются просто невероятные зависимости между случайными и на первый взгляд никак не связанными участками кода, и при малейших дальнейших модификациях (даже самих по себе корректных) всё может рухнуть. Полноценный реверс-инжиниринг гораздо надёжнее. То же самое можно сказать и о генной инженерии, в сравнении с традиционной селекцией.

    Ссылки на файлы


    • unchained_nostalgia.zip — демка Unchained Nostalgia, созданная методами реверс-инжиниринга.
    • guyver_hack.zip — исследуемый хак, созданный «случайным» образом, и его исходный ROM.
    • +23
    • 12,8k
    • 7
    Поделиться публикацией

    Комментарии 7

      +4
      Если вы хотите поразвлекаться, создавая случайные глюки в ваших любимых играх для Dendy, могу предложить вам небольшую программу на C#, которая предназначена именно для этого. Программа учитывает особенности формата iNES и вносит случайные изменения только в программный код.

      Для использования нужно запускать в консоли команды вида: mutator in.nes out.nes keyword 100, где keyword используется как randseed (то есть для одного и того же слова будет один и тот же набор случайных мутаций), а число задаёт количество мутаций (конкретно сколько байт будет испорчено).

      Программа для создания мутаций
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.IO;
      
      class NesFile
      {
      	public string FileName;
      
      	public byte[] Header;
      	public byte[] Trainer;
      	public List<byte[]> PRG;
      	public List<byte[]> CHR;
      	public byte[] Attach;
      
      	public NesFile(string filename)
      	{
      		FileName = filename;
      
      		var ROM = File.ReadAllBytes(FileName);
      		if (ROM[0] != 'N' || ROM[1] != 'E' || ROM[2] != 'S' || ROM[3] != 0x1A)
      		{
      			throw new Exception("Invalid iNES header");
      		}
      
      		Header = new byte[16];
      		Array.Copy(ROM, 0, Header, 0, 16);
      		var offset = 16;
      
      		if ((Header[6] & 0x04) != 0)
      		{
      			Trainer = new byte[512];
      			Array.Copy(ROM, offset, Trainer, 0, Trainer.Length);
      			offset += Trainer.Length;
      		}
      
      		PRG = new List<byte[]>();
      		for (var i = 0; i < Header[4]; i++)
      		{
      			PRG.Add(new byte[16384]);
      			Array.Copy(ROM, offset, PRG[i], 0, PRG[i].Length);
      			offset += PRG[i].Length;
      		}
      
      		CHR = new List<byte[]>();
      		for (var i = 0; i < Header[5]; i++)
      		{
      			CHR.Add(new byte[8192]);
      			Array.Copy(ROM, offset, CHR[i], 0, CHR[i].Length);
      			offset += CHR[i].Length;
      		}
      
      		if (ROM.Length > offset)
      		{
      			Attach = new byte[ROM.Length - offset];
      			Array.Copy(ROM, offset, Attach, 0, Attach.Length);
      		}
      	}
      
      	public void PrepareHeader()
      	{
      		Header[4] = (byte)PRG.Count;
      		Header[5] = (byte)CHR.Count;
      	}
      
      	public void Save(string filename = null)
      	{
      		PrepareHeader();
      
      		if (filename != null)
      		{
      			FileName = filename;
      		}
      
      		using (var fs = File.OpenWrite(FileName))
      		{
      			fs.Write(Header, 0, Header.Length);
      
      			if (Trainer != null)
      			{
      				fs.Write(Trainer, 0, Trainer.Length);
      			}
      
      			for (var i = 0; i < PRG.Count; i++)
      			{
      				fs.Write(PRG[i], 0, PRG[0].Length);
      			}
      
      			for (var i = 0; i < CHR.Count; i++)
      			{
      				fs.Write(CHR[i], 0, CHR[0].Length);
      			}
      
      			if (Attach != null)
      			{
      				fs.Write(Attach, 0, Attach.Length);
      			}
      		}
      	}
      }
      
      class Mutagen
      {
      	static void Main(string[] args)
      	{
      		if (args.Length < 4) return;
      		var nes = new NesFile(args[0]);
      		var rnd = new Random(args[2].GetHashCode());
      		var crb = Int32.Parse(args[3]);
      		for (int i = 0; i < crb; i++)
      		{
      			var prg = rnd.Next(nes.PRG.Count);
      			var pos = rnd.Next(nes.PRG[prg].Length);
      			var shift = rnd.Next(-2, +2);
      			int value = nes.PRG[prg][pos] + shift;
      			nes.PRG[prg][pos] = (byte)(value & 0xFF);
      		}
      		nes.Save(args[1]);
      	}
      }
      
        0
        Поделюсь балалайками (которые, в свою очередь, узнал от Mrrl). Ежели у Вас селекция, то у нас — ампутация. При нахождении в ассемблерном коде подпрограммы непонятного назначения можно заNOPить ее вызов и посмотреть, что отвалилось. Иногда это убивает работоспособность всей программы, иногда вызывает забавные глюки, но после удачного применения такой хитрости становится проще понять назначение подпрограммы.
          0
          Всё же «ампутация», на мой взгляд, больше подходит к отрезанию каких-то внешних вещей, не относящихся непосредственно к коду. В статье выше упоминается удаление некоторых тайлов в CHR ROM для того, чтобы сделать нарисованные ими элементы невидимыми.
          Ежели у Вас селекция, то у нас — ампутация.
          Не понял, почему вы говорите, что у меня селекция. Я сам занимался именно реверс-инжинирингом оригинальной менюшки, и в статье об этом сказано. Поскольку кода было немного (всего 16 килобайт), получилось разобраться в её работе на 100%, и на её основе сделать демку.
            0
            Не совсем ясно выразился. «У Вас» — это относилось к описанному у Вас в статье методу другого товарища, который занимался селекцией.
          +2
          Как же теперь легко будет матери объяснить пользу ГМО. Спасибо.
            +1
            Заходил несколько дней назад к вам на сайт, увидел обновление к Unchained Nostalgia, думаю, наверняка скоро и интересная статья появится, и вот она!

            Есть какие-то предположения, сколько потребовалось проб и ошибок для создания такого хака? Это все, полагаю, вручную проверялось?
              0
              Сколько именно времени ушло на создание хака — не знаю. Но его автор выкладывает и другие подобные хаки. Например, вот пачка странных хаков игры Battle City. На мой вопрос автор этого хака ответил лаконично:
              Как делал? Просто, но долго. Корруптором.
              Потом в процессе разговора он уточнил суть используемого им метода:
              Но не всегда случайные и не всегда случайным образом. Можно определённые на определённые. Но если ты не знаешь АСМ, дебаггеры и т.д., то только так.
              Видимо, «случайные» правки всё же как-то были приправлены интуицией. Как видно, использованная программа позволяет задавать некоторые правила для «мутаций»:
              image

              Я сам в детстве (15 лет назад) просто исправляя в HEX-редакторе байты, которые мне просто «не нравились», умудрился снять требование регистрации в одной из вариаций игры «О, счастливчик!» (я писал свой вариант этой игры, и взламывал «конкурента», который тоже был написан школьником). Просто очень сильно повезло. Плюс много терпения и сотни перезапусков с разными исправлениями :)

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое