OpenRaiser/Intern-Atlas huggingface dataset:
On Secrecy Rate of the Generalized Artificial-Noise Assisted Secure Beamforming for Wiretap Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we consider the secure transmission in fast Rayleigh fading channels with full knowledge of the main channel and only the statistics of the eavesdropper's channel state information at the transmitter. For the multiple-input, single-output, single-antenna eavesdropper systems, we generalize Goel and Negi's celebrated artificial-noise (AN) assisted beamforming, which just selects the directions to transmit AN heuristically. Our scheme may inject AN to the direction of the message, which outperforms Goel and Negi's scheme where AN is only injected in the directions orthogonal to the main channel. The ergodic secrecy rate of the proposed AN scheme can be represented by a highly simplified power allocation problem. To attain it, we prove that the optimal transmission scheme for the message bearing signal is a beamformer, which is aligned to the direction of the legitimate channel. After characterizing the optimal eigenvectors of the covariance matrices of signal and AN, we also provide the necessary condition for transmitting AN in the main channel to be optimal. Since the resulting secrecy rate is a non-convex power allocation problem, we develop an algorithm to efficiently solve it. Simulation results show that our generalized AN scheme outperforms Goel and Negi's, especially when the quality of legitimate channel is much worse than that of eavesdropper's. In particular, the regime with non-zero secrecy rate is enlarged, which can significantly improve the connectivity of the secure network when the proposed AN assisted beamforming is applied.
The Cost of Parameterized Reachability in Mobile Ad Hoc Networks
Venue: arXiv cs.LO 2012
Year: 2012

We investigate the impact of spontaneous movement in the complexity of verification problems for an automata-based protocol model of networks with selective broadcast communication. We first consider reachability of an error state and show that parameterized verification is decidable with polynomial complexity. We then move to richer queries and show how the complexity changes when considering properties with negation or cardinality constraints.
An efficient algorithm for the diameter of Cayley graphs generated by transposition trees
Venue: arXiv cs.DM 2012
Year: 2012

A problem of practical and theoretical interest is to determine or estimate the diameter of various families of Cayley networks. The previously known estimate for the diameter of Cayley graphs generated by transposition trees is an upper bound given in the oft-cited paper of Akers and Krishnamurthy (1989). In this work, we first assess the performance of their upper bound. We show that for every $n$, there exists a tree on $n$ vertices, such that the difference between the upper bound and the true diameter value is at least $n-4$. Evaluating their upper bound takes time $Ω(n!)$. In this paper, we provide an algorithm that obtains an estimate of the diameter, but which requires only time $O(n^2)$; furthermore, the value obtained by our algorithm is less than or equal to the previously known diameter upper bound. Such an improvement to polynomial time, while still performing at least as well as the previous bound, is possible because our algorithm works directly with the transposition tree on $n$ vertices and does not require examining any of the permutations. We also provide a tree for which the value computed by our algorithm is not necessarily unique, which is an important result because such examples are quite rare. For all families of trees we have investigated so far, each of the possible values computed by our algorithm happens to also be an upper bound on the diameter.
Estimators in Cryptography
Venue: arXiv cs.CR 2012
Year: 2012

One of the main problems in cryptography is to give criteria to provide good comparators of cipher systems. The security of a cipher system must include the security of the algorithm, the security of the key generator and management module (see [BM94], [CM97],[Mau92a]) and the security of the cryptographic key agreement protocol (see [Mau93a],[MC94],[Mau93b],[Mau92b]). This paper gives show the necessary mathematical background to estimate the most important cryptographic measures of the key generators and of the unconditionally key agreement protocols. These cryptographic measures are the Shannon entropy (for the key generator module) and Renyi entropy of order alpha for the key agreement protocol.
On the Convergence of Collaboration and Knowledge Management
Venue: arXiv cs.HC 2012
Year: 2012

Collaboration technology typically focuses on collaboration and group processes (cooperation, communication, coordination and coproduction). Knowledge Management (KM) technology typically focuses on content (creation, storage, sharing and use of data, information and knowledge). Yet, to achieve their common goals, teams and organizations need both KM and collaboration technology to make that more effective and efficient. This paper is interested in knowledge management and collaboration regarding their convergence and their integration. First, it contributes to a better understanding of the knowledge management and collaboration concepts. Second, it focuses on KM and collaboration convergence by presenting the different interpretation of this convergence. Third, this paper proposes a generic framework of collaborative knowledge management.
An Optimal Control Approach to the Persistent Monitoring Problem
Venue: arXiv cs.SY 2012
Year: 2012

We propose an optimal control framework for persistent monitoring problems where the objective is to control the movement of mobile nodes to minimize an uncertainty metric in a given mission space. For multi agent in a one-dimensional mission space, we show that the optimal solution is obtained in terms of a sequence of switching locations and waiting time on these switching points, thus reducing it to a parametric optimization problem. Using Infinitesimal Perturbation Analysis (IPA) we obtain a complete solution through a gradient-based algorithm. We also discuss a receding horizon controller which is capable of obtaining a near-optimal solution on-the-fly.
Model-Based Security Testing
Venue: arXiv cs.SE 2012
Year: 2012

Security testing aims at validating software system requirements related to security properties like confidentiality, integrity, authentication, authorization, availability, and non-repudiation. Although security testing techniques are available for many years, there has been little approaches that allow for specification of test cases at a higher level of abstraction, for enabling guidance on test identification and specification as well as for automated test generation. Model-based security testing (MBST) is a relatively new field and especially dedicated to the systematic and efficient specification and documentation of security test objectives, security test cases and test suites, as well as to their automated or semi-automated generation. In particular, the combination of security modelling and test generation approaches is still a challenge in research and of high interest for industrial applications. MBST includes e.g. security functional testing, model-based fuzzing, risk- and threat-oriented testing, and the usage of security test patterns. This paper provides a survey on MBST techniques and the related models as well as samples of new methods and tools that are under development in the European ITEA2-project DIAMONDS.
Reusing Test-Cases on Different Levels of Abstraction in a Model Based Development Tool
Venue: arXiv cs.SE 2012
Year: 2012

Seamless model based development aims to use models during all phases of the development process of a system. During the development process in a component-based approach, components of a system are described at qualitatively differing abstraction levels: during requirements engineering component models are rather abstract high-level and underspecified, while during implementation the component models are rather concrete and fully specified in order to enable code generation. An important issue that arises is assuring that the concrete models correspond to abstract models. In this paper, we propose a method to assure that concrete models for system components refine more abstract models for the same components. In particular we advocate a framework for reusing testcases at different abstraction levels. Our approach, even if it cannot completely prove the refinement, can be used to ensure confidence in the development process. In particular we are targeting the refinement of requirements which are represented as very abstract models. Besides a formal model of our approach, we discuss our experiences with the development of an Adaptive Cruise Control (ACC) system in a model driven development process. This uses extensions which we implemented for our model-based development tool and which are briefly presented in this paper.
Using Built-In Domain-Specific Modeling Support to Guide Model-Based Test Generation
Venue: arXiv cs.SE 2012
Year: 2012

We present a model-based testing approach to support automated test generation with domain-specific concepts. This includes a language expert who is an expert at building test models and domain experts who are experts in the domain of the system under test. First, we provide a framework to support the language expert in building test models using a full (Java) programming language with the help of simple but powerful modeling elements of the framework. Second, based on the model built with this framework, the toolset automatically forms a domain-specific modeling language that can be used to further constrain and guide test generation from these models by a domain expert. This makes it possible to generate a large set of test cases covering the full model, chosen (constrained) parts of the model, or manually define specific test cases on top of the model while using concepts familiar to the domain experts.
Model-Based Testing of Safety Critical Real-Time Control Logic Software
Venue: arXiv cs.SE 2012
Year: 2012

The paper presents the experience of the authors in model based testing of safety critical real-time control logic software. It describes specifics of the corresponding industrial settings and discusses technical details of usage of UniTESK model based testing technology in these settings. Finally, we discuss possible future directions of safety critical software development processes and a place of model based testing techniques in it.
One Decade of Universal Artificial Intelligence
Venue: arXiv cs.AI 2012
Year: 2012

The first decade of this century has seen the nascency of the first mathematical theory of general artificial intelligence. This theory of Universal Artificial Intelligence (UAI) has made significant contributions to many theoretical, philosophical, and practical AI questions. In a series of papers culminating in book (Hutter, 2005), an exciting sound and complete mathematical model for a super intelligent agent (AIXI) has been developed and rigorously analyzed. While nowadays most AI researchers avoid discussing intelligence, the award-winning PhD thesis (Legg, 2008) provided the philosophical embedding and investigated the UAI-based universal measure of rational intelligence, which is formal, objective and non-anthropocentric. Recently, effective approximations of AIXI have been derived and experimentally investigated in JAIR paper (Veness et al. 2011). This practical breakthrough has resulted in some impressive applications, finally muting earlier critique that UAI is only a theory. For the first time, without providing any domain knowledge, the same agent is able to self-adapt to a diverse range of interactive environments. For instance, AIXI is able to learn from scratch to play TicTacToe, Pacman, Kuhn Poker, and other games by trial and error, without even providing the rules of the games. These achievements give new hope that the grand goal of Artificial General Intelligence is not elusive. This article provides an informal overview of UAI in context. It attempts to gently introduce a very theoretical, formal, and mathematical subject, and discusses philosophical and technical ingredients, traits of intelligence, some social questions, and the past and future of UAI.
On Optimal Message Assignments for Interference Channels with CoMP Transmission
Venue: arXiv cs.IT 2012
Year: 2012

The degrees of freedom (DoF) number of the fully connected K-user Gaussian interference channel is known to be K/2. In [1], the DoF for the same channel model was studied while allowing each message to be available at its own transmitter as well as M-1 successive transmitters. In particular, it was shown that the DoF gain through cooperation does not scale with the number of users K for a fixed value of M, i.e., the per user DoF number is 1/2 . In this work, we relax the cooperation constraint such that each message can be assigned to M transmitters without imposing further constraints on their location. Under the new constraint, we study properties for different message assignments in terms of the gain in the per user DoF number over that achieved without cooperation. In particular, we show that a local cooperation constraint that confines the transmit set of each message within a o(K) radius cannot achieve a per user DoF number that is greater than 1/2. Moreover, we show that the same conclusion about the per user DoF number holds for any assignment of messages such that each message cannot be available at more than two transmitters. Finally, for the case where M > 2, we do not know whether a per user DoF number that is greater than 1/2 is achievable. However, we identify a candidate class of message assignments that could potentially lead to a positive answer. [1] V. S. Annapureddy, A. El Gamal, and V. V. Veervalli, "Degrees of Freedom of Interference Channels with CoMP Transmission and Reception," Submitted to IEEE Trans. Inf. Theory, Sep. 2011
Bisection (Band)Width of Product Networks with Application to Data Centers
Venue: arXiv cs.NI 2012
Year: 2012

The bisection width of interconnection networks has always been important in parallel computing, since it bounds the amount of information that can be moved from one side of a network to another, i.e., the bisection bandwidth. Finding its exact value has proven to be challenging for some network families. For instance, the problem of finding the exact bisection width of the multidimensional torus was posed by Leighton and has remained open for almost 20 years. In this paper we provide the exact value of the bisection width of the torus, as well as of several d-dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. To do so, we first provide two general results that allow to obtain upper and lower bounds on the bisection width of a product graph as a function of some properties of its factor graphs. We also apply these results to obtain bounds for the bisection bandwidth of a d-dimensional BCube network, a recently proposed topology for data centers.
Open Annotations on Multimedia Web Resources
Venue: arXiv cs.DL 2012
Year: 2012

Many Web portals allow users to associate additional information with existing multimedia resources such as images, audio, and video. However, these portals are usually closed systems and user-generated annotations are almost always kept locked up and remain inaccessible to the Web of Data. We believe that an important step to take is the integration of multimedia annotations and the Linked Data principles. We present the current state of the Open Annotation Model, explain our design rationale, and describe how the model can represent user annotations on multimedia Web resources. Applying this model in Web portals and devices, which support user annotations, should allow clients to easily publish and consume, thus exchange annotations on multimedia Web resources via common Web standards.
Quaternary Constant-Composition Codes with Weight Four and Distances Five or Six
Venue: arXiv cs.IT 2012
Year: 2012

The sizes of optimal constant-composition codes of weight three have been determined by Chee, Ge and Ling with four cases in doubt. Group divisible codes played an important role in their constructions. In this paper, we study the problem of constructing optimal quaternary constant-composition codes with Hamming weight four and minimum distances five or six through group divisible codes and Room square approaches. The problem is solved leaving only five lengths undetermined. Previously, the results on the sizes of such quaternary constant-composition codes were scarce.
First steps towards the certification of an ARM simulator using Compcert
Venue: arXiv cs.LO 2012
Year: 2012

The simulation of Systems-on-Chip (SoC) is nowadays a hot topic because, beyond providing many debugging facilities, it allows the development of dedicated software before the hardware is available. Low-consumption CPUs such as ARM play a central role in SoC. However, the effectiveness of simulation depends on the faithfulness of the simulator. To this effect, we propose here to prove significant parts of such a simulator, SimSoC. Basically, on one hand, we develop a Coq formal model of the ARM architecture while on the other hand, we consider a version of the simulator including components written in Compcert-C. Then we prove that the simulation of ARM operations, according to Compcert-C formal semantics, conforms to the expected formal model of ARM. Size issues are partly dealt with using automatic generation of significant parts of the Coq model and of SimSoC from the official textual definition of ARM. However, this is still a long-term project. We report here the current stage of our efforts and discuss in particular the use of Compcert-C in this framework.
Coverage and Economy of Cellular Networks with Many Base Stations
Venue: arXiv cs.NI 2012
Year: 2012

The performance of a cellular network can be significantly improved by employing many base stations (BSs), which shortens transmission distances. However, there exist no known results on quantifying the performance gains from deploying many BSs. To address this issue, we adopt a stochastic-geometry model of the downlink cellular network and analyze the mobile outage probability. Specifically, given Poisson distributed BSs, the outage probability is shown to diminish inversely with the increasing ratio between the BS and mobile densities. Furthermore, we analyze the optimal tradeoff between the performance gain from increasing the BS density and the resultant network cost accounting for energy consumption, BS hardware and backhaul cables. The optimal BS density is proved to be proportional to the square root of the mobile density and the inverse of the square root of the cost factors considered.
A Model-Driven Parser Generator, from Abstract Syntax Trees to Abstract Syntax Graphs
Venue: arXiv cs.PL 2012
Year: 2012

Model-based parser generators decouple language specification from language processing. The model-driven approach avoids the limitations that conventional parser generators impose on the language designer. Conventional tools require the designed language grammar to conform to the specific kind of grammar supported by the particular parser generator (being LL and LR parser generators the most common). Model-driven parser generators, like ModelCC, do not require a grammar specification, since that grammar can be automatically derived from the language model and, if needed, adapted to conform to the requirements of the given kind of parser, all of this without interfering with the conceptual design of the language and its associated applications. Moreover, model-driven tools such as ModelCC are able to automatically resolve references between language elements, hence producing abstract syntax graphs instead of abstract syntax trees as the result of the parsing process. Such graphs are not confined to directed acyclic graphs and they can contain cycles, since ModelCC supports anaphoric, cataphoric, and recursive references.
Trajectory and Policy Aware Sender Anonymity in Location Based Services
Venue: arXiv cs.DB 2012
Year: 2012

We consider Location-based Service (LBS) settings, where a LBS provider logs the requests sent by mobile device users over a period of time and later wants to publish/share these logs. Log sharing can be extremely valuable for advertising, data mining research and network management, but it poses a serious threat to the privacy of LBS users. Sender anonymity solutions prevent a malicious attacker from inferring the interests of LBS users by associating them with their service requests after gaining access to the anonymized logs. With the fast-increasing adoption of smartphones and the concern that historic user trajectories are becoming more accessible, it becomes necessary for any sender anonymity solution to protect against attackers that are trajectory-aware (i.e. have access to historic user trajectories) as well as policy-aware (i.e they know the log anonymization policy). We call such attackers TP-aware. This paper introduces a first privacy guarantee against TP-aware attackers, called TP-aware sender k-anonymity. It turns out that there are many possible TP-aware anonymizations for the same LBS log, each with a different utility to the consumer of the anonymized log. The problem of finding the optimal TP-aware anonymization is investigated. We show that trajectory-awareness renders the problem computationally harder than the trajectory-unaware variants found in the literature (NP-complete in the size of the log, versus PTIME). We describe a PTIME l-approximation algorithm for trajectories of length l and empirically show that it scales to large LBS logs (up to 2 million users).
Derivation Lengths Classification of Gödel's T Extending Howard's Assignment
Venue: arXiv cs.LO 2012
Year: 2012

Let T be Goedel's system of primitive recursive functionals of finite type in the lambda formulation. We define by constructive means using recursion on nested multisets a multivalued function I from the set of terms of T into the set of natural numbers such that if a term a reduces to a term b and if a natural number I(a) is assigned to a then a natural number I(b) can be assigned to b such that I(a) is greater than I(b). The construction of I is based on Howard's 1970 ordinal assignment for T and Weiermann's 1996 treatment of T in the combinatory logic version. As a corollary we obtain an optimal derivation length classification for the lambda formulation of T and its fragments. Compared with Weiermann's 1996 exposition this article yields solutions to several non-trivial problems arising from dealing with lambda terms instead of combinatory logic terms. It is expected that the methods developed here can be applied to other higher order rewrite systems resulting in new powerful termination orderings since T is a paradigm for such systems.
How does the Shift-insertion sort behave when the sorting elements follow a Normal distribution?
Venue: arXiv cs.DS 2012
Year: 2012

The present paper examines the behavior of Shift-insertion sort (insertion sort with shifting) for normal distribution inputs and is in continuation of our earlier work on this new algorithm for discrete distribution inputs, namely, negative binomial. Shift insertion sort is found more sensitive for main effects but not for all interaction effects compared to conventional insertion sort.
The Equational Approach to CF2 Semantics
Venue: arXiv cs.AI 2012
Year: 2012

We introduce a family of new equational semantics for argumentation networks which can handle odd and even loops in a uniform manner. We offer one version of equational semantics which is equivalent to CF2 semantics, and a better version which gives the same results as traditional Dung semantics for even loops but can still handle odd loops.