SMT решатели для битовой векторной арифметики - PullRequest
6 голосов
/ 07 июня 2011

Я планирую несколько экспериментов по символическому выполнению кода на языке C, используя готовый SMT-решатель, и задаюсь вопросом, какой решатель использовать; глядя на например участники конкурса SMT, принимая только системы с открытым исходным кодом, сужают его до Beaver, Boolector, CVC3, OpenSMT, Sateen, Sonolar, STP, Verit; который все еще длинный список.

Пытаясь сузить это немного дальше, я замечаю, что некоторые системы рекламируют способность обрабатывать битовую векторную арифметику, тогда как другие рекламируют только способность обрабатывать общую целочисленную арифметику. В принципе, первое верно для C, где переменные являются машинными словами, а не неограниченными целыми числами. Насколько это важно на практике? Что произойдет, если вы попытаетесь использовать общую целочисленную систему для такого рода работы? Применяется ли один из следующих сценариев?

  1. Битовая векторная система немного более эффективна, но вы можете использовать любую, без проблем.

  2. Вы можете использовать обычную целочисленную систему с небольшой настройкой.

  3. Обычная целочисленная система подходит для целых чисел со знаком (потому что результат переполнения не определен), но даст неправильный ответ для неподписанных.

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

  5. Что-то еще ...?

Я пытался задать как можно более конкретный вопрос, но если кто-нибудь может предложить какие-либо другие критерии для сужения списка, это было бы здорово!

Ответы [ 2 ]

7 голосов
/ 30 июня 2011

У меня был хороший опыт использования STP для символического исполнения. STP был разработан именно для этой задачи. Кроме того, было несколько символических инструментов выполнения, которые успешно использовали STP для этой цели, поэтому есть основания полагать, что STP не сосет. Я определенно рекомендую STP другим в качестве варианта по умолчанию для такого рода экспериментов.

Однако я не пробовал другие системы, поэтому не знаю, как STP сравнивается с ними.

Лично я вижу STP в качестве базовой линии и выбора по умолчанию для такого рода приложений. Так что, если у вас есть время попробовать только один решатель, попробовать STP кажется вполне разумным выбором.

Если бы мне пришлось угадывать, я бы предположил, что арифметику битовых векторов важно поддерживать, потому что любой большой системный код будет иметь нетривиальный объем кода, который выполняет побитовые операции. Кроме того, я подозреваю, что некоторые системные коды могут полагаться на поведение беззнаковой арифметики для переноса по модулю 2 n , и если вы попытаетесь смоделировать его с помощью целых чисел, вы не получите правильную семантику C (потому что, как вы говорите, целые числа просто не верны для машинной арифметики), и, следовательно, если вы попытаетесь использовать решатель только для целых чисел, у вас могут возникнуть некоторые трудности. Однако у меня нет веских доказательств для любого из этих подозрений.

P.S. Z3 также может быть претендентом на добавление в ваш список для рассмотрения. (Вам действительно нужен ваш решатель с открытым исходным кодом, если он бесплатный? Я ожидаю, что символический инструмент выполнения будет использовать его только как черный ящик, без изменений.)

1 голос
/ 01 сентября 2011

Согласно SMT-Wikipedia на 2011-08, у нас есть:

На основании этих мер представляется, что наиболее яркими, хорошо организованными проектами являются OpenSMT, STP и CVC4.

Я просто проверяю этот материал - пока что все три, кажется разумным, плюс старый CVC -> CVC3.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...