De reținut
- Metodele formale folosesc specificații precise, matematice. Model checker-ele explorează fiecare stare accesibilă a unui model, în anumite limite; demonstratoarele stabilesc proprietăți pentru toate datele de intrare.
- Excelează acolo unde testarea are dificultăți: concurență, protocoale distribuite, intercalări rare și nucleele critice pentru securitate. Contraexemplele vin ca trace-uri exacte, pas cu pas.
- Verifică față de o specificație și niște presupuneri, nu față de realitate. Testarea rămâne esențială, pentru erorile din specificație, părțile neverificate, mediu și diferența dintre model și cod.
De unde pornim
Ai văzut că testarea e o problemă de eșantionare și că unele defecțiuni din sistemele distribuite au nevoie de intercalări rare. Metodele formale atacă exact această slăbiciune: în loc să eșantioneze, raționează despre toate comportamentele unui sistem descris precis.
Spectrul
| Nivel | Exemple | Efort | Ce obții |
|---|---|---|---|
| Ușor | Sisteme de tipuri puternice, contracte, analizoare statice | Mic | Clase întregi de erori excluse automat |
| Specificație + model checking | TLA+ cu model checker-ul TLC, Alloy, SPIN | Mediu | Explorarea exhaustivă a unui design, în anumite limite; trace-uri de contraexemplu |
| Model checking la nivel de cod și execuție simbolică | Model checker-e mărginite, precum CBMC; unelte de execuție simbolică, precum KLEE | Mediu–mare | Drumuri prin codul real, explorate sistematic; bug-uri cu date de intrare concrete |
| Demonstrație | Demonstratoare interactive, precum Isabelle și Coq/Rocq; sisteme verificate, precum microkernel-ul seL4 și compilatorul C CompCert | Mare | Garanții matematice pentru toate datele de intrare, relativ la specificație |
Model checking-ul, pe scurt
Descrii un sistem prin stări și tranziții, într-un limbaj de specificare, împreună cu proprietăți:
- Proprietăți de siguranță (safety): ceva rău nu se întâmplă niciodată. „Două noduri nu sunt niciodată lider în același timp.”
- Proprietăți de vivacitate (liveness): ceva bun se întâmplă până la urmă. „Fiecare cerere primește până la urmă un răspuns.”
Model checker-ul explorează toate stările accesibile, în limitele configurate, de exemplu 3 noduri, 2 defecțiuni și 4 mesaje în tranzit, și fie confirmă că proprietățile sunt respectate în toate, fie produce un contraexemplu: secvența exactă de pași care duce la o încălcare.
Un fragment TLA+ minuscul pentru un sistem de transferuri bancare ar putea spune:
TotalMoney == balance["A"] + balance["B"]
Invariant == TotalMoney = 100 /\ \A acc \in Accounts : balance[acc] >= 0
TLC verifică apoi fiecare intercalare a transferurilor concurente, inclusiv cu defecțiuni, față de acest invariant.
În „How Amazon Web Services Uses Formal Methods” (Communications of the ACM, 2015), Chris Newcombe și colegii săi au descris cum inginerii AWS foloseau din 2011 limbajul de specificare TLA+ pentru sisteme distribuite complexe, inclusiv părți din S3, DynamoDB și EBS.
Pentru DynamoDB, model checker-ul a găsit un bug subtil care putea pierde date dacă o anumită secvență de defecțiuni și pași de recuperare se intercala cu alte procesări. Cel mai scurt trace care îl arăta avea 35 de pași de nivel înalt. Designul trecuse deja printr-o testare extinsă și prin analize atente, care nu-l scoseseră la iveală.
Autorii au raportat că specificarea formală a îmbunătățit și înțelegerea designurilor și le-a dat inginerilor încrederea de a face optimizări agresive.
Lecția: în designurile distribuite, unele bug-uri au nevoie de secvențe lungi și specifice de evenimente. Explorarea exhaustivă a unui model le găsește; eșantionarea lor prin testare e foarte puțin probabilă.
Ce înseamnă și ce nu înseamnă „verificat”
Garanțiile formale sunt mereu relative:
- La specificație: dacă specificației îi lipsește o cerință sau formulează una greșită, demonstrația e despre lucrul greșit.
- La limite: model checking-ul cu 3 noduri nu demonstrează că 5 noduri sunt sigure, deși majoritatea bug-urilor de protocol apar la dimensiuni mici.
- La diferența dintre model și cod: un design verificat poate fi implementat greșit.
- La presupuneri: despre hardware, compilatoare, sisteme de operare și datele de intrare.
Unde intră testerii
Nu trebuie să fii matematician ca să beneficiezi:
- Scrie proprietăți. Testerii gândesc deja în invarianți și în „ce nu trebuie să se întâmple niciodată”. Exact de asta au nevoie specificațiile.
- Analizează specificațiile ca pe niște cerințe: proprietățile ambigue, lipsă sau greșite sunt principalul risc.
- Transformă contraexemplele în teste. Un trace de model checker e un scenariu precis și reproductibil; rulează-l din nou pe sistemul real.
- Testează diferența. Folosește testarea bazată pe modele sau teste de conformitate ca să verifici că implementarea corespunde designului verificat.
- Începe cu varianta ușoară. Tipurile mai stricte, contractele și analiza statică dau garanții de tip formal cu efort mic.
Când merită
- Da: protocoale de consens și replicare, logica de plăți și de registre contabile, primitive de concurență, parsere critice pentru securitate, control critic pentru siguranță, orice sistem în care un bug rar e catastrofal.
- Probabil nu: fluxuri de UI, CRUD simplu, prototipuri care se schimbă repede. Acolo, testarea și un design bun aduc mai multă valoare.
Așa da
Să verifici cu model checking designul unui nou protocol de replicare sau de blocare înainte să-l implementezi, apoi să rulezi fiecare contraexemplu ca test de regresie pe cod.
Așa nu
Să tratezi „verificat formal” ca „nu mai trebuie testat”. Specificațiile, limitele, componentele neverificate și mediul au în continuare nevoie de testare.
Verifică-te
O echipă a verificat cu model checking designul alegerii liderului, cu 3 noduri, și n-a găsit nicio încălcare. Un manager conchide că „alegerea liderului e demonstrată corectă”. Ce ai sublinia?
Arată răspunsul
Rezultatul e valabil pentru model și în limitele lui: 3 noduri și defecțiunile și momentele modelate. Nu acoperă clustere mai mari, comportamente lăsate în afara specificației sau diferențele dintre implementare și design. Propune verificarea cu limite mai mari, unde e fezabil, analiza presupunerilor specificației și testarea conformității implementării, cu injectare de defecte și cu scenariile de contraexemplu.
