⼯作中常⽤的相似度算法以及特征提取算法
⽬录：
⼀、概述。
⼆、基于可变长度特征的相似度。
1、两个字符串之间的相似度（最短编辑距离）。
2、从样本到变长特征。
(1)      强弱hash模型。
(2)      关键字密度模型。
三、基于固定长度特征的相似度。
1、修改的K-means算法。
2、从样本到定长特征。
(1)      基于数据频度的量化。
(2)      基于图⽚压缩的算法。
四、总结。
五、引⽤。
概述
⼀、
⼀、概述
在⽇常⼯作中，病毒分析师经常被要求在样本库⾥查相似样本。⽐如在获得某APT组织的样本的情景下，希望查其历史版本来确定组织的活动时间，从⽽追踪溯源，也希望查样本的变种，来看⼀下恶意样本的影响范围。类似的⼯作往往会交给样本分析师（写样本分析报告的⼈）。样本分析师有很⼤概率根本就不知道怎么查历史样本，也不知道怎么查变种。归根结底，这是相似样本查问题。希望本⽂可以抛砖引⽟，让每个样本分析相关从业⼈员，都能够拥有⾃⼰的相似样本查⼯具。
通过长期的⼯作总结，发现恶意样本的特征可分为两类，⼀类是可变长度的特征，⼀类是固定长度的特征。本教程会以这两条主线为线索，分别介绍两种相似度算法，四种提取特征算法。
基于可变长度特征的相似度
⼆、基于可变长度特征的相似度
⼆、
变长特征是指，从样本中提取的特征序列长度不固定。也就是说，应⽤此类算法，从每⼀类样本提取的特征序列长度都不相同。我们要针对不同长度的两个特征序列进⾏相似度⽐对。
在实际⽣活中，我们⼀眼能认出两个长短不⼀的字符串是不是相似的，如（【abcdefg、abcde】、【abcdrfg、qwertyui】），第⼀组相似性要⽐第⼆组相似性⾼⼀些。这两组字符串就可看作可变长度的特征序列。相⽐较的每⼀组字符串，都不强制要求长度相等。
1、两个字符串之间的相似度（最短编辑距离）
我们先抛开从样本⽣成特征的问题，先假设我们有两个样本（A、B），样本A⽣成了特征序列abcd，样本B⽣成了特征序列acd。这样我们就把两个样本相似度的问题，转化成了两个字符串之间相似度的
问题。作为智能⽣物，我们很轻易的就能识别处两个复杂字符串所具有相似性。但是⼀旦把⼯作交给计算机，那么就需要算法来辅助了，⽽且字符串越复杂则计算过程越复杂。
为了解决这个复杂的问题，在1965年，俄罗斯数学家Vladimir Levenshtein提出了字符串的编辑距离，⼜称为Levenshtein距离[1]。编辑距离越⼩，则两个字符串的相似度越⾼。
对⼀个字符串⼀共有三种【字符操作】：插⼊⼀个字符、删除⼀个字符、替换⼀个字符。编辑距离指的是，从A字符串转换成B字符串的
过程中，要发⽣多少次【字符操作】。
例如：
（abcde  ->  abcdf），如果abcde想要变成abcdf，则需要把字符串中的e替换成f。总计进⾏过⼀次【字符操作】，所以编辑距离是1。
（abcde  ->  hijkl），如果abcde想要变成hijkl，则需要替换hijkl中的全部字符。总计进⾏5次替换，所以编辑距离是5。
从相似性上来讲，由于（abcde  ->  abcdf）的最⼩编辑距离是1，⽽（abcde  ->  hijkl）的最⼩编辑距
离是5，⼜由于1<5，所以【abcde、abcdf的相似性】⽐【abcde、hijkl的相似性】更⾼⼀些。上述就是计算机使⽤最⼩编辑距离算法理解相似性的过程。
接下来进⼊具体的算法环节：
严谨公式[2]：
为了弄明⽩这个公式我们需要，做⼀个⼩游戏。两张表格查重复数据
在上图的表格中，横列坐标是字符串abcd，纵列坐标是字符串acd。我们需要在标有问号的区域填写数字，把整张表填满。填表规则如下:
对于每⼀个问号（？）
1、取（？）所在格⼦向上⼀个格⼦的数值x，把数值x加1，记作(x+1)。
2、取（？）所在格⼦向左⼀个格⼦的数值y，把数值y加1，记作(y+1)。
3、取（？）所在格⼦向左上⼀个格⼦的数值z。⽐较上图中，格⼦所对应的，灰⾊区域中的字符是否相等。如相等，则不需要任何操作，记作z。如不相等，则把数值z加1，记作z+1。整体记作(z|z+1)。
4、⽐较(x+1)、(y+1)、(z|z+1)这三个数值，取三者中最⼩的，填⼊（？）。
例⼦：
⽐如要填写上图中红⾊问号的数值，需要：
取红⾊问号向上⼀个格⼦数值x，x为1，所以(x+1)=2。
红⾊问号向左⼀个格⼦y为1，所以(y+1)=2。
红⾊问号向左上⼀个格⼦z为0，所以z=0、z+1=1。⼜由于格⼦所对应的灰⾊区域中的字符相等，都为a，对应游戏规则第3条，所以(z|z+1)取z，所以(z|z+1)=0。
⽐较(x+1)=2、(y+1)=2、(z|z+1)=0。发现(z|z+1)=0数值最⼩，所以红⾊问号取0。
以此类推，我们把所有的问号都填满，如下图所⽰：
然后我们依照上图再做⼀个游戏，游戏规则是从坐标(0,0)开始，向右、向下，向右下，寻这三个格⼦中的最⼩数值，并把它标红。如下图所⽰。
如上图所⽰，绿⾊的箭头就是其最短的编辑路径了。这点先放下⼀会再说。
我们先看被黄框框起来的部分，当按照【右、下、右下，三个格⼦中的最⼩数值】的规则进⾏到黄框中0的格⼦的时候，会发现右、下、右下这三个格⼦中都是1，貌似⾛哪个⽅向都可以，我们该如何选择呢？此时就需要动态权重登场了，在实际⼯作中，我们需要根据样本的特征来动态优化这个权重，在本例就直接规定右下的权重最⾼就可以了。
再回过头来看绿⾊的箭头，绿⾊的箭头为最短编辑路径，其作⽤如下[2]：
上图不仅说明了绿⾊箭头的作⽤，还说明了计算公式与游戏规则的对应关系。⼀切如图中所⽰，第⼀条公式对应着游戏第⼆条规则，第⼆条公式对应着游戏第⼀条规则，第三条公式对应着游戏第三条规则。所以整个公式就是⽤数学语⾔来描述的整个游戏规则。
我们按照表格图⽚中的【编辑操作】这⼀列，来操作⼀下：对于横列abcd字符串来说，忽略#字符，第⼀个字符a箭头是右下的，且与竖列的acd第⼀个字符串匹配，所以不做任何操作，此时总操作数为0。对于横列abcd字符串来说，第⼆个字符b箭头是向右的，意味着删除操作，所以对于横列abcd这个字符串来说需要把b这⼀个字符删除，此时总操作数⾃加1。以此类推，计算所有字符后，发现想把abcd变成acd，总操作数为1。由于abcd这4个字符⼀共有4次操作机会，但是只有⼀次实际操作过，所以abcd与acd的差异度为1/4，相似度则为1-
1/4=75%。
2、从样本到变长特征。
有了求相似度的算法，还必须要有特征序列（向量）才⾏。我们当然可以把整个样本⽂件的数据当成特征序列来使⽤，但是会遇到⼏个问题：1、整个⽂件过于庞⼤，不利于存储。2、上述求相似度算法是和笛卡尔积具有相同复杂性的算法，所以如果把整个⽂件作为特征序列，计算过程将会变得⼗分缓慢。为了解决上述问题，我们需要对样本⽂件进⾏特征抽取。
(1)强弱hash模型。
⽤弱hash对⽂件进⾏数据块提取，⽤强hash对数据块进⾏hash计算，得到特征元。
弱hash在本例采⽤Adler32算法。Adler32算法有⼀个很好的特性，就是可以快速的增加和裁剪数据，这样可以减少计算量，使整个模型更⾼效。⽐如我已经有了0到16这个区间段的Adler32 Hash，命名为A。我现在想计算0到17这个区间的Adler32 Hash，此时我只需要把第17位数据“加”到A的后⾯就好了，⽽不⽤重新计算0到17这个区间的数据，由于具有上述特性，所以adler算法⼜被称为滚动算法[3]。
强hash随意采⽤即可，本例中使⽤RSHash算法做演⽰。
通常在实际⼯作中，我们采⽤⾃⼰的⼀套算法来代替强弱hash算法。强弱hash会⽆差别对待数据，这
样就失去了很多特异性。所以实际⼯作中，还需要⾃⼰编写专⽤的特征元⽣成算法，但是作为原理性解释，RSHash和Adler32算法⾜够了。
整个强弱hash模型流程如上图所⽰：
1、⾸先从起始地址0开始，取长度为len的数据块，命名为A0。
2、使⽤Adler32来计算A0的弱hash值。
3、然后我们定义⼀个阈值k，判断弱hash值是否满⾜阈值k。
①当弱hash满⾜阈值k的时候。
对整个A0数据块进⾏RSHash运算，得到强hash，把这个强hash记录下来，作为整个特征序列的⼀个单位特征。
②当弱hash不满⾜阈值k的时候。
重新选取数据块：以A0数据块起始地址+1为新起始点，长度为len不变，让A0=新数据块，然后重新进⾏步骤2，直到弱hash满⾜阈值k为⽌。
我们来简单介绍⼀下Adler32算法[3]：
上图为整个Adler32算法的计算步骤，图中D为具体的原始输⼊数据，n为数据的长度。
Adler32算法⼀共计算了两个值(A、B)。
A只是简单的将数据D的每⼀字节进⾏累加。
B则可以分成两步看：第⼀步计算D中每⼀个元素的tmp值，tmp =（D中的单个元素*（总长度n  -  单个元素在D中序号）），第⼆步，把每⼀个元素的tmp相加。
然后再把A和B值拼接起来，就成了Adler32 Hash。
上图是把Wikipedia字符串计算成Adler32 Hash的计算过程。
使⽤Adler32有个好处，⽐如我想在字符串Wikipedia基础上计算ikipediaX，我们看到新的字符串在Wikipedia字符串的基础上，开头去掉了W，结尾加上了X。所以计算ikipediaX的Adler32 Hash，我们只需要：
1、在A上减去W的ascii，A = A - 87 = 833.
2、在B上减去(len - offset)倍的W的ascii。其中W的偏移为0，Wikipedia字符串长度为9，所以 B = B - (9 - 0)*87 = 3799
3、在A上加X的ascii，A = A + 88 = 921
4、在B上加上A，B = B + A = 4720
5、在把A和B拼接到⼀起，就完成了ikipediaX的Adler32 Hash计算。
有了Adler32算法，我们就可以快速的对样本进⾏滚动运算，然后根据每轮计算的结果，来确定是否要进⾏RSHash强Hash计算。
⽐如假设⼀个样本为：【ABCDEFGHIJKLMNOPQRSTUVWXYZ】
我定义要以（起始地址为0、数据长度为4）来计算Adler32 Hash，然后根据每⼀轮滚动运算的结果，来判断是否需要进⾏RSHash计算：
第⼀轮：【ABCD---------------------------------------】Adler32 不符合阈值，不计算RSHash
第⼆轮：【--BCDE--------------------------------------】Adler32符合阈值，计算RSHash
第三轮：【----CDEF------------------------------------】Adler32符合阈值，计算RSHash
第四轮：【------DEFG----------------------------------】Adler32不符合阈值，不计算RSHash
第五轮：.........
在每⼀轮计算Adler32 Hash后都会与阈值相⽐对，如果符合阈值，则计算RSHash，把RSHash的计算结果当作特征元，存⼊特征序列。
⽐如在第⼆轮，我计算【--BCDE--------------------------------------】的Adler32 Hash⼤于阈值0x6666666，
那么我将对【--BCDE--------------------------------------】进⾏RSHash运算。然后把每⼀个RSHash运算的结果拼接起来，组合成⼀个特征序列，这个特征序列就是【变长特征】序列。
RSHash hash是⼀个简单的强hash算法，其python实现如下：
如上图所⽰，RSHash是⼀个不可逆运算的简单hash算法，没什么可说的。
(2)  关键字密度模型。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。