I detta dokument presenteras den första skalbara kontextkänsliga, inklusionsbaserade aliasanalysen för Javaprogram. Vår syn på kontextkänslighet är att skapa en klon av en metod för varje sammanhang av intresse, och köra en kontext-okänslig algoritm över den utvidgade anropsgrafen för att få sammanhangskänsliga resultat. För precision, genererar vi en klon för varje acyklisk väg genom ett programs anrop graf, behandla metoder i en starkt ansluten komponent som en enda nod. Normalt är denna formulering hopplöst svårfångad eftersom en anropsgraf ofta har 10 14 acykliska vägar eller mer. Vi visar att dessa exponentiella relationer kan beräknas effektivt med hjälp av binära beslut diagram (BDD). Nyckeln till teknikens skalbarhet är ett sammanhangsnumreringssystem som avslöjar de gemensamma egenskaperna i olika sammanhang. Vi tillämpade vår algoritm på de mest populära applikationer som finns på Sourceforge, och fann att de största programmen, med hundratusentals Java bytecodes, kan analyseras på under 20 minuter. Detta dokument visar att pekaranalys, och många andra frågor och algoritmer, kan beskrivas kortfattat och deklarativt med hjälp av Datalog, ett logiskt programmeringsspråk. Vi har utvecklat ett system som kallas bddbddb som automatiskt översätter Datalog-program till mycket effektiva BDD-implementationer. Vi använde denna metod för att utveckla en mängd olika sammanhangskänsliga algoritmer, inklusive sidoeffektanalys, typanalys och flyktanalys.
Det finns också en BDD-baserad deduktiva databassystem som kallas bddbddb REF implementeras för att användas i programverifiering som omvandlar Datalog program till effektiva BDD implementationer.
Cloning-based context-sensitive pointer alias analysis using binary decision diagrams
{'venue': "PLDI '04", 'journal': None, 'mag_field_of_study': ['Computer Science']}