OpenRaiser/Intern-Atlas huggingface dataset:
Jolie Static Type Checker: a prototype
Venue: arXiv cs.SE 2017
Year: 2017

Static verification of a program source code correctness is an important element of software reliability. Formal verification of software programs involves proving that a program satisfies a formal specification of its behavior. Many languages use both static and dynamic type checking. With such approach, the static type checker verifies everything possible at compile time, and dynamic checks the remaining. The current state of the Jolie programming language includes a dynamic type system. Consequently, it allows avoidable run-time errors. A static type system for the language has been formally defined on paper but lacks an implementation yet. In this paper, we describe a prototype of Jolie Static Type Checker (JSTC), which employs a technique based on a SMT solver. We describe the theory behind and the implementation, and the process of static analysis.
On Reversible Transducers
Venue: arXiv cs.FL 2017
Year: 2017

Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers cause a double exponential blow-up in the size of the inputs. In this paper, we introduce a class of transducers for which the composition has polynomial complexity. It is the class of reversible transducers, for which the computation steps can be reversed deterministically. While in the one-way setting this class is not very expressive, we prove that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, we prove that the composition of two-way transducers can be done with a single exponential blow-up in the number of states. A uniformization of a relation is a function with the same domain and which is included in the original relation. Our main result actually states that we can uniformize any non-deterministic two-way transducer by a reversible transducer with a single exponential blow-up, improving the known result by de Souza which has a quadruple exponential complexity. As a side result, our construction also gives a quadratic transformation from copyless streaming string transducers to two-way transducers, improving the exponential previous bound.
Utilizing Lexical Similarity between Related, Low-resource Languages for Pivot-based SMT
Venue: arXiv cs.CL 2017
Year: 2017

We investigate pivot-based translation between related languages in a low resource, phrase-based SMT setting. We show that a subword-level pivot-based SMT model using a related pivot language is substantially better than word and morpheme-level pivot models. It is also highly competitive with the best direct translation model, which is encouraging as no direct source-target training corpus is used. We also show that combining multiple related language pivot models can rival a direct translation model. Thus, the use of subwords as translation units coupled with multiple related pivot languages can compensate for the lack of a direct parallel corpus.
Massive MIMO Pilot Decontamination and Channel Interpolation via Wideband Sparse Channel Estimation
Venue: arXiv cs.IT 2017
Year: 2017

We consider a massive MIMO system based on Time Division Duplexing (TDD) and channel reciprocity, where the base stations (BSs) learn the channel vectors of their users via the pilots transmitted by the users in the uplink (UL). It is well-known that, in the limit of very large number of BS antennas, the system performance is limited by pilot contamination, due to the fact that the same set of orthogonal pilots is reused in multiple cells. In this paper, we propose a low-complexity algorithm that uses the received UL wideband pilot snapshots in an observation window comprising several coherence blocks (CBs) to obtain an estimate of the angle-delay Power Spread Function (PSF) of the received signal. This is generally given by the sum of the angle-delay PSF of the desired user and the angle-delay PSFs of the copilot users (CPUs), i.e., the users re-using the same pilot dimensions in other cells/sectors. We propose supervised and unsupervised clustering algorithms to decompose the estimated PSF and isolate the part corresponding to the desired user only. We use this decomposition to obtain an estimate of the covariance matrix of the user wideband channel vector, which we exploit to decontaminate the desired user channel estimate by applying Minimum Mean Squared Error (MMSE) smoothing filter, i.e., the optimal channel interpolator in the MMSE sense. We also propose an effective low-complexity approximation/implementation of this smoothing filter. We use numerical simulations to assess the performance of our proposed method, and compare it with other recently proposed schemes that use the same idea of separability of users in the angle-delay domain.
Online Load Balancing for Network Functions Virtualization
Venue: arXiv cs.NI 2017
Year: 2017

Network Functions Virtualization (NFV) aims to support service providers to deploy various services in a more agile and cost-effective way. However, the softwarization and cloudification of network functions can result in severe congestion and low network performance. In this paper, we propose a solution to address this issue. We analyze and solve the online load balancing problem using multipath routing in NFV to optimize network performance in response to the dynamic changes of user demands. In particular, we first formulate the optimization problem of load balancing as a mixed integer linear program for achieving the optimal solution. We then develop the ORBIT algorithm that solves the online load balancing problem. The performance guarantee of ORBIT is analytically proved in comparison with the optimal offline solution. The experiment results on real-world datasets show that ORBIT performs very well for distributing traffic of each service demand across multipaths without knowledge of future demands, especially under high-load conditions.
Generalized Bruhat decomposition in commutative domains
Venue: arXiv cs.SC 2017
Year: 2017

Deterministic recursive algorithms for the computation of generalized Bruhat decomposition of the matrix in commutative domain are presented. This method has the same complexity as the algorithm of matrix multiplication.
Experimental Validation of Contact Dynamics for In-Hand Manipulation
Venue: arXiv cs.RO 2017
Year: 2017

This paper evaluates state-of-the-art contact models at predicting the motions and forces involved in simple in-hand robotic manipulations. In particular it focuses on three primitive actions --linear sliding, pivoting, and rolling-- that involve contacts between a gripper, a rigid object, and their environment. The evaluation is done through thousands of controlled experiments designed to capture the motion of object and gripper, and all contact forces and torques at 250Hz. We demonstrate that a contact modeling approach based on Coulomb's friction law and maximum energy principle is effective at reasoning about interaction to first order, but limited for making accurate predictions. We attribute the major limitations to 1) the non-uniqueness of force resolution inherent to grasps with multiple hard contacts of complex geometries, 2) unmodeled dynamics due to contact compliance, and 3) unmodeled geometries dueto manufacturing defects.
Improving high-pass fusion method using wavelets
Venue: arXiv cs.CV 2017
Year: 2017

In an appropriate image fusion method, spatial information of the panchromatic image is injected into the multispectral images such that the spectral information is not distorted. The high-pass modulation method is a successful method in image fusion. However, the main drawback of this method is that this technique uses the boxcar filter to extract the high frequency information of the panchromatic image. Using the boxcar filter introduces the ringing effect into the fused image. To cope with this problem, we use the wavelet transform instead of boxcar filters. Then, the results of the proposed method and those of other methods such as, Brovey, IHS, and PCA ones are compared. Experiments show the superiority of the proposed method in terms of correlation coefficient and mutual information.
Toward Streaming Synapse Detection with Compositional ConvNets
Venue: arXiv cs.CV 2017
Year: 2017

Connectomics is an emerging field in neuroscience that aims to reconstruct the 3-dimensional morphology of neurons from electron microscopy (EM) images. Recent studies have successfully demonstrated the use of convolutional neural networks (ConvNets) for segmenting cell membranes to individuate neurons. However, there has been comparatively little success in high-throughput identification of the intercellular synaptic connections required for deriving connectivity graphs. In this study, we take a compositional approach to segmenting synapses, modeling them explicitly as an intercellular cleft co-located with an asymmetric vesicle density along a cell membrane. Instead of requiring a deep network to learn all natural combinations of this compositionality, we train lighter networks to model the simpler marginal distributions of membranes, clefts and vesicles from just 100 electron microscopy samples. These feature maps are then combined with simple rules-based heuristics derived from prior biological knowledge. Our approach to synapse detection is both more accurate than previous state-of-the-art (7% higher recall and 5% higher F1-score) and yields a 20-fold speed-up compared to the previous fastest implementations. We demonstrate by reconstructing the first complete, directed connectome from the largest available anisotropic microscopy dataset (245 GB) of mouse somatosensory cortex (S1) in just 9.7 hours on a single shared-memory CPU system. We believe that this work marks an important step toward the goal of a microscope-pace streaming connectomics pipeline.
An Optimal Algorithm for Computing the Spherical Depth of Points in the Plane
Venue: arXiv cs.CG 2017
Year: 2017

For a distribution function $F$ on $\mathbb{R}^d$ and a point $q\in \mathbb{R}^d$, the \emph{spherical depth} $\SphD(q;F)$ is defined to be the probability that a point $q$ is contained inside a random closed hyper-ball obtained from a pair of points from $F$. The spherical depth $\SphD(q;S)$ is also defined for an arbitrary data set $S\subseteq \mathbb{R}^d$ and $q\in \mathbb{R}^d$. This definition is based on counting all of the closed hyper-balls, obtained from pairs of points in $S$, that contain $q$. The significant advantage of using the spherical depth in multivariate data analysis is related to its complexity of computation. Unlike most other data depths, the time complexity of the spherical depth grows linearly rather than exponentially in the dimension $d$. The straightforward algorithm for computing the spherical depth in dimension $d$ takes $O(dn^2)$. The main result of this paper is an optimal algorithm that we present for computing the bivariate spherical depth. The algorithm takes $O(n \log n)$ time. By reducing the problem of \textit{Element Uniqueness}, we prove that computing the spherical depth requires $Ω(n \log n)$ time. Some geometric properties of spherical depth are also investigated in this paper. These properties indicate that \emph{simplicial depth} ($\SD$) (Liu, 1990) is linearly bounded by spherical depth (in particular, $\SphD\geq \frac{2}{3}SD$). To illustrate this relationship between the spherical depth and the simplicial depth, some experimental results are provided. The obtained experimental bound ($\SphD\geq 2\SD$) indicates that, perhaps, a stronger theoretical bound can be achieved.
A Debt-Aware Learning Approach for Resource Adaptations in Cloud Elasticity Management
Venue: arXiv cs.SE 2017
Year: 2017

Elasticity is a cloud property that enables applications and its execution systems to dynamically acquire and release shared computational resources on demand. Moreover, it unfolds the advantage of economies of scale in the cloud through a drop in the average costs of these shared resources. However, it is still an open challenge to achieve a perfect match between resource demand and provision in autonomous elasticity management. Resource adaptation decisions essentially involve a trade-off between economics and performance, which produces a gap between the ideal and actual resource provisioning. This gap, if not properly managed, can negatively impact the aggregate utility of a cloud customer in the long run. To address this limitation, we propose a technical debt-aware learning approach for autonomous elasticity management based on a reinforcement learning of elasticity debts in resource provisioning; the adaptation pursues strategic decisions that trades off economics against performance. We extend CloudSim and Burlap to evaluate our approach. The evaluation shows that a reinforcement learning of technical debts in elasticity obtains a higher utility for a cloud customer, while conforming expected levels of performance.
Assessment of Prediction Techniques: The Impact of Human Uncertainty
Venue: arXiv cs.HC 2017
Year: 2017

Many data mining approaches aim at modelling and predicting human behaviour. An important quantity of interest is the quality of model-based predictions, e.g. for finding a competition winner with best prediction performance. In real life, human beings meet their decisions with considerable uncertainty. Its assessment and resulting implications for statistically evident evaluation of predictive models are in the main focus of this contribution. We identify relevant sources of uncertainty as well as the limited ability of its accurate measurement, propose an uncertainty-aware methodology for more evident evaluations of data mining approaches, and discuss its implications for existing quality assessment strategies. Specifically, our approach switches from common point-paradigm to more appropriate distribution-paradigm. This is exemplified in the context of recommender systems and their established metrics of prediction quality. The discussion is substantiated by comprehensive experiments with real users, large-scale simulations, and discussion of prior evaluation campaigns (i.a. Netflix Prize) in the light of human uncertainty aspects.
Stochastic equivalence for performance analysis of concurrent systems in dtsiPBC
Venue: arXiv cs.LO 2017
Year: 2017

We propose an extension with immediate multiactions of discrete time stochastic Petri Box Calculus (dtsPBC), presented by I.V. Tarasyuk. The resulting algebra dtsiPBC is a discrete time analogue of stochastic Petri Box Calculus (sPBC) with immediate multiactions, designed by H. Macià, V. Valero et al. within a continuous time domain. The step operational semantics is constructed via labeled probabilistic transition systems. The denotational semantics is based on labeled discrete time stochastic Petri nets with immediate transitions. To evaluate performance, the corresponding semi-Markov chains are analyzed. We define step stochastic bisimulation equivalence of expressions that is applied to reduce their transition systems and underlying semi-Markov chains while preserving the functionality and performance characteristics. We explain how this equivalence can be used to simplify performance analysis of the algebraic processes. In a case study, a method of modeling, performance evaluation and behaviour reduction for concurrent systems is outlined and applied to the shared memory system.
SIFM: A network architecture for seamless flow mobility between LTE and WiFi networks - Analysis and Testbed Implementation
Venue: arXiv cs.NI 2017
Year: 2017

This paper deals with cellular (e.g. LTE) networks that selectively offload the mobile data traffic onto WiFi (IEEE 802.11) networks to improve network performance. We propose the Seamless Internetwork Flow Mobility (SIFM) architecture that provides seamless flow-mobility support using concepts of Software Defined Networking (SDN). The SDN paradigm decouples the control and data plane, leading to a centralized network intelligence and state. The SIFM architecture utilizes this aspect of SDN and moves the mobility decisions to a centralized Flow Controller (FC). This provides a global network view while making mobility decisions and also reduces the complexity at the PGW. We implement and evaluate both basic PMIPv6 and the SIFM architectures by incorporating salient LTE and WiFi network features in the ns-3 simulator. Performance experiments validate that seamless mobility is achieved. Also, the SIFM architecture shows an improved network performance when compared to the base PMIPv6 architecture. A proof-of-concept prototype of the SIFM architecture has been implemented on an experimental testbed. The LTE network is emulated by integrating USRP B210x with the OpenLTE eNodeB and OpenLTE EPC. The WiFi network is emulated using hostapd and dnsmasq daemons running on Ubuntu 12.04. An off-the-shelf LG G2 mobile phone running Android 4.2.2 is used as the user equipment. We demonstrate seamless mobility between the LTE network and the WiFi network with the help of ICMP ping and a TCP chat application.
Robot gains Social Intelligence through Multimodal Deep Reinforcement Learning
Venue: arXiv cs.RO 2017
Year: 2017

For robots to coexist with humans in a social world like ours, it is crucial that they possess human-like social interaction skills. Programming a robot to possess such skills is a challenging task. In this paper, we propose a Multimodal Deep Q-Network (MDQN) to enable a robot to learn human-like interaction skills through a trial and error method. This paper aims to develop a robot that gathers data during its interaction with a human and learns human interaction behaviour from the high-dimensional sensory information using end-to-end reinforcement learning. This paper demonstrates that the robot was able to learn basic interaction skills successfully, after 14 days of interacting with people.
Secure Clustered Distributed Storage Against Eavesdroppers
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the security issue of practical distributed storage systems (DSSs) which consist of multiple clusters of storage nodes. Noticing that actual storage nodes constituting a DSS are distributed in multiple clusters, two novel eavesdropper models - the node-restricted model and the cluster-restricted model - are suggested which reflect the clustered nature of DSSs. In the node-restricted model, an eavesdropper cannot access the individual nodes, but can eavesdrop incoming/outgoing data for $L_c$ compromised clusters. In the cluster-restricted model, an eavesdropper can access a total of $l$ individual nodes but the number of accessible clusters is limited to $L_c$. We provide an upper bound on the securely storable data for each model, while a specific network coding scheme which achieves the upper bound is obtained for the node-restricted model, given some mild condition on the node storage size.
Characterizing Classes of Potential Outliers through Traffic Data Set Data Signature 2D nMDS Projection
Venue: arXiv cs.OH 2017
Year: 2017

This paper presents a formal method for characterizing the potential outliers from the data signature projection of traffic data set using Non-Metric Multidimensional Scaling (nMDS) visualization. Previous work had only relied on visual inspection and the subjective nature of this technique may derive false and invalid potential outliers. The identification of correct potential outliers had already been an open problem proposed in literature. This is due to the fact that they pinpoint areas and time frames where traffic incidents/accidents occur along the North Luzon Expressway (NLEX) in Luzon. In this paper, potential outliers are classified into (1) absolute potential outliers; (2) valid potential outliers; and (3) ambiguous potential outliers through the use of confidence bands and confidence ellipse. A method is also described to validate cluster membership of identified ambiguous potential outliers. Using the 2006 NLEX Balintawak Northbound (BLK-NB) data set, we were able to identify two absolute potential outliers, nine valid potential outliers, and five ambiguous potential outliers. In a literature where Vector Fusion was used, 10 potential outliers were identified. Given the results for the nMDS visualization using the confidence bands and confidence ellipses, all of these 10 potential outliers were also found and 8 new potential outliers were also found.
High Throughput Probabilistic Shaping with Product Distribution Matching
Venue: arXiv cs.IT 2017
Year: 2017

Product distribution matching (PDM) is proposed to generate target distributions over large alphabets by combining the output of several parallel distribution matchers (DMs) with smaller output alphabets. The parallel architecture of PDM enables low-complexity and high-throughput implementation. PDM is used as a shaping device for probabilistic amplitude shaping (PAS). For 64-ASK and a spectral efficiency of 4.5 bits per channel use (bpcu), PDM is as power efficient as a single full-fledged DM. It is shown how PDM enables PAS for parallel channels present in multi-carrier systems like digital subscriber line (DSL) and orthogonal frequency-division multiplexing (OFDM). The key feature is that PDM shares the DMs for lower bit-levels among different sub-carriers, which improves the power efficiency significantly. A representative parallel channel example shows that PAS with PDM is 0.93 dB more power efficient than conventional uniform signaling and PDM is 0.35 dB more power efficient than individual per channel DMs.
Software Grand Exposure: SGX Cache Attacks Are Practical
Venue: arXiv cs.CR 2017
Year: 2017

Side-channel information leakage is a known limitation of SGX. Researchers have demonstrated that secret-dependent information can be extracted from enclave execution through page-fault access patterns. Consequently, various recent research efforts are actively seeking countermeasures to SGX side-channel attacks. It is widely assumed that SGX may be vulnerable to other side channels, such as cache access pattern monitoring, as well. However, prior to our work, the practicality and the extent of such information leakage was not studied. In this paper we demonstrate that cache-based attacks are indeed a serious threat to the confidentiality of SGX-protected programs. Our goal was to design an attack that is hard to mitigate using known defenses, and therefore we mount our attack without interrupting enclave execution. This approach has major technical challenges, since the existing cache monitoring techniques experience significant noise if the victim process is not interrupted. We designed and implemented novel attack techniques to reduce this noise by leveraging the capabilities of the privileged adversary. Our attacks are able to recover confidential information from SGX enclaves, which we illustrate in two example cases: extraction of an entire RSA-2048 key during RSA decryption, and detection of specific human genome sequences during genomic indexing. We show that our attacks are more effective than previous cache attacks and harder to mitigate than previous SGX side-channel attacks.