Fuzzer can pass one object into several arguments of same type

UnitTestBot · Markoutte · Dec 12, 2022 · Nov 2, 2022 · Dec 6, 2022 · Dec 7, 2022
commit 47a4c3c160d1386b7341f4b8da74a1475871f49f
diff --git a/utbot-fuzzers/src/main/kotlin/org/utbot/fuzzer/FuzzedType.kt b/utbot-fuzzers/src/main/kotlin/org/utbot/fuzzer/FuzzedType.kt
@@ -14,7 +14,7 @@ import org.utbot.framework.plugin.api.ClassId
  *
  * @see ClassId.typeParameters
  */
-class FuzzedType(
+data class FuzzedType(
     val classId: ClassId,
     val generics: List<FuzzedType> = emptyList(),
 )
diff --git a/utbot-fuzzers/src/main/kotlin/org/utbot/fuzzing/JavaLanguage.kt b/utbot-fuzzers/src/main/kotlin/org/utbot/fuzzing/JavaLanguage.kt
@@ -90,13 +90,13 @@ suspend fun runJavaFuzzing(
     val tracer = Trie(Instruction::id)
     val descriptionWithOptionalThisInstance = FuzzedDescription(createFuzzedMethodDescription(thisInstance), tracer)
     val descriptionWithOnlyParameters = FuzzedDescription(createFuzzedMethodDescription(null), tracer)
-    BaseFuzzing(providers) { _, t ->
+    runFuzzing(ValueProvider.of(providers), descriptionWithOptionalThisInstance) { _, t ->
         if (thisInstance == null) {
             exec(null, descriptionWithOnlyParameters, t)
         } else {
             exec(t.first(), descriptionWithOnlyParameters, t.drop(1))
         }
-    }.fuzz(descriptionWithOptionalThisInstance)
+    }
 }
 
 private fun toFuzzerType(type: Type): FuzzedType {

diff --git a/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/Api.kt b/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/Api.kt
@@ -5,6 +5,7 @@ import mu.KotlinLogging
 import org.utbot.fuzzing.seeds.KnownValue
 import org.utbot.fuzzing.utils.chooseOne
 import org.utbot.fuzzing.utils.flipCoin
+import org.utbot.fuzzing.utils.transformIfNotEmpty
 import kotlin.random.Random
 
 private val logger by lazy { KotlinLogging.logger {} }
@@ -30,16 +31,18 @@ interface Fuzzing<TYPE, RESULT, DESCRIPTION : Description<TYPE>, FEEDBACK : Feed
     fun generate(description: DESCRIPTION, type: TYPE): Sequence<Seed<TYPE, RESULT>>
 
     /**
+     * This method is called on every value list generated by fuzzer.
+     *
      * Fuzzing combines, randomize and mutates values using the seeds.
      * Then it generates values and runs them with this method. This method should provide some feedback,
      * which is the most important part for good fuzzing result. [emptyFeedback] can be provided only for test
      * or infinite loops. Consider to implement own implementation of [Feedback] to provide more correct data or
      * use [BaseFeedback] to generate key based feedback. In this case, the key is used to analyse what value should be next.
      *
      * @param description contains user-defined information about current run. Can be used as a state of the run.
-     * @param values current values to run.
+     * @param values current values to process.
      */
-    suspend fun run(description: DESCRIPTION, values: List<RESULT>): FEEDBACK
+    suspend fun handle(description: DESCRIPTION, values: List<RESULT>): FEEDBACK
 }
 
 /**
@@ -277,9 +280,11 @@ suspend fun <T, R, D : Description<T>, F : Feedback<T, R>> Fuzzing<T, R, D, F>.f
                 }
             }
         }.forEach execution@ { values ->
-            val result = values.map { create(it) }
+            check(values.parameters.size == values.result.size) { "Cannot create value for ${values.parameters}" }
+            val valuesCache = mutableMapOf<Result<T, R>, R>()
+            val result = values.result.map { valuesCache.computeIfAbsent(it) { r -> create(r) } }
             val feedback = try {
-                fuzzing.run(description, result)
+                fuzzing.handle(description, result)
             } catch (t: Throwable) {
                 logger.error(t) { "Error when running fuzzing with $values" }
                 return@execution
@@ -312,7 +317,17 @@ private fun <TYPE, RESULT, DESCRIPTION : Description<TYPE>, FEEDBACK : Feedback<
     builder: Routine<TYPE, RESULT>,
     state: State<TYPE, RESULT>,
 ): Node<TYPE, RESULT>  {
-    val result = parameters.map { type -> produce(type, fuzzing, description, random, configuration, state) }
+    val typeCache = mutableMapOf<TYPE, MutableList<Result<TYPE, RESULT>>>()
+    val result = parameters.map { type ->
+        val results = typeCache.computeIfAbsent(type) { mutableListOf() }
+        if (results.isNotEmpty() && random.flipCoin(configuration.probReuseGeneratedValueForSameType)) {
+            results.random(random)
+        } else {
+            produce(type, fuzzing, description, random, configuration, state).also {
+                results += it
+            }
+        }
+    }
     // is not inlined to debug values generated for a concrete type
     return Node(result, parameters, builder)
 }
@@ -413,8 +428,7 @@ private fun <TYPE, RESULT, DESCRIPTION : Description<TYPE>, FEEDBACK : Feedback<
                 State(state.recursionTreeDepth + 1, state.cache)
             ),
             modify = task.modify
-                .shuffled()
-                .take(configuration.maximumObjectModifications.coerceAtLeast(1))
+                .shuffled(random)
                 .mapTo(arrayListOf()) { routine ->
                     fuzz(
                         routine.types,
@@ -425,6 +439,8 @@ private fun <TYPE, RESULT, DESCRIPTION : Description<TYPE>, FEEDBACK : Feedback<
                         routine,
                         State(state.recursionTreeDepth + 1, state.cache)
                     )
+                }.transformIfNotEmpty {
+                    take(random.nextInt(size + 1).coerceAtLeast(1))
                 }
         )
     }
@@ -462,6 +478,11 @@ private fun <TYPE, RESULT, DESCRIPTION : Description<TYPE>, FEEDBACK : Feedback<
                     construct = mutate(resultToMutate.construct, fuzzing, random, configuration, State(state.recursionTreeDepth + 1, state.cache)),
                     modify = resultToMutate.modify
                 )
+            } else if (random.flipCoin(configuration.probShuffleAndCutRecursiveObjectModificationMutation)) {
+                Result.Recursive(
+                    construct = resultToMutate.construct,
+                    modify = resultToMutate.modify.shuffled(random).take(random.nextInt(resultToMutate.modify.size + 1).coerceAtLeast(1))
+                )
             } else {
                 Result.Recursive(
                     construct = resultToMutate.construct,
@@ -609,7 +630,7 @@ private class Node<TYPE, RESULT>(
     val result: List<Result<TYPE, RESULT>>,
     val parameters: List<TYPE>,
     val builder: Routine<TYPE, RESULT>,
-) : Iterable<Result<TYPE, RESULT>> by result
+)
 
 
 private class Statistics<TYPE, RESULT, FEEDBACK : Feedback<TYPE, RESULT>> {

diff --git a/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/Configuration.kt b/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/Configuration.kt
@@ -18,8 +18,6 @@ class Configuration(
      */
     var collectionIterations: Int = 5,
 
-    var maximumObjectModifications: Int = Int.MAX_VALUE,
-
     /**
      * Energy function that is used to choose seeded value.
      */
@@ -40,6 +38,11 @@ class Configuration(
      */
     var probConstructorMutationInsteadModificationMutation: Int = 90,
 
+    /**
+     * Probability to shuffle modification list of the recursive object
+     */
+    var probShuffleAndCutRecursiveObjectModificationMutation: Int = 10,
+
     /**
      * Probability to prefer create rectangle collections instead of creating saw-like one.
      */
@@ -64,4 +67,9 @@ class Configuration(
      * Probability of removing an old character from StringValue when mutating
      */
     var probStringRemoveCharacter: Int = 50,
+
+    /**
+     * Probability of reusing same generated value when 2 or more parameters have the same type.
+     */
+    var probReuseGeneratedValueForSameType: Int = 1
 )
diff --git a/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/Providers.kt b/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/Providers.kt
@@ -1,9 +1,23 @@
 package org.utbot.fuzzing
 
 import mu.KotlinLogging
+import kotlin.random.Random
 
 private val logger by lazy { KotlinLogging.logger {} }
 
+/**
+ * Entry point to run fuzzing.
+ */
+suspend fun <TYPE, RESULT, DESCRIPTION : Description<TYPE>, FEEDBACK : Feedback<TYPE, RESULT>> runFuzzing(
+    provider: ValueProvider<TYPE, RESULT, DESCRIPTION>,
+    description: DESCRIPTION,
+    random: Random = Random(0),
+    configuration: Configuration = Configuration(),
+    handle: suspend (description: DESCRIPTION, values: List<RESULT>) -> FEEDBACK
+) {
+    BaseFuzzing(listOf(provider), handle).fuzz(description, random, configuration)
+}
+
 /**
  * Implements base concepts that use providers to generate values for some types.
  *
@@ -32,7 +46,7 @@ class BaseFuzzing<T, R, D : Description<T>, F : Feedback<T, R>>(
         }
     }
 
-    override suspend fun run(description: D, values: List<R>): F {
+    override suspend fun handle(description: D, values: List<R>): F {
         return exec(description, values)
     }
 }

diff --git a/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/demo/AbcFuzzing.kt b/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/demo/AbcFuzzing.kt
@@ -47,7 +47,7 @@ suspend fun main() {
          * This implementation just calls the target function and returns a result. After it returns an empty feedback.
          * If some returned value equals to the length of the source string then feedback returns 'stop' signal.
          */
-        override suspend fun run(description: Description<Unit>, values: List<String>): BaseFeedback<Int, Unit, String> {
+        override suspend fun handle(description: Description<Unit>, values: List<String>): BaseFeedback<Int, Unit, String> {
             check(values.size == 1) {
                 "Only one value must be generated because of `description.parameters.size = ${description.parameters.size}`"
             }

diff --git a/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/demo/JavaFuzzing.kt b/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/demo/JavaFuzzing.kt
@@ -71,7 +71,7 @@ object JavaFuzzing : Fuzzing<Class<*>, Any?, Description<Class<*>>, Feedback<Cla
         }
     }
 
-    override suspend fun run(description: Description<Class<*>>, values: List<Any?>): Feedback<Class<*>, Any?> {
+    override suspend fun handle(description: Description<Class<*>>, values: List<Any?>): Feedback<Class<*>, Any?> {
         println(values.joinToString {
             when (it) {
                 is BooleanArray -> it.contentToString()

diff --git a/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/utils/Functions.kt b/utbot-fuzzing/src/main/kotlin/org/utbot/fuzzing/utils/Functions.kt
@@ -81,6 +81,10 @@ internal enum class BinaryFormat : (Int) -> Boolean {
     DOUBLE { override fun invoke(index: Int) = index % 16 == 0 && index != 0 },
 }
 
+internal fun <T> List<T>.transformIfNotEmpty(transform: List<T>.() -> List<T>): List<T> {
+    return if (isNotEmpty()) transform() else this
+}
+
 fun main() {
     val endian = Endian.BE
     println(255.toUByte().toBinaryString(endian))

diff --git a/utbot-fuzzing/src/test/kotlin/org/utbot/fuzzing/samples/Objects.java b/utbot-fuzzing/src/test/kotlin/org/utbot/fuzzing/samples/Objects.java
@@ -23,4 +23,14 @@ public boolean testMe(Recursive r) {
         return false;
     }
 
+    private int data;
+
+    public static void foo(Objects a, Objects b) {
+        a.data = 1;
+        b.data = 2;
+        //noinspection ConstantValue
+        if (a.data == b.data) {
+            throw new IllegalArgumentException();
+        }
+    }
 }