OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting Multi-Scale Fusion, Spatial Attention and Patch Interaction Techniques for Text-Independent Writer Identification
Venue: arXiv cs.CV 2021
Year: 2021

Text independent writer identification is a challenging problem that differentiates between different handwriting styles to decide the author of the handwritten text. Earlier writer identification relied on handcrafted features to reveal pieces of differences between writers. Recent work with the advent of convolutional neural network, deep learning-based methods have evolved. In this paper, three different deep learning techniques - spatial attention mechanism, multi-scale feature fusion and patch-based CNN were proposed to effectively capture the difference between each writer's handwriting. Our methods are based on the hypothesis that handwritten text images have specific spatial regions which are more unique to a writer's style, multi-scale features propagate characteristic features with respect to individual writers and patch-based features give more general and robust representations that helps to discriminate handwriting from different writers. The proposed methods outperforms various state-of-the-art methodologies on word-level and page-level writer identification methods on three publicly available datasets - CVL, Firemaker, CERUG-EN datasets and give comparable performance on the IAM dataset.
Probabilistic Model Checking and Autonomy
Venue: arXiv cs.LO 2021
Year: 2021

Design and control of autonomous systems that operate in uncertain or adversarial environments can be facilitated by formal modelling and analysis. Probabilistic model checking is a technique to automatically verify, for a given temporal logic specification, that a system model satisfies the specification, as well as to synthesise an optimal strategy for its control. This method has recently been extended to multi-agent systems that exhibit competitive or cooperative behaviour modelled via stochastic games and synthesis of equilibria strategies. In this paper, we provide an overview of probabilistic model checking, focusing on models supported by the PRISM and PRISM-games model checkers. This includes fully observable and partially observable Markov decision processes, as well as turn-based and concurrent stochastic games, together with associated probabilistic temporal logics. We demonstrate the applicability of the framework through illustrative examples from autonomous systems. Finally, we highlight research challenges and suggest directions for future work in this area.
TOUCAN: A proTocol tO secUre Controller Area Network
Venue: arXiv cs.CR 2021
Year: 2021

Modern cars are no longer purely mechanical devices but shelter so much digital technology that they resemble a network of computers. Electronic Control Units (ECUs) need to exchange a large amount of data for the various functions of the car to work, and such data must be made secure if we want those functions to work as intended despite malicious activity by attackers. TOUCAN is a new security protocol designed to be secure and at the same time both CAN and AUTOSAR compliant. It achieves security in terms of authenticity, integrity and confidentiality, yet without the need to upgrade (the hardware of) existing ECUs or enrich the network with novel components. The overhead is tiny, namely a reduction of the size of the Data field of a frame. A prototype implementation exhibits promising performance on a STM32F407Discovery board.
The Hidden Costs of Requiring Accounts: Quasi-Experimental Evidence From Peer Production
Venue: arXiv cs.CY 2021
Year: 2021

Online communities, like Wikipedia, produce valuable public information goods. Whereas some of these communities require would-be contributors to create accounts, many do not. Does this requirement catalyze cooperation or inhibit participation? Prior research provides divergent predictions but little causal evidence. We conduct an empirical test using longitudinal data from 136 natural experiments where would-be contributors to wikis were suddenly required to log in to contribute. Requiring accounts leads to a small increase in account creation, but reduces both high- and low-quality contributions from registered and unregistered participants. Although the change deters a large portion of low-quality participation, the vast majority of deterred contributions are of higher quality. We conclude that requiring accounts introduces an undertheorized tradeoff for public goods production in interactive communication systems.
Network Graph Generation through Adaptive Clustering and Infection Dynamics: A Step Towards Global Connectivity
Venue: arXiv cs.NI 2021
Year: 2021

More than 40% of the world's population is not connected to the internet, majorly due to the lack of adequate infrastructure. Our work aims to bridge this digital divide by proposing solutions for network deployment in remote areas. Specifically, a number of access points (APs) are deployed as an interface between the users and backhaul nodes (BNs). The main challenges include designing the number and location of the APs, and connecting them to the BNs. In order to address these challenges, we first propose a metric called connectivity ratio to assess the quality of the deployment. Next, we propose an agile search algorithm to determine the number of APs that maximizes this metric and perform clustering to find the optimal locations of the APs. Furthermore, we propose a novel algorithm inspired by infection dynamics to connect all the deployed APs to the existing BNs economically. To support the existing terrestrial BNs, we investigate the deployment of non-terrestrial BNs, which further improves the network performance in terms of average hop count, traffic distribution, and backhaul length. Finally, we use real datasets from a remote village to test our solution.
Self-Supervised Point Cloud Completion via Inpainting
Venue: arXiv cs.CV 2021
Year: 2021

When navigating in urban environments, many of the objects that need to be tracked and avoided are heavily occluded. Planning and tracking using these partial scans can be challenging. The aim of this work is to learn to complete these partial point clouds, giving us a full understanding of the object's geometry using only partial observations. Previous methods achieve this with the help of complete, ground-truth annotations of the target objects, which are available only for simulated datasets. However, such ground truth is unavailable for real-world LiDAR data. In this work, we present a self-supervised point cloud completion algorithm, PointPnCNet, which is trained only on partial scans without assuming access to complete, ground-truth annotations. Our method achieves this via inpainting. We remove a portion of the input data and train the network to complete the missing region. As it is difficult to determine which regions were occluded in the initial cloud and which were synthetically removed, our network learns to complete the full cloud, including the missing regions in the initial partial cloud. We show that our method outperforms previous unsupervised and weakly-supervised methods on both the synthetic dataset, ShapeNet, and real-world LiDAR dataset, Semantic KITTI.
MaIL: A Unified Mask-Image-Language Trimodal Network for Referring Image Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Referring image segmentation is a typical multi-modal task, which aims at generating a binary mask for referent described in given language expressions. Prior arts adopt a bimodal solution, taking images and languages as two modalities within an encoder-fusion-decoder pipeline. However, this pipeline is sub-optimal for the target task for two reasons. First, they only fuse high-level features produced by uni-modal encoders separately, which hinders sufficient cross-modal learning. Second, the uni-modal encoders are pre-trained independently, which brings inconsistency between pre-trained uni-modal tasks and the target multi-modal task. Besides, this pipeline often ignores or makes little use of intuitively beneficial instance-level features. To relieve these problems, we propose MaIL, which is a more concise encoder-decoder pipeline with a Mask-Image-Language trimodal encoder. Specifically, MaIL unifies uni-modal feature extractors and their fusion model into a deep modality interaction encoder, facilitating sufficient feature interaction across different modalities. Meanwhile, MaIL directly avoids the second limitation since no uni-modal encoders are needed anymore. Moreover, for the first time, we propose to introduce instance masks as an additional modality, which explicitly intensifies instance-level features and promotes finer segmentation results. The proposed MaIL set a new state-of-the-art on all frequently-used referring image segmentation datasets, including RefCOCO, RefCOCO+, and G-Ref, with significant gains, 3%-10% against previous best methods. Code will be released soon.
Secure Linear Aggregation Using Decentralized Threshold Additive Homomorphic Encryption For Federated Learning
Venue: arXiv cs.CR 2021
Year: 2021

Secure linear aggregation is to linearly aggregate private inputs of different users with privacy protection. The server in a federated learning (FL) environment can fulfill any linear computation on private inputs of users through the secure linear aggregation. At present, based on pseudo-random number generator and one-time padding technique, one can efficiently compute the sum of user inputs in FL, but linear calculations of user inputs are not well supported. Based on decentralized threshold additive homomorphic encryption (DTAHE) schemes, this paper provides a secure linear aggregation protocol, which allows the server to multiply the user inputs by any coefficients and to sum them together, so that the server can build a full connected layer or a convolution layer on top of user inputs. The protocol adopts the framework of Bonawitz et al. to provide fault tolerance for user dropping out, and exploits a blockchain smart contract to encourage the server honest. The paper gives a security model, security proofs and a concrete lattice based DTAHE scheme for the protocol. It evaluates the communication and computation costs of known DTAHE construction methods. The evaluation shows that an elliptic curve based DTAHE is friendly to users and the lattice based version leads to a light computation on the server.
Efficient Softmax Approximation for Deep Neural Networks with Attention Mechanism
Venue: arXiv cs.LG 2021
Year: 2021

There has been a rapid advance of custom hardware (HW) for accelerating the inference speed of deep neural networks (DNNs). Previously, the softmax layer was not a main concern of DNN accelerating HW, because its portion is relatively small in multi-layer perceptron or convolutional neural networks. However, as the attention mechanisms are widely used in various modern DNNs, a cost-efficient implementation of softmax layer is becoming very important. In this paper, we propose two methods to approximate softmax computation, which are based on the usage of LookUp Tables (LUTs). The required size of LUT is quite small (about 700 Bytes) because ranges of numerators and denominators of softmax are stable if normalization is applied to the input. We have validated the proposed technique over different AI tasks (object detection, machine translation, sentiment analysis, and semantic equivalence) and DNN models (DETR, Transformer, BERT) by a variety of benchmarks (COCO17, WMT14, WMT17, GLUE). We showed that 8-bit approximation allows to obtain acceptable accuracy loss below $1.0\%$.
Network representation learning: A macro and micro view
Venue: arXiv cs.LG 2021
Year: 2021

Graph is a universe data structure that is widely used to organize data in real-world. Various real-word networks like the transportation network, social and academic network can be represented by graphs. Recent years have witnessed the quick development on representing vertices in the network into a low-dimensional vector space, referred to as network representation learning. Representation learning can facilitate the design of new algorithms on the graph data. In this survey, we conduct a comprehensive review of current literature on network representation learning. Existing algorithms can be categorized into three groups: shallow embedding models, heterogeneous network embedding models, graph neural network based models. We review state-of-the-art algorithms for each category and discuss the essential differences between these algorithms. One advantage of the survey is that we systematically study the underlying theoretical foundations underlying the different categories of algorithms, which offers deep insights for better understanding the development of the network representation learning field.
Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Steiner Tree Problem (STP) in graphs aims to find a tree of minimum weight in the graph that connects a given set of vertices. It is a classic NP-hard combinatorial optimization problem and has many real-world applications (e.g., VLSI chip design, transportation network planning and wireless sensor networks). Many exact and approximate algorithms have been developed for STP, but they suffer from high computational complexity and weak worst-case solution guarantees, respectively. Heuristic algorithms are also developed. However, each of them requires application domain knowledge to design and is only suitable for specific scenarios. Motivated by the recently reported observation that instances of the same NP-hard combinatorial problem may maintain the same or similar combinatorial structure but mainly differ in their data, we investigate the feasibility and benefits of applying machine learning techniques to solving STP. To this end, we design a novel model Vulcan based on novel graph neural networks and deep reinforcement learning. The core of Vulcan is a novel, compact graph embedding that transforms highdimensional graph structure data (i.e., path-changed information) into a low-dimensional vector representation. Given an STP instance, Vulcan uses this embedding to encode its pathrelated information and sends the encoded graph to a deep reinforcement learning component based on a double deep Q network (DDQN) to find solutions. In addition to STP, Vulcan can also find solutions to a wide range of NP-hard problems (e.g., SAT, MVC and X3C) by reducing them to STP. We implement a prototype of Vulcan and demonstrate its efficacy and efficiency with extensive experiments using real-world and synthetic datasets.
New Binary-Addition Tree Algorithm for the All-Multiterminal Binary-State Network Reliability Problem
Venue: arXiv cs.NI 2021
Year: 2021

Various real-life applications, for example, Internet of Things, wireless sensor networks, smart grids, transportation networks, communication networks, social networks, and computer grid systems, are always modeled as network structures. The binary-state network composed of binary-state (e.g., functioning or failed) components (arcs and/or nodes) is one of the most popular network structures. The two-terminal network reliability is a success probability that the network is still functioning and can be calculated by verifying the connectivity between two specific nodes, and is an effective and popular technique for evaluating the performance of all types of networks. To obtain complete information for a making better decisions, a multi-terminal network reliability extends the two specific nodes to a specific node subset in which all nodes are connected. In this study, a new algorithm called the all-multiterminal BAT is proposed by revising the binary-addition-tree algorithm (BAT) and the layered-search algorithm (LSA) to calculate all multi-terminal reliabilities. The efficiency and effectiveness of the proposed all-multiterminal BAT are analyzed from the perspective of time complexity and explained via numerical experiments to solve the all-multiterminal network reliability problems.
CpT: Convolutional Point Transformer for 3D Point Cloud Processing
Venue: arXiv cs.CV 2021
Year: 2021

We present CpT: Convolutional point Transformer - a novel deep learning architecture for dealing with the unstructured nature of 3D point cloud data. CpT is an improvement over existing attention-based Convolutions Neural Networks as well as previous 3D point cloud processing transformers. It achieves this feat due to its effectiveness in creating a novel and robust attention-based point set embedding through a convolutional projection layer crafted for processing dynamically local point set neighbourhoods. The resultant point set embedding is robust to the permutations of the input points. Our novel CpT block builds over local neighbourhoods of points obtained via a dynamic graph computation at each layer of the networks' structure. It is fully differentiable and can be stacked just like convolutional layers to learn global properties of the points. We evaluate our model on standard benchmark datasets such as ModelNet40, ShapeNet Part Segmentation, and the S3DIS 3D indoor scene semantic segmentation dataset to show that our model can serve as an effective backbone for various point cloud processing tasks when compared to the existing state-of-the-art approaches.
Domain Page-Table Isolation
Venue: arXiv cs.CR 2021
Year: 2021

Modern applications often consist of different security domains that require isolation from each other. While several solutions exist, most of them rely on specialized hardware, hardware extensions, or require less-efficient software instrumentation of the application. In this paper, we propose Domain Page-Table Isolation (DPTI), a novel mechanism for hardware-enforced security domains that can be readily used on commodity off-the-shelf CPUs. DPTI uses two novel techniques for dynamic, time-limited changes to the memory isolation at security-critical points, called memory freezing and stashing. We demonstrate the versatility and efficacy of DPTI in two scenarios: First, DPTI freezes or stashes memory to support faster and more fine-grained syscall filtering than state-of-the-art seccomp-bpf. With the provided memory safety guarantees, DPTI can even securely support deep argument filtering, such as string comparisons. Second, DPTI freezes or stashes memory to efficiently confine potentially untrusted SGX enclaves, outperforming existing solutions by 14.6%-22% while providing the same security guarantees. Our results show that DPTI is a viable mechanism to isolate domains within applications using only existing mechanisms available on modern CPUs, without relying on special hardware instructions or extensions
On Fairness and Stability in Two-Sided Matchings
Venue: arXiv cs.CY 2021
Year: 2021

There are growing concerns that algorithms, which increasingly make or influence important decisions pertaining to individuals, might produce outcomes that discriminate against protected groups. We study such fairness concerns in the context of a two-sided market, where there are two sets of agents, and each agent has preferences over the other set. The goal is producing a matching between the sets. This setting has been the focus of a rich body of work. The seminal work of Gale and Shapley formulated a stability desideratum, and showed that a stable matching always exists and can be found efficiently. We study this question through the lens of metric-based fairness notions (Dwork et al., Kim et al.). We formulate appropriate definitions of fairness and stability in the presence of a similarity metric, and ask: does a fair and stable matching always exist? Can such a matching be found in polynomial time? Our contributions are as follows: (1) Composition failures for classical algorithms: We show that composing the Gale-Shapley algorithm with fair hospital preferences can produce blatantly unfair outcomes. (2) New algorithms for finding fair and stable matchings: Our main technical contributions are efficient new algorithms for finding fair and stable matchings when: (i) the hospitals' preferences are fair, and (ii) the fairness metric satisfies a strong "proto-metric" condition: the distance between every two doctors is either zero or one. In particular, these algorithms also show that, in this setting, fairness and stability are compatible. (3) Barriers for finding fair and stable matchings in the general case: We show that if the hospital preferences can be unfair, or if the metric fails to satisfy the proto-metric condition, then no algorithm in a natural class can find a fair and stable matching. The natural class includes the classical Gale-Shapley algorithms and our new algorithms.
Hybrid Imitative Planning with Geometric and Predictive Costs in Off-road Environments
Venue: arXiv cs.RO 2021
Year: 2021

Geometric methods for solving open-world off-road navigation tasks, by learning occupancy and metric maps, provide good generalization but can be brittle in outdoor environments that violate their assumptions (e.g., tall grass). Learning-based methods can directly learn collision-free behavior from raw observations, but are difficult to integrate with standard geometry-based pipelines. This creates an unfortunate conflict -- either use learning and lose out on well-understood geometric navigational components, or do not use it, in favor of extensively hand-tuned geometry-based cost maps. In this work, we reject this dichotomy by designing the learning and non-learning-based components in a way such that they can be effectively combined in a self-supervised manner. Both components contribute to a planning criterion: the learned component contributes predicted traversability as rewards, while the geometric component contributes obstacle cost information. We instantiate and comparatively evaluate our system in both in-distribution and out-of-distribution environments, showing that this approach inherits complementary gains from the learned and geometric components and significantly outperforms either of them. Videos of our results are hosted at https://sites.google.com/view/hybrid-imitative-planning
Towards a Zero-Trust Micro-segmentation Network Security Strategy: An Evaluation Framework
Venue: arXiv cs.NI 2021
Year: 2021

Micro-segmentation is an emerging security technique that separates physical networks into isolated logical micro-segments (workloads). By tying fine-grained security policies to individual workloads, it limits the attacker's ability to move laterally through the network, even after infiltrating the perimeter defences. While micro-segmentation is proved to be effective for shrinking enterprise networks attack surface, its impact assessment is almost absent in the literature. This research is dedicated to developing an analytical framework to characterise and quantify the effectiveness of micro-segmentation on enhancing networks security. We rely on a twofold graph-feature based framework of the network connectivity and attack graphs to evaluate the network exposure and robustness, respectively. While the former assesses the network assets connectedness, reachability and centrality, the latter depicts the ability of the network to resist goal-oriented attackers. Tracking the variations of formulated metrics values post the deployment of micro-segmentation reveals exposure reduction and robustness improvement in the range of 60% - 90%.