Search

Context: In the past decade, the World Wide Web has been subject to rapid changes. Web sites have evolved from static information pages to dynamic and service-oriented applications that are used for a broad range of activities on a daily basis. For this reason, thorough analysis and verification of Web Applications help assure the deployment of high quality applications. Objectives: In this paper, an approach is presented to the formal verification and validation of existing web applications. The approach consists of using execution traces of a web application to automatically generate a communicating automata model. The obtained model is used to model checking the application against predefined properties, to perform regression testing, and for documentation. Methods: Traces used in the proposed approach are collected by monitoring a web application while it is explored by a user or a program. An automata-based model is derived from the collected traces by mapping the pages of the application under test into states and the links and forms used to browse the application into transitions between the states. Properties, meanwhile, express correctness and quality requirements on web applications and might concern all states of the model; in many cases, these properties concern only a proper subset of the states, in which case the model is refined to designate the subset of the global states of interest. A related problem of property specification in Linear Temporal Logic (LTL) over only a subset of states of a system is solved by means of specialized operators that facilitate specifying properties over propositional scopes in a concise and intuitive way. Each scope constitutes a subset of states that satisfy a propositional logic formula. Results: An implementation of the verification approach that uses the model checker Spin is presented where an integrated toolset is developed and empirical results are shown. Also, Linear Temporal Logic is extended with propositional scopes. Conclusion: a formal approach is developed to build a finite automata model tuned to features of web applications that have to be validated, while delegating the task of property verification to an existing model checker. Also, the problem of property specification in LTL over a subset of the states of a given system is addressed, and a generic and practical solution is proposed which does not require any changes in the system model by defining specialized operators in LTL using scopes.

A formal framework for the analysis of execution traces collected from distributed systems at run-time is presented. We introduce the notions of event and message traces to capture the consistency of causal dependencies between the elements of a trace. We formulate an approach to property testing where a partially ordered execution trace is modeled by a collection of communicating automata. We prove that the model exactly characterizes the causality relation between the events/messages in the observed trace and discuss the implementation of this approach in SDL, where ObjectGEODE is used to verify properties using model-checking techniques. Finally, we illustrate the approach with industrial case studies.

Formal verification is not always applicable to large industrial software systems due to scalability issues and difficulties in formal model and requirements specification. The scalability and model derivation problems could be alleviated by runtime trace analysis, which combines both testing and formal verification. We implement and compare an ad-hoc custom approach and a formal approach to detect common bug patterns in multithreaded Java software. We use the tracing platform of the Eclipse IDE and state-of-the-art model checker Spin.

We investigate the problem of configuration verification for the extended FSM (EFSM) model. This is an extension of the FSM state identification problem. Specifically, given a configuration ("state vector") and an arbitrary set of configurations, determine an input sequence such that the EFSM in the given configuration produces an output sequence different from that of the configurations in the given set or at least in a maximal proper subset. Such a sequence can be used in a test case to confirm the destination configuration of a particular EFSM transition. We demonstrate that this problem could be reduced to the EFSM traversal problem, so that the existing methods and tools developed in the context of model checking become applicable. We introduce notions of EFSM projections and products and, based on these notions, we develop a theoretical framework for determining configuration-confirming sequences. The proposed approach is illustrated on a realistic example.

We report on a tool for generating executable concurrent tests from scenarios specified as message sequence charts. The proposed approach features three steps: 1) Deriving a MSC test implementation from a MSC scenario, 2) Mapping the test implementation into a Promela model, 3) Generating executable test scripts in Java. The generation of an intermediate Promela model allows for model-checking to inspect the test implementation for properties like soundness, fault detection power as well as for consistency checking between different test scenarios. Moreover decoupling the executable test scripts from the scenario specification makes it possible to use different backend code generators to support other scripting languages when needed.

International audience; Test case prioritisation aims at finding an ordering which enhances a certain property of an ordered test suite. Traditional techniques rely on the availability of code or a specification of the program under test. In this paper, we propose to use string distances on the text of test cases for their comparison and elaborate a prioritisation algorithm. Such a prioritisation does not require code and can be useful for initial testing and in cases when code is difficult to instrument. We also briefly report on preliminary results of an experiment where the proposed prioritisation technique was compared with random permutations and four classical string distance metrics were evaluated.

Given a test scenario as a Message Sequence Chart (MSC), a method for implementing an MSC test in a distributed asynchronous environment is suggested. Appropriate test coordination is achieved using coordinating messages and observed quiescence of a system under test. A formal definition and a classification of faults with respect to the test scenario are introduced. It is shown that the use of quiescence observation improves the fault detection and allows implementing sound tests for a wider class of test scenarios than before.

This chapter addresses the problem of Web application quality assessment from two perspectives. First, it shows the use of model checking of properties formulated in LTL to detect anomalies in Web applications. Anomalies can be derived from standard quality principles or defined for a specific organization or application. The detection is performed on communicating automata models inferred from execution traces. Second, the chapter explains how probabilistic models (Bayesian networks) can be built and used to evaluate quality characteristics. The structure of the networks is defined by refinement of existing models, where the parameters (probabilities and probability tables) are set using expert judgment and fuzzy clustering of empirical data. The two proposed approaches are evaluated and a discussion on how they complement each other is presented.

We present a framework for property testing where a partially ordered execution trace of a distributed system is modeled by a collection of communicating automata. We prove that the model exactly characterizes the causality relation between the events in the observed trace. We present the implementation of this approach in SDL, where ObjectGEODE is used to verify properties, and illustrate the approach with an industrial case study.

ing the behaviour of a specification is a key technique for dealing with the complexity of such tasks as reachability analysis and test generation. We adapted classical data-flow analysis techniques to abstract variables in SDL processes and addressed the problem of finding conservative state abstractions. Prototype tools have been developed to implement those techniques and applied to simple applications from the field of telecommunications.

We discuss how specification coverage and fault coverage based test derivation strategies can be combined. In particular, the problem of deriving a test suffix, which raises tester confidence in the configuration of the system, reached after a test derived by a specification coverage criterion, is formalized and solved in the CEFSM setting. The traditional mutant-based test derivation approach is extended with nondeterministic mutants to cover more faults. An experimental tool and case study are reported.

In this paper we investigate the problem of configuration distinguishability for the EFSM model, specifically, given a configuration and an arbitrary set of configurations, determine an input sequence such that the EFSM in the given configuration produces an output sequence different from that of the configurations in the given set or at least in a maximal proper subset. Such a sequence can be used in a test case to confirm the destination configuration. We demonstrate that the distinguishability problem could be reduced to the EFSM traversal problem, so that the existing methods and tools developed in the context of model checking become applicable. The theoretical framework for determining configuration-confirming sequences based on projections and products of EFSMs is presented. Our approach can be implemented in a number of heuristic test derivation strategies.