Abstract
Traditional verification of probabilistic systems often fails when faced with hyperproperties—requirements that relate multiple execution traces, such as noninterference or side-channel resilience. This paper presents HyperPCTL, a powerful temporal logic for expressing these properties, and a scalable Statistical Model Checking (SMC)* framework. By leveraging a novel multi-dimensional statistical test based on the Sequential Probability Ratio Test (SPRT), the proposed approach overcomes the state-space explosion that limits exhaustive model checkers, enabling the verification of systems with up to $2^{1000}$ states.
Introduction: The Challenge of Hyperproperties
In computer security, many critical requirements are hyperproperties, which describe relationships between sets of execution traces rather than individual ones. For instance, "probabilistic noninterference" ensures that a secret input does not alter the probability distribution of observable outputs. Verifying such properties requires comparing multiple paths, a task that is computationally expensive.
Existing verification tools face two primary hurdles:
- Expressiveness: Many logics cannot handle nested probabilistic requirements or explicit quantification over specific paths.
- Scalability: Exhaustive model checking, which calculates exact probabilities by exploring every state, suffers from exponential state-space explosion. This makes it impractical for complex, real-world systems.
Proposed Logic: HyperPCTL*
To address the expressiveness gap, the authors introduce HyperPCTL*. This logic extends previous frameworks by supporting nested operators (reasoning about the "probability of a probability"), arithmetic operations on probabilities (e.g., $P(\pi_1) + P(\pi_2) > p$), and explicit path variables for precise reasoning about path interactions.
The formal semantics, as shown in Figure 1, allow for complex path-based reasoning. For example, the logic can explicitly quantify over multiple paths $\pi_1, \pi_2, \dots, \pi_n$ to evaluate their collective behavior.
Statistical Model Checking Framework
To solve the scalability problem, the authors propose a Statistical Model Checking (SMC) approach. Instead of exhaustive state exploration, SMC uses sampling to estimate probabilities.
Sequential Probability Ratio Test (SPRT)
The framework employs the Sequential Probability Ratio Test (SPRT), a "lazy" sampling method. Unlike fixed-size sampling, SPRT continues to draw samples only until sufficient statistical evidence is gathered to accept or reject a hypothesis with a predefined confidence level.
Multi-Dimensional Indifference Regions
A key innovation of this work is the introduction of multi-dimensional indifference regions. Standard SPRT is designed for simple comparisons (e.g., $p > \theta$). However, HyperPCTL* formulas often involve complex arithmetic over multiple probabilities. The authors frame this as a geometric problem: the property is satisfied if the vector of sampled probabilities falls within a specific convex region in $n$-dimensional space. This allows the tool to handle nested quantifiers and complex mathematical conditions that were previously intractable for statistical methods.
As illustrated in Figure 3, hyperproperties involve reasoning about multiple paths simultaneously. The SMC approach samples these path combinations to build a statistical profile of the system's behavior.
Evaluation and Results
The tool was evaluated on several security benchmarks modeled as Discrete-Time Markov Chains (DTMCs), including timing side-channels in chat servers, parallel programs, and the Dining Cryptographers protocol.
- Massive Scalability: The framework successfully verified a 1,000-node Dining Cryptographers model. With a state space of $2^{1000}$, this system is far beyond the reach of numerical solvers.
- High Accuracy and Speed: Across all case studies, the algorithm achieved 98% to 100% accuracy, matching the desired statistical confidence. Most scenarios were verified in under 30 seconds on standard hardware.
- Efficiency: The SPRT-based approach proved more efficient than previous confidence-interval methods, requiring fewer samples to reach a conclusion.
Conclusion
By combining a highly expressive logic (HyperPCTL*) with a novel geometric approach to statistical testing, this work provides a scalable solution for verifying complex security hyperproperties. Future work includes extending the framework to timed hyperproperties and integrating symbolic techniques to further enhance verification capabilities.
Summary updated