OpenRaiser/Intern-Atlas huggingface dataset:
On Vulnerabilities, Constraints and Assumptions
Venue: arXiv cs.CR 2005
Year: 2005

This report presents a taxonomy of vulnerabilities created as a part of an effort to develop a framework for deriving verification and validation strategies to assess software security. This taxonomy is grounded in a theoretical model of computing, which establishes the relationship between vulnerabilities, software applications and the computer system resources. This relationship illustrates that a software application is exploited by violating constraints imposed by computer system resources and assumptions made about their usage. In other words, a vulnerability exists in the software application if it allows violation of these constraints and assumptions. The taxonomy classifies these constraints and assumptions. The model also serves as a basis for the classification scheme the taxonomy uses, in which the computer system resources such as, memory, input/output, and cryptographic resources serve as categories and subcategories. Vulnerabilities, which are expressed in the form of constraints and assumptions, are classified according to these categories and subcategories. This taxonomy is both novel and distinctively different from other taxonomies found in the literature.
An Improved Lower Bound to the Number of Neighbors Required for the Asymptotic Connectivity of Ad Hoc Networks
Venue: arXiv cs.NI 2005
Year: 2005

Xue and Kumar have established that the number of neighbors required for connectivity of wireless networks with N uniformly distributed nodes must grow as log(N), and they also established that the actual number required lies between 0.074log(N) and 5.1774log(N). In this short paper, by recognizing that connectivity results for networks where the nodes are distributed according to a Poisson point process can often be applied to the problem for a network with N nodes, we are able to improve the lower bound. In particular, we show that a network with nodes distributed in a unit square according to a 2D Poisson point process of parameter N will be asymptotically disconnected with probability one if the number of neighbors is less than 0.129log(N). Moreover, similar number of neighbors is not enough for an asymptotically connected network with N nodes uniformly in a unit square, hence improving the lower bound.
Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs
Venue: arXiv cs.DM 2005
Year: 2005

For digraphs $D$ and $H$, a mapping $f: V(D)\dom V(H)$ is a {\em homomorphism of $D$ to $H$} if $uv\in A(D)$ implies $f(u)f(v)\in A(H).$ For a fixed directed or undirected graph $H$ and an input graph $D$, the problem of verifying whether there exists a homomorphism of $D$ to $H$ has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced very recently by the authors and M. Tso. Suppose we are given a pair of digraphs $D,H$ and a positive integral cost $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$. The cost of a homomorphism $f$ of $D$ to $H$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. Let $H$ be a fixed digraph. The minimum cost homomorphism problem for $H$, MinHOMP($H$), is stated as follows: For input digraph $D$ and costs $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$, verify whether there is a homomorphism of $D$ to $H$ and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of \MiP for $H$ being a semicomplete digraph. In this paper we extend the classification to semicomplete $k$-partite digraphs, $k\ge 3$, and obtain such a classification for bipartite tournaments.
On the Outage Capacity of Correlated Multiple-Path MIMO Channels
Venue: arXiv cs.IT 2005
Year: 2005

The use of multi-antenna arrays in both transmission and reception has been shown to dramatically increase the throughput of wireless communication systems. As a result there has been considerable interest in characterizing the ergodic average of the mutual information for realistic correlated channels. Here, an approach is presented that provides analytic expressions not only for the average, but also the higher cumulant moments of the distribution of the mutual information for zero-mean Gaussian (multiple-input multiple-output) MIMO channels with the most general multipath covariance matrices when the channel is known at the receiver. These channels include multi-tap delay paths, as well as general channels with covariance matrices that cannot be written as a Kronecker product, such as dual-polarized antenna arrays with general correlations at both transmitter and receiver ends. The mathematical methods are formally valid for large antenna numbers, in which limit it is shown that all higher cumulant moments of the distribution, other than the first two scale to zero. Thus, it is confirmed that the distribution of the mutual information tends to a Gaussian, which enables one to calculate the outage capacity. These results are quite accurate even in the case of a few antennas, which makes this approach applicable to realistic situations.
Leveraging Social-Network Infrastructure to Improve Peer-to-Peer Overlay Performance: Results from Orkut
Venue: arXiv cs.NI 2005
Year: 2005

Application-level peer-to-peer (P2P) network overlays are an emerging paradigm that facilitates decentralization and flexibility in the scalable deployment of applications such as group communication, content delivery, and data sharing. However the construction of the overlay graph topology optimized for low latency, low link and node stress and lookup performance is still an open problem. We present a design of an overlay constructed on top of a social network and show that it gives a sizable improvement in lookups, average round-trip delay and scalability as opposed to other overlay topologies. We build our overlay on top of the topology of a popular real-world social network namely Orkut. We show Orkuts suitability for our purposes by evaluating the clustering behavior of its graph structure and the socializing pattern of its members.
Distance-2 Edge Coloring is NP-Complete
Venue: arXiv cs.DM 2005
Year: 2005

We prove that it is NP-complete to determine whether there exists a distance-2 edge coloring (strong edge coloring) with 5 colors of a bipartite 2-inductive graph with girth 6 and maximum degree 3.
On relating CTL to Datalog
Venue: arXiv cs.LO 2005
Year: 2005

CTL is the dominant temporal specification language in practice mainly due to the fact that it admits model checking in linear time. Logic programming and the database query language Datalog are often used as an implementation platform for logic languages. In this paper we present the exact relation between CTL and Datalog and moreover we build on this relation and known efficient algorithms for CTL to obtain efficient algorithms for fragments of stratified Datalog. The contributions of this paper are: a) We embed CTL into STD which is a proper fragment of stratified Datalog. Moreover we show that STD expresses exactly CTL -- we prove that by embedding STD into CTL. Both embeddings are linear. b) CTL can also be embedded to fragments of Datalog without negation. We define a fragment of Datalog with the successor build-in predicate that we call TDS and we embed CTL into TDS in linear time. We build on the above relations to answer open problems of stratified Datalog. We prove that query evaluation is linear and that containment and satisfiability problems are both decidable. The results presented in this paper are the first for fragments of stratified Datalog that are more general than those containing only unary EDBs.
Word sense disambiguation criteria: a systematic study
Venue: arXiv cs.CL 2005
Year: 2005

This article describes the results of a systematic in-depth study of the criteria used for word sense disambiguation. Our study is based on 60 target words: 20 nouns, 20 adjectives and 20 verbs. Our results are not always in line with some practices in the field. For example, we show that omitting non-content words decreases performance and that bigrams yield better results than unigrams.
Computing Pure Nash Equilibria via Markov Random Fields
Venue: arXiv cs.GT 2005
Year: 2005

In this paper we present a novel generic mapping between Graphical Games and Markov Random Fields so that pure Nash equilibria in the former can be found by statistical inference on the latter. Thus, the problem of deciding whether a graphical game has a pure Nash equilibrium, a well-known intractable problem, can be attacked by well-established algorithms such as Belief Propagation, Junction Trees, Markov Chain Monte Carlo and Simulated Annealing. Large classes of graphical games become thus tractable, including all classes already known, but also new classes such as the games with O(log n) treewidth.
Nonmonotonic Trust Management for P2P Applications
Venue: arXiv cs.LO 2005
Year: 2005

Community decisions about access control in virtual communities are non-monotonic in nature. This means that they cannot be expressed in current, monotonic trust management languages such as the family of Role Based Trust Management languages (RT). To solve this problem we propose RT-, which adds a restricted form of negation to the standard RT language, thus admitting a controlled form of non-monotonicity. The semantics of RT- is discussed and presented in terms of the well-founded semantics for Logic Programs. Finally we discuss how chain discovery can be accomplished for RT-.
On the Spread of Random Interleaver
Venue: arXiv cs.IT 2005
Year: 2005

For a given blocklength we determine the number of interleavers which have spread equal to two. Using this, we find out the probability that a randomly chosen interleaver has spread two. We show that as blocklength increases, this probability increases but very quickly converges to the value $1-e^{-2} \approx 0.8647$. Subsequently, we determine a lower bound on the probability of an interleaver having spread at least $s$. We show that this lower bound converges to the value $e^{-2(s-2)^{2}}$, as the blocklength increases.
A Simple Cooperative Diversity Method Based on Network Path Selection
Venue: arXiv cs.IT 2005
Year: 2005

Cooperative diversity has been recently proposed as a way to form virtual antenna arrays that provide dramatic gains in slow fading wireless environments. However most of the proposed solutions require distributed space-time coding algorithms, the careful design of which is left for future investigation if there is more than one cooperative relay. We propose a novel scheme, that alleviates these problems and provides diversity gains on the order of the number of relays in the network. Our scheme first selects the best relay from a set of M available relays and then uses this best relay for cooperation between the source and the destination. We develop and analyze a distributed method to select the best relay that requires no topology information and is based on local measurements of the instantaneous channel conditions. This method also requires no explicit communication among the relays. The success (or failure) to select the best available path depends on the statistics of the wireless channel, and a methodology to evaluate performance for any kind of wireless channel statistics, is provided. Information theoretic analysis of outage probability shows that our scheme achieves the same diversity-multiplexing tradeoff as achieved by more complex protocols, where coordination and distributed space-time coding for M nodes is required, such as those proposed in [7]. The simplicity of the technique, allows for immediate implementation in existing radio hardware and its adoption could provide for improved flexibility, reliability and efficiency in future 4G wireless systems.
On-Off Frequency-Shift-Keying for Wideband Fading Channels
Venue: arXiv cs.IT 2005
Year: 2005

M-ary On-Off Frequency-Shift-Keying (OOFSK) is a digital modulation format in which M-ary FSK signaling is overlaid on On/Off keying. This paper investigates the potential of this modulation format in the context of wideband fading channels. First it is assumed that the receiver uses energy detection for the reception of OOFSK signals. Capacity expressions are obtained for the cases in which the receiver has perfect and imperfect fading side information. Power efficiency is investigated when the transmitter is subject to a peak-to-average power ratio (PAR) limitation or a peak power limitation. It is shown that under a PAR limitation, it is extremely power inefficient to operate in the very low SNR regime. On the other hand, if there is only a peak power limitation, it is demonstrated that power efficiency improves as one operates with smaller SNR and vanishing duty factor. Also studied are the capacity improvements that accrue when the receiver can track phase shifts in the channel or if the received signal has a specular component. To take advantage of those features, the phase of the modulation is also allowed to carry information.
Réflexions sur la question fréquentielle en traitement du signal
Venue: arXiv cs.CE 2005
Year: 2005

New definitions are suggested for frequencies which may be instantaneous or not. The Heisenberg-Gabor inequality and the Shannon sampling theorem are briefly discussed.
Mismatched codebooks and the role of entropy-coding in lossy data compression
Venue: arXiv cs.IT 2005
Year: 2005

We introduce a universal quantization scheme based on random coding, and we analyze its performance. This scheme consists of a source-independent random codebook (typically_mismatched_ to the source distribution), followed by optimal entropy-coding that is_matched_ to the quantized codeword distribution. A single-letter formula is derived for the rate achieved by this scheme at a given distortion, in the limit of large codebook dimension. The rate reduction due to entropy-coding is quantified, and it is shown that it can be arbitrarily large. In the special case of "almost uniform" codebooks (e.g., an i.i.d. Gaussian codebook with large variance) and difference distortion measures, a novel connection is drawn between the compression achieved by the present scheme and the performance of "universal" entropy-coded dithered lattice quantizers. This connection generalizes the "half-a-bit" bound on the redundancy of dithered lattice quantizers. Moreover, it demonstrates a strong notion of universality where a single "almost uniform" codebook is near-optimal for_any_ source and_any_ difference distortion measure.
A Survey of Virtualization Techniques Focusing on Secure On-Demand Cluster Computing
Venue: arXiv cs.OS 2005
Year: 2005

Virtualization, a technique once used to multiplex the resources of high-priced mainframe hardware, is seeing a resurgence in applicability with the increasing computing power of commodity computers. By inserting a layer of software between the machine and traditional operating systems, this technology allows access to a shared computing medium in a manner that is secure, resource-controlled, and efficient. These properties are attractive in the field of on-demand computing, where the fine-grained subdivision of resources provided by virtualized systems allows potentially higher utilization of computing resources. It this work, we survey a number of virtual machine systems with the goal of finding an appropriate candidate to serve as the basis for the On-Demand Secure Cluster Computing project at the National Center for Supercomputing Applications. Contenders are reviewed on a number of desirable properties including portability and security. We conclude with a comparison and justification of our choice.
K-ANMI: A Mutual Information Based Clustering Algorithm for Categorical Data
Venue: arXiv cs.AI 2005
Year: 2005

Clustering categorical data is an integral part of data mining and has attracted much attention recently. In this paper, we present k-ANMI, a new efficient algorithm for clustering categorical data. The k-ANMI algorithm works in a way that is similar to the popular k-means algorithm, and the goodness of clustering in each step is evaluated using a mutual information based criterion (namely, Average Normalized Mutual Information-ANMI) borrowed from cluster ensemble. Experimental results on real datasets show that k-ANMI algorithm is competitive with those state-of-art categorical data clustering algorithms with respect to clustering accuracy.
Games of fixed rank: A hierarchy of bimatrix games
Venue: arXiv cs.GT 2005
Year: 2005

We propose a new hierarchical approach to understand the complexity of the open problem of computing a Nash equilibrium in a bimatrix game. Specifically, we investigate a hierarchy of bimatrix games $(A,B)$ which results from restricting the rank of the matrix $A+B$ to be of fixed rank at most $k$. For every fixed $k$, this class strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We show that even for $k=1$ the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we can provide polynomial time algorithms for finding an $ε$-approximation.
Does a Plane Imitate a Bird? Does Computer Vision Have to Follow Biological Paradigms?
Venue: arXiv cs.NE 2005
Year: 2005

We posit a new paradigm for image information processing. For the last 25 years, this task was usually approached in the frame of Treisman's two-stage paradigm [1]. The latter supposes an unsupervised, bottom-up directed process of preliminary information pieces gathering at the lower processing stages and a supervised, top-down directed process of information pieces binding and grouping at the higher stages. It is acknowledged that these sub-processes interact and intervene between them in a tricky and a complicated manner. Notwithstanding the prevalence of this paradigm in biological and computer vision, we nevertheless propose to replace it with a new one, which we would like to designate as a two-part paradigm. In it, information contained in an image is initially extracted in an independent top-down manner by one part of the system, and then it is examined and interpreted by another, separate system part. We argue that the new paradigm seems to be more plausible than its forerunner. We provide evidence from human attention vision studies and insights of Kolmogorov's complexity theory to support our arguments. We also provide some reasons in favor of separate image interpretation issues.
Logic Column 14: Nominal Logic and Abstract Syntax
Venue: arXiv cs.LO 2005
Year: 2005

Formalizing syntactic proofs of properties of logics, programming languages, security protocols, and other formal systems is a significant challenge, in large part because of the obligation to handle name-binding correctly. We present an approach called nominal abstract syntax that has attracted considerable interest since its introduction approximately six years ago. After an overview of other approaches, we describe nominal abstract syntax and nominal logic, a logic for reasoning about nominal abstract syntax. We also discuss applications of nominal techniques to programming, automated reasoning, and identify some future directions.
Spatiotemporal sensistivity and visual attention for efficient rendering of dynamic environments
Venue: arXiv cs.GR 2005
Year: 2005

We present a method to accelerate global illumination computation in dynamic environments by taking advantage of limitations of the human visual system. A model of visual attention is used to locate regions of interest in a scene and to modulate spatiotemporal sensitivity. The method is applied in the form of a spatiotemporal error tolerance map. Perceptual acceleration combined with good sampling protocols provide a global illumination solution feasible for use in animation. Results indicate an order of magnitude improvement in computational speed. The method is adaptable and can also be used in image-based rendering, geometry level of detail selection, realistic image synthesis, video telephony and video compression.
Design and Analysis of Nonbinary LDPC Codes for Arbitrary Discrete-Memoryless Channels
Venue: arXiv cs.IT 2005
Year: 2005

We present an analysis, under iterative decoding, of coset LDPC codes over GF(q), designed for use over arbitrary discrete-memoryless channels (particularly nonbinary and asymmetric channels). We use a random-coset analysis to produce an effect that is similar to output-symmetry with binary channels. We show that the random selection of the nonzero elements of the GF(q) parity-check matrix induces a permutation-invariance property on the densities of the decoder messages, which simplifies their analysis and approximation. We generalize several properties, including symmetry and stability from the analysis of binary LDPC codes. We show that under a Gaussian approximation, the entire q-1 dimensional distribution of the vector messages is described by a single scalar parameter (like the distributions of binary LDPC messages). We apply this property to develop EXIT charts for our codes. We use appropriately designed signal constellations to obtain substantial shaping gains. Simulation results indicate that our codes outperform multilevel codes at short block lengths. We also present simulation results for the AWGN channel, including results within 0.56 dB of the unconstrained Shannon limit (i.e. not restricted to any signal constellation) at a spectral efficiency of 6 bits/s/Hz.
Logic Programming with Default, Weak and Strict Negations
Venue: arXiv cs.LO 2005
Year: 2005

This paper treats logic programming with three kinds of negation: default, weak and strict negations. A 3-valued logic model theory is discussed for logic programs with three kinds of negation. The procedure is constructed for negations so that a soundness of the procedure is guaranteed in terms of 3-valued logic model theory.
Dimensions of Neural-symbolic Integration - A Structured Survey
Venue: arXiv cs.AI 2005
Year: 2005

Research on integrated neural-symbolic systems has made significant progress in the recent past. In particular the understanding of ways to deal with symbolic knowledge within connectionist systems (also called artificial neural networks) has reached a critical mass which enables the community to strive for applicable implementations and use cases. Recent work has covered a great variety of logics used in artificial intelligence and provides a multitude of techniques for dealing with them within the context of artificial neural networks. We present a comprehensive survey of the field of neural-symbolic integration, including a new classification of system according to their architectures and abilities.
Joint Network-Source Coding: An Achievable Region with Diversity Routing
Venue: arXiv cs.IT 2005
Year: 2005

We are interested in how to best communicate a (usually real valued) source to a number of destinations (sinks) over a network with capacity constraints in a collective fidelity metric over all the sinks, a problem which we call joint network-source coding. Unlike the lossless network coding problem, lossy reconstruction of the source at the sinks is permitted. We make a first attempt to characterize the set of all distortions achievable by a set of sinks in a given network. While the entire region of all achievable distortions remains largely an open problem, we find a large, non-trivial subset of it using ideas in multiple description coding. The achievable region is derived over all balanced multiple-description codes and over all network flows, while the network nodes are allowed to forward and duplicate data packets.
The Private Key Capacity Region for Three Terminals
Venue: arXiv cs.IT 2005
Year: 2005

We consider a model with three terminals and examine the problem of characterizing the largest rates at which two pairs of terminals can simultaneously generate private keys, each of which is effectively concealed from the remaining terminal.