OpenRaiser/Intern-Atlas huggingface dataset:
Nethammer: Inducing Rowhammer Faults through Network Requests
Venue: arXiv cs.CR 2018
Year: 2018

A fundamental assumption in software security is that memory contents do not change unless there is a legitimate deliberate modification. Classical fault attacks show that this assumption does not hold if the attacker has physical access. Rowhammer attacks showed that local code execution is already sufficient to break this assumption. Rowhammer exploits parasitic effects in DRAM to modify the content of a memory cell without accessing it. Instead, other memory locations are accessed at a high frequency. All Rowhammer attacks so far were local attacks, running either in a scripted language or native code. In this paper, we present Nethammer. Nethammer is the first truly remote Rowhammer attack, without a single attacker-controlled line of code on the targeted system. Systems that use uncached memory or flush instructions while handling network requests, e.g., for interaction with the network device, can be attacked using Nethammer. Other systems can still be attacked if they are protected with quality-of-service techniques like Intel CAT. We demonstrate that the frequency of the cache misses is in all three cases high enough to induce bit flips. We evaluated different bit flip scenarios. Depending on the location, the bit flip compromises either the security and integrity of the system and the data of its users, or it can leave persistent damage on the system, i.e., persistent denial of service. We investigated Nethammer on personal computers, servers, and mobile phones. Nethammer is a security landslide, making the formerly local attack a remote attack.
Accelerating Message Passing for MAP with Benders Decomposition
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a novel mechanism to tighten the local polytope relaxation for MAP inference in Markov random fields with low state space variables. We consider a surjection of the variables to a set of hyper-variables and apply the local polytope relaxation over these hyper-variables. The state space of each individual hyper-variable is constructed to be enumerable while the vector product of pairs is not easily enumerable making message passing inference intractable. To circumvent the difficulty of enumerating the vector product of state spaces of hyper-variables we introduce a novel Benders decomposition approach. This produces an upper envelope describing the message constructed from affine functions of the individual variables that compose the hyper-variable receiving the message. The envelope is tight at the minimizers which are shared by the true message. Benders rows are constructed to be Pareto optimal and are generated using an efficient procedure targeted for binary problems.
Multi-Agent Path Finding with Deadlines: Preliminary Results
Venue: arXiv cs.AI 2018
Year: 2018

We formalize the problem of multi-agent path finding with deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.
Multiple Access Computational Offloading: Communication Resource Allocation in the Two-User Case (Extended Version)
Venue: arXiv cs.IT 2018
Year: 2018

By offering shared computational facilities to which mobile devices can offload their computational tasks, the mobile edge computing framework is expanding the scope of applications that can be provided on resource-constrained devices. When multiple devices seek to use such a facility simultaneously, both the available computational resources and the available communication resources need to be appropriately allocated. In this manuscript, we seek insight into the impact of the choice of the multiple access scheme by developing solutions to the mobile energy minimization problem in the two-user case with plentiful shared computational resources. In that setting, the allocation of communication resources is constrained by the latency constraints of the applications, the computational capabilities and the transmission power constraints of the devices, and the achievable rate region of the chosen multiple access scheme. For both indivisible tasks and the limiting case of tasks that can be infinitesimally partitioned, we provide a closed-form and quasi-closed-form solution, respectively, for systems that can exploit the full capabilities of the multiple access channel, and for systems based on time-division multiple access (TDMA). For indivisible tasks, we also provide quasi-closed-form solutions for systems that employ sequential decoding without time sharing or independent decoding. Analyses of our results show that when the channel gains are equal and the transmission power budgets are larger than a threshold, TDMA (and the suboptimal multiple access schemes that we have considered) can achieve an optimal solution. However, when the channel gains of each user are significantly different and the latency constraints are tight, systems that take advantage of the full capabilities of the multiple access channel can substantially reduce the energy required to offload.
Utilizing Probase in Open Directory Project-based Text Classification
Venue: arXiv cs.IR 2018
Year: 2018

Open Directory Project (ODP) has been successfully utilized in text classification due to its representation ability of various categories. However, ODP includes a limited number of entities, which play an important role in classification tasks. In this paper, we enrich the semantics of ODP categories with Probase entities. To effectively incorporate Probase entities in ODP categories, we first represent each ODP category and Probase entity in terms of concepts. Next, we measure the semantic relevance between an ODP category and a Probase entity based on the concept vector. Finally, we use Probase entity to enrich the semantics of the ODP categories. Our experimental results show that the proposed methodology exhibits a significant improvement over state-of-the-art techniques in the ODP-based text classification.
Bilinear systems with two supports: Koszul resultant matrices, eigenvalues, and eigenvectors
Venue: arXiv cs.SC 2018
Year: 2018

A fundamental problem in computational algebraic geometry is the computation of the resultant. A central question is when and how to compute it as the determinant of a matrix. whose elements are the coefficients of the input polynomials up-to sign. This problem is well understood for unmixed multihomogeneous systems, that is for systems consisting of multihomogeneous polynomials with the * 1 same support. However, little is known for mixed systems, that is for systems consisting of polynomials with different supports. We consider the computation of the multihomogeneous resultant of bilinear systems involving two different supports. We present a constructive approach that expresses the resultant as the exact determinant of a Koszul resultant matrix, that is a matrix constructed from maps in the Koszul complex. We exploit the resultant matrix to propose an algorithm to solve such systems. In the process we extend the classical eigenvalues and eigenvectors criterion to a more general setting. Our extension of the eigenvalues criterion applies to a general class of matrices, including the Sylvester-type and the Koszul-type ones.
User Blocking Considered Harmful? An Attacker-controllable Side Channel to Identify Social Accounts
Venue: arXiv cs.CR 2018
Year: 2018

This paper presents a practical side-channel attack that identifies the social web service account of a visitor to an attacker's website. Our attack leverages the widely adopted user-blocking mechanism, abusing its inherent property that certain pages return different web content depending on whether a user is blocked from another user. Our key insight is that an account prepared by an attacker can hold an attacker-controllable binary state of blocking/non-blocking with respect to an arbitrary user on the same service; provided that the user is logged in to the service, this state can be retrieved as one-bit data through the conventional cross-site timing attack when a user visits the attacker's website. We generalize and refer to such a property as visibility control, which we consider as the fundamental assumption of our attack. Building on this primitive, we show that an attacker with a set of controlled accounts can gain a complete and flexible control over the data leaked through the side channel. Using this mechanism, we show that it is possible to design and implement a robust, large-scale user identification attack on a wide variety of social web services. To verify the feasibility of our attack, we perform an extensive empirical study using 16 popular social web services and demonstrate that at least 12 of these are vulnerable to our attack. Vulnerable services include not only popular social networking sites such as Twitter and Facebook, but also other types of web services that provide social features, e.g., eBay and Xbox Live. We also demonstrate that the attack can achieve nearly 100% accuracy and can finish within a sufficiently short time in a practical setting. We discuss the fundamental principles, practical aspects, and limitations of the attack as well as possible defenses.
Bianet: A Parallel News Corpus in Turkish, Kurdish and English
Venue: arXiv cs.CL 2018
Year: 2018

We present a new open-source parallel corpus consisting of news articles collected from the Bianet magazine, an online newspaper that publishes Turkish news, often along with their translations in English and Kurdish. In this paper, we describe the collection process of the corpus and its statistical properties. We validate the benefit of using the Bianet corpus by evaluating bilingual and multilingual neural machine translation models in English-Turkish and English-Kurdish directions.
Gracefully Degrading Gathering in Dynamic Rings
Venue: arXiv cs.DC 2018
Year: 2018

Gracefully degrading algorithms [Biely \etal, TCS 2018] are designed to circumvent impossibility results in dynamic systems by adapting themselves to the dynamics. Indeed, such an algorithm solves a given problem under some dynamics and, moreover, guarantees that a weaker (but related) problem is solved under a higher dynamics under which the original problem is impossible to solve. The underlying intuition is to solve the problem whenever possible but to provide some kind of quality of service if the dynamics become (unpredictably) higher.In this paper, we apply for the first time this approach to robot networks. We focus on the fundamental problem of gathering a squad of autonomous robots on an unknown location of a dynamic ring. In this goal, we introduce a set of weaker variants of this problem. Motivated by a set of impossibility results related to the dynamics of the ring, we propose a gracefully degrading gathering algorithm.
Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit
Venue: arXiv cs.DC 2018
Year: 2018

Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. These systems process computational workflows in a way that can be mathematically modeled by a fork-and-join queueing network with blocking (FJQN/B). While engineering solutions have long been made to build and scale such systems, it is challenging to rigorously characterize their throughput performance at scale theoretically. What further complicates the study is the presence of heavy-tailed delays that have been widely documented therein. To this end, we introduce two fundamental concepts for networks of arbitrary topology (scaling dimension and extended metric dimension) and utilize an infinite sequence of growing FJQN/Bs to study the throughput limit. The throughput is said to be scalable if the throughput limit infimum of the sequence is strictly positive as the network size grows to infinity. We investigate throughput scalability by focusing on heavy-tailed service times that are regularly varying (with index $α>1$) and featuring the network topology described by the two aforementioned dimensions. In particular, we show that an infinite sequence of FJQN/Bs is throughput scalable if the extended metric dimension $<α-1$ and only if the scaling dimension $\leα-1$. These theoretical results provide new insights on the scalability of a rich class of FJQN/Bs with various structures, including tandem, lattice, hexagon, pyramid, tree, and fractals.
Assembling Omnitigs using Hidden-Order de Bruijn Graphs
Venue: arXiv cs.DS 2018
Year: 2018

De novo DNA assembly is a fundamental task in Bioinformatics, and finding Eulerian paths on de Bruijn graphs is one of the dominant approaches to it. In most of the cases, there may be no one order for the de Bruijn graph that works well for assembling all of the reads. For this reason, some de Bruijn-based assemblers try assembling on several graphs of increasing order, in turn. Boucher et al. (2015) went further and gave a representation making it possible to navigate in the graph and change order on the fly, up to a maximum $K$, but they can use up to $\lg K$ extra bits per edge because they use an LCP array. In this paper, we replace the LCP array by a succinct representation of that array's Cartesian tree, which takes only 2 extra bits per edge and still lets us support interesting navigation operations efficiently. These operations are not enough to let us easily extract unitigs and only unitigs from the graph but they do let us extract a set of safe strings that contains all unitigs. Suppose we are navigating in a variable-order de Bruijn graph representation, following these rules: if there are no outgoing edges then we reduce the order, hoping one appears; if there is exactly one outgoing edge then we take it (increasing the current order, up to $K$); if there are two or more outgoing edges then we stop. Then we traverse a (variable-order) path such that we cross edges only when we have no choice or, equivalently, we generate a string appending characters only when we have no choice. It follows that the strings we extract are safe. Our experiments show we extract a set of strings more informative than the unitigs, while using a reasonable amount of memory.
Maximizing Expected Impact in an Agent Reputation Network -- Technical Report
Venue: arXiv cs.AI 2018
Year: 2018

Many multi-agent systems (MASs) are situated in stochastic environments. Some such systems that are based on the partially observable Markov decision process (POMDP) do not take the benevolence of other agents for granted. We propose a new POMDP-based framework which is general enough for the specification of a variety of stochastic MAS domains involving the impact of agents on each other's reputations. A unique feature of this framework is that actions are specified as either undirected (regular) or directed (towards a particular agent), and a new directed transition function is provided for modeling the effects of reputation in interactions. Assuming that an agent must maintain a good enough reputation to survive in the network, a planning algorithm is developed for an agent to select optimal actions in stochastic MASs. Preliminary evaluation is provided via an example specification and by determining the algorithm's complexity.
Decomposition of quantitative Gaifman graphs as a data analysis tool
Venue: arXiv cs.DB 2018
Year: 2018

We argue the usefulness of Gaifman graphs of first-order relational structures as an exploratory data analysis tool. We illustrate our approach with cases where the modular decompositions of these graphs reveal interesting facts about the data. Then, we introduce generalized notions of Gaifman graphs, enhanced with quantitative information, to which we can apply more general, existing decomposition notions via 2-structures; thus enlarging the analytical capabilities of the scheme. The very essence of Gaifman graphs makes this approach immediately appropriate for the multirelational data framework.
Blockchain to Improve Security, Knowledge and Collaboration Inter-Agent Communication over Restrict Domains of the Internet Infrastructure
Venue: arXiv cs.AI 2018
Year: 2018

This paper describes the deployment and implementation of a blockchain to improve the security, knowledge, intelligence and collaboration during the inter-agent communication processes in restrict domains of the Internet Infrastructure. It is a work that proposes the application of a blockchain, platform independent, on a particular model of agents, but that can be used in similar proposals, once the results on the specific model were satisfactory.
Iterative Bounded Distance Decoding of Product Codes with Scaled Reliability
Venue: arXiv cs.IT 2018
Year: 2018

We propose a modified iterative bounded distance decoding of product codes. The proposed algorithm is based on exchanging hard messages iteratively and exploiting channel reliabilities to make hard decisions at each iteration. Performance improvements up to 0.26 dB are achieved.
The Gap Game
Venue: arXiv cs.CR 2018
Year: 2018

Blockchain-based cryptocurrencies secure a decentralized consensus protocol by incentives. The protocol participants, called miners, generate (mine) a series of blocks, each containing monetary transactions created by system users. As incentive for participation, miners receive newly minted currency and transaction fees paid by transaction creators. Blockchain bandwidth limits lead users to pay increasing fees in order to prioritize their transactions. However, most prior work focused on models where fees are negligible. In a notable exception, Carlsten et al. postulated in CCS'16 that if incentives come only from fees then a mining gap would form~--- miners would avoid mining when the available fees are insufficient. In this work, we analyze cryptocurrency security in realistic settings, taking into account all elements of expenses and rewards. To study when gaps form, we analyze the system as a game we call \emph{the gap game}. We analyze the game with a combination of symbolic and numeric analysis tools in a wide range of scenarios. Our analysis confirms Carlsten et al.'s postulate; indeed, we show that gaps form well before fees are the only incentive, and analyze the implications on security. Perhaps surprisingly, we show that different miners choose different gap sizes to optimize their utility, even when their operating costs are identical. Alarmingly, we see that the system incentivizes large miner coalitions, reducing system decentralization. We describe the required conditions to avoid the incentive misalignment, providing guidelines for future cryptocurrency design.
Cycle-Dehaze: Enhanced CycleGAN for Single Image Dehazing
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we present an end-to-end network, called Cycle-Dehaze, for single image dehazing problem, which does not require pairs of hazy and corresponding ground truth images for training. That is, we train the network by feeding clean and hazy images in an unpaired manner. Moreover, the proposed approach does not rely on estimation of the atmospheric scattering model parameters. Our method enhances CycleGAN formulation by combining cycle-consistency and perceptual losses in order to improve the quality of textural information recovery and generate visually better haze-free images. Typically, deep learning models for dehazing take low resolution images as input and produce low resolution outputs. However, in the NTIRE 2018 challenge on single image dehazing, high resolution images were provided. Therefore, we apply bicubic downscaling. After obtaining low-resolution outputs from the network, we utilize the Laplacian pyramid to upscale the output images to the original resolution. We conduct experiments on NYU-Depth, I-HAZE, and O-HAZE datasets. Extensive experiments demonstrate that the proposed approach improves CycleGAN method both quantitatively and qualitatively.
AMORE-UPF at SemEval-2018 Task 4: BiLSTM with Entity Library
Venue: arXiv cs.CL 2018
Year: 2018

This paper describes our winning contribution to SemEval 2018 Task 4: Character Identification on Multiparty Dialogues. It is a simple, standard model with one key innovation, an entity library. Our results show that this innovation greatly facilitates the identification of infrequent characters. Because of the generic nature of our model, this finding is potentially relevant to any task that requires effective learning from sparse or unbalanced data.
Maximum Entropy Interval Aggregations
Venue: arXiv cs.IT 2018
Year: 2018

Given a probability distribution ${\bf p} = (p_1, \dots, p_n)$ and an integer $1\leq m < n$, we say that ${\bf q} = (q_1, \dots, q_m)$ is a contiguous $m$-aggregation of ${\bf p}$ if there exist indices $0=i_0 < i_1 < \cdots < i_{m-1} < i_m = n$ such that for each $j = 1, \dots, m$ it holds that $q_j = \sum_{k=i_{j-1}+1}^{i_j} p_k.$ In this paper, we consider the problem of efficiently finding the contiguous $m$-aggregation of maximum entropy. We design a dynamic programming algorithm that solves the problem exactly, and two more time-efficient greedy algorithms that provide slightly sub-optimal solutions. We also discuss a few scenarios where our problem matters.
Cognitive MIMO-RF/FSO Cooperative Relay Communication with Mobile Nodes and Imperfect Channel State Information
Venue: arXiv cs.IT 2018
Year: 2018

This work analyzes the performance of an underlay cognitive radio based decode-and-forward mixed multiple-input multiple-output (MIMO) radio frequency/free space optical (RF/FSO) cooperative relay system with multiple mobile secondary and primary user nodes. The effect of imperfect channel state information (CSI) arising due to channel estimation error is also considered at the secondary user transmitters (SU-TXs) and relay on the power control and symbol detection processes respectively. A unique aspect of this work is that both fixed and proportional interference power constraints are employed to limit the interference at the primary user receivers (PU-RXs). Analytical results are derived to characterize the exact and asymptotic outage and bit error probabilities of the above system under practical conditions of node mobility and imperfect CSI, together with impairments of the optical channel, such as path loss, atmospheric turbulence, and pointing errors, for orthogonal space-time block coded transmission between each SU-TX and relay. Finally, simulation results are presented to yield various interesting insights into the system performance such as the benefits of a midamble versus preamble for channel estimation.
Machine Learning for Public Administration Research, with Application to Organizational Reputation
Venue: arXiv cs.CY 2018
Year: 2018

Machine learning methods have gained a great deal of popularity in recent years among public administration scholars and practitioners. These techniques open the door to the analysis of text, image and other types of data that allow us to test foundational theories of public administration and to develop new theories. Despite the excitement surrounding machine learning methods, clarity regarding their proper use and potential pitfalls is lacking. This paper attempts to fill this gap in the literature through providing a machine learning "guide to practice" for public administration scholars and practitioners. Here, we take a foundational view of machine learning and describe how these methods can enrich public administration research and practice through their ability develop new measures, tap into new sources of data and conduct statistical inference and causal inference in a principled manner. We then turn our attention to the pitfalls of using these methods such as unvalidated measures and lack of interpretability. Finally, we demonstrate how machine learning techniques can help us learn about organizational reputation in federal agencies through an illustrated example using tweets from 13 executive federal agencies.