O A González-Estrada

J F Cáceres-Ramírez

W Pinto-Hernández

Virtual tool for training and evaluation of problem-based engineering subjects

In Educational Technology, one of the challenges in the use of virtual tools for engineering education is the assessment of problem-based subjects. In this work, a software generator of exercises is developed, to be contained in a virtual platform, which seeks to improve the learning process and the evaluation of the subjects based on problems such as, e.g., Mechanics of Materials. The student can use it for training, with content corresponding to the subject of the course, monitoring their performance and obtaining effective feedback. Additionally, the teacher has the possibility to periodically conduct formative assessments that allow him to recognize the concepts in which the students are failing. This tool can provide an objective instrument to normalize grading across groups directed by different lecturers. The software was written in the programming languages Java, JavaScript and HTML for the presentation of the contents, and can be used from any electronic device. This tool can be used to enhance classroom learning in face to face, blended or online learning.

Introduction

Since its inception, the World Wide Web has undergone several transformations thanks to technological advances and the needs that different types of users demand. Web 2.0 is the conception of the network as a platform, it gives people an active role, and encourage participation and usability [1]. These features have promoted the boom of Educational Technology aimed to enhance the teacherstudent experience, improve knowledge management [2], and facilitate the learning process [3]. Within Educational Technology, electronic learning (e-learning) consists in the use of new multimedia and Internet technologies to improve the quality of learning by facilitating access to resources and services, as well as to the collaboration and remote exchange. In e-learning, the formative process takes place through a kind of virtual environment in which the teacher-student interaction takes place as well as the activities of the students with the learning materials. The e-learning serves as a means for face-to-face, online or blended teaching.

Educational Technology has many advantages, it can be used to simplify and reduce the cost for labs used to demonstrate concepts [4], massify access to knowledge with initiatives as massive online open courses (MOOC), improve feedback for effective formative assessment [5], or even help vulnerable populations by facilitating access to remote places affected by security issues [6]. Challenges for developing countries include improving Information and Communication Technologies (ICT) infrastructure, facilitating access and use of the technological resources, and encouraging the adoption of new training methods [7].

We can find numerous efforts that have been reported in the literature to support the teachinglearning process of various subjects. In [8] a program created in Macromedia Flash v8.0 focuses on the understanding of the laboratory tests that accompany the theory of the course Mechanics of Materials. It includes tests of traction, compression, shear, Poisson's effect, torsion, extensometry, bending, columns and photo-elasticity. The student has different types of evaluations that not only allow him to evaluate his learning but also prepare him for the tests that are normally carried out in theory courses.

In [9], a didactic tool is developed with the objective of supporting the teaching-learning process of Linear Algebra in engineering degrees. When entering the problem data in the software, the operation is processed and the procedure is visualized, showing step by step how the problem is solved. Moreover, it contains theoretical material to review the concepts that the student needs to develop the exercises. The proposed system was implemented in the C ++ Builder.

SimulPhysics [10] is a multiplatform software, written in Java, that contains a set of interactive simulations on different topics of physics that supports the assimilation of the concepts developed in the theoretical part of the course. On the platform, we can find simulations on different topics that are seen in the subject of Basic Physics, e.g., mechanics, optics, waves, etc.

Celosías paramétricas [START_REF] Mansilla | Celosías Paramétricas[END_REF] is an Android application, targeted to Education and Learning, that automatically generates trusses by combining parameters related to the geometry, material, supports and loads, and shows the influence of each of them on its structural behavior: reaction forces, stresses, and deformations. It allows the optimization of the structural design by determining the values that produce the lowest stresses and deformations for the highest loads, while minimizing the weight.

MDSolids [START_REF] Philpot | [END_REF] is an educational software package dedicated to the introduction of the Mechanics of Materials course. The software has an intuitive interface that guides the user to understand important facts that are found in different types of problems. It helps to visualize the nature of internal stresses and strains.

Regarding assessment, Hernández Pina [START_REF] Pina | La evaluación de los alumnos en el contexto de la evaluación de la calidad de las universidades[END_REF] investigates the learning process in the university context, and concludes by stating that the way in which the teacher raises the evaluation affects learning approaches (superficial or deep) and the quality of such learning. Quantitative evaluation strategies lead to superficial learning approaches, while formative and qualitative strategies can produce deep learning and high-performance approaches [START_REF] Sadler | Formative assessment and the design of instructional systems[END_REF]. In [START_REF] Ochoa | Generador automático de tareas como apoyo a los procesos de evaluación Reunión Nacional ACOFI[END_REF], a project carried out by the School of Engineering of the EAFIT University implements an interactive software in a virtual platform. With this tool the students can carry out tests, clarifying doubts and preparing them for the final test. It incorporates a rating system and a problem generator algorithm for the course of Statics.

Following the development of the new Information and Communication Technologies (ICTs), we propose a software tool for a virtual educational environment which could be used to improve the assessment of problem-based subjects and provide a standardized marking system that could be used across classes and campuses. The software generates problems on the different topics of the subject Mechanics of Materials, giving the student an interactive tool that allows him to learn by solving problems that help him to strengthen his analytical skills and increase his cognitive abilities. Moreover, the teacher could perform controls and follow performance indicators, which can be used as a reference of the level of study and understanding of their students on the content seen in class, and the competences defined in the curriculum.

The paper is organized as follows: in the next section, we exposed the methodology, including the knowledge base and performance indicators, which are used to define the constraints for the design of the tool. In section 3, we present details related to the implementation of the tool in the Learning Management System. Conclusions are given in the final section.

Methods

The methodology is focused on the subject Mechanics of Materials, although it could be easily extended to other problem-based subjects in engineering curricula. The project is based on the framework of Educational Technology, which refers to the systematic way of conceiving, applying and evaluating the set of teaching and learning processes, considering both technical and human resources and the interactions between them, as a way to obtain a more effective education. In this regard, we define a strategy to tackle different issues detected during the learning and assessment process in the schools of engineering at Universidad Industrial de Santander. First, when evaluating problem-based subjects, the teacher should pay attention to the process followed by the student to reach the answer. Normally, the problem solution is divided into steps, and a weighting is given to each of the partial steps. However, if the student fails early in the process, the teacher should evaluate the remaining steps considering the wrong values obtained at the beginning, and their impact in the final answer. This is particularly difficult for large groups, which finally yields nonhomogeneous, subjective marks. This difference is accentuated if we consider groups led by different teachers. Moreover, regarding teachers, there is a notable difference in the assessment performed by tenured and non-tenured professors, mostly due to the correlation between the grades and the teacher evaluation, which affects contract extensions for non-tenured professors. There are even instances where the content given by the teacher is incomplete and we end up with groups of students with different level of competences reached. This non-standardized marking system gives rise to problems for the mobility of students across campuses, and helps to increase retention rates.

We start by defining the knowledge base that encompasses the area of Mechanics of Materials, putting special attention on the competences required at the end of the course. Next, we work on the performance indicators for the established competences, which help to define the constraints for the design of the tool.

Subject description and knowledge by competences

The subject Mechanics of Materials [START_REF] Beer | Mechanics of Materials[END_REF] studies the mechanics of deformable solids by simplified linear elastic models, relating in the design process the parameters of geometry, forces, and material. The mechanical engineer works with static and moving mechanical structures and systems. The design and calculation of these systems involve considering all the loads that act on each of its elements and the intensity of internal force (stresses) generated by these loads. In mechanical design, the stresses can be related to the mechanical strength of the material to assess the possibility of failure for a given element. In general, a machine element can fail because the stresses exceed the strength of the material, or because excessive deformation is occurring that prevents its normal operation [START_REF] Ayestarán | Resistencia de vigas esbeltas de acero inoxidable bajo cargas concentradas mediante elementos finitos[END_REF]. The calculation of these stresses and deformations involves considering the internal forces and the geometric features of the element.

At the end of the course the student is expected to:

• Recognize the type of stress produced by a force or moment applied to a machine or structural element, according to the way it acts on the element. • Calculate stresses and deformations that occur at any point of an element subjected to a specific type of load. • Select the critical point where the highest stress occurs in any element subjected to several types of load simultaneously. • Define the plane stress state at the critical point of any element subjected to different types of external load. • Analyze the possible failure of an element subjected to different types of loads using different criteria according to the type of material, and propose changes to the geometry accordingly. The curriculum is divided into four fundamental thematic blocks. The first block addresses the introduction to the concepts of stress and strain, and the state of axial loading. The second block deals with elements subjected to pure torsion. The third block describes pure bending, typical of beams. The fourth block refers to multiaxial stress, combined load, pressure vessels and design failure criteria.

Performance indicators

The performance of the student is evaluated with quantifiable indicators, related to the competences, which provide a global assessment of his understanding of the subject. These are:

• Identifies the type of load produced by a force or a moment applied on a machine or structural element and evaluates the corresponding stress and deformation. • Recognizes the differences between the different types of stresses and deformations that appear in elastic problems. • Identifies the critical point where the highest stresses occur in any mechanical element subjected to several types of load simultaneously. • Calculates the principal stresses, maximum shear stress and equivalent normal stress at the critical point of any element subjected to different types of external load, according to a specified failure theory.

Design of the tool

In this section, the thematic and evaluative content of the course is identified, as well as the parameters that can be varied to generate multiple versions of the same exercises without modifying their knowledge structure. To carry out this process the following steps were followed: Definition of the learning objective: to be able to define the exercise that is going to be proposed, we must know what we want to achieve with it, i.e., identify the cognitive competences that the student must acquire during the course. Here, we refer back to the competences listed in section 2.1.

Definition of the exercises: a review of the curriculum of the subject Mechanics of Materials must be done, and the main topics of the subject are identified: axial loading, bending, torsion and combined load. After considering the thematic content, the bibliography presented by the teachers is reviewed in order to look for the most representative exercises. For each topic, a set of exercises is proposed in order to cover the main knowledge components of the cognitive competences.

Solution and generalization of the exercise: the selected exercises must be solved to create a base algorithm that follows the steps taken to obtain the answer, in order to generate several versions of the same problem by modifying certain parameters but preserving the knowledge component. We define and bound the parameters that can vary to enforce randomness in the data of the problem. In Table 1 we can see an example of the design of an exercise that was included in the software database.

The problem template in Table 1 considers the following points: (i) the topic and objective of the exercise describing the knowledge component, (ii) the problem statement where the questions to be answered are proposed, (iii) the list of parameters acting as variables of the problem, i.e., the problem data randomly generated by the software that must have a previously defined range to avoid errors in the answers, (iv) a general solution for the exercise is developed, which allows to code the exercise easily.

Software implementation

There are many advantages of developing the program as web software. It is multiplatform and the student can use it from any electronic device. This approach is convenient as it makes the tool accessible from virtually anywhere, in agreement with mobile learning (m-learning) statement of students using mobile devices at their time convenience. The tool allows the teacher to use it to do quizzes and workshops. Any student will be able to propose new exercises, facilitating communication with the teacher and feeding the database to increase the knowledge base.

Due to the requirements of the software, especially the one focusing on facilitating the process for users with poor programming experience, there is a need to use an expression analyzer. An expression analyzer is an algorithm that interprets a mathematical expression with pre-established functions, assigns values to each of the variables that intervene in the expression, and gives a numerical answer, see Figure 1. This condition speed up the task of introducing new exercises to the database, since instead of programming the algorithm, the existing one can be quickly modified to the required needs. Thus, the expression analyzer is used to separate the coding of the exercises from the main routines, without it, the software was conditioned to a person making a particular code for each of the exercises.

Table 1. Problem template of an exercise for axial loading.

Topic: Axial loading. Objective: Determination of normal stress in the two-forces structural elements.

Problem statement:

There is a machine consisting of two tongs that support a cylindrical element, as shown in the figure .  • Determine the normal stress developed in the link AB. • Determine the shear stress developed on pin A, consider that it is subjected to double shear. Note: Units are given in international system, SI. After performing a search on the web, we found a previously coded expression analyzer with Lesser General Public License (LGPL) [START_REF] Parra | Evaluador de Expresiones Algebraicas II[END_REF]. This analyzer allows simplifying the template definition for the proposed problems. Equations obtained during the solution steps are introduced in the template to parametrize the solution of the problem with random input.

Parameters

The software was implemented in the proprietary platform COMA (http://calumet.github.io/) [START_REF] Calumet | [END_REF] used as the Learning Management System (LMS) at the School of Engineering. The software was codified in the programming languages Java and JavaScript, to follow a multiplatform (Linux, Windows, Android, Mac) approach. In addition, the HTML language was used for the presentation of the contents. The database of exercises can be constantly updated since anyone with access to the platform can propose problems. The database contains different types of questions, i.e., multiple choice, calculated, true/false, matching, and essay. As indicated before, the focus is on the development of calculated questions for problems centered in the process. One key feature that is proposed in this implementation is that values are recalculated with the input values given in previous steps during the process of solving the problem. This segmentation of the process allows assessing the competences of the student independently. For the specific case of problems related to Mechanics of Materials, it evaluates the statics, the geometry, the stress and the strains calculations, all in different steps, regardless of whether the student failed a previous step. The software offers two services: (i) Training: The teacher creates a workshop by setting the number of problems and the stipulated time to develop them. As the software has the option to review answers, the student can solve the exercise as many times as he wants, monitoring their results, until he is sure the procedure is correct. This improved feedback is required for effective formative assessment [START_REF] Sadler | Formative assessment and the design of instructional systems[END_REF], and it is extremely difficult with mainstream education, (ii) Evaluation: The teacher previously creates an exam, setting a number of problems and an adequate time to solve them, and takes the students to a computer room in order for the students to carry out the activity.

Figure 2 shows a flow diagram with the internal process that is carried out when the teacher introduces a query of the type "create questions with expressions" in the system. For a teacher to include a question in the software, he must add the statement and the problem image, followed by the data and the mathematical equations to develop the exercise, then he chooses which expressions will be used as answer. Figure 3 shows snippets for the definitions of variables and expressions in the code. When the student works on a workshop and presses the review option, the program follows a series of internal steps to show him if the answers are correct. This sequence consists in taking the randomly generated data and calculating the solution to the defined mathematical equations. After that, the software compares the values of the expressions indicated as answers with the values entered by the user, showing in red the boxes with wrong answers and in green the boxes with correct answers.

Conclusions

We presented the development of a multiplatform software tool to be used for the training and assessment of students of the subject Mechanics of Materials. The tool, implemented in Java, JavaScript and HTML, randomly generates exercises based on a parametric definition of the problems. The solution is calculated and compared with the answer given by the students and can be used to train or mark their performance. The problems are segmented into steps based on the knowledge base and the competences to be evaluated. The software is initially focused on the subject Mechanics of Materials, but it is easily extensible to other problem-based engineering subjects. By reviewing the answers, the student can check their errors and repeat the process in order to obtain effective feedback in the formative assessment process. This tool is based in innovative teaching strategies that seek to favor a teaching based on the active participation of the student. Moreover, it provides a standardized marking system that could be used across campuses and groups, reducing heterogeneities for large numbers of students due to subjective marking and non-uniform content.

Figure 1 .

 1 Figure 1. Basic algorithm of the expression analyzer.

Figure 2 .

 2 Figure 2. Basic algorithm for "create questions with expressions".

Acknowledgments

We acknowledge the support given by the group Calumet, Alejandro Riaño, and Luis Ignacio González Ramírez.

[{ "type": "variable", "variable": "b", "description": "L [m]", "min": "1.5", "max": "2.8", "value": "" }, … { "type": "variable", "variable": "z", "description": "Area bar AB [m]", "min": "0.001", "max": "0.002", "value": "" }, … { "type": "expresion", "variable": "g", "expression": "a/(2*sen(p*e/180))", "description": "R", "answer": false, "value": "" }, … { "type": "expression", "variable": "l", "expression": "k/z", "description": "Admissible shear stress AB", "answer": true, "value": "" }] Figure 3. Snippets of the array definition in JSON for the problem in Table 1, for variables and expressions.


Elie Noumon Allini

Maciej Skórski
email: maciej.skorski@gmail.com

Oto Petura

Florent Bernard

Marek Laban
email: marek.laban@micronic.sk

Viktor Fischer
email: fischer@univ-st-etienne.fr

Evaluation and monitoring of free running oscillators serving as source of randomness

Keywords: Physical source of randomness, physical RNG, stochastic model, entropy

In this paper, we evaluate clock signals generated in ring oscillators and self-timed rings and the way their jitter can be transformed into random numbers. We show that counting the periods of the jittery clock signal produces random numbers of significantly better quality than the methods in which the jittery signal is simply sampled (the case in almost all current methods). Moreover, we use the counter values to characterize and continuously monitor the source of randomness. However, instead of using the widely used statistical variance, we propose to use Allan variance to do so. There are two main advantages: Allan variance is insensitive to low frequency noises such as flicker noise that are known to be autocorrelated and significantly less circuitry is required for its computation than that used to compute commonly used variance. We also show that it is essential to use a differential principle of randomness extraction from the jitter based on the use of two identical oscillators to avoid autocorrelations originating from external and internal global jitter sources and that this fact is valid for both kinds of rings. Last but not least, we propose a method of statistical testing based on high order Markov model to show the reduced dependencies when the proposed randomness extraction is applied.

Introduction

In modern cryptographic systems, security is based on the statistical quality and on the unpredictability of confidential keys. These keys are generated in random number generators (RNGs) using random physical phenomena that occur in the hardware devices in which the system is implemented. A widespread source of randomness in digital devices is the jitter of the clock signal generated inside the device using free running oscillators such as ring oscillators [START_REF] Sunar | A provably secure true random number generator with built-in tolerance to active attacks[END_REF][START_REF] Baudet | On the security of oscillatorbased random number generators[END_REF][START_REF] Rozic | Highly efficient entropy extraction for true random number generators on FPGAs[END_REF], or self-timed rings [START_REF] Cherkaoui | A self-timed ring based true random number generator[END_REF].

The statistical quality and unpredictability of the generated numbers depend on the size and quality (e.g. the spectrum) of the clock jitter. It is therefore good practice to continuously monitor this jitter using an embedded jitter measurement method. As required in the document AIS-20/31 published by the German Federal Office for Information Security (German acronym BSI) [START_REF] Killmann | A proposal for: Functionality classes for random number generators, version 2.0[END_REF], the measured jitter parameters should then be used as input parameters in the stochastic model used to estimate entropy, which characterizes the unpredictability of generated numbers.

Generally, many sources of randomness contribute to the overall entropy rate at the output of the RNG based on free running oscillators [START_REF] Valtchanov | Characterization of randomness sources in ring oscillator-based true random number generators in FPGAs[END_REF]:

1. Secure sources -random sources such as thermal noise, which are considered to be the best sources of randomness, because of their large and almost uniform signal spectrum similar to white noise, they are mutually independent, and unavoidable (i.e. they cannot be manipulated by the attacker);

2. Security critical sources -random sources such as low frequency noises that feature some autocorrelation, which reduces the entropy rate at the generator output, while making entropy estimation very complex because of long term dependencies;

3. Dangerous sources -environmental, data dependent and correlated sources, which can be random or deterministic. Their contribution to random number generation must be avoided by the design, since they can be manipulated. If the manipulation cannot be avoided, it must at least be detectable through dedicated embedded tests.

In practice, most (and sometimes all) of these sources of randomness coexist. This would not be a big security issue if: 1) only the contribution of secure sources were taken into account when estimating the entropy rate; 2) the generated numbers were impossible to manipulate.

In [START_REF] Sunar | A provably secure true random number generator with built-in tolerance to active attacks[END_REF], Sunar et al. use an urn stochastic model to estimate the entropy rate at the output of the generator using a huge number of ring oscillators, which the authors claimed were independent. However, the model does not account for possible dependencies between the outputs of the ring oscillators, which can even cause the rings to lock [START_REF] Costea | Implementation of ring oscillators based physical unclonable functions with independent bits in the response[END_REF].

In [START_REF] Baudet | On the security of oscillatorbased random number generators[END_REF], Baudet et al. propose a comprehensive stochastic model for an elementary oscillator based random number generator sampling the jittery clock signal. In their model, the entropy rate at the generator output is estimated from the variance of the random jitter component that originates from the thermal noise.

The output numbers generated by both generators may be biased depending on the duty cycle of the sampled signal(s). Although both generators use the clock signal generated in the rings as a source of randomness, only the model proposed by Baudet et al. estimates the entropy rate from the jitter component originating from the thermal noise and consequently avoids overestimating entropy.

Evaluating the contribution of thermal and low frequency noises to the generated randomness is no simple task. In [START_REF] Haddad | On the Assumption of Mutual Independence of Jitter Realizations in P-TRNG Stochastic Models[END_REF], Haddad et al. computed the variance of the jitter for different accumulation times and then computed the jitter component originating from the thermal noise by curve fitting. This method has two disadvantages: 1) its precision depends to a great extent on the precision of the curve fitting algorithm; 2) it is not suitable for monitoring the jitter inside the device.

In [START_REF] Fischer | Embedded evaluation of randomness in oscillator based elementary trng[END_REF], Fischer and Lubicz proposed a method of evaluation of the variance of the random jitter originating from the thermal noise that can be embedded in logic devices and hence used for online evaluation of the entropy rate at the output of the generator. However, depending on the initial phase of the two clock signals and the jitter accumulation time, the method can produce incorrect results. The error can be corrected by using different accumulation times, but it is not easy to make this correction automatic.

In [START_REF] Killmann | A Design for a Physical RNG with Robust Entropy Estimators[END_REF], Killmann and Schindler used a pair of noisy diodes as a source of randomness and an operational amplifier, a Schmitt trigger and a counter of edges as a time-to-digital converter transforming the noise into the raw binary signal. Surprisingly, the time-to-digital conversion based on counters had not been previously studied in the context of the use of free running oscillators.

Our contributions: 1) We show that counting the periods of the jittery clock signal, representing a time-to-digital conversion, gives random numbers of significantly better quality than the methods based on sampling the jittery signals. What is more, the counter values can be used to characterize and to continuously monitor the source of randomness. 2) We propose to use Allan variance of counter values instead of the commonly used statistical variance to evaluate the jitter, since it is not sensitive to low frequency components of the jitter originating from low frequency noises, such as flicker noise, which are known to be autocorrelated. The proportion of thermal noise in the total jitter can thus be more easily measured inside the device with no error or overestimation. 3) We demonstrate that by using two identical rings instead of one ring and one quartz oscillator, the impact of not only external, but also of internal global jitter sources can be significantly reduced and render the generator much more robust. 4) We propose to use a statistical method based on a high order Markov model and show how efficient it is in detecting dependencies and correlations in low quality generators.

The paper is organized as follows: in Section 1, we provide the theoretical background and analyze state-of-the-art methods related to our approach. In Section 2, we describe the experimental setup and analyze the impact of the type of the oscillator on the commonly used statistical variance and on Allan variance. In Section 3, we present the results of implementation of variance computation circuitries in hardware and discuss the impact of the measurement circuitry and of the additional logic represented by an AES cipher on the source of randomness in Section 3.2. In Section 4, we discuss the main results. We present our conclusions in Section 5.

Theoretical background

In purely digital devices, which are currently used to implement cryptographic systems, analog noise signals such as thermal noise cannot be directly exploited. Instead, the designer can use the fact that electrical noises are transformed in free running oscillators into uncertainties in timings of generated digital clock signals, which can be observed as a jitter in the time domain and as a phase noise in the frequency domain [START_REF] Da Dalt | Understanding Jitter and Phase Noise[END_REF].

In logic devices, the most frequently used free running oscillators are ring oscillators (ROs) and self-timed rings (STRs), because both are easy to implement using standard logic gates. ROs are usually composed of an odd number of inverters as shown in the top panel of Fig. 1 (a) or a NAND gate and a sufficient number of non-inverting buffers, as shown in the bottom panel of Fig. 1 (a). In ROs, which are also called single-event ring oscillators [START_REF] Nishio | Oscillator Circuits: Frontiers in Design, Analysis and Applications[END_REF], only one event (the rising or falling edge of the clock signal) propagates at any given time in the ring. Its propagation time is impacted by noises that modify the slope of the rising and falling edges and the reference voltage of inverters (or buffers).

In STRs, also called multi-event oscillators without signal collision, several events can propagate over the ring at the same time. The STR is composed of L stages, each consisting of a Müller gate and an inverter (see Fig. 1 (b)) [START_REF] Nishio | Oscillator Circuits: Frontiers in Design, Analysis and Applications[END_REF]. F i is the forward input of the i-th stage, R i is the reverse input of the same stage, and C i is the output of the stage. If the forward and reverse input values differ, the forward input value is written to the stage output. Otherwise, the previous output value is maintained.

Ring oscillators are simpler and hence less expensive than STRs, so many rings can be used to increase entropy [START_REF] Sunar | A provably secure true random number generator with built-in tolerance to active attacks[END_REF]. STRs are more complex, but multiple outputs of the same ring can be used to increase entropy [START_REF] Cherkaoui | A very high speed true random number generator with entropy assessment[END_REF].

The randomness originating from electrical noises, which is transformed in the free running oscillators into a clock jitter, can be further transformed into random numbers obtained as a chain of 1-bit or n-bit random values by: 1) sampling the jittery clock signal(s) after a sufficiently long time interval required for entropy accumulation as shown in Fig. 2 (a) [START_REF] Sunar | A provably secure true random number generator with built-in tolerance to active attacks[END_REF], [START_REF] Baudet | On the security of oscillatorbased random number generators[END_REF]; 2) by counting the periods of the jittery clock signal during the time interval as shown in Fig. 2 (b) [START_REF] Kohlbrenner | An embedded true random number generator for FPGAs[END_REF].

While the first method based on sampling may be preferred because of its simplicity, it is very sensitive to dependencies between the clock signals and also to the duty cycle of the sampled clock signal, which can cause a significant bias in the generated numbers [START_REF] Baudet | On the security of oscillatorbased random number generators[END_REF].

F 1 F 2 F L R 1 R 2 R L C 1 C 2 C L V 1 V 2 V 3 V 1 V 2 V 3 ena F 1 F 2 F L R 1 R 2 R L C 1 C 2 C L a) b)
s 1 s 2 m-bit counter l-bit raw random signal (l < m) ena Q clk s 1 (a) (b) clk Counter of k periods s 2 FRO 2 FRO 1 FRO 2 FRO 1
Although the second method based on counting the periods of the jittery clock signal adds some complexity to the RNG design, we will show that it effectively removes dependencies between the clock signals by transforming random events from the time domain to the frequency domain, and even removes the dependence of generated numbers on the duty cycle of the jittery clock signal. We will also show that the counter can be used as a basis for dedicated embedded tests.

In the following sections, we will demonstrate and justify the relationship between the measured variance of counter values and that of the jitter present in clock signals s 1 and s 2 .

Characterization of the source of randomness by a statistical variance -a pitfall

Statistical variance characterizes the deviation of a random variable from its mean value. More precisely, if X is a square-integrable random variable, then its statistical variance can be computed as [START_REF] Žitković | Introduction to stochastic processes -lecture notes[END_REF][START_REF] Cooper | Probabilistic Methods of Signal and System Analysis[END_REF][START_REF] Engelberg | Random signals and noise: a mathematical introduction[END_REF]:

Var(X) = E X 2 -(E(X)) 2 (1)
where E denotes the statistical average. The estimate of this variance on a set of M samples {x i } 1 i M , is given as [START_REF] Riley | Handbook of Frequency Stability Analysis[END_REF]:

Var(X) = 1 M M i=1 x 2 i - 1 M M i=1 x i 2 .
(2)

Limitations of statistical variance in the presence of low frequency noises

We denote the output frequency of the oscillator under study by ν(t). The fractional frequency of the output is defined as:

y(t) = ν(t) -ν 0 ν 0 , ( 3
)
where ν 0 is the nominal frequency of the oscillator.

In oscillators, random fluctuations are often characterized by the power law spectrum [START_REF] Allan | A Modified "Allan Variance" with Increased Oscillator Characterization Ability[END_REF]:

S y (f ) = h α f α , ( 4
)
where f is the Fourier frequency, h α the intensity of the particular noise process and α a constant that characterizes this process. The typical values of α, with corresponding noise types, that often appear in the literature are +2 (white noise phase modulation), +1 (flicker noise phase modulation), 0 (white noise frequency modulation), -1 (flicker noise frequency modulation) and -2 (random walk frequency modulation). Knowing that random fluctuations are due to the above mentioned types of noises, the power spectral density of y can be expressed as [START_REF] Uhrich | Stabilité des oscillateurs ultra-stables[END_REF]:

S y (f ) = 2 α=-2 h α f α . ( 5
)
Under the assumption that y is a zero-mean stationary random process, its statistics do not change over time. This implies that y is an infinite signal that can only be observed through a time window defined by the function h τ . The observed signal y τ can then be considered as the response of a filter, with the impulse response h τ , to the random input y. The power spectral densities of y and y τ are therefore related by [START_REF] Cooper | Probabilistic Methods of Signal and System Analysis[END_REF]:

S yτ (f ) = S y (f ) |H τ (f )| 2 , ( 6
)
where H τ is the Fourier transform of h τ . Based on the Wiener-Khinchin theorem, the autocorrelation function of y τ can then be computed as [START_REF] Cooper | Probabilistic Methods of Signal and System Analysis[END_REF]:

R yτ (ξ) = +∞ -∞ S yτ (f )e i2πξf df = +∞ -∞ S y (f ) |H τ (f )| 2 e i2πξf df. ( 7
)
Because the process has zero mean, the variance is the autocorrelation function, evaluated at 0, hence [START_REF] Riley | Handbook of Frequency Stability Analysis[END_REF]:

Var(y) = E y 2 = E y 2 τ = +∞ -∞ S y (f ) |H τ (f )| 2 df. ( 8
)
The choice of h τ reveals how samples of the signal y are used in the variance computation. Since in the case of statistical variance, we are interested in consecutive samples, the corresponding time window has the form depicted in Fig. 3.

The magnitude squared transfer function of the statistical variance is thus [START_REF] Uhrich | Stabilité des oscillateurs ultra-stables[END_REF]: The statistical variance of the signal can then be expressed as:

|H τ (f )| 2 = sin πτ f πτ f 2 . ( 9
) t h τ (t) τ 1/τ
Var(y) = 2 α=-2 h α (πτ ) 2 f h 0 f α-2 sin 2 (πτ f )df, ( 10
)
where f h is the cutoff frequency of the oscillator. In Eq. ( 10), the integrand is equivalent to π 2 τ 2 f α as f → 0. The Riemann criterion therefore shows that the integral does not converge for α = -1 and α = -2 corresponding to low frequency noises. Consequently, it is not possible to compute the variance when the data is affected by low frequency noises. In other words, statistical variance should not be used when low frequency noises are not negligible.

Riemann criterion for improper integrals

For this reason, it is recommended to use other types of variance that converge in the presence of low frequency noises [START_REF] Riley | Handbook of Frequency Stability Analysis[END_REF][START_REF] Allan | Should the classical variance be used as a basic measure in standards metrology?[END_REF]. One example of this type of variance is the Allan variance, which is widely used to study the frequency stability of clocks and oscillators [START_REF] Allan | Statistics of atomic frequency standards[END_REF]. Next, we will show that the Allan variance should also be preferred in entropy rate estimation.

Allan variance

We recall that y denotes the fractional frequency of the oscillator. Thus, the average fractional frequency is defined as:

y(t) = 1 τ t+τ t y(u)du. ( 11
)
It corresponds to the average frequency deviation over a time interval of length τ . If the frequency data are acquired periodically with a sampling period of τ , the obtained fractional frequency series is denoted (y i ), where y i is the i th acquired sample. The Allan variance of the frequency deviation of y is then defined as [START_REF] Allan | A Modified "Allan Variance" with Increased Oscillator Characterization Ability[END_REF]:

σ 2 y (τ ) = 1 2 E y i+1 -y i 2 . ( 12
)
We denote Avar(y) the Allan variance of y as in [START_REF] Riley | Handbook of Frequency Stability Analysis[END_REF]. An estimate of this variance in a data set comprised of M average fractional frequency samples, is given as [START_REF] Riley | Handbook of Frequency Stability Analysis[END_REF]:

Avar(y) = σ 2 y (τ ) = 1 2(M -1) M -1 i=1 y i+1 -y i 2 . ( 13
)

Convergence in the presence of low frequency noises

Unlike statistical variance, the Allan variance computes the difference of consecutive samples. This yields the time window presented in Fig. 4, with a magnitude squared transfer function given by: This makes it possible to write the signal variance as:

|H τ (f )| 2 = 2 sin πτ f πτ f 2 sin 2 πτ f. ( 14
) t h τ (t) -τ τ 1/2τ -1/2τ
Avar(y) = σ 2 y (τ ) = 2 α=-2 2h α (πτ ) 2 f h 0 sin 4 (πτ f )f α-2 df. ( 15
)
In this new case, the integrand is equivalent to π 4 τ 4 f α+2 as f → 0. The Riemann criterion for f → 0 ensures that this integral converges when α > -3, and thus guarantees the accuracy of the Allan variance, even when the data are affected by low frequency noises (α = -1 and α = -2).

Next, we present the general properties of the Allan variance. Readers interested in the proofs of these properties should refer to Appendix A.

Theorem 1 (General properties of the Allan variance).

1. The Allan variance coincides with the statistical variance of any stationary and uncorrelated random process.

2. If λ is a real number and x is a stationary random process, then λx is also a stationary random process and:

Avar(λx) = λ 2 Avar(x). ( 16
)
3. If x and y are two independent stationary random processes, the following equation is valid:

Avar(x + y) = Avar(x) + Avar(y). ( 17
)
Since the measurement principle of the jitter is based on counter values, the properties of the Allan variance presented here will be used to establish the link between the variance of counter values and the variance of the jitter.

Link between the variance of counter values and of the jitter

We assume that both s 1 and s 2 contain jitter that causes variations in counter values. Before using the variance of a population of counter values as a measure of quality of the source of randomness, we need to determine and justify the relationship between this variance and the variance of the jitter on both signals s 1 and s 2 .

As mentioned above, the counter values are obtained by counting the number of periods of the measured clock signal s 1 during a time interval τ defined by the reference clock signal Of course, in practice, both signals feature a jitter, however, to simplify the computation, we include the jitter of signal s 1 in that of signal s 2 as done in [START_REF] Baudet | On the security of oscillatorbased random number generators[END_REF]. Consequently, the period T 2 of signal s 2 can be considered as a random variable of standard deviation (see [2, Appendix C]):

s 2 τ = k r=1 T 2r s 1 T1 N T1 1 T1 2 ϕ 0
σ eq σ 2 2 + T 2 T 1 σ 2 1 , ( 18
)
and the period T 1 of signal s 1 as a constant. The measurement time τ = k r=1 T 2r is thus a random variable. This time defines only the length of the time period, not the position of the initial phase ϕ 0 of the signal s 1 when the measurement (the counting) starts (see Fig. 5). However, to measure the jitter more accurately, the initial phase ϕ 0 has to be taken into account. This initial phase is independent of τ , since its value does not depend on the length τ .

Because T 1 is constant, the counter value N is a random variable defined as:

N := max k ∈ N, ϕ 0 + k r=1 T 1r τ = max {k ∈ N, ϕ 0 + kT 1 τ } . ( 19
)
The value N thus satisfies the inequality:

ϕ 0 + N × T 1 τ < ϕ 0 + (N + 1) × T 1 , (20)
which is equivalent to:

N τ -ϕ 0 T 1 < N + 1. (21)
It then follows that N can be written as:

N = τ -ϕ 0 T 1 . ( 22
)
It thus exists 0 ε < 1 such that:

N = τ -ϕ 0 T 1 -ε ( 23
)
According to Sheppard's correction [START_REF] Sheppard | On the Calculation of the most Probable Values of Frequency-Constants, for Data arranged according to Equidistant Division of a Scale[END_REF], ε is a random variable that is uniformly distributed over [0, 1). Since it is independent of τ -ϕ0 T1 , using Eq. ( 16) and ( 17) from Theorem 1, the following equation holds:

Avar(N ) = Avar τ -ϕ 0 T 1 + Avar(ε) = Avar(τ ) + Avar(ϕ 0 ) T 2 1 + 1 12 . ( 24
)
It is important to note that the Allan variance of counter values always overestimates the Allan variance of the jitter per unit of time (e.g the signal period). The correction must be applied by subtracting Avar(ε) = 1 12 and Avar(ϕ0)

T 2 1 .
As Avar(ϕ0)

T 2 1 ∈ 0, 1 12
(the maximum is obtained if ϕ 0 is uniformly distributed over [0, T 1 )), according to Eq. ( 24), Avar(τ ) = T 2 1 Avar(N )-

T 2 1 12 -Avar(ϕ 0 ) ≥ T 2 1 Avar(N )- T 2 1 12 - T 2 1
12 . As we do not want to overestimate the jitter, a conservative approach is to take the minimum value for Avar(τ ) that is:

Avar(τ ) = T 2 1 • Avar(N ) - T 2 1 6 . ( 25
)
Using Eq. ( 25), the variance of the accumulated jitter can be computed from the variance of counter values. This justifies using counter values to estimate the jitter.

Study and setup of the variance measurement

To study the difference between statistical variance and the Allan variance in different conditions, we first implemented the circuit presented in Fig. 2 (b) in the hardware. Four different hardware configurations were tested in an Intel Cyclone V FPGA:

• Configuration 1: Signal s 1 of 127 MHz was generated in an RO and signal s 2 came from a low jitter quartz oscillator generating a stable 125 MHz clock.

• Configuration 2: Both signals (s 1 and s 2 ) were generated in two ROs with the same number of elements, oscillating at a frequency of 125 and 127 MHz, respectively.

• Configuration 3: Signal s 1 of 128 MHz was generated in an STR and signal s 2 came from a low jitter quartz oscillator generating a stable 125 MHz clock.

• Configuration 4: Both signals (s 1 and s 2 ) were generated in two STRs with the same number of elements and oscillating at a frequency of 130 and 128 MHz, respectively.

The counter values were sent to a PC via a simple serial interface and evaluated in the software. The jitter accumulation time τ was set up from the PC using the serial link.

To obtain meaningful and reliable embedded measurements, we first needed to establish the right operating parameters. These parameters are k -the number of periods of signal s 2 , which determines the accumulation time τ and M -the number of samples from which the variance will be computed.

We performed a series of variance measurements for different values of M in order to find an acceptable compromise between the measurement time and precision. We used k = 30 000 for this study. Measurement results are shown in Fig. 6.

Figure 6 clearly shows the advantage of the Allan variance: it changes very slightly and only for low values of M , while the statistical variance increases with M and its values fluctuate. This fluctuation occurs because low frequency noises affect the signal periods. We selected M = 4096 as a compromise between the number of statistical data (which impacts the precision of the measurement) and the measurement time. To obtain coherent results, the same values of M were used when measuring variance and Allan variance.

We next studied the impact of the accumulation time τ = k r=1 T 2r on the measured variance. We observed the variances and Allan variances of counter values from two ring oscillators as well as two self-timed rings with k ranging from 300 to several million. The results are presented in Fig. 7 and Fig. 8. We also observed that for low values of k (k < 1 000), the computed variances varied probably because of the quantization noise, rather than random noises. Indeed, for these low values of k, the counter values varied only very slightly.

Last but not least, we observed that for sufficiently high values of k (k > 10 000), the Allan variance was always lower than the statistical variance. This proves that statistical variance overestimates the proportion of uncorrelated noise in the total accumulated jitter.

Accuracy of Allan variance estimation

The sample estimate given in Eq. ( 13) (time-average) approximates the true value1 from Eq. ( 12) (average over process randomness) well, provided that the series is wide-sense stationary and has rapidly decreasing correlations2 [START_REF] Leon-Garcia | Probability, Statistics, and Random Processes for Electrical Engineering[END_REF]. One can think of small correlations as a short memory of the process: substantial new information is gained with every sample, so that the estimate becomes increasingly accurate.

To check the quality of our estimate, we examined the process of counter values (used to compute the variance) and their first differences (used to compute the Allan variance) in more detail. We collected the data from four different hardware configurations, i.e. Configurations 1 to 4 described earlier in this section. All projects used k = 30 000 periods of s 2 to set the counting time. The behavior across all experiments is summarized at high level in Table 1. The autocorrelations were considerably reduced in first differences, as shown in Fig. 9. This confirms that differencing subsequent counter values is a good way of eliminating low frequency components and reducing correlations. Frequency noise in the ring oscillators is modeled by a process with stationary first differences in the theoretical literature 3 [26]; this is consistent with our experiments. More experiments are presented in Appendix B.

Based on our empirical evidence, we assume that the correlation is zero for sufficiently large lags. Under the mild assumption that the difference process is correlated Gaussian, we can bound estimation errors in the Allan variance computations (quantifying convergence

rate). More precisely, we assume

Model assumption: The process of counter differences is stationary normal, with zero correlations for lags larger than p.

The technical result and the corrolary regarding Allan variance are given below. Lemma 1. Let Z = {Z i } be a zero-mean stationary normal process with autocorrelation function zero for lags larger than p. Then for large M we have

Var 1 M M i=1 Z 2 i = O(p/M ),
in particular

1 M M i=1 Z 2 i -→E(Z 2 ) in probability.
By applying Lemma 1 to the differences of counter values ∆ȳ i = ȳiȳi-1 we obtain Corollary 1 (Consistency of Allan variance estimation 4 ). Under the chosen model, the Allan variance estimate 13) is asymptotically (for large M ) unbiased and consistent, with variance O(p/M ).

1 2(M -1) M i=1 (∆ȳ i ) 2 in Eq. (

Evaluation of randomness in counter values

We propose to use the least significant bit of the counter values (or of their first difference) as random values. To evaluate the quality of the generated sequence, we model dependencies between subsequent bits by higher-order Markov chains. First, we recall some basics on Markov chains in order to introduce the theorem used to compute the min-entropy rate, which is more conservative than the Shannon entropy rate. We then empirically (based on data generated under different hardware configurations) compare our evaluation technique with the entropy estimation methods in AIS31 and NIST 800-90B.

Theoretical Background

Model The Markov chain model of order d assumes a sequence of random variables {U i } i over the common state space S (S = {0, 1} in our case), such that:

• the next state distribution depends only on previous d states (short memory)

Pr[U i |U i-1 , U i-2 , . . . , U 0 ] = Pr[U i |U i-1 , U i-2 , . . . , U i-d ],
• the next state distribution is a function of state values (that are time homogeneous)

Pr[U i = u i |U i-1 = u i-1 , U i-2 = u i-2 , . . . , U i-d+1 = u i-d+1 ] = f (u i ; u i-1 , . . . , u i-d+1 ).
Reduction of a chain of order d to a first order chain A Markov chain of order d can be reduced to a chain of order 1 by introducing the sliding window of length d. More precisely, if {U i } i is a Markov chain of order d with the set of possible states S then the blocks

W i = (U i , U i-1 , . . . , U i-d+1 ) form a Markov chain of order 1 with states S d = S × . . . × S d .
The transition matrix can be then estimated by counting the transitions between subsequent states (blocks); namely P v,w = #{i:Wi=w and Wi-1=v}

#{i:Wi-1=v}
is the transition probability from v to w. In our case U i are bits and the assumed order is 8, thus the transformed chain W i has states {0, 1} 8 and the transition matrix has the size 2 8 × 2 8 .

Min-entropy rate Entropy rates (understood as the entropy per bit in long sequences) can generally be computed from the transition matrix. However, computation of the min-entropy rate is more complicated than that of the Shannon entropy and does not have a closed-form formula. We refer the reader to [START_REF] Kamath | Estimation of entropy rate and renyi entropy rate for markov chains[END_REF] for a detailed discussion of how different definitions of entropy (Shannon entropy, Renyi entropy, min-entropy) can be computed using Markov chains; below we state the result for min-entropy.

A sequence of states s 1 , . . . , s +1 is called a loop if s 1 = s 2 = . . . = s and s 1 = s +1 , where is the length of the loop. The min-entropy rate is then determined as follows.

Theorem 2 (Min-entropy rate of Markov chains [START_REF] Kamath | Estimation of entropy rate and renyi entropy rate for markov chains[END_REF]). Let P be the transition matrix of an irreducible and aperiodic Markov chain with the state space S. Then H ∞ (P ) = min min (s1,...,s +1 )∈C

1 k=1 log 1 P s k ,s k+1 ( 26
)
where C denotes the set of all loops of length and P s k ,s k+1 the probability of the transition from state s k to state s k+1 .

Implementation

Language We implemented the procedure to estimate the min-entropy rate of a Markov chain in Python; to increase the speed, parts of the code were compiled to C by the Cython module. For computation, we used the Numpy library with double precision (64 bits).

Algorithmic issues Computation of the transition matrix requires one pass on the data file. The value in Eq. ( 26) is found by dynamic programming; namely, for every and every pair of states s , s we compute r(s , s , ) = min s1=s ,s2,...,s -1 ,s =s

k i=1 log 1 Ps k ,s k+1
where s 1 , . . . , s -1 are different; dynamic programming is used to update values of r when changing from to + 1. Once we have these numbers, we can determine the value in Eq. [START_REF] Greenhall | A Structure Function Representation Theorem with Applications to Frequency Stability Estimation[END_REF]. Because the formula assumes different states s 1 , . . . , s we have that |S|. Computing all r(s , s , ) for s ∈ S, s ∈ S and |S| requires a memory size of about |S| 3 multiplied by the size of the float placeholders.

Parameters Based on the dependencies indicated by the results of the autocorrelations, we decided to use d = 8. We therefore study transitions between blocks of consecutive d = 8 bits, and the size of the transition matrix is 2 8 × 2 8 .

Experiments on the generation of random bit streams from free running oscillators

In our experiments on the generation of random numbers using free running oscillators, we wanted to compare randomness extraction using the two methods presented in Fig. 2. We analyzed the output values of the sampler from Fig. 2 (a) and the least significant bit of the counter values from Fig. 2 (b) (and their first differences). We thus analyzed the outputs of four projects.

• The first two projects used the method of entropy extraction based on sampling the jittery clock signal (according to Fig. 2(a)) with two kinds of oscillators used as a source of randomness:

signals s 1 and s 2 were generated by two ROs oscillating at 125 and 127 MHz, signals s 1 and s 2 were generated by two STRs oscillating at 130 and 128 MHz.

• The other two projects used the counter method of entropy extraction (according to Fig. 2(b)), while using the same oscillators as the first pair of projects.

For the method of extraction based on sampling of the jittery clock signal, we generated random bit streams for k ranging from 10 000 to 100 000. For the counter method of extraction we generated sequences for k ranging from 2 000 to 100 000. Two kinds of files were generated in this case -one containing the least significant bits of the counter values and the other containing the least significant bit of the first differences of counter values. We tested all the generated sequences using the AIS31 Procedure B (tests T6 -T8) and NIST 800-90B test suite, from which we also obtained Shannon entropy and min-entropy estimates respectively. The min-entropy was computed for every sequence according to Eq. ( 26), i.e. the computation was based on high order Markov chains while taking correlations between output bits into account. The results are presented in Appendix D, Table 5 to 10.

Three very important results stand out in the tables presented in Appendix D. First, the method of randomness extraction based on sampling of the jittery clock signal always gives lower entropy rates than those obtained by the method based on counting the jittery clock signal periods. Second, the method of min-entropy estimation based on high order Markov chains gives very consistent results even in the interval of values of k, for which Procedure B of AIS31 revealed no differences in Shannon entropy estimates. Third, the entropy rates are practically the same when the least significant bit of the counter values or that of their differences is used. This is valid independently of the type of free running oscillator (RO or STR).

Implementation of the variance measurements in hardware and monitoring of the source of randomness

According to AIS 31 recommendations, the source of randomness should be monitored continuously using dedicated embedded test(s). In our case, this monitoring process would be represented by an online check that the differences of counter values fall within the permitted interval.

To compare the parameters of the proposed randomness monitoring process, we implemented tests based on counter differences and two other state-of-the-art tests (proposed in [START_REF] Haddad | On the Assumption of Mutual Independence of Jitter Realizations in P-TRNG Stochastic Models[END_REF] and [START_REF] Fischer | Embedded evaluation of randomness in oscillator based elementary trng[END_REF]) in the same device -Intel Cyclone V FPGA.

The circuitry corresponding to implementation of the Allan variance according to Eq. ( 13) in hardware is shown in Fig. 10. 13) All the computations are in fixed point arithmetic. This method only requires one multiplier to square data. One subtractor is used to compute the difference of the consecutive samples and one adder with associated register is used as accumulator.

Var(cnt)
The circuitry corresponding to hardware implementation of the variance computation used by Haddad et al. in [START_REF] Haddad | On the Assumption of Mutual Independence of Jitter Realizations in P-TRNG Stochastic Models[END_REF] and for the one corresponding to Eq. ( 2) is depicted in Fig. 11. [START_REF] Haddad | On the Assumption of Mutual Independence of Jitter Realizations in P-TRNG Stochastic Models[END_REF] and for that corresponding to Eq. ( 2)

Again, all the computations are in fixed point arithmetic. Numbers before and after the radix point indicate the number of bits of the integer and fractional part of the given value, respectively. Two multipliers (one of 12 bits and the other of 24 bits) are used to square data. Two adders and associated registers (one of 24 bits and the other of 12 bits) are used to implement accumulators. One subtractor is used before the output of the block. Four additional data registers are used to store intermediate data.

The third test we implemented in the hardware has the same architecture as that presented in [START_REF] Fischer | Embedded evaluation of randomness in oscillator based elementary trng[END_REF], Fig. 6. In the following section, we compare the three implementations.

Implementation results

First, we evaluate design parameters like area, speed and power consumption of the three methods of variance measurement described above. Area and speed values were obtained from Quartus software. Power consumption was measured using a dedicated hardware evaluation platform [START_REF] Laban | Platform for testing and evaluation of PUF and TRNG implementations in FPGAs[END_REF]. The results are presented in Table 3. We observe that the Allan variance measurement circuitry based on Eq. ( 13) is smaller, faster and consumes slightly less power than the circuitry required by the other two methods. This is because the implementation of the Allan variance measurement is simple (only one subtractor and one adder needed, only one DSP block used instead of two or four, respectively).

Study of the impact of the measurement circuitry on the source of randomness

Next, we propose a rigorous approach to assess the impact of the embedded jitter measurement on the measured jitter itself. The impact of the jitter measurement on the jitter itself is evaluated in the following steps:

• Project 1 -Only two free running oscillators, used as sources of randomness, are implemented in the selected logic device. The generated clock signals are output using low voltage differential signaling (LVDS) outputs and measured externally using high end oscilloscope and differential probes (see Fig. 12). To ensure the measurement results are consistent, it is important to guarantee the same placement and routing of Osc1 and Osc2 in all projects. We generated the Exported Partition file (.qxp), which is the Quartus II software option used to export post-fitting netlists. The exported netlist was then used in all the projects.

We decided to implement only ROs as Osc1 and Osc2 because, as shown in Section 2, they are simpler to implement than STRs and the jitter behavior is very similar in both STRs and ROs. Oscillators Osc1 and Osc2 had the same number of elements and the same topology. They oscillated at respective frequencies of 124.5 ± 0.3 MHz and 126.3 ± 0.2 MHz. The difference in frequency in the three projects was thus less than 1 %, which was important to ensure the results were comparable.

We measured the jitter of both oscillators as well as the normalized counter value externally using a LeCroy WavePro 735i oscilloscope (4 GHz bandwidth, 40 GS/s) and two D420 WaveLink 4 GHz differential probes. Counter values cannot be obtained directly from an oscilloscope since the value of k cannot be set up like in hardware but can only be deduced from the oscilloscope time base, which, in our case, was set to 5 µs per division. We measured the number of periods of both clocks in this time interval. Finally, to make the comparison of values obtained using the external and embedded measurements more consistent, we measured the number of cycles of both clocks at the same time interval and normalized the resulting data according to the following equation:

cnt = n 1 n 2 • k, ( 27
)
where n 1 represents the number of clock periods of s 1 and n 2 the number of clock periods of s 2 that appear during the same time interval determined by oscilloscope's time base. In our case, we used k = 30 000 to normalize oscilloscope measurements.

Table 4 shows the results of external and internal measurements. The jitters of Osc 1 and Osc 2 were both measured by the oscilloscope. To compare these values with those obtained using the Allan variance according to Eq.( 25), we saved the counter values in a file for processing.

Table 4:

Results of external and internal measurements of oscillator jitters in three selected projects: Columns 2 and 3 list the jitters σ 1 , σ 2 measured using the oscilloscope. Column 4 lists the equivalent jitter σ eq computed from Eq. ( 18). Column 5 lists the normalized variance of counter values computed from the oscilloscope using Eq. ( 27). Column 6 lists the Allan variance estimate computed inside the device using Eq. [START_REF] Cherkaoui | A very high speed true random number generator with entropy assessment[END_REF].

Project σ 1 σ 2 σeq [ps] V ar(cnt) Avar(N ) Avar(τ ) [s 2 ] [ps]
[ps] from Eq.( 18) from Eq.( 27) from Eq.( 13) from Eq.( 25) Project 1

3.9 We can see that putting the whole cryptosystem including the AES cipher in an FPGA more than doubles the jitter of both oscillators, but the variance of counter values remains almost the same if only internal oscillators are used. In Project 2, in which the signal s 2 is generated by an external quartz oscillator, there was a significant increase in the variance of counter values, which confirms that using identically implemented oscillators and implementing them both inside the FPGA (differential principle of randomness extraction) helps prevent negative effects of the surrounding logic on the measured jitter.

To further confirm this claim, we acquired a large sequence of counter values from Project 2 and transferred them to a PC in order to visualize them over time. The acquisition was done with the accumulation period set by k = 30 000. The whole acquisition took approximately 30 minutes. Figure 14 shows the counter values when the signal s 2 was generated by an external quartz oscillator. A strong low frequency signal can be seen to affect the counter values. The frequency of the signal is approximately 1.5 mHz. We discovered that the observed low frequency signal originated from the power line even though the evaluation board was using only low noise linear power supplies. These findings confirm that unwanted global noises are almost always present and are unavoidable. Since this kind of noise can be manipulated, it can be extremely dangerous for the TRNG design. Moreover, a low frequency signal such as the one visible in Fig. 14 is usually hard to detect.

Discussion

We have very clearly demonstrated several advantages of the Allan variance over statistical variance: it gives stable values independent of low frequency noises even for short data sets. It is thus suitable for the estimation of entropy originating from non-manipulable independent noises such as thermal noise. It can serve as a basis for embedded tests, for which it is particularly suited because of its small area and low latency.

RO and STR behave similarly in terms of variance dependence on jitter accumulation time. Jitter accumulates in both structures in a very similar way. This is a new observation.

Using two identical oscillators reduces autocorrelations in RNG output values. Using the first differences of counter values instead of counter values themselves further reduces autocorrelations.

The method of randomness extraction based on sampling of the jittery clock signal always gives lower quality results than the method based on counting the jittery clock signal periods. The jitter accumulation times can be reduced more than ten times (more than 400 000 periods of the reference clock were needed in [START_REF] Fischer | Embedded evaluation of randomness in oscillator based elementary trng[END_REF] and fewer than 30 000 if the jittery clock periods are counted). This means significantly higher bit rates at generator output with no loss of entropy.

The method of min-entropy estimation based on high order Markov chains gives very consistent results even in the interval of values of k, for which Procedure B of AIS 31 revealed no differences in Shannon entropy estimates (see Tables 7 to 10).

The studies described here confirm, that using external oscillators jeopardizes the implementation of security critical applications. They also prove, that implementing identical oscillators inside the FPGA and using their relative jitter transformed into counter values or even better into their differences, can efficiently mitigate the negative effects of global noise sources both external to the FPGA and generated internally by the surrounding logic, represented in our case by the AES cipher.

Conclusions

We evaluated the jitter of clock signals generated in ring oscillators and self timed rings and the way the jitter is transformed into random numbers. We showed that counting the periods of the jittery clock signal gives random numbers of significantly better quality than the usual methods of sampling jittery clock signals. We used counter values to characterize and to continuously monitor the source of randomness. We showed that using the Allan variance to characterize the clock jitter has at least two advantages: first, it is not sensitive to low frequency noises such as flicker noise, and second, significantly less circuitry is required for its computation than that used in other methods. We also show that a differential principle of randomness extraction from the jitter, based on the use of two identical oscillators is essential to avoid autocorrelations originating from both the external and internal sources of global jitter, independently of the type of ring used. Last but not least, we propose a new method of statistical testing based on a high order Markov model to demonstrate the reduction of dependencies when the proposed randomness extraction is applied. While providing an estimation of min-entropy, the method is very efficient in detecting dependencies between generated numbers.

A Proofs of the Allan variance properties A.1 Allan variance generalizes the statistical variance

If x is a stationary and uncorrelated random process, we know that its statistical variance exists [START_REF] Allan | Should the classical variance be used as a basic measure in standards metrology?[END_REF]. If we call µ the expected value of x, then:

Avar(x) = 1 2 E (x i+1 -x i ) 2 = 1 2 E [(x i+1 -µ) -(x -µ)] 2 = 1 2 E (x i+1 -µ) 2 -(x i+1 -µ)(x i -µ) + (x i -µ) 2 = 1 2 E (x i+1 -µ) 2 - 1 2 E [(x i+1 -µ)(x i -µ)] + 1 2 E (x i -µ) 2 = 1 2 Var(x i+1 ) - 1 2 E [(x i+1 -µ)(x i -µ)] + 1 2 Var(x i ). ( 28
)
Since x is stationary, one has:

Var(x i+1 ) = Var(x i ) = Var(x) (29)
and:

E (x i+1 ) = E (x i ) = µ. ( 30
)
Moreover, the uncorrelatedness of x implies:

E (x i+1 x i ) = E (x i+1 ) E (x i ) . ( 31
)
It then follows:

E [(x i+1 -µ)(x i -µ)] = E x i+1 x i -µx i+1 -µx i + µ 2 = E (x i+1 x i ) -µ E (x i+1 ) -µ E (x i ) + µ 2 = 0. (32)
Hence:

Avar(x) = Var(x). (33)

A.2 Multiplication by a scalar

Given a real number λ and a stationary random process x, then λx is also a stationary random process. Its Allan variance is then:

Avar(λx) = 1 2 E (λx i+1 -λx i ) 2 = λ 2 1 2 E (x i+1 -x i ) 2 = λ 2 Avar(x). (34)

A.3 Sum of independent random processes

If x and y are two independent stationary random processes, one has:

Avar(x + y) = 1 2 E (x i+1 + y i+1 -x i -y i ) 2 = 1 2 E (x i+1 -x i + y i+1 -y i ) 2 = 1 2 E (x i+1 -x i ) 2 + (x i+1 -x i ) (y i+1 -y i ) + (y i+1 -y i ) 2 = 1 2 E (x i+1 -x i ) 2 + 1 2 E [(x i+1 -x i ) (y i+1 -y i )] + 1 2 E (y i+1 -y i ) 2 = Avar(x) + 1 2 E [(x i+1 -x i ) (y i+1 -y i )] + Avar(y). ( 35
)
Because the processes x and y are independent, one has:

E (x i y j ) = E (x i ) E (y j ) , (36)
for any i, j ∈ N. Since they are stationary:

E (x j ) = E (x i ) = E (x) and E (y j ) = E (y i ) = E (y) ,
for any i, j ∈ N. Hence:

E [(x i+1 -x i ) (y i+1 -y i )] = E [x i+1 y i+1 -x i+1 y i -x i y i+1 + x i y i ] = E [x i+1 y i+1 ] -E [x i+1 y i ] -E [x i y i+1 ] + E [x i y i ] = E [x i+1 ] E [y i+1 ] -E [x i+1 ] E [y i ] -E [x i ] E [y i+1 ] + E [x i ] E [y i ] = E [x] E [y] -E [x] E [y] -E [x] E [y] + E [x] E [y] = 0. ( 37
)
It then follows that:

Avar(x + y) = Avar(x) + Avar(y).

B Autocorrelations

B.1 Background

Sample autocorrelation Given a sequence of observations z 1 , . . . , z N originating from a random process {Z i } N i=1 , the sample autocorrelation is the function of the time lag τ defined by

ρu (τ ) = 1 N -τ N -τ i=1 (z i+τ -μ)(z i -μ) σ2 ( 39
)
where μ and σ2 are sample mean and variance estimates

μ = 1 N N i=1 z i σ2 = 1 N -1 N i=1 (z i -μ) 2
At longer lags τ ≈ N there are fewer samples to estimate, so that ρu becomes unstable; for this reason one often applies the following modification ρb

(τ ) = 1 N N -τ i=1 (z i+τ -μ)(z i -μ) σ2 (40)
which increases the bias but has lower variance (and smaller MSE error as suggested in some empirical studies); however, in our case N is big enough to obtain accurate results of ρu (τ ) for a wide range of values 0 τ N .

Process autocorrelation

If the sample z 1 , . . . , z N comes from a WSS ergodic process {Z i } i then ρ and ρb estimate the process autocorrelation function

ρ Z (τ ) = E(Z t+τ -EZ t+τ )(Z i -EZ t ) Var(Z t+τ ) Var(Z t )
which under the WSS assumption depends only on τ (as the mean E(Z i ) = µ and variance σ 2 = Var(Z i ) do not depend on i).

Sample vs. process autocorrelation

If the sample z 1 , . . . , z N comes from a WSS ergodic process {Z i } i then ρ and ρb estimate the process autocorrelation. This estimate converges provided the autocorrelations decay fast enough (in theoretical literature this is captured by the notion of covariance ergodicity [START_REF] Papoulis | Probability, random variables and stochastic processes[END_REF]). Confidence for these estimates, when necessary, can be obtained using Bartlet's formula [START_REF] Bartlett | On the theoretical specification and sampling properties of autocorrelated time-series[END_REF].

B.2 Examples

Raw counter values We first estimate autocorrelations of counter values. As expected they are very high, particularly for setups with a quartz reference clock. We use both estimators (40) and (39). We compute the sample autocorrelation function by fast Fourier transform.

C Proof of Lemma 1

Since the process is Gaussian and the variance and mean of Z i do not change over time, higher moments do not change over time either. We therefore have where the constant does not depend on time i. Now let us consider mixed moments

E Z 2 i -E(Z 2 i ) 2 = O(1) (41)
E Z 2 i -E(Z 2 i ) Z 2 j -E(Z 2 j ) = E(Z 2 i Z 2 j ) -E(Z 2 i )E(Z 2 j )
which, for the joint Gaussian distribution (Z i , Z j ) can be simplified5 as

E(Z 2 i Z 2 j ) -E(Z 2 i )E(Z 2 j ) = 2 • Cov(Z i , Z j ) 2 = 2 (ρ(Z i , Z j )Var(Z i )Var(Z j )) 2
where ρ(Z i , Z j ) is the correlation. Again Var(Z i ) does not change over time; moreover ρ(Z i , Z j ) depends only on the lag j -i and equals zero when |i -j| > p according to our assumptions. Thus

E Z 2 i -E(Z 2 i ) Z 2 j -E(Z 2 j ) = O(1) |i -j| p 0 |i -j| > p (42)
where the constant does not depend on i, j. By combining Equations ( 41) and (42) we obtain We used two standardized batteries of statistical tests alongside the method proposed in this article to evaluate the output of the TRNGs:

Var 1 M M i=1 Z 2 i = 1 M 2   E Z 2 i -E(Z 2 i ) 2 + i =j E Z 2 i -E(Z 2 i ) Z 2 j -E(Z 2 j )   = O(p/M ). ( 43
• Markov chain min-entropy estimate. This method is explained in detail in Section 2.

• German AIS 20/31 test suite from Procedure B, which is intended to test the output of the TRNG core. Entropy is estimated by the test T8 is the Shannon entropy per random bit.

• American NIST 800-90B test suites for independent and identically distributed data (IID) and non-IID data. If data is detected to be IID, the min-entropy estimate of the IID test track is given. Otherwise, the non-IID entropy estimate is used.

Figure 1 :

 1 Figure 1: Generation of the jittery clock signal s in free running oscillators: ring oscillators (a) and self-timed rings (b)

Figure 2 :

 2 Figure 2: Generation of random numbers from the jittery clock signals s 1 and s 2 using a sampler (a) and a counter (b). Signals s 1 and s 2 are generated in two free running oscillators (FRO) of the same type and topology.

Figure 3 :

 3 Figure 3: Time window of the statistical variance

Figure 4 :

 4 Figure 4: Time window of the Allan variance

Figure 5 : 1 s 2 .

 512 Figure 5: Timings in counting the periods of signal s 1

Figure 6 :

 6 Figure 6: Dependence of the statistical variance and Allan variance on the number of measurements M

Figure 7 :

 7 Figure 7: Variance and Allan variance of counter values depending on the measurement interval k, with two ROs as sources of the jittery clock signals

Figure 8 :

 8 Figure 8: Variance and Allan variance of counter values depending on the measurement interval k, with two STRs as sources of the jittery clock signals

Figure 9 :

 9 Figure 9: Autocorrelations of raw counter values and their first differences in the four hardware configurations. At lag 0, the correlation is by definition always equal to 1.

Figure 10 :

 10 Figure 10: Allan variance measurement circuitry based on Eq. (13)

Figure 11 :

 11 Figure 11: Implementation of the counter variance measurement circuitry for the method proposed by Haddad et al. in[START_REF] Haddad | On the Assumption of Mutual Independence of Jitter Realizations in P-TRNG Stochastic Models[END_REF] and for that corresponding to Eq.[START_REF] Baudet | On the security of oscillatorbased random number generators[END_REF]

2 Figure 12 : 2 Figure 13 :

 212213 Figure 12: External jitter measurement method using an oscilloscope and differential probes

Figure 14 : 2 Figure 15

 14215 Figure 14: Counter values acquired using an external oscillator for s 2Figure15shows the counter values when s 2 was generated by an internal RO. Even though the low frequency pattern is still slightly visible, its amplitude is significantly reduced.

Figure 15 :

 15 Figure 15: Counter values acquired when both oscillators are implemented in the FPGA

Figure 16 :

 16 Figure 16: Autocorrelations of counter values, small lags (bias-corrected estimate ρu )

Figure 17 :Figure 18 :

 1718 Figure 17: Autocorrelations of counter values, including large lags (variance-stable estimate ρb )

)D•••••

  Results of entropy estimation using a Markov chain model and statistical tests required by standardsEntropy was evaluated in six different configurations of the TRNG including two methods of randomness extraction and two types of oscillators, as explained in Sect. 1: Both clock signals generated by ROs, randomness extraction by sampling the clock. Both clock signals generated by STRs, randomness extraction by sampling the clock. Both clock signals generated by ROs, randomness extraction by counting the clock edges (the least significant bit of the counter represented the random bit). Both clock signals generated by ROs, randomness extraction by counting the edges. Both clock signals generated by STRs, randomness extraction by counting the edges. • Both clock signals generated by STRs, randomness extraction by counting the edges.

  Given two real numbers b and p such that b > 0, the function t -→ t p is integrable in the improper sense on (0, b] if, and only if, p > -1 [21, Chapter 10].

Table 1 :

 1 Comparison of raw counter values and their first differences.

	counter data	memory autocorrelations
	raw values	long	strong
	first differences	short	weak

Table 2 :

 2 Summary of implementation of the Markov chain model for entropy estimation.

	Order (window) States Trans. matrix Memory used Dyn. program. loops
	8	{0, 1} 8	2 8 × 2 8	128MB	2 8

Table 3 :

 3 Summary of implementation results of the variance measurement method based on counter differences compared to other state-of-the-art methods implemented in the dedicated evaluation board featuring Intel Cyclone V FPGA device 5CEBA4F17C8N

	Method	Area		fmax	Power
		ALM/Regs	DSPs	[MHz]	[mW]
	Haddad et al. [8], Eq. (2)	119/160	2	178.3	6-7
	Fischer and Lubicz [9]	169/200	4	187.7	7-8
	Proposed method, Eq. (13)	49/117	1	238.5	4-5

Table 5 :

 5 Entropy estimation using high order Markov chains, AIS 31 and NIST 800-90B tests, when two internal ROs and the sampling method was used. Dependencies are modeled using 8 th order Markov chains.

	τ	Markov	AIS 31	AIS 31 T8	NIST	NIST
		chain	Procedure B		800-90B	800-90B
	periods of s2	min-entropy		Shannon entropy	IID	min-entropy
		per bit		per bit		per bit
	10 000	0.8102	failed	0.9844	non-IID	0.648
	20 000	0.8105	failed	0.9851	non-IID	0.647
	30 000	0.8102	failed	0.9847	non-IID	0.648
	50 000	0.9369	failed	0.9992	non-IID	0.673
	100 000	0.9012	failed	0.9935	non-IID	0.670

Table 6 :

 6 Entropy estimation using high order Markov chains, AIS 31 and NIST 800-90B tests, when two internal STRs and the sampling method was used. Dependencies are modeled using 8 th order Markov chains.

	τ	Markov chain	AIS 31	AIS 31 T8	NIST	NIST
			Procedure B		800-90B	800-90B
	periods of s2	min-entropy		Shannon entropy	IID	min-entropy
		per bit		per bit		per bit
	10 000	0.5440	failed	0.9072	non-IID	0.489
	20 000	0.5435	failed	0.9074	non-IID	0.489
	30 000	0.5425	failed	0.9021	non-IID	0.489
	50 000	0.5432	failed	0.9030	non-IID	0.489
	100 000	0.5423	failed	0.9076	non-IID	0.489

Table 7 :

 7 Entropy estimation using high order Markov chains, AIS 31 and NIST 800-90B tests, when two internal ROs and the least significant bits of counter values were used. Dependencies are modeled using 8 th order Markov chains.

	τ	Markov chain	AIS 31	AIS 31 T8	NIST	NIST
			Procedure B		800-90B	800-90B
	periods of s2	min-entropy		Shannon entropy	IID	min-entropy
		per bit		per bit		per bit
	2 000	0.2939	failed	0.0910	non-IID	0.621
	10 000	0.8089	failed	0.9966	non-IID	0.844
	15 000	0.9769	passed	0.9998	non-IID	0.931
	15 000	0.9769	passed	0.9998	non-IID	0.931
	20 000	0.9865	passed	0.9999	IID	0.999
	25 000	0.9907	passed	0.9999	IID	0.998
	100 000	0.9910	passed	0.9999	IID	0.998

Table 8 :

 8 Entropy estimation using high order Markov chains, AIS 31 and NIST 800-90B tests, when two internal ROs and the least significant bits of the first differences of counter values were used. Dependencies are modeled using 8 th order Markov chains.

	τ	Markov chain	AIS 31	AIS 31 T8	NIST	NIST
			Procedure B		800-90B	800-90B
	periods of s2	min-entropy		Shannon entropy	IID	min-entropy
		per bit		per bit		per bit
	2 000	0.2816	failed	0.0981	non-IID	0.336
	10 000	0.8087	failed	0.9865	non-IID	0.661
	15 000	0.9783	passed	0.9998	non-IID	0.876
	20 000	0.9893	passed	0.9999	IID	0.999
	25 000	0.9908	passed	0.9999	IID	0.999
	100 000	0.9909	passed	0.9999	IID	0.998

Table 9 :

 9 Entropy estimation using high order Markov chains, AIS 31 and NIST 800-90B tests, when two internal STRs and the least significant bits of counter values were used. Dependencies are modeled using 8 th order Markov chains.

	τ	Markov chain	AIS 31	AIS 31 T8	NIST	NIST
			Procedure B		800-90B	800-90B
	periods of s2	min-entropy		Shannon entropy	IID	min-entropy
		per bit		per bit		per bit
	2 000	0.3331	failed	0.0999	non-IID	0.565
	10 000	0.8535	failed	0.9966	non-IID	0.849
	15 000	0.9871	passed	0.9999	IID	0.998
	20 000	0.9788	passed	0.9999	IID	0.999
	25 000	0.9915	passed	0.9996	IID	0.999
	100 000	0.9807	passed	0.9999	IID	0.998

Table 10 :

 10 Entropy estimation using high order Markov chains, AIS 31 and NIST 800-90B tests, when two internal STRs and the least significant bits of the first differences of counter values were used. Dependencies are modeled using 8 th order Markov chains.

	τ	Markov chain	AIS 31	AIS 31 T8	NIST	NIST
			Procedure B		800-90B	800-90B
	periods of s2	min-entropy		Shannon entropy	IID	min-entropy
		per bit		per bit		per bit
	2 000	0.3264	failed	0.0997	non-IID	0.346
	10 000	0.8463	failed	0.9979	non-IID	0.672
	15 000	0.9883	passed	0.9999	non-IID	0.897
	20 000	0.9924	passed	0.9999	IID	0.999
	25 000	0.9915	passed	0.9998	IID	0.999
	100 000	0.9835	passed	0.9999	IID	0.998

This is formally defined as ergodicity in mean.

We discuss basic facts about process correlations in Appendix B.

Equivalently, phase noise is modeled by a process with second stationary differences.

We use the well-known formulas for central 4th-order moments of multivariate Gaussians.

Acknowledgments

This work received funding from the European Union's Horizon 2020 research and innovation programme in the framework of the project HECTOR (Hardware Enabled Crypto and Randomness) under grant agreement No 644052. Maciej Skorski also acknowledges funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 682815/TOCNeT).