Un catálogo de construcciones de software, lenguajes y API que se completan inesperadamente con Turing; Las implicaciones de esto para la seguridad y la fiabilidad. Aplicación: ¿cuántas computadoras hay en tu computadora?

Cualquier programa C o Fortran bastante complejo contiene una implementación recientemente escrita, no especificada, con errores y lenta de la mitad del lenguaje Common Lisp . - Décima Regla Greenspan

La integridad de Turing (TC) es una propiedad del sistema para implementar cualquier función computable con alguna representación simple de entrada y salida.

La integridad de Turing es un concepto fundamental en informática. Ayuda a responder muchas preguntas clave, por ejemplo, por qué es imposible crear el programa antivirus perfecto. Pero al mismo tiempo, es un hecho sorprendentemente común . Parecería que es difícil para un sistema informático lograr tal universalidad que pueda ejecutar cualquier programa, pero lo contrario es cierto: es difícil escribir un sistema útil que no se convierta inmediatamente en un Turing completo. Resulta que incluso un pequeño control sobre los datos de entrada y convertirlos en un resultado, como regla, le permite crear un sistema completo. Puede ser divertido, útil (aunque generalmente no ), dañino o extremadamente inseguro y un verdadero regalo para un hacker (ver "seguridad teórica del lenguaje" , que estudia los métodos de piratería de "máquinas extrañas" ¹⁾ ) Increíbles ejemplos de este comportamiento nos recuerdan que la integridad de Turing acecha en todas partes, y es extremadamente difícil proteger el sistema.

Los lenguajes de programación demasiado potentes también pueden desencadenar ataques DoS desagradables. Fazzer afl encontró tal roff en OpenBSD que es capaz de generar un bucle infinito , abusando de algunas reglas de sustitución de cadenas.

Probablemente, estos ejemplos inesperados de sistemas completos de Turing se consideran mejor como un subconjunto de los lenguajes de programación esotéricos "descubiertos" o "encontrados". Por lo tanto, el FRACTRAN extraordinariamente minimalista no se considera ² , así como el lenguaje especialmente ofuscado Malbolge (donde escribir un programa trivial tomará años), porque estos son YaP esotéricos especialmente diseñados. Además, el juego Life no está incluido en nuestro subconjunto, porque las preguntas sobre la integridad de Turing aparecieron inmediatamente después de su lanzamiento, y el reconocimiento de su Turing completo no fue una sorpresa. Y teniendo en cuenta la complejidad de las redes con enrutamiento y conmutación de paquetes, no es sorprendente que pueda construir un autómata celular o esquemas lógicos de programa en estas redes, y la planificación / validación de tickets no solo es una tarea NP difícil e incluso EXPSPACE, sino que es completamente insoluble (debido a reglas complejas de la aerolínea).

Muchas configuraciones, lenguajes especiales, herramientas o juegos complejos, como resultado, violan la regla del menor poder y "se vuelven completados accidentalmente" , como MediaWiki , plantillas sed o comandos repetidos regexp / find-replace en el editor. En general, cualquier forma de reemplazo de línea o plantilla, o compilación sobre la marcha con alta probabilidad es un sistema completo de Turing o cuando se repite, ya que a menudo admiten el cálculo lambda o la reescritura de términos de un idioma o etiqueta, por ejemplo, idiomas esotéricos " /// " o jue

XSLT , Buscaminas infinito , Fortaleza enana ³ , Starcraft, Minecraft , Ant , Transport Tycoon , plantillas C ++ y generalizaciones de Java , cálculos de ADN , etc. Todos estos son sistemas completos de Turing, y esto tampoco es sorprendente. Muchos juegos admiten scripts para simplificar el desarrollo y las modificaciones personalizadas. Por lo tanto, para hacer que el juego Turing-complete sea elemental: solo active la sintaxis para llamar a idiomas más conocidos como Perl.

La integridad de Turing puede ser simplemente una parte poco conocida del formato estándar. Probablemente, en nuestro tiempo, muchos no saben que TrueType y muchas fuentes son programas PostScript en máquinas apiladas, similares a los metadatos ELF y la información de depuración DWARF . O que algunos formatos de música van más allá de MIDI , admiten guiones y necesitan interpretación. Si conoce la integridad de las fuentes de Turing, entonces la integridad de los documentos de Turing de TeX no es sorprendente, lo que naturalmente causa muchas vulnerabilidades de seguridad serias e interesantes en las fuentes y los medios, como las explotaciones BLEND o Linux SNES y NES . En otros formatos como PDF, solo hay una cantidad terrible de vulnerabilidades ⁴ . Una vez más, logros sobresalientes como la creación de una pequeña máquina de Turing a partir de bloques de Lego o dominó ⁵ no se consideran, ya que sabemos desde hace tiempo cómo funcionan las computadoras mecánicas.

Por otro lado, una línea de investigación de seguridad informática llamada máquinas extrañas a menudo revela sistemas realmente completos y sorprendentes. Además, causan sorpresa en diferentes grados en diferentes personas: una parece inusual que no sorprende a otras.

• Aritmética de Peano : la suma y multiplicación de números naturales es suficiente para completar Turing. Por el contrario, la aritmética de Presburger carece de multiplicación y, por lo tanto, no está completa.
• Fichas de Van : cuadrados multicolores, cuya ubicación está determinada por la regla de que los lados adyacentes de dos fichas deben ser del mismo color (históricamente claro para Van, pero el sistema me sorprendió, y probablemente a muchas otras personas).
• Fraude x86:
  
  • MMU baraja RAM para simplificar la programación. Si el programa asigna correctamente las direcciones en la memoria de una manera especial, podrá realizar cálculos arbitrarios en la MMU utilizando excepciones de fallas de página ( comentarios ; trabajo científico ) sin ejecutar el código en sí. El mecanismo de excepción MMU se convierte en una computadora con una sola instrucción .
  • mov es un sistema completo de Turing : instrucciones de ensamblador aparentemente inocuas mov , que transfiere datos entre la CPU y la RAM, le permite implementar una computadora con una sola instrucción en la arquitectura de transporte del disparador TTA . En una computadora así, puedes jugar Doom (como un bono: también en las instrucciones xor ).
  • "X86 es un conjunto completo sin registros".
• Ataques de retorno a la biblioteca: las bibliotecas de software proporcionan funciones preempaquetadas, cada una de las cuales está diseñada para hacer una cosa útil. A partir de las llamadas a estas funciones, puede crear un "lenguaje" completo que pueda evitar los mecanismos de seguridad, porque un atacante no ejecuta su propio código reconocible. Entre muchos otros ejemplos, vea "La geometría de la carne inocente en el hueso: return-into-libc sin llamadas a funciones (en x86)" y "Sobre la expresividad de los ataques return-into-libc" .
• Pokémon Amarillo : "El truco de control completo de Pokémon Amarillo" describe un ataque de corrupción de memoria que te permite crear programas arbitrarios en el ensamblador de Game Boy caminando de un lado a otro y comprando artículos en el juego. Hay logros similares por parte de los fanáticos de speedran (paso de velocidad), pero generalmente los ignoro como "impuros": por ejemplo, puedes convertir Super Mario World en SNES en un juego arbitrario como "Snakes" o "Pong" , pero es necesario descargar nuevos programas en equipos adicionales . En mi opinión, esto no nos permite llamar a Super Mario World un sistema "inesperadamente" completo y difiere de otros ejemplos en este artículo. Por ejemplo, puede pasar de Super Game Boy a SNES y a código arbitrario como IRC . Esta es una diferencia controvertida.
  
  • Un problema de corrupción de memoria similar ocurre en printf desde POSIX, en la opción %n , como en otras funciones de la biblioteca C ( Karlini et al., 2015 ). De ahí el « printbf -Brainfuck en printf .
  • La comunidad de StarCraft ha explotado un desbordamiento de búfer en el juego para implementar mapas complejos, juegos de defensa, juegos de Mario y editores de niveles. Hackear emulación para proteger mods en versiones actualizadas de SC causó muchos problemas a Blizzard .
• El juego de trenzas se está completando
• Una notación musical con instrucciones para transferir notas posteriores se convierte en el lenguaje esotérico de Choon .
• Las células musculares del corazón (cardiomiocitos) interactúan de tal manera que pueden programarse a través de puertas lógicas, por lo tanto, representan un sistema completo de turing (tal vez esto no sea demasiado sorprendente, porque los autómatas celulares se crean utilizando un ejemplo biológico)
• Una categoría de máquinas extrañas no se considera completamente completa en Turing, porque el usuario debe hacer clic en el interruptor mecánico o hacer la única opción posible para que el sistema vaya al siguiente paso. En este caso, el usuario no introduce ninguna lógica y no realiza cálculos, por lo tanto, esta categoría no satisface completamente la definición de sistemas completos de Turing:
  
  • Magic: the Gathering : este es un sistema completo , basado en la suposición de que los jugadores aceptan mecánicamente la opción propuesta, pero de lo contrario todas las acciones obedecen las reglas del juego
  • CSS está diseñado como un lenguaje de marcado declarativo para personalizar la apariencia visual de las páginas HTML, pero la regla 110 del autómata celular elemental, que cambia de estado mediante clics mecánicos del mouse en el navegador, puede codificarse en declaraciones CSS
  • Las animaciones de Microsoft PowerPoint (excluyendo macros, VBScript, etc.) con enlaces especiales pueden implementar una máquina Turing ( Wildenhain, 2017 : video ; PPT ) si el usuario hace clic en activadores de animación activos

Quizás los siguientes sistemas se completarán accidentalmente:

• CSS sin clics
• SVG: PostScript es TC por diseño, pero ¿qué pasa con el formato gráfico vectorial SVG más moderno, que está escrito en XML, es decir, en un lenguaje de documento que (generalmente) no está completo de Turing? Parece que en combinación con XSLT todavía puede ser así, pero no he encontrado ninguna evidencia o demostración de esto en el contexto habitual de un navegador web. El estándar SVG es excelente ya veces aterrador: una versión fallida del estándar SVG 1.2 intentó agregar la capacidad de abrir sockets de red en imágenes SVG.
• Unicode : Nicholas Seriot sugiere que los algoritmos bidireccionales Unicode (diseñados para mostrar secuencias de comandos de derecha a izquierda, como el árabe o el hebreo) pueden ser lo suficientemente complejos como para admitir un sistema de etiquetas a través de reglas sensibles a mayúsculas y minúsculas (por ejemplo, turco)

Ver también

• Efecto intraplataforma

Referencias

• Discusión en HN: 1 , 2
• Accidentalmente cuadrático
• "Máquinas de codificación" ; "Reflexiones sobre la delegación de confianza", Ken Thompson, 1984
• "Reprogramación adversa de redes neuronales" , Elsayed et al., 2018

App

¿Cuántas computadoras hay en tu computadora?

Algunos se estancan en disputas sobre autos extraños o sobre cuán "grande" se convertirá un agente de IA: se creará uno, dos, diez o millones. No importa, porque es solo una cuestión de organización. En realidad, las entradas y salidas del sistema son importantes: ¿qué tan eficiente es el sistema en su conjunto y qué recursos consume? A nadie le importa si Google funciona con 50 supercomputadoras, 50,000 mainframes, 5 millones de servidores, 50 millones de procesadores integrados / móviles, o una combinación de todo lo anterior . No importa que Google use una variedad de chips: desde "procesadores tensoriales" de fabricación propia hasta procesadores de silicio únicos (Intel los vende en chips para procesadores Xeon para varios clientes importantes), FPGA, GPU, CPU, hasta equipos más exóticos como computadoras cuánticas D-Wave . Solo es importante que siga siendo competitivo y pueda proporcionar servicios por una tarifa moderada. Al final, hoy en día una supercomputadora generalmente se parece a una gran cantidad de servidores en rack con una gran cantidad de GPU y conexiones InfiniBand inusualmente de alta velocidad. Es decir, la supercomputadora no es tan diferente del centro de datos, como podría pensar. Cualquiera de los equipos enumerados puede admitir numerosas máquinas extrañas, dependiendo de su dinámica interna y conectividad.

Del mismo modo, cualquier sistema de inteligencia artificial se puede implementar en forma de una red neuronal gigante o muchas redes neuronales separadas que funcionan de forma asincrónica, o como un conjunto heterogéneo de microservicios, o como una "sociedad de la mente" y así sucesivamente. Todo esto no es particularmente importante. Desde el punto de vista de la complejidad o los riesgos, no es tan importante cómo se organiza el sistema mientras funciona. El sistema se puede ver en muchos niveles, cada uno de los cuales es igualmente inválido en sí mismo, pero es útil para diferentes propósitos en el sistema general.

Aquí hay un ejemplo de una pregunta mal definida: ¿cuántas computadoras tiene en sus bolsillos y en su escritorio ahora? ¿Cuántas computadoras hay en tu "computadora"? Piensa solo uno? Echemos un vistazo más de cerca.

No se trata solo de la CPU: hoy en día, los transistores y los núcleos del procesador son tan baratos que ahora tiene sentido asignar núcleos separados para tareas en tiempo real, para mejorar el rendimiento, por seguridad, para evitar cargar el sistema operativo principal, por compatibilidad con la arquitectura antigua o paquete de software existente. Simplemente porque un DSP o kernel es más rápido de programar que crear un ASIC especializado, o porque es la solución más simple posible. Además, muchos de estos componentes pueden usarse como elementos computacionales, incluso si no están destinados o incluso ocultan esta funcionalidad.

Entonces

• En un procesador Intel convencional, miles de millones de transistores realizan muchas tareas:
  
  
  • Cada uno de los núcleos del procesador principal 2-8 puede funcionar de forma independiente, encendiéndose y apagándose según sea necesario, tiene su propia caché (más grande que la RAM en la mayoría de las computadoras hasta hace poco), y debe considerarse como una computadora independiente.
  • La CPU en su conjunto se reprograma a través de un microcódigo, por ejemplo, para eliminar errores de diseño de chips y hace alarde de objetos cada vez más opacos, como Intel Management Engine (con JVM para programación ; Rouen, 2014 y SGX ) o el procesador de seguridad de plataforma (PSP) de AMD, o Android TEE Estos módulos de hardware, por regla general, son computadoras de pleno derecho, funcionan independientemente del host y pueden interferir con su funcionamiento.
  • Cualquier FPU puede convertirse en un sistema completo de Turing mediante la codificación en operaciones de coma flotante en el espíritu de FRACTRAN.
• La MMU se puede programar en una máquina extraña de fallas de página, como se mencionó anteriormente.
• Bloques DSP , chips personalizados. Probablemente, los ASIC para formatos de video como h.264 no serán sistemas completos (a pesar del soporte de deltas complejos y métodos de compresión que pueden permitir algo como los mosaicos Van). Pero el SoC móvil Apple A9 va mucho más allá del habitual procesador ARM de doble núcleo con una GPU integrada. Al igual que los chips de escritorio Intel o AMD, incluye un entorno seguro llamado Secure Enclave (núcleos de procesador asignados físicamente), pero también contiene un coprocesador para imágenes, un coprocesador para reconocimiento de voz (parcialmente para admitir Siri) y, aparentemente, varios otros núcleos. Estos ASIC a veces existen para tareas de IA y, aparentemente, se especializan en multiplicaciones matriciales para redes neuronales, y dado que las redes neuronales recurrentes se están completando, entonces ... entiendes. Motorola, Qualcomm y otras compañías también se apresuraron a expandir su SoC.
• Placa base BIOS y / o chips de control de acceso a la red.
  
  
  • Mark Ermolov señala:
    
    

    "Es sorprendente la cantidad de núcleos de procesador heterogéneos integrados en Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, cada uno con su propio firmware y soporte para la interfaz JTAG

  
  Estos chips de control o depuración pueden "accidentalmente" permanecer activados en dispositivos después de la venta, como el ARM incorporado en la CPU Via C3 .
• La GPU tiene varios cientos o miles de núcleos simples, cada uno de los cuales funciona muy bien con redes neuronales o realiza cálculos de propósito general (aunque más lento que un procesador).
• Los controladores de cinta, disco duro, unidad flash y SSD generalmente se ejecutan en procesadores ARM para ejecutar utilidades integradas para tareas como ocultar sectores defectuosos del sistema operativo. Pueden ser pirateados. Pero los procesadores ARM se usan en la mayoría de las aplicaciones integradas, por lo que a ARM le encanta alardear de que "un teléfono inteligente moderno contiene de 8 a 14 procesadores ARM, uno de los cuales es un procesador de aplicaciones (con Android o iOS), y el otro es un procesador para la pila de banda de frecuencia (pila de banda base) " .
• Los chips de red realizan un procesamiento independiente para DMA (gracias a funciones de independencia como Wake-on-LAN para el trabajo de arranque de red ).
• teléfonos inteligentes: además de todos los bloques mencionados, también hay un procesador de banda base independiente que se ejecuta bajo su propio sistema operativo en tiempo real para procesar las comunicaciones con las torres celulares / GPS / etc. O incluso más de uno si usa virtualización como L4 . Ya se han detectado puertas traseras en los procesadores de banda base, además de otras vulnerabilidades.
• Las tarjetas SIM para teléfonos inteligentes son mucho más que simples tarjetas de memoria con la grabación de sus datos de suscriptor. Estas son tarjetas inteligentes que pueden ejecutar independientemente aplicaciones de Java Card (probablemente también chips NFC). Es como una JVM en IME. Naturalmente, las tarjetas SIM pueden ser pirateadas y utilizadas para vigilancia, etc.
• Los dispositivos conectados por USB o a la placa base pueden equiparse con sus propios procesadores. Por ejemplo, adaptadores WiFi, teclados, ratones, etc. Teóricamente, la mayoría de ellos están aislados de la interferencia directa con el host a través de DMA y IOMMU, pero el diablo está en los detalles ...
• chips extraños al azar como el MacBook Touch con WatchOS .
• ...

Por lo tanto, en un teléfono inteligente o computadora de escritorio normal, habrá de quince a varios miles de computadoras en el sentido de dispositivos completos. Cada uno de ellos puede programarse, tiene suficiente potencia para ejecutar muchos programas y puede ser utilizado por un atacante para monitorear, filtrar o atacar al resto del sistema.

No hay nada inusual en el contexto histórico, porque incluso los primeros mainframes generalmente incluían varias computadoras, donde la computadora principal realiza el procesamiento por lotes, y las computadoras auxiliares proporcionan operaciones de E / S de alta velocidad, que de lo contrario interferirían con la máquina principal con sus interrupciones.

En la práctica, además de la comunidad de seguridad de la información (dado que todas estas computadoras son inseguras y, por lo tanto, útiles para los creadores de virus y NSA), a todos los demás usuarios no les importa que, bajo el capó de nuestras computadoras, se encuentren sistemas increíblemente complejos que se consideran con mayor precisión como una colección heterogénea de cientos computadoras avergonzadas conectadas entre sí (no está claro, "una red es una computadora" o "una computadora es una red" ...?) El usuario percibe y usa esto como una sola computadora.

---

1. Un área activa de investigación es la creación de lenguajes y sistemas cuidadosamente diseñados y garantizados para que no se completen (por ejemplo, programación totalmente funcional ). ¿Por qué poner tanto esfuerzo en crear un lenguaje que muchos programas no pueden escribir? El hecho es que la integridad de Turing está estrechamente relacionada con el teorema de incompletitud de Gödel y el teorema de Rice. . TC, . , : , , , , , . , ( SQL, — . , , SQL , descenso de gradiente para modelos de aprendizaje automático , y algunas extensiones SQL lo hacen completo de todos modos, lo que le permite codificar un sistema de bucle , o modelDSL , o llamar a PL / SQL , etc.

Aquí hay algo de literatura sobre autos extraños:

• "Programación de exploits: desde desbordamientos de búfer a máquinas extrañas y teoría de la computación" , Bratus et al., 2011
• "El problema de detención en la seguridad de la pila de red", Sassamen et al., 2011
• La extraña máquina de fallas de página: lecciones en computación sin instrucciones , Bangert et al., 2013
• "Autos extraños en ELF: un enfoque en metadatos subestimados", Shapiro et al 2013
• "Programación de errores orientada a la interrupción: un enfoque minimalista para incorporar errores en el firmware de los sistemas integrados" , Tan et al., 2014
• Autos extraños en el código basado en evidencia , Vaneg, 2014
• "Señales cíclicas: volviendo a Shellcode portátil", Bosman y Bos, 2014

↑

2. Aunque las redes neuronales lineales explotan el modo de coma flotante con redondeo a cero para codificar el comportamiento potencialmente completo de Turing (para RNN), es invisible en el funcionamiento normal, que también es un comportamiento aleatorio de Turing completo y un buen ejemplo de un lenguaje seguro. ↑

3. Dwarf Fortress proporciona un mecanismo de relojería, por lo que la integridad de Turing no es sorprendente. Pero el agua también se implementa como un simple autómata celular, por lo que hay aún más formas de lograr la integridad. Ahora, el wiki del juego menciona cuatro formas potenciales de crear puertas lógicas: líquidos, mecanismos de reloj, carros de minas y puertas lógicas de criaturas / animales con puertas y sensores de presión. ↑

4. La especificación completa de PDF está excepcionalmente hinchada. Por ejemplo, en un simple visor de PDF que admite una buena cantidad de especificaciones de PDF como el navegador Google Chrome, puede jugar Breakout (porque PDF incluye su propio subconjunto extraño de JavaScript). El visor oficial de PDF de Adobe admite la funcionalidad de CAD hasta tridimensional. ↑

5. Vea las puertas lógicas de dominó en Think Math y la demostración de un sumador de dominó de 4 bits . ↑