Deriving a fixpoint computation algorithm for top-down abstract interpretation of logic programs

Bruynooghe described a framework for the top-down abstract interpretation of logic programs. In this framework, abstract interpretation is carried out by constructing an abstract and-or tree in a top-down fashion for a given query and program. Such an abstract interpreter requires fixpoint computation for programs which contain recursive predicates. This paper presents in detail a fixpoint algorithm that has been developed for this purpose and the motivation behind it. We start off by describing a simple-minded algorithm. After pointing out its shortcomings, we present a series of refinements to this algorithm, until we reach the final version. The aim is to give an intuitive grasp and provide justification for the relative complexity of the final algorithm. We also present an informal proof of correctness of the algorithm and some results obtained from an implementation.

Design and control of multi-finger haptic devices for dexterous manipulation

En la interacción con el entorno que nos rodea durante nuestra vida diaria (utilizar un cepillo de dientes, abrir puertas, utilizar el teléfono móvil, etc.) y en situaciones profesionales (intervenciones médicas, procesos de producción, etc.), típicamente realizamos manipulaciones avanzadas que incluyen la utilización de los dedos de ambas manos. De esta forma el desarrollo de métodos de interacción háptica multi-dedo dan lugar a interfaces hombre-máquina más naturales y realistas. No obstante, la mayoría de interfaces hápticas disponibles en el mercado están basadas en interacciones con un solo punto de contacto; esto puede ser suficiente para la exploración o palpación del entorno pero no permite la realización de tareas más avanzadas como agarres. En esta tesis, se investiga el diseño mecánico, control y aplicaciones de dispositivos hápticos modulares con capacidad de reflexión de fuerzas en los dedos índice, corazón y pulgar del usuario. El diseño mecánico de la interfaz diseñada, ha sido optimizado con funciones multi-objetivo para conseguir una baja inercia, un amplio espacio de trabajo, alta manipulabilidad y reflexión de fuerzas superiores a 3 N en el espacio de trabajo. El ancho de banda y la rigidez del dispositivo se han evaluado mediante simulación y experimentación real. Una de las áreas más importantes en el diseño de estos dispositivos es el efector final, ya que es la parte que está en contacto con el usuario. Durante este trabajo se ha diseñado un dedal de bajo peso, adaptable a diferentes usuarios que, mediante la incorporación de sensores de contacto, permite estimar fuerzas normales y tangenciales durante la interacción con entornos reales y virtuales. Para el diseño de la arquitectura de control, se estudiaron los principales requisitos para estos dispositivos. Entre estos, cabe destacar la adquisición, procesado e intercambio a través de internet de numerosas señales de control e instrumentación; la computación de equaciones matemáticas incluyendo la cinemática directa e inversa, jacobiana, algoritmos de detección de agarres, etc. Todos estos componentes deben calcularse en tiempo real garantizando una frecuencia mínima de 1 KHz. Además, se describen sistemas para manipulación de precisión virtual y remota; así como el diseño de un método denominado "desacoplo cinemático iterativo" para computar la cinemática inversa de robots y la comparación con otros métodos actuales. Para entender la importancia de la interacción multimodal, se ha llevado a cabo un estudio para comprobar qué estímulos sensoriales se correlacionan con tiempos de respuesta más rápidos y de mayor precisión. Estos experimentos se desarrollaron en colaboración con neurocientíficos del instituto Technion Israel Institute of Technology. Comparando los tiempos de respuesta en la interacción unimodal (auditiva, visual y háptica) con combinaciones bimodales y trimodales de los mismos, se demuestra que el movimiento sincronizado de los dedos para generar respuestas de agarre se basa principalmente en la percepción háptica. La ventaja en el tiempo de procesamiento de los estímulos hápticos, sugiere que los entornos virtuales que incluyen esta componente sensorial generan mejores contingencias motoras y mejoran la credibilidad de los eventos. Se concluye que, los sistemas que incluyen percepción háptica dotan a los usuarios de más tiempo en las etapas cognitivas para rellenar información de forma creativa y formar una experiencia más rica. Una aplicación interesante de los dispositivos hápticos es el diseño de nuevos simuladores que permitan entrenar habilidades manuales en el sector médico. En colaboración con fisioterapeutas de Griffith University en Australia, se desarrolló un simulador que permite realizar ejercicios de rehabilitación de la mano. Las propiedades de rigidez no lineales de la articulación metacarpofalange del dedo índice se estimaron mediante la utilización del efector final diseñado. Estos parámetros, se han implementado en un escenario que simula el comportamiento de la mano humana y que permite la interacción háptica a través de esta interfaz. Las aplicaciones potenciales de este simulador están relacionadas con entrenamiento y educación de estudiantes de fisioterapia. En esta tesis, se han desarrollado nuevos métodos que permiten el control simultáneo de robots y manos robóticas en la interacción con entornos reales. El espacio de trabajo alcanzable por el dispositivo háptico, se extiende mediante el cambio de modo de control automático entre posición y velocidad. Además, estos métodos permiten reconocer el gesto del usuario durante las primeras etapas de aproximación al objeto para su agarre. Mediante experimentos de manipulación avanzada de objetos con un manipulador y diferentes manos robóticas, se muestra que el tiempo en realizar una tarea se reduce y que el sistema permite la realización de la tarea con precisión. Este trabajo, es el resultado de una colaboración con investigadores de Harvard BioRobotics Laboratory. ABSTRACT When we interact with the environment in our daily life (using a toothbrush, opening doors, using cell-phones, etc.), or in professional situations (medical interventions, manufacturing processes, etc.) we typically perform dexterous manipulations that involve multiple fingers and palm for both hands. Therefore, multi-Finger haptic methods can provide a realistic and natural human-machine interface to enhance immersion when interacting with simulated or remote environments. Most commercial devices allow haptic interaction with only one contact point, which may be sufficient for some exploration or palpation tasks but are not enough to perform advanced object manipulations such as grasping. In this thesis, I investigate the mechanical design, control and applications of a modular haptic device that can provide force feedback to the index, thumb and middle fingers of the user. The designed mechanical device is optimized with a multi-objective design function to achieve a low inertia, a large workspace, manipulability, and force-feedback of up to 3 N within the workspace; the bandwidth and rigidity for the device is assessed through simulation and real experimentation. One of the most important areas when designing haptic devices is the end-effector, since it is in contact with the user. In this thesis the design and evaluation of a thimble-like, lightweight, user-adaptable, and cost-effective device that incorporates four contact force sensors is described. This design allows estimation of the forces applied by a user during manipulation of virtual and real objects. The design of a real-time, modular control architecture for multi-finger haptic interaction is described. Requirements for control of multi-finger haptic devices are explored. Moreover, a large number of signals have to be acquired, processed, sent over the network and mathematical computations such as device direct and inverse kinematics, jacobian, grasp detection algorithms, etc. have to be calculated in Real Time to assure the required high fidelity for the haptic interaction. The Hardware control architecture has different modules and consists of an FPGA for the low-level controller and a RT controller for managing all the complex calculations (jacobian, kinematics, etc.); this provides a compact and scalable solution for the required high computation capabilities assuring a correct frequency rate for the control loop of 1 kHz. A set-up for dexterous virtual and real manipulation is described. Moreover, a new algorithm named the iterative kinematic decoupling method was implemented to solve the inverse kinematics of a robotic manipulator. In order to understand the importance of multi-modal interaction including haptics, a subject study was carried out to look for sensory stimuli that correlate with fast response time and enhanced accuracy. This experiment was carried out in collaboration with neuro-scientists from Technion Israel Institute of Technology. By comparing the grasping response times in unimodal (auditory, visual, and haptic) events with the response times in events with bimodal and trimodal combinations. It is concluded that in grasping tasks the synchronized motion of the fingers to generate the grasping response relies on haptic cues. This processing-speed advantage of haptic cues suggests that multimodalhaptic virtual environments are superior in generating motor contingencies, enhancing the plausibility of events. Applications that include haptics provide users with more time at the cognitive stages to fill in missing information creatively and form a richer experience. A major application of haptic devices is the design of new simulators to train manual skills for the medical sector. In collaboration with physical therapists from Griffith University in Australia, we developed a simulator to allow hand rehabilitation manipulations. First, the non-linear stiffness properties of the metacarpophalangeal joint of the index finger were estimated by using the designed end-effector; these parameters are implemented in a scenario that simulates the behavior of the human hand and that allows haptic interaction through the designed haptic device. The potential application of this work is related to educational and medical training purposes. In this thesis, new methods to simultaneously control the position and orientation of a robotic manipulator and the grasp of a robotic hand when interacting with large real environments are studied. The reachable workspace is extended by automatically switching between rate and position control modes. Moreover, the human hand gesture is recognized by reading the relative movements of the index, thumb and middle fingers of the user during the early stages of the approximation-to-the-object phase and then mapped to the robotic hand actuators. These methods are validated to perform dexterous manipulation of objects with a robotic manipulator, and different robotic hands. This work is the result of a research collaboration with researchers from the Harvard BioRobotics Laboratory. The developed experiments show that the overall task time is reduced and that the developed methods allow for full dexterity and correct completion of dexterous manipulations.

Solution-processed organic devices developed by a novel cost-effective patterning technique based on electrical erosion

Application of arc erosion to the patterning of metallic contacts in organic devices is presented. A home-made systems and details of the working principles are described. Advantages and drawbacks of this novel technology are discussed.

Improving abstract interpretations by combining domains

This article considers static analysis based on abstract interpretation of logic programs over combined domains. It is known that analyses over combined domains provide more information potentially than obtained by the independent analyses. However, the construction of a combined analysis often requires redefining the basic operations for the combined domain. A practical approach to maintain precision in combined analyses of logic programs which reuses the individual analyses and does not redefine the basic operations is illustrated. The advantages of the approach are that proofs of correctness for the new domains are not required and implementations can be reused. The approach is demonstrated by showing that a combined sharing analysis — constructed from "old" proposals — compares well with other "new" proposals suggested in recent literature both from the point of view of efficiency and accuracy.

Estudio de la tolerancia al daño de los materiales y sistemas de pretensado

La mayoría de las estructuras de hormigón pretensadas construidas en los últimos 50 años han demostrado una excelente durabilidad cuando su construcción se realiza atendiendo las recomendaciones de un buen diseño así como una buena ejecución y puesta en obra de la estructura. Este hecho se debe en gran parte al temor que despierta el fenómeno de la corrosión bajo tensión típico de las armaduras de acero de alta resistencia. Menos atención se ha prestado a la susceptibilidad a la corrosión bajo tensión de los anclajes de postensado, posiblemente debido a que se han reportado pocos casos de fallos catastróficos. El concepto de Tolerancia al Daño y la Mecánica de la Fractura en estructuras de Ingeniería Civil ha empezado a incorporarse recientemente en algunas normas de diseño y cálculo de estructuras metálicas, sin embargo, aún está lejos de ser asimilado y empleado habitualmente por los ingenieros en sus cálculos cuando la ocasión lo requiere. Este desconocimiento de los aspectos relacionados con la Tolerancia al Daño genera importantes gastos de mantenimiento y reparación. En este trabajo se ha estudiado la aplicabilidad de los conceptos de la Mecánica de la Fractura a los componentes de los sistemas de postensado empleados en ingeniería civil, empleándolo para analizar la susceptibilidad de las armaduras activas frente a la corrosión bajo tensiones y a la pérdida de capacidad portante de las cabezas de anclajes de postensado debido a la presencia de defectos. Con este objeto se han combinado tanto técnicas experimentales como numéricas. Los defectos superficiales en los alambres de pretensado no se presentan de manera aislada si no que existe una cierta continuidad en la dirección axial así como un elevado número de defectos. Por este motivo se ha optado por un enfoque estadístico, que es más apropiado que el determinístico. El empleo de modelos estadísticos basados en la teoría de valores extremos ha permitido caracterizar el estado superficial en alambres de 5,2 mm de diámetro. Por otro lado la susceptibilidad del alambre frente a la corrosión bajo tensión ha sido evaluada mediante la realización de una campaña de ensayos de acuerdo con la actual normativa que ha permitido caracterizar estadísticamente su comportamiento. A la vista de los resultados ha sido posible evaluar como los parámetros que definen el estado superficial del alambre pueden determinar la durabilidad de la armadura atendiendo a su resistencia frente a la corrosión bajo tensión, evaluada mediante los ensayos que especifica la normativa. En el caso de las cabezas de anclaje de tendones de pretensado, los defectos se presentan de manera aislada y tienen su origen en marcas, arañazos o picaduras de corrosión que pueden producirse durante el proceso de fabricación, transporte, manipulación o puesta en obra. Dada la naturaleza de los defectos, el enfoque determinístico es más apropiado que el estadístico. La evaluación de la importancia de un defecto en un elemento estructural requiere la estimación de la solicitación local que genera el defecto, que permite conocer si el defecto es crítico o si puede llegar a serlo, si es que progresa con el tiempo (por fatiga, corrosión, una combinación de ambas, etc.). En este trabajo los defectos han sido idealizados como grietas, de manera que el análisis quedara del lado de la seguridad. La evaluación de la solicitación local del defecto ha sido calculada mediante el empleo de modelos de elementos finitos de la cabeza de anclaje que simulan las condiciones de trabajo reales de la cabeza de anclaje durante su vida útil. A partir de estos modelos numéricos se ha analizado la influencia en la carga de rotura del anclaje de diversos factores como la geometría del anclaje, las condiciones del apoyo, el material del anclaje, el tamaño del defecto su forma y su posición. Los resultados del análisis numérico han sido contrastados satisfactoriamente mediante la realización de una campaña experimental de modelos a escala de cabezas de anclaje de Polimetil-metacrilato en los que artificialmente se han introducido defectos de diversos tamaños y en distintas posiciones. ABSTRACT Most of the prestressed concrete structures built in the last 50 years have demonstrated an excellent durability when they are constructed in accordance with the rules of good design, detailing and execution. This is particularly true with respect to the feared stress corrosion cracking, which is typical of high strength prestressing steel wires. Less attention, however, has been paid to the stress corrosion cracking susceptibility of anchorages for steel tendons for prestressing concrete, probably due to the low number of reported failure cases. Damage tolerance and fracture mechanics concepts in civil engineering structures have recently started to be incorporated in some design and calculation rules for metallic structures, however it is still far from being assimilated and used by civil engineers in their calculations on a regular basis. This limited knowledge of the damage tolerance basis could lead to significant repair and maintenance costs. This work deals with the applicability of fracture mechanics and damage tolerance concepts to the components of prestressed systems, which are used in civil engineering. Such concepts have been applied to assess the susceptibility of the prestressing steel wires to stress corrosion cracking and the reduction of load bearing capability of anchorage devices due to the presence of defects. For this purpose a combination of experimental work and numerical techniques have been performed. Surface defects in prestressing steel wires are not shown alone, though a certain degree of continuity in the axial direction exist. A significant number of such defects is also observed. Hence a statistical approach was used, which is assumed to be more appropriate than the deterministic approach. The use of statistical methods based in extreme value theories has allowed the characterising of the surface condition of 5.2 mm-diameter wires. On the other hand the stress corrosion cracking susceptibility of the wire has been assessed by means of an experimental testing program in line with the current regulations, which has allowed statistical characterisasion of their performances against stress corrosion cracking. In the light of the test results, it has been possible to evaluate how the surface condition parameters could determine the durability of the active metal armour regarding to its resistance against stress corrosion cracking assessed by means of the current testing regulations. In the case of anchorage devices for steel tendons for prestressing concrete, the damage is presented as point defects originating from dents, scratches or corrosion pits that could be produced during the manufacturing proccess, transport, handling, assembly or use. Due to the nature of these defects, in this case the deterministic approach is more appropriate than the statistical approach. The assessment of the relevancy of defect in a structural component requires the computation of the stress intensity factors, which in turn allow the evaluation of whether the size defect is critical or could become critical with the progress of time (due to fatigue, corrosion or a combination of both effects). In this work the damage is idealised as tiny cracks, a conservative hypothesis. The stress intensity factors have been calculated by means of finite element models of the anchorage representing the real working conditions during its service life. These numeric models were used to assess the impact of some factors on the rupture load of the anchorage, such the anchorage geometry, material, support conditions, defect size, shape and its location. The results from the numerical analysis have been succesfully correlated against the results of the experimental testing program of scaled models of the anchorages in poly-methil methacrylate in which artificial damage in several sizes and locations were introduced.

Computation of nonlinear streaky structures in boundary layer flow

En esta tesis se integran numéricamente las ecuaciones reducidas de Navier Stokes (RNS), que describen el flujo en una capa límite tridimensional que presenta también una escala característica espacial corta en el sentido transversal. La formulación RNS se usa para el cálculo de “streaks” no lineales de amplitud finita, y los resultados conseguidos coinciden con los existentes en la literatura, obtenidos típicamente utilizando simulación numérica directa (DNS) o nonlinear parabolized stability equations (PSE). El cálculo de los “streaks” integrando las RNS es mucho menos costoso que usando DNS, y no presenta los problemas de estabilidad que aparecen en la formulación PSE cuando la amplitud del “streak” deja de ser pequeña. El código de integración RNS se utiliza también para el cálculo de los “streaks” que aparecen de manera natural en el borde de ataque de una placa plana en ausencia de perturbaciones en la corriente uniforme exterior. Los resultados existentes hasta ahora calculaban estos “streaks” únicamente en el límite lineal (amplitud pequeña), y en esta tesis se lleva a cabo el cálculo de los mismos en el régimen completamente no lineal (amplitud finita). En la segunda parte de la tesis se generaliza el código RNS para incluir la posibilidad de tener una placa no plana, con curvatura en el sentido transversal que varía lentamente en el sentido de la corriente. Esto se consigue aplicando un cambio de coordenadas, que transforma el dominio físico en uno rectangular. La formulación RNS se integra también expresada en las correspondientes coordenadas curvilíneas. Este código generalizado RNS se utiliza finalmente para estudiar el flujo de capa límite sobre una placa con surcos que varían lentamente en el sentido de la corriente, y es usado para simular el flujo sobre surcos que crecen en tal sentido. Abstract In this thesis, the reduced Navier Stokes (RNS) equations are numerically integrated. This formulation describes the flow in a three-dimensional boundary layer that also presents a short characteristic space scale in the spanwise direction. RNS equations are used to calculate nonlinear finite amplitude “streaks”, and the results agree with those reported in the literature, typically obtained using direct numerical simulation (DNS) or nonlinear parabolized stability equations (PSE). “Streaks” simulations through the RNS integration are much cheaper than using DNS, and avoid stability problems that appear in the PSE when the amplitude of the “streak” is not small. The RNS integration code is also used to calculate the “streaks” that naturally emerge at the leading edge of a flat plate boundary layer in the absence of any free stream perturbations. Up to now, the existing results for these “streaks” have been only calculated in the linear limit (small amplitude), and in this thesis their calculation is carried out in the fully nonlinear regime (finite amplitude). In the second part of the thesis, the RNS code is generalized to include the possibility of having a non-flat plate, curved in the spanwise direction and slowly varying in the streamwise direction. This is achieved by applying a change of coordinates, which transforms the physical domain into a rectangular one. The RNS formulation expressed in the corresponding curvilinear coordinates is also numerically integrated. This generalized RNS code is finally used to study the boundary layer flow over a plate with grooves which vary slowly in the streamwise direction; and this code is used to simulate the flow over grooves that grow in the streamwise direction.

Algoritmos de distribución de cargas de proceso en computación con membranas

Con el surgir de los problemas irresolubles de forma eficiente en tiempo polinomial en base al dato de entrada, surge la Computación Natural como alternativa a la computación clásica. En esta disciplina se trata de o bien utilizar la naturaleza como base de cómputo o bien, simular su comportamiento para obtener mejores soluciones a los problemas que los encontrados por la computación clásica. Dentro de la computación natural, y como una representación a nivel celular, surge la Computación con Membranas. La primera abstracción de las membranas que se encuentran en las células, da como resultado los P sistemas de transición. Estos sistemas, que podrían ser implementados en medios biológicos o electrónicos, son la base de estudio de esta Tesis. En primer lugar, se estudian las implementaciones que se han realizado, con el fin de centrarse en las implementaciones distribuidas, que son las que pueden aprovechar las características intrínsecas de paralelismo y no determinismo. Tras un correcto estudio del estado actual de las distintas etapas que engloban a la evolución del sistema, se concluye con que las distribuciones que buscan un equilibrio entre las dos etapas (aplicación y comunicación), son las que mejores resultados presentan. Para definir estas distribuciones, es necesario definir completamente el sistema, y cada una de las partes que influyen en su transición. Además de los trabajos de otros investigadores, y junto a ellos, se realizan variaciones a los proxies y arquitecturas de distribución, para tener completamente definidos el comportamiento dinámico de los P sistemas. A partir del conocimiento estático –configuración inicial– del P sistema, se pueden realizar distribuciones de membranas en los procesadores de un clúster para obtener buenos tiempos de evolución, con el fin de que la computación del P sistema sea realizada en el menor tiempo posible. Para realizar estas distribuciones, hay que tener presente las arquitecturas –o forma de conexión– de los procesadores del clúster. La existencia de 4 arquitecturas, hace que el proceso de distribución sea dependiente de la arquitectura a utilizar, y por tanto, aunque con significativas semejanzas, los algoritmos de distribución deben ser realizados también 4 veces. Aunque los propulsores de las arquitecturas han estudiado el tiempo óptimo de cada arquitectura, la inexistencia de distribuciones para estas arquitecturas ha llevado a que en esta Tesis se probaran las 4, hasta que sea posible determinar que en la práctica, ocurre lo mismo que en los estudios teóricos. Para realizar la distribución, no existe ningún algoritmo determinista que consiga una distribución que satisfaga las necesidades de la arquitectura para cualquier P sistema. Por ello, debido a la complejidad de dicho problema, se propone el uso de metaheurísticas de Computación Natural. En primer lugar, se propone utilizar Algoritmos Genéticos, ya que es posible realizar alguna distribución, y basada en la premisa de que con la evolución, los individuos mejoran, con la evolución de dichos algoritmos, las distribuciones también mejorarán obteniéndose tiempos cercanos al óptimo teórico. Para las arquitecturas que preservan la topología arbórea del P sistema, han sido necesarias realizar nuevas representaciones, y nuevos algoritmos de cruzamiento y mutación. A partir de un estudio más detallado de las membranas y las comunicaciones entre procesadores, se ha comprobado que los tiempos totales que se han utilizado para la distribución pueden ser mejorados e individualizados para cada membrana. Así, se han probado los mismos algoritmos, obteniendo otras distribuciones que mejoran los tiempos. De igual forma, se han planteado el uso de Optimización por Enjambres de Partículas y Evolución Gramatical con reescritura de gramáticas (variante de Evolución Gramatical que se presenta en esta Tesis), para resolver el mismo cometido, obteniendo otro tipo de distribuciones, y pudiendo realizar una comparativa de las arquitecturas. Por último, el uso de estimadores para el tiempo de aplicación y comunicación, y las variaciones en la topología de árbol de membranas que pueden producirse de forma no determinista con la evolución del P sistema, hace que se deba de monitorizar el mismo, y en caso necesario, realizar redistribuciones de membranas en procesadores, para seguir obteniendo tiempos de evolución razonables. Se explica, cómo, cuándo y dónde se deben realizar estas modificaciones y redistribuciones; y cómo es posible realizar este recálculo. Abstract Natural Computing is becoming a useful alternative to classical computational models since it its able to solve, in an efficient way, hard problems in polynomial time. This discipline is based on biological behaviour of living organisms, using nature as a basis of computation or simulating nature behaviour to obtain better solutions to problems solved by the classical computational models. Membrane Computing is a sub discipline of Natural Computing in which only the cellular representation and behaviour of nature is taken into account. Transition P Systems are the first abstract representation of membranes belonging to cells. These systems, which can be implemented in biological organisms or in electronic devices, are the main topic studied in this thesis. Implementations developed in this field so far have been studied, just to focus on distributed implementations. Such distributions are really important since they can exploit the intrinsic parallelism and non-determinism behaviour of living cells, only membranes in this case study. After a detailed survey of the current state of the art of membranes evolution and proposed algorithms, this work concludes that best results are obtained using an equal assignment of communication and rules application inside the Transition P System architecture. In order to define such optimal distribution, it is necessary to fully define the system, and each one of the elements that influence in its transition. Some changes have been made in the work of other authors: load distribution architectures, proxies definition, etc., in order to completely define the dynamic behaviour of the Transition P System. Starting from the static representation –initial configuration– of the Transition P System, distributions of membranes in several physical processors of a cluster is algorithmically done in order to get a better performance of evolution so that the computational complexity of the Transition P System is done in less time as possible. To build these distributions, the cluster architecture –or connection links– must be considered. The existence of 4 architectures, makes that the process of distribution depends on the chosen architecture, and therefore, although with significant similarities, the distribution algorithms must be implemented 4 times. Authors who proposed such architectures have studied the optimal time of each one. The non existence of membrane distributions for these architectures has led us to implement a dynamic distribution for the 4. Simulations performed in this work fix with the theoretical studies. There is not any deterministic algorithm that gets a distribution that meets the needs of the architecture for any Transition P System. Therefore, due to the complexity of the problem, the use of meta-heuristics of Natural Computing is proposed. First, Genetic Algorithm heuristic is proposed since it is possible to make a distribution based on the premise that along with evolution the individuals improve, and with the improvement of these individuals, also distributions enhance, obtaining complexity times close to theoretical optimum time. For architectures that preserve the tree topology of the Transition P System, it has been necessary to make new representations of individuals and new algorithms of crossover and mutation operations. From a more detailed study of the membranes and the communications among processors, it has been proof that the total time used for the distribution can be improved and individualized for each membrane. Thus, the same algorithms have been tested, obtaining other distributions that improve the complexity time. In the same way, using Particle Swarm Optimization and Grammatical Evolution by rewriting grammars (Grammatical Evolution variant presented in this thesis), to solve the same distribution task. New types of distributions have been obtained, and a comparison of such genetic and particle architectures has been done. Finally, the use of estimators for the time of rules application and communication, and variations in tree topology of membranes that can occur in a non-deterministic way with evolution of the Transition P System, has been done to monitor the system, and if necessary, perform a membrane redistribution on processors to obtain reasonable evolution time. How, when and where to make these changes and redistributions, and how it can perform this recalculation, is explained.

Adapting autonomously classification data mining algorithms for ubiquitous devices

Abstract Due to recent scientific and technological advances in information sys¬tems, it is now possible to perform almost every application on a mobile device. The need to make sense of such devices more intelligent opens an opportunity to design data mining algorithm that are able to autonomous execute in local devices to provide the device with knowledge. The problem behind autonomous mining deals with the proper configuration of the algorithm to produce the most appropriate results. Contextual information together with resource information of the device have a strong impact on both the feasibility of a particu¬lar execution and on the production of the proper patterns. On the other hand, performance of the algorithm expressed in terms of efficacy and efficiency highly depends on the features of the dataset to be analyzed together with values of the parameters of a particular implementation of an algorithm. However, few existing approaches deal with autonomous configuration of data mining algorithms and in any case they do not deal with contextual or resources information. Both issues are of particular significance, in particular for social net¬works application. In fact, the widespread use of social networks and consequently the amount of information shared have made the need of modeling context in social application a priority. Also the resource consumption has a crucial role in such platforms as the users are using social networks mainly on their mobile devices. This PhD thesis addresses the aforementioned open issues, focusing on i) Analyzing the behavior of algorithms, ii) mapping contextual and resources information to find the most appropriate configuration iii) applying the model for the case of a social recommender. Four main contributions are presented: - The EE-Model: is able to predict the behavior of a data mining algorithm in terms of resource consumed and accuracy of the mining model it will obtain. - The SC-Mapper: maps a situation defined by the context and resource state to a data mining configuration. - SOMAR: is a social activity (event and informal ongoings) recommender for mobile devices. - D-SOMAR: is an evolution of SOMAR which incorporates the configurator in order to provide updated recommendations. Finally, the experimental validation of the proposed contributions using synthetic and real datasets allows us to achieve the objectives and answer the research questions proposed for this dissertation.

Remarks on methods for the computation of boundary-element integrals by co-ordinate transformation

It is well known that the evaluation of the influence matrices in the boundary-element method requires the computation of singular integrals. Quadrature formulae exist which are especially tailored to the specific nature of the singularity, i.e. log(*- x0)9 Ijx- JC0), etc. Clearly the nodes and weights of these formulae vary with the location Xo of the singular point. A drawback of this approach is that a given problem usually includes different types of singularities, and therefore a general-purpose code would have to include many alternative formulae to cater for all possible cases. Recently, several authors1"3 have suggested a type independent alternative technique based on the combination of standard Gaussian rules with non-linear co-ordinate transformations. The transformation approach is particularly appealing in connection with the p.adaptive version, where the location of the collocation points varies at each step of the refinement process. The purpose of this paper is to analyse the technique in eference 3. We show that this technique is asymptotically correct as the number of Gauss points increases. However, the method possesses a 'hidden' source of error that is analysed and can easily be removed.

Ultra high frequency thin film saw devices

Durante los últimos años el flujo de datos en la transmisión que tiene lugar en los sistemas de comunicación ha aumentado considerablemente de forma que día a día se requieren más aplicaciones trabajando en un rango de frecuencias muy alto (3-30 GHz). Muchos de estos sistemas de comunicación incluyen dispositivos de onda acústica superficial (SAW) y por tanto se hace necesario el aumento de frecuencia a la que éstos trabajan. Pero este incremento de frecuencia de los dispositivos SAW no sólo es utilizado en los sistemas de comunicación, varios tipos de sensores, por ejemplo, aumentan su sensibilidad cuando la frecuencia a la que trabajan también lo hace. Tradicionalmente los dispositivos SAW se han fabricado sobre cuarzo, LiNbO3 y LiTaO3 principalmente. Sin embargo la principal limitación de estos materiales es su velocidad SAW. Además, debido a la alta temperatura a la que se depositan no pueden ser integrados en la tecnología de fabricación CMOS. El uso de la tecnología de capa delgada, en la que un material piezoeléctrico es depositado sobre un substrato, se está utilizando en las últimas décadas para incrementar la velocidad SAW de la estructura y poder obtener dispositivos trabajando en el rango de frecuencias requerido en la actualidad. Por otra parte, esta tecnología podría ser integrada en el proceso de fabricación CMOS. Durante esta tesis nos hemos centrado en la fabricación de dispositivos SAW trabajando a muy alta frecuencia. Para ello, utilizando la tecnología de capa delgada, hemos utilizado la estructura nitruro de aluminio (AlN) sobre diamante que permite conseguir velocidades SAW del sustrato que no se pueden alcanzar con otros materiales. El depósito de AlN se realizó mediante sputtering reactivo. Durante esta tesis se han realizado diferentes experimentos para optimizar dicho depósito de forma que se han obtenido los parámetros óptimos para los cuales se pueden obtener capas de AlN de alta calidad sobre cualquier tipo de sustrato. Además todo el proceso se realizó a baja temperatura para que el procesado de estos dispositivos pueda ser compatible con la tecnología CMOS. Una vez optimizada la estructura AlN/diamante, mediante litografía por haz de electrones se fabricaron resonadores SAW de tamaño nanométrico que sumado a la alta velocidad resultante de la combinación AlN/diamante nos ha permitido obtener dispositivos trabajando en el rango de 10-28 GHz con un alto factor de calidad y rechazo fuera de la banda. Estás frecuencias y prestaciones no han sido alcanzadas por el momento en resonadores de este tipo. Por otra parte, se han utilizado estos dispositivos para fabricar sensores de presión de alta sensibilidad. Estos dispositivos son afectados altamente por los cambios de temperatura. Se realizó también un exhaustivo estudio de cómo se comportan en temperatura estos resonadores, entre -250ºC y 250ºC (rango de temperaturas no estudiado hasta el momento) diferenciándose dos regiones una a muy baja temperatura en la que el dispositivo muestra un coeficiente de retraso en frecuencia (TCF) relativamente bajo y otra a partir de los -100ºC en la que el TCF es similar al observado en la bibliografía. Por tanto, durante esta tesis se ha optimizado el depósito de AlN sobre diamante para que sea compatible con la tecnología CMOS y permita el procesado de dispositivos trabajando a muy alta frecuencia con altas prestaciones para comunicaciones y sensores. ABSTRACT The increasing volume of information in data transmission systems results in a growing demand of applications working in the super-high-frequency band (3–30 GHz). Most of these systems work with surface acoustic wave (SAW) devices and thus there is a necessity of increasing their resonance frequency. Moreover, sensor application includes this kind of devices. The sensitivity of them is proportional with its frequency. Traditionally, quartz, LiNbO3 and LiTaO3 have been used in the fabrication of SAW devices. These materials suffer from a variety of limitations and in particular they have low SAW velocity as well as being incompatible with the CMOS technology. In order to overcome these problems, thin film technology, where a piezoelectric material is deposited on top of a substrate, has been used during the last decades. The piezoelectric/substrate structure allows to reach the frequencies required nowadays and could be compatible with the mass electronic production CMOS technology. This thesis work focuses on the fabrication of SAW devices working in the super-high-frequency range. Thin film technology has been used in order to get it, especially aluminum nitride (AlN) deposited by reactive sputtering on diamond has been used to increase the SAW velocity. Different experiments were carried out to optimize the parameters for the deposit of high quality AlN on any kind of substrates. In addition, the system was optimized under low temperature and thus this process is CMOS compatible. Once the AlN/diamond was optimized, thanks to the used e-beam lithography, nanometric SAW resonators were fabricated. The combination of the structure and the size of the devices allow the fabrication of devices working in the range of 10-28 GHz with a high quality factor and out of band rejection. These high performances and frequencies have not been reached so far for this kind of devices. Moreover, these devices have been used as high sensitivity pressure sensors. They are affected by temperature changes and thus a wide temperature range (-250ºC to 250ºC) study was done. From this study two regions were observed. At very low temperature, the temperature coefficient of frequency (TCF) is low. From -100ºC upwards the TCF is similar to the one appearing in the literature. Therefore, during this thesis work, the sputtering of AlN on diamond substrates was optimized for the CMOS compatible fabrication of high frequency and high performance SAW devices for communication and sensor application.

On a mathematical model arising in MHD perturbed equilibrium for Stellarator devices. A numerical approach.

Abstract?We consider a mathematical model related to the stationary regime of a plasma of fusion nuclear, magnetically confined in a Stellarator device. Using the geometric properties of the fusion device, a suitable system of coordinates and averaging methods, the mathematical problem may be reduced to a two dimensional free boundary problem of nonlocal type, where the corresponding differential equation is of the Grad?Shafranov type. The current balance within each flux magnetic gives us the possibility to define the third covariant magnetic field component with respect to the averaged poloidal flux function. We present here some numerical experiences and we give some numerical approach for the averaged poloidal flux and for the third covariant magnetic field component.

Photon Management Structures for Absorption Enhancement in Intermediate Band Solar Cells and Crystalline Silicon Solar Cells

El objetivo de la tesis es investigar los beneficios que el atrapamiento de la luz mediante fenómenos difractivos puede suponer para las células solares de silicio cristalino y las de banda intermedia. Ambos tipos de células adolecen de una insuficiente absorción de fotones en alguna región del espectro solar. Las células solares de banda intermedia son teóricamente capaces de alcanzar eficiencias mucho mayores que los dispositivos convencionales (con una sola banda energética prohibida), pero los prototipos actuales se resienten de una absorción muy débil de los fotones con energías menores que la banda prohibida. Del mismo modo, las células solares de silicio cristalino absorben débilmente en el infrarrojo cercano debido al carácter indirecto de su banda prohibida. Se ha prestado mucha atención a este problema durante las últimas décadas, de modo que todas las células solares de silicio cristalino comerciales incorporan alguna forma de atrapamiento de luz. Por razones de economía, en la industria se persigue el uso de obleas cada vez más delgadas, con lo que el atrapamiento de la luz adquiere más importancia. Por tanto aumenta el interés en las estructuras difractivas, ya que podrían suponer una mejora sobre el estado del arte. Se comienza desarrollando un método de cálculo con el que simular células solares equipadas con redes de difracción. En este método, la red de difracción se analiza en el ámbito de la óptica física, mediante análisis riguroso con ondas acopladas (rigorous coupled wave analysis), y el sustrato de la célula solar, ópticamente grueso, se analiza en los términos de la óptica geométrica. El método se ha implementado en ordenador y se ha visto que es eficiente y da resultados en buen acuerdo con métodos diferentes descritos por otros autores. Utilizando el formalismo matricial así derivado, se calcula el límite teórico superior para el aumento de la absorción en células solares mediante el uso de redes de difracción. Este límite se compara con el llamado límite lambertiano del atrapamiento de la luz y con el límite absoluto en sustratos gruesos. Se encuentra que las redes biperiódicas (con geometría hexagonal o rectangular) pueden producir un atrapamiento mucho mejor que las redes uniperiódicas. El límite superior depende mucho del periodo de la red. Para periodos grandes, las redes son en teoría capaces de alcanzar el máximo atrapamiento, pero sólo si las eficiencias de difracción tienen una forma peculiar que parece inalcanzable con las herramientas actuales de diseño. Para periodos similares a la longitud de onda de la luz incidente, las redes de difracción pueden proporcionar atrapamiento por debajo del máximo teórico pero por encima del límite Lambertiano, sin imponer requisitos irrealizables a la forma de las eficiencias de difracción y en un margen de longitudes de onda razonablemente amplio. El método de cálculo desarrollado se usa también para diseñar y optimizar redes de difracción para el atrapamiento de la luz en células solares. La red propuesta consiste en un red hexagonal de pozos cilíndricos excavados en la cara posterior del sustrato absorbente de la célula solar. La red se encapsula en una capa dieléctrica y se cubre con un espejo posterior. Se simula esta estructura para una célula solar de silicio y para una de banda intermedia y puntos cuánticos. Numéricamente, se determinan los valores óptimos del periodo de la red y de la profundidad y las dimensiones laterales de los pozos para ambos tipos de células. Los valores se explican utilizando conceptos físicos sencillos, lo que nos permite extraer conclusiones generales que se pueden aplicar a células de otras tecnologías. Las texturas con redes de difracción se fabrican en sustratos de silicio cristalino mediante litografía por nanoimpresión y ataque con iones reactivos. De los cálculos precedentes, se conoce el periodo óptimo de la red que se toma como una constante de diseño. Los sustratos se procesan para obtener estructuras precursoras de células solares sobre las que se realizan medidas ópticas. Las medidas de reflexión en función de la longitud de onda confirman que las redes cuadradas biperiódicas consiguen mejor atrapamiento que las uniperiódicas. Las estructuras fabricadas se simulan con la herramienta de cálculo descrita en los párrafos precedentes y se obtiene un buen acuerdo entre la medida y los resultados de la simulación. Ésta revela que una fracción significativa de los fotones incidentes son absorbidos en el reflector posterior de aluminio, y por tanto desaprovechados, y que este efecto empeora por la rugosidad del espejo. Se desarrolla un método alternativo para crear la capa dieléctrica que consigue que el reflector se deposite sobre una superficie plana, encontrándose que en las muestras preparadas de esta manera la absorción parásita en el espejo es menor. La siguiente tarea descrita en la tesis es el estudio de la absorción de fotones en puntos cuánticos semiconductores. Con la aproximación de masa efectiva, se calculan los niveles de energía de los estados confinados en puntos cuánticos de InAs/GaAs. Se emplea un método de una y de cuatro bandas para el cálculo de la función de onda de electrones y huecos, respectivamente; en el último caso se utiliza un hamiltoniano empírico. La regla de oro de Fermi permite obtener la intensidad de las transiciones ópticas entre los estados confinados. Se investiga el efecto de las dimensiones del punto cuántico en los niveles de energía y la intensidad de las transiciones y se obtiene que, al disminuir la anchura del punto cuántico respecto a su valor en los prototipos actuales, se puede conseguir una transición más intensa entre el nivel intermedio fundamental y la banda de conducción. Tomando como datos de partida los niveles de energía y las intensidades de las transiciones calculados como se ha explicado, se desarrolla un modelo de equilibrio o balance detallado realista para células solares de puntos cuánticos. Con el modelo se calculan las diferentes corrientes debidas a transiciones ópticas entre los numerosos niveles intermedios y las bandas de conducción y de valencia bajo ciertas condiciones. Se distingue de modelos de equilibrio detallado previos, usados para calcular límites de eficiencia, en que se adoptan suposiciones realistas sobre la absorción de fotones para cada transición. Con este modelo se reproducen datos publicados de eficiencias cuánticas experimentales a diferentes temperaturas con un acuerdo muy bueno. Se muestra que el conocido fenómeno del escape térmico de los puntos cuánticos es de naturaleza fotónica; se debe a los fotones térmicos, que inducen transiciones entre los estados excitados que se encuentran escalonados en energía entre el estado intermedio fundamental y la banda de conducción. En el capítulo final, este modelo realista de equilibrio detallado se combina con el método de simulación de redes de difracción para predecir el efecto que tendría incorporar una red de difracción en una célula solar de banda intermedia y puntos cuánticos. Se ha de optimizar cuidadosamente el periodo de la red para equilibrar el aumento de las diferentes transiciones intermedias, que tienen lugar en serie. Debido a que la absorción en los puntos cuánticos es extremadamente débil, se deduce que el atrapamiento de la luz, por sí solo, no es suficiente para conseguir corrientes apreciables a partir de fotones con energía menor que la banda prohibida en las células con puntos cuánticos. Se requiere una combinación del atrapamiento de la luz con un incremento de la densidad de puntos cuánticos. En el límite radiativo y sin atrapamiento de la luz, se necesitaría que el número de puntos cuánticos de una célula solar se multiplicara por 1000 para superar la eficiencia de una célula de referencia con una sola banda prohibida. En cambio, una célula con red de difracción precisaría un incremento del número de puntos en un factor 10 a 100, dependiendo del nivel de la absorción parásita en el reflector posterior. Abstract The purpose of this thesis is to investigate the benefits that diffractive light trapping can offer to quantum dot intermediate band solar cells and crystalline silicon solar cells. Both solar cell technologies suffer from incomplete photon absorption in some part of the solar spectrum. Quantum dot intermediate band solar cells are theoretically capable of achieving much higher efficiencies than conventional single-gap devices. Present prototypes suffer from extremely weak absorption of subbandgap photons in the quantum dots. This problem has received little attention so far, yet it is a serious barrier to the technology approaching its theoretical efficiency limit. Crystalline silicon solar cells absorb weakly in the near infrared due to their indirect bandgap. This problem has received much attention over recent decades, and all commercial crystalline silicon solar cells employ some form of light trapping. With the industry moving toward thinner and thinner wafers, light trapping is becoming of greater importance and diffractive structures may offer an improvement over the state-of-the-art. We begin by constructing a computational method with which to simulate solar cells equipped with diffraction grating textures. The method employs a wave-optical treatment of the diffraction grating, via rigorous coupled wave analysis, with a geometric-optical treatment of the thick solar cell bulk. These are combined using a steady-state matrix formalism. The method has been implemented computationally, and is found to be efficient and to give results in good agreement with alternative methods from other authors. The theoretical upper limit to absorption enhancement in solar cells using diffractions gratings is calculated using the matrix formalism derived in the previous task. This limit is compared to the so-called Lambertian limit for light trapping with isotropic scatterers, and to the absolute upper limit to light trapping in bulk absorbers. It is found that bi-periodic gratings (square or hexagonal geometry) are capable of offering much better light trapping than uni-periodic line gratings. The upper limit depends strongly on the grating period. For large periods, diffraction gratings are theoretically able to offer light trapping at the absolute upper limit, but only if the scattering efficiencies have a particular form, which is deemed to be beyond present design capabilities. For periods similar to the incident wavelength, diffraction gratings can offer light trapping below the absolute limit but above the Lambertian limit without placing unrealistic demands on the exact form of the scattering efficiencies. This is possible for a reasonably broad wavelength range. The computational method is used to design and optimise diffraction gratings for light trapping in solar cells. The proposed diffraction grating consists of a hexagonal lattice of cylindrical wells etched into the rear of the bulk solar cell absorber. This is encapsulated in a dielectric buffer layer, and capped with a rear reflector. Simulations are made of this grating profile applied to a crystalline silicon solar cell and to a quantum dot intermediate band solar cell. The grating period, well depth, and lateral well dimensions are optimised numerically for both solar cell types. This yields the optimum parameters to be used in fabrication of grating equipped solar cells. The optimum parameters are explained using simple physical concepts, allowing us to make more general statements that can be applied to other solar cell technologies. Diffraction grating textures are fabricated on crystalline silicon substrates using nano-imprint lithography and reactive ion etching. The optimum grating period from the previous task has been used as a design parameter. The substrates have been processed into solar cell precursors for optical measurements. Reflection spectroscopy measurements confirm that bi-periodic square gratings offer better absorption enhancement than uni-periodic line gratings. The fabricated structures have been simulated with the previously developed computation tool, with good agreement between measurement and simulation results. The simulations reveal that a significant amount of the incident photons are absorbed parasitically in the rear reflector, and that this is exacerbated by the non-planarity of the rear reflector. An alternative method of depositing the dielectric buffer layer was developed, which leaves a planar surface onto which the reflector is deposited. It was found that samples prepared in this way suffered less from parasitic reflector absorption. The next task described in the thesis is the study of photon absorption in semiconductor quantum dots. The bound-state energy levels of in InAs/GaAs quantum dots is calculated using the effective mass approximation. A one- and four- band method is applied to the calculation of electron and hole wavefunctions respectively, with an empirical Hamiltonian being employed in the latter case. The strength of optical transitions between the bound states is calculated using the Fermi golden rule. The effect of the quantum dot dimensions on the energy levels and transition strengths is investigated. It is found that a strong direct transition between the ground intermediate state and the conduction band can be promoted by decreasing the quantum dot width from its value in present prototypes. This has the added benefit of reducing the ladder of excited states between the ground state and the conduction band, which may help to reduce thermal escape of electrons from quantum dots: an undesirable phenomenon from the point of view of the open circuit voltage of an intermediate band solar cell. A realistic detailed balance model is developed for quantum dot solar cells, which uses as input the energy levels and transition strengths calculated in the previous task. The model calculates the transition currents between the many intermediate levels and the valence and conduction bands under a given set of conditions. It is distinct from previous idealised detailed balance models, which are used to calculate limiting efficiencies, since it makes realistic assumptions about photon absorption by each transition. The model is used to reproduce published experimental quantum efficiency results at different temperatures, with quite good agreement. The much-studied phenomenon of thermal escape from quantum dots is found to be photonic; it is due to thermal photons, which induce transitions between the ladder of excited states between the ground intermediate state and the conduction band. In the final chapter, the realistic detailed balance model is combined with the diffraction grating simulation method to predict the effect of incorporating a diffraction grating into a quantum dot intermediate band solar cell. Careful optimisation of the grating period is made to balance the enhancement given to the different intermediate transitions, which occur in series. Due to the extremely weak absorption in the quantum dots, it is found that light trapping alone is not sufficient to achieve high subbandgap currents in quantum dot solar cells. Instead, a combination of light trapping and increased quantum dot density is required. Within the radiative limit, a quantum dot solar cell with no light trapping requires a 1000 fold increase in the number of quantum dots to supersede the efficiency of a single-gap reference cell. A quantum dot solar cell equipped with a diffraction grating requires between a 10 and 100 fold increase in the number of quantum dots, depending on the level of parasitic absorption in the rear reflector.

Métodos acotados de aplicación de reglas de evolución para la implementación de Sistemas P de Transición

La característica fundamental de la Computación Natural se basa en el empleo de conceptos, principios y mecanismos del funcionamiento de la Naturaleza. La Computación Natural -y dentro de ésta, la Computación de Membranas- surge como una posible alternativa a la computación clásica y como resultado de la búsqueda de nuevos modelos de computación que puedan superar las limitaciones presentes en los modelos convencionales. En concreto, la Computación de Membranas se originó como un intento de formular un nuevo modelo computacional inspirado en la estructura y el funcionamiento de las células biológicas: los sistemas basados en este modelo constan de una estructura de membranas que actúan a la vez como separadores y como canales de comunicación, y dentro de esa estructura se alojan multiconjuntos de objetos que evolucionan de acuerdo a unas determinadas reglas de evolución. Al conjunto de dispositivos contemplados por la Computación de Membranas se les denomina genéricamente como Sistemas P. Hasta el momento los Sistemas P sólo han sido estudiados a nivel teórico y no han sido plenamente implementados ni en medios electrónicos, ni en medios bioquímicos, sólo han sido simulados o parcialmente implementados. Por tanto, la implantación de estos sistemas es un reto de investigación abierto. Esta tesis aborda uno de los problemas que debe ser resuelto para conseguir la implantación de los Sistemas P sobre plataformas hardware. El problema concreto se centra en el modelo de los Sistemas P de Transición y surge de la necesidad de disponer de algoritmos de aplicación de reglas que, independientemente de la plataforma hardware sobre la que se implementen, cumplan los requisitos de ser no deterministas, masivamente paralelos y además su tiempo de ejecución esté estáticamente acotado. Como resultado se ha obtenido un conjunto de algoritmos (tanto para plataformas secuenciales, como para plataformas paralelas) que se adecúan a las diferentes configuraciones de los Sistemas P. ABSTRACT The main feature of Natural Computing is the use of concepts, principles and mechanisms inspired by Nature. Natural Computing and within it, Membrane Computing emerges as an potential alternative to conventional computing and as from the search for new models of computation that may overcome the existing limitations in conventional models. Specifically, Membrane Computing was created to formulate a new computational paradigm inspired by the structure and functioning of biological cells: it consists of a membrane structure, which acts as separators as well as communication channels, and within this structure are stored multisets of objects that evolve according to certain evolution rules. The set of computing devices addressed by Membrane Computing are generically known P systems. Up to now, no P systems have been fully implemented yet in electronic or biochemical means. They only have been studied in theory, simulated or partially implemented. Therefore, the implementation of these systems is an open research challenge. This thesis addresses one of the problems to be solved in order to deploy P systems on hardware platforms. This specific problem is focused on the Transition P System model and emerges from the need of providing application rules algorithms that independently on the hardware platform on which they are implemented, meets the requirements of being nondeterministic, massively parallel and runtime-bounded. As a result, this thesis has developed a set of algorithms for both platforms, sequential and parallel, adapted to all possible configurations of P systems.

Análisis y diseño de un patrón de ruido térmico de 10 MHz a 26,5 GHz en tecnología coaxial

Esta Tesis Doctoral presenta las investigaciones y los trabajos desarrollados durante los años 2008 a 2012 para el análisis y diseño de un patrón primario de ruido térmico de banda ancha en tecnología coaxial. Para ubicar esta Tesis en su campo científico es necesario tomar conciencia de que la realización de mediciones fiables y trazables forma parte del sostenimiento del bienestar de una sociedad moderna y juega un papel crítico en apoyo de la competitividad económica, la fabricación y el comercio, así como de la calidad de vida. En el mundo moderno actual, una infraestructura de medición bien desarrollada genera confianza en muchas facetas de nuestra vida diaria, porque nos permite el desarrollo y fabricación de productos fiables, innovadores y de alta calidad; porque sustenta la competitividad de las industrias y su producción sostenible; además de contribuir a la eliminación de barreras técnicas y de dar soporte a un comercio justo, garantizar la seguridad y eficacia de la asistencia sanitaria, y por supuesto, dar respuesta a los grandes retos de la sociedad moderna en temas tan complicados como la energía y el medio ambiente. Con todo esto en mente se ha desarrollado un patrón primario de ruido térmico con el fin de aportar al sistema metrológico español un nuevo patrón primario de referencia capaz de ser usado para desarrollar mediciones fiables y trazables en el campo de la medida y calibración de dispositivos de ruido electromagnético de radiofrecuencia y microondas. Este patrón se ha planteado para que cumpla en el rango de 10 MHz a 26,5 GHz con las siguientes especificaciones: Salida nominal de temperatura de ruido aproximada de ~ 83 K. Incertidumbre de temperatura de ruido menor que ± 1 K en todo su rango de frecuencias. Coeficiente de reflexión en todo su ancho de banda de 0,01 a 26,5 GHz lo más bajo posible. Se ha divido esta Tesis Doctoral en tres partes claramente diferenciadas. La primera de ellas, que comprende los capítulos 1, 2, 3, 4 y 5, presenta todo el proceso de simulaciones y ajustes de los parámetros principales del dispositivo con el fin de dejar definidos los que resultan críticos en su construcción. A continuación viene una segunda parte compuesta por el capítulo 6 en donde se desarrollan los cálculos necesarios para obtener la temperatura de ruido a la salida del dispositivo. La tercera y última parte, capítulo 7, se dedica a la estimación de la incertidumbre de la temperatura de ruido del nuevo patrón primario de ruido obtenida en el capítulo anterior. Más concretamente tenemos que en el capítulo 1 se hace una exhaustiva introducción del entorno científico en donde se desarrolla este trabajo de investigación. Además se detallan los objetivos que se persiguen y se presenta la metodología utilizada para conseguirlos. El capítulo 2 describe la caracterización y selección del material dieléctrico para el anillo del interior de la línea de transmisión del patrón que ponga en contacto térmico los dos conductores del coaxial para igualar las temperaturas entre ambos y mantener la impedancia característica de todo el patrón primario de ruido. Además se estudian las propiedades dieléctricas del nitrógeno líquido para evaluar su influencia en la impedancia final de la línea de transmisión. En el capítulo 3 se analiza el comportamiento de dos cargas y una línea de aire comerciales trabajando en condiciones criogénicas. Se pretende con este estudio obtener la variación que se produce en el coeficiente de reflexión al pasar de temperatura ambiente a criogénica y comprobar si estos dispositivos resultan dañados por trabajar a temperaturas criogénicas; además se estudia si se modifica su comportamiento tras sucesivos ciclos de enfriamiento – calentamiento, obteniendo una cota de la variación para poder así seleccionar la carga que proporcione un menor coeficiente de reflexión y una menor variabilidad. En el capítulo 4 se parte del análisis de la estructura del anillo de material dieléctrico utilizada en la nota técnica NBS 1074 del NIST con el fin de obtener sus parámetros de dispersión que nos servirán para calcular el efecto que produce sobre el coeficiente de reflexión de la estructura coaxial completa. Además se realiza un estudio posterior con el fin de mejorar el diseño de la nota técnica NBS 1074 del NIST, donde se analiza el anillo de material dieléctrico, para posteriormente realizar modificaciones en la geometría de la zona donde se encuentra éste con el fin de reducir la reflexión que produce. Concretamente se estudia el ajuste del radio del conductor interior en la zona del anillo para que presente la misma impedancia característica que la línea. Y para finalizar se obtiene analíticamente la relación entre el radio del conductor interior y el radio de la transición de anillo térmico para garantizar en todo punto de esa transición la misma impedancia característica, manteniendo además criterios de robustez del dispositivo y de fabricación realistas. En el capítulo 5 se analiza el comportamiento térmico del patrón de ruido y su influencia en la conductividad de los materiales metálicos. Se plantean las posibilidades de que el nitrógeno líquido sea exterior a la línea o que éste penetre en su interior. En ambos casos, dada la simetría rotacional del problema, se ha simulado térmicamente una sección de la línea coaxial, es decir, se ha resuelto un problema bidimensional, aunque los resultados son aplicables a la estructura real tridimensional. Para la simulación térmica se ha empleado la herramienta PDE Toolbox de Matlab®. En el capítulo 6 se calcula la temperatura de ruido a la salida del dispositivo. Se parte del estudio de la aportación a la temperatura de ruido final de cada sección que compone el patrón. Además se estudia la influencia de las variaciones de determinados parámetros de los elementos que conforman el patrón de ruido sobre las características fundamentales de éste, esto es, el coeficiente de reflexión a lo largo de todo el dispositivo. Una vez descrito el patrón de ruido electromagnético se procede, en el capítulo 7, a describir los pasos seguidos para estimar la incertidumbre de la temperatura de ruido electromagnético a su salida. Para ello se utilizan dos métodos, el clásico de la guía para la estimación de la incertidumbre [GUM95] y el método de simulación de Monte Carlo. En el capítulo 8 se describen las conclusiones y lo logros conseguidos. Durante el desarrollo de esta Tesis Doctoral se ha obtenido un dispositivo novedoso susceptible de ser patentado, que ha sido registrado en la Oficina Española de Patentes y Marcas (O.E.P.M.) en Madrid, de conformidad con lo establecido en el artículo 20 de la Ley 11/1986, de 20 de Marzo, de Patentes, con el título Patrón Primario de Ruido Térmico de Banda Ancha (Referencia P-101061) con fecha 7 de febrero de 2011. ABSTRACT This Ph. D. work describes a number of investigations that were performed along the years 2008 to 2011, as a preparation for the study and design of a coaxial cryogenic reference noise standard. Reliable and traceable measurement underpins the welfare of a modern society and plays a critical role in supporting economic competitiveness, manufacturing and trade as well as quality of life. In our modern world, a well developed measurement infrastructure gives confidence in many aspects of our daily life, for example by enabling the development and manufacturing of reliable, high quality and innovative products; by supporting industry to be competitive and sustainable in its production; by removing technical barriers to trade and supporting fair trade; by ensuring safety and effectiveness of healthcare; by giving response to the major challenges in key sectors such energy and environment, etc. With all this in mind we have developed a primary standard thermal noise with the aim of providing the Spanish metrology system with a new primary standard for noise reference. This standard will allow development of reliable and traceable measurements in the field of calibration and measurement of electromagnetic noise RF and microwave devices. This standard has been designed to work in the frequency range from 10 MHz to 26.5 GHz, meeting the following specifications: 1. Noise temperature output is to be nominally ~ 83 K. 2. Noise temperature uncertainty less than ± 1 K in the frequency range from 0.01 to 26.5 GHz. 3. Broadband performance requires as low a reflection coefficient as possible from 0.01 to 26.5 GHz. The present Ph. D. work is divided into three clearly differentiated parts. The first one, which comprises Chapters 1 to 5, presents the whole process of simulation and adjustment of the main parameters of the device in order to define those of them which are critical for the manufacturing of the device. Next, the second part consists of Chapter 6 where the necessary computations to obtain the output noise temperature of the device are carried out. The third and last part, Chapter 7, is devoted to the estimation of the uncertainty related to the noise temperature of the noise primary standard as obtained in the preceding chapter. More specifically, Chapter 1 provides a thorough introduction to the scientific and technological environment where this research takes place. It also details the objectives to be achieved and presents the methodology used to achieve them. Chapter 2 describes the characterization and selection of the bead dielectric material inside the transmission line, intended to connect the two coaxial conductors equalizing the temperature between the two of them and thus keeping the characteristic impedance constant for the whole standard. In addition the dielectric properties of liquid nitrogen are analyzed in order to assess their influence on the impedance of the transmission line. Chapter 3 analyzes the behavior of two different loads and of a commercial airline when subjected to cryogenic working conditions. This study is intended to obtain the variation in the reflection coefficient when the temperature changes from room to cryogenic temperature, and to check whether these devices can be damaged as a result of working at cryogenic temperatures. Also we try to see whether the load changes its behavior after successive cycles of cooling / heating, in order to obtain a bound for the allowed variation of the reflection coefficient of the load. Chapter 4 analyzes the ring structure of the dielectric material used in the NBS technical note 1074 of NIST, in order to obtain its scattering parameters that will be used for computation of its effect upon the reflection coefficient of the whole coaxial structure. Subsequently, we perform a further investigation with the aim of improving the design of NBS technical note 1074 of NIST, and modifications are introduced in the geometry of the transition area in order to reduce the reflection it produces. We first analyze the ring, specifically the influence of the radius of inner conductor of the bead, and then make changes in its geometry so that it presents the same characteristic impedance as that of the line. Finally we analytically obtain the relationship between the inner conductor radius and the radius of the transition from ring, in order to ensure the heat flow through the transition thus keeping the same reflection coefficient, and at the same time meeting the robustness requirements and the feasibility of manufacturing. Chapter 5 analyzes the thermal behavior of the noise standard and its influence on the conductivity of metallic materials. Both possibilities are raised that the liquid nitrogen is kept outside the line or that it penetrates inside. In both cases, given the rotational symmetry of the structure, we have simulated a section of coaxial line, i.e. the equivalent two-dimensional problem has been resolved, although the results are applicable to the actual three-dimensional structure. For thermal simulation Matlab™ PDE Toolbox has been used. In Chapter 6 we compute the output noise temperature of the device. The starting point is the analysis of the contribution to the overall noise temperature of each section making up the standard. Moreover the influence of the variations in the parameters of all elements of the standard is analyzed, specifically the variation of the reflection coefficient along the entire device. Once the electromagnetic noise standard has been described and analyzed, in Chapter 7 we describe the steps followed to estimate the uncertainty of the output electromagnetic noise temperature. This is done using two methods, the classic analytical approach following the Guide to the Estimation of Uncertainty [GUM95] and numerical simulations made with the Monte Carlo method. Chapter 8 discusses the conclusions and achievements. During the development of this thesis, a novel device was obtained which was potentially patentable, and which was finally registered through the Spanish Patent and Trademark Office (SPTO) in Madrid, in accordance with the provisions of Article 20 of Law 11/1986 about Patents, dated March 20th, 1986. It was registered under the denomination Broadband Thermal Noise Primary Standard (Reference P-101061) dated February 7th, 2011.

Side-Channel Attack Protection Techniques in FPGA Systems using Enhanced Dual-Rail Solutions

Esta tesis doctoral se centra principalmente en técnicas de ataque y contramedidas relacionadas con ataques de canal lateral (SCA por sus siglas en inglés), que han sido propuestas dentro del campo de investigación académica desde hace 17 años. Las investigaciones relacionadas han experimentado un notable crecimiento en las últimas décadas, mientras que los diseños enfocados en la protección sólida y eficaz contra dichos ataques aún se mantienen como un tema de investigación abierto, en el que se necesitan iniciativas más confiables para la protección de la información persona de empresa y de datos nacionales. El primer uso documentado de codificación secreta se remonta a alrededor de 1700 B.C., cuando los jeroglíficos del antiguo Egipto eran descritos en las inscripciones. La seguridad de la información siempre ha supuesto un factor clave en la transmisión de datos relacionados con inteligencia diplomática o militar. Debido a la evolución rápida de las técnicas modernas de comunicación, soluciones de cifrado se incorporaron por primera vez para garantizar la seguridad, integridad y confidencialidad de los contextos de transmisión a través de cables sin seguridad o medios inalámbricos. Debido a las restricciones de potencia de cálculo antes de la era del ordenador, la técnica de cifrado simple era un método más que suficiente para ocultar la información. Sin embargo, algunas vulnerabilidades algorítmicas pueden ser explotadas para restaurar la regla de codificación sin mucho esfuerzo. Esto ha motivado nuevas investigaciones en el área de la criptografía, con el fin de proteger el sistema de información ante sofisticados algoritmos. Con la invención de los ordenadores se ha acelerado en gran medida la implementación de criptografía segura, que ofrece resistencia eficiente encaminada a obtener mayores capacidades de computación altamente reforzadas. Igualmente, sofisticados cripto-análisis han impulsado las tecnologías de computación. Hoy en día, el mundo de la información ha estado involucrado con el campo de la criptografía, enfocada a proteger cualquier campo a través de diversas soluciones de cifrado. Estos enfoques se han fortalecido debido a la unificación optimizada de teorías matemáticas modernas y prácticas eficaces de hardware, siendo posible su implementación en varias plataformas (microprocesador, ASIC, FPGA, etc.). Las necesidades y requisitos de seguridad en la industria son las principales métricas de conducción en el diseño electrónico, con el objetivo de promover la fabricación de productos de gran alcance sin sacrificar la seguridad de los clientes. Sin embargo, una vulnerabilidad en la implementación práctica encontrada por el Prof. Paul Kocher, et al en 1996 implica que un circuito digital es inherentemente vulnerable a un ataque no convencional, lo cual fue nombrado posteriormente como ataque de canal lateral, debido a su fuente de análisis. Sin embargo, algunas críticas sobre los algoritmos criptográficos teóricamente seguros surgieron casi inmediatamente después de este descubrimiento. En este sentido, los circuitos digitales consisten típicamente en un gran número de celdas lógicas fundamentales (como MOS - Metal Oxide Semiconductor), construido sobre un sustrato de silicio durante la fabricación. La lógica de los circuitos se realiza en función de las innumerables conmutaciones de estas células. Este mecanismo provoca inevitablemente cierta emanación física especial que puede ser medida y correlacionada con el comportamiento interno del circuito. SCA se puede utilizar para revelar datos confidenciales (por ejemplo, la criptografía de claves), analizar la arquitectura lógica, el tiempo e incluso inyectar fallos malintencionados a los circuitos que se implementan en sistemas embebidos, como FPGAs, ASICs, o tarjetas inteligentes. Mediante el uso de la comparación de correlación entre la cantidad de fuga estimada y las fugas medidas de forma real, información confidencial puede ser reconstruida en mucho menos tiempo y computación. Para ser precisos, SCA básicamente cubre una amplia gama de tipos de ataques, como los análisis de consumo de energía y radiación ElectroMagnética (EM). Ambos se basan en análisis estadístico y, por lo tanto, requieren numerosas muestras. Los algoritmos de cifrado no están intrínsecamente preparados para ser resistentes ante SCA. Es por ello que se hace necesario durante la implementación de circuitos integrar medidas que permitan camuflar las fugas a través de "canales laterales". Las medidas contra SCA están evolucionando junto con el desarrollo de nuevas técnicas de ataque, así como la continua mejora de los dispositivos electrónicos. Las características físicas requieren contramedidas sobre la capa física, que generalmente se pueden clasificar en soluciones intrínsecas y extrínsecas. Contramedidas extrínsecas se ejecutan para confundir la fuente de ataque mediante la integración de ruido o mala alineación de la actividad interna. Comparativamente, las contramedidas intrínsecas están integradas en el propio algoritmo, para modificar la aplicación con el fin de minimizar las fugas medibles, o incluso hacer que dichas fugas no puedan ser medibles. Ocultación y Enmascaramiento son dos técnicas típicas incluidas en esta categoría. Concretamente, el enmascaramiento se aplica a nivel algorítmico, para alterar los datos intermedios sensibles con una máscara de manera reversible. A diferencia del enmascaramiento lineal, las operaciones no lineales que ampliamente existen en criptografías modernas son difíciles de enmascarar. Dicho método de ocultación, que ha sido verificado como una solución efectiva, comprende principalmente la codificación en doble carril, que está ideado especialmente para aplanar o eliminar la fuga dependiente de dato en potencia o en EM. En esta tesis doctoral, además de la descripción de las metodologías de ataque, se han dedicado grandes esfuerzos sobre la estructura del prototipo de la lógica propuesta, con el fin de realizar investigaciones enfocadas a la seguridad sobre contramedidas de arquitectura a nivel lógico. Una característica de SCA reside en el formato de las fuentes de fugas. Un típico ataque de canal lateral se refiere al análisis basado en la potencia, donde la capacidad fundamental del transistor MOS y otras capacidades parásitas son las fuentes esenciales de fugas. Por lo tanto, una lógica robusta resistente a SCA debe eliminar o mitigar las fugas de estas micro-unidades, como las puertas lógicas básicas, los puertos I/O y las rutas. Las herramientas EDA proporcionadas por los vendedores manipulan la lógica desde un nivel más alto, en lugar de realizarlo desde el nivel de puerta, donde las fugas de canal lateral se manifiestan. Por lo tanto, las implementaciones clásicas apenas satisfacen estas necesidades e inevitablemente atrofian el prototipo. Por todo ello, la implementación de un esquema de diseño personalizado y flexible ha de ser tomado en cuenta. En esta tesis se presenta el diseño y la implementación de una lógica innovadora para contrarrestar SCA, en la que se abordan 3 aspectos fundamentales: I. Se basa en ocultar la estrategia sobre el circuito en doble carril a nivel de puerta para obtener dinámicamente el equilibrio de las fugas en las capas inferiores; II. Esta lógica explota las características de la arquitectura de las FPGAs, para reducir al mínimo el gasto de recursos en la implementación; III. Se apoya en un conjunto de herramientas asistentes personalizadas, incorporadas al flujo genérico de diseño sobre FPGAs, con el fin de manipular los circuitos de forma automática. El kit de herramientas de diseño automático es compatible con la lógica de doble carril propuesta, para facilitar la aplicación práctica sobre la familia de FPGA del fabricante Xilinx. En este sentido, la metodología y las herramientas son flexibles para ser extendido a una amplia gama de aplicaciones en las que se desean obtener restricciones mucho más rígidas y sofisticadas a nivel de puerta o rutado. En esta tesis se realiza un gran esfuerzo para facilitar el proceso de implementación y reparación de lógica de doble carril genérica. La viabilidad de las soluciones propuestas es validada mediante la selección de algoritmos criptográficos ampliamente utilizados, y su evaluación exhaustiva en comparación con soluciones anteriores. Todas las propuestas están respaldadas eficazmente a través de ataques experimentales con el fin de validar las ventajas de seguridad del sistema. El presente trabajo de investigación tiene la intención de cerrar la brecha entre las barreras de implementación y la aplicación efectiva de lógica de doble carril. En esencia, a lo largo de esta tesis se describirá un conjunto de herramientas de implementación para FPGAs que se han desarrollado para trabajar junto con el flujo de diseño genérico de las mismas, con el fin de lograr crear de forma innovadora la lógica de doble carril. Un nuevo enfoque en el ámbito de la seguridad en el cifrado se propone para obtener personalización, automatización y flexibilidad en el prototipo de circuito de bajo nivel con granularidad fina. Las principales contribuciones del presente trabajo de investigación se resumen brevemente a continuación: Lógica de Precharge Absorbed-DPL logic: El uso de la conversión de netlist para reservar LUTs libres para ejecutar la señal de precharge y Ex en una lógica DPL. Posicionamiento entrelazado Row-crossed con pares idénticos de rutado en redes de doble carril, lo que ayuda a aumentar la resistencia frente a la medición EM selectiva y mitigar los impactos de las variaciones de proceso. Ejecución personalizada y herramientas de conversión automática para la generación de redes idénticas para la lógica de doble carril propuesta. (a) Para detectar y reparar conflictos en las conexiones; (b) Detectar y reparar las rutas asimétricas. (c) Para ser utilizado en otras lógicas donde se requiere un control estricto de las interconexiones en aplicaciones basadas en Xilinx. Plataforma CPA de pruebas personalizadas para el análisis de EM y potencia, incluyendo la construcción de dicha plataforma, el método de medición y análisis de los ataques. Análisis de tiempos para cuantificar los niveles de seguridad. División de Seguridad en la conversión parcial de un sistema de cifrado complejo para reducir los costes de la protección. Prueba de concepto de un sistema de calefacción auto-adaptativo para mitigar los impactos eléctricos debido a la variación del proceso de silicio de manera dinámica. La presente tesis doctoral se encuentra organizada tal y como se detalla a continuación: En el capítulo 1 se abordan los fundamentos de los ataques de canal lateral, que abarca desde conceptos básicos de teoría de modelos de análisis, además de la implementación de la plataforma y la ejecución de los ataques. En el capítulo 2 se incluyen las estrategias de resistencia SCA contra los ataques de potencia diferencial y de EM. Además de ello, en este capítulo se propone una lógica en doble carril compacta y segura como contribución de gran relevancia, así como también se presentará la transformación lógica basada en un diseño a nivel de puerta. Por otra parte, en el Capítulo 3 se abordan los desafíos relacionados con la implementación de lógica en doble carril genérica. Así mismo, se describirá un flujo de diseño personalizado para resolver los problemas de aplicación junto con una herramienta de desarrollo automático de aplicaciones propuesta, para mitigar las barreras de diseño y facilitar los procesos. En el capítulo 4 se describe de forma detallada la elaboración e implementación de las herramientas propuestas. Por otra parte, la verificación y validaciones de seguridad de la lógica propuesta, así como un sofisticado experimento de verificación de la seguridad del rutado, se describen en el capítulo 5. Por último, un resumen de las conclusiones de la tesis y las perspectivas como líneas futuras se incluyen en el capítulo 6. Con el fin de profundizar en el contenido de la tesis doctoral, cada capítulo se describe de forma más detallada a continuación: En el capítulo 1 se introduce plataforma de implementación hardware además las teorías básicas de ataque de canal lateral, y contiene principalmente: (a) La arquitectura genérica y las características de la FPGA a utilizar, en particular la Xilinx Virtex-5; (b) El algoritmo de cifrado seleccionado (un módulo comercial Advanced Encryption Standard (AES)); (c) Los elementos esenciales de los métodos de canal lateral, que permiten revelar las fugas de disipación correlacionadas con los comportamientos internos; y el método para recuperar esta relación entre las fluctuaciones físicas en los rastros de canal lateral y los datos internos procesados; (d) Las configuraciones de las plataformas de pruebas de potencia / EM abarcadas dentro de la presente tesis. El contenido de esta tesis se amplia y profundiza a partir del capítulo 2, en el cual se abordan varios aspectos claves. En primer lugar, el principio de protección de la compensación dinámica de la lógica genérica de precarga de doble carril (Dual-rail Precharge Logic-DPL) se explica mediante la descripción de los elementos compensados a nivel de puerta. En segundo lugar, la lógica PA-DPL es propuesta como aportación original, detallando el protocolo de la lógica y un caso de aplicación. En tercer lugar, dos flujos de diseño personalizados se muestran para realizar la conversión de doble carril. Junto con ello, se aclaran las definiciones técnicas relacionadas con la manipulación por encima de la netlist a nivel de LUT. Finalmente, una breve discusión sobre el proceso global se aborda en la parte final del capítulo. El Capítulo 3 estudia los principales retos durante la implementación de DPLs en FPGAs. El nivel de seguridad de las soluciones de resistencia a SCA encontradas en el estado del arte se ha degenerado debido a las barreras de implantación a través de herramientas EDA convencionales. En el escenario de la arquitectura FPGA estudiada, se discuten los problemas de los formatos de doble carril, impactos parásitos, sesgo tecnológico y la viabilidad de implementación. De acuerdo con estas elaboraciones, se plantean dos problemas: Cómo implementar la lógica propuesta sin penalizar los niveles de seguridad, y cómo manipular un gran número de celdas y automatizar el proceso. El PA-DPL propuesto en el capítulo 2 se valida con una serie de iniciativas, desde características estructurales como doble carril entrelazado o redes de rutado clonadas, hasta los métodos de aplicación tales como las herramientas de personalización y automatización de EDA. Por otra parte, un sistema de calefacción auto-adaptativo es representado y aplicado a una lógica de doble núcleo, con el fin de ajustar alternativamente la temperatura local para equilibrar los impactos negativos de la variación del proceso durante la operación en tiempo real. El capítulo 4 se centra en los detalles de la implementación del kit de herramientas. Desarrollado sobre una API third-party, el kit de herramientas personalizado es capaz de manipular los elementos de la lógica de circuito post P&R ncd (una versión binaria ilegible del xdl) convertido al formato XDL Xilinx. El mecanismo y razón de ser del conjunto de instrumentos propuestos son cuidadosamente descritos, que cubre la detección de enrutamiento y los enfoques para la reparación. El conjunto de herramientas desarrollado tiene como objetivo lograr redes de enrutamiento estrictamente idénticos para la lógica de doble carril, tanto para posicionamiento separado como para el entrelazado. Este capítulo particularmente especifica las bases técnicas para apoyar las implementaciones en los dispositivos de Xilinx y su flexibilidad para ser utilizado sobre otras aplicaciones. El capítulo 5 se enfoca en la aplicación de los casos de estudio para la validación de los grados de seguridad de la lógica propuesta. Se discuten los problemas técnicos detallados durante la ejecución y algunas nuevas técnicas de implementación. (a) Se discute el impacto en el proceso de posicionamiento de la lógica utilizando el kit de herramientas propuesto. Diferentes esquemas de implementación, tomando en cuenta la optimización global en seguridad y coste, se verifican con los experimentos con el fin de encontrar los planes de posicionamiento y reparación optimizados; (b) las validaciones de seguridad se realizan con los métodos de correlación y análisis de tiempo; (c) Una táctica asintótica se aplica a un núcleo AES sobre BCDL estructurado para validar de forma sofisticada el impacto de enrutamiento sobre métricas de seguridad; (d) Los resultados preliminares utilizando el sistema de calefacción auto-adaptativa sobre la variación del proceso son mostrados; (e) Se introduce una aplicación práctica de las herramientas para un diseño de cifrado completa. Capítulo 6 incluye el resumen general del trabajo presentado dentro de esta tesis doctoral. Por último, una breve perspectiva del trabajo futuro se expone, lo que puede ampliar el potencial de utilización de las contribuciones de esta tesis a un alcance más allá de los dominios de la criptografía en FPGAs. ABSTRACT This PhD thesis mainly concentrates on countermeasure techniques related to the Side Channel Attack (SCA), which has been put forward to academic exploitations since 17 years ago. The related research has seen a remarkable growth in the past decades, while the design of solid and efficient protection still curiously remain as an open research topic where more reliable initiatives are required for personal information privacy, enterprise and national data protections. The earliest documented usage of secret code can be traced back to around 1700 B.C., when the hieroglyphs in ancient Egypt are scribed in inscriptions. Information security always gained serious attention from diplomatic or military intelligence transmission. Due to the rapid evolvement of modern communication technique, crypto solution was first incorporated by electronic signal to ensure the confidentiality, integrity, availability, authenticity and non-repudiation of the transmitted contexts over unsecure cable or wireless channels. Restricted to the computation power before computer era, simple encryption tricks were practically sufficient to conceal information. However, algorithmic vulnerabilities can be excavated to restore the encoding rules with affordable efforts. This fact motivated the development of modern cryptography, aiming at guarding information system by complex and advanced algorithms. The appearance of computers has greatly pushed forward the invention of robust cryptographies, which efficiently offers resistance relying on highly strengthened computing capabilities. Likewise, advanced cryptanalysis has greatly driven the computing technologies in turn. Nowadays, the information world has been involved into a crypto world, protecting any fields by pervasive crypto solutions. These approaches are strong because of the optimized mergence between modern mathematical theories and effective hardware practices, being capable of implement crypto theories into various platforms (microprocessor, ASIC, FPGA, etc). Security needs from industries are actually the major driving metrics in electronic design, aiming at promoting the construction of systems with high performance without sacrificing security. Yet a vulnerability in practical implementation found by Prof. Paul Kocher, et al in 1996 implies that modern digital circuits are inherently vulnerable to an unconventional attack approach, which was named as side-channel attack since then from its analysis source. Critical suspicions to theoretically sound modern crypto algorithms surfaced almost immediately after this discovery. To be specifically, digital circuits typically consist of a great number of essential logic elements (as MOS - Metal Oxide Semiconductor), built upon a silicon substrate during the fabrication. Circuit logic is realized relying on the countless switch actions of these cells. This mechanism inevitably results in featured physical emanation that can be properly measured and correlated with internal circuit behaviors. SCAs can be used to reveal the confidential data (e.g. crypto-key), analyze the logic architecture, timing and even inject malicious faults to the circuits that are implemented in hardware system, like FPGA, ASIC, smart Card. Using various comparison solutions between the predicted leakage quantity and the measured leakage, secrets can be reconstructed at much less expense of time and computation. To be precisely, SCA basically encloses a wide range of attack types, typically as the analyses of power consumption or electromagnetic (EM) radiation. Both of them rely on statistical analyses, and hence require a number of samples. The crypto algorithms are not intrinsically fortified with SCA-resistance. Because of the severity, much attention has to be taken into the implementation so as to assemble countermeasures to camouflage the leakages via "side channels". Countermeasures against SCA are evolving along with the development of attack techniques. The physical characteristics requires countermeasures over physical layer, which can be generally classified into intrinsic and extrinsic vectors. Extrinsic countermeasures are executed to confuse the attacker by integrating noise, misalignment to the intra activities. Comparatively, intrinsic countermeasures are built into the algorithm itself, to modify the implementation for minimizing the measurable leakage, or making them not sensitive any more. Hiding and Masking are two typical techniques in this category. Concretely, masking applies to the algorithmic level, to alter the sensitive intermediate values with a mask in reversible ways. Unlike the linear masking, non-linear operations that widely exist in modern cryptographies are difficult to be masked. Approved to be an effective counter solution, hiding method mainly mentions dual-rail logic, which is specially devised for flattening or removing the data-dependent leakage in power or EM signatures. In this thesis, apart from the context describing the attack methodologies, efforts have also been dedicated to logic prototype, to mount extensive security investigations to countermeasures on logic-level. A characteristic of SCA resides on the format of leak sources. Typical side-channel attack concerns the power based analysis, where the fundamental capacitance from MOS transistors and other parasitic capacitances are the essential leak sources. Hence, a robust SCA-resistant logic must eliminate or mitigate the leakages from these micro units, such as basic logic gates, I/O ports and routings. The vendor provided EDA tools manipulate the logic from a higher behavioral-level, rather than the lower gate-level where side-channel leakage is generated. So, the classical implementations barely satisfy these needs and inevitably stunt the prototype. In this case, a customized and flexible design scheme is appealing to be devised. This thesis profiles an innovative logic style to counter SCA, which mainly addresses three major aspects: I. The proposed logic is based on the hiding strategy over gate-level dual-rail style to dynamically overbalance side-channel leakage from lower circuit layer; II. This logic exploits architectural features of modern FPGAs, to minimize the implementation expenses; III. It is supported by a set of assistant custom tools, incorporated by the generic FPGA design flow, to have circuit manipulations in an automatic manner. The automatic design toolkit supports the proposed dual-rail logic, facilitating the practical implementation on Xilinx FPGA families. While the methodologies and the tools are flexible to be expanded to a wide range of applications where rigid and sophisticated gate- or routing- constraints are desired. In this thesis a great effort is done to streamline the implementation workflow of generic dual-rail logic. The feasibility of the proposed solutions is validated by selected and widely used crypto algorithm, for thorough and fair evaluation w.r.t. prior solutions. All the proposals are effectively verified by security experiments. The presented research work attempts to solve the implementation troubles. The essence that will be formalized along this thesis is that a customized execution toolkit for modern FPGA systems is developed to work together with the generic FPGA design flow for creating innovative dual-rail logic. A method in crypto security area is constructed to obtain customization, automation and flexibility in low-level circuit prototype with fine-granularity in intractable routings. Main contributions of the presented work are summarized next: Precharge Absorbed-DPL logic: Using the netlist conversion to reserve free LUT inputs to execute the Precharge and Ex signal in a dual-rail logic style. A row-crossed interleaved placement method with identical routing pairs in dual-rail networks, which helps to increase the resistance against selective EM measurement and mitigate the impacts from process variations. Customized execution and automatic transformation tools for producing identical networks for the proposed dual-rail logic. (a) To detect and repair the conflict nets; (b) To detect and repair the asymmetric nets. (c) To be used in other logics where strict network control is required in Xilinx scenario. Customized correlation analysis testbed for EM and power attacks, including the platform construction, measurement method and attack analysis. A timing analysis based method for quantifying the security grades. A methodology of security partitions of complex crypto systems for reducing the protection cost. A proof-of-concept self-adaptive heating system to mitigate electrical impacts over process variations in dynamic dual-rail compensation manner. The thesis chapters are organized as follows: Chapter 1 discusses the side-channel attack fundamentals, which covers from theoretic basics to analysis models, and further to platform setup and attack execution. Chapter 2 centers to SCA-resistant strategies against generic power and EM attacks. In this chapter, a major contribution, a compact and secure dual-rail logic style, will be originally proposed. The logic transformation based on bottom-layer design will be presented. Chapter 3 is scheduled to elaborate the implementation challenges of generic dual-rail styles. A customized design flow to solve the implementation problems will be described along with a self-developed automatic implementation toolkit, for mitigating the design barriers and facilitating the processes. Chapter 4 will originally elaborate the tool specifics and construction details. The implementation case studies and security validations for the proposed logic style, as well as a sophisticated routing verification experiment, will be described in Chapter 5. Finally, a summary of thesis conclusions and perspectives for future work are included in Chapter 5. To better exhibit the thesis contents, each chapter is further described next: Chapter 1 provides the introduction of hardware implementation testbed and side-channel attack fundamentals, and mainly contains: (a) The FPGA generic architecture and device features, particularly of Virtex-5 FPGA; (b) The selected crypto algorithm - a commercially and extensively used Advanced Encryption Standard (AES) module - is detailed; (c) The essentials of Side-Channel methods are profiled. It reveals the correlated dissipation leakage to the internal behaviors, and the method to recover this relationship between the physical fluctuations in side-channel traces and the intra processed data; (d) The setups of the power/EM testing platforms enclosed inside the thesis work are given. The content of this thesis is expanded and deepened from chapter 2, which is divided into several aspects. First, the protection principle of dynamic compensation of the generic dual-rail precharge logic is explained by describing the compensated gate-level elements. Second, the novel DPL is originally proposed by detailing the logic protocol and an implementation case study. Third, a couple of custom workflows are shown next for realizing the rail conversion. Meanwhile, the technical definitions that are about to be manipulated above LUT-level netlist are clarified. A brief discussion about the batched process is given in the final part. Chapter 3 studies the implementation challenges of DPLs in FPGAs. The security level of state-of-the-art SCA-resistant solutions are decreased due to the implementation barriers using conventional EDA tools. In the studied FPGA scenario, problems are discussed from dual-rail format, parasitic impact, technological bias and implementation feasibility. According to these elaborations, two problems arise: How to implement the proposed logic without crippling the security level; and How to manipulate a large number of cells and automate the transformation. The proposed PA-DPL in chapter 2 is legalized with a series of initiatives, from structures to implementation methods. Furthermore, a self-adaptive heating system is depicted and implemented to a dual-core logic, assumed to alternatively adjust local temperature for balancing the negative impacts from silicon technological biases on real-time. Chapter 4 centers to the toolkit system. Built upon a third-party Application Program Interface (API) library, the customized toolkit is able to manipulate the logic elements from post P&R circuit (an unreadable binary version of the xdl one) converted to Xilinx xdl format. The mechanism and rationale of the proposed toolkit are carefully convoyed, covering the routing detection and repairing approaches. The developed toolkit aims to achieve very strictly identical routing networks for dual-rail logic both for separate and interleaved placement. This chapter particularly specifies the technical essentials to support the implementations in Xilinx devices and the flexibility to be expanded to other applications. Chapter 5 focuses on the implementation of the case studies for validating the security grades of the proposed logic style from the proposed toolkit. Comprehensive implementation techniques are discussed. (a) The placement impacts using the proposed toolkit are discussed. Different execution schemes, considering the global optimization in security and cost, are verified with experiments so as to find the optimized placement and repair schemes; (b) Security validations are realized with correlation, timing methods; (c) A systematic method is applied to a BCDL structured module to validate the routing impact over security metric; (d) The preliminary results using the self-adaptive heating system over process variation is given; (e) A practical implementation of the proposed toolkit to a large design is introduced. Chapter 6 includes the general summary of the complete work presented inside this thesis. Finally, a brief perspective for the future work is drawn which might expand the potential utilization of the thesis contributions to a wider range of implementation domains beyond cryptography on FPGAs.