./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8393723b Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS --witnessprinter.witness.filename witness.graphml --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 a93c350e5795e32421c3bef9d7525c3fd53f570f971d574def19132b3d6f08b8 --- Real Ultimate output --- [0.001s][warning][os,container] Duplicate cpuset controllers detected. Picking /sys/fs/cgroup/cpuset, skipping /sys/fs/cgroup/cpuset. This is Ultimate 0.2.2-dev-8393723 [2022-11-19 06:49:59,640 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-11-19 06:49:59,643 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-11-19 06:49:59,683 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-11-19 06:49:59,684 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-11-19 06:49:59,685 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-11-19 06:49:59,686 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-11-19 06:49:59,688 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-11-19 06:49:59,690 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-11-19 06:49:59,691 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-11-19 06:49:59,692 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-11-19 06:49:59,693 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-11-19 06:49:59,693 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-11-19 06:49:59,694 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-11-19 06:49:59,695 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-11-19 06:49:59,697 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-11-19 06:49:59,698 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-11-19 06:49:59,708 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-11-19 06:49:59,712 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-11-19 06:49:59,720 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-11-19 06:49:59,722 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-11-19 06:49:59,725 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-11-19 06:49:59,726 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-11-19 06:49:59,726 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-11-19 06:49:59,730 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-11-19 06:49:59,730 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-11-19 06:49:59,730 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-11-19 06:49:59,739 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-11-19 06:49:59,740 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-11-19 06:49:59,741 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-11-19 06:49:59,741 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-11-19 06:49:59,742 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-11-19 06:49:59,744 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-11-19 06:49:59,745 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-11-19 06:49:59,747 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-11-19 06:49:59,747 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-11-19 06:49:59,747 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-11-19 06:49:59,748 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-11-19 06:49:59,748 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-11-19 06:49:59,749 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-11-19 06:49:59,749 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-11-19 06:49:59,750 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/config/svcomp-Reach-32bit-Taipan_Default.epf [2022-11-19 06:49:59,799 INFO L113 SettingsManager]: Loading preferences was successful [2022-11-19 06:49:59,799 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-11-19 06:49:59,800 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-11-19 06:49:59,800 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-11-19 06:49:59,801 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-11-19 06:49:59,801 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-11-19 06:49:59,801 INFO L138 SettingsManager]: * User list type=DISABLED [2022-11-19 06:49:59,802 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2022-11-19 06:49:59,802 INFO L138 SettingsManager]: * Explicit value domain=true [2022-11-19 06:49:59,802 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2022-11-19 06:49:59,803 INFO L138 SettingsManager]: * Octagon Domain=false [2022-11-19 06:49:59,803 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2022-11-19 06:49:59,804 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2022-11-19 06:49:59,804 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2022-11-19 06:49:59,804 INFO L138 SettingsManager]: * Interval Domain=false [2022-11-19 06:49:59,804 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2022-11-19 06:49:59,804 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2022-11-19 06:49:59,804 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2022-11-19 06:49:59,805 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-11-19 06:49:59,806 INFO L138 SettingsManager]: * sizeof long=4 [2022-11-19 06:49:59,806 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-11-19 06:49:59,806 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-11-19 06:49:59,806 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-11-19 06:49:59,808 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-11-19 06:49:59,808 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-11-19 06:49:59,808 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-11-19 06:49:59,808 INFO L138 SettingsManager]: * sizeof long double=12 [2022-11-19 06:49:59,809 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-11-19 06:49:59,809 INFO L138 SettingsManager]: * Use constant arrays=true [2022-11-19 06:49:59,809 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-11-19 06:49:59,809 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-11-19 06:49:59,810 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-11-19 06:49:59,810 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-11-19 06:49:59,810 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-11-19 06:49:59,810 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2022-11-19 06:49:59,810 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-11-19 06:49:59,811 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-11-19 06:49:59,811 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2022-11-19 06:49:59,811 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-11-19 06:49:59,811 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-11-19 06:49:59,811 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-11-19 06:49:59,812 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/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_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 -> a93c350e5795e32421c3bef9d7525c3fd53f570f971d574def19132b3d6f08b8 [2022-11-19 06:50:00,099 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-11-19 06:50:00,130 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-11-19 06:50:00,132 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-11-19 06:50:00,134 INFO L271 PluginConnector]: Initializing CDTParser... [2022-11-19 06:50:00,135 INFO L275 PluginConnector]: CDTParser initialized [2022-11-19 06:50:00,136 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound5.c [2022-11-19 06:50:00,225 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/data/49dbafd8f/6b57ccb8041048e5bf76146f67451906/FLAG553aedf26 [2022-11-19 06:50:00,750 INFO L306 CDTParser]: Found 1 translation units. [2022-11-19 06:50:00,751 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound5.c [2022-11-19 06:50:00,760 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/data/49dbafd8f/6b57ccb8041048e5bf76146f67451906/FLAG553aedf26 [2022-11-19 06:50:01,132 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/data/49dbafd8f/6b57ccb8041048e5bf76146f67451906 [2022-11-19 06:50:01,135 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-11-19 06:50:01,136 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-11-19 06:50:01,141 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-11-19 06:50:01,141 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-11-19 06:50:01,145 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-11-19 06:50:01,146 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,147 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4ce5374c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01, skipping insertion in model container [2022-11-19 06:50:01,148 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,159 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-11-19 06:50:01,178 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-11-19 06:50:01,445 WARN L234 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_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound5.c[538,551] [2022-11-19 06:50:01,470 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-11-19 06:50:01,484 INFO L203 MainTranslator]: Completed pre-run [2022-11-19 06:50:01,497 WARN L234 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_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/sv-benchmarks/c/nla-digbench-scaling/hard-ll_valuebound5.c[538,551] [2022-11-19 06:50:01,506 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-11-19 06:50:01,521 INFO L208 MainTranslator]: Completed translation [2022-11-19 06:50:01,524 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01 WrapperNode [2022-11-19 06:50:01,524 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-11-19 06:50:01,525 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-11-19 06:50:01,525 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-11-19 06:50:01,526 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-11-19 06:50:01,534 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,544 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,560 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 55 [2022-11-19 06:50:01,561 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-11-19 06:50:01,562 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-11-19 06:50:01,562 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-11-19 06:50:01,562 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-11-19 06:50:01,570 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,571 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,572 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,572 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,576 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,580 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,581 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,582 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,584 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-11-19 06:50:01,584 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-11-19 06:50:01,585 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-11-19 06:50:01,585 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-11-19 06:50:01,586 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (1/1) ... [2022-11-19 06:50:01,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-11-19 06:50:01,607 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:50:01,619 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-11-19 06:50:01,624 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-11-19 06:50:01,656 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-11-19 06:50:01,656 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-11-19 06:50:01,656 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-11-19 06:50:01,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-11-19 06:50:01,656 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-11-19 06:50:01,656 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-11-19 06:50:01,657 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-11-19 06:50:01,657 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-11-19 06:50:01,739 INFO L235 CfgBuilder]: Building ICFG [2022-11-19 06:50:01,741 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2022-11-19 06:50:01,998 INFO L276 CfgBuilder]: Performing block encoding [2022-11-19 06:50:02,032 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-11-19 06:50:02,032 INFO L300 CfgBuilder]: Removed 2 assume(true) statements. [2022-11-19 06:50:02,035 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 06:50:02 BoogieIcfgContainer [2022-11-19 06:50:02,035 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-11-19 06:50:02,037 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-11-19 06:50:02,038 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-11-19 06:50:02,041 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-11-19 06:50:02,042 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 06:50:01" (1/3) ... [2022-11-19 06:50:02,042 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3ff656e3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 06:50:02, skipping insertion in model container [2022-11-19 06:50:02,043 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 06:50:01" (2/3) ... [2022-11-19 06:50:02,043 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3ff656e3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 06:50:02, skipping insertion in model container [2022-11-19 06:50:02,043 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 06:50:02" (3/3) ... [2022-11-19 06:50:02,044 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound5.c [2022-11-19 06:50:02,062 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-11-19 06:50:02,062 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-11-19 06:50:02,141 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-11-19 06:50:02,159 INFO L357 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, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@5f976672, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2022-11-19 06:50:02,159 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-11-19 06:50:02,165 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-11-19 06:50:02,175 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-11-19 06:50:02,175 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:50:02,177 INFO L195 NwaCegarLoop]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:50:02,180 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:50:02,194 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:50:02,194 INFO L85 PathProgramCache]: Analyzing trace with hash 763440750, now seen corresponding path program 1 times [2022-11-19 06:50:02,206 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:50:02,207 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [502082310] [2022-11-19 06:50:02,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:02,208 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:50:02,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-19 06:50:02,690 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-11-19 06:50:02,691 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:50:02,691 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [502082310] [2022-11-19 06:50:02,692 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [502082310] provided 1 perfect and 0 imperfect interpolant sequences [2022-11-19 06:50:02,693 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-11-19 06:50:02,693 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-11-19 06:50:02,695 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [222347772] [2022-11-19 06:50:02,696 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-11-19 06:50:02,700 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-11-19 06:50:02,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:50:02,747 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-11-19 06:50:02,748 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-11-19 06:50:02,751 INFO L87 Difference]: Start difference. First operand has 27 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-11-19 06:50:02,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:50:02,905 INFO L93 Difference]: Finished difference Result 58 states and 96 transitions. [2022-11-19 06:50:02,907 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-11-19 06:50:02,908 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 17 [2022-11-19 06:50:02,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:50:02,917 INFO L225 Difference]: With dead ends: 58 [2022-11-19 06:50:02,917 INFO L226 Difference]: Without dead ends: 35 [2022-11-19 06:50:02,921 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-11-19 06:50:02,924 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 11 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-11-19 06:50:02,925 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 108 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-11-19 06:50:02,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-11-19 06:50:02,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 29. [2022-11-19 06:50:02,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-11-19 06:50:02,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 37 transitions. [2022-11-19 06:50:02,991 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 37 transitions. Word has length 17 [2022-11-19 06:50:02,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:50:02,991 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 37 transitions. [2022-11-19 06:50:02,992 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-11-19 06:50:02,992 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 37 transitions. [2022-11-19 06:50:02,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-11-19 06:50:02,994 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:50:02,994 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:50:02,994 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-11-19 06:50:02,995 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:50:02,995 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:50:02,996 INFO L85 PathProgramCache]: Analyzing trace with hash 1804559349, now seen corresponding path program 1 times [2022-11-19 06:50:02,996 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:50:02,996 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [578971048] [2022-11-19 06:50:02,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:02,997 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:50:03,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-19 06:50:03,141 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-11-19 06:50:03,141 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:50:03,141 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [578971048] [2022-11-19 06:50:03,141 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [578971048] provided 1 perfect and 0 imperfect interpolant sequences [2022-11-19 06:50:03,142 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-11-19 06:50:03,142 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-11-19 06:50:03,142 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [502112393] [2022-11-19 06:50:03,142 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-11-19 06:50:03,144 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-11-19 06:50:03,144 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:50:03,145 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-11-19 06:50:03,145 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-11-19 06:50:03,145 INFO L87 Difference]: Start difference. First operand 29 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-11-19 06:50:03,236 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:50:03,238 INFO L93 Difference]: Finished difference Result 41 states and 52 transitions. [2022-11-19 06:50:03,238 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-11-19 06:50:03,239 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 22 [2022-11-19 06:50:03,239 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:50:03,241 INFO L225 Difference]: With dead ends: 41 [2022-11-19 06:50:03,241 INFO L226 Difference]: Without dead ends: 39 [2022-11-19 06:50:03,242 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-11-19 06:50:03,243 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 8 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-11-19 06:50:03,244 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 100 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-11-19 06:50:03,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-11-19 06:50:03,254 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 33. [2022-11-19 06:50:03,254 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-11-19 06:50:03,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 40 transitions. [2022-11-19 06:50:03,256 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 40 transitions. Word has length 22 [2022-11-19 06:50:03,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:50:03,256 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 40 transitions. [2022-11-19 06:50:03,257 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-11-19 06:50:03,257 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 40 transitions. [2022-11-19 06:50:03,258 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-11-19 06:50:03,258 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:50:03,258 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:50:03,258 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-11-19 06:50:03,259 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:50:03,259 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:50:03,260 INFO L85 PathProgramCache]: Analyzing trace with hash 496345742, now seen corresponding path program 1 times [2022-11-19 06:50:03,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:50:03,260 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1748220724] [2022-11-19 06:50:03,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:03,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:50:03,276 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-11-19 06:50:03,277 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [880616462] [2022-11-19 06:50:03,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:03,277 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:50:03,277 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:50:03,286 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-19 06:50:03,303 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-11-19 06:50:03,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-19 06:50:03,376 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 19 conjunts are in the unsatisfiable core [2022-11-19 06:50:03,390 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-19 06:50:03,627 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-11-19 06:50:03,628 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-19 06:50:03,795 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-11-19 06:50:03,795 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:50:03,795 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1748220724] [2022-11-19 06:50:03,796 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-11-19 06:50:03,796 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [880616462] [2022-11-19 06:50:03,796 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [880616462] provided 0 perfect and 2 imperfect interpolant sequences [2022-11-19 06:50:03,796 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1599718415] [2022-11-19 06:50:03,836 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2022-11-19 06:50:03,837 INFO L166 IcfgInterpreter]: Building call graph [2022-11-19 06:50:03,841 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-19 06:50:03,846 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-19 06:50:03,847 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-19 06:50:04,404 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 38 for LOIs [2022-11-19 06:50:04,428 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2022-11-19 06:50:04,430 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-19 06:50:05,222 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSifa [1599718415] provided 1 perfect and 0 imperfect interpolant sequences [2022-11-19 06:50:05,223 INFO L184 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2022-11-19 06:50:05,223 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [8, 7] total 21 [2022-11-19 06:50:05,224 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [124819474] [2022-11-19 06:50:05,224 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-11-19 06:50:05,224 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-11-19 06:50:05,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:50:05,225 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-11-19 06:50:05,225 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2022-11-19 06:50:05,225 INFO L87 Difference]: Start difference. First operand 33 states and 40 transitions. Second operand has 11 states, 8 states have (on average 1.25) internal successors, (10), 6 states have internal predecessors, (10), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-11-19 06:50:05,755 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:50:05,755 INFO L93 Difference]: Finished difference Result 68 states and 84 transitions. [2022-11-19 06:50:05,756 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-11-19 06:50:05,756 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 8 states have (on average 1.25) internal successors, (10), 6 states have internal predecessors, (10), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 27 [2022-11-19 06:50:05,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:50:05,762 INFO L225 Difference]: With dead ends: 68 [2022-11-19 06:50:05,762 INFO L226 Difference]: Without dead ends: 50 [2022-11-19 06:50:05,763 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 54 SyntacticMatches, 6 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 172 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2022-11-19 06:50:05,768 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 53 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-11-19 06:50:05,769 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 39 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-11-19 06:50:05,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-11-19 06:50:05,819 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-11-19 06:50:05,820 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.103448275862069) internal successors, (32), 30 states have internal predecessors, (32), 13 states have call successors, (13), 7 states have call predecessors, (13), 7 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-11-19 06:50:05,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 57 transitions. [2022-11-19 06:50:05,827 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 57 transitions. Word has length 27 [2022-11-19 06:50:05,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:50:05,830 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 57 transitions. [2022-11-19 06:50:05,830 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 8 states have (on average 1.25) internal successors, (10), 6 states have internal predecessors, (10), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-11-19 06:50:05,831 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 57 transitions. [2022-11-19 06:50:05,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-11-19 06:50:05,832 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:50:05,832 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:50:05,844 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-11-19 06:50:06,038 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:50:06,038 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:50:06,039 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:50:06,039 INFO L85 PathProgramCache]: Analyzing trace with hash -202147981, now seen corresponding path program 1 times [2022-11-19 06:50:06,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:50:06,040 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [134575640] [2022-11-19 06:50:06,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:06,041 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:50:06,057 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-11-19 06:50:06,063 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1520985195] [2022-11-19 06:50:06,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:06,064 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:50:06,064 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:50:06,066 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-19 06:50:06,077 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-11-19 06:50:06,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-19 06:50:06,139 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 28 conjunts are in the unsatisfiable core [2022-11-19 06:50:06,142 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-19 06:50:06,420 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 11 proven. 17 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2022-11-19 06:50:06,421 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-19 06:50:06,649 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 11 proven. 13 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-11-19 06:50:06,649 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:50:06,649 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [134575640] [2022-11-19 06:50:06,650 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-11-19 06:50:06,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1520985195] [2022-11-19 06:50:06,650 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1520985195] provided 0 perfect and 2 imperfect interpolant sequences [2022-11-19 06:50:06,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1117823440] [2022-11-19 06:50:06,652 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2022-11-19 06:50:06,652 INFO L166 IcfgInterpreter]: Building call graph [2022-11-19 06:50:06,653 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-19 06:50:06,653 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-19 06:50:06,653 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-19 06:50:09,447 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2022-11-19 06:50:09,452 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2022-11-19 06:50:09,453 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-19 06:50:10,217 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '917#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2022-11-19 06:50:10,217 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-19 06:50:10,217 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-11-19 06:50:10,217 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 15 [2022-11-19 06:50:10,218 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1404096357] [2022-11-19 06:50:10,218 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-11-19 06:50:10,218 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-11-19 06:50:10,219 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:50:10,220 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-11-19 06:50:10,220 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=556, Unknown=0, NotChecked=0, Total=650 [2022-11-19 06:50:10,221 INFO L87 Difference]: Start difference. First operand 50 states and 57 transitions. Second operand has 15 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (14), 3 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 6 states have call successors, (13) [2022-11-19 06:50:10,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:50:10,698 INFO L93 Difference]: Finished difference Result 82 states and 104 transitions. [2022-11-19 06:50:10,699 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-11-19 06:50:10,699 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (14), 3 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 6 states have call successors, (13) Word has length 44 [2022-11-19 06:50:10,700 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:50:10,702 INFO L225 Difference]: With dead ends: 82 [2022-11-19 06:50:10,702 INFO L226 Difference]: Without dead ends: 69 [2022-11-19 06:50:10,703 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 105 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=118, Invalid=694, Unknown=0, NotChecked=0, Total=812 [2022-11-19 06:50:10,704 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 42 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 310 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 359 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 310 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-11-19 06:50:10,705 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 88 Invalid, 359 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 310 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-11-19 06:50:10,706 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-11-19 06:50:10,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2022-11-19 06:50:10,735 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 39 states have (on average 1.1025641025641026) internal successors, (43), 41 states have internal predecessors, (43), 21 states have call successors, (21), 8 states have call predecessors, (21), 8 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2022-11-19 06:50:10,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 84 transitions. [2022-11-19 06:50:10,737 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 84 transitions. Word has length 44 [2022-11-19 06:50:10,737 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:50:10,737 INFO L495 AbstractCegarLoop]: Abstraction has 69 states and 84 transitions. [2022-11-19 06:50:10,738 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (14), 3 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 6 states have call successors, (13) [2022-11-19 06:50:10,738 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 84 transitions. [2022-11-19 06:50:10,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-11-19 06:50:10,740 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:50:10,740 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:50:10,755 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-11-19 06:50:10,946 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:50:10,947 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:50:10,947 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:50:10,948 INFO L85 PathProgramCache]: Analyzing trace with hash -567180131, now seen corresponding path program 1 times [2022-11-19 06:50:10,948 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:50:10,948 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1826807891] [2022-11-19 06:50:10,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:10,949 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:50:10,968 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-11-19 06:50:10,968 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [186854682] [2022-11-19 06:50:10,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:10,969 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:50:10,969 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:50:10,970 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-19 06:50:10,989 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-11-19 06:50:11,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-19 06:50:11,073 INFO L263 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 25 conjunts are in the unsatisfiable core [2022-11-19 06:50:11,076 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-19 06:50:11,563 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 13 proven. 6 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-11-19 06:50:11,563 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-19 06:50:11,866 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-11-19 06:50:11,866 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:50:11,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1826807891] [2022-11-19 06:50:11,867 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-11-19 06:50:11,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [186854682] [2022-11-19 06:50:11,867 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [186854682] provided 0 perfect and 2 imperfect interpolant sequences [2022-11-19 06:50:11,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1911147809] [2022-11-19 06:50:11,870 INFO L159 IcfgInterpreter]: Started Sifa with 21 locations of interest [2022-11-19 06:50:11,870 INFO L166 IcfgInterpreter]: Building call graph [2022-11-19 06:50:11,870 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-19 06:50:11,871 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-19 06:50:11,871 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-19 06:50:14,129 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 25 for LOIs [2022-11-19 06:50:14,176 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2022-11-19 06:50:14,177 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-19 06:50:15,208 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1479#(and (<= |#NULL.offset| 0) (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (<= 0 |#NULL.offset|) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2022-11-19 06:50:15,208 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-19 06:50:15,208 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-11-19 06:50:15,209 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 15 [2022-11-19 06:50:15,209 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [36092352] [2022-11-19 06:50:15,209 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-11-19 06:50:15,209 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-11-19 06:50:15,210 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:50:15,210 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-11-19 06:50:15,210 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=602, Unknown=0, NotChecked=0, Total=702 [2022-11-19 06:50:15,211 INFO L87 Difference]: Start difference. First operand 69 states and 84 transitions. Second operand has 15 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 12 states have internal predecessors, (25), 8 states have call successors, (19), 3 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-11-19 06:50:15,617 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:50:15,617 INFO L93 Difference]: Finished difference Result 85 states and 98 transitions. [2022-11-19 06:50:15,618 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-11-19 06:50:15,618 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 12 states have internal predecessors, (25), 8 states have call successors, (19), 3 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 51 [2022-11-19 06:50:15,618 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:50:15,619 INFO L225 Difference]: With dead ends: 85 [2022-11-19 06:50:15,619 INFO L226 Difference]: Without dead ends: 83 [2022-11-19 06:50:15,620 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 119 SyntacticMatches, 7 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 365 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=126, Invalid=744, Unknown=0, NotChecked=0, Total=870 [2022-11-19 06:50:15,621 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 40 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 248 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 292 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 248 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-11-19 06:50:15,621 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 124 Invalid, 292 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 248 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-11-19 06:50:15,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2022-11-19 06:50:15,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 81. [2022-11-19 06:50:15,662 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 48 states have (on average 1.0833333333333333) internal successors, (52), 50 states have internal predecessors, (52), 21 states have call successors, (21), 11 states have call predecessors, (21), 11 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2022-11-19 06:50:15,663 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 93 transitions. [2022-11-19 06:50:15,663 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 93 transitions. Word has length 51 [2022-11-19 06:50:15,664 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:50:15,664 INFO L495 AbstractCegarLoop]: Abstraction has 81 states and 93 transitions. [2022-11-19 06:50:15,664 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.7857142857142858) internal successors, (25), 12 states have internal predecessors, (25), 8 states have call successors, (19), 3 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-11-19 06:50:15,664 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 93 transitions. [2022-11-19 06:50:15,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-11-19 06:50:15,669 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:50:15,669 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:50:15,679 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-11-19 06:50:15,869 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:50:15,870 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:50:15,870 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:50:15,870 INFO L85 PathProgramCache]: Analyzing trace with hash 166119996, now seen corresponding path program 1 times [2022-11-19 06:50:15,870 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:50:15,871 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2010175727] [2022-11-19 06:50:15,871 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:15,871 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:50:15,904 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-11-19 06:50:15,904 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1030584513] [2022-11-19 06:50:15,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:50:15,905 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:50:15,905 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:50:15,917 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-19 06:50:15,918 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-11-19 06:50:15,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-19 06:50:15,975 INFO L263 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 34 conjunts are in the unsatisfiable core [2022-11-19 06:50:15,978 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-19 06:50:16,733 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 38 proven. 8 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2022-11-19 06:50:16,733 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-19 06:51:03,451 WARN L233 SmtUtils]: Spent 28.19s on a formula simplification that was a NOOP. DAG size: 63 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-11-19 06:51:40,809 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 97 trivial. 0 not checked. [2022-11-19 06:51:40,809 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:51:40,809 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2010175727] [2022-11-19 06:51:40,809 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-11-19 06:51:40,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1030584513] [2022-11-19 06:51:40,810 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1030584513] provided 0 perfect and 2 imperfect interpolant sequences [2022-11-19 06:51:40,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1435585454] [2022-11-19 06:51:40,812 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2022-11-19 06:51:40,812 INFO L166 IcfgInterpreter]: Building call graph [2022-11-19 06:51:40,812 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-19 06:51:40,813 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-19 06:51:40,813 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-19 06:51:43,393 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2022-11-19 06:51:43,397 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2022-11-19 06:51:43,398 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-19 06:51:46,797 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2134#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2022-11-19 06:51:46,797 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-19 06:51:46,797 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-11-19 06:51:46,797 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 20 [2022-11-19 06:51:46,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1426260225] [2022-11-19 06:51:46,797 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-11-19 06:51:46,798 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-11-19 06:51:46,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:51:46,799 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-11-19 06:51:46,799 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=865, Unknown=0, NotChecked=0, Total=992 [2022-11-19 06:51:46,799 INFO L87 Difference]: Start difference. First operand 81 states and 93 transitions. Second operand has 20 states, 19 states have (on average 1.736842105263158) internal successors, (33), 16 states have internal predecessors, (33), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 10 states have call predecessors, (20), 7 states have call successors, (20) [2022-11-19 06:52:07,388 WARN L233 SmtUtils]: Spent 15.56s on a formula simplification. DAG size of input: 65 DAG size of output: 47 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-11-19 06:52:10,169 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:52:10,170 INFO L93 Difference]: Finished difference Result 100 states and 115 transitions. [2022-11-19 06:52:10,170 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-11-19 06:52:10,171 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 1.736842105263158) internal successors, (33), 16 states have internal predecessors, (33), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 10 states have call predecessors, (20), 7 states have call successors, (20) Word has length 63 [2022-11-19 06:52:10,171 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:52:10,172 INFO L225 Difference]: With dead ends: 100 [2022-11-19 06:52:10,172 INFO L226 Difference]: Without dead ends: 98 [2022-11-19 06:52:10,173 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 156 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 446 ImplicationChecksByTransitivity, 52.1s TimeCoverageRelationStatistics Valid=201, Invalid=1281, Unknown=0, NotChecked=0, Total=1482 [2022-11-19 06:52:10,190 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 62 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 574 mSolverCounterSat, 77 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 651 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 77 IncrementalHoareTripleChecker+Valid, 574 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2022-11-19 06:52:10,191 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 125 Invalid, 651 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [77 Valid, 574 Invalid, 0 Unknown, 0 Unchecked, 4.6s Time] [2022-11-19 06:52:10,192 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-11-19 06:52:10,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 92. [2022-11-19 06:52:10,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 56 states have (on average 1.0892857142857142) internal successors, (61), 58 states have internal predecessors, (61), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (21), 20 states have call predecessors, (21), 21 states have call successors, (21) [2022-11-19 06:52:10,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 104 transitions. [2022-11-19 06:52:10,226 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 104 transitions. Word has length 63 [2022-11-19 06:52:10,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:52:10,227 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 104 transitions. [2022-11-19 06:52:10,227 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 1.736842105263158) internal successors, (33), 16 states have internal predecessors, (33), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 10 states have call predecessors, (20), 7 states have call successors, (20) [2022-11-19 06:52:10,227 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 104 transitions. [2022-11-19 06:52:10,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-11-19 06:52:10,229 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:52:10,229 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:52:10,239 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-11-19 06:52:10,439 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-11-19 06:52:10,440 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:52:10,440 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:52:10,441 INFO L85 PathProgramCache]: Analyzing trace with hash 1987386298, now seen corresponding path program 1 times [2022-11-19 06:52:10,441 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:52:10,441 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [953738523] [2022-11-19 06:52:10,441 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:52:10,441 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:52:10,458 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-11-19 06:52:10,458 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1741020812] [2022-11-19 06:52:10,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:52:10,459 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:52:10,459 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:52:10,460 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-19 06:52:10,472 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-11-19 06:52:10,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-11-19 06:52:10,540 INFO L263 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 23 conjunts are in the unsatisfiable core [2022-11-19 06:52:10,542 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-19 06:52:10,894 INFO L134 CoverageAnalysis]: Checked inductivity of 215 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2022-11-19 06:52:10,894 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-19 06:52:11,406 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:52:11,406 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [953738523] [2022-11-19 06:52:11,407 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-11-19 06:52:11,407 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1741020812] [2022-11-19 06:52:11,407 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1741020812] provided 0 perfect and 1 imperfect interpolant sequences [2022-11-19 06:52:11,407 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2103394249] [2022-11-19 06:52:11,414 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2022-11-19 06:52:11,414 INFO L166 IcfgInterpreter]: Building call graph [2022-11-19 06:52:11,415 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-19 06:52:11,415 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-19 06:52:11,415 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-19 06:52:13,811 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2022-11-19 06:52:13,815 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2022-11-19 06:52:13,816 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-19 06:52:14,667 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2733#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2022-11-19 06:52:14,667 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-19 06:52:14,668 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-11-19 06:52:14,668 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-11-19 06:52:14,669 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1192192930] [2022-11-19 06:52:14,669 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-11-19 06:52:14,669 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-11-19 06:52:14,669 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:52:14,670 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-11-19 06:52:14,670 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=713, Unknown=0, NotChecked=0, Total=812 [2022-11-19 06:52:14,670 INFO L87 Difference]: Start difference. First operand 92 states and 104 transitions. Second operand has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2022-11-19 06:52:15,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:52:15,135 INFO L93 Difference]: Finished difference Result 102 states and 115 transitions. [2022-11-19 06:52:15,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-11-19 06:52:15,135 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) Word has length 74 [2022-11-19 06:52:15,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:52:15,137 INFO L225 Difference]: With dead ends: 102 [2022-11-19 06:52:15,137 INFO L226 Difference]: Without dead ends: 82 [2022-11-19 06:52:15,138 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 136 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 290 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=141, Invalid=1049, Unknown=0, NotChecked=0, Total=1190 [2022-11-19 06:52:15,138 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 25 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 285 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-11-19 06:52:15,139 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 136 Invalid, 285 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-11-19 06:52:15,139 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2022-11-19 06:52:15,168 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 82. [2022-11-19 06:52:15,168 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 50 states have (on average 1.06) internal successors, (53), 51 states have internal predecessors, (53), 19 states have call successors, (19), 12 states have call predecessors, (19), 12 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-11-19 06:52:15,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 90 transitions. [2022-11-19 06:52:15,169 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 90 transitions. Word has length 74 [2022-11-19 06:52:15,170 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:52:15,170 INFO L495 AbstractCegarLoop]: Abstraction has 82 states and 90 transitions. [2022-11-19 06:52:15,170 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2022-11-19 06:52:15,170 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 90 transitions. [2022-11-19 06:52:15,171 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-11-19 06:52:15,171 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:52:15,171 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:52:15,178 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-11-19 06:52:15,376 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:52:15,377 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:52:15,377 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:52:15,377 INFO L85 PathProgramCache]: Analyzing trace with hash 152662242, now seen corresponding path program 2 times [2022-11-19 06:52:15,377 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:52:15,378 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1264773836] [2022-11-19 06:52:15,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:52:15,378 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:52:15,387 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-11-19 06:52:15,388 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1116410418] [2022-11-19 06:52:15,388 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-11-19 06:52:15,388 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:52:15,388 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:52:15,389 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-19 06:52:15,431 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-11-19 06:52:15,507 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-11-19 06:52:15,507 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-11-19 06:52:15,509 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 40 conjunts are in the unsatisfiable core [2022-11-19 06:52:15,512 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-19 06:52:15,919 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 43 proven. 34 refuted. 0 times theorem prover too weak. 235 trivial. 0 not checked. [2022-11-19 06:52:15,919 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-19 06:52:17,391 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 41 proven. 29 refuted. 0 times theorem prover too weak. 242 trivial. 0 not checked. [2022-11-19 06:52:17,392 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2022-11-19 06:52:17,392 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1264773836] [2022-11-19 06:52:17,392 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-11-19 06:52:17,392 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1116410418] [2022-11-19 06:52:17,392 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1116410418] provided 0 perfect and 2 imperfect interpolant sequences [2022-11-19 06:52:17,392 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1664874624] [2022-11-19 06:52:17,394 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2022-11-19 06:52:17,394 INFO L166 IcfgInterpreter]: Building call graph [2022-11-19 06:52:17,395 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2022-11-19 06:52:17,395 INFO L176 IcfgInterpreter]: Starting interpretation [2022-11-19 06:52:17,395 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2022-11-19 06:52:19,536 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2022-11-19 06:52:19,540 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2022-11-19 06:52:19,541 INFO L180 IcfgInterpreter]: Interpretation finished [2022-11-19 06:52:20,527 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3548#(and (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2022-11-19 06:52:20,527 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2022-11-19 06:52:20,528 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-11-19 06:52:20,528 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 18 [2022-11-19 06:52:20,528 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1950391601] [2022-11-19 06:52:20,528 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-11-19 06:52:20,528 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-11-19 06:52:20,529 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2022-11-19 06:52:20,529 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-11-19 06:52:20,529 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=757, Unknown=0, NotChecked=0, Total=870 [2022-11-19 06:52:20,530 INFO L87 Difference]: Start difference. First operand 82 states and 90 transitions. Second operand has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (26), 3 states have call predecessors, (26), 3 states have return successors, (25), 9 states have call predecessors, (25), 9 states have call successors, (25) [2022-11-19 06:52:23,735 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-11-19 06:52:23,735 INFO L93 Difference]: Finished difference Result 108 states and 124 transitions. [2022-11-19 06:52:23,735 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-11-19 06:52:23,736 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (26), 3 states have call predecessors, (26), 3 states have return successors, (25), 9 states have call predecessors, (25), 9 states have call successors, (25) Word has length 85 [2022-11-19 06:52:23,736 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-11-19 06:52:23,737 INFO L225 Difference]: With dead ends: 108 [2022-11-19 06:52:23,737 INFO L226 Difference]: Without dead ends: 106 [2022-11-19 06:52:23,738 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 257 GetRequests, 223 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 346 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=149, Invalid=973, Unknown=0, NotChecked=0, Total=1122 [2022-11-19 06:52:23,739 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 53 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 480 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 555 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 480 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2022-11-19 06:52:23,739 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 119 Invalid, 555 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 480 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2022-11-19 06:52:23,740 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2022-11-19 06:52:23,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 106. [2022-11-19 06:52:23,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 63 states have (on average 1.0634920634920635) internal successors, (67), 65 states have internal predecessors, (67), 28 states have call successors, (28), 14 states have call predecessors, (28), 14 states have return successors, (27), 26 states have call predecessors, (27), 27 states have call successors, (27) [2022-11-19 06:52:23,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 122 transitions. [2022-11-19 06:52:23,773 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 122 transitions. Word has length 85 [2022-11-19 06:52:23,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-11-19 06:52:23,773 INFO L495 AbstractCegarLoop]: Abstraction has 106 states and 122 transitions. [2022-11-19 06:52:23,773 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (26), 3 states have call predecessors, (26), 3 states have return successors, (25), 9 states have call predecessors, (25), 9 states have call successors, (25) [2022-11-19 06:52:23,773 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 122 transitions. [2022-11-19 06:52:23,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2022-11-19 06:52:23,775 INFO L187 NwaCegarLoop]: Found error trace [2022-11-19 06:52:23,775 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-11-19 06:52:23,780 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-11-19 06:52:23,978 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:52:23,978 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-11-19 06:52:23,979 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-11-19 06:52:23,979 INFO L85 PathProgramCache]: Analyzing trace with hash 339357760, now seen corresponding path program 3 times [2022-11-19 06:52:23,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2022-11-19 06:52:23,979 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [842327710] [2022-11-19 06:52:23,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-11-19 06:52:23,979 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-11-19 06:52:23,990 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-11-19 06:52:23,990 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [180468433] [2022-11-19 06:52:23,990 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-11-19 06:52:23,990 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-11-19 06:52:23,991 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 [2022-11-19 06:52:23,992 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-11-19 06:52:24,028 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c8bc318c-5d38-4ac5-8359-28d9eb1c8bf8/bin/utaipan-I9t0OCRTmS/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-11-19 06:52:24,132 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-11-19 06:52:24,132 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-11-19 06:52:24,134 INFO L263 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 50 conjunts are in the unsatisfiable core [2022-11-19 06:52:24,137 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-11-19 06:52:25,177 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 72 proven. 45 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2022-11-19 06:52:25,177 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-11-19 06:52:59,975 WARN L233 SmtUtils]: Spent 6.50s on a formula simplification that was a NOOP. DAG size: 163 (called from [L 361] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-11-19 06:58:20,944 WARN L233 SmtUtils]: Spent 26.09s on a formula simplification. DAG size of input: 6309 DAG size of output: 6247 (called from [L 800] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)