Simbolično testiranje s Halmosom: izkoriščanje obstoječih testov za formalno preverjanje

Formalno preverjanje - postopek uporabe matematičnih metod za "pregled" programa ali pametne pogodbe v poljubnem številu vnosov - na splošno velja za bolj jedrnato, bolj celovito alternativo tradicionalnemu testiranju za pisanje kakovostnejše in varnejše kode. Toda v resnici je formalno preverjanje odprt in interaktiven proces. Podobno kot pri testiranju enot morajo razvijalci dinamično definirati formalne specifikacije in jih vnašati v sloje ter ponavljati svoj pristop, ko se njihova koda in analize razvijajo. Poleg tega je uradno preverjanje učinkovito le toliko, kolikor so učinkovite njegove specifikacije, katerih pisanje je lahko dolgotrajno (in pogosto vključuje strmo krivuljo učenja). 

Za mnoge razvijalce, ki se jim zdi proces zastrašujoč, so testi enot pogosto stroškovno učinkovitejša in časovno učinkovitejša pot za preverjanje pravilnosti programa. V praksi formalno preverjanje ni celovitejša alternativa testiranju enote, ampak dopolnilna. Ti procesi imajo različne prednosti in omejitve, ki zagotavljajo še večje zagotovilo, če se uporabljajo skupaj. Razvijalci bodo vedno morali pisati teste enot - kaj pa, če bi lahko uporabili iste lastnosti za formalno preverjanje?

Halmoš, naše odprtokodno formalno orodje za preverjanje, omogoča razvijalcem, da ponovna enake lastnosti, zapisane za teste enot za formalne specifikacije s pomočjo simboličnega testiranja. Namesto da bi morali od začetka ustvariti robusten nabor lastnosti, se lahko razvijalci izognejo podvajanju dela in izboljšajo svoje teste po nekaj specifikacij naenkrat, ne da bi začeli iz nič. To orodje smo zasnovali za uporabo, skupaj z drugimi v formalnem postopku preverjanja, kot na rampi za formalno preverjanje; razvijalci lahko začnejo z nekaj analizami z minimalnim naporom, preden dodajo več kasneje v procesu.

V tem prispevku pokrivamo izzive formalnega preverjanja in možnosti za premostitev vrzeli med testiranjem enote in formalnim preverjanjem s simboličnim testiranjem. Nato se sprehodimo skozi predstavitev Halmosa z uporabo obstoječe kode pametne pogodbe in si na hitro ogledamo druga formalna orodja za preverjanje (številna odprtokodna), ki so na voljo razvijalcem.

Formalno preverjanje proti testiranju

Uradno preverjanje — ki ga razvijalci blockchaina na splošno favorizirajo zaradi svoje strogosti in celovitosti — je postopek dokazovanja pravilnosti programa s preverjanjem, ali izpolnjuje določene lastnosti pravilnosti. Lastnosti, ki so specifične za program, so običajno podane zunaj in izražene z uporabo formalnega jezika ali zapisa, ki ga podpira uporabljeno orodje za preverjanje. Razvijalci pogosto dojemajo formalno preverjanje kot rešitev s pritiskom na gumb za samodejno testiranje lastnosti v vseh možnih scenarijih, v resnici pa je formalno preverjanje lahko delovno intenziven in zelo interaktiven proces.

Tako kot formalno preverjanje tudi testiranje enot vključuje ocenjevanje, ali program deluje po pričakovanjih; testiranje pa samo preverja obnašanje programa za nekaj vložkov, medtem ko ga lahko formalno preverjanje preveri vse možni vložki. Tako testiranje kot formalno preverjanje zahtevata opis pričakovanega obnašanja programa (s testnimi primeri, uporabljenimi pri testiranju, in formalnimi specifikacijami, uporabljenimi pri formalnem preverjanju). Če pa se uporabljata skupaj, lahko zagotovita temeljitejši pregled programa. Testiranje je na primer učinkovito pri iskanju enostavnih hroščev in napak, vendar je na splošno hitrejše in lažje za izvedbo. Formalno preverjanje, čeprav je bolj okorno za uporabo, je dovolj zmogljivo, da dokaže odsotnost napak ali razkrije subtilne napake, ki jih je zlahka spregledati pri testiranju ali pregledu kode.

Stroški specifikacije

Eden glavnih izzivov formalnega preverjanja so stroški pisanja in vzdrževanja formalnih specifikacij. Ta postopek pogosto vključuje dolgotrajno nalogo ročnega pisanja specifikacij z uporabo specializiranega jezika (ki se ga bodo morali mnogi razvijalci najprej naučiti). Postopek je tudi postopen, običajno se začne s pisanjem preprostih lastnosti in njihovim prvim preverjanjem, nato pa postopoma dodaja bolj zapletene lastnosti. Tako kot preizkušanje je tudi to odprt proces brez jasne končne točke in v razpoložljivem časovnem okviru je mogoče dodati čim več lastnosti. Poleg tega morajo razvijalci, ko spremenijo kodo med preverjanjem, tudi posodobiti svoje obstoječe specifikacije, kar vodi do dodatnih naporov pri vzdrževanju. Zaradi teh dejavnikov lahko formalno preverjanje postane zastrašujoča naloga za nekatere razvijalce, ki se ne želijo zavezati dodatnim režijskim stroškom.

In čeprav lahko testiranje in formalno preverjanje izboljšata kakovost kode, če se uporabljata skupaj, oba zahtevata (včasih podobne) opise pričakovanega vedenja programa v različnih jezikih in formatih. Pisanje in vzdrževanje teh opisov je delovno intenzivno, vzdrževanje dveh različnih oblik istega opisa pa se lahko zdi kot podvojen trud. To sproža naslednje vprašanje: Ali je mogoče opisati pričakovano vedenje na način, ki ga lahko razvijalci uporabijo za testiranje in preverjanje?

Premostitev vrzeli med testiranjem in formalnim preverjanjem s simboličnim testiranjem in Halmosom

Simbolično testiranje, praksa izvajanja testov s simbolnimi vhodi, je učinkovita formalna metoda preverjanja, ki zmanjša stroške specifikacij. Ta pristop omogoča uporabo istih testnih primerov za testiranje in formalno preverjanje. Za razliko od tradicionalnega testiranja, ki preverja, ali program deluje pravilno za omejen nabor vnosov, simbolno testiranje preverja program za vse možne vhode, zato se program, ki prestane simbolično testiranje, lahko šteje za formalno preverjenega.

Halmos je formalno orodje za preverjanje, zasnovano za simbolično testiranje. Namesto da bi zahteval ločene specifikacije ali učenje novega jezika, Halmos uporablja obstoječe teste kot formalne specifikacije. Izvajanje testov prek Halmosa bo samodejno preverilo, ali so uspešni za vse možne vnose, ali zagotovilo nasprotne primere. To ne le odpravlja potrebo po dodatnem pisanju specifikacij, ampak omogoča tudi ponovno uporabo testov, napisanih za testiranje enot ali fuzzing, za namene formalnega preverjanja.

Razvijalci imajo tako večjo prilagodljivost pri izbiri med številnimi možnostmi zagotavljanja kakovosti, vključno s testiranjem enot, fuzzingom in formalnim preverjanjem, odvisno od njihovih trenutnih potreb. Testi lahko na primer hitro odkrijejo preproste napake, po možnosti s pomočjo fuzzerja, ki generira naključne vnose, nato pa lahko Halmos dodatno poveča zaupanje v pravilnost programa pri vseh vhodih.

Primer: testiranje isPowerOfTwo() funkcija

Kot primer razmislite o naslednjem isPowerOfTwo() funkcijo, ki določa, ali je dano število potenca dvojke. Ta funkcija uporablja a algoritem bitne manipulacije za učinkovitost, vendar je lahko težko dokazati njegovo pravilnost, zlasti v primeru, ko vhod ni potenca dvojke.

Predstavljajte si naslednji test za isPowerOfTwo() funkcija: primerja dejanski izhod funkcije s pričakovanim izhodom za dani vhod. To je parametriran test (znan tudi kot test na podlagi lastnosti), kar pomeni, da ga lahko preprosto zaženete z različnimi vhodnimi vrednostmi, po možnosti z orodji za mehkanje, kot je Foundry.

S tem testom lahko preverite isPowerOfTwo() funkcijo prek testiranja enote ali fuzz testiranja, ki ga izvajate z izbiro vhodov. Takšni testi ne morejo formalno dokazati pravilnosti funkcije, saj je računsko neizvedljivo zagnati test za vse možne vnose.

Halmos pa razvijalcem dovoljuje, da ponovno uporabijo te že obstoječe teste za formalno preverjanje z le malo dodatnega truda. Orodje preveri, ali so testi uspešni za vse možne vnose, tako da izvede simbolično izvedbo testa in nato preveri, da trditev ni nikoli kršena (ali, če trditev is kršil, z navedbo protiprimera). To pomeni, da če je test uspešen Halmos, je pravilnost funkcije formalno preverjena, kar pomeni, da je algoritem pravilno implementiran in da ga je prevajalnik natančno prevedel v bajtno kodo.

Omejitev: Omejena simbolična izvedba

Na splošno ni mogoče izvesti popolnoma samodejnega, popolnega simboličnega testiranja, saj bi to zahtevalo rešitev problem zaustavljanja, za katerega se ve, da je ni mogoče določiti. Eden od razlogov za to je, da je pogosto nemogoče samodejno določiti, kolikokrat naj se zanka simbolično ponovi. Posledično je popolnoma samodejno formalno preverjanje na splošno neodločljivo.

Glede na te temeljne omejitve daje Halmos prednost avtomatizaciji pred popolnostjo. V ta namen je Halmos zasnovan za izvajanje omejenega simbolnega razmišljanja za neomejene zanke (kjer je število ponovitev odvisno od programskih vnosov) ali nizov spremenljive dolžine (vključno z nizi). To žrtvuje nekaj popolnosti, vendar omogoča Halmosu, da se izogne ​​zahtevi, da uporabnik zagotovi dodatne opombe, kot so invariante zanke.

Na primer, upoštevajte naslednjo iterativno različico isPowerOfTwo() funkcija, ki ima neomejeno zanko while, kjer je število ponovitev zanke določeno z najmanjšim številom bitov, potrebnih za predstavitev vhodnega števila.

Halmos simbolično ponovi to neomejeno zanko le do določene meje. Na primer, če je meja nastavljena na 3, bo Halmos zanko ponovil največ 3-krat in ne bo upošteval vhodnih vrednosti, ki bi povzročile več kot 3-kratno ponovitev zanke (tj. vse vrednosti, večje ali enake 2^3 ). V tem posebnem primeru bi nastavitev meje na 256 ali več omogočila, da je Halmos popoln.

Predstavitev: Formalno preverjanje ERC721A s Halmosom

Da bi prikazali zmogljivosti Halmosa, smo ga uporabili za simbolično testiranje in formalno preverjanje ERC721A, zelo plinsko optimizirana izvedba standarda ERC721, ki omogoča serijsko kovanje po skoraj enaki ceni kot enojno kovanje. ERC721A vključuje več inovativnih optimizacije doseči to učinkovitost; na primer, plin je mogoče prihraniti z odložitvijo posodobitev podatkov o lastništvu žetona, dokler se žeton ne prenese, ne v času kovanja. To zahteva uporabo kompleksnih podatkovnih struktur in algoritmov za učinkovito pridobivanje informacij o lastništvu iz lene podatkovne strukture. In čeprav ta optimizacija izboljša učinkovitost plina, poveča tudi kompleksnost kode in oteži dokazovanje pravilnosti izvedbe. Zaradi tega je ERC721A dober kandidat za formalno preverjanje, saj lahko poveča zaupanje v implementacijo in koristi potencialnim uporabnikom.

Simbolne lastnosti testiranja

Ker so bili obstoječi testi za ERC721A napisani v JavaScriptu s Hardhatom (ki ga Halmos trenutno ne podpira), smo v Solidity napisali nove teste za glavne funkcije vstopne točke: mint(), burn()in transfer(). Ti testi so preverili, ali vsaka funkcija pravilno posodablja lastništvo in stanje žetonov ter vpliva samo na ustrezne uporabnike, ne da bi spremenila stanje ali lastništvo drugih uporabnikov. Slednjega ni trivialno dokazati zaradi uporabe algoritma lene podatkovne strukture v ERC721A. Naslednji test na primer preveri, ali je transfer() funkcija pravilno posodobi lastništvo navedenega žetona:

Drugi test preverja, ali je transfer() funkcija ne spremeni ravnotežja za druge naslove, kar je težko dokazati, kot je bilo omenjeno prej:

Rezultati preverjanja

Izvedli smo poskus preverjanja s Halmosom na pametni pogodbi ERC721A, tako da smo zapisali skupno 19 testi. Preizkusi so bili izvedeni prek Halmosa z mejo odvijanja zanke 3, kar je trajalo 16 minut. Razčlenitev časa preverjanja je razvidna iz spodnje tabele. Poskus je bil izveden na MacBook Pro s čipom M1 Pro in 16 GB pomnilnika.

Test	Časi
testBurnBalanceUpdate	6.67
testBurnNextTokenIdUnchenged	1.40
testBurnOtherBalancePreservation	5.69
testBurnOtherOwnershipPreservation	189.70
testBurnOwnershipUpdate	3.81
testBurnRequirements	71.95
testMintBalanceUpdate	0.20
testMintNextTokenIdUpdate	0.18
testMintOtherBalancePreservation	0.26
testMintOtherOwnershipPreservation	5.74
testMintOwnershipUpdate	1.38
testMintRequirements	0.09
testTransferBalanceNespremenjeno	9.03
testTransferBalanceUpdate	53.53
testTransferNextTokenIdUnchenged	4.47
testTransferOtherBalancePreservation	19.57
testTransferOtherOwnershipPreservation	430.61
testTransferOwnershipUpdate	18.71
testTransferRequirements	149.18

Medtem ko je bila večina testov opravljenih v nekaj sekundah, je nekaj trajalo več minut. Te zamudne teste je bilo težko preveriti zaradi zapletene narave primerov, ki jih je bilo treba obravnavati, in so bili tesno povezani s pravilnostjo algoritma lene strukture podatkov.

Na splošno rezultati tega poskusa kažejo, da je Halmos sposoben učinkovito preveriti pravilnost kode pametne pogodbe. Zagotavlja povečano zaupanje v celovitost kode, kljub zapletenosti in potencialnim robnim primerom pametne pogodbe.

Eksperimentirajte z vbrizganimi hrošči

Da bi dokazali učinkovitost Halmosovega omejenega razmišljanja, smo ga uporabili za odkrivanje napak v prejšnji različici pogodbe ERC721A. Ta različica je imela težavo, ki je napačno obravnavala aritmetični preliv in potencialno omogočala paketno kovanje velikega števila žetonov, kar bi lahko zlomilo celovitost lene strukture podatkov in povzročilo, da bi nekateri uporabniki izgubili lastništvo žetonov (težava rešiti v trenutni različici). Enak niz 19 testov smo izvedli za ERC721A na različici s hrošči in Halmosu je uspelo najti protiprimer za lastnosti mint() funkcijo. Natančneje, Halmos je zagotovil vhodne vrednosti, ki so vodile do zgoraj opisanega scenarija izkoriščanja. Rezultati tega eksperimenta kažejo, da je lahko Halmosovo omejeno sklepanje kljub svoji nepopolnosti učinkovit način za odkrivanje in preprečevanje izkoriščenih hroščev v pametnih pogodbah.

Povezano delo

Formalna orodja za preverjanje bajtne kode pametne pogodbe Ethereum so razvile različne skupine. Ta orodja, vključno s Halmosom, se lahko uporabljajo za pomoč pri zagotavljanju varnosti in pravilnosti pametnih pogodb. Primerjava in razumevanje različnih funkcij, zmožnosti in omejitev teh orodij lahko razvijalcem pomagata izbrati najprimernejšega za svoje posebne potrebe.

Čeprav je Halmos dragocen dodatek k naboru orodij, ki so na voljo za preverjanje pametnih pogodb, naj bi dopolnjeval (ne nadomestil) obstoječa orodja. Razvijalci lahko kombinirajo Halmos z drugimi orodji, da dosežejo višjo raven zagotovila v svojih pogodbah. Spodaj primerjamo Halmos z nekaj izbranimi formalnimi orodji, ki podpirajo bajtno kodo EVM.

• K je zmogljivo formalno ogrodje za preverjanje, ki omogoča deduktivno preverjanje in interaktivno dokazovanje izrekov. Njegova osnovna teorija in izvedba zagotavljata visoko stopnjo izraznosti, zaradi česar je primeren za preverjanje kompleksnih programov in algoritmov. Vendar je treba opozoriti, da K ni zasnovan z močnim poudarkom na avtomatiziranem preverjanju in nima določenih funkcij avtomatizacije, ki lahko zahtevajo več ročnega truda med postopkom preverjanja. Za uporabo ogrodja K so formalne specifikacije napisane v jeziku K, ki se ga je treba naučiti pred uporabo. Njegova moč je še posebej uporabna pri preverjanju zapletenih sistemov, ki jih je lahko težko analizirati z avtomatiziranim razmišljanjem.
• Certora je formalno orodje za preverjanje pametnih pogodb, ki se osredotoča na avtomatizirano preverjanje in podpira preverjanje omejenega modela, podobno kot Halmos. Za uporabo Certora se morajo razvijalci naučiti njihovega novega jezika, CVL, da bi napisali specifikacije. Ta jezik omogoča jedrnat opis številnih kritičnih lastnosti prek pogodbenih invariant, funkcije, ki je Halmos trenutno ne podpira. Kljub temu, da je zaprtokodno lastniško orodje, Certora zagotavlja robustno formalno orodje za preverjanje s stalnim razvojem in dobro uporabniško podporo.
  
  Halmos je po drugi strani odprtokodno orodje, ki je manjšega obsega in trenutno nima nekaterih funkcij, ki jih ponuja Certora, vendar naj bi služilo kot javno dobro in je mišljeno kot nišna rešitev za hitro preverjanje pametnih pogodb brez potrebo po obsežni nastavitvi in ​​vzdrževanju.
• HEVM je še eno formalno orodje za preverjanje, ki je podobno Halmosu. Prej je bil del DappTools, ki je predhodnik Foundry. Tako HEVM kot Halmos imata to funkcijo, da ne zahtevata ločene specifikacije in lahko simbolično izvajata obstoječe teste za odkrivanje kršitev trditev. To uporabnikom omogoča, da obe orodji uporabljajo izmenično ali ju izvajajo vzporedno za iste teste, kar jim zagotavlja več možnosti za simbolično testiranje.
  
  Omeniti velja, da sta bila HEVM in Halmos kljub podobnosti razvita neodvisno in se razlikujeta v podrobnostih izvedbe; zlasti v smislu optimizacij in strategij simbolnega sklepanja. Poleg tega je HEVM napisan v Haskellu, medtem ko je Halmos napisan v Pythonu, kar zagotavlja izpostavljenost bogatemu ekosistemu Python. Možnost uporabe obeh orodij daje uporabnikom večjo prilagodljivost in možnosti za zagotavljanje varnosti in pravilnosti pametnih pogodb.

Halmoš je odprtokoden in je trenutno v beta fazi. Aktivno delamo na novih lastnosti in funkcionalnost, vključno s kodami za goljufanje Foundry in številnimi drugimi ključnimi funkcijami uporabnosti. Zelo bomo cenili vaše misli o tem, katere funkcije so najpomembnejše, in veseli bomo vseh povratnih informacij, predlogov in prispevkov, da bo Halmos boljše orodje za vse.

**

Tukaj izražena stališča so stališča posameznega citiranega osebja družbe AH Capital Management, LLC (»a16z«) in niso stališča družbe a16z ali njenih podružnic. Nekatere informacije, vsebovane tukaj, so bile pridobljene iz virov tretjih oseb, vključno s portfeljskimi družbami skladov, ki jih upravlja a16z. Čeprav so vzeti iz virov, za katere menijo, da so zanesljivi, a16z ni neodvisno preveril takšnih informacij in ne daje nobenih zagotovil o trenutni ali trajni točnosti informacij ali njihovi ustreznosti za dano situacijo. Poleg tega lahko ta vsebina vključuje oglase tretjih oseb; a16z ni pregledal takšnih oglasov in ne podpira nobene oglaševalske vsebine v njih.

Ta vsebina je na voljo samo v informativne namene in se je ne smete zanašati kot pravni, poslovni, naložbeni ali davčni nasvet. Glede teh zadev se morate posvetovati s svojimi svetovalci. Sklici na katere koli vrednostne papirje ali digitalna sredstva so samo v ilustrativne namene in ne predstavljajo naložbenega priporočila ali ponudbe za zagotavljanje investicijskih svetovalnih storitev. Poleg tega ta vsebina ni namenjena nobenim vlagateljem ali bodočim vlagateljem niti ji ni namenjena in se nanjo v nobenem primeru ne smete zanašati, ko se odločate za vlaganje v kateri koli sklad, ki ga upravlja a16z. (Ponudba za vlaganje v sklad a16z bo podana le z memorandumom o zasebni plasiranju, pogodbo o vpisu in drugo ustrezno dokumentacijo katerega koli takega sklada in jo je treba prebrati v celoti.) Vse naložbe ali portfeljske družbe, omenjene, navedene ali opisane niso reprezentativne za vse naložbe v vozila, ki jih upravlja a16z, in ni nobenega zagotovila, da bodo naložbe donosne ali da bodo imele druge naložbe v prihodnosti podobne značilnosti ali rezultate. Seznam naložb skladov, ki jih upravlja Andreessen Horowitz (razen naložb, za katere izdajatelj ni dal dovoljenja a16z za javno razkritje, ter nenapovedanih naložb v digitalna sredstva, s katerimi se javno trguje), je na voljo na https://a16z.com/investments /.

Grafi in grafi, ki so navedeni znotraj, so izključno informativne narave in se nanje ne bi smeli zanašati pri sprejemanju kakršnih koli investicijskih odločitev. Pretekla uspešnost ni pokazatelj prihodnjih rezultatov. Vsebina govori samo od navedenega datuma. Vse projekcije, ocene, napovedi, cilji, obeti in/ali mnenja, izražena v tem gradivu, se lahko spremenijo brez predhodnega obvestila in se lahko razlikujejo ali so v nasprotju z mnenji, ki so jih izrazili drugi. Za dodatne pomembne informacije obiščite https://a16z.com/disclosures.