How we applied fuzzing techniques to cURL
blog.trailofbits.com
blog.trailofbits.com
> If the data can’t be parsed into a valid TLV, instead of throwing it away, return a syntactically correct dummy TLV. This can be anything, as long as it can be successfully unpacked.
If you're creating a dummy value, how is that better than failing? How does that give your fuzzer better coverage?
The file format isn't what's being fuzzed, so trying to accept as many things as possible as valid is useful.
It's a trick to make the fuzzer faster.
The problem is that the space of invalid inputs is far larger than the space of valid inputs. Sometimes orders of magnitude larger, say billions or more invalid inputs to one valid input.
Naive fuzzing will hit so many error cases that it will hardly produce a valid input. For the ratio that I mentioned, you might run a fuzzer for a billion runs and only get one valid input in the bunch.
Using a custom mutator and returning a dummy value will give the fuzzer a starting point from a valid input and makes generating other valid inputs more likely.
For my part, I prefer to use custom mutators to generate valid test cases most of the time, but I want some invalid inputs because error handling is where most bugs are.
> If the data can’t be parsed into a valid TLV, instead of throwing it away, return a syntactically correct dummy TLV. This can be anything, as long as it can be successfully unpacked.
Is the syntactically correct dummy value the same each time? If so, how does that lead to new coverage?
If it's a different valid TLV value each time, then it's not really a dummy value, is it? In any case, why bother with this "if invalid replace with dummy" step? Why not generate/mutate a valid TLV value from the start?
Per my understanding, the dummy value is constant but is only used once (to create the first valid TLV). Everything after that is a mutation of the original value that, due to the custom mutator logic, is a valid TLV. The mutations are where new coverage comes from.
> In any case, why bother with this "if invalid replace with dummy" step? Why not generate/mutate a valid TLV value from the start?
I'm guessing to handle both when there are seed files that are already valid (which you'll want to use instead of a dummy value), and when there aren't any valid seed files.
Then again some things are just difficult to fuzz properly. I tried writing a libpurple IRC harness by doing it the "right way" with the 3000 libpurple event callbacks you are supposed to set up and structures you are supposed to allocate, which worked, but it was very slow. I ended up being lazy and only calling irc_parse_msg after modifying the code to remove error logging that required proper libpurple setup.
At that point, is it worth the time invested? Every new feature can take 2-3 times longer to deliver due to adding tests.
If it's a small project that won't be extended much, then perhaps then re-runnable unit tests may not make the bar as a net positive tradeoff. But some time must still be spent testing the code, even if it's not tests that are written in code.
The worst case is… arbitrarily bad, to the point of being impossible. Test setup is hell because there are too many dependencies. You have to mock the “real world” since (again) things depend on other things too much and you can’t really do a simple string-manipulating change without setting up a whole environment. Also you introduce bugs in your tests that take longer to debug than the real change you are making.
What I feel that we (current project) have fallen into the trap of is that there wasn’t a test suite from the start. Just manual testing. Then when you get to a stage where you feel you need one, the code base is not structured to make automated testing simple.
If all code was write-only then testing is probably a waste of time but code changes constantly.
In a business-oriented project(at most jobs), code may undergo frequent changes due to requests from business, thus too much focus on testing could potentially slowing down development speed if extensive testing is implemented for each change. However, regression tests can still provide valuable insights and allow for faster development later in the life of the project.
While many projects only focus on happy path testing, the use of such tests might not be as high. Coupling them with Negative Testing, and even better, implementing boundary testing, compels developers to consider both valid and invalid inputs, helping to identify and address potential edge cases before they become bugs or security issues in production.
For instance, this [0] codebase has more tests than actual code, including fuzzing tests.
A few weeks ago someone at the company implemented a feature without tests. It worked perfectly, everyone was happy. A release of another new feature by a different team a few days later broke the previous feature :)
Depends if you are writing software to control a pacemaker, or writing software for some silly smartphone game.
> As of version 3.42.0 (2023-05-16), the SQLite library consists of approximately 155.8 KSLOC of C code [...] the project has 590 times as much test code and test scripts - 92053.1 KSLOC.
seL4 is around 10-12 KLoC, and it took a decade of effort from multiple people to make it happen.
At the size of SQLite, especially where they have to operate on platforms with different behavior (as an OS, seL4 is the platform), formal verification is just too much effort.
All that said, your reaction is totally understandable.
There's also an interesting thing where formal verification requires a formal specification, which afaik there isn't one for SQLite. One of the toughest problems that someone would run into trying to put together a formal specification for code as widely deployed as SQLite boils down to Hyrum's Law[1]: on a long enough time scale, all observable behaviours of your system become interfaces that someone, somewhere depends on.
That massive suite of test cases isn't a formal specification but given that it achieves 100% branch coverage that implies to me that it:
- pretty tightly bounds the interface without formally specifying it
- also pretty tightly constrains the implementation to match the current implementation
Which, when you have as many users as you do with SQLite, is probably a fair way of providing guarantees to your users that upgrading from 3.44.0 to 3.45.1 isn't going to break anything you're using unless you were relying on explicitly-identified buggy behaviour (you'd be able to see the delta in the test cases if you looked at the Fossil diffs).
- use a memory safe language
- formal verification (multiple implementations even)
- build a simulator like FoundationDB did
Interestingly enough I found it while fuzz testing a query builder and cross testing it against PostgreSQL, MySQL and an in-memory filtering engine I wrote.
But also your time estimate does sound wonky, 2-3x sounds extreme. Maybe you need to improve your test writing process?
There are reasons many MVP developers and small teams whose focus is more on rapid feature implementation than large team coordination or code stability forego writing tests. It doesn't make sense in all circumstances. Generally, more complex, less grokable, more large-team-oriented or public library code is when you need testing.
I have yet to see a case where omitting tests actually helps you move meaningfully faster - you’re probably generating more heat than light and that makes you feel like you’re moving faster.
In those situations, yes I stand by them being a costly overhead - which makes sense in large collaborative systems, but not so much in small agile MVPs.
On the other hand, if you are Google, you already have found a money-printing firehose, and you /don't/ want to take on any additional unnecessary risk. Any new code needs to /not/ break existing functionality -- if it does, you might lose out of millions of revenue. In addition, your product becomes so large that it is impossible to manually test every feature. In this case, tests actually help you move /faster/ because they help you at scale automatically ensure that a change does not break anything.
While cURL does not make any money, it is solidly on the mature/Google end of the testing spectrum. It has found a footing in the open source tooling "market" and people rely on it to maintain its existing functionality. In addition, it has accumulated a fairly large surface area, so manual testing is not really feasible for every feature. So testing similarly helps cURL developers move faster (in the long run), not slower.
alternate framing: you can have a feature done in half or a third of the time, if you don't care whether it actually works or not
...or whether it will continue working, as other new features are added to the system and the codebase evolves and grows. that sort of maintainability is one of the key things you get from investing in writing tests - you can refactor without fear of breaking some existing feature.
it also allows you to hire engineers and give them a "safety net" where they can make changes and be confident they're not breaking some crucial functionality of the unfamiliar codebase.
done correctly (an important caveat, because lots of people do testing poorly and then conclude that all testing is bad) that time spent writing tests is not wasted effort. cutting corners by skipping tests is very much a false economy in the long term.
You may want to spend some time looking at code coverage and doing some of the advanced things outlined in this article, especially for very high risk / reward projects like Curl, but even that is not a lot of work.
You’re right that writing tests can make shipping a feature slower. However, already having tests makes shipping a feature faster (higher confidence it works, less manual testing of the feature and the adjacent ones). It also lowers the amount of bugs, which are going to slow down delivery of new features. They also increase maintenance cost though (tests are code that needs maintenance too).
Is it worth it? Depends, although it’s quite rare that no test at all is the right trade off