OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Dynamic Cache Partitioning for Encrypted Content Delivery
Venue: arXiv cs.NI 2016
Year: 2016

In-network caching is an appealing solution to cope with the increasing bandwidth demand of video, audio and data transfer over the Internet. Nonetheless, an increasing share of content delivery services adopt encryption through HTTPS, which is not compatible with traditional ISP-managed approaches like transparent and proxy caching. This raises the need for solutions involving both Internet Service Providers (ISP) and Content Providers (CP): by design, the solution should preserve business-critical CP information (e.g., content popularity, user preferences) on the one hand, while allowing for a deeper integration of caches in the ISP architecture (e.g., in 5G femto-cells) on the other hand. In this paper we address this issue by considering a content-oblivious ISP-operated cache. The ISP allocates the cache storage to various content providers so as to maximize the bandwidth savings provided by the cache: the main novelty lies in the fact that, to protect business-critical information, ISPs only need to measure the aggregated miss rates of the individual CPs and do not need to be aware of the objects that are requested, as in classic caching. We propose a cache allocation algorithm based on a perturbed stochastic subgradient method, and prove that the algorithm converges close to the allocation that maximizes the overall cache hit rate. We use extensive simulations to validate the algorithm and to assess its convergence rate under stationary and non-stationary content popularity. Our results (i) testify the feasibility of content-oblivious caches and (ii) show that the proposed algorithm can achieve within 10\% from the global optimum in our evaluation.
Threshold Multi Secret Sharing Using Elliptic Curve and Pairing
Venue: arXiv cs.CR 2016
Year: 2016

Secret Sharing techniques are now the building blocks of several security protocols. A (t;n) threshold secret sharing scheme is one in which t or more participant can join together to retrieve the secret.Traditional single secret sharing schemes are modified and generalized to share multiple secrets.Use of elliptic curve and pairing in secret sharing is gaining more importance.In this paper we propose a threshold multi secret sharing scheme where more than one secret is shared.When the threshold number of participants collate, the multi secret can be retrieved. The scheme make use of elliptic curve and bilinear pairing.Verification of shares by the participants, shares consistency checking, detection and identification of cheaters are the extended capabilities achieved.The shared secrets are retrieved in single stage here, unlike the multi stage secret sharing scheme.The participants can be added very easily.The scheme is efficient and the number of public parameters are also less compared with the existing threshold multi secret sharing scheme based on the elliptic curve.The dealer can easily modify the secret or add additional secret by changing the public parameters of the scheme.This is the first proposal of a threshold multi secret sharing scheme with extended capabilities using self pairing.
LlamaFur: Learning Latent Category Matrix to Find Unexpected Relations in Wikipedia
Venue: arXiv cs.SI 2016
Year: 2016

Besides finding trends and unveiling typical patterns, modern information retrieval is increasingly more interested in the discovery of surprising information in textual datasets. In this work we focus on finding "unexpected links" in hyperlinked document corpora when documents are assigned to categories. To achieve this goal, we model the hyperlinks graph through node categories: the presence of an arc is fostered or discouraged by the categories of the head and the tail of the arc. Specifically, we determine a latent category matrix that explains common links. The matrix is built using a margin-based online learning algorithm (Passive-Aggressive), which makes us able to process graphs with $10^{8}$ links in less than $10$ minutes. We show that our method provides better accuracy than most existing text-based techniques, with higher efficiency and relying on a much smaller amount of information. It also provides higher precision than standard link prediction, especially at low recall levels; the two methods are in fact shown to be orthogonal to each other and can therefore be fruitfully combined.
Flow- and Context-Sensitive Points-to Analysis using Generalized Points-to Graphs
Venue: arXiv cs.PL 2016
Year: 2016

Computing precise (fully flow-sensitive and context-sensitive) and exhaustive points-to information is computationally expensive. Many practical tools approximate the points-to information trading precision for efficiency. This has adverse impact on computationally intensive analyses such as model checking. Past explorations in top-down approaches of fully flow- and context-sensitive points-to analysis (FCPA) have not scaled. We explore the alternative of bottom-up interprocedural approach which constructs summary flow functions for procedures to represent the effect of their calls. This approach has been effectively used for many analyses. However, it is computationally expensive for FCPA which requires modelling unknown locations accessed indirectly through pointers. Such accesses are commonly handled by using placeholders to explicate unknown locations or by using multiple call-specific summary flow functions. We generalize the concept of points-to relations by using the counts of indirection levels leaving the unknown locations implicit. This allows us to create summary flow functions in the form of generalized points-to graphs (GPGs) without the need of placeholders. By design, GPGs represent both memory (in terms of classical points-to facts) and memory transformers (in terms of generalized points-to facts). We perform FCPA by progressively reducing generalized points-to facts to classical points-to facts. GPGs distinguish between may and must pointer updates thereby facilitating strong updates within calling contexts. The size of GPG is linearly bounded by the number of variables and is independent of the number of statements in the procedure. Empirical measurements on SPEC benchmarks show that GPGs are indeed compact in spite of large procedure sizes. This allows us to scale FCPA to 158 kLoC using GPGs (compared to 35 kLoC reported by liveness-based FCPA).
Online Optimization with Costly and Noisy Measurements using Random Fourier Expansions
Venue: arXiv cs.LG 2016
Year: 2016

This paper analyzes DONE, an online optimization algorithm that iteratively minimizes an unknown function based on costly and noisy measurements. The algorithm maintains a surrogate of the unknown function in the form of a random Fourier expansion (RFE). The surrogate is updated whenever a new measurement is available, and then used to determine the next measurement point. The algorithm is comparable to Bayesian optimization algorithms, but its computational complexity per iteration does not depend on the number of measurements. We derive several theoretical results that provide insight on how the hyper-parameters of the algorithm should be chosen. The algorithm is compared to a Bayesian optimization algorithm for a benchmark problem and three applications, namely, optical coherence tomography, optical beam-forming network tuning, and robot arm control. It is found that the DONE algorithm is significantly faster than Bayesian optimization in the discussed problems, while achieving a similar or better performance.
Web Toolkit for Scientific Research: State of the Art and the Prospect for Development
Venue: arXiv cs.DC 2016
Year: 2016

The paper examines the current trends in designing of systems for convenient and secure remote job submission to various computer resources, including supercomputers, computer clusters, cloud resources, data storages and databases, and grid infrastructures by authorized users, as well as remote job monitoring and obtaining the results. Currently, high-perfomance computing and storage resources are capable of solving independently the majority of practical problems in the field of science and technology. Therefore, the focus in the development of a new generation of middleware shifts from the global grid systems to building convenient and efficient web platforms for remote access to individual computing resources. The paper examines the general principles of the construction and briefly describes some of the specific implementations of the web platforms.
To Fall Or Not To Fall: A Visual Approach to Physical Stability Prediction
Venue: arXiv cs.CV 2016
Year: 2016

Understanding physical phenomena is a key competence that enables humans and animals to act and interact under uncertain perception in previously unseen environments containing novel object and their configurations. Developmental psychology has shown that such skills are acquired by infants from observations at a very early stage. In this paper, we contrast a more traditional approach of taking a model-based route with explicit 3D representations and physical simulation by an end-to-end approach that directly predicts stability and related quantities from appearance. We ask the question if and to what extent and quality such a skill can directly be acquired in a data-driven way bypassing the need for an explicit simulation. We present a learning-based approach based on simulated data that predicts stability of towers comprised of wooden blocks under different conditions and quantities related to the potential fall of the towers. The evaluation is carried out on synthetic data and compared to human judgments on the same stimuli.
A Compositional Approach to Language Modeling
Venue: arXiv cs.CL 2016
Year: 2016

Traditional language models treat language as a finite state automaton on a probability space over words. This is a very strong assumption when modeling something inherently complex such as language. In this paper, we challenge this by showing how the linear chain assumption inherent in previous work can be translated into a sequential composition tree. We then propose a new model that marginalizes over all possible composition trees thereby removing any underlying structural assumptions. As the partition function of this new model is intractable, we use a recently proposed sentence level evaluation metric Contrastive Entropy to evaluate our model. Given this new evaluation metric, we report more than 100% improvement across distortion levels over current state of the art recurrent neural network based language models.
Computing Join Queries with Functional Dependencies
Venue: arXiv cs.DB 2016
Year: 2016

Recently, Gottlob, Lee, Valiant, and Valiant (GLVV) presented an output size bound for join queries with functional dependencies (FD), based on a linear program on polymatroids. GLVV bound strictly generalizes the bound of Atserias, Grohe and Marx (AGM) for queries with no FD, in which case there are known algorithms running within AGM bound and thus are worst-case optimal. A main result of this paper is an algorithm for computing join queries with FDs, running within GLVV bound up to a poly-log factor. In particular, our algorithm is worst-case optimal for any query where the GLVV bound is tight. As an unexpected by-product, our algorithm manages to solve a harder problem, where (some) input relations may have prescribed maximum degree bounds, of which both functional dependencies and cardinality bounds are special cases. We extend Gottlob et al. framework by replacing all variable subsets with the lattice of closed sets (under the given FDs). This gives us new insights into the structure of the worst-case bound and worst-case instances. While it is still open whether GLVV bound is tight in general, we show that it is tight on distributive lattices and some other simple lattices. Distributive lattices capture a strict superset of queries with no FD and with simple FDs. We also present two simpler algorithms which are also worst-case optimal on distributive lattices within a single-$\log$ factor, but they do not match GLVV bound on a general lattice. Our algorithms are designed based on a novel principle: we turn a proof of a polymatroid-based output size bound into an algorithm.
Verifying Security Policies using Host Attributes
Venue: arXiv cs.CR 2016
Year: 2016

For the formal verification of a network security policy, it is crucial to express the verification goals. These formal goals, called security invariants, should be easy to express for the end user. Focusing on access control and information flow security strategies, this work discovers and proves universal insights about security invariants. This enables secure and convenient auto-completion of host attribute configurations. We demonstrate our results in a civil aviation scenario. All results are machine-verified with the Isabelle/HOL theorem prover.
Semantics-Preserving Simplification of Real-World Firewall Rule Sets
Venue: arXiv cs.CR 2016
Year: 2016

The security provided by a firewall for a computer network almost completely depends on the rules it enforces. For over a decade, it has been a well-known and unsolved problem that the quality of many firewall rule sets is insufficient. Therefore, there are many tools to analyze them. However, we found that none of the available tools could handle typical, real-world iptables rulesets. This is due to the complex chain model used by iptables, but also to the vast amount of possible match conditions that occur in real-world firewalls, many of which are not understood by academic and open source tools. In this paper, we provide algorithms to transform firewall rulesets. We reduce the execution model to a simple list model and use ternary logic to abstract over all unknown match conditions. These transformations enable existing tools to understand real-world firewall rules, which we demonstrate on four decently-sized rulesets. %After preparation with our algorithms, tools could understand them. Using the Isabelle theorem prover, we formally show that all our algorithms preserve the firewall's filtering behavior.
Demonstrating topoS: Theorem-Prover-Based Synthesis of Secure Network Configurations
Venue: arXiv cs.NI 2016
Year: 2016

In network management, when it comes to security breaches, human error constitutes a dominant factor. We present our tool topoS which automatically synthesizes low-level network configurations from high-level security goals. The automation and a feedback loop help to prevent human errors. Except for a last serialization step, topoS is formally verified with Isabelle/HOL, which prevents implementation errors. In a case study, we demonstrate topoS by example. For the first time, the complete transition from high-level security goals to both firewall and SDN configurations is presented.
Joint Resource Allocation for OFDMA based Overlay Cognitive Radio Networks under Stochastic Rate Constraint
Venue: arXiv cs.IT 2016
Year: 2016

This work presents joint subcarrier, power and bit allocation schemes for multi-user OFDM based overlay cognitive radio under constraints on primary user throughput loss and total secondary user transmitted power. Closed form for expressions for the optimal power and bit allocations are initially derived. Subsequently, optimal and suboptimal algorithms to realise the joint subcarrier, power and bit allocations are introduced. Numerical simulations are used to evaluate the performance of the joint resource allocation algorithms.
A Semisupervised Approach for Language Identification based on Ladder Networks
Venue: arXiv cs.CL 2016
Year: 2016

In this study we address the problem of training a neuralnetwork for language identification using both labeled and unlabeled speech samples in the form of i-vectors. We propose a neural network architecture that can also handle out-of-set languages. We utilize a modified version of the recently proposed Ladder Network semisupervised training procedure that optimizes the reconstruction costs of a stack of denoising autoencoders. We show that this approach can be successfully applied to the case where the training dataset is composed of both labeled and unlabeled acoustic data. The results show enhanced language identification on the NIST 2015 language identification dataset.
Incremental Consistency Checking in Delta-oriented UML-Models for Automation Systems
Venue: arXiv cs.SE 2016
Year: 2016

Automation systems exist in many variants and may evolve over time in order to deal with different environment contexts or to fulfill changing customer requirements. This induces an increased complexity during design-time as well as tedious maintenance efforts. We already proposed a multi-perspective modeling approach to improve the development of such systems. It operates on different levels of abstraction by using well-known UML-models with activity, composite structure and state chart models. Each perspective was enriched with delta modeling to manage variability and evolution. As an extension, we now focus on the development of an efficient consistency checking method at several levels to ensure valid variants of the automation system. Consistency checking must be provided for each perspective in isolation, in-between the perspectives as well as after the application of a delta.
Local pinning of networks of multi-agent systems with transmission and pinning delays
Venue: arXiv cs.SY 2016
Year: 2016

We study the stability of networks of multi-agent systems with local pinning strategies and two types of time delays, namely the transmission delay in the network and the pinning delay of the controllers. Sufficient conditions for stability are derived under specific scenarios by computing or estimating the dominant eigenvalue of the characteristic equation. In addition, controlling the network by pinning a single node is studied. Moreover, perturbation methods are employed to derive conditions in the limit of small and large pinning strengths.Numerical algorithms are proposed to verify stability, and simulation examples are presented to confirm the efficiency of analytic results.
Automatic Annotation of Structured Facts in Images
Venue: arXiv cs.CL 2016
Year: 2016

Motivated by the application of fact-level image understanding, we present an automatic method for data collection of structured visual facts from images with captions. Example structured facts include attributed objects (e.g., <flower, red>), actions (e.g., <baby, smile>), interactions (e.g., <man, walking, dog>), and positional information (e.g., <vase, on, table>). The collected annotations are in the form of fact-image pairs (e.g.,<man, walking, dog> and an image region containing this fact). With a language approach, the proposed method is able to collect hundreds of thousands of visual fact annotations with accuracy of 83% according to human judgment. Our method automatically collected more than 380,000 visual fact annotations and more than 110,000 unique visual facts from images with captions and localized them in images in less than one day of processing time on standard CPU platforms.
On the Dual of the Coulter-Matthews Bent Functions
Venue: arXiv cs.IT 2016
Year: 2016

For any bent function, it is very interesting to determine its dual function because the dual function is also bent in certain cases. For $k$ odd and $\gcd(n, k)=1$, it is known that the Coulter-Matthews bent function $f(x)=Tr(ax^{\frac{3^k+1}{2}})$ is weakly regular bent over $\mathbb{F}_{3^n}$, where $a\in\mathbb{F}_{3^n}^{*}$, and $Tr(\cdot):\mathbb{F}_{3^n}\rightarrow\mathbb{F}_3$ is the trace function. In this paper, we investigate the dual function of $f(x)$, and dig out an universal formula. In particular, for two cases, we determine the formula explicitly: for the case of $n=3t+1$ and $k=2t+1$ with $t\geq 2$, the dual function is given by $$Tr\left(-\frac{x^{3^{2t+1}+3^{t+1}+2}}{a^{3^{2t+1}+3^{t+1}+1}}-\frac{x^{3^{2t}+1}}{a^{-3^{2t}+3^{t}+1}}+\frac{x^{2}}{a^{-3^{2t+1}+3^{t+1}+1}}\right);$$ and for the case of $n=3t+2$ and $k=2t+1$ with $t\geq 2$, the dual function is given by $$Tr\left(-\frac{x^{3^{2t+2}+1}}{a^{3^{2t+2}-3^{t+1}+3}}-\frac{x^{2\cdot3^{2t+1}+3^{t+1}+1}}{a^{3^{2t+2}+3^{t+1}+1}}+\frac{x^2}{a^{-3^{2t+2}+3^{t+1}+3}}\right).$$ As a byproduct, we find two new classes of ternary bent functions with only three terms. Moreover, we also prove that in certain cases $f(x)$ is regular bent.
Voronoi Region-Based Adaptive Unsupervised Color Image Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Color image segmentation is a crucial step in many computer vision and pattern recognition applications. This article introduces an adaptive and unsupervised clustering approach based on Voronoi regions, which can be applied to solve the color image segmentation problem. The proposed method performs region splitting and merging within Voronoi regions of the Dirichlet Tessellated image (also called a Voronoi diagram) , which improves the efficiency and the accuracy of the number of clusters and cluster centroids estimation process. Furthermore, the proposed method uses cluster centroid proximity to merge proximal clusters in order to find the final number of clusters and cluster centroids. In contrast to the existing adaptive unsupervised cluster-based image segmentation algorithms, the proposed method uses K-means clustering algorithm in place of the Fuzzy C-means algorithm to find the final segmented image. The proposed method was evaluated on three different unsupervised image segmentation evaluation benchmarks and its results were compared with two other adaptive unsupervised cluster-based image segmentation algorithms. The experimental results reported in this article confirm that the proposed method outperforms the existing algorithms in terms of the quality of image segmentation results. Also, the proposed method results in the lowest average execution time per image compared to the existing methods reported in this article.
Improving SAT Solvers via Blocked Clause Decomposition
Venue: arXiv cs.LO 2016
Year: 2016

The decision variable selection policy used by the most competitive CDCL (Conflict-Driven Clause Learning) SAT solvers is either VSIDS (Variable State Independent Decaying Sum) or its variants such as exponential version EVSIDS. The common characteristic of VSIDS and its variants is to make use of statistical information in the solving process, but ignore structure information of the problem. For this reason, this paper modifies the decision variable selection policy, and presents a SAT solving technique based on BCD (Blocked Clause Decomposition). Its basic idea is that a part of decision variables are selected by VSIDS heuristic, while another part of decision variables are selected by blocked sets that are obtained by BCD. Compared with the existing BCD-based technique, our technique is simple, and need not to reencode CNF formulas. SAT solvers for certified UNSAT track can apply also our BCD-based technique. Our experiments on application benchmarks demonstrate that the new variables selection policy based on BCD can increase the performance of SAT solvers such as abcdSAT. The solver with BCD solved an instance from the SAT Race 2015 that was not solved by any solver so far. This shows that in some cases, the heuristic based on structure information is more efficient than that based on statistical information.
Parametric Study of Nonlinear Adaptive Cruise Control for a Road Vehicle Model by MPC
Venue: arXiv cs.SY 2016
Year: 2016

MPC (Model Predictive Control) techniques, with constraints, are applied to a nonlinear vehicle model for the development of an ACC (Adaptive Cruise Control) system for transitional manoeuvres. The dynamic model of the vehicle is developed in the continuous-time domain and captures the real dynamics of the sub-vehicle models for steady-state and transient operations. A parametric study for the MPC method is conducted to analyse the response of the ACC vehicle for critical manoeuvres. The simulation results show the significant sensitivity of the response of the vehicle model with ACC to controller parameter and comparisons are made with a previous study. Furthermore, the approach adopted in this work is believed to reflect the control actions taken by a real vehicle.