Page 326 - 《软件学报》2020年第10期

3302 Journal of Software 软件学报 Vol.31, No.10, October 2020

可以看出,得到的匹配序列为 S=T 7 ,T 11 ,T 7 ,T 11 ,T 2 .根据上述公式,我们可以得到当前变量:|S 1 |=7,|S 2 |=5,|S|=5,则
⎛ 7 5 ⎞ 12
计算得到这两个序列之间的距离为 d = ⎜ + ⎟ = = 2.4.
⎝ 5 5 ⎠ 5
3.4 基于自适应K项集的标准进行类别选择

层次聚类中,我们选择的距离度量仅能计算出两条日志类型序列的距离,但无法将任意一个日志类型的序
列映射到向量空间,这样就无法通过求日志类型序列的几何中心得到中心位置的日志类型序列.因此,我们需要
从其他角度来处理这个问题.
日志类型序列可以看成字符串数据.Seker [21] 在使用字符串匹配算法匹配人名时,通过选择人名中前 K 个频
繁出现次数的字母项和其对应数量作为识别人名的关键要素.我们也可以使用相似的方法来确定日志类型序
列的中心位置和单条日志距离其中心位置的距离.即,将同一种异常日志流量模式中所有出现的日志类型数量
的平均值作为该异常日志流量模式的中心数量.在寻找最靠近中心数量的日志类型序列时,考虑到日志序列类
型较多,数量分布不均匀的特点,因此不适合使用原文中固定 K 值法对序列进行比较.在实践中,我们提出一种自
适应 K 值的算法,该算法在计算不同类型日志中心距离时,采用了平均流量的数值进行比较,而对进行比较的类
型数目 K 的选择采用如下公式:
K=CountIf(AverageNum x >AverageTotalNum×Threshold),x=1,…,n.
AverageNum x 代表第 x 类型日志在该异常日志流量模式中出现次数的平均值,AverageTotalNum 代表所有类
别日志在该异常日志流量模式中出现的平均值之和,Threshold 代表异常百分比阈值.在实际操作时,我们将
1
Threshold 取值为 .这样选择是因为在异常流量筛选时,我们确定的日志数量阈值为 HTN,即保证了筛选出
HTN
1
来的每条日志异常流量所包含的日志数目大于 HTN.因此,设定 Threshold = 就保证挑选出的前 K 个频繁
HT N
类型的日志数量至少超过 1 条.因为如果一种类型的日志数量低于 1 条,则显然为不频繁类型.日志数目超过 1
条证明如下:
1
AverageNum > x AverageTotalNum Threshold× > HTN × = 1.
HTN
在确定 K 值后,即可根据平均流量计算每条日志模式序列与中心流量之间的距离,第 m 个日志类型序列与
中心之间的距离公式为
K
d = m i= 1 | AverageNum − ∑ i TypeNum mi |,
其中,AverageNum i 代表第 i 种类型日志在该日志类型序列集合中出现数量的平均值,TypeNum mi 代表第 m 个序
列中第 i 种类别日志出现的数量.根据距离公式将所有距离值计算出来后,将所有序列计算的 d 值中结果最小的
序列作为该类型异常流量的特征序列代表.
m
m
1
2
假设上一小节聚类后得到的 m 类异常日志流量模式记为{Y ,Y ,…,Y },第 m 类异常日志流量模式 Y 包含
()
的日志类型序列的集合记为{S 1 () ,S ( ) ,...,S nm m }, 则自适应最大 k 项集算法具体步骤如下.
m
m
2
w
步骤 1 读取第 w 类日志流量模式的全部日志类型序列集合 Y = {S 1 ()w ,S ()w ,...,S ()w };
2
nw
w
步骤 2 统计 Y 包含的所有日志类型{T w1 ,T w2 ,…,T wt };
∑ nw | S w | ∑ nw | S w | 1
步骤 3 计算数量阈值 AT = i= 1 i × Threshold = i= 1 i × ;
nw nw HTN
w
w
步骤 4 得到前 K 种频繁日志类型{T 1 ()w ,T 2 ()w ,...,T K ()w } {T∈ w 1 ,T w 2 ,...,T wt }, 满足 T x () (x = 1,..., )K 在集合 Y 包
含的日志类型序列中出现数量的平均值大于阈值 AT;
()m
步骤 5 根据公式 d = m K i= 1 | AverageNum − ∑ i TypeNum mi | 计算所有序列 {S 1 ()m ,S ( )m ,...,S nm } 对应的距离{d 1 ,
2
d 2 ,…,d nw };
步骤 6 得到最小距离 d xw =argmin{d 1 ,d 2 ,…,d nw }对应的序列 S xw 即为该异常日志流量模式 NM w ;