OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Data Attacks on Power Grids: Leveraging Detection & Measurement Jamming
Venue: arXiv cs.CR 2015
Year: 2015

Meter measurements in the power grid are susceptible to manipulation by adversaries, that can lead to errors in state estimation. This paper presents a general framework to study attacks on state estimation by adversaries capable of injecting bad-data into measurements and further, of jamming their reception. Through these two techniques, a novel `detectable jamming' attack is designed that changes the state estimation despite failing bad-data detection checks. Compared to commonly studied `hidden' data attacks, these attacks have lower costs and a wider feasible operating region. It is shown that the entire domain of jamming costs can be divided into two regions, with distinct graph-cut based formulations for the design of the optimal attack. The most significant insight arising from this result is that the adversarial capability to jam measurements changes the optimal 'detectable jamming' attack design only if the jamming cost is less than half the cost of bad-data injection. A polynomial time approximate algorithm for attack vector construction is developed and its efficacy in attack design is demonstrated through simulations on IEEE test systems.
PALPAS - PAsswordLess PAssword Synchronization
Venue: arXiv cs.CR 2015
Year: 2015

Tools that synchronize passwords over several user devices typically store the encrypted passwords in a central online database. For encryption, a low-entropy, password-based key is used. Such a database may be subject to unauthorized access which can lead to the disclosure of all passwords by an offline brute-force attack. In this paper, we present PALPAS, a secure and user-friendly tool that synchronizes passwords between user devices without storing information about them centrally. The idea of PALPAS is to generate a password from a high entropy secret shared by all devices and a random salt value for each service. Only the salt values are stored on a server but not the secret. The salt enables the user devices to generate the same password but is statistically independent of the password. In order for PALPAS to generate passwords according to different password policies, we also present a mechanism that automatically retrieves and processes the password requirements of services. PALPAS users need to only memorize a single password and the setup of PALPAS on a further device demands only a one-time transfer of few static data.
A community role approach to assess social capitalists visibility in the Twitter network
Venue: arXiv cs.SI 2015
Year: 2015

In the context of Twitter, social capitalists are specific users trying to increase their number of followers and interactions by any means. These users are not healthy for the service, because they are either spammers or real users flawing the notions of influence and visibility. Studying their behavior and understanding their position in Twit-ter is thus of important interest. It is also necessary to analyze how these methods effectively affect user visibility. Based on a recently proposed method allowing to identify social capitalists, we tackle both points by studying how they are organized, and how their links spread across the Twitter follower-followee network. To that aim, we consider their position in the network w.r.t. its community structure. We use the concept of community role of a node, which describes its position in a network depending on its connectiv-ity at the community level. However, the topological measures originally defined to characterize these roles consider only certain aspects of the community-related connectivity, and rely on a set of empirically fixed thresholds. We first show the limitations of these measures, before extending and generalizing them. Moreover, we use an unsupervised approach to identify the roles, in order to provide more flexibility relatively to the studied system. We then apply our method to the case of social capitalists and show they are highly visible on Twitter, due to the specific roles they hold.
SuperGraph Visualization
Venue: arXiv cs.SI 2015
Year: 2015

Given a large social or computer network, how can we visualize it, find patterns, outliers, communities? Although several graph visualization tools exist, they cannot handle large graphs with hundred thousand nodes and possibly million edges. Such graphs bring two challenges: interactive visualization demands prohibitive processing power and, even if we could interactively update the visualization, the user would be overwhelmed by the excessive number of graphical items. To cope with this problem, we propose a formal innovation on the use of graph hierarchies that leads to GMine system. GMine promotes scalability using a hierarchy of graph partitions, promotes concomitant presentation for the graph hierarchy and for the original graph, and extends analytical possibilities with the integration of the graph partitions in an interactive environment.
Service-Oriented Architecture in Industrial Automation Systems - The case of IEC 61499: A Review
Venue: arXiv cs.SE 2015
Year: 2015

In the paper by W. Dai et al. (IEEE Trans. On Industrial Informatics, vol. 11, no. 3, pp. 771-781, June 2015), a formal model is described for the application of SOA in the distributed automation domain in order to achieve flexible automation systems. A service-based execution environment architecture based on the IEC 61499 Function Block model is proposed and a case study is used to demonstrate dynamic reconfiguration. In this letter, a review of the literature related to the use of SOA in Industrial Automation Systems is given to set up a context for the discussion of the proposed in the above paper SOA IEC61499 formal model. The presented, in the above paper, formal model and execution environment architecture are commented towards a better understanding of the potentials for the exploitation of the SOA paradigm in the industrial automation domain.
Optimized Configurable Architectures for Scalable Soft-Input Soft-Output MIMO Detectors with 256-QAM
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents an optimized low-complexity and high-throughput multiple-input multiple-output (MIMO) signal detector core for detecting spatially-multiplexed data streams. The core architecture supports various layer configurations up to 4, while achieving near-optimal performance, as well as configurable modulation constellations up to 256-QAM on each layer. The core is capable of operating as a soft-input soft-output log-likelihood ratio (LLR) MIMO detector which can be used in the context of iterative detection and decoding. High area-efficiency is achieved via algorithmic and architectural optimizations performed at two levels. First, distance computations and slicing operations for an optimal 2-layer maximum a posteriori (MAP) MIMO detector are optimized to eliminate the use of multipliers and reduce the overhead of slicing in the presence of soft-input LLRs. We show that distances can be easily computed using elementary addition operations, while optimal slicing is done via efficient comparisons with soft decision boundaries, resulting in a simple feed-forward pipelined architecture. Second, to support more layers, an efficient channel decomposition scheme is presented that reduces the detection of multiple layers into multiple 2-layer detection subproblems, which map onto the 2-layer core with a slight modification using a distance accumulation stage and a post-LLR processing stage. Various architectures are accordingly developed to achieve a desired detection throughput and run-time reconfigurability by time-multiplexing of one or more component cores. The proposed core is applied as well to design an optimal multi-user MIMO detector for LTE. The core occupies an area of 1.58MGE and achieves a throughput of 733 Mbps for 256-QAM when synthesized in 90 nm CMOS.
Separations in Query Complexity Based on Pointer Functions
Venue: arXiv cs.CC 2015
Year: 2015

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $Ω(n/\log(n))$ while its zero-error randomized query complexity is $\tilde O(\sqrt{n})$. We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total boolean function $g$ on $n$ variables that has zero-error randomized query complexity $Ω(n/\log(n))$ and bounded-error randomized query complexity $R(g) = \tilde O(\sqrt{n})$. This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is $Q_E(g) = \tilde O(\sqrt{n})$. These two functions show that the relations $D(f) = O(R_1(f)^2)$ and $R_0(f) = \tilde O(R(f)^2)$ are optimal, up to poly-logarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between $Q$ and $R_0$, a $3/2$-power separation between $Q_E$ and $R$, and a 4th power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by \goos, Pitassi, and Watson which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.
Optimal Forwarding in Opportunistic Delay Tolerant Networks with Meeting Rate Estimations
Venue: arXiv cs.NI 2015
Year: 2015

Data transfer in opportunistic Delay Tolerant Networks (DTNs) must rely on unscheduled sporadic meetings between nodes. The main challenge in these networks is to develop a mechanism based on which nodes can learn to make nearly optimal forwarding decision rules despite having no a-priori knowledge of the network topology. The forwarding mechanism should ideally result in a high delivery probability, low average latency and efficient usage of the network resources. In this paper, we propose both centralized and decentralized single-copy message forwarding algorithms that, under relatively strong assumptions about the networks behaviour, minimize the expected latencies from any node in the network to a particular destination. After proving the optimality of our proposed algorithms, we develop a decentralized algorithm that involves a recursive maximum likelihood procedure to estimate the meeting rates. We confirm the improvement that our proposed algorithms make in the system performance through numerical simulations on datasets from synthetic and real-world opportunistic networks.
Cheap Bandits
Venue: arXiv cs.LG 2015
Year: 2015

We consider stochastic sequential learning problems where the learner can observe the \textit{average reward of several actions}. Such a setting is interesting in many applications involving monitoring and surveillance, where the set of the actions to observe represent some (geographical) area. The importance of this setting is that in these applications, it is actually \textit{cheaper} to observe average reward of a group of actions rather than the reward of a single action. We show that when the reward is \textit{smooth} over a given graph representing the neighboring actions, we can maximize the cumulative reward of learning while \textit{minimizing the sensing cost}. In this paper we propose CheapUCB, an algorithm that matches the regret guarantees of the known algorithms for this setting and at the same time guarantees a linear cost again over them. As a by-product of our analysis, we establish a $Ω(\sqrt{dT})$ lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension $d$.
A Novel Semantics and Feature Preserving Perspective for Content Aware Image Retargeting
Venue: arXiv cs.GR 2015
Year: 2015

There is an increasing requirement for efficient image retargeting techniques to adapt the content to various forms of digital media. With rapid growth of mobile communications and dynamic web page layouts, one often needs to resize the media content to adapt to the desired display sizes. For various layouts of web pages and typically small sizes of handheld portable devices, the importance in the original image content gets obfuscated after resizing it with the approach of uniform scaling. Thus, there occurs a need for resizing the images in a content aware manner which can automatically discard irrelevant information from the image and present the salient features with more magnitude. There have been proposed some image retargeting techniques keeping in mind the content awareness of the input image. However, these techniques fail to prove globally effective for various kinds of images and desired sizes. The major problem is the inefficiency of these algorithms to process these images with minimal visual distortion while also retaining the meaning conveyed from the image. In this dissertation, we present a novel perspective for content aware image retargeting, which is well implementable in real time. We introduce a novel method of analysing semantic information within the input image while also maintaining the important and visually significant features. We present the various nuances of our algorithm mathematically and logically, and show that the results prove better than the state-of-the-art techniques.
Empirical Coordination with Two-Sided State Information and Correlated Source and State
Venue: arXiv cs.IT 2015
Year: 2015

The coordination of autonomous agents is a critical issue for decentralized communication networks. Instead of transmitting information, the agents interact in a coordinated manner in order to optimize a general objective function. A target joint probability distribution is achievable if there exists a code such that the sequences of symbols are jointly typical. The empirical coordination is strongly related to the joint source-channel coding with two-sided state information and correlated source and state. This problem is also connected to state communication and is open for non-causal encoder and decoder. We characterize the optimal solutions for perfect channel, for lossless decoding, for independent source and channel, for causal encoding and for causal decoding.
Some Improvements on Locally Repairable Codes
Venue: arXiv cs.IT 2015
Year: 2015

The locally repairable codes (LRCs) were introduced to correct erasures efficiently in distributed storage systems. LRCs are extensively studied recently. In this paper, we first deal with the open case remained in \cite{q} and derive an improved upper bound for the minimum distances of LRCs. We also give an explicit construction for LRCs attaining this bound. Secondly, we consider the constructions of LRCs with any locality and availability which have high code rate and minimum distance as large as possible. We give a graphical model for LRCs. By using the deep results from graph theory, we construct a family of LRCs with any locality $r$ and availability $2$ with code rate $\frac{r-1}{r+1}$ and optimal minimum distance $O(\log n)$ where $n$ is the length of the code.
Significance of the levels of spectral valleys with application to front/back distinction of vowel sounds
Venue: arXiv cs.CL 2015
Year: 2015

An objective critical distance (OCD) has been defined as that spacing between adjacent formants, when the level of the valley between them reaches the mean spectral level. The measured OCD lies in the same range (viz., 3-3.5 bark) as the critical distance determined by subjective experiments for similar experimental conditions. The level of spectral valley serves a purpose similar to that of the spacing between the formants with an added advantage that it can be measured from the spectral envelope without an explicit knowledge of formant frequencies. Based on the relative spacing of formant frequencies, the level of the spectral valley, VI (between F1 and F2) is much higher than the level of VII (spectral valley between F2 and F3) for back vowels and vice-versa for front vowels. Classification of vowels into front/back distinction with the difference (VI-VII) as an acoustic feature, tested using TIMIT, NTIMIT, Tamil and Kannada language databases gives, on the average, an accuracy of about 95%, which is comparable to the accuracy (90.6%) obtained using a neural network classifier trained and tested using MFCC as the feature vector for TIMIT database. The acoustic feature (VI-VII) has also been tested for its robustness on the TIMIT database for additive white and babble noise and an accuracy of about 95% has been obtained for SNRs down to 25 dB for both types of noise.
Efficient Reverse k Nearest Neighbor evaluation for hierarchical index
Venue: arXiv cs.DS 2015
Year: 2015

"Reverse Nearest Neighbor" query finds applications in decision support systems, profile-based marketing, emergency services etc. In this paper, we point out a few flaws in the branch and bound algorithms proposed earlier for computing monochromatic RkNN queries over data points stored in hierarchical index. We give suitable counter examples to validate our claims and propose a correct algorithm for the corresponding problem. We show that our algorithm is correct by identifying necessary conditions behind correctness of algorithms for this problem.
Compositional Verification for Timed Systems Based on Automatic Invariant Generation
Venue: arXiv cs.LO 2015
Year: 2015

We propose a method for compositional verification to address the state space explosion problem inherent to model-checking timed systems with a large number of components. The main challenge is to obtain pertinent global timing constraints from the timings in the components alone. To this end, we make use of auxiliary clocks to automatically generate new invariants which capture the constraints induced by the synchronisations between components. The method has been implemented in the RTD-Finder tool and successfully experimented on several benchmarks.
Performance Evaluation Of Qos In Wimax Network
Venue: arXiv cs.NI 2015
Year: 2015

OPNET Modeler is used to simulate the architecture and to calculate the performance criteria (i.e. throughput, delay and data dropped) that slightly concerned in network estimation. It is concluded that our models shorten the time quite a bit for obtaining the performance measures of an end-to-end delay as well as throughput can be used as an effective tool for this purpose.
Sequential Consistency and Concurrent Data Structures
Venue: arXiv cs.DC 2015
Year: 2015

Linearizability, the de facto correctness condition for concurrent data structure implementations, despite its intuitive appeal is known to lead to poor scalability. This disadvantage has led researchers to design scalable data structures satisfying consistency conditions weaker than linearizability. Despite this recent trend, sequential consistency as a strictly weaker consistency condition than linearizability has received no interest. In this paper, we investigate the applicability of sequential consistency as an alternative correctness criterion for concurrent data structure implementations. Our first finding formally justifies the reluctance in moving towards sequentially consistent data structures: Implementations in which each thread modifies only its thread-local variables are sequentially consistent for various standard data structures such as pools, queues and stacks. We also show that for almost all data structures, and the data structures we consider in this paper, it is possible to have sequentially consistent behaviors in which a designated thread does not synchronize at all. As a potential remedy, we define a hierarchy of quantitatively strengthened variants of sequential consistency such that the stronger the variant the more synchronization it enforces which at the limit is equal to that enforced by linearizability.
Spatial Symmetry Driven Pruning Strategies for Efficient Declarative Spatial Reasoning
Venue: arXiv cs.AI 2015
Year: 2015

Declarative spatial reasoning denotes the ability to (declaratively) specify and solve real-world problems related to geometric and qualitative spatial representation and reasoning within standard knowledge representation and reasoning (KR) based methods (e.g., logic programming and derivatives). One approach for encoding the semantics of spatial relations within a declarative programming framework is by systems of polynomial constraints. However, solving such constraints is computationally intractable in general (i.e. the theory of real-closed fields). We present a new algorithm, implemented within the declarative spatial reasoning system CLP(QS), that drastically improves the performance of deciding the consistency of spatial constraint graphs over conventional polynomial encodings. We develop pruning strategies founded on spatial symmetries that form equivalence classes (based on affine transformations) at the qualitative spatial level. Moreover, pruning strategies are themselves formalised as knowledge about the properties of space and spatial symmetries. We evaluate our algorithm using a range of benchmarks in the class of contact problems, and proofs in mereology and geometry. The empirical results show that CLP(QS) with knowledge-based spatial pruning outperforms conventional polynomial encodings by orders of magnitude, and can thus be applied to problems that are otherwise unsolvable in practice.
Tensor Deflation for CANDECOMP/PARAFAC. Part 3: Rank Splitting
Venue: arXiv cs.NA 2015
Year: 2015

CANDECOMP/PARAFAC (CPD) approximates multiway data by sum of rank-1 tensors. Our recent study has presented a method to rank-1 tensor deflation, i.e. sequential extraction of the rank-1 components. In this paper, we extend the method to block deflation problem. When at least two factor matrices have full column rank, one can extract two rank-1 tensors simultaneously, and rank of the data tensor is reduced by 2. For decomposition of order-3 tensors of size R x R x R and rank-R, the block deflation has a complexity of O(R^3) per iteration which is lower than the cost O(R^4) of the ALS algorithm for the overall CPD.
A Robust Eco-Routing Protocol Against Malicious Data in Vehicular Networks
Venue: arXiv cs.CR 2015
Year: 2015

Vehicular networks have a diverse range of applications that vary from safety, to traffic management and comfort. Vehicular communications (VC) can assist in the ecorouting of vehicles in order to reduce the overall mileage and CO2 emissions by the exchange of data among vehicle-entities. However, the trustworthiness of these data is crucial as false information can heavily affect the performance of applications. Hence, the devising of mechanisms that reassure the integrity of the exchanged data is of utmost importance. In this article we investigate how tweaked information originating from malicious nodes can affect the performance of a real time eco routing mechanism that uses DSRC communications, namely ErouVe. We also develop and evaluate defense mechanisms that exploit vehicular communications in order to filter out tweaked data. We prove that our proposed mechanisms can restore the performance of the ErouVe to near its optimal operation and can be used as a basis for protecting other similar traffic management systems.