LCOV - code coverage report
Current view: top level - src - Anon.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 2 191 1.0 %
Date: 2010-12-13 Functions: 2 24 8.3 %
Branches: 2 101 2.0 %

           Branch data     Line data    Source code
       1                 :            : // $Id: Anon.cc 7075 2010-09-13 02:39:38Z vern $
       2                 :            : 
       3                 :            : #include <stdlib.h>
       4                 :            : #include <unistd.h>
       5                 :            : #include <assert.h>
       6                 :            : #include <sys/time.h>
       7                 :            : 
       8                 :            : #include "util.h"
       9                 :            : #include "net_util.h"
      10                 :            : #include "md5.h"
      11                 :            : #include "Anon.h"
      12                 :            : #include "Val.h"
      13                 :            : #include "NetVar.h"
      14                 :            : 
      15                 :            : 
      16                 :            : AnonymizeIPAddr* ip_anonymizer[NUM_ADDR_ANONYMIZATION_METHODS] = {0};
      17                 :            : 
      18                 :          0 : static uint32 rand32()
      19                 :            :         {
      20                 :          0 :         return ((random() & 0xffff) << 16) | (random() & 0xffff);
      21                 :            :         }
      22                 :            : 
      23                 :            : // From tcpdpriv.
      24                 :          0 : int bi_ffs(uint32 value)
      25                 :            :         {
      26                 :          0 :         int add = 0;
      27                 :            :         static uint8 bvals[] = {
      28                 :            :                 0, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1
      29                 :            :         };
      30                 :            : 
      31         [ #  # ]:          0 :         if ( (value & 0xFFFF0000) == 0 )
      32                 :            :                 {
      33         [ #  # ]:          0 :                 if ( value == 0 )
      34                 :            :                         // Zero input ==> zero output.
      35                 :          0 :                         return 0;
      36                 :            : 
      37                 :          0 :                 add += 16;
      38                 :            :                 }
      39                 :            : 
      40                 :            :         else
      41                 :          0 :                 value >>= 16;
      42                 :            : 
      43         [ #  # ]:          0 :         if ( (value & 0xFF00) == 0 )
      44                 :          0 :                 add += 8;
      45                 :            :         else
      46                 :          0 :                 value >>= 8;
      47                 :            : 
      48         [ #  # ]:          0 :         if ( (value & 0xF0) == 0 )
      49                 :          0 :                 add += 4;
      50                 :            :         else
      51                 :          0 :                 value >>= 4;
      52                 :            : 
      53                 :          0 :         return add + bvals[value & 0xf];
      54                 :            :         }
      55                 :            : 
      56                 :            : #define first_n_bit_mask(n)     (~(0xFFFFFFFFU >> n))
      57                 :            : 
      58                 :          0 : ipaddr32_t AnonymizeIPAddr::Anonymize(ipaddr32_t addr)
      59                 :            :         {
      60                 :          0 :         map<ipaddr32_t, ipaddr32_t>::iterator p = mapping.find(addr);
      61         [ #  # ]:          0 :         if ( p != mapping.end() )
      62                 :          0 :                 return p->second;
      63                 :            :         else
      64                 :            :                 {
      65                 :          0 :                 ipaddr32_t new_addr = anonymize(addr);
      66                 :          0 :                 mapping[addr] = new_addr;
      67                 :            : 
      68                 :          0 :                 return new_addr;
      69                 :            :                 }
      70                 :            :         }
      71                 :            : 
      72                 :          0 : int AnonymizeIPAddr::PreserveNet(ipaddr32_t input)
      73                 :            :         {
      74   [ #  #  #  # ]:          0 :         switch ( addr_to_class(ntohl(input)) ) {
      75                 :            :         case 'A':
      76                 :          0 :                 return PreservePrefix(input, 8);
      77                 :            :         case 'B':
      78                 :          0 :                 return PreservePrefix(input, 16);
      79                 :            :         case 'C':
      80                 :          0 :                 return PreservePrefix(input, 24);
      81                 :            :         default:
      82                 :          0 :                 return 0;
      83                 :            :         }
      84                 :            :         }
      85                 :            : 
      86                 :          0 : ipaddr32_t AnonymizeIPAddr_Seq::anonymize(ipaddr32_t /* input */)
      87                 :            :         {
      88                 :          0 :         return htonl(seq++);
      89                 :            :         }
      90                 :            : 
      91                 :          0 : ipaddr32_t AnonymizeIPAddr_RandomMD5::anonymize(ipaddr32_t input)
      92                 :            :         {
      93                 :            :         uint8 digest[16];
      94                 :          0 :         ipaddr32_t output = 0;
      95                 :            : 
      96                 :          0 :         hmac_md5(sizeof(input), (u_char*)(&input), digest);
      97                 :            : 
      98         [ #  # ]:          0 :         for ( int i = 0; i < 4; ++i )
      99                 :          0 :                 output = (output << 8) | digest[i];
     100                 :            : 
     101                 :          0 :         return output;
     102                 :            :         }
     103                 :            : 
     104                 :            : 
     105                 :            : // This code is from "On the Design and Performance of Prefix-Preserving 
     106                 :            : // IP Traffic Trace Anonymization", by Xu et al (IMW 2001)
     107                 :            : // 
     108                 :            : // http://www.imconf.net/imw-2001/proceedings.html
     109                 :            : 
     110                 :          0 : ipaddr32_t AnonymizeIPAddr_PrefixMD5::anonymize(ipaddr32_t input)
     111                 :            :         {
     112                 :            :         uint8 digest[16];
     113                 :          0 :         ipaddr32_t prefix_mask = 0xffffffff;
     114                 :          0 :         input = ntohl(input);
     115                 :          0 :         ipaddr32_t output = input;
     116                 :            : 
     117         [ #  # ]:          0 :         for ( int i = 0; i < 32; ++i )
     118                 :            :                 {
     119                 :            :                 // PAD(x_0 ... x_{i-1}) = x_0 ... x_{i-1} 1 0 ... 0 .
     120                 :          0 :                 prefix.len = htonl(i + 1);
     121                 :          0 :                 prefix.prefix = htonl((input & ~(prefix_mask>>i)) | (1<<(31-i)));
     122                 :            : 
     123                 :            :                 // HK(PAD(x_0 ... x_{i-1})).
     124                 :          0 :                 hmac_md5(sizeof(prefix), (u_char*) &prefix, digest);
     125                 :            : 
     126                 :            :                 // f_{i-1} = LSB(HK(PAD(x_0 ... x_{i-1}))).
     127                 :          0 :                 ipaddr32_t bit_mask = (digest[0] & 1) << (31-i);
     128                 :            : 
     129                 :            :                 // x_i' = x_i ^ f_{i-1}.
     130                 :          0 :                 output ^= bit_mask;
     131                 :            :                 }
     132                 :            : 
     133                 :          0 :         return htonl(output);
     134                 :            :         }
     135                 :            : 
     136                 :          0 : AnonymizeIPAddr_A50::~AnonymizeIPAddr_A50()
     137                 :            :         {
     138 [ #  # ][ #  # ]:          0 :         for ( unsigned int i = 0; i < blocks.size(); ++i )
                 [ #  # ]
     139 [ #  # ][ #  # ]:          0 :                 delete [] blocks[i];
                 [ #  # ]
     140                 :            : 
     141                 :          0 :         blocks.clear();
     142 [ #  # ][ #  # ]:          0 :         }
                 [ #  # ]
     143                 :            : 
     144                 :          0 : void AnonymizeIPAddr_A50::init()
     145                 :            :         {
     146                 :          0 :         root = next_free_node = 0;
     147                 :            : 
     148                 :            :         // Prepare special nodes for 0.0.0.0 and 255.255.255.255.
     149                 :          0 :         memset(&special_nodes[0], 0, sizeof(special_nodes));
     150                 :          0 :         special_nodes[0].input = special_nodes[0].output = 0;
     151                 :          0 :         special_nodes[1].input = special_nodes[1].output = 0xFFFFFFFF;
     152                 :            : 
     153                 :          0 :         before_anonymization = 1;
     154                 :          0 :         }
     155                 :            : 
     156                 :          0 : int AnonymizeIPAddr_A50::PreservePrefix(ipaddr32_t input, int num_bits)
     157                 :            :         {
     158                 :          0 :         DEBUG_MSG("%s/%d\n", dotted_addr(input), num_bits);
     159                 :            : 
     160         [ #  # ]:          0 :         if ( ! before_anonymization )
     161                 :            :                 {
     162                 :          0 :                 run_time("prefix perservation specified after anonymization begun");
     163                 :          0 :                 return 0;
     164                 :            :                 }
     165                 :            : 
     166                 :          0 :         input = ntohl(input);
     167                 :            : 
     168                 :            :         // Sanitize input.
     169                 :          0 :         input = input & first_n_bit_mask(num_bits);
     170                 :            : 
     171                 :          0 :         Node* n = find_node(input);
     172                 :            : 
     173                 :            :         // Preserve the first num_bits bits of addr.
     174         [ #  # ]:          0 :         if ( num_bits == 32 )
     175                 :          0 :                 n->output = input;
     176                 :            : 
     177         [ #  # ]:          0 :         else if ( num_bits > 0 )
     178                 :            :                 {
     179                 :            :                 assert((0xFFFFFFFFU >> 1) == 0x7FFFFFFFU);
     180                 :          0 :                 uint32 suffix_mask = (0xFFFFFFFFU >> num_bits);
     181                 :          0 :                 uint32 prefix_mask = ~suffix_mask;
     182                 :          0 :                 n->output = (input & prefix_mask) | (rand32() & suffix_mask);
     183                 :            :                 }
     184                 :            : 
     185                 :          0 :         return 1;
     186                 :            :         }
     187                 :            : 
     188                 :          0 : ipaddr32_t AnonymizeIPAddr_A50::anonymize(ipaddr32_t a)
     189                 :            :         {
     190                 :          0 :         before_anonymization = 0;
     191                 :          0 :         new_mapping = 0;
     192                 :            : 
     193         [ #  # ]:          0 :         if ( Node* n = find_node(ntohl(a)) )
     194                 :            :                 {
     195                 :          0 :                 ipaddr32_t output = htonl(n->output);
     196                 :          0 :                 return output;
     197                 :            :                 }
     198                 :            :         else
     199                 :          0 :                 return 0;
     200                 :            :         }
     201                 :            : 
     202                 :          0 : AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::new_node_block()
     203                 :            :         {
     204         [ #  # ]:          0 :         assert(! next_free_node);
     205                 :            : 
     206                 :          0 :         int block_size = 1024;
     207                 :          0 :         Node* block = new Node[block_size];
     208         [ #  # ]:          0 :         if ( ! block )
     209                 :          0 :                 internal_error("out of memory!");
     210                 :            : 
     211                 :          0 :         blocks.push_back(block);
     212                 :            : 
     213         [ #  # ]:          0 :         for ( int i = 1; i < block_size - 1; ++i )
     214                 :          0 :                 block[i].child[0] = &block[i+1];
     215                 :            : 
     216                 :          0 :         block[block_size - 1].child[0] = 0;
     217                 :          0 :         next_free_node = &block[1];
     218                 :            : 
     219                 :          0 :         return &block[0];
     220                 :            :         }
     221                 :            : 
     222                 :          0 : inline AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::new_node()
     223                 :            :         {
     224                 :          0 :         new_mapping = 1;
     225                 :            : 
     226         [ #  # ]:          0 :         if ( next_free_node )
     227                 :            :                 {
     228                 :          0 :                 Node* n = next_free_node;
     229                 :          0 :                 next_free_node = n->child[0];
     230                 :          0 :                 return n;
     231                 :            :                 }
     232                 :            :         else
     233                 :          0 :                 return new_node_block();
     234                 :            :         }
     235                 :            : 
     236                 :          0 : inline void AnonymizeIPAddr_A50::free_node(Node *n)
     237                 :            :         {
     238                 :          0 :         n->child[0] = next_free_node;
     239                 :          0 :         next_free_node = n;
     240                 :          0 :         }
     241                 :            : 
     242                 :          0 : ipaddr32_t AnonymizeIPAddr_A50::make_output(ipaddr32_t old_output, int swivel) const
     243                 :            :         {
     244                 :            :         // -A50 anonymization
     245         [ #  # ]:          0 :         if ( swivel == 32 )
     246                 :          0 :                 return old_output ^ 1;
     247                 :            :         else
     248                 :            :                 {
     249                 :            :                 // Bits up to swivel are unchanged; bit swivel is flipped.
     250                 :            :                 ipaddr32_t known_part =
     251                 :          0 :                         ((old_output >> (32 - swivel)) ^ 1) << (32 - swivel);
     252                 :            : 
     253                 :            :                 // Remainder of bits are random.
     254                 :          0 :                 return known_part | ((rand32() & 0x7FFFFFFF) >> swivel);
     255                 :            :                 }
     256                 :            :         }
     257                 :            : 
     258                 :          0 : AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::make_peer(ipaddr32_t a, Node* n)
     259                 :            :         {
     260 [ #  # ][ #  # ]:          0 :         if ( a == 0 || a == 0xFFFFFFFFU )
     261                 :          0 :                 internal_error("0.0.0.0 and 255.255.255.255 should never get into the tree");
     262                 :            : 
     263                 :            :         // Become a peer.
     264                 :            :         // Algorithm: create two nodes, the two peers.  Leave orig node as
     265                 :            :         // the parent of the two new ones.
     266                 :            : 
     267                 :            :         Node* down[2];
     268                 :            : 
     269         [ #  # ]:          0 :         if ( ! (down[0] = new_node()) )
     270                 :          0 :                 return 0;
     271                 :            : 
     272         [ #  # ]:          0 :         if ( ! (down[1] = new_node()) )
     273                 :            :                 {
     274                 :          0 :                 free_node(down[0]);
     275                 :          0 :                 return 0;
     276                 :            :                 }
     277                 :            : 
     278                 :            :         // swivel is first bit 'a' and 'old->input' differ.
     279                 :          0 :         int swivel = bi_ffs(a ^ n->input);
     280                 :            : 
     281                 :            :         // bitvalue is the value of that bit of 'a'.
     282                 :          0 :         int bitvalue = (a >> (32 - swivel)) & 1;
     283                 :            : 
     284                 :          0 :         down[bitvalue]->input = a;
     285                 :          0 :         down[bitvalue]->output = make_output(n->output, swivel);
     286                 :          0 :         down[bitvalue]->child[0] = down[bitvalue]->child[1] = 0;
     287                 :            : 
     288                 :          0 :         *down[1 - bitvalue] = *n;       // copy orig node down one level
     289                 :            : 
     290                 :          0 :         n->input = down[1]->input;        // NB: 1s to the right (0s to the left)
     291                 :          0 :         n->output = down[1]->output;
     292                 :          0 :         n->child[0] = down[0];               // point to children
     293                 :          0 :         n->child[1] = down[1];
     294                 :            : 
     295                 :          0 :         return down[bitvalue];
     296                 :            :         }
     297                 :            : 
     298                 :          0 : AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::find_node(ipaddr32_t a)
     299                 :            :         {
     300                 :            :         // Watch out for special IP addresses, which never make it
     301                 :            :         // into the tree.
     302 [ #  # ][ #  # ]:          0 :         if ( a == 0 || a == 0xFFFFFFFFU )
     303                 :          0 :                 return &special_nodes[a & 1];
     304                 :            : 
     305         [ #  # ]:          0 :         if ( ! root )
     306                 :            :                 {
     307                 :          0 :                 root = new_node();
     308                 :          0 :                 root->input = a;
     309                 :          0 :                 root->output = rand32();
     310                 :          0 :                 root->child[0] = root->child[1] = 0;
     311                 :            : 
     312                 :          0 :                 return root;
     313                 :            :                 }
     314                 :            : 
     315                 :            :         // Straight from tcpdpriv.
     316                 :          0 :         Node* n = root;
     317         [ #  # ]:          0 :         while ( n )
     318                 :            :                 {
     319         [ #  # ]:          0 :                 if ( n->input == a )
     320                 :          0 :                         return n;
     321                 :            : 
     322         [ #  # ]:          0 :                 if ( ! n->child[0] )
     323                 :          0 :                         n = make_peer(a, n);
     324                 :            : 
     325                 :            :                 else
     326                 :            :                         {
     327                 :            :                         // swivel is the first bit in which the two children
     328                 :            :                         // differ.
     329                 :            :                         int swivel =
     330                 :          0 :                                 bi_ffs(n->child[0]->input ^ n->child[1]->input);
     331                 :            : 
     332         [ #  # ]:          0 :                         if ( bi_ffs(a ^ n->input) < swivel )
     333                 :            :                                 // Input differs earlier.
     334                 :          0 :                                 n = make_peer(a, n);
     335                 :            : 
     336         [ #  # ]:          0 :                         else if ( a & (1 << (32 - swivel)) )
     337                 :          0 :                                 n = n->child[1];
     338                 :            : 
     339                 :            :                         else
     340                 :          0 :                                 n = n->child[0];
     341                 :            :                         }
     342                 :            :                 }
     343                 :            : 
     344                 :          0 :         internal_error("out of memory!");
     345                 :            :         return 0;
     346                 :            :         }
     347                 :            : 
     348                 :          0 : void init_ip_addr_anonymizers()
     349                 :            :         {
     350                 :          0 :         ip_anonymizer[KEEP_ORIG_ADDR] = 0;
     351                 :          0 :         ip_anonymizer[SEQUENTIALLY_NUMBERED] = new AnonymizeIPAddr_Seq();
     352                 :          0 :         ip_anonymizer[RANDOM_MD5] = new AnonymizeIPAddr_RandomMD5();
     353                 :          0 :         ip_anonymizer[PREFIX_PRESERVING_A50] = new AnonymizeIPAddr_A50();
     354                 :          0 :         ip_anonymizer[PREFIX_PRESERVING_MD5] = new AnonymizeIPAddr_PrefixMD5();
     355                 :          0 :         }
     356                 :            : 
     357                 :          0 : ipaddr32_t anonymize_ip(ipaddr32_t ip, enum ip_addr_anonymization_class_t cl)
     358                 :            :         {
     359                 :          0 :         TableVal* preserve_addr = 0;
     360                 :          0 :         AddrVal addr(ip);
     361                 :            : 
     362                 :          0 :         int method = -1;
     363                 :            : 
     364      [ #  #  # ]:          0 :         switch ( cl ) {
     365                 :            :         case ORIG_ADDR: // client address
     366                 :          0 :                 preserve_addr = preserve_orig_addr;
     367                 :          0 :                 method = orig_addr_anonymization;
     368                 :          0 :                 break;
     369                 :            : 
     370                 :            :         case RESP_ADDR: // server address
     371                 :          0 :                 preserve_addr = preserve_resp_addr;
     372                 :          0 :                 method = resp_addr_anonymization;
     373                 :          0 :                 break;
     374                 :            : 
     375                 :            :         default:
     376                 :          0 :                 preserve_addr = preserve_other_addr;
     377                 :          0 :                 method = other_addr_anonymization;
     378                 :            :                 break;
     379                 :            :         }
     380                 :            : 
     381                 :          0 :         ipaddr32_t new_ip = 0;
     382                 :            :                 
     383 [ #  # ][ #  # ]:          0 :         if ( preserve_addr && preserve_addr->Lookup(&addr) )
                 [ #  # ]
     384                 :          0 :                 new_ip = ip;
     385                 :            : 
     386 [ #  # ][ #  # ]:          0 :         else if ( method >= 0 && method < NUM_ADDR_ANONYMIZATION_METHODS )
     387                 :            :                 {
     388         [ #  # ]:          0 :                 if ( method == KEEP_ORIG_ADDR ) 
     389                 :          0 :                         new_ip = ip;
     390                 :            : 
     391         [ #  # ]:          0 :                 else if ( ! ip_anonymizer[method] )
     392                 :          0 :                         internal_error("IP anonymizer not initialized");
     393                 :            : 
     394                 :            :                 else
     395                 :          0 :                         new_ip = ip_anonymizer[method]->Anonymize(ip);
     396                 :            :                 }
     397                 :            : 
     398                 :            :         else
     399                 :          0 :                 internal_error("invalid IP anonymization method");
     400                 :            : 
     401                 :            : #ifdef LOG_ANONYMIZATION_MAPPING
     402                 :          0 :         log_anonymization_mapping(ip, new_ip);
     403                 :            : #endif
     404                 :          0 :         return new_ip;
     405                 :            :         }
     406                 :            : 
     407                 :            : #ifdef LOG_ANONYMIZATION_MAPPING
     408                 :            : 
     409                 :            : #include "NetVar.h"
     410                 :            : #include "Event.h"
     411                 :            : 
     412                 :          0 : void log_anonymization_mapping(ipaddr32_t input, ipaddr32_t output)
     413                 :            :         {
     414         [ #  # ]:          0 :         if ( anonymization_mapping )
     415                 :            :                 {
     416                 :          0 :                 val_list* vl = new val_list;
     417                 :          0 :                 vl->append(new AddrVal(input));
     418                 :          0 :                 vl->append(new AddrVal(output));
     419                 :          0 :                 mgr.QueueEvent(anonymization_mapping, vl);
     420                 :            :                 }
     421 [ +  - ][ +  - ]:          6 :         }
     422                 :          3 : 
     423                 :            : #endif

Generated by: LCOV version 1.8