{'fraction_non_alphanumeric': 0.04084649306496514, 'fraction_numerical': 0.013229533640462171, 'mean_word_length': 4.27237303545915, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploiting Trust for Resilient Hypothesis Testing with Malicious Robots

We develop a resilient binary hypothesis testing framework for decision making in adversarial multi-robot crowdsensing tasks. This framework exploits stochastic trust observations between robots to arrive at tractable, resilient decision making at a centralized Fusion Center (FC) even when i) there exist malicious robots in the network and their number may be larger than the number of legitimate robots, and ii) the FC uses one-shot noisy measurements from all robots. We derive two algorithms to achieve this. The first is the Two Stage Approach (2SA) that estimates the legitimacy of robots based on received trust observations, and provably minimizes the probability of detection error in the worst-case malicious attack. Here, the proportion of malicious robots is known but arbitrary. For the case of an unknown proportion of malicious robots, we develop the Adversarial Generalized Likelihood Ratio Test (A-GLRT) that uses both the reported robot measurements and trust observations to estimate the trustworthiness of robots, their reporting strategy, and the correct hypothesis simultaneously. We exploit special problem structure to show that this approach remains computationally tractable despite several unknown problem parameters. We deploy both algorithms in a hardware experiment where a group of robots conducts crowdsensing of traffic conditions on a mock-up road network similar in spirit to Google Maps, subject to a Sybil attack. We extract the trust observations for each robot from actual communication signals which provide statistical information on the uniqueness of the sender. We show that even when the malicious robots are in the majority, the FC can reduce the probability of detection error to 30.5% and 29% for the 2SA and the A-GLRT respectively.


I. INTRODUCTION
We are interested in the problem where robots observe the environment and estimate the presence of an event of interest. Each robot relays their measurement to a Fusion Center (FC) that makes an informed binary decision on the occurrence of the event. An unknown subset of the system are malicious robots whose goal is to increase the likelihood that the FC makes a wrong decision [1], [2], [3], [4]. This problem can be cast as an adversarial binary hypothesis testing problem, with relevance to a broad class of robotics tasks that rely on distributed sensing with possibly malicious or untrustworthy robots. For example, robots might perform coordinated coverage to maximize their ability to sense events of interest [5], [6], [7], [8], share target information for coordinated tracking [9], [10], [11], [12], or merge map information to provide a global understanding of the environment [13], [14], [15], [16]. In crowdsensing tasks such as traffic prediction, a server may use GPS data to estimate if a particular roadway is congested or not [17] (see Fig. 1). Unfortunately, this process is vulnerable to malicious robots [1], [3]. For example, prior works have shown that a Sybil attack can cause crowdsensing applications like Google Maps to incorrectly perceive traffic conditions, resulting in erroneous reporting of traffic flows [18], [19].
The problem of binary adversarial hypothesis testing has been studied within the context of sensor networks [20], [21], [22]. Many approaches use data, such as a history of measurements and hypothesis outcomes, to assess the trustworthiness of the robots [23], [24], [25], [26]. For example, if a robot consistently disagrees with the final decision of the FC, then the FC can flag that robot as potentially adversarial. However, the success of these methods often hinges upon a crucial assumption that more than half of the network is legitimate. A growing body of work investigates additionally sensed quantities arising from the physicality of cyberphysical systems such as multi-robot networks, to cross-validate and assess the trustworthiness of robots [27], [5], [28], [29]. This could include using camera feeds, GPS signals, or even the signatures of received wireless communication signals, to acquire additional information regarding the trustworthiness of the robots [30], [29], [31]. Importantly, this class of trust observations can often be obtained from a one-shot observation, independent of the transmitted measurement. The work in [32] uses trust observations to recover resilient consensus even in the case where more than half of the network is malicious. In this paper we wish to derive a framework for adversarial hypothesis testing that exploits stochastic trust observations to arrive at a similar level of resilience; whereby, a FC can conceivably reduce its probability of error, even in the one-shot scenario and where legitimate robots do not hold a majority in the network.
We derive algorithms for achieving resilient hypothesis testing by exploiting stochastic trust observations between the FC and a group of robots participating in event detection. We derive a framework that exploits one-shot trust observations, hereafter called trust values, over each link to arrive at tractable, closed-form solutions when the majority of the network may be malicious and the strategy of the malicious robots is unknown -a challenging and otherwise intractable problem to solve in the general case [33].
For the case where an upper limit on the proportion of malicious robots is known, we develop the Two Stage Approach (2SA). In the first stage this algorithm uses trust values to determine the most likely set of malicious robots, and then applies a Likelihood Ratio Test (LRT) only over trusted robots in the second stage. We show that this approach minimizes the error probability of the estimated hypothesis at the FC for a worst-case attack scenario. For the case where an upper bound on the proportion of malicious robots is unknown, we develop the Adversarial Generalized Likelihood Ratio Test (A-GLRT) algorithm which uses both stochastic trust values and event measurements to jointly estimate the trustworthiness of each robot, the strategy of malicious robots, and the hypothesis of the event. Our A-GLRT algorithm is based upon a common approach for decision making with unknown parameters, the Generalized Likelihood Ratio Test (GLRT), which replaces the unknown parameters with their maximum likelihood estimates (MLE) [34]. We show that the addition of trust values allows us to decouple the trustworthiness estimation from the strategy of the adversaries, allowing us to calculate the exact MLE of unknown parameters in polynomial time, instead of approximating them as in previous works [33], [35]. Our simulation results show that the A-GLRT empirically yields a lower probability of error than the 2SA, but at the expense of higher computational cost.
Finally we conduct a hardware experiment based on crowdsensing traffic conditions using a group of robots under a Sybil Attack. We show that the FC can recover a performance of 30.5% and 29.0% error, for the 2SA and A-GLRT respectively, even in the case where more than half of the robots are malicious.

II. PROBLEM FORMULATION
We consider a network of N robots, where each robot is indexed by some i ∈ N and N = {1, . . . , N }, that are deployed to sense an environment and determine if an event of interest has occurred. The event of interest is captured by the random variable Ξ, where Ξ = 1 if the event has happened and Ξ = 0 otherwise. Each robot i uses its sensed information to make a local decision about whether the event has happened or not, captured by the random variable Y i , where its realization y i = 1 if robot i believes the event has happened and y i = 0 otherwise. We denote the true hypothesis by H 1 if Ξ = 1 and H 0 if Ξ = 0. Each robot forwards its local decision to a centralized fusion center (FC).
We are concerned with the scenario where not all robots are trustworthy, that is, some are malicious and may manipulate the data that they send to the FC by flipping their measured bit with the goal of increasing the probability that the FC makes the wrong decision. We denote the set of malicious robots by M ⊂ N . The set of robots that are not malicious are termed legitimate robots, denoted by L ⊆ N , where L ∪ M = N and L ∩ M = ∅. Additionally, we define the true trust vector, t ∈ {0, 1} N , where t i = 1 if i ∈ L and t i = 0 if i ∈ M. We note that the true trust vector is unknown by the FC, but it is defined for analytical purposes. We are interested in estimating this vector.
We assume the following behavioral models for legitimate and malicious robots: Definition 1 (Legitimate robot). A legitimate robot i measures the event and sends its measurement Y i to the FC without altering it. We assume for each legitimate robot i ∈ L, the measured bit Y i is subject to noise with the following false alarm and missed detection probabilities where P FA,L ∈ (0, 0.5) and P MD,L ∈ (0, 0.5) without loss of generality. We assume that all legitimate robots have homogeneous sensing capabilities, i.e., they have the same probability of false alarm and missed detection. Moreover, we assume that the measurement of a legitimate robot is independent of all other robots, and identically distributed given the true hypothesis. Finally, we also assume that P FA,L and P MD,L are known by the FC.
Definition 2 (Malicious robot). A robot is said to be a malicious robot if it can choose to alter its measurements before sending it to the FC. We assume that a malicious robot i ∈ M can flip its measurement with probability p f ∈ [0, 1] after making an observation, and that all malicious robots flip their bit with the same probability. Let p FA,M , p MD,M ∈ [0, 0.5) be the probability of false alarm and missed-detection of a malicious robot before altering the bit. We assume that all malicious robots have the same probability of false alarm and missed detection. The effective probabilities of false alarm and missed-detection of a malicious robot after altering the bit are given as: We assume that a measurement coming from a malicious robot is independent of other measurements given the true hypothesis. This implies that malicious robots do not cooperate with each other. Furthermore, we assume that p FA,M , p MD,M , and the strategy of the malicious robots, which is the flipping probability p f , are not known by the FC. This implies that the FC does not know P FA,M and P MD,M either.
We use a common assumption in the literature which is that the measurements coming from malicious robots are i.i.d (see [2], [4], [21], [22]). In addition to the measurements Y i , we assume that each Y i is tagged with a trust value α i ∈ R. Specifically, we consider the class of problems where the FC can leverage the cyber-physical nature of the network to extract an estimation of trust about each communicating robot.
Definition 3 (Trust Value α i ). A trust value α i is a stochastic variable that captures information about the true legitimacy of a robot i. We denote the set of all possible trust values (aka sample space) by A and denote a realization for robot i by a i . Assumption 1. We assume that the set A is finite and that the trust value distributions are homogeneous across all the legitimate robots i ∈ L. To this end, we denote the probability mass function of the trust values of robots by p α (a|t). We assume the probability mass functions are known or can be estimated by the FC. 1 We assume that the trust values are i.i.d given the true legitimacy of the robot. Moreover, the trust values are assumed to be independent of the measurements, Y i , and the true hypothesis. Finally, to omit trivial or noninformative cases, we assume that We do not impose any restrictions over the conditional probability distributions p α (a|t = 1) and p α (a|t = 0). However, for the trust values to be meaningful they should have different probability mass functions, i.e., p α (a|t = 1) = p α (a|t = 0). How distinguishable the two probability mass functions are is termed the quality of the trust value, where a better quality corresponds to a larger distinction between the distributions p α (a|t = 1) and p α (a|t = 0). Based on these definitions, we provide the objective of the FC.

A. The objective of the FC
Denote the vector of all measurements with Y = (Y 1 , . . . , Y N ) and its realization y = (y 1 , . . . , y N ), and the vector of stochastic trust values by α = (α 1 , . . . , α N ) and its realization by a = (a 1 , . . . , a N ). Let D 0 and D 1 be the decision regions at the FC. That is, (a, y) ∈ D 0 if the FC chooses hypothesis H 0 whenever it measures the pair (a, y). Similarly (a, y) ∈ D 1 if the FC chooses hypothesis H 1 whenever it measures the pair (a, y). To simplify our notations we denote D := {D 0 , D 1 }.
Denote by P FA and P MD the false alarm and missed detection probabilities of the decision rule used by the FC, 1 Example of a trust value αi: One example of such trust values comes from the works in [32], [30], [31]. In these works, the trust values αi ∈ [0, 1] are stochastic and are determined from physical properties of wireless transmissions. We use these trust values in our hardware experiment in Section IV where we discretize the sample space by letting A = {0, 1} and find the probability mass functions to be pα(ai = 1|ti = 1) = 0.8350 and pα(ai = 1|ti = 0) = 0.1691. Other examples of observations can be found in [27], [36], [37]. (6) In this case, the vector of trust values α would not affect the optimal decision rule, and it would only depend on the vector of measurements Y .
However, there are two main obstacles to the optimization of the probability of error (6), namely: 1) The FC does not know the identity of the malicious robots, and thus it does not know the correct vector t. Therefore, the FC needs to estimate the true trust vector, where the estimated trust vector is denoted byt. 2) The FC does not know how the malicious robots alter their measurements before sending them. In our setup, this means that the FC does not know the values P FA,M and P MD,M . Therefore the FC needs to estimate P FA,M and P MD,M , where the estimates are denoted byP FA,M andP MD,M , respectively.
The FC needs to make a decision with these unknown parameters which is known as the composite hypothesis testing problem. Since the minimization of (6) is not tractable, we explore different ways to circumvent this issue. One way is to start by estimating the legitimacy of the robots using trust values only and assuming that the upper bound on the number of malicious robots in the network is known in order to make (6) tractable. Then, we can ignore the measurements from robots deemed to be malicious and choose the decision regions D 0 and D 1 using the measurements from the remaining robots. This approach leads us to the formulation in Problem 1.
Problem 1. Assume that the FC first estimates the identities of the robots in the network, i.e., it determinest, solely using the vector of trust values α. Then, the FC makes a decision about the hypothesis using only the vector of measurements Y, from robots it identifies as legitimate.
Given an upper boundm on the proportion of malicious robots in the network, we wish to determine a strategy for the FC that minimizes the following worst-case scenario under these assumptions: The definition in Problem 1 requires an approach that estimates the trustworthiness of a robot i using only the trust value a i associated with that robot while assuming a known upper bound on the proportion of malicious robots. However, it is natural to seek additional information about the trustworthiness of the robots that can be obtained from the random measurement vector y. Following this intuition, we seek a decision rule that estimates the unknown parameters in the system which are t, P FA,M , and P MD,M as well as the hypothesis H 0 or H 1 jointly, without requiring any known upper bound on the proportion of malicious robots. A common approach to hypothesis testing with unknown parameters is to use the generalized likelihood ratio test [34], that is whereθ 1 is the maximum likelihood estimator (MLE) of the unknown parameter θ 1 assuming Ξ = 1 andθ 0 is the MLE of θ 0 assuming Ξ = 0. For our problem, z = (a, y), θ 1 = (t, P MD,M ), and θ 0 = (t, P FA,M ), which results in the following formulation of the test Note that in this setup the vector t is a parameter, thus, we do not make any prior assumption on its distribution. Calculating the MLE in the numerator and denominator in (9) is not trivial since the unknown t is a discrete multidimensional variable while P MD,M and P FA,M are continuous variables. Doing this in a tractable way leads us to the formulation in Problem 2.
Problem 2. Find a computationally tractable algorithm that calculates the GLRT given in (9).
In the next section we propose solutions to these problems. Then, we investigate the performance of both methods in Section IV, and conclude the paper in Section V.

III. APPROACH
In this section we present two different approaches: one approach to solve Problem 1 and another to solve Problem 2. The first approach, called the Two Stage Approach, finds the optimum decision rule that solves Problem 1. The second approach, called the Adversarial Generalized Likelihood Ratio Test (A-GLRT) uses both the trust values and measurements simultaneously to arrive at a final decision while estimating the unknown parameters using the maximum likelihood estimation rule. The A-GLRT approach addresses Problem 2. The Two Stage Approach is shown to be computationally faster than the A-GLRT, but the A-GLRT attains a lower empirical probability of error.

A. Two Stage Approach Algorithm
In this section we present an intuitive approach where we separate the detection scheme into two stages where 1) a decision is made about the trustworthiness of each individual robot i based on the received value α i , and then 2) only the measurements Y i from robots that are trusted are used to choose H 0 or H 1 .
a) Detection of Trustworthy Robots: We utilize the Likelihood Ratio Test (LRT) to detect legitimate robots. This test is guaranteed to have minimal missed detection probability (i.e., detecting a legitimate robot as malicious) for a given false alarm probability (i.e., detecting a malicious robot as legitimate) [34,Chapter 3].
The FC decides which robots to trust using the LRT decision rule where γ t is a threshold value that we wish to optimize. Note that when γ t = 1 (10) is equivalent to a maximum likelihood detection.
The FC decides who to trust and stores it in the vector t, wheret i = 1 if the FC chooses to trust the robot, and t i = 0 otherwise. In the case of equality a random decision is made where the FC choosest i = 1 with probability p t and the FC choosest i = 0 with probability 1 − p t , where p t is another parameter to be optimized. This leads to the following trust probabilities, where P trust,L (γ t , p t ) is the probability of trusting a legitimate robot, and P trust,M (γ t , p t ) is the probability of trusting a malicious robot: The error probability P e at the FC is affected by the trustworthiness classification. That is, if a legitimate robot i is classified as malicious the FC discards its measurement Y i , which increases the error probability since fewer measurements are used in the FC decision making. On the other hand, if a malicious robot is classified as legitimate it can increase the error probability by sending falsified measurements to the FC. For that reason, we look to optimize the trustworthiness classification to balance these two conflicting scenarios. Determining the best γ t and p t to minimize the overall error probability of the hypothesis detection by the FC is the main focus of this section.
b) Detecting the Event Ξ: To determine a hypothesis H on the event Ξ, the FC only considers the measurements it receives from robots that it classifies as legitimate in the first stage, i.e., i :t i = 1. Equivalently, the FC discards all the received measurements of robots it classifies as malicious. Then, the FC uses the following decision rule: where exp(γ TS ) is the exponential function with respect to γ TS , and it is a constant decision threshold. We set Pr(Ξ=1) = exp(γ TS ) so that when we take the logarithm in later expressions we can express the resultant decision threshold as γ TS for ease of exposition. This decision rule is commonly used in standard binary hypothesis testing problems where no malicious robots are present, and will be referred to as the standard binary hypothesis decision rule.
The standard binary hypothesis decision rule is optimal in a system with no malicious robots, i.e., M = ∅, and thus we attempt to approximate the standard binary hypothesis decision rule by first removing information from all robots deemed to be malicious. However, since there may be detection errors in the first stage which classifies legitimate and malicious robots, the threshold γ t and tie-break probability p t should balance the need to exclude malicious robots from participating in the test (12) with the need to allow legitimate robots to participate in the test (12) and contribute their truthful measurements to decrease the probability of error resulting from (12). In what follows we show how to optimize the threshold γ t and tie-break probability p t by first computing the probability of error of the FC using the Two Stage Approach.
Recalling the Neyman-Pearson Lemma [34], we have that (10) minimizes the missed detection probability for a desired false alarm probability of misclassifying robots. This false alarm probability dictates the value of the threshold γ t . After the FC discards robot measurements that it does not trust, the decision rule (12) leads to the following false alarm and missed detection error probabilities, Consequently, the overall error probability at the FC is: We seek to minimize the probability of error (15) for the decision rule (12) by minimizing the false alarm and missed detection probabilities. Any sequence of 0's and 1's can occur for the detected trust vectort, each yielding a different error probability, so the error probability must be calculated for each possible vectort, along with each possible vector y. Unfortunately, this computation scales exponentially with the number of robots, N . Furthermore, the true trust vector t and the probabilities of false alarm and missed detection of the malicious robots are unknown, i.e., P FA,M and P MD,M , therefore, they cannot be used in minimizing (15).
To this end, we derive analytical guarantees regarding the error probability of the overall detection performance of the two-stage approach as follows. We minimize the worst-case probability of error of the FC over all the possible trust vectors t ∈ {0, 1} N and false alarm and missed detection probabilities P FA,M and P MD,M , respectively, in the interval [0, 1]. Then, we minimize this worst-case error probability by choosing the best threshold γ t , i.e., choose γ t = γ * t and tie-break (16) To this end, we must first determine the P FA,M , P MD,M , t that maximize P e . In the remainder of this section, we assume that the proportion of malicious robots to expect in the network, denoted by m, is known, or we choose an upper bound for it (m). The proof of Lemma 1 can be found in Appendix A.
Lemma 2. Lett be the worst-case vector t, i.e., the vector t that maximizes the probability of error (15). If P FA,L < 0.5, P MD,L < 0.5, and P FA,M = P MD,M = 1, then the probability of error P e (γ t , p t ,t, 1, 1) is maximized whent contains the maximum number of malicious robots, i.e., i∈Nt i =mN .
Proof. By Lemma 1 the probability of false alarm and missed detection (13) are maximized when a robot is trusted and its measurement reports the wrong hypothesis (Y i = 1|H 0 or Y i = 0|H 1 ). Since the optimal policy for malicious robots is to report the wrong hypothesis with probability 1 (Lemma 1), any robot increases the false alarm and missed detection probability of the FC when it is malicious instead of legitimate. Thus, the probability of error P e (γ t , p t , t, 1, 1) is maximized when the proportion of malicious robots, m, is maximized, i.e., whent hasmN malicious robots, wherē m is the upper bound on the proportion of malicious robots in the network.
Utilizing Lemma 2, we calculate the exact probability of error for the FC for the worst-case attack where t =t and P FA,M = P MD,M = 1. In order to compute the probability of error exactly, we must compute the probability of false alarm and missed detection (13). Let k L ∈ K L be the number of legitimate robots trusted by the FC, where K L = {0, . . . , (1− m)N }. Similarly, let k M ∈ K M be the number of malicious robots trusted by the FC, where K M = {0, . . . ,mN }. Let S N represent the left side of the inequalities in (13) given by: Using the law of total probability, the false alarm probability at the FC is given by (17) Similarly, the probability of missed detection of the FC is given by (18) The probability of false alarm for a particular instantiation of k L and k M can be written as a function of the Binomial Cumulative Distribution Function: where F b (x; p, n) = x i=0 n i p i (1 − p) n−i is the Binomial Cumulative Distribution Function evaluated at x for n variables and success probability p. Similarly, for the probability of missed detection we have that Recall (11). We note that these probabilities depend on the distribution of the robot's vector of trust values a. Then, we have that where f b (x; p, n) = n x p x (1 − p) n−x is the Binomial probability distribution function evaluated at x for n variables and success probability p. Thus, the probability of false alarm and missed detection are Therefore, we have the total error probability P e (γ t , p t ,t, 1, 1) = Pr(Ξ = 0)P FA (γ t , p t ,t, 1)+ and we can choose the thresholds γ t and p t that minimize the expression. Once we have chosen the thresholds γ t and p t , the rest of the two stage approach becomes a standard binary hypothesis testing problem.

Lemma 3. Denote
Then, the minimal value of (16) with respect to γ t can be achieved by γ t ∈ Γ t .
Proof. The proof follows directly from the finiteness of the Compute P trust,L (γ t ,p t ), P trust,M (γ t ,p t ) by (11).
Algorithm 1 explains the two stage approach step-by-step. Algorithm 1 takes a set Γ t as input. Then, for eachγ t ∈ Γ t and eachp t ∈ Γ p we compute P trust,L (γ t ,p t ), P trust,M (γ t ,p t ), as well as P FA (γ t ,p t ,t, 1) and P MD (γ t ,p t ,t, 1). Then we compute the probability of error at the FC for the givenγ t andp t . Theγ t andp t that yields the minimum probability of error is then used in the decision rule in (10) to determine which robots to trust or not trust (vectort). Finally, we use the chosen vectort to make a decision using the standard binary hypothesis decision rule (12).
Determining the threshold value γ t and tie-break probability p t requires computing the probability of error |Γ t | · |Γ p | times, where |·| represents the cardinality of the set. However, this only needs to be computed once, and then the returned γ t and p t can be used to run each subsequent hypothesis test. With a given γ t and p t , the hypothesis test requires O(N ) comparisons.
Theorem 1. Assume that the FC uses the decision rule in (10) to detect malicious robots, and then uses the decision rule (12). Then Algorithm 1 chooses the threshold value γ t and tie-break probability p t that minimize the worst-case probability of error of the FC up to a discretization distance Proof. The goal is to minimize the worst-case probability of error of the FC, i.e., LetP e be the worst-case probability of error computed using the worst-case probability of false alarm and missed detection from (22). Furthermore, lett be the worst-case vector t. Using the results from Lemmas 1, 2 and (22) we upper bound the error probability using the worst-case error probability: The equality in the first line directly follows from Lemma 1. The second line follows from the first by inserting the worstcase vector t as the one that maximizes the probability of error P e (Lemma 2). Additionally, by Lemma 3, it is sufficient to optimize γ t over the set Γ t . Now, since we optimize p t using a line search, we may not necessarily find an optimal pair (γ * t , p * t ). However, we can upper bound the distance from the optimal solution for the worst case scenario by: For every fixed γ t , the function P e (γ t , p t ,t, 1, 1) is a polynomial function of p t , therefore, it is continuous in p t (over the interval p t ∈ [0, 1]). Consequently, d(δ p ) → 0 as δ p → 0.

B. A-GLRT Algorithm
The main purpose of this section is to construct an efficient algorithm that implements the GLRT in (9). We can simplify (9) by recalling that given the true trustworthiness of a robot t i and the true hypothesis H, the trust value α i and the measurement Y i are statistically independent. Thus, We choose γ AG = Pr(Ξ=0) Pr(Ξ=1) since we do not assume anything about the the prior distribution of t. The challenging part of using the GLRT in this problem is calculating the maximum likelihood estimations for both numerator and denominator. The unknown t is a discrete multidimensional variable while P MD,M and P FA,M are continuous variables restricted to the domain [0, 1]. Therefore, calculating the MLE is not trivial. The main purpose of this section is to construct an efficient algorithm that implements the GLRT. Due to the symmetry in calculation of the numerator and denominator in (30), we focus our discussion on the calculation of the numerator.
Using Assumption 1 about the trust values, we obtain the following formulation of Pr(a|t): Additionally, we obtain the following equations using the i.i.d assumption about measurements: Using these equations, we write the numerator as: Since the optimization problem over variables t and P MD,M at the same time is difficult we can reformulate the problem as two nested optimizations using the Principle of Iterated Suprema [38, p. 515], that is: where f : Z × W → R, and Z, W ⊆ R d . By the Principle of Iterated Suprema we can calculate the maximization in (8) in two different ways. We rewrite the maximization problem in (33) as: (34) With this formulation, one possible way to calculate the maximization is iterating over all vectors t in the set {0, 1} N ; then for each t, calculating the inner maximization. We show how to calculate this maximization in the following lemma.
it follows that ( Note, that this estimator is equal to the empirical missed detection probability of the measurements sent by the malicious robots. Finally, it is easy to validate that if |{i : t i = 0}| = 0, any choice P MD,M ∈ [0, 1] maximizes (35).
Unfortunately, since the set {0, 1} N exponentially with the number of robots in the network, this approach is computationally intractable for large robot networks. Therefore, we look for an alternative solution. Another equivalent formulation of the maximization problem that is obtained by the Principle of Iterated Supremum is where the order of variables that the maximization is taken over is flipped. Since the variable P MD,M belongs to an uncountably infinite set, it is impossible to perform the maximization with this formulation. However, assuming that we have a given P MD,M , the inner maximization can still be calculated. The following lemma shows how to calculate the inner maximization. Proof. First, we reformulate (35) as: where the product is calculated by going through all robots rather than going through legitimate and malicious robots separately. We define Then, the expression in (38) becomes: Let 0 log 0 = 1, thus 0 0 = 1. Then, the expression (39) is maximized when choosing t i = 1 if c L,i ≥ c M,i and t i = 0 otherwise.
As we can see from Lemma 5, maximization with this formulation can be calculated by performing O(N ) comparisons. Now, we consider these two perspectives together to introduce an efficient calculation of the numerator of the GLRT given in (33). By Lemma 4, we can see that the optimum value of P MD,M has a special structure. Exploiting this knowledge, we can restrict the set that P MD,M belongs to in (37). Then, the inner maximization can be calculated using Lemma 5. The following theorem builds on this intuition to provide an efficient calculation of (33). Proof. First, we will approach the problem by rewriting it as (37) using the Principle of Iterated Suprema: By Lemma 5, we can calculate the inner maximization for a given P MD,M . Notice that, since the calculation requires a comparison for each robot, O(N ) comparisons need to be performed for this maximization. Now, consider the other formulation of the problem given by (34). From Lemma 4, we can see that the optimum P MD,M only depends on the number of ones and zeros of malicious robots for a given t. Moreover, the permutation of ones and zeros of malicious robots for a given t does not change the optimum and only the total number of ones and zeros does. We will restrict the set that the outer maximization process iterates over in (37) based on this observation. Denote Now, using Theorem 2, we introduce the algorithm A-GLRT, which makes a decision based on the GLRT given by (30). Finally, we investigate how the measurements y and stochastic trust values α are being used by the A-GLRT algorithm. Considering (38), an equivalent decision rule to the one derived in Lemma 5 is given as: With this new perspective, we can gain more insights about the A-GLRT. First, we can see that the A-GLRT is essentially performing a likelihood ratio test with α values for each robot to decide if they are legitimate or not using different threshold values based on the measurement coming from that robot. For now, let's assume that P MD,M is not 0 or 1. Then, we can see that as α values become more accurate, meaning that the ratio pα(ai|ti=1) pα(ai|ti=0) approaches infinity if t i = 1 or approaches zero otherwise, for all values that α i can take, the finite threshold value becomes insignificant and the decision is made using α values only. This situation agrees with the intuition as well since α values would become true indicators of robot identities.

IV. HARDWARE EXPERIMENT AND NUMERICAL RESULTS
We perform a hardware experiment with robotic vehicles driving on a mock-up road network where robots are tasked with reporting the traffic condition of their road segment to a FC. The objective of the malicious robots is to cause the FC  Set l num = l num · c L,i . Return decision H 0 25: end if to incorrectly perceive the traffic conditions (see Fig. 2). A numerical study further demonstrates the performance of this scenario with an increasing proportion of malicious robots.
We compare the performance of the 2SA and A-GLRT against several benchmarks including the Oracle, where the FC knows the true trust vector t and discards malicious measurements, (this serves as a lower bound on the probability of error), the Oblivious FC, where the FC treats every robot as legitimate, and a Baseline Approach [26] where the FC uses a history of T measurements to develop a reputation about each robot. The Baseline method ignores information from robots whose measurements disagree with the final decision at least η < T times. The Oracle, Oblivious FC, and Baseline Approach use the decision rule in (12). Malicious robots perform a Sybil attack where they spoof additional robots into the network. We use the opensource toolbox in [40] to obtain trust values from communicated WiFi signals by analyzing the similarity between different fingerprints to detect spoofed transmissions. The works in [32], [30], [31] model these trust values α i ∈ [0, 1] as a continuous random variable. We discretize the sample space by letting A = {0, 1} and setting a i = 1 if the measured trust value is ≥ 0.5 and a i = 0 otherwise. As the robots drive between points A and B they are given noisy position information for themselves and neighboring robots from an OptiTrack motion capture system with added white Gaussian noise with a variance of 1m 2 . This serves as a proxy for GPS-reported measures used in crowdsourcing traffic estimation schemes like Waze, Google Maps, and others. A road segment is considered to have traffic (y i = 1) if the number of robots on the segment is ≥ 2. Of the 11 robots in the group, 5 robots are legitimate, 3 are malicious, and 3 are spoofed by the malicious robots (making them also malicious). Malicious robots know the true traffic conditions and report the wrong measurement with probability 0.99, i.e., P FA,M = P MD,M = 0.99. The empirical data from the experiment is stated in Table I, where Baseline1 and Baseline5 refer to the Baseline Approach from [26] with parameters T and η set to (T = 1, η = 0.5) and (T = 5, η = 2.5). We determined the parameters in Table I by first running an experiment without performing hypothesis tests and observing the behavior of the system compared to ground truth. The trust values gathered using the toolbox in [40] led to the empirical probabilities p α (a i = 1|t i = 1) = 0.8350 and p α (a i = 1|t i = 0) = 0.1691 (see Fig. 3).
In our hardware experiment the 2SA and A-GLRT outperform the Oblivious FC and the Baseline Approach. The Baseline Approach exhibits a high percent error due to the fact that it relies on the majority of the network being legitimate. Since 6 out of 11 robots are malicious, it is likely that many hypothesis tests are conducted where the majority is malicious. This points to a common vulnerability of reputation based approaches that assume only a small proportion of the network is malicious. Empirical distribution of the trust values gathered during the hardware experiment for legitimate and malicious robots. The trust value is thresholded to a = 1 if it is ≥ 0.5, and a = 0 otherwise. b) Numerical Study: Next, we perform a numerical study on the performance of each approach when the proportion of malicious robots is varied. In the numerical study we use N = 10 robots with Pr(Ξ = 0) = Pr(Ξ = 1) = 0.5, P FA,L = P MD,L = 0.15, and P FA,M = P MD,M = 0.99 and perform hypothesis tests over 1000 trials for each proportion of malicious robots. In the simulation study the trust value distributions are fixed at p α (a i = 1|t i = 1) = 0.8, p α (a i = 1|t i = 0) = 0.2, and the proportion of malicious robots varies from 0 to 1. The results of the simulation study are plotted in Fig. 4. From the plot it can be seen that the 2SA and the A-GLRT perform well even after the number of malicious robots exceeds majority since they use additional trust information independent of the data, whereas the Baseline Approaches fail since they use only the data to assess the trustworthiness of the robots. Additionally, there exists a critical proportion of malicious robots, beyond which the 2SA chooses to ignore most of the measurements it receives and the decision rule becomes more dependent on the prior probabilities Pr(Ξ = 0) and Pr(Ξ = 1).

V. CONCLUSION
In this paper we present two methods to utilize trust values in solving the binary adversarial hypothesis testing problem. The 2SA uses the trust values to determine which robots to trust, and then makes a decision from the measurements of the trusted robots. The A-GLRT jointly uses the trust values and measurements to estimate the trustworthiness of each robot, the strategy of malicious robots, and the true hypothesis. Proof. Recall the false alarm and missed detection probabilities for the FC using decision rules (10) and (12) that lead to the overall false alarm and missed detection probabilities stated in (13).
Next, we show that the false alarm probability (13) is maximized when P FA,M = 1. The proof for P MD,M is analogous. In order to maximize P FA in (13) the summation must be maximized. We rewrite the summation by separating it into the terms affected by legitimate robots that were trusted and those affected by malicious robots that were trusted Any robot j ∈ {L ∩ M} can maximize (41) by maximizing [w 1,L y j − w 0,L (1 − y j )]. Note that when P FA,L < 0.5 and P MD,L < 0.5 then w 1,L > 0 and w 0,L > 0. Thus, [w 1,L y j − w 0,L (1 − y j )] is maximized when y j = 1 since Y j ∈ {0, 1}. Given the true hypothesis is H 0 , the measurement Y j = 1 occurs when robot j reports a false alarm. Therefore, the probability that robot j reports Y j = 1 is maximized when the probability of false alarm is maximized: Pr(Y j = 1|H 0 ) = P FA,M = 1. (42)