OpenRaiser/Intern-Atlas huggingface dataset:
CAPTIVE: Constrained Adversarial Perturbations to Thwart IC Reverse Engineering
Venue: arXiv cs.CR 2021
Year: 2021

Reverse engineering (RE) in Integrated Circuits (IC) is a process in which one will attempt to extract the internals of an IC, extract the circuit structure, and determine the gate-level information of an IC. In general, RE process can be done for validation as well as intellectual property (IP) stealing intentions. In addition, RE also facilitates different illicit activities such as insertion of hardware Trojan, pirate, or counterfeit a design, or develop an attack. In this work, we propose an approach to introduce cognitive perturbations, with the aid of adversarial machine learning, to the IC layout that could prevent the RE process from succeeding. We first construct a layer-by-layer image dataset of 45nm predictive technology. With this dataset, we propose a conventional neural network model called RecoG-Net to recognize the logic gates, which is the first step in RE. RecoG-Net is successfully to recognize the gates with more than 99.7% accuracy. Our thwarting approach utilizes the concept of the adversarial attack generation algorithms to generate perturbation. Unlike traditional adversarial attacks in machine learning, the perturbation generation needs to be highly constrained to meet the fab rules such as Design Rule Checking (DRC) Layout vs. Schematic (LVS) checks. Hence, we propose CAPTIVE as an constrained perturbation generation satisfying the DRC. The experiments shows that the accuracy of reverse engineering using machine learning techniques can decrease from 100% to approximately 30% based on the adversary generator.
A Fresh Look at the Architecture and Performance of Contemporary Isolation Platforms
Venue: arXiv cs.DC 2021
Year: 2021

With the ever-increasing pervasiveness of the cloud computing paradigm, strong isolation guarantees and low performance overhead from isolation platforms are paramount. An ideal isolation platform offers both: an impermeable isolation boundary while imposing a negligible performance overhead. In this paper, we examine various isolation platforms (containers, secure containers, hypervisors, unikernels), and conduct a wide array of experiments to measure the performance overhead and degree of isolation offered by the platforms. We find that container platforms have the best, near-native, performance while the newly emerging secure containers suffer from various overheads. The highest degree of isolation is achieved by unikernels, closely followed by traditional containers.
Real-Time Ground-Plane Refined LiDAR SLAM
Venue: arXiv cs.RO 2021
Year: 2021

SLAM system using only point cloud has been proven successful in recent years. In most of these systems, they extract features for tracking after ground removal, which causes large variance on the z-axis. Ground actually provides robust information to obtain [t_z, θ_{roll}, θ_{pitch}]$. In this project, we followed the LeGO-LOAM, a light-weighted real-time SLAM system that extracts and registers ground as an addition to the original LOAM, and we proposed a new clustering-based method to refine the planar extraction algorithm for ground such that the system can handle much more noisy or dynamic environments. We implemented this method and compared it with LeGo-LOAM on our collected data of CMU campus, as well as a collected dataset for ATV (All-Terrain Vehicle) for off-road self-driving. Both visualization and evaluation results show obvious improvement of our algorithm.
SiliFuzz: Fuzzing CPUs by proxy
Venue: arXiv cs.AR 2021
Year: 2021

CPUs are becoming more complex with every generation, at both the logical and the physical levels. This potentially leads to more logic bugs and electrical defects in CPUs being overlooked during testing, which causes data corruption or other undesirable effects when these CPUs are used in production. These ever-present problems may also have simply become more evident as more CPUs are operated and monitored by large cloud providers. If the RTL ("source code") of a CPU were available, we could apply greybox fuzzing to the CPU model almost as we do to any other software [arXiv:2102.02308]. However our targets are general purpose x86_64 CPUs produced by third parties, where we do not have the RTL design, so in our case CPU implementations are opaque. Moreover, we are more interested in electrical defects as opposed to logic bugs. We present SiliFuzz, a work-in-progress system that finds CPU defects by fuzzing software proxies, like CPU simulators or disassemblers, and then executing the accumulated test inputs (known as the corpus) on actual CPUs on a large scale. The major difference between this work and traditional software fuzzing is that a software bug fixed once will be fixed for all installations of the software, while for CPU defects we have to test every individual core repeatedly over its lifetime due to wear and tear. In this paper we also analyze four groups of CPU defects that SiliFuzz has uncovered and describe patterns shared by other SiliFuzz findings.
GCNScheduler: Scheduling Distributed Computing Applications using Graph Convolutional Networks
Venue: arXiv cs.DC 2021
Year: 2021

We consider the classical problem of scheduling task graphs corresponding to complex applications on distributed computing systems. A number of heuristics have been previously proposed to optimize task scheduling with respect to metrics such as makespan and throughput. However, they tend to be slow to run, particularly for larger problem instances, limiting their applicability in more dynamic systems. Motivated by the goal of solving these problems more rapidly, we propose, for the first time, a graph convolutional network-based scheduler (GCNScheduler). By carefully integrating an inter-task data dependency structure with network settings into an input graph and feeding it to an appropriate GCN, the GCNScheduler can efficiently schedule tasks of complex applications for a given objective. We evaluate our scheme with baselines through simulations. We show that not only can our scheme quickly and efficiently learn from existing scheduling schemes, but also it can easily be applied to large-scale settings where current scheduling schemes fail to handle. We show that it achieves better makespan than the classic HEFT algorithm, and almost the same throughput as throughput-oriented HEFT (TP-HEFT), while providing several orders of magnitude faster scheduling times in both cases. For example, for makespan minimization, GCNScheduler schedules 50-node task graphs in about 4 milliseconds while HEFT takes more than 1500 seconds; and for throughput maximization, GCNScheduler schedules 100-node task graphs in about 3.3 milliseconds, compared to about 6.9 seconds for TP-HEFT.
Methodology for Assessing the State of the Practice for Domain X
Venue: arXiv cs.SE 2021
Year: 2021

To improve software development methods and tools for research software, we first need to understand the current state of the practice. Therefore, we have developed a methodology for assessing the state of the software development practices for a given research software domain. For each domain we wish to answer questions such as: i) What artifacts (documents, code, test cases, etc.) are present? ii) What tools are used? iii) What principles, process and methodologies are used? iv) What are the pain points for developers? v) What actions are used to improve qualities like maintainability and reproducibility? To answer these questions, our methodology prescribes the following steps: i) Identify the domain; ii) Identify a list of candidate software packages; iii) Filter the list to a length of about 30 packages; iv) Gather source code and documentation for each package; v) Collect repository related data on each software package, like number of stars, number of open issues, number of lines of code; vi) Fill in the measurement template (the template consists of 108 questions to assess 9 qualities (including the qualities of installability, usability and visibility)); vii) Interview developers (the interview consists of 20 questions and takes about an hour); viii) Rank the software using the Analytic Hierarchy Process (AHP); and, ix) Analyze the data to answer the questions posed above. A domain expert should be engaged throughout the process, to ensure that implicit information about the domain is properly represented and to assist with conducting an analysis of the commonalities and variabilities between the 30 selected packages. Using our methodology, spreadsheet templates and AHP tool, we estimate (based on our experience with using the process) the time to complete an assessment for a given domain at 173 person hours.
PRECAD: Privacy-Preserving and Robust Federated Learning via Crypto-Aided Differential Privacy
Venue: arXiv cs.CR 2021
Year: 2021

Federated Learning (FL) allows multiple participating clients to train machine learning models collaboratively by keeping their datasets local and only exchanging model updates. Existing FL protocol designs have been shown to be vulnerable to attacks that aim to compromise data privacy and/or model robustness. Recently proposed defenses focused on ensuring either privacy or robustness, but not both. In this paper, we develop a framework called PRECAD, which simultaneously achieves differential privacy (DP) and enhances robustness against model poisoning attacks with the help of cryptography. Using secure multi-party computation (MPC) techniques (e.g., secret sharing), noise is added to the model updates by the honest-but-curious server(s) (instead of each client) without revealing clients' inputs, which achieves the benefit of centralized DP in terms of providing a better privacy-utility tradeoff than local DP based solutions. Meanwhile, a crypto-aided secure validation protocol is designed to verify that the contribution of model update from each client is bounded without leaking privacy. We show analytically that the noise added to ensure DP also provides enhanced robustness against malicious model submissions. We experimentally demonstrate that our PRECAD framework achieves higher privacy-utility tradeoff and enhances robustness for the trained models.
EvoGAN: An Evolutionary Computation Assisted GAN
Venue: arXiv cs.CV 2021
Year: 2021

The image synthesis technique is relatively well established which can generate facial images that are indistinguishable even by human beings. However, all of these approaches uses gradients to condition the output, resulting in the outputting the same image with the same input. Also, they can only generate images with basic expression or mimic an expression instead of generating compound expression. In real life, however, human expressions are of great diversity and complexity. In this paper, we propose an evolutionary algorithm (EA) assisted GAN, named EvoGAN, to generate various compound expressions with any accurate target compound expression. EvoGAN uses an EA to search target results in the data distribution learned by GAN. Specifically, we use the Facial Action Coding System (FACS) as the encoding of an EA and use a pre-trained GAN to generate human facial images, and then use a pre-trained classifier to recognize the expression composition of the synthesized images as the fitness function to guide the search of the EA. Combined random searching algorithm, various images with the target expression can be easily sythesized. Quantitative and Qualitative results are presented on several compound expressions, and the experimental results demonstrate the feasibility and the potential of EvoGAN.
Compressed Geometric Arrays for Point Cloud Processing
Venue: arXiv cs.MM 2021
Year: 2021

The ever-increasing demand for 3D modeling in the emerging immersive applications has made point clouds an essential class of data for 3D image and video processing. Tree based structures are commonly used for representing point clouds where pointers are used to realize the connection between nodes. Tree-based structures significantly suffer from irregular access patterns for large point clouds. Memory access indirection in such structures is disruptive to bandwidth efficiency and performance. In this paper, we propose a point cloud representation format based on compressed geometric arrays (CGA). Then, we examine new methods for point cloud processing based on CGA. The proposed format enables a higher bandwidth efficiency via eliminating memory access indirections (i.e., pointer chasing at the nodes of tree) thereby improving the efficiency of point cloud processing. Our experimental results show that using CGA for point cloud operations achieves 1328x speed up, 1321x better bandwidth utilization, and 54% reduction in the volume of transferred data as compared to the state-of-the-art tree-based format from point cloud library (PCL).
Node package manager's dependency network robustness
Venue: arXiv cs.SI 2021
Year: 2021

The robustness of npm dependency network is a crucial property, since many projects and web applications heavily rely on the functionalities of packages, especially popular ones that have many dependant packages. In the past, there have been instances where the removal or update of certain npm packages has caused widespread chaos and web-page downtime on the internet. Our goal is to track the network's resilience to such occurrences through time and figure out whether the state of the network is trending towards a more robust structure. We show that the network is not robust to targeted attacks, since a security risk in a few crucial nodes affects a large part of the network. Because such packages are often backed up by serious communities with high standards, the issue is not alarming and is a consequence of power law distribution of the network. The current trend in average number of dependencies and effect of important nodes on the rest of the network is decreasing, which further improves the resilience and sets a positive path in development. Furthermore, we show that communities form around the most important packages, although they do not conform well to the common community definition using modularity. We also provide guidelines for package development that increases the robustness of the network and reduces the possibility of introducing security risks.
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Venue: arXiv cs.DS 2021
Year: 2021

Given a directed, weighted graph $G=(V,E)$ undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances from a dedicated source $s$ while optimizing the total time required to process the insertion sequence of $m$ edges. Recently, Gutenberg, Williams and Wein [STOC'20] introduced a deterministic $\tilde{O}(n^2)$ algorithm for this problem, achieving near linear time for very dense graphs. For sparse graphs, Chechik and Zhang [SODA'21] recently presented a deterministic $\tilde{O}(m^{5/3})$ algorithm, and an adaptive randomized algorithm with run-time $\tilde{O}(m\sqrt{n} + m^{7/5})$. This algorithm is remarkable for two reasons: 1) in very spare graphs it reaches the directed hopset barrier of $\tildeΩ(n^{3/2})$ that applied to all previous approaches for partially-dynamic SSSP [STOC'14, SODA'20, FOCS'20] \emph{and} 2) it does not resort to a directed hopset technique itself. In this article we introduce \emph{propagation synchronization}, a new technique for controlling the error build-up on paths throughout batches of insertions. This leads us to a significant improvement of the approach in [SODA'21] yielding a \emph{deterministic} $\tilde{O}(m^{3/2})$ algorithm for the problem. By a very careful combination of our new technique with the sampling approach from [SODA'21], we further obtain an adaptive randomized algorithm with total update time $\tilde{O}(m^{4/3})$. This is the first partially-dynamic SSSP algorithm in sparse graphs to bypass the notorious directed hopset barrier which is often seen as the fundamental challenge towards achieving truly near-linear time algorithms.
Measuring the Non-Transitivity in Chess
Venue: arXiv cs.AI 2021
Year: 2021

It has long been believed that Chess is the \emph{Drosophila} of Artificial Intelligence (AI). Studying Chess can productively provide valid knowledge about complex systems. Although remarkable progress has been made on solving Chess, the geometrical landscape of Chess in the strategy space is still mysterious. Judging on AI-generated strategies, researchers hypothesised that the strategy space of Chess possesses a spinning top geometry, with the upright axis representing the \emph{transitive} dimension (e.g., A beats B, B beats C, A beats C), and the radial axis representing the \emph{non-transitive} dimension (e.g., A beats B, B beats C, C beats A). However, it is unclear whether such a hypothesis holds for real-world strategies. In this paper, we quantify the non-transitivity in Chess through real-world data from human players. Specifically, we performed two ways of non-transitivity quantifications -- Nash Clustering and counting the number of Rock-Paper-Scissor cycles -- on over one billion match data from Lichess and FICS. Our findings positively indicate that the strategy space occupied by real-world Chess strategies demonstrates a spinning top geometry, and more importantly, there exists a strong connection between the degree of non-transitivity and the progression of a Chess player's rating. In particular, high degrees of non-transitivity tend to prevent human players from making progress on their Elo rating, whereas progressions are easier to make at the level of ratings where the degree of non-transitivity is lower. Additionally, we also investigate the implication of the degree of non-transitivity for population-based training methods. By considering \emph{fixed-memory Fictitious Play} as a proxy, we reach the conclusion that maintaining large-size and diverse populations of strategies is imperative to training effective AI agents in solving Chess types of games.
Monitoring with Verified Guarantees
Venue: arXiv cs.LO 2021
Year: 2021

Runtime monitoring is generally considered a light-weight alternative to formal verification. In safety-critical systems, however, the monitor itself is a critical component. For example, if the monitor is responsible for initiating emergency protocols, as proposed in a recent aviation standard, then the safety of the entire system critically depends on guarantees of the correctness of the monitor. In this paper, we present a verification extension to the Lola monitoring language that integrates the efficient specification of the monitor with Hoare-style annotations that guarantee the correctness of the monitor specification. We add two new operators, assume and assert, which specify assumptions of the monitor and expectations on its output, respectively. The validity of the annotations is established by an integrated SMT solver. We report on experience in applying the approach to specifications from the avionics domain, where the annotation with assumptions and assertions has lead to the discovery of safety-critical errors in the specifications. The errors range from incorrect default values in offset computations to complex algorithmic errors that result in unexpected temporal patterns.
cleanTS: Automated (AutoML) Tool to Clean Univariate Time Series at Microscales
Venue: arXiv cs.DB 2021
Year: 2021

Data cleaning is one of the most important tasks in data analysis processes. One of the perennial challenges in data analytics is the detection and handling of non-valid data. Failing to do so can result in inaccurate analytics and unreliable decisions. The process of properly cleaning such data takes much time. Errors are prevalent in time series data. It is usually found that real world data is unclean and requires some pre-processing. The analysis of large amounts of data is difficult. This paper is intended to provide an easy to use and reliable system which automates the cleaning process of univariate time series data. Automating the process greatly reduces the time required. Visualizing a large amount of data at once is not very effective. To tackle this issue, an R package cleanTS is proposed. The proposed system provides a way to analyze data on different scales and resolutions. Also, it provides users with tools and a benchmark system for comparing various techniques used in data cleaning.
Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
Venue: arXiv cs.DS 2021
Year: 2021

In this work, we revisit the problem of estimating the mean and covariance of an unknown $d$-dimensional Gaussian distribution in the presence of an $\varepsilon$-fraction of adversarial outliers. The pioneering work of [DKK+16] gave a polynomial time algorithm for this task with optimal $\tilde{O}(\varepsilon)$ error using $n = \textrm{poly}(d, 1/\varepsilon)$ samples. On the other hand, [KS17b] introduced a general framework for robust moment estimation via a canonical sum-of-squares relaxation that succeeds for the more general class of certifiably subgaussian and certifiably hypercontractive [BK20] distributions. When specialized to Gaussians, this algorithm obtains the same $\tilde{O}(\varepsilon)$ error guarantee as [DKK+16] but incurs a super-polynomial sample complexity ($n = d^{O(\log(1/\varepsilon)}$) and running time ($n^{O(\log(1/\varepsilon))}$). This cost appears inherent to their analysis as it relies only on sum-of-squares certificates of upper bounds on directional moments while the analysis in [DKK+16] relies on lower bounds on directional moments inferred from algebraic relationships between moments of Gaussian distributions. We give a new, simple analysis of the same canonical sum-of-squares relaxation used in [KS17b, BK20] and show that for Gaussian distributions, their algorithm achieves the same error, sample complexity and running time guarantees as of the specialized algorithm in [DKK+16]. Our key innovation is a new argument that allows using moment lower bounds without having sum-of-squares certificates for them. We believe that our proof technique will likely be useful in developing further robust estimation algorithms.
Towards Using Clothes Style Transfer for Scenario-aware Person Video Generation
Venue: arXiv cs.CV 2021
Year: 2021

Clothes style transfer for person video generation is a challenging task, due to drastic variations of intra-person appearance and video scenarios. To tackle this problem, most recent AdaIN-based architectures are proposed to extract clothes and scenario features for generation. However, these approaches suffer from being short of fine-grained details and are prone to distort the origin person. To further improve the generation performance, we propose a novel framework with disentangled multi-branch encoders and a shared decoder. Moreover, to pursue the strong video spatio-temporal consistency, an inner-frame discriminator is delicately designed with input being cross-frame difference. Besides, the proposed framework possesses the property of scenario adaptation. Extensive experiments on the TEDXPeople benchmark demonstrate the superiority of our method over state-of-the-art approaches in terms of image quality and video coherence.