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.     

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].     

Type inference and strong static type checking for Promela

The Spin model checker and its specification language Promela have been used extensively in industry and academia to check the logical properties of distributed algorithms and protocols. Model checking with Spin involves reasoning about a system via an abstract Promela specification, thus the technique depends critically on the soundness of this specification. Promela includes a rich set of data types including first-class channels, but the language syntax restricts the declaration of channel types so that it is not generally possible to deduce the complete type of a channel directly from its declaration. We present the design and implementation of Etch, an enhanced type checker for Promela, which uses constraint-based type inference to perform strong type checking of Promela specifications, allowing static detection of errors that Spin would not detect until simulation/verification time, or that Spin may miss completely. We discuss theoretical and practical problems associated with designing a type system and type checker for an existing language, and formalise our approach using a Promela-like calculus. To handle subtyping between base types, we present an extension to a standard unification algorithm to solve a system of equality and subtyping constraints, based on bounded substitutions.     

Concurrent Java Test Generation as a Search Problem

A Random test generator generates executable tests together with their expected results. In the form of a noise-maker, it seeds the program with conditional scheduling primitives (such as yield()) that may cause context switches. As a result different interleavings are potentially produced in different executions of the program. Determining a-priori the set of seeded locations required for a bug to manifest itself is rarely possible.This work proposes to reformulate random test generation of concurrent Java programs as a search problem. Hence, it allows applying a set of well known search techniques from the domain of AI to the input space of the test generator. By iteratively refining the input parameters fed to the test generator, the search process creates testing scenarios (i.e. interleavings) that maximizes predefined objective functions. We develop geneticFinder, a noise-maker that uses a genetic algorithm as a search method. We demonstrate our approach by maximizing two objective functions: the high manifestation rate of concurrent bugs and the exporting of a high degree of debugging information to the user. Experimental results show our approach is effective.     

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.     

Verification of Random Graph Transformation Systems

In this paper we describe some statistical results obtained by the verification of random graph transformation systems (GTSs). As a verification technique we use over-approximation of GTSs by Petri nets. Properties we want to verify are given by markings of Petri nets. We also use counterexample-guided abstraction refinement approach to refine the obtained approximation. A software tool (Augur) supports the verification procedure. The idea of the paper is to see how many of the generated systems can be successfully verified using this technique.     

Frequency characteristics of the one-layer anisotropic magnetoresistive sensitive nanoelements

The high-frequency characteristics of the one-layer anisotropic magnetoresistive strip—the magnetosensitive nanoelement of the magnetic field sensor—were analyzed on the basis of the Landau-Livshits-Hilbert equation. The results of this study were shown to coincide completely with the linear microwave theory. The strip frequency characteristics were analyzed for low-anisotropy and high-anisotropy FeNiCo ferromagnetic films of various thickness, strip width, easy magnetization direction, and fixed external magnetic field.     

Probabilistic characteristics of the nonlinear dynamic parabolic system with random coefficients

A method to calculate the probabilistic characteristics of a nonlinear stochastic dynamic system by approximation of the solution of nonlinear stochastic system of parabolic equations by a segment of a uniformly converging generalized Kotel’nikov series was presented. It is applicable to any probability distributions of the random coefficients of equations for which expectations exist and provides precise solutions while considering a smaller number of the interpolation nodes as compared with the existing methods.     

Bytecode Rewriting in Tom

In this paper, we present a term rewriting based library for manipulating Java bytecode. We define a mapping from bytecode programs to algebraic terms, and we use Tom, an extension of Java that adds pattern-matching facilities, to describe transformations. An originality of Tom is that it provides a powerful strategy language to express traversals over trees and to control how transformation rules are applied. To be even more expressive, we use CTL formulae as conditions and we show how their satisfiability can be ensured using the strategy formalism. Through small examples, we show how bytecode analysis and transformations can be defined in an elegant way. In particular, we outline the implementation of a ClassLoader parameterized by a security policy that restricts file access.     

Design of a magnetostrictive (MS) actuator

Several advanced technologies are introduced in automotive applications. Higher energy density and dynamic performance are demanding new and cost-effective actuator structures. Magnetostriction (MS), change in shape of materials under the influence of an external magnetic field, is one of the advanced technologies. Good understanding of specific design constrains is required to define and optimize a magnetostrictive actuator. This paper presents parametrical analysis with magnetic simulation of a magnetostrictive actuator. Proposed actuator has been designed, and the performance has been evaluated on experimental rig. Strain, elongation of the shaft, of 1000 ppm at 10 A and a blocked force over 4500 N has been achieved with shaft of 8 mm diameter, made of Terfenol-D. Furthermore, the effect of pre-stress of the Terfenol-D shaft has been evaluated experimentally. The study shows that excellent features can be obtained by magnetostrictive materials for many advanced applications.     

Enantioselective, potentiometric membrane electrodes based on cyclodextrins for the determination of l-histidine

Four enantioselective, potentiometric membrane electrodes based on carbon paste impregnated with α-, β-, 2-hydroxyl-3-trimethylammoniopropyl-β-(as chloride salt) and γ-cyclodextrins (γ-CDs) are proposed for the assay of l-histidine (l-his). The proposed electrodes showed near-Nernstian response over l-his but not over d-histidine (d-his). The recovery of l-his in the presence of d-his was higher than 99.10% with R.S.D. lower than 0.1%. The surfaces of the electrodes are easily renewable by simply polishing on an alumina paper.     

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.     

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.

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.     

单播丢包率的时域特征参数估计

网络链路丢包的时域特征参数（如：平均丢包长度、平均传输长度等）能够表现出链路丢包的突发性。现有的针对多播网络链路丢包时域特征参数的估计方法不能直接应用于单播网络。针对这一问题,提出用探测包群在单播网络中模拟多播端到端的测量过程,然后根据测量得到的数据对链路的连续传输概率（连续传输两个包的概率）和平均丢包长度等进行了估计。采用NS2进行仿真,验证了方法的性能。     

Inverse NP Problems

The inverse problem relative to a verifier V of proofs of membership for a NP language is the problem of deciding, given a set π of proofs, whether or not there exists a string x having exactly π as its set of proofs. In this paper, we study the complexity of inverse problems. We develop a new notion of reduction which allows one to compare the complexity of inverse problems. Using this notion, we classify as coNP-complete the inverse problems for the “natural” verifiers of many NP-complete problems. We also show that the inverse complexity of a verifier for a language L cannot be predicted solely from the complexity of L, but rather, is highly dependent upon the choice of verifier used to accept L. In this context, a verifier with a Σ₂ ^p -complete inverse problem is exhibited, giving a new and natural example of a Σ₂ ^p -complete problem.