Недавно разбираясь с очередным алгоритмом шифрования и попутно знакомясь с миром FPGA, я случайно нашел одну маленькую утилитку, написанную на Python, которая в буквальном смысле позволяет посмотреть распределение информации в файле.
Данная утилитка (не буду говорить, как называется) была разработана для просмотра и изучения различного рода файлов прошивок устройств, но не это меня заинтересовало…
Первое, что меня удивило в программе, это то, как она позволяет изучать различные файлы, отображая их в графики информационной энтропии.
Информационная энтропия — это понятие из прикладной теории информации, которое обозначает меру неопределенности или непредсказуемости информационной системы. Однако, это понятие несколько шире данного определения и позволяет провести качественный или количественный анализ некоторого объема данных. Анализ в этом смысле предполагает некоторые предположения, которые основаны на том факте, что энтропия в информатике тесно связана с информацией (информация — это то, что уменьшает энтропию, и информации нужно столько, сколько необходимо и энтропии).
Информационная энтропия рассчитывается довольно просто: пусть есть некоторая величина x и у нее есть некоторый дискретный набор состояний (т.е значений, которые она может принимать). Тогда, обозначим некоторое произвольное состояние из этого набора как xi, а вероятность этого состояния обозначим как pi. В этом случае информационная энтропия для случайных и независимых значений xi с n возможными состояниями (n — количество возможных значений величины xi) будет рассчитываться по формуле:
H(x) = -sum(1, n, pi * log2(pi))
где sum(1, n, …) — сумма всех значений от 1 до n; log2(…) — логарифм по основанию 2.
Представим, что мы исследуем двоичный файл с помощью понятия информационной энтропии, тогда необходимо определить что будет играть роль величины x и какие значения (и в каком диапазоне она может принимать). Ответить на этот вопрос просто, если учесть тот факт, что файл на самом низком уровне своей реализации представляет собой поток байтов (лучше всего беззнаковых). При этом, становится понятным, что x может принимать значения от 0 до 255 (т.е диапазон — это [0;255]), а в роли вероятностей pi может выступать частота повторов конкретного байта. Также, если проводить анализ энтропии по всему массиву байтов, то обнаружиться, что практически каждый байт представлен достаточно высокой частотой повторения и значение энтропии будет достаточно велико, что может впоследствие создать некоторые неудобства.
Решением проблемы может выступить разделение файла на некоторые блоки и раздельный расчет энтропии для каждого из блоков (таким образом, мы получаем энтропию отдельного блока — чем выше энтропия отдельного блока, тем более широко представлены в нем практически все байты и тем выше вклад вклад каждого байта в разрешение неопределенности от файла — запомните это высказывание, так как в нем ключ).
Реализуем вычисление энтропии блока данных:
import std.algorithm;
import std.file;
import std.math;
import std.range;
import std.stdio;
auto shannon(ubyte[] data)
{
float[256] dataCounter = 0.0f;
float entropy = 0.0f;
float dataLength = data.length;
foreach (unit; data)
{
dataCounter[unit]++;
}
foreach (count; dataCounter)
{
float px = count / dataLength;
if (px > 0)
{
entropy -= px * log2(px);
}
}
return entropy / 8.0f;
}
Тут мы используем тот же прием, что и при вычислении гистограмм — количество возможных значений байта ограничено и оно равно 256. Выполняем проход по блоку данных и в случае нахождения некоторого байта увеличиваем на 1 ячейку аккумулятора с индексом равным значению байта. После этого шага у нас есть массив с количеством каждого байта в блоке, и теперь разделив каждое значение из массива на длину блока, получаем частоту встречи каждого байта в блоке. Тут же на месте этого вычисления, если вероятность не нулевая (т.к как логарифм по основанию 2 для нуля не существует), считаем энтропию используя формулу для энтропии. Финальным штрихом в функции служит деление полученного значения энтропии на 8, таким образом мы считаем энтропию, исходя из того, что в байте ровно 8 бит.
Теперь, когда есть расчет энтропии блока можно перейти к расчету энтропии файла, для этого нам потребуется целый массив, в котором будут хранится результаты вычислений для каждого блока и именно этот массив будет выводом функции:
auto shannonFile(string filename, uint chunkSize)
{
float[] chunksEntropy;
File file;
file.open(filename, "rb");
foreach (ubyte[] buffer; file.byChunk(chunkSize))
{
chunksEntropy ~= shannon(buffer);
}
return chunksEntropy;
}
В этой функции происходит поблочное считывания файла в некоторый буффер, который подается как блок данных в функцию расчета энтропии. После очередного вычисления происходит запись результата в массив и он выдается в качестве аргумента.
Для удобства можно также записать результат, как обычный CSV-файл, например, вот так:
auto toCSV(string source, string target, uint chunkSize)
{
File file;
file.open(target, "w");
auto entropies = shannonFile(source, chunkSize);
entropies.enumerate(0).each!(a => file.writef("%d;%f\n", a[0], a[1]));
}
После этого, можно подать полученный файл некоторой программе, которая выполнит визуализацию результата, выдав скачкообразный график, который покажет, как именно меняется энтропия в файле.
Интерпретировать результаты данной программы достаточно сложно, однако, стоит понимать, что распределение энтропии указывает на то, как именно информация распределена по файлу и насколько полно охватывается весь диапазон возможных значений байтов (соответственно, можно менять разрешение процедуры анализа, изменяя размер блока). Стоит также помнить, что чем больше блок данных, тем выше частота встречаемости каждого байта, однако, конкретные величины встречаемости все равно зависят от типа файла (и что самое важное, от его формата !), что также может быть использовано в анализе.
Напоследок, код моего опыта (анализируем программу на Go):
import std.algorithm;
import std.file;
import std.math;
import std.range;
import std.stdio;
auto shannon(ubyte[] data)
{
float[256] dataCounter = 0.0f;
float entropy = 0.0f;
float dataLength = data.length;
foreach (unit; data)
{
dataCounter[unit]++;
}
foreach (count; dataCounter)
{
float px = count / dataLength;
if (px > 0)
{
entropy -= px * log2(px);
}
}
return entropy / 8.0f;
}
auto shannonFile(string filename, uint chunkSize)
{
float[] chunksEntropy;
File file;
file.open(filename, "rb");
foreach (ubyte[] buffer; file.byChunk(chunkSize))
{
chunksEntropy ~= shannon(buffer);
}
return chunksEntropy;
}
auto toCSV(string source, string target, uint chunkSize)
{
File file;
file.open(target, "w");
auto entropies = shannonFile(source, chunkSize);
entropies.enumerate(0).each!(a => file.writef("%d;%f\n", a[0], a[1]));
}
void main()
{
toCSV("/home/aquareji/plan9/rgb", "entropy.txt", 256);
}