/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.use.bitabs.translation true -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-19 19:52:16,999 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-19 19:52:17,060 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2023-12-19 19:52:17,065 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-19 19:52:17,065 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-19 19:52:17,084 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-19 19:52:17,085 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-19 19:52:17,085 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-19 19:52:17,085 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-19 19:52:17,086 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-19 19:52:17,086 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-19 19:52:17,086 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-19 19:52:17,086 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-19 19:52:17,087 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-19 19:52:17,087 INFO L153 SettingsManager]: * Use SBE=true [2023-12-19 19:52:17,087 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-19 19:52:17,087 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-19 19:52:17,088 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-19 19:52:17,090 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-19 19:52:17,090 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-19 19:52:17,093 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-19 19:52:17,093 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-19 19:52:17,093 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-19 19:52:17,094 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-19 19:52:17,094 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-19 19:52:17,095 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-19 19:52:17,095 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-19 19:52:17,095 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-19 19:52:17,095 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-19 19:52:17,095 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-19 19:52:17,096 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-19 19:52:17,096 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-19 19:52:17,096 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-19 19:52:17,097 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-19 19:52:17,097 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-19 19:52:17,097 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-19 19:52:17,097 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-19 19:52:17,097 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-19 19:52:17,097 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-19 19:52:17,097 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-19 19:52:17,097 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-19 19:52:17,098 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-19 19:52:17,098 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-19 19:52:17,098 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: Use bitabs translation -> true [2023-12-19 19:52:17,269 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-19 19:52:17,292 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-19 19:52:17,293 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-19 19:52:17,294 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-19 19:52:17,294 INFO L274 PluginConnector]: CDTParser initialized [2023-12-19 19:52:17,295 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2023-12-19 19:52:18,359 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-19 19:52:18,528 INFO L384 CDTParser]: Found 1 translation units. [2023-12-19 19:52:18,529 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2023-12-19 19:52:18,535 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f10ddb610/4c9cf8ce1428481c893b46ade6e0b525/FLAGcf2dfa808 [2023-12-19 19:52:18,556 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f10ddb610/4c9cf8ce1428481c893b46ade6e0b525 [2023-12-19 19:52:18,558 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-19 19:52:18,559 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-19 19:52:18,562 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-19 19:52:18,562 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-19 19:52:18,565 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-19 19:52:18,565 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,566 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@64d57726 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18, skipping insertion in model container [2023-12-19 19:52:18,566 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,583 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-19 19:52:18,674 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2023-12-19 19:52:18,686 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-19 19:52:18,695 INFO L202 MainTranslator]: Completed pre-run [2023-12-19 19:52:18,702 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2023-12-19 19:52:18,709 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-19 19:52:18,717 INFO L206 MainTranslator]: Completed translation [2023-12-19 19:52:18,718 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18 WrapperNode [2023-12-19 19:52:18,718 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-19 19:52:18,718 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-19 19:52:18,718 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-19 19:52:18,719 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-19 19:52:18,723 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,726 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,738 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 86 [2023-12-19 19:52:18,738 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-19 19:52:18,738 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-19 19:52:18,739 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-19 19:52:18,739 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-19 19:52:18,745 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,745 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,746 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,754 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2023-12-19 19:52:18,754 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,754 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,757 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,759 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,759 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,760 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,761 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-19 19:52:18,761 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-19 19:52:18,761 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-19 19:52:18,761 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-19 19:52:18,762 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (1/1) ... [2023-12-19 19:52:18,765 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-19 19:52:18,774 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:18,809 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) [2023-12-19 19:52:18,814 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 [2023-12-19 19:52:18,834 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-19 19:52:18,835 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-12-19 19:52:18,835 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-12-19 19:52:18,835 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-19 19:52:18,835 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-19 19:52:18,835 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-19 19:52:18,835 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-19 19:52:18,835 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-19 19:52:18,913 INFO L241 CfgBuilder]: Building ICFG [2023-12-19 19:52:18,915 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-19 19:52:19,036 INFO L282 CfgBuilder]: Performing block encoding [2023-12-19 19:52:19,055 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-19 19:52:19,055 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-19 19:52:19,055 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 07:52:19 BoogieIcfgContainer [2023-12-19 19:52:19,055 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-19 19:52:19,056 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-19 19:52:19,056 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-19 19:52:19,058 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-19 19:52:19,058 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.12 07:52:18" (1/3) ... [2023-12-19 19:52:19,059 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@a73fe1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.12 07:52:19, skipping insertion in model container [2023-12-19 19:52:19,059 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:52:18" (2/3) ... [2023-12-19 19:52:19,059 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@a73fe1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.12 07:52:19, skipping insertion in model container [2023-12-19 19:52:19,059 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 07:52:19" (3/3) ... [2023-12-19 19:52:19,060 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.c [2023-12-19 19:52:19,071 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-19 19:52:19,071 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-19 19:52:19,097 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-19 19:52:19,101 INFO L357 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, mHoare=true, 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;@6626e77b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-19 19:52:19,101 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-19 19:52:19,104 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 19 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-12-19 19:52:19,108 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-19 19:52:19,108 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:19,109 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:19,109 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:19,112 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:19,112 INFO L85 PathProgramCache]: Analyzing trace with hash -689848145, now seen corresponding path program 1 times [2023-12-19 19:52:19,118 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:19,118 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2052108353] [2023-12-19 19:52:19,118 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:19,118 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:19,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:19,185 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:19,186 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2052108353] [2023-12-19 19:52:19,186 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-19 19:52:19,186 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [640254525] [2023-12-19 19:52:19,186 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:19,186 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:19,186 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:19,188 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) [2023-12-19 19:52:19,218 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-19 19:52:19,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:19,267 INFO L262 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-19 19:52:19,270 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:19,290 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-12-19 19:52:19,290 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-19 19:52:19,290 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [640254525] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-19 19:52:19,290 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-19 19:52:19,291 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-19 19:52:19,292 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2038259175] [2023-12-19 19:52:19,293 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 19:52:19,296 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-19 19:52:19,297 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:19,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-19 19:52:19,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-19 19:52:19,319 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 19 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 19:52:19,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:19,347 INFO L93 Difference]: Finished difference Result 60 states and 99 transitions. [2023-12-19 19:52:19,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-19 19:52:19,349 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2023-12-19 19:52:19,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:19,353 INFO L225 Difference]: With dead ends: 60 [2023-12-19 19:52:19,353 INFO L226 Difference]: Without dead ends: 29 [2023-12-19 19:52:19,355 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-19 19:52:19,357 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:19,359 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 40 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:19,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2023-12-19 19:52:19,379 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2023-12-19 19:52:19,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 16 states have (on average 1.3125) internal successors, (21), 18 states have internal predecessors, (21), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 19:52:19,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 40 transitions. [2023-12-19 19:52:19,382 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 40 transitions. Word has length 27 [2023-12-19 19:52:19,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:19,382 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 40 transitions. [2023-12-19 19:52:19,383 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 19:52:19,383 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 40 transitions. [2023-12-19 19:52:19,384 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-12-19 19:52:19,384 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:19,385 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:19,389 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:19,589 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-12-19 19:52:19,589 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:19,590 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:19,590 INFO L85 PathProgramCache]: Analyzing trace with hash -1989097615, now seen corresponding path program 1 times [2023-12-19 19:52:19,590 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:19,590 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1361177808] [2023-12-19 19:52:19,590 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:19,591 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:19,608 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:19,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2072836682] [2023-12-19 19:52:19,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:19,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:19,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:19,629 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) [2023-12-19 19:52:19,635 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-19 19:52:19,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:19,682 INFO L262 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-19 19:52:19,684 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:19,747 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-19 19:52:19,747 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-19 19:52:19,747 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:19,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1361177808] [2023-12-19 19:52:19,747 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:19,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2072836682] [2023-12-19 19:52:19,747 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2072836682] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-19 19:52:19,748 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-19 19:52:19,748 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-19 19:52:19,748 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [792763443] [2023-12-19 19:52:19,748 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 19:52:19,748 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-19 19:52:19,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:19,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-19 19:52:19,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-19 19:52:19,749 INFO L87 Difference]: Start difference. First operand 29 states and 40 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 19:52:19,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:19,761 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2023-12-19 19:52:19,761 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-19 19:52:19,761 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2023-12-19 19:52:19,762 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:19,762 INFO L225 Difference]: With dead ends: 39 [2023-12-19 19:52:19,762 INFO L226 Difference]: Without dead ends: 31 [2023-12-19 19:52:19,762 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-19 19:52:19,763 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:19,763 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 97 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:19,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-12-19 19:52:19,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2023-12-19 19:52:19,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 19 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 19:52:19,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 42 transitions. [2023-12-19 19:52:19,768 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 42 transitions. Word has length 28 [2023-12-19 19:52:19,769 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:19,769 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 42 transitions. [2023-12-19 19:52:19,769 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 19:52:19,769 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 42 transitions. [2023-12-19 19:52:19,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-12-19 19:52:19,770 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:19,770 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:19,776 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:19,974 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-12-19 19:52:19,974 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:19,976 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:19,976 INFO L85 PathProgramCache]: Analyzing trace with hash -1539070609, now seen corresponding path program 1 times [2023-12-19 19:52:19,976 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:19,977 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [942073548] [2023-12-19 19:52:19,977 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:19,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:20,002 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:20,002 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [439593262] [2023-12-19 19:52:20,002 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:20,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:20,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:20,008 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) [2023-12-19 19:52:20,009 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-19 19:52:20,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:20,062 INFO L262 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-19 19:52:20,064 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:20,091 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 19:52:20,091 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:20,154 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 19:52:20,155 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:20,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [942073548] [2023-12-19 19:52:20,155 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:20,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [439593262] [2023-12-19 19:52:20,155 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [439593262] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 19:52:20,155 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 19:52:20,155 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2023-12-19 19:52:20,155 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1781584211] [2023-12-19 19:52:20,155 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:20,156 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-19 19:52:20,156 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:20,157 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-19 19:52:20,158 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2023-12-19 19:52:20,158 INFO L87 Difference]: Start difference. First operand 31 states and 42 transitions. Second operand has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 19:52:20,237 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:20,238 INFO L93 Difference]: Finished difference Result 48 states and 66 transitions. [2023-12-19 19:52:20,238 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 19:52:20,238 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2023-12-19 19:52:20,239 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:20,241 INFO L225 Difference]: With dead ends: 48 [2023-12-19 19:52:20,241 INFO L226 Difference]: Without dead ends: 40 [2023-12-19 19:52:20,241 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 49 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2023-12-19 19:52:20,243 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 29 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:20,244 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 97 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:20,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2023-12-19 19:52:20,249 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 32. [2023-12-19 19:52:20,249 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 19:52:20,250 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2023-12-19 19:52:20,250 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2023-12-19 19:52:20,250 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:20,250 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2023-12-19 19:52:20,250 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-19 19:52:20,250 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2023-12-19 19:52:20,251 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2023-12-19 19:52:20,251 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:20,251 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:20,256 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-19 19:52:20,451 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:20,453 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:20,454 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:20,454 INFO L85 PathProgramCache]: Analyzing trace with hash -1634889762, now seen corresponding path program 1 times [2023-12-19 19:52:20,454 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:20,454 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1376995747] [2023-12-19 19:52:20,454 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:20,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:20,462 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:20,463 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [60033450] [2023-12-19 19:52:20,463 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:20,463 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:20,463 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:20,464 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) [2023-12-19 19:52:20,492 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-19 19:52:20,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:20,499 INFO L262 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-19 19:52:20,500 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:20,573 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 19:52:20,574 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:20,636 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-19 19:52:20,637 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:20,637 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1376995747] [2023-12-19 19:52:20,637 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:20,637 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [60033450] [2023-12-19 19:52:20,637 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [60033450] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-19 19:52:20,637 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-19 19:52:20,637 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 12 [2023-12-19 19:52:20,637 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [881430676] [2023-12-19 19:52:20,637 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 19:52:20,638 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 19:52:20,638 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:20,639 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 19:52:20,640 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2023-12-19 19:52:20,640 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 19:52:20,683 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:20,683 INFO L93 Difference]: Finished difference Result 38 states and 48 transitions. [2023-12-19 19:52:20,683 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 19:52:20,684 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), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 31 [2023-12-19 19:52:20,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:20,685 INFO L225 Difference]: With dead ends: 38 [2023-12-19 19:52:20,685 INFO L226 Difference]: Without dead ends: 36 [2023-12-19 19:52:20,686 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-12-19 19:52:20,688 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:20,688 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 116 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:20,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2023-12-19 19:52:20,698 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2023-12-19 19:52:20,698 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 23 states have internal predecessors, (27), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 19:52:20,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 46 transitions. [2023-12-19 19:52:20,701 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 46 transitions. Word has length 31 [2023-12-19 19:52:20,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:20,701 INFO L495 AbstractCegarLoop]: Abstraction has 36 states and 46 transitions. [2023-12-19 19:52:20,701 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 19:52:20,701 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 46 transitions. [2023-12-19 19:52:20,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-12-19 19:52:20,703 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:20,703 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:20,708 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:20,908 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:20,908 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:20,909 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:20,909 INFO L85 PathProgramCache]: Analyzing trace with hash 753217482, now seen corresponding path program 1 times [2023-12-19 19:52:20,909 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:20,909 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1553193164] [2023-12-19 19:52:20,909 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:20,909 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:20,916 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:20,917 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1099788036] [2023-12-19 19:52:20,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:20,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:20,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:20,919 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) [2023-12-19 19:52:20,933 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-19 19:52:20,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:20,968 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-19 19:52:20,969 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:21,001 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-19 19:52:21,001 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-19 19:52:21,002 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:21,002 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1553193164] [2023-12-19 19:52:21,002 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:21,002 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1099788036] [2023-12-19 19:52:21,002 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1099788036] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-19 19:52:21,002 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-19 19:52:21,002 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-19 19:52:21,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1889969520] [2023-12-19 19:52:21,002 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 19:52:21,002 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 19:52:21,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:21,003 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 19:52:21,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-19 19:52:21,003 INFO L87 Difference]: Start difference. First operand 36 states and 46 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 19:52:21,020 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:21,021 INFO L93 Difference]: Finished difference Result 61 states and 79 transitions. [2023-12-19 19:52:21,021 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-19 19:52:21,022 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), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 34 [2023-12-19 19:52:21,022 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:21,022 INFO L225 Difference]: With dead ends: 61 [2023-12-19 19:52:21,022 INFO L226 Difference]: Without dead ends: 38 [2023-12-19 19:52:21,023 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-19 19:52:21,023 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 0 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:21,023 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 119 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:21,023 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2023-12-19 19:52:21,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2023-12-19 19:52:21,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 25 states have internal predecessors, (29), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-19 19:52:21,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 48 transitions. [2023-12-19 19:52:21,028 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 48 transitions. Word has length 34 [2023-12-19 19:52:21,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:21,028 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 48 transitions. [2023-12-19 19:52:21,028 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-19 19:52:21,028 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 48 transitions. [2023-12-19 19:52:21,028 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-12-19 19:52:21,028 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:21,028 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:21,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:21,254 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:21,255 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:21,255 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:21,255 INFO L85 PathProgramCache]: Analyzing trace with hash 120049922, now seen corresponding path program 1 times [2023-12-19 19:52:21,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:21,255 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [485885211] [2023-12-19 19:52:21,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:21,256 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:21,262 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:21,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [332245964] [2023-12-19 19:52:21,263 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:21,263 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:21,263 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:21,267 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) [2023-12-19 19:52:21,268 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-19 19:52:21,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:21,325 INFO L262 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-19 19:52:21,326 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:21,476 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-12-19 19:52:21,476 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:21,539 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-19 19:52:21,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:21,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [485885211] [2023-12-19 19:52:21,539 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:21,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [332245964] [2023-12-19 19:52:21,540 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [332245964] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-19 19:52:21,540 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-19 19:52:21,540 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [11] total 13 [2023-12-19 19:52:21,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [929579867] [2023-12-19 19:52:21,540 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 19:52:21,540 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 19:52:21,540 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:21,541 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 19:52:21,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-12-19 19:52:21,541 INFO L87 Difference]: Start difference. First operand 38 states and 48 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-19 19:52:21,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:21,570 INFO L93 Difference]: Finished difference Result 52 states and 67 transitions. [2023-12-19 19:52:21,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 19:52:21,571 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), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2023-12-19 19:52:21,571 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:21,571 INFO L225 Difference]: With dead ends: 52 [2023-12-19 19:52:21,571 INFO L226 Difference]: Without dead ends: 50 [2023-12-19 19:52:21,572 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 59 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2023-12-19 19:52:21,572 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 7 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:21,572 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 133 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:21,573 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2023-12-19 19:52:21,578 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 49. [2023-12-19 19:52:21,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 31 states have internal predecessors, (37), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-19 19:52:21,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 64 transitions. [2023-12-19 19:52:21,578 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 64 transitions. Word has length 36 [2023-12-19 19:52:21,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:21,578 INFO L495 AbstractCegarLoop]: Abstraction has 49 states and 64 transitions. [2023-12-19 19:52:21,579 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-19 19:52:21,579 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 64 transitions. [2023-12-19 19:52:21,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2023-12-19 19:52:21,579 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:21,579 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:21,593 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:21,784 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:21,784 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:21,784 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:21,784 INFO L85 PathProgramCache]: Analyzing trace with hash 391757342, now seen corresponding path program 1 times [2023-12-19 19:52:21,784 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:21,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1859747377] [2023-12-19 19:52:21,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:21,785 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:21,791 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:21,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [622809087] [2023-12-19 19:52:21,791 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:21,791 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:21,791 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:21,810 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) [2023-12-19 19:52:21,837 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-19 19:52:21,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:21,848 INFO L262 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 23 conjunts are in the unsatisfiable core [2023-12-19 19:52:21,849 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:21,971 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-12-19 19:52:21,971 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:22,028 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-12-19 19:52:22,029 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:22,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1859747377] [2023-12-19 19:52:22,029 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:22,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [622809087] [2023-12-19 19:52:22,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [622809087] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-19 19:52:22,029 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-19 19:52:22,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [11] total 13 [2023-12-19 19:52:22,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [392322463] [2023-12-19 19:52:22,029 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 19:52:22,030 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 19:52:22,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:22,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 19:52:22,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-12-19 19:52:22,030 INFO L87 Difference]: Start difference. First operand 49 states and 64 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-19 19:52:22,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:22,063 INFO L93 Difference]: Finished difference Result 56 states and 70 transitions. [2023-12-19 19:52:22,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 19:52:22,063 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), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 41 [2023-12-19 19:52:22,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:22,064 INFO L225 Difference]: With dead ends: 56 [2023-12-19 19:52:22,064 INFO L226 Difference]: Without dead ends: 54 [2023-12-19 19:52:22,064 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2023-12-19 19:52:22,064 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:22,065 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 124 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:22,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2023-12-19 19:52:22,071 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2023-12-19 19:52:22,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 33 states have (on average 1.2121212121212122) internal successors, (40), 34 states have internal predecessors, (40), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-19 19:52:22,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 67 transitions. [2023-12-19 19:52:22,071 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 67 transitions. Word has length 41 [2023-12-19 19:52:22,072 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:22,072 INFO L495 AbstractCegarLoop]: Abstraction has 53 states and 67 transitions. [2023-12-19 19:52:22,072 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-19 19:52:22,072 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 67 transitions. [2023-12-19 19:52:22,072 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-12-19 19:52:22,072 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:22,072 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:22,092 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-19 19:52:22,277 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:22,277 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:22,277 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:22,277 INFO L85 PathProgramCache]: Analyzing trace with hash 439925314, now seen corresponding path program 1 times [2023-12-19 19:52:22,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:22,278 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [605081998] [2023-12-19 19:52:22,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:22,278 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:22,294 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:22,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [146548326] [2023-12-19 19:52:22,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:22,295 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:22,295 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:22,296 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) [2023-12-19 19:52:22,298 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-19 19:52:22,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:22,336 INFO L262 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 19 conjunts are in the unsatisfiable core [2023-12-19 19:52:22,341 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:22,445 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-12-19 19:52:22,446 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:22,810 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:22,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [605081998] [2023-12-19 19:52:22,810 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:22,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [146548326] [2023-12-19 19:52:22,810 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [146548326] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 19:52:22,810 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 19:52:22,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2023-12-19 19:52:22,810 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1354035458] [2023-12-19 19:52:22,810 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:22,810 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-19 19:52:22,810 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:22,811 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-19 19:52:22,811 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=68, Unknown=1, NotChecked=0, Total=90 [2023-12-19 19:52:22,811 INFO L87 Difference]: Start difference. First operand 53 states and 67 transitions. Second operand has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-12-19 19:52:22,881 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:22,881 INFO L93 Difference]: Finished difference Result 60 states and 73 transitions. [2023-12-19 19:52:22,881 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-19 19:52:22,881 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 46 [2023-12-19 19:52:22,881 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:22,882 INFO L225 Difference]: With dead ends: 60 [2023-12-19 19:52:22,882 INFO L226 Difference]: Without dead ends: 58 [2023-12-19 19:52:22,882 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=34, Invalid=97, Unknown=1, NotChecked=0, Total=132 [2023-12-19 19:52:22,882 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 13 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:22,883 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 121 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 19:52:22,883 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2023-12-19 19:52:22,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2023-12-19 19:52:22,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 37 states have internal predecessors, (43), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-19 19:52:22,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 70 transitions. [2023-12-19 19:52:22,890 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 70 transitions. Word has length 46 [2023-12-19 19:52:22,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:22,890 INFO L495 AbstractCegarLoop]: Abstraction has 57 states and 70 transitions. [2023-12-19 19:52:22,890 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-12-19 19:52:22,890 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 70 transitions. [2023-12-19 19:52:22,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2023-12-19 19:52:22,891 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:22,891 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 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, 1, 1] [2023-12-19 19:52:22,909 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:23,095 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-12-19 19:52:23,096 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:23,096 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:23,096 INFO L85 PathProgramCache]: Analyzing trace with hash -1428774585, now seen corresponding path program 1 times [2023-12-19 19:52:23,096 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:23,096 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [716894442] [2023-12-19 19:52:23,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:23,097 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:23,103 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:23,103 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1781544212] [2023-12-19 19:52:23,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:23,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:23,103 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:23,104 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) [2023-12-19 19:52:23,128 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-19 19:52:23,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:23,181 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-19 19:52:23,184 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:23,245 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-12-19 19:52:23,245 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:23,297 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-12-19 19:52:23,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:23,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [716894442] [2023-12-19 19:52:23,297 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:23,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1781544212] [2023-12-19 19:52:23,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1781544212] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 19:52:23,298 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 19:52:23,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2023-12-19 19:52:23,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1292860990] [2023-12-19 19:52:23,298 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:23,298 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-19 19:52:23,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:23,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-19 19:52:23,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2023-12-19 19:52:23,299 INFO L87 Difference]: Start difference. First operand 57 states and 70 transitions. Second operand has 9 states, 9 states have (on average 4.111111111111111) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2023-12-19 19:52:23,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:23,386 INFO L93 Difference]: Finished difference Result 168 states and 197 transitions. [2023-12-19 19:52:23,386 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-19 19:52:23,386 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.111111111111111) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 55 [2023-12-19 19:52:23,387 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:23,388 INFO L225 Difference]: With dead ends: 168 [2023-12-19 19:52:23,388 INFO L226 Difference]: Without dead ends: 160 [2023-12-19 19:52:23,388 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=47, Invalid=85, Unknown=0, NotChecked=0, Total=132 [2023-12-19 19:52:23,389 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 49 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:23,389 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 133 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 19:52:23,389 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2023-12-19 19:52:23,405 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 154. [2023-12-19 19:52:23,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 99 states have (on average 1.1818181818181819) internal successors, (117), 102 states have internal predecessors, (117), 34 states have call successors, (34), 20 states have call predecessors, (34), 20 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2023-12-19 19:52:23,406 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 182 transitions. [2023-12-19 19:52:23,406 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 182 transitions. Word has length 55 [2023-12-19 19:52:23,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:23,406 INFO L495 AbstractCegarLoop]: Abstraction has 154 states and 182 transitions. [2023-12-19 19:52:23,406 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.111111111111111) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2023-12-19 19:52:23,406 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 182 transitions. [2023-12-19 19:52:23,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-12-19 19:52:23,407 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:23,407 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 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, 1] [2023-12-19 19:52:23,425 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:23,612 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:23,612 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:23,613 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:23,613 INFO L85 PathProgramCache]: Analyzing trace with hash -1348925863, now seen corresponding path program 1 times [2023-12-19 19:52:23,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:23,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680757327] [2023-12-19 19:52:23,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:23,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:23,619 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:23,619 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [8258491] [2023-12-19 19:52:23,619 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:23,619 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:23,619 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:23,636 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) [2023-12-19 19:52:23,695 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-19 19:52:23,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:23,731 INFO L262 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjunts are in the unsatisfiable core [2023-12-19 19:52:23,732 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:23,782 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-12-19 19:52:23,782 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:23,840 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-12-19 19:52:23,840 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:23,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680757327] [2023-12-19 19:52:23,840 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:23,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [8258491] [2023-12-19 19:52:23,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [8258491] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 19:52:23,841 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 19:52:23,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2023-12-19 19:52:23,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [843246042] [2023-12-19 19:52:23,841 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:23,842 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-19 19:52:23,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:23,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-19 19:52:23,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2023-12-19 19:52:23,842 INFO L87 Difference]: Start difference. First operand 154 states and 182 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-12-19 19:52:23,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:23,973 INFO L93 Difference]: Finished difference Result 220 states and 287 transitions. [2023-12-19 19:52:23,974 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-19 19:52:23,974 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 56 [2023-12-19 19:52:23,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:23,975 INFO L225 Difference]: With dead ends: 220 [2023-12-19 19:52:23,975 INFO L226 Difference]: Without dead ends: 206 [2023-12-19 19:52:23,976 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 99 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2023-12-19 19:52:23,977 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 69 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 323 SdHoareTripleChecker+Invalid, 147 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:23,977 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 323 Invalid, 147 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 19:52:23,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2023-12-19 19:52:24,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 184. [2023-12-19 19:52:24,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 120 states have (on average 1.2166666666666666) internal successors, (146), 122 states have internal predecessors, (146), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2023-12-19 19:52:24,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 232 transitions. [2023-12-19 19:52:24,006 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 232 transitions. Word has length 56 [2023-12-19 19:52:24,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:24,006 INFO L495 AbstractCegarLoop]: Abstraction has 184 states and 232 transitions. [2023-12-19 19:52:24,006 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-12-19 19:52:24,006 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 232 transitions. [2023-12-19 19:52:24,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2023-12-19 19:52:24,009 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:24,009 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 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, 1] [2023-12-19 19:52:24,015 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:24,213 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-19 19:52:24,214 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:24,214 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:24,215 INFO L85 PathProgramCache]: Analyzing trace with hash -848672706, now seen corresponding path program 1 times [2023-12-19 19:52:24,215 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:24,215 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [641340162] [2023-12-19 19:52:24,215 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:24,215 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:24,232 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:24,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [125263683] [2023-12-19 19:52:24,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:24,233 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:24,233 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:24,235 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) [2023-12-19 19:52:24,263 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-19 19:52:24,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:24,277 INFO L262 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-19 19:52:24,280 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:24,329 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-12-19 19:52:24,329 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:24,371 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-12-19 19:52:24,371 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:24,371 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [641340162] [2023-12-19 19:52:24,371 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:24,371 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [125263683] [2023-12-19 19:52:24,372 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [125263683] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 19:52:24,372 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 19:52:24,372 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2023-12-19 19:52:24,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1275285519] [2023-12-19 19:52:24,372 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:24,372 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-19 19:52:24,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:24,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-19 19:52:24,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2023-12-19 19:52:24,374 INFO L87 Difference]: Start difference. First operand 184 states and 232 transitions. Second operand has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2023-12-19 19:52:24,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:24,453 INFO L93 Difference]: Finished difference Result 264 states and 345 transitions. [2023-12-19 19:52:24,453 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-19 19:52:24,453 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 58 [2023-12-19 19:52:24,454 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:24,456 INFO L225 Difference]: With dead ends: 264 [2023-12-19 19:52:24,456 INFO L226 Difference]: Without dead ends: 192 [2023-12-19 19:52:24,459 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 106 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2023-12-19 19:52:24,459 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 36 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:24,459 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 126 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:24,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2023-12-19 19:52:24,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 190. [2023-12-19 19:52:24,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 126 states have (on average 1.1825396825396826) internal successors, (149), 128 states have internal predecessors, (149), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2023-12-19 19:52:24,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 235 transitions. [2023-12-19 19:52:24,480 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 235 transitions. Word has length 58 [2023-12-19 19:52:24,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:24,481 INFO L495 AbstractCegarLoop]: Abstraction has 190 states and 235 transitions. [2023-12-19 19:52:24,481 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2023-12-19 19:52:24,481 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 235 transitions. [2023-12-19 19:52:24,482 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2023-12-19 19:52:24,482 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:24,482 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:24,488 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:24,686 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-12-19 19:52:24,686 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:24,687 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:24,687 INFO L85 PathProgramCache]: Analyzing trace with hash -421956392, now seen corresponding path program 1 times [2023-12-19 19:52:24,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:24,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1360561776] [2023-12-19 19:52:24,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:24,687 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:24,699 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:24,699 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [653678285] [2023-12-19 19:52:24,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:24,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:24,699 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:24,700 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:52:24,728 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-19 19:52:24,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:24,743 INFO L262 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 26 conjunts are in the unsatisfiable core [2023-12-19 19:52:24,745 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:24,810 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 23 proven. 12 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2023-12-19 19:52:24,811 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:24,896 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2023-12-19 19:52:24,896 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:24,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1360561776] [2023-12-19 19:52:24,896 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:24,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [653678285] [2023-12-19 19:52:24,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [653678285] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 19:52:24,896 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 19:52:24,896 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2023-12-19 19:52:24,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [77849586] [2023-12-19 19:52:24,896 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:24,897 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-19 19:52:24,897 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:24,897 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-19 19:52:24,897 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2023-12-19 19:52:24,897 INFO L87 Difference]: Start difference. First operand 190 states and 235 transitions. Second operand has 13 states, 13 states have (on average 3.3076923076923075) internal successors, (43), 12 states have internal predecessors, (43), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-12-19 19:52:25,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:25,069 INFO L93 Difference]: Finished difference Result 267 states and 353 transitions. [2023-12-19 19:52:25,069 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-19 19:52:25,069 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.3076923076923075) internal successors, (43), 12 states have internal predecessors, (43), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 63 [2023-12-19 19:52:25,069 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:25,071 INFO L225 Difference]: With dead ends: 267 [2023-12-19 19:52:25,071 INFO L226 Difference]: Without dead ends: 262 [2023-12-19 19:52:25,071 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=243, Unknown=0, NotChecked=0, Total=306 [2023-12-19 19:52:25,072 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 50 mSDsluCounter, 296 mSDsCounter, 0 mSdLazyCounter, 221 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 343 SdHoareTripleChecker+Invalid, 261 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 221 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:25,072 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 343 Invalid, 261 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 221 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 19:52:25,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 262 states. [2023-12-19 19:52:25,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 262 to 232. [2023-12-19 19:52:25,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 232 states, 154 states have (on average 1.2142857142857142) internal successors, (187), 162 states have internal predecessors, (187), 56 states have call successors, (56), 21 states have call predecessors, (56), 21 states have return successors, (53), 48 states have call predecessors, (53), 53 states have call successors, (53) [2023-12-19 19:52:25,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 232 states to 232 states and 296 transitions. [2023-12-19 19:52:25,127 INFO L78 Accepts]: Start accepts. Automaton has 232 states and 296 transitions. Word has length 63 [2023-12-19 19:52:25,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:25,127 INFO L495 AbstractCegarLoop]: Abstraction has 232 states and 296 transitions. [2023-12-19 19:52:25,127 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.3076923076923075) internal successors, (43), 12 states have internal predecessors, (43), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-12-19 19:52:25,127 INFO L276 IsEmpty]: Start isEmpty. Operand 232 states and 296 transitions. [2023-12-19 19:52:25,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2023-12-19 19:52:25,128 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:25,128 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 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, 1, 1] [2023-12-19 19:52:25,142 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:25,332 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-12-19 19:52:25,333 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:25,333 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:25,333 INFO L85 PathProgramCache]: Analyzing trace with hash -245166072, now seen corresponding path program 2 times [2023-12-19 19:52:25,333 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:25,333 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2016441375] [2023-12-19 19:52:25,333 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:25,333 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:25,346 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:25,347 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [778966779] [2023-12-19 19:52:25,347 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-19 19:52:25,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:25,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:25,348 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:52:25,375 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-19 19:52:25,393 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-19 19:52:25,393 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 19:52:25,394 INFO L262 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 40 conjunts are in the unsatisfiable core [2023-12-19 19:52:25,395 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:25,708 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 26 proven. 21 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2023-12-19 19:52:25,708 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:25,784 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:25,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2016441375] [2023-12-19 19:52:25,784 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:25,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [778966779] [2023-12-19 19:52:25,785 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [778966779] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 19:52:25,785 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 19:52:25,785 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-12-19 19:52:25,785 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2014804809] [2023-12-19 19:52:25,785 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:25,785 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-19 19:52:25,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:25,786 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-19 19:52:25,786 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=225, Unknown=0, NotChecked=0, Total=272 [2023-12-19 19:52:25,786 INFO L87 Difference]: Start difference. First operand 232 states and 296 transitions. Second operand has 14 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-19 19:52:25,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:25,997 INFO L93 Difference]: Finished difference Result 251 states and 319 transitions. [2023-12-19 19:52:25,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-19 19:52:25,997 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 68 [2023-12-19 19:52:25,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:25,998 INFO L225 Difference]: With dead ends: 251 [2023-12-19 19:52:25,998 INFO L226 Difference]: Without dead ends: 249 [2023-12-19 19:52:25,999 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=72, Invalid=348, Unknown=0, NotChecked=0, Total=420 [2023-12-19 19:52:25,999 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 85 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 239 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 96 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 275 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 239 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:25,999 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [96 Valid, 198 Invalid, 275 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 239 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-19 19:52:26,000 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 249 states. [2023-12-19 19:52:26,022 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 249 to 247. [2023-12-19 19:52:26,023 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 247 states, 163 states have (on average 1.2147239263803682) internal successors, (198), 171 states have internal predecessors, (198), 60 states have call successors, (60), 23 states have call predecessors, (60), 23 states have return successors, (57), 52 states have call predecessors, (57), 57 states have call successors, (57) [2023-12-19 19:52:26,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 247 states to 247 states and 315 transitions. [2023-12-19 19:52:26,024 INFO L78 Accepts]: Start accepts. Automaton has 247 states and 315 transitions. Word has length 68 [2023-12-19 19:52:26,024 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:26,024 INFO L495 AbstractCegarLoop]: Abstraction has 247 states and 315 transitions. [2023-12-19 19:52:26,024 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 5 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-19 19:52:26,024 INFO L276 IsEmpty]: Start isEmpty. Operand 247 states and 315 transitions. [2023-12-19 19:52:26,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-12-19 19:52:26,025 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:26,025 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 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] [2023-12-19 19:52:26,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:26,229 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-12-19 19:52:26,229 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:26,230 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:26,230 INFO L85 PathProgramCache]: Analyzing trace with hash -441972072, now seen corresponding path program 3 times [2023-12-19 19:52:26,230 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:26,230 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1604415948] [2023-12-19 19:52:26,230 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:26,230 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:26,241 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:26,241 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [401044576] [2023-12-19 19:52:26,241 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-19 19:52:26,241 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:26,241 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:26,242 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:52:26,272 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-12-19 19:52:26,289 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-19 19:52:26,289 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-19 19:52:26,290 INFO L262 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 49 conjunts are in the unsatisfiable core [2023-12-19 19:52:26,291 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:26,791 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 37 proven. 16 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2023-12-19 19:52:26,792 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:27,352 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:27,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1604415948] [2023-12-19 19:52:27,352 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:27,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [401044576] [2023-12-19 19:52:27,352 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [401044576] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-19 19:52:27,352 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-19 19:52:27,352 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2023-12-19 19:52:27,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1902041854] [2023-12-19 19:52:27,352 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:27,353 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-19 19:52:27,353 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:27,353 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-19 19:52:27,353 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=357, Unknown=0, NotChecked=0, Total=420 [2023-12-19 19:52:27,353 INFO L87 Difference]: Start difference. First operand 247 states and 315 transitions. Second operand has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2023-12-19 19:52:28,238 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:28,238 INFO L93 Difference]: Finished difference Result 259 states and 326 transitions. [2023-12-19 19:52:28,239 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-12-19 19:52:28,239 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) Word has length 73 [2023-12-19 19:52:28,239 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:28,240 INFO L225 Difference]: With dead ends: 259 [2023-12-19 19:52:28,241 INFO L226 Difference]: Without dead ends: 255 [2023-12-19 19:52:28,241 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 127 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=100, Invalid=550, Unknown=0, NotChecked=0, Total=650 [2023-12-19 19:52:28,241 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 50 mSDsluCounter, 230 mSDsCounter, 0 mSdLazyCounter, 302 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 261 SdHoareTripleChecker+Invalid, 315 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 302 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:28,241 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 261 Invalid, 315 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 302 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-12-19 19:52:28,242 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 255 states. [2023-12-19 19:52:28,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 255 to 253. [2023-12-19 19:52:28,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 168 states have (on average 1.2023809523809523) internal successors, (202), 175 states have internal predecessors, (202), 60 states have call successors, (60), 25 states have call predecessors, (60), 24 states have return successors, (57), 52 states have call predecessors, (57), 57 states have call successors, (57) [2023-12-19 19:52:28,274 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 319 transitions. [2023-12-19 19:52:28,274 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 319 transitions. Word has length 73 [2023-12-19 19:52:28,274 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:28,275 INFO L495 AbstractCegarLoop]: Abstraction has 253 states and 319 transitions. [2023-12-19 19:52:28,275 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2023-12-19 19:52:28,275 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 319 transitions. [2023-12-19 19:52:28,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2023-12-19 19:52:28,277 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:28,277 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 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, 1, 1, 1] [2023-12-19 19:52:28,284 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:28,482 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:28,482 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:28,482 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:28,482 INFO L85 PathProgramCache]: Analyzing trace with hash 2054740817, now seen corresponding path program 1 times [2023-12-19 19:52:28,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:28,482 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542935468] [2023-12-19 19:52:28,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:28,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:28,496 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:28,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1243102021] [2023-12-19 19:52:28,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:28,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:28,497 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:28,514 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:52:28,532 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-12-19 19:52:28,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:28,561 INFO L262 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjunts are in the unsatisfiable core [2023-12-19 19:52:28,563 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:28,992 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2023-12-19 19:52:28,992 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:29,479 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2023-12-19 19:52:29,479 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:29,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542935468] [2023-12-19 19:52:29,479 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:29,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1243102021] [2023-12-19 19:52:29,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1243102021] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 19:52:29,480 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 19:52:29,480 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2023-12-19 19:52:29,480 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [529040246] [2023-12-19 19:52:29,480 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:29,480 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-19 19:52:29,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:29,481 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-19 19:52:29,481 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2023-12-19 19:52:29,481 INFO L87 Difference]: Start difference. First operand 253 states and 319 transitions. Second operand has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-12-19 19:52:35,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:35,694 INFO L93 Difference]: Finished difference Result 399 states and 553 transitions. [2023-12-19 19:52:35,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2023-12-19 19:52:35,701 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 79 [2023-12-19 19:52:35,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:35,702 INFO L225 Difference]: With dead ends: 399 [2023-12-19 19:52:35,702 INFO L226 Difference]: Without dead ends: 393 [2023-12-19 19:52:35,704 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 137 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 394 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=375, Invalid=1605, Unknown=0, NotChecked=0, Total=1980 [2023-12-19 19:52:35,704 INFO L413 NwaCegarLoop]: 57 mSDtfsCounter, 150 mSDsluCounter, 568 mSDsCounter, 0 mSdLazyCounter, 489 mSolverCounterSat, 129 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 154 SdHoareTripleChecker+Valid, 625 SdHoareTripleChecker+Invalid, 618 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 129 IncrementalHoareTripleChecker+Valid, 489 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:35,705 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [154 Valid, 625 Invalid, 618 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [129 Valid, 489 Invalid, 0 Unknown, 0 Unchecked, 2.4s Time] [2023-12-19 19:52:35,705 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 393 states. [2023-12-19 19:52:35,778 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 393 to 358. [2023-12-19 19:52:35,779 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 358 states, 228 states have (on average 1.2763157894736843) internal successors, (291), 237 states have internal predecessors, (291), 103 states have call successors, (103), 26 states have call predecessors, (103), 26 states have return successors, (101), 94 states have call predecessors, (101), 101 states have call successors, (101) [2023-12-19 19:52:35,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 358 states to 358 states and 495 transitions. [2023-12-19 19:52:35,780 INFO L78 Accepts]: Start accepts. Automaton has 358 states and 495 transitions. Word has length 79 [2023-12-19 19:52:35,780 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:35,780 INFO L495 AbstractCegarLoop]: Abstraction has 358 states and 495 transitions. [2023-12-19 19:52:35,781 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-12-19 19:52:35,781 INFO L276 IsEmpty]: Start isEmpty. Operand 358 states and 495 transitions. [2023-12-19 19:52:35,781 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2023-12-19 19:52:35,781 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:35,781 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 3, 3, 3, 3, 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] [2023-12-19 19:52:35,791 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2023-12-19 19:52:35,986 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-12-19 19:52:35,986 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:35,987 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:35,987 INFO L85 PathProgramCache]: Analyzing trace with hash -1270806006, now seen corresponding path program 1 times [2023-12-19 19:52:35,987 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:35,987 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1898826022] [2023-12-19 19:52:35,987 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:35,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:35,998 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:35,998 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1400516767] [2023-12-19 19:52:35,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:35,998 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:35,998 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:36,004 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:52:36,006 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-12-19 19:52:36,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:36,082 INFO L262 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-19 19:52:36,084 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:36,104 INFO L134 CoverageAnalysis]: Checked inductivity of 181 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2023-12-19 19:52:36,104 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-19 19:52:36,104 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:36,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1898826022] [2023-12-19 19:52:36,104 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:36,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1400516767] [2023-12-19 19:52:36,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1400516767] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-19 19:52:36,104 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-19 19:52:36,104 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-19 19:52:36,105 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1468592361] [2023-12-19 19:52:36,105 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-19 19:52:36,105 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-19 19:52:36,105 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:36,105 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-19 19:52:36,106 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-19 19:52:36,106 INFO L87 Difference]: Start difference. First operand 358 states and 495 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-12-19 19:52:36,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:52:36,201 INFO L93 Difference]: Finished difference Result 571 states and 838 transitions. [2023-12-19 19:52:36,201 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-19 19:52:36,202 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 88 [2023-12-19 19:52:36,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:52:36,205 INFO L225 Difference]: With dead ends: 571 [2023-12-19 19:52:36,205 INFO L226 Difference]: Without dead ends: 402 [2023-12-19 19:52:36,205 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-12-19 19:52:36,206 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 12 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:52:36,206 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 171 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-19 19:52:36,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 402 states. [2023-12-19 19:52:36,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 402 to 359. [2023-12-19 19:52:36,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 359 states, 227 states have (on average 1.2687224669603525) internal successors, (288), 233 states have internal predecessors, (288), 105 states have call successors, (105), 26 states have call predecessors, (105), 26 states have return successors, (103), 99 states have call predecessors, (103), 103 states have call successors, (103) [2023-12-19 19:52:36,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 359 states to 359 states and 496 transitions. [2023-12-19 19:52:36,281 INFO L78 Accepts]: Start accepts. Automaton has 359 states and 496 transitions. Word has length 88 [2023-12-19 19:52:36,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:52:36,281 INFO L495 AbstractCegarLoop]: Abstraction has 359 states and 496 transitions. [2023-12-19 19:52:36,281 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2023-12-19 19:52:36,281 INFO L276 IsEmpty]: Start isEmpty. Operand 359 states and 496 transitions. [2023-12-19 19:52:36,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2023-12-19 19:52:36,282 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:52:36,282 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:52:36,287 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2023-12-19 19:52:36,487 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-12-19 19:52:36,487 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:52:36,488 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:52:36,488 INFO L85 PathProgramCache]: Analyzing trace with hash -1858222944, now seen corresponding path program 1 times [2023-12-19 19:52:36,488 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:52:36,488 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [594160039] [2023-12-19 19:52:36,488 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:36,488 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:52:36,497 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:52:36,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1538199467] [2023-12-19 19:52:36,497 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:52:36,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:52:36,497 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:52:36,499 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:52:36,523 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-12-19 19:52:36,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-19 19:52:36,557 INFO L262 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 48 conjunts are in the unsatisfiable core [2023-12-19 19:52:36,558 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-19 19:52:37,278 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 32 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2023-12-19 19:52:37,278 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-19 19:52:42,945 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 23 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2023-12-19 19:52:42,960 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-19 19:52:42,960 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [594160039] [2023-12-19 19:52:42,960 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-19 19:52:42,960 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1538199467] [2023-12-19 19:52:42,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1538199467] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-19 19:52:42,960 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-19 19:52:42,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 22 [2023-12-19 19:52:42,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1947104403] [2023-12-19 19:52:42,960 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-19 19:52:42,961 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-19 19:52:42,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-19 19:52:42,961 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-19 19:52:42,961 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2023-12-19 19:52:42,961 INFO L87 Difference]: Start difference. First operand 359 states and 496 transitions. Second operand has 22 states, 21 states have (on average 2.4761904761904763) internal successors, (52), 19 states have internal predecessors, (52), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-12-19 19:53:07,300 WARN L293 SmtUtils]: Spent 22.27s on a formula simplification that was a NOOP. DAG size: 69 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 19:53:14,795 WARN L293 SmtUtils]: Spent 7.40s on a formula simplification that was a NOOP. DAG size: 62 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 19:53:19,504 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-19 19:53:24,504 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-19 19:53:39,643 WARN L293 SmtUtils]: Spent 7.50s on a formula simplification that was a NOOP. DAG size: 44 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-19 19:53:43,706 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-19 19:53:47,783 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-19 19:53:48,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-19 19:53:48,313 INFO L93 Difference]: Finished difference Result 452 states and 635 transitions. [2023-12-19 19:53:48,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2023-12-19 19:53:48,313 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.4761904761904763) internal successors, (52), 19 states have internal predecessors, (52), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) Word has length 96 [2023-12-19 19:53:48,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-19 19:53:48,316 INFO L225 Difference]: With dead ends: 452 [2023-12-19 19:53:48,316 INFO L226 Difference]: Without dead ends: 450 [2023-12-19 19:53:48,316 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 170 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 319 ImplicationChecksByTransitivity, 50.9s TimeCoverageRelationStatistics Valid=356, Invalid=1284, Unknown=0, NotChecked=0, Total=1640 [2023-12-19 19:53:48,317 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 143 mSDsluCounter, 379 mSDsCounter, 0 mSdLazyCounter, 417 mSolverCounterSat, 98 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 416 SdHoareTripleChecker+Invalid, 519 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 98 IncrementalHoareTripleChecker+Valid, 417 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.0s IncrementalHoareTripleChecker+Time [2023-12-19 19:53:48,317 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [152 Valid, 416 Invalid, 519 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [98 Valid, 417 Invalid, 4 Unknown, 0 Unchecked, 19.0s Time] [2023-12-19 19:53:48,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 450 states. [2023-12-19 19:53:48,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 450 to 425. [2023-12-19 19:53:48,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 425 states, 270 states have (on average 1.2925925925925925) internal successors, (349), 277 states have internal predecessors, (349), 127 states have call successors, (127), 27 states have call predecessors, (127), 27 states have return successors, (125), 120 states have call predecessors, (125), 125 states have call successors, (125) [2023-12-19 19:53:48,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 425 states to 425 states and 601 transitions. [2023-12-19 19:53:48,443 INFO L78 Accepts]: Start accepts. Automaton has 425 states and 601 transitions. Word has length 96 [2023-12-19 19:53:48,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-19 19:53:48,443 INFO L495 AbstractCegarLoop]: Abstraction has 425 states and 601 transitions. [2023-12-19 19:53:48,443 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.4761904761904763) internal successors, (52), 19 states have internal predecessors, (52), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-12-19 19:53:48,443 INFO L276 IsEmpty]: Start isEmpty. Operand 425 states and 601 transitions. [2023-12-19 19:53:48,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2023-12-19 19:53:48,444 INFO L187 NwaCegarLoop]: Found error trace [2023-12-19 19:53:48,444 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:53:48,449 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2023-12-19 19:53:48,649 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-12-19 19:53:48,649 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-19 19:53:48,649 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-19 19:53:48,650 INFO L85 PathProgramCache]: Analyzing trace with hash -615201371, now seen corresponding path program 1 times [2023-12-19 19:53:48,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-19 19:53:48,650 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1182681443] [2023-12-19 19:53:48,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:53:48,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-19 19:53:48,655 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-19 19:53:48,655 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1999061852] [2023-12-19 19:53:48,655 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-19 19:53:48,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-19 19:53:48,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-19 19:53:48,678 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-19 19:53:48,678 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-12-19 19:53:48,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-12-19 19:53:48,747 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-12-19 19:53:48,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-12-19 19:53:48,818 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-12-19 19:53:48,818 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-12-19 19:53:48,819 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-19 19:53:48,846 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2023-12-19 19:53:49,020 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-12-19 19:53:49,023 INFO L445 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-19 19:53:49,026 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-19 19:53:49,065 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 19.12 07:53:49 BoogieIcfgContainer [2023-12-19 19:53:49,065 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-19 19:53:49,065 INFO L158 Benchmark]: Toolchain (without parser) took 90505.87ms. Allocated memory was 157.3MB in the beginning and 226.5MB in the end (delta: 69.2MB). Free memory was 121.1MB in the beginning and 157.4MB in the end (delta: -36.4MB). Peak memory consumption was 33.9MB. Max. memory is 8.0GB. [2023-12-19 19:53:49,065 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 157.3MB. Free memory is still 115.5MB. There was no memory consumed. Max. memory is 8.0GB. [2023-12-19 19:53:49,065 INFO L158 Benchmark]: CACSL2BoogieTranslator took 156.08ms. Allocated memory is still 157.3MB. Free memory was 121.1MB in the beginning and 109.7MB in the end (delta: 11.4MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-19 19:53:49,066 INFO L158 Benchmark]: Boogie Procedure Inliner took 19.74ms. Allocated memory is still 157.3MB. Free memory was 109.5MB in the beginning and 108.0MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-19 19:53:49,066 INFO L158 Benchmark]: Boogie Preprocessor took 22.29ms. Allocated memory is still 157.3MB. Free memory was 108.0MB in the beginning and 105.9MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-19 19:53:49,066 INFO L158 Benchmark]: RCFGBuilder took 293.87ms. Allocated memory is still 157.3MB. Free memory was 105.9MB in the beginning and 93.3MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2023-12-19 19:53:49,066 INFO L158 Benchmark]: TraceAbstraction took 90008.61ms. Allocated memory was 157.3MB in the beginning and 226.5MB in the end (delta: 69.2MB). Free memory was 92.3MB in the beginning and 157.4MB in the end (delta: -65.1MB). Peak memory consumption was 4.5MB. Max. memory is 8.0GB. [2023-12-19 19:53:49,067 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.10ms. Allocated memory is still 157.3MB. Free memory is still 115.5MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 156.08ms. Allocated memory is still 157.3MB. Free memory was 121.1MB in the beginning and 109.7MB in the end (delta: 11.4MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 19.74ms. Allocated memory is still 157.3MB. Free memory was 109.5MB in the beginning and 108.0MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * Boogie Preprocessor took 22.29ms. Allocated memory is still 157.3MB. Free memory was 108.0MB in the beginning and 105.9MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 293.87ms. Allocated memory is still 157.3MB. Free memory was 105.9MB in the beginning and 93.3MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 90008.61ms. Allocated memory was 157.3MB in the beginning and 226.5MB in the end (delta: 69.2MB). Free memory was 92.3MB in the beginning and 157.4MB in the end (delta: -65.1MB). Peak memory consumption was 4.5MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; [L20] int x, y; [L21] long long a, b, p, q, r, s, c, k, xy, yy; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L24] RET assume_abort_if_not(x >= 1) VAL [counter=0, x=2, y=3] [L25] CALL assume_abort_if_not(y >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L25] RET assume_abort_if_not(y >= 1) VAL [counter=0, x=2, y=3] [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 [L33] c = 0 [L34] k = 0 [L35] xy = (long long) x * y [L36] yy = (long long) y * y VAL [a=2, b=3, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L37] CALL assume_abort_if_not(xy < 2147483647) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L37] RET assume_abort_if_not(xy < 2147483647) VAL [a=2, b=3, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L38] CALL assume_abort_if_not(yy < 2147483647) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L38] RET assume_abort_if_not(yy < 2147483647) VAL [a=2, b=3, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L40] EXPR counter++ VAL [a=2, b=3, c=0, counter=1, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L40] COND TRUE counter++<5 [L41] COND FALSE, EXPR !(!(b != 0)) [L43] EXPR c = a [L44] EXPR k = 0 VAL [a=2, b=3, c=2, counter=1, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L46] EXPR counter++ VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L46] COND TRUE, EXPR counter++<5 [L47] CALL, EXPR __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L47] RET, EXPR __VERIFIER_assert(a == k * b + c) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L48] CALL, EXPR __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L48] RET, EXPR __VERIFIER_assert(a == y*r + x*p) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L49] CALL, EXPR __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L49] RET, EXPR __VERIFIER_assert(b == x * q + y * s) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L50] CALL, EXPR __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L50] RET, EXPR __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L51] COND TRUE, EXPR !(c >= b) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L57] EXPR a = b [L58] EXPR b = c [L60] long long temp; [L61] EXPR temp = p [L62] EXPR p = q [L63] EXPR q = temp - q * k [L64] EXPR temp = r [L65] EXPR r = s [L66] EXPR s = temp - s * k [L40-L67] { if (!(b != 0)) break; c = a; k = 0; while (counter++<5) { __VERIFIER_assert(a == k * b + c); __VERIFIER_assert(a == y*r + x*p); __VERIFIER_assert(b == x * q + y * s); __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0); if (!(c >= b)) break; c = c - b; k = k + 1; } a = b; b = c; long long temp; temp = p; p = q; q = temp - q * k; temp = r; r = s; s = temp - s * k; } VAL [a=3, b=2, c=2, counter=2, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L40] EXPR counter++ VAL [a=3, b=2, c=2, counter=3, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L40] COND TRUE counter++<5 [L41] COND FALSE, EXPR !(!(b != 0)) [L43] EXPR c = a [L44] EXPR k = 0 VAL [a=3, b=2, c=3, counter=3, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L46] EXPR counter++ VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L46] COND TRUE, EXPR counter++<5 [L47] CALL, EXPR __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L47] RET, EXPR __VERIFIER_assert(a == k * b + c) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L48] CALL, EXPR __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L48] RET, EXPR __VERIFIER_assert(a == y*r + x*p) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L49] CALL, EXPR __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L49] RET, EXPR __VERIFIER_assert(b == x * q + y * s) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L50] CALL, EXPR __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L50] RET, EXPR __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L51] COND FALSE, EXPR !(!(c >= b)) [L53] EXPR c = c - b [L54] EXPR k = k + 1 VAL [a=3, b=2, c=1, counter=4, k=1, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L46] EXPR counter++ VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L46] COND TRUE, EXPR counter++<5 [L47] CALL, EXPR __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L47] RET, EXPR __VERIFIER_assert(a == k * b + c) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L48] CALL, EXPR __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L48] RET, EXPR __VERIFIER_assert(a == y*r + x*p) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L49] CALL, EXPR __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L49] RET, EXPR __VERIFIER_assert(b == x * q + y * s) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L50] CALL, EXPR __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L50] RET, EXPR __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L51] COND TRUE, EXPR !(c >= b) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=2, xy=6, y=3, yy=9] [L57] EXPR a = b [L58] EXPR b = c [L60] long long temp; [L61] EXPR temp = p [L62] EXPR p = q [L63] EXPR q = temp - q * k [L64] EXPR temp = r [L65] EXPR r = s [L66] EXPR s = temp - s * k [L40-L67] { if (!(b != 0)) break; c = a; k = 0; while (counter++<5) { __VERIFIER_assert(a == k * b + c); __VERIFIER_assert(a == y*r + x*p); __VERIFIER_assert(b == x * q + y * s); __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0); if (!(c >= b)) break; c = c - b; k = k + 1; } a = b; b = c; long long temp; temp = p; p = q; q = temp - q * k; temp = r; r = s; s = temp - s * k; } VAL [a=2, b=1, c=1, counter=5, k=1, p=1, q=-1, r=0, s=1, x=2, xy=6, y=3, yy=9] [L40] EXPR counter++ VAL [a=2, b=1, c=1, counter=6, k=1, p=1, q=-1, r=0, s=1, x=2, xy=6, y=3, yy=9] [L40] COND FALSE !(counter++<5) [L70] CALL __VERIFIER_assert(q*x + s*y == 0) VAL [\old(cond)=0, counter=6] [L11] COND TRUE !(cond) VAL [\old(cond)=0, cond=0, counter=6] [L13] reach_error() VAL [\old(cond)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 31 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 89.9s, OverallIterations: 18, TraceHistogramMax: 13, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 73.7s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 4 mSolverCounterUnknown, 775 SdHoareTripleChecker+Valid, 22.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 708 mSDsluCounter, 3443 SdHoareTripleChecker+Invalid, 22.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2794 mSDsCounter, 387 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2167 IncrementalHoareTripleChecker+Invalid, 2558 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 387 mSolverCounterUnsat, 649 mSDtfsCounter, 2167 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1562 GetRequests, 1317 SyntacticMatches, 8 SemanticMatches, 237 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1033 ImplicationChecksByTransitivity, 56.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=425occurred in iteration=17, InterpolantAutomatonStates: 178, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.5s AutomataMinimizationTime, 17 MinimizatonAttempts, 178 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 10.5s InterpolantComputationTime, 1040 NumberOfCodeBlocks, 1020 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 1425 ConstructedInterpolants, 0 QuantifiedInterpolants, 8029 SizeOfPredicates, 79 NumberOfNonLiveVariables, 2627 ConjunctsInSsa, 330 ConjunctsInUnsatCore, 27 InterpolantComputations, 7 PerfectInterpolantSequences, 1954/2162 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2023-12-19 19:53:49,082 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...