TypeFuzz.jl - Fuzz testing of the Julia type system


#1

I’ve finally turned the fuzz testing code used for https://github.com/JuliaLang/julia/pull/21339 into a package:
https://github.com/martinholters/TypeFuzz.jl
It’s still rather basic, I would say, but it does find bugs. To vet your appetite:

julia> using TypeFuzz, Base.Test

julia> srand(2);

julia> @time testset = :(@testset "some tests found by TypeFuzz" begin $(testcases(testtypeintersect(150))) end)
  3.543186 seconds (1.67 M allocations: 150.785 MiB, 2.75% gc time)
:(@testset "some tests found by TypeFuzz" begin  # REPL[12], line 1:
            begin 
                @test_broken let a = Tuple{T1,T2,Int64} where T1 where T2, b = Tuple{Tuple{S1},S1,S3} where S1 where S3
                        typeintersect(a, b) == typeintersect(b, a)
                    end
                @test_broken let b = Tuple{Tuple{S1},S1,S3} where S1 where S3
                        typeintersect(b, Tuple{T1,T2,Int64} where T1 where T2) <: b
                    end
                @test_broken let a = Tuple{Val{T1},T1,T2} where T1 where T2, b = Tuple{S3,S4,3} where S3 where S4
                        typeintersect(a, b) == typeintersect(b, a)
                    end
                @test_broken let a = Tuple{Val{T1},T1,T2} where T1 where T2
                        typeintersect(a, Tuple{S3,S4,3} where S3 where S4) <: a
                    end
                @test_broken let b = Tuple{S2,Tuple{S2}} where S2
                        typeintersect(Tuple{Int64,T2} where T2, b) <: b
                    end
                @test_broken let b = Tuple{S3,S4,Val{S4}} where S3 where S4
                        typeintersect(b, Tuple{Val{T1},T1,T2} where T1 where T2) <: b
                    end
                @test_broken let a = Tuple{Tuple{T8,T8},T8} where T8, b = Tuple{S3,Int64} where S3
                        typeintersect(a, b) == typeintersect(b, a)
                    end
                @test_broken let a = Tuple{Tuple{T8},T8} where T8
                        typeintersect(a, Tuple{S3,Int64} where S3) <: a
                    end
                @test_broken let a = Tuple{Tuple{T8},T8} where T8
                        typeintersect(Tuple{S3,Int64} where S3, a) <: a
                    end
                @test_broken typeintersect(Tuple{S2,1} where S2, Tuple{T2,T2} where T2)
            end
        end)

julia> eval(testset);
Test Summary:                | Broken  Total
some tests found by TypeFuzz |     10     10

Feedback and contributions welcome!


#2

Cool work, this is an elegant approach.

The package resolver seems like a great case for fuzz testing as well – and badly needs it.

A while back I wrote some code that hooks into the compiler to record branches; this could be used for more directed fuzzing, like American Fuzzy Lop does. I can put that up if anyone’s interested.

I think that this could also be used in cases where it’s hard to figure out very general invariants. Instead, just generate a minimal set of test cases that explores all code paths, regardless of whether they are correct. Then review those manually and add them to your CI. Essentially, this would automatically generate your package’s tests for you.

Wish I had time to work on stuff like this :slight_smile:


#3

Definitely put that up!


#4

Yes, more informed fuzzing, whether with AFL or some other means, would certainly be the way to go in the long term. But for now, development time is probably better spent fixing the bugs uncovered even with this very naive fuzzing than coming up with more sophisticated fuzzing strategies.

A more near-term goal for me would be to cope with julia crashing/hanging. Spawning a new process for every test might be a bit too expensive. I’m therefore considering spawning one subprocess for a whole batch of tests and then writing the generated input type (or the RNG state) to a file or pipe prior to running the tests so that any crashing input can easily be reproduced. This is new territory for me, however, so if anyone has insights to share or would even like to tackle it, that would be great.


#5

Your wish is my command: https://github.com/MikeInnes/HotFuzz.jl

Let me know if you use it for something interesting.


#6

That is so much cleaner than I expected it to be! I guess it shouldn’t be too hard to integrate this with AFL, just need to set the proper bits in the bitmap (ex). Did you try any such thing?


#7

Didn’t try it, but just integrating with AFL directly is a nice approach that I hadn’t considered.

Main thing for me was I was mainly interested in using this for structured data, which opens up a lot of doors compared to working with whole programs that work on byte streams (which would be a special case). It would also be a lot faster if you could do everything in-process.

For DataFlow.jl I just wrote a mini custom fuzzer similar to OPs; the interesting test cases show up in small graphs so you can enumerate them and get something minimal. Once it passes your code is guaranteed bug-free.

But there are a few good test cases for AFL in the Julia ecosystem, like JSON.jl, the markdown parser or the nascent HTTP.jl (probably the best target as a security concern).