Мутация кода на основе llvm для генетического программирования?

Question

Для изучения генетического программирования я хотел бы реализовать эволюционную систему на основе llvm и применить кодовые мутации (возможно, на уровне IR).

Я нашел llvm-mutate, который очень полезен для выполнения точечных мутаций. Насколько я понял, инструкции подсчитываются / нумеруются, затем можно, например, удалить нумерованную инструкцию.

Тем не менее, введение новых инструкций представляется возможным в качестве одного из доступных утверждений в коде. Реальная мутация, однако, позволила бы вставить любую из разрешенных инструкций IR, независимо от того, используется ли она в коде, подлежащем мутации. Кроме того, должна быть возможность вставлять вызовы библиотечных функций связанных библиотек (не используется в текущем коде, но, возможно, доступно, потому что библиотека была связана в clang).

Я пропустил это в llvm-mutate или это действительно пока невозможно?

Есть ли какие-либо проекты, пытающиеся / уже внедрившие (ed) такие мутации для llvm?

У llvm есть много инструментов анализа кода, которые должны позволить реализацию вышеупомянутого подхода. llvm огромен, так что я немного дезориентирован. Любые советы, какие инструменты могут быть полезны (например, получение списка доступных функций библиотеки и т. Д.)?

Спасибо алекс

Answer 1

Очень интересный вопрос Я был заинтригован возможностью делать генетическое программирование двоичного уровня некоторое время. Что касается того, что вы спрашиваете:

Из их документации видно, что LLVM-mutate не может делать то, что вы просите. Тем не менее, я думаю, что не стоит этого делать. Я рассуждаю так, что любая генетическая программа на машинном языке неизбежно столкнется с "проблемой остановки", например, невозможно будет знать, приведет ли случайно сгенерированная инструкция к полному сбою всего компьютера (например, путем присвоения значения зарезервированному в ОС указатель), или он может работать вечно и занимать все циклы вашего процессора. Теорема Тьюринга говорит нам, что невозможно знать заранее, будет ли данная программа делать это. Имейте в виду, что LLVM-mutate может привести к тому, что совершенно безвредная программа все равно будет аварийно завершать работу или работать, но я думаю, что их подход делает это менее вероятным, принимая только существующие инструкции.

Однако такая вещь, как "невозможность", отпугивает только ученых, а не инженеров:-)...

Я думал следующее: в природе настоящие мутации работают гораздо больше, как LLVM-мутации, которые похожи на то, что мы делаем в обычном генетическом программировании. Другими словами, они просто меняют буквы из очень ограниченного набора (A,T,C,G), и из этого вытекают все возможные варианты. У нас может быть программа или набор программ с начальным набором инструкций плюс набор "возможных функций", связанных или определенных в программе. Большинство этих функций фактически не будут использоваться, но они будут там, чтобы обеспечить "сырую ДНК" для мутаций, как в нашей ДНК. Этот набор функций будет иметь полный (или полу-полный) набор возможных функций для проблемного пространства. Затем мы просто используем базовые операции, такие как те, что в LLVM-mutate.

Некоторые возможные проблемы, хотя:

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

• Вам все равно придется бороться с проблемой остановки мистера Тьюринга. Однако я думаю, что это можно решить, запустив решения в "песочнице", которая не подведет вас, если решение взорвется: что-то вроде одноразовой виртуальной машины или Docker-подобного контейнера с ограничением по времени (до выйти из бесконечных петель). Решение, которое дает сбой или тайм-аут, получит наихудшую возможную пригодность, так что программы будут отклоняться от этих путей.

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

Я думаю, что здесь есть потенциальный проект с открытым исходным кодом. Это было бы безумием, опасным и отвлекающим время вихрем: просто мой проект. Считайте меня, если кто-то делает это.