OpenRaiser/Intern-Atlas huggingface dataset:
Deciphering Malware's use of TLS (without Decryption)
Venue: arXiv cs.CR 2016
Year: 2016

The use of TLS by malware poses new challenges to network threat detection because traditional pattern-matching techniques can no longer be applied to its messages. However, TLS also introduces a complex set of observable data features that allow many inferences to be made about both the client and the server. We show that these features can be used to detect and understand malware communication, while at the same time preserving the privacy of benign uses of encryption. These data features also allow for accurate malware family attribution of network communication, even when restricted to a single, encrypted flow. To demonstrate this, we performed a detailed study of how TLS is used by malware and enterprise applications. We provide a general analysis on millions of TLS encrypted flows, and a targeted study on 18 malware families composed of thousands of unique malware samples and ten-of-thousands of malicious TLS flows. Importantly, we identify and accommodate the bias introduced by the use of a malware sandbox. The performance of a malware classifier is correlated with a malware family's use of TLS, i.e., malware families that actively evolve their use of cryptography are more difficult to classify. We conclude that malware's usage of TLS is distinct from benign usage in an enterprise setting, and that these differences can be effectively used in rules and machine learning classifiers.
Primitive recursive functions versus partial recursive functions: comparing the degree of undecidability
Venue: arXiv cs.LO 2016
Year: 2016

Consider a decision problem whose instance is a function. Its degree of undecidability, measured by the corresponding class of the arithmetic (or Kleene-Mostowski) hierarchy hierarchy, may depend on whether the instance is a partial recursive or a primitive recursive function. A similar situation happens for results like Rice Theorem (which is false for primitive recursive functions). Classical Recursion Theory deals mainly with the properties of partial recursive functions. We study several natural decision problems related to primitive recursive functions and characterise their degree of undecidability. As an example, we show that, for primitive recursive functions, the injectivity problem is Pi^0_1-complete while the surjectivity problem is Pi_2-complete (omit superscripts from now on). We compare the degree of undecidability (measured by the level in the arithmetic hierarchy) of several primitive recursive decision problems with the corresponding problems of classical Recursion Theory. For instance, the problem "does the codomain of a function have exactly one element?" is Pi_1-complete for primitive recursive functions and belongs to the class [Delta_2 - (Sigma_1 UNION Pi_1)] for partial recursive functions. An important decision problem, "does a given primitive recursive function have at least one zero?" is studied in detail.
Deep CORAL: Correlation Alignment for Deep Domain Adaptation
Venue: arXiv cs.CV 2016
Year: 2016

Deep neural networks are able to learn powerful representations from large quantities of labeled input data, however they cannot always generalize well across changes in input distributions. Domain adaptation algorithms have been proposed to compensate for the degradation in performance due to domain shift. In this paper, we address the case when the target domain is unlabeled, requiring unsupervised adaptation. CORAL is a "frustratingly easy" unsupervised domain adaptation method that aligns the second-order statistics of the source and target distributions with a linear transformation. Here, we extend CORAL to learn a nonlinear transformation that aligns correlations of layer activations in deep neural networks (Deep CORAL). Experiments on standard benchmark datasets show state-of-the-art performance.
Cost-Optimal Algorithms for Planning with Procedural Control Knowledge
Venue: arXiv cs.AI 2016
Year: 2016

There is an impressive body of work on developing heuristics and other reasoning algorithms to guide search in optimal and anytime planning algorithms for classical planning. However, very little effort has been directed towards developing analogous techniques to guide search towards high-quality solutions in hierarchical planning formalisms like HTN planning, which allows using additional domain-specific procedural control knowledge. In lieu of such techniques, this control knowledge often needs to provide the necessary search guidance to the planning algorithm, which imposes a substantial burden on the domain author and can yield brittle or error-prone domain models. We address this gap by extending recent work on a new hierarchical goal-based planning formalism called Hierarchical Goal Network (HGN) Planning to develop the Hierarchically-Optimal Goal Decomposition Planner (HOpGDP), an HGN planning algorithm that computes hierarchically-optimal plans. HOpGDP is guided by $h_{HL}$, a new HGN planning heuristic that extends existing admissible landmark-based heuristics from classical planning to compute admissible cost estimates for HGN planning problems. Our experimental evaluation across three benchmark planning domains shows that HOpGDP compares favorably to both optimal classical planners due to its ability to use domain-specific procedural knowledge, and a blind-search version of HOpGDP due to the search guidance provided by $h_{HL}$.
Single-Player and Two-Player Buttons & Scissors Games
Venue: arXiv cs.CC 2016
Year: 2016

We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for $C = 2$ colors but polytime solvable for $C = 1$. Similarly the game is NP-complete if every color is used by at most $F = 4$ buttons but polytime solvable for $F \leq 3$. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.
Compressive Spectral Estimation with Single-Snapshot ESPRIT: Stability and Resolution
Venue: arXiv cs.IT 2016
Year: 2016

In this paper Estimation of Signal Parameters via Rotational Invariance Techniques (ESPRIT) is developed for spectral estimation with single-snapshot measurement. Stability and resolution analysis with performance guarantee for Single-Snapshot ESPRIT (SS-ESPRIT) is the main focus. In the noise-free case, exact reconstruction is guaranteed for any arbitrary set of frequencies as long as the number of measurement data is at least twice the number of distinct frequencies to be recovered. In the presence of noise and under the assumption that the true frequencies are separated by at least two times Rayleigh's Resolution Length, an explicit error bound for frequency reconstruction is given in terms of the dynamic range and the separation of the frequencies. The separation and sparsity constraint compares favorably with those of the leading approaches to compressed sensing in the continuum.
A Quadratic Programming Relaxation Approach to Compute-and-Forward Network Coding Design
Venue: arXiv cs.IT 2016
Year: 2016

Using physical layer network coding, compute-and-forward is a promising relaying scheme that effectively exploits the interference between users and thus achieves high rates. In this paper, we consider the problem of finding the optimal integer-valued coefficient vector for a relay in the compute-and-forward scheme to maximize the computation rate at that relay. Although this problem turns out to be a shortest vector problem, which is suspected to be NP-hard, we show that it can be relaxed to a series of equality-constrained quadratic programmings. The solutions of the relaxed problems serve as real-valued approximations of the optimal coefficient vector, and are quantized to a set of integer-valued vectors, from which a coefficient vector is selected. The key to the efficiency of our method is that the closed-form expressions of the real-valued approximations can be derived with the Lagrange multiplier method. Numerical results demonstrate that compared with the existing methods, our method offers comparable rates at an impressively low complexity.
Downlink Cell Association and Load Balancing for Joint Millimeter Wave-Microwave Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

The integration of millimeter-wave base stations (mmW-BSs) with conventional microwave base stations ($μ$W-BSs) is a promising solution for enhancing the quality-of-service (QoS) of emerging 5G networks. However, the significant differences in the signal propagation characteristics over the mmW and $μ$W frequency bands will require novel cell association schemes cognizant of both mmW and $μ$W systems. In this paper, a novel cell association framework is proposed that considers both the blockage probability and the achievable rate to assign user equipments (UEs) to mmW-BSs or $μ$W-BSs. The problem is formulated as a one-to-many matching problem with minimum quota constraints for the BSs that provides an efficient way to balance the load over the mmW and $μ$W frequency bands. To solve the problem, a distributed algorithm is proposed that is guaranteed to yield a Pareto optimal and two-sided stable solution. Simulation results show that the proposed matching with minimum quota (MMQ) algorithm outperforms the conventional max-RSSI and max-SINR cell association schemes. In addition, it is shown that the proposed MMQ algorithm can effectively balance the number of UEs associated with the $μ$W-BSs and mmW-BSs and achieve further gains, in terms of the average sum rate.
Embracing Agile methodology during DevOps Developer Internship Program
Venue: arXiv cs.SE 2016
Year: 2016

The DevOps team adopted agile methodologies during the summer internship program as an initiative to move away from waterfall. The DevOps team implemented the Scrum software development strategy to create an internal data dictionary web application. This article reports on the transition process and lessons learned from the pilot program.
Rigorous Multiple-Precision Evaluation of D-Finite Functions in SageMath
Venue: arXiv cs.SC 2016
Year: 2016

We present a new open source implementation in the SageMath computer algebra system of algorithms for the numerical solution of linear ODEs with polynomial coefficients. Our code supports regular singular connection problems and provides rigorous error bounds.
A Novel Distributed Pseudo TDMA Channel Access Protocol for Multi-Transmit-Receive Wireless Mesh Networks
Venue: arXiv cs.NI 2016
Year: 2016

Wireless Mesh Networks (WMNs) technology has been used in recent years for broadband access in both cities and rural areas. A key development is to equip routers with multiple directional antennas so that these routers can transmit to, or receive from multiple neighbors simultaneously. The Multi-Transmit-Receive (MTR) feature can boost network capacity significantly if suitable scheduling policy is applied. In this paper, we propose a distributed link scheduler called PCP-TDMA that fully utilizes the MTR capability. In particular, it activates every link at least once within the shortest period of time. We evaluated the performance of PCP-TDMA in various network topologies, and compared it against a centralized algorithm called ALGO-2, and two distributed approaches: JazzyMAC and ROMA. The results show that PCP-TDMA achieves similar performance with the centralized algorithm in all scenarios, and outperforms the distributed approaches significantly. Specifically, in a fully connected network, the resulting superframe length of PCP-TDMA is less than 1/3 and 1/2 of JazzyMAC and ROMA, respectively.
On Selfish Creation of Robust Networks
Venue: arXiv cs.GT 2016
Year: 2016

Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.
A k-core Decomposition Framework for Graph Clustering
Venue: arXiv cs.SI 2016
Year: 2016

Graph clustering or community detection constitutes an important task for investigating the internal structure of graphs, with a plethora of applications in several domains. Traditional techniques for graph clustering, such as spectral methods, typically suffer from high time and space complexity. In this article, we present CoreCluster, an efficient graph clustering framework based on the concept of graph degeneracy, that can be used along with any known graph clustering algorithm. Our approach capitalizes on processing the graph in an hierarchical manner provided by its core expansion sequence, an ordered partition of the graph into different levels according to the k-core decomposition. Such a partition provides an efficient way to process the graph in an incremental manner that preserves its clustering structure, while making the execution of the chosen clustering algorithm much faster due to the smaller size of the graph's partitions onto which the algorithm operates. An experimental analysis on a multitude of real and synthetic data demonstrates that our approach can be applied to any clustering algorithm accelerating the clustering process, while the quality of the clustering structure is preserved or even improved.
Probabilistic Cooperation of a Full-Duplex Relay in Random Access Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this work, we analyze the probabilistic cooperation of a full-duplex relay in a multiuser random-access network. The relay is equipped with on/off modes for the receiver and the transmitter independently. These modes are modeled as probabilities by which the receiver and the transmitter are activated. We provide analytical expressions for the performance of the relay queue, such as arrival and service rates, stability conditions, and the average queue size. We optimize the relay's operation setup to maximize the network-wide throughput while, simultaneously, we keep the relay's queue stable and minimize the consumed energy. Furthermore, we study the effect of the SINR threshold and the self-interference (SI) coefficient on the per-user and network-wide throughput. For low SINR threshold, we show under which circumstances it is beneficial to switch off the relay completely, or switch off the relay's receiver only.
Models of the Chisholm set
Venue: arXiv cs.LO 2016
Year: 2016

We give a counter-example showing that Carmo and Jones' condition 5(e) may conflict with other conditions on the models in their paper \emph{A new approach to contrary-to-duty obligations}.
From Collective Adaptive Systems to Human Centric Computation and Back: Spatial Model Checking for Medical Imaging
Venue: arXiv cs.LO 2016
Year: 2016

Recent research on formal verification for Collective Adaptive Systems (CAS) pushed advancements in spatial and spatio-temporal model checking, and as a side result provided novel image analysis methodologies, rooted in logical methods for topological spaces. Medical Imaging (MI) is a field where such technologies show potential for ground-breaking innovation. In this position paper, we present a preliminary investigation centred on applications of spatial model checking to MI. The focus is shifted from pure logics to a mixture of logical, statistical and algorithmic approaches, driven by the logical nature intrinsic to the specification of the properties of interest in the field. As a result, novel operators are introduced, that could as well be brought back to the setting of CAS.
Incremental Quantitative Analysis on Dynamic Costs
Venue: arXiv cs.PL 2016
Year: 2016

In quantitative program analysis, values are assigned to execution traces to represent a quality measure. Such analyses cover important applications, e.g. resource usage. Examining all traces is well known to be intractable and therefore traditional algorithms reason over an over-approximated set. Typically, inaccuracy arises due to inclusion of infeasible paths in this set. Thus path-sensitivity is one cure. However, there is another reason for the inaccuracy: that the cost model, i.e., the way in which the analysis of each trace is quantified, is dynamic. That is, the cost of a trace is dependent on the context in which the trace is executed. Thus the goal of accurate analysis, already challenged by path-sensitivity, is now further challenged by context-sensitivity. In this paper, we address the problem of quantitative analysis defined over a dynamic cost model. Our algorithm is an "anytime" algorithm: it generates an answer quickly, but if the analysis resource budget allows, it progressively produces better solutions via refinement iterations. The result of each iteration remains sound, but importantly, must converge to an exact analysis when given an unlimited resource budget. In order to be scalable, our algorithm is designed to be incremental. We finally give evidence that a new level of practicality is achieved by an evaluation on a realistic collection of benchmarks.
Two RPG Flow-graphs for Software Watermarking using Bitonic Sequences of Self-inverting Permutations
Venue: arXiv cs.MM 2016
Year: 2016

Software watermarking has received considerable attention and was adopted by the software development community as a technique to prevent or discourage software piracy and copyright infringement. A wide range of software watermarking techniques has been proposed among which the graph-based methods that encode watermarks as graph structures. Following up on our recently proposed methods for encoding watermark numbers $w$ as reducible permutation flow-graphs $F[π^*]$ through the use of self-inverting permutations $π^*$, in this paper, we extend the types of flow-graphs available for software watermarking by proposing two different reducible permutation flow-graphs $F_1[π^*]$ and $F_2[π^*]$ incorporating important properties which are derived from the bitonic subsequences composing the self-inverting permutation $π^*$. We show that a self-inverting permutation $π^*$ can be efficiently encoded into either $F_1[π^*]$ or $F_2[π^*]$ and also efficiently decoded from theses graph structures. The proposed flow-graphs $F_1[π^*]$ and $F_2[π^*]$ enrich the repository of graphs which can encode the same watermark number $w$ and, thus, enable us to embed multiple copies of the same watermark $w$ into an application program $P$. Moreover, the enrichment of that repository with new flow-graphs increases our ability to select a graph structure more similar to the structure of a given application program $P$ thereby enhancing the resilience of our codec system to attacks.
On the Complexity and Approximability of Budget-Constrained Minimum Cost Flows
Venue: arXiv cs.DS 2016
Year: 2016

We investigate the complexity and approximability of the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a second kind of costs associated with each edge, whose total value in a feasible flow is constrained by a given budget B. This problem can, e.g., be seen as the application of the ε-constraint method to the bicriteria minimum cost flow problem. We show that we can solve the problem exactly in weakly polynomial time $O(\log M \cdot MCF(m,n,C,U))$, where C, U, and M are upper bounds on the largest absolute cost, largest capacity, and largest absolute value of any number occuring in the input, respectively, and MCF(m,n,C,U) denotes the complexity of finding a traditional minimum cost flow. Moreover, we present two fully polynomial-time approximation schemes for the problem on general graphs and one with an improved running-time for the problem on acyclic graphs.
Power-Availability-Aware Cell Association for Energy-Harvesting Small-Cell Base Stations
Venue: arXiv cs.IT 2016
Year: 2016

Energy harvesting brings a key solution to the increasing energy bill and environmental concerns but, at the same time, the network availability may be deteriorated due to potential energy shortage. In this paper, we analyze the performance of off-grid small-cell base stations (scBS) with finite battery capacity and design a new power-availability-aware cell association based on periodical broadcast of the scBS battery level. Each mobile terminal (MT) targets its own set of available scBSs before association, i.e. the set of scBSs that can guarantee service provided (i) the scBS battery level, (ii) the power required to satisfy a received power constraint at each MT, given the scBS-MT distance and the shadowing attenuation, and (iii) the estimated power consumed to serve other MTs potentially associated to the same scBS, which is computed using stochastic geometry tools. Next, we develop for it a tractable performance analysis and derive closed-form expressions for the probability of power outage and the coverage probability. By dynamically adapting to the fluctuations of the base station battery and user power requirement, the proposed cell association allows a more even distribution of the available energy in the network, brings robustness against harvesting impairment and thereby, significantly outperforms conventional strategies.
Lexical Based Semantic Orientation of Online Customer Reviews and Blogs
Venue: arXiv cs.CL 2016
Year: 2016

Rapid increase in internet users along with growing power of online review sites and social media has given birth to sentiment analysis or opinion mining, which aims at determining what other people think and comment. Sentiments or Opinions contain public generated content about products, services, policies and politics. People are usually interested to seek positive and negative opinions containing likes and dislikes, shared by users for features of particular product or service. This paper proposed sentence-level lexical based domain independent sentiment classification method for different types of data such as reviews and blogs. The proposed method is based on general lexicons i.e. WordNet, SentiWordNet and user defined lexical dictionaries for semantic orientation. The relations and glosses of these dictionaries provide solution to the domain portability problem. The method performs better than word and text level corpus based machine learning methods for semantic orientation. The results show the proposed method performs better as it shows precision of 87% and83% at document and sentence levels respectively for online comments.