./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4fc63b2a Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound100.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2 --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash e40af029af23d5cbf5d8bd74acfdc7af42526c81be3e447d3e43ec16d52857d1 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4fc63b2 [2024-11-02 12:34:52,070 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-02 12:34:52,166 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-02 12:34:52,176 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-02 12:34:52,177 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-02 12:34:52,238 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-02 12:34:52,240 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-02 12:34:52,240 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-02 12:34:52,241 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-02 12:34:52,241 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-02 12:34:52,242 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-02 12:34:52,243 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-02 12:34:52,243 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-02 12:34:52,246 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-02 12:34:52,246 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-02 12:34:52,247 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-02 12:34:52,247 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-02 12:34:52,265 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-02 12:34:52,265 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-02 12:34:52,266 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-02 12:34:52,266 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-02 12:34:52,267 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-02 12:34:52,267 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-02 12:34:52,268 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-02 12:34:52,268 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-02 12:34:52,268 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-02 12:34:52,268 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-02 12:34:52,269 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-02 12:34:52,269 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-02 12:34:52,269 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-02 12:34:52,269 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-02 12:34:52,270 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-02 12:34:52,270 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-02 12:34:52,272 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-02 12:34:52,272 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-02 12:34:52,272 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-02 12:34:52,273 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-02 12:34:52,273 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-02 12:34:52,273 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-02 12:34:52,273 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-02 12:34:52,273 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-02 12:34:52,274 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-02 12:34:52,274 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-02 12:34:52,274 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-02 12:34:52,275 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-02 12:34:52,275 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-02 12:34:52,276 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-02 12:34:52,276 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2 Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> 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 -> e40af029af23d5cbf5d8bd74acfdc7af42526c81be3e447d3e43ec16d52857d1 [2024-11-02 12:34:52,560 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-02 12:34:52,618 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-02 12:34:52,625 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-02 12:34:52,628 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-02 12:34:52,628 INFO L274 PluginConnector]: CDTParser initialized [2024-11-02 12:34:52,630 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound100.c Unable to find full path for "g++" Unable to find full path for "g++" [2024-11-02 12:34:55,763 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-02 12:34:55,967 INFO L384 CDTParser]: Found 1 translation units. [2024-11-02 12:34:55,968 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound100.c [2024-11-02 12:34:55,978 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/data/6fb0d08a1/c6305f3a1b234a139765d13f23d4d8ec/FLAG3566d5504 [2024-11-02 12:34:55,993 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/data/6fb0d08a1/c6305f3a1b234a139765d13f23d4d8ec [2024-11-02 12:34:55,996 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-02 12:34:55,998 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-02 12:34:56,000 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-02 12:34:56,000 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-02 12:34:56,007 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-02 12:34:56,008 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.11 12:34:55" (1/1) ... [2024-11-02 12:34:56,009 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1c21005f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56, skipping insertion in model container [2024-11-02 12:34:56,009 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.11 12:34:55" (1/1) ... [2024-11-02 12:34:56,032 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-02 12:34:56,235 WARN L251 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound100.c[458,471] [2024-11-02 12:34:56,255 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-02 12:34:56,264 INFO L200 MainTranslator]: Completed pre-run [2024-11-02 12:34:56,275 WARN L251 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound100.c[458,471] [2024-11-02 12:34:56,283 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-02 12:34:56,299 INFO L204 MainTranslator]: Completed translation [2024-11-02 12:34:56,300 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56 WrapperNode [2024-11-02 12:34:56,300 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-02 12:34:56,301 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-02 12:34:56,301 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-02 12:34:56,301 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-02 12:34:56,310 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,318 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,340 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 43 [2024-11-02 12:34:56,341 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-02 12:34:56,342 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-02 12:34:56,342 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-02 12:34:56,342 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-02 12:34:56,351 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,351 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,352 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,353 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,356 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,360 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,361 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,362 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,364 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-02 12:34:56,365 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-02 12:34:56,365 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-02 12:34:56,365 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-02 12:34:56,366 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (1/1) ... [2024-11-02 12:34:56,374 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-02 12:34:56,391 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:34:56,404 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-02 12:34:56,407 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-02 12:34:56,440 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-02 12:34:56,440 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-02 12:34:56,440 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-02 12:34:56,441 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-02 12:34:56,441 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-02 12:34:56,441 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-02 12:34:56,512 INFO L238 CfgBuilder]: Building ICFG [2024-11-02 12:34:56,514 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-02 12:34:56,701 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-02 12:34:56,702 INFO L287 CfgBuilder]: Performing block encoding [2024-11-02 12:34:56,775 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-02 12:34:56,776 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-02 12:34:56,776 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.11 12:34:56 BoogieIcfgContainer [2024-11-02 12:34:56,777 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-02 12:34:56,780 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-02 12:34:56,780 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-02 12:34:56,784 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-02 12:34:56,785 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.11 12:34:55" (1/3) ... [2024-11-02 12:34:56,786 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@33d8eb35 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.11 12:34:56, skipping insertion in model container [2024-11-02 12:34:56,786 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:34:56" (2/3) ... [2024-11-02 12:34:56,786 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@33d8eb35 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.11 12:34:56, skipping insertion in model container [2024-11-02 12:34:56,786 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.11 12:34:56" (3/3) ... [2024-11-02 12:34:56,788 INFO L112 eAbstractionObserver]: Analyzing ICFG ps6-ll_unwindbound100.c [2024-11-02 12:34:56,810 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-02 12:34:56,810 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-02 12:34:56,869 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-02 12:34:56,876 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;@79b3039d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-02 12:34:56,876 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-02 12:34:56,880 INFO L276 IsEmpty]: Start isEmpty. Operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-02 12:34:56,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-02 12:34:56,888 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:34:56,889 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-02 12:34:56,890 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:34:56,896 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:34:56,896 INFO L85 PathProgramCache]: Analyzing trace with hash -1749202120, now seen corresponding path program 1 times [2024-11-02 12:34:56,908 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:34:56,909 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [26989620] [2024-11-02 12:34:56,909 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:34:56,910 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:34:57,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:34:57,089 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-02 12:34:57,090 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:34:57,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [26989620] [2024-11-02 12:34:57,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [26989620] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 12:34:57,092 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 12:34:57,092 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-02 12:34:57,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1962728141] [2024-11-02 12:34:57,095 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 12:34:57,101 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-02 12:34:57,101 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:34:57,127 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-02 12:34:57,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-02 12:34:57,130 INFO L87 Difference]: Start difference. First operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:34:57,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:34:57,161 INFO L93 Difference]: Finished difference Result 29 states and 42 transitions. [2024-11-02 12:34:57,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-02 12:34:57,164 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2024-11-02 12:34:57,165 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:34:57,172 INFO L225 Difference]: With dead ends: 29 [2024-11-02 12:34:57,172 INFO L226 Difference]: Without dead ends: 13 [2024-11-02 12:34:57,176 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-02 12:34:57,181 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 16 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-02 12:34:57,182 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 16 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-02 12:34:57,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2024-11-02 12:34:57,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2024-11-02 12:34:57,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:34:57,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 16 transitions. [2024-11-02 12:34:57,229 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 16 transitions. Word has length 6 [2024-11-02 12:34:57,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:34:57,230 INFO L471 AbstractCegarLoop]: Abstraction has 13 states and 16 transitions. [2024-11-02 12:34:57,230 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:34:57,231 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 16 transitions. [2024-11-02 12:34:57,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-02 12:34:57,231 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:34:57,232 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:34:57,232 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-02 12:34:57,233 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:34:57,234 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:34:57,234 INFO L85 PathProgramCache]: Analyzing trace with hash 1208885392, now seen corresponding path program 1 times [2024-11-02 12:34:57,234 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:34:57,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1816589851] [2024-11-02 12:34:57,235 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:34:57,235 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:34:57,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:34:57,360 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-02 12:34:57,361 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:34:57,361 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1816589851] [2024-11-02 12:34:57,361 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1816589851] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 12:34:57,362 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 12:34:57,362 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-02 12:34:57,362 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [378054350] [2024-11-02 12:34:57,363 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 12:34:57,364 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-02 12:34:57,364 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:34:57,365 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-02 12:34:57,366 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-02 12:34:57,366 INFO L87 Difference]: Start difference. First operand 13 states and 16 transitions. Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:34:57,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:34:57,393 INFO L93 Difference]: Finished difference Result 23 states and 27 transitions. [2024-11-02 12:34:57,393 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-02 12:34:57,394 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-02 12:34:57,394 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:34:57,395 INFO L225 Difference]: With dead ends: 23 [2024-11-02 12:34:57,395 INFO L226 Difference]: Without dead ends: 15 [2024-11-02 12:34:57,396 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-02 12:34:57,398 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-02 12:34:57,398 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-02 12:34:57,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-11-02 12:34:57,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-11-02 12:34:57,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:34:57,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-11-02 12:34:57,411 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 7 [2024-11-02 12:34:57,411 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:34:57,411 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-11-02 12:34:57,412 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:34:57,416 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2024-11-02 12:34:57,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-02 12:34:57,417 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:34:57,417 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:34:57,417 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-02 12:34:57,418 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:34:57,418 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:34:57,419 INFO L85 PathProgramCache]: Analyzing trace with hash 1210672852, now seen corresponding path program 1 times [2024-11-02 12:34:57,419 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:34:57,419 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [410664270] [2024-11-02 12:34:57,419 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:34:57,420 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:34:57,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:34:57,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [477260990] [2024-11-02 12:34:57,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:34:57,475 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:34:57,477 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:34:57,480 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:34:57,486 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-02 12:34:57,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:34:57,570 INFO L255 TraceCheckSpWp]: Trace formula consists of 46 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-02 12:34:57,585 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:34:57,740 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-02 12:34:57,741 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-02 12:34:57,741 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:34:57,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [410664270] [2024-11-02 12:34:57,742 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-02 12:34:57,743 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [477260990] [2024-11-02 12:34:57,743 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [477260990] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 12:34:57,743 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 12:34:57,744 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-02 12:34:57,744 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [228960304] [2024-11-02 12:34:57,744 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 12:34:57,745 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-02 12:34:57,745 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:34:57,746 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-02 12:34:57,747 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-02 12:34:57,747 INFO L87 Difference]: Start difference. First operand 15 states and 18 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:34:57,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:34:57,824 INFO L93 Difference]: Finished difference Result 25 states and 30 transitions. [2024-11-02 12:34:57,825 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-02 12:34:57,825 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-02 12:34:57,825 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:34:57,826 INFO L225 Difference]: With dead ends: 25 [2024-11-02 12:34:57,826 INFO L226 Difference]: Without dead ends: 21 [2024-11-02 12:34:57,827 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-02 12:34:57,828 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-02 12:34:57,829 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 45 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-02 12:34:57,830 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-02 12:34:57,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-11-02 12:34:57,837 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-02 12:34:57,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2024-11-02 12:34:57,839 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 7 [2024-11-02 12:34:57,839 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:34:57,839 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2024-11-02 12:34:57,840 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:34:57,840 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2024-11-02 12:34:57,841 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-02 12:34:57,841 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:34:57,841 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:34:57,858 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-02 12:34:58,042 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:34:58,042 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:34:58,043 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:34:58,043 INFO L85 PathProgramCache]: Analyzing trace with hash 479296502, now seen corresponding path program 1 times [2024-11-02 12:34:58,043 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:34:58,044 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [801303649] [2024-11-02 12:34:58,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:34:58,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:34:58,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:34:58,259 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:34:58,260 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:34:58,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [801303649] [2024-11-02 12:34:58,260 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [801303649] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 12:34:58,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1410247356] [2024-11-02 12:34:58,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:34:58,261 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:34:58,261 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:34:58,266 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:34:58,267 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-02 12:34:58,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:34:58,336 INFO L255 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-02 12:34:58,338 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:34:58,380 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:34:58,382 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:34:58,456 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:34:58,456 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1410247356] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-02 12:34:58,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1587051171] [2024-11-02 12:34:58,485 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-02 12:34:58,485 INFO L166 IcfgInterpreter]: Building call graph [2024-11-02 12:34:58,489 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-02 12:34:58,495 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-02 12:34:58,495 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-02 12:34:59,793 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 66 for LOIs [2024-11-02 12:34:59,977 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-02 12:35:05,144 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '327#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (or (and (<= 101 ~counter~0) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8| Int)) (and (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (not (= (+ (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8| 12) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) (+ (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) 2) (* 6 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) (* 5 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|))))) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8|)))) (and (exists ((|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| Int)) (and (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9|) (not (= (+ (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) 2) (* 5 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|)) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) 6)) (+ (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| 12) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|)))))) (<= ~counter~0 100))))' at error location [2024-11-02 12:35:05,144 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-02 12:35:05,144 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-02 12:35:05,144 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-02 12:35:05,144 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [246364938] [2024-11-02 12:35:05,145 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-02 12:35:05,145 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-02 12:35:05,145 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:35:05,146 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-02 12:35:05,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=225, Unknown=1, NotChecked=0, Total=272 [2024-11-02 12:35:05,147 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-02 12:35:05,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:35:05,288 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2024-11-02 12:35:05,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-02 12:35:05,289 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 15 [2024-11-02 12:35:05,289 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:35:05,291 INFO L225 Difference]: With dead ends: 55 [2024-11-02 12:35:05,291 INFO L226 Difference]: Without dead ends: 47 [2024-11-02 12:35:05,292 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=66, Invalid=313, Unknown=1, NotChecked=0, Total=380 [2024-11-02 12:35:05,296 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 23 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-02 12:35:05,297 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 57 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-02 12:35:05,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-02 12:35:05,309 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2024-11-02 12:35:05,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 28 states have (on average 1.25) internal successors, (35), 31 states have internal predecessors, (35), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-02 12:35:05,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 52 transitions. [2024-11-02 12:35:05,312 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 52 transitions. Word has length 15 [2024-11-02 12:35:05,313 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:35:05,313 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 52 transitions. [2024-11-02 12:35:05,313 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-02 12:35:05,313 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 52 transitions. [2024-11-02 12:35:05,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-02 12:35:05,314 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:35:05,314 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:35:05,335 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-02 12:35:05,514 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:35:05,515 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:35:05,515 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:35:05,516 INFO L85 PathProgramCache]: Analyzing trace with hash 481083962, now seen corresponding path program 1 times [2024-11-02 12:35:05,516 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:35:05,516 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1018653412] [2024-11-02 12:35:05,516 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:35:05,516 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:35:05,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:35:05,542 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [625306460] [2024-11-02 12:35:05,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:35:05,542 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:35:05,542 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:35:05,544 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:35:05,546 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-02 12:35:05,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:35:05,611 INFO L255 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-02 12:35:05,613 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:35:05,684 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:35:05,684 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:35:05,769 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-02 12:35:05,769 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:35:05,770 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1018653412] [2024-11-02 12:35:05,770 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-02 12:35:05,770 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [625306460] [2024-11-02 12:35:05,770 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [625306460] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-02 12:35:05,770 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-02 12:35:05,770 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-02 12:35:05,770 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [583590851] [2024-11-02 12:35:05,771 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 12:35:05,771 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-02 12:35:05,771 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:35:05,772 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-02 12:35:05,772 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-02 12:35:05,774 INFO L87 Difference]: Start difference. First operand 43 states and 52 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-02 12:35:05,843 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:35:05,845 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2024-11-02 12:35:05,846 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-02 12:35:05,846 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-02 12:35:05,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:35:05,847 INFO L225 Difference]: With dead ends: 57 [2024-11-02 12:35:05,847 INFO L226 Difference]: Without dead ends: 49 [2024-11-02 12:35:05,848 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-02 12:35:05,848 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 5 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-02 12:35:05,849 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 33 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-02 12:35:05,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-02 12:35:05,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 43. [2024-11-02 12:35:05,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 32 states have internal predecessors, (34), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-02 12:35:05,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2024-11-02 12:35:05,866 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 15 [2024-11-02 12:35:05,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:35:05,867 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2024-11-02 12:35:05,867 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-02 12:35:05,867 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2024-11-02 12:35:05,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-02 12:35:05,868 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:35:05,868 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:35:05,892 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-02 12:35:06,070 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:35:06,071 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:35:06,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:35:06,072 INFO L85 PathProgramCache]: Analyzing trace with hash 669026573, now seen corresponding path program 1 times [2024-11-02 12:35:06,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:35:06,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1432824099] [2024-11-02 12:35:06,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:35:06,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:35:06,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:35:06,118 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1750730905] [2024-11-02 12:35:06,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:35:06,119 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:35:06,119 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:35:06,124 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:35:06,125 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-02 12:35:06,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:35:06,183 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-02 12:35:06,185 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:35:06,301 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-02 12:35:06,301 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:35:06,440 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-02 12:35:06,440 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:35:06,440 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1432824099] [2024-11-02 12:35:06,440 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-02 12:35:06,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1750730905] [2024-11-02 12:35:06,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1750730905] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-02 12:35:06,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1801744964] [2024-11-02 12:35:06,443 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-02 12:35:06,443 INFO L166 IcfgInterpreter]: Building call graph [2024-11-02 12:35:06,444 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-02 12:35:06,445 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-02 12:35:06,445 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-02 12:35:06,998 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2024-11-02 12:35:07,005 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-02 12:35:07,335 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '894#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 100))' at error location [2024-11-02 12:35:07,335 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-02 12:35:07,336 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-02 12:35:07,336 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-02 12:35:07,336 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1660077512] [2024-11-02 12:35:07,336 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-02 12:35:07,337 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-02 12:35:07,337 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:35:07,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-02 12:35:07,338 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=289, Unknown=0, NotChecked=0, Total=342 [2024-11-02 12:35:07,338 INFO L87 Difference]: Start difference. First operand 43 states and 49 transitions. Second operand has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-02 12:35:07,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:35:07,503 INFO L93 Difference]: Finished difference Result 52 states and 60 transitions. [2024-11-02 12:35:07,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-02 12:35:07,504 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 26 [2024-11-02 12:35:07,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:35:07,505 INFO L225 Difference]: With dead ends: 52 [2024-11-02 12:35:07,505 INFO L226 Difference]: Without dead ends: 43 [2024-11-02 12:35:07,506 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 57 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=68, Invalid=394, Unknown=0, NotChecked=0, Total=462 [2024-11-02 12:35:07,507 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-02 12:35:07,507 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 99 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-02 12:35:07,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-02 12:35:07,520 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-02 12:35:07,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-02 12:35:07,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 46 transitions. [2024-11-02 12:35:07,522 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 46 transitions. Word has length 26 [2024-11-02 12:35:07,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:35:07,522 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 46 transitions. [2024-11-02 12:35:07,522 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-02 12:35:07,523 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 46 transitions. [2024-11-02 12:35:07,523 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-02 12:35:07,524 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:35:07,524 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:35:07,546 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-02 12:35:07,724 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:35:07,725 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:35:07,725 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:35:07,725 INFO L85 PathProgramCache]: Analyzing trace with hash -783657828, now seen corresponding path program 1 times [2024-11-02 12:35:07,726 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:35:07,726 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101738378] [2024-11-02 12:35:07,726 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:35:07,726 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:35:07,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:35:08,042 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-02 12:35:08,043 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:35:08,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101738378] [2024-11-02 12:35:08,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1101738378] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 12:35:08,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [484963964] [2024-11-02 12:35:08,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:35:08,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:35:08,044 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:35:08,046 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:35:08,052 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-02 12:35:08,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:35:08,113 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-02 12:35:08,115 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:35:08,185 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-02 12:35:08,186 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:35:08,326 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-02 12:35:08,326 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [484963964] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-02 12:35:08,328 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1193594744] [2024-11-02 12:35:08,330 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-02 12:35:08,331 INFO L166 IcfgInterpreter]: Building call graph [2024-11-02 12:35:08,332 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-02 12:35:08,332 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-02 12:35:08,335 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-02 12:35:08,968 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-02 12:35:08,974 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-02 12:35:09,296 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1324#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-02 12:35:09,297 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-02 12:35:09,297 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-02 12:35:09,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2024-11-02 12:35:09,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1045803565] [2024-11-02 12:35:09,298 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-02 12:35:09,299 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-02 12:35:09,301 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:35:09,301 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-02 12:35:09,302 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=446, Unknown=0, NotChecked=0, Total=552 [2024-11-02 12:35:09,302 INFO L87 Difference]: Start difference. First operand 43 states and 46 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-02 12:35:09,617 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:35:09,617 INFO L93 Difference]: Finished difference Result 129 states and 141 transitions. [2024-11-02 12:35:09,618 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-02 12:35:09,618 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) Word has length 44 [2024-11-02 12:35:09,618 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:35:09,619 INFO L225 Difference]: With dead ends: 129 [2024-11-02 12:35:09,619 INFO L226 Difference]: Without dead ends: 119 [2024-11-02 12:35:09,620 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 272 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=219, Invalid=837, Unknown=0, NotChecked=0, Total=1056 [2024-11-02 12:35:09,621 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 77 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-02 12:35:09,621 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 105 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-02 12:35:09,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2024-11-02 12:35:09,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 94. [2024-11-02 12:35:09,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 66 states have (on average 1.106060606060606) internal successors, (73), 71 states have internal predecessors, (73), 17 states have call successors, (17), 11 states have call predecessors, (17), 10 states have return successors, (16), 11 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-02 12:35:09,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 106 transitions. [2024-11-02 12:35:09,649 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 106 transitions. Word has length 44 [2024-11-02 12:35:09,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:35:09,649 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 106 transitions. [2024-11-02 12:35:09,649 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-02 12:35:09,650 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 106 transitions. [2024-11-02 12:35:09,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-02 12:35:09,651 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:35:09,651 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:35:09,672 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-02 12:35:09,851 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-02 12:35:09,852 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:35:09,852 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:35:09,852 INFO L85 PathProgramCache]: Analyzing trace with hash 1502128027, now seen corresponding path program 2 times [2024-11-02 12:35:09,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:35:09,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1418818221] [2024-11-02 12:35:09,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:35:09,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:35:09,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:35:09,906 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [664150448] [2024-11-02 12:35:09,907 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-02 12:35:09,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:35:09,908 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:35:09,909 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:35:09,911 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_20e41365-6353-41b7-9184-3e43171d1781/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-02 12:35:09,981 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-02 12:35:09,981 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-02 12:35:09,983 INFO L255 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-02 12:35:09,986 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:35:10,266 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 25 proven. 51 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-02 12:35:10,266 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:35:14,725 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))) (= (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 2)) (+ (* |c_ULTIMATE.start_main_~c~0#1| 2) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|))))) is different from false [2024-11-02 12:35:22,830 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (= (+ (* |c_ULTIMATE.start_main_~c~0#1| 3) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|)) (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 3))) (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))))) is different from false [2024-11-02 12:35:32,969 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (= (+ (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~c~0#1| 4)) (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 4))) (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))))) is different from false