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

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

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

27.06.2016 14:27

VEG 7 8500 Источник

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

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

В качестве примера возьмём приставку 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.

Поделиться с друзьями

-->

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

VEG

27.06.2016 17:29

#9677104

Если вы хотите поразвлекаться, создавая случайные глюки в ваших любимых играх для 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]);
	}
}

pehat
27.06.2016 19:19
#9677380
Поделюсь балалайками (которые, в свою очередь, узнал от Mrrl). Ежели у Вас селекция, то у нас — ампутация. При нахождении в ассемблерном коде подпрограммы непонятного назначения можно заNOPить ее вызов и посмотреть, что отвалилось. Иногда это убивает работоспособность всей программы, иногда вызывает забавные глюки, но после удачного применения такой хитрости становится проще понять назначение подпрограммы.
1. VEG
  27.06.2016 20:01
  #9677428
  Всё же «ампутация», на мой взгляд, больше подходит к отрезанию каких-то внешних вещей, не относящихся непосредственно к коду. В статье выше упоминается удаление некоторых тайлов в CHR ROM для того, чтобы сделать нарисованные ими элементы невидимыми.
  
  Ежели у Вас селекция, то у нас — ампутация.
  Не понял, почему вы говорите, что у меня селекция. Я сам занимался именно реверс-инжинирингом оригинальной менюшки, и в статье об этом сказано. Поскольку кода было немного (всего 16 килобайт), получилось разобраться в её работе на 100%, и на её основе сделать демку.
  1. pehat
    27.06.2016 20:12
    #9677442
    Не совсем ясно выразился. «У Вас» — это относилось к описанному у Вас в статье методу другого товарища, который занимался селекцией.

Neftedollar
27.06.2016 22:23
#9677578
+2
Как же теперь легко будет матери объяснить пользу ГМО. Спасибо.

ValdikSS
28.06.2016 02:07
#9677736
+1
Заходил несколько дней назад к вам на сайт, увидел обновление к Unchained Nostalgia, думаю, наверняка скоро и интересная статья появится, и вот она!

Есть какие-то предположения, сколько потребовалось проб и ошибок для создания такого хака? Это все, полагаю, вручную проверялось?
1. VEG
  28.06.2016 15:45
  #9678654
  Сколько именно времени ушло на создание хака — не знаю. Но его автор выкладывает и другие подобные хаки. Например, вот пачка странных хаков игры Battle City. На мой вопрос автор этого хака ответил лаконично:
  Как делал? Просто, но долго. Корруптором.
  Потом в процессе разговора он уточнил суть используемого им метода:
  Но не всегда случайные и не всегда случайным образом. Можно определённые на определённые. Но если ты не знаешь АСМ, дебаггеры и т.д., то только так.
  Видимо, «случайные» правки всё же как-то были приправлены интуицией. Как видно, использованная программа позволяет задавать некоторые правила для «мутаций»:
  
  Я сам в детстве (15 лет назад) просто исправляя в HEX-редакторе байты, которые мне просто «не нравились», умудрился снять требование регистрации в одной из вариаций игры «О, счастливчик!» (я писал свой вариант этой игры, и взламывал «конкурента», который тоже был написан школьником). Просто очень сильно повезло. Плюс много терпения и сотни перезапусков с разными исправлениями :)