RankShift：数据库内分类偏移的检测与解释

# RankShift：分类漂移的数据库内检测与解释  
来源：https://arxiv.org/html/2608.28922  
###### 摘要  

登录服务可能保持通常的失败登录次数，但其中某个来源的占比从2%增长至30%。类似模式也出现在系统日志中：当罕见事件模板变得常见而消息速率保持稳定时，活跃类别发生变化而事件总数不变。RankShift在存储数据的分析数据库内部检测此类变化。它通过皮尔逊散度评分比较每个窗口的类别占比与良性参考基准，评分的各项组成能识别导致变化的类别。该查询可同时返回评分、校准警报及最大正向贡献项。  

我们在HDFS、BGL和Thunderbird数据集上评估RankShift。在HDFS上，其AUROC与计数向量自编码器仅差0.001（0.999对1.000），在Thunderbird上则领先（0.983对0.949）。在受控的固定总量实验中，RankShift能检测到事件计数监控无法发现的罕见类别漂移，达到0.787 AUROC，而自编码器为0.771。在所有三个数据集中，观测到的误报率与设定的运行级别基本一致。RankShift无需模型训练或推理服务，且自编码器的部署状态体积大137倍。  

###### 关键词：  

分类数据、异常检测、分布漂移、数据流、数据库内分析  

## I 引言  

监控系统通常通过请求速率、错误计数或延迟来汇总每个时间窗口。这些指标可能保持稳定，而源地址、路由、事件模板或错误代码的占比却可能发生剧烈变化。图1（https://arxiv.org/html/2608.28922#S1.F1）展示了在失败登录流中的这种模式。分类构成的变化可能揭示新兴来源、故障组件或聚合监控遗漏的新负载模式。有用的监控器必须能够检测变化并识别哪些类别的份额增加或减少。  

现有日志检测器需要预处理、拟合和评分流水线。计数向量方法首先将解析后的事件分组为时间窗口，并对生成的向量进行模型拟合[1]。本文评估的自编码器从良性拟合窗口学习归一化统计量，训练编码器-解码器，并通过重构误差对后续窗口评分。序列检测器构建有序的事件模板序列，并训练下一事件或遮蔽事件预测器[2,3]。部署时需要保留预处理统计量、学习到的权重和推理运行时。  

分布变化方法使用不同的操作状态。QuantTree从参考观测中估计分区，而MStream维护哈希草图和衰减计数[4,5]。它们作为专用流式算法在分析事件表之外运行。  

本文做出三项贡献：  

- **监控方法**：RankShift使用类别级皮尔逊贡献来评分窗口并识别驱动变化的类别。良性评分排名用于校准警报。  
- **评估**：我们在三个真实日志数据集上评估RankShift，并通过固定总量变化实验展示其在何种情况下领先或落后于计数向量自编码器。  
- **原生执行**：实现了等效的NumPy、DuckDB SQL和ADX KQL语义，并测量了正确性、事件量扩展、设置、在线成本和部署状态。  

图1：失败登录中固定总量变化的示例。（a）每分钟包含100次失败登录，其中来源x从总数的2%上升到30%。监控总流量的指标保持平稳。（b）在第8分钟，来源x占RankShift评分的98%（3.92/4.00）。符号表示每个来源是获得还是失去份额。  

## II 相关工作  

**分布监控**：皮尔逊卡方拟合优度检验比较各组观测频率与理论频率[6]。其统计量对每个组的归一化平方偏差求和，允许将总差异追溯到各个组。Lakhina等人分析了网络流中源地址、目标地址和端口的分布[7]。他们用熵概括这些分布，检测了超出基于流量方法发现的异常，并对结果进行聚类以实现无监督异常分类。QuantTree从平稳参考数据中学习具有规定箱概率的多变量直方图，然后使用进入每个箱的观测数测试后续批次[4]。RankShift保留操作类别名称（如源地址和事件模板），并比较其份额，使得总数的均匀变化不会改变评分。  

**日志与流检测器**：日志检测器在学习的关系上有所不同。Xu等人将每个窗口表示为事件模板计数，并使用PCA学习事件类型之间的相关性[1]。DeepLog学习哪些事件模板应跟在前面的序列之后，而LogBERT通过遮蔽事件预测和单类目标学习正常序列上下文[2,3]。流检测器在其他结构上操作。MStream捕获每个记录分类和数值属性之间的相关性，而MIDAS检测重复的源-目标边的突然爆发[5,8]。RankShift解决单个命名分类字段内相对频率的变化。事件顺序、跨字段关系和图结构不在其范围内。  

**解释异常**：现有方法通常解释另一个检测器产生的结果。SHAP将模型预测归因于其输入特征，计算和精确度取决于模型和选择的解释器[9]。ACE和DeepAID类似地在检测器产生异常评分后进行解释[10,11]。相反，MacroBase在已分类为异常值的记录中识别富集的属性值，而加权对数几率排列区分两个语料库的术语[12,13]。RankShift无需单独的解释器。其类别贡献作为评分的一部分计算，精确求和为该评分，并保留操作值（如源地址或事件模板）。  

**数据库内分析**：MADlib将统计分析和机器学习引入关系数据库，允许模型拟合和推理在数据存储位置运行[14]。DuckDB提供嵌入式分析数据库，直接在应用程序进程中执行SQL[15]。这些系统确立了在不将数据移动到单独处理服务的情况下进行分析的价值。RankShift将这一原则应用于分类监控，并通过关系操作同时返回警报及其类别级分解。  

**警报校准**：异常评分本身并不定义何时发出警报。分裂保形方法将新评分与来自保留校准示例的评分进行比较，并将其排名转换为p值[16,17,18]。当良性校准和未来窗口可交换时，在水平α发出警报可将边际误报概率控制在α。RankShift使用良性校准窗口设置此操作级别，而无需为其评分假设参数分布。  

## III RankShift  

### III-A 类别与参考份额  

RankShift监控按固定时间窗口分组的时间戳事件中的一个分类字段。在监控开始前，每个字段值被映射到C个类别之一。具有已知词表的字段（如HTTP状态码）可以直接使用其值。对于非结构化日志，可以从历史数据中学习解析器和模板字典，然后冻结；后续不匹配任何模板的消息映射为OTHER。对于大词表，固定大小的哈希映射是另一种选择。映射决定了RankShift识别驱动因素的精确度：合并到OTHER或相同哈希桶中的值将获得一个组合贡献。  

良性历史建立预期的类别混合。设r_i为参考事件中分配给类别i的数量，R=∑r_i为参考事件总数。在此历史中缺失的类别原始份额为零，不能用于皮尔逊评分，因为评分要除以参考份额。因此，RankShift在所有C个类别上分布一个小伪计数：  

q_i = (r_i + τ/C) / (R + τ), τ > 0。 (1)  
生成的参考份额q_i为正且总和为1。为每个类别分配τ/C，使总平滑量等于τ，无论词表大小。我们在此处使用τ=1，即在类别集上平均分配一个总计为1的计数。  

### III-B 窗口评分与类别贡献  

对于包含N>0个事件的窗口，设s_i为分配给类别i的数量。其观测类别份额为p_i = s_i/N，其中N=∑s_i。RankShift比较观测份额p和参考份额q：  

c_i = (p_i - q_i)² / q_i， X = ∑_{i=1}^C c_i。 (2)  
总和X是观测和参考组成之间的皮尔逊散度。每个项c_i衡量类别i对该差异的贡献程度。对于相同的份额变化，在参考中罕见的类别会获得更大的贡献，因为q_i出现在分母中。每个贡献均为非负，完整集合精确求和为X。平方移除了方向性，因此RankShift也记录p_i - q_i的符号：正值表示获得份额，负值表示失去份额。  

为便于分诊，RankShift报告份额增加的类别中k个最大贡献。失去份额的类别和排名低于k的贡献在完整表中仍可访问，但不在此排序视图中出现。  

RankShift在评分前按每个窗口的总事件数进行归一化。如果每个类别的计数按相同因子增长或减少，观测份额p_i保持不变，因此类别贡献和总评分X也保持不变。因此，该评分将类别混合的变化与流量总量的均匀变化隔离开来。它可以检测在总事件速率保持稳定时的重新分配，如图1所示。保持相同类别份额的激增或下降不会产生RankShift信号，需要单独的流量监控器。  

### III-C 警报校准  

一旦参考份额固定，单独一组良性窗口定义正常的评分范围。设T_1,...,T_n为n≥1个校准窗口的评分。对于评分为X的新窗口，RankShift计算  

p̂ = (1 + |{j: T_j ≥ X}|) / (n + 1)。 (3)  
分子计算评分至少与X一样大的校准窗口数。额外的1将新评分包含在其有限样本排名中，并防止p值为零。较小的p̂表示很少有良性校准窗口产生与新窗口一样大的评分。  

当p̂ ≤ α时，RankShift发出警报。如果校准评分和未来良性评分在参考固定后可交换，则边际误报概率最大为α[16,18]。≥比较将平局的校准评分计入警报。具有固定α的部署可以存储相应的评分截止值，而不是完整的校准样本。  

## IV 数据库执行  

在类别映射固定后，RankShift的部署状态包括C个参考份额和n个排序的校准评分或固定的警报截止值及比较规则。其评分和校准过程没有模型训练阶段、学习到的权重、模型推理运行时或GPU需求。当窗口打开时，每个事件增加一个类别计数。对于具有a个活动类别的窗口，稀疏评分需要O(a)工作，选择k个最大增加贡献需要O(a log k)工作。排序的校准样本支持在O(log n)时间内进行p值查找；固定的警报截止值将决策减少到O(1)。  

RankShift首先按队列、窗口和类别统计事件。数据库物化此分组表一次，允许参考构建、窗口评分、校准和驱动排名重用相同的计数，而无需重新扫描原始事件。密集实现会为每个窗口创建C行，包括事件数为零的类别。RankShift相反使用恒等式  

X = ∑_{i: p_i > 0} (p_i² / q_i) - 1，  
仅使用窗口中存在的类别计算精确评分。附录A给出了推导。参考计数产生平滑份额q_i。当存在类别没有参考计数时，查询分配其来自公式(1)的平滑下限(τ/C)/(R+τ)。  

在对每个测试窗口评分后，查询统计至少与测试评分一样大的校准评分，以产生保形p值和警报。然后保留份额增加的类别，按贡献和类别标识符排序，并返回最大的k个。每个结果包含窗口评分、p值、警报、选定的类别值及其贡献。将返回贡献的总和除以X，得到排序视图表示的评分比例。附录B打印了实验中执行的完整DuckDB SQL。  

保形警报依赖于窗口评分的排序。查询引擎之间的微小浮点差异可能改变平局或使评分跨越警报边界。因此，RankShift将报告的评分与用于决策的值分开。它返回未舍入的评分X，但在比较校准和测试评分之前，将非负副本舍入到六位小数，正好一半向上舍入。DuckDB和ADX使用相同的规则。  

我们在30个窗口的BGL固定装置上比较了两种查询引擎与NumPy参考实现。DuckDB的最大绝对评分差异为3×10⁻⁸，ADX为8×10⁻⁹。两个引擎产生完全相同的p值、警报、贡献值和类别排序。在确切舍入边界处的附加测试证实了相同的行为。