可靠计算系统设计分析与验证课程笔记 4,内容对应 Sessions 6–7:Error Detection,讨论 watchdog、heartbeat、Data Audits、控制流检查、应用感知断言,以及 RMK、SHD、AHD 和 Count&Check

错误检测

上一篇介绍了可靠性技术的分工。这一篇展开容错中的检测环节:系统如何发现自己已经进入错误状态,怎样在错误传播到服务接口之前作出反应?

检测器通常直接观察的是错误的表现,例如迟迟没有完成一个步骤、变量超出合法范围,或者执行路径偏离预期。观察到异常并不等于已经知道根因,而没有告警也不等于系统一定正确。理解每个检测器观察了什么,是分析覆盖率的起点

怎样评价一个错误检测器

检测器至少涉及四个方面:

  • 覆盖率:目标错误中,有多少被检测到
  • 检测延迟:从错误发生或被激活,到发出告警经过多久
  • 误报与漏报:正确行为被判错,以及错误行为没有被发现
  • 开销:额外时间、内存、代码体积、硬件资源和运维成本

覆盖率首先需要一个明确的分母。故障注入实验中,常见统计对象包括注入事件、真正被激活的错误,以及最终影响输出或造成失效的错误,三者不能混用

例如某个检测目标集合为 EE,在其中被发现的事件集合为 DD,则

Coverage=∣D∩E∣∣E∣\mathrm{Coverage}=\frac{|D\cap E|}{|E|}

检测器还可能发现 EE 之外的内部异常,因此不能把所有告警数量直接除以 ∣E∣|E|。误报率同样要说明按检查次数、请求数、运行次数还是时间统计

检测必须与恢复衔接

容错链通常包含检测、定位、遏制和恢复。错误被发现后,可以停止继续输出、隔离组件、切换副本或恢复 checkpoint。如果只记录日志,而错误结果已经提交给外部,检测对当前请求的保护可能已经太晚

在前面介绍的可用性模型中,缩短发现与恢复的总时间能够降低平均停机时间。但检测器不会自动减少原始故障发生的概率,其效果取决于告警时机、恢复策略及是否引入误切换

watchdog:是否在期限内完成了进度

Watchdog Timer 是一种成本较低的检测方法。被监控程序必须在超时前重置定时器;如果长期没有重置,监控方就怀疑程序已经失去正常进展

正常路径可以表示为

完成阶段工作⟶重置定时器⟶下一阶段工作\text{完成阶段工作}\longrightarrow\text{重置定时器} \longrightarrow\text{下一阶段工作}

发生错误时,若程序不再到达重置点,定时器到期就能触发告警和恢复

重置点放在哪里很关键

假设一个线程陷入死循环,而循环内部仍不断重置 watchdog,监控方就永远不会超时。因此重置操作应当对应真正需要验证的工作进度,而不是任意一段仍能运行的代码

同样,一个后台监控线程仍在刷新定时器,并不说明业务线程没有死锁。watchdog 观察的是“重置动作是否发生”,没有直接检查业务数据或结果

超时值还要求正常工作耗时相对可预测。阈值太短,会把负载波动或慢操作误判为故障;阈值太长,则增加发现故障的时间。对于每阶段耗时差异很大的程序,应按阶段设计进度检查和期限

它主要改善哪一个指标

例如,历史系统使用 watchdog 监测子系统自检、缓冲区归还、锁释放以及处理器响应等事件。重置系统或释放资源可以缩短停机时间,因而改善可用性

但若故障已经造成服务中断,再快速重启也不能把“从未失效”的任务历史恢复回来。如果检测发生在错误传播到服务接口之前,并成功恢复,才有机会避免这次外部失效。因此分析效果时要写清服务边界和检测时机

heartbeat:从本机进度扩展到分布式响应

在分布式系统中,监控方定期向进程或节点发送探测消息,并等待回复;超过预定时间没有响应,就将其标记为疑似失效,并启动后续处置。节点主动周期性上报也是常见组织方式

heartbeat 与 watchdog 的共同点是用时间约束观察活性,但 heartbeat 还受到网络延迟、丢包和对端负载的影响。没有收到回复,可能是进程失效,也可能是网络暂时拥塞,因此超时首先提供的是怀疑信号

Adaptive Heartbeat 与 Smart Heartbeat 解决不同问题

方法 改变什么 主要目的
固定超时 heartbeat 使用预先约定的期限 实现简单,适合负载与延迟较稳定的场景
Adaptive Heartbeat 根据网络和节点状态调整超时值 减少环境变化造成的误报
Smart Heartbeat 回复前执行预定义健康检查 让回复包含更多业务健康信息

Adaptive Heartbeat 处理“等多久才合理”,Smart Heartbeat 处理“回复能代表什么”。仅把阈值调得更准确,无法解决“回复线程正常而业务线程已经死锁”的覆盖问题

Smart Heartbeat 可以在回复前检查关键线程、队列或必要的数据关系,但检查范围仍需明确。检测路径本身也依赖 CPU、网络和调度资源,不能默认监控方永远不受故障影响

Capability Checking 与 Consistency Checking

这类机制不主要观察耗时,而是判断当前操作或数值是否满足已知约束

Capability Checking 限制哪些主体可以访问哪些对象,例如处理器或进程是否允许访问某个内存区域、I/O 设备或受保护资源。越权操作会引发异常或拒绝访问

Consistency Checking 则检查状态是否落在允许范围内,例如

  • 概率值必须位于 [0,1][0,1]
  • 目标地址必须存在,并满足对应访问条件
  • 指令操作码必须是体系结构定义的有效编码
  • 算术运算不能超出所要求的数值范围

两类机制可以互补:地址本身可能存在,但当前进程没有访问权限;操作可能获得授权,但输入值已经不符合应用语义

这类检查的优势是约束明确、检测位置接近错误使用点。其覆盖范围也由约束决定:一个错误值仍落在合法区间内,范围检查就无法发现它

异常处理:把硬件发现的异常交给软件

处理器和 MMU 可以发现非法指令、缺页、保护违规和某些算术异常,再将控制权转交给操作系统。以 x86 和 Linux 为例介绍这条处理路径

Fault、Trap 与 Abort

这里的 fault 是 x86 的异常分类名称,需要与可靠性故障链中的 Fault 区分。按处理后返回位置和可恢复性,典型分类为

分类 处理语义 典型例子
Fault 保存的位置指向引发异常的指令,修复条件后可以重新执行 缺页、某些保护违规
Trap 在触发指令完成后报告,通常从后续指令继续 软件断点
Abort 严重异常,可能无法精确报告触发位置,也不能按普通方式重新执行 双重故障等严重异常

这种分类依据异常的体系结构语义,不能简单等同于“无意触发”与“有意触发”,具体定义可参见 Intel 系统编程手册中的异常分类

缺页不一定意味着程序出错

缺页可能来自按需分页或写时复制,也可能来自非法地址访问。前者是正常的内存管理过程,内核建立映射后可以重试指令;后者则可能导致向用户进程发送信号或进入内核错误处理路径

还要区分 TLB 未命中 和缺页异常:TLB 中没有缓存某个地址转换,不代表页不存在。若页表给出有效映射,地址转换仍可以继续完成

硬件和软件怎样衔接

从概念上看,处理过程为

检测异常⟶确定异常向量⟶保存必要上下文⟶进入处理程序\text{检测异常}\longrightarrow\text{确定异常向量} \longrightarrow\text{保存必要上下文}\longrightarrow\text{进入处理程序}

处理程序根据异常类型、访问地址以及用户态或内核态等上下文,决定补齐资源、返回错误、发送信号、终止进程,还是执行更严重的系统处置

在异常处理过程中也可能再次出错,或者因为未释放锁而演化为挂起,所以捕获一次异常并不意味着故障影响已经结束

Data Audits:从数值合法到业务关系一致

Data Audits 在电信交换系统等场景中广泛使用。它把应用已知的数据约束变成周期性或事件触发的检查,既检查单个字段,也检查记录之间的结构与语义关系

静态数据与动态数据

对运行中不应变化的静态数据,可以在可信初始化阶段计算基准校验和,之后周期性重新计算并比较。若结果不同,就怀疑发生了非预期修改

动态数据正常情况下就会变化,不能一直与启动时的比特内容比较。可以改用字段范围、枚举值、状态转换规则或其他不变量,判断当前值是否合法

Structural Audit

考虑数据库采用固定且已知的记录大小,系统表保存布局信息。审计器根据记录大小计算各记录头应当出现的偏移,再检查相应位置的头字段是否符合预期

这类检查能发现记录错位、表结构损坏等问题。其前提是布局元数据本身可信;不同存储格式需要相应的结构检查方法

Semantic Referential Integrity Check

比“记录存在”更进一步的是:记录之间的关系是否闭合。以一次语音连接为例,使用三张表:

表 关键字段
进程表 Process ID、Connection ID、Status
连接表 Connection ID、Channel ID、Caller ID
资源表 Channel ID、Process ID、Status

活跃连接应当形成一致的依赖环:

Connection ID⟶Channel ID⟶Process ID⟶Connection ID\text{Connection ID}\longrightarrow\text{Channel ID} \longrightarrow\text{Process ID}\longrightarrow\text{Connection ID}

如果连接已经结束,资源表仍标记通道被占用,或者进程引用的连接记录已经消失,局部字段可能都在合法范围内,但整体关系已经不一致。沿依赖环审计,可以发现资源泄漏、孤立记录和关键属性损坏

实现时还应考虑合法的更新中间状态,例如通过一致快照或事务边界进行检查,避免把正常并发更新误认为数据损坏

控制流监测:程序是否按允许的路径执行

数据可能损坏,指令地址、返回地址和分支目标同样可能出错。控制流监测尝试把执行路径编码成签名,再与预期路径比较

这里的签名是执行特征,不是密码学中的数字签名

硬件与软件两种组织方式

硬件方案可用一个 watchdog processor 观察主处理器的地址与数据流,并与预先计算的签名比较。签名可以嵌入程序,也可以存放在监控处理器自己的存储中

这类方案需要专用资源和较紧密的耦合。缓存、多线程交错和复杂运行环境也会增加观察与重建路径的难度,因此更适合结构较简单的嵌入式场景

软件方案则把程序分成基本块或其他代码单元,在入口、出口或分支附近插入检查代码,无需额外的监控处理器,但会增加执行指令和维护签名的开销

路径签名怎样表示执行

在基本块中插入 Emit 事件,可以把分支和循环编码成运行时序列

用Emit事件记录分支与循环路径
用Emit事件记录分支与循环路径

图中允许的路径签名为

A B(CDB)∗EA\,B(CDB)^*E

每轮循环发出 C,D,BC,D,B,退出时发出 EE。运行时检查实际事件序列是否匹配该表达式,即使程序仍在运行或最终返回了结果,也能识别不合法的执行路径

为什么要在跳转前检查

若检查代码只放在目标块入口,错误跳转可能直接落到任意指令位置,从而绕过检查代码,在下一个检测点之前就已经执行危险操作

PECOS(Preemptive Control Signatures) 的核心是先求出即将使用的目标地址,在实际跳转之前判断

Xout∈{X1,X2,…,Xk}X_{\mathrm{out}}\in\{X_1,X_2,\ldots,X_k\}

其中右侧是允许的目标集合。不满足时先触发异常,尽量阻止非法目标中的指令被执行。可以通过断言块和异常机制实现这一过程

这种前置检查缩短了错误传播的窗口,但如果错误选择的是另一个合法目标,单纯的目标集合检查仍可能接受它。控制流符合图结构,不代表这次输入下的分支选择一定正确

应用感知错误检测(Application-Aware Error Detection)

通用机制知道地址、指令和时间约束,应用感知检测器还利用变量的含义以及变量之间的关系,自动或人工生成运行时断言

一个检测器可以看作一个二元选择:

检测器位置=(程序位置, 被检查变量)\text{检测器位置}=(\text{程序位置},\ \text{被检查变量})

即使检查同一个变量,放在刚产生错误的位置、放在输出之前,或者放在错误已经被覆盖之后,覆盖率与检测延迟也会不同

故障模型(Fault Model)

检测对象限定为应用使用的数据值错误,可能来自硬件或软件两方面

  • 硬件错误(Hardware Errors):内存或逻辑电路中的瞬态错误(soft errors)导致错误计算,且未被 ECC 捕获;指令和程序逻辑中的许多错误也可能通过异常数据值表现出来
  • 软件错误(Software Errors):未初始化或错误初始化的变量、内存损坏、整数溢出,以及同步错误和竞态条件

检测是否成功取决于错误值能否到达检测点,以及断言能否识别其异常。如果控制流错误绕过了检查,或直接把执行转移到程序之外,这类检测器就无法通过该检查发现错误,需要与控制流监测等机制配合

动态分析与静态分析的配合

动态分析通过正常运行采集选定位置的变量值,归纳取值集合、范围和变化模式。静态分析则可以从检测点做后向切片,找出影响该变量的语句,并建立相应的符号关系

实际断言类型包括

类型 检查形式
常量 ai=ca_i=c
交替值 (ai=x∧ai−1=y)∨(ai=y∧ai−1=x)(a_i=x\land a_{i-1}=y)\lor(a_i=y\land a_{i-1}=x)
多值集合 ai∈Va_i\in V
范围 l≤ai≤ul\leq a_i\leq u
固定差值 ai−ai−1=ca_i-a_{i-1}=c
有界差值 l≤ai−ai−1≤ul\leq a_i-a_{i-1}\leq u

还可以让多个线程或系统实体交叉检查它们对共享状态的认识,但交叉检查需要明确同步关系和观察时刻,否则读到不同版本的合法状态也可能引发告警

理想检测器与实际检测器

为了研究放置位置,可以先假设“理想检测器”:只要指定位置的变量值错误,它就能百分之百识别。这个假设把问题暂时集中到位置选择,而不是断言能否精确描述正确值

在 gcc95 实验中,选择 1010 个理想检测器可覆盖约 80%80\% 的崩溃和 60%60\% 的 silent data corruption,而对无害错误的检测约为 4%4\%。随机在热点路径放置检测器,则需要约 100100 个理想检测器才能达到约 90%90\% 的覆盖率

这些数值说明位置选择的重要性,但不代表十条普通范围断言就能获得相同效果。使用实际断言后,课件给出的不同程序的已表现错误覆盖率约为 50%50\% 至 75%75\%,效果受程序特征和断言表达能力影响

检测器数量增加也可能带来更多误报。如果训练数据没有覆盖某种合法输入,对训练范围之外的正确状态就可能错误告警。因此断言部署需要同时观察错误覆盖和正常执行的接受情况

操作系统级检测:Reliability Microkernel

Reliability Microkernel(RMK) 是一个用于组织检测与恢复功能的操作系统内模块框架。这里的 microkernel 指可靠性机制的核心组织层,并不要求把整个操作系统改成微内核体系结构

Pin、Module 与 Core

RMK 把平台相关操作和检测策略分开:

部分 职责 例子
Pin 封装底层硬件和系统服务,产生统一事件 捕获上下文切换、接收异常或信号
Module 实现具体检测与恢复策略 系统挂起检测、应用挂起检测
Core 管理 Pin 与 Module,分派事件和操作请求 订阅事件、加载配置、动态部署与移除

例如调度 Pin P_SCHL 捕获进程上下文切换,向模块发出 EVT_CONTSWITCH 事件,并提供安装与恢复拦截的操作。Linux 和 Windows 下的具体拦截方式不同,而上层模块尽量使用相同的事件接口

这种分层让检测模块不必各自重新实现调度拦截和硬件计数器管理,也便于组合多个检测策略

SHD:用指令计数发现系统挂起

System Hang Detection(SHD) 关注内核长时间执行或等待、用户线程却无法推进的情形,例如内核无限循环或导致处理器无法正常交还给调度器的错误

用上下文切换建立进度界限

在一定调度条件下,正常执行中相邻两次上下文切换之间的指令数量有一个可学习的上界。SHD 使用剖析计数器与检查计数器共同判断是否超出这个界限

系统挂起检测中的剖析计数器与检查计数器
系统挂起检测中的剖析计数器与检查计数器

虚线的 profiling counter 在相邻切换之间累计指令数,为检查阈值提供依据;实线的 checking counter 从阈值递减。若迟迟没有正常切换,计数器耗尽就触发 NMI,报告疑似挂起

与固定墙钟超时相比,指令数量更直接反映处理器执行进度,但效果仍取决于工作负载、调度策略和阈值是否匹配

NMI 提供了一条不同于普通可屏蔽中断的进入路径,有助于在部分内核异常状态下触发检测。它也不是对任意硬件失效都有效的万能入口

实验结果怎样读

在设备驱动调用场景中向内核代码内存注入错误,共执行 13461346 次实验。按最先观察到的结果分类如下:

最先观察到的表现 实验数 后续出现挂起的次数 检测到的挂起
正确输出 391 1 1
静默错误输出 380 0 0
内核异常 485 30 30
silent hang 90 90 90

其中 121121 次挂起均被检测到,实验中没有观察到误报。不能把这个结论写成“检测到了全部 13461346 次注入错误”,因为 SHD 的目标是挂起,而不是任意错误输出

“先有正确输出或内核异常,后有系统挂起”还说明,错误可以继续传播,第一次可见结果不是事件链的终点。包括空指针访问进入异常处理后再次出错,以及锁未释放使系统继续停滞

AHD:把挂起检测细化到线程与代码区段

系统仍然可以调度,并不代表某个应用线程没有死锁或陷入循环。Application Hang Detection(AHD) 进一步监视函数、循环、循环迭代或互斥区段

它通过硬件计数器统计线程实际执行的指令,并为每个“线程—受监控区段”维护逻辑计数器。如果未离开区段就超过了预期指令数量,则怀疑发生挂起

一个硬件计数器怎样服务多个逻辑区段

基本组织方式是

  1. 线程切换时,读出上一时间片执行的指令数,累计到该线程所有活跃区段
  2. 进入区段时,记录当前硬件计数器基值,并标记区段活跃
  3. 离开区段时,结算指令数、记录历史并清除活跃标志
  4. 根据历史行为更新检查阈值,之后继续检测

通过基值和逻辑计数器,计数可以跨时间片累计,并处理一个线程中多个同时活跃的受监控区段。将其他线程的指令错误累计进去,会直接破坏检测结果

阻塞线程还需要时间检查

若线程阻塞在锁上,它本身可能几乎不再执行指令,单纯依赖指令数就不会越过阈值。因此还周期性检查带有活跃区段的线程时间戳:如果长时间没有推进,同样报告挂起

这体现了两种进度信号的互补:指令计数有助于识别“持续执行但不退出”,时间检查则覆盖“停止执行却一直不完成”

可以在 Apache 上评估该机制:12061206 次人工挂起注入均被检测;18611861 次目标代码比特翻转实验中,18541854 次表现为崩溃、77 次表现为被检测到的挂起;20002000 次无故障注入实验中出现 11 次挂起告警。最后一组对应按实验次数计约 0.05%0.05\% 的误报,这些结果限定于该原型和测试条件

Count&Check:检测合法但错误的路径

控制流错误不一定表现为跳到非法地址。软件缺陷或错误输入可能使程序走上一条在源代码中完全存在、但当前语义下不应该选择的路径

例如表大小意外变成零后,初始化分支被跳过,程序继续使用未初始化的数据。每次跳转都可能满足控制流图的边约束,传统非法分支检查却无法据此判断结果正确与否

Count&Check(C&C) 尝试用正常执行中观察到的函数事件与指令数量,进一步区分这些路径

签名加入了指令数量

一个示意签名可以写成

1
2
sort() entry --22 instructions--> memcpy() entry
sort() entry --19 instructions--> malloc() entry

这里的数字是特定编译结果与实验环境下的指令计数,不是算法本身固定的常数

如果程序跳过分配或初始化,但仍然调用相同的后续函数,函数调用序列未必变化,两个事件之间的指令数量却可能不同。把它加入签名,就有机会发现只有调用序列看不见的异常

对不同代码结构,指令数量呈现不同模式:顺序代码通常固定,分支可以形成不同的离散计数,循环与迭代次数相关,函数成功和失败的执行路径也可能具有不同范围

训练与运行时检查

训练阶段使用正常输入执行程序,提取函数事件序列与计数模式。运行时再把观察到的特征与签名集比较。一种方案使用二进制重写插桩和硬件性能计数器,并在系统调用等检查点检验执行路径

其基本假设是错误行为通常会改变这些特征,但这种改变并不必然发生。错误若只影响与路径无关的数据,或者错误分支恰好与另一种正常执行具有相同签名,就可能漏检

训练也有两个方向的风险:

  • 合法路径未被训练覆盖,会在运行时产生误报
  • 训练把错误路径当作正常行为接受,会导致后续漏报

改进方法包括覆盖更多预期输入类别、按函数训练、人工确认异常路径,以及注入已知错误来辨别正常与错误模式

覆盖率实验中的分母

在 SimpleScalar 原型上评估 Siemens 测试程序,向函数参数和返回值注入比特翻转。两组正常执行检查的误报数分别为 Replace 的 4/3004/300 和 Tot_info 的 4/2004/200,对应约 1.3%1.3\% 和 2%2\%;Schedule2 的 300300 次检查中没有误报

错误检测实验中,Replace 的 7272 个已表现错误中检测到 6666 个,覆盖率约为 91.7%91.7\%;Tot_info 的 5656 个已表现错误中检测到 4747 个,约为 83.9%83.9\%

Schedule2 的统计尤其容易误读:比如 145145 个已表现错误,却有 151151 个检测结果,并报告对已表现错误的覆盖率为 100%100\%。原因是检测器还发现了没有改变最终输出、但改变内部状态的错误,不能直接用 151/145151/145 作为覆盖率

还有许多已激活错误没有表现为外部错误。例如程序只检查返回值是否非零,11 被翻转成 0x110x11 后仍满足成功分支。这样的语义屏蔽说明,注入次数、激活次数和已表现错误数之间可能相差很大

Apache 配置错误案例

接下来展示了一条业务层面的传播链:配置项本应控制最大空闲 HTTP 服务进程数,却接收到非数字字符串;程序通过 atoi() 得到零值后没有正确检查,导致一个线程周期性清理空闲服务进程,另一个线程又因进程不足不断创建进程,最终服务行为不稳定

C&C 利用非数字输入在转换函数中执行的指令较少这一差异发现异常。这个案例说明,检测信号可以出现在最终服务失效之前的底层函数中,进而辅助定位配置处理缺陷

从宿主系统扩展到虚拟机

最后,将 RMK 扩展到虚拟化场景:一部分机制放在受保护虚拟机中的设备驱动里,另一部分放在 Hypervisor 中,通过接口协同观察虚拟机和内部应用

崩溃检测可以在 Hypervisor 层捕获虚拟机及其应用相关的崩溃信号;挂起检测则结合客户机调度事件和 Hypervisor 调度事件,检查虚拟机的执行进展

这里计数范围非常重要:虚拟机被换出期间,其他虚拟机消耗的指令不应该算到它头上。判断“长期没有进展”时,也需要区分客户机已经得到 CPU 却不推进,与宿主根本没有调度它运行

把检测器放在更低层可以提供额外观察视角,但上层业务是否正确仍需要应用信息。虚拟机仍在执行指令,不代表它正在完成有用工作

怎样组合这些检测机制

机制 主要观察对象 典型覆盖范围 需要补充的观察
watchdog 重置动作与期限 未到达进度点、长时间停滞 数据与输出正确性
heartbeat 节点或进程响应 无响应、通信异常 业务线程和依赖服务状态
Capability Checking 与 Consistency Checking 操作权限、地址和数值约束 越权、非法值、部分算术异常 合法范围内的语义错误
Data Audits 数据内容、布局和引用关系 数据损坏、孤立记录、资源泄漏 与业务更新一致的检查时刻
控制流签名与 PECOS 事件路径、跳转目标 非法路径或非法目标 合法但语义错误的选择
应用感知断言 关键变量及其关系 经过检测点的数据异常 断言表达能力和位置覆盖
SHD / AHD 调度进展、区段指令数和时间戳 系统或应用挂起 未挂起的错误输出
Count&Check 函数事件与指令数量模式 部分非法路径及合法但错误的路径 签名不变的数据错误

选择检测机制时,应先确定故障模型、服务边界和错误传播路径,再安排检测点与恢复动作。时间、数据、控制流和调度进展提供的是不同证据,组合使用有助于覆盖单一机制看不见的错误

验证时则需要同时报告目标错误覆盖率、误报、检测延迟和开销,并保留故障注入与工作负载条件。只有把这些条件写清,才能判断一个检测器能否在当前系统中及时阻止错误传播,或者有效缩短恢复时间


© 2024 本网站由 renxiaodaifu 使用 Stellar主题 创建
总访问 次 | 本页访问 次

共 12 篇博客 · 共 89 篇 wiki · 总计 32.1k 字