Approximate Relational Reasoning for Probabilistic Programs

La seguridad verificada es una metodología para demostrar propiedades de seguridad de los sistemas informáticos que se destaca por las altas garantías de corrección que provee. Los sistemas informáticos se modelan como programas probabilísticos y para probar que verifican una determinada propiedad de seguridad se utilizan técnicas rigurosas basadas en modelos matemáticos de los programas. En particular, la seguridad verificada promueve el uso de demostradores de teoremas interactivos o automáticos para construir demostraciones completamente formales cuya corrección es certificada mecánicamente (por ordenador). La seguridad verificada demostró ser una técnica muy efectiva para razonar sobre diversas nociones de seguridad en el área de criptografía. Sin embargo, no ha podido cubrir un importante conjunto de nociones de seguridad “aproximada”. La característica distintiva de estas nociones de seguridad es que se expresan como una condición de “similitud” entre las distribuciones de salida de dos programas probabilísticos y esta similitud se cuantifica usando alguna noción de distancia entre distribuciones de probabilidad. Este conjunto incluye destacadas nociones de seguridad de diversas áreas como la minería de datos privados, el análisis de flujo de información y la criptografía. Ejemplos representativos de estas nociones de seguridad son la indiferenciabilidad, que permite reemplazar un componente idealizado de un sistema por una implementación concreta (sin alterar significativamente sus propiedades de seguridad), o la privacidad diferencial, una noción de privacidad que ha recibido mucha atención en los últimos años y tiene como objetivo evitar la publicación datos confidenciales en la minería de datos. La falta de técnicas rigurosas que permitan verificar formalmente este tipo de propiedades constituye un notable problema abierto que tiene que ser abordado. En esta tesis introducimos varias lógicas de programa quantitativas para razonar sobre esta clase de propiedades de seguridad. Nuestra principal contribución teórica es una versión quantitativa de una lógica de Hoare relacional para programas probabilísticos. Las pruebas de correción de estas lógicas son completamente formalizadas en el asistente de pruebas Coq. Desarrollamos, además, una herramienta para razonar sobre propiedades de programas a través de estas lógicas extendiendo CertiCrypt, un framework para verificar pruebas de criptografía en Coq. Confirmamos la efectividad y aplicabilidad de nuestra metodología construyendo pruebas certificadas por ordendor de varios sistemas cuyo análisis estaba fuera del alcance de la seguridad verificada. Esto incluye, entre otros, una meta-construcción para diseñar funciones de hash “seguras” sobre curvas elípticas y algoritmos diferencialmente privados para varios problemas de optimización combinatoria de la literatura reciente. ABSTRACT The verified security methodology is an emerging approach to build high assurance proofs about security properties of computer systems. Computer systems are modeled as probabilistic programs and one relies on rigorous program semantics techniques to prove that they comply with a given security goal. In particular, it advocates the use of interactive theorem provers or automated provers to build fully formal machine-checked versions of these security proofs. The verified security methodology has proved successful in modeling and reasoning about several standard security notions in the area of cryptography. However, it has fallen short of covering an important class of approximate, quantitative security notions. The distinguishing characteristic of this class of security notions is that they are stated as a “similarity” condition between the output distributions of two probabilistic programs, and this similarity is quantified using some notion of distance between probability distributions. This class comprises prominent security notions from multiple areas such as private data analysis, information flow analysis and cryptography. These include, for instance, indifferentiability, which enables securely replacing an idealized component of system with a concrete implementation, and differential privacy, a notion of privacy-preserving data mining that has received a great deal of attention in the last few years. The lack of rigorous techniques for verifying these properties is thus an important problem that needs to be addressed. In this dissertation we introduce several quantitative program logics to reason about this class of security notions. Our main theoretical contribution is, in particular, a quantitative variant of a full-fledged relational Hoare logic for probabilistic programs. The soundness of these logics is fully formalized in the Coq proof-assistant and tool support is also available through an extension of CertiCrypt, a framework to verify cryptographic proofs in Coq. We validate the applicability of our approach by building fully machine-checked proofs for several systems that were out of the reach of the verified security methodology. These comprise, among others, a construction to build “safe” hash functions into elliptic curves and differentially private algorithms for several combinatorial optimization problems from the recent literature.

Probabilistic analysis of water availability for agriculture and associated crop net margins.

Rising water demands are difficult to meet in many regions of the world. In consequence, under meteorological adverse conditions, big economic losses in agriculture can take place. This paper aims to analyze the variability of water shortage in an irrigation district and the effect on farmer?s income. A probabilistic analysis of water availability for agriculture in the irrigation district is performed, through a supply-system simulation approach, considering stochastically generated series of stream-flows. Net margins associated to crop production are as well estimated depending on final water allocations. Net margins are calculated considering either single-crop farming, either a polyculture system. In a polyculture system, crop distribution and water redistribution are calculated through an optimization approach using the General Algebraic Modeling System (GAMS) for several scenarios of irrigation water availability. Expected net margins are obtained by crop and for the optimal crop and water distribution. The maximum expected margins are obtained for the optimal crop combination, followed by the alfalfa monoculture, maize, rice, wheat and finally barley. Water is distributed as follows, from biggest to smallest allocation: rice, alfalfa, maize, wheat and barley.

Interpretation of the pressuremeter test using numerical models based on deformation tensor equations

The pressuremeter test in boreholes has proven itself as a useful tool in geotechnical explorations, especially comparing its results with those obtained from a mathematical model ruled by a soil representative constitutive equation. The numerical model shown in this paper is aimed to be the reference framework for the interpretation of this test. The model analyses variables such as: the type of response, the initial state, the drainage regime and the constitutive equations. It is a model of finite elements able to work with a mesh without deformation or one adapted to it.

Probabilistic reasoning with an enzyme-driven DNA device

We present a biomolecular probabilistic model driven by the action of a DNA toolbox made of a set of DNA templates and enzymes that is able to perform Bayesian inference. The model will take single-stranded DNA as input data, representing the presence or absence of a specific molecular signal (the evidence). The program logic uses different DNA templates and their relative concentration ratios to encode the prior probability of a disease and the conditional probability of a signal given the disease. When the input and program molecules interact, an enzyme-driven cascade of reactions (DNA polymerase extension, nicking and degradation) is triggered, producing a different pair of single-stranded DNA species. Once the system reaches equilibrium, the ratio between the output species will represent the application of Bayes? law: the conditional probability of the disease given the signal. In other words, a qualitative diagnosis plus a quantitative degree of belief in that diagno- sis. Thanks to the inherent amplification capability of this DNA toolbox, the resulting system will be able to to scale up (with longer cascades and thus more input signals) a Bayesian biosensor that we designed previously.

Reachability-based acyclicity analysis by Abstract Interpretation

In programming languages with dynamic use of memory, such as Java, knowing that a reference variable x points to an acyclic data structure is valuable for the analysis of termination and resource usage (e.g., execution time or memory consumption). For instance, this information guarantees that the depth of the data structure to which x points is greater than the depth of the data structure pointed to by x.f for any field f of x. This, in turn, allows bounding the number of iterations of a loop which traverses the structure by its depth, which is essential in order to prove the termination or infer the resource usage of the loop. The present paper provides an Abstract-Interpretation-based formalization of a static analysis for inferring acyclicity, which works on the reduced product of two abstract domains: reachability, which models the property that the location pointed to by a variable w can be reached by dereferencing another variable v (in this case, v is said to reach w); and cyclicity, modeling the property that v can point to a cyclic data structure. The analysis is proven to be sound and optimal with respect to the chosen abstraction.

A model of economic management of cultural heritage: the rehabilitation of fort christmas as an interpretation center of defensive architecture of the Mediterranean in Cartagena (Spain)

The Cultural Heritage constitutes a way to generate social identities and play an important role in the development of the Spanish Mediterranean cities that opt to sustainable quality tourism. The reflection on the necessity of intervention on this heritage, in addition to establishing what should be done, brings up the need to define the reasons for taking action, why and what-for. These decisions are essential to establish if its maintenance and recovery are economically sustainable. The Project "Cartagena Port of Cultures", with support from the European Union, is an example of effective instrument for ensuring the sustainability of our built heritage conservation. Its main objective was to enable sustainable development of tourism in Cartagena based on sustainability and seasonality. This was achieved through a process of recovery of heritage resources and their optimum promotion and marketing.

Probabilistic meta-analysis of risk from the exposure to Hg in artisanal gold mining communities in Colombia

Colombia is one of the largest per capita mercury polluters in the world as a consequence of its artisanal gold mining activities. The severity of this problem in terms of potential health effects was evaluated by means of a probabilistic risk assessment carried out in the twelve departments (or provinces) in Colombia with the largest gold production. The two exposure pathways included in the risk assessment were inhalation of elemental Hg vapors and ingestion of fish contaminated with methyl mercury. Exposure parameters for the adult population (especially rates of fish consumption) were obtained from nation-wide surveys and concentrations of Hg in air and of methyl-mercury in fish were gathered from previous scientific studies. Fish consumption varied between departments and ranged from 0 to 0.3 kg d?1. Average concentrations of total mercury in fish (70 data) ranged from 0.026 to 3.3 lg g?1. A total of 550 individual measurements of Hg in workshop air (ranging from menor queDL to 1 mg m?3) and 261 measurements of Hg in outdoor air (ranging from menor queDL to 0.652 mg m?3) were used to generate the probability distributions used as concentration terms in the calculation of risk. All but two of the distributions of Hazard Quotients (HQ) associated with ingestion of Hg-contaminated fish for the twelve regions evaluated presented median values higher than the threshold value of 1 and the 95th percentiles ranged from 4 to 90. In the case of exposure to Hg vapors, minimum values of HQ for the general population exceeded 1 in all the towns included in this study, and the HQs for miner-smelters burning the amalgam is two orders of magnitude higher, reaching values of 200 for the 95th percentile. Even acknowledging the conservative assumptions included in the risk assessment and the uncertainties associated with it, its results clearly reveal the exorbitant levels of risk endured not only by miner-smelters but also by the general population of artisanal gold mining communities in Colombia.

Probabilistic approach for longitudinal ventilation system design in fire situations

The main objective of ventilation systems in tunnels is to reach the highest possible safety level both in service and fire situation; being the fire one, the most relevant when designing the system. When designing a longitudinal ventilation system, the methodology to evaluate the capacity of the system is similar both in service and fire situation, with the exception of the chimney effect and the phenomena of thermal transfer which is responsible or the changes in the density of the air. When facing the dimensioning task for longitudinal ventilated tunnels, although similar methodologies are used in different countries, specific hypothesis (aerodynamic, thermal properties, traffic) even if discussed in the literature or current practice, are not usually detailed in the regulations or recommendations. The aim of this paper is to propose a probabilistic approach to the problem which would allow the designer, and the tunnel owner, to understand the uncertainty and sensibility adopted in the results and, eventually, identify possible ways of optimizing the ventilation solution to be adopted.

A dynamic, probabilistic model for city building

The problem of interdependence between housing and commuting in a city has been analysed within the framework of welfare economics. Uncertain changes overtime in the working population has been considered by means of a dynamic, probabilistic model. The characteristics of irreversibility and durability in city building have been explicitly dealt with. The ultimate objective is that the model after further development will be an auxiliary tool in city planning.

Probabilistic assessment of risk from the exposure to mercury in artisanal gold mining communities in Colombia

Colombia is one the largest per capita mercury polluters as a consequence of its artisanal gold mining operations, which are steadily increasing following the rising price of this metal. Compared to gravimetric separation methods and cyanidation, the concentration of gold using Hg amalgams presents several advantages: the process is less time-consuming and minimizes gold losses, and Hg is easily transported and inexpensive relative to the selling price of gold. Very often, mercury amalgamation is carried out on site by unprotected workers. During this operation large amounts of mercury are discharged to the environment and eventually reach the fresh water bodies in the vicinity where it is subjected to methylation. Additionally, as gold is released from the amalgam by heating on open charcoal furnaces in small workshops, mercury vapors are emitted and inhaled by the artisanal smelters and the general population

Resource usage analysis of logic programs via abstract interpretation using sized types

We present a novel general resource analysis for logic programs based on sized types. Sized types are representations that incorporate structural (shape) information and allow expressing both lower and upper bounds on the size of a set of terms and their subterms at any position and depth. They also allow relating the sizes of terms and subterms occurring at different argument positions in logic predicates. Using these sized types, the resource analysis can infer both lower and upper bounds on the resources used by all the procedures in a program as functions on input term (and subterm) sizes, overcoming limitations of existing resource analyses and enhancing their precision. Our new resource analysis has been developed within the abstract interpretation framework, as an extension of the sized types abstract domain, and has been integrated into the Ciao preprocessor, CiaoPP. The abstract domain operations are integrated with the setting up and solving of recurrence equations for inferring both size and resource usage functions. We show that the analysis is an improvement over the previous resource analysis present in CiaoPP and compares well in power to state of the art systems.

Center for Nature Interpretation II, Lanzarote (2012)

CENTER FOR NATURE INTERPRETATION II, LANZAROTE (2012). Texto en inglés y español

Center for Nature Interpretation, Lanzarote (2009)

A black plane. The place is an extraordinary landscape, black due to the ash of this volcanic island, the distant horizon and sea in the background to the west. A natural ring of hills surrounds a flat area that reaches to the sea, with a saltwater lake in the center, where the white salt mines were formed in the past century.

Integrated deterministic-probabilistic safety assessment methodologies

(ENG) IDPSA (Integrated Deterministic-Probabilistic Safety Assessment) is a family of methods which use tightly coupled probabilistic and deterministic approaches to address respective sources of uncertainties, enabling Risk informed decision making in a consistent manner. The starting point of the IDPSA framework is that safety justification must be based on the coupling of deterministic (consequences) and probabilistic (frequency) considerations to address the mutual interactions between stochastic disturbances (e.g. failures of the equipment, human actions, stochastic physical phenomena) and deterministic response of the plant (i.e. transients). This paper gives a general overview of some IDPSA methods as well as some possible applications to PWR safety analyses (SPA)DPSA (Metodologías Integradas de Análisis Determinista-Probabilista de Seguridad) es un conjunto de métodos que utilizan métodos probabilistas y deterministas estrechamente acoplados para abordar las respectivas fuentes de incertidumbre, permitiendo la toma de decisiones Informada por el Riesgo de forma consistente. El punto de inicio del marco IDPSA es que la justificación de seguridad debe estar basada en el acoplamiento entre consideraciones deterministas (consecuencias) y probabilistas (frecuencia) para abordar la interacción mutua entre perturbaciones estocásticas (como por ejemplo fallos de los equipos, acciones humanas, fenómenos físicos estocásticos) y la respuesta determinista de la planta (como por ejemplo los transitorios). Este artículo da una visión general de algunos métodos IDSPA así como posibles aplicaciones al análisis de seguridad de los PWR.

Nuances matter: How fossil woody remains changed the interpretation of the vegetation in Iberia

Ejemplos de cómo los macrorrestos ayudan a mejorar la interpretación del paisaje vegetal de la península Ibérica