# Secure Localization in the Presence of Colluders in WSNs
## 4 Super Cross-Check (SCC) Algorithm  
Algorithm 1 outlines the steps of _super cross-check_ (SCC). It assumes a sensor node \(A\) that executes two main processes. First, it tries to compute a consistent position in the system by requesting the position of every location-known sensor node in its neighbourhood Then, it labels its neighbours as either truth-tellers or colluders. The main steps to identify the colluders are the following. Once node \(A\) computes its position, it creates a cross-check list (\(CCL\)) for every neighbour in \(\mathcal{K}\). Then, node \(A\) exchanges its \(CCL\) with those sensor nodes in its communication range, in order to identify colluders. Upon request, every neighbour of \(A\) sends out its \(CCL\). Only colluders would send \(CCL\)s with wrong information (with respect to the truthful information provided by the truth-tellers). For example, a colluder may purposely include false positions about nodes that should have been excluded from its \(CCL\). If enough colluders collectively report exactly the same information, then node \(A\) will be deceived. The attack can be detected by using a traditional voting technique. Upon receiving a \(CCL\) from each neighbour, \(A\) computes for every neighbour either positive and negative scores. If a neighbour received two more positive scores than negative scores, then \(A\) concludes that such a node is a truth-teller. Otherwise, the node would be labelled as a colluder. In Figure 2 we provide a detailed example illustrating how algorithm SCC works. ```
1:repeat
2:// sensor \(A\) requests the location of all its neighbours and computes the point of
3:// intersection \((x_{t},y_{t})\) for each triplet \(t\) of nodes \(B_{i}\), \(B_{j}\), \(B_{k}\) in its neighbourhood;
4:until a consistent position is derived from the majority of triplets;
5:Once the above process returns a consistent position
6:// sensor \(A\) accepts \((x_{t},y_{t})\) as its position in the system, adds every triplet
7:// (\(B_{i}\); \(B_{j}\); \(B_{k}\)) in agreement with \((x_{t},y_{t})\) to its cross-check list (CCL), and
8:// broadcasts both its location \((x_{t},y_{t})\) and its CCL to all its neighbours;
9:repeat
10:// sensor \(A\) requests the CCL of each neighbour and includes the information in a set \(K\);
11:until all the neighbours of \(A\) are processed
12:for each node in \(K\) whose communication circle intersects with \(A\)do
13:if the node is reported in both the CCL of \(A\) and the CCL of \(A\)'s neighbours then
14:// the node gets a positive score;
15:else
16:// the node gets a negative score;
17:endif
18:endfor
19:for each node in \(K\) whose communication circle intersects with \(A\)do
20:if the node has twice positive scores than negative scores then
21:// the node is labelled as a truth-telling node
22:else
23:// the node is labelled as a colluder
24:endif
25:endfor
```  
**Algorithm 1** Super cross-check (SCC)  
Figure 2: Detailed example: (**a**) In this example, sensor \(A\) has four neighbours, i.e., \(\mathcal{K}\) contains \(B_{1}\), \(B_{2}\), \(B_{3}\) and \(B_{4}\). For \(i=1\), \(2\), \(3\), \(4\), sensor \(A\) (\(1\)) requests and gets the location \((x_{i},y_{t})\) of every neighbour \(B_{i}\); and (\(2\)) derives each self-to-neighbour \(B_{i}\) distance. (**b**) Using the location of every neighbour \(B_{i}\) and distance (\(d(B_{i},A)\)), a disc is calculated (\(d_{B_{i}}\)). Here this is shown for neighbour \(B_{1}\). (**c**) For each possible triplet \(t\) over the set of discs obtained in (**b**), calculate the intersection point \((x_{t},y_{t})\) of this triplet of discs. This is shown here for \(t\) equal to \(\{B_{2},B_{3},B_{4}\}\). In this example, there are four possible combinations of three, that is, four triplets. Assuming here that all neighbours are truth-tellers and mutually within communication range, they will be all in agreement (up to this point: Lines 1 to 4 of Algorithm 1). The CCL of \(A\) contains \(B_{1},B_{2},B_{3}\) and \(B_{4}\), and their coordinates (Lines 6 to 8 of Algorithm 1).