Ранее я описывал формальную верификацию на примере задачи о Волке, Козе, и капусте.
В этой статье я перехожу от формальной верификации задач, к программам, и опишу,
каким образом можно конвертировать их в системы формальных правил автоматически.
Для этого я написал свой аналог виртуальной машины, на символьных принципах.
Она разбирает код программы и транслирует его в систему уравнений (SMT), которую уже можно решить программным способом.
Так как информация о символьных вычислениях представлена в интернете довольно обрывочно,
я вкратце опишу что это такое.
Символьные вычисления представляют собой способ одновременного выполнения программы на широком диапазоне данных и являются главным инструментом для формальной верификации программ.
Например, мы можем задать входные условия где первый аргумент может принимать любые положительные значения, второй отрицательные, третий — ноль, а выходной аргумент, к примеру, 42.
Символьные вычисления за один запуск дадут нам ответ, возможно ли получение нами нужного результата и пример набора таких входных параметров. Либо же доказательство того, что таких параметров нет.
Более того, мы можем задать входные аргументы вообще как все возможные, и выберем только выходной, например пароль администратора.
В этом случае мы найдём все уязвимости программы или же получим доказательство того, что пароль админа в безопасности.
Можно заметить, что классическое выполнение программы с конкретными входными данными представляет собой частный случай символьного.
Поэтому моя символьная VM может работать и в режиме эмуляции стандартной виртуальной машины.
Читать дальше →
source https://habr.com/ru/post/450016/?utm_campaign=450016
Комментариев нет:
Отправить комментарий