Teorie modulo uspokojivosti - Satisfiability modulo theories

v počítačová věda a matematická logika, teorie uspokojivosti modulo (SMT) problém je rozhodovací problém pro logické vzorce s ohledem na kombinace pozadí teorie vyjádřeno klasicky logika prvního řádu s rovností. Příklady teorií obvykle používaných v informatice jsou teorie reálná čísla, teorie celá čísla a teorie různých datové struktury jako seznamy, pole, bitové vektory a tak dále. SMT lze považovat za formu problém spokojenosti s omezením a tedy určitý formalizovaný přístup k programování omezení.

Základní terminologie

Formálně vzato je instance SMT a vzorec v logika prvního řádu, kde některé symboly funkcí a predikátů mají další interpretace, a SMT je problém určení, zda je takový vzorec uspokojivý. Jinými slovy, představte si instanci Booleovský problém uspokojivosti (SAT), ve kterém jsou některé z binárních proměnných nahrazeny znakem predikáty přes vhodnou sadu nebinárních proměnných. Predikát je binární funkce nebinárních proměnných. Příklad predikátů zahrnuje lineární nerovnosti (např., ${displaystyle 3x + 2y-zgeq 4}$) nebo rovnosti zahrnující neinterpretované termíny a funkční symboly (např. ${displaystyle f (f (u, v), v) = f (u, v)}$ kde ${displaystyle f}$ je nějaká nespecifikovaná funkce dvou argumentů). Tyto predikáty jsou klasifikovány podle každé přiřazené teorie. Například lineární nerovnosti nad reálnými proměnnými jsou hodnoceny pomocí pravidel teorie lineárního reálného aritmetický, zatímco predikáty zahrnující neinterpretované termíny a funkční symboly se vyhodnocují pomocí pravidel teorie neinterpretované funkce s rovností (někdy označované jako prázdná teorie ). Mezi další teorie patří teorie pole a seznam struktury (užitečné pro modelování a ověřování počítačové programy ) a teorie bitové vektory (užitečné při modelování a ověřování návrhy hardwaru ). Možné jsou také podteorie: například diferenční logika je sub-teorie lineární aritmetiky, ve které je každá nerovnost omezena na formu ${displaystyle x-y> c}$ pro proměnné ${displaystyle x}$ a ${displaystyle y}$ a konstantní ${displaystyle c}$.

Většina řešitelů SMT podporuje pouze kvantifikátor -free fragmenty jejich logiky.

Expresivní síla

Instance SMT je zobecněním a Boolean SAT instance, ve které jsou různé sady proměnných nahrazeny predikáty z různých základních teorií. SMT vzorce poskytují mnohem bohatší modelovací jazyk než je to možné u booleovských vzorců SAT. Například vzorec SMT nám umožňuje modelovat datová cesta operace a mikroprocesor spíše na slovo než na bitovou úroveň.

Ve srovnání, programování sady odpovědí je také založen na predikátech (přesněji na atomové věty vytvořeno z atomový vzorec ). Na rozdíl od SMT programy odpovědí nemají kvantifikátory a nemohou snadno vyjádřit omezení, jako je lineární aritmetika nebo logika rozdílu —ASP je v nejlepším případě vhodný pro booleovské problémy, které se snižují na volná teorie neinterpretovaných funkcí. Implementace 32bitových celých čísel jako bitvektorů v ASP trpí většinou stejných problémů, kterým čelili první řešitelé SMT: „zjevné“ identity, jako například X+y=y+X je těžké odvodit.

Logické programování omezení poskytuje podporu pro lineární aritmetická omezení, ale v úplně jiném teoretickém rámci.^{[Citace je zapotřebí ]} Řešitelé SMT byly také rozšířeny o řešení vzorců v logika vyššího řádu.^[1]

Řešitel se blíží

První pokusy o řešení instancí SMT zahrnovaly jejich překlad do booleovských instancí SAT (např. 32bitová celočíselná proměnná by byla kódována 32 jednobitovými proměnnými s odpovídajícími váhami a operace na úrovni slov, jako například „plus“, byly nahrazeny nižšími logické operace na bitech) a předání tohoto vzorce booleovskému řešení SAT. Tento přístup, který se označuje jako the dychtivý přístup, má své výhody: předběžným zpracováním vzorce SMT na ekvivalentní booleovský vzorec SAT lze použít stávající řešení boolean SAT „tak, jak jsou“, a jejich vylepšení výkonu a kapacity se časem zvýší. Na druhou stranu ztráta sémantiky vysokých úrovní základních teorií znamená, že booleovský řešič SAT musí pracovat mnohem více, než je nutné, aby objevil „zjevná“ fakta (jako např. ${displaystyle x + y = y + x}$ Toto přidání vedlo k vývoji řady řešičů SMT, které pevně integrují logické uvažování DPLL hledání stylu s řešiteli specifickými pro teorii (Řešitelé T) ta rukojeť spojky (AND) predikátů z dané teorie. Tento přístup se označuje jako the líný přístup.

Dabovaný DPLL (T),^[2] tato architektura dává zodpovědnost booleovského uvažování za řešení SAT SAT založené na DPLL, které naopak interaguje s řešičem teorie T prostřednictvím dobře definovaného rozhraní. Řešitel teorie si musí dělat starosti pouze s kontrolou proveditelnosti spojování predikátů teorie, které mu byly předány ze SAT řešiče, protože zkoumá booleovský vyhledávací prostor vzorce. Aby tato integrace fungovala dobře, musí být řešitel teorie schopen podílet se na šíření a analýze konfliktů, tj. Musí být schopen odvodit nová fakta z již zjištěných skutečností a také poskytnout stručné vysvětlení neproveditelnosti, když dojde ke konfliktu teorie vzniknout. Jinými slovy, řešitel teorie musí být přírůstkový a zpětně vysledovatelný.

SMT pro nerozhodnutelné teorie

Většina běžných přístupů SMT podporuje rozhodnutelné teorie. Mnoho systémů v reálném světě však lze modelovat pouze pomocí nelineární aritmetiky nad reálnými čísly transcendentální funkce, např. letadlo a jeho chování. Tato skutečnost motivuje k rozšíření problému SMT na nelineární teorie, např. určit, zda

${displaystyle {egin {array} {lr} & (sin (x) ^ {3} = cos (log (y) cdot x) vee bvee -x ^ {2} geq 2.3y) klín vlevo (např. bvee y <- 34,4vee exp (x)> {y over x} ight) end {array}}}$

kde

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

je uspokojivý. Pak se takové problémy stanou nerozhodnutelný obecně. (Teorie skutečná uzavřená pole, a tedy úplná teorie prvního řádu reálná čísla, jsou však rozhodnutelné použitím eliminace kvantifikátoru. To je způsobeno Alfred Tarski.) Teorie prvního řádu přirozená čísla s přídavkem (ale ne s násobením), tzv Presburgerova aritmetika, je také rozhodnutelné. Vzhledem k tomu, že násobení konstantami lze implementovat jako vnořené dodatky, lze aritmetiku v mnoha počítačových programech vyjádřit pomocí Presburgerovy aritmetiky, což má za následek rozhodné vzorce.

Příklady řešitelů SMT, kteří se zabývají booleovskými kombinacemi atomů teorie z nerozhodnutelných aritmetických teorií nad reálemi, jsou ABsolver,^[3] který využívá klasickou architekturu DPLL (T) s nelineárním optimalizačním paketem jako (nutně neúplný) podřízený řešitel teorie a iSAT [1], navazující na sjednocení řešení DPLL SAT a šíření intervalového omezení volal algoritmus iSAT.^[4]

Řešitelé

Níže uvedená tabulka shrnuje některé funkce mnoha dostupných řešičů SMT. Sloupec „SMT-LIB“ označuje kompatibilitu s jazykem SMT-LIB; mnoho systémů označených jako „ano“ může podporovat pouze starší verze SMT-LIB nebo nabízí jazyk pouze částečnou podporu. Sloupec „CVC“ označuje podporu pro jazyk CVC. Sloupec "DIMACS" označuje podporu pro DIMACY formát.

Projekty se liší nejen funkcemi a výkonem, ale také životaschopností okolní komunity, jejím trvalým zájmem o projekt a schopností přispívat dokumentací, opravami, testy a vylepšeními.

Standardizace a soutěž řešitelů SMT-COMP

Existuje několik pokusů popsat standardizované rozhraní pro řešitele SMT (a automatizované věty provers, termín často používaný jako synonymum). Nejvýznamnějším je standard SMT-LIB,^{[Citace je zapotřebí ]} který poskytuje jazyk založený na S-výrazy. Další standardně podporované standardizované formáty jsou formát DIMACS^{[Citace je zapotřebí ]} podporováno mnoha booleovskými řešiteli SAT a formátem CVC^{[Citace je zapotřebí ]} používaný automatizovaným testerem vět CVC.

Formát SMT-LIB také přichází s řadou standardizovaných měřítek a umožnil každoroční soutěž mezi řešiteli SMT s názvem SMT-COMP. Soutěž se původně konala v průběhu Ověření pomocí počítače konference (CAV),^[5][6] ale od roku 2020 je soutěž pořádána jako součást SMT Workshopu, který je přidružen k Mezinárodní společná konference o automatizovaném uvažování (IJCAR).^[7]

Aplikace

Řešitelé SMT jsou užiteční jak pro ověření, tak i pro ověření správnost programů, testování softwaru založené na symbolické provedení, a pro syntéza, generování programových fragmentů prohledáváním prostoru možných programů. Kromě ověřování softwaru se řešitelé SMT používají také pro modelování teoretických scénářů, včetně modelování přesvědčení herců v jaderné ovládání zbraní ^[8].

Ověření

Počítačem podporovaný ověřování počítačových programů často používá řešení SMT. Běžnou technikou je převést předpoklady, postconditions, podmínky smyčky a tvrzení do vzorců SMT, aby se zjistilo, zda mohou všechny vlastnosti držet.

Existuje mnoho ověřovatelů postavených na vrcholu Řešitel Z3 SMT. Boogie je přechodný ověřovací jazyk, který používá Z3 k automatické kontrole jednoduchých imperativních programů. The VCC ověřovatel pro souběžné C používá Boogie, stejně jako Dafny pro imperativní objektové programy, Kalich pro souběžné programy a Spec # pro C #. F* je jazyk závislý na typu, který používá Z3 k hledání důkazů; kompilátor tyto důkazy přenáší, aby vytvořil bajtový kód nesoucí důkaz. The Infrastruktura pro ověření zmije kóduje podmínky ověření do Z3. The sbv knihovna poskytuje ověřování programů Haskell na základě SMT a umožňuje uživateli vybrat si z řady řešitelů, jako jsou Z3, ABC, Boolector, CVC4, MathSAT a Yices.

Na vrcholu je také mnoho ověřovatelů Alt-Ergo Řešitel SMT. Zde je seznam vyspělých aplikací:

• Proč3, platforma pro deduktivní ověření programu, používá Alt-Ergo jako hlavní prover;
• CAVEAT, ověřovatel C vyvinutý společností CEA a používaný společností Airbus; Alt-Ergo byl zařazen do kvalifikace DO-178C jednoho ze svých nedávných letadel;
• Frama-C, rámec pro analýzu C-kódu, používá Alt-Ergo v zásuvných modulech Jessie a WP (vyhrazeno pro "deduktivní ověření programu");
• JISKRA, používá CVC4 a Alt-Ergo (za GNATprove) k automatizaci ověření některých tvrzení ve SPARKu 2014;
• Atelier-B může použít Alt-Ergo místo svého hlavního proveru (zvýšení úspěšnosti z 84% na 98% na Benchmarky projektu ANR Bware );
• Rodine, rámec metody B vyvinutý společností Systerel, může používat Alt-Ergo jako back-end;
• Kóje, open source model checker pro ověřování bezpečnostních vlastností přechodových systémů založených na poli.
• EasyCrypt, sada nástrojů pro uvažování o relačních vlastnostech pravděpodobnostních výpočtů s kontradiktorním kódem.

Mnoho řešitelů SMT implementuje běžný formát rozhraní nazvaný SMTLIB2 (takové soubory mají obvykle příponu ".smt2") LiquidHaskell nástroj implementuje ověřovatel založený na typu upřesnění pro Haskell, který může použít jakýkoli řešič vyhovující SMTLIB2, např. CVC4, MathSat nebo Z3.

Analýza a testování založené na symbolickém provádění

Důležitou aplikací řešičů SMT je symbolické provedení pro analýzu a testování programů (např. concolic testování ), zaměřené zejména na hledání bezpečnostních slabin. Mezi důležité aktivně udržované nástroje v této kategorii patří ŠALVĚJ z Microsoft Research, KLEE, S2E, a Triton. Mezi ně patří řešiče SMT, které jsou zvláště užitečné pro aplikace symbolického provádění Z3, STP, Z3str2, a Boolektor.

Viz také

• Odpovězte na nastavené programování
• Automatizované dokazování věty

Poznámky

Reference

• C Barrett, R Sebastiani, S Seshia a C Tinelli, "Splnitelnost Modulární teorie "V příručce Satisfiability, sv. 185, Frontiers in Artificial Intelligence and Applications, (A Biere, M J H Heule, H van Maaren a T Walsh, eds.), IOS Press, únor 2009, s. 825–885.
• Vijay Ganesh (disertační práce 2007), Postupy rozhodování pro bitové vektory, pole a celá čísla, Computer Science Department, Stanford University, Stanford, CA, USA, září 2007
• Susmit Jha, Rhishikesh Limaye a Sanjit A. Seshia. Beaver: Inženýrství efektivního řešení SMT pro aritmetiku bitových vektorů. In Proceedings of 21st International Conference on Computer-Aided Verification, pp. 668–674, 2009.
• R. E. Bryant, S. M. German a M. N. Velev, "Ověření mikroprocesoru pomocí efektivních rozhodovacích postupů pro logiku rovnosti s neinterpretovanými funkcemi, „in Analytic Tableaux and Related Methods, s. 1–13, 1999.
• M. Davis a H. Putnam, Postup výpočtu pro teorii kvantifikace, Journal of the Association for Computing Machinery, sv. 7, č. S. 201–215, 1960.
• M. Davis, G. Logemann a D. Loveland, Strojový program pro dokazování teorémů „Komunikace ACM, sv. 5, č. 7, str. 394–397, 1962.
• D. Kroening a O. Strichman, Rozhodovací procedury - algoritmické hledisko (2008), Springer (řada Teoretická informatika) ISBN  978-3-540-74104-6.
• G.-J. Nam, K. A. Sakallah a R. Rutenbar, Nový přístup k podrobnému směrování FPGA prostřednictvím vyhledávací booleovské spokojenosti, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, č. 6, s. 674–684, 2002.
• SMT-LIB: Knihovna teorií modulárních teorií uspokojivosti
• SMT-COMP: Soutěž o teorie uspokojitelnosti v modulárních teoriích
• Rozhodovací postupy - algoritmické hledisko
• R. Sebastiani, Lazy uspokojivost modulární teorie „Dipartimento di Ingegneria e Scienza dell'Informazione, Universita di Trento, Itálie, prosinec 2007
• D. Juričev, Rychlý úvod do řešení SAT / SMT a symbolické provedení

Tento článek je převzat ze sloupce v ACM SIGDA elektronický zpravodaj podle Prof. Karem Sakallah. Původní text je k dispozici zde