OpenRaiser/Intern-Atlas huggingface dataset:
Attacking an OT-Based Blind Signature Scheme
Venue: arXiv cs.CR 2009
Year: 2009

In this paper, we describe an attack against one of the Oblivious-Transfer-based blind signatures scheme, proposed in [1]. An attacker with a primitive capability of producing specific-range random numbers, while exhibiting a partial MITM behavior, is able to corrupt the communication between the protocol participants. The attack is quite efficient as it leads to a protocol communication corruption and has a sound-minimal computational cost. We propose a solution to fix the security flaw.
Mnesors for automatic control
Venue: arXiv cs.AI 2009
Year: 2009

Mnesors are defined as elements of a semimodule over the min-plus integers. This two-sorted structure is able to merge graduation properties of vectors and idempotent properties of boolean numbers, which makes it appropriate for hybrid systems. We apply it to the control of an inverted pendulum and design a full logical controller, that is, without the usual algebra of real numbers.
Are stable instances easy?
Venue: arXiv cs.CC 2009
Year: 2009

We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then arises whether stable instances of NP--hard problems are easier to solve. In particular, whether there exist algorithms that solve correctly and in polynomial time all sufficiently stable instances of some NP--hard problem. The paper focuses on the Max--Cut problem, for which we show that this is indeed the case.
Representing a P-complete problem by small trellis automata
Venue: arXiv cs.CC 2009
Year: 2009

A restricted case of the Circuit Value Problem known as the Sequential NOR Circuit Value Problem was recently used to obtain very succinct examples of conjunctive grammars, Boolean grammars and language equations representing P-complete languages (Okhotin, http://dx.doi.org/10.1007/978-3-540-74593-8_23 "A simple P-complete problem and its representations by language equations", MCU 2007). In this paper, a new encoding of the same problem is proposed, and a trellis automaton (one-way real-time cellular automaton) with 11 states solving this problem is constructed.
New Choice for Small Universal Devices: Symport/Antiport P Systems
Venue: arXiv cs.CC 2009
Year: 2009

Symport/antiport P systems provide a very simple machinery inspired by corresponding operations in the living cell. It turns out that systems of small descriptional complexity are needed to achieve the universality by these systems. This makes them a good candidate for small universal devices replacing register machines for different simulations, especially when a simulating parallel machinery is involved. This article contains survey of these systems and presents different trade-offs between parameters.
Simplicity via Provability for Universal Prefix-free Turing Machines
Venue: arXiv cs.IT 2009
Year: 2009

Universality is one of the most important ideas in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we review recent results in Algorithmic Information Theory and propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, PA or ZFC. In all cases some, but not all, machines are simple.
Playing With Population Protocols
Venue: arXiv cs.GT 2009
Year: 2009

Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement: A collection of anonymous agents, modeled by finite automata, interact in pairs according to some rules. Predicates on the initial configurations that can be computed by such protocols have been characterized under several hypotheses. We discuss here whether and when the rules of interactions between agents can be seen as a game from game theory. We do so by discussing several basic protocols.
Maximum Error Modeling for Fault-Tolerant Computation using Maximum a posteriori (MAP) Hypothesis
Venue: arXiv cs.IT 2009
Year: 2009

The application of current generation computing machines in safety-centric applications like implantable biomedical chips and automobile safety has immensely increased the need for reviewing the worst-case error behavior of computing devices for fault-tolerant computation. In this work, we propose an exact probabilistic error model that can compute the maximum error over all possible input space in a circuit specific manner and can handle various types of structural dependencies in the circuit. We also provide the worst-case input vector, which has the highest probability to generate an erroneous output, for any given logic circuit. We also present a study of circuit-specific error bounds for fault-tolerant computation in heterogeneous circuits using the maximum error computed for each circuit. We model the error estimation problem as a maximum a posteriori (MAP) estimate, over the joint error probability function of the entire circuit, calculated efficiently through an intelligent search of the entire input space using probabilistic traversal of a binary join tree using Shenoy-Shafer algorithm. We demonstrate this model using MCNC and ISCAS benchmark circuits and validate it using an equivalent HSpice model. Both results yield the same worst-case input vectors and the highest % difference of our error model over HSpice is just 1.23%. We observe that the maximum error probabilities are significantly larger than the average error probabilities, and provides a much tighter error bounds for fault-tolerant computation. We also find that the error estimates depend on the specific circuit structure and the maximum error probabilities are sensitive to the individual gate failure probabilities.
Adaptive Regularization of Ill-Posed Problems: Application to Non-rigid Image Registration
Venue: arXiv cs.CV 2009
Year: 2009

We introduce an adaptive regularization approach. In contrast to conventional Tikhonov regularization, which specifies a fixed regularization operator, we estimate it simultaneously with parameters. From a Bayesian perspective we estimate the prior distribution on parameters assuming that it is close to some given model distribution. We constrain the prior distribution to be a Gauss-Markov random field (GMRF), which allows us to solve for the prior distribution analytically and provides a fast optimization algorithm. We apply our approach to non-rigid image registration to estimate the spatial transformation between two images. Our evaluation shows that the adaptive regularization approach significantly outperforms standard variational methods.
Spreading Code and Widely-Linear Receiver Design: Non-Cooperative Games for Wireless CDMA Networks
Venue: arXiv cs.IT 2009
Year: 2009

The issue of non-cooperative transceiver optimization in the uplink of a multiuser wireless code division multiple access data network with widely-linear detection at the receiver is considered. While previous work in this area has focused on a simple real signal model, in this paper a baseband complex representation of the data is used, so as to properly take into account the I and Q components of the received signal. For the case in which the received signal is improper, a widely-linear reception structure, processing separately the data and their complex conjugates, is considered. Several non-cooperative resource allocation games are considered for this new scenario, and the performance gains granted by the use of widely-linear detection are assessed through theoretical analysis. Numerical results confirm the validity of the theoretical findings, and show that exploiting the improper nature of the data in non-cooperative resource allocation brings remarkable performance improvements in multiuser wireless systems.
Decentralized Traffic Management Strategies for Sensor-Enabled Cars
Venue: arXiv cs.DC 2009
Year: 2009

Traffic Congestions and accidents are major concerns in today's transportation systems. This thesis investigates how to optimize traffic flow on highways, in particular for merging situations such as intersections where a ramp leads onto the highway. In our work, cars are equipped with sensors that can detect distance to neighboring cars, and communicate their velocity and acceleration readings with one another. Sensor-enabled cars can locally exchange sensed information about the traffic and adapt their behavior much earlier than regular cars. We propose proactive algorithms for merging different streams of sensor-enabled cars into a single stream. A proactive merging algorithm decouples the decision point from the actual merging point. Sensor-enabled cars allow us to decide where and when a car merges before it arrives at the actual merging point. This leads to a significant improvement in traffic flow as velocities can be adjusted appropriately. We compare proactive merging algorithms against the conventional priority-based merging algorithm in a controlled simulation environment. Experiment results show that proactive merging algorithms outperform the priority-based merging algorithm in terms of flow and delay.
Defense Strategies Against Modern Botnets
Venue: arXiv cs.CR 2009
Year: 2009

Botnets are networks of compromised computers with malicious code which are remotely controlled and which are used for starting distributed denial of service (DDoS) attacks, sending enormous number of e-mails (SPAM) and other sorts of attacks. Defense against modern Botnets is a real challenge. This paper offers several strategies for defense against Botnets with a list and description of measures and activities which should be carried out in order to establish successful defense. The paper also offers parallel preview of the strategies with their advantages and disadvantages considered in accordance with various criteria.
Threshold Verification Technique for Network Intrusion Detection System
Venue: arXiv cs.CR 2009
Year: 2009

Internet has played a vital role in this modern world, the possibilities and opportunities offered are limitless. Despite all the hype, Internet services are liable to intrusion attack that could tamper the confidentiality and integrity of important information. An attack started with gathering the information of the attack target, this gathering of information activity can be done as either fast or slow attack. The defensive measure network administrator can take to overcome this liability is by introducing Intrusion Detection Systems (IDSs) in their network. IDS have the capabilities to analyze the network traffic and recognize incoming and on-going intrusion. Unfortunately the combination of both modules in real time network traffic slowed down the detection process. In real time network, early detection of fast attack can prevent any further attack and reduce the unauthorized access on the targeted machine. The suitable set of feature selection and the correct threshold value, add an extra advantage for IDS to detect anomalies in the network. Therefore this paper discusses a new technique for selecting static threshold value from a minimum standard features in detecting fast attack from the victim perspective. In order to increase the confidence of the threshold value the result is verified using Statistical Process Control (SPC). The implementation of this approach shows that the threshold selected is suitable for identifying the fast attack in real time.
Energy-Efficient Modulation Design for Reliable Communication in Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we have considered the optimization of the $M$-ary quadrature amplitude modulation (MQAM) constellation size to minimize the bit energy consumption under average bit error rate (BER) constraints. In the computation of the energy expenditure, the circuit, transmission, and retransmission energies are taken into account. A combined log-normal shadowing and Rayleigh fading model is employed to model the wireless channel. The link reliabilities and retransmission probabilities are determined through the outage probabilities under log-normal shadowing effects. Both single-hop and multi-hop transmissions are considered. Through numerical results, the optimal constellation sizes are identified. Several interesting observations with practical implications are made. It is seen that while large constellations are preferred at small transmission distances, constellation size should be decreased as the distance increases. Similar trends are observed in both fixed and variable transmit power scenarios. We have noted that variable power schemes can attain higher energy-efficiencies. The analysis of energy-efficient modulation design is also conducted in multi-hop linear networks. In this case, the modulation size and routing paths are jointly optimized, and the analysis of both the bit energy and delay experienced in the linear network is provided.
Effective Capacity Analysis of Cognitive Radio Channels for Quality of Service Provisioning
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, cognitive transmission under quality of service (QoS) constraints is studied. In the cognitive radio channel model, it is assumed that the secondary transmitter sends the data at two different average power levels, depending on the activity of the primary users, which is determined by channel sensing performed by the secondary users. A state-transition model is constructed for this cognitive transmission channel. Statistical limitations on the buffer lengths are imposed to take into account the QoS constraints. The maximum throughput under these statistical QoS constraints is identified by finding the effective capacity of the cognitive radio channel. This analysis is conducted for fixed-power/fixed-rate, fixed-power/variable-rate, and variable-power/variable-rate transmission schemes under different assumptions on the availability of channel side information (CSI) at the transmitter. The impact upon the effective capacity of several system parameters, including channel sensing duration, detection threshold, detection and false alarm probabilities, QoS parameters, and transmission rates, is investigated. The performances of fixed-rate and variable-rate transmission methods are compared in the presence of QoS limitations. It is shown that variable schemes outperform fixed-rate transmission techniques if the detection probabilities are high. Performance gains through adapting the power and rate are quantified and it is shown that these gains diminish as the QoS limitations become more stringent.
Bayesian Forecasting of WWW Traffic on the Time Varying Poisson Model
Venue: arXiv cs.NI 2009
Year: 2009

Traffic forecasting from past observed traffic data with small calculation complexity is one of important problems for planning of servers and networks. Focusing on World Wide Web (WWW) traffic as fundamental investigation, this paper would deal with Bayesian forecasting of network traffic on the time varying Poisson model from a viewpoint from statistical decision theory. Under this model, we would show that the estimated forecasting value is obtained by simple arithmetic calculation and expresses real WWW traffic well from both theoretical and empirical points of view.
Theoretical Limits on Time Delay Estimation for Ultra-Wideband Cognitive Radios
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, theoretical limits on time delay estimation are studied for ultra-wideband (UWB) cognitive radio systems. For a generic UWB spectrum with dispersed bands, the Cramer-Rao lower bound (CRLB) is derived for unknown channel coefficients and carrier-frequency offsets (CFOs). Then, the effects of unknown channel coefficients and CFOs are investigated for linearly and non-linearly modulated training signals by obtaining specific CRLB expressions. It is shown that for linear modulations with a constant envelope, the effects of the unknown parameters can be mitigated. Finally, numerical results, which support the theoretical analysis, are presented.
Bayesian two-sample tests
Venue: arXiv cs.LG 2009
Year: 2009

In this paper, we present two classes of Bayesian approaches to the two-sample problem. Our first class of methods extends the Bayesian t-test to include all parametric models in the exponential family and their conjugate priors. Our second class of methods uses Dirichlet process mixtures (DPM) of such conjugate-exponential distributions as flexible nonparametric priors over the unknown distributions.
On computing the Hermite form of a matrix of differential polynomials
Venue: arXiv cs.SC 2009
Year: 2009

Given an n x n matrix over the ring of differential polynomials F(t)[\D;δ], we show how to compute the Hermite form H of A, and a unimodular matrix U such that UA=H. The algorithm requires a polynomial number of operations in terms of n, deg_D(A), and deg_t(A). When F is the field of rational numbers, it also requires time polynomial in the bit-length of the coefficients.
Distributed Fault Detection in Sensor Networks using a Recurrent Neural Network
Venue: arXiv cs.NE 2009
Year: 2009

In long-term deployments of sensor networks, monitoring the quality of gathered data is a critical issue. Over the time of deployment, sensors are exposed to harsh conditions, causing some of them to fail or to deliver less accurate data. If such a degradation remains undetected, the usefulness of a sensor network can be greatly reduced. We present an approach that learns spatio-temporal correlations between different sensors, and makes use of the learned model to detect misbehaving sensors by using distributed computation and only local communication between nodes. We introduce SODESN, a distributed recurrent neural network architecture, and a learning method to train SODESN for fault detection in a distributed scenario. Our approach is evaluated using data from different types of sensors and is able to work well even with less-than-perfect link qualities and more than 50% of failed nodes.
A Peer to Peer Protocol for Online Dispute Resolution over Storage Consumption
Venue: arXiv cs.DC 2009
Year: 2009

In bilateral accounting of resource consumption both the consumer and provider independently measure the amount of resources consumed by the consumer. The problem here is that potential disparities between the provider's and consumer's accountings, might lead to conflicts between the two parties that need to be resolved. We argue that with the proper mechanisms available, most of these conflicts can be solved online, as opposite to in court resolution; the design of such mechanisms is still a research topic; to help cover the gap, in this paper we propose a peer--to--peer protocol for online dispute resolution over storage consumption. The protocol is peer--to--peer and takes into consideration the possible causes (e.g, transmission delays, unsynchronized metric collectors, etc.) of the disparity between the provider's and consumer's accountings to make, if possible, the two results converge.
A Novel Bid Optimizer for Sponsored Search Auctions based on Cooperative Game Theory
Venue: arXiv cs.GT 2009
Year: 2009

In this paper, we propose a bid optimizer for sponsored keyword search auctions which leads to better retention of advertisers by yielding attractive utilities to the advertisers without decreasing the revenue to the search engine. The bid optimizer is positioned as a key value added tool the search engine provides to the advertisers. The proposed bid optimizer algorithm transforms the reported values of the advertisers for a keyword into a correlated bid profile using many ideas from cooperative game theory. The algorithm is based on a characteristic form game involving the search engine and the advertisers. Ideas from Nash bargaining theory are used in formulating the characteristic form game to provide for a fair share of surplus among the players involved. The algorithm then computes the nucleolus of the characteristic form game since we find that the nucleolus is an apt way of allocating the gains of cooperation among the search engine and the advertisers. The algorithm next transforms the nucleolus into a correlated bid profile using a linear programming formulation. This bid profile is input to a standard generalized second price mechanism (GSP) for determining the allocation of sponsored slots and the prices to be be paid by the winners. The correlated bid profile that we determine is a locally envy-free equilibrium and also a correlated equilibrium of the underlying game. Through detailed simulation experiments, we show that the proposed bid optimizer retains more customers than a plain GSP mechanism and also yields better long-run utilities to the search engine and the advertisers.
Sharp kernel clustering algorithms and their associated Grothendieck inequalities
Venue: arXiv cs.DS 2009
Year: 2009

In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with $\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0$ and a (small) $k\times k$ symmetric positive semidefinite matrix $B=(b_{ij})$. The goal is to find a partition $\{S_1,...,S_k\}$ of $\{1,... n\}$ which maximizes $ \sum_{i=1}^k\sum_{j=1}^k (\sum_{(p,q)\in S_i\times S_j}a_{pq})b_{ij}$. We design a polynomial time approximation algorithm that achieves an approximation ratio of $\frac{R(B)^2}{C(B)}$, where $R(B)$ and $C(B)$ are geometric parameters that depend only on the matrix $B$, defined as follows: if $b_{ij} = < v_i, v_j>$ is the Gram matrix representation of $B$ for some $v_1,...,v_k\in \R^k$ then $R(B)$ is the minimum radius of a Euclidean ball containing the points $\{v_1, ..., v_k\}$. The parameter $C(B)$ is defined as the maximum over all measurable partitions $\{A_1,...,A_k\}$ of $\R^{k-1}$ of the quantity $\sum_{i=1}^k\sum_{j=1}^k b_{ij}< z_i,z_j>$, where for $i\in \{1,...,k\}$ the vector $z_i\in \R^{k-1}$ is the Gaussian moment of $A_i$, i.e., $z_i=\frac{1}{(2π)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx$. We also show that for every $\eps > 0$, achieving an approximation guarantee of $(1-\e)\frac{R(B)^2}{C(B)}$ is Unique Games hard.
Intrusion Detection System Using Advanced Honeypots
Venue: arXiv cs.CR 2009
Year: 2009

The exponential growth of Internet traffic has made public servers increasingly vulnerable to unauthorized accesses and intrusions. In addition to maintaining low latency for the client, filtering unauthorized accesses has become one of the major concerns of a server maintainer. This implementation of an Intrusion Detection System distinguishes between the traffic coming from clients and the traffic originated from the attackers, in an attempt to simultaneously mitigate the problems of both latency and security. We then present the results of a series of stress and scalability tests, and suggest a number of potential uses for such a system. As computer attacks are becoming more and more difficult to identify the need for better and more efficient intrusion detection systems increases. The main problem with current intrusion detection systems is high rate of false alarms. Using honeypots provides effective solution to increase the security.