OpenRaiser/Intern-Atlas huggingface dataset:
Strategic Alert Throttling for Intrusion Detection Systems
Venue: arXiv cs.NE 2008
Year: 2008

Network intrusion detection systems are themselves becoming targets of attackers. Alert flood attacks may be used to conceal malicious activity by hiding it among a deluge of false alerts sent by the attacker. Although these types of attacks are very hard to stop completely, our aim is to present techniques that improve alert throughput and capacity to such an extent that the resources required to successfully mount the attack become prohibitive. The key idea presented is to combine a token bucket filter with a realtime correlation algorithm. The proposed algorithm throttles alert output from the IDS when an attack is detected. The attack graph used in the correlation algorithm is used to make sure that alerts crucial to forming strategies are not discarded by throttling.
Solving Min-Max Problems with Applications to Games
Venue: arXiv cs.GT 2008
Year: 2008

We refine existing general network optimization techniques, give new characterizations for the class of problems to which they can be applied, and show that they can also be used to solve various two-player games in almost linear time. Among these is a new variant of the network interdiction problem, where the interdictor wants to destroy high-capacity paths from the source to the destination using a vertex-wise limited budget of arc removals. We also show that replacing the limit average in mean payoff games by the maximum weight results in a class of games amenable to these techniques.
Quantum entanglement analysis based on abstract interpretation
Venue: arXiv cs.LO 2008
Year: 2008

Entanglement is a non local property of quantum states which has no classical counterpart and plays a decisive role in quantum information theory. Several protocols, like the teleportation, are based on quantum entangled states. Moreover, any quantum algorithm which does not create entanglement can be efficiently simulated on a classical computer. The exact role of the entanglement is nevertheless not well understood. Since an exact analysis of entanglement evolution induces an exponential slowdown, we consider approximative analysis based on the framework of abstract interpretation. In this paper, a concrete quantum semantics based on superoperators is associated with a simple quantum programming language. The representation of entanglement, i.e. the design of the abstract domain is a key issue. A representation of entanglement as a partition of the memory is chosen. An abstract semantics is introduced, and the soundness of the approximation is proven.
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems
Venue: arXiv cs.DS 2008
Year: 2008

We study scheduling problems motivated by recently developed techniques for microprocessor thermal management at the operating systems level. The general scenario can be described as follows. The microprocessor's temperature is controlled by the hardware thermal management system that continuously monitors the chip temperature and automatically reduces the processor's speed as soon as the thermal threshold is exceeded. Some tasks are more CPU-intensive than other and thus generate more heat during execution. The cooling system operates non-stop, reducing (at an exponential rate) the deviation of the processor's temperature from the ambient temperature. As a result, the processor's temperature, and thus the performance as well, depends on the order of the task execution. Given a variety of possible underlying architectures, models for cooling and for hardware thermal management, as well as types of tasks, this scenario gives rise to a plethora of interesting and never studied scheduling problems. We focus on scheduling real-time jobs in a simplified model for cooling and thermal management. A collection of unit-length jobs is given, each job specified by its release time, deadline and heat contribution. If, at some time step, the temperature of the system is t and the processor executes a job with heat contribution h, then the temperature at the next step is (t+h)/2. The temperature cannot exceed the given thermal threshold T. The objective is to maximize the throughput, that is, the number of tasks that meet their deadlines. We prove that, in the offline case, computing the optimum schedule is NP-hard, even if all jobs are released at the same time. In the online case, we show a 2-competitive deterministic algorithm and a matching lower bound.
Protecting Spreadsheets Against Fraud
Venue: arXiv cs.CY 2008
Year: 2008

Previous research on spreadsheet risks has predominantly focussed on errors inadvertently introduced by spreadsheet writers i.e. it focussed on the end-user aspects of spreadsheet development. When analyzing a faulty spreadsheet, one might not be able to determine whether a particular error (fault) has been made by mistake or with fraudulent intentions. However, the fences protecting against fraudulent errors have to be different from those shielding against inadvertent mistakes. Faults resulting from errors committed inadvertently can be prevented ab initio by tools that notify the spreadsheet writer about potential problems whereas faults that are introduced on purpose have to be discovered by auditors without the cooperation of their originators. Even worse, some spreadsheet writers will do their best to conceal fraudulent parts of their spreadsheets from auditors. In this paper we survey the available means for fraud protection by contrasting approaches suitable for spreadsheets with those known from fraud protection for conventional software.
Computational Models of Spreadsheet Development: Basis for Educational Approaches
Venue: arXiv cs.HC 2008
Year: 2008

Among the multiple causes of high error rates in spreadsheets, lack of proper training and of deep understanding of the computational model upon which spreadsheet computations rest might not be the least issue. The paper addresses this problem by presenting a didactical model focussing on cell interaction, thus exceeding the atomicity of cell computations. The approach is motivated by an investigation how different spreadsheet systems handle certain computational issues implied from moving cells, copy-paste operations, or recursion.
On Affinity Measures for Artificial Immune System Movie Recommenders
Venue: arXiv cs.NE 2008
Year: 2008

We combine Artificial Immune Systems 'AIS', technology with Collaborative Filtering 'CF' and use it to build a movie recommendation system. We already know that Artificial Immune Systems work well as movie recommenders from previous work by Cayzer and Aickelin 3, 4, 5. Here our aim is to investigate the effect of different affinity measure algorithms for the AIS. Two different affinity measures, Kendalls Tau and Weighted Kappa, are used to calculate the correlation coefficients for the movie recommender. We compare the results with those published previously and show that Weighted Kappa is more suitable than others for movie problems. We also show that AIS are generally robust movie recommenders and that, as long as a suitable affinity measure is chosen, results are good.
TER: A Robot for Remote Ultrasonic Examination: Experimental Evaluations
Venue: arXiv cs.OH 2008
Year: 2008

This chapter: o Motivates the clinical use of robotic tele-echography o Introduces the TER system o Describes technical and clinical evaluations performed with TER
Abstractions for biomolecular computations
Venue: arXiv cs.OH 2008
Year: 2008

Deoxyribonucleic acid is increasingly being understood to be an informational molecule, capable of information processing.It has found application in the determination of non-deterministic algorithms and in the design of molecular computing devices. This is a theoretical analysis of the mathematical properties and relations of the molecules which constituting DNA, which explains in part why DNA is a successful computing molecule.
The Complexity of Power-Index Comparison
Venue: arXiv cs.CC 2008
Year: 2008

We study the complexity of the following problem: Given two weighted voting games G' and G'' that each contain a player p, in which of these games is p's power index value higher? We study this problem with respect to both the Shapley-Shubik power index [SS54] and the Banzhaf power index [Ban65,DS79]. Our main result is that for both of these power indices the problem is complete for probabilistic polynomial time (i.e., is PP-complete). We apply our results to partially resolve some recently proposed problems regarding the complexity of weighted voting games. We also study the complexity of the raw Shapley-Shubik power index. Deng and Papadimitriou [DP94] showed that the raw Shapley-Shubik power index is #P-metric-complete. We strengthen this by showing that the raw Shapley-Shubik power index is many-one complete for #P. And our strengthening cannot possibly be further improved to parsimonious completeness, since we observe that, in contrast with the raw Banzhaf power index, the raw Shapley-Shubik power index is not #P-parsimonious-complete.
Graceful Degradation of Air Traffic Operations
Venue: arXiv cs.OH 2008
Year: 2008

The introduction of new technologies and concepts of operation in the air transportation system is not possible, unless they can be proven not to adversely affect the system operation under not only nominal, but also degraded conditions. In extreme scenarios, degraded operations due to partial or complete technological failures should never endanger system safety. Many past system evolutions, whether ground-based or airborne, have been based on trial-and-error, and system safety was addressed only after a specific event yielded dramatic or near- dramatic consequences. Future system evolutions, however, must leverage available computation, prior knowledge and abstract reasoning to anticipate all possible system degradations and prove that such degradations are graceful and safe. This paper is concerned with the graceful degradation of high-density, structured arrival traffic against partial or complete surveillance failures. It is shown that for equal performance requirements, some traffic configurations might be easier to handle than others, thereby offering a quantitative perspective on these traffic configurations. ability to "gracefully degrade". To support our work, we also introduce a new conflict resolution algorithm, aimed at solving conflicts involving many aircraft when aircraft position information is in the process of degrading.
Spreadsheet Assurance by "Control Around" is a Viable Alternative to the Traditional Approach
Venue: arXiv cs.SE 2008
Year: 2008

The traditional approach to spreadsheet auditing generally consists of auditing every distinct formula within a spreadsheet. Although tools are developed to support auditors during this process, the approach is still very time consuming and therefore relatively expensive. As an alternative to the traditional "control through" approach, this paper discusses a "control around" approach. Within the proposed approach not all distinct formulas are audited separately, but the relationship between input data and output data of a spreadsheet is audited through comparison with a shadow model developed in a modelling language. Differences between the two models then imply possible errors in the spreadsheet. This paper describes relevant issues regarding the "control around" approach and the circumstances in which this approach is preferred above a traditional spreadsheet audit approach.
Investigating the Potential of Test-Driven Development for Spreadsheet Engineering
Venue: arXiv cs.SE 2008
Year: 2008

It is widely documented that the absence of a structured approach to spreadsheet engineering is a key factor in the high level of spreadsheet errors. In this paper we propose and investigate the application of Test-Driven Development to the creation of spreadsheets. Test-Driven Development is an emerging development technique in software engineering that has been shown to result in better quality software code. It has also been shown that this code requires less testing and is easier to maintain. Through a pair of case studies we demonstrate that Test-Driven Development can be applied to the development of spreadsheets. We present the detail of these studies preceded by a clear explanation of the technique and its application to spreadsheet engineering. A supporting tool under development by the authors is also documented along with proposed research to determine the effectiveness of the methodology and the associated tool.
Zero-Knowledge Proofs of the Conjugacy for Permutation Groups
Venue: arXiv cs.CC 2008
Year: 2008

We design a perfect zero-knowledge proof system for recognition if two permutation groups are conjugate.
Mission impossible: Computing the network coding capacity region
Venue: arXiv cs.IT 2008
Year: 2008

One of the main theoretical motivations for the emerging area of network coding is the achievability of the max-flow/min-cut rate for single source multicast. This can exceed the rate achievable with routing alone, and is achievable with linear network codes. The multi-source problem is more complicated. Computation of its capacity region is equivalent to determination of the set of all entropy functions $Γ^*$, which is non-polyhedral. The aim of this paper is to demonstrate that this difficulty can arise even in single source problems. In particular, for single source networks with hierarchical sink requirements, and for single source networks with secrecy constraints. In both cases, we exhibit networks whose capacity regions involve $Γ^*$. As in the multi-source case, linear codes are insufficient.
Popularity, Novelty and Attention
Venue: arXiv cs.CY 2008
Year: 2008

We analyze the role that popularity and novelty play in attracting the attention of users to dynamic websites. We do so by determining the performance of three different strategies that can be utilized to maximize attention. The first one prioritizes novelty while the second emphasizes popularity. A third strategy looks myopically into the future and prioritizes stories that are expected to generate the most clicks within the next few minutes. We show that the first two strategies should be selected on the basis of the rate of novelty decay, while the third strategy performs sub-optimally in most cases. We also demonstrate that the relative performance of the first two strategies as a function of the rate of novelty decay changes abruptly around a critical value, resembling a phase transition in the physical world. 1
Rotated and Scaled Alamouti Coding
Venue: arXiv cs.IT 2008
Year: 2008

Repetition-based retransmission is used in Alamouti-modulation [1998] for $2\times 2$ MIMO systems. We propose to use instead of ordinary repetition so-called "scaled repetition" together with rotation. It is shown that the rotated and scaled Alamouti code has a hard-decision performance which is only slightly worse than that of the Golden code [2005], the best known $2\times 2$ space-time code. Decoding the Golden code requires an exhaustive search over all codewords, while our rotated and scaled Alamouti code can be decoded with an acceptable complexity however.
Knowledge management by wikis
Venue: arXiv cs.DL 2008
Year: 2008

Wikis provide a new way of collaboration and knowledge sharing. Wikis are software that allows users to work collectively on a web-based knowledge base. Wikis are characterised by a sense of anarchism, collaboration, connectivity, organic development and self-healing, and they rely on trust. We list several concerns about applying wikis in professional organisation. After these concerns are met, wikis can provide a progessive, new knowledge sharing and collaboration tool.
Using Bayesian Blocks to Partition Self-Organizing Maps
Venue: arXiv cs.NE 2008
Year: 2008

Self organizing maps (SOMs) are widely-used for unsupervised classification. For this application, they must be combined with some partitioning scheme that can identify boundaries between distinct regions in the maps they produce. We discuss a novel partitioning scheme for SOMs based on the Bayesian Blocks segmentation algorithm of Scargle [1998]. This algorithm minimizes a cost function to identify contiguous regions over which the values of the attributes can be represented as approximately constant. Because this cost function is well-defined and largely independent of assumptions regarding the number and structure of clusters in the original sample space, this partitioning scheme offers significant advantages over many conventional methods. Sample code is available.
Combining generic judgments with recursive definitions
Venue: arXiv cs.LO 2008
Year: 2008

Many semantical aspects of programming languages, such as their operational semantics and their type assignment calculi, are specified by describing appropriate proof systems. Recent research has identified two proof-theoretic features that allow direct, logic-based reasoning about such descriptions: the treatment of atomic judgments as fixed points (recursive definitions) and an encoding of binding constructs via generic judgments. However, the logics encompassing these two features have thus far treated them orthogonally: that is, they do not provide the ability to define object-logic properties that themselves depend on an intrinsic treatment of binding. We propose a new and simple integration of these features within an intuitionistic logic enhanced with induction over natural numbers and we show that the resulting logic is consistent. The pivotal benefit of the integration is that it allows recursive definitions to not just encode simple, traditional forms of atomic judgments but also to capture generic properties pertaining to such judgments. The usefulness of this logic is illustrated by showing how it can provide elegant treatments of object-logic contexts that appear in proofs involving typing calculi and of arbitrarily cascading substitutions that play a role in reducibility arguments.
Note sur les temps de service résiduels dans les systèmes type M/G/c
Venue: arXiv cs.NI 2008
Year: 2008

Approximations for the mean performance indices for the M/G/c queue rely on the approximate computation of the probability that an arriving request has to wait for service and of the minimum of residual service times if all servers are found busy. Using numerical examples, we investigate properties of these two quantities. In particular, we show that the minimum of residual service times depends on higher order properties, beyond the first two moments, of the service time distribution. Improved knowledge of the properties of the two quantities studied in this paper provides insight into avenues for improving the accuracy of approximations for the M/G/c queue.
Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
Venue: arXiv cs.LO 2008
Year: 2008

In this paper, we first introduce a lower bound technique for the state complexity of transformations of automata. Namely we suggest first considering the class of full automata in lower bound analysis, and later reducing the size of the large alphabet via alphabet substitutions. Then we apply such technique to the complementation of nondeterministic ω-automata, and obtain several lower bound results. Particularly, we prove an ω((0.76n)^n) lower bound for Büchi complementation, which also holds for almost every complementation or determinization transformation of nondeterministic omega-automata, and prove an optimal (ω(nk))^n lower bound for the complementation of generalized Büchi automata, which holds for Streett automata as well.
The Invar tensor package: Differential invariants of Riemann
Venue: arXiv cs.SC 2008
Year: 2008

The long standing problem of the relations among the scalar invariants of the Riemann tensor is computationally solved for all 6x10^23 objects with up to 12 derivatives of the metric. This covers cases ranging from products of up to 6 undifferentiated Riemann tensors to cases with up to 10 covariant derivatives of a single Riemann. We extend our computer algebra system Invar to produce within seconds a canonical form for any of those objects in terms of a basis. The process is as follows: (1) an invariant is converted in real time into a canonical form with respect to the permutation symmetries of the Riemann tensor; (2) Invar reads a database of more than 6x10^5 relations and applies those coming from the cyclic symmetry of the Riemann tensor; (3) then applies the relations coming from the Bianchi identity, (4) the relations coming from commutations of covariant derivatives, (5) the dimensionally-dependent identities for dimension 4, and finally (6) simplifies invariants that can be expressed as product of dual invariants. Invar runs on top of the tensor computer algebra systems xTensor (for Mathematica) and Canon (for Maple).
On Directed Information and Gambling
Venue: arXiv cs.IT 2008
Year: 2008

We study the problem of gambling in horse races with causal side information and show that Massey's directed information characterizes the increment in the maximum achievable capital growth rate due to the availability of side information. This result gives a natural interpretation of directed information $I(Y^n \to X^n)$ as the amount of information that $Y^n$ \emph{causally} provides about $X^n$. Extensions to stock market portfolio strategies and data compression with causal side information are also discussed.
Error-Correcting Data Structures
Venue: arXiv cs.DS 2008
Year: 2008

We study data structures in the presence of adversarial noise. We want to encode a given object in a succinct data structure that enables us to efficiently answer specific queries about the object, even if the data structure has been corrupted by a constant fraction of errors. This new model is the common generalization of (static) data structures and locally decodable error-correcting codes. The main issue is the tradeoff between the space used by the data structure and the time (number of probes) needed to answer a query about the encoded object. We prove a number of upper and lower bounds on various natural error-correcting data structure problems. In particular, we show that the optimal length of error-correcting data structures for the Membership problem (where we want to store subsets of size s from a universe of size n) is closely related to the optimal length of locally decodable codes for s-bit strings.
Program Promises
Venue: arXiv cs.SE 2008
Year: 2008

The framework of promise theory offers an alternative way of understanding programming models, especially in distributed systems. We show that promise theory can express some familiar constructs and resolve some problems in program interface design, using fewer and simpler concepts than the Unified Modelling Language (UML).
Diversity and Degrees of Freedom of Cooperative Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

Wireless fading networks with multiple antennas are typically studied information-theoretically from two different perspectives - the outage characterization and the ergodic capacity characterization. A key parameter in the outage characterization of a network is the diversity, whereas a first-order indicator for the ergodic capacity is the degrees of freedom (DOF), which is the pre-log coefficient in the capacity expression. In this paper, we present max-flow min-cut type theorems for computing both the diversity and the degrees of freedom of arbitrary single-source single-sink multi-antenna networks. We also show that an amplify-and-forward protocol is sufficient to achieve this. The degrees of freedom characterization is obtained using a conversion to a deterministic wireless network for which the capacity was recently found. We show that the diversity result easily extends to multi-source multi-sink networks and evaluate the DOF for multi-casting in single-source multi-sink networks.