Design Methodologies for Secure Embedded Systems

Lecture Notes in Electrical Engineering Volume 78 Cover Image: Hard’n’Soft c Konstantin Inozemtsev 2008 obtained from istockphoto.com Alexander Biedermann and H. Gregor Molter (Eds.) Design Methodologies for Secure Embedded Systems Festschrift in Honor of Prof. Dr.-Ing. Sorin A. Huss ABC Alexander Biedermann Technische Universität Darmstadt Department of Computer Science Integrated Circuits and Systems Lab Hochschulstr. 10 64289 Darmstadt, Germany E-mail: biedermann@iss.tu-darmstadt.de H. Gregor Molter Technische Universität Darmstadt Department of Computer Science Integrated Circuits and Systems Lab Hochschulstr. 10 64289 Darmstadt, Germany E-mail: molter@iss.tu-darmstadt.de ISBN 978-3-642-16766-9 e-ISBN 978-3-642-16767-6 DOI 10.1007/978-3-642-16767-6 Library of Congress Control Number: 2010937862 c 2010 Springer-Verlag Berlin Heidelberg This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broad￾casting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typeset: Scientific Publishing Services Pvt. Ltd., Chennai, India. Printed on acid-free paper 987654321 springer.com Sorin A. Huss Preface This Festschrift is dedicated to Mr. Sorin A. Huss by his friends and his Ph.D. students to honor him duly on the occasion of his 60th birthday. Mr. Sorin A. Huss was born in Bukarest, Romania on May 21, 1950. He attended a secondary school with emphasis on mathematic and scientific topics in Dachau near Munich and after his Abitur he studied Electrical Engineering with the discipline information technology at the Technische Universit¨at M¨unchen. 1976 he started his career at this university as the first research assistant at the newly established chair for design automation. Due to his very high ability he was a particularly important member of the staff especially in the development phase. In his research Mr. Huss dealt with methods for design automation of integrated circuits. The results of his research activities and his dissertation “Zur interaktiven Optimierung integrierter Schaltungen” were published in very high￾ranking international proceedings and scientific journals. In his dissertation he started from the recognition that the computer-aided dimensioning of integrated circuits on transistor level normally leads to a very bad conditioned optimization problem and that this aspect played the central role in solving this problem. Mr. Huss provided important contributions to this matter which were advanced in future activities of the chair and finally resulted in the establishment of a company. Today, 15 employees of the company MunEDA are busy with the production and the world-wide sale of software tools for the design of analog components in microchips. In 1982, Mr. Huss changed from university to industry and then worked at the AEG Concern in several positions. At last he was responsible for the development and adoption of new design methods as well as for the long-term application of the corresponding design systems as a department manager at the development center Integrated Circuits. Design tools that were developed under his direc￾tion, were used not only in the AEG Concern but also in famous domestic and foreign companies for the development of microelectronic circuits and systems. Important cross-departmental functions and the preparation of publicly funded major research projects indicate that his professional and organizational skills were well appreciated. Despite his technical-economical aim and the surrounding circumstances of internal release procedures Mr. Huss was able to document the academic level of the activities in his field of work by publications and talks outside of the company, too. One of these publications brought forth the award of the ITG in 1988, for one of the best publications of the year. After six years of university experience and eight years of employment in industry, Mr. Huss had proved to be a well appreciated and internationally accepted expert in the field of the computer￾aided design of integrated circuits and systems. VIII Preface After having obtained a call for a C4 professorship in Computer Engineering at the Technische Hochschule Darmstadt, Mr. Huss started his work as a full professor in Darmstadt on July 1, 1990. Since that time Prof. Huss not only had a decisive impact on the technical sector of the Department of Computer Science. Since 1996 he acts as a co-professor at the Department of Electrical Engineering of the Technische Universit¨at Darmstadt. With his assistance, the field of study Information System Technology (IST) was founded as cooperation between the Department of Computer Science and the Department of Electrical Engineering. In the same year, he rejected an appointment for a C4 professorship for technical computer science at the University Bonn and an offer as a head of the Institute for systems engineering at GMD, St. Augustin, to continue research and teaching at the TU Darmstadt. On the basis of design methods for embedded systems, the focus of his re￾search has enlarged and now connects aspects of heterogeneous systems with IT-systems and the automotive sector. More than 140 publications evidence his research activities. His contributions to research were acknowledged inter alia in 1988 with the Literature Award of the Information Technology Society (VDE/ITG), the Outstanding Paper Award of the SCS European Simulation Symposium in 1998, and both the Best Paper Award of the IEEE International Conference on Hardware/Software Codesign-Workshop on Application Specific Processors and the ITEA Achievement Award of the ITEA Society in 2004. Apart from his memberships in ACM, IEEE, VDE/ITG and edacentrum he is – due to his expert knowledge about the design of secure embedded systems – head of one of three departments of the Center of Advanced Security Research Darmstadt (CASED). CASED was established in the year 2008 by the Hessian campaign for the development of scientific-economical excellence (LOEWE) as one of five LOEWE-Centers. Just the research group lead by Prof Huss which deals with the design of secure hardware, has presented more than fifty inter￾national publications since then. An Award for Outstanding Achievements in Teaching in the year 2005 and other in-house awards for the best lecture fur￾thermore evidence his success in teaching. More than a dozen dissertations that have been supported by Prof. Sorin A. Huss to the present day complete the view of an expert, who does not only have extensive knowledge in his fields of research but is also able to convey his knowledge to others. We wish Prof. Dr.-Ing. Sorin Alexander Huss many more successful years! November 2010 Kurt Antreich Alexander Biedermann H. Gregor Molter Joint Celebration of the 60th Birthdays of Alejandro P. Buchmann, Sorin A. Huss, and Christoph Walther on November 19th, 2010 Honourable Colleague, Dear Sorin, Let me first send my congratulations to you as well as to the other two guys. You jointly celebrate your sixtieths birthdays this year. I wish you all the best for your future work at TU Darmstadt! Sorin, let me first thank you for the time you served as one of my Deputies General in that treadmill they call “Dekanat”. It was difficult for you to reserve some of your spare time for that voluntary, additional job. I appreciate that you agreed to take over this purely honorary post. Your advice has always been helpful for me. Your research and teaching activities are extraordinarily successful. Your success has led to a number of awards, from which I can only mention the most outstanding ones: Literature Award of the IT Chapter of the VDE (the German association of electrical engineers), European ITEA Achievement Award, Teaching Award of the Ernst-Ludwigs-Hochschulgesellschaft. You were one of the initiators of TU Darmstadt’s bachelor/master program in information systems technology. To conclude this list, I would also like to mention that you are one of the domain directors of CASED, which is an important position not only for CASED itself but for the department and for TU Darmstadt as well. You three guys are true institutions of the departments (I am tempted to speak of dinosaurs, however, in an absolutely positive sense). You have seen colleagues come and go. Due to your experience and your long time of service in the department, you have become critical nodes of the departments corporate memory network. Your experience has been deciding many discussions typically (yet not exclusively) for the better. I should mention that each of you three guys is equipped with a specific kind of spirit. Your humorous comments, always to the point, made many meetings of the colleagues really enjoyable for the audience (well, the meeting chair did not always enjoy, but thats fine). You have always combining passion with reason, spirit with analysis, vision with rationality. On behalf of the colleagues, the department, and TU Darmstadt, I wish you three guys that you will have another great time together with all of us and an even longer chain of success stories than ever. Happy Birthday! November 2010 Karsten Weihe Dean of the Department of Computer Science Technische Universit¨at Darmstadt The Darmstadt Microprocessor Practical Lab Some Memories of the E.I.S. Times At the beginning of the 1980s, the publication of the book “Introduction to VLSI-Systems” by Mead/Conway initiated a revolution in the design of inte￾grated circuits not only in the United States – it had a great feedback also in Germany. So it was intensively thought about establishing the design of inte￾grated circuits as a field of study at the Technical Universities and Universities of Applied Sciences. Funded by the German Federal Ministry of Research and Technology (BMFT) the project E.I.S. (Entwurf Integrierter Schaltungen [design of integrated circuits]) was started in close cooperation with industrial concerns in 1983. The project was coordinated by the Society for Mathematics and Data Processing at Bonn (today: Fraunhofer Institute) and had the following objec￾tives: – Intensification of the research in the field of the design of microelectronic circuits at the Universities and progress in the theory of design methods – Design and development of experimental CAD-software for microelectronic circuits for the use in research and teaching – Design and test of application-specific circuits – Enhancement of the number of computer scientists and electrical engineers with a special skill in VLSI-Design Following the publication of the book “Introduction to VLSI-Systems” by Mead/Conway also people in Germany quickly recognized that VLSI-Design was not a kind of black magic but was based on a well-structured methodology. Only by means of this methodology it would be possible to handle the exponentially increasing design complexity of digital (and analog) circuits expected in the future. Mr. Huss met this challenge very early and established a design lab at Darm￾stadt. The practical lab was intended to impart the complete design process from the behavior-oriented design model to the point of the layout. Based on a high￾level-design methodology – which was taught in an accompanying lecture – and by using a design example, the entire development should be comprehended in detail and realized by means of modern CAE-tools. The practical lab therefore allowed an integrated education in the field of high-level-design methodology which was theoretically sound and deepened in practice. The design was car￾ried out according to the principle of “Meet in the Middle” which was common practice instead of using the “Top Down” method. VHDL was used as formal language, as it enabled a description on all levels of abstraction. The neces￾sary transformations were explained didactical cleverly using the Y-diagram of Gajski. XII Some Memories of the E.I.S. Times The main objective of the practical lab at this was not only learning the lan￾guage, but to rehearse the Methodology in detail up of the design of a standard cell in a 1.5m CMOS-technology with about 16,000 transistors. The production took place within the framework of the EUROCHIP-program. The abstract of the practical lab at the TH Darmstadt was introduced to an international group of experts at the 6th E.I.S. Workshop 1993 in T”ubingen. As the Goethe Univer￾sity Frankfurt ran a practical lab with a similar intention, a lively exchange of experiences arose subsequent to the E.I.S. Workshop. This fruitful cooperation in teaching later brought forth a textbook with the title “Praktikum des moder￾nen VLSI-Entwurfs”. The authors were Andreas Bleck, Michael Goedecke, Sorin A. Huss and Klaus Waldschmidt. The book was published by Teubner Verlag, Stuttgart in 1996. Unfortunately, it is no longer available due to developments in the publishing sector. I gladly remember the cooperation with colleague Mr. Huss and his team. This cooperation later also continued in the area of research, for instance in the context of the SAMS-Project, which was funded by the BMBF and the edacentrum. For the future, I wish colleague Mr. Huss continued success and pleasure in teaching and research. November 2010 Klaus Waldschmidt Technische Informatik Goethe Universit¨at Frankfurt Table of Contents Towards Co-design of HW/SW/Analog Systems ..................... 1 Christoph Grimm, Markus Damm, and Jan Haase A Flexible Hierarchical Approach for Controlling the System-Level Design Complexity of Embedded Systems ........................... 25 Stephan Klaus Side-Channel Analysis – Mathematics Has Met Engineering .......... 43 Werner Schindler Survey of Methods to Improve Side-Channel Resistance on Partial Reconfigurable Platforms ......................................... 63 Marc St¨ottinger, Sunil Malipatlolla, and Qizhi Tian Multicast Rekeying: Performance Evaluation ........................ 85 Abdulhadi Shoufan and Tolga Arul Robustness Analysis of Watermark Verification Techniques for FPGA Netlist Cores .................................................... 105 Daniel Ziener, Moritz Schmid, and J¨urgen Teich Efficient and Flexible Co-processor for Server-Based Public Key Cryptography Applications ........................................ 129 Ralf Laue Cellular-Array Implementations of Bio-inspired Self-healing Systems: State of the Art and Future Perspectives ............................ 151 Andr´e Seffrin and Alexander Biedermann Combined Man-in-the-Loop and Software-in-the-Loop Simulation: Electronic Stability Program for Trucks on the Daimler Driving Simulator ....................................................... 171 Uwe Baake and Klaus W¨ust Secure Beamforming for Weather Hazard Warning Application in Car-to-X Communication ......................................... 187 Hagen St¨ubing and Attila Jaeger Author Index .................................................. 207 Towards Co-design of HW/SW/Analog Systems Christoph Grimm, Markus Damm, and Jan Haase Vienna University of Technology Chair of Embedded Systems Gußhausstrae 27-29 1040 Wien, Austria {grimm,damm,haase}@ict.tuwien.ac.at Abstract. We give an overview of methods for modeling and system level design of mixed HW/SW/Analog systems. For abstract, functional modeling we combine Kahn Process Networks and Timed Data Flow Graphs. In order to model concrete architectures, we combine KPN and TDF with transaction level modeling. We describe properties and issues raised by the combination of these models and show how these models can be used for executable specification and architecture exploration. For application in industrial practice we show how these models and methods can be implemented by combining the standardized SystemC AMS and TLM extensions. Keywords: Analog/Digital Co-Design, KPN, Timed Data Flow, Sys￾tem Synthesis, Refinement, Refactoring, SystemC AMS extensions. 1 Introduction Applications such as wireless sensor networks, cognitive radio, and multi-stan￾dard communication systems consist of multi-processor hardware, complex mul￾ti-threaded software, and analog/RF subsystems.Anew complexity raised by such applications is the tight functional interaction between the different do￾mains, even at mixed levels of abstraction. Therefore, specification and archi￾tecture level design require a comprehensive approach for system level design. System level design includes the following issues: 1. Executable specification of the intended behavior including analog/RF be￾havior and multi-process HW/SW systems. 2. Architecture exploration by mapping the executable specification to abstract processors, and adding SW that improves behavior of analog/RF components (calibration, error detection/correction, etc.). 3. System integration, mostly by mixed-level simulation, upon availability of hardware designs and software programs. Compared with HW/SW co-design, the co-design of HW/SW/Analog systems lacks models, methods and tools that go beyond modeling and simulation. A major problem for co-design of HW/SW/Analog systems is that modeling and A. Biedermann and H. Gregor Molter (Eds.): Secure Embedded Systems, LNEE 78, pp. 1–24. springerlink.com ￾ Springer-Verlag Berlin Heidelberg 201 2 C. Grimm, M. Damm, and J. Haase design of HW/SW systems at one hand, and of analog systems at the other use fundamentally different methods: – HW/SW Co-design is done usually “top-down”, relying on existing platforms that enable to some extent abstraction from realization. In contrast, analog design is rather done “bottom up”. – Design of HW/SW systems can to some extent be automated and formalized. In contrast, analog design is sometimes considered as “black magic”. In this work we give an overview of methods that together draw the vision of a co-design methodology that is applicable to HW/SW/Analog Systems as a whole as shown by Fig. 1. We simplify the problem a lot by taking the analog (and also digital) circuit design out of the challenge. Instead we assume that “HW/SW/Analog Co-Design” gets characterized models from analog design, and validated IP or platforms from digital design. Like in HW/SW Co-Design, we propose an interactive strategy where architecture mapping selects a limited number or architectures that are evaluated by modeling and simulation based on SystemC. However, we propose to restrict modeling techniques to Kahn Process Networks (KPN), Timed Data Flow (TDF), and Transaction Level Modeling (TLM). This allows us to also address issues such as (maybe in future work automated) partitioning or system synthesis. In the following, we first describe related work and KPN, Timed Data Flow (TDF) and Transaction Level Modeling (TLM). In Sect. 2 we discuss issues Fig. 1. HW/SW/Analog Co-Design with Executable Specification and Architecture Exploration consisting of architecture mapping and performance estimation by co￾simulation of mixed TLM/TDF models Towards Co-design of HW/SW/Analog Systems 3 raised by the combination of KPN, TDF and TLM and show how they can be modelled using SystemC. In Sect.3we show how the combination of KPN, TDF and TLM models can be used for architecture exploration. In Sect. 4 we discuss a real-world example. 1.1 Related Work For many years, modeling languages were the main tools for designers of HW/- SW/analog systems. A prominent success was the advent of standardized and agreed modeling languages such as VHDL-AMS [1] and Verilog-AMS [2] that fo￾cus design of analog/digital subsystems. Recently, AMS extensions for SystemC have been standardized that address the co-design of mixed HW/SW/Analog systems better [3]. However, we believe that co-design should be more ambi￾tious than just being able to co-simulate. First attempts to address co-design are made in [4,5,6,7] focusing the design of analog/mixed-signal subsystems. Interactive methodologies that tackle the transition from data flow oriented de￾scriptions to analog/digital circuits are described in [8,9,10,11]. In order to deal with overall HW/SW/Analog systems, models from HW/SW Co-Design and from analog/RF design have to be combined. In HW/SW Co-Design, models must show a maximum of parallelism. Task Graphs [12], Kahn Process Networks (KPN) [13] or Synchronous Data Flow (SDF) [14] are widely used in that context. Especially KPN and SDF maintain a maximum of parallelism in the specification while being independent from timing and synchronization issues, thus being useful for executable specification. Pioneering work was done in the Ptolemy Project [15,16]. Jantsch [17] gives a good summary and formalizes models of computation applied in embedded system design, including combined models. Transaction Level Modeling (TLM, [18,19]) and other means in SpecC and SystemC in contrast specifically enable to model timing and synchronization at architecture level. SysteMoC enables design of digital signal processing systems combining several models [20], but lacks support for analog/RF systems. In analog/RF systems, behavioralrepresentations abstract from physical quan￾tities. However, abstraction from time is hardly possible because typical analog functions such as integration over time are inherently time dependent. Block diagrams in Simulink or Timed Data Flow (TDF) in the SystemC AMS exten￾sions [3] therefore abstract structure and physical quantities while maintaining continuous or discrete time semantics. It is difficult to bring the worlds of HW/SW Co-Design and analog/RF de￾sign together. Main focus of the Ptolemy project [15] was simulation and HW or SW synthesis, but not overall system synthesis. Approaches such as Hybrid Automata ([32], Model Checking) lack the ability to deal with complex HW/SW systems. Hybrid Data Flow Graphs (HDFG [5,21], Partitioning) focus the border between discrete and continuous modeling. The functional semantics of HDFG 4 C. Grimm, M. Damm, and J. Haase offers – in combination with functional languages for system specification – in￾teresting perspectives for specification of parallel systems while being able to describe HW/SW/analog systems. However, due to availability of tools and lan￾guages we focus on KPN and TDF in the following as a starting point for system level synthesis, and TLM for architecture level modeling. 1.2 Kahn Process Networks, Timed Data Flow, and TLM Kahn Process Networks (KPN). KPN are a frequently used model of com￾putation that allows easy specification of parallel, distributed HW/SW systems. In KPN, processes specified e.g. in C/C++ communicate via buffers of infinite length. Writing is therefore always non-blocking, whereas reading is blocking. KPN are an untimed model of computation: Timing is not specified and not necessary because the results are independent from timing and scheduling. KPN are specifically useful for the executable specification of HW/SW systems, be￾cause they – in contrast to sequential program languages – maintain parallelism in an executable specification and therefore enable the mapping to parallel hard￾ware, e.g. multi-processor systems. A particular useful property of KPN is that it enables abstraction of timing and scheduling: Outputs only depend on the input values and their order (determinacy), provided all processes are deterministic. Non-determinacy can for example be introduced by a non-deterministic merge process. In order to enable execution, scheduling algorithms (e.g. Park’s algorithm [22]) may be defined that restrict the size of the buffers (Bounded KPN, BKPN). However, a limited size of buffers cannot be guaranteed in general. Timed Data Flow (TDF). In order to overcome the restrictions of KPN considering scheduling and size of buffers, different subsets of KPN have been defined, most prominent of them the Synchronous Data Flow (SDF, [14]). In SDF, an undividable execution of a process consumes a constant number of tokens or samples from the inputs and generates a constant number of tokens at the outputs. Under these conditions, a static schedule with size-limited buffers can be determined before execution of the processes by solving the balancing equations foracluster of processes. For repeated inputs, the schedule is repeated periodically. Like KPN, SDF is an untimed model of computation. Nevertheless, SDF is used for representing digital signal processing (DSP) methods, assuming constant time steps between samples. In Timed Data Flow (TDF, [3,31]), each process execution is assigned a time step. In case of multiple samples per execution, the time step is distributed equally between the samples. Apart from specification of DSP algorithms, this enables the representation of analog signals by a sequence of discrete-time samples while abstracting from physical quantities and assumingadirected communication between analog components. A major benefit of TDF for the specification of analog and RF systems is the ability to embed other “analog” formalisms in the processes. The analog formalisms can be transfer functions