Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Publications

Publications by Jorge Sousa Pinto

2016

Formalizing Single-Assignment Program Verification: An Adaptation-Complete Approach

Authors
Lourenco, CB; Frade, MJ; Pinto, JS;

Publication
PROGRAMMING LANGUAGES AND SYSTEMS (ESOP 2016)

Abstract
Deductive verification tools typically rely on the conversion of code to a single-assignment (SA) form. In this paper we formalize program verification based on the translation of While programs annotated with loop invariants into a dynamic single-assignment language with a dedicated iterating construct, and the subsequent generation of compact, indeed linear-size, verification conditions. Soundness and completeness proofs are given for the entire workflow, including the translation of annotated programs to SA form. The formalization is based on a program logic that we show to be adaptation-complete. Although this important property has not, as far as we know, been established for any existing program verification tool, we believe that adaptation-completeness is one of the major motivations for the use of SA form as an intermediate language. Our results here show that indeed this allows for the tools to achieve the maximum degree of adaptation when handling subprograms.

2015

Monitoring for a Decidable Fragment of MTL-integral

Authors
Pedro, AD; Pereira, D; Pinho, LM; Pinto, JS;

Publication
RUNTIME VERIFICATION, RV 2015

Abstract
Temporal logics targeting real-time systems are traditionally undecidable. Based on a restricted fragment of MTL-integral, we propose a new approach for the runtime verification of hard real-time systems. The novelty of our technique is that it is based on incremental evaluation, allowing us to effectively treat duration properties (which play a crucial role in real-time systems). We describe the two levels of operation of our approach: offline simplification by quantifier removal techniques; and online evaluation of a three-valued interpretation for formulas of our fragment. Our experiments show the applicability of this mechanism as well as the validity of the provided complexity results.

2014

CAOVerif: An open-source deductive verification platform for cryptographic software implementations

Authors
Almeida, JB; Barbosa, M; Filliatre, JC; Pinto, JS; Vieira, B;

Publication
SCIENCE OF COMPUTER PROGRAMMING

Abstract
CAO is a domain-specific imperative language for cryptography, offering a rich mathematical type system and crypto-oriented language constructions. We describe the design and implementation of a deductive verification platform for CAO and demonstrate that the development time of such a complex verification tool could be greatly reduced by building on the Jessie plug-in included in the Frama-C framework. We discuss the interesting challenges raised by the domain-specific characteristics of CAO, and describe how we tackle these problems in our design. We base our presentation on real-world examples of CAO code, extracted from the open-source code of the NaCl cryptographic library, and illustrate how various cryptography-relevant security properties can be verified.

2013

Formal verification of side-channel countermeasures using self-composition

Authors
Bacelar Almeida, JB; Barbosa, M; Pinto, JS; Vieira, B;

Publication
SCIENCE OF COMPUTER PROGRAMMING

Abstract
Formal verification of cryptographic software implementations poses significant challenges for off-the-shelf tools. This is due to the domain-specific characteristics of the code, involving aggressive optimizations and non-functional security requirements, namely the critical aspect of countermeasures against side-channel attacks. In this paper, we extend previous results supporting the practicality of self-composition proofs of non-interference and generalizations thereof. We tackle the formal verification of high-level security policies adopted in the implementation of the recently proposed NaCl cryptographic library. We formalize these policies and propose a formal verification approach based on self-composition, extending the range of security policies that could previously be handled using this technique. We demonstrate our results by addressing compliance with the NaCl security policies in real-world cryptographic code, highlighting the potential for automation of our techniques.

2014

A Bounded Model Checker for SPARK Programs

Authors
Lourenco, CB; Frade, MJ; Pinto, JS;

Publication
AUTOMATED TECHNOLOGY FOR VERIFICATION AND ANALYSIS, ATVA 2014

Abstract
This paper discusses the design and implementation of a bounded model checker for SPARK code, and provides a proof of concept of the utility and practicality of bounded verification for SPARK.

2014

Towards a Runtime Verification Framework for the Ada Programming Language

Authors
Pedro, AD; Pereira, D; Pinho, LM; Pinto, JS;

Publication
RELIABLE SOFTWARE TECHNOLOGIES - ADA-EUROPE 2014

Abstract
Runtime verification is an emerging discipline that investigates methods and tools to enable the verification of program properties during the execution of the application. The goal is to complement static analysis approaches, in particular when static verification leads to the explosion of states. Non-functional properties, such as the ones present in real-time systems are an ideal target for this kind of verification methodology, as are usually out of the range of the power and expressiveness of classic static analyses. In this paper, we present a framework that allows real-time programs written in Ada to be augmented with runtime verification capabilities. Our framework provides the infrastructures which is needed to instrument the code with runtime monitors. These monitors are responsible for observing the system and reaching verdicts about whether its behavior is compliant with its non-functional properties. We also sketch a contract language to extend the one currently provided by Ada, with the long term goal of having an elegant way in which runtime monitors can be automatically synthesized and instrumented into the target systems. The usefulness of the proposed approach is demonstrated by showing its use for an application scenario.

  • 1
  • 11