Quantifier Elimination over Algebraically Closed Fields in a Proof Assistant using a Computer Algebra System

We propose a decision procedure for algebraically closed fields based on a quantifier elimination method. The procedure is intended to build proofs for systems of polynomial equations and inequations. We describe how this procedure can be carried out in a proof assistant using a Computer Algebra system in a purely skeptical way. We present an implementation in the particular framework of Coq and Maple giving some details regarding the interface between the two tools. This allows us to show that a Computer Algebra system can be used not only to bring additional computational power to a proof assistant but also to enhance the automation of such tools.     

Exogenous Probabilistic Computation Tree Logic

We define a logic EpCTL for reasoning about the evolution of probabilistic systems. System states correspond to probability distributions over classical states and the system evolution is modelled by probabilistic Kripke structures that capture both stochastic and non–deterministic transitions. The proposed logic is a temporal enrichment of Exogenous Probabilistic Propositional Logic (EPPL). The model-checking problem for EpCTL is analysed and the logic is compared with PCTL; the semantics of the former is defined in terms of probability distributions over sets of propositional symbols, whereas the latter is designed for reasoning about distributions over paths of possible behaviour. The intended application of the logic is as a specification formalism for properties of communication protocols, and security protocols in particular; to demonstrate this, we specify relevant security properties for a classical contract signing protocol and for the so–called quantum one–time pad.     

Practical Reflection for Sequent Logics

It is well-known that adding reflective reasoning can tremendously increase the power of a proof assistant. In order for this theoretical increase of power to become accessible to users in practice, the proof assistant needs to provide a great deal of infrastructure to support reflective reasoning. In this paper we explore the problem of creating a practical implementation of such a support layer.Our implementation takes a specification of a logical theory (which is identical to how it would be specified if we were simply going to reason within this logical theory, instead of reflecting it) and automatically generates the necessary definitions, lemmas, and proofs that are needed to enable the reflected meta-reasoning in the provided theory.One of the key features of our approach is that the structure of a logic is preserved when it is reflected. In particular, all variables, including meta-variables, are preserved in the reflected representation. This also allows the preservation of proof automation—there is a structure-preserving one-to-one map from proof steps in the original logic to proof step in the reflected logic.To enable reasoning about terms with sequent context variables, we develop a principle for context induction, called teleportation.This work is fully implemented in the MetaPRL theorem prover.     

Virtual Organizations in Arigatoni

Arigatoni is a lightweight overlay network that deploys the Global Computing Paradigm over the Internet. Communication for over the behavioral units of the overlay is performed by a simple resource discovery protocol (RDP). Basic Global Computers Units (GC) can communicate by first registering to a brokering service and then by mutually asking and offering services.Colonies and communities are the main entities in the model. A colony is a simple virtual organization composed by exactly one leader and some set (possibly empty) of individuals. A community is a raw set of colonies and global computers (think it as a soup of colonies and global computer without a leader).We present an operational semantics via a labeled transition system, that describes the main operations necessary in the Arigatoni model to perform leader negotiation, joining/leaving a colony, linking two colonies and moving one GC from one colony to another. Our formalization results to be adequate w.r.t. the algorithm performing peer logging/delogging and colony aggregation.     

Deadlock and starvation free reentrant readers-writers: A case study combining model checking with theorem proving

The classic readers-writers problem has been extensively studied. This holds to a lesser degree for the reentrant version, where it is allowed to nest locking actions. Such nesting is useful when a library is created with various procedures each starting and ending with a lock operation. Allowing nesting makes it possible for these procedures to call each other.We considered an existing widely used industrial implementation of the reentrant readers-writers problem. Staying close to the original code, we modelled and analyzed it using a model checker resulting in the detection of a serious error: a possible deadlock situation. The model was improved and checked satisfactorily for a fixed number of processes. To achieve a correctness result for an arbitrary number of processes the model was converted to a specification that was proven with a theorem prover. Furthermore, we studied starvation. Using model checking we found a starvation problem. We have fixed the problem and checked the solution. Combining model checking with theorem proving appeared to be very effective in reducing the time of the verification process.     

ReSpecT Nets: Towards an Analysis Methodology for ReSpecT Specifications

A key feature for infrastructures providing coordination services is the ability to define the behaviour of coordination abstractions according to the requirements identified at design-time. We take as a representative for this scenario the logic-based language ReSpecT (Reaction Specification Tuples), used to program the reactive behaviour of tuple centres. ReSpecT specifications are at the core of the engineering methodology underlying the TuCSoN infrastructure, and are therefore the “conceptual place” where formal methods can be fruitfully applied to guarantee relevant system properties.In this paper we introduce ReSpecT nets, a formalism that can be used to describe reactive behaviours that can succeed and fail, and that allows for an encoding to Petri nets with inhibitor arcs. ReSpecT nets are introduced to give a core model to a fragment of the ReSpecT language, and to pave the way for devising an analysis methodology including formal verification of safety and liveness properties. In particular, we provide a semantics to ReSpecT specifications through a mapping to ReSpecT nets. The potential of this approach for the analysis of ReSpecT specifications is discussed, presenting initial results for the analysis of safety properties.     

PMaude: Rewrite-based Specification Language for Probabilistic Object Systems

We introduce a rewrite-based specification language for modelling probabilistic concurrent and distributed systems. The language, based on PMaude, has both a rigorous formal basis and the characteristics of a high-level rule-based programming language. Furthermore, we provide tool support for performing discrete-event simulations of models written in PMaude, and for statistically analyzing various quantitative aspects of such models based on the samples that are generated through discrete-event simulation. Because distributed and concurrent communication protocols can be modelled using actors (concurrent objects with asynchronous message passing), we provide an actor PMaude module. The module aids writing specifications in a probabilistic actor formalism. This allows us to easily write specifications that are purely probabilistic – and not just non-deterministic. The absence of such (un-quantified) non-determinism in a probabilistic system is necessary for a form of statistical analysis that we also discuss. Specifically, we introduce a query language called Quantitative Temporal Expressions (or QuaTEx in short), to query various quantitative aspects of a probabilistic model. We also describe a statistical technique to evaluate QuaTEx expressions for a probabilistic model.     

Security analysis of the SCO-family using key schedules

The COS-based ciphers SCO-1, SCO-2 and SCO-3 (called the SCO-family) have been designed to improve the security of DDP-based ciphers which are all broken by related-key attacks. In this paper we show that the SCO-family is still vulnerable to related-key attacks: we present related-key differential attacks on a full-round SCO-1, a full-round SCO-2 and an 11-round reduced SCO-3, respectively. The attack on SCO-1 requires 2⁶¹ related-key chosen ciphertexts and 2^120.59 full-round SCO-1 decryptions. For the attack on SCO-2, we require 2⁵⁹ related-key chosen plaintexts and 2^118.42 full-round SCO-2 encryptions, and the 11-round attack on SCO-3 works with 2⁵⁸ related-key chosen plaintexts and 2^117.54 11-round SCO-3 encryptions. This work is the first known cryptanalytic results on the SCO-family.     

Multidimensional analogs of the kendall equation for priority queueing systems: computational aspects

An analogy between celebrated Kendall equation for busy periods in the system M|GI|1 and analytical results for busy periods in the priority systemsM _r |GI _r |1 is drawn. These results can be viewed as generalizations of the functional Kendall equation. The methodology and algorithms of numerical solution of recurrent functional equations which appear in the analysis of such queueing systems are developed. The efficiency of the algorithms is achieved by acceleration of the numerical procedure of solving the classical Kendall equation. An algorithm of calculation of the system workload coefficient calculation is given.     

On-the-fly Workload Prediction and Redistribution in the Distributed Timed Model Checker Zeus

In this work we present the on-the-fly workload prediction and redistribution techniques used in Zeus [Braberman, V., A. Olivero and F. Schapachnik, Zeus: A distributed timed model checker based on kronos, in: Workshop on Parallel and Distributed Model Checking, affiliated to CONCUR 2002 (13^th International Conference on Concurrency Theory), ENTCS 68 (2002), Braberman, V., A. Olivero and F. Schapachnik, Issues in Distributed Model-Checking of Timed Automata: building zeus, to appear in International Journal of Software Tools for Technology Transfer (2004)], a Distributed Model Checker that evolves from the tool Kronos [Daws, C., A. Olivero, S. Tripakis and S. Yovine, The Tool KRONOS, in: Proceedings of Hybrid Systems III, LNCS 1066 (1996), pp. 208–219].After reviewing why it is so hard to have good speedups in distributed timed model checking, we present the methods used to get promising results when verifying reachability properties over timed automata [Alur, R. and D. L. Dill, A theory of timed automata, Theoretical Computer Science 126 (1994) 183–235].     

Nonlinear parity relations: A logic-dynamic approach

Consideration was given to construction of the parity relations for systems described by the nonlinear dynamic models. To solve this problem, a logic-dynamic approach was proposed, and the realizability conditions providing insensitivity to the perturbing actions were given for it.     

Supervised ranking in the weka environment

Software for solving the supervised ranking problem is presented. Four variants of the Ordinal Stochastic Dominance Learner (OSDL) are given, together with the space and time complexity of their implementations. It is shown that the described software, which includes two further algorithms for supervised ranking, fits seamlessly into the weka environment.     

Suppression of bounded exogenous disturbances: Output feedback

The paper was devoted to rejection of bounded exogenous disturbances and considered design of the static output feedback minimizing the invariant ellipsoids of the dynamic system. The problems of control analysis and design come to the equivalent conditions in the form of linear matrix inequalities and to the problem of semidefinite programming. The state estimate obtained using the Luenberger observer was used at that.     

Gaining insight through case-based explanation

Traditional explanation strategies in machine learning have been dominated by rule and decision tree based approaches. Case-based explanations represent an alternative approach which has inherent advantages in terms of transparency and user acceptability. Case-based explanations are based on a strategy of presenting similar past examples in support of and as justification for recommendations made. The traditional approach to such explanations, of simply supplying the nearest neighbour as an explanation, has been found to have shortcomings. Cases should be selected based on their utility in forming useful explanations. However, the relevance of the explanation case may not be clear to the end user as it is retrieved using domain knowledge which they themselves may not have. In this paper the focus is on a knowledge-light approach to case-based explanations that works by selecting cases based on explanation utility and offering insights into the effects of feature-value differences. In this paper we examine to two such a knowledge-light frameworks for case-based explanation. We look at explanation oriented retrieval (EOR) a strategy which explicitly models explanation utility and also at the knowledge-light explanation framework (KLEF) that uses local logistic regression to support case-based explanation.

Quasi-invariant control: Design and functional capabilities

The questions of physical realizability, stability, and control errors were considered by the example of a simplest mathematical model of the linear minimum phase system of quasi-invariant control. The problem of designing the quasi-invariant control was solved on this basis, thus providing the opportunity to extend control by designing a nonlinear system combining the quasi-invariant and classical control strategies.     

Robust filtering under nonrandom disturbances: The invariant ellipsoid approach

We present a simple and universal observer-based approach to solving the problem of robust filtering of unknown-but-bounded exogenous disturbances. The heart of this approach is the method of invariant ellipsoids. Application of this technique allows for a reformulation of the original problem in terms of linear matrix inequalities with reduction to semidefinite programming and one-dimensional optimization, which are easy to solve numerically. Continuous-time and discrete-time cases are studied in equal detail. The efficacy of the approach is demonstrated via the double pendulum example.     

Direct links in IEEE 802.11: Analytical study of unfairness problem

In this paper, the problem of mutual interference between direct links in IEEE 802.11 networks is represented. This problem is common for direct links in infrastructure networks with hidden terminals and for mesh networks as well. In this paper, we develop analytical models to study the impact of the direct link interference on links performance indices in various cases of links disposition. With these models proved by simulation, we show that network capacity distribution between direct links is unfair in many cases, explaining the reasons of the unfairness in every case. As a conclusion, we discuss possible mechanisms to solve the unfairness problem.     

Estimating the attraction domain of the invariant set in the problem of wheeled robot control

Consideration was given to the problem of controlling the planar motion of a wheeled robot with the driving rear wheels and forewheels intended for chassis rotation. The aim of control is to drive the goal point to the prescribed trajectory and stabilize the motion along it. The trajectory consists of segments of straight lines and circles. The forewheel rotation mechanism has inertiality due to its dynamic characteristics. Disregard for the dynamic properties of the forewheel drive at designing the control law leads in the course of motion to transients in the closed-loop system at passing from one trajectory segment to another. It was assumed that the drive dynamics obeys a first-order differential equation whose right-hand side satisfies the “sector condition.” To estimate these transients, in the system state space an invariant set is defined and estimated together with the estimate of the attraction domain.     

Application of the finite difference method to the problem of pursuit in the distributed-parameter systems

The problem of pursuit in the controlled systems of parabolic type without mixed derivatives with variable coefficients was considered and solved using the finite difference method. Sufficient conditions for pursuit completion were established.