Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Environmental impact assessment of the School of Engineering and Architecture (Lazzaretto) - A pathway towards LEED certification

The current work has for object the improvement and the maintenance of the School of Engineering and Architecture in Via Terracini 28 (Bologna), with the prospective to maximize the operative efficiency reducing to the minimum the environmental impact and the costs. In order to realize this work the LEED certification has been used. LEED (Leadership in Energy and Environmental Design) is a certification system of the buildings. It was born in United States by the U.S. Green Building Council (USGBC)

Night Vision Imaging System (NVIS) certification requirements analysis of an Airbus Helicopters H135

The safe operation of nighttime flight missions would be enhanced using Night Vision Imaging Systems (NVIS) equipment. This has been clear to the military since 1970s and to the civil helicopters since 1990s. In these last months, even Italian Emergency Medical Service (EMS) operators require Night Vision Goggles (NVG) devices that therefore amplify the ambient light. In order to fly with this technology, helicopters have to be NVIS-approved. The author have supported a company, to quantify the potentiality of undertaking the certification activity, through a feasibility study. Even before, NVG description and working principles have been done, then specifications analysis about the processes to make a helicopter NVIS-approved has been addressed. The noteworthy difference between military specifications and the civilian ones highlights non-irrevelant lacks in the latter. The activity of NVIS certification could be a good investment because the following targets have been achieved: Reductions of the certification cost, of the operating time and of the number of non-compliance.

Carbon stocks, tree diversity, and the role of organic certification in different cocoa production systems in Alto Beni, Bolivia

This study compares aboveground and belowground carbon stocks and tree diversity in different cocoa cultivation systems in Bolivia: monoculture, simple agroforestry, and successional agroforestry, as well as fallow as a control. Since diversified, agroforestry-based cultivation systems are often considered important for sustainable development, we also evaluated the links between carbon stocks and tree diversity, as well as the role of organic certification in transitioning from monoculture to agroforestry. Biomass, tree diversity, and soil physiochemical parameters were sampled in 15 plots measuring 48 × 48 m. Semi-structured interviews with 52 cocoa farmers were used to evaluate the role of organic certification and farmers’ organizations (e.g., cocoa cooperatives) in promoting tree diversity. Total carbon stocks in simple agroforestry systems (128.4 ± 20 Mg ha−1) were similar to those on fallow plots (125.2 ± 10 Mg ha−1). Successional agroforestry systems had the highest carbon stocks (143.7 ± 5.3 Mg ha−1). Monocultures stored significantly less carbon than all other systems (86.3 ± 4.0 Mg ha−1, posterior probability P(Diff > 0) of 0.000–0.006). Among shade tree species, Schizolobium amazonicum, Centrolobium ochroxylum, and Anadenanthera sp. accumulated the most biomass. High-value timber species (S. amazonicum, C. ochroxylum, Amburana cearensis, and Swietenia macrophylla) accounted for 22.0 % of shade tree biomass. The Shannon index and tree species richness were highest in successional agroforestry systems. Cocoa plots on certified organic farms displayed significantly higher tree species richness than plots on non-certified farms. Thus, expanding the coverage of organic farmers’ organizations may be an effective strategy for fostering transitions from monoculture to agroforestry systems.

Territorial quality and sustainable development : Indicators of performance in the context of a model for participatory rural tourism certification

El turismo rural ha sido incorporado por pequeños establecimientos agropecuarios del partido de Cnel. Suárez, provincia de Buenos Aires, Argentina, como actividad alternativa para mejorar la calidad de vida de sus miembros y superar situaciones de crisis agravadas por la marginalidad productiva del SO bonaerense, región a la que pertenecen. Bajo el programa Cambio Rural del INTA (Instituto Nacional de Tecnología Agropecuaria) conforman el Grupo 'Cortaderas II', junto a otros emprendedores interesados en valorar el medio rural. Han avanzado en el proceso de reconocimiento de su identidad y puesta en valor de recursos específicos con anclaje en el territorio. Esta identidad comienza a apreciarse internamente, a raíz de la dinámica grupal lograda y la incipiente articulación con otros actores para la construcción de un partenariado público y privado que genere sinergias y contribuya al desarrollo sustentable del territorio. Sin embargo, aún no es claramente percibida por el turista, cada vez más exigente. Por lo tanto, el presente trabajo persigue proponer indicadores para evaluar el desempeño de un Sistema de Gestión de Calidad con enfoque territorial que, adaptando el modelo europeo 'Marca de Calidad Territorial', sustente una estrategia comercial de diferenciación del servicio y simultáneamente, mida el progreso hacia una mejor calidad de vida y fortalecimiento de vínculos con la cultura local y el entorno físico-natural en el marco del desarrollo sustentable. La investigación se plantea para la micro escala, ya que se trata de un estudio de caso, relevándose información primaria mediante observación directa y entrevistas semi-estructuradas, complementada con información secundaria diagnóstica utilizada por INTA. Las características del grupo y su dinámica de funcionamiento bajo el programa Cambio Rural revelan que es posible adoptar un proceso de certificación participativa propuesto para cuatro pilares de la calidad: de Bienes y Servicios, Institucional, Social y Ambiental. El modelo se integra con indicadores de evaluación de desempeño, agrupados en áreas clave para cada una de las dimensiones de la sustentabilidad, que contemplan el paisaje y la gestión de los recursos naturales; el impacto económico de la actividad, la calidad de la oferta y satisfacción del turista; así como las relaciones sociales internas y los vínculos con otros actores del territorio. Principalmente se encontraron fortalezas en la búsqueda de partenariados y debilidades en aspectos de comunicación y promoción. Se considera que este sistema de herramientas de gestión sustentable permitiría superar las dificultades de una certificación individual, pudiendo aplicarse a emprendimientos con otra ubicación geográfica

Territorial quality and sustainable development : Indicators of performance in the context of a model for participatory rural tourism certification

El turismo rural ha sido incorporado por pequeños establecimientos agropecuarios del partido de Cnel. Suárez, provincia de Buenos Aires, Argentina, como actividad alternativa para mejorar la calidad de vida de sus miembros y superar situaciones de crisis agravadas por la marginalidad productiva del SO bonaerense, región a la que pertenecen. Bajo el programa Cambio Rural del INTA (Instituto Nacional de Tecnología Agropecuaria) conforman el Grupo 'Cortaderas II', junto a otros emprendedores interesados en valorar el medio rural. Han avanzado en el proceso de reconocimiento de su identidad y puesta en valor de recursos específicos con anclaje en el territorio. Esta identidad comienza a apreciarse internamente, a raíz de la dinámica grupal lograda y la incipiente articulación con otros actores para la construcción de un partenariado público y privado que genere sinergias y contribuya al desarrollo sustentable del territorio. Sin embargo, aún no es claramente percibida por el turista, cada vez más exigente. Por lo tanto, el presente trabajo persigue proponer indicadores para evaluar el desempeño de un Sistema de Gestión de Calidad con enfoque territorial que, adaptando el modelo europeo 'Marca de Calidad Territorial', sustente una estrategia comercial de diferenciación del servicio y simultáneamente, mida el progreso hacia una mejor calidad de vida y fortalecimiento de vínculos con la cultura local y el entorno físico-natural en el marco del desarrollo sustentable. La investigación se plantea para la micro escala, ya que se trata de un estudio de caso, relevándose información primaria mediante observación directa y entrevistas semi-estructuradas, complementada con información secundaria diagnóstica utilizada por INTA. Las características del grupo y su dinámica de funcionamiento bajo el programa Cambio Rural revelan que es posible adoptar un proceso de certificación participativa propuesto para cuatro pilares de la calidad: de Bienes y Servicios, Institucional, Social y Ambiental. El modelo se integra con indicadores de evaluación de desempeño, agrupados en áreas clave para cada una de las dimensiones de la sustentabilidad, que contemplan el paisaje y la gestión de los recursos naturales; el impacto económico de la actividad, la calidad de la oferta y satisfacción del turista; así como las relaciones sociales internas y los vínculos con otros actores del territorio. Principalmente se encontraron fortalezas en la búsqueda de partenariados y debilidades en aspectos de comunicación y promoción. Se considera que este sistema de herramientas de gestión sustentable permitiría superar las dificultades de una certificación individual, pudiendo aplicarse a emprendimientos con otra ubicación geográfica

Territorial quality and sustainable development : Indicators of performance in the context of a model for participatory rural tourism certification

El turismo rural ha sido incorporado por pequeños establecimientos agropecuarios del partido de Cnel. Suárez, provincia de Buenos Aires, Argentina, como actividad alternativa para mejorar la calidad de vida de sus miembros y superar situaciones de crisis agravadas por la marginalidad productiva del SO bonaerense, región a la que pertenecen. Bajo el programa Cambio Rural del INTA (Instituto Nacional de Tecnología Agropecuaria) conforman el Grupo 'Cortaderas II', junto a otros emprendedores interesados en valorar el medio rural. Han avanzado en el proceso de reconocimiento de su identidad y puesta en valor de recursos específicos con anclaje en el territorio. Esta identidad comienza a apreciarse internamente, a raíz de la dinámica grupal lograda y la incipiente articulación con otros actores para la construcción de un partenariado público y privado que genere sinergias y contribuya al desarrollo sustentable del territorio. Sin embargo, aún no es claramente percibida por el turista, cada vez más exigente. Por lo tanto, el presente trabajo persigue proponer indicadores para evaluar el desempeño de un Sistema de Gestión de Calidad con enfoque territorial que, adaptando el modelo europeo 'Marca de Calidad Territorial', sustente una estrategia comercial de diferenciación del servicio y simultáneamente, mida el progreso hacia una mejor calidad de vida y fortalecimiento de vínculos con la cultura local y el entorno físico-natural en el marco del desarrollo sustentable. La investigación se plantea para la micro escala, ya que se trata de un estudio de caso, relevándose información primaria mediante observación directa y entrevistas semi-estructuradas, complementada con información secundaria diagnóstica utilizada por INTA. Las características del grupo y su dinámica de funcionamiento bajo el programa Cambio Rural revelan que es posible adoptar un proceso de certificación participativa propuesto para cuatro pilares de la calidad: de Bienes y Servicios, Institucional, Social y Ambiental. El modelo se integra con indicadores de evaluación de desempeño, agrupados en áreas clave para cada una de las dimensiones de la sustentabilidad, que contemplan el paisaje y la gestión de los recursos naturales; el impacto económico de la actividad, la calidad de la oferta y satisfacción del turista; así como las relaciones sociales internas y los vínculos con otros actores del territorio. Principalmente se encontraron fortalezas en la búsqueda de partenariados y debilidades en aspectos de comunicación y promoción. Se considera que este sistema de herramientas de gestión sustentable permitiría superar las dificultades de una certificación individual, pudiendo aplicarse a emprendimientos con otra ubicación geográfica

The Effect That Project Management Certification Has on Employability: Agent's Perceptions from Spain

This study analyses the effects that the project management certification has on employability. This analysis started with a participative process in which various groups of experts who are involved in the certification of people were consulted. A personal interview was carried out amongst 106 professionals —certifying bodies, training institutions, the civil service, and international organisations— and amongst professional who are certified in project management by the International Project Management Association in Spain. The results show that the certification emerges as a powerful tool for improving employability. The effects are demonstrated across two complementary aspects: internal company aspects and external aspects relating to the labour market. Finally, by compiling the different agents’ opinions, a series of measures emerge for improving the accreditation processes as an employability tool and increasing the mutual learning between public and private actors.

Application of virtual certification techniques to vehicle design and track maintenance

Virtual certification partially substitutes by computer simulations the experimental techniques required for rail vehicle certification. In this paper, several works were these techniques were used in the vehicle design and track maintenance processes are presented. Dynamic simulation of multibody systems was used to virtually apply the EN14363 standard to certify the dynamic behaviour of vehicles. The works described are: assessment of a freight bogie design adapted to meter-gauge, assessment of a railway track layout for a subway network, freight bogie design with higher speed and axle load, and processing of the data acquired by a track recording vehicle for track maintenance.

Experiments in abstract interpretation-based code certification for pervasive systems

Proof carrying code (PCC) is a general is originally a roof in ñrst-order logic of certain vermethodology for certifying that the execution of an un- ification onditions and the checking process involves trusted mobile code is safe. The baste idea is that the ensuring that the certifícate is indeed a valid ñrst-order code supplier attaches a certifícate to the mobile code proof. which the consumer checks in order to ensure that the The main practical difñculty of PCC techniques is in code is indeed safe. The potential benefit is that the generating safety certiñeates which at the same time: i) consumer's task is reduced from the level of proving to allow expressing interesting safety properties, ii) can be the level of checking. Recently, the abstract interpre- generated automatically and, iii) are easy and efficient tation techniques developed, in logic programming have to check. In [1], the abstract interpretation techniques been proposed as a basis for PCC. This extended ab- [5] developed in logic programming1 are proposed as stract reports on experiments which illustrate several is- a basis for PCC. They offer a number of advantages sues involved in abstract interpretation-based certifica- for dealing with the aforementioned issues. In particution. First, we describe the implementation of our sys- lar, the xpressiveness of existing abstract domains will tem in the context of CiaoPP: the preprocessor of the be implicitly available in abstract interpretation-based Ciao multi-paradigm programming system. Then, by code certification to deñne a wide range of safety propermeans of some experiments, we show how code certifi- ties. Furthermore, the approach inherits the automation catión is aided in the implementation of the framework. and inference power of the abstract interpretation en- Finally, we discuss the application of our method within gines used in (Constraint) Logic Programming, (C)LP. the área, of pervasive systems

Abstract interpretation-based mobile code certification

Current approaches to mobile code safety – inspired by the technique of Proof-Carrying Code (PCC) [4] – associate safety information (in the form of a certificate) to programs. The certificate (or proof) is created by the code supplier at compile time, and packaged along with the untrusted code. The consumer who receives the code+certificate package can then run a checker which, by a straightforward inspection of the code and the certificate, is able to verify the validity of the certificate and thus compliance with the safety policy. The main practical difficulty of PCC techniques is in generating safety certificates which at the same time: i) allow expressing interesting safety properties, ii) can be generated automatically and, iii) are easy and efficient to check.

Abstract Interpretation-based verification/certification in the ciaoPP system

CiaoPP is the abstract interpretation-based preprocessor of the Ciao multi-paradigm (Constraint) Logic Programming system. It uses modular, incremental abstract interpretation as a fundamental tool to obtain information about programs. In CiaoPP, the semantic approximations thus produced have been applied to perform high- and low-level optimizations during program compilation, including transformations such as múltiple abstract specialization, parallelization, partial evaluation, resource usage control, and program verification. More recently, novel and promising applications of such semantic approximations are being applied in the more general context of program development such as program verification. In this work, we describe our extensión of the system to incorpórate Abstraction-Carrying Code (ACC), a novel approach to mobile code safety. ACC follows the standard strategy of associating safety certificates to programs, originally proposed in Proof Carrying- Code. A distinguishing feature of ACC is that we use an abstraction (or abstract model) of the program computed by standard static analyzers as a certifícate. The validity of the abstraction on the consumer side is checked in a single-pass by a very efficient and specialized abstractinterpreter. We have implemented and benchmarked ACC within CiaoPP. The experimental results show that the checking phase is indeed faster than the proof generation phase, and that the sizes of certificates are reasonable. Moreover, the preprocessor is based on compile-time (and run-time) tools for the certification of CLP programs with resource consumption assurances.

Abstract interpretation-based code certification for pervasive systems: Preliminary experiments

Proof carrying code is a general methodology for certifying that the execution of an untrusted mobile code is safe, according to a predefined safety policy. The basic idea is that the code supplier attaches a certifícate (or proof) to the mobile code which, then, the consumer checks in order to ensure that the code is indeed safe. The potential benefit is that the consumer's task is reduced from the level of proving to the level of checking, a much simpler task. Recently, the abstract interpretation techniques developed in logic programming have been proposed as a basis for proof carrying code [1]. To this end, the certifícate is generated from an abstract interpretation-based proof of safety. Intuitively, the verification condition is extracted from a set of assertions guaranteeing safety and the answer table generated during the analysis. Given this information, it is relatively simple and fast to verify that the code does meet this proof and so its execution is safe. This extended abstract reports on experiments which illustrate several issues involved in abstract interpretation-based code certification. First, we describe the implementation of our system in the context of CiaoPP: the preprocessor of the Ciao multi-paradigm (constraint) logic programming system. Then, by means of some experiments, we show how code certification is aided in the implementation of the framework. Finally, we discuss the application of our method within the área of pervasive systems which may lack the necessary computing resources to verify safety on their own. We herein illustrate the relevance of the information inferred by existing cost analysis to control resource usage in this context. Moreover, since the (rather complex) analysis phase is replaced by a simpler, efficient checking process at the code consumer side, we believe that our abstract interpretation-based approach to proof-carrying code becomes practically applicable to this kind of systems.

Advanced Topics in Resource Analysis: Certification, Incrementality, Concurrency and Array-Sensitivity

El Análisis de Consumo de Recursos o Análisis de Coste trata de aproximar el coste de ejecutar un programa como una función dependiente de sus datos de entrada. A pesar de que existen trabajos previos a esta tesis doctoral que desarrollan potentes marcos para el análisis de coste de programas orientados a objetos, algunos aspectos avanzados, como la eficiencia, la precisión y la fiabilidad de los resultados, todavía deben ser estudiados en profundidad. Esta tesis aborda estos aspectos desde cuatro perspectivas diferentes: (1) Las estructuras de datos compartidas en la memoria del programa son una pesadilla para el análisis estático de programas. Trabajos recientes proponen una serie de condiciones de localidad para poder mantener de forma consistente información sobre los atributos de los objetos almacenados en memoria compartida, reemplazando éstos por variables locales no almacenadas en la memoria compartida. En esta tesis presentamos dos extensiones a estos trabajos: la primera es considerar, no sólo los accesos a los atributos, sino también los accesos a los elementos almacenados en arrays; la segunda se centra en los casos en los que las condiciones de localidad no se cumplen de forma incondicional, para lo cual, proponemos una técnica para encontrar las precondiciones necesarias para garantizar la consistencia de la información acerca de los datos almacenados en memoria. (2) El objetivo del análisis incremental es, dado un programa, los resultados de su análisis y una serie de cambios sobre el programa, obtener los nuevos resultados del análisis de la forma más eficiente posible, evitando reanalizar aquellos fragmentos de código que no se hayan visto afectados por los cambios. Los analizadores actuales todavía leen y analizan el programa completo de forma no incremental. Esta tesis presenta un análisis de coste incremental, que, dado un cambio en el programa, reconstruye la información sobre el coste del programa de todos los métodos afectados por el cambio de forma incremental. Para esto, proponemos (i) un algoritmo multi-dominio y de punto fijo que puede ser utilizado en todos los análisis globales necesarios para inferir el coste, y (ii) una novedosa forma de almacenar las expresiones de coste que nos permite reconstruir de forma incremental únicamente las funciones de coste de aquellos componentes afectados por el cambio. (3) Las garantías de coste obtenidas de forma automática por herramientas de análisis estático no son consideradas totalmente fiables salvo que la implementación de la herramienta o los resultados obtenidos sean verificados formalmente. Llevar a cabo el análisis de estas herramientas es una tarea titánica, ya que se trata de herramientas de gran tamaño y complejidad. En esta tesis nos centramos en el desarrollo de un marco formal para la verificación de las garantías de coste obtenidas por los analizadores en lugar de analizar las herramientas. Hemos implementado esta idea mediante la herramienta COSTA, un analizador de coste para programas Java y KeY, una herramienta de verificación de programas Java. De esta forma, COSTA genera las garantías de coste, mientras que KeY prueba la validez formal de los resultados obtenidos, generando de esta forma garantías de coste verificadas. (4) Hoy en día la concurrencia y los programas distribuidos son clave en el desarrollo de software. Los objetos concurrentes son un modelo de concurrencia asentado para el desarrollo de sistemas concurrentes. En este modelo, los objetos son las unidades de concurrencia y se comunican entre ellos mediante llamadas asíncronas a sus métodos. La distribución de las tareas sugiere que el análisis de coste debe inferir el coste de los diferentes componentes distribuidos por separado. En esta tesis proponemos un análisis de coste sensible a objetos que, utilizando los resultados obtenidos mediante un análisis de apunta-a, mantiene el coste de los diferentes componentes de forma independiente. Abstract Resource Analysis (a.k.a. Cost Analysis) tries to approximate the cost of executing programs as functions on their input data sizes and without actually having to execute the programs. While a powerful resource analysis framework on object-oriented programs existed before this thesis, advanced aspects to improve the efficiency, the accuracy and the reliability of the results of the analysis still need to be further investigated. This thesis tackles this need from the following four different perspectives. (1) Shared mutable data structures are the bane of formal reasoning and static analysis. Analyses which keep track of heap-allocated data are referred to as heap-sensitive. Recent work proposes locality conditions for soundly tracking field accesses by means of ghost non-heap allocated variables. In this thesis we present two extensions to this approach: the first extension is to consider arrays accesses (in addition to object fields), while the second extension focuses on handling cases for which the locality conditions cannot be proven unconditionally by finding aliasing preconditions under which tracking such heap locations is feasible. (2) The aim of incremental analysis is, given a program, its analysis results and a series of changes to the program, to obtain the new analysis results as efficiently as possible and, ideally, without having to (re-)analyze fragments of code that are not affected by the changes. During software development, programs are permanently modified but most analyzers still read and analyze the entire program at once in a non-incremental way. This thesis presents an incremental resource usage analysis which, after a change in the program is made, is able to reconstruct the upper-bounds of all affected methods in an incremental way. To this purpose, we propose (i) a multi-domain incremental fixed-point algorithm which can be used by all global analyses required to infer the cost, and (ii) a novel form of cost summaries that allows us to incrementally reconstruct only those components of cost functions affected by the change. (3) Resource guarantees that are automatically inferred by static analysis tools are generally not considered completely trustworthy, unless the tool implementation or the results are formally verified. Performing full-blown verification of such tools is a daunting task, since they are large and complex. In this thesis we focus on the development of a formal framework for the verification of the resource guarantees obtained by the analyzers, instead of verifying the tools. We have implemented this idea using COSTA, a state-of-the-art cost analyzer for Java programs and KeY, a state-of-the-art verification tool for Java source code. COSTA is able to derive upper-bounds of Java programs while KeY proves the validity of these bounds and provides a certificate. The main contribution of our work is to show that the proposed tools cooperation can be used for automatically producing verified resource guarantees. (4) Distribution and concurrency are today mainstream. Concurrent objects form a well established model for distributed concurrent systems. In this model, objects are the concurrency units that communicate via asynchronous method calls. Distribution suggests that analysis must infer the cost of the diverse distributed components separately. In this thesis we propose a novel object-sensitive cost analysis which, by using the results gathered by a points-to analysis, can keep the cost of the diverse distributed components separate.