Property-based Testing of Abstract Domains

Staatilise programmianalüüsiga uuritakse programme lähtekoodi põhjal, ilma neid käivitamata. Üks võimalus on selleks kasutada abstraktset interpretatsiooni, et määrata programmi võimalikke ligikaudseid seisundeid, mis moodustavad abstraktse domeeni. Kui kasutatav domeen rahuldab teatud matemaatilisi omadusi, siis abstraktse interpretatsiooni teooria kohaselt on teostatav analüüs korrektne (ingl sound). Staatilise analüsaatori implementeerimisel võib juhtuda, et domeenides esineb vigu, mis rikuvad analüüsi ja selle korrektsuse. Töös koostatakse omaduste komplekt, mida kasutatakse Goblint analüsaatorist omaduspõhise testimise abil vigade leidmiseks. Selleks implementeeritakse Goblintis vajalik domeenide testimise raamistik ja elementide generaatorid. Lõpuks viiakse läbi testimine, tuvastatakse vead ja kirjeldatakse neid. Sellega näidatakse, et omaduspõhist testimist on võimalik efektiivselt rakendada abstraktsetest domeenidest vigade leidmiseks.Static program analysis studies programs based on their source code, without executing them. One approach is to use abstract interpretation to determine a program's possible approximate states, which make up an abstract domain. If the used domain satisfies certain mathematical properties, then the analysis is sound according to the theory of abstract interpretation. When implementing a static analyzer it may happen that the domains contain bugs, which ruin the analysis and its soundness. Here a set of properties is compiled, which are used to find bugs from the Goblint analyzer via property-based testing. For this the necessary domain testing framework and element generators are implemented in Goblint. Finally the testing is conducted, issues identified and described. This shows that property-based testing can effectively be used to find bugs from abstract domains