FIRST PROMETIDOS-CM SUMMER SCHOOL

(Free assistance -- no registration fees!)
19-21 September 2011
Facultad de Informática, Universidad Complutense de Madrid
Madrid, Spain


NEWS

  • 22-07-2011: Program and location information have been added
  • 13-09-2011: McErlang talk: Clara Benac added as co-speaker + some instructions about installing McErlang

LOCATION

Sala de Grados (first floor)

Facultad de Informática - UCM
C/ Profesor Jose Garcia Santesmases s/n
http://www.fdi.ucm.es/Acceso_fdi/Acceso.asp


View Larger Map

PROMETIDOS-CM (Madrid Program in Rigorous Methods for the Development of Software) is a R+D program funded by the regional government of Madrid, Spain, that involves some leading research groups in Computer Science in the region (IMDEA-Software, CLIP-UPM, BABEL-UPM, FADOSS-UCM, GPD-UCM).

The scientific interests of PROMETIDOS-CM cover all aspects of development of software based on modular, scalable and realistic rigorous methods.

One of the strategic purposes of PROMETIDOS-CM is the realization of effective training actions to introduce young post-graduate and PhD students in the research area of rigorous methods. The announced Summer School attempts to be a contribution in this sense.


STRUCTURE OF THE SCHOOL

The First PROMETIDOS-CM Summer School will consist of a series of talks given by experienced researchers affiliated to the program partners.

The talks are intended to be both attractive and rigorous. Some of them will include practical demonstrations..


LIST OF SPEAKERS/TALKS

  • David de Frutos (UCM) - Semantics of Concurrent Processes: Unification and new Directions.
  • Ricardo Peña (UCM) - Static Analysis and Certification of Safety Properties of Memory Usage
  • Rafael Caballero (UCM) - Declarative Debugging
  • Fernando Sáenz (UCM) - Deductive Databases
  • Elvira Albert - Miguel Gómez-Zamalloa (UCM) - Test Case Generation and Cost Analysis in Java-like Languages
  • Julio Mariño (UPM) - Modeling and verification of concurrent systems using shared resources
  • Lars-Åke Fredlund - Clara Benac (UPM) - Erlang and the McErlang model checker
  • Boris Köpf (IMDEA-Software) - Quantitative Information-Flow Analysis
  • César Kunz (IMDEA-Software) - Relational Verification Using Product Programs
  • Alexander Malkis (IMDEA-Software) - Modular verification of threads
  • Jose Francisco Morales (UPM) - Optimizing Compilation Techniques for Logic Programming
  • Manuel Carro Liñares (UPM) - Tabled Logic Programming and Applications

REGISTRATION

This Summer School is organized in a quite lightweight way. There are neither attendance fees nor a formal on-line registration. You only need to send a message to the organizers:

Francisco Lopez-Fraguas (fraguas at sip.ucm.es)

Narciso Martí (narciso at sip.ucm.es).

A certificate of assistance will be given at the end of the School.


LUNCH AND ACCOMMODATION

They are not provided by the organization. Having lunch at the Faculty cafeteria is easy and inexpensive (5 euro for a three courses meal).

Regarding accommodation, the organization can help as follows:

  • We have reserved some (very few) places in double rooms to share in a student residence hall in the Campus (~ 25 euro approx. per night and person) ; Please contact the organizers if you are interested in these.
  • Some hotels not far from the Campus have agreed with the University some reduced prices (around 90 euro/night for a single room) with respect to their normal rates. Please contact the organizers to get more information. But some people prefer to spend some googling time to get some other (maybe cheaper) accommodation options in the city center.

Please visit http://gpd.sip.ucm.es/trac/gpd/wiki/FirstPrometidosSummerSchool from time to time to see if some new information (location maps, programme,...) is given there.


ABSTRACTS OF THE TALKS, SHORT CV OF THE SPEAKERS AND VIDEOS

David de Frutos Escrig
Semantics of Concurrent Processes: Unification and new Directions.

The complexity of parallel systems produces a large collection of semantics for processes. We have looked for the ways to introduce some order in it, getting the keys to produce a systematic presentation of the spectrum of semantics using several frameworks: observational, equational and logic semantics. Our study produces not only a taxanomic classification, but more importantly take out the principles that participate in the conception of each of the semantics, and gives us some general techniques to study all the semantics in a uniform way, without needing to develop similar but separate proofs for the general results that are applicable to all of them. Moreover, we will discuss new aspects to take into account if we want to produce more accurate semantics that capture in the adequate way the characteristics of the different actions executed by a process. This means covariant-contravariant semantics and conformance, by means of which we can define more natural orderings that make the semantics more naturally applicable in practice.

David de Frutos Escrig is a Full Professor of Computer Science that is mainly interested in the study of Semantics for Programming Languages and Systems, and in particular in the Semantics of Concurrent Processes. As a consequence he has focussed his (recent) research in the field of Process Algebras and Petri Nets. He has supervised 8 Ph.D. Thesis devoted to these topics, and in particular the last two were devoted to the Unification of Process Semantics and the Decidability of Properties of Petri Net Systems including Replication and Names.'

Recording of the talk: Semantics of Concurrent Processes: Unification and new Directions


Ricardo Peña
Static Analysis and Certification of Safety Properties of Memory Usage

The talk summarizes the work done by the author and his group in the last few years on the functional language Safe. This is an experimental language aimed at platforms with limited memory resources, and at a proof-carrying code framework. Its programming model allows explicit deallocation of data structures, and its runtime system additionally supports regions, i.e. disjoint parts of the heap allocated and deallocated in constant time, which replace the more traditional garbage collector. The Safe compiler is equipped with a battery of static analyses and with a special type system which are able to first ensure, and then to formally certify, safety runtime properties such as absence of dangling pointers, and bounded memory consumption. Compiled programs are endowed with Isabelle/HOl scripts proving that these properties actually hold.

Ricardo Peña Marí is a full Professor in Computer Science at the "Sistemas Informáticos y Computación" Department of the "Universidad Complutense de Madrid". Up to 1991, he was Associate Professor at the "Universidad Politécnica de Cataluña", and prior to that he worked for two companies in the telecommunication and clothing industries as project leader of several software developments. He is the author of "Diseño de Programas", Pearson-Prentice Hall 2005, a textbook for undergraduate Computer Engineers, of "De Euclides a Java: historia de los algoritmos y de los lenguajes de programación", Nivola, 2006, a broad-audience book on the history of programming languages and algorithms, and co-author of "La Informática a todo mega", Ediciones SM 2000, a book for high-school students. He is co-author of more than 50 peer reviewed papers published in international journals and conferences, belongs or has belonged to several Program Committees of international conferences, has been the project leader of several competitive projects of the Spanish National Plan, and has been a member of several European Union funded projects. His research areas are functional language design and implementation, functional-parallel programming, static analysis, program certification, and proof-carrying code.'

Recording of the talk: Static Analysis and Certification of Safety Properties of Memory Usage


Rafael Caballero
Declarative Debugging

Declarative debugging is a debugging technique that abstracts the execution details to focus on the semantic meaning of the program components. It was first proposed in the field of Logic Programming, but its general structure has been later extended to other programming paradigms, becoming an active area of research. The technique relies on a data structure, the computation tree, that represents some computation producing an unexpected result. This tree is traversed by asking questions to the user about the correction of the intermediate computation steps until the source of the bug has been found. We show how instances of this general technique can be defined for different programming paradigms simply adapting the definition of computation tree. In particular we present the instances that have been developed by the Declarative Programming Group at the University Complutense of Madrid, which include functional-logic languages (Toy and Curry), object oriented languages (Java), deductive databases (Datalog) and SQL views.

Bachelor's degree in Computer Science by the Universidad Politécnica de Madrid and Ph.D in Mathematics by the Universidad Complutense de Madrid. Currently Lecturer (Prof. Contratado Doctor) in the Computer Science Department at the Faculty of Computer Science. Research areas of interest: functional-logic programming, declarative and algorithmic debugging, qualified declarative programming and in general declarative languages including uncertainty, SQL debugging and test-case generation, embedding of XML query languages in declarative languages, program transformation techniques for declarative languages.'

Recording of the talk: Declarative Debugging


Fernando Sáenz
Deductive Databases

We have witnessed a new interest on deductive databases, languages and technologies. Also, emerging companies promoting deductive technologies transfer these technological outcomes to practical applications. Datalog, as a preeminent deductive query language has been extensively studied and is gaining a renowned interest thanks to their application to ontologies, semantic web, social networks, policy languages, and even for optimization. Thus, the aim of this talk is to try to look at deductive databases from a renowned viewpoint as more features are being added making them more appealing. In addition to review some relevant deductive systems and technologies, we'll base our presentation on the grounds of DES (Datalog Educational System), which includes several extensions to the pure Datalog language, and its interactiveness makes it an adequate tool to rapidly acquire fundamentals.

Fernando Sáenz Pérez is currently an Associate Professor attached to the Department of Artificial Intelligence and Software Engineering. Since 1987, he has been involved in researching at the University Complutense of Madrid (Spain), and at the Institut für Informatik at Aachen (Germany). His current research interests include: declarative and constraint programming, and deductive databases. He has taken part in many basic research projects and development projects in tight touch with several corporations such as Repsol YPF, Enagás, Cofares, and Ente Público RTVE, performing actual research transfers. Sáenz-Pérez has been a member of several program committees and referee for both international and national conferences. He is also actively involved in several free, open-source projects such as DES.'

Recording of the talk: Deductive Databases


Elvira Albert - Miguel Gómez-Zamalloa
Test Case Generation and Cost Analysis in Java-like Languages

The course will focus on two topics which are often not related: (1) resource analysis and (2) test-case generation. As regards (1), the classical approach to static cost analysis consists of two phases: In the first one the program is translated into a set of recurrence relations; and in the second phase they are solved into closed-form upper/lower bounds. In this presentation we will discuss the main techniques used to generate cost relations in Java-like languages, depending on the nature of cost we are interested in approximating. We will also see the methods used for solving them into closed form bounds. As regards (2), we will study an approach to test case generation based on symbolic execution. The course will finish by relating the two techniques, namely by explaining how resource analysis can be used to guide the process of finding interesting test cases.

Elvira Albert is an Associate Professor at UCM since 2002. She has previously held positions at the Technical University of Valencia, where she received a Ph.D. in Computer Science in 2001. Elvira has been PC member at more than thirty international conferences (including major conferences like SAS, ISMM, LPAR, etc.), been conference chair of PPDP'08 and Bytecode'09 and belongs to the steering committee of PPDP. Her research interests include static and dynamic analyses, with special focus on resource consumption properties. She is author of more than 70 publications in international journals and volumes strongly related to the topics of the course.'

Miguel Gómez-Zamalloa is an assistant professor at the Complutense University of Madrid (UCM) since 2010. He was previously a lecturer at the Camilo José Cela University (2004 to 2006) and a teaching assistant at UCM (2007-2010). In 2009 Miguel received his Ph.D. in Computer Science at UCM supervised by professor Elvira Albert. His main research interests are program analysis, transformations and testing, namely, static resource analysis and test-case generation of object-oriented (concurrent) programs. Since 2006, Miguel has been a quiet active researcher in those research lines. This is witnessed by his more than 20 publications at international conferences and journals, the involvement in national and european research projects, the participation in the design and implementation of the COSTA (http://costa.ls.fi.upm.es) and PET (http://costa.ls.fi.upm.es/pet) systems, his collaboration as a reviewer in more than 20 international conferences, etc. See "http://clip.dia.fi.upm.es/~mzamalloa" for more details.'

Recording of Elvira's talk: Test Case Generation & Cost Analysis

Recording of Miguel's talk: Test Case Generation for OOP in CLP


Lars-Åke Fredlund - Clara Benac Earle
Erlang and the McErlang model checker

Developing reliable concurrent software is a hard task given the inherent non-deterministic nature of concurrent systems. A technique which is often used to check that a concurrent program fulfils a set of desirable properties is model checking. In model checking, all the states of a concurrent system are systematically explored.

We have developed McErlang, a model checker for Erlang. The Erlang program to be analyzed is run under the McErlang run-time system, under the control of a verification algorithm, by the normal Erlang byte-code interpreter. The pure computation part of the code, i.e, code with no side effects, including garbage collection, is executed by the normal Erlang run time system. However, the side effect part is executed under the McErlang run-time system which is a complete rewrite in Erlang of the basic process creating, scheduling, communication and fault-handling machinery of Erlang. Naturally the new run-time system offers easy check pointing (capturing the state of all nodes and processes, of the message mailboxes of all processes, and all messages in transit between processes) of the whole program state as a feature. McErlang has been used to verify critical parts of a number of Erlang applications.

In this talk we will give a brief introduction to Erlang and the McErlang tool.

Lars-Åke Fredlund first learned of Erlang when attending a course on "Declarative Real-Time Programming" at the Royal Institute of Technology in Stockholm, Sweden, in 1991. Working at the Swedish Institute of Computer Science (SICS), the relationship with Erlang continued; one outcome was a formal semantics for Erlang (part of his PhD thesis in 2001). Lured to Madrid in 2005, Lars-Åke found more free time to work with Erlang resulting in a number of articles concerning the "real" communication guarantees of Erlang (more tricky than you think...) and a new tool to verify concurrent Erlang software: McErlang. He also tries, mostly in vain, to convince his office mates and students at the Technical University of Madrid that Erlang has a much better process model than ADA.

Clara Benac Earle currently works at the Universidad Politécnica de Madrid where she lectures and works as a post-doc researcher in the EU FP7 ProTest Project. She first learnt of Erlang when working at the Ericsson CSLab in Stockholm, Sweden, in 1999. Her main research interest lies in the formal verification of concurrent programs, in particular applied to the Erlang programming language. She holds a PhD from the University of Kent, UK, since 2005.

Remark: the students are asked to bring a laptop with McErlang installed in it (follow the instructions "Installing McErlang" in https://babel.ls.fi.upm.es/trac/McErlang/)

Recording of the talk: Erlang and the McErlang model checker


Julio Mariño
Modeling and verification of concurrent systems using shared resources

"Shared resources" is a high-level, language independent model for concurrent programming based on a sharp distinction between active (threads, processes) and passive (interactions) entities. It is supported by a formal notation and companion methodology which, together, constitute a usable approach to the model driven development of concurrent applications. Shared resources have been used at UPM for teaching concurrency at the undergraduate level for the last 15 years.

Originally conceived as a gentle extension of a formal notation for teaching abstract data types -- just adding the extra synchronization component -- they have recently proved useful out of the classroom to model and analyze complex, real world systems.

From the point of view of software design, shared resources fill a gap in widely used modeling notations regarding concurrency. At the code level, they have been used for semi-automatic generation of correct-by-construction code. Finally, wrt. analysis and validation, they can be seen as automata generators.

The talk will give an overview of the formalism and methodology from the different points of view mentioned above. Then, a representative suite of examples of increasing complexity will be presented in order to demonstrate the expressivenes of the model. Finally, we will show the application of the formalism to requirements validation and code certification with the help of various analysis tools.

Julio Mariño is an associate professor at Universidad Politécnica de Madrid where he currently leads the Babel research group, devoted to the application of declarative technology to the development of reliable software. Most of his research deals with logic and constraint programming and the integration of the functional and logic paradigms. He has lectured on nonclassical logics, type systems, object-oriented analysis and design, and is currently responsible for teaching concurrency at undergraduate level and formal methods at graduate level at the School of Computer Science at UPM.'

Recording of the talk: Modeling and verification of concurrent systems using shared resources


Boris Köpf
Quantitative Information-Flow Analysis

Quantitative information-flow analysis (QIF) is an emerging method for establishing information-theoretic confidentiality guarantees. Such guarantees are attractive because they enable one to certify the security of systems that reveal only small amounts of information. Moreover, QIF provides a formal basis for reasoning about the ubiquitous trade-off between security and functionality / performance. In this tutorial I will give an overview of the state-of-the-art in research on QIF. In the first part, I will present the most influential measures of confidentiality and will compare them in terms of their underlying assumptions and the security guarantees they deliver. In the second part of the tutorial, I will present techniques for computing and enforcing corresponding quantitative security guarantees for real systems.

Boris is an Assistant Research Professor at the Madrid Institute of Advanced Studies in Software Development Technologies (IMDEA Software). His research centers around the quantitative aspects of Information Security. Prior to joining IMDEA, Boris completed his Ph.D. in the Information Security group of ETH Zurich and worked as a postdoc in the Information Security and Cryptography Group of the Max Planck Institute for Software Systems. Before that, he studied mathematics at the Universidad de Chile, the Universidade Federal de Campinas, and the University of Konstanz, from which he received a M.Sc.'


César Kunz
Relational reasoning using program products

Relational program logics are formalisms for specifying and verifying properties about two programs or two runs of the same program. These properties range from correctness of compiler optimizations or equivalence between two implementations of an abstract data type, to properties like non-interference or determinism. Yet the current technology for relational verification remains underdeveloped. Program products reduce relational verification directly to standard verification, thus enabling the use of existing tools, and minimize at the same time the loop specification effort. We illustrate the benefits of our method with selected examples, including non-interference, the validation of complex optimizations, and program continuity.

César Kunz is a Post-Doc researcher at the Technical University of Madrid (2011-present) and the IMDEA Software Institute in Madrid (2009-present), Spain, currently as a recipient of the Juan de la Cierva fellowship. He received his PhD in 2009 at the Ecole de Mines de Paris, advised by Gilles Barthe. His research interests are in the area of formal program analysis and verification, program optimization and compiler correctness. His recent work includes formal techniques for the verification of relational properties, such as translation validation, non-interference and program continuity.'

Recording of the talk: Relational reasoning using program products


Alexander Malkis
Verification of multi-threaded programs.

We give a short survey on verification of multi-threaded programs. The first part of our talk will concern practical verification in the SPIN tool, touching the following topics: Specification in Promela, saving space via COLLAPSE and automata encoding, saving time via partial order reduction. The second part of our talk will concern modular methods that try to save time and space even more: Owicki-Gries, rely-guarantee, thread-modular model checking, multithreaded Cartesian abstraction, concurrent procedures specification, thread simplification, Cartesian abstraction refinement.

Alexander has obtained his Diploma degree from the University of Saarland, Germany, in 2004-2005, for a work on polyforms (in other terminilogy, bond animals) under the guidance of Prof. Dr. Raimund Seidel; during his studies Alexander was financed by the prominent foundation “Studienstiftung des deutschen Volkes”. He continued his studies in Saarbruecken and Freiburg, funded by the Max-Planck society and the DFG (German science foundation), obtaining his PhD thesis in 2010 at the University of Freiburg for a work on verification of multithreaded programs under guidance of Prof. Dr. Andreas Podelski. In April 2010, he joined IMDEA Software.'

Recording of the talk: Verification of multi-threaded programs


Jose F. Morales Caballero
Optimizing Compilation Techniques for Logic Programming

This lecture will discuss the techniques and principles for optimizing the execution of logic programs. We will cover the tuning and design of abstract machines, analysis based on abstract interpretation, optimization based on partial evaluation, generation of native code, and how all those techniques can be combined together for the purpose of resource-friendly computation.

Jose F. Morales joined IMDEA Software Institute as a postdoctoral researcher in November 2010, after receiving his Ph.D degree in Computer Science from the Technical University of Madrid (UPM), Spain. Previously, he held a teaching assistant position at the Universidad Complutense de Madrid, starting in 2005. Jose's work to date has focused on mechanisms for the efficient execution of logic programs.'

Recording of the talk: Optimizing Compilation Techniques for Logic Programming


Manuel Carro Liñares
Tabled Logic Programming and Applications

Tabled Logic Programming, also known simply as "tabling", is a strategy for the evaluation of logic programs. As an alternative to the better-known SLD resolution, it provides an operational semantics which is closer to the declarative one by enhancing termination properties and, as a side-effect, improving performance. This leads to writing programs which are, in some cases, clearer, shorter, and more efficient than their Prolog counterparts. Additionally, tabling implementations can be used to execute programs featuring stratified negation and programs under the well-founded semantics. In this talk we will introduce tabling and its applications by means of examples, and we will devote some time to scratch on the surface of what making a tabling implementation entails.

Manuel Carro is an associate professor at the Computer Science School of the UPM and Deputy Director of the IMDEA Software Institute. He obtained his PhD at the UPM, and his research interests include declarative languages (especially logic and constraint-based ones), their implementation and analysis, parallelism, concurrency, visualization, and service-oriented computing. He has served as PC member in many conferences and publishind more than 60 papers in national and international conferences and journals.'

Recording of the talk: Tabled Logic Programming and Applications


PROGRAM

Monday 19

[9:00-10:45 9:00-10:45] Ricardo Peña: Static Analysis and Certification of Safety Properties of Memory Usage

Break

[11:15-13:00 11:15-13:00] Elvira Albert: Test Case Generation and Cost Analysis in Java-like Languages

Lunch

[14:30-16:15 14:30-16:15] Jose Francisco Morales: Optimizing Compilation Techniques for Logic Programming

Break

[16:45-18:30 16:45-18:30] Manuel Carro Liñares: Tabled Logic Programming and Applications


Tuesday 20

[9:00-10:45 9:00-10:45] Alexander Malkis: Modular verification of threads

Break

[11:15-13:00 11:15-13:00] David de Frutos: Semantics of Concurrent Processes: Unification and new Directions

Lunch

[14:30-16:15 14:30-16:15] Lars-Åke Fredlund: Erlang and the McErlang model checker

Break

[16:45-18:30 16:45-18:30] Julio Mariño: Modeling and verification of concurrent systems using shared resources


Wednesday 21

[9:00-10:45 9:00-10:45] Boris Köpf: Quantitative Information-Flow Analysis

Break

[11:15-13:00 11:15-13:00] César Kunz: Relational Verification Using Product Programs

Lunch

[14:30-16:15 14:30-16:15] Rafael Caballero: Declarative Debugging

Break

[16:45-18:30 16:45-18:30] Fernando Sáenz: Deductive Databases