Sümboolne testimine Halmosega: olemasolevate testide kasutamine ametlikuks kontrollimiseks

Ametlikku kontrollimist – matemaatiliste meetodite kasutamist programmi või nutika lepingu „kontrollimiseks” suvalise arvu sisendite lõikes – peetakse üldiselt lakoonilisemaks ja põhjalikumaks alternatiiviks traditsioonilisele testimisele kvaliteetsema ja turvalisema koodi kirjutamiseks. Kuid tegelikult on ametlik kontrollimine avatud ja interaktiivne protsess. Sarnaselt üksuse testimisega peavad arendajad dünaamiliselt määratlema ja kihistama formaalsed spetsifikatsioonid, korrates oma lähenemisviisi koodi ja analüüside arenedes. Lisaks on formaalne kontrollimine sama tõhus kui selle spetsifikatsioonid, mille kirjutamine võib olla aeganõudev (ja sageli kaasneb sellega järsk õppimiskõver). 

Paljude arendajate jaoks, kes peavad protsessi hirmutavaks, on ühikutestid sageli kulu- ja ajasäästlikum viis programmi õigsuse väljaselgitamiseks. Praktikas ei ole ametlik kontrollimine ühikutestimise ulatuslikum alternatiiv, vaid täiendav. Nendel protsessidel on erinevad tugevused ja piirangud, mis annavad koos kasutamisel veelgi suurema kindlustunde. Arendajad peavad alati kirjutama ühikuteste – mis siis, kui saaksime ametlikuks kontrollimiseks kasutada samu atribuute?

Halmos, meie avatud lähtekoodiga ametlik kinnitustööriist, võimaldab arendajatel seda teha taaskasutada samad omadused, mis on kirjutatud formaalsete spetsifikatsioonide ühiktestide jaoks sümboolse testimise kaudu. Selle asemel, et luua algusest peale tugev atribuutide komplekt, saavad arendajad vältida dubleerivat tööd ja täiustada oma teste mitu spetsifikatsiooni korraga, ilma nullist alustamata. Kavandasime selle tööriista kasutamiseks ametlikus kinnitamisprotsessis kõrvuti muude tööriistadega ametliku kinnitamise platvormina; arendajad saavad minimaalse vaevaga alustada mõne analüüsiga, enne kui lisavad hiljem neid.

Selles postituses käsitleme formaalse kontrolliga seotud väljakutseid ja potentsiaali ületada lõhe üksuse testimise ja ametliku kontrollimise vahel sümboolse testimise abil. Seejärel käime läbi Halmose demo, kasutades olemasolevat nutikat lepingukoodi, ja heidame kiire pilgu teistele arendajatele saadaolevatele ametlikele kinnitustööriistadele (paljud avatud lähtekoodiga).

Ametlik kontrollimine vs testimine

Ametlik kinnitus — mida plokiahela arendajad üldiselt eelistavad selle ranguse ja kõikehõlmavuse tõttu — on programmi õigsuse tõendamise protsess, kontrollides, kas see vastab teatud korrektsuse omadustele. Programmile omased atribuudid pakutakse tavaliselt väljastpoolt ja neid väljendatakse ametliku keele või märgete abil, mida kasutatav kinnitustööriist toetab. Arendajad tajuvad formaalset kontrollimist sageli kui klahvilahendust atribuutide automaatseks testimiseks kõigis võimalikes stsenaariumides, kuid tegelikult võib ametlik kontrollimine olla töömahukas ja väga interaktiivne protsess.

Sarnaselt ametlikule kontrollimisele hõlmab üksuse testimine hindamist, kas programm töötab ootuspäraselt; testimine aga kontrollib ainult programmi käitumist mõned sisendid, samas kui ametlik kontroll võib seda kontrollida kõik võimalikud sisendid. Nii testimine kui ka ametlik kontrollimine nõuavad programmi eeldatava käitumise kirjeldust (koos testimisel kasutatavate testjuhtumitega ja formaalsel kontrollimisel kasutatavate formaalsete spetsifikatsioonidega). Kuid koos kasutamisel võivad need pakkuda programmi põhjalikumat uurimist. Näiteks testimine on tõhus lihtsate vigade leidmisel, kuid üldiselt on seda kiirem ja lihtsam teostada. Ametlik kinnitamine, kuigi seda on tülikam kasutada, on piisavalt võimas, et tõestada vigade puudumist või paljastada peeneid vigu, mida on testimisel või koodiülevaatustel lihtne kahe silma vahele jätta.

Spetsifikatsioon üldkulud

Ametliku kontrollimise üks peamisi väljakutseid on ametlike spetsifikatsioonide kirjutamise ja säilitamise üldkulud. See protsess hõlmab sageli aeganõudvat ülesannet spetsifikatsioonide käsitsi kirjutamiseks spetsiaalses keeles (mida paljud arendajad peavad esmalt õppima). Protsess on ka järkjärguline, alustades tavaliselt lihtsate atribuutide kirjutamisest ja esmalt nende kontrollimisest, seejärel lisades järk-järgult keerukamad omadused. Sarnaselt testimisele on see avatud protsess, millel pole selget peatuspunkti, ja olemasoleva aja jooksul saab lisada ainult võimalikult palju omadusi. Lisaks, kui arendajad muudavad koodi kontrollimise ajal, peavad nad värskendama ka oma olemasolevaid spetsifikatsioone, mis toob kaasa täiendavaid hooldustöid. Need tegurid võivad muuta ametliku kontrollimise mõne arendaja jaoks hirmuäratavaks ülesandeks, kes kõhklevad lisakuludega.

Ja kuigi testimine ja ametlik kontrollimine võivad koos kasutamisel koodi kvaliteeti parandada, nõuavad mõlemad (mõnikord sarnased) programmi eeldatava käitumise kirjeldust erinevates keeltes ja vormingutes. Nende kirjelduste kirjutamine ja säilitamine on töömahukas ning sama kirjelduse kahe erineva vormi säilitamine võib tunduda dubleeritud pingutusena. See tõstatab järgmise küsimuse: kas oodatavat käitumist on võimalik kirjeldada viisil, mida arendajad saavad kasutada nii testimiseks kui ka kontrollimiseks?

Testimise ja formaalse kontrolli vahelise lõhe ületamine sümboolse testimise ja Halmosega

Sümboolne testimine, sümboolsete sisenditega testide käitamine, on tõhus ametlik kontrollimeetod, mis vähendab spetsifikatsiooni üldkulusid. See lähenemisviis võimaldab kasutada samu testjuhtumeid nii testimiseks kui ka ametlikuks kontrollimiseks. Erinevalt traditsioonilisest testimisest, mis kontrollib, kas programm töötab õigesti piiratud hulga sisendite korral, kontrollib sümboolne testimine programmi kõiki võimalikke sisendeid, seega võib sümboolse testimise läbinud programmi lugeda ametlikult kontrollituks.

Halmos on ametlik kontrollitööriist, mis on loodud sümboolseks testimiseks. Selle asemel, et nõuda eraldi spetsifikatsioone või õppida uut keelt, kasutab Halmos olemasolevaid teste ametlike spetsifikatsioonidena. Halmose kaudu testide käitamine kontrollib automaatselt, et need läbivad kõik võimalikud sisendid, või esitatakse vastunäiteid. See mitte ainult ei välista vajadust täiendavate spetsifikatsioonide kirjutamise järele, vaid võimaldab ka ühikutestimiseks või fuzzingiks kirjutatud teste ametliku kontrollimise eesmärgil uuesti kasutada.

Seega on arendajatel suurem paindlikkus valida erinevate kvaliteeditagamisvõimaluste hulgast, sealhulgas üksuse testimine, hägustamine ja ametlik kontrollimine, olenevalt nende hetkevajadustest. Näiteks võivad testid kiiresti tuvastada lihtsaid vigu, võib-olla juhuslikke sisendeid genereeriva fuzzeri abil, ja siis saab Halmos veelgi suurendada usaldust programmi õigsuses kõigis sisendites.

Näide: testimine isPowerOfTwo() funktsioon

Näiteks kaaluge järgmist isPowerOfTwo() funktsioon, mis määrab, kas antud arv on kahe astmega. See funktsioon kasutab a bitiga manipuleerimise algoritm tõhususe tagamiseks, kuid selle õigsuse tõestamine võib olla keeruline, eriti juhul, kui sisend ei ole kahe astmega.

Kujutage ette järgmist testi isPowerOfTwo() funktsioon: see võrdleb funktsiooni tegelikku väljundit antud sisendi eeldatava väljundiga. See on parameetritega test (tuntud ka kui atribuudipõhine test), mis tähendab, et saate seda hõlpsalt käivitada erinevate sisendväärtustega, võib-olla hägusate tööriistadega, nagu Foundry.

Selle testi abil saate uurida isPowerOfTwo() toimib üksuse testimise või fuzz-testimise kaudu, käivitades seda valitud sisenditega. Sellised testid ei saa formaalselt tõestada funktsiooni õigsust, kuna arvutuslikult on võimatu testida iga võimaliku sisendi jaoks.

Halmos aga võimaldab arendajatel neid olemasolevaid teste ametlikuks kontrollimiseks vaid vähese lisapingutusega uuesti kasutada. Tööriist kontrollib testide läbimist kõigi võimalike sisendite puhul, sooritades testi sümboolse täitmise ja seejärel kontrollides, et väidet pole kunagi rikutud (või kui väidet is rikutud, esitades vastunäite). See tähendab, et kui test läbib Halmose, kontrollitakse funktsiooni õigsust formaalselt, mis tähendab, et algoritm on õigesti rakendatud ja kompilaator on selle täpselt baitkoodiks tõlkinud.

Piirang: piiratud sümboolne täitmine

Täisautomaatset, täielikku sümboolset testimist ei ole üldjuhul võimalik teostada, kuna selleks oleks vaja lahendada probleemi peatamine, mis teatavasti on otsustamatu. Selle üheks põhjuseks on see, et sageli on võimatu automaatselt määrata, mitu korda tsükkel sümboolselt korduma peaks. Seetõttu on täisautomaatne formaalne kontrollimine üldiselt otsustamatu.

Arvestades neid põhimõttelisi piiranguid, eelistab Halmos automatiseerimist täielikkusele. Selleks on Halmos loodud piiritute tsüklite (kus iteratsioonide arv sõltub programmi sisenditest) või muutuva pikkusega massiivide (sh stringide) jaoks piiritletud sümboolsete arutluste teostamiseks. See ohverdab mõningase täielikkuse, kuid võimaldab Halmosel vältida nõudmist, et kasutaja esitaks täiendavaid märkusi, näiteks tsükliinvariante.

Näiteks kaaluge järgmist iteratiivset versiooni isPowerOfTwo() funktsioon, millel on piiramata while-tsükkel, kus tsükli iteratsioonide arv määratakse sisendnumbri esitamiseks vajaliku minimaalse bittide arvuga.

Halmos kordab seda piiramatut tsüklit sümboolselt ainult kuni määratud piirini. Näiteks kui piiranguks on seatud 3, kordab Halmos tsüklit maksimaalselt 3 korda ega võta arvesse sisendväärtusi, mis põhjustaksid tsükli kordumise rohkem kui 3 korda (st väärtused, mis on suuremad kui 2^3 või sellega võrdsed ). Sel konkreetsel juhul võimaldaks Halmose täielikuks seadmine piiranguks 256 või kõrgemale.

Demo: ERC721A ametlik kontrollimine Halmosega

Halmose võimekuse demonstreerimiseks kasutasime seda sümboolseks testimiseks ja formaalseks kontrollimiseks ERC721A, ERC721 standardi kõrgelt gaasile optimeeritud rakendus, mis võimaldab partiide vermimist peaaegu sama hinnaga kui ühe vermimise. ERC721A sisaldab mitmeid uuenduslikke optimeerimine selle tõhususe saavutamiseks; Näiteks saab gaasi säästa, kui viivitada märgi omandiandmete uuendamisega kuni märgi üleandmiseni, mitte vermimise ajal. See nõuab keerukate andmestruktuuride ja algoritmide kasutamist, et laisast andmestruktuurist omandiõiguse kohta teavet tõhusalt hankida. Ja kuigi see optimeerimine parandab gaasi tõhusust, suurendab see ka koodi keerukust ja muudab rakenduse õigsuse tõestamise keeruliseks. See muudab ERC721A heaks kandidaadiks ametlikuks kontrollimiseks, kuna see võib suurendada usaldust juurutamise vastu ja tuua kasu potentsiaalsetele kasutajatele.

Sümboolsed testimisomadused

Kuna olemasolevad testid ERC721A jaoks on kirjutatud JavaScriptis Hardhatiga (mida Halmos praegu ei toeta), kirjutasime Soliditysse uued testid peamiste sisenemispunkti funktsioonide jaoks: mint(), burn()ja transfer(). Need testid kontrollisid, kas iga funktsioon värskendab õigesti loa omandiõigust ja saldot ning mõjutab ainult asjakohaseid kasutajaid, ilma et see muudaks teiste kasutajate saldot või omandiõigust. Viimast ei ole triviaalne tõestada, kuna ERC721A kasutatakse laiska andmestruktuuri algoritmi. Näiteks kontrollib järgmine test, et transfer() funktsioon värskendab õigesti määratud loa omandiõigust:

Teine test kontrollib, kas transfer() funktsioon ei muuda teiste aadresside tasakaalu, mida on keeruline tõestada, nagu varem mainitud:

Kontrolli tulemused

Tegime ERC721A nutilepingul Halmose abil kontrollikatse, kirjutades kokku 19-test. Testid viidi läbi Halmose silmuse lahtirullimise piiriga 3, mille sooritamiseks kulus 16 minutit. Kontrollimise aja jaotus on näha allolevas tabelis. Katse viidi läbi MacBook Pro-ga, millel oli M1 Pro kiip ja 16 GB mälu.

test	Aeg (s)
testBurnBalanceUpdate	6.67
testBurnNextTokenIdUnchanged	1.40
testBurnOtherBalancePreservation	5.69
testBurnOtherOthershipPreservation	189.70
testBurnOwnershipUpdate	3.81
testBurnRequirements	71.95
testMintBalanceUpdate	0.20
testMintNextTokenIdUpdate	0.18
testMintOtherBalanceSäilitamine	0.26
testMintOtherOwnership Preservation	5.74
testMintOwnershipUpdate	1.38
testMintRequirements	0.09
testTransferBalanceUnchanged	9.03
testTransferBalanceUpdate	53.53
testTransferNextTokenIdUnchanged	4.47
testTransferOtherBalancePreservation	19.57
testTransferOtherOwnership Preservation	430.61
testTransferOwnershipUpdate	18.71
testTransferRequirements	149.18

Kui enamik teste tehti mõne sekundiga, siis mõnel neist kulus mitu minutit. Neid aeganõudvaid teste oli kaalutavate juhtumite keerukuse tõttu keeruline kontrollida ja need olid tihedalt seotud laisa andmestruktuuri algoritmi õigsusega.

Üldiselt näitavad selle katse tulemused, et Halmos suudab tõhusalt kontrollida nutika lepingu koodi õigsust. See tagab suurema usalduse koodi terviklikkuse suhtes, hoolimata nutika lepingu keerukusest ja võimalikest eelisjuhtudest.

Katsetage süstitud putukatega

Halmose piiratud arutluskäigu tõhususe demonstreerimiseks kasutasime seda vigade tuvastamiseks ERC721A lepingu eelmises versioonis. Sellel versioonil oli probleem, mis käsitles valesti aritmeetilist ületäitumist ja võimaldas potentsiaalselt suure hulga žetoonide partiide vermimist, mis võib rikkuda laiska andmestruktuuri terviklikkust ja põhjustada mõne kasutaja loa omandiõiguse kaotamise (probleem lahendatud praeguses versioonis). Tegime sama 19 testist koosneva komplekti ERC721A jaoks lollaka versiooniga ja Halmos suutis leida vastunäite auto omaduste kohta. mint() funktsiooni. Täpsemalt esitas Halmos sisendväärtused, mis viisid ülalkirjeldatud kasutusstsenaariumini. Selle katse tulemused näitavad, et vaatamata oma ebatäielikkusele võib Halmose piiratud arutluskäik olla tõhus viis arukate lepingute kasutatavate vigade tuvastamiseks ja ennetamiseks.

Seotud tööd

Erinevad meeskonnad on välja töötanud Ethereumi nutika lepingu baitkoodi ametlikud kontrollitööriistad. Nende tööriistade, sealhulgas Halmose abil saab tagada nutikate lepingute turvalisuse ja korrektsuse. Nende tööriistade erinevate funktsioonide, võimaluste ja piirangute võrdlemine ja mõistmine võib aidata arendajatel valida nende ainulaadsete vajaduste jaoks sobivaima.

Kuigi Halmos on aruka lepingu kinnitamise tööriistakomplekti väärtuslik täiendus, on see mõeldud olemasolevate tööriistade täiendamiseks (mitte asendamiseks). Arendajad saavad kombineerida Halmost teiste tööriistadega, et saavutada oma lepingutes kõrgem kindlustase. Allpool võrdleme Halmost mõne valitud formaalse tööriistaga, mis toetavad EVM-i baitkoodi.

• K on võimas formaalne kontrolliraamistik, mis võimaldab deduktiivset kontrolli ja interaktiivset teoreemide tõestamist. Selle aluseks olev teooria ja rakendamine pakuvad kõrget väljendusvõimet, muutes selle sobivaks keerukate programmide ja algoritmide kontrollimiseks. Siiski tuleb märkida, et K ei ole loodud automaatsele kinnitamisele suurt rõhku panema ja sellel puuduvad teatud automatiseerimisfunktsioonid, mis võivad nõuda kontrollimise ajal rohkem käsitsi tööd. K-raamistiku kasutamiseks kirjutatakse formaalsed spetsifikatsioonid K-keeles, mis tuleb enne kasutamist selgeks õppida. Selle tugevus on eriti kasulik keeruliste süsteemide kontrollimisel, mille analüüsimine automatiseeritud arutluskäigu abil võib olla keeruline.
• Certora on nutikate lepingute ametlik verifitseerimistööriist, mis keskendub automaatsele kontrollimisele ja toetab sarnaselt Halmosele piiratud mudelikontrolli. Certora kasutamiseks peavad arendajad õppima oma uut keelt, CVL, et kirjutada spetsifikatsioonid. See keel võimaldab paljude kriitiliste omaduste kokkuvõtlikku kirjeldamist lepinguinvariantide kaudu, mida Halmos praegu ei toeta. Hoolimata sellest, et Certora on suletud lähtekoodiga patenteeritud tööriist, pakub see tugevat ametlikku kontrollitööriista koos pideva arenduse ja hea kasutajatoega.
  
  Halmos seevastu on avatud lähtekoodiga tööriist, mis on mastaapselt väiksem ja millel puuduvad praegu mõned Certora pakutavad funktsioonid, kuid see on mõeldud teenima avalikku hüve ja on mõeldud nišilahenduseks nutikate lepingute kiireks kontrollimiseks ilma seda kasutamata. vajadus põhjaliku seadistamise ja hoolduse järele.
• HEVM on veel üks ametlik kontrollitööriist, mis sarnaneb Halmosega. See oli varem osa DappToolsist, mis on Foundry eelkäija. Nii HEVM-il kui ka Halmosel on omadus, et nad ei nõua eraldi spetsifikatsiooni ja võivad sümboolselt teostada olemasolevaid teste, et tuvastada väidete rikkumisi. See võimaldab kasutajatel kasutada mõlemat tööriista vaheldumisi või käitada neid samade testide jaoks paralleelselt, pakkudes neile mitu võimalust sümboolseks testimiseks.
  
  Väärib märkimist, et vaatamata nende sarnasustele on HEVM ja Halmos välja töötatud iseseisvalt ja erinevad rakendusdetailide poolest; eelkõige optimeerimiste ja sümboolsete arutlusstrateegiate osas. Lisaks on HEVM kirjutatud Haskelli keeles, Halmos aga Pythonis, pakkudes kokkupuudet rikkaliku Pythoni ökosüsteemiga. Mõlema tööriista kasutamise võimalus annab kasutajatele rohkem paindlikkust ja võimalusi nutikate lepingute turvalisuse ja korrektsuse tagamiseks.

Halmos on avatud lähtekoodiga ja praegu beetafaasis. Töötame aktiivselt uute kallal Omadused ja funktsionaalsus, sealhulgas Foundry petukoodid ja mitmed muud olulised kasutatavuse funktsioonid. Oleme väga tänulikud teie mõtete eest selle kohta, millised funktsioonid on kõige olulisemad, ning ootame tagasisidet, ettepanekuid ja kaastöid, et muuta Halmos kõigi jaoks paremaks tööriistaks.

**

Siin väljendatud seisukohad on tsiteeritud AH Capital Management, LLC (“a16z”) üksikute töötajate seisukohad, mitte a16z ega tema sidusettevõtete seisukohad. Teatud siin sisalduv teave on saadud kolmandate osapoolte allikatest, sealhulgas a16z hallatavate fondide portfelliettevõtetelt. Kuigi a16z on võetud usaldusväärseteks peetud allikatest, ei ole a16z sellist teavet sõltumatult kontrollinud ega kinnita teabe praegust või püsivat täpsust ega selle sobivust antud olukorras. Lisaks võib see sisu sisaldada kolmandate isikute reklaame; aXNUMXz ei ole selliseid reklaame üle vaadanud ega toeta neis sisalduvat reklaamisisu.

See sisu on esitatud ainult informatiivsel eesmärgil ja sellele ei tohiks tugineda kui juriidilisele, äri-, investeerimis- ega maksunõustamisele. Nendes küsimustes peaksite konsulteerima oma nõustajatega. Viited mis tahes väärtpaberitele või digitaalsetele varadele on illustratiivse tähendusega ega kujuta endast investeerimissoovitust ega investeerimisnõustamisteenuste pakkumist. Lisaks ei ole see sisu suunatud ega mõeldud kasutamiseks ühelegi investorile ega potentsiaalsetele investoritele ning sellele ei tohi mingil juhul tugineda, kui tehakse otsus investeerida a16z hallatavasse fondi. (A16z fondi investeerimise pakkumine tehakse ainult sellise fondi erainvesteeringute memorandumi, märkimislepingu ja muu asjakohase dokumentatsiooni alusel ning neid tuleks lugeda tervikuna.) Kõik mainitud, viidatud investeeringud või portfelliettevõtted või kirjeldatud ei esinda kõiki a16z hallatavatesse sõidukitesse tehtud investeeringuid ning ei saa olla kindlust, et investeeringud on tulusad või et teised tulevikus tehtavad investeeringud on sarnaste omaduste või tulemustega. Andreessen Horowitzi hallatavate fondide tehtud investeeringute loend (v.a investeeringud, mille kohta emitent ei ole andnud A16z-le luba avalikustada, samuti etteteatamata investeeringud avalikult kaubeldavatesse digitaalvaradesse) on saadaval aadressil https://a16z.com/investments /.

Siin esitatud diagrammid ja graafikud on üksnes informatiivsel eesmärgil ja neile ei tohiks investeerimisotsuse tegemisel tugineda. Varasemad tulemused ei näita tulevasi tulemusi. Sisu räägib ainult märgitud kuupäeva seisuga. Kõik nendes materjalides väljendatud prognoosid, hinnangud, prognoosid, eesmärgid, väljavaated ja/või arvamused võivad muutuda ilma ette teatamata ning võivad erineda või olla vastuolus teiste väljendatud arvamustega. Olulist lisateavet leiate aadressilt https://a16z.com/disclosures.