Formell Verifizéierung ass d'Verifizéierung vun engem Programm oder Algorithmus mat engem aneren.
Dëst ass eng vun de mächtegste Methoden, déi Iech erlaabt all Schwächen an engem Programm ze fannen oder ze beweisen datt se net existéieren.
Eng méi detailléiert Beschreiwung vun der formell Verifikatioun kann am Beispill vun léisen de Problem vun gesi ginn a mengem fréieren Artikel.
An dësem Artikel réckelen ech vun der formeller Verifizéierung vu Probleemer op Programmer a beschreiwen wéi
wéi kënne se automatesch an formell Regelsystemer ëmgewandelt ginn.
Fir dëst ze maachen, hunn ech meng eegen Analog vun enger virtueller Maschinn geschriwwen, mat symbolesche Prinzipien.
Et parséiert de Programmcode an iwwersetzt en an e System vun Equatiounen (SMT), dee scho programmatesch geléist ka ginn.
Well d'Informatioun iwwer symbolesch Berechnungen am Internet zimlech fragmentaresch presentéiert gëtt,
Ech wäert kuerz beschreiwen wat et ass.
Symbolesch Berechnung ass e Wee fir gläichzäiteg e Programm op eng breet Palette vun Daten auszeféieren an ass den Haaptinstrument fir formell Programmverifizéierung.
Zum Beispill kënne mir Inputbedéngungen astellen, wou dat éischt Argument all positiv Wäerter kann huelen, déi zweet negativ, déi drëtt Null, an d'Ausgangsargument, zum Beispill 42.
Symbolesch Berechnungen an engem Laf ginn eis d'Äntwert op ob et méiglech ass fir eis dat gewënschte Resultat ze kréien an e Beispill vun enger Rei vun esou Inputparameter. Oder Beweis datt et keng esou Parameteren sinn.
Ausserdeem kënne mir d'Input Argumenter op all méiglech setzen, a wielt nëmmen d'Ausgab, zum Beispill d'Administrator Passwuert.
An dësem Fall fanne mir all Schwachstelle vum Programm oder kréien Beweis datt d'Administrateurspasswuert sécher ass.
Et kann feststellen datt déi klassesch Ausféierung vun engem Programm mat spezifeschen Inputdaten e spezielle Fall vu symbolescher Ausféierung ass.
Dofir kann mäi Charakter VM och am Emulatiounsmodus vun enger Standard virtueller Maschinn schaffen.
An de Kommentaren zum viregten Artikel kann ee faire Kritik un der formell Verifizéierung mat enger Diskussioun iwwer seng Schwächen fannen.
D'Haaptproblemer sinn:
- Kombinatoresch Explosioun, well formell Verifizéierung schlussendlech op P = NP erof geet
- Veraarbechtung vun Uruff un de Dateiesystem, Netzwierker an aner extern Späichere ass méi schwéier ze verifizéieren
- Bugs an der Spezifizéierung, wann de Client oder de Programméierer eng Saach virgesinn huet, awer et net präzis genuch an der technescher Spezifizéierung beschriwwen huet.
Als Resultat gëtt de Programm verifizéiert a entsprécht der Spezifizéierung, awer wäert eppes komplett anescht maachen wéi d'Creatoren dovunner erwaart hunn.
Well ech an dësem Artikel haaptsächlech d'Benotzung vun der formeller Verifizéierung an der Praxis berücksichtegen, wäert ech de Kapp fir de Moment net op d'Mauer schloen, a wäert e System wielen wou d'algorithmesch Komplexitéit an d'Zuel vun externen Uruff minimal sinn.
Well Smart Kontrakter am Beschten dës Ufuerderunge passen, ass de Choix op RIDE Kontrakter vun der Waves Plattform gefall: si sinn net Turing komplett, an hir maximal Komplexitéit ass kënschtlech limitéiert.
Awer mir wäerte se exklusiv vun der technescher Säit betruechten.
Zousätzlech zu allem ass eng formell Verifizéierung besonnesch gefuerdert fir all Kontrakter: et ass normalerweis onméiglech fir e Kontraktfehler ze korrigéieren nodeems se lancéiert gouf.
An d'Käschte vun esou Feeler kënne ganz héich sinn, well zimlech grouss Quantitéiten u Fongen dacks op Smart Kontrakter gespäichert ginn.
Meng symbolesch virtuell Maschinn ass an PHP a Python geschriwwen, a benotzt Z3Prover vu Microsoft Research fir déi resultéierend SMT Formelen ze léisen.
Am Kär ass eng mächteg Multi-transaktiouns Sich, déi
erlaabt Iech Léisungen oder Schwachstelle ze fannen, och wann et vill Transaktiounen erfuerdert.
Och déi , ee vun de mächtegste symbolesche Kaderen fir Ethereum Schwachstelle ze fannen, huet dës Fäegkeet nëmmen e puer Méint bäigefüügt.
Awer et ass derwäert ze bemierken datt Etherkontrakter méi komplex sinn an Turing komplett.
PHP iwwersetzt de Quellcode vum RIDE Smart Kontrakt an e Python Skript, an deem de Programm als Z3 SMT-kompatibel System vu Kontraktstaaten a Konditioune fir hir Iwwergäng presentéiert gëtt:
Elo wäert ech beschreiwen wat dobannen geschitt méi am Detail.
Awer als éischt e puer Wierder iwwer d'RIDE Smart Kontrakt Sprooch.
Et ass eng funktionell an Ausdrock-baséiert Programméierungssprooch déi faul ass vum Design.
RIDE leeft isoléiert bannent der Blockchain a kann Informatioun aus der Späichere recuperéieren a schreiwen, déi mam Portemonnaie vum Benotzer verbonne sinn.
Dir kënnt e RIDE Kontrakt op all Portemonnaie befestegt, an d'Resultat vun der Ausféierung gëtt nëmmen TRUE oder FALSE.
TRUE heescht datt de Smart Kontrakt d'Transaktioun erlaabt, a FALSE heescht datt et et verbitt.
En einfacht Beispill: e Skript kann en Transfer verbidden wann de Portmonni Gläichgewiicht manner wéi 100 ass.
Als Beispill wäert ech dee selwechte Wolf, Geess a Kabes huelen, awer schonn a Form vun engem Smart Kontrakt presentéiert.
De Benotzer wäert net fäeg sinn Suen aus dem Portemonnaie zréckzéien, op deem de Kontrakt ofgesat ass, bis hien jiddereen op déi aner Säit geschéckt huet.
#Извлекаем положение всех объектов из блокчейна
let contract = tx.sender
let human= extract(getInteger(contract,"human"))
let wolf= extract(getInteger(contract,"wolf"))
let goat= extract(getInteger(contract,"goat"))
let cabbage= extract(getInteger(contract,"cabbage"))
#Это так называемая дата-транзакция, в которой пользователь присылает новые 4 переменные.
#Контракт разрешит её только в случае если все объекты останутся в сохранности.
match tx {
case t:DataTransaction =>
#Извлекаем будущее положение всех объектов из транзакции
let newHuman= extract(getInteger(t.data,"human"))
let newWolf= extract(getInteger(t.data,"wolf"))
let newGoat= extract(getInteger(t.data,"goat"))
let newCabbage= extract(getInteger(t.data,"cabbage"))
#0 обозначает, что объект на левом берегу, а 1 что на правом
let humanSide= human == 0 || human == 1
let wolfSide= wolf == 0 || wolf == 1
let goatSide= goat == 0 || goat == 1
let cabbageSide= cabbage == 0 || cabbage == 1
let side= humanSide && wolfSide && goatSide && cabbageSide
#Будут разрешены только те транзакции, где с козой никого нет в отсутствии фермера.
let safeAlone= newGoat != newWolf && newGoat != newCabbage
let safe= safeAlone || newGoat == newHuman
let humanTravel= human != newHuman
#Способы путешествия фермера туда и обратно, с кем-то либо в одиночку.
let t1= humanTravel && newWolf == wolf + 1 && newGoat == goat && newCabbage == cabbage
let t2= humanTravel && newWolf == wolf && newGoat == goat + 1 && newCabbage == cabbage
let t3= humanTravel && newWolf == wolf && newGoat == goat && newCabbage == cabbage + 1
let t4= humanTravel && newWolf == wolf - 1 && newGoat == goat && newCabbage == cabbage
let t5= humanTravel && newWolf == wolf && newGoat == goat - 1 && newCabbage == cabbage
let t6= humanTravel && newWolf == wolf && newGoat == goat && newCabbage == cabbage - 1
let t7= humanTravel && newWolf == wolf && newGoat == goat && newCabbage == cabbage
let objectTravel = t1 || t2 || t3 || t4 || t5 || t6 || t7
#Последняя строка в разделе транзакции описывает разрешающее транзакцию условие.
#Переменные транзакции должны иметь значения 1 или 0, все объекты должны
#быть в безопасности, а фермер должен переплывать реку в одиночку
#или с кем-то на каждом шагу
side && safe && humanTravel && objectTravel
case s:TransferTransaction =>
#Транзакция вывода средств разрешена только в случае если все переплыли на другой берег
human == 1 && wolf == 1 && goat == 1 && cabbage == 1
#Все прочие типы транзакций запрещены
case _ => false
}
PHP extrahéiert als éischt all Variabelen aus dem Smart Kontrakt a Form vun hire Schlësselen an der entspriechender boolescher Ausdrockvariabel.
cabbage: extract ( getInteger ( contract , "cabbage" ) )
goat: extract ( getInteger ( contract , "goat" ) )
human: extract ( getInteger ( contract , "human" ) )
wolf: extract ( getInteger ( contract , "wolf" ) )
fState: human== 1 && wolf== 1 && goat== 1 && cabbage== 1
fState:
wolf:
goat:
cabbage:
cabbageSide: cabbage== 0 || cabbage== 1
human: extract ( getInteger ( contract , "human" ) )
newGoat: extract ( getInteger ( t.data , "goat" ) )
newHuman: extract ( getInteger ( t.data , "human" ) )
goatSide: goat== 0 || goat== 1
humanSide: human== 0 || human== 1
t7: humanTravel && newWolf== wolf && newGoat== goat && newCabbage== cabbage
t3: humanTravel && newWolf== wolf && newGoat== goat && newCabbage== cabbage + 1
t6: humanTravel && newWolf== wolf && newGoat== goat && newCabbage== cabbage - 1
t2: humanTravel && newWolf== wolf && newGoat== goat + 1 && newCabbage== cabbage
t5: humanTravel && newWolf== wolf && newGoat== goat - 1 && newCabbage== cabbage
t1: humanTravel && newWolf== wolf + 1 && newGoat== goat && newCabbage== cabbage
t4: humanTravel && newWolf== wolf - 1 && newGoat== goat && newCabbage== cabbage
safeAlone: newGoat != newWolf && newGoat != newCabbage
wolfSide: wolf== 0 || wolf== 1
humanTravel: human != newHuman
side: humanSide && wolfSide && goatSide && cabbageSide
safe: safeAlone || newGoat== newHuman
objectTravel: t1 || t2 || t3 || t4 || t5 || t6 || t7
PHP konvertéiert se dann an eng Z3Prover SMT-kompatibel Systembeschreiwung am Python.
D'Daten sinn an enger Loop gewéckelt, wou Späichervariablen den Index i kréien, Transaktiounsvariablen Index i + 1, a Variablen mat Ausdrock setzen d'Regele fir den Iwwergang vum fréiere Staat an den nächsten.
Dëst ass d'Häerz vun eiser virtueller Maschinn, déi e multi-transaktionelle Sichmechanismus ubitt.
fState: And( And( And( human[Steps] == 1 , wolf[Steps] == 1 ) , goat[Steps] == 1 ) , cabbage[Steps] == 1 )
final: fState[Steps]
fState:
wolf:
goat:
cabbage:
cabbageSide: Or( cabbage[i] == 0 , cabbage[i] == 1 )
goatSide: Or( goat[i] == 0 , goat[i] == 1 )
humanSide: Or( human[i] == 0 , human[i] == 1 )
t7: And( And( And( humanTravel[i] , wolf == wolf[i] ) , goat[i+1] == goat[i] ) , cabbage == cabbage[i] )
t3: And( And( And( humanTravel[i] , wolf == wolf[i] ) , goat[i+1] == goat[i] ) , cabbage == cabbage[i] + 1 )
t6: And( And( And( humanTravel[i] , wolf == wolf[i] ) , goat[i+1] == goat[i] ) , cabbage == cabbage[i] - 1 )
t2: And( And( And( humanTravel[i] , wolf == wolf[i] ) , goat[i+1] == goat[i] + 1 ) , cabbage == cabbage[i] )
t5: And( And( And( humanTravel[i] , wolf == wolf[i] ) , goat[i+1] == goat[i] - 1 ) , cabbage == cabbage[i] )
t1: And( And( And( humanTravel[i] , wolf == wolf[i] + 1 ) , goat[i+1] == goat[i] ) , cabbage == cabbage[i] )
t4: And( And( And( humanTravel[i] , wolf == wolf[i] - 1 ) , goat[i+1] == goat[i] ) , cabbage == cabbage[i] )
safeAlone: And( goat[i+1] != wolf , goat[i+1] != cabbage )
wolfSide: Or( wolf[i] == 0 , wolf[i] == 1 )
humanTravel: human[i] != human[i+1]
side: And( And( And( humanSide[i] , wolfSide[i] ) , goatSide[i] ) , cabbageSide[i] )
safe: Or( safeAlone[i] , goat[i+1] == human[i+1] )
objectTravel: Or( Or( Or( Or( Or( Or( t1[i] , t2[i] ) , t3[i] ) , t4[i] ) , t5[i] ) , t6[i] ) , t7[i] )
data: And( And( And( side[i] , safe[i] ) , humanTravel[i] ) , objectTravel[i] )
D'Konditioune ginn zortéiert an an eng Skript-Schabloun agebaut fir de SMT-System am Python ze beschreiwen.
Blank Schabloun
import json
from z3 import *
s = Solver()
Steps=7
Num= Steps+1
$code$
#template, only start rest
s.add(data + start)
#template
s.add(final)
ind = 0
f = open("/var/www/html/all/bin/python/log.txt", "a")
while s.check() == sat:
ind = ind +1
print ind
m = s.model()
print m
print "traversing model..."
#for d in m.decls():
#print "%s = %s" % (d.name(), m[d])
f.write(str(m))
f.write("nn")
exit()
#s.add(Or(goat[0] != s.model()[data[0]] )) # prevent next model from using the same assignment as a previous model
print "Total solution number: "
print ind
f.close()
Fir de leschte Staat an der ganzer Kette ginn d'Regele applizéiert, déi an der Transaktiounssektioun spezifizéiert sinn.
Dëst bedeit datt Z3Prover genee sou Sets vu Konditioune sicht, déi schlussendlech Fongen aus dem Kontrakt zréckzéien.
Als Resultat kréien mir automatesch e voll funktionnelle SMT Modell vun eisem Kontrakt.
Dir kënnt gesinn datt et ganz ähnlech mam Modell aus mengem fréieren Artikel ass, deen ech manuell zesummegesat hunn.
Fäerdeg Schabloun
import json
from z3 import *
s = Solver()
Steps=7
Num= Steps+1
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) ]
nothing= [ And( human[i] == human[i+1], wolf[i] == wolf[i+1], goat[i] == goat[i+1], cabbage[i] == cabbage[i+1] ) for i in range(Num-1) ]
start= [ human[0] == 1, wolf[0] == 0, goat[0] == 1, cabbage[0] == 0 ]
safeAlone= [ And( goat[i+1] != wolf[i+1] , goat[i+1] != cabbage[i+1] ) for i in range(Num-1) ]
safe= [ Or( safeAlone[i] , goat[i+1] == human[i+1] ) for i in range(Num-1) ]
humanTravel= [ human[i] != human[i+1] for i in range(Num-1) ]
cabbageSide= [ Or( cabbage[i] == 0 , cabbage[i] == 1 ) for i in range(Num-1) ]
goatSide= [ Or( goat[i] == 0 , goat[i] == 1 ) for i in range(Num-1) ]
humanSide= [ Or( human[i] == 0 , human[i] == 1 ) for i in range(Num-1) ]
t7= [ And( And( And( humanTravel[i] , wolf[i+1] == wolf[i] ) , goat[i+1] == goat[i] ) , cabbage[i+1] == cabbage[i] ) for i in range(Num-1) ]
t3= [ And( And( And( humanTravel[i] , wolf[i+1] == wolf[i] ) , goat[i+1] == goat[i] ) , cabbage[i+1] == cabbage[i] + 1 ) for i in range(Num-1) ]
t6= [ And( And( And( humanTravel[i] , wolf[i+1] == wolf[i] ) , goat[i+1] == goat[i] ) , cabbage[i+1] == cabbage[i] - 1 ) for i in range(Num-1) ]
t2= [ And( And( And( humanTravel[i] , wolf[i+1] == wolf[i] ) , goat[i+1] == goat[i] + 1 ) , cabbage[i+1] == cabbage[i] ) for i in range(Num-1) ]
t5= [ And( And( And( humanTravel[i] , wolf[i+1] == wolf[i] ) , goat[i+1] == goat[i] - 1 ) , cabbage[i+1] == cabbage[i] ) for i in range(Num-1) ]
t1= [ And( And( And( humanTravel[i] , wolf[i+1] == wolf[i] + 1 ) , goat[i+1] == goat[i] ) , cabbage[i+1] == cabbage[i] ) for i in range(Num-1) ]
t4= [ And( And( And( humanTravel[i] , wolf[i+1] == wolf[i] - 1 ) , goat[i+1] == goat[i] ) , cabbage[i+1] == cabbage[i] ) for i in range(Num-1) ]
wolfSide= [ Or( wolf[i] == 0 , wolf[i] == 1 ) for i in range(Num-1) ]
side= [ And( And( And( humanSide[i] , wolfSide[i] ) , goatSide[i] ) , cabbageSide[i] ) for i in range(Num-1) ]
objectTravel= [ Or( Or( Or( Or( Or( Or( t1[i] , t2[i] ) , t3[i] ) , t4[i] ) , t5[i] ) , t6[i] ) , t7[i] ) for i in range(Num-1) ]
data= [ Or( And( And( And( side[i] , safe[i] ) , humanTravel[i] ) , objectTravel[i] ) , nothing[i]) for i in range(Num-1) ]
fState= And( And( And( human[Steps] == 1 , wolf[Steps] == 1 ) , goat[Steps] == 1 ) , cabbage[Steps] == 1 )
final= fState
#template, only start rest
s.add(data + start)
#template
s.add(final)
ind = 0
f = open("/var/www/html/all/bin/python/log.txt", "a")
while s.check() == sat:
ind = ind +1
print ind
m = s.model()
print m
print "traversing model..."
#for d in m.decls():
#print "%s = %s" % (d.name(), m[d])
f.write(str(m))
f.write("nn")
exit()
#s.add(Or(goat[0] != s.model()[data[0]] )) # prevent next model from using the same assignment as a previous model
print "Total solution number: "
print ind
f.close()
Nom Start léist Z3Prover de Smart Kontrakt a liwwert eis eng Kette vun Transaktiounen, déi eis erlaabt Fongen zréckzéien:
Winning transaction chain found:
Data transaction: human= 0, wolf= 0, goat= 1, cabbage= 0
Data transaction: human= 1, wolf= 0, goat= 1, cabbage= 1
Data transaction: human= 0, wolf= 0, goat= 0, cabbage= 1
Data transaction: human= 1, wolf= 1, goat= 0, cabbage= 1
Data transaction: human= 0, wolf= 1, goat= 0, cabbage= 1
Data transaction: human= 1, wolf= 1, goat= 1, cabbage= 1
Data transaction: human= 1, wolf= 1, goat= 1, cabbage= 1
Transfer transaction
Nieft dem Fährkontrakt kënnt Dir mat Ären eegene Kontrakter experimentéieren oder dëst einfacht Beispill probéieren, dat an 2 Transaktiounen geléist gëtt.
let contract = tx.sender
let a= extract(getInteger(contract,"a"))
let b= extract(getInteger(contract,"b"))
let c= extract(getInteger(contract,"c"))
let d= extract(getInteger(contract,"d"))
match tx {
case t:DataTransaction =>
let na= extract(getInteger(t.data,"a"))
let nb= extract(getInteger(t.data,"b"))
let nc= extract(getInteger(t.data,"c"))
let nd= extract(getInteger(t.data,"d"))
nd == 0 || a == 100 - 5
case s:TransferTransaction =>
( a + b - c ) * d == 12
case _ => true
}
Well dëst déi alleréischt Versioun ass, ass d'Syntax ganz limitéiert an et kënne Bugs ginn.
An den folgenden Artikelen plangen ech d'Weiderentwécklung vum VM ze decken, a weisen wéi Dir formell verifizéiert Smart Kontrakter mat senger Hëllef erstellt, an net nëmmen se léisen.
D'Charakter virtuell Maschinn ass verfügbar bei
Nodeems ech de Quellcode vum symbolesche VM an Uerdnung gesat hunn a Kommentarer do bäigefüügt hunn, plangen ech et op GitHub fir gratis Zougang.
Source: will.com