Electronic Communications of the EASST (European Association of Software Science and Technology)
Not a member yet
887 research outputs found
Sort by
Lattice-extended Coloured Petri Net Rewriting for Adaptable User Interface Models
Get PDFAdaptable user interfaces (UI) have shown a great variety of advantages in human computer interaction compared to classic UI designs. We show how adaptable UIs can be built by introducing coloured Petri nets to connect the UI’s physical representation with the system to be controlled. UI development benefits from formal modelling approaches regarding the derived close integration of creation, execution, and reconfiguration of formal UI models. Thus, adaptation does not only change the physical representation, but also the connecting Petri net. For the latter transformation, we enhance the DPO rewriting formalism by using an order on the set of labels and softening the label-preserving property of morphisms, i.e., an element can also be mapped to another element if the label is larger. We use lattices to ensure correctness and state application conditions of rewriting steps. Finally we define an order compatible with our framework for the use in our implementation
Fully Symbolic TCTL Model Checking for Incomplete Timed Systems
Get PDFIn this paper we present a fully symbolic TCTL model checking algorithm for incomplete timed systems. Our algorithm is able to prove that a TCTL property is violated or satisfied regardless of the implementation of unknown timed components in the system. For that purpose the algorithm computes over- approximations of sets of states fulfilling a TCTL property φ for at least one implementation of the unknown components and under-approximations of sets of states fulfilling φ for all possible implementations of the unknown components. The algorithm works on a symbolic model for timed systems, called a finite state machine with time (FSMT), and makes use of fully symbolic state set representations containing both the clock values and the state variables. In order to handle incomplete timed systems our model checking algorithm deals with different communication methods between the system and its unknown components, e.g. shared integer variables and urgent and non-urgent synchronization. Our experimental results demonstrate that it is possible to prove interesting properties at early stages of the design when parts of the overall system may not yet be finished. Additionally, fading out components of a large system may dramatically reduce the complexity of the system and thus the effort for verification
Towards Dynamic Reverse Engineering Visual Contracts from Java
Get PDFVisual contracts provide a concise and intuitive representation of preand postconditions for operations in object-oriented or component-based systems, which can be used for documentation, testing, or simulation. However, defining visual contracts to correctly describe the behaviour of existing classes or components requires a deep understanding of their data model and behaviour.We propose an approach to automatically extract instantiated versions of visual contracts, or contract instances, by observing the changes an operation performs on the objects in a system. We describe and evaluate the approach and tool to extract contract instances using the case study of Java-based DOM implementation NanoXML
On the Satisfiability of Metric Temporal Logics over the Reals
Get PDFWe show that there is a satisfiability-preserving translation of QTL formulae interpreted over finitely variable behaviors into formulae of the CLTL-overclocks logic. The satisfiability of CLTL-over-clocks can be determined through a suitable encoding into the input logics of SMT solvers, so it constitutes an effective decision procedure for QTL. Although decision procedures for determining satisfiability of QTL (and for the expressively equivalent logics MITL and QMLO) already exist, the automata-based techniques they employ appear to be very difficult to realize in practice, and, to the best of our knowledge, no implementation currently exists for them. A prototype tool for QTL based on the encoding presented here has, instead, been implemented and is publicly available
A Constraint-Solving Approach for Achieving Minimal-Reset Transition Coverage of Smartcard Behaviour
Get PDFSmartcards are security critical devices requiring a high assurance verification approach. Although formal techniques can be used at design or even at development stages, such systems have to undergo a traditional hardware-in-the-loop testing phase. This phase is subject to two key requirements: achieving exhaustive transition coverage of the behavior of the system under test, and minimizing the testing time. In this context, testing time is highly bound to a specific hardware reset operation. Model-based testing is the adequate approach given the availability of a precise model of the system behavior and its ability to produce high quality coverage while optimizing some cost criterion. %l'argument n'est pas convainquant.This paper presents an original algorithm addressing this problem by reformulating it as an integer programming problem to make a graph Eulerian. The associated cost criterion captures both the number of resets and the total length of the test suite, as an auxiliary objective. The algorithm ensures transition coverage. An implementation of the algorithm was developed, benchmarked, and integrated into an industrial smartcard testing framework. A validation case study from this domain is also presented. The approach can of course be applied to any other domains with similar reset-related testing constraints
How We Know the Practical Impact of Clone Analysis
Get PDFIn order to develop and improve clone analysis techniques for industrial application, it is necessary to know about how those techniques provide impacts on clone management in industry. In this position paper, we discuss approaches to observing the practical impact of clone analysis on the basis of our experience in applying clone analysis into an industrial development process
On the Efficiency of Deciding Probabilistic Automata Weak Bisimulation
Get PDFWeak probabilistic bisimulation on probabilistic automata can be decided by an algorithm that needs to check a polynomial number of linear programming problems encoding weak transitions. It is hence polynomial, but not guaranteed to be strongly polynomial. In this paper we show that for polynomial rational proba- bilistic automata strong polynomial complexity can be ensured. We further discuss complexity bounds for generic probabilistic automata. Then we consider several practical algorithms and LP transformations that enable an efficient solution for the concrete weak transition problem. This sets the ground for effective compositional minimisation approaches for probabilistic automata and Markov decision processes
On the Random Structure of Behavioural Transition Systems
Get PDFRandom graphs have the property that they are very predictable. Even by exploring a small part reliable observations are possible regarding their structure and size. An unfortunate observation is that standard models for random graphs, such as the Erdos-Renyi model, do not reflect the structure of the graphs that describe distributed systems and protocols. In this paper we propose to use the parallel composition of such random graphs to model `real' state spaces. We show how we can use this structure to predict the size of state spaces, and we can use it to explain that software bugs are in practice far easier to find than predicted by the standard random graph models. By some practical experiments we show that our new random model is an improvement over the standard model in predicting properties of transition systems representing realistic systems
Studying Late Propagations in Code Clone Evolution Using Software Repository Mining
Get PDFIn the code clone evolution community, the Late Propagation (LP) has been identified as one of the clone evolution patterns that can potentially lead to software defects. An LP occurs when instances of a clone pair are changed consistently, but not at the same time. The clone instance, which receives the update at a later time, might exhibit unintended behavior if the modification was a bugfix. In this paper, we present an approach to extract LPs from software repositories. Subsequently, we study LPs in four software systems, which allows us to investigate the propagation time, the clone dispersion and the effects of LPs on the software
Model Checking C++ with Exceptions
Get PDFWe present an extension of the DIVINE software model checker tosupport programs with exception handling. The extension consists of two parts, a language-neutral implementation of the LLVM exception-handling instructions, and an adaptation of the C++ runtime for the DIVINE/LLVM exception model. This constitutes an important step towards support of both the full C++ specification and towards verification of real-world C++ programs using a software model checker. Additionally, we show how these extensions can be used to elegantly implement other features with non-local control transfer, most importantly the longjmp function in C