./Ultimate.py --spec ../../sv-benchmarks/c/properties/no-overflow.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/freire1_valuebound2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/freire1_valuebound2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Overflow-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! overflow) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 2c82dcc3d917c20926ea634368e9542e23b7ae4e7817b33542bbba01403d748d --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 04:28:26,727 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 04:28:26,808 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Overflow-32bit-Taipan_Default.epf [2024-11-14 04:28:26,814 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 04:28:26,815 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 04:28:26,854 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 04:28:26,855 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 04:28:26,855 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 04:28:26,855 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 04:28:26,855 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 04:28:26,855 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 04:28:26,855 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 04:28:26,856 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 04:28:26,856 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 04:28:26,857 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 04:28:26,857 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 04:28:26,857 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 04:28:26,857 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 04:28:26,859 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 04:28:26,860 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 04:28:26,860 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 04:28:26,860 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 04:28:26,860 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 04:28:26,860 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 04:28:26,860 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2024-11-14 04:28:26,860 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-14 04:28:26,861 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 04:28:26,861 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 04:28:26,861 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 04:28:26,861 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 04:28:26,861 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 04:28:26,861 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 04:28:26,861 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:28:26,862 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 04:28:26,862 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 04:28:26,862 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 04:28:26,862 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 04:28:26,862 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 04:28:26,862 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 04:28:26,862 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 04:28:26,863 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 04:28:26,863 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES 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 -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E 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 ! overflow) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan 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 -> 2c82dcc3d917c20926ea634368e9542e23b7ae4e7817b33542bbba01403d748d [2024-11-14 04:28:27,237 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 04:28:27,247 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 04:28:27,250 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 04:28:27,251 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 04:28:27,251 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 04:28:27,253 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/freire1_valuebound2.c Unable to find full path for "g++" [2024-11-14 04:28:29,291 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 04:28:29,557 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 04:28:29,558 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/sv-benchmarks/c/nla-digbench-scaling/freire1_valuebound2.c [2024-11-14 04:28:29,567 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/data/3086008b5/ef6130742720418b9004ce3cd564fac1/FLAGd92514c4c [2024-11-14 04:28:29,594 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/data/3086008b5/ef6130742720418b9004ce3cd564fac1 [2024-11-14 04:28:29,597 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 04:28:29,599 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 04:28:29,600 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 04:28:29,602 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 04:28:29,607 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 04:28:29,608 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,609 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@309c428a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29, skipping insertion in model container [2024-11-14 04:28:29,612 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,631 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 04:28:29,857 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:28:29,871 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 04:28:29,894 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:28:29,911 INFO L204 MainTranslator]: Completed translation [2024-11-14 04:28:29,913 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29 WrapperNode [2024-11-14 04:28:29,914 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 04:28:29,915 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 04:28:29,916 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 04:28:29,916 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 04:28:29,929 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,937 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,957 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 44 [2024-11-14 04:28:29,958 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 04:28:29,959 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 04:28:29,959 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 04:28:29,959 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 04:28:29,968 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,969 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,970 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,971 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,978 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,988 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,989 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,990 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:29,991 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 04:28:29,994 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 04:28:29,994 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 04:28:29,994 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 04:28:29,996 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (1/1) ... [2024-11-14 04:28:30,003 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:28:30,020 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:30,038 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 04:28:30,044 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 04:28:30,073 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 04:28:30,074 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 04:28:30,074 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 04:28:30,074 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 04:28:30,074 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 04:28:30,074 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 04:28:30,143 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 04:28:30,145 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 04:28:30,287 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-14 04:28:30,287 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 04:28:30,341 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 04:28:30,341 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 04:28:30,342 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:28:30 BoogieIcfgContainer [2024-11-14 04:28:30,342 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 04:28:30,345 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 04:28:30,345 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 04:28:30,351 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 04:28:30,351 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 04:28:29" (1/3) ... [2024-11-14 04:28:30,352 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2139fbf3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:28:30, skipping insertion in model container [2024-11-14 04:28:30,352 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:28:29" (2/3) ... [2024-11-14 04:28:30,353 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2139fbf3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:28:30, skipping insertion in model container [2024-11-14 04:28:30,353 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:28:30" (3/3) ... [2024-11-14 04:28:30,354 INFO L112 eAbstractionObserver]: Analyzing ICFG freire1_valuebound2.c [2024-11-14 04:28:30,373 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 04:28:30,374 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG freire1_valuebound2.c that has 2 procedures, 21 locations, 1 initial locations, 1 loop locations, and 6 error locations. [2024-11-14 04:28:30,444 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 04:28:30,466 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=FINITE_AUTOMATA, 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;@233fe66a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 04:28:30,466 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2024-11-14 04:28:30,472 INFO L276 IsEmpty]: Start isEmpty. Operand has 21 states, 11 states have (on average 1.7272727272727273) internal successors, (19), 17 states have internal predecessors, (19), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:28:30,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2024-11-14 04:28:30,480 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:30,481 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1] [2024-11-14 04:28:30,482 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:30,489 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:30,490 INFO L85 PathProgramCache]: Analyzing trace with hash 98567, now seen corresponding path program 1 times [2024-11-14 04:28:30,500 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:30,500 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1412062645] [2024-11-14 04:28:30,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:30,502 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:30,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:28:30,670 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-14 04:28:30,671 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:28:30,671 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1412062645] [2024-11-14 04:28:30,671 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1412062645] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:28:30,672 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:28:30,672 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-11-14 04:28:30,676 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1096594005] [2024-11-14 04:28:30,677 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:28:30,682 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 04:28:30,682 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:28:30,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 04:28:30,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 04:28:30,707 INFO L87 Difference]: Start difference. First operand has 21 states, 11 states have (on average 1.7272727272727273) internal successors, (19), 17 states have internal predecessors, (19), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 1 states have (on average 3.0) internal successors, (3), 2 states have internal predecessors, (3), 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-14 04:28:30,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:28:30,753 INFO L93 Difference]: Finished difference Result 29 states and 31 transitions. [2024-11-14 04:28:30,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 04:28:30,758 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 1 states have (on average 3.0) internal successors, (3), 2 states have internal predecessors, (3), 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) Word has length 3 [2024-11-14 04:28:30,759 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:28:30,765 INFO L225 Difference]: With dead ends: 29 [2024-11-14 04:28:30,765 INFO L226 Difference]: Without dead ends: 16 [2024-11-14 04:28:30,773 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 1 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-14 04:28:30,777 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 17 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:28:30,778 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 17 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:28:30,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2024-11-14 04:28:30,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2024-11-14 04:28:30,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 10 states have (on average 1.4) internal successors, (14), 13 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 04:28:30,822 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2024-11-14 04:28:30,824 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 3 [2024-11-14 04:28:30,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:28:30,824 INFO L471 AbstractCegarLoop]: Abstraction has 16 states and 16 transitions. [2024-11-14 04:28:30,824 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 1 states have (on average 3.0) internal successors, (3), 2 states have internal predecessors, (3), 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-14 04:28:30,824 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 16 transitions. [2024-11-14 04:28:30,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2024-11-14 04:28:30,825 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:30,825 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1] [2024-11-14 04:28:30,825 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 04:28:30,825 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:30,826 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:30,826 INFO L85 PathProgramCache]: Analyzing trace with hash 3055628, now seen corresponding path program 1 times [2024-11-14 04:28:30,826 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:30,826 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1634713219] [2024-11-14 04:28:30,826 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:30,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:30,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:28:30,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1304572042] [2024-11-14 04:28:30,842 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:30,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:30,843 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:30,846 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:28:30,848 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 04:28:30,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:28:30,909 INFO L255 TraceCheckSpWp]: Trace formula consists of 27 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-14 04:28:30,914 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:28:30,955 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-14 04:28:30,956 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:28:30,956 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:28:30,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1634713219] [2024-11-14 04:28:30,957 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:28:30,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1304572042] [2024-11-14 04:28:30,957 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1304572042] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:28:30,957 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:28:30,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-11-14 04:28:30,958 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1960301680] [2024-11-14 04:28:30,958 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:28:30,961 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 04:28:30,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:28:30,962 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 04:28:30,962 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:28:30,962 INFO L87 Difference]: Start difference. First operand 16 states and 16 transitions. Second operand has 3 states, 2 states have (on average 2.0) internal successors, (4), 2 states have internal predecessors, (4), 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-14 04:28:31,023 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:28:31,023 INFO L93 Difference]: Finished difference Result 29 states and 30 transitions. [2024-11-14 04:28:31,024 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 04:28:31,024 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 2 states have internal predecessors, (4), 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) Word has length 4 [2024-11-14 04:28:31,024 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:28:31,024 INFO L225 Difference]: With dead ends: 29 [2024-11-14 04:28:31,024 INFO L226 Difference]: Without dead ends: 23 [2024-11-14 04:28:31,025 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:28:31,025 INFO L432 NwaCegarLoop]: 9 mSDtfsCounter, 5 mSDsluCounter, 5 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 14 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:28:31,026 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 14 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:28:31,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-14 04:28:31,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-14 04:28:31,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.25) internal successors, (20), 19 states have internal predecessors, (20), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:28:31,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2024-11-14 04:28:31,038 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 4 [2024-11-14 04:28:31,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:28:31,038 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 24 transitions. [2024-11-14 04:28:31,038 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 2 states have internal predecessors, (4), 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-14 04:28:31,038 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 24 transitions. [2024-11-14 04:28:31,039 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 04:28:31,039 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:31,040 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:28:31,057 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 04:28:31,244 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:31,244 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:31,245 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:31,245 INFO L85 PathProgramCache]: Analyzing trace with hash -1614454891, now seen corresponding path program 1 times [2024-11-14 04:28:31,245 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:31,245 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [853893946] [2024-11-14 04:28:31,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:31,245 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:31,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:28:31,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2062680268] [2024-11-14 04:28:31,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:31,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:31,289 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:31,295 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:28:31,298 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 04:28:31,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:28:31,376 INFO L255 TraceCheckSpWp]: Trace formula consists of 41 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 04:28:31,378 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:28:31,465 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:28:31,465 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:28:31,578 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:28:31,578 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:28:31,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [853893946] [2024-11-14 04:28:31,578 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:28:31,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2062680268] [2024-11-14 04:28:31,578 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2062680268] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:28:31,579 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [816460621] [2024-11-14 04:28:31,600 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:28:31,600 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:28:31,604 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:28:31,609 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:28:31,609 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:28:32,530 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:28:32,533 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:28:32,852 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '239#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_36| Int)) (and (<= |v_ULTIMATE.start_main_~r~0#1_36| 2147483647) (<= 0 |v_ULTIMATE.start_main_~r~0#1_36|) (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_36| |v_ULTIMATE.start_main_~r~0#1_36|)))))' at error location [2024-11-14 04:28:32,852 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:28:32,852 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:28:32,852 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3] total 5 [2024-11-14 04:28:32,853 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1092267088] [2024-11-14 04:28:32,853 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:28:32,853 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 04:28:32,853 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:28:32,854 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 04:28:32,856 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2024-11-14 04:28:32,856 INFO L87 Difference]: Start difference. First operand 23 states and 24 transitions. Second operand has 6 states, 5 states have (on average 4.2) internal successors, (21), 6 states have internal predecessors, (21), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:28:32,992 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:28:32,993 INFO L93 Difference]: Finished difference Result 45 states and 56 transitions. [2024-11-14 04:28:32,993 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 04:28:32,994 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 4.2) internal successors, (21), 6 states have internal predecessors, (21), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 13 [2024-11-14 04:28:32,994 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:28:32,994 INFO L225 Difference]: With dead ends: 45 [2024-11-14 04:28:32,995 INFO L226 Difference]: Without dead ends: 35 [2024-11-14 04:28:32,995 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 25 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=40, Invalid=116, Unknown=0, NotChecked=0, Total=156 [2024-11-14 04:28:32,997 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 19 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 24 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:28:32,998 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 24 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:28:33,000 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2024-11-14 04:28:33,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2024-11-14 04:28:33,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 29 states have (on average 1.0344827586206897) internal successors, (30), 29 states have internal predecessors, (30), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 04:28:33,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 38 transitions. [2024-11-14 04:28:33,010 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 38 transitions. Word has length 13 [2024-11-14 04:28:33,013 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:28:33,013 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 38 transitions. [2024-11-14 04:28:33,013 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 4.2) internal successors, (21), 6 states have internal predecessors, (21), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:28:33,014 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 38 transitions. [2024-11-14 04:28:33,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-14 04:28:33,016 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:33,016 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1] [2024-11-14 04:28:33,038 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-14 04:28:33,221 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:33,221 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:33,221 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:33,222 INFO L85 PathProgramCache]: Analyzing trace with hash 735915084, now seen corresponding path program 2 times [2024-11-14 04:28:33,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:33,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [486642063] [2024-11-14 04:28:33,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:33,222 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:33,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:28:33,275 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1343535685] [2024-11-14 04:28:33,275 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 04:28:33,275 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:33,276 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:33,278 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:28:33,282 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 04:28:33,390 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 04:28:33,391 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:28:33,392 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 04:28:33,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:28:33,501 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 54 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 04:28:33,501 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:28:33,748 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 54 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 04:28:33,748 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:28:33,748 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [486642063] [2024-11-14 04:28:33,749 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:28:33,749 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1343535685] [2024-11-14 04:28:33,749 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1343535685] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:28:33,749 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [467538643] [2024-11-14 04:28:33,751 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:28:33,751 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:28:33,751 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:28:33,752 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:28:33,752 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:28:34,192 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:28:34,194 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:28:34,681 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '595#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_49| Int)) (and (<= |v_ULTIMATE.start_main_~r~0#1_49| 2147483647) (<= 0 |v_ULTIMATE.start_main_~r~0#1_49|) (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_49| |v_ULTIMATE.start_main_~r~0#1_49|)))))' at error location [2024-11-14 04:28:34,682 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:28:34,682 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:28:34,682 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 11 [2024-11-14 04:28:34,682 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [350014954] [2024-11-14 04:28:34,682 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:28:34,682 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-14 04:28:34,683 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:28:34,683 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-14 04:28:34,684 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=239, Unknown=0, NotChecked=0, Total=306 [2024-11-14 04:28:34,684 INFO L87 Difference]: Start difference. First operand 35 states and 38 transitions. Second operand has 12 states, 11 states have (on average 5.181818181818182) internal successors, (57), 12 states have internal predecessors, (57), 8 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 04:28:35,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:28:35,068 INFO L93 Difference]: Finished difference Result 78 states and 92 transitions. [2024-11-14 04:28:35,069 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 04:28:35,069 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 5.181818181818182) internal successors, (57), 12 states have internal predecessors, (57), 8 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 40 [2024-11-14 04:28:35,070 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:28:35,070 INFO L225 Difference]: With dead ends: 78 [2024-11-14 04:28:35,071 INFO L226 Difference]: Without dead ends: 77 [2024-11-14 04:28:35,071 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 97 SyntacticMatches, 5 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=115, Invalid=347, Unknown=0, NotChecked=0, Total=462 [2024-11-14 04:28:35,072 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 18 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:28:35,072 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 95 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:28:35,073 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2024-11-14 04:28:35,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2024-11-14 04:28:35,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 65 states have (on average 1.0153846153846153) internal successors, (66), 65 states have internal predecessors, (66), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:28:35,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 86 transitions. [2024-11-14 04:28:35,098 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 86 transitions. Word has length 40 [2024-11-14 04:28:35,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:28:35,099 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 86 transitions. [2024-11-14 04:28:35,099 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 5.181818181818182) internal successors, (57), 12 states have internal predecessors, (57), 8 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 04:28:35,099 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 86 transitions. [2024-11-14 04:28:35,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2024-11-14 04:28:35,102 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:35,102 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 10, 1, 1] [2024-11-14 04:28:35,124 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-14 04:28:35,302 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:35,303 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:35,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:35,303 INFO L85 PathProgramCache]: Analyzing trace with hash 1958863532, now seen corresponding path program 3 times [2024-11-14 04:28:35,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:35,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1222287192] [2024-11-14 04:28:35,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:35,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:35,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:28:35,373 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [925949766] [2024-11-14 04:28:35,373 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 04:28:35,374 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:35,374 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:35,376 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:28:35,383 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 04:28:35,480 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 04:28:35,480 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:28:35,485 INFO L255 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-14 04:28:35,491 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:28:35,776 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-14 04:28:35,777 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:28:36,531 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-14 04:28:36,533 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:28:36,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1222287192] [2024-11-14 04:28:36,533 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:28:36,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [925949766] [2024-11-14 04:28:36,534 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [925949766] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:28:36,534 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1170168572] [2024-11-14 04:28:36,537 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:28:36,537 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:28:36,538 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:28:36,538 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:28:36,538 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:28:36,879 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:28:36,881 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:28:37,919 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1392#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_74| Int)) (and (<= |v_ULTIMATE.start_main_~r~0#1_74| 2147483647) (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_74| |v_ULTIMATE.start_main_~r~0#1_74|)) (<= 0 |v_ULTIMATE.start_main_~r~0#1_74|))))' at error location [2024-11-14 04:28:37,919 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:28:37,920 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:28:37,920 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 23 [2024-11-14 04:28:37,920 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [14913726] [2024-11-14 04:28:37,920 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:28:37,921 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-14 04:28:37,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:28:37,922 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-14 04:28:37,923 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=187, Invalid=683, Unknown=0, NotChecked=0, Total=870 [2024-11-14 04:28:37,925 INFO L87 Difference]: Start difference. First operand 77 states and 86 transitions. Second operand has 24 states, 23 states have (on average 5.608695652173913) internal successors, (129), 24 states have internal predecessors, (129), 20 states have call successors, (20), 1 states have call predecessors, (20), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-14 04:28:39,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:28:39,195 INFO L93 Difference]: Finished difference Result 162 states and 194 transitions. [2024-11-14 04:28:39,196 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-14 04:28:39,196 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 23 states have (on average 5.608695652173913) internal successors, (129), 24 states have internal predecessors, (129), 20 states have call successors, (20), 1 states have call predecessors, (20), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) Word has length 94 [2024-11-14 04:28:39,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:28:39,198 INFO L225 Difference]: With dead ends: 162 [2024-11-14 04:28:39,198 INFO L226 Difference]: Without dead ends: 161 [2024-11-14 04:28:39,202 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 290 GetRequests, 241 SyntacticMatches, 11 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 305 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=427, Invalid=1133, Unknown=0, NotChecked=0, Total=1560 [2024-11-14 04:28:39,203 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 39 mSDsluCounter, 362 mSDsCounter, 0 mSdLazyCounter, 681 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 407 SdHoareTripleChecker+Invalid, 694 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 681 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-14 04:28:39,205 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 407 Invalid, 694 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 681 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-14 04:28:39,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2024-11-14 04:28:39,237 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 161. [2024-11-14 04:28:39,239 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 137 states have (on average 1.0072992700729928) internal successors, (138), 137 states have internal predecessors, (138), 22 states have call successors, (22), 1 states have call predecessors, (22), 1 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 04:28:39,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 182 transitions. [2024-11-14 04:28:39,243 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 182 transitions. Word has length 94 [2024-11-14 04:28:39,243 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:28:39,244 INFO L471 AbstractCegarLoop]: Abstraction has 161 states and 182 transitions. [2024-11-14 04:28:39,244 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 23 states have (on average 5.608695652173913) internal successors, (129), 24 states have internal predecessors, (129), 20 states have call successors, (20), 1 states have call predecessors, (20), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-14 04:28:39,246 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 182 transitions. [2024-11-14 04:28:39,251 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 203 [2024-11-14 04:28:39,251 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:39,251 INFO L215 NwaCegarLoop]: trace histogram [23, 23, 22, 22, 22, 22, 22, 22, 22, 1, 1] [2024-11-14 04:28:39,277 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-14 04:28:39,452 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:39,453 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:39,454 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:39,455 INFO L85 PathProgramCache]: Analyzing trace with hash -1745635476, now seen corresponding path program 4 times [2024-11-14 04:28:39,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:39,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [509767687] [2024-11-14 04:28:39,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:39,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:39,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:28:39,595 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1724298685] [2024-11-14 04:28:39,595 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 04:28:39,595 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:39,595 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:39,597 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:28:39,604 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 04:28:39,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:28:39,759 INFO L255 TraceCheckSpWp]: Trace formula consists of 335 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-14 04:28:39,769 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:28:40,430 INFO L134 CoverageAnalysis]: Checked inductivity of 2145 backedges. 0 proven. 1683 refuted. 0 times theorem prover too weak. 462 trivial. 0 not checked. [2024-11-14 04:28:40,431 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:28:42,309 INFO L134 CoverageAnalysis]: Checked inductivity of 2145 backedges. 0 proven. 1683 refuted. 0 times theorem prover too weak. 462 trivial. 0 not checked. [2024-11-14 04:28:42,309 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:28:42,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [509767687] [2024-11-14 04:28:42,309 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:28:42,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1724298685] [2024-11-14 04:28:42,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1724298685] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:28:42,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1342563902] [2024-11-14 04:28:42,312 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:28:42,313 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:28:42,314 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:28:42,314 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:28:42,314 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:28:42,588 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:28:42,591 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:28:45,335 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3089#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_123| Int)) (and (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_123| |v_ULTIMATE.start_main_~r~0#1_123|)) (<= |v_ULTIMATE.start_main_~r~0#1_123| 2147483647) (<= 0 |v_ULTIMATE.start_main_~r~0#1_123|))))' at error location [2024-11-14 04:28:45,335 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:28:45,336 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:28:45,336 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 47 [2024-11-14 04:28:45,336 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1182420788] [2024-11-14 04:28:45,336 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:28:45,338 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2024-11-14 04:28:45,338 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:28:45,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2024-11-14 04:28:45,342 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=643, Invalid=2219, Unknown=0, NotChecked=0, Total=2862 [2024-11-14 04:28:45,343 INFO L87 Difference]: Start difference. First operand 161 states and 182 transitions. Second operand has 48 states, 47 states have (on average 5.808510638297872) internal successors, (273), 48 states have internal predecessors, (273), 44 states have call successors, (44), 1 states have call predecessors, (44), 1 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-14 04:28:49,617 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:28:49,618 INFO L93 Difference]: Finished difference Result 330 states and 398 transitions. [2024-11-14 04:28:49,618 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2024-11-14 04:28:49,619 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 47 states have (on average 5.808510638297872) internal successors, (273), 48 states have internal predecessors, (273), 44 states have call successors, (44), 1 states have call predecessors, (44), 1 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) Word has length 202 [2024-11-14 04:28:49,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:28:49,630 INFO L225 Difference]: With dead ends: 330 [2024-11-14 04:28:49,630 INFO L226 Difference]: Without dead ends: 329 [2024-11-14 04:28:49,632 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 626 GetRequests, 529 SyntacticMatches, 23 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1055 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=1699, Invalid=4001, Unknown=0, NotChecked=0, Total=5700 [2024-11-14 04:28:49,633 INFO L432 NwaCegarLoop]: 93 mSDtfsCounter, 72 mSDsluCounter, 1586 mSDsCounter, 0 mSdLazyCounter, 2805 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 1679 SdHoareTripleChecker+Invalid, 2829 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 2805 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-14 04:28:49,639 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 1679 Invalid, 2829 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 2805 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-14 04:28:49,641 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 329 states. [2024-11-14 04:28:49,689 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 329 to 329. [2024-11-14 04:28:49,690 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 329 states, 281 states have (on average 1.00355871886121) internal successors, (282), 281 states have internal predecessors, (282), 46 states have call successors, (46), 1 states have call predecessors, (46), 1 states have return successors, (46), 46 states have call predecessors, (46), 46 states have call successors, (46) [2024-11-14 04:28:49,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 329 states to 329 states and 374 transitions. [2024-11-14 04:28:49,694 INFO L78 Accepts]: Start accepts. Automaton has 329 states and 374 transitions. Word has length 202 [2024-11-14 04:28:49,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:28:49,695 INFO L471 AbstractCegarLoop]: Abstraction has 329 states and 374 transitions. [2024-11-14 04:28:49,695 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 47 states have (on average 5.808510638297872) internal successors, (273), 48 states have internal predecessors, (273), 44 states have call successors, (44), 1 states have call predecessors, (44), 1 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-14 04:28:49,695 INFO L276 IsEmpty]: Start isEmpty. Operand 329 states and 374 transitions. [2024-11-14 04:28:49,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 419 [2024-11-14 04:28:49,703 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:49,703 INFO L215 NwaCegarLoop]: trace histogram [47, 47, 46, 46, 46, 46, 46, 46, 46, 1, 1] [2024-11-14 04:28:49,725 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 04:28:49,904 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:49,904 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:49,904 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:49,905 INFO L85 PathProgramCache]: Analyzing trace with hash 107020524, now seen corresponding path program 5 times [2024-11-14 04:28:49,905 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:49,905 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [289637891] [2024-11-14 04:28:49,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:49,905 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:50,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:28:50,102 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1325203076] [2024-11-14 04:28:50,103 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 04:28:50,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:50,103 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:50,105 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:28:50,110 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 04:28:50,645 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 47 check-sat command(s) [2024-11-14 04:28:50,645 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:28:50,649 INFO L255 TraceCheckSpWp]: Trace formula consists of 671 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-14 04:28:50,665 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:28:52,180 INFO L134 CoverageAnalysis]: Checked inductivity of 9453 backedges. 0 proven. 7383 refuted. 0 times theorem prover too weak. 2070 trivial. 0 not checked. [2024-11-14 04:28:52,180 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:28:52,589 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:28:52,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [289637891] [2024-11-14 04:28:52,589 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:28:52,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1325203076] [2024-11-14 04:28:52,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1325203076] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:28:52,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2013546308] [2024-11-14 04:28:52,591 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:28:52,592 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:28:52,592 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:28:52,592 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:28:52,593 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:28:52,878 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:28:52,880 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:28:56,322 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5341#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_176| Int)) (and (<= 0 |v_ULTIMATE.start_main_~r~0#1_176|) (<= |v_ULTIMATE.start_main_~r~0#1_176| 2147483647) (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_176| |v_ULTIMATE.start_main_~r~0#1_176|)))))' at error location [2024-11-14 04:28:56,322 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:28:56,323 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 04:28:56,323 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2024-11-14 04:28:56,323 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [786341507] [2024-11-14 04:28:56,323 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 04:28:56,324 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2024-11-14 04:28:56,324 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:28:56,326 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2024-11-14 04:28:56,327 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1264, Invalid=2276, Unknown=0, NotChecked=0, Total=3540 [2024-11-14 04:28:56,327 INFO L87 Difference]: Start difference. First operand 329 states and 374 transitions. Second operand has 50 states, 49 states have (on average 5.73469387755102) internal successors, (281), 50 states have internal predecessors, (281), 46 states have call successors, (46), 1 states have call predecessors, (46), 1 states have return successors, (46), 46 states have call predecessors, (46), 46 states have call successors, (46) [2024-11-14 04:28:58,880 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:28:58,880 INFO L93 Difference]: Finished difference Result 341 states and 388 transitions. [2024-11-14 04:28:58,882 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2024-11-14 04:28:58,882 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 49 states have (on average 5.73469387755102) internal successors, (281), 50 states have internal predecessors, (281), 46 states have call successors, (46), 1 states have call predecessors, (46), 1 states have return successors, (46), 46 states have call predecessors, (46), 46 states have call successors, (46) Word has length 418 [2024-11-14 04:28:58,883 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:28:58,885 INFO L225 Difference]: With dead ends: 341 [2024-11-14 04:28:58,889 INFO L226 Difference]: Without dead ends: 340 [2024-11-14 04:28:58,891 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 897 GetRequests, 746 SyntacticMatches, 47 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4251 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=3748, Invalid=7382, Unknown=0, NotChecked=0, Total=11130 [2024-11-14 04:28:58,892 INFO L432 NwaCegarLoop]: 5 mSDtfsCounter, 233 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 93 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 234 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 349 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 93 IncrementalHoareTripleChecker+Valid, 256 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 04:28:58,892 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [234 Valid, 108 Invalid, 349 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [93 Valid, 256 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 04:28:58,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 340 states. [2024-11-14 04:28:58,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 340 to 336. [2024-11-14 04:28:58,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 336 states, 287 states have (on average 1.0034843205574913) internal successors, (288), 287 states have internal predecessors, (288), 47 states have call successors, (47), 1 states have call predecessors, (47), 1 states have return successors, (47), 47 states have call predecessors, (47), 47 states have call successors, (47) [2024-11-14 04:28:58,933 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 336 states to 336 states and 382 transitions. [2024-11-14 04:28:58,933 INFO L78 Accepts]: Start accepts. Automaton has 336 states and 382 transitions. Word has length 418 [2024-11-14 04:28:58,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:28:58,935 INFO L471 AbstractCegarLoop]: Abstraction has 336 states and 382 transitions. [2024-11-14 04:28:58,935 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 49 states have (on average 5.73469387755102) internal successors, (281), 50 states have internal predecessors, (281), 46 states have call successors, (46), 1 states have call predecessors, (46), 1 states have return successors, (46), 46 states have call predecessors, (46), 46 states have call successors, (46) [2024-11-14 04:28:58,935 INFO L276 IsEmpty]: Start isEmpty. Operand 336 states and 382 transitions. [2024-11-14 04:28:58,943 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 428 [2024-11-14 04:28:58,944 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:28:58,944 INFO L215 NwaCegarLoop]: trace histogram [48, 48, 47, 47, 47, 47, 47, 47, 47, 1, 1] [2024-11-14 04:28:58,970 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-14 04:28:59,144 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:59,145 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:28:59,145 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:28:59,145 INFO L85 PathProgramCache]: Analyzing trace with hash -1132332363, now seen corresponding path program 6 times [2024-11-14 04:28:59,145 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:28:59,145 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1004400095] [2024-11-14 04:28:59,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:28:59,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:28:59,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:28:59,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1637389919] [2024-11-14 04:28:59,377 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 04:28:59,377 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:28:59,377 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:28:59,382 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:28:59,386 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 04:28:59,567 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 04:28:59,567 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:28:59,570 INFO L255 TraceCheckSpWp]: Trace formula consists of 685 conjuncts, 97 conjuncts are in the unsatisfiable core [2024-11-14 04:28:59,576 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:29:01,174 INFO L134 CoverageAnalysis]: Checked inductivity of 9870 backedges. 0 proven. 7708 refuted. 0 times theorem prover too weak. 2162 trivial. 0 not checked. [2024-11-14 04:29:01,175 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:29:06,234 INFO L134 CoverageAnalysis]: Checked inductivity of 9870 backedges. 0 proven. 7708 refuted. 0 times theorem prover too weak. 2162 trivial. 0 not checked. [2024-11-14 04:29:06,234 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:29:06,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1004400095] [2024-11-14 04:29:06,234 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:29:06,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1637389919] [2024-11-14 04:29:06,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1637389919] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:29:06,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1399874734] [2024-11-14 04:29:06,236 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:29:06,236 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:29:06,237 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:29:06,237 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:29:06,237 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:29:06,443 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:29:06,445 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:29:14,534 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8965#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_275| Int)) (and (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_275| |v_ULTIMATE.start_main_~r~0#1_275|)) (<= |v_ULTIMATE.start_main_~r~0#1_275| 2147483647) (<= 0 |v_ULTIMATE.start_main_~r~0#1_275|))))' at error location [2024-11-14 04:29:14,534 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:29:14,534 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:29:14,534 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 97 [2024-11-14 04:29:14,535 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [446423145] [2024-11-14 04:29:14,535 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:29:14,536 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 98 states [2024-11-14 04:29:14,536 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:29:14,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 98 interpolants. [2024-11-14 04:29:14,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=2518, Invalid=8194, Unknown=0, NotChecked=0, Total=10712 [2024-11-14 04:29:14,542 INFO L87 Difference]: Start difference. First operand 336 states and 382 transitions. Second operand has 98 states, 97 states have (on average 5.907216494845361) internal successors, (573), 98 states have internal predecessors, (573), 94 states have call successors, (94), 1 states have call predecessors, (94), 1 states have return successors, (94), 94 states have call predecessors, (94), 94 states have call successors, (94) [2024-11-14 04:29:36,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:29:36,149 INFO L93 Difference]: Finished difference Result 680 states and 823 transitions. [2024-11-14 04:29:36,150 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 98 states. [2024-11-14 04:29:36,150 INFO L78 Accepts]: Start accepts. Automaton has has 98 states, 97 states have (on average 5.907216494845361) internal successors, (573), 98 states have internal predecessors, (573), 94 states have call successors, (94), 1 states have call predecessors, (94), 1 states have return successors, (94), 94 states have call predecessors, (94), 94 states have call successors, (94) Word has length 427 [2024-11-14 04:29:36,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:29:36,154 INFO L225 Difference]: With dead ends: 680 [2024-11-14 04:29:36,154 INFO L226 Difference]: Without dead ends: 679 [2024-11-14 04:29:36,158 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 1326 GetRequests, 1129 SyntacticMatches, 48 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4005 ImplicationChecksByTransitivity, 29.7s TimeCoverageRelationStatistics Valid=7124, Invalid=15526, Unknown=0, NotChecked=0, Total=22650 [2024-11-14 04:29:36,159 INFO L432 NwaCegarLoop]: 193 mSDtfsCounter, 147 mSDsluCounter, 6911 mSDsCounter, 0 mSdLazyCounter, 11855 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 149 SdHoareTripleChecker+Valid, 7104 SdHoareTripleChecker+Invalid, 11904 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 11855 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2024-11-14 04:29:36,160 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [149 Valid, 7104 Invalid, 11904 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [49 Valid, 11855 Invalid, 0 Unknown, 0 Unchecked, 4.6s Time] [2024-11-14 04:29:36,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 679 states. [2024-11-14 04:29:36,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 679 to 679. [2024-11-14 04:29:36,220 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 679 states, 581 states have (on average 1.0017211703958693) internal successors, (582), 581 states have internal predecessors, (582), 96 states have call successors, (96), 1 states have call predecessors, (96), 1 states have return successors, (96), 96 states have call predecessors, (96), 96 states have call successors, (96) [2024-11-14 04:29:36,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 679 states to 679 states and 774 transitions. [2024-11-14 04:29:36,225 INFO L78 Accepts]: Start accepts. Automaton has 679 states and 774 transitions. Word has length 427 [2024-11-14 04:29:36,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:29:36,226 INFO L471 AbstractCegarLoop]: Abstraction has 679 states and 774 transitions. [2024-11-14 04:29:36,227 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 98 states, 97 states have (on average 5.907216494845361) internal successors, (573), 98 states have internal predecessors, (573), 94 states have call successors, (94), 1 states have call predecessors, (94), 1 states have return successors, (94), 94 states have call predecessors, (94), 94 states have call successors, (94) [2024-11-14 04:29:36,227 INFO L276 IsEmpty]: Start isEmpty. Operand 679 states and 774 transitions. [2024-11-14 04:29:36,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 869 [2024-11-14 04:29:36,257 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:29:36,257 INFO L215 NwaCegarLoop]: trace histogram [97, 97, 96, 96, 96, 96, 96, 96, 96, 1, 1] [2024-11-14 04:29:36,280 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 04:29:36,457 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:29:36,458 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:29:36,458 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:29:36,458 INFO L85 PathProgramCache]: Analyzing trace with hash 1783973388, now seen corresponding path program 7 times [2024-11-14 04:29:36,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:29:36,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [216046847] [2024-11-14 04:29:36,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:29:36,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:29:36,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:29:36,847 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [148432893] [2024-11-14 04:29:36,847 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 04:29:36,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:29:36,847 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:29:36,849 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:29:36,851 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-14 04:29:37,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:29:37,209 INFO L255 TraceCheckSpWp]: Trace formula consists of 1371 conjuncts, 195 conjuncts are in the unsatisfiable core [2024-11-14 04:29:37,234 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:29:41,914 INFO L134 CoverageAnalysis]: Checked inductivity of 41328 backedges. 0 proven. 32208 refuted. 0 times theorem prover too weak. 9120 trivial. 0 not checked. [2024-11-14 04:29:41,915 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:30:00,679 INFO L134 CoverageAnalysis]: Checked inductivity of 41328 backedges. 0 proven. 32208 refuted. 0 times theorem prover too weak. 9120 trivial. 0 not checked. [2024-11-14 04:30:00,679 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:30:00,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [216046847] [2024-11-14 04:30:00,679 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:30:00,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [148432893] [2024-11-14 04:30:00,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [148432893] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:30:00,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [850324515] [2024-11-14 04:30:00,681 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:30:00,684 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:30:00,685 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:30:00,685 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:30:00,685 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:30:00,907 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:30:00,910 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:30:30,177 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '16212#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_472| Int)) (and (<= |v_ULTIMATE.start_main_~r~0#1_472| 2147483647) (<= 0 |v_ULTIMATE.start_main_~r~0#1_472|) (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_472| |v_ULTIMATE.start_main_~r~0#1_472|)))))' at error location [2024-11-14 04:30:30,177 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:30:30,177 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:30:30,178 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [98, 98] total 195 [2024-11-14 04:30:30,178 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1602506303] [2024-11-14 04:30:30,178 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:30:30,180 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 196 states [2024-11-14 04:30:30,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:30:30,190 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 196 interpolants. [2024-11-14 04:30:30,195 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9819, Invalid=30783, Unknown=0, NotChecked=0, Total=40602 [2024-11-14 04:30:30,198 INFO L87 Difference]: Start difference. First operand 679 states and 774 transitions. Second operand has 196 states, 195 states have (on average 5.953846153846154) internal successors, (1161), 196 states have internal predecessors, (1161), 192 states have call successors, (192), 1 states have call predecessors, (192), 1 states have return successors, (192), 192 states have call predecessors, (192), 192 states have call successors, (192) [2024-11-14 04:32:34,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:32:34,509 INFO L93 Difference]: Finished difference Result 1366 states and 1656 transitions. [2024-11-14 04:32:34,509 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 196 states. [2024-11-14 04:32:34,511 INFO L78 Accepts]: Start accepts. Automaton has has 196 states, 195 states have (on average 5.953846153846154) internal successors, (1161), 196 states have internal predecessors, (1161), 192 states have call successors, (192), 1 states have call predecessors, (192), 1 states have return successors, (192), 192 states have call predecessors, (192), 192 states have call successors, (192) Word has length 868 [2024-11-14 04:32:34,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:32:34,523 INFO L225 Difference]: With dead ends: 1366 [2024-11-14 04:32:34,523 INFO L226 Difference]: Without dead ends: 1365 [2024-11-14 04:32:34,536 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2698 GetRequests, 2305 SyntacticMatches, 97 SemanticMatches, 296 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15226 ImplicationChecksByTransitivity, 154.9s TimeCoverageRelationStatistics Valid=28635, Invalid=59871, Unknown=0, NotChecked=0, Total=88506 [2024-11-14 04:32:34,538 INFO L432 NwaCegarLoop]: 389 mSDtfsCounter, 297 mSDsluCounter, 28614 mSDsCounter, 0 mSdLazyCounter, 47731 mSolverCounterSat, 99 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 299 SdHoareTripleChecker+Valid, 29003 SdHoareTripleChecker+Invalid, 47830 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.2s SdHoareTripleChecker+Time, 99 IncrementalHoareTripleChecker+Valid, 47731 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:32:34,538 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [299 Valid, 29003 Invalid, 47830 Unknown, 0 Unchecked, 0.2s Time], IncrementalHoareTripleChecker [99 Valid, 47731 Invalid, 0 Unknown, 0 Unchecked, 16.0s Time] [2024-11-14 04:32:34,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1365 states. [2024-11-14 04:32:34,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1365 to 1365. [2024-11-14 04:32:34,636 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1365 states, 1169 states have (on average 1.0008554319931566) internal successors, (1170), 1169 states have internal predecessors, (1170), 194 states have call successors, (194), 1 states have call predecessors, (194), 1 states have return successors, (194), 194 states have call predecessors, (194), 194 states have call successors, (194) [2024-11-14 04:32:34,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1365 states to 1365 states and 1558 transitions. [2024-11-14 04:32:34,645 INFO L78 Accepts]: Start accepts. Automaton has 1365 states and 1558 transitions. Word has length 868 [2024-11-14 04:32:34,646 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:32:34,646 INFO L471 AbstractCegarLoop]: Abstraction has 1365 states and 1558 transitions. [2024-11-14 04:32:34,647 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 196 states, 195 states have (on average 5.953846153846154) internal successors, (1161), 196 states have internal predecessors, (1161), 192 states have call successors, (192), 1 states have call predecessors, (192), 1 states have return successors, (192), 192 states have call predecessors, (192), 192 states have call successors, (192) [2024-11-14 04:32:34,648 INFO L276 IsEmpty]: Start isEmpty. Operand 1365 states and 1558 transitions. [2024-11-14 04:32:34,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1751 [2024-11-14 04:32:34,670 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:32:34,671 INFO L215 NwaCegarLoop]: trace histogram [195, 195, 194, 194, 194, 194, 194, 194, 194, 1, 1] [2024-11-14 04:32:34,686 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-14 04:32:34,871 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:32:34,871 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:32:34,872 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:32:34,872 INFO L85 PathProgramCache]: Analyzing trace with hash 858609196, now seen corresponding path program 8 times [2024-11-14 04:32:34,872 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:32:34,872 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [645406952] [2024-11-14 04:32:34,873 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:32:34,873 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:32:35,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:32:35,611 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1426430849] [2024-11-14 04:32:35,611 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 04:32:35,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:32:35,612 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:32:35,614 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:32:35,616 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-14 04:32:39,086 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 195 check-sat command(s) [2024-11-14 04:32:39,086 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:32:39,100 INFO L255 TraceCheckSpWp]: Trace formula consists of 2743 conjuncts, 198 conjuncts are in the unsatisfiable core [2024-11-14 04:32:39,121 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:32:56,670 INFO L134 CoverageAnalysis]: Checked inductivity of 169071 backedges. 0 proven. 131629 refuted. 0 times theorem prover too weak. 37442 trivial. 0 not checked. [2024-11-14 04:32:56,671 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:32:58,023 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:32:58,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [645406952] [2024-11-14 04:32:58,023 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:32:58,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1426430849] [2024-11-14 04:32:58,023 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1426430849] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:32:58,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [851062856] [2024-11-14 04:32:58,032 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:32:58,032 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:32:58,032 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:32:58,032 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:32:58,032 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:32:58,432 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:32:58,433 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:33:40,755 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '25420#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_673| Int)) (and (<= 0 |v_ULTIMATE.start_main_~r~0#1_673|) (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_673| |v_ULTIMATE.start_main_~r~0#1_673|)) (<= |v_ULTIMATE.start_main_~r~0#1_673| 2147483647))))' at error location [2024-11-14 04:33:40,755 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:33:40,755 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-14 04:33:40,755 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [197] total 197 [2024-11-14 04:33:40,755 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1438145936] [2024-11-14 04:33:40,755 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-14 04:33:40,758 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 198 states [2024-11-14 04:33:40,758 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:33:40,764 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 198 interpolants. [2024-11-14 04:33:40,767 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19542, Invalid=23514, Unknown=0, NotChecked=0, Total=43056 [2024-11-14 04:33:40,769 INFO L87 Difference]: Start difference. First operand 1365 states and 1558 transitions. Second operand has 198 states, 197 states have (on average 5.934010152284264) internal successors, (1169), 198 states have internal predecessors, (1169), 194 states have call successors, (194), 1 states have call predecessors, (194), 1 states have return successors, (194), 194 states have call predecessors, (194), 194 states have call successors, (194) [2024-11-14 04:34:12,730 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:34:12,731 INFO L93 Difference]: Finished difference Result 1377 states and 1572 transitions. [2024-11-14 04:34:12,731 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 197 states. [2024-11-14 04:34:12,732 INFO L78 Accepts]: Start accepts. Automaton has has 198 states, 197 states have (on average 5.934010152284264) internal successors, (1169), 198 states have internal predecessors, (1169), 194 states have call successors, (194), 1 states have call predecessors, (194), 1 states have return successors, (194), 194 states have call predecessors, (194), 194 states have call successors, (194) Word has length 1750 [2024-11-14 04:34:12,736 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:34:12,742 INFO L225 Difference]: With dead ends: 1377 [2024-11-14 04:34:12,742 INFO L226 Difference]: Without dead ends: 1376 [2024-11-14 04:34:12,754 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3709 GetRequests, 3114 SyntacticMatches, 195 SemanticMatches, 400 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60861 ImplicationChecksByTransitivity, 87.9s TimeCoverageRelationStatistics Valid=58730, Invalid=102472, Unknown=0, NotChecked=0, Total=161202 [2024-11-14 04:34:12,754 INFO L432 NwaCegarLoop]: 5 mSDtfsCounter, 973 mSDsluCounter, 397 mSDsCounter, 0 mSdLazyCounter, 992 mSolverCounterSat, 389 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 974 SdHoareTripleChecker+Valid, 402 SdHoareTripleChecker+Invalid, 1381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 389 IncrementalHoareTripleChecker+Valid, 992 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-14 04:34:12,755 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [974 Valid, 402 Invalid, 1381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [389 Valid, 992 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-14 04:34:12,757 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1376 states. [2024-11-14 04:34:12,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1376 to 1372. [2024-11-14 04:34:12,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1372 states, 1175 states have (on average 1.0008510638297872) internal successors, (1176), 1175 states have internal predecessors, (1176), 195 states have call successors, (195), 1 states have call predecessors, (195), 1 states have return successors, (195), 195 states have call predecessors, (195), 195 states have call successors, (195) [2024-11-14 04:34:12,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1372 states to 1372 states and 1566 transitions. [2024-11-14 04:34:12,887 INFO L78 Accepts]: Start accepts. Automaton has 1372 states and 1566 transitions. Word has length 1750 [2024-11-14 04:34:12,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:34:12,892 INFO L471 AbstractCegarLoop]: Abstraction has 1372 states and 1566 transitions. [2024-11-14 04:34:12,893 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 198 states, 197 states have (on average 5.934010152284264) internal successors, (1169), 198 states have internal predecessors, (1169), 194 states have call successors, (194), 1 states have call predecessors, (194), 1 states have return successors, (194), 194 states have call predecessors, (194), 194 states have call successors, (194) [2024-11-14 04:34:12,893 INFO L276 IsEmpty]: Start isEmpty. Operand 1372 states and 1566 transitions. [2024-11-14 04:34:12,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1760 [2024-11-14 04:34:12,919 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:34:12,919 INFO L215 NwaCegarLoop]: trace histogram [196, 196, 195, 195, 195, 195, 195, 195, 195, 1, 1] [2024-11-14 04:34:12,940 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-14 04:34:13,120 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 04:34:13,120 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-14 04:34:13,120 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:34:13,121 INFO L85 PathProgramCache]: Analyzing trace with hash -1440641675, now seen corresponding path program 9 times [2024-11-14 04:34:13,121 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:34:13,121 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1574457685] [2024-11-14 04:34:13,121 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:34:13,121 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:34:13,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:34:13,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1159647080] [2024-11-14 04:34:13,853 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 04:34:13,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:34:13,853 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:34:13,856 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:34:13,858 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b401138d-11fb-4460-80c6-7bb232ada5e6/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-14 04:34:14,551 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 04:34:14,551 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:34:14,565 INFO L255 TraceCheckSpWp]: Trace formula consists of 2757 conjuncts, 393 conjuncts are in the unsatisfiable core [2024-11-14 04:34:14,583 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:34:31,930 INFO L134 CoverageAnalysis]: Checked inductivity of 170820 backedges. 0 proven. 132990 refuted. 0 times theorem prover too weak. 37830 trivial. 0 not checked. [2024-11-14 04:34:31,930 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:43,810 INFO L134 CoverageAnalysis]: Checked inductivity of 170820 backedges. 0 proven. 132990 refuted. 0 times theorem prover too weak. 37830 trivial. 0 not checked. [2024-11-14 04:35:43,810 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:43,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1574457685] [2024-11-14 04:35:43,810 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:43,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1159647080] [2024-11-14 04:35:43,810 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1159647080] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:43,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [515964542] [2024-11-14 04:35:43,813 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 04:35:43,813 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:43,813 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:43,813 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:43,813 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:44,013 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2024-11-14 04:35:44,015 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:37:45,406 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '40292#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~r~0#1_1068| Int)) (and (<= 2147483648 (* |v_ULTIMATE.start_main_~r~0#1_1068| |v_ULTIMATE.start_main_~r~0#1_1068|)) (<= |v_ULTIMATE.start_main_~r~0#1_1068| 2147483647) (<= 0 |v_ULTIMATE.start_main_~r~0#1_1068|))))' at error location [2024-11-14 04:37:45,406 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:37:45,406 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:37:45,407 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [197, 197] total 393 [2024-11-14 04:37:45,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [107799001] [2024-11-14 04:37:45,408 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:37:45,411 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 394 states [2024-11-14 04:37:45,411 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:37:45,423 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 394 interpolants. [2024-11-14 04:37:45,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39222, Invalid=120378, Unknown=0, NotChecked=0, Total=159600 [2024-11-14 04:37:45,435 INFO L87 Difference]: Start difference. First operand 1372 states and 1566 transitions. Second operand has 394 states, 393 states have (on average 5.977099236641221) internal successors, (2349), 394 states have internal predecessors, (2349), 390 states have call successors, (390), 1 states have call predecessors, (390), 1 states have return successors, (390), 390 states have call predecessors, (390), 390 states have call successors, (390)