Wykryj, czy Twój program został zmutowany

16

Napisz program, który kończy się bezbłędnie.

Jeśli jakikolwiek pojedynczy bajt zostanie zastąpiony innym bajtem, program powinien wypisać dane

CORRUPTED
  • Nie czytaj kodu źródłowego z pliku
  • Twój program nie powinien generować żadnych innych danych wyjściowych

To jest więc wygrywa najkrótsza odpowiedź w bajtach.

Edycja: usunięto wymaganie „NIEPRAWIDŁOWO”

noɥʇʎԀʎzɐɹƆ
źródło
utwardzanie promieniowaniem ma wiele podobnych pytań, ale nie znalazłem żadnych podobnych do tego.
FryAmTheEggman
7
Do downvoters: Podejrzewam, że jest to możliwe (jeśli bardzo trudne), jeśli wybierzesz odpowiedni język. Proszę nie zamykać ani nie usuwać pytania, chyba że uważasz, że coś jest z nim nie tak, jak to niemożliwe.
7
Co oznacza zmiana ? Zastąpiony innym bajtem?
Dennis
4
@ ais523 FWIW Głosowałem za wyzwaniem, ponieważ wydaje się ono zbyt pochopne, a nie dlatego, że myślę, że jest zbyt trudne.
Dennis
5
Nie chodzi o to, że coś jest niejasne, ale można to wyjaśnić . Możesz wyjaśnić, czy wymagany jest pełny program, dodać przykładowy program i zilustrować wszystkie możliwe modyfikacje, wspomnieć, w jaki sposób zastąpienie jednobajtowe wpłynęłoby na plik kodowany w UTF-8, dodać skrypt, którego można użyć do testowania zgłoszeń, wspomnieć, że program nie powinien brać wkładu itp.
Dennis

Odpowiedzi:

30

Grusza , 76 bajtów

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

Ten program zawiera kilka zbłąkanych oktetów, które nie są poprawne UTF-8. Jako taki jest pokazany tak, jak wygląda w Windows-1252. (Domyślnie, jeśli A Pear Tree widzi oktet nie będący ASCII w dosłownym ciągu znaków lub tym podobne, traktuje go jako obiekt nieprzezroczysty i nie próbuje go zrozumieć poza świadomością jego kodu znaków; takie zachowanie może być zostało zmienione poprzez deklarację kodowania, ale program jej nie ma. Program logicznie jest w „nieokreślonym zestawie znaków kompatybilnym z ASCII”. Wszystkie oktety spoza ASCII i tak są w komentarzach, więc to naprawdę nie ma znaczenia.)

Wyjaśnienie

Drzewo gruszy sumuje program, szukając najdłuższego podłańcucha, który ma CRC-32 00000000. (Jeśli jest remis, najpierw wybiera oktet.) Następnie program obraca się, aby umieścić go na początku. Wreszcie program jest interpretowany jako język, który jest prawie nadzbiorem Perla, definiując kilka rzeczy, które są niezdefiniowane w Perlu, aby działały tak samo jak w Pythonie (i z kilkoma drobnymi zmianami, np. printDrukuje ostatnią nową linię w A Pear Tree ale nie w Perlu). Mechanizm ten (i język jako całość) został zaprojektowany z myślą o problemach z i ; to nie jest ten pierwszy, ale to zdecydowanie ten drugi.

W tym programie mamy dwa znaczące podciągi, do których CRC-32 00000000; cały program robi to print"$@CORRUPTED"__DATA__ =®®samo, co samo (co pojawia się dwukrotnie). Jako taki, jeśli program nie jest uszkodzony, zostanie ustawiony $@naNOT a następnie wydrukowany, a następnie CORRUPTED. Jeśli program jest uszkodzony, to CRC-32 programu jako całość nie będzie pasował, ale jedna z krótszych sekcji pozostanie nienaruszona. Niezależnie od tego, który z nich zostanie obrócony na początek programu, po prostu zostanie wydrukowany CORRUPTED, podobnie jak $@ciąg pusty.

Po wydrukowaniu łańcucha __DATA__ jest używany, aby uniemożliwić uruchomienie pozostałej części programu. (Przyszło mi do głowy, żeby napisać, że __END__można by zamiast tego użyć, co wyraźnie zaoszczędziłoby dwa bajty. Ale równie dobrze mogę teraz opublikować tę wersję, ponieważ spędziłem sporo czasu na jej weryfikacji, a zmodyfikowana wersja musiałaby być ponownie zweryfikowany ze względu na zmiany CRC i nie włożyłem jeszcze wiele wysiłku w grę w golfa „ładowność”, więc chcę sprawdzić, czy ktoś ma inne ulepszenia w komentarzach, które mogę jednocześnie uwzględnić. Zauważ, że #to nie działa w sytuacji, gdy znak jest uszkodzony w nowej linii.)

Być może zastanawiasz się, w jaki sposób udało mi się kontrolować CRC-32 mojego kodu. Jest to dość prosta sztuczka matematyczna oparta na sposobie definiowania CRC-32: bierzesz CRC-32 kodu, piszesz w kolejności little-endian (odwrotność kolejności bajtów, która jest zwykle używana w obliczeniach CRC-32 programy) i XOR z9D 0A D9 6D . Następnie dodajesz to do programu, a będziesz mieć program z CRC-32 równym 0. (Jako najprostszy możliwy przykład, łańcuch zerowy ma CRC-32 równą 0, a zatem 9D 0A D9 6Dma również CRC-32 równą 0 .)

Weryfikacja

Grusza może obsłużyć większość rodzajów mutacji, ale zakładam, że „zmieniony” oznacza „zastąpiony dowolnym oktetem”. Jest teoretycznie możliwe (choć mało prawdopodobne w tak krótkim programie), że gdzieś może dojść do kolizji skrótu, która prowadzi do nieprawidłowego działania programu, więc musiałem brutalnie sprawdzić, czy wszystkie możliwe podmiany oktetów spowodują, że program będzie działał poprawnie. Oto skrypt weryfikacyjny (napisany w Perlu), którego użyłem:

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!    ";

źródło
N -bitowego CRC wykryje każdy pojedynczy błąd nie dłużej niż rozerwanie n bitów. W tym przypadku kolizje hashowe są niemożliwe, nie ma potrzeby weryfikacji z użyciem siły brutalnej.
Rainer P.
@RainerP .: Zdaję sobie sprawę, że mutacja zapobiegnie CRC dla części, które pierwotnie mają CRC równe 0. Istnieje jednak możliwość, że może wprowadzić nowy podciąg kodu, który ma CRC równe 0; celem brutalnego wymuszania jest zagwarantowanie, że tak się nie stało.