4 ms·

This article contains many good points. However, in my opinion, it is still overly lax: The aim should always be complete coverage. The article hints at this

by triska 5y ago

This article contains many good points. However, in my opinion, it is still overly lax: The aim should always be complete coverage. The article hints at this with: “Test every combination of events? Test every output for every combination of events? Test every possible corner case? You would need an absolutely enormous number of tests in order to achieve that!” However, it does not really follow through on it, and even continues with a dedicated section on "Why Random Testing Works". At least symbolic execution with coarse approximations should be used to cover all cases subsumed by more abstract domains. The reason for this is that the number of possible cases is usually so large, and the areas where problems lie often so small, that random tests are unlikely to discover all mistakes. The article mentions precisely this situation: "The bug only manifested itself during a small set of overlapping corner cases." QuickCheck and fuzzing are popular and do find mistakes in practice. However, how many mistakes are not found by these tools, if such random approaches already discover mistakes? In my opinion, an ideal test case only terminates if a mistake is found. If not, it will simply keep on searching, potentially for months, years, ... You need to be able to start the search for mistakes and keep it running for as long as you want. Logic programming languages like Prolog excel at writing test cases, because they provide search as an implicit language feature. It is easy to write a query that asks: "Are there cases where such-and-such holds?", and the system will search for them exhaustively. The ability to concisely write test cases that cover vast areas of the search space is a major attraction of logic programming languages.

throwamon 5y ago
> In my opinion, an ideal test case only terminates if a mistake is found. If not, it will simply keep on searching, potentially for months, years, ... You need to be able to start the search for mistakes and keep it running for as long as you want. That's a good point, but the fundamental problem is that any sufficiently complex space takes way more than a practical amount of time to be completely traversed (easily reaching or surpassing age-of-the-universe magnitudes), so isn't that where fuzzy testing comes in? If you use something like Prolog, isn't it going to perform the search in an ordered manner, drastically reducing the chances that a hard-to-spot mistake is found? And at least in the general case, don't you have to restart the search from scratch every time logic changes?
- zhd 5y ago
  These are basically the problems that https://hypofuzz.com https://hypofuzz.com is designed to solve. - You write standard property-based tests with Hypothesis, which fit into a traditional unit-test workflow (run with pytest, or unittest, or whatever) - then HypoFuzz runs indefinitely, using feedback-guided fuzzing to find bugs that random generation is too slow for - restarting the search on each new commit (or daily, etc) begins by replaying every distinguishable input found earlier so you don't have to start from scratch. There is _some_ loss of context, but that's inherent in testing different code. Plus other nice stuff like allocating more compute time to tests which are finding new behaviour faster, for maximum efficiency. The roadmap includes exploiting SAT solvers to find very very rare behaviour, git history to focus on recently changed code, statistical risk analysis ("what's the expected time to next bug"), and also a budget-mode ("my compute costs $. 08/hr, stop when you expect a bug to cost $100 or more to find"). It's a good time to be working on testing!
pjc50 5y ago
> The aim should always be complete coverage. The problem with this is the requirement to build a completely controllable test fixture including OS syscalls. In practice that's very difficult. How many people test their javascript in a sandbox that allows for arbitrary fault injection of calls into the browser API or DOM? > If not, it will simply keep on searching, potentially for months, years, ... You need to be able to start the search for mistakes and keep it running for as long as you want. You also need to ship, and in many startup environments you don't even have a deadline, it's just "as soon as possible". Fuzzing is very effective at finding security issues. It does seem reasonable to try to design the security boundary of an application in a way amenable to fuzzing.
- triska 5y ago
  To clarify: Tests as I see them and described them above do not need to stop when the software is shipped. They are meant to run indefinitely and can continue also long after the software is shipped, and independent of the environment in which it was developed. For example, I found several mistakes in released versions of GNU Emacs with test cases that repeatedly do the same thing, over and over, until they reveal a crash or memory leak. A few examples of this approach: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=496 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=496 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=576 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=576 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=726 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=726 Fuzzing is a useful approach and does reveal many issues with software. As I see it, the fact that fuzzing already tends to reveal mistakes in software is a good motivation to strive for methods that yield greater coverage based on systematic exhaustive search, so that also mistakes that occur in very rare situations are reliably detected.
jka 5y ago
Improving coverage is a good goal, although (depending on the codebase) I think it can provide a false sense of robustness. Generally more coverage is good, yes; but there can be an element of risk around "testing two inputs in isolation", to borrow terminology from the article. You may have coverage for every line of function A and every line of function B, but that doesn't guarantee that results of the two - when combined dynamically at runtime - are going behave the way that is expected and intended. I like your idea about tests that are continuously searching. In theory I also think it'd be possible to have tests that run on a codebase near-immediately as a developer types (even between commits); ideally exercising the data flow paths that are most directly affected by each syntax tree change first, and expanding out from there.

by triska 5y ago

throwamon 5y ago

> In my opinion, an ideal test case only terminates if a mistake is found. If not, it will simply keep on searching, potentially for months, years, ... You need to be able to start the search for mistakes and keep it running for as long as you want. That's a good point, but the fundamental problem is that any sufficiently complex space takes way more than a practical amount of time to be completely traversed (easily reaching or surpassing age-of-the-universe magnitudes), so isn't that where fuzzy testing comes in? If you use something like Prolog, isn't it going to perform the search in an ordered manner, drastically reducing the chances that a hard-to-spot mistake is found? And at least in the general case, don't you have to restart the search from scratch every time logic changes?

zhd 5y ago
These are basically the problems that https://hypofuzz.com https://hypofuzz.com is designed to solve. - You write standard property-based tests with Hypothesis, which fit into a traditional unit-test workflow (run with pytest, or unittest, or whatever) - then HypoFuzz runs indefinitely, using feedback-guided fuzzing to find bugs that random generation is too slow for - restarting the search on each new commit (or daily, etc) begins by replaying every distinguishable input found earlier so you don't have to start from scratch. There is _some_ loss of context, but that's inherent in testing different code. Plus other nice stuff like allocating more compute time to tests which are finding new behaviour faster, for maximum efficiency. The roadmap includes exploiting SAT solvers to find very very rare behaviour, git history to focus on recently changed code, statistical risk analysis ("what's the expected time to next bug"), and also a budget-mode ("my compute costs $. 08/hr, stop when you expect a bug to cost $100 or more to find"). It's a good time to be working on testing!

pjc50 5y ago

> The aim should always be complete coverage. The problem with this is the requirement to build a completely controllable test fixture including OS syscalls. In practice that's very difficult. How many people test their javascript in a sandbox that allows for arbitrary fault injection of calls into the browser API or DOM? > If not, it will simply keep on searching, potentially for months, years, ... You need to be able to start the search for mistakes and keep it running for as long as you want. You also need to ship, and in many startup environments you don't even have a deadline, it's just "as soon as possible". Fuzzing is very effective at finding security issues. It does seem reasonable to try to design the security boundary of an application in a way amenable to fuzzing.

triska 5y ago
To clarify: Tests as I see them and described them above do not need to stop when the software is shipped. They are meant to run indefinitely and can continue also long after the software is shipped, and independent of the environment in which it was developed. For example, I found several mistakes in released versions of GNU Emacs with test cases that repeatedly do the same thing, over and over, until they reveal a crash or memory leak. A few examples of this approach: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=496 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=496 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=576 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=576 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=726 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=726 Fuzzing is a useful approach and does reveal many issues with software. As I see it, the fact that fuzzing already tends to reveal mistakes in software is a good motivation to strive for methods that yield greater coverage based on systematic exhaustive search, so that also mistakes that occur in very rare situations are reliably detected.

jka 5y ago

Improving coverage is a good goal, although (depending on the codebase) I think it can provide a false sense of robustness. Generally more coverage is good, yes; but there can be an element of risk around "testing two inputs in isolation", to borrow terminology from the article. You may have coverage for every line of function A and every line of function B, but that doesn't guarantee that results of the two - when combined dynamically at runtime - are going behave the way that is expected and intended. I like your idea about tests that are continuously searching. In theory I also think it'd be possible to have tests that run on a codebase near-immediately as a developer types (even between commits); ideally exercising the data flow paths that are most directly affected by each syntax tree change first, and expanding out from there.