Search

Recognizing the importance of whole genome alignment (WGA), the National Institutes for Health maintains LASTZ, a sequential WGA application. As genomic data grows, there is a compelling need for scalable, high-performance WGA. Unfortunately, high-sensitivity, `gapped' alignment which uses dynamic programming (DP) is slow, whereas faster alignment with ungapped filtering is often less sensitive. We develop FastZ, a GPU-accelerated, gapped WGA software which matches gapped LASTZ in sensitivity. FastZ employs a novel inspector-executor scheme in which (a) the lightweight inspector elides DP traceback except in common, extremely short alignments, where the inspector performs limited, eager traceback to eliminate the executor, and (b) executor trimming avoids unnecessary work. Further, FastZ employs register-based cyclic-buffering to drastically reduce memory traffic, and groups DP problems by size for load balance. FastZ running on an RTX 3080 GPU and our multicore implementation of LASTZ achieve 111x and 20x speedups over the sequential LASTZ, respectively.

The rapidly growing size of deep neural network (DNN) models and datasets has given rise to a variety of distribution strategies such as data, horizontal, and pipeline parallelism. However, selecting the best set of strategies for a given model and hardware configuration is challenging because debugging and testing on clusters is expensive. In this work we propose DistIR, an IR for explicitly representing distributed DNN computation that can capture many popular distribution strategies. We build an analysis framework for DistIR programs, including a simulator and reference executor that can be used to automatically search for an optimal distribution strategy. Our unified global representation also eases development of new distribution strategies, as one can reuse the lowering to per-rank backend programs. Preliminary results using a grid search over a hybrid data/horizontal/pipeline-parallel space suggest DistIR and its simulator can aid automatic DNN distribution.

Mimic defense (MD) is a novel architecture which takes the dynamic and heterogeneous security of redundant executors, and prevents further attacks through multi-mode decision feedback mechanism. However, there is a lack of effective analysis and evaluation on the defense cost and risk of multi-mode decision output. In this paper, we proposed the idea of Bayesian decision-making with minimum risk combined with the failure probability of the executor and the output of multi-mode decision. After considering the impact of failed defense and defensive cost on strategy generation, the optimal cleaning strategy is designed to ensuring the validity of optimal strategy. Finally, simulation experiments confirm the effectiveness of the model.

The influence of AR instruction on intention sharing between task designer and task executor in AR manual assembly is studied. We propose a visual representation (SHARIdeas) to support intention sharing and evaluate the effectiveness of new instruction.

Dynamic software update (DSU) can patch programs without stopping them. The updating process includes replacing changed code, transforming stale objects with object transformers, and resuming the execution of the updated program. However, flawed object transformers currently hinder DSU from the wide application, since they may introduce the inconsistencies between the transformed objects with expected new ones, that are created by the new program executing from scratch with the same inputs. To detect such inconsistencies, our approach first utilizes fuzzing testing to explore test inputs, then executes them over the old and new versions of a program within our specially designed parallel executor. Any inconsistency and the corresponding test will be issued. The evaluation over default transformer in 50 updates (14 of them have the inconsistency problem) showed that our approach discovered inconsistency in 16 updates, with 5 false positives and 3 false negatives. We also optimized the seed selection strategy in fuzzing process and improved the efficiency by 25.0%.

Code reuse attacks have been the subject of a substantial amount of research during the past decade. This research largely resulted from early work on Return-Oriented Programming (ROP), which showed that the then newly proposed Non-Executable Memory (NX) defense could be bypassed. More recently, the research community has been simultaneously investigating new defenses that are believed to thwart code reuse attacks, such as Control Flow Integrity (CFI), and defense-aware techniques for attacking these defenses, such as Data-Oriented Programming (DOP). Unfortunately, the feasibility of defense-aware attacks are very dependent on the behaviors of the attacked program, which makes it difficult for defenders to understand how much protection a defense such as CFI may provide. To better understand this, researchers have introduced automated defense-aware code reuse attack systems. Unfortunately, the handful of existing systems implement a single fixed, defense-specific strategy that is complex and cannot be used to consider other defenses. In this paper, we propose a generic framework for automatically discovering defense-aware code reuse attacks in executables. Unlike existing work, which utilizes hard-coded strategies for specific defenses, our framework can produce attacks for multiple defenses by analyzing the runtime behavior of the defense. The high-level insight behind our framework is that code reuse attacks can be defined as a state reachability problem, and that defenses prevent some transitions between states. We implement our framework as a tool named Limbo, which employs an existing binary concolic executor to solve the reachability problem. We evaluate Limbo and show that it excels when there is little code available for reuse, making it complementary to existing techniques. We show that, in such scenarios, Limbo outperforms existing systems that automate ROP attacks, as well as systems that automate DOP attacks in the presence of fine-grained CFI, despite having no special knowledge about ROP or DOP attacks.

With the rapid development of cloud computing in recent years, how to improve the system's concurrency capabilities has become increasingly important. SW26010 is a heterogeneous many-core processor used to build the Sunway TaihuLight supercomputer. Since this processor can only run a single thread on CPE (computing processing element), its concurrency is limited. Coroutines are a lightweight user-mode thread that occupy less resources. Scheduling and switching can be completed in user mode for coroutines, which is more suitable for processing concurrent tasks. This paper designs and implements a coroutine scheduling system on the SW26010 processor which add the CPE concurrency and improve program performance. This system has three modules: scheduler, executor, coroutine tasks. The scheduler runs on the MPE (management processing element) of SW26010. The scheduler controls the executor on the CPE, the executors control the coroutine task queue. This paper also compares convolution calculations of different scales and creates coroutine of different numbers tasks for convolution calculations. The performance of programs using the coroutine scheduling system has been increased by 23 times compared to only using the CPE.

With the rapid development of information and communication technology (ICT), all services in various sectors of society have transformed in the form of digital services that utilize the internet, one of which is in the field of education. One type of service in the field of education that is highly developed now is E-Learning. E-learning itself has been widely known and accepted by Indonesian people, both academic institutions and business organizations. With this acceptance, it has created an opportunity to develop e-learning so that it can be accessed through m-learning devices. The Ministry of Education and Culture as the executor of government affairs in the field of education has developed a m-learning platform called "Rumah Belajar" to assist student learning in Indonesia. The combination of Unified Theory of Acceptance and Use of Technology (UTAUT) and Uses and Gratification Theory (UGT) is used to be tested by Partial Least Square-Structural Equation Modeling (PLS-SEM). Results show that there are seven accepted hypotheses from eleven tested hypotheses, with four factors having a significant effect on the adoption of "Rumah Belajar" mobile application by students. Then, the results are used for strategy development planning. This strategy was mapped with Strategy to Mission Matrix to see its compatibility with Information and Communication Technology Center as developer of the application.

File systems are too large to be bug free. Although handwritten test suites have been widely used to stress file systems, they can hardly keep up with the rapid increase in file system size and complexity, leading to new bugs being introduced and reported regularly. These bugs come in various flavors: simple buffer overflows to sophisticated semantic bugs. Although bug-specific checkers exist, they generally lack a way to explore file system states thoroughly. More importantly, no turnkey solution exists that unifies the checking effort of various aspects of a file system under one umbrella. In this paper, we highlight the potential of applying fuzzing to find not just memory errors but, in theory, any type of file system bugs with an extensible fuzzing framework: Hydra. Hydra provides building blocks for file system fuzzing, including input mutators, feedback engines, a libOS-based executor, and a bug reproducer with test case minimization. As a result, developers only need to focus on building the core logic for finding bugs of their own interests. We showcase the effectiveness of Hydra with four checkers that hunt crash inconsistency, POSIX violations, logic assertion failures, and memory errors. So far, Hydra has discovered 91 new bugs in Linux file systems, including one in a verified file system (FSCQ), as well as four POSIX violations.

Crowd network is a deep integration system, which includes information, consciousness and physics. Those system are characterized by large amount of data, openness, self-organization and ecologization. In terms of its components, the digital itself has taken on great changes. There have been heterogeneity changes in the way of interconnection, and the interconnection among digital-selves has been further deepened in depth and breadth. Modeling and simulation of crowd behavior and intelligence is widely used in many fields and disciplines. This paper proposes a general model of simulation members for digital-self in crowd networks, which is used to modelling the intelligent activities of digital-selves. The general model can be separated into eight parts. These eiht parts are pattern, executor, decider, decompositor, interator, affector, monitor and comparator.

The success and growing popularity of blockchain technology has lead to a significant increase in load on popular permissionless blockchains such as Ethereum. With the current design, these blockchain systems do not scale with additional nodes since every node executes every transaction. Further efforts are therefore necessary to develop scalable permissionless blockchain systems.In this paper, we provide an aggregated overview of the current research on the Ethereum blockchain towards solving the scalability challenge. We focus on the concept of sharding, which aims to break the restriction of every participant being required to execute every transaction and store the entire state. This concept however introduces new complexities in the form of stateless clients, which leads to a new challenge: how to guarantee that critical data is published and stays available for as long as it is relevant.We present an approach towards solving the data availability problem (DAP) that leverages synergy effects by reusing the validators from Casper. We then propose two distinct approaches for reliable collation proposal, state transition, and state verification in shard chains. One approach is based on verification by committees of Casper validators that execute transactions in proposed blocks using witness data provided by executors. The other approach relies on a proof of execution provided by the executor proposing the block and a challenge game, where other executors verify the proof. Both concepts rely on executors for long-term storage of shard chain state.

In this paper we present DtCraft, a distributed execution engine that enables a new powerful programming model to streamline cluster computing. Applications are described in a set of data-parallel streams, leaving difficult execution details and concurrency controls handled by our system kernel transparently. Compared with existing systems, DtCraft is unique in (1) an efficient stream-oriented programming paradigm using modern C++17, (2) an in-context resource controller and task executor based on Linux container technology, and (3) ease of development from prototyping machines to production cloud environments. These capabilities power industry applications and create new research directions in machine learning, stream processing, and distributed multimedia systems.

It is challenging to effectively check a regular property of a program. This paper presents RGSE, a regular property guided dynamic symbolic execution (DSE) engine, for finding a program path satisfying a regular property as soon as possible. The key idea is to evaluate the candidate branches based on the history and future information, and explore the branches along which the paths are more likely to satisfy the property in priority. We have applied RGSE to 16 real-world open source Java programs, totaling 270K lines of code. Compared with the state-of-the-art, RGSE achieves two orders of magnitude speedups for finding the first target path. RGSE can benefit many research topics of software testing and analysis, such as path-oriented test case generation, typestate bug finding, and performance tuning. The demo video is at: https://youtu.be/7zAhvRIdaUU, and RGSE can be accessed at: http://jrgse.github.io.

A One-time Program (OTP) is a program, proposed by Goldwasser et al., in which the number of executions is restricted to once. The OTP uses a Garbled Circuit (GC), a circuit which does not leak the information except the execution result, as a building block. However, we need to use a special hardware called One-time Memory (OTM) to permit access to only one of two labels necessary for the execution of the GC. When the OTM does not exist or it is expensive, the realistic realization of the OTP is difficult. Furthermore, the OTM needs to be transported to a program executor and needs the production cost. Instead of using OTMs, we propose a way to distribute inputs to multiple cloud storages by using Shamir's secret sharing. In addition, we apply the proposed method to electronic money. Existing electronic money schemes do not prevent double-spending itself, but detect it and identify the double-spender. Therefore, one can double-spend the same electronic money illegally in a short time. Then we can detect the double-spending and identify the double-spender after delivering a product, but the double-spender can abscond with it. To tackle such a problem, we construct an electronic money scheme which prevents double-spending itself based on the OTP that generates a digital signature during a transaction. Combining the proposed electronic money scheme with an existing electronic money scheme, we can also construct another electronic money scheme which can detect double-spending even if the security of the OTP is broken.

Short-lived tasks have a large impact on mobile computer's battery life. In executing such tasks, the whole system transitions in and out of the deep sleep mode. This suspend/resume procedure is controlled by the operating system (OS), which consumes a dominating portion of energy. Through characterizing the Linux kernel on a variety of modern system-on-chips (SoCs), we show that the OS suspend/resume mechanism is fundamentally slowed down by various IO devices, which frequently keep CPU waiting.To minimize energy consumption, we advocate offloading the OS suspend/resume to a miniature processor that waits more efficiently. To this end, we propose a new virtual executor that runs on a miniature core and directly executes the unmodified kernel binary of the main CPU. We construct the virtual executor centering on software-only, cross-ISA binary translation, an approach previously considered prohibitively expensive. Through novel designs and optimizations, we reduce the translation overhead by 5×. The preliminary benchmarks show promising energy efficiency.

We present the Java Bytecode Symbolic Executor (JBSE), a symbolic executor for Java programs that operates on complex heap inputs. JBSE implements both the novel Heap EXploration Logic (HEX), a symbolic execution approach to deal with heap inputs, and the main state-of-The-Art approaches that handle data structure constraints expressed as either executable programs (repOk methods) or declarative specifications. JBSE is the first symbolic executor specifically designed to deal with programs that operate on complex heap inputs, to experiment with the main state-of-The-Art approaches, and to combine different decision procedures to explore possible synergies among approaches for handling symbolic data structures.

Task migration happens when distributed data processing systems scale in real-time. To handle the task migration process more gracefully, we propose three task migration methods: (i) worker level migration, (ii) executor level migration, and (iii) executor level migration with reliable messaging. We implement our migration methods on Apache Storm. Our experiments show that, compared with Storm's original migration implementation, our methods significantly reduce the performance degradation and the number of task failures during each migration.

This paper presents an efficient collaboration approach for reusing and sharing freight train driving plans P using case-based reasoning (CBR). P is formed by a set of actions that can move a train from one end to the other in a railroad. Collaboration is established by sharing different train driving experiences in different stretches. Three agents are positioned at each end: Planner, Executor, and Memory. Planner is responsible for generating P. Executor tests/adjusts (if necessary)/executes the actions of P. Until the train reaches the end, P may undergo δ adjustments depending on environmental conditions. The modified plan P + δ is returned to the origin to be integrated into the local experience base, maintained by the Memory. The approach was evaluated according the fuel consumption, accuracy of the case recovery task, and efficiency of task adaptation and application of such cases. The expansion of the experiences reduced the efforts of both the Planner and the Executor. In addition, our approach allowed the reuse, with low effort, of the obtained experiences in similar scenarios.

This paper presents Kinesis, a security incident response and prevention system for wireless sensor networks, designed to keep the network functional despite anomalies or attacks and to recover from attacks without significant interruption. Due to the deployment of sensor networks in various critical infrastructures, the applications often impose stringent requirements on data reliability and service availability. Given the failure- and attack-prone nature of sensor networks, it is a pressing concern to enable the sensor networks provide continuous and unobtrusive services.Kinesis is quick and effective in response to incidents, distributed in nature, and dynamic in selecting response actions based on the context. It is lightweight in terms of response policy specification, and communication and energy overhead. A per-node single timer based distributed strategy to select the most effective response executor in a neighborhood makes the system simple and scalable, while achieving proper load distribution and redundant action optimization.We implement Kinesis in TinyOS and measure its performance for various application and network layer incidents. Extensive TOSSIM simulations and testbed experiments show that Kinesis successfully counteracts anomalies/attacks and behaves consistently under various attack scenarios and rates.

Symbolic execution calls for specialized address translation. Unlike a pointer on a traditional machine model, which corresponds to a single address, a symbolic pointer may represent multiple feasible addresses. A symbolic pointer dereference manipulates symbolic state, potentially submitting many theorem prover requests in the process. Hence, design and management of symbolic accesses critically affects symbolic executor performance, complexity, and completeness.We demonstrate a symbolic execution extension, the symMMU, which separates access dispatch mechanism from policy by servicing memory accesses with symbolically executed runtime software handlers. This runtime code concisely represents access policies including pointer concretization, address forking, and symbolic indexing. These policies are competitive with a baseline hard-coded memory policy. Furthermore, the symMMU cleanly supports handlers for profiling, heap analysis, and demand allocated symbolic buffers. In practice, the symMMU flags hardware-validated bugs for over a thousand Linux program binaries.

We present a novel method for Quantitative Information Flow analysis. We show how the problem of computing information leakage can be viewed as an extension of the Satisfiability Modulo Theories (SMT) problem. This view enables us to develop a framework for QIF analysis based on the framework DPLL(T) used in SMT solvers. We then show that the methodology of Symbolic Execution (SE) also fits our framework. Based on these ideas, we build two QIF analysis tools: the first one employs CBMC, a bounded model checker for ANSI C, and the second one is built on top of Symbolic PathFinder, a Symbolic Executor for Java. We use these tools to quantify leaks in industrial code such as C programs from the Linux kernel, a Java tax program from the European project HATS, and anonymity protocols.

The past decade has witnessed the popularity of push-based data management systems, in which the query executor passively receives data from either remote data sources (e.g., sensors) or I/O processes that scan database tables/files from local storage. Unlike traditional relational database management system (RDBMS) architectures that are mostly I/O-bound, push-based database systems often become heavily computation-bound since the data arrival rate could be very high. In this paper, we argue that modern multi-core hardware, especially Graphics Processing Units (GPU), provide the most cost-effective computing platform to catch up with the large amount of data streamed into a push-based database system. Based on that, we will open discussions on how to design and implement a query processing engine for such systems that run on GPUs.

In this demo, we prove that the flexibility supported by off-the-shelf IEEE 802.11 hardware can be significantly extended if we move the control of the MAC programming interface from the driver to the firmware, i.e. from the host CPU to the card CPU. To this purpose, we introduce the concept of MAC--Engine, that is an executor of Programmable Finite State Machines (PFSM) implemented at the firmware level: we show how the card itself can support different protocol logics thanks to PFSM bytecode representations that can be dynamically injected inside the card memory at run-time without incurring in down time issues or network disconnect events. We provide different PFSM examples in order to test the functional thoroughness of the programming interface provided by the MAC-Engine architecture. Finally, we introduce an experimental PFSM development framework, that can translate a graphical PFSM representation into an optimized bytecode.

In many emerging XML application contexts and distributed execution environments (like disconnected and cloud computing, collaborative editing and document versioning) the server that determines the updates to be performed on a document, by evaluating an XQuery Update expression, is not always the same that actually makes such updates -represented as Pending Update Lists (PULs)-effective. The process of generating the PUL is thus decoupled from that of making its effect persistent on the document. The PUL executor needs to manage several PULs, that, depending on the application context, are to be executed as sequential or parallel update requests, possibly relying on application-specific policies. This requires some capabilities of dynamic reasoning on updates. In the paper, we state the most relevant properties to reason on, develop the corresponding algorithms and present a PUL handling system, providing an experimental evaluation of this system.

This paper describes UUhistle, a highly interactive program visualization system for introductory programming courses. UUhistle's main novelty is its support for visual program simulation exercises, in which the student takes the role of the computer as executor of a program in order to learn about program dynamics and to demonstrate their understanding. The student needs to predict the steps involved in the execution of a given program and to directly manipulate the elements of a program visualization to show what happens next. Visual program simulation exercises aim to aid learning by promoting a high level of student engagement with visualizations. They are automatically assessable.

The concurrency utilities in the Java library supply a feature called the executor framework that initiates and controls the execution of threads. It provides many adjustable parameters and extensibility hooks to be useful across a wide range of contexts for specifically configuring a pool of threads to execute submitted runnables depending on the application's specific needs. The Real-Time Specification for Java (RTSJ) supports asynchronous event handling (AEH), where the mapping of handlers to server threads is performed by the real-time JVM. In the past we have criticized the RTSJ facility as it lacks user configurability. Two simple changes to the RTSJ model would allow the user to provide their own policy for mapping handlers to server threads using the executor framework. Although the executor framework is not RTSJ-aware it is very flexible. This paper therefore discusses the feasibility of using the framework to implement various AEH mapping models. We first identify the issues associated with adapting the executor framework to AEH in the RTSJ. Based on the findings, we propose a blueprint on how the framework can be incorporated with AEH in the RTSJ with real-time guarantees. By doing so, the programmer can be given comprehensive configurability over the pool of threads provided by the executor framework to execute asynchronous event handlers in the RTSJ with realtime guarantees.

iTuned is a tool that takes a SQL workload as input and recommends good settings for database configuration parameters such as buffer pool sizes, multi-programming level, and number of I/O daemons. iTuned also provides response-surface and sensitivity-analysis plots that help the end-user analyze the impact of each parameter. iTuned has the following novel features: (i) a technique called Adaptive Sampling that proactively brings in appropriate data through planned experiments to find high-impact parameters and high-performance parameter settings, (ii) an executor that supports on-line experiments in production database environments through a cycle-stealing paradigm that places minimal overhead on the production workload, and (iii) portability across different database systems. This demonstration will focus on the interesting use-case scenarios of iTuned, and show the effectiveness of recommended configuration settings on popular database benchmarks.

Making efficient use of modern multi-core and future many-core CPUs is a major challenge. We describe a new compiler-based platform, Prospect, that supports the parallelization of sequential applications. The underlying approach is a generalization of an existing approach to parallelize runtime checks. The basic idea is to generate two variants of the application: (1) a fast variant having bare bone functionality, and (2) a slow variant with extra functionality. The fast variant is executed sequentially. Its execution is divided into epochs.Each epoch is re-executed by an executor using the slow variant. The approach scales by running the executors on multiple cores in parallel to each other and to the fast variant. We have implemented the Prospect framework to evaluate this approach. Prospect allows custom plug-ins for generating the fast and slow variants. With the help of our novel StackLifter, a process can switch between the fast variant and the slow variant during runtime at arbitrary positions.

Remotely sensed data, in particular satellite imagery, play many important roles in environmental applications. In particular applications that study rapid changes in the environment require frequent access to these data. For continuous data products, users are often interested in formulating continuous queries that deliver results for each incoming image. In the presence of multiple continuous queries, there is clearly an opportunity to share common intermediate data and thus, increase the overall processing speed of the system.Based on the widely used GRASS, this paper describes a system that realizes multiple query processing using two major components. A query optimizer maintains the current set of active continuous queries. Queries are organized into a single processing plan designed to share intermediate results. For each new image from the stream, the optimizer generates an execution plan specific to the active queries. The query executor then rewrites this plan into a set of geospatial processing steps and executes the plan.We detail experiments using data from NOAA's GOES. Continuous queries are defined in a way similar to the OGC WMS query specification. Using predicted query patterns over the visible hemisphere of GOES, experimental results indicate that multiple-query optimized plans can improve performance significantly when compared to queries that are executed separately.