Crowbar Your Favorite Library for Fun and Bugfixes

Page content

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:

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:


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:

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:

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:

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:

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:

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.

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.