Publications

2021

• La vie et l'oeuvre de Kolmogorov
  
  • Rioul Olivier
  CultureMath, ENS, 2021. Andreï Nikolaïevitch Kolmogorov est un mathématicien soviétique, l'un des plus grands mathématiciens du XXe siècle. Un esprit des plus brillants, profonds et originaux que le monde ait jamais connu. Que ce soit en probabilité, statistiques, analyse fonctionnelle, analyse spectrale, géométrie, théorie de l'approximation, logique intuitionniste, topologie algébrique, génétique, écologie, systèmes dynamiques, turbulence, mécanique classique, théorie de l'information, complexité algorithmique, pédagogie mathématique.. . il révolutionnait chaque sujet en l'abordant avec un regard étonnamment neuf et une perspective totalement originale. Ses idées, toujours d'une grande portée, paraissent dans des articles très courts : seulement quelques pages d'une profondeur, d'une perspicacité et d'une imagination stupéfiantes. Et sa bibliographie complète comporte plus de 500 publications. Il était admiré par ses collègues mathématiciens du monde entier pendant plus de 60 ans et donnait l'impression qu'il démontrait tous les théorèmes qu'il voulait. Il est surtout connu pour ses travaux sur la théorie des probabilités et particulièrement pour ses Grundbegriffe der Wahrscheinlichkeitsrechnung (« Fondements de la théorie des probabilités »), une modeste monographie de 60 pages paru en 1933. En reconstruisant rigoureusement toute la théorie des probabilités, ce petit ouvrage a totalement révolutionné la discipline à la fois scientifiquement et culturellement.
• Strategy RV: A Tool to Approximate ATL Model Checking under Imperfect Information and Perfect Recall
  
  • Ferrando Angelo
  • Malvone Vadim
  , 2021.
• Soft Walks: Real-Time, Two-Ways Interaction between a Character and Loose Grounds
  
  • Paliard Chloé
  • Alvarado Eduardo
  • Rohmer Damien
  • Cani Marie-Paule
  , 2021. When walking on loose terrains, possibly covered with vegetation, the ground and grass should deform, but the character’s gait should also change accordingly. We propose a method for modeling such two-ways interactions in real-time. We first complement a layered character model by a high-level controller, which uses position and angular velocity inputs to improve dynamic oscillations when walking on various slopes. Secondly, at a refined level, the feet are set to locally deform the ground and surrounding vegetation using efficient procedural functions, while the character’s response to such deformations is computed through adapted inverse kinematics. While simple to set up, our method is generic enough to adapt to any character morphology. Moreover, its ability to generate in real time, consistent gaits on a variety of loose grounds of arbitrary slope, possibly covered with grass, makes it an interesting solution to enhance films and games.
• Online cycle detection for models with mode-dependent input and output dependencies
  
  • Park Heejong
  • Easwaran Arvind
  • Borde Etienne
  Journal of Systems Architecture, Elsevier, 2021, 115, pp.102017. In the fields of co-simulation and component-based modelling, designers import models as building blocks to create a composite model that provides more complex functionalities. Modelling tools perform instantaneous cycle detection (ICD) on the composite models having feedback loops to reject the models if the loops are mathematically unsound and to improve simulation performance. In this case, the analysis relies heavily on the availability of dependency information from the imported models. However, the cycle detection problem becomes harder when the model’s input to output dependencies are mode-dependent, i.e. changes for certain events generated internally or externally as inputs. The number of possible modes created by composing such models increases significantly and unknown factors such as environmental inputs make the offline (statical) ICD a difficult task. In this paper, an online ICD method is introduced to address this issue for the models used in cyber–physical systems. The method utilises an oracle as a central source of information that can answer whether the individual models can make mode transition without creating instantaneous cycles. The oracle utilises three types of data-structures created offline that are adaptively chosen during online (runtime) depending on the frequency as well as the number of models that make mode transitions. During the analysis, the models used online are stalled from running, resulting in the discrepancy with the physical system. The objective is to detect an absence of the instantaneous cycle while minimising the stall time of the model simulation that is induced from the analysis. The benchmark results show that our method is an adequate alternative to the offline analysis methods and significantly reduces the analysis time. (10.1016/j.sysarc.2021.102017)
  DOI : 10.1016/j.sysarc.2021.102017
• Espoir
  
  • Zayana Karim
  • Rabiet Victor
  CultureMath, ENS, 2021.
• Experimental vulnerability analysis of QKD based on attack ratings
  
  • Kumar Rupesh
  • Mazzoncini Francesco
  • Qin Hao
  • Alleaume Romain
  Scientific Reports, Nature Publishing Group, 2021, 11 (1). Abstract Inspired by the methodology used for classical cryptographic hardware, we consider the use of attack ratings in the context of QKD security evaluation. To illustrate the relevance of this approach, we conduct an experimental vulnerability assessment of CV-QKD against saturation attacks, for two different attack strategies. The first strategy relies on inducing detector saturation by performing a large coherent displacement. This strategy is experimentally challenging and therefore translates into a high attack rating. We also propose and experimentally demonstrate a second attack strategy that simply consists in saturating the detector with an external laser. The low rating we obtain indicates that this attack constitutes a primary threat for practical CV-QKD systems. These results highlight the benefits of combining theoretical security considerations with vulnerability analysis based on attack ratings, in order to guide the design and engineering of practical QKD systems towards the highest possible security standards. (10.1038/s41598-021-87574-4)
  DOI : 10.1038/s41598-021-87574-4
• More permutations and involutions for constructing bent functions
  
  • Li Yubo
  • Li Kangquan
  • Mesnager Sihem
  • Qu Longjiang
  Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, Springer, 2021, 13 (3), pp.459-473. (10.1007/s12095-021-00482-2)
  DOI : 10.1007/s12095-021-00482-2
• En phase et quadrature
  
  • Zayana Karim
  • Rabiet Victor
  CultureMath, ENS, 2021.
• Le paradoxe de Zéna
  
  • Zayana Karim
  • Rabiet Victor
  CultureMath, ENS, 2021.
• Smart Antenna Assignment is Essential in Full-Duplex Communications
  
  • Silva Jose Mairton B. Da
  • Ghauch Hadi
  • Fodor Gabor
  • Skoglund Mikael
  • Fischione Carlo
  IEEE Transactions on Communications, Institute of Electrical and Electronics Engineers, 2021, 69 (5), pp.3450-3466. (10.1109/TCOMM.2021.3059463)
  DOI : 10.1109/TCOMM.2021.3059463
• Approximate computation of projection depths
  
  • Dyckerhoff Rainer
  • Mozharovskyi Pavlo
  • Nagy Stanislav
  Computational Statistics and Data Analysis, Elsevier, 2021, 157, pp.107166. (10.1016/j.csda.2020.107166)
  DOI : 10.1016/j.csda.2020.107166
• Spot the Difference: Accuracy of Numerical Simulations via the Human Visual System
  
  • Um Kiwon
  • Hu Xiangyu
  • Wang Bing
  • Thuerey Nils
  ACM Transactions on Applied Perception, Association for Computing Machinery, 2021, 18 (2), pp.1-15. Comparative evaluation lies at the heart of science, and determining the accuracy of a computational method is crucial for evaluating its potential as well as for guiding future efforts. However, metrics that are typically used have inherent shortcomings when faced with the under-resolved solutions of real-world simulation problems. We show how to leverage the human visual system in conjunction with crowd-sourced user studies to address the fundamental problems of widely used classical evaluation metrics. We demonstrate that such user studies driven by visual perception yield a very robust metric and consistent answers for complex phenomena without any requirements for proficiency regarding the physics at hand. This holds even for cases away from convergence where traditional metrics often end up with inconclusive results. More specifically, we evaluate results of different essentially non-oscillatory (ENO) schemes in different fluid flow settings. Our methodology represents a novel and practical approach for scientific evaluations that can give answers for previously unsolved problems. (10.1145/3449064)
  DOI : 10.1145/3449064
• f' g + f g' ou f 'g − f g' ?
  
  • Zayana Karim
  • Rabiet Victor
  • Boyer Ivan
  CultureMath, ENS, 2021.
• A blockchain-based certificate revocation management and status verification system
  
  • Adja Elloh Yves Christian
  • Hammi Badis
  • Serhrouchni Ahmed
  • Zeadally Sherali
  Computers & Security, Elsevier, 2021, 104, pp.102209. Revocation management is one of the main tasks of the Public Key Infrastructure (PKI). It is also critical to the security of any PKI. As a result of the increase in the number and sizes of networks as well as the adoption of novel paradigms such as the Internet of Things and their usage of the web, current revocation mechanisms are vulnerable to single point of failures as the network loads increase. To address this challenge, we take advantage of blockchains power and resiliency in order to propose an efficient decentralized certificates revocation management and status verification system. We use the extension field of the X509 certificate’s structure to introduce a field that describes to which distribution point the certificate will belong to if revoked. Each distribution point is represented by a Bloom filter filled with revoked certificates. Bloom filters and revocation information are stored in a public blockchain. We developed a real implementation of our proposed mechanism in Python and the Namecoin blockchain. Then, we conducted an extensive evaluation of our scheme using performance metrics such as execution time and data consumption to demonstrate that it can meet the needed requirements with high efficiency and low cost. Moreover, we compare the performance of our approach with two of the most well-known/used revocation techniques which are Online Certificate Status Protocol (OCSP) and Certificate Revocation List (CRL). The results obtained show that our proposed approach outperforms these current schemes. (10.1016/j.cose.2021.102209)
  DOI : 10.1016/j.cose.2021.102209
• Towards a new open-source 5G development framework: an introduction to free5GRAN
  
  • de Javel Aymeric
  • Gomez Jean-Sébastien
  • Martins Philippe
  • Rougier Jean Louis
  • Nivaggioli Patrice
  , 2021, pp.1-5. 5G technology has been designed with flexibility and software reusability in mind. In this context, open-source developments are critical enablers for mastering software architecture and associated codes, which are of the utmost importance for all technology stakeholders (ranging from manufacturers to operators and service users). free5GRAN is a new open-source 5G development framework. It focuses on research and education. It provides a modular architecture and a set of well-documented APIs, which enable easy experiment reproduction. free5GRAN aims at easing the understanding of 5G standards and the development of new technology components. The global objective is to be as modular as GnuRadio project [1], but with full system implementation. It has not been designed with performances in mind, unlike other open-source projects such as srsLTE [2] and OpenAirInterface [3]. The current release implements a significant part of the PHY layer on the receiver side, and the MAC layer will be part of a future release. Its architecture, which is composed of a library and an implementation part, is described. Moreover, RAN components are explained, and custom implementation methods are provided. It has been tested and validated against a commercial Amarisoft 5G SA gNodeB in a Faraday Cage. (10.1109/VTC2021-Spring51267.2021.9448964)
  DOI : 10.1109/VTC2021-Spring51267.2021.9448964
• Slice-aware energy saving algorithm for 5G networks based on simplicial homology
  
  • de Javel Aymeric
  • Gomez J.S.
  • Martins P.
  • Rougier J.L.
  • Nivaggioli P.
  , 2021, pp.1-5. Network slicing is an important feature introduced by 5G. It enables an operator to deploy multiple independent end-to-end virtual networks, called network slices, on top of a common physical infrastructure. Network slices require the allocation of resources at different levels of the system, among which power budget is of upmost importance at RAN level. This work proposes a new power allocation algorithm for 5G network slicing. Network slices are introduced as a set of five parameters that reflect slices capacity, latency and reliability requirements. Simplicial homology is used to analyse network coverage. Reliability is then defined in terms of a multiple network connectivity criteria. The performances of the proposed algorithm are evaluated by simulations for a scenario with three different network slices: eMBB, uRLLC and mMTC. This method can be used to determine the required power budget at RAN level for different 5G network slices deployment scenarios. (10.1109/VTC2021-Spring51267.2021.9448860)
  DOI : 10.1109/VTC2021-Spring51267.2021.9448860
• Categorizing all linear codes of IPM over ${\mathbb {F}}_{2^{8}}$
  
  • Cheng Wei
  • Guilley Sylvain
  • Danger Jean-Luc
  Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, Springer, 2021. (10.1007/s12095-021-00483-1)
  DOI : 10.1007/s12095-021-00483-1
• Highly Reliable PUFs for Embedded Systems, Protected Against Tampering
  
  • Danger Jean-Luc
  • Guilley Sylvain
  • Pehl Michael
  • Senni Sophiane
  • Souissi Youssef
  , 2021, 379, pp.167-184. Physically Unclonable Functions (PUFs) are well-known to be solutions for silicon-level anti-copy applications. However, as they are sensitive components, they are the obvious target of physical attacks. Thus, they shall be well protected. In this work we discuss the use case of key generation with a Loop PUF. We discuss the Loop PUF's efficiency and efficacy. We analyze it with respect to several known attacks like sidechannel and machine learning attacks, and show that in all considered cases it either natively resists or can be protected. We also show that perturbation attempts should be within the scope of likely attacks, hence the PUF shall be protected against tampering attacks as well. Also for this attack scenario we highlight the salient features of the Loop PUF and explain how its mode of operation natively empowers it to resist such attacks. (10.1007/978-3-030-77424-0_14)
  DOI : 10.1007/978-3-030-77424-0_14
• Managing Consent for Data Access in Shared Databases
  
  • Drien Osnat
  • Amarilli Antoine
  • Amsterdamer Yael
  , 2021, pp.1949-1954. (10.1109/ICDE51399.2021.00182)
  DOI : 10.1109/ICDE51399.2021.00182
• Fingerprinting Concepts in Data Streams with Supervised and Unsupervised Meta-Information
  
  • Halstead Ben
  • Koh Yun Sing
  • Riddle Patricia
  • Pechenizkiy Mykola
  • Bifet Albert
  • Pears Russel
  , 2021, pp.1056--1067. Streaming sources of data are becoming more common as the ability to collect data in real-time grows. A major concern in dealing with data streams is concept drift, a change in the distribution of data over time, for example, due to changes in environmental conditions. Representing concepts (stationary periods featuring similar behaviour) is a key idea in adapting to concept drift. By testing the similarity of a concept representation to a window of observations, we can detect concept drift to a new or previously seen recurring concept. Concept representations are constructed using meta-information features, values describing aspects of concept behaviour. We find that previously proposed concept representations rely on small numbers of meta-information features. These representations often cannot distinguish concepts, leaving systems vulnerable to concept drift. We propose FiCSUM, a general framework to represent both supervised and unsupervised behaviours of a concept in a fingerprint, a vector of many distinct meta-information features able to uniquely identify more concepts. Our dynamic weighting strategy learns which meta-information features describe concept drift in a given dataset, allowing a diverse set of meta-information features to be used at once. FiCSUM outperforms state-of-the-art methods over a range of 11 real world and synthetic datasets in both accuracy and modeling underlying concept drift. (10.1109/ICDE51399.2021.00096)
  DOI : 10.1109/ICDE51399.2021.00096
• Quelles antennes pour la 5G ?
  
  • Begaud Xavier
  Télécom‎ : revue de l'association TELECOM Paristech ALUMNI, Association Télécom ParisTech alumni, 2021 (200), pp.12-13. Le déploiement des réseaux mobiles de cinquième génération (5G) apporte son lot d’innovations en termes de technologies d’antennes. Il serait trop ambitieux de lister toutes leurs spécificités et cet article se focalisera (comme les nouvelles antennes 5G) sur quelques solutions remarquables pour les smartphones et les points d’accès radio.
• Resisting Adversarial Examples via Wavelet Extension and Denoising
  
  • Zheng Qinkai
  • Qiu Han
  • Zhang Tianwei
  • Memmi Gerard
  • Qiu Meikang
  • Lu Jialiang
  , 2021, 12608, pp.204-214. (10.1007/978-3-030-74717-6_22)
  DOI : 10.1007/978-3-030-74717-6_22
• vertTIRP: Robust and efficient vertical frequent time interval-related pattern mining
  
  • Mordvanyuk Natalia
  • López Beatriz
  • Bifet Albert
  Expert Systems with Applications, Elsevier, 2021, 168, pp.114276. Time-interval-related pattern (TIRP) mining algorithms find patterns such as “A starts B” or “A overlaps B”. The discovery of TIRPs is computationally highly demanding. In this work, we introduce a new efficient algorithm for mining TIRPs, called vertTIRP which combines an efficient representation of these patterns, using their temporal transitivity properties to manage them, with a pairing strategy that sorts the temporal relations to be tested, in order to speed up the mining process. Moreover, this work presents a robust definition of the temporal relations that eliminates the ambiguities with other relations when taking into account the uncertainty in the start and end time of the events (epsilon-based approach), and includes two constraints that enable the user to better express the types of TIRPs to be learnt. An experimental evaluation of the method was performed with both synthetic and real datasets, and the results show that vertTIRP requires significantly less computation time than other state-of-the-art algorithms, and is an effective approach. (10.1016/J.ESWA.2020.114276)
  DOI : 10.1016/J.ESWA.2020.114276
• Constant-Delay Enumeration for Nondeterministic Document Spanners
  
  • Mengel Stefan
  • Amarilli Antoine
  • Bourhis Pierre
  • Niewerth Matthias
  ACM Transactions on Database Systems, Association for Computing Machinery, 2021, 46 (1), pp.1-30. We consider the information extraction framework known as document spanners and study the problem of efficiently computing the results of the extraction from an input document, where the extraction task is described as a sequential variable-set automaton (VA). We pose this problem in the setting of enumeration algorithms, where we can first run a preprocessing phase and must then produce the results with a small delay between any two consecutive results. Our goal is to have an algorithm that is tractable in combined complexity, i.e., in the sizes of the input document and the VA, while ensuring the best possible data complexity bounds in the input document size, i.e., constant delay in the document size. Several recent works at PODS’18 proposed such algorithms but with linear delay in the document size or with an exponential dependency in size of the (generally nondeterministic) input VA. In particular, Florenzano et al. suggest that our desired runtime guarantees cannot be met for general sequential VAs. We refute this and show that, given a nondeterministic sequential VA and an input document, we can enumerate the mappings of the VA on the document with the following bounds: the preprocessing is linear in the document size and polynomial in the size of the VA, and the delay is independent of the document and polynomial in the size of the VA. The resulting algorithm thus achieves tractability in combined complexity and the best possible data complexity bounds. Moreover, it is rather easy to describe, particularly for the restricted case of so-called extended VAs. Finally, we evaluate our algorithm empirically using a prototype implementation. (10.1145/3436487)
  DOI : 10.1145/3436487
• When OT meets MoM: Robust estimation of Wasserstein Distance
  
  • Staerman Guillaume
  • Mozharovskyi Pavlo
  • d'Alché-Buc Florence
  • Laforgue Pierre
  , 2021. Issued from Optimal Transport, the Wasserstein distance has gained importance in Machine Learning due to its appealing geometrical properties and the increasing availability of efficient approximations. In this work, we consider the problem of estimating the Wasserstein distance between two probability distributions when observations are polluted by outliers. To that end, we investigate how to leverage Medians of Means (MoM) estimators to robustify the estimation of Wasserstein distance. Exploiting the dual Kantorovitch formulation of Wasserstein distance, we introduce and discuss novel MoM-based robust estimators whose consistency is studied under a data contamination model and for which convergence rates are provided. These MoM estimators enable to make Wasserstein Generative Adversarial Network (WGAN) robust to outliers, as witnessed by an empirical study on two benchmarks CIFAR10 and Fashion MNIST. Eventually, we discuss how to combine MoM with the entropy-regularized approximation of the Wasserstein distance and propose a simple MoM-based re-weighting scheme that could be used in conjunction with the Sinkhorn algorithm.