OpenRaiser/Intern-Atlas huggingface dataset:
CloneCloud: Boosting Mobile Device Applications Through Cloud Clone Execution
Venue: arXiv cs.DC 2010
Year: 2010

Mobile applications are becoming increasingly ubiquitous and provide ever richer functionality on mobile devices. At the same time, such devices often enjoy strong connectivity with more powerful machines ranging from laptops and desktops to commercial clouds. This paper presents the design and implementation of CloneCloud, a system that automatically transforms mobile applications to benefit from the cloud. The system is a flexible application partitioner and execution runtime that enables unmodified mobile applications running in an application-level virtual machine to seamlessly off-load part of their execution from mobile devices onto device clones operating in a computational cloud. CloneCloud uses a combination of static analysis and dynamic profiling to optimally and automatically partition an application so that it migrates, executes in the cloud, and re-integrates computation in a fine-grained manner that makes efficient use of resources. Our evaluation shows that CloneCloud can achieve up to 21.2x speedup of smartphone applications we tested and it allows different partitioning for different inputs and networks.
Sensor Management for Tracking in Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

We study the problem of tracking an object moving through a network of wireless sensors. In order to conserve energy, the sensors may be put into a sleep mode with a timer that determines their sleep duration. It is assumed that an asleep sensor cannot be communicated with or woken up, and hence the sleep duration needs to be determined at the time the sensor goes to sleep based on all the information available to the sensor. Having sleeping sensors in the network could result in degraded tracking performance, therefore, there is a tradeoff between energy usage and tracking performance. We design sleeping policies that attempt to optimize this tradeoff and characterize their performance. As an extension to our previous work in this area [1], we consider generalized models for object movement, object sensing, and tracking cost. For discrete state spaces and continuous Gaussian observations, we derive a lower bound on the optimal energy-tracking tradeoff. It is shown that in the low tracking error regime, the generated policies approach the derived lower bound.
Evaluating Call-By-Need on the Control Stack
Venue: arXiv cs.PL 2010
Year: 2010

Ariola and Felleisen's call-by-need λ-calculus replaces a variable occurrence with its value at the last possible moment. To support this gradual notion of substitution, function applications-once established-are never discharged. In this paper we show how to translate this notion of reduction into an abstract machine that resolves variable references via the control stack. In particular, the machine uses the static address of a variable occurrence to extract its current value from the dynamic control stack.
Retrospective Interference Alignment
Venue: arXiv cs.IT 2010
Year: 2010

We explore similarities and differences in recent works on blind interference alignment under different models such as staggered block fading model and the delayed CSIT model. In particular we explore the possibility of achieving interference alignment with delayed CSIT when the transmitters are distributed. Our main contribution is an interference alignment scheme, called retrospective interference alignment in this work, that is specialized to settings with distributed transmitters. With this scheme we show that the 2 user X channel with only delayed channel state information at the transmitters can achieve 8/7 DoF, while the interference channel with 3 users is able to achieve 9/8 DoF. We also consider another setting where delayed channel output feedback is available to transmitters. In this setting the X channel and the 3 user interference channel are shown to achieve 4/3 and 6/5 DoF, respectively.
Preventing SQL Injection through Automatic Query Sanitization with ASSIST
Venue: arXiv cs.SE 2010
Year: 2010

Web applications are becoming an essential part of our everyday lives. Many of our activities are dependent on the functionality and security of these applications. As the scale of these applications grows, injection vulnerabilities such as SQL injection are major security challenges for developers today. This paper presents the technique of automatic query sanitization to automatically remove SQL injection vulnerabilities in code. In our technique, a combination of static analysis and program transformation are used to automatically instrument web applications with sanitization code. We have implemented this technique in a tool named ASSIST (Automatic and Static SQL Injection Sanitization Tool) for protecting Java-based web applications. Our experimental evaluation showed that our technique is effective against SQL injection vulnerabilities and has a low overhead.
Relational Constraint Driven Test Case Synthesis for Web Applications
Venue: arXiv cs.SE 2010
Year: 2010

This paper proposes a relational constraint driven technique that synthesizes test cases automatically for web applications. Using a static analysis, servlets can be modeled as relational transducers, which manipulate backend databases. We present a synthesis algorithm that generates a sequence of HTTP requests for simulating a user session. The algorithm relies on backward symbolic image computation for reaching a certain database state, given a code coverage objective. With a slight adaptation, the technique can be used for discovering workflow attacks on web applications.
Analysis and Verification of Service Interaction Protocols - A Brief Survey
Venue: arXiv cs.SE 2010
Year: 2010

Modeling and analysis of interactions among services is a crucial issue in Service-Oriented Computing. Composing Web services is a complicated task which requires techniques and tools to verify that the new system will behave correctly. In this paper, we first overview some formal models proposed in the literature to describe services. Second, we give a brief survey of verification techniques that can be used to analyse services and their interaction. Last, we focus on the realizability and conformance of choreographies.
A Test Automation Framework for Mercury
Venue: arXiv cs.LO 2010
Year: 2010

This paper presents a test automation framework for Mercury programs. We developed a method that generates runnable Mercury code from a formalized test suite, and which code provides a report on execution about the success of test cases. We also developed a coverage tool for the framework, which identifies and provide a visualization of the reached parts of the program when executing a given test suite.
Handover Control for WCDMA Femtocell Networks
Venue: arXiv cs.NI 2010
Year: 2010

The ability to seamlessly switch between the macro networks and femtocell networks is a key driver for femtocell network deployment. The handover procedures for the integrated femtocell/macrocell networks differ from the existing handovers. Some modifications of existing network and protocol architecture for the integration of femtocell networks with the existing macrocell networks are also essential. These modifications change the signal flow for handover procedures due to different 2-tier cell (macrocell and femtocell) environment. The handover between two networks should be performed with minimum signaling. A frequent and unnecessary handover is another problem for hierarchical femtocell/macrocell network environment that must be minimized. This work studies the details mobility management schemes for small and medium scale femtocell network deployment. To do that, firstly we present two different network architectures for small scale and medium scale WCDMA femtocell deployment. The details handover call flow for these two network architectures and CAC scheme to minimize the unnecessary handovers are proposed for the integrated femtocell/macrocell networks. The numerical analysis for the proposed M/M/N/N queuing scheme and the simulation results of the proposed CAC scheme demonstrate the handover call control performances for femtocell environment.
Quantifying Information Leakage in Finite Order Deterministic Programs
Venue: arXiv cs.CR 2010
Year: 2010

Information flow analysis is a powerful technique for reasoning about the sensitive information exposed by a program during its execution. While past work has proposed information theoretic metrics (e.g., Shannon entropy, min-entropy, guessing entropy, etc.) to quantify such information leakage, we argue that some of these measures not only result in counter-intuitive measures of leakage, but also are inherently prone to conflicts when comparing two programs P1 and P2 -- say Shannon entropy predicts higher leakage for program P1, while guessing entropy predicts higher leakage for program P2. This paper presents the first attempt towards addressing such conflicts and derives solutions for conflict-free comparison of finite order deterministic programs.
An Analysis of Transaction and Joint-patent Application Networks
Venue: arXiv cs.SI 2010
Year: 2010

Many firms these days are opting to specialize rather than generalize as a way of maintaining their competitiveness. Consequently, they cannot rely solely on themselves, but must cooperate by combining their advantages. To obtain the actual condition for this cooperation, a multi-layered network based on two different types of data was investigated. The first type was transaction data from Japanese firms. The network created from the data included 961,363 firms and 7,808,760 links. The second type of data were from joint-patent applications in Japan. The joint-patent application network included 54,197 nodes and 154,205 links. These two networks were merged into one network. The first anaysis was based on input-output tables and three different tables were compared. The correlation coefficients between tables revealed that transactions were more strongly tied to joint-patent applications than the total amount of money. The total amount of money and transactions have few relationships and these are probably connected to joint-patent applications in different mechanisms. The second analysis was conducted based on the p* model. Choice, multiplicity, reciprocity, multi-reciprocity and transitivity configurations were evaluated. Multiplicity and reciprocity configurations were significant in all the analyzed industries. The results for multiplicity meant that transactions and joint-patent application links were closely related. Multi-reciprocity and transitivity configurations were significant in some of the analyzed industries. It was difficult to find any common characteristics in the industries. Bayesian networks were used in the third analysis. The learned structure revealed that if a transaction link between two firms is known, the categories of firms' industries do not affect to the existence of a patent link.
A Middleware road towards Web (Grid) Services
Venue: arXiv cs.DC 2010
Year: 2010

Middleware technologies is a very big field, containing a strong already done research as well as the currently running research to confirm already done research's results and the to have some new solution by theoretical as well as the experimental (practical) way. This document has been produced by Zeeshan Ahmed (Student: Connectivity Software Technologies Blekinge Institute of Technologies). This describes the research already done in the field of middleware technologies including Web Services, Grid Computing, Grid Services and Open Grid Service Infrastructure & Architecture. This document concludes with the overview of Web (Grid) Service, Chain of Web (Grid) Services and the necessary security issue.
A Versatile Algorithm to Generate Various Combinatorial Structures
Venue: arXiv cs.DS 2010
Year: 2010

Algorithms to generate various combinatorial structures find tremendous importance in computer science. In this paper, we begin by reviewing an algorithm proposed by Rohl that generates all unique permutations of a list of elements which possibly contains repetitions, taking some or all of the elements at a time, in any imposed order. The algorithm uses an auxiliary array that maintains the number of occurrences of each unique element in the input list. We provide a proof of correctness of the algorithm. We then show how one can efficiently generate other combinatorial structures like combinations, subsets, n-Parenthesizations, derangements and integer partitions & compositions with minor changes to the same algorithm.
Dist-Orc: A Rewriting-based Distributed Implementation of Orc with Formal Analysis
Venue: arXiv cs.LO 2010
Year: 2010

Orc is a theory of orchestration of services that allows structured programming of distributed and timed computations. Several formal semantics have been proposed for Orc, including a rewriting logic semantics developed by the authors. Orc also has a fully fledged implementation in Java with functional programming features. However, as with descriptions of most distributed languages, there exists a fairly substantial gap between Orc's formal semantics and its implementation, in that: (i) programs in Orc are not easily deployable in a distributed implementation just by using Orc's formal semantics, and (ii) they are not readily formally analyzable at the level of a distributed Orc implementation. In this work, we overcome problems (i) and (ii) for Orc. Specifically, we describe an implementation technique based on rewriting logic and Maude that narrows this gap considerably. The enabling feature of this technique is Maude's support for external objects through TCP sockets. We describe how sockets are used to implement Orc site calls and returns, and to provide real-time timing information to Orc expressions and sites. We then show how Orc programs in the resulting distributed implementation can be formally analyzed at a reasonable level of abstraction by defining an abstract model of time and the socket communication infrastructure, and discuss the assumptions under which the analysis can be deemed correct. Finally, the distributed implementation and the formal analysis methodology are illustrated with a case study.
Extending the Real-Time Maude Semantics of Ptolemy to Hierarchical DE Models
Venue: arXiv cs.LO 2010
Year: 2010

This paper extends our Real-Time Maude formalization of the semantics of flat Ptolemy II discrete-event (DE) models to hierarchical models, including modal models. This is a challenging task that requires combining synchronous fixed-point computations with hierarchical structure. The synthesis of a Real-Time Maude verification model from a Ptolemy II DE model, and the formal verification of the synthesized model in Real-Time Maude, have been integrated into Ptolemy II, enabling a model-engineering process that combines the convenience of Ptolemy II DE modeling and simulation with formal verification in Real-Time Maude.
Lightweight Time Modeling in Timed Creol
Venue: arXiv cs.PL 2010
Year: 2010

Creol is an object-oriented modeling language in which inherently concurrent objects exchange asynchronous method calls. The operational semantics of Creol is written in an actor-based style, formulated in rewriting logic. The operational semantics yields a language interpreter in the Maude system, which can be used to analyze models. Recently, Creol has been applied to the modeling of systems with radio communication, such as sensor systems. With radio communication, messages expire and, if sent simultaneously, they may collide in the air. In order to capture these and other properties of distributed systems, we extended Creol's operational semantics with a notion of time. We exploit the framework of a language interpreter to use a lightweight notion of time, in contrast to that needed for a general purpose specification language. This paper presents a timed extension of Creol, including the semantics and the implementation strategy, and discusses its properties using an extended example. The approach can be generalized to other concurrent object or actor-based systems.
The Sorting Buffer Problem is NP-hard
Venue: arXiv cs.DS 2010
Year: 2010

We consider the offline sorting buffer problem. The input is a sequence of items of different types. All items must be processed one by one by a server. The server is equipped with a random-access buffer of limited capacity which can be used to rearrange items. The problem is to design a scheduling strategy that decides upon the order in which items from the buffer are sent to the server. Each type change incurs unit cost, and thus, the cost minimizing objective is to minimize the total number of type changes for serving the entire sequence. This problem is motivated by various applications in manufacturing processes and computer science, and it has attracted significant attention in the last few years. The main focus has been on online competitive algorithms. Surprisingly little is known on the basic offline problem. In this paper, we show that the sorting buffer problem with uniform cost is NP-hard and, thus, close one of the most fundamental questions for the offline problem. On the positive side, we give an O(1)-approximation algorithm when the scheduler is given a buffer only slightly larger than double the original size. We also give a dynamic programming algorithm for the special case of buffer size two that solves the problem exactly in linear time, improving on the standard DP which runs in cubic time.
Adding a referee to an interconnection network: What can(not) be computed in one round
Venue: arXiv cs.CC 2010
Year: 2010

In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes -which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3? cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs.
On Repetition Protocols and Power Control for Multiple Access Block-Fading Channels
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we study the long-term throughput performance of repetition protocols coupled with power control for multiple access block-fading channels. We propose to use the feedback bits to inform the transmitter about the decoding status and the instantaneous channel quality. We determine the throughput of simple and practically inspired protocols; we show remarkable throughput improvements, especially at low and moderate SNR, when compared to protocols where the feedback bits are used for acknowledgment only or for power control only; we show that the throughput is very close to the ultimate ergodic multi-user water-filling capacity for small number of feedback bits and/or retransmissions. For symmetric Rayleigh fading channels, numerical results show that the throughput improvement is mainly due to the ability to perform a power control, rather than to retransmit.
A new closed-loop output error method for parameter identification of robot dynamics
Venue: arXiv cs.RO 2010
Year: 2010

Off-line robot dynamic identification methods are mostly based on the use of the inverse dynamic model, which is linear with respect to the dynamic parameters. This model is sampled while the robot is tracking reference trajectories that excite the system dynamics. This allows using linear least-squares techniques to estimate the parameters. The efficiency of this method has been proved through the experimental identification of many prototypes and industrial robots. However, this method requires the joint force/torque and position measurements and the estimate of the joint velocity and acceleration, through the bandpass filtering of the joint position at high sampling rates. The proposed new method requires only the joint force/torque measurement. It is a closed-loop output error method where the usual joint position output is replaced by the joint force/torque. It is based on a closed-loop simulation of the robot using the direct dynamic model, the same structure of the control law, and the same reference trajectory for both the actual and the simulated robot. The optimal parameters minimize the 2-norm of the error between the actual force/torque and the simulated force/torque. This is a non-linear least-squares problem which is dramatically simplified using the inverse dynamic model to obtain an analytical expression of the simulated force/torque, linear in the parameters. A validation experiment on a 2 degree-of-freedom direct drive robot shows that the new method is efficient.
Fastest Distributed Consensus on Star-Mesh Hybrid Sensor Networks
Venue: arXiv cs.IT 2010
Year: 2010

Solving Fastest Distributed Consensus (FDC) averaging problem over sensor networks with different topologies has received some attention recently and one of the well known topologies in this issue is star-mesh hybrid topology. Here in this work we present analytical solution for the problem of FDC algorithm by means of stratification and semidefinite programming, for the Star-Mesh Hybrid network with K-partite core (SMHK) which has rich symmetric properties. Also the variations of asymptotic and per step convergence rate of SMHK network versus its topological parameters have been studied numerically.
Sequential item pricing for unlimited supply
Venue: arXiv cs.GT 2010
Year: 2010

We investigate the extent to which price updates can increase the revenue of a seller with little prior information on demand. We study prior-free revenue maximization for a seller with unlimited supply of n item types facing m myopic buyers present for k < log n days. For the static (k = 1) case, Balcan et al. [2] show that one random item price (the same on each item) yields revenue within a Θ(log m + log n) factor of optimum and this factor is tight. We define the hereditary maximizers property of buyer valuations (satisfied by any multi-unit or gross substitutes valuation) that is sufficient for a significant improvement of the approximation factor in the dynamic (k > 1) setting. Our main result is a non-increasing, randomized, schedule of k equal item prices with expected revenue within a O((log m + log n) / k) factor of optimum for private valuations with hereditary maximizers. This factor is almost tight: we show that any pricing scheme over k days has a revenue approximation factor of at least (log m + log n) / (3k). We obtain analogous matching lower and upper bounds of Θ((log n) / k) if all valuations have the same maximum. We expect our upper bound technique to be of broader interest; for example, it can significantly improve the result of Akhlaghpour et al. [1]. We also initiate the study of revenue maximization given allocative externalities (i.e. influences) between buyers with combinatorial valuations. We provide a rather general model of positive influence of others' ownership of items on a buyer's valuation. For affine, submodular externalities and valuations with hereditary maximizers we present an influence-and-exploit (Hartline et al. [13]) marketing strategy based on our algorithm for private valuations. This strategy preserves our approximation factor, despite an affine increase (due to externalities) in the optimum revenue.