OpenRaiser/Intern-Atlas huggingface dataset:
SOAR: A Synthesis Approach for Data Science API Refactoring
Venue: arXiv cs.SE 2021
Year: 2021

With the growth of the open-source data science community, both the number of data science libraries and the number of versions for the same library are increasing rapidly. To match the evolving APIs from those libraries, open-source organizations often have to exert manual effort to refactor the APIs used in the code base. Moreover, due to the abundance of similar open-source libraries, data scientists working on a certain application may have an abundance of libraries to choose, maintain and migrate between. The manual refactoring between APIs is a tedious and error-prone task. Although recent research efforts were made on performing automatic API refactoring between different languages, previous work relies on statistical learning with collected pairwise training data for the API matching and migration. Using large statistical data for refactoring is not ideal because such training data will not be available for a new library or a new version of the same library. We introduce Synthesis for Open-Source API Refactoring (SOAR), a novel technique that requires no training data to achieve API migration and refactoring. SOAR relies only on the documentation that is readily available at the release of the library to learn API representations and mapping between libraries. Using program synthesis, SOAR automatically computes the correct configuration of arguments to the APIs and any glue code required to invoke those APIs. SOAR also uses the interpreter's error messages when running refactored code to generate logical constraints that can be used to prune the search space. Our empirical evaluation shows that SOAR can successfully refactor 80% of our benchmarks corresponding to deep learning models with up to 44 layers with an average run time of 97.23 seconds, and 90% of the data wrangling benchmarks with an average run time of 17.31 seconds.
A novel method for object detection using deep learning and CAD models
Venue: arXiv cs.CV 2021
Year: 2021

Object Detection (OD) is an important computer vision problem for industry, which can be used for quality control in the production lines, among other applications. Recently, Deep Learning (DL) methods have enabled practitioners to train OD models performing well on complex real world images. However, the adoption of these models in industry is still limited by the difficulty and the significant cost of collecting high quality training datasets. On the other hand, when applying OD to the context of production lines, CAD models of the objects to be detected are often available. In this paper, we introduce a fully automated method that uses a CAD model of an object and returns a fully trained OD model for detecting this object. To do this, we created a Blender script that generates realistic labeled datasets of images containing the object, which are then used for training the OD model. The method is validated experimentally on two practical examples, showing that this approach can generate OD models performing well on real images, while being trained only on synthetic images. The proposed method has potential to facilitate the adoption of object detection models in industry as it is easy to adapt for new objects and highly flexible. Hence, it can result in significant costs reduction, gains in productivity and improved products quality.
Supporting search engines with knowledge and context
Venue: arXiv cs.IR 2021
Year: 2021

Search engines leverage knowledge to improve information access. In order to effectively leverage knowledge, search engines should account for context, i.e., information about the user and query. In this thesis, we aim to support search engines in leveraging knowledge while accounting for context. In the first part of this thesis, we study how to make structured knowledge more accessible to the user when the search engine proactively provides such knowledge as context to enrich search results. As a first task, we study how to retrieve descriptions of knowledge facts from a text corpus. Next, we study how to automatically generate knowledge fact descriptions. And finally, we study how to contextualize knowledge facts, that is, to automatically find facts related to a query fact. In the second part of this thesis, we study how to improve interactive knowledge gathering. We focus on conversational search, where the user interacts with the search engine to gather knowledge over large unstructured knowledge repositories. We focus on multi-turn passage retrieval as an instance of conversational search. We propose to model query resolution as a term classification task and propose a method to address it. In the final part of this thesis, we focus on search engine support for professional writers in the news domain. We study how to support such writers create event-narratives by exploring knowledge from a corpus of news articles. We propose a dataset construction procedure for this task that relies on existing news articles to simulate incomplete narratives and relevant articles. We study the performance of multiple rankers, lexical and semantic, and provide insights into the characteristics of this task.
Asynchronous Gossip in Smartphone Peer-to-Peer Networks
Venue: arXiv cs.DC 2021
Year: 2021

In this paper, we study gossip algorithms in communication models that describe the peer-to-peer networking functionality included in most standard smartphone operating systems. We begin by describing and analyzing a new synchronous gossip algorithm in this setting that features both a faster round complexity and simpler operation than the best-known existing solutions. We also prove a new lower bound on the rounds required to solve gossip that resolves a minor open question by establishing that existing synchronous solutions are within logarithmic factors of optimal. We then adapt our synchronous algorithm to produce a novel gossip strategy for an asynchronous model that directly captures the interface of a standard smartphone peer-to-peer networking library (enabling algorithms described in this model to be easily implemented on real phones). Using new analysis techniques, we prove that this asynchronous strategy efficiently solves gossip. This is the first known efficient asynchronous information dissemination result for the smartphone peer-to-peer setting. We argue that our new strategy can be used to implement effective information spreading subroutines in real world smartphone peer-to-peer network applications, and that the analytical tools we developed to analyze it can be leveraged to produce other broadly useful algorithmic strategies for this increasingly important setting.
Systematic Mutation-based Evaluation of the Soundness of Security-focused Android Static Analysis Techniques
Venue: arXiv cs.CR 2021
Year: 2021

Mobile application security has been a major area of focus for security research over the course of the last decade. Numerous application analysis tools have been proposed in response to malicious, curious, or vulnerable apps. However, existing tools, and specifically, static analysis tools, trade soundness of the analysis for precision and performance and are hence soundy. Unfortunately, the specific unsound choices or flaws in the design of these tools is often not known or well-documented, leading to misplaced confidence among researchers, developers, and users. This paper describes the Mutation-based Soundness Evaluation ($μ$SE) framework, which systematically evaluates Android static analysis tools to discover, document, and fix flaws, by leveraging the well-founded practice of mutation analysis. We implemented $μ$SE and applied it to a set of prominent Android static analysis tools that detect private data leaks in apps. In a study conducted previously, we used $μ$SE to discover $13$ previously undocumented flaws in FlowDroid, one of the most prominent data leak detectors for Android apps. Moreover, we discovered that flaws also propagated to other tools that build upon the design or implementation of FlowDroid or its components. This paper substantially extends our $μ$SE framework and offers an new in-depth analysis of two more major tools in our 2020 study, we find $12$ new, undocumented flaws and demonstrate that all $25$ flaws are found in more than one tool, regardless of any inheritance-relation among the tools. Our results motivate the need for systematic discovery and documentation of unsound choices in soundy tools and demonstrate the opportunities in leveraging mutation testing in achieving this goal.
Bibliometric analysis on mathematics, 3 snapshots: 2005, 2010, 2015
Venue: arXiv cs.DL 2021
Year: 2021

We carry out a thorough bibliometric analysis of recent publications in mathematics based on the database Web of Science. The individual relations between various features and the citations are provided, and the importance of the features is investigated with decision trees. The evolution of the features over a period of 10 years is also studied. National and international collaborations are scrutinized, but personal information are fully disregarded.
Learning Speech-driven 3D Conversational Gestures from Video
Venue: arXiv cs.CV 2021
Year: 2021

We propose the first approach to automatically and jointly synthesize both the synchronous 3D conversational body and hand gestures, as well as 3D face and head animations, of a virtual character from speech input. Our algorithm uses a CNN architecture that leverages the inherent correlation between facial expression and hand gestures. Synthesis of conversational body gestures is a multi-modal problem since many similar gestures can plausibly accompany the same input speech. To synthesize plausible body gestures in this setting, we train a Generative Adversarial Network (GAN) based model that measures the plausibility of the generated sequences of 3D body motion when paired with the input audio features. We also contribute a new way to create a large corpus of more than 33 hours of annotated body, hand, and face data from in-the-wild videos of talking people. To this end, we apply state-of-the-art monocular approaches for 3D body and hand pose estimation as well as dense 3D face performance capture to the video corpus. In this way, we can train on orders of magnitude more data than previous algorithms that resort to complex in-studio motion capture solutions, and thereby train more expressive synthesis algorithms. Our experiments and user study show the state-of-the-art quality of our speech-synthesized full 3D character animations.
Learning Variable Impedance Control via Inverse Reinforcement Learning for Force-Related Tasks
Venue: arXiv cs.RO 2021
Year: 2021

Many manipulation tasks require robots to interact with unknown environments. In such applications, the ability to adapt the impedance according to different task phases and environment constraints is crucial for safety and performance. Although many approaches based on deep reinforcement learning (RL) and learning from demonstration (LfD) have been proposed to obtain variable impedance skills on contact-rich manipulation tasks, these skills are typically task-specific and could be sensitive to changes in task settings. This paper proposes an inverse reinforcement learning (IRL) based approach to recover both the variable impedance policy and reward function from expert demonstrations. We explore different action space of the reward functions to achieve a more general representation of expert variable impedance skills. Experiments on two variable impedance tasks (Peg-in-Hole and Cup-on-Plate) were conducted in both simulations and on a real FANUC LR Mate 200iD/7L industrial robot. The comparison results with behavior cloning and force-based IRL proved that the learned reward function in the gain action space has better transferability than in the force space. Experiment videos are available at https://msc.berkeley.edu/research/impedance-irl.html.
Deciding Polynomial Termination Complexity for VASS Programs
Venue: arXiv cs.LO 2021
Year: 2021

We show that for every fixed $k\geq 3$, the problem whether the termination/counter complexity of a given demonic VASS is $\mathcal{O}(n^k)$, $Ω(n^{k})$, and $Θ(n^{k})$ is coNP-complete, NP-complete, and DP-complete, respectively. We also classify the complexity of these problems for $k\leq 2$. This shows that the polynomial-time algorithm designed for strongly connected demonic VASS in previous works cannot be extended to the general case. Then, we prove that the same problems for VASS games are PSPACE-complete. Again, we classify the complexity also for $k\leq 2$. Interestingly, tractable subclasses of demonic VASS and VASS games are obtained by bounding certain structural parameters, which opens the way to applications in program analysis despite the presented lower complexity bounds.
Cache Bypassing for Machine Learning Algorithms
Venue: arXiv cs.AR 2021
Year: 2021

Graphics Processing Units (GPUs) were once used solely for graphical computation tasks but with the increase in the use of machine learning applications, the use of GPUs to perform general-purpose computing has increased in the last few years. GPUs employ a massive amount of threads, that in turn achieve a high amount of parallelism, to perform tasks. Though GPUs have a high amount of computation power, they face the problem of cache contention due to the SIMT model that they use. A solution to this problem is called "cache bypassing". This paper presents a predictive model that analyzes the access patterns of various machine learning algorithms and determines whether certain data should be stored in the cache or not. It presents insights on how well each model performs on different datasets and also shows how minimizing the size of each model will affect its performance The performance of most of the models were found to be around 90% with KNN performing the best but not with the smallest size. We further increase the features by splitting the addresses into chunks of 4 bytes. We observe that this increased the performance of the neural network substantially and increased the accuracy to 99.9% with three neurons.
DNA codes over two noncommutative rings of order four
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we describe a new type of DNA codes over two noncommutative rings $E$ and $F$ of order four with characteristic 2. Our DNA codes are based on quasi self-dual codes over $E$ and $F$. Using quasi self-duality, we can describe fixed GC-content constraint weight distributions and reverse-complement constraint minimum distributions of those codes.
Data-Driven Vulnerability Detection and Repair in Java Code
Venue: arXiv cs.CR 2021
Year: 2021

Java platform provides various APIs to facilitate secure coding. However, correctly using security APIs is usually challenging for developers who lack cybersecurity training. Prior work shows that many developers misuse security APIs; such misuses can introduce vulnerabilities into software, void security protections, and present security exploits to hackers. To eliminate such API-related vulnerabilities, this paper presents SEADER -- our new approach that detects and repairs security API misuses. Given an exemplar, insecure code snippet, and its secure counterpart, SEADER compares the snippets and conducts data dependence analysis to infer the security API misuse templates and corresponding fixing operations. Based on the inferred information, given a program, SEADER performs inter-procedural static analysis to search for any security API misuse and to propose customized fixing suggestions for those vulnerabilities. To evaluate SEADER, we applied it to 25 <insecure, secure> code pairs, and SEADER successfully inferred 18 unique API misuse templates and related fixes. With these vulnerability repair patterns, we further applied SEADER to 10 open-source projects that contain in total 32 known vulnerabilities. Our experiment shows that SEADER detected vulnerabilities with 100% precision, 84% recall, and 91% accuracy. Additionally, we applied SEADER to 100 Apache open-source projects and detected 988 vulnerabilities; SEADER always customized repair suggestions correctly. Based on SEADER's outputs, we filed 60 pull requests. Up till now, developers of 18 projects have offered positive feedbacks on SEADER's suggestions. Our results indicate that SEADER can effectively help developers detect and fix security API misuses. Whereas prior work either detects API misuses or suggests simple fixes, SEADER is the first tool to do both for nontrivial vulnerability repairs.
An Evolutionary Study of Configuration Design and Implementation in Cloud Systems
Venue: arXiv cs.SE 2021
Year: 2021

Many techniques were proposed for detecting software misconfigurations in cloud systems and for diagnosing unintended behavior caused by such misconfigurations. Detection and diagnosis are steps in the right direction: misconfigurations cause many costly failures and severe performance issues. But, we argue that continued focus on detection and diagnosis is symptomatic of a more serious problem: configuration design and implementation are not yet first-class software engineering endeavors in cloud systems. Little is known about how and why developers evolve configuration design and implementation, and the challenges that they face in doing so. This paper presents a source-code level study of the evolution of configuration design and implementation in cloud systems. Our goal is to understand the rationale and developer practices for revising initial configuration design/implementation decisions, especially in response to consequences of misconfigurations. To this end, we studied 1178 configuration-related commits from a 2.5 year version-control history of four large-scale, actively-maintained open-source cloud systems (HDFS, HBase, Spark, and Cassandra). We derive new insights into the software configuration engineering process. Our results motivate new techniques for proactively reducing misconfigurations by improving the configuration design and implementation process in cloud systems. We highlight a number of future research directions.
Survey on Aerial Radio Access Networks: Toward a Comprehensive 6G Access Infrastructure
Venue: arXiv cs.NI 2021
Year: 2021

Current network access infrastructures are characterized by heterogeneity, low latency, high throughput, and high computational capability, enabling massive concurrent connections and various services. Unfortunately, this design does not pay significant attention to mobile services in underserved areas. In this context, the use of aerial radio access networks (ARANs) is a promising strategy to complement existing terrestrial communication systems. Involving airborne components such as unmanned aerial vehicles, drones, and satellites, ARANs can quickly establish a flexible access infrastructure on demand. ARANs are expected to support the development of seamless mobile communication systems toward a comprehensive sixth-generation (6G) global access infrastructure. This paper provides an overview of recent studies regarding ARANs in the literature. First, we investigate related work to identify areas for further exploration in terms of recent knowledge advancements and analyses. Second, we define the scope and methodology of this study. Then, we describe ARAN architecture and its fundamental features for the development of 6G networks. In particular, we analyze the system model from several perspectives, including transmission propagation, energy consumption, communication latency, and network mobility. Furthermore, we introduce technologies that enable the success of ARAN implementations in terms of energy replenishment, operational management, and data delivery. Subsequently, we discuss application scenarios envisioned for these technologies. Finally, we highlight ongoing research efforts and trends toward 6G ARANs.
Simple vertex coloring algorithms
Venue: arXiv cs.DS 2021
Year: 2021

Given a graph $G$ with $n$ vertices and maximum degree $Δ$, it is known that $G$ admits a vertex coloring with $Δ+ 1$ colors such that no edge of $G$ is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time $O(nΔ)$. Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et. al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for $(ε+ 1)Δ$-coloring in the query model making $\tilde{O}(n\sqrt{n})$ queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of $Ω(n\sqrt n)$ for any $O(Δ)$-coloring is established on general graphs. In this work, we give a simple algorithm for $(1 + ε)Δ$-coloring. This algorithm makes $O(ε^{-1/2}n\sqrt{n})$ queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large $ε$. Additionally, it can be readily adapted to a quantum query algorithm making $\tilde{O}(ε^{-1}n^{4/3})$ queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of $Ω(n)$ for $O(Δ)$-coloring.
Domain Adversarial Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

We consider the problem of generalization in reinforcement learning where visual aspects of the observations might differ, e.g. when there are different backgrounds or change in contrast, brightness, etc. We assume that our agent has access to only a few of the MDPs from the MDP distribution during training. The performance of the agent is then reported on new unknown test domains drawn from the distribution (e.g. unseen backgrounds). For this "zero-shot RL" task, we enforce invariance of the learned representations to visual domains via a domain adversarial optimization process. We empirically show that this approach allows achieving a significant generalization improvement to new unseen domains.
Distributed Estimation, Control and Coordination of Quadcopter Swarm Robots
Venue: arXiv cs.RO 2021
Year: 2021

In this thesis we are interested in applying distributed estimation, control and optimization techniques to enable a group of quadcopters to fly through openings. The quadcopters are assumed to be equipped with a simulated bearing and distance sensor for localization. Some quadcopters are designated as leaders who carry global position sensors. We assume quadcopters can communicate information with each other.
Comprehensive Comparative Study of Multi-Label Classification Methods
Venue: arXiv cs.LG 2021
Year: 2021

Multi-label classification (MLC) has recently received increasing interest from the machine learning community. Several studies provide reviews of methods and datasets for MLC and a few provide empirical comparisons of MLC methods. However, they are limited in the number of methods and datasets considered. This work provides a comprehensive empirical study of a wide range of MLC methods on a plethora of datasets from various domains. More specifically, our study evaluates 26 methods on 42 benchmark datasets using 20 evaluation measures. The adopted evaluation methodology adheres to the highest literature standards for designing and executing large scale, time-budgeted experimental studies. First, the methods are selected based on their usage by the community, assuring representation of methods across the MLC taxonomy of methods and different base learners. Second, the datasets cover a wide range of complexity and domains of application. The selected evaluation measures assess the predictive performance and the efficiency of the methods. The results of the analysis identify RFPCT, RFDTBR, ECCJ48, EBRJ48 and AdaBoostMH as best performing methods across the spectrum of performance measures. Whenever a new method is introduced, it should be compared to different subsets of MLC methods, determined on the basis of the different evaluation criteria.