2

Let's say we're writing a simple JSON parser and we've fully covered the code with unit tests:

  • it can parse primitives "0", "123", "-456", '""', '"asd"', true, false
  • it can parse arrays "[]", "[1, 2, 3]"
  • it can parse nested arrays "[[]]"
  • it can parse objects "{}", '{ "a": 1, "b": 2 }'
  • it can parse nested objects '{ "a": {} }'

Every possible JSON can be either a primitive or an array/object holding other primitives/arrays/objects - this is what I mean by inductive data structure (is 'recursive' a better term?). It seems to me that any JSON parsing can be reduced to these few cases and if the parser passes these tests then it is fully correct (unless it was explicitly hard-wired to break when you try to parse special numbers).

Is there still any point in creating a random tester that generates random stringified JSON in hope that one of them will break this parser? Would this random tester find anything interesting?

P.S. I chose JSON just as an example of an inductive data structure; I'm not interested in writing a JSON parser.

  • If you can construct a proof that the parser is correct, then there's no bugs. But it never hurts to have some tests - I'd just focus on constructing nastiest edge cases rather than trying to be exhaustive. This is especially true if there's no one around to validate your proof. There's also the chance that you'll find a bug in the implementation of your language of choice and/or its libraries. – Doval May 23 '14 at 11:54
  • 1
    I believe you may be confused about testing. What happens when you present bad data to the parser? Does it accept it? What about tokens that are too large for buffers? – BobDalgleish May 23 '14 at 21:37
  • Bob is absolutely right. If I can give you only one piece of advice: Test your error handling. Anybody can write "fair weather code", but proven robustness under harsh conditions makes your code really shine. – JensG May 24 '14 at 1:00
  • You've also missed (at least) two test cases: objects that contain arrays, and arrays that contain objects – Izkata May 24 '14 at 3:06
1

(The terms 'recursive' and 'inductive' pretty much mean the same thing, mathematically speaking, although 'recursive' is more common among the computing crowd. Even more common for data structures is 'dynamic', which comes down to the same thing, since the possible shapes of dynamic data structures are invariably defined by conditions such as "...and you can nest another node just like this one at either end.")

You're right that a recursively defined parser that parses recursive input is unlikely to have bugs that require very complicated input to expose - ether the base case and the recursive case are handled right, or else they aren't. There is always the issue of resource limits, of course, but even that usually just requires very big input to check, not necessarily very complex input.

In my experience, the insidious defects in parsers occur through the combination of features that are, in themselves, well-supported: strings containing embedded quotes and embedded escape characters simultaneously, tokens that according to one standard are literals but in practice are often written with quotes anyway because present-day browsers expect it that way, etc. So you should be aiming for novel configurations to test, not so much for longer ones.

1

The question I intend to answer is one about the value of random testing in general, and of inductive/recursive data structures in particular, not about JSON.

Random testing has value in several different settings. The primary purpose of random testing is to tackle cases where the test space is immensely large so that it cannot be tested exhaustively. I can think of 3 such spaces.

  1. Survivability. Does the system under test survive being fed large quantities of bizarre input data? Yes, you should test that.
  2. Limits. Does the SUT behave correctly when fed input that exceeds its limits, such as token length, recursion depth, backtracking or whatever, either alone or in combination? You can do most of that with planned testing, but a bit of random might be worthwhile.
  3. Test flaws. There is always a risk that your other tests missed something interesting, and that feeding a sufficient quantity of data around the margins (which you will know from white box inspection) will find it. Worth considering.

The problem with random testing is (a) how to adequately explore a near infinite input space (b) how to predict the test outcome for each input case.

If you have solutions for that, then random testing for these three reasons is at least worth considering.

0

One thing I do when testing parsers is to write separate tests for the just the lexer. This means that there are a lot fewer novel cases that will need to be tested by the parser stage.

Many of the testcases for the lexer might not even be valid to the parser. For example, the input "]:[," should successfully lex to [EndArray, KeyValueSeparator, StartArray, ElementSeparator, EOF], whereas '"\"' would fail to lex with Error("expected closing quote").

I wouldn't use a random tester, but I would generate each sequence of valid tokens and check whether the parser agrees with me on whether it should be parseable. Ensuring that your parser fails when appropriate is just as important as ensuring that it succeeds.

Json has 8 token types (String, Number, BeginList, EndList, BeginObject, EndObject, KeyValueSeparator, ElementSeparator), plus EOF (and occasionally Error, if you're not using exceptions). 4 of them error in the first position, so they'll need no testing with strings with more than one token. Two others (number and string) cannot legally be followed by anything else, so they need no testing with strings with more than two tokens. If the first token is BeginList or BeginObject, 3 of the tokens will error immediately.

Repeat with longer token sequences, until every one of them becomes invalid or repeats a previous testcase just with a longer list or something. But every positive testcase must be a prefix of at least 8 negative testcases.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.