@phdthesis{Ullah2012, author = {Ullah, Ehsan}, title = {New Techniques for Polynomial System Solving}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26815}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Since any encryption map may be viewed as a polynomial map between finite dimensional vector spaces over finite fields, the security of a cryptosystem can be examined by studying the difficulty of solving large systems of multivariate polynomial equations. Therefore, algebraic attacks lead to the task of solving polynomial systems over finite fields. In this thesis, we study several new algebraic techniques for polynomial system solving over finite fields, especially over the finite field with two elements. Instead of using traditional Gr{\"o}bner basis techniques we focus on highly developed methods from several other areas like linear algebra, discrete optimization, numerical analysis and number theory. We study some techniques from combinatorial optimization to transform a polynomial system solving problem into a (sparse) linear algebra problem. We highlight two new kinds of hybrid techniques. The first kind combines the concept of transforming combinatorial infeasibility proofs to large systems of linear equations and the concept of mutants (finding special lower degree polynomials). The second kind uses the concept of mutants to optimize the Border Basis Algorithm. We study recent suggestions of transferring a system of polynomial equations over the finite field with two elements into a system of polynomial equalities and inequalities over the set of integers (respectively over the set of reals). In particular, we develop several techniques and strategies for converting the polynomial system of equations over the field with two elements to a polynomial system of equalities and inequalities over the reals (respectively over the set of integers). This enables us to make use of several algorithms in the field of discrete optimization and number theory. Furthermore, this also enables us to investigate the use of numerical analysis techniques such as the homotopy continuation methods and Newton's method. In each case several conversion techniques have been developed, optimized and implemented. Finally, the efficiency of the developed techniques and strategies is examined using standard cryptographic examples such as CTC and HFE. Our experimental results show that most of the techniques developed are highly competitive to state-of-the-art algebraic techniques.}, subject = {Polynoml{\"o}sung}, language = {en} } @phdthesis{Xiu2012, author = {Xiu, Xingqiang}, title = {Non-commutative Gr{\"o}bner Bases and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26827}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Commutative Gr{\"o}bner bases have a lot of applications in theory and practice, because they have many nice properties, they are computable, and there exist many efficient improvements of their computations. Non-commutative Gr{\"o}bner bases also have many useful properties. However, applications of non-commutative Gr{\"o}bner bases are rarely considered due to high complexity of computations. The purpose of this study was to improve the computation of non-commutative Gr{\"o}bner bases and investigate the applications of non-commutative Gr{\"o}bner bases. Gr{\"o}bner basis theory in free monoid rings was carefully revised and Gr{\"o}bner bases were precisely characterized in great detail. For the computations of Gr{\"o}bner bases, the Buchberger Procedure was formulated. Three methods, say interreduction on obstructions, Gebauer-M{\"o}ller criteria, and detecting redundant generators, were developed for efficiently improving the Buchberger Procedure. Further, the same approach was applied to study Gr{\"o}bner basis theory in free bimodules over free monoid rings. The Buchberger Procedure was also formulated and improved in this setting. Moreover, J.-C. Faugere's F4 algorithm was generalized to this setting. Finally, many meaningful applications of non-commutative Gr{\"o}bner bases were developed. Enumerating procedures were proposed to semi-decide some interesting undecidable problems. All the examples in the thesis were computed using the package gbmr of the computer algebra system ApCoCoA. The package was developed by the author. It contains dozens of functions for Gr{\"o}bner basis computations and many concrete applications. The package gbmr and a collection of interesting examples are available at http://www.apcocoa.org/.}, subject = {Gr{\"o}bner-Basis}, language = {en} } @phdthesis{Groesslinger2009, author = {Gr{\"o}ßlinger, Armin}, title = {The Challenges of Non-linear Parameters and Variables in Automatic Loop Parallelisation}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-17893}, school = {Universit{\"a}t Passau}, year = {2009}, abstract = {With the rise of manycore processors, parallelism is becoming a mainstream necessity. Unfortunately, parallel programming is inherently more difficult than sequential programming; therefore, techniques for automatic parallelisation will become indispensable. We aim at extending the well-known polyhedron model, which promises this automation, beyond some of its current restrictions. Up to now, loop bounds and array subscripts in the modelled codes must be expressions linear in both the variables and the parameters. We lift this restriction and allow certain polynomial expressions instead of linear ones. With our extensions, we are able to handle more programs in all phases of the parallelisation process (dependence analysis, transformation of the program model, code generation). We extend Banerjee's classical dependence analysis to handle one non-linear parameter p, i.e., we are able to determine precisely the solutions of the system of conflict equalities for input programs with non-linear array accesses like A[p*i] in dependence of the residue class of p. We make contributions to three transformations desirable in automatic parallelisation. First, we show that using a generalised Simplex algorithm, which we have developed, schedules with non-linear parameters like theta(i)=floor(i/n) can be computed. In addition, such schedules can be expressed easily as a quantifier elimination problem but this approach turns out to be computationally less efficient with the available implementation. As a second transformation, we study parametric tiling which is used to adapt a parallelised program to the number of available processors at run time. Third, we present a localisation technique to exploit scratchpad memories on architectures on which data caching has to be handled by software. We transform a given code such that it keeps values which are reused in successive iterations of a sequential loop in the scratchpad. An access to a value written in an earlier iteration is served from the scratchpad to accelerate the access. In general, this transformation introduces non-linear loop bounds in the transformed model. Finally, we present an algorithm for generating code for arbitrary semi-algebraic iteration sets, i.e., for iteration sets described by polynomial inequalities in the variables and parameters. This is a vast generalisation of existing polyhedral code generation techniques. Although our algorithm is less efficient than polyhedral code generators, this paves the way for a code generator that can handle arbitrary parametric tilings and other transformations which introduce non-linear parameters (like non-linear schedules and the localisation we present) or even non-linear variables.}, subject = {Automatische Parallelisierung}, language = {en} } @phdthesis{Faber2007, author = {Faber, Peter}, title = {Code Optimization in the Polyhedron Model - Improving the Efficiency of Parallel Loop Nests}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-12512}, school = {Universit{\"a}t Passau}, year = {2007}, abstract = {A safe basis for automatic loop parallelization is the polyhedron model which represents the iteration domain of a loop nest as a polyhedron in \$\mathbb{Z}^n\$. However, turning the parallel loop program in the model to efficient code meets with several obstacles, due to which performance may deteriorate seriously -- especially on distributed memory architectures. We introduce a fine-grained model of the computation performed and show how this model can be applied to create efficient code.}, subject = {Polyeder}, language = {en} } @phdthesis{RehnSonigo2009, author = {Rehn-Sonigo, Veronika}, title = {Multi-criteria Mapping and Scheduling of Workflow Applications onto Heterogeneous Platforms}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-22249}, school = {Universit{\"a}t Passau}, year = {2009}, abstract = {The results summarized in this thesis deal with the mapping and scheduling of workflow applications on heterogeneous platforms. In this context, we focus on three different types of streaming applications: * Replica placement in tree networks * In this kind of application, clients are issuing requests to some servers and the question is where to place replicas in the network such that all requests can be processed. We discuss and compare several policies to place replicas in tree networks, subject to server capacity, Quality of Service (QoS) and bandwidth constraints. The client requests are known beforehand, while the number and location of the servers have to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. One major contribution of this work is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. We establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. * Pipeline workflow applications * We consider workflow applications that can be expressed as linear pipeline graphs. An example for this application type is digital image processing, where images are treated in steady-state mode. Several antagonist criteria should be optimized, such as throughput and latency (or a combination) as well as latency and reliability (i.e., the probability that the computation will be successful) of the application. While simple polynomial algorithms can be found for fully homogeneous platforms, the problem becomes NP-hard when tackling heterogeneous platforms. We present an integer linear programming formulation for this latter problem. Furthermore, we provide several efficient polynomial bi-criteria heuristics, whose relative performances are evaluated through extensive simulation. As a case-study, we provide simulations and MPI experimental results for the JPEG encoder application pipeline on a cluster of workstations. * Complex streaming applications * We consider the execution of applications structured as trees of operators, i.e., the application of one or several trees of operators in steady-state to multiple data objects that are continuously updated at various locations in a network. A first goal is to provide the user with a set of processors that should be bought or rented in order to ensure that the application achieves a minimum steady-state throughput, and with the objective of minimizing platform cost. We then extend our model to multiple applications: several concurrent applications are executed at the same time in a network, and one has to ensure that all applications can reach their application throughput. Another contribution of this work is to provide complexity results for different instances of the basic problem, as well as integer linear program formulations of various problem instances. The third contribution is the design of several polynomial-time heuristics, for both application models. One of the primary objectives of the heuristics for concurrent applications is to reuse intermediate results shared by multiple applications.}, language = {en} } @phdthesis{Kaebisch2013, author = {K{\"a}bisch, Sebastian}, title = {Resource Optimization of SOA-Technologies in Embedded Networks}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27338}, school = {Universit{\"a}t Passau}, year = {2013}, abstract = {Embedded networks are fundamental infrastructures of many different kinds of domains, such as home or industrial automation, the automotive industry, and future smart grids. Yet they can be very heterogeneous, containing wired and wireless nodes with different kinds of resources and service capabilities, such as sensing, acting, and processing. Driven by new opportunities and business models, embedded networks will play an ever more important role in the future, interconnecting more and more devices, even from other network domains. Realizing applications for such types of networks, however, is a highly challenging task, since various aspects have to be considered, including communication between a diverse assortment of resource-constrained nodes, such as microcontrollers, as well as flexible node infrastructure. Service Oriented Architecture (SOA) with Web services would perfectly meet these unique characteristics of embedded networks and ease the development of applications. Standardized Web services, however, are based on plain-text XML, which is not suitable for microcontroller-based devices with their very limited resources due to XML's verbosity, its memory and bandwidth usage, as well as its associated significant processing overhead. This thesis presents methods and strategies for realizing efficient XML-based Web service communication in embedded networks by means of binary XML using EXI format. We present a code generation approach to create optimized and dedicated service applications in resource-constrained embedded networks. In so doing, we demonstrate how EXI grammar can be optimally constructed and applied to the Web service and service requester context. In addition, so as to realize an optimized service interaction in embedded networks, we design and develop an optimized filter-enabled service data dissemination that takes into account the individual resource capabilities of the nodes and the connection quality within embedded networks. We show different approaches for efficiently evaluating binary XML data and applying it to resource constrained devices, such as microcontrollers. Furthermore, we will present the effectful placement of binary XML filters in embedded networks with the aim of reducing both, the computational load of constrained nodes and the network traffic. Various evaluation results of V2G applications prove the efficiency of our approach as compared to existing solutions and they also prove the seamless and successful applicability of SOA-based technologies in the microcontroller-based environment.}, subject = {Web Services}, language = {en} } @phdthesis{Seedorf2012, author = {Seedorf, Jan}, title = {Security for Decentralised Service Location - Exemplified with Real-Time Communication Session Establishment}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27147}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Decentralised Service Location, i.e. finding an application communication endpoint based on a Distributed Hash Table (DHT), is a fairly new concept. The precise security implications of this approach have not been studied in detail. More importantly, a detailed analysis regarding the applicability of existing security solutions to this concept has not been conducted. In many cases existing client-server approaches to security may not be feasible. In addition, to understand the necessity for such an analysis, it is key to acknowledge that Decentralised Service Location has some unique security requirements compared to other P2P applications such as filesharing or live streaming. This thesis concerns the security challenges for Decentralised Service Location. The goals of our work are on the one hand to precisely understand the security requirements and research challenges for Decentralised Service Location, and on the other hand to develop and evaluate corresponding security mechanisms. The thesis is organised as follows. First, fundamentals are explained and the scope of the thesis is defined. Decentralised Service Location is defined and P2PSIP is explained technically as a prototypical example. Then, a security analysis for P2PSIP is presented. Based on this security analysis, security requirements for Decentralised Service Location and the corresponding research challenges -- i.e. security concerns not suitably mitigated by existing solutions -- are derived. Second, several decentralised solutions are presented and evaluated to tackle the security challenges for Decentralised Service Location. We present decentralised algorithms to enable availability of the DHTs lookup service in the presence of adversary nodes. These algorithms are evaluated via simulation and compared to analytical bounds. Further, a cryptographic approach based on self-certifying identities is illustrated and discussed. This approach enables decentralised integrity protection of location-bindings. Finally, a decentralised approach to assess unknown identities is introduced. The approach is based on a Web-of-Trust model. It is evaluated via prototypical implementation. Finally, the thesis closes with a summary of the main contributions and a discussion of open issues.}, subject = {Peer-to-Peer-Netz}, language = {en} } @misc{Stadler2012, type = {Master Thesis}, author = {Stadler, Bernhard}, title = {Ein graphbasierter Formalismus zur Programmmanipulation}, doi = {10.15475/opus-198}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27128}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {In dieser Arbeit wird ein Formalismus zur implementierungs-, sprach- und repr{\"a}sentationsunabh{\"a}ngigen Beschreibung von Programmmanipulationen wie beispielsweise Merge, Featurekomposition und Interaktionsanalyse entwickelt. Dieser soll insbesondere der anwendungsnahen und wiederverwendbaren Definition von Programmanipulationen dienen. Programmmanipulationen werden auf repr{\"a}sentationsunabh{\"a}ngige, deklarative Art mit Mitteln der Kategorientheorie beschrieben. Auf Grundlage einer Analyse des Text-To-Model-Frameworks EMFText werden Graphvarianten aus der algebraischen Graphtransformationstheorie zur Programmrepr{\"a}sentation ausgew{\"a}hlt. Diese Graphvarianten werden anhand ihrer charakteristischen Merkmale in Graphfeatures aufgespalten. Auf Grundlage von Sketches, einer graphbasierten und kategorientheoretischen Art der algebraischen Spezifikation, wird eine Vorgehensweise f{\"u}r die formale Definition von Graphfeatures entwickelt. Diese Graphfeatures kann man auf flexible Weise zu sprach{\"u}bergreifenden graphbasierten Programmrepr{\"a}sentationen kombinieren. Als Anwendungen des Formalismus wurden der Merge und die Featurekomposition beschrieben.}, subject = {Informatik}, language = {de} } @phdthesis{Vilsmaier2014, author = {Vilsmaier, Christian}, title = {Contextualized Access To Distributed And Heterogeneous Multimedia Data Sources}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27374}, school = {Universit{\"a}t Passau}, year = {2014}, abstract = {Making multimedia data available online becomes less expensive and more convenient on a daily basis. This development promotes web phenomenons such as Facebook, Twitter, and Flickr. These phenomena and their increased acceptance in society in turn leads to a multiplication of the amount of available images online. This vast amount of, frequently public and therefore searchable, images already exceeds the zettabyte bound. Executing a similarity search on the magnitude of images that are publicly available in the Internet, and receiving a top quality result is a challenge that the scientific community has recently attempted to rise to. One approach to cope with this problem assumes the use of distributed heterogeneous Content Based Image Retrieval system (CBIRs). Following from this anticipation, the problems that emerge from a distributed query scenario must be dealt with. For example the involved CBIRs' usage of distinct metadata formats for describing their content, as well as their unequal technical and structural information. An addition issue is the individual metrics that are used by the CBIRs to calculate the similarity between pictures, as well as their specific way of being combined. Overall, receiving good results in this environment is a very labor intensive task which has been scientifically but not yet comprehensively explored. The problem primarily addressed in this work is the collection of pictures from CBIRs, that are similar to a given picture, as a response to a distributed multimedia query. The main contribution of this thesis is the construction of a network of Content Based Image Retrieval systems that are able to extract and exploit the information about an input image's semantic concept. This so called semantic CBIRn is mainly composed of CBIRs that are configured by the semantic CBIRn itself. Complementarily, there is a possibility that allows the integration of specialized external sources. The semantic CBIRn is able to collect and merge results of all of these attached CBIRs. In order to be able to integrate external sources that are willing to join the network, but are not willing to disclose their configuration, an algorithm was developed that approximates these configurations. By categorizing existing - as well as external - CBIRs and analyzing incoming queries, image queries are exclusively forwarded to the most suitable CBIRs. In this way, images that are not of any use for the user can be omitted beforehand. The hereafter returned images are rendered comparable in order to be able to merge them to one single result list of images, that are similar to the input image. The feasibility of the approach and the hereby obtained improvement of the search process is demonstrated by a prototypical implementation and its evaluation using classified images of ImageNet. Using this prototypical implementation an augmentation of the number of returned images that are of the same semantic concept as the input images is achieved by a factor of 4.75 with respect to a predefined non-semantic CBIRn.}, subject = {Multimedia}, language = {en} } @phdthesis{Peintner2014, author = {Peintner, Daniel}, title = {Efficient Exchange and Processing of Semi-structured Data in the Embedded Domain}, doi = {10.15475/UPA1113}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27610}, school = {Universit{\"a}t Passau}, year = {2014}, abstract = {The Internet is a global system of interconnected computers and computer networks where semi-structured data has been successfully applied for exchanging information. In nowadays Internet the huge range of actors, the large diversity of the associated device classes and domains, and the enormous amount of resource-restricted controllers in this system created new requirements and coined also a new term. Internet of Things (IoT), in this regard, refers to identifiable objects (things) and their virtual representations in an Internet-like structure. The fundamental question the thesis tries to answer is whether and how the same semi-structured data can be also applied to the IoT and the embedded domain in spite of resource-limited controllers. In order to discuss this question properties and requirements of embedded networks with regard to the IoT domain have been collected and evaluated. Thereafter the omnipresent semi-structured data exchange format in the Web, the Extensible Markup Language (XML), has been validated. The result was a list of missing requirements such as a compact representation, a representation that can be generated and consumed fast and also allows a small footprint implementation. To address the compiled requirements a binary representation of XML which nowadays is known as W3Cs Efficient XML Interchange (EXI) format has been accomplished which simultaneously optimizes performance and the utilization of computational resources and is designed to be compatible with XML. Moreover, in this work the format has been practically validated and tested. Addressing the needs of the embedded domain one result of this analyzes were optimizations to constrain runtime memory usage and to predict memory growth at runtime. A concept introduced in this thesis is LazyDOM which reduces memory requirements when processing and querying data. By means of a newly proposed code generation technique processing of EXI on ultra-constrained device classes has been enabled and resulting format modifications have been adopted by the W3C standardization. The research work described in this thesis on efficiently exchanging and processing semi-structured data on constrained embedded devices has not only triggered modifications in the W3C EXI format but even is already adopted in domain specific application standards and implementations. The above mentioned optimizations such as predictably limit the memory growth at runtime have been contributed, discussed and evaluated by the W3C experts and become a core part of the EXI specification. Even more significantly from the IoT perspective these optimizations provide the basis for the adoption of this technology in ISO and IEC standardization which is the first time for automotive and power industry to use IoT in the control plane. The implementation of EXI to conduct the evaluation as part of this thesis has become the de-facto open source reference implementation of EXI and became the basis of a number of other reference implementations such as the OpenV2G project that provides the reference implementation of the communication interface in ISO/IEC 15118. In summary the conducted research work has evaluated the options to adapt semi-structured data for the constrained embedded domain, proposed modifications and evaluated those under realistic conditions. This made it relevant for the technology as well as for application standardization despite the short period of this work. As such the research can now be taken as a basis for further challenges in the IoT field namely adopting concepts of the Semantic Web and adapting those to stimulate the quickly expanding eco-system of embedded devices.}, subject = {Mikrocontroller}, language = {en} }