Jaccard改进算法在用户实体行为分析分组异常检测中的应用

蒋 明 方 圆

(国家电网安徽省电力有限公司信息通信分公司 安徽 合肥 230009)

0 引 言

用户实体行为分析(User Entity Behavior Analysis，UEBA)是现代安全信息事件管理系统(Security Information Event Management System，SIEMS)中对于安全事件进行二次分析的重要手段，其主要分析的目标是检测主体(可理解为用户、账号、主机等，这些信息均可与实际用户即自然人进行关联)对于客体(可以理解为实体)相关操作中是否存在异常，实体可以是主机、服务/端口、文件夹/文件、系统定时任务、Windows主机的注册表等。一般而言，这种分析的方法包括特征匹配、流式计算、基于机器学习的分析，其中基于机器学习的分析是用户实体行为分析中比较重要的手段。在用户实体行为分析中，可以对特征进行匹配(如使用一些正则方法)或者使用流式计算(其本质上也是一种特征匹配方式，只不过包含了对于多状态机的处理)方法，对于无法使用特征分析的未知威胁则可以利用机器学习的方法进行检测。这些未知威胁检测包括诸如对于数据窃取的分析、数据横向移动的分析、账号盗用分析、金融欺诈(如养号等)、用户撞库、拖库等。

在实际应用中，分组异常或用户分组异常也是一种特别需要关注的未知威胁，而且是非常重要的一种威胁，其判断依据是根据历史数据(主要是用户对于系统的访问日志或者是主机之间的访问记录)，对当前需要检测的数据进行判断；在实际分析中，系统将收集各类访问日志，根据主体之间访问的相似程度划分为若干组，当对相关数据进行验证时，计算其行为是否存在跨组访问。本质上，对于分组异常的分析是一种无监督学习，需要利用诸如K-means、DBScan、山峰聚类、混合高斯、K近邻等聚类分析算法。

由于在实际环境中，可以收集到的访问日志中最多的就是主机之间的连接信息，系统可以比较方便地从诸如网络流量探针或者如路由器、交换机等网络设备的Netflow/sFlow统计信息中较为容易地获得(相较于文件、注册表等的访问而言，如果需要获取这些信息则应在相关主机上安装代理程序)，故分组异常分析的焦点一般也集中于主机之间的访问关系，换言之，可以对主机间访问进行画像，找出其中存在的异常行为，但由于一般在一个大型企业或学校网络中，存在超大量的IP地址(对于一些特殊的大型企业级用户而言，可能超过20万个)，采用一般的聚类算法无法做到快速分析，从而导致实时性较差，故提出基于改进的Jaccard相似性评估算法，此算法特别针对IP地址形成的数据向量，可以较大程度地提升处理速度，而且可以对保存的数据进行压缩。

1 相关算法

在用户实体行为分析中，对于用户分组异常的首要问题就是怎样通过数据对用户进行分组，这需要评估用户之间的相似程度，即用户之间存在多少相似性，这些问题在一些电商网站中的应用显得尤其重要，特别是应用协同过滤在商品推荐的场景下。

由于在本文中，分析的数据是来源于主机之间的访问记录，即主机之间的通信情况，而且主要是分析内网主机之间的访问，所以分析的焦点就是如何根据这些数据对相关访问源主机进行分组划分。

1.1 Jaccard相似性算法

一般而言，用于评估相似性的算法主要包括如余弦夹角、局部敏感哈希、皮尔逊相关系数等方法，而针对主机访问记录，Jaccard相似性算法由于能比较好地适用此方面的数据分析，而且计算较为简单，故在用户相似性分析中采用基于Jaccard算法，其基本计算方法如下。

使用符号ui、uj分别表示现网中的两个用户，其访问主机集合分别是Hi、Hj，而这两个用户的基于访问主机的相似程度计算公式为：

(1)

在式(1)中用户之间的相似度是通过它们访问主机之间的情况来评判的，其分子是用户访问主机的交集而其分母则为用户同时访问主机的并集，当然还有若干种Jaccard的变体，如文献[1]中提出的基于权重的Jaccard相似度度量方法，文献[2]中的相似矩阵方法，另如式(1)中分母修改为较大集合的元素数量等。但无论是哪种Jaccard方法，它们在分析诸如IP主机之间访问行为的场合，都显得捉襟见肘，而且在某种程度上可能不能正确反映不同用户之间的访问关系，其复杂度为O(mn2),其中:m为分组数量；n为用户数量。

另外，本文参照文献[3-9]给出了UEBA中的对于异常分组分析的一系列成套思路，但在这些文献中并未提及分组异常检测的具体方法，文献[10]提出了针对网络流量用户行为异常检测的一些方法，但未就分组异常检测提出相关具体方案，其主要关注点仍是针对一些网络数据特征的抽取。

1.2 Jaccard相似性算法改进

1.2.1网段访问分析

在前文中已经提到，现实环境中可能存在超大规模的主机访问记录，其规模多达20余万，而且它们可能来自不同的内网网段(可能10、172、192等内网均涉及到)，故这些数据离散程度过大，使用传统的Jaccard相似性算法进行集合计算所消耗的CPU性能相当巨大，甚至是不可能完成的任务。

由于是针对IP主机的访问关系分析，故可以对于数据进行一些分层处理并对主机数据进行一定的预备处理。

根据各主机访问目标机器的网段情况，使用{0,1}n向量来标识其访问的目标网段，即通过这种方式先从网段的方面进行划分。如对于一个192.168子网网段，其包含了256子网，在实际实现时，使用32个字节的数组来表示，故可以涵盖这256个子网，如某用户(实际上是主机)对某个子网的数据进行访问，则将其标志值1，否则为0，对于存在n个用户的系统而言，可以形式化地表示为：

A=[a1,a2,…，an]Tai∈{0,1}256

(2)

对于式(2)而言，矩阵A就是不同用户的网段访问关系矩阵，其中每个向量的维度均为256(即可以认为是32个字节)，而且为了计算统一起见，可以将式(1)中的分母部分进行修改，则对于两个用户的相似度而言，可以变形为如下形式：

(3)

可以看出，在式(3)中分母部分已经修改成了所有用户针对所有网段的访问关系，进一步地，如果需要更为快速地进行计算，可以直接将分母部分修改为256，从而加速整体计算；分子的交集计算部分可以直接采用二进制位与方式，以做到最大程度的优化。

另外，为了充分发挥现代CPU指令集的并发能力，可以采用x86平台的AVX2/AVX512向量指令集以并发地进行位与运算，如_mm256_and_pd或_mm512_and_pd等，位与运算的结果中包含多少个1即说明两个用户都访问的网段有多少个；为获取某个变量包含1的数量，算法采用最为快速的查表法(经实验，对于32个字节的计算约为1 000个CPU指令周期)。

1.2.2网段访问聚类

根据不同用户对于网段访问的相似度计算可以形成相似度矩阵，它是一个实对称阵，其行、列均为用户数量，其对角线均为1；进行分组聚类计算时，可以采用一种简单的策略进行聚类，即设定一个用户间相似度阈值tu，如超过tu则可以认为是同组用户，否则不是同组用户，故分组的数量不定。具体算法流程如算法1所示。

算法1网段访问聚类

输入：用户网段访问相似度矩阵。

输出：用户分组后的集类。

Step1初始化用户分组集合(分组集合中的元素是对用户的一个划分，故元素也是集合)。

Step2从网段访问相似度矩阵中获取一个未分组用户向量，将所有大于等于相似度阈值tu的对应用户加入分组集合中的一个元素。

Step3如集合为空，则将自身加入分组集合对应元素；如存在未分组的用户则转Step2，如果用户都已分组完成则转Step4。

Step4算法结束。

最后的用户分组集合形如{{u1,u2},{u3,u4,u5},…}，该集合用G0表示，形式化地可以表示为：

(4)

式中：集合U是所有用户(或者是源主机)组成的全集。

1.2.3主机访问分析和访问异常分析

与前文中对于网段访问的分析类似，具体到某个C类网段而言(如是A类或者B类网段也可以最终分解到C类网段)，需要计算的最多只是254个主机地址(去除子网地址和广播地址)，可以采用改进的Jaccard相似性算法进行计算，其公式也与式(2)、式(3)、式(4)无区别，只不过这里是针对不同的主机，即其向量中的每一维是否访问了某台主机，如访问则为1，否则为0。

通过对于各个C类子网的访问记录计算，可以得到256个(针对B类网络)用户分组集类{Gi}(下标i的取值范围在1到256之间)，每个Gi都是在不同子网下对于同一个用户集合的划分，对于用户分组异常的判断也基于这个集类以及对于网段访问分组情况：{Gi}(i∈[1,256])。

在综合判断用户是否存在分组异常时，遵循如下判断方式，如存在：

∃Uj∈G0Uj∉G′0(ui∈Uj)

(5)

因此，针对各个网段主机访问分组异常的情况，对于某个具体的用户而言，本文算法采用异常分组比例来判断：

(6)

在式(6)中，对于某一网段而言，其分子部分是对一个指示函数I的结果求和，其求和内容主要为当前用户ui出现在分组异常的子网数量，而分母部分的含义则表示取历史分组集合规模和当前分组集合规模的大者(当然分母也可以取别的形式，如仅历史分组或当前分组数量等)。故通过式(6)可以看出在此上下文中，分组异常是一个介于0和1之间的浮点数，在实际应用时，可以设定阈值ta来评判异常分组的程度，一般可以设置为0.5。

2 实验与分析

在实际验证时，从运行系统中采样了历史上最近10天的相关主机访问日志，约20亿条，其主机IP地址为10.0.0.0/8的A类地址，包含了232个C类子网，共52 834个不同的IP地址。

然后对这些IP地址的近3日数据进行采样，分别使用传统不分段、非并行、无位操作的Jaccard相似性算法以及本文的改进后的Jaccard相似性算法实验的性能结果，实验平台为Intel至强E5-2680 V4(此CPU支持AVX2/AVX512指令集)，64 GB内存，操作系统为Ubuntu 18 LTS。表1是对于相关数据的训练情况，表2则是对于数据的验证情况。

表1 数据训练

表2 数据验证

在表1中，包含的源主机数量分别为1 000、2 000、5 000、10 000、20 000及50 000，训练时长单位为ms，可以看出在使用向量指令的情况下，其性能远远高于传统的Jaccard算法，两者相较大约相差约30倍(此数据主要为建立分组的时间，数据加载等时间消耗未统计在内，而且数据是通过10次执行得到的数学期望)。

表2与表1类似，包含的源主机数量分别为1 000、2 000、5 000、10 000、20 000及50 000，验证时长单位为ms，可以看出在使用向量指令的情况下，其性能远远高于传统的Jaccard算法，两者也大约相差近30倍；如果采用多线程并发地进行训练和验证则速度更快。

改进后的Jaccard算法明显在这个较大规模的数据集上，特别是针对IPv4主机连接关系的分组上表现得远比传统算法更快速；另外，它在数据训练上的提升也有良好表现。

通过利用网段划分将用户访问记录进行分层处理，再利用Jaccard算法对相似性进行计算，本文主要实现了一个基于多层模式下的改进Jaccard相似性算法。利用本文方法可以在网段部分直接对验证数据进行筛选，这能够极大地减少CPU计算量。

另外，由于通过使用基于二进制位与操作的并行处理方法和用固定数值替代集合并集运算，也能在很大程度上对整体算法进行加速，从而做到对超大规模数据的处理。

最后，由于本文算法采用了二进制位方法表示访问情况集合，故在相关数据的存储上也极为节省空间，而且在对威胁进行回溯时，获取相关异常源来进行展示也较为方便。

3 结 语

本文所提出的Jaccard改进算法主要是针对IP主机间访问的，对于一些其他的诸如用户访问文件/文件夹、注册表、系统定时任务等也是可以应用的，但如果在纯IPv6环境下，针对IP地址的访问分析，此方法可能需要做一些改动方可使用，其主要原因是IPv6包含了巨大的地址空间，当然可以采用其他方法根据现网情况进行建模。

由于本文主要分析的访问记录是针对内网环境下的，但在有外网主机参与的情况下该如何高效地进行分组是一个需要考虑的问题，初步想法应还是根据访问目标的地理位置而非最终的访问目的IP地址进行，这在一定程度上对数据进行了缩减，当然也可以使用Jaccard算法进行。

对于用户的分组一般采用硬分组方法，即一个用户只能属于一个组，这种分类方法可能在一些场景下导致未必能非常真实地反映客观情况，或者造成过多的离群数据，反而导致结果不可用，所以可以考虑采用软分组方法处理之，即针对用户给出其所属用户组的概率，依照此概率进行分组，从而在一定程度上避免硬分组所带来的问题。

对于一些实在无法分组的离群数据的处理也是今后需要解决的问题，这可能是需要最终算法检验结果是否可用并能在实际使用时是否适用的重要方面。