c++ - clang

Instrumentación de códigos C/C++ utilizando LLVM

Question

Acabo de leer sobre el proyecto LLVM y que podría usarse para hacer análisis estáticos en códigos C / C ++ utilizando el analizador Clang que es la parte frontal de LLVM. Quería saber si es posible extraer todos los accesos a la memoria (variables, tanto locales como globales) en el código fuente utilizando LLVM.

¿Hay alguna biblioteca incorporada presente en LLVM que pueda usar para extraer esta información? De lo contrario, sugiérame cómo escribir funciones para hacer lo mismo (código fuente existente, referencia, tutorial, ejemplo ...). Lo que he pensado es que primero convertiría el código fuente en LLVM bc y luego lo instrumentaría para hacer el análisis, pero no sé exactamente cómo hacerlo.

Intenté averiguar qué IR debería usar para mi propósito (Clang''s Abstract Syntax Tree (AST) o LLVM SSA Intermediate Representation (IR)), pero realmente no pude averiguar cuál usar. Esto es lo que estoy tratando de hacer. Dado cualquier programa C / C ++ (como el que se muestra a continuación), estoy tratando de insertar llamadas a alguna función, antes y después de cada instrucción que lee / escribe en / desde la memoria. Por ejemplo, considere el siguiente programa de C ++ (Account.cpp)

#include <stdio.h>
class Account {
int balance;
public:
Account(int b) {
balance = b;
}
int read() {
int r;
r = balance;
return r;
}
void deposit(int n) {
balance = balance + n;
}
void withdraw(int n) {
int r = read();
balance = r - n;
}
};
int main () {
Account* a = new Account(10);
a->deposit(1);
a->withdraw(2);
delete a;
}

Así que después de la instrumentación mi programa debería verse como:

#include <stdio.h>
class Account {
int balance;
public:
Account(int b) {
balance = b;
}
int read() {
int r;
foo();
r = balance;
foo();
return r;
}
void deposit(int n) {
foo();
balance = balance + n;
foo();
}
void withdraw(int n) {
foo();
int r = read();
foo();
foo();
balance = r - n;
foo();
}
};
int main () {
Account* a = new Account(10);
a->deposit(1);
a->withdraw(2);
delete a;
}

donde foo () puede ser cualquier función como obtener la hora actual del sistema o incrementar un contador ... así sucesivamente. Entiendo que para insertar una función como la anterior, primero tendré que obtener el IR y luego ejecutar un pase de instrumentación en el IR que insertará dichas llamadas en el IR, pero no sé realmente cómo lograrlo. Por favor, sugiérame con ejemplos cómo hacerlo.

También entiendo que una vez que compile el programa en el IR, sería muy difícil obtener un mapeo 1: 1 entre mi programa original y el IR instrumentado. Entonces, ¿es posible reflejar los cambios realizados en el IR (debido a la instrumentación) en el programa original?

Para comenzar con el pase de LLVM y cómo hacer uno por mi cuenta, miré un ejemplo de un pase que agrega controles de tiempo de ejecución a las cargas y almacenes de LLVM IR, el pase de instrumentación de carga / almacenamiento del SAFECode ( http://llvm.org/viewvc/llvm-project/safecode/trunk/include/safecode/LoadStoreChecks.h?view=markup y http://llvm.org/viewvc/llvm-project/safecode/trunk/lib/InsertPoolChecks/LoadStoreChecks.cpp?view=markup ). Pero no pude averiguar cómo ejecutar este pase. Dame los pasos para ejecutar este pase en algún programa, como el Account.cpp anterior.

Answer 1

En primer lugar, debe decidir si desea trabajar con clang o LLVM. Ambos operan en estructuras de datos muy diferentes que tienen ventajas y desventajas.

A partir de su breve descripción de su problema, le recomendaré obtener pases de optimización en LLVM. Trabajar con el IR hará que sea mucho más fácil de desinfectar, analizar e inyectar código porque para eso fue diseñado. El inconveniente es que su proyecto dependerá de LLVM, lo que puede o no ser un problema para usted. Puede generar el resultado utilizando el backend de C, pero eso no será utilizable por un humano.

Otro inconveniente importante cuando se trabaja con pases de optimización es que también pierde todos los símbolos del código fuente original. Incluso si la clase Value (más sobre esto más adelante) tiene un método getName , nunca debe confiar en que contenga algo significativo. Está destinado a ayudarte a depurar tus pases y nada más.

También tendrá que tener una comprensión básica de los compiladores. Por ejemplo, es un poco requisito conocer los bloques básicos y el formulario de asignación única estática . Afortunadamente, no son conceptos muy difíciles de aprender o entender (los artículos de Wikipedia deberían ser adecuados).

Antes de que pueda comenzar a codificar, primero debe leer un poco, así que aquí hay algunos enlaces para comenzar:

• Descripción general de la arquitectura : Una descripción general rápida de la arquitectura de LLVM. Le dará una buena idea de con qué está trabajando y si LLVM es la herramienta adecuada para usted.

• Jefe de documentación : donde puede encontrar todos los enlaces a continuación y más. Refiérase a esto si me perdí algo.

• Referencia de IR de LLVM : Esta es la descripción completa de LLVM IR, que es lo que estará manipulando. El lenguaje es relativamente simple por lo que no hay mucho que aprender.

• Manual del programador : una descripción general rápida de las cosas básicas que debe saber al trabajar con LLVM.

• llvm.org/docs/WritingAnLLVMPass.html : Todo lo que necesita saber para escribir pases de análisis o transformación.

• Pases de LLVM : una lista completa de todos los pases proporcionados por LLVM que puede y debe usar. Esto realmente puede ayudar a limpiar el código y facilitar el análisis. Por ejemplo, cuando se trabaja con bucles, las lcssa , simplify-loop e indvar salvarán su vida.

• Árbol de herencia de valor : esta es la página doxygen para la clase de valor. El bit importante aquí es el árbol de herencia que puede seguir para obtener la documentación de todas las instrucciones definidas en la página de referencia de IR. Simplemente ignora la monstruosidad impía que ellos llaman el diagrama de colaboración.

• Árbol de herencia de tipos : igual que el anterior pero para los tipos.

Una vez que entiendes todo eso, entonces es pastel. ¿Para encontrar accesos de memoria? Buscar instrucciones para store y load . ¿Instrumento? Simplemente cree lo que necesita usando la subclase adecuada de la clase Value e insértela antes o después de la instrucción de almacenamiento y carga. Debido a que tu pregunta es un poco demasiado amplia, realmente no puedo ayudarte más que esto. (Ver corrección abajo)

Por cierto, tuve que hacer algo similar hace unas semanas. En aproximadamente 2-3 semanas, pude aprender todo lo que necesitaba sobre LLVM, crear un pase de análisis para encontrar accesos a la memoria (y más) dentro de un bucle e instrumentarlos con un pase de transformación que creé. No hubo algoritmos sofisticados (excepto los proporcionados por LLVM) y todo fue bastante sencillo. La moraleja de la historia es que LLVM es fácil de aprender y trabajar.

Corrección : Cometí un error cuando dije que todo lo que tienes que hacer es buscar las instrucciones de load y store .

Las instrucciones de load y store solo darán accesos que se hacen al montón usando punteros. Para obtener todos los accesos a la memoria, también debe observar los valores que pueden representar una ubicación de memoria en la pila. Si el valor se escribe en la pila o se almacena en un registro, se determina durante la fase de asignación del registro que se produce en una fase de optimización del servidor. Lo que significa que depende de la plataforma y no debe ser invocado.

Ahora, a menos que proporcione más información sobre qué tipo de accesos de memoria está buscando, en qué contexto y cómo pretende instrumentarlos, no puedo ayudarlo mucho más que esto.

Answer 2

Ya que no hay respuesta a su pregunta después de dos días, le ofreceré una que sea ligeramente pero no completamente fuera de tema.

Como alternativa a LLVM, para el análisis estático de programas en C, puede considerar escribir un complemento de Frama-C .

El complemento existente que calcula una lista de entradas para una función en C debe visitar cada valor de l en el cuerpo de la función. Esto se implementa en el archivo src / inout / inputs.ml. La implementación es corta (la complejidad se encuentra en otros complementos que proporcionan sus resultados a este, por ejemplo, la resolución de punteros) y se puede utilizar como un esqueleto para su propio complemento.

El marco proporciona un visitante para el árbol de sintaxis abstracta. Para hacer algo especial para valores, simplemente defina el método correspondiente. El corazón del complemento de entradas es la definición del método:

method vlval lv = ...

Aquí hay un ejemplo de lo que hace el complemento de entradas:

int a, b, c, d, *p;
main(){
p = &a;
b = c + *p;
}

Las entradas de main() se calculan así:

$ frama-c -input t.c
...
[inout] Inputs for function main:
a; c; p;

Puede encontrar más información sobre cómo escribir complementos de Frama-C en general here .