WirelessHART is one of the latest communication standards that have enhanced functionality and robustness. The standard is ideal for applications in control and automation industry. In this work we present an implementation the TDMA state machine of the WirelessHART communication protocol on TinyOS operating system using the nesC language for the Telobs motes. The development was carried out using software reuse principle and involved comparing the state diagram description of the TDMA presented in WirelessHART with that of the time synchronized frequency hopping implementation that was already available for reuse. The work highlights the differences between the TSCH code and the WirelessHART specifications and builds upon the TSCH code to arrive at the WirelessHART TDMA state machine implementation.

Automated software testing techniques have become increasingly popular in recent years, with fuzzing being one of the most prevalent approaches. However, fuzzing Finite State Machines (FSMs) poses a significant challenge due to state and input dependency, resulting in exponential exploration time required to unlock the Finite State Machine. To address this issue, we present a novel approach in this research paper by introducing FINITEFUZZ, a Grey Box Fuzzer explicitly designed to fuzz Finite State Machines. Unlike the Blackbox fuzzers, FINITEFUZZ employs a mutational technique that utilizes feedback to steer the fuzzing process. FINITEFUZZ takes a random set of states and compares them with the desired FSM and records the states that increase the coverage of the Finite State Machine. The next seed incorporates the feedback received from all the previous seed inputs. This avoids exploring the same path multiple times and results in linear performance for all the types of Finite State machines possible. Our findings reveal that the use of FINITEFUZZ significantly reduces the exploration time required to uncover each state of the machine, making it a promising solution for generating Finite State Machines. We tested our FINITEFUZZ on 4 different types of Finite State Machines with each scenario resulting in at least 5X performance improvement in FSM generation. The potential applications of FSMs are vast, and our research suggests that the proposed approach can be used to generate any type of Finite State Machine. / Master of Science / Fuzzing, also known as Fuzz testing is a technique used to test software for security vulner- abilities, errors, and unexpected behavior. It involves generating random or semi-random input to a software application such as an operating system, or network service to test how it responds. Once input is generated, it is sent to the target application, which may crash, hang or produce unexpected results in response to the input. The results are then analyzed to identify potential vulnerabilities such as buffer overflows, input validation errors, and re- source leaks. Fuzzing is also used to test software that is difficult to test through other means, such as closed-source software or embedded systems. We generated a Fuzzer,FINITEFUZZ for Finite State Machine that unlocks the FSM starting from the random input and exploring only those seeds that increases the test coverage

State machine replication (SMR) is one of the most widely studied and used methodology for building highly available distributed applications and services. SMR replicates a service across a set of computing hosts, and executes client operations on the replicas in an agreed- upon total order, ensuring linearizability of the replicated shared state. The problem of determining a total order reduces to one of computing consensus. State-of-the-art consensus protocols are inadequate for newer classes of applications such as Blockchains and for geographically distributed infrastructures. The widely used Crash Fault Tolerance (CFT) fault model of consensus protocols is prone to malicious and adversarial behaviors as well as non-crash faults such as software bugs. The Byzantine fault-tolerance (BFT) model and its trust-based variant, the hybrid model, permit stronger failure adversaries. However, state-of-the-art Byzantine and hybrid consensus protocols have performance limitations in geographically distributed environments: they designate a primary replica for proposing total-orders, which becomes a bottleneck and yields sub-optimal latencies for faraway clients. Additionally, they do not scale to hundreds of replicas and provide consistent performance as the system size grows. To overcome these limitations and develop highly scalable SMR solutions, this dissertation presents two leaderless consensus protocols, namely ezBFT and Dester, for the Byzantine and hybrid models, respectively. These protocols enable every replica to receive and order client commands. Additionally, they exchange command dependencies to collectively order commands without relying on a primary. Our experimental evaluations in a 7-node geographically distributed setup reveals that ezBFT improves client-side latency by as much as 40% over state-of-the-art BFT protocols including PBFT, FaB, and Zyzzyva. Dester, for the hybrid model, reduces latency by as much as 30% over ezBFT. Next, the dissertation presents a new paradigm called DQBFT for designing consensus protocols that can scale to hundreds of nodes in geographically distributed environments. Since leaderless protocols exchange command dependencies, they do not scale to hundreds of nodes. DQBFT overcomes this scalability limitation by decentralizing only the heavy task of replicating commands and centralizing the process of ordering the commands. While DQBFT can be used to enhance existing primary-based protocols, Destiny is a hybrid instantiation of the DQBFT paradigm using linear communication for better scalability than naive instantiations. Experimental evaluations in a 193-node geographically distributed setup reveal that Destiny achieves ≈ 3× better throughput and ≈50% better latency than state-of-the-art BFT protocols including Hotstuff, SBFT, and Hybster. Lastly, the dissertation presents two techniques for designing and implementing BFT protocols with reduced development costs. The dissertation presents Bumblebee, a methodology for manually transforming CFT protocols to tolerate Byzantine faults using trusted execution environments that are increasingly available in commodity hardware. Bumblebee is based on the observation that CFT protocols are incapable of tolerating non-malicous non-crash faults, but they are nevertheless deployed in many production systems. Bumblebee provides a Generic Algorithm that can represent protocols in both CFT and hybrid fault models, thus allowing easy construction of hybrid protocols using CFT protocols as baselines. The dissertation constructs hybrid instantiations of CFT protocols including Paxos, Raft, and M2Paxos. Experimental evaluations of the hybrid variants reveal that they perform at par with native hybrid protocols, but incur a 30% overhead over their CFT counterparts. Hybrid protocols rely on the integrity of trusted execution environments, which are increasingly subject to security exploits. To withstand exploits, the dissertation presents DuoBFT, a protocol that exposes both the BFT and hybrid fault models within a single consensus protocol. This enables consensus under both fault models within the same protocol and without additional redundancy, allowing DuoBFT to achieve the performance of hybrid protocols and the security of BFT protocols. Experimental evaluations reveal that DuoBFT achieves the best of both hybrid and BFT fault models with less than 10% overhead. / Doctor of Philosophy / Computers are ubiquitous; they perform some of the most complex and safety-critical tasks such as controlling aircraft, managing the financial markets, and maintaining sensitive medical records. The undeniable fact is that computers are faulty. They are prone to crash and can behave arbitrarily. Even the most robust computers such as those that are sent to the outer space eventually fail. External phenomenon such as power outages and network disruptions affect their operation. To make computing systems reliable, researchers and practitioners have long focussed on interconnecting many individual computers and programming them to effectively be duplicates of one another. This way when one computer fails in a system, the rest of the computers still ensure that the system as a whole is operational. Duplication requires that multiple computers effectively perform the same task. In order for multiple computers to perform the same task together, they should first agree on the task. More generally, since computing systems perform multiple tasks, they should agree on the sequence of tasks that they will individually perform and follow the agreement. This is what is known as the State Machine Replication technique. State Machine Replication (SMR) is a powerful technique that is applicable to numerous computing applications. Blockchain systems, the technology behind the cryptocurrencies such as Bitcoin and Ethereum, uses the SMR technique. In the context of Blockchain, the added challenge in that some of the computers involved in SMR can be programmed by adversarial parties and could act in a way to jeopardize the integrity of the whole system. For Bitcoin and Ethereum, this could mean embezzlement of hundreds or even millions of dollars worth of cryptocurrencies. Certain SMR systems are capable of tolerating such intrusions and ensure system integrity. Such systems are deemed to be Byzantine tolerant. This dissertation presents designs, techniques, and implementations of Byzantine State Machine Replication systems. The problems addressed in this dissertation are those that plague existing Byzantine SMR systems making them suboptimal for newer applications such as Blockchains. First, when computers that participate in SMR are spread around the world, their performance is dependent on the communication latencies between any two pair of computers. Second, the number of computers required is proportional the number of adversarial computers that need to be tolerated. Consequently, certain SMR systems for Blockchains require hundreds of computers to tolerate heavy adversarial behavior. Many existing SMR technique perform poorly under these scenarios. The techniques presented in this dissertation address various permutations of these challenges.

This is a study taking an information theoretic approach toward quantum contextuality. The approach is that of using the memory complexity of finite-state machines to quantify quantum contextuality. These machines simulate the outcome behaviour of sequential measurements on systems of quantum bits as predicted by quantum mechanics. Of interest is the question of whether or not classical representations by finite-state machines are able to effectively represent the state-independent contextual outcome behaviour. Here we consider spatial efficiency, rather than temporal efficiency as considered by D. Gottesman (1999), for the particular measurement dynamics in systems of quantum bits. Extensions of cases found in the adjacent study of Kleinmann et al. (2010) are established by which upper bounds on memory complexity for particular scenarios are found. Furthermore, an optimal machine structure for simulating any n-partite system of quantum bits is found, by which a lower bound for the memory complexity is found for each n in the natural numbers. Within this finite-state machine approach questions of foundational concerns on quantum mechanics were sought to be addressed. Alas, nothing of novel thought on such concerns is here reported on.

This paper proposes new approaches to improve the coding performance of intra block coding in H.264/AVC via finite state machine and residual prediction. Grounding on high correlation between neighboring blocks, finite state machine is employed both at encoder and decoder to reduce the number of bits required for encoding to enhance coding performance. Two extra intra prediction modes are created in our proposed method. Through these two modes, the number of bits required to denote the current block is greatly reduced and low bit rate can be achieved. According to spatial correlation, intra-coded residual prediction reduces residual block by neighboring residual block. In this paper, we combine finite state machine with intra-coded residual prediction to achieve better coding performance. Experimental results show that the proposed method can greatly improve coding efficiency of intra macroblock coding in H.264/AVC.

Software needs to be adequately tested in order to increase the confidence that the system being developed is reliable. However, testing is a complicated and expensive process. Formal specification based models such as finite state machines have been widely used in system modelling and testing. In this PhD thesis, we primarily investigate fault detection and identification when testing from finite state machines. The research in this thesis is mainly comprised of three topics - construction of multiple Unique Input/Output (UIO) sequences using Metaheuristic Optimisation Techniques (MOTs), the improved fault coverage by using robust Unique Input/Output Circuit (UIOC) sequences, and fault diagnosis when testing from finite state machines. In the studies of the construction of UIOs, a model is proposed where a fitness function is defined to guide the search for input sequences that are potentially UIOs. In the studies of the improved fault coverage, a new type of UIOCs is defined. Based upon the Rural Chinese Postman Algorithm (RCPA), a new approach is proposed for the construction of more robust test sequences. In the studies of fault diagnosis, heuristics are defined that attempt to lead to failures being observed in some shorter test sequences, which helps to reduce the cost of fault isolation and identification. The proposed approaches and techniques were evaluated with regard to a set of case studies, which provides experimental evidence for their efficacy.

Telecom today has become an essence of life. Everywhere we see people using their smart phones for calling, checking email or accessing internet. To handle all these kinds of services without any intrusion is a very challenging task. This study deals with software testing which helps to ensure the quality of service to the end user. Software testing is an essential part in the software development process. Software development for telecom domain might not look as safety critical as of an airplane or nuclear reactor but it is arguably more complex. The main focus of this study is to provide automation to the unit testing of different types of radio connections that can be assigned to the end user based on the requested service and capacity of the 3G network. This research is sponsored by Ericsson to improve the testing of User Equipment Radio Connection Handling system that controls multiple possible radio connection configurations. This research attempts to identify and test all possible transitions between radio connection states. This will improve the existing manual state testing system, where changes in connection states cause dramatic impacts on test fixtures. As a solution, an automatic test case executor is proposed that generates possible transitions, which are later executed and verified automatically.

abstract: Laboratory automation systems have seen a lot of technological advances in recent times. As a result, the software that is written for them are becoming increasingly sophisticated. Existing software architectures and standards are targeted to a wider domain of software development and need to be customized in order to use them for developing software for laboratory automation systems. This thesis proposes an architecture that is based on existing software architectural paradigms and is specifically tailored to developing software for a laboratory automation system. The architecture is based on fairly autonomous software components that can be distributed across multiple computers. The components in the architecture make use of asynchronous communication methodologies that are facilitated by passing messages between one another. The architecture can be used to develop software that is distributed, responsive and thread-safe. The thesis also proposes a framework that has been developed to implement the ideas proposed by the architecture. The framework is used to develop software that is scalable, distributed, responsive and thread-safe. The framework currently has components to control very commonly used laboratory automation devices such as mechanical stages, cameras, and also to do common laboratory automation functionalities such as imaging. / Dissertation/Thesis / Thesis Presentation / M.S. Computer Science 2012

This thesis describes extensions to state machines in the Umple model-oriented programming language to offer queued state machines (QSM), pooled state machines (PSM) and handing of the arrival of unexpected events. These features allow for modeling the behavior of a system or protocol in a more accurate way in Umple because they enable detecting and fixing common design errors such as unspecified receptions. In addition, they simplify the communication between communicating state machines by allowing for asynchronous calls of events and passing of messages between state machines. Also, a pooled state machine (PSM) has been developed to provide a different policy of handling events that avoid unspecified receptions. This mechanism has similar semantics as a queued state machine, but it differs in the way of detecting unspecified receptions because it helps handling these errors. Another mechanism has been designed to use the keyword ‘unspecified’ in whatever state of a state machine the user wants to detect these errors. In this thesis, the test-driven development (TDD) process has been followed to first modify the Umple syntax to add ‘queued,’ ‘pooled,’ and ‘unspecified’ keywords to Umple state machine’s grammar; and second, to make a change to the Umple semantics in order to implement these extensions in Umple. Then, additional modifications have been made to allow for Java code generation from those types of state machines. Finally, more test cases have been written to ensure that these models are syntactically and semantically correct. In order to show the usefulness and usability of these new features, an example is shown as a case study that is modeled using the queued state machine (QSM) besides other small tests cases.

This thesis presents Caesar, a novel multi-leader Generalized Consensus protocol for geographically replicated systems. Caesar is able to achieve near-perfect availability, provide high performance - low latency and high throughput compared to the existing state-of-the- art, and tolerate replica failures. Recently, a number of state-of-the-art consensus protocols that implement the Generalized Consensus definition have been proposed. However, the major limitation of these existing approaches is the significant performance degradation when application workload produces conflicting requests. Caesar's main goal is to overcome this limitation by changing the way a fast decision is taken: its ordering protocol does not reject a fast decision for a client request if a quorum of nodes reply with different dependency sets for that request. It only switches to a slow decision if there is no chance to agree on the proposed order for that request. Caesar is able to achieve this using a combination of wait condition and logical time stamping. The effectiveness of Caesar is demonstrated through an evaluation study performed on Amazon's EC2 infrastructure using 5 geo-replicated sites. Caesar outperforms other multi-leader (e.g., EPaxos) competitors by as much as 1.7x in presence of 30% conflicting requests, and single-leader (e.g., Multi-Paxos) by as much as 3.5x. The protocol is also resistant to heavy client loads unlike existing protocols. / Master of Science