webentwicklung-frage-antwort-db.com.de

Wie berechnet man die Entropie einer Datei?

Wie berechnet man die Entropie einer Datei? (Oder sagen wir einfach ein paar Bytes)
Ich habe eine Idee, bin mir aber nicht sicher, ob sie mathematisch korrekt ist.

Meine Idee ist folgende:

  • Erstellen Sie ein Array mit 256 Ganzzahlen (alle Nullen).
  • Durchsuchen Sie die Datei und für jedes ihrer Bytes,
    erhöhen Sie die entsprechende Position im Array.
  • Am Ende: Berechnen Sie den "Durchschnittswert" für das Array.
  • Initialisiere einen Zähler mit Null,
    und für jeden Eintrag des Arrays:
    Addiere die Differenz des Eintrags zum "Durchschnitt" des Zählers.

Nun, jetzt stecke ich fest. Wie kann man das Zählergebnis so "projizieren", dass alle Ergebnisse zwischen 0.0 und 1.0 liegen? Aber ich bin mir sicher, die Idee ist sowieso inkonsistent ...

Ich hoffe jemand hat bessere und einfachere Lösungen?

Hinweis: Ich brauche das Ganze, um Annahmen über den Inhalt der Datei zu treffen:
(Klartext, Markup, komprimiert oder eine Binärdatei, ...)

  • Am Ende: Berechnen Sie den "Durchschnittswert" für das Array.
  • Initialisieren Sie einen Zähler mit Null und fügen Sie für jeden Eintrag des Arrays die Differenz des Eintrags zum "Durchschnitt" des Zählers hinzu.

Mit einigen Modifikationen können Sie Shannons Entropie erhalten:

benenne "Durchschnitt" in "Entropie" um

(float) entropy = 0
for i in the array[256]:Counts do 
  (float)p = Counts[i] / filesize
  if (p > 0) entropy = entropy - p*lg(p) // lgN is the logarithm with base 2

Edit: Wie Wesley bereits erwähnt hat, müssen wir die Entropie durch 8 teilen, um sie im Bereich .. 1 anzupassen (alternativ können wir die logarithmische Basis 256 verwenden) .

47

Eine einfachere Lösung: gzip die Datei. Verwenden Sie das Verhältnis der Dateigrößen: (Größe des gezippten Dokuments)/(Größe des Originals) als Maß für die Zufälligkeit (d. H. Entropie).

Diese Methode gibt nicht den genauen absoluten Wert der Entropie an (da gzip kein "idealer" Kompressor ist), aber sie ist gut genug, wenn Sie die Entropie verschiedener Quellen vergleichen müssen.

31
Igor Krivokon

Um die Informationsentropie einer Sammlung von Bytes zu berechnen, müssen Sie etwas tun, das der Antwort von tydok ähnelt. (Tydoks Antwort funktioniert mit einer Sammlung von Bits.)

Es wird davon ausgegangen, dass die folgenden Variablen bereits vorhanden sind:

  • byte_counts ist eine 256-Elemente-Liste mit der Anzahl der Bytes für jeden Wert in Ihrer Datei. Zum Beispiel, byte_counts[2] ist die Anzahl der Bytes mit dem Wert 2.

  • total ist die Gesamtzahl der Bytes in Ihrer Datei.

Ich werde den folgenden Code in Python schreiben, aber es sollte klar sein, was los ist.

import math

entropy = 0

for count in byte_counts:
    # If no bytes of this value were seen in the value, it doesn't affect
    # the entropy of the file.
    if count == 0:
        continue
    # p is the probability of seeing this byte in the file, as a floating-
    # point number
    p = 1.0 * count / total
    entropy -= p * math.log(p, 256)

Es gibt einige wichtige Dinge, die zu beachten sind.

  • Der Scheck für count == 0 ist nicht nur eine Optimierung. Wenn count == 0, dann p == 0 und log ( p ) sind undefiniert ("negative infinity") und verursachen einen Fehler.

  • Das 256 im Aufruf an math.log steht für die Anzahl der möglichen diskreten Werte. Ein Byte, das aus acht Bits besteht, hat 256 mögliche Werte.

Der resultierende Wert liegt zwischen 0 (jedes einzelne Byte in der Datei ist gleich) und 1 (die Bytes werden gleichmäßig auf jeden möglichen Wert eines Bytes aufgeteilt).


Eine Erklärung für die Verwendung der Protokollbasis 256

Es ist richtig, dass dieser Algorithmus normalerweise auf der Basis von Protokoll 2 angewendet wird. Dies gibt die resultierende Antwort in Bits. In einem solchen Fall haben Sie maximal 8 Entropiebits für eine bestimmte Datei. Probieren Sie es selbst aus: Maximieren Sie die Entropie der Eingabe, indem Sie byte_counts eine Liste aller 1 oder 2 oder 100. Wenn die Bytes einer Datei gleichmäßig verteilt sind, gibt es eine Entropie von 8 Bits.

Es ist möglich, andere Logarithmusbasen zu verwenden. Die Verwendung von b = 2 ermöglicht ein Ergebnis in Bits, da jedes Bit 2 Werte haben kann. Die Verwendung von b = 10 setzt das Ergebnis in Stellen oder Dezimalstellen da gibt es 10 mögliche Werte für jeden dit. Die Verwendung von b = 256 ergibt das Ergebnis in Bytes, da jedes Byte einen von 256 diskreten Werten haben kann.

Interessanterweise können Sie mithilfe von Protokollidentitäten herausfinden, wie die resultierende Entropie zwischen Einheiten konvertiert wird. Jedes Ergebnis, das in Einheiten von Bits erhalten wird, kann durch Teilen durch 8 in Einheiten von Bytes umgewandelt werden. Als interessanter, absichtlicher Nebeneffekt ergibt sich daraus die Entropie als Wert zwischen 0 und 1.

In Summe:

  • Sie können verschiedene Einheiten verwenden, um die Entropie auszudrücken
  • Die meisten Menschen drücken Entropie in Bits aus ( b = 2)
    • Für eine Sammlung von Bytes ergibt dies eine maximale Entropie von 8 Bits
    • Da der Fragesteller ein Ergebnis zwischen 0 und 1 haben möchte, dividieren Sie dieses Ergebnis durch 8, um einen aussagekräftigen Wert zu erhalten
  • Der obige Algorithmus berechnet die Entropie in Bytes ( b = 256)
    • Dies entspricht (Entropie in Bits)/8
    • Dies ergibt bereits einen Wert zwischen 0 und 1
30
Wesley

Für das, was es wert ist, ist hier die traditionelle Berechnung (Bits of Entropy) in c # dargestellt

/// <summary>
/// returns bits of entropy represented in a given string, per 
/// http://en.wikipedia.org/wiki/Entropy_(information_theory) 
/// </summary>
public static double ShannonEntropy(string s)
{
    var map = new Dictionary<char, int>();
    foreach (char c in s)
    {
        if (!map.ContainsKey(c))
            map.Add(c, 1);
        else
            map[c] += 1;
    }

    double result = 0.0;
    int len = s.Length;
    foreach (var item in map)
    {
        var frequency = (double)item.Value / len;
        result -= frequency * (Math.Log(frequency) / Math.Log(2));
    }

    return result;
}
17
Jeff Atwood

Ist das etwas, das ent handhaben könnte? (Oder vielleicht ist es nicht auf Ihrer Plattform verfügbar.)

$ dd if=/dev/urandom of=file bs=1024 count=10
$ ent file
Entropy = 7.983185 bits per byte.
...

Als Gegenbeispiel sehen Sie hier eine Datei ohne Entropie.

$ dd if=/dev/zero of=file bs=1024 count=10
$ ent file
Entropy = 0.000000 bits per byte.
...
14
Peter Kovacs

Ich habe zwei Jahre Verspätung bei der Beantwortung. Bitte bedenken Sie dies trotz nur weniger Gegenstimmen.

Kurze Antwort: Verwenden Sie meine erste und dritte fett gedruckte Gleichung, um herauszufinden, woran die meisten Leute denken, wenn sie "Entropie" einer Datei in Bits sagen. Verwenden Sie nur die 1. Gleichung, wenn Sie Shannons H-Entropie wollen, die tatsächlich Entropie/Symbol ist, wie er in seiner Arbeit 13 Mal angegeben hat, was den meisten Menschen nicht bewusst ist. Einige Online-Entropie-Rechner verwenden diesen, aber Shannons H ist "spezifische Entropie", nicht "totale Entropie", was so viel Verwirrung gestiftet hat. Verwenden Sie die 1. und 2. Gleichung, wenn Sie eine Antwort zwischen 0 und 1 wünschen, bei der es sich um normalisierte Entropie/Symbol handelt (es handelt sich nicht um Bits/Symbol, sondern um ein echtes statistisches Maß für die "entropische Natur" der Daten, indem Sie die Daten ihre eigene Protokollbasis auswählen lassen anstatt willkürlich 2, e oder 10 zuzuweisen).

Es gibt 4 Arten von Entropie von Dateien (Daten) von N Symbolen mit n eindeutigen Symbolarten. Beachten Sie jedoch, dass Sie den Status einer Datei kennen und daher S = 0 sind, wenn Sie den Inhalt einer Datei kennen. Um genau zu sein, wenn Sie eine Quelle haben, die viele Daten generiert, auf die Sie zugreifen können, können Sie die erwartete zukünftige Entropie/den erwarteten zukünftigen Charakter dieser Quelle berechnen. Wenn Sie Folgendes für eine Datei verwenden, ist es genauer zu sagen, dass die erwartete Entropie anderer Dateien aus dieser Quelle geschätzt wird.

  • Shannon (spezifische) Entropie H = -1 * Summe (count_i/N * log (count_i/N)
    wobei count_i die Häufigkeit ist, mit der das Symbol i in N vorkam.
    Einheiten sind Bits/Symbole, wenn das Protokoll die Basis 2 ist, und Nats/Symbole, wenn das natürliche Protokoll ist.
  • Normalisierte spezifische Entropie: H/log (n)
    Einheiten sind Entropie/Symbol. Bereiche von 0 bis 1. 1 bedeutet, dass jedes Symbol gleich oft vorkam und in der Nähe von 0 alle Symbole außer 1 nur einmal vorkamen und der Rest einer sehr langen Datei das andere Symbol war. Das Protokoll befindet sich in derselben Basis wie das Protokoll H.
  • Absolute Entropie S = N * H
    Einheiten sind Bits, wenn log zur Basis 2 gehört, und nats, wenn ln ()).
  • Normalisierte absolute Entropie S = N · H/log (n)
    Einheit ist "Entropie", variiert von 0 bis N. Das Protokoll befindet sich in der gleichen Basis wie das H.

Obwohl die letzte die wahrste "Entropie" ist, ist die erste (Shannon-Entropie H) das, was alle Bücher "Entropie" nennen, ohne (die erforderliche IMHO-) Qualifikation. Die meisten erklären nicht (wie Shannon), dass es sich um Bits/Symbole oder Entropie pro Symbol handelt. H "Entropie" zu nennen, spricht zu locker.

Für Dateien mit der gleichen Häufigkeit jedes Symbols gilt: S = N * H = N. Dies ist bei den meisten großen Bitdateien der Fall. Entropy komprimiert die Daten nicht und kennt daher keinerlei Muster. Daher hat 000000111111 dasselbe H und S wie 010111101000 (in beiden Fällen 6 Einsen und 6 Nullen).

Wie bereits erwähnt, können Sie mit einer Standard-Komprimierungsroutine wie "gzip" und "Teilen vor und nach" die bereits vorhandene "Reihenfolge" in der Datei besser abschätzen. Dabei werden jedoch Daten berücksichtigt, die besser zum Komprimierungsschema passen. Es gibt keinen perfekt optimierten Allzweckkompressor, mit dem wir eine absolute "Reihenfolge" definieren können.

Eine weitere zu berücksichtigende Sache: H ändert sich, wenn Sie die Art und Weise ändern, wie Sie die Daten ausdrücken. H ist unterschiedlich, wenn Sie verschiedene Gruppierungen von Bits (Bits, Halbbytes, Bytes oder Hex) auswählen. Also dividieren Sie durch log (n), wobei n die Anzahl der eindeutigen Symbole in den Daten ist (2 für Binärdaten, 256 für Bytes) und H von 0 bis 1 reicht (dies ist normalisierte intensive Shannon-Entropie) in Einheiten der Entropie pro Symbol). Aber technisch gesehen, wenn nur 100 der 256 Arten von Bytes vorkommen, dann ist n = 100, nicht 256.

H ist eine "intensive" Entropie, d. H. Es ist pro Symbol, das analog ist zu spezifische Entropie in der Physik, die Entropie pro kg oder pro Mol ist. Regelmäßige "umfangreiche" Entropie einer Datei analog zu Physik 'S ist S = N * H wobei N die Anzahl der Symbole in der Datei ist. H wäre genau analog zu einem Teil eines idealen Gasvolumens. Die Informationsentropie kann nicht einfach in einem tieferen Sinne genau gleichgesetzt werden mit der physikalischen Entropie, da die physikalische Entropie sowohl "geordnete" als auch ungeordnete Anordnungen ermöglicht: Die physikalische Entropie ist mehr als eine völlig zufällige Entropie (wie eine komprimierte Datei). Ein Aspekt des Unterschieds Für ein ideales Gas gibt es einen zusätzlichen Faktor von 5/2, der dies erklärt: S = k * N * (H + 5/2) wobei H = mögliche Quantenzustände pro Molekül = (xp) ^ 3/hbar * 2 * Sigma ^ 2 wobei x = Breite des Kastens, p = ungerichteter Gesamtimpuls im System (berechnet aus kinetischer Energie und Masse pro Molekül) und Sigma = 0,341 gemäß dem Unsicherheitsprinzip, wobei nur die Anzahl von angegeben wird mögliche Zustände innerhalb von 1 std dev.

Ein bisschen Mathe ergibt eine kürzere Form einer normalisierten umfangreichen Entropie für eine Datei:

S = N · H/log (n) = Summe (count_i · log (N/count_i))/log (n)

Einheiten davon sind "Entropie" (was nicht wirklich eine Einheit ist). Es wird normalisiert, um ein besseres universelles Maß zu sein als die "Entropie" -Einheiten von N * H. Es sollte aber auch nicht ohne Klärung "Entropie" genannt werden, da die normale historische Konvention darin besteht, H fälschlicherweise "Entropie" zu nennen (was im Gegensatz zu "Entropie" steht) die Klarstellungen in Shannons Text).

12
zawy

Es gibt keine Entropie einer Datei. In der Informationstheorie ist die Entropie eine Funktion einer Zufallsvariablen, nicht eines festen Datensatzes (technisch gesehen hat ein fester Datensatz eine Entropie, aber diese Entropie wäre 0 - das können wir betrachten die Daten als zufällige Verteilung, die nur ein mögliches Ergebnis mit der Wahrscheinlichkeit 1) hat.

Um die Entropie zu berechnen, benötigen Sie eine Zufallsvariable, mit der Sie Ihre Datei modellieren können. Die Entropie ist dann die Entropie der Verteilung dieser Zufallsvariablen. Diese Entropie entspricht der Anzahl der in dieser Zufallsvariablen enthaltenen Informationsbits.

10
Adam Rosenfield

Wenn Sie die informationstheoretische Entropie verwenden, ist es möglicherweise sinnvoll, sie nicht für Bytes zu verwenden. Wenn Ihre Daten aus Floats bestehen, sollten Sie stattdessen eine Wahrscheinlichkeitsverteilung an diese Floats anpassen und die Entropie dieser Verteilung berechnen.

Wenn der Inhalt der Datei aus Unicode-Zeichen besteht, sollten Sie diese usw. verwenden.

5
bayer

Betreff: Ich brauche das Ganze, um Annahmen über den Inhalt der Datei zu treffen: (Klartext, Markup, Komprimiert oder eine Binärdatei, ...)

Wie andere darauf hingewiesen haben (oder von verwirrt/abgelenkt wurden), spreche ich tatsächlich von metrische Entropie (Entropie geteilt durch Länge der Nachricht). Weitere Informationen finden Sie unter Entropie (Informationstheorie) - Wikipedia .

der Kommentar von Jitter, der mit Daten auf Entropieanomalien scannen verknüpft ist, ist für Ihr zugrunde liegendes Ziel sehr relevant. Das führt schließlich zu libdisorder (C-Bibliothek zur Messung der Byte-Entropie) . Dieser Ansatz scheint Ihnen viel mehr Informationen zu bieten, da er zeigt, wie sich die metrische Entropie in verschiedenen Teilen der Datei unterscheidet. Siehe z. Dieses Diagramm zeigt, wie sich die Entropie eines 256-Byte-Blocks aus einem 4-MB-JPG-Bild (y-Achse) für verschiedene Offsets (x-Achse) ändert. Zu Beginn und am Ende ist die Entropie niedriger, da sie teilweise eintritt, aber für den größten Teil der Datei sind es ungefähr 7 Bits pro Byte.

enter image description here Quelle: https://github.com/cyphunk/entropy_examples . [ Beachten Sie, dass diese und andere Grafiken über den Roman verfügbar sind http://nonwhiteheterosexualmalelicense.org license ....]

Interessanter ist die Analyse und ähnliche Grafiken unter Analyse der Byte-Entropie einer FAT-formatierten Platte | GL.IB.LY

Statistiken wie Max, Min, Modus und Standardabweichung der Metrikentropie für die gesamte Datei und/oder den ersten und letzten Block davon können als Signatur sehr hilfreich sein.

Dieses Buch scheint ebenfalls relevant zu sein: Erkennung und Erkennung von Dateimasquerading für E-Mail und Datensicherheit - Springer

2
nealmcb

Berechnet die Entropie einer beliebigen Zeichenfolge ohne Vorzeichen der Größe "Länge". Dies ist im Grunde eine Überarbeitung des Codes unter http://rosettacode.org/wiki/Entropy . Ich verwende dies für einen 64-Bit-IV-Generator, der einen Container mit 100000000 IVs ohne Dupes und einer durchschnittlichen Entropie von 3,9 erstellt. http://www.quantifiedtechnologies.com/Programming.html

#include <string>
#include <map>
#include <algorithm>
#include <cmath>
typedef unsigned char uint8;

double Calculate(uint8 * input, int  length)
  {
  std::map<char, int> frequencies;
  for (int i = 0; i < length; ++i)
    frequencies[input[i]] ++;

  double infocontent = 0;
  for (std::pair<char, int> p : frequencies)
  {
    double freq = static_cast<double>(p.second) / length;
    infocontent += freq * log2(freq);
  }
  infocontent *= -1;
  return infocontent;
 }
2
iggy_pop