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

FriendlyReader and TeCST are text simplification tools developed at Linköping University, using an API service at the university called SAPIS. Both tools are web services that run in the browser for users. To improve the services an implementation of state-transition tracking was chosen as a way to both improve the website by enabling the user to undo actions, but also enable the client to cache information which lowers the amount of requests required to SAPIS. Two libraries, called MobX and Redux, where compared to find the one which worked best for FriendlyReader and TeCST. The main difference between MobX and Redux is the programming paradigms, MobX is object-oriented while Redux is functional. In the end MobX was chosen due to the object-oriented nature of the library which is more familiar for beginners while also requiring less code to achieve similar results. MobX lacks native support to keep track of previous state transitions which is required to be able to go back to a previous state. Using MobX a new library called GlobalStore was created to solve this problem. An implementation example for synonyms was produced as a proof of concept for FriendlyReader.

In large-scale model-based development, developers periodically need to combine collections of interrelated models. These models may capture different features of a system, describe alternative perspectives on a single feature, or express ways in which different features alter one another's structure or behaviour. We refer to the process of combining a set of interrelated models as "model fusion". A number of factors make model fusion complicated. Models may overlap, in that they refer to the same concepts, but these concepts may be presented differently in each model, and the models may contradict one another. Models may describe independent system components, but the components may interact, potentially causing undesirable side effects. Finally, models may cross-cut, modifying one another in ways that violate their syntactic or semantic properties. In this thesis, we study three instances of the fusion problem for "behavioural models", motivated by real-world applications. The first problem is combining "partial" models of a single feature with the goal of creating a more complete description of that feature. The second problem is maintenance of "variant" specifications of individual features. The goal here is to combine the variants while preserving their points of difference (i.e., variabilities). The third problem is analysis of interactions between models describing "different" features. Specifically, given a set of features, the goal is to construct a composition such that undesirable interactions are absent. We provide an automated tool-supported solution to each of these problems and evaluate our solutions. The main novelties of the techniques presented in this thesis are (1) preservation of semantics during the fusion process, and (2) applicability to large and evolving collections of models. These are made possible by explicit modelling of partiality, variability and regularity in behavioural models, and providing semantic-preserving notions for relating these models.

In large-scale model-based development, developers periodically need to combine collections of interrelated models. These models may capture different features of a system, describe alternative perspectives on a single feature, or express ways in which different features alter one another's structure or behaviour. We refer to the process of combining a set of interrelated models as "model fusion". A number of factors make model fusion complicated. Models may overlap, in that they refer to the same concepts, but these concepts may be presented differently in each model, and the models may contradict one another. Models may describe independent system components, but the components may interact, potentially causing undesirable side effects. Finally, models may cross-cut, modifying one another in ways that violate their syntactic or semantic properties. In this thesis, we study three instances of the fusion problem for "behavioural models", motivated by real-world applications. The first problem is combining "partial" models of a single feature with the goal of creating a more complete description of that feature. The second problem is maintenance of "variant" specifications of individual features. The goal here is to combine the variants while preserving their points of difference (i.e., variabilities). The third problem is analysis of interactions between models describing "different" features. Specifically, given a set of features, the goal is to construct a composition such that undesirable interactions are absent. We provide an automated tool-supported solution to each of these problems and evaluate our solutions. The main novelties of the techniques presented in this thesis are (1) preservation of semantics during the fusion process, and (2) applicability to large and evolving collections of models. These are made possible by explicit modelling of partiality, variability and regularity in behavioural models, and providing semantic-preserving notions for relating these models.

Embedded memories dominate area, power and cost of modern very large scale integrated circuits system on chips ( VLSI SoCs). Furthermore, due to process variations, it becomes challenging to design reliable energy efficient systems. Therefore, fault-tolerant designs will be area efficient, cost effective and have low power consumption. The idea of this project is to design embedded memories where reliability is intentionally compromised to increase storage density. Gain cell memories are smaller than SRAM and unlike DRAM they are logic compatible. In multilevel DRAM storage density is increased by storing two bits per cell without reducing feature size. This thesis targets multilevel read and write schemes that provide short access time, small area overhead and are highly reliable. First, timing analysis of reference design is performed for read and write operation. An analytical model of write bit line (WBL) is developed to have an estimate of write delay. Replica technique is designed to generate the delay and track variations of storage array. Design of replica technique is accomplished by designing replica column, read and write control circuits. A memory controller is designed to control the read and write operation in multilevel DRAM. A multilevel DRAM is with storage capacity of eight kilobits is designed in UMC 90 nm technology. Simulations are performed for testing and results are reported for energy and access time. Monte Carlo analysis is done for variation tolerance of replica technique. Finally, multilevel DRAM with replica technique is compared with reference design to check the improvement in access times.

Object-oriented analysis and design approach has become the mainstream of today¡¦s systems development technique. The Timing Diagram and State Machine Diagram from the Unified Modeling Language (UML) are becoming the major tools for modeling the platform independent model (PIM) of an embedded system. Once these two diagrams are constructed, the results can then be transformed into its platform specific model and template code based on the model driven architecture (MDA) approach. However, the detailed guideline for the transformation from Timing Diagram and State Machine Diagram to the template code is lacking. Therefore, this study presents a methodology which provides guidelines for the transformation from State Machine Diagram and Timing Diagram to template code for the embedded system. The research methodology is articulated using the design science research methodology. A usability evaluation with a real-world embedded system case is performed to demonstrate its applicability. The results indicated that with this proposed method, the system developer can effectively transform the PIM of an embedded system into its template code.

We present an Intellectual Property (IP) protection technique for sequential circuits driven by embedding a decomposed signature into a Finite State Machine (FSM) through the manipulation of the arbitrary state encoding of the unprotected FSM. This technique is composed of three steps: (a) transforming the signature into a watermark graph, (b) embedding watermark graphs into the original FSM's State Transition Graph (STG) and (c) generating models for verification and extraction. In the watermark construction process watermark graphs are generated from signatures. The proposed methods for watermark construction are: (1) BSD, (2) FSD, and (3) HSD. The HSD method is shown to be advantageous for all signatures while providing sparse watermark FSMs with complexity O(n^2). The embedding process is related to the sub-graph matching problem. Due to the computational complexity of the matching problem, attempts to reverse engineer or remove the constructed watermark from the protected FSM, with only finite resources and time, are shown to be infeasible. The proposed embedding solutions are: (1) Brute Force and (2) Greedy Heuristic. The greedy heuristic has a computational complexity of O(n log n), where n is the number of states in the watermark graph. The greedy heuristic showed improvements for three of the six encoding schemes used in experimental results. Model generation and verification utilizes design automation techniques for generating multiple representations of the original, watermark, and watermarked FSMs. Analysis of the security provided by this method shows that a variety of attacks on the watermark and system including: (1) data-mining hidden functionality, (2) preimage, (3) secondary preimage, and (4) collision, can be shown to be computationally infeasible. Experimental results for the ten largest IWLS 93 benchmarks that the proposed watermarking technique is a secure, yet flexible, technique for protecting sequential circuit based IP cores.

We present a method of mitigating theft of sequential circuit Intellectual Property hardware designs through means of watermarking. Hardware watermarking can be performed by selectively embedding a watermark in the state encoding of the Finite State Machine. This form of watermarking can be achieved by matching a directed graph representation of the watermark with a sub-graph in state transition graph representation of the FSM. We experiment with three approaches: a brute force method that provides a proof of concept, a greedy algorithm that provides excellent runtime with a drawback of sub-optimal results, and finally a simulated annealing method that provides near optimal solutions with runtimes that meet our performance goals. The simulated annealing approach when applied on a ten benchmarks chosen from IWLS 93 benchmark suite, provides watermarking results with edge overhead of less than 6% on average with runtimes not exceeding five minutes.

Experiences with computer systems indicate an inconvenient truth: computers fail and they fail in interesting ways. Although using redundancy to protect against fail-stop failures is common practice, non-fail-stop computer and network failures occur for a variety of reasons including power outage, disk or memory corruption, NIC malfunction, user error, operating system and application bugs or misconfiguration, and many others. The impact of these failures can be dramatic, ranging from service unavailability to stranding airplane passengers on the runway to companies closing. While high-stakes embedded systems have embraced Byzantine fault tolerant techniques, general purpose computing continues to rely on techniques that are fundamentally crash tolerant. In a general purpose environment, the current best practices response to non-fail-stop failures can charitably be described as pragmatic: identify a root cause and add checksums to prevent that error from happening again in the future. Pragmatic responses have proven effective for patching holes and protecting against faults once they have occurred; unfortunately the initial damage has already been done, and it is difficult to say if the patches made to address previous faults will protect against future failures. We posit that an end-to-end solution based on Byzantine fault tolerant (BFT) state machine replication is an efficient and deployable alternative to current ad hoc approaches favored in general purpose computing. The replicated state machine approach ensures that multiple copies of the same deterministic application execute requests in the same order and provides end-to-end assurance that independent transient failures will not lead to unavailability or incorrect responses. An efficient and effective end-to-end solution covers faults that have already been observed as well as failures that have not yet occurred, and it provides structural confidence that developers won't have to track down yet another failure caused by some unpredicted memory, disk, or network behavior. While the promise of end-to-end failure protection is intriguing, significant technical and practical challenges currently prevent adoption in general purpose computing environments. On the technical side, it is important that end-to-end solutions maintain the performance characteristics of deployed systems: if end-to-end solutions dramatically increase computing requirements, dramatically reduce throughput, or dramatically increase latency during normal operation then end-to-end techniques are a non-starter. On the practical side, it is important that end-to-end approaches be both comprehensible and easy to incorporate: if the cost of end-to-end solutions is rewriting an application or trusting intricate and arcane protocols, then end-to-end solutions will not be adopted. In this thesis we show that BFT state machine replication can and be used in deployed systems. Reaching this goal requires us to address both the technical and practical challenges previously mentioned. We revisiting disparate research results from the last decade and tweak, refine, and revise the core ideas to fit together into a coherent whole. Addressing the practical concerns requires us to simplify the process of incorporating BFT techniques into legacy applications. / text

Darbo tikslas – pagerinti UML kalbą naudojančius projektavimo procesus, papildant juos sekų ir būsenų diagramų derinimo galimybėmis, praplėsti UML specifikaciją, kad būtų įmanomas abipusis sekų diagramų ir būsenų mašinų transformavimas. Antrame darbo skyriuje pateikti keli literatūroje pasiūlyti sekų diagramų transformavimo į būsenų mašinas algoritmai ir transformacijų pavyzdžiai. Skyriaus gale pateikta šių algoritmų palyginimo lentelė pagal tam tikras savybes bei keleto CASE įrankių, kuriuose galėtų būti įgyvendinti algoritmai, apžvalga. Trečiame skyriuje pateikta abipusės sekų ir būsenų diagramų transformacijos metodika. Ketvirtame skyriuje pateiktas pagal trečio skyriaus metodiką atliktos sekų ir būsenų diagramų transformacijų realizacijos projektas praplečiant MagicDraw UML įrankį. Penktame skyriuje pateiktas sukurto įskiepio efektyvumo tyrimas bei transformacijų pavyzdžiai. Šeštame skyriuje pateiktos bendros darbo išvados. / In this master thesis the transformation from sequence diagrams to statemachines and vice versa is presented. The first section describes a research of four existing algorithms of generating state machines from sequence diagrams. For diagrams transformation plug-in for CASE tool MagicDraw is created according MDA standards. Transformation plug-in takes sequence (state) diagram model as input and generates state (sequence) diagrams according to transformation sules. Created plug-in requirements,functional specification and architecture described in Project section. The investigation section describes investigation of the developed plug-in. In this section were investigate the working efficiency of designer trying to reconcile model diagrams.