cdxy.me
Footprints on Cyber Security and Python

安全领域与图计算

安全领域噱头不断,前两年不少厂商大吹AI,如今"图计算"一词大有再掀风浪之势。

首先"图"和"计算"应该分开看。"图"是一种数据结构、信息载体。

  • 机器学习的一种思路是将"信息"编码为"数字",然后再对"数字"应用算法来满足业务场景。比如通过embedding将单词映射成空间向量,就可以通过空间距离来表达单词之间含义的相似性。
  • 客观场景中存在一种拓扑信息——谁和谁有何种联系,如网络拓扑、社交拓扑等。这里拓扑知识是一种"信息","图"是承载这一信息的数据结构。为了将信息编码成数字以应用算法,"node embedding"应运而生。

图计算对网络安全场景重不重要?不如换个方式问:拓扑信息这个"特征维度"对"入侵检测"这个二分类问题重不重要。

图计算在什么场景能落地——哪种攻防场景有明显的拓扑特征

Louvain与DGA

Louvain社区发现算法背景知识参考:

  • https://www.cnblogs.com/LittleHann/p/9078909.html

该算法的关键在于边的权重。weight描述的是节点之间的相关性,如何定义、如何计算weight值,直接决定了算法的效果。

在DGA域名检测这个场景中,360netlab团队之前分享的过程如下。

  • https://pc.nanog.org/static/published/meetings/NANOG71/1444/20171004_Gong_A_Dga_Odyssey__v1.pdf

这个过程非常清晰:

  • 将域名视作节点,域名之间的关系视作边,weight表达域名的相关性(用矩阵存储weight),然后用Louvain算法做DGA的家族分类。
  • 域名A与B的相关性(weight)=同时访问过A和B域名的IP数量。

png png

所有算法都有"假设",也就是它的前置条件、适合的场景。

本场景的隐含假设——每个受感染的IP只运行了一种家族的malware

明确这一假设非常重要。如果有大量IP被植入两种或更多家族的malware,则IP维度的统计不能表达出某一家族的特征,需要将malware hash与dns query domain做关联,再统计count(公共hash)作为weight。确认这个假设是否成立,需要数据检验。

LittleHann的博文中对这个问题的描述,原因是没有想清楚weight怎么计算,也就是他的"假设"在他的"场景"下是不成立的。

  1. weight的表征意义问题要特别注意! weigth对于pylouvain社区发现算法来说,期望表征的是节点间的关系,这种关系必须是非对偶已经唯一确定的。 举例来说,如果我们用节点间的simhash相似性来表征来节点间的weight,则会出现这种情况: A <-> B:weight(相似性)= 0.1 B <-> C:weight(相似性)= 0.1 但是,很可能存在 A 和 C 是完全不同的两个样本,所以 A 和 C 属于一个社区的这种传递关系是不能成立的。 本质上来说,这涉及到如何进行图节点间weight的特征工程问题,特征工程提取的方法必须要能unique唯一代表样本本身的规律,不能出现:2+8 = 5+5 这种非唯一的情况,即不能出现两个拥有不同概率分布的样本,特征向量是一样的。

再谈DGA与Louvain:

  1. Louvain是聚类方法,不是二分类方法。适用于DGA家族分类而非DGA域名检测。反之,聚类结果可以作为一个重要维度,辅助DGA域名检测。
  2. Louvain核心在于权重的计算逻辑,需要做清晰的假设验证。

SQL的魅力

上文所述,想清楚如何定义weight之后(先沿用360netlab的方案),还需要计算出这个"权重矩阵",写代码。

这里输入是IP与访问的域名记录(DNS Log),输出是域名之间的相似性矩阵。

如果使用Python完成可能是以下思路:

  1. 清洗出一共这些日志中出现过的域名list
  2. 对1的list中的每个域名,统计访问过这个域名的ip list。
  3. 对1中长度为N的域名list自身做笛卡尔积,初始化N*N的权重矩阵。
  4. 遍历矩阵的每个元素,计算weight(i,j) = len(set(访问过i的IP) & set(访问过j的IP))

这个逻辑用SQL完成,只需一个语句。输入表${t1}有两列ip,domain,每条记录代表这个ip对domain的一次访问。

select 
    a_domain as node1_id, -- 节点1
    b_domain as node2_id, -- 节点2
    count(distinct ip) as weight -- 重复qry的IP数量代表边的权重
from (
    select /*+mapjoin(b)*/
        a.src_ip as ip,
        a.domain as a_domain,
        b.domain as b_domain
    from (
        select distinct src_ip,domain from ${t1}
    ) a join (
        select distinct src_ip,domain from ${t1}
    ) b on a.src_ip=b.src_ip -- 内连接,drop掉weight为0的的边
)_
where a_domain > b_domain -- 去除自连接,去除无向边的计算重复(取上三角矩阵)
group by a_domain,b_domain

输出表有三列node1_id,node2_id,weight,每一条记录代表了两个节点和其间边的权重。由于没有存储和计算weight=0的边,避免了笛卡尔积。

这段简单的SQL搞定了前面两页PPT描述的算法流程,逻辑可以慢慢理解一下。