Non-Deterministic Planning for Hyperproperty Verification

Overview

• This paper explores using planning as an approach for automated verification of hyperproperties, which are properties that relate multiple paths of a system.
• Hyperproperties can capture important security and information-flow policies, and logics like HyperLTL enable expressing these properties.
• The paper presents an algorithm that converts a HyperLTL verification problem into a non-deterministic multi-agent planning instance, which can then be solved to verify the original property.

Plain English Explanation

Planning is a way for computer systems to figure out a series of actions that will achieve a desired goal, even when the effects of those actions are uncertain. This paper explores using planning as a tool for verifying hyperproperties, which are special properties that look at how a system behaves across multiple possible paths or executions.

Hyperproperties are important for capturing security and information-flow policies, and logics like HyperLTL provide a way to express these properties. However, verifying hyperproperties can be challenging.

The key insight in this paper is that planning can act as a powerful intermediary language for verifying hyperproperties. The researchers present an algorithm that takes a HyperLTL verification problem and converts it into a multi-agent planning problem, where the planning instance corresponds to different possible executions of the system. If a plan can be found for this planning problem, it implies that the original HyperLTL property is satisfied.

This approach can simplify the verification of hyperproperties by leveraging existing planning techniques and tools. Depending on the specific HyperLTL property, the resulting planning instance may correspond to a classical, FOND, or POND planning problem, which have well-studied solution methods.

Technical Explanation

The key technical contribution of this paper is an algorithm that converts a HyperLTL verification problem into a non-deterministic multi-agent planning instance, specifically in the form of a QDec-POMDP (Quantified Decentralized Partially Observable Markov Decision Process).

The algorithm works by creating a planning instance where each agent corresponds to a different execution path of the system being verified. The agents must coordinate their actions to ensure that the overall behavior satisfies the given HyperLTL property. The non-determinism in the planning instance captures the uncertain effects of actions, and the partial observability models the fact that each agent may only observe a subset of the overall system state.

The paper shows that for large fragments of HyperLTL, the resulting planning instance corresponds to well-studied planning problems, such as classical planning, fully observable non-deterministic (FOND) planning, or partially observable non-deterministic (POND) planning. This means that existing planning techniques and tools can be leveraged to verify the original HyperLTL property.

The paper includes a prototype implementation of this approach and reports on encouraging experimental results, demonstrating the viability of using planning as an intermediate language for hyperproperties verification.

Critical Analysis

The paper presents a novel and promising approach for verifying hyperproperties, but there are a few potential limitations and areas for further research:

1. The paper focuses on a specific logic, HyperLTL, and it's unclear how the approach would generalize to other hyperproperties logics or specification languages.
2. The complexity of the resulting planning instances may limit the scalability of this approach, especially for more complex HyperLTL properties.
3. The paper does not provide a comprehensive analysis of the tradeoffs between the planning-based approach and other hyperproperties verification techniques, such as automata-based methods.

Further research could explore extending the planning-based approach to other hyperproperties logics, investigating optimization techniques to improve the scalability of the approach, and conducting a more thorough comparison with alternative verification methods. Additionally, integrating inductive logic reasoning into the planning-based approach could potentially enhance its capabilities.

Conclusion

This paper presents an innovative approach to verifying hyperproperties, a class of system properties that are important for capturing security and information-flow policies. By encoding HyperLTL verification problems as multi-agent planning instances, the researchers have shown that planning can serve as a powerful intermediate language for automated hyperproperties verification.

The key strength of this approach is its ability to leverage existing planning techniques and tools to tackle hyperproperties, which can be challenging to verify using traditional methods. While the paper focuses on HyperLTL, the general idea of using planning as an intermediate language could potentially be extended to other hyperproperties logics, opening up new avenues for research and practical applications in system verification.

Overall, this work demonstrates the versatility of planning and its potential for tackling complex verification problems, highlighting the ongoing synergies between the fields of planning, verification, and formal methods.