Valhalla Legends Archive

Last night, I left my new bot online, running in debug mode under the control of a friend with instructions that he should "try to break it".

When I got up this morning, the bot had crashed with an access violation.

The call stack was as follows:

memcpy(unsigned char * 0x00431810, unsigned char * 0x00deebc4, unsigned long 0xffffbaad) line 171
CReceiveBuffer::Insert(void * 0x00deebc4) line 73 + 31 bytes
CBnetSocket::ReceiveThread() line 172


Examining the data being passed to the Insert member of the ReceiveBuffer class, it turned out that the following data had been returned by the last call to the recv function on the connected socket:


00DEEBC4  0D F0 AD BA 53 69 43 2E 62 6F 79 00 50 58 45 53  .ð­ºSiC.boy.PXES
00DEEBD4  20 37 30 31 20 30 20 36 38 37 20 30 20 30 20 31   701 0 687 0 0 1
00DEEBE4  30 33 33 20 30 20 30 20 30 00 FF 0F 3F 00 01 00  033 0 0 0.ÿ.?...
00DEEBF4  00 00 00 00 00 00 2F 00 00 00 00 00 00 00 0D F0  ....../........ð
00DEEC04  AD BA 0D F0 AD BA 43 65 6E 74 69 67 72 61 64 65  ­º.ð­ºCentigrade
00DEEC14  00 50 58 45 53 20 30 20 30 20 37 37 20 30 20 30  .PXES 0 0 77 0 0
00DEEC24  20 30 20 30 20 30 20 30 00 FF 0F 3D 00 01 00 00   0 0 0 0.ÿ.=....
00DEEC34  00 00 00 00 00 3E 00 00 00 00 00 00 00 0D F0 AD  .....>........ð­
00DEEC44  BA 0D F0 AD BA 4C 61 75 52 61 5B 46 61 5D 00 50  º.ð­ºLauRa[Fa].P
00DEEC54  58 45 53 20 30 20 30 20 31 20 30 20 30 20 30 20  XES 0 0 1 0 0 0
00DEEC64  30 20 30 20 30 00 FF 0F 3C 00 01 00 00 00 00 00  0 0 0.ÿ.<.......
00DEEC74  00 00 AC 00 00 00 00 00 00 00 0D F0 AD BA 0D F0  ..¬........ð­º.ð
00DEEC84  AD BA 43 6F 62 61 6C 74 2D 32 00 50 58 45 53 20  ­ºCobalt-2.PXES
00DEEC94  30 20 30 20 30 20 30 20 30 20 30 20 30 20 30 20  0 0 0 0 0 0 0 0
00DEECA4  30 00 FF 0F 32 00 05 00 00 00 00 00 00 00 2E 00  0.ÿ.2...........
00DEECB4  00 00 00 00 00 00 0D F0 AD BA 0D F0 AD BA 42 61  .......ð­º.ð­ºBa
00DEECC4  44 4D 61 4E 4E 65 52 00 54 79 20 4A 61 6D 65 73  DMaNNeR.Ty James
00DEECD4  20 3A 29 00


This is the raw data received on the socket. Obviously there are several packets queued up here, but my code can handle and split them in those circumstances.

What seems to have happened is that the first packet received is partial/incomplete, causing the interrogation of the packet header and subsequent memcpy to illegally access unallocated memory....

Now... what I dont understand is why that happened.

The only posssible thing I can think of is that the previous call had received more packets than could be held by the receiving buffer, causing the next call to return the second half of the last packet first.

This could potentially occur with a mass-loaded floodbot (my receiving buffer for the recv function is only 5012 bytes)... however, at the time of this error, the ReceiveBuffer class was reporting that it had zero packets queued for processing.

I've introduced code to check for partial packets and discard them now, but can anyone think of any other circumstance, other than overflow on previous call, in which a call to recv could return a partial/malformed packet... or is it a simple case of making my receiving buffer larger to accomodate mass-loaded floodbots?

Any ideas would be welcome

sometimes bnet won't send you the complete packet, that's why there's a length field. instead of discarding partial packets, wait for the rest of the data and complete the packet.

Ahhh, thanks. I didnt realise that was liable to happen.

I've adjusted my code accordingly.

Is it safe to assume that if a partial packet is received (header + SOME data) that the next partial packet received will be the end of the previous one, or is the server liable to send them out of order?

Quote from: EvilCheese on May 05, 2003, 09:29 AM
Ahhh, thanks. I didnt realise that was liable to happen.

I've adjusted my code accordingly.

Is it safe to assume that if a partial packet is received (header + SOME data) that the next partial packet received will be the end of the previous one, or is the server liable to send them out of order?

If the server spontaneously reordered packet fragments, all clients would become very confused since they rely on the packets being in order and of the length specified.  I'm guessing that in your case, you somehow processed the first portion of a chat event (0xf) before the rest was received.  Your memdump says that the first four bytes were (in little endian) 0xbaadf00d -- a value that occurs within packet 0xf, but not as its head.  Another sanity check you can add is that the first byte must be 0xff.  All bncs packets start out as 0xff, followed by their command byte.  You could also validate that the command byte is below or equal to the maximum valid command for the client you're emulating.  Finally, you should check that the length of the message is not longer than your receive buffer.  If it is, you either have not received the complete packet, or you have misparsed the existing data and are interpreting something else as a length.

Also of interest is that it appears you sign-extended the supposed length field (0xbaad) to 0xffffbaad.  Lengths are generally unsigned, since no one uses negative length packets.

[Edit: fixed a minor terminology mistake and added another sanity check.]

Quote
If the server spontaneously reordered packet fragments, all clients would become very confused since they rely on the packets being in order and of the length specified.

That's what I was thinking... the question was more sarcasm than anything else

Quote
I'm guessing that in your case, you somehow processed the first portion of a chat event (0xf) before the rest was received.  Your memdump says that the first four bytes were (in little endian) 0xbaadf00d -- a value that occurs within packet 0xf, but not as its head.

Exactly what happened. Turns out my friend DID in fact drop the bot into a channel full of spambots (about 35 if he's to be believed)... I guess that one call to recv exceeded the size of my buffer, so I got half of the last packet on the next call. Was my first guess too

Quote
Another sanity check you can add is that the first byte must be 0xff.

Done

Quote
You could also validate that the command byte is below or equal to the maximum valid command for the client you're emulating.

Done now. Thank you for that one

Quote
Finally, you should check that the length of the message is not longer than your receive buffer.

Also done

Quote
Also of interest is that it appears you sign-extended the supposed length field (0xbaad) to 0xffffbaad.  Lengths are generally unsigned, since no one uses negative length packets.

Well.... I figured this is Blizzard we're dealing with, so better safe than sorry

Quote from: EvilCheese on May 05, 2003, 12:37 PMThis is Blizzard we're dealing with, so better safe than sorry.

I laughed so hard at that.

EvilCheese, be sure that you have allocated a buffer the size of the maximum packet size (32k if you read the packet lengths as signed, 64k if not), so that you should always have sufficient buffer space to parse the largest of packets, even if it's one at a time.

If you must disgard a packet (from buffers being full, or some other reason), be sure that you don't disgard data at random. You can do this by pre-parsing the packet header, saving the packet length, and then disgarding data from that packet as it comes in (being sure to decrement the saved packet length to zero so you know when you've reached a new packet).

Quote
Quote from: EvilCheese on Yesterday at 06:37:47pm
This is Blizzard we're dealing with, so better safe than sorry.

I laughed so hard at that.

Anyone who's ever even skim-read a disassembly of the D2 game server (based mainly in D2Game.dll) will understand what I mean by that.

Okay, this is what I came up with as my first solution to the problem. I also included some extra sanity checking in the Insert member of CReceiveBuffer (not shown here)


      if(expectedfragmentsize) //We're expecting a second-half fragment.
      {
         //Just assume it's there (should be safe, since no re-ordering of fragments (Kp) )
         memcpy( (fragmentbuffer + thisfragmentsize), buffer, expectedfragmentsize);
         //Fragment should now be complete, so insert it.
         packetfeed->Insert(fragmentbuffer);
         //Move stepptr to next good packet in buffer.
         stepptr += expectedfragmentsize;
         //Tidy up
         expectedfragmentsize = 0;
         thisfragmentsize = 0;
      }

      //Split up and insert remaining packets.
      while(stepptr < buffer + received)
      {
         if( ((BNCSHeader*)stepptr)->StartPacket == 0xff ) //If it's a valid packet, should never be otherwise.
         {
            //If the length of the packet would take us past the end of received
            //data, then this is a first-half fragment

            DWORD endbuffer = (DWORD)buffer + received;
            DWORD endpacket = (DWORD)( ((BNCSHeader*)stepptr)->PacketLength + stepptr );

            if( endpacket > endbuffer)
            {
               //Find out how much to expect in next fragment
               expectedfragmentsize = endpacket - endbuffer;
               //Then copy this fragment to the fragmentbuffer
               thisfragmentsize = (char*)endbuffer - stepptr;
               memcpy(fragmentbuffer, stepptr, thisfragmentsize);
               //This will always be the last packet in the buffer, so break out of the loop
               break;
            }
            //Otherwise insert the packet and step to next packet.
            packetfeed->Insert(stepptr);
            stepptr += ((BNCSHeader*)stepptr)->PacketLength;
         }
      }


This seems to work admirably.

Comments or other critique welcome

Feel free to steal it if you wanna

case FD_READ:
   int n;
   n = recv( ZakBot.GetSocketHandle(), (char *)(RecvBuffer + BufferLen), sizeof(RecvBuffer) - BufferLen, 0);

   BufferLen += n;

   while ( BufferLen >= 4 ) {
      WORD PacketLen = *(LPWORD)( RecvBuffer + 2 );
      if ( PacketLen > BufferLen ) {
         break;
      }

      //here you deal with the packet

      BufferLen -= PacketLen;

      memmove( RecvBuffer, RecvBuffer + PacketLen, BufferLen );
   }

Mine seems to be just a little more concise.

Quote from: Zakath on May 07, 2003, 11:25 AM

Code Select Expand

case FD_READ:
   int n;
   n = recv( ZakBot.GetSocketHandle(), (char *)(RecvBuffer + BufferLen), sizeof(RecvBuffer) - BufferLen, 0);

   BufferLen += n;

   while ( BufferLen >= 4 ) {
      WORD PacketLen = *(LPWORD)( RecvBuffer + 2 );
      if ( PacketLen > BufferLen ) {
         break;
      }

      //here you deal with the packet

      BufferLen -= PacketLen;

      memmove( RecvBuffer, RecvBuffer + PacketLen, BufferLen );
   }

Mine seems to be just a little more concise.

I'd recommend moving that function (and the receive buffers) inside your bot class.

Yeah, I know. I'd certainly like to. I'm having some trouble figuring out how to do it though. The way the class is constructed makes it a little tougher than I'd like, since the declaring program relies on feedback from the packet parser. I may set up some sort of looping function that I can poll regularly. I have to work on that.

Sky, if you've any suggestions, I'd be more than happy to hear 'em.

wouldnt you take the dwords and ints and everythign and move it under private: or public:

Quote from: Zakath on May 07, 2003, 12:44 PM
Yeah, I know. I'd certainly like to. I'm having some trouble figuring out how to do it though. The way the class is constructed makes it a little tougher than I'd like, since the declaring program relies on feedback from the packet parser. I may set up some sort of looping function that I can poll regularly. I have to work on that.

Sky, if you've any suggestions, I'd be more than happy to hear 'em.

I generally encapsulate all event-handling things within the class.  Typically, my classes have a public "OnEvent" function which is called by the driver when the appropriate event happens.  Often there'll be some method to either give a waitable handle to the class, or get a waitable handle from the class.

Note that if you use overlapped I/O and APCs, you can directly specify a callback function which the system calls in many cases, bypassing the need for the driver to make any explicit calls except run an alertable wait function in a loop.

Classes of mine that implement timers typically have a function to examine the current wait interval and return the minimum wait interval required to set off a timer or the current wait interval, whichever is less.

The data is sent correctly; the problem is most people don't have a good understanding of TCP/IP.  With TCP/IP, you can assume (at the app-level) that what you receive is in the order that it was sent.  What a lot of people are assuming is what was received was how the other end sent it as.  TCP/IP (at the app-level) is stream based, not packet based so don't treat them that way like you're currently doing.  In most apps, Nagel's algorithm is not disabled so if the app sends 1 byte and immediately (or a few usecs later) sends another byte, both bytes will usually be combined into 1 real packet that's sent out to the remote end.  The other end will require only 1 recv to get both bytes, not 2.  If Nagel was disabled, there's a higher chance the two sends will result in 2 packets, but on the remote end, they might be able to get away with only doing 1 recv (depending on the route the packet took to get there, what those routers did to the packets, and when the remote app decides to do the recv).  On the flip side, packets can get fragmented for various reasons and you'll receive part of it initially and the rest later (but you'll be guaranteed to receive all of it in the correct order as long as you don't get disconnected).  The receiver's job is to packetize the stream that it gets; for some protocols a "packet" can be assumed to end at a new-line character.  For others, it might be a fixed length (of 1 or some other number) or it might be read off of the first few bytes of a known sync point.

Zakath is closer to how it can be implemented simply and elegantly.  However, he does not account error conditions.

As Skywing pointed out, it's better to implement the receiver in a class, but it should be in the communications/sockets class, not the bot class.  Aside from being cleaner, it'd also make it more portable since you could do something like:

case FD_READ:
 if((conn=lookup(s)))
   conn->Receive();

for async communications under Windows, and a:

select/poll(....) ...
... (handle select errors)
if(FD_ISSET(....)) {
  if((conn=lookup(s)))
    conn->Receive()
}

for synchronous communications under Windows/Unix/Linux without having to do major rewrites or cut/pastes (and having to maintain multiple versions of it if you find out your receiver had a bug in it).

A better receive implementation would be (basing it off of Zakath's code):


  int n;
  n = recv( ZakBot.GetSocketHandle(), (char *)(RecvBuffer + BufferLen), sizeof(RecvBuffer) - BufferLen, 0);
  if(-1==n) {
     if(EINTR==errno || EAGAIN==errno || EWOULDBLOCK==errno)
        // got here by mistake or got interrupted so do nothing
        return;
     // I/O error; close the connection
     ZakBot.Close();
     return;
  }

  BufferLen += n;

  while ( BufferLen >= 4 ) {
     // start of packetizer
     WORD PacketLen = *(LPWORD)( RecvBuffer + 2 );
     if ( PacketLen > BufferLen ) {
        // buffer is too small to handle the packet or probably something wrong (maybe we're desynced?), just close the connection
        ZakBot.Close();
        return;
     }

     //here you deal with the packet (process or queue it here)
     ZakBot.QueuePacket(RecvBuffer, PacketLen);

     // update buffer
     BufferLen -= PacketLen;
     memmove( RecvBuffer, RecvBuffer + PacketLen, BufferLen );
  }

It can be improved to be thread safe and work with more than just the ZakBot connection (it should actually be in its own communications class and not some bot class) with a global buffer common to all bot connections (bad!).  If it were handling high-traffic I/O, using a circular queue might be better than doing a simple memmove for each packet.  For a single bot, the memmove is enough and shouldn't warrent having a much more complicated circular receive queue.  1000 bots with constant I/O for each is another story....

Quote from: Noodlez on May 05, 2003, 09:13 AM
sometimes bnet won't send you the complete packet, that's why there's a length field. instead of discarding partial packets, wait for the rest of the data and complete the packet.

and because it can send multiple packets at once