Use after free bug

[DRMacIver]

Because I have a weird idea of fun, I'm running American Fuzzy Lop against jq.

So far it's not been running very long and it's found one interesting bug. If I put the following text in a file (note: this doesn't seem to work from stdin for some reason):

[[0]]{}

And then run the following command:

jq ".foo[.bar = 12].bar = 1" short.json

then I get a crash with a "corrupted double-linked list" error, which seems to be from libc. Running this under valgrind tells me it's a use after free bug:

==6474== Invalid read of size 4
==6474==    at 0x40D8E4: jvp_object_free.isra.44 (jv.c:960)
==6474==    by 0x40C9CC: jvp_array_free.isra.41 (jv.c:202)
==6474==    by 0x4042CA: frame_pop (execute.c:153)
==6474==    by 0x4046B0: stack_restore (execute.c:250)
==6474==    by 0x404B57: jq_next (execute.c:728)
==6474==    by 0x403A67: process (main.c:125)
==6474==    by 0x40281E: main (main.c:530)
==6474==  Address 0x5662cb0 is 0 bytes inside a block of size 392 free'd
==6474==    at 0x4C2CE10: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6474==    by 0x417B35: jv_set (jv_aux.c:169)
==6474==    by 0x418AF0: jv_setpath (jv_aux.c:319)
==6474==    by 0x418AD6: jv_setpath (jv_aux.c:319)
==6474==    by 0x408E81: f_setpath (builtin.c:972)
==6474==    by 0x405D62: jq_next (execute.c:786)
==6474==    by 0x403A67: process (main.c:125)
==6474==    by 0x40281E: main (main.c:530)

This is running against jq master checked out to 89897b4.

I'll let you know if AFL turns up anything else interesting.

[dtolnay]

Thanks! This is what all bug reports should be like.

Here is a slightly smaller repro:

jq -n '.[.bar = 0].bar = 0'

[dtolnay]

jq -n '.[{}] = 0'

[pkoppstein]

Hopefully this bug (or these bugs) will free us from being slaves to the implementation of = and |=.

[dtolnay]

Do you mean the PATH_BEGIN/PATH_END business? I am still tracking this down but the bug isn't in any of that. For example this hits the issue without using PATH_BEGIN/PATH_END:

jq -n 'setpath([{}]; 0)'

[nicowilliams]

Fuzzing the compiler and interpreter is a very nice idea, thanks. (And we should use AFL for the JSON parser as well, not just the half-baked fuzzer we have in-tree, though it found plenty of bugs.)

The bug is in jv_set(), which should not jv_free(k) when parse_slice() fails, or, better yet, parse_slice() should adhere to the convention that functions always consume a reference to any jv passed in, and then we need to fix the callers of parse_slice() to make sure they jv_copy() or not as needed.

@pkoppstein This has nothing to do with your issues with the assignment operators. The fix for this is in C code, whereas the problems you have with the assignment operators are really a topic for a different issue.

[DRMacIver]

Fuzzing the compiler and interpreter is a very nice idea, thanks.

No problem. FWIW, what I'm doing is very straightforward: I just extracted all lines from jq.test (I didn't even bother to filter down to the ones that are jq), filtered the set down with afl-cmin and then used these as seeds to AFL. Initially I was running this on a large JSON file but now I'm just trying it with -n.

(And we should use AFL for the JSON parser as well, not just the half-baked fuzzer we have in-tree, though it found plenty of bugs.)

I actually started there and switched to fuzzing the jq language as it seemed like a richer target. It's probably still a good idea to use it on the JSON parser though.

[nicowilliams]

Indeed, what I supposed above is correct. A fix to parse_slice() and its callers takes care of this one.

@DRMacIver I'm quite glad you chose to attack the jq language first, as chances are our JSON parser fuzzer has caught enough bugs that the language bugs are likely more interesting. Our friends at jqplay.org will benefit from this. Of course, the JSON parser needs more fuzzing, but one step at a time.

How easy would it be to script fuzzing of the jq-coded tests? Maybe we could run AFL as part of make check then.

[DRMacIver]

AFL does not generally seem designed to run as part of a CI build. Its behaviour is more well suited to running as a long-running server process somewhere which you can use to build up a corpus of examples that you can use for elsewhere.

[DRMacIver]

(I mean it's pretty easy to automate management of such a corpus and using AFL to work with it, it just doesn't really work as part of make check)

[nicowilliams]

Got it, thanks. Perhaps we could have a script to update the corpus as we add jq-coded tests?

[pkoppstein]

@DRMacIver - It's interesting that AFL didn't catch #922. I don't know very much about AFL but was wondering (a) whether it can be instructed to use certain test cases (notably, those in tests/jq.test and tests/onig.test) as jumping-off points; and (b) whether AFL can be "taught" that testing with UTF-8 strings should be done in certain ways.

[DRMacIver]

The way I was running afl is almost certainly at fault there.

Essentially the problem is that as AFL is designed I can fuzz according to the jq program or I can fuzz according to the input, but at any point I have to keep one of these elements fixed - there's no easy way for me to fuzz according to both. So what I was testing was the behaviour of jq programs when run under jq -n, which looks like it can't trigger #922.

[dtolnay]

It can, jq -n '"—" | sub("(.)"; "")'.

[DRMacIver]

Ah, of course. In that case a likely culprit there is that it was mostly starting with ascii examples, so it wsas probably relatively hard to reach something like that from there. It might have found it if I'd run it for longer, but I reached a point where the computer I was running it on wasn't very happy so I decided to stop. Adding just a bunch of utf-8 strings into the seeding might have been enough to trigger this. I'm not sure.

[nicowilliams]

We want to fuzz regexp patterns and input strings. This could be done with --arg pattern "<pattern>" and --raw-input, then fuzz the <pattern> and the character data on stdin. EDIT: with a fixed jq program, of course.