Explaining artificial intelligence models can be utilized to launch targeted adversarial attacks on text classification algorithms. Understanding the reasoning behind the model’s decisions makes it easier to prepare such samples. Most of the current text-based adversarial attacks rely on brute-force by using SHAP approach to identify the importance of tokens in the samples, we modify the crucial ones to prepare targeted attacks. We base our results on experiments using 5 datasets. Our results show that our approach outperforms TextBugger and TextFooler, achieving better results with 4 out of 5 datasets against TextBugger, and 3 out of 5 datasets against TextFooler, while minimizing perturbation introduced to the texts. In particular, we managed to outperform the efficacy of TextFooler by over 3100% and TextBugger by over 420% on the WikiPL dataset, additionally keeping high cosine similarity between the original text sample and the adversarial example. The evaluation of the results was additionally supported through a survey to assess their quality and ensure that the text perturbations did not change the intended class according to subjective, human classification.

A majority of research in communication in wireless networks is devoted to maximizing information flow, improving connectivity, or making the system robust against physical perturbations such as jamming. In this work we study how intentional jamming can be used for assuring privacy of wireless communication under the popular Signal-to-Interference-plus- Noise-Ratio (SINR) model. The considered problem, called Zone-restriction with Max-coverage, is as follows: how to place a number of jamming stations in order to generate interference that block the signal of given genuine stations in a specified restricted area, i.e., by making the SINR value of the genuine stations’ signal below a pre-defined threshold in that area. In the construction of algorithms, we aim at optimizing both the accuracy – by minimizing the impact of the jamming stations to the area of genuine communication and by maximizing their influence to the area that should be jammed, as well as the energy consumption of the jamming stations. We present several solutions in various settings of the network, which often lead to challenging analysis even in relatively simple cases. Among others, we show that, surprisingly, it is possible to jam arbitrarily large areas by jammers using total energy arbitrarily close to zero.

We examine deterministic contention resolution on a multiple-access channel when packets are injected continuously by an adversary to the buffers of n available stations in the system, arbitrarily at rate at most ρ packets per round. The aim is to successfully transmit packets and maintain system stability, that is, bounded queues, even in infinite executions. The largest injection rate for which a given contention resolution algorithm guaranties stability is called (algorithm's) throughput. In contrast to the previous work, we consider a channel in which there is a strict limit k on the total number of stations allowed to transmit or listen to the channel at a given time, that can never be exceeded; we call such channel a k-restrained channel. We construct adaptive and full sensing protocols with optimal throughput 1 and almost optimal throughput 1-1/n, respectively, in a constant-restrained channel. By contrast, we show that restricted protocols based on schedules known in advance obtain throughput at most min{[k/n], [1/3logn]}. We also support our theoretical analysis by simulation results of our algorithms in systems of moderate, realistic sizes and scenarios, and compare them with popular backoff protocols.

We study the problem of scheduling n similar jobs on m machines, with respect to the fact that jobs are dependent and some of them must be performed before others. Dependencies between jobs are modeled as a partial order relation. Machines are prone to crashes, induced by an Adaptive f-Bounded adversary who can fail up to f machines, where . Communication takes place via a Multiple-Access Channel (MAC), which restricts simultaneous transmissions. We show an optimal solution (with respect to total work of all machines) for partially ordered sets of jobs forming chains and an algorithm and lower bound for trees.

We investigate routing on networks modeled as multiple access channels, when packets are injected continually. An energy cap is a component of the system, understood as a bound on the number of stations that can be switched on simultaneously. Each packet is injected into some station and needs to be delivered to its destination station via the channel. A station has to be switched on in order to receive a packet when it is heard on the channel. Each station manages when it is switched on and off by way of a programmable wake-up mechanism, which is scheduled by a routing algorithm. Packet injection is governed by adversarial models that determine upper bounds on injection rates and burstiness. We develop deterministic distributed routing algorithms and assess their performance in the worst-case sense. An algorithm knows the number of stations but does not know the adversary. One of the algorithms maintains bounded queues for the maximum injection rate 1 subject only to the energy cap 3. This energy cap is provably optimal, in that obtaining the same throughput with the energy cap 2 is impossible. We give algorithms subject to the minimum energy cap 2 that have latency polynomial in the total number of stations~n for each fixed adversary of injection rate less than 1. An algorithm is k-energy-oblivious if at most k stations are switched on in a round and for each station the rounds when it will be switched on are determined in advance. We give a k-energy-oblivious algorithm that has packet delay O(n) for adversaries of injection rates less than (k-1)/(n-1), and show that there is no k-energy-oblivious stable algorithm against adversaries with injection rates greater than k/n. An algorithm routes directly when each packet makes only one hop from the station into which it is injected straight to its destination. We give a k-energy-oblivious algorithm routing directly, which has latency O(n^2/k) for adversaries of sufficiently small injection rates that are O(k^2/n^2). We develop a k-energy-oblivious algorithm routing directly, which is stable for injection rate k(k-1)/n(n-1), and show that no k-energy-oblivious algorithm routing directly can be stable against adversaries with injection rates greater than k(k-1)/n(n-1).

An execution of a distributed algorithm is often seen as a game between the algorithm and a conceptual adversary causing specific distractions to the computation. In this work we define a class of ordered adaptive adversaries, which cause distractions—in particular crashes—online according to some partial order of the participating stations, which is fixed by the adversary before the execution. We distinguish: Linearly-Ordered adversary, restricted by some pre-defined linear order of (potentially) crashing stations; Anti-Chain-Ordered adversary, previously known as the Weakly-Adaptive adversary, which is restricted by some pre-defined set of crash-prone stations (it can be seen as an ordered adversary with the order being an anti-chain, i.e., a collection of incomparable elements, consisting of these stations); k-Thick-Ordered adversary restricted by partial orders of stations with a maximum anti-chain of size k. We initiate a study of how they affect performance of algorithms. For this purpose, we focus on the well-known Do-All problem of performing t tasks by p synchronous crash-prone stations communicating on a shared channel. The channel restricts communication by the fact that no message is delivered to the operational stations if more than one station transmits at the same time. The question addressed in this work is how the ordered adversaries controlling crashes of stations influence work performance, defined as the total number of available processor steps during the whole execution and introduced by Kanellakis and Shvartsman (Distrib Comput 5(4):201–217, 1992) in the context of Write-All algorithms. The first presented algorithm solves the Do-All problem with work $${\mathcal {O}}(t+p \sqrt{t}\log p)$$ against the Linearly-Ordered adversary. Surprisingly, the upper bound on performance of this algorithm does not depend on the number of crashes f and is close to the absolute lower bound $$\varOmega (t+p\sqrt{t})$$ proved in Chlebus et al. (Distrib Comput 18(6):435–451, 2006). Another algorithm is developed against the Weakly-Adaptive adversary. Work done by this algorithm is $$\mathcal {O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} \log p ),$$ which is close to the lower bound $$\varOmega (t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} )$$ proved in [11] and answers the open questions posed there. We generalize this result to the class of k-Thick-Ordered adversaries, in which case the work of the algorithm is bounded by $$\mathcal {O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),k,t\right\} \log p ).$$ We complement this result by proving the almost matching lower bound $$\begin{aligned} \varOmega (t + p\sqrt{t} + p\min \left\{ p/(p-f),k,t\right\} ). \end{aligned}$$ Independently from the results for the ordered adversaries, we consider a class of delayed adaptive adversaries, which could see random choices with some delay. We present an algorithm that works efficiently against the 1-RD adversary, which could see random choices of stations with one round delay, achieving close to optimal $${\mathcal {O}}(t+p \sqrt{t}\log ^{2} p)$$ work complexity. This shows that restricting the adversary by not allowing it to react on random decisions immediately makes it significantly weaker, in the sense that there is an algorithm achieving (almost) optimal work performance.

In wireless networks, consisting of battery-powered devices, energy is a costly resource and most of it is spent on transmitting messages. Broadcast is a problem where a message needs to be transmitted from one node to all other nodes of the network. We study algorithms that can work under limited energy measured as the maximum number of transmissions among all the stations. The goal of the paper is to study tradeoffs between time and energy complexity of broadcast problem in unknown multi-hop radio networks with no collision detection.

In 2011 Bhaskar et al. pointed out that in many cases one can ensure sufficient level of privacy without adding noise by utilizing adversarial uncertainty. Informally speaking, this observation comes from the fact that if at least a part of the data is randomized from the adversary's point of view, it can be effectively used for hiding other values.

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes execute a concurrent program that occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource (also called a critical section), in such a way that at any time, there is at most one process accessing it. In our considerations, the shared resource is the shared communication channel itself (multiple access channel), and the main challenge arises because the channel is also the only mean of communication between these processes. We consider both the classic and a slightly weaker version of mutual exclusion, called $$\varepsilon $$ -mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $$\varepsilon $$ . We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while the $$\varepsilon $$ -mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $$\varepsilon $$ -exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.

Decentralized monitoring and alarming systems can be an attractive alternative to centralized architectures. Distributed sensor nodes (e.g., in the smart grid's distribution network) are closer to an observed event than a global and remote observer or controller. This improves the visibility and response time of the system. Moreover, in a distributed system, local problems may also be handled locally and without overloading the communication network. This paper studies alarming from a distributed computing perspective and for two fundamentally different scenarios: on-duty and off-duty. We model the alarming system as a sensor network consisting of a set of distributed nodes performing local measurements to sense events. In order to avoid false alarms, the sensor nodes cooperate and only escalate an event (i.e., raise an alarm) if the number of sensor nodes sensing an event exceeds a certain threshold. In the on-duty scenario, nodes not affected by the event can actively help in the communication process, while in the off-duty scenario, non-event nodes are inactive. We present and analyze algorithms that minimize the reaction time of the monitoring system while avoiding unnecessary message transmissions. We investigate time and message complexity tradeoffs in different settings, and also shed light on the optimality of our algorithms by deriving cost lower bounds for distributed alarming systems.

In this paper we present a fast leader election protocol for single-hop wireless networks, provably robust against jamming by an external and powerful adversary. A (T,1--ε)-bounded adversary can jam at most (1--ε)w out of any w ≥ T contiguous time slots, for 0 < ε < 1. The network consists of n stations that do not have knowledge of any global parameter n, T,ε. Each station can transmit or listen to the common communication channel. In each slot, all listeners are notified in which of the three states the communication channel is in the current slot: no transmitters, exactly one transmitter or at least two transmitters. To the listening stations, a jammed slot is indistinguishable from the case of at least two transmitters.

A key distribution scheme for wireless sensor networks based on a system of dynamic, pairwise keys is considered. In the scheme, each pair of communicating nodes shares pairwise symmetric keys and changes them at every transmission using a set of hashing functions. This article examines security aspects of the protocol. The most important issue is to ensure that it is infeasible for an adversary to restrict exhaustive key search to a subset of the keyspace. This desirable property holds if, after a small number of random key transitions, the distribution of keys among the nodes is close to uniform. The article provides a rigorous mathematical analysis of the distribution of keys and supplements it with experimental results. The problem is reduced to the question of determining mixing time and the stationary distribution of a random walk on a random digraph. It is shown that with probability close to 1, the mixing time is of small order and the fluctuations of the distribution are limited. This ensures the ongoing security of the protocol by making the communications forward secure and protecting against node compromise.

In this paper we investigate leader election protocols for single-hop radio networks from the perspective of energetic complexity. We discuss different models of energy consumption and their impact on time complexity. We also present some results about energy consumption in classic protocols optimal with respect to time complexity - we show that some very basic, intuitive algorithms for simpler model (with known number of stations) do not have to be optimal when energy of stations is restricted. We show that they can be significantly improved by introducing very simple modifications. Our main technical result is however a protocol for solving leader election problem in case of unknown number of stations n, with expected time O(log epsilon n), such that each station transmits O(1) number of times and no station is awake for more than O(log log log n) rounds.

We present two protocols for data aggregation in networks consisting of many subsystems run by different and potentially adversarial parties. In such a case the messages from the nodes of a subnetwork are aggregated and transmitted to the sink over intermediate nodes which are not controlled by the subnetwork, and which potentially are influenced by an adversary. The adversary aims at changing the result of computations and/or learning the data processed by the stations of the subnetwork.

It has been shown that Sybil attack -- forging identities in order to gain disproportional influence on a distributed system -- can be easily applied in Wireless Sensor Networks (WSN). An adversary capturing a few stations can corrupt most of classic protocols (e.g. leader election procedures) in most of considered models. Moreover, such attack is in practice undetectable in many realistic scenarios. In this paper we present an efficient countermeasure against Sybil attack. It is based on Proofs-of-Work technique -- one of the methods of preventing sending spam. In contrast to previous solutions it is based only on limited computational power of the adversarial devices. Our approach does not require any restrictions on communication between adversarial stations.

In this paper we study the efficiency of information flooding protocols in various communication networks, and in the presence of random faults. We show big differences between the flooding performance of networks with a seemingly similar structure. Since real-life systems usually consist of a moderate number of devices, the analysis presented in this paper is not limited to the asymptotic behavior of the flooding protocol. Instead, exact formulas are provided whenever possible. The presented results can be useful building blocks for the analysis of other, more sophisticated protocols. In particular, they may be used for planning and analyzing sensors network deployed in an environment subject to communication failures.

In this paper we consider the problem of listing all active stations in a single hop radio network in such a way that the outer adversary observing communication could not gain any significant information about the real number of stations. We also consider a counterpart of this problem such that only a good approximation of the number of activated stations is needed. This problem is motivated mainly by military applications of sensors networks, however we present how our approach can be extended to other natural problems and similar models. In our paper we present two algorithms for secure listing and size approximation of the set of activated stations. Both of them are fairly practical (in terms of volume of communication, time of execution and computational complexity) and provably secure for the assumed adversarial model.

In this paper we introduce and analyse the λ-Alert problem: in a single hop radio network a subset of stations is activated. The aim of the protocol is to decide if the number of activated stations is greater or equal to λ. This problem is similar to the k-Selection problem. It can also be seen as an extension of the standard Alert problem. In our paper we consider the λ-Alert problem in various settings. We describe characteristics of oblivious and adaptive deterministic algorithms for the model with and without collision detection. We also show some results for randomized algorithms. In particular, we present a very efficient Las Vegastype algorithm which is immune to an adversary.

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, $n$ processes perform a concurrent program which occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource in such a way that in any time there is at most one process accessing it. We consider both the classic and a slightly weaker version of mutual exclusion, called $\ep$-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $\ep$. We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while $\ep$-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $\ep$-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.

We consider access scheduling to a shared radio channel in networks where a set of stations tries to get exclusive rights to transmit over a shared radio channel. A frequent strategy to solve this problem is that each station independently tosses an asymmetric coin and transmits in case of tails. The trials are executed some number of times and the first station that sends alone in a trial gets the right to broadcast over the shared channel. We consider here a multi-channel case: during onetime slot a station may transmit on k different channels.In this case trials can be arranged in two slightly different ways. The first method is that in each trial a station decides whether to participate in it; if it is so, then the station decides independently for each channel whether to transmit on it. According to the second method a station makes one decision whether to send and if the decision is positive it chooses a single channel for transmission. The second method guarantees a limited energy cost for each station but,as we show, turns out to be inferior regarding success probability. We consider these algorithms for a realistic number of stations. We analyze subtle differences between both algorithms regarding success probability.