In this paper, we introduce a framework for programmable logic controller programs that combines a deductive verification approach on control flow automata with an inductive verification technique used to automatically derive loop invariants. The deductive verification is based on Hoare triples that are propagated through loop-free sections of the program using strongest postcondition and weakest precondition. Loop invariants are derived from loop pre- and postconditions with a modified version of the IC3 algorithm with predicate abstraction. While this approach is straightforward for programs with a single loop, programs with multiple loops require iterating potential loop invariants between the loops until an overall proof can be found. We demonstrate the efficacy of our approach by evaluating example programs, showing both improved performance compared to inductive verification of the complete program, and a push-button approach to deductive verification requiring – ideally – no user-supplied loop invariants.

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

IC3 for Loop Invariant Generation in Deductive Analysis

  • Niklas van de Sand,
  • Marcus Völker

摘要

In this paper, we introduce a framework for programmable logic controller programs that combines a deductive verification approach on control flow automata with an inductive verification technique used to automatically derive loop invariants. The deductive verification is based on Hoare triples that are propagated through loop-free sections of the program using strongest postcondition and weakest precondition. Loop invariants are derived from loop pre- and postconditions with a modified version of the IC3 algorithm with predicate abstraction. While this approach is straightforward for programs with a single loop, programs with multiple loops require iterating potential loop invariants between the loops until an overall proof can be found. We demonstrate the efficacy of our approach by evaluating example programs, showing both improved performance compared to inductive verification of the complete program, and a push-button approach to deductive verification requiring – ideally – no user-supplied loop invariants.