A Novel Symbolic Approach to Verifying Epistemic Properties of Programs

Nikos Gorogiannis, Franco Raimondi, Ioana BoureanuIJCAI 2017 · DOI

TL;DR

This paper introduces a new symbolic method for verifying epistemic properties (like "agent A knows X") of programs. By reducing these complex verification problems to standard first-order logic queries, their approach can leverage existing powerful SMT solvers, offering a competitive and often faster alternative to traditional model-checking techniques for epistemic logics.

What Problem Does This Paper Address?

Verifying properties related to knowledge and belief (epistemic properties) in complex systems is crucial for security and reliability. Existing tools for this often require translating programs into a specialized logic, making it difficult to work directly with program code or handle rich state specifications (like those involving integers). This paper bridges the gap between program verification, which excels at handling concrete programs and expressive state descriptions, and epistemic logic verification, which focuses on knowledge. They aim to verify epistemic properties directly on programs, using a symbolic approach that can handle general-purpose programming languages and expressive base logics.

Methods

The core of the paper is a novel methodology that translates epistemic properties of programs into first-order logic (FOL) formulas. This translation relies on:

  • A Symbolic Framework: They define a framework that allows users to specify a base logic (e.g., propositional logic, linear integer arithmetic), a programming language (e.g., loop-free imperative programs), and which variables each agent can observe.
  • Strongest Postcondition (SP) Operator: They leverage the concept of the strongest postcondition, a standard tool in program verification, which computes the most precise post-state of a program given a pre-state.
  • Reduction to First-Order Logic: The key innovation is a function, denoted by $\tau$, that translates epistemic formulas into FOL. This translation, combined with the SP operator, allows them to reduce the problem of verifying an epistemic property of a program to checking the satisfiability of a FOL formula.
  • Handling Undecidability: For cases where the SP operator cannot be precisely computed (e.g., due to unbounded loops), they propose an over-approximation technique. This results in a sound but potentially incomplete verification method, mirroring common practices in program analysis.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and its evaluation on established problems.

Key Insights and Ideas

  • Bridging Program and Epistemic Verification: The paper successfully connects two distinct verification domains by using program verification techniques (SP operator) to tackle epistemic logic properties.
  • Leveraging SMT Solvers: By reducing the problem to FOL, the approach can harness the power of highly optimized SMT solvers (like Z3), which are often more scalable than specialized epistemic model checkers.
  • Flexibility in Base Logic: The framework is designed to be instantiated with various base logics, allowing for verification of epistemic properties over rich state spaces (e.g., involving integers and arithmetic).
  • Performance Gains: For certain types of epistemic properties and system sizes, their method demonstrates significant speedups compared to existing state-of-the-art epistemic model checkers.

Key Results

The paper presents two main theoretical results:

  1. Theorem 3.3: When the strongest postcondition operator is computable (e.g., for loop-free programs), the validity of program-epistemic specifications is equivalent to the validity of the translated first-order formulas.
  2. Theorem 3.5: When the strongest postcondition can only be over-approximated, the validity of positive epistemic specifications (in a fragment called $L_K^{\neg\neg}$) implies the validity of the translated first-order formulas (sound but incomplete).

Experimental results on two case studies (Dining Cryptographers and ThreeBallot Voting Protocol) show that their approach, implemented using SMT solvers, can be competitive with and often significantly outperform existing model checkers like MCMAS, especially for larger instances of the problems. For example, they report speedups of several orders of magnitude for certain Dining Cryptographers scenarios.

Limitations and Future Work

The authors acknowledge several limitations and outline promising future research directions:

  • Temporal Expressivity: The current framework is limited to verifying properties about final states of programs and cannot directly encode complex temporal properties (like "until" operators). Future work aims to extend this by drawing inspiration from techniques for verifying temporal properties in infinite-state systems.
  • Common Knowledge: Properties involving common knowledge are not currently supported. The authors plan to investigate extensions to handle this, possibly using fixpoint techniques.
  • Handling Negative Epistemic Properties: When the SP operator is not well-behaved, the current method is restricted to positive epistemic properties. They suggest that static analysis techniques like abstract interpretation could be used to extend their approach to handle negative properties.
  • Security and Privacy: Future work includes embedding different security semantics to verify privacy and anonymity properties, potentially by extending their methodology to handle more complex security protocols.
  • Scalability: While competitive, performance still degrades with increasing system size (number of agents, voters, candidates), particularly for complex specifications. Further optimizations and theoretical advancements are needed.

Summary updated

BibTeX
@inproceedings{gorogiannis2017novel,
  author = {Nikos Gorogiannis and Franco Raimondi and Ioana Boureanu},
  title = {{A Novel Symbolic Approach to Verifying Epistemic Properties of Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/30},
}

Loading related content...

Figure