Tsang Wing Yee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 90-93). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Preliminaries --- p.4 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.4 / Chapter 2.2 --- Dataflow Networks --- p.5 / Chapter 2.3 --- The Lucid Programming Language --- p.9 / Chapter 2.3.1 --- Daton Domain --- p.10 / Chapter 2.3.2 --- Constants --- p.10 / Chapter 2.3.3 --- Variables --- p.10 / Chapter 2.3.4 --- Dataflow Operators --- p.11 / Chapter 2.3.5 --- Functions --- p.16 / Chapter 2.3.6 --- Expression and Statement --- p.17 / Chapter 2.3.7 --- Examples --- p.17 / Chapter 2.3.8 --- Implementation --- p.19 / Chapter 3 --- Extended Dataflow Network --- p.25 / Chapter 3.1 --- Assertion Arcs --- p.25 / Chapter 3.2 --- Selection Operators --- p.27 / Chapter 3.2.1 --- The Discrete Choice Operator --- p.27 / Chapter 3.2.2 --- The Discrete Committed Choice Operator --- p.29 / Chapter 3.2.3 --- The Range Choice Operators --- p.29 / Chapter 3.2.4 --- The Range Committed Choice Operators --- p.32 / Chapter 3.3 --- Examples --- p.33 / Chapter 3.4 --- E-Lucid --- p.39 / Chapter 3.4.1 --- Modified Four Cockroaches Problem --- p.42 / Chapter 3.4.2 --- Traffic Light Problem --- p.45 / Chapter 3.4.3 --- Old Maid Problem --- p.48 / Chapter 4 --- Implementation of E-Lucid --- p.54 / Chapter 4.1 --- Overview --- p.54 / Chapter 4.2 --- Definition of Terms --- p.56 / Chapter 4.3 --- Function ELUCIDinterpreter --- p.57 / Chapter 4.4 --- Function Edemand --- p.58 / Chapter 4.5 --- Function transf ormD --- p.59 / Chapter 4.5.1 --- Labelling Datastreams of Selection Operators --- p.59 / Chapter 4.5.2 --- Removing Committed Choice Operators --- p.62 / Chapter 4.5.3 --- "Removing asa, wvr, and upon" --- p.62 / Chapter 4.5.4 --- Labelling Output Datastreams of if-then-else-fi --- p.63 / Chapter 4.5.5 --- Transforming Statements to Daton Statements --- p.63 / Chapter 4.5.6 --- Transforming Daton Expressions Recursively --- p.65 / Chapter 4.5.7 --- An Example --- p.65 / Chapter 4.6 --- "Functions constructCSP, f indC, and transf ormC" --- p.68 / Chapter 4.7 --- An Example --- p.75 / Chapter 4.8 --- Function backtrack --- p.77 / Chapter 5 --- Related Works --- p.83 / Chapter 6 --- Conclusion --- p.87

Current data flow testing criteria cannot be applied to test array elements for two reasons: 1. The criteria are defined in terms of graph theory which is insufficiently expressive to investigate array elements. 2. Identifying input data which test a specified array element is an unsolvable problem. We solve the first problem by redefining the criteria without graph theory. We address the second problem with the invention of the wp_du method, which is based on Dijkstra's weakest pre-condition formalism. This method accomplishes the following: Given a program, a def-use pair and a variable (which can be an array element), the method computes a logical expression which characterizes all the input data which test that def-use pair with respect to that variable. Further, for any data flow criterion, this method can be used to construct a logical expression which characterizes all test sets which satisfy that data flow criterion. Although the wp_du method cannot avoid unsolvability, it does confine the presence of unsolvability to the final step in constructing a test set.

The dataflow model of computation differs from the traditional control-flow model of computation in that it does not utilize a program counter to sequence instructions in a program. Instead, the execution of instructions is based solely on the availability of their operands. Thus, an instruction is executed in a dataflow computer when all of its operands are available. This asynchronous nature of the dataflow model of computation allows the exploitation of fine-grain parallelism inherent in programs. Although the dataflow model of computation exploits parallelism, the problem of optimally allocating a program to processors belongs to the class of NP-complete problems. Therefore, one of the major issues facing designers of dataflow multiprocessors is the proper allocation of programs to processors. The problem of program allocation lies in maximizing parallelism while minimizing interprocessor communication costs. The culmination of research in the area of program allocation has produced the proposed method called the Balanced Layered Allocation Scheme that utilizes heuristic rules to strike a balance between computation time and communication costs in dataflow multiprocessors. Specifically, the proposed allocation scheme utilizes Critical Path and Longest Directed Path heuristics when allocating instructions to processors. Simulation studies indicate that the proposed scheme is effective in reducing the overall execution time of a program by considering the effects of communication costs on computation times. / Graduation date: 1993

Thesis (M.S.)--Ohio University, June, 2000. / Title from PDF t.p.

Thesis (M.S.)--Rochester Institute of Technology, 2009. / Typescript. Includes bibliographical references (leaves 104-107).

Thesis. / Includes vita. Includes bibliographical references (leaves 136-146)

Thesis (Ph. D.)--Rutgers University, 2008. / "Graduate Program in Electrical and Computer Engineering." Includes bibliographical references (p. 136-143).

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.

Data Flow Tracking (DFT) is a technique broadly used in a variety of security applications such as attack detection, privacy leak detection, and policy enforcement. Although effective, DFT inherits the high overhead common to in-line monitors which subsequently hinders their adoption in production systems. Typically, the runtime overhead of DFT systems range from 3× to 100× when applied to pure binaries, and 1.5× to 3× when inserted during compilation. Many performance optimization approaches have been introduced to mitigate this problem by relaxing propagation policies under certain conditions but these typically introduce the issue of inaccurate taint tracking that leads to over-tainting or under-tainting. Despite acknowledgement of these performance / accuracy trade-offs, the DFT literature consistently fails to provide insights about their implications. A core reason, we believe, is the lack of established methodologies to understand accuracy. In this dissertation, we attempt to address both efficiency and accuracy issues. To this end, we begin with libdft, a DFT framework for COTS binaries running atop commodity OSes and we then introduce two major optimization approaches based on statically and dynamically analyzing program binaries. The first optimization approach extracts DFT tracking logics and abstracts them using TFA. We then apply classic compiler optimizations to eliminate redundant tracking logic and minimize interference with the target program. As a result, the optimization can achieve 2× speed-up over base-line performance measured for libdft. The second optimization approach decouples the tracking logic from execution to run them in parallel leveraging modern multi-core innovations. We apply his approach again applied to libdft where it can run four times as fast, while concurrently consuming fewer CPU cycles. We then present a generic methodology and tool for measuring the accuracy of arbitrary DFT systems in the context of real applications. With a prototype implementation for the Android framework – TaintMark, we have discovered that TaintDroid’s various performance optimizations lead to serious accuracy issues, and that certain optimizations should be removed to vastly improve accuracy at little performance cost. The TaintMark approach is inspired by blackbox differential testing principles to test for inaccuracies in DFTs, but it also addresses numerous practical challenges that arise when applying those principles to real, complex applications. We introduce the TaintMark methodology by using it to understand taint tracking accuracy trade-offs in TaintDroid, a well-known DFT system for Android. While the aforementioned works focus on the efficiency and accuracy issues of DFT systems that dynamically track data flow, we also explore another design choice that statically tracks information flow by analyzing and instrumenting the application source code. We apply this approach to the different problem of integer error detection in order to reduce the number of false alarmings.

Many modern computer systems are distributed over space. Well-known examples are the Internet of Things and IBM's TrueNorth for deep learning applications. At the Asynchronous Research Center (ARC) at Portland State University we build distributed hardware systems using self-timed computation and delay-insensitive communication. Where appropriate, self-timed hardware operations can reduce average and peak power, energy, latency, and electromagnetic interference. Alternatively, self-timed operations can increase throughput, tolerance to delay variations, scalability, and manufacturability. The design of complex hardware systems requires design automation and support for test, debug, and product characterization. This thesis focuses on design compilation and test support for dataflow applications. Both parts are necessary to go from self-timed circuits to large-scale hardware systems. As part of the research in design compilation, the ARCwelder compiler designed by Willem Mallon (previously with NXP and Philips Handshake Solutions) was extended. The key to testing distributed systems, including self-timed systems, is to identify the actions in the systems. In distributed systems there is no such thing as a global action. To test, debug, characterize, and even initialize distributed systems, it is necessary to control the local actions. The designs developed at the ARC separate the actions from the states ab initio. As part of the research in test and debug, a special circuit to control actions, called MrGO, was implemented. A scan and JTAG test interface was also implemented. The test implementations have been built into two silicon test experiments, called Weaver and Anvil, and were used successfully for testing, debug, and performance characterizations.