OpenRaiser/Intern-Atlas huggingface dataset:
A lightweight MapReduce framework for secure processing with SGX
Venue: arXiv cs.DC 2017
Year: 2017

MapReduce is a programming model used extensively for parallel data processing in distributed environments. A wide range of algorithms were implemented using MapReduce, from simple tasks like sorting and searching up to complex clustering and machine learning operations. Many of these implementations are part of services externalized to cloud infrastructures. Over the past years, however, many concerns have been raised regarding the security guarantees offered in such environments. Some solutions relying on cryptography were proposed for countering threats but these typically imply a high computational overhead. Intel, the largest manufacturer of commodity CPUs, recently introduced SGX (software guard extensions), a set of hardware instructions that support execution of code in an isolated secure environment. In this paper, we explore the use of Intel SGX for providing privacy guarantees for MapReduce operations, and based on our evaluation we conclude that it represents a viable alternative to a cryptographic mechanism. We present results based on the widely used k-means clustering algorithm, but our implementation can be generalized to other applications that can be expressed using MapReduce model.
Strider: A Hybrid Adaptive Distributed RDF Stream Processing Engine
Venue: arXiv cs.DB 2017
Year: 2017

Real-time processing of data streams emanating from sensors is becoming a common task in Internet of Things scenarios. The key implementation goal consists in efficiently handling massive incoming data streams and supporting advanced data analytics services like anomaly detection. In an on-going, industrial project, we found out that a 24/7 available stream processing engine usually faces dynamically changing data and workload characteristics. These changes impact the engine's performance and reliability. We propose Strider, a hybrid adaptive distributed RDF Stream Processing engine that optimizes logical query plan according to the state of data streams. Strider has been designed to guarantee important industrial properties such as scalability, high availability, fault-tolerant, high throughput and acceptable latency. These guarantees are obtained by designing the engine's architecture with state-of-the-art Apache components such as Spark and Kafka. We highlight the efficiency (e.g., on a single machine machine, up to 60x gain on throughput compared to state-of-the-art systems, a throughput of 3.1 million triples/second on a 9 machines cluster, a major breakthrough in this system's category) of Strider on real-world and synthetic data sets.
A Characterization of Infinite LSP Words
Venue: arXiv cs.FL 2017
Year: 2017

G. Fici proved that a finite word has a minimal suffix automaton if and only if all its left special factors occur as prefixes. He called LSP all finite and infinite words having this latter property. We characterize here infinite LSP words in terms of $S$-adicity. More precisely we provide a finite set of morphisms $S$ and an automaton ${\cal A}$ such that an infinite word is LSP if and only if it is $S$-adic and all its directive words are recognizable by ${\cal A}$.
Optimal Resource Allocation for Power-Efficient MC-NOMA with Imperfect Channel State Information
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study power-efficient resource allocation for multicarrier non-orthogonal multiple access (MC-NOMA) systems. The resource allocation algorithm design is formulated as a non-convex optimization problem which jointly designs the power allocation, rate allocation, user scheduling, and successive interference cancellation (SIC) decoding policy for minimizing the total transmit power. The proposed framework takes into account the imperfection of channel state information at transmitter (CSIT) and quality of service (QoS) requirements of users. To facilitate the design of optimal SIC decoding policy on each subcarrier, we define a channel-to-noise ratio outage threshold. Subsequently, the considered non-convex optimization problem is recast as a generalized linear multiplicative programming problem, for which a globally optimal solution is obtained via employing the branch-and-bound approach. The optimal resource allocation policy serves as a system performance benchmark due to its high computational complexity. To strike a balance between system performance and computational complexity, we propose a suboptimal iterative resource allocation algorithm based on difference of convex programming. Simulation results demonstrate that the suboptimal scheme achieves a close-to-optimal performance. Also, both proposed schemes provide significant transmit power savings than that of conventional orthogonal multiple access (OMA) schemes.
A Novel Neural Network Model for Joint POS Tagging and Graph-based Dependency Parsing
Venue: arXiv cs.CL 2017
Year: 2017

We present a novel neural network model that learns POS tagging and graph-based dependency parsing jointly. Our model uses bidirectional LSTMs to learn feature representations shared for both POS tagging and dependency parsing tasks, thus handling the feature-engineering problem. Our extensive experiments, on 19 languages from the Universal Dependencies project, show that our model outperforms the state-of-the-art neural network-based Stack-propagation model for joint POS tagging and transition-based dependency parsing, resulting in a new state of the art. Our code is open-source and available together with pre-trained models at: https://github.com/datquocnguyen/jPTDP
IoT Stream Processing and Analytics in The Fog
Venue: arXiv cs.NI 2017
Year: 2017

The emerging Fog paradigm has been attracting increasing interests from both academia and industry, due to the low-latency, resilient, and cost-effective services it can provide. Many Fog applications such as video mining and event monitoring, rely on data stream processing and analytics, which are very popular in the Cloud, but have not been comprehensively investigated in the context of Fog architecture. In this article, we present the general models and architecture of Fog data streaming, by analyzing the common properties of several typical applications. We also analyze the design space of Fog streaming with the consideration of four essential dimensions (system, data, human, and optimization), where both new design challenges and the issues arise from leveraging existing techniques are investigated, such as Cloud stream processing, computer networks, and mobile computing.
A Survey on Trapping Sets and Stopping Sets
Venue: arXiv cs.IT 2017
Year: 2017

LDPC codes are used in many applications, however, their error correcting capabilities are limited by the presence of stopping sets and trapping sets. Trapping sets and stopping sets occur when specific low-wiehgt error patterns cause a decoder to fail. Trapping sets were first discovered with investigation of the error floor of the Margulis code. Possible solutions are constructions which avoid creating trapping sets, such as progressive edge growth (PEG), or methods which remove trapping sets from existing constructions, such as graph covers. This survey examines trapping sets and stopping sets in LDPC codes over channels such as BSC, BEC and AWGNC.
One Shot Joint Colocalization and Cosegmentation
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a novel framework in which image cosegmentation and colocalization are cast into a single optimization problem that integrates information from low level appearance cues with that of high level localization cues in a very weakly supervised manner. In contrast to multi-task learning paradigm that learns similar tasks using a shared representation, the proposed framework leverages two representations at different levels and simultaneously discriminates between foreground and background at the bounding box and superpixel level using discriminative clustering. We show empirically that constraining the two problems at different scales enables the transfer of semantic localization cues to improve cosegmentation output whereas local appearance based segmentation cues help colocalization. The unified framework outperforms strong baseline approaches, of learning the two problems separately, by a large margin on four benchmark datasets. Furthermore, it obtains competitive results compared to the state of the art for cosegmentation on two benchmark datasets and second best result for colocalization on Pascal VOC 2007.
Attribute-based Encryption for Attribute-based Authentication, Authorization, Storage, and Transmission in Distributed Storage Systems
Venue: arXiv cs.CR 2017
Year: 2017

Attribute-based encryption is a form of encryption which offers the capacity to encrypt data such that it is only accessible to individuals holding a satisfactory configuration of attributes. As cloud and distributed computing become more pervasive in both private and public spheres, attribute-based encryption holds potential to address the issue of achieving secure authentication, authorization, and transmission in these environments where performance must scale with security while also supporting fine-grained access control among a massively large number of consumers. With this work, we offer an example generic configurable stateless protocol for secure attribute-based authentication, authorization, storage, and transmission in distributed storage systems based upon ciphertext-policy attribute-based encryption (CP-ABE), discuss the experience of implementing a distributed storage system around this protocol, and present future avenues of work enabled by such a protocol. The key contribution of this work is an illustration of a means by which any CP-ABE system may be utilized in a black-box manner for attribute-based authentication and cryptographically enforced attribute-based access control in distributed storage systems.
The Odyssey Approach for Optimizing Federated SPARQL Queries
Venue: arXiv cs.DB 2017
Year: 2017

Answering queries over a federation of SPARQL endpoints requires combining data from more than one data source. Optimizing queries in such scenarios is particularly challenging not only because of (i) the large variety of possible query execution plans that correctly answer the query but also because (ii) there is only limited access to statistics about schema and instance data of remote sources. To overcome these challenges, most federated query engines rely on heuristics to reduce the space of possible query execution plans or on dynamic programming strategies to produce optimal plans. Nevertheless, these plans may still exhibit a high number of intermediate results or high execution times because of heuristics and inaccurate cost estimations. In this paper, we present Odyssey, an approach that uses statistics that allow for a more accurate cost estimation for federated queries and therefore enables Odyssey to produce better query execution plans. Our experimental results show that Odyssey produces query execution plans that are better in terms of data transfer and execution time than state-of-the-art optimizers. Our experiments using the FedBench benchmark show execution time gains of at least 25 times on average.
Mixing MACs: An Introduction to Hybrid Radio Wireless Virtualization
Venue: arXiv cs.NI 2017
Year: 2017

This study presents the design of the hybrid wireless virtualization HWV controller based network architecture. Using a HWV controller, an unified approach can be taken for provisioning and management of virtualized heterogeneous radios, irrespective of their MAC and PHY layer mechanisms. It is shown that the airtime occupancy by transmissions from different slices or groups can be used as a single metric for tying these virtualized platforms. The HWV controller can account and dynamically reprovision slice quotas, which can be used for maximizing the revenue of the network operator or aggregate system throughput performance. Results from simulations show that an HWV controller based infrastructure is able to improve the revenue generated from a single virtualized basestation and an AP by up to 40 percent under tested conditions.
Higher-Order Constrained Horn Clauses and Refinement Types
Venue: arXiv cs.PL 2017
Year: 2017

Motivated by applications in automated verification of higher-order functional programs, we develop a notion of constrained Horn clauses in higher-order logic and a decision problem concerning their satisfiability. We show that, although satisfiable systems of higher-order clauses do not generally have least models, there is a notion of canonical model obtained through a reduction to a problem concerning a kind of monotone logic program. Following work in higher-order program verification, we develop a refinement type system in order to reason about and automate the search for models. This provides a sound but incomplete method for solving the decision problem. Finally, we show that an extension of the decision problem in which refinement types are used directly as guards on existential quantifiers can be reduced to the original problem. This result can be used to show that properties of higher-order functions that are definable using refinement types are also expressible using higher-order constrained Horn clauses.
Stories From the Past Web
Venue: arXiv cs.DL 2017
Year: 2017

Archiving Web pages into themed collections is a method for ensuring these resources are available for posterity. Services such as Archive-It exists to allow institutions to develop, curate, and preserve collections of Web resources. Understanding the contents and boundaries of these archived collections is a challenge for most people, resulting in the paradox of the larger the collection, the harder it is to understand. Meanwhile, as the sheer volume of data grows on the Web, "storytelling" is becoming a popular technique in social media for selecting Web resources to support a particular narrative or "story". There are multiple stories that can be generated from an archived collection with different perspectives about the collection. For example, a user may want to see a story that is composed of the key events from a specific Web site, a story that is composed of the key events of the story regardless of the sources, or how a specific event at a specific point in time was covered by different Web sites, etc. In this paper, we provide different case studies for possible types of stories that can be extracted from a collection. We also provide the definitions and models of these types of stories.
Direct Ensemble Estimation of Density Functionals
Venue: arXiv cs.IT 2017
Year: 2017

Estimating density functionals of analog sources is an important problem in statistical signal processing and information theory. Traditionally, estimating these quantities requires either making parametric assumptions about the underlying distributions or using non-parametric density estimation followed by integration. In this paper we introduce a direct nonparametric approach which bypasses the need for density estimation by using the error rates of k-NN classifiers asdata-driven basis functions that can be combined to estimate a range of density functionals. However, this method is subject to a non-trivial bias that dramatically slows the rate of convergence in higher dimensions. To overcome this limitation, we develop an ensemble method for estimating the value of the basis function which, under some minor constraints on the smoothness of the underlying distributions, achieves the parametric rate of convergence regardless of data dimension.
Scalable Exact Parent Sets Identification in Bayesian Networks Learning with Apache Spark
Venue: arXiv cs.AI 2017
Year: 2017

In Machine Learning, the parent set identification problem is to find a set of random variables that best explain selected variable given the data and some predefined scoring function. This problem is a critical component to structure learning of Bayesian networks and Markov blankets discovery, and thus has many practical applications, ranging from fraud detection to clinical decision support. In this paper, we introduce a new distributed memory approach to the exact parent sets assignment problem. To achieve scalability, we derive theoretical bounds to constraint the search space when MDL scoring function is used, and we reorganize the underlying dynamic programming such that the computational density is increased and fine-grain synchronization is eliminated. We then design efficient realization of our approach in the Apache Spark platform. Through experimental results, we demonstrate that the method maintains strong scalability on a 500-core standalone Spark cluster, and it can be used to efficiently process data sets with 70 variables, far beyond the reach of the currently available solutions.
TableQA: Question Answering on Tabular Data
Venue: arXiv cs.IR 2017
Year: 2017

Tabular data is difficult to analyze and to search through, yielding for new tools and interfaces that would allow even non tech-savvy users to gain insights from open datasets without resorting to specialized data analysis tools or even without having to fully understand the dataset structure. The goal of our demonstration is to showcase answering natural language questions from tabular data, and to discuss related system configuration and model training aspects. Our prototype is publicly available and open-sourced (see https://svakulenko.ai.wu.ac.at/tableqa).
Weak Interactions Based System Partitioning Using Integer Linear Programming
Venue: arXiv cs.SY 2017
Year: 2017

The partitioning of a system model will condition the structure of the controller as well as its design. In order to partition a system model, one has to know what states and inputs to group together to define subsystem models. For a given partitioning, the total magnitude of the interactions between subsystem models is evaluated. Therefore, the partitioning problem seeking for weak interactions can be posed as a minimization problem. Initially, the problem is formulated as a non-linear integer minimization that is then relaxed into a linear integer programming problem. It is shown within this paper that cuts can be applied to the initial search space in order to find the least interacting partitioning; only composed of controllable subsystems. Two examples are given to demonstrate the methodology.
Robust Chance-Constrained Optimization for Power-Efficient and Secure SWIPT Systems
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose beamforming schemes to simultaneously transmit data securely to multiple information receivers (IRs) while transferring power wirelessly to multiple energy-harvesting receivers (ERs). Taking into account the imperfection of the instantaneous channel state information (CSI), we introduce a chance-constrained optimization problem to minimize the total transmit power while guaranteeing data transmission reliability, data transmission security, and power transfer reliability. As the proposed optimization problem is non-convex due to the chance constraints, we propose two robust reformulations of the original problem based on safe-convex-approximation techniques. Subsequently, applying semidefinite programming relaxation (SDR), the derived robust reformulations can be effectively solved by standard convex optimization packages. We show that the adopted SDR is tight and thus the globally optimal solutions of the reformulated problems can be recovered. Simulation results confirm the superiority of the proposed methods in guaranteeing transmission security compared to a baseline scheme. Furthermore, the performance of proposed methods can closely follow that of a benchmark scheme where perfect CSI is available for resource allocation.
Online learnability of Statistical Relational Learning in anomaly detection
Venue: arXiv cs.LG 2017
Year: 2017

Statistical Relational Learning (SRL) methods for anomaly detection are introduced via a security-related application. Operational requirements for online learning stability are outlined and compared to mathematical definitions as applied to the learning process of a representative SRL method - Bayesian Logic Programs (BLP). Since a formal proof of online stability appears to be impossible, tentative common sense requirements are formulated and tested by theoretical and experimental analysis of a simple and analytically tractable BLP model. It is found that learning algorithms in initial stages of online learning can lock on unstable false predictors that nevertheless comply with our tentative stability requirements and thus masquerade as bona fide solutions. The very expressiveness of SRL seems to cause significant stability issues in settings with many variables and scarce data. We conclude that reliable anomaly detection with SRL-methods requires monitoring by an overarching framework that may involve a comprehensive context knowledge base or human supervision.
Factors in Recommending Contrarian Content on Social Media
Venue: arXiv cs.SI 2017
Year: 2017

Polarization is a troubling phenomenon that can lead to societal divisions and hurt the democratic process. It is therefore important to develop methods to reduce it. We propose an algorithmic solution to the problem of reducing polarization. The core idea is to expose users to content that challenges their point of view, with the hope broadening their perspective, and thus reduce their polarity. Our method takes into account several aspects of the problem, such as the estimated polarity of the user, the probability of accepting the recommendation, the polarity of the content, and popularity of the content being recommended. We evaluate our recommendations via a large-scale user study on Twitter users that were actively involved in the discussion of the US elections results. Results shows that, in most cases, the factors taken into account in the recommendation affect the users as expected, and thus capture the essential features of the problem.
DeepXplore: Automated Whitebox Testing of Deep Learning Systems
Venue: arXiv cs.LG 2017
Year: 2017

Deep learning (DL) systems are increasingly deployed in safety- and security-critical domains including self-driving cars and malware detection, where the correctness and predictability of a system's behavior for corner case inputs are of great importance. Existing DL testing depends heavily on manually labeled data and therefore often fails to expose erroneous behaviors for rare inputs. We design, implement, and evaluate DeepXplore, the first whitebox framework for systematically testing real-world DL systems. First, we introduce neuron coverage for systematically measuring the parts of a DL system exercised by test inputs. Next, we leverage multiple DL systems with similar functionality as cross-referencing oracles to avoid manual checking. Finally, we demonstrate how finding inputs for DL systems that both trigger many differential behaviors and achieve high neuron coverage can be represented as a joint optimization problem and solved efficiently using gradient-based search techniques. DeepXplore efficiently finds thousands of incorrect corner case behaviors (e.g., self-driving cars crashing into guard rails and malware masquerading as benign software) in state-of-the-art DL models with thousands of neurons trained on five popular datasets including ImageNet and Udacity self-driving challenge data. For all tested DL models, on average, DeepXplore generated one test input demonstrating incorrect behavior within one second while running only on a commodity laptop. We further show that the test inputs generated by DeepXplore can also be used to retrain the corresponding DL model to improve the model's accuracy by up to 3%.