Perbandingan entropi dan distribusi byte dalam data terkompresi / terenkripsi

8

Saya punya beberapa pertanyaan yang cukup lama.

Tes entropi sering digunakan untuk mengidentifikasi data yang dienkripsi. Entropi mencapai maksimum ketika byte dari data yang dianalisis didistribusikan secara seragam. Tes entropi mengidentifikasi data yang dienkripsi, karena data ini memiliki data terkompresi seperti distribusi yang seragam, yang diklasifikasikan sebagai terenkripsi ketika menggunakan tes entropi.

Contoh: Entropi dari beberapa file JPG adalah 7.9961532 Bits / Byte, entropi dari beberapa TrueCrypt-container adalah 7.9998857. Ini berarti dengan tes entropi saya tidak dapat mendeteksi perbedaan antara data terenkripsi dan terkompresi. TAPI: seperti yang Anda lihat pada gambar pertama, jelas byte dari file JPG tidak didistribusikan secara seragam (setidaknya tidak seragam seperti byte dari truecrypt-container).

Tes lain dapat berupa analisis frekuensi. Distribusi setiap byte diukur dan misalnya uji chi-square dilakukan untuk membandingkan distribusi dengan distribusi hipotesis. sebagai hasilnya, saya mendapatkan nilai-p. ketika saya melakukan tes ini pada JPG dan TrueCrypt-data, hasilnya berbeda.

Nilai p dari file JPG adalah 0, yang berarti bahwa distribusi dari tampilan statistik tidak seragam. Nilai p dari file TrueCrypt adalah 0,95, yang berarti bahwa distribusinya hampir seragam sempurna.

Pertanyaan saya sekarang: Dapatkah seseorang memberi tahu saya mengapa tes entropi menghasilkan positif palsu seperti ini? Apakah ini skala unit, di mana konten informasi diekspresikan (bit per byte)? Apakah misalnya p-value "unit" jauh lebih baik, karena skala yang lebih halus?

Terima kasih banyak atas jawaban / ide!

JPG-Image masukkan deskripsi gambar di sini TrueCrypt-Container masukkan deskripsi gambar di sini

tommynogger
sumber
2
Meskipun Anda memberikan dua contoh entropi, Anda tidak benar-benar menerapkan apa pun yang disebut "tes Entropi." Bisakah Anda secara eksplisit memberi tahu kami apa tes itu dan bagaimana cara kerjanya dengan dua file Anda?
whuber
Anda harus dapat memposting gambar sekarang. Harap berikan beberapa detail lebih lanjut sesuai komentar @ whuber.
kardinal
Untuk entropi, saya menghitung probabilitas setiap angka (0-255) muncul. maka saya meringkas semua log (probabilitas) dan memiliki entropi. perangkat lunak seperti encase, yang digunakan untuk pemeriksaan forensik, menggunakan entropi untuk mendeteksi data terenkripsi. tetapi seperti yang Anda lihat, entropi mengarah ke banyak positif palsu. pendekatan lain, seperti chi square, memiliki hasil yang jauh lebih baik. tetapi dua tes digunakan untuk hal yang sama, mendeteksi keseragaman byte. bagaimana hasilnya bisa sangat berbeda?
tommynogger
maaf, uraian saya salah ... Saya menghitung jumlah entropi (p log p), di mana p adalah probabilitas untuk setiap angka.
tommynogger
Saya pikir sangat mungkin Anda salah menghitung entropi. Mungkin ada baiknya memberikan lebih banyak detail dan beberapa kode sampel. Sudahkah Anda menormalkan distribusi probabilitas dengan benar (sehingga jumlahnya menjadi satu). Bagaimana Anda melakukannya dengan lebih detail? Apakah kedua ilustrasi itu memiliki skala y yang sama? jika ya maka saya pikir entropi JPEG harus lebih rendah, tetapi apakah mereka pada skala yang sama?
Thrope

Jawaban:

6

Pertanyaan ini masih kekurangan informasi penting, tapi saya pikir saya bisa membuat beberapa tebakan cerdas:

  • The entropi dari suatu distribusi diskritp=(p0,p1,,p255) didefinisikan sebagai

    H(p)=i=0255pilog2pi.
  • Karena log adalah fungsi cekung, entropi dimaksimalkan ketika semuanya piadalah sama. Karena mereka menentukan distribusi probabilitas (mereka berjumlah satu), ini terjadi ketikapi=28 untuk setiap i, dari mana entropi maksimum adalah

    H0=i=025528log2(28)=i=025528×8=8.
  • Entropi dari 7.9961532bit / byte ( yaitu , menggunakan logaritma biner) dan7.9998857 sangat dekat satu sama lain dan dengan batas teoritis H0=8.

    Betapa dekat? MemperluasH(p) dalam seri Taylor sekitar maksimum menunjukkan bahwa penyimpangan antara H0 dan entropi apa pun H(p) sama dengan

    H0H(p)=i(pi28)2228log(2)+O(pi28)3.

    Dengan menggunakan rumus ini kita dapat menyimpulkan bahwa entropi dari 7.9961532, yang merupakan perbedaan 0.0038468, Diproduksi oleh deviasi akar-rata-kuadrat dari adil 0.00002099 diantara pi dan distribusi seragam yang sempurna 28. Ini mewakili penyimpangan relatif rata-rata saja0.5%. Perhitungan serupa untuk entropi7.9998857 sesuai dengan penyimpangan RMS di pi hanya 0,09%.

    (Pada gambar seperti yang paling bawah dalam pertanyaan, yang tingginya berkisar sekitar 1000 piksel, jika kami menganggap ketinggian bilah mewakili pi, lalu a 0.09% Variasi RMS sesuai dengan perubahan hanya satu piksel di atas atau di bawah tinggi rata-rata, dan hampir selalu kurang dari tiga piksel. Seperti itulah tampilannya. SEBUAH0.5% RMS, di sisi lain, akan dikaitkan dengan variasi tentang 6 piksel rata-rata, tetapi jarang melebihi 15piksel atau lebih. Itulah tidak apa sosok penampilan atas suka, dengan variasi yang nyata dari100atau lebih banyak piksel. Karena itu saya menduga bahwa angka-angka ini tidak dapat dibandingkan secara langsung satu sama lain.)

Dalam kedua kasus ini adalah penyimpangan kecil, tetapi satu lebih dari lima kali lebih kecil dari yang lain. Sekarang kita harus membuat beberapa tebakan, karena pertanyaannya tidak memberi tahu kita bagaimana entropi digunakan untuk menentukan keseragaman, juga tidak memberi tahu kita berapa banyak data yang ada. Jika "tes entropi" yang sebenarnya telah diterapkan, maka seperti tes statistik lainnya, tes ini perlu memperhitungkan variasi peluang. Dalam hal ini, frekuensi yang diamati (dari mana entropi telah dihitung) akan cenderung bervariasi dari frekuensi dasar yang sebenarnya karena kebetulan. Variasi ini menerjemahkan, melalui rumus yang diberikan di atas, ke dalam variasi entropi yang diamati dari entropi yang mendasarinya. Diberikan data yang cukup, kita dapat mendeteksi apakah entropi yang benar berbeda dari nilai 8terkait dengan distribusi yang seragam. Semua hal lain dianggap sama, jumlah data yang diperlukan untuk mendeteksi perbedaan rata-rata hanya0.09% dibandingkan dengan perbedaan rata - rata 0.5% akan menjadi sekitar (0.5/0.09)2 kali lebih banyak: dalam hal ini, hasilnya lebih dari 33 kali lebih banyak.

Akibatnya, sangat mungkin ada data yang cukup untuk menentukan bahwa entropi yang diamati 7.996berbeda secara signifikan dari8 sementara jumlah data yang setara tidak dapat dibedakan 7.99988 dari 8. (Situasi ini, omong-omong, disebut negatif palsu , bukan "positif palsu," karena telah gagal mengidentifikasi kurangnya keseragaman (yang dianggap sebagai hasil "negatif").) Dengan demikian, saya mengusulkan bahwa (a ) entropi memang telah dihitung dengan benar dan (b) jumlah data cukup menjelaskan apa yang telah terjadi.


Kebetulan, angka-angka itu tampaknya tidak berguna atau menyesatkan, karena mereka tidak memiliki label yang sesuai. Meskipun bagian bawah tampak menggambarkan distribusi yang hampir seragam (dengan asumsi sumbu x terpisah dan sesuai dengan256 nilai byte yang mungkin dan sumbu y sebanding dengan frekuensi yang diamati), yang teratas tidak mungkin sesuai dengan entropi di dekat 8. Saya menduga nol dari sumbu y pada gambar atas belum diperlihatkan, sehingga perbedaan di antara frekuensi dilebih-lebihkan. (Tufte akan mengatakan angka ini memiliki Faktor Kebohongan besar.)

whuber
sumber
Entropi yang dihitung mengacu pada gambar di atas. File JPG memiliki ukuran sekitar 5MB, TrueCrypt-Container sekitar 100MB. Bahkan jika saya mengambil 5MB TrueCrypt-Container, itu terdistribusi secara merata - jauh lebih sama daripada file JPG. Jawaban Anda memberi banyak detail tentang entropi yang belum saya dengar, terima kasih untuk ini! Mungkin beberapa detail terlalu banyak, saya tidak terlalu ke statistik ... Saya baru saja mencoba "menggunakan" statistik untuk sementara waktu. Masih ada satu pertanyaan: Apa alasan mengapa perbedaan dapat dibuat dengan analisis frekuensi (misalnya chi square), tetapi tidak dengan entropi?
tommynogger
Tes chi kuadrat menyumbang kemungkinan jumlah variasi peluang. Sejauh yang saya tahu, perbandingan entropi Anda tidak. Itu tampaknya menjadi sumber perbedaan. Anda juga perlu berhati-hati bagaimana Anda menafsirkan hasil: hal dapat juga merata ; yang juga bisa diambil sebagai bukti terhadap perilaku acak.
whuber