ВПнМ/Теормин

Материал из eSyr's wiki.

Перейти к: навигация, поиск

Содержание

Лекция 1

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

Верификация - исследование и обоснование того, что программа соответствует своей спецификации.

Верификация в общем случае алгоритмически неразрешима.

Методы верификации:

  • "Полное" тестирование (слайды 14-22)
  • Имитационное моделирование
  • Доказательство теорем (27-29)
  • Статический анализ (30-33)
  • Верификация на моделях (34-38)

Моделирование и абстракция

Моделирование программ. Понятие состояния. Потенциальные и достижимые состояния. Требования к модели. Процесс построения модели.

Схема верификации на моделях (Лекция 2, слайд 3)

Состояние программы - совокупность значений переменных и управления, связанных с некоторой моделью программы.

Модель - упрощённое описание реальности, выполненное с определенной целью.

  • с каждым объектом может быть связано несколько моделей
  • каждая модель отражает свой аспект реальности

Аспекты модели:

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

Построение модели

  1. формализация требований (постановка задачи моделирования)
  2. выбор языка моделирования
  3. абстракция системы до модели с учётом требований

Моделирование программ. Размеченные системы переходов. Детерминизм и недетерминизм. Вычисления и трассы. Свойства линейного времени. Выполнимость свойства на трассе.

Размеченная система переходов (LTS)

TS = \langle S, Act, \overset{a}{\rightarrow} ,s_0, AP, L \rangle

  • S - множество состояний
  • Act - множество действий
  • τ - невидимое действие
  • \overset{a}{\rightarrow} \subseteq S \times Act \times S - тотальное отношение переходов
  • s_0 \in S - начальное состояние
  • AP - множество атомарных высказываний
  • L:S \rightarrow 2^{AP} - функция разметки

S, Act - конечные или счётные множества

\langle s, a, s' \rangle \in \overset{a}{\rightarrow} \equiv s \overset{a}{\rightarrow} s'

Пример LTS: Лекция 2, слайд 40-41

Прямые потомки

  • Post(s, a) = \{s' \in S, s \overset{a}{\rightarrow} s'\} - такие состояния s', которые непосредственно вытекают из s через переход a
  • Post(s) = \bigcup_{a \in Act} Post(s, a) - все возможные состояния s', которые непосредственно вытекают из s

Система TS = <S, Act, \overset{a}{\rightarrow} ,s_0, AP, L> детерменирована:

  • по действиям тогда и только тогда, когда
    • |I| \leqslant 1
    • \forall s \in S, \forall a \in Act \Rightarrow |Post(s, a)| \leqslant 1
  • по атомарным высказываниям
    • |I| \leqslant 1
    • \forall s \in S, \forall A \in 2^{AP} ~ \Rightarrow ~ |Post(s) \cap \{s' \in S, L(s') = A\}| \leqslant 1 ( количество одинаково размеченных потомков не больше одного )


Недетерменизм - это фича! Полезен для:

  • моделирования параллельного выполнения в режиме чередования (интерливинга)
    • позволяет не указывать скорость выполнения процессов
  • моделирования прототипа системы
    • не ограничивает реализацию заданным порядком выполнения операторов
  • построения абстракции реальной системы
    • модель может быть построена по неполной информации

Вычисления

  1. Конечный фрагмент вычисления σ системы переходов TS называется конечная последовательность чередующихся состояний и действий \sigma = s_0 a_1 s_1 a_2 s_2 \dots a_n s_n, \forall i \in [0,n] \Rightarrow s_i \overset{a_{i+1}}{\rightarrow} s_{i+1}
  2. Бесконечный (максимальный) фрагмент вычисления ρ - \rho = s_0 a_1 s_1 a_2 s_2 \dots, \forall i \geqslant 0 \Rightarrow s_i \overset{a_{i+1}}{\rightarrow} s_{i+1}
  3. Начальный фрагмент вычисления - фрагмент вычисления, для которого s_0 \in I
  4. Вычисление - начальный максимальный фрагмент вычисления

Достижимое состояние (из начального) в системе переходов TS - такое состояние s \in S, для которого существует конечный фрагмент вычисления s_0 a_1 s_1 a_2 s_2 \dots a_n s_n = s

Rich(TS) - множество всех достижимых состояний в TS

Трасса tr = L(s_0) L(s_1) \dots \in (2^{AP})^\omega

Свойства линейного времени

  • Свойство \varphi определяет набор допустимых трасс: \varphi \in (2^{AP})^\omega
  • Система переходов TS удовлетворяет свойству линейного времени \varphi
    • TS \models \varphi ~~ \Leftrightarrow ~~ Traces(TS) \subseteq \varphi
    • TS(P) \models \varphi ~~ \equiv ~~ P \models \varphi

Моделирование программ. Графы программ. Статическая и операционная семантика.

Граф программы – формальное описание текста программы.

  • Dp -- единый абстрактный домен данных.
  • P -- программа.
    • Vp -- множество переменных программы(Var).
  • v \in Var
    • dom(v) = D_p^v \subseteq D_p -- каждая переменная принадлежит какому-либо домену
  • n -- подстановка. n: V_p \rightarrow D_p, \forall v \in Var n(v) \in D_p^v
  • Cond(Vp) -- Набор булевых условий над Vp
    • формулы пропозициональной логики
    • условия на переменные
  • Эффект операторов: Effect: Act \times Eval(Var) \rightarrow Eval(Var)

Граф программы:

PG= \langle Loc , Act , Effect ,\rightarrow, Loc_0, g_0 \rangle

  • Loc -- множество точек
    • Loc_0 \in Loc -- множество начальных точек
  • Act -- множество действий
  • \rightarrow : Loc \times (Cond(V_p) \times Act) \times Loc -- отношение перехода (Cond(Vp) -- это фактически страж оператора )
  • Effect -- функция эффекта
  • g_0 \in Cond(V_p) -- начальное условие

Получение TS из PG: раскрутка графа

  • Состояние в TS -- это точка программы и текущая подстановка
  • Начальное состояние -- исходная точка, удовлетворяющая начальному условию
  • Атомарные высказывания в TS:
    • находимся в точке программы l
    • значение переменной x принадлежит некоторому множеству и это множество является подмножеством множеств значений этой переменной.
  • Состояния < l,n > размечаются высказыванием о том, то мы находимся в точке программы l и всеми высказываниями, истинными в n
  • Если в графе программы есть дуга из l в l' со стражем g и действием a и в некоторой подстановке n выполняется страж g, то в системе переходов, которая соответствует этой программе будет присутствовать дуга из состояния < l,n > в состояние < l',Effect(a,n) > по действию a.

Системы переходов графов программ Операционная семантика -- как из TS(PG) -- система переходов графа программы PG= \langle Loc , Act , Effect ,\rightarrow, Loc_0, g_0 \rangle задается сигнатурой \langle S, Act, \rightarrow, I, AP, L \rangle

  • S = Loc \times Eval(V_p)


Пример: Лекция 4, слайд 16

Параллелизм. Чередование систем переходов.

Параллелизм. Чередование графов программ. Случаи без разделяемых переменных и с разделяемыми переменными.

Параллелизм. Синхронный параллелизм. Рандеву.

  • распределённые программы выполняются параллельно
  • в распределённой программе нет разделяемых переменных

Передача сообщений в распределённых программах:

  • cинхронная передача сообщений (рандеву)
  • асинхронная передача сообщений (кналы)

Синхронный обмен сообщенийями:

  • Процессы вместе выполняют синхронизированные действия
  • Взаимодействие процессов - одновременно

Рандеву

  • TS_i = \langle S_i, Act_i, \overset{a}{\rightarrow}_i ,I_i, AP_i, L_i \rangle ~~~ i=\{1,2\}
  • H \subseteq Act_1 \cap Act_2

Тогда TS_1 ||_H = \langle S_1 \times S_2, Act_1 \cup Act_2, \rightarrow, I_1 \times I_2, AP_1 \cup AP_2, L \rangle, где

  • L(\langle s_1, s_2 \rangle) = L_1(s_1) \cup L_2(s_2)
  • \rightarrow определяется как:
    • интерливинг для \alpha \not\in H~:~~~ \frac{s_1 \overset{a}{\rightarrow}_1 s_1'}{ \langle s_1, s_2 \rangle \overset{a}{\rightarrow} \langle s_1', s_2 \rangle} и \frac{s_2 \overset{a}{\rightarrow}_2 s_2'}{ \langle s_1, s_2 \rangle \overset{a}{\rightarrow} \langle s_1, s_2' \rangle}
    • рандеву для \alpha \in H~:~~~ \frac{s_1 \overset{a}{\rightarrow}_1 s_1' ~ \wedge ~ s_2 \overset{a}{\rightarrow}_2 s_2'}{ \langle s_1, s_2 \rangle \overset{a}{\rightarrow} \langle s_1', s_2 \rangle}


Пример рандеву: Лекция 4, слайд 32


Синхронный параллелизм

  • TS_i = \langle S_i, Act_i, \overset{a}{\rightarrow}_i ,I_i, AP_i, L_i \rangle ~~~ i=\{1,2\}
  • Act_1 \times Act_2 \rightarrow Act ~~ : ~~ (\alpha, \beta) \rightarrow \alpha * \beta

Тогда TS_1 \times TS_2 = \langle S_1 \times S_2, Act, \rightarrow, I_1 \times I_2, AP_1 \cup AP_2, L \rangle , где

  • L(\langle s_1, s_2 \rangle) = L_1(s_1) \cup L_2(s_2)
  • \rightarrow определяется как: \frac{s_1 \overset{\alpha}{\rightarrow}_1 s_1' ~ \wedge ~ s_2 \overset{\beta}{\rightarrow}_2 s_2'}{ \langle s_1, s_2 \rangle \overset{\alpha * \beta}{\rightarrow} \langle s_1', s_2 \rangle}

Параллелизм. Асинхронный параллелизм. Системы с каналами. Операционная семантика.

Абстракция. Абстракция трасс. Абстракция системы переходов. Необходимое и достаточное условие корректности LTS модели.

Представим трассу в форме интерпретации I: I(tr) = <N, \leqslant, \xi>

  • N - множество натуральных чисел
  • \leqslant - отношение порядка на N
  • \xi: N \times AP \rightarrow \{true, false\}, ~~ \forall n>0, p \in AP ~~ \Rightarrow ~~ \xi(n, p) = true \Leftrightarrow p \in L(s)

Рассмотрим трассы tr и tr' такие, что

  • I(tr) = <N, \leqslant, \xi>, ~~ \xi: N \times AP = \{true, false\}
  • I(tr) = <N, \leqslant, \xi'>, ~~ \xi: N \times AP' = \{true, false\}

Будем говорить, что трасса tr' является абстракцией трассы tr, если

  1. AP' \subseteq AP
  2. \exists \alpha : N \rightarrow N такое, что \forall n,k \in N, n \leqslant k ~~ \Rightarrow ~~ \alpha(n) \leqslant \alpha(k)
  3. \forall n \in N, p \in AP' ~~ \Rightarrow ~~ \xi(n, p) = \xi'(n, p)

Пример абстракции трассы: Лекция 2, слайд 53

Необходимое условие корректности модели - \forall tr \in Traces(TS(P)) ~ \exists tr' \in Traces(TS(M)) ~ : ~ tr \leqslant tr', где

  • P - система
  • M - модель этой системы

При этом, если \varphi - некоторое свойство системы, то M \models \varphi ~ \Rightarrow ~ P \models \varphi выполняется тогда и только тогда, когда верно условие корректности модели.

Абстракция. Абстракция системы переходов. Достаточное условие корректности LTS модели. Адекватность LTS модели.

Абстракция системы переходов -- картинка на 4 слайде 3-й лекции.

Достаточное условие корректности LTS модели.

Пусть у нас имеются две системы переходов, TS1 и TS2 -- для системы и модели соответственно:

TS^i = \langle S^i, Act^i, \rightarrow_i, I^i, AP^i, L^i \rangle

Достаточное условие корректности:

  • Алфавит предикатов модели включен в алафвит предикатов системы: AP^2 \subset AP^1
  • Задано отображение a: S^1 \rightarrow S^2. На отображение накладываются следующие условия:
    • Оно преобразует начальное состояние системы в начальное состояние модели: s^2_0 = a(s^1_0)
    • Каждому переходу из системы должен соответствовать переход в модели: s^1_1 \rightarrow_1 s^1_2 ~ \Rightarrow ~ a(s^1_1) \rightarrow_2 a(s^1_2)
  • Метки на состояниях модели должны состоять только из предикатов модели: \forall s \in S^1: L^2(a(s)) = L^1(s) \cap AP^1

Достаточное условие адекватности модели свойствам правильность  :

Алфавит предикатов свойств правильности включен в алфавит предикатов модели.

Абстракция. Абстракция графов программ. Отношение слабой симуляции.

Логика LTL, автоматы Бюхи

Свойства правильности. Формулирование требований правильности программы. Двойственность. Типы свойств.

  • Требования правильности задаются как утверждения о возможных и невозможных вариантах выполнения программы.
  • Некоторые варианты выполнения модели:
    • либо невозможны
    • либо неизбежны
  • Двойственность
    • если какое-то утверждение невозможно, то обратное -- неизбежно
    • если какое-то утверждение неизбежно, то обратное -- невозможно
    • при помощи логики от одного можно переходить к другому при помощи отрицания

Типы свойств:

  • свойства безопасности
    • ничего плохого никогда не произойдет
    • пример: инвариант системы(например, x всегда меньше y);
    • задача верификатора -- найти те вычисления, которые ведут к нарушению безопасности.
  • свойства живучести
    • рано или поздно произойдет что-то хорошее
    • пример: “отзывчивость” (например, если отправлен запрос, то рано или поздно будет сгенерирован ответ)
    • задача верификатора – найти вычисления, в которых это “хорошее” может откладываться до бесконечности.

Свойства правильности. Свойства безопасности и живучести. Проверка таких свойств. Примеры свойств.

Автоматы Бюхи. Конечные автоматы. Проход автомата. Язык автомата.

Автоматы Бюхи. Омега-допускание. Расширение автоматов Бюхи.

Логика LTL. Синтаксис LTL. Семантика выполнимости формул. Сильный и слабый until.

Логика LTL. Основные типы свойств LTL. Цикличность, стабильность, инвариант, гарантия, отклик, приоритет, корреляция.

Логика LTL. Эквивалентные преобразования формул LTL.

Логика LTL. Оператор neXt. Свойства, инвариантные к прореживанию.

Логика LTL. Проверка выполнимости формул LTL при помощи автоматов Бюхи. Проверка LTL-формул в Spin.

Логика LTL. Выразительная мощность LTL. Логики LTL + существование, CTL* и CTL. Сравнение выразительной мощности.

Получено с http://esyr.us/wiki/%D0%92%D0%9F%D0%BD%D0%9C/%D0%A2%D0%B5%D0%BE%D1%80%D0%BC%D0%B8%D0%BD
Личные инструменты
Разделы