./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/config/AutomizerReach.xml -i ../../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-13 15:54:14,630 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-13 15:54:14,728 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-13 15:54:14,734 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-13 15:54:14,736 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-13 15:54:14,769 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-13 15:54:14,770 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-13 15:54:14,770 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-13 15:54:14,771 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-13 15:54:14,771 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-13 15:54:14,771 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-13 15:54:14,771 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-13 15:54:14,771 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-13 15:54:14,771 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-13 15:54:14,772 INFO L153 SettingsManager]: * Use SBE=true [2024-11-13 15:54:14,772 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-13 15:54:14,772 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-13 15:54:14,773 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-13 15:54:14,773 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-13 15:54:14,774 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-13 15:54:14,774 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-13 15:54:14,775 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-13 15:54:14,775 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-13 15:54:14,776 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-13 15:54:14,776 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-13 15:54:14,776 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 [2024-11-13 15:54:15,075 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-13 15:54:15,087 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-13 15:54:15,092 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-13 15:54:15,093 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-13 15:54:15,093 INFO L274 PluginConnector]: CDTParser initialized [2024-11-13 15:54:15,095 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/../../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c Unable to find full path for "g++" [2024-11-13 15:54:16,899 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-13 15:54:17,267 INFO L384 CDTParser]: Found 1 translation units. [2024-11-13 15:54:17,271 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2024-11-13 15:54:17,284 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/data/c75e44bd8/b6d25f8ce4a047b98f55652199eb042f/FLAG032fc596c [2024-11-13 15:54:17,307 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/data/c75e44bd8/b6d25f8ce4a047b98f55652199eb042f [2024-11-13 15:54:17,310 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-13 15:54:17,312 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-13 15:54:17,315 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-13 15:54:17,315 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-13 15:54:17,320 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-13 15:54:17,321 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,322 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6e297f44 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17, skipping insertion in model container [2024-11-13 15:54:17,324 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,344 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-13 15:54:17,514 WARN L250 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_1432696a-ad04-4b39-9959-3da1dd8b3195/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c[1076,1089] [2024-11-13 15:54:17,580 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-13 15:54:17,597 INFO L200 MainTranslator]: Completed pre-run [2024-11-13 15:54:17,611 WARN L250 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_1432696a-ad04-4b39-9959-3da1dd8b3195/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c[1076,1089] [2024-11-13 15:54:17,659 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-13 15:54:17,678 INFO L204 MainTranslator]: Completed translation [2024-11-13 15:54:17,678 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17 WrapperNode [2024-11-13 15:54:17,680 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-13 15:54:17,681 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-13 15:54:17,682 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-13 15:54:17,682 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-13 15:54:17,689 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,704 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,734 INFO L138 Inliner]: procedures = 17, calls = 173, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 114 [2024-11-13 15:54:17,734 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-13 15:54:17,735 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-13 15:54:17,735 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-13 15:54:17,736 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-13 15:54:17,744 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,745 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,749 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,786 INFO L175 MemorySlicer]: Split 139 memory accesses to 6 slices as follows [2, 30, 21, 35, 22, 29]. 25 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 2, 1, 3, 2, 3]. [2024-11-13 15:54:17,787 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,787 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,802 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,807 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,813 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,814 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,822 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-13 15:54:17,822 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-13 15:54:17,823 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-13 15:54:17,826 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-13 15:54:17,827 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (1/1) ... [2024-11-13 15:54:17,833 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-13 15:54:17,846 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:54:17,864 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-13 15:54:17,871 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-13 15:54:17,896 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-13 15:54:17,896 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_33_0 [2024-11-13 15:54:17,897 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_33_0 [2024-11-13 15:54:17,897 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-13 15:54:17,897 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-13 15:54:17,898 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-13 15:54:17,898 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-13 15:54:17,898 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-13 15:54:17,898 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-13 15:54:17,898 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-13 15:54:17,898 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-13 15:54:17,899 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-13 15:54:17,899 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-13 15:54:17,899 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-13 15:54:17,899 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-13 15:54:17,899 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-13 15:54:17,899 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_37_to_53_0 [2024-11-13 15:54:17,899 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_37_to_53_0 [2024-11-13 15:54:17,900 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-13 15:54:17,900 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-13 15:54:17,900 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-13 15:54:17,900 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-13 15:54:17,900 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-13 15:54:17,900 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-13 15:54:17,900 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-13 15:54:17,900 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-13 15:54:17,901 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-13 15:54:17,901 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-13 15:54:17,902 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-13 15:54:18,040 INFO L238 CfgBuilder]: Building ICFG [2024-11-13 15:54:18,042 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-13 15:54:18,439 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-13 15:54:18,439 INFO L287 CfgBuilder]: Performing block encoding [2024-11-13 15:54:18,448 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-13 15:54:18,449 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-13 15:54:18,449 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.11 03:54:18 BoogieIcfgContainer [2024-11-13 15:54:18,449 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-13 15:54:18,452 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-13 15:54:18,452 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-13 15:54:18,456 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-13 15:54:18,457 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 13.11 03:54:17" (1/3) ... [2024-11-13 15:54:18,457 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1827eb4d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 13.11 03:54:18, skipping insertion in model container [2024-11-13 15:54:18,457 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.11 03:54:17" (2/3) ... [2024-11-13 15:54:18,458 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1827eb4d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 13.11 03:54:18, skipping insertion in model container [2024-11-13 15:54:18,458 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.11 03:54:18" (3/3) ... [2024-11-13 15:54:18,459 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra-u.c [2024-11-13 15:54:18,475 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-13 15:54:18,477 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_dijkstra-u.c that has 4 procedures, 47 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2024-11-13 15:54:18,550 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-13 15:54:18,566 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=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;@4559f801, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-13 15:54:18,566 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-13 15:54:18,570 INFO L276 IsEmpty]: Start isEmpty. Operand has 47 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 32 states have internal predecessors, (37), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-13 15:54:18,577 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-13 15:54:18,577 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:54:18,578 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:54:18,578 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:54:18,583 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:54:18,584 INFO L85 PathProgramCache]: Analyzing trace with hash 2024161958, now seen corresponding path program 1 times [2024-11-13 15:54:18,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:54:18,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [436330428] [2024-11-13 15:54:18,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:54:18,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:54:18,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:18,864 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 15:54:18,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:18,886 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-13 15:54:18,888 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:54:18,888 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [436330428] [2024-11-13 15:54:18,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [436330428] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-13 15:54:18,889 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-13 15:54:18,890 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-13 15:54:18,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1749897039] [2024-11-13 15:54:18,894 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-13 15:54:18,897 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-13 15:54:18,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:54:18,919 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-13 15:54:18,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-13 15:54:18,922 INFO L87 Difference]: Start difference. First operand has 47 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 32 states have internal predecessors, (37), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-13 15:54:19,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:54:19,242 INFO L93 Difference]: Finished difference Result 95 states and 141 transitions. [2024-11-13 15:54:19,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-13 15:54:19,244 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2024-11-13 15:54:19,245 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:54:19,252 INFO L225 Difference]: With dead ends: 95 [2024-11-13 15:54:19,252 INFO L226 Difference]: Without dead ends: 47 [2024-11-13 15:54:19,256 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-13 15:54:19,261 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 19 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-13 15:54:19,262 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 50 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-13 15:54:19,275 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-13 15:54:19,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2024-11-13 15:54:19,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 29 states have internal predecessors, (30), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-13 15:54:19,314 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2024-11-13 15:54:19,317 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 16 [2024-11-13 15:54:19,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:54:19,319 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2024-11-13 15:54:19,319 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-13 15:54:19,319 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2024-11-13 15:54:19,320 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-13 15:54:19,320 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:54:19,320 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:54:19,321 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-13 15:54:19,321 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:54:19,322 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:54:19,323 INFO L85 PathProgramCache]: Analyzing trace with hash 715108188, now seen corresponding path program 1 times [2024-11-13 15:54:19,323 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:54:19,323 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [681781694] [2024-11-13 15:54:19,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:54:19,323 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:54:19,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:21,000 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 15:54:21,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:21,364 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-13 15:54:21,365 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:54:21,365 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [681781694] [2024-11-13 15:54:21,365 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [681781694] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-13 15:54:21,365 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-13 15:54:21,365 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2024-11-13 15:54:21,365 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [491265211] [2024-11-13 15:54:21,365 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-13 15:54:21,366 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-13 15:54:21,367 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:54:21,368 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-13 15:54:21,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2024-11-13 15:54:21,369 INFO L87 Difference]: Start difference. First operand 43 states and 55 transitions. Second operand has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-13 15:54:22,800 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:54:22,800 INFO L93 Difference]: Finished difference Result 76 states and 99 transitions. [2024-11-13 15:54:22,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-13 15:54:22,801 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 17 [2024-11-13 15:54:22,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:54:22,803 INFO L225 Difference]: With dead ends: 76 [2024-11-13 15:54:22,805 INFO L226 Difference]: Without dead ends: 74 [2024-11-13 15:54:22,806 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-13 15:54:22,807 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 55 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 466 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 508 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 466 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-13 15:54:22,809 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 153 Invalid, 508 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 466 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-13 15:54:22,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-13 15:54:22,844 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 69. [2024-11-13 15:54:22,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 41 states have (on average 1.1219512195121952) internal successors, (46), 44 states have internal predecessors, (46), 20 states have call successors, (20), 5 states have call predecessors, (20), 7 states have return successors, (24), 19 states have call predecessors, (24), 19 states have call successors, (24) [2024-11-13 15:54:22,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 90 transitions. [2024-11-13 15:54:22,851 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 90 transitions. Word has length 17 [2024-11-13 15:54:22,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:54:22,851 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 90 transitions. [2024-11-13 15:54:22,852 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-13 15:54:22,852 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 90 transitions. [2024-11-13 15:54:22,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-13 15:54:22,852 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:54:22,852 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:54:22,853 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-13 15:54:22,853 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:54:22,853 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:54:22,853 INFO L85 PathProgramCache]: Analyzing trace with hash 1913135784, now seen corresponding path program 1 times [2024-11-13 15:54:22,853 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:54:22,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1783505227] [2024-11-13 15:54:22,854 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:54:22,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:54:22,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 15:54:22,915 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [124339183] [2024-11-13 15:54:22,915 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:54:22,915 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:54:22,915 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:54:22,918 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:54:22,920 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-13 15:54:23,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:23,230 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 69 conjuncts are in the unsatisfiable core [2024-11-13 15:54:23,261 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:54:23,300 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 [2024-11-13 15:54:23,310 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 [2024-11-13 15:54:23,316 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 [2024-11-13 15:54:23,323 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 [2024-11-13 15:54:23,697 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 [2024-11-13 15:54:23,702 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 [2024-11-13 15:54:23,780 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-13 15:54:23,781 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:54:24,052 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:54:24,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1783505227] [2024-11-13 15:54:24,053 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 15:54:24,053 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [124339183] [2024-11-13 15:54:24,053 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [124339183] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:54:24,053 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 15:54:24,053 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-13 15:54:24,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [26732841] [2024-11-13 15:54:24,053 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 15:54:24,054 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-13 15:54:24,054 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:54:24,054 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-13 15:54:24,054 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2024-11-13 15:54:24,055 INFO L87 Difference]: Start difference. First operand 69 states and 90 transitions. Second operand has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-13 15:54:25,060 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:54:25,060 INFO L93 Difference]: Finished difference Result 92 states and 113 transitions. [2024-11-13 15:54:25,060 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-13 15:54:25,061 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2024-11-13 15:54:25,061 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:54:25,062 INFO L225 Difference]: With dead ends: 92 [2024-11-13 15:54:25,062 INFO L226 Difference]: Without dead ends: 90 [2024-11-13 15:54:25,063 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 14 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2024-11-13 15:54:25,063 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 46 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 311 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 348 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 311 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-13 15:54:25,064 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 213 Invalid, 348 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 311 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-13 15:54:25,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2024-11-13 15:54:25,087 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 88. [2024-11-13 15:54:25,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 54 states have (on average 1.1296296296296295) internal successors, (61), 57 states have internal predecessors, (61), 23 states have call successors, (23), 8 states have call predecessors, (23), 10 states have return successors, (26), 22 states have call predecessors, (26), 21 states have call successors, (26) [2024-11-13 15:54:25,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 110 transitions. [2024-11-13 15:54:25,090 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 110 transitions. Word has length 23 [2024-11-13 15:54:25,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:54:25,090 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 110 transitions. [2024-11-13 15:54:25,090 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-13 15:54:25,090 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 110 transitions. [2024-11-13 15:54:25,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-13 15:54:25,094 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:54:25,094 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:54:25,101 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-13 15:54:25,297 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:54:25,298 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:54:25,298 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:54:25,298 INFO L85 PathProgramCache]: Analyzing trace with hash -1510470269, now seen corresponding path program 1 times [2024-11-13 15:54:25,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:54:25,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1197333338] [2024-11-13 15:54:25,299 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:54:25,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:54:25,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:26,544 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 15:54:26,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:27,120 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:54:27,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:27,401 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-13 15:54:27,401 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:54:27,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1197333338] [2024-11-13 15:54:27,401 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1197333338] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:54:27,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [879927444] [2024-11-13 15:54:27,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:54:27,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:54:27,401 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:54:27,403 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:54:27,405 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-13 15:54:27,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:27,693 INFO L255 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 96 conjuncts are in the unsatisfiable core [2024-11-13 15:54:27,697 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:54:27,702 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 [2024-11-13 15:54:27,708 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 [2024-11-13 15:54:27,714 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 [2024-11-13 15:54:27,720 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 [2024-11-13 15:54:28,399 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 [2024-11-13 15:54:28,419 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:54:28,419 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 32 [2024-11-13 15:54:28,687 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 [2024-11-13 15:54:28,852 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-13 15:54:28,853 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:54:30,380 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [879927444] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:54:30,380 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-13 15:54:30,380 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 28 [2024-11-13 15:54:30,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [790414521] [2024-11-13 15:54:30,380 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-13 15:54:30,381 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-13 15:54:30,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:54:30,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-13 15:54:30,382 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=1092, Unknown=0, NotChecked=0, Total=1190 [2024-11-13 15:54:30,382 INFO L87 Difference]: Start difference. First operand 88 states and 110 transitions. Second operand has 28 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 20 states have internal predecessors, (27), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-13 15:54:39,979 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] [2024-11-13 15:54:42,508 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:54:42,508 INFO L93 Difference]: Finished difference Result 126 states and 160 transitions. [2024-11-13 15:54:42,509 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-13 15:54:42,509 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 20 states have internal predecessors, (27), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 23 [2024-11-13 15:54:42,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:54:42,511 INFO L225 Difference]: With dead ends: 126 [2024-11-13 15:54:42,511 INFO L226 Difference]: Without dead ends: 124 [2024-11-13 15:54:42,513 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 17 SyntacticMatches, 2 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 355 ImplicationChecksByTransitivity, 7.4s TimeCoverageRelationStatistics Valid=227, Invalid=2222, Unknown=1, NotChecked=0, Total=2450 [2024-11-13 15:54:42,514 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 100 mSDsluCounter, 366 mSDsCounter, 0 mSdLazyCounter, 1673 mSolverCounterSat, 69 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 112 SdHoareTripleChecker+Valid, 410 SdHoareTripleChecker+Invalid, 1743 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 1673 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.7s IncrementalHoareTripleChecker+Time [2024-11-13 15:54:42,514 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [112 Valid, 410 Invalid, 1743 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 1673 Invalid, 1 Unknown, 0 Unchecked, 6.7s Time] [2024-11-13 15:54:42,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2024-11-13 15:54:42,562 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 116. [2024-11-13 15:54:42,563 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 71 states have (on average 1.1267605633802817) internal successors, (80), 74 states have internal predecessors, (80), 30 states have call successors, (30), 11 states have call predecessors, (30), 14 states have return successors, (36), 30 states have call predecessors, (36), 28 states have call successors, (36) [2024-11-13 15:54:42,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 146 transitions. [2024-11-13 15:54:42,570 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 146 transitions. Word has length 23 [2024-11-13 15:54:42,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:54:42,570 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 146 transitions. [2024-11-13 15:54:42,570 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 20 states have internal predecessors, (27), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-13 15:54:42,570 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 146 transitions. [2024-11-13 15:54:42,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-13 15:54:42,571 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:54:42,571 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:54:42,593 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-13 15:54:42,771 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-13 15:54:42,772 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:54:42,773 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:54:42,773 INFO L85 PathProgramCache]: Analyzing trace with hash 1851427818, now seen corresponding path program 2 times [2024-11-13 15:54:42,774 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:54:42,774 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1333134111] [2024-11-13 15:54:42,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:54:42,777 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:54:42,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:43,932 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 15:54:43,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:44,796 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:54:44,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:45,506 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:54:45,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:54:45,878 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-13 15:54:45,878 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:54:45,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1333134111] [2024-11-13 15:54:45,878 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1333134111] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:54:45,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1487157337] [2024-11-13 15:54:45,878 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-13 15:54:45,879 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:54:45,879 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:54:45,883 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:54:45,884 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-13 15:54:46,016 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-13 15:54:46,016 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 15:54:46,019 WARN L253 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 123 conjuncts are in the unsatisfiable core [2024-11-13 15:54:46,023 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:54:46,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 1 [2024-11-13 15:54:46,097 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 [2024-11-13 15:54:46,104 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 [2024-11-13 15:54:46,112 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 [2024-11-13 15:54:47,108 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 [2024-11-13 15:54:47,135 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:54:47,135 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 32 [2024-11-13 15:54:47,497 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 [2024-11-13 15:54:47,668 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-13 15:54:47,668 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:54:49,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1487157337] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:54:49,598 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-13 15:54:49,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17] total 34 [2024-11-13 15:54:49,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [75747858] [2024-11-13 15:54:49,598 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-13 15:54:49,598 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-13 15:54:49,602 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:54:49,604 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-13 15:54:49,605 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=1530, Unknown=0, NotChecked=0, Total=1640 [2024-11-13 15:54:49,605 INFO L87 Difference]: Start difference. First operand 116 states and 146 transitions. Second operand has 34 states, 25 states have (on average 1.36) internal successors, (34), 26 states have internal predecessors, (34), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-13 15:54:57,927 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] [2024-11-13 15:55:12,710 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] [2024-11-13 15:55:13,177 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:55:13,177 INFO L93 Difference]: Finished difference Result 165 states and 210 transitions. [2024-11-13 15:55:13,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2024-11-13 15:55:13,178 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 25 states have (on average 1.36) internal successors, (34), 26 states have internal predecessors, (34), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 29 [2024-11-13 15:55:13,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:55:13,180 INFO L225 Difference]: With dead ends: 165 [2024-11-13 15:55:13,180 INFO L226 Difference]: Without dead ends: 163 [2024-11-13 15:55:13,182 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 747 ImplicationChecksByTransitivity, 14.4s TimeCoverageRelationStatistics Valid=429, Invalid=4399, Unknown=2, NotChecked=0, Total=4830 [2024-11-13 15:55:13,183 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 133 mSDsluCounter, 496 mSDsCounter, 0 mSdLazyCounter, 2505 mSolverCounterSat, 94 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 149 SdHoareTripleChecker+Valid, 540 SdHoareTripleChecker+Invalid, 2601 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 2505 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.9s IncrementalHoareTripleChecker+Time [2024-11-13 15:55:13,183 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [149 Valid, 540 Invalid, 2601 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 2505 Invalid, 2 Unknown, 0 Unchecked, 11.9s Time] [2024-11-13 15:55:13,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2024-11-13 15:55:13,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 126. [2024-11-13 15:55:13,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 77 states have (on average 1.12987012987013) internal successors, (87), 81 states have internal predecessors, (87), 31 states have call successors, (31), 12 states have call predecessors, (31), 17 states have return successors, (39), 32 states have call predecessors, (39), 29 states have call successors, (39) [2024-11-13 15:55:13,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 157 transitions. [2024-11-13 15:55:13,236 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 157 transitions. Word has length 29 [2024-11-13 15:55:13,237 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:55:13,237 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 157 transitions. [2024-11-13 15:55:13,238 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 25 states have (on average 1.36) internal successors, (34), 26 states have internal predecessors, (34), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-13 15:55:13,238 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 157 transitions. [2024-11-13 15:55:13,239 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-13 15:55:13,239 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:55:13,239 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:55:13,260 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-13 15:55:13,440 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:55:13,440 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:55:13,440 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:55:13,440 INFO L85 PathProgramCache]: Analyzing trace with hash -1343310350, now seen corresponding path program 1 times [2024-11-13 15:55:13,441 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:55:13,441 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2107136906] [2024-11-13 15:55:13,441 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:55:13,441 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:55:13,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 15:55:13,469 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1540933381] [2024-11-13 15:55:13,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:55:13,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:55:13,469 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:55:13,471 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:55:13,473 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-13 15:55:13,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:55:13,645 INFO L255 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 71 conjuncts are in the unsatisfiable core [2024-11-13 15:55:13,648 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:55:13,653 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 [2024-11-13 15:55:13,658 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 [2024-11-13 15:55:13,665 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 [2024-11-13 15:55:14,139 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-13 15:55:14,139 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:55:15,058 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:55:15,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2107136906] [2024-11-13 15:55:15,058 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 15:55:15,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1540933381] [2024-11-13 15:55:15,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1540933381] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:55:15,059 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 15:55:15,059 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-13 15:55:15,059 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1314301572] [2024-11-13 15:55:15,059 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 15:55:15,059 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-13 15:55:15,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:55:15,060 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-13 15:55:15,061 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2024-11-13 15:55:15,061 INFO L87 Difference]: Start difference. First operand 126 states and 157 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-13 15:55:15,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:55:15,888 INFO L93 Difference]: Finished difference Result 134 states and 163 transitions. [2024-11-13 15:55:15,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-13 15:55:15,889 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2024-11-13 15:55:15,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:55:15,891 INFO L225 Difference]: With dead ends: 134 [2024-11-13 15:55:15,891 INFO L226 Difference]: Without dead ends: 132 [2024-11-13 15:55:15,891 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 18 SyntacticMatches, 6 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2024-11-13 15:55:15,892 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 52 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 282 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 282 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-13 15:55:15,892 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 183 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 282 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-13 15:55:15,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-13 15:55:15,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 130. [2024-11-13 15:55:15,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 80 states have (on average 1.125) internal successors, (90), 84 states have internal predecessors, (90), 31 states have call successors, (31), 13 states have call predecessors, (31), 18 states have return successors, (39), 32 states have call predecessors, (39), 29 states have call successors, (39) [2024-11-13 15:55:15,936 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 160 transitions. [2024-11-13 15:55:15,936 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 160 transitions. Word has length 29 [2024-11-13 15:55:15,936 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:55:15,936 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 160 transitions. [2024-11-13 15:55:15,937 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-13 15:55:15,937 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 160 transitions. [2024-11-13 15:55:15,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-13 15:55:15,938 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:55:15,938 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-13 15:55:15,959 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-13 15:55:16,141 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-13 15:55:16,142 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:55:16,142 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:55:16,142 INFO L85 PathProgramCache]: Analyzing trace with hash -1540028529, now seen corresponding path program 1 times [2024-11-13 15:55:16,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:55:16,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [521150464] [2024-11-13 15:55:16,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:55:16,142 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:55:16,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 15:55:16,166 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [602115856] [2024-11-13 15:55:16,166 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:55:16,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:55:16,166 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:55:16,168 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:55:16,170 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-13 15:55:16,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:55:16,774 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 87 conjuncts are in the unsatisfiable core [2024-11-13 15:55:16,779 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:55:16,785 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 [2024-11-13 15:55:16,790 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 [2024-11-13 15:55:16,796 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 [2024-11-13 15:55:16,803 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 [2024-11-13 15:55:17,097 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 [2024-11-13 15:55:17,459 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:55:17,460 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 30 treesize of output 30 [2024-11-13 15:55:17,473 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:55:17,473 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 31 treesize of output 31 [2024-11-13 15:55:17,578 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-13 15:55:17,578 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:55:17,904 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:55:17,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [521150464] [2024-11-13 15:55:17,905 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 15:55:17,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [602115856] [2024-11-13 15:55:17,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [602115856] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:55:17,905 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 15:55:17,905 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2024-11-13 15:55:17,905 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [366623223] [2024-11-13 15:55:17,905 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 15:55:17,906 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-13 15:55:17,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:55:17,907 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-13 15:55:17,907 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=204, Unknown=0, NotChecked=0, Total=240 [2024-11-13 15:55:17,907 INFO L87 Difference]: Start difference. First operand 130 states and 160 transitions. Second operand has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-13 15:55:19,501 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:55:19,502 INFO L93 Difference]: Finished difference Result 174 states and 210 transitions. [2024-11-13 15:55:19,502 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-13 15:55:19,502 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 29 [2024-11-13 15:55:19,503 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:55:19,504 INFO L225 Difference]: With dead ends: 174 [2024-11-13 15:55:19,504 INFO L226 Difference]: Without dead ends: 172 [2024-11-13 15:55:19,505 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 17 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2024-11-13 15:55:19,506 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 47 mSDsluCounter, 218 mSDsCounter, 0 mSdLazyCounter, 711 mSolverCounterSat, 36 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 757 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 711 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-13 15:55:19,507 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 264 Invalid, 757 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 711 Invalid, 10 Unknown, 0 Unchecked, 1.2s Time] [2024-11-13 15:55:19,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2024-11-13 15:55:19,587 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 168. [2024-11-13 15:55:19,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 168 states, 103 states have (on average 1.116504854368932) internal successors, (115), 107 states have internal predecessors, (115), 41 states have call successors, (41), 17 states have call predecessors, (41), 23 states have return successors, (50), 43 states have call predecessors, (50), 38 states have call successors, (50) [2024-11-13 15:55:19,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 168 states to 168 states and 206 transitions. [2024-11-13 15:55:19,590 INFO L78 Accepts]: Start accepts. Automaton has 168 states and 206 transitions. Word has length 29 [2024-11-13 15:55:19,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:55:19,590 INFO L471 AbstractCegarLoop]: Abstraction has 168 states and 206 transitions. [2024-11-13 15:55:19,590 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-13 15:55:19,590 INFO L276 IsEmpty]: Start isEmpty. Operand 168 states and 206 transitions. [2024-11-13 15:55:19,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-13 15:55:19,591 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:55:19,591 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:55:19,599 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-13 15:55:19,795 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:55:19,796 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:55:19,796 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:55:19,796 INFO L85 PathProgramCache]: Analyzing trace with hash 1581095569, now seen corresponding path program 3 times [2024-11-13 15:55:19,796 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:55:19,796 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1492807164] [2024-11-13 15:55:19,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:55:19,796 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:55:19,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:55:20,925 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 15:55:20,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:55:21,508 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:55:21,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:55:22,057 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:55:22,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:55:22,543 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:55:22,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:55:22,851 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-13 15:55:22,852 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:55:22,852 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1492807164] [2024-11-13 15:55:22,852 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1492807164] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:55:22,852 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [854554272] [2024-11-13 15:55:22,852 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-13 15:55:22,852 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:55:22,852 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:55:22,854 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:55:22,857 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-13 15:55:23,159 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-13 15:55:23,159 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 15:55:23,162 WARN L253 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 147 conjuncts are in the unsatisfiable core [2024-11-13 15:55:23,166 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:55:23,176 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 [2024-11-13 15:55:23,245 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 [2024-11-13 15:55:23,253 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 [2024-11-13 15:55:23,259 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-13 15:55:24,584 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:55:24,584 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 36 [2024-11-13 15:55:24,603 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 [2024-11-13 15:55:25,019 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 [2024-11-13 15:55:25,233 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-13 15:55:25,234 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:55:27,243 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [854554272] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:55:27,243 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-13 15:55:27,243 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 18] total 38 [2024-11-13 15:55:27,243 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [452121648] [2024-11-13 15:55:27,244 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-13 15:55:27,244 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2024-11-13 15:55:27,244 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:55:27,244 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2024-11-13 15:55:27,245 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=121, Invalid=1859, Unknown=0, NotChecked=0, Total=1980 [2024-11-13 15:55:27,245 INFO L87 Difference]: Start difference. First operand 168 states and 206 transitions. Second operand has 38 states, 28 states have (on average 1.3571428571428572) internal successors, (38), 30 states have internal predecessors, (38), 10 states have call successors, (10), 6 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-13 15:55:45,995 WARN L286 SmtUtils]: Spent 16.14s on a formula simplification. DAG size of input: 109 DAG size of output: 73 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 15:55:50,963 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] [2024-11-13 15:55:55,122 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] [2024-11-13 15:56:07,279 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] [2024-11-13 15:56:31,651 WARN L286 SmtUtils]: Spent 8.17s on a formula simplification. DAG size of input: 109 DAG size of output: 79 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 15:56:35,695 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] [2024-11-13 15:56:43,853 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] [2024-11-13 15:56:47,905 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] [2024-11-13 15:56:51,981 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] [2024-11-13 15:56:56,535 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] [2024-11-13 15:57:00,610 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] [2024-11-13 15:57:04,716 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] [2024-11-13 15:57:08,776 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] [2024-11-13 15:57:13,080 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] [2024-11-13 15:57:17,141 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] [2024-11-13 15:57:21,433 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] [2024-11-13 15:57:25,440 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] [2024-11-13 15:57:46,056 WARN L286 SmtUtils]: Spent 16.18s on a formula simplification. DAG size of input: 112 DAG size of output: 75 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 15:57:56,884 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] [2024-11-13 15:58:00,891 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] [2024-11-13 15:58:05,969 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] [2024-11-13 15:58:10,086 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-13 15:58:10,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:58:10,538 INFO L93 Difference]: Finished difference Result 215 states and 268 transitions. [2024-11-13 15:58:10,539 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-11-13 15:58:10,539 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 28 states have (on average 1.3571428571428572) internal successors, (38), 30 states have internal predecessors, (38), 10 states have call successors, (10), 6 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 6 states have call successors, (8) Word has length 35 [2024-11-13 15:58:10,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:58:10,541 INFO L225 Difference]: With dead ends: 215 [2024-11-13 15:58:10,541 INFO L226 Difference]: Without dead ends: 213 [2024-11-13 15:58:10,543 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1364 ImplicationChecksByTransitivity, 84.3s TimeCoverageRelationStatistics Valid=528, Invalid=6603, Unknown=9, NotChecked=0, Total=7140 [2024-11-13 15:58:10,544 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 170 mSDsluCounter, 538 mSDsCounter, 0 mSdLazyCounter, 2647 mSolverCounterSat, 136 mSolverCounterUnsat, 19 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 81.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 180 SdHoareTripleChecker+Valid, 583 SdHoareTripleChecker+Invalid, 2802 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 136 IncrementalHoareTripleChecker+Valid, 2647 IncrementalHoareTripleChecker+Invalid, 19 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 82.0s IncrementalHoareTripleChecker+Time [2024-11-13 15:58:10,544 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [180 Valid, 583 Invalid, 2802 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [136 Valid, 2647 Invalid, 19 Unknown, 0 Unchecked, 82.0s Time] [2024-11-13 15:58:10,545 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2024-11-13 15:58:10,598 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 173. [2024-11-13 15:58:10,599 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 105 states have (on average 1.1142857142857143) internal successors, (117), 110 states have internal predecessors, (117), 42 states have call successors, (42), 17 states have call predecessors, (42), 25 states have return successors, (55), 45 states have call predecessors, (55), 39 states have call successors, (55) [2024-11-13 15:58:10,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 214 transitions. [2024-11-13 15:58:10,601 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 214 transitions. Word has length 35 [2024-11-13 15:58:10,601 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:58:10,601 INFO L471 AbstractCegarLoop]: Abstraction has 173 states and 214 transitions. [2024-11-13 15:58:10,601 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 28 states have (on average 1.3571428571428572) internal successors, (38), 30 states have internal predecessors, (38), 10 states have call successors, (10), 6 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-13 15:58:10,601 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 214 transitions. [2024-11-13 15:58:10,603 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-13 15:58:10,603 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:58:10,603 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:58:10,617 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-13 15:58:10,803 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:58:10,803 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:58:10,804 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:58:10,804 INFO L85 PathProgramCache]: Analyzing trace with hash -345050438, now seen corresponding path program 1 times [2024-11-13 15:58:10,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:58:10,804 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1291943817] [2024-11-13 15:58:10,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:58:10,804 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:58:10,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 15:58:10,834 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [111508956] [2024-11-13 15:58:10,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:58:10,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:58:10,835 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:58:10,837 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:58:10,838 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-13 15:58:11,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:11,096 INFO L255 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 101 conjuncts are in the unsatisfiable core [2024-11-13 15:58:11,100 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:58:11,105 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 [2024-11-13 15:58:11,110 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 [2024-11-13 15:58:11,117 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 [2024-11-13 15:58:11,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 11 treesize of output 7 [2024-11-13 15:58:11,619 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 22 [2024-11-13 15:58:11,651 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 20 [2024-11-13 15:58:11,659 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 16 [2024-11-13 15:58:11,817 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-13 15:58:11,817 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:58:28,357 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:58:28,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1291943817] [2024-11-13 15:58:28,357 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 15:58:28,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [111508956] [2024-11-13 15:58:28,357 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [111508956] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:58:28,357 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 15:58:28,358 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-13 15:58:28,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [158102169] [2024-11-13 15:58:28,358 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 15:58:28,358 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-13 15:58:28,358 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:58:28,359 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-13 15:58:28,359 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=82, Unknown=4, NotChecked=0, Total=110 [2024-11-13 15:58:28,359 INFO L87 Difference]: Start difference. First operand 173 states and 214 transitions. Second operand has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-13 15:58:29,239 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:58:29,239 INFO L93 Difference]: Finished difference Result 216 states and 263 transitions. [2024-11-13 15:58:29,240 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-13 15:58:29,240 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 35 [2024-11-13 15:58:29,242 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:58:29,243 INFO L225 Difference]: With dead ends: 216 [2024-11-13 15:58:29,244 INFO L226 Difference]: Without dead ends: 214 [2024-11-13 15:58:29,244 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 22 SyntacticMatches, 9 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 16.9s TimeCoverageRelationStatistics Valid=49, Invalid=157, Unknown=4, NotChecked=0, Total=210 [2024-11-13 15:58:29,244 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 40 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 213 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-13 15:58:29,245 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 187 Invalid, 213 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 195 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-13 15:58:29,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2024-11-13 15:58:29,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 212. [2024-11-13 15:58:29,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 212 states, 130 states have (on average 1.1076923076923078) internal successors, (144), 135 states have internal predecessors, (144), 51 states have call successors, (51), 22 states have call predecessors, (51), 30 states have return successors, (63), 54 states have call predecessors, (63), 47 states have call successors, (63) [2024-11-13 15:58:29,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 258 transitions. [2024-11-13 15:58:29,321 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 258 transitions. Word has length 35 [2024-11-13 15:58:29,321 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:58:29,321 INFO L471 AbstractCegarLoop]: Abstraction has 212 states and 258 transitions. [2024-11-13 15:58:29,321 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-13 15:58:29,321 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 258 transitions. [2024-11-13 15:58:29,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-13 15:58:29,323 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:58:29,323 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:58:29,341 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-13 15:58:29,523 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:58:29,525 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:58:29,525 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:58:29,525 INFO L85 PathProgramCache]: Analyzing trace with hash 1503662489, now seen corresponding path program 1 times [2024-11-13 15:58:29,525 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:58:29,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [928647267] [2024-11-13 15:58:29,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:58:29,525 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:58:29,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 15:58:29,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [954072900] [2024-11-13 15:58:29,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:58:29,575 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:58:29,575 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:58:29,578 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:58:29,580 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-13 15:58:29,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:29,782 INFO L255 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 115 conjuncts are in the unsatisfiable core [2024-11-13 15:58:29,788 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:58:29,793 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 [2024-11-13 15:58:29,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 11 treesize of output 7 [2024-11-13 15:58:29,810 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 [2024-11-13 15:58:29,820 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 [2024-11-13 15:58:29,832 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 [2024-11-13 15:58:30,267 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 [2024-11-13 15:58:30,848 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:58:30,848 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 23 treesize of output 27 [2024-11-13 15:58:43,186 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 [2024-11-13 15:58:43,394 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 8 refuted. 4 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-13 15:58:43,394 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:58:45,309 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:58:45,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [928647267] [2024-11-13 15:58:45,310 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 15:58:45,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [954072900] [2024-11-13 15:58:45,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [954072900] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:58:45,310 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 15:58:45,310 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-13 15:58:45,310 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [403823969] [2024-11-13 15:58:45,310 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 15:58:45,310 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-13 15:58:45,310 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:58:45,311 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-13 15:58:45,311 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=257, Unknown=2, NotChecked=0, Total=306 [2024-11-13 15:58:45,311 INFO L87 Difference]: Start difference. First operand 212 states and 258 transitions. Second operand has 16 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 13 states have internal predecessors, (25), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-13 15:58:48,126 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:58:48,126 INFO L93 Difference]: Finished difference Result 224 states and 267 transitions. [2024-11-13 15:58:48,127 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-13 15:58:48,127 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 13 states have internal predecessors, (25), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 35 [2024-11-13 15:58:48,127 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:58:48,129 INFO L225 Difference]: With dead ends: 224 [2024-11-13 15:58:48,129 INFO L226 Difference]: Without dead ends: 222 [2024-11-13 15:58:48,130 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 20 SyntacticMatches, 4 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 15.1s TimeCoverageRelationStatistics Valid=100, Invalid=450, Unknown=2, NotChecked=0, Total=552 [2024-11-13 15:58:48,130 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 47 mSDsluCounter, 266 mSDsCounter, 0 mSdLazyCounter, 874 mSolverCounterSat, 36 mSolverCounterUnsat, 20 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 312 SdHoareTripleChecker+Invalid, 930 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 874 IncrementalHoareTripleChecker+Invalid, 20 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-11-13 15:58:48,130 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 312 Invalid, 930 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 874 Invalid, 20 Unknown, 0 Unchecked, 2.2s Time] [2024-11-13 15:58:48,131 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2024-11-13 15:58:48,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 216. [2024-11-13 15:58:48,185 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 133 states have (on average 1.105263157894737) internal successors, (147), 138 states have internal predecessors, (147), 51 states have call successors, (51), 23 states have call predecessors, (51), 31 states have return successors, (63), 54 states have call predecessors, (63), 47 states have call successors, (63) [2024-11-13 15:58:48,186 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 261 transitions. [2024-11-13 15:58:48,186 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 261 transitions. Word has length 35 [2024-11-13 15:58:48,186 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:58:48,186 INFO L471 AbstractCegarLoop]: Abstraction has 216 states and 261 transitions. [2024-11-13 15:58:48,186 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 13 states have internal predecessors, (25), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-13 15:58:48,187 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 261 transitions. [2024-11-13 15:58:48,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-13 15:58:48,187 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:58:48,188 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:58:48,202 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-13 15:58:48,388 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-13 15:58:48,388 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:58:48,389 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:58:48,389 INFO L85 PathProgramCache]: Analyzing trace with hash -1260200778, now seen corresponding path program 2 times [2024-11-13 15:58:48,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:58:48,389 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1398000186] [2024-11-13 15:58:48,389 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:58:48,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:58:48,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 15:58:48,412 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [859356534] [2024-11-13 15:58:48,412 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-13 15:58:48,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:58:48,413 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:58:48,415 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:58:48,416 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-13 15:58:48,692 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-13 15:58:48,692 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 15:58:48,696 INFO L255 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 103 conjuncts are in the unsatisfiable core [2024-11-13 15:58:48,699 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:58:48,720 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 [2024-11-13 15:58:48,752 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 [2024-11-13 15:58:48,763 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 [2024-11-13 15:58:48,781 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 [2024-11-13 15:58:49,216 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 [2024-11-13 15:58:49,751 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:58:49,751 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 30 treesize of output 26 [2024-11-13 15:58:49,763 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:58:49,764 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 27 treesize of output 23 [2024-11-13 15:58:49,916 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-13 15:58:49,916 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:58:50,382 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:58:50,383 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1398000186] [2024-11-13 15:58:50,383 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 15:58:50,383 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [859356534] [2024-11-13 15:58:50,383 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [859356534] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:58:50,383 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 15:58:50,383 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-13 15:58:50,383 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1954659582] [2024-11-13 15:58:50,383 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 15:58:50,384 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-13 15:58:50,384 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:58:50,384 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-13 15:58:50,384 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=264, Unknown=0, NotChecked=0, Total=306 [2024-11-13 15:58:50,384 INFO L87 Difference]: Start difference. First operand 216 states and 261 transitions. Second operand has 16 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 13 states have internal predecessors, (22), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-13 15:58:53,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 15:58:53,122 INFO L93 Difference]: Finished difference Result 266 states and 316 transitions. [2024-11-13 15:58:53,123 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-13 15:58:53,123 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 13 states have internal predecessors, (22), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 35 [2024-11-13 15:58:53,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 15:58:53,125 INFO L225 Difference]: With dead ends: 266 [2024-11-13 15:58:53,125 INFO L226 Difference]: Without dead ends: 264 [2024-11-13 15:58:53,126 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 21 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=87, Invalid=465, Unknown=0, NotChecked=0, Total=552 [2024-11-13 15:58:53,126 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 47 mSDsluCounter, 259 mSDsCounter, 0 mSdLazyCounter, 855 mSolverCounterSat, 36 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 898 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 855 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-11-13 15:58:53,127 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 300 Invalid, 898 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 855 Invalid, 7 Unknown, 0 Unchecked, 2.2s Time] [2024-11-13 15:58:53,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2024-11-13 15:58:53,203 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 260. [2024-11-13 15:58:53,204 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 160 states have (on average 1.1) internal successors, (176), 165 states have internal predecessors, (176), 61 states have call successors, (61), 28 states have call predecessors, (61), 38 states have return successors, (75), 66 states have call predecessors, (75), 56 states have call successors, (75) [2024-11-13 15:58:53,205 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 312 transitions. [2024-11-13 15:58:53,205 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 312 transitions. Word has length 35 [2024-11-13 15:58:53,205 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 15:58:53,206 INFO L471 AbstractCegarLoop]: Abstraction has 260 states and 312 transitions. [2024-11-13 15:58:53,206 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 13 states have internal predecessors, (22), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-13 15:58:53,206 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 312 transitions. [2024-11-13 15:58:53,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-13 15:58:53,207 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 15:58:53,207 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 15:58:53,215 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-13 15:58:53,407 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-13 15:58:53,408 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 15:58:53,408 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 15:58:53,408 INFO L85 PathProgramCache]: Analyzing trace with hash -1743017608, now seen corresponding path program 4 times [2024-11-13 15:58:53,408 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 15:58:53,408 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [699270240] [2024-11-13 15:58:53,408 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 15:58:53,408 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 15:58:53,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:54,867 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 15:58:54,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:55,722 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:58:55,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:56,564 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:58:56,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:57,214 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:58:57,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:57,915 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 15:58:57,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 15:58:58,353 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-11-13 15:58:58,354 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 15:58:58,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [699270240] [2024-11-13 15:58:58,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [699270240] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:58:58,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1464168872] [2024-11-13 15:58:58,354 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-13 15:58:58,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 15:58:58,354 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 15:58:58,356 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 15:58:58,359 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-13 15:58:58,517 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-13 15:58:58,517 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 15:58:58,520 WARN L253 TraceCheckSpWp]: Trace formula consists of 304 conjuncts, 164 conjuncts are in the unsatisfiable core [2024-11-13 15:58:58,524 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 15:58:58,537 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 [2024-11-13 15:58:58,626 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 [2024-11-13 15:58:58,640 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 [2024-11-13 15:58:58,647 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 [2024-11-13 15:59:00,878 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 [2024-11-13 15:59:00,909 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 15:59:00,909 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 28 [2024-11-13 15:59:01,481 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 [2024-11-13 15:59:01,917 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-13 15:59:01,917 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 15:59:06,072 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1464168872] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 15:59:06,072 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-13 15:59:06,072 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 19] total 42 [2024-11-13 15:59:06,072 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [593068003] [2024-11-13 15:59:06,072 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-13 15:59:06,073 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2024-11-13 15:59:06,073 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 15:59:06,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2024-11-13 15:59:06,074 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=2222, Unknown=0, NotChecked=0, Total=2352 [2024-11-13 15:59:06,074 INFO L87 Difference]: Start difference. First operand 260 states and 312 transitions. Second operand has 42 states, 31 states have (on average 1.3548387096774193) internal successors, (42), 34 states have internal predecessors, (42), 11 states have call successors, (11), 6 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-13 15:59:11,720 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] [2024-11-13 15:59:18,155 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] [2024-11-13 15:59:34,960 WARN L286 SmtUtils]: Spent 16.19s on a formula simplification. DAG size of input: 107 DAG size of output: 70 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 15:59:40,476 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] [2024-11-13 15:59:44,954 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] [2024-11-13 16:00:01,321 WARN L286 SmtUtils]: Spent 8.17s on a formula simplification. DAG size of input: 105 DAG size of output: 73 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 16:00:05,606 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] [2024-11-13 16:00:09,958 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] [2024-11-13 16:00:33,338 WARN L286 SmtUtils]: Spent 16.20s on a formula simplification. DAG size of input: 112 DAG size of output: 67 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 16:00:37,990 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] [2024-11-13 16:00:48,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 16:00:48,950 INFO L93 Difference]: Finished difference Result 304 states and 369 transitions. [2024-11-13 16:00:48,951 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2024-11-13 16:00:48,951 INFO L78 Accepts]: Start accepts. Automaton has has 42 states, 31 states have (on average 1.3548387096774193) internal successors, (42), 34 states have internal predecessors, (42), 11 states have call successors, (11), 6 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 7 states have call successors, (10) Word has length 41 [2024-11-13 16:00:48,952 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 16:00:48,954 INFO L225 Difference]: With dead ends: 304 [2024-11-13 16:00:48,954 INFO L226 Difference]: Without dead ends: 302 [2024-11-13 16:00:48,956 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 36 SyntacticMatches, 2 SemanticMatches, 91 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1644 ImplicationChecksByTransitivity, 71.6s TimeCoverageRelationStatistics Valid=590, Invalid=7962, Unknown=4, NotChecked=0, Total=8556 [2024-11-13 16:00:48,957 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 195 mSDsluCounter, 704 mSDsCounter, 0 mSdLazyCounter, 3382 mSolverCounterSat, 169 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 36.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 205 SdHoareTripleChecker+Valid, 750 SdHoareTripleChecker+Invalid, 3558 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 169 IncrementalHoareTripleChecker+Valid, 3382 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 37.3s IncrementalHoareTripleChecker+Time [2024-11-13 16:00:48,957 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [205 Valid, 750 Invalid, 3558 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [169 Valid, 3382 Invalid, 7 Unknown, 0 Unchecked, 37.3s Time] [2024-11-13 16:00:48,958 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 302 states. [2024-11-13 16:00:49,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 302 to 262. [2024-11-13 16:00:49,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 262 states, 161 states have (on average 1.0993788819875776) internal successors, (177), 166 states have internal predecessors, (177), 61 states have call successors, (61), 28 states have call predecessors, (61), 39 states have return successors, (77), 67 states have call predecessors, (77), 56 states have call successors, (77) [2024-11-13 16:00:49,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 262 states to 262 states and 315 transitions. [2024-11-13 16:00:49,037 INFO L78 Accepts]: Start accepts. Automaton has 262 states and 315 transitions. Word has length 41 [2024-11-13 16:00:49,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 16:00:49,038 INFO L471 AbstractCegarLoop]: Abstraction has 262 states and 315 transitions. [2024-11-13 16:00:49,038 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 31 states have (on average 1.3548387096774193) internal successors, (42), 34 states have internal predecessors, (42), 11 states have call successors, (11), 6 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-13 16:00:49,038 INFO L276 IsEmpty]: Start isEmpty. Operand 262 states and 315 transitions. [2024-11-13 16:00:49,039 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-13 16:00:49,039 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 16:00:49,039 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 16:00:49,060 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-13 16:00:49,240 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-13 16:00:49,240 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 16:00:49,240 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 16:00:49,240 INFO L85 PathProgramCache]: Analyzing trace with hash 762521759, now seen corresponding path program 5 times [2024-11-13 16:00:49,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 16:00:49,240 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1343717480] [2024-11-13 16:00:49,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 16:00:49,240 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 16:00:49,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:00:50,626 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 16:00:50,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:00:51,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:00:51,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:00:52,018 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:00:52,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:00:52,680 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:00:52,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:00:53,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:00:53,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:00:54,046 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:00:54,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:00:54,395 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-13 16:00:54,395 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 16:00:54,395 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1343717480] [2024-11-13 16:00:54,395 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1343717480] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 16:00:54,395 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [136559292] [2024-11-13 16:00:54,395 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-13 16:00:54,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 16:00:54,396 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 16:00:54,397 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 16:00:54,398 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-13 16:00:54,577 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-13 16:00:54,577 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 16:00:54,580 WARN L253 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 193 conjuncts are in the unsatisfiable core [2024-11-13 16:00:54,585 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 16:00:54,601 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 [2024-11-13 16:00:54,773 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 [2024-11-13 16:00:54,781 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 [2024-11-13 16:00:54,791 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 [2024-11-13 16:00:57,601 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 [2024-11-13 16:00:57,625 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 16:00:57,626 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 28 [2024-11-13 16:00:58,453 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 [2024-11-13 16:00:58,867 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-13 16:00:58,867 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 16:01:03,894 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [136559292] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 16:01:03,894 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-13 16:01:03,894 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 20] total 46 [2024-11-13 16:01:03,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [464028752] [2024-11-13 16:01:03,894 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-13 16:01:03,895 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2024-11-13 16:01:03,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 16:01:03,896 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2024-11-13 16:01:03,898 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=2622, Unknown=0, NotChecked=0, Total=2756 [2024-11-13 16:01:03,898 INFO L87 Difference]: Start difference. First operand 262 states and 315 transitions. Second operand has 46 states, 34 states have (on average 1.3529411764705883) internal successors, (46), 38 states have internal predecessors, (46), 12 states have call successors, (12), 6 states have call predecessors, (12), 12 states have return successors, (12), 12 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-13 16:01:12,439 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] [2024-11-13 16:01:36,966 WARN L286 SmtUtils]: Spent 16.27s on a formula simplification. DAG size of input: 128 DAG size of output: 80 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 16:01:41,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=false, quantifiers [0] [2024-11-13 16:01:45,754 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] [2024-11-13 16:02:19,425 WARN L286 SmtUtils]: Spent 24.35s on a formula simplification. DAG size of input: 129 DAG size of output: 83 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 16:02:24,124 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] [2024-11-13 16:02:30,211 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] [2024-11-13 16:03:02,909 WARN L286 SmtUtils]: Spent 16.37s on a formula simplification. DAG size of input: 122 DAG size of output: 85 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 16:03:06,914 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] [2024-11-13 16:03:11,051 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] [2024-11-13 16:03:15,558 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] [2024-11-13 16:03:19,563 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] [2024-11-13 16:03:23,932 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] [2024-11-13 16:03:29,151 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] [2024-11-13 16:03:37,168 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 16:03:37,169 INFO L93 Difference]: Finished difference Result 306 states and 372 transitions. [2024-11-13 16:03:37,169 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2024-11-13 16:03:37,169 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 34 states have (on average 1.3529411764705883) internal successors, (46), 38 states have internal predecessors, (46), 12 states have call successors, (12), 6 states have call predecessors, (12), 12 states have return successors, (12), 12 states have call predecessors, (12), 8 states have call successors, (12) Word has length 47 [2024-11-13 16:03:37,170 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 16:03:37,177 INFO L225 Difference]: With dead ends: 306 [2024-11-13 16:03:37,177 INFO L226 Difference]: Without dead ends: 304 [2024-11-13 16:03:37,184 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1192 ImplicationChecksByTransitivity, 105.7s TimeCoverageRelationStatistics Valid=578, Invalid=7604, Unknown=8, NotChecked=0, Total=8190 [2024-11-13 16:03:37,187 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 191 mSDsluCounter, 882 mSDsCounter, 0 mSdLazyCounter, 3764 mSolverCounterSat, 157 mSolverCounterUnsat, 11 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 53.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 207 SdHoareTripleChecker+Valid, 930 SdHoareTripleChecker+Invalid, 3932 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 157 IncrementalHoareTripleChecker+Valid, 3764 IncrementalHoareTripleChecker+Invalid, 11 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 54.4s IncrementalHoareTripleChecker+Time [2024-11-13 16:03:37,189 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [207 Valid, 930 Invalid, 3932 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [157 Valid, 3764 Invalid, 11 Unknown, 0 Unchecked, 54.4s Time] [2024-11-13 16:03:37,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 304 states. [2024-11-13 16:03:37,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 304 to 264. [2024-11-13 16:03:37,354 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 264 states, 162 states have (on average 1.0987654320987654) internal successors, (178), 167 states have internal predecessors, (178), 61 states have call successors, (61), 28 states have call predecessors, (61), 40 states have return successors, (80), 68 states have call predecessors, (80), 56 states have call successors, (80) [2024-11-13 16:03:37,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 264 states to 264 states and 319 transitions. [2024-11-13 16:03:37,358 INFO L78 Accepts]: Start accepts. Automaton has 264 states and 319 transitions. Word has length 47 [2024-11-13 16:03:37,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 16:03:37,358 INFO L471 AbstractCegarLoop]: Abstraction has 264 states and 319 transitions. [2024-11-13 16:03:37,359 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 34 states have (on average 1.3529411764705883) internal successors, (46), 38 states have internal predecessors, (46), 12 states have call successors, (12), 6 states have call predecessors, (12), 12 states have return successors, (12), 12 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-13 16:03:37,359 INFO L276 IsEmpty]: Start isEmpty. Operand 264 states and 319 transitions. [2024-11-13 16:03:37,362 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-13 16:03:37,362 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 16:03:37,362 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 16:03:37,381 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-13 16:03:37,563 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-13 16:03:37,563 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 16:03:37,564 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 16:03:37,564 INFO L85 PathProgramCache]: Analyzing trace with hash -734576000, now seen corresponding path program 1 times [2024-11-13 16:03:37,564 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 16:03:37,564 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1794582033] [2024-11-13 16:03:37,564 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 16:03:37,564 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 16:03:37,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 16:03:37,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [990987296] [2024-11-13 16:03:37,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 16:03:37,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 16:03:37,593 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 16:03:37,595 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 16:03:37,597 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-13 16:03:37,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:03:37,944 INFO L255 TraceCheckSpWp]: Trace formula consists of 368 conjuncts, 85 conjuncts are in the unsatisfiable core [2024-11-13 16:03:37,954 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 16:03:37,969 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-13 16:03:37,975 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 [2024-11-13 16:03:37,984 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 [2024-11-13 16:03:37,995 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 [2024-11-13 16:03:38,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 19 treesize of output 11 [2024-11-13 16:03:38,739 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 [2024-11-13 16:03:38,766 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 [2024-11-13 16:03:38,879 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-13 16:03:38,880 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 16:03:47,304 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 16:03:47,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1794582033] [2024-11-13 16:03:47,304 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 16:03:47,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [990987296] [2024-11-13 16:03:47,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [990987296] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 16:03:47,304 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 16:03:47,304 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-13 16:03:47,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [539628568] [2024-11-13 16:03:47,304 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 16:03:47,305 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-13 16:03:47,305 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 16:03:47,306 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-13 16:03:47,306 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=84, Unknown=2, NotChecked=0, Total=110 [2024-11-13 16:03:47,306 INFO L87 Difference]: Start difference. First operand 264 states and 319 transitions. Second operand has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-13 16:03:48,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 16:03:48,175 INFO L93 Difference]: Finished difference Result 284 states and 337 transitions. [2024-11-13 16:03:48,175 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-13 16:03:48,175 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 41 [2024-11-13 16:03:48,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 16:03:48,178 INFO L225 Difference]: With dead ends: 284 [2024-11-13 16:03:48,179 INFO L226 Difference]: Without dead ends: 282 [2024-11-13 16:03:48,179 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 26 SyntacticMatches, 11 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=49, Invalid=159, Unknown=2, NotChecked=0, Total=210 [2024-11-13 16:03:48,186 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 33 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 216 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-13 16:03:48,187 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 194 Invalid, 216 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 201 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-13 16:03:48,188 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 282 states. [2024-11-13 16:03:48,331 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 282 to 280. [2024-11-13 16:03:48,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 280 states, 174 states have (on average 1.0919540229885059) internal successors, (190), 179 states have internal predecessors, (190), 61 states have call successors, (61), 32 states have call predecessors, (61), 44 states have return successors, (80), 68 states have call predecessors, (80), 56 states have call successors, (80) [2024-11-13 16:03:48,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 280 states to 280 states and 331 transitions. [2024-11-13 16:03:48,333 INFO L78 Accepts]: Start accepts. Automaton has 280 states and 331 transitions. Word has length 41 [2024-11-13 16:03:48,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 16:03:48,334 INFO L471 AbstractCegarLoop]: Abstraction has 280 states and 331 transitions. [2024-11-13 16:03:48,334 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-13 16:03:48,334 INFO L276 IsEmpty]: Start isEmpty. Operand 280 states and 331 transitions. [2024-11-13 16:03:48,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-13 16:03:48,335 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 16:03:48,335 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 16:03:48,358 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-13 16:03:48,536 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 16:03:48,536 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 16:03:48,536 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 16:03:48,536 INFO L85 PathProgramCache]: Analyzing trace with hash 317533568, now seen corresponding path program 2 times [2024-11-13 16:03:48,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 16:03:48,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [769873831] [2024-11-13 16:03:48,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 16:03:48,537 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 16:03:48,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 16:03:48,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [133594742] [2024-11-13 16:03:48,561 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-13 16:03:48,562 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 16:03:48,562 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 16:03:48,564 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 16:03:48,568 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-13 16:03:48,890 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-13 16:03:48,890 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 16:03:48,895 WARN L253 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 183 conjuncts are in the unsatisfiable core [2024-11-13 16:03:48,900 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 16:03:48,926 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 [2024-11-13 16:03:49,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 [2024-11-13 16:03:49,168 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 [2024-11-13 16:03:49,187 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 [2024-11-13 16:03:49,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 11 treesize of output 7 [2024-11-13 16:03:50,131 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 [2024-11-13 16:03:50,778 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 [2024-11-13 16:03:54,033 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 16:03:54,033 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 84 treesize of output 72 [2024-11-13 16:03:54,083 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 16:03:54,083 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 98 treesize of output 78 [2024-11-13 16:03:54,688 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 1 proven. 19 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-13 16:03:54,688 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 16:04:59,950 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 16:04:59,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [769873831] [2024-11-13 16:04:59,950 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 16:04:59,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [133594742] [2024-11-13 16:04:59,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [133594742] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 16:04:59,950 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 16:04:59,950 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2024-11-13 16:04:59,950 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2077568465] [2024-11-13 16:04:59,950 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 16:04:59,951 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-13 16:04:59,951 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 16:04:59,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-13 16:04:59,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=567, Unknown=14, NotChecked=0, Total=650 [2024-11-13 16:04:59,954 INFO L87 Difference]: Start difference. First operand 280 states and 331 transitions. Second operand has 24 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 20 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-13 16:05:29,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 16:05:29,118 INFO L93 Difference]: Finished difference Result 292 states and 340 transitions. [2024-11-13 16:05:29,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-13 16:05:29,118 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 20 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Word has length 41 [2024-11-13 16:05:29,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 16:05:29,121 INFO L225 Difference]: With dead ends: 292 [2024-11-13 16:05:29,121 INFO L226 Difference]: Without dead ends: 290 [2024-11-13 16:05:29,122 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 91.0s TimeCoverageRelationStatistics Valid=223, Invalid=1565, Unknown=18, NotChecked=0, Total=1806 [2024-11-13 16:05:29,123 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 57 mSDsluCounter, 286 mSDsCounter, 0 mSdLazyCounter, 1644 mSolverCounterSat, 46 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 1700 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 1644 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.9s IncrementalHoareTripleChecker+Time [2024-11-13 16:05:29,123 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 325 Invalid, 1700 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 1644 Invalid, 10 Unknown, 0 Unchecked, 5.9s Time] [2024-11-13 16:05:29,124 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 290 states. [2024-11-13 16:05:29,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 290 to 232. [2024-11-13 16:05:29,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 232 states, 144 states have (on average 1.0972222222222223) internal successors, (158), 149 states have internal predecessors, (158), 51 states have call successors, (51), 26 states have call predecessors, (51), 36 states have return successors, (68), 57 states have call predecessors, (68), 47 states have call successors, (68) [2024-11-13 16:05:29,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 232 states to 232 states and 277 transitions. [2024-11-13 16:05:29,277 INFO L78 Accepts]: Start accepts. Automaton has 232 states and 277 transitions. Word has length 41 [2024-11-13 16:05:29,277 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 16:05:29,277 INFO L471 AbstractCegarLoop]: Abstraction has 232 states and 277 transitions. [2024-11-13 16:05:29,277 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 20 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-13 16:05:29,278 INFO L276 IsEmpty]: Start isEmpty. Operand 232 states and 277 transitions. [2024-11-13 16:05:29,278 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-13 16:05:29,279 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 16:05:29,279 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 16:05:29,294 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-13 16:05:29,479 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-13 16:05:29,479 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 16:05:29,480 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 16:05:29,480 INFO L85 PathProgramCache]: Analyzing trace with hash 133435933, now seen corresponding path program 3 times [2024-11-13 16:05:29,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 16:05:29,480 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [595776268] [2024-11-13 16:05:29,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 16:05:29,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 16:05:29,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-13 16:05:29,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [726460999] [2024-11-13 16:05:29,533 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-13 16:05:29,534 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 16:05:29,534 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 16:05:29,543 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 16:05:29,545 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-13 16:05:29,901 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-13 16:05:29,901 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 16:05:29,903 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 57 conjuncts are in the unsatisfiable core [2024-11-13 16:05:29,906 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 16:05:29,917 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 [2024-11-13 16:05:29,956 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 [2024-11-13 16:05:29,968 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 [2024-11-13 16:05:30,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 15 treesize of output 7 [2024-11-13 16:05:30,477 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 [2024-11-13 16:05:30,481 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 [2024-11-13 16:05:30,560 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-13 16:05:30,561 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 16:05:30,684 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 27 [2024-11-13 16:05:30,784 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 16:05:30,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [595776268] [2024-11-13 16:05:30,784 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-13 16:05:30,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [726460999] [2024-11-13 16:05:30,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [726460999] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 16:05:30,784 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-13 16:05:30,784 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-13 16:05:30,784 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [580185013] [2024-11-13 16:05:30,784 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-13 16:05:30,785 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-13 16:05:30,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 16:05:30,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-13 16:05:30,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-13 16:05:30,786 INFO L87 Difference]: Start difference. First operand 232 states and 277 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-13 16:05:31,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-13 16:05:31,622 INFO L93 Difference]: Finished difference Result 277 states and 339 transitions. [2024-11-13 16:05:31,622 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-13 16:05:31,622 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 41 [2024-11-13 16:05:31,623 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-13 16:05:31,625 INFO L225 Difference]: With dead ends: 277 [2024-11-13 16:05:31,625 INFO L226 Difference]: Without dead ends: 275 [2024-11-13 16:05:31,626 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 31 SyntacticMatches, 5 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-13 16:05:31,626 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 62 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 210 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 250 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 210 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-13 16:05:31,627 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 194 Invalid, 250 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 210 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-13 16:05:31,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2024-11-13 16:05:31,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 271. [2024-11-13 16:05:31,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 271 states, 168 states have (on average 1.1011904761904763) internal successors, (185), 174 states have internal predecessors, (185), 61 states have call successors, (61), 30 states have call predecessors, (61), 41 states have return successors, (83), 67 states have call predecessors, (83), 56 states have call successors, (83) [2024-11-13 16:05:31,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 271 states to 271 states and 329 transitions. [2024-11-13 16:05:31,778 INFO L78 Accepts]: Start accepts. Automaton has 271 states and 329 transitions. Word has length 41 [2024-11-13 16:05:31,778 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-13 16:05:31,778 INFO L471 AbstractCegarLoop]: Abstraction has 271 states and 329 transitions. [2024-11-13 16:05:31,779 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-13 16:05:31,779 INFO L276 IsEmpty]: Start isEmpty. Operand 271 states and 329 transitions. [2024-11-13 16:05:31,781 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-11-13 16:05:31,781 INFO L207 NwaCegarLoop]: Found error trace [2024-11-13 16:05:31,781 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-13 16:05:31,788 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-13 16:05:31,982 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-13 16:05:31,982 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-13 16:05:31,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-13 16:05:31,983 INFO L85 PathProgramCache]: Analyzing trace with hash 96897030, now seen corresponding path program 6 times [2024-11-13 16:05:31,983 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-13 16:05:31,983 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1955039257] [2024-11-13 16:05:31,983 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-13 16:05:31,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-13 16:05:32,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:33,450 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-13 16:05:33,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:34,486 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:05:34,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:35,199 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:05:35,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:35,877 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:05:35,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:36,624 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:05:36,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:37,282 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:05:37,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:38,015 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-13 16:05:38,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-13 16:05:38,426 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2024-11-13 16:05:38,426 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-13 16:05:38,426 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1955039257] [2024-11-13 16:05:38,426 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1955039257] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 16:05:38,426 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [327290749] [2024-11-13 16:05:38,426 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-13 16:05:38,426 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-13 16:05:38,427 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 [2024-11-13 16:05:38,428 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-13 16:05:38,430 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1432696a-ad04-4b39-9959-3da1dd8b3195/bin/uautomizer-verify-qhAvR1uOyd/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-13 16:05:38,807 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2024-11-13 16:05:38,807 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-13 16:05:38,812 WARN L253 TraceCheckSpWp]: Trace formula consists of 362 conjuncts, 221 conjuncts are in the unsatisfiable core [2024-11-13 16:05:38,817 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-13 16:05:38,840 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 49 [2024-11-13 16:05:38,862 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 [2024-11-13 16:05:39,028 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 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 [2024-11-13 16:05:39,039 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-13 16:05:39,054 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-13 16:05:39,224 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-13 16:05:43,123 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-13 16:05:43,124 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 36 [2024-11-13 16:05:43,189 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-13 16:05:44,093 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2024-11-13 16:05:44,093 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 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 [2024-11-13 16:05:44,099 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2024-11-13 16:05:44,636 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 48 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-13 16:05:44,636 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-13 16:05:50,789 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [327290749] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-13 16:05:50,789 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-13 16:05:50,789 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 21] total 50 [2024-11-13 16:05:50,790 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1063500801] [2024-11-13 16:05:50,790 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-13 16:05:50,790 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2024-11-13 16:05:50,790 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-13 16:05:50,791 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2024-11-13 16:05:50,792 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=145, Invalid=3047, Unknown=0, NotChecked=0, Total=3192 [2024-11-13 16:05:50,792 INFO L87 Difference]: Start difference. First operand 271 states and 329 transitions. Second operand has 50 states, 37 states have (on average 1.3513513513513513) internal successors, (50), 42 states have internal predecessors, (50), 13 states have call successors, (13), 6 states have call predecessors, (13), 14 states have return successors, (14), 14 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-13 16:06:00,800 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] [2024-11-13 16:06:25,753 WARN L286 SmtUtils]: Spent 16.72s on a formula simplification. DAG size of input: 160 DAG size of output: 96 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 16:06:30,145 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] [2024-11-13 16:06:39,549 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] [2024-11-13 16:06:51,854 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] [2024-11-13 16:07:08,076 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-13 16:07:40,884 WARN L286 SmtUtils]: Spent 24.43s on a formula simplification. DAG size of input: 150 DAG size of output: 100 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-13 16:07:44,968 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-13 16:08:05,224 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] [2024-11-13 16:08:09,835 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] [2024-11-13 16:08:14,719 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] [2024-11-13 16:08:18,826 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] [2024-11-13 16:08:22,933 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] [2024-11-13 16:08:27,081 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] [2024-11-13 16:08:31,166 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] [2024-11-13 16:08:35,273 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] [2024-11-13 16:08:39,413 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] [2024-11-13 16:08:43,551 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-13 16:08:47,654 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] [2024-11-13 16:08:51,828 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] [2024-11-13 16:08:55,926 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] [2024-11-13 16:09:00,039 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]