Erkennen Sie, ob Ihr Programm mutiert wurde

16

Schreiben Sie ein Programm, das fehlerfrei beendet wird.

Wenn ein einzelnes Byte durch ein anderes Byte ersetzt wird, sollte das Programm dies ausgeben

CORRUPTED
  • Lesen Sie Ihren Quellcode nicht aus einer Datei
  • Ihr Programm sollte keine andere Ausgabe erzeugen

Das ist also gewinnt die kürzeste Antwort in Bytes.

Bearbeiten: Anforderung "NICHT KORRUPTIERT" entfernt

noɥʇʎԀʎzɐɹƆ
quelle
Das Strahlenhärten hat eine Reihe ähnlicher Fragen, aber ich habe keine gefunden, die dieser sehr ähnlich sind.
FryAmTheEggman
7
An die Downvoter: Ich vermute, dass dies möglich ist (wenn es sehr schwierig ist), wenn Sie die richtige Sprache auswählen. Bitte schließen oder löschen Sie die Frage nur, wenn Sie der Meinung sind, dass etwas nicht stimmt, außer dass dies unmöglich ist.
7
Was bedeutet geändert ? Ersetzt durch ein anderes Byte?
Dennis
4
@ ais523 FWIW Ich habe die Herausforderung abgelehnt, weil sie hastig geschrieben zu sein scheint, nicht weil ich sie für zu schwierig halte.
Dennis
5
Es ist nicht so, dass irgendetwas unklar ist, aber es könnte klarer formuliert werden . Sie könnten klären, ob ein vollständiges Programm erforderlich ist, ein Beispielprogramm hinzufügen und alle möglichen Änderungen veranschaulichen, erwähnen, wie sich Einzelbyte-Ersetzungen auf eine UTF-8-codierte Datei auswirken würden, ein Skript hinzufügen, das zum Testen von Einsendungen verwendet werden kann, und das Programm erwähnen sollte keine Eingaben machen, etc.
Dennis

Antworten:

30

Ein Birnbaum , 76 Bytes

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

Dieses Programm enthält einige streunende Oktette, die nicht für UTF-8 gültig sind. Als solches wird es so angezeigt, wie es in Windows-1252 aussieht. (Wenn A Pear Tree ein Nicht-ASCII-Oktett in einem String-Literal oder ähnlichem sieht, wird es standardmäßig als undurchsichtiges Objekt behandelt und versucht nicht, es zu verstehen, ohne zu wissen, um welchen Zeichencode es sich handelt. Dies kann sein.) geändert über eine Kodierungsdeklaration, aber das Programm hat keine. Das Programm befindet sich logischerweise in einem "nicht spezifizierten ASCII-kompatiblen Zeichensatz". Alle Nicht-ASCII-Oktette sind sowieso in Kommentaren, daher ist das eigentlich egal.)

Erläuterung

Ein Birnbaum prüft das Programm und sucht nach dem längsten Teilstring mit einem CRC-32 von 00000000. (Wenn es einen Gleichstand gibt, wählt es zuerst das Oktett.) Dann wird das Programm gedreht, um es an den Anfang zu setzen. Schließlich wird das Programm als eine Sprache interpretiert, die beinahe eine Obermenge von Perl darstellt und einige Dinge definiert, die in Perl nicht definiert sind, um auf die gleiche Weise wie in Python zu funktionieren (und mit ein paar geringfügigen Änderungen, z. B. printeine letzte neue Zeile in A Pear Tree ausgeben aber nicht in Perl). Dieser Mechanismus (und die Sprache als Ganzes) wurde für Probleme mit und entwickelt. das ist nicht das erstere, aber es ist definitiv das letztere.

In diesem Programm haben wir zwei bemerkenswerte Teilzeichenfolgen, die CRC-32 zu 00000000; Das gesamte Programm funktioniert und das auch print"$@CORRUPTED"__DATA__ =®®von selbst (was zweimal vorkommt). Als solcher, wenn das Programm nicht korrumpiert ist, wird es eingestellt $@auf NOT und dann drucken Sie es anschließend CORRUPTED. Wenn das Programm beschädigt ist, stimmt der CRC-32 des gesamten Programms nicht überein, einer der kürzeren Abschnitte bleibt jedoch unbeschädigt. Unabhängig davon, was zum Start des Programms gedreht wird CORRUPTED, wird nur gedruckt , ebenso $@wie die Nullzeichenfolge.

Wird __DATA__verwendet, um zu verhindern, dass der Rest des Programms ausgeführt wird, nachdem die Zeichenfolge gedruckt wurde . (Es __END__fällt mir ein, dies zu schreiben, das stattdessen verwendet werden könnte, was eindeutig zwei Bytes einsparen würde. Aber ich kann diese Version auch jetzt posten, da ich einige Zeit damit verbracht habe, sie zu überprüfen, und eine modifizierte Version müsste es sein Aufgrund der CRC-Änderungen erneut verifiziert, und ich habe noch keine großen Anstrengungen unternommen, um die "Nutzlast" zu ermitteln. Deshalb möchte ich herausfinden, ob jemand andere Verbesserungen in den Kommentaren vorgenommen hat, die ich gleichzeitig einbauen kann. Beachten Sie, dass #dies nicht funktioniert, wenn ein Zeichen in einer neuen Zeile beschädigt ist.)

Sie fragen sich vielleicht, wie ich es überhaupt geschafft habe, den CRC-32 meines Codes zu kontrollieren. Dies ist ein relativ einfacher mathematischer Trick, der auf der Art und Weise basiert, wie CRC-32 definiert ist: Sie nehmen den CRC-32 des Codes und schreiben ihn in Little-Endian-Reihenfolge (die Umkehrung der Byte-Reihenfolge, die normalerweise bei der CRC-32-Berechnung verwendet wird) Programme) und XOR mit 9D 0A D9 6D. Dann hängen Sie das an das Programm an, und Sie erhalten ein Programm mit einem CRC-32 von 0. (Als einfachstes Beispiel hat der Null-String einen CRC-32 von 0, also 9D 0A D9 6Dauch einen CRC-32 von 0.) .)

Nachprüfung

Ein Birnbaum kann mit den meisten Arten von Mutationen umgehen, aber ich gehe davon aus, dass "geändert" "durch ein beliebiges Oktett ersetzt" bedeutet. Theoretisch ist es möglich (obwohl es in einem so kurzen Programm unwahrscheinlich ist), dass es irgendwo zu einer Hash-Kollision kommt, die zur Ausführung des falschen Programms führt. Deshalb musste ich mit brachialer Gewalt prüfen, ob alle möglichen Oktettsubstitutionen dazu führen, dass das Programm ordnungsgemäß funktioniert. Hier ist das Überprüfungsskript (geschrieben in Perl), das ich verwendet habe:

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

quelle
Ein n- Bit-CRC erkennt jeden einzelnen Fehlerburst, der nicht länger als n Bits ist. Hash-Kollisionen sind im gegebenen Fall nicht möglich, eine Brute-Force-Überprüfung ist nicht erforderlich.
Rainer P.
@RainerP .: Mir ist bekannt, dass eine Mutation die CRC für die Teile verhindert, die ursprünglich eine CRC von 0 aufweisen. Es besteht jedoch die Möglichkeit, dass eine neue Teilzeichenfolge des Codes eingeführt wird, die eine CRC von 0 hat. Der Zweck der rohen Gewalt besteht darin, sicherzustellen, dass dies nicht geschehen ist.