paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Asynchronous Extensions of HyperLTL

HyperLTL 的异步扩展
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 3/10 · 该论文属于形式化验证中的超属性时序逻辑与模型检测复杂度研究,与用户核心关注的 LLM/Agent 和静态分析/形式化验证交叉、浮点程序分析及贝叶斯程序分析均无直接关联。仅可作为形式验证与逻辑背景参考,不涉及 AI 或程序分析工程落地。引用 0 inbox
Laura Bozzelli, Adriano Peron, Cesar Sanchez
crossref: 2026-09-12

AI 速览

一句话:提出 HyperLTL 的两种异步正交扩展 HyperLTLS 与 HyperLTLC,证明一般模型检测不可判定并给出可判定片段及复杂度。

HyperLTL 等超属性时序逻辑通常采用同步语义,难以直接表达异步信息流安全等需求。本文引入两种异步且正交的扩展:Stuttering HyperLTL(HyperLTLS)与 Context HyperLTL(HyperLTLC)。作者证明这两个逻辑的模型检测问题一般是不可判定的,同时分别识别出一个可判定的模型检测片段;这些片段均包含 HyperLTL,并能表达有意义的异步要求。文章进一步给出这两个片段模型检测的精确计算复杂度,其中 HyperLTLS 片段的复杂度与表达力更弱的 HyperLTL 相同。

问题
HyperLTL 等超属性时序逻辑采用同步语义,难以刻画异步信息流安全等异步超属性需求。
方法
引入 Stuttering HyperLTL 与 Context HyperLTL 两种异步正交扩展,并为它们分别定义可判定模型检测片段。
评估
通过可判定性与计算复杂性分析,证明一般模型检测不可判定,并给出两个可判定片段的精确复杂度。
原文摘要(Abstract)

Hyperproperties are a modern specification paradigm that extends trace properties to express properties of sets of traces. Temporal logics for hyperproperties studied in the literature, including HyperLTL, assume a synchronous semantics and enjoy a decidable model checking problem. In this paper, we introduce two asynchronous and orthogonal extensions of HyperLTL, namely Stuttering HyperLTL (HyperLTLS) and Context HyperLTL (HyperLTLC). Both of these extensions are useful, for instance, to formulate asynchronous variants of information-flow security properties. We show that for these logics, model checking is in general undecidable. On the positive side, for each of them, we identify a fragment with a decidable model checking that subsumes HyperLTL and that can express meaningful asynchronous requirements. Moreover, we provide the exact computational complexity of model checking for these two fragments which, for the HyperLTLS fragment, coincides with that of the strictly less expressive logic HyperLTL.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot6160,
  title = {Asynchronous Extensions of HyperLTL},
  author = {Laura Bozzelli and Adriano Peron and Cesar Sanchez},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470583}
}