dosreduce.c

Go to the documentation of this file.

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>

#define INFINITY -1;
#define INC 0

int debug=0;

typedef struct node {
  int c;   /* color  0:white 1:grey 2:black */
  int d;   /* Distance */
  int p;   /* parent */
  int id;   
} node;

typedef struct QueueItem{
  struct node *u;
  struct QueueItem *next;
} QueueItem;

typedef struct ATlinks{
  int n1;
  int n2;
  struct ATlinks *next;
} ATlinks;

typedef struct CTinfo{
  int src;          
  int dst; 
  int *path;    
  int flag;   /* whether it should be used or not */
} CTinfo;

QueueItem *head, *tail;
ATlinks *AThead, *ATtail;

void enqueue(struct node *vertex );
struct node* dequeue(void);
void cleanq(void);


int main(int argc, char **argv)
{
  int i,j,k, maxd,id1,id2,noattackers,wt;
  int node_count,edges,victim;
  FILE *fp;
  struct node **V, *u;
  struct ATlinks *newlink;
  struct ATlinks *p;
  struct CTinfo **CrossTraffic;
  int **matrix;
  char temp[30];
  int pn1,pn2,*attackers;
  int found,activeconn,pathlen;
  int tempi;
  int *FT,lc,nc;


  if (argc < 3 ){
    printf("Usage: %s inet_topology #attackers #activeconnections\n",argv[0]);
    exit(0);
  }

  noattackers = atoi(argv[2]);
  activeconn = atoi(argv[3]);
  
  /* Read the node_count and edges for topo file */ 
  if ( (fp = fopen(argv[1],"r")) == NULL ){
    printf(" Error openning the adjanceny file\n");
    exit(1);
  }

  fscanf(fp,"%d %d",&node_count,&edges);
  /* Ignore location infomation */
  for(i=0;i<=node_count;i++){
    fgets(temp,30,fp);
  }

  /* Randomly choose victim node */
  victim = (int)((float)node_count*rand()/(RAND_MAX+1.0));
  if(debug){
    printf("node_count= %d edges %d victim=%d\n",node_count,edges,victim);
  }

  /* Initialise all remaining vertices 
   */
  V = (struct node **)malloc(node_count*sizeof(node));
  for(i=0;i<node_count;i++){
    V[i] = (struct node *) malloc (sizeof(node));
    V[i]->id=i;
    V[i]->c=0;
    V[i]->d=INFINITY;
    V[i]->p=INFINITY;
  }
  
  /* Initialise queue */
  head = tail = NULL;
  
  /* Initialise the root of bfs tree 
   * rootid can be the id of any node. like node 0 or leaf */
  V[victim]->c = 1;
  V[victim]->d = 0;
  V[victim]->p = INFINITY;

  enqueue(V[victim]);
  
  /* open file with adjaceny information */
  matrix = (int**)malloc(node_count*sizeof(int*));
  for(i=0;i<node_count;i++){
    matrix[i] = (int*)malloc(node_count*sizeof(int));
    for(j=0;j<node_count;j++){
      matrix[i][j]=0;
    }
  }

  for(i=0;i<edges;i++){
    fscanf(fp,"%d %d %d",&id1,&id2,&wt);
    matrix[id1][id2]=1;
    matrix[id2][id1]=1;
  }

  close(fp);

  
  while(head){
    u = (struct node *) malloc (sizeof(node));
    if(u== NULL){
      printf("Error allocationg u\n");
      exit(1);
    }
    u=dequeue();
    id1= u->id;
    for(i=0;i<node_count;i++){
      /* refer to adj matrix */
      if(matrix[id1][i] == 1 ){
    if (V[i]->c == 0){
      V[i]->c =1;
      V[i]->d = u->d + 1;
      V[i]->p = u->id;
      enqueue(V[i]);
    } 
      }
    }

      V[id1]->c = 2;
      V[id1]->p = u->p;
      V[id1]->d = u->d;
  }

  maxd =0;
  /* print out all the information */
  for (i=0;i<node_count;i++){
    /* printf("id: %d c=%d d=%d p=%d\n",V[i]->id,V[i]->c,V[i]->d,V[i]->p);  */
     if(maxd < V[i]->d)
       maxd = V[i]->d;

  }    
  if (debug) printf(" Max depth %d\n",maxd);
  
  /* Choose the attackers randomly in the topology  */
  attackers = (int*)malloc(noattackers*sizeof(int));
  for(i=0;i<noattackers;i++){
    attackers[i] = victim;
    /* Ensure the victim and attackers are distinct */
    while(attackers[i] == victim){
      attackers[i]= (int)((float)node_count*rand()/(RAND_MAX+1.0));
    }
    if(debug)
      printf("attacker[%d] = %d\n",i,attackers[i]);
  }

  /* Record the attack tree links */
  AThead = ATtail = NULL;
  for(i=0;i<noattackers;i++){
    pn1 = V[attackers[i]]->id;
    pn2 = V[attackers[i]]->p;
    while(pn2 != victim) {

      if(AThead == NULL){
    if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
      printf("Error allocationg space for new ATlink\n");
      exit(1);
    }
    newlink->n1=pn1;
    newlink->n2=pn2;
    AThead = newlink;
    ATtail = newlink;
    newlink->next = NULL;
      } else {
    /* insert only if not already present */
    ATlinks *p = AThead;
    while (p){
      if( (p->n1 != pn1) || (p->n2 != pn2) )
        p = p->next; 
      else 
        break;
    }
    /* link not found */ 
    if(p==NULL){
        if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
          printf("Error allocationg space for new ATlink\n");
          exit(1);
        }
        newlink->n1=pn1;
        newlink->n2=pn2;
        newlink->next = NULL;
        ATtail->next = newlink;
        ATtail = newlink;
    } else {
      /* reached common attack tree. Break from while */
      break; 
    }

      }
      pn1 = pn2;
      pn2 = V[pn1]->p;
    }
    /* Insert the last link before victim */ 
    if(pn2 == victim){
       if(AThead == NULL){
    if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
      printf("Error allocationg space for new ATlink\n");
      exit(1);
    }
    newlink->n1=pn1;
    newlink->n2=pn2;
    AThead = newlink;
    ATtail = newlink;
    newlink->next = NULL;
      } else {
      /* insert only if not already present */
    ATlinks *p = AThead;
    while (p){
      if( (p->n1 != pn1) || (p->n2 != pn2) )
        p = p->next;
      else 
        break;
    }
        /* link not found */ 
    if(p==NULL){
        if((newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
          printf("Error allocationg space for new ATlink\n");
          exit(1);
        }
        newlink->n1=pn1;
        newlink->n2=pn2;
        newlink->next = NULL;
        ATtail->next = newlink;
        ATtail = newlink;
    }
      } /* end else */
    }
    
  }
    
  
  /* print the attack tree  and encode into matrix */
  i=0;
  p = AThead;
  while(p){
     if(debug) printf("%d n1= %d n2= %d\n",i++,p->n1,p->n2);
      matrix[p->n1][p->n2] = 2;
      p = p->next;
  }

  /* Now randomly choose the cross traffic source and sinks */
  CrossTraffic = (struct CTinfo **)malloc(activeconn*sizeof(CTinfo));
  for(k=0;k<activeconn;k++){
    if ((CrossTraffic[k] = (struct CTinfo *)malloc(sizeof(CTinfo))) == NULL){
      printf("%d:Error allocation Crosstraffic structure\n",errno);
      exit(1);
    }
    CrossTraffic[k]->src =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
    CrossTraffic[k]->dst =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
    if(CrossTraffic[k]->src == CrossTraffic[k]->dst){
      while(CrossTraffic[k]->dst == CrossTraffic[k]->src)
    CrossTraffic[k]->dst =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
    }
    CrossTraffic[k]->flag = 0; /* Usable */
    /* printf("src %d dst %d\n",CrossTraffic[k]->src, CrossTraffic[k]->dst);
       fflush(NULL); */
    
    /* fill path after bfs */
    /* Initialise the V matrix */
    for(i=0;i<node_count;i++){
      V[i]->id=i;
      V[i]->c=0;
      V[i]->d=INFINITY;
      V[i]->p=INFINITY;
    }
  
    /* Initialise queue */
    head = tail = NULL;
    tempi = CrossTraffic[k]->src;

    /* Initialise the root of bfs tree 
     * rootid can be the id of any node. like node 0 or leaf */
    V[tempi]->c = 1;
    V[tempi]->d = 0;
    V[tempi]->p = INFINITY;

    enqueue(V[tempi]);
    found=0;
    while(head){
      if((u = (struct node *)malloc(sizeof(node))) == NULL){
    printf("out of memory for u %d\n",errno);
    exit(1);
      }
    
      u=dequeue();
      id1= u->id;
      for(i=0;i<node_count;i++){
    /* refer to adj matrix */
    if(matrix[id1][i] != 0 ){
      if (V[i]->c == 0){
        V[i]->c =1;
        V[i]->d = u->d + 1;
        V[i]->p = u->id;
        if (V[i]->id == CrossTraffic[k]->dst){
          found = 1;
          pathlen = V[i]->d;
          break; 
        }
        enqueue(V[i]);
      } 
    }
      }
      if(found == 1){ 
    cleanq();
    break;
      }
      V[id1]->c = 2;
      V[id1]->p = u->p;
      V[id1]->d = u->d;
    }

    /* print the information */
    if(debug)
      printf("%d Src %d Dst %d Path ",k,CrossTraffic[k]->src,CrossTraffic[k]->dst);

    /* Find the path from src to dst */
    /* Stored dst, dst-1...src */ 

    CrossTraffic[k]->path = (int*)malloc(sizeof(pathlen));
    for(j=pathlen;j>=0;j--){
      if(j==pathlen)
    CrossTraffic[k]->path[j] = CrossTraffic[k]->dst;
      else {
    tempi = CrossTraffic[k]->path[j+1];
    CrossTraffic[k]->path[j] = V[tempi]->p;
      }
      if(debug)
    printf("%d ",CrossTraffic[k]->path[j]);

    }
  
    /* Matrix encoding 
     * 0 = no link 
     * 1 = link ( no traffic )
     * 2 = attack link only 
     * 3 = attack + cross traffic link 
     * 4 = cross traffic link only but path on AT  
     * 5 = only one flow of cross traffic 
     * 6 = more than one flow of cross traffic on link 
     *

     * Flag encoding 
     * 0 : discard 
     * 1 : shared attack tree 
     * 2 : shared cross traffic links 
     **** */ 
    /* Check is flag should change */ 
    for(j=0;j<pathlen;j++){
      if((matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] == 2) \
      || (matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] == 3)){
    CrossTraffic[k]->flag = 1;
      }
    }

    for(j=0;j<pathlen;j++){
      switch(matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]){
      case 1:
    if(CrossTraffic[k]->flag == 1)
      tempi=4;
    else 
      tempi=5;
    break;
      case 2:
    if(CrossTraffic[k]->flag == 0){
      printf("Flag has to be 1 or 2 for %d\n",k);
      printf("info: link %d %d, matrix = %d\n",\
         CrossTraffic[k]->path[j],CrossTraffic[k]->path[j+1], matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]); 
      exit(1);
    }
    tempi=3;
    break;
      case 3:
    if(CrossTraffic[k]->flag == 0){
      printf("Flag has to be 1 or 2 for %d\n",k);
      printf("info: link %d %d, matrix = %d\n",\
         CrossTraffic[k]->path[j],CrossTraffic[k]->path[j+1], matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]); 

      exit(1);
    }
    tempi=3;
    break;
    /*
       //case 4:
    //if(CrossTraffic[k]->flag == 1)
     // tempi=4;
    //else {
    //  tempi=6;
    //  CrossTraffic[k]->flag = 2;
    //}
    //break;
      //case 5:
//  if (CrossTraffic[k]->flag == 0)
//    tempi = 5;
//  else {
//    CrossTraffic[k]->flag =2;
//    tempi = 6;
//  }
//  break; 
    */
    
}
      matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] = tempi;
    } /* for the switch */ 

    if(debug) printf("Flag %d\n",CrossTraffic[k]->flag);
  } /* Close for number of active connections  */

  /* Get number of nodes and links in reducted topology */ 
  FT = (int *)malloc(node_count*sizeof(int));
  if ( FT == NULL){
    printf("out of memory\n");
    exit(0);
  }
  for(i=0;i<node_count;i++)
    FT[i] =0;
  lc=0;
  nc=0;

  for(i=0;i<node_count;i++){
    for(j=0;j<node_count;j++){
      // printf("[%d][%d]= %d\n",i,j,matrix[i][j]);
      if((matrix[i][j] == 2) || (matrix[i][j] == 3) || (matrix[i][j] == 4) || (matrix[i][j] == 6)){
    if(FT[i]==0){
      FT[i] = 1;
      printf("node %d\n",i);
      nc++;
    }
    if(FT[j] == 0){
      FT[j]=1;
      printf("node %d\n",j);
      nc++;
    }
    printf("link %d %d\n",i,j);
    lc++;
      } 
    }
  }
  printf("\nSummary\n");
  printf("Total: Nodes %d Links %d\n",nc,lc);
  printf("Victim: %d\n",victim);
  printf("Attackers:");
  for(i=0;i<noattackers;i++) printf(" %d",attackers[i]);
  printf("\n");
  
  return 0; 
}
  
  

void cleanq(void)
{
  struct node *p;
  while(head)
    p = dequeue();
}

void enqueue(struct node *vertex)
{
  QueueItem *p = (struct QueueItem *) malloc (sizeof(QueueItem));
  if ( p == NULL){
    printf("Error here");
    exit(0);
  }
  p->u = vertex;
  p->next = NULL;

  if(head==NULL){
    head = p;
    tail = p;
  }
  else {
    tail->next= p;
    tail = p;
  }
}

struct node* dequeue(void)
{
  struct node *retvertex;
  QueueItem *p = (struct QueueItem *) malloc (sizeof(QueueItem));

  if (head == tail) {
    retvertex = head->u;
    head = tail = NULL;
  } else {
    p = head;
    retvertex=head->u;
    head = head->next;
    free(p);
  }
  return retvertex;
}

---