Как рассчитать энтропию файла?

Question

Как рассчитать энтропию файла? (или, скажем, несколько байтов)
У меня есть идея, но я не уверен, что она математически верна.

Моя идея заключается в следующем:

• Создать массив из 256 целых чисел (все нули).
• Переход по файлу и для каждого из его байтов,
  увеличить соответствующую позицию в массиве.
• В конце: вычислить «среднее» значение для массива.
• Инициализировать счетчик с нуля,
  и для каждой записи массива:
  добавить разницу в записи «в среднем» к счетчику.

Ну, теперь я застрял. Как «спроецировать» счетчик таким образом что все результаты будут лежать между 0,0 и 1,0? Но я уверен, в любом случае идея противоречива ...

Надеюсь, у кого-то есть лучшие и более простые решения?

Примечание. Мне нужно все, чтобы сделать предположения относительно содержимого файла:
(открытый текст, разметка, сжатый или некоторый двоичный файл, ...)

Answer 1

• В конце: вычислить «среднее» значение для массива.
• Инициализировать счетчик с нуля, и для каждой записи массива: добавьте разность записи к «среднему» к счетчику.

С некоторыми модификациями вы можете получить энтропию Шеннона:

переименуйте «среднее» в «энтропию»

(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: Как упоминал Уэсли, мы должны разделить энтропию на 8, чтобы скорректировать ее в диапазоне 0. , 1 (или, альтернативно, мы можем использовать логарифмическое основание 256).

Answer 2

Чтобы рассчитать информационную энтропию набора байтов, вам нужно сделать что-то похожее на ответ Тыдока. (ответ Тыдока работает над набором битов.)

Предполагается, что следующие переменные уже существуют:

• byte_counts - это 256-элементный список количества байтов с каждым значением в вашем файле. Например, byte_counts[2] - это число байтов со значением 2.

• total - общее количество байтов в вашем файле.

Я напишу следующий код на Python, но должно быть очевидно, что происходит.

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)

Есть несколько вещей, на которые важно обратить внимание.

• Проверка для count == 0 - это не просто оптимизация. Если count == 0, то p == 0 и log ( p ) будут неопределенными («отрицательная бесконечность»), что приведет к ошибке.

• 256 в вызове math.log представляет количество возможных дискретных значений. Байт, состоящий из восьми битов, будет иметь 256 возможных значений.

Результирующее значение будет находиться в диапазоне от 0 (все байты в файле одинаковы) до 1 (байты равномерно делятся между всеми возможными значениями байта).

---

Объяснение использования базы журнала 256

Это правда, что этот алгоритм обычно применяется с использованием базы журнала 2. Это дает полученный ответ в битах. В таком случае у вас есть максимум 8 бит энтропии для любого данного файла. Попробуйте сами: максимизируйте энтропию ввода, составив byte_counts список всех 1 или 2 или 100. Когда байты файла распределены равномерно, вы обнаружите, что энтропия составляет 8 бит.

Возможно использование других основ логарифма. Использование b = 2 позволяет получить результат в битах, поскольку каждый бит может иметь 2 значения. Использование b = 10 приводит к результату в dits или десятичных битах, поскольку для каждого dit существует 10 возможных значений. Использование b = 256 даст результат в байтах, поскольку каждый байт может иметь одно из 256 дискретных значений.

Интересно, что используя идентификаторы журналов, вы можете решить, как преобразовать полученную энтропию между единицами. Любой результат, полученный в единицах битов, может быть преобразован в единицы байтов путем деления на 8. Как интересный, преднамеренный побочный эффект, это дает энтропию как значение от 0 до 1.

В итоге:

• Вы можете использовать различные единицы для выражения энтропии
• Большинство людей выражают энтропию в битах ( b = 2)
  • Для набора байтов это дает максимальную энтропию 8 битов
  • Поскольку просящий хочет получить результат от 0 до 1, разделите этот результат на 8 для значимого значения
• Приведенный выше алгоритм вычисляет энтропию в байтах ( b = 256)
  • Это эквивалентно (энтропия в битах) / 8
  • Это уже дает значение от 0 до 1

Answer 3

Более простое решение: сжать файл. Используйте соотношение размеров файлов: (size-of-gzipped) / (size-of-original) в качестве меры случайности (то есть энтропии).

Этот метод не дает точного абсолютного значения энтропии (поскольку gzip не является «идеальным» компрессором), но он достаточно хорош, если вам нужно сравнивать энтропию разных источников.

Answer 4

Для чего это стоит, вот традиционные (биты энтропии) вычисления, представленные в c #

/// <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;
}

Answer 5

Это то, с чем ent может справиться? (Или, возможно, его нет на вашей платформе.)

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

В качестве встречного примера приведен файл без энтропии.

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

Answer 6

Я опоздал с ответом на два года, поэтому, пожалуйста, учтите это, несмотря на то, что проголосовали только несколько раз.

Краткий ответ: используйте мои 1-е и 3-е смелые уравнения, приведенные ниже, чтобы получить то, о чем думает большинство людей, когда они говорят "энтропия" файла в битах. Используйте только 1-е уравнение, если вы хотите энтропию Шеннона, которая на самом деле является энтропией / символом, как он 13 раз говорил в своей статье, о которой большинство людей не знают. Некоторые онлайн-калькуляторы энтропии используют этот, но H Шеннона - это «специфическая энтропия», а не «полная энтропия», которая вызывает столько путаницы. Используйте 1-е и 2-е уравнение, если вы хотите получить ответ между 0 и 1, который является нормализованной энтропией / символом (это не биты / символ, а истинная статистическая мера "энтропийной природы" данных, позволяя данным выбирать свою собственную базу журналов вместо произвольного присвоения 2, е или 10).

Там 4 типа энтропии файлов (данных) длиной N символов с n уникальными типами символов. Но имейте в виду, что, зная содержимое файла, вы знаете его состояние и, следовательно, S = 0. Если быть точным, если у вас есть источник, который генерирует много данных, к которым у вас есть доступ, вы можете рассчитать ожидаемую будущую энтропию / характер этого источника. Если вы используете в отношении файла следующее, более правильно будет сказать, что он оценивает ожидаемую энтропию других файлов из этого источника.

• Энтропия Шеннона (специфическая) H = -1 * сумма (count_i / N * log (count_i / N))
  где count_i - количество символов, которое я встретил в N.
  Единицы - биты / символ, если log - основание 2, нац / символ, если натуральный лог.
• Нормализованная удельная энтропия: H / log (n)
  Единицы энтропии / символа. Диапазон от 0 до 1. 1 означает, что каждый символ встречался одинаково часто, а около 0 все символы, кроме 1, встречались только один раз, а остальная часть очень длинного файла была другим символом. Журнал находится в той же базе, что и H.
• Абсолютная энтропия S = N * H
  Единицы - биты, если log - это основание 2, nats - если ln ()).
• Нормализованная абсолютная энтропия S = N * H / log (n)
  Единица «энтропия», варьируется от 0 до N. Журнал находится в той же базе, что и H.

Хотя последняя является истинной «энтропией», первая (энтропия Шеннона H) - это то, что все книги называют «энтропией» без (необходимого ИМХО) квалификации. Большинство не уточняет (как это сделал Шеннон), что это бит / символ или энтропия на символ. Называть H "энтропией" - значит говорить слишком свободно.

Для файлов с одинаковой частотой каждого символа: S = N * H = N. Это касается большинства больших файлов битов. Энтропия не производит никакого сжатия данных и, таким образом, полностью игнорирует любые шаблоны, поэтому 000000111111 имеет те же H и S, что и 010111101000 (6 1 и 6 0 в обоих случаях).

Как уже говорили другие, использование стандартной процедуры сжатия, такой как gzip и деление до и после, даст лучшую меру количества ранее существовавшего «порядка» в файле, но это смещено по отношению к данным, которые соответствуют схеме сжатия лучше. Не существует полностью оптимизированного компрессора общего назначения, который мы могли бы использовать для определения абсолютного «порядка».

Еще одна вещь, которую следует учитывать: H меняется, если вы меняете способ выражения данных. H будет другим, если вы выберете разные группы битов (биты, кусочки, байты или шестнадцатеричные значения). Таким образом, вы делите на log (n) где n - количество уникальных символов в данных (2 для двоичного, 256 для байтов), а H будет варьироваться от 0 до 1 (это нормализованная интенсивная энтропия Шеннона в единицы энтропии на символ). Но технически, если встречается только 100 из 256 типов байтов, тогда n = 100, а не 256.

H - это «интенсивная» энтропия, то есть для каждого символа она аналогична удельной энтропии в физике, которая представляет собой энтропию на кг или на моль. Обычная «обширная» энтропия файла, аналогичного физике, S равна S = N * H, где N - количество символов в файле. H будет в точности аналогична части идеального объема газа. Информационная энтропия не может быть просто сделана точно равной физической энтропии в более глубоком смысле, потому что физическая энтропия допускает «упорядоченные», а также неупорядоченные схемы: физическая энтропия получается больше, чем совершенно случайная энтропия (такая как сжатый файл). Один аспект отличается Для идеального газа есть дополнительный фактор 5/2 для учета этого: S = k * N * (H + 5/2), где H = возможные квантовые состояния на молекулу = (xp) ^ 3 / hbar * 2 * sigma ^ 2, где x = ширина прямоугольника, p = общий ненаправленный импульс в системе (рассчитанный по кинетической энергии и массе на молекулу) и sigma = 0,341 в соответствии с принципом неопределенности, дающим только число возможные состояния в пределах 1-го уровня.

Небольшая математика дает более короткую форму нормализованной обширной энтропии для файла:

S = N * H / log (n) = сумма (count_i * log (N / count_i)) / log (n)

Единицами этого являются "энтропия" (которая на самом деле не единица). Нормализовано, чтобы быть лучшей универсальной мерой, чем единицы «энтропии» N * H. Но это также не должно называться «энтропией» без пояснения, потому что нормальное историческое соглашение ошибочно называет H «энтропией» (что противоречит пояснения, сделанные в тексте Шеннона).

Answer 7

Нет такой вещи как энтропия файла. В теории информации энтропия является функцией случайной величины , а не фиксированного набора данных (ну, технически фиксированный набор данных имеет энтропию, но эта энтропия будет равна 0 - мы можем рассмотреть данные как случайное распределение, которое имеет только один возможный результат с вероятностью 1).

Чтобы рассчитать энтропию, вам нужна случайная величина, с помощью которой можно смоделировать ваш файл. Тогда энтропия будет энтропией распределения этой случайной величины. Эта энтропия будет равна числу битов информации, содержащейся в этой случайной переменной.

Answer 8

Если вы используете энтропию теории информации, помните, что, возможно, имеет смысл не использовать ее в байтах. Скажем, если ваши данные состоят из чисел с плавающей точкой, вы должны вместо этого распределить распределение вероятностей по этим числам и вычислить энтропию этого распределения.

Или, если содержимое файла содержит символы Unicode, вы должны использовать их и т. Д.

Answer 9

Re: Мне нужно все, чтобы сделать предположения о содержимом файла: (открытый текст, разметка, сжатый или некоторый двоичный файл, ...)

Как уже отмечали другие (или были сбиты с толку / отвлечены), я думаю, что вы на самом деле говорите о метрической энтропии (энтропия, деленная на длину сообщения). Подробнее на Энтропия (теория информации) - Википедия .

комментарий джиттера, ссылающийся на Сканирование данных на предмет аномалий энтропии очень важно для вашей основной цели. В конечном итоге это связывается с libdisorder (библиотека C для измерения энтропии байтов) . Этот подход, по-видимому, даст вам гораздо больше информации для работы, поскольку он показывает, как метрическая энтропия изменяется в разных частях файла. Смотрите, например Этот график показывает, как изменяется энтропия блока из 256 последовательных байтов изображения JPG размером 4 МБ (ось Y) для различных смещений (ось X). В начале и в конце энтропия ниже, так как она находится на полпути, но для большей части файла она составляет около 7 бит на байт.

Источник: https://github.com/cyphunk/entropy_examples. [ Обратите внимание, что этот и другие графики доступны по новой лицензии http://nonwhiteheterosexualmalelicense.org .... ]

Более интересным является анализ и аналогичные графики на Анализ байтовой энтропии диска в формате FAT | GL.IB.LY

Статистика, такая как максимальное, минимальное, режимное и стандартное отклонение метрической энтропии для всего файла и / или первого и последнего его блоков, может быть очень полезна в качестве сигнатуры.

Эта книга также представляется актуальной: Обнаружение и распознавание маскировки файлов для электронной почты и защиты данных - Springer

Answer 10

Рассчитывает энтропию любой строки беззнаковых символов размера "длина". По сути, это рефакторинг кода, найденного на http://rosettacode.org/wiki/Entropy.. Я использую его для 64-битного генератора IV, который создает контейнер из 100000000 IV без дублирования и средней энтропии 3,9. 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;
 }