В процессе подготовки к вебинару (см. подпись) возник вопрос... Для машины Тьюринга (МТ) конфигурация (рантайм-снэпшот процесса вычисления) определяется как текущее состояние, в котором находится МТ, содержимое ее ленты и позиция на этой ленте. Конфигурация позволяет сделать срез по конкретной МТ, проанализировать его и продолжить вычисление. Это важнейшее понятие с т.з. анализа данной модели и исследования тех или иных нетривиальных свойств частично-рекурсивной функции (ЧРФ), которую реализует МТ. Например, понятие уязвимости конкретной ЧРФ, вычисляемой на МТ, может быть выражено, как достижимая конфигурация, при которой нарушается любое из свойств защищенности (конфиденциальность, доступность, целостность, аутентифицированность, авторизованность, неотказуемость) потоков данных, принадлежащих области ее определения или области значений. Например, в http://www.slideshare.net/kochetkov.vladimir/hdswasm-russianproofreaded/26 я рассматриваю пример МТ, уязвимой сразу в двух конфигурациях, достижимых в случае, если входные данные будут начинаться с пустого символа (тогда МТ перейдет в неопределенное состояние) или будут содержать управляющий символ # (тогда удаление символов "А" из подстроки после него осуществляться не будет). В первом случае, нарушается доступность исходной МТ и (в зависимости от конкретной реализации УМТ, которая ее выполняет), нарушение целостности программы исходной МТ. Во втором — нарушение целостности выходного потока данных (обход фильтрации символов "А"). Соответственно, в первом случае уязвимостью является конфигурация, наступающая при обработке первого символа, если этот символ пустой, а во втором — при первом срабатывании любой из функций перехода, связанных с символом #.

Стало интересно, а что является конфигурацией в эквивалентых моделях вычислений (конкретно: в λ-исчислении и нормальных алгоритмах Маркова)? Или, хотя бы, какую характеристику процесса вычисления в этих моделях можно взять за основу, чтобы дать аналогичное определение уязвимости и в них?

Для марковских алгоритмов все вроде бы достаточно просто — конфигурацией там является текущее значение слова к которому применяются формулы подстановки. Соответственно, уязвимостью в них является достижимое значение преобразуемого слова, при котором нарушается любое из свойств его защищенности. Например, если марковской алгоритм обрабатывает слово, изначально содержащее символ, который используется алгоритмом в качестве управляющего (как в случае с #), то уязвимостью в нем будет являться то состояние исходного слова, при котором впервые произойдет применение формулы подстановки, основанной на вхождении этого символа.

В λ-исчислении все как-то слегка сложнее. Насколько я понимаю, текущее состояние вычислительного процесса там можно выразить через своеобразный стек вычислений — упорядоченное множество троек (F, A, C), где F — функция, A — множество значений ее аргументов, с которыми она вычисляется и C — множество значений всех свободных переменных, на которые она ссылается (пустое для чистых функций). Следовательно, в примере с #, уязвимостью будет являться последняя в последовательности вычислений функция, область значений которой зависит от появления символа # в ее аргументах или свободных переменных.

И, поскольку мой мозг насквозь императивен и явно не принадлежит математику, возник очевидный вопрос — ошибаюсь ли я в чем-либо в двух предыдущих абзацах, особенно в последнем?