In u mo parè, in u settore in lingua russa di l'Internet, u tema di a verificazione formale ùn hè micca abbastanza coperta, è ci hè soprattuttu una mancanza di esempi simplici è chjaru.
Daraghju un esempiu da una fonte straniera, è aghjunghje a mo solu suluzione à u prublema ben cunnisciutu di attraversà un lupu, un caprettu è una col à l'altra parte di u fiume.
Ma prima, descriveraghju brevemente ciò chì a verificazione formale hè è perchè hè necessariu.
A verificazione formale generalmente significa cuntrollà un prugramma o algoritmu utilizendu un altru.
Questu hè necessariu per assicurà chì u prugramma si cumporta cum'è previstu è ancu per assicurà a so sicurità.
A verificazione formale hè u mezzu più putente di truvà è eliminà e vulnerabilità: permette di truvà tutti i buchi esistenti è i bug in un prugramma, o pruvucà chì ùn esistenu micca.
Hè da nutà chì in certi casi questu hè impussibile, cum'è in u prublema di 8 regine cù una larghezza di tavulinu di 1000 quadrati: tuttu hè ghjuntu à a cumplessità algoritmica o u prublema di stopping.
Tuttavia, in ogni casu, una di e trè risposte serà ricevutu: u prugramma hè currettu, sbagliatu, o ùn era micca pussibule di calculà a risposta.
S'ellu hè impussibile di truvà una risposta, hè spessu pussibule di rielaborazione di parti pocu chjaru di u prugramma, riducendu a so cumplessità algoritmica, per ottene una risposta specifica sì o no.
È a verificazione formale hè aduprata, per esempiu, in u kernel di Windows è i sistemi operativi di drone Darpa, per assicurà u massimu livellu di prutezzione.
Useremu Z3Prover, un strumentu assai putente per a prova automatizata di teoremi è a risoluzione di equazioni.
Inoltre, Z3 risolve equazioni, è ùn selezziunate micca i so valori cù a forza bruta.
Questu significa chì hè capace di truvà a risposta, ancu in i casi induve ci sò 10 ^ 100 cumminazzioni di opzioni di input.
Ma questu hè solu una decina d'argumenti di input di tipu Integer, è questu hè spessu scontru in pratica.
Prublemu circa 8 regine (Pigliatu da l'inglese ).
# We know each queen must be in a different row.
# So, we represent each queen by a single integer: the column position
Q = [ Int('Q_%i' % (i + 1)) for i in range(8) ]
# Each queen is in a column {1, ... 8 }
val_c = [ And(1 <= Q[i], Q[i] <= 8) for i in range(8) ]
# At most one queen per column
col_c = [ Distinct(Q) ]
# Diagonal constraint
diag_c = [ If(i == j,
True,
And(Q[i] - Q[j] != i - j, Q[i] - Q[j] != j - i))
for i in range(8) for j in range(i) ]
solve(val_c + col_c + diag_c)
Running Z3, avemu a suluzione:
[Q_5 = 1,
Q_8 = 7,
Q_3 = 8,
Q_2 = 2,
Q_6 = 3,
Q_4 = 6,
Q_7 = 5,
Q_1 = 4]
U prublema di a regina hè paragunabile à un prugramma chì piglia cum'è input e coordenate di 8 regine è dà a risposta se e regine si battenu l'una l'altra.
S'ellu ci vole à risolve un tali prugramma cù a verificazione formale, allora paragunatu à u prublema, avaristi solu bisognu di fà un passu in più in a forma di cunvertisce u codice di u prugramma in una equazioni: risulterà esse essenzialmente identica à a nostra ( di sicuru, se u prugramma hè statu scrittu currettamente).
Quasi listessa cosa succederà in u casu di ricerca di vulnerabilità: avemu solu stabilitu e cundizioni di output chì avemu bisognu, per esempiu, a password di l'amministratore, trasfurmà u codice fonte o decompilatu in equazioni cumpatibili cù a verificazione, è dopu avè una risposta à ciò chì dati deve esse furnitu cum'è input per ghjunghje u scopu.
In u mo scusa, u prublema di u lupu, u caprettu è a col hè ancu più interessante, postu chì a risolviri hè digià bisognu di parechji (7) passi.
Se u prublema di a regina hè paragunabbili à u casu induve pudete penetrà in un servitore cù una sola dumanda GET o POST, allura u lupu, u caprettu è a col dimustra un esempiu da una categuria assai più cumplessa è diffusa, in quale u scopu pò esse rializatu solu. da parechje richieste.
Questu hè paragunabile, per esempiu, à un scenariu induve avete bisognu di truvà una iniezione SQL, scrivite un schedariu per ellu, dopu elevà i vostri diritti è solu dopu avè una password.
Cundizioni di u prublema è a so suluzioneL'agricultore hà bisognu di trasportu un lupu, una capra è una col à traversu u fiume. L'agricultore hà una barca chì pò accoglie solu un ughjettu, in più di l'agricultore stessu. U lupu manghjarà u caprettu è u caprettu manghjarà a col s'ellu l'agricultore li lassa senza cura.
A suluzione hè chì in u passu 4 l'agricultore hà bisognu di ripiglià u caprettu.
Avà cuminciamu à risolve u prugramma.
Denotemu l'agricultore, u lupu, u caprettu è u colu cum'è 4 variàbili chì piglianu u valore solu 0 o 1. Zero significa chì sò nantu à a riva manca, è unu significa chì sò à diritta.
import json
from z3 import *
s = Solver()
Num= 8
Human = [ Int('Human_%i' % (i + 1)) for i in range(Num) ]
Wolf = [ Int('Wolf_%i' % (i + 1)) for i in range(Num) ]
Goat = [ Int('Goat_%i' % (i + 1)) for i in range(Num) ]
Cabbage = [ Int('Cabbage_%i' % (i + 1)) for i in range(Num) ]
# Each creature can be only on left (0) or right side (1) on every state
HumanSide = [ Or(Human[i] == 0, Human[i] == 1) for i in range(Num) ]
WolfSide = [ Or(Wolf[i] == 0, Wolf[i] == 1) for i in range(Num) ]
GoatSide = [ Or(Goat[i] == 0, Goat[i] == 1) for i in range(Num) ]
CabbageSide = [ Or(Cabbage[i] == 0, Cabbage[i] == 1) for i in range(Num) ]
Side = HumanSide+WolfSide+GoatSide+CabbageSide
Num hè u numeru di passi necessarii per risolve. Ogni passu rapprisenta u statu di u fiume, a barca è tutte e entità.
Per avà, scegliemu à l'aleatoriu è cun un margine, pigliate 10.
Ogni entità hè rapprisintata in 10 copie - questu hè u so valore à ognunu di i 10 passi.
Avà stabilitu e cundizioni per u principiu è a fine.
Start = [ Human[0] == 0, Wolf[0] == 0, Goat[0] == 0, Cabbage[0] == 0 ]
Finish = [ Human[9] == 1, Wolf[9] == 1, Goat[9] == 1, Cabbage[9] == 1 ]
Allora avemu stabilitu e cundizioni induve u lupu manghja u caprettu, o u caprettu manghja a col, cum'è limitazioni in l'equazioni.
(In presenza di un agricultore, l'aggressione hè impussibile)
# Wolf cant stand with goat, and goat with cabbage without human. Not 2, not 0 which means that they are one the same side
Safe = [ And( Or(Wolf[i] != Goat[i], Wolf[i] == Human[i]), Or(Goat[i] != Cabbage[i], Goat[i] == Human[i])) for i in range(Num) ]
È infine, avemu da definisce tutte l'azzioni pussibuli di l'agricultore quandu attraversà quì o torna.
Si pò piglià un lupu, un caprettu o una col cù ellu, o ùn piglià nimu, o ùn navigà in ogni locu.
Di sicuru, nimu pò attraversà senza un agricultore.
Questu serà spressu da u fattu chì ogni statu dopu di u fiumu, barca è entità pò differisce da u precedente solu in una manera strettamente limitata.
No più di 2 bits, è cù assai altri limiti, postu chì l'agricultore pò esse trasportatu solu una entità à tempu è micca tutti ponu esse lasciati inseme.
Travel = [ Or(
And(Human[i] == Human[i+1] + 1, Wolf[i] == Wolf[i+1] + 1, Goat[i] == Goat[i+1], Cabbage[i] == Cabbage[i+1]),
And(Human[i] == Human[i+1] + 1, Goat[i] == Goat[i+1] + 1, Wolf[i] == Wolf[i+1], Cabbage[i] == Cabbage[i+1]),
And(Human[i] == Human[i+1] + 1, Cabbage[i] == Cabbage[i+1] + 1, Wolf[i] == Wolf[i+1], Goat[i] == Goat[i+1]),
And(Human[i] == Human[i+1] - 1, Wolf[i] == Wolf[i+1] - 1, Goat[i] == Goat[i+1], Cabbage[i] == Cabbage[i+1]),
And(Human[i] == Human[i+1] - 1, Goat[i] == Goat[i+1] - 1, Wolf[i] == Wolf[i+1], Cabbage[i] == Cabbage[i+1]),
And(Human[i] == Human[i+1] - 1, Cabbage[i] == Cabbage[i+1] - 1, Wolf[i] == Wolf[i+1], Goat[i] == Goat[i+1]),
And(Wolf[i] == Wolf[i+1], Goat[i] == Goat[i+1], Cabbage[i] == Cabbage[i+1])) for i in range(Num-1) ]
Andemu a suluzione.
solve(Side + Start + Finish + Safe + Travel)
È avemu a risposta!
Z3 hà trovu un inseme consistente di stati chì satisface tutte e cundizioni.
Un tipu di cast quadridimensionale di u spaziu-tempu.
Scupritemu ciò chì hè accadutu.
Avemu vistu chì à a fine tutti attraversò, solu à u primu u nostru agricultore hà decisu di riposu, è in i primi 2 passi ùn hà micca natà in ogni locu.
Human_2 = 0
Human_3 = 0
Questu suggerisce chì u numeru di stati chì avemu sceltu hè eccessivu, è 8 serà abbastanza abbastanza.
In u nostru casu, l'agricultore hà fattu questu: principià, riposu, riposu, attraversà u caprettu, cruciate in daretu, attraversà a col, vultà cù u caprettu, attraversà u lupu, vultà solu, rinvià u caprettu.
Ma à a fine u prublema hè stata risolta.
#Старт.
Human_1 = 0
Wolf_1 = 0
Goat_1 = 0
Cabbage_1 = 0
#Фермер отдыхает.
Human_2 = 0
Wolf_2 = 0
Goat_2 = 0
Cabbage_2 = 0
#Фермер отдыхает.
Human_3 = 0
Wolf_3 = 0
Goat_3 = 0
Cabbage_3 = 0
#Фермер отвозит козу на нужный берег.
Human_4 = 1
Wolf_4 = 0
Goat_4 = 1
Cabbage_4 = 0
#Фермер возвращается.
Human_5 = 0
Wolf_5 = 0
Goat_5 = 1
Cabbage_5 = 0
#Фермер отвозит капусту на нужный берег.
Human_6 = 1
Wolf_6 = 0
Cabbage_6 = 1
Goat_6 = 1
#Ключевая часть операции: фермер возвращает козу обратно.
Human_7 = 0
Wolf_7 = 0
Goat_7 = 0
Cabbage_7 = 1
#Фермер отвозит волка на другой берег, где он теперь находится вместе с капустой.
Human_8 = 1
Wolf_8 = 1
Goat_8 = 0
Cabbage_8 = 1
#Фермер возвращается за козой.
Human_9 = 0
Wolf_9 = 1
Goat_9 = 0
Cabbage_9 = 1
#Фермер повторно доставляет козу на нужный берег и завершают переправу.
Human_10 = 1
Wolf_10 = 1
Goat_10 = 1
Cabbage_10 = 1
Avà pruvemu à cambià e cundizioni è pruvemu chì ùn ci hè micca suluzione.
Per fà questu, daremu à u nostru lupu erbivoru, è ellu vulete manghjà col.
Questu pò esse paragunatu à u casu in u quale u nostru scopu hè di assicurà l'appiecazione è avemu bisognu di assicurà chì ùn ci sò micca loopholes.
Safe = [ And( Or(Wolf[i] != Goat[i], Wolf[i] == Human[i]), Or(Goat[i] != Cabbage[i], Goat[i] == Human[i]), Or(Wolf[i] != Cabbage[i], Goat[i] == Human[i])) for i in range(Num) ]
Z3 ci hà datu a seguente risposta:
no solution
Significa chì ùn ci hè veramente micca suluzione.
Cusì, avemu dimustratu programaticamente l'impossibilità di attraversà un lupu omnivoru senza pèrdite per l'agricultore.
Se l'audienza trova stu tema interessante, allora in articuli futuri vi dicu cumu trasfurmà un prugramma o funzione ordinariu in una equazione cumpatibile cù i metudi formali, è risolve, cusì palesanu tutti i scenarii legittimi è vulnerabili. Prima, nantu à u listessu compitu, ma prisintatu in a forma di un prugramma, è dopu à pocu à pocu cumplicà è si passa à esempi attuali da u mondu di u sviluppu di software.
U prossimu articulu hè digià prontu:
In questu passa da a verificazione formale di i prublemi à i prugrammi, è discrive
cumu pudete cunvertisce in sistemi di regule formale automaticamente.
Source: www.habr.com