Deep packet inspection (DPI) is useful as a tool for analyzing internet traffic. Regular expressions (regexps) can be used to detect the network traffic patterns that the DPI is able to identify. These regexps can be represented as state-machines, and sometimes combining smaller state-machines into larger state-machines can result in more efficient processing. This thesis looks at how to decide which state-machines used in DPI-classes should be combined with which other state-machines in an efficient manner using genetic algorithms. The goal being to create as few resulting state-machines from the combination while still maintaining a upper limit on the size of the resulting state-machines. The problem is modelled as an assignment problem for which an emulated surrogate problem is used in order to make experimental evaluations. Several genetic algorithms are suggested in an attempt to explore a wide range of parameters. It is also evaluated if different genetic algorithms perform differently depending on if the state-machines represent DPI-classes used to parse UDP or TCP traffic. A 2-dimensional representation is used that allows for a better capture of the underlying assignment problem. Different approaches to fitness are explored and found to have different efficacy in different situations. Several genetic algorithm operators are suggested for different situations and a difference is found between what works for UDP and for TCP. / Deep packet inspection (DPI) ̈ar användbart som ett verktyg f ̈or att analysera internettrafik. Regular expressions (regexps) kan användas för att detektera trafik mönster somDPI:n kan identifiera. De här regexps kan representeras som state-machines, och ibland så kan kombinationen av mindre state-machines till större state-machines resultera i mer effektiv bearbetning. Den här tesen undersöker hur man kan bestämma vilka state-machines som används iDPI-klassen bör bli kombinerade på ett effektivt sätt med genetiska algoritmer. Målet är att skapa så fǻ resulterande state-machines från kombineringen på ett sådant sätt att storleken på alla resulterande state-machines håller sig under en övre gräns. Problemet är modellerat som ett assignment problem för vilket ett emulerat surrogatproblem används för att tillåta experiment att utföras. Ett flertal genetiska algoritmer är föreslagna i ett försök att undersöka en bred räckvidd av parametrar. Det är också undersökt om olika genetiska algoritmer har olika prestanda beroende på om state-machines representerar DPI-klasser använda för UDP eller TCP trafik. En 2-dimensionell representation som fångar det underliggande problemet på ett bras sätt är använd. Olika tillvägagångssätt för att representera fitness är undersökta och är upptäckta att ha olika effektivitet i olika situationer. Ett flertal genetiska algoritm operatorer är föreslagna för olika situationer och en skillnad är hittad mellan vad som fungerar för UDP och vad som fungerar för TCP.

Les travaux de cette thèse s'inscrivent dans la théorie des automates et des langages formels. ils peuvent se diviser en deux parties qui donnent également deux visions différentes de manipuler les langages dans la théorie des automates. La première partie s'intéresse à la notion de dérivation des expressions qui permet de faire passer le formalisme des quotients de langages au niveau des expressions rationnelles. en particulier cette thèse étudie les termes dérivés cassés d'une expression rationnelle. ces termes dérivés cassés permettent, sous certaines circonstances, et à l'aide d'autres opérations, une réversibilité de la transformation d'un automate en une expression rationnelle. Dans la seconde partie, la théorie des automates est utilisée pour traiter des problèmes sur les systèmes de numération. les systèmes de numération représentent des nombres par des mots. il est possible d'utiliser des automates et des transducteurs afin d'être capable de 'compter' sur un langage rationnel représentant les entiers. plus précisément ces automates sont étudiés pour le cas des systèmes de numération abstraits qui associent à chaque entier un mot d'un langage rationnel, ordonné par l'ordre radiciel. dans un tel système, la fonction qui permet de calculer le mot suivant est une fonction co-séquentielle par morceaux, c'est-à-dire qu'il suffit de lire deux fois le mot d'entrée de la droite vers la gauche pour qu'une machine calcule son image. / The works in this thesis lies in the automata and formal languages theory. in the first part, the notion of derivation of rational expressions is studied. more precisely the broken derived terms of a rational expressions. Theses broken derived terms allow, under certain circumstances, with some other operations on automata, to have the reversibility of the transformation of an automaton into a rational expression. In the second part, automata and tranducers allow to 'count' on a numeration system, where integers are represented by words on a rational language. more precisely, this part adress the problem of counting in an abstract numeration systems, which maps to any word of a rational language, ordored by radix order, the integer corresponding to the order of the word. in such a numeration system, the function which computes the successor of a word is a piecewise co-sequential function: it can be realised by a machine which reads the input two times to give the output.

A state machine model can turn a complex behavioural system into a more accessible graphical model, and can improve the way people work with system design by making it easier to communicate and understand the system. The clear structure of a state machine model enables automatic generation of well structured, and consequently readable, and maintainable code. There are many known implementations and even plenty of commercial software available for working with state machines, and the goal of this project is to compare and discuss some of these implementations in the context of Ericsson's demands for run time, memory usage, scalability, readability, and maintainability. More specifically, the project focuses on the state machine models specified in the UML (the unified modeling language [15]), utilizing UML's associated markup language, XMI, to go from graphical model to generated C code. The resulting C code is primarily a code skeleton which only provides the basic behaviour of transitioning between states given a specific event, it is expected that the developers manually implement additional features themselves. The examined implementations are: Nested Switch, Array of Structs, Function Pointers, Basic State Pattern, State-Table Pattern, and Hierarchical State Pattern. Additionally, the project investigates how multiple state machines can communicate and work together as interacting state machines. And finally, to showcase how a state machine implementation can be maintainable, we develop an iterative code editor that can edit already operating and manually modified state machine implementations. The implementations are tested on a case study example provided by Ericsson, aimed to represent a sort of typical state machine design when it comes to number of states and events. The implementations are further tested with randomly generated state machines, to examine their scalability properties. In our opinion the results favour the Array of Structs and Basic State Pattern implementations and the choice depends on the optimisation used and the priority between run time and memory.

Indiana University-Purdue University Indianapolis (IUPUI) / Testing and verification are essential to safe and consistent products. Simulation is a widely accepted method used for verification and testing of distributed components. Generally, one of the major hurdles in using simulation is the development of detailed and accurate models. Since there are time constraints on projects, fast and effective methods of simulation model creation emerge as essential for testing. This thesis proposes to solve these issues by presenting a method to automatically generate a simulation model and run a random walk simulation using that model. The method is automated so that a modeler spends as little time as possible creating a simulation model and the errors normally associated with manual modeling are eliminated. The simulation is automated to allow a human to focus attention on the device that should be tested. The communications transactions between two nodes on a network are recorded as a trace file. This trace file is used to automatically generate a finite state machine model. The model can be adjusted by a designer to add missing information and then simulated in real-time using a software-in-the-loop approach. The innovations in this thesis include adaptation of a synthesis method for use in simulation, introduction of a random simulation method, and introduction of a practical evaluation method for two finite state machines. Test results indicate that nodes can be adequately replaced by models generated automatically by these methods. In addition, model construction time is reduced when comparing to the from scratch model creation method.

<p dir="ltr">Practically, Byzantine faults are not assumed in cloud applications. Byzantine fault-tolerance adds significant cryptographic, communication, throughput, and latency overheads to applications, contributing to the resistance towards its widespread adoption. Existing Byzantine-fault tolerant protocols focus on optimal latency or optimal communication while ignoring the throughput and cryptographic overheads.</p><p dir="ltr">In this thesis, we explore pipelining for Byzantine fault-tolerant applications. Pipelining tasks is a common optimization in distributed systems that involves executing tasks in stages. The idea is that instead of executing a task in an iteration as an atomic unit, we split the execution into stages and execute all stages of <i>different</i> tasks per iteration. We observe significant performance benefits if executing later stages of a task helps other tasks in earlier stages, saving effort in each stage. The length of the pipeline, i.e., the number of stages, determines the latency of an individual task. However, if the pipeline improves the execution of every stage enough, then the latency improves.</p><p dir="ltr">We primarily explore three Byzantine Fault Tolerant (BFT) applications with pipelining: (i) unique chain-based State Machine Replication protocols: <i>Apollo</i>, <i>Artemis</i>, <i>Leto</i>, and <i>Zeus</i>, and (ii) energy-efficient State Machine Replication: <i>EESMR</i>. (iii) random beacon protocols: <i>GRandPiper</i>, <i>BRandPiper</i>, and <i>OptRand</i>. We design them with a pipeline-first approach to improve the throughput, cryptographic, and communication costs at every stage of the pipeline. With respect to latency, we show (i) pipelined SMR protocols where our pipeline stages have constant cryptographic and linear communication costs allowing our protocols to outperform state-of-the-art BFT-SMR protocols in throughput. (ii) pipelined SMR protocols with techniques to make each stage of the pipeline independent, thus achieving demonstrable energy efficiency while allowing an unbounded number of non-interactive parallel proposals. (iii) reduced latencies for reconfiguration-friendly random beacons by using two pipelines: an SMR pipeline to commit and a beacon pipeline to produce random numbers and decoupling the two pipelines thereby removing the impact of the high-latency SMR pipeline on the latency of the randomness output by the system. </p>

Present-day commonly used systems like Cassandra, Spanner, and CockroachDB require high availability and strict consistency guarantees. High availability is attained through redundancy. In the field of computing, redundancy is attained through state machine repli- cation. Protocols like Raft, Multi-Paxos, ZAB, or other variants of Paxos are commonly used to achieve state machine replication. These protocols choose one of the processes from multiple processes running on various machines in a distributed setting as the leader. The leader is responsible for client interactions, replicating client operations on all the followers, and maintaining a consistent view across the system. In these protocols, the leader is more loaded than other nodes or followers in the system, making the leader a significant scalabil- ity bottleneck for multi-datacenter and edge deployments. The overall commit throughput and latency are further exacerbated in majority agreement with the hardware and network heterogeneity. This work aims to reduce the load on the leader by using reduced dynamic latency-aware flexible quorums while maintaining strict correctness guarantees like linearizability. In this thesis, we implement dynamic reduced-size commit quorums to reduce the leader’s load and improve throughput and latency, called FDRaft. The commit quorums are computed based on an exponentially moving weighted average of the followers’ time to respond to the leader, accounting for the heterogeneity in hardware and network. The reduced commit quorum requires a bigger election quorum, but elections rarely happen, and a single leader can serve for significant durations. We evaluate this protocol using a key-value store built on FDRaft and Raft and compare multi-datacenter and edge deployments. The evaluation shows 2x improved throughput and around 55% improved latency over Raft during normal operations and 45% improvement over Raft with vanilla flexible-quorums under failure conditions. / M.S. / In our day-to-day life, we rely heavily on different internet applications, be it Instagram for sharing pictures, Amazon for our shopping, Doordaash for our food orders, Spotify for listening to music, or Uber for traveling. These applications share many commonalities, like the scale at which they operate, maintaining strict latency guarantees, high availability to serve the users, and using databases to maintain shared states. The data is replicated across multiple servers to provide fault tolerance against failures. The replication across multiple servers is achieved through state-machine replication. In state-machine replication, multiple servers start with the same initial state and perform operations in the same order to reach the same final state. This process of replication in computing is achieved through a consensus algorithm. Con- sensus means agreement, and consensus algorithms are used to reach an agreement for a particular value. Raft, Multi-Paxos, or any other variant of Paxos are the commonly used consensus algorithms to achieve agreement on a particular value in a distributed setting. In these algorithms, one of the servers is chosen as the leader responsible for client interactions, replicating and maintaining the same state across all the servers, even when faced with server and network failures. Every time the leader receives a client operation, it starts the consensus process by forwarding the client request to all the servers and committing the client request after receiving an agreement from the majority. As the leader does most of the work, it is more loaded than other servers and becomes a significant scalability bottleneck. The leader bottleneck becomes more evident in multi-datacenters and edge deployments. The hardware and network heterogeneity also severely affects the overall commit throughput and latency in majority agreement. In this thesis, we reduce the load on the leader by building a smaller-sized dynamic commit quorum with latency-aware server selection based on an exponentially weighted moving av- erage of the followers’ response time to the leader’s requests without compromising safety and liveness properties. Our design also provides a higher efficiency for throughput and commit latency. We evaluate this protocol against multiple workloads and failure conditions and find that it outperforms Raft by 2x in terms of throughput and around 55% in latency over Raft during normal operations. It also shows improvement in throughput and latency by 45% over Raft with vanilla flexible-quorums under failure conditions.

No description available.

No description available.

This paper will present a multistage localization approach for an autonomous industrial mobile manipulator (AIMM). This approach allows tasks with an operational scope outside the range of the robot's manipulator to be completed without having to recalibrate the position of the end-effector each time the robot's mobile base moves to another position. This is achieved by localizing the AIMM within its area of operation (AO) using adaptive Monte Carlo localization (AMCL), which relies on the fused odometry and sensor messages published by the robot, as well as a 2-D map of the AO, which is generated using an optimization-based smoothing simultaneous localization and mapping (SLAM) technique. The robot navigates to a predefined start location in the map incorporating obstacle avoidance through the use of a technique called trajectory rollout. Once there, the robot uses its RGB-D sensor to localize an augmented reality (AR) tag in the map frame. Once localized, the identity and the 3-D position and orientation, collectively known as pose, of the tag are used to generate a list of initial feature points and their locations based on a priori knowledge. After the end-effector moves to the approximate location of a feature point provided by the AR tag localization, the feature point's location, as well as the end-effector's pose are refined to within a user specified tolerance through the use of a control loop, which utilizes images from a calibrated machine vision camera and a laser pointer, simulating stereo vision, to localize the feature point in 3-D space using computer vision techniques and basic geometry. This approach was implemented on two different ROS enabled robots, the Clearpath Robotics' Husky and the Fetch Robotics' Fetch, in order to show the utility of the multistage localization approach in executing two tasks which are prevalent in both manufacturing and construction: drilling and sealant application. The proposed approach was able to achieve an average accuracy of ± 1 mm in these operations, verifying its efficacy for tasks which have a larger operational scope than that of the range of the AIMM's manipulator and its robustness to general applications in manufacturing. / Master of Science

Automatic test data generation helps testers to validate software against user requirements more easily. Test data can be generated from many sources; for example, experience of testers, source program, or software specification. Selecting a proper test data set is a decision making task. Testers have to decide what test data that they should use, and a heuristic technique is needed to solve this problem automatically. In this paper, we propose a framework for generating test data from software specifications. The selected specification is Unified Modeling Language (UML) state machine diagram. UML state machine diagram describes a system in term of state which can be changed when there is an action occurring in the system. The generated test data is a sequence of these actions. These sequences of action help testers to know how they should test the system. The quality of generated test data is measured by the number of transitions which is fired using the test data. The more transitions test data can fire, the better quality of test data is. The number of coverage transitions is also used as a feedback for a heuristic search for a better test set. Genetic algorithms (GAs) are selected for searching the best test data. Our experimental results show that the proposed GA-based approach can work well for generating test data for some types of UML state machine diagrams.