OpenRaiser/Intern-Atlas huggingface dataset:
Query-Sequence Optimization on a Reconfigurable Hardware-Accelerated System
Venue: arXiv cs.DB 2020
Year: 2020

Hardware acceleration of database query processing can be done with the help of FPGAs. In particular, they are partially reconfigurable during runtime, which allows for the runtime adaption of the hardware to a variety of queries. Reconfiguration itself, however, takes some time. As the affected area of the FPGA is not available for computations during the reconfiguration, avoiding some of the reconfigurations can improve overall performance. This paper presents optimizations based on query sequences, which reduces the impact of the reconfigurations. Knowledge of coming queries is used to (I) speculatively start reconfiguration already when a query is still running and (II) avoid overwriting of reconfigurable regions that will be used again in subsequent queries. We evaluate our optimizations with a calibrated model and measurements for various parameter values. Improvements in execution time of up to 21% can be obtained even with sequences of only two queries
Concise Read-Only Specifications for Better Synthesis of Programs with Pointers -- Extended Version
Venue: arXiv cs.PL 2020
Year: 2020

In program synthesis there is a well-known trade-off between concise and strong specifications: if a specification is too verbose, it might be harder to write than the program; if it is too weak, the synthesised program might not match the user's intent. In this work we explore the use of annotations for restricting memory access permissions in program synthesis, and show that they can make specifications much stronger while remaining surprisingly concise. Specifically, we enhance Synthetic Separation Logic (SSL), a framework for synthesis of heap-manipulating programs, with the logical mechanism of read-only borrows. We observe that this minimalistic and conservative SSL extension benefits the synthesis in several ways, making it more (a) expressive (stronger correctness guarantees are achieved with a modest annotation overhead), (b) effective (it produces more concise and easier-to-read programs), (c) efficient (faster synthesis), and (d) robust (synthesis efficiency is less affected by the choice of the search heuristic). We explain the intuition and provide formal treatment for read-only borrows. We substantiate the claims (a)--(d) by describing our quantitative evaluation of the borrowing-aware synthesis implementation on a series of standard benchmark specifications for various heap-manipulating programs.
Exploiting Randomly-located Blockages for Large-Scale Deployment of Intelligent Surfaces
Venue: arXiv cs.IT 2020
Year: 2020

One of the promising technologies for the next generation wireless networks is the reconfigurable intelligent surfaces (RISs). This technology provides planar surfaces the capability to manipulate the reflected waves of impinging signals, which leads to a more controllable wireless environment. One potential use case of such technology is providing indirect line-of-sight (LoS) links between mobile users and base stations (BSs) which do not have direct LoS channels. Objects that act as blockages for the communication links, such as buildings or trees, can be equipped with RISs to enhance the coverage probability of the cellular network through providing extra indirect LoS-links. In this paper, we use tools from stochastic geometry to study the effect of large-scale deployment of RISs on the performance of cellular networks. In particular, we model the blockages using the line Boolean model. For this setup, we study how equipping a subset of the blockages with RISs will enhance the performance of the cellular network. We first derive the ratio of the blind-spots to the total area. Next, we derive the probability that a typical mobile user associates with a BS using an RIS. Finally, we derive the probability distribution of the path-loss between the typical user and its associated BS. We draw multiple useful system-level insights from the proposed analysis. For instance, we show that deployment of RISs highly improves the coverage regions of the BSs. Furthermore, we show that to ensure that the ratio of blind-spots to the total area is below 10^5, the required density of RISs increases from just 6 RISs/km2 when the density of the blockages is 300 blockage/km^2 to 490 RISs/km^2 when the density of the blockages is 700 blockage/km^2.
On Maximizing Egalitarian Value in K-coalitional Hedonic Games
Venue: arXiv cs.GT 2020
Year: 2020

This paper considers the problem of dividing agents among coalitions. We concentrate on Additively Separable Hedonic Games (ASHG's), in which each agent has a non-negative value for every other agent and her utility is the sum of the values she assigns to the members of her coalition. Unlike previous work, we analyze a model where exactly $k$ coalitions must be formed, and the goal is to maximize the utility of the agent which is worst off, i.e., the egalitarian social welfare. We show that this problem is hard, even when the number of agents should be equally divided among the coalitions. We thus propose a heuristic that maximizes the egalitarian social welfare and maximizes the average utility of each agent as a secondary goal. Using extensive simulations, both on synthetic and real data, we demonstrate the effectiveness of our approach. Specifically, our heuristic provides solutions that are much fairer than the solutions that maximize the average social welfare, while still providing a relatively high average social welfare.
RSA and redactable blockchains
Venue: arXiv cs.CR 2020
Year: 2020

A blockchain is redactable if a private key holder (e.g. a central authority) can change any single block without violating integrity of the whole blockchain, but no other party can do that. In this paper, we offer a simple method of constructing redactable blockchains inspired by the ideas underlying the well-known RSA encryption scheme. Notably, our method can be used in conjunction with any reasonable hash function that is used to build a blockchain. Public immutability of a blockchain in our construction is based on the computational hardness of the RSA problem and not on properties of the underlying hash function. Corruption resistance is based on the computational hardness of the discrete logarithm problem.
Business Negotiation Definition Language
Venue: arXiv cs.AI 2020
Year: 2020

The target of this paper is to present an industry-ready prototype software for general game playing. This software can also be used as the central element for experimental economics research, interfacing of game-theoretic libraries, AI-driven software testing, algorithmic trade, human behavior mining and simulation of (strategic) interactions. The software is based on a domain-specific language for electronic business to business negotiations -- SIDL3.0. The paper also contains many examples to prove the power of this language.
Variational Autoencoders for Opponent Modeling in Multi-Agent Systems
Venue: arXiv cs.LG 2020
Year: 2020

Multi-agent systems exhibit complex behaviors that emanate from the interactions of multiple agents in a shared environment. In this work, we are interested in controlling one agent in a multi-agent system and successfully learn to interact with the other agents that have fixed policies. Modeling the behavior of other agents (opponents) is essential in understanding the interactions of the agents in the system. By taking advantage of recent advances in unsupervised learning, we propose modeling opponents using variational autoencoders. Additionally, many existing methods in the literature assume that the opponent models have access to opponent's observations and actions during both training and execution. To eliminate this assumption, we propose a modification that attempts to identify the underlying opponent model using only local information of our agent, such as its observations, actions, and rewards. The experiments indicate that our opponent modeling methods achieve equal or greater episodic returns in reinforcement learning tasks against another modeling method.
A kind of quaternary sequences of period $2p^mq^n$ and their linear complexity
Venue: arXiv cs.IT 2020
Year: 2020

Sequences with high linear complexity have wide applications in cryptography. In this paper, a new class of quaternary sequences over $\mathbb{F}_4$ with period $2p^mq^n$ is constructed using generalized cyclotomic classes. Results show that the linear complexity of these sequences attains the maximum.
Provably Secure Isolation for Interruptible Enclaved Execution on Small Microprocessors: Extended Version
Venue: arXiv cs.CR 2020
Year: 2020

Computer systems often provide hardware support for isolation mechanisms like privilege levels, virtual memory, or enclaved execution. Over the past years, several successful software-based side-channel attacks have been developed that break, or at least significantly weaken the isolation that these mechanisms offer. Extending a processor with new architectural or micro-architectural features, brings a risk of introducing new such side-channel attacks. This paper studies the problem of extending a processor with new features without weakening the security of the isolation mechanisms that the processor offers. We propose to use full abstraction as a formal criterion for the security of a processor extension, and we instantiate that criterion to the concrete case of extending a microprocessor that supports enclaved execution with secure interruptibility of these enclaves. This is a very relevant instantiation as several recent papers have shown that interruptibility of enclaves leads to a variety of software-based side-channel attacks. We propose a design for interruptible enclaves, and prove that it satisfies our security criterion. We also implement the design on an open-source enclave-enabled microprocessor, and evaluate the cost of our design in terms of performance and hardware size.
Cross-Layer Scheduling and Beamforming in Smart-Grid Powered Cellular Networks With Heterogeneous Energy Coordination
Venue: arXiv cs.IT 2020
Year: 2020

User scheduling, beamforming and energy coordination are investigated in smart-grid powered cellular networks (SGPCNs), where the base stations are powered by a smart grid and natural renewable energy sources. Heterogeneous energy coordination is considered in SGPCNs, namely energy merchandizing with the smart grid and energy exchanging among the base stations. A long-term grid-energy expenditure minimization problem with proportional-rate constraints is formulated for SGPCNs. Since user scheduling is coupled with the beamforming vectors, the formulated problem is challenging to handle via standard convex optimization methods. In practice, the beamforming vectors need to be updated over each slot according to the channel variations. User scheduling needs to be updated over several slots (frame) since the frequent scheduling of user equipment can cause reliability issues. Therefore, the Lyapunov optimization method is used to decouple the problem. A practical two-scale algorithm is proposed to schedule users at each frame, and obtain the beamforming vectors and amount of exchanged natural renewable energy at each slot. We prove that the proposed two-scale algorithm can asymptotically achieve the optimal solutions via tuning a control parameter. Numerical results verify the performance of the proposed two-scale algorithm.
ScreenTrack: Using a Visual History of a Computer Screen to Retrieve Documents and Web Pages
Venue: arXiv cs.HC 2020
Year: 2020

Computers are used for various purposes, so frequent context switching is inevitable. In this setting, retrieving the documents, files, and web pages that have been used for a task can be a challenge. While modern applications provide a history of recent documents for users to resume work, this is not sufficient to retrieve all the digital resources relevant to a given primary document. The histories currently available do not take into account the complex dependencies among resources across applications. To address this problem, we tested the idea of using a visual history of a computer screen to retrieve digital resources within a few days of their use through the development of ScreenTrack. ScreenTrack is software that captures screenshots of a computer at regular intervals. It then generates a time-lapse video from the captured screenshots and lets users retrieve a recently opened document or web page from a screenshot after recognizing the resource by its appearance. A controlled user study found that participants were able to retrieve requested information more quickly with ScreenTrack than under the baseline condition with existing tools. A follow-up study showed that the participants used ScreenTrack to retrieve previously used resources and to recover the context for task resumption.
Interventions and Counterfactuals in Tractable Probabilistic Models: Limitations of Contemporary Transformations
Venue: arXiv cs.AI 2020
Year: 2020

In recent years, there has been an increasing interest in studying causality-related properties in machine learning models generally, and in generative models in particular. While that is well motivated, it inherits the fundamental computational hardness of probabilistic inference, making exact reasoning intractable. Probabilistic tractable models have also recently emerged, which guarantee that conditional marginals can be computed in time linear in the size of the model, where the model is usually learned from data. Although initially limited to low tree-width models, recent tractable models such as sum product networks (SPNs) and probabilistic sentential decision diagrams (PSDDs) exploit efficient function representations and also capture high tree-width models. In this paper, we ask the following technical question: can we use the distributions represented or learned by these models to perform causal queries, such as reasoning about interventions and counterfactuals? By appealing to some existing ideas on transforming such models to Bayesian networks, we answer mostly in the negative. We show that when transforming SPNs to a causal graph interventional reasoning reduces to computing marginal distributions; in other words, only trivial causal reasoning is possible. For PSDDs the situation is only slightly better. We first provide an algorithm for constructing a causal graph from a PSDD, which introduces augmented variables. Intervening on the original variables, once again, reduces to marginal distributions, but when intervening on the augmented variables, a deterministic but nonetheless causal-semantics can be provided for PSDDs.
Credit Scoring for Good: Enhancing Financial Inclusion with Smartphone-Based Microlending
Venue: arXiv cs.SI 2020
Year: 2020

Globally, two billion people and more than half of the poorest adults do not use formal financial services. Consequently, there is increased emphasis on developing financial technology that can facilitate access to financial products for the unbanked. In this regard, smartphone-based microlending has emerged as a potential solution to enhance financial inclusion. We propose a methodology to improve the predictive performance of credit scoring models used by these applications. Our approach is composed of several steps, where we mostly focus on engineering appropriate features from the user data. Thereby, we construct pseudo-social networks to identify similar people and combine complex network analysis with representation learning. Subsequently we build credit scoring models using advanced machine learning techniques with the goal of obtaining the most accurate credit scores, while also taking into consideration ethical and privacy regulations to avoid unfair discrimination. A successful deployment of our proposed methodology could improve the performance of microlending smartphone applications and help enhance financial wellbeing worldwide.
A4 : Evading Learning-based Adblockers
Venue: arXiv cs.CR 2020
Year: 2020

Efforts by online ad publishers to circumvent traditional ad blockers towards regaining fiduciary benefits, have been demonstrably successful. As a result, there have recently emerged a set of adblockers that apply machine learning instead of manually curated rules and have been shown to be more robust in blocking ads on websites including social media sites such as Facebook. Among these, AdGraph is arguably the state-of-the-art learning-based adblocker. In this paper, we develop A4, a tool that intelligently crafts adversarial samples of ads to evade AdGraph. Unlike the popular research on adversarial samples against images or videos that are considered less- to un-restricted, the samples that A4 generates preserve application semantics of the web page, or are actionable. Through several experiments we show that A4 can bypass AdGraph about 60% of the time, which surpasses the state-of-the-art attack by a significant margin of 84.3%; in addition, changes to the visual layout of the web page due to these perturbations are imperceptible. We envision the algorithmic framework proposed in A4 is also promising in improving adversarial attacks against other learning-based web applications with similar requirements.
stream-learn -- open-source Python library for difficult data stream batch analysis
Venue: arXiv cs.LG 2020
Year: 2020

stream-learn is a Python package compatible with scikit-learn and developed for the drifting and imbalanced data stream analysis. Its main component is a stream generator, which allows to produce a synthetic data stream that may incorporate each of the three main concept drift types (i.e. sudden, gradual and incremental drift) in their recurring or non-recurring versions. The package allows conducting experiments following established evaluation methodologies (i.e. Test-Then-Train and Prequential). In addition, estimators adapted for data stream classification have been implemented, including both simple classifiers and state-of-art chunk-based and online classifier ensembles. To improve computational efficiency, package utilises its own implementations of prediction metrics for imbalanced binary classification tasks.
Ensemble Grammar Induction For Detecting Anomalies in Time Series
Venue: arXiv cs.LG 2020
Year: 2020

Time series anomaly detection is an important task, with applications in a broad variety of domains. Many approaches have been proposed in recent years, but often they require that the length of the anomalies be known in advance and provided as an input parameter. This limits the practicality of the algorithms, as such information is often unknown in advance, or anomalies with different lengths might co-exist in the data. To address this limitation, previously, a linear time anomaly detection algorithm based on grammar induction has been proposed. While the algorithm can find variable-length patterns, it still requires preselecting values for at least two parameters at the discretization step. How to choose these parameter values properly is still an open problem. In this paper, we introduce a grammar-induction-based anomaly detection method utilizing ensemble learning. Instead of using a particular choice of parameter values for anomaly detection, the method generates the final result based on a set of results obtained using different parameter values. We demonstrate that the proposed ensemble approach can outperform existing grammar-induction-based approaches with different criteria for selection of parameter values. We also show that the proposed approach can achieve performance similar to that of the state-of-the-art distance-based anomaly detection algorithm.
Joint Visual-Temporal Embedding for Unsupervised Learning of Actions in Untrimmed Sequences
Venue: arXiv cs.CV 2020
Year: 2020

Understanding the structure of complex activities in untrimmed videos is a challenging task in the area of action recognition. One problem here is that this task usually requires a large amount of hand-annotated minute- or even hour-long video data, but annotating such data is very time consuming and can not easily be automated or scaled. To address this problem, this paper proposes an approach for the unsupervised learning of actions in untrimmed video sequences based on a joint visual-temporal embedding space. To this end, we combine a visual embedding based on a predictive U-Net architecture with a temporal continuous function. The resulting representation space allows detecting relevant action clusters based on their visual as well as their temporal appearance. The proposed method is evaluated on three standard benchmark datasets, Breakfast Actions, INRIA YouTube Instructional Videos, and 50 Salads. We show that the proposed approach is able to provide a meaningful visual and temporal embedding out of the visual cues present in contiguous video frames and is suitable for the task of unsupervised temporal segmentation of actions.
On the Age of Information in Internet of Things Systems with Correlated Devices
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, a real-time Internet of Things (IoT) monitoring system is considered in which multiple IoT devices must transmit timely updates on the status information of a common underlying physical process to a common destination. In particular, a real-world IoT scenario is considered in which multiple (partially) observed status information by different IoT devices are required at the destination, so that the real-time status of the physical process can be properly re-constructed. By taking into account such correlated status information at the IoT devices, the problem of IoT device scheduling is studied in order to jointly minimize the average age of information (AoI) at the destination and the average energy cost at the IoT devices. Particularly, two types of IoT devices are considered: Type-I devices whose status updates randomly arrive and type-II devices whose status updates can be generated-at-will with an associated sampling cost. This stochastic problem is formulated as an infinite horizon average cost Markov decision process (MDP). The optimal scheduling policy is shown to be threshold-based with respect to the AoI at the destination, and the threshold is non-increasing with the channel condition of each device. For a special case in which all devices are type-II, the original MDP can be reduced to an MDP with much smaller state and action spaces. The optimal policy is further shown to have a similar threshold-based structure and the threshold is non-decreasing with an energy cost function of the devices. Simulation results illustrate the structure of the optimal policy and show the effectiveness of the optimal policy compared with a myopic baseline policy.