Friday, July 24, 2009

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)
>>> hex(x)
>>> hex(x[16:32])
>>> bin(int (x))
>>> str (x)
'\xde \xad \xbe \xef '
>>> x[0:8] = 0xAA
>>> x[8:16] = [1,1,1,1,0,0,0,0]
>>> hex(x)
>>> int (x) == 0xAAF0BEEF

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

def __setslice__(self,i,j,x):
bs = BitString(x)

def __invert__(self):
return BitString([0 if x else 1 for x in self])

def __add__(self,x):
return BitString(list.__add__(self,x))


Thursday, July 23, 2009



class  BitString(object): 
Allows bit-level manipulation of a string as if it were an array.

>>> x = pcs.BitString('\xff \xff ')
>>> print x
>>> print repr (x.bytes)
'\xff \xff '
>>> x[4:12] = 0
>>> print x
>>> print bin(x[:8])
>>> print bin(x[8:12])
>>> print bin(x[12:])
>>> print repr (x.bytes)
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
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:
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(
<class payload {payload: ''}>


Wednesday, July 22, 2009

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:

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...

Tuesday, July 21, 2009

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


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)


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



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 =
tcp =
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


Friday, July 17, 2009

Interesting Observation

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

I thought that was interesting.


Got Money, Got Paid


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:

>>> from segmentBuffer import *
>>> sb = segmentBuffer(base=10, max=15)
>>> sb += range(8)
>>> sb[10] # The first item is at [10]
>>> sb[11] # The second item is at [11]
>>> 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.
>>> sb == sb[10:] # Truth works just fine.
>>> 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
>>> sb += range(100,200)
>>> len(sb) # Adding 100 items keeps the correct length
>>> 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.
>>> 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]


Thursday, July 9, 2009

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).


Monday, July 6, 2009


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




No, no, no


Sunday, July 5, 2009

Okay, okay, okay


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.



Saturday, July 4, 2009


Hmm. Multiprocessing may not be the way to go, as it runs into issues.
Might have to think about this some 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})
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:

# 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:
# 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).


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



Thursday, July 2, 2009

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!


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).