Как вы думаете, существует ли недетектируемый вирус?
Начать тут нужно со строгого определения, но уже на этом этапе начинаются проблемы.
Понятно, что это псевдослучайный синтезатор программ, выход которого неотличим от случайной программы на заданном языке.
Также, наш синтезатор не обязан давать хорошие результаты на любом входе, но обязательно должен быть самоприменимым.
Но что такое случайная программа? Программы, которые написаны или могут быть написаны человеком занимают ничтожно малую часть пространства возможных программ. К тому же, они распределены неравномерно. Короче, с определением затык.
Теперь по поводу самого синтеза.
Комбинаторный синтез занимает экспоненциальное время, поэтому смотреть стоит либо в сторону дедуктивного синтеза, либо на сочетание первого и второго.
Самая примитивная форма дедуктивного синтеза выглядит примерно так:
- Спецификация на вход подается в виде программы, т.е. это трансформатор программ.
- Далее к ней применяются алгебраические законы. Например, для функциональных языков композиция ассоциативна, функция map дистрибутивна относительно композиции и т.д.
- Законы применяются в каком-то порядке, т.е. присутствует стратегия.
Чтобы подход работал на нашей задаче, нужно чтобы в нашей алгебре программ проблема эквивалентности двух термов была очень сложна. Буквами в такой алгебре будут обозначаться не примитивы языка, а какие-то сложные составные программы. Для них уже можно использовать комбинаторный синтез. Проблема здесь в том, что они сами могут быть легко детектированы. Здесь пока тоже затык.
Ну и для демонстрации схемы выше я тут написал псевдослучайный мультиквайн на языке Joy:
https://github.com/undetectablev/joytrain/
Работает все очень просто: сначала частично применяем список аксиом к паттерн матчеру, потом применяем остаточную программу к самой себе. Программы получаются не очень интересные, но в качестве прикола сойдет.
Есть какие-нибудь мысли?
