Generación de Casos de Prueba en Programación Orientada a Objetos = Test Case Generation in Object-Oriented Programming

Las pruebas de software (Testing) son en la actualidad la técnica más utilizada para la validación y la evaluación de la calidad de un programa. El testing está integrado en todas las metodologías prácticas de desarrollo de software y juega un papel crucial en el éxito de cualquier proyecto de software. Desde las unidades de código más pequeñas a los componentes más complejos, su integración en un sistema de software y su despliegue a producción, todas las piezas de un producto de software deben ser probadas a fondo antes de que el producto de software pueda ser liberado a un entorno de producción. La mayor limitación del testing de software es que continúa siendo un conjunto de tareas manuales, representando una buena parte del coste total de desarrollo. En este escenario, la automatización resulta fundamental para aliviar estos altos costes. La generación automática de casos de pruebas (TCG, del inglés test case generation) es el proceso de generar automáticamente casos de prueba que logren un alto recubrimiento del programa. Entre la gran variedad de enfoques hacia la TCG, esta tesis se centra en un enfoque estructural de caja blanca, y más concretamente en una de las técnicas más utilizadas actualmente, la ejecución simbólica. En ejecución simbólica, el programa bajo pruebas es ejecutado con expresiones simbólicas como argumentos de entrada en lugar de valores concretos. Esta tesis se basa en un marco general para la generación automática de casos de prueba dirigido a programas imperativos orientados a objetos (Java, por ejemplo) y basado en programación lógica con restricciones (CLP, del inglés constraint logic programming). En este marco general, el programa imperativo bajo pruebas es primeramente traducido a un programa CLP equivalente, y luego dicho programa CLP es ejecutado simbólicamente utilizando los mecanismos de evaluación estándar de CLP, extendidos con operaciones especiales para el tratamiento de estructuras de datos dinámicas. Mejorar la escalabilidad y la eficiencia de la ejecución simbólica constituye un reto muy importante. Es bien sabido que la ejecución simbólica resulta impracticable debido al gran número de caminos de ejecución que deben ser explorados y a tamaño de las restricciones que se deben manipular. Además, la generación de casos de prueba mediante ejecución simbólica tiende a producir un número innecesariamente grande de casos de prueba cuando es aplicada a programas de tamaño medio o grande. Las contribuciones de esta tesis pueden ser resumidas como sigue. (1) Se desarrolla un enfoque composicional basado en CLP para la generación de casos de prueba, el cual busca aliviar el problema de la explosión de caminos interprocedimiento analizando de forma separada cada componente (p.ej. método) del programa bajo pruebas, almacenando los resultados y reutilizándolos incrementalmente hasta obtener resultados para el programa completo. También se ha desarrollado un enfoque composicional basado en especialización de programas (evaluación parcial) para la herramienta de ejecución simbólica Symbolic PathFinder (SPF). (2) Se propone una metodología para usar información del consumo de recursos del programa bajo pruebas para guiar la ejecución simbólica hacia aquellas partes del programa que satisfacen una determinada política de recursos, evitando la exploración de aquellas partes del programa que violan dicha política. (3) Se propone una metodología genérica para guiar la ejecución simbólica hacia las partes más interesantes del programa, la cual utiliza abstracciones como generadores de trazas para guiar la ejecución de acuerdo a criterios de selección estructurales. (4) Se propone un nuevo resolutor de restricciones, el cual maneja eficientemente restricciones sobre el uso de la memoria dinámica global (heap) durante ejecución simbólica, el cual mejora considerablemente el rendimiento de la técnica estándar utilizada para este propósito, la \lazy initialization". (5) Todas las técnicas propuestas han sido implementadas en el sistema PET (el enfoque composicional ha sido también implementado en la herramienta SPF). Mediante evaluación experimental se ha confirmado que todas ellas mejoran considerablemente la escalabilidad y eficiencia de la ejecución simbólica y la generación de casos de prueba. ABSTRACT Testing is nowadays the most used technique to validate software and assess its quality. It is integrated into all practical software development methodologies and plays a crucial role towards the success of any software project. From the smallest units of code to the most complex components and their integration into a software system and later deployment; all pieces of a software product must be tested thoroughly before a software product can be released. The main limitation of software testing is that it remains a mostly manual task, representing a large fraction of the total development cost. In this scenario, test automation is paramount to alleviate such high costs. Test case generation (TCG) is the process of automatically generating test inputs that achieve high coverage of the system under test. Among a wide variety of approaches to TCG, this thesis focuses on structural (white-box) TCG, where one of the most successful enabling techniques is symbolic execution. In symbolic execution, the program under test is executed with its input arguments being symbolic expressions rather than concrete values. This thesis relies on a previously developed constraint-based TCG framework for imperative object-oriented programs (e.g., Java), in which the imperative program under test is first translated into an equivalent constraint logic program, and then such translated program is symbolically executed by relying on standard evaluation mechanisms of Constraint Logic Programming (CLP), extended with special treatment for dynamically allocated data structures. Improving the scalability and efficiency of symbolic execution constitutes a major challenge. It is well known that symbolic execution quickly becomes impractical due to the large number of paths that must be explored and the size of the constraints that must be handled. Moreover, symbolic execution-based TCG tends to produce an unnecessarily large number of test cases when applied to medium or large programs. The contributions of this dissertation can be summarized as follows. (1) A compositional approach to CLP-based TCG is developed which overcomes the inter-procedural path explosion by separately analyzing each component (method) in a program under test, stowing the results as method summaries and incrementally reusing them to obtain whole-program results. A similar compositional strategy that relies on program specialization is also developed for the state-of-the-art symbolic execution tool Symbolic PathFinder (SPF). (2) Resource-driven TCG is proposed as a methodology to use resource consumption information to drive symbolic execution towards those parts of the program under test that comply with a user-provided resource policy, avoiding the exploration of those parts of the program that violate such policy. (3) A generic methodology to guide symbolic execution towards the most interesting parts of a program is proposed, which uses abstractions as oracles to steer symbolic execution through those parts of the program under test that interest the programmer/tester most. (4) A new heap-constraint solver is proposed, which efficiently handles heap-related constraints and aliasing of references during symbolic execution and greatly outperforms the state-of-the-art standard technique known as lazy initialization. (5) All techniques above have been implemented in the PET system (and some of them in the SPF tool). Experimental evaluation has confirmed that they considerably help towards a more scalable and efficient symbolic execution and TCG.

Advances in global instability computations: from incompressible to hypersonic flow

Esta tesis constituye un gran avance en el conocimiento del estudio y análisis de inestabilidades hidrodinámicas desde un punto de vista físico y teórico, como consecuencia de haber desarrollado innovadoras técnicas para la resolución computacional eficiente y precisa de la parte principal del espectro correspondiente a los problemas de autovalores (EVP) multidimensionales que gobiernan la inestabilidad de flujos con dos o tres direcciones espaciales inhomogéneas, denominados problemas de estabilidad global lineal. En el contexto del trabajo de desarrollo de herramientas computacionales presentado en la tesis, la discretización mediante métodos de diferencias finitas estables de alto orden de los EVP bidimensionales y tridimensionales que se derivan de las ecuaciones de Navier-Stokes linealizadas sobre flujos con dos o tres direcciones espaciales inhomogéneas, ha permitido una aceleración de cuatro órdenes de magnitud en su resolución. Esta mejora de eficiencia numérica se ha conseguido gracias al hecho de que usando estos esquemas de diferencias finitas, técnicas eficientes de resolución de problemas lineales son utilizables, explotando el alto nivel de dispersión o alto número de elementos nulos en las matrices involucradas en los problemas tratados. Como más notable consecuencia cabe destacar que la resolución de EVPs multidimensionales de inestabilidad global, que hasta la fecha necesitaban de superordenadores, se ha podido realizar en ordenadores de sobremesa. Además de la solución de problemas de estabilidad global lineal, el mencionado desarrollo numérico facilitó la extensión de las ecuaciones de estabilidad parabolizadas (PSE) lineales y no lineales para analizar la inestabilidad de flujos que dependen fuertemente en dos direcciones espaciales y suavemente en la tercera con las ecuaciones de estabilidad parabolizadas tridimensionales (PSE-3D). Precisamente la capacidad de extensión del novedoso algoritmo PSE-3D para el estudio de interacciones no lineales de los modos de estabilidad, desarrollado íntegramente en esta tesis, permite la predicción de transición en flujos complejos de gran interés industrial y por lo tanto extiende el concepto clásico de PSE, el cuál ha sido empleado exitosamente durante las pasadas tres décadas en el mismo contexto para problemas de capa límite bidimensional. Típicos ejemplos de flujos incompresibles se han analizado en este trabajo sin la necesidad de recurrir a restrictivas presuposiciones usadas en el pasado. Se han estudiado problemas vorticales como es el caso de un vórtice aislado o sistemas de vórtices simulando la estela de alas, en los que la homogeneidad axial no se impone y así se puede considerar la difusión viscosa del flujo. Además, se ha estudiado el chorro giratorio turbulento, cuya inestabilidad se utiliza para mejorar las características de funcionamiento de combustores. En la tesis se abarcan adicionalmente problemas de flujos compresibles. Se presenta el estudio de inestabilidad de flujos de borde de ataque a diferentes velocidades de vuelo. También se analiza la estela formada por un elemento rugoso aislado en capa límite supersónica e hipersónica, mostrando excelentes comparaciones con resultados obtenidos mediante simulación numérica directa. Finalmente, nuevas inestabilidades se han identificado en el flujo hipersónico a Mach 7 alrededor de un cono elíptico que modela el vehículo de pruebas en vuelo HIFiRE-5. Los resultados comparan favorablemente con experimentos en vuelo, lo que subraya aún más el potencial de las metodologías de análisis de estabilidad desarrolladas en esta tesis. ABSTRACT The present thesis constitutes a step forward in advancing the frontiers of knowledge of fluid flow instability from a physical point of view, as a consequence of having been successful in developing groundbreaking methodologies for the efficient and accurate computation of the leading part of the spectrum pertinent to multi-dimensional eigenvalue problems (EVP) governing instability of flows with two or three inhomogeneous spatial directions. In the context of the numerical work presented in this thesis, the discretization of the spatial operator resulting from linearization of the Navier-Stokes equations around flows with two or three inhomogeneous spatial directions by variable-high-order stable finite-difference methods has permitted a speedup of four orders of magnitude in the solution of the corresponding two- and three-dimensional EVPs. This improvement of numerical performance has been achieved thanks to the high-sparsity level offered by the high-order finite-difference schemes employed for the discretization of the operators. This permitted use of efficient sparse linear algebra techniques without sacrificing accuracy and, consequently, solutions being obtained on typical workstations, as opposed to the previously employed supercomputers. Besides solution of the two- and three-dimensional EVPs of global linear instability, this development paved the way for the extension of the (linear and nonlinear) Parabolized Stability Equations (PSE) to analyze instability of flows which depend in a strongly-coupled inhomogeneous manner on two spatial directions and weakly on the third. Precisely the extensibility of the novel PSE-3D algorithm developed in the framework of the present thesis to study nonlinear flow instability permits transition prediction in flows of industrial interest, thus extending the classic PSE concept which has been successfully employed in the same context to boundary-layer type of flows over the last three decades. Typical examples of incompressible flows, the instability of which was analyzed in the present thesis without the need to resort to the restrictive assumptions used in the past, range from isolated vortices, and systems thereof, in which axial homogeneity is relaxed to consider viscous diffusion, as well as turbulent swirling jets, the instability of which is exploited in order to improve flame-holding properties of combustors. The instability of compressible subsonic and supersonic leading edge flows has been solved, and the wake of an isolated roughness element in a supersonic and hypersonic boundary-layer has also been analyzed with respect to its instability: excellent agreement with direct numerical simulation results has been obtained in all cases. Finally, instability analysis of Mach number 7 ow around an elliptic cone modeling the HIFiRE-5 flight test vehicle has unraveled flow instabilities near the minor-axis centerline, results comparing favorably with flight test predictions.

Spatial linear global instability analysis of the HIFiRE-5 elliptic cone model flow

The linear instability of the three-dimensional boundary-layer over the HIFiRE-5 flight test geometry, i.e. a rounded-tip 2:1 elliptic cone, at Mach 7, has been analyzed through spatial BiGlobal analysis, in a effort to understand transition and accurately predict local heat loads on next-generation ight vehicles. The results at an intermediate axial section of the cone, Re x = 8x10 5, show three different families of spatially amplied linear global modes, the attachment-line and cross- ow modes known from earlier analyses, and a new global mode, peaking in the vicinity of the minor axis of the cone, termed \center-line mode". We discover that a sequence of symmetric and anti-symmetric centerline modes exist and, for the basic ow at hand, are maximally amplied around F* = 130kHz. The wavenumbers and spatial distribution of amplitude functions of the centerline modes are documented

Global research alliance modelling platform (GRAMP): an open web platform for modelling greenhouse gas emissions from agro-ecosystems

Carbon (C) and nitrogen (N) process-based models are important tools for estimating and reporting greenhouse gas emissions and changes in soil C stocks. There is a need for continuous evaluation, development and adaptation of these models to improve scientific understanding, national inventories and assessment of mitigation options across the world. To date, much of the information needed to describe different processes like transpiration, photosynthesis, plant growth and maintenance, above and below ground carbon dynamics, decomposition and nitrogen mineralization. In ecosystem models remains inaccessible to the wider community, being stored within model computer source code, or held internally by modelling teams. Here we describe the Global Research Alliance Modelling Platform (GRAMP), a web-based modelling platform to link researchers with appropriate datasets, models and training material. It will provide access to model source code and an interactive platform for researchers to form a consensus on existing methods, and to synthesize new ideas, which will help to advance progress in this area. The platform will eventually support a variety of models, but to trial the platform and test the architecture and functionality, it was piloted with variants of the DNDC model. The intention is to form a worldwide collaborative network (a virtual laboratory) via an interactive website with access to models and best practice guidelines; appropriate datasets for testing, calibrating and evaluating models; on-line tutorials and links to modelling and data provider research groups, and their associated publications. A graphical user interface has been designed to view the model development tree and access all of the above functions.

Global Stability Analysis of a Compressible Turbulent Flow around a High-Lift Configuration

The purpose of this work is to analyze a complex high lift configuration for which significant regions of separated flow are present. Current state of the art methods have some diffculty to predict the origin and the progression of this separated flow when increasing the angle of attack. The mechanisms responsible for the maximum lift limit on multi-element wing con?gurations are not clear; this stability analysis could help to understand the physics behind the phenomenon and to find a relation between the flow separation and the instability onset. The methodology presented herein consists in the computation of a steady base flow solution based on a finite volume discretization and a proposal of the solution for a generalized eigenvalue problem corresponding to the perturbed and linearized problem. The eigenvalue problem has been solved with the Arnoldi iterative method, one of the Krylov subspace projection methods. The described methodology was applied to the NACA0012 test case in subsonic and in transonic conditions and, finally, for the first time to the authors knowledge, on an industrial multi-component geometry, such as the A310 airfoil, in order to identify low frequency instabilities related to the separation. One important conclusion is that for all the analyzed geometries, one unstable mode related to flow separation appears for an angle of attack greater than the one correspondent to the maximum lift coe?cient condition. Finally, an adjoint study was carried out in order to evaluate the receptivity and the structural sensitivity of the geometries, giving an indication of the domain region that could be modified resulting in the biggest change of the flowfield.

Global Stability Analysis of Turbulent Transonic Flows on Airfoil geometries

La aparición de inestabilidades en un flujo es un problema importante que puede afectar a algunas aplicaciones aerodinámicas. De hecho existen diferentes tipos de fenómenos no-estacionarios que actualmente son tema de investigación; casos como la separación a altos ángulos de ataque o el buffet transónico son dos ejemplos de cierta relevancia. El análisis de estabilidad global permite identificar la aparición de dichas condiciones inestables, proporcionando información importante sobre la región donde la inestabilidad es dominante y sobre la frecuencia del fenómeno inestable. La metodología empleada es capaz de calcular un flujo base promediado mediante una discretización con volúmenes finitos y posteriormente la solución de un problema de autovalores asociado a la linealización que aparece al perturbar el flujo base. El cálculo numérico se puede dividir en tres pasos: primero se calcula una solución estacionaria para las ecuaciones RANS, luego se extrae la matriz del Jacobiano que representa el problema linealizado y finalmente se deriva y se resuelve el problema de autovalores generalizado mediante el método iterativo de Arnoldi. Como primer caso de validación, la técnica descrita ha sido aplicada a un cilindro circular en condiciones laminares para detectar el principio de las oscilaciones de los vórtices de von Karman, y se han comparado los resultados con experimentos y cálculos anteriores. La parte más importante del estudio se centra en el análisis de flujos compresibles en régimen turbulento. La predicción de la aparición y la progresión de flujo separado a altos ángulos de ataque se han estudiado en el perfil NACA0012 en condiciones tanto subsónicas como supersónicas y en una sección del ala del A310 en condiciones de despegue. Para todas las geometrías analizadas, se ha podido observar que la separación gradual genera la aparición de un modo inestable específico para altos ángulos de ataque siempre mayores que el ángulo asociado al máximo coeficiente de sustentación. Además, se ha estudiado el problema adjunto para obtener información sobre la zona donde una fuerza externa provoca el máximo cambio en el campo fluido. El estudio se ha completado calculando el mapa de sensibilidad estructural y localizando el centro de la inestabilidad. En el presente trabajo de tesis se ha analizado otro importante fenómeno: el buffet transónico. En condiciones transónicas, la interacción entre la onda de choque y la capa límite genera una oscilación de la posición de la onda de choque y, por consiguiente, de las fuerzas aerodinámicas. El conocimiento de las condiciones críticas y su origen puede ayudar a evitar la oscilación causada por estas fuerzas. Las condiciones para las cuales comienza la inestabilidad han sido calculadas y comparadas con trabajos anteriores. Por otra parte, los resultados del correspondiente problema adjunto y el mapa de sensibilidad se han obtenido por primera vez para el buffet, indicando la región del dominio que sera necesario modificar para crear el mayor cambio en las propiedades del campo fluido. Dado el gran consumo de memoria requerido para los casos 3D, se ha realizado un estudio sobre la reducción del domino con la finalidad de reducirlo a la región donde está localizada la inestabilidad. La eficacia de dicha reducción de dominio ha sido evaluada investigando el cambio en la dimensión de la matriz del Jacobiano, no resultando muy eficiente en términos del consumo de memoria. Dado que el buffet es un problema en general tridimensional, el análisis TriGlobal de una geometría 3D podría considerarse el auténtico reto futuro. Como aproximación al problema, un primer estudio se ha realizado empleando una geometría tridimensional extruida del NACA00f2. El cálculo del flujo 3D y, por primera vez en casos tridimensionales compresibles y turbulentos, el análisis de estabilidad TriGlobal, se han llevado a cabo. La comparación de los resultados obtenidos con los resultados del anterior modelo 2D, ha permitido, primero, verificar la exactitud del cálculo 2D realizado anteriormente y también ha proporcionado una estimación del consumo de memoria requerido para el caso 3D. ABSTRACT Flow unsteadiness is an important problem in aerodynamic applications. In fact, there are several types of unsteady phenomena that are still at the cutting edge of research in the field; separation at high angles of attack and transonic buffet are two important examples. Global Stability Analysis can identify the unstable onset conditions, providing important information about the instability location in the domain and the frequency of the unstable phenomenon. The methodology computes a base flow averaged state based on a finite volume discretization and a solution for a generalized eigenvalue problem corresponding to the perturbed linearized equations. The numerical computation is then performed in three steps: first, a steady solution for the RANS equation is computed; second, the Jacobian matrix that represents the linearized problem is obtained; and finally, the generalized eigenvalue problem is derived and solved with an Arnoldi iterative method. As a first validation test, the technique has been applied on a laminar circular cylinder in order to detect the von Karman vortex shedding onset, comparing the results with experiments and with previous calculations. The main part of the study focusses on turbulent and compressible cases. The prediction of the origin and progression of separated flows at high angles of attack has been studied on the NACA0012 airfoil at subsonic and transonic conditions and for the A310 airfoil in take-off configuration. For all the analyzed geometries, it has been found that gradual separation generates the appearance of one specific unstable mode for angles of attack always greater than the ones related to the maximum lift coefficient. In addition, the adjoint problem has been studied to suggest the location of an external force that results in the largest change to the flow field. From the direct and the adjoint analysis the structural sensitivity map has been computed and the core of the instability has been located. The other important phenomenon analyzed in this work is the transonic buffet. In transonic conditions, the interaction between the shock wave and the boundary layer leads to an oscillation of the shock location and, consequently, of the aerodynamic forces. Knowing the critical operational conditions and its origin can be helpful in preventing such fluctuating forces. The instability onset has then been computed and compared with the literature. Moreover, results of the corresponding adjoint problem and a sensitivity map have been provided for the first time for the buffet problem, indicating the region that must be modified to create the biggest change in flow field properties. Because of the large memory consumption required when a 3D case is approached, a domain reduction study has been carried out with the aim of limiting the domain size to the region where the instability is located. The effectiveness of the domain reduction has been evaluated by investigating the change in the Jacobian matrix size, not being very efficient in terms of memory consumption. Since buffet is a three-dimensional problem, TriGlobal stability analysis can be seen as a future challenge. To approximate the problem, a first study has been carried out on an extruded three-dimensional geometry of the NACA0012 airfoil. The 3D flow computation and the TriGlobal stability analysis have been performed for the first time on a compressible and turbulent 3D case. The results have been compared with a 2D model, confirming that the buffet onset evaluated in the 2D case is well detected. Moreover, the computation has given an indication about the memory consumption for a 3D case.

Impacts of global change on iberian forest ecosystems inferred from the spanish national forest inventory = Impactos del cambio global en ecosistemas forestales ibéricos a partir del inventario forestal nacional

Los efectos del cambio global sobre los bosques son una de las grandes preocupaciones de la sociedad del siglo XXI. Algunas de sus posibles consecuencias como son los efectos en la producción, la sostenibilidad, la pérdida de biodiversidad o cambios en la distribución y ensamblaje de especies forestales pueden tener grandes repercusiones sociales, ecológicas y económicas. La detección y seguimiento de estos efectos constituyen uno de los retos a los que se enfrentan en la actualidad científicos y gestores forestales. En base a la comparación de series históricas del Inventario Forestal Nacional Español (IFN), esta tesis trata de arrojar luz sobre algunos de los impactos que los cambios socioeconómicos y ambientales de las últimas décadas han generado sobre nuestros bosques. En primer lugar, esta tesis presenta una innovadora metodología con base geoestadística que permite la comparación de diferentes ciclos de inventario sin importar los diferentes métodos de muestreo empleados en cada uno de ellos (Capítulo 3). Esta metodología permite analizar cambios en la dinámica y distribución espacial de especies forestales en diferentes gradientes geográficos. Mediante su aplicación, se constatarán y cuantificarán algunas de las primeras evidencias de cambio en la distribución altitudinal y latitudinal de diferentes especies forestales ibéricas, que junto al estudio de su dinámica poblacional y tasas demográficas, ayudarán a testar algunas hipótesis biogeográficas en un escenario de cambio global en zonas de especial vulnerabilidad (Capítulos 3, 4 y 5). Por último, mediante la comparación de ciclos de parcelas permanentes del IFN se ahondará en el conocimiento de la evolución en las últimas décadas de especies invasoras en los ecosistemas forestales del cuadrante noroccidental ibérico, uno de los más afectados por la invasión de esta flora (Capítulo 6). ABSTRACT The effects of global change on forests are one of the major concerns of the XXI century. Some of the potential impacts of global change on forest growth, productivity, biodiversity or changes in species assembly and spatial distribution may have great ecological and economic consequences. The detection and monitoring of these effects are some of the major challenges that scientists and forest managers face nowadays. Based on the comparison of historical series of the Spanish National Forest Inventory (NFI), this thesis tries to shed some light on some of the impacts driven by recent socio-economic and environmental changes on our forest ecosystems. Firstly, this thesis presents an innovative methodology based on geostatistical techniques that allows the comparison of different NFI cycles regardless of the different sampling methods used in each of them (Chapter 3). This methodology, in conjunction with other statistical techniques, allows to analyze changes in the spatial distribution and population dynamics of forest species along different geographic gradients. By its application, this thesis presents some of the first evidences of changes in species distribution along different geographical gradients in the Iberian Peninsula. The analysis of these findings, of species population dynamics and demographic rates will help to test some biogeographical hypothesis on forests under climate change scenarios in areas of particular vulnerability (Chapters 3, 4 and 5). Finally, by comparing NFI cycles with permanent plots, this thesis increases our knowledge about the patterns and processes associated with the recent evolution of invasive species in the forest ecosystems of North-western Iberia, one of the areas most affected by the invasion of allien species at national scale (Chapter 6).