./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version fca748b1 Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound5.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 173419c809fa8cb7fa094fdfc7b5765802a9a2fdebfe9d0a53cd745fd0c573d2 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dd.update-z3-fca748b-m [2024-11-19 21:10:36,044 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 21:10:36,103 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-19 21:10:36,107 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 21:10:36,108 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 21:10:36,132 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 21:10:36,133 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 21:10:36,133 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 21:10:36,134 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 21:10:36,134 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 21:10:36,135 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-19 21:10:36,135 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-19 21:10:36,135 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 21:10:36,137 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 21:10:36,137 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 21:10:36,137 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 21:10:36,138 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-19 21:10:36,138 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-19 21:10:36,138 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 21:10:36,138 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-19 21:10:36,138 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 21:10:36,141 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-19 21:10:36,141 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-19 21:10:36,142 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-19 21:10:36,142 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 21:10:36,142 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-19 21:10:36,142 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 21:10:36,142 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 21:10:36,143 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 21:10:36,143 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 21:10:36,143 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-19 21:10:36,143 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-19 21:10:36,143 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 21:10:36,143 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 21:10:36,143 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-19 21:10:36,144 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-19 21:10:36,144 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 21:10:36,144 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-19 21:10:36,144 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-19 21:10:36,144 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-19 21:10:36,144 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-19 21:10:36,145 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-19 21:10:36,146 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 173419c809fa8cb7fa094fdfc7b5765802a9a2fdebfe9d0a53cd745fd0c573d2 [2024-11-19 21:10:36,384 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 21:10:36,407 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 21:10:36,409 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 21:10:36,410 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 21:10:36,411 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 21:10:36,411 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound5.c [2024-11-19 21:10:37,716 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 21:10:37,861 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 21:10:37,862 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound5.c [2024-11-19 21:10:37,871 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/23fe5d711/9646ef04332f474ca6bb9809fe274769/FLAG220a1bfed [2024-11-19 21:10:38,265 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/23fe5d711/9646ef04332f474ca6bb9809fe274769 [2024-11-19 21:10:38,267 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 21:10:38,268 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 21:10:38,268 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 21:10:38,269 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 21:10:38,272 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 21:10:38,273 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,274 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@11eef7d4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38, skipping insertion in model container [2024-11-19 21:10:38,274 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,288 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 21:10:38,420 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound5.c[588,601] [2024-11-19 21:10:38,445 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 21:10:38,451 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 21:10:38,462 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound5.c[588,601] [2024-11-19 21:10:38,472 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 21:10:38,485 INFO L204 MainTranslator]: Completed translation [2024-11-19 21:10:38,485 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38 WrapperNode [2024-11-19 21:10:38,486 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 21:10:38,487 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 21:10:38,487 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 21:10:38,487 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 21:10:38,492 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,497 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,509 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 49 [2024-11-19 21:10:38,510 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 21:10:38,510 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 21:10:38,510 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 21:10:38,511 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 21:10:38,518 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,518 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,519 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,527 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]. [2024-11-19 21:10:38,527 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,528 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,529 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,531 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,532 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,532 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,534 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 21:10:38,534 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 21:10:38,534 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 21:10:38,534 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 21:10:38,536 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (1/1) ... [2024-11-19 21:10:38,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 21:10:38,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:38,569 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-19 21:10:38,576 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-19 21:10:38,612 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-19 21:10:38,612 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-19 21:10:38,612 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 21:10:38,612 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 21:10:38,613 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-19 21:10:38,613 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-19 21:10:38,654 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 21:10:38,655 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 21:10:38,756 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2024-11-19 21:10:38,757 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 21:10:38,773 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 21:10:38,773 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-19 21:10:38,774 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 09:10:38 BoogieIcfgContainer [2024-11-19 21:10:38,774 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 21:10:38,776 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-19 21:10:38,776 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-19 21:10:38,779 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-19 21:10:38,779 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 09:10:38" (1/3) ... [2024-11-19 21:10:38,780 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@485c3d5b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 09:10:38, skipping insertion in model container [2024-11-19 21:10:38,781 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:10:38" (2/3) ... [2024-11-19 21:10:38,781 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@485c3d5b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 09:10:38, skipping insertion in model container [2024-11-19 21:10:38,781 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 09:10:38" (3/3) ... [2024-11-19 21:10:38,782 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound5.c [2024-11-19 21:10:38,795 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-19 21:10:38,795 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-19 21:10:38,841 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-19 21:10:38,846 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@24d1edc3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-19 21:10:38,846 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-19 21:10:38,850 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 13 states have internal predecessors, (17), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-19 21:10:38,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-19 21:10:38,854 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:38,855 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:38,855 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:38,859 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:38,859 INFO L85 PathProgramCache]: Analyzing trace with hash 1823967074, now seen corresponding path program 1 times [2024-11-19 21:10:38,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:38,891 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1363842107] [2024-11-19 21:10:38,891 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:38,892 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:38,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:39,005 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:10:39,006 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:39,006 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1363842107] [2024-11-19 21:10:39,006 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1363842107] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:10:39,007 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:10:39,007 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-19 21:10:39,008 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1108593570] [2024-11-19 21:10:39,009 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:10:39,012 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-19 21:10:39,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:39,027 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-19 21:10:39,028 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-19 21:10:39,029 INFO L87 Difference]: Start difference. First operand has 26 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 13 states have internal predecessors, (17), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 21:10:39,044 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:39,045 INFO L93 Difference]: Finished difference Result 50 states and 87 transitions. [2024-11-19 21:10:39,046 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-19 21:10:39,047 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-19 21:10:39,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:39,052 INFO L225 Difference]: With dead ends: 50 [2024-11-19 21:10:39,052 INFO L226 Difference]: Without dead ends: 22 [2024-11-19 21:10:39,054 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-19 21:10:39,057 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:39,057 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:10:39,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-19 21:10:39,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-19 21:10:39,086 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 10 states have internal predecessors, (12), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-19 21:10:39,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 33 transitions. [2024-11-19 21:10:39,088 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 33 transitions. Word has length 7 [2024-11-19 21:10:39,088 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:39,088 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 33 transitions. [2024-11-19 21:10:39,089 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 21:10:39,089 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 33 transitions. [2024-11-19 21:10:39,089 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-19 21:10:39,089 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:39,090 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:39,090 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-19 21:10:39,090 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:39,091 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:39,091 INFO L85 PathProgramCache]: Analyzing trace with hash 178926099, now seen corresponding path program 1 times [2024-11-19 21:10:39,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:39,091 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2123097599] [2024-11-19 21:10:39,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:39,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:39,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:39,152 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:10:39,153 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:39,153 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2123097599] [2024-11-19 21:10:39,153 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2123097599] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:10:39,153 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:10:39,153 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-19 21:10:39,153 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1816506334] [2024-11-19 21:10:39,154 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:10:39,154 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-19 21:10:39,155 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:39,155 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-19 21:10:39,155 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-19 21:10:39,156 INFO L87 Difference]: Start difference. First operand 22 states and 33 transitions. Second operand has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 21:10:39,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:39,177 INFO L93 Difference]: Finished difference Result 36 states and 52 transitions. [2024-11-19 21:10:39,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-19 21:10:39,178 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-19 21:10:39,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:39,178 INFO L225 Difference]: With dead ends: 36 [2024-11-19 21:10:39,178 INFO L226 Difference]: Without dead ends: 24 [2024-11-19 21:10:39,179 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-19 21:10:39,180 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:39,180 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 89 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:10:39,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-19 21:10:39,189 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-19 21:10:39,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 12 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-19 21:10:39,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 35 transitions. [2024-11-19 21:10:39,190 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 35 transitions. Word has length 8 [2024-11-19 21:10:39,190 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:39,190 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 35 transitions. [2024-11-19 21:10:39,191 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 21:10:39,191 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 35 transitions. [2024-11-19 21:10:39,191 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-19 21:10:39,191 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:39,191 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:39,191 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-19 21:10:39,192 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:39,192 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:39,192 INFO L85 PathProgramCache]: Analyzing trace with hash 180475231, now seen corresponding path program 1 times [2024-11-19 21:10:39,192 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:39,193 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [287327190] [2024-11-19 21:10:39,193 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:39,193 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:39,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:39,317 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:10:39,317 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:39,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [287327190] [2024-11-19 21:10:39,318 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [287327190] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:10:39,318 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:10:39,318 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:10:39,318 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [104408053] [2024-11-19 21:10:39,318 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:10:39,319 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:10:39,319 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:39,319 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:10:39,319 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:10:39,320 INFO L87 Difference]: Start difference. First operand 24 states and 35 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 21:10:39,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:39,377 INFO L93 Difference]: Finished difference Result 30 states and 40 transitions. [2024-11-19 21:10:39,377 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:10:39,377 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-19 21:10:39,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:39,378 INFO L225 Difference]: With dead ends: 30 [2024-11-19 21:10:39,378 INFO L226 Difference]: Without dead ends: 28 [2024-11-19 21:10:39,379 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:10:39,380 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 5 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:39,380 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 85 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:10:39,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-19 21:10:39,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-19 21:10:39,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-19 21:10:39,389 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 38 transitions. [2024-11-19 21:10:39,390 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 38 transitions. Word has length 8 [2024-11-19 21:10:39,390 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:39,390 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 38 transitions. [2024-11-19 21:10:39,390 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 21:10:39,390 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 38 transitions. [2024-11-19 21:10:39,391 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-19 21:10:39,391 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:39,391 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:39,391 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-19 21:10:39,391 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:39,392 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:39,392 INFO L85 PathProgramCache]: Analyzing trace with hash -1275442234, now seen corresponding path program 1 times [2024-11-19 21:10:39,392 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:39,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1217589344] [2024-11-19 21:10:39,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:39,393 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:39,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:39,405 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [510175999] [2024-11-19 21:10:39,405 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:39,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:39,405 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:39,407 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:39,410 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-19 21:10:39,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:39,444 INFO L255 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 21:10:39,447 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:39,511 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:10:39,511 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:10:39,512 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:39,512 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1217589344] [2024-11-19 21:10:39,512 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:39,512 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [510175999] [2024-11-19 21:10:39,513 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [510175999] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:10:39,513 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:10:39,513 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:10:39,513 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1260079871] [2024-11-19 21:10:39,513 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:10:39,513 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:10:39,513 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:39,514 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:10:39,514 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:10:39,514 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), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 21:10:39,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:39,559 INFO L93 Difference]: Finished difference Result 46 states and 66 transitions. [2024-11-19 21:10:39,559 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:10:39,559 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2024-11-19 21:10:39,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:39,573 INFO L225 Difference]: With dead ends: 46 [2024-11-19 21:10:39,573 INFO L226 Difference]: Without dead ends: 44 [2024-11-19 21:10:39,573 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:10:39,574 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 4 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:39,575 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 120 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:10:39,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-19 21:10:39,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 34. [2024-11-19 21:10:39,611 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-19 21:10:39,612 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 45 transitions. [2024-11-19 21:10:39,612 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 45 transitions. Word has length 13 [2024-11-19 21:10:39,612 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:39,613 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 45 transitions. [2024-11-19 21:10:39,613 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 21:10:39,613 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 45 transitions. [2024-11-19 21:10:39,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-19 21:10:39,613 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:39,613 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:39,622 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-19 21:10:39,814 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:39,817 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:39,818 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:39,818 INFO L85 PathProgramCache]: Analyzing trace with hash 427545983, now seen corresponding path program 1 times [2024-11-19 21:10:39,818 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:39,818 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1644844941] [2024-11-19 21:10:39,818 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:39,818 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:39,835 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:39,836 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1210863900] [2024-11-19 21:10:39,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:39,836 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:39,836 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:39,839 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:39,844 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-19 21:10:39,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:39,876 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 21:10:39,877 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:39,912 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-19 21:10:39,912 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:10:39,912 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:39,912 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1644844941] [2024-11-19 21:10:39,913 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:39,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1210863900] [2024-11-19 21:10:39,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1210863900] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:10:39,913 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:10:39,913 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:10:39,913 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754088589] [2024-11-19 21:10:39,913 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:10:39,913 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:10:39,914 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:39,914 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:10:39,914 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:10:39,914 INFO L87 Difference]: Start difference. First operand 34 states and 45 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-19 21:10:39,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:39,967 INFO L93 Difference]: Finished difference Result 50 states and 69 transitions. [2024-11-19 21:10:39,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:10:39,967 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-11-19 21:10:39,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:39,968 INFO L225 Difference]: With dead ends: 50 [2024-11-19 21:10:39,968 INFO L226 Difference]: Without dead ends: 48 [2024-11-19 21:10:39,969 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:10:39,969 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 4 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 129 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 [2024-11-19 21:10:39,969 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 129 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:10:39,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-19 21:10:39,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 44. [2024-11-19 21:10:39,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-19 21:10:39,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 60 transitions. [2024-11-19 21:10:39,982 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 60 transitions. Word has length 18 [2024-11-19 21:10:39,982 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:39,982 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 60 transitions. [2024-11-19 21:10:39,982 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-19 21:10:39,982 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 60 transitions. [2024-11-19 21:10:39,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-19 21:10:39,983 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:39,983 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:39,991 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-19 21:10:40,186 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:40,187 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:40,188 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:40,188 INFO L85 PathProgramCache]: Analyzing trace with hash 5607206, now seen corresponding path program 1 times [2024-11-19 21:10:40,188 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:40,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [23422523] [2024-11-19 21:10:40,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:40,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:40,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:40,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [250558531] [2024-11-19 21:10:40,212 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:40,212 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:40,212 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:40,215 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:40,216 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-19 21:10:40,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,248 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-19 21:10:40,249 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:40,346 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-19 21:10:40,347 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:10:40,347 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:40,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [23422523] [2024-11-19 21:10:40,347 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:40,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [250558531] [2024-11-19 21:10:40,347 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [250558531] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:10:40,347 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:10:40,347 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:10:40,347 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1345684904] [2024-11-19 21:10:40,347 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:10:40,348 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:10:40,348 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:40,348 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:10:40,348 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:10:40,351 INFO L87 Difference]: Start difference. First operand 44 states and 60 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-19 21:10:40,424 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:40,425 INFO L93 Difference]: Finished difference Result 58 states and 75 transitions. [2024-11-19 21:10:40,425 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:10:40,425 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (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 [2024-11-19 21:10:40,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:40,426 INFO L225 Difference]: With dead ends: 58 [2024-11-19 21:10:40,426 INFO L226 Difference]: Without dead ends: 46 [2024-11-19 21:10:40,427 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:10:40,427 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:40,428 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 115 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:40,428 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-19 21:10:40,435 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2024-11-19 21:10:40,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 24 states have (on average 1.125) internal successors, (27), 25 states have internal predecessors, (27), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-19 21:10:40,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 58 transitions. [2024-11-19 21:10:40,438 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 58 transitions. Word has length 23 [2024-11-19 21:10:40,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:40,438 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 58 transitions. [2024-11-19 21:10:40,438 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-19 21:10:40,438 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 58 transitions. [2024-11-19 21:10:40,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-19 21:10:40,439 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:40,439 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:40,448 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-19 21:10:40,640 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:40,640 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:40,641 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:40,641 INFO L85 PathProgramCache]: Analyzing trace with hash -1172224904, now seen corresponding path program 1 times [2024-11-19 21:10:40,641 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:40,641 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [637273522] [2024-11-19 21:10:40,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:40,642 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:40,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,710 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-19 21:10:40,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,715 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-19 21:10:40,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-19 21:10:40,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,722 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-11-19 21:10:40,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,726 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-19 21:10:40,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,730 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-11-19 21:10:40,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,733 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-19 21:10:40,733 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:40,733 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [637273522] [2024-11-19 21:10:40,733 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [637273522] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:10:40,734 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [53948627] [2024-11-19 21:10:40,734 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:40,734 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:40,734 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:40,736 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:40,737 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-19 21:10:40,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:40,771 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-19 21:10:40,773 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:40,818 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 30 proven. 2 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2024-11-19 21:10:40,819 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:40,886 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-19 21:10:40,886 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [53948627] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:40,886 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 21:10:40,886 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-19 21:10:40,887 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [665316798] [2024-11-19 21:10:40,887 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:40,887 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-19 21:10:40,887 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:40,887 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-19 21:10:40,888 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-19 21:10:40,888 INFO L87 Difference]: Start difference. First operand 46 states and 58 transitions. Second operand has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2024-11-19 21:10:41,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:41,028 INFO L93 Difference]: Finished difference Result 116 states and 151 transitions. [2024-11-19 21:10:41,028 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-19 21:10:41,029 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) Word has length 41 [2024-11-19 21:10:41,029 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:41,030 INFO L225 Difference]: With dead ends: 116 [2024-11-19 21:10:41,030 INFO L226 Difference]: Without dead ends: 100 [2024-11-19 21:10:41,030 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-19 21:10:41,031 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 51 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:41,031 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 138 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:41,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-19 21:10:41,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 96. [2024-11-19 21:10:41,054 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 47 states have (on average 1.148936170212766) internal successors, (54), 50 states have internal predecessors, (54), 38 states have call successors, (38), 10 states have call predecessors, (38), 10 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-19 21:10:41,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 127 transitions. [2024-11-19 21:10:41,057 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 127 transitions. Word has length 41 [2024-11-19 21:10:41,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:41,058 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 127 transitions. [2024-11-19 21:10:41,058 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2024-11-19 21:10:41,058 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 127 transitions. [2024-11-19 21:10:41,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-19 21:10:41,059 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:41,059 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:41,068 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-19 21:10:41,259 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:41,260 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:41,260 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:41,260 INFO L85 PathProgramCache]: Analyzing trace with hash -680109588, now seen corresponding path program 1 times [2024-11-19 21:10:41,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:41,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [262284876] [2024-11-19 21:10:41,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:41,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:41,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:41,292 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2127251233] [2024-11-19 21:10:41,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:41,292 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:41,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:41,294 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:41,297 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-19 21:10:41,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:41,336 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-19 21:10:41,338 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:41,431 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 11 proven. 20 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-19 21:10:41,431 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:41,565 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-19 21:10:41,567 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:41,567 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [262284876] [2024-11-19 21:10:41,568 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:41,568 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2127251233] [2024-11-19 21:10:41,568 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2127251233] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:41,568 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:10:41,568 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-11-19 21:10:41,568 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [358489801] [2024-11-19 21:10:41,568 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:41,569 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-19 21:10:41,569 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:41,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-19 21:10:41,569 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=121, Unknown=0, NotChecked=0, Total=156 [2024-11-19 21:10:41,570 INFO L87 Difference]: Start difference. First operand 96 states and 127 transitions. Second operand has 13 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-19 21:10:41,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:41,756 INFO L93 Difference]: Finished difference Result 114 states and 143 transitions. [2024-11-19 21:10:41,756 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 21:10:41,757 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 41 [2024-11-19 21:10:41,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:41,758 INFO L225 Difference]: With dead ends: 114 [2024-11-19 21:10:41,758 INFO L226 Difference]: Without dead ends: 112 [2024-11-19 21:10:41,758 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2024-11-19 21:10:41,759 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 14 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 243 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:41,759 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 164 Invalid, 243 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:41,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2024-11-19 21:10:41,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 112. [2024-11-19 21:10:41,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 59 states have (on average 1.11864406779661) internal successors, (66), 62 states have internal predecessors, (66), 38 states have call successors, (38), 14 states have call predecessors, (38), 14 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-19 21:10:41,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 139 transitions. [2024-11-19 21:10:41,777 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 139 transitions. Word has length 41 [2024-11-19 21:10:41,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:41,777 INFO L471 AbstractCegarLoop]: Abstraction has 112 states and 139 transitions. [2024-11-19 21:10:41,778 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-19 21:10:41,778 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 139 transitions. [2024-11-19 21:10:41,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-19 21:10:41,778 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:41,779 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:41,787 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-19 21:10:41,979 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:41,980 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:41,980 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:41,980 INFO L85 PathProgramCache]: Analyzing trace with hash -399462631, now seen corresponding path program 2 times [2024-11-19 21:10:41,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:41,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2076395691] [2024-11-19 21:10:41,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:41,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:41,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:41,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1988871774] [2024-11-19 21:10:41,993 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:10:41,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:41,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:41,995 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:41,996 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-19 21:10:42,043 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:10:42,043 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:10:42,044 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-19 21:10:42,046 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:42,164 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 28 proven. 9 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-19 21:10:42,164 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:42,298 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 28 proven. 9 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-19 21:10:42,298 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:42,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2076395691] [2024-11-19 21:10:42,298 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:42,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1988871774] [2024-11-19 21:10:42,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1988871774] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:42,299 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:10:42,299 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2024-11-19 21:10:42,299 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1608918719] [2024-11-19 21:10:42,299 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:42,299 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-19 21:10:42,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:42,300 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-19 21:10:42,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-11-19 21:10:42,300 INFO L87 Difference]: Start difference. First operand 112 states and 139 transitions. Second operand has 14 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 11 states have internal predecessors, (26), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-19 21:10:42,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:42,510 INFO L93 Difference]: Finished difference Result 127 states and 154 transitions. [2024-11-19 21:10:42,511 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-19 21:10:42,511 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 11 states have internal predecessors, (26), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) Word has length 46 [2024-11-19 21:10:42,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:42,513 INFO L225 Difference]: With dead ends: 127 [2024-11-19 21:10:42,513 INFO L226 Difference]: Without dead ends: 122 [2024-11-19 21:10:42,513 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=68, Invalid=238, Unknown=0, NotChecked=0, Total=306 [2024-11-19 21:10:42,514 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 14 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 134 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 134 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:42,514 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 110 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 134 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:42,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-19 21:10:42,534 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 121. [2024-11-19 21:10:42,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 71 states have internal predecessors, (75), 35 states have call successors, (35), 17 states have call predecessors, (35), 17 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-19 21:10:42,535 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 142 transitions. [2024-11-19 21:10:42,536 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 142 transitions. Word has length 46 [2024-11-19 21:10:42,536 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:42,536 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 142 transitions. [2024-11-19 21:10:42,536 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 11 states have internal predecessors, (26), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-19 21:10:42,536 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 142 transitions. [2024-11-19 21:10:42,537 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-19 21:10:42,537 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:42,537 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:42,544 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-19 21:10:42,738 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:42,738 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:42,739 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:42,739 INFO L85 PathProgramCache]: Analyzing trace with hash 616227619, now seen corresponding path program 1 times [2024-11-19 21:10:42,739 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:42,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1310833429] [2024-11-19 21:10:42,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:42,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:42,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:42,769 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [424547942] [2024-11-19 21:10:42,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:42,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:42,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:42,771 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:42,772 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-19 21:10:42,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:42,807 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-19 21:10:42,809 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:42,980 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 22 proven. 8 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-19 21:10:42,981 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:43,120 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 22 proven. 8 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-19 21:10:43,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:43,121 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1310833429] [2024-11-19 21:10:43,121 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:43,121 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [424547942] [2024-11-19 21:10:43,121 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [424547942] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:43,121 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:10:43,121 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2024-11-19 21:10:43,121 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [14697402] [2024-11-19 21:10:43,121 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:43,121 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-19 21:10:43,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:43,122 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-19 21:10:43,122 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-19 21:10:43,122 INFO L87 Difference]: Start difference. First operand 121 states and 142 transitions. Second operand has 12 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (24), 3 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-19 21:10:43,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:43,304 INFO L93 Difference]: Finished difference Result 135 states and 154 transitions. [2024-11-19 21:10:43,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 21:10:43,305 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (24), 3 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) Word has length 67 [2024-11-19 21:10:43,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:43,306 INFO L225 Difference]: With dead ends: 135 [2024-11-19 21:10:43,306 INFO L226 Difference]: Without dead ends: 131 [2024-11-19 21:10:43,306 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 122 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2024-11-19 21:10:43,307 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 5 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 188 SdHoareTripleChecker+Invalid, 145 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:43,307 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 188 Invalid, 145 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:43,307 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2024-11-19 21:10:43,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 131. [2024-11-19 21:10:43,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 76 states have (on average 1.0789473684210527) internal successors, (82), 78 states have internal predecessors, (82), 35 states have call successors, (35), 20 states have call predecessors, (35), 19 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-19 21:10:43,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 149 transitions. [2024-11-19 21:10:43,329 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 149 transitions. Word has length 67 [2024-11-19 21:10:43,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:43,329 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 149 transitions. [2024-11-19 21:10:43,329 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 6 states have call successors, (24), 3 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-19 21:10:43,330 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 149 transitions. [2024-11-19 21:10:43,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-19 21:10:43,330 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:43,330 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:43,337 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-19 21:10:43,534 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:43,535 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:43,535 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:43,535 INFO L85 PathProgramCache]: Analyzing trace with hash 1808123650, now seen corresponding path program 1 times [2024-11-19 21:10:43,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:43,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [348680407] [2024-11-19 21:10:43,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:43,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:43,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:43,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1944506631] [2024-11-19 21:10:43,555 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:43,555 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:43,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:43,557 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:43,558 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-19 21:10:43,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:43,599 INFO L255 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-19 21:10:43,601 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:43,726 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 56 proven. 9 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-19 21:10:43,726 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:43,803 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:43,804 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [348680407] [2024-11-19 21:10:43,804 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:43,804 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1944506631] [2024-11-19 21:10:43,804 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1944506631] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:10:43,804 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-19 21:10:43,804 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-19 21:10:43,804 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [691463971] [2024-11-19 21:10:43,804 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:43,805 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-19 21:10:43,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:43,805 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-19 21:10:43,805 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-19 21:10:43,805 INFO L87 Difference]: Start difference. First operand 131 states and 149 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-19 21:10:44,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:44,005 INFO L93 Difference]: Finished difference Result 137 states and 153 transitions. [2024-11-19 21:10:44,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 21:10:44,006 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) Word has length 72 [2024-11-19 21:10:44,006 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:44,010 INFO L225 Difference]: With dead ends: 137 [2024-11-19 21:10:44,010 INFO L226 Difference]: Without dead ends: 126 [2024-11-19 21:10:44,010 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 66 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2024-11-19 21:10:44,011 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 3 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 204 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:44,011 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 161 Invalid, 204 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:44,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-11-19 21:10:44,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 126. [2024-11-19 21:10:44,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 74 states have (on average 1.0675675675675675) internal successors, (79), 76 states have internal predecessors, (79), 32 states have call successors, (32), 19 states have call predecessors, (32), 19 states have return successors, (30), 30 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-19 21:10:44,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 141 transitions. [2024-11-19 21:10:44,058 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 141 transitions. Word has length 72 [2024-11-19 21:10:44,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:44,059 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 141 transitions. [2024-11-19 21:10:44,059 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 3 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-19 21:10:44,059 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 141 transitions. [2024-11-19 21:10:44,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-19 21:10:44,060 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:44,060 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-19 21:10:44,077 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-19 21:10:44,264 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-19 21:10:44,265 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:44,265 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:44,265 INFO L85 PathProgramCache]: Analyzing trace with hash 514910066, now seen corresponding path program 3 times [2024-11-19 21:10:44,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:44,266 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1134020535] [2024-11-19 21:10:44,266 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:44,266 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:44,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:44,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1699592432] [2024-11-19 21:10:44,299 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 21:10:44,299 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:44,299 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:44,302 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:44,305 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-19 21:10:44,372 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-19 21:10:44,372 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:10:44,373 INFO L255 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-19 21:10:44,375 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:44,549 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-19 21:10:44,550 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:44,831 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-19 21:10:44,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:44,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1134020535] [2024-11-19 21:10:44,832 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:44,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1699592432] [2024-11-19 21:10:44,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1699592432] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:44,832 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:10:44,832 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2024-11-19 21:10:44,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [643800422] [2024-11-19 21:10:44,833 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:44,833 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-19 21:10:44,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:44,834 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-19 21:10:44,836 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=188, Unknown=0, NotChecked=0, Total=240 [2024-11-19 21:10:44,836 INFO L87 Difference]: Start difference. First operand 126 states and 141 transitions. Second operand has 16 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-19 21:10:50,608 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 5.51s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-19 21:10:50,749 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:50,749 INFO L93 Difference]: Finished difference Result 138 states and 154 transitions. [2024-11-19 21:10:50,750 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-19 21:10:50,750 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) Word has length 79 [2024-11-19 21:10:50,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:50,751 INFO L225 Difference]: With dead ends: 138 [2024-11-19 21:10:50,752 INFO L226 Difference]: Without dead ends: 129 [2024-11-19 21:10:50,752 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 142 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=80, Invalid=262, Unknown=0, NotChecked=0, Total=342 [2024-11-19 21:10:50,752 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 16 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 270 mSolverCounterSat, 67 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 240 SdHoareTripleChecker+Invalid, 338 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 270 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.8s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:50,753 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 240 Invalid, 338 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 270 Invalid, 1 Unknown, 0 Unchecked, 5.8s Time] [2024-11-19 21:10:50,753 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2024-11-19 21:10:50,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 127. [2024-11-19 21:10:50,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 79 states have (on average 1.0506329113924051) internal successors, (83), 80 states have internal predecessors, (83), 27 states have call successors, (27), 21 states have call predecessors, (27), 20 states have return successors, (25), 25 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-19 21:10:50,769 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 135 transitions. [2024-11-19 21:10:50,769 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 135 transitions. Word has length 79 [2024-11-19 21:10:50,769 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:50,769 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 135 transitions. [2024-11-19 21:10:50,769 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-19 21:10:50,770 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 135 transitions. [2024-11-19 21:10:50,770 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-19 21:10:50,770 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:50,771 INFO L215 NwaCegarLoop]: trace histogram [18, 17, 17, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:50,777 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-19 21:10:50,974 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:50,975 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:50,975 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:50,975 INFO L85 PathProgramCache]: Analyzing trace with hash 75049244, now seen corresponding path program 2 times [2024-11-19 21:10:50,975 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:50,976 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1564245541] [2024-11-19 21:10:50,976 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:50,976 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:51,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:51,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2071902388] [2024-11-19 21:10:51,003 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:10:51,003 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:51,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:51,009 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:51,010 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-19 21:10:51,057 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:10:51,057 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:10:51,062 INFO L255 TraceCheckSpWp]: Trace formula consists of 229 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-19 21:10:51,064 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:51,240 INFO L134 CoverageAnalysis]: Checked inductivity of 602 backedges. 63 proven. 43 refuted. 0 times theorem prover too weak. 496 trivial. 0 not checked. [2024-11-19 21:10:51,240 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:51,506 INFO L134 CoverageAnalysis]: Checked inductivity of 602 backedges. 63 proven. 35 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2024-11-19 21:10:51,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:51,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1564245541] [2024-11-19 21:10:51,506 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:51,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2071902388] [2024-11-19 21:10:51,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2071902388] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:51,506 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:10:51,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2024-11-19 21:10:51,507 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [447808491] [2024-11-19 21:10:51,507 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:51,507 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-19 21:10:51,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:51,508 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-19 21:10:51,508 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-19 21:10:51,508 INFO L87 Difference]: Start difference. First operand 127 states and 135 transitions. Second operand has 17 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (29), 7 states have call predecessors, (29), 9 states have call successors, (29) [2024-11-19 21:10:51,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:51,764 INFO L93 Difference]: Finished difference Result 137 states and 148 transitions. [2024-11-19 21:10:51,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-19 21:10:51,764 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (29), 7 states have call predecessors, (29), 9 states have call successors, (29) Word has length 100 [2024-11-19 21:10:51,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:51,765 INFO L225 Difference]: With dead ends: 137 [2024-11-19 21:10:51,765 INFO L226 Difference]: Without dead ends: 126 [2024-11-19 21:10:51,766 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 182 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=102, Invalid=360, Unknown=0, NotChecked=0, Total=462 [2024-11-19 21:10:51,766 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 10 mSDsluCounter, 206 mSDsCounter, 0 mSdLazyCounter, 222 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 258 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 222 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:51,766 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 236 Invalid, 258 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 222 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:51,767 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-11-19 21:10:51,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 125. [2024-11-19 21:10:51,782 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 77 states have (on average 1.0389610389610389) internal successors, (80), 79 states have internal predecessors, (80), 27 states have call successors, (27), 20 states have call predecessors, (27), 20 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-19 21:10:51,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 133 transitions. [2024-11-19 21:10:51,783 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 133 transitions. Word has length 100 [2024-11-19 21:10:51,783 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:51,783 INFO L471 AbstractCegarLoop]: Abstraction has 125 states and 133 transitions. [2024-11-19 21:10:51,783 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (29), 7 states have call predecessors, (29), 9 states have call successors, (29) [2024-11-19 21:10:51,783 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 133 transitions. [2024-11-19 21:10:51,784 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2024-11-19 21:10:51,784 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:51,784 INFO L215 NwaCegarLoop]: trace histogram [22, 21, 21, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:51,790 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-19 21:10:51,990 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-19 21:10:51,990 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:51,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:51,991 INFO L85 PathProgramCache]: Analyzing trace with hash -1859389073, now seen corresponding path program 2 times [2024-11-19 21:10:51,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:51,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350771729] [2024-11-19 21:10:51,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:51,992 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:52,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:52,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [723209105] [2024-11-19 21:10:52,020 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:10:52,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:52,021 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:52,022 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:52,023 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-19 21:10:52,070 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:10:52,070 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:10:52,071 INFO L255 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-19 21:10:52,073 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:52,206 INFO L134 CoverageAnalysis]: Checked inductivity of 930 backedges. 86 proven. 64 refuted. 0 times theorem prover too weak. 780 trivial. 0 not checked. [2024-11-19 21:10:52,206 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:52,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:52,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350771729] [2024-11-19 21:10:52,236 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:52,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [723209105] [2024-11-19 21:10:52,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [723209105] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:10:52,236 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-19 21:10:52,237 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2024-11-19 21:10:52,237 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1728809594] [2024-11-19 21:10:52,237 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:52,237 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-19 21:10:52,237 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:52,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-19 21:10:52,237 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2024-11-19 21:10:52,238 INFO L87 Difference]: Start difference. First operand 125 states and 133 transitions. Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 5 states have call predecessors, (21), 5 states have call successors, (21) [2024-11-19 21:10:52,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:52,466 INFO L93 Difference]: Finished difference Result 145 states and 160 transitions. [2024-11-19 21:10:52,467 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-19 21:10:52,467 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 5 states have call predecessors, (21), 5 states have call successors, (21) Word has length 123 [2024-11-19 21:10:52,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:52,468 INFO L225 Difference]: With dead ends: 145 [2024-11-19 21:10:52,468 INFO L226 Difference]: Without dead ends: 143 [2024-11-19 21:10:52,468 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2024-11-19 21:10:52,469 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 4 mSDsluCounter, 259 mSDsCounter, 0 mSdLazyCounter, 375 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 298 SdHoareTripleChecker+Invalid, 385 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 375 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:52,469 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 298 Invalid, 385 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 375 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 21:10:52,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-19 21:10:52,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 141. [2024-11-19 21:10:52,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 84 states have (on average 1.0476190476190477) internal successors, (88), 87 states have internal predecessors, (88), 34 states have call successors, (34), 22 states have call predecessors, (34), 22 states have return successors, (33), 31 states have call predecessors, (33), 33 states have call successors, (33) [2024-11-19 21:10:52,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 155 transitions. [2024-11-19 21:10:52,490 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 155 transitions. Word has length 123 [2024-11-19 21:10:52,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:52,490 INFO L471 AbstractCegarLoop]: Abstraction has 141 states and 155 transitions. [2024-11-19 21:10:52,490 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 5 states have call predecessors, (21), 5 states have call successors, (21) [2024-11-19 21:10:52,491 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 155 transitions. [2024-11-19 21:10:52,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 126 [2024-11-19 21:10:52,491 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:52,491 INFO L215 NwaCegarLoop]: trace histogram [22, 21, 21, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:52,498 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-19 21:10:52,692 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-19 21:10:52,692 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:52,693 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:52,693 INFO L85 PathProgramCache]: Analyzing trace with hash -1602424598, now seen corresponding path program 2 times [2024-11-19 21:10:52,693 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:52,693 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1099901295] [2024-11-19 21:10:52,693 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:52,693 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:52,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,891 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-19 21:10:52,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,894 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-19 21:10:52,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,896 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-19 21:10:52,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,898 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-11-19 21:10:52,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,900 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-19 21:10:52,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,902 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-11-19 21:10:52,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,904 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-11-19 21:10:52,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,906 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-19 21:10:52,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,908 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-19 21:10:52,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,910 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-19 21:10:52,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,913 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-19 21:10:52,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,914 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-19 21:10:52,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,916 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-19 21:10:52,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,918 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2024-11-19 21:10:52,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,920 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 80 [2024-11-19 21:10:52,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,922 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-11-19 21:10:52,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,924 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-11-19 21:10:52,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,926 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 98 [2024-11-19 21:10:52,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,928 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 103 [2024-11-19 21:10:52,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,930 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 108 [2024-11-19 21:10:52,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,932 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 116 [2024-11-19 21:10:52,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:52,934 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2024-11-19 21:10:52,934 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:52,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1099901295] [2024-11-19 21:10:52,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1099901295] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:10:52,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [449476248] [2024-11-19 21:10:52,934 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:10:52,934 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:52,934 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:52,936 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:52,943 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-19 21:10:52,992 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:10:52,992 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:10:52,993 INFO L255 TraceCheckSpWp]: Trace formula consists of 292 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-19 21:10:52,995 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:53,089 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 120 proven. 656 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2024-11-19 21:10:53,089 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:53,185 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2024-11-19 21:10:53,186 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [449476248] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:53,186 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 21:10:53,186 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 8 [2024-11-19 21:10:53,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1090038987] [2024-11-19 21:10:53,186 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:53,187 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-19 21:10:53,187 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:53,187 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-19 21:10:53,187 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2024-11-19 21:10:53,187 INFO L87 Difference]: Start difference. First operand 141 states and 155 transitions. Second operand has 8 states, 8 states have (on average 4.5) internal successors, (36), 8 states have internal predecessors, (36), 5 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 5 states have call predecessors, (42), 5 states have call successors, (42) [2024-11-19 21:10:53,293 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:53,293 INFO L93 Difference]: Finished difference Result 181 states and 193 transitions. [2024-11-19 21:10:53,294 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-19 21:10:53,294 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.5) internal successors, (36), 8 states have internal predecessors, (36), 5 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 5 states have call predecessors, (42), 5 states have call successors, (42) Word has length 125 [2024-11-19 21:10:53,294 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:53,295 INFO L225 Difference]: With dead ends: 181 [2024-11-19 21:10:53,295 INFO L226 Difference]: Without dead ends: 165 [2024-11-19 21:10:53,295 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 301 GetRequests, 285 SyntacticMatches, 6 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2024-11-19 21:10:53,295 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 10 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:53,296 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 103 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:53,296 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2024-11-19 21:10:53,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 163. [2024-11-19 21:10:53,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 100 states have (on average 1.04) internal successors, (104), 102 states have internal predecessors, (104), 36 states have call successors, (36), 27 states have call predecessors, (36), 26 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-19 21:10:53,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 174 transitions. [2024-11-19 21:10:53,317 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 174 transitions. Word has length 125 [2024-11-19 21:10:53,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:53,318 INFO L471 AbstractCegarLoop]: Abstraction has 163 states and 174 transitions. [2024-11-19 21:10:53,318 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.5) internal successors, (36), 8 states have internal predecessors, (36), 5 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 5 states have call predecessors, (42), 5 states have call successors, (42) [2024-11-19 21:10:53,318 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 174 transitions. [2024-11-19 21:10:53,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 134 [2024-11-19 21:10:53,319 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:53,319 INFO L215 NwaCegarLoop]: trace histogram [24, 23, 23, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:53,325 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-19 21:10:53,523 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-19 21:10:53,524 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:53,524 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:53,524 INFO L85 PathProgramCache]: Analyzing trace with hash 36255119, now seen corresponding path program 1 times [2024-11-19 21:10:53,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:53,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1061395184] [2024-11-19 21:10:53,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:53,525 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:53,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:53,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1827547473] [2024-11-19 21:10:53,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:53,550 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:53,550 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:53,552 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:53,557 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-19 21:10:53,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:10:53,611 INFO L255 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-19 21:10:53,613 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:53,856 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 45 proven. 115 refuted. 0 times theorem prover too weak. 946 trivial. 0 not checked. [2024-11-19 21:10:53,856 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:54,588 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 45 proven. 115 refuted. 0 times theorem prover too weak. 946 trivial. 0 not checked. [2024-11-19 21:10:54,589 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:54,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1061395184] [2024-11-19 21:10:54,589 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:54,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1827547473] [2024-11-19 21:10:54,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1827547473] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:54,589 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:10:54,589 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2024-11-19 21:10:54,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2004255665] [2024-11-19 21:10:54,590 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:54,590 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-19 21:10:54,590 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:54,590 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-19 21:10:54,591 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-19 21:10:54,591 INFO L87 Difference]: Start difference. First operand 163 states and 174 transitions. Second operand has 17 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 9 states have call successors, (48), 3 states have call predecessors, (48), 2 states have return successors, (46), 8 states have call predecessors, (46), 9 states have call successors, (46) [2024-11-19 21:10:56,438 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.42s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-19 21:10:56,899 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:56,900 INFO L93 Difference]: Finished difference Result 177 states and 185 transitions. [2024-11-19 21:10:56,900 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-19 21:10:56,900 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 9 states have call successors, (48), 3 states have call predecessors, (48), 2 states have return successors, (46), 8 states have call predecessors, (46), 9 states have call successors, (46) Word has length 133 [2024-11-19 21:10:56,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:56,901 INFO L225 Difference]: With dead ends: 177 [2024-11-19 21:10:56,901 INFO L226 Difference]: Without dead ends: 151 [2024-11-19 21:10:56,901 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 266 GetRequests, 249 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2024-11-19 21:10:56,902 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 14 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 317 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 292 SdHoareTripleChecker+Invalid, 353 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 317 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:56,902 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 292 Invalid, 353 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 317 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-19 21:10:56,902 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2024-11-19 21:10:56,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 151. [2024-11-19 21:10:56,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 95 states have (on average 1.0315789473684212) internal successors, (98), 97 states have internal predecessors, (98), 30 states have call successors, (30), 25 states have call predecessors, (30), 25 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2024-11-19 21:10:56,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 156 transitions. [2024-11-19 21:10:56,940 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 156 transitions. Word has length 133 [2024-11-19 21:10:56,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:56,941 INFO L471 AbstractCegarLoop]: Abstraction has 151 states and 156 transitions. [2024-11-19 21:10:56,941 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 9 states have call successors, (48), 3 states have call predecessors, (48), 2 states have return successors, (46), 8 states have call predecessors, (46), 9 states have call successors, (46) [2024-11-19 21:10:56,941 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 156 transitions. [2024-11-19 21:10:56,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 152 [2024-11-19 21:10:56,942 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:56,942 INFO L215 NwaCegarLoop]: trace histogram [27, 26, 26, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:56,948 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-19 21:10:57,144 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-19 21:10:57,145 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:57,145 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:57,145 INFO L85 PathProgramCache]: Analyzing trace with hash 2091975957, now seen corresponding path program 3 times [2024-11-19 21:10:57,145 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:57,145 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1000540490] [2024-11-19 21:10:57,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:57,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:57,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:57,173 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1485265651] [2024-11-19 21:10:57,173 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 21:10:57,173 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:57,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:57,175 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:57,180 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-19 21:10:57,218 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-19 21:10:57,218 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:10:57,218 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-19 21:10:57,220 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:10:57,265 INFO L134 CoverageAnalysis]: Checked inductivity of 1432 backedges. 158 proven. 1 refuted. 0 times theorem prover too weak. 1273 trivial. 0 not checked. [2024-11-19 21:10:57,266 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:10:57,381 INFO L134 CoverageAnalysis]: Checked inductivity of 1432 backedges. 158 proven. 1 refuted. 0 times theorem prover too weak. 1273 trivial. 0 not checked. [2024-11-19 21:10:57,381 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:10:57,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1000540490] [2024-11-19 21:10:57,381 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:10:57,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1485265651] [2024-11-19 21:10:57,381 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1485265651] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:10:57,382 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:10:57,382 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 11 [2024-11-19 21:10:57,382 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1147322647] [2024-11-19 21:10:57,382 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:10:57,382 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-19 21:10:57,382 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:10:57,383 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-19 21:10:57,383 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-19 21:10:57,383 INFO L87 Difference]: Start difference. First operand 151 states and 156 transitions. Second operand has 11 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 9 states have internal predecessors, (22), 4 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-19 21:10:57,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:10:57,514 INFO L93 Difference]: Finished difference Result 157 states and 161 transitions. [2024-11-19 21:10:57,515 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 21:10:57,515 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 9 states have internal predecessors, (22), 4 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 151 [2024-11-19 21:10:57,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:10:57,517 INFO L225 Difference]: With dead ends: 157 [2024-11-19 21:10:57,517 INFO L226 Difference]: Without dead ends: 149 [2024-11-19 21:10:57,517 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 302 GetRequests, 289 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2024-11-19 21:10:57,518 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 164 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:10:57,518 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 125 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 164 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:10:57,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2024-11-19 21:10:57,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2024-11-19 21:10:57,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 95 states have (on average 1.0210526315789474) internal successors, (97), 96 states have internal predecessors, (97), 28 states have call successors, (28), 25 states have call predecessors, (28), 25 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2024-11-19 21:10:57,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 152 transitions. [2024-11-19 21:10:57,540 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 152 transitions. Word has length 151 [2024-11-19 21:10:57,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:10:57,542 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 152 transitions. [2024-11-19 21:10:57,542 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 9 states have internal predecessors, (22), 4 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-19 21:10:57,542 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 152 transitions. [2024-11-19 21:10:57,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2024-11-19 21:10:57,543 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:10:57,543 INFO L215 NwaCegarLoop]: trace histogram [27, 26, 26, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:57,553 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-19 21:10:57,747 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:57,747 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:10:57,748 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:10:57,748 INFO L85 PathProgramCache]: Analyzing trace with hash -1091720432, now seen corresponding path program 3 times [2024-11-19 21:10:57,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:10:57,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [688258235] [2024-11-19 21:10:57,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:10:57,748 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:10:57,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:10:57,774 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1346344657] [2024-11-19 21:10:57,774 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 21:10:57,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:10:57,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:10:57,776 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:10:57,777 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-19 21:10:57,916 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 18 check-sat command(s) [2024-11-19 21:10:57,916 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 21:10:57,917 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 21:10:57,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 21:10:57,971 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 21:10:57,972 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-19 21:10:57,972 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-19 21:10:57,980 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-19 21:10:58,177 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-19 21:10:58,180 INFO L407 BasicCegarLoop]: Path program histogram: [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:10:58,214 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-19 21:10:58,215 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 19.11 09:10:58 BoogieIcfgContainer [2024-11-19 21:10:58,215 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-19 21:10:58,216 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-19 21:10:58,216 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-19 21:10:58,216 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-19 21:10:58,218 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 09:10:38" (3/4) ... [2024-11-19 21:10:58,219 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-19 21:10:58,280 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-19 21:10:58,280 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-19 21:10:58,280 INFO L158 Benchmark]: Toolchain (without parser) took 20012.93ms. Allocated memory was 163.6MB in the beginning and 297.8MB in the end (delta: 134.2MB). Free memory was 93.4MB in the beginning and 103.1MB in the end (delta: -9.7MB). Peak memory consumption was 126.1MB. Max. memory is 16.1GB. [2024-11-19 21:10:58,281 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 163.6MB. Free memory is still 115.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-19 21:10:58,281 INFO L158 Benchmark]: CACSL2BoogieTranslator took 217.43ms. Allocated memory is still 163.6MB. Free memory was 93.1MB in the beginning and 80.2MB in the end (delta: 12.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-19 21:10:58,281 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.41ms. Allocated memory is still 163.6MB. Free memory was 80.2MB in the beginning and 78.6MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-19 21:10:58,281 INFO L158 Benchmark]: Boogie Preprocessor took 23.29ms. Allocated memory is still 163.6MB. Free memory was 78.6MB in the beginning and 76.9MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-19 21:10:58,281 INFO L158 Benchmark]: RCFGBuilder took 239.60ms. Allocated memory is still 163.6MB. Free memory was 76.9MB in the beginning and 64.4MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-19 21:10:58,282 INFO L158 Benchmark]: TraceAbstraction took 19439.26ms. Allocated memory was 163.6MB in the beginning and 297.8MB in the end (delta: 134.2MB). Free memory was 63.8MB in the beginning and 108.3MB in the end (delta: -44.6MB). Peak memory consumption was 92.5MB. Max. memory is 16.1GB. [2024-11-19 21:10:58,282 INFO L158 Benchmark]: Witness Printer took 64.42ms. Allocated memory is still 297.8MB. Free memory was 108.3MB in the beginning and 103.1MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-11-19 21:10:58,283 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.13ms. Allocated memory is still 163.6MB. Free memory is still 115.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 217.43ms. Allocated memory is still 163.6MB. Free memory was 93.1MB in the beginning and 80.2MB in the end (delta: 12.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.41ms. Allocated memory is still 163.6MB. Free memory was 80.2MB in the beginning and 78.6MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 23.29ms. Allocated memory is still 163.6MB. Free memory was 78.6MB in the beginning and 76.9MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 239.60ms. Allocated memory is still 163.6MB. Free memory was 76.9MB in the beginning and 64.4MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 19439.26ms. Allocated memory was 163.6MB in the beginning and 297.8MB in the end (delta: 134.2MB). Free memory was 63.8MB in the beginning and 108.3MB in the end (delta: -44.6MB). Peak memory consumption was 92.5MB. Max. memory is 16.1GB. * Witness Printer took 64.42ms. Allocated memory is still 297.8MB. Free memory was 108.3MB in the beginning and 103.1MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; VAL [counter=0] [L24] short a; [L25] long long n, x, y, z; [L26] a = __VERIFIER_nondet_ushort() [L28] n = 0 [L29] x = 0 [L30] y = 1 [L31] z = 6 VAL [a=5, counter=0, n=0, x=0, y=1, z=6] [L33] EXPR counter++ VAL [a=5, counter=1, n=0, x=0, y=1, z=6] [L33] COND TRUE counter++<5 [L34] CALL __VERIFIER_assert(z == 6 * n + 6) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L34] RET __VERIFIER_assert(z == 6 * n + 6) VAL [a=5, counter=1, n=0, x=0, y=1, z=6] [L35] CALL __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L35] RET __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [a=5, counter=1, n=0, x=0, y=1, z=6] [L36] CALL __VERIFIER_assert(x == n * n * n) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L36] RET __VERIFIER_assert(x == n * n * n) VAL [a=5, counter=1, n=0, x=0, y=1, z=6] [L37] CALL __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L37] RET __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [a=5, counter=1, n=0, x=0, y=1, z=6] [L38] CALL __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L38] RET __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [a=5, counter=1, n=0, x=0, y=1, z=6] [L39] COND FALSE !(!(n <= a)) [L42] n = n + 1 [L43] x = x + y [L44] y = y + z [L45] z = z + 6 VAL [a=5, counter=1, n=1, x=1, y=7, z=12] [L33] EXPR counter++ VAL [a=5, counter=2, n=1, x=1, y=7, z=12] [L33] COND TRUE counter++<5 [L34] CALL __VERIFIER_assert(z == 6 * n + 6) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L34] RET __VERIFIER_assert(z == 6 * n + 6) VAL [a=5, counter=2, n=1, x=1, y=7, z=12] [L35] CALL __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L35] RET __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [a=5, counter=2, n=1, x=1, y=7, z=12] [L36] CALL __VERIFIER_assert(x == n * n * n) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L36] RET __VERIFIER_assert(x == n * n * n) VAL [a=5, counter=2, n=1, x=1, y=7, z=12] [L37] CALL __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L37] RET __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [a=5, counter=2, n=1, x=1, y=7, z=12] [L38] CALL __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L38] RET __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [a=5, counter=2, n=1, x=1, y=7, z=12] [L39] COND FALSE !(!(n <= a)) [L42] n = n + 1 [L43] x = x + y [L44] y = y + z [L45] z = z + 6 VAL [a=5, counter=2, n=2, x=8, y=19, z=18] [L33] EXPR counter++ VAL [a=5, counter=3, n=2, x=8, y=19, z=18] [L33] COND TRUE counter++<5 [L34] CALL __VERIFIER_assert(z == 6 * n + 6) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L34] RET __VERIFIER_assert(z == 6 * n + 6) VAL [a=5, counter=3, n=2, x=8, y=19, z=18] [L35] CALL __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L35] RET __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [a=5, counter=3, n=2, x=8, y=19, z=18] [L36] CALL __VERIFIER_assert(x == n * n * n) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L36] RET __VERIFIER_assert(x == n * n * n) VAL [a=5, counter=3, n=2, x=8, y=19, z=18] [L37] CALL __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L37] RET __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [a=5, counter=3, n=2, x=8, y=19, z=18] [L38] CALL __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L38] RET __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [a=5, counter=3, n=2, x=8, y=19, z=18] [L39] COND FALSE !(!(n <= a)) [L42] n = n + 1 [L43] x = x + y [L44] y = y + z [L45] z = z + 6 VAL [a=5, counter=3, n=3, x=27, y=37, z=24] [L33] EXPR counter++ VAL [a=5, counter=4, n=3, x=27, y=37, z=24] [L33] COND TRUE counter++<5 [L34] CALL __VERIFIER_assert(z == 6 * n + 6) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L34] RET __VERIFIER_assert(z == 6 * n + 6) VAL [a=5, counter=4, n=3, x=27, y=37, z=24] [L35] CALL __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L35] RET __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [a=5, counter=4, n=3, x=27, y=37, z=24] [L36] CALL __VERIFIER_assert(x == n * n * n) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L36] RET __VERIFIER_assert(x == n * n * n) VAL [a=5, counter=4, n=3, x=27, y=37, z=24] [L37] CALL __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L37] RET __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [a=5, counter=4, n=3, x=27, y=37, z=24] [L38] CALL __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L38] RET __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [a=5, counter=4, n=3, x=27, y=37, z=24] [L39] COND FALSE !(!(n <= a)) [L42] n = n + 1 [L43] x = x + y [L44] y = y + z [L45] z = z + 6 VAL [a=5, counter=4, n=4, x=64, y=61, z=30] [L33] EXPR counter++ VAL [a=5, counter=5, n=4, x=64, y=61, z=30] [L33] COND TRUE counter++<5 [L34] CALL __VERIFIER_assert(z == 6 * n + 6) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L34] RET __VERIFIER_assert(z == 6 * n + 6) VAL [a=5, counter=5, n=4, x=64, y=61, z=30] [L35] CALL __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L35] RET __VERIFIER_assert(y == 3 * n * n + 3 * n + 1) VAL [a=5, counter=5, n=4, x=64, y=61, z=30] [L36] CALL __VERIFIER_assert(x == n * n * n) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L36] RET __VERIFIER_assert(x == n * n * n) VAL [a=5, counter=5, n=4, x=64, y=61, z=30] [L37] CALL __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L37] RET __VERIFIER_assert(y*z - 18*x - 12*y + 2*z - 6 == 0) VAL [a=5, counter=5, n=4, x=64, y=61, z=30] [L38] CALL __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L38] RET __VERIFIER_assert((z*z) - 12*y - 6*z + 12 == 0) VAL [a=5, counter=5, n=4, x=64, y=61, z=30] [L39] COND FALSE !(!(n <= a)) [L42] n = n + 1 [L43] x = x + y [L44] y = y + z [L45] z = z + 6 VAL [a=5, counter=5, n=5, x=125, y=91, z=36] [L33] EXPR counter++ VAL [a=5, counter=6, n=5, x=125, y=91, z=36] [L33] COND FALSE !(counter++<5) [L48] CALL __VERIFIER_assert(z == 6*n + 6) VAL [\old(cond)=1, counter=6] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=6] [L48] RET __VERIFIER_assert(z == 6*n + 6) VAL [a=5, counter=6, n=5, x=125, y=91, z=36] [L49] CALL __VERIFIER_assert(6*a*x - x*z + 12*x == 0) VAL [\old(cond)=0, counter=6] [L15] COND TRUE !(cond) VAL [\old(cond)=0, counter=6] [L17] reach_error() VAL [\old(cond)=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 26 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 19.4s, OverallIterations: 18, TraceHistogramMax: 27, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 10.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 216 SdHoareTripleChecker+Valid, 9.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 162 mSDsluCounter, 2630 SdHoareTripleChecker+Invalid, 8.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2095 mSDsCounter, 324 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2295 IncrementalHoareTripleChecker+Invalid, 2620 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 324 mSolverCounterUnsat, 535 mSDtfsCounter, 2295 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1915 GetRequests, 1735 SyntacticMatches, 10 SemanticMatches, 170 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 241 ImplicationChecksByTransitivity, 2.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=163occurred in iteration=15, InterpolantAutomatonStates: 140, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 17 MinimizatonAttempts, 26 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 4.2s InterpolantComputationTime, 2393 NumberOfCodeBlocks, 2242 NumberOfCodeBlocksAsserted, 58 NumberOfCheckSat, 1976 ConstructedInterpolants, 0 QuantifiedInterpolants, 7587 SizeOfPredicates, 30 NumberOfNonLiveVariables, 2218 ConjunctsInSsa, 285 ConjunctsInUnsatCore, 28 InterpolantComputations, 6 PerfectInterpolantSequences, 10862/12144 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-19 21:10:58,305 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE