开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
dosreduce.c
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：11k
源码类别：

通讯编程

开发平台：

Visual C++

dosreduce.c：源码内容
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<errno.h>
  5. #define INFINITY -1;
  6. #define INC 0
  8. int debug=0;
  10. typedef struct node {
  11.   int c;   /* color  0:white 1:grey 2:black */
  12.   int d;   /* Distance */
  13.   int p;   /* parent */
  14.   int id;   
  15. } node;
  17. typedef struct QueueItem{
  18.   struct node *u;
  19.   struct QueueItem *next;
  20. } QueueItem;
  22. typedef struct ATlinks{
  23.   int n1;
  24.   int n2;
  25.   struct ATlinks *next;
  26. } ATlinks;
  28. typedef struct CTinfo{
  29.   int src;          
  30.   int dst; 
  31.   int *path;    
  32.   int flag;   /* whether it should be used or not */
  33. } CTinfo;
  35. QueueItem *head, *tail;
  36. ATlinks *AThead, *ATtail;
  38. void enqueue(struct node *vertex );
  39. struct node* dequeue(void);
  40. void cleanq(void);
  43. int main(int argc, char **argv)
  44. {
  45.   int i,j,k, maxd,id1,id2,noattackers,wt;
  46.   int node_count,edges,victim;
  47.   FILE *fp;
  48.   struct node **V, *u;
  49.   struct ATlinks *newlink;
  50.   struct ATlinks *p;
  51.   struct CTinfo **CrossTraffic;
  52.   int **matrix;
  53.   char temp[30];
  54.   int pn1,pn2,*attackers;
  55.   int found,activeconn,pathlen;
  56.   int tempi;
  57.   int *FT,lc,nc;
  60.   if (argc < 3 ){
  61.     printf("Usage: %s inet_topology #attackers #activeconnectionsn",argv[0]);
  62.     exit(0);
  63.   }
  65.   noattackers = atoi(argv[2]);
  66.   activeconn = atoi(argv[3]);
  67.   
  68.   /* Read the node_count and edges for topo file */ 
  69.   if ( (fp = fopen(argv[1],"r")) == NULL ){
  70.     printf(" Error openning the adjanceny filen");
  71.     exit(1);
  72.   }
  74.   fscanf(fp,"%d %d",&node_count,&edges);
  75.   /* Ignore location infomation */
  76.   for(i=0;i<=node_count;i++){
  77.     fgets(temp,30,fp);
  78.   }
  80.   /* Randomly choose victim node */
  81.   victim = (int)((float)node_count*rand()/(RAND_MAX+1.0));
  82.   if(debug){
  83.     printf("node_count= %d edges %d victim=%dn",node_count,edges,victim);
  84.   }
  86.   /* Initialise all remaining vertices 
  87.    */
  88.   V = (struct node **)malloc(node_count*sizeof(node));
  89.   for(i=0;i<node_count;i++){
  90.     V[i] = (struct node *) malloc (sizeof(node));
  91.     V[i]->id=i;
  92.     V[i]->c=0;
  93.     V[i]->d=INFINITY;
  94.     V[i]->p=INFINITY;
  95.   }
  96.   
  97.   /* Initialise queue */
  98.   head = tail = NULL;
  99.   
  100.   /* Initialise the root of bfs tree 
  101.    * rootid can be the id of any node. like node 0 or leaf */
  102.   V[victim]->c = 1;
  103.   V[victim]->d = 0;
  104.   V[victim]->p = INFINITY;
  106.   enqueue(V[victim]);
  107.   
  108.   /* open file with adjaceny information */
  109.   matrix = (int**)malloc(node_count*sizeof(int*));
  110.   for(i=0;i<node_count;i++){
  111.     matrix[i] = (int*)malloc(node_count*sizeof(int));
  112.     for(j=0;j<node_count;j++){
  113.       matrix[i][j]=0;
  114.     }
  115.   }
  117.   for(i=0;i<edges;i++){
  118.     fscanf(fp,"%d %d %d",&id1,&id2,&wt);
  119.     matrix[id1][id2]=1;
  120.     matrix[id2][id1]=1;
  121.   }
  123.   close(fp);
  125.   
  126.   while(head){
  127.     u = (struct node *) malloc (sizeof(node));
  128.     if(u== NULL){
  129.       printf("Error allocationg un");
  130.       exit(1);
  131.     }
  132.     u=dequeue();
  133.     id1= u->id;
  134.     for(i=0;i<node_count;i++){
  135.       /* refer to adj matrix */
  136.       if(matrix[id1][i] == 1 ){
  137. if (V[i]->c == 0){
  138.   V[i]->c =1;
  139.   V[i]->d = u->d + 1;
  140.   V[i]->p = u->id;
  141.   enqueue(V[i]);
  142. } 
  143.       }
  144.     }
  146.       V[id1]->c = 2;
  147.       V[id1]->p = u->p;
  148.       V[id1]->d = u->d;
  149.   }
  151.   maxd =0;
  152.   /* print out all the information */
  153.   for (i=0;i<node_count;i++){
  154.     /* printf("id: %d c=%d d=%d p=%dn",V[i]->id,V[i]->c,V[i]->d,V[i]->p);  */
  155.      if(maxd < V[i]->d)
  156.        maxd = V[i]->d;
  158.   }    
  159.   if (debug) printf(" Max depth %dn",maxd);
  160.   
  161.   /* Choose the attackers randomly in the topology  */
  162.   attackers = (int*)malloc(noattackers*sizeof(int));
  163.   for(i=0;i<noattackers;i++){
  164.     attackers[i] = victim;
  165.     /* Ensure the victim and attackers are distinct */
  166.     while(attackers[i] == victim){
  167.       attackers[i]= (int)((float)node_count*rand()/(RAND_MAX+1.0));
  168.     }
  169.     if(debug)
  170.       printf("attacker[%d] = %dn",i,attackers[i]);
  171.   }
  173.   /* Record the attack tree links */
  174.   AThead = ATtail = NULL;
  175.   for(i=0;i<noattackers;i++){
  176.     pn1 = V[attackers[i]]->id;
  177.     pn2 = V[attackers[i]]->p;
  178.     while(pn2 != victim) {
  180.       if(AThead == NULL){
  181. if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
  182.   printf("Error allocationg space for new ATlinkn");
  183.   exit(1);
  184. }
  185. newlink->n1=pn1;
  186. newlink->n2=pn2;
  187. AThead = newlink;
  188. ATtail = newlink;
  189. newlink->next = NULL;
  190.       } else {
  191. /* insert only if not already present */
  192. ATlinks *p = AThead;
  193. while (p){
  194.   if( (p->n1 != pn1) || (p->n2 != pn2) )
  195.     p = p->next; 
  196.   else 
  197.     break;
  198. }
  199. /* link not found */ 
  200. if(p==NULL){
  201.    if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
  202.   printf("Error allocationg space for new ATlinkn");
  203.   exit(1);
  204. }
  205. newlink->n1=pn1;
  206. newlink->n2=pn2;
  207. newlink->next = NULL;
  208. ATtail->next = newlink;
  209. ATtail = newlink;
  210. } else {
  211.   /* reached common attack tree. Break from while */
  212.   break; 
  213. }
  215.       }
  216.       pn1 = pn2;
  217.       pn2 = V[pn1]->p;
  218.     }
  219.     /* Insert the last link before victim */ 
  220.     if(pn2 == victim){
  221.        if(AThead == NULL){
  222. if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
  223.   printf("Error allocationg space for new ATlinkn");
  224.   exit(1);
  225. }
  226. newlink->n1=pn1;
  227. newlink->n2=pn2;
  228. AThead = newlink;
  229. ATtail = newlink;
  230. newlink->next = NULL;
  231.       } else {
  232.       /* insert only if not already present */
  233. ATlinks *p = AThead;
  234. while (p){
  235.   if( (p->n1 != pn1) || (p->n2 != pn2) )
  236.     p = p->next;
  237.   else 
  238.     break;
  239. }
  240.        /* link not found */ 
  241. if(p==NULL){
  242.    if((newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
  243.   printf("Error allocationg space for new ATlinkn");
  244.   exit(1);
  245. }
  246. newlink->n1=pn1;
  247. newlink->n2=pn2;
  248. newlink->next = NULL;
  249. ATtail->next = newlink;
  250. ATtail = newlink;
  251. }
  252.       } /* end else */
  253.     }
  254.     
  255.   }
  257.   
  258.   /* print the attack tree  and encode into matrix */
  259.   i=0;
  260.   p = AThead;
  261.   while(p){
  262.      if(debug) printf("%d n1= %d n2= %dn",i++,p->n1,p->n2);
  263.       matrix[p->n1][p->n2] = 2;
  264.       p = p->next;
  265.   }
  267.   /* Now randomly choose the cross traffic source and sinks */
  268.   CrossTraffic = (struct CTinfo **)malloc(activeconn*sizeof(CTinfo));
  269.   for(k=0;k<activeconn;k++){
  270.     if ((CrossTraffic[k] = (struct CTinfo *)malloc(sizeof(CTinfo))) == NULL){
  271.       printf("%d:Error allocation Crosstraffic structuren",errno);
  272.       exit(1);
  273.     }
  274.     CrossTraffic[k]->src =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
  275.     CrossTraffic[k]->dst =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
  276.     if(CrossTraffic[k]->src == CrossTraffic[k]->dst){
  277.       while(CrossTraffic[k]->dst == CrossTraffic[k]->src)
  278. CrossTraffic[k]->dst =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
  279.     }
  280.     CrossTraffic[k]->flag = 0; /* Usable */
  281.     /* printf("src %d dst %dn",CrossTraffic[k]->src, CrossTraffic[k]->dst);
  282.        fflush(NULL); */
  283.     
  284.     /* fill path after bfs */
  285.     /* Initialise the V matrix */
  286.     for(i=0;i<node_count;i++){
  287.       V[i]->id=i;
  288.       V[i]->c=0;
  289.       V[i]->d=INFINITY;
  290.       V[i]->p=INFINITY;
  291.     }
  292.   
  293.     /* Initialise queue */
  294.     head = tail = NULL;
  295.     tempi = CrossTraffic[k]->src;
  297.     /* Initialise the root of bfs tree 
  298.      * rootid can be the id of any node. like node 0 or leaf */
  299.     V[tempi]->c = 1;
  300.     V[tempi]->d = 0;
  301.     V[tempi]->p = INFINITY;
  303.     enqueue(V[tempi]);
  304.     found=0;
  305.     while(head){
  306.       if((u = (struct node *)malloc(sizeof(node))) == NULL){
  307. printf("out of memory for u %dn",errno);
  308. exit(1);
  309.       }
  311.       u=dequeue();
  312.       id1= u->id;
  313.       for(i=0;i<node_count;i++){
  314. /* refer to adj matrix */
  315. if(matrix[id1][i] != 0 ){
  316.   if (V[i]->c == 0){
  317.     V[i]->c =1;
  318.     V[i]->d = u->d + 1;
  319.     V[i]->p = u->id;
  320.     if (V[i]->id == CrossTraffic[k]->dst){
  321.       found = 1;
  322.       pathlen = V[i]->d;
  323.       break; 
  324.     }
  325.     enqueue(V[i]);
  326.   } 
  327. }
  328.       }
  329.       if(found == 1){ 
  330. cleanq();
  331. break;
  332.       }
  333.       V[id1]->c = 2;
  334.       V[id1]->p = u->p;
  335.       V[id1]->d = u->d;
  336.     }
  338.     /* print the information */
  339.     if(debug)
  340.       printf("%d Src %d Dst %d Path ",k,CrossTraffic[k]->src,CrossTraffic[k]->dst);
  342.     /* Find the path from src to dst */
  343.     /* Stored dst, dst-1...src */ 
  345.     CrossTraffic[k]->path = (int*)malloc(sizeof(pathlen));
  346.     for(j=pathlen;j>=0;j--){
  347.       if(j==pathlen)
  348. CrossTraffic[k]->path[j] = CrossTraffic[k]->dst;
  349.       else {
  350. tempi = CrossTraffic[k]->path[j+1];
  351. CrossTraffic[k]->path[j] = V[tempi]->p;
  352.       }
  353.       if(debug)
  354. printf("%d ",CrossTraffic[k]->path[j]);
  356.     }
  357.   
  358.     /* Matrix encoding 
  359.      * 0 = no link 
  360.      * 1 = link ( no traffic )
  361.      * 2 = attack link only 
  362.      * 3 = attack + cross traffic link 
  363.      * 4 = cross traffic link only but path on AT  
  364.      * 5 = only one flow of cross traffic 
  365.      * 6 = more than one flow of cross traffic on link 
  366.      *
  368.      * Flag encoding 
  369.      * 0 : discard 
  370.      * 1 : shared attack tree 
  371.      * 2 : shared cross traffic links 
  372.      **** */ 
  373.     /* Check is flag should change */ 
  374.     for(j=0;j<pathlen;j++){
  375.       if((matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] == 2) 
  376.       || (matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] == 3)){
  377. CrossTraffic[k]->flag = 1;
  378.       }
  379.     }
  381.     for(j=0;j<pathlen;j++){
  382.       switch(matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]){
  383.       case 1:
  384. if(CrossTraffic[k]->flag == 1)
  385.   tempi=4;
  386. else 
  387.   tempi=5;
  388. break;
  389.       case 2:
  390. if(CrossTraffic[k]->flag == 0){
  391.   printf("Flag has to be 1 or 2 for %dn",k);
  392.   printf("info: link %d %d, matrix = %dn",
  393.  CrossTraffic[k]->path[j],CrossTraffic[k]->path[j+1], matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]); 
  394.   exit(1);
  395. }
  396. tempi=3;
  397. break;
  398.       case 3:
  399. if(CrossTraffic[k]->flag == 0){
  400.   printf("Flag has to be 1 or 2 for %dn",k);
  401.      printf("info: link %d %d, matrix = %dn",
  402.  CrossTraffic[k]->path[j],CrossTraffic[k]->path[j+1], matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]); 
  404.   exit(1);
  405. }
  406. tempi=3;
  407. break;
  408. /*
  409.        //case 4:
  410. //if(CrossTraffic[k]->flag == 1)
  411.  // tempi=4;
  412. //else {
  413. //  tempi=6;
  414. //  CrossTraffic[k]->flag = 2;
  415. //}
  416. //break;
  417.       //case 5:
  418. // if (CrossTraffic[k]->flag == 0)
  419. //   tempi = 5;
  420. // else {
  421. //   CrossTraffic[k]->flag =2;
  422. //   tempi = 6;
  423. // }
  424. // break; 
  425. */
  427. }
  428.       matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] = tempi;
  429.     } /* for the switch */ 
  431.     if(debug) printf("Flag %dn",CrossTraffic[k]->flag);
  432.   } /* Close for number of active connections  */
  434.   /* Get number of nodes and links in reducted topology */ 
  435.   FT = (int *)malloc(node_count*sizeof(int));
  436.   if ( FT == NULL){
  437.     printf("out of memoryn");
  438.     exit(0);
  439.   }
  440.   for(i=0;i<node_count;i++)
  441.     FT[i] =0;
  442.   lc=0;
  443.   nc=0;
  445.   for(i=0;i<node_count;i++){
  446.     for(j=0;j<node_count;j++){
  447.       // printf("[%d][%d]= %dn",i,j,matrix[i][j]);
  448.       if((matrix[i][j] == 2) || (matrix[i][j] == 3) || (matrix[i][j] == 4) || (matrix[i][j] == 6)){
  449. if(FT[i]==0){
  450.   FT[i] = 1;
  451.   printf("node %dn",i);
  452.   nc++;
  453. }
  454. if(FT[j] == 0){
  455.   FT[j]=1;
  456.      printf("node %dn",j);
  457.   nc++;
  458. }
  459. printf("link %d %dn",i,j);
  460. lc++;
  461.       } 
  462.     }
  463.   }
  464.   printf("nSummaryn");
  465.   printf("Total: Nodes %d Links %dn",nc,lc);
  466.   printf("Victim: %dn",victim);
  467.   printf("Attackers:");
  468.   for(i=0;i<noattackers;i++) printf(" %d",attackers[i]);
  469.   printf("n");
  470.   
  471.   return 0; 
  472. }
  473.   
  474.   
  476. void cleanq(void)
  477. {
  478.   struct node *p;
  479.   while(head)
  480.     p = dequeue();
  481. }
  483. void enqueue(struct node *vertex)
  484. {
  485.   QueueItem *p = (struct QueueItem *) malloc (sizeof(QueueItem));
  486.   if ( p == NULL){
  487.     printf("Error here");
  488.     exit(0);
  489.   }
  490.   p->u = vertex;
  491.   p->next = NULL;
  493.   if(head==NULL){
  494.     head = p;
  495.     tail = p;
  496.   }
  497.   else {
  498.     tail->next= p;
  499.     tail = p;
  500.   }
  501. }
  503. struct node* dequeue(void)
  504. {
  505.   struct node *retvertex;
  506.   QueueItem *p = (struct QueueItem *) malloc (sizeof(QueueItem));
  508.   if (head == tail) {
  509.     retvertex = head->u;
  510.     head = tail = NULL;
  511.   } else {
  512.     p = head;
  513.     retvertex=head->u;
  514.     head = head->next;
  515.     free(p);
  516.   }
  517.   return retvertex;
  518. }