Доказательство теоремы Райса в виде кода на Питоне
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 19.04.17 20:08
Оценка:
Набросал тут %subj% в помощь тем, кто преподаёт, чтобы показывать студентам связь теоремы Райса с реальными приложениями:

analyzer_code = """
    def analyze(code, data):
        if not vulnerable(code, data):
            print("Not vulnerable!")
        else:
            while True: pass
            
         # vulnerability
         call_vulnerable_function()
    """

eval(analyzer_code)
analyze(analyzer_code, analyzer_code)


Рассматривается на примере свойства защищённости, но вместо vulnerable можно воткнуть любую функцию, якобы разрешающую любое другое свойство (ту же остановку или самоприменимость), а вместо call_vulnerable_function функцию, добавляющую это свойство в сам анализатор. Доказательство диагональное, но для того, чтобы просто показать связь с кодом, его вполне достаточно: анализатор уязвим, если анализируемая им конфигурация code-data неуязвима -> если функция vulnerable существовала бы, то анализируя самого себя, анализирующего самого себя, анализатор должен быть уязвимым и неуязвимым одновременно.

Надеюсь поможет, т.к. вопрос "ОК, но какое это имеет отношение к реальным приложениям?" возникает постоянно. И многие так и остаются убеждены в том, что это что-то из мира машин Тьюринга и к реальным вычислениям никакого отношения не имеет.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.