Um catálogo de construções de software, idiomas e APIs que são inesperadamente concluídos por Turing; as implicações disso para segurança e confiabilidade. Aplicação: quantos computadores no seu computador?

Qualquer programa C ou Fortran bastante complexo contém uma implementação recém-escrita, não especificada, com bugs e lenta de metade da linguagem Common Lisp . - Décima regra de Greenspan

A integridade de Turing (TC) é uma propriedade do sistema para implementar qualquer função computável com alguma representação simples de entrada e saída.

Turing completude é um conceito fundamental em ciência da computação. Ajuda a responder a muitas perguntas importantes, por exemplo, por que é impossível criar o programa antivírus perfeito. Mas, ao mesmo tempo, é uma ocorrência surpreendentemente comum . Parece que é difícil para um sistema de computador alcançar tal universalidade que possa executar qualquer programa, mas o oposto é verdadeiro: é difícil escrever um sistema útil que não se transforma imediatamente em um Turing completo. Acontece que mesmo um pouco de controle sobre os dados de entrada e convertê-los em resultado, via regra, permite criar um sistema completo de busca. Pode ser engraçado, útil (embora geralmente não seja ), prejudicial ou extremamente inseguro e um presente real para um hacker (consulte “segurança teórica da linguagem” , que estuda métodos de hacking de “máquinas estranhas” ¹ ) Exemplos surpreendentes desse comportamento nos lembram que a integridade de Turing se esconde em todos os lugares e é extremamente difícil proteger o sistema.

Linguagens de programação muito poderosas também podem desencadear ataques desagradáveis ​​de DoS. Fazzer afl encontrou tal roff no OpenBSD que é capaz de gerar um loop infinito , abusando de algumas regras de substituição de strings.

Provavelmente, esses exemplos inesperados de sistemas completos de Turing são mais bem considerados como um subconjunto das linguagens de programação esotérica "descobertas" ou "encontradas". Portanto, o FRACTRAN extraordinariamente minimalista não é considerado ² , bem como a linguagem especialmente ofuscada Malbolge (onde escrever um programa trivial levará anos), porque esses são YaP esotérico especialmente projetado. Além disso, o jogo Life não está incluído em nosso subconjunto, porque perguntas sobre a integridade de Turing apareceram imediatamente após seu lançamento e o reconhecimento de sua completa Turing não foi uma surpresa. E, dada a complexidade das redes de roteamento e comutação de pacotes, não surpreende que um autômato celular possa ser construído nessas redes ou esquemas lógicos possam ser programados, e o planejamento / validação de tickets não seja apenas uma tarefa difícil para NP ou mesmo para EXPSPACE, mas também completamente insolúvel (devido a regras complexas das companhias aéreas).

Muitas configurações, idiomas especiais, ferramentas ou jogos complexos violam a regra de menor poder e “acidentalmente se tornam Turing completos” , como o MediaWiki , modelos sed ou comandos repetidos de regexp / find-replace no editor. Em geral, qualquer forma de substituição ou modelagem de linha ou compilação em tempo real com alta probabilidade é um sistema completo de Turing ou quando repetido, pois geralmente suporta cálculo lambda ou reescrita de termos de um idioma ou rótulo, por exemplo, idiomas esotéricos " /// " ou terça .

XSLT , Caça-minas infinito , Fortaleza dos Anões ³ , Starcraft, Minecraft , Ant , Transport Tycoon , modelos C ++ e generalizações Java , cálculos de DNA e assim por diante - todos esses são sistemas completos de Turing, e isso também não é surpreendente. Muitos jogos suportam scripts para simplificar o desenvolvimento e mods personalizados. Portanto, para tornar o jogo completo de Turing elementar: basta ativar a sintaxe para chamar idiomas mais conhecidos, como Perl.

A integridade de Turing pode ser simplesmente uma parte pouco conhecida do formato padrão. Provavelmente, atualmente, muitos não sabem que TrueType e muitas fontes são programas PostScript em máquinas empilhadas, semelhantes aos metadados ELF e às informações de depuração DWARF . Ou que alguns formatos de música vão além do MIDI , suportam scripts e precisam de interpretação. Se você conhece a integridade das fontes de Turing, a integridade do ajuste de documentos do TeX não é surpreendente, o que naturalmente causa muitas vulnerabilidades de segurança sérias e interessantes em fontes e mídias, como explorações BLEND ou Linux SNES e NES . Em outros formatos como PDF, há apenas uma quantidade terrível de vulnerabilidades ⁴ . Novamente, realizações excelentes, como a criação de uma pequena máquina de Turing a partir de blocos ou dominós de Lego ⁵ não são considerados, pois sabemos há muito tempo como os computadores mecânicos funcionam.

Por outro lado, uma linha de pesquisa em segurança de computadores chamada máquinas estranhas geralmente revela sistemas verdadeiramente completos e surpreendentes. Além disso, causam surpresa em diferentes graus em pessoas diferentes: uma parece incomum que não surpreende outras.

• Aritmética peano : adição e multiplicação de números naturais são suficientes para a integridade de Turing. Pelo contrário, a aritmética de Presburger é desprovida de multiplicação e, portanto, não é Turing completa.
• Ladrilhos de van : quadrados multicoloridos, cuja colocação é determinada pela regra de que os lados adjacentes de dois ladrilhos devem ter a mesma cor (historicamente claro para Van, mas o sistema me surpreendeu e provavelmente muitas outras pessoas).
• fraude x86:
  
  • A MMU embaralha a RAM para simplificar a programação. Se o programa atribuir corretamente endereços na memória de uma maneira especial, ele poderá executar cálculos arbitrários na MMU usando exceções de falhas de página ( comentários ; trabalho científico ) sem executar o próprio código. O mecanismo de exceção da MMU se transforma em um computador com uma instrução .
  • mov é um sistema Turing-complete : instrução aparentemente inócua do assembler mov , que transfere dados entre a CPU e a RAM, permite implementar um computador com uma instrução na arquitetura de transporte do acionador TTA . Nesse computador, você pode jogar Doom (como um bônus: também nas instruções xor ).
  • "O X86 é um conjunto completo de atualizações sem registros."
• Ataques de retorno à libc : as bibliotecas de software fornecem funções pré-empacotadas, cada uma delas projetada para fazer uma coisa útil. De chamadas para essas funções, você pode criar uma "linguagem" completa e completa que pode ignorar os mecanismos de segurança, porque um invasor não executa seu próprio código reconhecível. Entre muitos outros exemplos, consulte “A geometria da carne inocente no osso: retorno à libc sem chamadas de função (em x86)” e “Sobre a expressividade dos ataques de retorno à libc” .
• Pokemon Yellow : “O hack de controle Pokemon Yellow completo” descreve um ataque de corrupção de memória que permite criar programas arbitrários no Game Boy assembler andando de um lado para o outro e comprando itens no jogo. Existem conquistas semelhantes dos fãs de speedran (passagem de velocidade), mas eu geralmente as ignoro como "impuras": por exemplo, você pode transformar Super Mario World no SNES em um jogo arbitrário como "Snakes" ou "Pong" , mas novos programas precisam ser baixados para equipamentos adicionais . Na minha opinião, isso não nos permite chamar Super Mario World de um sistema "inesperadamente" completo e diferente de outros exemplos neste artigo. Por exemplo, você pode ir do Super Game Boy ao SNES e a códigos arbitrários como o IRC . Esta é uma diferença controversa.
  
  • Um problema semelhante de corrupção de memória ocorre no printf do POSIX, na opção %n , como em outras funções da biblioteca C ( Karlini et al., 2015 ). Daí o « printbf -Brainfuck em printf .
  • A comunidade StarCraft explorou um estouro de buffer no jogo para implementar mapas complexos, jogos de defesa, jogos do Mario e editores de níveis para ele. A emulação de hackers para proteger os mods nas versões atualizadas do SC causou muitos problemas à Blizzard .
• O jogo Braid está completo
• Uma notação musical com instruções para transferir notas subseqüentes se torna a linguagem esotérica de Choon .
• As células musculares do coração (cardiomiócitos) interagem de tal forma que podem ser programadas através de portas lógicas, portanto, representam um sistema completo de turing (talvez isso não seja muito surpreendente, porque autômatos celulares são criados usando um exemplo biológico)
• Uma categoria de máquinas estranhas não é considerada completamente concluída por Turing, porque o usuário deve clicar no interruptor mecânico ou fazer a única opção possível para que o sistema avance para a próxima etapa. Nesse caso, o usuário não introduz nenhuma lógica e não realiza cálculos; portanto, essa categoria não atende totalmente à definição de sistemas Turing-complete:
  
  • Magic: the Gathering : este é um sistema completo , baseado no pressuposto de que os jogadores concordam mecanicamente com a opção proposta, mas, caso contrário, todas as ações obedecem às regras do jogo
  • O CSS foi projetado como uma linguagem de marcação declarativa para personalizar a aparência visual das páginas HTML, mas a regra 110 do autômato celular elementar, que muda de estado por cliques mecânicos do mouse no navegador, pode ser codificada nas declarações CSS
  • As animações do Microsoft PowerPoint (excluindo macros, VBScript, etc.) com links especiais podem implementar uma máquina de Turing ( Wildenhain, 2017 : video ; PPT ) se o usuário clicar na animação ativa.

Talvez os seguintes sistemas estejam acidentalmente completos:

• CSS sem cliques
• SVG: PostScript é TC por design, mas e o formato gráfico vetorial SVG mais moderno, escrito em XML, ou seja, em uma linguagem de documento que geralmente não é completa em Turing? Parece que em combinação com o XSLT ainda pode ser assim, mas não encontrei nenhuma evidência ou demonstração disso no contexto usual de um navegador da web. O padrão SVG é ótimo e às vezes aterrorizante: uma versão sem êxito do padrão SVG 1.2 tentou adicionar a capacidade de abrir soquetes de rede em imagens SVG.
• Unicode : Nicholas Seriot sugere que algoritmos Unicode bidirecionais (projetados para exibir scripts da direita para a esquerda, como árabe ou hebraico) podem ser complexos o suficiente para suportar um sistema de tags por meio de regras que diferenciam maiúsculas de minúsculas (por exemplo, turco)

Veja também

• Efeito intraplataforma

Referências

• Discussão em HN: 1 , 2
• Acidentalmente quadrático
• "Máquinas codificadoras" ; "Reflexões sobre a delegação de confiança", Ken Thompson, 1984
• “Reprogramação adversa de redes neurais” , Elsayed et al., 2018

App

Quantos computadores existem no seu computador?

Alguns ficam atolados em disputas sobre carros estranhos ou sobre o quão “grande” um agente de IA se tornará: um desses, dois, dez ou milhões serão criados. Não importa, pois é apenas uma questão organizacional. Na verdade, as entradas e saídas do sistema são importantes: qual a eficiência do sistema como um todo e que recursos consome? Ninguém se importa se o Google roda em 50 supercomputadores, 50.000 mainframes, 5 milhões de servidores, 50 milhões de processadores embarcados / móveis ou uma combinação de todos os itens acima . Não importa que o Google use uma variedade de chips: de "processadores tensores" caseiros a processadores de silício exclusivos (a Intel os vende em chips para processadores Xeon para vários clientes importantes), FPGA, GPU, CPU, a equipamentos ainda mais exóticos, como computadores quânticos D-Wave . É importante que permaneça competitivo e possa fornecer serviços por uma taxa moderada. No final, hoje em dia, um supercomputador geralmente se parece com um grande número de servidores em rack com uma enorme quantidade de GPUs e conexões InfiniBand de alta velocidade incomum. Ou seja, o supercomputador não é tão diferente do data center, como você pode pensar. Qualquer um dos equipamentos listados pode suportar inúmeras máquinas estranhas, dependendo de sua dinâmica interna e conectividade.

Da mesma forma, qualquer sistema de IA pode ser implementado na forma de uma rede neural gigante ou de muitas redes neurais separadas operando de forma assíncrona, ou como um conjunto heterogêneo de microsserviços, ou como uma "sociedade da mente" e assim por diante. Tudo isso não é particularmente importante. Do ponto de vista da complexidade ou dos riscos, não é tão importante como o sistema está organizado enquanto trabalha. O sistema pode ser visto em vários níveis, cada um dos quais é igualmente inválido em si, mas é útil para diferentes propósitos no sistema geral.

Aqui está um exemplo de uma pergunta mal definida: quantos computadores você tem nos bolsos e na mesa agora? Quantos computadores existem no seu "computador"? Pense apenas um? Vamos dar uma olhada.

Não se trata apenas da CPU: hoje em dia, os núcleos dos transistores e do processador são tão baratos que agora faz sentido alocar núcleos separados para tarefas em tempo real, para melhorar o desempenho, a segurança, evitar o carregamento do sistema operacional principal, compatibilidade com a arquitetura antiga ou pacote de software existente. Só porque um DSP ou kernel é mais rápido de programar do que criar um ASIC especializado, ou porque é a solução mais simples possível. Além disso, muitos desses componentes podem ser usados ​​como elementos computacionais, mesmo que não sejam destinados ou ocultem essa funcionalidade.

Então:

• Em um processador Intel convencional, bilhões de transistores realizam muitas tarefas:
  
  
  • Cada um dos 2 a 8 núcleos do processador principal é capaz de trabalhar de forma independente, ativando e desativando o necessário, possui seu próprio cache (maior que a RAM na maioria dos computadores até recentemente) e deve ser considerado como um computador independente.
  • A CPU como um todo é reprogramada via microcódigo, por exemplo, para eliminar erros de design de chips e exibe objetos cada vez mais opacos, como o Intel Management Engine (com JVM para programação ; Rouen, 2014 e SGX ) ou o Platform Security Processor (PSP) da AMD ou Android TEE Esses módulos de hardware, como regra, são computadores de pleno direito, funcionam independentemente do host e podem interferir em sua operação.
  • Qualquer FPU pode se tornar um sistema completo de Turing através da codificação em operações de ponto flutuante, no espírito do FRACTRAN.
• A MMU pode ser programada em uma máquina de falha de página estranha, como mencionado acima.
• Blocos DSP , chips personalizados. Provavelmente, os ASICs para formatos de vídeo como o h.264 não serão sistemas completos (apesar do suporte a deltas complexos e métodos de compactação que podem permitir algo como blocos de Van). Mas o SoC móvel Apple A9 vai muito além do habitual processador ARM de núcleo duplo com uma GPU integrada. Como os chips de desktop Intel ou AMD, ele inclui um ambiente seguro chamado Secure Enclave (núcleos de processador fisicamente dedicados), mas também contém um coprocessador para imagens, um coprocessador para reconhecimento de voz (parcialmente para suportar a Siri) e, aparentemente, vários outros núcleos. Esses ASICs às vezes existem para tarefas de IA e, aparentemente, se especializam em multiplicações de matrizes para redes neurais, e como as redes neurais recorrentes são completas de Turing, então ... você se conhece. Motorola, Qualcomm e outras empresas também correram para expandir seu SoC.
• BIOS da placa-mãe e / ou chips de controle de acesso à rede.
  
  
  • Mark Ermolov observa:
    
    

    “É incrível quantos núcleos de processadores heterogêneos estão integrados no Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, DSP de áudio, cada um com seu próprio firmware e suporte para a interface JTAG

  
  Esses chips de controle ou depuração podem "acidentalmente" permanecer ativados nos dispositivos após a venda, como o ARM embutido na CPU Via C3 .
• A GPU possui várias centenas ou milhares de núcleos simples, cada um dos quais funciona muito bem com redes neurais ou realiza cálculos de uso geral (embora mais lento que um processador).
• Controladores de fita, disco rígido, unidade flash e SSD normalmente são executados nos processadores ARM para executar utilitários internos para tarefas como ocultar setores defeituosos do sistema operacional. Eles podem ser hackeados. Como os processadores ARM são usados ​​na maioria dos aplicativos incorporados, o ARM gosta de se gabar de que “um smartphone moderno contém de 8 a 14 processadores ARM, um dos quais é um processador de aplicativos (executando Android ou iOS) e o outro é um processador para a pilha de faixas de frequências (pilha de banda base) . "
• os chips de rede executam processamento independente para DMA (graças a funções de independência, como Wake-on-LAN, para trabalho com inicialização via rede ).
• smartphones: além de todos os blocos mencionados, há também um processador de banda de base independente que roda sob seu próprio sistema operacional em tempo real para processar comunicações com torres de celular / GPS / etc. Ou ainda mais de um, se você usar a virtualização como L4 . Backdoors já foram detectados em processadores de banda base, além de outras vulnerabilidades.
• Os cartões SIM para smartphones são muito mais do que apenas cartões de memória com a gravação dos dados do assinante. Estes são cartões inteligentes que podem executar aplicativos Java Card independentemente (provavelmente também chips NFC). É como uma JVM no IME. Naturalmente, os cartões SIM podem ser invadidos e usados ​​para vigilância etc.
• Os dispositivos conectados via USB ou à placa-mãe podem ser equipados com seus próprios processadores. Por exemplo, adaptadores WiFi, teclados, mouses, etc. Teoricamente, a maioria deles é isolada da interferência direta com o host através do DMA e do IOMMU, mas o diabo está nos detalhes ...
• chips estranhos aleatórios como o MacBook Touch executando o WatchOS .
• ...

Assim, em um smartphone ou computador de mesa comum, haverá de quinze a vários milhares de computadores no sentido de dispositivos completos. Cada um deles pode ser programado, possui poder suficiente para executar muitos programas e pode ser usado por um invasor para monitorar, exfiltrar ou atacar o restante do sistema.

Não há nada incomum no contexto histórico, porque mesmo os primeiros mainframes geralmente incluíam vários computadores nos quais o computador principal realiza o processamento em lote, e os computadores auxiliares fornecem operações de E / S de alta velocidade, o que de outra forma interferiria na máquina principal com suas interrupções.

Na prática, além da comunidade de segurança da informação (uma vez que todos esses computadores são inseguros e, portanto, úteis para criadores de NSA e vírus), todos os outros usuários não se importam que, sob o capô de nossos computadores, existam sistemas insanamente complexos que são considerados com mais precisão como uma mistura heterogênea de centenas computadores conectados embaraçosamente uns com os outros (não está claro, “uma rede é um computador” ou “um computador é uma rede” ...?). O usuário percebe e usa isso como um computador.

---

1. Uma área ativa de pesquisa é a criação de linguagens e sistemas cuidadosamente projetados e com garantia de não serem completos para Turing (por exemplo, programação totalmente funcional ). Por que se esforçar tanto para criar uma linguagem que muitos programas não conseguem escrever? O fato é que a integridade de Turing está intimamente relacionada ao teorema da incompletude de Gödel e ao teorema de Rice.. Portanto, se o TC for permitido, perderemos todas as propriedades de provabilidade possíveis. Pelo contrário, várias coisas úteis são facilmente provadas em uma linguagem incompleta de Turing: por exemplo, que um programa é completo, seguro ou não, que é fácil converter para um teorema lógico, que consome uma quantidade limitada de recursos, que a implementação do protocolo é verdadeira ou equivalente a outra implementação. É fácil provar que não há efeitos colaterais e que o programa pode ser convertido em um equivalente logicamente, mas uma opção mais rápida (isso é especialmente importante para linguagens declarativas como SQL, onde a capacidade do otimizador de converter consultas é a chave para um desempenho aceitável. Embora, é claro, coisas incríveis possam ser feitas com o SQL, comodescida de gradiente para modelos de aprendizado de máquina , e algumas extensões SQL o tornam completo de qualquer maneira, permitindo que você codifique um sistema de loop ou modelDSL ou chame PL / SQL etc.

Aqui está uma literatura sobre carros estranhos:

• “Explorar a programação: dos estouros de buffer às máquinas estranhas e à teoria da computação” , Bratus et al., 2011
• “O problema de parada na segurança da pilha de rede”, Sassamen et al., 2011
• A máquina estranha de falha de página: lições de computação sem instruções , Bangert et al., 2013
• “Carros estranhos na ELF: foco em metadados subestimados”, Shapiro et al 2013
• “Programação de bugs orientada a interrupções: uma abordagem minimalista para a introdução de bugs no firmware de sistemas embarcados” , Tan et al., 2014
• Carros estranhos no código baseado em evidências , Vaneg, 2014
• “Sinais Cíclicos - Retornando ao Shellcode Portátil”, Bosman e Bos, 2014

↑

2. Embora as redes neurais lineares explorem o modo de ponto flutuante com arredondamento para zero para codificar o comportamento potencialmente completo de Turing (para RNN), ele é invisível na operação normal, que também é um comportamento aleatório completo de Turing e um bom exemplo de linguagem segura. ↑

3. O Dwarf Fortress fornece um relógio, de modo que Turing não é surpreendente. Mas a água também é implementada como um autômato celular simples, portanto, existem ainda mais maneiras de obter a completude! Agora, o wiki do jogo cita quatro maneiras possíveis de criar portas lógicas: líquidos, mecanismos de relógio, carros de minas e portas lógicas de criaturas / animais com portas e sensores de pressão. ↑

4. A especificação completa do PDF é excepcionalmente inchada. Por exemplo, em um visualizador de PDF simples que ofereça suporte suficiente à especificação de PDF, como o navegador Google Chrome, você pode executar o Breakout (porque o PDF inclui seu próprio subconjunto estranho de JavaScript). O visualizador oficial do Adobe PDF suporta funcionalidades de CAD tridimensional. ↑

5. Veja as portas lógicas do dominó no Think Math e a demonstração de um somador de juntas de dominó de 4 bits . ↑