Recent Publications

Fayollas C, Martinie C, Palanque P, Masci P, Harrison MD, Campos JC, Silva SR.  2016.  Evaluation of formal IDEs for human-machine interface design and analysis: the case of CIRCUS and PVSio-web. Workshop on Integrated Formal Development Environment (F-IDE 2016), co-located with FM2016. f-ide2016-camera-ready.pdf
Costa CM, Leite CRM, Sousa AL.  2016.  Efficient SQL adaptive query processing in cloud databases systems. 2016 {IEEE} Conference on Evolving and Adaptive Intelligent Systems, {EAIS} 2016, Natal, Brazil, May 23-25, 2016. :114–121. Abstract16.pdf

n/a

Oliveira B, Belo O, Macedo N.  2016.  Towards a Formal Validation of ETL Patterns Behavior. 6th International Conference on Model and Data Engineering (MEDI 2016).
Macedo N, Brunel J, Chemouil D, Cunha A, Kuperberg D.  2016.  Lightweight Specification and Analysis of Dynamic Systems with Rich Configurations. 24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE 2016). 14.pdf
Almeida JB, Barbosa M, Barthe G, Dupressoir F.  2016.  Verifiable side-channel security of cryptographic implementations: constant-time MEE-CBC. Fast Software Encryption – 23nd International Workshop, FSE 2016. 9783:163–184. Abstract16fse.pdf

We provide further evidence that implementing software countermeasures against timing attacks is a non-trivial task and requires domain-specific software development processes: we report an implementation bug in the s2n library, recently released by AWS Labs. This bug (now fixed) allowed bypassing the balancing countermeasures against timing attacks deployed in the implementation of the MAC-then- Encode-then-CBC-Encrypt (MEE-CBC) component, creating a timing side-channel similar to that exploited by Lucky 13.

Although such an attack could only be launched when the MEE-CBC component is used in isolation – Albrecht and Paterson recently confirmed in independent work that s2n’s second line of defence, once reinforced, provides adequate mitigation against current adversary capabilities – its existence serves as further evidence to the fact that conventional software validation processes are not effective in the study and validation of security properties. To solve this problem, we define a methodology for proving security of implementations in the presence of timing attackers: first, prove black-box security of an algorithmic description of a cryptographic construction; then, establish functional correctness of an implementation with respect to the algorithmic description; and finally, prove that the implementation is leakage secure.

We present a proof-of-concept application of our methodology to MEE-CBC, bringing together three different formal verification tools to produce an assembly implementation of this construction that is verifiably secure against adversaries with access to some timing leakage. Our methodology subsumes previous work connecting provable security and side-channel analysis at the implementation level, and supports the verification of a much larger case study. Our case study itself provides the first provable security validation of complex timing countermeasures deployed, for example, in OpenSSL.

Almeida JB, Barbosa M, Barthe G, Dupressoir F, Emmi M.  2016.  Verifying Constant-Time Implementations. 25th USENIX Security Symposium, USENIX Security' 16. :53–70. Abstract16usenix.pdf

The constant-time programming discipline is an effective countermeasure against timing attacks, which can lead to complete breaks of otherwise secure systems. However, adhering to constant-time programming is hard on its own, and extremely hard under additional efficiency and legacy constraints. This makes automated verification of constant-time code an essential component for building secure software.

We propose a novel approach for verifying constant-time security of real-world code. Our approach is able to validate implementations that locally and intentionally violate the constant-time policy, when such violations are benign and leak no more information than the public outputs of the computation. Such implementations, which are used in cryptographic libraries to obtain important speedups or to comply with legacy APIs, would be declared insecure by all prior solutions.

We implement our approach in a publicly available, cross-platform, and fully automated prototype, ct-verif, that leverages the SMACK and Boogie tools and verifies optimized LLVM implementations. We present verification results obtained over a wide range of constant-time components from the NaCl, OpenSSL, FourQ and other off-the-shelf libraries. The diversity and scale of our examples, as well as the fact that we deal with top-level APIs rather than being limited to low-level leaf functions, distinguishes ct-verif from prior tools.

Our approach is based on a simple reduction of constant-time security of a program P to safety of a product program Q that simulates two executions of P. We formalize and verify the reduction for a core high-level language using the Coq proof assistant.

Pontes R, Maia F, Paulo J, Vilaça R.  2016.  SafeRegions: Performance Evaluation of Multi-party Protocols on HBase. 2016 IEEE 35th Symposium on Reliable Distributed Systems Workshops (SRDSW), 2016 . :31-36.13.pdf
Burihabwa D, Pontes R, Felber P, Maia F, Mercier H, Oliveira R, Paulo J, Schiavoni V.  2016.  On the Cost of Safe Storage for Public Clouds: an Experimental Evaluation.. 35th IEEE International Symposium on Reliable Distributed Systems 2016.. 12.pdf
Kolev B, Bondiombouy C, Valduriez P, Jimenez-Peris R, Pau R, Pereira JO.  2016.  The CloudMdsQL Multistore System. Proceedings of the 2016 International Conference on Management of Data. :2113–2116. Abstract11.pdf

n/a

Kolev B, Bondiombouy C, Levchenko O, Valduriez P, Jimenez-Peris R, Pau R, Pereira JO.  2016.  Design and Implementation of the CloudMdsQL Multistore System. Proceedings of the 6th International Conference on Cloud Computing and Services Science. :352-359. Abstract10.pdf

n/a

Santiago RHN, Bedregal B{\'ı}nRC, Madeira A, Martins MA.  2016.  On Interval Dynamic Logic. Formal Methods: Foundations and Applications - 19th Brazilian Symposium, {SBMF} 2016, Natal, Brazil, November 23-25, 2016, Proceedings. :129–144. Abstract
n/a
Madeira A, Martins MA, Barbosa LS.  2016.  A logic for n-dimensional hierarchical refinement. Proceedings 17th International Workshop on Refinement, Refine@FM 2015, Oslo, Norway, 22nd June 2015. 209:40–56.2.pdf
Madeira A, Barbosa LS, Hennicker R, Martins MA.  2016.  Dynamic Logic with Binders and Its Application to the Development of Reactive Systems. Theoretical Aspects of Computing - ICTAC 2016 - 13th International Colloquium, Taipei, Taiwan, ROC, October 24-31, 2016, Proceedings. 9965:422–440. Abstractmbhm16.pdf

This paper introduces a logic to support the specification and development of reactive systems on various levels of abstraction, from property specifications, concerning e.g. safety and liveness requirements, to constructive specifications representing concrete processes. This is achieved by combining binders of hybrid logic with regular modalities of dynamic logics in the same formalism, which we call D↓-logic. The semantics of our logic focuses on effective processes and is therefore given in terms of reachable transition systems with initial states. The second part of the paper resorts to this logic to frame stepwise development of reactive systems within the software development methodology proposed by Sannella and Tarlecki. In particular, we instantiate the generic concepts of constructor and abstractor implementations by using standard operators on reactive components, like relabelling and parallel composition, as constructors, and bisimulation for abstraction. We also study vertical composition of implementations which relies on the preservation of bisimularity by the constructions on labeleld transition systems.

Neves R, Barbosa LS.  2016.  Hybrid Automata as Coalgebras. Theoretical Aspects of Computing - ICTAC 2016 - 13th International Colloquium, Taipei, Taiwan, ROC, October 24-31, 2016, Proceedings. 9965:385–402. Abstractnb16.pdf

Able to simultaneously encode discrete transitions and continuous behaviour, hybrid automata are the de facto framework for the formal specification and analysis of hybrid systems. The current paper revisits hybrid automata from a coalgebraic point of view. This allows to interpret them as state-based components, and provides a uniform theory to address variability in their definition, as well as the corresponding notions of behaviour, bisimulation, and observational semantics.

Fernandes S, Barbosa LS.  2016.  Applying the 3C Model to FLOSS Communities. Collaboration and Technology - 22nd International Conference, CRIWG 2016, Kanazawa, Japan, September 14-16, 2016, Proceedings. 9848:139–150. Abstractfb16a.pdf

How learning occurs within Free/Libre Open Source (FLOSS) communities and what is the dynamics such projects (e.g. the life cycle of such projects) are very relevant questions when considering the use of FLOSS projects in a formal education setting. This paper introduces an approach based on the 3C collaboration model (communication, coordination and cooperation) to represent the collaborative learning dynamics within FLOSS communities. To explore the collaborative learning potential of FLOSS communities a number of questionnaires and interviews to selected FLOSS contributors were run. From this study a 3C collaborative model applicable to FLOSS communities was designed and discussed.