Recent Publications

Campos JC, Barbosa LS, Barbosa M.  2009.  A coordination model for interactive components. 3rd International Conference on Fundamentals of Software Engineering - FSEN. Abstractbbc09.pdf

Although presented with a variety of ‘flavours’, the notion of an interactor, as an abstract characterisation of an interactive component, is well-known in the area of formal modelling techniques for interactive systems. This paper replaces traditional, hierarchical, ‘tree-like' composition of interactors in the specification of complex interactive systems, by their exogenous coordination through general-purpose software connectors which assure the flow of data and the meet of synchronisation constraints. The paper’s technical contribution is twofold. First a modal logic is defined to express behavioural properties of both interactors and connectors. The logic is new in the sense that its modalities are indexed by fragments of sets of actions to cater for action co-occurrence. Then, this logic is used in the specification of both interactors and coordination layers which orchestrate their interconnection.

Gibbons J, Oliveira JN.  2009.  Teaching Formal Methods - 2nd International Conference. TFM - Teaching Formal Methods. Abstract

This volume contains the proceedings of TFM2009, the Second International FME Conference on Teaching Formal Methods, organized by the Subgroup of Education of the Formal Methods Europe (FME) association. The conference took place as part of the first Formal Methods Week (FMWeek), held in Eind- hoven, The Netherlands, in November 2009.
TFM 2009 was a one-day forum in which to explore the successes and fail- ures of formal method (FM) education, and to promote cooperative projects to further education and training in FMs. The organizers gathered lecturers, teach- ers, and industrial partners to discuss their experience, present their pedagogical methodologies, and explore best practices.

Nunes A, Marques J, Pereira JO.  2009.  Seeds: The social internet feed caching and dissemination architecture. INForum - Simpósio de Informática. :25. Abstractseeds.pdf

Syndicated content in the Internet has been a huge success ever since the early days of RSS 0.9 and MyNetscape. Currently, it is the cornerstone of content push, ranging from podcasts to emerging Web 2.0 sites such as Friend-Feed and Plexus. Unfortunately, the simple technology that makes publication and subscription very simple and flexible, thus explaining in part its success, is also limiting its usefulness in more demanding applications.
This paper proposes a novel distributed architecture for feed caching and dissemination. It leverages social networks as promoters of discovery and aggregation, and peer-to-peer protocols for content distribution, while providing an evolutionary upgrade path that does not disrupt current infrastructure or require changes to publishers’ or consumers’ habits.

Bonchi F, Bonsangue M, Rutten J, Silva A.  2009.  Deriving Syntax and axioms for quantitative regular behaviours. Proceedings of the 20th International Conference on Concurrency Theory (CONCUR 2009). 5710:146–162. Abstractconcur09.pdf

We present a systematic way to generate (1) languages of (generalised) regular expressions, and (2) sound and complete axiomatizations thereof, for a wide variety of quantitative systems. Our quantitative systems include weighted versions of automata and transition systems, in which transitions are assigned a value in a monoid that represents cost, duration, probability, etc. Such systems are represented as coalgebras and (1) and (2) above are derived in a modular fashion from the underlying (functor) type of these coalgebras.

In previous work, we applied a similar approach to a class of systems (without weights) that generalizes both the results of Kleene (on rational languages and DFA’s) and Milner (on regular behaviours and finite LTS’s), and includes many other systems such as Mealy and Moore machines. In the present paper, we extend this framework to deal with quantitative systems. As a consequence, our results now include languages and axiomatizations, both existing and new ones, for many different kinds of probabilistic systems.

Bonsangue M, Clarke D, Silva A.  2009.  Automata for Context-dependent Connectors. Proceedings of the Eleventh International Conference on Coordination Models and Languages (Coordination 2009). 5521:184–203. Abstractcoord09.pdf

Recent approaches to component-based software engineering employ coordinating connectors to compose components into software systems. For maximum flexibility and reuse, such connectors can themselves be composed, resulting in an expressive calculus of connectors whose semantics encompasses complex combinations of synchronisation, mutual exclusion, non-deterministic choice and state-dependent behaviour. A more expressive notion of connector includes also context-dependent behaviour, namely, whenever the choices the connector can take change non-monotonically as the context, given by the pending activity on its ports, changes. Context dependency can express notions of priority and inhibition. Capturing context-dependent behaviour in formal models is non-trivial, as it is unclear how to propagate context in- formation through composition. In this paper we present an intuitive automata-based formal model of context-dependent connectors, and argue that it is superior to previous attempts at such a model for the coordination language Reo.

Bonsangue M, Rutten J, Silva A.  2009.  A Kleene theorem for polynomial coalgebras. Proceedings of the Twelfth International Conference on Foundations of Software Science and Computation structures (FoSSaCS 2009). 5504:122–136. Abstractbrs09a.pdf

For polynomial functors G, we show how to generalize the classical notion of regular expression to G-coalgebras. We introduce a language of expressions for describing elements of the final G-coalgebra and, analogously to Kleene’s theorem, we show the correspondence between expressions and finite G-coalgebras.

Abreu R, Zoeteweij P, Van Gemund AJC.  2009.  Spectrum-based multiple fault localization. 24th IEEE/ACM International Conference on Automated Software Engineering - ASE. :88–99. Abstractase09-1.pdf

Fault diagnosis approaches can generally be categorized into spectrum-based fault localization (SFL, correlating failures with abstractions of program traces), and model-based diagnosis (MBD, logic reasoning over a behavioral model). Although MBD approaches are inherently more accurate than SFL, their high computational complexity prohibits application to large programs. We present a framework to combine the best of both worlds, coined BARINEL. The program is modeled using abstractions of program traces (as in SFL) while Bayesian reasoning is used to deduce multiple-fault candidates and their probabilities (as in MBD). A particular feature of BARINEL is the usage of a probabilistic component model that accounts for the fact that faulty components may fail intermittently. Experimental results on both synthetic and real software programs show that BARINEL typically outperforms current SFL approaches at a cost complexity that is only marginally higher. In the context of single faults this superiority is established by formal proof.

Janssen T, Abreu R, Van Gemund AJC.  2009.  Zoltar: A toolset for automatic fault localization. Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering. :662–664. Abstractase09-2.pdf

Locating software components which are responsible for observed failures is the most expensive, error-prone phase in the software development life cycle. Automated diagnosis of software faults can improve the efficiency of the debugging process, and is therefore an important process for the development of dependable software. In this paper we present a toolset for automatic fault localization, dubbed Zoltar, which hosts a range of spectrum-based fault localization techniques featuring BARINEL, our latest algorithm. The toolset provides the infrastructure to automatically instrument the source code of software programs to produce runtime data, which is subsequently analyzed to return a ranked list of diagnosis candidates. Aimed at total automation (e.g., for runtime fault diagnosis), Zoltar has the capability of instrumenting the program under analysis with fault screeners as a run-time replacement for design-time test oracles.

Abreu R, Zoeteweij P, Van Gemund AJC.  2009.  A new bayesian approach to multiple intermittent fault diagnosis. Proceedings of the 21st international jont conference on Artifical intelligence. :653–658. Abstractijcai09-114.pdf

Logic reasoning approaches to fault diagnosis account for the fact that a component cjmay fail intermittently by introducing a parameter gj that ex presses the probability the component exhibits correct behavior. This component parameter gj, in conjunction with a priori fault probability, is used in a Bayesian framework to compute the posterior fault candidate probabilities. Usually, information ongjis not known a priori. While proper estimation of gjcan have a great impact on the diagnostic accuracy, at present, only approximations have been proposed. We present a novel framework, BARINEL, that computes exact estimations of gjas integral part of the posterior candidate probability computation. BARINEL’s diagnostic performance is evaluated for both synthetic and real software systems. Our results show that our approach is superior to approaches based on classical persistent fault models as well as previously proposed intermittent fault models.

Janssen T, Abreu R, Van Gemund AJC.  2009.  Zoltar: a spectrum-based fault localization tool. Proceedings of the 2009 ESEC/FSE workshop on Software integration and evolution. :23–30. Abstractp23.pdf

Locating software components which are responsible for observed failures is the most expensive, error-prone phase in the software development life cycle. Automated diagnosis of software faults can improve the efficiency of the debugging process, and is therefore an important process for the development of dependable software. In this paper we present a toolset for automatic fault localization, dubbed Zoltar, which adopts a spectrum-based fault localization technique. The toolset provides the infrastructure to automatically instrument the source code of software programs to produce runtime data, which is subsequently analyzed to return a ranked list of likely faulty locations. Aimed at total automation (e.g., for runtime fault diagnosis), Zoltar has the capability of instrumenting the program under analysis with fault screeners, for automatic error detection. Using a small thread-based example program as well as a large realistic program, we show the applicability of the proposed toolset.

Abreu R, Mayer W, Stumptner M, Van Gemund AJC.  2009.  Refining spectrum-based fault localization rankings. Proceedings of the 2009 ACM symposium on Applied Computing - ACM SAC. :409–414. Abstractsacse-abreu09.pdf

Spectrum-based fault localization is a statistical technique that aims at helping software developers to find faults quickly by analyzing abstractions of program traces to create a ranking of most probable faulty components (e.g., program statements). Although spectrum-based fault localization has been shown to be effective, its diagnostic accuracy is inherently limited, since the semantics of components are not considered. In particular, components that exhibit identical execution patterns cannot be distinguished. To enhance its diagnostic quality, in this paper, we combine spectrum-based fault localization with a model-based debugging approach based on abstract interpretation within a framework coined DEPUTO. The model-based approach is used to refine the ranking obtained from the spectrum-based method by filtering out those components that do not explain the observed failures when the program’s semantics is considered. We show that this combined approach outperforms the individual approaches and other state-of-the-art automated debugging techniques.

Mayer W, Abreu R, Stumptner M, van Gemund AJ, others.  2009.  Prioritising model-based debugging diagnostic reports. Proceedings of the International Workshop on Principles of Diagnosis (DX). Abstract0deec52dfd7882839b000000.pdf

Model-based debugging has proved successful as a tool to guide automated debugging efforts, but the technique may suffer from large result sets in prac-tice, since no means to rank or discriminate between the returned candidate explanations are available. We present a unique combination of model-and spectrum-based fault localisation approach to rank explanations and show that the combined frame-work outperforms the individual approaches as well as other state of the art automated debugging mech-anisms.

Abreu R, Zoeteweij P, Gemund A.  2009.  Localizing Software Faults Simultaneously. 9th International Conference on Quality Software - QSIC. :367–376. Abstractqsic09.pdf

Current automatic diagnosis techniques are predominantly of a statistical nature and, despite typical defect densities, do not explicitly consider multiple faults, as also demonstrated by the popularity of the single-fault Siemens set. We present a logic reasoning approach, called Zoltar-M(ultiple fault), that yields multiple-fault diagnoses, ranked in order of their probability. Although application of Zoltar-M to programs with many faults requires further research into heuristics to reduce computational complexity, theory as well as experiments on synthetic program models and two multiple-fault program versions from the Siemens set show that for multiple-fault programs this approach can outperform statistical techniques, notably spectrum-based fault localization (SFL). As a side-effect of this research, we present a new SFL variant, called Zoltar-S(ingle fault), that is provably optimal for single-fault programs, outperforming all other variants known to date.

Abreu R, Zoeteweij P, Van Gemund AJC.  2009.  A Bayesian Approach to Diagnose Multiple Intermittent Faults. Proceedings of the Twentieth International Workshop on Principles of Diagnosis (DX'09). Abstractdx09-1.pdf

Logic reasoning approaches to fault diagnosis account for the fact that a component cj may
fail intermittently by introducing a parameter gj that expresses the probability the component exhibits
correct behavior. This component parameter gj , in conjunction with a priori fault probability, is used in
a Bayesian framework to compute the posterior fault candidate probabilities. Usually, information on gj
is not known a priori. While proper estimation of gj can have a great impact on the diagnostic accuracy,
at present, only approximations have been proposed. We present a novel framework, BARINEL, that
computes exact estimations of gj as integral part of the posterior candidate probability computation.
BARINEL’s diagnostic performance is evaluated for both synthetic systems and the Siemens software
benchmark. Our results show that our approach is superior to approaches based on classical persistent
fault models as well as previously proposed intermittent fault models.

Abreu R, Van Gemund AJC.  2009.  Statistics-directed Minimal Hitting Set Algorithm. Proceedings of the Twentieth International Workshop on Principles of Diagnosis (DX'09). :51–58. Abstractsara09.pdf

Generating minimal hitting sets of a collection of sets is known to be NP-hard, necessitating heuristic approaches to handle large problems. In this paper a low-cost, approximate minimal hitting set (MHS) algorithm, coined Staccato, is presented. Staccato uses a heuristic function, borrowed from a lightweight, statistics-based software fault localization approach, to guide the MHS search. Given the nature of the heuristic function, Staccato is specially tailored to model-based diagnosis problems (where each MHS solution is a diagnosis to the problem), although well-suited for other application domains as well. We apply Staccato in the context of model-based diagnosis and show that even for small problems our approach is orders of magnitude faster than the brute-force approach, while still capturing all important solutions. Furthermore, due to its low cost complexity, we also show that Staccato is amenable to large problems including millions of variables.