Deteksi jika program Anda telah dimutasi

16

Tulis program yang berakhir tanpa kesalahan.

Jika ada byte tunggal yang diganti oleh byte lain, program akan menampilkan

CORRUPTED
  • Jangan membaca kode sumber Anda dari file
  • Program Anda seharusnya tidak menghasilkan output lain

Ini adalah sehingga jawaban tersingkat dalam byte menang.

Sunting: dihapus "NOT CORRUPTED"

noɥʇʎԀʎzɐɹƆ
sumber
pengerasan radiasi memiliki sejumlah pertanyaan serupa, tetapi saya belum menemukan yang cukup seperti ini.
FryAmTheEggman
7
Untuk para downvoters: Saya kira ini mungkin (jika sangat sulit), jika Anda memilih bahasa yang tepat. Tolong jangan menutup atau menghapus pertanyaan kecuali Anda berpikir ada yang salah dengan itu selain tidak mungkin.
7
Apa artinya berubah ? Digantikan oleh byte lain?
Dennis
4
@ ais523 FWIW Saya menolak tantangan karena tampaknya tergesa-gesa ditulis, bukan karena saya pikir itu terlalu sulit.
Dennis
5
Bukannya ada sesuatu yang tidak jelas, tetapi bisa dibuat lebih jelas . Anda dapat mengklarifikasi jika program lengkap diperlukan, menambahkan contoh program dan menggambarkan semua modifikasi yang mungkin, menyebutkan bagaimana penggantian byte tunggal akan mempengaruhi file yang dikodekan UTF-8, tambahkan skrip yang dapat digunakan untuk menguji pengiriman, menyebutkan bahwa program tidak boleh mengambil input, dll.
Dennis

Jawaban:

30

Pohon Pir , 76 byte

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

Program ini mengandung beberapa oktet nyasar yang tidak valid UTF-8. Dengan demikian, ditampilkan seperti pada Windows-1252. (Secara default, jika A Pear Tree melihat oktet non-ASCII dalam string literal atau sejenisnya memperlakukannya sebagai objek buram dan tidak mencoba memahaminya selain menyadari apa kode karakternya; perilaku ini dapat berupa diubah melalui deklarasi penyandian tetapi program tidak memilikinya. Jadi program ini secara logis dalam "set karakter yang kompatibel dengan ASCII yang tidak ditentukan."

Penjelasan

Sebuah Pear Tree checksum program, mencari substring terpanjang yang memiliki CRC-32 00000000. (Jika ada dasi, maka akan memilih oktetika terlebih dahulu.) Kemudian program diputar untuk meletakkannya di awal. Akhirnya, program ditafsirkan sebagai bahasa yang hampir superset dari Perl, mendefinisikan beberapa hal yang tidak terdefinisi dalam Perl untuk bekerja dengan cara yang sama seperti di Python (dan dengan beberapa perubahan kecil, misalnya printmencetak baris baru terakhir di A Pear Tree tapi tidak di Perl). Mekanisme ini (dan bahasa secara keseluruhan) dirancang untuk masalah dan ; ini bukan yang pertama, tapi jelas yang terakhir.

Dalam program ini, kami memiliki dua substring penting yang CRC-32 untuk 00000000; seluruh program tidak, dan begitu jugaprint"$@CORRUPTED"__DATA__ =®® dengan sendirinya (yang muncul dua kali). Dengan demikian, jika program tidak rusak, itu akan diatur $@ke NOT dan kemudian cetak diikuti oleh CORRUPTED. Jika program rusak, maka CRC-32 program secara keseluruhan akan gagal untuk mencocokkan, tetapi salah satu bagian yang lebih pendek akan tetap tidak rusak. Mana pun yang dirotasi ke awal program hanya akan mencetak CORRUPTED, sebagaimana $@akan menjadi string nol.

Setelah string sudah dicetak, __DATA__digunakan untuk mencegah sisa program berjalan. (Melintas dalam pikiran saya menulis ini yang __END__dapat digunakan sebagai gantinya, yang jelas akan menghemat dua byte. Tapi saya mungkin juga memposting versi ini sekarang, karena saya telah menghabiskan banyak waktu untuk memverifikasi itu, dan versi yang dimodifikasi harus diverifikasi ulang karena perubahan CRC, dan saya belum melakukan upaya besar dalam mem-golf "payload", jadi saya ingin melihat apakah ada yang memiliki peningkatan lain dalam komentar yang dapat saya sertakan pada saat yang sama. Catatan yang #tidak berfungsi dalam situasi di mana karakter rusak ke baris baru.)

Anda mungkin bertanya-tanya bagaimana saya berhasil mengendalikan CRC-32 kode saya di tempat pertama. Ini adalah trik matematika yang cukup sederhana berdasarkan cara CRC-32 didefinisikan: Anda mengambil CRC-32 dari kode, menuliskannya dalam urutan little-endian (kebalikan dari urutan byte yang biasanya digunakan oleh perhitungan CRC-32 program), dan XOR dengan9D 0A D9 6D . Kemudian Anda menambahkannya ke program, dan Anda akan memiliki program dengan CRC-32 dari 0. (Sebagai contoh sesederhana mungkin, string nol memiliki CRC-32 dari 0, sehingga 9D 0A D9 6Djuga memiliki CRC-32 dari 0 .)

Verifikasi

Pohon Pir dapat menangani sebagian besar jenis mutasi, tetapi saya mengasumsikan "diubah" berarti "diganti dengan oktet sewenang-wenang". Secara teori dimungkinkan (walaupun tidak mungkin dalam program sependek ini) bahwa mungkin ada tabrakan hash di suatu tempat yang menyebabkan program salah berjalan, jadi saya harus memeriksa melalui brute force bahwa semua kemungkinan penggantian oktet akan membuat program bekerja dengan benar. Berikut skrip verifikasi (ditulis dalam Perl) yang saya gunakan:

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

sumber
Sebuah n -bit CRC akan mendeteksi setiap kesalahan tunggal meledak tidak lebih dari n bit. Tabrakan Hash tidak mungkin dalam kasus yang diberikan, tidak perlu untuk verifikasi brute-force.
Rainer P.
@RainerP .: Saya sadar bahwa mutasi akan mencegah CRC untuk bagian yang awalnya memiliki CRC 0 yang cocok. Namun, ada kemungkinan bahwa itu dapat memperkenalkan substring baru dari kode yang memiliki CRC 0; tujuan dari kekerasan itu adalah untuk menjamin bahwa itu tidak terjadi.