OpenRaiser/Intern-Atlas huggingface dataset:
Malicious Code Execution Detection and Response Immune System inspired by the Danger Theory
Venue: arXiv cs.AI 2010
Year: 2010

The analysis of system calls is one method employed by anomaly detection systems to recognise malicious code execution. Similarities can be drawn between this process and the behaviour of certain cells belonging to the human immune system, and can be applied to construct an artificial immune system. A recently developed hypothesis in immunology, the Danger Theory, states that our immune system responds to the presence of intruders through sensing molecules belonging to those invaders, plus signals generated by the host indicating danger and damage. We propose the incorporation of this concept into a responsive intrusion detection system, where behavioural information of the system and running processes is combined with information regarding individual system calls.
Mathematical Foundations for a Compositional Distributional Model of Meaning
Venue: arXiv cs.CL 2010
Year: 2010

We propose a mathematical framework for a unification of the distributional theory of meaning in terms of vector space models, and a compositional theory for grammatical types, for which we rely on the algebra of Pregroups, introduced by Lambek. This mathematical framework enables us to compute the meaning of a well-typed sentence from the meanings of its constituents. Concretely, the type reductions of Pregroups are `lifted' to morphisms in a category, a procedure that transforms meanings of constituents into a meaning of the (well-typed) whole. Importantly, meanings of whole sentences live in a single space, independent of the grammatical structure of the sentence. Hence the inner-product can be used to compare meanings of arbitrary sentences, as it is for comparing the meanings of words in the distributional model. The mathematical structure we employ admits a purely diagrammatic calculus which exposes how the information flows between the words in a sentence in order to make up the meaning of the whole sentence. A variation of our `categorical model' which involves constraining the scalars of the vector spaces to the semiring of Booleans results in a Montague-style Boolean-valued semantics.
Involutive Categories and Monoids, with a GNS-correspondence
Venue: arXiv cs.LO 2010
Year: 2010

This paper develops the basics of the theory of involutive categories and shows that such categories provide the natural setting in which to describe involutive monoids. It is shown how categories of Eilenberg-Moore algebras of involutive monads are involutive, with conjugation for modules and vector spaces as special case. The core of the so-called Gelfand-Naimark-Segal (GNS) construction is identified as a bijective correspondence between states on involutive monoids and inner products. This correspondence exists in arbritrary involutive categories.
Efficient Construction, Update and Downdate Of The Coefficients Of Interpolants Based On Polynomials Satisfying A Three-Term Recurrence Relation
Venue: arXiv cs.NA 2010
Year: 2010

In this paper, we consider methods to compute the coefficients of interpolants relative to a basis of polynomials satisfying a three-term recurrence relation. Two new algorithms are presented: the first constructs the coefficients of the interpolation incrementally and can be used to update the coefficients whenever a nodes is added to or removed from the interpolation. The second algorithm, which constructs the interpolation coefficients by decomposing the Vandermonde-like matrix iteratively, can not be used to update or downdate an interpolation, yet is more numerically stable than the first algorithm and is more efficient when the coefficients of multiple interpolations are to be computed over the same set of nodes.
Verifying Temporal Regular Properties of Abstractions of Term Rewriting Systems
Venue: arXiv cs.LO 2010
Year: 2010

The tree automaton completion is an algorithm used for proving safety properties of systems that can be modeled by a term rewriting system. This representation and verification technique works well for proving properties of infinite systems like cryptographic protocols or more recently on Java Bytecode programs. This algorithm computes a tree automaton which represents a (regular) over approximation of the set of reachable terms by rewriting initial terms. This approach is limited by the lack of information about rewriting relation between terms. Actually, terms in relation by rewriting are in the same equivalence class: there are recognized by the same state in the tree automaton. Our objective is to produce an automaton embedding an abstraction of the rewriting relation sufficient to prove temporal properties of the term rewriting system. We propose to extend the algorithm to produce an automaton having more equivalence classes to distinguish a term or a subterm from its successors w.r.t. rewriting. While ground transitions are used to recognize equivalence classes of terms, epsilon-transitions represent the rewriting relation between terms. From the completed automaton, it is possible to automatically build a Kripke structure abstracting the rewriting sequence. States of the Kripke structure are states of the tree automaton and the transition relation is given by the set of epsilon-transitions. States of the Kripke structure are labelled by the set of terms recognized using ground transitions. On this Kripke structure, we define the Regular Linear Temporal Logic (R-LTL) for expressing properties. Such properties can then be checked using standard model checking algorithms. The only difference between LTL and R-LTL is that predicates are replaced by regular sets of acceptable terms.
Bisimulation Relations Between Automata, Stochastic Differential Equations and Petri Nets
Venue: arXiv cs.LO 2010
Year: 2010

Two formal stochastic models are said to be bisimilar if their solutions as a stochastic process are probabilistically equivalent. Bisimilarity between two stochastic model formalisms means that the strengths of one stochastic model formalism can be used by the other stochastic model formalism. The aim of this paper is to explain bisimilarity relations between stochastic hybrid automata, stochastic differential equations on hybrid space and stochastic hybrid Petri nets. These bisimilarity relations make it possible to combine the formal verification power of automata with the analysis power of stochastic differential equations and the compositional specification power of Petri nets. The relations and their combined strengths are illustrated for an air traffic example.
Tuple-based abstract data types: full parallelism
Venue: arXiv cs.DB 2010
Year: 2010

Commutativity has the same inherent limitations as compatibility. Then, it is worth conceiving simple concurrency control techniques. We propose a restricted form of commutativity which increases parallelism without incurring a higher overhead than compatibility. Advantages of our proposition are: (1) commutativity of operations is determined at compile-time, (2) run-time checking is as efficient as for compatibility, (3) neither commutativity relations, (4) nor inverse operations, need to be specified, and (5) log space utilization is reduced.
Doubly Perfect Nonlinear Boolean Permutations
Venue: arXiv cs.DM 2010
Year: 2010

Due to implementation constraints the XOR operation is widely used in order to combine plaintext and key bit-strings in secret-key block ciphers. This choice directly induces the classical version of the differential attack by the use of XOR-kind differences. While very natural, there are many alternatives to the XOR. Each of them inducing a new form for its corresponding differential attack (using the appropriate notion of difference) and therefore block-ciphers need to use S-boxes that are resistant against these nonstandard differential cryptanalysis. In this contribution we study the functions that offer the best resistance against a differential attack based on a finite field multiplication. We also show that in some particular cases, there are robust permutations which offers the best resistant against both multiplication and exponentiation base differential attacks. We call them doubly perfect nonlinear permutations.
Common Frame of reference in collaborative virtual environments and their impact on presence
Venue: arXiv cs.HC 2010
Year: 2010

Virtual collaborative environment are 3D shared spaces in which people can work together. To collaborate through these systems, users must have a shared comprehension of the environment. The objective of this experimental study was to determine if visual stable landmarks improve the construction of a common representation of the virtual environment and thus facilitate collaboration. This seems to increase the awareness of the partner's presence.
Transparent Anonymization: Thwarting Adversaries Who Know the Algorithm
Venue: arXiv cs.DB 2010
Year: 2010

Numerous generalization techniques have been proposed for privacy preserving data publishing. Most existing techniques, however, implicitly assume that the adversary knows little about the anonymization algorithm adopted by the data publisher. Consequently, they cannot guard against privacy attacks that exploit various characteristics of the anonymization mechanism. This paper provides a practical solution to the above problem. First, we propose an analytical model for evaluating disclosure risks, when an adversary knows everything in the anonymization process, except the sensitive values. Based on this model, we develop a privacy principle, transparent l-diversity, which ensures privacy protection against such powerful adversaries. We identify three algorithms that achieve transparent l-diversity, and verify their effectiveness and efficiency through extensive experiments with real data.
LEXSYS: Architecture and Implication for Intelligent Agent systems
Venue: arXiv cs.AI 2010
Year: 2010

LEXSYS, (Legume Expert System) was a project conceived at IITA (International Institute of Tropical Agriculture) Ibadan Nigeria. It was initiated by the COMBS (Collaborative Group on Maize-Based Systems Research in the 1990. It was meant for a general framework for characterizing on-farm testing for technology design for sustainable cereal-based cropping system. LEXSYS is not a true expert system as the name would imply, but simply a user-friendly information system. This work is an attempt to give a formal representation of the existing system and then present areas where intelligent agent can be applied.
Lazy Evaluation and Delimited Control
Venue: arXiv cs.PL 2010
Year: 2010

The call-by-need lambda calculus provides an equational framework for reasoning syntactically about lazy evaluation. This paper examines its operational characteristics. By a series of reasoning steps, we systematically unpack the standard-order reduction relation of the calculus and discover a novel abstract machine definition which, like the calculus, goes "under lambdas." We prove that machine evaluation is equivalent to standard-order evaluation. Unlike traditional abstract machines, delimited control plays a significant role in the machine's behavior. In particular, the machine replaces the manipulation of a heap using store-based effects with disciplined management of the evaluation stack using control-based effects. In short, state is replaced with control. To further articulate this observation, we present a simulation of call-by-need in a call-by-value language using delimited control operations.
Determinating Timing Channels in Compute Clouds
Venue: arXiv cs.OS 2010
Year: 2010

Timing side-channels represent an insidious security challenge for cloud computing, because: (a) massive parallelism in the cloud makes timing channels pervasive and hard to control; (b) timing channels enable one customer to steal information from another without leaving a trail or raising alarms; (c) only the cloud provider can feasibly detect and report such attacks, but the provider's incentives are not to; and (d) resource partitioning schemes for timing channel control undermine statistical sharing efficiency, and, with it, the cloud computing business model. We propose a new approach to timing channel control, using provider-enforced deterministic execution instead of resource partitioning to eliminate timing channels within a shared cloud domain. Provider-enforced determinism prevents execution timing from affecting the results of a compute task, however large or parallel, ensuring that a task's outputs leak no timing information apart from explicit timing inputs and total compute duration. Experiments with a prototype OS for deterministic cloud computing suggest that such an approach may be practical and efficient. The OS supports deterministic versions of familiar APIs such as processes, threads, shared memory, and file systems, and runs coarse-grained parallel tasks as efficiently and scalably as current timing channel-ridden systems.
On the Interplay between Incentive Compatibility and Envy Freeness
Venue: arXiv cs.GT 2010
Year: 2010

We study mechanisms for an allocation of goods among agents, where agents have no incentive to lie about their true values (incentive compatible) and for which no agent will seek to exchange outcomes with another (envy-free). Mechanisms satisfying each requirement separately have been studied extensively, but there are few results on mechanisms achieving both. We are interested in those allocations for which there exist payments such that the resulting mechanism is simultaneously incentive compatible and envy-free. Cyclic monotonicity is a characterization of incentive compatible allocations, local efficiency is a characterization for envy-free allocations. We combine the above to give a characterization for allocations which are both incentive compatible and envy free. We show that even for allocations that allow payments leading to incentive compatible mechanisms, and other payments leading to envy free mechanisms, there may not exist any payments for which the mechanism is simultaneously incentive compatible and envy-free. The characterization that we give lets us compute the set of Pareto-optimal mechanisms that trade off envy freeness for incentive compatibility.
Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem
Venue: arXiv cs.DS 2010
Year: 2010

The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper we discuss possible adaptations of TSP heuristics for the Generalized Traveling Salesman Problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search.
Bounds for the Sum Capacity of Binary CDMA Systems in Presence of Near-Far Effect
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we are going to estimate the sum capacity of a binary CDMA system in presence of the near-far effect. We model the near-far effect as a random variable that is multiplied by the users binary data before entering the noisy channel. We will find a lower bound and a conjectured upper bound for the sum capacity in this situation. All the derivations are in the asymptotic case. Simulations show that especially the lower bound is very tight for typical values Eb/N0 and near-far effect. Also, we exploit our idea in conjunction with the Tanaka's formula [6] which also estimates the sum capacity of binary CDMA systems with perfect power control.
Image Compression and Watermarking scheme using Scalar Quantization
Venue: arXiv cs.CV 2010
Year: 2010

This paper presents a new compression technique and image watermarking algorithm based on Contourlet Transform (CT). For image compression, an energy based quantization is used. Scalar quantization is explored for image watermarking. Double filter bank structure is used in CT. The Laplacian Pyramid (LP) is used to capture the point discontinuities, and then followed by a Directional Filter Bank (DFB) to link point discontinuities. The coefficients of down sampled low pass version of LP decomposed image are re-ordered in a pre-determined manner and prediction algorithm is used to reduce entropy (bits/pixel). In addition, the coefficients of CT are quantized based on the energy in the particular band. The superiority of proposed algorithm to JPEG is observed in terms of reduced blocking artifacts. The results are also compared with wavelet transform (WT). Superiority of CT to WT is observed when the image contains more contours. The watermark image is embedded in the low pass image of contourlet decomposition. The watermark can be extracted with minimum error. In terms of PSNR, the visual quality of the watermarked image is exceptional. The proposed algorithm is robust to many image attacks and suitable for copyright protection applications.
A Performance Analysis for UMTS Packet Switched Network Based on Multivariate KPIS
Venue: arXiv cs.NI 2010
Year: 2010

Mobile data services are penetrating mobile markets rapidly. The mobile industry relies heavily on data service to replace the traditional voice services with the evolution of the wireless technology and market. A reliable packet service network is critical to the mobile operators to maintain their core competence in data service market. Furthermore, mobile operators need to develop effective operational models to manage the varying mix of voice, data and video traffic on a single network. Application of statistical models could prove to be an effective approach. This paper first introduces the architecture of Universal Mobile Telecommunications System (UMTS) packet switched (PS) network and then applies multivariate statistical analysis to Key Performance Indicators (KPI) monitored from network entities in UMTS PS network to guide the long term capacity planning for the network. The approach proposed in this paper could be helpful to mobile operators in operating and maintaining their 3G packet switched networks for the long run.
Arithmetic Operations in Multi-Valued Logic
Venue: arXiv cs.OH 2010
Year: 2010

This paper presents arithmetic operations like addition, subtraction and multiplications in Modulo-4 arithmetic, and also addition, multiplication in Galois field, using multi-valued logic (MVL). Quaternary to binary and binary to quaternary converters are designed using down literal circuits. Negation in modular arithmetic is designed with only one gate. Logic design of each operation is achieved by reducing the terms using Karnaugh diagrams, keeping minimum number of gates and depth of net in to consideration. Quaternary multiplier circuit is proposed to achieve required optimization. Simulation result of each operation is shown separately using Hspice.
Truthful Fair Division
Venue: arXiv cs.GT 2010
Year: 2010

We address the problem of fair division, or cake cutting, with the goal of finding truthful mechanisms. In the case of a general measure space ("cake") and non-atomic, additive individual preference measures - or utilities - we show that there exists a truthful "mechanism" which ensures that each of the k players gets at least 1/k of the cake. This mechanism also minimizes risk for truthful players. Furthermore, in the case where there exist at least two different measures we present a different truthful mechanism which ensures that each of the players gets more than 1/k of the cake. We then turn our attention to partitions of indivisible goods with bounded utilities and a large number of goods. Here we provide similar mechanisms, but with slightly weaker guarantees. These guarantees converge to those obtained in the non-atomic case as the number of goods goes to infinity.
Categorical Models for a Semantically Linear Lambda-calculus
Venue: arXiv cs.LO 2010
Year: 2010

This paper is about a categorical approach to model a very simple Semantically Linear lambda calculus, named Sll-calculus. This is a core calculus underlying the programming language SlPCF. In particular, in this work, we introduce the notion of Sll-Category, which is able to describe a very large class of sound models of Sll-calculus. Sll-Category extends in the natural way Benton, Bierman, Hyland and de Paiva's Linear Category, in order to soundly interpret all the constructs of Sll-calculus. This category is general enough to catch interesting models in Scott Domains and Coherence Spaces.
Resource-Bound Quantification for Graph Transformation
Venue: arXiv cs.LO 2010
Year: 2010

Graph transformation has been used to model concurrent systems in software engineering, as well as in biochemistry and life sciences. The application of a transformation rule can be characterised algebraically as construction of a double-pushout (DPO) diagram in the category of graphs. We show how intuitionistic linear logic can be extended with resource-bound quantification, allowing for an implicit handling of the DPO conditions, and how resource logic can be used to reason about graph transformation systems.
An Iteratively Decodable Tensor Product Code with Application to Data Storage
Venue: arXiv cs.IT 2010
Year: 2010

The error pattern correcting code (EPCC) can be constructed to provide a syndrome decoding table targeting the dominant error events of an inter-symbol interference channel at the output of the Viterbi detector. For the size of the syndrome table to be manageable and the list of possible error events to be reasonable in size, the codeword length of EPCC needs to be short enough. However, the rate of such a short length code will be too low for hard drive applications. To accommodate the required large redundancy, it is possible to record only a highly compressed function of the parity bits of EPCC's tensor product with a symbol correcting code. In this paper, we show that the proposed tensor error-pattern correcting code (T-EPCC) is linear time encodable and also devise a low-complexity soft iterative decoding algorithm for EPCC's tensor product with q-ary LDPC (T-EPCC-qLDPC). Simulation results show that T-EPCC-qLDPC achieves almost similar performance to single-level qLDPC with a 1/2 KB sector at 50% reduction in decoding complexity. Moreover, 1 KB T-EPCC-qLDPC surpasses the performance of 1/2 KB single-level qLDPC at the same decoder complexity.
The impact of cell site re-homing on the performance of umts core networks
Venue: arXiv cs.NI 2010
Year: 2010

Mobile operators currently prefer optimizing their radio networks via re-homing or cutting over the cell sites in 2G or 3G networks. The core network, as the parental part of radio network, is inevitably impacted by the re-homing in radio domain. This paper introduces the cell site re-homing in radio network and analyzes its impact on the performance of GSM/UMTS core network. The possible re-homing models are created and analyzed for core networks. The paper concludes that appropriate re-homing in radio domain, using correct algorithms, not only optimizes the radio network but also helps improve the QoS of the core network and saves the carriers' OPEX and CAPEX on their core networks.
Bricks and conjectures of Berge, Fulkerson and Seymour
Venue: arXiv cs.DM 2010
Year: 2010

An $r$-graph is an $r$-regular graph where every odd set of vertices is connected by at least $r$ edges to the rest of the graph. Seymour conjectured that any $r$-graph is $r+1$-edge-colorable, and also that any $r$-graph contains $2r$ perfect matchings such that each edge belongs to two of them. We show that the minimum counter-example to either of these conjectures is a brick. Furthermore we disprove a variant of a conjecture of Fan, Raspaud.