编辑推荐:
线性时态性质(如线性时态逻辑(LTL)所描述的性质)通常被建模为无限迹的集合。然而,在运行时验证(run-time verification)情境中,例如测试或监控系统时,只能观察到系统行为的有限前缀。对于某些性质,这些有限前缀可能是确定性的——无需进一步观察
线性时态性质(如线性时态逻辑(LTL)所描述的性质)通常被建模为无限迹的集合。然而,在运行时验证(run-time verification)情境中,例如测试或监控系统时,只能观察到系统行为的有限前缀。对于某些性质,这些有限前缀可能是确定性的——无需进一步观察即可给出是或否的答案。研究人员通过用这些确定性前缀丰富LTL的语义,为LTL3(一种面向运行时验证应用的多值线性时态逻辑变体)的语义给出了恰当的归纳式说明。以往工作中对LTL3的语义描述仅以其与常规LTL的关系给出。研究人员证明了LTL与LTL3的语义是同构的。此外,研究人员形式化了运行时验证中常用的公式推进(formula progression)求值技术,并证明了该技术相对于上述语义在有限迹范围内的可靠性与完备性。然后,研究人员转向更一般的线性时态性质:利用确定性前缀理论重新证明了著名的安全-活性分解定理,并重构了无限迹的拓扑。研究人员为性质定义了可监控性(monitorability),为各种可监控性类别提供了简洁的拓扑刻画,并将它们排列成一个层级结构。所有定义与证明均在Isabelle/HOL中机械化实现。
论文《有限时间中的无限》发表于《Information and Computation》,作者为Rayhana Amjad、Rob van Glabbeek和Liam O'Connor。该研究面向反应式与并发系统的规格说明、验证和建模问题,核心是线性时态性质。传统上,线性时态性质被建模为无限迹的集合,经典线性时态逻辑(Linear-time Temporal Logic,LTL)也以无限迹为模型。然而在运行时验证、测试或监控场景中,系统行为仍是无限的,但只能观察到其有限前缀,因此需要处理有限观察与无限行为之间的张力。已有的有限迹逻辑变体LTLf等并不完全适用,因为被观察片段并非完整迹,而是无限行为的有限前缀。某些性质可以通过有限前缀给出确定性结论,这类前缀被称为确定性前缀(definitive prefixes)。LTL3是面向运行时验证的多值LTL变体,但其既有语义仅借助常规LTL定义,且以往文献认为LTL3不能给出归纳式语义。针对这些问题,研究人员发展了系统的确定性前缀理论,并据此为LTL3建立组合式、归纳式的模型语义。
研究人员的主要工作与结论包括:证明LTL与LTL3的语义同构,说明LTL3本质上可视为常规LTL的另一种呈现;形式化公式推进(formula progression)求值技术,并证明其相对于所提出语义在有限迹范围内的可靠性和完备性;利用确定性前缀重新证明著名的安全-活性分解定理,并重构无限迹的拓扑结构;定义多种可监控性类别,给出它们的拓扑刻画并排列成层级。全部定义和证明均在Isabelle/HOL中机械化实现,共超过2900行证明脚本。
关键技术方法方面,研究人员主要使用了以下几类方法:一是确定性前缀和确定性集合理论,用算子?刻画所有扩展均落入某性质的前缀,并据此建立确定性集合与线性时态性质之间的格同构;二是答案索引族(answer-indexed family),以真值答案为输入、模型集合为输出,分别构造常规LTL和LTL3的语义;三是前置运算(prepend operation)?,用于将状态添加到迹的前端,并证明该运算对确定性集合封闭;四是公式推进规则,以语法指导的方式逐步消解公式,再通过归纳证明其与模型语义一致;五是拓扑学方法,利用保证核(guarantee kernel)、安全闭包(safety closure)、度量、内部、闭包和边界等概念刻画安全、活性、保证、共活性以及各类可监控性质;六是在Isabelle/HOL中机械化全部证明。
研究结果按论文主体部分如下。第2节“确定性前缀集”:研究人员定义?X为所有无限扩展均包含于X的迹的集合,证明确定性集合在交下封闭但不在并下封闭;通过定义确定性并作为上确界,证明确定性集合按包含序构成完全格。进一步定义Pr(X)=X∩Σ
ω与Df(P)=?P,证明二者构成确定性集合与线性时态性质之间的格同构,因此每个线性时态性质由其确定性前缀集合唯一确定。第3节“线性时态逻辑”:回顾LTL语法和以无限迹为模型的常规语义。LTL3以三值??
3={??,??,?}解释有限前缀,其中?表示既不能确定满足也不能确定违反,并非第三个语义状态。既有LTL3语义无法组合计算,因为两个子公式同为?时,其析取或合取可能已有确定答案。第4节“LTL与LTL3的语义”:研究人员引入答案索引族,以答案为输入、模型集合为输出。常规LTL中,??答案对应的集合与??答案对应的集合互为补集;LTL3中,输出改为确定性集合,二者不相交但不互补。通过前置运算?X={t | t的尾迹∈X},并证明其对确定性集合封闭,研究人员构造出LTL3的组合式归纳语义。定理4.3证明该归纳语义与Bauer等人原始LTL3定义等价;定理4.4证明LTL3语义与常规LTL语义同构,因此LTL3可视为常规LTL的一种更细致呈现。第5节“公式推进”:给出总且语法指导的推进规则。仅靠局部逻辑化简不足以完全匹配LTL3语义,因为某些重言式需化简为?,矛盾式需化简为⊥。研究人员通过两个引理连接单步推进与前置运算,再按迹长度归纳证明:对有限迹t,公式φ推进后具有平凡语义当且仅当t属于LTL3语义中φ的??答案集合(或相应??答案集合),从而证明公式推进语义的可靠性和完备性。第6节“性质与可监控性”:第6.1节利用保证核与安全闭包刻画保证性质和安全性质。保证核是内部算子,安全闭包是闭包算子;性质空间在度量下可度量化,保证性质恰为开集。由此重新证明Alpern & Schneider经典结果:每个性质是保证性质与共活性(morbidity,即co-liveness)性质之并,取补即得安全-活性分解定理。第6.2节定义好可监控(good monitorable)、坏可监控(bad monitorable)、弱可监控(weak monitorable)、丑陋前缀(ugly prefixes)、BLS(Bauer-Leucker-Schallhart)可监控、义务性质(obligation properties)和强可监控(strong monitorable)。研究证明:安全性质均坏可监控,保证性质均好可监控;弱可监控类恰为好可监控与坏可监控之并;丑陋前缀恰为不可监控迹边界的确定性前缀;BLS可监控等价于性质边界具有空内部,且对补、有限交和有限并封闭;所有义务性质均BLS可监控;强可监控性质恰为既是安全性质又是保证性质的性质。
讨论部分(相关工作)将上述结果与有限-无限语义(finfinite semantics)、语法刻画、Havelund-Peled性质类、RV-LTL可撤销语义以及分支时间监控等进行了比较,指出不同语义框架下可监控性类别的差异,并展望了将确定性前缀理论应用于其他偏迹逻辑、多值逻辑以及超性质监控等方向。结论部分可翻译为:研究人员提出了一个以无限迹语义为基础的运行时验证综合语义基础。通过识别对性质具有决定性意义的有限前缀,研究人员给出了LTL3基于答案索引族的归纳式模型语义,并表明LTL3更宜被理解为常规LTL的更为细致的呈现方式,而非一种独立逻辑。研究人员还形式化了运行时验证与测试中常用的公式推进技术,并证明其相对于该语义的可靠性和完备性。以确定性前缀为基础,研究人员以鲜明的拓扑风格刻画了若干性质类别及其可监控性特征,延续了Alpern & Schneider的研究脉络。全部工作均在Isabelle/HOL中机械化实现。