¿Cómo podemos estar seguros de que los componentes inferiores de la programación de computadoras, como compiladores, ensambladores, instrucciones de máquina, etc., son perfectos?

57

Como nos estamos volviendo cada vez más dependientes de la informática, incluidas las tareas muy críticas de la vida cotidiana, me preguntaba cómo se prueban esos componentes vitales.

Más técnicamente, ¿cómo se prueban los compiladores y ensambladores? (¡Supongo que esto se relaciona con el problema de detención !)

Sudip Bhandari
fuente
36
Es posible que desee comenzar su investigación con el "Ken Thompson Hack" Vea Reflexiones sobre Confianza Confiada
Bryan Oakley
77
Aquí hay un ejemplo de un compilador para el cual hay una prueba de corrección: compcert.inria.fr/doc/index.html
Giorgio
8
La mayoría de los compiladores / enlazadores / ensambladores se prueban más profundamente al usarlos en muchas circunstancias diferentes. Para encontrar errores, no hay nada más que tener millones de usuarios usando su compilador.
Bart van Ingen Schenau
3
y agregue el sistema operativo a la lista también.
Erik Eidt

Respuestas:

104

No puedes estar seguro, pero solo asumes que lo son, hasta que descubres que no lo son. Ha habido muchos errores en compiladores y hardware a lo largo de los años.

La forma en que se prueban, por ejemplo, un compilador, es que se definen de forma muy estrecha y rígida, se escriben cuidadosamente y luego se prueban con un enorme conjunto de pruebas para verificar la corrección. Agregue a eso la amplia base de usuarios de un compilador, y se detectarán e informarán más errores. Una aplicación de programación de citas con el dentista, comparativamente, tiene muchos menos usuarios y aún menos capaces de detectar defectos.

SQLite consta de aproximadamente 73k líneas de código, mientras que su conjunto de pruebas consta de aproximadamente 91378k líneas de código, más de 1250 veces más que el propio SQLite. Espero que los compiladores y otras herramientas centrales tengan proporciones similares. Los procesadores de hoy están diseñados esencialmente con software, utilizando lenguajes de descripción de hardware como Verilog o VHDL, y también tienen pruebas de software ejecutadas en ellos, así como pines de E / S especializados para ejecutar autocomprobaciones en el punto de fabricación.

En última instancia, es un juego de probabilidad, y las pruebas repetidas y de cobertura amplia le permiten reducir la probabilidad de defectos a un nivel aceptablemente bajo, lo mismo que otro proyecto de software.

whatsisname
fuente
77
A menudo me he preguntado la misma pregunta que el OP, pero con respecto a los DBMS. Diste un gran ejemplo que lo respondió dentro del contexto de SQLite. ¡Gracias!
Brandon
77
+1 pero de alguna manera dudo que "los compiladores y otras herramientas centrales tengan proporciones similares".
Mehrdad
55
Tenga en cuenta que (1) SQLite tiene en realidad dos conjuntos de pruebas, con redundancia no trivial entre los dos y (2) todavía hay errores encontrados en SQLite a pesar de esto.
Matthieu M.
77
He tenido la impresión de que SQLite es una de las piezas de software más "ampliamente probadas" (en términos de líneas de código de prueba / líneas de código operativo) disponibles para uso general, más aún que muchos compiladores. Por lo menos, un compilador con todas las funciones es una enorme pieza de software, y no puedo imaginar que tenga mil veces esa cantidad de código de prueba. (Según los informes, GCC tiene hasta 14,5 millones de líneas. Parece poco probable que la colección del compilador propiamente dicha sea de solo 14k LOC, o que tengan una base de código de prueba de 14 mil millones de líneas a un lado! :-P)
David Z
2
@DavidZ: Es, sin duda, es el único proyecto que conozco que usa pruebas OOM extensas, por ejemplo (usan un inyector de fallas para la prueba y las repiten una y otra vez fallando en la primera, luego en la segunda asignación ... hasta la prueba completa es ejecutado).
Matthieu M.
46

En términos simples:

  1. No se puede.
  2. Los compiladores e intérpretes se prueban en unidades como cualquier otro software (profesional).
  3. Una prueba exitosa no significa que un programa esté libre de errores, solo significa que no se detectaron errores.
  4. Una amplia base de usuarios que utiliza el compilador durante mucho tiempo es un buen indicador de que tiene muy pocos errores, porque los usuarios suelen probar casos en los que los diseñadores no pensaron.
  5. Ser de código abierto también es un buen indicador. "Dadas suficientes globos oculares, todos los errores son superficiales ... Dada una base beta-tester y co-desarrolladora lo suficientemente grande, casi todos los problemas se caracterizarán rápidamente y la solución será obvia para alguien". . Un compilador de código cerrado podría tener errores que surgen en momentos muy específicos o que generan un código de máquina menos que óptimo y la compañía detrás de él simplemente no puede revelar su existencia y darle una prioridad muy baja en la hoja de ruta del producto.

Línea de fondo:

Yo diría que vaya a OOP ( O ld, O pen y P opular). Acabo de inventar ese acrónimo.

Tulains Córdova
fuente
19
+1 Por inventar otro TLA (acrónimo de tres letras): el mundo todavía no tiene suficientes.
s1lv3r
34
Además, OOP no tenía ningún significado en la programación de computadoras todavía. ¡Así que KTT (felicitaciones a ti)!
Pierre Arlaud
15
El comentario de Pierre es una broma @Dannnno.
yannis
19
Alternativamente, podría P opular, O ld y O pen. ;) En realidad, así es como los clasificaría en orden de importancia.
jpmc26
23
@ jpmc26 Me gustaría ir con Practical, Old, Open y Popular. En cuanto a las siglas ...
StupidOne
24

Son tortugas hasta el fondo.

Nada es seguro. No tiene más remedio que conformarse con las calificaciones de confianza.

Puede pensarlo como una pila: Matemáticas> Física> Hardware> Firmware> Sistema operativo> Ensamblador / Compilador / etc.

En cada nivel tiene pruebas que puede realizar para mejorar sus índices de confianza. Algunas de estas pruebas tienen la calidad de pruebas formales, algunas se basan en la observación, la mayoría son una combinación de ambas.

La parte difícil es desentrañar la recursividad en algunas de estas pruebas porque usamos programas para hacer pruebas y análisis de observación ahora donde se ha vuelto demasiado difícil hacerlo a mano.

Finalmente, la respuesta es que intentas todo lo que se te ocurre. Análisis estático, fuzzing, simulación, ejecución con entradas extremas seleccionadas a propósito o entradas aleatorias, ejecución / mapeo de cada ruta de control, pruebas formales, etc. Básicamente, su objetivo en las pruebas siempre debe ser hacer todo lo posible para demostrar que su producto (por ejemplo, teoría / chip / programa) no funciona según lo previsto. Si hace un esfuerzo genuino y aún falla, puede mejorar su índice de confianza en la corrección de su producto.

Las pruebas son, en el mejor de los casos, un proceso de semidecisión, lo que significa que dado que hay un error, eventualmente lo encontrará, pero nunca puede estar seguro de haberlo encontrado a todos. Incluso con el software verificado formalmente, usted sigue confiando en la física, las herramientas utilizadas para hacer las pruebas formales, y que lo que probó es necesario y suficiente para que su programa haga lo que (a menudo subjetivamente) está "previsto". Eso sin mencionar todos los otros componentes que está utilizando que no tienen pruebas formales.

voutasaurus
fuente
17

Esta es una pregunta "peligrosa" para los nuevos desarrolladores, ya que comenzarán a culpar a sus herramientas en lugar de su código (estado allí, hecho eso, visto que muchos lo hacen). Aunque hay errores en los compiladores, entornos de tiempo de ejecución, sistema operativo, etc., los desarrolladores deben ser realistas y recordar que, hasta que haya pruebas y pruebas unitarias que demuestren lo contrario, el error está en su código .

En más de 25 años de programación en su mayoría en C, C ++ y Java, he encontrado:

  • dos errores debido a un error del compilador (gcc y SunOS C)
  • aproximadamente una vez al año o dos, un error debido a un problema de Java JVM (generalmente relacionado con el consumo de memoria / recolección de basura)
  • aproximadamente una vez al mes o dos, un error en una biblioteca, que con frecuencia se corrige utilizando la última versión o volviendo a la versión anterior de la biblioteca

Todos los otros errores están directamente relacionados con un error o, más frecuentemente, con la falta de comprensión de cómo funciona una biblioteca. A veces, lo que parece ser un error se debe a una incompatibilidad, por ejemplo, cómo cambió la estructura de clases de Java que rompió algunas bibliotecas AOP.

Ed Griebel
fuente
Tengo curiosidad, ¿qué años para qué idiomas? En los días de EGCS antes de que C ++ se estandarizara correctamente, los errores del compilador no eran tan difíciles de encontrar ...
Charles Duffy
3
Cuanto más oscuro sea el compilador, la CPU o el lenguaje, más fácil será encontrar un error en los compiladores (antes que otra persona), por lo que encontrar 2 en GCC C es bueno :)
Surt
1
Resulta que perdí alrededor de un mes presumiendo que el problema que tenía estaba en mis scripts gdb, o en mi comprensión de lo que estaba examinando. Finalmente, sospeché, simplifiqué mi caso de prueba y encontré una falla de diseño en una biblioteca (libkvm), lo que hizo que un depurador de kernel no pudiera acceder a ciertas direcciones desde un volcado de núcleo. Es decir, YMMV, y estoy más feliz cuando encuentro un nuevo error en el código de mi parte, especialmente algo que estoy usando en lugar de desarrollar.
Arlie Stephens
Por supuesto, no fue un error del compilador , ni siquiera una de las bibliotecas más utilizadas. Y la verdad es que no encuentro errores en aquellos con ninguna frecuencia.
Arlie Stephens el
@ArlieStephens Hay una lección allí: simplificar su caso de prueba es algo que debe hacer desde el principio cuando no encuentra un problema. Independientemente de si el problema es suyo o de otro código, eso lo ayudará a reducirlo. A menudo, si el problema está en el otro código, esto resultará en "evidencia y pruebas unitarias que lo demuestran".
jpmc26
8

Creo que un punto interesante aquí es que la gran mayoría de las licencias de software comercial (y de hecho software de código abierto) especifican específicamente que no puede confiar en el software.

EL SOFTWARE SE PROPORCIONA "TAL CUAL", SIN GARANTÍA DE NINGÚN TIPO, EXPLÍCITA O IMPLÍCITA, INCLUYENDO PERO SIN LIMITARSE A LAS GARANTÍAS DE COMERCIABILIDAD, APTITUD PARA UN PROPÓSITO Y NO INFRACCIÓN PARTICULARES.

Del acuerdo de licencia de Microsoft Word

. Excepto por la Garantía limitada y en la medida máxima permitida por la ley aplicable, Microsoft y sus proveedores proporcionan el Software y los servicios de soporte (si los hay) TAL CUAL Y CON TODAS LAS FALLAS, y por la presente renuncian a todas las demás garantías y condiciones, ya sean expresas, implícitas o estatutario, que incluye, entre otros, garantías implícitas (si las hay), deberes o condiciones de comerciabilidad, idoneidad para un propósito particular, confiabilidad o disponibilidad, precisión o integridad de las respuestas, de los resultados, del esfuerzo profesional, de falta de virus y falta de negligencia, todo con respecto al Software, y la provisión o incumplimiento de proporcionar soporte u otros servicios, información, software y contenido relacionado a través del Software o que surjan del uso del Software .

En esencia, esta oración en la licencia de casi todos los programas que usa específicamente le dice que no puede confiar en el software y mucho menos en el compilador utilizado.

El software es como una teoría científica, se considera que funciona como se especifica hasta que no funciona.

Toby Allen
fuente
+1 por señalar que las mismas licencias indican que ningún software es perfecto.
Tulains Córdova
3
Me complació observar una desviación de esta práctica en ViaVoice para Mac de IBM. En lugar de la costumbre "si no funciona, qué mal", en realidad dijeron algo como "El software está garantizado para funcionar como se especifica".
WGroleau
1
Una traducción en lenguaje sencillo de esta frase de garantía en particular es: "Esto podría ser una pieza de software, o podría ser un pedazo de mierda. Podría funcionar. Podría no funcionar. Incluso si funciona, podría no funcionar". haz lo que quieras Oh, por cierto, podríamos haberle robado trozos de él a otra persona. Lástima. Tenemos tu dinero y lo hemos usado para contratar a muchos abogados. ¡JUEGO! ¡ENCENDIDO! Nyah-nyah -nyah-nyah-nyaaah-naah! ". :-)
Bob Jarvis
2
@BobJarvis: Mi declaración de garantía favorita, utilizada en algún software de código abierto (como nmap IIRC), es "Si se rompe, puedes conservar ambas piezas".
Peter Cordes
Esta declaración es omnipresente en el software de código abierto y en muchos programas de código cerrado sin costo. No aparece en la mayoría de las licencias comerciales de software de pago.
jwg
2

Como escritor compilador de un lenguaje matemático *, desde mi experiencia puedo decir en teoría que tú no puedes. Y algunos de los errores solo dan resultados incorrectos como (de mi lista de vergüenza) calcular 6/3*2desde la derecha 6/(3*2)y generar 1 sin fallar ni dar errores de compilación sin sentido.

Pero en mi humilde opinión, muchos compiladores no tienen tantos errores como otro software porque:

  • Escribir pruebas unitarias es fácil. Cada declaración es una unidad y puede escribir pruebas tan simples como:test_unit("2+(-2)*(-2+1)*3+1",9);
  • Un programa es una combinación de declaraciones y para que cualquier programa produzca el resultado correcto, cada declaración individual debe dar el resultado correcto (principalmente). Por lo tanto, es muy poco probable que tenga errores mientras el programa da el resultado correcto.
  • A medida que el tamaño y la cantidad de programas escritos aumentan, la probabilidad de detectar errores aumenta dramáticamente.

Para ensambladores, instrucciones de máquina, etc., lo anterior también es válido; Por otro lado, la verificación y validación en el diseño y la producción de chips tienen procesos mucho más estrictos, ya que es un gran negocio: la automatización del diseño electrónico .

Antes de pasar a producción, cada CPU debe probarse rigurosamente porque cada error cuesta casi un par de millones de dólares: existen enormes costos de producción no recurrentes en la producción de chips. Por lo tanto, las empresas gastan mucho dinero y escriben mucho código de simulación para su diseño antes de comenzar la producción, aunque esto no ofrece una garantía del 100%, por ejemplo: el error Pentium FDIV.

En resumen, es muy poco probable que tenga errores graves en los compiladores, códigos de máquina, etc.

Mi humilde lenguaje matemático *

Gorkem
fuente
Intel pone a prueba sus CPUs ejecutando secuencias de instrucciones aleatorias y comparándolas con un modelo de software, entre otras cosas: tweakers.net/reviews/740/4/… . Esta es la razón por la que a menudo se ven erratas muy oscuras publicadas, para alguna combinación de instrucciones realmente poco probable en un modo inusual.
Peter Cordes
0

¿Perfecto? Ellos no están. Recientemente instalé algunas "actualizaciones", y pasaron meses (y varias secciones de código reprogramadas) más tarde antes de que mi sitio ASP.NET volviera a funcionar correctamente, debido a cambios inexplicables en cómo funcionaban o fallaban varias cosas básicas.

Sin embargo, son probados y luego utilizados por muchas personas muy inteligentes orientadas a los detalles, que tienden a notar, informar y corregir la mayoría de las cosas. Stack Exchange es un gran ejemplo (y mejora) de cómo todas las personas que usan esas herramientas ayudan a probar y analizar cómo funcionan estas herramientas increíblemente complejas y de bajo nivel, al menos en lo que respecta al uso práctico.

Pero perfecto, no. Aunque también puede ver a las personas en Stack Exchange obteniendo una visión impresionante de los detalles de rendimiento y el cumplimiento de estándares y peculiaridades, siempre hay fallas e imperfecciones, especialmente cuando diferentes personas tienen diferentes opiniones sobre lo que es una falla.

Dronz
fuente
-1

Para demostrar que los sistemas subyacentes son perfectos

a) Necesidad de probar que son impecables

  1. Prueba matemática
  2. Solo realistamente posible para programas triviales

b) Hacer una prueba exhaustiva

  1. Solo es posible para programas triviales y algunos programas simples
  2. Tan pronto como un elemento de temporización ingresa a la prueba, no es posible hacer una prueba exhaustiva ya que el tiempo puede dividirse indefinidamente.
  3. Más allá de los programas triviales, las posibles opciones de ejecución explotan exponencialmente.

En las pruebas de software, la prueba exhaustiva solo se usa en pruebas unitarias de algunas funciones simples.

Ejemplo: si desea probar una entrada utf-8 de 8 caracteres en algún campo, elige cortar la entrada a 8 veces la longitud máxima 6 de utf-8 en bytes, lo que da 8 * 6 = 48 bytes para tener realmente un cantidades finitas de posibilidades.

Ahora podría pensar que solo necesita probar los 1.112.064 puntos de código válidos de cada uno de los 8 caracteres, es decir. 1,112,064 ^ 8 (digamos 10 ^ 48) pruebas (que ya es poco probable que sea posible), pero en realidad tienes que probar cada valor de cada uno de los 48 bytes o 256 ^ 48, que es alrededor de 10 ^ 120, que es la misma complejidad que el ajedrez en comparación con el número total de átomos en el universo de aproximadamente 10 ^ 80.

En su lugar, puede usar, en orden creciente de esfuerzo, y cada prueba debe cubrir todo lo anterior:

a) pruebe una buena y una mala muestra.

b) cobertura de código, es decir. intente probar cada línea de código, que es relativamente simple para la mayoría de los códigos. Ahora puede preguntarse cuál es el último 1% del código que no puede probar ... errores, código muerto, excepciones de hardware, etc.

c) cobertura de ruta, se prueban todos los resultados de todas las ramas en todas las combinaciones. Ahora sabe por qué el departamento de pruebas lo odia cuando sus funciones contienen más de 10 condiciones. También te preguntas por qué no se puede probar el último 1% ... algunas ramas dependen de las ramas anteriores.

d) prueba de datos, prueba una cantidad de muestra con valor de borde, valores problemáticos comunes y números mágicos, cero, -1, 1, min +/- 1, max +/- 1, 42, valores rnd. Si esto no le brinda cobertura de ruta, sabe que no ha captado todos los valores en su análisis.

Si ya lo hace, debería estar listo para el examen básico de ISTQB.

Surt
fuente