Biblio

By broadcasting false Global Navigation Satellite System (GNSS) signals, spoofing attacks will induce false position and time fixes within the victim receiver. In this article, we propose a Sparse Decomposition (SD)-based spoofing detection algorithm in the acquisition process, which can be applied in a single-antenna receiver. In the first step, we map the Fast Fourier transform (FFT)-based acquisition result in a two-dimensional matrix, which is a distorted autocorrelation function when the receiver is under spoof attack. In the second step, the distorted function is decomposed into two main autocorrelation function components of different code phases. The corresponding elements of the result vector of the SD are the code-phase values of the spoofed and the authentic signals. Numerical simulation results show that the proposed method can not only outcome spoofing detection result, but provide reliable estimations of the code phase delay of the spoof attack.

The age of data (AoD) is identified as one of the most novel and important metrics to measure the quality of big data analytics for Internet-of-Things (IoT) applications. Meanwhile, mobile edge computing (MEC) is envisioned as an enabling technology to minimize the AoD of IoT applications by processing the data in edge servers close to IoT devices. In this paper, we study the AoD minimization problem for IoT big data processing in MEC networks. We first propose an exact solution for the problem by formulating it as an Integer Linear Program (ILP). We then propose an efficient heuristic for the offline AoD minimization problem. We also devise an approximation algorithm with a provable approximation ratio for a special case of the problem, by leveraging the parametric rounding technique. We thirdly develop an online learning algorithm with a bounded regret for the online AoD minimization problem under dynamic arrivals of IoT requests and uncertain network delay assumptions, by adopting the Multi-Armed Bandit (MAB) technique. We finally evaluate the performance of the proposed algorithms by extensive simulations and implementations in a real test-bed. Results show that the proposed algorithms outperform existing approaches by reducing the AoD around 10%.

Graph-based Semi-Supervised Learning (GSSL) is a practical solution to learn from a limited amount of labelled data together with a vast amount of unlabelled data. However, due to their reliance on the known labels to infer the unknown labels, these algorithms are sensitive to data quality. It is therefore essential to study the potential threats related to the labelled data, more specifically, label poisoning. In this paper, we propose a novel data poisoning method which efficiently approximates the result of label inference to identify the inputs which, if poisoned, would produce the highest number of incorrectly inferred labels. We extensively evaluate our approach on three classification problems under 24 different experimental settings each. Compared to the state of the art, our influence-driven attack produces an average increase of error rate 50% higher, while being faster by multiple orders of magnitude. Moreover, our method can inform engineers of inputs that deserve investigation (relabelling them) before training the learning model. We show that relabelling one-third of the poisoned inputs (selected based on their influence) reduces the poisoning effect by 50%. ACM Reference Format: Adriano Franci, Maxime Cordy, Martin Gubri, Mike Papadakis, and Yves Le Traon. 2022. Influence-Driven Data Poisoning in Graph-Based Semi-Supervised Classifiers. In 1st Conference on AI Engineering - Software Engineering for AI (CAIN’22), May 16–24, 2022, Pittsburgh, PA, USA. ACM, New York, NY, USA, 11 pages. https://doi.org/10.1145/3522664.3528606

We present a scalable optimization algorithm and its parallel implementation for two-stage stochastic programming problems of large-scale, particularly the security constrained optimal power flow models routinely used in electrical power grid operations. Such problems can be prohibitively expensive to solve on industrial scale with the traditional methods or in serial. The algorithm decomposes the problem into first-stage and second-stage optimization subproblems which are then scheduled asynchronously for efficient evaluation in parallel. Asynchronous evaluations are crucial in achieving good balancing and parallel efficiency because the second-stage optimization subproblems have highly varying execution times. The algorithm employs simple local second-order approximations of the second-stage optimal value functions together with exact first- and second-order derivatives for the first-stage subproblems to accelerate convergence. To reduce the number of the evaluations of computationally expensive second-stage subproblems required by line search, we devised a flexible mechanism for controlling the step size that can be tuned to improve performance for individual class of problems. The algorithm is implemented in C++ using MPI non-blocking calls to overlap computations with communication and boost parallel efficiency. Numerical experiments of the algorithm are conducted on Summit and Lassen supercomputers at Oak Ridge and Lawrence Livermore National Laboratories and scaling results show good parallel efficiency.

The increasing penetration of cyber systems into smart grids has resulted in these grids being more vulnerable to cyber physical attacks. The central challenge of higher order cyber-physical contingency analysis is the exponential blow-up of the attack surface due to a large number of attack vectors. This gives rise to computational challenges in devising efficient attack mitigation strategies. However, a system operator can leverage private information about the underlying network to maintain a strategic advantage over an adversary equipped with superior computational capability and situational awareness. In this work, we examine the following scenario: A malicious entity intrudes the cyber-layer of a power network and trips the transmission lines. The objective of the system operator is to deploy security measures in the cyber-layer to minimize the impact of such attacks. Due to budget constraints, the attacker and the system operator have limits on the maximum number of transmission lines they can attack or defend. We model this adversarial interaction as a resource-constrained attacker-defender game. The computational intractability of solving large security games is well known. However, we exploit the approximately modular behaviour of an impact metric known as the disturbance value to arrive at a linear-time algorithm for computing an optimal defense strategy. We validate the efficacy of the proposed strategy against attackers of various capabilities and provide an algorithm for a real-time implementation.

We consider that in order to improve the utilization rate of spectrum resources and the security rate of unmanned aerial vehicle (UAV) Communication system, a secure transmission scheme of UAV relay assisted cognitive radio network (CRN) is proposed. In the presence of primary users and eavesdroppers, the UAV acts as the decoding and forwarding mobile relay to assist the secure transmission from the source node to the legitimate destination node. This paper optimizes the flight trajectory and transmission power of the UAV relay to maximize the security rate. Since the design problem is nonconvex, the original problem is approximated to a convex constraint by constructing a surrogate function with nonconvex constraints, and an iterative algorithm based on continuous convex approximation is used to solve the problem. The simulation results show that the algorithm can effectively improve the average security rate of the secondary system and successfully optimize the UAV trajectory.

This paper investigates the optimization of physical layer security in multiple-input multiple-output (MIMO) enabled visible light communication (VLC) networks. In the considered model, one transmitter equipped with light-emitting diodes (LEDs) intends to send confidential messages to legitimate users while one eavesdropper attempts to eavesdrop on the communication between the transmitter and legitimate users. This security problem is formulated as an optimization problem whose goal is to minimize the sum mean-square-error (MSE) of all legitimate users while meeting the MSE requirement of the eavesdropper thus ensuring the security. To solve this problem, the original optimization problem is first transformed to a convex problem using successive convex approximation. An iterative algorithm with low complexity is proposed to solve this optimization problem. Simulation results show that the proposed algorithm can reduce the sum MSE of legitimate users by up to 40% compared to a conventional zero forcing scheme.

Deep learning has made remarkable achievements in various domains. Active learning, which aims to reduce the budget for training a machine-learning model, is especially useful for the Deep learning tasks with the demand of a large number of labeled samples. Unfortunately, our empirical study finds that many of the active learning heuristics are not effective when applied to Deep learning models in batch settings. To tackle these limitations, we propose a density weighted diversity based query strategy (DWDS), which makes use of the geometry of the samples. Within a limited labeling budget, DWDS enhances model performance by querying labels for the new training samples with the maximum informativeness and representativeness. Furthermore, we propose a beam-search based method to obtain a good approximation to the optimum of such samples. Our experiments show that DWDS outperforms existing algorithms in Deep learning tasks.

Online social network (OSN) is an ideal venue to enhance one's visibility. This paper considers how a user (called requester) in an OSN selects a small number of available users and invites them as new friends/followers so as to maximize his "social visibility". More importantly, the requester has to do this under the anonymity setting, which means he is not allowed to know the neighborhood information of these available users in the OSN. In this paper, we first develop a mathematical model to quantify the social visibility and formulate the problem of visibility maximization with anonymity guarantee, abbreviated as "VisMAX-A". Then we design an algorithmic framework named as "AdaExp", which adaptively expands the requester's visibility in multiple rounds. In each round of the expansion, AdaExp uses a query oracle with anonymity guarantee to select only one available user. By using probabilistic data structures like the k-minimum values (KMV) sketch, we design an efficient query oracle with anonymity guarantees. We also conduct experiments on real-world social networks and validate the effectiveness of our algorithms.

In some cases, the confidentiality of cryptographic algorithms used in digital communication is related to computational complexity mathematical problems, such as calculating the discrete logarithm, the knapsack problem, decomposing a composite number into prime divisors etc. This article describes the application of insolvability of factorization of a large composite number, and reviews previous work integer factorization using either the deterministic or the bio-inspired algorithms. This article focuses on the possibility of using bio-inspired methods to solve the problem of cryptanalysis of asymmetric encryption algorithms, which ones based on factorization of composite numbers. The purpose of this one is to reviewing previous work in integer factorization algorithms, developing a prototype of either the deterministic and the bio-inspired algorithm and the effectiveness of the developed algorithms and recommendations are made for future research paths.

In this paper, we study the resilient vector consensus problem in multi-agent networks and improve resilience guarantees of existing algorithms. In resilient vector consensus, agents update their states, which are vectors in ℝd, by locally interacting with other agents some of which might be adversarial. The main objective is to ensure that normal (non-adversarial) agents converge at a common state that lies in the convex hull of their initial states. Currently, resilient vector consensus algorithms, such as approximate distributed robust convergence (ADRC) are based on the idea that to update states in each time step, every normal node needs to compute a point that lies in the convex hull of its normal neighbors' states. To compute such a point, the idea of Tverberg partition is typically used, which is computationally hard. Approximation algorithms for Tverberg partition negatively impact the resilience guarantees of consensus algorithm. To deal with this issue, we propose to use the idea of centerpoint, which is an extension of median in higher dimensions, instead of Tverberg partition. We show that the resilience of such algorithms to adversarial nodes is improved if we use the notion of centerpoint. Furthermore, using centerpoint provides a better characterization of the necessary and sufficient conditions guaranteeing resilient vector consensus. We analyze these conditions in two, three, and higher dimensions separately. We also numerically evaluate the performance of our approach.

We focus on policy-aware data centers (PADCs), wherein virtual machine (VM) traffic traverses a sequence of middleboxes (MBs) for security and performance purposes, and propose two new VM placement and migration problems. We first study PAL: policy-aware virtual machine placement. Given a PADC with a data center policy that communicating VM pairs must satisfy, the goal of PAL is to place the VMs into the PADC to minimize their total communication cost. Due to dynamic traffic loads in PADCs, however, above VM placement may no longer be optimal after some time. We thus study PAM: policy-aware virtual machine migration. Given an existing VM placement in the PADC and dynamic traffic rates among communicating VMs, PAM migrates VMs in order to minimize the total cost of migration and communication of the VM pairs. We design optimal, approximation, and heuristic policyaware VM placement and migration algorithms. Our experiments show that i) VM migration is an effective technique, reducing total communication cost of VM pairs by 25%, ii) our PAL algorithms outperform state-of-the-art VM placement algorithm that is oblivious to data center policies by 40-50%, and iii) our PAM algorithms outperform the only existing policy-aware VM migration scheme by 30%.

We study the optimal control problem of the maximum a posteriori (MAP) state sequence detection of an adversary using smart meter data. The privacy leakage is measured using the Bayesian risk and the privacy-enhancing control is achieved in real-time using an energy storage system. The control strategy is designed to minimize the expected performance of a non-causal adversary at each time instant. With a discrete-state Markov model, we study two detection problems: when the adversary is unaware or aware of the control. We show that the adversary in the former case can be controlled optimally. In the latter case, where the optimal control problem is shown to be non-convex, we propose an adaptive-grid approximation algorithm to obtain a sub-optimal strategy with reduced complexity. Although this work focuses on privacy in smart meters, it can be generalized to other sensor networks.

As the computer architecture technology evolves, communication protocols have been demanded not only having reliable security but also flexible functionality. Advanced cryptography has been expected as a new generation cryptography which suffices such the requirements. A pairing is one of the key technologies of the cryptography and the pairing has been known as having a substantial amount of construction parameters. Recently, the elliptic curve with embedding degree 14 is evaluated as one of the efficient curves for pairing. In the paper, we implement an optimal ate pairing on the elliptic curve by applying several variants of multiplication algorithms of extension field of degree 7 on multiple devices. The best multiplication algorithm among the candidates is derived. Besides, for efficient calculations, we propose a pseudo 7-sparse algorithm and a fast calculation method of final exponentiation. As a result, we discover the proper multiplication algorithm bases on the rate of addition and multiplications on several different computer platforms. Our proposed pseudo 7-sparse algorithm is approximately 1.54% faster than a regular algorithm on almost all tested platforms. Eventually, for the total execution time of pairing we record 9.33ms on Corei5-9500.

Although deep convolutional neural network (CNN) performs well in many computer vision tasks, its classification mechanism is very vulnerable when it is exposed to the perturbation of adversarial attacks. In this paper, we proposed a new algorithm to generate the substitute model of black-box CNN models by using knowledge distillation. The proposed algorithm distills multiple CNN teacher models to a compact student model as the substitution of other black-box CNN models to be attacked. The black-box adversarial samples can be consequently generated on this substitute model by using various white-box attacking methods. According to our experiments on ResNet18 and DenseNet121, our algorithm boosts the attacking success rate (ASR) by 20% by training the substitute model based on knowledge distillation.

K-Nearest Neighbor (k-NN) search is one of the most commonly used approaches for similarity search. It finds extensive applications in machine learning and data mining. This era of big data warrants efficiently scaling k-NN search algorithms for billion-scale datasets with high dimensionality. In this paper, we propose a solution towards this end where we use vantage point trees for partitioning the dataset across multiple processes and exploit an existing graph-based sequential approximate k-NN search algorithm called HNSW (Hierarchical Navigable Small World) for searching locally within a process. Our hybrid MPI-OpenMP solution employs techniques including exploiting MPI one-sided communication for reducing communication times and partition replication for better load balancing across processes. We demonstrate computation of k-NN for 10,000 queries in the order of seconds using our approach on 8000 cores on a dataset with billion points in an 128-dimensional space. We also show 10X speedup over a completely k-d tree-based solution for the same dataset, thus demonstrating better suitability of our solution for high dimensional datasets. Our solution shows almost linear strong scaling.

Recent foundational work on leakage-abuse attacks on encrypted databases has broadened our understanding of what an adversary can accomplish with a standard leakage profile. Nevertheless, all known value reconstruction attacks succeed under strong assumptions that may not hold in the real world. The most prevalent assumption is that queries are issued uniformly at random by the client. We present the first value reconstruction attacks that succeed without any knowledge about the query or data distribution. Our approach uses the search-pattern leakage, which exists in all known structured encryption schemes but has not been fully exploited so far. At the core of our method lies a support size estimator, a technique that utilizes the repetition of search tokens with the same response to estimate distances between encrypted values without any assumptions about the underlying distribution. We develop distribution-agnostic reconstruction attacks for both range queries and k-nearest-neighbor (k-NN) queries based on information extracted from the search-pattern leakage. Our new range attack follows a different algorithmic approach than state-of-the-art attacks, which are fine-tuned to succeed under the uniformly distributed queries. Instead, we reconstruct plaintext values under a variety of skewed query distributions and even outperform the accuracy of previous approaches under the uniform query distribution. Our new k-NN attack succeeds with far fewer samples than previous attacks and scales to much larger values of k. We demonstrate the effectiveness of our attacks by experimentally testing them on a wide range of query distributions and database densities, both unknown to the adversary.

The method of extremal filtration implementing the decomposition of signals into alternating components is considered. The history of the method development is described, its mathematical substantiation is given. The method suggests signal decomposition based on the removal of known components locally determined by their extrema. The similarity of the method with empirical modes decomposition in terms of the result is shown, and their comparison is also carried out. The algorithm of extremal filtration has a simple mathematical basis that does not require the calculation of transcendental functions, which provides it with higher performance with comparable results. The advantages and disadvantages of the extremal filtration method are analyzed, and the possibility of its application for solving various technical problems is shown, i.e. the formation of diagnostic features, rapid analysis of signals, spectral and time-frequency analysis, etc. The methods for calculating spectral characteristics are described: by the parameters of the distinguished components, based on the approximation on the extrema by bell-shaped pulses. The method distribution in case of wavelet transform of signals is described. The method allows obtaining rapid evaluation of the frequencies and amplitudes (powers) of the components, which can be used as diagnostic features in solving problems of recognition, diagnosis and monitoring. The possibility of using extremal filtration in real-time systems is shown.

The concept of the adversary model has been widely applied in the context of cryptography. When designing a cryptographic scheme or protocol, the adversary model plays a crucial role in the formalization of the capabilities and limitations of potential attackers. These models further enable the designer to verify the security of the scheme or protocol under investigation. Although being well established for conventional cryptanalysis attacks, adversary models associated with attackers enjoying the advantages of machine learning techniques have not yet been developed thoroughly. In particular, when it comes to composed hardware, often being security-critical, the lack of such models has become increasingly noticeable in the face of advanced, machine learning-enabled attacks. This paper aims at exploring the adversary models from the machine learning perspective. In this regard, we provide examples of machine learning-based attacks against hardware primitives, e.g., obfuscation schemes and hardware root-of-trust, claimed to be infeasible. We demonstrate that this assumption becomes however invalid as inaccurate adversary models have been considered in the literature.

Tor anonymous communication system's resource publishing is vulnerable to enumeration attacks. Zhao determines users who requested resources are unavailable as suspicious malicious users, and gradually reduce the scope of suspicious users through several stages to reduce the false positive rate. However, it takes several stages to distinguish users. Although this method successfully detects the malicious user, the malicious user has acquired many resources in the previous stages, which reduce the availability of the anonymous communication system. This paper proposes a detection method based on Integer Linear Program to detect malicious users who perform enumeration attacks on resources in the process of resource distribution. First, we need construct a bipartite graph between the unavailable resources and the users who requested for these resources in the anonymous communication system; next we use Integer Linear Program to find the minimum malicious user set. We simulate the resource distribution process through computer program, we perform an experimental analysis of the method in this paper is carried out. Experimental results show that the accuracy of the method in this paper is above 80%, when the unavailable resources in the system account for no more than 50%. It is about 10% higher than Zhao's method.

For solving multi-objective optimization problems, this paper firstly combines a multi-objective evolutionary algorithm based on decomposition (MOEA/D) with good convergence and non-dominated sorting genetic algorithm II (NSGA-II) with good distribution to construct. Thus we propose a hybrid multi-objective optimization solving algorithm. Then, we consider that the population diversity needs to be improved while applying multi-objective particle swarm optimization (MOPSO) to solve the multi-objective optimization problems and an improved MOPSO algorithm is proposed. We give the distance function between the individual and the population, and the individual with the largest distance is selected as the global optimal individual to maintain population diversity. Finally, the simulation experiments are performed on the ZDT\textbackslashtextbackslashDTLZ test functions and track planning problems. The results indicate the better performance of the improved algorithms.

Understanding the privacy relevant characteristics of data sets, such as reidentifiability and joinability, is crucial for data governance, yet can be difficult for large data sets. While computing the data characteristics by brute force is straightforward, the scale of systems and data collected by large organizations demands an efficient approach. We present KHyperLogLog (KHLL), an algorithm based on approximate counting techniques that can estimate the reidentifiability and joinability risks of very large databases using linear runtime and minimal memory. KHLL enables one to measure reidentifiability of data quantitatively, rather than based on expert judgement or manual reviews. Meanwhile, joinability analysis using KHLL helps ensure the separation of pseudonymous and identified data sets. We describe how organizations can use KHLL to improve protection of user privacy. The efficiency of KHLL allows one to schedule periodic analyses that detect any deviations from the expected risks over time as a regression test for privacy. We validate the performance and accuracy of KHLL through experiments using proprietary and publicly available data sets.

The application of deep recurrent networks to audio transcription has led to impressive gains in automatic speech recognition (ASR) systems. Many have demonstrated that small adversarial perturbations can fool deep neural networks into incorrectly predicting a specified target with high confidence. Current work on fooling ASR systems have focused on white-box attacks, in which the model architecture and parameters are known. In this paper, we adopt a black-box approach to adversarial generation, combining the approaches of both genetic algorithms and gradient estimation to solve the task. We achieve a 89.25% targeted attack similarity, with 35% targeted attack success rate, after 3000 generations while maintaining 94.6% audio file similarity.

This paper studies the deletion propagation problem in terms of minimizing view side-effect. It is a problem funda-mental to data lineage and quality management which could be a key step in analyzing view propagation and repairing data. The investigated problem is a variant of the standard deletion propagation problem, where given a source database D, a set of key preserving conjunctive queries Q, and the set of views V obtained by the queries in Q, we try to identify a set T of tuples from D whose elimination prevents all the tuples in a given set of deletions on views △V while preserving any other results. The complexity of this problem has been well studied for the case with only a single query. Dichotomies, even trichotomies, for different settings are developed. However, no results on multiple queries are given which is a more realistic case. We study the complexity and approximations of optimizing the side-effect on the views, i.e., find T to minimize the additional damage on V after removing all the tuples of △V. We focus on the class of key-preserving conjunctive queries which is a dichotomy for the single query case. It is surprising to find that except the single query case, this problem is NP-hard to approximate within any constant even for a non-trivial set of multiple project-free conjunctive queries in terms of view side-effect. The proposed algorithm shows that it can be approximated within a bound depending on the number of tuples of both V and △V. We identify a class of polynomial tractable inputs, and provide a dynamic programming algorithm to solve the problem. Besides data lineage, study on this problem could also provide important foundations for the computational issues in data repairing. Furthermore, we introduce some related applications of this problem, especially for query feedback based data cleaning.

The storage efficiency of hash codes and their application in the fast approximate nearest neighbor search, along with the explosion in the size of available labeled image datasets caused an intensive interest in developing learning based hash algorithms recently. In this paper, we present a learning based hash algorithm that utilize ordinal information of feature vectors. We have proposed a novel mathematically differentiable approximation of argmax function for this hash algorithm. It has enabled seamless integration of hash function with deep neural network architecture which can exploit the rich feature vectors generated by convolutional neural networks. We have also proposed a loss function for the case that the hash code is not binary and its entries are digits of arbitrary k-ary base. The resultant model comprised of feature vector generation and hashing layer is amenable to end-to-end training using gradient descent methods. In contrast to the majority of current hashing algorithms that are either not learning based or use hand-crafted feature vectors as input, simultaneous training of the components of our system results in better optimization. Extensive evaluations on NUS-WIDE, CIFAR-10 and MIRFlickr benchmarks show that the proposed algorithm outperforms state-of-art and classical data agnostic, unsupervised and supervised hashing methods by 2.6% to 19.8% mean average precision under various settings.