./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound10.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 53086523abe0dc699ccd28b0916f17f8825d4641577f06835b9d81e9579a444f --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:43:25,289 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:43:25,369 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:43:25,377 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:43:25,378 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:43:25,408 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:43:25,409 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:43:25,409 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:43:25,409 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:43:25,410 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:43:25,411 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:43:25,412 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:43:25,413 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:43:25,416 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:43:25,417 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:43:25,417 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:43:25,417 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:43:25,418 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:43:25,418 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:43:25,418 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:43:25,418 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:43:25,419 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:43:25,420 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:43:25,420 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:43:25,421 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:43:25,421 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:43:25,421 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:43:25,422 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:43:25,422 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:43:25,422 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:43:25,423 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:43:25,423 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:43:25,423 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:43:25,424 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:43:25,424 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:43:25,425 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:43:25,425 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:43:25,425 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:43:25,426 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:43:25,426 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:43:25,426 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:43:25,426 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:43:25,427 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 -> 53086523abe0dc699ccd28b0916f17f8825d4641577f06835b9d81e9579a444f [2024-11-08 14:43:25,696 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:43:25,716 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:43:25,722 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:43:25,723 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:43:25,724 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:43:25,725 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound10.c [2024-11-08 14:43:27,223 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:43:27,419 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:43:27,421 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound10.c [2024-11-08 14:43:27,430 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5c2225f16/b23e6586bf1042bb9e225cd63eb0c861/FLAG35b63f80e [2024-11-08 14:43:27,802 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5c2225f16/b23e6586bf1042bb9e225cd63eb0c861 [2024-11-08 14:43:27,804 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:43:27,805 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:43:27,809 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:43:27,810 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:43:27,815 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:43:27,816 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:43:27" (1/1) ... [2024-11-08 14:43:27,817 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@66a00c5c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:27, skipping insertion in model container [2024-11-08 14:43:27,817 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:43:27" (1/1) ... [2024-11-08 14:43:27,838 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:43:28,013 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/ps4-ll_valuebound10.c[458,471] [2024-11-08 14:43:28,033 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:43:28,047 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:43:28,061 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/ps4-ll_valuebound10.c[458,471] [2024-11-08 14:43:28,067 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:43:28,083 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:43:28,083 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28 WrapperNode [2024-11-08 14:43:28,083 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:43:28,084 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:43:28,085 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:43:28,085 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:43:28,091 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,095 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,114 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 38 [2024-11-08 14:43:28,114 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:43:28,115 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:43:28,115 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:43:28,115 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:43:28,123 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,123 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,124 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,135 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-08 14:43:28,136 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,136 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,138 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,145 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,146 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,148 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,150 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:43:28,151 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:43:28,152 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:43:28,152 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:43:28,153 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (1/1) ... [2024-11-08 14:43:28,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:43:28,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:43:28,181 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-08 14:43:28,183 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-08 14:43:28,240 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:43:28,241 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:43:28,241 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:43:28,241 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:43:28,241 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:43:28,241 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:43:28,297 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:43:28,299 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:43:28,428 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-08 14:43:28,428 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:43:28,441 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:43:28,441 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-08 14:43:28,442 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:43:28 BoogieIcfgContainer [2024-11-08 14:43:28,442 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:43:28,444 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:43:28,444 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:43:28,448 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:43:28,448 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:43:27" (1/3) ... [2024-11-08 14:43:28,450 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2fb14e09 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:43:28, skipping insertion in model container [2024-11-08 14:43:28,450 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:43:28" (2/3) ... [2024-11-08 14:43:28,453 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2fb14e09 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:43:28, skipping insertion in model container [2024-11-08 14:43:28,453 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:43:28" (3/3) ... [2024-11-08 14:43:28,454 INFO L112 eAbstractionObserver]: Analyzing ICFG ps4-ll_valuebound10.c [2024-11-08 14:43:28,473 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:43:28,473 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:43:28,557 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:43:28,566 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;@259f6b3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:43:28,567 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:43:28,571 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 14:43:28,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-08 14:43:28,580 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:43:28,581 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:43:28,581 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:43:28,587 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:43:28,588 INFO L85 PathProgramCache]: Analyzing trace with hash -589436290, now seen corresponding path program 1 times [2024-11-08 14:43:28,597 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:43:28,598 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [594623728] [2024-11-08 14:43:28,598 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:28,599 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:43:28,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:43:28,753 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-08 14:43:28,753 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:43:28,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [594623728] [2024-11-08 14:43:28,754 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [594623728] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:43:28,754 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:43:28,754 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:43:28,756 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [52062251] [2024-11-08 14:43:28,756 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:43:28,759 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:43:28,760 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:43:28,780 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:43:28,781 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:43:28,783 INFO L87 Difference]: Start difference. First operand has 19 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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-08 14:43:28,798 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:43:28,799 INFO L93 Difference]: Finished difference Result 35 states and 49 transitions. [2024-11-08 14:43:28,800 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:43:28,801 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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 9 [2024-11-08 14:43:28,802 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:43:28,809 INFO L225 Difference]: With dead ends: 35 [2024-11-08 14:43:28,809 INFO L226 Difference]: Without dead ends: 15 [2024-11-08 14:43:28,813 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-08 14:43:28,818 INFO L432 NwaCegarLoop]: 21 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, 21 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-08 14:43:28,820 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:43:28,835 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-11-08 14:43:28,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-11-08 14:43:28,852 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.2) internal successors, (12), 11 states have internal predecessors, (12), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:43:28,853 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 17 transitions. [2024-11-08 14:43:28,854 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 17 transitions. Word has length 9 [2024-11-08 14:43:28,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:43:28,855 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 17 transitions. [2024-11-08 14:43:28,855 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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-08 14:43:28,856 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 17 transitions. [2024-11-08 14:43:28,856 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-08 14:43:28,856 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:43:28,856 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:43:28,857 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:43:28,857 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:43:28,858 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:43:28,858 INFO L85 PathProgramCache]: Analyzing trace with hash 1187358532, now seen corresponding path program 1 times [2024-11-08 14:43:28,858 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:43:28,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [538795719] [2024-11-08 14:43:28,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:28,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:43:28,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:43:28,899 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [335153866] [2024-11-08 14:43:28,900 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:28,901 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:43:28,901 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:43:28,903 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-08 14:43:28,905 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-08 14:43:28,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:43:28,985 INFO L255 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:43:28,991 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:43:29,116 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-08 14:43:29,119 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:43:29,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:43:29,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [538795719] [2024-11-08 14:43:29,121 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:43:29,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [335153866] [2024-11-08 14:43:29,122 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [335153866] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:43:29,123 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:43:29,123 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:43:29,124 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1781335685] [2024-11-08 14:43:29,125 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:43:29,125 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:43:29,126 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:43:29,127 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:43:29,127 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:43:29,127 INFO L87 Difference]: Start difference. First operand 15 states and 17 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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-08 14:43:29,190 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:43:29,190 INFO L93 Difference]: Finished difference Result 26 states and 30 transitions. [2024-11-08 14:43:29,191 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:43:29,191 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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 9 [2024-11-08 14:43:29,191 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:43:29,192 INFO L225 Difference]: With dead ends: 26 [2024-11-08 14:43:29,192 INFO L226 Difference]: Without dead ends: 22 [2024-11-08 14:43:29,193 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 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-08 14:43:29,195 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:43:29,195 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 45 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:43:29,196 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-08 14:43:29,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-08 14:43:29,203 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 14:43:29,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 24 transitions. [2024-11-08 14:43:29,204 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 24 transitions. Word has length 9 [2024-11-08 14:43:29,204 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:43:29,204 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 24 transitions. [2024-11-08 14:43:29,205 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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-08 14:43:29,205 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 24 transitions. [2024-11-08 14:43:29,206 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-08 14:43:29,206 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:43:29,206 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:43:29,226 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-08 14:43:29,411 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:43:29,412 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:43:29,413 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:43:29,413 INFO L85 PathProgramCache]: Analyzing trace with hash -1781398469, now seen corresponding path program 1 times [2024-11-08 14:43:29,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:43:29,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [28166175] [2024-11-08 14:43:29,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:29,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:43:29,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:43:29,456 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1549449708] [2024-11-08 14:43:29,456 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:29,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:43:29,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:43:29,460 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-08 14:43:29,463 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-08 14:43:29,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:43:29,514 INFO L255 TraceCheckSpWp]: Trace formula consists of 61 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:43:29,516 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:43:29,604 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:43:29,605 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:43:29,697 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-08 14:43:29,698 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:43:29,698 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [28166175] [2024-11-08 14:43:29,698 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:43:29,699 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1549449708] [2024-11-08 14:43:29,699 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1549449708] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-08 14:43:29,699 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:43:29,699 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-08 14:43:29,699 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [980970448] [2024-11-08 14:43:29,700 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:43:29,700 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:43:29,700 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:43:29,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:43:29,704 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:43:29,704 INFO L87 Difference]: Start difference. First operand 22 states and 24 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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-08 14:43:29,755 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:43:29,755 INFO L93 Difference]: Finished difference Result 28 states and 29 transitions. [2024-11-08 14:43:29,755 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:43:29,755 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2024-11-08 14:43:29,756 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:43:29,756 INFO L225 Difference]: With dead ends: 28 [2024-11-08 14:43:29,756 INFO L226 Difference]: Without dead ends: 23 [2024-11-08 14:43:29,757 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:43:29,758 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 4 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:43:29,758 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 44 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:43:29,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-08 14:43:29,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-08 14:43:29,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 17 states have (on average 1.0588235294117647) internal successors, (18), 17 states have internal predecessors, (18), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:43:29,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2024-11-08 14:43:29,767 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 16 [2024-11-08 14:43:29,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:43:29,768 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2024-11-08 14:43:29,768 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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-08 14:43:29,771 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2024-11-08 14:43:29,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-08 14:43:29,772 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:43:29,772 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:43:29,787 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-08 14:43:29,972 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-08 14:43:29,973 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:43:29,973 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:43:29,974 INFO L85 PathProgramCache]: Analyzing trace with hash -1711372296, now seen corresponding path program 1 times [2024-11-08 14:43:29,974 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:43:29,974 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1284947589] [2024-11-08 14:43:29,974 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:29,974 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:43:30,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:43:30,018 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2014490762] [2024-11-08 14:43:30,018 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:30,018 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:43:30,018 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:43:30,020 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-08 14:43:30,027 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-08 14:43:30,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:43:30,078 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-08 14:43:30,080 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:43:30,172 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:43:30,174 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:43:30,309 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:43:30,309 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:43:30,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1284947589] [2024-11-08 14:43:30,310 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:43:30,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2014490762] [2024-11-08 14:43:30,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2014490762] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:43:30,310 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:43:30,311 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-08 14:43:30,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [47810529] [2024-11-08 14:43:30,312 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:43:30,313 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-08 14:43:30,315 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:43:30,316 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-08 14:43:30,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:43:30,318 INFO L87 Difference]: Start difference. First operand 23 states and 23 transitions. Second operand has 10 states, 8 states have (on average 2.375) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-08 14:43:30,487 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:43:30,488 INFO L93 Difference]: Finished difference Result 38 states and 43 transitions. [2024-11-08 14:43:30,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-08 14:43:30,489 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 22 [2024-11-08 14:43:30,490 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:43:30,490 INFO L225 Difference]: With dead ends: 38 [2024-11-08 14:43:30,490 INFO L226 Difference]: Without dead ends: 32 [2024-11-08 14:43:30,491 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 32 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-11-08 14:43:30,492 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 1 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:43:30,492 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 109 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:43:30,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-08 14:43:30,508 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-11-08 14:43:30,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.0434782608695652) internal successors, (24), 23 states have internal predecessors, (24), 6 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-08 14:43:30,511 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 35 transitions. [2024-11-08 14:43:30,511 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 35 transitions. Word has length 22 [2024-11-08 14:43:30,512 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:43:30,512 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 35 transitions. [2024-11-08 14:43:30,512 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-08 14:43:30,512 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 35 transitions. [2024-11-08 14:43:30,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-08 14:43:30,515 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:43:30,515 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:43:30,532 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-08 14:43:30,716 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:43:30,716 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:43:30,717 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:43:30,717 INFO L85 PathProgramCache]: Analyzing trace with hash 1384689793, now seen corresponding path program 2 times [2024-11-08 14:43:30,717 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:43:30,717 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1233562305] [2024-11-08 14:43:30,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:43:30,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:43:30,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:43:30,774 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [341266357] [2024-11-08 14:43:30,774 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:43:30,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:43:30,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:43:30,777 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-08 14:43:30,779 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-08 14:43:30,844 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:43:30,844 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:43:30,846 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-08 14:43:30,848 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:43:31,096 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 9 proven. 43 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 14:43:31,096 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:43:31,450 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 9 proven. 43 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 14:43:31,450 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:43:31,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1233562305] [2024-11-08 14:43:31,451 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:43:31,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [341266357] [2024-11-08 14:43:31,451 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [341266357] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:43:31,451 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:43:31,451 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 22 [2024-11-08 14:43:31,452 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1413975564] [2024-11-08 14:43:31,452 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:43:31,452 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-08 14:43:31,452 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:43:31,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-08 14:43:31,454 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2024-11-08 14:43:31,454 INFO L87 Difference]: Start difference. First operand 32 states and 35 transitions. Second operand has 22 states, 20 states have (on average 1.9) internal successors, (38), 19 states have internal predecessors, (38), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 14:43:31,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:43:31,795 INFO L93 Difference]: Finished difference Result 36 states and 41 transitions. [2024-11-08 14:43:31,795 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-08 14:43:31,795 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.9) internal successors, (38), 19 states have internal predecessors, (38), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 43 [2024-11-08 14:43:31,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:43:31,796 INFO L225 Difference]: With dead ends: 36 [2024-11-08 14:43:31,796 INFO L226 Difference]: Without dead ends: 0 [2024-11-08 14:43:31,797 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=139, Invalid=617, Unknown=0, NotChecked=0, Total=756 [2024-11-08 14:43:31,798 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 5 mSDsluCounter, 176 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 192 SdHoareTripleChecker+Invalid, 193 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:43:31,798 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 192 Invalid, 193 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 185 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:43:31,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-08 14:43:31,799 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-08 14:43:31,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:43:31,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-08 14:43:31,799 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 43 [2024-11-08 14:43:31,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:43:31,800 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-08 14:43:31,800 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.9) internal successors, (38), 19 states have internal predecessors, (38), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 14:43:31,800 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-08 14:43:31,800 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-08 14:43:31,803 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-08 14:43:31,819 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-08 14:43:32,003 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:43:32,007 INFO L407 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1] [2024-11-08 14:43:32,009 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-08 14:43:32,456 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-08 14:43:32,484 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 08.11 02:43:32 BoogieIcfgContainer [2024-11-08 14:43:32,486 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-08 14:43:32,486 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-08 14:43:32,487 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-08 14:43:32,487 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-08 14:43:32,487 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:43:28" (3/4) ... [2024-11-08 14:43:32,490 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-08 14:43:32,503 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-08 14:43:32,507 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 12 nodes and edges [2024-11-08 14:43:32,508 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-11-08 14:43:32,508 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-08 14:43:32,508 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-08 14:43:32,604 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-08 14:43:32,604 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-08 14:43:32,604 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-08 14:43:32,605 INFO L158 Benchmark]: Toolchain (without parser) took 4799.92ms. Allocated memory was 130.0MB in the beginning and 178.3MB in the end (delta: 48.2MB). Free memory was 75.7MB in the beginning and 147.0MB in the end (delta: -71.3MB). Peak memory consumption was 81.3MB. Max. memory is 16.1GB. [2024-11-08 14:43:32,607 INFO L158 Benchmark]: CDTParser took 0.24ms. Allocated memory is still 130.0MB. Free memory was 91.3MB in the beginning and 91.2MB in the end (delta: 134.3kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-08 14:43:32,608 INFO L158 Benchmark]: CACSL2BoogieTranslator took 274.49ms. Allocated memory is still 130.0MB. Free memory was 75.4MB in the beginning and 62.5MB in the end (delta: 12.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-08 14:43:32,608 INFO L158 Benchmark]: Boogie Procedure Inliner took 29.71ms. Allocated memory is still 130.0MB. Free memory was 62.5MB in the beginning and 60.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-08 14:43:32,608 INFO L158 Benchmark]: Boogie Preprocessor took 35.58ms. Allocated memory is still 130.0MB. Free memory was 60.9MB in the beginning and 59.5MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-08 14:43:32,609 INFO L158 Benchmark]: RCFGBuilder took 290.77ms. Allocated memory was 130.0MB in the beginning and 178.3MB in the end (delta: 48.2MB). Free memory was 59.5MB in the beginning and 145.8MB in the end (delta: -86.3MB). Peak memory consumption was 11.2MB. Max. memory is 16.1GB. [2024-11-08 14:43:32,609 INFO L158 Benchmark]: TraceAbstraction took 4041.84ms. Allocated memory is still 178.3MB. Free memory was 145.8MB in the beginning and 46.0MB in the end (delta: 99.8MB). Peak memory consumption was 97.7MB. Max. memory is 16.1GB. [2024-11-08 14:43:32,609 INFO L158 Benchmark]: Witness Printer took 117.92ms. Allocated memory is still 178.3MB. Free memory was 46.0MB in the beginning and 147.0MB in the end (delta: -101.0MB). Peak memory consumption was 3.9MB. Max. memory is 16.1GB. [2024-11-08 14:43:32,611 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.24ms. Allocated memory is still 130.0MB. Free memory was 91.3MB in the beginning and 91.2MB in the end (delta: 134.3kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 274.49ms. Allocated memory is still 130.0MB. Free memory was 75.4MB in the beginning and 62.5MB in the end (delta: 12.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 29.71ms. Allocated memory is still 130.0MB. Free memory was 62.5MB in the beginning and 60.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 35.58ms. Allocated memory is still 130.0MB. Free memory was 60.9MB in the beginning and 59.5MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 290.77ms. Allocated memory was 130.0MB in the beginning and 178.3MB in the end (delta: 48.2MB). Free memory was 59.5MB in the beginning and 145.8MB in the end (delta: -86.3MB). Peak memory consumption was 11.2MB. Max. memory is 16.1GB. * TraceAbstraction took 4041.84ms. Allocated memory is still 178.3MB. Free memory was 145.8MB in the beginning and 46.0MB in the end (delta: 99.8MB). Peak memory consumption was 97.7MB. Max. memory is 16.1GB. * Witness Printer took 117.92ms. Allocated memory is still 178.3MB. Free memory was 46.0MB in the beginning and 147.0MB in the end (delta: -101.0MB). Peak memory consumption was 3.9MB. 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 - PositiveResult [Line: 12]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 19 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 3.5s, OverallIterations: 5, TraceHistogramMax: 6, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 0.7s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 18 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 14 mSDsluCounter, 411 SdHoareTripleChecker+Invalid, 0.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 333 mSDsCounter, 13 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 275 IncrementalHoareTripleChecker+Invalid, 288 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 13 mSolverCounterUnsat, 78 mSDtfsCounter, 275 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 177 GetRequests, 126 SyntacticMatches, 4 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=32occurred in iteration=4, InterpolantAutomatonStates: 36, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 5 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 1.2s InterpolantComputationTime, 189 NumberOfCodeBlocks, 189 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 172 ConstructedInterpolants, 0 QuantifiedInterpolants, 817 SizeOfPredicates, 7 NumberOfNonLiveVariables, 298 ConjunctsInSsa, 64 ConjunctsInUnsatCore, 8 InterpolantComputations, 3 PerfectInterpolantSequences, 96/190 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 - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 27]: Loop Invariant Derived loop invariant: (((((y + ((__int128) y * y)) == (c + ((__int128) c * y))) && ((((__int128) 2 * c) + ((__int128) c * y)) == (((__int128) 2 * y) + ((__int128) y * y)))) && ((((__int128) k * y) == ((__int128) y * y)) || (c < k))) && (((((((__int128) y * y) * y) * 2) + ((((__int128) y * y) * y) * y)) + ((__int128) y * y)) == ((__int128) x * 4))) - ProcedureContractResult [Line: 9]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= cond) Ensures: (1 <= cond) RESULT: Ultimate proved your program to be correct! [2024-11-08 14:43:32,628 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 Result: TRUE