Some Random Idiot

Crowbar Your Favorite Library for Fun and Bugfixes

Crowbar is a tool that combines afl-persistent’s instrumentation with quickcheck-like property-based testing. afl-fuzz is a great tool for detecting crashes, but Crowbar helps us go a step farther and automatically discover inputs which cause our program to no longer have the properties we expect it to have.

For reasons that don’t need exploring at this juncture, I first thought to apply Crowbar to charrua-client, a library which implements the DHCP state machine from a client perspective. Code snippets below are taken from the dhcp directory in my somerandompacket repository on GitHub.

Where to begin?

charrua-client attempts to express a simple API:

1
2
3
4
5
6
7
8
type t
type buffer = Cstruct.t

val pp : Format.formatter -> t -> unit
val create : ?requests : Dhcp_wire.option_code list -> Macaddr.t -> (t * buffer)
val input : t -> buffer -> [ `Response of (t * buffer) | `New_lease of (t * Dhcp_wire.pkt) | `Noop ]
val lease : t -> Dhcp_wire.pkt option
val renew : t -> [ `Response of (t * buffer) | `Noop ]

which can then be used by a specific implementation that sends packets and manages timeouts. With Crowbar, we can randomize the parameters to these functions, and make sure that the properties we expect still hold.

Generators and How to Make Them

In order to do much with the code above, we’ll need to get a Dhcp_client.t, and the only way to do that is via Dhcp_client.create, which needs a Macaddr.t (six bytes corresponding to a MAC address) and a Dhcp_wire.option_code list (a list of DHCP options to request in the initial message). To start with, we can write a Crowbar generator for a Macaddr.t, a generator for Dhcp_wire.option_codes, and use those as arguments to Dhcp_client.create:

1
2
3
4
5
6
7
8
9
10
let macaddr : Macaddr.t Crowbar.gen =
  Crowbar.Map (Crowbar.[uint8; uint8; uint8; uint8; uint8; uint8], fun a b c d e f ->
  Macaddr.make_local @@ function
    | 0 -> (a land 252)
    | 1 -> b | 2 -> c | 3 -> d | 4 -> e | _n -> f
  )

let opt_code : Dhcp_wire.option_code gen =
  Crowbar.Map (Crowbar.[uint8], fun a -> match Dhcp_wire.int_to_option_code a with
    | None -> bad_test () | Some o -> o)

Given macaddr and opt_code generators, we can then use Dhcp_client.create to get a client and a suggested first message. We can check to see whether the message asks for the option codes as we expect:

1
2
3
4
5
6
let discovering_clients_ask_for_opt_code () =
  Crowbar.add_test ~name:"discovering_clients ask for the given option codes"
    Crowbar.[macaddr; List1 opt_code] @@ fun m o ->
    let (_c, b) = Dhcp_client.create ~requests:o m in
    let b = really_parse b in (* a helper function for parse failures *)
    Crowbar.check_eq (Dhcp_wire.find_parameter_requests b.options) (Some o)

The generators for Dhcp_wire.pkt are fairly complicated because nearly all possible option types are handled — if you’re interested, you can see generators.ml in the source repository for the code discussed here.

Useful Properties to Test

To construct more tests for charrua-client in Crowbar, it’s necessary to think about the properties a client should have. Here are some simpler ones:

  • clients generate DHCPDISCOVER packets that ask for the options specified in create (we made a test fort this above)
  • clients which have not received input don’t have a lease
  • clients which have received only one input frame don’t have a lease
  • clients only change their state in response to messages where the xid matches the one the client expects

state :(

A troublesome feature of code which includes a state machine is some dependency on state. Since the client’s reaction to various inputs is not purely expressed by the code and the input alone, but is also a function of the current state (and therefore the set of previously-sent input which was accepted), it’s helpful for us to include tests which get the client into various states. Then we can quickly discover new paths, rather than having to wait for the fuzzer to discover sets of input which result in them from the initial state. (When using afl-fuzz, this is commonly done by including examples of input which advance the state machine in the in/ directory, so that afl-fuzz’s mutation of the input begins from an “interesting” point.)

Notably, the t in our Dhcp_client module is abstract, and no interface to the current state of the client is exposed. A user of the Dhcp_client module can only find out whether a client has a lease or doesn’t, and what to do in response to input. It’s tempting to expose the state directly for easier testing (e.g., “after calling input with a DHCPOFFER packet, the state is REQUESTING”), but that information isn’t necessary to expose in common use — we want our library to make the right decisions, not to punt them to the user. Instead, we can use “generates a new response or notes a new valid lease” as a proxy for “changed state”.

We also want to make an assertion about the client: that given a server that responds “reasonably” to client requests, the client’s state also advances as we’d expect it to. In more concrete terms, we want to assert that usually, the following conversation happens:

1
2
3
4
CLIENT: DHCPDISCOVER
SERVER: DHCPOFFER
CLIENT: DHCPREQUEST
SERVER: DHCPACK

and that when the client hears DHCPACK, it notes that it now has a valid lease and exposes this information to any caller.

In other words, the test we want to write is:

  • the client and a server negotiate a lease in four messages

In order to write such a test, we need to have some “reasonable” server. Luckily, the Dhcp_server module in charrua-core.server exposes the configuration record, so we can automatically generate one in Crowbar:

1
2
3
4
5
6
7
8
9
10
11
let range_server : Dhcp_server.Config.t Crowbar.gen =
  Crowbar.Map (Crowbar.[Generators.macaddr; Generators.ipv4_prefix], fun m network ->
    Crowbar.guard (Ipaddr.V4.Prefix.bits network < 30);
      (* need room for our ip + at least one in the range *)
    let ip = Ipaddr.V4.Prefix.network network in
    let range_low = Ipaddr.V4.(of_int32 @@ Int32.add 1l @@ to_int32 ip) in
    let range_high = Ipaddr.V4.(of_int32 @@ Int32.sub (to_int32 @@ Prefix.broadcast network) 1l) in
      Dhcp_server.Config.make ?hostname:None ?default_lease_time:None
      ?max_lease_time:None ?hosts:None ~addr_tuple:(ip, m) ~network
         ~range:(Some (range_low, range_high)) ~options:[]
  )

As a precondition for the test we’d actually like to write, it’s sensible to write a more basic one first:

  • the client and server generate messages which are mutually intelligible

which looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
let client_intelligible_by_server () =
  Crowbar.add_test ~name:"fresh client and server can communicate without sharing config"
  Crowbar.[range_server; discovering_client] @@ fun s (_c, client_output) ->
     let dhcpdiscover = really_parse client_output in
     Crowbar.guard (Dhcp_server.Input.for_us s dhcpdiscover);
     match Dhcp_server.Input.input_pkt s
       (Dhcp_server.Lease.make_db ()) dhcpdiscover 0l with
     | Dhcp_server.Input.Reply _ -> Crowbar.check true
     | Dhcp_server.Input.Silence
     | Dhcp_server.Input.Update _ -> Crowbar.check false
     | Dhcp_server.Input.Warning s
     | Dhcp_server.Input.Error s ->
         (Printf.eprintf "something bad happened: %s\n%!" s; Crowbar.bad_test ())

and once this passes, we can do something more complicated:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
let lease_in_four () =
  Crowbar.add_test ~name:"four message exchanges gets us a lease"
  Crowbar.[range_server; discovering_client] @@ fun s (c, send_me) ->
    let really_input s db buf time =
      match Dhcp_server.Input.input_pkt s db buf time with
      | Dhcp_server.Input.Reply (dhcpoffer, db) -> (dhcpoffer, db)
      | Dhcp_server.Input.Silence
      | Dhcp_server.Input.Update _
      | Dhcp_server.Input.Warning _
      | Dhcp_server.Input.Error _ ->
        Crowbar.bad_test ()
    in
    let err_no_response pkt =
      Error (fun ppf () -> Crowbar.pp ppf "no response to %s" @@
      Dhcp_wire.pkt_to_string pkt)
    in
    let time = 0l in
    let dhcpdiscover = really_parse send_me in
    let (dhcpoffer, db) = really_input s (Dhcp_server.Lease.make_db ()) dhcpdiscover time in
    match Dhcp_client.input c (Dhcp_wire.buf_of_pkt dhcpoffer) with
    | `Noop -> err_no_response dhcpoffer
    | `New_lease (_c, lease) ->
      Error (fun ppf () -> Crowbar.pp ppf "client thought dhcpoffer gave it a lease %s" @@
      Dhcp_wire.pkt_to_string lease)
    | `Response (c, dhcprequest) ->
      let dhcprequest = really_parse dhcprequest in
      let (dhcpack, _db) = really_input s db dhcprequest time in
      match Dhcp_client.input c (Dhcp_wire.buf_of_pkt dhcpack) with
      | `Noop -> err_no_response dhcpack
      | `Response (_c, wat) ->
        Error (fun ppf () -> Crowbar.pp ppf "response to dhcpack: %s" @@
        Dhcp_wire.pkt_to_string (really_parse wat))
      | `New_lease (c, l) -> Crowbar.check_eq (Dhcp_client.lease c) (Some l)

Bonus Testing: charrua-core

charrua-client is, at its heart, a fairly simple wrapper around charrua-core. In particular, charrua-client mostly exposes interfaces which deal with input and output in terms of buffer (which is a Cstruct.t), but charrua-client itself immediately calls Dhcp_wire.pkt_of_buf on the Cstruct.t supplied to input, and similarly calls Dhcp_wire.pkt_to_buf on a constructed pkt just before returning a Response. Several of the tests above hinted at inconsistent behavior in pkt_of_buf and pkt_to_buf, so perhaps some direct testing is warranted.

Dhcp_wire.pkt is exposed in Dhcp_wire’s public interface, so we can write a generator for Dhcp_wire.pkts. (The generator for pkts is quite a bit more involved than any of the generators above, as it also includes reference to a generator for Dhcp_wire.dhcp_options, a type with over 100 variants.)

A common test for sets of functions like pkt_to_buf and pkt_of_buf is to see whether the pkt is the same after being serialized and then deserialized. Hopefully, a round-trip through pkt_to_buf and pkt_of_buf won’t gain or lose any information.

1
2
3
4
5
6
7
8
9
10
11
let serialize_deserialize () =
  let pp fmt pkt =
    Format.fprintf fmt "%s" @@ Dhcp_wire.pkt_to_string pkt
  in
  Crowbar.add_test ~name:"records print/parse and are the same"
  Crowbar.[Generators.packet ()] @@ fun pkt ->
  let serialized = Dhcp_wire.buf_of_pkt pkt in
    let deserialized = really_parse serialized in
    Crowbar.check_eq ~pp ~cmp:(fun a b ->
      String.compare (Dhcp_wire.pkt_to_string a) (Dhcp_wire.pkt_to_string b)
    ) pkt deserialized

The full test suite includes a few more tests which are less visually interesting (or too long to reproduce here!).

Findings

  • charrua-client’s API wasn’t sufficient for the user to make the correct decision about what to do given arbitrary inputs (diff)
  • charrua-core parsed some options which contained lists incorrectly: (#49, #54, #55)
  • charrua-core looked for the flags field of the DHCP header at the wrong offset: (#51)
  • charrua-core didn’t have parity between the DHCP options it was possible to emit and those it understood (#50, #52)
  • charrua-core had a few typos in its option code processing, meaning some options couldn’t be expressed and some would be expressed counter to intentions (#53, #48)
  • charrua-core valiantly attempted to serialize empty lists in some cases where the spec disallows it (#47, #48)

A number of these bugs would have had bad implications had they been in a program written in a language that wasn’t memory safe.

After my experiences with charrua-core’s predecessor, I was very impressed by how hard I had to try to find bugs in charrua-core. I was additionally impressed by how easy it was to fix said bugs once I had discovered them — generally it took only minutes or tens of minutes to discover and isolate the problem, and the fix was fairly obvious. I would caution against concluding that charrua-core is a low-quality library based on these findings; it is very hard to write software that doesn’t have any bugs. If you think you’ve done so, I recommend seeing whether Crowbar agrees!

Acknowledgements

Thanks to Stephen Dolan for Crowbar, Christiano Haesbaert and Gina Maini for charrua-core, and to Thomas Leonard and Hannes Mehnert for comments on this post.

A Quick Guide to Quick Changes in MirageOS

MirageOS is a collection of libraries and a system for assembling them into unikernels. What happens if you want to make changes to those libraries and test them with a new unikernel?

Say, for example, I have a static website (like this blog) that I build in MirageOS. I want to make some changes to the TCP implementation against which the blog is built. In order to do that, I need to do all the following:

  • figure out which module to change
  • figure out which package provides that module
  • get the source for that package and instruct the package manager to use it instead of the release
  • make changes
  • reinstall the package with your changes
  • rebuild the unikernel completely
  • see whether changes had the desired effect

Here’s a quick primer on how.

OCaml Workshop and Strange Loop Talks

As a result of great encouragement from colleagues and friends, I gave a few talks in September.

Persistent Networking with Irmin and MirageOS, which I gave at the OCaml Workshop, is a talk on sticking a persistent database into various levels of the network stack. (It includes demonstrations from What a Distributed, Version-Controlled ARP Cache Gets You, as well as an Irmin-ified NAT device that I haven’t yet written up here.) The slides for my OCaml Workshop talk are also available.

Non-Imperative Network Programming, which I gave at Strange Loop, is a talk on building better abstractions for network communications, and how library operating systems make these constructions possible. The slides for my Strange Loop talk are available; for speaker notes, see the raw content.md. Those interested in learning more about library operating systems and unikernels in this context might be interested in a more configuration-focused piece on the MirageOS modular network stack from last year, or the MirageOS network stack code repository itself.

I’m grateful to my friends at the Recurse Center and OCaml Labs for their support in these endeavors and others.

Fun With Opam: Advice to My Past Self

Most instructions on how to get started with OCaml packages now advise the user to get started with opam, which is excellent advice. Getting up and running with opam is pretty easy, but I wasn’t sure where to go from there when I wanted to modify other people’s packages and use the modifications in my environment. I wish I’d realized that the documentation for making packages has a lot of applicable advice for that use case, as well as the apparent target (making your own packges from scratch).

Most of the documentation on opam seems to focus on its use as a dependency manager, but it’s also capable of providing many virtual environments via opam switch. Often buried in documentation is the very useful opam switch --alias-of, which one can use to make new virtual environments using a standard OCaml compiler. Most of my current switches are based off the 4.02.1 compiler (just a bit short of up-to-date), so I make new switches for projects with opam switch new_project --alias-of 4.02.1.

I wish, also, that I’d started writing opam files for my own projects and installing them locally via opam pin sooner. The earlier I do this, the less likely I am to publicize a repository with missing or broken dependencies, and it reduces the friction of sharing early-stage code with other people. Combined with the switch-per-project approach, having opam files ready means you can easily have fresh switches with the minimal amount of dependencies installed; you can also install a minimal set of reverse-dependencies (if any!), to limit the amount of time you spend waiting for downstream packages to recompile when you want to test a change. I have great sorrow when I think back on the number of times I waited through a complete recompile of all zillion packages that depend on mirage-types when I really only wanted to test tcpip; a switch that doesn’t have mirage-console-unix and friends installed won’t try to recompile them, and I won’t have to spend any minutes of my only life waiting for that compilation to finish.

Having a lot of switches does lead to some confusion, since executing opam switch results in a filesystem change in the user’s .opam directory but can’t enforce the change in all open terminals. The problem is compounded by the requirement to eval $(opam config env) after running opam switch — if the user forgets to do this, opam switch will report the expected branch, but any commands that try to use the configuration will use the values for the previous switch. After having been caught out by this a few times, I caved and customized my command prompt to report on the current actual switch (along with the current git branch):

1
2
3
4
5
6
7
8
9
function git-current-branch {
  git branch 2> /dev/null | sed -e '/^[^*]/d' -e 's/* \(.*\)/() /'
}
function opam-sw {
  # this is pretty brittle but good enough
  # have to adjust last cut if .opam is not /home/username/.opam or similar depth
  echo $CAML_LD_LIBRARY_PATH|cut -d: -f 1|cut -d'/' -f 5
}
export PS1="[\$(opam-sw)] \$(git-current-branch)$PS1"

It’s embarrassing to admit how many times I was confused by the apparently nonsensical output of make and opam install before I made this change, but at least that’s decreased since I started showing myself this information by default.

Something that still trips me up, though, is the setup.data file created by projects that use oasis to generate build files. setup.data contains cached information on how to build projects, including full paths to compilers and libraries, which isn’t updated if you use opam switch. When I began writing this post, my “solution” for this was compulsively removing setup.data every time there’s a weird-looking problem building a project that uses oasis, but writing I’ve been inspired to do better by making another adjustment:

1
2
3
4
5
6
7
8
9
10
11
12
function setup-data {
  grep -E "^standard_library=" setup.data 2>/dev/null|cut -d'/' -f5
}
function opam-sw {
  setup=$(setup-data)
  switch=$(echo $CAML_LD_LIBRARY_PATH|cut -d: -f 1|cut -d'/' -f 5)
  if [ -n "$setup" ] && [ "$switch" != "$setup" ]
  then echo "(!!! setup.data $switch)"
  else echo $switch
  fi
}
export PS1="[\$(opam-sw)] \$(git-current-branch)$PS1"

Now my prompt will warn me when setup.data and my current switch conflict, as they do in the following example where I last built mirage-tcpip in the separate-arp-tcpip switch:

1
2
[4.02.1] user@computer:~$ cd mirage-tcpip
[(!!! setup.data 4.02.1)] (separate_arp) user@computer:~/mirage-tcpip$ 

This hasn’t saved me any grief yet, but I’m sure it will soon enough.

Retrospective

In 2014, I spent 12 weeks at the Recurse Center, formerly (and at the time) known as Hacker School. After finishing up my time there in May of that year, a lot of people asked me reasonable questions like:

  • How was the Recurse Center?
  • Was attending RC worth your time?
  • What did you learn at the Recurse Center?

My response to these questions was “I don’t know yet! It’s too early to say.” Now that more than a year has passed, I think I might have some idea of where to start.

What a Distributed, Version-Controlled ARP Cache Gets You

git (and its distributed version control system friends hg and darcs) have some great properties. Not only do you get a full history of changes on objects stored in them, you can get comments on changes, as well as branching and merging, which lets you do intermediate changes without messing up state for other entities which want to work with the repository.

That’s all pretty cool. I actually want that for some of my data structures, come to think of it. Say, for example, a boring ol’ key-value store which can be updated from a few different threads — in this case, a cache that stores values it gets from the network and the querying/timeout code around it. It would be nice if each thread could make a new branch, make its changes, then merge them into the primary branch once it’s done.

It turns out you can totally do that with Irmin, “the database that never forgets”! I did (and am still doing) a bit of work on sticking a modified version of the MirageOS address resolution protocol code’s data structures into Irmin:

1
2
3
4
5
6
7
8
9
10
11
$ git log --all --decorate --oneline --graph
* 68216f3 (HEAD, primary, expire_1429688434.645130) Arp.tick: updating to age out old entries
* ec10c9a entry added: 192.168.3.1 -> 02:50:2a:16:6d:01
* 6446cef entry added: 10.20.254.2 -> 02:50:2a:16:6d:01
* 81cfa43 entry added: 10.50.20.22 -> 02:50:2a:16:6d:01
*   4e1e1c7 Arp.tick: merge expiry branch
|\
| * cd787a0 (expire_1429688374.601896) Arp.tick: updating to age out old entries
* | 8df2ef7 entry added: 10.23.10.1 -> 02:50:2a:16:6d:01
|/
* 8d11bba Arp.create: Initial empty cache