Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

однозначно хак года: вычисления без вычислений

(может быть интересно в основном программистам)

Вот очень странный и невероятно крутой хак: trapcc - вычисление без единой инструкции CPU.

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

Известно, что одной инструкции условного перехода по вычитанию (вычисли a = a-b, и если это меньше или равно нуля, перейди в c) достаточно для Тьюринг-полноты. В этом хаке такая инструкция симулируется с помощью последовательности page faults (от невозможности загрузить данные), которая заканчивается double fault (когда указатель на стек уменьшается ниже нуля).

Несколько более подробное объяснение - в этом комментарии.

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

Как ни странно, у всего этого даже есть практические применения, правда, в области, которая ничего хорошего и полезного миру не приносит - обнаружение того, что программа бежит под отладчиком или в виртуальной машине. Ну а так - это просто неимоверно круто и красиво.
Tags: программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments