指标模式漂移后的准确异常检测

1,436 阅读9分钟
原文链接: mp.weixin.qq.com

作者|马明华 张明

编辑|Vicky

1

简介

本文将向大家介绍清华NetMan实验室与搜狗公司合作的最新研究成果:StepWise。StepWise 能快速且准确的适应异常检测系统面临概念偏移的问题。概念偏移(Concept Drift)是指异常检测的对象 KPI(关键业务指标)时序数据发生剧变。概念漂移会直接导致异常检测系统的准确率降低,而StepWise能够使得异常检测算法快速适应并恢复到原来的准确率。 StepWise能应对各种类型的异常检测算法。该论文发表在ISSRE18,软件可靠性工程的旗舰会议(CCF rank B),并且入选了该次会议的 Best Paper Finalist(三篇之一)。

2

背景

随着Web服务如搜索引擎、电子商务和社交网络等突飞猛进的发展,细致的监控服务关键业务指标(KPI,比如页面浏览量、在线用户数、平均响应时间等时序数据流)对保障服务的稳定性尤为重要。我们曾介绍过 KPI 异常检测的框架(opprentice),包括现有的多种类型检测器如滑动平均、时间序列分解(TSD)等。为了能够准确的检测出异常,运维工程师需要花费大量精力选择检测器、调整参数和阈值等。

实际运维场景中调整好的检测器也不是一劳永逸的,我们发现检测准确率会随着时间的推移而显著降低,这是因为 KPI 发生了概念偏移(Concept Drift)。在我们的语境下,Concept 是 KPI 的数据分布,Concept Drift 意为 KPI 的数据分布发生了剧变。而这种变化一般是KPI曲线的阶跃(如图中所示的巨幅下降),或是缓慢的上升/下降(如内存泄露等逐渐恶化的场景)。

概念偏移被运维工程师分成符合预期的与不符合预期的,符合预期的是由运维工程师主动操作或者业务实际增长导致的 KPI 剧变,而不符合预期意味着异常的突变,比如软件变更后导致服务性能受损甚至中断,需要快速回滚到之前的版本。符合预期的概念偏移发生的次数更多,据统计在概念偏移总数中占比超过80%。这是因为运维工程师的日常工作就在做软件的变更,包括软件升级,扩容,迁移和配置更新,以满足部署新特性、修复bug和提升系统性能的需求,比如扩容是把服务部署到更多的服务器上,单台服务器上的请求量就会明显下降,因为全部的请求量是稳定的,这种情况就是一个预期之中的概念偏移:运维工程师认为每台服务器的PV会在很短时间内下降。这些正常的运维操作之后就会使得数据分布发生符合预期的剧变,而异常检测算法总是利用历史的数据分布,不能够准确的预测新的数据分布而做出准确的异常判断。

如下图所示,假设运维工程师使用时间序列分解(TSD)算法做为异常检测器,这个异常检测的参数为扩容以前的 KPI “量身定制”的,绿色的点线可反应其基准线和噪声标准差的正常范围。在8月3日扩容后 KPI 数据分布变化了,TSD 就会产生很长时间(8月3日一天时间)的误报,因为算法本身使用历史的数据预测新的“正常”数据。虽然检测器可以逐渐跟上新的数据分布的基准线,但新的噪声标准差是很难适应的,还会有误报/漏报(如8月6日)。因此 TSD 输出的异常点不再符合运维工程师的需求。我们工作的目标就是适应新的数据分布(运维工程师预期之中的概念偏移)应对各种异常检测系统,以避免长时间的准确率损失。

图 1 概念偏移的示例

3

挑战

1. 频繁出现的符合预期的概念偏移:大型 web 服务每天都会有上千次的软件升级和配置变更,使得 KPI 中会出现很多符合预期的概念偏移。

2. 海量的 KPI 数据:有数十个业务部署在上万的服务器上。每个服务器上都有多种关键指标。

3. 不同类型的异常检测器:针对不同的 KPI 曲线,实际会用到不同种类的异常检测器甚至是几种检测器的组合。

4. 需要快速适应:发生预期之中的概念偏移,运维人员会收到大量的误报和错报。

4

设计思想

发生概念偏移后通过人工重新配置异常检测器参数来应对是很不方便的,针对上述挑战,我们提出了一个自动的、鲁棒的、快速的能适应各种异常检测器的概念偏移的系统 -- StepWise。下图是 StepWise 的设计框架。

图 2 StepWise系统框架

StepWise 主要分为三个部分:

1. 概念偏移的检测:StepWise 系统要位于异常检测系统之前,KPI 数据流输入后首先检测是否有概念偏移。

2. 区分概念偏移是否符合预期:如果有概念偏移,我们需要区分其是否符合预期,不符合预期的概念偏移运维工程师要快速处理该异常,符合预期的进行下一步。

3. 迅速适应符合预期的概念偏移:就是要使得概念偏移后新的数据分布也能快速适配原来精心设计的异常检测算法和参数,输出的数据进行异常检测。

5

概念偏移的检测:iSST-EVT

概念偏移的检测等同于剧变检测,我们之前介绍过的 FUNNEL 使用 improved SST(iSST)算法能快速、准确的检测出KPI剧变,然而该算法应对海量KPI数据还有局限性,它需要运维人员根据不同曲线的剧变分数指定阈值。

我们设计了iSST-EVT算法,利用极值理论(EVT)作为自动设置阈值的工具,极值理论不需要对数据分布(Uniform/Gamma/Frechet)进行假设,而是能通过通用的经验参数来确定阈值。如下图所示,用 iSST 算法可以得到原始 KPI 的剧变分数(图 a 和 b 中绿色虚线所示,由奇异谱分解得到的没有上界的数值,对应于 KPI 中的每个点),而确定剧变点需要对剧变分数设置阈值,这个阈值在不同的 KPI 曲线中不同,EVT 能够自动给出阈值(图 b 中紫色点所示),不再需要手动设置或对剧变分数的分布做假设。

图 3 iSST-EVT 算法结果示例

6

区分概念偏移是否符合预期:DiD

当检测出概念偏移,运维工程师需要根据其领域知识判断其是否符合预期,我们提供了差分分析(DiD)的方法给运维工程师参考。当有准确的活动时刻输入(如上线、配置变更、节假日),DiD 能得到当前的概念偏移是否由该活动导致的而排除其他季节等条件的影响,然后由运维工程师决定该概念偏移是否符合预期。如上线失败与否都可能导致概念偏移,只有运维工程师才能根据其领域知识作出决策。

7

迅速适应符合预期的概念偏移:RLM

对符合预期的概念偏移需要快速使其数据分布适配原来精心设计的异常检测算法和参数,这里我们通过大量的历史概念偏移情况得到一个观察,即新的数据分布和久的数据分布是可以线性拟合的,也就是说新的数据分布是旧的数据分布一个缩放版本。这是有物理意义的,因为扩缩容等产生的概念偏移都是把服务器的流量平均分配到了更多或更少的服务器上。

根据这个观察我们设计了使用鲁棒的线性模型(RLM)进行适应的算法,如下图所示,取概念偏移后新的数据分布全部样本 A,和它的时间段在周期历史上对应的若干段按采样时间逐点取中位数得到 B ,使用 RLM 得到 B 和 A 的线性关系 f = RLM(B ~ A),接下来新收到的时间点数值就由此线性关系进行变化计算 A' = f(A),A' 即作为异常检测器的输入。而后新的点也再加入 A 集合重覆上述得到 f 的过程。这一线性拟合的时间初始可用 6 分钟的数据(正好是第一步概念偏移的检测时间窗),停止计算 f 时间经实验得到最好是 24 小时即一天的时间,之后的新来数据都用 f 进行线性变化。也就是说使用我们的方法,在 6 分钟后就可以适应符合预期的概念偏移,在实际场景中是比较适合的。

图 4 RLM 算法过程示例

8

结论

我们的 StepWise 系统给出快速鲁棒的概念偏移检测与适应方法,通过 iSST-EVT、DiD 和 RLM 适应算法,运维工程师不再需要人工的设置检测算法的参数和阈值,也使得异常检测系统能够持续有效的发挥作用。我们的评估实验是基于搜狗搜索部门提供的真实运维数据,使用几百条、六个月范围有标注的 KPI 数据,发现对比传统不做概念偏移适应的异常检测方法,使用 StepWise 能使得多种常用异常检测算法的平均准确率(F1-score)提升 206%,适应时间约为 6 分钟。

论文题目:Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection

论文作者:Minghua Ma(清华),Shenglin Zhang(南开),Dan Pei(清华),Xin Huang(搜狗),Hongwei Dai(搜狗)

由于篇幅所限,部分内容未在文中详细描述,有兴趣的读者可以关注本公众号之后回复:2018101 ,下载原文后阅读。

长按二维码     关注我们