Diagram

Sexy.

http://www.eventhelix.com/RealtimeMantra/Networking/Tcp.pdf

Read more...

BitString Cleanup

Finally settled on the below design for BitString. I had added, and then removed, functionality for AND, OR, and XOR because it is ambiguous as to what length to use if the operands are not the same length.

For example, it should be possible to AND
0xFFFF & 0x7
To get 0x7.

However, is that '0b0000000000000111' or '0b0111' or some other variant. Given that the values are indexes from the most-significant-bit, this creates an issue.

Anyway, here it is below. Modding PCS to use this for decoding simple values.

class  BitString(list):
     '''  
     Creates a list containing the individual bits from a byte-string, integer, 
     or list of values (where each list is interpreted as 1 or 0 based on its 
     truth balue ). 
      
     Bits are ordered from most-significant to least-significant. 
      
     >>> import pcs  
     >>> x = pcs.BitString(0xDEADBEEF)   
     >>> x 
     [1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1] 
     >>> x[4:12] 
     [1, 1, 1, 0, 1, 0, 1, 0] 
     >>> int (x) 
     3735928559L 
     >>> hex(x) 
     '0xdeadbeefL' 
     >>> hex(x[16:32]) 
     '0xbeef' 
     >>> bin(int (x)) 
     '0b11011110101011011011111011101111' 
     >>> str (x) 
     '\xde \xad \xbe \xef ' 
     >>> x[0:8] = 0xAA 
     >>> x[8:16] = [1,1,1,1,0,0,0,0] 
     >>> hex(x) 
     '0xaaf0beefL' 
     >>> int (x) == 0xAAF0BEEF 
     True 
     ''' 
  
     def  __init__(self,bytes): 
          # Convert integer values to their byte representation 
         if  isinstance(bytes,int) or  isinstance(bytes,long): 
             packString = ''  
             if  abs(bytes) <= 0xff : 
                 packString = '!B'  
             elif  abs(bytes) <= 0xffff : 
                 packString = '!H'  
             elif  abs(bytes) <= 0xffffffff : 
                 packString = '!I'  
             bytes = struct.pack(packString, bytes) 
          
          # Convert a list into a byte representation by taking each item 
          # and turning it into a bit. 
         if  isinstance(bytes,list) or  isinstance(bytes,tuple): 
             self.length = len(bytes)*8  
             for  index,i in  enumerate(bytes): 
                 self.append(1  if  i else  0 )   
          
          # For strings or string'ized integers, do bit-shifty stuff 
          # >>> bin(0xFF00) 
          # '0b1111111100000000' 
         if  isinstance(bytes, str): 
             self.length = len(bytes)*8  
              # Do each byte in-order 
             for  i,byte in  enumerate(bytes): 
                  # Most-significant-bit first 
                 for  bit in  range(8 )[::-1 ]: 
                     self.append(1  if  ord(byte) & (1  << bit) else  0 ) 
              
                      
     def  __int__(self): 
         intVal = 0  
         for  index,i in  enumerate(self):       
             intVal += self[-index-1 ] << index 
         return  intVal 
      
     def  __str__(self): 
         value = int(self) 
         formatString = "%0"  + ("%s"  % (len(self)/8 )) + "x"  
         hexstring = formatString % value 
         while  len(hexstring) % 2  != 0 : 
             hexstring = '0'  + hexstring   
         byteString = binascii.unhexlify(hexstring) 
          
         while  len(byteString) < len(self)/8 : 
             byteString = "\x00"  + byteString 
         return  byteString        
      
     def  __hex__(self): 
         return  hex(int(self)) 
      
     def  __getitem__(self, x): 
         return  list.__getitem__(self,x) 
      
     def  __getslice__(self,i,j): 
         return  BitString(list.__getslice__(self,i,j)) 
      
     def  __setitem__(self, i, x): 
         x = 1  if  x else  0  
         list.__setitem__(self,i,x) 
          
     def  __setslice__(self,i,j,x): 
         bs = BitString(x) 
         list.__setslice__(self,i,j,bs) 
      
     def  __invert__(self): 
         return  BitString([0  if  x else  1  for  x in  self]) 
          
     def  __add__(self,x): 
         return  BitString(list.__add__(self,x)) 

Read more...

Untitled

asdfasdf

class  BitString(object): 
     '''  
     Allows bit-level manipulation of a string as if it were an array. 
      
     Example: 
     >>> x = pcs.BitString('\xff \xff ') 
     >>> print x 
     0b1111111111111111 
     >>> print repr (x.bytes) 
     '\xff \xff ' 
     >>> x[4:12] = 0 
     >>> print x 
     0b1111000000001111 
     >>> print bin(x[:8]) 
     0b11110000 
     >>> print bin(x[8:12]) 
     0b0 
     >>> print bin(x[12:]) 
     0b1111 
     >>> print repr (x.bytes) 
     '\xf0\x0f' 
     '''       
     def  __init__(self, bytes): 
         self.value = 0  
         self.length = len(bytes)*8  
         for  i,byte in  enumerate(bytes[::-1 ]):              
             self.value += ord(byte) << (i*8 ) 
     def  __getitem__(self, n):          
         if  n > len(self): 
             raise  IndexError 
         return  1  if  self.value & (1  << (len(self)-n-1 )) else  0  
     def  __getslice__(self, i, j): 
         retVal= 0  
         i = max(i,0 ) 
         j = min(j,len(self)) 
         for  n,bit in  enumerate(range(i,j)): 
             retVal <<= 1  
             retVal += self[bit] 
         return  retVal 
      @property 
     def  bytes(self): return  self.getBytes() 
     def  getBytes(self): 
         formatString = "%0"  + ("%s"  % (len(self)/8 )) + "x"  
         hexstring = formatString % self.value 
         byteString = binascii.unhexlify(hexstring) 
          
         while  len(byteString) < len(self)/8 : 
             byteString = "\x00"  + byteString 
         return  byteString          
     def  __len__(self): 
         return  self.length 
     def  __str__(self): 
         return  self.bin() 
     def  __repr__(self): 
         return  self.__class__.__name__ + "(%s)"  % repr(self.getBytes()) 
     def  __setitem__(self, n, x): 
         x = 1  if  x else  0  
         if  x: 
             self.value |= (x << (len(self)-n-1 )) 
         else : 
             self.value = self.value & self._makeMask(n) 
     def  __setslice__(self, i, j, x): 
         i = max(i,0 ) 
         j = min(j,len(self)) 
          
         isAList = True  
         if  isinstance(x,int) or  isinstance(x,long) or  isinstance(x,bool): 
             isAList = False  
          
         for  index,n in  enumerate(range(i,j)): 
             if  isAList: 
                 self[n] = x[index] 
             else : 
                 self[n] = x 
     def  _makeMask(self, bit): 
         mask = 0  
         bitSkip = (len(self)-bit-1 ) 
         for  i in  range(len(self)): 
             if  i == bitSkip: 
                 continue  
             mask += 1  << i 
         return  mask 
     def  hex(self): 
         return  hex(self.value) 
     def  bin(self): 
         return  bin(self.value) 

When used in conjunction with pcs.Field, I've set it up to calculate the value with the new method, but still *use* the value from the old method, to show the difference between the new vs. old method. Pay particular attention to syn, ack, fin, reset, and push.

>>> synAckPkt = tcp('09\xd4191\xf6\xae\x00\x00\x00\x01`\x12\xff\xff\xfe"\x00\x00')
Decoding sport --> 12345
Decoding dport --> 54321
Decoding sequence --> 959575726
Decoding ack_number --> 1
Decoding offset --> 6
Decoding reserved --> 0
Decoding urgent --> 0
Decoding ack --> 1
Decoding psh --> 0
Decoding reset --> 0
Decoding syn --> 1
Decoding fin --> 0
Decoding window --> 65535
Decoding checksum --> 65058
Decoding urg_pointer --> 0
>>> print repr(synAckPkt)
<class tcp {reset: 4, psh: 2, reserved: 0, sequence: 959575726, ack: 1, checksum: 65058, offset: 6, syn: 9, urgent: 0, window: 65535, ack_number: 1, dport: 54321, sport: 12345, fin: 0, urg_pointer: 0}>
>>> print repr(synAckPkt.data)
<class payload {payload: ''}> 

Read more...

Just Kooky

So PCS can pick up the fields just fine, as long as they're zeros. Make SYN *and* ACK set to '1' and everything is FUBAR.

Packet data taken from:
http://support.microsoft.com/kb/172983

Syn Packet Data:
TCP: ....S., len: 4, seq: 8221822-8221825, ack: 0, win: 8192, src: 1037
dst: 139 (NBT Session)

Syn-Ack Packet Data:
TCP: .A..S., len: 4, seq: 1109645-1109648, ack: 8221823, win: 8760,
src: 139 (NBT Session) dst: 1037

>>> from pcs.packets.tcp import tcp
>>> import binascii
>>> synAck = "008B040D0010EE8D007D747F60122238012D0000020405B42020"
>>> syn = "040D008B007D747E0000000060022000F2130000020405B42020"
>>>
>>> synPkt = tcp(binascii.a2b_hex(syn))
>>> synAckPkt = tcp(binascii.a2b_hex(synAck))
>>>
>>> print repr(synPkt)
[TCP: reset: 0, reserved: 0, sequence: 8221822, ack: 0, checksum: 61971, offset: 6, syn: 1, urgent: 0, window: 8192, push: 0, ack_number: 0, dport: 139, sport: 1037, fin: 0, urg_pointer: 0]
>>>
>>> print repr(synAckPkt)
[TCP: reset: 4, reserved: 0, sequence: 1109645, ack: 1, checksum: 301, offset: 6, syn: 9, urgent: 0, window: 8760, push: 2, ack_number: 8221823, dport: 1037, sport: 139, fin: 0, urg_pointer: 0] Read more...

PCS Bit Encoding

Just some interesting code that I found in PCS. As far as I can tell, the bits of code are the exact same, except for the "shift" field, which is not even used in the scope of the conditional.

            # These two bits of code are the same.
            elif fieldBR > byteBR:
                print "Cannot fit field into current byte"
                shift = fieldBR - byteBR
                mask = 2 ** byteBR - 1
                value = (ord(bytes[curr]) & mask)
                fieldBR -= byteBR
                byteBR = 8
                curr += 1 # next byte
            elif fieldBR == byteBR:
                mask = 2 ** byteBR - 1
                value = ord(bytes[curr]) & mask
                fieldBR -= byteBR
                byteBR = 8
                curr += 1 # next byte
            real_value += value << fieldBR

Read more...

Yeah

Working on the aforementioned PCS bug brought to my attention that I've fixed a few bugs in PCS that need to be fixed in the general distribution before running the below script will work.

Rather, try this (which should work in PCS-0.5 without modification):

from pcs.packets.tcp import tcp

t = tcp('09\xd4191\xf6\xae\x00\x00\x00\x01`\x12\xff\xff\xfe"\x00\x00')

print repr(t)

Read more...

PyDev

Just found out that PyDev has a built-in Python shell that does completion.

FML.

Read more...

Full-Stop

Ran into a BIG issue with PCS last night. Evidently it's mis-identifying packet fields for TCP.

Demo included below:

from pcs.packets.localhost import *
import binascii
x = '020000004500002cca844000400600007f0000017f0000033039d4313931f6ae000000016012fffffe220000'
bytes = binascii.a2b_hex(x)
l = localhost(bytes)
ip = l.data
tcp = ip.data
print repr(tcp)
print tcp

Prints out the following. Notice that instead of SYN/ACK, it is identified as SYN/ACK/RST/PSH.

[class tcp {reset: 4, psh: 2, reserved: 0, sequence: 959575726, ack: 1, checksum: 65058, offset: 6, syn: 9, urgent: 0, window: 65535, ack_number: 1, dport: 54321, sport: 12345, fin: 0, urg_pointer: 0},

class payload {payload: ''}]

That packet is a loopback-ipv4-tcp packet, should look like the following:

Transmission Control Protocol, Src Port: italk (12345), Dst Port: 54321 (54321), Seq: 959575726, Ack: 1, Len: 0

Here's the bytes printed in an easier-to-read format. Emphasis on the flags mine.

02 00 00 00 45 00 00 2c ca 84 40 00 40 06 00 00

7f 00 00 01 7f 00 00 03 30 39 d4 31 39 31 f6 ae

00 00 00 01 60 12 ff ff fe 22 00 00

Read more...

Interesting Observation

In Python, None is so truly equivalent to *nothing* that help(None) spawns the interactive help.

I thought that was interesting.

Read more...

Got Money, Got Paid

Finally!

Anyway, I haven't mad a blog post in waaaaaaaaaaaaaay too long. Anyway, the bit that I'm working on now is to resolve the issue of sequence number wrap-around. The way that I'm implementing it will (hopefully) have the benefit of automating the calculation of SND.NXT and a buffer of octets that need to be retransmitted based off of the send/sent segments, and SND.UNA.

Essentially, it's a continuous list with an offset. Less simple than it would originally appear due to the way slices work. Here's a quick example:

Example:
>>> from segmentBuffer import *
>>> sb = segmentBuffer(base=10, max=15)
>>> sb += range(8)
>>> sb[10] # The first item is at [10]
0
>>> sb[11] # The second item is at [11]
1
>>> sb # However, the items are in the proper order
[0, 1, 2, 3, 4, 5, 6, 7]
>>> sb[10:] # And are properly sliced
[0, 1, 2, 3, 4, 5, 6, 7]
>>> sb[10:2] # And the slices wrap-around at max
[0, 1, 2, 3, 4, 5, 6]
>>> sb[2:10] # And slices stop when it hits a gap.
[7]
>>> sb == sb[10:] # Truth works just fine.
True
>>> sb += 2 # The offset is incremented easily
>>> sb # Notice that the first two items are deleted
[2, 3, 4, 5, 6, 7]
>>> len(sb) # The length indeed goes down 8->2
6
>>> sb += range(100,200)
>>> len(sb) # Adding 100 items keeps the correct length
15
>>> sb # Only items up to the limit are added
[2, 3, 4, 5, 6, 7, 100, 101, 102, 103, 104, 105, 106, 107, 108]
>>> sb2 = sb + range(300,400)
>>> sb is sb2 # Addition operator returns a new object.
False
>>> sb2 += 3 # The other object can be incremented
>>> [i for i in sb if i not in sb2]
[2, 3, 4] # Just an example to show the difference
>>> sb[12:15] # This shows that the items were taken off the front
[2, 3, 4]
>>> sb[12:2]
[2, 3, 4, 5, 6]
>>> sb2[12:2] # The indexes for the remaining items do not change
[5, 6] # Although the deleted items are gone.
>>> sb
[2, 3, 4, 5, 6, 7, 100, 101, 102, 103, 104, 105, 106, 107, 108]
>>> sb2
[5, 6, 7, 100, 101, 102, 103, 104, 105, 106, 107, 108]

Read more...

Birthday and Eclipse Galileo

The birthday went pretty well (I'm still alive, after all) and I just grabbed Galileo and installed all of my tools (PyDev, CDT, Perforce) that I need on a regular basis. Excited to see that there's a Cocoa implementation of Eclipse now, and Galileo seems to start up a lot faster than Ganymeade (don't know if that's an effect of Cocoa-Carbon or general bloat reduction).

Read more...

WTF

Evidently Ecto ate my last SEVERAL blog posts, by not actually posting anything.

Read more...

Hmm

Read more...

No, no, no

Read more...

Okay, okay, okay

Read more...

I Think I've Got It!

I might have finally figured out the packet flow for the most flexibility and utility.

1. Packet arrives on interface
2. Is queued by libpcap
3. Thread grabs packet off of pcap queue
4. IF the packet is NOT the packet we are expecting next (seg.sequence != rcv.nxt)
   1. Throw it into a list used by the thread.
   2. Go back up one level
5. ELSE the packet is one we were expecting
   1. Add the packet to the State Machine's recv() queue, IF there is not already a packet with the same sequence number
   2. IF processing is enabled
      1. Process the packet (i.e. "Segment Arrives" stuff)
      2. Advance the 'processed packet' index, which points to the last packet in the recv() queue that has been processed.
   3. Iterate over all packets in the thread's personal queue. This is done because we might have already received the 'next' packet, but it was received out-of-order.

Okay, so now the packets are being added to a queue, and they are in the correct order. They are also conditionally processed/handled/whatever you want to call it.

Now, we are writing a test. We want to stop when [1] A certain packet is received or [2] A specific state change occurs. This means that two methods need to be hooked into: the state-change method, and the packet-handling method. With the state change, we will want to pass control to the user (i.e. disable auto-processing) AFTER the state transition. With the packet-recv stuff, we want to do it BEFORE the packet is processed. This means that there needs to be a step between '5.1' and '5.2' that checks to see if the packet is flagged, and appropriately disables processing when the packet is encountered.

The test-writer then can call the 'recv()' method and be guaranteed to get the next packet, in the proper order. Additionally, the test-writer can set "break points" that disable auto-processing. This is important, because auto-processing can lead to sending out additional packets (i.e. response to a SYN-ACK, response to a FIN packet, etc.) that may need to be omitted for a test to be successful.

Whew.

Read more...

Multiprocessing

Hmm. Multiprocessing may not be the way to go, as it runs into issues.

Might have to think about this some more.

Read more...

Implementing TCP Stack Stuff

So I'm implementing more and more of the TCP stack. The idea is that if I actually implement a TCP stack (which was expected, in small chunks) then I [1] understand how TCP should operate much better which allows me to [2] write tests much better and [3] identify corner-cases much better.

One of the issues that I ran into tonight reaches back to my idea to run a separate process that's always "listening" for new packets, and does all of the "Segment Arrives" processing (see pp65 in the RFC).

In order to manipulate the TCP stack of some remote host, it is expected that it will be necessary to get one side of the connection into a specific state (e.g., get the remote state to be SYN-SENT, or the local state to be SYN-RECEIVED) and then perform specific operations that test very specific points of the specification.

In order to do this efficiently, it becomes of the utmost importance to be able to get into these states very easily. Connection buildup and tear-down must be simple, as they are not important except for the individual tests that test these portions (and even then, we might want to skip right to receiving the SYN-ACK packet, before sending the ACK packet to enter the Established state).

In order to perform these state transitions gracefully and properly, it becomes necessary to implement the entire TCP stack, and build in hooks that halt at certain points (on a state transition, specific packet sent or received, malformed packet, etc.).

Now, it turns out that I still hadn't done enough planning to foresee the issue with packet ordering. The model that I thought would work would be to call a "recv()" method that would receive the next packet, and then the test would do something interesting with it. That becomes a problem when the test is expecting a specific field -- say, with a specific ACK number -- but receives that packet after receiving some other packet. The test might not properly realize that the first packet (which didn't match the expected pattern) was pertinent, and would be needed later in the test.

This gives two options:

1. The recv() method should only return the next packet (i.e. the segment's sequence number == rcv.nxt)
   
2. The recv() method simply fetches the next packet off of a queue, to which packets are added in-order by a separate thread/process that manages the state.
   

Both of these approaches have their limitations. Consider a test in which we want to send a malformed ACK packet in response to a SYN-ACK packet. The code for that might look something like this:

tsm = TcpStateMachine()
i = tsm.packetsRecvd.size()
syn = tsm.newPacket({'syn':1})
tsm.sendRawTcp(syn)
startTime = time.time()
# Keep looping. Note that this loop would be rolled into a seperate method.
while True:
  # 30 second timeout. Test fails.
  if time.time() < startTime + 30:
    return False
  # If no new packets we received, sleep
  if tsm.packetsRecvd.size() <= i:
    time.sleep(0.1)

  # Loop through available packets.
  for i in range(i, tsm.packetsRecvd.size()):
    p = tsm.packetsRecvd[i]
    # See if it's a SYN-ACK and the ack number matches.
    if p.ack and p.syn and p.ack_number == syn.sequence + 1:
      break
  # Do stuff with packet at offset 'i'.

The code would send a SYN packet, with the other fields auto-filled, then wait until some packet is received, then do processing based on that.

Actually, after writing that, performing some method of callback on a state transition could lead to un-necessary complications. What might be more useful is a way to turn off auto-processing (not receipt of, just processing of) packets upon some trigger (i.e. after transitioning to state 'FIN-WAIT-1', don't do anything with the packets), and a way to see if that trigger has been hit (although checking to see if the state is FIN-WAIT-1 should be sufficient).

Hmm.

Working all of this out in writing might have cleared things up a bit.

Thanks!

Read more...

Time Off Did The Trick

Looks like a little time-off did the trick. Got back into the problem that I was working on last (fighting with the operating system, and the various interfaces). Looks like using 127.0.0.X where X is not '1' works to elicit the correct SYN/ACK response, on the correct interface (lo0), and the host OS doesn't try to fight me about it.

Now all I've gotta do is get the test working :-)

Hopefully, things will be smooth sailing from here on forward!

Read more...

Soy Libre!

Just finished up the last of my exams. About friggin' time. I feel pretty confident about all of them -- and I've been doing better this semester than a usually do.

Schedule for the rest of the evening is GSoC, same for tomorrow. Saturday I've got a BBQ for the 4th. GSoC starts accepting status reports on the 6th, they're due on the 13th (which means I have to submit it to Google/GNN, and they/he has to approve it by then).

Should be an interesting weekend.

I turn 21 next Wednesday (the 8th) so count on nothing getting done on the 8th/9th (Maybe on the 9th, I took the day off from work).

Read more...