Tilatarkistuslogiikka

Tilatarkistuslogiikka on ala, joka tutkii menetelmiä ja teoreettisia periaatteita järjestelmän tilojen ja tilansiirtojen formalisoimiseksi ja tarkistamiseksi. Keskeisiä tavoitteita ovat turvallisuusominaisuudet, joissa ei haluta päätyä virhetilaan, sekä elinkykyisyysominaisuudet, joiden mukaan jokin hyväksytty tapahtuma tapahtuu riittävän usein tai aina.

Järjestelmä kuvataan usein tilakoneena, Kripke-merkistönä tai tilaverkkona, jossa tilat kuvaavat järjestelmän tiloja ja siirtymät kuvaavat tilansiirtymiä. Ominaisuuksia ilmaistaan temporaalilausekkein, kuten LTL tai CTL. Verifiointi pyrkii todentamaan, että määritellyt ominaisuudet pitävät kaikissa mahdollisissa suorituksissa; epäonnistuessa voidaan osoittaa virheellinen polku.

Päämenelmät ovat explicit-state -mallintarkastus sekä symbolinen mallintarkastus (esim. BDD- ja SMT-pohjaiset tekniikat). Myös rajattu mallintarkastus (bounded model checking) sekä abstraktio ja komponointinen verifiointi ovat yleisiä. Tavoitteena on hallita tilan räjähtämistä ja parantaa skaalautuvuutta.

Sovellukset kattavat sulautetut järjestelmät ja teolliset ohjausjärjestelmät, ohjelmistojen varmistus, verkkoprotokollat sekä aikaisiin järjestelmiin liittyvät analyysit. Alalla käytetään työkaluja kuten SPIN, NuSMV, UPPAAL ja PRISM.

Haasteita ovat tilan räjähtäminen, epärealististen mallien rakentuminen sekä skaalautuvuuden ongelmat; näitä torjutaan abstraktion, symmetrian hyödyntämisen ja osittaisella verifioinnilla.