./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive/gcd02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 527bcce2 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/config/AutomizerReach.xml -i ../../sv-benchmarks/c/recursive/gcd02.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx --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 5840bf8cb045a250261e3957017079dce43a53700f7c91e31c16b36d5b980e00 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-527bcce [2023-11-21 22:08:21,617 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-21 22:08:21,733 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-11-21 22:08:21,742 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-21 22:08:21,743 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-21 22:08:21,785 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-21 22:08:21,786 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-21 22:08:21,787 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-21 22:08:21,788 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-11-21 22:08:21,793 INFO L153 SettingsManager]: * Use memory slicer=true [2023-11-21 22:08:21,793 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-21 22:08:21,794 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-21 22:08:21,795 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-21 22:08:21,797 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-21 22:08:21,797 INFO L153 SettingsManager]: * Use SBE=true [2023-11-21 22:08:21,798 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-21 22:08:21,798 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-21 22:08:21,799 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-21 22:08:21,799 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-21 22:08:21,800 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-21 22:08:21,800 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-21 22:08:21,801 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-21 22:08:21,801 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-21 22:08:21,801 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-21 22:08:21,802 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-21 22:08:21,802 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-21 22:08:21,803 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-21 22:08:21,803 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-21 22:08:21,804 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-21 22:08:21,804 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-21 22:08:21,806 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-21 22:08:21,806 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-21 22:08:21,806 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-21 22:08:21,807 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-21 22:08:21,807 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-21 22:08:21,807 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-21 22:08:21,807 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-21 22:08:21,808 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-21 22:08:21,808 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-21 22:08:21,808 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-21 22:08:21,808 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-11-21 22:08:21,809 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-21 22:08:21,809 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx 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 -> 5840bf8cb045a250261e3957017079dce43a53700f7c91e31c16b36d5b980e00 [2023-11-21 22:08:22,176 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-21 22:08:22,210 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-21 22:08:22,213 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-21 22:08:22,215 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-21 22:08:22,215 INFO L274 PluginConnector]: CDTParser initialized [2023-11-21 22:08:22,217 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/../../sv-benchmarks/c/recursive/gcd02.c [2023-11-21 22:08:25,345 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-21 22:08:25,574 INFO L384 CDTParser]: Found 1 translation units. [2023-11-21 22:08:25,576 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/sv-benchmarks/c/recursive/gcd02.c [2023-11-21 22:08:25,588 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/data/1c710c579/2596aa72af2f49de813f05c39aad2588/FLAGb543a870c [2023-11-21 22:08:25,609 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/data/1c710c579/2596aa72af2f49de813f05c39aad2588 [2023-11-21 22:08:25,615 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-21 22:08:25,617 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-21 22:08:25,621 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-21 22:08:25,621 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-21 22:08:25,626 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-21 22:08:25,627 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,628 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5d2cf3be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25, skipping insertion in model container [2023-11-21 22:08:25,629 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,652 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-21 22:08:25,844 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/sv-benchmarks/c/recursive/gcd02.c[623,636] [2023-11-21 22:08:25,865 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/sv-benchmarks/c/recursive/gcd02.c[1283,1296] [2023-11-21 22:08:25,866 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-21 22:08:25,877 INFO L202 MainTranslator]: Completed pre-run [2023-11-21 22:08:25,891 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/sv-benchmarks/c/recursive/gcd02.c[623,636] [2023-11-21 22:08:25,897 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/sv-benchmarks/c/recursive/gcd02.c[1283,1296] [2023-11-21 22:08:25,897 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-21 22:08:25,916 INFO L206 MainTranslator]: Completed translation [2023-11-21 22:08:25,916 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25 WrapperNode [2023-11-21 22:08:25,916 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-21 22:08:25,918 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-21 22:08:25,918 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-21 22:08:25,918 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-21 22:08:25,926 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,934 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,957 INFO L138 Inliner]: procedures = 14, calls = 20, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 47 [2023-11-21 22:08:25,958 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-21 22:08:25,958 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-21 22:08:25,959 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-21 22:08:25,959 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-21 22:08:25,969 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,969 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,971 INFO L184 PluginConnector]: Executing the observer HeapSplitter from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,981 INFO L187 HeapSplitter]: Split 10 memory accesses to 2 slices as follows [2, 8] [2023-11-21 22:08:25,985 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,986 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,989 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,992 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,993 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,994 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:25,996 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-21 22:08:25,997 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-21 22:08:26,007 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-21 22:08:26,008 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-21 22:08:26,008 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (1/1) ... [2023-11-21 22:08:26,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-21 22:08:26,031 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:26,041 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-21 22:08:26,044 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-21 22:08:26,074 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-21 22:08:26,074 INFO L130 BoogieDeclarations]: Found specification of procedure gcd [2023-11-21 22:08:26,075 INFO L138 BoogieDeclarations]: Found implementation of procedure gcd [2023-11-21 22:08:26,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-11-21 22:08:26,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-11-21 22:08:26,075 INFO L130 BoogieDeclarations]: Found specification of procedure divides [2023-11-21 22:08:26,075 INFO L138 BoogieDeclarations]: Found implementation of procedure divides [2023-11-21 22:08:26,075 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-21 22:08:26,075 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-21 22:08:26,144 INFO L240 CfgBuilder]: Building ICFG [2023-11-21 22:08:26,147 INFO L266 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-21 22:08:26,327 INFO L281 CfgBuilder]: Performing block encoding [2023-11-21 22:08:26,355 INFO L303 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-21 22:08:26,356 INFO L308 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-21 22:08:26,357 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.11 10:08:26 BoogieIcfgContainer [2023-11-21 22:08:26,358 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-21 22:08:26,361 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-21 22:08:26,361 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-21 22:08:26,365 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-21 22:08:26,365 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.11 10:08:25" (1/3) ... [2023-11-21 22:08:26,366 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@138816cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.11 10:08:26, skipping insertion in model container [2023-11-21 22:08:26,366 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 10:08:25" (2/3) ... [2023-11-21 22:08:26,366 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@138816cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.11 10:08:26, skipping insertion in model container [2023-11-21 22:08:26,367 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.11 10:08:26" (3/3) ... [2023-11-21 22:08:26,368 INFO L112 eAbstractionObserver]: Analyzing ICFG gcd02.c [2023-11-21 22:08:26,388 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-21 22:08:26,389 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2023-11-21 22:08:26,445 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-21 22:08:26,451 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@199b9c18, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-21 22:08:26,452 INFO L358 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2023-11-21 22:08:26,457 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 22 states have (on average 1.5) internal successors, (33), 24 states have internal predecessors, (33), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-21 22:08:26,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2023-11-21 22:08:26,463 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:26,463 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:26,464 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting gcdErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:26,468 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:26,469 INFO L85 PathProgramCache]: Analyzing trace with hash 192890080, now seen corresponding path program 1 times [2023-11-21 22:08:26,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:26,477 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1412789486] [2023-11-21 22:08:26,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:26,477 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:26,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:26,813 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-21 22:08:26,814 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:26,814 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1412789486] [2023-11-21 22:08:26,815 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1412789486] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-21 22:08:26,816 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-21 22:08:26,816 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-21 22:08:26,818 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023213537] [2023-11-21 22:08:26,819 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-21 22:08:26,824 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-21 22:08:26,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:26,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-21 22:08:26,858 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-21 22:08:26,861 INFO L87 Difference]: Start difference. First operand has 32 states, 22 states have (on average 1.5) internal successors, (33), 24 states have internal predecessors, (33), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 5 states have internal predecessors, (7), 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) [2023-11-21 22:08:27,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:27,155 INFO L93 Difference]: Finished difference Result 71 states and 98 transitions. [2023-11-21 22:08:27,156 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-21 22:08:27,158 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 5 states have internal predecessors, (7), 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 8 [2023-11-21 22:08:27,158 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:27,166 INFO L225 Difference]: With dead ends: 71 [2023-11-21 22:08:27,166 INFO L226 Difference]: Without dead ends: 40 [2023-11-21 22:08:27,170 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2023-11-21 22:08:27,174 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 30 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 63 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 63 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:27,175 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 116 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-21 22:08:27,194 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2023-11-21 22:08:27,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2023-11-21 22:08:27,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 28 states have (on average 1.25) internal successors, (35), 29 states have internal predecessors, (35), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-11-21 22:08:27,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 49 transitions. [2023-11-21 22:08:27,220 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 49 transitions. Word has length 8 [2023-11-21 22:08:27,220 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:27,220 INFO L495 AbstractCegarLoop]: Abstraction has 40 states and 49 transitions. [2023-11-21 22:08:27,221 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 5 states have internal predecessors, (7), 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) [2023-11-21 22:08:27,221 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 49 transitions. [2023-11-21 22:08:27,222 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2023-11-21 22:08:27,222 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:27,222 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:27,223 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-21 22:08:27,223 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting gcdErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:27,224 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:27,224 INFO L85 PathProgramCache]: Analyzing trace with hash -344313825, now seen corresponding path program 1 times [2023-11-21 22:08:27,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:27,225 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350622469] [2023-11-21 22:08:27,225 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:27,225 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:27,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:27,406 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-21 22:08:27,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:27,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350622469] [2023-11-21 22:08:27,407 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [350622469] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-21 22:08:27,408 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-21 22:08:27,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-21 22:08:27,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1615779438] [2023-11-21 22:08:27,408 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-21 22:08:27,410 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-21 22:08:27,410 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:27,411 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-21 22:08:27,411 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2023-11-21 22:08:27,412 INFO L87 Difference]: Start difference. First operand 40 states and 49 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 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) [2023-11-21 22:08:27,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:27,513 INFO L93 Difference]: Finished difference Result 58 states and 74 transitions. [2023-11-21 22:08:27,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-21 22:08:27,514 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 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 13 [2023-11-21 22:08:27,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:27,517 INFO L225 Difference]: With dead ends: 58 [2023-11-21 22:08:27,518 INFO L226 Difference]: Without dead ends: 56 [2023-11-21 22:08:27,518 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2023-11-21 22:08:27,520 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 21 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:27,521 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 97 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-21 22:08:27,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2023-11-21 22:08:27,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 50. [2023-11-21 22:08:27,536 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 36 states have internal predecessors, (44), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-21 22:08:27,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 62 transitions. [2023-11-21 22:08:27,538 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 62 transitions. Word has length 13 [2023-11-21 22:08:27,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:27,539 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 62 transitions. [2023-11-21 22:08:27,539 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 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) [2023-11-21 22:08:27,540 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2023-11-21 22:08:27,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2023-11-21 22:08:27,541 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:27,541 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:27,541 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-21 22:08:27,542 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting gcdErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:27,542 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:27,542 INFO L85 PathProgramCache]: Analyzing trace with hash -341483680, now seen corresponding path program 1 times [2023-11-21 22:08:27,543 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:27,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [493852716] [2023-11-21 22:08:27,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:27,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:27,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:27,710 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-21 22:08:27,711 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:27,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [493852716] [2023-11-21 22:08:27,712 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [493852716] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-21 22:08:27,712 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-21 22:08:27,712 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2023-11-21 22:08:27,712 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1836570775] [2023-11-21 22:08:27,713 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-21 22:08:27,713 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-21 22:08:27,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:27,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-21 22:08:27,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2023-11-21 22:08:27,715 INFO L87 Difference]: Start difference. First operand 50 states and 62 transitions. Second operand has 7 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 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) [2023-11-21 22:08:27,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:27,900 INFO L93 Difference]: Finished difference Result 62 states and 82 transitions. [2023-11-21 22:08:27,901 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-21 22:08:27,902 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 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 13 [2023-11-21 22:08:27,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:27,904 INFO L225 Difference]: With dead ends: 62 [2023-11-21 22:08:27,904 INFO L226 Difference]: Without dead ends: 60 [2023-11-21 22:08:27,905 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=65, Unknown=0, NotChecked=0, Total=110 [2023-11-21 22:08:27,906 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 21 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:27,907 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 154 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-21 22:08:27,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2023-11-21 22:08:27,927 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 48. [2023-11-21 22:08:27,932 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 34 states have internal predecessors, (42), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-21 22:08:27,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 60 transitions. [2023-11-21 22:08:27,937 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 60 transitions. Word has length 13 [2023-11-21 22:08:27,938 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:27,938 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 60 transitions. [2023-11-21 22:08:27,939 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 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) [2023-11-21 22:08:27,939 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 60 transitions. [2023-11-21 22:08:27,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-11-21 22:08:27,942 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:27,943 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:27,943 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-21 22:08:27,943 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:27,944 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:27,944 INFO L85 PathProgramCache]: Analyzing trace with hash -205465366, now seen corresponding path program 1 times [2023-11-21 22:08:27,945 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:27,945 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1782138234] [2023-11-21 22:08:27,945 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:27,945 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:27,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,054 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:28,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,059 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2023-11-21 22:08:28,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,082 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-21 22:08:28,082 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:28,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1782138234] [2023-11-21 22:08:28,082 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1782138234] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-21 22:08:28,083 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-21 22:08:28,083 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-21 22:08:28,083 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1149260023] [2023-11-21 22:08:28,083 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-21 22:08:28,084 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-21 22:08:28,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:28,085 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-21 22:08:28,085 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-21 22:08:28,085 INFO L87 Difference]: Start difference. First operand 48 states and 60 transitions. Second operand has 4 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-21 22:08:28,104 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:28,104 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2023-11-21 22:08:28,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-21 22:08:28,105 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2023-11-21 22:08:28,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:28,106 INFO L225 Difference]: With dead ends: 54 [2023-11-21 22:08:28,107 INFO L226 Difference]: Without dead ends: 50 [2023-11-21 22:08:28,111 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-21 22:08:28,113 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:28,114 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 92 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-21 22:08:28,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2023-11-21 22:08:28,125 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2023-11-21 22:08:28,125 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 36 states have internal predecessors, (43), 9 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2023-11-21 22:08:28,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 62 transitions. [2023-11-21 22:08:28,127 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 62 transitions. Word has length 19 [2023-11-21 22:08:28,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:28,127 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 62 transitions. [2023-11-21 22:08:28,128 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-21 22:08:28,128 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2023-11-21 22:08:28,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2023-11-21 22:08:28,129 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:28,130 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:28,130 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-21 22:08:28,130 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:28,131 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:28,131 INFO L85 PathProgramCache]: Analyzing trace with hash -1363529512, now seen corresponding path program 1 times [2023-11-21 22:08:28,131 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:28,131 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1768191273] [2023-11-21 22:08:28,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:28,132 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:28,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,283 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:28,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,369 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2023-11-21 22:08:28,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,439 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-21 22:08:28,439 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:28,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1768191273] [2023-11-21 22:08:28,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1768191273] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-21 22:08:28,441 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-21 22:08:28,441 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2023-11-21 22:08:28,441 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1606366024] [2023-11-21 22:08:28,442 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-21 22:08:28,443 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-21 22:08:28,443 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:28,444 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-21 22:08:28,445 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2023-11-21 22:08:28,446 INFO L87 Difference]: Start difference. First operand 50 states and 62 transitions. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-21 22:08:28,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:28,607 INFO L93 Difference]: Finished difference Result 68 states and 85 transitions. [2023-11-21 22:08:28,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-21 22:08:28,608 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2023-11-21 22:08:28,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:28,614 INFO L225 Difference]: With dead ends: 68 [2023-11-21 22:08:28,614 INFO L226 Difference]: Without dead ends: 64 [2023-11-21 22:08:28,615 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2023-11-21 22:08:28,619 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 16 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:28,619 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 94 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-21 22:08:28,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-11-21 22:08:28,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 56. [2023-11-21 22:08:28,648 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 38 states have (on average 1.2105263157894737) internal successors, (46), 41 states have internal predecessors, (46), 10 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (14), 10 states have call predecessors, (14), 10 states have call successors, (14) [2023-11-21 22:08:28,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 70 transitions. [2023-11-21 22:08:28,653 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 70 transitions. Word has length 20 [2023-11-21 22:08:28,653 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:28,653 INFO L495 AbstractCegarLoop]: Abstraction has 56 states and 70 transitions. [2023-11-21 22:08:28,653 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-21 22:08:28,654 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 70 transitions. [2023-11-21 22:08:28,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-11-21 22:08:28,661 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:28,661 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:28,662 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-11-21 22:08:28,662 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:28,663 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:28,663 INFO L85 PathProgramCache]: Analyzing trace with hash 1456991186, now seen corresponding path program 1 times [2023-11-21 22:08:28,663 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:28,663 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1441146266] [2023-11-21 22:08:28,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:28,664 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:28,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,743 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:28,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,750 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2023-11-21 22:08:28,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,801 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:28,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,827 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-21 22:08:28,827 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:28,827 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1441146266] [2023-11-21 22:08:28,827 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1441146266] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-21 22:08:28,828 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-21 22:08:28,829 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-21 22:08:28,829 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [388704489] [2023-11-21 22:08:28,834 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-21 22:08:28,835 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-21 22:08:28,835 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:28,836 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-21 22:08:28,836 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-21 22:08:28,837 INFO L87 Difference]: Start difference. First operand 56 states and 70 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-21 22:08:28,863 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:28,863 INFO L93 Difference]: Finished difference Result 63 states and 78 transitions. [2023-11-21 22:08:28,864 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-21 22:08:28,864 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) Word has length 26 [2023-11-21 22:08:28,864 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:28,865 INFO L225 Difference]: With dead ends: 63 [2023-11-21 22:08:28,865 INFO L226 Difference]: Without dead ends: 54 [2023-11-21 22:08:28,866 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-21 22:08:28,867 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:28,867 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 121 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-21 22:08:28,868 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2023-11-21 22:08:28,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2023-11-21 22:08:28,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 39 states have internal predecessors, (44), 10 states have call successors, (10), 4 states have call predecessors, (10), 6 states have return successors, (13), 10 states have call predecessors, (13), 10 states have call successors, (13) [2023-11-21 22:08:28,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 67 transitions. [2023-11-21 22:08:28,880 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 67 transitions. Word has length 26 [2023-11-21 22:08:28,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:28,880 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 67 transitions. [2023-11-21 22:08:28,881 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-21 22:08:28,881 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 67 transitions. [2023-11-21 22:08:28,882 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-11-21 22:08:28,882 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:28,882 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:28,883 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-11-21 22:08:28,883 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:28,883 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:28,883 INFO L85 PathProgramCache]: Analyzing trace with hash 1678448864, now seen corresponding path program 1 times [2023-11-21 22:08:28,884 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:28,884 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [760494982] [2023-11-21 22:08:28,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:28,884 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:28,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,959 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:28,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:28,979 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2023-11-21 22:08:28,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:29,034 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:29,037 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:29,119 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-21 22:08:29,119 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:29,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [760494982] [2023-11-21 22:08:29,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [760494982] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:29,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1519207168] [2023-11-21 22:08:29,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:29,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:29,121 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:29,125 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:29,173 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-21 22:08:29,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:29,242 INFO L262 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-21 22:08:29,248 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:29,371 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-21 22:08:29,372 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:29,593 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-21 22:08:29,594 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1519207168] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:29,594 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:29,594 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 10] total 14 [2023-11-21 22:08:29,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [751050264] [2023-11-21 22:08:29,595 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:29,595 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-21 22:08:29,596 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:29,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-21 22:08:29,597 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2023-11-21 22:08:29,597 INFO L87 Difference]: Start difference. First operand 54 states and 67 transitions. Second operand has 14 states, 13 states have (on average 2.230769230769231) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 1 states have call predecessors, (4), 3 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-21 22:08:29,755 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:29,755 INFO L93 Difference]: Finished difference Result 62 states and 78 transitions. [2023-11-21 22:08:29,756 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-21 22:08:29,756 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.230769230769231) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 1 states have call predecessors, (4), 3 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) Word has length 27 [2023-11-21 22:08:29,756 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:29,757 INFO L225 Difference]: With dead ends: 62 [2023-11-21 22:08:29,757 INFO L226 Difference]: Without dead ends: 54 [2023-11-21 22:08:29,758 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 55 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=212, Unknown=0, NotChecked=0, Total=272 [2023-11-21 22:08:29,759 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 21 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:29,759 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 120 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-21 22:08:29,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2023-11-21 22:08:29,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 48. [2023-11-21 22:08:29,769 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 34 states have (on average 1.1764705882352942) internal successors, (40), 34 states have internal predecessors, (40), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-21 22:08:29,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 58 transitions. [2023-11-21 22:08:29,770 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 58 transitions. Word has length 27 [2023-11-21 22:08:29,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:29,770 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 58 transitions. [2023-11-21 22:08:29,771 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.230769230769231) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 1 states have call predecessors, (4), 3 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-21 22:08:29,771 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 58 transitions. [2023-11-21 22:08:29,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-11-21 22:08:29,772 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:29,772 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:29,799 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:29,985 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-21 22:08:29,986 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:29,986 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:29,986 INFO L85 PathProgramCache]: Analyzing trace with hash -1626959476, now seen corresponding path program 1 times [2023-11-21 22:08:29,986 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:29,986 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1729167954] [2023-11-21 22:08:29,986 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:29,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:29,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:30,056 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:30,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:30,141 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:30,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:30,192 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2023-11-21 22:08:30,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:30,244 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-21 22:08:30,245 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:30,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1729167954] [2023-11-21 22:08:30,245 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1729167954] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:30,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1384560725] [2023-11-21 22:08:30,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:30,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:30,246 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:30,247 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:30,269 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-21 22:08:30,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:30,315 INFO L262 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 15 conjunts are in the unsatisfiable core [2023-11-21 22:08:30,318 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:30,475 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-21 22:08:30,475 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:30,877 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-21 22:08:30,877 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1384560725] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:30,878 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:30,878 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 21 [2023-11-21 22:08:30,878 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1603700400] [2023-11-21 22:08:30,878 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:30,879 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-11-21 22:08:30,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:30,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-11-21 22:08:30,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=361, Unknown=0, NotChecked=0, Total=420 [2023-11-21 22:08:30,880 INFO L87 Difference]: Start difference. First operand 48 states and 58 transitions. Second operand has 21 states, 19 states have (on average 2.1052631578947367) internal successors, (40), 17 states have internal predecessors, (40), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2023-11-21 22:08:31,155 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:31,155 INFO L93 Difference]: Finished difference Result 73 states and 92 transitions. [2023-11-21 22:08:31,156 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-21 22:08:31,157 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.1052631578947367) internal successors, (40), 17 states have internal predecessors, (40), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) Word has length 28 [2023-11-21 22:08:31,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:31,158 INFO L225 Difference]: With dead ends: 73 [2023-11-21 22:08:31,158 INFO L226 Difference]: Without dead ends: 69 [2023-11-21 22:08:31,159 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 46 SyntacticMatches, 4 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=95, Invalid=505, Unknown=0, NotChecked=0, Total=600 [2023-11-21 22:08:31,160 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 24 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 311 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 317 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 311 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:31,160 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 220 Invalid, 317 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 311 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-21 22:08:31,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2023-11-21 22:08:31,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 58. [2023-11-21 22:08:31,172 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 40 states have (on average 1.15) internal successors, (46), 41 states have internal predecessors, (46), 10 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (16), 12 states have call predecessors, (16), 10 states have call successors, (16) [2023-11-21 22:08:31,173 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 72 transitions. [2023-11-21 22:08:31,174 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 72 transitions. Word has length 28 [2023-11-21 22:08:31,174 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:31,174 INFO L495 AbstractCegarLoop]: Abstraction has 58 states and 72 transitions. [2023-11-21 22:08:31,175 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.1052631578947367) internal successors, (40), 17 states have internal predecessors, (40), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2023-11-21 22:08:31,175 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 72 transitions. [2023-11-21 22:08:31,176 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-11-21 22:08:31,176 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:31,176 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:31,201 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:31,389 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:31,390 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:31,390 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:31,390 INFO L85 PathProgramCache]: Analyzing trace with hash -2138734868, now seen corresponding path program 1 times [2023-11-21 22:08:31,390 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:31,390 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [71553574] [2023-11-21 22:08:31,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:31,390 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:31,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:31,457 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:31,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:31,533 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:31,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:31,565 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2023-11-21 22:08:31,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:31,605 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-21 22:08:31,605 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:31,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [71553574] [2023-11-21 22:08:31,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [71553574] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-21 22:08:31,606 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-21 22:08:31,606 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2023-11-21 22:08:31,606 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1678622108] [2023-11-21 22:08:31,606 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-21 22:08:31,607 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-21 22:08:31,607 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:31,608 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-21 22:08:31,608 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2023-11-21 22:08:31,608 INFO L87 Difference]: Start difference. First operand 58 states and 72 transitions. Second operand has 9 states, 8 states have (on average 2.375) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-21 22:08:31,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:31,758 INFO L93 Difference]: Finished difference Result 79 states and 99 transitions. [2023-11-21 22:08:31,758 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-21 22:08:31,759 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.375) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 28 [2023-11-21 22:08:31,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:31,760 INFO L225 Difference]: With dead ends: 79 [2023-11-21 22:08:31,761 INFO L226 Difference]: Without dead ends: 75 [2023-11-21 22:08:31,761 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-11-21 22:08:31,763 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 15 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 166 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:31,764 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 108 Invalid, 166 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-21 22:08:31,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2023-11-21 22:08:31,783 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 62. [2023-11-21 22:08:31,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 43 states have (on average 1.1395348837209303) internal successors, (49), 43 states have internal predecessors, (49), 10 states have call successors, (10), 4 states have call predecessors, (10), 8 states have return successors, (19), 14 states have call predecessors, (19), 10 states have call successors, (19) [2023-11-21 22:08:31,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2023-11-21 22:08:31,786 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 28 [2023-11-21 22:08:31,786 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:31,786 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2023-11-21 22:08:31,787 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.375) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-21 22:08:31,787 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2023-11-21 22:08:31,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-11-21 22:08:31,790 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:31,790 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:31,790 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2023-11-21 22:08:31,791 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:31,791 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:31,791 INFO L85 PathProgramCache]: Analyzing trace with hash 1097221548, now seen corresponding path program 1 times [2023-11-21 22:08:31,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:31,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1556726855] [2023-11-21 22:08:31,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:31,792 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:31,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:31,912 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:31,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:31,990 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:31,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:32,035 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2023-11-21 22:08:32,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:32,093 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:32,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:32,125 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-21 22:08:32,125 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:32,125 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1556726855] [2023-11-21 22:08:32,125 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1556726855] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:32,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2098426237] [2023-11-21 22:08:32,126 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:32,126 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:32,126 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:32,127 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:32,153 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-21 22:08:32,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:32,195 INFO L262 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 21 conjunts are in the unsatisfiable core [2023-11-21 22:08:32,197 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:32,390 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-21 22:08:32,391 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:33,174 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-21 22:08:33,174 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2098426237] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:33,174 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:33,174 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 13] total 21 [2023-11-21 22:08:33,175 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [443113421] [2023-11-21 22:08:33,175 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:33,177 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-11-21 22:08:33,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:33,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-11-21 22:08:33,179 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=360, Unknown=0, NotChecked=0, Total=420 [2023-11-21 22:08:33,180 INFO L87 Difference]: Start difference. First operand 62 states and 78 transitions. Second operand has 21 states, 20 states have (on average 2.55) internal successors, (51), 19 states have internal predecessors, (51), 8 states have call successors, (8), 1 states have call predecessors, (8), 6 states have return successors, (8), 4 states have call predecessors, (8), 8 states have call successors, (8) [2023-11-21 22:08:33,522 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:33,522 INFO L93 Difference]: Finished difference Result 88 states and 114 transitions. [2023-11-21 22:08:33,522 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-21 22:08:33,523 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.55) internal successors, (51), 19 states have internal predecessors, (51), 8 states have call successors, (8), 1 states have call predecessors, (8), 6 states have return successors, (8), 4 states have call predecessors, (8), 8 states have call successors, (8) Word has length 35 [2023-11-21 22:08:33,523 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:33,524 INFO L225 Difference]: With dead ends: 88 [2023-11-21 22:08:33,524 INFO L226 Difference]: Without dead ends: 84 [2023-11-21 22:08:33,525 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 60 SyntacticMatches, 6 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=103, Invalid=547, Unknown=0, NotChecked=0, Total=650 [2023-11-21 22:08:33,526 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 37 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 351 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 363 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 351 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:33,526 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 245 Invalid, 363 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 351 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-21 22:08:33,527 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2023-11-21 22:08:33,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 72. [2023-11-21 22:08:33,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 49 states have (on average 1.1224489795918366) internal successors, (55), 50 states have internal predecessors, (55), 11 states have call successors, (11), 4 states have call predecessors, (11), 11 states have return successors, (27), 17 states have call predecessors, (27), 11 states have call successors, (27) [2023-11-21 22:08:33,539 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 93 transitions. [2023-11-21 22:08:33,539 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 93 transitions. Word has length 35 [2023-11-21 22:08:33,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:33,540 INFO L495 AbstractCegarLoop]: Abstraction has 72 states and 93 transitions. [2023-11-21 22:08:33,540 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.55) internal successors, (51), 19 states have internal predecessors, (51), 8 states have call successors, (8), 1 states have call predecessors, (8), 6 states have return successors, (8), 4 states have call predecessors, (8), 8 states have call successors, (8) [2023-11-21 22:08:33,540 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 93 transitions. [2023-11-21 22:08:33,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-11-21 22:08:33,541 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:33,542 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:33,576 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:33,765 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-21 22:08:33,766 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:33,766 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:33,767 INFO L85 PathProgramCache]: Analyzing trace with hash -1054634932, now seen corresponding path program 1 times [2023-11-21 22:08:33,767 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:33,767 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [117572570] [2023-11-21 22:08:33,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:33,767 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:33,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:33,864 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:33,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:33,914 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:33,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:33,931 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2023-11-21 22:08:33,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:33,989 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:33,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:34,077 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-21 22:08:34,077 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:34,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [117572570] [2023-11-21 22:08:34,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [117572570] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:34,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [685783819] [2023-11-21 22:08:34,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:34,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:34,079 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:34,080 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:34,117 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-21 22:08:34,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:34,160 INFO L262 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-21 22:08:34,162 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:34,250 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-21 22:08:34,251 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:34,463 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-21 22:08:34,463 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [685783819] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:34,463 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:34,464 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 11] total 15 [2023-11-21 22:08:34,464 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [90658255] [2023-11-21 22:08:34,464 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:34,465 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-21 22:08:34,465 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:34,466 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-21 22:08:34,466 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2023-11-21 22:08:34,466 INFO L87 Difference]: Start difference. First operand 72 states and 93 transitions. Second operand has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-21 22:08:34,670 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:34,671 INFO L93 Difference]: Finished difference Result 83 states and 107 transitions. [2023-11-21 22:08:34,671 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-21 22:08:34,672 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Word has length 35 [2023-11-21 22:08:34,674 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:34,675 INFO L225 Difference]: With dead ends: 83 [2023-11-21 22:08:34,675 INFO L226 Difference]: Without dead ends: 74 [2023-11-21 22:08:34,676 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2023-11-21 22:08:34,676 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 22 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 212 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 212 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:34,677 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 139 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 212 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-21 22:08:34,677 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2023-11-21 22:08:34,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2023-11-21 22:08:34,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 48 states have (on average 1.125) internal successors, (54), 50 states have internal predecessors, (54), 11 states have call successors, (11), 4 states have call predecessors, (11), 11 states have return successors, (26), 16 states have call predecessors, (26), 11 states have call successors, (26) [2023-11-21 22:08:34,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 91 transitions. [2023-11-21 22:08:34,689 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 91 transitions. Word has length 35 [2023-11-21 22:08:34,689 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:34,689 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 91 transitions. [2023-11-21 22:08:34,690 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-21 22:08:34,690 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 91 transitions. [2023-11-21 22:08:34,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-21 22:08:34,694 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:34,694 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:34,719 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:34,917 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-11-21 22:08:34,918 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:34,918 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:34,918 INFO L85 PathProgramCache]: Analyzing trace with hash 2077305336, now seen corresponding path program 1 times [2023-11-21 22:08:34,919 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:34,919 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [620820451] [2023-11-21 22:08:34,919 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:34,919 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:34,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:35,040 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:35,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:35,157 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:35,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:35,323 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:35,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:35,354 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2023-11-21 22:08:35,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:35,411 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-21 22:08:35,411 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:35,411 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [620820451] [2023-11-21 22:08:35,411 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [620820451] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:35,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [34162967] [2023-11-21 22:08:35,412 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:35,412 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:35,412 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:35,414 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:35,418 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-21 22:08:35,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:35,493 INFO L262 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-21 22:08:35,500 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:35,840 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-21 22:08:35,841 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:36,940 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-21 22:08:36,940 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [34162967] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:36,941 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:36,941 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 16] total 39 [2023-11-21 22:08:36,943 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1634662975] [2023-11-21 22:08:36,943 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:36,945 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2023-11-21 22:08:36,945 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:36,946 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2023-11-21 22:08:36,947 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=138, Invalid=1344, Unknown=0, NotChecked=0, Total=1482 [2023-11-21 22:08:36,947 INFO L87 Difference]: Start difference. First operand 71 states and 91 transitions. Second operand has 39 states, 32 states have (on average 1.875) internal successors, (60), 31 states have internal predecessors, (60), 9 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) [2023-11-21 22:08:37,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:37,724 INFO L93 Difference]: Finished difference Result 102 states and 133 transitions. [2023-11-21 22:08:37,724 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-11-21 22:08:37,725 INFO L78 Accepts]: Start accepts. Automaton has has 39 states, 32 states have (on average 1.875) internal successors, (60), 31 states have internal predecessors, (60), 9 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) Word has length 36 [2023-11-21 22:08:37,726 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:37,727 INFO L225 Difference]: With dead ends: 102 [2023-11-21 22:08:37,727 INFO L226 Difference]: Without dead ends: 98 [2023-11-21 22:08:37,729 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 50 SyntacticMatches, 4 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 586 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=351, Invalid=2199, Unknown=0, NotChecked=0, Total=2550 [2023-11-21 22:08:37,730 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 50 mSDsluCounter, 366 mSDsCounter, 0 mSdLazyCounter, 677 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 390 SdHoareTripleChecker+Invalid, 716 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 677 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:37,730 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 390 Invalid, 716 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 677 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-21 22:08:37,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2023-11-21 22:08:37,743 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 67. [2023-11-21 22:08:37,744 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 45 states have (on average 1.1333333333333333) internal successors, (51), 48 states have internal predecessors, (51), 11 states have call successors, (11), 4 states have call predecessors, (11), 10 states have return successors, (23), 14 states have call predecessors, (23), 11 states have call successors, (23) [2023-11-21 22:08:37,745 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 85 transitions. [2023-11-21 22:08:37,746 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 85 transitions. Word has length 36 [2023-11-21 22:08:37,746 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:37,746 INFO L495 AbstractCegarLoop]: Abstraction has 67 states and 85 transitions. [2023-11-21 22:08:37,746 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 39 states, 32 states have (on average 1.875) internal successors, (60), 31 states have internal predecessors, (60), 9 states have call successors, (9), 1 states have call predecessors, (9), 9 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) [2023-11-21 22:08:37,746 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 85 transitions. [2023-11-21 22:08:37,748 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-11-21 22:08:37,748 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:37,749 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:37,769 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:37,968 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-11-21 22:08:37,969 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:37,969 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:37,969 INFO L85 PathProgramCache]: Analyzing trace with hash 511799736, now seen corresponding path program 2 times [2023-11-21 22:08:37,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:37,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [765288335] [2023-11-21 22:08:37,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:37,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:37,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:38,078 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:38,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:38,170 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:38,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:38,238 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:38,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:38,262 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2023-11-21 22:08:38,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:38,310 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-21 22:08:38,310 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:38,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [765288335] [2023-11-21 22:08:38,311 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [765288335] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:38,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1210852440] [2023-11-21 22:08:38,311 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-21 22:08:38,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:38,311 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:38,312 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:38,337 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-21 22:08:38,387 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-21 22:08:38,387 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:08:38,389 INFO L262 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 20 conjunts are in the unsatisfiable core [2023-11-21 22:08:38,391 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:38,521 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-11-21 22:08:38,522 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:39,251 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-21 22:08:39,251 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1210852440] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:39,252 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:39,252 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 15] total 23 [2023-11-21 22:08:39,252 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [734769285] [2023-11-21 22:08:39,252 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:39,253 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-11-21 22:08:39,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:39,255 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-11-21 22:08:39,256 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=448, Unknown=0, NotChecked=0, Total=506 [2023-11-21 22:08:39,256 INFO L87 Difference]: Start difference. First operand 67 states and 85 transitions. Second operand has 23 states, 20 states have (on average 2.3) internal successors, (46), 18 states have internal predecessors, (46), 8 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 8 states have call successors, (9) [2023-11-21 22:08:39,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:39,708 INFO L93 Difference]: Finished difference Result 80 states and 104 transitions. [2023-11-21 22:08:39,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-21 22:08:39,708 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 20 states have (on average 2.3) internal successors, (46), 18 states have internal predecessors, (46), 8 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 8 states have call successors, (9) Word has length 36 [2023-11-21 22:08:39,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:39,709 INFO L225 Difference]: With dead ends: 80 [2023-11-21 22:08:39,710 INFO L226 Difference]: Without dead ends: 76 [2023-11-21 22:08:39,711 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 61 SyntacticMatches, 7 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=172, Invalid=950, Unknown=0, NotChecked=0, Total=1122 [2023-11-21 22:08:39,711 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 43 mSDsluCounter, 195 mSDsCounter, 0 mSdLazyCounter, 377 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 412 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 377 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:39,712 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 212 Invalid, 412 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 377 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-21 22:08:39,712 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2023-11-21 22:08:39,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 63. [2023-11-21 22:08:39,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 43 states have (on average 1.1395348837209303) internal successors, (49), 45 states have internal predecessors, (49), 10 states have call successors, (10), 4 states have call predecessors, (10), 9 states have return successors, (19), 13 states have call predecessors, (19), 10 states have call successors, (19) [2023-11-21 22:08:39,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 78 transitions. [2023-11-21 22:08:39,723 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 78 transitions. Word has length 36 [2023-11-21 22:08:39,724 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:39,724 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 78 transitions. [2023-11-21 22:08:39,724 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 20 states have (on average 2.3) internal successors, (46), 18 states have internal predecessors, (46), 8 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 8 states have call successors, (9) [2023-11-21 22:08:39,724 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 78 transitions. [2023-11-21 22:08:39,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-21 22:08:39,725 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:39,725 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:39,752 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:39,940 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-11-21 22:08:39,941 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:39,941 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:39,941 INFO L85 PathProgramCache]: Analyzing trace with hash -2085961572, now seen corresponding path program 2 times [2023-11-21 22:08:39,947 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:39,947 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1080624535] [2023-11-21 22:08:39,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:39,948 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:39,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:40,149 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:40,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:40,245 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:40,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:40,323 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:40,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:40,365 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2023-11-21 22:08:40,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:40,461 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:40,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:40,509 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:40,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:40,544 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 6 proven. 14 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-21 22:08:40,544 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:40,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1080624535] [2023-11-21 22:08:40,545 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1080624535] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:40,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705472144] [2023-11-21 22:08:40,545 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-21 22:08:40,545 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:40,545 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:40,547 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:40,573 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-21 22:08:40,652 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-21 22:08:40,652 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:08:40,654 INFO L262 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-21 22:08:40,658 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:40,923 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 6 proven. 14 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-21 22:08:40,924 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:42,864 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 29 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-21 22:08:42,865 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [705472144] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:42,865 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:42,865 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 18] total 27 [2023-11-21 22:08:42,865 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [91352207] [2023-11-21 22:08:42,865 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:42,866 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-21 22:08:42,866 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:42,867 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-21 22:08:42,867 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=625, Unknown=0, NotChecked=0, Total=702 [2023-11-21 22:08:42,868 INFO L87 Difference]: Start difference. First operand 63 states and 78 transitions. Second operand has 27 states, 26 states have (on average 2.576923076923077) internal successors, (67), 23 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) [2023-11-21 22:08:43,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:43,306 INFO L93 Difference]: Finished difference Result 93 states and 120 transitions. [2023-11-21 22:08:43,306 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-21 22:08:43,306 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 2.576923076923077) internal successors, (67), 23 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) Word has length 50 [2023-11-21 22:08:43,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:43,308 INFO L225 Difference]: With dead ends: 93 [2023-11-21 22:08:43,308 INFO L226 Difference]: Without dead ends: 89 [2023-11-21 22:08:43,311 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 88 SyntacticMatches, 9 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 177 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2023-11-21 22:08:43,311 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 85 mSDsluCounter, 295 mSDsCounter, 0 mSdLazyCounter, 431 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 322 SdHoareTripleChecker+Invalid, 473 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 431 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:43,312 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 322 Invalid, 473 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 431 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-21 22:08:43,312 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2023-11-21 22:08:43,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 74. [2023-11-21 22:08:43,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 50 states have (on average 1.12) internal successors, (56), 52 states have internal predecessors, (56), 11 states have call successors, (11), 4 states have call predecessors, (11), 12 states have return successors, (28), 17 states have call predecessors, (28), 11 states have call successors, (28) [2023-11-21 22:08:43,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 95 transitions. [2023-11-21 22:08:43,323 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 95 transitions. Word has length 50 [2023-11-21 22:08:43,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:43,324 INFO L495 AbstractCegarLoop]: Abstraction has 74 states and 95 transitions. [2023-11-21 22:08:43,324 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 2.576923076923077) internal successors, (67), 23 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) [2023-11-21 22:08:43,324 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 95 transitions. [2023-11-21 22:08:43,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2023-11-21 22:08:43,326 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:43,326 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:43,359 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:43,549 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-11-21 22:08:43,550 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:43,550 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:43,550 INFO L85 PathProgramCache]: Analyzing trace with hash -267988016, now seen corresponding path program 3 times [2023-11-21 22:08:43,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:43,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1245106093] [2023-11-21 22:08:43,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:43,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:43,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:43,678 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:43,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:43,738 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:43,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:43,782 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2023-11-21 22:08:43,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:43,852 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:43,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:43,915 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:43,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:43,975 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-21 22:08:43,976 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:43,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1245106093] [2023-11-21 22:08:43,976 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1245106093] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:43,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [440700955] [2023-11-21 22:08:43,976 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-21 22:08:43,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:43,977 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:43,978 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:44,015 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-21 22:08:44,076 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-21 22:08:44,077 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:08:44,078 INFO L262 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-21 22:08:44,081 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:44,338 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-21 22:08:44,339 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:45,224 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-21 22:08:45,224 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [440700955] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:45,224 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:45,225 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 16] total 32 [2023-11-21 22:08:45,225 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1736768309] [2023-11-21 22:08:45,225 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:45,225 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2023-11-21 22:08:45,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:45,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2023-11-21 22:08:45,227 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=885, Unknown=0, NotChecked=0, Total=992 [2023-11-21 22:08:45,228 INFO L87 Difference]: Start difference. First operand 74 states and 95 transitions. Second operand has 32 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 28 states have internal predecessors, (63), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) [2023-11-21 22:08:45,655 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:45,655 INFO L93 Difference]: Finished difference Result 83 states and 106 transitions. [2023-11-21 22:08:45,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-21 22:08:45,656 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 28 states have internal predecessors, (63), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) Word has length 42 [2023-11-21 22:08:45,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:45,657 INFO L225 Difference]: With dead ends: 83 [2023-11-21 22:08:45,657 INFO L226 Difference]: Without dead ends: 74 [2023-11-21 22:08:45,658 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 68 SyntacticMatches, 6 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 354 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=196, Invalid=1286, Unknown=0, NotChecked=0, Total=1482 [2023-11-21 22:08:45,659 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 42 mSDsluCounter, 239 mSDsCounter, 0 mSdLazyCounter, 388 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 260 SdHoareTripleChecker+Invalid, 402 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 388 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:45,659 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 260 Invalid, 402 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 388 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-21 22:08:45,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2023-11-21 22:08:45,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 69. [2023-11-21 22:08:45,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 47 states have (on average 1.127659574468085) internal successors, (53), 49 states have internal predecessors, (53), 10 states have call successors, (10), 4 states have call predecessors, (10), 11 states have return successors, (24), 15 states have call predecessors, (24), 10 states have call successors, (24) [2023-11-21 22:08:45,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 87 transitions. [2023-11-21 22:08:45,671 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 87 transitions. Word has length 42 [2023-11-21 22:08:45,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:45,672 INFO L495 AbstractCegarLoop]: Abstraction has 69 states and 87 transitions. [2023-11-21 22:08:45,672 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 28 states have internal predecessors, (63), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) [2023-11-21 22:08:45,672 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 87 transitions. [2023-11-21 22:08:45,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-21 22:08:45,673 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:45,673 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:45,699 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:45,894 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-11-21 22:08:45,894 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:45,894 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:45,895 INFO L85 PathProgramCache]: Analyzing trace with hash -1480464800, now seen corresponding path program 4 times [2023-11-21 22:08:45,895 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:45,895 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [898499548] [2023-11-21 22:08:45,895 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:45,895 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:45,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:45,999 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:46,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:46,077 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:46,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:46,165 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:46,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:46,201 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2023-11-21 22:08:46,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:46,264 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:46,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:46,293 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-21 22:08:46,293 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:46,293 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [898499548] [2023-11-21 22:08:46,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [898499548] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:46,294 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1449573871] [2023-11-21 22:08:46,294 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-21 22:08:46,294 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:46,294 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:46,295 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:46,313 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-21 22:08:46,380 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-21 22:08:46,380 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:08:46,382 INFO L262 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-21 22:08:46,385 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:46,612 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-21 22:08:46,612 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:48,015 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 1 proven. 15 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-21 22:08:48,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1449573871] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:48,016 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:48,016 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 31 [2023-11-21 22:08:48,017 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [783055209] [2023-11-21 22:08:48,017 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:48,018 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2023-11-21 22:08:48,018 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:48,019 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2023-11-21 22:08:48,020 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=827, Unknown=0, NotChecked=0, Total=930 [2023-11-21 22:08:48,020 INFO L87 Difference]: Start difference. First operand 69 states and 87 transitions. Second operand has 31 states, 29 states have (on average 2.2758620689655173) internal successors, (66), 26 states have internal predecessors, (66), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) [2023-11-21 22:08:48,699 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:48,700 INFO L93 Difference]: Finished difference Result 93 states and 119 transitions. [2023-11-21 22:08:48,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-21 22:08:48,701 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 29 states have (on average 2.2758620689655173) internal successors, (66), 26 states have internal predecessors, (66), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) Word has length 43 [2023-11-21 22:08:48,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:48,702 INFO L225 Difference]: With dead ends: 93 [2023-11-21 22:08:48,703 INFO L226 Difference]: Without dead ends: 89 [2023-11-21 22:08:48,704 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 71 SyntacticMatches, 6 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 291 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=194, Invalid=1212, Unknown=0, NotChecked=0, Total=1406 [2023-11-21 22:08:48,705 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 17 mSDsluCounter, 302 mSDsCounter, 0 mSdLazyCounter, 479 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 480 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 479 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:48,705 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 325 Invalid, 480 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 479 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-21 22:08:48,706 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2023-11-21 22:08:48,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 77. [2023-11-21 22:08:48,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 52 states have (on average 1.1153846153846154) internal successors, (58), 54 states have internal predecessors, (58), 11 states have call successors, (11), 4 states have call predecessors, (11), 13 states have return successors, (29), 18 states have call predecessors, (29), 11 states have call successors, (29) [2023-11-21 22:08:48,733 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 98 transitions. [2023-11-21 22:08:48,733 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 98 transitions. Word has length 43 [2023-11-21 22:08:48,734 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:48,734 INFO L495 AbstractCegarLoop]: Abstraction has 77 states and 98 transitions. [2023-11-21 22:08:48,734 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 29 states have (on average 2.2758620689655173) internal successors, (66), 26 states have internal predecessors, (66), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) [2023-11-21 22:08:48,735 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 98 transitions. [2023-11-21 22:08:48,736 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-21 22:08:48,736 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:48,736 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:48,779 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:48,937 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-11-21 22:08:48,937 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:48,938 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:48,938 INFO L85 PathProgramCache]: Analyzing trace with hash -755000384, now seen corresponding path program 1 times [2023-11-21 22:08:48,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:48,938 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1624807951] [2023-11-21 22:08:48,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:48,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:48,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:49,055 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:49,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:49,124 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:49,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:49,231 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:49,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:49,257 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2023-11-21 22:08:49,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:49,320 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:49,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:49,357 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 5 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-11-21 22:08:49,357 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:49,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1624807951] [2023-11-21 22:08:49,357 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1624807951] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:49,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [334756648] [2023-11-21 22:08:49,358 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:49,358 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:49,358 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:49,360 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:49,365 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-21 22:08:49,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:49,471 INFO L262 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 27 conjunts are in the unsatisfiable core [2023-11-21 22:08:49,473 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:49,842 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 5 proven. 9 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-21 22:08:49,842 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:51,161 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 1 proven. 16 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-21 22:08:51,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [334756648] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:51,162 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:51,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 17] total 33 [2023-11-21 22:08:51,163 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1473652709] [2023-11-21 22:08:51,163 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:51,163 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2023-11-21 22:08:51,163 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:51,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2023-11-21 22:08:51,165 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=956, Unknown=0, NotChecked=0, Total=1056 [2023-11-21 22:08:51,165 INFO L87 Difference]: Start difference. First operand 77 states and 98 transitions. Second operand has 33 states, 30 states have (on average 2.2333333333333334) internal successors, (67), 26 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 9 states have return successors, (13), 9 states have call predecessors, (13), 12 states have call successors, (13) [2023-11-21 22:08:51,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:51,911 INFO L93 Difference]: Finished difference Result 119 states and 158 transitions. [2023-11-21 22:08:51,911 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-21 22:08:51,912 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 30 states have (on average 2.2333333333333334) internal successors, (67), 26 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 9 states have return successors, (13), 9 states have call predecessors, (13), 12 states have call successors, (13) Word has length 43 [2023-11-21 22:08:51,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:51,913 INFO L225 Difference]: With dead ends: 119 [2023-11-21 22:08:51,913 INFO L226 Difference]: Without dead ends: 115 [2023-11-21 22:08:51,915 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 69 SyntacticMatches, 6 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 351 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=271, Invalid=1799, Unknown=0, NotChecked=0, Total=2070 [2023-11-21 22:08:51,916 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 78 mSDsluCounter, 307 mSDsCounter, 0 mSdLazyCounter, 561 mSolverCounterSat, 60 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 331 SdHoareTripleChecker+Invalid, 621 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 561 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:51,916 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 331 Invalid, 621 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 561 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-21 22:08:51,917 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2023-11-21 22:08:51,931 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 81. [2023-11-21 22:08:51,932 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 55 states have (on average 1.1090909090909091) internal successors, (61), 56 states have internal predecessors, (61), 11 states have call successors, (11), 4 states have call predecessors, (11), 14 states have return successors, (32), 20 states have call predecessors, (32), 11 states have call successors, (32) [2023-11-21 22:08:51,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 104 transitions. [2023-11-21 22:08:51,934 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 104 transitions. Word has length 43 [2023-11-21 22:08:51,935 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:51,935 INFO L495 AbstractCegarLoop]: Abstraction has 81 states and 104 transitions. [2023-11-21 22:08:51,935 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 30 states have (on average 2.2333333333333334) internal successors, (67), 26 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 9 states have return successors, (13), 9 states have call predecessors, (13), 12 states have call successors, (13) [2023-11-21 22:08:51,935 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 104 transitions. [2023-11-21 22:08:51,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-21 22:08:51,937 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:51,938 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:51,962 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:52,153 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:52,154 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:52,154 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:52,154 INFO L85 PathProgramCache]: Analyzing trace with hash 648223744, now seen corresponding path program 2 times [2023-11-21 22:08:52,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:52,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1369898494] [2023-11-21 22:08:52,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:52,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:52,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:52,253 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:52,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:52,309 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:52,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:52,360 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:52,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:52,390 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2023-11-21 22:08:52,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:52,438 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:52,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:52,465 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-11-21 22:08:52,465 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:52,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1369898494] [2023-11-21 22:08:52,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1369898494] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:52,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1341538122] [2023-11-21 22:08:52,466 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-21 22:08:52,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:52,466 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:52,467 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:52,493 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-21 22:08:52,570 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-21 22:08:52,570 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:08:52,572 INFO L262 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 25 conjunts are in the unsatisfiable core [2023-11-21 22:08:52,576 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:52,704 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-21 22:08:52,704 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:53,615 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-21 22:08:53,615 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1341538122] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:53,615 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:53,615 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 14] total 22 [2023-11-21 22:08:53,616 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1391120091] [2023-11-21 22:08:53,616 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:53,616 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-11-21 22:08:53,616 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:53,617 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-11-21 22:08:53,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=400, Unknown=0, NotChecked=0, Total=462 [2023-11-21 22:08:53,618 INFO L87 Difference]: Start difference. First operand 81 states and 104 transitions. Second operand has 22 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 19 states have internal predecessors, (56), 9 states have call successors, (11), 1 states have call predecessors, (11), 6 states have return successors, (11), 5 states have call predecessors, (11), 9 states have call successors, (11) [2023-11-21 22:08:53,945 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:53,945 INFO L93 Difference]: Finished difference Result 108 states and 141 transitions. [2023-11-21 22:08:53,945 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-21 22:08:53,946 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 19 states have internal predecessors, (56), 9 states have call successors, (11), 1 states have call predecessors, (11), 6 states have return successors, (11), 5 states have call predecessors, (11), 9 states have call successors, (11) Word has length 43 [2023-11-21 22:08:53,946 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:53,947 INFO L225 Difference]: With dead ends: 108 [2023-11-21 22:08:53,947 INFO L226 Difference]: Without dead ends: 104 [2023-11-21 22:08:53,948 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 76 SyntacticMatches, 9 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 103 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=114, Invalid=642, Unknown=0, NotChecked=0, Total=756 [2023-11-21 22:08:53,949 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 18 mSDsluCounter, 218 mSDsCounter, 0 mSdLazyCounter, 345 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 239 SdHoareTripleChecker+Invalid, 345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 345 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:53,949 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 239 Invalid, 345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 345 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-21 22:08:53,949 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2023-11-21 22:08:53,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 88. [2023-11-21 22:08:53,958 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 60 states have (on average 1.1) internal successors, (66), 60 states have internal predecessors, (66), 11 states have call successors, (11), 4 states have call predecessors, (11), 16 states have return successors, (38), 23 states have call predecessors, (38), 11 states have call successors, (38) [2023-11-21 22:08:53,959 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 115 transitions. [2023-11-21 22:08:53,960 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 115 transitions. Word has length 43 [2023-11-21 22:08:53,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:53,960 INFO L495 AbstractCegarLoop]: Abstraction has 88 states and 115 transitions. [2023-11-21 22:08:53,960 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 19 states have internal predecessors, (56), 9 states have call successors, (11), 1 states have call predecessors, (11), 6 states have return successors, (11), 5 states have call predecessors, (11), 9 states have call successors, (11) [2023-11-21 22:08:53,961 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 115 transitions. [2023-11-21 22:08:53,962 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-11-21 22:08:53,962 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:53,962 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:53,989 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:54,177 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-11-21 22:08:54,178 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:54,178 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:54,178 INFO L85 PathProgramCache]: Analyzing trace with hash 575852236, now seen corresponding path program 3 times [2023-11-21 22:08:54,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:54,178 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [191448631] [2023-11-21 22:08:54,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:54,179 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:54,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:54,308 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:54,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:54,390 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:54,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:54,452 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:54,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:54,544 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:54,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:54,582 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2023-11-21 22:08:54,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:54,675 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:54,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:54,713 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-21 22:08:54,713 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:54,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [191448631] [2023-11-21 22:08:54,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [191448631] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:54,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [542454763] [2023-11-21 22:08:54,714 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-21 22:08:54,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:54,715 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:54,716 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:54,733 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-21 22:08:54,845 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-11-21 22:08:54,845 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:08:54,847 INFO L262 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 32 conjunts are in the unsatisfiable core [2023-11-21 22:08:54,854 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:08:55,336 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-21 22:08:55,336 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:08:57,927 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 3 proven. 30 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-21 22:08:57,927 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [542454763] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:08:57,928 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:08:57,928 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 20] total 41 [2023-11-21 22:08:57,928 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [287999015] [2023-11-21 22:08:57,928 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:08:57,930 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 41 states [2023-11-21 22:08:57,930 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:08:57,931 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2023-11-21 22:08:57,932 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=1499, Unknown=0, NotChecked=0, Total=1640 [2023-11-21 22:08:57,933 INFO L87 Difference]: Start difference. First operand 88 states and 115 transitions. Second operand has 41 states, 38 states have (on average 2.1052631578947367) internal successors, (80), 30 states have internal predecessors, (80), 14 states have call successors, (16), 1 states have call predecessors, (16), 10 states have return successors, (18), 13 states have call predecessors, (18), 14 states have call successors, (18) [2023-11-21 22:08:58,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:08:58,838 INFO L93 Difference]: Finished difference Result 177 states and 237 transitions. [2023-11-21 22:08:58,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-11-21 22:08:58,842 INFO L78 Accepts]: Start accepts. Automaton has has 41 states, 38 states have (on average 2.1052631578947367) internal successors, (80), 30 states have internal predecessors, (80), 14 states have call successors, (16), 1 states have call predecessors, (16), 10 states have return successors, (18), 13 states have call predecessors, (18), 14 states have call successors, (18) Word has length 51 [2023-11-21 22:08:58,842 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:08:58,844 INFO L225 Difference]: With dead ends: 177 [2023-11-21 22:08:58,844 INFO L226 Difference]: Without dead ends: 173 [2023-11-21 22:08:58,846 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 85 SyntacticMatches, 2 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 641 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=409, Invalid=2783, Unknown=0, NotChecked=0, Total=3192 [2023-11-21 22:08:58,848 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 80 mSDsluCounter, 339 mSDsCounter, 0 mSdLazyCounter, 588 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 361 SdHoareTripleChecker+Invalid, 638 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 588 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-21 22:08:58,848 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 361 Invalid, 638 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 588 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-21 22:08:58,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2023-11-21 22:08:58,863 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 90. [2023-11-21 22:08:58,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 62 states have (on average 1.096774193548387) internal successors, (68), 60 states have internal predecessors, (68), 11 states have call successors, (11), 4 states have call predecessors, (11), 16 states have return successors, (38), 25 states have call predecessors, (38), 11 states have call successors, (38) [2023-11-21 22:08:58,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 117 transitions. [2023-11-21 22:08:58,866 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 117 transitions. Word has length 51 [2023-11-21 22:08:58,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:08:58,866 INFO L495 AbstractCegarLoop]: Abstraction has 90 states and 117 transitions. [2023-11-21 22:08:58,867 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 41 states, 38 states have (on average 2.1052631578947367) internal successors, (80), 30 states have internal predecessors, (80), 14 states have call successors, (16), 1 states have call predecessors, (16), 10 states have return successors, (18), 13 states have call predecessors, (18), 14 states have call successors, (18) [2023-11-21 22:08:58,867 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 117 transitions. [2023-11-21 22:08:58,868 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-11-21 22:08:58,868 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:08:58,868 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:08:58,891 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-11-21 22:08:59,088 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:59,089 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:08:59,089 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:08:59,089 INFO L85 PathProgramCache]: Analyzing trace with hash 610835820, now seen corresponding path program 4 times [2023-11-21 22:08:59,089 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:08:59,090 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [30903959] [2023-11-21 22:08:59,090 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:08:59,090 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:08:59,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:59,236 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:59,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:59,321 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:59,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:59,378 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:59,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:59,474 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:08:59,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:59,496 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2023-11-21 22:08:59,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:59,547 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:08:59,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:08:59,602 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 9 proven. 13 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-21 22:08:59,602 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:08:59,602 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [30903959] [2023-11-21 22:08:59,602 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [30903959] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:08:59,602 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1302698259] [2023-11-21 22:08:59,602 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-21 22:08:59,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:08:59,603 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:08:59,604 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:08:59,625 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-21 22:08:59,729 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-21 22:08:59,729 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:08:59,731 INFO L262 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-21 22:08:59,733 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:09:00,081 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-21 22:09:00,081 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-21 22:09:01,832 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 5 proven. 28 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-21 22:09:01,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1302698259] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-21 22:09:01,833 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-21 22:09:01,833 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 20] total 36 [2023-11-21 22:09:01,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1939000916] [2023-11-21 22:09:01,833 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-21 22:09:01,833 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2023-11-21 22:09:01,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-21 22:09:01,834 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2023-11-21 22:09:01,835 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=1146, Unknown=0, NotChecked=0, Total=1260 [2023-11-21 22:09:01,835 INFO L87 Difference]: Start difference. First operand 90 states and 117 transitions. Second operand has 36 states, 33 states have (on average 2.272727272727273) internal successors, (75), 27 states have internal predecessors, (75), 13 states have call successors, (15), 1 states have call predecessors, (15), 9 states have return successors, (16), 11 states have call predecessors, (16), 13 states have call successors, (16) [2023-11-21 22:09:02,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-21 22:09:02,591 INFO L93 Difference]: Finished difference Result 131 states and 177 transitions. [2023-11-21 22:09:02,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-11-21 22:09:02,592 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 33 states have (on average 2.272727272727273) internal successors, (75), 27 states have internal predecessors, (75), 13 states have call successors, (15), 1 states have call predecessors, (15), 9 states have return successors, (16), 11 states have call predecessors, (16), 13 states have call successors, (16) Word has length 51 [2023-11-21 22:09:02,593 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-21 22:09:02,594 INFO L225 Difference]: With dead ends: 131 [2023-11-21 22:09:02,594 INFO L226 Difference]: Without dead ends: 127 [2023-11-21 22:09:02,595 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 85 SyntacticMatches, 7 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 453 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=335, Invalid=2215, Unknown=0, NotChecked=0, Total=2550 [2023-11-21 22:09:02,596 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 51 mSDsluCounter, 301 mSDsCounter, 0 mSdLazyCounter, 672 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 323 SdHoareTripleChecker+Invalid, 698 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 672 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-21 22:09:02,597 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 323 Invalid, 698 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 672 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-21 22:09:02,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-11-21 22:09:02,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 69. [2023-11-21 22:09:02,607 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 47 states have (on average 1.127659574468085) internal successors, (53), 49 states have internal predecessors, (53), 10 states have call successors, (10), 4 states have call predecessors, (10), 11 states have return successors, (22), 15 states have call predecessors, (22), 10 states have call successors, (22) [2023-11-21 22:09:02,607 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 85 transitions. [2023-11-21 22:09:02,608 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 85 transitions. Word has length 51 [2023-11-21 22:09:02,608 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-21 22:09:02,608 INFO L495 AbstractCegarLoop]: Abstraction has 69 states and 85 transitions. [2023-11-21 22:09:02,608 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 33 states have (on average 2.272727272727273) internal successors, (75), 27 states have internal predecessors, (75), 13 states have call successors, (15), 1 states have call predecessors, (15), 9 states have return successors, (16), 11 states have call predecessors, (16), 13 states have call successors, (16) [2023-11-21 22:09:02,609 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 85 transitions. [2023-11-21 22:09:02,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-21 22:09:02,609 INFO L187 NwaCegarLoop]: Found error trace [2023-11-21 22:09:02,610 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-21 22:09:02,630 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-11-21 22:09:02,825 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:09:02,826 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-21 22:09:02,826 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-21 22:09:02,826 INFO L85 PathProgramCache]: Analyzing trace with hash -755482820, now seen corresponding path program 5 times [2023-11-21 22:09:02,826 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-21 22:09:02,826 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [609992295] [2023-11-21 22:09:02,826 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-21 22:09:02,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-21 22:09:02,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:09:02,940 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:09:02,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:09:02,996 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:09:02,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:09:03,080 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-21 22:09:03,082 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:09:03,117 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2023-11-21 22:09:03,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:09:03,177 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:09:03,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:09:03,215 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-21 22:09:03,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-21 22:09:03,244 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 5 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-21 22:09:03,244 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-21 22:09:03,244 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [609992295] [2023-11-21 22:09:03,245 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [609992295] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-21 22:09:03,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2072254188] [2023-11-21 22:09:03,245 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-11-21 22:09:03,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-21 22:09:03,245 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 [2023-11-21 22:09:03,250 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-21 22:09:03,265 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_6619abbb-9e4a-454d-8c87-6b51c4386b5e/bin/uautomizer-verify-bycVGegfSx/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-11-21 22:09:03,388 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2023-11-21 22:09:03,389 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-21 22:09:03,390 INFO L262 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-21 22:09:03,392 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-21 22:09:03,622 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 5 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-21 22:09:03,622 INFO L327 TraceCheckSpWp]: Computing backward predicates...