Определите, была ли ваша программа видоизменена

16

Напишите программу, которая завершается без ошибок.

Если какой-либо один байт заменяется любым другим байтом, программа должна вывести

CORRUPTED
  • Не читайте ваш исходный код из файла
  • Ваша программа не должна производить никаких других выводов

Это поэтому выигрывает самый короткий ответ в байтах.

Редактировать: удалено требование «НЕ ИСПРАВЛЕНО»

noɥʇʎԀʎzɐɹƆ
источник
У радиационной закалки есть множество подобных вопросов, но я не нашел ни одного, который был бы похож на этот.
FryAmTheEggman
7
Для нижестоящих: Я подозреваю, что это возможно (если очень сложно), если вы выберете правильный язык. Пожалуйста, не закрывайте и не удаляйте вопрос, если не считаете, что с ним что-то не так, кроме невозможного.
7
Что значит изменилось ? Заменен другим байтом?
Денис
4
@ ais523 FWIW Я отклонил вызов, потому что он написан на скорую руку, а не потому, что я думаю, что это слишком сложно.
Деннис
5
Это не значит, что что-то неясно, но это можно сделать более понятным . Вы можете уточнить, требуется ли полная программа, добавить пример программы и проиллюстрировать все возможные модификации, указать, как однобайтовые замены влияют на файл в кодировке UTF-8, добавить сценарий, который можно использовать для проверки представлений, упомянуть, что программа не должны принимать участие и т. д.
Денис

Ответы:

30

Груша , 76 байт

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

Эта программа содержит несколько случайных октетов, которые не являются допустимыми UTF-8. Таким образом, он выглядит так, как выглядит в Windows-1252. (По умолчанию, если A Pear Tree видит не-ASCII октет в строковом литерале или тому подобное, он обрабатывает его как непрозрачный объект и не пытается понять его, не зная, каков его код символа; такое поведение может быть изменено с помощью объявления кодировки, но у программы его нет. Таким образом, программа логически находится в «неопределенном ASCII-совместимом наборе символов». Все не-ASCII-октеты в любом случае находятся в комментариях, поэтому это не имеет значения.)

объяснение

Pear Tree проверяет контрольную сумму программы в поисках самой длинной подстроки с CRC-32 00000000. (Если есть связь, сначала выбирается октетбетически.) Затем программа поворачивается, чтобы поставить ее в начале. Наконец, программа интерпретируется как язык, который является почти надмножеством Perl, определяя несколько вещей, которые не определены в Perl, чтобы работать так же, как в Python (и с некоторыми незначительными изменениями, например, printпечатать последний перевод строки в A Pear Tree но не в Perl). Этот механизм (и язык в целом) был разработан для проблем и ; это не первое, но определенно второе.

В этой программе у нас есть две заметные подстроки, которые CRC-32 00000000; вся программа делает то же print"$@CORRUPTED"__DATA__ =®®самое и сама (которая появляется дважды). Таким образом , если программа неповрежденная, она будет установлена $@на , NOT а затем распечатать его последующим CORRUPTED. Если программа повреждена, то CRC-32 программы в целом не будет соответствовать, но один из более коротких разделов останется не поврежденным. Независимо от того, кто из них повернут к началу программы, просто напечатается CORRUPTED, как $@и пустая строка.

Как только строка напечатана, __DATA__она используется для предотвращения запуска остальной части программы. (Мне пришло в голову написать этот текст, который __END__можно было бы использовать вместо этого, что явно сэкономило бы два байта. Но я могу также опубликовать эту версию сейчас, потому что я потратил кучу времени на ее проверку, и модифицированная версия должна быть перепроверен из-за изменений CRC, и я еще не приложил огромных усилий для игры в «полезную нагрузку», поэтому я хочу посмотреть, есть ли у кого-то другие улучшения в комментариях, которые я могу включить одновременно. Обратите внимание, что #не работает в ситуации, когда символ поврежден в новую строку.)

Вы можете быть удивлены, как мне удалось контролировать CRC-32 моего кода. Это довольно простой математический прием, основанный на способе определения CRC-32: вы берете код CRC-32, записываете его в порядке с прямым порядком байтов (обратный порядок байтов, который обычно используется при вычислении CRC-32). программы) и XOR с 9D 0A D9 6D. Затем вы добавляете это к программе, и у вас будет программа с CRC-32, равным 0. (Как простейший возможный пример, нулевая строка имеет CRC-32, равный 0, таким образом, 9D 0A D9 6Dтакже имеет CRC-32, равный 0. .)

верификация

Грушевое дерево может обрабатывать большинство видов мутаций, но я предполагаю, что «измененный» означает «замененный произвольным октетом». Теоретически возможно (хотя и маловероятно, что в такой короткой программе) может быть где-то коллизия хешей, которая приведет к неправильной работе программы, поэтому мне пришлось проверить с помощью грубой силы, что все возможные замены октетов оставят программу работающей правильно. Вот скрипт проверки (написанный на Perl), который я использовал:

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

источник
П -битовый CRC обнаружит какой - либо одной ошибки лопнуть не больше , чем п бит. В данном случае хеш-коллизии невозможны, нет необходимости в грубой проверке.
Райнер П.
@RainerP .: Я знаю, что мутация предотвратит CRC для частей, которые изначально имеют совпадение CRC 0. Однако есть вероятность, что он может ввести новую подстроку кода, которая имеет CRC 0; Цель грубого принуждения - гарантировать, что этого не произошло.