./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/gcd_4+newton_3_3.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version d790fecc Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/config/AutomizerReach.xml -i ../../sv-benchmarks/c/combinations/gcd_4+newton_3_3.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB --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 fac7e7835446ac69229cd712eb8181e46fef468b0e6881ccc6e306adaaef48bd --- Real Ultimate output --- This is Ultimate 0.3.0-dev-d790fec [2024-11-27 19:50:24,002 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-27 19:50:24,094 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-27 19:50:24,108 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-27 19:50:24,108 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-27 19:50:24,148 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-27 19:50:24,149 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-27 19:50:24,150 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-27 19:50:24,150 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-27 19:50:24,151 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-27 19:50:24,152 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-27 19:50:24,152 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-27 19:50:24,152 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-27 19:50:24,152 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-27 19:50:24,153 INFO L153 SettingsManager]: * Use SBE=true [2024-11-27 19:50:24,153 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-27 19:50:24,154 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-27 19:50:24,154 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-27 19:50:24,154 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-27 19:50:24,154 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2024-11-27 19:50:24,155 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-27 19:50:24,156 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-27 19:50:24,156 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-27 19:50:24,156 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-27 19:50:24,156 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-27 19:50:24,156 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 19:50:24,157 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-27 19:50:24,157 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-27 19:50:24,158 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-27 19:50:24,158 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-27 19:50:24,158 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 19:50:24,158 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-27 19:50:24,158 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-27 19:50:24,158 INFO L153 SettingsManager]: * Compute procedure contracts=false [2024-11-27 19:50:24,158 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-27 19:50:24,159 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-27 19:50:24,159 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-27 19:50:24,159 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-27 19:50:24,159 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-27 19:50:24,159 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-27 19:50:24,159 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-27 19:50:24,160 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_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB 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 -> fac7e7835446ac69229cd712eb8181e46fef468b0e6881ccc6e306adaaef48bd [2024-11-27 19:50:24,520 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-27 19:50:24,534 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-27 19:50:24,537 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-27 19:50:24,538 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-27 19:50:24,539 INFO L274 PluginConnector]: CDTParser initialized [2024-11-27 19:50:24,541 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/../../sv-benchmarks/c/combinations/gcd_4+newton_3_3.i [2024-11-27 19:50:27,553 INFO L533 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/2af876485/48a57f3d55424041b87f177a163207f1/FLAG685e50b41 [2024-11-27 19:50:27,821 INFO L384 CDTParser]: Found 1 translation units. [2024-11-27 19:50:27,822 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i [2024-11-27 19:50:27,830 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/2af876485/48a57f3d55424041b87f177a163207f1/FLAG685e50b41 [2024-11-27 19:50:27,845 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/2af876485/48a57f3d55424041b87f177a163207f1 [2024-11-27 19:50:27,850 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-27 19:50:27,852 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-27 19:50:27,853 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-27 19:50:27,853 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-27 19:50:27,859 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-27 19:50:27,859 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 07:50:27" (1/1) ... [2024-11-27 19:50:27,863 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@50eadb38 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:27, skipping insertion in model container [2024-11-27 19:50:27,863 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 07:50:27" (1/1) ... [2024-11-27 19:50:27,882 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-27 19:50:28,071 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[1224,1237] [2024-11-27 19:50:28,117 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[2848,2861] [2024-11-27 19:50:28,122 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-27 19:50:28,140 INFO L200 MainTranslator]: Completed pre-run [2024-11-27 19:50:28,151 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[1224,1237] [2024-11-27 19:50:28,172 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[2848,2861] [2024-11-27 19:50:28,176 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-27 19:50:28,194 INFO L204 MainTranslator]: Completed translation [2024-11-27 19:50:28,195 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28 WrapperNode [2024-11-27 19:50:28,196 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-27 19:50:28,197 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-27 19:50:28,198 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-27 19:50:28,198 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-27 19:50:28,209 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,217 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,243 INFO L138 Inliner]: procedures = 27, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 83 [2024-11-27 19:50:28,243 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-27 19:50:28,243 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-27 19:50:28,244 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-27 19:50:28,245 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-27 19:50:28,256 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,256 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,263 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,285 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-27 19:50:28,286 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,286 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,291 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,296 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,304 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,305 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,306 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,312 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-27 19:50:28,313 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-27 19:50:28,313 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-27 19:50:28,313 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-27 19:50:28,317 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (1/1) ... [2024-11-27 19:50:28,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 19:50:28,347 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:28,364 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-27 19:50:28,368 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-27 19:50:28,400 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-27 19:50:28,400 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2024-11-27 19:50:28,400 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2024-11-27 19:50:28,401 INFO L130 BoogieDeclarations]: Found specification of procedure f [2024-11-27 19:50:28,401 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2024-11-27 19:50:28,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-27 19:50:28,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-27 19:50:28,401 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-27 19:50:28,401 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-27 19:50:28,401 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-27 19:50:28,401 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-27 19:50:28,481 INFO L234 CfgBuilder]: Building ICFG [2024-11-27 19:50:28,483 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-27 19:50:28,716 INFO L? ?]: Removed 25 outVars from TransFormulas that were not future-live. [2024-11-27 19:50:28,716 INFO L283 CfgBuilder]: Performing block encoding [2024-11-27 19:50:28,731 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-27 19:50:28,731 INFO L312 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-27 19:50:28,731 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 07:50:28 BoogieIcfgContainer [2024-11-27 19:50:28,732 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-27 19:50:28,734 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-27 19:50:28,735 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-27 19:50:28,740 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-27 19:50:28,741 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.11 07:50:27" (1/3) ... [2024-11-27 19:50:28,741 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19a722b3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 07:50:28, skipping insertion in model container [2024-11-27 19:50:28,742 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:28" (2/3) ... [2024-11-27 19:50:28,742 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19a722b3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 07:50:28, skipping insertion in model container [2024-11-27 19:50:28,742 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 07:50:28" (3/3) ... [2024-11-27 19:50:28,744 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_3.i [2024-11-27 19:50:28,762 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-27 19:50:28,766 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_3.i that has 4 procedures, 46 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2024-11-27 19:50:28,844 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-27 19:50:28,861 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;@57fad0b6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-27 19:50:28,862 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2024-11-27 19:50:28,867 INFO L276 IsEmpty]: Start isEmpty. Operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-27 19:50:28,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-27 19:50:28,877 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:28,877 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:28,878 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:28,885 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:28,885 INFO L85 PathProgramCache]: Analyzing trace with hash -1780387208, now seen corresponding path program 1 times [2024-11-27 19:50:28,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:28,895 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1425660959] [2024-11-27 19:50:28,896 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:28,896 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:29,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:50:29,298 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-27 19:50:29,298 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:29,299 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1425660959] [2024-11-27 19:50:29,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1425660959] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-27 19:50:29,300 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-27 19:50:29,300 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-27 19:50:29,302 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1839183613] [2024-11-27 19:50:29,302 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-27 19:50:29,307 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-27 19:50:29,307 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:29,329 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-27 19:50:29,330 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-27 19:50:29,332 INFO L87 Difference]: Start difference. First operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:29,389 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:29,389 INFO L93 Difference]: Finished difference Result 90 states and 123 transitions. [2024-11-27 19:50:29,394 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-27 19:50:29,396 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-27 19:50:29,396 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:29,402 INFO L225 Difference]: With dead ends: 90 [2024-11-27 19:50:29,402 INFO L226 Difference]: Without dead ends: 42 [2024-11-27 19:50:29,405 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 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-27 19:50:29,408 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 7 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:29,409 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 95 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-27 19:50:29,423 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-27 19:50:29,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2024-11-27 19:50:29,447 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:50:29,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 47 transitions. [2024-11-27 19:50:29,460 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 47 transitions. Word has length 11 [2024-11-27 19:50:29,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:29,460 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 47 transitions. [2024-11-27 19:50:29,461 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:29,461 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 47 transitions. [2024-11-27 19:50:29,462 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-27 19:50:29,463 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:29,464 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:29,465 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-27 19:50:29,465 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:29,466 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:29,466 INFO L85 PathProgramCache]: Analyzing trace with hash 1301222473, now seen corresponding path program 1 times [2024-11-27 19:50:29,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:29,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1458369548] [2024-11-27 19:50:29,467 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:29,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:29,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:50:29,631 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-27 19:50:29,632 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:29,632 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1458369548] [2024-11-27 19:50:29,632 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1458369548] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-27 19:50:29,632 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-27 19:50:29,633 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-27 19:50:29,633 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1188707844] [2024-11-27 19:50:29,633 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-27 19:50:29,634 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-27 19:50:29,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:29,635 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-27 19:50:29,635 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-27 19:50:29,635 INFO L87 Difference]: Start difference. First operand 39 states and 47 transitions. Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:29,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:29,678 INFO L93 Difference]: Finished difference Result 55 states and 68 transitions. [2024-11-27 19:50:29,679 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-27 19:50:29,679 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2024-11-27 19:50:29,679 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:29,680 INFO L225 Difference]: With dead ends: 55 [2024-11-27 19:50:29,680 INFO L226 Difference]: Without dead ends: 41 [2024-11-27 19:50:29,681 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 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-27 19:50:29,681 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 4 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:29,685 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 79 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-27 19:50:29,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-27 19:50:29,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2024-11-27 19:50:29,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:50:29,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2024-11-27 19:50:29,699 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 13 [2024-11-27 19:50:29,699 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:29,699 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2024-11-27 19:50:29,700 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:29,700 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2024-11-27 19:50:29,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-27 19:50:29,702 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:29,703 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:29,703 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-27 19:50:29,703 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:29,704 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:29,704 INFO L85 PathProgramCache]: Analyzing trace with hash 299954435, now seen corresponding path program 1 times [2024-11-27 19:50:29,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:29,704 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1413750419] [2024-11-27 19:50:29,704 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:29,704 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:29,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:50:29,877 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:29,878 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:29,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1413750419] [2024-11-27 19:50:29,878 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1413750419] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-27 19:50:29,878 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-27 19:50:29,879 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-27 19:50:29,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1475431825] [2024-11-27 19:50:29,880 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-27 19:50:29,880 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-27 19:50:29,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:29,882 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-27 19:50:29,882 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-27 19:50:29,882 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:29,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:29,926 INFO L93 Difference]: Finished difference Result 56 states and 68 transitions. [2024-11-27 19:50:29,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-27 19:50:29,929 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2024-11-27 19:50:29,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:29,931 INFO L225 Difference]: With dead ends: 56 [2024-11-27 19:50:29,931 INFO L226 Difference]: Without dead ends: 43 [2024-11-27 19:50:29,933 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 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-27 19:50:29,934 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:29,936 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 77 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-27 19:50:29,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-27 19:50:29,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-27 19:50:29,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 31 states have internal predecessors, (34), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:50:29,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 51 transitions. [2024-11-27 19:50:29,949 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 51 transitions. Word has length 15 [2024-11-27 19:50:29,950 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:29,950 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 51 transitions. [2024-11-27 19:50:29,950 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:29,950 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 51 transitions. [2024-11-27 19:50:29,951 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-27 19:50:29,951 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:29,951 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:29,951 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-27 19:50:29,951 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:29,951 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:29,952 INFO L85 PathProgramCache]: Analyzing trace with hash -153993347, now seen corresponding path program 1 times [2024-11-27 19:50:29,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:29,954 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [756224357] [2024-11-27 19:50:29,954 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:29,955 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:29,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:50:30,170 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:30,171 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:30,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [756224357] [2024-11-27 19:50:30,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [756224357] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 19:50:30,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [470047534] [2024-11-27 19:50:30,171 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:30,171 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:30,171 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:30,176 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:30,177 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-27 19:50:30,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:50:30,239 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-27 19:50:30,243 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:50:30,353 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:30,354 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:50:30,428 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:30,429 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [470047534] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:50:30,429 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 19:50:30,429 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 4] total 9 [2024-11-27 19:50:30,429 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495519142] [2024-11-27 19:50:30,429 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 19:50:30,430 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-27 19:50:30,430 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:30,430 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-27 19:50:30,430 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2024-11-27 19:50:30,431 INFO L87 Difference]: Start difference. First operand 43 states and 51 transitions. Second operand has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:30,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:30,506 INFO L93 Difference]: Finished difference Result 60 states and 73 transitions. [2024-11-27 19:50:30,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-27 19:50:30,507 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 17 [2024-11-27 19:50:30,507 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:30,507 INFO L225 Difference]: With dead ends: 60 [2024-11-27 19:50:30,508 INFO L226 Difference]: Without dead ends: 47 [2024-11-27 19:50:30,508 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2024-11-27 19:50:30,509 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:30,509 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 222 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 19:50:30,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-27 19:50:30,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2024-11-27 19:50:30,516 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 35 states have internal predecessors, (38), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:50:30,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 55 transitions. [2024-11-27 19:50:30,517 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 55 transitions. Word has length 17 [2024-11-27 19:50:30,517 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:30,517 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 55 transitions. [2024-11-27 19:50:30,518 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:30,518 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 55 transitions. [2024-11-27 19:50:30,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-27 19:50:30,519 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:30,519 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:30,529 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-27 19:50:30,723 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:30,723 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:30,723 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:30,724 INFO L85 PathProgramCache]: Analyzing trace with hash -1157932815, now seen corresponding path program 2 times [2024-11-27 19:50:30,724 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:30,724 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [904716520] [2024-11-27 19:50:30,724 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-27 19:50:30,724 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:30,763 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-27 19:50:30,765 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:50:30,966 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:30,966 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:30,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [904716520] [2024-11-27 19:50:30,967 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [904716520] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 19:50:30,967 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1694454688] [2024-11-27 19:50:30,967 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-27 19:50:30,967 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:30,968 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:30,970 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:30,973 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-27 19:50:31,028 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-27 19:50:31,028 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:50:31,029 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-27 19:50:31,031 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:50:31,195 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:31,195 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:50:31,317 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:31,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1694454688] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:50:31,317 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 19:50:31,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2024-11-27 19:50:31,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1769287211] [2024-11-27 19:50:31,318 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 19:50:31,318 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-27 19:50:31,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:31,319 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-27 19:50:31,319 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=172, Unknown=0, NotChecked=0, Total=272 [2024-11-27 19:50:31,319 INFO L87 Difference]: Start difference. First operand 47 states and 55 transitions. Second operand has 17 states, 17 states have (on average 2.7058823529411766) internal successors, (46), 17 states have internal predecessors, (46), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:31,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:31,477 INFO L93 Difference]: Finished difference Result 69 states and 88 transitions. [2024-11-27 19:50:31,478 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-27 19:50:31,479 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.7058823529411766) internal successors, (46), 17 states have internal predecessors, (46), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 21 [2024-11-27 19:50:31,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:31,481 INFO L225 Difference]: With dead ends: 69 [2024-11-27 19:50:31,481 INFO L226 Difference]: Without dead ends: 54 [2024-11-27 19:50:31,482 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=124, Invalid=218, Unknown=0, NotChecked=0, Total=342 [2024-11-27 19:50:31,482 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 7 mSDsluCounter, 217 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 257 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:31,485 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 257 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 19:50:31,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-11-27 19:50:31,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 52. [2024-11-27 19:50:31,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 38 states have (on average 1.131578947368421) internal successors, (43), 40 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:50:31,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 60 transitions. [2024-11-27 19:50:31,501 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 60 transitions. Word has length 21 [2024-11-27 19:50:31,501 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:31,501 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 60 transitions. [2024-11-27 19:50:31,501 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.7058823529411766) internal successors, (46), 17 states have internal predecessors, (46), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:31,501 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 60 transitions. [2024-11-27 19:50:31,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-27 19:50:31,502 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:31,502 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:31,513 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-27 19:50:31,703 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:31,703 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:31,703 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:31,703 INFO L85 PathProgramCache]: Analyzing trace with hash -1417329111, now seen corresponding path program 3 times [2024-11-27 19:50:31,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:31,704 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1697471654] [2024-11-27 19:50:31,704 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-27 19:50:31,704 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:31,736 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-27 19:50:31,736 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-27 19:50:31,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [998312224] [2024-11-27 19:50:31,738 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-27 19:50:31,738 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:31,738 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:31,741 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:31,744 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-27 19:50:31,801 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-27 19:50:31,802 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:50:31,807 INFO L256 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-27 19:50:31,808 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:50:32,011 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-27 19:50:32,012 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:50:32,511 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-27 19:50:32,512 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:32,512 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1697471654] [2024-11-27 19:50:32,512 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-27 19:50:32,512 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [998312224] [2024-11-27 19:50:32,512 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [998312224] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:50:32,513 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:50:32,514 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2024-11-27 19:50:32,514 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1847895954] [2024-11-27 19:50:32,514 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:50:32,514 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-27 19:50:32,515 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:32,517 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-27 19:50:32,518 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2024-11-27 19:50:32,518 INFO L87 Difference]: Start difference. First operand 52 states and 60 transitions. Second operand has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:33,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:33,041 INFO L93 Difference]: Finished difference Result 75 states and 91 transitions. [2024-11-27 19:50:33,041 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-27 19:50:33,042 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2024-11-27 19:50:33,042 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:33,043 INFO L225 Difference]: With dead ends: 75 [2024-11-27 19:50:33,043 INFO L226 Difference]: Without dead ends: 72 [2024-11-27 19:50:33,044 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-11-27 19:50:33,047 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 12 mSDsluCounter, 409 mSDsCounter, 0 mSdLazyCounter, 260 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 445 SdHoareTripleChecker+Invalid, 272 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 260 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:33,047 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 445 Invalid, 272 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 260 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-27 19:50:33,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-11-27 19:50:33,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2024-11-27 19:50:33,067 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 51 states have (on average 1.196078431372549) internal successors, (61), 55 states have internal predecessors, (61), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-27 19:50:33,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 83 transitions. [2024-11-27 19:50:33,070 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 83 transitions. Word has length 23 [2024-11-27 19:50:33,070 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:33,070 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 83 transitions. [2024-11-27 19:50:33,070 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:33,070 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 83 transitions. [2024-11-27 19:50:33,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-27 19:50:33,071 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:33,071 INFO L218 NwaCegarLoop]: trace histogram [6, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:33,084 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-27 19:50:33,275 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-27 19:50:33,275 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:33,276 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:33,276 INFO L85 PathProgramCache]: Analyzing trace with hash -1589066399, now seen corresponding path program 4 times [2024-11-27 19:50:33,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:33,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1010916914] [2024-11-27 19:50:33,276 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-27 19:50:33,276 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:33,297 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-27 19:50:33,297 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:50:33,514 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:33,514 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:33,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1010916914] [2024-11-27 19:50:33,515 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1010916914] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 19:50:33,516 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [612127169] [2024-11-27 19:50:33,516 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-27 19:50:33,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:33,516 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:33,518 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:33,522 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-27 19:50:33,579 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-27 19:50:33,579 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:50:33,580 INFO L256 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-27 19:50:33,582 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:50:33,827 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 2 proven. 34 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:33,827 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:50:34,029 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:34,030 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [612127169] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:50:34,030 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 19:50:34,030 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 22 [2024-11-27 19:50:34,030 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1822960931] [2024-11-27 19:50:34,030 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 19:50:34,031 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-27 19:50:34,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:34,032 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-27 19:50:34,032 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=367, Unknown=0, NotChecked=0, Total=462 [2024-11-27 19:50:34,032 INFO L87 Difference]: Start difference. First operand 69 states and 83 transitions. Second operand has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:34,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:34,347 INFO L93 Difference]: Finished difference Result 90 states and 108 transitions. [2024-11-27 19:50:34,347 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-27 19:50:34,347 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 25 [2024-11-27 19:50:34,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:34,348 INFO L225 Difference]: With dead ends: 90 [2024-11-27 19:50:34,348 INFO L226 Difference]: Without dead ends: 61 [2024-11-27 19:50:34,349 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=174, Invalid=528, Unknown=0, NotChecked=0, Total=702 [2024-11-27 19:50:34,350 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 12 mSDsluCounter, 470 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 509 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:34,350 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 509 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-27 19:50:34,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-11-27 19:50:34,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2024-11-27 19:50:34,363 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 44 states have (on average 1.1136363636363635) internal successors, (49), 47 states have internal predecessors, (49), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-27 19:50:34,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 69 transitions. [2024-11-27 19:50:34,365 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 69 transitions. Word has length 25 [2024-11-27 19:50:34,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:34,365 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 69 transitions. [2024-11-27 19:50:34,365 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:34,365 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 69 transitions. [2024-11-27 19:50:34,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-27 19:50:34,368 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:34,368 INFO L218 NwaCegarLoop]: trace histogram [7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:34,378 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-27 19:50:34,568 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:34,569 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:34,569 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:34,569 INFO L85 PathProgramCache]: Analyzing trace with hash 616958939, now seen corresponding path program 5 times [2024-11-27 19:50:34,569 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:34,569 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [716863976] [2024-11-27 19:50:34,569 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-27 19:50:34,569 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:34,586 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2024-11-27 19:50:34,586 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:50:34,706 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 25 proven. 20 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-27 19:50:34,706 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:34,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [716863976] [2024-11-27 19:50:34,707 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [716863976] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-27 19:50:34,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [138882743] [2024-11-27 19:50:34,707 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-27 19:50:34,707 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:34,707 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:34,709 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:34,712 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-27 19:50:34,767 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2024-11-27 19:50:34,767 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:50:34,768 INFO L256 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-27 19:50:34,770 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:50:35,008 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 12 proven. 37 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:35,008 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:50:35,246 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:50:35,246 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [138882743] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:50:35,246 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-27 19:50:35,247 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 10, 10] total 23 [2024-11-27 19:50:35,247 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [374987111] [2024-11-27 19:50:35,247 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-27 19:50:35,247 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-27 19:50:35,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:35,248 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-27 19:50:35,249 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=384, Unknown=0, NotChecked=0, Total=506 [2024-11-27 19:50:35,249 INFO L87 Difference]: Start difference. First operand 61 states and 69 transitions. Second operand has 23 states, 23 states have (on average 2.6956521739130435) internal successors, (62), 23 states have internal predecessors, (62), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:35,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:35,420 INFO L93 Difference]: Finished difference Result 67 states and 74 transitions. [2024-11-27 19:50:35,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-27 19:50:35,420 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.6956521739130435) internal successors, (62), 23 states have internal predecessors, (62), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2024-11-27 19:50:35,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:35,421 INFO L225 Difference]: With dead ends: 67 [2024-11-27 19:50:35,422 INFO L226 Difference]: Without dead ends: 49 [2024-11-27 19:50:35,423 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=142, Invalid=410, Unknown=0, NotChecked=0, Total=552 [2024-11-27 19:50:35,423 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 512 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 550 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:35,425 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 550 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 19:50:35,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-27 19:50:35,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2024-11-27 19:50:35,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 36 states have (on average 1.0277777777777777) internal successors, (37), 37 states have internal predecessors, (37), 8 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-27 19:50:35,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 52 transitions. [2024-11-27 19:50:35,437 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 52 transitions. Word has length 27 [2024-11-27 19:50:35,437 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:35,437 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 52 transitions. [2024-11-27 19:50:35,437 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.6956521739130435) internal successors, (62), 23 states have internal predecessors, (62), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:35,437 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 52 transitions. [2024-11-27 19:50:35,438 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-27 19:50:35,438 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:35,438 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:35,451 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-27 19:50:35,638 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:35,639 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:35,639 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:35,639 INFO L85 PathProgramCache]: Analyzing trace with hash -1889018642, now seen corresponding path program 1 times [2024-11-27 19:50:35,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:35,640 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [523517383] [2024-11-27 19:50:35,640 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:35,640 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:35,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-27 19:50:35,679 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1667513057] [2024-11-27 19:50:35,679 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:35,679 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:35,679 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:35,683 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:35,686 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-27 19:50:35,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:50:35,736 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-27 19:50:35,738 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:50:35,933 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-27 19:50:35,934 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:50:36,362 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-27 19:50:36,362 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-27 19:50:36,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [523517383] [2024-11-27 19:50:36,362 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-27 19:50:36,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1667513057] [2024-11-27 19:50:36,362 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1667513057] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:50:36,362 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:50:36,363 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2024-11-27 19:50:36,363 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [981763327] [2024-11-27 19:50:36,363 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:50:36,363 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-27 19:50:36,363 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-27 19:50:36,364 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-27 19:50:36,364 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2024-11-27 19:50:36,364 INFO L87 Difference]: Start difference. First operand 49 states and 52 transitions. Second operand has 16 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 15 states have internal predecessors, (38), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-27 19:50:36,610 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:36,610 INFO L93 Difference]: Finished difference Result 49 states and 52 transitions. [2024-11-27 19:50:36,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-27 19:50:36,610 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 15 states have internal predecessors, (38), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 28 [2024-11-27 19:50:36,611 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:36,611 INFO L225 Difference]: With dead ends: 49 [2024-11-27 19:50:36,611 INFO L226 Difference]: Without dead ends: 23 [2024-11-27 19:50:36,612 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 38 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2024-11-27 19:50:36,612 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 1 mSDsluCounter, 376 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 410 SdHoareTripleChecker+Invalid, 178 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:36,613 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 410 Invalid, 178 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-27 19:50:36,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-27 19:50:36,615 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-27 19:50:36,616 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 14 states have (on average 1.0) internal successors, (14), 14 states have internal predecessors, (14), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-27 19:50:36,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2024-11-27 19:50:36,616 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 28 [2024-11-27 19:50:36,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:36,617 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2024-11-27 19:50:36,617 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 15 states have internal predecessors, (38), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-27 19:50:36,617 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2024-11-27 19:50:36,617 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-27 19:50:36,618 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:36,618 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:36,628 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-27 19:50:36,822 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:36,822 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:36,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:36,823 INFO L85 PathProgramCache]: Analyzing trace with hash -21288017, now seen corresponding path program 1 times [2024-11-27 19:50:36,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-27 19:50:36,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [265030030] [2024-11-27 19:50:36,823 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:36,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-27 19:50:36,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-27 19:50:36,832 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-27 19:50:36,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-27 19:50:36,859 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-27 19:50:36,861 INFO L340 BasicCegarLoop]: Counterexample is feasible [2024-11-27 19:50:36,863 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2024-11-27 19:50:36,865 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2024-11-27 19:50:36,866 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-11-27 19:50:36,870 INFO L422 BasicCegarLoop]: Path program histogram: [5, 1, 1, 1, 1, 1] [2024-11-27 19:50:36,897 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-27 19:50:36,900 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 27.11 07:50:36 BoogieIcfgContainer [2024-11-27 19:50:36,902 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-27 19:50:36,903 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-27 19:50:36,903 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-27 19:50:36,903 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-27 19:50:36,904 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 07:50:28" (3/4) ... [2024-11-27 19:50:36,906 INFO L149 WitnessPrinter]: No result that supports witness generation found [2024-11-27 19:50:36,907 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-27 19:50:36,908 INFO L158 Benchmark]: Toolchain (without parser) took 9056.13ms. Allocated memory is still 142.6MB. Free memory was 117.3MB in the beginning and 100.4MB in the end (delta: 16.9MB). Peak memory consumption was 13.8MB. Max. memory is 16.1GB. [2024-11-27 19:50:36,908 INFO L158 Benchmark]: CDTParser took 0.36ms. Allocated memory is still 117.4MB. Free memory is still 73.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-27 19:50:36,909 INFO L158 Benchmark]: CACSL2BoogieTranslator took 343.64ms. Allocated memory is still 142.6MB. Free memory was 117.0MB in the beginning and 105.2MB in the end (delta: 11.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-27 19:50:36,909 INFO L158 Benchmark]: Boogie Procedure Inliner took 45.59ms. Allocated memory is still 142.6MB. Free memory was 104.9MB in the beginning and 103.7MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-27 19:50:36,910 INFO L158 Benchmark]: Boogie Preprocessor took 68.87ms. Allocated memory is still 142.6MB. Free memory was 103.7MB in the beginning and 102.0MB in the end (delta: 1.7MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-27 19:50:36,910 INFO L158 Benchmark]: RCFGBuilder took 418.67ms. Allocated memory is still 142.6MB. Free memory was 102.0MB in the beginning and 88.5MB in the end (delta: 13.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-27 19:50:36,910 INFO L158 Benchmark]: TraceAbstraction took 8167.66ms. Allocated memory is still 142.6MB. Free memory was 87.7MB in the beginning and 100.4MB in the end (delta: -12.7MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-27 19:50:36,911 INFO L158 Benchmark]: Witness Printer took 4.27ms. Allocated memory is still 142.6MB. Free memory was 100.4MB in the beginning and 100.4MB in the end (delta: 27.1kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-27 19:50:36,912 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.36ms. Allocated memory is still 117.4MB. Free memory is still 73.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 343.64ms. Allocated memory is still 142.6MB. Free memory was 117.0MB in the beginning and 105.2MB in the end (delta: 11.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 45.59ms. Allocated memory is still 142.6MB. Free memory was 104.9MB in the beginning and 103.7MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 68.87ms. Allocated memory is still 142.6MB. Free memory was 103.7MB in the beginning and 102.0MB in the end (delta: 1.7MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 418.67ms. Allocated memory is still 142.6MB. Free memory was 102.0MB in the beginning and 88.5MB in the end (delta: 13.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 8167.66ms. Allocated memory is still 142.6MB. Free memory was 87.7MB in the beginning and 100.4MB in the end (delta: -12.7MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 4.27ms. Allocated memory is still 142.6MB. Free memory was 100.4MB in the beginning and 100.4MB in the end (delta: 27.1kB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - UnprovableResult [Line: 109]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: overapproximation of someBinaryFLOATComparisonOperation at line 98, overapproximation of someBinaryDOUBLEComparisonOperation at line 108, overapproximation of someBinaryArithmeticFLOAToperation at line 100, overapproximation of someBinaryArithmeticFLOAToperation at line 102, overapproximation of someBinaryArithmeticFLOAToperation at line 92, overapproximation of someBinaryArithmeticFLOAToperation at line 87, overapproximation of someBinaryArithmeticFLOAToperation at line 104. Possible FailurePath: [L115] COND FALSE !(__VERIFIER_nondet_int()) [L118] CALL main2() [L97] float IN = __VERIFIER_nondet_float(); [L98] CALL assume_abort_if_not(IN > -0.6f && IN < 0.6f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -0.6f && IN < 0.6f) [L100] CALL, EXPR f(IN) VAL [\old(x)=112] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=112] [L100] RET, EXPR f(IN) VAL [IN=112] [L100] CALL, EXPR fp(IN) VAL [\old(x)=112] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=112] [L100] RET, EXPR fp(IN) VAL [IN=112] [L100] float x = IN - f(IN)/fp(IN); [L102] CALL, EXPR f(x) VAL [\old(x)=110] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=110] [L102] RET, EXPR f(x) VAL [IN=112, x=110] [L102] CALL, EXPR fp(x) VAL [\old(x)=110] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=110] [L102] RET, EXPR fp(x) VAL [IN=112, x=110] [L102] x = x - f(x)/fp(x) [L104] CALL, EXPR f(x) VAL [\old(x)=111] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=111] [L104] RET, EXPR f(x) VAL [IN=112, x=111] [L104] CALL, EXPR fp(x) VAL [\old(x)=111] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=111] [L104] RET, EXPR fp(x) VAL [IN=112, x=111] [L104] x = x - f(x)/fp(x) [L108] COND TRUE !(x < 0.1) VAL [IN=112] [L109] reach_error() VAL [IN=112] - UnprovableResult [Line: 27]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 46 locations, 2 error locations. Started 1 CEGAR loops. OverallTime: 8.1s, OverallIterations: 10, TraceHistogramMax: 7, PathProgramHistogramMax: 5, EmptinessCheckTime: 0.0s, AutomataDifference: 1.7s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 47 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 43 mSDsluCounter, 2644 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2283 mSDsCounter, 36 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 920 IncrementalHoareTripleChecker+Invalid, 956 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 36 mSolverCounterUnsat, 361 mSDtfsCounter, 920 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 323 GetRequests, 210 SyntacticMatches, 2 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 411 ImplicationChecksByTransitivity, 1.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=69occurred in iteration=6, InterpolantAutomatonStates: 71, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 8 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 4.0s InterpolantComputationTime, 355 NumberOfCodeBlocks, 351 NumberOfCodeBlocksAsserted, 42 NumberOfCheckSat, 392 ConstructedInterpolants, 0 QuantifiedInterpolants, 1983 SizeOfPredicates, 17 NumberOfNonLiveVariables, 549 ConjunctsInSsa, 95 ConjunctsInUnsatCore, 19 InterpolantComputations, 3 PerfectInterpolantSequences, 108/420 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available RESULT: Ultimate could not prove your program: unable to determine feasibility of some traces [2024-11-27 19:50:36,938 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/config/AutomizerReach.xml -i ../../sv-benchmarks/c/combinations/gcd_4+newton_3_3.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB --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 fac7e7835446ac69229cd712eb8181e46fef468b0e6881ccc6e306adaaef48bd --- Real Ultimate output --- This is Ultimate 0.3.0-dev-d790fec [2024-11-27 19:50:39,695 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-27 19:50:39,819 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2024-11-27 19:50:39,829 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-27 19:50:39,829 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-27 19:50:39,868 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-27 19:50:39,869 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-27 19:50:39,870 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-27 19:50:39,870 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-27 19:50:39,871 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-27 19:50:39,871 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-27 19:50:39,871 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-27 19:50:39,872 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-27 19:50:39,872 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-27 19:50:39,872 INFO L153 SettingsManager]: * Use SBE=true [2024-11-27 19:50:39,872 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-27 19:50:39,872 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-27 19:50:39,872 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-27 19:50:39,872 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-27 19:50:39,873 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-27 19:50:39,874 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-27 19:50:39,874 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-27 19:50:39,875 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-27 19:50:39,875 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-27 19:50:39,875 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-27 19:50:39,875 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-27 19:50:39,875 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-27 19:50:39,876 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-27 19:50:39,876 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2024-11-27 19:50:39,876 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-27 19:50:39,876 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-27 19:50:39,877 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-27 19:50:39,877 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-27 19:50:39,877 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-27 19:50:39,877 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 19:50:39,877 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-27 19:50:39,877 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 19:50:39,878 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Compute procedure contracts=false [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-27 19:50:39,878 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-27 19:50:39,879 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-27 19:50:39,880 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_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB 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 -> fac7e7835446ac69229cd712eb8181e46fef468b0e6881ccc6e306adaaef48bd [2024-11-27 19:50:40,221 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-27 19:50:40,230 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-27 19:50:40,233 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-27 19:50:40,234 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-27 19:50:40,235 INFO L274 PluginConnector]: CDTParser initialized [2024-11-27 19:50:40,237 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/../../sv-benchmarks/c/combinations/gcd_4+newton_3_3.i [2024-11-27 19:50:43,292 INFO L533 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/ee3e9b42c/0a1a07dfc97b4c1d8374f77fde06c443/FLAGaa9ee4d2e [2024-11-27 19:50:43,584 INFO L384 CDTParser]: Found 1 translation units. [2024-11-27 19:50:43,589 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i [2024-11-27 19:50:43,601 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/ee3e9b42c/0a1a07dfc97b4c1d8374f77fde06c443/FLAGaa9ee4d2e [2024-11-27 19:50:43,625 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/data/ee3e9b42c/0a1a07dfc97b4c1d8374f77fde06c443 [2024-11-27 19:50:43,627 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-27 19:50:43,630 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-27 19:50:43,631 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-27 19:50:43,633 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-27 19:50:43,638 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-27 19:50:43,639 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 07:50:43" (1/1) ... [2024-11-27 19:50:43,640 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@13e33003 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:43, skipping insertion in model container [2024-11-27 19:50:43,642 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 07:50:43" (1/1) ... [2024-11-27 19:50:43,661 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-27 19:50:43,862 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[1224,1237] [2024-11-27 19:50:43,915 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[2848,2861] [2024-11-27 19:50:43,920 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-27 19:50:43,942 INFO L200 MainTranslator]: Completed pre-run [2024-11-27 19:50:43,958 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[1224,1237] [2024-11-27 19:50:43,981 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_9650a620-6933-4a67-8ce9-23fad19f6d37/sv-benchmarks/c/combinations/gcd_4+newton_3_3.i[2848,2861] [2024-11-27 19:50:43,986 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-27 19:50:44,009 INFO L204 MainTranslator]: Completed translation [2024-11-27 19:50:44,009 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44 WrapperNode [2024-11-27 19:50:44,010 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-27 19:50:44,011 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-27 19:50:44,011 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-27 19:50:44,011 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-27 19:50:44,022 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,038 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,057 INFO L138 Inliner]: procedures = 28, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 80 [2024-11-27 19:50:44,058 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-27 19:50:44,058 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-27 19:50:44,059 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-27 19:50:44,059 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-27 19:50:44,069 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,069 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,072 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,086 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-27 19:50:44,086 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,087 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,095 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,096 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,100 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,102 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,103 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,110 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-27 19:50:44,110 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-27 19:50:44,111 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-27 19:50:44,111 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-27 19:50:44,112 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (1/1) ... [2024-11-27 19:50:44,129 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-27 19:50:44,145 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:44,158 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-27 19:50:44,162 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-27 19:50:44,188 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-27 19:50:44,189 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-27 19:50:44,189 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-27 19:50:44,189 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2024-11-27 19:50:44,189 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2024-11-27 19:50:44,189 INFO L130 BoogieDeclarations]: Found specification of procedure f [2024-11-27 19:50:44,189 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2024-11-27 19:50:44,189 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-27 19:50:44,190 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-27 19:50:44,190 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-27 19:50:44,191 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-27 19:50:44,286 INFO L234 CfgBuilder]: Building ICFG [2024-11-27 19:50:44,287 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-27 19:50:59,094 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2024-11-27 19:50:59,094 INFO L283 CfgBuilder]: Performing block encoding [2024-11-27 19:50:59,108 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-27 19:50:59,109 INFO L312 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-27 19:50:59,110 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 07:50:59 BoogieIcfgContainer [2024-11-27 19:50:59,111 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-27 19:50:59,114 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-27 19:50:59,116 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-27 19:50:59,122 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-27 19:50:59,122 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.11 07:50:43" (1/3) ... [2024-11-27 19:50:59,123 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@52a0fe0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 07:50:59, skipping insertion in model container [2024-11-27 19:50:59,123 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 07:50:44" (2/3) ... [2024-11-27 19:50:59,123 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@52a0fe0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 07:50:59, skipping insertion in model container [2024-11-27 19:50:59,123 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 07:50:59" (3/3) ... [2024-11-27 19:50:59,125 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_3.i [2024-11-27 19:50:59,138 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-27 19:50:59,139 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_3.i that has 4 procedures, 46 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2024-11-27 19:50:59,199 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-27 19:50:59,214 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;@127cb3c3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-27 19:50:59,215 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2024-11-27 19:50:59,219 INFO L276 IsEmpty]: Start isEmpty. Operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-27 19:50:59,226 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-27 19:50:59,227 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:59,227 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:59,228 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:59,233 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:59,233 INFO L85 PathProgramCache]: Analyzing trace with hash -1780387208, now seen corresponding path program 1 times [2024-11-27 19:50:59,241 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:50:59,242 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1217869864] [2024-11-27 19:50:59,242 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:59,242 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:59,243 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:59,244 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:59,246 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-27 19:50:59,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:50:59,363 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-27 19:50:59,367 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:50:59,477 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-27 19:50:59,478 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-27 19:50:59,478 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:50:59,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1217869864] [2024-11-27 19:50:59,480 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1217869864] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-27 19:50:59,481 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-27 19:50:59,481 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-27 19:50:59,484 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [567452576] [2024-11-27 19:50:59,485 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-27 19:50:59,489 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-27 19:50:59,489 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:50:59,512 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-27 19:50:59,513 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-27 19:50:59,516 INFO L87 Difference]: Start difference. First operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:59,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:50:59,658 INFO L93 Difference]: Finished difference Result 90 states and 123 transitions. [2024-11-27 19:50:59,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-27 19:50:59,661 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-27 19:50:59,662 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:50:59,669 INFO L225 Difference]: With dead ends: 90 [2024-11-27 19:50:59,669 INFO L226 Difference]: Without dead ends: 42 [2024-11-27 19:50:59,673 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 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-27 19:50:59,677 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 7 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 19:50:59,678 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 96 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 19:50:59,693 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-27 19:50:59,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2024-11-27 19:50:59,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:50:59,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 47 transitions. [2024-11-27 19:50:59,725 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 47 transitions. Word has length 11 [2024-11-27 19:50:59,726 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:50:59,726 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 47 transitions. [2024-11-27 19:50:59,726 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:50:59,726 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 47 transitions. [2024-11-27 19:50:59,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-27 19:50:59,728 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:50:59,728 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:50:59,741 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-27 19:50:59,929 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:59,929 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:50:59,930 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:50:59,930 INFO L85 PathProgramCache]: Analyzing trace with hash 1301222473, now seen corresponding path program 1 times [2024-11-27 19:50:59,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:50:59,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2050908837] [2024-11-27 19:50:59,931 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:50:59,931 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:50:59,931 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:50:59,933 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:50:59,935 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-27 19:51:00,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:51:00,027 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-27 19:51:00,030 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:51:00,119 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-27 19:51:00,123 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-27 19:51:00,123 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:51:00,123 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2050908837] [2024-11-27 19:51:00,123 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2050908837] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-27 19:51:00,123 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-27 19:51:00,123 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-27 19:51:00,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [911522687] [2024-11-27 19:51:00,124 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-27 19:51:00,125 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-27 19:51:00,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:51:00,128 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-27 19:51:00,128 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-27 19:51:00,129 INFO L87 Difference]: Start difference. First operand 39 states and 47 transitions. Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:51:00,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:51:00,242 INFO L93 Difference]: Finished difference Result 55 states and 68 transitions. [2024-11-27 19:51:00,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-27 19:51:00,243 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2024-11-27 19:51:00,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:51:00,244 INFO L225 Difference]: With dead ends: 55 [2024-11-27 19:51:00,244 INFO L226 Difference]: Without dead ends: 41 [2024-11-27 19:51:00,245 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 11 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-27 19:51:00,246 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 4 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-27 19:51:00,246 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 79 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-27 19:51:00,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-27 19:51:00,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2024-11-27 19:51:00,254 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:51:00,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2024-11-27 19:51:00,255 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 13 [2024-11-27 19:51:00,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:51:00,256 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2024-11-27 19:51:00,256 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:51:00,256 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2024-11-27 19:51:00,257 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-27 19:51:00,257 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:51:00,257 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:51:00,268 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-27 19:51:00,457 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:51:00,458 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:51:00,458 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:51:00,459 INFO L85 PathProgramCache]: Analyzing trace with hash 299954435, now seen corresponding path program 1 times [2024-11-27 19:51:00,459 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:51:00,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1782982356] [2024-11-27 19:51:00,459 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:51:00,459 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:51:00,460 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:51:00,465 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:51:00,466 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-27 19:51:00,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:51:00,539 INFO L256 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-27 19:51:00,542 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:51:00,891 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:51:00,891 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:51:01,158 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:51:01,162 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:51:01,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1782982356] [2024-11-27 19:51:01,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1782982356] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:51:01,162 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:51:01,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2024-11-27 19:51:01,162 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1872779004] [2024-11-27 19:51:01,163 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:51:01,163 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-27 19:51:01,163 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:51:01,164 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-27 19:51:01,164 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-27 19:51:01,164 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 6 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:51:01,527 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:51:01,529 INFO L93 Difference]: Finished difference Result 59 states and 73 transitions. [2024-11-27 19:51:01,530 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-27 19:51:01,530 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2024-11-27 19:51:01,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:51:01,531 INFO L225 Difference]: With dead ends: 59 [2024-11-27 19:51:01,531 INFO L226 Difference]: Without dead ends: 46 [2024-11-27 19:51:01,532 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2024-11-27 19:51:01,533 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 5 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-27 19:51:01,533 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 113 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-27 19:51:01,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-27 19:51:01,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 44. [2024-11-27 19:51:01,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:51:01,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 52 transitions. [2024-11-27 19:51:01,553 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 52 transitions. Word has length 15 [2024-11-27 19:51:01,553 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:51:01,553 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 52 transitions. [2024-11-27 19:51:01,553 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:51:01,554 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 52 transitions. [2024-11-27 19:51:01,554 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-27 19:51:01,555 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:51:01,555 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:51:01,567 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-27 19:51:01,756 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:51:01,756 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:51:01,756 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:51:01,757 INFO L85 PathProgramCache]: Analyzing trace with hash 1688852343, now seen corresponding path program 1 times [2024-11-27 19:51:01,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:51:01,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1139297398] [2024-11-27 19:51:01,757 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:51:01,757 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:51:01,757 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:51:01,759 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:51:01,760 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-27 19:51:01,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:51:01,827 INFO L256 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-27 19:51:01,829 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:51:02,540 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:51:02,540 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:51:03,184 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-27 19:51:03,184 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:51:03,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1139297398] [2024-11-27 19:51:03,184 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1139297398] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:51:03,184 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:51:03,184 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2024-11-27 19:51:03,184 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1986989868] [2024-11-27 19:51:03,184 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:51:03,187 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-27 19:51:03,187 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:51:03,188 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-27 19:51:03,191 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2024-11-27 19:51:03,191 INFO L87 Difference]: Start difference. First operand 44 states and 52 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:51:04,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:51:04,200 INFO L93 Difference]: Finished difference Result 67 states and 83 transitions. [2024-11-27 19:51:04,201 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-27 19:51:04,201 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 19 [2024-11-27 19:51:04,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:51:04,202 INFO L225 Difference]: With dead ends: 67 [2024-11-27 19:51:04,203 INFO L226 Difference]: Without dead ends: 53 [2024-11-27 19:51:04,203 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=57, Invalid=99, Unknown=0, NotChecked=0, Total=156 [2024-11-27 19:51:04,204 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 7 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-27 19:51:04,205 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 185 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-27 19:51:04,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-11-27 19:51:04,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2024-11-27 19:51:04,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-27 19:51:04,217 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 62 transitions. [2024-11-27 19:51:04,217 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 62 transitions. Word has length 19 [2024-11-27 19:51:04,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:51:04,218 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 62 transitions. [2024-11-27 19:51:04,218 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:51:04,218 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 62 transitions. [2024-11-27 19:51:04,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-27 19:51:04,219 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:51:04,219 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:51:04,232 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-27 19:51:04,420 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:51:04,420 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:51:04,420 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:51:04,420 INFO L85 PathProgramCache]: Analyzing trace with hash -1417329111, now seen corresponding path program 2 times [2024-11-27 19:51:04,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:51:04,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [182260466] [2024-11-27 19:51:04,421 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-27 19:51:04,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:51:04,421 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:51:04,425 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:51:04,426 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-27 19:51:04,508 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-27 19:51:04,508 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:51:04,512 INFO L256 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-27 19:51:04,514 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:51:06,225 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-27 19:51:06,225 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:51:16,903 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-27 19:51:16,903 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:51:16,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [182260466] [2024-11-27 19:51:16,904 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [182260466] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:51:16,904 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:51:16,904 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12] total 20 [2024-11-27 19:51:16,908 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [233528683] [2024-11-27 19:51:16,908 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:51:16,909 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-27 19:51:16,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:51:16,911 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-27 19:51:16,912 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2024-11-27 19:51:16,912 INFO L87 Difference]: Start difference. First operand 52 states and 62 transitions. Second operand has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:51:29,293 WARN L286 SmtUtils]: Spent 8.20s on a formula simplification that was a NOOP. DAG size: 30 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-27 19:51:33,655 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-27 19:51:37,664 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-27 19:51:41,670 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-27 19:51:53,951 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-27 19:51:57,536 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.58s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-27 19:52:00,390 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.74s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-27 19:52:04,397 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-27 19:52:12,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:52:12,083 INFO L93 Difference]: Finished difference Result 76 states and 94 transitions. [2024-11-27 19:52:12,089 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-27 19:52:12,089 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2024-11-27 19:52:12,089 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:52:12,090 INFO L225 Difference]: With dead ends: 76 [2024-11-27 19:52:12,091 INFO L226 Difference]: Without dead ends: 73 [2024-11-27 19:52:12,091 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 31.6s TimeCoverageRelationStatistics Valid=96, Invalid=503, Unknown=1, NotChecked=0, Total=600 [2024-11-27 19:52:12,092 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 3 mSDsluCounter, 384 mSDsCounter, 0 mSdLazyCounter, 229 mSolverCounterSat, 6 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 32.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 421 SdHoareTripleChecker+Invalid, 240 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 229 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 32.6s IncrementalHoareTripleChecker+Time [2024-11-27 19:52:12,093 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 421 Invalid, 240 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 229 Invalid, 5 Unknown, 0 Unchecked, 32.6s Time] [2024-11-27 19:52:12,094 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-27 19:52:12,107 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2024-11-27 19:52:12,107 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 53 states have (on average 1.2264150943396226) internal successors, (65), 57 states have internal predecessors, (65), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-27 19:52:12,109 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 87 transitions. [2024-11-27 19:52:12,109 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 87 transitions. Word has length 23 [2024-11-27 19:52:12,109 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:52:12,109 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 87 transitions. [2024-11-27 19:52:12,110 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:52:12,110 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 87 transitions. [2024-11-27 19:52:12,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-27 19:52:12,111 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:52:12,111 INFO L218 NwaCegarLoop]: trace histogram [6, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:52:12,122 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-27 19:52:12,312 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:52:12,312 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:52:12,312 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:52:12,313 INFO L85 PathProgramCache]: Analyzing trace with hash -1196039389, now seen corresponding path program 3 times [2024-11-27 19:52:12,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:52:12,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [17521114] [2024-11-27 19:52:12,313 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-27 19:52:12,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:52:12,313 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:52:12,315 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:52:12,316 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-27 19:52:12,409 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-27 19:52:12,409 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:52:12,415 INFO L256 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-27 19:52:12,417 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:52:13,156 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 15 proven. 20 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-27 19:52:13,156 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:52:16,875 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 19 proven. 16 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-27 19:52:16,876 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:52:16,876 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [17521114] [2024-11-27 19:52:16,876 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [17521114] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:52:16,876 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:52:16,876 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 13 [2024-11-27 19:52:16,877 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [246777646] [2024-11-27 19:52:16,877 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:52:16,878 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-27 19:52:16,878 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:52:16,879 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-27 19:52:16,880 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=103, Unknown=0, NotChecked=0, Total=156 [2024-11-27 19:52:16,880 INFO L87 Difference]: Start difference. First operand 71 states and 87 transitions. Second operand has 13 states, 13 states have (on average 2.923076923076923) internal successors, (38), 13 states have internal predecessors, (38), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:52:20,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:52:20,107 INFO L93 Difference]: Finished difference Result 104 states and 132 transitions. [2024-11-27 19:52:20,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-27 19:52:20,108 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.923076923076923) internal successors, (38), 13 states have internal predecessors, (38), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 25 [2024-11-27 19:52:20,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:52:20,110 INFO L225 Difference]: With dead ends: 104 [2024-11-27 19:52:20,111 INFO L226 Difference]: Without dead ends: 74 [2024-11-27 19:52:20,111 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=96, Invalid=176, Unknown=0, NotChecked=0, Total=272 [2024-11-27 19:52:20,112 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-27 19:52:20,115 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 183 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2024-11-27 19:52:20,116 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-27 19:52:20,125 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 72. [2024-11-27 19:52:20,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 55 states have (on average 1.2363636363636363) internal successors, (68), 58 states have internal predecessors, (68), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-27 19:52:20,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 88 transitions. [2024-11-27 19:52:20,127 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 88 transitions. Word has length 25 [2024-11-27 19:52:20,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:52:20,128 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 88 transitions. [2024-11-27 19:52:20,128 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.923076923076923) internal successors, (38), 13 states have internal predecessors, (38), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:52:20,128 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 88 transitions. [2024-11-27 19:52:20,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-27 19:52:20,129 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:52:20,129 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:52:20,137 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-27 19:52:20,330 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:52:20,330 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:52:20,331 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:52:20,331 INFO L85 PathProgramCache]: Analyzing trace with hash -1889018642, now seen corresponding path program 1 times [2024-11-27 19:52:20,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:52:20,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [920829296] [2024-11-27 19:52:20,331 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:52:20,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:52:20,331 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:52:20,333 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:52:20,334 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-27 19:52:20,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-27 19:52:20,425 INFO L256 TraceCheckSpWp]: Trace formula consists of 63 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-27 19:52:20,427 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:52:22,811 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-27 19:52:22,811 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:52:48,832 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-27 19:52:48,832 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:52:48,833 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [920829296] [2024-11-27 19:52:48,833 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [920829296] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:52:48,833 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:52:48,833 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 24 [2024-11-27 19:52:48,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1918762261] [2024-11-27 19:52:48,833 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:52:48,834 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-27 19:52:48,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:52:48,835 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-27 19:52:48,835 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=472, Unknown=0, NotChecked=0, Total=552 [2024-11-27 19:52:48,836 INFO L87 Difference]: Start difference. First operand 72 states and 88 transitions. Second operand has 24 states, 20 states have (on average 2.1) internal successors, (42), 21 states have internal predecessors, (42), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-27 19:53:09,799 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:53:09,799 INFO L93 Difference]: Finished difference Result 91 states and 113 transitions. [2024-11-27 19:53:09,806 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-27 19:53:09,807 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 20 states have (on average 2.1) internal successors, (42), 21 states have internal predecessors, (42), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 28 [2024-11-27 19:53:09,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:53:09,809 INFO L225 Difference]: With dead ends: 91 [2024-11-27 19:53:09,809 INFO L226 Difference]: Without dead ends: 81 [2024-11-27 19:53:09,810 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 30.3s TimeCoverageRelationStatistics Valid=114, Invalid=642, Unknown=0, NotChecked=0, Total=756 [2024-11-27 19:53:09,811 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 460 mSDsCounter, 0 mSdLazyCounter, 343 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 492 SdHoareTripleChecker+Invalid, 352 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 343 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.1s IncrementalHoareTripleChecker+Time [2024-11-27 19:53:09,811 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 492 Invalid, 352 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 343 Invalid, 0 Unknown, 0 Unchecked, 12.1s Time] [2024-11-27 19:53:09,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-11-27 19:53:09,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 81. [2024-11-27 19:53:09,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 64 states have (on average 1.234375) internal successors, (79), 67 states have internal predecessors, (79), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-27 19:53:09,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 100 transitions. [2024-11-27 19:53:09,827 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 100 transitions. Word has length 28 [2024-11-27 19:53:09,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:53:09,827 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 100 transitions. [2024-11-27 19:53:09,828 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 20 states have (on average 2.1) internal successors, (42), 21 states have internal predecessors, (42), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-27 19:53:09,828 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 100 transitions. [2024-11-27 19:53:09,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-27 19:53:09,829 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:53:09,829 INFO L218 NwaCegarLoop]: trace histogram [7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:53:09,841 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-27 19:53:10,029 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:53:10,029 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:53:10,030 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:53:10,030 INFO L85 PathProgramCache]: Analyzing trace with hash 1268151387, now seen corresponding path program 4 times [2024-11-27 19:53:10,030 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:53:10,030 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1059906948] [2024-11-27 19:53:10,030 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-27 19:53:10,031 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:53:10,031 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-27 19:53:10,036 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-27 19:53:10,037 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-27 19:53:10,131 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-27 19:53:10,131 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-27 19:53:10,137 INFO L256 TraceCheckSpWp]: Trace formula consists of 62 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-27 19:53:10,139 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-27 19:53:11,104 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 22 proven. 25 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-27 19:53:11,104 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-27 19:53:15,599 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 25 proven. 22 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-27 19:53:15,599 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-27 19:53:15,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1059906948] [2024-11-27 19:53:15,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1059906948] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-27 19:53:15,600 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-27 19:53:15,600 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 15 [2024-11-27 19:53:15,600 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1961163404] [2024-11-27 19:53:15,600 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-27 19:53:15,600 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-27 19:53:15,601 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-27 19:53:15,601 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-27 19:53:15,601 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=141, Unknown=0, NotChecked=0, Total=210 [2024-11-27 19:53:15,602 INFO L87 Difference]: Start difference. First operand 81 states and 100 transitions. Second operand has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 15 states have internal predecessors, (40), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:53:16,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-27 19:53:16,357 INFO L93 Difference]: Finished difference Result 81 states and 100 transitions. [2024-11-27 19:53:16,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-27 19:53:16,357 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 15 states have internal predecessors, (40), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2024-11-27 19:53:16,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-27 19:53:16,358 INFO L225 Difference]: With dead ends: 81 [2024-11-27 19:53:16,358 INFO L226 Difference]: Without dead ends: 23 [2024-11-27 19:53:16,359 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=79, Invalid=161, Unknown=0, NotChecked=0, Total=240 [2024-11-27 19:53:16,359 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 0 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-27 19:53:16,360 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 157 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-27 19:53:16,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-27 19:53:16,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-27 19:53:16,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 14 states have (on average 1.0) internal successors, (14), 14 states have internal predecessors, (14), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-27 19:53:16,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2024-11-27 19:53:16,367 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 27 [2024-11-27 19:53:16,368 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-27 19:53:16,368 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2024-11-27 19:53:16,368 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 15 states have internal predecessors, (40), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-27 19:53:16,368 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2024-11-27 19:53:16,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-27 19:53:16,369 INFO L210 NwaCegarLoop]: Found error trace [2024-11-27 19:53:16,369 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-27 19:53:16,383 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-27 19:53:16,569 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-27 19:53:16,570 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-27 19:53:16,570 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-27 19:53:16,570 INFO L85 PathProgramCache]: Analyzing trace with hash -21288017, now seen corresponding path program 1 times [2024-11-27 19:53:16,571 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-27 19:53:16,571 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1310824666] [2024-11-27 19:53:16,571 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-27 19:53:16,571 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-27 19:53:16,571 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/mathsat [2024-11-27 19:53:16,573 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-27 19:53:16,575 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9650a620-6933-4a67-8ce9-23fad19f6d37/bin/uautomizer-verify-aQ6SnzHsRB/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (10)] Waiting until timeout for monitored process