Detectar se seu programa foi alterado

16

Escreva um programa que termine sem erro.

Se qualquer byte único for substituído por outro byte, o programa deve gerar

CORRUPTED
  • Não leia seu código fonte de um arquivo
  • Seu programa não deve produzir nenhuma outra saída

Isso é então a resposta mais curta em bytes vence.

Editar: removido o requisito "NÃO CORROMPIDO"

noɥʇʎԀʎzɐɹƆ
fonte
O endurecimento por radiação tem uma série de perguntas semelhantes, mas não encontrei nenhuma que seja parecida com essa.
FryAmTheEggman
7
Para os que recusam: suspeito que isso seja possível (se muito difícil), se você escolher o idioma certo. Não feche ou exclua a pergunta, a menos que você ache que há algo errado com ela, além de ser impossível.
7
O que significa mudou ? Substituído por outro byte?
Dennis
4
@ ais523 FWIW Eu votei contra o desafio porque parece escrito às pressas, não porque acho que é muito difícil.
Dennis
5
Não é que alguma coisa não está clara, mas poderia ser feita mais clara . Você pode esclarecer se um programa completo é necessário, adicionar um programa de exemplo e ilustrar todas as modificações possíveis, mencionar como as substituições de byte único afetariam um arquivo codificado em UTF-8, adicionar um script que possa ser usado para testar envios, mencionar que o programa não deve receber entrada, etc.
Dennis

Respostas:

30

Uma pereira , 76 bytes

$@='NOT ';print"$@CORRUPTED"__DATA__ =®®”print"$@CORRUPTED"__DATA__ =®®”Ê®›~

Este programa contém alguns octetos perdidos que não são válidos UTF-8. Como tal, é mostrado como parece no Windows-1252. (Por padrão, se A Pear Tree vê um octeto não ASCII em uma string literal ou semelhante, trata-o como um objeto opaco e não tenta entendê-lo além de estar ciente de qual é seu código de caractere; esse comportamento pode ser alterado através de uma declaração de codificação, mas o programa não possui uma. Portanto, o programa está logicamente em "conjunto de caracteres não especificado compatível com ASCII". Todos os octetos não ASCII estão nos comentários de qualquer maneira, portanto, isso realmente não importa.)

Explicação

Uma árvore de pera soma o programa, procurando a substring mais longa que possui um CRC-32 00000000. (Se houver um empate, ele escolhe o octetbeticamente primeiro.) Em seguida, o programa é rotacionado para colocá-lo no início. Finalmente, o programa é interpretado como uma linguagem que é quase um superconjunto do Perl, definindo algumas coisas indefinidas no Perl para que funcionem da mesma maneira que no Python (e com algumas pequenas alterações, por exemplo, printimprime uma nova linha final em A Pear Tree mas não em Perl). Esse mecanismo (e a linguagem como um todo) foi projetado para problemas e ; este não é o primeiro, mas é definitivamente o último.

Neste programa, temos duas substrings notáveis ​​para as quais o CRC-32 00000000; o programa inteiro faz, e o faz print"$@CORRUPTED"__DATA__ =®®sozinho (que aparece duas vezes). Como tal, se o programa não estiver corrompido, ele será definido $@como NOT e depois será impresso CORRUPTED. Se o programa estiver corrompido, o CRC-32 do programa como um todo falhará ao corresponder, mas uma das seções mais curtas permanecerá incorreta. O que for girado para o início do programa será impresso CORRUPTED, assim como $@a sequência nula.

Depois que a string é impressa, __DATA__é usada para impedir a execução do restante do programa. (Me passa pela cabeça escrever isso que __END__poderia ser usado em vez disso, o que claramente salvaria dois bytes. Mas também posso postar esta versão agora, porque passei muito tempo verificando-a e uma versão modificada teria que ser foi verificada novamente devido às alterações da CRC e ainda não dediquei um grande esforço ao golfe da "carga útil", então quero ver se alguém tem outras melhorias nos comentários que posso incorporar ao mesmo tempo. Observe que #não funciona na situação em que um personagem está corrompido em uma nova linha.)

Você pode estar se perguntando como eu consegui controlar o CRC-32 do meu código em primeiro lugar. Este é um truque matemático bastante simples, baseado na maneira como o CRC-32 é definido: você pega o CRC-32 do código, escreve-o em ordem little-endian (o inverso da ordem de bytes que normalmente é usado no cálculo do CRC-32 programas) e XOR com 9D 0A D9 6D. Em seguida, você anexa isso ao programa e terá um programa com um CRC-32 de 0. (Como o exemplo mais simples possível, a cadeia nula tem um CRC-32 de 0, 9D 0A D9 6Dtambém possui um CRC-32 de 0 .)

Verificação

Uma árvore de pêra pode lidar com a maioria dos tipos de mutações, mas estou assumindo que "alterado" significa "substituído por um octeto arbitrário". É teoricamente possível (embora improvável em um programa tão curto) que possa haver uma colisão de hash em algum lugar que leve ao programa errado em execução, então eu tive que verificar por força bruta que todas as possíveis substituições de octetos deixariam o programa funcionando corretamente. Aqui está o script de verificação (escrito em Perl) que eu usei:

use 5.010;
use IPC::Run qw/run/;
use warnings;
use strict;
undef $/;
$| = 1;
my $program = <>;
for my $x (0 .. (length $program - 1)) {
    for my $a (0 .. 255) {
        print "$x $a    \r";
        my $p = $program;
        substr $p, $x, 1, chr $a;
        $p eq $program and next;
        alarm 4;
        run [$^X, '-M5.010', 'apeartree.pl'], '<', \$p, '>', \my $out, '2>', \my $err;
        if ($out ne "CORRUPTED\n") {
            print "Failed mutating $x to $a\n";
            print "Output: {{{\n$out}}}\n";
            print "Errors: {{{\n$err}}}\n";
            exit;
        }
    }
}

say "All OK!    ";

fonte
Um CRC de n bits detectará qualquer explosão de erro não superior a n bits. As colisões de hash são impossíveis no caso em questão, não há necessidade de verificação da força bruta.
Rainer P.
@RainerP .: Estou ciente de que uma mutação impedirá o CRC para as partes que originalmente têm um CRC de 0 correspondente. No entanto, existe a possibilidade de que ele possa introduzir uma nova substring do código que tenha um CRC de 0; o objetivo da força bruta é garantir que isso não aconteceu.