OpenRaiser/Intern-Atlas huggingface dataset:
Verification Artifacts in Cooperative Verification: Survey and Unifying Component Framework
Venue: arXiv cs.SE 2019
Year: 2019

The goal of cooperative verification is to combine verification approaches in such a way that they work together to verify a system model. In particular, cooperative verifiers provide exchangeable information (verification artifacts) to other verifiers or consume such information from other verifiers with the goal of increasing the overall effectiveness and efficiency of the verification process. This paper first gives an overview over approaches for leveraging strengths of different techniques, algorithms, and tools in order to increase the power and abilities of the state of the art in software verification. Second, we specifically outline cooperative verification approaches and discuss their employed verification artifacts. We formalize all artifacts in a uniform way, thereby fixing their semantics and providing verifiers with a precise meaning of the exchanged information.
Exploring the effects of Lx-norm penalty terms in multivariate curve resolution methods for resolving LC/GC-MS data
Venue: arXiv cs.LG 2019
Year: 2019

There are different problems for resolution of complex LC-MS or GC-MS data, such as the existence of embedded chromatographic peaks, continuum background and overlapping in mass channels for different components. These problems cause rotational ambiguity in recovered profiles calculated using multivariate curve resolution (MCR) methods. Since mass spectra are sparse in nature, sparsity has been proposed recently as a constraint in MCR methods for analyzing LC-MS data. There are different ways for implementation of the sparsity constraint, and majority of methods rely on imposing a penalty based on the L0-, L1- and L2-norms of recovered mass spectra. Ridge regression and least absolute shrinkage and selection operator (Lasso) can be used for implementation of L2- and L1-norm penalties in MCR, respectively. The main question is which Lx-norm penalty is more worthwhile for implementation of the sparsity constraint in MCR methods. In order to address this question, two and three component LC-MS data were simulated and used for the case study in this work. The areas of feasible solutions (AFS) were calculated using the grid search strategy. Calculating Lx-norms values in AFS for x between zero and two revealed that the gradient of optimization surface increased from x values equal to two to x values near zero. However, for x equal to zero, the optimization surface was similar to a plateau, which increased the risk of sticking in local minima. Generally, results in this work, recommend the use of L1-norm penalty methods like Lasso for implementation of sparsity constraint in MCR-ALS algorithm for finding more sparse solutions and reducing the extent of rotational ambiguity.
Machine learning approach for segmenting glands in colon histology images using local intensity and texture features
Venue: arXiv cs.CV 2019
Year: 2019

Colon Cancer is one of the most common types of cancer. The treatment is planned to depend on the grade or stage of cancer. One of the preconditions for grading of colon cancer is to segment the glandular structures of tissues. Manual segmentation method is very time-consuming, and it leads to life risk for the patients. The principal objective of this project is to assist the pathologist to accurate detection of colon cancer. In this paper, the authors have proposed an algorithm for an automatic segmentation of glands in colon histology using local intensity and texture features. Here the dataset images are cropped into patches with different window sizes and taken the intensity of those patches, and also calculated texture-based features. Random forest classifier has been used to classify this patch into different labels. A multilevel random forest technique in a hierarchical way is proposed. This solution is fast, accurate and it is very much applicable in a clinical setup.
Dilated Spatial Generative Adversarial Networks for Ergodic Image Generation
Venue: arXiv cs.CV 2019
Year: 2019

Generative models have recently received renewed attention as a result of adversarial learning. Generative adversarial networks consist of samples generation model and a discrimination model able to distinguish between genuine and synthetic samples. In combination with convolutional (for the discriminator) and de-convolutional (for the generator) layers, they are particularly suitable for image generation, especially of natural scenes. However, the presence of fully connected layers adds global dependencies in the generated images. This may lead to high and global variations in the generated sample for small local variations in the input noise. In this work we propose to use architec-tures based on fully convolutional networks (including among others dilated layers), architectures specifically designed to generate globally ergodic images, that is images without global dependencies. Conducted experiments reveal that these architectures are well suited for generating natural textures such as geologic structures .
Fonts-2-Handwriting: A Seed-Augment-Train framework for universal digit classification
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose a Seed-Augment-Train/Transfer (SAT) framework that contains a synthetic seed image dataset generation procedure for languages with different numeral systems using freely available open font file datasets. This seed dataset of images is then augmented to create a purely synthetic training dataset, which is in turn used to train a deep neural network and test on held-out real world handwritten digits dataset spanning five Indic scripts, Kannada, Tamil, Gujarati, Malayalam, and Devanagari. We showcase the efficacy of this approach both qualitatively, by training a Boundary-seeking GAN (BGAN) that generates realistic digit images in the five languages, and also quantitatively by testing a CNN trained on the synthetic data on the real-world datasets. This establishes not only an interesting nexus between the font-datasets-world and transfer learning but also provides a recipe for universal-digit classification in any script.
An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint
Venue: arXiv cs.DS 2019
Year: 2019

Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization within the procedure, which can complicate the analysis. We suggest a different, polyhedral viewpoint to design contention resolution schemes, which avoids to deal explicitly with the randomization in the second step. This is achieved by focusing on the marginals of a dropping procedure. Apart from avoiding one source of randomization, our viewpoint allows for employing polyhedral techniques. Both can significantly simplify the construction and analysis of contention resolution schemes. We show how, through our framework, one can obtain an optimal monotone contention resolution scheme for bipartite matchings. So far, only very few results are known about optimality of monotone contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings. Furthermore, we derive a monotone contention resolution scheme for matchings that significantly improves over the previously best one. At the same time, our scheme implies that the currently best lower bound on the correlation gap for matchings is not tight. Our results lead to improved approximation factors for various constrained submodular function maximization problems over a combination of matching constraints with further constraints.
MultiWiki: Interlingual Text Passage Alignment in Wikipedia
Venue: arXiv cs.CL 2019
Year: 2019

In this article we address the problem of text passage alignment across interlingual article pairs in Wikipedia. We develop methods that enable the identification and interlinking of text passages written in different languages and containing overlapping information. Interlingual text passage alignment can enable Wikipedia editors and readers to better understand language-specific context of entities, provide valuable insights in cultural differences and build a basis for qualitative analysis of the articles. An important challenge in this context is the trade-off between the granularity of the extracted text passages and the precision of the alignment. Whereas short text passages can result in more precise alignment, longer text passages can facilitate a better overview of the differences in an article pair. To better understand these aspects from the user perspective, we conduct a user study at the example of the German, Russian and the English Wikipedia and collect a user-annotated benchmark. Then we propose MultiWiki -- a method that adopts an integrated approach to the text passage alignment using semantic similarity measures and greedy algorithms and achieves precise results with respect to the user-defined alignment. MultiWiki demonstration is publicly available and currently supports four language pairs.
Your PIN Sounds Good! On The Feasibility of PIN Inference Through Audio Leakage
Venue: arXiv cs.CR 2019
Year: 2019

Personal Identification Numbers (PIN) are widely used as authentication method for systems such as Automated Teller Machines (ATMs) and Point of Sale (PoS). Input devices (PIN pads) usually give the user a feedback sound when a key is pressed. In this paper, we propose an attack based on the extraction of inter-keystroke timing from the feedback sound when users type their PINs. Our attack is able to reach an accuracy of 98% with a mean error of 0.13 +/-6.66 milliseconds. We demonstrate that inter-keystroke timing significantly improves the guessing probability of certain subsets of PINs. We believe this represents a security problem that has to be taken into account for secure PIN generation. Furthermore, we identified several attack scenarios where the adversary can exploit inter-keystroke timing and additional information about the user or the PIN, such as typing behavior. Our results show that combining the inter-keystroke timing with other information drastically reduces attempts to guess a PIN, outperforming random guessing. With our attack, we are able to guess 72% of the 4-digit PINs within 3 attempts. We believe this poses a serious security problem for systems that use PIN-based authentication.
Performance Analysis of Deep Learning Workloads on Leading-edge Systems
Venue: arXiv cs.PF 2019
Year: 2019

This work examines the performance of leading-edge systems designed for machine learning computing, including the NVIDIA DGX-2, Amazon Web Services (AWS) P3, IBM Power System Accelerated Compute Server AC922, and a consumer-grade Exxact TensorEX TS4 GPU server. Representative deep learning workloads from the fields of computer vision and natural language processing are the focus of the analysis. Performance analysis is performed along with a number of important dimensions. Performance of the communication interconnects and large and high-throughput deep learning models are considered. Different potential use models for the systems as standalone and in the cloud also are examined. The effect of various optimization of the deep learning models and system configurations is included in the analysis.
Economical Caching for Scalable Videos in Cache-enabled Heterogeneous Networks
Venue: arXiv cs.MM 2019
Year: 2019

We develop the optimal economical caching schemes in cache-enabled heterogeneous networks, while delivering multimedia video services with personalized viewing qualities to mobile users. By applying scalable video coding (SVC), each video file to be requested is divided into one base layer (BL) and several enhancement layers (ELs). In order to assign different transmission tasks, the serving small-cell base stations (SBSs) are grouped into K clusters. The SBSs are able to cache and cooperatively transmit BL and EL contents to the user. We analytically derive the expressions for successful transmission probability and ergodic service rate, and then the closed form of EConomical Efficiency (ECE) is obtained. In order to enhance the ECE performance, we formulate the ECE optimization problems for two cases. In the first case, with equal cache size equipped at each SBS, the layer caching indicator is determined. Since this problem is NP-hard, after the l0-norm approximation, the discrete optimization variables are relaxed to be continuous, and this relaxed problem is convex. Next, based on the optimal solution derived from the relaxed problem, we devise a greedystrategy based heuristic algorithm to achieve the near-optimal layer caching indicators. In the second case, the cache size for each SBS, the layer size and the layer caching indicator are jointly optimized. This problem is a mixed integer programming problem, which is more challenging. To effectively solve this problem, the original ECE maximization problem is divided into two subproblems. These two subproblems are iteratively solved until the original optimization problem is convergent. Numerical results verify the correctness of theoretical derivations. Additionally, compared to the most popular layer placement strategy, the performance superiority of the proposed SVC-based caching schemes is testified.
Codebooks from generalized bent $\mathbb{Z}_4$-valued quadratic forms
Venue: arXiv cs.IT 2019
Year: 2019

Codebooks with small inner-product correlation have application in unitary space-time modulations, multiple description coding over erasure channels, direct spread code division multiple access communications, compressed sensing, and coding theory. It is interesting to construct codebooks (asymptotically) achieving the Welch bound or the Levenshtein bound. This paper presented a class of generalized bent $\mathbb{Z}_4$-valued quadratic forms, which contain functions of Heng and Yue (Optimal codebooks achieving the Levenshtein bound from generalized bent functions over $\mathbb{Z}_4$. Cryptogr. Commun. 9(1), 41-53, 2017). By using these generalized bent $\mathbb{Z}_4$-valued quadratic forms, we constructs optimal codebooks achieving the Levenshtein bound. These codebooks have parameters $(2^{2m}+2^m,2^m)$ and alphabet size $6$.
Parallel Reachability in Almost Linear Work and Square Root Depth
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we provide a parallel algorithm that given any $n$-node $m$-edge directed graph and source vertex $s$ computes all vertices reachable from $s$ with $\tilde{O}(m)$ work and $n^{1/2 + o(1)}$ depth with high probability in $n$ . This algorithm also computes a set of $\tilde{O}(n)$ edges which when added to the graph preserves reachability and ensures that the diameter of the resulting graph is at most $n^{1/2 + o(1)}$. Our result improves upon the previous best known almost linear work reachability algorithm due to Fineman which had depth $\tilde{O}(n^{2/3})$. Further, we show how to leverage this algorithm to achieve improved distributed algorithms for single source reachability in the CONGEST model. In particular, we provide a distributed algorithm that given a $n$-node digraph of undirected hop-diameter $D$ solves the single source reachability problem with $\tilde{O}(n^{1/2} + n^{1/3 + o(1)} D^{2/3})$ rounds of the communication in the CONGEST model with high probability in $n$. Our algorithm is nearly optimal whenever $D = O(n^{1/4 - ε})$ for any constant $ε> 0$ and is the first nearly optimal algorithm for general graphs whose diameter is $Ω(n^δ)$ for any constant $δ$.
Properties and Extensions of Alternating Path Relevance - I
Venue: arXiv cs.LO 2019
Year: 2019

When proving theorems from large sets of logical assertions, it can be helpful to restrict the search for a proof to those assertions that are relevant, that is, closely related to the theorem in some sense. For example, in the Watson system, a large knowledge base must rapidly be searched for relevant facts. It is possible to define formal concepts of relevance for propositional and first-order logic. Various concepts of relevance have been defined for this, and some have yielded good results on large problems. We consider here in particular a concept based on alternating paths.We present efficient graph-based methods for computing alternating path relevance and give some results indicating its effectiveness. We also propose an alternating path based extension of this relevance method to DPLL with an improved time bound, and give other extensions to alternating path relevance intended to improve its performance.
Evolving neural networks to follow trajectories of arbitrary complexity
Venue: arXiv cs.NE 2019
Year: 2019

Many experiments have been performed that use evolutionary algorithms for learning the topology and connection weights of a neural network that controls a robot or virtual agent. These experiments are not only performed to better understand basic biological principles, but also with the hope that with further progress of the methods, they will become competitive for automatically creating robot behaviors of interest. However, current methods are limited with respect to the (Kolmogorov) complexity of evolved behavior. Using the evolution of robot trajectories as an example, we show that by adding four features, namely (1) freezing of previously evolved structure, (2) temporal scaffolding, (3) a homogeneous transfer function for output nodes, and (4) mutations that create new pathways to outputs, to standard methods for the evolution of neural networks, we can achieve an approximately linear growth of the complexity of behavior over thousands of generations. Overall, evolved complexity is up to two orders of magnitude over that achieved by standard methods in the experiments reported here, with the major limiting factor for further growth being the available run time. Thus, the set of methods proposed here promises to be a useful addition to various current neuroevolution methods.
Two Decades of SCADA Exploitation: A Brief History
Venue: arXiv cs.CR 2019
Year: 2019

Since the early 1960, industrial process control has been applied by electric systems. In the mid 1970's, the term SCADA emerged, describing the automated control and data acquisition. Since most industrial and automation networks were physically isolated, security was not an issue. This changed, when in the early 2000's industrial networks were opened to the public internet. The reasons were manifold. Increased interconnectivity led to more productivity, simplicity and ease of use. It decreased the configuration overhead and downtimes for system adjustments. However, it also led to an abundance of new attack vectors. In recent time, there has been a remarkable amount of attacks on industrial companies and infrastructures. In this paper, known attacks on industrial systems are analysed. This is done by investigating the exploits that are available on public sources. The different types of attacks and their points of entry are reviewed in this paper. Trends in exploitation as well as targeted attack campaigns against industrial enterprises are introduced.
Anchor-Less Producer Mobility Management in Named Data Networking for Real-Time Multimedia
Venue: arXiv cs.NI 2019
Year: 2019

Information-centric networking (ICN) is one of the promising solutions that cater to the challenges of IP-based networking. ICN shifts the IP-based access model to a data-centric model. Named Data Networking (NDN) is a flexible ICN architecture, which is based on content distribution considering data as the core entity rather than IP-based hosts. User-generated mobile contents for real-time multimedia communication such as Internet telephony are very common these days and are increasing both in quality and quantity. In NDN, producer mobility is one of the challenging problems to support uninterrupted real-time multimedia communication and needs to be resolved for the adoption of NDN as future Internet architecture. We assert that mobile nodes' future location prediction can aid in designing efficient anchor-less mobility management techniques. In this article, we show how location prediction techniques can be used to provide an anchor-less mobility management solution in order to ensure seamless handover of the producer during real-time multimedia communication. The results indicate that with a low level of location prediction accuracy, our proposed methodology still profoundly reduces the total handover latency and round trip time without creating network overhead.
Efficient Multi-Resource, Multi-Unit VCG Auction
Venue: arXiv cs.GT 2019
Year: 2019

We consider the optimization problem of a multi-resource, multi-unit VCG auction that produces an optimal, i.e., non-approximated, social welfare. We present an algorithm that solves this optimization problem with pseudo-polynomial complexity and demonstrate its efficiency via our implementation. Our implementation is efficient enough to be deployed in real systems to allocate computing resources in fine time-granularity. Our algorithm has a pseudo-near-linear time complexity on average (over all possible realistic inputs) with respect to the number of clients and the number of possible unit allocations. In the worst case, it is quadratic with respect to the number of possible allocations. Our experiments validate our analysis and show near-linear complexity. This is in contrast to the unbounded, nonpolynomial complexity of known solutions, which do not scale well for a large number of agents. For a single resource and concave valuations, our algorithm reproduces the results of a well-known algorithm. It does so, however, without subjecting the valuations to any restrictions and supports a multiple resource auction, which improves the social welfare over a combination of single-resource auctions by a factor of 2.5-50. This makes our algorithm applicable to real clients in a real system.
Practical Robot Learning from Demonstrations using Deep End-to-End Training
Venue: arXiv cs.RO 2019
Year: 2019

Robots need to learn behaviors in intuitive and practical ways for widespread deployment in human environments. To learn a robot behavior end-to-end, we train a variant of the ResNet that maps eye-in-hand camera images to end-effector velocities. In our setup, a human teacher demonstrates the task via joystick. We show that a simple servoing task can be learned in less than an hour including data collection, model training and deployment time. Moreover, 16 minutes of demonstrations were enough for the robot to learn the task.
Spatial Sampling Network for Fast Scene Understanding
Venue: arXiv cs.CV 2019
Year: 2019

We propose a network architecture to perform efficient scene understanding. This work presents three main novelties: the first is an Improved Guided Upsampling Module that can replace in toto the decoder part in common semantic segmentation networks. Our second contribution is the introduction of a new module based on spatial sampling to perform Instance Segmentation. It provides a very fast instance segmentation, needing only thresholding as post-processing step at inference time. Finally, we propose a novel efficient network design that includes the new modules and test it against different datasets for outdoor scene understanding. To our knowledge, our network is one of the themost efficient architectures for scene understanding published to date, furthermore being 8.6% more accurate than the fastest competitor on semantic segmentation and almost five times faster than the most efficient network for instance segmentation.