OpenRaiser/Intern-Atlas huggingface dataset:
Leveraging Motifs to Model the Temporal Dynamics of Diffusion Networks
Venue: arXiv cs.SI 2020
Year: 2020

Information diffusion mechanisms based on social influence models are mainly studied using likelihood of adoption when active neighbors expose a user to a message. The problem arises primarily from the fact that for the most part, this explicit information of who-exposed-whom among a group of active neighbors in a social network, before a susceptible node is infected is not available. In this paper, we attempt to understand the diffusion process through information cascades by studying the temporal network structure of the cascades. In doing so, we accommodate the effect of exposures from active neighbors of a node through a network pruning technique that leverages network motifs to identify potential infectors responsible for exposures from among those active neighbors. We attempt to evaluate the effectiveness of the components used in modeling cascade dynamics and especially whether the additional effect of the exposure information is useful. Following this model, we develop an inference algorithm namely InferCut, that uses parameters learned from the model and the exposure information to predict the actual parent node of each potentially susceptible user in a given cascade. Empirical evaluation on a real world dataset from Weibo social network demonstrate the significance of incorporating exposure information in recovering the exact parents of the exposed users at the early stages of the diffusion process.
Distributed Synthesis of Local Controllers for Networked Systems with Arbitrary Interconnection Topologies
Venue: arXiv cs.SY 2020
Year: 2020

We consider the problem of designing distributed controllers to guarantee dissipativity of a networked system comprised of dynamically coupled subsystems. We require that the control synthesis is carried out locally at the subsystem-level, without explicit knowledge of the dynamics of other subsystems in the network. We solve this problem in two steps. First, we provide distributed subsystem-level dissipativity analysis conditions whose feasibility is sufficient to guarantee dissipativity of the networked system. We then use these conditions to synthesize controllers locally at the subsystem-level, using only the knowledge of the dynamics of that subsystem, and limited information about the dissipativity of the subsystems to which it is dynamically coupled. We show that the subsystem-level controllers synthesized in this manner are sufficient to guarantee dissipativity of the networked dynamical system. We also provide an approach to make this synthesis compositional, that is, when a new subsystem is added to an existing network, only the dynamics of the new subsystem, and information about the dissipativity of the subsystems in the existing network to which it is coupled are used to design a controller for the new subsystem, while guaranteeing dissipativity of the networked system including the new subsystem. Finally, we demonstrate the application of this synthesis in enabling plug-and-play operations of generators in a microgrid by extending our results to networked switched systems.
Is Less Really More? Why Reducing Code Reuse Gadget Counts via Software Debloating Doesn't Necessarily Indicate Improved Security
Venue: arXiv cs.CR 2020
Year: 2020

Nearly all modern software suffers from bloat that negatively impacts its performance and security. To combat this problem, several automated techniques have been proposed to debloat software. A key metric used in many of these works to demonstrate improved security is code reuse gadget count reduction. The use of this metric is based on the prevailing idea that reducing the number of gadgets available in a software package reduces its attack surface and makes mounting a gadget-based code reuse exploit such as return-oriented programming (ROP) more difficult for an attacker. In this paper, we challenge this idea and show through a variety of realistic debloating scenarios the flaws inherent to the gadget count reduction metric. Specifically, we demonstrate that software debloating can achieve high gadget count reduction rates, yet fail to limit an attacker's ability to construct an exploit. Worse yet, in some scenarios high gadget count reduction rates conceal instances in which software debloating makes security worse by introducing new, useful gadgets. To address these issues, we propose a set of four new metrics for measuring security improvements realized through software debloating that are quality-oriented rather than quantity-oriented. We show that these metrics can identify when debloating negatively impacts security and be efficiently calculated using our static binary analysis tool, the Gadget Set Analyzer. Finally, we demonstrate the utility of these metrics in two realistic case studies: iterative debloating and debloater evaluation.
Channel Max Pooling Layer for Fine-Grained Vehicle Classification
Venue: arXiv cs.CV 2020
Year: 2020

Deep convolutional networks have recently shown excellent performance on Fine-Grained Vehicle Classification. Based on these existing works, we consider that the back-probation algorithm does not focus on extracting less discriminative feature as much as possible, but focus on that the loss function equals zero. Intuitively, if we can learn less discriminative features, and these features still could fit the training data well, the generalization ability of neural network could be improved. Therefore, we propose a new layer which is placed between fully connected layers and convolutional layers, called as Chanel Max Pooling. The proposed layer groups the features map first and then compress each group into a new feature map by computing maximum of pixels with same positions in the group of feature maps. Meanwhile, the proposed layer has an advantage that it could help neural network reduce massive parameters. Experimental results on two fine-grained vehicle datasets, the Stanford Cars-196 dataset and the Comp Cars dataset, demonstrate that the proposed layer could improve classification accuracies of deep neural networks on fine-grained vehicle classification in the situation that a massive of parameters are reduced. Moreover, it has a competitive performance with the-state-of-art performance on the two datasets.
Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs
Venue: arXiv cs.DS 2020
Year: 2020

We study the problem of online graph exploration on undirected graphs, where a searcher has to visit every vertex and return to the origin. Once a new vertex is visited, the searcher learns of all neighboring vertices and the connecting edge weights. The goal such an exploration is to minimize its total cost, where each edge traversal incurs a cost of the corresponding edge weight. We investigate the problem on tadpole graphs (also known as dragons, kites), which consist of a cycle with an attached path. Miyazaki et al. (The online graph exploration problem on restricted graphs, IEICE Transactions 92-D (9), 2009) showed that every online algorithm on these graphs must have a competitive ratio of 2-epsilon, but did not provide upper bounds for non-unit edge weights. We show via amortized analysis that a greedy approach yields a matching competitive ratio of 2 on tadpole graphs, for arbitrary non-negative edge weights.
DeepGini: Prioritizing Massive Tests to Enhance the Robustness of Deep Neural Networks
Venue: arXiv cs.SE 2020
Year: 2020

Deep neural networks (DNN) have been deployed in many software systems to assist in various classification tasks. In company with the fantastic effectiveness in classification, DNNs could also exhibit incorrect behaviors and result in accidents and losses. Therefore, testing techniques that can detect incorrect DNN behaviors and improve DNN quality are extremely necessary and critical. However, the testing oracle, which defines the correct output for a given input, is often not available in the automated testing. To obtain the oracle information, the testing tasks of DNN-based systems usually require expensive human efforts to label the testing data, which significantly slows down the process of quality assurance. To mitigate this problem, we propose DeepGini, a test prioritization technique designed based on a statistical perspective of DNN. Such a statistical perspective allows us to reduce the problem of measuring misclassification probability to the problem of measuring set impurity, which allows us to quickly identify possibly-misclassified tests. To evaluate, we conduct an extensive empirical study on popular datasets and prevalent DNN models. The experimental results demonstrate that DeepGini outperforms existing coverage-based techniques in prioritizing tests regarding both effectiveness and efficiency. Meanwhile, we observe that the tests prioritized at the front by DeepGini are more effective in improving the DNN quality in comparison with the coverage-based techniques.
Complex Stiffness Model of Physical Human-Robot Interaction: Implications for Control of Performance Augmentation Exoskeletons
Venue: arXiv cs.RO 2020
Year: 2020

Human joint dynamic stiffness plays an important role in the stability of performance augmentation exoskeletons. In this paper, we consider a new frequency domain model of the human joint dynamics which features a complex value stiffness. This complex stiffness consists of a real stiffness and a hysteretic damping. We use it to explain the dynamic behaviors of the human connected to the exoskeleton, in particular the observed non-zero low frequency phase shift and the near constant damping ratio of the resonant as stiffness and inertia vary. We validate this concept by experimenting with an elbow-joint exoskeleton testbed on a subject while modifying joint stiffness behavior, exoskeleton inertia, and strength augmentation gains. We compare three different models of elbow-joint dynamic stiffness: a model with real stiffness, viscous damping and inertia, a model with complex stiffness and inertia, and a model combining the previous two models. Our results show that the hysteretic damping term improves modeling accuracy, using a statistical F-test. Moreover this improvement is statistically more significant than using classical viscous damping term. In addition, we experimentally observe a linear relationship between the hysteretic damping and the real part of the stiffness which allows us to simplify the complex stiffness model as a 1-parameter system. Ultimately, we design a fractional order controller to demonstrate how human hysteretic damping behavior can be exploited to improve strength amplification performance while maintaining stability.
A survey of security and privacy issues in the Internet of Things from the layered context
Venue: arXiv cs.NI 2020
Year: 2020

Internet of Things (IoT) is a novel paradigm, which not only facilitates a large number of devices to be ubiquitously connected over the Internet but also provides a mechanism to remotely control these devices. The IoT is pervasive and is almost an integral part of our daily life. As devices are becoming increasingly connected, privacy and security issues become more and more critical and these need to be addressed on an urgent basis. IoT implementations and devices are eminently prone to threats that could compromise the security and privacy of the consumers, which, in turn, could influence its practical deployment. In recent past, some research has been carried out to secure IoT devices with an intention to alleviate the security concerns of users. The purpose of this paper is to highlight the security and privacy issues in IoT systems. To this effect, the paper examines the security issues at each layer in the IoT protocol stack, identifies the underlying challenges and key security requirements and provides a brief overview of existing security solutions to safeguard the IoT from the layered context.
Neural Networks Trained on Natural Scenes Exhibit Gestalt Closure
Venue: arXiv cs.LG 2020
Year: 2020

The Gestalt laws of perceptual organization, which describe how visual elements in an image are grouped and interpreted, have traditionally been thought of as innate despite their ecological validity. We use deep-learning methods to investigate whether natural scene statistics might be sufficient to derive the Gestalt laws. We examine the law of closure, which asserts that human visual perception tends to "close the gap" by assembling elements that can jointly be interpreted as a complete figure or object. We demonstrate that a state-of-the-art convolutional neural network, trained to classify natural images, exhibits closure on synthetic displays of edge fragments, as assessed by similarity of internal representations. This finding provides support for the hypothesis that the human perceptual system is even more elegant than the Gestaltists imagined: a single law---adaptation to the statistical structure of the environment---might suffice as fundamental.
Nonlinear Craig Interpolant Generation
Venue: arXiv cs.FL 2020
Year: 2020

Interpolation-based techniques have become popularized in recent years because of their inherently modular and local reasoning, which can scale up existing formal verification techniques like theorem proving, model-checking, abstraction interpretation, and so on, while the scalability is the bottleneck of these techniques. Craig interpolant generation plays a central role in interpolation-based techniques, and therefore has drawn increasing attentions. In the literature, there are various works done on how to automatically synthesize interpolants for decidable fragments of first-order logic, linear arithmetic, array logic, equality logic with uninterpreted functions (EUF), etc., and their combinations. But Craig interpolant generation for non-linear theory and its combination with the aforementioned theories are still in infancy, although some attempts have been done. In this paper, we first prove that a polynomial interpolant of the form $h(\mathbf{x})>0$ exists for two mutually contradictory polynomial formulas $ϕ(\mathbf{x},\mathbf{y})$ and $ψ(\mathbf{x},\mathbf{z})$, with the form $f_1\ge0\wedge\cdots\wedge f_n\ge0$, where $f_i$ are polynomials in $\mathbf{x},\mathbf{y}$ or $\mathbf{x},\mathbf{z}$, and the quadratic module generated by $f_i$ is Archimedean. Then, we show that synthesizing such interpolant can be reduced to solving a semi-definite programming problem (${\rm SDP}$). In addition, we propose a verification approach to assure the validity of the synthesized interpolant and consequently avoid the unsoundness caused by numerical error in ${\rm SDP}$ solving. Finally, we discuss how to generalize our approach to general semi-algebraic formulas.
TKD: Temporal Knowledge Distillation for Active Perception
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks based methods have been proved to achieve outstanding performance on object detection and classification tasks. Despite significant performance improvement, due to the deep structures, they still require prohibitive runtime to process images and maintain the highest possible performance for real-time applications. Observing the phenomenon that human vision system (HVS) relies heavily on the temporal dependencies among frames from the visual input to conduct recognition efficiently, we propose a novel framework dubbed as TKD: temporal knowledge distillation. This framework distills the temporal knowledge from a heavy neural networks based model over selected video frames (the perception of the moments) to a light-weight model. To enable the distillation, we put forward two novel procedures: 1) an Long-short Term Memory (LSTM) based key frame selection method; and 2) a novel teacher-bounded loss design. To validate, we conduct comprehensive empirical evaluations using different object detection methods over multiple datasets including Youtube-Objects and Hollywood scene dataset. Our results show consistent improvement in accuracy-speed trad-offs for object detection over the frames of the dynamic scene, compare to other modern object recognition methods.
MGpi: A Computational Model of Multiagent Group Perception and Interaction
Venue: arXiv cs.LG 2020
Year: 2020

Toward enabling next-generation robots capable of socially intelligent interaction with humans, we present a $\mathbf{computational\; model}$ of interactions in a social environment of multiple agents and multiple groups. The Multiagent Group Perception and Interaction (MGpi) network is a deep neural network that predicts the appropriate social action to execute in a group conversation (e.g., speak, listen, respond, leave), taking into account neighbors' observable features (e.g., location of people, gaze orientation, distraction, etc.). A central component of MGpi is the Kinesic-Proxemic-Message (KPM) gate, that performs social signal gating to extract important information from a group conversation. In particular, KPM gate filters incoming social cues from nearby agents by observing their body gestures (kinesics) and spatial behavior (proxemics). The MGpi network and its KPM gate are learned via imitation learning, using demonstrations from our designed $\mathbf{social\; interaction\; simulator}$. Further, we demonstrate the efficacy of the KPM gate as a social attention mechanism, achieving state-of-the-art performance on the task of $\mathbf{group\; identification}$ without using explicit group annotations, layout assumptions, or manually chosen parameters.
Profitable Double-Spending Attacks
Venue: arXiv cs.CR 2020
Year: 2020

Our aim in this paper is to investigate the profitability of double-spending (DS) attacks that manipulate an a priori mined transaction in a blockchain. It was well understood that a successful DS attack is established when the proportion of computing power an attacker possesses is higher than that the honest network does. What is not yet well understood is how threatening a DS attack with less than 50% computing power used can be. Namely, DS attacks at any proportion can be of a threat as long as the chance to making a good profit exists. Profit is obtained when the revenue from making a successful DS attack is greater than the cost of carrying out one. We have developed a novel probability theory for calculating a finite time attack probability. This can be used to size up attack resources needed to obtain the profit. The results enable us to derive a sufficient and necessary condition on the value of a transaction targeted by a DS attack. Our result is quite surprising: we theoretically show that DS attacks at any proportion of computing power can be made profitable. Given one's transaction size, the results can also be used to assess the risk of a DS attack. An example of the attack resources is provided for the BitcoinCash network.
Robust Semantic Segmentation By Dense Fusion Network On Blurred VHR Remote Sensing Images
Venue: arXiv cs.CV 2020
Year: 2020

Robust semantic segmentation of VHR remote sensing images from UAV sensors is critical for earth observation, land use, land cover or mapping applications. Several factors such as shadows, weather disruption and camera shakes making this problem highly challenging, especially only using RGB images. In this paper, we propose the use of multi-modality data including NIR, RGB and DSM to increase robustness of segmentation in blurred or partially damaged VHR remote sensing images. By proposing a cascaded dense encoder-decoder network and the SELayer based fusion and assembling techniques, the proposed RobustDenseNet achieves steady performance when the image quality is decreasing, compared with the state-of-the-art semantic segmentation model.
Hair Segmentation on Time-of-Flight RGBD Images
Venue: arXiv cs.CV 2020
Year: 2020

Robust segmentation of hair from portrait images remains challenging: hair does not conform to a uniform shape, style or even color; dark hair in particular lacks features. We present a novel computational imaging solution that tackles the problem from both input and processing fronts. We explore using Time-of-Flight (ToF) RGBD sensors on recent mobile devices. We first conduct a comprehensive analysis to show that scattering and inter-reflection cause different noise patterns on hair vs. non-hair regions on ToF images, by changing the light path and/or combining multiple paths. We then develop a deep network based approach that employs both ToF depth map and the RGB gradient maps to produce an initial hair segmentation with labeled hair components. We then refine the result by imposing ToF noise prior under the conditional random field. We collect the first ToF RGBD hair dataset with 20k+ head images captured on 30 human subjects with a variety of hairstyles at different view angles. Comprehensive experiments show that our approach outperforms the RGB based techniques in accuracy and robustness and can handle traditionally challenging cases such as dark hair, similar hair/background, similar hair/foreground, etc.
On the security of a Loidreau's rank metric code based encryption scheme
Venue: arXiv cs.IT 2020
Year: 2020

We present a polynomial time attack of a rank metric code based encryption scheme due to Loidreau for some parameters.
Learning Hierarchical Teaching Policies for Cooperative Agents
Venue: arXiv cs.LG 2020
Year: 2020

Collective learning can be greatly enhanced when agents effectively exchange knowledge with their peers. In particular, recent work studying agents that learn to teach other teammates has demonstrated that action advising accelerates team-wide learning. However, the prior work has simplified the learning of advising policies by using simple function approximations and only considered advising with primitive (low-level) actions, limiting the scalability of learning and teaching to complex domains. This paper introduces a novel learning-to-teach framework, called hierarchical multiagent teaching (HMAT), that improves scalability to complex environments by using the deep representation for student policies and by advising with more expressive extended action sequences over multiple levels of temporal abstraction. Our empirical evaluations demonstrate that HMAT improves team-wide learning progress in large, complex domains where previous approaches fail. HMAT also learns teaching policies that can effectively transfer knowledge to different teammates with knowledge of different tasks, even when the teammates have heterogeneous action spaces.
Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and ordered set union, intersection and difference. In the binary-forking model, tasks can only fork into two child tasks, but can do so recursively and asynchronously. The tasks share memory, supporting reads, writes and test-and-sets. Costs are measured in terms of work (total number of instructions), and span (longest dependence chain). The binary-forking model is meant to capture both algorithm performance and algorithm-design considerations on many existing multithreaded languages, which are also asynchronous and rely on binary forks either explicitly or under the covers. In contrast to the widely studied PRAM model, it does not assume arbitrary-way forks nor synchronous operations, both of which are hard to implement in modern hardware. While optimal PRAM algorithms are known for the problems studied herein, it turns out that arbitrary-way forking and strict synchronization are powerful, if unrealistic, capabilities. Natural simulations of these PRAM algorithms in the binary-forking model (i.e., implementations in existing parallel languages) incur an $Ω(\log n)$ overhead in span. This paper explores techniques for designing optimal algorithms when limited to binary forking and assuming asynchrony. All algorithms described in this paper are the first algorithms with optimal work and span in the binary-forking model. Most of the algorithms are simple. Many are randomized.