OpenRaiser/Intern-Atlas huggingface dataset:
Automated Cryptanalysis of Bloom Filter Encryptions of Health Records
Venue: arXiv cs.CR 2014
Year: 2014

Privacy-preserving record linkage with Bloom filters has become increasingly popular in medical applications, since Bloom filters allow for probabilistic linkage of sensitive personal data. However, since evidence indicates that Bloom filters lack sufficiently high security where strong security guarantees are required, several suggestions for their improvement have been made in literature. One of those improvements proposes the storage of several identifiers in one single Bloom filter. In this paper we present an automated cryptanalysis of this Bloom filter variant. The three steps of this procedure constitute our main contributions: (1) a new method for the detection of Bloom filter encrytions of bigrams (so-called atoms), (2) the use of an optimization algorithm for the assignment of atoms to bigrams, (3) the reconstruction of the original attribute values by linkage against bigram sets obtained from lists of frequent attribute values in the underlying population. To sum up, our attack provides the first convincing attack on Bloom filter encryptions of records built from more than one identifier.
Power Redistribution for Optimizing Performance in MPI Clusters
Venue: arXiv cs.DC 2014
Year: 2014

Power efficiency has recently become a major concern in the high-performance computing domain. HPC centers are provisioned by a power bound which impacts execution time. Naturally, a tradeoff arises between power efficiency and computational efficiency. This paper tackles the problem of performance optimization for MPI applications, where a power bound is assumed. The paper exposes a subset of HPC applications that leverage cluster parallelism using MPI, where nodes encounter multiple synchronization points and exhibit inter-node dependency. We abstract this structure into a dependency graph, and leverage the asymmetry in execution time of parallel jobs on different nodes by redistributing power gained from idling a blocked node to nodes that are lagging in their jobs. We introduce a solution based on integer linear programming (ILP) for optimal power distribution algorithm that minimizes total execution time, while maintaining an upper power bound. We then present an online heuristic that dynamically redistributes power at run time. The heuristic shows significant reductions in total execution time of a set of parallel benchmarks with speedup up to 2.25x.
Editing to Eulerian Graphs
Venue: arXiv cs.DM 2014
Year: 2014

We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let $ea$, $ed$ and $vd$ denote the operations edge addition, edge deletion and vertex deletion respectively. For any $S\subseteq \{ea,ed,vd\}$, we define Connected Degree Parity Editing$(S)$ (CDPE($S$)) to be the problem that takes as input a graph $G$, an integer $k$ and a function $δ\colon V(G)\rightarrow\{0,1\}$, and asks whether $G$ can be modified into a connected graph $H$ with $d_{H}(v)\equivδ(v)~(\bmod~2)$ for each $v\in V(H)$, using at most $k$ operations from $S$. We prove that 1. if $S=\{ea\}$ or $S=\{ea,ed\}$, then CDPE($S$) can be solved in polynomial time; 2. if $\{vd\} \subseteq S\subseteq \{ea,ed,vd\}$, then CDPE($S$) is NP-complete and W[1]-hard when parameterized by $k$, even if $δ\equiv 0$. Together with known results by Cai and Yang and by Cygan, Marx, Pilipczuk, Pilipczuk and Schlotter, our results completely classify the classical and parameterized complexity of the CDPE($S$) problem for all $S\subseteq \{ea,ed,vd\}$. We obtain the same classification for a natural variant of the CDPE($S$) problem on directed graphs, where the target is a weakly connected digraph in which the difference between the in- and out-degree of every vertex equals a prescribed value. As an important implication of our results, we obtain polynomial-time algorithms for the Eulerian Editing problem and its directed variant.
Analyzing Expected Outcomes and Almost-Sure Termination of Probabilistic Programs is Hard
Venue: arXiv cs.LO 2014
Year: 2014

This paper considers the computational hardness of computing expected outcomes and deciding almost-sure termination of probabilistic programs. We show that deciding almost-sure termination and deciding whether the expected outcome of a program equals a given rational value is $Π^0_2$-complete. Computing lower and upper bounds on the expected outcome is shown to be recursively enumerable and $Σ^0_2$-complete, respectively.
A New Perspective on the Windows Scheduling Problem
Venue: arXiv cs.CC 2014
Year: 2014

The Windows Scheduling Problem, also known as the Pinwheel Problem, is to schedule periodic jobs subject to their processing frequency demands. Instances are given as a set of jobs that have to be processed infinitely often such that the time interval between two consecutive executions of the same job j is no longer than the job's given period $p_j$. The key contribution of this work is a new interpretation of the problem variant with exact periods, where the time interval between consecutive executions must be strictly $p_j$. We show that this version is equivalent to a natural combinatorial problem we call Partial Coding. Reductions in both directions can be realized in polynomial time, so that both hardness proofs and algorithms for Partial Coding transfer to Windows Scheduling. Applying this new perspective, we obtain a number of new results regarding the computational complexity of various Windows Scheduling Problem variants. We prove that even the case of one processor and unit-length jobs does not admit a pseudo-polynomial time algorithm unless SAT can be solved by a randomized method in expected quasi-polynomial time. This result also extends to the case of inexact periods, which answers a question that has remained open for more than two decades. Furthermore, we report an error found in a hardness proof previously given for the multi-machine case without machine migration, and we show that this variant reduces to the single-machine case. Finally, we prove that even with unit-length jobs the problem is co-NP-hard when jobs are allowed to migrate between machines.
Optimization of the Multigrid-Convergence Rate on Semi-structured Meshes by Local Fourier Analysis
Venue: arXiv cs.NA 2014
Year: 2014

In this paper a local Fourier analysis for multigrid methods on tetrahedral grids is presented. Different smoothers for the discretization of the Laplace operator by linear finite elements on such grids are analyzed. A four-color smoother is presented as an efficient choice for regular tetrahedral grids, whereas line and plane relaxations are needed for poorly shaped tetrahedra. A novel partitioning of the Fourier space is proposed to analyze the four-color smoother. Numerical test calculations validate the theoretical predictions. A multigrid method is constructed in a block-wise form, by using different smoothers and different numbers of pre- and post-smoothing steps in each tetrahedron of the coarsest grid of the domain. Some numerical experiments are presented to illustrate the efficiency of this multigrid algorithm.
High Range Resolution Profiling in Missing Data Case: A New Approach
Venue: arXiv cs.IT 2014
Year: 2014

We have proposed a novel method for Synthetic High Range Resolution (HRR) profiling, under the condition of missing frequency domain samples. This new approach estimates the autocovariance function (ACF) of the signal by valid sample pairs. Autocovariance matrix is formed from ACF estimations. Even with large part of data missing, new approach exhibits robust profiling result. Simulations are presented to show a advantage over other approaches in missing data case. Moreover, a real radar experiment was conducted to validate the new approach.
On-the-fly Probabilistic Model Checking
Venue: arXiv cs.LO 2014
Year: 2014

Model checking approaches can be divided into two broad categories: global approaches that determine the set of all states in a model M that satisfy a temporal logic formula f, and local approaches in which, given a state s in M, the procedure determines whether s satisfies f. When s is a term of a process language, the model checking procedure can be executed "on-the-fly", driven by the syntactical structure of s. For certain classes of systems, e.g. those composed of many parallel components, the local approach is preferable because, depending on the specific property, it may be sufficient to generate and inspect only a relatively small part of the state space. We propose an efficient, on-the-fly, PCTL model checking procedure that is parametric with respect to the semantic interpretation of the language. The procedure comprises both bounded and unbounded until modalities. The correctness of the procedure is shown and its efficiency is compared with a global PCTL model checker on representative applications.
From Orchestration to Choreography through Contract Automata
Venue: arXiv cs.FL 2014
Year: 2014

We study the relations between a contract automata and an interaction model. In the former model, distributed services are abstracted away as automata - oblivious of their partners - that coordinate with each other through an orchestrator. The interaction model relies on channel-based asynchronous communication and choreography to coordinate distributed services. We define a notion of strong agreement on the contract model, exhibit a natural mapping from the contract model to the interaction model, and give conditions to ensure that strong agreement corresponds to well-formed choreography.
A note on two notions of compliance
Venue: arXiv cs.PL 2014
Year: 2014

We establish a relation between two models of contracts: binary session types, and a model based on event structures and game-theoretic notions. In particular, we show that compliance in session types corresponds to the existence of certain winning strategies in game-based contracts.
Random-Facet and Random-Bland require subexponential time even for shortest paths
Venue: arXiv cs.DS 2014
Year: 2014

The Random-Facet algorithm of Kalai and of Matousek, Sharir and Welzl is an elegant randomized algorithm for solving linear programs and more general LP-type problems. Its expected subexponential time of $2^{\tilde{O}(\sqrt{m})}$, where $m$ is the number of inequalities, makes it the fastest known combinatorial algorithm for solving linear programs. We previously showed that Random-Facet performs an expected number of $2^{\tildeΩ(\sqrt[3]{m})}$ pivoting steps on some LPs with $m$ inequalities that correspond to $m$-action Markov Decision Processes (MDPs). We also showed that Random-Facet-1P, a one permutation variant of Random-Facet, performs an expected number of $2^{\tilde{O}(\sqrt{m})}$ pivoting steps on these examples. Here we show that the same results can be obtained using LPs that correspond to instances of the classical shortest paths problem. This shows that the stochasticity of the MDPs, which is essential for obtaining lower bounds for Random-Edge, is not needed in order to obtain lower bounds for Random-Facet. We also show that our new $2^{\tildeΩ(\sqrt{m})}$ lower bound applies to Random-Bland, a randomized variant of the classical anti-cycling rule suggested by Bland.
Fisher-Yates Chaotic Shuffling Based Image Encryption
Venue: arXiv cs.CR 2014
Year: 2014

In Present era, information security is of utmost concern and encryption is one of the alternatives to ensure security. Chaos based cryptography has brought a secure and efficient way to meet the challenges of secure multimedia transmission over the networks. In this paper, we have proposed a secure Grayscale image encryption methodology in wavelet domain. The proposed algorithm performs shuffling followed by encryption using states of chaotic map in a secure manner. Firstly, the image is transformed from spatial domain to wavelet domain by the Haar wavelet. Subsequently, Fisher Yates chaotic shuffling technique is employed to shuffle the image in wavelet domain to confuse the relationship between plain image and cipher image. A key dependent piece-wise linear chaotic map is used to generate chaos for the chaotic shuffling. Further, the resultant shuffled approximate coefficients are chaotically modulated. To enhance the statistical characteristics from cryptographic point of view, the shuffled image is self keyed diffused and mixing operation is carried out using keystream extracted from one-dimensional chaotic map and the plain-image. The proposed algorithm is tested over some standard image dataset. The results of several experimental, statistical and sensitivity analyses proved that the algorithm provides an efficient and secure method to achieve trusted gray scale image encryption.
Multi Core SSL/TLS Security Processor Architecture Prototype Design with automated Preferential Algorithm in FPGA
Venue: arXiv cs.AR 2014
Year: 2014

In this paper a pipelined architecture of a high speed network security processor (NSP) for SSL,TLS protocol is implemented on a system on chip (SOC) where hardware information of all encryption, hashing and key exchange algorithms are stored in flash memory in terms of bit files, in contrary to related works where all are actually implemented in hardware. The NSP finds applications in e-commerce, virtual private network (VPN) and in other fields that require data confidentiality. The motivation of the present work is to dynamically execute applications with stipulated throughput within budgeted hardware resource and power. A preferential algorithm choosing an appropriate cipher suite is proposed, which is based on Efficient System Index (ESI) budget comprising of power, throughput and resource given by the user. The bit files of the chosen security algorithms are downloaded from the flash memory to the partial region of field programmable gate array (FPGA). The proposed SOC controls data communication between an application running in a system through a PCI and the Ethernet interface of a network. Partial configuration feature is used in ISE14.4 suite with ZYNQ 7z020-clg484 FPGA platform. The performances
Adaptive Synchronization of Robotic Sensor Networks
Venue: arXiv cs.DC 2014
Year: 2014

The main focus of recent time synchronization research is developing power-efficient synchronization methods that meet pre-defined accuracy requirements. However, an aspect that has been often overlooked is the high dynamics of the network topology due to the mobility of the nodes. Employing existing flooding-based and peer-to-peer synchronization methods, are networked robots still be able to adapt themselves and self-adjust their logical clocks under mobile network dynamics? In this paper, we present the application and the evaluation of the existing synchronization methods on robotic sensor networks. We show through simulations that Adaptive Value Tracking synchronization is robust and efficient under mobility. Hence, deducing the time synchronization problem in robotic sensor networks into a dynamic value searching problem is preferable to existing synchronization methods in the literature.
Performance evaluation with a Comparative analysis of mimo channel on The basis of doppler shift and other Probabilistic parameters in fading Environment
Venue: arXiv cs.NI 2014
Year: 2014

At this present scenario, the demand of the system capacity is very high in wireless network. MIMO technology is used from the last decade to provide this requirement for wireless network antenna technology. MIMO channels are mostly used for advanced antenna array technology. But it is most important to control the error rate with enhanced system capacity in MIMO for present-day progressive wireless communication. This paper explores the frame error rate with respect to different path gain of MIMO channel. This work has been done in different fading scenario and produces a comparative analysis of MIMO on the basis of those fading models in various conditions. Here, it is to be considered that modulation technique as QPSK to observe these comparative evaluations for different Doppler frequencies. From the comparative analysis, minimum amount of frame error rate is viewed for Rician distribution at LOS path Doppler shift of 0 Hz. At last, this work is concluded with a comparative bit error rate study on the basis of singular parameters at different SNR levels to produce the system performance for uncoded QPSK modulation.
Differentially Private Location Privacy in Practice
Venue: arXiv cs.CR 2014
Year: 2014

With the wide adoption of handheld devices (e.g. smartphones, tablets) a large number of location-based services (also called LBSs) have flourished providing mobile users with real-time and contextual information on the move. Accounting for the amount of location information they are given by users, these services are able to track users wherever they go and to learn sensitive information about them (e.g. their points of interest including home, work, religious or political places regularly visited). A number of solutions have been proposed in the past few years to protect users location information while still allowing them to enjoy geo-located services. Among the most robust solutions are those that apply the popular notion of differential privacy to location privacy (e.g. Geo-Indistinguishability), promising strong theoretical privacy guarantees with a bounded accuracy loss. While these theoretical guarantees are attracting, it might be difficult for end users or practitioners to assess their effectiveness in the wild. In this paper, we carry on a practical study using real mobility traces coming from two different datasets, to assess the ability of Geo-Indistinguishability to protect users' points of interest (POIs). We show that a curious LBS collecting obfuscated location information sent by mobile users is still able to infer most of the users POIs with a reasonable both geographic and semantic precision. This precision depends on the degree of obfuscation applied by Geo-Indistinguishability. Nevertheless, the latter also has an impact on the overhead incurred on mobile devices resulting in a privacy versus overhead trade-off. Finally, we show in our study that POIs constitute a quasi-identifier for mobile users and that obfuscating them using Geo-Indistinguishability is not sufficient as an attacker is able to re-identify at least 63% of them despite a high degree of obfuscation.
An Application Package Configuration Approach to Mitigating Android SSL Vulnerabilities
Venue: arXiv cs.CR 2014
Year: 2014

Computing platforms such as smartphones frequently access Web content using many separate applications rather than a single Web browser application. These applications often deal with sensitive user information such as financial data or passwords, and use Secure Sockets Layer (SSL) to protect it from unauthorized eavesdropping. However, recent studies have confirmed a wide-spread misconfiguration of SSL verification in applications. This paper considers the difficulty faced by Android application developers when modifying SSL code for using common features like pinning or using a self-signed SSL certificate. For example, developing an application that accesses a test Web server with a self-signed certificate requires additional code to remove SSL verification; however, this code is not always removed in production versions of the application. To mitigate vulnerabilities introduced because of the complexity of customizing SSL code in Android applications, we propose that common SSL configuration should be specified in the application's package manifest. We provide two concrete suggestions: 1) linking the application's debug state to SSL verification, and 2) pinning certificates and CAs in the manifest. We evaluate the appropriateness of these two suggestions on over 13,000 applications from Google's Play Store, of which 3,302 use SSL in non-advertisement code, and find that 1,889 (57.20%) of these SSL applications would benefit.
Correcting Errors in Digital Lexicographic Resources Using a Dictionary Manipulation Language
Venue: arXiv cs.CL 2014
Year: 2014

We describe a paradigm for combining manual and automatic error correction of noisy structured lexicographic data. Modifications to the structure and underlying text of the lexicographic data are expressed in a simple, interpreted programming language. Dictionary Manipulation Language (DML) commands identify nodes by unique identifiers, and manipulations are performed using simple commands such as create, move, set text, etc. Corrected lexicons are produced by applying sequences of DML commands to the source version of the lexicon. DML commands can be written manually to repair one-off errors or generated automatically to correct recurring problems. We discuss advantages of the paradigm for the task of editing digital bilingual dictionaries.
A Markov Decision Process Analysis of the Cold Start Problem in Bayesian Information Filtering
Venue: arXiv cs.LG 2014
Year: 2014

We consider the information filtering problem, in which we face a stream of items, and must decide which ones to forward to a user to maximize the number of relevant items shown, minus a penalty for each irrelevant item shown. Forwarding decisions are made separately in a personalized way for each user. We focus on the cold-start setting for this problem, in which we have limited historical data on the user's preferences, and must rely on feedback from forwarded articles to learn which the fraction of items relevant to the user in each of several item categories. Performing well in this setting requires trading exploration vs. exploitation, forwarding items that are likely to be irrelevant, to allow learning that will improve later performance. In a Bayesian setting, and using Markov decision processes, we show how the Bayes-optimal forwarding algorithm can be computed efficiently when the user will examine each forwarded article, and how an upper bound on the Bayes-optimal procedure and a heuristic index policy can be obtained for the setting when the user will examine only a limited number of forwarded items. We present results from simulation experiments using parameters estimated using historical data from arXiv.org.
Resource Allocation Optimization for Delay-Sensitive Traffic in Fronthaul Constrained Cloud Radio Access Networks
Venue: arXiv cs.IT 2014
Year: 2014

The cloud radio access network (C-RAN) provides high spectral and energy efficiency performances, low expenditures and intelligent centralized system structures to operators, which has attracted intense interests in both academia and industry. In this paper, a hybrid coordinated multi-point transmission (H-CoMP) scheme is designed for the downlink transmission in C-RANs, which fulfills the flexible tradeoff between cooperation gain and fronthaul consumption. The queue-aware power and rate allocation with constraints of average fronthaul consumption for the delay-sensitive traffic are formulated as an infinite horizon constrained partially observed Markov decision process (POMDP), which takes both the urgent queue state information (QSI) and the imperfect channel state information at transmitters (CSIT) into account. To deal with the curse of dimensionality involved with the equivalent Bellman equation, the linear approximation of post-decision value functions is utilized. A stochastic gradient algorithm is presented to allocate the queue-aware power and transmission rate with H-CoMP, which is robust against unpredicted traffic arrivals and uncertainties caused by the imperfect CSIT. Furthermore, to substantially reduce the computing complexity, an online learning algorithm is proposed to estimate the per-queue post-decision value functions and update the Lagrange multipliers. The simulation results demonstrate performance gains of the proposed stochastic gradient algorithms, and confirm the asymptotical convergence of the proposed online learning algorithm.