Выполнимость по модулю теорий - Satisfiability modulo theories

В Информатика и математическая логика, то выполнимость по модулю теорий (SMT) проблема - это проблема решения для логических формул относительно комбинаций фона теории выраженный в классических логика первого порядка с равенством. Примеры теорий, обычно используемых в информатике, - это теория действительные числа, теория целые числа, и теории различных структуры данных Такие как списки, массивы, битовые векторы и так далее. SMT можно рассматривать как форму проблема удовлетворения ограничений и, следовательно, некий формализованный подход к программирование в ограничениях.

Основная терминология

Формально говоря, экземпляр SMT - это формула в логика первого порядка, где некоторые функции и предикатные символы имеют дополнительную интерпретацию, а SMT - это проблема определения выполнимости такой формулы. Другими словами, представьте себе экземпляр Проблема логической выполнимости (SAT), в котором некоторые двоичные переменные заменены на предикаты над подходящим набором недвоичных переменных. Предикат - это двоичная функция от недвоичных переменных. Примеры предикатов включают линейные неравенство (например., ${displaystyle 3x + 2y-zgeq 4}$ ) или равенства с участием неинтерпретированные термины и функциональные символы (например, ${displaystyle f (f (u, v), v) = f (u, v)}$ куда ${displaystyle f}$ некоторая неопределенная функция двух аргументов). Эти предикаты классифицируются согласно каждой присвоенной теории. Например, линейные неравенства над действительными переменными оцениваются с использованием правил теории линейных вещественных чисел. арифметика, тогда как предикаты, содержащие неинтерпретированные термины и функциональные символы, оцениваются с использованием правил теории неинтерпретированные функции с равенством (иногда называемое пустая теория ). Другие теории включают теории массивы и список структур (полезно для моделирования и проверки компьютерные программы ), и теория битовые векторы (полезно при моделировании и проверке конструкции оборудования ). Также возможны подтеории: например, разностная логика - это подтеория линейной арифметики, в которой каждое неравенство ограничивается формой ${displaystyle x-y> c}$ для переменных ${displaystyle x}$ и ${displaystyle y}$ и постоянный ${displaystyle c}$ .

Большинство решателей SMT поддерживают только квантификатор -свободные фрагменты их логики.

Выразительная сила

Экземпляр SMT - это обобщение Логическое SAT пример, в котором различные наборы переменных заменяются на предикаты из множества лежащих в основе теорий. Формулы SMT обеспечивают гораздо более богатый язык моделирования чем это возможно с булевыми формулами SAT. Например, формула SMT позволяет нам моделировать путь к данным операции микропроцессор на уровне слова, а не на уровне битов.

По сравнению, программирование набора ответов также основан на предикатах (точнее, на атомарные предложения создан из атомная формула ). В отличие от SMT, программы с набором ответов не имеют квантификаторов и не могут легко выразить ограничения, такие как линейная арифметика или же логика различия —ASP в лучшем случае подходит для логических задач, которые сводятся к свободная теория неинтерпретированных функций. Реализация 32-битных целых чисел в качестве битовых векторов в ASP страдает от большинства проблем, с которыми сталкивались ранние решатели SMT: «очевидные» идентификаторы, такие как Икс+у=у+Икс сложно вывести.

Программирование логики ограничений действительно обеспечивает поддержку линейных арифметических ограничений, но в совершенно другой теоретической структуре.^{[нужна цитата ]} Решатели SMT также были расширены для решения формул в логика высшего порядка.^[1]

Подходы решателя

Ранние попытки решения экземпляров SMT включали преобразование их в логические экземпляры SAT (например, 32-разрядная целочисленная переменная будет кодироваться 32 однобитовыми переменными с соответствующими весами, а операции на уровне слова, такие как «плюс», будут заменены на более низкие - логические операции уровня над битами) и передать эту формулу логическому вычислителю SAT. Этот подход, называемый то жаждущий подход, имеет свои достоинства: путем предварительной обработки формулы SMT в эквивалентную булеву формулу SAT существующие булевы решатели SAT могут использоваться «как есть», а их производительность и емкость улучшаются с течением времени. С другой стороны, потеря высокоуровневой семантики лежащих в основе теорий означает, что логическая программа расчета SAT должна работать намного усерднее, чем необходимо, для обнаружения «очевидных» фактов (таких как ${displaystyle x + y = y + x}$ для сложения целых чисел.) Это наблюдение привело к разработке ряда решателей SMT, которые тесно интегрируют логические рассуждения DPLL поиск в стиле с помощью решателей для конкретной теории (Т-решатели) эта ручка союзы (И) предикатов из данной теории. Этот подход называется то ленивый подход.

Дублированный DPLL (T),^[2] Эта архитектура возлагает ответственность за логические рассуждения на решатель SAT на основе DPLL, который, в свою очередь, взаимодействует с решателем теории T через четко определенный интерфейс. Решателю теории нужно беспокоиться только о проверке выполнимости конъюнкций предикатов теории, переданных ему из решателя SAT, когда он исследует булево пространство поиска формулы. Однако для того, чтобы эта интеграция работала хорошо, решатель теории должен иметь возможность участвовать в распространении и анализе конфликтов, т. Е. Он должен иметь возможность выводить новые факты из уже установленных фактов, а также давать краткие объяснения неосуществимости, когда теория противоречит возникают. Другими словами, решатель теории должен быть инкрементальным и с возможностью возврата.

SMT для неразрешимых теорий

Большинство распространенных подходов SMT поддерживают разрешимый теории. Однако многие реальные системы можно смоделировать только с помощью нелинейной арифметики над действительными числами, включая трансцендентные функции, например самолет и его поведение. Этот факт побуждает распространить проблему SMT на нелинейные теории, например определить

{displaystyle {egin {array} {lr} & (sin (x) ^ {3} = cos (log (y) cdot x) vee bvee -x ^ {2} geq 2.3y) клин влево (например, bvee y <- 34.4vee exp (x)> {y over x} ight) end {array}}}

куда

{displaystyle bin {mathbb {B}}, x, yin {mathbb {R}}}

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

Примерами решателей SMT, обращающихся к булевым комбинациям теоретических атомов из неразрешимых арифметических теорий над действительными числами, являются ABsolver,^[3] который использует классическую архитектуру DPLL (T) с пакетом нелинейной оптимизации в качестве (обязательно неполного) решателя теории подчиненных функций, и iSAT [1], основанный на объединении DPLL SAT-решения и распространение ограничения интервала называется алгоритмом iSAT.^[4]

Решатели

В приведенной ниже таблице приведены некоторые функции многих доступных решателей SMT. Столбец «SMT-LIB» указывает совместимость с языком SMT-LIB; многие системы, отмеченные «да», могут поддерживать только старые версии SMT-LIB или предлагать только частичную поддержку языка. Столбец «CVC» указывает на поддержку языка CVC. Столбец «DIMACS» указывает на поддержку DIMACS формат.

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

Платформа			Функции						Примечания
Имя	Операционные системы	Лицензия	SMT-LIB	CVC	DIMACS	Встроенные теории	API	SMT-COMP [2]
ABsolver	Linux	CPL	v1.2	Нет	да	линейная арифметика, нелинейная арифметика	C ++	нет	На основе DPLL
Альт-Эрго	Linux, Mac OS, Windows	CeCILL-C (примерно эквивалентно LGPL )	частичные v1.2 и v2.0	Нет	Нет	пустая теория, линейная целочисленная и рациональная арифметика, нелинейная арифметика, полиморфные массивы, перечисленные типы данных, Символы переменного тока, битвекторы, типы данных записи, кванторы	OCaml	2008	Полиморфный язык ввода первого порядка а-ля ML, основанный на SAT-решателе, объединяет подходы типа Шостака и Нельсона-Оппена для рассуждения теорий по модулю
Barcelogic	Linux	Проприетарный	v1.2			пустая теория, логика различия	C ++	2009	На основе DPLL, закрытие конгруэнтности
Бобр	Linux, Windows	BSD	v1.2	Нет	Нет	битвекторы	OCaml	2009	На основе SAT-решателя
Булектор	Linux	Массачусетский технологический институт	v1.2	Нет	Нет	битвекторы, массивы	C	2009	На основе SAT-решателя
CVC3	Linux	BSD	v1.2	да		пустая теория, линейная арифметика, массивы, кортежи, типы, записи, битовые векторы, кванторы	C /C ++	2010	вывод доказательства в HOL
CVC4	Linux, Mac OS, Windows, FreeBSD	BSD	да	да		рациональная и целочисленная линейная арифметика, массивы, кортежи, записи, индуктивные типы данных, битовые векторы, строки и равенство над неинтерпретируемыми функциональными символами	C ++	2010	версия 1.5 выпущена в июле 2017 г.
Инструментарий процедуры принятия решений (DPT)	Linux	Apache	Нет				OCaml	нет	На основе DPLL
я сидела	Linux	Проприетарный	Нет			нелинейная арифметика		нет	На основе DPLL
MathSAT	Linux, Mac OS, Windows	Проприетарный	да		да	пустая теория, линейная арифметика, нелинейная арифметика, битовые векторы, массивы	C /C ++, Python, Ява	2010	На основе DPLL
MiniSmt	Linux	LGPL	частичная v2.0			нелинейная арифметика		2010	На основе SAT-решателя, на основе Yices
Норн									Решатель SMT для строковых ограничений
OpenCog	Linux	AGPL	Нет	Нет	Нет	вероятностная логика, арифметика. реляционные модели	C ++, Схема, Python	нет	изоморфизм подграфов
OpenSMT	Linux, Mac OS, Windows	GPLv3	частичная v2.0		да	пустая теория, разности, линейная арифметика, битовые векторы	C ++	2011	ленивый SMT Solver
расат	Linux	GPLv3	v2.0			действительная и целочисленная нелинейная арифметика		2014, 2015	Расширение распространения интервальных ограничений с помощью тестирования и теоремы о промежуточном значении
Сатин	?	Проприетарный	v1.2			линейная арифметика, разностная логика	никто	2009
СМТИнтерпол	Linux, Mac OS, Windows	LGPLv3	v2.5			неинтерпретируемые функции, линейная вещественная арифметика и линейная целочисленная арифметика	Ява	2012	Ориентирован на создание высококачественных компактных интерполянтов.
СМЧР	Linux, Mac OS, Windows	GPLv3	Нет	Нет	Нет	линейная арифметика, нелинейная арифметика, кучи	C	нет	Может реализовать новые теории, используя Правила обработки ограничений.
SMT-RAT	Linux, Mac OS	Массачусетский технологический институт	v2.0	Нет	Нет	линейная арифметика, нелинейная арифметика	C ++	2015	Набор инструментов для стратегического и параллельного решения SMT, состоящий из набора совместимых с SMT реализаций.
SONOLAR	Linux, Windows	Проприетарный	частичная v2.0			битвекторы	C	2010	На основе SAT-решателя
Копье	Linux, Mac OS, Windows	Проприетарный	v1.2			битвекторы		2008
STP	Linux, OpenBSD, Windows, Mac OS	Массачусетский технологический институт	частичная v2.0	да	Нет	битовые векторы, массивы	C, C ++, Python, OCaml, Ява	2011	На основе SAT-решателя
МЕЧ	Linux	Проприетарный	v1.2			битвекторы		2009
UCLID	Linux	BSD	Нет	Нет	Нет	пустая теория, линейная арифметика, битовые векторы и лямбда с ограничениями (массивы, память, кеш и т. д.)		нет	На основе SAT-решателя, написанного на Москва МЛ. Язык ввода - проверка модели SMV. Хорошо задокументированы!
верит	Linux, OS X	BSD	частичная v2.0			пустая теория, рациональная и целочисленная линейная арифметика, кванторы и равенство по неинтерпретируемым функциональным символам	C /C ++	2010	На основе SAT-решателя
Yices	Linux, Mac OS, Windows, FreeBSD	GPLv3	v2.0	Нет	да	рациональная и целочисленная линейная арифметика, битовые векторы, массивы и равенство по неинтерпретируемым функциональным символам	C	2014	Исходный код доступен онлайн
Z3 Доказательство теорем	Linux, Mac OS, Windows, FreeBSD	Массачусетский технологический институт	v2.0		да	пустая теория, линейная арифметика, нелинейная арифметика, битовые векторы, массивы, типы данных, кванторы, струны	C /C ++, .СЕТЬ, OCaml, Python, Ява, Haskell	2011	Исходный код доступен онлайн

Стандартизация и соревнование решателей SMT-COMP

Есть несколько попыток описать стандартизованный интерфейс для решателей SMT (и автоматические средства доказательства теорем, термин, часто используемый как синоним). Самым известным является стандарт SMT-LIB,^{[нужна цитата ]} который предоставляет язык, основанный на S-выражения. Другие обычно поддерживаемые стандартизованные форматы - это формат DIMACS.^{[нужна цитата ]} поддерживается многими логическими программами SAT и форматом CVC^{[нужна цитата ]} используется автоматическим средством доказательства теорем CVC.

Формат SMT-LIB также поставляется с рядом стандартизированных тестов и позволяет проводить ежегодное соревнование между решателями SMT под названием SMT-COMP. Изначально соревнования проходили во время Компьютерная проверка конференция (CAV),^[5]^[6] но с 2020 года конкурс проводится в рамках SMT Workshop, который связан с Международная совместная конференция по автоматизированному мышлению (IJCAR).^[7]

Приложения

Решатели SMT полезны как для проверки, так и для доказательства правильность программ, тестирование ПО на базе символическая казнь, и для синтез, генерируя фрагменты программ путем поиска в пространстве возможных программ. Помимо проверки программного обеспечения, решатели SMT также использовались для моделирования теоретических сценариев, включая моделирование убеждений субъектов в ядерной энергетике. контроль над вооружениями ^[8].

Проверка

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

Есть много верификаторов, построенных на Z3 SMT решатель. Буги - это промежуточный язык проверки, использующий Z3 для автоматической проверки простых императивных программ. В VCC верификатор для параллельного C использует Boogie, а также Дафни для императивных объектно-ориентированных программ, Чаша для параллельных программ и Спецификация # для C #. F * это язык с зависимой типизацией, использующий Z3 для поиска доказательств; компилятор передает эти доказательства для создания байт-кода, несущего доказательство. В Инфраструктура проверки Viper кодирует условия проверки в Z3. В SBV Библиотека обеспечивает проверку программ Haskell на основе SMT и позволяет пользователю выбирать среди ряда решателей, таких как Z3, ABC, Boolector, CVC4, MathSAT и Yices.

Есть также много верификаторов, построенных на Альт-Эрго Решатель SMT. Вот список зрелых приложений:

Почему3 платформа для дедуктивной верификации программ использует Alt-Ergo в качестве основного средства проверки;
CAVEAT, C-верификатор, разработанный CEA и используемый Airbus; Alt-Ergo был включен в квалификацию DO-178C одного из своих последних самолетов;
Фрама-С, фреймворк для анализа C-кода, использует Alt-Ergo в плагинах Jessie и WP (предназначенных для «дедуктивной проверки программ»);
ИСКРА, использует CVC4 и Alt-Ergo (за GNATprove) для автоматизации проверки некоторых утверждений в SPARK 2014;
Ателье-Б может использовать Alt-Ergo вместо основного прувера (увеличение успеха с 84% до 98% на Тесты ANR Bware project );
Роден фреймворк B-методов, разработанный Systerel, может использовать Alt-Ergo в качестве бэкэнда;
Кабина, средство проверки моделей с открытым исходным кодом для проверки свойств безопасности систем перехода на основе массивов.
EasyCrypt, набор инструментов для рассуждения о реляционных свойствах вероятностных вычислений с состязательным кодом.

Многие решатели SMT реализуют общий формат интерфейса, называемый SMTLIB2 (такие файлы обычно имеют расширение ".smt2"). LiquidHaskell Инструмент реализует верификатор на основе типа уточнения для Haskell, который может использовать любой совместимый с SMTLIB2 решатель, например CVC4, MathSat или Z3.

Анализ и тестирование на основе символьного исполнения

Важным приложением решателей SMT является символическая казнь для анализа и тестирования программ (например, конколическое испытание ), направленный, в частности, на поиск уязвимостей в системе безопасности. Важные активно поддерживаемые инструменты в этой категории включают МУДРЕЦ из Microsoft Research, KLEE, S2E, и Тритон. Решатели SMT, которые особенно полезны для приложений с символьным исполнением, включают Z3, STP, Z3str2, и Булектор.

Смотрите также

Примечания

^ Барбоза, Ханиэль и др. "Расширение решателей SMT до логики более высокого порядка. »Международная конференция по автоматизированному вычету. Springer, Cham, 2019.
^ Nieuwenhuis, R .; Oliveras, A .; Тинелли, C. (2006), "Решение теорий SAT и SAT по модулю: от абстрактной процедуры Дэвиса-Патнэма-Логеманна-Ловленда к DPLL (T)", Журнал ACM (PDF), 53, стр. 937–977
^ Bauer, A .; Пистер, М .; Tautschnig, M. (2007), "Инструментальная поддержка для анализа гибридных систем и моделей", Труды конференции по проектированию, автоматизации и тестированию в Европе 2007 г. (DATE'07), IEEE Computer Society, стр. 1, CiteSeerX 10.1.1.323.6807, Дои:10.1109 / ДАТА.2007.364411, ISBN 978-3-9810801-2-4, S2CID 9159847
^ Fränzle, M .; Herde, C .; Ratschan, S .; Schubert, T .; Тейге, Т. (2007), "Эффективное решение больших нелинейных арифметических систем ограничений со сложной булевой структурой", Специальный выпуск JSAT по интеграции SAT / CP (PDF), 1, стр. 209–236
^ Барретт, Кларк; де Моура, Леонардо; Пень, Аарон (2005). Этессами, Коуша; Раджамани, Шрирам К. (ред.). "SMT-COMP: Конкурс теорий удовлетворенности по модулю". Компьютерная проверка. Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 20–23. Дои:10.1007/11513988_4. ISBN 978-3-540-31686-2.
^ Барретт, Кларк; де Моура, Леонардо; Ранис, Сильвио; Пень, Аарон; Тинелли, Чезаре (2011). Барнер, Шэрон; Харрис, Ян; Кронинг, Даниэль; Раз, Орна (ред.). «Инициатива SMT-LIB и рост SMT». Аппаратное и программное обеспечение: проверка и тестирование. Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 3–3. Дои:10.1007/978-3-642-19583-9_2. ISBN 978-3-642-19583-9.
^ «СМТ-КОМП 2020». SMT-COMP. Получено 2020-10-19.
^ Бомонт, Пол; Эванс, Нил; Хут, Майкл; Завод, Том (2015). Пернул, Гюнтер; Y. Райан, Питер; Weippl, Эдгар (ред.). "Анализ уверенности для контроля над ядерным оружием: SMT-абстракции байесовских сетей верований". Компьютерная безопасность - ESORICS 2015. Конспект лекций по информатике. Чам: Издательство Springer International: 521–540. Дои:10.1007/978-3-319-24174-6_27. ISBN 978-3-319-24174-6.