Biblio

Algorithm parallelization diversifies a complicated computing task into small parts, and thus it receives wide attention when it is implemented to evolutionary algorithms (EA). This works considers a recently developed EA called the Swarm Intelligence Based (SIB) method as a benchmark to compare the performance of two types of parallel computing approaches: a CPU-based approach via OpenMP and a GPU-based approach via CUDA. The experiments are conducted to solve an optimization problem in the search of supersaturated designs via the SIB method. Unlike conventional suggestions, we show that the CPU-based OpenMP outperforms CUDA at the execution time. At the end of this paper, we provide several potential problems in GPU parallel computing towards EA and suggest to use CPU-based OpenMP for parallel computing of EA.

Persistent spread measurement is to count the number of distinct elements that persist in each network flow for predefined time periods. It has many practical applications, including detecting long-term stealthy network activities in the background of normal-user activities, such as stealthy DDoS attack, stealthy network scan, or faked network trend, which cannot be detected by traditional flow cardinality measurement. With big network data, one challenge is to measure the persistent spreads of a massive number of flows without incurring too much memory overhead as such measurement may be performed at the line speed by network processors with fast but small on-chip memory. We propose a highly compact Virtual Intersection HyperLogLog (VI-HLL) architecture for this purpose. It achieves far better memory efficiency than the best prior work of V-Bitmap, and in the meantime drastically extends the measurement range. Theoretical analysis and extensive experiments demonstrate that VI-HLL provides good measurement accuracy even in very tight memory space of less than 1 bit per flow.

In this paper, we present a differential privacy preserving approach, which extracts personality-based knowledge to serve privacy guarantee data analysis on personal sensitive data. Based on the approach, we further implement an end-to-end privacy guarantee system, KaPPA, to provide researchers iterative data analysis on sensitive data. The key challenge for differential privacy is determining a reasonable amount of privacy budget to balance privacy preserving and data utility. Most of the previous work applies unified privacy budget to all individual data, which leads to insufficient privacy protection for some individuals while over-protecting others. In KaPPA, the proposed personality-based privacy preserving approach automatically calculates privacy budget for each individual. Our experimental evaluations show a significant trade-off of sufficient privacy protection and data utility.

Memory-based vulnerabilities are a major source of attack vectors. They allow attackers to gain unauthorized access to computers and their data. Previous research has made significant progress in detecting attacks. However, developers still need to locate and fix these vulnerabilities, a mostly manual and time-consuming process. They face a number of challenges. Particularly, the manifestation of an attack does not always coincide with the exploited vulnerabilities, and many attacks are hard to reproduce in the lab environment, leaving developers with limited information to locate them. In this paper, we propose Ravel, an architectural approach to pinpoint vulnerabilities from attacks. Ravel consists of an online attack detector and an offline vulnerability locator linked by a record & replay mechanism. Specifically, Ravel records the execution of a production system and simultaneously monitors it for attacks. If an attack is detected, the execution is replayed to reveal the targeted vulnerabilities by analyzing the program's memory access patterns under attack. We have built a prototype of Ravel based on the open-source FreeBSD operating system. The evaluation results in security and performance demonstrate that Ravel can effectively pinpoint various types of memory vulnerabilities and has low performance overhead.

The Polytope Escape Problem for continuous linear dynamical systems consists of deciding, given an affine function f:Rd -\textbackslashtextgreater Rd and a convex polytope P⊆ Rd, both with rational descriptions, whether there exists an initial point x0 in P such that the trajectory of the unique solution to the differential equation: ·x(t)=f(x(t)) x 0= x0 is entirely contained in P. We show that this problem is reducible in polynomial time to the decision version of linear programming with real algebraic coefficients. The latter is a special case of the decision problem for the existential theory of real closed fields, which is known to lie between NP and PSPACE. Our algorithm makes use of spectral techniques and relies, among others, on tools from Diophantine approximation.

Approximate nearest neighbor (ANN) search in high-dimensional space plays an essential role in many multimedia applications. Recently, product quantization (PQ) based methods for ANN search have attracted enormous attention in the community of computer vision, due to its good balance between accuracy and space requirement. PQ based methods embed a high-dimensional vector into a short binary code (called PQ code), and the squared Euclidean distance is estimated by asymmetric quantizer distance (AQD) with pretty high precision. Thus, ANN search in the original space can be converted to similarity search on AQD using the PQ approach. All existing PQ methods are in-memory solutions, which may not handle massive data if they cannot fit entirely in memory. In this paper, we propose an I/O-efficient PQ based solution for ANN search. We design an index called PQB+-forest to support efficient similarity search on AQD. PQB+-forest first creates a number of partitions of the PQ codes by a coarse quantizer and then builds a B+-tree, called PQB+-tree, for each partition. The search process is greatly expedited by focusing on a few selected partitions that are closest to the query, as well as by the pruning power of PQB+-trees. According to the experiments conducted on two large-scale data sets containing up to 1 billion vectors, our method outperforms its competitors, including the state-of-the-art PQ method and the state-of-the-art LSH methods for ANN search.

Graph modeling allows numerous security problems to be tackled in a general way, however, little work has been done to understand their ability to withstand adversarial attacks. We design and evaluate two novel graph attacks against a state-of-the-art network-level, graph-based detection system. Our work highlights areas in adversarial machine learning that have not yet been addressed, specifically: graph-based clustering techniques, and a global feature space where realistic attackers without perfect knowledge must be accounted for (by the defenders) in order to be practical. Even though less informed attackers can evade graph clustering with low cost, we show that some practical defenses are possible.

A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs. Essentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called "depth-robustness") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice. In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we: Prove that their depth-robustness is asymptotically maximal. Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF. Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice. Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT).

Certification of keys and attributes is in practice typically realized by a hierarchy of issuers. Revealing the full chain of issuers for certificate verification, however, can be a privacy issue since it can leak sensitive information about the issuer's organizational structure or about the certificate owner. Delegatable anonymous credentials solve this problem and allow one to hide the full delegation (issuance) chain, providing privacy during both delegation and presentation of certificates. However, the existing delegatable credentials schemes are not efficient enough for practical use. In this paper, we present the first hierarchical (or delegatable) anonymous credential system that is practical. To this end, we provide a surprisingly simple ideal functionality for delegatable credentials and present a generic construction that we prove secure in the UC model. We then give a concrete instantiation using a recent pairing-based signature scheme by Groth and describe a number of optimizations and efficiency improvements that can be made when implementing our concrete scheme. The latter might be of independent interest for other pairing-based schemes as well. Finally, we report on an implementation of our scheme in the context of transaction authentication for blockchain, and provide concrete performance figures.

This paper presents Themis, an end-to-end static analysis tool for finding resource-usage side-channel vulnerabilities in Java applications. We introduce the notion of epsilon-bounded non-interference, a variant and relaxation of Goguen and Meseguer's well-known non-interference principle. We then present Quantitative Cartesian Hoare Logic (QCHL), a program logic for verifying epsilon-bounded non-interference. Our tool, Themis, combines automated reasoning in CHL with lightweight static taint analysis to improve scalability. We evaluate Themis on well known Java applications and demonstrate that Themis can find unknown side-channel vulnerabilities in widely-used programs. We also show that Themis can verify the absence of vulnerabilities in repaired versions of vulnerable programs and that Themis compares favorably against Blazer, a state-of-the-art static analysis tool for finding timing side channels in Java applications.

In this paper, we study the model of human trust where an operator controls a robotic swarm remotely for a search mission. Existing trust models in human-in-the-loop systems are based on task performance of robots. However, we find that humans tend to make their decisions based on physical characteristics of the swarm rather than its performance since task performance of swarms is not clearly perceivable by humans. We formulate trust as a Markov decision process whose state space includes physical parameters of the swarm. We employ an inverse reinforcement learning algorithm to learn behaviors of the operator from a single demonstration. The learned behaviors are used to predict the trust level of the operator based on the features of the swarm.

A well studied privacy problem in the area of smart grids is the question of how to aggregate the sum of a set of smart meter readings in a privacy friendly manner, i.e., in such a way that individual meter readings are not revealed to the adversary. Much less well studied is how to deal with arbitrary meter crashes during such aggregation protocols: current privacy friendly aggregation protocols cannot deal with these type of failures. Such failures do happen in practice, though. We therefore propose two privacy friendly aggregation protocols that tolerate such crash failures, up to a predefined maximum number of smart meters. The basic protocol tolerates meter crashes at the start of each aggregation round only. The full, more complex, protocol tolerates meter crashes at arbitrary moments during an aggregation round. It runs in a constant number of phases, cleverly avoiding the otherwise applicable consensus protocol lower bound.

For a secure communication over an insecure channel the Diffie-Hellman key exchange protocol (DHKEP) is treated as the de facto standard. However, it suffers form server-side compromisation, identity compromisation, man-in-the-middle, replay attacks, etc. Also, there are single point of vulnerability (SOV), single point of failure (SOF) and user privacy preservation issues. This work proposes an identity-based two-server DHKEP to address the aforesaid issues and alleviating the attacks. To preserve user identity from outside intruders, a k-anonymity based identity hiding principle has been adopted. Further, to ensure efficient utilization of channel bandwidth, the proposed scheme employs elliptic curve cryptography. The security analysis substantiate that our scheme is provably secure and successfully addressed the above-mentioned issues. The performance study contemplates that the overhead of the protocol is reasonable and comparable with other schemes.

As teleoperated robot technology becomes cheaper, more powerful, and more reliable, remotely-operated telepresence robots will become more prevalent in homes and businesses, allowing visitors and business partners to be present without the need to travel. Hindering adoption is the issue of privacy: an Internet-connected telepresence robot has the ability to spy on its local area, either for the remote operator or a third party with access to the video data. Additionally, since the remote operator may move about and manipulate objects without local-user intervention, certain typical privacy-protecting techniques such as moving objects to a different room or putting them in a cabinet may prove insufficient. In this paper, we examine the effects of three whole-image filters on the remote operator's ability to discern details while completing a navigation task.

This paper explores recent achievements and novel challenges of the annoying privacy-preserving big data stream mining problem, which consists in applying mining algorithms to big data streams while ensuring the privacy of data. Recently, the emerging big data analytics context has conferred a new light to this exciting research area. This paper follows the so-depicted research trend.

SDN approaches to inter-domain routing promise better traffic engineering, enhanced security, and higher automation. Yet, naïve deployment of SDN on the Internet is dangerous as the control-plane expressiveness of BGP is significantly more limited than the data-plane expressiveness of SDN, which allows fine-grained rules to deflect traffic from BGP's default routes. This mismatch may lead to incorrect forwarding behaviors such as forwarding loops and blackholes, ultimately hindering SDN deployment at the inter-domain level. In this work, we make a first step towards verifying the correctness of inter-domain forwarding state with a focus on loop freedom while keeping private the SDN rules, as they comprise confidential routing information. To this end, we design a simple yet powerful primitive that allows two networks to verify whether their SDN rules overlap, i.e., the set of packets matched by these rules is non-empty, without leaking any information about the SDN rules. We propose an efficient implementation of this primitive by using recent advancements in Secure Multi-Party Computation and we then leverage it as the main building block for designing a system that detects Internet-wide forwarding loops among any set of SDN-enabled Internet eXchange Points.

Network accountability, forensic analysis, and failure diagnosis are becoming increasingly important for network management and security. Network provenance significantly aids network administrators in these tasks by explaining system behavior and revealing the dependencies between system states. Although resourceful, network provenance can sometimes be too rich, revealing potentially sensitive information that was involved in system execution. In this paper, we propose a cryptographic approach to preserve the confidentiality of provenance (sub)graphs while allowing users to query and access the parts of the graph for which they are authorized. Our proposed solution is a novel application of searchable symmetric encryption (SSE) and more generally structured encryption (SE). Our SE-enabled provenance system allows a node to enforce access control policies over its provenance data even after the data has been shipped to remote nodes (e.g., for optimization purposes). We present a prototype of our design and demonstrate its practicality, scalability, and efficiency for both provenance maintenance and querying.

Probabilistic model checking is a formal verification technique that has been applied successfully in a variety of domains, providing identification of system errors through quantitative verification of stochastic system models. One domain that can benefit from probabilistic model checking is cloud computing, which must provide highly reliable and secure computational and storage services to large numbers of mission-critical software systems. For real-world domains like cloud computing, external system factors and environmental changes must be estimated accurately in the form of probabilities in system models; inaccurate estimates for the model probabilities can lead to invalid verification results. To address the effects of uncertainty in probability estimates, in previous work we have developed a variety of techniques for perturbation analysis of discrete- and continuous-time Markov chains (DTMCs and CTMCs). These techniques determine the consequences of the uncertainty on verification of system properties. In this paper, we present the first approach for perturbation analysis of Markov decision processes (MDPs), a stochastic formalism that is especially popular due to the significant expressive power it provides through the combination of both probabilistic and nondeterministic choice. Our primary contribution is a novel technique for efficiently analyzing the effects of perturbations of model probabilities on verification of reachability properties of MDPs. The technique heuristically explores the space of adversaries of an MDP, which encode the different ways of resolving the MDP’s nondeterministic choices. We demonstrate the practical effectiveness of our approach by applying it to two case studies of cloud systems.

With technology at our fingertips waiting to be exploited, the past decade saw the revolutionizing Human Computer Interactions. The ease with which a user could interact was the Unique Selling Proposition (USP) of a sales team. Human Computer Interactions have many underlying parameters like Data Visualization and Presentation as some to deal with. With the race, on for better and faster presentations, evolved many frameworks to be widely used by all software developers. As the need grew for user friendly applications, more and more software professionals were lured into the front-end sophistication domain. Application frameworks have evolved to such an extent that with just a few clicks and feeding values as per requirements we are able to produce a commercially usable application in a few minutes. These frameworks generate quantum lines of codes in minutes which leaves a contrail of bugs to be discovered in the future. We have also succumbed to the benchmarking in Software Quality Metrics and have made ourselves comfortable with buggy software's to be rectified in future. The exponential evolution in the cyber domain has also attracted attackers equally. Average human awareness and knowledge has also improved in the cyber domain due to the prolonged exposure to technology for over three decades. As the attack sophistication grows and zero day attacks become more popular than ever, the suffering end users only receive remedial measures in spite of the latest Antivirus, Intrusion Detection and Protection Systems installed. We designed a software to display the complete services and applications running in users Operating System in the easiest perceivable manner aided by Computer Graphics and Data Visualization techniques. We further designed a study by empowering the fence sitter users with tools to actively participate in protecting themselves from threats. The designed threats had impressions from the complete threat canvas in some form or other restricted to systems functioning. Network threats and any sort of packet transfer to and from the system in form of threat was kept out of the scope of this experiment. We discovered that end users had a good idea of their working environment which can be used exponentially enhances machine learning for zero day threats and segment the unmarked the vast threat landscape faster for a more reliable output.

With technology at our fingertips waiting to be exploited, the past decade saw the revolutionizing Human Computer Interactions. The ease with which a user could interact was the Unique Selling Proposition (USP) of a sales team. Human Computer Interactions have many underlying parameters like Data Visualization and Presentation as some to deal with. With the race, on for better and faster presentations, evolved many frameworks to be widely used by all software developers. As the need grew for user friendly applications, more and more software professionals were lured into the front-end sophistication domain. Application frameworks have evolved to such an extent that with just a few clicks and feeding values as per requirements we are able to produce a commercially usable application in a few minutes. These frameworks generate quantum lines of codes in minutes which leaves a contrail of bugs to be discovered in the future. We have also succumbed to the benchmarking in Software Quality Metrics and have made ourselves comfortable with buggy software's to be rectified in future. The exponential evolution in the cyber domain has also attracted attackers equally. Average human awareness and knowledge has also improved in the cyber domain due to the prolonged exposure to technology for over three decades. As the attack sophistication grows and zero day attacks become more popular than ever, the suffering end users only receive remedial measures in spite of the latest Antivirus, Intrusion Detection and Protection Systems installed. We designed a software to display the complete services and applications running in users Operating System in the easiest perceivable manner aided by Computer Graphics and Data Visualization techniques. We further designed a study by empowering the fence sitter users with tools to actively participate in protecting themselves from threats. The designed threats had impressions from the complete threat canvas in some form or other restricted to systems functioning. Network threats and any sort of packet transfer to and from the system in form of threat was kept out of the scope of this experiment. We discovered that end users had a good idea of their working environment which can be used exponentially enhances machine learning for zero day threats and segment the unmarked the vast threat landscape faster for a more reliable output.

Sensors incorporated into mobile devices provide unique opportunities to capture detailed environmental information that cannot be readily collected in other ways. We show here how data from networked navigational sensors on leisure vessels can be used to construct unique new datasets, using the example of underwater topography (bathymetry) to demonstrate the approach. Specifically, we describe an end-to-end workflow that involves the collection of large numbers of timestamped (position, depth) measurements from "internet of floating things" devices on leisure vessels; the communication of data to cloud resources, via a specialized protocol capable of dealing with delayed, intermittent, or even disconnected networks; the integration of measurement data into cloud storage; the efficient correction and interpolation of measurements on a cloud computing platform; and the creation of a continuously updated bathymetric database. Our prototype implementation of this workflow leverages the FACE-IT Galaxy workflow engine to integrate network communication and database components with a CUDA-enabled algorithm running in a virtualized cloud environment.

Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first recording an execution and then replaying that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, etc., do not have a notion of threads. Instead, these languages provide a processor-oblivious model of programming, where programs expose task-parallelism using high-level constructs such as spawn/sync without regard to the number of threads/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads. In this paper, we present a processor-oblivious record-and-replay scheme for such languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme — namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads.

The fast and energy-efficient simulation of dynamical systems defined by coupled ordinary/partial differential equations has emerged as an important problem. The accelerated simulation of coupled ODE/PDE is critical for analysis of physical systems as well as computing with dynamical systems. This paper presents a fast and programmable accelerator for simulating dynamical systems. The computing model of the proposed platform is based on multilayer cellular nonlinear network (CeNN) augmented with nonlinear function evaluation engines. The platform can be programmed to accelerate wide classes of ODEs/PDEs by modulating the connectivity within the multilayer CeNN engine. An innovative hardware architecture including data reuse, memory hierarchy, and near-memory processing is designed to accelerate the augmented multilayer CeNN. A dataflow model is presented which is supported by optimized memory hierarchy for efficient function evaluation. The proposed solver is designed and synthesized in 15nm technology for the hardware analysis. The performance is evaluated and compared to GPU nodes when solving wide classes of differential equations and the power consumption is analyzed to show orders of magnitude improvement in energy efficiency.

Apps written in JavaScript are an easy target for reverse engineering attacks, e.g. to steal the intellectual property or to create a clone of an app. Unprotected JavaScript apps even contain high level information such as developer comments, if those were not explicitly stripped. This fact becomes more and more important with the increasing popularity of JavaScript as language of choice for both web development and hybrid mobile apps. In this paper, we present a novel JavaScript obfuscator based on the Google Closure Compiler, which transforms readable JavaScript source code into a representation much harder to analyze for adversaries. We evaluate this obfuscator regarding its performance impact and its semantics-preserving property.

This paper presents PT-CFI, a new backward-edge control flow violation detection system based on a novel use of a recently introduced hardware feature called Intel Processor Trace (PT). Designed primarily for offline software debugging and performance analysis, PT offers the capability of tracing the entire control flow of a running program. In this paper, we explore the practicality of using PT for security applications, and propose to build a new control flow integrity (CFI) model that enforces a backward-edge CFI policy for native COTS binaries based on the traces from Intel PT. By exploring the intrinsic properties of PT with a system call based synchronization primitive and a deep inspection capability, we have addressed a number of technical challenges such as how to make sure the backward edge CFI policy is both sound and complete, how to make PT enforce our CFI policy, and how to balance the performance overhead. We have implemented PT-CFI and evaluated with a number of programs including SPEC2006 and HTTP daemons. Our experimental results show that PT-CFI can enforce a perfect backward-edge CFI with only small overhead for the protected program.