OpenRaiser/Intern-Atlas huggingface dataset:
SODEXO: A System Framework for Deployment and Exploitation of Deceptive Honeybots in Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

As social networking sites such as Facebook and Twitter are becoming increasingly popular, a growing number of malicious attacks, such as phishing and malware, are exploiting them. Among these attacks, social botnets have sophisticated infrastructure that leverages compromised users accounts, known as bots, to automate the creation of new social networking accounts for spamming and malware propagation. Traditional defense mechanisms are often passive and reactive to non-zero-day attacks. In this paper, we adopt a proactive approach for enhancing security in social networks by infiltrating botnets with honeybots. We propose an integrated system named SODEXO which can be interfaced with social networking sites for creating deceptive honeybots and leveraging them for gaining information from botnets. We establish a Stackelberg game framework to capture strategic interactions between honeybots and botnets, and use quantitative methods to understand the tradeoffs of honeybots for their deployment and exploitation in social networks. We design a protection and alert system that integrates both microscopic and macroscopic models of honeybots and optimally determines the security strategies for honeybots. We corroborate the proposed mechanism with extensive simulations and comparisons with passive defenses.
Redundant Sudoku Rules
Venue: arXiv cs.AI 2012
Year: 2012

The rules of Sudoku are often specified using twenty seven \texttt{all\_different} constraints, referred to as the {\em big} \mrules. Using graphical proofs and exploratory logic programming, the following main and new result is obtained: many subsets of six of these big \mrules are redundant (i.e., they are entailed by the remaining twenty one \mrules), and six is maximal (i.e., removing more than six \mrules is not possible while maintaining equivalence). The corresponding result for binary inequality constraints, referred to as the {\em small} \mrules, is stated as a conjecture.
File system on CRDT
Venue: arXiv cs.DC 2012
Year: 2012

In this report we show how to manage a distributed hierarchical structure representing a file system. This structure is optimistically replicated, each user work on his local replica, and updates are sent to other replica. The different replicas eventually observe same view of file systems. At this stage, conflicts between updates are very common. We claim that conflict resolution should rely as little as possible on users. In this report we propose a simple and modular solution to resolve these problems and maintain data consistency.
Composition of Modular Telemetry System with Interval Multiset Estimates
Venue: arXiv cs.SY 2012
Year: 2012

The paper describes combinatorial synthesis approach with interval multset estimates of system elements for modeling, analysis, design, and improvement of a modular telemetry system. Morphological (modular) system design and improvement are considered as composition of the telemetry system elements (components) configuration. The solving process is based on Hierarchical Morphological Multicriteria Design (HMMD): (i) multicriteria selection of alternatives for system components, (ii) synthesis of the selected alternatives into a resultant combination (while taking into account quality of the alternatives above and their compatibility). Interval multiset estimates are used for assessment of design alternatives for telemetry system elements. Two additional systems problems are examined: (a) improvement of the obtained solutions, (b) aggregation of the obtained solutions into a resultant system configuration. The improvement and aggregation processes are based on multiple choice problem with interval multiset estimates. Numerical examples for an on-board telemetry subsystem illustrate the design and improvement processes.
Coding Delay Analysis of Dense and Chunked Network Codes over Line Networks
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we analyze the coding delay and the average coding delay of random linear network codes (a.k.a. dense codes) and chunked codes (CC), which are an attractive alternative to dense codes due to their lower complexity, over line networks with Bernoulli losses and deterministic regular or Poisson transmissions. Our results, which include upper bounds on the delay and the average delay, are (i) for dense codes, in some cases more general, and in some other cases tighter, than the existing bounds, and provide a more clear picture of the speed of convergence of dense codes to the (min-cut) capacity of line networks; and (ii) the first of their kind for CC over networks with such probabilistic traffics. In particular, these results demonstrate that a stand-alone CC or a precoded CC provide a better tradeoff between the computational complexity and the convergence speed to the network capacity over the probabilistic traffics compared to arbitrary deterministic traffics which have previously been studied in the literature.
Information Embedding on Actions
Venue: arXiv cs.IT 2012
Year: 2012

The problem of optimal actuation for channel and source coding was recently formulated and solved in a number of relevant scenarios. In this class of models, actions are taken at encoders or decoders, either to acquire side information in an efficient way or to control or probe effectively the channel state. In this paper, the problem of embedding information on the actions is studied for both the source and the channel coding set-ups. In both cases, a decoder is present that observes only a function of the actions taken by an encoder or a decoder of an action-dependent point-to-point link. For the source coding model, this decoder wishes to reconstruct a lossy version of the source being transmitted over the point-to-point link, while for the channel coding problem the decoder wishes to retrieve a portion of the message conveyed over the link. For the problem of source coding with actions taken at the decoder, a single letter characterization of the set of all achievable tuples of rate, distortions at the two decoders and action cost is derived, under the assumption that the mentioned decoder observes a function of the actions non-causally, strictly causally or causally. A special case of the problem in which the actions are taken by the encoder is also solved. A single-letter characterization of the achievable capacity-cost region is then obtained for the channel coding set-up with actions. Examples are provided that shed light into the effect of information embedding on the actions for the action-dependent source and channel coding problems.
A Unified Approach of Observability Analysis for Airborne SLAM
Venue: arXiv cs.RO 2012
Year: 2012

Observability is a key aspect of the state estimation problem of SLAM, However, the dimension and variables of SLAM system might be changed with new features, to which little attention is paid in the previous work. In this paper, a unified approach of observability analysis for SLAM system is provided, whether the dimension and variables of SLAM system are changed or not, we can use this approach to analyze the local or total observability of the SLAM system.
Achieving Approximate Soft Clustering in Data Streams
Venue: arXiv cs.DS 2012
Year: 2012

In recent years, data streaming has gained prominence due to advances in technologies that enable many applications to generate continuous flows of data. This increases the need to develop algorithms that are able to efficiently process data streams. Additionally, real-time requirements and evolving nature of data streams make stream mining problems, including clustering, challenging research problems. In this paper, we propose a one-pass streaming soft clustering (membership of a point in a cluster is described by a distribution) algorithm which approximates the "soft" version of the k-means objective function. Soft clustering has applications in various aspects of databases and machine learning including density estimation and learning mixture models. We first achieve a simple pseudo-approximation in terms of the "hard" k-means algorithm, where the algorithm is allowed to output more than $k$ centers. We convert this batch algorithm to a streaming one (using an extension of the k-means++ algorithm recently proposed) in the "cash register" model. We also extend this algorithm when the clustering is done over a moving window in the data stream.
Sum-Rate Optimization in a Two-Way Relay Network with Buffering
Venue: arXiv cs.IT 2012
Year: 2012

A Relay Station (RS) uses a buffer to store and process the received data packets before forwarding them. Recently, the buffer has been exploited in one-way relaying to opportunistically schedule the two different links according to their channel quality. The intuition is that, if the channel to the destination is poor, then RS stores more data from the source, in order to use it when the channel to the destination is good. We apply this intuition to the case of half-duplex two-way relaying, where the interactions among the buffers and the links become more complex. We investigate the sum-rate maximization problem in the Time Division Broadcast (TDBC): the users send signals to the RS in different time slots, the RS decodes and stores messages in the buffers. For downlink transmission, the RS re-encodes and sends using the optimal broadcast strategy. The operation in each time slot is not determined in advance, but depends on the channel state information (CSI). We derive the decision function for adaptive link selection with respect to CSI using the Karush-Kuhn-Tucker (KKT) conditions. The thresholds of the decision function are obtained under Rayleigh fading channel conditions. The numerical results show that the sum-rate of the adaptive link selection protocol with buffering is significantly larger compared to the reference protocol with fixed transmission schedule.
Mimicking Networks and Succinct Representations of Terminal Cuts
Venue: arXiv cs.DS 2012
Year: 2012

Given a large edge-weighted network $G$ with $k$ terminal vertices, we wish to compress it and store, using little memory, the value of the minimum cut (or equivalently, maximum flow) between every bipartition of terminals. One appealing methodology to implement a compression of $G$ is to construct a \emph{mimicking network}: a small network $G'$ with the same $k$ terminals, in which the minimum cut value between every bipartition of terminals is the same as in $G$. This notion was introduced by Hagerup, Katajainen, Nishimura, and Ragde [JCSS '98], who proved that such $G'$ of size at most $2^{2^k}$ always exists. Obviously, by having access to the smaller network $G'$, certain computations involving cuts can be carried out much more efficiently. We provide several new bounds, which together narrow the previously known gap from doubly-exponential to only singly-exponential, both for planar and for general graphs. Our first and main result is that every $k$-terminal planar network admits a mimicking network $G'$ of size $O(k^2 2^{2k})$, which is moreover a minor of $G$. On the other hand, some planar networks $G$ require $|E(G')| \ge Ω(k^2)$. For general networks, we show that certain bipartite graphs only admit mimicking networks of size $|V(G')| \geq 2^{Ω(k)}$, and moreover, every data structure that stores the minimum cut value between all bipartitions of the terminals must use $2^{Ω(k)}$ machine words.
Power Control for Two User Cooperative OFDMA Channels
Venue: arXiv cs.IT 2012
Year: 2012

For a two user cooperative orthogonal frequency division multiple access (OFDMA) system with full channel state information (CSI), we obtain the optimal power allocation (PA) policies which maximize the rate region achievable by a channel adaptive implementation of inter-subchannel block Markov superposition encoding (BMSE), used in conjunction with backwards decoding. We provide the optimality conditions that need to be satisfied by the powers associated with the users' codewords and derive the closed form expressions for the optimal powers. We propose two algorithms that can be used to optimize the powers to achieve any desired rate pair on the rate region boundary: a projected subgradient algorithm, and an iterative waterfilling-like algorithm based on Karush-Kuhn-Tucker (KKT) conditions for optimality, which operates one user at a time and converges much faster. We observe that, utilization of power control to take advantage of the diversity offered by the cooperative OFDMA system, not only leads to a remarkable improvement in achievable rates, but also may help determine how the subchannels have to be instantaneously allocated to various tasks in cooperation.
Concept of the abstract program
Venue: arXiv cs.PL 2012
Year: 2012

The aim of this paper is to alter the abstract definition of the program of the theoretical programming model which has been developed at Eotvos Lorand University for many years in order to investigate methods that support designing correct programs. The motivation of this modification was that the dynamic properties of programs appear in the model. This new definition of the program gives a hand to extend the model with the concept of subprograms while the earlier results of the original programming model are preserved.
Earthquake Scenario Reduction by Symmetry Reasoning
Venue: arXiv cs.AI 2012
Year: 2012

A recently identified problem is that of finding an optimal investment plan for a transportation network, given that a disaster such as an earthquake may destroy links in the network. The aim is to strengthen key links to preserve the expected network connectivity. A network based on the Istanbul highway system has thirty links and therefore a billion scenarios, but it has been estimated that sampling a million scenarios gives reasonable accuracy. In this paper we use symmetry reasoning to reduce the number of scenarios to a much smaller number, making sampling unnecessary. This result can be used to facilitate metaheuristic and exact approaches to the problem.
Guided Grammar Convergence. Full Case Study Report. Generated by converge::Guided
Venue: arXiv cs.PL 2012
Year: 2012

This report is meant to be used as auxiliary material for the guided grammar convergence technique proposed earlier as problem-specific improvement in the topic of convergence of grammars. It contains a narrated MegaL megamodel, as well as full results of the guided grammar convergence experiment on the Factorial Language, with details about each grammar source packaged in a readable form. All formulae used within this document, are generated automatically by the convergence infrastructure in order to avoid any mistakes. The generator source code and the source of the introduction text can be found publicly available in the Software Language Processing Suite repository.
Two player game variant of the Erdos-Szekeres problem
Venue: arXiv cs.CG 2012
Year: 2012

The classical Erdos-Szekeres theorem states that a convex $k$-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex $k$-gon problem, convex $k$-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.
Une approche IDM de transformation exogène de Wright vers Ada
Venue: arXiv cs.SE 2012
Year: 2012

The formal ADL Wright allows to describe the structural and behavioral aspects of abstract software architecture. The behavioral aspects are described in CSP and checked using the model-checker FDR. While the ADL Wright does not offer any means to realize such architectures abstract. The objective of this work is to open up the ADL Wright for Ada through an automated approach based on MDE. To achieve this, we have developed two Ecore meta-models: the meta-model Wright and the partial meta-model of Ada. Moreover, we have designed, built and tested our program Wright2Ada written in ATL to transform software architecture described in Wright to a concurrent program in Ada.
The Effectiveness of Virtual R&D Teams in SMEs: Experiences of Malaysian SMEs
Venue: arXiv cs.OH 2012
Year: 2012

The number of small and medium enterprises (SMEs), especially those involved with research and development (R&D) programs and employed virtual teams to create the greatest competitive advantage from limited labor are increasing. Global and localized virtual R&D teams are believed to have high potential for the growth of SMEs. Due to the fast-growing complexity of new products coupled with new emerging opportunities of virtual teams, a collaborative approach is believed to be the future trend. This research explores the effectiveness of virtuality in SMEs' virtual R&D teams. Online questionnaires were emailed to Malaysian manufacturing SMEs and 74 usable questionnaires were received, representing a 20.8 percent return rate. In order to avoid biases which may result from pre-suggested answers, a series of open-ended questions were retrieved from the experts. This study was focused on analyzing an open-ended question, whereby four main themes were extracted from the experts' recommendations regarding the effectiveness of virtual teams for the growth and performance of SMEs. The findings of this study would be useful to product design managers of SMEs in order to realize the key advantages and significance of virtual R&D teams during the new product development (NPD) process. This in turn, leads to increased effectiveness in new product development's procedure.
Three Degrees of Distance on Twitter
Venue: arXiv cs.SI 2012
Year: 2012

Recent work has found that the propagation of behaviors and sentiments through networks extends in ranges up to 2 to 4 degrees of distance. The regularity with which the same observation is found in dissimilar phenomena has been associated with friction in the propagation process and the instability of link structure that emerges in the dynamic of social networks. We study a contagious behavior, the practice of retweeting, in a setting where neither of those restrictions is present and still found the same result.
Fault-Tolerant Spanners for Doubling Metrics: Better and Simpler
Venue: arXiv cs.DS 2012
Year: 2012

In STOC'95 Arya et al. (1995) conjectured that for any constant dimensional $n$-point Euclidean space, a $(1+\eps)$-spanner with constant degree, hop-diameter $O(\log n)$ and weight $O(\log n) \cdot ω(MST)$ can be built in $O(n \log n)$ time. Recently Elkin and Solomon (technical report, April 2012) proved this conjecture of Arya et al. in the affirmative. In fact, the proof of Elkin and Solomon is more general in two ways. First, it applies to arbitrary doubling metrics. Second, it provides a complete tradeoff between the three involved parameters that is tight (up to constant factors) in the entire range. Subsequently, Chan et al. (technical report, July 2012) provided another proof for Arya et al.'s conjecture, which is simpler than the proof of Elkin and Solomon. Moreover, Chan et al. (2012) also showed that one can build a fault-tolerant (FT) spanner with similar properties. Specifically, they showed that there exists a $k$-FT $(1+\eps)$-spanner with degree $O(k^2)$, hop-diameter $O(\log n)$ and weight $O(k^3 \cdot \log n) \cdot ω(MST)$. The running time of the construction of Chan et al. was not analyzed. In this work we improve the results of Chan et al., using a simpler proof. Specifically, we present a simple proof which shows that a $k$-FT $(1+\eps)$-spanner with degree $O(k^2)$, hop-diameter $O(\log n)$ and weight $O(k^2 \cdot \log n) \cdot ω(MST)$ can be built in $O(n \cdot (\log n + k^2))$ time. Similarly to the constructions of Elkin and Solomon and Chan et al., our construction applies to arbitrary doubling metrics. However, in contrast to the construction of Elkin and Solomon, our construction fails to provide a complete (and tight) tradeoff between the three involved parameters. The construction of Chan et al. has this drawback too. For random point sets in $\mathbb R^d$, we "shave" a factor of $\log n$ from the weight bound.
Traveling the Silk Road: A measurement analysis of a large anonymous online marketplace
Venue: arXiv cs.CY 2012
Year: 2012

We perform a comprehensive measurement analysis of Silk Road, an anonymous, international online marketplace that operates as a Tor hidden service and uses Bitcoin as its exchange currency. We gather and analyze data over eight months between the end of 2011 and 2012, including daily crawls of the marketplace for nearly six months in 2012. We obtain a detailed picture of the type of goods being sold on Silk Road, and of the revenues made both by sellers and Silk Road operators. Through examining over 24,400 separate items sold on the site, we show that Silk Road is overwhelmingly used as a market for controlled substances and narcotics, and that most items sold are available for less than three weeks. The majority of sellers disappears within roughly three months of their arrival, but a core of 112 sellers has been present throughout our measurement interval. We evaluate the total revenue made by all sellers, from public listings, to slightly over USD 1.2 million per month; this corresponds to about USD 92,000 per month in commissions for the Silk Road operators. We further show that the marketplace has been operating steadily, with daily sales and number of sellers overall increasing over our measurement interval. We discuss economic and policy implications of our analysis and results, including ethical considerations for future research in this area.
A Formalization and Proof of the Extended Church-Turing Thesis -Extended Abstract-
Venue: arXiv cs.LO 2012
Year: 2012

We prove the Extended Church-Turing Thesis: Every effective algorithm can be efficiently simulated by a Turing machine. This is accomplished by emulating an effective algorithm via an abstract state machine, and simulating such an abstract state machine by a random access machine, representing data as a minimal term graph.
Novel Modulation Techniques using Isomers as Messenger Molecules for Nano Communication Networks via Diffusion
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose three novel modulation techniques, i.e., concentration-based, molecular-type-based, and molecular-ratio-based, using isomers as messenger molecules for nano communication networks via diffusion. To evaluate achievable rate performance, we compare the proposed tech- niques with conventional insulin based concepts under practical scenarios. Analytical and numerical results confirm that the proposed modulation techniques using isomers achieve higher data transmission rate performance (max 7.5 dB signal-to-noise ratio gain) than the insulin based concepts. We also investigate the tradeoff between messenger sizes and modulation orders and provide guidelines for selecting from among several possible candidates.