OpenRaiser/Intern-Atlas huggingface dataset:
Empirical Network Structure of Malicious Programs
Venue: arXiv cs.SI 2022
Year: 2022

A modern binary executable is a composition of various networks. Control flow graphs are commonly used to represent an executable program in labeled datasets used for classification tasks. Control flow and term representations are widely adopted, but provide only a partial view of program semantics. This study is an empirical analysis of the networks composing malicious binaries in order to provide a complete representation of the structural properties of a program. This is accomplished by the measurement of structural properties of program networks in a malicious binary executable dataset. We demonstrate the presence of Scale-Free properties of network structure for program data dependency and control flow graphs, and show that data dependency graphs also have Small-World structural properties. We show that program data dependency graphs have a degree correlation that is structurally disassortative, and that control flow graphs have a neutral degree assortativity, indicating the use of random graphs to model the structural properties of program control flow graphs would show increased accuracy. By providing an increase in feature resolution within labeled datasets of executable programs we provide a quantitative basis to interpret the results of classifiers trained on CFG graph features. An increase in feature resolution allows for the structural properties of program classes to be analyzed for patterns as well as their component parts. By capturing a complete picture of program graphs we can enable theoretical solutions for the mapping a program's operational semantics to its structure.
TestAug: A Framework for Augmenting Capability-based NLP Tests
Venue: arXiv cs.SE 2022
Year: 2022

The recently proposed capability-based NLP testing allows model developers to test the functional capabilities of NLP models, revealing functional failures that cannot be detected by the traditional heldout mechanism. However, existing work on capability-based testing requires extensive manual efforts and domain expertise in creating the test cases. In this paper, we investigate a low-cost approach for the test case generation by leveraging the GPT-3 engine. We further propose to use a classifier to remove the invalid outputs from GPT-3 and expand the outputs into templates to generate more test cases. Our experiments show that TestAug has three advantages over the existing work on behavioral testing: (1) TestAug can find more bugs than existing work; (2) The test cases in TestAug are more diverse; and (3) TestAug largely saves the manual efforts in creating the test suites. The code and data for TestAug can be found at our project website (https://guanqun-yang.github.io/testaug/) and GitHub (https://github.com/guanqun-yang/testaug).
Keypoint Cascade Voting for Point Cloud Based 6DoF Pose Estimation
Venue: arXiv cs.CV 2022
Year: 2022

We propose a novel keypoint voting 6DoF object pose estimation method, which takes pure unordered point cloud geometry as input without RGB information. The proposed cascaded keypoint voting method, called RCVPose3D, is based upon a novel architecture which separates the task of semantic segmentation from that of keypoint regression, thereby increasing the effectiveness of both and improving the ultimate performance. The method also introduces a pairwise constraint in between different keypoints to the loss function when regressing the quantity for keypoint estimation, which is shown to be effective, as well as a novel Voter Confident Score which enhances both the learning and inference stages. Our proposed RCVPose3D achieves state-of-the-art performance on the Occlusion LINEMOD (74.5%) and YCB-Video (96.9%) datasets, outperforming existing pure RGB and RGB-D based methods, as well as being competitive with RGB plus point cloud methods.
Reflections on trusting distributed trust
Venue: arXiv cs.CR 2022
Year: 2022

Many systems today distribute trust across multiple parties such that the system provides certain security properties if a subset of the parties are honest. In the past few years, we have seen an explosion of academic and industrial cryptographic systems built on distributed trust, including secure multi-party computation applications (e.g., private analytics, secure learning, and private key recovery) and blockchains. These systems have great potential for improving security and privacy, but face a significant hurdle on the path to deployment. We initiate study of the following problem: a single organization is, by definition, a single party, and so how can a single organization build a distributed-trust system where corruptions are independent? We instead consider an alternative formulation of the problem: rather than ensuring that a distributed-trust system is set up correctly by design, what if instead, users can audit a distributed-trust deployment? We propose a framework that enables a developer to efficiently and cheaply set up any distributed-trust system in a publicly auditable way. To do this, we identify two application-independent building blocks that we can use to bootstrap arbitrary distributed-trust applications: secure hardware and an append-only log. We show how to leverage existing implementations of these building blocks to deploy distributed-trust systems, and we give recommendations for infrastructure changes that would make it easier to deploy distributed-trust systems in the future.
Beyond the Worst Case: Semi-Random Complexity Analysis of Winner Determination
Venue: arXiv cs.GT 2022
Year: 2022

The computational complexity of winner determination is a classical and important problem in computational social choice. Previous work based on worst-case analysis has established NP-hardness of winner determination for some classic voting rules, such as Kemeny, Dodgson, and Young. In this paper, we revisit the classical problem of winner determination through the lens of semi-random analysis, which is a worst average-case analysis where the preferences are generated from a distribution chosen by the adversary. Under a natural class of semi-random models that are inspired by recommender systems, we prove that winner determination remains hard for Dodgson, Young, and some multi-winner rules such as the Chamberlin-Courant rule and the Monroe rule. Under another natural class of semi-random models that are extensions of the Impartial Culture, we show that winner determination is hard for Kemeny, but is easy for Dodgson. This illustrates an interesting separation between Kemeny and Dodgson.
How advertising strategies affects the diffusion of information in markets
Venue: arXiv cs.SI 2022
Year: 2022

Consumer behavior under social influence is a well-known phenomenon and computer scientists and economists are prevalently trying to analyze the dynamics behind decision making during the consumption process through agent-based modeling (ABM). Some articles tried to explain market inequality because of the social influencing, but the impact of advertising is underestimated and not included as a parameter in the ABM simulations. In the first part of the work we give a background about related works, afterwards, we explain our model with newly introduced advertisement and penalty parameters. To best our knowledge our work will be the first paper that will consider the effects of social influencing, advertisement, and the novelty of the product at the same time. The type of interactions is defined as advertisement and social influencing. We are interested in showing the effects of advertisement and social interactions in different time intervals. The influencing takes time by its nature, however, advertisement is a stronger approach to introduce new products to consumers. These effects are not linearly positive for the fashion products, since the fashion changes over time and consumed items get old-fashioned and ordinary for users. Our Sigmoid penalty function adds non-linearity to the model to show the time and popularity effects against the advertisement and social interactions.
HP-GMN: Graph Memory Networks for Heterophilous Graphs
Venue: arXiv cs.LG 2022
Year: 2022

Graph neural networks (GNNs) have achieved great success in various graph problems. However, most GNNs are Message Passing Neural Networks (MPNNs) based on the homophily assumption, where nodes with the same label are connected in graphs. Real-world problems bring us heterophily problems, where nodes with different labels are connected in graphs. MPNNs fail to address the heterophily problem because they mix information from different distributions and are not good at capturing global patterns. Therefore, we investigate a novel Graph Memory Networks model on Heterophilous Graphs (HP-GMN) to the heterophily problem in this paper. In HP-GMN, local information and global patterns are learned by local statistics and the memory to facilitate the prediction. We further propose regularization terms to help the memory learn global information. We conduct extensive experiments to show that our method achieves state-of-the-art performance on both homophilous and heterophilous graphs.
DyFEn: Agent-Based Fee Setting in Payment Channel Networks
Venue: arXiv cs.LG 2022
Year: 2022

In recent years, with the development of easy to use learning environments, implementing and reproducible benchmarking of reinforcement learning algorithms has been largely accelerated by utilizing these frameworks. In this article, we introduce the Dynamic Fee learning Environment (DyFEn), an open-source real-world financial network model. It can provide a testbed for evaluating different reinforcement learning techniques. To illustrate the promise of DyFEn, we present a challenging problem which is a simultaneous multi-channel dynamic fee setting for off-chain payment channels. This problem is well-known in the Bitcoin Lightning Network and has no effective solutions. Specifically, we report the empirical results of several commonly used deep reinforcement learning methods on this dynamic fee setting task as a baseline for further experiments. To the best of our knowledge, this work proposes the first virtual learning environment based on a simulation of blockchain and distributed ledger technologies, unlike many others which are based on physics simulations or game platforms.
Large Language Models for Multi-label Propaganda Detection
Venue: arXiv cs.CL 2022
Year: 2022

The spread of propaganda through the internet has increased drastically over the past years. Lately, propaganda detection has started gaining importance because of the negative impact it has on society. In this work, we describe our approach for the WANLP 2022 shared task which handles the task of propaganda detection in a multi-label setting. The task demands the model to label the given text as having one or more types of propaganda techniques. There are a total of 21 propaganda techniques to be detected. We show that an ensemble of five models performs the best on the task, scoring a micro-F1 score of 59.73%. We also conduct comprehensive ablations and propose various future directions for this work.
DI-NIDS: Domain Invariant Network Intrusion Detection System
Venue: arXiv cs.CR 2022
Year: 2022

The performance of machine learning based network intrusion detection systems (NIDSs) severely degrades when deployed on a network with significantly different feature distributions from the ones of the training dataset. In various applications, such as computer vision, domain adaptation techniques have been successful in mitigating the gap between the distributions of the training and test data. In the case of network intrusion detection however, the state-of-the-art domain adaptation approaches have had limited success. According to recent studies, as well as our own results, the performance of an NIDS considerably deteriorates when the `unseen' test dataset does not follow the training dataset distribution. In some cases, swapping the train and test datasets makes this even more severe. In order to enhance the generalisibility of machine learning based network intrusion detection systems, we propose to extract domain invariant features using adversarial domain adaptation from multiple network domains, and then apply an unsupervised technique for recognising abnormalities, i.e., intrusions. More specifically, we train a domain adversarial neural network on labelled source domains, extract the domain invariant features, and train a One-Class SVM (OSVM) model to detect anomalies. At test time, we feedforward the unlabeled test data to the feature extractor network to project it into a domain invariant space, and then apply OSVM on the extracted features to achieve our final goal of detecting intrusions. Our extensive experiments on the NIDS benchmark datasets of NFv2-CIC-2018 and NFv2-UNSW-NB15 show that our proposed setup demonstrates superior cross-domain performance in comparison to the previous approaches.
Motion estimation and filtered prediction for dynamic point cloud attribute compression
Venue: arXiv cs.CV 2022
Year: 2022

In point cloud compression, exploiting temporal redundancy for inter predictive coding is challenging because of the irregular geometry. This paper proposes an efficient block-based inter-coding scheme for color attribute compression. The scheme includes integer-precision motion estimation and an adaptive graph based in-loop filtering scheme for improved attribute prediction. The proposed block-based motion estimation scheme consists of an initial motion search that exploits geometric and color attributes, followed by a motion refinement that only minimizes color prediction error. To further improve color prediction, we propose a vertex-domain low-pass graph filtering scheme that can adaptively remove noise from predictors computed from motion estimation with different accuracy. Our experiments demonstrate significant coding gain over state-of-the-art coding methods.
Assessing the Solid Protocol in Relation to Security & Privacy Obligations
Venue: arXiv cs.CR 2022
Year: 2022

The Solid specification aims to empower data subjects by giving them direct access control over their data across multiple applications. As governments are manifesting their interest in this framework for citizen empowerment and e-government services, security and privacy represent pivotal issues to be addressed. By analyzing the relevant legislation, notably GDPR, and international standards, namely ISO/IEC 27001:2011 and 15408, we formulate the primary security and privacy requirements for such a framework. Furthermore, we survey the current Solid protocol specifications regarding how they cover the highlighted requirements, and draw attention to potential gaps between the specifications and requirements. We also point out the contribution of recent academic work presenting novel approaches to increase the security and privacy degree provided by the Solid project. This paper has a twofold contribution to improve user awareness of how Solid can help protect their data and to present possible future research lines on Solid security and privacy enhancements.
On depth-3 circuits and covering number: an explicit counter-example
Venue: arXiv cs.CC 2022
Year: 2022

We give a simple construction of $n\times n$ Boolean matrices with $Ω(n^{4/3})$ zero entries that are free of $2 \times 2$ all-zero submatrices and have covering number $O(\log^4(n))$. This construction provides an explicit counterexample to a conjecture of Pudlák, Rödl and Savický and Research Problems 1.33, 4.9, 11.17 of Jukna [Boolean function complexity]. These conjectures were previously refuted by Katz using a probabilistic construction.
Fair Effect Attribution in Parallel Online Experiments
Venue: arXiv cs.LG 2022
Year: 2022

A/B tests serve the purpose of reliably identifying the effect of changes introduced in online services. It is common for online platforms to run a large number of simultaneous experiments by splitting incoming user traffic randomly in treatment and control groups. Despite a perfect randomization between different groups, simultaneous experiments can interact with each other and create a negative impact on average population outcomes such as engagement metrics. These are measured globally and monitored to protect overall user experience. Therefore, it is crucial to measure these interaction effects and attribute their overall impact in a fair way to the respective experimenters. We suggest an approach to measure and disentangle the effect of simultaneous experiments by providing a cost sharing approach based on Shapley values. We also provide a counterfactual perspective, that predicts shared impact based on conditional average treatment effects making use of causal inference techniques. We illustrate our approach in real world and synthetic data experiments.
An Efficient and Decentralized Blockchain-based Commercial Alternative (Full Version)
Venue: arXiv cs.GT 2022
Year: 2022

While online interactions and exchanges have grown exponentially over the past decade, most commercial infrastructures still operate through centralized protocols, and their success essentially depends on trust between different economic actors. Digital advances such as blockchain technology has led to a massive wave of \textit{Decentralized Ledger Technology} (\textit{DLT}) initiatives, protocols and solutions. This advance makes it possible to implement trustless systems in the real world, which, combined with appropriate economic and participatory incentives, would foster the proper functioning and drive the adoption of a decentralized platform among different actors. This paper describes an alternative to current commercial structures and networks by introducing \textit{Lyzis Labs}, which is is an incentive-driven and democratic protocol designed to support a decentralized online marketplace, based on blockchain technology. The proposal, \textit{Lyzis Marketplace}, allows to connect two or more people in a decentralized and secure way without having to rely on a \textit{Trusted Third Party} (\textit{TTP}) in order to perform physical asset exchanges while mainly providing transparent and fully protected data storage. This approach can potentially lead to the creation of a permissionless, efficient, secure and transparent business environment where each user can gain purchasing and decision-making power by supporting the collective welfare while following their personal interests during their various interactions on the network.
The Effects of Partitioning Strategies on Energy Consumption in Distributed CNN Inference at The Edge
Venue: arXiv cs.AI 2022
Year: 2022

Nowadays, many AI applications utilizing resource-constrained edge devices (e.g., small mobile robots, tiny IoT devices, etc.) require Convolutional Neural Network (CNN) inference on a distributed system at the edge due to limited resources of a single edge device to accommodate and execute a large CNN. There are four main partitioning strategies that can be utilized to partition a large CNN model and perform distributed CNN inference on multiple devices at the edge. However, to the best of our knowledge, no research has been conducted to investigate how these four partitioning strategies affect the energy consumption per edge device. Such an investigation is important because it will reveal the potential of these partitioning strategies to be used effectively for reduction of the per-device energy consumption when a large CNN model is deployed for distributed inference at the edge. Therefore, in this paper, we investigate and compare the per-device energy consumption of CNN model inference at the edge on a distributed system when the four partitioning strategies are utilized. The goal of our investigation and comparison is to find out which partitioning strategies (and under what conditions) have the highest potential to decrease the energy consumption per edge device when CNN inference is performed at the edge on a distributed system.
Semantic Segmentation with Active Semi-Supervised Representation Learning
Venue: arXiv cs.CV 2022
Year: 2022

Obtaining human per-pixel labels for semantic segmentation is incredibly laborious, often making labeled dataset construction prohibitively expensive. Here, we endeavor to overcome this problem with a novel algorithm that combines semi-supervised and active learning, resulting in the ability to train an effective semantic segmentation algorithm with significantly lesser labeled data. To do this, we extend the prior state-of-the-art S4AL algorithm by replacing its mean teacher approach for semi-supervised learning with a self-training approach that improves learning with noisy labels. We further boost the neural network's ability to query useful data by adding a contrastive learning head, which leads to better understanding of the objects in the scene, and hence, better queries for active learning. We evaluate our method on CamVid and CityScapes datasets, the de-facto standards for active learning for semantic segmentation. We achieve more than 95% of the network's performance on CamVid and CityScapes datasets, utilizing only 12.1% and 15.1% of the labeled data, respectively. We also benchmark our method across existing stand-alone semi-supervised learning methods on the CityScapes dataset and achieve superior performance without any bells or whistles.
Efficient Cross-Modal Video Retrieval with Meta-Optimized Frames
Venue: arXiv cs.CV 2022
Year: 2022

Cross-modal video retrieval aims to retrieve the semantically relevant videos given a text as a query, and is one of the fundamental tasks in Multimedia. Most of top-performing methods primarily leverage Visual Transformer (ViT) to extract video features [1, 2, 3], suffering from high computational complexity of ViT especially for encoding long videos. A common and simple solution is to uniformly sample a small number (say, 4 or 8) of frames from the video (instead of using the whole video) as input to ViT. The number of frames has a strong influence on the performance of ViT, e.g., using 8 frames performs better than using 4 frames yet needs more computational resources, resulting in a trade-off. To get free from this trade-off, this paper introduces an automatic video compression method based on a bilevel optimization program (BOP) consisting of both model-level (i.e., base-level) and frame-level (i.e., meta-level) optimizations. The model-level learns a cross-modal video retrieval model whose input is the "compressed frames" learned by frame-level optimization. In turn, the frame-level optimization is through gradient descent using the meta loss of video retrieval model computed on the whole video. We call this BOP method as well as the "compressed frames" as Meta-Optimized Frames (MOF). By incorporating MOF, the video retrieval model is able to utilize the information of whole videos (for training) while taking only a small number of input frames in actual implementation. The convergence of MOF is guaranteed by meta gradient descent algorithms. For evaluation, we conduct extensive experiments of cross-modal video retrieval on three large-scale benchmarks: MSR-VTT, MSVD, and DiDeMo. Our results show that MOF is a generic and efficient method to boost multiple baseline methods, and can achieve a new state-of-the-art performance.