Модель процессора с одной командой

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

В середине 90-x, в эхо-конференции Фидо RU.HACKER, небезысвестный Solar Designer (он же Alexander Peslyak, автор таких вещей как John The Ripper и Openwall Linux), опубликовал интересную программу собственного сочинения, и предлагал попробовать ее взломать, угадав пароль, который она запрашивает и проверяет.

В отличие от большинства подобных hackme, в программе не было трюков, затрудняющих работу отладчика. Единственная трудность - это логика самой программы, так весь ее исполняемый код - это менее 100 байт интерпретатора виртуальной машины, которая умеет делать только одну операцию - NOR (или Стрелку Пирса).

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

Трюк тут в том, что указатель на текущую инструкцию находится в адресном пространстве интерпретатора, поэтому для реализации команды перехода надо просто записать значение в ячейку, где этот указатель хранится. Сам интерпретатор очень прост и может быть написан на чем угодно. В оригинальной программе он был ассемблере x86:

cld
emCPU:
mov  si,emIP
lodsw
xchg ax,di
mov  di,[di]
lodsw
xchg ax,bx
or   di,[bx]
lodsw
xchg ax,di
not  ax
mov  emIP,si
stosw
jmp  short emCPU

Но ни что не мешает перенести его в мир, например, Питона (тут вместо NOR используется NAND):

def nand(a, b):
  return ~(a & b) & 0xFFFF

def norcpu():
  while 1:
    i = mem[IP];
    a = mem[i + 0]
    b = mem[i + 1]
    r = mem[i + 2]
    mem[IP] = i + 3
    f = nand(mem[a], mem[b])
    mem[r] = f

Почему именно NOR? Из теории булевой алгебры известно, что любую из 14-ти логических функций (например, NOT, AND, OR, XOR и т.д., всего их 16) двух одно битовых аргументов можно выразить через функции NOR и NAND. Например:

NOT(a) = NAND(a, a)
AND(a, b) = NAND(NAND(a, b), NAND(b, a))
OR(a, b) = NAND(NAND(a, a), NAND(b, b))
XOR(a, b) = OR(AND(a, NOT(b)), AND(NOT(a), b)))

Пересылка данных MOVE(src, dst) может быть сделана через OR:

mem[dst] = OR(mem[src], mem[src])

Условный переход также реализуется через булеву логику. Если cond равно 0xFFFF (истина), то осуществляется переход на адрес addr, а если cond равно 0x0000, то выполнение продолжается линейно:

mem[IP] = OR(AND(addr, cond), AND(mem[IP], cond))

или в нотации интерпретатора:

AND addr, cond, @t1
AND IP, cond, @t2
OR @t1, @t2, IP

где @t1 и @t2 - некоторые вспомогательные переменные. Команды AND и OR также раскрываются в последовательность элементарных NOR, как было показано ранее.

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

Вот тут в оригинальной программе Александра был трюк, с помощью которого можно было вызывать native код x86. Так как код самого интерпретатора на ассемблере x86 также находился в адресном пространстве виртуальной машины, то в нужный момент в начало интерпретатора командой MOVE подставлялась двухбайтовая команда перехода x86 (то есть интерпретатор сам себя модифицировал), по адресу перехода которой находился нужный native код x86. После его выполнения восстанавливались оригинальные первые два байты интерпретатора, интерпретация продолжалась в обычном режиме.

Именно так была реализована команда сложения и несколько утилитарных вызовов прерываний DOS для печати на экран и ввода с клавиатуры.

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

Кроме того, если писать интерпретатор на произвольном языке, например Питоне, то для выполнения стороннего кода, который не получается реализовать в рамкам интерпретатора, надо как-то перехватывать управление, и идея машины только на одной операции NOR перестает быть "чистой".

Лирическое отступление. Я всегда интересовался reverse engineering'ом (даже сейчас не прочь покопаться IDA'ой в каком-нибудь экзешнике), и в частности различными идеями защиты от отладки. А данная идея интерпретатора одной команды тут подходит как нельзя лучше. Так как все реализовано через одну элементарную функцию, то при анализе и дизассемблировании сложно понять, где границы высокоуровневых команд. Как одну из идей, я переделал свой простейший Форт-интерпретатор с прямым шитым кодом (который сам по себе затруднен для анализа) под использование NOR интерпретатора для реализации всех низкоуровневых Форт-примитивов.

Недавно я вернулся к теме NOR-интерпретатора. Интересно было написать это на Питоне. Также пришла мысль, как можно модифицировать интерпретатор, чтобы на нем можно было бы реализоваться и полноценное сложение.

Я ввел одну дополнительную команду в него — циклический сдвиг результата каждой операции и сохранение значения в специальной ячейке-регистре:

def norcpu():
  while 1:
    i = mem[IP];
    a = mem[i + 0]
    b = mem[i + 1]
    r = mem[i + 2]
    mem[IP] = i + 3
    f = nand(mem[a], mem[b])
    mem[r] = f
    mem[S] = ((f >> 31) & 1) | ((f & 0x7FFF) << 1)

То есть теперь есть две особые ячейки: IP (instruction pointer) и S (значение последней операции, циклически сдвинутое влево).

Попробуем реализовать полное суммирование 16-х слов с переносом. Я буду писать на некотором элементарном макро-ассемблере.

Итак, полный однобитный сумматор в нотации булевой алгебры:

sum = (a ^ b) ^ carry
carry = (a & b) | (carry & (a ^ b))

Теперь на языке NOR(NAND)-процессора:

; Вход:
;  mask  - битовая маска рабочего бита (0x0001, 0x0002, 0x0004, 0x0008 и т.д.)
;  carry - перенос от предыдущего бита (бит определяется маской mask)
;  a, b  - адреса аргументов
;  r     - адрес результата
; Выход:
;  r     - результат
;  carry - перенос для следующего разряда (по отношению к mask уже сдвинут на 1 бит влево)
;  mask  - маска, сдвинутая слево на 1 бит
;
; Переменные с префиксом '@' - локальные для этого макроса.
;
!macro FADD mask, carry, a, b, r
  AND a, mask, @bit_a        ; Уберем в "a" все биты, кроме нужного.
  AND b, mask, @bit_b        ; Уберем в "b" все биты, кроме нужного.
  AND carry, mask, carry     ; Уберем в переносе все биты, кроме нужного.
  XOR a, b, @t1              ; Формула: sum = (a ^ b) ^ carry.
  XOR @t1, carry, @bit_r     ; 
  AND @bit_r, mask, @bit_r   ; Уберем из @bit_r все биты, кроме текущего 
                             ; по маске.
  OR @bit_r, r, r            ; Наложим текущий сложенный бит на результат: 
                             ; r |= sum
  AND a, b, @t2              ; Формула: carry = (a & b) | (carry & (a ^ b))
  AND carry, @t1, @t1        ;
  OR @t2, @t1, carry         ; Перенос получил новое значение. Регистр S
                             ; равен ему же, но сдвинутому влево на 1 бит. 
  MOVE S, carry              ; Теперь перенос равен себе же, но со сдвигом
                             ; влево на 1 (для суммирования в следующем бите).
  MOVE mask, mask, mask      ; Пустое присваивание mask самой себе, чтобы
                             ; получить сдвинутое значение в S.
  MOVE S, mask               ; Маска сдвинута влево на 1 бит для суммирования
                             ; следующего бита: mask = S = mask << 1

И теперь сам макрос полного суммирования:

; Вход:
;  a, b  - аргументы
;  carry - перенос (0 или 1 в младшем разряде)
; Выход:
;  r     - результат
;  carry - перенос (0 или 1 в младшем разряде)
;
; Переменные с префиксом '@' - локальные для этого макроса.
; const_1 - специальная ячейка, в которой содержится 0x0001.
;
!macro ADC a, b, carry, r
  XOR r, r, r                     ; Запишем 0 в r.
  MOVE const_1, @mask             ; Начальное значение маски: 0x0001
  *16 FADD @mask, carry, a, b, r  ; Повторяем FADD 16 раз (просто линейно в
                                  ; памяти, никаких циклов).
  AND carry, const_1, carry       ; Почистим перенос от мусора в старших
                                  ; разрядах.

Что происходить в ADC? При каждом повторении FADD происходит суммирование текущего бита, маска которого задана в mask. Просуммированный бит добавляется (через OR) в результат. Кроме этого mask автоматически сдвигается влево на 1 бит, чтобы указывать на следующей бит (0x0001 -> 0x0002 -> 0x0004 и т.д.). Также в каждом вызове FADD перенос после суммирования тоже сдвигается влево на 1 бит, чтобы быть готовым для суммирования на следующей итерации. После суммирования последнего 16-го бита перенос уйдет снова в самый младший разряд (так как интерпретатор делает циклический сдвиг), и это значение и будет результирующим переносом после всего суммирования.

Все, сложение у нас есть. Далее дело техники. Реализация стека чисто программная. Команды вызовы подпрограммы и возврата на место вызова реализуются уже через механизм стека и команд перехода.

Итак, что мы имеем в сухом остатке после муторных битовых баталий? Некую битовую виртуальную машину, на которой можно делать любые вычисления.

Машина крайне проста, но из-за этого программный код, состоящий из примитивных NOR'ов (или NAND'ов) может быть большим.

Для чего? Первое и главное: академический интерес. Прикольно же получить полноценную вычислительную среду на базе единственной операции NOR или NAND. Второе: изначально все это задумывалось как вариант защиты, например, от копирования. На данной виртуальной машине можно реализовать хитрую крипто-функцию и ей проверять валидность ключа. Таким образом к крипто-защите еще и добавится трудный анализа кода.

Но на дворе время opensource, то что повторюсь - академический интерес!

Посты по теме:

• Обмен двух переменных через XOR