Automated Verification of Equivalence Properties in Advanced Logic Programs -- Bachelor Thesis

Read original: arXiv:2310.19806 - Published 7/18/2024 by Jan Heuer

🤔

Overview

As the use of Answer Set Programming (ASP) in industrial applications has increased, the need for formal verification tools, particularly for critical applications, has also grown.
During program optimization, it would be desirable to have a tool that can automatically verify whether an optimized subprogram can replace the original subprogram.
This corresponds to the problem of verifying the strong equivalence of two programs, which can be addressed using the anthem translation tool.
The current version of anthem can only verify the strong equivalence of positive programs with a restricted input language, due to the limitations of the tau* translation it implements.

Plain English Explanation

The paper presents an extension to the anthem tool, which is used to verify the strong equivalence of logic programs. Strong equivalence means that two programs produce the same output for any given input.

As the use of Answer Set Programming (ASP) has grown in industry, there is a need for tools that can automatically check if an optimized version of a program is equivalent to the original. This is important for critical applications, where we want to be sure that changes to the program don't accidentally introduce bugs.

The anthem tool was developed to address this problem. It can be used with an automated theorem prover to verify the strong equivalence of two programs. However, the current version of anthem has some limitations - it can only handle positive programs (programs without negation) and a restricted input language.

The paper extends anthem to overcome these limitations. It introduces a new transformation called sigma*, which can express equivalence in the logic of "here-and-there" (a more general logic than classical logic) in classical logic. It also extends the tau* translation used by anthem to handle programs with negation, simple choices, and pools (a type of data structure).

With these extensions, the new version of anthem can verify the strong equivalence of a wider range of logic programs, including those with negation, simple choices, and pools.

Technical Explanation

The paper presents two key extensions to the anthem tool:

The introduction of the sigma* transformation, which can express equivalence in the logic of "here-and-there" (a more general logic than classical logic) in classical logic. This allows anthem to handle programs that cannot be expressed in classical logic alone.
The extension of the tau* translation used by anthem to handle programs with negation, simple choices, and pools (a type of data structure). This expands the class of programs that anthem can verify.

The paper provides theorems that formalize how sigma* and the extended tau* can be used to express the strong equivalence of logic programs in classical logic.

Several examples of logic programs containing pools, negation, and simple choice rules are presented, demonstrating that the new version of anthem can translate these programs to classical logic and verify their strong equivalence.

Critical Analysis

The paper addresses an important problem in the context of Answer Set Programming (ASP) and formal verification, but it also has some limitations:

The extension of tau* to handle programs with negation, simple choices, and pools is a significant contribution, but the paper does not discuss the computational complexity or scalability of this extended translation.
The paper focuses on the theoretical aspects of the sigma* transformation and its integration with tau*, but it does not provide a comprehensive evaluation of the new version of anthem on a diverse set of real-world ASP programs.
The paper does not address the potential limitations or challenges that may arise when integrating the extended anthem tool with automated theorem provers, which are a crucial component of the verification process.

Future research could focus on evaluating the performance and scalability of the extended anthem tool on a wider range of ASP programs, as well as exploring ways to improve its integration with automated theorem provers for more efficient and robust verification of critical applications.

Conclusion

This paper presents an extension to the anthem tool, which is used to formally verify the strong equivalence of logic programs. The extension overcomes the limitations of the previous version of anthem, allowing it to handle programs with negation, simple choices, and pools.

This work is significant because it expands the capabilities of anthem to verify a broader class of ASP programs, which is important for critical applications where program correctness is paramount. The sigma* transformation and the extended tau* translation are key technical contributions that enable this expanded verification capability.

While the paper focuses on the theoretical aspects of these extensions, future research could explore the practical performance and scalability of the new anthem tool, as well as ways to improve its integration with automated theorem provers for more efficient and robust verification of critical ASP applications.

This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!

Follow @aimodelsfyi on 𝕏 →

Related Papers

🤔

Automated Verification of Equivalence Properties in Advanced Logic Programs -- Bachelor Thesis

Jan Heuer

With the increase in industrial applications using Answer Set Programming, the need for formal verification tools, particularly for critical applications, has also increased. During the program optimisation process, it would be desirable to have a tool which can automatically verify whether an optimised subprogram can replace the original subprogram. Formally this corresponds to the problem of verifying the strong equivalence of two programs. In order to do so, the translation tool anthem was developed. It can be used in conjunction with an automated theorem prover for classical logic to verify that two programs are strongly equivalent. With the current version of anthem, only the strong equivalence of positive programs with a restricted input language can be verified. This is a result of the translation $tau^*$ implemented in anthem that produces formulas in the logic of here-and-there, which coincides with classical logic only for positive programs. This thesis extends anthem in order to overcome these limitations. First, the transformation $sigma^*$ is presented, which transforms formulas from the logic of here-and-there to classical logic. A theorem formalises how $sigma^*$ can be used to express equivalence in the logic of here-and-there in classical logic. Second, the translation $tau^*$ is extended to programs containing pools. Another theorem shows how $sigma^*$ can be combined with $tau^*$ to express the strong equivalence of two programs in classical logic. With $sigma^*$ and the extended $tau^*$, it is possible to express the strong equivalence of logic programs containing negation, simple choices, and pools. Both the extended $tau^*$ and $sigma^*$ are implemented in a new version of anthem. Several examples of logic programs containing pools, negation, and simple choice rules, which the new version of anthem can translate to classical logic, are presented. Some a...

7/18/2024

Automated Theorem Provers Help Improve Large Language Model Reasoning

Lachlan McGinness, Peter Baumgartner

In this paper we demonstrate how logic programming systems and Automated first-order logic Theorem Provers (ATPs) can improve the accuracy of Large Language Models (LLMs) for logical reasoning tasks where the baseline performance is given by direct LLM solutions. We first evaluate LLM reasoning on steamroller problems using the PRONTOQA benchmark. We show how accuracy can be improved with a neuro-symbolic architecture where the LLM acts solely as a front-end for translating a given problem into a formal logic language and an automated reasoning engine is called for solving it. However, this approach critically hinges on the correctness of the LLM translation. To assess this translation correctness, we secondly define a framework of syntactic and semantic error categories. We implemented the framework and used it to identify errors that LLMs make in the benchmark domain. Based on these findings, we thirdly extended our method with capabilities for automatically correcting syntactic and semantic errors. For semantic error correction we integrate first-order logic ATPs, which is our main and novel contribution. We demonstrate that this approach reduces semantic errors significantly and further increases the accurracy of LLM logical reasoning.

8/9/2024

Enchanting Program Specification Synthesis by Large Language Models using Static Analysis and Program Verification

Cheng Wen, Jialun Cao, Jie Su, Zhiwu Xu, Shengchao Qin, Mengda He, Haokun Li, Shing-Chi Cheung, Cong Tian

Formal verification provides a rigorous and systematic approach to ensure the correctness and reliability of software systems. Yet, constructing specifications for the full proof relies on domain expertise and non-trivial manpower. In view of such needs, an automated approach for specification synthesis is desired. While existing automated approaches are limited in their versatility, i.e., they either focus only on synthesizing loop invariants for numerical programs, or are tailored for specific types of programs or invariants. Programs involving multiple complicated data types (e.g., arrays, pointers) and code structures (e.g., nested loops, function calls) are often beyond their capabilities. To help bridge this gap, we present AutoSpec, an automated approach to synthesize specifications for automated program verification. It overcomes the shortcomings of existing work in specification versatility, synthesizing satisfiable and adequate specifications for full proof. It is driven by static analysis and program verification, and is empowered by large language models (LLMs). AutoSpec addresses the practical challenges in three ways: (1) driving name by static analysis and program verification, LLMs serve as generators to generate candidate specifications, (2) programs are decomposed to direct the attention of LLMs, and (3) candidate specifications are validated in each round to avoid error accumulation during the interaction with LLMs. In this way, AutoSpec can incrementally and iteratively generate satisfiable and adequate specifications. The evaluation shows its effectiveness and usefulness, as it outperforms existing works by successfully verifying 79% of programs through automatic specification synthesis, a significant improvement of 1.592x. It can also be successfully applied to verify the programs in a real-world X509-parser project.

4/3/2024

📊

Solving Quantified Modal Logic Problems by Translation to Classical Logics

Alexander Steen, Geoff Sutcliffe, Christoph Benzmuller

This article describes an evaluation of Automated Theorem Proving (ATP) systems on problems taken from the QMLTP library of first-order modal logic problems. Principally, the problems are translated to both typed first-order and higher-order logic in the TPTP language using an embedding approach, and solved using first-order resp. higher-order logic ATP systems and model finders. Additionally, the results from native modal logic ATP systems are considered, and compared with the results from the embedding approach. The findings are that the embedding process is reliable and successful when state-of-the-art ATP systems are used as backend reasoners, The first-order and higher-order embeddings perform similarly, native modal logic ATP systems have comparable performance to classical systems using the embedding for proving theorems, native modal logic ATP systems are outperformed by the embedding approach for disproving conjectures, and the embedding approach can cope with a wider range of modal logics than the native modal systems considered.

4/30/2024