OpenRaiser/Intern-Atlas huggingface dataset:
Spinner: Automated Dynamic Command Subsystem Perturbation
Venue: arXiv cs.CR 2021
Year: 2021

Injection attacks have been a major threat to web applications. Despite the significant effort in thwarting injection attacks, protection against injection attacks remains challenging due to the sophisticated attacks that exploit the existing protection techniques' design and implementation flaws. In this paper, we develop Spinner, a system that provides general protection against input injection attacks, including OS/shell command, SQL, and XXE injection. Instead of focusing on detecting malicious inputs, Spinner constantly randomizes underlying subsystems so that injected inputs (e.g., commands or SQL queries) that are not properly randomized will not be executed, hence prevented. We revisit the design and implementation choices of previous randomization-based techniques and develop a more robust and practical protection against various sophisticated input injection attacks. To handle complex real-world applications, we develop a bidirectional analysis that combines forward and backward static analysis techniques to identify intended commands or SQL queries to ensure the correct execution of the randomized target program. We implement Spinner for the shell command processor and two different database engines (MySQL and SQLite) and in diverse programming languages including C/C++, PHP, JavaScript and Lua. Our evaluation results on 42 real-world applications including 27 vulnerable ones show that it effectively prevents a variety of input injection attacks with low runtime overhead (around 5%).
Winning Sets of Regular Languages: Descriptional and Computational Complexity
Venue: arXiv cs.FL 2021
Year: 2021

We investigate certain word-construction games with variable turn orders. In these games, Alice and Bob take turns on choosing consecutive letters of a word of fixed length, with Alice winning if the result lies in a predetermined target language. The turn orders that result in a win for Alice form a binary language that is regular whenever the target language is, and we prove some upper and lower bounds for its state complexity based on that of the target language. We also consider the computational complexity of membership and intersection problems of winning sets.
Analysis of Machine Learning Approaches to Packing Detection
Venue: arXiv cs.CR 2021
Year: 2021

Packing is an obfuscation technique widely used by malware to hide the content and behavior of a program. Much prior research has explored how to detect whether a program is packed. This research includes a broad variety of approaches such as entropy analysis, syntactic signatures and more recently machine learning classifiers using various features. However, no robust results have indicated which algorithms perform best, or which features are most significant. This is complicated by considering how to evaluate the results since accuracy, cost, generalization capabilities, and other measures are all reasonable. This work explores eleven different machine learning approaches using 119 features to understand: which features are most significant for packing detection; which algorithms offer the best performance; and which algorithms are most economical.
Residual Enhanced Multi-Hypergraph Neural Network
Venue: arXiv cs.CV 2021
Year: 2021

Hypergraphs are a generalized data structure of graphs to model higher-order correlations among entities, which have been successfully adopted into various research domains. Meanwhile, HyperGraph Neural Network (HGNN) is currently the de-facto method for hypergraph representation learning. However, HGNN aims at single hypergraph learning and uses a pre-concatenation approach when confronting multi-modal datasets, which leads to sub-optimal exploitation of the inter-correlations of multi-modal hypergraphs. HGNN also suffers the over-smoothing issue, that is, its performance drops significantly when layers are stacked up. To resolve these issues, we propose the Residual enhanced Multi-Hypergraph Neural Network, which can not only fuse multi-modal information from each hypergraph effectively, but also circumvent the over-smoothing issue associated with HGNN. We conduct experiments on two 3D benchmarks, the NTU and the ModelNet40 datasets, and compare against multiple state-of-the-art methods. Experimental results demonstrate that both the residual hypergraph convolutions and the multi-fusion architecture can improve the performance of the base model and the combined model achieves a new state-of-the-art. Code is available at \url{https://github.com/OneForward/ResMHGNN}.
Curious Exploration and Return-based Memory Restoration for Deep Reinforcement Learning
Venue: arXiv cs.RO 2021
Year: 2021

Reward engineering and designing an incentive reward function are non-trivial tasks to train agents in complex environments. Furthermore, an inaccurate reward function may lead to a biased behaviour which is far from an efficient and optimised behaviour. In this paper, we focus on training a single agent to score goals with binary success/failure reward function in Half Field Offense domain. As the major advantage of this research, the agent has no presumption about the environment which means it only follows the original formulation of reinforcement learning agents. The main challenge of using such a reward function is the high sparsity of positive reward signals. To address this problem, we use a simple prediction-based exploration strategy (called Curious Exploration) along with a Return-based Memory Restoration (RMR) technique which tends to remember more valuable memories. The proposed method can be utilized to train agents in environments with fairly complex state and action spaces. Our experimental results show that many recent solutions including our baseline method fail to learn and perform in complex soccer domain. However, the proposed method can converge easily to the nearly optimal behaviour. The video presenting the performance of our trained agent is available at http://bit.ly/HFO_Binary_Reward.
Universal scaling laws in the gradient descent training of neural networks
Venue: arXiv cs.LG 2021
Year: 2021

Current theoretical results on optimization trajectories of neural networks trained by gradient descent typically have the form of rigorous but potentially loose bounds on the loss values. In the present work we take a different approach and show that the learning trajectory can be characterized by an explicit asymptotic at large training times. Specifically, the leading term in the asymptotic expansion of the loss behaves as a power law $L(t) \sim t^{-ξ}$ with exponent $ξ$ expressed only through the data dimension, the smoothness of the activation function, and the class of function being approximated. Our results are based on spectral analysis of the integral operator representing the linearized evolution of a large network trained on the expected loss. Importantly, the techniques we employ do not require specific form of a data distribution, for example Gaussian, thus making our findings sufficiently universal.
CDR Based Trajectories: Tentative for Filtering Ping-pong Handover
Venue: arXiv cs.CV 2021
Year: 2021

Call Detail Records (CDRs) coupled with the coverage area locations provide the operator with an incredible amount of information on its customers' whereabouts and movement. Due to the non-static and overlapping nature of the antenna coverage area there commonly exist situations where cellphones geographically close to each other can be connected to different antennas due to handover rule - the operator hands over a certain cellphone to another antenna to spread the load between antennas. Hence, this aspect introduces a ping-pong handover phenomena in the trajectories extracted from the CDR data which can be misleading in understanding the mobility pattern. To reconstruct accurate trajectories it is a must to reduce the number of those handovers appearing in the dataset. This letter presents a novel approach for filtering ping-pong handovers from CDR based trajectories. Primarily, the approach is based on anchors model utilizing different features and parameters extracted from the coverage areas and reconstructed trajectories mined from the CDR data. Using this methodology we can significantly reduce the ping-pong handover noise in the trajectories, which gives a more accurate reconstruction of the customers' movement pattern.
Adapting CRISP-DM for Idea Mining: A Data Mining Process for Generating Ideas Using a Textual Dataset
Venue: arXiv cs.IR 2021
Year: 2021

Data mining project managers can benefit from using standard data mining process models. The benefits of using standard process models for data mining, such as the de facto and the most popular, Cross-Industry-Standard-Process model for Data Mining (CRISP-DM) are reduced cost and time. Also, standard models facilitate knowledge transfer, reuse of best practices, and minimize knowledge requirements. On the other hand, to unlock the potential of ever-growing textual data such as publications, patents, social media data, and documents of various forms, digital innovation is increasingly needed. Furthermore, the introduction of cutting-edge machine learning tools and techniques enable the elicitation of ideas. The processing of unstructured textual data to generate new and useful ideas is referred to as idea mining. Existing literature about idea mining merely overlooks the utilization of standard data mining process models. Therefore, the purpose of this paper is to propose a reusable model to generate ideas, CRISP-DM, for Idea Mining (CRISP-IM). The design and development of the CRISP-IM are done following the design science approach. The CRISP-IM facilitates idea generation, through the use of Dynamic Topic Modeling (DTM), unsupervised machine learning, and subsequent statistical analysis on a dataset of scholarly articles. The adapted CRISP-IM can be used to guide the process of identifying trends using scholarly literature datasets or temporally organized patent or any other textual dataset of any domain to elicit ideas. The ex-post evaluation of the CRISP-IM is left for future study.
Consistency and Monotonicity Regularization for Neural Knowledge Tracing
Venue: arXiv cs.LG 2021
Year: 2021

Knowledge Tracing (KT), tracking a human's knowledge acquisition, is a central component in online learning and AI in Education. In this paper, we present a simple, yet effective strategy to improve the generalization ability of KT models: we propose three types of novel data augmentation, coined replacement, insertion, and deletion, along with corresponding regularization losses that impose certain consistency or monotonicity biases on the model's predictions for the original and augmented sequence. Extensive experiments on various KT benchmarks show that our regularization scheme consistently improves the model performances, under 3 widely-used neural networks and 4 public benchmarks, e.g., it yields 6.3% improvement in AUC under the DKT model and the ASSISTmentsChall dataset.
A 3D Advancing-Front Delaunay Mesh Refinement Algorithm
Venue: arXiv cs.CG 2021
Year: 2021

I present a 3D advancing-front mesh refinement algorithm that generates a constrained Delaunay mesh for any piecewise linear complex (PLC) and extend this algorithm to produce truly Delaunay meshes for any PLC. First, as in my recently published 2D algorithm, I split the input line segments such that the length of the subsegments is asymptotically proportional to the local feature size (LFS). For each facet, I refine the mesh such that the edge lengths and the radius of the circumcircle of every triangular element are asymptotically proportional to the LFS. Finally, I refine the volume mesh to produce a constrained Delaunay mesh whose tetrahedral elements are well graded and have a radius-edge ratio less than some $ω^* > 2/\sqrt{3}$ (except ``near'' small input angles). I extend this algorithm to generate truly Delaunay meshes by ensuring that every triangular element on a facet satisfies Gabriel's condition, i.e., its diametral sphere is empty. On an ``apex'' vertex where multiple facets intersect, Gabriel's condition is satisfied by a modified split-on-a-sphere (SOS) technique. On a line where multiple facets intersect, Gabriel's condition is satisfied by mirroring meshes near the line of intersection. The SOS technique ensures that the triangles on a facet near the apex vertex have angles that are proportional to the angular feature size (AFS), a term I define in the paper. All tetrahedra (except ``near'' small input angles) are well graded and have a radius-edge ratio less than $ω^* > \sqrt{2}$ for a truly Delaunay mesh. The upper bounds for the radius-edge ratio are an improvement by a factor of $\sqrt{2}$ over current state-of-the-art algorithms.
S3Net: A Single Stream Structure for Depth Guided Image Relighting
Venue: arXiv cs.CV 2021
Year: 2021

Depth guided any-to-any image relighting aims to generate a relit image from the original image and corresponding depth maps to match the illumination setting of the given guided image and its depth map. To the best of our knowledge, this task is a new challenge that has not been addressed in the previous literature. To address this issue, we propose a deep learning-based neural Single Stream Structure network called S3Net for depth guided image relighting. This network is an encoder-decoder model. We concatenate all images and corresponding depth maps as the input and feed them into the model. The decoder part contains the attention module and the enhanced module to focus on the relighting-related regions in the guided images. Experiments performed on challenging benchmark show that the proposed model achieves the 3 rd highest SSIM in the NTIRE 2021 Depth Guided Any-to-any Relighting Challenge.
APEX: A High-Performance Learned Index on Persistent Memory
Venue: arXiv cs.DB 2021
Year: 2021

The recently released persistent memory (PM) offers high performance, persistence, and is cheaper than DRAM. This opens up new possibilities for indexes that operate and persist data directly on the memory bus. Recent learned indexes exploit data distribution and have shown great potential for some workloads. However, none support persistence or instant recovery, and existing PM-based indexes typically evolve B+-trees without considering learned indexes. This paper proposes APEX, a new PM-optimized learned index that offers high performance, persistence, concurrency, and instant recovery. APEX is based on ALEX, a state-of-the-art updatable learned index, to combine and adapt the best of past PM optimizations and learned indexes, allowing it to reduce PM accesses while still exploiting machine learning. Our evaluation on Intel DCPMM shows that APEX can perform up to ~15x better than existing PM indexes and can recover from failures in ~42ms.
Graph Learning: A Survey
Venue: arXiv cs.LG 2021
Year: 2021

Graphs are widely used as a popular representation of the network structure of connected data. Graph data can be found in a broad spectrum of application domains such as social systems, ecosystems, biological networks, knowledge graphs, and information systems. With the continuous penetration of artificial intelligence technologies, graph learning (i.e., machine learning on graphs) is gaining attention from both researchers and practitioners. Graph learning proves effective for many tasks, such as classification, link prediction, and matching. Generally, graph learning methods extract relevant features of graphs by taking advantage of machine learning algorithms. In this survey, we present a comprehensive overview on the state-of-the-art of graph learning. Special attention is paid to four categories of existing graph learning methods, including graph signal processing, matrix factorization, random walk, and deep learning. Major models and algorithms under these categories are reviewed respectively. We examine graph learning applications in areas such as text, images, science, knowledge graphs, and combinatorial optimization. In addition, we discuss several promising research directions in this field.
Turing Number: How Far Are You to A. M. Turing Award?
Venue: arXiv cs.SI 2021
Year: 2021

The ACM A.M. Turing Award is commonly acknowledged as the highest distinction in the realm of computer science. Since 1960s, it has been awarded to computer scientists who made outstanding contributions. The significance of this award is far-reaching to the laureates as well as their research teams. However, unlike the Nobel Prize that has been extensively investigated, little research has been done to explore this most important award. To this end, we propose the Turing Number (TN) index to measure how far a specific scholar is to this award. Inspired by previous works on Erdos Number and Bacon Number, this index is defined as the shortest path between a given scholar to any Turing Award Laureate. Experimental results suggest that TN can reflect the closeness of collaboration between scholars and Turing Award Laureates. With the correlation analysis between TN and metrics from the bibliometric-level and network-level, we demonstrate that TN has the potential of reflecting a scholar's academic influence and reputation.
Characterization of Secure Multiparty Computation Without Broadcast
Venue: arXiv cs.CR 2021
Year: 2021

A major challenge in the study of cryptography is characterizing the necessary and sufficient assumptions required to carry out a given cryptographic task. The focus of this work is the necessity of a broadcast channel for securely computing symmetric functionalities (where all the parties receive the same output) when one third of the parties, or more, might be corrupted. Assuming all parties are connected via a peer-to-peer network, but no broadcast channel (nor a secure setup phase) is available, we prove the following characterization: 1) A symmetric $n$-party functionality can be securely computed facing $n/3\le t<n/2$ corruptions (\ie honest majority), if and only if it is \emph{$(n-2t)$-dominated}; a functionality is $k$-dominated, if \emph{any} $k$-size subset of its input variables can be set to \emph{determine} its output. 2) Assuming the existence of one-way functions, a symmetric $n$-party functionality can be securely computed facing $t\ge n/2$ corruptions (\ie no honest majority), if and only if it is $1$-dominated and can be securely computed with broadcast. It follows that, in case a third of the parties might be corrupted, broadcast is necessary for securely computing non-dominated functionalities (in which "small" subsets of the inputs cannot determine the output), including, as interesting special cases, the Boolean XOR and coin-flipping functionalities.
The Matter of Chance: Auditing Web Search Results Related to the 2020 U.S. Presidential Primary Elections Across Six Search Engines
Venue: arXiv cs.CY 2021
Year: 2021

We examine how six search engines filter and rank information in relation to the queries on the U.S. 2020 presidential primary elections under the default - that is nonpersonalized - conditions. For that, we utilize an algorithmic auditing methodology that uses virtual agents to conduct large-scale analysis of algorithmic information curation in a controlled environment. Specifically, we look at the text search results for "us elections", "donald trump", "joe biden" and "bernie sanders" queries on Google, Baidu, Bing, DuckDuckGo, Yahoo, and Yandex, during the 2020 primaries. Our findings indicate substantial differences in the search results between search engines and multiple discrepancies within the results generated for different agents using the same search engine. It highlights that whether users see certain information is decided by chance due to the inherent randomization of search results. We also find that some search engines prioritize different categories of information sources with respect to specific candidates. These observations demonstrate that algorithmic curation of political information can create information inequalities between the search engine users even under nonpersonalized conditions. Such inequalities are particularly troubling considering that search results are highly trusted by the public and can shift the opinions of undecided voters as demonstrated by previous research.
Pattern Complexity of Aperiodic Substitutive Subshifts
Venue: arXiv cs.DM 2021
Year: 2021

This paper aims to better understand the link better understand the links between aperiodicity in subshifts and pattern complexity. Our main contribution deals with substitutive subshifts, an equivalent to substitutive tilings in the context of symbolic dynamics. For a class of substitutive subshifts, we prove a quadratic lower bound on their pattern complexity. Together with an already known upper bound, this shows that this class of substitutive subshifts has a pattern complexity in $Θ(n^2)$. We also prove that the recent bound of Kari and Moutot, showing that any aperiodic subshift has pattern complexity at least $mn+1$, is optimal for fixed $m$ and $n$.
LACLICHEV: Exploring the History of Climate Change in Latin America within Newspapers Digital Collections
Venue: arXiv cs.DL 2021
Year: 2021

This paper introduces LACLICHEV (Latin American Climate Change Evolution platform ), a data collections exploration environment for exploring historical newspapers searching for articles reporting meteorological events. LACLICHEV is based on data collections' exploration techniques combined with information retrieval, data analytics, and geographic querying and visualization. This environment provides tools for curating, exploring and analyzing historical newspapers articles, their description and location, and the vocabularies used for referring to meteorological events. The objective being to understand the content of newspapers and identifying possible patterns and models that can build a view of the history of climate change in the Latin American region.
Switching Contexts: Transportability Measures for NLP
Venue: arXiv cs.CL 2021
Year: 2021

This paper explores the topic of transportability, as a sub-area of generalisability. By proposing the utilisation of metrics based on well-established statistics, we are able to estimate the change in performance of NLP models in new contexts. Defining a new measure for transportability may allow for better estimation of NLP system performance in new domains, and is crucial when assessing the performance of NLP systems in new tasks and domains. Through several instances of increasing complexity, we demonstrate how lightweight domain similarity measures can be used as estimators for the transportability in NLP applications. The proposed transportability measures are evaluated in the context of Named Entity Recognition and Natural Language Inference tasks.
La evaluacion de la investigacion: Espana suspende
Venue: arXiv cs.DL 2021
Year: 2021

The research assessments of countries or institutions should reveal their contribution to the advancement of science. Taking into consideration the correlation that exists between scientific impact and number of citations, research assessments can be based on citation counts. However, it is crucial to perform the counts in the heavy tail of citation distributions. Following this heavy tail approach, all measurements performed in Spanish universities show that their research is inefficient because the proportion of highly cited papers is much lower than in the most scientifically advanced countries. The same conclusion is reached when considering the number of researchers in the Ioannidis, Boyack, and Baas lists of highly cited researchers.