Análisis de código fuente estático con LLVM

Question

Descubrí recientemente el proyecto LLVM (low level virtual machine), y por lo que he escuchado Se puede usar para realizar análisis estáticos en un código fuente. Me gustaría saber si es posible extraer la llamada de función diferente a través del puntero de función (encontrar la función de llamada y la función llamada) en un programa.

Pude encontrar el tipo de información en el sitio web, por lo que sería muy útil si pudieras decirme si esa biblioteca ya existe en LLVM o si puedes indicarme la buena dirección sobre cómo construirla yo mismo (existente código fuente, referencia, tutorial, ejemplo ...).

EDIT:

Con mi análisis que en realidad desea extraer llamada a la función que llama/destinatario de la llamada. En el caso de un puntero a función, me gustaría devolver un conjunto de posibles destinatarios. tanto el llamador como el destinatario deben definirse en el código fuente (esto no incluye la función de un tercero en una biblioteca).

Answer 1

Deberías echar un vistazo a Elsa. Es relativamente fácil de extender y le permite analizar un AST con bastante facilidad. Maneja todo el análisis sintáctico, el lexing y la generación de AST y luego le permite recorrer el árbol utilizando el patrón Visitor.

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

Puede detectar declaraciones de funciones y probablemente detectar el uso del puntero a la función. Finalmente, puede verificar las declaraciones de los punteros de función y generar una lista de las funciones declaradas que podrían haberse llamado con ese puntero.

Answer 2

Creo que su pregunta es defectuosa. El título dice "Análisis del código fuente estático". Sin embargo, su razón subyacente parece ser la construcción de (parte de) un gráfico de llamadas que incluye llamadas a través de un puntero de función. La esencia de los punteros de función es que no puede conocer sus valores en tiempo de compilación, es decir, en el punto en el que realiza un análisis de código fuente estático. Considere este trozo de código:

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

análisis de código estático no puede decirle lo getFoo() devuelve en tiempo de ejecución, aunque se le puede decir que el resultado sea utilizado para contener una llamada de función.

Ahora, ¿qué valores podría devolver GetFoo()? Simplemente no puede decir esto en general (equivalente a resolver el problema de detención). Podrá adivinar algunos casos triviales. Por supuesto, el porcentaje imaginable aumentará dependiendo de cuánto esfuerzo esté dispuesto a invertir.

Answer 3

Creo que Clang (el analizador que forma parte de LLVM) está orientado a la detección de errores, lo que significa que el analizador intenta calcular los valores posibles de algunas expresiones (para reducir los falsos positivos) pero a veces se rinde (en este caso, no emitir alarma para evitar un diluvio de falsos positivos).

Si su programa es solo C, le recomiendo que eche un vistazo al Análisis del valor en Frama-C. Calcula superconjuntos de valores posibles para cualquier valor l en cada punto del programa, bajo algunas hipótesis que se explican en detalle en here. La complejidad en el programa analizado solo significa que los superconjuntos devueltos son más aproximados, pero aún contienen todos los valores de tiempo de ejecución posibles (siempre y cuando permanezca dentro de las hipótesis antes mencionadas).

EDITAR: si le interesan los posibles valores de los punteros a fin de dividir el programa analizado, debería echar un vistazo a los existentes dependencies y los cálculos de corte en Frama-C. El sitio web no tiene ningún buen ejemplo para cortar, aquí está one from a discussion on the mailing-list

Answer 4

En nuestro proyecto, realizamos análisis de código fuente estático convirtiendo el código de bytes LLVM en código C con la ayuda del programa llc que se envía con LLVM. Luego analizamos el código C con CIL (C Intermediate Language), pero para el lenguaje C hay muchas herramientas disponibles. El pitfail que el código generado por llc es AWFUL y adolece de una gran pérdida de precisión. Pero aún así, es una forma de hacerlo.

Editar: de hecho, yo no recomendaría a nadie que me gusta esto. Pero aún así, solo por un registro ...

Answer 5

El DMS Software Reengineering Toolkit proporciona varios tipos de control, data flow, and global points-to analyzers para grandes sistemas de código C, y construcciones llaman gráficos usando que los puntos a globales análisis (con los supuestos conservadores apropiados). Se puede encontrar más discusión y ejemplos de los análisis en el sitio web.

DMS ha sido probado en sistemas monolíticos de código C con 25 millones de líneas. (El gráfico de llamadas para este monstruo tenía 250,000 funciones en él).

Ingeniería de toda esta maquinaria a partir de C básicos ASTs y tablas de símbolos es una gran cantidad de trabajo; estado allí, hecho eso. No quiere hacer esto usted mismo si tiene algo más que ver con su vida, como implementar otras aplicaciones.