OpenRaiser/Intern-Atlas huggingface dataset:
ROPNN: Detection of ROP Payloads Using Deep Neural Networks
Venue: arXiv cs.CR 2024
Year: 2024

Return-oriented programming (ROP) is a code reuse attack that chains short snippets of existing code to perform arbitrary operations on target machines. Existing detection methods against ROP exhibit unsatisfactory detection accuracy and/or have high runtime overhead. In this paper, we present ROPNN, which innovatively combines address space layout guided disassembly and deep neural networks to detect ROP payloads. The disassembler treats application input data as code pointers and aims to find any potential gadget chains, which are then classified by a deep neural network as benign or malicious. Our experiments show that ROPNN has high detection rate (99.3%) and a very low false positive rate (0.01%). ROPNN successfully detects all of the 100 real-world ROP exploits that are collected in-the-wild, created manually or created by ROP exploit generation tools. Additionally, ROPNN detects all 10 ROP exploits that can bypass Bin-CFI. ROPNN is non-intrusive and does not incur any runtime overhead to the protected program.
Private Information Retrieval from Locally Repairable Databases with Colluding Servers
Venue: arXiv cs.IT 2024
Year: 2024

We consider information-theoretical private information retrieval (PIR) from a coded database with colluding servers. We target, for the first time, locally repairable storage codes (LRCs). We consider any number of local groups $ g $, locality $ r $, local distance $ δ$ and dimension $ k $. Our main contribution is a PIR scheme for maximally recoverable (MR) LRCs based on linearized Reed--Solomon codes, which achieve the smallest field sizes among MR-LRCs for many parameter regimes. In our scheme, nodes are identified with codeword symbols and servers are identified with local groups of nodes. Only locally non-redundant information is downloaded from each server, that is, only $ r $ nodes (out of $ r+δ-1 $) are downloaded per server. The PIR scheme achieves the (download) rate $ R = (N - k - rt + 1)/N $, where $ N = gr $ is the length of the MDS code obtained after removing the local parities, and for any $ t $ colluding servers such that $ k + rt \leq N $. For an unbounded number of stored files, the obtained rate is strictly larger than those of known PIR schemes that work for any MDS code. Finally, the obtained PIR scheme can also be adapted when communication between the user and each server is performed via linear network coding, achieving the same rate as previous PIR schemes for this scenario but with polynomial finite field sizes, instead of exponential. Our rates are equal to those of PIR schemes for Reed--Solomon codes, but Reed--Solomon codes are incompatible with the MR-LRC property or linear network coding, thus our PIR scheme is less restrictive in its applications.
Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
Venue: arXiv cs.LG 2024
Year: 2024

We study the training process of Deep Neural Networks (DNNs) from the Fourier analysis perspective. We demonstrate a very universal Frequency Principle (F-Principle) -- DNNs often fit target functions from low to high frequencies -- on high-dimensional benchmark datasets such as MNIST/CIFAR10 and deep neural networks such as VGG16. This F-Principle of DNNs is opposite to the behavior of most conventional iterative numerical schemes (e.g., Jacobi method), which exhibit faster convergence for higher frequencies for various scientific computing problems. With a simple theory, we illustrate that this F-Principle results from the regularity of the commonly used activation functions. The F-Principle implies an implicit bias that DNNs tend to fit training data by a low-frequency function. This understanding provides an explanation of good generalization of DNNs on most real datasets and bad generalization of DNNs on parity function or randomized dataset.
Contextual Encoder-Decoder Network for Visual Saliency Prediction
Venue: arXiv cs.CV 2024
Year: 2024

Predicting salient regions in natural images requires the detection of objects that are present in a scene. To develop robust representations for this challenging task, high-level visual features at multiple spatial scales must be extracted and augmented with contextual information. However, existing models aimed at explaining human fixation maps do not incorporate such a mechanism explicitly. Here we propose an approach based on a convolutional neural network pre-trained on a large-scale image classification task. The architecture forms an encoder-decoder structure and includes a module with multiple convolutional layers at different dilation rates to capture multi-scale features in parallel. Moreover, we combine the resulting representations with global scene information for accurately predicting visual saliency. Our model achieves competitive and consistent results across multiple evaluation metrics on two public saliency benchmarks and we demonstrate the effectiveness of the suggested approach on five datasets and selected examples. Compared to state of the art approaches, the network is based on a lightweight image classification backbone and hence presents a suitable choice for applications with limited computational resources, such as (virtual) robotic systems, to estimate human fixations across complex natural scenes.
Parsing Gigabytes of JSON per Second
Venue: arXiv cs.DB 2024
Year: 2024

JavaScript Object Notation or JSON is a ubiquitous data exchange format on the Web. Ingesting JSON documents can become a performance bottleneck due to the sheer volume of data. We are thus motivated to make JSON parsing as fast as possible. Despite the maturity of the problem of JSON parsing, we show that substantial speedups are possible. We present the first standard-compliant JSON parser to process gigabytes of data per second on a single core, using commodity processors. We can use a quarter or fewer instructions than a state-of-the-art reference parser like RapidJSON. Unlike other validating parsers, our software (simdjson) makes extensive use of Single Instruction, Multiple Data (SIMD) instructions. To ensure reproducibility, simdjson is freely available as open-source software under a liberal license.
Fake News, Disinformation, and Deepfakes: Leveraging Distributed Ledger Technologies and Blockchain to Combat Digital Deception and Counterfeit Reality
Venue: arXiv cs.CY 2024
Year: 2024

The rise of ubiquitous deepfakes, misinformation, disinformation, propaganda and post-truth, often referred to as fake news, raises concerns over the role of Internet and social media in modern democratic societies. Due to its rapid and widespread diffusion, digital deception has not only an individual or societal cost (e.g., to hamper the integrity of elections), but it can lead to significant economic losses (e.g., to affect stock market performance) or to risks to national security. Blockchain and other Distributed Ledger Technologies (DLTs) guarantee the provenance, authenticity and traceability of data by providing a transparent, immutable and verifiable record of transactions while creating a peer-to-peer secure platform for storing and exchanging information. This overview aims to explore the potential of DLTs and blockchain to combat digital deception, reviewing initiatives that are currently under development and identifying their main current challenges. Moreover, some recommendations are enumerated to guide future researchers on issues that will have to be tackled to face fake news, disinformation and deepfakes, as an integral part of strengthening the resilience against cyber-threats on today's online media.
Introduction to Multi-Armed Bandits
Venue: arXiv cs.LG 2024
Year: 2024

Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a particular line of work, providing a self-contained, teachable technical introduction and a brief review of the further developments; many of the chapters conclude with exercises. The book is structured as follows. The first four chapters are on IID rewards, from the basic model to impossibility results to Bayesian priors to Lipschitz rewards. The next three chapters cover adversarial rewards, from the full-feedback version to adversarial bandits to extensions with linear rewards and combinatorially structured actions. Chapter 8 is on contextual bandits, a middle ground between IID and adversarial bandits in which the change in reward distributions is completely explained by observable contexts. The last three chapters cover connections to economics, from learning in repeated games to bandits with supply/budget constraints to exploration in the presence of incentives. The appendix provides sufficient background on concentration and KL-divergence. The chapters on "bandits with similarity information", "bandits with knapsacks" and "bandits and agents" can also be consumed as standalone surveys on the respective topics.
Composing dynamic programming tree-decomposition-based algorithms
Venue: arXiv cs.DS 2024
Year: 2024

Given two integers $\ell$ and $p$ as well as $\ell$ graph classes $\mathcal{H}_1,\ldots,\mathcal{H}_\ell$, the problems $\mathsf{GraphPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell,p)$, \break $\mathsf{VertPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell)$, and $\mathsf{EdgePart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell)$ ask, given graph $G$ as input, whether $V(G)$, $V(G)$, $E(G)$ respectively can be partitioned into $\ell$ sets $S_1, \ldots, S_\ell$ such that, for each $i$ between $1$ and $\ell$, $G[S_i] \in \mathcal{H}_i$, $G[S_i] \in \mathcal{H}_i$, $(V(G),S_i) \in \mathcal{H}_i$ respectively. Moreover in $\mathsf{GraphPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell,p)$, we request that the number of edges with endpoints in different sets of the partition is bounded by $p$. We show that if there exist dynamic programming tree-decomposition-based algorithms for recognizing the graph classes $\mathcal{H}_i$, for each $i$, then we can constructively create a dynamic programming tree-decomposition-based algorithms for $\mathsf{GraphPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell,p)$, $\mathsf{VertPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell)$, and $\mathsf{EdgePart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell)$. We apply this approach to known problems. For well-studied problems, like VERTEX COVER and GRAPH $q$-COLORING, we obtain running times that are comparable to those of the best known problem-specific algorithms. For an exotic problem from bioinformatics, called DISPLAYGRAPH, this approach improves the known algorithm parameterized by treewidth.
Exact Hard Monotonic Attention for Character-Level Transduction
Venue: arXiv cs.CL 2024
Year: 2024

Many common character-level, string-to string transduction tasks, e.g., grapheme-tophoneme conversion and morphological inflection, consist almost exclusively of monotonic transductions. However, neural sequence-to sequence models that use non-monotonic soft attention often outperform popular monotonic models. In this work, we ask the following question: Is monotonicity really a helpful inductive bias for these tasks? We develop a hard attention sequence-to-sequence model that enforces strict monotonicity and learns a latent alignment jointly while learning to transduce. With the help of dynamic programming, we are able to compute the exact marginalization over all monotonic alignments. Our models achieve state-of-the-art performance on morphological inflection. Furthermore, we find strong performance on two other character-level transduction tasks. Code is available at https://github.com/shijie-wu/neural-transducer.
Domain Adaptive Attention Learning for Unsupervised Person Re-Identification
Venue: arXiv cs.CV 2024
Year: 2024

Person re-identification (Re-ID) across multiple datasets is a challenging task due to two main reasons: the presence of large cross-dataset distinctions and the absence of annotated target instances. To address these two issues, this paper proposes a domain adaptive attention learning approach to reliably transfer discriminative representation from the labeled source domain to the unlabeled target domain. In this approach, a domain adaptive attention model is learned to separate the feature map into domain-shared part and domain-specific part. In this manner, the domain-shared part is used to capture transferable cues that can compensate cross-dataset distinctions and give positive contributions to the target task, while the domain-specific part aims to model the noisy information to avoid the negative transfer caused by domain diversity. A soft label loss is further employed to take full use of unlabeled target data by estimating pseudo labels. Extensive experiments on the Market-1501, DukeMTMC-reID and MSMT17 benchmarks demonstrate the proposed approach outperforms the state-of-the-arts.
Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
Venue: arXiv cs.FL 2024
Year: 2024

We introduce a novel technique to analyse unambiguous Büchi automata quantitatively, and apply this to the model checking problem. It is based on linear-algebra arguments that originate from the analysis of matrix semigroups with constant spectral radius. This method can replace a combinatorial procedure that dominates the computational complexity of the existing procedure by Baier et al. We analyse the complexity in detail, showing that, in terms of the set $Q$ of states of the automaton, the new algorithm runs in time $O(|Q|^4)$, improving on an efficient implementation of the combinatorial algorithm by a factor of $|Q|$.
FDive: Learning Relevance Models using Pattern-based Similarity Measures
Venue: arXiv cs.LG 2024
Year: 2024

The detection of interesting patterns in large high-dimensional datasets is difficult because of their dimensionality and pattern complexity. Therefore, analysts require automated support for the extraction of relevant patterns. In this paper, we present FDive, a visual active learning system that helps to create visually explorable relevance models, assisted by learning a pattern-based similarity. We use a small set of user-provided labels to rank similarity measures, consisting of feature descriptor and distance function combinations, by their ability to distinguish relevant from irrelevant data. Based on the best-ranked similarity measure, the system calculates an interactive Self-Organizing Map-based relevance model, which classifies data according to the cluster affiliation. It also automatically prompts further relevance feedback to improve its accuracy. Uncertain areas, especially near the decision boundaries, are highlighted and can be refined by the user. We evaluate our approach by comparison to state-of-the-art feature selection techniques and demonstrate the usefulness of our approach by a case study classifying electron microscopy images of brain cells. The results show that FDive enhances both the quality and understanding of relevance models and can thus lead to new insights for brain research.
LassoNet: Deep Lasso-Selection of 3D Point Clouds
Venue: arXiv cs.HC 2024
Year: 2024

Selection is a fundamental task in exploratory analysis and visualization of 3D point clouds. Prior researches on selection methods were developed mainly based on heuristics such as local point density, thus limiting their applicability in general data. Specific challenges root in the great variabilities implied by point clouds (e.g., dense vs. sparse), viewpoint (e.g., occluded vs. non-occluded), and lasso (e.g., small vs. large). In this work, we introduce LassoNet, a new deep neural network for lasso selection of 3D point clouds, attempting to learn a latent mapping from viewpoint and lasso to point cloud regions. To achieve this, we couple user-target points with viewpoint and lasso information through 3D coordinate transform and naive selection, and improve the method scalability via an intention filtering and farthest point sampling. A hierarchical network is trained using a dataset with over 30K lasso-selection records on two different point cloud data. We conduct a formal user study to compare LassoNet with two state-of-the-art lasso-selection methods. The evaluations confirm that our approach improves the selection effectiveness and efficiency across different combinations of 3D point clouds, viewpoints, and lasso selections. Project Website: https://lassonet.github.io
Outstanding: A Multi-Perspective Travel Approach for Virtual Reality Games
Venue: arXiv cs.HC 2024
Year: 2024

In virtual reality games, players dive into fictional environments and can experience a compelling and immersive world. State-of-the-art VR systems allow for natural and intuitive navigation through physical walking. However, the tracking space is still limited, and viable alternatives are required to reach further virtual destinations. Our work focuses on the exploration of vast open worlds - an area where existing local navigation approaches such as the arc-based teleport are not ideally suited and world-in-miniature techniques potentially reduce presence. We present a novel alternative for open environments: Our idea is to equip players with the ability to switch from first-person to a third-person bird's eye perspective on demand. From above, players can command their avatar and initiate travels over large distance. Our evaluation reveals a significant increase in spatial orientation while avoiding cybersickness and preserving presence, enjoyment, and competence. We summarize our findings in a set of comprehensive design guidelines to help developers integrate our technique.
Multiplayer Bandit Learning, from Competition to Cooperation
Venue: arXiv cs.GT 2024
Year: 2024

The stochastic multi-armed bandit model captures the tradeoff between exploration and exploitation. We study the effects of competition and cooperation on this tradeoff. Suppose there are $k$ arms and two players, Alice and Bob. In every round, each player pulls an arm, receives the resulting reward, and observes the choice of the other player but not their reward. Alice's utility is $Γ_A + λΓ_B$ (and similarly for Bob), where $Γ_A$ is Alice's total reward and $λ\in [-1, 1]$ is a cooperation parameter. At $λ= -1$ the players are competing in a zero-sum game, at $λ= 1$, they are fully cooperating, and at $λ= 0$, they are neutral: each player's utility is their own reward. The model is related to the economics literature on strategic experimentation, where usually players observe each other's rewards. With discount factor $β$, the Gittins index reduces the one-player problem to the comparison between a risky arm, with a prior $μ$, and a predictable arm, with success probability $p$. The value of $p$ where the player is indifferent between the arms is the Gittins index $g = g(μ,β) > m$, where $m$ is the mean of the risky arm. We show that competing players explore less than a single player: there is $p^* \in (m, g)$ so that for all $p > p^*$, the players stay at the predictable arm. However, the players are not myopic: they still explore for some $p > m$. On the other hand, cooperating players explore more than a single player. We also show that neutral players learn from each other, receiving strictly higher total rewards than they would playing alone, for all $ p\in (p^*, g)$, where $p^*$ is the threshold from the competing case. Finally, we show that competing and neutral players eventually settle on the same arm in every Nash equilibrium, while this can fail for cooperating players.
Toward a Taxonomy of Inventory Systems for Virtual Reality Games
Venue: arXiv cs.HC 2024
Year: 2024

Virtual reality (VR) games are gradually becoming more elaborated and feature-rich, but fail to reach the complexity of traditional digital games. One common feature that is used to extend and organize complex gameplay is the in-game inventory, which allows players to obtain and carry new tools and items throughout their journey. However, VR imposes additional requirements and challenges that impede the implementation of this important feature and hinder games to unleash their full potential. Our current work focuses on the design space of inventories in VR games. We introduce this sparsely researched topic by constructing a first taxonomy of the underlying design considerations and building blocks. Furthermore, we present three different inventories that were designed using our taxonomy and evaluate them in an early qualitative study. The results underline the importance of our research and reveal promising insights that show the huge potential for VR games.
Online Causal Inference for Advertising in Real-Time Bidding Auctions
Venue: arXiv cs.LG 2024
Year: 2024

Real-time bidding (RTB) systems, which utilize auctions to allocate user impressions to competing advertisers, continue to enjoy success in digital advertising. Assessing the effectiveness of such advertising remains a challenge in research and practice. This paper proposes a new approach to perform causal inference on advertising bought through such mechanisms. Leveraging the economic structure of first- and second-price auctions, we first show that the effects of advertising are identified by the optimal bids. Hence, since these optimal bids are the only objects that need to be recovered, we introduce an adapted Thompson sampling (TS) algorithm to solve a multi-armed bandit problem that succeeds in recovering such bids and, consequently, the effects of advertising while minimizing the costs of experimentation. We derive a regret bound for our algorithm which is order optimal and use data from RTB auctions to show that it outperforms commonly used methods that estimate the effects of advertising.
Eliminating Left Recursion without the Epsilon
Venue: arXiv cs.DS 2024
Year: 2024

The standard algorithm to eliminate indirect left recursion takes a preventative approach, rewriting a grammar's rules so that indirect left recursion is no longer possible, rather than eliminating it only as and when it occurs. This approach results in many of the rules being lost, so that the parse trees that result are often devoid of the detail that the BNF was supposed to capture in the first place. Furthermore, the standard algorithm results in exponential blow-up as the BNF is rewritten, making it wholly unworkable in practice. To avoid these pitfalls, we revise the standard algorithm to eliminate direct left recursion and then take a graph-theoretic approach to eliminating indirect left recursion. We also extend the algorithm to rewrite the resultant parse trees in order to recover the parse trees that would have resulted if left recursion had not had to be eliminated in the first place. Therefore, aside from a couple of caveats, our algorithm works not just in theory but also in practice.
Returning to Shannon's Original Meaning
Venue: arXiv cs.IT 2024
Year: 2024

Shannon theory is revisited to show that ergodicity is an indispensable element of channel capacity. The generalized channel capacity $C=\sup_{\bm{X}}\underline{I}(\bm{X}; \bm{Y})$ is checked with a negative conclusion and the popular assertion "the capacity of a slow fading channel is zero in strict Shannon sense" is found to be conceptually wrong.