Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

Protocol analysis modulo combination of theories: A case study in Maude-NPA

  • Sasse, Ralf
  • Meadows, Catherine
  • Meseguer, José
  • Escobar Román, Santiago|||0000-0002-3550-4781
There is a growing interest in formal methods and tools to analyze cryptographic protocols modulo algebraic properties of their underlying cryptographic functions. It is well-known that an intruder who uses algebraic equivalences of such functions can mount attacks that would be impossible if the cryptographic functions did not satisfy such equivalences. In practice, however, protocols use a collection of well-known functions, whose algebraic properties can naturally be grouped together as a union of theories E 1... ¿ n. Reasoning symbolically modulo the algebraic properties E 1... ¿ n requires performing (E 1... ¿ n)-unification. However, even if a unification algorithm for each individual E i is available, this requires combining the existing algorithms by methods that are highly non-deterministic and have high computational cost. In this work we present an alternative method to obtain unification algorithms for combined theories based on variant narrowing. Although variant narrowing is less efficient at the level of a single theory E i, it does not use any costly combination method. Furthermore, it does not require that each E i has a dedicated unification algorithm in a tool implementation. We illustrate the use of this method in the Maude-NPA tool by means of a well-known protocol requiring the combination of three distinct equational theories. © 2011 Springer-Verlag., R. Sasse and J. Meseguer have been partially supported by NSF Grants CNS0716638, CNS-0831064 and CNS-0904749. S. Escobar has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN under grant TIN 2007-68093- C02-02. C. Meadows has been partially supported by NSF Grant CNS-0904749
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Folding variant narrowing and optimal variant termination

  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sasse, Ralf
  • Meseguer, José
Automated reasoning modulo an equational theory E is a fundamental technique in many applications. If E can be split as a disjoint union E u Ax in such a way that E is confluent, terminating, sort-decreasing, and coherent modulo a set of equational axioms Ax, narrowing with E modulo Ax provides a complete E-unification algorithm. However, except for the hopelessly inefficient case of full narrowing, little seems to be known about effective narrowing strategies in the general modulo case beyond the quite depressing observation that basic narrowing is incomplete modulo AC. Narrowing with equations E modulo axioms Ax can be turned into a practical automated reasoning technique by systematically exploiting the notion of E, Ax-variants of a term. After reviewing such a notion, originally proposed by Comon-Lundh and Delaune, and giving various necessary and/or sufficient conditions for it, we explain how narrowing strategies can be used to obtain narrowing algorithms modulo axioms that are: (i) variant-complete (generate a complete set of variants for any input term), (ii) minimal (such a set does not have redundant variants), and (iii) are optimally variant-terminating (the strategy will terminate for an input term t iff t has a finite complete set of variants). We define a strategy called folding variant narrowing that satisfies above properties (i)-(iii); in particular, when E u Ax has the finite variant property, that is, when any term t has a finite complete set of variants, this strategy terminates on any input term and provides a finitary E u Ax-unification algorithm. We also explain how folding variant narrowing has a number of interesting applications in areas such as unification theory, cryptographic protocol verification, and proofs of termination, confluence and coherence of a set of rewrite rules R modulo an equational theory E. © 2012 Elsevier Inc. All rights reserved, S. Escobar has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN under Grant TIN 2010-21062-C02-02, and by Generalitat Valenciana PROMETEO2011/052. R. Sasse and J. Meseguer have been partially supported by NSF Grants CNS 07-16638, CNS 08-31064, CNS 09-04749, and CCF 09-05584.