Analisi del puntatore - Pointer analysis

In informatica , l' analisi dei puntatori o analisi dei punti è una tecnica di analisi statica del codice che stabilisce quali puntatori , o riferimenti di heap, possono puntare a quali variabili o posizioni di archiviazione. È spesso una componente di analisi più complesse come l' analisi della fuga . Una tecnica strettamente correlata è l' analisi della forma .

(Questo è l'uso colloquiale più comune del termine. Un uso secondario prevede che analisi puntatore sia il nome collettivo sia per analisi punti a , definita come sopra, sia per analisi alias . L' analisi punti a e alias sono strettamente correlati ma non sempre equivalenti i problemi.)

Esempio

Per il seguente programma di esempio, un'analisi di punti da calcolare che l'insieme di punti da raggiungere p è { x , y }. 

int x;
int y;
int* p = unknown() ? &x : &y;

introduzione

Come forma di analisi statica, è possibile dimostrare che l'analisi puntatore completamente precisa è indecidibile . La maggior parte degli approcci sono validi , ma variano ampiamente in termini di prestazioni e precisione. Per programmi di grandi dimensioni, potrebbero essere necessari alcuni compromessi per completare l'analisi in un tempo e uno spazio ragionevoli. Due esempi di questi compromessi sono:

  • Trattare tutti i riferimenti di un oggetto strutturato come se provenissero dall'oggetto nel suo insieme. Questo è noto come insensibilità al campo o insensibilità alla struttura .
  • Ignorare il flusso di controllo durante l'analisi degli oggetti assegnati ai puntatori. Questa è nota come analisi del puntatore insensibile al contesto (quando si ignora il contesto in cui vengono effettuate le chiamate di funzione) o analisi del puntatore insensibile al flusso (quando si ignora il flusso di controllo all'interno di una procedura).

Lo svantaggio di queste semplificazioni è che l'insieme calcolato di oggetti puntati può diventare meno preciso.

Algoritmi insensibili al contesto e al flusso

Gli algoritmi di analisi del puntatore vengono utilizzati per convertire gli utilizzi del puntatore non elaborato raccolti (assegnazioni di un puntatore a un altro o assegnazione di un puntatore per puntare a un altro) in un grafico utile di ciò a cui può puntare ciascun puntatore.

L'algoritmo di Steensgaard e l'algoritmo di Andersen sono algoritmi comuni insensibili al contesto e al flusso per l'analisi dei puntatori. Sono spesso usati nei compilatori e hanno implementazioni nella codebase LLVM .

Approcci insensibili al flusso

Molti approcci all'analisi del puntatore insensibile al flusso possono essere intesi come forme di interpretazione astratta , in cui le allocazioni di heap sono astratte dal loro sito di allocazione (cioè, una posizione del programma).

Molti algoritmi insensibili al flusso sono specificati in Datalog , inclusi quelli nel framework di analisi della fuliggine per Java.

Gli algoritmi sensibili al contesto e insensibili al flusso raggiungono una maggiore precisione, generalmente a scapito di alcune prestazioni, analizzando ciascuna procedura più volte, una volta per contesto . La maggior parte delle analisi utilizza un approccio "stringa di contesto", in cui i contesti sono costituiti da un elenco di voci (le scelte comuni di immissione di contesto includono siti di chiamata, siti di allocazione e tipi). Per garantire la terminazione (e più in generale, la scalabilità), tali analisi generalmente utilizzano un approccio k -limiting, in cui il contesto ha una dimensione massima fissa e gli elementi aggiunti meno di recente vengono rimossi secondo necessità. Tre varianti comuni dell'analisi sensibile al contesto e insensibile al flusso sono:

  • Sensibilità del sito di chiamata
  • Sensibilità agli oggetti
  • Digitare la sensibilità

Sensibilità del sito di chiamata

Nella sensibilità del sito di chiamata, il set di punti a di ciascuna variabile (l'insieme di allocazioni di heap astratte a cui ciascuna variabile potrebbe puntare) è ulteriormente qualificato da un contesto costituito da un elenco di siti di chiamata nel programma. Questi contesti astraggono il flusso di controllo del programma.

Il programma seguente dimostra come la sensibilità del sito di chiamata può ottenere una precisione maggiore rispetto a un'analisi insensibile al flusso e al contesto. 

int *id(int* x) {
  return x;
}
int main() {
  int y;
  int z;
  int *y2 = id(&y); // call-site 1
  int *z2 = id(&z); // call-site 2
  return 0;
}

Per questo programma, un'analisi insensibile al contesto concluderebbe (in modo corretto ma impreciso) che x può indicare o l'allocazione che contiene y o quella di z , quindi y2 e z2 possono alias, ed entrambi potrebbero puntare a entrambe le allocazioni. Un'analisi sensibile al sito di chiamata analizzerebbe l' id due volte, una volta per il sito di chiamata 1 e una volta per il sito di chiamata 2, e i fatti di punti per x sarebbero qualificati dal sito di chiamata, consentendo all'analisi di dedurlo quando il principale ritorna , y2 può puntare solo all'allocazione che tiene y e z2 può solo puntare all'allocazione che tiene z .

Sensibilità agli oggetti

In un'analisi sensibile agli oggetti, il set di punti di ciascuna variabile è qualificato dall'allocazione astratta dell'heap dell'oggetto destinatario della chiamata al metodo. A differenza della sensibilità del sito di chiamata, la sensibilità agli oggetti è non sintattica o non locale : le voci di contesto vengono derivate durante l'analisi stessa dei punti.

Digitare la sensibilità

La sensibilità al tipo è una variante della sensibilità agli oggetti in cui il sito di allocazione dell'oggetto destinatario viene sostituito dalla classe / tipo contenente il metodo contenente il sito di allocazione dell'oggetto destinatario. Ciò si traduce in un numero rigorosamente inferiore di contesti rispetto a quello utilizzato in un'analisi sensibile agli oggetti, il che generalmente significa prestazioni migliori.

Riferimenti

Bibliografia