Fuzzer cannot create any graphs of objects, other than trees, and fairly rarely reuses the same primitive values in different places

[IlyaMuravjov]

Description

Right now fuzzer can only create trees of objects (as opposed to DAGs and cyclic graphs), which severely limits its ability to test methods that, for example, try to find something in a database and need to be passed same attribute values as the ones used when saving data to the database.

Real world (concrete) example

To test successful scenario for method UserService.getOneByUsernameAndRole() in Medical-Web-App project, method under test should be called with the same username and role that were used when creating User for orderRepository.save(User) modification.

Additional context

Limited ability to generate equal values shouldn't be fixed by simply increasing value of probReuseGeneratedValueForSameType, because it only helps with generating values that are passed to the same method, while in concrete example above one pair of username and role are passed to setUsername() and setRole() respectively, while the other one is passed to getOneByUsernameAndRole().

To Reproduce

Run the following unit tests.

Limited ability to generate equal values:

@Test
fun `fuzzer frequently generates equal known values `() {
   runBlocking {
       val totalRuns = 10000
       var runsLeft = totalRuns
       val minAcceptableSeenEqual = totalRuns / 10
       var seenEqual = 0
       runFuzzing(
           { _, _ ->
               sequenceOf("", "abc", "XZ", "#$\\\"'", "\n\t\r", "10", "-3")
                   .map { Seed.Known(StringValue(it), StringValue::value) }
           },
           Description(listOf(Unit, Unit))
       ) { _, (s1, s2) ->
           if (s1 == s2) seenEqual++
           runsLeft--
           BaseFeedback(Unit, if (runsLeft > 0) Control.CONTINUE else Control.STOP)
       }
       Assertions.assertTrue(seenEqual >= minAcceptableSeenEqual) {
           "Too few equal known values generated, expected at least $minAcceptableSeenEqual, but got $seenEqual"
       }
   }
}


@Test
fun `fuzzer frequently generates equal recursive values`() {
   runBlocking {
       val totalRuns = 10000
       var runsLeft = totalRuns
       val minAcceptableSeenEqual = totalRuns / 10
       var seenEqual = 0
       runFuzzing(
           { _, _ ->
               List(3) { seedIdx ->
                   (Seed.Recursive(
                       construct = Routine.Create(emptyList()) { StringBuilder(seedIdx.toString()) },
                       modify = List<Routine.Call<Unit, StringBuilder>>(3) { modifyIdx ->
                           Routine.Call(emptyList()) { s, _ -> s.append(modifyIdx.toString()) }
                       }.asSequence(),
                       empty = Routine.Empty { fail("Empty is called despite construct requiring no args") }
                   ))
               }.asSequence()
           },
           Description(listOf(Unit, Unit))
       ) { _, (s1, s2) ->
           if (s1 == s2) seenEqual++
           runsLeft--
           BaseFeedback(Unit, if (runsLeft > 0) Control.CONTINUE else Control.STOP)
       }
       Assertions.assertTrue(seenEqual >= minAcceptableSeenEqual) {
           "Too few equal recursive values generated, expected at least $minAcceptableSeenEqual, but got $seenEqual"
       }
   }
}

Inability to create DAGs and cyclic object graphs:

@Test
fun `fuzzer can generate values that are equal by reference at any depth`() {
   class Node(val parent: Node?)

   runBlocking {
       var seenReferenceEqual = false
       withTimeout(1000) {
           runFuzzing(
               { _, _ -> sequenceOf(Seed.Recursive<Unit, Node?>(
                   construct = Routine.Create(listOf(Unit)) { (parent) -> Node(parent) },
                   modify = emptySequence(),
                   empty = Routine.Empty { null }
               )) },
               Description(listOf(Unit, Unit))
           ) { _, (n1, n2) ->
               if (n1?.parent === n2 && n2 != null) {
                   seenReferenceEqual = true
                   BaseFeedback(Unit, Control.STOP)
               } else BaseFeedback(Unit, Control.CONTINUE)
           }
       }
       Assertions.assertTrue(seenReferenceEqual) { "Reference equal values weren't generated" }
   }
}

@Test
fun `fuzzer can generate cyclic object graphs`() {
   class MutableNode(var parent: MutableNode? = null)

   runBlocking {
       var seenCycle = false
       withTimeout(1000) {
           runFuzzing(
               { _, _ -> sequenceOf(Seed.Recursive<Unit, MutableNode?>(
                   construct = Routine.Create(emptyList()) { MutableNode() },
                   modify = sequenceOf(Routine.Call(listOf(Unit)) { self, (parent) -> self?.parent = parent }),
                   empty = Routine.Empty { null }
               )) },
               Description(listOf(Unit))
           ) { _, (n1) ->
               if (n1 != null && n1.parent === n1) {
                   seenCycle = true
                   BaseFeedback(Unit, Control.STOP)
               } else BaseFeedback(Unit, Control.CONTINUE)
           }
       }
       Assertions.assertTrue(seenCycle) { "Cyclic object graph wasn't generated" }
   }
}

Expected behavior

All unit tests pass.

Actual behavior

All unit tests fail.

Visual proofs (screenshots, logs, images)

Too few equal known values generated, expected at least 1000, but got 244 ==> expected: <true> but was: <false>
Too few equal recursive values generated, expected at least 1000, but got 1 ==> expected: <true> but was: <false>

Timed out waiting for 1000 ms
kotlinx.coroutines.TimeoutCancellationException: Timed out waiting for 1000 ms
    (Coroutine boundary)
    at org.utbot.fuzzing.FuzzingApi.fuzz(Api.kt:352)
    at org.utbot.fuzzing.FuzzerSmokeTest$fuzzer can generate values that are equal by reference at any depth$1$1.invokeSuspend(FuzzerSmokeTest.kt:317)
    at org.utbot.fuzzing.FuzzerSmokeTest$fuzzer can generate values that are equal by reference at any depth$1.invokeSuspend(FuzzerSmokeTest.kt:316)

Timed out waiting for 1000 ms
kotlinx.coroutines.TimeoutCancellationException: Timed out waiting for 1000 ms
    (Coroutine boundary)
    at org.utbot.fuzzing.FuzzingApi.fuzz(Api.kt:352)
    at org.utbot.fuzzing.FuzzerSmokeTest$fuzzer can generate cyclic object graphs$1$1.invokeSuspend(FuzzerSmokeTest.kt:342)
    at org.utbot.fuzzing.FuzzerSmokeTest$fuzzer can generate cyclic object graphs$1.invokeSuspend(FuzzerSmokeTest.kt:341)

Additional concerns

When generation of cyclic object graphs is supported, fuzzer still must not generate graphs that can't be constructed in practice (i.e. cyclic graphs of immutable objects), meaning the following test should continue to pass.

@Test
fun `fuzzer can't generate cyclic object graphs for immutable objects`() {
   class Node(val parent: Node?)

   runBlocking {
       var remainingRuns = 10000
       runFuzzing(
           { _, _ ->
               sequenceOf(Seed.Recursive<Unit, Node?>(
                   construct = Routine.Create(listOf(Unit)) { (parent) -> Node(parent) },
                   modify = emptySequence(),
                   empty = Routine.Empty { null }
               ))
           },
           Description(listOf(Unit))
       ) { _, (n1) ->
           remainingRuns--
           if (n1 != null && n1.parent === n1) fail("Cyclic object graph generated for immutable objects")
           else if (remainingRuns == 0) BaseFeedback(Unit, Control.STOP)
           else BaseFeedback(Unit, Control.CONTINUE)
       }
   }
}

[alisevych]

@Markoutte
Can you please check this enhancement suggestion for Fuzzing platform?
I'm not sure if it is correct to change the default Fuzzer behavior. Probably it would be correct to implicitly tell Fuzzing when instances of same type should be preferably used in different method calls.
Please share you thoughts on the subj.

[Markoutte]

@Markoutte Can you please check this enhancement suggestion for Fuzzing platform? I'm not sure if it is correct to change the default Fuzzer behavior. Probably it would be correct to implicitly tell Fuzzing when instances of same type should be preferably used in different method calls. Please share you thoughts on the subj.

As I can see the real-world example requires a very specific way to be good. Usually, there's no sense to test so many equal pairs in Java, because my intuition is that when two arguments are equal, they cover only one branch. Changing them to another value doesn't reveal new paths. I mean that calling method("one", "one") and method("two", "two") do the same thing (usually).

Another discussed problem about DAGs is bound with aliasing. Yes, right now fuzzer doesn't support aliasing for injecting same instance in several places of the tree. But it is scheduled to be done later.