Analisi codice sorgente statico con LLVM

Question

Recentemente ho scoperto il progetto LLVM (low level virtual machine) e da quello che ho sentito può essere utilizzato per eseguire analisi statiche su un codice sorgente. Vorrei sapere se è possibile estrarre la diversa chiamata di funzione tramite il puntatore di funzione (trova la funzione chiamante e la funzione chiamata) in un programma.

Potrei trovare il tipo di informazioni nel sito Web, quindi sarebbe molto utile se potessi dirmi se tale libreria esiste già in LLVM o puoi indicarmi la buona direzione su come costruirla da sola (esistente codice sorgente, riferimento, tutorial, esempio ...).

EDIT:

con la mia analisi Io in realtà voglio estrarre la funzione di chiamata del chiamante/chiamato. Nel caso di un puntatore a funzione, vorrei restituire un set di possibili eventi. sia il chiamante che il chiamato devono essere definiti nel codice sorgente (questo non include la funzione di terze parti in una libreria).

Answer 1

Si dovrebbe dare un'occhiata a Elsa. È relativamente facile da estendere e consente di analizzare un AST abbastanza facilmente. Gestisce tutte le operazioni di parsing, lexing e AST e quindi ti permette di attraversare l'albero usando il pattern Visitor.

class CallGraphGenerator : public ASTVisitor 
{ 
    //... 
    virtual bool visitFunction(Function *func); 
    virtual bool visitExpression(Expression *expr); 
} 

È quindi possibile rilevare le dichiarazioni di funzione e probabilmente rilevare l'utilizzo del puntatore di funzione. Infine è possibile controllare le dichiarazioni dei puntatori di funzione e generare un elenco delle funzioni dichiarate che potrebbero essere state chiamate utilizzando quel puntatore.

Answer 2

Penso che la tua domanda sia difettosa. Il titolo dice "Analisi del codice sorgente statico". Eppure la tua ragione di fondo sembra essere la costruzione di (parte di) un grafo di chiamata che include le chiamate attraverso un puntatore a funzione. L'essenza dei puntatori di funzione è che non puoi conoscere i loro valori in fase di compilazione, cioè nel punto in cui esegui l'analisi del codice sorgente statica. Considerate questo pezzo di codice:

void (*pFoo)() = GetFoo(); 
pFoo(); 

Analisi statica del codice, non si può dire che cosa getFoo() restituisce in fase di esecuzione, anche se potrebbe dire che il risultato viene successivamente utilizzato per una chiamata di funzione.

Ora, quali valori potrebbe restituire GetFoo()? Semplicemente non si può dire questo in generale (equivalente a risolvere il problema dell'arresto). Sarai in grado di indovinare alcuni casi banali. La percentuale presumibile, ovviamente, salirà a seconda di quanto impegno sei disposto a investire.

Answer 3

Penso che Clang (l'analizzatore che fa parte di LLVM) è orientata verso l'individuazione di bug, il che significa che l'analizzatore cerca di calcolare i possibili valori di alcune espressioni (per ridurre i falsi positivi), ma a volte si arrende (in questo caso, non emettere allarmi per evitare un diluvio di falsi positivi).

Se il tuo programma è solo C, ti consiglio di dare un'occhiata all'analisi del valore in Frama-C. Calcola superset di valori possibili per ogni valore di l in ogni punto del programma, sotto alcune ipotesi che sono spiegate alla lunghezza here. La complessità nel programma analizzato significa solo che i superset restituiti sono più approssimati, ma contengono ancora tutti i possibili valori di runtime (a patto che rimangano all'interno delle ipotesi menzionate sopra).

MODIFICA: se sei interessato a possibili valori di puntatori di funzione allo scopo di affettare il programma analizzato, dovresti assolutamente dare un'occhiata allo dependencies esistente e ai calcoli di slicing in Frama-C. Il sito non ha alcuna bell'esempio per affettare, qui è one from a discussion on the mailing-list

Answer 4

Nel nostro progetto, abbiamo eseguire l'analisi statica del codice sorgente convertendo LLVM bytecode in codice C con l'aiuto di llc programma che viene fornito con LLVM. Quindi analizziamo il codice C con CIL (C Intermediate Language), ma per il linguaggio C sono disponibili molti strumenti. Il pitpail che il codice generato da llc è AWFUL e soffre di una grande perdita di precisione. Ma ancora, è un modo per andare.

Modifica: in effetti, non consiglierei a nessuno di piacere. Ma ancora, solo per un record ...

Answer 5

Il fornisce vari tipi di control, data flow, and global points-to analyzers per grandi sistemi di codice C e costruisce grafici di chiamata utilizzando quell'analisi globale di punti-a (con le assunzioni conservative appropriate). Ulteriori discussioni ed esempi delle analisi possono essere trovati sul sito web.

DMS è stato testato su sistemi monolitici di codice C con 25 milioni di linee. (Il grafo delle chiamate per questo mostro conteneva 250.000 funzioni).

Ingegneria tutto questo macchinario da AST C di base e le tabelle dei simboli è una quantità enorme di lavoro; stato lì, fatto. Non vuoi farlo da solo se hai qualcos'altro da fare con la tua vita, come implementare altre applicazioni.