Вычисление энтропии Шеннона HTTP-заголовка с использованием Python. Как это сделать?

Ответ 1

Пока я не понимаю, почему вы хотите это сделать, я не согласен с другими, которые считают, что это бессмысленно.

Вы могли бы, например, взять монету и перевернуть ее и измерить ее энтропию. Предположим, вы переворачиваете 1000 раз и получаете 500 голов и 500 хвостов. Это 0,5 частоты для каждого результата, или то, что статистики официально называют "событием".

Теперь, поскольку два Ti равны (0,5), а логарифмическая база 2 0,5 равна -1, энтропия монеты равна -2 * (0,5 * -1) = -1 (минус 2 является минус выходить вперед и распознавать добавление двух одинаковых вещей - это то же самое, что умножить на 2.

Что, если монета придумала головы в 127 раз чаще, чем хвосты? Теперь хвосты встречаются с вероятностью 1/128, которая имеет логарифмическую базу 2 -7. Это дает вклад примерно 1/32 от умножения -7 раз 1/128 (примерно). Головы имеют вероятность, очень близкую к 1. Но база базы 2 (или база ничего) из 1 равна нулю. Таким образом, этот термин дает примерно ноль. Таким образом, энтропия этой монеты составляет около -1/32, помня знак минуса (если я сделал это все в моей голове).

Итак, трюк для вас - собрать много случайных сообщений и посчитать их на два ведра. Затем просто выполните вычисления, как указано выше.

Если вы спрашиваете, как сделать этот подсчет, и у вас есть это на компьютере, вы можете использовать такой инструмент, как grep (инструмент регулярного выражения в unix) или аналогичную утилиту для других систем. Он сортирует их для вас.

Ответ 2

Напоминание: формула для энтропии

H(S)=-sum[ P(Xi) * log2 P(Xi) ], где

S - это контент, который вы хотите вычислить энтропией,

Xi является символом i-th в документе и

P(Xi) - это вероятность увидеть символ Xi в контенте.

Первая проблема здесь - правильно оценить P(Xi). Чтобы сделать это правильно, вам нужно загрузить как можно больше разнообразных страниц. По меньшей мере 100, несколько тысяч были бы лучше. Это важно, потому что вам нужно иметь реальные страницы, которые хорошо отражают ваш домен.

Теперь вам нужно восстановить уровень HTTP из пакетов. Это не простая задача в реальной жизни, потому что некоторые страницы будут разбиты на несколько пакетов, и их порядок прибытия может быть не таким, как вы ожидаете, и некоторые пакеты могут быть потеряны и повторно переданы. Я рекомендую вам прочитать этот блог, чтобы получить доступ к subj.

Кроме того, я предлагаю вам рассчитать энтропию для заголовков и тела HTTP-запросов отдельно. Это связано с тем, что я ожидаю, что распределение символов в заголовке и теле должно отличаться.

Теперь, когда у вас есть доступ к нужному контенту, вы просто подсчитываете частоты каждого символа. Что-то вроде следующего (doc_collection может содержать список из всех HTTP-заголовков, которые вы извлекли из своих PCAP.):

def estimate_probabilities(doc_collection):
    freq = Counter()
    for doc in doc_collection:
        freq.update(Counter(doc))
    total = 1.0*sum(freq.values())
    P = { k : freq[k]/total for k in freq.keys() }
    return P

Теперь, когда у вас есть вероятности символов, вычисление энтропии прост:

import numpy as np
def entropy(s, P):
    epsilon = 1e-8
    sum = 0
    for k,v in Counter(s).iteritems():
        sum -= v*P[k]*np.log2(P[k] + epsilon) 
    return sum

Если вам нравится, вы можете даже ускорить его, используя map:

import numpy as np
def entropy(s, P):
    epsilon = 1e-8
    return -sum(map(lambda a: a[1] * P[a[0]] * np.log2(P[a[0]] + epsilon), Counter(s).items()))

epsilon необходим, чтобы не допустить логарифма до минус бесконечности, если вероятность символа близка к нулю.

Теперь, если вы хотите вычислить энтропию, исключая некоторые символы ( "\ r" и "\n" в вашем случае), просто нулевые их вероятности, например. P['\n'] = 0 Это приведет к удалению всех этих символов из числа.

- обновлено, чтобы ответить на комментарий:

Если вы хотите суммировать энтропию в зависимости от существования подстроки, ваша программа будет выглядеть так:

....
P = estimate_probabilities(all_HTTP_headers_list)

....
count_with, count_without = 0, 0
H = entropy(s, P)
if '\r\n\r\n' in s:
    count_with += H
else:
    count_without += H

all_HTTP_headers_list представляет собой конкатенацию всех ваших заголовков, S - это конкретный заголовок.

- update2: как читать заголовки HTTP

pyshark - не лучшее решение для пакетной манипуляции, потому что оно снижает полезную нагрузку, но вполне нормально получать заголовки.

pkts = pyshark.FileCapture('dump.pcap')

headers = []
for pk in pkts:
    if pk.highest_layer == 'HTTP':
        raw = pk.tcp.payload.split(':')
        headers.append( ''.join([ chr(int(ch, 16)) for ch in raw ]) )

Здесь вы проверяете, действительно ли у вашего пакета есть HTTP-уровень, получить его полезную нагрузку (от уровня TCP как строку::), затем выполнить некоторые строковые манипуляции и в конце получить все HTTP-заголовки из PCAP в виде списка.