/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 false -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-21 07:15:25,618 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-21 07:15:25,701 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-21 07:15:25,704 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-21 07:15:25,704 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-21 07:15:25,738 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-21 07:15:25,738 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-21 07:15:25,739 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-21 07:15:25,740 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-21 07:15:25,743 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-21 07:15:25,743 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-21 07:15:25,743 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-21 07:15:25,744 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-21 07:15:25,745 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-21 07:15:25,745 INFO L153 SettingsManager]: * Use SBE=true [2023-12-21 07:15:25,746 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-21 07:15:25,746 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-21 07:15:25,746 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-21 07:15:25,746 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-21 07:15:25,747 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-21 07:15:25,748 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-21 07:15:25,748 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-21 07:15:25,748 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-21 07:15:25,748 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-21 07:15:25,749 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-21 07:15:25,749 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-21 07:15:25,749 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-21 07:15:25,749 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-21 07:15:25,750 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-21 07:15:25,750 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-21 07:15:25,751 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-21 07:15:25,751 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-21 07:15:25,751 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 07:15:25,752 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-21 07:15:25,752 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-21 07:15:25,752 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-21 07:15:25,752 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-21 07:15:25,752 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-21 07:15:25,752 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-21 07:15:25,753 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-21 07:15:25,753 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-21 07:15:25,753 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-21 07:15:25,753 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-21 07:15:25,753 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 -> false [2023-12-21 07:15:25,984 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-21 07:15:26,006 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-21 07:15:26,008 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-21 07:15:26,009 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-21 07:15:26,009 INFO L274 PluginConnector]: CDTParser initialized [2023-12-21 07:15:26,010 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2023-12-21 07:15:27,123 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-21 07:15:27,272 INFO L384 CDTParser]: Found 1 translation units. [2023-12-21 07:15:27,273 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2023-12-21 07:15:27,279 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7b0013a38/349ce346161b4fc78c4a875eebdb7072/FLAG6410fae27 [2023-12-21 07:15:27,289 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7b0013a38/349ce346161b4fc78c4a875eebdb7072 [2023-12-21 07:15:27,291 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-21 07:15:27,292 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-21 07:15:27,293 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-21 07:15:27,293 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-21 07:15:27,300 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-21 07:15:27,301 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,301 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@78dc64f9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27, skipping insertion in model container [2023-12-21 07:15:27,302 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,322 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-21 07:15:27,434 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/hard-ll_valuebound20.c[538,551] [2023-12-21 07:15:27,449 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 07:15:27,457 INFO L202 MainTranslator]: Completed pre-run [2023-12-21 07:15:27,466 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/hard-ll_valuebound20.c[538,551] [2023-12-21 07:15:27,473 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 07:15:27,484 INFO L206 MainTranslator]: Completed translation [2023-12-21 07:15:27,485 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27 WrapperNode [2023-12-21 07:15:27,485 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-21 07:15:27,486 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-21 07:15:27,486 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-21 07:15:27,486 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-21 07:15:27,490 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,495 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,510 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 56 [2023-12-21 07:15:27,511 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-21 07:15:27,511 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-21 07:15:27,511 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-21 07:15:27,512 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-21 07:15:27,521 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,521 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,522 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,531 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-21 07:15:27,531 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,531 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,534 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,537 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,537 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,538 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,539 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-21 07:15:27,540 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-21 07:15:27,540 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-21 07:15:27,540 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-21 07:15:27,541 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (1/1) ... [2023-12-21 07:15:27,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 07:15:27,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:27,575 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-21 07:15:27,597 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-21 07:15:27,607 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-21 07:15:27,608 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-12-21 07:15:27,608 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-12-21 07:15:27,609 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-21 07:15:27,609 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-21 07:15:27,609 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-21 07:15:27,610 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-21 07:15:27,610 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-21 07:15:27,663 INFO L241 CfgBuilder]: Building ICFG [2023-12-21 07:15:27,665 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-21 07:15:27,871 INFO L282 CfgBuilder]: Performing block encoding [2023-12-21 07:15:27,891 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-21 07:15:27,892 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-21 07:15:27,892 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 07:15:27 BoogieIcfgContainer [2023-12-21 07:15:27,892 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-21 07:15:27,894 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-21 07:15:27,894 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-21 07:15:27,896 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-21 07:15:27,897 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.12 07:15:27" (1/3) ... [2023-12-21 07:15:27,897 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@44f6397e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 07:15:27, skipping insertion in model container [2023-12-21 07:15:27,897 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:15:27" (2/3) ... [2023-12-21 07:15:27,897 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@44f6397e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 07:15:27, skipping insertion in model container [2023-12-21 07:15:27,898 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 07:15:27" (3/3) ... [2023-12-21 07:15:27,898 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound20.c [2023-12-21 07:15:27,915 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-21 07:15:27,916 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-21 07:15:27,954 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-21 07:15:27,960 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;@488b79dd, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-21 07:15:27,960 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-21 07:15:27,963 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 16 states have (on average 1.625) internal successors, (26), 17 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-21 07:15:27,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-12-21 07:15:27,978 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:27,979 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:15:27,979 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:27,983 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:27,983 INFO L85 PathProgramCache]: Analyzing trace with hash 760957734, now seen corresponding path program 1 times [2023-12-21 07:15:27,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:27,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [11120324] [2023-12-21 07:15:27,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:27,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:28,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,110 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-12-21 07:15:28,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,118 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-12-21 07:15:28,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,122 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-12-21 07:15:28,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,128 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:15:28,128 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:28,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [11120324] [2023-12-21 07:15:28,129 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [11120324] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:15:28,129 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:15:28,129 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-21 07:15:28,131 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [856881147] [2023-12-21 07:15:28,131 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:15:28,135 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-21 07:15:28,135 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:28,156 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-21 07:15:28,156 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-21 07:15:28,158 INFO L87 Difference]: Start difference. First operand has 30 states, 16 states have (on average 1.625) internal successors, (26), 17 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.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-21 07:15:28,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:28,182 INFO L93 Difference]: Finished difference Result 58 states and 99 transitions. [2023-12-21 07:15:28,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-21 07:15:28,184 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2023-12-21 07:15:28,185 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:28,190 INFO L225 Difference]: With dead ends: 58 [2023-12-21 07:15:28,190 INFO L226 Difference]: Without dead ends: 28 [2023-12-21 07:15:28,193 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 11 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-21 07:15:28,196 INFO L413 NwaCegarLoop]: 38 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, 38 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-21 07:15:28,196 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:15:28,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-12-21 07:15:28,220 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2023-12-21 07:15:28,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 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-21 07:15:28,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 38 transitions. [2023-12-21 07:15:28,224 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 38 transitions. Word has length 23 [2023-12-21 07:15:28,224 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:28,224 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 38 transitions. [2023-12-21 07:15:28,224 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-21 07:15:28,224 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 38 transitions. [2023-12-21 07:15:28,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-12-21 07:15:28,225 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:28,225 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:15:28,226 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-12-21 07:15:28,226 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:28,227 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:28,227 INFO L85 PathProgramCache]: Analyzing trace with hash -387749596, now seen corresponding path program 1 times [2023-12-21 07:15:28,227 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:28,227 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [786302214] [2023-12-21 07:15:28,227 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:28,228 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:28,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,424 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-12-21 07:15:28,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,436 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-12-21 07:15:28,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,440 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-12-21 07:15:28,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,446 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:15:28,447 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:28,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [786302214] [2023-12-21 07:15:28,447 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [786302214] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:15:28,447 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:15:28,447 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-21 07:15:28,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [64018766] [2023-12-21 07:15:28,448 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:15:28,449 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:15:28,449 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:28,450 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:15:28,450 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:15:28,450 INFO L87 Difference]: Start difference. First operand 28 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:15:28,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:28,523 INFO L93 Difference]: Finished difference Result 41 states and 55 transitions. [2023-12-21 07:15:28,524 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:15:28,524 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 23 [2023-12-21 07:15:28,525 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:28,527 INFO L225 Difference]: With dead ends: 41 [2023-12-21 07:15:28,527 INFO L226 Difference]: Without dead ends: 39 [2023-12-21 07:15:28,528 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:15:28,529 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 12 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:15:28,530 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 118 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:15:28,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2023-12-21 07:15:28,537 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 32. [2023-12-21 07:15:28,537 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 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-21 07:15:28,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2023-12-21 07:15:28,538 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 23 [2023-12-21 07:15:28,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:28,539 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2023-12-21 07:15:28,539 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:15:28,539 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2023-12-21 07:15:28,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-12-21 07:15:28,540 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:28,540 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:15:28,540 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-21 07:15:28,541 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:28,541 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:28,541 INFO L85 PathProgramCache]: Analyzing trace with hash -1391236353, now seen corresponding path program 1 times [2023-12-21 07:15:28,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:28,541 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [895356322] [2023-12-21 07:15:28,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:28,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:28,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,642 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-12-21 07:15:28,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,647 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-12-21 07:15:28,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,650 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-12-21 07:15:28,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,653 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2023-12-21 07:15:28,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,659 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:15:28,659 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:28,659 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [895356322] [2023-12-21 07:15:28,660 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [895356322] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:15:28,668 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:15:28,668 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-21 07:15:28,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [797045814] [2023-12-21 07:15:28,668 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:15:28,668 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:15:28,669 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:28,669 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:15:28,669 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:15:28,670 INFO L87 Difference]: Start difference. First operand 32 states and 41 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), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-21 07:15:28,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:28,748 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2023-12-21 07:15:28,749 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:15:28,749 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), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2023-12-21 07:15:28,749 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:28,750 INFO L225 Difference]: With dead ends: 45 [2023-12-21 07:15:28,750 INFO L226 Difference]: Without dead ends: 43 [2023-12-21 07:15:28,750 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:15:28,751 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 10 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 07:15:28,752 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 114 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 07:15:28,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2023-12-21 07:15:28,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 36. [2023-12-21 07:15:28,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-21 07:15:28,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2023-12-21 07:15:28,759 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 28 [2023-12-21 07:15:28,760 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:28,760 INFO L495 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2023-12-21 07:15:28,760 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), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-21 07:15:28,760 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2023-12-21 07:15:28,761 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-12-21 07:15:28,761 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:28,761 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:15:28,761 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-12-21 07:15:28,761 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:28,762 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:28,762 INFO L85 PathProgramCache]: Analyzing trace with hash 831418820, now seen corresponding path program 1 times [2023-12-21 07:15:28,762 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:28,762 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2121278418] [2023-12-21 07:15:28,762 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:28,762 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:28,774 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:15:28,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1083498140] [2023-12-21 07:15:28,775 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:28,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:28,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:28,784 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-21 07:15:28,788 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-21 07:15:28,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:28,841 INFO L262 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 19 conjunts are in the unsatisfiable core [2023-12-21 07:15:28,848 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:15:28,987 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2023-12-21 07:15:28,987 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:15:29,139 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2023-12-21 07:15:29,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:29,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2121278418] [2023-12-21 07:15:29,140 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:15:29,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1083498140] [2023-12-21 07:15:29,141 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1083498140] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:15:29,141 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:15:29,141 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-12-21 07:15:29,141 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1375077374] [2023-12-21 07:15:29,141 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:15:29,142 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 07:15:29,142 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:29,142 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 07:15:29,143 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-12-21 07:15:29,143 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 12 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 5 states have call successors, (7) [2023-12-21 07:15:29,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:29,388 INFO L93 Difference]: Finished difference Result 71 states and 92 transitions. [2023-12-21 07:15:29,389 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-21 07:15:29,389 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 5 states have call successors, (7) Word has length 33 [2023-12-21 07:15:29,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:29,393 INFO L225 Difference]: With dead ends: 71 [2023-12-21 07:15:29,393 INFO L226 Difference]: Without dead ends: 56 [2023-12-21 07:15:29,394 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-12-21 07:15:29,395 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 27 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 07:15:29,395 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 105 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 07:15:29,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2023-12-21 07:15:29,407 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2023-12-21 07:15:29,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 32 states have (on average 1.15625) internal successors, (37), 34 states have internal predecessors, (37), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2023-12-21 07:15:29,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2023-12-21 07:15:29,409 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 33 [2023-12-21 07:15:29,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:29,409 INFO L495 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2023-12-21 07:15:29,409 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 5 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 5 states have call successors, (7) [2023-12-21 07:15:29,409 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2023-12-21 07:15:29,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-12-21 07:15:29,410 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:29,411 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:15:29,416 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-12-21 07:15:29,616 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:29,617 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:29,617 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:29,617 INFO L85 PathProgramCache]: Analyzing trace with hash -1016562388, now seen corresponding path program 1 times [2023-12-21 07:15:29,617 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:29,617 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1028910461] [2023-12-21 07:15:29,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:29,618 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:29,636 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:15:29,636 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2008050347] [2023-12-21 07:15:29,636 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:29,637 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:29,637 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:29,638 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-21 07:15:29,661 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-21 07:15:29,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:29,687 INFO L262 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 22 conjunts are in the unsatisfiable core [2023-12-21 07:15:29,693 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:15:29,913 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-12-21 07:15:29,913 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:15:29,913 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:29,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1028910461] [2023-12-21 07:15:29,914 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:15:29,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2008050347] [2023-12-21 07:15:29,914 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2008050347] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:15:29,914 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:15:29,914 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2023-12-21 07:15:29,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1364049119] [2023-12-21 07:15:29,915 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:15:29,915 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-21 07:15:29,915 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:29,916 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-21 07:15:29,916 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2023-12-21 07:15:29,916 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 10 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2023-12-21 07:15:30,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:30,055 INFO L93 Difference]: Finished difference Result 66 states and 77 transitions. [2023-12-21 07:15:30,056 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-21 07:15:30,056 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 40 [2023-12-21 07:15:30,056 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:30,057 INFO L225 Difference]: With dead ends: 66 [2023-12-21 07:15:30,057 INFO L226 Difference]: Without dead ends: 55 [2023-12-21 07:15:30,058 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2023-12-21 07:15:30,058 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 30 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 07:15:30,059 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 120 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 07:15:30,059 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2023-12-21 07:15:30,071 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2023-12-21 07:15:30,072 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 33 states have (on average 1.121212121212121) internal successors, (37), 35 states have internal predecessors, (37), 14 states have call successors, (14), 7 states have call predecessors, (14), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-21 07:15:30,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 64 transitions. [2023-12-21 07:15:30,073 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 64 transitions. Word has length 40 [2023-12-21 07:15:30,073 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:30,073 INFO L495 AbstractCegarLoop]: Abstraction has 55 states and 64 transitions. [2023-12-21 07:15:30,073 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2023-12-21 07:15:30,073 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2023-12-21 07:15:30,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2023-12-21 07:15:30,074 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:30,075 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:15:30,082 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-21 07:15:30,280 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:30,280 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:30,281 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:30,281 INFO L85 PathProgramCache]: Analyzing trace with hash 2057146835, now seen corresponding path program 1 times [2023-12-21 07:15:30,281 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:30,281 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [990096555] [2023-12-21 07:15:30,281 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:30,281 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:30,291 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:15:30,291 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [449018908] [2023-12-21 07:15:30,291 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:30,291 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:30,291 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:30,292 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-21 07:15:30,301 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-21 07:15:30,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:30,341 INFO L262 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 24 conjunts are in the unsatisfiable core [2023-12-21 07:15:30,344 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:15:30,710 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2023-12-21 07:15:30,711 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:15:30,900 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2023-12-21 07:15:30,900 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:30,900 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [990096555] [2023-12-21 07:15:30,900 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:15:30,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [449018908] [2023-12-21 07:15:30,901 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [449018908] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:15:30,901 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:15:30,901 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 16 [2023-12-21 07:15:30,901 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1653763722] [2023-12-21 07:15:30,901 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:15:30,902 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-12-21 07:15:30,902 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:30,902 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-12-21 07:15:30,903 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=191, Unknown=0, NotChecked=0, Total=240 [2023-12-21 07:15:30,903 INFO L87 Difference]: Start difference. First operand 55 states and 64 transitions. Second operand has 16 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 12 states have internal predecessors, (28), 8 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) [2023-12-21 07:15:31,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:31,255 INFO L93 Difference]: Finished difference Result 96 states and 120 transitions. [2023-12-21 07:15:31,255 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-12-21 07:15:31,256 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 12 states have internal predecessors, (28), 8 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) Word has length 57 [2023-12-21 07:15:31,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:31,257 INFO L225 Difference]: With dead ends: 96 [2023-12-21 07:15:31,257 INFO L226 Difference]: Without dead ends: 92 [2023-12-21 07:15:31,258 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 59 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=102, Invalid=360, Unknown=0, NotChecked=0, Total=462 [2023-12-21 07:15:31,258 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 41 mSDsluCounter, 275 mSDsCounter, 0 mSdLazyCounter, 247 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 306 SdHoareTripleChecker+Invalid, 280 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 247 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 07:15:31,258 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 306 Invalid, 280 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 247 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 07:15:31,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2023-12-21 07:15:31,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 85. [2023-12-21 07:15:31,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 51 states have (on average 1.1568627450980393) internal successors, (59), 54 states have internal predecessors, (59), 23 states have call successors, (23), 10 states have call predecessors, (23), 10 states have return successors, (22), 20 states have call predecessors, (22), 22 states have call successors, (22) [2023-12-21 07:15:31,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 104 transitions. [2023-12-21 07:15:31,282 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 104 transitions. Word has length 57 [2023-12-21 07:15:31,282 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:31,282 INFO L495 AbstractCegarLoop]: Abstraction has 85 states and 104 transitions. [2023-12-21 07:15:31,282 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 12 states have internal predecessors, (28), 8 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) [2023-12-21 07:15:31,282 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 104 transitions. [2023-12-21 07:15:31,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-12-21 07:15:31,284 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:31,284 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 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-21 07:15:31,295 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-12-21 07:15:31,495 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:31,495 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:31,496 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:31,496 INFO L85 PathProgramCache]: Analyzing trace with hash 1282123871, now seen corresponding path program 1 times [2023-12-21 07:15:31,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:31,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1751325927] [2023-12-21 07:15:31,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:31,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:31,506 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:15:31,506 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1915402494] [2023-12-21 07:15:31,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:31,506 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:31,506 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:31,507 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-21 07:15:31,514 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-21 07:15:31,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:31,567 INFO L262 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 33 conjunts are in the unsatisfiable core [2023-12-21 07:15:31,575 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:15:31,994 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2023-12-21 07:15:31,994 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:15:33,419 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2023-12-21 07:15:33,419 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:33,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1751325927] [2023-12-21 07:15:33,419 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:15:33,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1915402494] [2023-12-21 07:15:33,419 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1915402494] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:15:33,420 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:15:33,420 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 19 [2023-12-21 07:15:33,420 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1089866869] [2023-12-21 07:15:33,420 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:15:33,423 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-12-21 07:15:33,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:33,424 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-12-21 07:15:33,424 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=278, Unknown=0, NotChecked=0, Total=342 [2023-12-21 07:15:33,424 INFO L87 Difference]: Start difference. First operand 85 states and 104 transitions. Second operand has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 16 states have internal predecessors, (34), 9 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-21 07:15:39,211 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-21 07:15:40,572 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.30s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:15:43,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:43,266 INFO L93 Difference]: Finished difference Result 148 states and 197 transitions. [2023-12-21 07:15:43,267 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-21 07:15:43,267 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 16 states have internal predecessors, (34), 9 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) Word has length 70 [2023-12-21 07:15:43,268 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:43,269 INFO L225 Difference]: With dead ends: 148 [2023-12-21 07:15:43,269 INFO L226 Difference]: Without dead ends: 127 [2023-12-21 07:15:43,270 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 155 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=158, Invalid=654, Unknown=0, NotChecked=0, Total=812 [2023-12-21 07:15:43,271 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 88 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 340 mSolverCounterSat, 89 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 430 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 340 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.2s IncrementalHoareTripleChecker+Time [2023-12-21 07:15:43,271 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 249 Invalid, 430 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 340 Invalid, 1 Unknown, 0 Unchecked, 7.2s Time] [2023-12-21 07:15:43,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-12-21 07:15:43,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 99. [2023-12-21 07:15:43,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 60 states have (on average 1.1833333333333333) internal successors, (71), 63 states have internal predecessors, (71), 27 states have call successors, (27), 11 states have call predecessors, (27), 11 states have return successors, (26), 24 states have call predecessors, (26), 26 states have call successors, (26) [2023-12-21 07:15:43,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 124 transitions. [2023-12-21 07:15:43,298 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 124 transitions. Word has length 70 [2023-12-21 07:15:43,298 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:43,298 INFO L495 AbstractCegarLoop]: Abstraction has 99 states and 124 transitions. [2023-12-21 07:15:43,299 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 16 states have internal predecessors, (34), 9 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-21 07:15:43,299 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 124 transitions. [2023-12-21 07:15:43,300 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2023-12-21 07:15:43,300 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:43,300 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 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] [2023-12-21 07:15:43,308 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-21 07:15:43,505 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:43,506 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:43,506 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:43,506 INFO L85 PathProgramCache]: Analyzing trace with hash 1411586487, now seen corresponding path program 1 times [2023-12-21 07:15:43,506 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:43,506 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [520612342] [2023-12-21 07:15:43,507 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:43,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:43,517 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:15:43,517 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1727753632] [2023-12-21 07:15:43,517 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:43,518 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:43,518 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:43,519 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-21 07:15:43,521 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-21 07:15:43,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:15:43,567 INFO L262 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 25 conjunts are in the unsatisfiable core [2023-12-21 07:15:43,569 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:15:43,822 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 26 proven. 9 refuted. 0 times theorem prover too weak. 186 trivial. 0 not checked. [2023-12-21 07:15:43,822 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:15:44,070 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:44,070 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [520612342] [2023-12-21 07:15:44,070 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:15:44,070 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1727753632] [2023-12-21 07:15:44,070 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1727753632] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-21 07:15:44,071 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-21 07:15:44,071 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2023-12-21 07:15:44,071 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1443775826] [2023-12-21 07:15:44,071 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-21 07:15:44,071 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 07:15:44,071 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:44,072 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 07:15:44,072 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2023-12-21 07:15:44,072 INFO L87 Difference]: Start difference. First operand 99 states and 124 transitions. Second operand has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2023-12-21 07:15:44,490 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:44,491 INFO L93 Difference]: Finished difference Result 113 states and 141 transitions. [2023-12-21 07:15:44,491 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-21 07:15:44,491 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) Word has length 81 [2023-12-21 07:15:44,492 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:44,493 INFO L225 Difference]: With dead ends: 113 [2023-12-21 07:15:44,493 INFO L226 Difference]: Without dead ends: 104 [2023-12-21 07:15:44,493 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2023-12-21 07:15:44,494 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 35 mSDsluCounter, 290 mSDsCounter, 0 mSdLazyCounter, 252 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 328 SdHoareTripleChecker+Invalid, 275 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 252 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 07:15:44,494 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 328 Invalid, 275 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 252 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 07:15:44,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2023-12-21 07:15:44,522 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 104. [2023-12-21 07:15:44,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 63 states have (on average 1.1428571428571428) internal successors, (72), 65 states have internal predecessors, (72), 29 states have call successors, (29), 11 states have call predecessors, (29), 11 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2023-12-21 07:15:44,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 129 transitions. [2023-12-21 07:15:44,524 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 129 transitions. Word has length 81 [2023-12-21 07:15:44,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:44,524 INFO L495 AbstractCegarLoop]: Abstraction has 104 states and 129 transitions. [2023-12-21 07:15:44,524 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2023-12-21 07:15:44,524 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 129 transitions. [2023-12-21 07:15:44,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2023-12-21 07:15:44,529 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:44,529 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 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] [2023-12-21 07:15:44,540 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-21 07:15:44,730 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:44,730 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:44,730 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:44,730 INFO L85 PathProgramCache]: Analyzing trace with hash -302279341, now seen corresponding path program 2 times [2023-12-21 07:15:44,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:44,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [399520488] [2023-12-21 07:15:44,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:44,731 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:44,739 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:15:44,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2119336803] [2023-12-21 07:15:44,739 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 07:15:44,740 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:44,740 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:44,747 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-21 07:15:44,767 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-21 07:15:44,801 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 07:15:44,801 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:15:44,803 INFO L262 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-21 07:15:44,805 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:15:44,831 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2023-12-21 07:15:44,831 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:15:44,912 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2023-12-21 07:15:44,913 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:15:44,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [399520488] [2023-12-21 07:15:44,913 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:15:44,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2119336803] [2023-12-21 07:15:44,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2119336803] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:15:44,913 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:15:44,913 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2023-12-21 07:15:44,913 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1047728032] [2023-12-21 07:15:44,914 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:15:44,914 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:15:44,914 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:15:44,915 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:15:44,915 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:15:44,915 INFO L87 Difference]: Start difference. First operand 104 states and 129 transitions. Second operand has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2023-12-21 07:15:44,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:15:44,980 INFO L93 Difference]: Finished difference Result 129 states and 162 transitions. [2023-12-21 07:15:44,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-21 07:15:44,980 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 83 [2023-12-21 07:15:44,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:15:44,984 INFO L225 Difference]: With dead ends: 129 [2023-12-21 07:15:44,984 INFO L226 Difference]: Without dead ends: 99 [2023-12-21 07:15:44,985 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 161 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:15:44,986 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 136 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-21 07:15:44,987 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 136 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:15:44,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-12-21 07:15:45,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2023-12-21 07:15:45,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 60 states have (on average 1.1333333333333333) internal successors, (68), 62 states have internal predecessors, (68), 27 states have call successors, (27), 11 states have call predecessors, (27), 11 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2023-12-21 07:15:45,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 121 transitions. [2023-12-21 07:15:45,015 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 121 transitions. Word has length 83 [2023-12-21 07:15:45,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:15:45,016 INFO L495 AbstractCegarLoop]: Abstraction has 99 states and 121 transitions. [2023-12-21 07:15:45,016 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2023-12-21 07:15:45,016 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 121 transitions. [2023-12-21 07:15:45,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2023-12-21 07:15:45,017 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:15:45,017 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:15:45,030 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-21 07:15:45,223 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:45,223 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:15:45,224 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:15:45,224 INFO L85 PathProgramCache]: Analyzing trace with hash 1209712204, now seen corresponding path program 3 times [2023-12-21 07:15:45,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:15:45,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2013837114] [2023-12-21 07:15:45,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:15:45,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:15:45,232 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:15:45,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1218183109] [2023-12-21 07:15:45,232 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-21 07:15:45,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:15:45,233 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:15:45,234 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-21 07:15:45,252 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-21 07:15:45,293 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-12-21 07:15:45,293 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:15:45,294 INFO L262 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 43 conjunts are in the unsatisfiable core [2023-12-21 07:15:45,297 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:15:45,748 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 32 proven. 24 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2023-12-21 07:15:45,749 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:16:19,398 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 324 trivial. 0 not checked. [2023-12-21 07:16:19,398 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:16:19,399 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2013837114] [2023-12-21 07:16:19,399 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:16:19,399 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1218183109] [2023-12-21 07:16:19,399 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1218183109] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:16:19,399 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:16:19,399 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2023-12-21 07:16:19,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1028593334] [2023-12-21 07:16:19,399 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:16:19,400 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-21 07:16:19,400 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:16:19,400 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-21 07:16:19,401 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2023-12-21 07:16:19,401 INFO L87 Difference]: Start difference. First operand 99 states and 121 transitions. Second operand has 21 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 10 states have call predecessors, (30), 9 states have call successors, (30) [2023-12-21 07:16:26,312 WARN L293 SmtUtils]: Spent 5.15s on a formula simplification. DAG size of input: 172 DAG size of output: 48 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:16:31,854 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.17s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:16:37,381 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.33s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:16:37,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:16:37,589 INFO L93 Difference]: Finished difference Result 211 states and 282 transitions. [2023-12-21 07:16:37,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-12-21 07:16:37,589 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 10 states have call predecessors, (30), 9 states have call successors, (30) Word has length 100 [2023-12-21 07:16:37,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:16:37,590 INFO L225 Difference]: With dead ends: 211 [2023-12-21 07:16:37,591 INFO L226 Difference]: Without dead ends: 168 [2023-12-21 07:16:37,591 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 179 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 13.4s TimeCoverageRelationStatistics Valid=137, Invalid=619, Unknown=0, NotChecked=0, Total=756 [2023-12-21 07:16:37,592 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 98 mSDsluCounter, 452 mSDsCounter, 0 mSdLazyCounter, 583 mSolverCounterSat, 110 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 108 SdHoareTripleChecker+Valid, 493 SdHoareTripleChecker+Invalid, 693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 110 IncrementalHoareTripleChecker+Valid, 583 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.3s IncrementalHoareTripleChecker+Time [2023-12-21 07:16:37,592 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [108 Valid, 493 Invalid, 693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [110 Valid, 583 Invalid, 0 Unknown, 0 Unchecked, 9.3s Time] [2023-12-21 07:16:37,593 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2023-12-21 07:16:37,642 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 152. [2023-12-21 07:16:37,642 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 91 states have (on average 1.1538461538461537) internal successors, (105), 95 states have internal predecessors, (105), 46 states have call successors, (46), 14 states have call predecessors, (46), 14 states have return successors, (45), 42 states have call predecessors, (45), 45 states have call successors, (45) [2023-12-21 07:16:37,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 196 transitions. [2023-12-21 07:16:37,644 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 196 transitions. Word has length 100 [2023-12-21 07:16:37,645 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:16:37,645 INFO L495 AbstractCegarLoop]: Abstraction has 152 states and 196 transitions. [2023-12-21 07:16:37,646 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 10 states have call predecessors, (30), 9 states have call successors, (30) [2023-12-21 07:16:37,646 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 196 transitions. [2023-12-21 07:16:37,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2023-12-21 07:16:37,649 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:16:37,649 INFO L195 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:16:37,654 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-12-21 07:16:37,849 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:16:37,850 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:16:37,850 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:16:37,850 INFO L85 PathProgramCache]: Analyzing trace with hash 924515754, now seen corresponding path program 2 times [2023-12-21 07:16:37,850 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:16:37,851 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [700978856] [2023-12-21 07:16:37,851 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:16:37,851 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:16:37,858 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:16:37,858 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [363451181] [2023-12-21 07:16:37,859 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 07:16:37,859 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:16:37,859 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:16:37,860 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-21 07:16:37,862 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-21 07:16:37,938 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 07:16:37,938 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:16:37,940 INFO L262 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 47 conjunts are in the unsatisfiable core [2023-12-21 07:16:37,943 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:16:39,328 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 32 proven. 68 refuted. 0 times theorem prover too weak. 390 trivial. 0 not checked. [2023-12-21 07:16:39,328 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:16:59,180 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 32 proven. 68 refuted. 0 times theorem prover too weak. 390 trivial. 0 not checked. [2023-12-21 07:16:59,180 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:16:59,181 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [700978856] [2023-12-21 07:16:59,181 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:16:59,181 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [363451181] [2023-12-21 07:16:59,181 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [363451181] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:16:59,181 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:16:59,181 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 26 [2023-12-21 07:16:59,181 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1647818389] [2023-12-21 07:16:59,181 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:16:59,182 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-12-21 07:16:59,182 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:16:59,183 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-12-21 07:16:59,183 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=509, Unknown=0, NotChecked=0, Total=650 [2023-12-21 07:16:59,183 INFO L87 Difference]: Start difference. First operand 152 states and 196 transitions. Second operand has 26 states, 24 states have (on average 2.0) internal successors, (48), 24 states have internal predecessors, (48), 16 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (33), 14 states have call predecessors, (33), 14 states have call successors, (33) [2023-12-21 07:17:09,502 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.03s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:17:12,841 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.50s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:17:15,608 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:17:15,608 INFO L93 Difference]: Finished difference Result 233 states and 306 transitions. [2023-12-21 07:17:15,609 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-12-21 07:17:15,609 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 24 states have (on average 2.0) internal successors, (48), 24 states have internal predecessors, (48), 16 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (33), 14 states have call predecessors, (33), 14 states have call successors, (33) Word has length 111 [2023-12-21 07:17:15,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:17:15,610 INFO L225 Difference]: With dead ends: 233 [2023-12-21 07:17:15,610 INFO L226 Difference]: Without dead ends: 171 [2023-12-21 07:17:15,611 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 231 GetRequests, 196 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 205 ImplicationChecksByTransitivity, 12.3s TimeCoverageRelationStatistics Valid=322, Invalid=1010, Unknown=0, NotChecked=0, Total=1332 [2023-12-21 07:17:15,611 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 56 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 434 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 399 SdHoareTripleChecker+Invalid, 523 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 434 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.6s IncrementalHoareTripleChecker+Time [2023-12-21 07:17:15,611 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 399 Invalid, 523 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 434 Invalid, 0 Unknown, 0 Unchecked, 7.6s Time] [2023-12-21 07:17:15,612 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2023-12-21 07:17:15,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 135. [2023-12-21 07:17:15,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 82 states have (on average 1.146341463414634) internal successors, (94), 84 states have internal predecessors, (94), 38 states have call successors, (38), 14 states have call predecessors, (38), 14 states have return successors, (37), 36 states have call predecessors, (37), 37 states have call successors, (37) [2023-12-21 07:17:15,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 169 transitions. [2023-12-21 07:17:15,667 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 169 transitions. Word has length 111 [2023-12-21 07:17:15,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:17:15,668 INFO L495 AbstractCegarLoop]: Abstraction has 135 states and 169 transitions. [2023-12-21 07:17:15,668 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 24 states have (on average 2.0) internal successors, (48), 24 states have internal predecessors, (48), 16 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (33), 14 states have call predecessors, (33), 14 states have call successors, (33) [2023-12-21 07:17:15,668 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 169 transitions. [2023-12-21 07:17:15,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2023-12-21 07:17:15,669 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:17:15,669 INFO L195 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:17:15,676 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-21 07:17:15,875 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,SelfDestructingSolverStorable10 [2023-12-21 07:17:15,875 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:17:15,876 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:17:15,876 INFO L85 PathProgramCache]: Analyzing trace with hash -1038207041, now seen corresponding path program 4 times [2023-12-21 07:17:15,876 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:17:15,876 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1259716122] [2023-12-21 07:17:15,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:17:15,876 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:17:15,896 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:17:15,896 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1163753403] [2023-12-21 07:17:15,896 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-21 07:17:15,896 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:17:15,896 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:17:15,898 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-21 07:17:15,900 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-21 07:17:15,993 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-21 07:17:15,994 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:17:15,995 INFO L262 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 59 conjunts are in the unsatisfiable core [2023-12-21 07:17:15,999 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:17:16,638 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 62 proven. 76 refuted. 0 times theorem prover too weak. 573 trivial. 0 not checked. [2023-12-21 07:17:16,638 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:18:57,663 WARN L293 SmtUtils]: Spent 22.64s on a formula simplification that was a NOOP. DAG size: 386 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:20:42,814 WARN L293 SmtUtils]: Spent 7.53s on a formula simplification. DAG size of input: 115 DAG size of output: 113 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:21:17,216 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 62 proven. 76 refuted. 0 times theorem prover too weak. 573 trivial. 0 not checked. [2023-12-21 07:21:17,216 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:21:17,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1259716122] [2023-12-21 07:21:17,216 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:21:17,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1163753403] [2023-12-21 07:21:17,217 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1163753403] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:21:17,217 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:21:17,217 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 31 [2023-12-21 07:21:17,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [169730339] [2023-12-21 07:21:17,217 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:21:17,217 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2023-12-21 07:21:17,217 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:21:17,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2023-12-21 07:21:17,218 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=161, Invalid=769, Unknown=0, NotChecked=0, Total=930 [2023-12-21 07:21:17,218 INFO L87 Difference]: Start difference. First operand 135 states and 169 transitions. Second operand has 31 states, 31 states have (on average 1.8064516129032258) internal successors, (56), 29 states have internal predecessors, (56), 18 states have call successors, (41), 3 states have call predecessors, (41), 2 states have return successors, (39), 15 states have call predecessors, (39), 16 states have call successors, (39) [2023-12-21 07:25:43,144 WARN L293 SmtUtils]: Spent 4.34m on a formula simplification. DAG size of input: 600 DAG size of output: 157 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:25:45,912 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.84s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:48,796 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.63s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:51,760 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.72s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:56,099 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-21 07:25:58,210 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:02,890 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.79s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] Received shutdown request... [2023-12-21 07:29:57,506 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-21 07:29:57,506 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-21 07:29:58,515 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-21 07:29:58,707 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forcibly destroying the process [2023-12-21 07:29:58,740 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 137 [2023-12-21 07:29:58,741 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-21 07:29:58,741 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 262 GetRequests, 229 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 312.3s TimeCoverageRelationStatistics Valid=192, Invalid=930, Unknown=0, NotChecked=0, Total=1122 [2023-12-21 07:29:58,741 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 30 mSDsluCounter, 353 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 63 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 21.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 384 SdHoareTripleChecker+Invalid, 350 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 21.9s IncrementalHoareTripleChecker+Time [2023-12-21 07:29:58,742 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 384 Invalid, 350 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 286 Invalid, 1 Unknown, 0 Unchecked, 21.9s Time] [2023-12-21 07:29:58,742 INFO L805 garLoopResultBuilder]: Registering result TIMEOUT for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-21 07:29:58,743 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2023-12-21 07:29:58,743 WARN L619 AbstractCegarLoop]: Verification canceled: while NwaCegarLoop was constructing difference of abstraction (135states) and FLOYD_HOARE automaton (currently 12 states, 31 states before enhancement),while PredicateUnifier was unifying predicates,while executing Executor. [2023-12-21 07:29:58,746 INFO L445 BasicCegarLoop]: Path program histogram: [4, 2, 1, 1, 1, 1, 1, 1] [2023-12-21 07:29:58,748 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-21 07:29:58,749 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.12 07:29:58 BoogieIcfgContainer [2023-12-21 07:29:58,750 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-21 07:29:58,750 INFO L158 Benchmark]: Toolchain (without parser) took 871457.81ms. Allocated memory was 286.3MB in the beginning and 343.9MB in the end (delta: 57.7MB). Free memory was 233.2MB in the beginning and 177.0MB in the end (delta: 56.2MB). Peak memory consumption was 191.1MB. Max. memory is 8.0GB. [2023-12-21 07:29:58,750 INFO L158 Benchmark]: CDTParser took 0.49ms. Allocated memory is still 199.2MB. Free memory is still 146.1MB. There was no memory consumed. Max. memory is 8.0GB. [2023-12-21 07:29:58,750 INFO L158 Benchmark]: CACSL2BoogieTranslator took 192.03ms. Allocated memory is still 286.3MB. Free memory was 233.2MB in the beginning and 222.1MB in the end (delta: 11.1MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2023-12-21 07:29:58,751 INFO L158 Benchmark]: Boogie Procedure Inliner took 25.09ms. Allocated memory is still 286.3MB. Free memory was 222.1MB in the beginning and 220.2MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-21 07:29:58,751 INFO L158 Benchmark]: Boogie Preprocessor took 28.17ms. Allocated memory is still 286.3MB. Free memory was 220.2MB in the beginning and 218.5MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-21 07:29:58,751 INFO L158 Benchmark]: RCFGBuilder took 352.02ms. Allocated memory is still 286.3MB. Free memory was 218.5MB in the beginning and 205.9MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2023-12-21 07:29:58,751 INFO L158 Benchmark]: TraceAbstraction took 870855.81ms. Allocated memory was 286.3MB in the beginning and 343.9MB in the end (delta: 57.7MB). Free memory was 205.3MB in the beginning and 177.0MB in the end (delta: 28.3MB). Peak memory consumption was 163.9MB. Max. memory is 8.0GB. [2023-12-21 07:29:58,752 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.49ms. Allocated memory is still 199.2MB. Free memory is still 146.1MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 192.03ms. Allocated memory is still 286.3MB. Free memory was 233.2MB in the beginning and 222.1MB in the end (delta: 11.1MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 25.09ms. Allocated memory is still 286.3MB. Free memory was 222.1MB in the beginning and 220.2MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * Boogie Preprocessor took 28.17ms. Allocated memory is still 286.3MB. Free memory was 220.2MB in the beginning and 218.5MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 352.02ms. Allocated memory is still 286.3MB. Free memory was 218.5MB in the beginning and 205.9MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 870855.81ms. Allocated memory was 286.3MB in the beginning and 343.9MB in the end (delta: 57.7MB). Free memory was 205.3MB in the beginning and 177.0MB in the end (delta: 28.3MB). Peak memory consumption was 163.9MB. 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 - TimeoutResultAtElement [Line: 17]: Timeout (TraceAbstraction) Unable to prove that a call to reach_error is unreachable (line 17). Cancelled while NwaCegarLoop was constructing difference of abstraction (135states) and FLOYD_HOARE automaton (currently 12 states, 31 states before enhancement),while PredicateUnifier was unifying predicates,while executing Executor. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 30 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 870.8s, OverallIterations: 12, TraceHistogramMax: 19, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 567.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 2 mSolverCounterUnknown, 469 SdHoareTripleChecker+Valid, 46.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 427 mSDsluCounter, 2790 SdHoareTripleChecker+Invalid, 46.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2394 mSDsCounter, 451 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2424 IncrementalHoareTripleChecker+Invalid, 2877 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 451 mSolverCounterUnsat, 396 mSDtfsCounter, 2424 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1380 GetRequests, 1182 SyntacticMatches, 0 SemanticMatches, 197 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 771 ImplicationChecksByTransitivity, 341.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=152occurred in iteration=10, InterpolantAutomatonStates: 129, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 11 MinimizatonAttempts, 102 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 300.5s InterpolantComputationTime, 779 NumberOfCodeBlocks, 752 NumberOfCodeBlocksAsserted, 18 NumberOfCheckSat, 1344 ConstructedInterpolants, 0 QuantifiedInterpolants, 55913 SizeOfPredicates, 34 NumberOfNonLiveVariables, 1528 ConjunctsInSsa, 279 ConjunctsInUnsatCore, 19 InterpolantComputations, 4 PerfectInterpolantSequences, 4008/4403 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 could not prove your program: Timeout Completed graceful shutdown