./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench/egcd2-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 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_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench/egcd2-ll.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:51:36,008 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:51:36,136 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:51:36,154 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:51:36,155 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:51:36,194 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:51:36,194 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:51:36,195 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:51:36,196 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:51:36,203 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:51:36,204 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:51:36,205 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:51:36,206 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:51:36,208 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:51:36,208 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:51:36,209 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:51:36,209 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:51:36,210 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:51:36,210 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:51:36,211 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:51:36,211 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:51:36,212 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:51:36,212 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:51:36,213 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:51:36,213 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:51:36,214 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:51:36,214 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:51:36,214 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:51:36,215 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:51:36,215 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:51:36,216 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:51:36,217 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:51:36,217 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:51:36,217 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:51:36,217 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:51:36,218 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:51:36,218 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:51:36,218 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:51:36,218 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:51:36,219 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:51:36,219 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:51:36,219 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:51:36,219 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:51:36,220 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:51:36,220 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:51:36,221 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/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_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 [2023-11-12 00:51:36,595 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:51:36,626 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:51:36,628 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:51:36,630 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:51:36,631 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:51:36,633 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench/egcd2-ll.c [2023-11-12 00:51:39,778 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:51:40,073 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:51:40,074 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/sv-benchmarks/c/nla-digbench/egcd2-ll.c [2023-11-12 00:51:40,085 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/data/d319d95f3/90e0b41c48c44fdc8818877b7883c336/FLAGc83fef10b [2023-11-12 00:51:40,104 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/data/d319d95f3/90e0b41c48c44fdc8818877b7883c336 [2023-11-12 00:51:40,116 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:51:40,118 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:51:40,120 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:51:40,120 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:51:40,126 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:51:40,127 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,128 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1f8d71c4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40, skipping insertion in model container [2023-11-12 00:51:40,128 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,154 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:51:40,326 WARN L240 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_b327999d-eca8-4ff6-9a54-b915a99d9623/sv-benchmarks/c/nla-digbench/egcd2-ll.c[490,503] [2023-11-12 00:51:40,348 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:51:40,360 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:51:40,374 WARN L240 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_b327999d-eca8-4ff6-9a54-b915a99d9623/sv-benchmarks/c/nla-digbench/egcd2-ll.c[490,503] [2023-11-12 00:51:40,385 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:51:40,401 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:51:40,401 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40 WrapperNode [2023-11-12 00:51:40,402 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:51:40,403 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:51:40,403 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:51:40,403 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:51:40,412 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,426 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,450 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2023-11-12 00:51:40,450 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:51:40,451 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:51:40,452 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:51:40,452 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:51:40,462 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,462 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,464 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,465 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,469 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,473 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,475 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,487 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,489 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:51:40,490 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:51:40,491 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:51:40,491 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:51:40,492 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (1/1) ... [2023-11-12 00:51:40,508 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:51:40,522 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:40,537 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:51:40,540 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:51:40,576 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:51:40,576 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-12 00:51:40,577 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-12 00:51:40,577 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:51:40,577 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:51:40,577 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:51:40,580 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:51:40,581 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:51:40,666 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:51:40,668 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:51:40,879 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:51:40,940 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:51:40,940 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 00:51:40,956 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:51:40 BoogieIcfgContainer [2023-11-12 00:51:40,956 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:51:40,959 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:51:40,959 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:51:40,963 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:51:40,963 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:51:40" (1/3) ... [2023-11-12 00:51:40,964 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54ead024 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:51:40, skipping insertion in model container [2023-11-12 00:51:40,964 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:51:40" (2/3) ... [2023-11-12 00:51:40,965 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54ead024 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:51:40, skipping insertion in model container [2023-11-12 00:51:40,965 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:51:40" (3/3) ... [2023-11-12 00:51:40,966 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll.c [2023-11-12 00:51:40,989 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:51:40,989 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:51:41,037 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:51:41,045 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=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@4fb4e243, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:51:41,047 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:51:41,052 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 15 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) [2023-11-12 00:51:41,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-11-12 00:51:41,060 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:41,061 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:41,062 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:41,067 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:41,068 INFO L85 PathProgramCache]: Analyzing trace with hash 1444820577, now seen corresponding path program 1 times [2023-11-12 00:51:41,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:41,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2017791655] [2023-11-12 00:51:41,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:41,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:41,188 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:41,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1979483951] [2023-11-12 00:51:41,189 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:41,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:41,189 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:41,193 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:41,202 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:51:41,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:41,305 INFO L262 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 1 conjunts are in the unsatisfiable core [2023-11-12 00:51:41,311 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:41,338 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:51:41,339 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:51:41,339 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:41,340 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2017791655] [2023-11-12 00:51:41,340 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:41,340 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1979483951] [2023-11-12 00:51:41,341 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1979483951] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:51:41,341 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:51:41,342 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-12 00:51:41,344 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1610347143] [2023-11-12 00:51:41,345 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:51:41,350 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-12 00:51:41,350 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:41,380 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-12 00:51:41,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-12 00:51:41,383 INFO L87 Difference]: Start difference. First operand has 27 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 15 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 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:51:41,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:41,417 INFO L93 Difference]: Finished difference Result 46 states and 73 transitions. [2023-11-12 00:51:41,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-12 00:51:41,420 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 19 [2023-11-12 00:51:41,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:41,428 INFO L225 Difference]: With dead ends: 46 [2023-11-12 00:51:41,429 INFO L226 Difference]: Without dead ends: 25 [2023-11-12 00:51:41,432 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-12 00:51:41,437 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:41,438 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 33 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:51:41,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2023-11-12 00:51:41,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2023-11-12 00:51:41,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 12 states have (on average 1.25) internal successors, (15), 14 states have internal predecessors, (15), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:51:41,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 34 transitions. [2023-11-12 00:51:41,483 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 34 transitions. Word has length 19 [2023-11-12 00:51:41,484 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:41,485 INFO L495 AbstractCegarLoop]: Abstraction has 25 states and 34 transitions. [2023-11-12 00:51:41,485 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:51:41,485 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 34 transitions. [2023-11-12 00:51:41,487 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2023-11-12 00:51:41,487 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:41,487 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:41,499 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:41,694 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-11-12 00:51:41,694 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:41,695 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:41,695 INFO L85 PathProgramCache]: Analyzing trace with hash -599376077, now seen corresponding path program 1 times [2023-11-12 00:51:41,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:41,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1058965329] [2023-11-12 00:51:41,696 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:41,696 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:41,714 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:41,714 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1662338539] [2023-11-12 00:51:41,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:41,715 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:41,715 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:41,716 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:41,735 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:51:41,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:41,785 INFO L262 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-12 00:51:41,788 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:41,870 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:51:41,871 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:41,950 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:51:41,950 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:41,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1058965329] [2023-11-12 00:51:41,951 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:41,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1662338539] [2023-11-12 00:51:41,951 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1662338539] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:51:41,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [54243932] [2023-11-12 00:51:41,974 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-12 00:51:41,974 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:51:41,979 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:51:41,985 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:51:41,986 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:51:43,440 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2023-11-12 00:51:43,442 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:51:44,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [54243932] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:51:44,293 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:51:44,293 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [5, 5] total 13 [2023-11-12 00:51:44,294 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [102397149] [2023-11-12 00:51:44,294 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:51:44,295 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 00:51:44,295 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:44,296 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 00:51:44,297 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=103, Unknown=0, NotChecked=0, Total=156 [2023-11-12 00:51:44,297 INFO L87 Difference]: Start difference. First operand 25 states and 34 transitions. Second operand has 10 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-12 00:51:44,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:44,503 INFO L93 Difference]: Finished difference Result 35 states and 45 transitions. [2023-11-12 00:51:44,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 00:51:44,504 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 20 [2023-11-12 00:51:44,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:44,505 INFO L225 Difference]: With dead ends: 35 [2023-11-12 00:51:44,505 INFO L226 Difference]: Without dead ends: 27 [2023-11-12 00:51:44,506 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 45 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=53, Invalid=103, Unknown=0, NotChecked=0, Total=156 [2023-11-12 00:51:44,508 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 13 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:44,508 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 51 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:51:44,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-11-12 00:51:44,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-11-12 00:51:44,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:51:44,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 36 transitions. [2023-11-12 00:51:44,542 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 36 transitions. Word has length 20 [2023-11-12 00:51:44,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:44,544 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 36 transitions. [2023-11-12 00:51:44,545 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-12 00:51:44,546 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 36 transitions. [2023-11-12 00:51:44,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2023-11-12 00:51:44,549 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:44,549 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:44,564 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:44,756 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-11-12 00:51:44,756 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:44,757 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:44,758 INFO L85 PathProgramCache]: Analyzing trace with hash -1396531969, now seen corresponding path program 1 times [2023-11-12 00:51:44,758 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:44,758 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [50404891] [2023-11-12 00:51:44,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:44,759 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:44,783 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:44,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1125227883] [2023-11-12 00:51:44,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:44,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:44,786 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:44,787 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:44,793 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:51:44,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:44,850 INFO L262 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 00:51:44,853 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:44,934 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:51:44,934 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:45,013 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:51:45,013 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:45,013 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [50404891] [2023-11-12 00:51:45,014 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:45,014 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1125227883] [2023-11-12 00:51:45,014 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1125227883] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-12 00:51:45,014 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:51:45,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 11 [2023-11-12 00:51:45,015 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1889579002] [2023-11-12 00:51:45,015 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:51:45,015 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:51:45,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:45,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:51:45,017 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2023-11-12 00:51:45,017 INFO L87 Difference]: Start difference. First operand 27 states and 36 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:51:45,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:45,395 INFO L93 Difference]: Finished difference Result 33 states and 41 transitions. [2023-11-12 00:51:45,395 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:51:45,395 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 21 [2023-11-12 00:51:45,396 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:45,397 INFO L225 Difference]: With dead ends: 33 [2023-11-12 00:51:45,397 INFO L226 Difference]: Without dead ends: 31 [2023-11-12 00:51:45,397 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-11-12 00:51:45,399 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 7 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:45,399 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 90 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 00:51:45,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-11-12 00:51:45,414 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2023-11-12 00:51:45,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 18 states have internal predecessors, (20), 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) [2023-11-12 00:51:45,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 39 transitions. [2023-11-12 00:51:45,416 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 39 transitions. Word has length 21 [2023-11-12 00:51:45,416 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:45,416 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 39 transitions. [2023-11-12 00:51:45,416 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:51:45,417 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 39 transitions. [2023-11-12 00:51:45,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-11-12 00:51:45,418 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:45,418 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:45,424 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:45,624 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:45,624 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:45,625 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:45,625 INFO L85 PathProgramCache]: Analyzing trace with hash -112873217, now seen corresponding path program 1 times [2023-11-12 00:51:45,625 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:45,625 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2025205972] [2023-11-12 00:51:45,625 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:45,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:45,638 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:45,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1761519965] [2023-11-12 00:51:45,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:45,638 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:45,639 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:45,640 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:45,646 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:51:45,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:45,722 INFO L262 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:51:45,727 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:45,928 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:51:45,928 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:46,074 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:51:46,075 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:46,075 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2025205972] [2023-11-12 00:51:46,075 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:46,075 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1761519965] [2023-11-12 00:51:46,077 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1761519965] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-12 00:51:46,077 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:51:46,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 12 [2023-11-12 00:51:46,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1420039003] [2023-11-12 00:51:46,079 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:51:46,079 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:51:46,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:46,080 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:51:46,080 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-11-12 00:51:46,082 INFO L87 Difference]: Start difference. First operand 31 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 00:51:46,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:46,162 INFO L93 Difference]: Finished difference Result 44 states and 56 transitions. [2023-11-12 00:51:46,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:51:46,163 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 26 [2023-11-12 00:51:46,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:46,165 INFO L225 Difference]: With dead ends: 44 [2023-11-12 00:51:46,165 INFO L226 Difference]: Without dead ends: 42 [2023-11-12 00:51:46,166 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2023-11-12 00:51:46,169 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:46,171 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 105 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:51:46,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2023-11-12 00:51:46,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2023-11-12 00:51:46,202 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-11-12 00:51:46,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 53 transitions. [2023-11-12 00:51:46,209 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 53 transitions. Word has length 26 [2023-11-12 00:51:46,209 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:46,209 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 53 transitions. [2023-11-12 00:51:46,209 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 00:51:46,209 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 53 transitions. [2023-11-12 00:51:46,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2023-11-12 00:51:46,211 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:46,211 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:46,223 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:46,418 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:46,418 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:46,419 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:46,419 INFO L85 PathProgramCache]: Analyzing trace with hash 665597119, now seen corresponding path program 1 times [2023-11-12 00:51:46,419 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:46,419 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [804799416] [2023-11-12 00:51:46,419 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:46,419 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:46,431 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:46,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [459984528] [2023-11-12 00:51:46,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:46,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:46,431 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:46,433 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:46,451 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:51:46,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:46,493 INFO L262 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:51:46,496 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:46,692 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-11-12 00:51:46,692 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:46,873 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-11-12 00:51:46,873 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:46,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [804799416] [2023-11-12 00:51:46,873 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:46,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [459984528] [2023-11-12 00:51:46,874 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [459984528] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-12 00:51:46,874 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:51:46,874 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 12 [2023-11-12 00:51:46,874 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [810272736] [2023-11-12 00:51:46,875 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:51:46,875 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:51:46,875 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:46,876 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:51:46,876 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-11-12 00:51:46,876 INFO L87 Difference]: Start difference. First operand 41 states and 53 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-12 00:51:46,955 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:46,955 INFO L93 Difference]: Finished difference Result 48 states and 59 transitions. [2023-11-12 00:51:46,955 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:51:46,956 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 31 [2023-11-12 00:51:46,956 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:46,957 INFO L225 Difference]: With dead ends: 48 [2023-11-12 00:51:46,957 INFO L226 Difference]: Without dead ends: 46 [2023-11-12 00:51:46,957 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2023-11-12 00:51:46,958 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 6 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 96 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.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:46,959 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 96 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:51:46,959 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-11-12 00:51:46,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2023-11-12 00:51:46,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 25 states have (on average 1.16) internal successors, (29), 26 states have internal predecessors, (29), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-11-12 00:51:46,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 56 transitions. [2023-11-12 00:51:46,977 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 56 transitions. Word has length 31 [2023-11-12 00:51:46,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:46,978 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 56 transitions. [2023-11-12 00:51:46,978 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-12 00:51:46,978 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 56 transitions. [2023-11-12 00:51:46,979 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-12 00:51:46,979 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:46,979 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:46,995 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:47,190 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:47,191 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:47,192 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:47,192 INFO L85 PathProgramCache]: Analyzing trace with hash -610328385, now seen corresponding path program 1 times [2023-11-12 00:51:47,192 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:47,192 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1522083899] [2023-11-12 00:51:47,192 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:47,193 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:47,223 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:47,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [10034197] [2023-11-12 00:51:47,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:47,224 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:47,224 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:47,231 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:47,240 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:51:47,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:47,297 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-12 00:51:47,299 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:47,471 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-12 00:51:47,471 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:47,652 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:47,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1522083899] [2023-11-12 00:51:47,652 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:47,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [10034197] [2023-11-12 00:51:47,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [10034197] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:51:47,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [31078216] [2023-11-12 00:51:47,656 INFO L159 IcfgInterpreter]: Started Sifa with 21 locations of interest [2023-11-12 00:51:47,656 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:51:47,656 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:51:47,657 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:51:47,657 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:51:49,078 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:51:49,083 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2023-11-12 00:51:49,084 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:51:53,161 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [31078216] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:51:53,161 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:51:53,161 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [7] total 18 [2023-11-12 00:51:53,161 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [17130649] [2023-11-12 00:51:53,162 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:51:53,162 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:51:53,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:53,163 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:51:53,163 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:51:53,163 INFO L87 Difference]: Start difference. First operand 45 states and 56 transitions. Second operand has 13 states, 8 states have (on average 1.375) internal successors, (11), 7 states have internal predecessors, (11), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-12 00:51:53,695 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:53,696 INFO L93 Difference]: Finished difference Result 70 states and 82 transitions. [2023-11-12 00:51:53,696 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-12 00:51:53,697 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 8 states have (on average 1.375) internal successors, (11), 7 states have internal predecessors, (11), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 36 [2023-11-12 00:51:53,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:53,705 INFO L225 Difference]: With dead ends: 70 [2023-11-12 00:51:53,705 INFO L226 Difference]: Without dead ends: 68 [2023-11-12 00:51:53,706 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 54 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:51:53,707 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 26 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 169 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:53,708 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 46 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 169 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 00:51:53,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2023-11-12 00:51:53,743 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 66. [2023-11-12 00:51:53,744 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 38 states have (on average 1.105263157894737) internal successors, (42), 40 states have internal predecessors, (42), 18 states have call successors, (18), 9 states have call predecessors, (18), 9 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-12 00:51:53,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 77 transitions. [2023-11-12 00:51:53,746 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 77 transitions. Word has length 36 [2023-11-12 00:51:53,747 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:53,747 INFO L495 AbstractCegarLoop]: Abstraction has 66 states and 77 transitions. [2023-11-12 00:51:53,747 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 8 states have (on average 1.375) internal successors, (11), 7 states have internal predecessors, (11), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-12 00:51:53,747 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 77 transitions. [2023-11-12 00:51:53,749 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-11-12 00:51:53,749 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:53,749 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:53,759 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:53,955 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:53,955 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:53,956 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:53,956 INFO L85 PathProgramCache]: Analyzing trace with hash 1276270888, now seen corresponding path program 1 times [2023-11-12 00:51:53,956 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:53,956 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1680012679] [2023-11-12 00:51:53,956 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:53,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:53,967 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:53,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [323338346] [2023-11-12 00:51:53,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:53,971 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:53,971 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:53,972 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:53,991 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:51:54,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:54,042 INFO L262 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-12 00:51:54,044 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:54,101 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2023-11-12 00:51:54,102 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:54,191 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2023-11-12 00:51:54,191 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:54,192 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1680012679] [2023-11-12 00:51:54,192 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:54,192 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [323338346] [2023-11-12 00:51:54,192 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [323338346] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:51:54,192 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [556288613] [2023-11-12 00:51:54,195 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-11-12 00:51:54,195 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:51:54,196 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:51:54,196 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:51:54,196 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:51:59,769 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:51:59,774 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2023-11-12 00:51:59,775 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:52:07,842 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1883#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:52:07,843 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:52:07,843 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:52:07,843 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2023-11-12 00:52:07,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2118216243] [2023-11-12 00:52:07,843 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:52:07,844 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-12 00:52:07,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:52:07,845 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-12 00:52:07,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=318, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:52:07,845 INFO L87 Difference]: Start difference. First operand 66 states and 77 transitions. Second operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-11-12 00:52:08,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:52:08,057 INFO L93 Difference]: Finished difference Result 108 states and 143 transitions. [2023-11-12 00:52:08,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:52:08,062 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 45 [2023-11-12 00:52:08,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:52:08,064 INFO L225 Difference]: With dead ends: 108 [2023-11-12 00:52:08,064 INFO L226 Difference]: Without dead ends: 100 [2023-11-12 00:52:08,065 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 101 SyntacticMatches, 13 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 228 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=143, Invalid=457, Unknown=0, NotChecked=0, Total=600 [2023-11-12 00:52:08,065 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 34 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:52:08,066 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 187 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:52:08,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2023-11-12 00:52:08,097 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 91. [2023-11-12 00:52:08,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 51 states have (on average 1.1764705882352942) internal successors, (60), 52 states have internal predecessors, (60), 30 states have call successors, (30), 9 states have call predecessors, (30), 9 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2023-11-12 00:52:08,099 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 119 transitions. [2023-11-12 00:52:08,099 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 119 transitions. Word has length 45 [2023-11-12 00:52:08,099 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:52:08,100 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 119 transitions. [2023-11-12 00:52:08,100 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-11-12 00:52:08,100 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 119 transitions. [2023-11-12 00:52:08,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-11-12 00:52:08,101 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:52:08,101 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:52:08,107 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-11-12 00:52:08,306 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:52:08,306 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:52:08,307 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:52:08,307 INFO L85 PathProgramCache]: Analyzing trace with hash 2083634996, now seen corresponding path program 1 times [2023-11-12 00:52:08,307 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:52:08,307 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [49261294] [2023-11-12 00:52:08,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:52:08,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:52:08,317 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:52:08,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1212972626] [2023-11-12 00:52:08,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:52:08,318 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:52:08,318 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:52:08,319 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:52:08,337 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:52:08,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:52:08,386 INFO L262 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 24 conjunts are in the unsatisfiable core [2023-11-12 00:52:08,389 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:52:08,477 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 28 proven. 5 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2023-11-12 00:52:08,477 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:52:08,597 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-11-12 00:52:08,597 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:52:08,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [49261294] [2023-11-12 00:52:08,597 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:52:08,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1212972626] [2023-11-12 00:52:08,598 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1212972626] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:52:08,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [954647861] [2023-11-12 00:52:08,601 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2023-11-12 00:52:08,601 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:52:08,601 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:52:08,601 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:52:08,601 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:52:13,430 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:52:13,435 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2023-11-12 00:52:13,436 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:52:22,178 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2522#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:52:22,179 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:52:22,179 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:52:22,179 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 10 [2023-11-12 00:52:22,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [587253449] [2023-11-12 00:52:22,179 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:52:22,180 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 00:52:22,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:52:22,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 00:52:22,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=442, Unknown=0, NotChecked=0, Total=552 [2023-11-12 00:52:22,181 INFO L87 Difference]: Start difference. First operand 91 states and 119 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 9 states have internal predecessors, (24), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 00:52:22,412 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:52:22,413 INFO L93 Difference]: Finished difference Result 101 states and 131 transitions. [2023-11-12 00:52:22,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:52:22,413 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 9 states have internal predecessors, (24), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 51 [2023-11-12 00:52:22,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:52:22,416 INFO L225 Difference]: With dead ends: 101 [2023-11-12 00:52:22,416 INFO L226 Difference]: Without dead ends: 98 [2023-11-12 00:52:22,417 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 119 SyntacticMatches, 11 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 346 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=136, Invalid=566, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:52:22,418 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 17 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:52:22,419 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 115 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:52:22,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2023-11-12 00:52:22,457 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 98. [2023-11-12 00:52:22,457 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 55 states have (on average 1.1636363636363636) internal successors, (64), 57 states have internal predecessors, (64), 32 states have call successors, (32), 10 states have call predecessors, (32), 10 states have return successors, (31), 30 states have call predecessors, (31), 31 states have call successors, (31) [2023-11-12 00:52:22,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 127 transitions. [2023-11-12 00:52:22,459 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 127 transitions. Word has length 51 [2023-11-12 00:52:22,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:52:22,460 INFO L495 AbstractCegarLoop]: Abstraction has 98 states and 127 transitions. [2023-11-12 00:52:22,460 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 9 states have internal predecessors, (24), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 00:52:22,460 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 127 transitions. [2023-11-12 00:52:22,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-11-12 00:52:22,462 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:52:22,462 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 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] [2023-11-12 00:52:22,471 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 00:52:22,667 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-12 00:52:22,667 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:52:22,668 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:52:22,668 INFO L85 PathProgramCache]: Analyzing trace with hash -695615574, now seen corresponding path program 2 times [2023-11-12 00:52:22,668 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:52:22,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [637858141] [2023-11-12 00:52:22,668 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:52:22,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:52:22,678 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:52:22,678 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [241974389] [2023-11-12 00:52:22,678 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:52:22,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:52:22,678 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:52:22,680 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:52:22,703 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b327999d-eca8-4ff6-9a54-b915a99d9623/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 00:52:22,762 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-11-12 00:52:22,762 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:52:22,764 INFO L262 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 39 conjunts are in the unsatisfiable core [2023-11-12 00:52:22,767 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:52:23,168 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 14 proven. 8 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2023-11-12 00:52:23,169 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:52:23,501 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2023-11-12 00:52:23,502 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:52:23,502 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [637858141] [2023-11-12 00:52:23,502 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:52:23,502 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [241974389] [2023-11-12 00:52:23,502 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [241974389] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:52:23,502 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2114350242] [2023-11-12 00:52:23,505 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2023-11-12 00:52:23,505 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:52:23,506 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:52:23,506 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:52:23,506 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:52:27,266 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:52:27,275 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2023-11-12 00:52:27,276 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:52:33,938 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3195#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:52:33,938 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:52:33,939 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:52:33,939 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 16 [2023-11-12 00:52:33,939 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1958108299] [2023-11-12 00:52:33,939 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:52:33,940 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-11-12 00:52:33,940 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:52:33,941 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-11-12 00:52:33,942 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=726, Unknown=0, NotChecked=0, Total=870 [2023-11-12 00:52:33,942 INFO L87 Difference]: Start difference. First operand 98 states and 127 transitions. Second operand has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 8 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20)