Secure circuits embed hardware primitives that provide security properties: Physical Unclonable Functions (PUFs) or attack sensors, for example. These only fulfil their role when powered, which makes a new class of attacks that would be carried out when the targeted circuit is powered off particularly worrying. The aim of our project is precisely to verify the feasibility of laser attacks on powered-off devices and to propose suitable countermeasures to protect against these attacks. In order to carry out this work, we first plan to design in-house and then have an external service provider manufacture a test circuit with carefully selected elementary blocks and simple security primitives for characterisation, testing and modelling purposes. We then plan to carry out laser injection campaigns on this circuit, but also on other circuits already available from the project partners. These experimental campaigns can therefore start at the beginning of the project. This first stage will lead to the development of a fault model, describing the observed faults as exhaustively as possible, at different levels of abstraction: physical, logical and functional. Once we understand the effects of laser attacks on powered-off devices, we plan to apply the resulting fault model to two classical examples of safety primitives. For the PUF, the aim will be to disprove the unclonability property, by experimentally modifying the statistical distribution of the identifiers generated by the PUF. This could go as far as gaining precise control of individual bits of the response obtained. The second application will be the deactivation of an attack sensor before its use, by exposing it to laser radiation when it is powered off. The aim here is to render the sensor non-functional once it is powered. Finally, we plan to illustrate the developed fault model by applying it to two existing systems, resulting from previous ANR projects, and which use the security primitives described above. Thus, we will first target the intellectual property protection system of the SALWARE project, protecting IP cores against illegal copying. This system is based on the intrinsic identification of the different instances of an IP core using a PUF, and the possibility of cloning the PUF would make it possible to illegally activate several components from a single legal activation. The second target device is an integrated substrate current sensor, known as BBICS, from the ANR LIESSE project. The objective here is to raise the detection threshold of the sensor to make it insensitive to the currents induced by a laser attack carried out later. Finally, once this original threat has been clearly identified and validated, we will propose countermeasures that are adapted and suitably designed.

The concept of graph is ubiquitous in modern science: it is a basic notion in combinatorics and algorithmics and it is used as a tool for abstraction in an ever increasing variety of contexts, from social networks to biological process modelling. While the theory of graphs is rich and interesting in general, it also appears clearly that in many applicative contexts, the graphs of interest come with some extra structure that needs to be taken into account, both to improve the focus of the modelisation and to benefit from potentially more efficient algorithmic solutions. Examples range from the celebrated power laws and small-world properties of networks to the dimension reduction phenomenon in geometric data. Our project focuses on the extra combinatorial and topological structure carried by graphs coming with an embedding on a surface of low genus. The resulting objects, called "maps", are fundamental in computer graphics and geometric modelling where maps underlie all classical data structures for the manipulation of 2d meshes. Maps also play an important role in the celebrated graph minor theory of Robertson and Seymour and in its algorithmical consequences: a remarkable outcome of this theory is that for many problems, any improvement on their complexity when restricted to graphs with bounded genus directly extends to the (much wider) class of graphs with forbidden minors. Combinatorial properties of maps have also proven to be very relevant to the study of random models of surfaces as considered in the probabilistic community and in physics in relation with mathematical models of quantum gravity. In the last few years the members of our project have been involved in various deep and independent algorithmic and combinatorial progresses that directly regard maps: we may quote the optimization of curves on surfaces, succinct data structures for meshes, dynamic programming on bounded genus graphs, or bijective decompositions of various families of planar maps, among several others. We believe our group has the right size and expertise to attack the hard challenges raised by the handling of maps on non-trivial surfaces. Let us succinctly describe some of the problematics we want to consider. The combinatorial structure of planar maps is now well understood thanks to the notion of Schnyder woods. One of our main objectives is to extend Schnyder woods to non-planar maps. Another fundamental parameter for maps on higher genus surfaces is the minimal length of a non-contractible cycle. This parameter, called the edge-width, measures the local planarity of a map. Since a typical (random) map has a large edge-width it is relevant to study the dependency of structural properties on this parameter. Apart from Schnyder woods and the edge-width, we want to concentrate on specific families of maps, such as irreducible triangulations, for which topological decompositions such as pants decompositions appear more appropriate for the study of their structure. Understanding the structure of maps is crucial when enumerating, sampling or even representing maps. The representation of non-planar maps, i.e. their geometric embedding, for the purpose of visualization, texture mapping, or network analysis is another of our challenges. In parallel to these theoretical investigations, we wish to implement the state of the art concerning algorithms for maps on surfaces and fix the knowledge in this domain in a dedicated handbook.

The structure of RNA molecules and their complexes are crucial for understanding biology. Notorious examples of large RNAs include the genomes of RNA viruses (Influenza, HIV, Chikungunya, SARS-CoV2...), whose lengths exceed the current capabilities of predictive computational methods, as well as high-res experimental structural techniques. In the INSSANE project, we will develop integrated experimental protocols, together with efficient computational methods for the structural modeling of large RNAs. We will accurately probe and predict the genomic RNA architectures of, bio-medically relevant, viruses. The scope of applicability of our methodologies in bioinformatics will extend beyond viruses, and could be used to model the structure of other large RNAs (lncRNAS, Introns). Towards that goal, we will introduce a novel protocol, named SHAPE-Cut, to streamline the probing of large RNAs. SHAPE-Cut will measure position-specific solvent accessibility by combining novel chemistry and long-read sequencing. In comparison to existing protocols, we expect SHAPE-Cut to avoid typical biases, be easier to implement, and provide increased accuracy, when coupled with specific data analyses and computational methods. We will combine the complementary data of crosslinking and probing experiments: the former reveals long-range interactions, while the latter, through accessibility profiles, has been shown to greatly improve the prediction of local structures. We will implement a recent crosslinking protocol and use its data in index-based genome-wide search of thermodynamically stable RNA-RNA interactions. Then, we devise an integrative structure prediction method that combines SHAPE reactivity, long-range interactions, homology, and thermodynamic stability. Finally, a novel visualization tool will represent genome-scale RNAs and streamline the interdisciplinary dialogue. Algorithmic hurdles will be overcome to improve the processing of sequencing data produced by RNA structure-targeting experiments. All modern RNA probing protocols are based on sequencing technologies, and reveal structural information indirectly, through an alteration that is observable at the RNA sequence level (mutations, stops/cut). However, the crucial mapping of primary sequencing data has received relatively scarce attention in the context of probing techniques, despite specific challenges (chimeric reads, informative errors/stops) having been identified at the root of biases and technical artifacts. We will tailor mapping to our protocols, and develop data structures and indexing techniques to fully exploit sequencing data to its fullest extent. We will also inform mapping by predicted accessibility, e.g. to disambiguate the mapping of erroneous (but probably informative) reads. Beyond increasing mappability, we will deconvolute isoforms/subgenomes, which are known to occur in viral genomes. Our final integrative structure modeling method will consider evolutionary information, and will be formulated as a Maximum-Independent-Set (MIS) graph problem for a conflict graph including both alternative local structure and long-range interactions. We will implement a Fixed Parameter Tractable algorithm based on the treewidth to produce a model with maximal support and thermodynamic stability. By including experts in bioinformatics of RNA structure, sequence analysis, biochemistry, and organic chemistry, our consortium is uniquely positioned to address the timely challenges tackled in the project. Its implementation requires a combination of expertise from traditionally distinct areas of bioinformatics, namely combinatorial structure prediction and high-throughput sequencing analysis. Its synergies will build on existing pairwise collaborations and will streamline the communication between partners representing complementary perspectives on RNA as an object of study.

Verifying correctness and robustness of programs and systems is a major challenge in a society which relies more and more on safety-critical systems controlled by embedded software. This issue is even more critical when the computations involve floating-point number arithmetic, an arithmetic known for its quite unusual behaviors, and which is increasingly used in embedded software. Note for example the "catastrophic cancellation" phenomenon where most of the significant digits of a result are cancelled or, numerical sequences whose limit is very different over the real numbers and over the floating-point numbers. A more important problem arises when we want to analyse the relationship between floating-point computations and an "idealized" computation that would be carried out with real numbers, the reference in the design of the program. The point is that for some input values, the control flow over the real numbers can go through one conditional branch while it goes through another one over the floating-point numbers. Certifying that a program, despite some control flow divergences, computes what it is actually expected to compute with a minimum error is the subject of the robustness or continuity analysis. Providing a set of techniques and tools for verifying the accuracy, correctness and robustness for critical embedded software is a major challenge. The aim of this project is to address this challenge by exploring new methods based on a tight collaboration between abstract interpretation (IA) and constraint programming (CP). In other words, the goal is to push the limits of these two techniques for improving accuracy analysis, to enable a more complete verification of programs using floating point computations, and thus, to make critical decisions more robust. The cornerstone of this project is the combination of the two approaches to increase the accuracy of the proof of robustness by using PPC techniques, and, where appropriate, to generate non-robust test cases. The goal is to benefit from the strengths of both techniques: PPC provides powerful but computationally expensive algorithms to reduce domains with an arbitrary given precision whereas AI does not provide fine control over domain precision, but has developed many abstract domains that quickly capture program invariants of various forms. Incorporating some PPC mechanisms (search tree, heuristics) in abstract domains would enable, in the presence of false alarms, to refine the abstract domain by using a better accuracy. The first problem to solve is to set the theoretical foundations of an analyser based on two substantially different paradigms. Once the interactions between PPC and IA are well formalized, the next issue is to handle constraints of general forms and potentially non-linear abstract domains. Last but not least, an important issue concerns the robustness analysis of more general systems than programs, like hybrid systems which are modeling control command programs. Research results will be evaluated on realistic benchmarks coming from industrial companies, in order to determine their benefits and relevance. For the explored approaches, using realistic examples is a key point since the proposed techniques often only behave in an acceptable manner on a given sub classes of problems (if we consider the worst-case computational complexity all these problems are intractable). That's why many solutions are closely connected to the target problems.

Stakeholders from the built environment (designers, contractors, owners, facility managers) often face problems related to data access and sharing, on one hand, and to the integration of high volumes of heterogeneous data from different knowledge domains, on the other hand. These limitations directly impact the effectiveness of data processing and data analysis and are a common issue in the field of Architecture, Engineering, and Construction (AEC). When considering the built environment, practitioners cannot rely only on building-level data; buildings evolve in a much larger ecosystem expanding upwards to the level and scale of a city and downwards to the level and scale of products and related components (e.g. installed heating, ventilating and air conditioning - HVAC components, wall types, window and door materials, floor finishing, domotica) and sensors (e.g. temperature sensors, air quality sensors, cameras, smart appliances sensors). This ecosystem involves an increasing number of services and applications. Even with access to standardized building information, multiple data sources have to be integrated for an organization to hold a considerable competitive advantage. A uniform approach is thus needed for modelling data and processes at any level of granularity, from the level of real-time sensor monitoring to the level of long-term urban planning. The multi-disciplinary goal of this research project is to deliver a spatio-temporal model for Big semantic and spatio-temporal Data extracted from a variety of sources. For the processing of data, an innovative lambda architecture will ease the definition of a Big Data architecture allowing a seamless real-time semantic and spatio-temporal qualitative analysis of the data mentioned above. The spatio-temporal issue is present both at the level of the data model itself and at the level of sensors and the context in which they perform data acquisition (component, building or urban level, indoor or outdoor). Our project addresses the following issues: a) delivering a novel architecture for optimizing big semantic and spatio-temporal data processing tasks; b) implementing distributed semantic and spatio-temporal data and process qualitative analysis and mining, at the service of stakeholders from the built environment; c) allowing real-time geospatial event processing, over a large number of high volume streams of sensor or third party data. Coupling the defined data model to the defined infrastructure allows capturing sensor data and integrating a business-related spatio-temporal reference. By merging building-internal and building-external knowledge, along with qualitative and quantitative analysis tools, we deliver upper-level business services (Big Data as a Service). Finally, we investigate and deliver a specialization of those services for the smart buildings and the smart cities domains. This project addresses cross-sector (building industry, geospatial management, process modelling, multi-level sensor analysis) and cross-border (urban administrations, national and local governments, European regulations) issues, our goal in this MRSEI funding request is to build a consortium of public and private partners for addressing these challenges in the domain of built environment life-cycle management. We have identified the "Big data PPP: research addressing main technology challenges of the data economy" (ICT-16-2017) call as most pertaining given our project's goals. ICT-16-2017 summarizes the exact key challenge in handling big semantic and spatio-temporal built environment data (GIS, BIM, and sensor data). Our project aims at extending results obtained in previous EU FP7 projects such as City Pulse, Ready4SmartCities, SO-PC-Pro, DURAAK, along with respecting the directives defined through EU FP6 INSPIRE.