Arriving At the Mirage

When last we left our hero, I was strugging valiantly to get a Mirage unikernel version of this blog running on Amazon EC2. All unikernels built and shipped off to EC2 would begin booting, but never become pingable or reachable on TCP port 80. ec2-get-console-output on any instance running a Mirage unikernel would show the beginning stages of a DHCP transaction, then the disappointing RX exn Invalid_argument("String.sub"), then… silence.

When all you had for many years was a hammer, stuff is still going to look an awful lot like nails to you, even if it’s pretty distinctly screw-shaped. I wanted to take a packet trace of this transaction pretty badly. I could do three things that were almost like this:

  • get a packet trace of another machine getting a DHCP lease on EC2
  • get a packet trace of a unikernel getting a DHCP lease on my local Xen server
  • print out an awful lot of diagnostic data from the EC2 unikernel and read it from the console

Trying to draw some conclusions from the first option above led me down the wrong path for about a day or so. I did manage to cause the DHCP client to fail on my local Xen server by sending a DHCP reply packet with no server-identifier set, using scapy and some hackery to cause the xid to always match:

>>> bootp_reply=BOOTP(yiaddr="192.168.2.20",op=2,xid=0x7fffffff)
>>> reply_packet=(IP(src="192.168.2.1",dst="192.168.2.255")/UDP(sport=67,dport=68)/bootp_reply/DHCP(options=[("message-type","offer"),"end"]))
>>> reply_packet.show()
###[ IP ]###
  version= 4
  ihl= None
  tos= 0x0
  len= None
  id= 1
  flags= 
  frag= 0
  ttl= 64
  proto= udp
  chksum= None
  src= 192.168.2.1
  dst= 192.168.2.255
  \options\
###[ UDP ]###
     sport= bootps
     dport= bootpc
     len= None
     chksum= None
###[ BOOTP ]###
        op= BOOTREPLY
        htype= 1
        hlen= 6
        hops= 0
        xid= 2147483647
        secs= 0
        flags= 
        ciaddr= 0.0.0.0
        yiaddr= 172.31.4.46
        siaddr= 0.0.0.0
        giaddr= 0.0.0.0
        chaddr= ''
        sname= ''
        file= ''
        options= 'c\x82Sc'
###[ DHCP options ]###
           options= [message-type='offer' end]

After receiving this packet, the unikernel comes to a dead halt. The expected behavior is to time out after not receiving a response after a certain amount of time. This is a problem (and looking more carefully at the code, the comments even note that it’s a known issue with the current implementation). This is the why the unikernel seems to try to get a lease once, and then never try again. Unfortunately, after doing a packet dump on another, more fully-featured machine getting a DHCP lease on EC2, I determined that it’s not the problem - DHCP leases from the upstream server have a server-identifier set, as they should, so the root cause of the initial failure isn’t explained by this.

On the advice of the wise Katherine Ye, who was visiting Hacker School for Alumni Thursday, I started digging around in code instead of trying to figure out what was going on with a packet dumper and a screwdriver. A simple grep led me pretty quickly to the DHCP option-handling code. This is the only code module that calls String.sub.

Looking at the String documentation, it’s clear why one might get an exception from String.sub; it’s possible to call it with arguments which are outside the bounds of the string. (In other words, if you ask “Please give me 10 letters, starting from the 100th letter, from the string I like pies”, the runtime should rightly tell you that this is a nonsensical thing to ask; I like pies doesn’t have a 100th letter. The quality of crashing when this happens, instead of just allowing the program to randomly reference and write to memory that might be outside the bounds of the intended data, is extremely desirable.)

Why is this happening, though? The only call to String.sub is in a function called slice, in the of_bytes function, which is called by Unmarshal. This chunk of code parses through a bunch of DHCP options. DHCP options are generally specified by a code number, a length, and whatever random crap is appropriate for that option (e.g. an IP address, a server name, an MTU size, a web proxy URL, or one of a bunch more).

The actual implementation in dhcpv4_option.ml is written quite imperatively. It begins by beginning at the beginning, which means setting the wodge of bytes representing the DHCP options in a global buffer, setting the variable pos to 0, and moving on in the following fashion:

  • look at the posth single byte in the buffer
  • try to figure out which option the byte corresponds to
  • if the code matches an option we know how to parse, add 1 to pos and run the code corresponding to that option
  • if the code doesn’t match a known option, add 1 to pos and look at the value at that byte, which should be the length of the option. Advance pos that many bytes. (In other words, skip the option.)

Most of the code for parsing a specific option looks a lot like the code for an unknown option: look at the posth byte to find the length, advance pos to find the beginning of the option, and then take as many bytes as you found when you initially examined pos and do something with them. Some of them use slice for this, a convenience function for grabbing some number of bytes off of the buffer, and slice is our String.sub smoking-gun offender.

I added some debug output to slice to attempt to get some useful information around which option, precisely, might be causing this specific problem.

   let slice len = (* Get a substring *)
      printf "About to pull %d characters from %d in a buffer of length %d\n " len !pos (String.length buf);
      if (pos + len) > (String.length buf) || !pos > (String.length buf)  
        then raise (Error (sprintf "Requested too much string at %d %d (%d)" !pos len (String.length buf) ));
      let r = String.sub buf !pos len in
      pos := !pos + len;
      r in

I got some pretty good output indeed from this:

Parsing option type Message typeParsing option type Server identifierAbout to pull 4 characters from 5 in a buffer of length 102
 Parsing option type Lease timeAbout to pull 4 characters from 11 in a buffer of length 102
 Parsing option type Subnet maskAbout to pull 4 characters from 17 in a buffer of length 102
 Parsing option type RouterAbout to pull 4 characters from 23 in a buffer of length 102
 Parsing option type DNS serverAbout to pull 4 characters from 29 in a buffer of length 102
 Parsing option type Host nameAbout to pull 16 characters from 35 in a buffer of length 102
 Parsing option type Interface MTUParsing option type Unknown(220)About to pull 58 characters from 56 in a buffer of length 102
 RX exn Dhcpv4_option.Unmarshal.Error("Requested too much string at 56 58 (102)")

So when parsing an unknown option, we seem to request an unreasonable length of string. I tried to replicate this locally by setting a DHCP option that Mirage doesn’t know about, but Mirage just discards it and keeps on chuggin’. While staring at the unknown option handling code, trying to figure out how this could be, I noticed that the MTU-handling code seemed to be missing something that all the other functions had.

      |`Interface_mtu -> 
          let l1 = getint () lsl 8 in
          cont (`Interface_mtu (getint () + l1))

Nothing examines or moves the pos variable past the first byte of this option, which is the length of the option field. This means that the length will be incorrectly interpreted as the first byte of the MTU length, and the first byte will be incorrectly shifted.

Worse, there’s a leftover byte after this is done parsing. pos is still sitting at what should’ve been taken to be the second byte of the MTU, but instead will be read as a DHCP option code. The next DHCP option code will be taken for a length for that option code, and gamely fed to slice.

I set up my local DHCP server to send a bog-standard Ethernet MTU of 1500 bytes, and I was immediately rewarded with a thunderous crash. At last! Now all we need is a fix:

  |`Interface_mtu ->
          let _ = getint () in (* read length and discard it *)
          let l1 = getint () lsl 8 in
          cont (`Interface_mtu (getint () + l1))

I shove this into the code, recompile, and deploy as fast as I can. (This is an incorrect solution, by the way, and will have the exact same problem with MTU options of size > 2 bytes; the correct solution, which I haven’t yet written, doesn’t just disregard the length of the option.)

And sure enough, it works:

Parsing option type Message typeParsing option type Server identifierAbout to pull 4 characters from 5 in a buffer of length 101
 Parsing option type Lease timeAbout to pull 4 characters from 11 in a buffer of length 101
 Parsing option type Subnet maskAbout to pull 4 characters from 17 in a buffer of length 101
 Parsing option type RouterAbout to pull 4 characters from 23 in a buffer of length 101
 Parsing option type DNS serverAbout to pull 4 characters from 29 in a buffer of length 101
 Parsing option type Host nameAbout to pull 15 characters from 35 in a buffer of length 101
 Parsing option type Interface MTUParsing option type Unknown(58)About to pull 4 characters from 56 in a buffer of length 101
 Parsing option type Unknown(59)About to pull 4 characters from 62 in a buffer of length 101
 Parsing option type BroadcastAbout to pull 4 characters from 68 in a buffer of length 101
 Parsing option type Domain nameAbout to pull 26 characters from 74 in a buffer of length 101
 Parsing option type EndARP: sending gratuitous from 172.31.11.92
DHCP offer received and bound
ARP responding to: who-has 172.31.11.92?
ARP responding to: who-has 172.31.11.92?

That’s the sweetest “DHCP offer received and bound” I’ve ever seen. It’s even serving webpages! I’m able to get the front page of this blog (including the nascent version of this entry!) off the unikernel with no problem.

I have a little more work to do before submitting a pull request, but I’m hoping to do that shortly, and hopefully soon after that my changes will be in the master mirage-tcpip branch. Hooray!

As a final note, my ability to take the time and attention to understand this bug, as well as the wisdom I needed to find it, is in no small part thanks to Hacker School. I recommend it without reservation.