Probabilistic reasoning of inconsistent belief in protocol analysis

Qingfeng Chen, Chengqi Zhang, Yi-Ping Phoebe ChenPROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS AND KNOWLEDGE ENGINEERING (ISKE ) 2007 · OpenReview

Abstract

Formal verification of security protocols typically assumes a binary state of truth, which proves inadequate in real-world scenarios characterized by malicious actors and conflicting information. This paper introduces a novel framework that integrates probabilistic reasoning with Quasi-Classical (QC) logic to handle inconsistent beliefs among protocol participants. By utilizing Minimal QC (MQC) models and weighted belief aggregation, the proposed method quantifies the trustworthiness of protocol goals even in hostile environments. The framework is validated through a simulation of the Secure Electronic Transaction (SET) protocol, demonstrating its ability to derive security conclusions from contradictory data.

Introduction

Traditional security analysis tools, such as BAN logic, operate under the assumption of a "perfect world" where participants are generally honest and communication channels are secure. However, in practical applications, principals often hold divergent or even contradictory beliefs about the state of a protocol. Standard logics suffer from the "explosion principle," where a single contradiction allows for the proof of any statement, rendering the analysis useless. To address this, we propose a multi-layered approach that treats inconsistency not as a failure of the model, but as quantifiable data reflecting environmental hostility.

Methodology

Quasi-Classical Logic and Minimal Models

To circumvent the limitations of standard logic, this framework employs Quasi-Classical (QC) logic. Unlike classical logic, QC logic allows for the simultaneous existence of a fact ($+\alpha$) and its negation ($-\alpha$) without leading to mathematical collapse. This property is essential for modeling scenarios where different principals provide conflicting evidence regarding message authenticity or integrity.

The core of the reasoning process involves Minimal QC (MQC) models. These models are used to calculate a Support Function, which provides a numeric estimation of partial belief. The Support Function measures the "Quality of Support" for a specific belief by evaluating the ratio of evidence supporting a claim versus evidence refuting it.

Probabilistic Extension of Non-monotonic Dynamic Logic (ENDL)

The framework extends the "Extension of Non-monotonic Dynamic Logic" (ENDL) by incorporating probabilities. Instead of treating inference rules as absolute, each rule is assigned a probability representing the "inferred belief." This allows the system to account for the reliability of different inference paths.

Belief Aggregation and Rule Independence

A critical aspect of the framework is how it combines beliefs from multiple sources. The model recognizes that not all participants (e.g., Sender, Receiver, Third Party) are equally authoritative. Consequently, it assigns weights ($\varpi$) to different principals. The final belief in a protocol goal is a weighted sum of these individual perspectives.

Inference structure for belief aggregation from multiple message sets ($M_R, M_T$) to a protocol goal $m$ using various rules.

As illustrated in Figure 1, a protocol goal $m$ may be supported by multiple message sets ($M_R, M_T$) through various inference rules ($rule_1, rule_2, rule_3$). The framework distinguishes between independent and dependent rules—those sharing common conditions—to accurately calculate the cumulative probability of the conclusion.

Case Study: The SET Protocol

The proposed method was evaluated using simulated data from the Secure Electronic Transaction (SET) protocol, a standard for securing credit card transactions. The simulation involved a scenario where the Sender, Receiver, and a Third Party held conflicting "observed beliefs" about a message's authenticity.

The analysis utilized a Discriminant threshold ($\eta$). If the total calculated belief $Bel(m)$ exceeds this threshold, the protocol goal is deemed secure. In the experiment:

  • The calculated total belief $Bel(m)$ was 1.5.
  • The security threshold $\eta$ was set at 0.85.

Since $Bel(m) > \eta$, the framework correctly concluded that the message was secure, effectively filtering through the "noise" of conflicting data points to reach a consensus.

Conclusion and Future Work

This research demonstrates that probabilistic QC logic provides a robust mathematical foundation for reasoning about security in uncertain environments. By treating inconsistency as a metric rather than an error, the framework offers a more realistic assessment of protocol security.

Future work will focus on refining the assignment of weights ($\varpi$) to principals, which currently remains a manual and somewhat arbitrary process. Additionally, we aim to conduct performance benchmarks to compare the computational overhead of QC-logic-based approaches against traditional formal methods and explore dynamic models that track belief evolution over multiple protocol steps.

Summary updated

BibTeX
@inproceedings{chen2007probabilistic,
  author = {Qingfeng Chen and Chengqi Zhang and Yi-Ping Phoebe Chen},
  title = {{Probabilistic reasoning of inconsistent belief in protocol analysis}},
  booktitle = {PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS AND KNOWLEDGE ENGINEERING (ISKE )},
  year = {2007},
  url = {https://openreview.net/forum?id=yIGG0uijiP},
}
Figure