projects.mako.cc - wikiq/blob - disorder.c

   1 /***************************************************************************
   2  *  libdisorder: A Library for Measuring Byte Stream Entropy
   3  *  Copyright (C) 2010 Michael E. Locasto
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful, but
  11  *  WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the:
  17  *       Free Software Foundation, Inc.
  18  *       59 Temple Place, Suite 330
  19  *       Boston, MA  02111-1307  USA
  20  *
  21  * $Id$
  22  **************************************************************************/
  23
  24 #include <math.h> //for log2()
  25 #include <stdio.h> //for NULL
  26 #include "disorder.h"
  27
  28 #if defined(__FreeBSD__)
  29 #define        log2(x) (log((x)) * (1./M_LN2))
  30 #endif
  31
  32 /** Frequecies for each byte */
  33 static int m_token_freqs[LIBDO_MAX_BYTES]; //frequency of each token in sample
  34 static float m_token_probs[LIBDO_MAX_BYTES]; //P(each token appearing)
  35 static int m_num_tokens = 0; //actual number of `seen' tokens, max 256
  36 static float m_maxent = 0.0;
  37 static float m_ratio = 0.0;
  38 static int LIBDISORDER_INITIALIZED = 0;
  39
  40 static void
  41 initialize_lib()
  42 {
  43   int i = 0;
  44   if(1==LIBDISORDER_INITIALIZED)
  45     return;
  46
  47   m_num_tokens = 0;
  48
  49   for(i=0;i<LIBDO_MAX_BYTES;i++)
  50   {
  51     m_token_freqs[i]=0;
  52     m_token_probs[i]=0.0;
  53   }
  54
  55   LIBDISORDER_INITIALIZED = 1;
  56 }
  57
  58 /**
  59  * Set m_num_tokens by iterating over m_token_freq[] and maintaining
  60  * a counter of each position that does not hold the value of zero.
  61  */
  62 static void
  63 count_num_tokens()
  64 {
  65   int i = 0;
  66   int counter = 0;
  67   for(i=0;i<LIBDO_MAX_BYTES;i++)
  68   {
  69     if(0!=m_token_freqs[i])
  70     {
  71       counter++;
  72     }
  73   }
  74   m_num_tokens = counter;
  75   return;
  76 }
  77
  78 /**
  79  * Sum frequencies for each token (i.e., byte values 0 through 255)
  80  * We assume the `length' parameter is correct.
  81  *
  82  * This function is available only to functions in this file.
  83  */
  84 static void
  85 get_token_frequencies(char* buf,
  86                       long long length)
  87 {
  88   int i=0;
  89   char* itr=NULL;
  90   unsigned char c=0;
  91
  92   itr = buf;
  93
  94   //reset number of tokens
  95   m_num_tokens = 0;
  96
  97   //make sure freqency and probability arrays are cleared
  98   for(i=0;i<LIBDO_MAX_BYTES;i++)
  99   {
 100     m_token_freqs[i] = 0;
 101     m_token_probs[i] = 0.0;
 102   }
 103
 104   for(i=0;i<length;i++)
 105   {
 106     c = (unsigned char)*itr;
 107     //assert(0<=c<LIBDO_MAX_BYTES);
 108     m_token_freqs[c]++;
 109     itr++;
 110   }
 111 }
 112
 113 /**
 114  * Return entropy (in bits) of this buffer of bytes. We assume that the
 115  * `length' parameter is correct. This implementation is a translation
 116  * of the PHP code found here:
 117  *
 118  *    http://onlamp.com/pub/a/php/2005/01/06/entropy.html
 119  *
 120  * with a helpful hint on the `foreach' statement from here:
 121  *
 122  *    http://php.net/manual/en/control-structures.foreach.php
 123  */
 124 float
 125 shannon_H(char* buf,
 126           long long length)
 127 {
 128   int i = 0;
 129   float bits = 0.0;
 130   char* itr=NULL; //values of itr should be zero to 255
 131   unsigned char token;
 132   int num_events = 0; //`length' parameter
 133   float freq = 0.0; //loop variable for holding freq from m_token_freq[]
 134   float entropy = 0.0; //running entropy sum
 135
 136   if(NULL==buf || 0==length)
 137     return 0.0;
 138
 139   if(0==LIBDISORDER_INITIALIZED)
 140     initialize_lib();
 141
 142   itr = buf;
 143   m_maxent = 0.0;
 144   m_ratio = 0.0;
 145   num_events = length;
 146   get_token_frequencies(itr, num_events); //modifies m_token_freqs[]
 147   //set m_num_tokens by counting unique m_token_freqs entries
 148   count_num_tokens();
 149
 150   if(m_num_tokens>LIBDO_MAX_BYTES)
 151   {
 152     //report error somehow?
 153     return 0.0;
 154   }
 155
 156   //iterate through whole m_token_freq array, but only count
 157   //spots that have a registered token (i.e., freq>0)
 158   for(i=0;i<LIBDO_MAX_BYTES;i++)
 159   {
 160     if(0!=m_token_freqs[i])
 161     {
 162       token = i;
 163       freq = ((float)m_token_freqs[token]);
 164       m_token_probs[token] = (freq / ((float)num_events));
 165       entropy += m_token_probs[token] * log2(m_token_probs[token]);
 166     }
 167   }
 168
 169   bits = -1.0 * entropy;
 170   m_maxent = log2(m_num_tokens);
 171   m_ratio = bits / m_maxent;
 172
 173   return bits;
 174 }
 175
 176 int
 177 get_num_tokens()
 178 {
 179   return m_num_tokens;
 180 }
 181
 182 float
 183 get_max_entropy()
 184 {
 185   return m_maxent;
 186 }
 187
 188 float
 189 get_entropy_ratio()
 190 {
 191   return m_ratio;
 192 }