2010-09-09 12 views
11

He oído hablar un poco sobre el uso de demostradores de teoremas automatizados para intentar demostrar que las vulnerabilidades de seguridad no existen en un sistema de software. En general, esto es diabólicamente difícil de hacer.Uso de demostradores de teoremas para encontrar ataques

Mi pregunta es si alguien ha trabajado en el uso de herramientas similares a encontrar vulnerabilidades en los sistemas existentes o propuestos?


Eidt: Soy NO preguntando por demostrando que es un sistema de software seguro. Pregunto sobre la búsqueda de vulnerabilidades (idealmente desconocidas previamente) (o incluso clases de ellas). Estoy pensando (pero no) en un sombrero negro: describo la semántica formal del sistema, describo lo que quiero atacar y luego dejo que la computadora descubra qué cadena de acciones necesito usar para controlar su sistema.

+0

Creo que el cliente nativo de google podría facilitar esto; engañaron al requerir un compilador especial (que se compila en un subconjunto del conjunto de instrucciones de destino que hace que sea más fácil verificar el código). Consulte NaCl en http://www.chromium.org/nativeclient/reference/research-papers – sehe

Respuesta

4

Por lo tanto, al menos en algún sentido significativo, lo contrario de probar que algo es seguro es encontrar rutas de código para las cuales no lo es.

Probar Byron Cook's TERMINATOR project.

Y al menos dos videos en Channel9. Here's one of them

Su investigación es probable que sea un buen punto de partida para que pueda aprender sobre esta área de investigación extremadamente interesante.

Los proyectos tales como SpeC# y Typed-Assembly-Language también están relacionados. En su intento de trasladar la posibilidad de verificaciones de seguridad del tiempo de ejecución al tiempo de compilación, permiten al compilador detectar muchas rutas de código incorrectas como errores de compilación. Estrictamente, no ayudan a su intención declarada, pero la teoría que explotan podría ser útil para usted.

1

No está realmente relacionado con la demostración de teoremas, pero fuzz testing es una técnica común para encontrar vulnerabilidades de forma automática.

1

Está el L4 verified kernel que está tratando de hacer precisamente eso. Sin embargo, si nos fijamos en el historial de explotación, se encuentran patrones de ataque completamente nuevos y, a continuación, una gran cantidad de software escrito hasta ese punto es muy vulnerable a los ataques. Por ejemplo, las vulnerabilidades de cadenas de formato no se descubrieron hasta 1999. Hace aproximadamente un mes H.D. Moore lanzó DLL Hijacking y literalmente todo bajo windows is vulnerable.

No creo que sea posible probar que un software es seguro contra un ataque desconocido. Al menos no hasta que un teorema pueda descubrir tal ataque, y hasta donde sé, esto no ha sucedido.

+0

Por seguridad, creo que quiere decir que un conjunto de invariantes contienen cierto código que se ejecuta en hardware conocido. Si ese es el caso, creo que es posible demostrar que los invariantes se mantienen. Simplemente se vuelve más difícil a medida que el software crece, pero por lo que he leído, nos estamos volviendo más inteligentes. –

+0

Si eso no es cierto, estaría muy molesto. –

+0

@ uosɐs Permítanme poner esto de otra manera, escribí muchas hazañas a lo largo de los años y perdí la pista de la cantidad de números CVE que se me emitieron, y no creo que esto pueda probarse. Al menos no todavía. – rook

0

Negación: tiene poca o ninguna experiencia con demostradores automáticos

algunas observaciones

  • Cosas como la criptografía son rara vez "probado", simplemente se cree que son seguras. Si su programa usa algo así, solo será tan fuerte como la criptografía.
  • Los demostradores de teoremas no pueden analizar todo (o podrían resolver el problema de detención)
  • Tendría que definir muy claramente qué significa inseguro para el probador.Esto en sí mismo es un gran desafío
+0

No estoy 100% seguro de esto, pero estoy bastante seguro de que gran parte de la criptografía está probada hasta los axiomas (especialmente con el P! = NP propuesto), a menudo se aplica mal. Como observa en su tercer punto, es importante definir estrictamente para qué está contando el mecanismo; solo entonces puede probar que su uso es una aplicación correcta. –

+0

@ uosɐ gran parte del criptoanálisis implica reducir el número de rondas necesarias para la fuerza bruta de un cifrado/hash. Además, estoy bastante seguro de que "factorizar es difícil" no ha sido probado (fuente no confiable: http://en.wikipedia.org/wiki/Integer_factorization) – cobbal

+0

Una vez más, no soy un experto, pero para su consideración : La factorización de enteros no es el único mecanismo "duro" disponible. Además, el reciente P! = NP (revisión pendiente) demuestra que existen problemas difíciles. ¡Y creo que ha sido probado! ¡SI! existen problemas difíciles, esa factorización de enteros o algunos de sus amigos están en esa categoría. –

0

Sí. Muchos proyectos de demostración de teoremas muestran la calidad de su software al demostrar agujeros o defectos en el software. Para hacerlo relacionado con la seguridad, imagínese encontrar un agujero en un protocolo de seguridad. Doctor de Carlos Olarte la tesis de Ugo Montanari tiene uno de esos ejemplos.

Está en la aplicación. No es realmente el probador del teorema en sí mismo el que tiene algo que ver con la seguridad o el conocimiento especial del mismo.

2

Actualmente estoy escribiendo un analizador de PDF en Coq junto con otra persona. Si bien el objetivo en este caso es producir una pieza segura de código, hacer algo como esto definitivamente puede ayudar a encontrar errores lógicos fatales.

Una vez que se haya familiarizado con la herramienta, la mayoría de las pruebas se vuelven fáciles. Las pruebas más duras dan casos de prueba interesantes, que a veces pueden desencadenar errores en programas reales y existentes. (Y para encontrar errores, simplemente puede asumir teoremas como axiomas una vez que esté seguro de que no hay errores que encontrar, no es necesario probarlos).

Hace aproximadamente una polilla, llegamos a un problema para analizar archivos PDF con múltiples/anteriores Tablas XREF. No pudimos probar que el análisis finaliza. Pensando en esto, construí un PDF con looping/Prev Pointers in the Trailer (¿quién pensaría en eso? :-P), lo que naturalmente hizo que algunos espectadores giraran para siempre. (Más notablemente, casi cualquier visor basado en poppler en Ubuntu. Me hizo reír y la maldición de Gnome/evince-thumbnailer para comer toda mi CPU. Creo que lo arreglaron ahora, aunque.)


Usando Coq a encontrar errores de bajo nivel será difícil. Para probar algo, necesitas un modelo del comportamiento del programa. Para problemas de pila/pila, probablemente tendrá que modelar el nivel de CPU o al menos la ejecución de nivel C. Si bien es técnicamente posible, diría que esto no vale la pena el esfuerzo.

Usar SPLint for C o escribir un comprobador personalizado en el idioma de su elección debería ser más eficiente.

5

Sí, se ha hecho mucho trabajo en esta área. Los solucionadores de Satisfabilidad (SAT y SMT) se usan regularmente para encontrar vulnerabilidades de seguridad. Por ejemplo, en Microsoft, una herramienta llamada SAGE se usa para erradicar el búfer que sobrepasa los errores de Windows. SAGE usa el Z3 theorem prover como su verificador de satisfacibilidad. Si busca en Internet usando palabras clave como "smart fuzzing" o "white-box fuzzing", encontrará varios otros proyectos que utilizan inspectores de satisfacción para encontrar vulnerabilidades de seguridad. La idea de alto nivel es la siguiente: recopilar rutas de ejecución en su programa (que no logró hacer ejercicio, es decir, no encontró una entrada que hizo que el programa lo ejecute), convertir estas rutas en fórmulas matemáticas y alimenta estas fórmulas a un solucionador de satisfacciones. La idea es crear una fórmula que sea satisfactoria/factible solo si hay una entrada que hará que el programa ejecute la ruta dada. Si la fórmula producida es satisfactoria (es decir, factible), el solucionador de satisfacibilidad producirá una asignación y los valores de entrada deseados. Los fuzzers de caja blanca usan diferentes estrategias para seleccionar rutas de ejecución. El objetivo principal es encontrar una entrada que haga que el programa ejecute una ruta que provoque un bloqueo.

2

STACK y KINT utilizan solucionadores de restricciones para encontrar vulnerabilidades en muchos proyectos de OSS, como el kernel de linux y ffmpeg. Las páginas del proyecto apuntan a documentos y código.

+0

El fragmento de código en la p. 1 del documento de APILAMIENTO es un gran ejemplo de algo que se ve sólido como una roca, pero en realidad no lo es. También es un gran ejemplo para los autores de los estándares de lenguaje de cómo definir algo como "comportamiento indefinido" inesperadamente puede ser contraproducente. –

Cuestiones relacionadas