基于信息熵判断非PE文件是否加密混淆的方法浅析

Delina

原文链接：基于信息熵判断非PE文件是否加密混淆的方法浅析
一 • 信息熵



什么是信息
在计算机科学中，我们通常认为信息是一种数据或指令的集合，泛指我们通过载体传播的内容。

信息熵
熵是一个热力学概念，是形容物质混乱程度的单位，当物质混乱程度越高的时候熵值越高。在上个世纪40年度，香农将熵引入到信息论中，把信息中排除冗余后的平均信息量定义为信息熵。

香农公式
我们假定有一列信息abaaabbababa...，其中字母a出现的概率是p，则字母b出现的概率是(1-p)，那么当信息的长度为N的时候，信息中就会存在pN个a，以及(1-p)个b，那么这个信息的排列方式就有N!/(pN)!((1-p)N)!种。

对于a的自信息量就是Pa=-p*log2(p)，那么整个信息列的熵就是S=-p*log2(p)-(1-p)*log2(1-p)，这里用log2做底数是因为只有ab两种情况。

那么现在我们对整个公式进行抽象，可以得到：

• 
  

log2(1/pa) + log2(1/pb) + ... + log2(1/pn)= ∑ log2(1/pn)
如果把2也当作是一个变量的话，我们可以进一步得出：

• 
  

S=log(1/pa) + log(1/pb) + ... + log(1/pn)= ∑ log(1/pn)= ∑ -p*log(p)
这就是大名鼎鼎的香农公式了。

信息熵的应用
信息熵目前被广泛应用在各种压缩场景种，对于长度相同的信息，熵值p越大，则表明信息内容越有规律，可压缩的体积就越大；p越小，则信息内容越随机，可压缩的体积就越小。

对于非PE文件，例如恶意脚本，为了逃避杀软检测经常使用加密/压缩等手段，无论如何处理都会增大信息的随机性，那么我们就可以利用信息熵来做对应检测了。


二 • 实现


思路
一个文本信息的基本单位是字节，一个字节的范围是0~255，那么我们就可以得到公式：

• 
  

I(n)=(S(a/256))+(S(b/256))....(S(n/256))

代码：

1. double CEntropy::calculate()
   
2. {
   
3.     double entropy = 0;
   
4.     DWORD dwMapSize = g_GlobalInfo.GetSize();
   
5.     for (int i = 0; i < 256; i++)
   
6.     {
   
7.         double p_x = double(g_GlobalInfo.count(((char)i))) / dwMapSize;
   
8.         if (p_x > 0)
   
9.             entropy += -p_x * (log(p_x));
   
10.     }
    
11.     return entropy;
    
12. }

复制代码

样本：

• 
  

aGVsbG8gd29yZA==hello word
我们分别对Base64前后的数据进行计算，可以得到：

• 
  

encode_base64_entropy = 3.0351414decode_base64_entropy = 2.1535325
信息熵会明显增大，但是这里不是绝对的，因为这个信息熵是标识信息的复杂度的，所以在某些加密方法中，会显著降低信息熵，例如：

• 
  

Chr(104)+Chr(101)+Chr(108)+Chr(108)+Chr(111)+Chr(9)+Chr(119)+Chr(111)+Chr(114)+Chr(100)

他的信息熵只有2.3509156，我们就可以根据这个原理做一个期望，一段符合自然语言语法的信息，他的信息熵范围是可预期的，同样长度的信息，如果信息熵低于或者高于，都有可能是一段混淆加密的信息。


三 • 扩展


平均巧合指数(Index of Coincidence)
当然如果混淆算法经过特殊处理，是可以计算到一个接近正常的信息熵，那么我们需要更多的维度去判断，这里我们可以使用一个密码学的概念「巧合指数」。

巧合指数（index of coincidence）就是任意拿出两个字母，两个字母相同的概率。

以英文字母为例，从26个字母中随机拿出一个字母的概率是1/26，随机选择两个字母，选择出相同字母对的概率是 26x(1/26)x(1/26)=0.0385。

而在自然语言中，英文的巧合指数是一个数学期望的，大概等于
（13/100)x(13/100)+(8/100)x(8/100)+(3/100)x (3/100)...=0.0667。

抽象后我们可以通过这样一个公式来计算
​
其中fi标识某字母在该段文字中出现的次数。

而我们常用的脚本语言也是接近自然语言语法，所以他的巧合指数也是可以获得一个期望的，我之前简单计算过，大概是在0.046~0.047之间。

贴代码：

1. double CLanguageIC::calculate()
   
2. {
   
3.     DWORD64 _char_count = 0;
   
4.     DWORD64 _total_char_count = 0;
   
5. 
   
6.     for (int i = 0; i < 256; i++)
   
7.     {
   
8.         DWORD64 charcount = g_GlobalInfo.count(((char)i));
   
9.         _char_count += charcount * (charcount - 1);
   
10.         _total_char_count += charcount;
    
11.     }
    
12. 
    
13.     double ic = 0;
    
14.     if (_total_char_count - 1 != 0)
    
15.         ic = double(_char_count) / (_total_char_count * (_total_char_count - 1));
    
16. 
    
17.     calculate_char_count();
    
18.     return ic;
    
19. }

复制代码

样本我们依然选择上面的：

• 
  

hello wordaGVsbG8gd29yZA==Chr(104)+Chr(101)+Chr(108)+Chr(108)+Chr(111)+Chr(9)+Chr(119)+Chr(111)+Chr(114)+Chr(100)
之后我们分别计算他们的巧合指数：

• 
  

a1 = 0.0761905a2 = 0.0380952a2 = 0.0967511
由于样本长度不足所以不会有太明显的区别，我另外对一个线上样本做了计算。

​
​


巧合指数分别为0.1249589和0.0310315，明显上面的会远远高于我们的期望。

互信息
这一步我写的比较简单，直接计算的H(Y|X)，其实是可以从条件熵和联合熵分别去计算，废话不说上代码：

1. double CEntropyMI::calculate()
   
2. {
   
3.     double entropy = 0;
   
4.     DWORD dwMapSize = g_GlobalInfo.GetSize();
   
5. 
   
6.     for (int i = 0; i < 256; i++)
   
7.     {
   
8.         double p_x = double(g_GlobalInfo.count(((char)i))) / dwMapSize;
   
9.         double p_y = (double)1 / 256;
   
10.         double p_x_y = p_x * p_y;
    
11.         if (p_x > 0)
    
12.             entropy += -(p_x * p_x_y) * (log(((p_x * p_x_y) / p_y)));
    
13.     }
    
14.     return entropy;
    
15. }
    
16. 
    
17. 
    
18. 
    

复制代码