./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash a077c1334c11d8329da2d0c58ca917b2036581fa7e949d1d304e3346ec54a811 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 22:46:57,135 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 22:46:57,190 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 22:46:57,193 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 22:46:57,193 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 22:46:57,215 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 22:46:57,215 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 22:46:57,215 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 22:46:57,216 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 22:46:57,217 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 22:46:57,217 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 22:46:57,217 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 22:46:57,218 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 22:46:57,219 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 22:46:57,219 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 22:46:57,220 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 22:46:57,220 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 22:46:57,220 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 22:46:57,220 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 22:46:57,223 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 22:46:57,224 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 22:46:57,224 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 22:46:57,224 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 22:46:57,224 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 22:46:57,225 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 22:46:57,225 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 22:46:57,225 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 22:46:57,225 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 22:46:57,225 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 22:46:57,225 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 22:46:57,226 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 22:46:57,226 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 22:46:57,226 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:46:57,226 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 22:46:57,226 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 22:46:57,226 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 22:46:57,227 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 22:46:57,227 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 22:46:57,227 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 22:46:57,227 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 22:46:57,228 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 22:46:57,229 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 22:46:57,229 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> a077c1334c11d8329da2d0c58ca917b2036581fa7e949d1d304e3346ec54a811 [2024-11-09 22:46:57,450 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 22:46:57,467 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 22:46:57,470 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 22:46:57,471 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 22:46:57,471 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 22:46:57,472 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c [2024-11-09 22:46:58,593 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 22:46:58,737 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 22:46:58,738 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c [2024-11-09 22:46:58,743 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ced7a5d96/6975f6532e37426cb8b31011e90a7d3a/FLAG7f0629bce [2024-11-09 22:46:59,166 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ced7a5d96/6975f6532e37426cb8b31011e90a7d3a [2024-11-09 22:46:59,168 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 22:46:59,169 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 22:46:59,170 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 22:46:59,170 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 22:46:59,175 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 22:46:59,175 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,176 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2dc1ee07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59, skipping insertion in model container [2024-11-09 22:46:59,176 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,188 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 22:46:59,315 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c[526,539] [2024-11-09 22:46:59,332 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:46:59,348 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 22:46:59,360 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c[526,539] [2024-11-09 22:46:59,367 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:46:59,383 INFO L204 MainTranslator]: Completed translation [2024-11-09 22:46:59,386 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59 WrapperNode [2024-11-09 22:46:59,386 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 22:46:59,387 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 22:46:59,387 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 22:46:59,387 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 22:46:59,392 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,398 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,410 INFO L138 Inliner]: procedures = 14, calls = 23, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 62 [2024-11-09 22:46:59,410 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 22:46:59,411 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 22:46:59,411 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 22:46:59,411 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 22:46:59,418 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,418 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,419 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,427 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-09 22:46:59,428 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,428 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,430 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,431 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,432 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,434 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,435 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 22:46:59,436 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 22:46:59,436 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 22:46:59,436 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 22:46:59,437 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (1/1) ... [2024-11-09 22:46:59,440 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:46:59,451 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:46:59,462 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-09 22:46:59,464 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-09 22:46:59,494 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 22:46:59,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 22:46:59,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-09 22:46:59,494 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 22:46:59,494 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 22:46:59,494 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 22:46:59,494 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 22:46:59,542 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 22:46:59,544 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 22:46:59,708 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 22:46:59,708 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 22:46:59,717 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 22:46:59,717 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 22:46:59,717 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:46:59 BoogieIcfgContainer [2024-11-09 22:46:59,717 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 22:46:59,719 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 22:46:59,719 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 22:46:59,721 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 22:46:59,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 10:46:59" (1/3) ... [2024-11-09 22:46:59,722 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70a486ef and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:46:59, skipping insertion in model container [2024-11-09 22:46:59,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:46:59" (2/3) ... [2024-11-09 22:46:59,722 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70a486ef and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:46:59, skipping insertion in model container [2024-11-09 22:46:59,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:46:59" (3/3) ... [2024-11-09 22:46:59,723 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_valuebound5.c [2024-11-09 22:46:59,734 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 22:46:59,734 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 22:46:59,774 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 22:46:59,779 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@7e4c00b7, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 22:46:59,779 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 22:46:59,783 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-09 22:46:59,787 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-09 22:46:59,787 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:46:59,788 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:46:59,788 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:46:59,792 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:46:59,792 INFO L85 PathProgramCache]: Analyzing trace with hash -292126860, now seen corresponding path program 1 times [2024-11-09 22:46:59,799 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:46:59,799 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [976696191] [2024-11-09 22:46:59,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:46:59,800 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:46:59,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:46:59,904 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:46:59,905 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:46:59,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [976696191] [2024-11-09 22:46:59,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [976696191] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:46:59,906 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:46:59,906 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 22:46:59,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1078699931] [2024-11-09 22:46:59,907 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:46:59,910 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 22:46:59,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:46:59,923 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 22:46:59,924 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:46:59,925 INFO L87 Difference]: Start difference. First operand has 29 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:46:59,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:46:59,939 INFO L93 Difference]: Finished difference Result 55 states and 89 transitions. [2024-11-09 22:46:59,939 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 22:46:59,940 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-09 22:46:59,940 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:46:59,944 INFO L225 Difference]: With dead ends: 55 [2024-11-09 22:46:59,944 INFO L226 Difference]: Without dead ends: 25 [2024-11-09 22:46:59,947 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:46:59,951 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:46:59,952 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:46:59,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-09 22:46:59,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-09 22:46:59,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 22:46:59,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 33 transitions. [2024-11-09 22:46:59,975 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 33 transitions. Word has length 11 [2024-11-09 22:46:59,976 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:46:59,976 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 33 transitions. [2024-11-09 22:46:59,976 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:46:59,976 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 33 transitions. [2024-11-09 22:46:59,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-09 22:46:59,977 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:46:59,977 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:46:59,977 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 22:46:59,977 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:46:59,978 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:46:59,978 INFO L85 PathProgramCache]: Analyzing trace with hash -2099581323, now seen corresponding path program 1 times [2024-11-09 22:46:59,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:46:59,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1190783280] [2024-11-09 22:46:59,978 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:46:59,978 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:46:59,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:00,102 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:47:00,102 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:00,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1190783280] [2024-11-09 22:47:00,103 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1190783280] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:47:00,103 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:47:00,103 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:47:00,103 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1437652300] [2024-11-09 22:47:00,103 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:47:00,104 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:47:00,104 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:00,105 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:47:00,105 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:47:00,105 INFO L87 Difference]: Start difference. First operand 25 states and 33 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:47:00,158 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:00,159 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2024-11-09 22:47:00,159 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:47:00,159 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-09 22:47:00,159 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:00,160 INFO L225 Difference]: With dead ends: 40 [2024-11-09 22:47:00,160 INFO L226 Difference]: Without dead ends: 37 [2024-11-09 22:47:00,160 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:47:00,161 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 10 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:00,162 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 101 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:47:00,162 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-09 22:47:00,170 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 29. [2024-11-09 22:47:00,171 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 22:47:00,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 36 transitions. [2024-11-09 22:47:00,173 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 36 transitions. Word has length 11 [2024-11-09 22:47:00,173 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:00,173 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 36 transitions. [2024-11-09 22:47:00,175 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:47:00,175 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 36 transitions. [2024-11-09 22:47:00,175 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-09 22:47:00,175 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:00,176 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:00,176 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 22:47:00,176 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:00,177 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:00,177 INFO L85 PathProgramCache]: Analyzing trace with hash 2100820203, now seen corresponding path program 1 times [2024-11-09 22:47:00,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:00,178 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1102774538] [2024-11-09 22:47:00,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:00,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:00,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:00,286 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:47:00,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:00,295 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:47:00,299 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:00,299 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1102774538] [2024-11-09 22:47:00,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1102774538] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:47:00,300 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:47:00,300 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:47:00,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1028363043] [2024-11-09 22:47:00,300 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:47:00,300 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:47:00,301 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:00,301 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:47:00,302 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:47:00,302 INFO L87 Difference]: Start difference. First operand 29 states and 36 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 22:47:00,364 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:00,364 INFO L93 Difference]: Finished difference Result 44 states and 55 transitions. [2024-11-09 22:47:00,365 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:47:00,366 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2024-11-09 22:47:00,366 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:00,366 INFO L225 Difference]: With dead ends: 44 [2024-11-09 22:47:00,367 INFO L226 Difference]: Without dead ends: 41 [2024-11-09 22:47:00,367 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:47:00,368 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 10 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:00,368 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 98 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:47:00,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-09 22:47:00,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2024-11-09 22:47:00,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 22:47:00,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 39 transitions. [2024-11-09 22:47:00,376 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 39 transitions. Word has length 16 [2024-11-09 22:47:00,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:00,376 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 39 transitions. [2024-11-09 22:47:00,376 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 22:47:00,377 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 39 transitions. [2024-11-09 22:47:00,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-09 22:47:00,377 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:00,377 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:00,378 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 22:47:00,378 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:00,378 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:00,378 INFO L85 PathProgramCache]: Analyzing trace with hash 1262954485, now seen corresponding path program 1 times [2024-11-09 22:47:00,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:00,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [12349486] [2024-11-09 22:47:00,379 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:00,379 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:00,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:47:00,399 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [708587716] [2024-11-09 22:47:00,399 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:00,400 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:00,400 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:00,402 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:00,403 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 22:47:00,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:00,455 INFO L255 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 22:47:00,459 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:00,567 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:47:00,568 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:47:00,576 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:00,576 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [12349486] [2024-11-09 22:47:00,577 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:47:00,577 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [708587716] [2024-11-09 22:47:00,577 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [708587716] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:47:00,577 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:47:00,578 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:47:00,578 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1106159941] [2024-11-09 22:47:00,578 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:47:00,578 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:47:00,578 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:00,579 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:47:00,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:47:00,579 INFO L87 Difference]: Start difference. First operand 33 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:47:00,631 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:00,631 INFO L93 Difference]: Finished difference Result 63 states and 80 transitions. [2024-11-09 22:47:00,632 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:47:00,632 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2024-11-09 22:47:00,632 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:00,633 INFO L225 Difference]: With dead ends: 63 [2024-11-09 22:47:00,633 INFO L226 Difference]: Without dead ends: 48 [2024-11-09 22:47:00,633 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:47:00,634 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 6 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:00,634 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 101 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:47:00,635 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-09 22:47:00,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2024-11-09 22:47:00,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 32 states have internal predecessors, (36), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 22:47:00,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 59 transitions. [2024-11-09 22:47:00,649 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 59 transitions. Word has length 21 [2024-11-09 22:47:00,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:00,649 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 59 transitions. [2024-11-09 22:47:00,649 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:47:00,649 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 59 transitions. [2024-11-09 22:47:00,650 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-09 22:47:00,650 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:00,650 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:00,662 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 22:47:00,850 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:00,851 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:00,851 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:00,852 INFO L85 PathProgramCache]: Analyzing trace with hash -23433476, now seen corresponding path program 1 times [2024-11-09 22:47:00,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:00,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1767785988] [2024-11-09 22:47:00,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:00,852 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:00,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:47:00,872 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2005945223] [2024-11-09 22:47:00,872 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:00,875 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:00,875 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:00,876 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:00,881 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 22:47:00,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:00,922 INFO L255 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:47:00,924 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:01,006 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 22:47:01,007 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:47:01,007 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:01,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1767785988] [2024-11-09 22:47:01,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:47:01,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2005945223] [2024-11-09 22:47:01,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2005945223] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:47:01,008 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:47:01,008 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:47:01,008 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [443298579] [2024-11-09 22:47:01,008 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:47:01,009 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:47:01,009 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:01,009 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:47:01,009 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:47:01,009 INFO L87 Difference]: Start difference. First operand 48 states and 59 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 22:47:01,069 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:01,069 INFO L93 Difference]: Finished difference Result 63 states and 78 transitions. [2024-11-09 22:47:01,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:47:01,070 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 29 [2024-11-09 22:47:01,070 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:01,071 INFO L225 Difference]: With dead ends: 63 [2024-11-09 22:47:01,071 INFO L226 Difference]: Without dead ends: 60 [2024-11-09 22:47:01,071 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:47:01,072 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:01,072 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 82 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:47:01,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-09 22:47:01,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-11-09 22:47:01,084 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-09 22:47:01,085 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 74 transitions. [2024-11-09 22:47:01,086 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 74 transitions. Word has length 29 [2024-11-09 22:47:01,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:01,087 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 74 transitions. [2024-11-09 22:47:01,087 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 22:47:01,087 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 74 transitions. [2024-11-09 22:47:01,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-09 22:47:01,090 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:01,090 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:01,102 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 22:47:01,290 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:01,291 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:01,291 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:01,291 INFO L85 PathProgramCache]: Analyzing trace with hash 253378592, now seen corresponding path program 1 times [2024-11-09 22:47:01,291 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:01,292 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1256218511] [2024-11-09 22:47:01,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:01,292 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:01,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:47:01,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [448770037] [2024-11-09 22:47:01,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:01,310 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:01,310 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:01,311 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:01,313 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 22:47:01,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:01,357 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 22:47:01,358 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:01,454 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-09 22:47:01,454 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:01,516 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 22:47:01,517 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:01,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1256218511] [2024-11-09 22:47:01,517 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:47:01,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [448770037] [2024-11-09 22:47:01,517 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [448770037] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-09 22:47:01,517 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:47:01,518 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-09 22:47:01,518 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [704933244] [2024-11-09 22:47:01,518 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:47:01,518 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:47:01,518 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:01,519 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:47:01,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-09 22:47:01,519 INFO L87 Difference]: Start difference. First operand 59 states and 74 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 22:47:02,848 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.29s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:47:02,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:02,858 INFO L93 Difference]: Finished difference Result 71 states and 88 transitions. [2024-11-09 22:47:02,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:47:02,858 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 39 [2024-11-09 22:47:02,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:02,860 INFO L225 Difference]: With dead ends: 71 [2024-11-09 22:47:02,860 INFO L226 Difference]: Without dead ends: 68 [2024-11-09 22:47:02,860 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 69 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:47:02,862 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 6 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:02,864 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 93 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-09 22:47:02,864 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2024-11-09 22:47:02,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 67. [2024-11-09 22:47:02,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 43 states have (on average 1.1627906976744187) internal successors, (50), 46 states have internal predecessors, (50), 17 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-09 22:47:02,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 83 transitions. [2024-11-09 22:47:02,873 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 83 transitions. Word has length 39 [2024-11-09 22:47:02,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:02,874 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 83 transitions. [2024-11-09 22:47:02,874 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 22:47:02,874 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 83 transitions. [2024-11-09 22:47:02,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-09 22:47:02,875 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:02,875 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:02,888 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-09 22:47:03,075 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:03,076 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:03,076 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:03,076 INFO L85 PathProgramCache]: Analyzing trace with hash -1361005644, now seen corresponding path program 1 times [2024-11-09 22:47:03,076 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:03,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1408592608] [2024-11-09 22:47:03,076 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:03,076 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:03,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,156 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:47:03,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,160 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:47:03,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,162 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:47:03,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,166 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:47:03,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,169 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:47:03,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,172 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-09 22:47:03,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,177 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 22:47:03,177 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:03,177 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1408592608] [2024-11-09 22:47:03,177 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1408592608] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:47:03,177 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:47:03,178 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:47:03,178 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1884594187] [2024-11-09 22:47:03,178 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:47:03,178 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:47:03,178 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:03,182 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:47:03,182 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:47:03,183 INFO L87 Difference]: Start difference. First operand 67 states and 83 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-09 22:47:03,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:03,215 INFO L93 Difference]: Finished difference Result 76 states and 92 transitions. [2024-11-09 22:47:03,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:47:03,216 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 45 [2024-11-09 22:47:03,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:03,217 INFO L225 Difference]: With dead ends: 76 [2024-11-09 22:47:03,217 INFO L226 Difference]: Without dead ends: 62 [2024-11-09 22:47:03,217 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:47:03,218 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 3 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:03,219 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 111 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:47:03,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-11-09 22:47:03,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2024-11-09 22:47:03,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 40 states have (on average 1.15) internal successors, (46), 43 states have internal predecessors, (46), 15 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-09 22:47:03,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 75 transitions. [2024-11-09 22:47:03,232 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 75 transitions. Word has length 45 [2024-11-09 22:47:03,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:03,234 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 75 transitions. [2024-11-09 22:47:03,234 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-09 22:47:03,235 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 75 transitions. [2024-11-09 22:47:03,235 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-09 22:47:03,235 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:03,236 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:03,236 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-09 22:47:03,236 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:03,236 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:03,236 INFO L85 PathProgramCache]: Analyzing trace with hash -646613615, now seen corresponding path program 1 times [2024-11-09 22:47:03,236 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:03,236 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1325456008] [2024-11-09 22:47:03,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:03,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:03,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:47:03,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [560958848] [2024-11-09 22:47:03,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:03,259 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:03,259 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:03,262 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:03,263 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 22:47:03,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:03,311 INFO L255 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-09 22:47:03,324 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:03,611 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-09 22:47:03,612 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:04,905 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-09 22:47:04,906 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:04,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1325456008] [2024-11-09 22:47:04,906 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:47:04,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [560958848] [2024-11-09 22:47:04,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [560958848] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:47:04,906 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:47:04,906 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-09 22:47:04,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1891200862] [2024-11-09 22:47:04,907 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:47:04,907 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 22:47:04,908 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:04,908 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 22:47:04,908 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:47:04,909 INFO L87 Difference]: Start difference. First operand 62 states and 75 transitions. Second operand has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-09 22:47:05,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:05,418 INFO L93 Difference]: Finished difference Result 148 states and 193 transitions. [2024-11-09 22:47:05,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-09 22:47:05,419 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 61 [2024-11-09 22:47:05,419 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:05,420 INFO L225 Difference]: With dead ends: 148 [2024-11-09 22:47:05,420 INFO L226 Difference]: Without dead ends: 122 [2024-11-09 22:47:05,421 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 107 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2024-11-09 22:47:05,421 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 35 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 309 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 357 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 309 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:05,421 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 269 Invalid, 357 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 309 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 22:47:05,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-09 22:47:05,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 120. [2024-11-09 22:47:05,440 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 83 states have internal predecessors, (92), 31 states have call successors, (31), 10 states have call predecessors, (31), 10 states have return successors, (30), 26 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-09 22:47:05,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 153 transitions. [2024-11-09 22:47:05,441 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 153 transitions. Word has length 61 [2024-11-09 22:47:05,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:05,441 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 153 transitions. [2024-11-09 22:47:05,441 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-09 22:47:05,441 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 153 transitions. [2024-11-09 22:47:05,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-09 22:47:05,442 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:05,442 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:05,455 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-09 22:47:05,643 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:05,643 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:05,643 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:05,644 INFO L85 PathProgramCache]: Analyzing trace with hash -641848553, now seen corresponding path program 1 times [2024-11-09 22:47:05,644 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:05,644 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [686306634] [2024-11-09 22:47:05,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:05,644 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:05,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:47:05,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1417324539] [2024-11-09 22:47:05,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:05,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:05,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:05,660 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:05,662 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 22:47:05,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:05,706 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-09 22:47:05,708 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:05,966 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-09 22:47:05,966 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:06,499 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-09 22:47:06,500 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:06,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [686306634] [2024-11-09 22:47:06,500 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:47:06,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1417324539] [2024-11-09 22:47:06,500 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1417324539] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:47:06,500 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:47:06,500 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2024-11-09 22:47:06,500 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1591316194] [2024-11-09 22:47:06,500 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:47:06,501 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-09 22:47:06,501 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:06,501 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-09 22:47:06,501 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=294, Unknown=0, NotChecked=0, Total=380 [2024-11-09 22:47:06,501 INFO L87 Difference]: Start difference. First operand 120 states and 153 transitions. Second operand has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) [2024-11-09 22:47:06,902 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:06,902 INFO L93 Difference]: Finished difference Result 192 states and 246 transitions. [2024-11-09 22:47:06,902 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-09 22:47:06,903 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) Word has length 72 [2024-11-09 22:47:06,903 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:06,904 INFO L225 Difference]: With dead ends: 192 [2024-11-09 22:47:06,904 INFO L226 Difference]: Without dead ends: 140 [2024-11-09 22:47:06,905 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 124 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=120, Invalid=386, Unknown=0, NotChecked=0, Total=506 [2024-11-09 22:47:06,905 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 27 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 238 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 238 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:06,905 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 208 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 238 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 22:47:06,906 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-11-09 22:47:06,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 113. [2024-11-09 22:47:06,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 74 states have (on average 1.135135135135135) internal successors, (84), 78 states have internal predecessors, (84), 27 states have call successors, (27), 11 states have call predecessors, (27), 11 states have return successors, (26), 23 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-09 22:47:06,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 137 transitions. [2024-11-09 22:47:06,922 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 137 transitions. Word has length 72 [2024-11-09 22:47:06,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:06,922 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 137 transitions. [2024-11-09 22:47:06,922 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) [2024-11-09 22:47:06,923 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 137 transitions. [2024-11-09 22:47:06,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-09 22:47:06,923 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:06,924 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:06,937 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-09 22:47:07,127 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:07,128 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:07,128 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:07,128 INFO L85 PathProgramCache]: Analyzing trace with hash 1640886345, now seen corresponding path program 1 times [2024-11-09 22:47:07,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:07,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [750875494] [2024-11-09 22:47:07,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:07,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:07,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,356 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:47:07,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,360 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:47:07,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:47:07,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,365 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:47:07,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,367 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:47:07,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,370 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-09 22:47:07,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,372 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-09 22:47:07,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,375 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-09 22:47:07,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,382 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2024-11-09 22:47:07,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,386 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-11-09 22:47:07,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,388 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2024-11-09 22:47:07,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,390 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 22:47:07,390 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:07,390 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [750875494] [2024-11-09 22:47:07,390 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [750875494] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:47:07,391 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1110488619] [2024-11-09 22:47:07,391 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:07,391 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:07,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:07,392 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:07,393 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 22:47:07,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:07,436 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 22:47:07,438 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:07,553 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 22:47:07,554 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:07,845 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 22:47:07,845 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1110488619] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:47:07,845 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:47:07,845 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2024-11-09 22:47:07,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [636183068] [2024-11-09 22:47:07,845 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:47:07,846 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-09 22:47:07,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:07,846 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-09 22:47:07,846 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2024-11-09 22:47:07,846 INFO L87 Difference]: Start difference. First operand 113 states and 137 transitions. Second operand has 13 states, 13 states have (on average 4.153846153846154) internal successors, (54), 11 states have internal predecessors, (54), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2024-11-09 22:47:07,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:07,966 INFO L93 Difference]: Finished difference Result 133 states and 157 transitions. [2024-11-09 22:47:07,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 22:47:07,967 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 4.153846153846154) internal successors, (54), 11 states have internal predecessors, (54), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) Word has length 77 [2024-11-09 22:47:07,967 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:07,968 INFO L225 Difference]: With dead ends: 133 [2024-11-09 22:47:07,968 INFO L226 Difference]: Without dead ends: 103 [2024-11-09 22:47:07,969 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 183 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:47:07,969 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 8 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 200 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:07,969 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 200 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:47:07,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-09 22:47:07,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2024-11-09 22:47:07,984 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 71 states have internal predecessors, (75), 23 states have call successors, (23), 11 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-09 22:47:07,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 120 transitions. [2024-11-09 22:47:07,985 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 120 transitions. Word has length 77 [2024-11-09 22:47:07,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:07,985 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 120 transitions. [2024-11-09 22:47:07,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 4.153846153846154) internal successors, (54), 11 states have internal predecessors, (54), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2024-11-09 22:47:07,985 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 120 transitions. [2024-11-09 22:47:07,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-11-09 22:47:07,986 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:07,986 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:07,999 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-09 22:47:08,190 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:08,191 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:08,191 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:08,191 INFO L85 PathProgramCache]: Analyzing trace with hash 985163622, now seen corresponding path program 2 times [2024-11-09 22:47:08,191 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:08,191 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [871964720] [2024-11-09 22:47:08,191 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:08,192 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:08,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:47:08,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1432529985] [2024-11-09 22:47:08,217 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:47:08,217 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:08,217 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:08,219 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:08,220 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 22:47:08,270 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:47:08,270 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:47:08,271 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-09 22:47:08,273 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:08,600 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-09 22:47:08,601 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:19,309 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-09 22:47:19,309 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:19,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [871964720] [2024-11-09 22:47:19,309 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:47:19,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1432529985] [2024-11-09 22:47:19,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1432529985] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:47:19,310 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:47:19,310 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2024-11-09 22:47:19,310 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [522933208] [2024-11-09 22:47:19,310 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:47:19,310 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 22:47:19,310 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:19,311 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 22:47:19,311 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2024-11-09 22:47:19,311 INFO L87 Difference]: Start difference. First operand 103 states and 120 transitions. Second operand has 21 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-09 22:47:33,024 WARN L286 SmtUtils]: Spent 13.47s on a formula simplification. DAG size of input: 168 DAG size of output: 83 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:47:36,058 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.70s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:47:38,608 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:38,608 INFO L93 Difference]: Finished difference Result 226 states and 289 transitions. [2024-11-09 22:47:38,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-09 22:47:38,608 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) Word has length 93 [2024-11-09 22:47:38,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:38,610 INFO L225 Difference]: With dead ends: 226 [2024-11-09 22:47:38,610 INFO L226 Difference]: Without dead ends: 189 [2024-11-09 22:47:38,610 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 165 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 15.2s TimeCoverageRelationStatistics Valid=158, Invalid=544, Unknown=0, NotChecked=0, Total=702 [2024-11-09 22:47:38,611 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 83 mSDsluCounter, 450 mSDsCounter, 0 mSdLazyCounter, 577 mSolverCounterSat, 112 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 498 SdHoareTripleChecker+Invalid, 689 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 112 IncrementalHoareTripleChecker+Valid, 577 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:38,611 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 498 Invalid, 689 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [112 Valid, 577 Invalid, 0 Unknown, 0 Unchecked, 5.1s Time] [2024-11-09 22:47:38,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-11-09 22:47:38,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 185. [2024-11-09 22:47:38,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 121 states have (on average 1.1487603305785123) internal successors, (139), 129 states have internal predecessors, (139), 49 states have call successors, (49), 14 states have call predecessors, (49), 14 states have return successors, (48), 41 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-09 22:47:38,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 236 transitions. [2024-11-09 22:47:38,652 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 236 transitions. Word has length 93 [2024-11-09 22:47:38,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:38,652 INFO L471 AbstractCegarLoop]: Abstraction has 185 states and 236 transitions. [2024-11-09 22:47:38,652 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-09 22:47:38,652 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 236 transitions. [2024-11-09 22:47:38,654 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2024-11-09 22:47:38,654 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:38,654 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:38,667 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-09 22:47:38,858 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:38,859 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:38,859 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:38,859 INFO L85 PathProgramCache]: Analyzing trace with hash 515453474, now seen corresponding path program 2 times [2024-11-09 22:47:38,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:38,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [27936406] [2024-11-09 22:47:38,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:38,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:38,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:47:38,891 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1487856452] [2024-11-09 22:47:38,891 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:47:38,891 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:38,891 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:38,892 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:38,893 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 22:47:38,945 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:47:38,945 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:47:38,947 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-09 22:47:38,949 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:39,269 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 50 proven. 56 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-09 22:47:39,269 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:42,388 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 50 proven. 56 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-09 22:47:42,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:42,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [27936406] [2024-11-09 22:47:42,388 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:47:42,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1487856452] [2024-11-09 22:47:42,388 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1487856452] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:47:42,388 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:47:42,388 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 27 [2024-11-09 22:47:42,388 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [361577157] [2024-11-09 22:47:42,388 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:47:42,389 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-09 22:47:42,389 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:42,390 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-09 22:47:42,390 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=547, Unknown=0, NotChecked=0, Total=702 [2024-11-09 22:47:42,390 INFO L87 Difference]: Start difference. First operand 185 states and 236 transitions. Second operand has 27 states, 25 states have (on average 2.36) internal successors, (59), 25 states have internal predecessors, (59), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-09 22:47:50,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:50,131 INFO L93 Difference]: Finished difference Result 263 states and 337 transitions. [2024-11-09 22:47:50,132 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-09 22:47:50,132 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 2.36) internal successors, (59), 25 states have internal predecessors, (59), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) Word has length 104 [2024-11-09 22:47:50,132 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:50,134 INFO L225 Difference]: With dead ends: 263 [2024-11-09 22:47:50,134 INFO L226 Difference]: Without dead ends: 189 [2024-11-09 22:47:50,135 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 213 GetRequests, 181 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 170 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=270, Invalid=852, Unknown=0, NotChecked=0, Total=1122 [2024-11-09 22:47:50,135 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 69 mSDsluCounter, 284 mSDsCounter, 0 mSdLazyCounter, 378 mSolverCounterSat, 110 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 324 SdHoareTripleChecker+Invalid, 488 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 110 IncrementalHoareTripleChecker+Valid, 378 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:50,136 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 324 Invalid, 488 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [110 Valid, 378 Invalid, 0 Unknown, 0 Unchecked, 2.3s Time] [2024-11-09 22:47:50,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-11-09 22:47:50,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 163. [2024-11-09 22:47:50,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 107 states have (on average 1.1121495327102804) internal successors, (119), 114 states have internal predecessors, (119), 40 states have call successors, (40), 15 states have call predecessors, (40), 15 states have return successors, (39), 33 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-09 22:47:50,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 198 transitions. [2024-11-09 22:47:50,182 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 198 transitions. Word has length 104 [2024-11-09 22:47:50,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:50,182 INFO L471 AbstractCegarLoop]: Abstraction has 163 states and 198 transitions. [2024-11-09 22:47:50,182 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 2.36) internal successors, (59), 25 states have internal predecessors, (59), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-09 22:47:50,182 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 198 transitions. [2024-11-09 22:47:50,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-09 22:47:50,184 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:50,184 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:50,197 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-09 22:47:50,384 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-09 22:47:50,384 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:50,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:50,385 INFO L85 PathProgramCache]: Analyzing trace with hash 107255838, now seen corresponding path program 2 times [2024-11-09 22:47:50,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:50,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1685283024] [2024-11-09 22:47:50,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:50,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:50,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,617 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:47:50,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,620 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:47:50,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,639 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:47:50,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,642 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:47:50,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,644 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:47:50,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,645 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-09 22:47:50,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,648 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-09 22:47:50,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,650 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-09 22:47:50,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,652 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-09 22:47:50,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,654 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-09 22:47:50,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,656 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-09 22:47:50,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,658 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 74 [2024-11-09 22:47:50,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,660 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 79 [2024-11-09 22:47:50,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,663 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-11-09 22:47:50,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,665 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-11-09 22:47:50,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,666 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-11-09 22:47:50,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:50,668 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-09 22:47:50,669 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:50,669 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1685283024] [2024-11-09 22:47:50,669 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1685283024] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:47:50,669 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1008067626] [2024-11-09 22:47:50,669 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:47:50,669 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:50,669 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:50,670 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:50,671 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-09 22:47:50,718 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:47:50,718 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:47:50,719 INFO L255 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-09 22:47:50,721 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:50,909 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-09 22:47:50,909 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:51,703 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-09 22:47:51,703 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1008067626] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:47:51,703 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:47:51,703 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 8] total 19 [2024-11-09 22:47:51,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1805535579] [2024-11-09 22:47:51,703 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:47:51,704 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 22:47:51,704 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:51,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 22:47:51,704 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-09 22:47:51,705 INFO L87 Difference]: Start difference. First operand 163 states and 198 transitions. Second operand has 19 states, 19 states have (on average 3.9473684210526314) internal successors, (75), 17 states have internal predecessors, (75), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) [2024-11-09 22:47:51,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:51,970 INFO L93 Difference]: Finished difference Result 189 states and 225 transitions. [2024-11-09 22:47:51,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 22:47:51,971 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.9473684210526314) internal successors, (75), 17 states have internal predecessors, (75), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) Word has length 109 [2024-11-09 22:47:51,971 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:51,972 INFO L225 Difference]: With dead ends: 189 [2024-11-09 22:47:51,972 INFO L226 Difference]: Without dead ends: 146 [2024-11-09 22:47:51,972 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 238 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=96, Invalid=366, Unknown=0, NotChecked=0, Total=462 [2024-11-09 22:47:51,972 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 12 mSDsluCounter, 339 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 383 SdHoareTripleChecker+Invalid, 277 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:51,973 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 383 Invalid, 277 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:47:51,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-09 22:47:52,005 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 146. [2024-11-09 22:47:52,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 96 states have (on average 1.1041666666666667) internal successors, (106), 101 states have internal predecessors, (106), 34 states have call successors, (34), 15 states have call predecessors, (34), 15 states have return successors, (32), 29 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-09 22:47:52,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 172 transitions. [2024-11-09 22:47:52,006 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 172 transitions. Word has length 109 [2024-11-09 22:47:52,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:52,006 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 172 transitions. [2024-11-09 22:47:52,006 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.9473684210526314) internal successors, (75), 17 states have internal predecessors, (75), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) [2024-11-09 22:47:52,006 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 172 transitions. [2024-11-09 22:47:52,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2024-11-09 22:47:52,007 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:52,007 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:52,020 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-09 22:47:52,208 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-09 22:47:52,208 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:52,208 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:52,208 INFO L85 PathProgramCache]: Analyzing trace with hash 443438552, now seen corresponding path program 1 times [2024-11-09 22:47:52,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:52,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [753313076] [2024-11-09 22:47:52,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:52,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:52,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,351 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:47:52,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,353 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:47:52,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,355 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:47:52,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,357 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:47:52,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,358 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:47:52,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,360 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-09 22:47:52,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-09 22:47:52,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,364 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-09 22:47:52,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,365 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-09 22:47:52,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,368 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-09 22:47:52,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,370 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-09 22:47:52,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,372 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-09 22:47:52,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,374 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-09 22:47:52,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,376 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-09 22:47:52,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-09 22:47:52,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,383 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-09 22:47:52,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,385 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 106 [2024-11-09 22:47:52,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,390 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 111 [2024-11-09 22:47:52,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,392 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 54 proven. 34 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-09 22:47:52,394 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:52,394 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [753313076] [2024-11-09 22:47:52,394 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [753313076] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:47:52,394 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [729287802] [2024-11-09 22:47:52,394 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:52,394 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:52,394 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:52,396 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:52,397 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-09 22:47:52,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:52,448 INFO L255 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:47:52,449 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:52,502 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 72 proven. 16 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-09 22:47:52,503 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:47:52,633 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 72 proven. 16 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-09 22:47:52,633 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [729287802] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:47:52,633 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:47:52,633 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 6] total 9 [2024-11-09 22:47:52,633 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1585587489] [2024-11-09 22:47:52,633 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:47:52,634 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-09 22:47:52,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:47:52,635 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-09 22:47:52,635 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:47:52,635 INFO L87 Difference]: Start difference. First operand 146 states and 172 transitions. Second operand has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2024-11-09 22:47:52,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:47:52,731 INFO L93 Difference]: Finished difference Result 153 states and 178 transitions. [2024-11-09 22:47:52,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-09 22:47:52,732 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 122 [2024-11-09 22:47:52,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:47:52,733 INFO L225 Difference]: With dead ends: 153 [2024-11-09 22:47:52,733 INFO L226 Difference]: Without dead ends: 145 [2024-11-09 22:47:52,734 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 273 SyntacticMatches, 6 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:47:52,734 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 9 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:47:52,734 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 157 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:47:52,735 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-09 22:47:52,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 140. [2024-11-09 22:47:52,764 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 93 states have (on average 1.096774193548387) internal successors, (102), 97 states have internal predecessors, (102), 31 states have call successors, (31), 15 states have call predecessors, (31), 15 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-09 22:47:52,765 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 163 transitions. [2024-11-09 22:47:52,766 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 163 transitions. Word has length 122 [2024-11-09 22:47:52,766 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:47:52,766 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 163 transitions. [2024-11-09 22:47:52,767 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2024-11-09 22:47:52,767 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 163 transitions. [2024-11-09 22:47:52,768 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 126 [2024-11-09 22:47:52,768 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:47:52,768 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:47:52,781 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-09 22:47:52,969 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-09 22:47:52,969 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:47:52,970 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:47:52,970 INFO L85 PathProgramCache]: Analyzing trace with hash -399076229, now seen corresponding path program 3 times [2024-11-09 22:47:52,970 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:47:52,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1809321145] [2024-11-09 22:47:52,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:47:52,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:47:52,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,375 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:47:53,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,379 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:47:53,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,383 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:47:53,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,385 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:47:53,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,387 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:47:53,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-09 22:47:53,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,394 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-09 22:47:53,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,396 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-09 22:47:53,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,399 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-09 22:47:53,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,402 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-09 22:47:53,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,404 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-09 22:47:53,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,407 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-09 22:47:53,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,409 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-09 22:47:53,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-09 22:47:53,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,415 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-09 22:47:53,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,417 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-09 22:47:53,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,420 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 106 [2024-11-09 22:47:53,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,423 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 111 [2024-11-09 22:47:53,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:47:53,427 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 45 proven. 54 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-09 22:47:53,427 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:47:53,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1809321145] [2024-11-09 22:47:53,427 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1809321145] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:47:53,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [872960998] [2024-11-09 22:47:53,427 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 22:47:53,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:47:53,427 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:47:53,429 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:47:53,430 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 22:47:53,487 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-09 22:47:53,488 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:47:53,489 INFO L255 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-09 22:47:53,490 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:47:53,684 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 159 proven. 47 refuted. 0 times theorem prover too weak. 505 trivial. 0 not checked. [2024-11-09 22:47:53,684 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:48:17,618 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 10 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 22:48:29,635 WARN L286 SmtUtils]: Spent 12.01s on a formula simplification that was a NOOP. DAG size: 5 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 22:48:37,643 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 5 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)