OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic and Auto Responsive Solution for Distributed Denial-of-Service Attacks Detection in ISP Network
Venue: arXiv cs.CR 2012
Year: 2012

Denial of service (DoS) attacks and more particularly the distributed ones (DDoS) are one of the latest threat and pose a grave danger to users, organizations and infrastructures of the Internet. Several schemes have been proposed on how to detect some of these attacks, but they suffer from a range of problems, some of them being impractical and others not being effective against these attacks. This paper reports the design principles and evaluation results of our proposed framework that autonomously detects and accurately characterizes a wide range of flooding DDoS attacks in ISP network. Attacks are detected by the constant monitoring of propagation of abrupt traffic changes inside ISP network. For this, a newly designed flow-volume based approach (FVBA) is used to construct profile of the traffic normally seen in the network, and identify anomalies whenever traffic goes out of profile. Consideration of varying tolerance factors make proposed detection system scalable to the varying network conditions and attack loads in real time. Six-sigma method is used to identify threshold values accurately for malicious flows characterization. FVBA has been extensively evaluated in a controlled test-bed environment. Detection thresholds and efficiency is justified using receiver operating characteristics (ROC) curve. For validation, KDD 99, a publicly available benchmark dataset is used. The results show that our proposed system gives a drastic improvement in terms of detection and false alarm rate.
Locally Most Powerful Invariant Tests for Correlation and Sphericity of Gaussian Vectors
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we study the existence of locally most powerful invariant tests (LMPIT) for the problem of testing the covariance structure of a set of Gaussian random vectors. The LMPIT is the optimal test for the case of close hypotheses, among those satisfying the invariances of the problem, and in practical scenarios can provide better performance than the typically used generalized likelihood ratio test (GLRT). The derivation of the LMPIT usually requires one to find the maximal invariant statistic for the detection problem and then derive its distribution under both hypotheses, which in general is a rather involved procedure. As an alternative, Wijsman's theorem provides the ratio of the maximal invariant densities without even finding an explicit expression for the maximal invariant. We first consider the problem of testing whether a set of $N$-dimensional Gaussian random vectors are uncorrelated or not, and show that the LMPIT is given by the Frobenius norm of the sample coherence matrix. Second, we study the case in which the vectors under the null hypothesis are uncorrelated and identically distributed, that is, the sphericity test for Gaussian vectors, for which we show that the LMPIT is given by the Frobenius norm of a normalized version of the sample covariance matrix. Finally, some numerical examples illustrate the performance of the proposed tests, which provide better results than their GLRT counterparts.
Intelligent Automated Diagnosis of Client Device Bottlenecks in Private Clouds
Venue: arXiv cs.NI 2012
Year: 2012

We present an automated solution for rapid diagnosis of client device problems in private cloud environments: the Intelligent Automated Client Diagnostic (IACD) system. Clients are diagnosed with the aid of Transmission Control Protocol (TCP) packet traces, by (i) observation of anomalous artifacts occurring as a result of each fault and (ii) subsequent use of the inference capabilities of soft-margin Support Vector Machine (SVM) classifiers. The IACD system features a modular design and is extendible to new faults, with detection capability unaffected by the TCP variant used at the client. Experimental evaluation of the IACD system in a controlled environment demonstrated an overall diagnostic accuracy of 98%.
Efficient Generation ε-close to G(n,p) and Generalizations
Venue: arXiv cs.DS 2012
Year: 2012

We give an efficient algorithm to generate a graph from a distribution $ε$-close to $G(n,p)$, in the sense of total variation distance. In particular, if $p$ is represented with $O(\log n)$-bit accuracy, then, with high probability, the running time is linear in the expected number of edges of the output graph (up to poly-logarithmic factors). All our running times include the complexity of the arithmetic involved in the corresponding algorithms. Previous standard methods for exact $G(n,p)$ sampling (see e.g. Batagelj and Brandes, 2005) achieve similar running times, however, under the assumption that performing real number arithmetic with arbitrary accuracy takes constant time. We note that the actual accuracy required by these methods is O(n)-bit per step, which results in quadratic running times. The main idea of our $G(n,p)$ generation algorithm is a Metropolis Markov chain to sample $ε$-close from the binomial distribution. This is a new method for sampling from the binomial distribution: it is of separate interest and may find other useful applications. Our analysis accounts for all necessary bit-accuracy and arithmetic, and our running times are comparable to known methods for exact binomial sampling. We further obtain efficient generation algorithms for random graphs with given arbitrary degree distributions, Inhomogeneous Random Graphs when the kernel function is the inner product, and Stochastic Kronecker Graphs. To the best our knowledge, our work can be viewed as the first effort to simulate efficient generation of graphs from classical random graph models, while taking into account implementational considerations as fundamental computational aspects, and quantifying the tradeoff between accuracy and running time in a way that can be useful in practice.
Context-sensitive Spelling Correction Using Google Web 1T 5-Gram Information
Venue: arXiv cs.CL 2012
Year: 2012

In computing, spell checking is the process of detecting and sometimes providing spelling suggestions for incorrectly spelled words in a text. Basically, a spell checker is a computer program that uses a dictionary of words to perform spell checking. The bigger the dictionary is, the higher is the error detection rate. The fact that spell checkers are based on regular dictionaries, they suffer from data sparseness problem as they cannot capture large vocabulary of words including proper names, domain-specific terms, technical jargons, special acronyms, and terminologies. As a result, they exhibit low error detection rate and often fail to catch major errors in the text. This paper proposes a new context-sensitive spelling correction method for detecting and correcting non-word and real-word errors in digital text documents. The approach hinges around data statistics from Google Web 1T 5-gram data set which consists of a big volume of n-gram word sequences, extracted from the World Wide Web. Fundamentally, the proposed method comprises an error detector that detects misspellings, a candidate spellings generator based on a character 2-gram model that generates correction suggestions, and an error corrector that performs contextual error correction. Experiments conducted on a set of text documents from different domains and containing misspellings, showed an outstanding spelling error correction rate and a drastic reduction of both non-word and real-word errors. In a further study, the proposed algorithm is to be parallelized so as to lower the computational cost of the error detection and correction processes.
Numeration Systems: a Link between Number Theory and Formal Language Theory
Venue: arXiv cs.FL 2012
Year: 2012

We survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies. We do not attempt to be exhaustive but try instead to give some personal interpretations and some research directions. We discuss the notion of numeration systems, recognizable sets of integers and automatic sequences. We briefly sketch some results about transcendence related to the representation of real numbers. We conclude with some applications to combinatorial game theory and verification of infinite-state systems and present a list of open problems.
Quantified Conditional Logics are Fragments of HOL
Venue: arXiv cs.AI 2012
Year: 2012

A semantic embedding of (constant domain) quantified conditional logic in classical higher-order logic is presented.
V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors
Venue: arXiv cs.DB 2012
Year: 2012

This work proposes V-SMART-Join, a scalable MapReduce-based framework for discovering all pairs of similar entities. The V-SMART-Join framework is applicable to sets, multisets, and vectors. V-SMART-Join is motivated by the observed skew in the underlying distributions of Internet traffic, and is a family of 2-stage algorithms, where the first stage computes and joins the partial results, and the second stage computes the similarity exactly for all candidate pairs. The V-SMART-Join algorithms are very efficient and scalable in the number of entities, as well as their cardinalities. They were up to 30 times faster than the state of the art algorithm, VCL, when compared on a real dataset of a small size. We also established the scalability of the proposed algorithms by running them on a dataset of a realistic size, on which VCL never succeeded to finish. Experiments were run using real datasets of IPs and cookies, where each IP is represented as a multiset of cookies, and the goal is to discover similar IPs to identify Internet proxies.
A structured approach to VO reconfigurations through Policies
Venue: arXiv cs.MA 2012
Year: 2012

One of the strength of Virtual Organisations is their ability to dynamically and rapidly adapt in response to changing environmental conditions. Dynamic adaptability has been studied in other system areas as well and system management through policies has crystallized itself as a very prominent solution in system and network administration. However, these areas are often concerned with very low-level technical aspects. Previous work on the APPEL policy language has been aimed at dynamically adapting system behaviour to satisfy end-user demands and - as part of STPOWLA - APPEL was used to adapt workflow instances at runtime. In this paper we explore how the ideas of APPEL and STPOWLA can be extended from workflows to the wider scope of Virtual Organisations. We will use a Travel Booking VO as example.
Strong Backdoors to Bounded Treewidth SAT
Venue: arXiv cs.DS 2012
Year: 2012

There are various approaches to exploiting "hidden structure" in instances of hard combinatorial problems to allow faster algorithms than for general unstructured or random instances. For SAT and its counting version #SAT, hidden structure has been exploited in terms of decomposability and strong backdoor sets. Decomposability can be considered in terms of the treewidth of a graph that is associated with the given CNF formula, for instance by considering clauses and variables as vertices of the graph, and making a variable adjacent with all the clauses it appears in. On the other hand, a strong backdoor set of a CNF formula is a set of variables such that each possible partial assignment to this set moves the formula into a fixed class for which (#)SAT can be solved in polynomial time. In this paper we combine the two above approaches. In particular, we study the algorithmic question of finding a small strong backdoor set into the class W_t of CNF formulas whose associated graphs have treewidth at most t. The main results are positive: (1) There is a cubic-time algorithm that, given a CNF formula F and two constants k,t\ge 0, either finds a strong W_t-backdoor set of size at most 2^k, or concludes that F has no strong W_t-backdoor set of size at most k. (2) There is a cubic-time algorithm that, given a CNF formula F, computes the number of satisfying assignments of F or concludes that sb_t(F)>k, for any pair of constants k,t\ge 0. Here, sb_t(F) denotes the size of a smallest strong W_t-backdoor set of F. The significance of our results lies in the fact that they allow us to exploit algorithmically a hidden structure in formulas that is not accessible by any one of the two approaches (decomposability, backdoors) alone. Already a backdoor size 1 on top of treewidth 1 (i.e., sb_1(F)=1) entails formulas of arbitrarily large treewidth and arbitrarily large cycle cutsets.
Revisiting the D-iteration method: runtime comparison
Venue: arXiv cs.NA 2012
Year: 2012

In this paper, we revisit the D-iteration algorithm in order to better explain different performance results that were observed for the numerical computation of the eigenvector associated to the PageRank score. We revisit here the practical computation cost based on the execution runtime compared to the theoretical number of iterations.
Where First-Order and Monadic Second-Order Logic Coincide
Venue: arXiv cs.LO 2012
Year: 2012

We study on which classes of graphs first-order logic (FO) and monadic second-order logic (MSO) have the same expressive power. We show that for all classes C of graphs that are closed under taking subgraphs, FO and MSO have the same expressive power on C if, and only if, C has bounded tree depth. Tree depth is a graph invariant that measures the similarity of a graph to a star in a similar way that tree width measures the similarity of a graph to a tree. For classes just closed under taking induced subgraphs, we show an analogous result for guarded second-order logic (GSO), the variant of MSO that not only allows quantification over vertex sets but also over edge sets. A key tool in our proof is a Feferman-Vaught-type theorem that is constructive and still works for unbounded partitions.
Model for Predicting End User Web Page Response Time
Venue: arXiv cs.PF 2012
Year: 2012

Perceived responsiveness of a web page is one of the most important and least understood metrics of web page design, and is critical for attracting and maintaining a large audience. Web pages can be designed to meet performance SLAs early in the product lifecycle if there is a way to predict the apparent responsiveness of a particular page layout. Response time of a web page is largely influenced by page layout and various network characteristics. Since the network characteristics vary widely from country to country, accurately modeling and predicting the perceived responsiveness of a web page from the end user's perspective has traditionally proven very difficult. We propose a model for predicting end user web page response time based on web page, network, browser download and browser rendering characteristics. We start by understanding the key parameters that affect perceived response time. We then model each of these parameters individually using experimental tests and statistical techniques. Finally, we demonstrate the effectiveness of this model by conducting an experimental study with Yahoo! web pages in two countries and compare it with 3rd party measurement application.
Catroid: A Mobile Visual Programming System for Children
Venue: arXiv cs.PL 2012
Year: 2012

Catroid is a free and open source visual programming language, programming environment, image manipulation program, and website. Catroid allows casual and first-time users starting from age eight to develop their own animations and games solely using their Android phones or tablets. Catroid also allows to wirelessly control external hardware such as Lego Mindstorms robots via Bluetooth, Bluetooth Arduino boards, as well as Parrot's popular and inexpensive AR.Drone quadcopters via WiFi.
Efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we present randomized algorithms for sorting and convex hull that achieves optimal performance (for speed-up and cache misses) on the multicore model with private cache model. Our algorithms are cache oblivious and generalize the randomized divide and conquer strategy given by Reischuk and Reif and Sen. Although the approach yielded optimal speed-up in the PRAM model, we require additional techniques to optimize cache-misses in an oblivious setting. Under a mild assumption on input and number of processors our algorithm will have optimal time and cache misses with high probability. Although similar results have been obtained recently for sorting, we feel that our approach is simpler and general and we apply it to obtain an optimal parallel algorithm for 3D convex hulls with similar bounds. We also present a simple randomized processor allocation technique without the explicit knowledge of the number of processors that is likely to find additional applications in resource oblivious environments.
Harnessing Folksonomies for Resource Classification
Venue: arXiv cs.DL 2012
Year: 2012

In our daily lives, organizing resources into a set of categories is a common task. Categorization becomes more useful as the collection of resources increases. Large collections of books, movies, and web pages, for instance, are cataloged in libraries, organized in databases and classified in directories, respectively. However, the usual largeness of these collections requires a vast endeavor and an outrageous expense to organize manually. Recent research is moving towards developing automated classifiers that reduce the increasing costs and effort of the task. Little work has been done analyzing the appropriateness of and exploring how to harness the annotations provided by users on social tagging systems as a data source. Users on these systems save resources as bookmarks in a social environment by attaching annotations in the form of tags. It has been shown that these tags facilitate retrieval of resources not only for the annotators themselves but also for the whole community. Likewise, these tags provide meaningful metadata that refers to the content of the resources. In this thesis, we deal with the utilization of these user-provided tags in search of the most accurate classification of resources as compared to expert-driven categorizations. To the best of our knowledge, this is the first research work performing actual classification experiments utilizing social tags. By exploring the characteristics and nature of these systems and the underlying folksonomies, this thesis sheds new light on the way of getting the most out of social tags for the sake of automated resource classification tasks. Therefore, we believe that the contributions in this work are of utmost interest for future researchers in the field, as well as for the scientific community in order to better understand these systems and further utilize the knowledge garnered from social tags.
Parametric annealing: a stochastic search method for human pose tracking
Venue: arXiv cs.CV 2012
Year: 2012

Model based methods to marker-free motion capture have a very high computational overhead that make them unattractive. In this paper we describe a method that improves on existing global optimization techniques to tracking articulated objects. Our method improves on the state-of-the-art Annealed Particle Filter (APF) by reusing samples across annealing layers and by using an adaptive parametric density for diffusion. We compare the proposed method with APF on a scalable problem and study how the two methods scale with the dimensionality, multi-modality and the range of search. Then we perform sensitivity analysis on the parameters of our algorithm and show that it tolerates a wide range of parameter settings. We also show results on tracking human pose from the widely-used Human Eva I dataset. Our results show that the proposed method reduces the tracking error despite using less than 50% of the computational resources as APF. The tracked output also shows a significant qualitative improvement over APF as demonstrated through image and video results.
Escape to Mizar for ATPs
Venue: arXiv cs.LO 2012
Year: 2012

We announce a tool for mapping derivations of the E theorem prover to Mizar proofs. Our mapping complements earlier work that generates problems for automated theorem provers from Mizar inference checking problems. We describe the tool, explain the mapping, and show how we solved some of the difficulties that arise in mapping proofs between different logical formalisms, even when they are based on the same notion of logical consequence, as Mizar and E are (namely, first-order classical logic with identity).
Linear Time Algorithm for Projective Clustering
Venue: arXiv cs.CG 2012
Year: 2012

Projective clustering is a problem with both theoretical and practical importance and has received a great deal of attentions in recent years. Given a set of points $P$ in $\mathbb{R}^{d}$ space, projective clustering is to find a set $\mathbb{F}$ of $k$ lower dimensional $j$-flats so that the average distance (or squared distance) from points in $P$ to their closest flats is minimized. Existing approaches for this problem are mainly based on adaptive/volume sampling or core-sets techniques which suffer from several limitations. In this paper, we present the first uniform random sampling based approach for this challenging problem and achieve linear time solutions for three cases, general projective clustering, regular projective clustering, and $L_τ$ sense projective clustering. For the general projective clustering problem, we show that for any given small numbers $0<γ, ε<1$, our approach first removes $γ|P|$ points as outliers and then determines $k$ $j$-flats to cluster the remaining points into $k$ clusters with an objective value no more than $(1+ε)$ times of the optimal for all points. For regular projective clustering, we demonstrate that when the input points satisfy some reasonable assumption on its input, our approach for the general case can be extended to yield a PTAS for all points. For $L_τ$ sense projective clustering, we show that our techniques for both the general and regular cases can be naturally extended to the $L_τ$ sense projective clustering problem for any $1 \le τ< \infty$. Our results are based on several novel techniques, such as slab partition, $Δ$-rotation, symmetric sampling, and recursive projection, and can be easily implemented for applications.
Robust Distributed Routing in Dynamical Networks with Cascading Failures
Venue: arXiv cs.SY 2012
Year: 2012

Robustness of routing policies for networks is a central problem which is gaining increased attention with a growing awareness to safeguard critical infrastructure networks against natural and man-induced disruptions. Routing under limited information and the possibility of cascades through the network adds serious challenges to this problem. This abstract considers the framework of dynamical networks introduced in our earlier work [1,2], where the network is modeled by a system of ordinary differential equations derived from mass conservation laws on directed acyclic graphs with a single origin-destination pair and a constant inflow at the origin. The rate of change of the particle density on each link of the network equals the difference between the inflow and the outflow on that link. The latter is modeled to depend on the current particle density on that link through a flow function. The novel modeling element in this paper is that every link is assumed to have finite capacity for particle density and that the flow function is modeled to be strictly increasing as density increases from zero up to the maximum density capacity, and is discontinuous at the maximum density capacity, with the flow function value being zero at that point. This feature, in particular, allows for the possibility of spill-backs in our model. In this paper, we present our results on resilience of such networks under distributed routing, towards perturbations that reduce link-wise flow functions.