./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.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_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/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_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/config/AutomizerReach.xml -i ../../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/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_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/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 020f2d3a270ed8dfae4a7c8fa8db16a8ad645d088f685c7c500cf3124112cf45 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-11-29 05:31:42,412 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-29 05:31:42,479 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-11-29 05:31:42,483 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-29 05:31:42,484 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-29 05:31:42,506 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-29 05:31:42,507 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-29 05:31:42,507 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-29 05:31:42,508 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-11-29 05:31:42,509 INFO L153 SettingsManager]: * Use memory slicer=true [2023-11-29 05:31:42,509 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-29 05:31:42,510 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-29 05:31:42,510 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-29 05:31:42,511 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-29 05:31:42,511 INFO L153 SettingsManager]: * Use SBE=true [2023-11-29 05:31:42,512 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-29 05:31:42,512 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-29 05:31:42,513 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-29 05:31:42,513 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-29 05:31:42,514 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-29 05:31:42,514 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-29 05:31:42,518 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-29 05:31:42,518 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-29 05:31:42,518 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-29 05:31:42,519 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-29 05:31:42,519 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-29 05:31:42,520 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-29 05:31:42,520 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-29 05:31:42,520 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-29 05:31:42,521 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-29 05:31:42,521 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-29 05:31:42,522 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-11-29 05:31:42,522 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-29 05:31:42,522 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-29 05:31:42,522 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-29 05:31:42,523 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-29 05:31:42,523 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-29 05:31:42,523 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-29 05:31:42,523 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-29 05:31:42,523 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-29 05:31:42,524 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-11-29 05:31:42,524 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-29 05:31:42,524 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_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/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_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/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 -> 020f2d3a270ed8dfae4a7c8fa8db16a8ad645d088f685c7c500cf3124112cf45 [2023-11-29 05:31:42,785 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-29 05:31:42,807 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-29 05:31:42,810 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-29 05:31:42,811 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-29 05:31:42,812 INFO L274 PluginConnector]: CDTParser initialized [2023-11-29 05:31:42,813 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/../../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c [2023-11-29 05:31:45,601 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-29 05:31:45,777 INFO L384 CDTParser]: Found 1 translation units. [2023-11-29 05:31:45,777 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c [2023-11-29 05:31:45,786 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/data/a95294361/258b3e1753944e109d88d94fc85c536c/FLAGa42f0d8cd [2023-11-29 05:31:45,801 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/data/a95294361/258b3e1753944e109d88d94fc85c536c [2023-11-29 05:31:45,803 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-29 05:31:45,805 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-29 05:31:45,806 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-29 05:31:45,806 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-29 05:31:45,812 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-29 05:31:45,812 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.11 05:31:45" (1/1) ... [2023-11-29 05:31:45,814 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6911962e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:45, skipping insertion in model container [2023-11-29 05:31:45,814 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.11 05:31:45" (1/1) ... [2023-11-29 05:31:45,847 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-29 05:31:45,993 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_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c[1037,1050] [2023-11-29 05:31:46,027 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-29 05:31:46,038 INFO L202 MainTranslator]: Completed pre-run [2023-11-29 05:31:46,052 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_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c[1037,1050] [2023-11-29 05:31:46,075 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-29 05:31:46,088 INFO L206 MainTranslator]: Completed translation [2023-11-29 05:31:46,088 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46 WrapperNode [2023-11-29 05:31:46,088 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-29 05:31:46,089 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-29 05:31:46,089 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-29 05:31:46,089 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-29 05:31:46,097 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,109 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,133 INFO L138 Inliner]: procedures = 17, calls = 141, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 136 [2023-11-29 05:31:46,134 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-29 05:31:46,135 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-29 05:31:46,135 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-29 05:31:46,135 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-29 05:31:46,146 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,146 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,151 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,176 INFO L175 MemorySlicer]: Split 86 memory accesses to 13 slices as follows [2, 7, 10, 7, 7, 5, 8, 5, 8, 3, 3, 9, 12]. 14 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The 22 writes are split as follows [0, 2, 2, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1]. [2023-11-29 05:31:46,176 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,177 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,190 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,193 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,196 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,199 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,205 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-29 05:31:46,206 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-29 05:31:46,206 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-29 05:31:46,206 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-29 05:31:46,207 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (1/1) ... [2023-11-29 05:31:46,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-11-29 05:31:46,225 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:31:46,236 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2023-11-29 05:31:46,238 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2023-11-29 05:31:46,265 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-29 05:31:46,265 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-29 05:31:46,265 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-29 05:31:46,265 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-11-29 05:31:46,265 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-11-29 05:31:46,266 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2023-11-29 05:31:46,266 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2023-11-29 05:31:46,266 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2023-11-29 05:31:46,266 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2023-11-29 05:31:46,266 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2023-11-29 05:31:46,266 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#8 [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#9 [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#10 [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#11 [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#12 [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2023-11-29 05:31:46,267 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2023-11-29 05:31:46,268 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2023-11-29 05:31:46,268 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2023-11-29 05:31:46,268 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2023-11-29 05:31:46,268 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2023-11-29 05:31:46,268 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2023-11-29 05:31:46,268 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2023-11-29 05:31:46,268 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#8 [2023-11-29 05:31:46,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#9 [2023-11-29 05:31:46,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#10 [2023-11-29 05:31:46,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#11 [2023-11-29 05:31:46,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#12 [2023-11-29 05:31:46,269 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_45_to_53_0 [2023-11-29 05:31:46,269 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_45_to_53_0 [2023-11-29 05:31:46,269 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_39_to_65_0 [2023-11-29 05:31:46,269 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_39_to_65_0 [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-29 05:31:46,270 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2023-11-29 05:31:46,270 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#8 [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#9 [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#10 [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#11 [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#12 [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-29 05:31:46,271 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-29 05:31:46,271 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-29 05:31:46,408 INFO L241 CfgBuilder]: Building ICFG [2023-11-29 05:31:46,410 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-29 05:31:46,715 INFO L282 CfgBuilder]: Performing block encoding [2023-11-29 05:31:46,747 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-29 05:31:46,747 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-29 05:31:46,748 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.11 05:31:46 BoogieIcfgContainer [2023-11-29 05:31:46,748 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-29 05:31:46,750 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-29 05:31:46,750 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-29 05:31:46,753 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-29 05:31:46,753 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 29.11 05:31:45" (1/3) ... [2023-11-29 05:31:46,754 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@773cacae and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.11 05:31:46, skipping insertion in model container [2023-11-29 05:31:46,754 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.11 05:31:46" (2/3) ... [2023-11-29 05:31:46,754 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@773cacae and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.11 05:31:46, skipping insertion in model container [2023-11-29 05:31:46,754 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.11 05:31:46" (3/3) ... [2023-11-29 05:31:46,756 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_egcd2-ll.c [2023-11-29 05:31:46,771 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-29 05:31:46,772 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-29 05:31:46,817 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-29 05:31:46,823 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;@44d453b3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-29 05:31:46,823 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-29 05:31:46,827 INFO L276 IsEmpty]: Start isEmpty. Operand has 48 states, 28 states have (on average 1.25) internal successors, (35), 31 states have internal predecessors, (35), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2023-11-29 05:31:46,834 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-29 05:31:46,834 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:31:46,835 INFO L195 NwaCegarLoop]: trace histogram [4, 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] [2023-11-29 05:31:46,835 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:31:46,840 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:31:46,840 INFO L85 PathProgramCache]: Analyzing trace with hash -1748206812, now seen corresponding path program 1 times [2023-11-29 05:31:46,847 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:31:46,848 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1245683818] [2023-11-29 05:31:46,848 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:31:46,849 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:31:47,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:31:47,083 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:31:47,083 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1245683818] [2023-11-29 05:31:47,084 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-11-29 05:31:47,084 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [496664835] [2023-11-29 05:31:47,084 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:31:47,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:31:47,085 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:31:47,086 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:31:47,092 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-29 05:31:47,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:31:47,375 INFO L262 TraceCheckSpWp]: Trace formula consists of 480 conjuncts, 1 conjunts are in the unsatisfiable core [2023-11-29 05:31:47,382 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:31:47,409 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-29 05:31:47,409 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-29 05:31:47,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [496664835] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-29 05:31:47,410 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-29 05:31:47,410 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-29 05:31:47,412 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1136394363] [2023-11-29 05:31:47,413 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-29 05:31:47,416 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-29 05:31:47,417 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:31:47,438 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-29 05:31:47,439 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-29 05:31:47,440 INFO L87 Difference]: Start difference. First operand has 48 states, 28 states have (on average 1.25) internal successors, (35), 31 states have internal predecessors, (35), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 2 states, 2 states have (on average 9.0) internal successors, (18), 2 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-11-29 05:31:47,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:31:47,523 INFO L93 Difference]: Finished difference Result 94 states and 137 transitions. [2023-11-29 05:31:47,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-29 05:31:47,526 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 9.0) internal successors, (18), 2 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 36 [2023-11-29 05:31:47,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:31:47,533 INFO L225 Difference]: With dead ends: 94 [2023-11-29 05:31:47,533 INFO L226 Difference]: Without dead ends: 46 [2023-11-29 05:31:47,537 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-29 05:31:47,541 INFO L413 NwaCegarLoop]: 57 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-29 05:31:47,542 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 57 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-29 05:31:47,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-11-29 05:31:47,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2023-11-29 05:31:47,573 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 27 states have (on average 1.1111111111111112) internal successors, (30), 30 states have internal predecessors, (30), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-11-29 05:31:47,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 57 transitions. [2023-11-29 05:31:47,577 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 57 transitions. Word has length 36 [2023-11-29 05:31:47,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:31:47,577 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 57 transitions. [2023-11-29 05:31:47,578 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 9.0) internal successors, (18), 2 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-11-29 05:31:47,578 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 57 transitions. [2023-11-29 05:31:47,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-29 05:31:47,580 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:31:47,580 INFO L195 NwaCegarLoop]: trace histogram [4, 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] [2023-11-29 05:31:47,588 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-29 05:31:47,780 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-11-29 05:31:47,781 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:31:47,781 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:31:47,782 INFO L85 PathProgramCache]: Analyzing trace with hash -754527188, now seen corresponding path program 1 times [2023-11-29 05:31:47,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:31:47,782 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [676886250] [2023-11-29 05:31:47,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:31:47,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:31:47,845 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:31:47,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1773520114] [2023-11-29 05:31:47,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:31:47,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:31:47,846 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:31:47,846 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:31:47,852 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-29 05:31:48,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:31:48,088 INFO L262 TraceCheckSpWp]: Trace formula consists of 480 conjuncts, 89 conjunts are in the unsatisfiable core [2023-11-29 05:31:48,095 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:31:48,252 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 23 treesize of output 15 [2023-11-29 05:31:48,260 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 05:31:48,268 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 05:31:48,486 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 05:31:48,495 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 05:31:48,686 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 05:31:48,690 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 05:31:48,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 15 treesize of output 7 [2023-11-29 05:31:48,749 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 13 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-29 05:31:48,749 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:31:49,054 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-29 05:31:49,055 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:31:49,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [676886250] [2023-11-29 05:31:49,055 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:31:49,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1773520114] [2023-11-29 05:31:49,056 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1773520114] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-29 05:31:49,056 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:31:49,056 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [17] total 23 [2023-11-29 05:31:49,056 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1538202526] [2023-11-29 05:31:49,056 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-29 05:31:49,057 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-29 05:31:49,057 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:31:49,058 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-29 05:31:49,059 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=447, Unknown=0, NotChecked=0, Total=506 [2023-11-29 05:31:49,059 INFO L87 Difference]: Start difference. First operand 46 states and 57 transitions. Second operand has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-29 05:31:55,001 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.38s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:07,432 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.70s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:12,953 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 [1] [2023-11-29 05:32:16,982 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 [1] [2023-11-29 05:32:20,481 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.49s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:23,044 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.50s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:27,462 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 [1] [2023-11-29 05:32:31,480 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 [1] [2023-11-29 05:32:35,531 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 [1] [2023-11-29 05:32:39,260 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.73s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:40,904 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.64s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:44,906 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 [1] [2023-11-29 05:32:48,908 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 [1] [2023-11-29 05:32:51,867 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.85s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:54,672 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.78s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:32:58,693 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 [1] [2023-11-29 05:32:59,992 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.07s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:33:03,996 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 [1] [2023-11-29 05:33:07,269 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.84s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:33:11,277 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 [1] [2023-11-29 05:33:13,250 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.97s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:33:17,257 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 [1] [2023-11-29 05:33:21,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 [1] [2023-11-29 05:33:25,325 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 [1] [2023-11-29 05:33:29,466 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 [1] [2023-11-29 05:33:33,477 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 [1] [2023-11-29 05:33:37,479 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 [1] [2023-11-29 05:33:41,493 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 [1] [2023-11-29 05:33:44,885 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.37s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:33:49,044 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 [1] [2023-11-29 05:33:53,126 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 [1] [2023-11-29 05:33:57,798 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 [1] [2023-11-29 05:34:01,801 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 [1] [2023-11-29 05:34:04,171 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.37s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2023-11-29 05:34:08,174 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 [1] [2023-11-29 05:34:08,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:34:08,226 INFO L93 Difference]: Finished difference Result 66 states and 81 transitions. [2023-11-29 05:34:08,227 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-29 05:34:08,227 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 36 [2023-11-29 05:34:08,228 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:34:08,230 INFO L225 Difference]: With dead ends: 66 [2023-11-29 05:34:08,230 INFO L226 Difference]: Without dead ends: 64 [2023-11-29 05:34:08,231 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 46 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 152 ImplicationChecksByTransitivity, 14.8s TimeCoverageRelationStatistics Valid=73, Invalid=569, Unknown=8, NotChecked=0, Total=650 [2023-11-29 05:34:08,232 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 19 mSDsluCounter, 255 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 11 mSolverCounterUnsat, 33 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 124.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 302 SdHoareTripleChecker+Invalid, 146 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 33 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 124.8s IncrementalHoareTripleChecker+Time [2023-11-29 05:34:08,232 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 302 Invalid, 146 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 102 Invalid, 33 Unknown, 0 Unchecked, 124.8s Time] [2023-11-29 05:34:08,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-11-29 05:34:08,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2023-11-29 05:34:08,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 38 states have (on average 1.105263157894737) internal successors, (42), 41 states have internal predecessors, (42), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) [2023-11-29 05:34:08,250 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 78 transitions. [2023-11-29 05:34:08,251 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 78 transitions. Word has length 36 [2023-11-29 05:34:08,251 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:34:08,251 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 78 transitions. [2023-11-29 05:34:08,251 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-29 05:34:08,251 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 78 transitions. [2023-11-29 05:34:08,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-29 05:34:08,253 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:34:08,253 INFO L195 NwaCegarLoop]: trace histogram [4, 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] [2023-11-29 05:34:08,258 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-11-29 05:34:08,453 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:34:08,454 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:34:08,455 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:34:08,455 INFO L85 PathProgramCache]: Analyzing trace with hash 1375000559, now seen corresponding path program 1 times [2023-11-29 05:34:08,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:34:08,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1097287843] [2023-11-29 05:34:08,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:34:08,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:34:08,506 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:34:08,506 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1329799556] [2023-11-29 05:34:08,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:34:08,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:34:08,507 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:34:08,508 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:34:08,511 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-29 05:34:08,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:34:08,729 INFO L262 TraceCheckSpWp]: Trace formula consists of 375 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-29 05:34:08,733 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:34:08,808 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 23 treesize of output 15 [2023-11-29 05:34:08,814 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 05:34:09,027 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 13 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-29 05:34:09,027 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:34:09,381 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-29 05:34:09,382 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:34:09,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1097287843] [2023-11-29 05:34:09,382 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:34:09,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1329799556] [2023-11-29 05:34:09,382 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1329799556] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-29 05:34:09,383 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 05:34:09,383 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 22 [2023-11-29 05:34:09,383 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1646397009] [2023-11-29 05:34:09,383 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 05:34:09,384 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-11-29 05:34:09,384 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:34:09,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-11-29 05:34:09,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=393, Unknown=0, NotChecked=0, Total=462 [2023-11-29 05:34:09,386 INFO L87 Difference]: Start difference. First operand 63 states and 78 transitions. Second operand has 22 states, 20 states have (on average 1.7) internal successors, (34), 18 states have internal predecessors, (34), 7 states have call successors, (11), 5 states have call predecessors, (11), 6 states have return successors, (10), 7 states have call predecessors, (10), 6 states have call successors, (10) [2023-11-29 05:34:13,505 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 05:34:18,195 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 05:34:22,280 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 05:34:26,447 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 05:34:30,497 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 05:34:30,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:34:30,531 INFO L93 Difference]: Finished difference Result 123 states and 147 transitions. [2023-11-29 05:34:30,532 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-29 05:34:30,532 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.7) internal successors, (34), 18 states have internal predecessors, (34), 7 states have call successors, (11), 5 states have call predecessors, (11), 6 states have return successors, (10), 7 states have call predecessors, (10), 6 states have call successors, (10) Word has length 36 [2023-11-29 05:34:30,533 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:34:30,536 INFO L225 Difference]: With dead ends: 123 [2023-11-29 05:34:30,536 INFO L226 Difference]: Without dead ends: 111 [2023-11-29 05:34:30,537 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 48 SyntacticMatches, 3 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 210 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=177, Invalid=945, Unknown=0, NotChecked=0, Total=1122 [2023-11-29 05:34:30,538 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 118 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 466 mSolverCounterSat, 80 mSolverCounterUnsat, 12 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 20.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 126 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 558 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Valid, 466 IncrementalHoareTripleChecker+Invalid, 12 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.9s IncrementalHoareTripleChecker+Time [2023-11-29 05:34:30,539 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [126 Valid, 87 Invalid, 558 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 466 Invalid, 12 Unknown, 0 Unchecked, 20.9s Time] [2023-11-29 05:34:30,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-11-29 05:34:30,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 108. [2023-11-29 05:34:30,562 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 67 states have (on average 1.1044776119402986) internal successors, (74), 71 states have internal predecessors, (74), 28 states have call successors, (28), 12 states have call predecessors, (28), 12 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2023-11-29 05:34:30,564 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 132 transitions. [2023-11-29 05:34:30,564 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 132 transitions. Word has length 36 [2023-11-29 05:34:30,565 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:34:30,565 INFO L495 AbstractCegarLoop]: Abstraction has 108 states and 132 transitions. [2023-11-29 05:34:30,565 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.7) internal successors, (34), 18 states have internal predecessors, (34), 7 states have call successors, (11), 5 states have call predecessors, (11), 6 states have return successors, (10), 7 states have call predecessors, (10), 6 states have call successors, (10) [2023-11-29 05:34:30,565 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 132 transitions. [2023-11-29 05:34:30,566 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2023-11-29 05:34:30,567 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:34:30,567 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:34:30,573 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-29 05:34:30,767 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:34:30,768 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:34:30,768 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:34:30,768 INFO L85 PathProgramCache]: Analyzing trace with hash 1363352137, now seen corresponding path program 1 times [2023-11-29 05:34:30,768 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:34:30,768 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1580191785] [2023-11-29 05:34:30,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:34:30,769 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:34:30,813 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:34:30,813 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [33727549] [2023-11-29 05:34:30,813 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:34:30,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:34:30,814 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:34:30,815 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:34:30,823 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-29 05:34:31,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:34:31,041 INFO L262 TraceCheckSpWp]: Trace formula consists of 499 conjuncts, 151 conjunts are in the unsatisfiable core [2023-11-29 05:34:31,048 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:34:31,075 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 05:34:31,081 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 05:34:31,163 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 05:34:31,171 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 05:34:31,186 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 05:34:31,202 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 05:34:31,743 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 05:35:00,133 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 05:35:00,136 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 05:35:00,145 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 7 treesize of output 3 [2023-11-29 05:35:00,194 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 16 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-11-29 05:35:00,194 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:35:00,639 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-29 05:35:00,639 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:35:00,639 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1580191785] [2023-11-29 05:35:00,639 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:35:00,639 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [33727549] [2023-11-29 05:35:00,639 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [33727549] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-29 05:35:00,640 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:35:00,640 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [16] total 24 [2023-11-29 05:35:00,640 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1602273459] [2023-11-29 05:35:00,640 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-29 05:35:00,640 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-29 05:35:00,640 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:35:00,641 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-29 05:35:00,641 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=477, Unknown=6, NotChecked=0, Total=552 [2023-11-29 05:35:00,642 INFO L87 Difference]: Start difference. First operand 108 states and 132 transitions. Second operand has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2023-11-29 05:35:02,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:35:02,544 INFO L93 Difference]: Finished difference Result 115 states and 138 transitions. [2023-11-29 05:35:02,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-29 05:35:02,545 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 42 [2023-11-29 05:35:02,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:35:02,547 INFO L225 Difference]: With dead ends: 115 [2023-11-29 05:35:02,547 INFO L226 Difference]: Without dead ends: 113 [2023-11-29 05:35:02,548 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 56 SyntacticMatches, 4 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 171 ImplicationChecksByTransitivity, 28.9s TimeCoverageRelationStatistics Valid=87, Invalid=663, Unknown=6, NotChecked=0, Total=756 [2023-11-29 05:35:02,549 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 23 mSDsluCounter, 267 mSDsCounter, 0 mSdLazyCounter, 213 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 213 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2023-11-29 05:35:02,549 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 313 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 213 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2023-11-29 05:35:02,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2023-11-29 05:35:02,568 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 112. [2023-11-29 05:35:02,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 70 states have (on average 1.1) internal successors, (77), 74 states have internal predecessors, (77), 28 states have call successors, (28), 13 states have call predecessors, (28), 13 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2023-11-29 05:35:02,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 135 transitions. [2023-11-29 05:35:02,570 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 135 transitions. Word has length 42 [2023-11-29 05:35:02,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:35:02,570 INFO L495 AbstractCegarLoop]: Abstraction has 112 states and 135 transitions. [2023-11-29 05:35:02,570 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2023-11-29 05:35:02,570 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 135 transitions. [2023-11-29 05:35:02,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-11-29 05:35:02,571 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:35:02,571 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 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] [2023-11-29 05:35:02,577 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-11-29 05:35:02,772 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:35:02,772 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:35:02,772 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:35:02,772 INFO L85 PathProgramCache]: Analyzing trace with hash 676224932, now seen corresponding path program 1 times [2023-11-29 05:35:02,772 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:35:02,773 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1649707641] [2023-11-29 05:35:02,773 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:35:02,773 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:35:02,819 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:35:02,819 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1346747144] [2023-11-29 05:35:02,819 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:35:02,819 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:35:02,819 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:35:02,820 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:35:02,821 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-29 05:35:03,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:35:03,019 INFO L262 TraceCheckSpWp]: Trace formula consists of 518 conjuncts, 141 conjunts are in the unsatisfiable core [2023-11-29 05:35:03,024 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:35:03,033 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 05:35:03,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 15 treesize of output 1 [2023-11-29 05:35:03,145 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 05:35:03,152 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 05:35:03,161 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 05:35:04,188 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 7 treesize of output 3 [2023-11-29 05:35:04,195 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 05:35:04,198 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 05:35:04,261 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-29 05:35:04,261 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:35:04,670 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-29 05:35:04,670 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:35:04,670 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1649707641] [2023-11-29 05:35:04,670 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:35:04,670 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1346747144] [2023-11-29 05:35:04,670 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1346747144] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-29 05:35:04,670 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:35:04,671 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [18] total 26 [2023-11-29 05:35:04,671 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1629727839] [2023-11-29 05:35:04,671 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-29 05:35:04,671 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-29 05:35:04,671 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:35:04,672 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-29 05:35:04,672 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=581, Unknown=0, NotChecked=0, Total=650 [2023-11-29 05:35:04,672 INFO L87 Difference]: Start difference. First operand 112 states and 135 transitions. Second operand has 10 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 7 states have internal predecessors, (21), 5 states have call successors, (9), 4 states have call predecessors, (9), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2023-11-29 05:35:06,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:35:06,588 INFO L93 Difference]: Finished difference Result 119 states and 141 transitions. [2023-11-29 05:35:06,588 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-29 05:35:06,589 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 7 states have internal predecessors, (21), 5 states have call successors, (9), 4 states have call predecessors, (9), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 48 [2023-11-29 05:35:06,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:35:06,591 INFO L225 Difference]: With dead ends: 119 [2023-11-29 05:35:06,591 INFO L226 Difference]: Without dead ends: 117 [2023-11-29 05:35:06,592 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 63 SyntacticMatches, 7 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 234 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=87, Invalid=783, Unknown=0, NotChecked=0, Total=870 [2023-11-29 05:35:06,593 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 22 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 295 SdHoareTripleChecker+Invalid, 244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2023-11-29 05:35:06,593 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 295 Invalid, 244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2023-11-29 05:35:06,594 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2023-11-29 05:35:06,622 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 116. [2023-11-29 05:35:06,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 73 states have (on average 1.095890410958904) internal successors, (80), 77 states have internal predecessors, (80), 28 states have call successors, (28), 14 states have call predecessors, (28), 14 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2023-11-29 05:35:06,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 138 transitions. [2023-11-29 05:35:06,624 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 138 transitions. Word has length 48 [2023-11-29 05:35:06,625 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:35:06,625 INFO L495 AbstractCegarLoop]: Abstraction has 116 states and 138 transitions. [2023-11-29 05:35:06,625 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 7 states have internal predecessors, (21), 5 states have call successors, (9), 4 states have call predecessors, (9), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2023-11-29 05:35:06,625 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 138 transitions. [2023-11-29 05:35:06,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2023-11-29 05:35:06,626 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:35:06,626 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:35:06,633 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-11-29 05:35:06,827 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:35:06,827 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:35:06,827 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:35:06,828 INFO L85 PathProgramCache]: Analyzing trace with hash 711966141, now seen corresponding path program 1 times [2023-11-29 05:35:06,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:35:06,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1923315321] [2023-11-29 05:35:06,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:35:06,828 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:35:06,865 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:35:06,865 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2003695009] [2023-11-29 05:35:06,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:35:06,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:35:06,865 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:35:06,866 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:35:06,871 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-29 05:35:07,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:35:07,096 INFO L262 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 208 conjunts are in the unsatisfiable core [2023-11-29 05:35:07,104 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:35:07,118 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 05:35:07,126 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 05:35:07,191 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 05:35:07,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 21 treesize of output 17 [2023-11-29 05:35:07,206 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 05:35:07,217 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 05:35:07,224 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 05:35:08,995 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 7 treesize of output 3 [2023-11-29 05:35:09,001 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 7 treesize of output 3 [2023-11-29 05:35:09,011 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 05:35:09,018 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 05:35:09,023 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 15 [2023-11-29 05:35:09,109 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 22 proven. 6 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-29 05:35:09,109 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:35:10,537 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-11-29 05:35:10,538 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:35:10,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1923315321] [2023-11-29 05:35:10,538 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:35:10,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2003695009] [2023-11-29 05:35:10,538 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2003695009] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-29 05:35:10,538 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 05:35:10,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 27 [2023-11-29 05:35:10,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065610407] [2023-11-29 05:35:10,539 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 05:35:10,539 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-29 05:35:10,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:35:10,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-29 05:35:10,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=617, Unknown=0, NotChecked=0, Total=702 [2023-11-29 05:35:10,541 INFO L87 Difference]: Start difference. First operand 116 states and 138 transitions. Second operand has 27 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 12 states have call successors, (20), 8 states have call predecessors, (20), 4 states have return successors, (14), 7 states have call predecessors, (14), 8 states have call successors, (14) [2023-11-29 05:35:20,137 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 [1] [2023-11-29 05:35:24,798 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 [1] [2023-11-29 05:35:29,749 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 [1] [2023-11-29 05:35:30,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:35:30,128 INFO L93 Difference]: Finished difference Result 125 states and 145 transitions. [2023-11-29 05:35:30,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-11-29 05:35:30,129 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 12 states have call successors, (20), 8 states have call predecessors, (20), 4 states have return successors, (14), 7 states have call predecessors, (14), 8 states have call successors, (14) Word has length 54 [2023-11-29 05:35:30,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:35:30,131 INFO L225 Difference]: With dead ends: 125 [2023-11-29 05:35:30,131 INFO L226 Difference]: Without dead ends: 123 [2023-11-29 05:35:30,132 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 73 SyntacticMatches, 9 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 284 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=161, Invalid=1029, Unknown=0, NotChecked=0, Total=1190 [2023-11-29 05:35:30,133 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 39 mSDsluCounter, 402 mSDsCounter, 0 mSdLazyCounter, 595 mSolverCounterSat, 24 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 17.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 436 SdHoareTripleChecker+Invalid, 622 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 595 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 18.6s IncrementalHoareTripleChecker+Time [2023-11-29 05:35:30,133 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 436 Invalid, 622 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 595 Invalid, 3 Unknown, 0 Unchecked, 18.6s Time] [2023-11-29 05:35:30,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2023-11-29 05:35:30,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 120. [2023-11-29 05:35:30,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 76 states have (on average 1.0921052631578947) internal successors, (83), 80 states have internal predecessors, (83), 28 states have call successors, (28), 15 states have call predecessors, (28), 15 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2023-11-29 05:35:30,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 141 transitions. [2023-11-29 05:35:30,162 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 141 transitions. Word has length 54 [2023-11-29 05:35:30,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:35:30,163 INFO L495 AbstractCegarLoop]: Abstraction has 120 states and 141 transitions. [2023-11-29 05:35:30,163 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 12 states have call successors, (20), 8 states have call predecessors, (20), 4 states have return successors, (14), 7 states have call predecessors, (14), 8 states have call successors, (14) [2023-11-29 05:35:30,163 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 141 transitions. [2023-11-29 05:35:30,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-11-29 05:35:30,164 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:35:30,164 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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, 1] [2023-11-29 05:35:30,170 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-11-29 05:35:30,365 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-29 05:35:30,365 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:35:30,365 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:35:30,365 INFO L85 PathProgramCache]: Analyzing trace with hash 1336898608, now seen corresponding path program 1 times [2023-11-29 05:35:30,366 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:35:30,366 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [989088937] [2023-11-29 05:35:30,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:35:30,366 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:35:30,398 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:35:30,398 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2097488638] [2023-11-29 05:35:30,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:35:30,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:35:30,398 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:35:30,399 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:35:30,401 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-29 05:35:30,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:35:30,656 INFO L262 TraceCheckSpWp]: Trace formula consists of 679 conjuncts, 163 conjunts are in the unsatisfiable core [2023-11-29 05:35:30,664 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:35:30,712 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 05:35:30,909 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 05:35:30,935 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 11 [2023-11-29 05:35:30,950 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 05:35:35,051 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#b~0#1.base_BEFORE_CALL_23| Int) (|v_ULTIMATE.start_main_~#y~0#1.base_BEFORE_CALL_20| Int)) (= (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#b~0#1.base_BEFORE_CALL_23|) 0) (select (select |c_#memory_int#12| |v_ULTIMATE.start_main_~#y~0#1.base_BEFORE_CALL_20|) 0))) is different from true [2023-11-29 05:35:39,232 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#b~0#1.base_BEFORE_CALL_24| Int) (|v_ULTIMATE.start_main_~#y~0#1.base_BEFORE_CALL_21| Int)) (= (select (select |c_#memory_int#12| |v_ULTIMATE.start_main_~#y~0#1.base_BEFORE_CALL_21|) 0) (select (select |c_#memory_int#2| |v_ULTIMATE.start_main_~#b~0#1.base_BEFORE_CALL_24|) 0))) is different from true [2023-11-29 05:35:39,726 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 05:35:39,778 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 05:35:42,969 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 05:35:55,697 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 35 treesize of output 21 [2023-11-29 05:35:55,730 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 05:35:56,435 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 05:35:56,450 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 05:35:56,463 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 05:35:57,200 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 22 proven. 14 refuted. 9 times theorem prover too weak. 10 trivial. 4 not checked. [2023-11-29 05:35:57,200 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:35:59,351 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2023-11-29 05:35:59,351 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:35:59,351 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [989088937] [2023-11-29 05:35:59,351 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:35:59,351 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2097488638] [2023-11-29 05:35:59,352 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2097488638] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-29 05:35:59,352 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 05:35:59,352 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 8] total 28 [2023-11-29 05:35:59,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1614300477] [2023-11-29 05:35:59,352 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 05:35:59,353 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-11-29 05:35:59,353 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:35:59,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-11-29 05:35:59,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=571, Unknown=4, NotChecked=98, Total=756 [2023-11-29 05:35:59,355 INFO L87 Difference]: Start difference. First operand 120 states and 141 transitions. Second operand has 28 states, 23 states have (on average 2.5652173913043477) internal successors, (59), 22 states have internal predecessors, (59), 12 states have call successors, (24), 11 states have call predecessors, (24), 6 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2023-11-29 05:36:10,606 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 05:36:13,428 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:36:13,428 INFO L93 Difference]: Finished difference Result 169 states and 193 transitions. [2023-11-29 05:36:13,428 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2023-11-29 05:36:13,429 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 23 states have (on average 2.5652173913043477) internal successors, (59), 22 states have internal predecessors, (59), 12 states have call successors, (24), 11 states have call predecessors, (24), 6 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) Word has length 64 [2023-11-29 05:36:13,429 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:36:13,432 INFO L225 Difference]: With dead ends: 169 [2023-11-29 05:36:13,432 INFO L226 Difference]: Without dead ends: 167 [2023-11-29 05:36:13,433 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 93 SyntacticMatches, 8 SemanticMatches, 39 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 282 ImplicationChecksByTransitivity, 28.8s TimeCoverageRelationStatistics Valid=193, Invalid=1293, Unknown=4, NotChecked=150, Total=1640 [2023-11-29 05:36:13,434 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 88 mSDsluCounter, 418 mSDsCounter, 0 mSdLazyCounter, 608 mSolverCounterSat, 51 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 89 SdHoareTripleChecker+Valid, 464 SdHoareTripleChecker+Invalid, 1096 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 608 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 436 IncrementalHoareTripleChecker+Unchecked, 10.7s IncrementalHoareTripleChecker+Time [2023-11-29 05:36:13,435 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [89 Valid, 464 Invalid, 1096 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 608 Invalid, 1 Unknown, 436 Unchecked, 10.7s Time] [2023-11-29 05:36:13,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2023-11-29 05:36:13,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 160. [2023-11-29 05:36:13,491 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 160 states, 102 states have (on average 1.0686274509803921) internal successors, (109), 107 states have internal predecessors, (109), 33 states have call successors, (33), 21 states have call predecessors, (33), 24 states have return successors, (40), 32 states have call predecessors, (40), 32 states have call successors, (40) [2023-11-29 05:36:13,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 182 transitions. [2023-11-29 05:36:13,493 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 182 transitions. Word has length 64 [2023-11-29 05:36:13,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:36:13,493 INFO L495 AbstractCegarLoop]: Abstraction has 160 states and 182 transitions. [2023-11-29 05:36:13,493 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 23 states have (on average 2.5652173913043477) internal successors, (59), 22 states have internal predecessors, (59), 12 states have call successors, (24), 11 states have call predecessors, (24), 6 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2023-11-29 05:36:13,494 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 182 transitions. [2023-11-29 05:36:13,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-11-29 05:36:13,495 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:36:13,496 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:36:13,504 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-11-29 05:36:13,699 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-29 05:36:13,700 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:36:13,700 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:36:13,700 INFO L85 PathProgramCache]: Analyzing trace with hash -1343293503, now seen corresponding path program 1 times [2023-11-29 05:36:13,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:36:13,700 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1769183374] [2023-11-29 05:36:13,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:36:13,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:36:13,746 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:36:13,746 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1727522713] [2023-11-29 05:36:13,746 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:36:13,747 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:36:13,747 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:36:13,748 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:36:13,771 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-29 05:36:14,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:36:14,034 INFO L262 TraceCheckSpWp]: Trace formula consists of 717 conjuncts, 65 conjunts are in the unsatisfiable core [2023-11-29 05:36:14,039 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:36:14,648 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 05:36:14,680 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 05:36:14,709 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 05:36:20,778 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 05:36:22,026 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 22 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-29 05:36:22,026 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:36:28,145 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-11-29 05:36:28,146 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:36:28,146 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1769183374] [2023-11-29 05:36:28,146 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:36:28,146 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1727522713] [2023-11-29 05:36:28,146 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1727522713] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-29 05:36:28,147 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 05:36:28,147 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17] total 33 [2023-11-29 05:36:28,147 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [426463814] [2023-11-29 05:36:28,147 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 05:36:28,148 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2023-11-29 05:36:28,148 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:36:28,149 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2023-11-29 05:36:28,149 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=950, Unknown=1, NotChecked=0, Total=1056 [2023-11-29 05:36:28,150 INFO L87 Difference]: Start difference. First operand 160 states and 182 transitions. Second operand has 33 states, 29 states have (on average 2.2413793103448274) internal successors, (65), 29 states have internal predecessors, (65), 13 states have call successors, (23), 10 states have call predecessors, (23), 10 states have return successors, (22), 10 states have call predecessors, (22), 12 states have call successors, (22) [2023-11-29 05:36:33,628 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 05:36:47,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:36:47,515 INFO L93 Difference]: Finished difference Result 192 states and 226 transitions. [2023-11-29 05:36:47,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2023-11-29 05:36:47,516 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 29 states have (on average 2.2413793103448274) internal successors, (65), 29 states have internal predecessors, (65), 13 states have call successors, (23), 10 states have call predecessors, (23), 10 states have return successors, (22), 10 states have call predecessors, (22), 12 states have call successors, (22) Word has length 73 [2023-11-29 05:36:47,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:36:47,518 INFO L225 Difference]: With dead ends: 192 [2023-11-29 05:36:47,519 INFO L226 Difference]: Without dead ends: 176 [2023-11-29 05:36:47,521 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 172 GetRequests, 111 SyntacticMatches, 4 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 569 ImplicationChecksByTransitivity, 16.5s TimeCoverageRelationStatistics Valid=461, Invalid=2960, Unknown=1, NotChecked=0, Total=3422 [2023-11-29 05:36:47,521 INFO L413 NwaCegarLoop]: 15 mSDtfsCounter, 137 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 921 mSolverCounterSat, 156 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 1080 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 156 IncrementalHoareTripleChecker+Valid, 921 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.7s IncrementalHoareTripleChecker+Time [2023-11-29 05:36:47,521 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 114 Invalid, 1080 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [156 Valid, 921 Invalid, 3 Unknown, 0 Unchecked, 12.7s Time] [2023-11-29 05:36:47,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2023-11-29 05:36:47,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 168. [2023-11-29 05:36:47,564 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 168 states, 107 states have (on average 1.0654205607476634) internal successors, (114), 112 states have internal predecessors, (114), 34 states have call successors, (34), 22 states have call predecessors, (34), 26 states have return successors, (42), 33 states have call predecessors, (42), 33 states have call successors, (42) [2023-11-29 05:36:47,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 168 states to 168 states and 190 transitions. [2023-11-29 05:36:47,566 INFO L78 Accepts]: Start accepts. Automaton has 168 states and 190 transitions. Word has length 73 [2023-11-29 05:36:47,566 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:36:47,566 INFO L495 AbstractCegarLoop]: Abstraction has 168 states and 190 transitions. [2023-11-29 05:36:47,566 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 29 states have (on average 2.2413793103448274) internal successors, (65), 29 states have internal predecessors, (65), 13 states have call successors, (23), 10 states have call predecessors, (23), 10 states have return successors, (22), 10 states have call predecessors, (22), 12 states have call successors, (22) [2023-11-29 05:36:47,566 INFO L276 IsEmpty]: Start isEmpty. Operand 168 states and 190 transitions. [2023-11-29 05:36:47,567 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2023-11-29 05:36:47,567 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:36:47,568 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:36:47,573 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-11-29 05:36:47,768 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:36:47,768 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:36:47,769 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:36:47,769 INFO L85 PathProgramCache]: Analyzing trace with hash 1742802459, now seen corresponding path program 1 times [2023-11-29 05:36:47,769 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:36:47,769 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1743785538] [2023-11-29 05:36:47,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:36:47,769 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:36:47,807 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:36:47,808 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [538572403] [2023-11-29 05:36:47,808 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:36:47,808 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:36:47,808 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:36:47,809 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:36:47,810 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-29 05:36:48,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:36:48,076 INFO L262 TraceCheckSpWp]: Trace formula consists of 839 conjuncts, 197 conjunts are in the unsatisfiable core [2023-11-29 05:36:48,086 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:36:48,125 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 05:36:48,149 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 05:36:48,319 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 05:36:48,383 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 05:36:48,431 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 05:36:51,319 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 05:36:51,351 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 05:36:51,364 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 23 treesize of output 15 [2023-11-29 05:36:51,391 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 05:36:53,002 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 7 treesize of output 3 [2023-11-29 05:36:53,034 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 05:36:53,047 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 05:36:53,633 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 16 proven. 35 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2023-11-29 05:36:53,633 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:36:56,877 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 15 proven. 4 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2023-11-29 05:36:56,878 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:36:56,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1743785538] [2023-11-29 05:36:56,878 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:36:56,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [538572403] [2023-11-29 05:36:56,878 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [538572403] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-29 05:36:56,878 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 05:36:56,879 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 12] total 27 [2023-11-29 05:36:56,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [849938576] [2023-11-29 05:36:56,879 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 05:36:56,880 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-29 05:36:56,880 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:36:56,881 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-29 05:36:56,881 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=630, Unknown=0, NotChecked=0, Total=702 [2023-11-29 05:36:56,882 INFO L87 Difference]: Start difference. First operand 168 states and 190 transitions. Second operand has 27 states, 25 states have (on average 2.64) internal successors, (66), 18 states have internal predecessors, (66), 13 states have call successors, (28), 11 states have call predecessors, (28), 3 states have return successors, (20), 9 states have call predecessors, (20), 9 states have call successors, (20) [2023-11-29 05:37:08,526 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:37:08,526 INFO L93 Difference]: Finished difference Result 235 states and 268 transitions. [2023-11-29 05:37:08,527 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-11-29 05:37:08,527 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 2.64) internal successors, (66), 18 states have internal predecessors, (66), 13 states have call successors, (28), 11 states have call predecessors, (28), 3 states have return successors, (20), 9 states have call predecessors, (20), 9 states have call successors, (20) Word has length 77 [2023-11-29 05:37:08,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:37:08,529 INFO L225 Difference]: With dead ends: 235 [2023-11-29 05:37:08,529 INFO L226 Difference]: Without dead ends: 233 [2023-11-29 05:37:08,530 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 162 GetRequests, 122 SyntacticMatches, 6 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 243 ImplicationChecksByTransitivity, 6.8s TimeCoverageRelationStatistics Valid=135, Invalid=1125, Unknown=0, NotChecked=0, Total=1260 [2023-11-29 05:37:08,531 INFO L413 NwaCegarLoop]: 54 mSDtfsCounter, 76 mSDsluCounter, 532 mSDsCounter, 0 mSdLazyCounter, 887 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 586 SdHoareTripleChecker+Invalid, 930 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 887 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.5s IncrementalHoareTripleChecker+Time [2023-11-29 05:37:08,531 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 586 Invalid, 930 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 887 Invalid, 0 Unknown, 0 Unchecked, 9.5s Time] [2023-11-29 05:37:08,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2023-11-29 05:37:08,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 229. [2023-11-29 05:37:08,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 229 states, 145 states have (on average 1.0758620689655172) internal successors, (156), 152 states have internal predecessors, (156), 48 states have call successors, (48), 29 states have call predecessors, (48), 35 states have return successors, (59), 47 states have call predecessors, (59), 46 states have call successors, (59) [2023-11-29 05:37:08,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 263 transitions. [2023-11-29 05:37:08,592 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 263 transitions. Word has length 77 [2023-11-29 05:37:08,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:37:08,592 INFO L495 AbstractCegarLoop]: Abstraction has 229 states and 263 transitions. [2023-11-29 05:37:08,592 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 2.64) internal successors, (66), 18 states have internal predecessors, (66), 13 states have call successors, (28), 11 states have call predecessors, (28), 3 states have return successors, (20), 9 states have call predecessors, (20), 9 states have call successors, (20) [2023-11-29 05:37:08,592 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 263 transitions. [2023-11-29 05:37:08,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2023-11-29 05:37:08,594 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:37:08,594 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:37:08,600 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-11-29 05:37:08,794 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:37:08,794 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:37:08,795 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:37:08,795 INFO L85 PathProgramCache]: Analyzing trace with hash 71740918, now seen corresponding path program 2 times [2023-11-29 05:37:08,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:37:08,795 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1396160099] [2023-11-29 05:37:08,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:37:08,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:37:08,836 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:37:08,837 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1304467042] [2023-11-29 05:37:08,837 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-29 05:37:08,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:37:08,837 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:37:08,838 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:37:08,844 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-29 05:37:09,289 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-29 05:37:09,289 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-29 05:37:09,296 INFO L262 TraceCheckSpWp]: Trace formula consists of 858 conjuncts, 183 conjunts are in the unsatisfiable core [2023-11-29 05:37:09,303 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:37:09,321 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 05:37:09,667 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 05:37:09,705 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 05:37:09,732 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 05:37:09,759 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 05:37:11,831 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 05:37:11,845 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 23 treesize of output 15 [2023-11-29 05:37:11,912 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 05:37:12,153 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 05:37:21,994 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 05:37:22,020 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 27 treesize of output 19 [2023-11-29 05:37:22,034 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 05:37:22,077 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 05:37:24,891 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 05:37:24,905 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 05:37:25,571 INFO L134 CoverageAnalysis]: Checked inductivity of 107 backedges. 19 proven. 55 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2023-11-29 05:37:25,571 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:37:26,851 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:37:26,851 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1396160099] [2023-11-29 05:37:26,851 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:37:26,851 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1304467042] [2023-11-29 05:37:26,852 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1304467042] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 05:37:26,852 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:37:26,852 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2023-11-29 05:37:26,852 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [87223493] [2023-11-29 05:37:26,852 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 05:37:26,853 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-11-29 05:37:26,853 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:37:26,853 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-11-29 05:37:26,854 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=484, Unknown=2, NotChecked=0, Total=552 [2023-11-29 05:37:26,854 INFO L87 Difference]: Start difference. First operand 229 states and 263 transitions. Second operand has 20 states, 19 states have (on average 2.210526315789474) internal successors, (42), 16 states have internal predecessors, (42), 7 states have call successors, (15), 9 states have call predecessors, (15), 6 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2023-11-29 05:37:41,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:37:41,356 INFO L93 Difference]: Finished difference Result 290 states and 330 transitions. [2023-11-29 05:37:41,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-11-29 05:37:41,357 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.210526315789474) internal successors, (42), 16 states have internal predecessors, (42), 7 states have call successors, (15), 9 states have call predecessors, (15), 6 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) Word has length 83 [2023-11-29 05:37:41,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:37:41,360 INFO L225 Difference]: With dead ends: 290 [2023-11-29 05:37:41,360 INFO L226 Difference]: Without dead ends: 286 [2023-11-29 05:37:41,361 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 60 SyntacticMatches, 7 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 19.6s TimeCoverageRelationStatistics Valid=146, Invalid=1041, Unknown=3, NotChecked=0, Total=1190 [2023-11-29 05:37:41,362 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 63 mSDsluCounter, 383 mSDsCounter, 0 mSdLazyCounter, 823 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 429 SdHoareTripleChecker+Invalid, 863 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 823 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.3s IncrementalHoareTripleChecker+Time [2023-11-29 05:37:41,362 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 429 Invalid, 863 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 823 Invalid, 0 Unknown, 0 Unchecked, 7.3s Time] [2023-11-29 05:37:41,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2023-11-29 05:37:41,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 282. [2023-11-29 05:37:41,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 282 states, 180 states have (on average 1.0777777777777777) internal successors, (194), 188 states have internal predecessors, (194), 58 states have call successors, (58), 37 states have call predecessors, (58), 43 states have return successors, (71), 56 states have call predecessors, (71), 56 states have call successors, (71) [2023-11-29 05:37:41,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 282 states to 282 states and 323 transitions. [2023-11-29 05:37:41,439 INFO L78 Accepts]: Start accepts. Automaton has 282 states and 323 transitions. Word has length 83 [2023-11-29 05:37:41,440 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:37:41,440 INFO L495 AbstractCegarLoop]: Abstraction has 282 states and 323 transitions. [2023-11-29 05:37:41,440 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.210526315789474) internal successors, (42), 16 states have internal predecessors, (42), 7 states have call successors, (15), 9 states have call predecessors, (15), 6 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2023-11-29 05:37:41,440 INFO L276 IsEmpty]: Start isEmpty. Operand 282 states and 323 transitions. [2023-11-29 05:37:41,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2023-11-29 05:37:41,441 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:37:41,441 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:37:41,448 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-11-29 05:37:41,641 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:37:41,642 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:37:41,642 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:37:41,642 INFO L85 PathProgramCache]: Analyzing trace with hash 1144293007, now seen corresponding path program 3 times [2023-11-29 05:37:41,642 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:37:41,642 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1279513865] [2023-11-29 05:37:41,642 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:37:41,643 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:37:41,681 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:37:41,681 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1501387113] [2023-11-29 05:37:41,681 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-29 05:37:41,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:37:41,682 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:37:41,683 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:37:41,693 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-29 05:37:42,165 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-29 05:37:42,166 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-29 05:37:42,174 INFO L262 TraceCheckSpWp]: Trace formula consists of 821 conjuncts, 310 conjunts are in the unsatisfiable core [2023-11-29 05:37:42,183 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:37:42,200 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 05:37:42,309 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 05:37:42,737 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 05:37:42,800 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 05:37:42,826 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 05:37:42,854 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 05:37:42,951 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 21 treesize of output 17 [2023-11-29 05:37:42,996 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 05:37:48,610 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 05:37:48,867 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 05:37:48,888 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 23 treesize of output 15 [2023-11-29 05:37:53,340 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 05:38:00,855 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 27 treesize of output 19 [2023-11-29 05:38:00,874 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 27 treesize of output 19 [2023-11-29 05:38:00,910 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 05:38:01,012 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 05:38:21,493 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 32 treesize of output 20 [2023-11-29 05:38:21,509 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 32 treesize of output 20 [2023-11-29 05:38:21,523 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 19 [2023-11-29 05:38:21,538 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 05:38:22,456 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 25 proven. 75 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2023-11-29 05:38:22,456 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:38:26,110 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:38:26,110 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1279513865] [2023-11-29 05:38:26,110 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:38:26,110 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1501387113] [2023-11-29 05:38:26,110 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1501387113] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 05:38:26,110 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:38:26,110 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2023-11-29 05:38:26,111 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1109952254] [2023-11-29 05:38:26,111 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 05:38:26,111 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-11-29 05:38:26,111 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:38:26,112 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-11-29 05:38:26,112 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=723, Unknown=1, NotChecked=0, Total=812 [2023-11-29 05:38:26,113 INFO L87 Difference]: Start difference. First operand 282 states and 323 transitions. Second operand has 24 states, 22 states have (on average 2.090909090909091) internal successors, (46), 20 states have internal predecessors, (46), 9 states have call successors, (16), 9 states have call predecessors, (16), 7 states have return successors, (12), 6 states have call predecessors, (12), 7 states have call successors, (12) [2023-11-29 05:38:43,288 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 05:38:49,347 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.66s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 05:39:01,719 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.12s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 05:39:04,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:39:04,698 INFO L93 Difference]: Finished difference Result 299 states and 338 transitions. [2023-11-29 05:39:04,699 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2023-11-29 05:39:04,699 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 2.090909090909091) internal successors, (46), 20 states have internal predecessors, (46), 9 states have call successors, (16), 9 states have call predecessors, (16), 7 states have return successors, (12), 6 states have call predecessors, (12), 7 states have call successors, (12) Word has length 89 [2023-11-29 05:39:04,700 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:39:04,701 INFO L225 Difference]: With dead ends: 299 [2023-11-29 05:39:04,701 INFO L226 Difference]: Without dead ends: 297 [2023-11-29 05:39:04,703 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 58 SyntacticMatches, 9 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 445 ImplicationChecksByTransitivity, 47.4s TimeCoverageRelationStatistics Valid=202, Invalid=1689, Unknown=1, NotChecked=0, Total=1892 [2023-11-29 05:39:04,703 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 89 mSDsluCounter, 252 mSDsCounter, 0 mSdLazyCounter, 673 mSolverCounterSat, 46 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 24.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 296 SdHoareTripleChecker+Invalid, 720 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 673 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 24.7s IncrementalHoareTripleChecker+Time [2023-11-29 05:39:04,703 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [95 Valid, 296 Invalid, 720 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 673 Invalid, 1 Unknown, 0 Unchecked, 24.7s Time] [2023-11-29 05:39:04,704 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 297 states. [2023-11-29 05:39:04,779 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 297 to 291. [2023-11-29 05:39:04,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 291 states, 186 states have (on average 1.075268817204301) internal successors, (200), 195 states have internal predecessors, (200), 59 states have call successors, (59), 39 states have call predecessors, (59), 45 states have return successors, (71), 57 states have call predecessors, (71), 57 states have call successors, (71) [2023-11-29 05:39:04,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 291 states to 291 states and 330 transitions. [2023-11-29 05:39:04,782 INFO L78 Accepts]: Start accepts. Automaton has 291 states and 330 transitions. Word has length 89 [2023-11-29 05:39:04,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:39:04,782 INFO L495 AbstractCegarLoop]: Abstraction has 291 states and 330 transitions. [2023-11-29 05:39:04,782 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 2.090909090909091) internal successors, (46), 20 states have internal predecessors, (46), 9 states have call successors, (16), 9 states have call predecessors, (16), 7 states have return successors, (12), 6 states have call predecessors, (12), 7 states have call successors, (12) [2023-11-29 05:39:04,783 INFO L276 IsEmpty]: Start isEmpty. Operand 291 states and 330 transitions. [2023-11-29 05:39:04,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2023-11-29 05:39:04,784 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:39:04,784 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:39:04,792 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-11-29 05:39:04,984 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:39:04,984 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:39:04,985 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:39:04,985 INFO L85 PathProgramCache]: Analyzing trace with hash -914886710, now seen corresponding path program 1 times [2023-11-29 05:39:04,985 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:39:04,985 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [255523394] [2023-11-29 05:39:04,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:39:04,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:39:05,020 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:39:05,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [420975543] [2023-11-29 05:39:05,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:39:05,021 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:39:05,021 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:39:05,022 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:39:05,023 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-29 05:39:05,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:39:05,402 INFO L262 TraceCheckSpWp]: Trace formula consists of 918 conjuncts, 212 conjunts are in the unsatisfiable core [2023-11-29 05:39:05,413 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:39:05,431 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 05:39:05,519 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 05:39:05,852 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 05:39:05,892 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 05:39:05,920 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 05:39:05,948 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 05:39:06,003 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 05:39:06,074 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 05:39:08,122 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 05:39:08,136 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 05:39:09,193 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 05:39:09,386 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 05:39:11,733 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 05:39:12,746 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 05:39:12,779 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 46 treesize of output 28 [2023-11-29 05:39:13,531 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 28 [2023-11-29 05:39:15,885 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 23 treesize of output 15 [2023-11-29 05:39:15,899 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 23 treesize of output 15 [2023-11-29 05:39:15,932 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 05:39:15,959 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 13 [2023-11-29 05:39:16,299 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 05:39:16,313 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 05:39:17,144 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 49 proven. 21 refuted. 0 times theorem prover too weak. 100 trivial. 0 not checked. [2023-11-29 05:39:17,144 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:39:41,570 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:39:41,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [255523394] [2023-11-29 05:39:41,571 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:39:41,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [420975543] [2023-11-29 05:39:41,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [420975543] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 05:39:41,571 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:39:41,571 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2023-11-29 05:39:41,571 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1535212964] [2023-11-29 05:39:41,572 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 05:39:41,572 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-11-29 05:39:41,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:39:41,573 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-11-29 05:39:41,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=904, Unknown=2, NotChecked=0, Total=992 [2023-11-29 05:39:41,574 INFO L87 Difference]: Start difference. First operand 291 states and 330 transitions. Second operand has 26 states, 22 states have (on average 2.090909090909091) internal successors, (46), 21 states have internal predecessors, (46), 8 states have call successors, (17), 6 states have call predecessors, (17), 7 states have return successors, (16), 8 states have call predecessors, (16), 7 states have call successors, (16) [2023-11-29 05:40:06,016 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:40:06,017 INFO L93 Difference]: Finished difference Result 319 states and 371 transitions. [2023-11-29 05:40:06,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2023-11-29 05:40:06,019 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 22 states have (on average 2.090909090909091) internal successors, (46), 21 states have internal predecessors, (46), 8 states have call successors, (17), 6 states have call predecessors, (17), 7 states have return successors, (16), 8 states have call predecessors, (16), 7 states have call successors, (16) Word has length 103 [2023-11-29 05:40:06,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:40:06,023 INFO L225 Difference]: With dead ends: 319 [2023-11-29 05:40:06,023 INFO L226 Difference]: Without dead ends: 317 [2023-11-29 05:40:06,026 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 81 SyntacticMatches, 3 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 673 ImplicationChecksByTransitivity, 34.5s TimeCoverageRelationStatistics Valid=345, Invalid=3193, Unknown=2, NotChecked=0, Total=3540 [2023-11-29 05:40:06,026 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 128 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 1126 mSolverCounterSat, 121 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 129 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 1247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 121 IncrementalHoareTripleChecker+Valid, 1126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.4s IncrementalHoareTripleChecker+Time [2023-11-29 05:40:06,027 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [129 Valid, 153 Invalid, 1247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [121 Valid, 1126 Invalid, 0 Unknown, 0 Unchecked, 11.4s Time] [2023-11-29 05:40:06,027 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 317 states. [2023-11-29 05:40:06,128 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 317 to 313. [2023-11-29 05:40:06,129 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 313 states, 198 states have (on average 1.0707070707070707) internal successors, (212), 207 states have internal predecessors, (212), 62 states have call successors, (62), 40 states have call predecessors, (62), 52 states have return successors, (90), 65 states have call predecessors, (90), 60 states have call successors, (90) [2023-11-29 05:40:06,131 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 313 states to 313 states and 364 transitions. [2023-11-29 05:40:06,131 INFO L78 Accepts]: Start accepts. Automaton has 313 states and 364 transitions. Word has length 103 [2023-11-29 05:40:06,131 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:40:06,131 INFO L495 AbstractCegarLoop]: Abstraction has 313 states and 364 transitions. [2023-11-29 05:40:06,132 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 22 states have (on average 2.090909090909091) internal successors, (46), 21 states have internal predecessors, (46), 8 states have call successors, (17), 6 states have call predecessors, (17), 7 states have return successors, (16), 8 states have call predecessors, (16), 7 states have call successors, (16) [2023-11-29 05:40:06,132 INFO L276 IsEmpty]: Start isEmpty. Operand 313 states and 364 transitions. [2023-11-29 05:40:06,133 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2023-11-29 05:40:06,133 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:40:06,134 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:40:06,140 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2023-11-29 05:40:06,334 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:40:06,334 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:40:06,335 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:40:06,335 INFO L85 PathProgramCache]: Analyzing trace with hash 18697309, now seen corresponding path program 1 times [2023-11-29 05:40:06,335 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:40:06,335 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [91159291] [2023-11-29 05:40:06,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:40:06,335 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:40:06,376 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:40:06,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2122898022] [2023-11-29 05:40:06,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:40:06,377 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:40:06,377 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:40:06,378 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:40:06,379 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-29 05:40:06,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:40:06,780 INFO L262 TraceCheckSpWp]: Trace formula consists of 937 conjuncts, 299 conjunts are in the unsatisfiable core [2023-11-29 05:40:06,792 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:40:06,864 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 05:40:06,933 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 05:40:07,397 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 05:40:07,436 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 05:40:07,502 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 05:40:07,532 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 05:40:07,609 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 05:40:09,575 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 05:40:09,589 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 05:40:10,818 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 05:40:11,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 11 treesize of output 7 [2023-11-29 05:40:11,502 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 05:40:19,349 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_func_to_recursive_line_45_to_53_0_#in~q.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_45_to_53_0_#in~x.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_45_to_53_0_#in~b.offset_BEFORE_CALL_12| Int) (|v_func_to_recursive_line_45_to_53_0_#in~q.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_45_to_53_0_#in~s.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_45_to_53_0_#in~y.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_45_to_53_0_#in~x.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_45_to_53_0_#in~b.base_BEFORE_CALL_12| Int) (|v_func_to_recursive_line_45_to_53_0_#in~s.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_45_to_53_0_#in~y.base_BEFORE_CALL_4| Int)) (= (+ (* (select (select |c_#memory_int#6| |v_func_to_recursive_line_45_to_53_0_#in~q.base_BEFORE_CALL_4|) |v_func_to_recursive_line_45_to_53_0_#in~q.offset_BEFORE_CALL_4|) (select (select |c_#memory_int#11| |v_func_to_recursive_line_45_to_53_0_#in~x.base_BEFORE_CALL_4|) |v_func_to_recursive_line_45_to_53_0_#in~x.offset_BEFORE_CALL_4|)) (* (select (select |c_#memory_int#8| |v_func_to_recursive_line_45_to_53_0_#in~s.base_BEFORE_CALL_4|) |v_func_to_recursive_line_45_to_53_0_#in~s.offset_BEFORE_CALL_4|) (select (select |c_#memory_int#12| |v_func_to_recursive_line_45_to_53_0_#in~y.base_BEFORE_CALL_4|) |v_func_to_recursive_line_45_to_53_0_#in~y.offset_BEFORE_CALL_4|))) (select (select |c_#memory_int#2| |v_func_to_recursive_line_45_to_53_0_#in~b.base_BEFORE_CALL_12|) |v_func_to_recursive_line_45_to_53_0_#in~b.offset_BEFORE_CALL_12|))) is different from true [2023-11-29 05:40:25,261 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 05:40:50,654 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_func_to_recursive_line_45_to_53_0_#in~q.offset_BEFORE_CALL_5| Int) (|v_func_to_recursive_line_45_to_53_0_#in~x.offset_BEFORE_CALL_5| Int) (|v_func_to_recursive_line_45_to_53_0_#in~x.base_BEFORE_CALL_5| Int) (|v_func_to_recursive_line_45_to_53_0_#in~b.offset_BEFORE_CALL_13| Int) (|v_func_to_recursive_line_45_to_53_0_#in~q.base_BEFORE_CALL_5| Int) (|v_func_to_recursive_line_45_to_53_0_#in~s.offset_BEFORE_CALL_5| Int) (|v_func_to_recursive_line_45_to_53_0_#in~y.offset_BEFORE_CALL_5| Int) (|v_func_to_recursive_line_45_to_53_0_#in~b.base_BEFORE_CALL_13| Int) (|v_func_to_recursive_line_45_to_53_0_#in~y.base_BEFORE_CALL_5| Int) (|v_func_to_recursive_line_45_to_53_0_#in~s.base_BEFORE_CALL_5| Int)) (= (select (select |c_#memory_int#2| |v_func_to_recursive_line_45_to_53_0_#in~b.base_BEFORE_CALL_13|) |v_func_to_recursive_line_45_to_53_0_#in~b.offset_BEFORE_CALL_13|) (+ (* (select (select |c_#memory_int#6| |v_func_to_recursive_line_45_to_53_0_#in~q.base_BEFORE_CALL_5|) |v_func_to_recursive_line_45_to_53_0_#in~q.offset_BEFORE_CALL_5|) (select (select |c_#memory_int#11| |v_func_to_recursive_line_45_to_53_0_#in~x.base_BEFORE_CALL_5|) |v_func_to_recursive_line_45_to_53_0_#in~x.offset_BEFORE_CALL_5|)) (* (select (select |c_#memory_int#8| |v_func_to_recursive_line_45_to_53_0_#in~s.base_BEFORE_CALL_5|) |v_func_to_recursive_line_45_to_53_0_#in~s.offset_BEFORE_CALL_5|) (select (select |c_#memory_int#12| |v_func_to_recursive_line_45_to_53_0_#in~y.base_BEFORE_CALL_5|) |v_func_to_recursive_line_45_to_53_0_#in~y.offset_BEFORE_CALL_5|))))) is different from true [2023-11-29 05:41:02,256 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 55 treesize of output 28 [2023-11-29 05:41:02,513 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 05:41:03,580 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 05:41:03,645 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 21 [2023-11-29 05:41:04,595 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:41:04,595 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 59 treesize of output 63 [2023-11-29 05:41:04,693 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:41:04,694 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 62 treesize of output 62 [2023-11-29 05:41:04,723 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 34 [2023-11-29 05:41:05,145 INFO L349 Elim1Store]: treesize reduction 20, result has 58.3 percent of original size [2023-11-29 05:41:05,146 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 86 treesize of output 82 [2023-11-29 05:41:05,278 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:41:05,278 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 56 treesize of output 60 [2023-11-29 05:41:05,304 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 44 treesize of output 36 [2023-11-29 05:41:08,590 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:41:08,590 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 41 [2023-11-29 05:41:08,711 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:41:08,712 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 33 treesize of output 37 [2023-11-29 05:41:09,130 INFO L349 Elim1Store]: treesize reduction 20, result has 58.3 percent of original size [2023-11-29 05:41:09,131 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 91 treesize of output 83 [2023-11-29 05:41:09,163 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 55 treesize of output 39 [2023-11-29 05:41:09,288 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:41:09,288 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 54 treesize of output 54 [2023-11-29 05:41:09,420 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 05:41:11,335 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 05:41:11,349 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 05:41:11,361 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 05:41:16,971 INFO L134 CoverageAnalysis]: Checked inductivity of 204 backedges. 85 proven. 27 refuted. 0 times theorem prover too weak. 29 trivial. 63 not checked. [2023-11-29 05:41:16,971 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:41:37,803 WARN L293 SmtUtils]: Spent 13.70s on a formula simplification. DAG size of input: 276 DAG size of output: 276 (called from [L 279] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.cfg.transitions.TransFormulaUtils.sequentialComposition) [2023-11-29 05:41:43,396 WARN L293 SmtUtils]: Spent 5.59s on a formula simplification that was a NOOP. DAG size: 130 (called from [L 302] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.cfg.transitions.TransFormulaUtils.sequentialComposition) [2023-11-29 05:42:09,600 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 124 treesize of output 120 [2023-11-29 05:42:16,023 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:42:16,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [91159291] [2023-11-29 05:42:16,024 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:42:16,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2122898022] [2023-11-29 05:42:16,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2122898022] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 05:42:16,024 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:42:16,024 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [36] total 36 [2023-11-29 05:42:16,024 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2073496612] [2023-11-29 05:42:16,024 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 05:42:16,025 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2023-11-29 05:42:16,025 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:42:16,026 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2023-11-29 05:42:16,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=1835, Unknown=10, NotChecked=174, Total=2162 [2023-11-29 05:42:16,027 INFO L87 Difference]: Start difference. First operand 313 states and 364 transitions. Second operand has 36 states, 30 states have (on average 1.9666666666666666) internal successors, (59), 31 states have internal predecessors, (59), 12 states have call successors, (18), 10 states have call predecessors, (18), 11 states have return successors, (17), 10 states have call predecessors, (17), 11 states have call successors, (17) [2023-11-29 05:42:21,461 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 05:42:27,083 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 05:42:31,845 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.53s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 05:42:35,882 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.61s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 05:42:40,231 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 05:42:50,566 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.22s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2023-11-29 05:43:17,143 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 05:43:21,149 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 05:43:33,889 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 05:43:49,548 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 05:44:21,561 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 05:44:25,912 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 05:44:38,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:44:38,288 INFO L93 Difference]: Finished difference Result 341 states and 389 transitions. [2023-11-29 05:44:38,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2023-11-29 05:44:38,289 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 30 states have (on average 1.9666666666666666) internal successors, (59), 31 states have internal predecessors, (59), 12 states have call successors, (18), 10 states have call predecessors, (18), 11 states have return successors, (17), 10 states have call predecessors, (17), 11 states have call successors, (17) Word has length 109 [2023-11-29 05:44:38,289 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:44:38,291 INFO L225 Difference]: With dead ends: 341 [2023-11-29 05:44:38,292 INFO L226 Difference]: Without dead ends: 325 [2023-11-29 05:44:38,296 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 84 SyntacticMatches, 10 SemanticMatches, 91 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 2189 ImplicationChecksByTransitivity, 158.5s TimeCoverageRelationStatistics Valid=802, Invalid=7380, Unknown=16, NotChecked=358, Total=8556 [2023-11-29 05:44:38,297 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 153 mSDsluCounter, 176 mSDsCounter, 0 mSdLazyCounter, 1745 mSolverCounterSat, 144 mSolverCounterUnsat, 17 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 62.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 154 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 2165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 144 IncrementalHoareTripleChecker+Valid, 1745 IncrementalHoareTripleChecker+Invalid, 17 IncrementalHoareTripleChecker+Unknown, 259 IncrementalHoareTripleChecker+Unchecked, 64.5s IncrementalHoareTripleChecker+Time [2023-11-29 05:44:38,297 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [154 Valid, 193 Invalid, 2165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [144 Valid, 1745 Invalid, 17 Unknown, 259 Unchecked, 64.5s Time] [2023-11-29 05:44:38,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 325 states. [2023-11-29 05:44:38,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 325 to 321. [2023-11-29 05:44:38,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 321 states, 205 states have (on average 1.078048780487805) internal successors, (221), 214 states have internal predecessors, (221), 61 states have call successors, (61), 43 states have call predecessors, (61), 54 states have return successors, (87), 63 states have call predecessors, (87), 59 states have call successors, (87) [2023-11-29 05:44:38,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 321 states to 321 states and 369 transitions. [2023-11-29 05:44:38,405 INFO L78 Accepts]: Start accepts. Automaton has 321 states and 369 transitions. Word has length 109 [2023-11-29 05:44:38,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:44:38,405 INFO L495 AbstractCegarLoop]: Abstraction has 321 states and 369 transitions. [2023-11-29 05:44:38,405 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 30 states have (on average 1.9666666666666666) internal successors, (59), 31 states have internal predecessors, (59), 12 states have call successors, (18), 10 states have call predecessors, (18), 11 states have return successors, (17), 10 states have call predecessors, (17), 11 states have call successors, (17) [2023-11-29 05:44:38,405 INFO L276 IsEmpty]: Start isEmpty. Operand 321 states and 369 transitions. [2023-11-29 05:44:38,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2023-11-29 05:44:38,407 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:44:38,407 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:44:38,414 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2023-11-29 05:44:38,607 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:44:38,608 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:44:38,608 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:44:38,608 INFO L85 PathProgramCache]: Analyzing trace with hash -2105378551, now seen corresponding path program 4 times [2023-11-29 05:44:38,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:44:38,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1083949124] [2023-11-29 05:44:38,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:44:38,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:44:38,644 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:44:38,644 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2075977413] [2023-11-29 05:44:38,644 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-29 05:44:38,644 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:44:38,644 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:44:38,645 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:44:38,646 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-11-29 05:44:38,947 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-29 05:44:38,947 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-29 05:44:38,952 INFO L262 TraceCheckSpWp]: Trace formula consists of 1016 conjuncts, 106 conjunts are in the unsatisfiable core [2023-11-29 05:44:38,957 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:44:38,969 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 11 [2023-11-29 05:44:38,981 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 05:44:39,004 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 05:44:39,051 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 05:44:40,067 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 36 treesize of output 24 [2023-11-29 05:44:40,082 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 40 treesize of output 17 [2023-11-29 05:44:40,095 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 40 treesize of output 17 [2023-11-29 05:44:40,312 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 21 [2023-11-29 05:44:40,339 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 05:44:40,448 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 13 treesize of output 9 [2023-11-29 05:44:41,087 INFO L134 CoverageAnalysis]: Checked inductivity of 223 backedges. 71 proven. 1 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2023-11-29 05:44:41,087 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:44:44,361 INFO L134 CoverageAnalysis]: Checked inductivity of 223 backedges. 43 proven. 12 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2023-11-29 05:44:44,362 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:44:44,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1083949124] [2023-11-29 05:44:44,362 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:44:44,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2075977413] [2023-11-29 05:44:44,362 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2075977413] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-29 05:44:44,362 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-29 05:44:44,362 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13] total 22 [2023-11-29 05:44:44,362 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [54176581] [2023-11-29 05:44:44,362 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-29 05:44:44,363 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-11-29 05:44:44,363 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:44:44,364 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-11-29 05:44:44,364 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=394, Unknown=0, NotChecked=0, Total=462 [2023-11-29 05:44:44,365 INFO L87 Difference]: Start difference. First operand 321 states and 369 transitions. Second operand has 22 states, 19 states have (on average 3.1052631578947367) internal successors, (59), 16 states have internal predecessors, (59), 10 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) [2023-11-29 05:44:50,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-29 05:44:50,977 INFO L93 Difference]: Finished difference Result 414 states and 495 transitions. [2023-11-29 05:44:50,977 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2023-11-29 05:44:50,978 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 19 states have (on average 3.1052631578947367) internal successors, (59), 16 states have internal predecessors, (59), 10 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) Word has length 112 [2023-11-29 05:44:50,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-29 05:44:50,980 INFO L225 Difference]: With dead ends: 414 [2023-11-29 05:44:50,980 INFO L226 Difference]: Without dead ends: 339 [2023-11-29 05:44:50,981 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 204 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 250 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=187, Invalid=1145, Unknown=0, NotChecked=0, Total=1332 [2023-11-29 05:44:50,982 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 51 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 615 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 275 SdHoareTripleChecker+Invalid, 666 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 615 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.5s IncrementalHoareTripleChecker+Time [2023-11-29 05:44:50,982 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 275 Invalid, 666 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 615 Invalid, 0 Unknown, 0 Unchecked, 4.5s Time] [2023-11-29 05:44:50,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states. [2023-11-29 05:44:51,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 332. [2023-11-29 05:44:51,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 332 states, 214 states have (on average 1.074766355140187) internal successors, (230), 222 states have internal predecessors, (230), 63 states have call successors, (63), 46 states have call predecessors, (63), 54 states have return successors, (90), 63 states have call predecessors, (90), 61 states have call successors, (90) [2023-11-29 05:44:51,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 332 states to 332 states and 383 transitions. [2023-11-29 05:44:51,100 INFO L78 Accepts]: Start accepts. Automaton has 332 states and 383 transitions. Word has length 112 [2023-11-29 05:44:51,100 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-29 05:44:51,100 INFO L495 AbstractCegarLoop]: Abstraction has 332 states and 383 transitions. [2023-11-29 05:44:51,101 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 19 states have (on average 3.1052631578947367) internal successors, (59), 16 states have internal predecessors, (59), 10 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) [2023-11-29 05:44:51,101 INFO L276 IsEmpty]: Start isEmpty. Operand 332 states and 383 transitions. [2023-11-29 05:44:51,102 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2023-11-29 05:44:51,102 INFO L187 NwaCegarLoop]: Found error trace [2023-11-29 05:44:51,102 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-29 05:44:51,108 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2023-11-29 05:44:51,302 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:44:51,303 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-29 05:44:51,303 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-29 05:44:51,303 INFO L85 PathProgramCache]: Analyzing trace with hash -1660686657, now seen corresponding path program 1 times [2023-11-29 05:44:51,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-29 05:44:51,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621587989] [2023-11-29 05:44:51,303 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:44:51,303 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-29 05:44:51,336 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-29 05:44:51,336 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [42392707] [2023-11-29 05:44:51,336 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-29 05:44:51,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-29 05:44:51,337 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-29 05:44:51,337 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-29 05:44:51,339 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_c2e61e98-eb5d-4c5b-a23a-02587fa16ff6/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-11-29 05:44:51,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-29 05:44:51,872 INFO L262 TraceCheckSpWp]: Trace formula consists of 1059 conjuncts, 393 conjunts are in the unsatisfiable core [2023-11-29 05:44:51,881 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-29 05:44:51,945 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 05:44:51,958 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 05:44:52,442 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 05:44:52,478 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 05:44:52,527 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 05:44:52,553 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 05:44:52,579 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 05:44:52,608 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 05:44:52,650 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 05:44:55,639 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 05:44:55,764 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 05:44:55,780 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 23 treesize of output 15 [2023-11-29 05:44:56,167 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 05:45:28,575 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 35 treesize of output 21 [2023-11-29 05:45:28,697 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 05:45:33,375 INFO L349 Elim1Store]: treesize reduction 23, result has 32.4 percent of original size [2023-11-29 05:45:33,376 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 27 [2023-11-29 05:45:33,402 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 33 treesize of output 25 [2023-11-29 05:45:33,603 INFO L349 Elim1Store]: treesize reduction 18, result has 52.6 percent of original size [2023-11-29 05:45:33,604 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 46 treesize of output 47 [2023-11-29 05:45:33,810 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-11-29 05:45:33,810 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2023-11-29 05:45:33,926 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2023-11-29 05:45:33,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 15 treesize of output 7 [2023-11-29 05:45:43,349 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:45:43,350 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 76 treesize of output 84 [2023-11-29 05:45:43,586 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-29 05:45:43,587 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 64 treesize of output 80 [2023-11-29 05:45:43,604 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 05:45:44,637 INFO L134 CoverageAnalysis]: Checked inductivity of 255 backedges. 19 proven. 114 refuted. 0 times theorem prover too weak. 122 trivial. 0 not checked. [2023-11-29 05:45:44,637 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-29 05:46:17,776 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-29 05:46:17,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621587989] [2023-11-29 05:46:17,777 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-29 05:46:17,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [42392707] [2023-11-29 05:46:17,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [42392707] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-29 05:46:17,777 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-29 05:46:17,777 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2023-11-29 05:46:17,777 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [398105632] [2023-11-29 05:46:17,777 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-29 05:46:17,778 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-29 05:46:17,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-29 05:46:17,778 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-29 05:46:17,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=1197, Unknown=12, NotChecked=0, Total=1332 [2023-11-29 05:46:17,779 INFO L87 Difference]: Start difference. First operand 332 states and 383 transitions. Second operand has 27 states, 24 states have (on average 2.0833333333333335) internal successors, (50), 22 states have internal predecessors, (50), 11 states have call successors, (20), 9 states have call predecessors, (20), 7 states have return successors, (16), 9 states have call predecessors, (16), 9 states have call successors, (16)