The Experts below are selected from a list of 312 Experts worldwide ranked by ideXlab platform
Bruno Blanchet - One of the best experts on this subject based on the ideXlab platform.
-
Security Protocol Verification: Symbolic and Computational Models
2012Co-Authors: Bruno BlanchetAbstract:Security Protocol Verification has been a very active research area since the 1990s. This paper surveys various approaches in this area, considering the Verification in the symbolic model, as well as the more recent approaches that rely on the computational model or that verify Protocol implementations rather than specifications. Additionally, we briefly describe our symbolic security Protocol verifier ProVerif and situate it among these approaches.
-
POST - Security Protocol Verification: symbolic and computational models
Lecture Notes in Computer Science, 2012Co-Authors: Bruno BlanchetAbstract:Security Protocol Verification has been a very active research area since the 1990s. This paper surveys various approaches in this area, considering the Verification in the symbolic model, as well as the more recent approaches that rely on the computational model or that verify Protocol implementations rather than specifications. Additionally, we briefly describe our symbolic security Protocol verifier ProVerif and situate it among these approaches.
Jun Pang - One of the best experts on this subject based on the ideXlab platform.
-
Stateful Security Protocol Verification.
arXiv: Cryptography and Security, 2014Co-Authors: Jun Pang, Yang Liu, Jun Sun, Jin Song DongAbstract:A long-standing research problem in security Protocol design is how to efficiently verify security Protocols with tamper-resistant global states. In this paper, we address this problem by first proposing a Protocol specification framework, which explicitly represents Protocol execution states and state transformations. Secondly, we develop an algorithm for verifying security properties by utilizing the key ingredients of the first-order reasoning for reachability analysis, while tracking state transformation and checking the validity of newly generated states. Our Verification algorithm is proven to be (partially) correct, if it terminates. We have implemented the proposed framework and Verification algorithms in a tool named SSPA, and evaluate it using a number of stateful security Protocols. The experimental results show that our approach is not only feasible but also practically efficient. In particular, we have found a security flaw on the digital envelope Protocol, which could not be detected by existing security Protocol verifiers.
-
Cones and foci: A mechanical framework for Protocol Verification
Formal Methods in System Design, 2006Co-Authors: Wan Fokkink, Jun PangAbstract:We define a cones and foci proof method, which rephrases the question whether two system specifications are branching bisimilar in terms of proof obligations on relations between data objects. Compared to the original cones and foci method from Groote and Springintveld, our method is more generally applicable, because it does not require a preprocessing step to eliminate τ-loops. We prove soundness of our approach and present a set of rules to prove the reachability of focus points. Our method has been formalized and proved correct using PVS. Thus we have established a framework for mechanical Protocol Verification. We apply this framework to the Concurrent Alternating Bit Protocol.
-
FoSSaCS - Cones and foci for Protocol Verification revisited
Lecture Notes in Computer Science, 2003Co-Authors: Wan Fokkink, Jun PangAbstract:We define a cones and foci proof method, which rephrases the question whether two system specifications are branching bisimilar in terms of proof obligations on relations between data objects. Compared to the original cones and foci method from Groote and Springintveld [22], our method is more generally applicable, and does not require a preprocessing step to eliminate τ-loops. We prove soundness of our approach and give an application.
-
Cones and foci for Protocol Verification revisited
Report - Software engineering, 2002Co-Authors: Wan Fokkink, Jun PangAbstract:We define a cones and foci proof method, which rephrases the question whether two system specifications are branching bisimilar in terms of proof obligations on relations between data objects. Compared to the original cones and foci method from Groote and Springintveld cite{GroSpr01}, our method is more generally applicable, and does not require a preprocessing step to eliminate $ au$-loops. We prove soundness of our approach and give an application.
Sebastian Mödersheim - One of the best experts on this subject based on the ideXlab platform.
-
Automated Stateful Protocol Verification
The Archive of Formal Proofs, 2020Co-Authors: Andreas Victor Hess, Sebastian Mödersheim, Achim D. Brucker, Anders SchlichtkrullAbstract:In Protocol Verification we observe a wide spectrum from fully automated methods to interactive theorem proving with proof assistants like Isabelle/HOL. In this AFP entry, we present a fully-automated approach for verifying stateful security Protocols, i.e., Protocols with mutable state that may span several sessions. The approach supports reachability goals like secrecy and authentication. We also include a simple user-friendly transaction-based Protocol specification language that is embedded into Isabelle.
-
On the relationships between models in Protocol Verification (extended version)
CTIT technical reports series, 2011Co-Authors: Sebastian MödersheimAbstract:We formally investigate the relationship between several models that are widely used in Protocol Verification, namely variants of the inductive model of message traces inspired by Paulson’s approach, and models based on rewriting. More precisely, we prove several overapproximation relationships between models, i.e. that one model allows strictly more traces or reachable states than the other. This is common in Verification: often an over-approximation is easier to prove correct than the original model, and proving the over-approximation is safe implies that the original model is safe—provided that the models are indeed in an overapproximation relation. We also show that some over-approximations are not sound with respect to authentication goals. The precise formal account that we give on the relation of the models allows us to correct the situation.
-
Formal Aspects in Security and Trust - Integrating automated and interactive Protocol Verification
Formal Aspects in Security and Trust, 2010Co-Authors: Achim D. Brucker, Sebastian MödersheimAbstract:A number of current automated Protocol Verification tools are based on abstract interpretation techniques and other over-approximations of the set of reachable states or traces. The Protocol models that these tools employ are shaped by the needs of automated Verification and require subtle assumptions. Also, a complex Verification tool may suffer from implementation bugs so that in the worst case the tool could accept some incorrect Protocols as being correct. These risks of errors are also present, but considerably smaller, when using an LCF-style theorem prover like Isabelle. The interactive security proof, however, requires a lot of expertise and time. We combine the advantages of both worlds by using the representation of the over-approximated search space computed by the automated tools as a “proof idea” in Isabelle. Thus, we devise proof tactics for Isabelle that generate the correctness proof of the Protocol from the output of the automated tools. In the worst case, these tactics fail to construct a proof, namely when the representation of the search space is for some reason incorrect. However, when they succeed, the correctness only relies on the basic model and the Isabelle core.
-
On the relationships between models in Protocol Verification
Information & Computation, 2007Co-Authors: Sebastian MödersheimAbstract:We formally investigate the relationships between several models that are widely used in Protocol Verification, namely variants of the inductive model of message traces inspired by Paulson's approach, and models based on rewriting. More precisely, we prove several over-approximation relationships between models, i.e. that one model allows strictly more traces or reachable states than the other. This is common in Verification: often an over-approximation is easier to prove correct than the original model, and proving that the over-approximation is safe implies that the original model is safe-provided that the models are indeed in an over-approximation relation. We then show that some over-approximations are not sound with respect to a common formalization of authentication goals based on exchanged messages. The precise formal account that we give on the relation of the models allows us to correct the situation.
Chyan-goei Chung - One of the best experts on this subject based on the ideXlab platform.
-
Symbolic path-based Protocol Verification
Information and Software Technology, 2000Co-Authors: Wen Chien Liu, Chyan-goei ChungAbstract:The principal problem in Protocol Verification is state explosion problem. In our work (W.C. Liu, C.G. Chung, Path-based Protocol Verification Approach, Technical Report, Department of Computer Science and Information Engineering, National Chiao-Tung University, Hsin-Chu, Taiwan, ROC, 1998), we have proposed a “divide and conquer” approach to alleviate this problem, the path-based approach. This approach separates the Protocol into a set of concurrent paths, each of which can be generated and verified independently of the others. However, reachability analysis is used to identify the concurrent paths from the Cartesian product of unit paths, and it is time-consuming. Therefore, in this paper, we propose a simple and efficient checking algorithm to identify the concurrent paths from the Cartesian product, using only Boolean and simple arithmetic operations.
-
Path-based Protocol Verification approach
Information and Software Technology, 2000Co-Authors: Wen Chien Liu, Chyan-goei ChungAbstract:Abstract Protocol Verification is one of the most challenging tasks in the design of Protocols. Among the various proposed approaches, the one based on reachability analysis (or known as state enumeration approach) is of the most simple, automatic and effective. However, the state explosion problem is a principle obstacle toward successful and complete Verifications of complex Protocols. To overcome this problem, we proposed a new approach, the “path-based approach.” The idea is to divide a Protocol into a collection of individual execution record, denoted as concurrent paths, a partial order representation recording the execution paths of individual entities. Then, the Verification of the Protocol is, thus, replaced by that of individual concurrent paths. Since concurrent paths can be automatically generated through Cartesian product of the execution paths of all modules, and verified independently, the memory requirement is limited to the complexity of individual concurrent path rather than the whole Protocol. Thus, the state explosion problem is alleviated from such “divide and conquer” approach. Furthermore, we propose an algorithm, making the trade-off on memory requirement to generate the concurrent paths more efficiently; and utilize the technique of symmetric Verification, parallel computing to improve the efficiency of Verification. Eventually, our experience of verifying real Protocols shows that our approach uses much less memory and time than reachability analysis.
-
Protocol Verification using concurrent paths
Fifth Asia-Pacific Conference on ... and Fourth Optoelectronics and Communications Conference on Communications, 1999Co-Authors: Wen Chien Liu, Chyan-goei ChungAbstract:To overcome the state explosion problem, we proposed the path-based approach, representing the system as a set of concurrent paths. The concurrent paths can be generated automatically and verified independently, thus the complexity of Verification is reduced and the problem is alleviated.
Natarajan Shankar - One of the best experts on this subject based on the ideXlab platform.
-
experiments in theorem proving and model checking for Protocol Verification
Formal Methods, 1996Co-Authors: Klaus Havelund, Natarajan ShankarAbstract:Communication Protocols pose interesting and difficult challenges for Verification technologies. The state spaces of interesting Protocols are either infinite or too large for finite-state Verification techniques like model checking and state exploration. Theorem proving is also not effective since the formal correctness proofs of these Protocols can be long and complicated. We describe a series of Protocol Verification experiments culminating in a methodology where theorem proving is used to abstract out the sources of unboundedness in the Protocol to yield a skeletal Protocol that can be verified using model checking.
-
FME - Experiments in Theorem Proving and Model Checking for Protocol Verification
FME'96: Industrial Benefit and Advances in Formal Methods, 1996Co-Authors: Klaus Havelund, Natarajan ShankarAbstract:Communication Protocols pose interesting and difficult challenges for Verification technologies. The state spaces of interesting Protocols are either infinite or too large for finite-state Verification techniques like model checking and state exploration. Theorem proving is also not effective since the formal correctness proofs of these Protocols can be long and complicated. We describe a series of Protocol Verification experiments culminating in a methodology where theorem proving is used to abstract out the sources of unboundedness in the Protocol to yield a skeletal Protocol that can be verified using model checking.
