Navegación

Búsqueda

Búsqueda avanzada

Resultados de búsqueda para Rewriting Logic

First steps towards a specification of Blockchain systems using Maude

This work presents a formal specification of the blockchain algorithm. We specify the consensus algorithm in rewriting logic and Maude. The fact that the specification is executable allows us to simulate and analyze it, with the goal of identifying potential weaknesses and testing new algorithms built on top of the existing infrastructure.

Autores: Francisco Durán / Antonio Moreno-Delgado / 
Palabras Clave: Blockchain - Maude - Rewriting Logic

Towards a Maude-based implementation of MultEcore multilevel modelling languages

MultEcore is a language and tool for the definition of domain-specific modelling languages following the multilevel modelling approach. This work presents some challenges towards the rewriting logic semantics of multilevel model hierarchies and multilevel coupled model transformations used to specify such languages. Although we briefly describe the specification of hierarchies and transformations, we will focus on the latest additions to the language, which allow the instantiation of the multilevel models with a language of choice, e.g., OCL or SML, for the specification and manipulation of values of objects’ attributes, and the use of nested and cross-level boxes for the specification of patterns in the rules. The executable specification can then be used for the simulation/execution of MultEcore models and their analysis using Maude formal tools.

Autores: Francisco Durán / Alejandro Rodríguez / 
Palabras Clave: Maude - MultEcore - multilevel modeling - Rewriting Logic

Verification of ROS Navigation using Maude

The Robot Operating System (ROS) is a framework for building robust software for complex robot systems in several domains. The emph{Navigation Stack} stands out among the different libraries available in ROS. This library provides a set of reusable components that developers can use to build robots with autonomous navigation capabilities. This is a critical component, as navigation failures could have catastrophical consequences for applications like self-driving cars.Here we show our work on the verification of the C++ code for the navfn planner, which is the main planner component of the Navigation Stack. We have ported the planner to a Maude specification, and validated their equivalence using differential testing techniques. For this purpose, we integrated the specification into ROS using a novel high performance Python interface for Maude. We then analyzed the Maude specification by means of model checking and functional verification techniques, using not only the built-in tools of Maude, but also a translation into Dafny, and a manual but systematic generation of verification conditions from the Maude specification. Along the way we also encountered counterexamples for some soundness properties —e.g. that paths should not collide with obstacles— and optimatility —paths should have the lowest possible cost— of the NavFn planner.

Autores: Enrique Martin-Martin / Manuel Montenegro / Adrián Riesco / Juan Rodríguez-Hortalá / Rubén Rubio / 
Palabras Clave: Dafny - Formal Verification - Maude - Model checking - Navigation - Rewriting Logic - ROS

Model-checking strategy-controlled rewriting systems

Strategies are a widespread but ambiguous concept in Computer Science. In the domain of reduction and rewriting systems, strategies are studied as recipes to restrict and control reduction steps and rule applications, which are intimately local, in a derivation-global sense. This idea has been exploited by various tools and rewriting-based specification languages where strategies are an additional specification layer. Systems so described need to be analyzed too. This article discusses model checking of systems controlled by strategies and presents a working strategy-aware model checker built on top of the Maude specification language, based on rewriting logic, and its strategy language.Pendiente de publicación en «International Conference on Formal Structures for Computation and Deduction» (FSCD) 2019. Se envía la versión aceptada. La versión definitiva estará lista a finales de abril.

Autores: Rubén Rubio / Narciso Marti-Oliet / Isabel Pita / Alberto Verdejo / 
Palabras Clave: Maude - Model checking - Rewriting Logic - strategies

Formal verification of the YubiKey and YubiHSM APIs in Maude-NPA

We perform an automated analysis of two devices developed by Yubico: YubiKey, designed to authenticate a user to network-based services, and YubiHSM, Yubico’s hardware security module. Both are analyzed using the Maude-NPA cryptographic protocol analyzer. Although previous work has been done applying formal tools to these devices, there has not been any completely automated analysis. This is not surprising, because both YubiKey and YubiHSM, which make use of cryptographic APIs, involve a number of complex features: (i) discrete time in the form of Lamport clocks, (ii) a mutable memory for storing previously seen keys or nonces, (iii) event-based properties that require an analysis of sequences of actions, and (iv) reasoning modulo exclusive-or. Maude-NPA has provided support for exclusive-or for years but has not provided support for the other three features, which we show can also be supported by using constraints on natural numbers, protocol composition and reasoning modulo associativity. In this work, we have been able to automatically prove security properties of YubiKey and find the known attacks on the YubiHSM, in both cases beyond the capabilities of previous work using the Tamarin Prover due to the need of auxiliary user-defined lemmas and limited support for exclusive-or. Tamarin has recently been endowed with exclusive-or and we have rewritten the original specification of YubiHSM in Tamarin to use exclusive-or, confirming that both attacks on YubiHSM can be carried out by this recent version of Tamarin.

Autores: Antonio Gonzalez-Burgueño / Damian Aparicio / Santiago Escobar / Catherine Meadows / Jose Meseguer / 
Palabras Clave: equational unification - narrowing - protocol analysis - Rewriting Logic - security

Associative Unification and Symbolic Reasoning Modulo Associativity in Maude

We have added support for associative unification to Maude 2.7.1. Associative unification is infinitary, i.e., there are unifica- tion problems u =? v such that there is an infinite minimal set of unifiers, whereas associative-commutative unification is finitary. A unique feature of the associative unification algorithm implemented in Maude is that it is guaranteed to terminate with a finite and complete set of associative unifiers for a fairly large class of unification problems occurring in prac- tice. For any problems outside this class, the algorithm returns a finite set of unifiers together with a warning that such set may be incom- plete. This paper describes this associative unification algorithm imple- mented in Maude and also how other symbolic reasoning Maude features such as (i) variant generation; (ii) variant unification; and (iii) narrow- ing based symbolic reachability analysis have been extended to deal with associativity.

Autores: Francisco Durán / Steven Eker / Santiago Escobar / Narciso Marti-Oliet / Jose Meseguer / Carolyn Talcott / 
Palabras Clave: associativity - narrowing - Rewriting Logic - unification

Partial Evaluation of Order-sorted Equational Programs modulo Axioms (Trabajo de alto nivel)

Partial evaluation (PE) is a powerful and general program optimization
technique with many successful applications. However, it has never been investigated
in the context of expressive rule-based languages like Maude, CafeOBJ,
OBJ, ASF+SDF, and ELAN, which support: rich type structures with sorts, subsorts
and overloading; and equational rewriting modulo axioms such as commutativity,
associativity–commutativity, and associativity–commutativity–identity. In
this paper, we illustrate the key concepts by showing how they apply to partial
evaluation of expressive rule-based programs written in Maude. Our partial evaluation
scheme is based on an automatic unfolding algorithm that computes term
variants and relies on equational least general generalization for ensuring global
termination. We demonstrate the use of the resulting partial evaluator for program
optimization on several examples where it shows significant speed-ups.

Autores: María Alpuente / Angel Cuenca-Ortega / Santiago Escobar / José Meseguer / 
Palabras Clave: Equational Rewriting modulo Axioms - Maude - Partial Evaluation - Rewriting Logic

No encuentra los resultados que busca? Prueba nuestra Búsqueda avanzada