Zephyrnet-logo

Symbolisch testen met Halmos: gebruikmaken van bestaande tests voor formele verificatie

Datum:

2 februari 2023 Daejun-park

Formele verificatie - het proces waarbij wiskundige methoden worden gebruikt om een โ€‹โ€‹programma of slim contract te "inspecteren" op een willekeurig aantal ingangen - wordt over het algemeen gezien als het beknoptere, uitgebreidere alternatief voor traditioneel testen voor het schrijven van veiligere code van hogere kwaliteit. Maar in werkelijkheid is formele verificatie een open en interactief proces. Net zoals het testen van eenheden, moeten ontwikkelaars op dynamische wijze formele specificaties definiรซren en in lagen aanbrengen, waarbij ze hun aanpak herhalen naarmate hun code en analyses evolueren. Verder is formele verificatie slechts zo effectief als de specificaties, die tijdrovend kunnen zijn om te schrijven (en vaak gepaard gaan met een steile leercurve). 

Voor veel ontwikkelaars die het proces ontmoedigend vinden, zijn unit-tests vaak de meer kosteneffectieve en tijdbesparende manier om de juistheid van een programma te onderzoeken. In de praktijk is formele verificatie geen uitgebreider alternatief voor unit testing, maar een aanvulling. Deze processen hebben verschillende sterktes en beperkingen, waardoor ze nog meer zekerheid bieden als ze samen worden gebruikt. Ontwikkelaars zullen altijd unit-tests moeten schrijven - dus wat als we dezelfde eigenschappen zouden kunnen gebruiken voor formele verificatie?

Halmos, onze open source formele verificatietool, stelt ontwikkelaars in staat om hergebruiken dezelfde eigenschappen die zijn geschreven voor eenheidstests voor formele specificaties door middel van symbolische tests. In plaats van vanaf het begin een robuuste set eigenschappen te moeten maken, kunnen ontwikkelaars dubbel werk vermijden en hun tests met enkele specificaties tegelijk verbeteren zonder helemaal opnieuw te beginnen. We hebben deze tool ontworpen voor gebruik, naast andere in het formele verificatieproces, als opstap naar formele verificatie; ontwikkelaars kunnen met minimale inspanning beginnen met een paar analyses, voordat ze later in het proces meer toevoegen.

In dit bericht behandelen we de uitdagingen van formele verificatie en het potentieel om de kloof tussen het testen van eenheden en formele verificatie te overbruggen met symbolisch testen. Vervolgens lopen we door een demo van Halmos met behulp van bestaande slimme contractcode en bekijken we snel andere formele verificatietools (veel open source) die beschikbaar zijn voor ontwikkelaars.

Formele verificatie versus testen

Formele verificatie - over het algemeen favoriet bij blockchain-ontwikkelaars vanwege zijn nauwgezetheid en volledigheid - is het proces van het bewijzen van de juistheid van een programma door te verifiรซren dat het voldoet aan bepaalde correctheidseigenschappen. De eigenschappen, die specifiek zijn voor het programma, worden meestal extern verstrekt en uitgedrukt in een formele taal of notatie die wordt ondersteund door de gebruikte verificatietool. Ontwikkelaars zien formele verificatie vaak als een drukknopoplossing voor het automatisch testen van eigenschappen in alle mogelijke scenario's, maar in werkelijkheid kan formele verificatie een arbeidsintensief en zeer interactief proces zijn.

Net als bij formele verificatie houdt het testen van eenheden in dat wordt beoordeeld of een programma werkt zoals verwacht; testen controleert echter alleen het gedrag van het programma op sommige input, terwijl formele verificatie het kan controleren allen mogelijke ingangen. Zowel testen als formele verificatie vereisen een beschrijving van het verwachte gedrag van het programma (met testgevallen die worden gebruikt bij testen en formele specificaties die worden gebruikt bij formele verificatie). Maar wanneer ze samen worden gebruikt, kunnen ze een grondiger onderzoek van een programma bieden. Testen is bijvoorbeeld effectief bij het vinden van eenvoudige bugs en fouten, maar is over het algemeen sneller en gemakkelijker uit te voeren. Formele verificatie, hoewel omslachtiger in gebruik, is krachtig genoeg om de afwezigheid van fouten te bewijzen of subtiele bugs aan het licht te brengen die gemakkelijk over het hoofd worden gezien bij testen of codebeoordelingen.

Specificatie overhead

Een van de belangrijkste uitdagingen van formele verificatie is de overhead van het schrijven en onderhouden van formele specificaties. Dit proces omvat vaak de tijdrovende taak van het handmatig schrijven van de specificaties met behulp van een gespecialiseerde taal (die veel ontwikkelaars eerst zullen moeten leren). Het proces is ook incrementeel, meestal beginnend met het schrijven van eenvoudige eigenschappen en deze eerst te verifiรซren, en vervolgens geleidelijk aan meer complexe eigenschappen toe te voegen. Net als testen is het een proces met een open einde, zonder duidelijk stoppunt, en men kan alleen zoveel mogelijk eigenschappen toevoegen binnen het beschikbare tijdsbestek. Bovendien, wanneer ontwikkelaars de code wijzigen terwijl deze wordt geverifieerd, moeten ze ook hun bestaande specificaties bijwerken, wat leidt tot extra onderhoudsinspanningen. Deze factoren kunnen formele verificatie tot een ontmoedigende taak maken voor sommige ontwikkelaars die aarzelen om zich vast te leggen op de extra overhead.

En hoewel testen en formele verificatie de codekwaliteit kunnen verbeteren wanneer ze samen worden gebruikt, vereisen beide (soms vergelijkbare) beschrijvingen van het verwachte gedrag van een programma in verschillende talen en formaten. Het schrijven en onderhouden van deze beschrijvingen is arbeidsintensief en het onderhouden van twee verschillende vormen van dezelfde beschrijving kan als dubbele inspanning aanvoelen. Dit roept de volgende vraag op: is het mogelijk om het verwachte gedrag te beschrijven op een manier die ontwikkelaars kunnen gebruiken voor zowel testen als verifiรซren?

Overbrug de kloof tussen testen en formele verificatie met symbolisch testen en Halmos

Symbolisch testen, de praktijk van het uitvoeren van tests met symbolische invoer, is een effectieve formele verificatiemethode die de specificatieoverhead vermindert. Deze aanpak maakt het gebruik van dezelfde testgevallen mogelijk voor zowel testen als formele verificatie. In tegenstelling tot traditioneel testen, dat verifieert dat een programma correct werkt voor een beperkte set inputs, controleert symbolisch testen het programma op alle mogelijke inputs, vandaar dat een programma dat symbolisch getest is, als formeel geverifieerd kan worden beschouwd.

Halmos is een formele verificatietool die is ontworpen voor symbolisch testen. In plaats van aparte specificaties te eisen of een nieuwe taal te leren, gebruikt Halmos bestaande tests als formele specificaties. Het uitvoeren van tests via Halmos zal automatisch verifiรซren dat ze slagen voor alle mogelijke ingangen, of tegenvoorbeelden geven. Dit elimineert niet alleen de noodzaak voor het schrijven van aanvullende specificaties, maar maakt ook het hergebruik mogelijk van tests die zijn geschreven voor het testen van eenheden of fuzzing, voor formele verificatiedoeleinden.

Ontwikkelaars hebben dus meer flexibiliteit om te kiezen uit een reeks kwaliteitsborgingsopties, waaronder unit testing, fuzzing en formele verificatie, afhankelijk van hun huidige behoeften. Tests kunnen bijvoorbeeld snel eenvoudige fouten identificeren, mogelijk met behulp van een fuzzer die willekeurige invoer genereert, en dan kan Halmos het vertrouwen in de juistheid van het programma voor alle invoer verder vergroten.

Voorbeeld: testen van de isPowerOfTwo() functie

Beschouw als voorbeeld het volgende isPowerOfTwo() functie, die bepaalt of een bepaald getal een macht van twee is. Deze functie gebruikt een bit-manipulatie-algoritme voor efficiรซntie, maar het kan een uitdaging zijn om de juistheid ervan te bewijzen, vooral in het geval dat de invoer geen macht van twee is.

Stel je de volgende test voor de isPowerOfTwo() functie: het vergelijkt de werkelijke uitvoer van de functie met de verwachte uitvoer voor een bepaalde invoer. Dit is een geparametriseerde test (ook bekend als een op eigenschappen gebaseerde test), wat betekent dat u deze gemakkelijk kunt uitvoeren met verschillende invoerwaarden, mogelijk met fuzzing-tools zoals Foundry.

U kunt deze test gebruiken om de isPowerOfTwo() functie door middel van unit-testen of fuzz-testen, waarbij het wordt uitgevoerd met een selectie van ingangen. Dergelijke tests kunnen de juistheid van de functie niet formeel bewijzen, aangezien het rekenkundig onhaalbaar is om de test voor elke mogelijke invoer uit te voeren.

Met Halmos kunnen ontwikkelaars deze reeds bestaande tests echter met slechts een kleine extra inspanning hergebruiken voor formele verificatie. De tool controleert of tests slagen voor alle mogelijke invoer door symbolische uitvoering van de test uit te voeren en vervolgens te verifiรซren dat de bewering nooit wordt geschonden (of, als de bewering is geschonden, door een tegenvoorbeeld te geven). Dit betekent dat als de test Halmos doorstaat, de juistheid van de functie formeel wordt geverifieerd, wat betekent dat het algoritme correct is geรฏmplementeerd en door de compiler nauwkeurig is vertaald in bytecode.

Beperking: begrensde symbolische uitvoering

Het is over het algemeen niet mogelijk om volledig automatische, volledige symbolische tests uit te voeren, omdat hiervoor het oplossen van het stopprobleem, dat is bekend onbeslist. Een reden hiervoor is dat het vaak onmogelijk is om automatisch te bepalen hoeveel keer een lus symbolisch moet worden herhaald. Als gevolg hiervan is volautomatische formele verificatie over het algemeen onbeslisbaar.

Gezien deze fundamentele beperkingen geeft Halmos prioriteit aan automatisering boven volledigheid. Daartoe is Halmos ontworpen om begrensde symbolische redeneringen uit te voeren voor onbegrensde lussen (waarbij het aantal iteraties afhangt van programma-invoer) of arrays met variabele lengte (inclusief strings). Dit offert enige volledigheid op, maar stelt Halmos in staat om te voorkomen dat de gebruiker aanvullende annotaties moet opgeven, zoals lusinvarianten.

Beschouw bijvoorbeeld de volgende iteratieve versie van het isPowerOfTwo() functie, die een onbeperkte while-lus bevat, waarbij het aantal lus-iteraties wordt bepaald door het minimale aantal bits dat nodig is om het invoernummer weer te geven.

Halmos herhaalt symbolisch deze onbegrensde lus slechts tot een gespecificeerde grens. Als de grens bijvoorbeeld is ingesteld op 3, herhaalt Halmos de lus maximaal 3 keer en houdt geen rekening met invoerwaarden die ervoor zorgen dat de lus meer dan 3 keer wordt herhaald (d.w.z. alle waarden groter dan of gelijk aan 2^3 ). In dit specifieke geval zou het instellen van de grens op 256 of hoger ervoor zorgen dat Halmos volledig is.

Demo: formele verificatie van ERC721A met Halmos

Om de mogelijkheden van Halmos te demonstreren, gebruikten we het om symbolisch te testen en formeel te verifiรซren ERC721A, een zeer gas-geoptimaliseerde implementatie van de ERC721-standaard die batch-munten mogelijk maakt tegen bijna dezelfde kosten als enkelvoudig slaan. ERC721A bevat verschillende innovatieve optimalisaties om deze efficiรซntie te bereiken; gas kan bijvoorbeeld worden bespaard door updates van de eigendomsgegevens van het token uit te stellen totdat het token is overgedragen, niet op het moment van slaan. Dit vereist het gebruik van complexe datastructuren en algoritmen om eigendomsinformatie efficiรซnt uit de luie datastructuur te halen. En hoewel deze optimalisatie de gasefficiรซntie verbetert, verhoogt het ook de complexiteit van de code en maakt het een uitdaging om de juistheid van de implementatie te bewijzen. Dit maakt ERC721A een goede kandidaat voor formele verificatie, omdat het het vertrouwen in de implementatie kan vergroten en ten goede kan komen aan potentiรซle gebruikers.

Symbolische testeigenschappen

Aangezien de bestaande tests voor ERC721A zijn geschreven in JavaScript met Hardhat (wat momenteel niet wordt ondersteund door Halmos), hebben we nieuwe tests in Solidity geschreven voor de belangrijkste ingangspuntfuncties: mint(), burn() en transfer(). Deze tests hebben gecontroleerd of elke functie het eigendom en de balans van het token correct bijwerkt en alleen de relevante gebruikers beรฏnvloedt zonder de balans of het eigendom van andere gebruikers te wijzigen. Dit laatste is niet triviaal om te bewijzen vanwege het gebruik van het lazy datastructuur-algoritme in ERC721A. De volgende test controleert bijvoorbeeld of de transfer() functie werkt het eigendom van het opgegeven token correct bij:

Een andere test controleert of de transfer() functie verandert de balans voor andere adressen niet, wat een uitdaging is om te bewijzen, zoals eerder vermeld:

Verificatie resultaten

We hebben een verificatie-experiment uitgevoerd met Halmos op het slimme contract ERC721A door in totaal te schrijven 19-tests. De tests werden uitgevoerd door Halmos met een lusafwikkelingsgrens van 3, wat 16 minuten in beslag nam. De uitsplitsing van de verificatietijd is te zien in onderstaande tabel. Het experiment is uitgevoerd op een MacBook Pro met een M1 Pro-chip en 16 GB geheugen.

test Keer)
testBurnBalanceUpdate 6.67
testBurnNextTokenIdOngewijzigd 1.40
testBurnAndersBalansBehoud 5.69
testBurnOwnershipPreservation 189.70
testBurnOwnershipUpdate 3.81
testBurn-vereisten 71.95
testMintBalanceUpdate 0.20
testMintNextTokenIdUpdate 0.18
testMintOtherBalanceBehoud 0.26
testMintOverigEigendomBehoud 5.74
testMintOwnershipUpdate 1.38
testMintVereisten 0.09
testTransferBalanceOngewijzigd 9.03
testTransferBalanceUpdate 53.53
testTransferNextTokenIdOngewijzigd 4.47
testOverdrachtAndersBalansBehoud 19.57
testTransferOthershipPreservation 430.61
testTransferOwnershipUpdate 18.71
testOverdrachtsvereisten 149.18

Hoewel de meeste tests binnen enkele seconden zijn voltooid, duurde een aantal enkele minuten. Deze tijdrovende tests waren een uitdaging om te verifiรซren vanwege de complexe aard van de gevallen die moesten worden overwogen, en hielden nauw verband met de juistheid van het luie datastructuur-algoritme.

Over het algemeen geven de resultaten van dit experiment aan dat Halmos in staat is om de juistheid van slimme contractcode effectief te verifiรซren. Het geeft meer vertrouwen in de integriteit van de code, ondanks de complexiteit en mogelijke randgevallen van het slimme contract.

Experimenteer met geรฏnjecteerde bugs

Om de effectiviteit van de begrensde redenering van Halmos aan te tonen, hebben we deze gebruikt om bugs op te sporen in een eerdere versie van het ERC721A-contract. Deze versie had een probleem dat rekenkundige overflow verkeerd behandelde en mogelijk een groot aantal tokens in batch kon slaan, wat de integriteit van de luie datastructuur zou kunnen breken en ertoe zou kunnen leiden dat sommige gebruikers hun tokeneigendom verliezen (een probleem opgelost in de huidige versie). We hebben dezelfde set van 19 tests uitgevoerd voor ERC721A op de buggy-versie en Halmos kon een tegenvoorbeeld vinden voor de eigenschappen van de mint() functie. Met name Halmos leverde invoerwaarden die leidden tot het hierboven beschreven exploitatiescenario. De resultaten van dit experiment geven aan dat, ondanks de onvolledigheid, de begrensde redenering van Halmos een effectieve manier kan zijn om exploiteerbare bugs in slimme contracten op te sporen en te voorkomen.

Gerelateerd werk

Formele verificatietools voor Ethereum smart contract bytecode zijn ontwikkeld door verschillende teams. Deze tools, waaronder Halmos, kunnen worden gebruikt om de veiligheid en correctheid van slimme contracten te helpen waarborgen. Door de verschillende functies, mogelijkheden en beperkingen van deze tools te vergelijken en te begrijpen, kunnen ontwikkelaars de meest geschikte tool kiezen voor hun unieke behoeften.

Hoewel Halmos een waardevolle aanvulling is op de toolset die beschikbaar is voor slimme contractverificatie, is het bedoeld als aanvulling op (niet als vervanging van) bestaande tools. Ontwikkelaars kunnen Halmos combineren met andere tools om een โ€‹โ€‹hoger niveau van zekerheid in hun contracten te bereiken. Hieronder vergelijken we Halmos met een paar geselecteerde formele tools die EVM bytecode ondersteunen.

  • K is een krachtig formeel verificatieraamwerk dat deductieve verificatie en interactief bewijs van stellingen mogelijk maakt. De onderliggende theorie en implementatie zorgen voor een hoge mate van expressiviteit, waardoor het geschikt is voor het verifiรซren van complexe programma's en algoritmen. Er moet echter worden opgemerkt dat K niet is ontworpen met grote nadruk op geautomatiseerde verificatie en bepaalde automatiseringsfuncties mist die tijdens het verificatieproces meer handmatige inspanning kunnen vergen. Om het K-raamwerk te gebruiken, worden formele specificaties geschreven in de K-taal, die vรณรณr gebruik moet worden geleerd. De kracht ervan is vooral handig bij het verifiรซren van complexe systemen, die een uitdaging kunnen zijn om te analyseren met behulp van geautomatiseerd redeneren.
  • Certora is een formele verificatietool voor slimme contracten die zich richt op geautomatiseerde verificatie en begrensde modelcontrole ondersteunt, vergelijkbaar met Halmos. Om Certora te gebruiken, moeten ontwikkelaars hun nieuwe taal leren, CVL, om specificaties te schrijven. Deze taal maakt de beknopte beschrijving mogelijk van veel kritieke eigenschappen door middel van contractinvarianten, een functie die Halmos momenteel niet ondersteunt. Ondanks dat het een closed-source, bedrijfseigen tool is, biedt Certora robuuste formele verificatietools, met voortdurende ontwikkeling en goede gebruikersondersteuning.

    Halmos, aan de andere kant, is een open-source tool die kleinschaliger is en momenteel enkele functies van Certora mist, maar het is bedoeld om te dienen als een openbaar goed en is bedoeld als een niche-oplossing voor het snel verifiรซren van slimme contracten zonder de behoefte aan uitgebreide installatie en onderhoud.
  • HEVM is een andere formele verificatietool die vergelijkbaar is met Halmos. Het was voorheen onderdeel van DappTools, een voorloper van Foundry. Zowel HEVM als Halmos hebben het kenmerk dat ze geen aparte specificatie vereisen en symbolisch bestaande tests kunnen uitvoeren om schendingen van beweringen te identificeren. Hierdoor kunnen gebruikers beide tools door elkaar gebruiken of parallel uitvoeren voor dezelfde tests, waardoor ze meerdere opties hebben voor symbolisch testen.

    Het is vermeldenswaard dat, ondanks hun overeenkomsten, HEVM en Halmos onafhankelijk zijn ontwikkeld en verschillen in hun implementatiedetails; met name in termen van optimalisaties en symbolische redeneerstrategieรซn. Bovendien is HEVM geschreven in Haskell, terwijl Halmos is geschreven in Python, wat zorgt voor blootstelling aan het rijke Python-ecosysteem. De mogelijkheid om beide tools te gebruiken, geeft gebruikers meer flexibiliteit en opties om de veiligheid en juistheid van slimme contracten te waarborgen.

Halmos is open source en bevindt zich momenteel in de bรจtafase. We werken actief aan nieuwe functionaliteiten en functionaliteit, inclusief Foundry-cheatcodes en verschillende andere belangrijke gebruiksfuncties. We stellen uw mening over welke functies het belangrijkst zijn zeer op prijs en verwelkomen alle feedback, suggesties en bijdragen om van Halmos een betere tool voor iedereen te maken.

**

De standpunten die hier naar voren worden gebracht, zijn die van het individuele personeel van AH Capital Management, LLC (โ€œa16zโ€) dat wordt geciteerd en zijn niet de standpunten van a16z of haar gelieerde ondernemingen. Bepaalde informatie in dit document is verkregen uit externe bronnen, waaronder van portefeuillebedrijven van fondsen die worden beheerd door a16z. Hoewel ontleend aan bronnen die betrouwbaar worden geacht, heeft a16z dergelijke informatie niet onafhankelijk geverifieerd en doet het geen uitspraken over de huidige of blijvende nauwkeurigheid van de informatie of de geschiktheid ervan voor een bepaalde situatie. Bovendien kan deze inhoud advertenties van derden bevatten; a16z heeft dergelijke advertenties niet beoordeeld en keurt de daarin opgenomen advertentie-inhoud niet goed.

Deze inhoud is uitsluitend bedoeld voor informatieve doeleinden en mag niet worden beschouwd als juridisch, zakelijk, investerings- of belastingadvies. U dient hierover uw eigen adviseurs te raadplegen. Verwijzingen naar effecten of digitale activa zijn alleen voor illustratieve doeleinden en vormen geen beleggingsaanbeveling of aanbod om beleggingsadviesdiensten te verlenen. Bovendien is deze inhoud niet gericht op of bedoeld voor gebruik door beleggers of potentiรซle beleggers, en mag er in geen geval op worden vertrouwd bij het nemen van een beslissing om te beleggen in een fonds dat wordt beheerd door a16z. (Een aanbod om te beleggen in een a16z-fonds wordt alleen gedaan door middel van het onderhandse plaatsingsmemorandum, de inschrijvingsovereenkomst en andere relevante documentatie van een dergelijk fonds en moet in hun geheel worden gelezen.) Alle genoemde beleggingen of portefeuillebedrijven waarnaar wordt verwezen, of beschreven zijn niet representatief voor alle investeringen in voertuigen die door a16z worden beheerd, en er kan geen garantie worden gegeven dat de investeringen winstgevend zullen zijn of dat andere investeringen die in de toekomst worden gedaan vergelijkbare kenmerken of resultaten zullen hebben. Een lijst van investeringen die zijn gedaan door fondsen die worden beheerd door Andreessen Horowitz (met uitzondering van investeringen waarvoor de uitgevende instelling geen toestemming heeft gegeven aan a16z om openbaar te maken, evenals onaangekondigde investeringen in openbaar verhandelde digitale activa) is beschikbaar op https://a16z.com/investments /.

De grafieken en grafieken die hierin worden verstrekt, zijn uitsluitend bedoeld voor informatieve doeleinden en er mag niet op worden vertrouwd bij het nemen van een investeringsbeslissing. In het verleden behaalde resultaten zijn geen indicatie voor toekomstige resultaten. De inhoud spreekt alleen vanaf de aangegeven datum. Alle projecties, schattingen, voorspellingen, doelstellingen, vooruitzichten en/of meningen die in deze materialen worden uitgedrukt, kunnen zonder voorafgaande kennisgeving worden gewijzigd en kunnen verschillen of in strijd zijn met meningen van anderen. Zie https://a16z.com/disclosures voor aanvullende belangrijke informatie.

spot_img

Laatste intelligentie

spot_img