Copyright © 2014 by Intelligent Systems Laboratory, Computer Science Department, Technion - Israel Institute of Technology, Haifa 3200003, Israel. All rights reserved


TheGrue.org

Network Vaccination Simulator

Network Vaccination Simulator

By: Sagi Ben Moshe

Instructor: Yaniv Altshuler

This simulation attempts to test a simple model of the Vaccination Algorithm against the state of the art algorithm of message flooding.

 

 General

The framework of this work assumes a network (modeled as a graph), at which threats (representing computer viruses or other malicious pieces of software) try to spread. We assume that each member of the network is equipped with a monitoring capability. Namely – it can select an application that is installed on it, and monitor it for some time. This monitoring process can identify whether this application is malicious or not (with some false positive and false negative error probabilities). Once a network member becomes aware of the fact that a given application is malicious, it is "vaccinated" against it. This means that if the application is installed on this device, it uninstalls it. Alternatively – if the application is not installed, should this device encounter it in the future, it will recognize it as malicious and will not install it.


The naïve way of vaccinating a network is therefore to let each and every network member sequentially selects each of the applications which are installed in it, and monitor them. Also, when becoming aware of such a malicious application, a device can flood the network with this information. This is likely to achieve a fast vaccination of every network member against every possible device. However, this will also be very expensive (a lot of expensive monitoring processes, and a lot of messages transmitted across the network).


The solution is therefore to form a collaborative system – devices will occasionally perform monitoring, and will send the information to some of the network's members. Calibrating this mechanism correctly will yield an efficient and cheap solution. Also, such a system should cope with two kinds of threats – · Malicious applications may spread across the network, and we would like not only to complete an efficient vaccination process, but also to minimize the number of infected network's members. · Adversaries may attack the vaccination mechanism itself. For example – transmitting messages that some application (which is not malicious) is in fact – malicious. We want to show that we are robust against such attacks. We will also compare our mechanism with state of the art information propagation mechanisms. We want to show that we are the most efficient \ cost-efficient.


Algorithm

Each unit may or may not have a malicious application on startup, depending on the parameter P. All units start as unsafe. The simulation runs until the percent of unsafe applications goes below the vaccination threshold, pMax.


In each cycle, each unsafe unit that has a malicious application is tested with probability pT. One of the applications is selected randomly. If it is found as malicious, with probability of 1-Enegative, the unit is marked as safe and messages are sent to other units. If no application is selected for testing this cycle, the number of applications is decremented. In the state of the art algorithm, a message is sent with probability pSend. In the vaccination algorithm, a message is sent to each friend.


When a message is received, if the threshold Rho is reached, the unit is marked safe. In the vaccination algorithm, if TTL is positive, the message is sent on to one other friend, with a decremented TTL, while in the state of the art algorithm, the message is sent to each friend with probability pSend.


Execution

YProject can be executed in two ways:
1. Manually
The parameters are entered in response to prompts on screen and the output is directed to the screen.
2. Batch Mode
YProject.exe < in.txt > out.txt where in.txt is a file containing the parameters, one on a line, in the order of the prompts, and out.txt is the output file.

Input Parameters

n Number of units in the network
N Number of applications on a unit
pT Probability to perform a test in each time step
Rho Adversaries threshold
P Probablity of possessing a malicious application
pMax Threshold for vaccination
Epsilon Probability for unsuccessful vaccination
Enegative False negative probablity in application testing
TTL TTL: -1, -2 – use 1st or 2nd formulas respectively. >0 – specific TTL value.
fModal

Friends Modal

1 – small distance geographic graph
2 – bidirectional random graph
3 – directed random graph
4 – fixed number random graph

Modal

Algorithm
0 – State of the art
1 – Vaccination

pSend Probability for sending notification
Debug Debug Mode (0,1)
Distance Distance, for fModal=1
Pn Probability, for fModal=2,3
nFriends Number of friends, for fModal=4

Running Examples

Example no. 1 :


Input file, containing the parameters :
1000
100
0.1
30
.1
0.005
0.001
0.001
-1
310
.3
00
.05


Output file :


Number of units in the network (n) =>
Number of application installed on a unit (N) =>
Probability to perform a test in each timestamp (pT) =>
Adversaries threshold (RHO) =>
Probability of possessing a malicious application (P) =>
PMAX =>
Epsilon =>
False negative probability (E Negative) =>
TTL (-2,-1,...) =>
Friends Modal (1..4) =>
Modal (0 - State of the art,1 - Vaccination) =>
PSend =>
Debug Mode (0,1) =>
Pn =>
TTL = 527


Round 1;Calc Percent 1;Cycle Sent 0;Cycle Recv 0;
Round 2;Calc Percent 1;Cycle Sent 0;Cycle Recv 0;
Round 3;Calc Percent 0.999;Cycle Sent 51;Cycle Recv 0;
Round 4;Calc Percent 0.999;Cycle Sent 55;Cycle Recv 55;
Round 5;Calc Percent 0.999;Cycle Sent 88;Cycle Recv 88;
Round 6;Calc Percent 0.998;Cycle Sent 136;Cycle Recv 87;
Round 7;Calc Percent 0.998;Cycle Sent 240;Cycle Recv 240;
Round 8;Calc Percent 0.998;Cycle Sent 216;Cycle Recv 216;
Round 9;Calc Percent 0.998;Cycle Sent 208;Cycle Recv 208;
Round 10;Calc Percent 0.998;Cycle Sent 203;Cycle Recv 203;
Round 11;Calc Percent 0.996;Cycle Sent 286;Cycle Recv 193;
Round 12;Calc Percent 0.95;Cycle Sent 371;Cycle Recv 371;
Round 13;Calc Percent 0.893;Cycle Sent 390;Cycle Recv 390;
Round 14;Calc Percent 0.797;Cycle Sent 389;Cycle Recv 389;
Round 15;Calc Percent 0.708;Cycle Sent 390;Cycle Recv 390;
Round 16;Calc Percent 0.639;Cycle Sent 381;Cycle Recv 381;
Round 17;Calc Percent 0.586;Cycle Sent 369;Cycle Recv 369;
Round 18;Calc Percent 0.519;Cycle Sent 393;Cycle Recv 393;
Round 19;Calc Percent 0.447;Cycle Sent 382;Cycle Recv 382;
Round 20;Calc Percent 0.399;Cycle Sent 382;Cycle Recv 382;
Round 21;Calc Percent 0.344;Cycle Sent 375;Cycle Recv 375;
Round 22;Calc Percent 0.297;Cycle Sent 407;Cycle Recv 407;
Round 23;Calc Percent 0.256;Cycle Sent 385;Cycle Recv 385;
Round 24;Calc Percent 0.226;Cycle Sent 374;Cycle Recv 374;
Round 25;Calc Percent 0.188;Cycle Sent 380;Cycle Recv 380;
Round 26;Calc Percent 0.172;Cycle Sent 388;Cycle Recv 388;
Round 27;Calc Percent 0.147;Cycle Sent 401;Cycle Recv 401;
Round 28;Calc Percent 0.128;Cycle Sent 391;Cycle Recv 391;
Round 29;Calc Percent 0.111;Cycle Sent 408;Cycle Recv 408;
Round 30;Calc Percent 0.098;Cycle Sent 365;Cycle Recv 365;
Round 31;Calc Percent 0.085;Cycle Sent 396;Cycle Recv 396;
Round 32;Calc Percent 0.075;Cycle Sent 396;Cycle Recv 396;
Round 33;Calc Percent 0.064;Cycle Sent 394;Cycle Recv 394;
Round 34;Calc Percent 0.056;Cycle Sent 383;Cycle Recv 383;
Round 35;Calc Percent 0.044;Cycle Sent 400;Cycle Recv 400;
Round 36;Calc Percent 0.036;Cycle Sent 381;Cycle Recv 381;
Round 37;Calc Percent 0.031;Cycle Sent 392;Cycle Recv 392;
Round 38;Calc Percent 0.027;Cycle Sent 388;Cycle Recv 388;
Round 39;Calc Percent 0.023;Cycle Sent 396;Cycle Recv 396;
Round 40;Calc Percent 0.02;Cycle Sent 376;Cycle Recv 376;
Round 41;Calc Percent 0.018;Cycle Sent 380;Cycle Recv 380;
Round 42;Calc Percent 0.014;Cycle Sent 377;Cycle Recv 377;
Round 43;Calc Percent 0.013;Cycle Sent 381;Cycle Recv 381;
Round 44;Calc Percent 0.01;Cycle Sent 418;Cycle Recv 418;
Round 45;Calc Percent 0.009;Cycle Sent 383;Cycle Recv 383;
Round 46;Calc Percent 0.007;Cycle Sent 384;Cycle Recv 384;
Round 47;Calc Percent 0.006;Cycle Sent 379;Cycle Recv 379;
Round 48;Calc Percent 0.004;Cycle Sent 386;Cycle Recv 386;
Msgs Sent 15794
Msgs Recv 15601


Example no. 2 :


Input file, containing the parameters :
1000
100
0.1
30
.1
0.01
0.001
0.001
-1
310
.3
00
.05


Output file :


Number of units in the network (n) =>
Number of application installed on a unit (N) =>
Probability to perform a test in each timestamp (pT) =>
Adversaries threshold (RHO) =>
Probability of possessing a malicious application (P) =>
PMAX =>
Epsilon =>
False negative probability (E Negative) =>
TTL (-2,-1,...) =>
Friends Modal (1..4) =>
Modal (0 - State of the art,1 - Vaccination) =>
PSend =>
Debug Mode (0,1) =>
Pn =>
TTL = 375
Round 1;Calc Percent 1;Cycle Sent 0;Cycle Recv 0;
Round 2;Calc Percent 1;Cycle Sent 0;Cycle Recv 0;
Round 3;Calc Percent 1;Cycle Sent 0;Cycle Recv 0;
Round 4;Calc Percent 0.999;Cycle Sent 41;Cycle Recv 0;
Round 5;Calc Percent 0.999;Cycle Sent 56;Cycle Recv 56;
Round 6;Calc Percent 0.999;Cycle Sent 93;Cycle Recv 93;
Round 7;Calc Percent 0.999;Cycle Sent 77;Cycle Recv 77;
Round 8;Calc Percent 0.999;Cycle Sent 80;Cycle Recv 80;
Round 9;Calc Percent 0.999;Cycle Sent 75;Cycle Recv 75;
Round 10;Calc Percent 0.999;Cycle Sent 93;Cycle Recv 93;
Round 11;Calc Percent 0.999;Cycle Sent 82;Cycle Recv 82;
Round 12;Calc Percent 0.999;Cycle Sent 84;Cycle Recv 84;
Round 13;Calc Percent 0.999;Cycle Sent 74;Cycle Recv 74;
Round 14;Calc Percent 0.999;Cycle Sent 90;Cycle Recv 90;
Round 15;Calc Percent 0.999;Cycle Sent 78;Cycle Recv 78;
Round 16;Calc Percent 0.999;Cycle Sent 68;Cycle Recv 68;
Round 17;Calc Percent 0.999;Cycle Sent 82;Cycle Recv 82;
Round 18;Calc Percent 0.999;Cycle Sent 84;Cycle Recv 84;
Round 19;Calc Percent 0.999;Cycle Sent 75;Cycle Recv 75;
Round 20;Calc Percent 0.999;Cycle Sent 83;Cycle Recv 83;
Round 21;Calc Percent 0.999;Cycle Sent 81;Cycle Recv 81;
Round 22;Calc Percent 0.999;Cycle Sent 83;Cycle Recv 83;
Round 23;Calc Percent 0.998;Cycle Sent 119;Cycle Recv 80;
Round 24;Calc Percent 0.997;Cycle Sent 183;Cycle Recv 131;
Round 25;Calc Percent 0.989;Cycle Sent 272;Cycle Recv 272;
Round 26;Calc Percent 0.969;Cycle Sent 277;Cycle Recv 277;
Round 27;Calc Percent 0.94;Cycle Sent 279;Cycle Recv 279;
Round 28;Calc Percent 0.92;Cycle Sent 239;Cycle Recv 239;
Round 29;Calc Percent 0.884;Cycle Sent 249;Cycle Recv 249;
Round 30;Calc Percent 0.836;Cycle Sent 340;Cycle Recv 291;
Round 31;Calc Percent 0.76;Cycle Sent 328;Cycle Recv 328;
Round 32;Calc Percent 0.686;Cycle Sent 339;Cycle Recv 339;
Round 33;Calc Percent 0.604;Cycle Sent 357;Cycle Recv 357;
Round 34;Calc Percent 0.533;Cycle Sent 346;Cycle Recv 346;
Round 35;Calc Percent 0.469;Cycle Sent 367;Cycle Recv 367;
Round 36;Calc Percent 0.4;Cycle Sent 364;Cycle Recv 364;
Round 37;Calc Percent 0.344;Cycle Sent 368;Cycle Recv 368;
Round 38;Calc Percent 0.302;Cycle Sent 359;Cycle Recv 359;
Round 39;Calc Percent 0.265;Cycle Sent 355;Cycle Recv 355;
Round 40;Calc Percent 0.235;Cycle Sent 371;Cycle Recv 371;
Round 41;Calc Percent 0.198;Cycle Sent 373;Cycle Recv 373;
Round 42;Calc Percent 0.165;Cycle Sent 380;Cycle Recv 380;
Round 43;Calc Percent 0.142;Cycle Sent 371;Cycle Recv 371;
Round 44;Calc Percent 0.122;Cycle Sent 374;Cycle Recv 374;
Round 45;Calc Percent 0.106;Cycle Sent 350;Cycle Recv 350;
Round 46;Calc Percent 0.09;Cycle Sent 354;Cycle Recv 354;
Round 47;Calc Percent 0.073;Cycle Sent 370;Cycle Recv 370;
Round 48;Calc Percent 0.063;Cycle Sent 364;Cycle Recv 364;
Round 49;Calc Percent 0.054;Cycle Sent 371;Cycle Recv 371;
Round 50;Calc Percent 0.045;Cycle Sent 361;Cycle Recv 361;
Round 51;Calc Percent 0.038;Cycle Sent 360;Cycle Recv 360;
Round 52;Calc Percent 0.031;Cycle Sent 374;Cycle Recv 374;
Round 53;Calc Percent 0.026;Cycle Sent 347;Cycle Recv 347;
Round 54;Calc Percent 0.024;Cycle Sent 371;Cycle Recv 371;
Round 55;Calc Percent 0.02;Cycle Sent 361;Cycle Recv 361;
Round 56;Calc Percent 0.016;Cycle Sent 350;Cycle Recv 350;
Round 57;Calc Percent 0.014;Cycle Sent 357;Cycle Recv 357;
Round 58;Calc Percent 0.011;Cycle Sent 372;Cycle Recv 372;
Round 59;Calc Percent 0.011;Cycle Sent 389;Cycle Recv 389;
Round 60;Calc Percent 0.009;Cycle Sent 379;Cycle Recv 379;
Msgs Sent 14319
Msgs Recv 14138

 

Project Book: [PDF]

Simulator Download: [RAR]