Список инструментов проверки модели - List of model checking tools

В этой статье перечислены проверка модели инструменты и дает синтетический обзор их функций.

Обзор некоторых инструментов проверки модели

В следующей таблице представлены средства проверки моделей, у которых есть

(1) веб-сайт, с которого его можно загрузить,

(2) заявленная лицензия,

(3) описание, опубликованное в архивной литературе, и

(4) статья в Википедии с его описанием.

В таблице ниже используются следующие сокращения:

  • Эквивалентности:
    • SB: сильная бисимуляция
    • WB: слабая бисимуляция
    • BB: ветвящаяся бисимуляция
    • STE: сильная эквивалентность трассировки
    • WTE: слабая эквивалентность трассировки
    • я: Май Эквивалентность
    • Я: должна быть эквивалентна
    • OE: наблюдательная эквивалентность
    • SE: Эквивалентность безопасности
    • t * E: tau * .a Эквивалентность
  • Лицензия на программное обеспечение:
    • FUSC: Бесплатно при определенных условиях (например, бесплатно для ученых)
ИмяПроверка моделиПроверка эквивалентностиGUIДоступность
Обычный, вероятностный, стохастический, ...Язык моделированияЯзык свойствПоддерживаемые эквивалентыГенерация примера счетчика GUIГрафическая спецификацияВизуализация примера счетчикаЛицензия на программное обеспечениеИспользуемый язык программированияПлатформа / ОС
ВЗРЫВАнализ кодаCМониторинг автоматовдаНетНетНетСвободныйOCamlСвязанные с Windows и Unix
CADPПростой и вероятностныйLOTOS, FC2, FSP, LNTAFMC, MCL, XTLSB, WB, BB, OE, STE, WTE, SE, tau * EдадаНетдаFUSCC, Оболочка Борна, Tcl /Тк, LOTOS, LNTMac OS, Linux, Solaris, Windows
CPAcheckerАнализ кодаCМониторинг автоматовдадаНетдаСвободныйЯваЛюбой
МЕЧТАТЬВ реальном времениC ++, Временные автоматыМониторинг автоматовдаНетНетНетСвободныйC ++Связанные с Windows и Unix
Java PathfinderПростой и рассчитанныйЯванеизвестныйНетдаНетНетСоглашение об открытом исходном кодеЯваMac OS, Windows, Linux
LTSminОбычный, в реальном времениПромела, мкКРЛ, mCRL2, Язык ввода DVEμ-исчисление, LTL, CTL *SB, BBдаНетНетНетСвободныйC, C ++Unix, Mac OS X, Windows
mCRL2Обычный, в реальном времениmCRL2μ-исчислениеSB, BB, t * E, STE, WTEдадаНетдаСвободныйC ++Mac OS, Linux, Solaris, Windows
MRMCВ реальном времени, вероятностныйОбычный MCCSL, CSRL, PCTL, PRCTLSBНетНетНетНетСвободныйCWindows, Linux, Mac OS
NuSMVПростойЯзык ввода SMVCTL, LTL, PSLдаНетНетНетСвободныйCUnix, Windows, Mac OS X
PATОбычный, в реальном времени, вероятностныйCSP #, Синхронизированный CSP, вероятностный CSPLTL, УтверждениядадададаСвободныйC #Windows, другие ОС с Mono
ПРИЗМАВероятностныйPEPA, Язык PRISM, простой MCCSL, PLTL, PCTLНетдаНетНетСвободныйC ++, ЯваWindows, Linux, Mac OS
ВРАЩЕНИЕПростойПромелаLTLдадаНетдаFUSCC, C ++Связанные с Windows и Unix
ТАПААЛВ реальном времениСети Петри с временной дугой, инварианты возраста, ингибиторные дуги, транспортные дугиПодмножество TCTLНетдададаСвободныйC ++, ЯваMac OS, Windows, Linux
ТАПАПростойCCSPCTL, μ-исчислениеSB, WB, BB, STE, WTE, я, я, OEдадададаСвободныйЯваСвязанные с Windows, Mac OS и Unix
UPPAALВ реальном времениВременные автоматы, Подмножество CПодмножество TCTLдадададаFUSCC ++, ЯваMac OS, Windows, Linux
РОМЕОВ реальном времениВремя сети Петри, секундомер параметрические сети ПетриПодмножество TCTLдададаНетСвободныйC ++, tcl / tkMac OS, Windows, Linux
TLA + Средство проверки модели (TLC)ПростойTLA +, PlusCalTLAдададаНетСвободныйЯваMac OS, Windows, Linux

Языки моделирования

  • CCSP: расчет процесса, полученный из CCS путем включения некоторых операторов CSP. Это определено Ольдерогом[1] и ван Глаббек / Ваандрагер.[2]
  • CSP: Связь последовательных процессов; формальный язык для описания паттернов взаимодействия в параллельных системах. FDR2 это инструмент проверки уточнения для CSP, сравнивающий две модели на совместимость.
  • Язык ввода DVE: система описывается как сеть расширенных конечных автоматов, взаимодействующих через общие переменные и небуферизованные каналы. Не содержит поддержки буферизованных каналов и проверки типа сообщения, которое должно быть получено, без выполнения надлежащего приема.
  • FC2: (Общий формат V2) представление ASCII на уровне машины для синхронизированных (иерархических) сетей автоматов. Определено Esprit Basic Research Action CONCUR, 1992. Используется в качестве формата ввода и обмена рядом инструментов проверки, в основном в области алгебр процессов.
  • FSP: язык процессов конечного состояния, определенный в Имперском колледже.
  • Ява: Объектно-ориентированный язык программирования.
  • LNT: Новые технологии LOTOS; язык спецификаций, вдохновленный исчислениями процессов, языками функционального программирования и императивными языками программирования; LNT был разработан как современная замена LOTOS и E-LOTOS.
  • LOTOS: Язык спецификации временного упорядочивания (стандарт ISO 8807); формальный язык спецификации, основанный на временном порядке, используемый для спецификации протокола в стандартах ISO OSI.
  • PEPA: Алгебра процесса оценки эффективности; это алгебра стохастических процессов, предназначенная для моделирования компьютерных систем и систем связи.
  • Plain MC: простые форматы текстовых файлов, используемые в MRMC и PRISM.
  • Промела: Метаязык процесса или протокола; это язык верификационного моделирования. Язык позволяет динамически создавать параллельные процессы для моделирования, например, распределенных систем.
  • TLA +: Язык спецификаций общего назначения, основанный на временной логике действий, первоначально использовавшийся для распределенных и параллельных систем. Язык спецификаций и их свойств такой же.

Язык свойств

  • AFMC: без чередования модальное μ-исчисление.
  • Утверждения: Императивные утверждения утверждения.
  • CSL: Continuous Stochastic Logic, характеризует двойное моделирование марковских процессов с непрерывным временем.
  • CSRL: Непрерывная стохастическая логика вознаграждения; логика для определения мер по CTMC, расширенная структурой вознаграждения (так называемые марковские модели вознаграждения).
  • CTL: Логика дерева вычислений; логика времени ветвления, означающая, что ее модель времени представляет собой древовидную структуру, в которой будущее не определено; в будущем есть разные пути, любой из которых может быть реальным, реализованным.
  • LTL: Линейная темпоральная логика; модальная темпоральная логика с модальностями, относящимися ко времени.
  • MCL: язык проверки модели; Без чередования Модальное μ-исчисление расширен удобными регулярными выражениями и конструкциями передачи значений; включает CTL и LTL.
  • mCRL2 mu-исчисление: пропозициональное модальное μ-исчисление (исключая атомарные предложения), расширенный: процессы, зависящие от данных, количественная оценка по типам данных, мульти-действия, время и обычные формулы.
  • PCTL: Вероятностный CTL; расширение CTL, которое позволяет вероятностную количественную оценку описанных свойств.
  • PLTL: вероятностная линейная временная логика.
  • PRCTL: логика дерева вероятностных вычислений вознаграждения; он расширяется PCTL со свойствами, ограниченными вознаграждением.
  • PSL: Язык описания свойств
  • SVA: SystemVerilog подмножество языков утверждения стандартов, стандартизованное как IEEE 1800
  • XTL: расширенный темпоральный язык; предметно-ориентированный язык для быстрой реализации основанных на действии средств проверки моделей с явным состоянием и передачей значений.

Сравнение инструментов проверки модели

Научные публикации

Существует несколько статей, в которых систематически сравниваются различные средства проверки моделей на общем примере. В сравнении обычно обсуждаются компромиссы моделирования, с которыми приходится сталкиваться при использовании языков ввода каждого средства проверки модели, а также сравнение производительности инструментов при проверке свойств правильности. Можно упомянуть:

  • В 1999 году Джуди Ромейн сравнила две модели шашек (CADP и ВРАЩЕНИЕ ) об аудио-видео протоколе взаимодействия HAVi для бытовой электроники.[3]
  • В 2003 году Ифэй Донг, Сяокун Ду, Джерард Хольцманн и Скотт А. Смолка опубликовали сравнение четырех модельных шашек (а именно: Cospan, Murphi, ВРАЩЕНИЕ, и XMC) по протоколу связи, i-протоколу GNU.[4]
  • В 2005 году Елена М. Бортник, Никола Трка, Антон Вийс, Бас Луттик, Й. М. ван де Мортель-Фрончак, Йос К. М. Бэтен, Ван Фоккинк и Й. Э. Руда опубликовали сравнение четырех модельных шашек (а именно: CADP, muCRL, ВРАЩЕНИЕ, и UPPAAL ) на промышленной производственной системе, вращающемся сверлильном станке.[5]
  • В 2018 году F. Mazzanti и A. Ferrari опубликовали сравнение десяти моделей шашек (а именно: CADP, CPN Tools, FDR4, NuSMV / nuXmv, mCRL2, Проба, ВРАЩЕНИЕ, TLA +, UMC и UPPAAL ) по проблеме надзора за поездом, принимая во внимание удобство использования языков и производительность инструментов.[6]

Международные конкурсы программного обеспечения

  • С 2007 г. Конкурс по проверке модели оборудования (HWMCC) сравнивает производительность инструментов проверки моделей, ориентированных на проектирование оборудования.
  • С 2011 г. Конкурс проверки моделей (MCC) сравнивает производительность инструментов проверки моделей, предназначенных для анализа систем с высокой степенью параллелизма.

Общие тесты

  • MCC (модели конкурса Model Checking Contest): собрание сотен сетей Петри, созданных на основе многих академических и промышленных тематических исследований.
  • VLTS (Очень большие переходные системы): коллекция помеченных переходных систем увеличивающегося размера, используемая во многих научных публикациях.

Рекомендации

  1. ^ Э. Р. Ольдерог: Семантика операционной сети Петри для CCSP
  2. ^ Роб ван Глаббек, Фриц Ваандрагер: Объединение структур событий и CCSP
  3. ^ Ромейн, Джуди (июнь 1999 г.). Модель проверки протокола выборов лидера HAVi (Технический отчет). Амстердам: CWI. SEN-R9915. Сложить резюме.
  4. ^ Донг, Ифэй; Ду Сяоцюнь; Хольцманн, Жерар; Смолка, Скотт (2003). «Борьба с Livelock в GNU i-Protocol: пример проверки модели явного состояния». Программный инструмент для передачи технологий. 4 (4): 505–528.
  5. ^ Бортник Елена М .; Трцка, Никола; Вийс, Антон; Луттик, Бас; van de Mortel-Fronczak, J.M .; Baeten, Jos C.M .; Фоккинк, Ван; Руда, Дж. Э. (2005). "Анализируя чи модель поворотного стола с использованием Spin, CADP и Uppaal " (PDF). Журнал логических и алгебраических методов программирования. 65 (2): 51–104. Дои:10.1016 / j.jlap.2005.05.001.
  6. ^ Маццанти, Франко; Феррари, Алессио (2018). «Десять различных формальных моделей для автоматической системы наблюдения за поездом CBTC». Материалы 3-го семинара по моделям для формального анализа реальных систем и 6-го международного семинара по верификации и трансформации программ (MARS / VPT’18), Салоники, Греция. Электронные труды по теоретической информатике. 268. С. 104–149. arXiv:1803.10324v1. Дои:10.4204 / EPTCS.268.4.

внешняя ссылка

Другие модели чекеров, у которых еще нет страницы в Википедии:

и