Many important properties of computer systems are relational properties, which are often difficult to express and verify. Dynamic logics are well-known formalisms for program verification. We present a general extension, called the rel extension, of dynamic logics to support first-class relational reasoning. The extension provides intuitive syntax to express relational properties, which may be difficult or impossible to express in the host dynamic logic. The rel extension can be instantiated for different host logics. Verifying relational properties expressed by the rel extension can benefit from techniques developed for general relational reasoning and domain-specific relational reasoning, and existing tools developed for the host logic. We validate the applicability of the rel extension by instantiating it for a well-known dynamic logic: differential dynamic logic (d \(\mathcal {L}\) ). As a result, the instantiation can express key relational properties that cannot be easily expressed with d \(\mathcal {L}\) . We develop an encoding for the instantiation to leverage existing verification tools for d \(\mathcal {L}\) . We conduct an experiment on a set of benchmarks, and successfully verify a set of non-trivial relational properties either fully or semi automatically.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Extending Dynamic Logics with First-Class Relational Reasoning

  • Jian Xiang,
  • Stephen Chong

摘要

Many important properties of computer systems are relational properties, which are often difficult to express and verify. Dynamic logics are well-known formalisms for program verification. We present a general extension, called the rel extension, of dynamic logics to support first-class relational reasoning. The extension provides intuitive syntax to express relational properties, which may be difficult or impossible to express in the host dynamic logic. The rel extension can be instantiated for different host logics. Verifying relational properties expressed by the rel extension can benefit from techniques developed for general relational reasoning and domain-specific relational reasoning, and existing tools developed for the host logic. We validate the applicability of the rel extension by instantiating it for a well-known dynamic logic: differential dynamic logic (d \(\mathcal {L}\) ). As a result, the instantiation can express key relational properties that cannot be easily expressed with d \(\mathcal {L}\) . We develop an encoding for the instantiation to leverage existing verification tools for d \(\mathcal {L}\) . We conduct an experiment on a set of benchmarks, and successfully verify a set of non-trivial relational properties either fully or semi automatically.