Search

A faulty situation occurred in Service Oriented Architecture (SOA) based systems can affect its functionality. It is challenging to guarantee the reliability of service utilization in a distributed, concurrent and dynamic composition of web services. This paper aims to present a fault detection approach of SOA using dependency analysis. Data and control dependencies are identified and a fault diagnosis approach based on these dependencies is proposed in this paper. The presented approach extends discrete state space techniques to simulate the concurrent and distributed behavior through Colored Petri Nets (CPNs) for the SOA-based systems in case of the faulty situation. Concrete translation from SOA based system to a CPN model is presented. Model-based technique is used and some heuristics are presented for dependency analysis and fault detection purpose. The experimental performance analysis shows the feasibility of our proposed approach.

Memory caches are being used aggressively in today's data analytics systems such as Spark, Tez, and Piccolo. The significant performance impact of caches and their limited sizes call for efficient cache management in data analytics clusters. However, prevalent data analytics systems employ rather simple cache management policies-notably Least Recently Used (LRU) and Least Frequently Used (LFU)-that are oblivious to the application semantics of data dependency, expressed as directed acyclic graphs (DAGs). Without this knowledge, cache management can, at best, be performed by "guessing" the future data access patterns based on history, which frequently results in inefficient, erroneous caching with a low hit rate and a long response time. Worse still, the lack of data dependency knowledge makes it impossible to retain the all-or-nothing cache property of cluster applications, in that a compute task cannot be sped up unless all the dependent data has been kept in the main memory. In this paper, we propose a novel cache replacement policy, named Least Reference Count (LRC), which exploits the application's data dependency information to optimize the cache management. LRC keeps track of the reference count of each data block, defined as the number of dependent child blocks that have not been computed yet, and always evicts the block with the smallest reference count. Furthermore, we incorporate the all-or-nothing requirement into LRC by coordinately managing the reference counts of all the input data blocks for the same computation. We demonstrate the efficacy of LRC through both empirical analysis and cluster deployments against popular benchmarking workloads. Our Spark implementation shows that, the proposed policies well address the all-or-nothing requirement and significantly improve the cache performance. Compared with LRU and a recently proposed caching policy called MEMTUNE, LRC improves the caching performance of typical workloads in production clusters by 22% and 284%, respectively.

Static malware detection approaches are time-consuming and cannot deal with code obfuscation techniques. Dynamic malware detection approaches, on the other hand, address these two challenges, however, suffer from behavioral ambiguity, such as the system calls obfuscation. In this paper, we introduce Markhor, a dynamic and behavior-based malware detection approach. Markhor uses system call data dependency and system call control dependency sequences to create a weighted list of malicious patterns. The list is then used to determine the malicious processes. Next, the similarity of a file system call sequences to a malicious pattern is extracted based on a fuzzy algorithm and the file nature is determined. The evaluation results reveal the efficiency of Markhor in terms of accuracy (0.982), precision (0.976), and F-measure (0.982).

Scientific computations with a wide range of applications in domains such as developing vaccines, forecasting the weather, predicting natural disasters, simulating aerodynamics of spacecraft, and exploring oil resources, create the main workloads of supercomputers. The key integration of such scientific computations is modeling physical phenomena that are done with the aid of partial differential equations (PDEs). Solving PDEs on supercomputers, even with those equipped with GPUs, consumes a large amount of power and yet is not as fast as desired. The main reason behind such slow processing is data dependency. The key challenge is that software techniques cannot resolve these dependencies, therefore, such applications cannot benefit from the parallelism provided by processors such as GPUs. Our key insight to address this challenge is that although we cannot resolve the dependencies, we can reduce their negative impacts by using hardware/software co-optimization. To this end, we propose breaking down the data-dependent operations into two groups of operations: a majority of parallelizable and the minority of data-dependent operations. We execute these two groups in the desired order: first, we put together all parallelizable operations and execute them all, subsequently; then, we switch to execute the small data-dependent part. As long as the data-dependent part is small, we can accelerate them by using fast hardware mechanisms. Besides, our proposed hardware mechanisms guarantee quickly switching between the two groups of operations. To follow the same order of execution, dictated by our software mechanism, and implemented in hardware, we also propose a new low-overhead compression format – sparsity is another attribute of PDEs that require compression. Furthermore, the core generic architecture of our proposed hardware allows the execution of other applications including sparse matrix-vector multiplication (SpMV) and graph algorithms. The key feature of the proposed hardware is partial reconfigurability, which on one hand, facilitates the execution of data-dependent computations, and on the other hand, allows executing broad application without changing the entire configuration. Our evaluations show that compared to GPUs, we achieve an average speedup of 15.6× for scientific computations while consuming 14× less energy.

To overcome the limitation of standalone edge cloud in terms of computing power and resource, a concept of distributed edge cloud has been introduced, where application tasks are distributed to multiple edge clouds for collaborative processing. To maximize the effectiveness of the distributed edge cloud, we formulate an optimization problem of task allocation to minimize the application completion time. To mitigate high complexity overhead in the formulated problem, we devise a low-complexity heuristic algorithm called dependency-aware task allocation (DATA) algorithm. Evaluation results demonstrate that DATA can reduce the application completion time up to by 15%–32% compared to conventional dependency-unaware task allocation schemes.

The state-of-the-art convolutional neural network (CNN) structures present growing irregularity in the sense of layer connections, which derives from the innovative manual designs and the recently proposed neural architecture searching approaches. Such irregular structures improve recognition accuracy, but also bring challenges for hardware deployment, especially on CNN accelerators with regular architectures: 1) the complicated data dependency makes it nontrivial to decide the data reuse strategy between layers and 2) since the execution order of each network is not unique, the choice of layer scheduling, memory allocating, and loop tiling strategies greatly impact the hardware performance. These challenges cannot be solved by the existing CNN schedulers, which mainly focuses on the dataflow of a single layer. In this work, we propose a comprehensive framework to analyze and solve the mapping of an arbitrarily connected CNN network to specific hardware accelerators. We propose: 1) a dynamic programming and node-clustering-based DAG partitioning approach to efficiently exploit interlayer data reuse and 2) a subgraph scheduling and on-chip memory allocating strategy to find the optimal execution order. With the modeling of CNN accelerators, we also propose a loop tiling approach for fused layers. An automated framework is established to generate binary machine codes from original CNN models produced by mainstream deep learning frameworks, which can process large-scale CNNs with more than 1000 layers in only a few minutes. Experiments based on state-of-the-art accelerators (e.g., NVDLA) show that our techniques greatly reduce the external data transfer of interlayer dependencies and bring significant performance improvement over existing approaches.

Machine learning over graphs has been emerging as powerful learning tools for graph data. However, it is challenging for industrial communities to leverage the techniques, such as graph neural networks (GNNs), and solve real-world problems at scale because of inherent data dependency in the graphs. As such, we cannot simply train a GNN with classic learning systems, for instance, parameter server that assumes data parallelism. Existing systems store the graph data in-memory for fast accesses either in a single machine or graph stores from remote. The major drawbacks are three-fold. First, they cannot scale because of the limitations on the volume of the memories, or the bandwidth between graph stores and workers. Second, they require extra development of graph stores without well exploiting mature infrastructures such as MapReduce that guarantee good system properties. Third, they focus on training but ignore optimizing the performance of inference over graphs, thus makes them an unintegrated system. In this paper, we design AGL, a scalable and integrated system, with fully-functional training and inference for GNNs. Our system design follows the message passing scheme underlying the computations of GNNs. We design to generate the K -hop neighborhood, an information-complete subgraph for each node, as well as do the inference simply by merging values from in-edge neighbors and propagating values to out-edge neighbors via MapReduce. In addition, the K -hop neighborhood contains information-complete subgraphs for each node, thus we simply do the training on parameter servers due to data independence. Our system AGL, implemented on mature infrastructures, can finish the training of a 2-layer GNN on a graph with billions of nodes and hundred billions of edges in 14 hours, and complete the inference in 1.2 hours.

Matrix Factorization (MF) based on Stochastic Gradient Descent (SGD) is a powerful machine learning technique to derive hidden features of objects from observations. In this article, we design a highly parallel architecture based on Field-Programmable Gate Array (FPGA) to accelerate the training process of the SGD-based MF algorithm. We identify the challenges for the acceleration and propose novel algorithmic optimizations to overcome them. By transforming the SGD-based MF algorithm into a bipartite graph processing problem, we propose a 3-level hierarchical partitioning scheme that enables conflict-minimizing scheduling and processing of edges to achieve significant speedup. First, we develop a fast heuristic graph partitioning approach to partition the bipartite graph into induced subgraphs; this enables to efficiently use the on-chip memory resources of FPGA for data reuse and completely hide the data communication between FPGA and external memory. Second, we partition all the edges of each subgraph into non-overlapping matchings to extract the maximum parallelism. Third, we propose a batching algorithm to schedule the execution of the edges inside each matching to reduce the memory access conflicts to the on-chip RAMs of FPGA. Compared with non-optimized FPGA-based baseline designs, the proposed optimizations result in up to 60× data dependency reduction, 4.2× bank conflict reduction, and 15.4× speedup. We evaluate the performance of our design using a state-of-the-art FPGA device. Experimental results show that our FPGA accelerator sustains a high computing throughput of up to 217 billion floating-point operations per second (GFLOPS) for training very large real-life sparse matrices. Compared with highly-optimized GPU-based accelerators, our FPGA accelerator achieves up to 12.7× speedup. Based on our optimization methodology, we also implement a software-based design on a multi-core platform, which demonstrates 1.3× speedup compared with the state-of-the-art multi-core implementation.

The paper presents an algorithm for the worst case response time (WCRT) estimation for multiprocessor systems with fixed-priority preemptive schedulers and the interval uncertainty of tasks execution times. Each task has a unique priority within its processor, a period, an execution time interval [BCET, WCET] and can have data dependency on other tasks. If a decrease in the execution time of the task A can lead to an increase in the response time of the another task B, then task A is called an anomalous task for task B. According to the chosen approach, in order to estimate a task’s WCRT, two steps should be performed. The first one is to construct a set of anomalous tasks using the proposed algorithm for the given task. The paper provides the algorithm and the proof of its correctness. The second one is to find the WCRT estimation using a genetic algorithm. The proposed approach has been implemented software as a program in Python3. A set of experiments have been carried out in order to compare the proposed method in terms of precision and speed with two well-known WCRT estimating methods: the method that does not take into account interval uncertainty (assuming that the execution time of a given task is equal to WCET) and the brute force method. The results of the experiments have shown that, in contrast to the brute force method, the proposed method is applicable to the analysis of the real scale computing systems and also allows to achieve greater precision than the method that does not take into account interval uncertainty.

For the fault diagnosis problems of rotating machinery in the real industrial practice, measurement data with imbalanced class distributions negatively affect the diagnostic performance of most conventional machine learning classification algorithms since equal cost weights are assigned to different fault classes. Meanwhile, the widely used traditional data generation methods for the imbalanced data problem are limited by data dependencies over time continuity. To fill this research gap, this paper develops a new diagnostic framework based on the adversarial neural networks (GAN) and multi-sensor data fusion technique to generate new synthetic data for data compensation purpose. Two different practice modes are designed based on this framework according to the position logic of the data fusion, namely a Pre-fusion GAN mode and a Post-fusion GAN mode. More concretely, without data pre-processing, the designed generator generates synthetic data to puzzle the discriminator and the synthetic data that out-trick the discriminator can be used to compensate the minor class. To avoid data dependency and to ensure the generality of the proposed framework, the network modelling are trained with a more practical approach where the training and test data are obtained under different rotating speeds. Two imbalanced data sets on the rotating machinery, one benchmark public rolling bearing data set and another gear box data set acquired in our lab, are used to validate the proposed method. The performance is examined through a wide range of data imbalanced ratios (as high as 30:1), and compared with other state-of-the-art methods. The experiment results conclude that the proposed Pre-fusion GAN and Post-fusion GAN frameworks both have good performance on the imbalanced fault diagnosis of rotating machinery.

Newly introduced Iris recognition systems (IRSs) run on serial processors. In this paper, an alternative method has been introduced for parallel processing on Graphic processing unit (GPU) with Compute unified device architecture (CUDA) in order to increase the speed of the system. The IRS has two main parallel processing criteria, which include the division of computations into hundreds of independent units and the time of calculation more than the time of transferring from the GPU. The IRS is divided into six stages including imaging, pre-processing, segmentation, normalization, feature extraction, and matching. In order to increase speed and accuracy, two stages of iris segmentation and matching play an important role in the IRS. In this paper parallel execution of an identical algorithm for these two stages has been used. The reason for paralleling the iris segmentation stage and their low speed matching is due to a great amount of information in the iris database, plenty of calculations and lack of data dependency in these two stages. For parallelism at the segmentation stage, for each radius, the Hough transform (HT) is a processor, and in the matching stage two parts are considered: The first part consists of 32 actions comparing the input code with the database code in parallel and in the second part 2048 bits with the use of threads on each processor is performed in two sub-sections in pairs of bits and in parallel with each other. Finally, the two-way coding is achieved. In compare of existing methods, this method has rather more accurate and is also superior in terms of processing time on the GPU with CUDA. The results of the implementation of the above method on the images in UBIRIS, BATH, CASIA and MMUI databases show that the proposed method has a precision accuracy of 99.12%, 97.98%, 98.80% and 98.34%, respectively, and the average speedup for parallel processing of images in the database in the proposed method on the GPU with CUDA are 18.8, 14.7, 18, and 19 times, respectively.

This paper presents a new method for parallelizing geodesic algorithms on triangle meshes. Using the half-edge data structure, we define the propagation dependency graph to characterize data dependency in computing geodesics. Then, we design an active strategy such that the vertices and half-edges on the wavefront take the initiative to collect their input data and then propagate windows and update geodesic information in their own memory space. As a result, all the read and write operations can be carried out simultaneously. Our method, named AWP, works for both exact (e.g., the CH algorithm) and approximate (e.g., the fast marching method) geodesic algorithms. Our implementation on various NVIDIA GPUs exhibit perfect linear speedup, i.e., doubling the computational power (i.e., FLOPS) doubles the speed. We prove that the AWP-CH algorithm runs in O(n2∕min(C,n)) time, where n and C are the numbers of faces and cores, respectively. Evaluation on GTX Titan XP shows that AWP-CH empirically runs in np time, p∈[1.25,1.35], for real-world models with n≤107 and anisotropy measure τ≤2.0. Thanks to its perfect efficiency and the trend of increasing the number of processors in graphics hardware, we believe that the actual performance of AWP can be further improved in the near future. Ministry of Education (MOE) This project is partially supported by the National Natural Science Foundation of China (Grant No. 61402322), Tianjin Research Program of Application Foundation and Advanced Technology, China (Grant No, 15JCQNJC00300) and Singapore Ministry of Education Grant RG26/17.

This study focuses on the fault diagnosis of a hydroelectric generation system with hydraulic‐mechanical‐electric structures. To achieve this analysis, a methodology combining Bayesian network approach and fault diagnosis expert system is presented, which enables the time‐based maintenance to transform to the condition‐based maintenance. First, fault types and the associated fault characteristics of the generation system are extensively analyzed to establish a precise Bayesian network. Then, the Noisy‐Or modeling approach is used to implement the fault diagnosis expert system, which not only reduces node computations without severe information loss but also eliminates the data dependency. Some typical applications are proposed to fully show the methodology capability of the fault diagnosis of the hydroelectric generation system.

Recently, the authors have proposed a scalable holistic scheduling approach for time-triggered applications on FlexRay, under end-to-end deadline and data dependency constraints. This approach divides the problem to two sub-problems that can be solved separately. The first sub-problem optimally schedules the set of messages to minimize number of used slots, and with respect to information exchanges between tasks and messages, end-to-end deadlines and FlexRay protocol constraints. The second sub-problem optimally schedules the set of tasks to minimize tasks response times, with respect to the solution returned by the first sub-problem. In this paper, our goal is to increase the scalability of our solution to each sub-problem. We propose a greedy heuristic approach for the first sub-problem that can find feasible solutions at a low runtime cost. In addition, to resolve assignment conflicts, we apply rescheduling the conflicted application with offset modification and priority promotion procedures. Furthermore, we show that the task scheduling in the second sub-problem can be divided into K independent child sub-problems, where K is the number of ECUs. Our experiments show high scalability and efficiency of our approaches comparing with our optimization-based approaches in the previous work.

Rate-compatible modulation (RCM) achieves seamless rate adaptation under time-varying channels by varying the number of transmitted symbols at a small granularity. The implementation of effective decoders based on the belief propagation (BP) algorithm suffers from the varying number of symbols and highly complex symbol nodes. Considering these RCM-specific characteristics, we present a top–down design methodology, including decoding algorithm, mapping matrix construction, and hardware implementation. The layered BP algorithm provides the potential to implement the decoders that fine-tune the decoding throughput according to the number of symbols. To mitigate the impact of inter-layer data dependency on decoding throughput and facilitate the implementation of low parallelism decoders, a construction and optimization algorithm is proposed to obtain the two-level quasi-cyclic matrices with small sub-matrix size. The proposed algorithm and matrix are applied to a partially parallel RCM decoder for a ${5544 \times 5544}$ matrix on a field-programmable gate-array (FPGA) device. A memory access structure that requires only one barrel shifter is used to improve area efficiency. The post-route results show that the decoder achieves a throughput of 377 M ~ 1100 Mbit/s at six iterations with a clock frequency of 218 MHz.

Well plugging and abandonment are necessitated to ensure safe closure of a non-producing offshore asset. Little or no condition monitoring is done after the abandonment operation, and data are often unavailable to analyze the risks of potential leakage. It is therefore essential to capture all inherent and evolving hazards associated with this activity before its implementation. The current probabilistic risk analysis approaches such as fault tree, event tree and bowtie though able to model potential leak scenarios; these approaches have limited capabilities to handle evolving well conditions and data unavailability. Many of the barriers of an abandoned well deteriorates over time and are dependent on external conditions, making it necessary to consider advanced approaches to model potential leakage risk. This paper presents a Bayesian network-based model for well plugging and abandonment. The proposed model able to handle evolving conditions of the barriers, their failure dependence and, also uncertainty in the data. The model uses advanced logic conditions such as Noisy-OR and leaky Noisy-OR to define the condition and data dependency. The proposed model is explained and tested on a case study from the Elgin platform's well plugging and abandonment failure.

In classification theory, it is generally assumed that the data are independent and identically distributed. However, in many practical applications, we face a set of observations that are collected sequentially with a dependence structure among samples. The primary focus of this investigation is to construct the optimal Bayesian classifier (OBC) when the training observations are serially dependent. To model the effect of dependency, we assume the training observations are generated from $\text{VAR }(p)$ , which is a multidimensional vector autoregressive process of order $p$ . At the same time, we assume there exists uncertainty about parameters governing the $\text{VAR}(p)$ model. To model this uncertainty, we assume that model parameters (coefficient matrices) are random variables with a prior distribution, and find the resulting OBC under the assumption of known covariance matrices of white-noise processes. We employ simulations using both synthetic and real data to demonstrate the efficacy of the constructed OBC.

We present Lerna, an end-to-end tool that automatically and transparently detects and extracts parallelism from data-dependent sequential loops. Lerna uses speculation combined with a set of techniques including code profiling, dependency analysis, instrumentation, and adaptive execution. Speculation is needed to avoid conservative actions and detect actual conflicts. Lerna targets applications that are hard-to-parallelize due to data dependency. Our experimental study involves the parallelization of 13 applications with data dependencies. Results on a 24-core machine show an average of 2.7× speedup for micro-benchmarks and 2.5× for the macro-benchmarks.

Non-dominated sorting is a crucial component of Pareto-based multi- and many-objective evolutionary algorithms. As the number of objectives increases, the execution time of a multi-objective evolutionary algorithm increases, too. Since multi-objective evolutionary algorithms normally have a low data dependency, research-ers have increasingly adopted parallel programming techniques to reduce their execution time. Evidently, it is also desirable to parallelize non-dominated sorting. There are some recent proposals which focus on the parallelization of non-dominated sorting, with a particular emphasis on a very well-known approach called fast non-dominated sorting. In this paper, however, we explore the scope of parallelism in an approach called divide-and-conquer based non-dominated sorting (DCNS), which we recently introduced. This paper explores the parallelism from a theoretical point of view. The parallelization of the DCNS approach has been explored considering the PRAM-CREW (Parallel Random Access Machine, Concurrent Read Exclusive Write) model. The analysis of parallel algorithms is usually carried out under the assumption that an unbounded number of processors are available. So, in our analysis, we have also considered the same assumption. The time and space complexities of the parallel version of the DCNS approach is obtained in different scenarios. The time complexity of the parallel version of the DCNS approach in different scenarios is proved to be $$\mathcal {O}(\log M + N)$$ . We have also obtained the maximum number of processors which can be required by the parallel version of the DCNS approach. The comparison of the parallel version of the DCNS approach with respect to some other approaches is also performed.

Smith–Waterman algorithm (SW) is a popular dynamic programming algorithm widely used in bioinformatics for local biological sequence alignment. Due to the $$O(n^2)$$ high time and space complexity of SW and growing size of biological data, it is crucial to accelerate SW for high performance. In view of the GPU high efficiency in science computation, many existing studies (e.g., CUDAlign, CUDASW++) speedup SW with GPU. However, the strong data dependency makes SW communication intensive, and the previous works fail to fully leverage the heterogeneous capabilities of the GPU machine for either the neglect of the CPU ability or the low bandwidth of PCI-e. In this paper, we propose ASW, which aims at accelerating SW algorithm with accelerated processing unit (APU), a heterogeneous processor integrates CPU and GPU in a single die and share the same memory. This coupled CPU–GPU architecture is more suitable for frequent data exchanging due to the elimination of PCI-e bus. For the full utilization of both CPU and GPU in APU system, ASW partitions the whole SW matrix into blocks and dynamically dispatches each block to CPU and GPU for the concurrent execution. A DAG-based dynamic scheduling method is presented to dispatch the workload automatically. Moreover, we also design a time cost model to determine the partition granularity in the matrix division phase. We have evaluated ASW on AMD A12 platform and our results show that ASW achieves a good performance of 7.2 GCUPS (gigacells update per second).

Today enterprises have massive stream data that require to be processed in real time due to data explosion in recent years. Spark Streaming as an emerging system is developed to process real time stream data analytics by using micro-batch approach. The unified programming model of Spark Steaming leads to some unique benefits over other traditional streaming systems, such as fast recovery from failures, better load balancing and resource usage. It treats the continuous stream as a series of micro-batches of data and continuously process these micro-batch jobs. However, efficient scheduling of micro-batch jobs to achieve high throughput and low latency is very challenging due to the complex data dependency and dynamism inherent in streaming workloads. In this paper, we propose A-scheduler, an adaptive scheduling approach that dynamically schedules parallel micro-batch jobs in Spark Streaming and automatically adjusts scheduling parameters to improve performance and resource efficiency. Specifically, A-scheduler dynamically schedules multiple jobs concurrently using different policies based on their data dependencies and automatically adjusts the level of job parallelism and resource shares among jobs based on workload properties. Furthermore, we integrate dynamic batching technique with A-Scheduler to further improve the overall performance of the customized Spark Streaming system. It relies on an expert fuzzy control mechanism to dynamically adjust the length of each batch interval in response to time-varying streaming workload and system processing rate. We implemented A-scheduler and evaluated it with a real-time security event processing workload. Our experimental results show that A-scheduler with dynamic batching can reduce end-to-end latency by 38 percent and meanwhile improve workload throughput and energy efficiency by 23 and 15 percent, respectively, compared to the default Spark Streaming scheduler.

The security of transmitting information from one point to another through different media is an important issue in the modern digital society. Researchers have consistently developed and proposed modern data transfer systems in order to transfer data in a safe manner. DNA (deoxyribonucleic acid) based encryption technology is a new encryption model used to protect data during transmission. Current systems that use DNA technology to encrypt Arabic texts are virtually non-existent and intended to hide data rather than encrypting it (i.e., steganography). In this research, an asymmetric DNA encryption technology is offered to encrypt and decrypt simple Arabic scripts. This technology depends on the integrity between asymmetric cryptography (i.e. RSA algorithm), dynamic encoding, and data dependency with the scope of DNA computing technology. Asymmetric cryptosystem is used only to begin the process of encryption and decryption, which is then processed fully using DNA computing. The idea of the proposed algorithm aims to generate a dynamic DNA table that depend on plain text, that aims to generate a dynamically generating 14 circular keys based on a multi-level security. Here, JAVA platform is used to implement the proposed work, and the randomization and avalanche effect are used to prove the efficiency of the proposed algorithm. This technique provides a significant change in the encoded text with an average of 53% of the avalanche characteristic.

Vulnerabilities threaten the security of information systems. It is crucial to detect and patch vulnerabilities before attacks happen. However, existing vulnerability detection methods suffer from long-term dependency, out of vocabulary, bias towards global features or local features, and coarse detection granularity. This paper proposes an automatic vulnerability detection framework in source code based on a hybrid neural network. First, the inputs are transformed into an intermediate representation with explicit structure information using lower level virtual machine intermediate representation (LLVM IR) and backward program slicing. After the transformation, the size of samples and the size of vocabulary are significantly reduced. A hybrid neural network model is then applied to extract high-level features of vulnerability, which learns features both from convolutional neural networks (CNNs) and recurrent neural networks (RNNs). The former is applied to learn local vulnerability features, such as buffer size. Furthermore, the latter is utilized to learn global features, such as data dependency. The extracted features are made up of concatenated outputs of CNN and RNN. Experiments are performed to validate our vulnerability detection method. The results show that our proposed method achieves excellent results with F1-scores of 98.6% and accuracy of 99.0% on the SARD dataset. It outperforms state-of-the-art methods.

In current times, with data security being recognised as an irrefutable requirement within an organisation, the importance of institution of intrusion detection system has grown manifolds. Identification of outsider attacks as well as misuse of database privileges by authorised entity has been a primary requirement in modern intrusion detection systems. In this paper we present BIDE (BI-Directional Extension) an efficient algorithm for mining frequent closed sequences without candidate maintenance and modified Particle Swarm Optimization clustering based malicious query detection (BPSOMQD), an advanced approach that detects and prevents malicious transactions from disrupting the consistency of the database. This method incorporates frequent closed sequential pattern mining which forms the basis for generation of data dependency rules. Further to recognise anomalous user activity, modified Particle Swarm Optimization algorithm is proposed which is used to generate role profiles associated with the transaction. A combination of Multilevel Rule Similarity Score (MRSS) between data dependency rules with incoming transaction and Cluster Similarity Index (CSI) with generated role profiles is considered to categorise the transaction as malicious or non-malicious. Experimental evaluation of proposed approach shows remarkable results on a characteristic banking database with accuracies over 92.37%.

Smart contracts are Turing-complete programs that are executed across a blockchain. Unlike traditional programs, once deployed, they cannot be modified. As smart contracts carry more value, they become more of an exciting target for attackers. Over the last years, they suffered from exploits costing millions of dollars due to simple programming mistakes. As a result, a variety of tools for detecting bugs have been proposed. Most of these tools rely on symbolic execution, which may yield false positives due to over-approximation. Recently, many fuzzers have been proposed to detect bugs in smart contracts. However, these tend to be more effective in finding shallow bugs and less effective in finding bugs that lie deep in the execution, therefore achieving low code coverage and many false negatives. An alternative that has proven to achieve good results in traditional programs is hybrid fuzzing, a combination of symbolic execution and fuzzing. In this work, we study hybrid fuzzing on smart contracts and present ConFuzzius, the first hybrid fuzzer for smart contracts. ConFuzzius uses evolutionary fuzzing to exercise shallow parts of a smart contract and constraint solving to generate inputs that satisfy complex conditions that prevent evolutionary fuzzing from exploring deeper parts. Moreover, ConFuzzius leverages dynamic data dependency analysis to efficiently generate sequences of transactions that are more likely to result in contract states in which bugs may be hidden. We evaluate the effectiveness of ConFuzzius by comparing it with state-of-the-art symbolic execution tools and fuzzers for smart contracts. Our evaluation on a curated dataset of 128 contracts and a dataset of 21K real-world contracts shows that our hybrid approach detects more bugs than state-of-the-art tools (up to 23%) and that it outperforms existing tools in terms of code coverage (up to 69%). We also demonstrate that data dependency analysis can boost bug detection up to 18%.

Scientific workflows are increasingly important for complex scientific applications. Recently, Function as a Service (FaaS) has emerged as a platform for processing non-interactive tasks. FaaS (such as AWS Lambda and Google Cloud Functions) can play an important role in processing scientific workflows. A number of works have demonstrated their ability to process these workflows. However, some issues were identified when workflows executed on cloud functions due to their limits (e.g., stateless behaviour). A major issue is the additional data transfer during the execution between object storage and the FaaS invocation environment. This leads to increased communication costs. DEWE v3 is one of the Workflow Management Systems (WMSs) that already had foundations for processing workflows with cloud functions. In this paper, we have modified the job dispatch algorithm of DEWE v3 on a function environment to reduce data dependency transfers. Our modified algorithm schedules jobs with precedence constraints to be executed in a single function invocation. Therefore, later jobs can utilise output files generated from their predecessor job in the same invocation. This reduces the makespan of workflow execution. We have evaluated the improved scheduling algorithm and the original with small- and large-scale Montage workflows. The experimental results show that our algorithm can reduce the overall makespan in contrast to the original DEWE v3 by about 10%.

Performance has a major impact on the overall quality of software projects. Performance bugs---bugs that substantially decrease run-time---have long been studied in software engineering, and yet they remain incredibly difficult for developers to handle. Because these bugs do not cause fail-stop errors, they are both harder to discover and to fix. As a result, techniques to help programmers detect and reason about performance are needed for managing performance bugs. Here we propose a static, probabilistic embedding technique to provide developers with useful information about potential performance bugs at the statement level. Using Leetcode samples scraped from real algorithms challenges, we use DeepWalk to embed data dependency graphs in Euclidean space. We then describe how these graph embeddings can be used to detect which statements in code are likely to contribute to performance bugs.

Research on data dependencies has experienced a revival as dependency violations can reveal errors in data. Several data cleaning systems use a DBMS to detect such violations. While DBMSs are efficient for some kinds of data dependencies (e.g., unique constraints), they are likely to fall short of satisfactory performance for more complex ones, such as order dependencies. We present a novel system to efficiently detect violations of denial constraints (DCs), a well-known formalism that generalizes many kinds of data dependencies. We describe its execution model, which operates on a compressed block of tuples at-a-time, and we present various algorithms that take advantage of the predicate form in the DCs to provide effective code patterns. Our experimental evaluation includes comparisons with DBMS-based and DC-specific approaches, real-world and synthetic data, and various kinds of DCs. It shows that our system is up to three orders-of-magnitude faster than the other solutions, especially for datasets with a large number of tuples and DCs that identify a large number of violations.

Recently, Long Short-Term Memory (LSTM), a type of recurrent neural network, has been widely employed in realtime applications, such as speech recognition, word segmentation, machine translation, etc. While existing works demonstrate that LSTM can be efficiently deployed in cloud platforms, the high communication latency between cloud and edge will drastically reduce its efficiency. Therefore, efficient LSTM accelerators at the edge are highly demanded. The limited resource in edge devices and the heterogeneous operations in LSTM (e.g., LSTM gates) bring challenges for the LSTM accelerator design. It seems straightforward to implement each operation as a specific hardware kernel. However, the data dependency among gates leads to significant running stalls in the existing heterogeneous-kernel accelerator, resulting in low parallelism and low resource utilization. To overcome the above challenges, this work proposes a novel generic LSTM accelerator design for Field-programmable Gate Array (FPGA) and Application-specific Integrated Circuit (ASIC) platforms, where two fundamental computing patterns (i.e., element-wise multiplication and addition) are incorporated in a unified computing kernel to execute operations in all LSTM gates simultaneously. Thus, the running stalls caused by heterogeneous kernels can be eliminated, achieving full parallelism in LSTM. The proposed technique and architecture are validated on Xilinx PYNQ-Z1 FPGA which can fully utilize the available resource, achieving 10x faster in inference time and 15.2x improvement in computing power efficiency compared with the state-of-the-art LSTM accelerator.

The variability of the wind resource is the primary challenge associated with the introduction of large scale wind power onto electricity networks. In addressing uncertainties associated with wind power, probabilistic power flow analysis (PPF) is often used in resolving current or future system states. These simulations are informed by input scenarios - i.e. time series that represent conditions being simulated. Thereby defining appropriate input scenarios is a critically important part of the process. This study proposes a novel methodology for clustering wind power time series based on the dominant concurrent atmospheric circulation patterns. These patterns are classified into generalized architypes using Self Organizing Maps. Thereby the probabilistic properties and data dependency structures of wind farms are approximated at the hand of the causative weather phenomena. It was found that this methodology resulted in significant variations in the probabilistic properties of wind power time series and the correlations between wind generators. It is anticipated that this methodology could be effectively applied in defining the input characteristics into operational scenarios within a PPF analysis, and inform correlations between wind farms in spatiotemporal probabilistic forecasts.

Symbolic execution is a powerful technique for systematically exploring program paths, but scaling symbolic execution to practical programs remains challenging. State-of-the-art techniques face the challenge to efficiently explore incremental behaviors, especially for highly coupled programs with complex control and data dependency. In this paper, we present a novel approach for incremental symbolic execution based on an iteration loop between path exploration and path suffixes summarization. On one hand, the explored paths are summarized to enable more precise identification of affected paths; on the other hand, the summary guides path exploration to prune paths that have no incremental behaviors. We implemented the prototype of our approach and conducted experiments on a set of real-world applications. The results show that it is efficient and effective in exploring incremental behaviors.

Since business processes are important assets of enterprises, thousands of business processes are modeled. After modeling business process models, a problem arises here is how to improve the efficiency of these models? In this paper, we propose a novel approach to refactor business process models with process fragments substitution for efficiency improvement. First, we propose a process model smell for identifying inefficient process fragments in business process models based on a sequence relation matrix and a data dependency matrix. Second, we propose a refactoring technique to replace inefficient process fragments in business process models with efficient process fragments. After refactoring, concurrent execution of business tasks in efficient process fragments can be maximized, so the efficiency of business process models can be improved. Experiments show our approach can improve efficiency of business process models effectively.

Software-Defined Networking (SDN) is an emerging network architecture that provides programmable networking through a logically centralized controller. As SDN becomes more prominent, its security vulnerabilities become more evident than ever. Serving as the "brain" of a software-defined network, how the control plane (of the network) is exposed to external inputs (i.e., data plane messages) is directly correlated with how secure the network is. Fortunately, due to some unique SDN design choices (e.g., control plane and data plane separation), attackers often struggle to find a reachable path to those vulnerable logic hidden deeply within the control plane.In this paper, we demonstrate that it is possible for a weak adversary who only controls a commodity network device (host or switch) to attack previously unreachable control plane components by maliciously increasing reachability in the control plane. We introduce D2C2 (data dependency creation and chaining) attack, which leverages some widely-used SDN protocol features (e.g., custom fields) to create and chain unexpected data dependencies in order to achieve greater reachability. We have developed a novel tool, SVHunter, which can effectively identify D2C2 vulnerabilities. Till now we have evaluated SVHunter on three mainstream open-source SDN controllers (i.e., ONOS, Floodlight, and Opendaylight) as well as one security-enhanced controller (i.e., SE-Floodlight). SVHunter detects 18 previously unknown vulnerabilities, all of which can be exploited remotely to launch serious attacks such as executing arbitrary commands, exfiltrating confidential files, and crashing SDN services.

This paper proposes a novel latency-hiding hardware architecture based on column-wise matrix-vector multiplication to eliminate data dependency, improving the throughput of systems of RNN models. In addition, a flexible checkerboard tiling strategy is introduced to allow large weight matrices, while supporting element-based parallelism and vector-based parallelism. These optimizations improve the exploitation of the available parallelism to increase run-time hardware utilization and boost inference throughput. Furthermore, a quantization scheme with fine-tuning is proposed to achieve high accuracy. Evaluation results show that the proposed architecture can enhance performance and energy efficiency with little accuracy loss. It achieves 1.05 to 3.35 times better performance and 1.22 to 3.92 times better hardware utilization than a state-of-theart FPGA-based LSTM design, which shows that our approach contributes to high performance FPGA-based LSTM systems.

The maximum common subgraph of two graphs is the largest possible common subgraph, i.e., the common subgraph with as many vertices as possible. Even if this problem is very challenging, as it has been long proven NP-hard, its countless practical applications still motivates searching for exact solutions. This work discusses the possibility to extend an existing, very effective branch-and-bound procedure on parallel multi-core and many-core architectures. We analyze a parallel multi-core implementation that exploits a divide-and-conquer approach based on a thread pool, which does not deteriorate the original algorithmic efficiency and it minimizes data structure repetitions. We also extend the original algorithm to parallel many-core GPU architectures adopting the CUDA programming framework, and we show how to handle the heavily workload-unbalance and the massive data dependency. Then, we suggest new heuristics to reorder the adjacency matrix, to deal with &ldquo, dead-ends&rdquo, and to randomize the search with automatic restarts. These heuristics can achieve significant speed-ups on specific instances, even if they may not be competitive with the original strategy on average. Finally, we propose a portfolio approach, which integrates all the different local search algorithms as component tools, such portfolio, rather than choosing the best tool for a given instance up-front, takes the decision on-line. The proposed approach drastically limits memory bandwidth constraints and avoids other typical portfolio fragility as CPU and GPU versions often show a complementary efficiency and run on separated platforms. Experimental results support the claims and motivate further research to better exploit GPUs in embedded task-intensive and multi-engine parallel applications.

Vulnerabilities in OS kernel are more severe than those in user space because they allow attackers to access a system with full privileges. Fuzzing is an efficient technique to detect vulnerabilities though little fuzzing efforts aim to kernels. On one hand, by hooking the kernel, passive fuzzing can satisfy the dependencies among system calls but get no feedback, and thus fails to generate test cases for a resulted crash. On the other hand, guided with run-time feedback, active fuzzing can easily reproduce the crash with generated test cases, but cannot find bugs in deeper code path due to lacking of data dependency or control dependency. In this paper, we propose a novel approach for fuzzing kernel which combines passive fuzzing and active fuzzing and therefore gain their advantages. We implement the approach in a prototype called X-AFL which currently aims to test the Android kernel. Preliminary evaluation results show that X-AFL is an effective kernel fuzzer and can indeed find kernel vulnerabilities.

Bidirectional order dependencies state relationships of order between lists of attributes. They naturally model the order-by clauses in SQL queries, and are proved effective in query optimizations concerning sorting. Despite their importance, order dependencies on a dataset are typically unknown and are too costly, if not impossible, to design or discover manually. Techniques for automatic order dependency discovery are recently studied. It is challenging for order dependency discovery to scale well, since it is by nature factorial in the number m of attributes and quadratic in the number n of tuples. In this paper, we adopt a strategy that decouples the impact of m from that of n, and that still finds all minimal valid bidirectional order dependencies. We present carefully designed data structures, a host of algorithms and optimizations, for efficient order dependency discovery. With extensive experimental studies on both real-life and synthetic datasets, we verify our approach significantly outperforms state-of-the-art techniques, by orders of magnitude.

Physical attacks, namely invasive, observation and combined, represent a great challenge for today’s digital design. Successful class of strategies adopted by industry, allowing hiding data dependency of the side channel emissions in CMOS is based on balancing. Although attacks on CMOS dynamic power represent a class of state-of-the-art attacks, vulnerabilities exploiting data dependency in CMOS static power and light- modulated static power were recently presented. In this paper, we describe structures and techniques developed to enhance and balance traditional static CMOS bulk structures. To enable data dependency hiding, we propose low-level techniques based on complementary-value induced balancing currents, constant current source behavioral approximation, and light-sensing capability of traditional CMOS structures. The proposed techniques may be used to build a dual-rail circuit balanced from both perspectives: static and dynamic power. The publicly available TSMC180nm node standard cell simulation is used for evaluation.

Long-Short Term Memory (LSTM) can retain memory and learn from data sequences. It gives state-of-the-art accuracy in many applications such as speech recognition, natural language processing and video classifications. Field-Programmable Gate Arrays (FPGAs) have been used to speed up the inference of LSTMs, but FPGA-based LSTM accelerators are limited by the size of on-chip memory and the bandwidth of external memory on FPGA boards. We propose a novel hardware architecture to overcome data dependency and a new blocking-batching strategy to reuse the LSTM weights fetched from external memory to optimize the performance of systems with size-limited on-chip memory for large machine learning models. Evaluation results show that our architecture can achieve 20.8 GOPS/W, which is among the highest for the FPGA-based LSTM designs storing weights in off-chip memory. Our design achieves 1.65 times higher performance-per-watt efficiency and 2.48 times higher performance-per-DSP efficiency when compared with the current state-of-the-art designs of LSTM using weights stored in off-chip memory. Compared with CPU and GPU implementations, our FPGA implementation is 23.7 and 1.3 times faster while consuming 208 and 19.2 times lower energy respectively, which shows that our approach enables large LSTM systems to be processed efficiently on FPGAs with high performance and low power consumption.

Recently Convolutional Neural Networks (CNNs) are widely applied into novel intelligent applications and systems. However, the CNN computation performance is significantly hindered by its computation flow, which computes the model structure sequentially by layers with massive convolution operations. Such a layer-wise sequential computation flow can cause certain performance issues, such as resource under-utilization, huge memory overhead, etc. To solve these problems, we propose a novel CNN structural decoupling method, which could decouple CNN models into "critical paths" and eliminate the inter-layer data dependency. Based on this method, we redefine the CNN computation flow into parallel and cascade computing paradigms, which can significantly enhance the CNN computation performance with both multi-core and single-core CPU processors. Experiments show that, our DC-CNN framework could reduce 24% to 33% latency on multi-core CPUs for CIFAR and ImageNet. On small-capacity mobile platforms, cascade computing could reduce the latency by average 24% on ImageNet and 42% on CIFAR10. Meanwhile, the memory reduction could also reach average 21% and 64%, respectively.

Error-bounded lossy compression is critical to the success of extreme-scale scientific research because of ever-increasing volumes of data produced by today's high-performance computing (HPC) applications. Not only can error-controlled lossy compressors significantly reduce the I/O and storage burden but they can retain high data fidelity for post analysis. Existing state-of-the-art lossy compressors, however, generally suffer from relatively low compression and decompression throughput (up to hundreds of megabytes per second on a single CPU core), which considerably restrict the adoption of lossy compression by many HPC applications especially those with a fairly high data production rate. In this paper, we propose a highly efficient lossy compression approach based on field programmable gate arrays (FPGAs) under the state-of-the-art lossy compression model SZ. Our contributions are fourfold. (1) We adopt a wavefront memory layout to alleviate the data dependency during the prediction for higher-dimensional predictors, such as the Lorenzo predictor. (2) We propose a co-design framework named waveSZ based on the wavefront memory layout and the characteristics of SZ algorithm and carefully implement it by using high-level synthesis. (3) We propose a hardware-algorithm co-optimization method to improve the performance. (4) We evaluate our proposed waveSZ on three real-world HPC simulation datasets from the Scientific Data Reduction Benchmarks and compare it with other state-of-the-art methods on both CPUs and FPGAs. Experiments show that our waveSZ can improve SZ's compression throughput by 6.9X ~ 8.7X over the production version running on a state-of-the-art CPU and improve the compression ratio and throughput by 2.1X and 5.8X on average, respectively, compared with the state-of-the-art FPGA design.

Incremental feature extraction algorithms are designed to analyze large-scale data streams. Many of them suffer from high computational cost, time complexity, and data dependency, which adversely affects the processing of the data stream. With this motivation, this paper presents a novel incremental feature extraction approach based on the Discrete Cosine Transform (DCT) for the data stream. The proposed approach is separated into initial and sequential phases, and each phase uses a fixed-size windowing technique for processing the current samples. The initial phase is performed only on the first window to construct the initial model as a baseline. In this phase, normalization and DCT are applied to each sample in the window. Subsequently, the efficient feature subset is determined by a particle swarm optimization-based method. With the construction of the initial model, the sequential phase begins. The normalization and DCT processes are likewise applied to each sample. Afterward, the feature subset is selected according to the initial model. Finally, the k-nearest neighbor classifier is employed for classification. The approach is tested on the well-known streaming data sets and compared with state-of-the-art incremental feature extraction algorithms. The experimental studies demonstrate the proposed approach’s success in terms of recognition accuracy and learning time.

The complexity in automotive systems engineering is increasing over the last decade. Autonomous driving and new comfort functions are some reasons for this growing complexity. With the introduction of multi-core processors in automotive system architectures, the shift from sequential to parallel thinking is more and more important in the different development phases. Based on the EAST-ADL, we present an approach to support the design process for distributed systems by using partitioning as an additional viewpoint on the architecture level. Therefore, we developed an extension to the EAST-ADL for partitioning and show automatic partitioning analysis on different architecture abstractions. These derived partitions can support system designers during the design process of functional architectures, by having a first insight how independent the functional components are structured from a data dependency viewpoint. This gives hints for the allocation of functions to hardware in later stages of the development process.

ROC analysis involving two large datasets is an important method for analyzing statistics of interest for decision making of a classifier in many disciplines. And data dependency due to multiple use of the same subjects exists ubiquitously in order to generate more samples because of limited resources. Hence, a two-layer data structure is constructed and the nonparametric two-sample two-layer bootstrap is employed to estimate standard errors of statistics of interest derived from two sets of data, such as a weighted sum of two probabilities. In this article, to reduce the bootstrap variance and ensure the accuracy of computation, Monte Carlo studies of bootstrap variability were carried out to determine the appropriate number of bootstrap replications in ROC analysis with data dependency. It is suggested that with a tolerance 0.02 of the coefficient of variation, 2,000 bootstrap replications be appropriate under such circumstances.

Blur detection, a task to determine whether an image is blurred or not, is very helpful in various applications of image processing and computer vision. In this paper, we propose a novel method to accelerate blur detection algorithms based on Haar wavelet transform. The method decouples data dependency to gain fast 3-level Haar wavelet transform. With the obtained independence, the blur detection steps can be performed in parallel using native GPU thread blocks. We evaluated our proposed method on embedded devices, desktop and server. Our experiments show that on desktop and server, the proposed method obtains a huge performance speedup. On embedded devices, our GPU-based 3-level Haar wavelet transform is up to 4.9 times better performance and 4.3 times better power efficiency than CPU-based blur detection algorithms.

Heterogeneous multiprocessor platforms have been widely adopted as an efficient approach to providing high instruction throughput while keeping power and complexity under control. Although this approach can achieve improved performance for large-scale real-time systems, it results in a complex task scheduling problem. All tasks should be scheduled according to a proper strategy such that their deadlines will be met even in the worst case situations. In this work, we study the non-preemptive scheduling problem of periodic tasks with data dependency upon heterogeneous multiprocessor platforms. We first analyze the space, time and precedence constraints of tasks, and propose an exact formulation to determine the schedulability of tasks. Then, inspired from the Heterogeneous Earliest Finish Time (HEFT) algorithm, we present a list-based scheduling heuristic to schedule the jobs generated by the periodic tasks and minimize the jobs' finish time. The proposed approach is efficient and can help in guiding the design of heterogeneous multiprocessor systems.

International audience; Watershed Transform is a widely used image segmentation technique that is known to be very data-intensive and time-consuming. The M-border Kernel Algorithm computes watersheds in the framework of Edge Weighted Graphs and allows to preserve the topology of the initial map. Par-allelization represents an effective solution to accelerate it. However, this task remains challenging due to the nature of this technique. In this paper, we address this problem. We start by analyzing the Data Dependency Issues that this algorithm raises when dealing with parallel execution. With respect to that, we propose a parallelization strategy that opts for vertices scanning instead of edges scanning of the graph while preserving the thinning paradigm on which the M-border Kernel Algorithm is based. We show that this strategy overcomes the problem of the simultaneous lowering of two adjacent M-border edges that may occur when edges scan is used. The implementation of the proposed algorithm on a shared memory multicore architecture proves its effectiveness in terms of speedup. In fact, the experimental results show that a 2 Yosra Braham et al. speedup factor of 5.55 is achieved using 8 processors for 2048 × 2048 images over the performance of the sequential algorithm using a single processor on the same architecture. Furthermore, the gain in terms of execution time and thus speedup is guaranteed whatever is the size of images on which the algorithm is applied. In fact, a speedup factor of 5.55 is obtained for 2048 × 2048 images, 5.11 for 1024 × 1024 images and 4.45 for 512 × 512 images using 8 cores.

In this paper, we study convergence and data dependence of SP and normal-S iterative methods for the class of almost contraction mappings under some mild conditions. The validity of these theoretical results is confirmed with numerical examples. It has been observed that a special case of SP iterative method, namely normal-S iterative method, performs better and so the latter is implemented in the stable inversion of nonlinear discrete time dynamical systems to yield convergence results when Picard iterative method diverges. This is also illustrated with a numerical example. Our work extends and improves upon many results existing in the literature.

With the intensive use of the internet, patient centric healthcare systems shifted away from paper-based records towards a computerized format. Electronic patient centric healthcare databases contain information about patients that should be kept available for further reference. Healthcare databases contain potential data that makes them a goal for attackers. Hacking into these systems and publishing their contents online exposes them to a challenge that affects their continuity. Any denial of this service will not be tolerated since we cannot know when we need to retrieve a patient’s record. Denial of service affects the continuity of the healthcare system which in turn threatens patients’ lives, decreases the efficiency of the healthcare system and increases the operating costs of the attacked healthcare organization. Although there are many defensive security methods that have been devised, nonetheless malicious transactions may find a way to penetrate the secured safeguard and then modify critical data of healthcare databases. When a malicious transaction modifies a patient record in a database, the damage may spread to other records through valid transactions. Therefore, recovery techniques are required. The efficiency of the data recovery algorithm is substantial for e-healthcare systems. A patient cannot wait too long for his/her medical history to be recovered so that the correct medication be prescribed. Nevertheless, in order to have fast data recovery, an efficient damage assessment process should precede the recovery stage. The damage assessment must be performed as the intrusion detection system detects the malicious activity. The execution time of the recovery process is a crucial factor for measuring the performance because it is directly proportional to the denial of service time of any healthcare system. This paper presents a high performance damage assessment and recovery algorithm for e-healthcare systems. The algorithm provides fast damage assessment after an attack by a malicious transaction to keep the availability of the e-healthcare database. Reducing the execution time of recovery is the key target of our algorithm. The proposed algorithm outperforms the existing algorithm. It is about six times faster than the most recent proposed algorithm. In the worst case, the proposed algorithm takes 8.81 ms to discover the damaged part of the database; however, the fastest recent algorithm requires 50.91 ms. In the best case, the proposed algorithm requires 0.43 ms, which is 86 times faster than the fastest recent work. This is a significant reduction of execution time compared with other available approaches. Saving the damage assessment time means shorter denial of service periods, which in turn guarantees the continuity of the patient centric healthcare system.

Cloud computing enables end-users to outsource their dataset and data management needs to a third-party service provider. One of the major security concerns of the outsourcing paradigm is how to protect sensitive information in the outsourced dataset. In some applications, only partial values are considered sensitive. In general, the sensitive information can be protected by encryption. However, data dependency constraints (together with the unencrypted data) in the outsourced data may serve as adversary knowledge and bring security vulnerabilities to the encrypted data. In this paper, we focus on functional dependency (FD), an important type of data dependency constraints, and study the security threats by the adversarial FDs. We design a practical scheme that can defend against the FD attack by encrypting a small amount of non-sensitive data (encryption overhead). We prove that finding the scheme that leads to the optimal encryption overhead is NP-complete, and design efficient heuristic algorithms, under the presence of one or multiple FDs. We design a secure query rewriting scheme that enables the service provider to answer various types of queries on the encrypted data with provable security guarantee. We extend our study to enforce security when there are conditional functional dependencies (CFDs) and data updates. We conduct an extensive set of experiments on two real-world datasets. The experiment results show that our heuristic approach brings small amounts of encryption overhead (at most 1% more than the optimal overhead), and enjoys a 10-time speedup compared with the optimal solution. Besides, our approach can reduce up to 90% of the encryption overhead of state-of-the-art solution.