首页
社区
课程
招聘
[分享]文件相似度的计算
发表于: 2013-6-21 23:45 8721

[分享]文件相似度的计算

2013-6-21 23:45
8721
相似度 = (1 - (差异数)/ max(sizeof(文件1), sizoof(文件2))) * (min(sizeof(文件1), sizoof(文件2)) / max(sizeof(文件1), sizoof(文件2)))
相似度取值0(不相似)-> 1(相似) ,一个应用是计算一批变形蠕虫样本是不是同一个

// filr_sim.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <fstream>
#include <math.h>
#include <iostream>
using namespace std;

bool loadfile(const wchar_t *name, vector<unsigned char> &v)
{
    fstream fs(name, ios::in | ios::binary);
    if (!fs.is_open())
        return false;

    fs.seekg(0, ios::end);
    streampos ps = fs.tellg();
    fs.seekg(0, ios::beg);

    v.resize(ps);
    fs.read((char *)&v[0], ps);
    return true;
}

bool loadfile(const char *name, vector<unsigned char> &v)
{
    fstream fs(name, ios::in | ios::binary);
    if (!fs.is_open())
        return false;

    fs.seekg(0, ios::end);
    streampos ps = fs.tellg();
    fs.seekg(0, ios::beg);

    v.resize(ps);
    fs.read((char *)&v[0], ps);
    return true;
}

bool savefile(const char *name, vector<unsigned char> &v)
{
    fstream fs(name, ios::out | ios::binary);
    if (!fs.is_open())
        return false;

    fs.write((char *)&v[0], v.size());
    return true;
}

typedef struct 
{
    vector<int> _v;
}bitvec;

bool file2vec(unsigned char *buf, size_t len, bitvec &vec)
{
    vec._v.resize(256 * 256);
    for (size_t i = 0; i < len - 1; i++)
    {
        unsigned char x = buf[i + 1];
        unsigned char y = buf[i];
        vec._v[y * 256 + x] += 1;
    }
    return true;
}

inline double sim(bitvec &vec1, bitvec &vec2)
{
    double x = 0;
    double nx = 0;
    double ny = 0;
    for (size_t i = 0; i < vec1._v.size(); i++)
    {
        x += abs(vec1._v[i] - vec2._v[i]);
        nx += vec1._v[i];
        ny += vec2._v[i];
    }
    return (1 - x / (max(nx, ny) + 1)) * ((min(nx, ny) + 1) / (max(nx, ny) + 1));
}


int _tmain(int argc, _TCHAR* argv[])
{
    vector<unsigned char> buf;

    loadfile("calc1.exe", buf);
    bitvec vec;
    file2vec(&buf[0], buf.size(), vec);

    loadfile("calc2.exe", buf);
    bitvec vec1;
    file2vec(&buf[0], buf.size(), vec1);

    cout << sim(vec, vec1) << endl;

    return 0;
}

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (11)
雪    币: 324
活跃值: (113)
能力值: ( LV15,RANK:280 )
在线值:
发帖
回帖
粉丝
2
对你这个算式挺感兴趣的,不知道实际效果怎么样。从算式上看,它只考虑了文件大小,为什么不考虑内容相似度呢?  有中计算内容相似度的算法, fuzzy hash: http://blog.sei.cmu.edu/post.cfm/fuzzy-hashing-techniques-in-applied-malware-analysis
2013-6-24 10:22
0
雪    币: 59
活跃值: (25)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
3
这个算法是将文件中数据进行如下形式的转换

假如有
数据1:abcdd
数据2:aaabc
->
数据1 =
abcdd
ab
bc
  cd
   dd
->
aa ab ac ad ba bb bc bd ca cb cc cd da dd dc dd
0  1  0  0  0  0  1  0  0  0  0  1  0  0  0  1

数据2 =
aaabc
aa
aa
  ab
   bc
->
aa ab ac ad ba bb bc bd ca cb cc cd da dd dc dd
2  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0

然后可以用余弦相似度或者欧式距离公式计算出相似度,

  实际应用的话,如果需要度量的数据比较小,可以进行这种方式的转换:
aaa aab aac aad aba abb abc abd baa bab bac bad ...ddd
或者取更长的特征(特征数指数级增长), 如果数据很大的话取两个单位特征的组合效果就比较理想了

  fuzzy hash 我了解的也不是太多,大概看了下描述,不知道他对形如这样的数据要如何处理

  数据1:abcdefgh
  数据2:habcdefg
2013-6-24 21:44
0
雪    币: 27
活跃值: (127)
能力值: ( LV8,RANK:120 )
在线值:
发帖
回帖
粉丝
4
有点兴趣,不过没太看懂。。
2013-6-24 22:11
0
雪    币: 316
活跃值: (128)
能力值: ( LV7,RANK:110 )
在线值:
发帖
回帖
粉丝
5
先顶顶,这样计算完全不靠谱啊......
2013-6-24 22:33
0
雪    币: 324
活跃值: (113)
能力值: ( LV15,RANK:280 )
在线值:
发帖
回帖
粉丝
6
给定长度的字串,计算字串频度,再计算频度的相似度。不错,挺好的,其他地方估计也能用到。
2013-6-25 11:18
0
雪    币: 316
活跃值: (128)
能力值: ( LV7,RANK:110 )
在线值:
发帖
回帖
粉丝
7
两个文件特征码计算应该比较靠谱一点,取相似度,在下觉得如何?
2013-6-25 11:24
0
雪    币: 324
活跃值: (113)
能力值: ( LV15,RANK:280 )
在线值:
发帖
回帖
粉丝
8
这种方法是有用的!
判读用户输入的字符串是正常英文,或者是形如"sdfsdwefrjofjvgdvd"之类的乱码。就可以利用频度统计的方法。
字串:co, an, he, ck等在英文中频度很高。
而字串:jb, kc  在常见英文中基本找不到。
2013-6-25 11:25
0
雪    币: 324
活跃值: (113)
能力值: ( LV15,RANK:280 )
在线值:
发帖
回帖
粉丝
9
什么是特种码?不大明白。

针对PE文件的相似度计算,有启发式算法。把PE文件的所有静态属性作为比较对象,比如,section 数量,section名字,section属性,EP地址,导入函数个数等。
2013-6-25 11:33
0
雪    币: 27
活跃值: (127)
能力值: ( LV8,RANK:120 )
在线值:
发帖
回帖
粉丝
10
结合这句话看来楼主的代码,就理解了,3Q。。
2013-6-25 12:00
0
雪    币: 59
活跃值: (25)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
11
    向你学习,把复杂的东西简单的解释清楚
2013-6-25 15:15
0
雪    币: 316
活跃值: (128)
能力值: ( LV7,RANK:110 )
在线值:
发帖
回帖
粉丝
12
向大牛致敬,向你学习!!!!!!
2013-6-25 16:22
0
游客
登录 | 注册 方可回帖
返回
//