Category Archives: Python

The easy way to get started with property based testing

There seems to be a common impression that property based testing is really for when you have code that manipulates perfect platonic objects with elegant algebraic relationships between them.

And, well, don’t get me wrong. When you do have those, property-based testing really shines. It’s an incredibly powerful way to test them, and it works really well.

But… that’s mostly because this is a realm that is incredibly easy to test compared to the complexity of getting it right, so almost anything you can do to improve your testing will help it. It’s less that that’s what property based testing is good for, and more that it’s easy to try new things when you’re playing testing on easy mode.

Here’s a recipe for getting started when you’re not playing testing on easy mode:

  1. Pick a function in your code base that you want to be better tested
  2. Call it with random data

This will possibly require you to figure out how to generate your domain objects. Hypothesis has a pretty extensive library of tools for generating custom types, but if you can try to start somewhere where the types you need aren’t too complicated to generate.

Chances are actually pretty good that you’ll find something wrong this way if you pick a sufficiently interesting entry point. For example, there’s a long track record of people trying to test interesting properties with their text handling and getting unicode errors when text() gives them something that their code didn’t know how to handle (The astral plane: It’s not just for D&D).

You’ll probably get exceptions here you don’t care about. e.g. some arguments to functions may not be valid. Set up your test to ignore those.

So at this point you’ll have something like this:

from hypothesis import given, reject
 
@given(some(), strategies())
def test_some_stuff(x, y):
    try:
       my_function(x, y)
    except (Ignorable, Exceptions):
       reject()

(reject simply filters out the example – you’re trying to find a large number of examples that don’t raise any of those exceptions).

This is already a pretty good starting point and does have a decent tendency to flush out bugs. You’ll often find cases where you forgot some boundary condition and your code misbehaves as a result. But there’s still plenty of room to improve.

There are now two directions you can go in from here:

  1. Try to assert some things about the function’s result. Anything at all. What type is it? Can it be None? Does it have any relation at all to the input values that you can check? It doesn’t have to be clever – even very trivial properties are useful here.
  2. Start making your code more defensive

The second part is probably the most productive one.

The goal is to turn faulty assumptions in your code into crashes instead of silent corruption of your application state. You can do this in a couple ways:

  1. Add argument checking to your functions (Hypothesis uses a dedicated InvalidArgumentException for this case, but you can raise whatever errors you find appropriate)
  2. Add a whole bunch of assertions into your code itself

Even when it’s hard to reason about formal properties of your code, it’s usually relatively easy to add local properties, and assertions are a great way to encode them. I like this post by John Regehr on the subject.

This approach will make your code more robust even if you don’t find any bugs in it during testing (and you’ll probably find bugs in it during testing), and it gives you a nice easy route into property based testing by letting you focus on only one half of the problem at a time.

And, of course, if you’re still having trouble getting started with property-based testing, the other easy way is to persuade your company to hire me for a training course. Drop me an email if you’re interested.

This entry was posted in Hypothesis, programming, Python on by .

Hypothesis progress is alarming

I had a brilliant idea just now:

08:54 <DRMacIver> shapr: So I’ve been thinking about your point that you have to save pre-shrinking state because you might have found multiple bugs, and I think it’s wrong.
08:54 <DRMacIver> Because I think you’re much more likely to have found those other bugs in the course of shrinking than you are with the original value
08:54 <DRMacIver> So what will happen if you save the pre-shrinking state is that it’ll rerun and go “Yup, that’s fine”
08:54 <DRMacIver> My solution of saving the post-shrinking state is *also* wrong in this case mind you.
08:55 <DRMacIver> I think I have a solution, but it relies pretty heavily on glassbox testing in order to be any good
08:57 <DRMacIver> I have a really frustrating level of future designs for Hypothesis in my head.
08:58 <DRMacIver> (frustrating because I can tell how far I am from implementing it, and every time I get closer I come up with new ones so the goal recedes into the distance)
09:22 <DRMacIver> Ooh. I’ve just had a *great* idea
09:23 <DRMacIver> It not only solves this problem it solves a bunch of historic problems too
09:24 <DRMacIver> Basically 1) save every interesting example in the database. 2) examples loaded from the database which are valid but uninteresting “radioactively decay”. I.e. they get deleted with some probability once they’ve been run

The context: Both Haskell’s QuickCheck and Hypothesis save the last failing example. QuickCheck saves it prior to minimization, Hypothesis saves it post minimization. Because of the issues pointed out in Reducers are Fuzzers, both are the wrong thing to do.

Additionally, Hypothesis has historically had the following problems:

  • What do you do when the database fills up with more examples than you know what to do with in a given run and none of them are interesting?
  • What do you do if the shrinker gets stuck or the process crashes before you’ve saved the example?

This solves both problems: We save every intermediate shrink as we find it and let the garbage collection process deal with the debris that subsequently proves uninteresting.

The above is a clever idea but is not the point of this post: The point of this post is that I have a growing sense that I am missing something.

Basically there is no reasonable way that I should be making as much progress on Hypothesis, Conjecture, etc as I am. This is not the first brilliant idea – I’ve had dozens. I’ve had so many brilliant ideas that I haven’t had time to implement all of them yet.

This is  bad sign.

There are three ways to make an astonishing amount of progress:

  1. Be wrong about the amount of progress you are making
  2. Be an unparalleled genius
  3. Be where the low hanging fruit is

I do not think I am wrong about the amount of progress I’m making. I will grant that some of my ideas turn out to be bad ones, or modifiable to make them good ones, but I’ve had enough practical validation that I’m reasonably sure that a lot of these concepts work and are useful. I’m probably off by a factor of two or three, but I doubt I’m out by an order of magnitude.

I am not an unparalleled genius. I am smart, but I’m one in a thousand, not one in a million. There are plenty of other people smarter than me, many of them working in similar fields.

So the only real option is that I’m hanging out in an orchard full of low hanging fruit, and I don’t really understand how that could be. Right now, life feels a bit like James Mickens describes in The Slow Winter:

I think that it used to be fun to be a hardware architect. Anything that you invented would be amazing, and the laws of physics were actively trying to help you succeed. Your friend would say, “I wish that we could predict branches more accurately,” and you’d think, “maybe we can leverage three bits of state per branch to implement a simple saturating counter,” and you’d laugh and declare that such a stupid scheme would never work, but then you’d test it and it would be 94% accurate, and the branches would wake up the next morning and read their newspapers and the headlines would say OUR WORLD HAS BEEN SET ON FIRE

I keep coming up with genuinely useful ideas with practical significance that work really well, and it all feels too easy.

There are a number of reasonable hypotheses about how this could be the case:

  1. I had one clever idea that unlocked everything else.
  2. Nobody cares about this problem, so they haven’t bothered to pick the fruit.
  3. I am ignoring giant swathes of prior art that I just don’t know exist because I’m an outsider to this field and couldn’t find on a google search because competence or academic firewall of doom.
  4. I am ignoring huge swathes of prior art because nobody has ever bothered to write it down or it’s locked up in proprietary tools.

Obviously the first is the one that I hope it is. To some extent I even have a plausible candidate for it: The idea that having data generators work on an intermediate representation of the final result rather than the final result directly would be useful. But this isn’t actually a very clever idea. It’s proven very fruitful, but it’s sufficiently obvious that it should have occurred to someone else before.

Two seems plausible. e.g. the idea I started out with is only really interesting if you want to integrate this sort of testing with normal testing workflows, which I do and some other people do but not many people who get to do full time research on this do. The conjecture concept only really matters if you’re trying to make these ideas work in imperative languages. etc. I’m in enough intersections that it’s at least plausible that nobody has cared about this intersection before. Additionally, my impression is that random testing isn’t very interesting to academics and most of the people who have put a lot of work into it are security researches, who have rather different focuses than I do.

So those are the optimistic scenarios. Both are a little depressing because it suggests there just hasn’t been enough interest in something that massively improves software quality to do even the level of research I’ve put into it, but at least they suggest I’m not wasting my time.

But I really can’t rule out 3 and 4, both of which are worrying.

The prior art I am mostly aware of and have based my work on is:

And I’m semi aware of but have consciously decided not to use the work on concolic testing, etc.

But I can’t help but feel there’s a lot more out there.

So, um, halp. Any prior art you can send me on the general subject of random testing, etc. would be very appreciated. Papers or working software or random blog posts that someone thought of a thing. It’s all good.

This entry was posted in programming, Python on by .

Superposition values for testing

Cory was talking about using AFL to fuzz test hyper-h2 the other day.

We talked about the difficulty of building a good starter corpus, and I thought I’d pull out some old code I had for using glassbox to do this.

It proceeded to fail utterly.

The problem is that H2 is a complex protocol which is very hard to basically probe through due to the number of different interactions. Simply throwing bytes at it just to see what happens is unlikely to do anything useful. This is similar to why historically that approach worked will with binaryornot and chardet, but was pretty rubbish on pyasn1.

Yesterday evening I thought about this problem a bit more and then started giggling. This is usually a bad sign.

The idea I’d come up with was this: What if we use a custom type to hold off on deciding the values until the last possible minute. That way we can get values that do interesting things to the internals of complex protocols by looking at the questions that the parser asks about the values and deciding what the answer is then rather than immediately.

The way this works is that you have a mock object that internally is saying “I am one of these values but I don’t know which”. Every time you perform a comparison it picks a possible answer at random and uses that to narrow down the list of possible values. At the end, your program should have behaved as if there had just been a really well chosen initial set of integers.

It turns out to work pretty well based on brief experimentation. My initial prototype didn’t support anything more than comparison operators, but after some further pondering I got it to support arbitrary arithmetic expressions. And thus, I present schroedinteger.

>>> x = schroedinteger({1, 3, 7})
>>> y = schroedinteger({-1, 1})
>>> z = x * y
>>> z
indeterminate: {-7, -3, -1, 1, 3, 7}
>>> x == 1
False
>>> x == 3
False
>>> z
indeterminate: {-7, 7}
>>> z == -7
True
>>> z
-7
>>> y
-1

The way this works is to separate out concepts: You have observables which are basically just a list of possible integers that get whittled down over time, and you have schroedintegers, which consist of:

  1. A set of observables they are interested in
  2. A function which maps an assignment of those observables to integers to a concrete integer

So when you perform arithmetic operations on schroedintegers it just creates a new one that shares the sets of observables of the two sides and evaluates both.

Every time you observe something about the system it looks at the set of possible answers, picks an answer uniformly at random from the results, and then collapses the state of possibilities to only those that would have produced that answer, and then returns it.

Performance is… OK. Where by OK I mean “not very good”. The set of heuristics used keep it manageable, but no better than that.

It could be improved if I really cared, but right now this project is a bit of a toy. In particular most operations are currently O(m * n). Many of these could be fixed to not be quite readily with a little more work – currently the implementation is very generic and many of the operations admit a nicely specific implementation that I haven’t used. e.g. a thing that would be pretty easy to do is to track upper and lower bounds for every schroedinteger and use those to exclude many possibilities.

I also investigated using Z3 to do this. It would be an interesting backend that would remove the most of the limitations. Unfortunately the results were really slow and kinda crashy (I had at least one hard to minimize segfault), so I’ve given up on that for now.

All told, an interesting result for about a day of hacking. Right now I plan to leave it where it is unless I come up with a particularly interesting use case. Let me know if you have one.

 

This entry was posted in programming, Python on by .

How to help your favourite open source project

So, you’re an engineer at FooCorp, or the hot new startup Barrrrr. You use a lot of open source, and you feel like your company isn’t really giving back enough to the community for the benefit it’s receiving. You feel generically guilty about this but aren’t really sure what to do about it, and aren’t really sure what the developers of those open source projects need or want.

As a developer of a reasonably popular open source library, I can tell you what I want from my corporate users:

It’s money. I’d like money.

This isn’t because I’m greedy and want to be swimming in a giant vault full of coins. I mean I’d not say no to the vault of coins, but if that was what I wanted there are a lot better ways to get there. The reason I want money to work on open source is that I want to work on open source, and I require money in order to survive. I think making it your day job is the dream of most of us who work on open source, but very few of us get to do that.

The thing is, I don’t want your money. People occasionally ask me how they can donate, and the answer is that they can’t. It’s just not a viable model. Individuals can’t and shouldn’t really donate enough money to make funding open source work viable. Things like Patreon work great if you’re doing something with sufficient mass appeal that you’ve got thousands of users willing to donate. Very few open source projects are in this category, and even if they were, I wouldn’t really feel any better about companies making profits off their employees’ individual donations than I would about them making profits off my free labour.

Companies could donate. Ned Batchelder wrote about this recently. He’s more optimistic about this than I am. Most companies can’t even be persuaded that they should upstream patches they make to open source, let alone that they should give their hard-earned money away.

So, what I would like instead is for companies to pay open source developers for services: Support contracts, custom development, training, etc. Long-term, this isn’t optimal, but it works now, which as someone who exists now rather than in the future, let me tell you is a big plus.

So what can you,  the aforementioned engineer at FooCorp/Barrrrr do in order to make this possible?

You might think that the answer is “advocate for it internally”. After all, you don’t have control of budget, so the thing to do here is to persuade people who do.

This can work, but it’s quite hit or miss. It can expend a lot of political capital, and you’re often not the best placed to argue for it.

Instead I would like to propose a simpler solution: Make introductions.

As an open source developer, the single most useful thing you can do for me if you do not yourself have control of budget is introduce me to someone who does. Ideally someone reasonably technical – if you’re a small enough company that you have access to the CTO, the CTO is a perfect person to do introductions to. If not, development managers or people who organise training are also great choices.

How do you do this?

Well, it’s quite straightforward:

To the CTO/etc: We’re using some projects that we think we could be using it more effectively, which would save us a lot of time and effort. Would you be up for an introduction to the developers of some of these projects to talk about how they can help us do so?

To the developers: We’re using your project. We’d like to give you money in exchange for your helping us use it more effectively. Is this a thing you would be interested in talking to someone over here about that?

The developers might say no, and that’s OK. Especially people who have full time jobs may not be able to find the time for this. But it can never hurt to ask, and I think most of us will say yes.

The CTO/etc might say no, but they shouldn’t. The maths is very simple: You have a lot of developers. Learning is slow and developers are expensive. If you can save each of those developers 1-2 days of time, that’s N-2N developer days of money saved. Paying an expert for a couple of days of even very well paid work is likely to cost you significantly less than that. Pointing this out to them may be useful.

Pointing out the sort of numbers involved to the open source developers in question may also be useful. It certainly would never have occurred to me prior to getting some experience in this area that offering training days for £2000 would actually be a huge discount (by the way, I’m offering said discount until January 22nd 2016, so now is an especially good time to make those intros).

Note: You don’t have to convince anyone to do work or pay money. All you have to convince them of is the idea that it might be worth doing this, and that it’s worth talking about the possibility.

Sometimes this will work out, sometimes it won’t, but in the cases where it doesn’t there was probably very little you could have done that would have worked, and in the cases where it does work you’ve saved your company a large chunk of money and given back to the project that is helping you, all for really very little effort.

You don’t have to restrict this to companies you work at either! Mentioning this to your friends at other companies can be very helpful too: “Hey, I remember you saying you had $PROBLEM. Well we’re using $PROJECT for something related. Why don’t you check it out? The authors are generally available to help you out if you need some assistance getting started, and for a very reasonable price”.

Ultimately, on our side, this is the “turn your open source software into a consultancy” model, and it doesn’t work for everyone, but I think a lot more of us would be doing it if we thought we could, and for those of us who already are, making those introductions is incredibly useful, easy to do, hugely appreciated.

Or, in other words: Take me to your leader. Please?

This entry was posted in programming, Python on by .

Let’s help people go to PyCon Namibia

PyCon Namibia is coming up. I think it’s a great idea and I’m planning to go.

I’m currently somewhat budget constrained while I sort out the early days of my new business. But… I’m self-employed, right? If I want more money, I can just work more (Technically correct. The best kind of correct). So lets do that!

Of course, there are plenty of other people who want to go and are vastly more budget constrained than I am. There are travel grants, but there are a lot more people who need budget than there is budget. So if I’m helping myself go by working more, perhaps I can lend a hand with that too?

A plan emerges.

This is how it goes:

  1. I will be going to PyCon Namibia regardless. If this plan somehow fails spectacularly, I’ll just suck up the cost.
  2. I’ll be doing a Hypothesis and Python testing tutorial there, so if you want to attend that go buy a ticket.
  3. At any point between now and when I physically set foot on the plane to go to Namibia on the 21st of January, my Hypothesis training courses (details below) are available for the fairly heavily discounted price of £2000 (if that sounds like a lot to you, me too. It’s a sign that neither of us should be put in charge of a training budget, because for advanced software training courses this is dirt cheap).
  4. Of that £2000, I will be donating 50%, i.e. £1000, to the PyCon Namibia travel fund to help bring people there. I shall not further earmark it but leave it up to the judgement of the organisers as to who most needs it.

Questions

What does the training course entail?

My training courses are designed for groups of up to ten people. In theory an even number of people is better because I like to organise people to pair during it, but in practice that usually breaks down so any number up to ten people is fine.

The primary training course I am currently offering is a very hands on workshop. It’s structured around helping you test your code better using Hypothesis – there is some theory, but it is mostly going to be about your engineers working to improve the quality of your testing, with my being there to point them in the right direction, answer questions, and generally offer advice that will help them avoid false starts and dead ends.

I am in the process of developing a more theory heavy course, some material of which will be in my proposed session in Namibia, so if you are interested in something that involves a lot more theory and working through examples I provide, we can talk about that, but it’s not quite ready yet.

You can see a bit more detail on my consulting page.

Where can you do the training course?

Anywhere that I can get to, really. For now, that definitely restricts it to the UK (and, really, England). If it’s in London or within about two hours drive of Cambridge, it’s probably fine. If it involves more travel than that scheduling starts to become more complicated. If you don’t fit this description, read on to the next section for the ability to schedule a course for after the conference at a still reduced rate.

When can you do the training course?

I have a moderate amount of availability between now and PyCon Namibia. Realistically I can almost certainly fit in 5 courses between now and then, and I can probably fit in up to 10 but it will start to be tight. These will be available on a more or less first come first served basis, so getting in touch soon is a good idea.

If we simply cannot find a mutually agreeable schedule between now and the conference, I’m happy to offer the following fall back plan:

For up to ten additional clients, if you become a sponsor and donate £1500 directly to PyCon Namibia’s travel funds between now and the start of the conference, I am prepared to offer you a one day training course for only £1000 to be claimed at any mutually convenient date in 2016.

Note: Unlike the main offer, this offer is also available to people outside of the UK, but I will also require travel expenses in this case. Also if you don’t get in touch with me before donating this may turn out to no longer be an option, so get in touch first (although feel free to donate even if this is no longer available!)

How can I take you up on this offer?

Drop me an email at [email protected] with the subject line “Hypothesis training” or similar.

Are you affiliated with PyCon Namibia in some way?

Not even slightly. Until yesterday morning I wasn’t even totally sure I was going. I have talked to them a bit about this plan though.

Are you going to change any details of this plan?

I may update some of the details of how funds will be directed if things go very well and e.g. we swamp the travel fund. All funds that I’ve currently said will be going to PyCon Namibia will go to them or a charity of their choice in some capacity though.

Why are you doing this?

Because it’s a good deed, because I can, and because I’m in the right place at the right time. I like the idea of PyCon Namibia a lot, and I suddenly saw the possibility of doing a thing that helps both of us, so I decided to do it.

Have you considered this other worthy cause?

My plan is that once my business is reasonably profitable I will be donating a significant amount of its revenue to charity (probably around 10%), but plans are still TBD. For now, this is what I’m doing.

I have another question

Please either email me privately or post any additional questions in the comments, and I’ll do my best to answer them and keep this post updated.

This entry was posted in programming, Python on by .