vendor/github.com/google/gopacket/ip4defrag/defrag.go

   1 // Copyright 2013 Google, Inc. All rights reserved.
   2 //
   3 // Use of this source code is governed by a BSD-style license
   4 // that can be found in the LICENSE file in the root of the source
   5 // tree.
   6
   7 // Package ip4defrag implements a IPv4 defragmenter
   8 package ip4defrag
   9
  10 import (
  11         "container/list"
  12         "errors"
  13         "fmt"
  14         "log"
  15         "sync"
  16         "time"
  17
  18         "github.com/google/gopacket"
  19         "github.com/google/gopacket/layers"
  20 )
  21
  22 // Quick and Easy to use debug code to trace
  23 // how defrag works.
  24 var debug debugging = false // or flip to true
  25 type debugging bool
  26
  27 func (d debugging) Printf(format string, args ...interface{}) {
  28         if d {
  29                 log.Printf(format, args...)
  30         }
  31 }
  32
  33 // Constants determining how to handle fragments.
  34 const (
  35         IPv4MinimumFragmentSize    = 576   // Minimum size of a single fragment
  36         IPv4MaximumSize            = 65535 // Maximum size of a fragment (2^16)
  37         IPv4MaximumFragmentOffset  = 8189  // Maximum offset of a fragment
  38         IPv4MaximumFragmentListLen = 8     // Back out if we get more than this many fragments
  39 )
  40
  41 // DefragIPv4 takes in an IPv4 packet with a fragment payload.
  42 //
  43 // It do not modify the IPv4 layer in place, 'in' remains untouched
  44 // It returns a ready-to be used IPv4 layer.
  45 //
  46 // If the passed-in IPv4 layer is NOT fragmented, it will
  47 // immediately return it without modifying the layer.
  48 //
  49 // If the IPv4 layer is a fragment and we don't have all
  50 // fragments, it will return nil and store whatever internal
  51 // information it needs to eventually defrag the packet.
  52 //
  53 // If the IPv4 layer is the last fragment needed to reconstruct
  54 // the packet, a new IPv4 layer will be returned, and will be set to
  55 // the entire defragmented packet,
  56 //
  57 // It use a map of all the running flows
  58 //
  59 // Usage example:
  60 //
  61 // func HandlePacket(in *layers.IPv4) err {
  62 //     defragger := ip4defrag.NewIPv4Defragmenter()
  63 //     in, err := defragger.DefragIPv4(in)
  64 //     if err != nil {
  65 //         return err
  66 //     } else if in == nil {
  67 //         return nil  // packet fragment, we don't have whole packet yet.
  68 //     }
  69 //     // At this point, we know that 'in' is defragmented.
  70 //     //It may be the same 'in' passed to
  71 //         // HandlePacket, or it may not, but we don't really care :)
  72 //         ... do stuff to 'in' ...
  73 //}
  74 //
  75 func (d *IPv4Defragmenter) DefragIPv4(in *layers.IPv4) (*layers.IPv4, error) {
  76         return d.DefragIPv4WithTimestamp(in, time.Now())
  77 }
  78
  79 // DefragIPv4WithTimestamp provides functionality of DefragIPv4 with
  80 // an additional timestamp parameter which is used for discarding
  81 // old fragments instead of time.Now()
  82 //
  83 // This is useful when operating on pcap files instead of live captured data
  84 //
  85 func (d *IPv4Defragmenter) DefragIPv4WithTimestamp(in *layers.IPv4, t time.Time) (*layers.IPv4, error) {
  86         // check if we need to defrag
  87         if st := d.dontDefrag(in); st == true {
  88                 debug.Printf("defrag: do nothing, do not need anything")
  89                 return in, nil
  90         }
  91         // perfom security checks
  92         st, err := d.securityChecks(in)
  93         if err != nil || st == false {
  94                 debug.Printf("defrag: alert security check")
  95                 return nil, err
  96         }
  97
  98         // ok, got a fragment
  99         debug.Printf("defrag: got a new fragment in.Id=%d in.FragOffset=%d in.Flags=%d\n",
 100                 in.Id, in.FragOffset*8, in.Flags)
 101
 102         // have we already seen a flow between src/dst with that Id?
 103         ipf := newIPv4(in)
 104         var fl *fragmentList
 105         var exist bool
 106         d.Lock()
 107         fl, exist = d.ipFlows[ipf]
 108         if !exist {
 109                 debug.Printf("defrag: unknown flow, creating a new one\n")
 110                 fl = new(fragmentList)
 111                 d.ipFlows[ipf] = fl
 112         }
 113         d.Unlock()
 114         // insert, and if final build it
 115         out, err2 := fl.insert(in, t)
 116
 117         // at last, if we hit the maximum frag list len
 118         // without any defrag success, we just drop everything and
 119         // raise an error
 120         if out == nil && fl.List.Len()+1 > IPv4MaximumFragmentListLen {
 121                 d.flush(ipf)
 122                 return nil, fmt.Errorf("defrag: Fragment List hits its maximum"+
 123                         "size(%d), without success. Flushing the list",
 124                         IPv4MaximumFragmentListLen)
 125         }
 126
 127         // if we got a packet, it's a new one, and he is defragmented
 128         if out != nil {
 129                 // when defrag is done for a flow between two ip
 130                 // clean the list
 131                 d.flush(ipf)
 132                 return out, nil
 133         }
 134         return nil, err2
 135 }
 136
 137 // DiscardOlderThan forgets all packets without any activity since
 138 // time t. It returns the number of FragmentList aka number of
 139 // fragment packets it has discarded.
 140 func (d *IPv4Defragmenter) DiscardOlderThan(t time.Time) int {
 141         var nb int
 142         d.Lock()
 143         for k, v := range d.ipFlows {
 144                 if v.LastSeen.Before(t) {
 145                         nb = nb + 1
 146                         delete(d.ipFlows, k)
 147                 }
 148         }
 149         d.Unlock()
 150         return nb
 151 }
 152
 153 // flush the fragment list for a particular flow
 154 func (d *IPv4Defragmenter) flush(ipf ipv4) {
 155         d.Lock()
 156         fl := new(fragmentList)
 157         d.ipFlows[ipf] = fl
 158         d.Unlock()
 159 }
 160
 161 // dontDefrag returns true if the IPv4 packet do not need
 162 // any defragmentation
 163 func (d *IPv4Defragmenter) dontDefrag(ip *layers.IPv4) bool {
 164         // don't defrag packet with DF flag
 165         if ip.Flags&layers.IPv4DontFragment != 0 {
 166                 return true
 167         }
 168         // don't defrag not fragmented ones
 169         if ip.Flags&layers.IPv4MoreFragments == 0 && ip.FragOffset == 0 {
 170                 return true
 171         }
 172         return false
 173 }
 174
 175 // securityChecks performs the needed security checks
 176 func (d *IPv4Defragmenter) securityChecks(ip *layers.IPv4) (bool, error) {
 177         // don't allow too big fragment offset
 178         if ip.FragOffset > IPv4MaximumFragmentOffset {
 179                 return false, fmt.Errorf("defrag: fragment offset too big "+
 180                         "(handcrafted? %d > %d)", ip.FragOffset, IPv4MaximumFragmentOffset)
 181         }
 182         fragOffset := ip.FragOffset * 8
 183
 184         // don't allow fragment that would oversize an IP packet
 185         if fragOffset+ip.Length > IPv4MaximumSize {
 186                 return false, fmt.Errorf("defrag: fragment will overrun "+
 187                         "(handcrafted? %d > %d)", ip.FragOffset*8+ip.Length, IPv4MaximumSize)
 188         }
 189
 190         return true, nil
 191 }
 192
 193 // fragmentList holds a container/list used to contains IP
 194 // packets/fragments.  It stores internal counters to track the
 195 // maximum total of byte, and the current length it has received.
 196 // It also stores a flag to know if he has seen the last packet.
 197 type fragmentList struct {
 198         List          list.List
 199         Highest       uint16
 200         Current       uint16
 201         FinalReceived bool
 202         LastSeen      time.Time
 203 }
 204
 205 // insert insert an IPv4 fragment/packet into the Fragment List
 206 // It use the following strategy : we are inserting fragment based
 207 // on their offset, latest first. This is sometimes called BSD-Right.
 208 // See: http://www.sans.org/reading-room/whitepapers/detection/ip-fragment-reassembly-scapy-33969
 209 func (f *fragmentList) insert(in *layers.IPv4, t time.Time) (*layers.IPv4, error) {
 210         // TODO: should keep a copy of *in in the list
 211         // or not (ie the packet source is reliable) ? -> depends on Lazy / last packet
 212         fragOffset := in.FragOffset * 8
 213         if fragOffset >= f.Highest {
 214                 f.List.PushBack(in)
 215         } else {
 216                 for e := f.List.Front(); e != nil; e = e.Next() {
 217                         frag, _ := e.Value.(*layers.IPv4)
 218                         if in.FragOffset == frag.FragOffset {
 219                                 // TODO: what if we receive a fragment
 220                                 // that begins with duplicate data but
 221                                 // *also* has new data? For example:
 222                                 //
 223                                 // AAAA
 224                                 //     BB
 225                                 //     BBCC
 226                                 //         DDDD
 227                                 //
 228                                 // In this situation we completely
 229                                 // ignore CC and the complete packet can
 230                                 // never be reassembled.
 231                                 debug.Printf("defrag: ignoring frag %d as we already have it (duplicate?)\n",
 232                                         fragOffset)
 233                                 return nil, nil
 234                         }
 235                         if in.FragOffset < frag.FragOffset {
 236                                 debug.Printf("defrag: inserting frag %d before existing frag %d\n",
 237                                         fragOffset, frag.FragOffset*8)
 238                                 f.List.InsertBefore(in, e)
 239                                 break
 240                         }
 241                 }
 242         }
 243
 244         f.LastSeen = t
 245
 246         fragLength := in.Length - 20
 247         // After inserting the Fragment, we update the counters
 248         if f.Highest < fragOffset+fragLength {
 249                 f.Highest = fragOffset + fragLength
 250         }
 251         f.Current = f.Current + fragLength
 252
 253         debug.Printf("defrag: insert ListLen: %d Highest:%d Current:%d\n",
 254                 f.List.Len(),
 255                 f.Highest, f.Current)
 256
 257         // Final Fragment ?
 258         if in.Flags&layers.IPv4MoreFragments == 0 {
 259                 f.FinalReceived = true
 260         }
 261         // Ready to try defrag ?
 262         if f.FinalReceived && f.Highest == f.Current {
 263                 return f.build(in)
 264         }
 265         return nil, nil
 266 }
 267
 268 // Build builds the final datagram, modifying ip in place.
 269 // It puts priority to packet in the early position of the list.
 270 // See Insert for more details.
 271 func (f *fragmentList) build(in *layers.IPv4) (*layers.IPv4, error) {
 272         var final []byte
 273         var currentOffset uint16
 274
 275         debug.Printf("defrag: building the datagram \n")
 276         for e := f.List.Front(); e != nil; e = e.Next() {
 277                 frag, _ := e.Value.(*layers.IPv4)
 278                 if frag.FragOffset*8 == currentOffset {
 279                         debug.Printf("defrag: building - adding %d\n", frag.FragOffset*8)
 280                         final = append(final, frag.Payload...)
 281                         currentOffset = currentOffset + frag.Length - 20
 282                 } else if frag.FragOffset*8 < currentOffset {
 283                         // overlapping fragment - let's take only what we need
 284                         startAt := currentOffset - frag.FragOffset*8
 285                         debug.Printf("defrag: building - overlapping, starting at %d\n",
 286                                 startAt)
 287                         if startAt > frag.Length-20 {
 288                                 return nil, errors.New("defrag: building - invalid fragment")
 289                         }
 290                         final = append(final, frag.Payload[startAt:]...)
 291                         currentOffset = currentOffset + frag.FragOffset*8
 292                 } else {
 293                         // Houston - we have an hole !
 294                         debug.Printf("defrag: hole found while building, " +
 295                                 "stopping the defrag process\n")
 296                         return nil, errors.New("defrag: building - hole found")
 297                 }
 298                 debug.Printf("defrag: building - next is %d\n", currentOffset)
 299         }
 300
 301         // TODO recompute IP Checksum
 302         out := &layers.IPv4{
 303                 Version:    in.Version,
 304                 IHL:        in.IHL,
 305                 TOS:        in.TOS,
 306                 Length:     f.Highest,
 307                 Id:         0,
 308                 Flags:      0,
 309                 FragOffset: 0,
 310                 TTL:        in.TTL,
 311                 Protocol:   in.Protocol,
 312                 Checksum:   0,
 313                 SrcIP:      in.SrcIP,
 314                 DstIP:      in.DstIP,
 315                 Options:    in.Options,
 316                 Padding:    in.Padding,
 317         }
 318         out.Payload = final
 319
 320         return out, nil
 321 }
 322
 323 // ipv4 is a struct to be used as a key.
 324 type ipv4 struct {
 325         ip4 gopacket.Flow
 326         id  uint16
 327 }
 328
 329 // newIPv4 returns a new initialized IPv4 Flow
 330 func newIPv4(ip *layers.IPv4) ipv4 {
 331         return ipv4{
 332                 ip4: ip.NetworkFlow(),
 333                 id:  ip.Id,
 334         }
 335 }
 336
 337 // IPv4Defragmenter is a struct which embedded a map of
 338 // all fragment/packet.
 339 type IPv4Defragmenter struct {
 340         sync.RWMutex
 341         ipFlows map[ipv4]*fragmentList
 342 }
 343
 344 // NewIPv4Defragmenter returns a new IPv4Defragmenter
 345 // with an initialized map.
 346 func NewIPv4Defragmenter() *IPv4Defragmenter {
 347         return &IPv4Defragmenter{
 348                 ipFlows: make(map[ipv4]*fragmentList),
 349         }
 350 }