programacion - ¿Una implementación en C++ que detecta un comportamiento indefinido?
manual de programacion android pdf (10)
Al igual que una observación lateral, de acuerdo con la teoría de la computación, no se puede tener un programa que detecte todos los posibles comportamientos indefinidos.
Solo puede tener herramientas que usan heurística y detectar algunos casos particulares que siguen ciertos patrones. O puede, en ciertos casos, probar que un programa se comporta como lo desea. Pero no se puede detectar un comportamiento indefinido en general.
Editar
Si un programa no termina (cuelga, gira para siempre) en una entrada dada, entonces su salida no está definida.
Si acepta esta definición, entonces determinar si un programa finaliza es el conocido "Problema de detención", que se ha demostrado que es indecidible, es decir, no existe ningún programa (Máquina de Turing, Programa C, Programa C ++, Programa Pascal, en cualquier lenguaje) que pueda resolver este problema en general.
En pocas palabras: no existe ningún programa P que pueda tomar como entrada cualquier programa Q y datos de entrada I e imprimir como salida VERDADERA si Q (I) termina, o si no imprime FALSO si Q (I) no termina.
Para obtener más información, puede consultar http://en.wikipedia.org/wiki/Halting_problem .
Una gran cantidad de operaciones en C ++ resultan en un comportamiento indefinido, donde la especificación es completamente muda sobre cuál debe ser el comportamiento del programa y permite que ocurra cualquier cosa. Debido a esto, hay todo tipo de casos en que las personas tienen código que se compila en modo de depuración pero no de liberación, o que funciona hasta que se realiza un cambio aparentemente no relacionado, o que funciona en una máquina pero no en otra, etc.
Mi pregunta es si hay una utilidad que analiza la ejecución del código C ++ y señala todas las instancias en las que el programa invoca un comportamiento indefinido. Si bien es bueno tener herramientas como valgrind y las implementaciones comprobadas de STL, estas no son tan sólidas como lo que estoy pensando - valgrind puede tener falsos negativos si destruye la memoria que aún tiene asignada, por ejemplo, y verifica las implementaciones de STL no detectará la eliminación a través de un puntero de clase base.
¿Esta herramienta existe? ¿O sería útil tenerlo en absoluto?
EDITAR : Soy consciente de que, en general, es indecidible comprobar estáticamente si un programa C ++ puede alguna vez ejecutar algo que tiene un comportamiento indefinido. Sin embargo, es posible determinar si una ejecución específica de C ++ produjo un comportamiento indefinido. Una forma de hacerlo sería crear un intérprete de C ++ que pase por el código de acuerdo con las definiciones establecidas en la especificación, en cada punto que determina si el código tiene un comportamiento indefinido o no. Esto no detectará un comportamiento indefinido que no ocurre en una ejecución particular del programa, pero encontrará cualquier comportamiento indefinido que realmente se manifieste en el programa. Esto se relaciona con la forma en que es reconocible por Turing determinar si una TM acepta alguna entrada, incluso si todavía es indecidible en general.
¡Gracias!
Clang tiene -fsanitize que captan diversas formas de comportamiento indefinido. Su objetivo final es poder detectar todo el comportamiento indefinido del lenguaje central de C ++, pero en este momento faltan algunas formas complicadas de comportamiento indefinido.
Para un conjunto decente de desinfectantes, intente:
clang++ -fsanitize=undefined,address
-fsanitize=address comprobaciones de -fsanitize=address para el uso de punteros incorrectos (que no apuntan a la memoria válida), y -fsanitize=undefined habilita un conjunto de comprobaciones UB livianas (desbordamiento de enteros, cambios incorrectos, punteros desalineados, ...).
-fsanitize=memory (para detectar lecturas de memoria no inicializadas) y -fsanitize=thread (para detectar carreras de datos) también son útiles, pero ninguno de estos se puede combinar con -fsanitize=address ni entre ellos porque los tres tienen un impacto invasivo en el espacio de direcciones del programa.
El compilador clang puede detectar algunos comportamientos indefinidos y advertir en contra de ellos. Probablemente no sea tan completo como desee, pero definitivamente es un buen comienzo.
El comportamiento indefinido no está definido . Lo mejor que puede hacer es ajustarse al estándar de forma pedante, como han sugerido otros, sin embargo, no puede probar lo que no está definido, porque no sabe de qué se trata. Si supiera lo que era y los estándares lo especificaran, no estaría indefinido.
Sin embargo, si por alguna razón realmente confía en lo que dice el estándar no definido , y resulta en un resultado particular, entonces puede optar por definirlo y escribir algunas pruebas unitarias para confirmar que para su compilación particular, es definido. Sin embargo, es mucho mejor evitar comportamientos indefinidos siempre que sea posible.
Es posible que desee leer sobre SAFECode .
Este es un proyecto de investigación de la Universidad de Illinois, el objetivo se indica en la página principal (vinculado anteriormente):
El propósito del proyecto SAFECode es habilitar la seguridad del programa sin recolección de basura y con un mínimo de verificaciones en tiempo de ejecución usando análisis estáticos cuando sea posible y verificaciones de tiempo de ejecución cuando sea necesario. SAFECode define una representación de código con restricciones semánticas mínimas diseñadas para permitir la aplicación estática de seguridad, utilizando técnicas agresivas de compilación desarrolladas en este proyecto.
Lo que es realmente interesante para mí es la eliminación de los controles de tiempo de ejecución cada vez que se puede probar que el programa es correcto estáticamente, por ejemplo:
int array[N];
for (i = 0; i != N; ++i) { array[i] = 0; }
No debe incurrir en más gastos generales que la versión normal.
En una forma más ligera, Clang tiene algunas garantías sobre el comportamiento indefinido también, por lo que recuerdo, pero no puedo tenerlo en mis manos ...
Esta es una gran pregunta, pero permítanme dar una idea de por qué creo que podría ser imposible (o al menos muy difícil) en general.
Presumiblemente, tal implementación sería casi un intérprete de C ++, o al menos un compilador de algo más parecido a Lisp o Java. Tendría que mantener datos adicionales para cada puntero para asegurarse de que no realizó la aritmética fuera de una matriz o desreferencia de algo que ya fue liberado o lo que sea.
Ahora, considere el siguiente código:
int *p = new int;
delete p;
int *q = new int;
if (p == q)
*p = 17;
¿Es el comportamiento *p = 17 indefinido? Por un lado, desreferencia p después de haber sido liberado. Por otro lado, desreferenciar q es correcto p == q ...
Pero ese no es realmente el punto. El punto es que si el if evalúa como verdadero depende de los detalles de la implementación del montón, que puede variar desde la implementación hasta la implementación. Así que reemplace *p = 17 por algún comportamiento real no definido, y usted tiene un programa que bien podría explotar en un compilador normal, pero funcionar bien en su hipotético "detector UB". (Una implementación típica de C ++ utilizará una lista libre de LIFO, por lo que los indicadores tienen buenas posibilidades de ser iguales. Un hipotético "detector UB" podría funcionar más como un lenguaje basura para detectar problemas de uso después de la liberación).
Dicho de otro modo, sospecho que la existencia de un comportamiento simplemente definido por la implementación hace imposible escribir un "detector UB" que funcione para todos los programas.
Dicho esto, un proyecto para crear un "compilador de C ++ uber-strict" sería muy interesante. Avísame si quieres comenzar uno. :-)
Lamentablemente, no conozco ninguna de esas herramientas. Normalmente, UB se define como tal precisamente porque sería difícil o imposible para un compilador diagnosticarlo en todos los casos.
De hecho, su mejor herramienta probablemente sean las advertencias del compilador: a menudo advierten sobre los elementos de tipo UB (por ejemplo, el destructor no virtual en las clases base, el abuso de las reglas de alias estrictos, etc.).
La revisión del código también puede ayudar a detectar casos en los que se confía en UB.
Luego debes confiar en valgrind para capturar los casos restantes.
Usando g++
-Wall -Werror -pedantic-error
(preferiblemente con un argumento -std apropiado también) recogerá bastantes casos de UB
Las cosas que -Wall te consigue incluyen:
-pedante
Emita todas las advertencias exigidas por los estrictos ISO C e ISO C ++; rechaza todos los programas que usan extensiones prohibidas, y algunos otros programas que no siguen ISO C y ISO C ++. Para ISO C, sigue la versión del estándar ISO C especificado por cualquier opción -std utilizada.-Winit-self (C, C ++, Objective-C y Objective-C ++ solamente)
Advierta sobre variables no inicializadas que se inicializan consigo mismas. Tenga en cuenta que esta opción solo se puede usar con la opción -Winicializada, que a su vez solo funciona con -O1 y superior.-Inicializado
Advierta si se usa una variable automática sin inicializarla primero o si una variable puede ser arrastrada por una llamada "setjmp".
y varias cosas no permitidas que puede hacer con los especificadores para printf y scanf funciones de la familia.
John Regehr en Finding Undefined Behavior Bugs by Finding Dead Code señala una herramienta llamada STACK y cito del sitio ( énfasis mío ):
Optimización: código inestable (código inestable para abreviar) es una clase emergente de errores de software: código que inesperadamente se elimina mediante optimizaciones del compilador debido a un comportamiento indefinido en el programa. El código inestable está presente en muchos sistemas, incluidos el kernel de Linux y el servidor de la base de datos de Postgres. Las consecuencias del código inestable van desde la funcionalidad incorrecta hasta las comprobaciones de seguridad faltantes.
STACK es un comprobador estático que detecta código inestable en programas C / C ++ . La aplicación de STACK a los sistemas ampliamente utilizados ha descubierto 160 nuevos errores que han sido confirmados y reparados por los desarrolladores.
También en C ++ 11 para el caso de variables y funciones constexpr , el comportamiento indefinido debe capturarse en tiempo de compilación .
También tenemos gcc ubsan :
Recientemente, GCC (versión 4.9) obtuvo Undefined Behavior Sanitizer (ubsan), un comprobador de tiempo de ejecución para los lenguajes C y C ++. Para verificar su programa con ubsan, compile y vincule el programa con la opción -fsanitize = undefined. Dichos binarios instrumentados deben ser ejecutados; si ubsan detecta algún problema, emite un mensaje de "error de tiempo de ejecución:", y en la mayoría de los casos continúa ejecutando el programa.
y Clang Static Analyzer que incluye muchas comprobaciones de comportamiento indefinido. Por ejemplo, -fsanitize checks que incluye -fsanitize=undefined :
-fsanitize = undefined: comprobador de comportamiento indefinido rápido y compatible. Permite las comprobaciones de comportamiento indefinido que tienen un costo de tiempo de ejecución pequeño y no tienen impacto en el diseño de espacio de direcciones o ABI. Esto incluye todas las comprobaciones enumeradas a continuación distintas de desbordamiento de enteros sin signo.
y para C podemos ver su artículo Es hora de ponerse serio sobre la explotación del comportamiento indefinido que dice:
[..] Confieso que personalmente no tengo la agitación necesaria para abarrotar GCC o LLVM a través de las mejores comprobaciones dinámicas de comportamiento indefinido disponibles: KCC y Frama-C . [...]
Aquí hay un enlace a kcc y cito:
[...] Si intentas ejecutar un programa que no está definido (o uno para el que nos falta semántica), el programa se quedará atascado. El mensaje debe decirle dónde se quedó y puede dar una pista de por qué. Si desea ayuda para descifrar el resultado, o ayuda a comprender por qué el programa no está definido, envíenos su archivo .kdump. [...]
y aquí hay un enlace a Frama-C , un article donde se describe el primer uso de Frama-C como intérprete C y una addendum al artículo.