10

The Shannon entropy is:

SHannon

\r\n\r\n is the end of a HTPP header:

enter image description here

Incomplete HTTP header:

Incomplete HTTP header

I have a network dump in PCAP format (dump.pcap) and I am trying to compute the entropy of the number of packets in HTTP protocol with \r\n\r\n and without \r\n\r\n in the header using Python and compare them. I read the packets using:

import pyshark

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

I think Ti in shannon formula is the data of my dump file.

dump.pcap: https://uploadfiles.io/y5c7k

I already computed the entropy of IP numbers:

import numpy as np
import collections

sample_ips = [
    "131.084.001.031",
    "131.084.001.031",
    "131.284.001.031",
    "131.284.001.031",
    "131.284.001.000",
]

C = collections.Counter(sample_ips)
counts = np.array(list(C.values()),dtype=float)
#counts  = np.array(C.values(),dtype=float)
prob    = counts/counts.sum()
shannon_entropy = (-prob*np.log2(prob)).sum()
print (shannon_entropy)

Any idea? Is it possible to compute the entropy of the number of packets in HTTP protocol with \r\n\r\n and without \r\n\r\n in the header or it is a nonsense idea?

A few lines of the dump:

HTTP filter of wireshark

 30 2017/246 11:20:00.304515    192.168.1.18    192.168.1.216   HTTP    339 GET / HTTP/1.1 


    GET / HTTP/1.1
    Host: 192.168.1.216
    accept-language: en-US,en;q=0.5
    accept-encoding: gzip, deflate
    accept: */*
    user-agent: Mozilla/5.0 (X11; Linux i686; rv:45.0) Gecko/20100101 Firefox/45.0
    Connection: keep-alive
    content-type: application/x-www-form-urlencoded; charset=UTF-8
11
  • 1
    This is a nonsense idea. As you showed in your IP addresses calculation, Shannon's entropy is calculated on strings, not a number of packets. Are you looking for the entropy of the string "\r\n\r\n"? That is calculated with this handy online calculator
    – call-in-co
    Commented Sep 11, 2017 at 1:35
  • @ScouserInTrousers: I thought that I could compute the frequency of packets with "\r\n\r\n" and without "\r\n\r\n". Is this non sense? Thanks for helping! Commented Sep 11, 2017 at 18:56
  • Sure, you could compute the frequency no problem. I'm not familiar with pyshark but if you can capture the HTTP requests, you can just do a Regular Expression and have two counters: count_with and count_without. If "\r\n\r\n" is in the string, increment count_with; else increment count_without.
    – call-in-co
    Commented Sep 12, 2017 at 14:39
  • @ScouserInTrousers: good idea, but the problem is how do it ? I can not write the script! Could you help me? Commented Sep 12, 2017 at 15:51
  • You do not quite understand what are you doing. The Ti in the formula is the probability of seeing a certain character. And you can not calculate entropy of number of packets. But you can calculate entropy of each specific page. First, you have to find the probabilities of each symbol. In order to do that, you need to estimate those probabilities. That means downloading as many pages as you can (several thousands would be enough, to represent well the statistics), and running your code on all the data.
    – igrinis
    Commented Sep 12, 2017 at 15:52

2 Answers 2

3
+25

While I don't see why you want to do it, I disagree with others who believe it is nonsensical.

You could, for instance take a coin and flip it and and measure its entropy. Suppose you flip 1,000 times and get 500 heads and 500 tails. That is 0.5 frequency for each outcome, or what statisticians would formally call an 'event'.

Now, since the two Ti's are equally (0.5), and the log base 2 of 0.5 is -1, the entropy of the coin is -2 *(0.5 * -1) = -1 (the minus 2 is the minus sign out front and recognizing adding two identical things is the same as multiplying by 2.

What if the coin came up with heads 127 times more often than tails? Tails now occurs with probability 1/128 which has a log base 2 of -7. So that gives a contribution of about 1/32 from multiplying -7 times 1/128 (roughly). Heads have a probability really close to 1. But the log base 2 (or base anything) of 1 is zero. So that term gives roughly zero. Thus, the entropy of that coin is about -1/32, remembering the minus sign (if I did this all right in my head).

So the trick for you is to collect lots of random messages, and count them into two buckets. Then just do the calculations as above.

If you are asking how to do that counting, and you have these on a computer, you can use a tool like grep (the regular expression tool on unix) or a similar utility on other systems. It will sort them for you.

2
  • Thanks! my goal is compare the entropy before an during a Denial of service attack. I would like to implement the idea of two counters: count_with and count_without. If "\r\n\r\n" is in the string, increment count_with; else increment count_without. I dont know how to extract the "\r\n\r\n" for counting! Commented Sep 12, 2017 at 21:31
  • 1
    I think your idea has a lot more merit than others are giving it. Don't know if it will work, but entropy is a very powerful test of actual 'randomness'.
    – eSurfsnake
    Commented Sep 14, 2017 at 5:32
3

Reminder: the formula for entropy is

H(S)=-sum[ P(Xi) * log2 P(Xi) ], where

S is a content you want to calculates it's entropy,

Xi is i-th character in the document, and

P(Xi) is a probability of seeing the character Xi in the content.

The first problem here is to estimate correctly P(Xi). To do it correctly you need to download as many diverse pages as you can. At very least 100, several thousands would be better. This is important, because you need to have a real pages that represent well your domain.

Now, you have to reconstruct HTTP layer from the packets. It is not easy task in real life, because some pages will be split across several packets, and their order of arrival may be not be as you expect, and some packets might be lost and retransmitted. I recommend you to read this blog, to get the grip on the subj.

Also, I suggest you calculate entropy for headers and body of HTTP requests separately. This is because I expect that distribution of characters in the header and the body to be different.

Now, when you have an access to the desired content you just count frequencies of each character. Something like following (doc_collection might a list composed of content of all HTTP headers you have extracted from your PCAPs.):

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

Now that you have the probabilities of the characters, calculating entropy is simple:

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

If you like, you can even speed it up using 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 is needed to prevent from logarithm to go to minus infinity, if the probability of a symbol is close to zero.

Now, if you want to calculate entropy excluding some characters ("\r" and "\n" in your case) just zero their probabilities, e.g. P['\n'] = 0 That will remove all those characters from the count.

-- updated to answer the comment:

If you want to sum the entropy depending on existence of the substring, your program will look like:

....
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 is a concatenation of all the headers you have, s is the specific header.

-- update2: how to read HTTP headers

pyshark is not the best solution for packet manipulation, because it drops the payload, but it is ok to just get the headers.

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 ]) )

Here you check that your packet actually has HTTP layer, get its payload (from the TCP layer as ':' separated string), then do some string manipulations and at the end receive all HTTP headers from the PCAP as a list.

4
  • thanks. my goal is compare the entropy before an during a Denial of service attack. I would like to implement the idea of two counters: count_with and count_without. If "\r\n\r\n" is in the string, increment count_with; else increment count_without. I dont know how to extract the "\r\n\r\n" for counting! Commented Sep 13, 2017 at 20:38
  • You do not need to extract the substring, just to check if it matches. See updated answer
    – igrinis
    Commented Sep 14, 2017 at 7:21
  • I understood the idea but I am not able to join it with the part of script that reads the PCAP file... I need to read the PCAP file to check if it matches. I only know how to read the PCAP file: import pyshark pkts = pyshark.FileCapture('dump.pcap') Commented Sep 14, 2017 at 11:09
  • Sorry for my ignorance. I am lost! Commented Sep 14, 2017 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.