安全领域与图计算

安全领域噱头不断，前两年不少厂商大吹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数量。

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

本场景的隐含假设——每个受感染的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描述的算法流程，逻辑可以慢慢理解一下。