Claudio A Ardagna

Ernesto Damiani

Fulvio Frati
email: fulvio.frati@unimi.itmregoli@crema.unimi.it

Sergio Oltolina
email: sergio.oltolina@eng.it

Mauro Regoli

Gabriele Ruffatti
email: gabriele.ruffatti@eng.it

Spago4Q and the QEST nD Model: an Open Source Solution for Software Performance Measurement

Keywords: QEST nD, Spago4Q, Performance Indicator, process monitoring

Improving the software development process requires tools and model of increasing complexity, capable of satisfying project managers' and analyzers' needs. In that paper we present a solution integrating a formalized and established model for performance evaluation like QEST nD, and an open source Business Intelligence platform like Spago4Q. We obtain a new environment that can produce immediate snapshots of projects' status without any constraint on the number of projects and the type of development process.

Introduction

The availability of detailed and updated information on the software development process is of paramount importance for organizations to maintain their competitiveness level and operate in new and more challenging markets. Such a scenario of integrated information is known as Business Intelligence and encloses all the business processes and tools used by organizations for data acquisition.

Within this context, a number of structured process models are adopted by enterprises, depending on their application domain and size, to collect specific knowledge about their development processes, strengthening, at the same time, their know-how in terms of more efficiency and quality.

In this paper, we describe our experience in the deployment of an integrated and complete environment for software performance evaluation. To this aim, we exploit a formal model for process performance evaluation (QEST nD) and we connect it with an open source Business Intelligence application (Spago4Q). In particular, the QEST nD model (Quality factor + Economic, Social, and Technological Dimension) is a multi-dimensional model, proposed in [START_REF] Buglione | QEST nD: n-Dimensional Extension and Generalisation[END_REF] and [START_REF] Buglione | A quality factor for software[END_REF], for the performance evaluation of software processes. Its multi-dimensional nature is based on three important concepts:

1. A number of measurable concepts derived from different business areas (called dimensions) including economic, social, and technological ones. 2. The number of business areas interested by the analysis. This number may change for each single project, without any limit (from here comes the acronym nDn Dimensions). 3. Organizations are allowed to choose the dimensions of each analysis with respect to their needs.

Such a philosophy makes QEST nD an open model, decoupled from any specific development process, allowing multi-process, multi-project performance analysis.

The final objective of the model is to express the overall process performance (P) as a combination of the performance of any considered dimension, calculated as the weighted sum of the applied metrics. The global performance value approach gives an immediate and accurate snapshot of the current state of the project, and allows a topdown analysis starting from the global value, which includes all the single measurements, to the analysis of the performance of the single dimension. The performance indicator is calculated by the integration of instrumental measurements (called RP -Rough Productivity) and the subjective perception of the overall quality (express as QF -Quality Factor).

A problem characterizing the QEST nD model and preventing its diffusion in the Business Intelligence context was the lack of reliable and flexible environments where the model could be implemented and distributed. As described in the following sections, we deliver QEST nD on an open source business intelligence platform, Spago4Q (SpagoBI for Quality) [2] [START_REF] Damiani | The use of a metamodel to support multi-project process measurement[END_REF]. Spago4Q is a platform for maturity assessment, effectiveness of development software processes and application services, and quality inspection of the released software, achieved by the evaluation of data and measures collected from the process management and development tools with noninvasive techniques.

The tool is easily adaptable to different organizational contexts, independently from the development process adopted by the single projects (i.e. waterfall, XP, Scrum, etc.), meeting exactly the multi-process multi-project approach of QEST nD. Although the initial vision of Spago4Q was focused on the software development process, the implementation of the QEST nD model, and consequently of a global multi-dimensional performance value, could extend the performance and quality evaluation to services and business areas that are typical of software organizations.

The paper is organized as follows. Section 2 describes more in detail the two frameworks (QEST nD and Spago4Q). Section 3 shows the steps to build the implemented integration. Section 4 presents two real case studies. Finally, Section 5 contains our conclusions.

2

The Context: QEST nD and Spago4Q

In the following sections, we give an overview of the two frameworks describing the mathematical formalization of QEST nD, and the main characteristics of Spago4Q.

2.1

The QEST nD Model

In the software engineering context, several one-dimensional performance models are available which integrate individual measurements into a single performance index. By comparison, in more traditional domains such as Business Modeling, there exist a number of multi-dimensional models that take into account data derived directly from their accounting systems, which means that multiple viewpoints are, in fact, considered [START_REF] Buglione | QEST nD: n-Dimensional Extension and Generalisation[END_REF].

Furthermore, models currently available in the software engineering domains are too oversimplified to properly reflect the different aspects of performance when various perspectives, or viewpoints, must be taken into account at the same time. Therefore, to manage simultaneous multi-dimensional constraints in development projects, managers need to estimate the status of current projects based on their own interpretation of rough data, due to the lack of reliable measurement models.

In multi-dimensional analysis, complex viewpoints are taken into account simultaneously, each one analyzing a distinct aspect of the overall process performance. Therefore, an extension to the traditional single-dimension approach is needed, to consider both quality and performance of the development process.

The QEST nD model [START_REF] Buglione | A quality factor for software[END_REF] is aimed at measuring software project performances addressing the aspects of multidimensionality and qualitative-quantitative assessment. With respect to the original QEST model that was initially designed for measurements to be done at the end of a project, QEST nD provides a dynamic extension to analyze software process data throughout all the development phases. In particular, in the QEST model the quality can be viewed as the integration of at least three different viewpoints.

• Economical (E): expresses the viewpoint of management, interested in measurements focused on the overall quality level, rather than the quality of specific features or process areas. • Social (S): measures the perspective of the user, where the quality is intended as the characteristic of a product to satisfy present and future needs. • Technical (T): relative to developers, for whom software quality is achieved by conforming to specific, explicitly stated standards and requirements explicitly stated.

In the QEST model the measurement of performance (P) is given by combining a quantitative measurement, indicated by the component RP-Rough Productivity, and a qualitative measurement, calculated as a perception-based measurement of the overall product quality (QF-Quality Factor). A detailed explanation of the model, that has been formalized in [3] [4], is out of the scope of this paper. For the initial QEST model, the three-dimension geometrical representation of a regular tetrahedron (see Fig. 1) was selected and studied to help the model formalization. In particular:

• the three dimensions (E, S, T) in the space d to the corners of the pyramid's base, and the convergence of the edges to the P vertex describes the top performance level; • the three sides are of equal length: the solid shape that represents this 3D concept is therefore a pyramid with a triangular base and sides of equal length (tetrahedron).

The figure represents the ranges to which the dimensions performances will belong to.

The geometrical approach permits the representation of the measurement of performance in a simple and visual way, assisting the global performance computation. Thanks to this representation, it is possible to express the performance value in term of geometrical concepts like distance, surface, and volume. The value of each dimension is seen as the weighted sum of a list of n distinct measures, each one representing single measurable concepts for each perspective. Then, the values of the three dimensions E, S, T are placed on the respective tetrahedron side, describing a sloped plane section and representing the three dimensional performance measurements [START_REF] Buglione | A quality factor for software[END_REF]. Fig. 2 better explains such a geometrical aspect, indicating the three dimensions' values as Q e , Q s , and Q t . Finally, the QF, with respect to each dimension, is added to the previous values describing an upward or downward translation of the plan (Q e , Q s , Q t ) finding the new plan (Q' e , Q' s , Q' t ).

On the other side, the value RP can simply be expressed as the distance between each single corner (E, S, T) with the specific point Q e , Q s , and Q t . Please note that the maximum value of each edge is 1, consequently all the values that are placed on the tetrahedron have to be normalized. Then, the performance value is calculated as the distance between the center of gravity of the original tetrahedron and the center of the described plane section along the tetrahedron height (see Fig. 2).

The explanation above is valid for the QEST nD case, where more than 3 dimensions are taken into account. Through computational geometry, it is possible to develop a generic representation of it with a generalization of a tetrahedral region of space to n dimensions describing it with a simplex [START_REF] Buglione | Geometrical and statistical foundation of a three-dimensional model of performance[END_REF]. To conclude, the geometrical formalization of the model allows to describe it with a simple formula for the computation of the global performance value P: 1Where p i represents the single dimension performance value added with the respective QF value. Section 3 and 4 deal with the definition of the environment and, in particular, of the metrics model that will be used to compute the value of the single dimensions.

∏ = - - = n i i p P 1 ) 1 (

Spago4Q

Spago4Q (SpagoBI for Quality) [2] is an open source platform for the continuous monitoring of software quality. Its most important characteristic is the total independence from the adopted development process and from the number of monitored projects. Spago4Q can then be described as a multi-process multi-project monitoring platform.

In Spago4Q, the evaluation of metrics and the collection of data are executed in a fully-transparent way, without any action due by programmers and designers and any change in their typical working tasks.

Spago4Q includes in its package a number of extractors for the main environments that are exploited during the software lifecycle (IDE, text editing tools, requirements management frameworks, and the like) that collect data directly from process work-products (e.g. java classes or logs).

Since Spago4Q relies exclusively on open frameworks and it is released under an open source license, its structure could be enriched with the implementation of additional extractors for particular work-product types. In any case, the extractors will [START_REF] Buglione | QEST nD: n-Dimensional Extension and Generalisation[END_REF] be executed at specified time intervals and store data directly in the application data warehouse.

Spago4Q is a vertical adaptation of SpagoBI [10], a more complex framework for Business Intelligence analysis, whose structure was enriched with the use of a complex meta-model (see Fig. 3) for the representation and description of the generic development process, the measurement framework, the extractors, and the assessment framework [START_REF] Damiani | The use of a metamodel to support multi-project process measurement[END_REF], that defines the entities that play a role in the monitoring process the relations between them. The Development Process meta-model has been designed to be as generic as possible, allowing the modeling of virtually all process models, from waterfall to XP. It is connected with the Measurement Framework meta-model, which defines a skeletal generic framework and is used to obtain measures from most development processes. Then, the Assessment meta-model allows to model a generic evaluation structure with a simple classification in terms of Category, Target, and Practice. Finally, the Extractors meta-model is used to formalize and define the extractors used to retrieve data from process module and supply it to the measurement module.

In particular, the inclusion of a specific meta-model for the assessment framework allows the tool to implement metrics that are specific to a particular assessment model. Originally Spago4Q was studied to fully support the CMMi framework [START_REF]CMMi -Capability Maturity Model integration[END_REF] for Fig. 3. The Spago4Q meta-model [START_REF] Damiani | The use of a metamodel to support multi-project process measurement[END_REF].

the maturity assessment of the development process. However, the intrinsic generality of the meta-model approach allows adapting it to any assessment model, for instance ISO 9000 or Balanced Scorecards. In fact, Spago4Q provides support for the definition and implementation of measurement frameworks based on the GQM (Goal-Question-Metric) approach [START_REF] Basili | The Goal Question Metric approach[END_REF], which categorizes the metrics in terms of (i) generic goals to be measured, (ii) the particular aspects that the metric has to measure, and (iii) the metrics that implement the actual measurement.

An integrated Environment

The below-described work has been the subject of a Master thesis carried out within the Department of Information Technology, Università degli Studi di Milano. The definition of a QEST nD model is a five-step procedure that will be described in following paragraphs, without entering in the implementation details for the sake of conciseness.

The steps, all executable through the graphical interface of Spago4Q, are coherent with the PMAI (Plan-Measure-Assess-Improve) cycle [START_REF] Deming | Out of the Crisis[END_REF], which is composed of four logical phases:

1. PLAN, which consists in defining a set of metrics basing on the GQM approach, defining the dimensions that characterize the analysis, the mathematic formalization of the metrics and the weight to assign to each metric. 2. MEASURE, which includes the collection of data, the computation of metrics values, the normalization of them (values must be ≤ 1), and the computation of global Performance value using the Eq. 1. 3. ASSESS: results are presented in dashboards and reports, and analyzed by the management and analyzers. 4. IMPROVE: every negative or low value is deeply analyzed to find problems in the processes and consequently find solutions to improve the overall quality.

Step 1: Metrics and Model Definition

The first step deals with the declaration of a complete GQM, with the definition of the analysis dimensions, the concepts to measure, and the metrics to apply to project work-products.

The GQM will be defined using the Model Definition interface, while metrics (or KPI -Key Performance Indicator) are defined through the KPI Definition section.

In particular, the definition of KPIs involves the specification of an algorithm for the computation of the metric. This algorithm will exploit the SQL mathematical library for simple computations, or call an ad-hoc Java class for more complex ones. The KPI will collect data directly from the Spago4Q data warehouse, which contains all the data that the extractors get from the project work-products.

3.2

Step 2: Weights and Threshold Definition

The QEST nD model requires each metric to be coupled with the respective weight, which indicates the importance that such a concept plays in the dimension it belongs to. A complete analysis of the GQM should be performed prior to define the weights for each KPI. Thus, for each metric it is important to define the specific thresholds, which allow to evaluate the value with respect to the organization policies. The thresholds have to take into account the normalization of metrics and are also important for the creation of complete and understandable reports. The KPI Definition interface helps to define such aspects.

Finally, although the use of the QF is optional and its absence does not preclude the entire Global Performance value, in this step it is possible to assign the QF to each specific dimension. The definition of the QF is subjected to the analysis of pool of experts that define the value that will be added to the respective RP. A complete guide for the definition of the QF of a software product can be found in [START_REF] Buglione | A quality factor for software[END_REF].

Step 3: Measures Collection

Measures are taken directly from Spago4Q data warehouse, which in turn is filled by data collected by extractors accessing process work-products. The collection process is defined in the configuration phase, where a specific dataset, that contains the description of the metric itself, is defined for each KPI or group of KPIs.

Metrics are described in terms of (i) the name of the model to which the metric is assigned to, (ii) default value, (iii) minimum and maximum values (for normalization), and (iv) the algorithm for the metric computation.

In particular, the algorithm can be implemented using the common mathematic library of SQL, as a separate Web Services or, for computations that involve complex operations, as a Java package. Furthermore, the application supplies to users KPIspecific drivers to be used in the metric formula to help the definition of it in the selected programming language, supplying methods for the direct access to data warehouse fields. Finally, specific fields for the KPI results will be added to the data warehouse and supplied to other KPIs and components of Spago4Q.

3.4

Step 4: Global Performance Computation

In our approach, both global and dimension-wise performance indexes are computed as simple KPIs that take in input configuration data and results of the metrics at the bottom of the GQM tree. First of all, the performance value of each dimension is calculated as the sums of the product of each metric, belonging to the dimension, with its specific weight:

∑ = = n i i i w V D 1 ) * ( ( 2
)
where D is the dimension performance value, V is the result of the i-th metric, and w is the assigned weight. If the QF is provided by the model, its value is added to the results:

QF w V QF D D n i i i + = + = ∑ =1
) * ( ' Note that Eq. 2 and 3 are computed for each of the n dimensions that compose the QEST nD model that has been specified. Finally, the KPI that computes the global performance indicator could be defined using the Eq. 1, defined in Section 3.1 and it is valid in the case the QF is defined or not.

∏ = - - = n j j D P 1 ) 1 ( 1
The global performance P value will be assigned to the root node of the created model.

3.5

Step 5: Reports

As last step of the process, a set of reports and dashboards could be defined and configured to satisfy any reporting and managerial need. One of the open source reporting tools we integrated with Spago4Q is Eclipse BIRT [START_REF][END_REF]. The generation of reports requires the creation of a specific dataset that includes all the data that will be described by the report.

Such data is collected from the application data warehouse and, in particular, from the fields that contain the metrics values. Several pre-defined templates and layouts are available.

Spago4Q provides methods and interfaces to directly configure and create a new report using all the facilities provided by BIRT.

Case Studies

The application of the QEST nD model in Spago4Q has been tested using two real case studies on data taken from real development projects realized by Engineering Ingegneria Informatica, a major player within the community of Spago4Q.

The two projects are of increasing complexity: the first one deals with a little project consisting of a single measurement of project data, while the second one measures the complex performance of three big projects with several measurements in a three-month time slot.

For the sake of conciseness, in this section we focus on the second case study only, providing information about the steps that were described in Section 3. The realized QEST nD model was called Business-Service Model and takes into consideration four specific analysis dimensions:

(3) (4) 1. QEST-EC: Economic performance indicator; Fig. 4 shows the complete model, highlighting the GQM structure of the metrics. The root node is the global performance indicator (QEST-BS), which includes the four goals describing the analysis dimensions. For each dimension, a set of questions (i.e., the concepts to measure) has been defined, which in turn includes the metric, or the metrics, which evaluates the concept. Table 1 summarizes the metrics, along with the respective weights, that compose the model.

Each metric is associated to specific SQL queries or Java classes that directly access to the data warehouse to collect the input for the computation. For each metric, a field in the data warehouse has been created to store its output, to be used by other KPIs or reports. It is important to remark that the definition of weights and thresholds has to be very careful and must involve skilled experts that have a solid background in the enterprise scenario. In fact, an overestimation, or underestimation, of metrics weights will result in a global value that does not reflect the process state, as well as, the definition of incorrect thresholds will imply an incorrect analysis of the organization status. In these case studies, for the sake of conciseness, the QF has not been taken into consideration; hence the performance computation takes into account only the weighted sums of the metric results. The experimentation covered three months of development. Raw data have been collected by the application from process work products and stored in the data warehouse. In particular, Table 2 shows a snapshot of values collected at the end of the three months for each project.

Finally, metric values were normalized and used as inputs to Eq. 2 and Eq. 4, for the computation of single dimension and global performance indicators. The values of indicators can be represented using the internal Spago4Q dashboards (Fig. 5) or the user can create ad-hoc reports using BIRT functionalities. In particular, dashboard gives an immediate snapshot of the situation, highlighting problems and suggesting to project managers the areas where the effort should be concentrated or where a quality improvement of the process is needed. By contrast, reports can give a more detailed analysis of the data, describing in details the results of indicators and better targeting the improvement actions. Looking at the results of our case study, the graphs in Fig. 6 and7 show that all projects were concluded with an excellent global performance (close to one), showing some issues in the process that is worth analyzing.

For instance, the Economic dimension of Project 1 is characterized by a red square, indicating that the value is within the bad area, hence a deep analysis of that area is needed for next implementations. In fact, project managers discovered that the financial resources assigned to the project were overestimated for the needed effort, suggesting an adjustment to the enterprise criteria for projects financing.

Conclusions

The integration of the QEST nD model and Spago4Q allows implementing a complete multi-project multi-process performance evaluation environment that combines the mathematical formalization the QEST nD model and the facilities offered by Spago4Q. In this paper, we analyzed such an integration, and described a complete case study that shows the high configurability and reliability of the framework.

The contribution is twofold. First, we implemented and used a formal model for process performance evaluation (QEST nD) and we connected it with an open source Business Intelligence application (Spago4Q). Second, we developed a solution that derives global performance indicators of the enterprise developing work by analyzing its process raw data (e.g., java classes, logs).

The main benefit of the proposed solution lays in the fact that it gives the possibility to analyze the performance of the development process from different points of view and integrate semantically different metrics and KPIs in a single indicator. The QEST nD model described in this paper will be made available in the future version of Spago4Q.

Fig. 1 .

 1 Fig. 1. Geometrical representation of QEST model using E, S, T dimensions and P value as edges of the figure [1].

Fig. 2 .

 2 Fig. 2.(Q e , Q s , Q t ) and (Q' e , Q' s , Q' t ) plane sections[START_REF] Buglione | QEST nD: n-Dimensional Extension and Generalisation[END_REF].

Fig. 4 .

 4 Fig. 4. The complete GQM model defined in the case studies.

Fig. 5 .

 5 Fig. 5. Spago4Q dashboards for projects state at month 3.

Fig. 6 .

 6 Fig. 6. Spago4Q graph for projects global performance comparison.

Fig. 7 .

 7 Fig. 7. Spago4Q graph for projects single dimensions performance comparison.

Table 1 .

 1 List of KPIs defined for the case study.

	KPI	Description	Weight
	QEST-KPI-BS	Global Performance Indicator
	QEST-EC	Economic Performance Indicator	1.0
	QEST-RS	Resources Performance Indicator	1.0
	QEST-TE	Technical Performance Indicator	1.0
	QEST-CS	Customers Satisfaction Performance Indicator	1.0
	QEST-EC-1	Product/Service Usage Factor	0.2
	QEST-EC-2	Support Services -Business Services Costs Ratio	0.4
	QEST-EC-3	CR Development Services -Business Services Costs Ratio	0.4
	QEST-RS-1	Services Availability Factor	0.7
	QEST-RS-2	Resources Turnover Factor	0.15
	QEST-RS-3	Unresolved Issues Factor	0.15
	QEST-TE-1	Average Cyclomatic Complexity	0.1
	QEST-TE-2	Documentation Quality Issues Factor	0.05
	QEST-TE-3	Coding Rules Unconformity Factor	0.05
	QEST-TE-4	Object-oriented Rules Unconformity Factor	0.1
	QEST-TE-5	Running Applications Issues Factor	0.15
	QEST-TE-6	Average Recovering Time	0.1
	QEST-TE-7	Milestones Shifting Factor	0.1
	QEST-TE-8	Productivity Factor	0.1
	QEST-TE-9	Application Variability Factor	0.05
	QEST-TE-10	Requirement -Test Coverage Ratio	0.08
	QEST-TE-11	Deploy Issues	0.07
	QEST-TE-12	Patches Installation Frequency	0.05
	QEST-CS-1	Training Factor	0.1
	QEST-CS-2	Customers Satisfaction Factor	0.6
	QEST-CS-3	Usability Factor	0.3

Table 2 .

 2 Metrics values collected for the three projects at the end of each month. Note that data are cumulative and have to be normalized before performance computation.

	KPI		Project 1			Project 2			Project 3
		M1	M2	M3	M1	M2	M3	M1	M2	M3
	QEST-EC-1	80	78	82	50	68	72	25	49	70
	QEST-EC-2	25	45	30	5	7	6	8	9	7
	QEST-EC-3	50	65	55	2	4	5	14	11	10
	QEST-RS-1	99	97	98	60	70	87	97	95	96
	QEST-RS-2	91	94	95	96	93	94	98	97	97
	QEST-RS-3	50	62	82	35	37	68	10	35	88
	QEST-TE-1	20	18	15	30	32	25	50	39	35
	QEST-TE-2	1.1	1.9	1.8	1.8	2.3	2.1	4.5	3.2	1.9
	QEST-TE-3	95	93	94	96	92	93	82	91	92
	QEST-TE-4	99	97	95	30	49	67	85	89	93
	QEST-TE-5	2	1	2	1	2	1	1	2	2
	QEST-TE-6	3,5	3.2	3.1	2,4	1.3	1.1	16	12	8
	QEST-TE-7	87	78	83	88	92	93	50	80	85
	QEST-TE-8	10	20	17	55	40	35	68	65	55
	QEST-TE-9	2	122	9	25	15	12	29	22	18
	QEST-TE-10	375	390	410	178	230	245	210	240	255
	QEST-TE-11	1	2	2	2	1	1	3	2	2
	QEST-TE-12	2	3	4	9	6	5	10	8	7
	QEST-CS-1	60	75	89	95	91	92	94	92	91
	QEST-CS-2	75	85	90	91	87	90	93	95	94
	QEST-CS-3	91	83	92	96	93	92	80	83	93

Acknowledgments

This work was partly founded by the European Commission under the project SecureSCM (contract n. FP7-213531) and by the Italian Ministry of Research under FIRB TEKNE (contract n. RBNE05FKZ2_004).


Keywords: Physical Cryptography, Physical Unclonable Functions, SIMPL Systems, Public Key Systems

This paper discusses strategies for the electrical, integrated implementation of a novel security tool termed SIMPL system, which was introduced in [1]. SIMPL systems are a public key version of Physical Unclonable Functions (PUFs). Like a PUF, each SIMPL system S is physically unique and nonreproducible, and implements an individual function FS. In opposition to a PUF, every SIMPL system S possesses a publicly known numerical description D(S), which allows its digital simulation and prediction. However, any such simulation must work at a detectably lower speed than the real-time behavior of S. As argued in [1], SIMPL systems have practicality and security advantages over PUFs, Certificates of Authenticity (COAs), Physically Obfuscated Keys (POKs), and also over standard mathematical cryptotechniques. This manuscript focuses on electrical, integrated realizations of SIMPL systems, and proposes two potential candidates: SIMPL systems derived from special SRAM-architectures (so-called "skew designs" of SRAM cells), and implementations based on analog computing arrays called Cellular Non-Linear Networks (CNNs).

Towards Electrical, Integrated Implementations of SIMPL Systems

Ulrich Rührmair * , , Qingqing Chen †, ‡ , Martin Stutzmann ⋄ , Paolo Lugli ‡ , Ulf Schlichtmann † , and György Csaba ‡

Introduction

Physical Unclonable Functions (PUFs) are a relatively young, emerging cryptographic primitive [START_REF] Pappu | Physical One-Way Functions[END_REF] [3] [4] [START_REF] Tuyls | Rob Wolters Read-Proof Hardware from Protective Coatings[END_REF] [6] [START_REF] Tuyls | Strong Authentication with PUFs[END_REF]. However, one potential downside of PUF-based protocols is that they usually require a previously shared piece of information (typically some challenge-response-pairs) that was established in a joint set-up phase between the communicants. Alternatively, an online connection to a trusted authority at the time of the protocol execution must be employed. In this particular structural aspect, PUFs are resemblant of classical private key systems.

In this paper, we are concerned with an alternative security tool called SIMPL systems, which is a public key version of standard PUFs. SIMPL systems have been introduced in [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]. The acronym SIMPL stands for "SIMulation Possible, but Laborious", and hints at the critical security feature of these structures. A physical system S is called a SIMPL system if the following holds:

1. It is possible for everyone to numerically simulate and, thus, to predict the physical behaviour of S with very high accuracy. The basis of the simulation is an individual description D(S) of S, and a generic simulation algorithm Sim, which are both publicly known. 2. Any sufficiently accurate numerical simulation -as well as any arbitrary physical emulation of S -is slower than the real-time behavior of S. Determining the system's behavior by an actual measurement on the original system S works detectably quicker than any other approach. 3. It is difficult to physically reproduce or clone S.

Put together in one sentence, the holder of a SIMPL system S can compute a publicly known, publicly computable individual function F S faster than anyone else. Applying the familiar public key terminology to this situation, one could state that the numeric description D(S) essentially serves as a public key, while the physical system S constitutes an equivalent to a private key. This "private key", however, is a physically irreproducible structure, which contains no secret information at all. This leads to several significant security advantages, which have been discussed in [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF].

One critical question is certainly how SIMPL systems can be implemented in practice. We suggest two variants based on integrated electrical circuits in this publication: Firstly, special SRAM-memories based on a newly developed "skew" design, which leads to fuzzy memory cell behavior at quickly varied operational voltages. Secondly, we propose analog circuits known as Cellular Non-Linear Networks (CNN), whose cells evolve over time in an analog, highly parallel fashion. This can help them to outperform classical architectures on certain computational tasks, as is required from SIMPL systems.

Organization of the Paper. The rest of this manuscript is organized as follows: In section 2 we cite and discuss the formal specifications of SIMPL systems of [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]. Section 3 provides one example protocol and briefly discusses applications and advantages of SIMPL systems. In section 4 we treat the implementation of SIMPL systems by Cellular Non-Linear Networks. Section 5 introduces SIMPL systems based on special SRAM architectures. We conclude the paper in section 6.

SIMPL Systems

The following specification of SIMPL systems has been provided in [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]. Specification 1 ((t C , t P h , ǫ)-SIMPL Systems). Let S be a physical system mapping challenges C i to responses R i , with C denoting the finite set of all possible challenges. Let furthermore t max be the maximum time (over all challenges C i ∈ C) which it takes until the system has generated the corresponding response R i . S is called a (t C , t P h , ǫ)-SIMPL SYSTEM if there is a numerical string D(S), called the description of S, and a generic computer algorithm Sim such that the following conditions are met:

(i) V Eve = R i0 . (ii)
The time that Eve needed to output V Eve after she was presented with C i0 is at most 2 • t max . The said probability of ǫ is taken over the uniformly random choice of C i0 ∈ C, and the random choices or actions that Eve might take in steps 2a, 2b and 2c. Some remarks on the specification are in order.

Security Model. Let us start by briefly discussing the security model of the specification. In practice, an adversary Eve can gather information about S in essentially two ways. Firstly computationally, by analyzing challenge-response-pairs (C i , R i ) and by analyzing the algorithm Sim and the description D(S). The CRPs may either stem from eavesdropping on protocols, or they may be computed by the adversary hinself via the algorithm Sim and the description D(S). These possibilities are reflected in item 2a of the specification. Secondly, Eve may physically measure arbitrary features of the system S at some point. For example, she might try to obtain some physical characteristics or internal parameters of the system which are not easily deducable from knowing many CRPs, but which could speed up her simulation. This possibility is covered in item 2b. The model tries to reflect real-world situations, for example if S was used in mobile systems for identification purposes.

Immunity against Full Read-Out. It follows from Specification 1 that for any SIMPL system S, it must be impossible to measure the values R i for all possible parameters C i ∈ C within the timeframe t P h . Otherwise, Eve could create an exhaustive lookuptable for all possible values R i during step 2b, which would enable her to succeed in the described experiment. Hence, for any SIMPL system either the set of possible measurement parameters C must be very large (for example exponential in some system parameter) and/or successive read-outs can only be carried out relatively slowly.

Immunity Against Cloning. Please note further that Specification 1 implies that previous physical access and a number of known Challenge-Response-Pairs of S must not enable Eve to do one of the following:

1. Build an exact physical clone S ′ of the system S, for which

R i = R ′ i for (almost) all C i ∈ C,
and for which the evaluation of the R ′ i works comparably quickly as by an experiment on S. The inability for digital cloning implies a number of non-trivial requirements: Firstly, it logically includes the immunity against full read-out that we discussed earlier. Secondly, it implies that the behaviour of S cannot be learned by a machine learning algorithm that has a very rapid prediction phase, which works on a comparable timescales as the real-time behavior of S. Thirdly, and most generally, it implies that the simulation of S on the basis of D(S) cannot be split into a possibly laborious precomputation phase independent of a concrete challenge, and a specific computation phase that very rapidly determines R i once C i is given.

In the sequel, we will sometimes refer to the immunity of S against cloning also as the unreproducibility or the uniqueness of S.

Feedback Loops and Security Margin. Specification 1 stipulates that the time gap between Eve and the real SIMPL system must be at least a factor of 2. This seems surprising: One might expect a polynomial vs. exponential distinction here. However, such asymptotic notions cannot be applied directly to the finite function which a SIMPL system implements without rising contradictions [START_REF] Rührmair | On the Foundations of Physical Unclonable Functions[END_REF]. Furthermore, it is not clear whether a unique, non-reproducible hardware system with a truly exponential speed up exists at all: Quantum computers or quantum hardware are clonable, and other practical physical system with an exponential speed up over classical Turing machines currently are not known [START_REF] Andrew | Classical physics and the Church-Turing Thesis[END_REF] [20] [START_REF] Shor | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[END_REF]. Nevertheless, in the application protocols which we suggest (identification and onthe-fly message authentication), a detectable time difference at the time of the protocol execution suffices. No security properties similar to the long-term confidentiality of encryption are required, that would make a polynomial vs. exponential time gap necessary.

Furthermore, the absolute (but not the relative!) time difference between the original system and Eve can be amplified via feedback loops. There, the SIMPL systems successively determines a sequence of challenge-responses-pairs

(C i1 , R i1 ), (C i2 , R i2 ), . . . , (C i k , R i k )
, in which later challenges C im are determined by earlier results R i l , with m > l. In this context, (C i1 , R i k ) can be regarded as the overall challenge-response pair determined by the structure, and the set C and t max can be adjusted accordingly. Such feedback loops shift us into a region of absolute delay values (e.g. seconds) where we can maintain security even in the face of unwanted side effects, such as network and transmission delays.

Different Adversarial Scenarios. The specification leaves to some extent open which specific resources Eve may employ during her attack. There are several meaningful scenarios, leading to different security notions.

1. CONSUMER SECURITY: Eve is assumed to be a private person, possibly very educated in cryptographic and security matters, but with a budget not exceeding one million dollars. 2. TECHNOLOGICAL SECURITY: We assume that Eve is allowed to use basically unlimited financial resources, and faces no restrictions other than those induced by current technology.

When we say that a SIMPL system is secure in one of the above scenarios, we mean that it remains secure in the sense of Specification 1 if Eve is allowed the described resources. Which type of security we seek strongly depends on the intended application. A SIMPL system that is not technologically secure, but consumer secure might still find very fruitful applications in the consumer market. One should have this fact in mind, and not aim for technological security only when designing SIMPL systems.

Protocols and Applications

We will now quote one exemplary protocol that can be realized by SIMPL systems in order to illustrate their working principle [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]. A few applications and the advantages of SIMPL systems are briefly discussed, too.

Identification by SIMPL Systems

We assume that Alice, who holds an individual SIMPL system S, has put D(S), Sim, t max and a description of C in a public register. Now, she can prove her identity to an arbitrary second party Bob as follows [

V i = R i .
If this is the case, Bob believes Alice's identity, otherwise not.

Security. As usual, k is the security parameter of the protocol. In a nutshell, the protocol works because Eve is unable to determine the values R i for randomly chosen C i comparably quickly as Alice, provided that: (i) The lifetime of the system S (and the period since D(S) was made public) does not exceed t C , and (ii) Eve's accumulated physical access times to S do not exceed t P h . In that case, Eve's probability to succeed in the protocol without possessing S are less or equal to ǫ k .

Practicality. Bob can improve his computational efficiency by verifying the correctness of the responses R i merely for a randomly chosen, smaller subset of {1, . . . , k}. If necessary, possible network and transmission delays can be compensated for in advance by amplifying the absolute time gap between Eve and S through feedback loops (see discussion in section 2). Also the asymmetry between checking a solution and computing a solution may be exploited in future protocols (see section 6.3 of [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]).

Applications and Advantages of SIMPL Systems

Straightforward applications of the above identification protocol include [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]:

(i) Identification of hardware and computer systems.

(ii) Secure labeling of valuable items, such as branded products, pharmaceuticals, passports, bank notes, credit cards, and the like. (iii) Unclonable (copy protected) representations of digital content and software, digital rights management. (iv) Tamper sensitive hardware environments.

The upside of using SIMPL systems in these situations over standard mathematical cryptotechniques or alternative approaches such as Certificates of Authenticity [START_REF] Dejean | RF-DNA: Radio-Frequency Certificates of Authenticity[END_REF] or PUFs has been discussed in detail in [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]. It includes: (i) SIMPL systems do neither contain nor constitute any sort of secret binary information. This makes them naturally immune against any side channel, invasive or malware attack. (ii) They allow protocols that are independent of the standard, unproven number theoretic assumptions (factoring, discrete log). (iii) They have strong practicality advantages over COAs and PUFs, due to their public key nature. (iv) They allow new DRM techniques, or unforgeable labels that can be read out digitally over long distances, and which can be verified offline at the same time [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF].

These assets make them a worthwhile target for future investigations. In particular, it would be important to find electrical, integrated implementations -an issue which was left open in [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF].

SIMPL Systems from Cellular Non-Linear Networks

Introduction and General Idea

A first electrical and on-chip candidate for SIMPL systems are Cellular Non-Linear Networks (CNNs) [START_REF] Chua | Cellular Neural Networks and Visual Computing: Foundations and Applications[END_REF]. If successfully implemented, they would result in a technologically secure SIMPL system (see page 5).

CNNs are analog computing arrays with a regular, periodic, cellular structure. The cells are characterized by a dynamical state variable, and their time evolution depends on their own internal state and on the inputs from their neighbouring cells. On an abstract level, their behavior is given and determined by so-called templates, which in the simpliest case are real-valued matrices. On a circuit level, it is given by the transistor architecture of a cell, which implements the behavior specified by the templates.

More specifically, each cell is characterized by a dynamical state variable x, which obeys the following, ordinary differential equation (ODE):

ẋij = -x ij + k,l A i,j,k,l y kl + k,l B i,j,k,l u kl + z ij i.e
. the time derivative of the state variable (for the cell with i, j indices) depends on the y output of the neighboring cells (denoted by the k, l indices) via a the A cloning templates. Each cell has a bias (z) and inputs, which are coupled by the B template to the equation.

As a mathematical model, CNNs are very general; for example, cellular automata [START_REF] Wolfram | Statistical mechanics of cellular automata[END_REF] can be interpreted as a special CNN which operates on discrete variables in discrete time (and where rules replace the ODE-based description). CNNs are also known to be Turing-complete [START_REF] Roska | The CNN universal machine: An analogic array computer[END_REF]. CNNs often have multiple layers, and these layers are also coupled to each other via B templates.

Due to their analog and highly parallel architecture, CNNs have a remarkable computing power and efficiency. Already in 2004, a state-of-the-art programmable, commercially available CNN in a 0.35-µm standard CMOS technology exhibited peak computing figures of 330 GOPS [START_REF] Rodriguez-Vazquez | ACE16k: The Third Generation of Mixed Signal SIMD-CNN ACE Chips Toward VSoCs[END_REF] (or 3.6 GOPS/mm 2 and 82.5 GOPS/W in terms of area and power consumption). These numbers are yet excelled by non-programmable CNNs, which we propose for use as SIMPL systems. In specialized tasks, it is known that CNNs can outperform digital computers by a factor of up to 1,000 [START_REF] Chua | CNN Universal Chips crank up the computing power[END_REF] [START_REF]Cellular Wave Computers for Nano-Tera-Scale Technology -beyond spatial-temporal logic in million processor devices[END_REF]. CNNs are the largest analog circuits, with the CNN referred to above [START_REF] Rodriguez-Vazquez | ACE16k: The Third Generation of Mixed Signal SIMD-CNN ACE Chips Toward VSoCs[END_REF] containing 3.75 million transistors.

A further important property of CNNs is that their functionality is especially sensitive to the inevitable variations in the fabrication process, unless special countermeasures are taken. This can make the function F S computed by a CNN S truly unique. At the same time, since CNNs are integrated electrical systems, dedicated on-chip measurement circuitry can determine the fabrication mismatches, and deliver a sufficiently detailed description D(S) to simulate F S . Such types of self-measuring cells are already today in standard use for calibration purposes [26]. Furthermore, it is known that there is a stable regime where the fabrication mismatches determine the CNN behavior, and where they override circuit noise and temperature variations [START_REF] Xavier De Souza | Toward CNN Chip-Specific Robustness[END_REF] [START_REF] Hillier | CNNOPT Learning CNN Dynamics and Chip-Specific Robustness[END_REF]. Altogether, said properties make CNNs quite interesting candidates for SIMPL systems.

Implementation

We propose two concrete candidates for CNN-based SIMPL systems. Firstly, CNNs employed for specialized tasks (see above), for example image processing tasks, where they are known to outperform classical architectures by factors of 10 -1,000 [START_REF] Chua | CNN Universal Chips crank up the computing power[END_REF] [25] [START_REF] Roska | Cellular Wave Computers for Brain-Like Spatial-Temporal Sensory Computing[END_REF].

Another attractive option, which we discuss in greater detail, is a template and circuit-design that has been recently devised in our group [START_REF] Csaba | On-Chip Electric Waves: An Analog Circuit Approach to Physical Uncloneable Functions[END_REF]. It is inspired by the high internal complexity of optical PUFs [START_REF] Pappu | Physical One-Way Functions[END_REF], in whose time evolution many internal scattering components interact in parallel, leading to a high computational complexity and to laborious simulatability.

Our template has the remarkable property that it effectively transfers optical behavior onto a CNN (i.e. onto an electrical integrated circuit), which then behaves quasioptical, that is, similar to an optical system. In particular, the electrical current flowing through a certain reference point in each CNN-cell is equivalent to the local light intensity in an optical interference reference system.

The upcoming figures provide the templates and cell architecture of this 3-layer CNN, as well as simulation results that confirm the quasi-optical behavior. Figure 1 shows the templates and the interaction structure of the proposed 3-layer CNN. Figure 2 illustrates the circuit-level design. Figure 3 provides simulation data which shows the quasi-optical interference patterns in the linear (left) and non-linear/mismatched case (right). Figure 4 illustrates that local changes in the structure propagate globally. This further illustrates the quasi-optical nature and the high computational complexity of the structure: Its evolution involves many interacting subunits in parallel. The described CNN-design seems particularly suited as SIMPL system because its quasi-optical behavior fosters pairwise interaction between the cells throughout the structure. This leads to a particularly strong, inherent parallelism, which will be costly to simulate on digital architectures. Furthermore, as we could show in simulations, the behavior of the quasi-optical SIMPL automatically shifts into a non-linear, highly complex regime through the occurring manufacturing mismatches, which can be exploited even better for our purposes. In opposition to three-dimensional optical PUFs, its description D(S) can be determined by in-built on chip measurement circuitry.

+ - + - 1 R 2 R 3 R V(state) -V(output) 4
Another very important characteristics of our circuit that its behavior is sensitive, but not chaotic. Chaotic circuits are well known [START_REF] Kennedy | Three steps to chaos. II: A Chua's circuit primer[END_REF] and several CNN templates are known to realize chaos [START_REF] Zou | A chaotic attractor with cellular neural networks[END_REF] [17] [START_REF] Gomez-Gesteira | Experimental Chua's Circuit Arrays As an Autowave Simulator[END_REF]. The time trajectories of a chaotic system are irreproducible in a real physical environment and are hence unsuited as a SIMPL system. Security Aspects. A 100 × 100 cell CNN with our architecture leads to the following specific numbers: It requires a description D(S) containing about 10 4 • 19 template values, which is about 100 kB of information. In order to simulate the real-time evolution which the CNN undergoes in a few microsecond time frame, 10 4 coupled differential equations need to be solved (i.e., one for each cell). We estimate that this gives us a speed advantage of 10 -100 to comparable digital computing machines. Please note also that CNNs are very small and energy efficient, allowing their integration into small devices, while classical architectures with comparable computing power will often be distinguishable already by their size on mobile devices such as smart cards or security tokens.

SIMPL Systems from Special SRAM Memories

Introduction and General Idea

One practical and stable, but only consumer secure SIMPL candidate will be presented in this section. It is based on a special design of SRAM memories, which we call "skew design". Its basic idea is to design the SRAM-cells such that they exhibit varying behavior in different operational voltage regions. Some of the cells (cells of type 1) will function properly over the whole operational voltage range. Others, of type 2, will possess stable read operations, but exhibit (intended) write failures whenever the operational voltage V DD is below a certain threshold. This means that in these V DD regions, the content of the cell is not changed or affected by write procedures. Below the threshold, however, the write operation in cells of type 2 functions properly. Finally, there are cells of type 3, which contain a fixed bit value (0 or 1). It has been hardwired into them already in their fabrication, and their content cannot be changed by any write operation at all, regardless of the applied operational voltage. Now, imagine an SRAM-memory M where cells of the described three types are randomly distributed or mixed. We call such a memory a "skew memory". Imagine further that on the basis of M , we build a larger hardware system S, which repeats the following feedback loop l times at maximal operational speed.

Feedback loop, iteration i: S is depicted schematically in Fig. 5. In order to associate a global input and a global output with S, we may say that the values b 0 that occured in the last q iterations of the loop. In this sense, we can interpret the behavior of S as a function F S mapping global inputs to outputs. Then, F S has the following properties:

1. Write bitvalues b i 1 , . . . , b i k into the addresses W R i 1 , . . . , W R i k of M 2. Read out the bit values B i 1 , . . . , B i m from the addresses READ i 1 , . . . , READ i
1 , . . . , b 0 k , W R 0 1 , . . . , W R 0 k , READ 0
(i) F S can be individualized by changing the design of the memory M . To that aim, for example memory cells of type 3 (fixed bitvalues) can be distributed randomly over the memory in a final fabrication step. (ii) If the distribution of the cells of type 1, 2 and 3 is known, the function F S can be simulated digitally. (iii) The simulation of F S on a standard architecture will be slower than the real-time computation of F S by S. Also configurable hardware or ASICs that are not based on a skew design will have a speed disadvantage. In both cases, the speed gap will only be a constant factor, however. (iv) If the special skew design of SRAM cells is legally protected, then an adversary needs his own chip foundry to produce a hardware system that implements F S comparably quickly, since ordering ASICs with a skew design will be legally prohibited.

The above properties qualify S as a consumer secure SIMPL system. We will discuss the practical implementation over the next section.

Implementation

A concrete skew design developed in our group [START_REF] Srinivas | SRAM for use in Physical Cryptography[END_REF] is illustrated in Fig. 1a), with width and length specified beside each transistor. The functionality of the design based on TSMC 0.18 µm technology has been succssfully verified with Spectre [START_REF]Virtuoso Spectre Circuit Simulator[END_REF] simulations. The corresponding results are illustrated in Figure 7. In our case, V DD min = 1.4 V, V DD max = 1.7 V , and V DD f uncmin = 1.58 V . The memories, which will all share the same layout, can be individualized towards the end of manufacturing by fixing the content of some individually chosen cells to certain values. This means that the resulting structure will not be manufacturer resistant in the sense of [START_REF] Gassend | Physical Random Functions[END_REF], but will at least require a fraudster to possess its own chip foundry. The common SRAM-cell arragement will be contained in the general simulation algorithm Sim, and the individual description D(S) consists of the cells that have been fixed to certain values. Please note that the described individualization can be carried out on the basis of a pseudorandom number sequence, which means that a short, few-hundred bit long random seed s suffices as D(S).

The basic implementation of the feedback-loop is sketched in Fig. 1b). The implementation of the pseudo-random generator is carried out by an LSFR, since a LSFR works very quickly. Computationally more laborious PRNGs could perhaps be implemented more quickly by a fraudster in his hardware. He would thereby regain some of his speed disadvantage. Please note that we do not require a PRNG with cryptographic security in this application, but merely a PRNG with a long periodicity, such that as many memory cells as possible are at least once written to or read from in the feedback loop.

The relative speed advantage of the real system can be further amplified by activating and writing into multiple word lines during one write cycle. Due to the skew design, the same value written in several lines will not necessarily result in the same cell content. Based on the simulation data we obtained, we estimate that the relative speed advantage of a SIMPL SRAM memory will be a factor on the order of 10, even compared to dedicated, configurable hardware such as FPGAs. At the same time, since all operations on the SRAM-memory are fully digital and well-defined, the content of the memory can be precisely simulated and predicted.

Compared to optical SIMPLs [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF] and CNN-SIMPLs, the great advantage of the SRAM-variant is its practicality and stability. It can be implemented relatively cheaply, integrated in existing systems, and requires only very short descriptions D(S). This comes at the cost of losing their technological security, and exchanging it against consumer security (see page 5). Nevertheless, this seems acceptable in many applications.

Security Aspects. Let us discuss a few security relevant aspects. A fraudster who wants to imitate the skew SIMPL systems without a skew architecture has a number of basic possibilities.

First of all, he may try to implement the feedback loop in full logic, that is, without any memory cells at all. His hope may be that pure logic operations work faster than memory read and write steps, and that he can so outperform (or at least match) the speed of the original SIMPL. However, if the memory is sufficiently large, then the construction of such a pure logic will be prohibited by size and complexity constraints.

This means that the faker needs to employ some sort of memory in his attempts. SRAM memories are, in general, the fastest currently available technology, meaning that the faker should use SRAM cells, too. If he cannot rely on skew cells, however, he cannot obtain the result of the WRITE operation in a skew cell (which is a function of the WRITE value, the actual operational voltage and the type of the cell) within one WRITE step.

The faker rather needs to compute the resulting value "by hand" before he writes it into a classical cell. To that end, he needs to look up the type of the cell before writing the value. That costs him one extra read operation before he executes the write procedure. Furthermore, computing the resulting write value "by hand" also costs time.

Overall, a faker without a skew memory requires one read operation, some computation and one write operation in order to emulate what happens within one write step of the skew memory. This provides a speed advantage of a factor around 2, as desired.

As said earlier, our group currently investigates designs where the SIMPL memory allows to write the same bit block into more than one word line simultaneously. The values that arrive in the multiple lines eventually differ due to the individual skew design of the cells. This could rise the speed advantage to a constant factor on the order of 10.

Conclusions

SIMPL Systems are a novel security concept, which can be regarded as a public key version of Physical Unclonable Functions [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF]. Structurally, they function like a private/public key cryptosystem, with the notable difference that the equivalent to the private key is a physically hard-to-reproduce structure, which does not contain any secret information at all. This leads to critical security and practicality advances. In this paper, we reviewed the basic concepts presented in [START_REF] Rührmair | SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions[END_REF], but mainly focused on promising IC-based implementations of SIMPL systems.

Our first idea was to employ large, analog computing arrays as SIMPL systems. They evolve in parallel and by exchanging analog signals between their subunits, creating a significant computational power and complexity. At the same time, the arrays can be designed to strongly depend on fabrication mismatches, making the function which they implement individual and unique. We suggested to use cellular, non-linear networks with special templates, since they are the largest currently known analog circuits with up to millions of transistors. We proposed one concrete design on the template and circuit level, and evaluated its functionality in several simulations. One important asset of CNN-based SIMPL systems was that they can eventually lead to technologically secure SIMPL systems.

Our second idea was to use special ASICs as SIMPL systems, whose circuit design implements one specific digital function more efficiently than a standard architecture. We suggested special SRAM designs, where the dimensions of the SRAM-cells are varied in such a fashion that their functionality depends on the applied operational voltage. This creates a small, constant computational overhead in the simulation of the cells, especially in the case where many subsequent read and write operations are applied at maximal speed and at quickly varied operational voltages in a feedback loop. The feedback loop also allows us to extend the relative, small computational overhead to larger absolute (but not relative!) time margins.

Future work will focus on implementing these structures in silicon, and on the analysis of their concrete time margins over cryptographic adversaries.

Fig. 1 .

 1 Fig. 1. Templates and interaction structure of our 3-layer CNN-SIMPL system.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Circuit level design of our proposed CNN-SIMPL system.

Fig. 4 .

 4 Fig. 4. A difference map that illustrates the global sensitivity of our CNN design to a local change in the structure. We changed only a single template at a particular position (denoted by B in the figure), which was even located far away from the input exciting the structure (marked as In). This altered the global behavior of the circuit detectably. The figure shows the difference of the values E 1 z and E 2 z obtained by two simulations, one for the original value of the templates, the other for one template value in position B altered.

m 3 .

 3 Switch to operational voltage V DD(i) 4. Determine the parameters necessary for the next iteration, namely b i+1 1 , . . . , b i+1 k , W R i+1 1 , . . . , W R i+1 k , READ i+1 1 , . . . , READ i+1 m , V DD(i + 1), as a pseudorandom function of the values B i 1 , . . . , B i m obtained in step 2.

  1 , . . . , READ 0 m , V DD(0) that are necessary to start the loop, constitute its global input. After the last of the l iterations, the values B l 1 , . . . , B l m can serve as the global output of S. Alternatively, one may define the global output to be a function (e.g. a hash function) of the values B l-q+1 1 , . . . , B l-q+1 m , B l-q+2 1 , . . . , B l-q+2 m , . . . , B l 1 , . . . , B l m

Fig. 5 .

 5 Fig. 5. Schematic illustration of the input-output behavior of S and of the function FS.

Fig. 6 .

 6 Fig. 6. (a) The SRAM cell layout. (b) The basic operation cycle of the SRAM-SIMPL system.

Fig. 7 .

 7 Fig. 7. Spectre Simulations confirm the desired behavior: Write failures occur at certain voltages, meaning that the content of the SRAM cell remains unchanged in the WRITE operation. At the same time, the READ operation functions properly at all voltages.

1 .

 1 For all challenges C i ∈ C, the algorithm Sim on input For a time period of length t C , Eve is given the numerical description D(S) and the code of the algorithm Sim. (b) Within this time period t C , Eve is furthermore granted adaptive physical access to the system S at adaptively chosen time points. However, her overall access times must add up to a total of at most t P h . (c) After the time period t C has expired, Eve can still access D(S) and Sim, but has no physical access to S any more. She is presented with a challenge C i0 that was chosen uniformly at random from the set C, and must output a value V Eve . We say that Eve succeeded in the above experiment if the following conditions are met:

	C i , D(S)
	outputs R i in feasible time.
	2. Any cryptographic adversary Eve will succeed in the following security experi-
	ment with a probability of at most ǫ:
	(a)

  2. Build a functional physical clone S ′ of S, which may be a physical system of a possibly very different structure or different lengthscales than S, that enables Eve to determine the values R i for (almost) all C i ∈ C correctly and comparably quickly as by experiment on S. 3. Build a digital clone, which is a computer algorithm Alg that numerically computes the values Alg(C i ) = R i for (almost) all C i ∈ C comparably quickly as by an experiment on S.

  IDENTIFICATION OF ENTITIES BY SIMPL SYSTEMS 1. Bob obtains the information D(S), Sim, t max , and C associated with Alice from the public register. 2. Bob sends a number of randomly chosen challenges C 1 , . . . , C k ∈ C to Alice. 3. Alice determines the corresponding responses R 1 , . . . , R k by experiment on her SIMPL system S, and returns them immediately to Bob. 4. Bob receives values V 1 , . . . , V k , and measures Alice's response time (i.e. the time between the two events of sending C 1 , . . . , C k and receiving V 1 , . . . , V k ). If this time is above the threshold 2 • t max , he aborts the protocol. 5. Bob checks through simulation by the algorithm Sim if for all i = 1, . . . , k,

1]: Protocol 2:

Acknowledgements

This work was conducted in the course of the Physical Cryptography Project at the TU München. Support by the Institute for Advanced Study and the International Graduate School of Science and Engineering of the TU München is gratefully acknowlegded. We thank Peter Vogl, Tamas Roska, and Wolfgang Porod for helpful discussions.