Recent Publications

Cunha A, Garis A, Paiva A, Riesco D.  2012.  Specifying UML Protocol State Machines in Alloy. Proceedings of the 9th International Conference on Integrated Formal Methods - IFM. 7321 Abstractifm12.pdf

A UML Protocol State Machine (PSM) is a behavioral diagram for the specification of the external behavior of a class, interface or component. PSMs have been used in the software development process for different purposes, such as requirements analysis and testing. However, like other UML diagrams, they are often difficult to validate and verify, specially when combined with other artifacts, such as Object Constraint Language (OCL) specifications. This drawback can be overcome by application of an off-the-shelf formal method, namely one supporting automatic validation and verification. Among those, we have the increasingly popular Alloy, based on a simple relational flavor of first-order logic. This paper presents a model transformation from PSMs, optionally complemented with OCL specifications, to Alloy. Not only it enables automatic verification and validation of PSMs, but also a smooth integration of Alloy in current software development practices.

Jimenez-Peris R, Patiño-Martínez M, Brondino I, Pereira JO, Oliveira R, Vilaça R, Kemme B, Ahmad Y.  2012.  CumuloNimbo: Parallel-Distributed Transactional Processing. Proceedings of the CloudFutures Workshop. Abstractcumulonimbo-ultra-scalable-transactional-processing-v6.pdf

CumuloNimbo aims at solving the lack of scalability of transactional applications that represent a large fraction of existing applications. CumuloNimbo aims at conceiving, architecting and developing a transactional, coherent, elastic and ultra scalable Platform as a Service. Its goals are: Ultra scalable and dependable, able to scale from a few users to many millions of users while at the same time providing continuous availability; Support transparent migration of multi-tier applications (e.g. Java EE applications, relational DB applications, etc.) to the cloud with automatic scalability and elasticity. Avoid reprogramming of applications and non-transparent scalability techniques such as sharding. Support transactions for new data stores such as cloud data stores, graph databases, etc.The main challenges are: Update ultrascalability (million update transactions per second and as many read-only transactions as needed). Strong transactional consistency. Non-intrusive elasticity. Inexpensive high availability. Low latency. CumuloNimbo goes beyond the state of the art by scaling transparently transactional applications to very large rates without sharding, the current practice in Today?s cloud. In this paper we describe CumuloNimbo architecture and its performance.

Beernaert L, Matos M, Vilaça R, Oliveira R.  2012.  Automatic elasticity in OpenStack. Proceedings of Workshop on Secure and Dependable Middleware for Cloud Monitoring and Management (with Middleware 2012). Abstractsdmcmm-elastack.pdf

Cloud computing infrastructures are the most recent ap- proach to the development and conception of computational systems. Cloud infrastructures are complex environments with various subsystems, each one with their own challenges. Cloud systems should be able to provide the following fun- damental property: elasticity. Elasticity is the ability to automatically add and remove instances according to the needs of the system. This is an requirement for pay-per-use billing models. Various open source software solutions allow companies and institutions to build their own Cloud infrastructure. How- ever, in most of these, the elasticity feature is quite imma- ture. Monitoring and timely adapting the active resources of a Cloud computing infrastructure is key to provide the elasticity required by diverse, multi tenant and pay-per-use business models. In this paper, we propose Elastack, an automated monitor- ing and adaptive system, generic enough to be applied to existing IaaS frameworks and intended to enable the elastic- ity they currently lack. Our approach offers any Cloud in- frastructure the mechanisms to implement automated mon- itoring and adaptation as well as the flexibility to go beyond these. We evaluate Elastack by integrating it with the Open- Stack and showing how easy it is to add these important features with a minimum, almost imperceptible, amount of modifications to the default installation.

Matos M, Schiavoni V, Felber P, Oliveira R, Rivière E.  2012.  Brisa: Combining efficiency and reliability in epidemic data dissemination. Proceedings of 26th IEEE International Parallel & Distributed Processing Symposium (IPDPS). Abstractipdps-brisa.pdf

There is an increasing demand for efficient and robust systems able to cope with today's global needs for intensive data dissemination, e.g., media content or news feeds. Unfortunately, traditional approaches tend to focus on one end of the efficiency/robustness design spectrum, by either leveraging rigid structures such as trees to achieve efficient distribution, or using loosely-coupled epidemic protocols to obtain robustness. In this paper we present BRISA, a hybrid approach combining the robustness of epidemic-based dissemination with the effi- ciency of tree-based structured approaches. This is achieved by having dissemination structures such as trees implicitly emerge from an underlying epidemic substrate by a judicious selection of links. These links are chosen with local knowledge only and in such a way that the completeness of data dissemination is not compromised, i.e., the resulting structure covers all nodes. Failures are treated as an integral part of the system as the dissemination structures can be promptly compensated and repaired thanks to the underlying epidemic substrate. Besides presenting the protocol design, we conduct an extensive evaluation in a real environment, analyzing the effectiveness of the structure creation mechanism and its robustness under faults and churn. Results confirm BRISA as an efficient and robust approach to data dissemination in the large scale.

Oliveira JN.  2012.  Typed Linear Algebra for Weighted (Probabilistic) Automata. CIAA - 17th International Conference on Implementation and Application of Automata . 7381:52-65. Abstract_ol12.pdf

There is a need for a language able to reconcile the recent upsurge of interest in quantitative methods in the software sciences with logic and set theory that have been used for so many years in capturing the qualitative aspects of the same body of knowledge. Such a lingua franca should be typed, polymorphic, diagrammatic, calculational and easy to blend with traditional notation.
This paper puts forward typed linear algebra (LA) as a candidate notation for such a role. Typed LA emerges from regarding matrices as morphisms of suitable categories whereby traditional linear algebra is equipped with a type system.
In this paper we show typed LA at work in describing weighted (prob- abilistic) automata. Some attention is paid to the interface between the index-free language of matrix combinators and the corresponding index- wise notation, so as to blend with traditional set theoretic notation.

Macedo H, Oliveira JN.  2012.  Towards Linear Algebras of Components. FACS - Formal Aspects of Component Software . 6921:300-303. Abstract

We show that there is significant foundational work on what could lead to a linear algebra approach to software components. Should these be weighted automata or machines in the sense of Bloom, we show that there is a constructive, fully typed approach to such matrix models. However abstract or primitive these may look to practitioners, they promise the calculation style which is the hallmark of engineering disciplines.

Couto R, Ribeiro AN, Campos JC.  2012.  A Patterns Based Reverse Engineering Approach for Java Source Code. 35th Annual Software Engineering Workshop - SEW. :140-147. Abstractsew_35.pdf

The ever increasing number of platforms and languages available to software developers means that the software industry is reaching high levels of complexity. Model Driven Architecture (MDA) presents a solution to the problem of improving software development processes in this changing and complex environment. MDA driven development is based on models definition and transformation. Design patterns provide a means to reuse proven solutions during development. Identifying design patterns in the models of a MDA approach helps their understanding, but also the identification of good practices during analysis. However, when analyzing or maintaining code that has not been developed according to MDA principles, or that has been changed independently from the models, the need arises to reverse engineer the models from the code prior to patterns' identification. The approach presented herein consists in transforming source code into models, and infer design patterns from these models. Erich Gamma's cataloged patterns provide us a starting point for the pattern inference process. MapIt, the tool which implements these functionalities is described.

Jorge AM, Moreira JM, de Sousa JF, Soares C, Azevedo PJ.  2012.  Finding Interesting Contexts for Explaining Deviations in Bus Trip Duration Using Distribution Rules. The 11th International Symposium on Intelligent Data Analysis - IDA. :139-149. Abstractchp3a10.10072f978-3-642-34156-4_14.pdf

In this paper we study the deviation of bus trip duration and its causes. Deviations are obtained by comparing scheduled times against actual trip duration and are either delays or early arrivals. We use distribution rules, a kind of association rules that may have continuous distributions on the consequent. Distribution rules allow the systematic identification of particular conditions, which we call contexts, under which the distribution of trip time deviations differs significantly from the overall deviation distribution. After identifying specific causes of delay the bus company operational managers can make adjustments to the timetables increasing punctuality without disrupting the service.

Cruz D, Frade MJ, Pinto JS.  2012.  Verification conditions for single-assignment programs. Proceedings of the 27th Annual Symposium on Applied Computing - SAC. :1264–1270. Abstractverification-conditions-revised.pdf

This paper is a systematic study of verification conditions and their use in the context of program verification. We take Hoare logic as a starting point and study in detail how a verification conditions generator can be obtained from it. The notion of program annotation is essential in this process. Weakest preconditions and the use of updates are also studied as alternative approaches to verification conditions. Our study is carried on in the context of a While language. Important extensions to this language are considered toward the end of the paper. We also briefly survey modern program verification tools and their approaches to the generation of verification conditions.

Faria JM, Martins J, Pinto JS.  2012.  An approach to model checking Ada programs. Proceedings of the 17th Ada-Europe international conference on Reliable Software Technologies - Ada- Europe. :105–118. Abstractinforum.pdf

This paper describes a tool-supported method for the formal veri cation of Ada programs. It presents ATOS, a tool that automatically extracts a model in SPIN from an Ada Program, together with a set of properties that state the correctness of the model. ATOS is also capable of extracting properties from user-provided annotations in Ada programs, inspired by the Spark Annotation language. The goal of ATOS is to help in the veri cation of sequential and concurrent Ada programs based on model checking. The paper introduces the details of the proposed mechanisms, as well as the results of experimental validation, through a case study.

Almeida PS, Moreno CB, Cunha A.  2012.  A Fast Distributed Computation of Distances in Networks. IEEE 51st Annual Conference on Decision and Control - CDC. :5215–5220. Abstractcdc12-1.pdf

This paper presents a distributed algorithm to simultaneously compute the diameter, radius and node eccentricity in all nodes of a synchronous network. Such topological information may be useful as input to configure other algorithms. Previous approaches have been modular, progressing in sequential phases using building blocks such as BFS tree construction, thus incurring longer executions than strictly required. We present an algorithm that, by timely propagation of available estimations, achieves a faster convergence to the correct values. We show local criteria for detecting convergence in each node. The algorithm avoids the creation of BFS trees and simply manipulates sets of node ids and hop counts. For the worst scenario of variable start times, each node i with eccentricity ecc(i) can compute: the node eccentricity in diam(G)+ecc(i)+2 rounds; the diameter in 2 diam(G)+ecc(i)+2 rounds; and the radius in diam(G) + ecc(i) + 2 radius(G) rounds.

Almeida JB, Barbosa MB, Bangerter E, Barthe G, Krenn S, Béguelin SZ.  2012.  Full proof cryptography: verifiable compilation of efficient zero-knowledge protocols. Conference on Computer and Communications Security - CCS. :488-500. Abstract12ccs.pdf

Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from having to implement cryptography on their own by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is risky as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify.
In this paper, we present ZKCrypt, an optimizing cryptographic compiler that achieves an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt tightly integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage in the pipeline, ZKCrypt provides assurance that the implementation it outputs securely realizes the high-level proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.

Martins P, Lopes P, Fernandes JP, Saraiva JA, Cardoso J.  2012.  Program and Aspect Metrics for MATLAB. 12th International Conference on Computational Science and Its Applications - ICCSA. :217-233. Abstracticcsa12_matlab.pdf

In this paper we present the main concepts of a domain-specific aspect language for specifying cross-cutting concerns of MATLAB programs, together with a suite of metrics that is capable of assessing the overall advantage of introducing aspects in the development cycle of MATLAB software. We present the results of using our own suite to quantify the advantages of using aspect oriented programming, both in terms of programming effort and code quality. The results are promising and show a good potential for aspect oriented programming in MATLAB while our suite proves to be capable of analyzing the overall characteristics of MATLAB solutions and providing interesting results about them.

Martins P, Fernandes JP, Saraiva JA.  2012.  A Purely Functional Combinator Language for Software Quality Assessment. Symposium Languages, Applications and Technologies - SLATE. :51-69. Abstract7.pdf

Quality assessment of open source software is becoming an important and active research area. One of the reasons for this recent interest is the consequence of Internet popularity. Nowadays, programming also involves looking for the large set of open source libraries and tools that may be reused when developing our software applications. In order to reuse such open source software artifacts, programmers not only need the guarantee that the reused artifact is certified, but also that independently developed artifacts can be easily combined into a coherent piece of software. In this paper we describe a domain specific language that allows programmers to describe in an abstract level how software artifacts can be combined into powerful software certification processes. This domain specific language is the building block of a web-based, open-source software certification portal. This paper introduces the embedding of such domain specific language as combinator library written in the Haskell programming language. The semantics of this language is expressed via attribute grammars that are embedded in Haskell, which provide a modular and incremental setting to define the combination of software artifacts.

Barbosa LS.  2012.  Software Components as Invariant-Typed Arrows - (Keynote Talk). Proceedings of 16th Brazilian Symposium on Programming Languages - SBLP. 7554:1-5. Abstractbarbosacbsoft12.pdf

nvariants are constraints on software components which restrict their behavior in some desirable way, but whose maintenance entails some kind of proof obligation discharge. Such constraints may act not only over the input and output domains, as in a purely functional setting, but also over the underlying state space, as in the case of reactive components. This talk introduces an approach for reasoning about invariants which is both compositional and calculational: compositional because it is based on rules which break the complexity of such proof obligations across the structures involved; calculational because such rules are de- rived thanks to an algebra of invariants encoded in the language of binary relations. A main tool of this approach is the pointfree transform of the predicate calculus, which opens the possibility of changing the underly- ing mathematical space so as to enable agile algebraic calculation. The development of a theory of invariant preservation requires a broad, but uniform view of computational processes embodied in software components able to take into account data persistence and continued interaction. Such is the plan for this talk: we first introduce such processes as arrows, and then invariants as their types.