./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc 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_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/config/AutomizerReach.xml -i ../../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya --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 Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-11-29 03:42:44,631 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-29 03:42:44,696 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-11-29 03:42:44,701 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-29 03:42:44,701 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-29 03:42:44,724 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-29 03:42:44,725 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-29 03:42:44,725 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-29 03:42:44,726 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-11-29 03:42:44,727 INFO L153 SettingsManager]: * Use memory slicer=true [2023-11-29 03:42:44,727 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-29 03:42:44,728 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-29 03:42:44,729 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-29 03:42:44,729 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-29 03:42:44,730 INFO L153 SettingsManager]: * Use SBE=true [2023-11-29 03:42:44,730 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-29 03:42:44,731 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-29 03:42:44,731 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-29 03:42:44,732 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-29 03:42:44,732 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-29 03:42:44,732 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-29 03:42:44,733 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-29 03:42:44,733 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-29 03:42:44,734 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-29 03:42:44,734 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-29 03:42:44,734 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-29 03:42:44,735 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-29 03:42:44,735 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-29 03:42:44,736 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-29 03:42:44,736 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-29 03:42:44,736 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-29 03:42:44,737 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-11-29 03:42:44,737 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-29 03:42:44,737 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-29 03:42:44,737 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-29 03:42:44,738 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-29 03:42:44,738 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-29 03:42:44,738 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-29 03:42:44,738 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-29 03:42:44,738 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-29 03:42:44,738 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-11-29 03:42:44,739 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-29 03:42:44,739 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/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_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya 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 -> Automizer 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 -> 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 [2023-11-29 03:42:44,965 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-29 03:42:44,984 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-29 03:42:44,987 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-29 03:42:44,988 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-29 03:42:44,988 INFO L274 PluginConnector]: CDTParser initialized [2023-11-29 03:42:44,990 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/../../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2023-11-29 03:42:47,713 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-29 03:42:47,891 INFO L384 CDTParser]: Found 1 translation units. [2023-11-29 03:42:47,892 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2023-11-29 03:42:47,900 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/data/91bfb3795/4ea81be5a1744df78543531dcdf742da/FLAG8f82c09e4 [2023-11-29 03:42:47,916 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/data/91bfb3795/4ea81be5a1744df78543531dcdf742da [2023-11-29 03:42:47,919 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-29 03:42:47,921 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-29 03:42:47,922 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-29 03:42:47,923 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-29 03:42:47,933 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-29 03:42:47,934 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.11 03:42:47" (1/1) ... [2023-11-29 03:42:47,935 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@782efa50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:47, skipping insertion in model container [2023-11-29 03:42:47,935 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.11 03:42:47" (1/1) ... [2023-11-29 03:42:47,962 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-29 03:42:48,112 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_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c[1076,1089] [2023-11-29 03:42:48,152 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-29 03:42:48,163 INFO L202 MainTranslator]: Completed pre-run [2023-11-29 03:42:48,176 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_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c[1076,1089] [2023-11-29 03:42:48,205 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-29 03:42:48,220 INFO L206 MainTranslator]: Completed translation [2023-11-29 03:42:48,221 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48 WrapperNode [2023-11-29 03:42:48,221 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-29 03:42:48,222 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-29 03:42:48,223 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-29 03:42:48,223 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-29 03:42:48,230 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,241 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,264 INFO L138 Inliner]: procedures = 17, calls = 173, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 114 [2023-11-29 03:42:48,265 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-29 03:42:48,265 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-29 03:42:48,265 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-29 03:42:48,266 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-29 03:42:48,275 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,275 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,281 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,297 INFO L175 MemorySlicer]: Split 139 memory accesses to 6 slices as follows [2, 30, 22, 29, 21, 35]. 25 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 2, 2, 3, 1, 3]. [2023-11-29 03:42:48,297 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,297 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,309 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,312 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,315 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,317 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,321 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-29 03:42:48,322 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-29 03:42:48,322 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-29 03:42:48,322 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-29 03:42:48,323 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (1/1) ... [2023-11-29 03:42:48,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-11-29 03:42:48,341 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:42:48,353 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2023-11-29 03:42:48,356 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2023-11-29 03:42:48,387 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-29 03:42:48,387 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_33_0 [2023-11-29 03:42:48,387 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_33_0 [2023-11-29 03:42:48,387 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-11-29 03:42:48,388 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-11-29 03:42:48,388 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2023-11-29 03:42:48,388 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2023-11-29 03:42:48,388 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2023-11-29 03:42:48,388 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2023-11-29 03:42:48,389 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-29 03:42:48,389 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2023-11-29 03:42:48,389 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2023-11-29 03:42:48,389 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2023-11-29 03:42:48,389 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2023-11-29 03:42:48,389 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2023-11-29 03:42:48,389 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2023-11-29 03:42:48,390 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_37_to_53_0 [2023-11-29 03:42:48,390 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_37_to_53_0 [2023-11-29 03:42:48,390 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-29 03:42:48,390 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-29 03:42:48,390 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2023-11-29 03:42:48,390 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2023-11-29 03:42:48,390 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2023-11-29 03:42:48,391 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2023-11-29 03:42:48,391 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2023-11-29 03:42:48,391 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2023-11-29 03:42:48,391 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-29 03:42:48,391 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-29 03:42:48,391 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-29 03:42:48,522 INFO L241 CfgBuilder]: Building ICFG [2023-11-29 03:42:48,524 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-29 03:42:48,865 INFO L282 CfgBuilder]: Performing block encoding [2023-11-29 03:42:48,891 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-29 03:42:48,892 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-29 03:42:48,892 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.11 03:42:48 BoogieIcfgContainer [2023-11-29 03:42:48,892 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-29 03:42:48,895 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-29 03:42:48,895 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-29 03:42:48,897 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-29 03:42:48,898 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 29.11 03:42:47" (1/3) ... [2023-11-29 03:42:48,898 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@298ac842 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.11 03:42:48, skipping insertion in model container [2023-11-29 03:42:48,898 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 03:42:48" (2/3) ... [2023-11-29 03:42:48,899 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@298ac842 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.11 03:42:48, skipping insertion in model container [2023-11-29 03:42:48,899 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.11 03:42:48" (3/3) ... [2023-11-29 03:42:48,900 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra-u.c [2023-11-29 03:42:48,916 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-29 03:42:48,916 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-29 03:42:48,957 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-29 03:42:48,962 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=PETRI_NET, 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;@744d1c02, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-29 03:42:48,962 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-29 03:42:48,966 INFO L276 IsEmpty]: Start isEmpty. Operand has 44 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 29 states have internal predecessors, (34), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-11-29 03:42:48,972 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2023-11-29 03:42:48,972 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:42:48,973 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:42:48,973 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:42:48,977 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:42:48,977 INFO L85 PathProgramCache]: Analyzing trace with hash 1180092585, now seen corresponding path program 1 times [2023-11-29 03:42:48,984 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:42:48,984 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1754817609] [2023-11-29 03:42:48,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:42:48,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:42:49,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:49,164 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:42:49,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:49,173 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-29 03:42:49,174 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:42:49,174 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1754817609] [2023-11-29 03:42:49,175 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1754817609] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-29 03:42:49,175 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-29 03:42:49,175 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-29 03:42:49,177 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [694018266] [2023-11-29 03:42:49,178 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-29 03:42:49,182 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-29 03:42:49,182 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:42:49,207 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-29 03:42:49,208 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-29 03:42:49,209 INFO L87 Difference]: Start difference. First operand has 44 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 29 states have internal predecessors, (34), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-29 03:42:49,370 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:42:49,370 INFO L93 Difference]: Finished difference Result 90 states and 136 transitions. [2023-11-29 03:42:49,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-29 03:42:49,373 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2023-11-29 03:42:49,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:42:49,382 INFO L225 Difference]: With dead ends: 90 [2023-11-29 03:42:49,382 INFO L226 Difference]: Without dead ends: 46 [2023-11-29 03:42:49,385 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-29 03:42:49,388 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 19 mSDsluCounter, 7 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-29 03:42:49,389 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 40 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-29 03:42:49,402 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-11-29 03:42:49,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 42. [2023-11-29 03:42:49,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 25 states have (on average 1.16) internal successors, (29), 28 states have internal predecessors, (29), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2023-11-29 03:42:49,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 54 transitions. [2023-11-29 03:42:49,423 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 54 transitions. Word has length 15 [2023-11-29 03:42:49,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:42:49,423 INFO L495 AbstractCegarLoop]: Abstraction has 42 states and 54 transitions. [2023-11-29 03:42:49,424 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-29 03:42:49,424 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 54 transitions. [2023-11-29 03:42:49,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-11-29 03:42:49,425 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:42:49,426 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:42:49,426 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-29 03:42:49,426 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:42:49,427 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:42:49,427 INFO L85 PathProgramCache]: Analyzing trace with hash 318761401, now seen corresponding path program 1 times [2023-11-29 03:42:49,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:42:49,427 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1310921825] [2023-11-29 03:42:49,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:42:49,428 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:42:49,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:50,559 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:42:50,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:50,798 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-29 03:42:50,798 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:42:50,798 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1310921825] [2023-11-29 03:42:50,798 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1310921825] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-29 03:42:50,799 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-29 03:42:50,799 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2023-11-29 03:42:50,799 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1576194199] [2023-11-29 03:42:50,799 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-29 03:42:50,800 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-29 03:42:50,800 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:42:50,801 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-29 03:42:50,801 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2023-11-29 03:42:50,802 INFO L87 Difference]: Start difference. First operand 42 states and 54 transitions. Second operand has 13 states, 10 states have (on average 1.2) internal successors, (12), 9 states have internal predecessors, (12), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-29 03:42:51,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:42:51,768 INFO L93 Difference]: Finished difference Result 76 states and 99 transitions. [2023-11-29 03:42:51,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-29 03:42:51,769 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.2) internal successors, (12), 9 states have internal predecessors, (12), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2023-11-29 03:42:51,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:42:51,771 INFO L225 Difference]: With dead ends: 76 [2023-11-29 03:42:51,771 INFO L226 Difference]: Without dead ends: 74 [2023-11-29 03:42:51,772 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2023-11-29 03:42:51,774 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 62 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 389 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 435 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 389 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-29 03:42:51,774 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 113 Invalid, 435 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 389 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-29 03:42:51,775 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2023-11-29 03:42:51,795 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 68. [2023-11-29 03:42:51,795 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 40 states have (on average 1.125) internal successors, (45), 43 states have internal predecessors, (45), 20 states have call successors, (20), 5 states have call predecessors, (20), 7 states have return successors, (24), 19 states have call predecessors, (24), 19 states have call successors, (24) [2023-11-29 03:42:51,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 89 transitions. [2023-11-29 03:42:51,798 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 89 transitions. Word has length 16 [2023-11-29 03:42:51,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:42:51,798 INFO L495 AbstractCegarLoop]: Abstraction has 68 states and 89 transitions. [2023-11-29 03:42:51,799 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.2) internal successors, (12), 9 states have internal predecessors, (12), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-29 03:42:51,799 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 89 transitions. [2023-11-29 03:42:51,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-29 03:42:51,800 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:42:51,800 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:42:51,800 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-29 03:42:51,801 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:42:51,801 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:42:51,801 INFO L85 PathProgramCache]: Analyzing trace with hash -210214075, now seen corresponding path program 1 times [2023-11-29 03:42:51,802 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:42:51,802 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1605806474] [2023-11-29 03:42:51,802 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:42:51,802 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:42:51,830 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:42:51,830 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1073171778] [2023-11-29 03:42:51,830 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:42:51,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:42:51,831 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:42:51,832 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:42:51,840 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-29 03:42:52,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:52,014 INFO L262 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 69 conjunts are in the unsatisfiable core [2023-11-29 03:42:52,023 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:42:52,082 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:42:52,113 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:42:52,119 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:42:52,550 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-11-29 03:42:52,558 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-11-29 03:42:52,562 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-11-29 03:42:52,611 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-29 03:42:52,611 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:42:52,705 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 27 [2023-11-29 03:42:52,864 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:42:52,864 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1605806474] [2023-11-29 03:42:52,864 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:42:52,864 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1073171778] [2023-11-29 03:42:52,865 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1073171778] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:42:52,865 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:42:52,865 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2023-11-29 03:42:52,865 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1516789378] [2023-11-29 03:42:52,865 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:42:52,866 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-29 03:42:52,866 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:42:52,867 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-29 03:42:52,867 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2023-11-29 03:42:52,867 INFO L87 Difference]: Start difference. First operand 68 states and 89 transitions. Second operand has 13 states, 10 states have (on average 1.6) internal successors, (16), 10 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-29 03:42:53,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:42:53,659 INFO L93 Difference]: Finished difference Result 115 states and 151 transitions. [2023-11-29 03:42:53,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-29 03:42:53,661 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.6) internal successors, (16), 10 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2023-11-29 03:42:53,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:42:53,663 INFO L225 Difference]: With dead ends: 115 [2023-11-29 03:42:53,663 INFO L226 Difference]: Without dead ends: 113 [2023-11-29 03:42:53,664 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 9 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 104 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=97, Invalid=455, Unknown=0, NotChecked=0, Total=552 [2023-11-29 03:42:53,666 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 49 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 380 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 235 SdHoareTripleChecker+Invalid, 418 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 380 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-29 03:42:53,666 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 235 Invalid, 418 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 380 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-29 03:42:53,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2023-11-29 03:42:53,694 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 103. [2023-11-29 03:42:53,695 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 61 states have (on average 1.1311475409836065) internal successors, (69), 65 states have internal predecessors, (69), 30 states have call successors, (30), 8 states have call predecessors, (30), 11 states have return successors, (37), 29 states have call predecessors, (37), 28 states have call successors, (37) [2023-11-29 03:42:53,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 136 transitions. [2023-11-29 03:42:53,697 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 136 transitions. Word has length 22 [2023-11-29 03:42:53,697 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:42:53,697 INFO L495 AbstractCegarLoop]: Abstraction has 103 states and 136 transitions. [2023-11-29 03:42:53,697 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.6) internal successors, (16), 10 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-29 03:42:53,698 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 136 transitions. [2023-11-29 03:42:53,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-29 03:42:53,699 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:42:53,699 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:42:53,705 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-29 03:42:53,899 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:42:53,900 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:42:53,900 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:42:53,900 INFO L85 PathProgramCache]: Analyzing trace with hash 661147168, now seen corresponding path program 1 times [2023-11-29 03:42:53,900 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:42:53,900 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1048238549] [2023-11-29 03:42:53,901 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:42:53,901 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:42:53,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:54,686 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:42:54,694 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:55,093 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:42:55,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:55,308 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-29 03:42:55,308 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:42:55,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1048238549] [2023-11-29 03:42:55,308 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1048238549] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:42:55,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1338091562] [2023-11-29 03:42:55,309 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:42:55,309 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:42:55,309 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:42:55,310 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:42:55,319 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-29 03:42:55,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:42:55,500 WARN L260 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 114 conjunts are in the unsatisfiable core [2023-11-29 03:42:55,505 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:42:55,544 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:42:55,656 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:42:55,672 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:42:55,682 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:42:56,560 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-11-29 03:42:56,578 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:42:56,578 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 41 treesize of output 33 [2023-11-29 03:42:56,950 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:42:56,951 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 22 [2023-11-29 03:42:57,102 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-29 03:42:57,102 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:42:58,637 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1338091562] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:42:58,638 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 03:42:58,638 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2023-11-29 03:42:58,638 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2011503400] [2023-11-29 03:42:58,638 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 03:42:58,639 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2023-11-29 03:42:58,639 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:42:58,640 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2023-11-29 03:42:58,641 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=1299, Unknown=0, NotChecked=0, Total=1406 [2023-11-29 03:42:58,641 INFO L87 Difference]: Start difference. First operand 103 states and 136 transitions. Second operand has 31 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 23 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-29 03:43:03,788 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:43:03,788 INFO L93 Difference]: Finished difference Result 151 states and 196 transitions. [2023-11-29 03:43:03,788 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-11-29 03:43:03,789 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 23 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 22 [2023-11-29 03:43:03,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:43:03,791 INFO L225 Difference]: With dead ends: 151 [2023-11-29 03:43:03,791 INFO L226 Difference]: Without dead ends: 149 [2023-11-29 03:43:03,793 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 452 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=252, Invalid=2828, Unknown=0, NotChecked=0, Total=3080 [2023-11-29 03:43:03,795 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 111 mSDsluCounter, 346 mSDsCounter, 0 mSdLazyCounter, 1878 mSolverCounterSat, 80 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 382 SdHoareTripleChecker+Invalid, 1958 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Valid, 1878 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.4s IncrementalHoareTripleChecker+Time [2023-11-29 03:43:03,795 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 382 Invalid, 1958 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 1878 Invalid, 0 Unknown, 0 Unchecked, 3.4s Time] [2023-11-29 03:43:03,796 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2023-11-29 03:43:03,831 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 140. [2023-11-29 03:43:03,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 85 states have (on average 1.1294117647058823) internal successors, (96), 89 states have internal predecessors, (96), 37 states have call successors, (37), 13 states have call predecessors, (37), 17 states have return successors, (48), 37 states have call predecessors, (48), 35 states have call successors, (48) [2023-11-29 03:43:03,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 181 transitions. [2023-11-29 03:43:03,834 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 181 transitions. Word has length 22 [2023-11-29 03:43:03,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:43:03,834 INFO L495 AbstractCegarLoop]: Abstraction has 140 states and 181 transitions. [2023-11-29 03:43:03,835 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 23 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-29 03:43:03,835 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 181 transitions. [2023-11-29 03:43:03,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-11-29 03:43:03,836 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:43:03,837 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:43:03,842 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-11-29 03:43:04,039 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:43:04,040 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:43:04,040 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:43:04,040 INFO L85 PathProgramCache]: Analyzing trace with hash 466428615, now seen corresponding path program 2 times [2023-11-29 03:43:04,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:43:04,041 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1105509027] [2023-11-29 03:43:04,041 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:43:04,041 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:43:04,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:43:04,825 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:43:04,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:43:05,276 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:43:05,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:43:05,691 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:43:05,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:43:05,949 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-29 03:43:05,950 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:43:05,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1105509027] [2023-11-29 03:43:05,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1105509027] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:43:05,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1261261736] [2023-11-29 03:43:05,950 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-29 03:43:05,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:43:05,950 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:43:05,951 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:43:05,954 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-29 03:43:06,206 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-29 03:43:06,206 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-29 03:43:06,211 WARN L260 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 131 conjunts are in the unsatisfiable core [2023-11-29 03:43:06,216 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:43:06,225 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:43:06,289 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:43:06,295 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:43:06,301 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:43:07,100 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-11-29 03:43:07,116 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:43:07,116 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 28 [2023-11-29 03:43:07,426 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2023-11-29 03:43:07,582 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-11-29 03:43:07,582 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:43:10,278 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1261261736] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:43:10,278 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 03:43:10,278 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16] total 34 [2023-11-29 03:43:10,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1608022732] [2023-11-29 03:43:10,278 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 03:43:10,279 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2023-11-29 03:43:10,279 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:43:10,279 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2023-11-29 03:43:10,280 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=1530, Unknown=0, NotChecked=0, Total=1640 [2023-11-29 03:43:10,280 INFO L87 Difference]: Start difference. First operand 140 states and 181 transitions. Second operand has 34 states, 25 states have (on average 1.32) internal successors, (33), 26 states have internal predecessors, (33), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-29 03:43:17,642 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:43:25,773 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:43:38,199 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:43:42,438 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:43:46,485 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:43:50,539 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:43:55,170 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:43:59,200 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:44:03,341 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:44:07,551 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:44:11,602 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:44:15,677 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:44:19,948 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:44:24,235 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:44:28,785 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:44:29,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:44:29,746 INFO L93 Difference]: Finished difference Result 190 states and 247 transitions. [2023-11-29 03:44:29,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2023-11-29 03:44:29,746 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 25 states have (on average 1.32) internal successors, (33), 26 states have internal predecessors, (33), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 28 [2023-11-29 03:44:29,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:44:29,749 INFO L225 Difference]: With dead ends: 190 [2023-11-29 03:44:29,749 INFO L226 Difference]: Without dead ends: 188 [2023-11-29 03:44:29,751 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 810 ImplicationChecksByTransitivity, 18.3s TimeCoverageRelationStatistics Valid=440, Invalid=4669, Unknown=3, NotChecked=0, Total=5112 [2023-11-29 03:44:29,751 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 136 mSDsluCounter, 499 mSDsCounter, 0 mSdLazyCounter, 2505 mSolverCounterSat, 94 mSolverCounterUnsat, 15 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 64.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 546 SdHoareTripleChecker+Invalid, 2614 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 2505 IncrementalHoareTripleChecker+Invalid, 15 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 64.4s IncrementalHoareTripleChecker+Time [2023-11-29 03:44:29,752 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [152 Valid, 546 Invalid, 2614 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 2505 Invalid, 15 Unknown, 0 Unchecked, 64.4s Time] [2023-11-29 03:44:29,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2023-11-29 03:44:29,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 150. [2023-11-29 03:44:29,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 150 states, 91 states have (on average 1.1318681318681318) internal successors, (103), 96 states have internal predecessors, (103), 38 states have call successors, (38), 14 states have call predecessors, (38), 20 states have return successors, (51), 39 states have call predecessors, (51), 36 states have call successors, (51) [2023-11-29 03:44:29,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 192 transitions. [2023-11-29 03:44:29,783 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 192 transitions. Word has length 28 [2023-11-29 03:44:29,783 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:44:29,783 INFO L495 AbstractCegarLoop]: Abstraction has 150 states and 192 transitions. [2023-11-29 03:44:29,783 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 25 states have (on average 1.32) internal successors, (33), 26 states have internal predecessors, (33), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-29 03:44:29,783 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 192 transitions. [2023-11-29 03:44:29,784 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-11-29 03:44:29,784 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:44:29,784 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:44:29,789 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-11-29 03:44:29,985 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:44:29,985 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:44:29,985 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:44:29,986 INFO L85 PathProgramCache]: Analyzing trace with hash 1566657743, now seen corresponding path program 1 times [2023-11-29 03:44:29,986 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:44:29,986 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1022535808] [2023-11-29 03:44:29,986 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:44:29,986 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:44:30,001 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:44:30,001 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [794488750] [2023-11-29 03:44:30,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:44:30,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:44:30,002 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:44:30,003 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:44:30,006 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-29 03:44:30,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:44:30,202 WARN L260 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 133 conjunts are in the unsatisfiable core [2023-11-29 03:44:30,207 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:44:30,215 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:44:30,259 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:44:30,276 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:44:30,283 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:44:30,291 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:44:30,947 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2023-11-29 03:44:30,953 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2023-11-29 03:44:31,058 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-29 03:44:31,058 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:44:35,649 WARN L876 $PredicateComparison]: unable to prove that (forall ((|func_to_recursive_line_37_to_53_0_#t~mem13| Int) (|v_func_to_recursive_line_37_to_53_0_#t~mem26_5| Int) (|v_func_to_recursive_line_37_to_53_0_#t~mem27_5| Int)) (let ((.cse0 (select (select |c_#memory_int#5| c_func_to_recursive_line_37_to_53_0_~q.base) c_func_to_recursive_line_37_to_53_0_~q.offset))) (or (< |v_func_to_recursive_line_37_to_53_0_#t~mem26_5| .cse0) (= (mod (let ((.cse4 (select (select |c_#memory_int#4| c_func_to_recursive_line_37_to_53_0_~n.base) c_func_to_recursive_line_37_to_53_0_~n.offset)) (.cse2 (select (select |c_#memory_int#1| c_func_to_recursive_line_37_to_53_0_~h.base) c_func_to_recursive_line_37_to_53_0_~h.offset)) (.cse1 (select (select |c_#memory_int#2| c_func_to_recursive_line_37_to_53_0_~r.base) c_func_to_recursive_line_37_to_53_0_~r.offset)) (.cse3 (select (select |c_#memory_int#3| c_func_to_recursive_line_37_to_53_0_~p.base) c_func_to_recursive_line_37_to_53_0_~p.offset))) (+ (* .cse1 .cse0 12 .cse2) (* .cse0 16 .cse3 .cse4) (* .cse0 .cse0 4294967295 .cse2) (* .cse0 .cse4 .cse2 4294967284) (* |func_to_recursive_line_37_to_53_0_#t~mem13| .cse2 .cse2) (* .cse1 .cse0 .cse3 4294967280) (* 4294967292 .cse3 |v_func_to_recursive_line_37_to_53_0_#t~mem27_5| |v_func_to_recursive_line_37_to_53_0_#t~mem26_5|))) 4294967296) 0) (< |v_func_to_recursive_line_37_to_53_0_#t~mem27_5| .cse0)))) is different from true [2023-11-29 03:45:08,264 WARN L293 SmtUtils]: Spent 16.17s on a formula simplification that was a NOOP. DAG size: 66 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-11-29 03:45:08,265 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:45:08,265 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1022535808] [2023-11-29 03:45:08,265 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:45:08,266 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [794488750] [2023-11-29 03:45:08,266 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [794488750] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:45:08,266 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:45:08,266 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-11-29 03:45:08,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [940480885] [2023-11-29 03:45:08,266 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:45:08,267 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-29 03:45:08,267 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:45:08,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-29 03:45:08,268 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=257, Unknown=4, NotChecked=32, Total=342 [2023-11-29 03:45:08,268 INFO L87 Difference]: Start difference. First operand 150 states and 192 transitions. Second operand has 14 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 11 states have internal predecessors, (20), 4 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-29 03:45:17,592 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:45:17,592 INFO L93 Difference]: Finished difference Result 168 states and 210 transitions. [2023-11-29 03:45:17,593 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-29 03:45:17,593 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 11 states have internal predecessors, (20), 4 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 28 [2023-11-29 03:45:17,593 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:45:17,595 INFO L225 Difference]: With dead ends: 168 [2023-11-29 03:45:17,595 INFO L226 Difference]: Without dead ends: 166 [2023-11-29 03:45:17,596 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 12 SyntacticMatches, 4 SemanticMatches, 26 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 98 ImplicationChecksByTransitivity, 45.5s TimeCoverageRelationStatistics Valid=129, Invalid=571, Unknown=6, NotChecked=50, Total=756 [2023-11-29 03:45:17,596 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 55 mSDsluCounter, 222 mSDsCounter, 0 mSdLazyCounter, 435 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 476 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 435 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-29 03:45:17,596 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 247 Invalid, 476 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 435 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-29 03:45:17,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2023-11-29 03:45:17,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 164. [2023-11-29 03:45:17,628 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 100 states have (on average 1.13) internal successors, (113), 105 states have internal predecessors, (113), 41 states have call successors, (41), 16 states have call predecessors, (41), 22 states have return successors, (53), 42 states have call predecessors, (53), 38 states have call successors, (53) [2023-11-29 03:45:17,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 207 transitions. [2023-11-29 03:45:17,630 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 207 transitions. Word has length 28 [2023-11-29 03:45:17,630 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:45:17,630 INFO L495 AbstractCegarLoop]: Abstraction has 164 states and 207 transitions. [2023-11-29 03:45:17,630 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 11 states have internal predecessors, (20), 4 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-29 03:45:17,630 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 207 transitions. [2023-11-29 03:45:17,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-11-29 03:45:17,631 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:45:17,631 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:45:17,637 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-29 03:45:17,832 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-29 03:45:17,832 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:45:17,832 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:45:17,833 INFO L85 PathProgramCache]: Analyzing trace with hash 1068029870, now seen corresponding path program 3 times [2023-11-29 03:45:17,833 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:45:17,833 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [31412044] [2023-11-29 03:45:17,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:45:17,833 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:45:17,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:45:18,974 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:45:18,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:45:19,455 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:45:19,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:45:19,808 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:45:19,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:45:20,223 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-29 03:45:20,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:45:20,465 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-29 03:45:20,466 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:45:20,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [31412044] [2023-11-29 03:45:20,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [31412044] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:45:20,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1916675350] [2023-11-29 03:45:20,466 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-29 03:45:20,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:45:20,467 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:45:20,468 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:45:20,470 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-29 03:45:21,130 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-11-29 03:45:21,130 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-29 03:45:21,134 WARN L260 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 139 conjunts are in the unsatisfiable core [2023-11-29 03:45:21,139 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:45:21,148 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:45:21,199 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:45:21,205 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:45:21,471 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:45:21,962 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:45:21,963 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 36 [2023-11-29 03:45:30,289 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2023-11-29 03:45:30,292 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2023-11-29 03:45:30,410 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-29 03:45:30,410 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:45:32,465 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 251 treesize of output 239 [2023-11-29 03:45:33,279 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1916675350] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:45:33,280 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 03:45:33,280 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 16] total 36 [2023-11-29 03:45:33,280 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [184920166] [2023-11-29 03:45:33,280 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 03:45:33,280 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2023-11-29 03:45:33,280 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:45:33,281 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2023-11-29 03:45:33,282 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=1684, Unknown=2, NotChecked=0, Total=1806 [2023-11-29 03:45:33,282 INFO L87 Difference]: Start difference. First operand 164 states and 207 transitions. Second operand has 36 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 27 states have internal predecessors, (36), 9 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2023-11-29 03:45:41,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:45:41,696 INFO L93 Difference]: Finished difference Result 227 states and 289 transitions. [2023-11-29 03:45:41,696 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2023-11-29 03:45:41,697 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 27 states have internal predecessors, (36), 9 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 34 [2023-11-29 03:45:41,697 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:45:41,699 INFO L225 Difference]: With dead ends: 227 [2023-11-29 03:45:41,699 INFO L226 Difference]: Without dead ends: 225 [2023-11-29 03:45:41,701 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 869 ImplicationChecksByTransitivity, 13.9s TimeCoverageRelationStatistics Valid=482, Invalid=5066, Unknown=2, NotChecked=0, Total=5550 [2023-11-29 03:45:41,702 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 158 mSDsluCounter, 365 mSDsCounter, 0 mSdLazyCounter, 2272 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 172 SdHoareTripleChecker+Valid, 400 SdHoareTripleChecker+Invalid, 2398 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 2272 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.4s IncrementalHoareTripleChecker+Time [2023-11-29 03:45:41,703 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [172 Valid, 400 Invalid, 2398 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [126 Valid, 2272 Invalid, 0 Unknown, 0 Unchecked, 5.4s Time] [2023-11-29 03:45:41,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states. [2023-11-29 03:45:41,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 159. [2023-11-29 03:45:41,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 159 states, 98 states have (on average 1.1326530612244898) internal successors, (111), 103 states have internal predecessors, (111), 40 states have call successors, (40), 16 states have call predecessors, (40), 20 states have return successors, (47), 39 states have call predecessors, (47), 37 states have call successors, (47) [2023-11-29 03:45:41,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 198 transitions. [2023-11-29 03:45:41,750 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 198 transitions. Word has length 34 [2023-11-29 03:45:41,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:45:41,750 INFO L495 AbstractCegarLoop]: Abstraction has 159 states and 198 transitions. [2023-11-29 03:45:41,750 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 27 states have internal predecessors, (36), 9 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2023-11-29 03:45:41,750 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 198 transitions. [2023-11-29 03:45:41,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-11-29 03:45:41,752 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:45:41,752 INFO L195 NwaCegarLoop]: trace histogram [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, 1, 1] [2023-11-29 03:45:41,757 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-11-29 03:45:41,952 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-29 03:45:41,953 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:45:41,953 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:45:41,953 INFO L85 PathProgramCache]: Analyzing trace with hash -858116137, now seen corresponding path program 1 times [2023-11-29 03:45:41,953 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:45:41,953 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [876333239] [2023-11-29 03:45:41,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:45:41,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:45:41,968 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:45:41,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1453842964] [2023-11-29 03:45:41,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:45:41,968 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:45:41,969 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:45:41,969 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:45:41,970 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-29 03:45:42,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:45:42,111 INFO L262 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 95 conjunts are in the unsatisfiable core [2023-11-29 03:45:42,115 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:45:42,121 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:45:42,132 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:45:46,146 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_14| Int) (|v_ULTIMATE.start_main_~#n~0#1.base_BEFORE_CALL_11| Int)) (= (select (select |c_#memory_int#4| |v_ULTIMATE.start_main_~#n~0#1.base_BEFORE_CALL_11|) 0) (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_14|) 0))) is different from true [2023-11-29 03:45:50,207 WARN L876 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_4 Int) (v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_4 Int)) (= (select (select |c_#memory_int#2| v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_4) 0) (select (select |c_#memory_int#4| v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_4) 0))) is different from true [2023-11-29 03:45:54,242 WARN L876 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_5 Int) (v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_5 Int)) (= (select (select |c_#memory_int#4| v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_5) 0) (select (select |c_#memory_int#2| v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_5) 0))) is different from true [2023-11-29 03:45:58,273 WARN L876 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_6 Int) (v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_6 Int)) (= (select (select |c_#memory_int#4| v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_6) 0) (select (select |c_#memory_int#2| v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_6) 0))) is different from true [2023-11-29 03:45:58,379 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 19 [2023-11-29 03:45:58,392 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 22 [2023-11-29 03:45:58,411 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-11-29 03:45:58,420 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 26 [2023-11-29 03:45:58,434 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 22 [2023-11-29 03:46:02,592 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 17 not checked. [2023-11-29 03:46:02,592 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:46:07,065 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 156 treesize of output 128 [2023-11-29 03:46:07,068 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 128 treesize of output 104 [2023-11-29 03:46:11,272 WARN L876 $PredicateComparison]: unable to prove that (forall ((v_arrayElimCell_27 Int) (v_arrayElimCell_26 Int)) (= (mod (let ((.cse1 (select (select |c_#memory_int#3| c_func_to_recursive_line_37_to_53_0_~p.base) c_func_to_recursive_line_37_to_53_0_~p.offset)) (.cse0 (select (select |c_#memory_int#2| c_func_to_recursive_line_37_to_53_0_~r.base) c_func_to_recursive_line_37_to_53_0_~r.offset)) (.cse2 (select (select |c_#memory_int#4| c_func_to_recursive_line_37_to_53_0_~n.base) c_func_to_recursive_line_37_to_53_0_~n.offset))) (+ (* .cse0 v_arrayElimCell_26 v_arrayElimCell_26) (* .cse0 .cse1 4 v_arrayElimCell_27) (* .cse2 v_arrayElimCell_27 v_arrayElimCell_27) (* .cse0 .cse0 4 v_arrayElimCell_26) (* .cse2 .cse2 4 v_arrayElimCell_26) (* .cse0 4294967295 v_arrayElimCell_27 v_arrayElimCell_27) (* 4294967292 .cse1 .cse2 v_arrayElimCell_27) (* 4294967295 .cse2 v_arrayElimCell_26 v_arrayElimCell_26) (* .cse0 4294967288 .cse2 v_arrayElimCell_26))) 4294967296) 0)) is different from true [2023-11-29 03:46:11,747 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:46:11,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [876333239] [2023-11-29 03:46:11,747 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:46:11,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1453842964] [2023-11-29 03:46:11,747 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1453842964] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:46:11,747 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:46:11,747 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-11-29 03:46:11,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1991318996] [2023-11-29 03:46:11,747 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:46:11,748 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-29 03:46:11,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:46:11,748 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-29 03:46:11,748 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=155, Unknown=7, NotChecked=140, Total=342 [2023-11-29 03:46:11,748 INFO L87 Difference]: Start difference. First operand 159 states and 198 transitions. Second operand has 15 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 3 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-11-29 03:46:20,063 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:46:20,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:46:20,433 INFO L93 Difference]: Finished difference Result 179 states and 216 transitions. [2023-11-29 03:46:20,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-29 03:46:20,434 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 3 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 34 [2023-11-29 03:46:20,434 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:46:20,436 INFO L225 Difference]: With dead ends: 179 [2023-11-29 03:46:20,436 INFO L226 Difference]: Without dead ends: 177 [2023-11-29 03:46:20,436 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 18 SyntacticMatches, 4 SemanticMatches, 22 ConstructedPredicates, 5 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 32.8s TimeCoverageRelationStatistics Valid=70, Invalid=284, Unknown=8, NotChecked=190, Total=552 [2023-11-29 03:46:20,437 INFO L413 NwaCegarLoop]: 45 mSDtfsCounter, 23 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 249 mSolverCounterSat, 8 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 268 SdHoareTripleChecker+Invalid, 803 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 249 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 545 IncrementalHoareTripleChecker+Unchecked, 4.5s IncrementalHoareTripleChecker+Time [2023-11-29 03:46:20,437 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 268 Invalid, 803 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 249 Invalid, 1 Unknown, 545 Unchecked, 4.5s Time] [2023-11-29 03:46:20,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2023-11-29 03:46:20,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 175. [2023-11-29 03:46:20,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 110 states have (on average 1.1363636363636365) internal successors, (125), 115 states have internal predecessors, (125), 40 states have call successors, (40), 20 states have call predecessors, (40), 24 states have return successors, (47), 39 states have call predecessors, (47), 37 states have call successors, (47) [2023-11-29 03:46:20,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 212 transitions. [2023-11-29 03:46:20,492 INFO L78 Accepts]: Start accepts. Automaton has 175 states and 212 transitions. Word has length 34 [2023-11-29 03:46:20,492 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:46:20,492 INFO L495 AbstractCegarLoop]: Abstraction has 175 states and 212 transitions. [2023-11-29 03:46:20,492 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 3 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-11-29 03:46:20,492 INFO L276 IsEmpty]: Start isEmpty. Operand 175 states and 212 transitions. [2023-11-29 03:46:20,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-11-29 03:46:20,493 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:46:20,493 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:46:20,498 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-11-29 03:46:20,693 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:46:20,694 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:46:20,694 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:46:20,694 INFO L85 PathProgramCache]: Analyzing trace with hash 990596790, now seen corresponding path program 1 times [2023-11-29 03:46:20,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:46:20,694 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1004604490] [2023-11-29 03:46:20,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:46:20,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:46:20,709 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:46:20,709 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1609116831] [2023-11-29 03:46:20,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:46:20,709 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:46:20,709 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:46:20,710 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:46:20,711 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-29 03:46:20,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:46:20,906 INFO L262 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 141 conjunts are in the unsatisfiable core [2023-11-29 03:46:20,911 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:46:20,922 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:46:20,953 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:46:20,960 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:46:20,965 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:46:20,972 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:46:21,152 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-11-29 03:46:21,927 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:46:21,927 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 29 [2023-11-29 03:46:21,943 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:46:21,944 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 34 treesize of output 26 [2023-11-29 03:46:22,108 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-29 03:46:22,108 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:46:42,009 WARN L293 SmtUtils]: Spent 8.10s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-11-29 03:46:47,469 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:46:47,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1004604490] [2023-11-29 03:46:47,469 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:46:47,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1609116831] [2023-11-29 03:46:47,469 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1609116831] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:46:47,469 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:46:47,469 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2023-11-29 03:46:47,469 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [115930769] [2023-11-29 03:46:47,469 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:46:47,470 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-11-29 03:46:47,470 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:46:47,470 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-11-29 03:46:47,471 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=329, Unknown=1, NotChecked=0, Total=380 [2023-11-29 03:46:47,471 INFO L87 Difference]: Start difference. First operand 175 states and 212 transitions. Second operand has 16 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 12 states have internal predecessors, (24), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-29 03:46:57,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:46:57,541 INFO L93 Difference]: Finished difference Result 229 states and 272 transitions. [2023-11-29 03:46:57,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-29 03:46:57,542 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 12 states have internal predecessors, (24), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 34 [2023-11-29 03:46:57,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:46:57,543 INFO L225 Difference]: With dead ends: 229 [2023-11-29 03:46:57,543 INFO L226 Difference]: Without dead ends: 227 [2023-11-29 03:46:57,544 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 18 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 23.6s TimeCoverageRelationStatistics Valid=119, Invalid=635, Unknown=2, NotChecked=0, Total=756 [2023-11-29 03:46:57,545 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 52 mSDsluCounter, 239 mSDsCounter, 0 mSdLazyCounter, 885 mSolverCounterSat, 33 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 922 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 885 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2023-11-29 03:46:57,545 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 277 Invalid, 922 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 885 Invalid, 4 Unknown, 0 Unchecked, 2.6s Time] [2023-11-29 03:46:57,546 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 227 states. [2023-11-29 03:46:57,604 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 227 to 221. [2023-11-29 03:46:57,604 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 221 states, 139 states have (on average 1.1223021582733812) internal successors, (156), 144 states have internal predecessors, (156), 50 states have call successors, (50), 26 states have call predecessors, (50), 31 states have return successors, (59), 50 states have call predecessors, (59), 46 states have call successors, (59) [2023-11-29 03:46:57,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 221 states to 221 states and 265 transitions. [2023-11-29 03:46:57,606 INFO L78 Accepts]: Start accepts. Automaton has 221 states and 265 transitions. Word has length 34 [2023-11-29 03:46:57,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:46:57,606 INFO L495 AbstractCegarLoop]: Abstraction has 221 states and 265 transitions. [2023-11-29 03:46:57,607 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 12 states have internal predecessors, (24), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-29 03:46:57,607 INFO L276 IsEmpty]: Start isEmpty. Operand 221 states and 265 transitions. [2023-11-29 03:46:57,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-29 03:46:57,608 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:46:57,608 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 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, 1] [2023-11-29 03:46:57,615 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-11-29 03:46:57,808 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:46:57,809 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:46:57,809 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:46:57,809 INFO L85 PathProgramCache]: Analyzing trace with hash -1818921507, now seen corresponding path program 1 times [2023-11-29 03:46:57,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:46:57,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [76445713] [2023-11-29 03:46:57,810 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:46:57,810 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:46:57,824 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:46:57,824 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1793495752] [2023-11-29 03:46:57,824 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:46:57,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:46:57,825 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:46:57,825 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:46:57,826 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-29 03:46:57,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:46:58,003 INFO L262 TraceCheckSpWp]: Trace formula consists of 368 conjuncts, 119 conjunts are in the unsatisfiable core [2023-11-29 03:46:58,009 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:46:58,019 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:46:58,040 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:46:58,044 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:46:58,052 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:46:58,691 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2023-11-29 03:46:58,695 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2023-11-29 03:46:58,709 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2023-11-29 03:46:58,782 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 9 proven. 8 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-29 03:46:58,782 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:47:14,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:47:14,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [76445713] [2023-11-29 03:47:14,833 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:47:14,833 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1793495752] [2023-11-29 03:47:14,833 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1793495752] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:47:14,833 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:47:14,833 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2023-11-29 03:47:14,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [221134184] [2023-11-29 03:47:14,833 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:47:14,833 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-29 03:47:14,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:47:14,834 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-29 03:47:14,834 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=198, Unknown=2, NotChecked=0, Total=240 [2023-11-29 03:47:14,834 INFO L87 Difference]: Start difference. First operand 221 states and 265 transitions. Second operand has 12 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-29 03:47:16,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:47:16,451 INFO L93 Difference]: Finished difference Result 259 states and 301 transitions. [2023-11-29 03:47:16,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-29 03:47:16,452 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 40 [2023-11-29 03:47:16,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:47:16,454 INFO L225 Difference]: With dead ends: 259 [2023-11-29 03:47:16,454 INFO L226 Difference]: Without dead ends: 257 [2023-11-29 03:47:16,455 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 22 SyntacticMatches, 9 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 16.1s TimeCoverageRelationStatistics Valid=79, Invalid=339, Unknown=2, NotChecked=0, Total=420 [2023-11-29 03:47:16,455 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 37 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 324 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 228 SdHoareTripleChecker+Invalid, 343 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 324 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-29 03:47:16,456 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 228 Invalid, 343 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 324 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-29 03:47:16,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 257 states. [2023-11-29 03:47:16,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 257 to 255. [2023-11-29 03:47:16,537 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 255 states, 163 states have (on average 1.116564417177914) internal successors, (182), 168 states have internal predecessors, (182), 53 states have call successors, (53), 33 states have call predecessors, (53), 38 states have return successors, (61), 53 states have call predecessors, (61), 48 states have call successors, (61) [2023-11-29 03:47:16,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 255 states to 255 states and 296 transitions. [2023-11-29 03:47:16,538 INFO L78 Accepts]: Start accepts. Automaton has 255 states and 296 transitions. Word has length 40 [2023-11-29 03:47:16,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:47:16,539 INFO L495 AbstractCegarLoop]: Abstraction has 255 states and 296 transitions. [2023-11-29 03:47:16,539 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.2) internal successors, (22), 9 states have internal predecessors, (22), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-29 03:47:16,539 INFO L276 IsEmpty]: Start isEmpty. Operand 255 states and 296 transitions. [2023-11-29 03:47:16,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-29 03:47:16,540 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:47:16,540 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:47:16,545 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-11-29 03:47:16,740 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-29 03:47:16,740 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:47:16,741 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:47:16,741 INFO L85 PathProgramCache]: Analyzing trace with hash -766811939, now seen corresponding path program 2 times [2023-11-29 03:47:16,741 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:47:16,741 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1413027620] [2023-11-29 03:47:16,741 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:47:16,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:47:16,755 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:47:16,755 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1817386035] [2023-11-29 03:47:16,755 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-29 03:47:16,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:47:16,755 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:47:16,756 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:47:16,758 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-29 03:47:17,076 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-29 03:47:17,076 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-29 03:47:17,080 INFO L262 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 150 conjunts are in the unsatisfiable core [2023-11-29 03:47:17,085 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:47:17,099 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2023-11-29 03:47:17,107 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:47:17,145 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:47:17,157 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:47:17,167 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:47:17,178 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:47:17,219 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2023-11-29 03:47:17,698 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 3 [2023-11-29 03:47:18,858 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:47:18,859 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 5 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 29 [2023-11-29 03:47:18,882 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:47:18,882 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 34 treesize of output 26 [2023-11-29 03:47:18,905 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2023-11-29 03:47:18,906 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 7 [2023-11-29 03:47:18,915 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 22 [2023-11-29 03:47:19,079 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-29 03:47:19,079 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:47:23,952 WARN L876 $PredicateComparison]: unable to prove that (forall ((|func_to_recursive_line_37_to_53_0_#t~mem15| Int) (|func_to_recursive_line_37_to_53_0_#t~mem13| Int) (|func_to_recursive_line_37_to_53_0_#t~mem24| Int) (|func_to_recursive_line_37_to_53_0_#t~mem23| Int) (|v_func_to_recursive_line_37_to_53_0_#t~mem27_10| Int) (|v_func_to_recursive_line_37_to_53_0_#t~mem26_10| Int)) (let ((.cse0 (select (select |c_#memory_int#5| c_func_to_recursive_line_37_to_53_0_~q.base) c_func_to_recursive_line_37_to_53_0_~q.offset))) (or (< |v_func_to_recursive_line_37_to_53_0_#t~mem27_10| .cse0) (= (mod (let ((.cse4 (select (select |c_#memory_int#4| c_func_to_recursive_line_37_to_53_0_~n.base) c_func_to_recursive_line_37_to_53_0_~n.offset)) (.cse3 (select (select |c_#memory_int#1| c_func_to_recursive_line_37_to_53_0_~h.base) c_func_to_recursive_line_37_to_53_0_~h.offset)) (.cse2 (select (select |c_#memory_int#2| c_func_to_recursive_line_37_to_53_0_~r.base) c_func_to_recursive_line_37_to_53_0_~r.offset)) (.cse1 (select (select |c_#memory_int#3| c_func_to_recursive_line_37_to_53_0_~p.base) c_func_to_recursive_line_37_to_53_0_~p.offset))) (+ (* 4294967292 .cse1 |v_func_to_recursive_line_37_to_53_0_#t~mem27_10| |v_func_to_recursive_line_37_to_53_0_#t~mem26_10|) (* .cse2 .cse0 12 .cse3) (* .cse0 16 .cse1 .cse4) (* .cse0 .cse4 .cse3 4294967284) (* |func_to_recursive_line_37_to_53_0_#t~mem24| |func_to_recursive_line_37_to_53_0_#t~mem23| 4294967295 .cse3) (* |func_to_recursive_line_37_to_53_0_#t~mem15| |func_to_recursive_line_37_to_53_0_#t~mem13| .cse3) (* .cse2 .cse0 .cse1 4294967280))) 4294967296) 0) (< |v_func_to_recursive_line_37_to_53_0_#t~mem26_10| .cse0)))) is different from true [2023-11-29 03:47:24,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:47:24,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1413027620] [2023-11-29 03:47:24,032 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:47:24,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1817386035] [2023-11-29 03:47:24,032 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1817386035] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:47:24,032 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:47:24,032 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2023-11-29 03:47:24,032 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [394134798] [2023-11-29 03:47:24,032 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:47:24,033 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-11-29 03:47:24,033 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:47:24,033 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-11-29 03:47:24,033 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=298, Unknown=1, NotChecked=34, Total=380 [2023-11-29 03:47:24,033 INFO L87 Difference]: Start difference. First operand 255 states and 296 transitions. Second operand has 16 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 12 states have internal predecessors, (23), 6 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2023-11-29 03:47:28,076 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:47:32,186 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:47:36,283 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:47:36,283 INFO L93 Difference]: Finished difference Result 315 states and 362 transitions. [2023-11-29 03:47:36,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-29 03:47:36,284 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 12 states have internal predecessors, (23), 6 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 40 [2023-11-29 03:47:36,284 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:47:36,285 INFO L225 Difference]: With dead ends: 315 [2023-11-29 03:47:36,285 INFO L226 Difference]: Without dead ends: 313 [2023-11-29 03:47:36,286 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 24 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 94 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=93, Invalid=510, Unknown=1, NotChecked=46, Total=650 [2023-11-29 03:47:36,286 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 58 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 771 mSolverCounterSat, 42 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 265 SdHoareTripleChecker+Invalid, 817 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 771 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.4s IncrementalHoareTripleChecker+Time [2023-11-29 03:47:36,286 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 265 Invalid, 817 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 771 Invalid, 4 Unknown, 0 Unchecked, 11.4s Time] [2023-11-29 03:47:36,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 313 states. [2023-11-29 03:47:36,354 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 313 to 257. [2023-11-29 03:47:36,355 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 257 states, 164 states have (on average 1.1158536585365855) internal successors, (183), 169 states have internal predecessors, (183), 53 states have call successors, (53), 33 states have call predecessors, (53), 39 states have return successors, (63), 54 states have call predecessors, (63), 48 states have call successors, (63) [2023-11-29 03:47:36,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 257 states to 257 states and 299 transitions. [2023-11-29 03:47:36,356 INFO L78 Accepts]: Start accepts. Automaton has 257 states and 299 transitions. Word has length 40 [2023-11-29 03:47:36,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:47:36,357 INFO L495 AbstractCegarLoop]: Abstraction has 257 states and 299 transitions. [2023-11-29 03:47:36,357 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 12 states have internal predecessors, (23), 6 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2023-11-29 03:47:36,357 INFO L276 IsEmpty]: Start isEmpty. Operand 257 states and 299 transitions. [2023-11-29 03:47:36,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-11-29 03:47:36,357 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:47:36,358 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:47:36,363 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-11-29 03:47:36,558 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:47:36,558 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:47:36,559 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:47:36,559 INFO L85 PathProgramCache]: Analyzing trace with hash 1584657220, now seen corresponding path program 3 times [2023-11-29 03:47:36,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:47:36,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1374636132] [2023-11-29 03:47:36,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:47:36,559 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:47:36,573 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:47:36,573 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [119244211] [2023-11-29 03:47:36,573 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-29 03:47:36,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:47:36,573 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:47:36,574 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:47:36,575 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-29 03:47:37,230 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-29 03:47:37,231 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-29 03:47:37,234 INFO L262 TraceCheckSpWp]: Trace formula consists of 268 conjuncts, 96 conjunts are in the unsatisfiable core [2023-11-29 03:47:37,238 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:47:37,247 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:47:37,271 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:47:37,279 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:47:37,283 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:47:37,732 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2023-11-29 03:47:37,747 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2023-11-29 03:47:37,761 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-11-29 03:47:37,840 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2023-11-29 03:47:37,841 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:47:39,285 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 95 treesize of output 87 [2023-11-29 03:47:51,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:47:51,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1374636132] [2023-11-29 03:47:51,976 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:47:51,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [119244211] [2023-11-29 03:47:51,976 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [119244211] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:47:51,976 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:47:51,976 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-11-29 03:47:51,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1405796100] [2023-11-29 03:47:51,976 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:47:51,977 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-29 03:47:51,977 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:47:51,977 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-29 03:47:51,977 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=148, Unknown=1, NotChecked=0, Total=182 [2023-11-29 03:47:51,977 INFO L87 Difference]: Start difference. First operand 257 states and 299 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-29 03:48:00,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:48:00,987 INFO L93 Difference]: Finished difference Result 261 states and 301 transitions. [2023-11-29 03:48:00,987 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-29 03:48:00,987 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 46 [2023-11-29 03:48:00,988 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:48:00,989 INFO L225 Difference]: With dead ends: 261 [2023-11-29 03:48:00,989 INFO L226 Difference]: Without dead ends: 259 [2023-11-29 03:48:00,990 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 34 SyntacticMatches, 5 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 22.2s TimeCoverageRelationStatistics Valid=61, Invalid=242, Unknown=3, NotChecked=0, Total=306 [2023-11-29 03:48:00,990 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 48 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-29 03:48:00,990 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 190 Invalid, 214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 189 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-29 03:48:00,991 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2023-11-29 03:48:01,045 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 205. [2023-11-29 03:48:01,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 205 states, 131 states have (on average 1.1221374045801527) internal successors, (147), 136 states have internal predecessors, (147), 43 states have call successors, (43), 26 states have call predecessors, (43), 30 states have return successors, (49), 42 states have call predecessors, (49), 39 states have call successors, (49) [2023-11-29 03:48:01,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 205 states to 205 states and 239 transitions. [2023-11-29 03:48:01,047 INFO L78 Accepts]: Start accepts. Automaton has 205 states and 239 transitions. Word has length 46 [2023-11-29 03:48:01,047 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:48:01,047 INFO L495 AbstractCegarLoop]: Abstraction has 205 states and 239 transitions. [2023-11-29 03:48:01,047 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-29 03:48:01,047 INFO L276 IsEmpty]: Start isEmpty. Operand 205 states and 239 transitions. [2023-11-29 03:48:01,048 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-11-29 03:48:01,048 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:48:01,048 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 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, 1, 1, 1, 1] [2023-11-29 03:48:01,053 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-29 03:48:01,248 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:48:01,249 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:48:01,249 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:48:01,249 INFO L85 PathProgramCache]: Analyzing trace with hash 1462790241, now seen corresponding path program 1 times [2023-11-29 03:48:01,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:48:01,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [194497043] [2023-11-29 03:48:01,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:48:01,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:48:01,264 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:48:01,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [953223562] [2023-11-29 03:48:01,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:48:01,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:48:01,265 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:48:01,266 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:48:01,266 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-29 03:48:01,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:48:01,438 INFO L262 TraceCheckSpWp]: Trace formula consists of 389 conjuncts, 70 conjunts are in the unsatisfiable core [2023-11-29 03:48:01,441 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:48:01,447 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:48:01,461 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:48:05,476 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#n~0#1.base_BEFORE_CALL_21| Int) (|v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_24| Int)) (= (select (select |c_#memory_int#4| |v_ULTIMATE.start_main_~#n~0#1.base_BEFORE_CALL_21|) 0) (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_24|) 0))) is different from true [2023-11-29 03:48:09,542 WARN L876 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_17 Int) (v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_17 Int)) (= (select (select |c_#memory_int#2| v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_17) 0) (select (select |c_#memory_int#4| v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_17) 0))) is different from true [2023-11-29 03:48:13,617 WARN L876 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_18 Int) (v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_18 Int)) (= (select (select |c_#memory_int#4| v_func_to_recursive_line_37_to_53_0_~n.base_BEFORE_CALL_18) 0) (select (select |c_#memory_int#2| v_func_to_recursive_line_37_to_53_0_~r.base_BEFORE_CALL_18) 0))) is different from true [2023-11-29 03:48:46,777 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:48:46,777 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 93 treesize of output 81 [2023-11-29 03:48:46,806 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:48:46,806 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 103 treesize of output 103 [2023-11-29 03:48:57,727 WARN L293 SmtUtils]: Spent 10.91s on a formula simplification that was a NOOP. DAG size: 12 (called from [L 346] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2023-11-29 03:48:57,727 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:48:57,727 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 73 treesize of output 61 [2023-11-29 03:49:04,737 WARN L293 SmtUtils]: Spent 7.00s on a formula simplification that was a NOOP. DAG size: 19 (called from [L 346] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2023-11-29 03:49:04,737 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 03:49:04,737 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 97 treesize of output 85 [2023-11-29 03:49:26,211 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 9 proven. 8 refuted. 5 times theorem prover too weak. 6 trivial. 22 not checked. [2023-11-29 03:49:26,211 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:49:54,162 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 64 [2023-11-29 03:49:54,170 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-29 03:49:54,170 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:49:54,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [194497043] [2023-11-29 03:49:54,170 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:49:54,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [953223562] [2023-11-29 03:49:54,170 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [953223562] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-29 03:49:54,170 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 03:49:54,170 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 9] total 27 [2023-11-29 03:49:54,171 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1099987274] [2023-11-29 03:49:54,171 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 03:49:54,171 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-29 03:49:54,171 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:49:54,172 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-29 03:49:54,172 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=467, Unknown=14, NotChecked=138, Total=702 [2023-11-29 03:49:54,172 INFO L87 Difference]: Start difference. First operand 205 states and 239 transitions. Second operand has 27 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 23 states have internal predecessors, (51), 10 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (12), 6 states have call predecessors, (12), 8 states have call successors, (12) [2023-11-29 03:49:58,631 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:49:59,786 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.07s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 03:50:04,283 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.05s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-11-29 03:50:08,287 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:50:29,153 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:50:33,184 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:50:35,448 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.26s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:50:47,871 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:50:51,906 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:50:56,566 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:51:05,054 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:51:09,500 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:51:13,545 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:51:24,752 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.74s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:51:28,758 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:51:32,787 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:51:56,033 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.15s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:52:04,569 WARN L293 SmtUtils]: Spent 7.08s on a formula simplification that was a NOOP. DAG size: 92 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-11-29 03:52:06,866 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.06s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:52:12,380 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:52:16,307 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.93s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:52:21,183 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:52:25,190 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:52:30,319 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:52:35,952 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:52:39,960 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:52:52,458 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:52:56,607 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:53:21,874 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:53:25,904 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:53:29,987 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:53:34,968 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:53:38,999 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 03:53:43,026 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:53:47,058 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:53:50,098 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.00s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 03:53:54,105 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:53:58,147 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:02,178 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:06,602 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:54:08,315 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.68s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:12,321 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:20,734 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:24,740 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:28,767 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:32,790 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:54:36,794 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:54:40,799 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:54:44,815 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:09,070 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:55:13,073 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:55:15,740 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.67s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:19,746 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:55:23,750 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-29 03:55:27,766 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:31,877 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:35,902 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:37,204 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.28s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-11-29 03:55:41,208 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:45,421 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:49,442 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:55:53,505 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:55:57,698 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0, 1] [2023-11-29 03:55:57,828 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:55:57,828 INFO L93 Difference]: Finished difference Result 223 states and 257 transitions. [2023-11-29 03:55:57,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2023-11-29 03:55:57,829 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 23 states have internal predecessors, (51), 10 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (12), 6 states have call predecessors, (12), 8 states have call successors, (12) Word has length 46 [2023-11-29 03:55:57,829 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:55:57,830 INFO L225 Difference]: With dead ends: 223 [2023-11-29 03:55:57,830 INFO L226 Difference]: Without dead ends: 221 [2023-11-29 03:55:57,831 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 62 SyntacticMatches, 4 SemanticMatches, 43 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 208.1s TimeCoverageRelationStatistics Valid=245, Invalid=1450, Unknown=39, NotChecked=246, Total=1980 [2023-11-29 03:55:57,831 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 87 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 483 mSolverCounterSat, 49 mSolverCounterUnsat, 51 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 240.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 273 SdHoareTripleChecker+Invalid, 1139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 483 IncrementalHoareTripleChecker+Invalid, 51 IncrementalHoareTripleChecker+Unknown, 556 IncrementalHoareTripleChecker+Unchecked, 241.3s IncrementalHoareTripleChecker+Time [2023-11-29 03:55:57,832 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 273 Invalid, 1139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 483 Invalid, 51 Unknown, 556 Unchecked, 241.3s Time] [2023-11-29 03:55:57,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 221 states. [2023-11-29 03:55:57,885 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 221 to 163. [2023-11-29 03:55:57,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 105 states have (on average 1.1238095238095238) internal successors, (118), 110 states have internal predecessors, (118), 33 states have call successors, (33), 21 states have call predecessors, (33), 24 states have return successors, (37), 32 states have call predecessors, (37), 30 states have call successors, (37) [2023-11-29 03:55:57,887 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 188 transitions. [2023-11-29 03:55:57,887 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 188 transitions. Word has length 46 [2023-11-29 03:55:57,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:55:57,887 INFO L495 AbstractCegarLoop]: Abstraction has 163 states and 188 transitions. [2023-11-29 03:55:57,887 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 23 states have internal predecessors, (51), 10 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (12), 6 states have call predecessors, (12), 8 states have call successors, (12) [2023-11-29 03:55:57,887 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 188 transitions. [2023-11-29 03:55:57,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-11-29 03:55:57,888 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:55:57,888 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:55:57,893 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-11-29 03:55:58,088 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-11-29 03:55:58,089 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:55:58,089 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:55:58,089 INFO L85 PathProgramCache]: Analyzing trace with hash 1317720319, now seen corresponding path program 1 times [2023-11-29 03:55:58,089 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:55:58,089 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [468823618] [2023-11-29 03:55:58,090 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:55:58,090 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:55:58,106 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:55:58,106 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1456185499] [2023-11-29 03:55:58,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:55:58,106 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:55:58,106 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:55:58,107 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:55:58,108 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-29 03:55:58,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:55:58,308 INFO L262 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 71 conjunts are in the unsatisfiable core [2023-11-29 03:55:58,322 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:55:58,328 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:55:58,342 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:55:58,347 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:55:58,356 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:55:58,483 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:55:58,704 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-11-29 03:55:58,709 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-11-29 03:55:58,793 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 26 proven. 1 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-29 03:55:58,793 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:56:06,071 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:56:06,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [468823618] [2023-11-29 03:56:06,071 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:56:06,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1456185499] [2023-11-29 03:56:06,072 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1456185499] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:56:06,072 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:56:06,072 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2023-11-29 03:56:06,072 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1343062370] [2023-11-29 03:56:06,072 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:56:06,072 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-29 03:56:06,073 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:56:06,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-29 03:56:06,073 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=175, Unknown=1, NotChecked=0, Total=210 [2023-11-29 03:56:06,073 INFO L87 Difference]: Start difference. First operand 163 states and 188 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 3 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-29 03:56:08,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:56:08,576 INFO L93 Difference]: Finished difference Result 171 states and 194 transitions. [2023-11-29 03:56:08,576 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-29 03:56:08,576 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 3 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 56 [2023-11-29 03:56:08,577 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:56:08,578 INFO L225 Difference]: With dead ends: 171 [2023-11-29 03:56:08,578 INFO L226 Difference]: Without dead ends: 169 [2023-11-29 03:56:08,578 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 50 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=103, Invalid=448, Unknown=1, NotChecked=0, Total=552 [2023-11-29 03:56:08,579 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 71 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 314 mSolverCounterSat, 53 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 372 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 314 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2023-11-29 03:56:08,579 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [80 Valid, 111 Invalid, 372 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 314 Invalid, 5 Unknown, 0 Unchecked, 1.5s Time] [2023-11-29 03:56:08,580 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2023-11-29 03:56:08,652 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 167. [2023-11-29 03:56:08,653 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 108 states have (on average 1.1203703703703705) internal successors, (121), 113 states have internal predecessors, (121), 33 states have call successors, (33), 22 states have call predecessors, (33), 25 states have return successors, (37), 32 states have call predecessors, (37), 30 states have call successors, (37) [2023-11-29 03:56:08,654 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 191 transitions. [2023-11-29 03:56:08,654 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 191 transitions. Word has length 56 [2023-11-29 03:56:08,654 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:56:08,654 INFO L495 AbstractCegarLoop]: Abstraction has 167 states and 191 transitions. [2023-11-29 03:56:08,654 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 3 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-29 03:56:08,654 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 191 transitions. [2023-11-29 03:56:08,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2023-11-29 03:56:08,655 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:56:08,655 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 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, 1, 1, 1, 1, 1, 1] [2023-11-29 03:56:08,660 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2023-11-29 03:56:08,855 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-11-29 03:56:08,856 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:56:08,856 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:56:08,856 INFO L85 PathProgramCache]: Analyzing trace with hash 17279192, now seen corresponding path program 1 times [2023-11-29 03:56:08,856 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:56:08,856 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1311069378] [2023-11-29 03:56:08,856 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:56:08,856 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:56:08,874 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:56:08,874 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [74338112] [2023-11-29 03:56:08,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:56:08,874 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:56:08,874 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:56:08,875 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:56:08,876 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-29 03:56:09,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:56:09,037 INFO L262 TraceCheckSpWp]: Trace formula consists of 480 conjuncts, 32 conjunts are in the unsatisfiable core [2023-11-29 03:56:09,040 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:56:09,048 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:56:09,380 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-11-29 03:56:09,380 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-29 03:56:09,380 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:56:09,380 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1311069378] [2023-11-29 03:56:09,380 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:56:09,380 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [74338112] [2023-11-29 03:56:09,380 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [74338112] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-29 03:56:09,380 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-29 03:56:09,380 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2023-11-29 03:56:09,381 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1219766] [2023-11-29 03:56:09,381 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-29 03:56:09,381 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-29 03:56:09,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:56:09,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-29 03:56:09,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2023-11-29 03:56:09,381 INFO L87 Difference]: Start difference. First operand 167 states and 191 transitions. Second operand has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 3 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-29 03:56:11,426 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 03:56:11,426 INFO L93 Difference]: Finished difference Result 315 states and 358 transitions. [2023-11-29 03:56:11,426 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-29 03:56:11,427 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 3 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 57 [2023-11-29 03:56:11,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 03:56:11,428 INFO L225 Difference]: With dead ends: 315 [2023-11-29 03:56:11,428 INFO L226 Difference]: Without dead ends: 227 [2023-11-29 03:56:11,429 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 35 SyntacticMatches, 11 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=93, Invalid=327, Unknown=0, NotChecked=0, Total=420 [2023-11-29 03:56:11,430 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 69 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 327 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 374 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 327 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2023-11-29 03:56:11,430 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 115 Invalid, 374 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 327 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2023-11-29 03:56:11,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 227 states. [2023-11-29 03:56:11,529 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 227 to 211. [2023-11-29 03:56:11,529 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 211 states, 137 states have (on average 1.094890510948905) internal successors, (150), 142 states have internal predecessors, (150), 40 states have call successors, (40), 29 states have call predecessors, (40), 33 states have return successors, (45), 39 states have call predecessors, (45), 37 states have call successors, (45) [2023-11-29 03:56:11,530 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 235 transitions. [2023-11-29 03:56:11,530 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 235 transitions. Word has length 57 [2023-11-29 03:56:11,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 03:56:11,530 INFO L495 AbstractCegarLoop]: Abstraction has 211 states and 235 transitions. [2023-11-29 03:56:11,531 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 3 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-29 03:56:11,531 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 235 transitions. [2023-11-29 03:56:11,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2023-11-29 03:56:11,531 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 03:56:11,531 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 03:56:11,538 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-11-29 03:56:11,732 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-11-29 03:56:11,732 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 03:56:11,732 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 03:56:11,732 INFO L85 PathProgramCache]: Analyzing trace with hash 990060440, now seen corresponding path program 1 times [2023-11-29 03:56:11,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 03:56:11,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1593710905] [2023-11-29 03:56:11,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:56:11,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 03:56:11,748 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 03:56:11,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1856096791] [2023-11-29 03:56:11,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 03:56:11,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 03:56:11,748 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 03:56:11,749 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 03:56:11,751 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_baf0f8cd-eae9-44d7-8d9f-cb0255276de2/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-11-29 03:56:11,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 03:56:11,933 INFO L262 TraceCheckSpWp]: Trace formula consists of 447 conjuncts, 84 conjunts are in the unsatisfiable core [2023-11-29 03:56:11,937 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 03:56:11,943 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:56:11,964 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-29 03:56:11,969 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-11-29 03:56:15,986 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#n~0#1.base_BEFORE_CALL_25| Int) (|v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_28| Int)) (= (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_28|) 0) (select (select |c_#memory_int#4| |v_ULTIMATE.start_main_~#n~0#1.base_BEFORE_CALL_25|) 0))) is different from true [2023-11-29 03:56:16,022 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-29 03:56:16,320 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-11-29 03:56:16,883 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 38 [2023-11-29 03:56:16,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 30 [2023-11-29 03:56:16,892 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 14 [2023-11-29 03:56:16,958 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 50 proven. 3 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-29 03:56:16,958 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 03:56:18,328 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 32 [2023-11-29 03:56:18,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 03:56:18,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1593710905] [2023-11-29 03:56:18,437 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 03:56:18,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1856096791] [2023-11-29 03:56:18,437 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1856096791] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 03:56:18,437 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 03:56:18,437 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2023-11-29 03:56:18,437 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [866156665] [2023-11-29 03:56:18,437 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 03:56:18,438 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-29 03:56:18,438 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 03:56:18,438 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-29 03:56:18,438 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=364, Unknown=1, NotChecked=38, Total=462 [2023-11-29 03:56:18,438 INFO L87 Difference]: Start difference. First operand 211 states and 235 transitions. Second operand has 18 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 5 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2023-11-29 03:56:26,742 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:56:34,495 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.11s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:56:39,086 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:56:43,099 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:56:47,103 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:56:51,276 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:56:55,278 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:56:59,488 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:57:03,492 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:57:07,495 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:57:11,502 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:57:13,117 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.62s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:57:21,337 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:57:34,247 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 03:57:35,714 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.46s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0]