./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/bresenham-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4fc63b2a Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/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_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/bresenham-ll_unwindbound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/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_2b2d6653-a483-49fa-a776-e825e1da337a/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 0bb6ea6333d2c4e133ad252fe2bcbc17b832f383e2bb5defb402851de157204c --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4fc63b2 [2024-11-02 12:23:07,007 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-02 12:23:07,093 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-02 12:23:07,103 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-02 12:23:07,104 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-02 12:23:07,139 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-02 12:23:07,141 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-02 12:23:07,142 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-02 12:23:07,143 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-02 12:23:07,144 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-02 12:23:07,144 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-02 12:23:07,145 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-02 12:23:07,145 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-02 12:23:07,145 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-02 12:23:07,147 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-02 12:23:07,148 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-02 12:23:07,148 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-02 12:23:07,148 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-02 12:23:07,149 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-02 12:23:07,149 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-02 12:23:07,149 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-02 12:23:07,154 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-02 12:23:07,154 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-02 12:23:07,155 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-02 12:23:07,155 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-02 12:23:07,155 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-02 12:23:07,155 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-02 12:23:07,156 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-02 12:23:07,156 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-02 12:23:07,156 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-02 12:23:07,156 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-02 12:23:07,157 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-02 12:23:07,157 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-02 12:23:07,157 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-02 12:23:07,158 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-02 12:23:07,159 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-02 12:23:07,159 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-02 12:23:07,159 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-02 12:23:07,159 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-02 12:23:07,160 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-02 12:23:07,160 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-02 12:23:07,160 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-02 12:23:07,161 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-02 12:23:07,161 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-02 12:23:07,161 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-02 12:23:07,162 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-02 12:23:07,162 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-02 12:23:07,162 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_2b2d6653-a483-49fa-a776-e825e1da337a/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_2b2d6653-a483-49fa-a776-e825e1da337a/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 -> 0bb6ea6333d2c4e133ad252fe2bcbc17b832f383e2bb5defb402851de157204c [2024-11-02 12:23:07,481 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-02 12:23:07,510 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-02 12:23:07,514 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-02 12:23:07,516 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-02 12:23:07,517 INFO L274 PluginConnector]: CDTParser initialized [2024-11-02 12:23:07,519 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/../../sv-benchmarks/c/nla-digbench-scaling/bresenham-ll_unwindbound50.c Unable to find full path for "g++" [2024-11-02 12:23:09,635 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-02 12:23:09,814 INFO L384 CDTParser]: Found 1 translation units. [2024-11-02 12:23:09,814 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/sv-benchmarks/c/nla-digbench-scaling/bresenham-ll_unwindbound50.c [2024-11-02 12:23:09,822 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/data/1f6b26bd6/3d25bfa5cd214d5ab447da5a37760fb1/FLAGcc1b6cd64 [2024-11-02 12:23:09,838 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/data/1f6b26bd6/3d25bfa5cd214d5ab447da5a37760fb1 [2024-11-02 12:23:09,840 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-02 12:23:09,842 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-02 12:23:09,843 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-02 12:23:09,844 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-02 12:23:09,850 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-02 12:23:09,850 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.11 12:23:09" (1/1) ... [2024-11-02 12:23:09,852 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@25f89593 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:09, skipping insertion in model container [2024-11-02 12:23:09,852 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.11 12:23:09" (1/1) ... [2024-11-02 12:23:09,873 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-02 12:23:10,060 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_2b2d6653-a483-49fa-a776-e825e1da337a/sv-benchmarks/c/nla-digbench-scaling/bresenham-ll_unwindbound50.c[597,610] [2024-11-02 12:23:10,088 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-02 12:23:10,100 INFO L200 MainTranslator]: Completed pre-run [2024-11-02 12:23:10,113 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_2b2d6653-a483-49fa-a776-e825e1da337a/sv-benchmarks/c/nla-digbench-scaling/bresenham-ll_unwindbound50.c[597,610] [2024-11-02 12:23:10,126 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-02 12:23:10,149 INFO L204 MainTranslator]: Completed translation [2024-11-02 12:23:10,149 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10 WrapperNode [2024-11-02 12:23:10,150 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-02 12:23:10,151 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-02 12:23:10,151 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-02 12:23:10,151 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-02 12:23:10,160 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:23:10" (1/1) ... [2024-11-02 12:23:10,168 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:23:10" (1/1) ... [2024-11-02 12:23:10,186 INFO L138 Inliner]: procedures = 14, calls = 9, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 55 [2024-11-02 12:23:10,186 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-02 12:23:10,187 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-02 12:23:10,188 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-02 12:23:10,188 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-02 12:23:10,198 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,198 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,199 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,200 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,203 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,206 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,208 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,209 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,210 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-02 12:23:10,211 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-02 12:23:10,212 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-02 12:23:10,212 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-02 12:23:10,213 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (1/1) ... [2024-11-02 12:23:10,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-02 12:23:10,232 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:10,249 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/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:23:10,254 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/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:23:10,285 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-02 12:23:10,285 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-02 12:23:10,286 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-02 12:23:10,286 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-02 12:23:10,286 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-02 12:23:10,286 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-02 12:23:10,348 INFO L238 CfgBuilder]: Building ICFG [2024-11-02 12:23:10,350 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-02 12:23:10,491 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-02 12:23:10,491 INFO L287 CfgBuilder]: Performing block encoding [2024-11-02 12:23:10,558 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-02 12:23:10,558 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-02 12:23:10,559 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.11 12:23:10 BoogieIcfgContainer [2024-11-02 12:23:10,559 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-02 12:23:10,562 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-02 12:23:10,562 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-02 12:23:10,566 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-02 12:23:10,567 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.11 12:23:09" (1/3) ... [2024-11-02 12:23:10,569 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8cc18e8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.11 12:23:10, skipping insertion in model container [2024-11-02 12:23:10,570 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 12:23:10" (2/3) ... [2024-11-02 12:23:10,571 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8cc18e8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.11 12:23:10, skipping insertion in model container [2024-11-02 12:23:10,571 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.11 12:23:10" (3/3) ... [2024-11-02 12:23:10,574 INFO L112 eAbstractionObserver]: Analyzing ICFG bresenham-ll_unwindbound50.c [2024-11-02 12:23:10,595 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-02 12:23:10,595 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-02 12:23:10,674 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-02 12:23:10,680 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;@61386635, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-02 12:23:10,681 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-02 12:23:10,685 INFO L276 IsEmpty]: Start isEmpty. Operand has 15 states, 10 states have (on average 1.5) internal successors, (15), 11 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:23:10,691 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-02 12:23:10,692 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:10,692 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:10,693 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:10,698 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:10,698 INFO L85 PathProgramCache]: Analyzing trace with hash -26250642, now seen corresponding path program 1 times [2024-11-02 12:23:10,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:10,710 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1655271674] [2024-11-02 12:23:10,710 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:10,711 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:10,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:23:10,882 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1349870184] [2024-11-02 12:23:10,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:10,883 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:10,883 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:10,886 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:23:10,888 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-02 12:23:10,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:10,973 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-02 12:23:10,978 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:23:11,221 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:23:11,223 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-02 12:23:11,225 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:11,226 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1655271674] [2024-11-02 12:23:11,226 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-02 12:23:11,227 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1349870184] [2024-11-02 12:23:11,229 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1349870184] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 12:23:11,229 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 12:23:11,229 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-02 12:23:11,232 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2098527468] [2024-11-02 12:23:11,233 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 12:23:11,239 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-02 12:23:11,239 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:23:11,264 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-02 12:23:11,265 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-02 12:23:11,267 INFO L87 Difference]: Start difference. First operand has 15 states, 10 states have (on average 1.5) internal successors, (15), 11 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 6 states, 5 states have (on average 1.2) internal successors, (6), 4 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:23:11,443 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:23:11,443 INFO L93 Difference]: Finished difference Result 41 states and 58 transitions. [2024-11-02 12:23:11,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-02 12:23:11,446 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 1.2) internal successors, (6), 4 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:23:11,447 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:23:11,456 INFO L225 Difference]: With dead ends: 41 [2024-11-02 12:23:11,456 INFO L226 Difference]: Without dead ends: 24 [2024-11-02 12:23:11,462 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-02 12:23:11,467 INFO L432 NwaCegarLoop]: 8 mSDtfsCounter, 7 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-02 12:23:11,471 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 39 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-02 12:23:11,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-02 12:23:11,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 20. [2024-11-02 12:23:11,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 16 states have internal predecessors, (18), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:23:11,535 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2024-11-02 12:23:11,537 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 7 [2024-11-02 12:23:11,537 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:23:11,538 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2024-11-02 12:23:11,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 1.2) internal successors, (6), 4 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:23:11,539 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2024-11-02 12:23:11,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-02 12:23:11,542 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:11,542 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:11,563 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-02 12:23:11,743 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:11,743 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:11,744 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:11,744 INFO L85 PathProgramCache]: Analyzing trace with hash -886343683, now seen corresponding path program 1 times [2024-11-02 12:23:11,745 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:11,745 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [700929700] [2024-11-02 12:23:11,745 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:11,745 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:11,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:11,955 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:23:11,956 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:11,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [700929700] [2024-11-02 12:23:11,956 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [700929700] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 12:23:11,957 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 12:23:11,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-02 12:23:11,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [905381732] [2024-11-02 12:23:11,957 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 12:23:11,958 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-02 12:23:11,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:23:11,959 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-02 12:23:11,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-02 12:23:11,960 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:23:11,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:23:11,997 INFO L93 Difference]: Finished difference Result 28 states and 30 transitions. [2024-11-02 12:23:11,998 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-02 12:23:11,998 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-02 12:23:11,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:23:12,000 INFO L225 Difference]: With dead ends: 28 [2024-11-02 12:23:12,000 INFO L226 Difference]: Without dead ends: 20 [2024-11-02 12:23:12,001 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:23:12,004 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 0 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-02 12:23:12,005 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-02 12:23:12,007 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2024-11-02 12:23:12,012 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2024-11-02 12:23:12,015 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:23:12,017 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 22 transitions. [2024-11-02 12:23:12,018 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 22 transitions. Word has length 8 [2024-11-02 12:23:12,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:23:12,019 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 22 transitions. [2024-11-02 12:23:12,019 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-02 12:23:12,019 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 22 transitions. [2024-11-02 12:23:12,020 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-02 12:23:12,020 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:12,020 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:12,021 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-02 12:23:12,022 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:12,022 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:12,023 INFO L85 PathProgramCache]: Analyzing trace with hash 1600851875, now seen corresponding path program 1 times [2024-11-02 12:23:12,024 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:12,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [512638943] [2024-11-02 12:23:12,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:12,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:12,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:23:12,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [315062682] [2024-11-02 12:23:12,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:12,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:12,077 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:12,079 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:23:12,083 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-02 12:23:12,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:12,146 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-02 12:23:12,148 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:23:12,290 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:23:12,291 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-02 12:23:12,291 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:12,292 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [512638943] [2024-11-02 12:23:12,292 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-02 12:23:12,296 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [315062682] [2024-11-02 12:23:12,296 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [315062682] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 12:23:12,296 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 12:23:12,297 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-02 12:23:12,297 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1608725947] [2024-11-02 12:23:12,297 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 12:23:12,297 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-02 12:23:12,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:23:12,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-02 12:23:12,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-02 12:23:12,299 INFO L87 Difference]: Start difference. First operand 20 states and 22 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 2 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:23:12,412 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:23:12,412 INFO L93 Difference]: Finished difference Result 29 states and 31 transitions. [2024-11-02 12:23:12,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-02 12:23:12,413 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 2 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 14 [2024-11-02 12:23:12,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:23:12,414 INFO L225 Difference]: With dead ends: 29 [2024-11-02 12:23:12,414 INFO L226 Difference]: Without dead ends: 21 [2024-11-02 12:23:12,415 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-02 12:23:12,416 INFO L432 NwaCegarLoop]: 7 mSDtfsCounter, 4 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-02 12:23:12,417 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 35 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-02 12:23:12,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-02 12:23:12,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-11-02 12:23:12,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:23:12,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 23 transitions. [2024-11-02 12:23:12,423 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 23 transitions. Word has length 14 [2024-11-02 12:23:12,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:23:12,423 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 23 transitions. [2024-11-02 12:23:12,424 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 2 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:23:12,424 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 23 transitions. [2024-11-02 12:23:12,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-02 12:23:12,425 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:12,425 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:12,445 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-02 12:23:12,630 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-02 12:23:12,630 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:12,631 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:12,631 INFO L85 PathProgramCache]: Analyzing trace with hash 1971909778, now seen corresponding path program 1 times [2024-11-02 12:23:12,631 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:12,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1532714085] [2024-11-02 12:23:12,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:12,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:12,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:23:12,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1554335407] [2024-11-02 12:23:12,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:12,669 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:12,669 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:12,674 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:23:12,677 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-02 12:23:12,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:12,736 INFO L255 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-02 12:23:12,738 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:23:13,238 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:23:13,238 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:23:13,609 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:23:13,609 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:13,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1532714085] [2024-11-02 12:23:13,609 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-02 12:23:13,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1554335407] [2024-11-02 12:23:13,610 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1554335407] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-02 12:23:13,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1937855065] [2024-11-02 12:23:13,632 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-02 12:23:13,632 INFO L166 IcfgInterpreter]: Building call graph [2024-11-02 12:23:13,638 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-02 12:23:13,644 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-02 12:23:13,644 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-02 12:23:14,415 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 41 for LOIs [2024-11-02 12:23:14,457 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-02 12:23:17,469 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '420#(and (<= 1 |#StackHeapBarrier|) (<= ~counter~0 50) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-02 12:23:17,470 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-02 12:23:17,470 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-02 12:23:17,470 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-02 12:23:17,470 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1310673486] [2024-11-02 12:23:17,471 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-02 12:23:17,471 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-02 12:23:17,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:23:17,472 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-02 12:23:17,473 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=255, Unknown=1, NotChecked=0, Total=306 [2024-11-02 12:23:17,474 INFO L87 Difference]: Start difference. First operand 21 states and 23 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:23:17,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:23:17,898 INFO L93 Difference]: Finished difference Result 34 states and 38 transitions. [2024-11-02 12:23:17,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-02 12:23:17,899 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2024-11-02 12:23:17,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:23:17,900 INFO L225 Difference]: With dead ends: 34 [2024-11-02 12:23:17,901 INFO L226 Difference]: Without dead ends: 30 [2024-11-02 12:23:17,902 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 25 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=75, Invalid=386, Unknown=1, NotChecked=0, Total=462 [2024-11-02 12:23:17,905 INFO L432 NwaCegarLoop]: 9 mSDtfsCounter, 19 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-02 12:23:17,906 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 43 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-02 12:23:17,906 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-11-02 12:23:17,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 23. [2024-11-02 12:23:17,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 17 states have (on average 1.1176470588235294) internal successors, (19), 17 states have internal predecessors, (19), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:23:17,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2024-11-02 12:23:17,922 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 15 [2024-11-02 12:23:17,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:23:17,923 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 24 transitions. [2024-11-02 12:23:17,923 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-02 12:23:17,924 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 24 transitions. [2024-11-02 12:23:17,925 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-02 12:23:17,925 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:17,925 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:17,947 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-02 12:23:18,126 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:18,126 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:18,127 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:18,127 INFO L85 PathProgramCache]: Analyzing trace with hash 927087193, now seen corresponding path program 1 times [2024-11-02 12:23:18,127 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:18,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1684374307] [2024-11-02 12:23:18,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:18,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:18,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:18,335 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:23:18,335 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:18,335 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1684374307] [2024-11-02 12:23:18,336 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1684374307] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 12:23:18,336 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [725207996] [2024-11-02 12:23:18,336 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:18,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:18,336 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:18,339 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:23:18,340 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-02 12:23:18,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:18,398 INFO L255 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-02 12:23:18,399 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:23:18,462 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:23:18,462 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:23:18,563 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:23:18,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [725207996] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-02 12:23:18,564 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [423124308] [2024-11-02 12:23:18,566 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-02 12:23:18,566 INFO L166 IcfgInterpreter]: Building call graph [2024-11-02 12:23:18,566 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-02 12:23:18,571 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-02 12:23:18,571 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-02 12:23:19,062 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 76 for LOIs [2024-11-02 12:23:19,182 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-02 12:23:21,856 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '616#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-02 12:23:21,857 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-02 12:23:21,857 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-02 12:23:21,857 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-02 12:23:21,857 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1311758336] [2024-11-02 12:23:21,857 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-02 12:23:21,858 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-02 12:23:21,858 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:23:21,861 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-02 12:23:21,862 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=354, Unknown=0, NotChecked=0, Total=420 [2024-11-02 12:23:21,862 INFO L87 Difference]: Start difference. First operand 23 states and 24 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 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:23:22,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:23:22,035 INFO L93 Difference]: Finished difference Result 59 states and 62 transitions. [2024-11-02 12:23:22,036 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-02 12:23:22,036 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 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 16 [2024-11-02 12:23:22,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:23:22,037 INFO L225 Difference]: With dead ends: 59 [2024-11-02 12:23:22,037 INFO L226 Difference]: Without dead ends: 53 [2024-11-02 12:23:22,038 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 148 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=79, Invalid=427, Unknown=0, NotChecked=0, Total=506 [2024-11-02 12:23:22,039 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 21 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 55 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-02 12:23:22,039 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 55 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-02 12:23:22,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-11-02 12:23:22,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 41. [2024-11-02 12:23:22,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 31 states have internal predecessors, (35), 5 states have call successors, (5), 5 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-02 12:23:22,061 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 44 transitions. [2024-11-02 12:23:22,061 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 44 transitions. Word has length 16 [2024-11-02 12:23:22,061 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:23:22,061 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 44 transitions. [2024-11-02 12:23:22,062 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 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:23:22,062 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 44 transitions. [2024-11-02 12:23:22,062 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-02 12:23:22,062 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:22,063 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:22,085 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-02 12:23:22,266 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:22,267 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:22,267 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:22,267 INFO L85 PathProgramCache]: Analyzing trace with hash 1587911935, now seen corresponding path program 1 times [2024-11-02 12:23:22,268 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:22,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1077929859] [2024-11-02 12:23:22,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:22,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:22,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-02 12:23:22,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1065076413] [2024-11-02 12:23:22,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:22,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:22,354 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:22,359 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:23:22,366 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-02 12:23:22,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:22,448 INFO L255 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-02 12:23:22,450 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:23:23,215 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-02 12:23:23,215 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:23:24,024 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 10 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-02 12:23:24,025 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:24,025 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1077929859] [2024-11-02 12:23:24,025 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-02 12:23:24,025 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1065076413] [2024-11-02 12:23:24,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1065076413] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-02 12:23:24,026 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [757822334] [2024-11-02 12:23:24,028 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-02 12:23:24,029 INFO L166 IcfgInterpreter]: Building call graph [2024-11-02 12:23:24,029 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-02 12:23:24,029 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-02 12:23:24,030 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-02 12:23:24,465 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 61 for LOIs [2024-11-02 12:23:24,510 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-02 12:23:32,771 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '918#(and (<= 1 |#StackHeapBarrier|) (<= ~counter~0 50) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-02 12:23:32,771 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-02 12:23:32,772 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-02 12:23:32,772 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 17 [2024-11-02 12:23:32,772 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1952388863] [2024-11-02 12:23:32,772 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-02 12:23:32,772 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-02 12:23:32,773 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:23:32,773 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-02 12:23:32,774 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=608, Unknown=2, NotChecked=0, Total=702 [2024-11-02 12:23:32,774 INFO L87 Difference]: Start difference. First operand 41 states and 44 transitions. Second operand has 17 states, 13 states have (on average 2.076923076923077) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-02 12:23:33,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:23:33,813 INFO L93 Difference]: Finished difference Result 49 states and 51 transitions. [2024-11-02 12:23:33,814 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-02 12:23:33,814 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 13 states have (on average 2.076923076923077) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 22 [2024-11-02 12:23:33,814 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:23:33,815 INFO L225 Difference]: With dead ends: 49 [2024-11-02 12:23:33,815 INFO L226 Difference]: Without dead ends: 41 [2024-11-02 12:23:33,816 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 37 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 204 ImplicationChecksByTransitivity, 9.6s TimeCoverageRelationStatistics Valid=128, Invalid=800, Unknown=2, NotChecked=0, Total=930 [2024-11-02 12:23:33,817 INFO L432 NwaCegarLoop]: 8 mSDtfsCounter, 8 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-02 12:23:33,817 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 64 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 116 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-02 12:23:33,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-02 12:23:33,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2024-11-02 12:23:33,834 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 31 states have (on average 1.032258064516129) internal successors, (32), 31 states have internal predecessors, (32), 5 states have call successors, (5), 5 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-02 12:23:33,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 41 transitions. [2024-11-02 12:23:33,837 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 41 transitions. Word has length 22 [2024-11-02 12:23:33,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:23:33,837 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 41 transitions. [2024-11-02 12:23:33,838 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 13 states have (on average 2.076923076923077) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-02 12:23:33,838 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 41 transitions. [2024-11-02 12:23:33,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-02 12:23:33,838 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:33,839 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:33,860 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-02 12:23:34,039 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:34,039 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:34,040 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:34,040 INFO L85 PathProgramCache]: Analyzing trace with hash -1355163283, now seen corresponding path program 2 times [2024-11-02 12:23:34,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:34,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [104330013] [2024-11-02 12:23:34,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:34,040 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:34,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:34,547 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-02 12:23:34,547 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:34,547 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [104330013] [2024-11-02 12:23:34,548 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [104330013] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 12:23:34,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1938233375] [2024-11-02 12:23:34,548 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-02 12:23:34,548 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:34,549 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:34,551 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:23:34,553 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-02 12:23:34,617 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-02 12:23:34,618 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-02 12:23:34,619 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-02 12:23:34,621 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:23:34,892 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:23:34,893 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-02 12:23:35,406 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-02 12:23:35,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1938233375] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-02 12:23:35,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1168677525] [2024-11-02 12:23:35,409 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-02 12:23:35,410 INFO L166 IcfgInterpreter]: Building call graph [2024-11-02 12:23:35,410 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-02 12:23:35,411 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-02 12:23:35,411 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-02 12:23:35,802 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 76 for LOIs [2024-11-02 12:23:35,871 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-02 12:23:40,636 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1317#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-02 12:23:40,637 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-02 12:23:40,637 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-02 12:23:40,637 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-11-02 12:23:40,637 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [804563865] [2024-11-02 12:23:40,638 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-02 12:23:40,638 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-02 12:23:40,639 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 12:23:40,639 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-02 12:23:40,640 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=526, Unknown=1, NotChecked=0, Total=650 [2024-11-02 12:23:40,640 INFO L87 Difference]: Start difference. First operand 41 states and 41 transitions. Second operand has 16 states, 16 states have (on average 3.25) internal successors, (52), 16 states have internal predecessors, (52), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-02 12:23:41,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 12:23:41,514 INFO L93 Difference]: Finished difference Result 95 states and 100 transitions. [2024-11-02 12:23:41,515 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-02 12:23:41,515 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.25) internal successors, (52), 16 states have internal predecessors, (52), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 40 [2024-11-02 12:23:41,515 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 12:23:41,517 INFO L225 Difference]: With dead ends: 95 [2024-11-02 12:23:41,517 INFO L226 Difference]: Without dead ends: 89 [2024-11-02 12:23:41,518 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 304 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=223, Invalid=898, Unknown=1, NotChecked=0, Total=1122 [2024-11-02 12:23:41,519 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 41 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-02 12:23:41,519 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 66 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-02 12:23:41,520 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2024-11-02 12:23:41,551 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2024-11-02 12:23:41,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 67 states have (on average 1.0149253731343284) internal successors, (68), 67 states have internal predecessors, (68), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-02 12:23:41,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 89 transitions. [2024-11-02 12:23:41,552 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 89 transitions. Word has length 40 [2024-11-02 12:23:41,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 12:23:41,553 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 89 transitions. [2024-11-02 12:23:41,553 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.25) internal successors, (52), 16 states have internal predecessors, (52), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-02 12:23:41,553 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 89 transitions. [2024-11-02 12:23:41,555 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2024-11-02 12:23:41,555 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 12:23:41,555 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1] [2024-11-02 12:23:41,570 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-02 12:23:41,756 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-02 12:23:41,756 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 12:23:41,757 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 12:23:41,757 INFO L85 PathProgramCache]: Analyzing trace with hash 1093149589, now seen corresponding path program 3 times [2024-11-02 12:23:41,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 12:23:41,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2082942505] [2024-11-02 12:23:41,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 12:23:41,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 12:23:41,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 12:23:42,990 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-02 12:23:42,990 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 12:23:42,991 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2082942505] [2024-11-02 12:23:42,991 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2082942505] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 12:23:42,991 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1753602788] [2024-11-02 12:23:42,991 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-02 12:23:42,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 12:23:42,992 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 12:23:42,994 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 12:23:42,995 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b2d6653-a483-49fa-a776-e825e1da337a/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-02 12:23:43,092 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-02 12:23:43,093 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-02 12:23:43,095 INFO L255 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-02 12:23:43,098 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 12:23:43,600 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 12:23:43,601 INFO L311 TraceCheckSpWp]: Computing backward predicates...