Skip to content

Commit 3801e27

Browse files
dtimdtim
committed
Prefer symbolic executions during minimization
1 parent 64d1bd3 commit 3801e27

File tree

4 files changed

+116
-12
lines changed

4 files changed

+116
-12
lines changed

‎utbot-framework-api/src/main/kotlin/org/utbot/framework/UtSettings.kt‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -378,6 +378,11 @@ object UtSettings : AbstractSettings(
378378
*/
379379
var disableSandbox by getBooleanProperty(false)
380380

381+
/**
382+
* Exclude fuzzer-produced executions during minimization if there is an equivalent symbolic execution
383+
*/
384+
var preferSymbolicExecutionsDuringMinimization by getBooleanProperty(true)
385+
381386
}
382387

383388
/**

‎utbot-framework-test/src/test/kotlin/org/utbot/framework/minimization/MinimizationGreedyEssentialTest.kt‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -68,4 +68,46 @@ class MinimizationGreedyEssentialTest {
6868
val minimizedExecutions = GreedyEssential.minimize(executions)
6969
assertEquals((1..size).toList(), minimizedExecutions.sorted())
7070
}
71+
72+
@Test
73+
fun testWithSourcePriority() {
74+
val executions = mapOf(
75+
10 to listOf(1, 2, 3, 4, 5),
76+
20 to listOf(2, 3, 4, 5, 6, 7),
77+
21 to listOf(2, 3, 4, 5, 6, 7),
78+
25 to listOf(1, 7, 2, 3, 5),
79+
30 to listOf(8, 9),
80+
50 to listOf(1, 8, 9),
81+
60 to listOf(1, 9)
82+
)
83+
84+
val sourcePriorities = mapOf(
85+
10 to 0,
86+
20 to 1,
87+
21 to 0,
88+
25 to 0,
89+
30 to 1,
90+
50 to 1,
91+
60 to 0
92+
)
93+
94+
val minimizedExecutions = GreedyEssential.minimize(executions, sourcePriorities)
95+
assertEquals(listOf(21, 50), minimizedExecutions)
96+
}
97+
98+
@Test
99+
fun testWithoutSourcePriority() {
100+
val executions = mapOf(
101+
10 to listOf(1, 2, 3, 4, 5),
102+
20 to listOf(2, 3, 4, 5, 6, 7),
103+
21 to listOf(2, 3, 4, 5, 6, 7),
104+
25 to listOf(1, 7, 2, 3, 5),
105+
30 to listOf(8, 9),
106+
50 to listOf(1, 8, 9),
107+
60 to listOf(1, 9)
108+
)
109+
110+
val minimizedExecutions = GreedyEssential.minimize(executions)
111+
assertEquals(listOf(20, 50), minimizedExecutions)
112+
}
71113
}

‎utbot-framework/src/main/kotlin/org/utbot/framework/minimization/GreedyEssential.kt‎

Lines changed: 44 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,33 +2,58 @@ package org.utbot.framework.minimization
22

33
import java.util.PriorityQueue
44

5-
private inline class ExecutionNumber(val number: Int)
5+
@JvmInline
6+
private value class ExecutionNumber(val number: Int)
67

7-
private inline class LineNumber(val number: Int)
8+
@JvmInline
9+
private value class LineNumber(val number: Int)
10+
11+
/**
12+
* Execution source priority (symbolic executions are considered more important than fuzzed executions).
13+
* @see [UtSettings.preferSymbolicExecutionsDuringMinimization]
14+
*/
15+
@JvmInline
16+
private value class SourcePriority(val number: Int)
17+
18+
/**
19+
* A wrapper that combines covered lines with the execution source priority
20+
*/
21+
private data class ExecutionCoverageInfo(
22+
val sourcePriority: SourcePriority,
23+
val coveredLines: List<LineNumber>
24+
)
825

926
/**
1027
* [Greedy essential algorithm](CONFLUENCE:Test+Minimization)
1128
*/
1229
class GreedyEssential private constructor(
13-
executionToCoveredLines: Map<ExecutionNumber, List<LineNumber>>
30+
executionToCoveredLines: Map<ExecutionNumber, ExecutionCoverageInfo>
1431
) {
32+
private val executionToSourcePriority: Map<ExecutionNumber, SourcePriority> =
33+
executionToCoveredLines
34+
.mapValues { it.value.sourcePriority }
35+
1536
private val executionToUsefulLines: Map<ExecutionNumber, MutableSet<LineNumber>> =
1637
executionToCoveredLines
17-
.mapValues { it.value.toMutableSet() }
38+
.mapValues { it.value.coveredLines.toMutableSet() }
1839

1940
private val lineToUnusedCoveringExecutions: Map<LineNumber, MutableSet<ExecutionNumber>> =
2041
executionToCoveredLines
21-
.flatMap { (execution, lines) -> lines.map { it to execution } }
42+
.flatMap { (execution, lines) -> lines.coveredLines.map { it to execution } }
2243
.groupBy({ it.first }) { it.second }
2344
.mapValues { it.value.toMutableSet() }
2445

2546
private val executionByPriority =
26-
PriorityQueue(compareByDescending<Pair<ExecutionNumber, Int>> { it.second }.thenBy { it.first.number })
47+
PriorityQueue(
48+
compareByDescending<Triple<ExecutionNumber, Int, SourcePriority>> { it.second }
49+
.thenBy { it.third.number }
50+
.thenBy { it.first.number }
51+
)
2752
.apply {
2853
addAll(
2954
executionToCoveredLines
3055
.keys
31-
.map { it to executionToUsefulLines[it]!!.size }
56+
.map { Triple(it, executionToUsefulLines[it]!!.size, executionToSourcePriority[it]!!) }
3257
)
3358
}
3459

@@ -69,7 +94,7 @@ class GreedyEssential private constructor(
6994
}
7095

7196
private fun executionToPriority(execution: ExecutionNumber) =
72-
execution to executionToUsefulLines[execution]!!.size
97+
Triple(execution, executionToUsefulLines[execution]!!.size, executionToSourcePriority[execution]!!)
7398

7499
private fun removeLineFromExecution(execution: ExecutionNumber, line: LineNumber) {
75100
executionByPriority.remove(executionToPriority(execution))
@@ -87,12 +112,21 @@ class GreedyEssential private constructor(
87112
* Minimizes the given [executions] assuming the map represents mapping from execution id to covered
88113
* instruction ids.
89114
*
115+
* @param executions the mapping of execution ids to lists of lines covered by the execution.
116+
* @param sourcePriorities execution priorities: lower values correspond to more important executions
117+
* that should be kept everything else being equal.
118+
*
90119
* @return retained execution ids.
91120
*/
92-
fun minimize(executions: Map<Int, List<Int>>): List<Int> {
121+
fun minimize(executions: Map<Int, List<Int>>, sourcePriorities: Map<Int, Int> = emptyMap()): List<Int> {
93122
val convertedExecutions = executions
94123
.entries
95-
.associate { (execution, lines) -> ExecutionNumber(execution) to lines.map { LineNumber(it) } }
124+
.associate { (execution, lines) ->
125+
ExecutionNumber(execution) to ExecutionCoverageInfo(
126+
SourcePriority(sourcePriorities.getOrDefault(execution, 0)),
127+
lines.map { LineNumber(it) }
128+
)
129+
}
96130

97131
val prioritizer = GreedyEssential(convertedExecutions)
98132
val list = mutableListOf<ExecutionNumber>()

‎utbot-framework/src/main/kotlin/org/utbot/framework/minimization/Minimization.kt‎

Lines changed: 25 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,11 +13,14 @@ import org.utbot.framework.plugin.api.UtExecutableCallModel
1313
import org.utbot.framework.plugin.api.UtExecution
1414
import org.utbot.framework.plugin.api.UtExecutionFailure
1515
import org.utbot.framework.plugin.api.UtExecutionResult
16+
import org.utbot.framework.plugin.api.UtFailedExecution
1617
import org.utbot.framework.plugin.api.UtModel
1718
import org.utbot.framework.plugin.api.UtNullModel
1819
import org.utbot.framework.plugin.api.UtPrimitiveModel
1920
import org.utbot.framework.plugin.api.UtStatementModel
21+
import org.utbot.framework.plugin.api.UtSymbolicExecution
2022
import org.utbot.framework.plugin.api.UtVoidModel
23+
import org.utbot.fuzzer.UtFuzzedExecution
2124

2225

2326
/**
@@ -52,8 +55,17 @@ fun minimizeExecutions(executions: List<UtExecution>): List<UtExecution> {
5255
executions.indices.filter { executions[it].coverage?.coveredInstructions?.isEmpty() ?: true }.toSet()
5356
// ^^^ here we add executions with empty or null coverage, because it happens only if a concrete execution failed,
5457
// so we don't know the actual coverage for such executions
58+
59+
// If the minimizer is configured to prefer symbolic executions, compute the priority for each execution,
60+
// otherwise use an empty priority map to mark that all executions have the same priority
61+
val sourcePriorities = if (UtSettings.preferSymbolicExecutionsDuringMinimization) {
62+
executions.withIndex().associate { it.index to it.value.getSourcePriorityForMinimization() }
63+
} else {
64+
emptyMap()
65+
}
66+
5567
val mapping = buildMapping(executions.filterIndexed { idx, _ -> idx !in unknownCoverageExecutions })
56-
val usedExecutionIndexes = (GreedyEssential.minimize(mapping) + unknownCoverageExecutions).toSet()
68+
val usedExecutionIndexes = (GreedyEssential.minimize(mapping, sourcePriorities) + unknownCoverageExecutions).toSet()
5769

5870
val usedMinimizedExecutions = executions.filterIndexed { idx, _ -> idx in usedExecutionIndexes }
5971

@@ -64,6 +76,18 @@ fun minimizeExecutions(executions: List<UtExecution>): List<UtExecution> {
6476
}
6577
}
6678

79+
/**
80+
* Compute the priority of the given execution during minimization. Lower values correspond to higher priority.
81+
*
82+
* If [UtSettings.preferSymbolicExecutionsDuringMinimization] is true, minimizer will use these priorities
83+
* to select symbolic executions instead of fuzzer-generated executions with the same coverage.
84+
*/
85+
private fun UtExecution.getSourcePriorityForMinimization(): Int = when (this) {
86+
is UtSymbolicExecution -> 0
87+
is UtFuzzedExecution -> 1
88+
else -> 2
89+
}
90+
6791
/**
6892
* Groups the [executions] by their `paths` on `first` [branchInstructionsNumber] `branch` instructions.
6993
*
@@ -150,7 +174,6 @@ private fun buildMapping(executions: List<UtExecution>): Map<Int, List<Int>> {
150174
val thrownExceptions = mutableMapOf<String, Long>()
151175
val mapping = mutableMapOf<Int, List<Int>>()
152176

153-
154177
executions.forEachIndexed { idx, execution ->
155178
execution.coverage?.let { coverage ->
156179
val instructionsWithoutExtra = coverage.coveredInstructions.map { it.id }

0 commit comments

Comments
 (0)