OpenRaiser/Intern-Atlas huggingface dataset:
Thermal (and Hybrid Thermal/Audio) Side-Channel Attacks on Keyboard Input
Venue: arXiv cs.CR 2022
Year: 2022

To date, there has been no systematic investigation of thermal profiles of keyboards, and thus no efforts have been made to secure them. This serves as our main motivation for constructing a means for password harvesting from keyboard thermal emanations. Specifically, we introduce Thermanator: a new post-factum insider attack based on heat transfer caused by a user typing a password on a typical external (plastic) keyboard. We conduct and describe a user study that collected thermal residues from 30 users entering 10 unique passwords (both weak and strong) on 4 popular commodity keyboards. Results show that entire sets of key-presses can be recovered by non-expert users as late as 30 seconds after initial password entry, while partial sets can be recovered as late as 1 minute after entry. However, the thermal residue side-channel lacks information about password length, duplicate key-presses, and key-press ordering. To overcome these limitations, we leverage keyboard acoustic emanations and combine the two to yield AcuTherm, the first hybrid side-channel attack on keyboards. AcuTherm significantly reduces password search without the need for any training on the victim's typing. We report results gathered for many representative passwords based on a user study involving 19 subjects. The takeaway of this work is three-fold: (1) using plastic keyboards to enter secrets (such as passwords and PINs) is even less secure than previously recognized, (2) post-factum thermal imaging attacks are realistic, and (3) hybrid (multiple side-channel) attacks are both realistic and effective.
On Neural Consolidation for Transfer in Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Although transfer learning is considered to be a milestone in deep reinforcement learning, the mechanisms behind it are still poorly understood. In particular, predicting if knowledge can be transferred between two given tasks is still an unresolved problem. In this work, we explore the use of network distillation as a feature extraction method to better understand the context in which transfer can occur. Notably, we show that distillation does not prevent knowledge transfer, including when transferring from multiple tasks to a new one, and we compare these results with transfer without prior distillation. We focus our work on the Atari benchmark due to the variability between different games, but also to their similarities in terms of visual features.
Cost Aware Asynchronous Multi-Agent Active Search
Venue: arXiv cs.LG 2022
Year: 2022

Multi-agent active search requires autonomous agents to choose sensing actions that efficiently locate targets. In a realistic setting, agents also must consider the costs that their decisions incur. Previously proposed active search algorithms simplify the problem by ignoring uncertainty in the agent's environment, using myopic decision making, and/or overlooking costs. In this paper, we introduce an online active search algorithm to detect targets in an unknown environment by making adaptive cost-aware decisions regarding the agent's actions. Our algorithm combines principles from Thompson Sampling (for search space exploration and decentralized multi-agent decision making), Monte Carlo Tree Search (for long horizon planning) and pareto-optimal confidence bounds (for multi-objective optimization in an unknown environment) to propose an online lookahead planner that removes all the simplifications. We analyze the algorithm's performance in simulation to show its efficacy in cost aware active search.
Covering Properties of Sum-Rank Metric Codes
Venue: arXiv cs.IT 2022
Year: 2022

The sum-rank metric can be seen as a generalization of both, the rank and the Hamming metric. It is well known that sum-rank metric codes outperform rank metric codes in terms of the required field size to construct maximum distance separable codes (i.e., the codes achieving the Singleton bound in the corresponding metric). In this work, we investigate the covering property of sum-rank metric codes to enrich the theory of sum-rank metric codes. We intend to answer the question: what is the minimum cardinality of a code given a sum-rank covering radius? We show the relations of this quantity between different metrics and provide several lower and upper bounds for sum-rank metric codes.
On Convexity in Split graphs: Complexity of Steiner tree and Domination
Venue: arXiv cs.CC 2022
Year: 2022

Given a graph $G$ with a terminal set $R \subseteq V(G)$, the Steiner tree problem (STREE) asks for a set $S\subseteq V(G) \setminus R$ such that the graph induced on $S\cup R$ is connected. A split graph is a graph which can be partitioned into a clique and an independent set. It is known that STREE is NP-complete on split graphs \cite{white1985steiner}. To strengthen this result, we introduce convex ordering on one of the partitions (clique or independent set), and prove that STREE is polynomial-time solvable for tree-convex split graphs with convexity on clique ($K$), whereas STREE is NP-complete on tree-convex split graphs with convexity on independent set ($I$). We further strengthen our NP-complete result by establishing a dichotomy which says that for unary-tree-convex split graphs (path-convex split graphs), STREE is polynomial-time solvable, and NP-complete for binary-tree-convex split graphs (comb-convex split graphs). We also show that STREE is polynomial-time solvable for triad-convex split graphs with convexity on $I$, and circular-convex split graphs. Further, we show that STREE can be used as a framework for the dominating set problem (DS) on split graphs, and hence the classical complexity (P vs NPC) of STREE and DS is the same for all these subclasses of split graphs. Furthermore, it is important to highlight that in \cite{CHLEBIK20081264}, it is incorrectly claimed that the problem of finding a minimum dominating set on split graphs cannot be approximated within $(1-ε)\ln |V(G)|$ in polynomial-time for any $ε>0$ unless NP $\subseteq$ DTIME $n^{O(\log \log n)}$. When the input is restricted to split graphs, we show that the minimum dominating set problem has $2-\frac{1}{|I|}$-approximation algorithm that runs in polynomial time.
A Liquid Democracy System for Human-Computer Societies
Venue: arXiv cs.MA 2022
Year: 2022

Problem of reliable democratic governance is critical for survival of any community, and it will be critical for communities powered with Artificial Intelligence (AI) systems upon developments of the latter. Apparently, it will be getting more and more critical because of increasing speeds and scales of electronic communications and decreasing latencies in system responses. In order to address this need, we present design and implementation of a reputation system supporting "liquid democracy" principle. The system is based on "weighted liquid rank" algorithm employing different sorts of explicit and implicit ratings being exchanged by members of the society as well as implicit assessments of of the members based on measures of their activity in the society. The system is evaluated against live social network data with help of simulation modelling for an online marketplace case.
Goal Recognition as a Deep Learning Task: the GRNet Approach
Venue: arXiv cs.AI 2022
Year: 2022

In automated planning, recognising the goal of an agent from a trace of observations is an important task with many applications. The state-of-the-art approaches to goal recognition rely on the application of planning techniques, which requires a model of the domain actions and of the initial domain state (written, e.g., in PDDL). We study an alternative approach where goal recognition is formulated as a classification task addressed by machine learning. Our approach, called GRNet, is primarily aimed at making goal recognition more accurate as well as faster by learning how to solve it in a given domain. Given a planning domain specified by a set of propositions and a set of action names, the goal classification instances in the domain are solved by a Recurrent Neural Network (RNN). A run of the RNN processes a trace of observed actions to compute how likely it is that each domain proposition is part of the agent's goal, for the problem instance under considerations. These predictions are then aggregated to choose one of the candidate goals. The only information required as input of the trained RNN is a trace of action labels, each one indicating just the name of an observed action. An experimental analysis confirms that \our achieves good performance in terms of both goal classification accuracy and runtime, obtaining better performance w.r.t. a state-of-the-art goal recognition system over the considered benchmarks.
Learning from aggregated data with a maximum entropy model
Venue: arXiv cs.LG 2022
Year: 2022

Aggregating a dataset, then injecting some noise, is a simple and common way to release differentially private data.However, aggregated data -- even without noise -- is not an appropriate input for machine learning classifiers.In this work, we show how a new model, similar to a logistic regression, may be learned from aggregated data only by approximating the unobserved feature distribution with a maximum entropy hypothesis. The resulting model is a Markov Random Field (MRF), and we detail how to apply, modify and scale a MRF training algorithm to our setting. Finally we present empirical evidence on several public datasets that the model learned this way can achieve performances comparable to those of a logistic model trained with the full unaggregated data.
Analyzing historical diagnosis code data from NIH N3C and RECOVER Programs using deep learning to determine risk factors for Long Covid
Venue: arXiv cs.LG 2022
Year: 2022

Post-acute sequelae of SARS-CoV-2 infection (PASC) or Long COVID is an emerging medical condition that has been observed in several patients with a positive diagnosis for COVID-19. Historical Electronic Health Records (EHR) like diagnosis codes, lab results and clinical notes have been analyzed using deep learning and have been used to predict future clinical events. In this paper, we propose an interpretable deep learning approach to analyze historical diagnosis code data from the National COVID Cohort Collective (N3C) to find the risk factors contributing to developing Long COVID. Using our deep learning approach, we are able to predict if a patient is suffering from Long COVID from a temporally ordered list of diagnosis codes up to 45 days post the first COVID positive test or diagnosis for each patient, with an accuracy of 70.48\%. We are then able to examine the trained model using Gradient-weighted Class Activation Mapping (GradCAM) to give each input diagnoses a score. The highest scored diagnosis were deemed to be the most important for making the correct prediction for a patient. We also propose a way to summarize these top diagnoses for each patient in our cohort and look at their temporal trends to determine which codes contribute towards a positive Long COVID diagnosis.
Designing Strategyproof Election Systems with Score Voting
Venue: arXiv cs.GT 2022
Year: 2022

We focus on the strategyproofness of voting systems where voters must choose a number of options among several possibilities. These systems include those that are used for Participatory Budgeting, where we organize an election to determine the allocation of a community's budget (city, region, etc.) dedicated to the financing of projects. We present a model for studying voting mechanisms and the Constrained Change Property (CCP), which will be used to design voting mechanisms that are always strategyproof. We also define a new notion of social choice function and use it to design a new class of utilitarian voting mechanisms that we call score voting. We prove that the mechanisms designed with core voting with a neutral score function are equivalent to knapsack voting on the same instance and that any score voting designed with a total score function is strategyproof if and only if its score function satisfies CCP. These results are combined to devise an algorithm that can find the closest total score function that makes any given score voting to be strategyproof.
Dual-Domain Cross-Iteration Squeeze-Excitation Network for Sparse Reconstruction of Brain MRI
Venue: arXiv cs.CV 2022
Year: 2022

Magnetic resonance imaging (MRI) is one of the most commonly applied tests in neurology and neurosurgery. However, the utility of MRI is largely limited by its long acquisition time, which might induce many problems including patient discomfort and motion artifacts. Acquiring fewer k-space sampling is a potential solution to reducing the total scanning time. However, it can lead to severe aliasing reconstruction artifacts and thus affect the clinical diagnosis. Nowadays, deep learning has provided new insights into the sparse reconstruction of MRI. In this paper, we present a new approach to this problem that iteratively fuses the information of k-space and MRI images using novel dual Squeeze-Excitation Networks and Cross-Iteration Residual Connections. This study included 720 clinical multi-coil brain MRI cases adopted from the open-source deidentified fastMRI Dataset. 8-folder downsampling rate was applied to generate the sparse k-space. Results showed that the average reconstruction error over 120 testing cases by our proposed method was 2.28%, which outperformed the existing image-domain prediction (6.03%, p<0.001), k-space synthesis (6.12%, p<0.001), and dual-domain feature fusion (4.05%, p<0.001).
Reading Chinese in Natural Scenes with a Bag-of-Radicals Prior
Venue: arXiv cs.CV 2022
Year: 2022

Scene text recognition (STR) on Latin datasets has been extensively studied in recent years, and state-of-the-art (SOTA) models often reach high accuracy. However, the performance on non-Latin transcripts, such as Chinese, is not satisfactory. In this paper, we collect six open-source Chinese STR datasets and evaluate a series of classic methods performing well on Latin datasets, finding a significant performance drop. To improve the performance on Chinese datasets, we propose a novel radical-embedding (RE) representation to utilize the ideographic descriptions of Chinese characters. The ideographic descriptions of Chinese characters are firstly converted to bags of radicals and then fused with learnable character embeddings by a character-vector-fusion-module (CVFM). In addition, we utilize a bag of radicals as supervision signals for multi-task training to improve the ideographic structure perception of our model. Experiments show performance of the model with RE + CVFM + multi-task training is superior compared with the baseline on six Chinese STR datasets. In addition, we utilize a bag of radicals as supervision signals for multi-task training to improve the ideographic structure perception of our model. Experiments show performance of the model with RE + CVFM + multi-task training is superior compared with the baseline on six Chinese STR datasets.
A Closer Look at Robustness to L-infinity and Spatial Perturbations and their Composition
Venue: arXiv cs.LG 2022
Year: 2022

In adversarial machine learning, the popular $\ell_\infty$ threat model has been the focus of much previous work. While this mathematical definition of imperceptibility successfully captures an infinite set of additive image transformations that a model should be robust to, this is only a subset of all transformations which leave the semantic label of an image unchanged. Indeed, previous work also considered robustness to spatial attacks as well as other semantic transformations; however, designing defense methods against the composition of spatial and $\ell_{\infty}$ perturbations remains relatively underexplored. In the following, we improve the understanding of this seldom investigated compositional setting. We prove theoretically that no linear classifier can achieve more than trivial accuracy against a composite adversary in a simple statistical setting, illustrating its difficulty. We then investigate how state-of-the-art $\ell_{\infty}$ defenses can be adapted to this novel threat model and study their performance against compositional attacks. We find that our newly proposed TRADES$_{\text{All}}$ strategy performs the strongest of all. Analyzing its logit's Lipschitz constant for RT transformations of different sizes, we find that TRADES$_{\text{All}}$ remains stable over a wide range of RT transformations with and without $\ell_\infty$ perturbations.
AOE-Net: Entities Interactions Modeling with Adaptive Attention Mechanism for Temporal Action Proposals Generation
Venue: arXiv cs.CV 2022
Year: 2022

Temporal action proposal generation (TAPG) is a challenging task, which requires localizing action intervals in an untrimmed video. Intuitively, we as humans, perceive an action through the interactions between actors, relevant objects, and the surrounding environment. Despite the significant progress of TAPG, a vast majority of existing methods ignore the aforementioned principle of the human perceiving process by applying a backbone network into a given video as a black-box. In this paper, we propose to model these interactions with a multi-modal representation network, namely, Actors-Objects-Environment Interaction Network (AOE-Net). Our AOE-Net consists of two modules, i.e., perception-based multi-modal representation (PMR) and boundary-matching module (BMM). Additionally, we introduce adaptive attention mechanism (AAM) in PMR to focus only on main actors (or relevant objects) and model the relationships among them. PMR module represents each video snippet by a visual-linguistic feature, in which main actors and surrounding environment are represented by visual information, whereas relevant objects are depicted by linguistic features through an image-text model. BMM module processes the sequence of visual-linguistic features as its input and generates action proposals. Comprehensive experiments and extensive ablation studies on ActivityNet-1.3 and THUMOS-14 datasets show that our proposed AOE-Net outperforms previous state-of-the-art methods with remarkable performance and generalization for both TAPG and temporal action detection. To prove the robustness and effectiveness of AOE-Net, we further conduct an ablation study on egocentric videos, i.e. EPIC-KITCHENS 100 dataset. Source code is available upon acceptance.
Star-Graph Multimodal Matching Component Analysis for Data Fusion and Transfer Learning
Venue: arXiv cs.LG 2022
Year: 2022

Previous matching component analysis (MCA) techniques map two data domains to a common domain for further processing in data fusion and transfer learning contexts. In this paper, we extend these techniques to the star-graph multimodal (SGM) case in which one particular data domain is connected to $m$ others via an objective function. We provide a particular feasible point for the resulting trace maximization problem in closed form and algorithms for its computation and iterative improvement, leading to our main result, the SGM maps. We also provide numerical examples demonstrating that SGM is capable of encoding into its maps more information than MCA when few training points are available. In addition, we develop a further generalization of the MCA covariance constraint, eliminating a previous feasibility condition and allowing larger values of the rank of the prescribed covariance matrix.
$(1-ε)$-approximate fully dynamic densest subgraph: linear space and faster update time
Venue: arXiv cs.DS 2022
Year: 2022

We consider the problem of maintaining a $(1-ε)$-approximation to the densest subgraph (DSG) in an undirected multigraph as it undergoes edge insertions and deletions (the fully dynamic setting). Sawlani and Wang [SW20] developed a data structure that, for any given $ε> 0$, maintains a $(1-ε)$-approximation with $O(\log^4 n/ε^6)$ worst-case update time for edge operations, and $O(1)$ query time for reporting the density value. Their data structure was the first to achieve near-optimal approximation, and improved previous work that maintained a $(1/4 - ε)$ approximation in amortized polylogarithmic update time [BHNT15]. In this paper we develop a data structure for $(1-ε)$-approximate DSG that improves the one from [SW20] in two aspects. First, the data structure uses linear space improving the space bound in [SW20] by a logarithmic factor. Second, the data structure maintains a $(1-ε)$-approximation in amortized $O(\log^2 n/ε^4)$ time per update while simultaneously guaranteeing that the worst case update time is $O(\log^3 n \log \log n/ε^6)$. We believe that the space and update time improvements are valuable for current large scale graph data sets. The data structure extends in a natural fashion to hypergraphs and yields improvements in space and update times over recent work [BBCG22] that builds upon [SW20].
TensorAnalyzer: Identification of Urban Patterns in Big Cities using Non-Negative Tensor Factorization
Venue: arXiv cs.LG 2022
Year: 2022

Extracting relevant urban patterns from multiple data sources can be difficult using classical clustering algorithms since we have to make a suitable setup of the hyperparameters of the algorithms and deal with outliers. It should be addressed correctly to help urban planners in the decision-making process for the further development of a big city. For instance, experts' main interest in criminology is comprehending the relationship between crimes and the socio-economic characteristics at specific georeferenced locations. In addition, the classical clustering algorithms take little notice of the intricate spatial correlations in georeferenced data sources. This paper presents a new approach to detecting the most relevant urban patterns from multiple data sources based on tensor decomposition. Compared to classical methods, the proposed approach's performance is attested to validate the identified patterns' quality. The result indicates that the approach can effectively identify functional patterns to characterize the data set for further analysis in achieving good clustering quality. Furthermore, we developed a generic framework named TensorAnalyzer, where the effectiveness and usefulness of the proposed methodology are tested by a set of experiments and a real-world case study showing the relationship between the crime events around schools and students performance and other variables involved in the analysis.
Feasibility on Detecting Door Slamming towards Monitoring Early Signs of Domestic Violence
Venue: arXiv cs.SD 2022
Year: 2022

By using low-cost microcontrollers and TinyML, we investigate the feasibility of detecting potential early warning signs of domestic violence and other anti-social behaviors within the home. We created a machine learning model to determine if a door was closed aggressively by analyzing audio data and feeding this into a convolutional neural network to classify the sample. Under test conditions, with no background noise, accuracy of 88.89\% was achieved, declining to 87.50\% when assorted background noises were mixed in at a relative volume of 0.5 times that of the sample. The model is then deployed on an Arduino Nano BLE 33 Sense attached to the door, and only begins sampling once an acceleration greater than a predefined threshold acceleration is detected. The predictions made by the model can then be sent via BLE to another device, such as a smartphone of Raspberry Pi.