OpenRaiser/Intern-Atlas huggingface dataset:
A simple abstraction of arrays and maps by program translation
Venue: arXiv cs.PL 2015
Year: 2015

We present an approach for the static analysis of programs handling arrays, with a Galois connection between the semantics of the array program and semantics of purely scalar operations. The simplest way to implement it is by automatic, syntactic transformation of the array program into a scalar program followed analysis of the scalar program with any static analysis technique (abstract interpretation, acceleration, predicate abstraction,.. .). The scalars invariants thus obtained are translated back onto the original program as universally quantified array invariants. We illustrate our approach on a variety of examples, leading to the " Dutch flag " algorithm.
Malicious Behavior Detection using Windows Audit Logs
Venue: arXiv cs.CR 2015
Year: 2015

As antivirus and network intrusion detection systems have increasingly proven insufficient to detect advanced threats, large security operations centers have moved to deploy endpoint-based sensors that provide deeper visibility into low-level events across their enterprises. Unfortunately, for many organizations in government and industry, the installation, maintenance, and resource requirements of these newer solutions pose barriers to adoption and are perceived as risks to organizations' missions. To mitigate this problem we investigated the utility of agentless detection of malicious endpoint behavior, using only the standard build-in Windows audit logging facility as our signal. We found that Windows audit logs, while emitting manageable sized data streams on the endpoints, provide enough information to allow robust detection of malicious behavior. Audit logs provide an effective, low-cost alternative to deploying additional expensive agent-based breach detection systems in many government and industrial settings, and can be used to detect, in our tests, 83% percent of malware samples with a 0.1% false positive rate. They can also supplement already existing host signature-based antivirus solutions, like Kaspersky, Symantec, and McAfee, detecting, in our testing environment, 78% of malware missed by those antivirus systems.
Parallel sparse interpolation using small primes
Venue: arXiv cs.SC 2015
Year: 2015

To interpolate a supersparse polynomial with integer coefficients, two alternative approaches are the Prony-based "big prime" technique, which acts over a single large finite field, or the more recently-proposed "small primes" technique, which reduces the unknown sparse polynomial to many low-degree dense polynomials. While the latter technique has not yet reached the same theoretical efficiency as Prony-based methods, it has an obvious potential for parallelization. We present a heuristic "small primes" interpolation algorithm and report on a low-level C implementation using FLINT and MPI.
Fog Computing based Radio Access Networks: Issues and Challenges
Venue: arXiv cs.IT 2015
Year: 2015

A fog computing based radio access network (F-RAN) is presented in this article as a promising paradigm for the fifth generation (5G) wireless communication system to provide high spectral and energy efficiency. The core idea is to take full advantages of local radio signal processing, cooperative radio resource management, and distributed storing capabilities in edge devices, which can decrease the heavy burden on fronthaul and avoid large-scale radio signal processing in the centralized baseband unit pool. This article comprehensively presents the system architecture and key techniques of F-RANs. In particular, key techniques and their corresponding solutions, including transmission mode selection and interference suppression, are discussed. Open issues in terms of edge caching, software-defined networking, and network function virtualization, are also identified.
A consistent solution of the reinitialization equation in the conservative level-set method
Venue: arXiv cs.NA 2015
Year: 2015

In this paper, a new re-initialization method for the conservative level-set function is put forward. First, it has been shown that the re-initialization and advection equations of the conservative level-set function are mathematically equivalent to the re-initialization and advection equations of the localized signed distance function. Next, a new discretization for the spatial derivatives of the conservative level-set function has been proposed. This new discretization is consistent with the re-initialization procedure and it guarantees a second-order convergence rate of the interface curvature on gradually refined grids. The new re-initialization method does not introduce artificial deformations to stationary and non-stationary interfaces, even when the number of re-initialization steps is large.
Rare Speed-up in Automatic Theorem Proving Reveals Tradeoff Between Computational Time and Information Value
Venue: arXiv cs.LO 2015
Year: 2015

We show that strategies implemented in automatic theorem proving involve an interesting tradeoff between execution speed, proving speedup/computational time and usefulness of information. We advance formal definitions for these concepts by way of a notion of normality related to an expected (optimal) theoretical speedup when adding useful information (other theorems as axioms), as compared with actual strategies that can be effectively and efficiently implemented. We propose the existence of an ineluctable tradeoff between this normality and computational time complexity. The argument quantifies the usefulness of information in terms of (positive) speed-up. The results disclose a kind of no-free-lunch scenario and a tradeoff of a fundamental nature. The main theorem in this paper together with the numerical experiment---undertaken using two different automatic theorem provers AProS and Prover9 on random theorems of propositional logic---provide strong theoretical and empirical arguments for the fact that finding new useful information for solving a specific problem (theorem) is, in general, as hard as the problem (theorem) itself.
Making Code Voting Secure against Insider Threats using Unconditionally Secure MIX Schemes and Human PSMT Protocols
Venue: arXiv cs.CR 2015
Year: 2015

Code voting was introduced by Chaum as a solution for using a possibly infected-by-malware device to cast a vote in an electronic voting application. Chaum's work on code voting assumed voting codes are physically delivered to voters using the mail system, implicitly requiring to trust the mail system. This is not necessarily a valid assumption to make - especially if the mail system cannot be trusted. When conspiring with the recipient of the cast ballots, privacy is broken. It is clear to the public that when it comes to privacy, computers and "secure" communication over the Internet cannot fully be trusted. This emphasizes the importance of using: (1) Unconditional security for secure network communication. (2) Reduce reliance on untrusted computers. In this paper we explore how to remove the mail system trust assumption in code voting. We use PSMT protocols (SCN 2012) where with the help of visual aids, humans can carry out $\mod 10$ addition correctly with a 99\% degree of accuracy. We introduce an unconditionally secure MIX based on the combinatorics of set systems. Given that end users of our proposed voting scheme construction are humans we \emph{cannot use} classical Secure Multi Party Computation protocols. Our solutions are for both single and multi-seat elections achieving: \begin{enumerate}[i)] \item An anonymous and perfectly secure communication network secure against a $t$-bounded passive adversary used to deliver voting, \item The end step of the protocol can be handled by a human to evade the threat of malware. \end{enumerate} We do not focus on active adversaries.
Dual Memory Architectures for Fast Deep Learning of Stream Data via an Online-Incremental-Transfer Strategy
Venue: arXiv cs.LG 2015
Year: 2015

The online learning of deep neural networks is an interesting problem of machine learning because, for example, major IT companies want to manage the information of the massive data uploaded on the web daily, and this technology can contribute to the next generation of lifelong learning. We aim to train deep models from new data that consists of new classes, distributions, and tasks at minimal computational cost, which we call online deep learning. Unfortunately, deep neural network learning through classical online and incremental methods does not work well in both theory and practice. In this paper, we introduce dual memory architectures for online incremental deep learning. The proposed architecture consists of deep representation learners and fast learnable shallow kernel networks, both of which synergize to track the information of new data. During the training phase, we use various online, incremental ensemble, and transfer learning techniques in order to achieve lower error of the architecture. On the MNIST, CIFAR-10, and ImageNet image recognition tasks, the proposed dual memory architectures performs much better than the classical online and incremental ensemble algorithm, and their accuracies are similar to that of the batch learner.
Some Extensions of the Inversion Complexity of Boolean Functions
Venue: arXiv cs.DM 2015
Year: 2015

The minimum number of NOT gates in a Boolean circuit computing a Boolean function is called the inversion complexity of the function. In 1957, A. A. Markov determined the inversion complexity of every Boolean function and proved that $\lceil\log_{2}(d(f)+1)\rceil$ NOT gates are necessary and sufficient to compute any Boolean function $f$ (where $d(f)$ is maximum number of value changes from 1 to 0 over all increasing chains of tuples of variables values). In this paper we consider Boolean circuits over an arbitrary basis that consists of all monotone functions (with zero weight) and finite nonempty set of non-monotone functions (with unit weight). It is shown that the minimal sufficient for a realization of the Boolean function $f$ number of non-monotone gates is equal to $\lceil\log_{2}(d(f)+1)\rceil - O(1)$. Similar extends of another classical result of A. A. Markov for the inversion complexity of system of Boolean functions has been obtained.
Steganography and Broadcasting
Venue: arXiv cs.CR 2015
Year: 2015

Informally, steganography is the process of exchanging a secret message between two communicating entities so that an eavesdropper may not know that a message has been sent. After a review of some steganographic systems, we found that these systems have some defects. First, there are situations in which some concealment algorithms do not properly hide a secret message. Second, to conceal one bit of a secret message, some ask at least five documents and make at least two sampling operations, thus increasing their run-times. Considering the different ways to communicate with the receiver, we propose two steganographic systems adapted to the email communication whose algorithms are deterministic. To hide one bit of a secret message, our steganographic systems need only one document and performs one sampling operation and therefore significantly reduces the run-time.
Optimising Spatial and Tonal Data for PDE-based Inpainting
Venue: arXiv cs.CV 2015
Year: 2015

Some recent methods for lossy signal and image compression store only a few selected pixels and fill in the missing structures by inpainting with a partial differential equation (PDE). Suitable operators include the Laplacian, the biharmonic operator, and edge-enhancing anisotropic diffusion (EED). The quality of such approaches depends substantially on the selection of the data that is kept. Optimising this data in the domain and codomain gives rise to challenging mathematical problems that shall be addressed in our work. In the 1D case, we prove results that provide insights into the difficulty of this problem, and we give evidence that a splitting into spatial and tonal (i.e. function value) optimisation does hardly deteriorate the results. In the 2D setting, we present generic algorithms that achieve a high reconstruction quality even if the specified data is very sparse. To optimise the spatial data, we use a probabilistic sparsification, followed by a nonlocal pixel exchange that avoids getting trapped in bad local optima. After this spatial optimisation we perform a tonal optimisation that modifies the function values in order to reduce the global reconstruction error. For homogeneous diffusion inpainting, this comes down to a least squares problem for which we prove that it has a unique solution. We demonstrate that it can be found efficiently with a gradient descent approach that is accelerated with fast explicit diffusion (FED) cycles. Our framework allows to specify the desired density of the inpainting mask a priori. Moreover, is more generic than other data optimisation approaches for the sparse inpainting problem, since it can also be extended to nonlinear inpainting operators such as EED. This is exploited to achieve reconstructions with state-of-the-art quality. We also give an extensive literature survey on PDE-based image compression methods.
Latent Regression Bayesian Network for Data Representation
Venue: arXiv cs.LG 2015
Year: 2015

Deep directed generative models have attracted much attention recently due to their expressive representation power and the ability of ancestral sampling. One major difficulty of learning directed models with many latent variables is the intractable inference. To address this problem, most existing algorithms make assumptions to render the latent variables independent of each other, either by designing specific priors, or by approximating the true posterior using a factorized distribution. We believe the correlations among latent variables are crucial for faithful data representation. Driven by this idea, we propose an inference method based on the conditional pseudo-likelihood that preserves the dependencies among the latent variables. For learning, we propose to employ the hard Expectation Maximization (EM) algorithm, which avoids the intractability of the traditional EM by max-out instead of sum-out to compute the data likelihood. Qualitative and quantitative evaluations of our model against state of the art deep models on benchmark datasets demonstrate the effectiveness of the proposed algorithm in data representation and reconstruction.
Automatic Layer Separation using Light Field Imaging
Venue: arXiv cs.CV 2015
Year: 2015

We propose a novel approach that jointly removes reflection or translucent layer from a scene and estimates scene depth. The input data are captured via light field imaging. The problem is couched as minimizing the rank of the transmitted scene layer via Robust Principle Component Analysis (RPCA). We also impose regularization based on piecewise smoothness, gradient sparsity, and layer independence to simultaneously recover 3D geometry of the transmitted layer. Experimental results on synthetic and real data show that our technique is robust and reliable, and can handle a broad range of layer separation problems.
Complexity of Manipulative Actions When Voting with Ties
Venue: arXiv cs.GT 2015
Year: 2015

Most of the computational study of election problems has assumed that each voter's preferences are, or should be extended to, a total order. However in practice voters may have preferences with ties. We study the complexity of manipulative actions on elections where voters can have ties, extending the definitions of the election systems (when necessary) to handle voters with ties. We show that for natural election systems allowing ties can both increase and decrease the complexity of manipulation and bribery, and we state a general result on the effect of voters with ties on the complexity of control.
Power Systems Without Fuel
Venue: arXiv cs.SY 2015
Year: 2015

The finiteness of fossil fuels implies that future electric power systems may predominantly source energy from fuel-free renewable resources like wind and solar. Evidently, these power systems without fuel will be environmentally benign, sustainable, and subject to milder failure scenarios. Many of these advantages were projected decades ago with the definition of the soft energy path, which describes a future where all energy is provided by numerous small, simple, and diverse renewable sources. Here we provide a thorough investigation of power systems without fuel from technical and economic standpoints. The paper is organized by timescale and covers issues like the irrelevance of unit commitment in networks without large, fuel-based generators, the dubiousness of nodal pricing without fuel costs, and the need for new system-level models and control methods for semiconductor-based energy-conversion interfaces.
Empirical Coordination with Channel Feedback and Strictly Causal or Causal Encoding
Venue: arXiv cs.IT 2015
Year: 2015

In multi-terminal networks, feedback increases the capacity region and helps communication devices to coordinate. In this article, we deepen the relationship between coordination and feedback by considering a point-to-point scenario with an information source and a noisy channel. Empirical coordination is achievable if the encoder and the decoder can implement sequences of symbols that are jointly typical for a target probability distribution. We investigate the impact of feedback when the encoder has strictly causal or causal observation of the source symbols. For both cases, we characterize the optimal information constraints and we show that feedback improves coordination possibilities. Surprisingly, feedback also reduces the number of auxiliary random variables and simplifies the information constraints. For empirical coordination with strictly causal encoding and feedback, the information constraint does not involve auxiliary random variable anymore.
Mutually Exclusive Modules in Logic Programming
Venue: arXiv cs.PL 2015
Year: 2015

Logic programming has traditionally lacked devices for expressing mutually exclusive modules. We address this limitation by adopting choice-conjunctive modules of the form $D_0 \& D_1$ where $D_0, D_1$ are a conjunction of Horn clauses and $\&$ is a linear logic connective. Solving a goal $G$ using $D_0 \& D_1$ -- $exec(D_0 \& D_1,G)$ -- has the following operational semantics: $choose$ a successful one between $exec(D_0,G)$ and $exec(D_1,G)$. In other words, if $D_0$ is chosen in the course of solving $G$, then $D_1$ will be discarded and vice versa. Hence, the class of choice-conjunctive modules can capture the notion of mutually exclusive modules.
FM-index for dummies
Venue: arXiv cs.DS 2015
Year: 2015

The FM-index is a celebrated compressed data structure for full-text pattern searching. After the first wave of interest in its theoretical developments, we can observe a surge of interest in practical FM-index variants in the last few years. These enhancements are often related to a bit-vector representation, augmented with an efficient rank-handling data structure. In this work, we propose a new, cache-friendly, implementation of the rank primitive and advocate for a very simple architecture of the FM-index, which trades compression ratio for speed. Experimental results show that our variants are 2--3 times faster than the fastest known ones, for the price of using typically 1.5--5 times more space.
Linear-Time Sequence Comparison Using Minimal Absent Words & Applications
Venue: arXiv cs.DS 2015
Year: 2015

Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realized by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this article, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not occur in the sequence. An absent word is {\em minimal} if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering {\em all} their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences.
Revisiting Pattern Structure Projections
Venue: arXiv cs.DM 2015
Year: 2015

Formal concept analysis (FCA) is a well-founded method for data analysis and has many applications in data mining. Pattern structures is an extension of FCA for dealing with complex data such as sequences or graphs. However the computational complexity of computing with pattern structures is high and projections of pattern structures were introduced for simplifying computation. In this paper we introduce o-projections of pattern structures, a generalization of projections which defines a wider class of projections preserving the properties of the original approach. Moreover, we show that o-projections form a semilattice and we discuss the correspondence between o-projections and the representation contexts of o-projected pattern structures. KEYWORDS: formal concept analysis, pattern structures, representation contexts, projections
Review on the Design of Web Based SCADA Systems Based on OPC DA Protocol
Venue: arXiv cs.OH 2015
Year: 2015

One of the most familiar SCADA (supervisory control and data acquisition) application protocols now is OPC protocol. This interface is supported by almost all SCADA, visualization, and process control systems. There are many research efforts tried to design and implement an approach to access an OPC DA server through the Internet. To achieve this goal they used diverse of modern IT technologies like XML, Web services, Java and AJAX. In this paper, we present a complete classification of the different approaches introduced in the literature. A comparative study is also introduced. Finally we study the feasibility of the realization of these approaches based on the real time constraints imposed by the nature of the problem.
StructMatrix: large-scale visualization of graphs by means of structure detection and dense matrices
Venue: arXiv cs.SI 2015
Year: 2015

Given a large-scale graph with millions of nodes and edges, how to reveal macro patterns of interest, like cliques, bi-partite cores, stars, and chains? Furthermore, how to visualize such patterns altogether getting insights from the graph to support wise decision-making? Although there are many algorithmic and visual techniques to analyze graphs, none of the existing approaches is able to present the structural information of graphs at large-scale. Hence, this paper describes StructMatrix, a methodology aimed at high-scalable visual inspection of graph structures with the goal of revealing macro patterns of interest. StructMatrix combines algorithmic structure detection and adjacency matrix visualization to present cardinality, distribution, and relationship features of the structures found in a given graph. We performed experiments in real, large-scale graphs with up to one million nodes and millions of edges. StructMatrix revealed that graphs of high relevance (e.g., Web, Wikipedia and DBLP) have characterizations that reflect the nature of their corresponding domains; our findings have not been seen in the literature so far. We expect that our technique will bring deeper insights into large graph mining, leveraging their use for decision making.