1.0. Introduction

Delay-Tolerant Security Key Agreement, or DTKA, is an ION-compatible module for security key administration in DTN prototyped by the Jet Propulsion Laboratory (JPL) at CalTech for NASA.
A high-level overview of DTKA can be read in this document: ^{http://apps.topcoder.com/wiki/download/attachments/143950053/Delay-Tolerant+Key+Administration+cleared.pptx}

As part of the modifications we'll be making to DTKA, we would like to prototype a proof of concept that demonstrates that, after a few key exchanges, the Key Authority (KA) servers in a DTN network are able to determine with some accuracy, the malicious nodes in the network that should be blacklisted before the next key exchange round.

This guide will outline instructions on how to implement the Iterative Reputation and Trust Management (ITRM) algorithm that will be added to DTKA to keep track of the trustworthiness or otherwise of new nodes that join a DTN network.

2.0. Related Literature

An Iterative Algorithm for Trust Management and Adversary Detection for Delay-Tolerant Networks. Erman Ayday, Student Member, IEEE, and Faramarz Fekri, Senior Member, IEEE

https://documents.epfl.ch/users/a/ay/ayday/www/erman_publications/tmc12.pdf

3.0. Algorithm

3.1. ITRM Algorithm Explanation

Initially the network has one first node N1 and by assumption it is trustful node (even this assumption can be wrong and will be discovered by iterative process later). This node belongs to trusted nodes in bipartite graph. The second node N2 is market as not-trusted at the beginning. There is a vertex between N1 and N2 with weight V12. Node N1 has a rating V1, node N2 has a rating V2, node N1 rate node N2 with V12 rating and node N2 rate N1 with rating V21.

Given that each node Ni rated other nodes Nj with rating values V(ij) let us compute rating of the node Nj. Plus, Vi means the rating of trust for node Ni and Vj means the rating of trust for node Nj. Each node as a rater corresponds to a check vertex in the graph. If a node Ni has rating for Nj, the edge has weight edge with value Vij from the Ni vertex to Nj vertex.

Vj = ∑(Vi*Vij)/∑Vi, (i=I,N; i!= j)                 (1)

where N number of all nodes in trusted DTN.

There is another formula to calculate inconsistency coefficient for each node Ni as Ci:

Ci = (1/[T])* ∑dist(Vij,Vj),            (2)

Where sum is for every j of Nj from set T, dist is a distance metrics, [T] is size of set of all nodes connected with node Ni.

A node creates its own rating about another node by collecting ratings about the node and aggregating them. Each node has rating table, whose entries are used for storing the ratings of the nodes. In DTN a node has to wait for a very long time to issue its own ratings for all the nodes in the network.  However, it is desirable for a node to have a fresh estimate of the reputation of all the nodes in the network in a timely manner, mitigating the effects of malicious nodes immediately. To achieve this goal, I propose an iterative detection mechanism, which operates by using the rating tables formed by other nodes. The rating table of a node can be represented by a bipartite graph consisting one check vertex and some bit vertices (a subset of all nodes in DTN for which the node has received big number of feedbacks to form a rating).

How to detect malicious node using ITRM? Check vertex Ni with the highest inconsistency coefficient Ci (calculated by formula 2) is selected and put to the blacklist if its inconsistency is greater than or equal to pre-definite threshold. If there is no check vertex with inconsistency greater than or equal to pre-defined threshold, the algorithm stops its iterations. Once the check vertex Ni is put to the blacklist, its rating Vi (calculated by formula 1) is deleted for all vertices Nj it is connected to:
{Vij}

Please refer to the spec for more details: http://apps.topcoder.com/wiki/download/attachments/146767909/ITRM.docx

3.2. Class Diagram

This assembly will build a proof of concept implementation of the Iterative Trust and Reputation Management (ITRM) algorithm to isolate malicious nodes in a network of connected nodes.

Please refer to the attached TC UML diagram for the classes in scope for this assembly. http://apps.topcoder.com/wiki/download/attachments/146767909/dtka_diagrams.tcuml

3.3. Testing

Your submission must demonstrate that after a few runs of the ITRM algorithm, the rating values of non-malicious nodes converge to a value that asserts that such nodes are not malicious. Of course, your implementation of the algorithm should equally demonstrate with a certain degree of accuracy that the ITRM algorithm is able to identify nodes that are malicious by allowing the rating of such nodes to fall below the trustworthiness threshold.

The following example is for illustration though in practice, the number of malicious nodes will usually not be as high as half the number of nodes in the network.
 
There are 3 KA servers named KA1 - KA3.
There are 6 nodes which are named n1 - n6.
Let's assume that only nodes 1, 2 and 6 are trustworthy, the others (3, 4 and 5) are malicious.

Assuming that inconsistency coeff (i.c.) ranges from 0 - 1 and a node is considered malicious when its i.c. drops below 0.5, and that when a node contacts a KA server for key exchange for the first time, the KA server assigns it an i.c of 0.5 (but in my example below the value is chosen at random), then the inconsistency coeff of nodes 1 - 6 at each server are as follows:

Round 1 KA1: 0.5, 0.6, 0.1, 0.3, 0.5, 0.9 KA2: 0.9, 0.5, 0.3, 0.1, 0.6, 0.5 KA3: 0.1, 0.1, 0.2, 0.3, 0.2, 0.1
Round 2 KA1: 0.6, 0.8, 0.2, 0.1, 0.4, 0.8 KA2: 0.7, 0.7, 0.3, 0.1, 0.6, 0.6 KA3: 0.4, 0.3, 0.2, 0.3, 0.2, 0.5
Round 3 KA1: 0.8, 0.7, 0.1, 0.3, 0.5, 0.8 KA2: 0.9, 0.6, 0.3, 0.1, 0.6, 0.6 KA3: 0.6, 0.6, 0.2, 0.3, 0.2, 0.5

By round 3, the values of nodes 1, 2 and 6 converge above 0.5 across the 3 KA servers showing that they are not malicious nodes.
 

4. Submission Deliverables

You are free to develop your implementation in any of the programming languages listed in the contest spec (C, C++, C#, Java, Python, or Node.js JavaScript).

With the exception of solutions coded in C, you must structure your code using object oriented techniques.

• Your final submission must include all necessary files required to run the code, including IDE project files.
• Your test output. Can be a simple text file containing the piped output from executing the app from the console.
• A detailed deployment guide describing all the steps required to test the solution successfully.

5. Support

All standard terms governing assembly contests including support applies to this contest.

Final Submission Guidelines

Allowed programming languages: C, C++, C#, Java, Python or JavaScript (Node.js).

1. Submission Upload - For each member, the final submission should be uploaded via the challenge detail page on topcoder.com.

2. Third Party Code/Libraries - All third party code/libraries must be open source and you must include the license in your submission. The license must allow us to modify/re-package the code as necessary. If you have any questions regarding this, please post in the forums. Submissions that include third party code without the proper license information will be disqualified if the third party code is found to be non-usable due to license restrictions.

3. Attribution/References- You must properly attribute and or reference any sentences, paragraphs or quotes that you cite in your text-based submission. If your submission is found to include text that has been copied and pasted from an online source without properly attributing the source, you will receive a not-so-nice email from the topcoder competition manager.

4. Spell Check - We understand that not all submitters will be native English speakers and that there will be spelling/grammatical mistakes. We request that you first run your submission through a grammar/spell checker before submission so as to fix simple mistakes.