Abstraktse tõlgendamise selgitus: võreteooriast järelduste ja astroloogiani

Kujutage ette kahte programmi, mis mõlemad läbivad kõik teie kirjutatud testid. Üks on õige. Teisel on nulliga jagamise viga, mis käivitub ainult siis, kui samaaegselt saabub kindel sisendite kombinatsioon – kombinatsioon, mida teie testid kunagi ei anna. Traditsiooniline testimine ei saa teile öelda, milline on milline. Abstraktne interpretatsioon saab seda teha.

Abstraktne interpretatsioon on matemaatiline raamistik, mis annab staatilise analüüsi tööriistadele võimaluse arutleda programmi kõigi võimalike käitumiste üle ilma seda käivitamata. See on tehnika, mille taga on Facebooki Infer, mis leiab null-pointeri vigu suures mahus, Astrée analüsaator, mis ametlikult kontrollib Airbusi lennujuhtimistarkvara, ja iga staatiline analüsaator, mis väidab end olevat usaldusväärne – garantii, et kui programm läbib analüüsi, on see tegelikult vaba kontrollitavatest vigadest. Selle toimimise mõistmine selgitab, miks mõned tööriistad leiavad vigu, mida teised ei märka, ja miks nende garantiidega kaasnevad teatud kompromissid.

Mis on abstraktne tõlgendamine?

Abstraktne interpretatsioon on programmi lähendamise teooria, mille töötasid välja Patrick Cousot ja Radhia Cousot 1977. aastal. Põhiidee: kõigi võimalike programmi olekute täpse hulga arvutamise asemel, mis on üldiselt lahendamatu, arvutada ohutu ülelähendamine lihtsustatud matemaatilise domeeni abil, mida on lihtne analüüsida.

Sõna „abstraktne” ei tähenda siin ebamäärast ega kontseptuaalset. See viitab konkreetsele matemaatilisele tehtele: konkreetsete väärtuste hulga abstraktseks esitamiseks lihtsamal kujul, mis säilitab olulised omadused, jättes samal ajal välja ebavajalikud detailid. Konkreetne täisarv, näiteks 42 muutub märgianalüüsi abstraktsioonis lihtsalt „positiivseks“. Abstraktsioon kaotab informatsiooni (te ei tea enam täpset väärtust), kuid saavutab käsitletavuse (mis tahes täisarvu märk on üks kolmest võimalusest: positiivne, negatiivne või null).

Programmianalüüsi jaoks on selle kasulikuks tinginud garantii: kui analüüs ei leia abstraktses domeenis viga, siis pole viga ka üheski konkreetses teostuses. Kui see leiab potentsiaalse vea, võib see viga praktikas esineda või mitte, kuid tegelikku viga ei saa varjata. See on usaldusväärsus.

Abstraktne tõlgendamine vs. AST analüüs vs. dünaamiline analüüs

Neid termineid aetakse sageli segamini, selle artikli otsinguandmetes esineb „AST-koodi analüüs” ja need kirjeldavad erinevaid asju.

Abstraktne süntaksipuu on andmestruktuur, mis esindab lähtekoodi grammatilist struktuuri. Iga kompilaator ja linter loob selle. See on aluseks parsimisele, refaktoreerimistööriistadele ja mustripõhisele staatilisele analüüsile. AST-põhine analüüs leiab mustreid: märgistatakse reeglile vastav kood (liiga paljude parameetritega funktsioon, liitmise teel loodud SQL-string). See ei arutle väärtuste ega käitusaja käitumise üle.

Abstraktne interpretatsioon arutleb käitusaja käitumise üle ilma programmi käivitamata. See kasutab sisendina AST-d, kuid läheb sellest palju kaugemale: modelleerib väärtuste liikumist programmis, muutujate vahemikke, kas pointer võib konkreetses kutsumiskohas olla null ja kas tsükkel lõpeb. AST-analüüs on mustrite sobitamine. Abstraktne interpretatsioon on käitumuslik arutluskäik.

Enamik lintreid (ESLint, Checkstyle, Pylint) on peamiselt AST-põhised. Enamik formaalseid verifitseerimisvahendeid (Infer, Astrée, Polyspace) kasutavad abstraktset interpretatsiooni. Dünaamiline analüüs (programmi käivitamine ja tegeliku käitumise jälgimine) leiab ainult teatud sisendite poolt käivitatud vigu. Abstraktne interpretatsioon leiab vigu kõigist võimalikest sisenditest ilma programmi üldse käivitamata.

Staatilise analüüsi matemaatilised põhimõtted

Päring „millised on staatilise analüüsi tööriistade matemaatilised põhimõtted?” kuvatakse otse otsinguandmetes. Siin on lihtne vastus.

Abstraktne tõlgendus tugineb kolmele matemaatilisele struktuurile:

Võred. Võre on osaliselt järjestatud hulk, kus igal elementide paaril on vähim ülemine piir (liitumine) ja suurim alumine piir (kohtumine). Staatilises analüüsis esindab võre abstraktset domeeni ehk võimalike abstraktsete väärtuste hulka, mis on järjestatud vastavalt sellele, kui palju infot nad kannavad. Märkide analüüsis näeb võre välja selline:

        ⊤ (unknown -- could be anything)
       / \
   pos   neg
       \ /
        0
        |
        ⊥ (unreachable -- no possible value)

Võres ülespoole liikumine tähendab täpsuse kaotamist (vähem teadmist). Allapoole liikumine tähendab selle saavutamist (rohkem teadmist). Ülemine element ⊤ tähendab „me ei tea midagi kasulikku“. Alumine element ⊥ tähendab „see olek on kättesaamatu“.

Galois' seosed. Galois' seos on formaalne seos konkreetse domeeni (tegelikud programmi väärtused) ja abstraktse domeeni (lihtsustatud esitus) vahel. See koosneb kahest funktsioonist: abstraktsioonifunktsioonist α, mis seob konkreetsed väärtused nende abstraktse esitusega, ja konkretiseerimisfunktsioonist γ, mis seob abstraktsed väärtused tagasi konkreetsete väärtuste hulgaga, mida nad esindavad.

Kriitiline omadus: abstraktne domeen peab olema ohutu üleaproksimatsioon. γ(α(S)) ⊇ S iga konkreetse hulga S korral. Abstraktsioon võib sisaldada rohkem väärtusi, kui tegelikult esineb, mis annabki valepositiivseid tulemusi, kuid see ei tohi kunagi välistada väärtusi, mis tegelikult esinevad. Reaalsete väärtuste välistamine tähendaks reaalsete vigade märkamata jätmist.

Fikseeritud punkti iteratsioon. Tsüklitega programmide puhul peab analüüs itereeruma seni, kuni see jõuab stabiilsesse olekusse. Sellise tsükli puhul nagu:

c

int x = 0;
while (condition) {
    x = x + 1;
}

Esimesel iteratsioonil x is {0}Pärast ühte silmust keha x võib olla {0, 1}Pärast kahte {0, 1, 2}See hulk kasvab pidevalt, see ei stabiliseeru kunagi iseenesest. Lahendus on laienemine: operaator, mis sunnib lähenemist, hüpates laiemale lähendusele (tavaliselt [0, +∞) intervallanalüüsi jaoks). Seejärel kasutab analüüs ahenemine et taastada teatav täpsus.

See fikseeritud komaga arvutus on see, mis muudab abstraktse interpretatsiooni täielikuks kõigil teostusradadel, sealhulgas tsüklitel, ja mis teeb selle arvutuslikult kallimaks kui lihtne mustrite sobitamine.

Abstraktsed domeenid: lähendatavate valdkondade valimine

Abstraktne valdkond määrab, mida analüüs suudab ja mida mitte leida. Erinevad valdkonnad vastavad programmi käitumise kohta erinevatele küsimustele.

Abstraktne domeen	Mida see jälgib	Kasutamise näide	Mida see igatseb
Märkide analüüs	Kas väärtused on positiivsed, negatiivsed või nullid	Nulli abil jagamine	Täpsed väärtused, ületäitumise tingimused
Intervalli analüüs	Numbriliste väärtuste ülemine ja alumine piir	Puhvri ületäitumine, massiivi juurdepääsu ohutus	Muutujate vahelised seosed
Kaheksanurkne domeen	Muutujate paaride vahelised lineaarsed seosed	Täpsem ülevoolu tuvastamine	Mittelineaarsed seosed
Pointeri analüüs	Kas osutid võivad olla nullid või üksteise aliasendid	Null dereferents, kasutus pärast vabaks jätmist	Objekti eluiga, kuhja kuju
Rikkumise analüüs	Kas väärtused pärinevad ebausaldusväärsetest allikatest	SQL-süstimine, XSS-tuvastus	Kaudsed vood läbivad kontrolli
Polüheedriline domeen	Suvalised lineaarsed aritmeetilised piirangud	Silmusepiiriga seotud verifitseerimine	Toimivuskulud skaleeruvad eksponentsiaalselt

Domeenide vaheline kompromiss on alati täpsuse ja jõudluse vahel. Intervallidomeen on kiire ja tabab enamiku numbrilisi vigu. Hulktahuline domeen on palju täpsem, kuid sellel on muutujate arvu osas eksponentsiaalne keerukus. Praktilised staatilise analüüsi tööriistad valivad domeenid, mis tasakaalustavad kompromissi oma sihtrakenduse jaoks, ohutuskriitilised manussüsteemid saavad endale lubada aeglasemat ja täpsemat analüüsi; CI/CD-integreeritud linterid peavad töö lõpetama sekunditega.

Kuidas kolm reaalset tööriista abstraktset tõlgendust kasutavad

Teooria eraldi kirjeldamise asemel teevad selle rakendamise selgeks konkreetsed vahendid.

Facebook Infer kasutab Java, C, C++ ja Objective-C analüüsimiseks abstraktse interpretatsiooni vormi, mida nimetatakse bi-abduktsiooniks. Bi-abduktsiooni abil saab automaatselt tuvastada funktsioonide eel- ja järeltingimusi, võimaldades interprotseduurset analüüsi ilma käsitsi täpsustamata. Infer töötab CI-s Facebookis, Spotifys, Mozillas ja kümnetes teistes suurtes organisatsioonides, kuna see skaleerub mitme miljoni rea pikkustele koodibaasidele, jäädes samal ajal kontrollitavate veaklasside jaoks usaldusväärseks.

Astrée kasutab numbriliste abstraktsete domeenidega abstraktset interpretatsiooni, et tõestada C-programmides käitusaja vigade puudumist. Airbus kasutas seda A380 peamise lennujuhtimistarkvara ametlikuks kontrollimiseks, tõestades käitusaja vigade puudumist kogu juhtimissüsteemis – garantiid, mida ükski testimisprogramm ei suuda pakkuda. Astrée ei leia kontrollitavate veaklasside puhul ühtegi valepositiivset tulemust, kuigi see võib anda valepositiivseid tulemusi, mis vajavad käsitsi ülevaatamist.

Polyspace (MathWorks) rakendab ohutuskriitiliste rakenduste manustatud C- ja C++-koodi abstraktset interpretatsiooni. See liigitab iga operatsiooni kas „roheliseks“ (tõestatavalt viga pole), „punaseks“ (kindlasti viga) või „oranžiks“ (potentsiaalne viga, mis vajab ülevaatamist). Roheline klassifikatsioon on formaalne tõestus: ükski teostus ei saa selle operatsiooni juures põhjustada käitusaja viga.

Usaldusväärsuse-täpsuse-jõudluse kolmnurk

Abstraktsete tõlgenduste tööriistad navigeerivad konkureerivate omaduste põhikolmnurgas. Ükski tööriist ei suuda kõiki kolme samaaegselt maksimeerida.

Usaldusväärsus tähendab vale-negatiivsete tulemuste puudumist: analüüsitud klassis tuvastatakse kõik tegelikud vead. Usaldusväärsed tööriistad pakuvad garantiid; mitte-usaldusväärsed tööriistad võivad vigu mitte märgata.

Täpsus tähendab vähe valepositiivseid tulemusi: leiud vastavad pigem tegelikele probleemidele kui teoreetilistele, mis ei saa esineda. Suur täpsus nõuab rafineeritumaid abstraktseid valdkondi ja interprotseduuride analüüsi.

Jõudlus tähendab, et analüüs valmib kasuliku aja jooksul. Täpsem analüüs on kallim. Miljonirealise koodibaasiga kõigi käitusaja vigade puudumise tõestamine võtab tunde; linter-skannimine võtab sekundeid.

Erinevad rakendused vajavad selles kolmnurgas erinevaid punkte:

• IDE linting ja CI/CD: esikohal jõudlus, teiseks täpsus, usaldusväärsus valikuline
• Turvaskannimine: täpsus esikohal (vähendab arendaja valvsuse väsimust), usaldusväärsus on oluline kõrge raskusastmega klasside puhul
• Ohutuskriitiline sertifitseerimine: esikohal on usaldusväärsus (ei saa jätta märkamata tegelikke vigu), jõudlus teisejärguline, valepositiivsed tulemused on vastuvõetavad käsitsi ülevaatamise protsessiga

Abstraktne tõlgendamine manussüsteemides ja ohutuskriitilises arenduses

Päring „staatilise analüüsi eelised manussüsteemide arenduses” viitab abstraktse tõlgendamise ühele olulisemale rakendusvaldkonnale. Manussüsteemidel, autojuhtimisseadmetel, meditsiiniseadmete püsivaral ja lennunduse lennujuhtimistarkvaral on piirangud, mis muudavad abstraktse tõlgendamise eriti väärtuslikuks:

Puudub testimissüsteem kõigi olekute jaoks. Auto ECU reageerib reaalajas tuhandetele andurite kombinatsioonidele. Testide koostamine iga kombinatsiooni jaoks on võimatu. Abstraktne tõlgendus hõlmab kõiki olekuid samaaegselt.

Sertifitseerimisnõuded. Standardid DO-178C (lennundus), ISO 26262 (autotööstus) ja IEC 62443 (tööstuskontroll) nõuavad tarkvara korrektse käitumise demonstreerimist igas olukorras. Formaalne verifitseerimine abstraktse tõlgenduse abil saab seda nõuet täita viisil, mida testide katvusaruanded ei suuda.

Ressursipiirangud. Sisseehitatud tarkvaral puudub sageli mälu eraldaja, erandite käsitlemine ja operatsioonisüsteemi varuvõimalus. Käitusaja viga, null-pointeri viidete puudumine või lubatud piiridest väljas olev massiiv on tõsine süsteemirike. Nende vigade märkamata jätmise hind ei ole krahhiaruanne ja kiirparandus. See on ohutusintsident.

Astrée ja Polyspace'i analüsaatorid on loodud spetsiaalselt selle konteksti jaoks. Nende disain aktsepteerib kõrget valepositiivsete tulemuste määra ja aeglast analüüsi vastutasuks garantii eest, et vale-negatiivseid tulemusi läbi ei pääse.

Valepositiivsed tulemused ja laienev probleem

Abstraktsete tõlgendusvahendite kõige levinum kriitika on valepositiivsed tulemused – hoiatused võimalike vigade kohta, mis reaalses teostuses tegelikult esineda ei saa. Mõistmine, miks valepositiivsed tulemused on omased, mitte kvaliteedipuudujääk, muudab nende haldamise lihtsamaks.

Valepositiivsed tulemused tulenevad kahest allikast:

Ülelähendamine abstraktses valdkonnas. Kui intervalli domeen jälgib x ∈ [0, 100], ei saa see eristada juhtumeid, kus x on praktikas alati väiksem kui 50. Jagamine arvuga x võib olla märgistatud potentsiaalselt nulliga jagatavaks isegi siis, kui programmi loogika garanteerib x > 0Täpsem domeen (täpse väärtuse jälgimine või piiranguga seos) x teisele muutujale) välistaks valepositiivse tulemuse, kuid suurema arvutusliku kuluga.

Laienemine. Konvergeerumisoperaator, mis muudab tsüklianalüüsi teostatavaks, kaotab paratamatult teavet. Pärast laiendamist x Rohkem kui [0, 5] et [0, +∞), analüsaator seda enam ei tea x jääb piiratuks. Kui kood kontrollib assert(x < 1000) pärast tsüklit ei saa seda väidet enam tõestada, isegi kui praktikas x jääb alati alla 1000.

Praktilised strateegiad valepositiivsete tulemuste haldamiseks: konfigureerige analüüs nii, et see kasutaks kriitiliste moodulite jaoks täpsemaid domeene (aktsepteerides aeglasemat analüüsi), summutage kinnitatud valepositiivsed tulemused sihipäraste märkustega ja käsitlege tööriista oranže/tundmatuid leide prioriteetse ülevaatusjärjekorrana, mitte kinnitatud vigadena.

Kuidas SMART TS XL Rakendab staatilist analüüsi ettevõtte tasandil

SMART TS XL tegutseb ruumis, kus abstraktse interpretatsiooni teooria kohtub ettevõtte reaalsusega: mitut keelt hõlmavad koodibaasid, aastakümneid kestnud arendustegevust ja organisatsioonilised piirid, mis muudavad ametliku programmipõhise verifitseerimise ebapraktiliseks.

Selle asemel, et rakendada kõigile programmidele ühte abstraktset domeeni, SMART TS XL'S staatilise koodi analüüs ühendab iga keskkonnas oleva keele (COBOL, JCL, Java, Python, RPG, PL/I, SQL ja kaasaegsed programmeerimiskeeled) jaoks sobivaid struktuurianalüüsi tehnikaid, luues kvaliteedimõõdikuid, sõltuvusandmeid ja turvaleide samaaegselt kogu portfoolio ulatuses.

Rakendussõltuvuste kaardistamise funktsioon rakendab graafiteoreetilist analüüsi keelteülesele kõnegraafikule, tuvastades, kuidas programmid, andmekogumid ja töövood ühenduvad üle keelepiiride – sellist terviklikku süsteemi analüüsi, mida ühe keele tööriistad teha ei suuda. See on struktuuriline arutluskäik süsteemi tasandil: mitte üksikute programmide omaduste, vaid nende ühenduvuse omaduste tõestamine.

Mõjuanalüüsi võimalus rakendab ligipääsetavuse analüüsi sõltuvusgraafikule: kui ühes sõlmes on kavandatud muudatus, arvutage kõigi sellest kättesaadavate sõlmede hulk. See on staatilise analüüsi küsimus „mida see mõjutab?“, millele vastatakse koodi struktuuri, mitte käitusaja vaatluse või inimese hinnangu põhjal.

Meeskondadele, kes juhivad pärand moderniseerimine programmid, SMART TS XLstruktuurianalüüs kaotab lünga formaalsete abstraktsete tõlgendustööriistade (mis on keelespetsiifilised ja nõuavad konfigureerimiseks valdkonnaalaseid teadmisi) ja praktilise vajaduse vahel mõista, mida suured, dokumenteerimata ja mitmekeelsed pärandsüsteemid tegelikult teevad, mis on eeltingimus iga moderniseerimisprogrammi jaoks, mis ei soovi oma kõige kallimaid üllatusi avastada teostuse keskel.

Korduma kippuvad küsimused

Mis vahe on abstraktsel interpretatsioonil ja mudeli kontrollimisel? Mõlemad on formaalsed meetodid programmi verifitseerimiseks. Abstraktne interpretatsioon üleaproksimeerib võimalike olekute hulka (usaldusväärne, kuid potentsiaalselt ebatäpne). Mudeli kontroll uurib ammendavalt olekuruumi (täielik, kuid teostatav ainult lõplike, piiratud süsteemide puhul). Abstraktne interpretatsioon skaleerub suurtele programmidele. Mudeli kontroll skaleerub keerukate omadusteni väiksematel mudelitel. Need täiendavad teineteist, mitte ei konkureeri.

Kas abstraktne interpretatsioon on mõeldud ainult ohutuskriitilise tarkvara jaoks? Ei, kuigi see pakub seal kõige selgemat väärtust. Järeldused töötavad suurte tehnoloogiaettevõtete standardsetes CI/CD torujuhtmetes, leides igapäevases Java ja C koodis null-pointeri deviatsioonide ja ressursilekkeid. Rakendatava ranguse aste on valikuline: ühes otsas täielik usaldusväärsus formaalsete garantiidega, teises otsas kerge heuristiline analüüs ja enamik praktilisi tööriistu kuskil vahepeal.

Kas abstraktne interpretatsioon suudab COBOLi analüüsida? Abstraktne interpretatsioon on teooriana keeleagnostiline. Selle rakendamine COBOLi puhul nõuab COBOLi toimingute abstraktsete ülekandefunktsioonide rakendamist, PIC-välja aritmeetikat, REDEFINES-klausleid, 88. taseme tingimuste nimetusi jne. Üldotstarbelised abstraktse interpretatsiooni tööriistad (Infer, Astrée) ei toeta COBOLi. Ettevõtte struktuurianalüüsi platvormid, mis mõistavad COBOLi natiivselt, rakendavad seotud staatiliste analüüsi tehnikaid, et leida kvaliteediprobleeme, surnud koodi ja arhitektuurilisi probleeme COBOLi koodibaasides.