OpenRaiser/Intern-Atlas huggingface dataset:
A partisan districting protocol with provably nonpartisan outcomes
Venue: arXiv cs.GT 2017
Year: 2017

We design and analyze a protocol for dividing a state into districts, where parties take turns proposing a division, and freezing a district from the other party's proposed division. We show that our protocol has predictable and provable guarantees for both the number of districts in which each party has a majority of supporters, and the extent to which either party has the power to pack a specific population into a single district.
A Quantitative Analysis of WCAG 2.0 Compliance For Some Indian Web Portals
Venue: arXiv cs.HC 2017
Year: 2017

Web portals have served as an excellent medium to facilitate user centric services for organizations irrespective of the type, size, and domain of operation. The objective of these portals has been to deliver a plethora of services such as information dissemination, transactional services, and customer feedback. Therefore, the design of a web portal is crucial in order that it is accessible to a wide range of user community irrespective of age group, physical abilities, and level of literacy. In this paper, we have studied the compliance of WCAG 2.0 by three different categories of Indian web sites which are most frequently accessed by a large section of user community. We have provided a quantitative evaluation of different aspects of accessibility which we believe can pave the way for better design of web sites by taking care of the deficiencies inherent in the web portals.
Deadlock and Termination Detection using IMDS Formalism and Model Checking. Version 2
Venue: arXiv cs.DC 2017
Year: 2017

Modern model checking techniques concentrate on global properties of verified systems, because the methods base on global state space. Local features like partial deadlock or process termination are not easy to express and check. In the paper a description of distributed system in an Integrated Model of Distributed Systems (IMDS) combined with model checking is presented. IMDS expresses a dualism in distributed systems: server view and agent view. The formalism uses server states and messages. A progress in computations is defined in terms of actions consuming and producing states and messages. Distributed actions are totally independent and they do not depend on global state. Therefore, IMDS allows the designer to express local features of subsystems. In this model it is easy to describe various kinds of deadlock (including partial deadlock) and to differentiate deadlock from termination. The integration of IMDS with model checking is presented. Temporal formulas testing various kinds of deadlock (in communication or over resources) and termination are proposed.
ROS and Buzz: consensus-based behaviors for heterogeneous teams
Venue: arXiv cs.RO 2017
Year: 2017

This paper address the challenges encountered by developers when deploying a distributed decision-making behavior on heterogeneous robotic systems. Many applications benefit from the use of multiple robots, but their scalability and applicability are fundamentally limited if relying on a central control station. Getting beyond the centralized approach can increase the complexity of the embedded intelligence, the sensitivity to the network topology, and render the deployment on physical robots tedious and error-prone. By integrating the swarm-oriented programming language Buzz with the standard environment of ROS, this work demonstrates that behaviors requiring distributed consensus can be successfully deployed in practice. From simulation to the field, the behavioral script stays untouched and applicable to heterogeneous robot teams. We present the software structure of our solution as well as the swarm-oriented paradigms required from Buzz to implement a robust generic consensus strategy. We show the applicability of our solution with simulations and experiments with heterogeneous ground-and-air robotic teams.
JADE - A Platform for Research on Cooperation of Physical and Virtual Agents
Venue: arXiv cs.MA 2017
Year: 2017

In the ICS, WUT a platform for simulation of cooperation of physical and virtual mobile agents is under development. The paper describes the motivation of the research, an organization of the platform, a model of agent, and the principles of design of the platform. Several experimental simulations are briefly described.
A Variable Length Coding Framework for Cost Function Reduction in Non-Volatile Memory Systems
Venue: arXiv cs.ET 2017
Year: 2017

Variable length coding for Non-Volatile Memory (NVM) technologies is a promising method to improve memory capacity and system performance through compressing memory blocks. However, compression techniques used to improve capacity or bandwidth utilization do not take into consideration the asymmetric costs of writing 1's and 0's in NVMs. Taking into account this asymmetry, we propose a variable length encoding framework that reduces the cost of writing data into NVM. Our experimental results on 12 workloads of the SPEC CPU2006 benchmark suite show that, when the cost asymmetry is 1:2, the proposed framework is capable of reducing the NVM programming cost by up to 24% more than leading compression approaches and by 12.5% more than the flip-and-write approach which selects between the data and its complement based on the programming cost.
Solving Packing and Covering LPs in $\tilde{O}(\frac{1}{ε^2})$ Distributed Iterations with a Single Algorithm and Simpler Analysis
Venue: arXiv cs.DS 2017
Year: 2017

Packing and covering linear programs belong to the narrow class of linear programs that are efficiently solvable in parallel and distributed models of computation, yet are a powerful modeling tool for a wide range of fundamental problems in theoretical computer science, operations research, and many other areas. Following recent progress in obtaining faster distributed and parallel algorithms for packing and covering linear programs, we present a simple algorithm whose iteration count matches the best known $\tilde{O}(\frac{1}{ε^2})$ for this class of problems. The algorithm is similar to the algorithm of [Allen-Zhu and Orecchia, 2015], it can be interpreted as Nesterov's dual averaging, and it constructs approximate solutions to both primal (packing) and dual (covering) problems. However, the analysis relies on the construction of an approximate optimality gap and a primal-dual view, leading to a more intuitive interpretation. Moreover, our analysis suggests that all existing algorithms for solving packing and covering linear programs in parallel/distributed models of computation are, in fact, unaccelerated, and raises the question of designing accelerated algorithms for this class of problems.
Janus: An Uncertain Cache Architecture to Cope with Side Channel Attacks
Venue: arXiv cs.CR 2017
Year: 2017

Side channel attacks are a major class of attacks to crypto-systems. Attackers collect and analyze timing behavior, I/O data, or power consumption in these systems to undermine their effectiveness in protecting sensitive information. In this work, we propose a new cache architecture, called Janus, to enable crypto-systems to introduce randomization and uncertainty in their runtime timing behavior and power utilization profile. In the proposed cache architecture, each data block is equipped with an on-off flag to enable/disable the data block. The Janus architecture has two special instructions in its instruction set to support the on-off flag. Beside the analytical evaluation of the proposed cache architecture, we deploy it in an ARM-7 processor core to study its feasibility and practicality. Results show a significant variation in the timing behavior across all the benchmarks. The new secure processor architecture has minimal hardware overhead and significant improvement in protecting against power analysis and timing behavior attacks.
Leaking Uninitialized Secure Enclave Memory via Structure Padding (Extended Abstract)
Venue: arXiv cs.CR 2017
Year: 2017

Intel software guard extensions (SGX) aims to provide an isolated execution environment, known as an enclave, for a user-level process to maximize its confidentiality and integrity. In this paper, we study how uninitialized data inside a secure enclave can be leaked via structure padding. We found that, during ECALL and OCALL, proxy functions that are automatically generated by the Intel SGX Software Development Kit (SDK) fully copy structure variables from an enclave to the normal memory to return the result of an ECALL function and to pass input parameters to an OCALL function. If the structure variables contain padding bytes, uninitialized enclave memory, which might contain confidential data like a private key, can be copied to the normal memory through the padding bytes. We also consider potential countermeasures against these security threats.
State Space Reduction for Reachability Graph of CSM Automata
Venue: arXiv cs.SE 2017
Year: 2017

Classical CTL temporal logics are built over systems with interleaving model concurrency. Many attempts are made to fight a state space explosion problem (for instance, compositional model checking). There are some methods of reduction of a state space based on independence of actions. However, in CSM model, which is based on coincidences rather than on interleaving, independence of actions cannot be defined. Therefore a state space reduction basing on identical temporal consequences rather than on independence of action is proposed. The new reduction is not as good as for interleaving systems, because all successors of a state (in depth of two levels) must be obtained before a reduction may be applied. This leads to reduction of space required for representation of a state space, but not in time of state space construction. Yet much savings may occur in regular state spaces for CSM systems.
New Results on the Fluctuating Two-Ray Model with Arbitrary Fading Parameters and Its Applications
Venue: arXiv cs.IT 2017
Year: 2017

The fluctuating two-ray (FTR) fading model provides a much better fit than other fading models for small-scale fading measurements in millimeter wave communications. In this paper, using a mixture of gamma distributions, new exact analytical expressions for the probability density and cumulative distribution functions of the FTR distribution with arbitrary fading parameters are presented. Moreover, the performance of digital communication systems over the FTR fading channel is evaluated in terms of the channel capacity and the bit error rate. The interaction between channel fading parameters and system performance is further investigated. Our newly derived results extend and complement previous knowledge of the FTR fading model.
Adversarial Deep Structured Nets for Mass Segmentation from Mammograms
Venue: arXiv cs.CV 2017
Year: 2017

Mass segmentation provides effective morphological features which are important for mass diagnosis. In this work, we propose a novel end-to-end network for mammographic mass segmentation which employs a fully convolutional network (FCN) to model a potential function, followed by a CRF to perform structured learning. Because the mass distribution varies greatly with pixel position, the FCN is combined with a position priori. Further, we employ adversarial training to eliminate over-fitting due to the small sizes of mammogram datasets. Multi-scale FCN is employed to improve the segmentation performance. Experimental results on two public datasets, INbreast and DDSM-BCRP, demonstrate that our end-to-end network achieves better performance than state-of-the-art approaches. \footnote{https://github.com/wentaozhu/adversarial-deep-structural-networks.git}
Privacy-Utility Tradeoffs under Constrained Data Release Mechanisms
Venue: arXiv cs.IT 2017
Year: 2017

Privacy-preserving data release mechanisms aim to simultaneously minimize information-leakage with respect to sensitive data and distortion with respect to useful data. Dependencies between sensitive and useful data results in a privacy-utility tradeoff that has strong connections to generalized rate-distortion problems. In this work, we study how the optimal privacy-utility tradeoff region is affected by constraints on the data that is directly available as input to the release mechanism. In particular, we consider the availability of only sensitive data, only useful data, and both (full data). We show that a general hierarchy holds: the tradeoff region given only the sensitive data is no larger than the region given only the useful data, which in turn is clearly no larger than the region given both sensitive and useful data. In addition, we determine conditions under which the tradeoff region given only the useful data coincides with that given full data. These are based on the common information between the sensitive and useful data. We establish these results for general families of privacy and utility measures that satisfy certain natural properties required of any reasonable measure of privacy or utility. We also uncover a new, subtler aspect of the data processing inequality for general non-symmetric privacy measures and discuss its operational relevance and implications. Finally, we derive exact closed-analytic-form expressions for the privacy-utility tradeoffs for symmetrically dependent sensitive and useful data under mutual information and Hamming distortion as the respective privacy and utility measures.
Design and Evaluation of a Novel Short Prototype Filter for FBMC/OQAM Modulation
Venue: arXiv cs.IT 2017
Year: 2017

Filter-Bank Multi-Carrier with Offset Quadrature Amplitude Modulation (FBMC/OQAM) is considered by recent research projects as one of the key enablers for the future 5G air interface. It exhibits better spectral shape and improves mobility support compared to Orthogonal Frequency-Division Multiplexing (OFDM) thanks to the use of a time and frequency localized prototype filter. The choice of this filter is crucial for FBMC/OQAM, due to its substantial impact on achieved performance and complexity levels. In the context of 5G, short frame sizes are foreseen in several communication scenarios to reduce system latency, and therefore short filters are preferred. In this context, a novel short filter allowing for near perfect reconstruction and having the same size as one OFDM symbol is proposed. Using Frequency-Spread (FS) implementation for the FBMC/OQAM receiver, analytical analysis and simulation results show that the proposed filter exhibits better robustness to several types of channel impairments when compared to State-of-The-Art (SoTA) prototype filters and OFDM modulation. In addition, FS-based hardware architecture of the filtering stage is proposed, showing lower complexity than the classical PolyPhase Network (PPN)-based implementation.
Setting the threshold for high throughput detectors: A mathematical approach for ensembles of dynamic, heterogeneous, probabilistic anomaly detectors
Venue: arXiv cs.CR 2017
Year: 2017

Anomaly detection (AD) has garnered ample attention in security research, as such algorithms complement existing signature-based methods but promise detection of never-before-seen attacks. Cyber operations manage a high volume of heterogeneous log data; hence, AD in such operations involves multiple (e.g., per IP, per data type) ensembles of detectors modeling heterogeneous characteristics (e.g., rate, size, type) often with adaptive online models producing alerts in near real time. Because of high data volume, setting the threshold for each detector in such a system is an essential yet underdeveloped configuration issue that, if slightly mistuned, can leave the system useless, either producing a myriad of alerts and flooding downstream systems, or giving none. In this work, we build on the foundations of Ferragut et al. to provide a set of rigorous results for understanding the relationship between threshold values and alert quantities, and we propose an algorithm for setting the threshold in practice. Specifically, we give an algorithm for setting the threshold of multiple, heterogeneous, possibly dynamic detectors completely a priori, in principle. Indeed, if the underlying distribution of the incoming data is known (closely estimated), the algorithm provides provably manageable thresholds. If the distribution is unknown (e.g., has changed over time) our analysis reveals how the model distribution differs from the actual distribution, indicating a period of model refitting is necessary. We provide empirical experiments showing the efficacy of the capability by regulating the alert rate of a system with $\approx$2,500 adaptive detectors scoring over 1.5M events in 5 hours. Further, we demonstrate on the real network data and detection framework of Harshaw et al. the alternative case, showing how the inability to regulate alerts indicates the detection model is a bad fit to the data.
Spatial Field estimation from Samples taken at Unknown Locations generated by an Unknown Autoregressive Process
Venue: arXiv cs.IT 2017
Year: 2017

Sampling of physical fields with mobile sensors is an upcoming field of interest. This offers greater advantages in terms of cost as often just a single sensor can be used for the purpose and this can be employed almost everywhere without sensing stations and has nominal operational costs. In a mobile sensing setup, the accurate knowledge of sampling locations may lead to a manifold increase in the costs. Moreover, the inertia of the moving vehicle constrains the independence between the intersample distances, making them correlated. This work, thus, aims at estimating spatially bandlimited fields from samples, corrupted with measurement noise, collected on sampling locations obtained from an autoregressive model on the intersample distances. The autoregressive model is used to capture the correlation between the intersample distances. In this setup of sampling at unknown sampling locations obtained from an autoregressive model on intersample distances, the mean squared error between the field and its estimated version has been shown to decrease as O($1/n$), where $n$ is the average number of samples taken by the moving sensor.
On Bandlimited Spatiotemporal Field Sampling with Location and Time Unaware Mobile Sensors
Venue: arXiv cs.IT 2017
Year: 2017

Sampling of a spatiotemporal field for environmental sensing is of interest. Traditionally, a few fixed stations or sampling locations aid in the reconstruction of the spatial field. Recently, there has been an interest in mobile sensing and location-unaware sensing of spatial fields. In this work, the general class of fields governed by a constant coefficient linear partial differential equations is considered. This class models many physical fields including temperature, pollution, and diffusion fields. The analysis is presented in one dimension for a first exposition. It is assumed that a mobile sensing unit is available to sample the spatiotemporal field of interest at unknown locations and unknown times -- both generated by independent and unknown renewal processes. Based on measurement-noise affected samples, a spatial field reconstruction algorithm is proposed. It is shown that if the initial condition on the field is bandlimited, then the mean squared error between the original and the estimated field decreases as $O(1/n)$, where $n$ is the average sampling density of the mobile sensor. The field reconstruction algorithm is universal, that is, it does not require the knowledge of unknown sampling locations' or unknown time instants' statistical distributions.
Rotational Unit of Memory
Venue: arXiv cs.LG 2017
Year: 2017

The concepts of unitary evolution matrices and associative memory have boosted the field of Recurrent Neural Networks (RNN) to state-of-the-art performance in a variety of sequential tasks. However, RNN still have a limited capacity to manipulate long-term memory. To bypass this weakness the most successful applications of RNN use external techniques such as attention mechanisms. In this paper we propose a novel RNN model that unifies the state-of-the-art approaches: Rotational Unit of Memory (RUM). The core of RUM is its rotational operation, which is, naturally, a unitary matrix, providing architectures with the power to learn long-term dependencies by overcoming the vanishing and exploding gradients problem. Moreover, the rotational unit also serves as associative memory. We evaluate our model on synthetic memorization, question answering and language modeling tasks. RUM learns the Copying Memory task completely and improves the state-of-the-art result in the Recall task. RUM's performance in the bAbI Question Answering task is comparable to that of models with attention mechanism. We also improve the state-of-the-art result to 1.189 bits-per-character (BPC) loss in the Character Level Penn Treebank (PTB) task, which is to signify the applications of RUM to real-world sequential data. The universality of our construction, at the core of RNN, establishes RUM as a promising approach to language modeling, speech recognition and machine translation.
ALL-IN-1: Short Text Classification with One Model for All Languages
Venue: arXiv cs.CL 2017
Year: 2017

We present ALL-IN-1, a simple model for multilingual text classification that does not require any parallel data. It is based on a traditional Support Vector Machine classifier exploiting multilingual word embeddings and character n-grams. Our model is simple, easily extendable yet very effective, overall ranking 1st (out of 12 teams) in the IJCNLP 2017 shared task on customer feedback analysis in four languages: English, French, Japanese and Spanish.
Improved Workflow for Unsupervised Multiphase Image Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Quantitative image analysis often depends on accurate classification of pixels through a segmentation process. However, imaging artifacts such as the partial volume effect and sensor noise complicate the classification process. These effects increase the pixel intensity variance of each constituent class, causing intensities from one class to overlap with another. This increased variance makes threshold based segmentation methods insufficient due to ambiguous overlap regions in the pixel intensity distributions. The class ambiguity becomes even more complex for systems with more than two constituents, such as unsaturated moist granular media. In this paper, we propose an image processing workflow that improves segmentation accuracy for multiphase systems. First, the ambiguous transition regions between classes are identified and removed, which allows for global thresholding of single-class regions. Then the transition regions are classified using a distance function, and finally both segmentations are combined into one classified image. This workflow includes three methodologies for identifying transition pixels and we demonstrate on a variety of synthetic images that these approaches are able to accurately separate the ambiguous transition pixels from the single-class regions. For situations with typical amounts of image noise, misclassification errors and area differences calculated between each class of the synthetic images and the resultant segmented images range from 0.69-1.48% and 0.01-0.74%, respectively, showing the segmentation accuracy of this approach. We demonstrate that we are able to accurately segment x-ray microtomography images of moist granular media using these computationally efficient methodologies.