A logical approach to automated program verification has been drawing attention recently, where various program verification problems are transformed into formulas of fixpoint logics such as CHC and \(\nu \) HFL(Z), so that a given program satisfies a property just if the corresponding fixpoint formula is valid. In this paper, we show a kind of converse transformation, converting fixpoint logic formulas to programs so that a formula is valid just if the resulting program never evaluates to an (error) value. This, together with the aforementioned transformation from programs to formulas, allows us to go back and forth between logical formulas and programs. In particular, our transformation enables us to use random testing to disprove a given formula, implying that the original program does not satisfy the specified property. As the programs generated by a naive transformation are not suitable for random testing, we employ mode analysis to generate more test-friendly programs. We have implemented the mode-guided transformation and confirmed its effectiveness through experiments.

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

Mode-based Reduction from Validity Checking of Fixpoint Logic Formulas to Test-Friendly Reachability Problem

  • Hiroyuki Katsura,
  • Naoki Kobayashi,
  • Ken Sakayori,
  • Ryosuke Sato

摘要

A logical approach to automated program verification has been drawing attention recently, where various program verification problems are transformed into formulas of fixpoint logics such as CHC and \(\nu \) HFL(Z), so that a given program satisfies a property just if the corresponding fixpoint formula is valid. In this paper, we show a kind of converse transformation, converting fixpoint logic formulas to programs so that a formula is valid just if the resulting program never evaluates to an (error) value. This, together with the aforementioned transformation from programs to formulas, allows us to go back and forth between logical formulas and programs. In particular, our transformation enables us to use random testing to disprove a given formula, implying that the original program does not satisfy the specified property. As the programs generated by a naive transformation are not suitable for random testing, we employ mode analysis to generate more test-friendly programs. We have implemented the mode-guided transformation and confirmed its effectiveness through experiments.