Memnuniyet modulo teorileri - Satisfiability modulo theories

Olarak bilgisayar biliminin ve matematiksel mantık , Satisfiability modülo teori ( SMT ) sorunu olan karar problemi arka kombinasyonları ile ilgili olarak mantıksal formüller için teorileri , klasik olarak ifade birinci derece mantık eşitlikle. Bilgisayar biliminde tipik olarak kullanılan teori örnekleri, gerçek sayılar teorisi, tamsayılar teorisi ve listeler , diziler , bit vektörleri vb. gibi çeşitli veri yapılarının teorileridir . SMT, kısıtlama tatmin sorununun bir biçimi ve dolayısıyla kısıtlama programlamaya belirli bir resmileştirilmiş yaklaşım olarak düşünülebilir .

Temel terminoloji

Resmi olarak, konuşma, bir SMT örneği olan formül içinde birinci derece mantık bir fonksiyonu ve yüklem sembolü ek yorumlanabildiğinde, SMT gibi bir formül karşılanabilir olup olmadığının saptanması için bir sorundur. Başka bir deyişle, ikili değişkenlerin bazılarının uygun bir ikili olmayan değişkenler kümesi üzerindeki yüklemlerle değiştirildiği Boolean tatmin edilebilirlik probleminin (SAT) bir örneğini hayal edin . Bir yüklem, ikili olmayan değişkenlerin ikili değerli bir işlevidir. Örnek yüklemler lineer, eşitsizliği (örneğin, içeren) ya da eşitlikler Uninterpreted koşullar ve fonksiyon sembolleri (örneğin, burada iki bağımsız bazı belirlenmemiş fonksiyonudur). Bu yüklemler, atanan her bir teoriye göre sınıflandırılır. Örneğin, gerçek değişkenler üzerindeki doğrusal eşitsizlikler, doğrusal gerçek aritmetik teorisinin kuralları kullanılarak değerlendirilirken , yorumlanmamış terimler ve fonksiyon sembolleri içeren yüklemler , eşitlikle yorumlanmamış fonksiyonlar teorisinin (bazen boş teori olarak da adlandırılır) kuralları kullanılarak değerlendirilir. ). Diğer teoriler, diziler ve liste yapıları teorilerini ( bilgisayar programlarını modellemek ve doğrulamak için yararlıdır ) ve bit vektörleri teorisini ( donanım tasarımlarını modelleme ve doğrulamada faydalıdır ) içerir. Alt teoriler de mümkündür: örneğin, fark mantığı lineer aritmetiğin bir alt teorisidir, burada her eşitsizlik değişkenler ve ve sabit için forma sahip olacak şekilde sınırlandırılır . ${\displaystyle 3x+2y-z\geq 4}$${\görüntüleme stili f(f(u,v),v)=f(u,v)}$${\görüntüleme stili f}$${\displaystyle xy>c}$${\görüntüleme stili x}$${\görüntüleme stili y}$${\görüntüleme stili c}$

Çoğu SMT çözücü , mantıklarının yalnızca niceleyici içermeyen parçalarını destekler .

ifade gücü

Bir SMT örneği, çeşitli değişken kümelerinin çeşitli temel teorilerden gelen yüklemlerle değiştirildiği bir Boolean SAT örneğinin genelleştirilmiş halidir. SMT formülleri , Boolean SAT formülleriyle mümkün olandan çok daha zengin bir modelleme dili sağlar . Örneğin, bir SMT formülü , bir mikroişlemcinin veri yolu işlemlerini bit seviyesinden ziyade word'de modellememize izin verir .

Karşılaştırıldığında, cevap kümesi programlaması da yüklemlere (daha doğrusu, atom formülünden oluşturulan atomik cümlelere) dayanır . SMT'den farklı olarak, cevap kümesi programlarının niceleyicileri yoktur ve doğrusal aritmetik veya fark mantığı gibi kısıtlamaları kolayca ifade edemezler - ASP, yorumlanmamış fonksiyonların serbest teorisine indirgenen Boole problemleri için en uygunudur . 32 bit tam sayıların ASP'de bit vektörleri olarak uygulanması, erken SMT çözücülerinin karşılaştığı sorunların çoğundan muzdariptir: x + y = y + x gibi "bariz" kimlikleri çıkarmak zordur.

Kısıtlama mantığı programlaması , doğrusal aritmetik kısıtlamalar için destek sağlar, ancak tamamen farklı bir teorik çerçeve içinde. SMT çözücüler, formülleri daha yüksek mertebeden mantıkta çözmek için de genişletildi .

Çözümleyici yaklaşımlar

SMT örneklerini çözmeye yönelik ilk girişimler, bunları Boolean SAT örneklerine çevirmeyi içeriyordu (örneğin, 32 bitlik bir tamsayı değişkeni, uygun ağırlıklara sahip 32 tek bitlik değişkenler tarafından kodlanır ve 'artı' gibi sözcük düzeyindeki işlemler daha düşük ile değiştirilirdi. bitler üzerinde seviye mantık işlemleri) ve bu formülü bir Boolean SAT çözücüsüne geçirme. İstekli yaklaşım olarak adlandırılan bu yaklaşımın avantajları vardır: SMT formülünü eşdeğer bir Boolean SAT formülüne önceden işleyerek mevcut Boolean SAT çözücüleri "olduğu gibi" kullanılabilir ve performans ve kapasite iyileştirmelerinden zaman içinde yararlanılabilir. . Öte yandan, altta yatan teorilerin üst düzey semantiğinin kaybı, Boolean SAT çözücüsünün "bariz" gerçekleri ( tamsayı toplama gibi) keşfetmek için gerekenden çok daha fazla çalışması gerektiği anlamına gelir . DPLL tarzı bir aramanın Boolean akıl yürütmesini, belirli bir teoriden yüklemlerin bağlaçlarını ( AND'ler) işleyen teoriye özgü çözücüler ( T-çözücüler ) ile sıkı bir şekilde bütünleştiren bir dizi SMT çözücünün geliştirilmesi . Bu yaklaşım olarak adlandırılır tembel bir yaklaşım . ${\görüntüleme stili x+y=y+x}$

DPLL(T) olarak adlandırılan bu mimari, Boole mantığının sorumluluğunu DPLL tabanlı SAT çözücüye verir ve bu da iyi tanımlanmış bir arayüz aracılığıyla T teorisi için bir çözücü ile etkileşime girer. Teori çözücünün yalnızca, formülün Boolean arama uzayını araştırırken SAT çözücüsünden kendisine iletilen teori yüklemlerinin bağlaçlarının uygulanabilirliğini kontrol etme konusunda endişelenmesi gerekir. Bununla birlikte, bu entegrasyonun iyi çalışması için, teori çözücünün yayılma ve çatışma analizine katılabilmesi gerekir, yani halihazırda kurulmuş gerçeklerden yeni gerçekleri çıkarabilmeli ve teori çatıştığında kısa ve öz açıklamalar sunabilmelidir. ortaya çıkmak. Başka bir deyişle, teori çözücü, artımlı ve geri izlenebilir olmalıdır .

Kararsız teoriler için SMT

Yaygın SMT yaklaşımlarının çoğu, karar verilebilir teorileri destekler . Bununla birlikte, birçok gerçek dünya sistemi , örneğin bir uçak ve davranışı gibi aşkın işlevleri içeren gerçek sayılar üzerinde yalnızca doğrusal olmayan aritmetik yoluyla modellenebilir . Bu gerçek, SMT probleminin lineer olmayan teorilere genişletilmesini motive eder, örn.

${\displaystyle {\begin{array}{lr}&(\sin(x)^{3}=\cos(\log(y)\cdot x)\vee b\vee -x^{2}\geq 2.3 y)\wedge \left(\neg b\vee y<-34.4\vee \exp(x)>{y \üzerinde x}\sağ)\end{dizi}}}$

nerede

${\displaystyle b\in {\mathbb {B} },x,y\in {\mathbb {R} }}$

tatmin edici. O zaman, bu tür sorunlar genel olarak kararsız hale gelir . (Teorisi gerçek kapalı alanlar ve böylece tam birinci dereceden teorisi gerçek sayılar , ancak vardır Karar verilebilen kullanarak niceleyici yokedilmesine Bu kaynaklanmaktadır. Alfred Tarski birinci dereceden teorisi.) Doğal sayılar eklenmesiyle (ancak çarpma) Presburger aritmetiği olarak adlandırılan , aynı zamanda karar verilebilir. Sabitlerle çarpma, iç içe toplamalar olarak uygulanabileceğinden, birçok bilgisayar programında aritmetik, Presburger aritmetiği kullanılarak ifade edilebilir ve bu da karar verilebilir formüllerle sonuçlanır.

Gerçekler üzerinde karar verilemeyen aritmetik teorilerden teori atomlarının Boole kombinasyonlarını ele alan SMT çözücü örnekleri, (mutlaka eksik) alt teori çözücü olarak doğrusal olmayan bir optimizasyon paketine sahip klasik bir DPLL(T) mimarisini kullanan ABsolver ve üzerine inşa edilen iSAT'dir . iSAT algoritması olarak adlandırılan DPLL SAT çözme ve aralık kısıtlama yayılımının bir birleşimi .

çözücüler

Aşağıdaki tablo, mevcut birçok SMT çözücünün bazı özelliklerini özetlemektedir. "SMT-LIB" sütunu, SMT-LIB diliyle uyumluluğu belirtir; 'evet' olarak işaretlenmiş birçok sistem, SMT-LIB'nin yalnızca eski sürümlerini destekleyebilir veya dil için yalnızca kısmi destek sunabilir. "CVC" sütunu, CVC dili için desteği gösterir. "DIMACS" sütunu, DIMACS formatı desteğini gösterir .

Projeler yalnızca özellikler ve performans açısından değil, aynı zamanda çevredeki topluluğun yaşayabilirliği, bir projeye olan sürekli ilgisi ve belgelere, düzeltmelere, testlere ve iyileştirmelere katkıda bulunma yeteneği bakımından da farklılık gösterir.

Platformu			Özellikleri						Notlar
isim	işletim sistemi	Lisans	SMT-LIB	özgeçmiş	DIMAKS	Yerleşik teoriler	API	SMT-COMP [1]
AB çözücü	Linux	CPL	v1.2	Hayır	Evet	doğrusal aritmetik, doğrusal olmayan aritmetik	C++	Hayır	DPLL tabanlı
Alt-Ergo	Linux , Mac OS , Windows	CeCILL-C (kabaca eşdeğer LGPL'nin )	kısmi v1.2 ve v2.0	Hayır	Hayır	boş teori , lineer tamsayı ve rasyonel aritmetik, lineer olmayan aritmetik, polimorfik diziler , numaralandırılmış veri türleri , AC sembolleri , bitvektörler , kayıt veri türleri , niceleyiciler	OCaml	2008	SAT-çözücü tabanlı ML gibi polimorfik birinci dereceden giriş dili, modülo teorilerini akıl yürütme için Shostak benzeri ve Nelson-Oppen benzeri yaklaşımları birleştirir
barselolojik	Linux	tescilli	v1.2			boş teori , fark mantığı	C++	2009	DPLL tabanlı, uyum kapatma
kunduz	Linux , Windows	BSD	v1.2	Hayır	Hayır	bitvektörler	OCaml	2009	SAT çözücü tabanlı
Boolector	Linux	MİT	v1.2	Hayır	Hayır	bitvektörler , diziler	C	2009	SAT çözücü tabanlı
CVC3	Linux	BSD	v1.2	Evet		boş teori , lineer aritmetik, diziler, demetler, türler, kayıtlar, bitvektörler, niceleyiciler	C / C++	2010	HOL'ye kanıt çıktısı
CVC4	Linux , Mac OS , Windows , FreeBSD	BSD	Evet	Evet		rasyonel ve tamsayılı lineer aritmetik, diziler, demetler, kayıtlar, endüktif veri türleri, bitvektörler, diziler ve yorumlanmamış fonksiyon sembolleri üzerinde eşitlik	C++	2010	sürüm 1.5 Temmuz 2017'de yayınlandı
Karar Prosedürü Araç Seti (DPT)	Linux	Apaçi	Hayır				OCaml	Hayır	DPLL tabanlı
iSAT	Linux	tescilli	Hayır			doğrusal olmayan aritmetik		Hayır	DPLL tabanlı
MatematikSAT	Linux , Mac OS , Windows	tescilli	Evet		Evet	boş teori , lineer aritmetik, lineer olmayan aritmetik, bitvektörler, diziler	C / C++ , Python , Java	2010	DPLL tabanlı
MiniSmt	Linux	LGPL	kısmi v2.0			doğrusal olmayan aritmetik		2010	SAT çözücü tabanlı, Yices tabanlı
Norn									Dizi kısıtlamaları için SMT çözücü
OpenCog	Linux	AGPL	Hayır	Hayır	Hayır	olasılıksal mantık , aritmetik. ilişkisel modeller	C++ , Şema , Python	Hayır	alt graf izomorfizmi
OpenSMT	Linux , Mac OS , Windows	GPLv3	kısmi v2.0		Evet	boş teori , farklar, lineer aritmetik, bitvektörler	C++	2011	tembel SMT Çözücü
raSAT	Linux	GPLv3	v2.0			gerçek ve tamsayı doğrusal olmayan aritmetik		2014, 2015	Aralıklı Kısıt Yayılımının Test Edilerek Uzatılması ve Ara Değer Teoremi
SatEEn	?	tescilli	v1.2			lineer aritmetik, fark mantığı	Yok	2009
SMTInterpol	Linux , Mac OS , Windows	LGPLv3	v2.5			yorumlanmamış fonksiyonlar, doğrusal gerçek aritmetik ve doğrusal tamsayı aritmetiği	Java	2012	Yüksek kaliteli, kompakt interpolantlar üretmeye odaklanır.
SMCHR	Linux , Mac OS , Windows	GPLv3	Hayır	Hayır	Hayır	doğrusal aritmetik, doğrusal olmayan aritmetik, yığınlar	C	Hayır	Kısıtlama İşleme Kurallarını kullanarak yeni teorileri uygulayabilir .
SMT-RAT	Linux , Mac OS	MİT	v2.0	Hayır	Hayır	doğrusal aritmetik, doğrusal olmayan aritmetik	C++	2015	SMT uyumlu uygulamalar koleksiyonundan oluşan stratejik ve paralel SMT çözümü için araç kutusu.
SONOLAR	Linux , Windows	tescilli	kısmi v2.0			bitvektörler	C	2010	SAT çözücü tabanlı
Mızrak	Linux , Mac OS , Windows	tescilli	v1.2			bitvektörler		2008
STP	Linux , OpenBSD , Windows , Mac OS	MİT	kısmi v2.0	Evet	Hayır	bitvektörler, diziler	C , C++ , Python , OCaml , Java	2011	SAT çözücü tabanlı
KILIÇ	Linux	tescilli	v1.2			bitvektörler		2009
UCLID	Linux	BSD	Hayır	Hayır	Hayır	boş teori , doğrusal aritmetik, bitvektörler ve kısıtlı lambda (diziler, bellekler, önbellek vb.)		Hayır	SAT-çözücü tabanlı, Moscow ML ile yazılmıştır . Giriş dili SMV model denetleyicisidir. İyi belgelenmiş!
gerçek	Linux , OS X	BSD	kısmi v2.0			boş teori , rasyonel ve tamsayı lineer aritmetik, niceleyiciler ve yorumlanmamış fonksiyon sembolleri üzerinde eşitlik	C / C++	2010	SAT çözücü tabanlı
Yices	Linux , Mac OS , Windows , FreeBSD	GPLv3	v2.0	Hayır	Evet	rasyonel ve tamsayılı lineer aritmetik, bitvektörler, diziler ve yorumlanmamış fonksiyon sembolleri üzerinde eşitlik	C	2014	Kaynak kodu çevrimiçi olarak mevcuttur
Z3 Teoremi Kanıtlayıcısı	Linux , Mac OS , Windows , FreeBSD	MİT	v2.0		Evet	boş teori , doğrusal aritmetik, doğrusal olmayan aritmetik, bitvektörler, diziler, veri türleri, niceleyiciler , diziler	C / C++ , .NET , OCaml , Python , Java , Haskell	2011	Kaynak kodu çevrimiçi olarak mevcuttur

Standardizasyon ve SMT-COMP çözücü rekabeti

SMT çözücülere (ve genellikle eşanlamlı olarak kullanılan bir terim olan otomatik teorem kanıtlayıcılara) standartlaştırılmış bir arabirimi tanımlamak için birçok girişim vardır . En belirgin olanı, S-ifadelerine dayalı bir dil sağlayan SMT-LIB standardıdır . Yaygın olarak desteklenen diğer standartlaştırılmış formatlar, birçok Boolean SAT çözücüsü tarafından desteklenen DIMACS formatı ve CVC otomatik teorem ispatlayıcısı tarafından kullanılan CVC formatıdır.

SMT-LIB formatı ayrıca bir dizi standartlaştırılmış kıyaslama ile birlikte gelir ve SMT-COMP adı verilen SMT çözücüler arasında yıllık bir rekabeti mümkün kılmıştır. Başlangıçta, yarışma Bilgisayar Destekli Doğrulama konferansı (CAV) sırasında gerçekleşti , ancak 2020 itibariyle yarışma, Uluslararası Otomatik Akıl Yürütme Konferansı'na (IJCAR) bağlı SMT Çalıştayı'nın bir parçası olarak düzenleniyor .

Uygulamalar

SMT çözücüler hem doğrulama, programların doğruluğunu kanıtlama, sembolik yürütmeye dayalı yazılım testi hem de olası programların alanı üzerinde arama yaparak program parçaları oluşturma sentez için yararlıdır . Yazılım doğrulamasının dışında, SMT çözücüler ayrıca tip çıkarımı için ve nükleer silahların kontrolünde aktör inançlarının modellenmesi de dahil olmak üzere teorik senaryoların modellenmesi için kullanılmıştır .

Doğrulama

Bilgisayar programlarının bilgisayar destekli doğrulaması genellikle SMT çözücülerini kullanır. Yaygın bir teknik, tüm özelliklerin tutulup tutulamayacağını belirlemek için ön koşulları, son koşulları, döngü koşullarını ve iddiaları SMT formüllerine çevirmektir.

Z3 SMT çözücünün üzerine inşa edilmiş birçok doğrulayıcı vardır . Boogie , basit zorunlu programları otomatik olarak kontrol etmek için Z3 kullanan bir ara doğrulama dilidir. VCC eşzamanlı C doğrulayıcı Boogie yanı sıra kullandığı Dafny , zorunlu nesne tabanlı programlar için Kadeh eşzamanlı programlar için ve Spec # C # için. F* , kanıtları bulmak için Z3'ü kullanan, bağımlı olarak yazılan bir dildir; derleyici, kanıt taşıyan bayt kodu üretmek için bu kanıtları taşır. Engerek doğrulama alt Z3 Doğrulama koşulları kodlar. Sbv kütüphanesi Haskell programlarının SMT tabanlı doğrulama sağlar ve kullanıcı, Z3, ABC, Boolector gibi çözücüleri bir dizi arasından seçim yapabilirsiniz KVK4 , MathSAT ve Yices.

Alt-Ergo SMT çözücünün üzerine inşa edilmiş birçok doğrulayıcı da vardır . İşte olgun uygulamaların bir listesi:

• Tümdengelimli program doğrulaması için bir platform olan Why3 , ana kanıtlayıcı olarak Alt-Ergo'yu kullanır;
• CEA tarafından geliştirilen ve Airbus tarafından kullanılan bir C-doğrulayıcı olan CAVEAT; Alt-Ergo, en son uçaklarından birinin DO-178C kalifikasyonuna dahil edildi;
• C kodunu analiz etmek için bir çerçeve olan Frama-C , Jessie ve WP eklentilerinde Alt-Ergo'yu kullanır ("tümdengelimli program doğrulamaya" adanmış);
• SPARK , SPARK 2014'teki bazı iddiaların doğrulanmasını otomatikleştirmek için CVC4 ve Alt-Ergo'yu (GNATprove'un arkasında) kullanır;
• Atelier-B , ana kanıtlayıcısı yerine Alt-Ergo'yu kullanabilir ( ANR Bware proje kıyaslamalarında başarıyı %84'ten %98'e yükselterek );
• Systerel tarafından geliştirilen bir B yöntemi çerçevesi olan Rodin , Alt-Ergo'yu arka uç olarak kullanabilir;
• Cubicle , dizi tabanlı geçiş sistemlerinin güvenlik özelliklerini doğrulamak için açık kaynaklı bir model denetleyicisi.
• EasyCrypt , rakip kodla olasılıklı hesaplamaların ilişkisel özellikleri hakkında muhakeme yapmak için bir araç seti.

Çoğu SMT çözücüsü, SMTLIB2 adı verilen ortak bir arabirim biçimi uygular (bu tür dosyalar genellikle " .smt2 " uzantısına sahiptir ). LiquidHaskell aracı uygular herhangi SMTLIB2 uyumlu çözücüsü kullanabilirsiniz Haskell için doğrulayıcı dayalı bir arıtma tipi, örn KVK4, MathSat veya Z3.

Sembolik-yürütme tabanlı analiz ve test

SMT çözücülerinin önemli bir uygulaması, özellikle güvenlik açıklarını bulmayı amaçlayan programların (örn., concolic testi ) analizi ve test edilmesi için sembolik yürütmedir . Bu kategoride Önemli aktif bakımlı araçlar şunlardır SAGE gelen Microsoft Research , Klee , S2E ve Triton . Sembolik yürütme uygulamaları için özellikle yararlı olan SMT çözücüler arasında Z3 , STP , Z3str2 ve Boolector bulunur .

Ayrıca bakınız

• Cevap seti programlama
• Otomatik teorem ispatı

Notlar

Referanslar

• C Barrett, R Sebastiani, S Seshia ve C Tinelli, " Satisfiability Modulo Theories ." Memnuniyet El Kitabı'nda, cilt. Frontiers in Yapay Zeka ve Uygulamalar, (A Biere, MJH Heule, H van Maaren ve T Walsh, eds.), IOS Press, Şubat 2009, s. 825-885.
• Vijay Ganesh (Doktora Tezi 2007), Bit-Vektörler, Diziler ve Tamsayılar için Karar Prosedürleri , Bilgisayar Bilimleri Bölümü, Stanford Üniversitesi, Stanford, CA, ABD, Eylül 2007
• Susmit Jha, Rhishikesh Limaye ve Sanjit A. Seshia. Beaver: Bit-vektör aritmetiği için verimli bir SMT çözücü mühendisliği. 21. Uluslararası Bilgisayar Destekli Doğrulama Konferansı Tutanakları içinde, s. 668-674, 2009.
• RE Bryant, SM German ve MN Velev, " Yorumlanmamış Fonksiyonlarla Eşitlik Mantığı için Etkin Karar Prosedürlerini Kullanan Mikroişlemci Doğrulaması ", Analitik Tablo ve İlgili Yöntemler, s. 1–13, 1999.
• M. Davis ve H. Putnam, Quantification Theory için Hesaplama Prosedürü , Journal of the Association for Computing Machinery, cilt. 7, no., s. 201–215, 1960.
• M. Davis, G. Logemann ve D. Loveland, A Machine Program for Theorem-Proving , Communications of the ACM, cilt. 5, hayır. 7, s. 394-397, 1962.
• D. Kroening ve O. Strichman, Karar Prosedürleri – algoritmik bir bakış açısı (2008), Springer (Teorik Bilgisayar Bilimi serisi) ISBN  978-3-540-74104-6 .
• G.-J. Nam, KA Sakallah ve R. Rutenbar, Arama Tabanlı Boolean Satisfiability ile Yeni Bir FPGA Ayrıntılı Yönlendirme Yaklaşımı , Tümleşik Devrelerin ve Sistemlerin Bilgisayar Destekli Tasarımında IEEE İşlemleri, cilt. 21, hayır. 6, s. 674–684, 2002.
• SMT-LIB: Memnuniyet Modulo Teorileri Kitaplığı
• SMT-COMP: Memnuniyet Modulo Teorileri Yarışması
• Karar prosedürleri - algoritmik bir bakış açısı
• R. Sebastiani, Lazy Satisfiability Modulo Theories , Dipartimento di Ingegneria e Scienza dell'Informazione, Universita di Trento, İtalya, Aralık 2007
• D.Yurichev, SAT/SMT çözücülere hızlı giriş ve sembolik yürütme

---

Bu makalede, ACM, bir sütun uyarlanmıştır SIGDA e-bülten ile Dr. Karem Sakallah . Orijinal metin burada mevcuttur