This thesis consists of six papers. In Paper I, we give an algorithm for merging sorted lists of monomials and together with a projection technique, we obtain a new complexity bound for the Buchberger-Möller algorithm and the FGLM algorithm. In Paper II, we discuss four different constructions of vector space bases associated to vanishing ideals of points. We show how to compute normal forms with respect to these bases and give complexity bounds. As an application we drastically improve the computational algebra approach to the reverse engineering of gene regulatory networks. In Paper III, we introduce the concept of multiplication matrices for ideals of projective dimension zero. We discuss various applications and, in particular, we give a new algorithm to compute the variety of an ideal of projective dimension zero. In Paper IV, we consider a subset of projective space over a finite field and give a geometric description of the minimal degree of a non-vanishing form with respect to this subset. We also give bounds on the minimal degree in terms of the cardinality of the subset. In Paper V, we study an associative version of an algorithm constructed to compute the Hilbert series for graded Lie algebras. In the commutative case we use Gotzmann's persistence theorem to show that the algorithm terminates in finite time. In Paper VI, we connect the commutative version of the algorithm in Paper V with the Buchberger algorithm. / At the time of doctoral defence, the following papers were unpublished and had a status as follows: Paper 3: Manuscript. Paper 4: Manuscript. Paper 5: Manuscript. Paper 6: Manuscript

Abstract This doctoral thesis addresses the design of embedded electronic systems based on run-time reconfigurable hardware technology –available through SRAM-based FPGA/SoC devices– aimed at contributing to enhance the life quality of the human beings. This work does research on the conception of the system architecture and the reconfiguration engine that provides to the FPGA the capability of dynamic partial reconfiguration in order to synthesize, by means of hardware/software co-design, a given application partitioned in processing tasks which are multiplexed in time and space, optimizing thus its physical implementation –silicon area, processing time, complexity, flexibility, functional density, cost and power consumption– in comparison with other alternatives based on static hardware (MCU, DSP, GPU, ASSP, ASIC, etc.). The design flow of such technology is evaluated through the prototyping of several engineering applications (control systems, mathematical coprocessors, complex image processors, etc.), showing a high enough level of maturity for its exploitation in the industry. / Resumen Esta tesis doctoral abarca el diseño de sistemas electrónicos embebidos basados en tecnología hardware dinámicamente reconfigurable –disponible a través de dispositivos lógicos programables SRAM FPGA/SoC– que contribuyan a la mejora de la calidad de vida de la sociedad. Se investiga la arquitectura del sistema y del motor de reconfiguración que proporcione a la FPGA la capacidad de reconfiguración dinámica parcial de sus recursos programables, con objeto de sintetizar, mediante codiseño hardware/software, una determinada aplicación particionada en tareas multiplexadas en tiempo y en espacio, optimizando así su implementación física –área de silicio, tiempo de procesado, complejidad, flexibilidad, densidad funcional, coste y potencia disipada– comparada con otras alternativas basadas en hardware estático (MCU, DSP, GPU, ASSP, ASIC, etc.). Se evalúa el flujo de diseño de dicha tecnología a través del prototipado de varias aplicaciones de ingeniería (sistemas de control, coprocesadores aritméticos, procesadores de imagen, etc.), evidenciando un nivel de madurez viable ya para su explotación en la industria. / Resum Aquesta tesi doctoral està orientada al disseny de sistemes electrònics empotrats basats en tecnologia hardware dinàmicament reconfigurable –disponible mitjançant dispositius lògics programables SRAM FPGA/SoC– que contribueixin a la millora de la qualitat de vida de la societat. S’investiga l’arquitectura del sistema i del motor de reconfiguració que proporcioni a la FPGA la capacitat de reconfiguració dinàmica parcial dels seus recursos programables, amb l’objectiu de sintetitzar, mitjançant codisseny hardware/software, una determinada aplicació particionada en tasques multiplexades en temps i en espai, optimizant així la seva implementació física –àrea de silici, temps de processat, complexitat, flexibilitat, densitat funcional, cost i potència dissipada– comparada amb altres alternatives basades en hardware estàtic (MCU, DSP, GPU, ASSP, ASIC, etc.). S’evalúa el fluxe de disseny d’aquesta tecnologia a través del prototipat de varies aplicacions d’enginyeria (sistemes de control, coprocessadors aritmètics, processadors d’imatge, etc.), demostrant un nivell de maduresa viable ja per a la seva explotació a la indústria.

Multi-stage programming is a valuable technique for improving the performance of computer programs through run-time optimization. Current implementations of multi-stage programming do not support run-time type introspection, which is a significant feature of modern object-oriented platforms such as Java and C#. This is unfortunate because many programs that use type introspection in these languages could be improved with multi-staging programming. The aim of this research is to investigate the interaction between multi-stage programming and object-oriented type introspection. This is done by the invention of a new programming language that is a multi-stage extension to C#. The language is capable of expressing traditional multi-stage programs as well as a new style of multi-stage programs that incorporate type introspection, most notably polytypic algorithms such as object serialization. A compiler for the language is implemented and freely available. The language is significant because it is the first object-oriented, multi-stage language; the first attempt to combine type introspection with multi-stage programming; and the first exploration of polytypic programming in a multi-stage context.

The vision of automated driving demands a highly available system, especially in safety-critical functionalities. In automated driving when a driver is not binding to be a part of the control loop, the system needs to be operational even after failure of a critical component until driver regain the control of vehicle. In pursuit of such a fail-operational behavior, the developed design process with software redundancy in contrast to conventional dedicated backup requires the support of automatic configurator for scheduling relevant parameters to ensure real-time behavior of the system. Multiple implementation methods are introduced to provide an automatic service which also considers task criticality before assigning task to the processor. Also, a generic method is developed to generate adaptation plans automatically for an already monitoring and reconfiguration service to handle fault occurring environment.

Memorization of a method is a commonly used re-factoring wherein developer modules the code of a method to save return values for some or all incoming parameter values. Whenever a parameter-tuple is received for the second or subsequent time, the method's execution can be elided and the corresponding saved value can be returned. It is quite challenging for developers to identify suitable methods for memorization, as these may not necessarily be the methods that account for a high fraction of the running time in the program. What are really sought are the methods that cumulatively incur signi_cant execution time in invocations that receive repeat parameter values. Our primary contribution is a novel dynamic analysis approach that emits a report that contains, for each method in an application, an estimate of the execution time savings to be expected from memorizing this method. The key technical novelty of our approach is a set of design elements that allow our approach to target real-world programs, and to compute the estimates in a re-grained manner. We describe our approach in detail, and evaluate an implementation of it on several real-world programs. Our evaluation reveals that there do exist many methods with good estimated savings that the approach is reasonably ancient, and that it has good precision (relative to actual savings).

Correct behavior of programs can be defined by their temporal properties. One of the options for formal specification of such properties is  linear temporal logic - LTL . This master's thesis describes design and implementation of a tool for automatic checking of temporal properties of programs, that are specified using Past-Time LTL formulae. The trace of a given program is analyzed in run-time and any violation of given formulae is reported in details to help to find the code location with a root cause of the bug.

No description available.

In line with the growth of software, code bases are getting bigger and more complex. As a result of this, the architectural patterns, which systems rely upon, are becoming increasingly important. Recently, decomposed architectural styles have become a popular choice. This thesis explores system behavior with respect to decomposing system granularity and external communication between the resulting decomposed services. An e-commerce scenario was modeled and implemented at different granularity levels to measure the response time. In establishing the communication, both REST with HTTP and JSON and the gRPC framework were utilized. The results showed that decomposition has impact on run-time behaviour and external communication. The highest granularity level implemented with gRPC for communication establishment adds 10ms. In the context of how the web behaves today, it can be interpreted as feasible but there is no discussion yet on whether it is theoretically desirable. / I linje med de växande mjukvarusystemen blir kodbaserna större och mer komplexa. Arkitekturerna som systemen bygger på får allt större betydelse. Detta examensarbete utforskar hur upplösning av system som tillämpar mikroservicearkitektur beter sig, och hur de påverkas av kommunikationsupprättande bland de upplösta och resulterande tjänsterna. Ett e-handelsscenario modelleras i olika granularitetsnivåer där REST med HTTP och JSON samt gRPC används för att upprätta kommunikationen. Resultaten visar att upplösningen påverkar runtimebeteendet och den externa kommunikationen blir långsammare. En möjlig slutsats är att påverkan från den externa kommunikationen i förhållande till hur webben beter sig idag är acceptabel. Men om man ska ligga inom teoretiskt optimala gränser kan påverkan ses som för stor.

In today's modern world, Cyber-Physical Systems (CPS) have gained widespread prevalence, offering tremendous benefits while also increasing society's dependence on them. Given the direct interaction of CPS with the physical environment, their malfunction or compromise can pose significant risks to human life, property, and the environment. However, as the complexity of CPS rises due to heightened expectations and expanded functional requirements, ensuring their trustworthy operation solely during the development process becomes increasingly challenging. This thesis introduces and delves into the novel concept of the 'Protective Shell' – a real-time safeguard actively monitoring CPS during their operational phases. The protective shell serves as a last line of defence, designed to detect abnormal behaviour, conduct thorough analyses, and initiate countermeasures promptly, thereby mitigating unforeseen risks in real-time. The primary objective of this research is to enhance the overall safety and security of CPS by refining, partly implementing, and evaluating the innovative protective shell concept. To provide context for collaborative systems working towards higher objectives — common within CPS as system-of-systems (SoS) — the thesis introduces the 'Emergence Matrix'. This matrix categorises outcomes of such collaboration into four quadrants based on their anticipated nature and desirability. Particularly concerning are outcomes that are both unexpected and undesirable, which frequently serve as the root cause of safety accidents and security incidents in CPS scenarios. The protective shell plays a critical role in mitigating these unfavourable outcomes, as conventional vulnerability elimination procedures during the CPS design phase prove insufficient due to their inability to proactively anticipate and address these unforeseen situations. Employing the design science research methodology, the thesis is structured around its iterative cycles and the research questions imposed, offering a systematic exploration of the topic. A detailed analysis of various safety accidents and security incidents involving CPS was conducted to retrieve vulnerabilities that led to dangerous outcomes. By developing specific protective shells for each affected CPS and assessing their effectiveness during these hazardous scenarios, a generic core for the protective shell concept could be retrieved, indicating general characteristics and its overall applicability. Furthermore, the research presents a generic protective shell architecture, integrating advanced anomaly detection techniques rooted in explainable artificial intelligence (XAI) and human machine teaming. While the implementation of protective shells demonstrate substantial positive impacts in ensuring CPS safety and security, the thesis also articulates potential risks associated with their deployment that require careful consideration. In conclusion, this thesis makes a significant contribution towards the safer and more secure integration of complex CPS into daily routines, critical infrastructures and other sectors by leveraging the capabilities of the generic protective shell framework.:1 Introduction 1.1 Background and Context 1.2 Research Problem 1.3 Purpose and Objectives 1.3.1 Thesis Vision 1.3.2 Thesis Mission 1.4 Thesis Outline and Structure 2 Design Science Research Methodology 2.1 Relevance-, Rigor- and Design Cycle 2.2 Research Questions 3 Cyber-Physical Systems 3.1 Explanation 3.2 Safety- and Security-Critical Aspects 3.3 Risk 3.3.1 Quantitative Risk Assessment 3.3.2 Qualitative Risk Assessment 3.3.3 Risk Reduction Mechanisms 3.3.4 Acceptable Residual Risk 3.4 Engineering Principles 3.4.1 Safety Principles 3.4.2 Security Principles 3.5 Cyber-Physical System of Systems (CPSoS) 3.5.1 Emergence 4 Protective Shell 4.1 Explanation 4.2 System Architecture 4.3 Run-Time Monitoring 4.4 Definition 4.5 Expectations / Goals 5 Specific Protective Shells 5.1 Boeing 737 Max MCAS 5.1.1 Introduction 5.1.2 Vulnerabilities within CPS 5.1.3 Specific Protective Shell Mitigation Mechanisms 5.1.4 Protective Shell Evaluation 5.2 Therac-25 5.2.1 Introduction 5.2.2 Vulnerabilities within CPS 5.2.3 Specific Protective Shell Mitigation Mechanisms 5.2.4 Protective Shell Evaluation 5.3 Stuxnet 5.3.1 Introduction 5.3.2 Exploited Vulnerabilities 5.3.3 Specific Protective Shell Mitigation Mechanisms 5.3.4 Protective Shell Evaluation 5.4 Toyota 'Unintended Acceleration' ETCS 5.4.1 Introduction 5.4.2 Vulnerabilities within CPS 5.4.3 Specific Protective Shell Mitigation Mechanisms 5.4.4 Protective Shell Evaluation 5.5 Jeep Cherokee Hack 5.5.1 Introduction 5.5.2 Vulnerabilities within CPS 5.5.3 Specific Protective Shell Mitigation Mechanisms 5.5.4 Protective Shell Evaluation 5.6 Ukrainian Power Grid Cyber-Attack 5.6.1 Introduction 5.6.2 Vulnerabilities in the critical Infrastructure 5.6.3 Specific Protective Shell Mitigation Mechanisms 5.6.4 Protective Shell Evaluation 5.7 Airbus A400M FADEC 5.7.1 Introduction 5.7.2 Vulnerabilities within CPS 5.7.3 Specific Protective Shell Mitigation Mechanisms 5.7.4 Protective Shell Evaluation 5.8 Similarities between Specific Protective Shells 5.8.1 Mitigation Mechanisms Categories 5.8.2 Explanation 5.8.3 Conclusion 6 AI 6.1 Explainable AI (XAI) for Anomaly Detection 6.1.1 Anomaly Detection 6.1.2 Explainable Artificial Intelligence 6.2 Intrinsic Explainable ML Models 6.2.1 Linear Regression 6.2.2 Decision Trees 6.2.3 K-Nearest Neighbours 6.3 Example Use Case - Predictive Maintenance 7 Generic Protective Shell 7.1 Architecture 7.1.1 MAPE-K 7.1.2 Human Machine Teaming 7.1.3 Protective Shell Plugin Catalogue 7.1.4 Architecture and Design Principles 7.1.5 Conclusion Architecture 7.2 Implementation Details 7.3 Evaluation 7.3.1 Additional Vulnerabilities introduced by the Protective Shell 7.3.2 Summary 8 Conclusion 8.1 Summary 8.2 Research Questions Evaluation 8.3 Contribution 8.4 Future Work 8.5 Recommendation

Partial evaluation is a program transformation technique that specializes a program with respect to part of its input. While the specialization is typically performed ahead-of-time, moving it to a later stage may expose additional opportunities and allow for faster residual programs to be constructed. In this thesis, we present a method for specializing programs at run-time, for compiled code, using an online partial evaluator. Although partial evaluation has several applications, the evaluation of the method primarily focuses on its performance benefits. The main research problem addressed in this thesis is that of incorporating an online partial evaluator in compiled code. The partial evaluator is a sourceto-source translator that takes and produces an abstract syntax tree (AST). Our approach consists of three parts, namely that of partially evaluating, obtaining a partially evaluable representation and run-time code emitting. Concretely, we use the concept of lifting to store an AST in the compiled code that the partial evaluator then specializes at run-time. The residual code is thereafter naively just-in-time (JIT) compiled through dynamically linking it back to the executable as a shared library. We evaluate the method on several programs and show that the specialized programs sometimes are faster even with a low recursion depth. Though, while the results are promising, the overhead is typically significant and therefore the break-even points are large. Further research, for example using an efficient JIT compiler, is required to better evaluate the performance benefits of the approach. / Partiell evaluering är en programtransformationsteknik som specialiserar ett program givet delar av dess indata. Typisk sätt specialiseras program innan de exekveras, men genom att flytta specialisering till då programmet körs kan ytterligare information utnyttjas och därmed snabbare residualprogram konstrueras. I det här examensarbetet presenteras en metod för att specialisera program i körtid med online partiell evaluering, specifikt för kompilerade program. Metoden utvärderas främst utefter prestanda, men det ska nämnas att partiell evaluering har fler tillämpningar än så. Det huvudsakliga problemet som examensarbetet undersöker är inkorporeringen av en programspecialiserare (partial evaluator) i kompilerad kod. Den programspecialiserare som används tar både som indata och producerar ett abstrakt syntaxträd (AST). Vårt tillvägagångssätt består av tre delar, nämligen programspecialisering, erhållning av en representation som kan specialiseras och slutligen kodgenerering i körtid. Mer specifikt används konceptet lyftning för att spara ett AST i den kompilerade koden som därefter partiellt evalueras av programspecialiseraren under körtid. Som ett sista steg just-in-time (JIT) kompileras residualprogrammet. Detta görs på ett naivt vis genom att programmet kompileras till ett delat bibliotek som därefter dynamiskt länkas tillbaka till huvudprogrammet. Metoden utvärderas på flera program och vi visar att de specialiserade programmen i vissa fall var snabbare och det även med små rekursionsdjup. Resultaten är lovande, men den overhead som metoden ger upphov till är ofta signifikant vilket gör att det krävs många iterationer innan det specialiserade programmet blir snabbare. Ytterligare forskning och tester, till exempel med en effektiv JIT kompilator, är nödvändig för att bättre kunna utvärdera metodens prestandafördelar.