OpenRaiser/Intern-Atlas huggingface dataset:
User Awareness Measurement Through Social Engineering
Venue: arXiv cs.CR 2011
Year: 2011

TUBITAK National Research Institute of Electronics and Cryptology (UEKAE) Department of Information Systems Security makes social engineering attacks to Turkish public agencies within the frame of "Information Security Tests" [19]. This paper will make an analysis of the social engineering tests that have been carried out in several Turkish public agencies. The tests include phone calling to sample employees by the social engineer and trying to seize employees' sensitive information by exploiting their good faith. The aim of this research is to figure that the employees in Turkish public agencies have a lack of information security awareness and they compromise the information security principles which should be necessarily applied for any public agencies. Social engineering, both with its low cost and ability to take advantage of low technology, has taken its place in the information security literature as a very effective form of attack [8].
Smart Meter Privacy: A Utility-Privacy Framework
Venue: arXiv cs.IT 2011
Year: 2011

End-user privacy in smart meter measurements is a well-known challenge in the smart grid. The solutions offered thus far have been tied to specific technologies such as batteries or assumptions on data usage. Existing solutions have also not quantified the loss of benefit (utility) that results from any such privacy-preserving approach. Using tools from information theory, a new framework is presented that abstracts both the privacy and the utility requirements of smart meter data. This leads to a novel privacy-utility tradeoff problem with minimal assumptions that is tractable. Specifically for a stationary Gaussian Markov model of the electricity load, it is shown that the optimal utility-and-privacy preserving solution requires filtering out frequency components that are low in power, and this approach appears to encompass most of the proposed privacy approaches.
A theorem proving framework for the formal verification of Web Services Composition
Venue: arXiv cs.LO 2011
Year: 2011

We present a rigorous framework for the composition of Web Services within a higher order logic theorem prover. Our approach is based on the proofs-as-processes paradigm that enables inference rules of Classical Linear Logic (CLL) to be translated into pi-calculus processes. In this setting, composition is achieved by representing available web services as CLL sentences, proving the requested composite service as a conjecture, and then extracting the constructed pi-calculus term from the proof. Our framework, implemented in HOL Light, not only uses an expressive logic that allows us to incorporate multiple Web Services properties in the composition process, but also provides guarantees of soundness and correctness for the composition.
Binary Error Correcting Network Codes
Venue: arXiv cs.IT 2011
Year: 2011

We consider network coding for networks experiencing worst-case bit-flip errors, and argue that this is a reasonable model for highly dynamic wireless network transmissions. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. We propose a new metric for errors under this model. Using this metric, we prove a new Hamming-type upper bound on the network capacity. We also show a commensurate lower bound based on GV-type codes that can be used for error-correction. The codes used to attain the lower bound are non-coherent (do not require prior knowledge of network topology). The end-to-end nature of our design enables our codes to be overlaid on classical distributed random linear network codes. Further, we free internal nodes from having to implement potentially computationally intensive link-by-link error-correction.
Deciding Regularity of Hairpin Completions of Regular Languages in Polynomial Time
Venue: arXiv cs.FL 2011
Year: 2011

The hairpin completion is an operation on formal languages that has been inspired by the hairpin formation in DNA biochemistry and by DNA computing. In this paper we investigate the hairpin completion of regular languages. It is well known that hairpin completions of regular languages are linear context-free and not necessarily regular. As regularity of a (linear) context-free language is not decidable, the question arose whether regularity of a hairpin completion of regular languages is decidable. We prove that this problem is decidable and we provide a polynomial time algorithm. Furthermore, we prove that the hairpin completion of regular languages is an unambiguous linear context-free language and, as such, it has an effectively computable growth function. Moreover, we show that the growth of the hairpin completion is exponential if and only if the growth of the underlying languages is exponential and, in case the hairpin completion is regular, then the hairpin completion and the underlying languages have the same growth indicator.
Cryptovirology: Virus Approach
Venue: arXiv cs.CR 2011
Year: 2011

Traditionally, "Cryptography" is a benediction to information processing and communications, it helps people to store information securely and the private communications over long distances. Cryptovirology is the study of applications of cryptography to build the malicious software. It is an investigation, how modern cryptographic tools and paradigms can be used to strengthen, develop and improve new malicious software attacks. Cryptovirology attacks have been categorized as : give malware enhanced privacy and be more robust against reverse-engineering, secondly give the attacker enhanced anonymity while communicating with deployed malware. This paper presents the idea of "Cryptovirology" which introduce a twist on how cryptography can also be used offensively. Being offensive means, it can be used to mount extortion based attacks that cause loss of access to information, loss of confidentiality, and information leakage, tasks which cryptography usually prevents. Also analyze threats and attacks that misuse of cryptography can cause when combined with fraudulent software (viruses, Trojans). Public-key cryptography is very essential for the attacks that based on cryptovirology. This paper also suggest some of the countermeasures, mechanisms to cope with and prevent such attacks. Even if the attackers actions on the host machine are being monitored, it still cannot be proven beyond reasonable doubt that he or she is the attacker; and it is an "originator-concealing attack". Evidence should be collected from the "author's own system which was used for the attack". These attacks have implications on how the use of cryptographic tools and techniques should be audited and managed in general purpose computing environments, and imply that access to the cryptographic tools should be in well control of the system(such as API routines).
Tensor-Based Link Prediction in Intermittently Connected Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

Through several studies, it has been highlighted that mobility patterns in mobile networks are driven by human behaviors. This effect has been particularly observed in intermittently connected networks like DTN (Delay Tolerant Networks). Given that common social intentions generate similar human behavior, it is relevant to exploit this knowledge in the network protocols design, e.g. to identify the closeness degree between two nodes. In this paper, we propose a temporal link prediction technique for DTN which quantifies the behavior similarity between each pair of nodes and makes use of it to predict future links. Our prediction method keeps track of the spatio-temporal aspects of nodes behaviors organized as a third-order tensor that aims to records the evolution of the network topology. After collapsing the tensor information, we compute the degree of similarity for each pair of nodes using the Katz measure. This metric gives us an indication on the link occurrence between two nodes relying on their closeness. We show the efficiency of this method by applying it on three mobility traces: two real traces and one synthetic trace. Through several simulations, we demonstrate the effectiveness of the technique regarding another approach based on a similarity metric used in DTN. The validity of this method is proven when the computation of score is made in a distributed way (i.e. with local information). We attest that the tensor-based technique is effective for temporal link prediction applied to the intermittently connected networks. Furthermore, we think that this technique can go beyond the realm of DTN and we believe this can be further applied on every case of figure in which there is a need to derive the underlying social structure of a network of mobile users.
Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
Venue: arXiv cs.CV 2011
Year: 2011

We propose a novel algorithm for compressive imaging that exploits both the sparsity and persistence across scales found in the 2D wavelet transform coefficients of natural images. Like other recent works, we model wavelet structure using a hidden Markov tree (HMT) but, unlike other works, ours is based on loopy belief propagation (LBP). For LBP, we adopt a recently proposed "turbo" message passing schedule that alternates between exploitation of HMT structure and exploitation of compressive-measurement structure. For the latter, we leverage Donoho, Maleki, and Montanari's recently proposed approximate message passing (AMP) algorithm. Experiments with a large image database suggest that, relative to existing schemes, our turbo LBP approach yields state-of-the-art reconstruction performance with substantial reduction in complexity.
Gabor frames with rational density
Venue: arXiv cs.IT 2011
Year: 2011

We consider the frame property of the Gabor system G(g, α, β) = {e2πiβnt g(t - αm) : m, n \in Z} for the case of rational oversampling, i.e. α, β \in Q. A 'rational' analogue of the Ron-Shen Gramian is constructed, and prove that for any odd window function g the system G(g, α, β) does not generate a frame if αβ = (n-1)/n. Special attention is paid to the first Hermite function h_1(t) = te^(-πt^2).
Attacks on Local Searching Tools
Venue: arXiv cs.CR 2011
Year: 2011

The Google Desktop Search is an indexing tool, currently in beta testing, designed to allow users fast, intuitive, searching for local files. The principle interface is provided through a local web server which supports an interface similar to Google.com's normal web page. Indexing of local files occurs when the system is idle, and understands a number of common file types. A optional feature is that Google Desktop can integrate a short summary of a local search results with Google.com web searches. This summary includes 30-40 character snippets of local files. We have uncovered a vulnerability that would release private local data to an unauthorized remote entity. Using two different attacks, we expose the small snippets of private local data to a remote third party.
The Information Flow and Capacity of Channels with Noisy Feedback
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider some long-standing problems in communication systems with access to noisy feedback. We introduce a new notion, the residual directed information, to capture the effective information flow (i.e. mutual information between the message and the channel outputs) in the forward channel. In light of this new concept, we investigate discrete memoryless channels (DMC) with noisy feedback and prove that the noisy feedback capacity is not achievable by using any typical closed-loop encoder (non-trivially taking feedback information to produce channel inputs). We then show that the residual directed information can be used to characterize the capacity of channels with noisy feedback. Finally, we provide computable bounds on the noisy feedback capacity, which are characterized by the causal conditional directed information.
Bounds on the Achievable Rate of Noisy feedback Gaussian Channels under Linear Feedback Coding Scheme
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate the additive Gaussian noise channel with noisy feedback. We consider the setup of linear coding of the feedback information and Gaussian signaling of the message (i.e. Cover-Pombra Scheme). Then, we derive the upper and lower bounds on the largest achievable rate for this setup. We show that these two bounds can be obtained by solving two convex optimization problems. Finally, we present some simulations and discussion.
Capacity of Strong and Very Strong Gaussian Interference Relay-without-delay Channels
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study the interference relay-without-delay channel which is an interference channel with a relay helping the communication. We assume the relay's transmit symbol depends not only on its past received symbols but also on its current received symbol, which is an appropriate model for studying amplify-and-forward type relaying when the overall delay spread is much smaller than the inverse of the bandwidth. For the discrete memoryless interference relay-without-delay channel, we show an outer bound using genie-aided outer bounding. For the Gaussian interference relay-without-delay channel, we define strong and very strong interference relay-without-delay channels and propose an achievable scheme based on instantaneous amplify-and-forward (AF) relaying. We also propose two outer bounds for the strong and very strong cases. Using the proposed achievable scheme and outer bounds, we show that our scheme can achieve the capacity exactly when the relay's transmit power is greater than a certain threshold. This is surprising since the conventional AF relaying is usually only asymptotically optimal, not exactly optimal. The proposed scheme can be useful in many practical scenarios due to its optimality as well as its simplicity.
Optimal Power Allocation for OFDM-Based Wire-Tap Channels with Arbitrarily Distributed Inputs
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate power allocation that maximizes the secrecy rate of orthogonal frequency division multiplexing (OFDM) systems under arbitrarily distributed inputs. Considering commonly assumed Gaussian inputs are unrealistic, we focus on secrecy systems with more practical discrete distributed inputs, such as PSK, QAM, etc. While the secrecy rate achieved by Gaussian distributed inputs is concave with respect to the transmit power, we have found and rigorously proved that the secrecy rate is non-concave under any discrete inputs. Hence, traditional convex optimization methods are not applicable any more. To address this non-concave power allocation problem, we propose an efficient algorithm. Its gap from optimality vanishes asymptotically at the rate of $O(1/\sqrt{N})$, and its complexity grows in the order of O(N), where $N$ is the number of sub-carriers. Numerical results are provided to illustrate the efficacy of the proposed algorithm.
Reduced-Complexity Decoder of Long Reed-Solomon Codes Based on Composite Cyclotomic Fourier Transforms
Venue: arXiv cs.IT 2011
Year: 2011

Long Reed-Solomon (RS) codes are desirable for digital communication and storage systems due to their improved error performance, but the high computational complexity of their decoders is a key obstacle to their adoption in practice. As discrete Fourier transforms (DFTs) can evaluate a polynomial at multiple points, efficient DFT algorithms are promising in reducing the computational complexities of syndrome based decoders for long RS codes. In this paper, we first propose partial composite cyclotomic Fourier transforms (CCFTs) and then devise syndrome based decoders for long RS codes over large finite fields based on partial CCFTs. The new decoders based on partial CCFTs achieve a significant saving of computational complexities for long RS codes. Since partial CCFTs have modular and regular structures, the new decoders are suitable for hardware implementations. To further verify and demonstrate the advantages of partial CCFTs, we implement in hardware the syndrome computation block for a $(2720, 2550)$ shortened RS code over GF$(2^{12})$. In comparison to previous results based on Horner's rule, our hardware implementation not only has a smaller gate count, but also achieves much higher throughputs.
Selectivity in Probabilistic Causality: Drawing Arrows from Inputs to Stochastic Outputs
Venue: arXiv cs.AI 2011
Year: 2011

Given a set of several inputs into a system (e.g., independent variables characterizing stimuli) and a set of several stochastically non-independent outputs (e.g., random variables describing different aspects of responses), how can one determine, for each of the outputs, which of the inputs it is influenced by? The problem has applications ranging from modeling pairwise comparisons to reconstructing mental processing architectures to conjoint testing. A necessary and sufficient condition for a given pattern of selective influences is provided by the Joint Distribution Criterion, according to which the problem of "what influences what" is equivalent to that of the existence of a joint distribution for a certain set of random variables. For inputs and outputs with finite sets of values this criterion translates into a test of consistency of a certain system of linear equations and inequalities (Linear Feasibility Test) which can be performed by means of linear programming. The Joint Distribution Criterion also leads to a metatheoretical principle for generating a broad class of necessary conditions (tests) for diagrams of selective influences. Among them is the class of distance-type tests based on the observation that certain functionals on jointly distributed random variables satisfy triangle inequality.
Upward Point Set Embeddability for Convex Point Sets is in $P$
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we present a polynomial dynamic programming algorithm that tests whether a $n$-vertex directed tree $T$ has an upward planar embedding into a convex point-set $S$ of size $n$. Further, we extend our approach to the class of outerplanar digraphs. This nontrivial and surprising result implies that any given digraph can be efficiently tested for an upward planar embedding into a given convex point set.
Cooperative Packet Routing using Mutual Information Accumulation
Venue: arXiv cs.IT 2011
Year: 2011

We consider the resource allocation problem in cooperative wireless networks wherein nodes perform mutual information accumulation. We consider a unicast setting and arbitrary arrival processes at the source node. Source arrivals can be broken down into numerous packets to better exploit the spatial and temporal diversity of the routes available in the network. We devise a linear-program-based algorithm which allocates network resource to meet a certain transmission objective. Given a network, a source with multiple arriving packets and a destination, our algorithm generates a policy that regulates which nodes should participate in transmitting which packets, when and with what resource. By routing different packets through different nodes the policy exploits spatial route diversity, and by sequencing packet transmissions along the same route it exploits temporal route diversity.
On the average sensitivity of laced Boolean functions
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we obtain the average sensitivity of the laced Boolean functions. This confirms a conjecture of Shparlinski. We also compute the weights of the laced Boolean functions and show that they are almost balanced.
Finding Similar/Diverse Solutions in Answer Set Programming
Venue: arXiv cs.AI 2011
Year: 2011

For some computational problems (e.g., product configuration, planning, diagnosis, query answering, phylogeny reconstruction) computing a set of similar/diverse solutions may be desirable for better decision-making. With this motivation, we studied several decision/optimization versions of this problem in the context of Answer Set Programming (ASP), analyzed their computational complexity, and introduced offline/online methods to compute similar/diverse solutions of such computational problems with respect to a given distance function. All these methods rely on the idea of computing solutions to a problem by means of finding the answer sets for an ASP program that describes the problem. The offline methods compute all solutions in advance using the ASP formulation of the problem with an ASP solver, like Clasp, and then identify similar/diverse solutions using clustering methods. The online methods compute similar/diverse solutions following one of the three approaches: by reformulating the ASP representation of the problem to compute similar/diverse solutions at once using an ASP solver; by computing similar/diverse solutions iteratively (one after other) using an ASP solver; by modifying the search algorithm of an ASP solver to compute similar/diverse solutions incrementally. We modified Clasp to implement the last online method and called it Clasp-NK. In the first two online methods, the given distance function is represented in ASP; in the last one it is implemented in C++. We showed the applicability and the effectiveness of these methods on reconstruction of similar/diverse phylogenies for Indo-European languages, and on several planning problems in Blocks World. We observed that in terms of computational efficiency the last online method outperforms the others; also it allows us to compute similar/diverse solutions when the distance function cannot be represented in ASP.
On the Performance of MPI-OpenMP on a 12 nodes Multi-core Cluster
Venue: arXiv cs.DC 2011
Year: 2011

With the increasing number of Quad-Core-based clusters and the introduction of compute nodes designed with large memory capacity shared by multiple cores, new problems related to scalability arise. In this paper, we analyze the overall performance of a cluster built with nodes having a dual Quad-Core Processor on each node. Some benchmark results are presented and some observations are mentioned when handling such processors on a benchmark test. A Quad-Core-based cluster's complexity arises from the fact that both local communication and network communications between the running processes need to be addressed. The potentials of an MPI-OpenMP approach are pinpointed because of its reduced communication overhead. At the end, we come to a conclusion that an MPI-OpenMP solution should be considered in such clusters since optimizing network communications between nodes is as important as optimizing local communications between processors in a multi-core cluster.
Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
Venue: arXiv cs.CC 2011
Year: 2011

We introduce an idea called anti-gadgets in complexity reductions. These combinatorial gadgets have the effect of erasing the presence of some other graph fragment, as if we had managed to include a negative copy of a graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function $Z(G)$ on 3-regular directed graphs $G$, where each edge is given a complex-valued binary function $f: \{0,1\}^2 \rightarrow \mathbb{C}$. We show that \[Z(G) = \sum_{σ: V(G) \to \{0,1\}} \prod_{(u,v) \in E(G)} f(σ(u), σ(v)),\] is either computable in polynomial time or #P-hard, depending explicitly on $f$.