Abstract Secure signal authentication is arguably one of the most challenging problems in the Internet of Things (IoT), due to the large-scale nature of the system and its susceptibility to man-in-the-middle and data-injection attacks. In this paper, a novel watermarking algorithm is proposed for dynamic authentication of IoT signals to detect cyber-attacks. The proposed watermarking algorithm, based on a deep learning long shortterm memory structure, enables the IoT devices (IoTDs) to extract a set of stochastic features from their generated signal and dynamically watermark these features into the signal. This method enables the IoT gateway, which collects signals from the IoTDs, to effectively authenticate the reliability of the signals. Moreover, in massive IoT scenarios, since the gateway cannot authenticate all of the IoTDs simultaneously due to computational limitations, a game-theoretic framework is proposed to improve the gateway's decision making process by predicting vulnerable IoTDs. The mixed-strategy Nash equilibrium (MSNE) for this game is derived, and the uniqueness of the expected utility at the equilibrium is proven. In the massive IoT system, due to the large set of available actions for the gateway, the MSNE is shown to be analytically challenging to derive, and thus, a learning algorithm that converges to the MSNE is proposed. Moreover, in order to handle incomplete information scenarios, in which the gateway cannot access the state of the unauthenticated IoTDs, a deep reinforcement learning algorithm is proposed to dynamically predict the state of unauthenticated IoTDs and allow the gateway to decide on which IoTDs to authenticate. Simulation results show that with an attack detection delay of under 1 s, the messages can be transmitted from IoTDs with an almost 100% reliability. The results also show that by optimally predicting the set of vulnerable IoTDs, the proposed deep reinforcement learning algorithm reduces the number of compromised IoTDs by up to 30%, compared to an equal probability baseline. message transmission from the IoT devices (IoTDs) [7] . Most IoT architectures consist of four layers: perceptual, network, support, and application [8] . The perceptual layer is the most fundamental layer which collects all sorts of information from the physical world using devices such as accelerometers or radio frequency identification (RFID) tags. Due to the simplicity of the devices and components at the perceptual layer and their resource-constrained nature, securing the IoT signals at this layer is notoriously challenging [8] . Recently, a number of security solutions have been proposed for IoT signal authentication [9] [10] [11] [12] [13] [14] [15] . The work in [9] investigated physical layer security techniques for securing IoT applications. These methods include optimal sensor censoring, channel-based bit flipping, probabilistic ciphering of quantized IoT signals, and artificial noise signal transmission. In [10] , the author suggested bridging the security gap in IoTDs by applying information theory and cryptography at the physical layer of the IoT. An authentication protocol for the IoT is presented in [11] , using lightweight encryption method in order to cope with constrained IoTDs. Moreover, in [12] , the authors developed a learning mechanisms for fingerprinting and authenticating IoTDs and their environment. Other useful signal authentication approaches are found in [13] [14] [15] . To secure IoT-like cyber-physical systems (CPSs), the idea of watermarking has been studied in [16] [17] [18] [19] . In [16] , a new method was proposed to watermark a predefined signal unto a CPS input signal so as to detect replay attacks. A dynamic watermarking algorithm was proposed in [17] for integrity attack detection in networked CPSs. In [18] , the authors introduced a security scheme that ensures detection of data injection attacks using a non-stationary watermarking technique. Finally, the work in [19] analyzed the optimality of Gaussian watermarked signals in presence of cyber attacks in linear time-variant IoT-like systems. Moreover, the security of massive IoT systems has gained attention in recent years [20] [21] [22] [23] . In [20] , a blockchain-based approach was proposed to provide a distributed security solution for the IoT. The work in [21] demonstrated the feasibility of implementing existing device management protocols on resource-constrained devices. A cloud-based algorithm was proposed in [22] to provide privacy service for resourceconstrained IoTDs. Finally, the work in [23] investigated how cloud computing can be securely integrated in large-scale IoT systems. However, the authentication solutions of [9] [10] [11] [12] [13] [14] [15] remain highly complex for deployment at the IoT perceptual layer, and require high computational power. Moreover, these methods do 0090-6778 © 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. not take into account dynamic data injection attacks in which the attacker collects data for a long time duration and uses it for designing stealthy attacks. Furthermore, the watermarking algorithms introduced in [16] [17] [18] [19] , can be detrimental to the performance of a system such as the IoT since an augmented watermark is applied in parallel to the control signal of the system. This can, in turn, lead to a suboptimal performance for the system. In addition, the input signals to IoTDs include information such as temperature, heart rate, and location, which are not controllable and require changing the IoTDs' environment. Moreover, the works in [20] [21] [22] [23] do not consider resource constraints at the IoT gateway for authentication. In a large-scale IoT system, the gateway cannot authenticate all of the transmitted signals from the IoTDs due to the large amount of required computational resources and bandwidth. Therefore, in a practical IoT, the gateway must optimally and intelligently choose which IoTDs to authenticate. The main contribution of this paper is a comprehensive framework that integrates new ideas from deep learning and game theory to enable computationally-efficient authentication of IoT signals and devices, in massive IoT systems. The key contributions include: • We propose a novel watermarking framework that enables the IoT's gateway to authenticate IoTD signals and detect the existence of a cyber attacker who seeks to degrade the performance of the IoT by changing the devices' output signal. The proposed watermarking algorithm uses deep long short-term memory (LSTM) [24] blocks to extract stochastic features such as spectral flatness, skewness, kurtosis, and central moments from IoT signal and watermarks these features inside the original signal. • This dynamic feature extraction approach allows the gateway to detect dynamic data injection attacks in which the attacker can record and process IoT signals, extract the watermarking key, and inject faulty data. Moreover, the proposed LSTM-based watermarking effectively complements other security solutions, such as encryption, by reducing the complexity and latency of data injection attack detection. • To enable the gateway to authenticate IoTDs in a massive IoT system and under resource constraints, we formulate a noncooperative game between the gateway and the attacker to derive the gateway's optimal action in predicting vulnerable IoTDs while considering its computational resource constraints. We derive the mixed-strategy Nash equilibrium of the game and prove the uniqueness of the gateway's expected utility at this equilibrium. • We show that analytically finding the gateway's optimal strategy is computationally expensive in the massive IoT scenario. Therefore, we propose a learning algorithm based on fictitious play that converges to the mixedstrategy Nash equilibrium. Finally, we extend our analysis to a practical case in which the gateway does not have complete information about all the IoTDs. To address this challenge we propose a deep reinforcement learning approach based on LSTM blocks, to learn the security state of the IoTDs based on their past states. We show that the gateway's expected utility using this proposed deep reinforcement learning method is higher than baseline scenarios in which the gateway authenticates all the IoTDs with the same probability. Simulation results show that, using the proposed watermarking approach and for a latency of under 1 second, the IoT signals can be reliably transmitted from IoTDs to the gateway. Moreover, in a massive IoT scenario, the learning algorithms improves the protection of the system by reducing by about 30% the number of compromised IoTDs. The rest of the paper is organized as follows. Section II introduces the system model for IoTD-gateway signal transmission in large-scale IoT systems and proposes the deep learning-based dynamic watermarking for IoTD-gateway signal authentication. Section III analyzes the authentication scenario in the case of a massive IoT with limited resources at the gateway. Section IV presents the simulation results and their analysis while conclusions are drawn in Section V. II. IOT SIGNAL AUTHENTICATION: SYSTEM MODEL AND DEEP LEARNING SOLUTION Consider a massive IoT system having a set N of N IoTDs communicating with a gateway such as a base station as shown in Fig. 1 [25] . Any IoTD i in the system generates a signal y i (t) at time step t with sampling frequency f s i , and transmits this signal to the gateway which uses the received signal for estimation and control of the IoTD operation. In this system, we consider an adversary that seeks to compromise the IoTD by collecting the data from the communication link between the IoTD and the gateway, and, then, manipulates the transmitted signal. In this case, the transmitted signal from each IoTD i will beȳ i (t) = y i (t) which will cause an estimation error at the gateway. Therefore, the gateway must implement an attack detection mechanism to differentiate between honest and false signals received from an IoTD. II. IOT SIGNAL AUTHENTICATION: SYSTEM MODEL First, we analyze the signal authentication process between a single IoTD and the gateway and, then, we propose a dynamic watermarking framework based on deep learning to authenticate this signal communication with a very small delay. Subsequently, in Section III, we study the case in which, due to the massive nature of the system, the gateway is unable to authenticate all of the IoTDs and must choose an optimal subset to authenticate. A. Spread Spectrum Watermarking Watermarking uses a hidden, predefined non-perceptual code (bit stream) inside a multimedia signal to authenticate the ownership of such signals. One of the most widely used watermarking methods is spread spectrum (SS) [26] in which a key pseudo-noise sequence is added to the original signal. The watermarked signal from each IoTD i can then be written as follows: A. Spread Spectrum Watermarking where w i is the IoTD i's watermarked signal, p i is a pseudonoise binary sequence of +1 and −1 for IoTD i, β i is the IoTD i's relative power of the pseudo-noise signal to the original signal, b i is the hidden bit in the signal which can take values +1 and −1, and n i is the number of samples (frame length) of IoTD i's original signal used to hide a single bit. To extract the watermarked bit, the gateway receives the watermarked signal from each IoTD i and correlates it with the key pseudo-noise sequence. The extraction process will be: A. Spread Spectrum Watermarking where, forb i > 0, the extracted bit is 1, forb i < 0, the extracted bit is −1 with < w i , p i > ni being the inner production of n i samples of w i and p i . p i (t) and y i (t) are independent stochastic variables at time t. We assume that y i (t) has mean μ i and variance σ 2 i . Next, we analyze the bit error rate of the extracted bit to evaluate the proposed watermarking scheme's performance. A. Spread Spectrum Watermarking Lemma 1: In the proposed SS watermarking scheme, the bit extraction error for IoTD i is A. Spread Spectrum Watermarking if n i+ = n i− , where n i+ and n i− are the number of samples in p(t) with values equal to +1 and −1, respectively. A. Spread Spectrum Watermarking Proof: Forỹ i , we can write: A. Spread Spectrum Watermarking where A. Spread Spectrum Watermarking Since (3) can be expressed as a sum of i.i.d variables, then, for large values of n i+ and n i− using the central limit theorem, we can write (3) as a linear combination of two Gaussian distributions Sinceỹ is a linear combination of two independent Gaussian distributions, we have: A. Spread Spectrum Watermarking Since n i+ and n i− are design parameters, we choose n i+ = n i− . Thus, we haveỹ i ∼ N 0, 1 A. Spread Spectrum Watermarking Then, to analyze the probability of error we consider b i = 1. In this case an error occurs whenb i < 0, therefore, the probability of an error is: A. Spread Spectrum Watermarking The same error probability can be obtained for b i = −1. From (6), we can observe that, for large values of β i and n i , the bit extraction error goes to zero. However, selecting large values for β i and n i will incur latency and computational costs for IoTDs and gateway, as discussed next. B. Static Watermarking for IoTD Attack Detection Now, using the SS method, we present a technique for authenticating the signals transmitted from an IoTD to the gateway. We first generate a random pseudo-noise binary sequence with n i samples. Also, for every IoTD i, we define a bit stream s i with n si samples. Then, using (1), we embed every bit of s i in n i samples of y i . Therefore, for any bit stream s i , we use n i n si samples of y i , and this embedding procedure will repeat every n i n si samples of y i . At the gateway, using (2), we extract the bit stream. In case of a cyber attack, the received signal in the gateway will beȳ i (t) rather than w i (t), and, hence, the extracted bit stream will differ from s i . Thus, the gateway will trigger an alarm for declaring the existence of a cyber attack. Fig. 2 shows the block diagram of static watermarking for attack detection at the level of an IoTD. B. Static Watermarking for IoTD Attack Detection In our proposed watermarking scheme, β i , n i , and n si play crucial roles in the security of a given IoTD. The value of β i must be much smaller than the value of σ i . Indeed, for B. Static Watermarking for IoTD Attack Detection Therefore, we must choose small values for β i . However, from Lemma 1, we know that a small β i will yields a higher bit error rate. To overcome this issue, we have to increase the pseudo-noise key length, n i . Although increasing the value of n i will reduce the bit error rate, for large values of n i , the bit extraction procedure in (2) will result in higher computation load and will also cause higher latency since the gateway must wait for n i n si samples from the IoTD to detect the attack. Moreover, large values of n si will also cause larger delay at the gateway. Therefore, next, we propose a method to choose suitable values for these three parameters. B. Static Watermarking for IoTD Attack Detection Theorem 1: To reduce the attacker's ability to extract the hidden bit stream as well as minimize the attack detection delay of the watermarking scheme β i , n i , and n si must be selected to satisfy the following conditions: B. Static Watermarking for IoTD Attack Detection where d is the acceptable delay (in seconds) for attack detection, μ 1i and σ 2 1i are the mean and variance of the multiplication of random variables y 1i (t) and y 2i (t) with the same distribution as y i (t), P is our desired probability of unsuccessful attack, andP is our desired bit extraction error probability. B. Static Watermarking for IoTD Attack Detection Proof: See Appendix A. Using (7) , (8) , and (9), we can find the values for the three parameters which satisfy our performance and delay constraints. For example, in Fig. 3 , we consider a scenario in which μ 1i = 0, δ 1i = 0.5, δ i = 0.5, P = 0.05, and P = 0.01. We can see from Fig. 3 that, β i = 0.5 and n i = 10 can satisfy conditions (7) and (8) . Now, if we consider that f s i = 1000, from condition (9), to be able to have a delay at most d = 0.1 seconds, we must have n si = 10. The proposed SS watermarking method can detect a cyber attack which can only change the transmitted data from an IoTD to the gateway. By choosing optimal values for the three watermarking parameters, the gateway can authenticate the transmitted data. Consider a case in which an attacker can also collect data from the IoTDs. Here, the attacker can launch a more complex dynamic data injection attack by recording the transmitted data from the IoTD and, then, summing the recorded data for a long period of time. Such an attack can potentially reveal the key p. For example, if the attacker collects the data for m windows of size nn s and adds this data together, it obtains: B. Static Watermarking for IoTD Attack Detection where y j i is the signal received in window j from an IoTD, andw mi is the summation of collected data. If we consider σ 2 mi as the variance of the sum of m random variable y 1 i (t), . . . , y m i (t), then, there will exist a value for m where m 2 β 2 i σ 2 mi . Hence, the attacker can usē w mi mβ i b i p i as the key for watermarked signal. This attack is successful because the embedded stream s is static, at all times. However, if the bit stream s i changes dynamically in each window of n i n si samples then, the system can deter such a dynamic data injection attack. Next, we propose a dynamic bit stream generation using deep learning. C. Deep Learning for Dynamic IoT Signal Watermarking To improve our authentication scheme, we propose a novel deep learning watermarking method for dynamically generating the bit stream s i which can thwart dynamic data injection attacks. In the proposed dynamic watermarking scheme, we use the fingerprints of the signal y i generated by an IoTD to dynamically update the bit stream, s i . Signal fingerprints are unique identifiers of a signal that can be mapped to a bit stream. Signal stochastic characteristics such as spectral flatness, central moments, skewness, and kurtosis can be used for extraction of fingerprints from signals [27] [28] [29] [30] . Due to time dependence of the IoTD signal stream on past time steps, we use the powerful deep LSTM framework, one of the most effective deep learning methods for sequence analysis, to extract the IoTD signal fingerprints [24] , [31] , and [32] . 1) Introduction to LSTM Cells: Recurrent neural networks (RNNs) are a special type of artificial neural networks (ANNs) which are useful for time series analysis [24] . ANNs are function approximators which map an input vector to a target vector. They are made of layers of artificial neurons which take a vector as an input, aggregate such input vector, and pass the aggregation through an activation function. The output of the last layer's activation function can be considered as the target vector. While such ANNs map an input vector to an output vector, RNNs also feedback the output to their input which makes them suitable to analyze a time dependence in the input. Fig. 4 shows a normal neuron and a recurrent neuron which are used in different ANN architectures. Each of these neurons will have a number of hyperparameters called bias and weights in the aggregation and activation steps. Thus, the aim of using this RNN is to derive those hyperparameters such that one can find an approximation of mapping from input to output. One of the widely used methods to train the RNN and derive the hyperparamters is the gradient descent algorithm [24] , which uses the chain rule and gradient of the RNN's layers to find the optimal hyperparamters which minimize the difference between the RNN's output and the target vector. However, RNNs have a vanishing gradient problem [32] during training phase which means that the gradient of layers close to the input does not change much compared to layers close to the output which makes the convergence of the gradient descent algorithm challenging. Moreover, conventional RNNs such as the ones shown in Fig. 4 tend to forget the information about past samples and emphasize on learning from recent samples. To overcome these challenges, we use LSTM blocks [32] which have three main components as shown in Fig. 5 : 1) A forget gate which receives an extra input called the cell state input and learns how much it should memorize or forget from the past, 2) An input gate which aggregates the output of past steps and the current input and passes it through an activation function as done in a conventional RNN, and 3) An output gate which combines the current cell state and the output of input gate and generates the LSTM output. Next, we explain how we use the LSTMs for IoTD watermarking. C. Deep Learning for Dynamic IoT Signal Watermarking 2) LSTM for Dynamic Signal Watermarking at the IoTDS: To dynamically extract fingerprints from IoTD signals, we use an LSTM algorithm that allows an IoTD to update the bit stream based on the sequence of generated data. An LSTM algorithm processes an input (y i (1), . . . , y i (n i n si )) by adding new information into a memory, and using gates which control the extent to which new information should be memorized, old information should be forgotten, and current information should be used. The output of an LSTM algorithm will be impacted by the network activation at previous time steps and, hence, LSTMs are suitable for our IoT application in which we want to extract fingerprints from signals which are dependent on previous time steps. C. Deep Learning for Dynamic IoT Signal Watermarking During the training phase, the parameters of the LSTM algorithm are learned from a given training dataset of different IoTDs such as accelerometer, gyroscope and positioning devices. As done in [27] [28] [29] [30] , we choose spectral flatness, mean, variance, skewness, and kurtosis as features that are extracted from a signal of length n i n si and then map these values to a bit stream with length n i . Next, we watermark this extracted bit stream into the original signal using a key. To train the LSTM, we use the original signal y i and a pseudo noise key p i as input stream and the watermarked signal w i as output stream. Fig. 6a shows the training phase. Next, we illustrate how we use the trained LSTM to dynamically watermark an IoT signal. C. Deep Learning for Dynamic IoT Signal Watermarking 3) LSTM for Dynamic Signal Authentication at the gateway: At the gateway, we use a dynamic watermarking LSTM (DW-LSTM) for bit extraction. To train this DW-LSTM, we use the watermarked signal w i and key p i as inputs to the neural network and the features of the original signal and extracted bit stream as outputs. The block diagram model of the training phase at the gateway for our DW-LSTM is shown in Fig. 6b . Using the DW-LSTM block of Fig. 6a at the IoTD and the DW-LSTM block of Fig. 6b at the gateway, we propose a dynamic LSTM watermarking scheme to implement an attack detector at the gateway. C. Deep Learning for Dynamic IoT Signal Watermarking In this method, a predefined bit stream is not used since a bit stream is dynamically generated inside the LSTM blocks at the IoTD and the gateway. This dynamic bit stream generation at the hidden layers of LSTMs solves the dynamic data injection attack problem, since recording and summing the IoTD signals will not increase the power ratio of the key sequence to the signal and the attacker will not be able to extract the key and bit stream. Using this method, the IoTD inserts the generated signal and key in its LSTM block in each window of n i n si samples and produces a watermarked signal with different bit stream s i in each window. At the gateway, the received watermarked signal and key are passed from the LSTM. Then, the two outputs (the extracted bits, and extracted features) are compared. In case of dissimilarity between two sequences, an attack alarm is triggered. Fig. 7 shows the block diagram if the proposed dynamic LSTM watermarking for attack detection. In addition, note that the computationally expensive phase in this algorithm is actually the training phase where several iterations are done during gradient descent algorithm to find the optimal weights for the neural network [24] . However, the testing phase is actually a series of summations, multiplications, and activation functions which are not computationally expensive and can be run on any device [24] . The training phase of our proposed deep learning dynamic watermarking can be done offline (e.g. on high performance computers), as already adopted in the literature [24] . Hence, for every IoTD, we train an LSTM network offline and then implement at the corresponding IoTD. After implementation, the IoTDs will not need to train their associated LSTM network online and they will operate in the testing phase. 1 Also, the proposed algorithm enables the gateway to authenticate any IoTD signal with a delay of d. To analyze the required computational resource at the gateway, next, we derive the computational complexity of the proposed watermarking algorithm. C. Deep Learning for Dynamic IoT Signal Watermarking Proposition 1: The complexity of the proposed signal authentication method at the gateway is bounded by O(df s i ). Proof: From (2), we know that, in order to extract each bit in stream s, we need n multiplications and n − 1 summations. Therefore, the complexity of extracting one bit is O(n i ) and extracting all of the bits in s will have a complexity of O(n i n si ). Moreover, from Theorem 1, we know that n i is chosen based on the watermarking performance criteria, while n si is bounded by C. Deep Learning for Dynamic IoT Signal Watermarking . Proposition 1 shows that the sampling rate of an IoTD's signal directly affects the complexity of the authentication process. However, as previously mentioned, an IoTD with higher sampling and packet transmission rates to the gateway will be more valuable for the IoT system [33] . Thus, under 1 The training phase can be done online as well by using some recent advances in LSTM architectures. limited computational resources, the gateway can only authenticate a limited number of IoTD signals using our proposed method and, thus, it has to choose which subset of N it can authenticate. This computational limitation provides an opportunity for the attacker to choose the IoTDs with unauthenticated signals to attack and stay undetected. We assume that the amount of computations that can be done at the gateway is bounded by O(C) which means that the total authentication complexity of all the received signals cannot exceed O(C): C. Deep Learning for Dynamic IoT Signal Watermarking where S ⊆ N is the set of IoTDs whose signals will be authenticated by the gateway and f s i is the sampling rate of IoTD i. Since the arguments on both sides of (10) are linear, we have: C. Deep Learning for Dynamic IoT Signal Watermarking Since the sampling rate f s of each IoTD corresponds to its value for the gateway, v i , by considering a value proportional 2 to each IoTD's sampling frequency C. Deep Learning for Dynamic IoT Signal Watermarking Thus, the gateway must choose a set S ⊆ N that satisfies (12) . In addition, the attacker has a limitation on the number of IoTDs that it can attack simultaneously due to its limited available resources. We capture this resource limitation by assuming that the attacker has only K devices that it can use to dynamically inject data to IoTD signals. Thus, the attacker must choose K target IoTDs, that are not S, while the gateway must predict the IoTDs that the attacker will target and, then, it will authenticate them. Since the attacker's and the gateway's actions are interdependent, the outcome of their decisions requires analyzing their interaction. In the following, we address this interaction between the gateway and the attacker in the large-scale IoT system using a game-theoretic approach [34] . III. GAME THEORY FOR AUTHENTICATION UNDER COMPUTATIONAL CONSTRAINTS In the considered massive IoT system, we assume that IoTDs that have more data to send will be more valuable for the system since more important applications require more frequent monitoring and control [33] . However, IoTDs with more valuable data are also more likely to be selected as an attack target by the adversary. As discussed in Section II, IoTD signal authentication using our proposed technique requires computational resources at the gateway to process the received data from all IoTDs. Therefore, the gateway must optimally predict the vulnerable IoTDs while the attacker must predict which unauthenticated IoTDs to target so as to maximize the disruption in the IoT system. We analyze this problem using game theory. A. Game Formulation To model the interdependent decision making processes of the attacker and the gateway, we introduce a noncooperative game P, Q j , u j , K, C defined by five components: a) the players which are the attacker a and the gateway g in the set P {a, g}, b) the strategy spaces Q j for each player j ∈ P, c) a utility function, u j for each player, d) the number of attacker's devices, K, which can record IoT signals and e) the available computational resources for the gateway, C. Note that the gateway can get the information about K using the typical attackers' capabilities, past attacks, or known data on similar attacks. Moreover, the attacker can extract information about the computational capability of gateways from data sheets and documentations, particularly for standard IoT systems that typically deploy known types of hardware and software. For the gateway, the set of pure strategies Q g corresponds to different feasible IoTD subsets whose signals can be authenticated without exceeding the available computational resources: A. Game Formulation On the other hand, for the attacker the set of pure strategies Q a is a set of K IoTDs that will be targeted by an attack: A. Game Formulation Q a = K ⊂ N |K| ≤ K . Moreover, the utility function 3 of each player can be written as follows: A. Game Formulation where v i is IoTD i's value. These utility functions essentially capture the fraction of secured IoTD signals for the defender, and the fraction of IoTDs that the attacker can compromise while remaining undetected. Therefore, the attacker seeks to maximize the fraction of compromised IoTDs while the defender seeks to minimize it. This coupling in the players strategies and utilities naturally leads to a game-theoretic situation [35] . One of the most important solution concepts for noncooperative games is that of a Nash equilibrium (NE). The NE characterizes a state at which no player j can improve its utility by changing its own strategy, given the strategy of the other player is fixed. For a noncooperative game, the NE in pure (deterministic) strategies can be defined as follows: Definition 1: A pure-strategy Nash equilibrium of a noncooperative game is a vector of strategies X g * , X a * ∈ Q g ×Q a such that ∀j ∈ P, the following holds true: A. Game Formulation The NE characterizes a stable game state at which the gateway cannot improve the protection of IoTD signals by unilaterally changing its action S given that the action of the attacker is fixed. Moreover, at the NE, the attacker cannot manipulate more IoTD signals by changing its action K while the gateway keeps its action S fixed. Before analyzing the NE of our game, we introduce the useful concept of a dominated strategy that we will use in our further analysis. A. Game Formulation Definition 2: Player j's strategy X j is weakly dominated if there exists another strategyX j ⊂ Q j such that: A. Game Formulation with the strict inequality for at least one X −j . In case the above inequality holds strictly for all X −j ∈ Q −j , X j is said to be strictly dominated (byX j ). A. Game Formulation Essentially, a strategy is dominated if choosing it always yields a smaller utility compared to any other strategy, given all possible strategies for other players. Using this definition, prior to finding the NE, we next derive the dominated strategies of the gateway and the attacker. A. Game Formulation Proposition 2: The gateway must choose as many IoTDs as possible to authenticate and, thus, any strategy S ∈ Q g is weakly dominated byS ∈ Q g if S ⊆S. A. Game Formulation Proof: From set theory we have: Therefore, we have: A. Game Formulation which proves that S is weakly dominated byS. Proposition 2 shows that the gateway must use all of its available computational resource to authenticate the IoTD signals since any strategy that is a subset of another strategy uses less computational resources. A. Game Formulation Proposition 3: The attacker must use all of its K recording devices, i.e., any strategy K ∈ Q a is weakly dominated bỹ K ∈ Q a if K ⊆K and K = K. A. Game Formulation Proof: We know that K ⊆K, and, thus, the number of IoTDs that are attacked by the adversary when choosing strategyK is higher than the number of attacked IoTDs when choosing strategy K. Therefore, if the gateway chooses any strategy S, then the number of unauthenticated IoTD devices for the first case will be greater than or equal to the latter case or: A. Game Formulation and, thus, we have: A. Game Formulation Since the attacker cannot choose more than K IoTDs to attack, thus any strategyK with K members, K = K, dominates all the strategies that are K ⊆K. Proposition 3 shows that non-dominated strategies for the attacker are those that include K IoTDs to attack. Here, we defineQ j ⊆ Q j as the set of player j's non-dominated strategies. The attacker's non-dominated strategies can be interpreted as combination of K IoTDs from all N IoTDs. Therefore, the number attacker's strategies is N K . Since the number of attacker's recording devices, K, is comparably less than the number of IoTDs N , we can easily see that the complexity of finding the attacker's non-dominated strategy set is O N K which is comparably smaller than considering all the subsets of N , that results in a complexity of O(2 N ). Thus, Proposition 3 reduces the complexity of the attacker's game significantly. A. Game Formulation For the gateway, finding all the strategies that satisfy the condition in Proposition 2 is an NP-hard problem [36] . Thus, in Algorithm 1 we propose a novel dynamic programing approach to reduce the complexity of finding the nondominated strategies of the gateway. The algorithm takes the set of all IoTD sampling frequencies and C/d as input. In this algorithm, we first define a (N + 1) × (C/d − f s 1 + 1), matrix M whose element M [i, j] is set to a "True" value if there is a subset of IoTDs with a sampling frequency less than f s i such that the summation of all IoTD sampling frequencies in this subset equals j. 3: Start filling all the entities of matrix M : 4: for i ← 1 to N do 5: for j ← f s 1 to C/d do 6 : B ← R, 13 : 15 : A. Game Formulation R ← f s i , 16 : A. Game Formulation Output R 18: Output S Corollary 1: At each stage of computation, the Algorithm 1 uses the solutions of previous subproblems and since the operations used to fill each entity of M are similar, the complexity of finding the defender's non-dominated strategies reduces from O(2 N ) to O(N C/d). Even though Algorithm 1 reduces the complexity of finding the gateway's non-dominated strategies to a linear time, the number of these non-dominated strategies is dependent on the gateway's available resources and the distribution of sampling frequencies. Fig. 8 shows the number of nondominated strategies for the gateway and the attacker, when N = 1000 IoTDs, R ∈ (0, 1], and K ∈ [0.01N, 0.1N ]. In this massive IoT scenario, from Fig. 8 , we can see that, the number of strategies for both players is very large which consequently requires a complex process to find the pure-strategy NE. Moreover, even though we derived the non-dominated strategies for both players, the NE is not guaranteed to exist for our game [34] . For example, consider only three IoTDs with I AN EXAMPLE OF STRATEGIES AND UTILITIES FOR THE GAME BETWEEN THE GATEWAY AND THE ATTACKER {1000, 2000, 3000} as their sampling frequency, assume that C/d = 5000, and an attacker having 1 recording device. This example game, along with the non-dominated strategies of both players, is summarized in Table I . Any element (i, j) in Table I is the outcome of playing the gateway's i-th and the attacker's j-th strategy. From Table I , we observe that, for any outcome of the game, at least one of the players can change its strategy to gain a better payoff. Therefore, this game cannot have a pure-strategy NE for a general case. Thus, we investigate the NE in mixed strategies which is guaranteed to exist for finite noncooperative games [34] . When using mixed strategies, each player will assign a probability for playing each one of its pure strategies. For a massive IoT, the use of mixed strategies is motivated by two facts: a) the gateway and the attacker must randomize over their strategies in order to make it nontrivial for the opponent to guess their potential action, and b) the procedure of choosing IoTDs can be repeated over an infinite time duration and mixed strategies can capture the frequency of choosing certain strategies for both players. Thus, next, we analyze our game's mixed-strategy NE. B. Mixed-Strategy Nash Equilibrium In our game, by using mixed strategies, the attacker and defender will assign probabilities for playing each one of their non-dominated strategies [34] . Let p a be the vector of mixed strategies for the attacker where each element in p a is the probability of choosing a set of IoTDs, i.e., selecting one strategy from the attacker's strategy set K. Moreover, p g is the vector of mixed strategies for the gateway whose elements represent the probability of choosing a certain strategy from the gateway's strategy set, S. Consequently, each player must choose its own mixed-strategy to maximize its expected utility which is defined by: B. Mixed-Strategy Nash Equilibrium for ∀j ∈ P. (19) To solve this problem, we seek to find the mixed-strategy Nash equilibrium, defined as follows: B. Mixed-Strategy Nash Equilibrium Definition 3: A mixed strategy profile p * constitutes a mixed-strategy Nash equilibrium (MSNE) if, for each player, j, we have: U j (p j * , p −j * ) ≥ U j (p j , p −j * ), ∀p j ∈ P j , where P j is the set of all probability distributions for player j over its action space Q j . B. Mixed-Strategy Nash Equilibrium The MSNE for our game implies a state at which the gateway has chosen its optimal randomization over authenticating the signals of its IoTDs and, therefore, cannot further improve the system security by changing this randomization. Similarly, for the attacker, an MSNE is a state at which the attacker has chosen its probability distribution over the selection of IoTDs that it will attack and, thus, cannot improve its expected utility by changing its choice. Since our game is a constant-sum two-player game, the von Neuman indifference principle can be used to find a closed-form solution for the MSNE [34] . Under this principle, at the MSNE, the expected utilities of the players with respect to the mixed strategies played by the opponent must be equal, for every pure strategy choice. To derive the MSNE for our game, we first define an allocation vectorp j N ×1 for each player j such that each element i in this vector is the probability of choosing IoTD i. The relationship between the allocation vector and the mixed-strategy of our game can be written as follows: B. Mixed-Strategy Nash Equilibrium wherep j i is element i of vectorp j . We define K i = K ∈Q a |i ∈ K as the set of all attacker strategies that have IoTD i, and S i = S ∈Q g |i ∈ S as the set of all gateway strategies that have IoTD i. We next derive the mapping between the expected utility of each player by playing mixedstrategy vector p j and the allocation vectorp j , then we prove that our game has infinitely many, MSNEs all of which achieve a unique expected value for both attacker and defender. B. Mixed-Strategy Nash Equilibrium Proposition 4: To map the mixed strategy vectors to allocation vectors the following conditions must hold true: B. Mixed-Strategy Nash Equilibrium where D is the maximum number of IoTDs in a strategy S ∈Q g and, ∀i ∈ N , α i is an integer. Proof: First, we analyze the mapping between attacker's allocation vector and mixed-strategy,p i . From the definition of K i , we have K∈Ki p a (K) =p a i . Moreover, we know that the summation of all the attacker's non-dominated mixed strategies equals to 1, i.e., K∈Q a p a (K) = 1. In addition, since every strategy K ∈Q a has K IoTDs, then, if we make a set by K times repeating the setQ a , we can build each K i from this set to obtain: B. Mixed-Strategy Nash Equilibrium For the gateway, the procedure is similar. From the definition of S i , we have S∈Si p g (S) =p g i and S∈Q g p g (S) = 1. Here, the number of IoTDs in each S ∈Q g is not equal, however, to build S i , ∀i ∈ N , we must define a set with D repetitions ofQ g where D is the maximum number of IoTDs in a strategy S ∈Q g , i.e., D max S∈Q g |S|. Since some of the IoTDs might not be included in the strategies which consist of D IoTDs, the set S i can repeat more than once for these IoTDs, and, therefore, we will have: B. Mixed-Strategy Nash Equilibrium where α i is the number of times S i shows up in D repetitions of setQ g . Proposition 4 uncovers a linear relationship between the allocation probabilities. Using this relationship, and given that the attacker can have a successful attack on IoTD i if the defender does not authenticate IoTD i, we can define the expected utility of the players as follows: B. Mixed-Strategy Nash Equilibrium with the condition in (21) . Next, we derive the MSNE using (21) and (23) . Theorem 2: The defined game between the attacker and the gateway has infinitely many MSNEs that achieve a unique expected utility, V j * , for each player j. These MSNEs can be derived by solving the following minimax problem: B. Mixed-Strategy Nash Equilibrium Proof: Since the game between the players is constantsum, then the expected utility of the game at MSNE is the solution of minimax problem in (24) [34] . Moreover, the defined expected utilities and the constraints in (21) and (23) are linear functions, therefore, the minimax problem in (24) has a single solution which we callp j * and thus the expected utility is unique, V j * . Moreover, using the mapping between the allocation vectors and mixed-strategy vectors we can find the mixed-strategies at MSNE, by solving a set of N equations in (20) . However, since the number of the attacker's and the gateway's strategies are greater than N , then solving this set of equations will result in an infinite number of solutions, i.e., infinitely many MSNEs. B. Mixed-Strategy Nash Equilibrium To solve problem (24) , one must find all the non-dominated strategies of the gateway to derive values of D and α i . However, as discussed before, finding all the gateway's nondominated strategies is challenging in massive IoT scenarios. Therefore, in a massive IoT scenario analytically deriving the MSNE by using traditional algorithms such as minimax is computationally expensive. Moreover, the gateway will need to store the player's massive strategy set and re-run the entire steps of the conventional algorithms to reach an MSNE as the IoT system changes or a new IoTD joins to the system. Hence, the delay during the convergence process of such algorithms may not be tolerable for massive IoT scenarios. Also, at each time step, since the gateway cannot have complete information about the unauthenticated IoTDs due to its resource limitation which makes the convergence of conventional algorithms not suitable for finding MSNE. Therefore, we propose two learning algorithms: a) a fictitious play (FP) for a complete information game where the gateway knows all IoTDs' states at each time step and b) a deep reinforcement learning (DRL) algorithm that considers the gateway's lack of information about the unauthenticated IoTDs. C. Fictitious Play for Complete Information To find the allocation vector at MSNE,p j * , we propose a learning algorithm based on fictitious play (FP) [37] . C. Fictitious Play for Complete Information Since our two-player game is constant-sum, using the results of [34] and [37] , we can guarantee convergence FP to an MSNE. In the proposed algorithm, each player uses its belief about the allocation vector that its opponent will adopt. This belief stems from previous observations and is updated at every iteration. Given that the FP algorithm learns the allocation vector rather than the mixed strategies, it does not require storing the set of players' strategies thus significantly reducing the complexity of finding MSNE compared to von Neuman's approach. Note that the von Neuman approach has a combinatorial complexity O(2 N ). In contrast, by using FP, the complexity reduces to O(N ). Let δ j (t) be player j's perception of the mixed strategy that −j adopts at time instant t. Each element δ j i (t) of δ j (t) represents the belief that j has at time t, that is the probability of attacking IoTD i (for the attacker) or authenticating an IoTD i (for the defender). Such a belief can be built based on the empirical frequency with which j has chosen IoTD i in the past. Thus, let η j i (t) be the number of times that j has observed −j choosing IoTD i up to time instant t. Then, δ j i (t) can be calculated as follows: C. Fictitious Play for Complete Information To this end, at time instant t + 1, based on the vector of empirical probabilities, δ j (t), that it has perceived until time t, each player j chooses the IoTDs that maximize its expected utility with respect to its belief about its opponent while considering both players' constraints, that is, the attacker chooses a set H a of K IoTDs such that: C. Fictitious Play for Complete Information Meanwhile, the gateway chooses a set of IoTDs such that the resulting computational complexity does not exceed its computational resource constraints, as follows: C. Fictitious Play for Complete Information After each player j chooses its strategy at time instant t + 1, it can update its belief as follows: C. Fictitious Play for Complete Information This learning process proceeds until the calculated empirical frequencies converge. Convergence is achieved when: C. Fictitious Play for Complete Information where is the convergence error which is a very small number. C. Fictitious Play for Complete Information This algorithm assumes complete information for the players since they update their strategies based on (26) and (27) at each step, i.e., this algorithm assumes that the attacker knows which IoTDs the gateway authenticated at the previous step, and the gateway knows which IoTDs the attacker attacked at the previous step. This can be practical in scenarios in which even the unauthenticated IoTDs can report their security status to the gateway. However, in more realistic scenarios, the gateway can only have information about the IoTDs that it has authenticated at the previous
{'paper_id': '3666582', 'title': 'Deep Learning for Signal Authentication and Security in Massive Internet-of-Things Systems', 's2_url': 'https://api.semanticscholar.org/CorpusID:3666582', 'source': 'S2ORC'}