Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-08-31T18:01:45Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tese-tmp - Entrega Biblioteca.pdf: 5443368 bytes, checksum: 91e38ed8db35fc81cfcacf861c54bc96 (MD5) / Made available in DSpace on 2017-08-31T18:01:45Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tese-tmp - Entrega Biblioteca.pdf: 5443368 bytes, checksum: 91e38ed8db35fc81cfcacf861c54bc96 (MD5) Previous issue date: 2016-10-07 / As linguagens declarativas normalmente atuam no desenvolvimento de aplicações multimídia, pois suas características permitem suportar adequadamente a natureza assíncrona e descritiva dessas aplicações. Neste cenário, a robustez surge como um fator determinante para a qualidade dessas aplicações, dada a vasta quantidade de plataformas e dispositivos usuais, que, ocasionalmente, apresentam problemas de execução. Neste contexto, as especificações dessas linguagens são de grande importância para o processo de desenvolvimento, pois além de direcionar a codificação, definindo as restrições léxicas, sintáticas e semânticas, também formalizam como os conteúdos devem ser executados pelos interpretadores. Este trabalho tem por objetivo investigar a viabilidade de se aplicar análises estruturais e comportamentais orientadas a conformidade para o desenvolvimento de aplicações multimídia, a fim de eliminar a dependência de interpretadores para atestar sua corretude. Para tal, a linguagem NCL foi utilizada como alvo do estudo, devido à sua representatividade para o problema. / Declarative languages are typically used in the development of multimedia applications, as its features allow to properly support the asynchronous and descriptive nature of these applications. In such a scenario, robustness appears as a determining factor in the quality of these applications, given the vast amount of platforms and devices that occasionally have implementation problems. In this context, specifications of these languages are of great importance to the development process, as they impose lexical, syntactic and semantic restrictions, and also formalize how content must be interpreted. This work aims at investigating the feasibility of applying structural and behavioral analysis oriented to compliance to the development of multimedia applications in order to eliminate dependence on interpreters to prove its correctness. To this end, NCL was used as a target of study due to its problem representativeness.

O teste baseado em modelos tem como objetivo auxiliar a atividade de testes, gerando conjuntos de casos de teste a partir de modelos, como Máquinas de Estados Finitos (MEFs). Diversos métodos de geração de conjuntos de caso de teste têm sido propostos ao longo das últimas décadas, com algumas contribuições recentes. Dentre esses trabalhos, há os que geram seqüências de verificação que são conjuntos de caso de teste formados por uma única seqüência e que são capazes de detectar os defeitos de uma implementação cujo comportamento pode ser modelado a partir de uma MEF. Neste trabalho é proposto um algoritmo de geração de seqüências de verificação que tem a finalidade de gerar seqüências menores que as seqüências geradas pelos métodos existentes. O algoritmo, que é baseado na técnica de algoritmos genéticos e nas condições de suficiência para a completude de casos de teste, consiste basicamente em criar novas seqüências a partir de seqüências menores. Por meio de mutações, novas seqüências são geradas pelo algoritmo. As condições de suficiência são utilizadas para determinar quais seqüências geradas são seqüências de verificação. Também são apresentados neste trabalho os estudos experimentais realizados para determinar o comportamento do algoritmo diante de diferentes contextos / Model-based testing aims at aiding the testing activity, generating test cases from models such as Finite State Machines (FSM). Several test cases generation methods have been proposed along the last decades, with some recent contributions. Among these works, there are those that generate checking sequences, which are test cases formed by a single sequence and which are capable of detecting faults in an implementation whose behavior can be modeled as an FSM. This work proposes a checking sequences generation algorithm which aims at generating sequences smaller than the sequences generated by existing methods. The algorithm, which is based on the genetic algorithms technique and sufficient conditions for completeness of test cases, basically consists of creating new sequences from small sequences. Through mutations, new sequences are generated by the algorithm. The suffcient conditions are used to determine which sequences are checking sequences. Experimental studies are presented in this work to determine the behavior of the algorithm on different contexts

Developing real-time strategy game AI is a challenging task due to that an AI-player has to deal with many different decisions and actions in an ever changing complex game world. Humans have little problem when it comes to dealing with the complexity of the game genre while it is a difficult obstacle to overcome for the computer. Adapting to the opponents strategy is one of many things that players typically have to do during the course of a game in the real-time strategy genre. This report presents a finite-state machine based solution to the mentioned problem and implements it with the help of the existing Starcraft: Broodwar AI Opprimobot. The extension is experimentally compared to the original implementation of Opprimobot. The comparison shows that both manages to achieve approximately the same win ratio against the built-in AI of Starcraft: Broodwar, but the modified version provides away to model more complex strategies.

This work deals with the design and realization of an automated test software for the Honeywell superheat controller. The first part of the project includes brief description about embedded systems and heat pumps. Afterwards testing principles are covered in a short chapter, followed by a description of the Honeywell superheat controller. After these chapters actual software structure will be introduced to the reader- with a detailed description of the most interesting parts. At the end of the document there will be a summary what was achieved exactly, and what was the plan. After this summary, the reader can study almost all the Virtual Instruments created during the development of this project.

Traits are primitive units of code reuse that serve as building blocks of classes. In this research, we enhance reuse by extending the capabilities of traits; in particular, we add modeling abstractions to them. Traits have a variety of benefits, including facilitating reuse and separation of concerns. They have appeared in several programming languages, particularly derivatives of Smalltalk. However, there is still no support for traits that contain modeling abstractions, and no straightforward support for them in general-purpose programming languages. The latter is due to structural concerns that exist for them at runtime, especially traits that contain modeling abstractions. Model-driven technologies are making inroads into the development community, albeit slowly. Modeling abstractions such as state machines and associations provide new opportunities for reuse, and can be combined with inheritance for even greater reusability. However, issues with inheritance apply also when these new abstractions are inheritable units. This suggests that traits and models ought to be able to be synergistically combined. We perform a comprehensive analysis of using modeling elements in traits. We implement such traits in Umple, which is a model-oriented programming language that permits embedding of programming concepts into models. The contributions of the thesis are: a) Adding new elements including state machines and associations into traits, hence bringing more reusability, modularity, and applications to traits; b) Developing an algorithm that allows reusing, extending, and composing state machines through traits; c) Extending traits with required interfaces so dependencies at the semantic level become part of their usage, rather than simple syntactic capture; d) Adding template parameters with associations in traits, offering new applications for traits in which it is possible to define design patterns and to have a library of most-used functionality; e) The implementation of all the above concepts, including generating code in multiple general-purpose programming languages through automatic model transformation.

This master´s thesis thesis deals with the design of software for the control of a robotic cell, which consists of two KUKA robots and a belt conveyor. The robots will perform robotic operations similar to those in real industrial practice. At the beginning of the work will be the state of current knowledge. A key part will be the design of software for robotic cell control in the TwinCAT environment from Beckhoff. The robots and the conveyor will be controlled by a superior PLC, which will be commanded from the designed software using the HMI. The goal is to successfully implement the proposed software for robotic cell control and monitoring using a unique visualization, which will be designed specifically for the robotic cell and its associated manipulation operations.

This master’s thesis deals with analysis of state machines for embedded applications. The issue of finite-state machine is described theoretically. The document also contains a proposal for funding for modeling finite state machines in Matlab/Simulink. It is designed data representation of finite automaton. Over this data representation algorithm of minimization is applied. Finally, the algorithm is implemented to generate code in C language.

Fuzzing is a test method used to automatically generate test case inputs and to executea system under test (SUT) with those inputs. The method is traditionally used to discovercrash-inducing bugs in software. Fuzzing can generate thousands of inputs per secondand many implementations use smart techniques to reach deeply into the code. Fewfuzz testing implementations, however, have the ability to explore and retain informationof state in stateful applications. We develop an extension of the fuzzer American Fuzzy Lop (AFL), building on the workof the Ijon project, and utilize its fuzzing capabilities to discover states in SUT; inparticular, applications built as finite state machines. The extension successfullyharnesses AFL’s input generation to explore the SUT’s state space. We then implement functionality that allows for the SUT to return state information tothe fuzzer, including the state path and path length. Furthermore, functionality is addedthat allows the test operator to specify the expected number of states in the SUT, andGUI extensions that provide real-time information of state discovery during fuzzing. The state information retained after a completed fuzzing session is automaticallysummarized in a structured format. We further demonstrate that the summarizedinformation can be used to generate test cases for a test operator to verify the SUT.

Despite extensive research on Byzantine Fault Tolerant (BFT) systems, overheads associated with such solutions preclude widespread adoption. Past efforts such as the Cross Fault Tolerance (XFT) model address this problem by making a weaker assumption that a majority of processes are correct and communicate synchronously. Although XPaxos of Liu et al. (using the XFT model) achieves similar performance as Paxos, it does not scale with the number of faults. Also, its reliance on a single leader introduces considerable downtime in case of failures. This thesis presents Elpis, the first multi-leader XFT consensus protocol. By adopting the Generalized Consensus specification from the Crash Fault Tolerance model, we were able to devise a multi-leader protocol that exploits the commutativity property inherent in the commands ordered by the system. Elpis maps accessed objects to non-faulty processes during periods of synchrony. Subsequently, these processes order all commands which access these objects. Experimental evaluation confirms the effectiveness of this approach: Elpis achieves up to 2x speedup over XPaxos and up to 3.5x speedup over state-of-the-art Byzantine Fault-Tolerant Consensus Protocols. / Master of Science / Online services like Facebook, Twitter, Netflix and Spotify to cloud services like Google and Amazon serve millions of users which include individuals as well as organizations. They use many distributed technologies to deliver a rich experience. The distributed nature of these technologies has removed geographical barriers to accessing data, services, software, and hardware. An essential aspect of these technologies is the concept of the shared state. Distributed databases with multiple replicated data nodes are an example of this shared state. Maintaining replicated data nodes provides several advantages such as (1) availability so that in case one node goes down the data can still be accessed from other nodes, (2) quick response times, by placing data nodes closer to the user, the data can be obtained quickly, (3) scalability by enabling multiple users to access different nodes so that a single node does not cause bottlenecks. To maintain this shared state some mechanism is required to maintain consistency, that is the copies of these shared state must be identical on all the data nodes. This mechanism is called Consensus, and several such mechanisms exist in practice today which use the Crash Fault Tolerance (CFT). The CFT model implies that these mechanisms provide consistency in the presence of nodes crashing. While the state-of-the-art for security has moved from assuming a trusted environment inside a firewall to a perimeter-less and semi-trusted environment with every service living on the internet, only the application layer is required to be secured while the core is built just with an idea of crashes in mind. While there exists comprehensive research on secure Consensus mechanisms which utilize what is called the Byzantine Fault Tolerance (BFT) model, the extra costs required to implement these mechanisms and comparatively lower performance in a geographically distributed setting has impeded widespread adoption. A new model recently proposed tries to find a cross between these models that is achieving security while paying no extra costs called the Cross Fault Tolerance (XFT). This thesis presents Elpis, a consensus mechanism which uses precisely this model that will secure the shared state from its core without modifications to the existing setups while delivering high performance and lower response times. We perform a comprehensive evaluation on AWS and demonstrate that Elpis achieves 3.5x over the state-of-the-art while improving response times by as much as 50%.

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.