Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit90e85f4

Browse files
committed
Implement state initialization by fuzzing
1 parent74e7a34 commit90e85f4

File tree

7 files changed

+395
-44
lines changed

7 files changed

+395
-44
lines changed

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

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -258,7 +258,7 @@ object UtSettings {
258258

259259

260260
/**
261-
* Set to true to start fuzzing if symbolic execution haven't return anything
261+
* Set to true to start fuzzing if symbolic execution haven't return anything.
262262
*/
263263
var useFuzzing:Boolean by getBooleanProperty(true)
264264

@@ -272,6 +272,11 @@ object UtSettings {
272272
*/
273273
var fuzzingTimeoutInMillis:Int by getIntProperty(3_000)
274274

275+
/**
276+
* Set to true to initialize symbolic parameters by values from fuzzing.
277+
*/
278+
var useFuzzingInitialization:Boolean by getBooleanProperty(false)
279+
275280
/**
276281
* Generate tests that treat possible overflows in arithmetic operations as errors
277282
* that throw Arithmetic Exception.

‎utbot-framework/src/main/kotlin/org/utbot/engine/Extensions.kt‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,11 @@ import kotlin.reflect.jvm.javaMethod
4646
importkotlinx.collections.immutable.PersistentMap
4747
importkotlinx.collections.immutable.persistentHashMapOf
4848
importorg.utbot.engine.pc.UtSolverStatusUNDEFINED
49+
importorg.utbot.engine.pc.select
50+
importorg.utbot.framework.plugin.api.ClassId
51+
importorg.utbot.framework.plugin.api.util.isArray
4952
importsoot.ArrayType
53+
importsoot.IntType
5054
importsoot.PrimType
5155
importsoot.RefLikeType
5256
importsoot.RefType
@@ -303,6 +307,9 @@ fun classBytecodeSignatureToClassNameOrNull(signature: String?) =
303307
?.replace("$",".")
304308
?.let { it.substring(1, it.lastIndex) }
305309

310+
val <R>UtMethod<R>.hasThisInParameters:Boolean
311+
get()=!isConstructor&&!isStatic
312+
306313
val <R>UtMethod<R>.javaConstructor:Constructor<*>?
307314
get()= (callableas?KFunction<*>)?.javaConstructor
308315

@@ -484,3 +491,29 @@ val SootMethod.isUtMockAssumeOrExecuteConcretely
484491
*/
485492
valSootMethod.isPreconditionCheckMethod
486493
get()= declaringClass.isOverridden&& name=="preconditionCheck"
494+
495+
/**
496+
* Search symbolic ordinal of enum in memory by address [addr].
497+
*/
498+
fun Memory.findOrdinal(type:RefType,addr:UtAddrExpression) :PrimitiveValue {
499+
val array= findArray(MemoryChunkDescriptor(ENUM_ORDINAL, type,IntType.v()))
500+
return array.select(addr).toIntValue()
501+
}
502+
503+
fun ClassId.toSoot():SootClass=Scene.v().getSootClass(this.name)
504+
505+
// Our and Soot's representations are not same
506+
fun ClassId.toType():Type {
507+
var arrayDim=0
508+
var result=this
509+
while (result.isArray) {
510+
++arrayDim
511+
result= result.elementClassId!!
512+
}
513+
val typeResult=Scene.v().getType(result.name)
514+
returnif (arrayDim!=0) {
515+
ArrayType.v(typeResult, arrayDim)
516+
}else {
517+
typeResult
518+
}
519+
}

‎utbot-framework/src/main/kotlin/org/utbot/engine/Traverser.kt‎

Lines changed: 20 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -255,6 +255,12 @@ class Traverser(
255255
// A counter for objects created as native method call result.
256256
privatevar unboundedConstCounter=0
257257

258+
funcollectUpdates():SymbolicStateUpdate {
259+
val updates= queuedSymbolicStateUpdates
260+
queuedSymbolicStateUpdates=SymbolicStateUpdate()
261+
return updates
262+
}
263+
258264
funtraverse(state:ExecutionState):Collection<ExecutionState> {
259265
val context=TraversalContext()
260266

@@ -1245,13 +1251,7 @@ class Traverser(
12451251
}
12461252
isClassConstant-> {
12471253
val sootType= constant.toSootType()
1248-
val result=if (sootTypeisRefLikeType) {
1249-
typeRegistry.createClassRef(sootType.baseType, sootType.numDimensions)
1250-
}else {
1251-
error("Can't get class constant for${constant.value}")
1252-
}
1253-
queuedSymbolicStateUpdates+= result.symbolicStateUpdate
1254-
(result.symbolicResultasSymbolicSuccess).value
1254+
createClassRef(sootType)
12551255
}
12561256
else-> error("Unsupported type:$constant")
12571257
}
@@ -1990,6 +1990,16 @@ class Traverser(
19901990
returnObjectValue(typeStorage, addr)
19911991
}
19921992

1993+
funcreateClassRef(sootType:Type):SymbolicValue {
1994+
val result=if (sootTypeisRefLikeType) {
1995+
typeRegistry.createClassRef(sootType.baseType, sootType.numDimensions)
1996+
}else {
1997+
error("Can't get class constant for$sootType")
1998+
}
1999+
queuedSymbolicStateUpdates+= result.symbolicStateUpdate
2000+
return (result.symbolicResultasSymbolicSuccess).value
2001+
}
2002+
19932003
privatefunarrayUpdate(array:ArrayValue,index:PrimitiveValue,value:UtExpression):MemoryUpdate {
19942004
val type= array.type
19952005
val chunkId= typeRegistry.arrayChunkId(type)
@@ -2052,7 +2062,7 @@ class Traverser(
20522062
*
20532063
* If the field belongs to a substitute object, record the read access for the real type instead.
20542064
*/
2055-
privatefunrecordInstanceFieldRead(addr:UtAddrExpression,field:SootField) {
2065+
funrecordInstanceFieldRead(addr:UtAddrExpression,field:SootField) {
20562066
val realType= typeRegistry.findRealType(field.declaringClass.type)
20572067
if (realTypeisRefType) {
20582068
val readOperation=InstanceFieldReadOperation(addr,FieldId(realType.id, field.name))
@@ -2681,10 +2691,8 @@ class Traverser(
26812691
returnwhen (instance) {
26822692
isReferenceValue-> {
26832693
val type= instance.type
2684-
val createClassRef=if (typeisRefLikeType) {
2685-
typeRegistry.createClassRef(type.baseType, type.numDimensions)
2686-
}else {
2687-
error("Can't get class name for$type")
2694+
val createClassRef= asMethodResult {
2695+
createClassRef(type)
26882696
}
26892697
OverrideResult(success=true, createClassRef)
26902698
}

‎utbot-framework/src/main/kotlin/org/utbot/engine/UtBotSymbolicEngine.kt‎

Lines changed: 117 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
11
packageorg.utbot.engine
22

3+
importjava.lang.reflect.Method
4+
importkotlin.random.Random
5+
importkotlin.system.measureTimeMillis
36
importkotlinx.collections.immutable.persistentListOf
47
importkotlinx.coroutines.CancellationException
58
importkotlinx.coroutines.Job
@@ -22,6 +25,8 @@ import org.utbot.common.bracket
2225
importorg.utbot.common.debug
2326
importorg.utbot.common.workaround
2427
importorg.utbot.engine.MockStrategy.NO_MOCKS
28+
importorg.utbot.engine.mvisitors.ConstraintModelVisitor
29+
importorg.utbot.engine.mvisitors.visit
2530
importorg.utbot.engine.pc.UtArraySelectExpression
2631
importorg.utbot.engine.pc.UtBoolExpression
2732
importorg.utbot.engine.pc.UtContextInitializer
@@ -70,34 +75,37 @@ import org.utbot.framework.plugin.api.UtError
7075
importorg.utbot.framework.plugin.api.UtExecution
7176
importorg.utbot.framework.plugin.api.UtInstrumentation
7277
importorg.utbot.framework.plugin.api.UtMethod
78+
importorg.utbot.framework.plugin.api.UtModel
7379
importorg.utbot.framework.plugin.api.UtNullModel
7480
importorg.utbot.framework.plugin.api.UtOverflowFailure
7581
importorg.utbot.framework.plugin.api.UtResult
76-
importorg.utbot.framework.util.graph
7782
importorg.utbot.framework.plugin.api.onSuccess
83+
importorg.utbot.framework.plugin.api.util.description
7884
importorg.utbot.framework.plugin.api.util.executableId
7985
importorg.utbot.framework.plugin.api.util.id
8086
importorg.utbot.framework.plugin.api.util.utContext
81-
importorg.utbot.framework.plugin.api.util.description
82-
importorg.utbot.framework.util.jimpleBody
8387
importorg.utbot.framework.plugin.api.util.voidClassId
88+
importorg.utbot.framework.util.graph
89+
importorg.utbot.framework.util.jimpleBody
8490
importorg.utbot.fuzzer.FallbackModelProvider
8591
importorg.utbot.fuzzer.FuzzedMethodDescription
8692
importorg.utbot.fuzzer.FuzzedValue
8793
importorg.utbot.fuzzer.ModelProvider
8894
importorg.utbot.fuzzer.Trie
8995
importorg.utbot.fuzzer.collectConstantsForFuzzer
9096
importorg.utbot.fuzzer.defaultModelProviders
97+
importorg.utbot.fuzzer.exceptIsInstance
9198
importorg.utbot.fuzzer.fuzz
9299
importorg.utbot.fuzzer.names.MethodBasedNameSuggester
93100
importorg.utbot.fuzzer.names.ModelBasedNameSuggester
101+
importorg.utbot.fuzzer.providers.CollectionModelProvider
102+
importorg.utbot.fuzzer.providers.NullModelProvider
94103
importorg.utbot.fuzzer.providers.ObjectModelProvider
95104
importorg.utbot.instrumentation.ConcreteExecutor
105+
importsoot.jimple.ParameterRef
96106
importsoot.jimple.Stmt
107+
importsoot.jimple.internal.JIdentityStmt
97108
importsoot.tagkit.ParamNamesTag
98-
importjava.lang.reflect.Method
99-
importkotlin.random.Random
100-
importkotlin.system.measureTimeMillis
101109

102110
val logger=KotlinLogging.logger {}
103111
val pathLogger=KotlinLogging.logger(logger.name+".path")
@@ -158,6 +166,11 @@ class UtBotSymbolicEngine(
158166
logger.trace {"JIMPLE for$methodUnderTest:\n$this" }
159167
}.graph()
160168

169+
privateval methodUnderTestId=if (methodUnderTest.isConstructor) {
170+
methodUnderTest.javaConstructor!!.executableId
171+
}else {
172+
methodUnderTest.javaMethod!!.executableId
173+
}
161174
privateval methodUnderAnalysisStmts:Set<Stmt>= graph.stmts.toSet()
162175
privateval globalGraph=InterProceduralUnitGraph(graph)
163176
privateval typeRegistry:TypeRegistry=TypeRegistry()
@@ -347,7 +360,7 @@ class UtBotSymbolicEngine(
347360
}
348361
for (newStatein newStates) {
349362
when (newState.label) {
350-
StateLabel.INTERMEDIATE->pathSelector.offer(newState)
363+
StateLabel.INTERMEDIATE->processIntermediateState(newState)
351364
StateLabel.CONCRETE-> statesForConcreteExecution.add(newState)
352365
StateLabel.TERMINAL-> consumeTerminalState(newState)
353366
}
@@ -365,28 +378,66 @@ class UtBotSymbolicEngine(
365378
}
366379
}
367380

381+
privatefungetModelProviderToFuzzingInitializing(modelProvider:ModelProvider):ModelProvider=
382+
modelProvider
383+
.with(NullModelProvider)
384+
// these providers use AssembleModel, now impossible to get path conditions from it
385+
.exceptIsInstance<ObjectModelProvider>()
386+
.exceptIsInstance<CollectionModelProvider>()
368387

369388
/**
370-
* Run fuzzing flow.
371-
*
372-
* @param until is used by fuzzer to cancel all tasks if the current time is over this value
373-
* @param modelProvider provides model values for a method
389+
* Construct sequence of [ExecutionState] that's initialized by fuzzing.
374390
*/
375-
funfuzzing(until:Long =Long.MAX_VALUE,modelProvider: (ModelProvider)->ModelProvider = { it })= flow {
376-
val executableId=if (methodUnderTest.isConstructor) {
377-
methodUnderTest.javaConstructor!!.executableId
378-
}else {
379-
methodUnderTest.javaMethod!!.executableId
380-
}
391+
privatefunstatesInitializedFromFuzzing(state:ExecutionState):Sequence<ExecutionState>=
392+
fuzzInitialValues(::getModelProviderToFuzzingInitializing)
393+
.map { parameters->
394+
val stateParametersWithoutThis=if (methodUnderTest.hasThisInParameters) {
395+
state.parameters.drop(1)
396+
}else {
397+
state.parameters
398+
}
399+
val initialConstraints= stateParametersWithoutThis
400+
.zip(parameters)
401+
.flatMap { (parameter, fuzzedValue)->
402+
buildConstraintsFromModel(parameter.value, fuzzedValue.model)
403+
}
404+
state.update(traverser.collectUpdates()).apply {
405+
solver.checkWithInitialConstraints(initialConstraints)
406+
}
407+
}
408+
409+
privatefunbuildConstraintsFromModel(symbolicValue:SymbolicValue,model:UtModel):List<UtBoolExpression> {
410+
val modelVisitor=ConstraintModelVisitor(symbolicValue, traverser)
411+
return model.visit(modelVisitor)
412+
}
381413

382-
val isFuzzable= executableId.parameters.all { classId->
414+
privatefunfuzzInitialValues(
415+
modelProvider: (ModelProvider)->ModelProvider,
416+
methodDescription:FuzzedMethodDescription? = null
417+
):Sequence<List<FuzzedValue>> {
418+
val isFuzzable= methodUnderTestId.parameters.all { classId->
383419
classId!=Method::class.java.id&&// causes the child process crash at invocation
384-
classId!=Class::class.java.id// causes java.lang.IllegalAccessException: java.lang.Class at sun.misc.Unsafe.allocateInstance(Native Method)
420+
classId!=Class::class.java.id// causes java.lang.IllegalAccessException: java.lang.Class at sun.misc.Unsafe.allocateInstance(Native Method)
385421
}
386422
if (!isFuzzable) {
387-
return@flow
423+
return emptySequence()
388424
}
389425

426+
val methodDescriptionOrDefault= methodDescription?:
427+
FuzzedMethodDescription(methodUnderTestId, collectConstantsForFuzzer(graph))
428+
val initializedModelProvider= modelProvider(defaultModelProviders { nextDefaultModelId++ })
429+
430+
return fuzz(methodDescriptionOrDefault, initializedModelProvider)
431+
}
432+
433+
434+
/**
435+
* Run fuzzing flow.
436+
*
437+
* @param until is used by fuzzer to cancel all tasks if the current time is over this value
438+
* @param modelProvider provides model values for a method
439+
*/
440+
funfuzzing(until:Long =Long.MAX_VALUE,modelProvider: (ModelProvider)->ModelProvider = { it })= flow {
390441
val fallbackModelProvider=FallbackModelProvider { nextDefaultModelId++ }
391442
val constantValues= collectConstantsForFuzzer(graph)
392443

@@ -411,28 +462,28 @@ class UtBotSymbolicEngine(
411462
}
412463
}
413464

414-
val methodUnderTestDescription=FuzzedMethodDescription(executableId, collectConstantsForFuzzer(graph)).apply {
415-
compilableName=if (methodUnderTest.isMethod)executableId.nameelsenull
416-
className=executableId.classId.simpleName
417-
packageName=executableId.classId.packageName
465+
val methodUnderTestDescription=FuzzedMethodDescription(methodUnderTestId, collectConstantsForFuzzer(graph)).apply {
466+
compilableName=if (methodUnderTest.isMethod)methodUnderTestId.nameelsenull
467+
className=methodUnderTestId.classId.simpleName
468+
packageName=methodUnderTestId.classId.packageName
418469
val names= graph.body.method.tags.filterIsInstance<ParamNamesTag>().firstOrNull()?.names
419470
parameterNameMap= { index-> names?.getOrNull(index) }
420471
}
421472
val coveredInstructionTracker=Trie(Instruction::id)
422473
val coveredInstructionValues= mutableMapOf<Trie.Node<Instruction>,List<FuzzedValue>>()
423474
var attempts=UtSettings.fuzzingMaxAttempts
424-
val hasMethodUnderTestParametersToFuzz=executableId.parameters.isNotEmpty()
475+
val hasMethodUnderTestParametersToFuzz=methodUnderTestId.parameters.isNotEmpty()
425476
val fuzzedValues=if (hasMethodUnderTestParametersToFuzz) {
426-
fuzz(methodUnderTestDescription, modelProvider(defaultModelProviders { nextDefaultModelId++ }))
477+
fuzzInitialValues(modelProvider, methodUnderTestDescription)
427478
}else {
428479
// in case a method with no parameters is passed fuzzing tries to fuzz this instance with different constructors, setters and field mutators
429480
val thisMethodDescription=FuzzedMethodDescription("thisInstance", voidClassId,listOf(methodUnderTest.clazz.id), constantValues).apply {
430-
className=executableId.classId.simpleName
431-
packageName=executableId.classId.packageName
481+
className=methodUnderTestId.classId.simpleName
482+
packageName=methodUnderTestId.classId.packageName
432483
}
433-
fuzz(thisMethodDescription,ObjectModelProvider { nextDefaultModelId++ }.apply {
484+
fuzzInitialValues({ObjectModelProvider { nextDefaultModelId++ }.apply {
434485
limitValuesCreatedByFieldAccessors=500
435-
})
486+
} }, thisMethodDescription)
436487
}
437488
fuzzedValues.forEach { values->
438489
if (System.currentTimeMillis()>= until) {
@@ -515,6 +566,42 @@ class UtBotSymbolicEngine(
515566
emit(failedConcreteExecution)
516567
}
517568

569+
privatefunprocessIntermediateState(
570+
state:ExecutionState
571+
) {
572+
require(state.label==StateLabel.INTERMEDIATE)
573+
574+
// create new state initialized by fuzzing if it is the last identity stmt for parameter
575+
val initializedStateByFuzzing=if (
576+
UtSettings.useFuzzingInitialization&&
577+
!state.isInNestedMethod()&&
578+
state.stmtisJIdentityStmt&&
579+
state.stmt.rightOpisParameterRef
580+
) {
581+
var expectedParamsSize=if (methodUnderTest.isConstructor) {
582+
methodUnderTest.javaConstructor!!.parameterCount
583+
}else {
584+
methodUnderTest.javaMethod!!.parameterCount
585+
}
586+
if (methodUnderTest.hasThisInParameters) {
587+
++expectedParamsSize
588+
}
589+
590+
// check that is the last parameter identity stmt
591+
if (expectedParamsSize== state.parameters.size) {
592+
statesInitializedFromFuzzing(state).firstOrNull()
593+
}else {
594+
null
595+
}
596+
}else {
597+
null
598+
}
599+
600+
initializedStateByFuzzing?.let {
601+
pathSelector.offer(it)
602+
}?: pathSelector.offer(state)
603+
}
604+
518605
privatesuspendfun FlowCollector<UtResult>.consumeTerminalState(
519606
state:ExecutionState,
520607
) {

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp