Symbolic Reachability Analysis Using Narrowing and its Application to Verification of Cryptographic Protocols | Zendy

José Meseguer | Zendy; Prasanna Thati | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Symbolic Reachability Analysis Using Narrowing and its Application to Verification of Cryptographic Protocols

Author(s) -

José Meseguer,

Prasanna Thati

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2004.06.024

Subject(s) - reachability , modulo , generalization , cryptographic primitive , cryptographic protocol , computer science , cryptography , theoretical computer science , set (abstract data type) , model checking , reachability problem , mathematics , discrete mathematics , algorithm , programming language , mathematical analysis

Narrowing was introduced, and has traditionally been used, to solve equations in initial and free algebras modulo a set of equations E. This paper proposes a generalization of narrowing which can be used to solve reachability goals in initial and free models of a rewrite theory R. We show that narrowing is sound and weakly complete (i.e., complete for normalized solutions) under reasonable executability assumptions about R. We also show that in general narrowing is not strongly com- plete, that is, not complete when some solutions can be further rewritten by R. We then identify several large classes of rewrite theories, covering many practical applications, for which narrowing is strongly complete. Finally, we illustrate an application of narrowing to analysis of cryptographic protocols

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research