Abstrakt. En kompilator är helt abstrakt om sammanställningen från källspråksprogram till målspråksprogram reflekterar och bevarar beteendelikvärdighet. Sådana kompilatorer har viktiga säkerhetsfördelar, eftersom de begränsar kraften hos en angripare som interagerar med programmet i målspråket till att en angripare interagerar med programmet i källspråket. Att testa kompilatorn full-abstraktion är dock ganska komplicerat. En gemensam bevisteknik bygger på en bakåtöversättning av programkontexter på målnivå till beteendemässigt likvärdiga källnivåkontexter. Men det är problematiskt att bygga upp en sådan motöversättning när källspråket inte är tillräckligt starkt för att bädda in en kodning av målspråket. Till exempel, vid sammanställning från en enkel-typad λ-calculus (λ τ ) till en otypad λ-calculus (λ u ), bristen på rekursiva typer i λ τ förhindrar en sådan tillbakaöversättning. Vi föreslår en allmän och elegant lösning på detta problem. Den viktigaste insikten är att det räcker att konstruera en ungefärlig bakåtöversättning. approximationen är endast exakt upp till ett visst antal steg och konservativ utöver detta, i den meningen att det sammanhang som genereras av back-translation kan avvika när originalet inte skulle, men inte vice versa. Baserat på denna insikt, beskriver vi en allmän teknik för att bevisa kompilatorn full-abstraktion och visa det på en kompilator från λ τ till λ u. Beviset använder asymmetriska tvärspråkslogiska relationer och gör innovativt bruk av stegindexering för att uttrycka förhållandet mellan ett sammanhang och dess ungefärliga bakgrundsöversättning. Beviset sträcker sig lätt till vanliga kompilatormönster såsom modulära sammanställningar och, så vitt vi vet, är det den första kompilatorns fullständiga abstraktionsbevis som har mekaniserats helt i Coq. Vi tror att denna bevisteknik kan skala till utmanande inställningar och möjliggöra enklare, mer skalbara bevis på kompilator full-abstraktion.
I en annan tråd av arbete, Devriese et al. REF bevisade modulär fullständig abstraktion genom ungefärlig back-translation för en kompilator från helt enkelt maskinskriven till otypad λ-calculus.
Modular, Fully-abstract Compilation by Approximate Back-translation
{'venue': 'Logical Methods in Computer Science, Volume 13, Issue 4 (October 25, 2017) lmcs:4011', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}