OpenRaiser/Intern-Atlas huggingface dataset:
Hardware Trojan by Hot Carrier Injection
Venue: arXiv cs.AR 2009
Year: 2009

This paper discusses how hot carrier injection (HCI) can be exploited to create a trojan that will cause hardware failures. The trojan is produced not via additional logic circuitry but by controlled scenarios that maximize and accelerate the HCI effect in transistors. These scenarios range from manipulating the manufacturing process to varying the internal voltage distribution. This new type of trojan is difficult to test due to its gradual hardware degradation mechanism. This paper describes the HCI effect, detection techniques and discusses the possibility for maliciously induced HCI trojans.
Aspects of enumeration and generation with a string automata representation
Venue: arXiv cs.FL 2009
Year: 2009

In general, the representation of combinatorial objects is decisive for the feasibility of several enumerative tasks. In this work, we show how a (unique) string representation for (complete) initially-connected deterministic automata (ICDFAs) with n states over an alphabet of k symbols can be used for counting, exact enumeration, sampling and optimal coding, not only the set of ICDFAs but, to some extent, the set of regular languages. An exact generation algorithm can be used to partition the set of ICDFAs in order to parallelize the counting of minimal automata (and thus of regular languages). We present also a uniform random generator for ICDFAs that uses a table of pre-calculated values. Based on the same table it is also possible to obtain an optimal coding for ICDFAs.
Games for width parameters and monotonicity
Venue: arXiv cs.DM 2009
Year: 2009

We introduce a search game for two players played on a "scenario" consisting of a ground set together with a collection of feasible partitions. This general setting allows us to obtain new characterisations of many width parameters such as rank-width and carving-width of graphs, matroid tree-width and GF(4)-rank-width. We show that the monotone game variant corresponds to a tree decomposition of the ground set along feasible partitions. Our framework also captures many other decompositions into "simple" subsets of the ground set, such as decompositions into planar subgraphs. Within our general framework, we take a step towards characterising monotone search games. We exhibit a large class of "monotone" scenarios, i.e. of scenarios where the game and its monotone variant coincide. As a consequence, determining the winner is in NP for these games. This result implies monotonicity for all our search games, that are equivalent to branch-width of a submodular function. Finally, we include a proof showing that the matroid tree-width of a graphic matroid is not larger than the tree-width of the corresponding graph. This proof is considerably shorter than the original proof and it is purely graph theoretic.
An Introduction to Simulation-Based Techniques for Automated Service Composition
Venue: arXiv cs.SE 2009
Year: 2009

This work is an introduction to the author's contributions to the SOC area, resulting from his PhD research activity. It focuses on the problem of automatically composing a desired service, given a set of available ones and a target specification. As for description, services are represented as finite-state transition systems, so to provide an abstract account of their behavior, seen as the set of possible conversations with external clients. In addition, the presence of a finite shared memory is considered, that services can interact with and which provides a basic form of communication. Rather than describing technical details, we offer an informal overview of the whole work, and refer the reader to the original papers, referenced throughout this work, for all details.
Physical Modeling Techniques in Active Contours for Image Segmentation
Venue: arXiv cs.CV 2009
Year: 2009

Physical modeling method, represented by simulation and visualization of the principles in physics, is introduced in the shape extraction of the active contours. The objectives of adopting this concept are to address the several major difficulties in the application of Active Contours. Primarily, a technique is developed to realize the topological changes of Parametric Active Contours (Snakes). The key strategy is to imitate the process of a balloon expanding and filling in a closed space with several objects. After removing the touched balloon surfaces, the objects can be identified by surrounded remaining balloon surfaces. A burned region swept by Snakes is utilized to trace the contour and to give a criterion for stopping the movement of Snake curve. When the Snakes terminates evolution totally, through ignoring this criterion, it can form a connected area by evolving the Snakes again and continuing the region burning. The contours extracted from the boundaries of the burned area can represent the child snake of each object respectively. Secondly, a novel scheme is designed to solve the problems of leakage of the contour from the large gaps, and the segmentation error in Geometric Active Contours (GAC). It divides the segmentation procedure into two processing stages. By simulating the wave propagating in the isotropic substance at the final stage, it can significantly enhance the effect of image force in GAC based on Level Set and give the satisfied solutions to the two problems. Thirdly, to support the physical models for active contours above, we introduce a general image force field created on a template plane over the image plane. This force is more adaptable to noisy images with complicated geometric shapes.
Recommender Systems for the Conference Paper Assignment Problem
Venue: arXiv cs.IR 2009
Year: 2009

Conference paper assignment, i.e., the task of assigning paper submissions to reviewers, presents multi-faceted issues for recommender systems research. Besides the traditional goal of predicting `who likes what?', a conference management system must take into account aspects such as: reviewer capacity constraints, adequate numbers of reviews for papers, expertise modeling, conflicts of interest, and an overall distribution of assignments that balances reviewer preferences with conference objectives. Among these, issues of modeling preferences and tastes in reviewing have traditionally been studied separately from the optimization of paper-reviewer assignment. In this paper, we present an integrated study of both these aspects. First, due to the paucity of data per reviewer or per paper (relative to other recommender systems applications) we show how we can integrate multiple sources of information to learn paper-reviewer preference models. Second, our models are evaluated not just in terms of prediction accuracy but in terms of the end-assignment quality. Using a linear programming-based assignment optimization formulation, we show how our approach better explores the space of unsupplied assignments to maximize the overall affinities of papers assigned to reviewers. We demonstrate our results on real reviewer preference data from the IEEE ICDM 2007 conference.
Adaptive Process Management in Highly Dynamic and Pervasive Scenarios
Venue: arXiv cs.SE 2009
Year: 2009

Process Management Systems (PMSs) are currently more and more used as a supporting tool for cooperative processes in pervasive and highly dynamic situations, such as emergency situations, pervasive healthcare or domotics/home automation. But in all such situations, designed processes can be easily invalidated since the execution environment may change continuously due to frequent unforeseeable events. This paper aims at illustrating the theoretical framework and the concrete implementation of SmartPM, a PMS that features a set of sound and complete techniques to automatically cope with unplanned exceptions. PMS SmartPM is based on a general framework which adopts the Situation Calculus and Indigolog.
On the relation between size-based termination and semantic labelling
Venue: arXiv cs.LO 2009
Year: 2009

We investigate the relationship between two independently developed termination techniques. On the one hand, sized-types based termination (SBT) uses types annotated with size expressions and Girard's reducibility candidates, and applies on systems using constructor matching only. On the other hand, semantic labelling transforms a rewrite system by annotating each function symbol with the semantics of its arguments, and applies to any rewrite system. First, we introduce a simplified version of SBT for the simply-typed lambda-calculus. Then, we give new proofs of the correctness of SBT using semantic labelling, both in the first and in the higher-order case. As a consequence, we show that SBT can be extended to systems using matching on defined symbols (e.g. associative functions).
The Pattern Matrix Method (Journal Version)
Venue: arXiv cs.CC 2009
Year: 2009

We develop a novel and powerful technique for communication lower bounds, the pattern matrix method. Specifically, fix an arbitrary function f:{0,1}^n->{0,1} and let A_f be the matrix whose columns are each an application of f to some subset of the variables x_1,x_2,...,x_{4n}. We prove that A_f has bounded-error communication complexity Omega(d), where d is the approximate degree of f. This result remains valid in the quantum model, regardless of prior entanglement. In particular, it gives a new and simple proof of Razborov's breakthrough quantum lower bounds for disjointness and other symmetric predicates. We further characterize the discrepancy, approximate rank, and approximate trace norm of A_f in terms of well-studied analytic properties of f, broadly generalizing several recent results on small-bias communication and agnostic learning. The method of this paper has recently enabled important progress in multiparty communication complexity.
As time goes by: Constraint Handling Rules - A survey of CHR research from 1998 to 2007
Venue: arXiv cs.PL 2009
Year: 2009

Constraint Handling Rules (CHR) is a high-level programming language based on multi-headed multiset rewrite rules. Originally designed for writing user-defined constraint solvers, it is now recognized as an elegant general purpose language. CHR-related research has surged during the decade following the previous survey by Fruehwirth. Covering more than 180 publications, this new survey provides an overview of recent results in a wide range of research areas, from semantics and analysis to systems, extensions and applications.
Coarse-grained Dynamic Taint Analysis for Defeating Control and Non-control Data Attacks
Venue: arXiv cs.CR 2009
Year: 2009

Memory corruption attacks remain the primary threat for computer security. Information flow tracking or taint analysis has been proven to be effective against most memory corruption attacks. However, there are two shortcomings with current taint analysis based techniques. First, these techniques cause application slowdown by about 76% thereby limiting their practicality. Second, these techniques cannot handle non-control data attacks i.e., attacks that do not overwrite control data such as return address, but instead overwrite critical application configuration data or user identity data. In this work, to address these problems, we describe a coarse-grained taint analysis technique that uses information flow tracking at the level of application data objects. We propagate a one-bit taint over each application object that is modified by untrusted data thereby reducing the taint management overhead considerably. We performed extensive experimental evaluation of our approach and show that it can detect all critical attacks such as buffer overflows, and format string attacks, including non-control data attacks. Unlike the currently known approaches that can detect such a wide range of attacks, our approach does not require the source code or any hardware extensions. Run-time performance overhead evaluation shows that, on an average, our approach causes application slowdown by only 37% which is an order of magnitude improvement over existing approaches. Finally, since our approach performs run-time binary instrumentation, it is easier to integrate it with existing applications and systems.
Efficient Generation of Craig Interpolants in Satisfiability Modulo Theories
Venue: arXiv cs.LO 2009
Year: 2009

The problem of computing Craig Interpolants has recently received a lot of interest. In this paper, we address the problem of efficient generation of interpolants for some important fragments of first order logic, which are amenable for effective decision procedures, called Satisfiability Modulo Theory solvers. We make the following contributions. First, we provide interpolation procedures for several basic theories of interest: the theories of linear arithmetic over the rationals, difference logic over rationals and integers, and UTVPI over rationals and integers. Second, we define a novel approach to interpolate combinations of theories, that applies to the Delayed Theory Combination approach. Efficiency is ensured by the fact that the proposed interpolation algorithms extend state of the art algorithms for Satisfiability Modulo Theories. Our experimental evaluation shows that the MathSAT SMT solver can produce interpolants with minor overhead in search, and much more efficiently than other competitor solvers.
The Poisson Channel with Side Information
Venue: arXiv cs.IT 2009
Year: 2009

The continuous-time, peak-limited, infinite-bandwidth Poisson channel with spurious counts is considered. It is shown that if the times at which the spurious counts occur are known noncausally to the transmitter but not to the receiver, then the capacity is equal to that of the Poisson channel with no spurious counts. Knowing the times at which the spurious counts occur only causally at the transmitter does not increase capacity.
A Trivial Observation related to Sparse Recovery
Venue: arXiv cs.IT 2009
Year: 2009

We make a trivial modification to the elegant analysis of Garg and Khandekar (\emph{Gradient Descent with Sparsification} ICML 2009) that replaces the standard Restricted Isometry Property (RIP), with another RIP-type property (which could be simpler than the RIP, but we are not sure; it could be as hard as the RIP to check, thereby rendering this little writeup totally worthless).
Physical Layer Security: Coalitional Games for Distributed Cooperation
Venue: arXiv cs.IT 2009
Year: 2009

Cooperation between wireless network nodes is a promising technique for improving the physical layer security of wireless transmission, in terms of secrecy capacity, in the presence of multiple eavesdroppers. While existing physical layer security literature answered the question "what are the link-level secrecy capacity gains from cooperation?", this paper attempts to answer the question of "how to achieve those gains in a practical decentralized wireless network and in the presence of a secrecy capacity cost for information exchange?". For this purpose, we model the physical layer security cooperation problem as a coalitional game with non-transferable utility and propose a distributed algorithm for coalition formation. Through the proposed algorithm, the wireless users can autonomously cooperate and self-organize into disjoint independent coalitions, while maximizing their secrecy capacity taking into account the security costs during information exchange. We analyze the resulting coalitional structures, discuss their properties, and study how the users can self-adapt the network topology to environmental changes such as mobility. Simulation results show that the proposed algorithm allows the users to cooperate and self-organize while improving the average secrecy capacity per user up to 25.32% relative to the non-cooperative case.
A New Approach to Manage QoS in Distributed Multimedia Systems
Venue: arXiv cs.MM 2009
Year: 2009

Dealing with network congestion is a criterion used to enhance quality of service (QoS) in distributed multimedia systems. The existing solutions for the problem of network congestion ignore scalability considerations because they maintain a separate classification for each video stream. In this paper, we propose a new method allowing to control QoS provided to clients according to the network congestion, by discarding some frames when needed. The technique proposed, called (m,k)-frame, is scalable with little degradation in application performances. (m,k)-frame method is issued from the notion of (m,k)-firm realtime constraints which means that among k invocations of a task, m invocations must meet their deadline. Our simulation studies show the usefulness of (m,k)-frame method to adapt the QoS to the real conditions in a multimedia application, according to the current system load. Notably, the system must adjust the QoS provided to active clients1 when their number varies, i.e. dynamic arrival of clients.
Concept-based Recommendations for Internet Advertisement
Venue: arXiv cs.AI 2009
Year: 2009

The problem of detecting terms that can be interesting to the advertiser is considered. If a company has already bought some advertising terms which describe certain services, it is reasonable to find out the terms bought by competing companies. A part of them can be recommended as future advertising terms to the company. The goal of this work is to propose better interpretable recommendations based on FCA and association rules.
Dispositif de supervision pour les tuteurs impliqués dans un apprentissage à la gestion de projets
Venue: arXiv cs.CY 2009
Year: 2009

This article presents results of the observation of a project management teaching-by-project course. It describe return of experience not only of student but also of tutors one years after the course. Many problems are identified like individual student evaluation, tutor distance, lake of coordination, lake of communication. We ask tutor about the pertinence of an instrumental solution, based upon dashboard, to solve problems of coordination and evaluation identified. We made the hypothese that a cognitive tool will improve too the knowledge construction and the learning process.
Collaborative filtering with diffusion-based similarity on tripartite graphs
Venue: arXiv cs.IR 2009
Year: 2009

Collaborative tags are playing more and more important role for the organization of information systems. In this paper, we study a personalized recommendation model making use of the ternary relations among users, objects and tags. We propose a measure of user similarity based on his preference and tagging information. Two kinds of similarities between users are calculated by using a diffusion-based process, which are then integrated for recommendation. We test the proposed method in a standard collaborative filtering framework with three metrics: ranking score, Recall and Precision, and demonstrate that it performs better than the commonly used cosine similarity.
Statistical Analysis of Privacy and Anonymity Guarantees in Randomized Security Protocol Implementations
Venue: arXiv cs.CR 2009
Year: 2009

Security protocols often use randomization to achieve probabilistic non-determinism. This non-determinism, in turn, is used in obfuscating the dependence of observable values on secret data. Since the correctness of security protocols is very important, formal analysis of security protocols has been widely studied in literature. Randomized security protocols have also been analyzed using formal techniques such as process-calculi and probabilistic model checking. In this paper, we consider the problem of validating implementations of randomized protocols. Unlike previous approaches which treat the protocol as a white-box, our approach tries to verify an implementation provided as a black box. Our goal is to infer the secrecy guarantees provided by a security protocol through statistical techniques. We learn the probabilistic dependency of the observable outputs on secret inputs using Bayesian network. This is then used to approximate the leakage of secret. In order to evaluate the accuracy of our statistical approach, we compare our technique with the probabilistic model checking technique on two examples: crowds protocol and dining crypotgrapher's protocol.
Cryptanalysis of SDES via evolutionary computation techniques
Venue: arXiv cs.CR 2009
Year: 2009

The cryptanalysis of simplified data encryption standard can be formulated as NP-Hard combinatorial problem. The goal of this paper is two fold. First we want to make a study about how evolutionary computation techniques can efficiently solve the NP-Hard combinatorial problem. For achieving this goal we test several evolutionary computation techniques like memetic algorithm, genetic algorithm and simulated annealing for the cryptanalysis of simplified data encryption standard problem (SDES). And second was a comparison between memetic algorithm, genetic algorithm and simulated annealing were made in order to investigate the performance for the cryptanalysis on SDES. The methods were tested and extensive computational results show that memetic algorithm performs better than genetic algorithms and simulated annealing for such type of NP-Hard combinatorial problem. This paper represents our first effort toward efficient memetic algorithm for the cryptanalysis of SDES.
A Comment on Nonextensive Statistical Mechanics
Venue: arXiv cs.IT 2009
Year: 2009

There is a conception that Boltzmann-Gibbs statistics cannot yield the long tail distribution. This is the justification for the intensive research of nonextensive entropies (i.e. Tsallis entropy and others). Here the error that caused this misconception is explained and it is shown that a long tail distribution exists in equilibrium thermodynamics for more than a century.
Asymmetric Quantum Cyclic Codes
Venue: arXiv cs.IT 2009
Year: 2009

It is recently conjectured in quantum information processing that phase-shift errors occur with high probability than qubit-flip errors, hence the former is more disturbing to quantum information than the later one. This leads us to construct asymmetric quantum error controlling codes to protect quantum information over asymmetric channels, $\Pr Z \geq \Pr X$. In this paper we present two generic methods to derive asymmetric quantum cyclic codes using the generator polynomials and defining sets of classical cyclic codes. Consequently, the methods allow us to construct several families of asymmetric quantum BCH, RS, and RM codes. Finally, the methods are used to construct families of asymmetric subsystem codes.
A Novel Two-Staged Decision Support based Threat Evaluation and Weapon Assignment Algorithm, Asset-based Dynamic Weapon Scheduling using Artificial Intelligence Techinques
Venue: arXiv cs.AI 2009
Year: 2009

Surveillance control and reporting (SCR) system for air threats play an important role in the defense of a country. SCR system corresponds to air and ground situation management/processing along with information fusion, communication, coordination, simulation and other critical defense oriented tasks. Threat Evaluation and Weapon Assignment (TEWA) sits at the core of SCR system. In such a system, maximal or near maximal utilization of constrained resources is of extreme importance. Manual TEWA systems cannot provide optimality because of different limitations e.g.surface to air missile (SAM) can fire from a distance of 5Km, but manual TEWA systems are constrained by human vision range and other constraints. Current TEWA systems usually work on target-by-target basis using some type of greedy algorithm thus affecting the optimality of the solution and failing in multi-target scenario. his paper relates to a novel two-staged flexible dynamic decision support based optimal threat evaluation and weapon assignment algorithm for multi-target air-borne threats.