Symbolsk test med Halmos: Udnyttelse af eksisterende tests til formel verifikation

Formel verifikation - processen med at bruge matematiske metoder til at "inspicere" et program eller smart kontrakt på tværs af et vilkårligt antal input - ses generelt som det mere kortfattede, mere omfattende alternativ til traditionel test for at skrive højere kvalitet og mere sikker kode. Men i virkeligheden er formel verifikation en åben og interaktiv proces. Ligesom enhedstestning skal udviklere dynamisk definere og lægge på formelle specifikationer og gentage deres tilgang, efterhånden som deres kode og analyser udvikler sig. Yderligere er formel verifikation kun så effektiv som dens specifikationer, hvilket kan være tidskrævende at skrive (og ofte kommer med en stejl indlæringskurve). 

For mange udviklere, der finder processen skræmmende, er enhedstests ofte den mere omkostningseffektive og tidseffektive vej til at finde ud af, om et program er korrekt. I praksis er formel verifikation ikke et mere omfattende alternativ til enhedstest, men et komplementært alternativ. Disse processer har forskellige styrker og begrænsninger, hvilket giver endnu større sikkerhed, når de bruges sammen. Udviklere skal altid skrive enhedstests - så hvad nu hvis vi kunne bruge de samme egenskaber til formel verifikation?

Halmos, vores open source formelle verifikationsværktøj, giver udviklere mulighed for genbruge de samme egenskaber skrevet til enhedstest til formelle specifikationer gennem symbolsk test. I stedet for at skulle oprette et robust sæt egenskaber fra starten, kan udviklere undgå dobbeltarbejde og forbedre deres test et par specifikationer ad gangen uden at starte fra bunden. Vi har designet dette værktøj til brug sammen med andre i den formelle verifikationsproces, som en påkørsel til formel verifikation; udviklere kan starte med et par analyser med minimal indsats, før de tilføjer flere senere i processen.

I dette indlæg dækker vi udfordringerne ved formel verifikation og potentialet til at bygge bro mellem enhedstestning og formel verifikation med symbolsk test. Vi gennemgår derefter en demo af Halmos ved hjælp af eksisterende smart kontraktkode og tager et hurtigt kig på andre formelle verifikationsværktøjer (mange open source) tilgængelige for udviklere.

Formel verifikation vs test

Formel verifikation - generelt begunstiget af blockchain-udviklere for dets stringens og omfattendehed - er processen med at bevise rigtigheden af ​​et program ved at verificere, at det opfylder visse korrekthedsegenskaber. Egenskaberne, som er specifikke for programmet, leveres normalt eksternt og udtrykt ved hjælp af et formelt sprog eller notation, der understøttes af det verifikationsværktøj, der bruges. Udviklere opfatter ofte formel verifikation som en trykknapløsning til automatisk at teste egenskaber på tværs af alle mulige scenarier, men i virkeligheden kan formel verifikation være en arbejdskrævende og meget interaktiv proces.

Ligesom formel verifikation involverer enhedstestning at evaluere, om et program fungerer som forventet; test tjekker dog kun programmets adfærd for nogle input, mens formel verifikation kan tjekke det for alle mulige input. Både test og formel verifikation kræver en beskrivelse af programmets forventede opførsel (med testcases brugt i test og formelle specifikationer brugt til formel verifikation). Men når de bruges sammen, kan de give en mere grundig undersøgelse af et program. Test er for eksempel effektivt til at finde simple fejl og fejl, men er generelt hurtigere og nemmere at udføre. Formel verifikation, selvom den er mere besværlig at bruge, er kraftfuld nok til at bevise fraværet af fejl eller afsløre subtile fejl, der er nemme at gå glip af i test eller kodegennemgange.

Specifikation overhead

En af hovedudfordringerne ved formel verifikation er omkostningerne ved at skrive og vedligeholde formelle specifikationer. Denne proces involverer ofte den tidskrævende opgave at manuelt skrive specifikationerne ved hjælp af et specialiseret sprog (som mange udviklere skal lære først). Processen er også trinvis og starter typisk med at skrive simple egenskaber og verificere dem først og derefter gradvist tilføje mere komplekse egenskaber oveni. Ligesom test er det en åben proces, uden noget klart stoppunkt, og man kan kun tilføje så mange egenskaber som muligt inden for den tilgængelige tidsramme. Derudover, når udviklere ændrer koden, mens den bliver verificeret, skal de også opdatere deres eksisterende specifikationer, hvilket fører til ekstra vedligeholdelsesindsats. Disse faktorer kan gøre formel verifikation til en skræmmende opgave for nogle udviklere, der tøver med at forpligte sig til de ekstra omkostninger.

Og selvom test og formel verifikation kan forbedre kodekvaliteten, når de bruges sammen, kræver begge (nogle gange lignende) beskrivelser af et programs forventede adfærd på forskellige sprog og formater. At skrive og vedligeholde disse beskrivelser er arbejdskrævende, og det kan føles som dobbeltarbejde at vedligeholde to forskellige former for samme beskrivelse. Dette rejser følgende spørgsmål: Er det muligt at beskrive den forventede adfærd på en måde, som udviklere kan bruge til både test og verifikation?

Slå bro mellem test og formel verifikation med symbolsk test og Halmos

Symbolsk test, praksis med at køre test med symbolske input, er en effektiv formel verifikationsmetode, der reducerer specifikationsoverhead. Denne tilgang gør det muligt at bruge de samme testcases til både test og formel verifikation. I modsætning til traditionel test, som verificerer, at et program fungerer korrekt for et begrænset sæt af input, kontrollerer symbolsk test programmet for alle mulige input, hvorfor et program, der består symbolsk test, kan betragtes som formelt verificeret.

Halmos er et formelt verifikationsværktøj designet til symbolsk test. I stedet for at kræve separate specifikationer eller lære et nyt sprog, bruger Halmos eksisterende tests som formelle specifikationer. Kørsel af tests gennem Halmos vil automatisk bekræfte, at de består for alle mulige input, eller give modeksempler. Dette eliminerer ikke kun behovet for yderligere specifikationsskrivning, men giver også mulighed for genbrug af test skrevet til enhedstestning eller fuzzing til formelle verifikationsformål.

Udviklere har således større fleksibilitet til at vælge mellem en række kvalitetssikringsmuligheder, herunder enhedstest, fuzzing og formel verifikation, afhængigt af deres aktuelle behov. For eksempel kan tests hurtigt identificere simple fejl, muligvis ved hjælp af en fuzzer, der genererer tilfældige input, og så kan Halmos yderligere øge tilliden til programmets korrekthed på tværs af alle input.

Eksempel: Test af isPowerOfTwo() funktion

Som et eksempel kan du overveje følgende isPowerOfTwo() funktion, som bestemmer om et givet tal er en potens af to. Denne funktion bruger en bit manipulation algoritme for effektivitet, men det kan være udfordrende at bevise dets rigtighed, især i det tilfælde, hvor input ikke er en potens af to.

Forestil dig følgende test for isPowerOfTwo() funktion: den sammenligner det faktiske output af funktionen med det forventede output for en given input. Dette er en parameteriseret test (også kendt som en egenskabsbaseret test), hvilket betyder, at du nemt kan køre den med forskellige inputværdier, muligvis med fuzzing-værktøjer som Foundry.

Du kan bruge denne test til at undersøge isPowerOfTwo() funktion gennem enhedstest eller fuzz-test, og kører den med et udvalg af input. Test som disse kan ikke formelt bevise rigtigheden af ​​funktionen, da det er beregningsmæssigt umuligt at køre testen for alle mulige input.

Halmos giver imidlertid udviklere mulighed for at genbruge disse allerede eksisterende tests til formel verifikation med kun en lille ekstra indsats. Værktøjet kontrollerer, at testene består for alle mulige input ved at udføre symbolsk udførelse af testen og derefter verificere, at påstanden aldrig bliver overtrådt, (eller, hvis påstanden is krænketved at give et modeksempel). Dette betyder, at hvis testen består Halmos, bliver funktionen formelt verificeret, hvilket betyder, at algoritmen er korrekt implementeret og er blevet nøjagtigt oversat af compileren til bytekode.

Begrænsning: Afgrænset symbolsk udførelse

Det er generelt ikke muligt at udføre fuldautomatisk, fuldstændig symbolsk test, da dette ville kræve at løse problemet standsningsproblem, hvilket vides at være uafgøreligt. En grund til dette er, at det ofte er umuligt automatisk at bestemme, hvor mange gange en loop skal gentages symbolsk. Som følge heraf er fuldautomatisk formel verifikation generelt uafklaret.

I betragtning af disse grundlæggende begrænsninger prioriterer Halmos automatisering frem for fuldstændighed. Til dette formål er Halmos designet til at udføre afgrænset symbolsk ræsonnement for ubundne sløjfer (hvor antallet af iterationer afhænger af programinput) eller arrays med variabel længde (inklusive strenge). Dette ofrer en vis fuldstændighed, men gør det muligt for Halmos at undgå at kræve, at brugeren skal levere yderligere annoteringer såsom loop-invarianter.

Overvej for eksempel følgende iterative version af isPowerOfTwo() funktion, som har en ubegrænset while-løkke, hvor antallet af loop-iterationer bestemmes af det mindste antal bits, der kræves for at repræsentere inputtallet.

Halmos gentager symbolsk kun denne ubundne løkke op til en specificeret grænse. For eksempel, hvis grænsen er sat til 3, vil Halmos iterere løkken højst 3 gange og vil ikke overveje inputværdier, der ville få løkken til at iterere mere end 3 gange (dvs. alle værdier større end eller lig med 2^3 ). I dette særlige tilfælde vil en indstilling af grænsen til 256 eller højere gøre det muligt for Halmos at være komplet.

Demo: Formel verifikation af ERC721A med Halmos

For at demonstrere Halmos' muligheder brugte vi den til symbolsk at teste og formelt verificere ERC721A, en meget gasoptimeret implementering af ERC721-standarden, der giver mulighed for batchprægning til næsten samme pris som enkeltprægning. ERC721A omfatter flere innovative optimeringer at opnå denne effektivitet; for eksempel kan gas spares ved at forsinke opdateringer af token-ejerskabsdata, indtil tokenet er overført, ikke på tidspunktet for prægning. Dette kræver brug af komplekse datastrukturer og algoritmer for effektivt at hente ejerskabsoplysninger fra den dovne datastruktur. Og selvom denne optimering forbedrer gaseffektiviteten, øger den også kodekompleksiteten og gør det udfordrende at bevise implementeringens rigtighed. Dette gør ERC721A til en god kandidat til formel verifikation, da det kan øge tilliden til implementeringen og gavne potentielle brugere.

Symbolske testegenskaber

Da de eksisterende tests for ERC721A blev skrevet i JavaScript med Hardhat (som i øjeblikket ikke understøttes af Halmos), skrev vi nye test i Solidity til hovedindgangsfunktionerne: mint(), burn()og transfer(). Disse tests kontrollerede, at hver funktion korrekt opdaterer token-ejerskab og -balance og kun påvirker de relevante brugere uden at ændre balancen eller ejerskabet af andre brugere. Sidstnævnte er ikke-trivielt at bevise på grund af brugen af ​​den dovne datastrukturalgoritme i ERC721A. For eksempel kontrollerer følgende test, at transfer() funktion opdaterer ejerskabet af det angivne token korrekt:

En anden test kontrollerer, at transfer() funktion ændrer ikke balancen for andre adresser, hvilket er udfordrende at bevise som tidligere nævnt:

Bekræftelsesresultater

Vi udførte et verifikationseksperiment med Halmos på ERC721A smart kontrakten ved at skrive i alt 19-test. Testene blev kørt gennem Halmos med en løkkeudrulningsgrænse på 3, hvilket tog 16 minutter at gennemføre. Opdelingen af ​​verifikationstiden kan ses i tabellen nedenfor. Eksperimentet blev udført på en MacBook Pro med en M1 Pro-chip og 16 GB hukommelse.

Test	Tid (er)
testBurnBalanceUpdate	6.67
testBurnNextTokenIdUændret	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
testTransferBalanceUændret	9.03
testTransferBalanceUpdate	53.53
testTransferNextTokenIdUændret	4.47
testOverførselAndenBalanceBevarelse	19.57
testOverførselAndetEjerskabBevaring	430.61
testTransferOwnershipUpdate	18.71
testTransferkrav	149.18

Mens de fleste af testene blev gennemført på få sekunder, tog nogle få af dem flere minutter. Disse tidskrævende tests var udfordrende at verificere på grund af den komplekse karakter af de sager, der skulle overvejes, og var tæt forbundet med rigtigheden af ​​den dovne datastrukturalgoritme.

Samlet set indikerer resultaterne af dette eksperiment, at Halmos effektivt er i stand til at verificere rigtigheden af ​​smart kontraktkode. Det giver øget tillid til kodens integritet på trods af den smarte kontrakts kompleksitet og potentielle fordele.

Eksperimenter med injicerede bugs

For at demonstrere effektiviteten af ​​Halmos' afgrænsede ræsonnement brugte vi den til at opdage fejl i en tidligere version af ERC721A-kontrakten. Denne version havde et problem, der mishandlede aritmetisk overløb og potentielt muliggjorde batch-minting af et stort antal tokens, hvilket kunne bryde integriteten af ​​den dovne datastruktur og resultere i, at nogle brugere mistede deres token-ejerskab (et problem løst i den aktuelle version). Vi kørte det samme sæt af 19 tests for ERC721A på buggy-versionen, og Halmos var i stand til at finde et modeksempel for egenskaberne af mint() fungere. Specifikt leverede Halmos inputværdier, der førte til udnyttelsesscenariet beskrevet ovenfor. Resultaterne af dette eksperiment indikerer, at på trods af dets ufuldstændighed, kan Halmos' afgrænsede ræsonnement være en effektiv måde at opdage og forhindre udnyttelige fejl i smarte kontrakter.

Relateret arbejde

Formelle verifikationsværktøjer til Ethereum smart kontrakt bytecode er blevet udviklet af forskellige teams. Disse værktøjer, inklusive Halmos, kan bruges til at sikre sikkerheden og korrektheden af ​​smarte kontrakter. Sammenligning og forståelse af de forskellige funktioner, muligheder og begrænsninger af disse værktøjer kan hjælpe udviklere med at vælge den mest passende til deres unikke behov.

Mens Halmos er en værdifuld tilføjelse til det tilgængelige værktøjssæt til smart kontraktverifikation, er det beregnet til at supplere (ikke erstatte) eksisterende værktøjer. Udviklere kan kombinere Halmos med andre værktøjer for at opnå en højere grad af sikkerhed i deres kontrakter. Nedenfor sammenligner vi Halmos med nogle få udvalgte formelle værktøjer, der understøtter EVM bytecode.

• K er en kraftfuld formel verifikationsramme, der muliggør deduktiv verifikation og interaktiv teorembevis. Dens underliggende teori og implementering giver et højt niveau af udtryksevne, hvilket gør det velegnet til at verificere komplekse programmer og algoritmer. Det skal dog bemærkes, at K ikke er designet med stor vægt på automatiseret verifikation og mangler visse automatiseringsfunktioner, som kan kræve mere manuel indsats under verifikationsprocessen. For at bruge K-rammerne er formelle specifikationer skrevet på K-sproget, som skal læres inden brug. Dens styrke er især nyttig til at verificere komplekse systemer, som kan være udfordrende at analysere ved hjælp af automatiseret ræsonnement.
• Certora er et formelt verifikationsværktøj til smarte kontrakter, der fokuserer på automatiseret verifikation og understøtter afgrænset modelkontrol, svarende til Halmos. For at bruge Certora skal udviklere lære deres nye sprog, CVL, for at skrive specifikationer. Dette sprog giver mulighed for en kortfattet beskrivelse af mange kritiske egenskaber gennem kontraktinvarianter, en funktion, som Halmos i øjeblikket ikke understøtter. På trods af at det er et proprietært værktøj med lukket kilde, leverer Certora robust formelt verifikationsværktøj med løbende udvikling og god brugersupport.
  
  Halmos, på den anden side, er et open source-værktøj, der er mindre i skala og i øjeblikket mangler nogle funktioner leveret af Certora, men det er beregnet til at tjene som et offentligt gode og er tænkt som en nicheløsning til hurtigt at verificere smarte kontrakter uden behovet for omfattende opsætning og vedligeholdelse.
• HEVM er et andet formelt verifikationsværktøj, der ligner Halmos. Det var tidligere en del af DappTools, som er en forløber for Foundry. Både HEVM og Halmos har den funktion, at de ikke kræver en separat specifikation og kan symbolsk udføre eksisterende tests for at identificere påstandsovertrædelser. Dette giver brugerne mulighed for at bruge begge værktøjer i flæng eller køre dem parallelt til de samme tests, hvilket giver dem flere muligheder for symbolsk test.
  
  Det er værd at bemærke, at på trods af deres ligheder er HEVM og Halmos blevet udviklet uafhængigt og adskiller sig i deres implementeringsdetaljer; især med hensyn til optimeringer og symbolske ræsonnementstrategier. Derudover er HEVM skrevet i Haskell, mens Halmos er skrevet i Python, hvilket giver eksponering til det rige Python-økosystem. At have muligheden for at bruge begge værktøjer giver brugerne mere fleksibilitet og muligheder for at sikre sikkerheden og korrektheden af ​​smarte kontrakter.

Halmos er open source og i øjeblikket i sin betafase. Vi arbejder aktivt på nye funktioner og funktionalitet, inklusive Foundry-snydekoder og flere andre vigtige brugervenlighedsfunktioner. Vi ville sætte stor pris på dine tanker om, hvilke funktioner der er vigtigst, og vi glæder os over enhver feedback, forslag og bidrag for at gøre Halmos til et bedre værktøj for alle.

**

De synspunkter, der er udtrykt her, er dem fra det enkelte AH Capital Management, LLC ("a16z") personale, der er citeret, og er ikke synspunkter fra a16z eller dets tilknyttede selskaber. Visse oplysninger indeholdt heri er indhentet fra tredjepartskilder, herunder fra porteføljeselskaber af fonde forvaltet af a16z. Selvom det er taget fra kilder, der menes at være pålidelige, har a16z ikke uafhængigt verificeret sådanne oplysninger og fremsætter ingen repræsentationer om den aktuelle eller vedvarende nøjagtighed af oplysningerne eller dens passende for en given situation. Derudover kan dette indhold omfatte tredjepartsreklamer; a16z har ikke gennemgået sådanne annoncer og støtter ikke noget reklameindhold indeholdt deri.

Dette indhold er kun givet til informationsformål og bør ikke påberåbes som juridisk, forretningsmæssig, investerings- eller skatterådgivning. Du bør rådføre dig med dine egne rådgivere om disse spørgsmål. Henvisninger til værdipapirer eller digitale aktiver er kun til illustrationsformål og udgør ikke en investeringsanbefaling eller tilbud om at levere investeringsrådgivningstjenester. Ydermere er dette indhold ikke rettet mod eller beregnet til brug af nogen investorer eller potentielle investorer og kan under ingen omstændigheder stoles på, når der træffes en beslutning om at investere i en fond, der administreres af a16z. (Et tilbud om at investere i en a16z-fond vil kun blive givet af private placement-memorandummet, tegningsaftalen og anden relevant dokumentation for en sådan fond og bør læses i deres helhed.) Eventuelle investeringer eller porteføljeselskaber nævnt, refereret til eller beskrevne er ikke repræsentative for alle investeringer i køretøjer, der administreres af a16z, og der kan ikke gives sikkerhed for, at investeringerne vil være rentable, eller at andre investeringer foretaget i fremtiden vil have lignende karakteristika eller resultater. En liste over investeringer foretaget af fonde forvaltet af Andreessen Horowitz (undtagen investeringer, hvortil udstederen ikke har givet tilladelse til, at a16z offentliggør såvel som uanmeldte investeringer i offentligt handlede digitale aktiver) er tilgængelig på https://a16z.com/investments /.

Diagrammer og grafer, der er angivet i, er udelukkende til informationsformål og bør ikke stoles på, når der træffes nogen investeringsbeslutning. Tidligere resultater er ikke vejledende for fremtidige resultater. Indholdet taler kun fra den angivne dato. Alle fremskrivninger, estimater, prognoser, mål, udsigter og/eller meninger udtrykt i disse materialer kan ændres uden varsel og kan afvige fra eller være i modstrid med andres meninger. Se venligst https://a16z.com/disclosures for yderligere vigtige oplysninger.