Создавање формален систем за верификација од нула. Дел 1: Виртуелна машина со карактери во PHP и Python

Формална верификација е верификација на една програма или алгоритам користејќи друга.

Ова е еден од најмоќните методи кој ви овозможува да ги пронајдете сите пропусти во програмата или да докажете дека тие не постојат.

Подетален опис на формалната верификација може да се види во примерот за решавање на проблемот на Волк, коза и зелка во мојата претходна статија.

Во оваа статија се префрлам од формална проверка на проблемите на програми и опишувам како
како може автоматски да се претворат во системи за формални правила.

За да го направам ова, напишав свој аналог на виртуелна машина, користејќи симболични принципи.

Го анализира програмскиот код и го преведува во систем на равенки (SMT), кој веќе може да се реши програмски.

Бидејќи информациите за симболичните пресметки се претставени на Интернет прилично фрагментарно,
Накратко ќе опишам што е тоа.

Симболичкото пресметување е начин за истовремено извршување на програма на широк опсег на податоци и е главната алатка за формална верификација на програмата.

На пример, можеме да поставиме влезни услови каде што првиот аргумент може да има позитивни вредности, вториот негативен, третата нула и излезниот аргумент, на пример, 42.

Симболичните пресметки во едно возење ќе ни дадат одговор дали е можно да го добиеме посакуваниот резултат и пример за множество од такви влезни параметри. Или доказ дека нема такви параметри.

Покрај тоа, можеме да ги поставиме влезните аргументи на сите можни и да ги избереме само излезните, на пример, администраторската лозинка.

Во овој случај, ќе ги најдеме сите пропусти на програмата или ќе добиеме доказ дека лозинката на администраторот е безбедна.

Може да се забележи дека класичното извршување на програма со специфични влезни податоци е посебен случај на симболично извршување.

Затоа, мојот лик VM може да работи и во режим на емулација на стандардна виртуелна машина.

Во коментарите на претходната статија може да се најде фер критика на формалната верификација со дискусија за нејзините слабости.

Главните проблеми се:

1. Комбинаторна експлозија, бидејќи формалната верификација на крајот се сведува на P=NP
2. Потешко е да се потврди обработката на повиците до датотечен систем, мрежи и друга надворешна меморија
3. Грешки во спецификацијата, кога клиентот или програмерот имал намера една работа, но не ја опишал доволно точно во техничката спецификација.

Како резултат на тоа, програмата ќе биде потврдена и усогласена со спецификацијата, но ќе направи нешто сосема поинакво од она што креаторите го очекуваа од неа.

Бидејќи во оваа статија главно размислувам за употреба на формална верификација во пракса, засега нема да ја удрам главата од ѕид и ќе изберам систем каде што алгоритамската сложеност и бројот на надворешни повици се минимални.

Бидејќи паметните договори најдобро одговараат на овие барања, изборот падна на договорите RIDE од платформата Waves: тие не се завршени на Туринг и нивната максимална сложеност е вештачки ограничена.

Но, ние ќе ги разгледаме исклучиво од техничка страна.

Покрај сè, формалната верификација ќе биде особено барана за какви било договори: обично е невозможно да се поправи грешката на договорот откако ќе биде лансирана.
И цената на таквите грешки може да биде многу висока, бидејќи доста големи количини на средства често се складираат на паметни договори.

Мојата симболична виртуелна машина е напишана во PHP и Python и користи Z3Prover од Microsoft Research за да ги реши добиените SMT формули.

Во неговото јадро е моќното мулти-трансакциско пребарување, кое
ви овозможува да најдете решенија или пропусти, дури и ако тоа бара многу трансакции.
Дури и Митрил, една од најмоќните симболични рамки за пронаоѓање на ранливости на Ethereum, ја додаде оваа способност само пред неколку месеци.

Но, вреди да се напомене дека етерските договори се посложени, а Туринг е завршен.

PHP го преведува изворниот код на паметниот договор RIDE во скрипта за пајтон, во која програмата е претставена како Z3 SMT-компатибилен систем на договорни состојби и услови за нивни транзиции:

Сега ќе опишам што се случува внатре подетално.

Но, прво, неколку зборови за јазикот за паметни договори RIDE.

Тоа е функционален програмски јазик базиран на изразување кој е мрзлив по дизајн.
RIDE работи изолирано во рамките на блокчејнот и може да поврати и запише информации од складиштето поврзано со паричникот на корисникот.

Можете да прикачите договор за RIDE на секој паричник, а резултатот од извршувањето ќе биде само ТОЧНО или НЕТОЧНО.

ТОЧНО значи дека паметниот договор ја дозволува трансакцијата, а FALSE значи дека ја забранува.
Едноставен пример: скрипта може да забрани пренос ако салдото на паричникот е помало од 100.

Како пример, ќе ги земам истите Волк, Коза и Зелка, но веќе претставени во форма на паметен договор.

Корисникот нема да може да повлече пари од паричникот на кој е распореден договорот додека не ги испрати сите на другата страна.

#Извлекаем положение всех объектов из блокчейна
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 прво ги извлекува сите променливи од паметниот договор во форма на нивните клучеви и соодветната булова променлива за изразување.

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 потоа ги конвертира во системски опис компатибилен со Z3Prover SMT во Python.
Податоците се завиткани во јамка, каде што променливите за складирање добиваат индекс i, променливите на трансакцијата индекс i + 1, а променливите со изрази ги поставуваат правилата за премин од претходната состојба во следната.

Ова е самото срце на нашата виртуелна машина, која обезбедува мулти-трансакциски пребарувач.

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] )  

Условите се подредени и вметнати во шаблон за скрипта дизајниран да го опише SMT системот во Python.

Празен шаблон

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()
 

За последната состојба во целиот синџир, се применуваат правилата кои се наведени во делот за трансакција за пренос.

Ова значи дека Z3Prover ќе бара токму такви услови кои на крајот ќе овозможат повлекување на средствата од договорот.

Како резултат на тоа, ние автоматски добиваме целосно функционален SMT модел на нашиот договор.
Можете да видите дека е многу сличен на моделот од мојата претходна статија, која ја составив рачно.

Завршен шаблон

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()
 

По лансирањето, Z3Prover го решава паметниот договор и ни обезбедува синџир на трансакции што ќе ни овозможат да повлечеме средства:

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

Покрај договорот за траект, можете да експериментирате со вашите сопствени договори или да го пробате овој едноставен пример, кој се решава во 2 трансакции.

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

}

Бидејќи ова е првата верзија, синтаксата е многу ограничена и може да има грешки.
Во следните статии, планирам да го опфатам понатамошниот развој на VM и да покажам како можете да креирате формално потврдени паметни договори со негова помош, а не само да ги решавате.

Ликот на виртуелната машина е достапен на http://2.59.42.98/hyperbox/
Откако ќе го подредам изворниот код на симболичното VM и ќе додадам коментари таму, планирам да го објавам на GitHub за бесплатен пристап.

Извор: www.habr.com